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

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

机器学习实战（Machine Learning in Action）学习笔记————08.使用FPgrowth算法来高效发现频繁项集的相关教程结束。