机器学习实战(Machine Learning in Action)学习笔记————08.使用FPgrowth算法来高效发现频繁项集

时间:2021-07-22 14:30:15

机器学习实战(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只需要对数据库进行两次扫描,能够显著加快频繁项集发现速度
缺点:该算法能够更高效的发现频繁项集,但不能用于发现关联规则
应用:搜索引擎推荐词(经常在一块出现的词对)等