专栏首页蛰虫始航Python数据分析基础之关联分析FP_growth

Python数据分析基础之关联分析FP_growth

本文1995字,预计阅读需9分钟;

上篇文章我们了解了关联分析的基本概念和应用场景,以及挖掘数据集中关联规则的Apriori算法,通过具体代码实现了一个Apriori算法,在上一篇文章的最后提到Apriori算法的效率并不高,因此本文就深入一个优化了的关联规则算法FP-growth。


FP-growth算法是伊利罗伊香槟分校的韩嘉炜教授于2004年提出的,它是为了解决Apriori算法每次增加频繁项集的大小都要遍历整个数据库的缺点,特别是当数据集很大时,该算法执行速度要快于Apriori算法两个数量级。

FP-growth算法的任务是将数据集存储在一个特定的称为FP树的结构之后发现频繁项集或者频繁项对,虽然它能够高效地发现频繁项集,但是不能用来发现关联规则,也就是只优化了Apriori算法两个功能中的前一个功能。

FP-growth算法将数据存储在一个称为FP树的紧凑数据结构中,它与计算机科学中的其他树的结构类似,但是它通过链接来链接相似元素,被连起来的元素可以看做一个链表。

FP_Tree_chpten

FP-growth算法只需要对数据集进行两次扫描,所以即使数据集很大时也不会花费太多的时间在扫描数据上,它发现频繁项集的基本过程如下:1)构建FP树 2)从FP树中挖掘频繁项集

创建FP Tree的数据结构

对每一频繁项,都要创建一颗条件FP树,将上面的条件模式基作为输入,通过相同的建树方法来构建这些条件树,然后递归地发现频繁项、发现条件模式基,以及发现另外的条件树。举个例子,假定为频繁项t创建一个条件FP树,然后对{t,y},{t,x}、...重复该过程。

构建相关类的代码如下:

class treeNode:  #FP Tree的树节点
    def __init__(self, nameValue, numOccur, parentNode):
        self.name = nameValue
        self.count = numOccur  #计数
        self.parent = parentNode     #父节点
        self.nodeLink = None  #横向链
        self.children = {}   #子节点

    def inc(self, numOccur):
        self.count += numOccur

    def disp(self, ind=1): #将树以文本形式显示
        print ('  '*ind, self.name, ' ', self.count)
        for child in self.children.values():
            child.disp(ind+1)

创建 FP 树的函数:

def createTree(dataSet, minSup=1): #从数据集创建FP Tree
    headerTable = {}
    #两次遍历数据集
    for trans in dataSet:#第一次遍历:统计每个元素项出现次数
        for item in trans:
            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
    klst=[j for j in  headerTable.keys()]
    for k in klst:  #移除不满足最小支持度的元素项
        if headerTable[k] < minSup: 
            del(headerTable[k])
    freqItemSet = set(headerTable.keys())
    if len(freqItemSet) == 0: return None, None  #i如果没有元素项满足要求,退出
    for k in headerTable:
        headerTable[k] = [headerTable[k], None] 
    retTree = treeNode('Null Set', 1, None) #建立树的节点
    for tranSet, count in dataSet.items():  
        localD = {}
        for item in tranSet:  
            if item in freqItemSet:
                localD[item] = headerTable[item][0]
        if len(localD) > 0: #对剩下的元素项迭代,调用updateTree
            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]
            updateTree(orderedItems, retTree, headerTable, count)
    return retTree, headerTable

def updateTree(items, inTree, headerTable, count): #增长更新树
    if items[0] in inTree.children:
        inTree.children[items[0]].inc(count) 
    else: #加入i[0]
        inTree.children[items[0]] = treeNode(items[0], count, inTree)
        if headerTable[items[0]][1] == None:
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
    if len(items) > 1:
        updateTree(items[1::], inTree.children[items[0]], headerTable, count)

def updateHeader(nodeToTest, targetNode):  
    while (nodeToTest.nodeLink != None):   
        nodeToTest = nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode

抽取条件模式基(conditional pattern base)以及递归查找频繁项集。

#发现以给定元素项结尾的所有路径
def ascendTree(leafNode, prefixPath): #迭代上溯整棵树
    if leafNode.parent != None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent, prefixPath)

def findPrefixPath(basePat, treeNode): 
    #返回basePat对于的所有前缀和计数,treeNode是其对应的第一个节点
    condPats = {}
    while treeNode != None:
        prefixPath = []
        ascendTree(treeNode, prefixPath)
        if len(prefixPath) > 1: 
            condPats[frozenset(prefixPath[1:])] = treeNode.count
        treeNode = treeNode.nodeLink
    return condPats

def mineTree(inTree, headerTable, minSup, preFix, freqItemList): #递归查找频繁项集的函数
    bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])]#排序头指针
    for basePat in bigL:  #从头指针表的底端开始
        newFreqSet = preFix.copy()
        newFreqSet.add(basePat)

        freqItemList.append(newFreqSet)
        condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
        #从条件模式基构建FP树
        myCondTree, myHead = createTree(condPattBases, minSup)

        if myHead != None: #挖掘条件FP树
            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)

创建一个虚拟的数据集进行测试:

def createInitSet(dataSet):
    retDict = {}
    for trans in dataSet:
        retDict[frozenset(trans)] = 1
    return retDict

#测试数据
simpDat = [['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 = createInitSet(simpDat)
myFPtree, myHeaderTab = createTree(initSet,3)
myFPtree.disp()
myFreqList = []
mineTree(myFPtree, myHeaderTab, 3, set([]), myFreqList)

输出:

 Null Set   1
     z   5
       r   1
       x   3
         y   3
           s   2
             t   2
           r   1
             t   1
     x   1
       s   1
         r   1

关联分析还有其他的算法,以后自己肯定还会进行更深入的学习,这两篇文章分别记录了Apriori算法FP growth算法,这两个算法是很基础的,并且我们从FP growth算法对Apriori算法的改进中也应该体会这种优化的思维。这在自己建模以及使用经典模型中是很重要的。

本文相关内容同步于readingForDS[1]。

References

[1] readingForDS: https://github.com/QLWeilcf/LcfsPythonWork/blob/master/readingForDS

本文分享自微信公众号 - 蛰虫始航(lyns_sailing),作者:蛰虫始航

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • D3库实践笔记之几类特定图表与布局 |可视化系列37

    布局(Layout)可以看成是D3对图形元素的一种排布方式,在绘制柱状图时,是在横平竖直的直角坐标系下,确定矩形的左上角坐标,就可以画出随着高度变化的一系列柱子...

    蛰虫始航
  • 读Python数据分析基础之Excel读写与处理

    对于业务型数据分析来说,Excel可以说是打交道最多的软件了,可以说没有之一。之前有比较系统地读过《Python数据分析基础》(Foundations for ...

    蛰虫始航
  • 《使用D3设计交互式图表》简读笔记|可视化系列31

    本文是《数据可视化实战:使用D3设计交互式图表》[1]的简要版读书笔记,通过约4000字概览如何用D3做可视化、实践从数据到图形的过程。D3是一个根据数据操纵文...

    蛰虫始航
  • 机器学习(九)—FP-growth算法

      本来老师是想让我学Hadoop的,也装了Ubuntu,配置了Hadoop,一时间却不知从何学起,加之自己还是想先看点自己喜欢的算法,学习Hadoop也就暂且...

    oYabea
  • FP-growth算法的python实现

    FP-growth算法是一种用于发现数据集中频繁模式的有效方法。Apriori算法在产生频繁模式完全集前需要对数据库进行多次扫描,同时产生大量的候选频繁集,这就...

    用户6021899
  • 如何构建可扩展的应用程序

    所以你有一个很棒的主意。而且你有来自大学的朋友可以帮助你开始构建你的应用程序。您也可以从早期采用者那里获得很好的反馈。所以你做任何人都会做的事。启动你的应用!

    February
  • python实现密度聚类(模板代码+sklearn代码)

    本人在此就不搬运书上关于密度聚类的理论知识了,仅仅实现密度聚类的模板代码和调用skelarn的密度聚类算法。 有人好奇,为什么有sklearn库了还要自己去实...

    砸漏
  • 编程资源

    现在网上视频资源很多,我一开始很喜欢这些资源,看到了也总想保存,有种感觉是收藏了自己就一定会看,看了就一定会用。其实资源太多,太杂并不是好事,会让你不知道应该看...

    企鹅号小编
  • 第三十三课 如何创建自己的ERC721非同质化资产生物商店?

    从加密猫游戏开始,非同质化资产NFT的概念深入人心。不过现在社区中讲概念的多,真正落地发布自己ERC721资产的文章没有看到。辉哥这篇文章就来弥补下这个空缺。 ...

    辉哥
  • 如何在 Ubuntu 18.04 上安装和配置 Cyberpanel

    CyberPanel 是开源和使用 OpenLiteSpeed 的市场中第一个控制面板。意思就是说,和其他使用传统网站服务器的面板相比,CyberPanel 可...

    雪梦科技

扫码关注云+社区

领取腾讯云代金券