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

这篇具有很好参考价值的文章主要介绍了数据挖掘(3.1)--频繁项集挖掘方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

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

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

求频繁项集:

  •  频繁1-项集L1{A},{B},{C},{E};
  • 数据挖掘(3.1)--频繁项集挖掘方法
  •  频繁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β,β); 

参考资料《数据挖掘:方法与应用》徐华著文章来源地址https://www.toymoban.com/news/detail-407704.html

到了这里,关于数据挖掘(3.1)--频繁项集挖掘方法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据挖掘十大算法之Apriori算法

    国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法: C4.5 , k-Means , SVM , Apriori , EM , PageRank , AdaBoost , kNN , Naive Bayes , CART 这十个算法涵盖了分类、聚类、统计学习、关联分析和链接分析等重要的数据挖掘研究和发展主题

    2024年02月04日
    浏览(45)
  • 数据挖掘-关联规则学习-Apriori算法原理

    比如你女朋友,低头玩手指+沉默,那大概率生气了,那这就是你总结出来的规则。啤酒与尿布的例子相信很多人都听说过吧,故事是这样的:在一家超市中,人们发现了一个特别有趣的现象,尿布与啤酒这两种风马牛不相及的商品居然摆在一起,但这一奇怪的举措居然使尿布

    2024年02月11日
    浏览(76)
  • 数据挖掘|关联分析与Apriori算法详解

    关联规则分析(Association-rules Analysis)是数据挖掘领域的一个重要方法,它是以某种方式分析数据源,从数据样本集中发现一些潜在有用的信息和不同数据样本之间关系的过程。 关联是指在两个或多个变量之间存在某种规律性,但关联并不一定意味着因果关系。 关联规则是寻

    2024年04月10日
    浏览(52)
  • 利用weka进行数据挖掘——基于Apriori算法的关联规则挖掘实例

    首先,如果不熟悉weka的使用的话,可以从我的git仓库里面拉取一下weka的相关教程,仓库里面还有包含此次实例的所有资源 我们可以在weka的官网上下载weka软件:weka官网 如果下载速度慢的话也可以直接从我的git仓库里面拉取这个软件,软件是win64位的weka-3-8-6 然后找到对应版

    2024年02月06日
    浏览(49)
  • 数据挖掘(一)使用 Apriori 算法进行关联分析

    关联分析是一种在大规模数据集中寻找有趣关系的任务。 这些关系可以有两种形式: 频繁项集(frequent item sets): 经常出现在一块的物品的集合。 关联规则(associational rules): 暗示两种物品之间可能存在很强的关系。 关联分析(关联规则学习): 从大规模数据集中寻找物品间的

    2024年02月09日
    浏览(52)
  • 大数据关联规则挖掘:Apriori算法的深度探讨

    在本文中,我们深入探讨了Apriori算法的理论基础、核心概念及其在实际问题中的应用。文章不仅全面解析了算法的工作机制,还通过Python代码段展示了具体的实战应用。此外,我们还针对算法在大数据环境下的性能局限提出了优化方案和扩展方法,最终以独到的技术洞见进行

    2024年01月24日
    浏览(253)
  • 数据挖掘——关联规则(Association Rule)Apriori算法和python代码实现

    关联规则(Association Rules)是反映一个事物与其他事物之间的相互依存性和关联性,是数据挖掘的一个重要技术,用于从大量数据中挖掘出有价值的数据项之间的相关关系。 用一些例子来说明一下: 当我们在超市进行购物时,超市中有琳琅满目的商品,在每一次购物结束之后,

    2024年02月04日
    浏览(52)
  • 数据分析、数据挖掘常用的数据清洗方法

    数据的完整性—例如:人的属性中缺少性别 数据的唯一性—例如:不同来源的数据出现重复 数据的权威性—例如:同一个指标出现多个来源的数据且数值不同 数据的合法性—例如:获取的数据与常识不符,年龄大于200岁 数据的一致性—例如:不同来源的不同指标,实际内涵

    2024年02月08日
    浏览(55)
  • [数据挖掘] 数据分析的八种方法

    不 同类型的数据分析包括描述性、诊断性、探索性、推理性、预测性、因果性、机械性和规范性。以下是您需要了解的有关每个的信息。本文对于前人归纳的8种进行叙述。

    2024年02月13日
    浏览(54)
  • 数据挖掘学习——数据预处理方法代码汇总(python)

    目录 一、归一化处理方法 (1)min-max方法(离散归一化) (2)零-均值规范化方法 (3)小数定标规范化 二、插值法 (1)拉格朗日插值法 三、相关性分析 (1)pearson相关性系数 (2)spearman相关性系数 四、主成分分析(PCA) 归一化常用方法有: (1)min-max方法(离散归一化

    2024年02月08日
    浏览(66)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包