求助：关联规则挖掘中FP树的构造问题
题目说明比较长，分几次贴上来
ps：题目说明里的示例图不知道怎么贴上来，如果大家需要看请告诉我贴图的方法
解答与否，先谢谢大家^_^
题目：关联规则挖掘中FP树的构造
1问题描述
类似于从大量砂子中搜集黄金，从大量数据中发现有用信息的过程就是数据挖掘。关联规则是给定数据集中数据项之间的联系。关联规则的发现是一种非常重要的数据挖掘类型。
1.1 一个引发关联规则挖掘的例子
假定作为家乐福分店的经理，你一定希望能够通过了解顾客的购物习惯从而采取适当的店面布局策略来促进销售。例如，如果从大量销售数据中发现顾客有购买葡萄酒的同时也购买面包的购物习惯，那么可以将这两类商品布置的近一些，以便刺激这些商品共同销售；或者故意将这两类商品放在超市的两端，使需要购买这些商品的顾客一路走去，从而增加挑选其他商品的机会。
表1是商品代号－商品名称对照表。表2是某超市的零售数据，每行记录一张售货小票中出现的所有商品代号（相同商品代号不重复记录，不计销售数量），TID是售货小票的序列号。顾客的购物习惯指那些以较高概率出现在同一张小票中的商品组合。这些商品组合就是对零售数据进行挖掘后得到的关联规则。
一种商品组合的销售记录在全部销售记录中所占的百分比叫做支持度。当该组合的支持度不小于预先设定的最小支持度时，可以判定该组合满足最小置信度。比如，表2共有9条销售记录，其中包含I1的销售记录有6条，同时包含I1与I2的销售记录有4条，同时包含I1、I2与I3的销售记录有2条，那么I1在表2中的支持度为6/9，I1与I2在表2中的支持度为4/9，I1、I2与I3在表2中的支持度为2/9。如果设最小支持度为1/3，那么I1与I2在表2中满足最小支持度，I1和I1、I2与I3在表2中不满足最小支持度。
一种商品组合的销售记录在包含该组合子集的销售记录中所占的百分比叫做置信度。判断一种商品组合是否满足预先设定的最小置信度时，必须考察该组合相对于其所有真子集的置信度。只有当该组合相对于其所有真子集的置信度都不小于最小置信度时，才能判定该组合满足设定的置信度。比如，表2中包含I1的销售记录有6条，包含I2的销售记录有7条，同时包含I1与I2的销售记录有4条，那么I1与I2相对于I1的置信度为4/6，I1与I2相对于I2的置信度为4/7。如果设最小置信度为1/3，那么I1与I2在表2中满足最小置信度。
同时满足最小支持度与最小置信度的商品组合称为关联规则。判定一种商品组合是否满足最小置信度的计算量随着组合中商品数目增加而快速加大，因此，有时我们不考虑一种商品组合是否满足最小置信度。只要一种商品组合满足最小支持度，那么该商品组合称为频繁模式。
商品编号 商品名称
I1 牛奶
I2 面粉
I3 食用油
I4 蔬菜
I5 软饮料
TID 销售商品列表
T100 I1, I2, I5
T200 I2, I4
T300 I2, I3
T400 I1, I2, I4
T500 I1, I3
T600 I2, I3
T700 I1, I3
T800 I1, I2, I3, I5
T900 I1, I2, I3
问题点数：0、回复次数：5Top
1 楼SuperFreshMan（）回复于 2005-06-30 19:32:33 得分 0
1.2 FP树的构造
我们通过构造频繁模式树（Frequent-Pattern Tree，简称FP树）来实现关联规则的挖掘。
首先，对表2中的所有商品，按照它们在表2的销售记录中出现次数递减的顺序排序，放在结果表L。对表2中出现的商品I1，I2，I3，I4，I5，统计它们在销售记录中的出现次数，得到
L=[I2:7, I1:6, I3:6, I4:2, I5:2]
其中，形如I2:7这样的一个数对，I2表示商品代号，7表示I2在表2的销售记录中出现的总次数，称为支持度计数。在表2中出现的商品代号都是数据项，简称为项。
然后，FP树的构造方法如下：
1 创建FP树的根结点，用NULL标记。如图1所示。
2 扫描表2，对每条记录中的项按照L中的次序重新排序，依次处理每一项。
根据表2构造FP树时，首先构造FP树的根结点。然后开始扫描表2，最先处理记录“T100: I1, I2, I5”，该记录按照L的次序重新排序后得到{I2, I1, I5}。如果以项为FP树中的结点，项之间按L中的次序先后形成父子关系，那么I2-I1-I5即为需要加入FP树的一个分支。此时，FP树中除根结点以外无任何结点，所以需要为I2-I1-I5中的各项创建结点，并且将这些结点按照I2是根结点的孩子，I1是I2的孩子，I2是I5的孩子的顺序加入FP树。这些操作完成后， 目前的FP树中存在一条路径<(I2:1), (I1:1), (I5:1)>，如图2所示。其中，形如(I2:1)的数对表示结点计数器，(I2:1)表示目前FP树中以I2为前缀的路径计数为1，(I1:1)表示目前FP树中以I2-I1为前缀的路径计数为1，(I5:1) 表示目前FP树中以I2-I1-I5为前缀的路径计数为1。
接着处理表2中的记录“T200: I2, I4”，该记录按照L的次序重新排序后得到{I2, I4}。如果以项为FP树中的结点，项之间按照L中的次序先后形成父子关系，那么I2-I4即为需要加入FP树的一个分支。此时，FP树中已经存在路径I2-I1-I5，I2-I4可以与I2-I1-I5共享前缀路径<I2>。所以只需为I4创建结点，设I4的结点计数器为1，将I4作为I2的孩子加入FP树，为I2的结点计数器加1，如图3所示。(I2:2)表示目前FP树中以I2为前缀的路径计数为2，其中以I2-I1-I5为前缀的路径对该计数的贡献为1，以I2-I4为前缀的路径对该计数的贡献为1。接着处理表2中的记录“T300: I2, I3”，该记录按照L的次序重新排序后得到{I2, I3}。如果以项为FP树中的结点，项之间按照L中的次序先后形成父子关系，那么I2-I3即为需要加入FP树的一个分支。此时，FP树中已经存在路径I2-I1-I5，I2-I4。I2-I3可以与I2-I1-I5和I2-I4共享前缀路径<I2>。所以只需为I3创建结点，设I3的结点计数器为1，将I3作为I2的孩子加入FP树，为I2的结点计数器加1，如图4所示。(I2:3)表示目前FP树中以I2为前缀的路径计数为3，其中以I2-I1-I5为前缀的路径对该计数的贡献为1，以I2-I4为前缀的路径对该计数的贡献为1，以I2-I3为前缀的路径对该计数的贡献为1。Top
2 楼SuperFreshMan（）回复于 2005-06-30 19:34:00 得分 0
接着处理记录“T400: I1, I2, I4”，该记录按照L的次序重新排序后得到{I2, I1, I4}。如果以项为FP树中的结点，项之间按L中的次序先后形成父子关系，那么I2-I1-I4即为需要加入FP树的一个分支。此时，FP树中已经存在路径I2-I1-I5，I2-I4，I2-I3。I2-I1-I4可以与I2-I1-I5共享前缀路径<I2, I1>，I2-I1-I4也可以与I2-I4或者I2-I3共享前缀路径<I2>。比较发现前者的共享前缀路径较长，所以需要再次创建结点I4，设该I4结点的计数器为1，将这个I4结点作为I2-I1路径中I1的孩子加入FP树，I2-I1路径中各个结点的计数器均加1，如图5所示。(I2:4)表示目前FP树中以I2为前缀的路径计数为4，其中以I2-I1为前缀的路径对该计数的贡献为2，以I2-I4为前缀的路径对该计数的贡献为1，以I2-I3为前缀的路径对该计数的贡献为1。(I1:2)表示目前FP树中以I2-I1为前缀的路径计数为2，其中以I2-I1-I5为前缀的路径对该计数的贡献为1，以I2-I1-I4为前缀的路径对该计数的贡献为1。
接着处理表2中的记录“T500: I1, I3”，该记录按照L的次序重新排序后得到{I1, I3}。如果以项为FP树中的结点，项之间按照L中的次序先后形成父子关系，那么I1-I3即为需要加入FP树的一个分支。此时，FP树中既不存在前缀路径I1，也不存在前缀路径I1-I3，所以需要创建结点I1与结点I3，设I1与I3的结点计数器均为1，将I1作为根结点的孩子加入FP树，将I3作为I1的孩子加入FP树。如图6所示。路径< (I1:1), (I3:1)>中的(I1:1)表示目前FP树中以I1为前缀的路径计数为1，路径< (I1:1), (I3:1)>中的(I3:1)表示目前FP树中以I1-I3为前缀的路径计数为1。
接着处理表2中的记录“T600: I2, I3”，该记录按照L的次序重新排序后得到{I2, I3}。如果以项为FP树中的结点，项之间按照L中的次序先后形成父子关系，那么I2-I3即为需要加入FP树的一个分支。此时，FP树中已经存在前缀路径<(I2:4), (I3:1)>，所以无需创建新结点，只需将<(I2:4), (I3:1)>路径中I2与I3的结点计数器各加1即可，处理完毕后得到的FP树如图7所示。
接着处理表2中的记录“T700: I1, I3”，该记录按照L的次序重新排序后得到{I1, I3}。如果以项为FP树中的结点，项之间按照L中的次序先后形成父子关系，那么I1-I3即为需要加入FP树的一个分支。此时，FP树中已经存在前缀路径<(I1:1), (I3:1)>，所以无需创建新结点，只需将<(I1:1), (I3:1)>路径中I1与I3的结点计数器各加1即可，处理完毕后得到的FP树如图8所示。
接着处理记录“T800: I1, I2, I3, I5”，该记录按照L的次序重新排序后得到{I2, I1, I3, I5}。如果以项为FP树中的结点，项之间按L中的次序先后形成父子关系，那么I2-I1-I3-I5即为需要加入FP树的一个分支。考察FP树中已经存在的路径，发现目前I2-I1-I3-I5在FP树中可以使用的最大共享前缀为<I2, I1>，所以需要创建结点I3与结点I5，设这两个结点的计数器为1，将结点I3作为<I2, I1>路径中I1的孩子加入FP树，结点I5作为<I2, I1, I3>路径中I3的孩子加入FP树。<I2, I1>路径中各个结点的计数器均加1，处理完毕后得到的FP树如图9所示。Top
3 楼SuperFreshMan（）回复于 2005-06-30 19:34:56 得分 0
最后处理记录“T900: I1, I2, I3”，该记录按照L的次序重新排序后得到{I2, I1, I3}。如果以项为FP树中的结点，项之间按L中的次序先后形成父子关系，那么I2-I1-I3即为需要加入FP树的一个分支。考察FP树中的路径，发现已经存在前缀路径<(I2:6), (I1:3), (I3:1)>，所以无需创建新结点，只需将<(I2:6), (I1:3), (I3:1)>路径中各结点计数器加1即可，处理完毕后得到的FP树如图10所示。
到目前为止，根据表2中的数据已经初步构造了一棵FP树。一般的，当处理表中的一条记录考虑为FP树增加分支时，如果FP树中已经存在该分支对应的前缀路径，那么在这些前缀路径中选择最长的，将其中各结点的计数器加1，并且为需要增加的分支剩余部分创建结点，将其顺次连接在最长的前缀路径后面。
为方便FP树的遍历，需要为L中的各项依次创建一个项头表，如图11所示。其中，“支持度计数”指的是项在数据集（本例指表2）中的全部出现次数，“结点链”保存指向一个结点链表的指针。项头表中的每一项可以通过一个结点链表串联起它在FP树中的所有出现。不同的项在FP树中的出现链表以不同颜色的虚线表示。项的支持度计数等于该项在FP中所有出现的结点计数器计数之和。
项 支持度计数 结点链
I2 7
I1 6
I3 6
I4 2
I5 2
Top
4 楼woyaoqiuzhu（）回复于 2005-06-30 19:47:53 得分 0
回复次数满了，新注册了个帐号来继续发题目说明
1.3 FP树中频繁模式的挖掘
我们按照项头表的逆序（项的支持度计数从小到大）在根据表2构造的FP树中挖掘频繁模式。设频繁模式需要满足的最小支持度计数为2。
在图11所示的FP树中挖掘频繁模式，首先考虑项头表中的最后一项I5。根据项头表中I5的结点链，发现I5出现在FP树的两个分支中<(I2 I1 I5:1)>与<(I2 I1 I3 I5:1)>中。在形如<(I2 I1 I5:1)>的序列中，I2 I1 I5指示前缀路径，1指示该分支的支持度计数，也就是该前缀路径在FP树中的出现次数。在这两个分支中，包含I5并且长度为2的结点组合有I2 I5，I1 I5，I3 I5。其中I2 I5与I1 I5在这两个分支中各出现2次，满足最小支持度计数，作为频繁模式输出。在这两个分支中，包含I5并且长度为3的结点组合有I2 I1 I5，I1 I3 I5。其中I2 I1 I5在这两个分支中出现2次，满足最小支持度计数，作为频繁模式输出；I1 I3 I5在这两个分支中出现1次，不满足最小支持度计数，不是频繁模式。在这两个分支中，包含I5并且长度为4的结点组合有I2 I1 I3 I5，该组合在这两个分支中出现1次，不满足最小支持度计数，不是频繁模式。至此，由I5产生的频繁模式挖掘完毕，删除FP树中的所有I5结点和项头表中I5的结点链指表针，处理完毕得到FP树如图12所示。
项 支持度计数 结点链
I2 7
I1 6
I3 6
I4 2
I5 2
接着处理项头表中的项I4。根据I4的结点链，发现I4出现在FP树的两个分支中<(I2 I1 I4:1)>与<(I2 I4:1)>中。在这两个分支中，包含I4并且长度为2的结点组合有I2 I4，I1 I4。其中I2 I4在这两个分支中出现2次，满足最小支持度计数，作为频繁模式输出；I1 I4在这两个分支中出现1次，不满足最小支持度计数，不是频繁模式。在这两个分支中，包含I4并且长度为3的结点组合有I2 I1 I4，该组合在这两个分支中出现1次，不满足最小支持度计数，不是频繁模式。至此，由I4产生的频繁模式挖掘完毕，删除FP树中的所有I4结点和项头表中I4的结点链指表针，处理完毕得到FP树如图13所示。
项 支持度计数 结点链
I2 7
I1 6
I3 6
I4 2
I5 2
Top
5 楼woyaoqiuzhu（）回复于 2005-06-30 19:50:25 得分 0
接着处理项头表中的项I3。根据I3的结点链，发现I3出现在FP树的3个分支中<(I2 I1 I3:2)>，<(I2 I3:2)>与<(I1 I3:2)>中。在这3个分支中，包含I3并且长度为2的结点组合有I2 I3，I1 I3。其中I2 I4与I1 I3在这两个分支中各出现4次，满足最小支持度计数，作为频繁模式输出。在这3个分支中，包含I3并且长度为3的结点组合有I2 I1 I3，该组合在这两个分支中出现2次，满足最小支持度计数，作为频繁模式输出。至此，由I3产生的频繁模式挖掘完毕，删除FP树中的所有I3结点和项头表中I3的结点链指表针，处理完毕得到FP树如图14所示。
项 支持度计数 结点链
I2 7
I1 6
I3 6
I4 2
I5 2
接着处理项头表中的项I1。根据I1的结点链，发现I1出现在FP树的2个分支中<(I2 I1:4)>与<(I1:2)>中。在这2个分支中，包含I3并且长度为2的结点组合有I2 I1，在这两个分支中出现4次，满足最小支持度计数，作为频繁模式输出。至此，由I1产生的频繁模式挖掘完毕，删除FP树中的所有I1结点和项头表中I1的结点链指表针，处理完毕得到FP树如图15所示。
项 支持度计数 结点链
I2 7
I1 6
I3 6
I4 2
I5 2
图15中已经不存在长度为2的结点组合，频繁模式挖掘完毕。根据表2构造的FP树产生的所有支持度计数不小于2的频繁模式如表3所示。
项 产生的频繁模式
I5 I2 I5:2, I1 I5:2,I2 I1 I5:2
I4 I2 I4:2
I3 I2 I3:4, I1 I3:4,I2 I1 I3:2
I1 I2 I1:4
说明完了，下面是要求：
1为FP树设计数据结构
2假设输入文件中的一行即为一条销售记录（不包含表2中的TID），其中不同的商品以空格符相互分隔，对于各种商品，按照它们在销售记录中出现次数递减的顺序排序并且加以显示
3为输入文件中的数据集构造FP树，完成要求A与B。
A 要求能够打印项头表中任意一项的结点链表。
B 给定任意一项，要求能够打印FP树中以其为终点的所有前缀路径
结束，等待解答，谢谢大家Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
