详解python实现FP-TREE进行关联规则挖掘(带有FP树显示功能)附源代码下载(4)
上一节我们讲到根据一颗树的情况来判断是否有必要进行进一步的挖掘,这里有一个重要的概念叫单路径树，请看下面三张图：
图1
图2
图3
它们分别是beer ，chips和 milk 的条件模式 子树，当对最小支持度为3的关联规则进行挖掘时其中图1那棵树其实是可以视为空树的,而图2那棵树则可视为单路径树,而图3则是多路径树(路径数为2)。
表面上看这几棵树都是多路径的，图1那棵树有3个分叉，图2图3则有两路，但考虑到我们只对支持度为3以上的关联规则进行挖掘：
图1 中 支持度大于3的特征项只有两个分别是eggs和bread , 而且bread还分布在两条路径上，所以在将这两个特征项与 milk 作完并集后,这棵树不再有必要挖掘下去,等同一颗空树。
图2 中 支持读大于3的特征项也是eggs和bread，bread也同样分布在两条路径上，但是在其中一条路径上其支持度为4，大于3！所以从这条路径上我们又能挖掘出一个关联规则（eggs,bread,chips）其支持度为4。这种有且仅有一条路径的情况称为单路径树，对于单路径树是没有必要继续挖掘的，只要把路径上所有节点的长度大于等于2的组合与条件基（即这里的chips）做并集就行了,得到的关联规则的支持度为组合中节点的最小支持度。
图3 是一个非常有迷惑性的情况，一开始我误把它当作单路径的情况，把右边的chips和eggs剪枝剪掉了。如果这样做就会得到（chips,eggs,milk）支持度为3的关联规则,但其实考虑了右边的路径后，你就会明白这个组合的实际支持度为4。所以应该将其当作多路径的情况，以eggs为条件基递归继续挖掘下去。
下面请看我在源程序中用于判断一棵树是什么样的树的判断代码：
#检查是否为单路径的树,如果是返回1,不是返回0,如果空树则返回-1
def checksinglepathtree(self,node,threshold):
if node.root and node.isleaf():
return 0
if node.isleaf():
return 1
else:
if node.root or node.count>=threshold:
ccc=0 #count of child has children
for child in node.children:
if not child.isleaf():
ccc+=1
notleafchild=child
if child.isleaf() and not node.root:
return 1
if ccc>1:
return ccc
elif ccc==1:
if notleafchild.count<threshold:
return 0
else:
return self.checksinglepathtree(notleafchild,threshold)
else:
return 0
else:
return 1
在这段代码中我把凡是有两个或更多 节点数大于2的路径 的树 一律视为多路径树，个人感觉还是有优化的余地的，毕竟尽早判断出一棵树是单路径树或空树，可以避免继续挖掘的巨大开销。
但判断出一棵树是单路径树后，要将路径上的支持度大于等于3的节点的所有组合输出出来，这里所采用的求组合的算法叫10转换法。实现代码如下：
class util:
def __init__(self):
self.comdict={}
'''
获取列表l的长为m的组合
'''
def getcombination(self,l,m):
if l is None or (type(l) is not list and type(l) is not tuple):
return None
ll=len(l)
if ll == 0 or m==0:
return ()
if m>=ll:
return (tuple(l),)
if m==1:
return tuple([(item,) for item in l])
else:
s=self.getsequence(ll,m)
return self.createcombination(l,s)
def getsequence(self,ll,m):
if (ll,m) in self.comdict:
return self.comdict[(ll,m)]
else:
olist=[1]*m+[0]*(ll-m)
return self.createsequence(olist,[])
def createsequence(self,olist,rs):
if olist not in rs:
rs.append(olist)
for i in range(0,len(olist)-1):
if olist[i]==1 and olist[i+1]==0:
newlist=olist[:]
newlist[i]=0
newlist[i+1]=1
if newlist not in rs:
rs=self.createsequence(newlist,rs)
return rs
def createcombination(self,l,s):
rs=[]
for cs in s:
comb=[]
for i in range(0,len(cs)):
if cs[i]==1:
comb.append(l[i])
rs.append(tuple(comb))
return tuple(rs)
这是一个很有用的算法。有兴趣可以百度一下算法的原理。