Apriori_FP

Apriori 算法

1. 频繁项集：经常出现在一块的物品的集合；
2. 关联规则（association rules）暗示两种物品之间可能存在很强的关系。
3. 频繁的定义：支持度、可信度
   1. 支持度：项集{豆奶，尿布}在记录中的出现频率
      有多少比例的交易记录包含该集合
   2. confidentce： 关联规则{尿布}->{葡萄酒}的可信度为：“支持度({尿布, 葡萄酒})/支持度({尿布})”。
   • 表示对于包含”尿布”的规则，规则对其中（可信度）%的记录适用。

原理

1. 假设想找到支持度大于0.8的所有项集；4种物品的集合要遍历数据15次

   对于包含N种物品的数据集共有2N-1种项集组合。

2. 连线表明两个或者更多集合可以组合成一个更大集合
   )

• 某个项集是频繁的，那么它的所有子集也是频繁的
  )

算法

1. 发现频繁项集：输入：最小支持度，数据集

2. 生成候选集

   1. 从{1个元素集合}计数数据集中出现次数
   2. 算每个元素出现频次，超出阈值的保留

   3. 按计算k=2;k-2求k-2个项相同的并集

      a[:k-2]==b[:k-2]
      .append(a|b)#|set的并，出现在a或b中的元素#a.union(b)

   4. 计算{2个元素的集合}的频率(1、2) //+1个元素的集合

   5. 当3.的并集为空 得到

      #L[0] 1项的频繁集[1]两项 [2]3项的 [3]4 [4]空集
      #都是支持度超过support的子集

3. 关联规则：

   有一个频繁项集{豆奶, 莴苣}，那么就可能有一条关联规则“豆奶 ➞ 莴苣”。
   P ➞ H的可信度定义为support(P | H)/support(P)。

   1. 生成一个可能的规则列表，然后测试每条规则的可信度。如果可信度不满足最小要求，则去掉该规则。
      )
   2. 从一个频繁项集开始，接着创建一个规则列表，其中规则右部只包含一个元素，然后对这些规则进行测试。接下来合并所有剩余规则来创建一个新的规则列表，其中规则右部包含两个元素。这种方法也被称作分级法。

FP-growth FP树-频繁集-自动补全

• FP只需要对数据库进行两次扫描，Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁，

FP树（频繁模式（Frequent Pattern））编码数据集

1. 一个元素项可以在一棵FP树中出现多次。
2. FP树会存储项集的出现频率，而每个项集会以路径的方式存储在树中。
3. 存在相似元素的集合会共享树的一部分。

算法

1. 对原始数据集扫描两遍。第一遍对所有元素项的出现次数进行计数。
2. 只考虑频繁元素