数据挖掘-Aprior-Algorithm

写在前面的话

• Aprior Algorithm(先验算法)，它是我在数据挖掘这门课学的第一个算法，由于当时觉得数据挖掘是一门很深奥的学科，所以在学习之前就对它心怀敬畏之心，学起来压力也是很大。不过后来弄懂了之后觉得理解思路也不是很难。

Aprior Algorithm

算法背景

• Aprior Algorithm是布尔关联规则里的一项基本算法，它是由Rakesh Agrawal和Ramakrishnan Srikant两位博士在1994年提出的。所谓关联，反映的是一个事件和其他事件之间的依赖或相关程度，它包括事件之间的频繁模式、相关性或因果结构，在数据挖掘中它通常也被称为“购物篮分析”(Market Basket analysis)。
• 关于“购物篮分析”还有一个很有名的故事：美国的妈妈经常叫丈夫到超市帮孩子买尿布，而作为一个男人，由于心理作用，他们觉得自己只是买了尿布就往家提总感觉有点别扭，所以在超市他们顺便提上啤酒这种看上去比较狼性的商品。这一有趣的现象慢慢被超市经理发现了，后来超市就在尿布的旁边摆上了啤酒，这样就省得丈夫们走来走去，可以随手一提就是自己想要的2样东西，结果超市的尿布和啤酒都大卖了。

算法原理

Aprior的基本思想

• 频繁项集的任何子集也一定是频繁的。

基本概念和定义

• 资料库(Transaction Database):存储着二维结构的记录集。定义为：D
• 所有项集(Items):所有项目的集合。定义为：I
• 记录(Transaction):资料库里的子集。定义为：T (T ∈ D)
• 项集(Itemset)：同时出现的项的集合。定义为：k-itemset(k项集)
• 支持度(Suppor)：定义为supp(X) = occur(x) / count(D) = P(X)
• 置信度(Confidence):定义为conf(A->B) = supp(A∪B)/supp(A) = P(B|A)

算法步骤：

• Aprior Algorithm算法分2步进行：
  • 扫描数据库，累计每个项的计数，找出所有频繁数据项集，即找出所有支持度超过指定阈值的数据项集。
  • 利用频繁数据项集，生成候选的关联规则，并验证其可信度。如果可信度超过指定阈值，则该候选关联规则为要找的关联规则。

算法应用

• 例子：以下为AllElectronics的事务数据库D。该数据库有9个事务，即|D|=9。
  • (1).在算法的第一次迭代时，每个项都是候选1项集的集合C1的成员。算法简单地扫描所有的事务，对每个项的出现次数进行计数。
  • (2).假设最小支持度计数为2，即min_sup = 2，可以确定频繁1项集的集合L1.它由满足最小支持度的候选1项集组成。在我们的例子中，C1中的所有候选都满足最小支持度。
  • (3).为了发现频繁2项集的集合L2，算法使用连接L1∞L1产生候选2项集的集合C2.然后进行剪枝，在本例中，没有候选从C2中删除，因为这些候选的每个子集也是频繁的。
  • (4).扫描D中事务，累计C2中的每个候选项集的支持计数。
  • (5).然后，确定频繁2项集的集合L2，它由C2中满足最小支持度的候选2项集组成。
  • (6).如此循环，直到找出所有的频繁项集。

 

• 算法的伪代码： 

算法的不足与改进

算法的不足

• 可能产生大量的候选集，没有排除不应该参与组合的元素
• 需要重复扫描数据库，因此如果挖掘数据仓库数据量很大，应用此算法每次迭代产生候选项集用来统计其支持度就需要花费很多时间，而这种代价是随着数据的记录数的增加呈现几何级数的增加。

算法的改进

• 基于散列的技术
• 事务压缩
• 划分
• 抽样
• 动态项集计数
• FP-growth tree

后记

• 后记我想首先叹一声：我的妈( ⊙ o ⊙ )啊！原来写一篇这样的算法总结是那么的累！！！我真的是累趴了！！！请叫我大四狗！

• 本次博文真所谓是我经历千辛万苦的心血，边写边哭，那资料东找西找，各种躁动，思路不断短路，终于还是OK的完成了。其实我想说，我太渣了。

• 还有一点，我发现我越来越喜欢抄教材的内容了。

• 参考链接wikipedia