头歌实践教学平台-FPgrowth算法

目录

#第一关：头表建设

任务描述

本关任务：认识 FPgrowth 算法及FP树的头表构建。

相关知识

为了完成本关任务，你需要掌握：FP 树表示法及头表构建。

本节我们开始介绍一种称作 FP增长的算法。该算法采用完全不同的方法来发现频繁项集。该算法不同于 Apriori 算法的“产生测试”范型，而是使用一种称作 FP 树的紧凑数据结构组织数据，并直接从该结构中提取频繁项集。下面详细说明该方法。

FP树表示法及头表构建

FP 树是一种输入数据的压缩表示，它通过逐个读入事务，并把每个事务映射到 FP 树中的一条路径来构造。由于不同的事务可能会有若千个相同的项，因此它们的路径可能部分重叠。路径相互重叠越多，使用 FP 树结构获得的压缩的效果越好。如果 FP 树足够小，能够存放在内存中，就可以直接从这个内存中的结构提取频繁项集，而不必重复地扫描存放在硬盘上的数据。

图一 构建的FP树

上图显示了一个数据集，它包含 10 个事务和 5 个项。图中还绘制了读入前 3 个事务之后FP树的结构。树中每一个结点都包括一个项的标记和一个计数，计数显示映射到给定路径的事务个数。初始，FP 树仅包含一个根结点，用符号null标记。随后，用如下方法扩充 FP 树: (1) 扫描一次数据集，确定每个项的支持度计数。丢弃非频繁项，而将频繁项按照支持度的递减排序。对于上图中的数据集，a是最频繁的项，接下来依次是b,c, d,e。
该过程是头表的构建过程，主要的代码实现如下：

1. # 统计各项出现次数
3. # 第一次遍历，得到频繁一项集
5. headerTable = {} #头表构建
6. for k in item_count: # 剔除不满足最小支持度的项
7. if item_count[k] >= min_support:
8. headerTable[k] = item_count[k]
10. freqItemSet = set(headerTable.keys()) # 满足最小支持度的频繁项集

编程要求

根据提示，在右侧编辑器Begin和End之间补充代码，完成 头表构建的过程。

测试说明

点击评测，平台会对你编写的代码进行测试。 如程序无误，运行程序后提示程序执行成功，结果见文档输出。，输出会展示在文档中； 如程序有误，无法通过评测，且提示程序执行出错。

import os
import time
from tqdm import tqdm

class Node():
    def __init__(self, node_name, count, parentNode):
        self.name = node_name
        self.count = count
        self.nodeLink = None  # 根据nideLink可以找到整棵树中所有nodename一样的节点
        self.parent = parentNode  # 父亲节点
        self.children = {}  # 子节点{节点名字:节点地址}

        
class Fp_tree():
    def update_header(self, node, targetNode):  # 更新headertable中的node节点形成的链表
        while node.nodeLink != None:
            node = node.nodeLink
        node.nodeLink = targetNode

    def update_fptree(self, items, node, headerTable):  # 用于更新fptree
        if items[0] in node.children:
            # 判断items的第一个结点是否已作为子结点
            node.children[items[0]].count += 1
        else:
            # 创建新的分支
            node.children[items[0]] = Node(items[0], 1, node)
            # 更新相应频繁项集的链表，往后添加
            if headerTable[items[0]][1] == None:
                headerTable[items[0]][1] = node.children[items[0]]
            else:
                self.update_header(headerTable[items[0]][1], node.children[items[0]])
        # 递归
        if len(items) > 1:
            self.update_fptree(items[1:], node.children[items[0]], headerTable)

    def create_fptree(self, data_set, min_support, flag=False):  # FPTree构建, 建树主函数
        '''
        根据data_set创建fp树
        header_table结构为
        {"nodename":[num,node],..} 根据node.nodelink可以找到整个树中的所有nodename
        '''

        ###########Begin##########
       


        ###########End###########
        
        if flag:
            ite = tqdm(data_set)
        else:
            ite = data_set
        for t in ite:  # 第二次遍历，建树
            localD = {}
            for item in t:
                if item in freqItemSet:  # 过滤，只取该样本中满足最小支持度的频繁项
                    localD[item] = headerTable[item][0]  # element : count
            if len(localD) > 0:
                # 根据全局频数从大到小对单样本排序
                order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
                # 用过滤且排序后的样本更新树
                self.update_fptree(order_item, tree_header, headerTable)
        return tree_header, headerTable

第一关通关代码

        ###########Begin##########
        # 头表构建
        item_count = {}  # 统计各项出现次数
        for t in data_set:  # 第一次遍历，得到频繁一项集
            for item in t:
                if item not in item_count:
                    item_count[item] = 1
                else:
                    item_count[item] += 1
        headerTable = {}  #头表构建
        for k in item_count:  # 剔除不满足最小支持度的项
            if item_count[k] >= min_support:
                headerTable[k] = [item_count[k], None]  # element: [count, node]
        
        freqItemSet = set(headerTable.keys())  # 满足最小支持度的频繁项集
        tree_header = Node('head node', 1, None)


        ###########End###########

第二关：FPtree构建

任务描述

本关任务：完成FPtree的构建。

相关知识

为了完成本关任务，你需要掌握：1. FP 树表示法，2.FPtree的构建。

图一 构建的FP树 上节我们对FPtree做了基本认识并构建的头表，下面我们来看它整体的构造过程。初始，FP 树仅包含一个根结点，用符号null标记。随后，用如下方法扩充 FP 树: (1) 扫描一次数据集，确定每个项的支持度计数。丢弃非频繁项，而将频繁项按照支持度的递减排序。对于上图中的数据集，a是最频繁的项，接下来依次是b,c, d,e。

(2) 算法第二次扫描数据集，构建 FP 树。读入第一个事务{a, b}之后，创建标记为 a 和 b 的结点。然后形成null→a→b路径，对该事务编码。该路径上的所有结点的频度计数为 1 。

(3) 读入第二个事务{b, c, d}之后，为项 b, c 和 d 创建新的结点集。然后，连接结点null→b→c→d,形成一条代表该事务的路径。该路径上的每个结点的频度计数也等于1。尽管前两个事务具有一个共同项 b ，但是它们的路径不相交，因为这两个事务没有共同的前缀。

(4) 第三个事务{a, c, d, e}与第一个事务共享一个共同前缀项 a ，所以第三个事务的路径null→a→c→d→e与第-个事务的路径null→a→b部分重叠。因为它们的路径重叠，所以结点 a 的频度计数增加为 2 ，而新创建的结点 c , d 和 e 的频度计数等于 1 。

(5) 继续该过程,直到每个事务都映射到 FP 树的一条路径。读入所有的事务后即可形成的 FP 树。

整个FP树构建的代码实现如下：

for t in ite:  # 第二次遍历，建树
    localD = {}
    for item in t:
        if item in freqItemSet:  # 过滤，只取该样本中满足最小支持度的频繁项
            localD[item] = headerTable[item][0]  # element : count
    if len(localD) > 0:
        # 根据全局频数从大到小对单样本排序
        order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
        # 用过滤且排序后的样本更新树
        self.update_fptree(order_item, tree_header, headerTable)

上图构建的 FP 树还包含一个连接具有相同项的结点的指针列表。这些指针用虚线表示，有助于方便快速地访问树中的项。之后将使用FP树和它的相应指针产生频繁项集。

编程要求

根据提示，在右侧编辑器Begin和End之间补充代码，完成 FPtree的构建过程。

测试说明

点击评测，平台会对你编写的代码进行测试。 如程序无误，运行程序后提示程序执行成功，结果见文档输出。，输出会展示在文档中； 如程序有误，无法通过评测，且提示程序执行出错。

源代码

import os
import time
from tqdm import tqdm

class Node():
    def __init__(self, node_name, count, parentNode):
        self.name = node_name
        self.count = count
        self.nodeLink = None  # 根据nideLink可以找到整棵树中所有nodename一样的节点
        self.parent = parentNode  # 父亲节点
        self.children = {}  # 子节点{节点名字:节点地址}

        
class Fp_tree():
    def update_header(self, node, targetNode):  # 更新headertable中的node节点形成的链表
        while node.nodeLink != None:
            node = node.nodeLink
        node.nodeLink = targetNode

    def update_fptree(self, items, node, headerTable):  # 用于更新fptree
        if items[0] in node.children:
            # 判断items的第一个结点是否已作为子结点
            node.children[items[0]].count += 1
        else:
            # 创建新的分支
            node.children[items[0]] = Node(items[0], 1, node)
            # 更新相应频繁项集的链表，往后添加
            if headerTable[items[0]][1] == None:
                headerTable[items[0]][1] = node.children[items[0]]
            else:
                self.update_header(headerTable[items[0]][1], node.children[items[0]])
        # 递归
        if len(items) > 1:
            self.update_fptree(items[1:], node.children[items[0]], headerTable)

    def create_fptree(self, data_set, min_support, flag=False):  # FPTree构建, 建树主函数
        '''
        根据data_set创建fp树
        header_table结构为
        {"nodename":[num,node],..} 根据node.nodelink可以找到整个树中的所有nodename
        '''
        ###########Begin##########
        


        ###########End##########
        return tree_header, headerTable

通关代码

        ###########Begin##########
        # 头表构建
        item_count = {}  # 统计各项出现次数
        for t in data_set:  # 第一次遍历，得到频繁一项集
            for item in t:
                if item not in item_count:
                    item_count[item] = 1
                else:
                    item_count[item] += 1
        headerTable = {}  #头表构建
        for k in item_count:  # 剔除不满足最小支持度的项
            if item_count[k] >= min_support:
                headerTable[k] = [item_count[k], None]  # element: [count, node]
        
        freqItemSet = set(headerTable.keys())  # 满足最小支持度的频繁项集
        tree_header = Node('head node', 1, None)
        
        
        # 建树
        if flag:
            ite = tqdm(data_set)
        else:
            ite = data_set
        for t in ite:  # 第二次遍历，建树
            localD = {}
            for item in t:
                if item in freqItemSet:  # 过滤，只取该样本中满足最小支持度的频繁项
                    localD[item] = headerTable[item][0]  # element : count
            if len(localD) > 0:
                # 根据全局频数从大到小对单样本排序
                order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
                # 用过滤且排序后的样本更新树
                self.update_fptree(order_item, tree_header, headerTable)
        ###########End##########

第三关：{e)的条件FPtree构建

任务描述

本关任务：认识 FP 增长算法的频繁项集产生。

相关知识

为了完成本关任务，你需要掌握：FP 增长算法的频繁项集产生及条件FPtree构建。

FP 增长算法的频繁项集产生

FP 增长(FP-growth)是一种以自底向上方式探索树，由FP 树产生频繁项集的算法。给定图一产生的树，算法首先查找以 e 结尾的频繁项集，接下来依次是d,c,b,最后是a。由于每一个事务都映射到FP树中的一条路径，因而通过仅考察包含特定结点(例如e)的路径，就可以发现以e结尾的频繁项集.使用与结点e相关联的指针,可以快速访问这些路径。下图a显示了所提取的路径。之后我们便可以处理这些路径，以得到频繁项集。

图一 包含各结点的路径

发现以 e 结尾的频繁项集之后，算法通过处理与结点d相关联的路径，进一步寻找以 d 结尾的频繁项集。上图 b 显示了对应的路径。继续该过程，直到处理了所有与结点 c, b 和 a 相关联的路径为止。上图c、d、e分别显示了这些项的路径，而它们对应的频繁项集汇总如下：

FP 增长采用分治策略将一个问题分解为较小的子问题，从而发现以某个特定后缀结尾的所有频繁项集。例如，假设对发现所有以e结尾的频繁项集感兴趣。为了实现这个目的，必须首先检查项集{e}本身是否频繁。如果它是频繁的，则考虑发现以de结尾的频繁项集子问题，接下来是ce和ae。依次,每一个子问题可以进一步划分为更小的子问题。通过合并这些子问题得到的结果，就可以找到所有以 e 结尾的频繁项集。这种分治策略是FP增长算法采用的关键策略。

为了更具体地说明如何解决这些子问题，考虑发现所有以e结尾的频繁项集的任务:

(1) 第一步收集包含e结点的所有路径。这些初始的路径称为前缀路径(prefix path)，如图二 a 所示。

图二 使用FP增长算法发现以e结尾的频繁项集

(2) 由图二a中所显示的前缀路径，通过把与结点e相关联的支持度计数相加得到 e 的支持度计数。假定最小支持度为 2 ,因为{e}的支持度是 3 ，所以它是频繁项集。

(3) 由于{e}是频繁的，因此算法必须解决发现以de、ce、 be 和ae结尾的频繁项集的子问题。在解决这些子问题之前，必须先将前缀路径转化为条件 FP 树(conditional FP-tree)。除了用于发现以某特定后缀结尾的频繁项集之外,条件 FP 树的结构与FP树类似。 条件FP树通过以下步骤得到： (a) 首先，必须更新前缀路径上的支持度计数，因为某些计数包括那些不含项e的事务。例如，图二 a 中的最右边路径null→b:2→c:2→e:1,包括并不含项 e 的事务{b,c}.因此，必须将该前缀路径上的计数调整为 1 ,以反映包含{b, c, e}的事务的实际个数。 (b) 删除 e 的结点，修剪前缀路径。删除这些结点是因为，沿这些前缀路径的支持度计数已经更新，以反映包含e的那些事务，并且发现以de, ce, be和ae结尾的频繁项集的子问题不再需要结点e的信息。 (c) 更新沿前缀路径上的支持度计数之后，某些项可能不再是频繁的。例如，结点b只出现了 1 次，它的支持度计数等于 1 ,这就意味着只有一个事务同时包含b和e。因为所有以be结尾的项集一定都是非频繁的，所以在其后的分析中可以安全地忽略 b。 创建{e}条件模式树过程的实现代码为：

1. cond_pat_base = fp.find_cond_pattern_base('e', headerTable)
2. cond_pat_dataset = [] # 将条件模式基字典转化为数组
3. for item in cond_pat_base:
4. item_temp = list(item)
5. item_temp.sort()
6. for i in range(cond_pat_base[item]):
7. cond_pat_dataset.append(item_temp)
8. # 创建条件模式树
9. cond_tree, cur_headtable = fp.create_fptree(cond_pat_dataset, min_support)

编程要求

根据提示，在右侧编辑器Begin和End之间补充代码，完成 FP条件树的构建过程。

测试说明

点击评测，平台会对你编写的代码进行测试。 如程序无误，运行程序后提示程序执行成功，结果见文档输出。，输出会展示在文档中； 如程序有误，无法通过评测，且提示程序执行出错。

源代码

import os
import time
from tqdm import tqdm

class Node:
    def __init__(self, node_name, count, parentNode):
        self.name = node_name
        self.count = count
        self.nodeLink = None  # 根据nideLink可以找到整棵树中所有nodename一样的节点
        self.parent = parentNode  # 父亲节点
        self.children = {}  # 子节点{节点名字:节点地址}


class Base():
    def update_header(self, node, targetNode):  # 更新headertable中的node节点形成的链表
        while node.nodeLink != None:
            node = node.nodeLink
        node.nodeLink = targetNode

    def update_fptree(self, items, node, headerTable):  # 用于更新fptree
        if items[0] in node.children:
            # 判断items的第一个结点是否已作为子结点
            node.children[items[0]].count += 1
        else:
            # 创建新的分支
            node.children[items[0]] = Node(items[0], 1, node)
            # 更新相应频繁项集的链表，往后添加
            if headerTable[items[0]][1] == None:
                headerTable[items[0]][1] = node.children[items[0]]
            else:
                self.update_header(headerTable[items[0]][1], node.children[items[0]])
        # 递归
        if len(items) > 1:
            self.update_fptree(items[1:], node.children[items[0]], headerTable)

    def create_fptree(self, data_set, min_support, flag=False):  # FPTree构建, 建树主函数
        '''
        根据data_set创建fp树
        header_table结构为
        {"nodename":[num,node],..} 根据node.nodelink可以找到整个树中的所有nodename
        '''

        item_count = {}  # 统计各项出现次数
        for t in data_set:  # 第一次遍历，得到频繁一项集
            for item in t:
                if item not in item_count:
                    item_count[item] = 1
                else:
                    item_count[item] += 1
        headerTable = {}  #头表构建
        for k in item_count:  # 剔除不满足最小支持度的项
            if item_count[k] >= min_support:
                headerTable[k] = item_count[k]

        freqItemSet = set(headerTable.keys())  # 满足最小支持度的频繁项集
        if len(freqItemSet) == 0:
            return None, None
        for k in headerTable:
            headerTable[k] = [headerTable[k], None]  # element: [count, node]
        tree_header = Node('head node', 1, None)
        if flag:
            ite = tqdm(data_set)
        else:
            ite = data_set
        for t in ite:  # 第二次遍历，建树
            localD = {}
            for item in t:
                if item in freqItemSet:  # 过滤，只取该样本中满足最小支持度的频繁项
                    localD[item] = headerTable[item][0]  # element : count
            if len(localD) > 0:
                # 根据全局频数从大到小对单样本排序
                order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
                # 用过滤且排序后的样本更新树
                self.update_fptree(order_item, tree_header, headerTable)
        return tree_header, headerTable

    def find_path(self, node, nodepath):
        '''
        递归将node的父节点添加到路径
        '''
        if node.parent != None:
            nodepath.append(node.parent.name)
            self.find_path(node.parent, nodepath)

    def find_cond_pattern_base(self, node_name, headerTable):
        '''
        根据节点名字，找出所有条件模式基
        '''
        treeNode = headerTable[node_name][1]
        cond_pat_base = {}  # 保存所有条件模式基
        while treeNode != None:
            nodepath = []
            self.find_path(treeNode, nodepath)
            if len(nodepath) > 1:
                cond_pat_base[frozenset(nodepath[:-1])] = treeNode.count
            treeNode = treeNode.nodeLink
        return cond_pat_base

    def create_cond_fptree(self, headerTable, min_support, temp, freq_items, support_data):
        '''
       条件树建立的过程
        '''
        ##########Begin##########




        ############End##########
        return cur_headtable

通关代码

        ##########Begin##########
        freqs = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])]  # 根据频繁项的总频次排序
        for freq in freqs:  # 对每个频繁项
            freq_set = temp.copy()
            freq_set.add(freq)
            freq_items.add(frozenset(freq_set))
            if frozenset(freq_set) not in support_data:  # 检查该频繁项是否在support_data中
                support_data[frozenset(freq_set)] = headerTable[freq][0]
            else:
                support_data[frozenset(freq_set)] += headerTable[freq][0]

            cond_pat_base = self.find_cond_pattern_base(freq, headerTable)  # 寻找到所有条件模式基
            cond_pat_dataset = []  # 将条件模式基字典转化为数组
            for item in cond_pat_base:
                item_temp = list(item)
                item_temp.sort()
                for i in range(cond_pat_base[item]):
                    cond_pat_dataset.append(item_temp)
            cond_tree, cur_headtable = self.create_fptree(cond_pat_dataset, min_support)
            if cur_headtable != None:
                self.create_cond_fptree(cur_headtable, min_support, freq_set, freq_items, support_data)  # 递归挖掘条件FP树
        return cur_headtable
        ############End##########

第四关：根据由{e)结尾的条件FPtree树计算由(e)结尾的频繁2项集

任务描述

本关任务：认识 FPgrowth 算法计算频繁项集。

相关知识

为了完成本关任务，你需要掌握：根据由{e)结尾的条件FPtree树计算由(e)结尾的频繁2项集。

FP 增长算法的频繁项集产生

上一个关卡中，我们通过（1）（2）（3）步骤已经完成了{e}条件下的FPtree构建，下面我们接着来看如何通过该条件树计算由(e)结尾的频繁2项集。

(4) FP 增长使用 e 的条件FP树来解决发现以de, ce, be和ae结尾的频繁项集的子问题。为了发现以 de 结尾的频繁项集，从项e的条件FP树收集d的所有前缀路径.通过将与结点 d 相关联的频度计数求和，得到项集{d, e}的支持度计数。因为项集{d, e}的支持度计数等于 2 ，所以它是频繁项集。接下来，算法采用第 3 步介绍的方法构建de的条件FP树。更新了支持度计数并删除了非频繁项c之后，de 的条件FP树显示在图三d中。因为该条件FP树只包含一个支持度等于最小支持度的项a,算法提取出频繁项集{a, d, e}并转到下一-个子问题，产生以ce结尾的频繁项集。处理c的前缀路径后，只发现项集{c, e}是频繁的。接下来，算法继续解决下一个子问题并发现项集{a, e}是剩下唯一的频繁项集。 使用e的条件FP树来计算以{e}结尾的频繁2项集的过程的实现如下：

1. # 将条件模式基字典转化为数组
2. # 创建条件模式树
3. cond_tree, cur_headtable = fp.create_fptree(cond_pat_dataset, min_support)
4. freqItemSet = set()
5. support_data = {}
6. if cur_headtable != None:
7. fp.create_cond_fptree(cur_headtable, min_support, set(), freqItemSet, support_data) # 递归挖掘条件FP树
8. print(cur_headtable)#根据e的条件FP树计算以e为结尾的频繁二项集

FP 增长是一一个有趣的算法，它展示了如何使用事务数据集的压缩表示来有效地产生频繁项集。此外，对于某些事务数据集，FP增长算法比标准的 Apriori 算法要快几个数量级。FP增长算法的运行性能依赖于数据集的压缩因子(compaction factor)。如果生成的条件P树非常茂盛(在最坏情形下，是一棵满前缀树)，则算法的性能显著下降，因为算法必须产生大量的子问题，并且需要合并每个子问题返回的结果。

编程要求

根据提示，在右侧编辑器Begin和End之间补充代码，完成 FP 增长算法寻找频繁二项集的过程。

测试说明

点击评测，平台会对你编写的代码进行测试。 如程序无误，运行程序后提示程序执行成功，结果见文档输出。，输出会展示在文档中； 如程序有误，无法通过评测，且提示程序执行出错。

通关代码（我在最后面print那里加了else，也能通关）文章来源地址https://www.toymoban.com/news/detail-853409.html

import os
import time
from tqdm import tqdm

class Node:
    def __init__(self, node_name, count, parentNode):
        self.name = node_name
        self.count = count
        self.nodeLink = None  # 根据nideLink可以找到整棵树中所有nodename一样的节点
        self.parent = parentNode  # 父亲节点
        self.children = {}  # 子节点{节点名字:节点地址}


class Fp_growth():
    def update_header(self, node, targetNode):  # 更新headertable中的node节点形成的链表
        while node.nodeLink != None:
            node = node.nodeLink
        node.nodeLink = targetNode

    def update_fptree(self, items, node, headerTable):  # 用于更新fptree
        if items[0] in node.children:
            # 判断items的第一个结点是否已作为子结点
            node.children[items[0]].count += 1
        else:
            # 创建新的分支
            node.children[items[0]] = Node(items[0], 1, node)
            # 更新相应频繁项集的链表，往后添加
            if headerTable[items[0]][1] == None:
                headerTable[items[0]][1] = node.children[items[0]]
            else:
                self.update_header(headerTable[items[0]][1], node.children[items[0]])
        # 递归
        if len(items) > 1:
            self.update_fptree(items[1:], node.children[items[0]], headerTable)

    def create_fptree(self, data_set, min_support, flag=False):  # FPTree构建, 建树主函数
        '''
        根据data_set创建fp树
        header_table结构为
        {"nodename":[num,node],..} 根据node.nodelink可以找到整个树中的所有nodename
        '''

        item_count = {}  # 统计各项出现次数
        for t in data_set:  # 第一次遍历，得到频繁一项集
            for item in t:
                if item not in item_count:
                    item_count[item] = 1
                else:
                    item_count[item] += 1
        headerTable = {}  #头表构建
        for k in item_count:  # 剔除不满足最小支持度的项
            if item_count[k] >= min_support:
                headerTable[k] = item_count[k]

        freqItemSet = set(headerTable.keys())  # 满足最小支持度的频繁项集
        if len(freqItemSet) == 0:
            return None, None
        for k in headerTable:
            headerTable[k] = [headerTable[k], None]  # element: [count, node]
        tree_header = Node('head node', 1, None)
        if flag:
            ite = tqdm(data_set)
        else:
            ite = data_set
        for t in ite:  # 第二次遍历，建树
            localD = {}
            for item in t:
                if item in freqItemSet:  # 过滤，只取该样本中满足最小支持度的频繁项
                    localD[item] = headerTable[item][0]  # element : count
            if len(localD) > 0:
                # 根据全局频数从大到小对单样本排序
                order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
                # 用过滤且排序后的样本更新树
                self.update_fptree(order_item, tree_header, headerTable)
        return tree_header, headerTable

    def find_path(self, node, nodepath):
        '''
        递归将node的父节点添加到路径
        '''
        if node.parent != None:
            nodepath.append(node.parent.name)
            self.find_path(node.parent, nodepath)

    def find_cond_pattern_base(self, node_name, headerTable):
        '''
        根据节点名字，找出所有条件模式基
        '''
        treeNode = headerTable[node_name][1]
        cond_pat_base = {}  # 保存所有条件模式基
        while treeNode != None:
            nodepath = []
            self.find_path(treeNode, nodepath)
            if len(nodepath) > 1:
                cond_pat_base[frozenset(nodepath[:-1])] = treeNode.count
            treeNode = treeNode.nodeLink
        return cond_pat_base

    def create_cond_fptree(self, headerTable, min_support, temp, freq_items, support_data):
        '''
        # 创建条件树
        '''
        # 最开始的频繁项集是headerTable中的各元素
        freqs = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])]  # 根据频繁项的总频次排序
        for freq in freqs:  # 对每个频繁项
            freq_set = temp.copy()
            freq_set.add(freq)
            freq_items.add(frozenset(freq_set))
            if frozenset(freq_set) not in support_data:  # 检查该频繁项是否在support_data中
                support_data[frozenset(freq_set)] = headerTable[freq][0]
            else:
                support_data[frozenset(freq_set)] += headerTable[freq][0]

            cond_pat_base = self.find_cond_pattern_base(freq, headerTable)  # 寻找到所有条件模式基
            cond_pat_dataset = []  # 将条件模式基字典转化为数组
            for item in cond_pat_base:
                item_temp = list(item)
                item_temp.sort()
                for i in range(cond_pat_base[item]):
                    cond_pat_dataset.append(item_temp)
            # 创建条件模式树
            cond_tree, cur_headtable = self.create_fptree(cond_pat_dataset, min_support)
            if cur_headtable != None:
                self.create_cond_fptree(cur_headtable, min_support, freq_set, freq_items, support_data)  # 递归挖掘条件FP树


    def generate_L(self, data_set, min_support):
        freqItemSet = set()
        support_data = {}
        tree_header, headerTable = self.create_fptree(data_set, min_support, flag=True)  # 创建数据集的fptree
        # 创建各频繁一项的fptree，并挖掘频繁项并保存支持度计数
        self.create_cond_fptree(headerTable, min_support, set(), freqItemSet, support_data)

        max_l = 0
        for i in freqItemSet:  # 将频繁项根据大小保存到指定的容器L中
            if len(i) > max_l: max_l = len(i)
        L = [set() for _ in range(max_l)]
        for i in freqItemSet:
            L[len(i) - 1].add(i)
        for i in range(len(L)):
            print("frequent item {}:{}".format(i + 1, len(L[i])))
        return L, support_data

    def generate_R(self, data_set, min_support, min_conf):
        L, support_data = self.generate_L(data_set, min_support)
        rule_list = []
        sub_set_list = []
        for i in range(0, len(L)):
            for freq_set in L[i]:
                for sub_set in sub_set_list:
                    if sub_set.issubset(
                            freq_set) and freq_set - sub_set in support_data:  # and freq_set-sub_set in support_data
                        conf = support_data[freq_set] / support_data[freq_set - sub_set]
                        big_rule = (freq_set - sub_set, sub_set, conf)
                        if conf >= min_conf and big_rule not in rule_list:
                            # print freq_set-sub_set, " => ", sub_set, "conf: ", conf
                            rule_list.append(big_rule)
                sub_set_list.append(freq_set)
        rule_list = sorted(rule_list, key=lambda x: (x[2]), reverse=True)
        return rule_list


if __name__ == "__main__":

    min_support = 2  # 最小支持度
    min_conf = 0.5  # 最小置信度

    data_set = [['a', 'b'], ['b', 'c', 'd'], ['a','c', 'd','e'], ['a', 'd', 'e'], ['a', 'b','c'], ['b', 'c'], ['a', 'b','c','d'],
            ['a', 'b', 'd'], ['a', 'b', 'c'], ['b', 'c', 'e']]
    #根据dataset获得规则
    fp = Fp_growth()
    rule_list = fp.generate_R(data_set, min_support, min_conf)
    print(rule_list)

    ##############Begin##################
    # 根据由{e}结尾的条件FPtree树计算由{e}结尾的频繁2项集
    # 创建Fptree
    e_condition_tree, e_header_table = fp.create_fptree([['e']], min_support)
    if e_condition_tree is not None and e_header_table is not None:  # 检查结果是否为空
        cond_pattern_base = fp.find_cond_pattern_base('e', e_header_table)
        cond_pattern_dataset = []
        for item in cond_pattern_base:
            item_temp = list(item)
            item_temp.sort()
            for i in range(cond_pattern_base[item]):
                cond_pattern_dataset.append(item_temp)
        e_cond_tree, cur_headtable = fp.create_fptree(cond_pattern_dataset, min_support)
        print(cur_headtable)  # 在这里打印 cur_headtable
    else:
        print("No frequent itemsets found for the given condition.")

到了这里，关于头歌实践教学平台-FPgrowth算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！