机器学习(11): FP |
您所在的位置：网站首页 › fp实验 › 机器学习(11): FP |
机器学习(11): FP
|
注：转载请标明原文出处链接：https://xiongyiming.blog.csdn.net/article/details/97782705 1 FP-growth算法简介众所周知，Apriori算法在产生频繁模式完全集前需要对数据库进行多次扫描，同时产生大量的候选频繁集，这就使Apriori算法时间和空间复杂度较大。但是Apriori算法中有一个很重要的性质：频繁项集的所有非空子集都必须也是频繁的。但是Apriori算法在挖掘额长频繁模式的时候性能往往低下，Jiawei Han提出了FP-Growth算法，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树(FP-tree)，但仍保留项集关联信息。 在算法中使用了一种称为频繁模式树(Frequent Pattern Tree)的数据结构。FP-tree是一种特殊的前缀树，由频繁项头表和项前缀树构成。FP-Growth算法基于以上的结构加快整个挖掘过程。 (以上均来自百度百科) 2 FP-growth算法原理使用百度搜索时，当你输入一个词语的时候，搜索引擎就会帮你自动补全你可能要查询的词项。比如，下图中所示，当我输入"机器学习"时，百度自动给出了"机器学习算法"、“机器学习python”、“机器学习 周志华”、"机器学习 周志华 pdf"这四个词条供我们参考。
从FP-growth算法挖掘频繁项集这个流程图中可以看出，FP-growth算法步骤为 FP-growth算法主要有两个步骤： 构建FP树从FP树中挖掘频繁项集 2.1 FP树的表示方式FP是频繁模式 (Frequent Pattern)的缩写。FP-growth算法将数据存储在一种称为FP树的的紧凑数据结构中，并直接从该结构中提取频繁项集。一棵FP树的结构如下图所示，和其他树结构不同之处是FP树通过链接(link)来连接相似元素，被连起来的元素项可以看成一个链表。可以说，FP树是一种用于编码数据集的有效方式。 为了快速访问树中的相同项，还需要维护一个连接具有相同项的节点的指针列表(headTable)，每个列表元素包括：数据项、该项的全局最小支持度、指向FP树中该项链表的表头的指针。
FP树的特点 一个元素项可以在一棵FP树中出现多次;项集以路径+频率的方式存储在FP树中;树节点中的频率表示的是集合中单个元素在其序列中出现的次数;一条路径表示的是一个事务，如果事务完全一致，则路径可以重合;相似项之间的链接即为节点链接(link)，主要是用来快速发现相似项的位置. 2.2 FP树的构建过程为了更好地理解FP树，我们通过一个例子构建FP树，简单数据集如下表所示 FP树的构建的步骤 统计原始事务集中各元素项出现的频率支持度过滤排序构建FP树具体步骤如下 (1) 统计原始事务集中各元素项出现的频率这一步主要作用是生成FP树的树节点，统计好的元素项及其频率即为我们所需要的树节点。根据原始事务集，我们可以计算中共有17个元素项，然后分别计算每个元素项在事务集中一共出现了多少次。统计结果如下表所示：
上表计算出来的所有树节点并非全部都是我们需要的树节点。我们构建FP树的主要目的是为了挖掘频繁项集，所以为了减少后续的计算量，在这一步我们就可以把不满足最小支持度的元素项给剔除了。因为我们知道，如果一个元素项是不频繁的，那么包含该元素项的超集也是不频繁的，所以就不需要考虑这些超集了。 假设这里我们定义最小支持度为3，那么进行支持度过滤之后得到的元素项为：
根据频率大小，将支持度过滤后的元素项(即频繁元素项)进行排序，并根据排序后的元素项，将原始事务集也进行排序。这样做的原因是，我们构建的FP树中，相同项只会出现一次，但是大家都知道集合是无序的，对于集合{x, y, z}和集合{z, y, x}我们可以一眼看出这两个集合是一样的，但是对于FP树来说，它会把这两个集合当做两个不同的集合，然后生成两条路径，这样的结果不是我们想要的。所以为了解决这样的问题，我们需要将集合添加到树之前对它们进行排序。 频繁元素项排序结果：
在对事务集过滤和重排序后，就可以构建FP树了。首先从空集(∅)开始，向其中不断添加频繁项集。如果树中已存在现有元素，则增加现有元素的值。如果现有元素不存在，则向树中添加一个分支。具体过程如下所示：
(1) 创建FP树的数据结构 由于FP树比之前建立的决策树要复杂，所以我们这里创建一个类来保存树的每一个节点。类中包含用于存放节点名字的变量和1个计数值，nodeLink变量用于链接相似的元素项，parent变量用于指向当前父节点(如果从上到下迭代访问节点的话不需要这个变量，此处使用是为后面的内容做铺垫)，空字典变量用于存放节点的子节点。 类中包含了两个方法： inc()方法的功能是对count变量增加给定值；disp()方法的功能是将树以文本形式显示，主要是方便调试。函数定义及测试 class treeNode: def __init__(self, nameValue, numOccur, parentNode): self.name = nameValue #名字变量 self.count = numOccur #计数变量(频率) self.nodeLink = None #链接相似元素项 self.parent = parentNode #当前父节点 self.children = {} #用于存放子节点 # inc 函数 对count变量增加给定值； def inc(self, numOccur): self.count += numOccur # disp()方法的功能是将树以文本形式显示，主要是方便调试 def disp(self, ind=1): print( ' ' *ind, self.name, ' ', self.count) for child in self.children.values(): child.disp(ind +1) #子节点向右缩减 #测试 # 显示节点 #创建一个单节点 rootNode = treeNode('这是父节点',9,None) #创建一个子节点 rootNode.children['这是子节点'] = treeNode('这是子节点',13,None) #显示节点 rootNode.disp() print("---------------------------------") #再增加一个子节点 rootNode.children['这是另一个子节点'] = treeNode('这是另一个子节点',3,None) #显示节点 rootNode.disp()结果如下 (2) 创建简单数据集 # 创建简单数据集 def loadSimpDat(): 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']] return simpDat data=loadSimpDat() print("data=",data)运行结果
(3) 创建FP树 a) 数据格式化 得到数据集后，我们需要遍历每一条交易数据，并把它们变成固定格式(frozenset)。这里使用了一个.setdefault()函数，该函数的功能是返回指定键的值，如果键不在字典中，将会添加键并将值设置为一个指定值，默认为None，该函数与get()函数功能类似，但是不同的是setdefault() 返回的键如果不在字典中，会添加键(更新字典)，而get()不会添加键。 代码示例 # 数据格式化 # 函数的功能是返回指定键的值，如果键不在字典中，将会添加键并将值设置为一个指定值，默认为None def createInitSet(dataSet): retDict = {} for trans in dataSet: # print("trans=",trans) fset = frozenset(trans) # print("fest=",fset) retDict.setdefault(fset, 0) #返回指定键的值，如果没有则添加一个键 # print("retDict=",retDict) retDict[fset] += 1 print("retDict=",retDict) return retDict createInitSet(data)运行结果 {frozenset({'r', 'h', 'j', 'z', 'p'}): 1, frozenset({'x', 'v', 's', 'z', 'y', 't', 'u', 'w'}): 1, frozenset({'z'}): 1, frozenset({'r', 'x', 's', 'o', 'n'}): 1, frozenset({'r', 'q', 'x', 'z', 'p', 'y', 't'}): 1, frozenset({'q', 'e', 'x', 'z', 'y', 'm', 't', 's'}): 1}b) 更新头指针表 updateHeader()函数的功能是确保节点链接指向树中该元素的每一个实例。从头指针表的nodeLink开始，一直沿着nodeLink知道到达链表末尾。 c) FP树的生长函数 该函数的主要功能是让树生长(这就是FP-growth中growth的来源)。首先测试事务中第一个元素项是不是子节点，如果是子节点，则更新count参数；如果不是子节点，则创建一个新的treeNode作为子节点添加到树中。此时，头指针表也要跟着更新以指向新的节点，这个更新需要调用updateHeader()函数。如果item中不止一个元素项的话，则将剩下的元素项作为参数进行迭代，注意：迭代的时候每次调用会去掉列表中的第一个元素(因为我们在前面判断过了) d) 创建FP树 该函数主要功能是创建FP树，树构建过程中会遍历数据集两次。第一次遍历数据集并统计每个元素项出现的次数。这些信息被存储在头指针表中。接下来扫描头指针表，删掉那些不满足最小支持度minSup的元素项。在头指针表中增加一列，用来存放指向每种类型第一个元素项的指针。然后创建只包含空集合∅的根节点。第二次遍历数据集，此次只考虑频繁项集。对频繁项集进行排序，最后调用updateTree() 让树生长。 完整代码示例 class treeNode: def __init__(self, nameValue, numOccur, parentNode): self.name = nameValue #名字变量 self.count = numOccur #计数变量(频率) self.nodeLink = None #链接相似元素项 self.parent = parentNode #当前父节点 self.children = {} #用于存放子节点 # inc 函数 对count变量增加给定值； def inc(self, numOccur): self.count += numOccur # disp()方法的功能是将树以文本形式显示，主要是方便调试 def disp(self, ind=1): print( ' ' *ind, self.name, ' ', self.count) for child in self.children.values(): child.disp(ind +1) #子节点向右缩减 # # 显示节点 # # #创建一个单节点 # rootNode = treeNode('这是父节点',9,None) # #创建一个子节点 # rootNode.children['这是子节点'] = treeNode('这是子节点',13,None) # #显示节点 # rootNode.disp() # # print("---------------------------------") # # #再增加一个子节点 # rootNode.children['这是另一个子节点'] = treeNode('这是另一个子节点',3,None) # #显示节点 # rootNode.disp() # 创建简单数据集 def loadSimpDat(): 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']] return simpDat # data=loadSimpDat() # print("data=",data) # 数据格式化 # 函数的功能是返回指定键的值，如果键不在字典中，将会添加键并将值设置为一个指定值，默认为None def createInitSet(dataSet): retDict = {} for trans in dataSet: # print("trans=",trans) fset = frozenset(trans) # print("fest=",fset) retDict.setdefault(fset, 0) #返回指定键的值，如果没有则添加一个键 # print("retDict=",retDict) retDict[fset] += 1 # print("retDict=",retDict) return retDict # 更新头指针表 def updateHeader(nodeToTest, targetNode): while (nodeToTest.nodeLink != None): nodeToTest = nodeToTest.nodeLink nodeToTest.nodeLink = targetNode # FP树的生长函数 def updateTree(items, myTree, headerTable, count): if items[0] in myTree.children: myTree.children[items[0]].inc(count) else: myTree.children[items[0]] = treeNode(items[0], count, myTree) if headerTable[items[0]][1] == None: headerTable[items[0]][1] = myTree.children[items[0]] else: updateHeader(headerTable[items[0]][1], myTree.children[items[0]]) if len(items) > 1: updateTree(items[1:], myTree.children[items[0]], headerTable, count) # 创建FP树 def createTree(dataSet, minSup=1): headerTable = {} #第一次遍历数据集， 记录每个数据项的支持度 for trans in dataSet: for item in trans: headerTable[item] = headerTable.get(item, 0) + 1 #根据最小支持度过滤 lessThanMinsup = list(filter(lambda k:headerTable[k] } #用于存放子节点 # inc 函数 对count变量增加给定值； def inc(self, numOccur): self.count += numOccur # disp()方法的功能是将树以文本形式显示，主要是方便调试 def disp(self, ind=1): print( ' ' *ind, self.name, ' ', self.count) for child in self.children.values(): child.disp(ind +1) #子节点向右缩减 # 创建简单数据集 def loadSimpDat(): 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']] return simpDat # 数据格式化 # 函数的功能是返回指定键的值，如果键不在字典中，将会添加键并将值设置为一个指定值，默认为None def createInitSet(dataSet): retDict = {} for trans in dataSet: # print("trans=",trans) fset = frozenset(trans) # print("fest=",fset) retDict.setdefault(fset, 0) #返回指定键的值，如果没有则添加一个键 # print("retDict=",retDict) retDict[fset] += 1 # print("retDict=",retDict) return retDict # 更新头指针表 def updateHeader(nodeToTest, targetNode): while (nodeToTest.nodeLink != None): nodeToTest = nodeToTest.nodeLink nodeToTest.nodeLink = targetNode # FP树的生长函数 def updateTree(items, myTree, headerTable, count): if items[0] in myTree.children: myTree.children[items[0]].inc(count) else: myTree.children[items[0]] = treeNode(items[0], count, myTree) if headerTable[items[0]][1] == None: headerTable[items[0]][1] = myTree.children[items[0]] else: updateHeader(headerTable[items[0]][1], myTree.children[items[0]]) if len(items) > 1: updateTree(items[1:], myTree.children[items[0]], headerTable, count) # 创建FP树 def createTree(dataSet, minSup=1): headerTable = {} #第一次遍历数据集， 记录每个数据项的支持度 for trans in dataSet: for item in trans: headerTable[item] = headerTable.get(item, 0) + 1 #根据最小支持度过滤 lessThanMinsup = list(filter(lambda k:headerTable[k] } treeNode = headerTable[basePat][1] while treeNode != None: prefixPath = [] ascendTree(treeNode, prefixPath) if len(prefixPath) > 1: condPats[frozenset(prefixPath[1:])] = treeNode.count treeNode = treeNode.nodeLink return condPats # 创造条件FP树 def mineTree(inTree, headerTable, minSup=1, preFix=set([]), freqItemList=[]): #排序minSup asc, value asc bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: (p[1][0],p[0]))] for basePat in bigL: newFreqSet = preFix.copy() newFreqSet.add(basePat) freqItemList.append(newFreqSet) # 通过条件模式基找到的频繁项集 condPattBases = findPrefixPath(basePat, headerTable) myCondTree, myHead = createTree(condPattBases, minSup) if myHead != None: print('condPattBases: ', basePat, condPattBases) myCondTree.disp() print('*' * 30) mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList) #测试 simpDat = loadSimpDat() # 读取数据 dictDat = createInitSet(simpDat) # 格式化数据 myFPTree,myheader = createTree(dictDat, 3) #创建FP树 myFPTree.disp() mineTree(myFPTree, myheader, 2)运行结果
[1] 机器学习实战. 人民邮电出版社. [2] https://www.bilibili.com/video/av40754697?t=1758 |
对于百度的研究人员来说，想要给出这些推荐查询的词项，他们需要查看互联网上的用词并快速地找出经常出现在一起的词对，因此他们需要一种更加高效的发现频繁项集的方法。 Apriori算法是一种很好的发现频繁项集的方法，但是每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集，当数据量很大的时候，这毫无疑问会成为Apriori算法最大的缺点：频繁项集发现的速度太慢。FPgrowth算法其实是在Apriori算法基础上进行了优化得到的算法，下面看一下两者的对比：
FP-growth算法只需要对数据库进行了两次扫描，而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁，因此FP-growth算法的速度要比Apriori算法快。在小规模数据集上，这不是什么问题，但是当处理大规模数据集时，就会产生很大的区别。 关于FP-growth算法需要注意的两点是： (1) 该算法采用了与Apriori完全不同的方法来发现频繁项集； (2) 该算法虽然能更为高效地发现频繁项集，但不能用于发现关联规则。
从上图可以看到，经过支持度过滤之后，元素项由原来的17个变为了6个，可以大大减少后续的计算量。
原始事务集支持度过滤及重排序后的结果：
这里需要注意的是：事务集在重排序的时候，我们进行了两步操作： 第一步：按照频率大小对元素项进行排序； 第二步：对于相同频率的元素项，则对关键字进行降序排列(顺序会影响FP的结构)。
把六个事务都添加进去之后，我们的FP树就建立好了。我们可以这棵树跟我们一开始示意的FP树不太一样。原因是：我们对频率相同的元素项进行了关键字排序处理。这说明，对项的关键字排序将会影响FP树的结构。进而，树的结构也将影响后续发现频繁项的结果。
【本文地址】