关联规则挖掘理论和算法（数据挖掘十大算法---Apriori算法）
发布时间
阅读量：
阅读量
一、（Apriori）发现频繁项目集
通过用户给定的 最小支持度 ，寻找所有频繁项目集（满足Support不小于Minsupport的所有项目子集）
逐层发现算法，按照项集的长度由下到大逐级进行，并最后发现频繁几项集
项（Item）
购物篮（Transcation）：交易
项集（Itemset）：所有项的集合
K项集：在集合中包含K个项的项集
支持度：support(x)=count(x) / |D| *100%
——x出现的概率
count(x):一个项集x在数据库中出现的次数x
D：数据库（交易的个数）
置信度：confidence(X->Y) = support(X->Y) / support(X) *100%
support(X)=support(X∩Y)
———X出现了的同时Y出现的概率
算法实现：
输入：数据库D；最小支持度minsup_count
输出：频繁项目集L
样本事务数据库| TID | Itemset |
|---|---|
| 1 | A,B,C,D |
| 2 | B,C,E |
| 3 | A,B,C,E |
| 4 | B,D,E |
| 5 | A,B,C,D |
minsupport=40%
==>min_support(最小频数)：5*40%=2 （要求：minsup_count >= 2）
步骤：生成候选集并通过扫描数据库得到他们的支持数,挑选minsup_count >= 2的项目集组成频繁项目集L
1、L1生成
| Itemset | sup_count |
|---|---|
| {A} | 3 |
| {B} | 5 |
| {C} | 4 |
| {E} | 3 |
L1={A,B,C,D,E}
2、L2生成
| Itemset | sup-count |
|---|---|
| {A,B} | 3 |
| {A,C} | 3 |
| {A,D} | 2 |
| {B,C} | 4 |
| {B,D} | 3 |
| {B,E} | 3 |
| {C,D} | 2 |
| {C,E} | 2 |
L2={AB,AC,AD,BC,BD,BE,CD,CE}
3、L3生成(不频繁集其超集也是不频繁的)
| Itemset | sup_count |
|---|---|
| {A,B,C} | 3 |
| {A,B,D} | 2 |
| {A,C,D} | 2 |
| {B,C,D} | 2 |
| {B,C,E} | 2 |
L3={ABC,ABD,ACD,BCD,BCE}
4、L4生成
| Itemset | sup_count |
|---|---|
| {A,B,C,D} | 2 |
L4={ABCD}
所有频繁项目集：{A,B,C,D,E,AB,AC,AD,BC,BD,BE,CD,CE,ABC,ABD,ACD,BCD,BCE,ABCD}
最大频繁项目集：
{BCE,ABCD}
最大频繁项集是各项K项集中符合无超集条件的频繁项集
全部评论 (0)
还没有任何评论哟~