机器学习实战（Machine Learning in Action）学习笔记————08.使用FPgrowth算法来高效发现频繁项集
关键字：FPgrowth、频繁项集、条件FP树、非监督学习
作者：米仓山下
时间：2018-11-3
机器学习实战（Machine Learning in Action,@author: Peter Harrington）
源码下载地址：https://www.manning.com/books/machine-learning-in-action
git@github.com:pbharrin/machinelearninginaction.git
*************************************************************
一、使用FPgrowth算法来高效发现频繁项集
FPgrowth算法原理：
基于Apriori构建，但在完成相同任务时，采用了一些不同的的技术。这里的任务是将数据集存储在一个特定的称为FP树的结构之后发现频繁项集或则频繁项对，即在一块出现的的元素项的集合FP树。这种做法的执行速度要快于Apriori，通常性能要好两个数量级以上。
FP——Frequent pattern（频繁模式）
*************************************************************
二、FPgrowth算法——构建FP树
FP树构建函数
----------------------------------------------------------------------------
输入：dataSet——待挖掘数据集；minSup——最小支持度，默认为1
输出：retTree——构建的FP树； headerTable——头指针表
def createTree(dataSet, minSup=1): #create FP-tree from dataset but don't mine
headerTable = {} #扫描两次数据集dataSet
for trans in dataSet:#第一次扫描，统计所有元素出现的频次
for item in trans:
headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
for k in headerTable.keys(): #移除不符合minSup的items
if headerTable[k] < minSup:
del(headerTable[k])
freqItemSet = set(headerTable.keys())
#print 'freqItemSet: ',freqItemSet
if len(freqItemSet) == 0: return None, None #没有items符合minSup，返回None退出
for k in headerTable:
headerTable[k] = [headerTable[k], None] #结构化headerTable
#print 'headerTable: ',headerTable
retTree = treeNode('Null Set', 1, None) #创建FP树根节点
for tranSet, count in dataSet.items(): #第二次扫描，构建FP树retTree
localD = {}
for item in tranSet: #获取条数据中每个元素的全局频次，以便排序
if item in freqItemSet:
localD[item] = headerTable[item][0]
if len(localD) > 0:
orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] #排序
updateTree(orderedItems, retTree, headerTable, count) #更新FP树retTree
return retTree, headerTable #返回FP树retTree，头指针表headerTable
注：createTree足够灵活，下面构建条件FP树时还要用到
#更新FP树retTree
def updateTree(items, inTree, headerTable, count):
if items[0] in inTree.children: #如果第一个元素orderedItems[0]在子节点中
inTree.children[items[0]].inc(count) #增加计数
else: #不存在，增加子节点
inTree.children[items[0]] = treeNode(items[0], count, inTree)
if headerTable[items[0]][1] == None: #头指针表中items没有指向节点
headerTable[items[0]][1] = inTree.children[items[0]]
else: #头指针表中items以指向某个相似节点，追加到后面
updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
if len(items) > 1: #items不止一个元素，去掉第一个元素，递归调用updateTree构建树
updateTree(items[1::], inTree.children[items[0]], headerTable, count)
----------------------------------------------------------------------------
测试：
>>> import fpGrowth
>>> simpdata=fpGrowth.loadSimpDat()
>>> initset=fpGrowth.createInitSet(simpdata)
>>> simpdata
[['r', 'z', 'h', 'j', 'p'], ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'], ['z'], ['r', 'x', 'n', 'o', 's'], ['y', 'r', 'x', 'z', 'q', 't', 'p'], ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
>>> initset
{frozenset(['e', 'm', 'q', 's', 't', 'y', 'x', 'z']): 1, frozenset(['x', 's', 'r', 'o', 'n']): 1, frozenset(['s', 'u', 't', 'w', 'v', 'y', 'x', 'z']): 1, frozenset(['q', 'p', 'r', 't', 'y', 'x', 'z']): 1, frozenset(['h', 'r', 'z', 'p', 'j']): 1, frozenset(['z']): 1}
>>> minSup = 3
>>> myFPtree, myHeaderTab = fpGrowth.createTree(initset, minSup)
>>> myFPtree.disp()
Null Set 1
x 1
s 1
r 1
z 5
x 3
y 3
s 2
t 2
r 1
t 1
r 1
>>> myHeaderTab
{'s': [3, <fpGrowth.treeNode instance at 0x00000000039FE608>], 'r': [3, <fpGrowth.treeNode instance at 0x00000000039FE788>], 't': [3, <fpGrowth.treeNode instance at 0x00000000039FE688>], 'y': [3, <fpGrowth.treeNode instance at 0x00000000039FE5C8>], 'x': [4, <fpGrowth.treeNode instance at 0x00000000039FE588>], 'z': [5, <fpGrowth.treeNode instance at 0x00000000039FE548>]}
>>>
*************************************************************
三、从一棵FP树种挖掘频繁项集
#递归查找频繁项：mineTree函数
----------------------------------------------------------------------------
#输入：inTree——输入FP树，递归调用时为此时的元素preFix条件FP树；headerTable——头指针表；minSup——最小支持数；preFix——初始化为set([])，递归调用时为条件FP树inTree对应的元素；freqItemList——初始化为[]，用来存储频繁项集。
#输出：freqItemList——用来存储频繁项集
def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1])] #头指针表排序
for basePat in bigL: #从头指针表bigL（headerTable）底端开始遍历（从小到大）
newFreqSet = preFix.copy()
newFreqSet.add(basePat) #递归前，newFreqSet为单元素频繁项；递归时preFix不为空，开始组合
freqItemList.append(newFreqSet) #将每个频繁项加入到列表freqItemList中
condPattBases = findPrefixPath(basePat,\ #抽取条件模式基condPattBases，去掉了元素本身
headerTable[basePat][1])
myCondTree, myHead = createTree(condPattBases,\ #根据条件模式基condPattBases构建条件频繁树myCondTree
minSup)
if myHead != None: #挖掘FP条件树
#print 'conditional tree for: ',newFreqSet
#myCondTree.disp(1)
mineTree(myCondTree, myHead, minSup, \ #newFreqSet不为空set([]),递归调用mineTree函数
newFreqSet, freqItemList)
----------------------------------------------------------------------------
将源码中下面两行取消注释：
#print 'conditional tree for: ',newFreqSet
#myCondTree.disp(1) #打印条件树
测试：
>>> myFreqList = []
>>> reload(fpGrowth)
<module 'fpGrowth' from 'fpGrowth.py'> #遍历头指针表myHeaderTab，将其单元素频繁项加入myFreqList后，再找出每个元素的条件FP树。递归调用组合频繁项
>>> fpGrowth.mineTree(myFPtree, myHeaderTab, minSup, set([]), myFreqList)
conditional tree for: set(['y'])
Null Set 1
x 3
z 3
conditional tree for: set(['y', 'z'])
Null Set 1
x 3
conditional tree for: set(['s'])
Null Set 1
x 3
conditional tree for: set(['t'])
Null Set 1
y 3
x 3
z 3
conditional tree for: set(['x', 't'])
Null Set 1
y 3
conditional tree for: set(['z', 't'])
Null Set 1
y 3
x 3
conditional tree for: set(['x', 'z', 't'])
Null Set 1
y 3
conditional tree for: set(['x'])
Null Set 1
z 3
>>> myFreqList
[set(['y']), set(['y', 'z']), set(['y', 'x', 'z']), set(['y', 'x']), set(['s']), set(['x', 's']), set(['t']), set(['z', 't']), set(['x', 'z', 't']), set(['y', 'x', 'z', 't']), set(['y', 'z', 't']), set(['x', 't']), set(['y', 'x', 't']), set(['y', 't']), set(['r']), set(['x']), set(['x', 'z']), set(['z'])]
>>> len(myFreqList)
18
>>>
*************************************************************
四、示例：从新闻网站点击流中挖掘
kosarak.dat中有将近100万条记录，每一行包含了某个用户浏览过得新闻报道。有些用户只看过一篇，有的用户看过2498篇报道。用户和报道编码成整数，利用FPgrowth算法
#读取数据，数据集格式化
>>> parsedDat=[line.split() for line in open('kosarak.dat').readlines()]
>>> len(parsedDat)
990002
>>> initset=fpGrowth.createInitSet(parsedDat)
#构建FP树，寻找阅读量10+的新闻报道
>>> myFPtree, myHeaderTab = fpGrowth.createTree(initset, 100000)
#创建条件FP树
>>> myFreqList = []
>>> fpGrowth.mineTree(myFPtree, myHeaderTab, 100000, set([]), myFreqList)
>>> len(myFreqList)
9
>>> myFreqList
[set(['']), set(['', '']), set(['']), set(['', '']), set(['', '', '']), set(['', '']), set(['']), set(['', '']), set([''])]
>>>
----------------------------------------------------------------------------
总结：
优点：FPgrowth算法相比Apriori只需要对数据库进行两次扫描，能够显著加快频繁项集发现速度
缺点：该算法能够更高效的发现频繁项集，但不能用于发现关联规则
应用：搜索引擎推荐词（经常在一块出现的词对）等