厦门市网站建设app开发,企业网站seo推广,江西做网站哪家好,辽宁seo推广公司目录 #第一关#xff1a;头表建设 任务描述
本关任务#xff1a;认识 FPgrowth 算法及FP树的头表构建。
相关知识
为了完成本关任务#xff0c;你需要掌握#xff1a;FP 树表示法及头表构建。
本节我们开始介绍一种称作 FP增长的算法。该算法采用完全不同的方法来发现频…目录 #第一关头表建设 任务描述
本关任务认识 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。 该过程是头表的构建过程主要的代码实现如下 # 统计各项出现次数# 第一次遍历得到频繁一项集headerTable {} #头表构建for k in item_count: # 剔除不满足最小支持度的项if item_count[k] min_support:headerTable[k] item_count[k]freqItemSet set(headerTable.keys()) # 满足最小支持度的频繁项集
编程要求
根据提示在右侧编辑器Begin和End之间补充代码完成 头表构建的过程。
测试说明
点击评测平台会对你编写的代码进行测试。 如程序无误运行程序后提示程序执行成功结果见文档输出。输出会展示在文档中 如程序有误无法通过评测且提示程序执行出错。
import os
import time
from tqdm import tqdmclass Node():def __init__(self, node_name, count, parentNode):self.name node_nameself.count countself.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.nodeLinknode.nodeLink targetNodedef update_fptree(self, items, node, headerTable): # 用于更新fptreeif items[0] in node.children:# 判断items的第一个结点是否已作为子结点node.children[items[0]].count 1else:# 创建新的分支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, flagFalse): # FPTree构建, 建树主函数根据data_set创建fp树header_table结构为{nodename:[num,node],..} 根据node.nodelink可以找到整个树中的所有nodename###########Begin#####################End###########if flag:ite tqdm(data_set)else:ite data_setfor t in ite: # 第二次遍历建树localD {}for item in t:if item in freqItemSet: # 过滤只取该样本中满足最小支持度的频繁项localD[item] headerTable[item][0] # element : countif len(localD) 0:# 根据全局频数从大到小对单样本排序order_item [v[0] for v in sorted(localD.items(), keylambda x: x[1], reverseTrue)]# 用过滤且排序后的样本更新树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] 1else:item_count[item] 1headerTable {} #头表构建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 : countif len(localD) 0:# 根据全局频数从大到小对单样本排序order_item [v[0] for v in sorted(localD.items(), keylambda x: x[1], reverseTrue)]# 用过滤且排序后的样本更新树self.update_fptree(order_item, tree_header, headerTable)
上图构建的 FP 树还包含一个连接具有相同项的结点的指针列表。这些指针用虚线表示有助于方便快速地访问树中的项。之后将使用FP树和它的相应指针产生频繁项集。
编程要求
根据提示在右侧编辑器Begin和End之间补充代码完成 FPtree的构建过程。
测试说明
点击评测平台会对你编写的代码进行测试。 如程序无误运行程序后提示程序执行成功结果见文档输出。输出会展示在文档中 如程序有误无法通过评测且提示程序执行出错。
源代码
import os
import time
from tqdm import tqdmclass Node():def __init__(self, node_name, count, parentNode):self.name node_nameself.count countself.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.nodeLinknode.nodeLink targetNodedef update_fptree(self, items, node, headerTable): # 用于更新fptreeif items[0] in node.children:# 判断items的第一个结点是否已作为子结点node.children[items[0]].count 1else:# 创建新的分支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, flagFalse): # 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] 1else:item_count[item] 1headerTable {} #头表构建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_setfor t in ite: # 第二次遍历建树localD {}for item in t:if item in freqItemSet: # 过滤只取该样本中满足最小支持度的频繁项localD[item] headerTable[item][0] # element : countif len(localD) 0:# 根据全局频数从大到小对单样本排序order_item [v[0] for v in sorted(localD.items(), keylambda x: x[1], reverseTrue)]# 用过滤且排序后的样本更新树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分别显示了这些项的路径而它们对应的频繁项集汇总如下
后缀频繁项集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}条件模式树过程的实现代码为 cond_pat_base fp.find_cond_pattern_base(e, 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 fp.create_fptree(cond_pat_dataset, min_support)
编程要求
根据提示在右侧编辑器Begin和End之间补充代码完成 FP条件树的构建过程。
测试说明
点击评测平台会对你编写的代码进行测试。 如程序无误运行程序后提示程序执行成功结果见文档输出。输出会展示在文档中 如程序有误无法通过评测且提示程序执行出错。
源代码
import os
import time
from tqdm import tqdmclass Node:def __init__(self, node_name, count, parentNode):self.name node_nameself.count countself.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.nodeLinknode.nodeLink targetNodedef update_fptree(self, items, node, headerTable): # 用于更新fptreeif items[0] in node.children:# 判断items的第一个结点是否已作为子结点node.children[items[0]].count 1else:# 创建新的分支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, flagFalse): # FPTree构建, 建树主函数根据data_set创建fp树header_table结构为{nodename:[num,node],..} 根据node.nodelink可以找到整个树中的所有nodenameitem_count {} # 统计各项出现次数for t in data_set: # 第一次遍历得到频繁一项集for item in t:if item not in item_count:item_count[item] 1else:item_count[item] 1headerTable {} #头表构建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, Nonefor 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_setfor t in ite: # 第二次遍历建树localD {}for item in t:if item in freqItemSet: # 过滤只取该样本中满足最小支持度的频繁项localD[item] headerTable[item][0] # element : countif len(localD) 0:# 根据全局频数从大到小对单样本排序order_item [v[0] for v in sorted(localD.items(), keylambda x: x[1], reverseTrue)]# 用过滤且排序后的样本更新树self.update_fptree(order_item, tree_header, headerTable)return tree_header, headerTabledef 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.counttreeNode treeNode.nodeLinkreturn cond_pat_basedef 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(), keylambda 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 增长算法的频繁项集产生
上一个关卡中我们通过123步骤已经完成了{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项集的过程的实现如下 # 将条件模式基字典转化为数组# 创建条件模式树cond_tree, cur_headtable fp.create_fptree(cond_pat_dataset, min_support)freqItemSet set()support_data {}if cur_headtable ! None:fp.create_cond_fptree(cur_headtable, min_support, set(), freqItemSet, support_data) # 递归挖掘条件FP树print(cur_headtable)#根据e的条件FP树计算以e为结尾的频繁二项集
FP 增长是一一个有趣的算法它展示了如何使用事务数据集的压缩表示来有效地产生频繁项集。此外对于某些事务数据集FP增长算法比标准的 Apriori 算法要快几个数量级。FP增长算法的运行性能依赖于数据集的压缩因子(compaction factor)。如果生成的条件P树非常茂盛(在最坏情形下是一棵满前缀树)则算法的性能显著下降因为算法必须产生大量的子问题并且需要合并每个子问题返回的结果。
编程要求
根据提示在右侧编辑器Begin和End之间补充代码完成 FP 增长算法寻找频繁二项集的过程。
测试说明
点击评测平台会对你编写的代码进行测试。 如程序无误运行程序后提示程序执行成功结果见文档输出。输出会展示在文档中 如程序有误无法通过评测且提示程序执行出错。
通关代码我在最后面print那里加了else也能通关
import os
import time
from tqdm import tqdmclass Node:def __init__(self, node_name, count, parentNode):self.name node_nameself.count countself.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.nodeLinknode.nodeLink targetNodedef update_fptree(self, items, node, headerTable): # 用于更新fptreeif items[0] in node.children:# 判断items的第一个结点是否已作为子结点node.children[items[0]].count 1else:# 创建新的分支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, flagFalse): # FPTree构建, 建树主函数根据data_set创建fp树header_table结构为{nodename:[num,node],..} 根据node.nodelink可以找到整个树中的所有nodenameitem_count {} # 统计各项出现次数for t in data_set: # 第一次遍历得到频繁一项集for item in t:if item not in item_count:item_count[item] 1else:item_count[item] 1headerTable {} #头表构建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, Nonefor 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_setfor t in ite: # 第二次遍历建树localD {}for item in t:if item in freqItemSet: # 过滤只取该样本中满足最小支持度的频繁项localD[item] headerTable[item][0] # element : countif len(localD) 0:# 根据全局频数从大到小对单样本排序order_item [v[0] for v in sorted(localD.items(), keylambda x: x[1], reverseTrue)]# 用过滤且排序后的样本更新树self.update_fptree(order_item, tree_header, headerTable)return tree_header, headerTabledef 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.counttreeNode treeNode.nodeLinkreturn cond_pat_basedef create_cond_fptree(self, headerTable, min_support, temp, freq_items, support_data):# 创建条件树# 最开始的频繁项集是headerTable中的各元素freqs [v[0] for v in sorted(headerTable.items(), keylambda 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, flagTrue) # 创建数据集的fptree# 创建各频繁一项的fptree并挖掘频繁项并保存支持度计数self.create_cond_fptree(headerTable, min_support, set(), freqItemSet, support_data)max_l 0for 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_datadef 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_dataconf 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: , confrule_list.append(big_rule)sub_set_list.append(freq_set)rule_list sorted(rule_list, keylambda x: (x[2]), reverseTrue)return rule_listif __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项集# 创建Fptreee_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_headtableelse:print(No frequent itemsets found for the given condition.)
