关联分析

1）支持度计算

a) 项集: 包含0个或者多个项(特征) 的集合被称为项集。如果一个项集包含k个项则称为k-项集。例如， {啤酒，尿布，牛奶} 是一个 3-项集

b) 事务: 可以理解为一个样本

c) 支持度计数: 在所有事务中该项集出现的次数。例如，{啤酒，尿布，牛奶} 的支持度为 2

• 支持度用于确定给定数据集的频繁程度 [ 支持度计数 / 事务总数 ]

  （考虑规则{牛奶，尿布}->{啤酒}）{牛奶，尿布，啤酒}的支持度为 **2/5=0.4 ** (其中 5 为 事务总数 )

• 置信度确定 在考虑规则X->Y，Y在包含X的事务中出现的频繁程度

  （考虑规则{牛奶，尿布}->{啤酒}）{牛奶，尿布}的支持度计数为 3 ,则该规则的置信度为 2/3

image

2. Aprori 算法

• 原理（先验原理）: 如果一个项集是频繁的，那么它的子集一定也是频繁的；相反，如果项集{a}是非频繁的，那么它的所有超集也一定是非频繁的。

• 思路：

  • 初始化所有的1-项集，计算其支持度技术，过滤支持度计数小于阈值的项
  • 构建所有满足支持度计数阈值的 k-项集
  • 根据 目标项 依次遍历整个k-项集网络（ 从网络的底部，即最大k-项集，开始 ），找到包含目标项的k-项集{related_items,target_item} 及 关联项的k-1项集{related_items}，计算规则{related_items}->{target_item}的 置信度 ，过滤小于置信度阈值的规则

• 实现：

  • 数据结构:

    • 项集网络：

      Fks = [fk_1,fk_2,] = [[[(a1,),w1]],[[(a1,a2,),w2],],]

    • k-项集：

      Fk = [[(a1,...,an),w],]

      • 说明

        fk的每个元素由一个 tuple类型的项集 和其对应的 支持度计数 构成

    • 说明：为了防止重复构建相同的项集，如由{1,2}和{2,3}构建的项集 以及 由{1,2}和{1,3}构建的项集，对每个k-1项集的集合做字典排序( 依据字母顺序或者数字顺序 )

  • k-项集的构建

  def apriori_gen(Fk,N):  # Fk为k-1项集的集合，N为总项数
    # k-1项集的总数
    lenFk = len(Fk)
    # k-1
    lenfk = len(Fk[0][0])
    # 每个k-1项集对应的k项集的最大数量
    step = N - lenfk
  
    ind = 0
    new_Fk = []
    for _fk,_w in Fk:
        for _i in range(ind,ind+step):
            # 输入的k-1项集是剪枝后的项集，项集总数会小于N和k-1的组合数
            if _i > lenFk - 1:
                break
            if Fk[_i][0] == _fk:
                continue
            # 取出前k-2项相同的k-1项集合并成k项集
            if Fk[_i][0][:lenfk-1] != _fk[:lenfk-1]:
                break
            new_fk = tuple(sorted(set(_fk).union(Fk[_i][0])))
            new_Fk.append([new_fk,-1])
        ind += 1
    return new_Fk
  

  • k项集的剪枝

  def Fk_optimize(Fk,minsup):
    Fk_new = deepcopy(Fk)
    for fk in Fk:
        if fk[1] < minsup:
            Fk_new.remove(fk)
    return Fk_new
  

  • 匹配包含目标项的k项集及对应的k-1项集

   def find_fk_target(Fk, deepth, target):
    if type(target) == str:
        for _fk, _w in Fk[deepth]:
            if target in _fk:
                return _fk, _w
        return None, None
    elif type(target) == tuple:
        for _fk, _w in Fk[deepth]:
            if _fk == target:
                return _w
    else:
        assert False, 'please check the type of target which must be str or tuple'
  

  • apriori算法

  def apriori(data,targets):
    # 支持度计数阈值
    minsup = 20
    # 项总数（特征总数）
    N = data.shape[1]
    # 置信度阈值
    minconf = 0.3
  
    Fk = []
    # 初始化1-项集 & 剪枝
    Fk_1 = [[(_col,), len(data[data.loc[:,_col]==1])] for _col in sorted(data.columns)]
    Fk_1 = Fk_optimize(Fk_1, minsup)
    fks_1 = [_fk[0] for _fk, _w in Fk_1]
  
    # 频繁项集网络的构建（遍历）
    fk = Fk_1
    while len(fk) > 0:
        Fk.append(fk)
        fk = apriori_gen(fk,N)
        # 在数据集中找出对应特征均为1的行的总数作为支持度计数
        fk = [[_fk,data[data.loc[:, list(_fk)].sum(1) == len(_fk)].shape[0]]
            for _fk, _w in fk]
        fk = Fk_optimize(fk, minsup)
  
    # 规则的构建
    Rules = []
    for _target in targets:
        # 如果目标项不在初始的1-项集中
        if _target not in fks_1:
            continue
        # 从Fk项集网络的底部开始倒序遍历
        for deepth in reversed(range(1,len(Fk))):
            target_fk, target_w = find_fk_target(Fk, deepth, _target)
            if target_fk != None:
                # 抽取规则前件（关联项集{related_items}）
                _fk = list(target_fk)
                _fk.remove(_target)
                _fk = tuple(_fk)
                # 计算规则的置信度
                target_conf = target_w / find_fk_target(Fk,deepth-1, _fk)
                if target_conf > minconf:
                    Rules.append([_target, _fk, target_conf])
  
    return Rules