数据挖掘(3.1)--频繁项集挖掘方法

简介: 关联规则挖掘是数据挖掘领域中研究最为广泛的也最为活跃的方法之一关联规则反应了一个事物和其他事物之间的相互依存性和关联性如果存在一定的关联关系,其中一个事物就可以通过其他事物预测到最小支持度:就是说当支持度达到一定的阈值后,某种数据才有被挖掘的潜力这个阈值就是最小支持度计数(min_sup)。

目录


1.Apriori算法


Apriori性质


伪代码


apriori算法


apriori-gen(Lk-1)【候选集产生】


has_infrequent_subset(c,Lx-1)【判断候选集元素】


例题


求频繁项集:


对于频繁项集L={B,C,E},可以得到哪些关联规则:


2.FP-growth算法


FP-tree构造算法【自顶向下建树】


insert_tree([plP],T)


利用FP-tree挖掘频繁项集



关联规则挖掘是数据挖掘领域中研究最为广泛的也最为活跃的方法之一


关联规则反应了一个事物和其他事物之间的相互依存性和关联性


如果存在一定的关联关系,其中一个事物就可以通过其他事物预测到


最小支持度:就是说当支持度达到一定的阈值后,某种数据才有被挖掘的潜力这个阈值就是最小支持度计数(min_sup)。


频繁项集:当某种数据的支持度超过最小支持计数阈值时就叫做频繁项集。


1.Apriori算法

Apriori算法是R.Agrawal和R.Srikant于1994年提出的为布尔关联规则挖掘频繁项集的原创性算法。


主要有以下几个步骤:首先通过扫描数据库积累每个项的计数,并收集满足最小支持度的项,找出频繁1-项集的集合(该集合记做L1)。然后L1用于找到频繁2-项集的集合L2,利用L2再找到L3,如此下去直到不能再找到频繁k-项集为止。


Apriori性质

频繁项集的所有非空子集也必须是频繁的。


非频繁项集的所有超集也必须是频繁的。


主要用于压缩拽索空间,从而更快地找到频繁项集。


伪代码

摘自《数据挖掘:方法与应用》徐华著


apriori算法

输人:数据集D;最小支持度计数minsup_count。
输出:频繁项目集L。//所有支持度不小于minsupport的1-项集
L1={频繁1-项集};
Ck=apriori-gen (L-1);//C是k个元素的候选集
for(k=2;Lk-1≠0;k++)
for all transaction t属于D
Ct=subset(Ck,t);
for all candidates c属于Ct
c.count++;
End for
End for
Lk={c∈Ck|c.count>=minsup_count}
End for
L=ULk

apriori-gen(Lk-1)【候选集产生】

输入:(k-1)-项集
输出:k-候选集C。
for all itemset p∈Lk-1
for all itemset q∈Lk-1
if (p.item1=q.item1, p.item2=q.item2,…,p.itemk-2=q.itemk-2,p.itemk-1<q.itemk-1)
c=p∞q;
if(has_infrequent_subset(c,Lx-1)) delete c;
else add c to Ck;
End for
End for
Return Ck

has_infrequent_subset(c,Lx-1)【判断候选集元素】

输入:一个k-项集c,(k-1)-项集Lk-1
输出:c是否从候选集中删除。
for all (k-l)-subsets of c
if S不属于Lk-1
return true;
return false

例题

假设最小支持度是2

966ca40b6bbbb3626b42bbb79142088e_674c0fc2008246b5b186836c5d5d6412.png



求频繁项集:

频繁1-项集L1{A},{B},{C},{E};

2b399da5a11f87c3bbbc6850fc2992b0_538dcf1d819742af8391612359017daa.png

频繁2-项集L2:{A,C},{B,C},{B,E},{C,E};

频繁3-项集L3:{B,C,E};

说白了就是找哪种组合出现的次数>=2。


对于频繁项集L={B,C,E},可以得到哪些关联规则:

B->C,Econfidence=2/2=100%

C->B,Econfidence=2/3=67%

E->B,Cconfidence=2/2=100%

C,E->Bconfidence=2/3=67%

B,E->Cconfidence=2/3=67%

B,C->Econfidence=2/3=67%

2.FP-growth算法

FP-growth算法主要采用如下的分治策略:首先将提供频繁项的数据库压缩到一个频繁模式树(FP-tree),但仍保留相关信息。然后将压缩后的数据库划分成一组条件数据库,每个关联一个频繁项或“模式段”,并分别挖掘每个条件数据库。


FP-tree构造算法【自顶向下建树】

输人:事务数据库DB;最小支持度阈值Minsupport。


输出:FP-tree树。


(1)扫描事务数据库D一次。收集频繁项集合E以及它们的支持度计数,对F按照支持度计数降序排序,得到频繁项列表L。


(2)创建FP-tree的根节点,以“null"标记它。对于D中的每个事务T,作如下处理:选择T中的频繁项,并按照L中的次序进行排序,排序后的频繁项标记为[plP],其中p是第一个元素,P是剩余元素的表。调用insert_tree([plP],T)将此元组对应的信息加入到T中。


insert_tree([plP],T)

构造FP-tree算法的核心是insert_tree过程。Insert_tree过程是对数据库的一个候选项目集的处理,它对排序后的一个项目集的所有项目进行递归式的处理直到项目表为空。


(1)if(T有一个子女N使得N.item-name=p.item-name)


(2)N的计数加一


(3) else


(4)创建一个新节点N,将其计数设为1,链接到它的父节点T,并通过节点链结构将其链接到具有相同项名的节点。


(5)如果P非空,递归地调用insert_tree(P,N)。


利用FP-tree挖掘频繁项集

输入:构造好的FP-tree,事务数据库D,最小支持度阈值Minsupport。


输出:频繁项集。FP-growth(Tree,α)


(1)if(Tree含单个路径P)


(2)for路径P中节点的每个组合(记作β)


(3)产生模式βUα,其支持度support=β中节点的最小支持度


(4)else for each ai 在Tree的头部{


(5)产生一个模式β=aiUα,其支持度support=ai.support;


(6)构造β的条件模式基,然后构造β的条件FP-树Treeß;


(7) if Treeβ≠0 then


(8)调用FP_growth(Treeβ,β);  

目录
相关文章
|
4月前
|
算法 数据挖掘 数据库
【数据挖掘】频繁项集挖掘方法中Apriori、FP-Growth算法详解(图文解释 超详细)
【数据挖掘】频繁项集挖掘方法中Apriori、FP-Growth算法详解(图文解释 超详细)
143 0
|
4月前
|
算法 数据挖掘 数据库
【数据挖掘】关联规则、频繁项集、闭项集详解(图文解释 超详细)
【数据挖掘】关联规则、频繁项集、闭项集详解(图文解释 超详细)
278 1
|
5月前
|
存储 算法 数据挖掘
数据挖掘2.4——关联规则挖掘 知识点整理
数据挖掘2.4——关联规则挖掘 知识点整理
121 0
|
9月前
|
机器学习/深度学习 人工智能 算法
数据挖掘18大算法实现以及其他相关经典DM算法:决策分类,聚类,链接挖掘,关联挖掘,模式挖掘。图算法,搜索算法等
数据挖掘18大算法实现以及其他相关经典DM算法:决策分类,聚类,链接挖掘,关联挖掘,模式挖掘。图算法,搜索算法等
|
12月前
|
数据采集 算法 数据挖掘
【数据挖掘实战】——中医证型的关联规则挖掘(Apriori算法)
项目地址:Datamining_project: 数据挖掘实战项目代码
485 0
|
存储 算法 数据挖掘
数据挖掘从入门到放弃(四):手撕(绘)关联规则挖掘算法
数据挖掘从入门到放弃(四):手撕(绘)关联规则挖掘算法
132 0
|
数据可视化 数据挖掘 数据库
【数据挖掘】用Excel挖掘股权关系并按照年份统计不同类型的亲缘关系在上市公司中的分布和趋势【动态可视化工具】
推荐一个在线制作动图网站 Flourish(https://app.flourish.studio) 无需编程基础就可以做出漂亮的动态图表🎉🎉🎉
187 1
【数据挖掘】用Excel挖掘股权关系并按照年份统计不同类型的亲缘关系在上市公司中的分布和趋势【动态可视化工具】
|
算法 数据挖掘
【数据挖掘】关联规则挖掘 Apriori 算法 ( Apriori 算法过程 | Apriori 算法示例 )
【数据挖掘】关联规则挖掘 Apriori 算法 ( Apriori 算法过程 | Apriori 算法示例 )
152 0
|
机器学习/深度学习 算法 数据挖掘
【数据挖掘】关联规则挖掘 Apriori 算法 ( 关联规则性质 | 非频繁项集超集性质 | 频繁项集子集性质 | 项集与超集支持度性质 )
【数据挖掘】关联规则挖掘 Apriori 算法 ( 关联规则性质 | 非频繁项集超集性质 | 频繁项集子集性质 | 项集与超集支持度性质 )
333 0
|
算法 IDE 数据挖掘
【数据挖掘】关联规则挖掘 Apriori 算法 ( 频繁项集 | 非频繁项集 | 强关联规则 | 弱关联规则 | 发现关联规则 )
【数据挖掘】关联规则挖掘 Apriori 算法 ( 频繁项集 | 非频繁项集 | 强关联规则 | 弱关联规则 | 发现关联规则 )
325 0