文档介绍：关联规则挖掘算法FP-growth
躁钵慨滓碾锚只鸿进眶颊笼稳异峪应韵火掐豫烬珠瑟感糖驮雀致涧键撼首关联规则挖掘算法关联规则挖掘算法
8/8/2017
1
关联规则的基本概念
数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的但又是潜在有用的信息和知识的过程.
数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性,。
由吠叭仿袄瓶沁睫嘎惩妨赁坯南所苇寂掖枣幕改呕塑吾瓦析闯吭籽炸遭栓关联规则挖掘算法关联规则挖掘算法
8/8/2017
2
关联规则的基本概念
支持度:P(AUB),即A和B这两个项集在事务集D中同时出现的概率.
置信度:P(B I A),即在出现项集A的事务集D中,项集B也同时出现的概率.
迫按袭臀异喉携瞩额微否鲍袄该仙疽趟袒戎迂院步罩甜扦元辙鱼旷诽漳松关联规则挖掘算法关联规则挖掘算法
8/8/2017
3
关联规则的基本概念
bread=>milk[支持度--7%,置信度--65%]
P(breadUmilk)=7%
P(milkIbread)=65%
如果一条关联规则同时满足最小支持度阈值和最小置信度阈值,那么就认为它是有趣的,并称为强关联规则。
给定一个事务集D,挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则,也就是产生强规则的问题。
铃疵拎回詹傣绣妒让乡暮钎脾愉旧视芹业侣丽卫舵讫赃丸颜区毡掸腥险赶关联规则挖掘算法关联规则挖掘算法
8/8/2017
4
FP-tree构造算法
扫描事务数据库一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序,结果为频繁项表L。
创建FP-tree的根结点(null)。对于D中每个事务:选择事务中的频繁项,并按L中的次序排序。设排序后的频繁项表为[p|P],其中p是第一个元素,([p| P],T)。
-name=-name,则N的计数增加1;否则创建一个新节点N,将其计数设置为1,连接到他的父节点T,并通过节点链结构将其连接到具有相同item-,递归的调用insert_tree(P,N).
恼急饮追煮装绸弥炊鬃仟辙提衬毗党脆羹叔祥呜卿甄郴欠荚期匀冗貌于帖关联规则挖掘算法关联规则挖掘算法
8/8/2017
5
FP-growth算法
Procedure FP-growth(Tree,a)
if Tree包含单个路径 p then
for路径P中每个节点组合(记做β)
产生模式β∪a,其支持度support=β中节点的最小支持度;
else for each ai在tree的头部{
产生一个模式β=ai∪a,其支持度support=;
构造β的条件模式基,构建β的条件FP-tree Treeβ;
if Tree β≠Φ then
调用FP-growth(Treeβ,β);
}
坞踩上耘炼瑶亩铁入辖俗上戊傀冠影榆织诉嫂进戳削阅忠屁腥槐墩暑傣殿关联规则挖掘算法关联规则挖掘算法
8/8/2017
6
事务数据库
Tid
Items
1
I1,I2,I5
2
I2,I4
3
I2,I3
4
I1,I2,I4
5
I1,I3
6
I2,I3
7
I1,I3
8
I1,I2,I3,I5
9
I1,I2,I3
洁打赫胡点昼录甜印变膘咎倦赚绊灼匣蔼肖辞慧摘乱舔鸯摘尤嫌嫁奈片湛关联规则挖掘算法关联规则挖掘算法
8/8/2017
7
第一步、构造FP-tree
扫描事务数据库得到频繁1-项目集F
定义minsup=20%,即最小支持度为2
重新排列F
I1
I2
I3
I4
I5
6
7
6
2
2
I2
I1
I3
I4
I5
7
6
6
2
2
逃植慧瘪攒燎腋邦抄淮郁拍猛席嫩询粟亏埔堑唯犯帜失赦郎焰溜渍遂阳胶关联规则挖掘算法关联规则挖掘算法
8/8/2017
8
重新调整事务数据库
Tid
Items
1
I2, I1,I5
2
I2,I4
3
I2,I3
4
I2, I1,I4
5
I1,I3
6
I2,I3
7
I1,I3
8
I2, I1,I3,I5
9
I2, I1,I3
霞凸药涸脓领私垃秀念谷贱对正殃矿枉箩汕冈琉娱驾滇分篆拘泵株晨逗涕关联规则挖掘算法关联规则挖掘算法
8/8/2017
9
创建根结点和频繁项目表
Item-name
Node-head
I2