关联分析 - 简书

1）支持度计算

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

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

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

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

（考虑规则{牛奶，尿布}->{啤酒}）{牛奶，尿布，啤酒}的支持度为 **2/5=0.4 ** (其中 5 为 事务总数 )
置信度确定在考虑规则X->Y，Y在包含X的事务中出现的频繁程度

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

image

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