网站建设的项目说明书,德阳网站建设网站建设,养老院为什么要建设网站,知名网站建设推荐目录
1.Apriori算法
Apriori性质
伪代码
apriori算法
apriori-gen(Lk-1)【候选集产生】
has_infrequent_subset(c,Lx-1)【判断候选集元素】
例题
求频繁项集#xff1a;
对于频繁项集L{B,C,E}#xff0c;可以得到哪些关联规则#xff1a;
2.FP-growth算法
FP-tre…目录
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-项集}
Ckapriori-gen (L-1);//C是k个元素的候选集
for(k2;Lk-1≠0;k)
for all transaction t属于D
Ctsubset(Ck,t);
for all candidates c属于Ct
c.count;
End for
End for
Lk{c∈Ck|c.countminsup_count}
End for
LULk
apriori-gen(Lk-1)【候选集产生】
输入k-1-项集
输出k-候选集C。
for all itemset p∈Lk-1
for all itemset q∈Lk-1
if (p.item1q.item1, p.item2q.item2,…,p.itemk-2q.itemk-2,p.itemk-1q.itemk-1)
cp∞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 求频繁项集 频繁1-项集L1{A},{B},{C},{E} 频繁2-项集L2:{A,C},{B,C},{B,E},{C,E}; 频繁3-项集L3:{B,C,E};说白了就是找哪种组合出现的次数2。
对于频繁项集L{B,C,E}可以得到哪些关联规则
B-C,Econfidence2/2100%C-B,Econfidence2/367%E-B,Cconfidence2/2100%C,E-Bconfidence2/367%B,E-Cconfidence2/367%B,C-Econfidence2/367%
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-namep.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α,其支持度supportai.support (6构造β的条件模式基然后构造β的条件FP-树Treeß (7) if Treeβ≠0 then (8)调用FP_growth(Treeβ,β) 参考资料《数据挖掘方法与应用》徐华著
