Data Mining 笔记关联规则之Apriori算法笔记

一、前言
上篇文章中对频繁项和关联规则做了一般性描述。知道关联规则的挖掘其实就是从事务、关系数据中发现频繁项集、再考察项之间的关联。
项集itemset生成是一个很费力力气的事情,如果事务中有d项待考察,则理论上会有2^d个candidate itemset。
generate-itemset

实际上并不是并不是所有的都candidate itemsets都需要考察。因为频繁项集有这样的性质

  • ?性质1:频繁项集的子集必为频繁项集。
  • ?性质2:非频繁项集的超集一定是非频繁的。

?二、Apriori算法

Apriori算法运用性质1,通过已知的频繁项集构成长度更大的项集,并将其称为潜在频繁项集。潜在频繁k项集的集合Ck?是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度,而不必计算所有不同项集的支持度,因此在一定程度上减少了计算量。
generate-frequent-itemset
Apriori算法将发现关联规则的过程分为两个步骤:
  1. 检索出事务数据库中的所有频繁项集,即支持度不低于用户设定最小支持度计数阈值的项集;
  2. 利用频繁项集构造出满足用户最小信任度的规则。

三、Apriori算法的伪代码:

挖掘并产生所有频繁项集是该算法的核心,占整个计算量的大部分。

aprioro example
The Apriori Algorithm—An Example

?四、Apriori实现中改进点

Major computational challenges
  • Multiple scans of transaction database
  • Huge number of candidates
  • Tedious workload of support counting for candidates
Improving Apriori: general ideas
  • Reduce passes of transaction database scans
  • Shrink number of candidates
  • Facilitate support counting of candidates

详细改进方法参照文中描述。

View 06FPBasic.ppt and other presentations by idouba.

完。

 

原创文章。为了维护文章的版本一致、最新、可追溯,转载请注明: 转载自idouba

本文链接地址: Data Mining 笔记关联规则之Apriori算法笔记


, , ,

Trackbacks/Pingbacks

  1. Data Mining 笔记&实践 | 学而时习之 - 2016年4月6日

    […] Data Mining 笔记关联规则之Apriori算法笔记 […]

发表评论