Apriori算法以及ECLAT算法
算法起源
关联规则挖掘是数据挖掘中最活跃的研究方法之一 ，最早是由 Agrawal 等人提出的。1993最初提出的动机是针对购物篮分析问题提出的，其目的是为了发现交易数据库中不同商品之间的联系规则。这些规则刻画了顾客购买行为模式，可以用来指导商家科学地安排进货，库存以及货架设计等。之后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。
算法介绍
以超市交易记录为例
-
关联规则举例：
{Diaper} --> {Beer},
{Milk, Bread} --> {Eggs,Coke},
{Beer, Bread} --> {Milk},
概念引入
项集：一个或多个项的集合
例如：{Milk，Bread,Diaper}，而Milk,Bread,Diaper就为对应项集中的项
k-项集：包含k个项的集合
支持度计数：一个项集出现的频数
例如：
支持度：数据集中包含该项集的记录所占的比例
例如：
频繁项集：一个项集的支持度大于等于最小阈值
例如：最小阈值为2
则{Milk,Bread,Diaper}为频繁项集
关联规则定义
关联规则
关联规则的形式：X->Y (其中X,Y都为项集)
例如：
{Milk，Diaper}->{Beer}
规则评估度量
关联规则的支持度
数据集中包含X,Y所占的比例
关联规则的置信度
交易集包含X和Y的交易数和包含X的交易数之比
强关联规则
关联规则的支持度和置信度都大于等于最小支持度以及最小置信度(或直接由频繁项集D产生的关联规则X->Y，其置信度大于等于置信度阈值)
举例：
例如:
Apriori基本思想
- 找到所有的频繁项集
- 由频繁项集找到所有的强关联规则
目标
给定一个事务集T，关联规则挖掘的目标是找到所有规则满足以下要求：
- support>=minsup threshold
- confidence>=minconf threshold
Brute-force 方法：
- 列出所有可能的关联规则
- 计算每条规则的支持度以及置信度
- 如果一些规则不满足minsup以及minconf则删除
Two-step 方法：
①找出频繁项集
找出所有的频繁项集，即support>=minsup
②规则生成
从频繁项集中找出高置信度的规则
（规则即对每个频繁项集进行一个二分）
频繁项集性质引入：
任何一个频繁项集的子集是频繁的，反之不一定
例如：假定支持度计数为2
①任何一个事务中包含{beer,diaper,milk}一定包含{beer,diaper}
②{beer, diaper, milk} 是频繁的，可推出 {beer, diaper} 也是频繁的
③{Milk,Coke}是频繁的，其支持度计数为2，而{Bread,Milk,Coke}不是频繁的，其支持度计数为1
候选项集的产生方法（Fk−1×Fk−1方法）
当它们的前k-2个项都相同时，合并一对频繁k-1项集
K-2集合项顺序也要相同，并确保是频繁的
如何找频繁项集
|
如何找强关联规则： 假设最小支持度为2，X={I1,I2,I5}为一个频繁项集。可以由X产生哪些关联规则呢？ X的非空子集为{I1,I2},{I1,I5},{I2,I5},{I1},{I2},{I5}结果关联规则如下（每个都列出了置信度）： {I1,I2}=>I5 confidence=2/4=50% {I1,I5}=>I2 confidence=2/2=100% {I2,I5}=>I1 confidence=2/2=100% I1=>{I2,I5} confidence=2/6=33% I2=>{I1,I5} confidence=2/7=29% I5=>{I1,I2} confidence=2/2=100% L为频繁项集，如果|L|=k,则有2k-2条候选关联规则(除去L->ᴓ和ᴓ->L)
关联规则产生： 如何从频繁项集有效的产生关联规则？ 例如：L={A,B,C,D} 如果ABC -> D不满足最小置信度，则前缀是{A,B,C}子集的都可以被剪枝 关联规则生成如下：
关联规则产生： 首先产生右边只有1个元素的规则；接着产生右边为2个元素的规则，以此类推
算法应用： 经典的关联规则数据挖掘算法Apriori 算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值
Apriori算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他
算法改进： ECLAT: 先举例说明使用垂直数据格式挖掘频繁项集。 考虑表1的事务数据库D的水平数据格式。扫描一次该数据集就可以把它转换成表2所生死的垂直数据格式。
表1
表2 表1事务数据库D的垂直数据格式 通过取每对频繁项的TID集的交，可以在该数据集上进行挖掘。设最小支持度计数为2。由于表2的每个项都是频繁的，因此总共进行10次交运算，导致8个非空2项集，如表3所示。注意，项集｛I1，I4｝和｛I3，I5｝都只包含一个事务，因此它们都不属于频繁2项集的集合。
表3 垂直数据格式的2项集 根据先验性质，一个给定的3项集是候选3项集，仅当它的每一个2项集子集都是频繁的。这里候选产生过程将仅产生两个3项集：｛I1，I2，I3｝，｛I1，I2，I5｝。通过取这些候选3项集任意对应2项集的TID集的交，得到表4，其中只有两个频繁3项集：｛I1，I2，I3：2｝和｛I1，I2，I5：2｝
Eclat算法最大的特点便是倒排思想，也就是生成一个统计每一个项在哪些事务中出现过的倒排表，表中的每一行由项和它对应的TID集组成，TID集即包含此项目的所有事务的集合。
Eclat算法挖掘频繁项集的过程如下： （1）通过扫描一次数据集，把水平格式的数据转换成垂直格式； （2）项集的支持度计数简单地等于项集的TID集的长度； （3）从k=1开始，可以根据先验性质，使用频繁k项集来构造候选（k+1）项集； （4）通过取频繁k项集的TID集的交，计算对应的（k+1）项集的TID集。 （5）重复该过程，每次k增加1，直到不能再找到频繁项集或候选项集。 Eclat算法产生候选项集的理论基础是：频繁K-项集可以通过或运算生成候选的K+1-项集，频繁K-项集中的项是按照字典序排列，并且进行或运算的频繁K-项集的前K-1个项是完全相同的。 Eclat算法除了在产生候选（k+1）项集时利用先验性质外，另一个优点是不需要扫描数据库来确定（k+1）项集的支持度（k>=1），这是因为每个k项集的TID集携带了计算支持度的完整信息。然而，TID集可能很长，需要大量的内存空间，长集合的交运算还需要大量的计算时间。
ECLAT与Apriori算法的对比如下：
注：第二步以及第三步已经把不频繁项集给删除了，第四步，即频繁四项集只能构成{I1,I2,I3,I5}且不频繁，则频繁项集查找结束 Apriori算法与ECLAT算法的比较： Apriori算法找频繁项集需要依次扫描数据库，扫描时间消耗大，而ECLAT算法只需要计算各个频繁项集出现在哪些交易记录中，可以缩短扫描时间，提高时间效率。 ECLAT与Apriori实验对比: 红线：eclat 蓝线：apriori
|