详解python实现FP-TREE进行关联规则挖掘(带有FP树显示功能)附源代码下载(3)

上一节简单讲了下FP树的生成,在这一节我将描述FP树的挖掘过程.

首先我们回顾一下要挖掘的特征项及样本空间:

items=('chips','eggs','bread','milk','beer','popcorn','butter')
sample=[
    ['milk','eggs','bread','chips'],
    ['eggs','popcorn','chips','beer'],
    ['eggs','bread','chips'],
    ['milk','eggs','bread','popcorn','chips','beer'],
    ['milk','bread','beer'],
    ['eggs','bread','beer'],
    ['milk','bread','chips'],
    ['milk','eggs','bread','butter','chips'],
    ['milk','eggs','butter','chips']
]

由于要寻找的关联规则的最小支持度为3,所以butter和popcorn两个特征项就可以首先被忽略掉了，因为它们的支持度都只有2。

根据挖掘的规则，挖掘将从支持度最接近3的特征项开始，即本例中的beer，它的支持度为4.

从图中可以看到beer的节点数为4,于是它有4个条件模式基(CPB):

{eggs,bread,chips:1}

{eggs,bread:1}

{eggs,chips:1}

{bread,milk:1}

生成的FP子树如下图:

(注意:在源代码中,我为milk的FP子树单独生成了一个对象,其实在实际使用中FP树会占用很大的内从空间,所以FP子树一般会利用FP树而不是重新生成,一个可行的办法是将FP树的节点支持度数表示为一个字典,例如{root:7,milk:3}表示该节点在FP树中支持度为7,而在特征项milk的FP子树中支持度为3)

得到FP子树后要进行两步操作：

第一步：将该子树中所有支持度大于3的特征项与milk作并集，得到满足条件的二项集：

（eggs，milk ）

（bread，milk )  

它们的支持度都为3。

第二步：判断这颗子树是否有必要进一步挖掘，这是难点，也是优化算法的一个方向。

判断的结果有三种：

1. 该树没有任何一个特征项的支持度 >= 3，那么等同于空树，就没有必要挖掘了。

2. 该树是一棵单路径的树。

3. 该树是一棵多路径的树。

情况2和情况3是怎么回事，又该如何处理，请看下节

转载请注明出处:http://blog.csdn.net/rav009/article/details/8976421