当前位置:首页 » 《随便一记》 » 正文

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

11 人参与  2023年04月08日 08:01  分类 : 《随便一记》  评论

点击全文阅读


目录

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属于DCt=subset(Ck,t);for all candidates c属于Ctc.count++;End forEnd forLk={c∈Ck|c.count>=minsup_count}End forL=ULk

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

输入:(k-1)-项集输出:k-候选集C。for all itemset p∈Lk-1for all itemset q∈Lk-1if (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 forEnd forReturn Ck

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

输入:一个k-项集c,(k-1)-项集Lk-1输出:c是否从候选集中删除。for all (k-l)-subsets of cif S不属于Lk-1return 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,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β,β); 

参考资料《数据挖掘:方法与应用》徐华著


点击全文阅读


本文链接:http://zhangshiyu.com/post/58792.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 京圈佛子破戒后,我改嫁京圈纨绔(沈墨渊,白晶晶)
  • 前世被闺蜜害死,重生后我让她从太子妃变疯女苏婉儿,清歌完本_前世被闺蜜害死,重生后我让她从太子妃变疯女(苏婉儿,清歌)
  • 全书浏览七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)_七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)全书结局
  • 今天也没变成昨天(周扬陈默)全书免费_(周扬陈默)今天也没变成昨天后续(周扬陈默)
  • 重生后,秦总非要父以子贵(许沐晴,秦越泽)全书浏览_重生后,秦总非要父以子贵全书浏览
  • 他嫌弃我喝两块钱豆浆上不了台面,我结婚后他又哭又闹全书万照,白青青在线
  • 昭然若梦前尘烬列表_昭然若梦前尘烬(温昭然方池雲)
  • 导师借我股票账号,我倒欠五十万(孟潇潇,宁薇)_导师借我股票账号,我倒欠五十万孟潇潇,宁薇
  • 拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾(周钰泽,蒋清清,思源)全书浏览_拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾全书浏览
  • 我的人生,你已出局(程森凌古楚文)_我的人生,你已出局程森凌古楚文
  • 穿书成病娇女配,睁眼就签下离婚协议书(朱楼)_穿书成病娇女配,睁眼就签下离婚协议书
  • 老婆逼我给白月光捐肾,我死后她悔疯了(宋逸晨沈墨白)全书浏览_老婆逼我给白月光捐肾,我死后她悔疯了全书浏览

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1