devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

头歌实践教学平台-FPgrowth算法_graphaprior算法 第1关:候选生成一顶点增长 头歌

作者：知新_RL | 2024-05-03 09:17:47

赞

踩

graphaprior算法 第1关:候选生成一顶点增长 头歌

目录

#第一关：头表建设

任务描述

本关任务：认识 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之间补充代码，完成 头表构建的过程。
 

测试说明
 

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

  1. import os
  2. import time
  3. from tqdm import tqdm
  4.  
  5. class Node():
  6.     def __init__(self, node_name, count, parentNode):
  7.         self.name = node_name
  8.         self.count = count
  9.         self.nodeLink = None  # 根据nideLink可以找到整棵树中所有nodename一样的节点
  10.         self.parent = parentNode  # 父亲节点
  11.         self.children = {}  # 子节点{节点名字:节点地址}
  12.  
  13.         
  14. class Fp_tree():
  15.     def update_header(self, node, targetNode):  # 更新headertable中的node节点形成的链表
  16.         while node.nodeLink != None:
  17.             node = node.nodeLink
  18.         node.nodeLink = targetNode
  19.  
  20.     def update_fptree(self, items, node, headerTable):  # 用于更新fptree
  21.         if items[0] in node.children:
  22.             # 判断items的第一个结点是否已作为子结点
  23.             node.children[items[0]].count += 1
  24.         else:
  25.             # 创建新的分支
  26.             node.children[items[0]] = Node(items[0], 1, node)
  27.             # 更新相应频繁项集的链表，往后添加
  28.             if headerTable[items[0]][1] == None:
  29.                 headerTable[items[0]][1] = node.children[items[0]]
  30.             else:
  31.                 self.update_header(headerTable[items[0]][1], node.children[items[0]])
  32.         # 递归
  33.         if len(items) > 1:
  34.             self.update_fptree(items[1:], node.children[items[0]], headerTable)
  35.  
  36.     def create_fptree(self, data_set, min_support, flag=False):  # FPTree构建, 建树主函数
  37.         '''
  38.         根据data_set创建fp树
  39.         header_table结构为
  40.         {"nodename":[num,node],..} 根据node.nodelink可以找到整个树中的所有nodename
  41.         '''
  42.  
  43.         ###########Begin##########
  44.        
  45.  
  46.  
  47.         ###########End###########
  48.         
  49.         if flag:
  50.             ite = tqdm(data_set)
  51.         else:
  52.             ite = data_set
  53.         for t in ite:  # 第二次遍历，建树
  54.             localD = {}
  55.             for item in t:
  56.                 if item in freqItemSet:  # 过滤，只取该样本中满足最小支持度的频繁项
  57.                     localD[item] = headerTable[item][0]  # element : count
  58.             if len(localD) > 0:
  59.                 # 根据全局频数从大到小对单样本排序
  60.                 order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
  61.                 # 用过滤且排序后的样本更新树
  62.                 self.update_fptree(order_item, tree_header, headerTable)
  63.         return tree_header, headerTable
 

第一关通关代码
 

  1.         ###########Begin##########
  2.         # 头表构建
  3.         item_count = {}  # 统计各项出现次数
  4.         for t in data_set:  # 第一次遍历，得到频繁一项集
  5.             for item in t:
  6.                 if item not in item_count:
  7.                     item_count[item] = 1
  8.                 else:
  9.                     item_count[item] += 1
  10.         headerTable = {}  #头表构建
  11.         for k in item_count:  # 剔除不满足最小支持度的项
  12.             if item_count[k] >= min_support:
  13.                 headerTable[k] = [item_count[k], None]  # element: [count, node]
  14.         
  15.         freqItemSet = set(headerTable.keys())  # 满足最小支持度的频繁项集
  16.         tree_header = Node('head node', 1, None)
  17.  
  18.  
  19.         ###########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树构建的代码实现如下：
 

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

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

编程要求
 

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

测试说明
 

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

源代码
 

  1. import os
  2. import time
  3. from tqdm import tqdm
  4.  
  5. class Node():
  6.     def __init__(self, node_name, count, parentNode):
  7.         self.name = node_name
  8.         self.count = count
  9.         self.nodeLink = None  # 根据nideLink可以找到整棵树中所有nodename一样的节点
  10.         self.parent = parentNode  # 父亲节点
  11.         self.children = {}  # 子节点{节点名字:节点地址}
  12.  
  13.         
  14. class Fp_tree():
  15.     def update_header(self, node, targetNode):  # 更新headertable中的node节点形成的链表
  16.         while node.nodeLink != None:
  17.             node = node.nodeLink
  18.         node.nodeLink = targetNode
  19.  
  20.     def update_fptree(self, items, node, headerTable):  # 用于更新fptree
  21.         if items[0] in node.children:
  22.             # 判断items的第一个结点是否已作为子结点
  23.             node.children[items[0]].count += 1
  24.         else:
  25.             # 创建新的分支
  26.             node.children[items[0]] = Node(items[0], 1, node)
  27.             # 更新相应频繁项集的链表，往后添加
  28.             if headerTable[items[0]][1] == None:
  29.                 headerTable[items[0]][1] = node.children[items[0]]
  30.             else:
  31.                 self.update_header(headerTable[items[0]][1], node.children[items[0]])
  32.         # 递归
  33.         if len(items) > 1:
  34.             self.update_fptree(items[1:], node.children[items[0]], headerTable)
  35.  
  36.     def create_fptree(self, data_set, min_support, flag=False):  # FPTree构建, 建树主函数
  37.         '''
  38.         根据data_set创建fp树
  39.         header_table结构为
  40.         {"nodename":[num,node],..} 根据node.nodelink可以找到整个树中的所有nodename
  41.         '''
  42.         ###########Begin##########
  43.         
  44.  
  45.  
  46.         ###########End##########
  47.         return tree_header, headerTable
 

通关代码
 

  1.         ###########Begin##########
  2.         # 头表构建
  3.         item_count = {}  # 统计各项出现次数
  4.         for t in data_set:  # 第一次遍历，得到频繁一项集
  5.             for item in t:
  6.                 if item not in item_count:
  7.                     item_count[item] = 1
  8.                 else:
  9.                     item_count[item] += 1
  10.         headerTable = {}  #头表构建
  11.         for k in item_count:  # 剔除不满足最小支持度的项
  12.             if item_count[k] >= min_support:
  13.                 headerTable[k] = [item_count[k], None]  # element: [count, node]
  14.         
  15.         freqItemSet = set(headerTable.keys())  # 满足最小支持度的频繁项集
  16.         tree_header = Node('head node', 1, None)
  17.         
  18.         
  19.         # 建树
  20.         if flag:
  21.             ite = tqdm(data_set)
  22.         else:
  23.             ite = data_set
  24.         for t in ite:  # 第二次遍历，建树
  25.             localD = {}
  26.             for item in t:
  27.                 if item in freqItemSet:  # 过滤，只取该样本中满足最小支持度的频繁项
  28.                     localD[item] = headerTable[item][0]  # element : count
  29.             if len(localD) > 0:
  30.                 # 根据全局频数从大到小对单样本排序
  31.                 order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
  32.                 # 用过滤且排序后的样本更新树
  33.                 self.update_fptree(order_item, tree_header, headerTable)
  34.         ###########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分别显示了这些项的路径，而它们对应的频繁项集汇总如下：
 

后缀频繁项集
e{e},{d.e},{a,d,e},{c,e},{a,e}
d{d},{c,d},{b,c,d},{a,c,d},{b,d},{a,b,d},{a,d}
c{c],{b,c},{a,b,c},{a,c}
b{b},{a,b}
a{a}
 

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条件树的构建过程。
 

测试说明
 

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

源代码
 

  1. import os
  2. import time
  3. from tqdm import tqdm
  4.  
  5. class Node:
  6.     def __init__(self, node_name, count, parentNode):
  7.         self.name = node_name
  8.         self.count = count
  9.         self.nodeLink = None  # 根据nideLink可以找到整棵树中所有nodename一样的节点
  10.         self.parent = parentNode  # 父亲节点
  11.         self.children = {}  # 子节点{节点名字:节点地址}
  12.  
  13.  
  14. class Base():
  15.     def update_header(self, node, targetNode):  # 更新headertable中的node节点形成的链表
  16.         while node.nodeLink != None:
  17.             node = node.nodeLink
  18.         node.nodeLink = targetNode
  19.  
  20.     def update_fptree(self, items, node, headerTable):  # 用于更新fptree
  21.         if items[0] in node.children:
  22.             # 判断items的第一个结点是否已作为子结点
  23.             node.children[items[0]].count += 1
  24.         else:
  25.             # 创建新的分支
  26.             node.children[items[0]] = Node(items[0], 1, node)
  27.             # 更新相应频繁项集的链表，往后添加
  28.             if headerTable[items[0]][1] == None:
  29.                 headerTable[items[0]][1] = node.children[items[0]]
  30.             else:
  31.                 self.update_header(headerTable[items[0]][1], node.children[items[0]])
  32.         # 递归
  33.         if len(items) > 1:
  34.             self.update_fptree(items[1:], node.children[items[0]], headerTable)
  35.  
  36.     def create_fptree(self, data_set, min_support, flag=False):  # FPTree构建, 建树主函数
  37.         '''
  38.         根据data_set创建fp树
  39.         header_table结构为
  40.         {"nodename":[num,node],..} 根据node.nodelink可以找到整个树中的所有nodename
  41.         '''
  42.  
  43.         item_count = {}  # 统计各项出现次数
  44.         for t in data_set:  # 第一次遍历，得到频繁一项集
  45.             for item in t:
  46.                 if item not in item_count:
  47.                     item_count[item] = 1
  48.                 else:
  49.                     item_count[item] += 1
  50.         headerTable = {}  #头表构建
  51.         for k in item_count:  # 剔除不满足最小支持度的项
  52.             if item_count[k] >= min_support:
  53.                 headerTable[k] = item_count[k]
  54.  
  55.         freqItemSet = set(headerTable.keys())  # 满足最小支持度的频繁项集
  56.         if len(freqItemSet) == 0:
  57.             return None, None
  58.         for k in headerTable:
  59.             headerTable[k] = [headerTable[k], None]  # element: [count, node]
  60.         tree_header = Node('head node', 1, None)
  61.         if flag:
  62.             ite = tqdm(data_set)
  63.         else:
  64.             ite = data_set
  65.         for t in ite:  # 第二次遍历，建树
  66.             localD = {}
  67.             for item in t:
  68.                 if item in freqItemSet:  # 过滤，只取该样本中满足最小支持度的频繁项
  69.                     localD[item] = headerTable[item][0]  # element : count
  70.             if len(localD) > 0:
  71.                 # 根据全局频数从大到小对单样本排序
  72.                 order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
  73.                 # 用过滤且排序后的样本更新树
  74.                 self.update_fptree(order_item, tree_header, headerTable)
  75.         return tree_header, headerTable
  76.  
  77.     def find_path(self, node, nodepath):
  78.         '''
  79.         递归将node的父节点添加到路径
  80.         '''
  81.         if node.parent != None:
  82.             nodepath.append(node.parent.name)
  83.             self.find_path(node.parent, nodepath)
  84.  
  85.     def find_cond_pattern_base(self, node_name, headerTable):
  86.         '''
  87.         根据节点名字，找出所有条件模式基
  88.         '''
  89.         treeNode = headerTable[node_name][1]
  90.         cond_pat_base = {}  # 保存所有条件模式基
  91.         while treeNode != None:
  92.             nodepath = []
  93.             self.find_path(treeNode, nodepath)
  94.             if len(nodepath) > 1:
  95.                 cond_pat_base[frozenset(nodepath[:-1])] = treeNode.count
  96.             treeNode = treeNode.nodeLink
  97.         return cond_pat_base
  98.  
  99.     def create_cond_fptree(self, headerTable, min_support, temp, freq_items, support_data):
  100.         '''
  101.        条件树建立的过程
  102.         '''
  103.         ##########Begin##########
  104.  
  105.  
  106.  
  107.  
  108.         ############End##########
  109.         return cur_headtable
 

通关代码
 

  1.         ##########Begin##########
  2.         freqs = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])]  # 根据频繁项的总频次排序
  3.         for freq in freqs:  # 对每个频繁项
  4.             freq_set = temp.copy()
  5.             freq_set.add(freq)
  6.             freq_items.add(frozenset(freq_set))
  7.             if frozenset(freq_set) not in support_data:  # 检查该频繁项是否在support_data中
  8.                 support_data[frozenset(freq_set)] = headerTable[freq][0]
  9.             else:
  10.                 support_data[frozenset(freq_set)] += headerTable[freq][0]
  11.  
  12.             cond_pat_base = self.find_cond_pattern_base(freq, headerTable)  # 寻找到所有条件模式基
  13.             cond_pat_dataset = []  # 将条件模式基字典转化为数组
  14.             for item in cond_pat_base:
  15.                 item_temp = list(item)
  16.                 item_temp.sort()
  17.                 for i in range(cond_pat_base[item]):
  18.                     cond_pat_dataset.append(item_temp)
  19.             cond_tree, cur_headtable = self.create_fptree(cond_pat_dataset, min_support)
  20.             if cur_headtable != None:
  21.                 self.create_cond_fptree(cur_headtable, min_support, freq_set, freq_items, support_data)  # 递归挖掘条件FP树
  22.         return cur_headtable
  23.         ############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，也能通关）
 

  1. import os
  2. import time
  3. from tqdm import tqdm
  4.  
  5. class Node:
  6.     def __init__(self, node_name, count, parentNode):
  7.         self.name = node_name
  8.         self.count = count
  9.         self.nodeLink = None  # 根据nideLink可以找到整棵树中所有nodename一样的节点
  10.         self.parent = parentNode  # 父亲节点
  11.         self.children = {}  # 子节点{节点名字:节点地址}
  12.  
  13.  
  14. class Fp_growth():
  15.     def update_header(self, node, targetNode):  # 更新headertable中的node节点形成的链表
  16.         while node.nodeLink != None:
  17.             node = node.nodeLink
  18.         node.nodeLink = targetNode
  19.  
  20.     def update_fptree(self, items, node, headerTable):  # 用于更新fptree
  21.         if items[0] in node.children:
  22.             # 判断items的第一个结点是否已作为子结点
  23.             node.children[items[0]].count += 1
  24.         else:
  25.             # 创建新的分支
  26.             node.children[items[0]] = Node(items[0], 1, node)
  27.             # 更新相应频繁项集的链表，往后添加
  28.             if headerTable[items[0]][1] == None:
  29.                 headerTable[items[0]][1] = node.children[items[0]]
  30.             else:
  31.                 self.update_header(headerTable[items[0]][1], node.children[items[0]])
  32.         # 递归
  33.         if len(items) > 1:
  34.             self.update_fptree(items[1:], node.children[items[0]], headerTable)
  35.  
  36.     def create_fptree(self, data_set, min_support, flag=False):  # FPTree构建, 建树主函数
  37.         '''
  38.         根据data_set创建fp树
  39.         header_table结构为
  40.         {"nodename":[num,node],..} 根据node.nodelink可以找到整个树中的所有nodename
  41.         '''
  42.  
  43.         item_count = {}  # 统计各项出现次数
  44.         for t in data_set:  # 第一次遍历，得到频繁一项集
  45.             for item in t:
  46.                 if item not in item_count:
  47.                     item_count[item] = 1
  48.                 else:
  49.                     item_count[item] += 1
  50.         headerTable = {}  #头表构建
  51.         for k in item_count:  # 剔除不满足最小支持度的项
  52.             if item_count[k] >= min_support:
  53.                 headerTable[k] = item_count[k]
  54.  
  55.         freqItemSet = set(headerTable.keys())  # 满足最小支持度的频繁项集
  56.         if len(freqItemSet) == 0:
  57.             return None, None
  58.         for k in headerTable:
  59.             headerTable[k] = [headerTable[k], None]  # element: [count, node]
  60.         tree_header = Node('head node', 1, None)
  61.         if flag:
  62.             ite = tqdm(data_set)
  63.         else:
  64.             ite = data_set
  65.         for t in ite:  # 第二次遍历，建树
  66.             localD = {}
  67.             for item in t:
  68.                 if item in freqItemSet:  # 过滤，只取该样本中满足最小支持度的频繁项
  69.                     localD[item] = headerTable[item][0]  # element : count
  70.             if len(localD) > 0:
  71.                 # 根据全局频数从大到小对单样本排序
  72.                 order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
  73.                 # 用过滤且排序后的样本更新树
  74.                 self.update_fptree(order_item, tree_header, headerTable)
  75.         return tree_header, headerTable
  76.  
  77.     def find_path(self, node, nodepath):
  78.         '''
  79.         递归将node的父节点添加到路径
  80.         '''
  81.         if node.parent != None:
  82.             nodepath.append(node.parent.name)
  83.             self.find_path(node.parent, nodepath)
  84.  
  85.     def find_cond_pattern_base(self, node_name, headerTable):
  86.         '''
  87.         根据节点名字，找出所有条件模式基
  88.         '''
  89.         treeNode = headerTable[node_name][1]
  90.         cond_pat_base = {}  # 保存所有条件模式基
  91.         while treeNode != None:
  92.             nodepath = []
  93.             self.find_path(treeNode, nodepath)
  94.             if len(nodepath) > 1:
  95.                 cond_pat_base[frozenset(nodepath[:-1])] = treeNode.count
  96.             treeNode = treeNode.nodeLink
  97.         return cond_pat_base
  98.  
  99.     def create_cond_fptree(self, headerTable, min_support, temp, freq_items, support_data):
  100.         '''
  101.         # 创建条件树
  102.         '''
  103.         # 最开始的频繁项集是headerTable中的各元素
  104.         freqs = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])]  # 根据频繁项的总频次排序
  105.         for freq in freqs:  # 对每个频繁项
  106.             freq_set = temp.copy()
  107.             freq_set.add(freq)
  108.             freq_items.add(frozenset(freq_set))
  109.             if frozenset(freq_set) not in support_data:  # 检查该频繁项是否在support_data中
  110.                 support_data[frozenset(freq_set)] = headerTable[freq][0]
  111.             else:
  112.                 support_data[frozenset(freq_set)] += headerTable[freq][0]
  113.  
  114.             cond_pat_base = self.find_cond_pattern_base(freq, headerTable)  # 寻找到所有条件模式基
  115.             cond_pat_dataset = []  # 将条件模式基字典转化为数组
  116.             for item in cond_pat_base:
  117.                 item_temp = list(item)
  118.                 item_temp.sort()
  119.                 for i in range(cond_pat_base[item]):
  120.                     cond_pat_dataset.append(item_temp)
  121.             # 创建条件模式树
  122.             cond_tree, cur_headtable = self.create_fptree(cond_pat_dataset, min_support)
  123.             if cur_headtable != None:
  124.                 self.create_cond_fptree(cur_headtable, min_support, freq_set, freq_items, support_data)  # 递归挖掘条件FP树
  125.  
  126.  
  127.     def generate_L(self, data_set, min_support):
  128.         freqItemSet = set()
  129.         support_data = {}
  130.         tree_header, headerTable = self.create_fptree(data_set, min_support, flag=True)  # 创建数据集的fptree
  131.         # 创建各频繁一项的fptree，并挖掘频繁项并保存支持度计数
  132.         self.create_cond_fptree(headerTable, min_support, set(), freqItemSet, support_data)
  133.  
  134.         max_l = 0
  135.         for i in freqItemSet:  # 将频繁项根据大小保存到指定的容器L中
  136.             if len(i) > max_l: max_l = len(i)
  137.         L = [set() for _ in range(max_l)]
  138.         for i in freqItemSet:
  139.             L[len(i) - 1].add(i)
  140.         for i in range(len(L)):
  141.             print("frequent item {}:{}".format(i + 1, len(L[i])))
  142.         return L, support_data
  143.  
  144.     def generate_R(self, data_set, min_support, min_conf):
  145.         L, support_data = self.generate_L(data_set, min_support)
  146.         rule_list = []
  147.         sub_set_list = []
  148.         for i in range(0, len(L)):
  149.             for freq_set in L[i]:
  150.                 for sub_set in sub_set_list:
  151.                     if sub_set.issubset(
  152.                             freq_set) and freq_set - sub_set in support_data:  # and freq_set-sub_set in support_data
  153.                         conf = support_data[freq_set] / support_data[freq_set - sub_set]
  154.                         big_rule = (freq_set - sub_set, sub_set, conf)
  155.                         if conf >= min_conf and big_rule not in rule_list:
  156.                             # print freq_set-sub_set, " => ", sub_set, "conf: ", conf
  157.                             rule_list.append(big_rule)
  158.                 sub_set_list.append(freq_set)
  159.         rule_list = sorted(rule_list, key=lambda x: (x[2]), reverse=True)
  160.         return rule_list
  161.  
  162.  
  163. if __name__ == "__main__":
  164.  
  165.     min_support = 2  # 最小支持度
  166.     min_conf = 0.5  # 最小置信度
  167.  
  168.     data_set = [['a', 'b'], ['b', 'c', 'd'], ['a','c', 'd','e'], ['a', 'd', 'e'], ['a', 'b','c'], ['b', 'c'], ['a', 'b','c','d'],
  169.             ['a', 'b', 'd'], ['a', 'b', 'c'], ['b', 'c', 'e']]
  170.     #根据dataset获得规则
  171.     fp = Fp_growth()
  172.     rule_list = fp.generate_R(data_set, min_support, min_conf)
  173.     print(rule_list)
  174.  
  175.     ##############Begin##################
  176.     # 根据由{e}结尾的条件FPtree树计算由{e}结尾的频繁2项集
  177.     # 创建Fptree
  178.     e_condition_tree, e_header_table = fp.create_fptree([['e']], min_support)
  179.     if e_condition_tree is not None and e_header_table is not None:  # 检查结果是否为空
  180.         cond_pattern_base = fp.find_cond_pattern_base('e', e_header_table)
  181.         cond_pattern_dataset = []
  182.         for item in cond_pattern_base:
  183.             item_temp = list(item)
  184.             item_temp.sort()
  185.             for i in range(cond_pattern_base[item]):
  186.                 cond_pattern_dataset.append(item_temp)
  187.         e_cond_tree, cur_headtable = fp.create_fptree(cond_pattern_dataset, min_support)
  188.         print(cur_headtable)  # 在这里打印 cur_headtable
  189.     else:
  190.         print("No frequent itemsets found for the given condition.")
 


                

        声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签
Copyright ©  2003-2013 www.wpsshop.cn  版权所有，并保留所有权利。

  
闽ICP备14008679号