机器学习算法学习---关联分析算法（二）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了机器学习算法学习---关联分析算法（二），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4539字，纯文字阅读大概需要7分钟。

内容图文

FP-growth算法只需要对数据库进行两次扫描，故速度要比Apriori算法快。

发现频繁项集的基本过程：（1）构建FP树；（2）从FP树中挖掘频繁项集。

优点：一般要快于Apriori

缺点：实现比较困难，在某些数据集上性能会下降

适用数据：标称型

1、FP树：用于编码数据集的有效方式

FP代表频繁模式（Frequent Pattern）。FP树看上去与其他树类似，但是它通过链接来连接相似元素，被连起来的元素项可以看成一个链表。一个元素项可以在一棵FP树中出现多次；FP树会存储项集的出现频率，而每个项集会以路径的方式存储在树中。存在相似元素的集合会共享树的一部分；只有当集合之间完全不同时，树才会分叉。树节点上给出集合中的单个元素及其在序列中的出现次数，路径会给出该序列的出现次数。

相似项之间的链接即节点链接，用于快速发现相似项的位置。

算法流程：首先构建FP树，然后利用它来挖掘频繁项集。

构建FP树需要对原始数据集扫描两遍：第一遍对所有元素项的出现次数进行计数，根据Apriori原理，排除非频繁元素项；第二遍只考虑频繁元素构建树。

2、构建FP树

（1）创建存储其的数据结构

利用python类进行定义，具体定义如下：

 

FP树的定义

class treeNode: def __init__(self, nameValue,numOccur,parentNode): self.name = nameValue self.count = numOccur self.nodeLink = None self.parent = parentNode 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)

 

（2）构建

除了FP树，还需一个头指针表来指向给定类型的第一个实例。

可以使用字典保存头指针表。除了存放指针，头指针表还可以用来保存FP树中每类元素的总数。

为了使相同项不会重复出现在树中，在将集合添加到树之前，需要对每个集合进行排序。排序基于元素项的绝对出现频率来进行。

基本思想：从空集开始，向其中不断添加频繁项集；过滤、排序后的事物依次添加到树中，如果树中已存在现有元素，则增加现有元素的值；如果现有元素不存在，则向树添加一个分枝。

python实现如下：

 

构建

def createTree(dataSet,minSup=1): headerTable={} for trans in dataSet: for item in trans: headerTable[item] = headerTable.get(item,0) + dataSet[trans] for k in headerTable.keys(): if headerTable[k]<minSup: del headerTable[k] freqItemSet = set(headerTable.keys()) if len(freqItemSet)==0: return None,None for k in headerTable: headerTable[k] = [headerTable[k],None] retTree = treeNode('NullSet',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: orderedItems = [v[0] for v in sorted(localD.items(),key=lambda p:p[1],reverse=True)] updateTree(orderedItems,retTree,headerTable,count) return retTree,headerTabledef updateTree(items,inTree,headerTable,count):#更新FP树 if items[0] in inTree.children: inTree.children[items[0]].inc(count) else: 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#简单数据集及数据包装器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 simpDatdef createInitSet(dataSet): retDict={} for trans in dataSet: retDict[frozenset(trans)] = 1 return retDict

 

3、从一棵FP树中挖掘频繁项集

基本步骤：

（1）从FP树中获得条件模式基；

（2）利用条件模式基，构建一个条件FP树；

（3）迭代重复步骤（1）（2），直到树包含一个元素项为止。

1）抽取条件模式基

条件模式基：以查找元素为结尾的路径集合。（均为前缀路径：介于所查找元素项与树根结点之间的所有内容）

每一条前缀路径都与一个计数值关联。该计数值等与起始元素项的计数值。

python实现如下：

 

发现以给定元素项结尾的所有路径的函数

def ascendTree(leafNode,prefixPath): if leafNode.parent !=None: prefixPath.append(leafNode.name) ascendTree(leafNode.parent,prefixPath)def findPrefixPath(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

 

2）创建条件FP树

python实现如下：

 

递归查找频繁项集

def mineTree(inTree,headerTable,minSup,preFix,freqItemList): bigL = [v[0] for v in sorted(headerTable.items(),key=lambda p:p[1])] for basePat in bigL: newFreqSet = preFix.copy() newFreqSet.add(basePat) freqItemList.append(newFreqSet) condPattBases = findPrefixPath(basePat.headerTable[basePat][1]) myCondTree,myHead = createTree(condPattBases,minSup) if myHead != None: mineTree(myCondTree,myHead,minSup,newFreqSet,freqItemList)

?

 

内容总结

以上是互联网集市为您收集整理的机器学习算法学习---关联分析算法（二）全部内容，希望文章能够帮你解决机器学习算法学习---关联分析算法（二）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---