wordpress优秀移动站点,网盟推广有哪些,网站手机端设计,重庆市建设工程信息网查证件在第二次扫描数据集时会构建一棵FP树。为构建一棵树#xff0c;需要一个容器来保存树。
创建FP树的数据结构
FP树要比书中其他树更加复杂#xff0c;因此需要创建一个类来保存树的每一个节点#xff1a;
class treeNode:def __init__(self,nameValue,numOccur,parentNode…在第二次扫描数据集时会构建一棵FP树。为构建一棵树需要一个容器来保存树。
创建FP树的数据结构
FP树要比书中其他树更加复杂因此需要创建一个类来保存树的每一个节点
class treeNode:def __init__(self,nameValue,numOccur,parentNode):self.namenameValueself.countnumOccurself.nodeLinkNoneself.parentparentNodeself.children{}def inc(self,numOccur):self.countself.countnumOccurdef disp(self,ind1):print( *ind,self.name, ,self.count)for child in self.children.values():child.disp(ind1)
上面的程序给出了FP树中节点的类定义。类中包含用于存放节点名字的变量和1个计数值nodeLink变量用于链接相似的元素项。类中还使用了父变量parent来指向当前节点的父节点。通常情况下并不需要这个变量因为通常是从上向下迭代访问节点的。之后还需要根据给定叶子节点上溯整棵树这是就需要指向父节点的指针。最后类中还包括一个空字典变量用于存放节点的子节点。
上述代码还包括两个方法其中inc()对count变量增加给定值另一个方法disp()用于将树以文本形式显示。后者对于树构建来说并不是必要的但它对调试非常有用。
创建一棵树的一个单节点之后为其增加一个子节点
rootNodetreeNode(pyramid,9,None)
rootNode.children[eye]treeNode(eye,13,None)
print(rootNode.disp()) 再添加一个节点看一下两个子节点的展示效果
rootNode.children[phoenix]treeNode(phoenix,3,None)
print(rootNode.disp()) 现在FP树所需的数据结构已经建好之后就可以构建FP树了。
构建FP树
FP树中需要一个头指针来指向给定类型的第一个实例。利用头指针表可以快速访问FP树中一个给定类型的所有元素比如 这里使用一个字典作为数据结构来保存头指针表。除了存放指针外头指针表还可以用来保存FP树中每个元素的总数。
第一次遍历数据集会获得每个元素项的出现频率。接下来去掉不满足最小支持度的元素项。再下一步构建FP树。在构建时读入每个项集并将其添加到一条已经存在的路径中。如果该路径不存在则创建一条新路径。每个事务就是一个无序集合。假设有集合{z,x,y}和{y,z,r}那么在FP树中相同项会只表示一次。为了解决这个问题在将集合添加到树之前需要对每个集合进行排序。排序基于元素项的绝对出现频率来进行。使用上图中的头指针节点值对数据进行过滤、重排序的数据如下 在对事务记录进行过滤和排序之后就可以构建FP树了。从空集开始向其中不断添加频繁项集。过滤、排序后的事务依次添加到树中如果树中已存在现有元素则增加现有元素的值如果现有元素不存在则向树添加一个分枝。
对上表前两条事务进行添加的过程 接下来是代码实现上述过程
def createTree(dataSet,minSup1):headerTable{}for trans in dataSet:for item in trans:headerTable[item]headerTable.get(item,0)dataSet[trans]#移除不满足最小支持度的元素项#print(keys,list(headerTable.keys()))for k in list(headerTable.keys()):if headerTable[k]minSup:del(headerTable[k])freqItemSetset(headerTable.keys())#如果没有元素项满足要求退出返回Noneif len(freqItemSet)0:return None,Nonefor k in headerTable:headerTable[k][headerTable[k],None]retTreetreeNode(Null set,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(),keylambda p:p[1],reverseTrue)]#使用排序后的频率项集对树进行填充updateTree(orderedItems,retTree,headerTable,count)return retTree,headerTabledef updateTree(items,inTree,headerTable,count):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函数updateTree(items[1::],inTree.children[items[0]],headerTable,count)
def updateHeader(nodeToTest,targetNode):while (nodeToTest.nodeLink ! None):nodeToTestnodeToTest.nodeLinknodeToTest.nodeLinktargetNode
上述代码包含3个函数。第一个函数createTree()使用数据集以及最小支持度作为参数构建FP树。树构建过程中会遍历数据集两次。第一次遍历扫描数据集并统计每个元素项出现的频度。所有所有项都不频繁就不需要进行下一步处理。接下来对头指针表稍加扩展以便可以保存计数值及指向每种类型第一个元素项的指针。然后创建只包含空集合的根节点。最后再一次遍历数据集这次只考虑哪些频繁项。这些项已经进行了排序然后调用updateTree()方法。
为了让FP树生长需调用updateTree其中的输入参数为一个项集。该函数首先测试事务中的第一个元素项是否作为子节点存在。如果存在的话则更新该元素项的计数如果不存在则创建一个新的treeNode并将其作为一个子节点添加到树中。这是头指针表也要更新以指向新的节点。更新头指针表需要调用函数updateHeader()。updateTree()完成的最后一件事是不断迭代调用自身每次调用时会去掉列表中第一个元素。
最后一个函数是updateHeader()它确保节点链接指向树中该元素项的每一个实例。从头指针的nodeLink开始一直沿着nodeLink直到到达链表末尾。这就是一个链表。当处理树的时候一种很自然的反应就是迭代完成每一件事。当以相同方式处理链表时可能会遇到一些问题原因是如果链表很长可能会遇到迭代调用的次数限制。
下面创建一个真正的数据集用来运行上面的函数查看运行效果
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
def createInitSet(dataSet):retDict{}for trans in dataSet:retDict[frozenset(trans)]1return retDict
下面实际运行首先导入数据库实例然后对数据进行格式化处理
simpDatloadSimpDat()
print(simpDat) 接下来为了函数createTree需要对上面的数据进行格式化处理
initSetcreateInitSet(simpDat)
print(initSet) 创建FP树
myFPtree,myHeaderTabcreateTree(initSet,3)
print(myFPtree.disp()) 上面给出的是元素项及其对应的频率计数值其中每个缩进表示所处的数的深度。
