minekirito的个人博客分享 http://blog.sciencenet.cn/u/minekirito

博文

数据挖掘领域必须熟悉的十大经典算法其一——Apriori算法

已有 2776 次阅读 2019-1-22 20:49 |个人分类:数据挖掘算法介绍|系统分类:科研笔记| Apriori

国际权威学术组织IEEE International Conference on Data Mining评出了数据挖掘领域的十大经典算法。在真正进入数据挖掘算法的学习之前,这十个在该领域产生了深远影响的算法应该优先学习一下。    

        注:本文是对《大数据、数据挖掘与智慧运营综述》第一章的重新梳理,并加入了自己的理解。每个算法只是简单介绍,日后会详细研究。

   

     Apriori算法是最有影响力的挖掘布尔关联规则的算法,就是挖掘数据中潜在的关联关系。例如著名的购物篮问题中顾客在买完尿布之后通常会买啤酒。作为第一个关联规则挖掘算法,它开创性的使用了基于支持度的剪枝技术。该算法的核心是基于两段频集思想的递推算法。(其中有很多数理统计相关的知识)频集是指所有支持度大于最小支持度的项。在频集中,所有置信度大于最小置信度的规则成为强关联规则。

u=2204244812,2285795706&fm=11&gp=0.jpg

    首先,先找出所有的频集。然后再由频集找出强规则。大部分的计算都集中在第一步,故对于Apriori的效率优化也集中在第一步。

    产生候选项时,有一个先验原理。如果一个项集是频繁的,则他的子集也是频繁的。相反,如果一个项集是非频繁的,则包含它的所有超集一定是非频繁的。Apriori会将所有非频繁的集剪掉

    近些年对于Apriori的优化主要从一下几个方面入手:

    1.      减少比较次数。相同项目之间的比较太多,如何避免重复的比较从而提高算法效率?

    2.      减少候选项集数。在寻找频集的过程中,原有的方法先利用已知的(k-1)维的频集来找出候选的k维频集又要回去穷举一遍候选项集是不是频集。如果可以减少遍历的次数(利用hash函数),或者更直接的生成候选频集那么就可以提高算法的效率。

    3.      压缩原始数据库,对数据库的项目进行预修剪,减少时间开销。

    近两年关于Apriori的研究相比其他算法有所减少,希望日后可以看到优秀的新方法。



 



https://blog.sciencenet.cn/blog-3401624-1158537.html

上一篇:数据挖掘领域必须熟悉的十大经典算法其三——SVM
下一篇:数据压缩算法——无损压缩
收藏 IP: 180.212.235.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 23:14

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部