Apriori算法

Apriori算法2016年07月15日黄维基本概念•Apriori算法是关联规则里一项基本算法。•关联规则的目的就是在一个数据集中找出项与项之间的关系，也被称为购物篮分析(MarketBasketanalysis)，因为“购物篮分析”很贴切的表达了适用该算法情景中的一个子集。•算法功能：为了挖掘出事物之间的依赖性或关联性。基本概念•项集:项的集合，包含k个项的项集称为k项集。•频繁项集:项集的相对支持度满足预定义的最小支持度阈值。（绝对支持度满足对应的最小支持度计数阈值）•频繁模式（frequentpattern）：是频繁地出现在数据集中的模式（项集、子序列、子结构）。基本概念•项集：面包+牛奶•子序列：PC电脑-数码相机-内存卡•子结构：有多种结构形式，如项集+子序列的结合购物篮分析例子关联规则：例：购买计算机同时会购买杀毒软件的关联规则如下：computer=antivirus_software[support=2%;confidence=60%]AB支持度置信度规则的支持度和置信度:支持度：support(A=B)=P(A∪B)=2%（A和B同时发生的概率）置信度：confidence(A=B)=P(B|A)=60%（在A事件中同时发生B的概率）关联规则挖掘过程•1、找出所有的频繁项集项集的出现次数≥最小支持度计数•2、由频繁项集产生强关联规则这些规则必须满足最小支持度和最小置信度由于第二步的开销远低于第一步，所以挖掘关联规则的总体性能由第一步决定。Apriori算法：是一种发现频繁项集的基本算法先验性质：频繁项集的所有非空子集也一定是频繁的。Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，(k-1)项集用于探索k项集。核心算法过程1、扫描数据库D，计算出各个1项集的支持度，得到频繁1项集的集合。2、连接步：为找出Lk（所有的频繁k项集的集合），通过将Lk-1（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作Ck。3、剪枝步：通过扫描所有的事务，确定Ck中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。为了压缩Ck,可以利用Apriori性质：任一频繁项集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。TID商品ID的列表T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3例子：AllElectronics某分店的事务数据1.扫描D，对每个候选计数(设min_sup=2)项集支持度计数{I1}{I2}{I3}{I4}{I5}67622项集支持度计数{I1}{I2}{I3}{I4}{I5}67622与最小支持度计数比较C1L12.由L1产生候选C2项集支持度计数{I1,I2}{I1,I3}{I1,I4}{I1,I5}{I2,I3}{I2,I4}{I2,I5}{I3,I4}{I3,I5}{I4,I5}4412422010与最小支持度计数比较C2L2项集{I1,I2}{I1,I3}{I1,I4}{I1,I5}{I2,I3}{I2,I4}{I2,I5}{I3,I4}{I3,I5}{I4,I5}扫描D，对每个候选计数C2项集支持度计数{I1,I2}{I1,I3}{I1,I5}{I2,I3}{I2,I4}{I2,I5}4424223.由L2产生候选C3项集支持度计数{I1,I2,I3}{I1,I2,I5}22与最小支持度计数比较C3L3项集{I1,I2,I3}{I1,I2,I5}扫描D，对每个候选计数C3项集支持度计数{I1,I2,I3}{I1,I2,I5}22Apriori算法的不足正如我们已经看到的，在许多情况下，Apriori算法的候选产生-检查方法显著压缩了候选项集的规模，并产生很好的性能。然而，它可能受两种非平凡开销的影响。谢谢！