|||
国际权威学术组织IEEE International Conference on Data Mining评出了数据挖掘领域的十大经典算法。在真正进入数据挖掘算法的学习之前,这十个在该领域产生了深远影响的算法应该优先学习一下。
注:本文是对《大数据、数据挖掘与智慧运营综述》第一章的重新梳理,并加入了自己的理解。每个算法只是简单介绍,日后会详细研究。
Apriori算法是最有影响力的挖掘布尔关联规则的算法,就是挖掘数据中潜在的关联关系。例如著名的购物篮问题中顾客在买完尿布之后通常会买啤酒。作为第一个关联规则挖掘算法,它开创性的使用了基于支持度的剪枝技术。该算法的核心是基于两段频集思想的递推算法。(其中有很多数理统计相关的知识)频集是指所有支持度大于最小支持度的项。在频集中,所有置信度大于最小置信度的规则成为强关联规则。
首先,先找出所有的频集。然后再由频集找出强规则。大部分的计算都集中在第一步,故对于Apriori的效率优化也集中在第一步。
产生候选项时,有一个先验原理。如果一个项集是频繁的,则他的子集也是频繁的。相反,如果一个项集是非频繁的,则包含它的所有超集一定是非频繁的。Apriori会将所有非频繁的集剪掉
近些年对于Apriori的优化主要从一下几个方面入手:
1. 减少比较次数。相同项目之间的比较太多,如何避免重复的比较从而提高算法效率?
2. 减少候选项集数。在寻找频集的过程中,原有的方法先利用已知的(k-1)维的频集来找出候选的k维频集又要回去穷举一遍候选项集是不是频集。如果可以减少遍历的次数(利用hash函数),或者更直接的生成候选频集那么就可以提高算法的效率。
3. 压缩原始数据库,对数据库的项目进行预修剪,减少时间开销。
近两年关于Apriori的研究相比其他算法有所减少,希望日后可以看到优秀的新方法。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-3-29 23:14
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社