这里使用Python字典作为数据结构，来保存头指针表。以元素项名称为键，保存出现的总次数和一个指向第一个相似元素项的指针。
3.2 对每个项集进行过滤和重排序2、剪枝：（去掉非频繁项集）
x {z}: 3, {}: 1简单关联规则是无指导的学习方法，着重探索内部结构。简单关联规则也是使用最多的技术，主要算法包括：Apriori、GRI、Carma，其中Apriori和Carma主要是如何提高关联规则的分析效率，而GRI注重如何将单一概念层次的关联推广到更多概念层次的关联，进而揭示事物内在结构。
下图给出了FP树的一个例子。
项集置信度：数据集中同时包含A、B的百分比
(3)：从新闻网站点击流中挖掘新闻流行趋势，挖掘哪些新闻广泛被用户浏览到
当购买一款新手机后，就会考虑去购买手机膜等手机配件，这就是一种序列关系，不会先买手机膜再买手机的，先后关系是非常明显的，这种关系是一种顺序性的关系，也就是一种序列关联关系。
频繁项 前缀路径有了FP树和条件FP树，我们就可以在前两步的基础上递归得查找频繁项集。
第一次遍历数据集会获得每个元素项的出现频率，去掉不满足最小支持度的元素项，生成这个头指针表。
和之前一样，我们取一个最小阈值，出现次数低于最小阈值的元素项将被直接忽略。图中将最小支持度设为3，所以q和p没有在FP中出现。
上文提到过，FP树会合并相同的频繁项集（或相同的部分）。因此为判断两个项集的相似程度需要对项集中的元素进行排序（不过原因也不仅如此，还有其它好处）。排序基于元素项的绝对出现频率（总的出现次数）来进行。在第二次遍历数据集时，会读入每个项集（读取），去掉不满足最小支持度的元素项（过滤），然后对元素进行排序（重排序）。
简单关联规则算法算法思想基础
2、发现关联规则，即计算不小于人为设定的最小支持度的集合的置信度，找到不小于认为设定的最小置信度规则。
递归查找频繁项集
关联分析步骤1、发现频繁项集，即计算所有可能组合数的支持度，找出不少于人为设定的最小支持度的集合。
优缺点：
频繁项集（Frequent Item Sets）：经常出现在一块的物品的集合，即包含0个或者多个项的集合称为项集。
生成的FP树为
与搜索树不同的是，一个元素项可以在一棵FP树种出现多次。FP树会存储项集的出现频率，而每个项集会以路径的方式存储在数中。 树节点上给出集合中的单个元素及其在序列中的出现次数，路径会给出该序列的出现次数。
3.2 将newFreqSet添加到freqItemList中利用已经找到的k个项的频繁项集Lk，通过两两连接得出候选集Ck+1，注意进行连接的Lk[i]，Lk[j]，必须有k-1个属性值相同，然后另外两个不同的分别分布在Lk[i]，Lk[j]，这样的求出的Ck+1为Lk+1的候选集。
(2)：在Twitter源中发现一些公共词。对于给定的搜索词，发现推文中频繁出现的单词集合
3.3.2 否则，创建新的子节点，更新头指针表对FP树的解读：
算法实现
3.3.1 如果当前项集的第一个元素项存在于FP树当前节点的子节点中，则更新这个子节点的计数值（1）如果支持度和置信度闭值设置的过高，虽然可以减少挖掘时间，但是容易造成一些隐含在数据中非频繁特征项被忽略掉，难以发现足够有用的规则；
构建FP树
# FP树类 class treeNode: def __init__(self, nameValue, numOccur, parentNode): self.name = nameValue #节点元素名称，在构造时初始化为给定值 self.count = numOccur # 出现次数，在构造时初始化为给定值 self.nodeLink = None # 指向下一个相似节点的指针，默认为None self.parent = parentNode # 指向父节点的指针，在构造时初始化为给定值 self.children = {} # 指向子节点的字典，以子节点的元素名称为键，指向子节点的指针为值，初始化为空字典 # 增加节点的出现次数值 def inc(self, numOccur): self.count += numOccur # 输出节点和子节点的FP树结构 def disp(self, ind=1): print(' ' * ind, self.name, ' ', self.count) for child in self.children.values(): child.disp(ind + 1) # =======================================================构建FP树================================================== # 对不是第一个出现的节点，更新头指针块。就是添加到相似元素链表的尾部 def updateHeader(nodeToTest, targetNode): while (nodeToTest.nodeLink != None): nodeToTest = nodeToTest.nodeLink nodeToTest.nodeLink = targetNode # 根据一个排序过滤后的频繁项更新FP树 def updateTree(items, inTree, headerTable, count): if items[0] in inTree.children: # 有该元素项时计数值+1 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) # 主程序。创建FP树。dataSet为事务集，为一个字典，键为每个事物，值为该事物出现的次数。minSup为最低支持度 def createTree(dataSet, minSup=1): # 第一次遍历数据集，创建头指针表 headerTable = {} for trans in dataSet: for item in trans: headerTable[item] = headerTable.get(item, 0) + dataSet[trans] # 移除不满足最小支持度的元素项 keys = list(headerTable.keys()) # 因为字典要求在迭代中不能修改，所以转化为列表 for k in 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('Null Set', 1, None) # 根节点 # 第二次遍历数据集，创建FP树 for tranSet, count in dataSet.items(): localD = {} # 记录频繁1项集的全局频率，用于排序 for item in tranSet: if item in freqItemSet: # 只考虑频繁项 localD[item] = headerTable[item][0] # 注意这个[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) # 更新FP树 return retTree, headerTable # =================================================查找元素条件模式基=============================================== # 直接修改prefixPath的值，将当前节点leafNode添加到prefixPath的末尾，然后递归添加其父节点。 # prefixPath就是一条从treeNode（包括treeNode）到根节点（不包括根节点）的路径 def ascendTree(leafNode, prefixPath): if leafNode.parent != None: prefixPath.append(leafNode.name) ascendTree(leafNode.parent, prefixPath) # 为给定元素项生成一个条件模式基（前缀路径）。basePet表示输入的频繁项，treeNode为当前FP树中对应的第一个节点 # 函数返回值即为条件模式基condPats，用一个字典表示，键为前缀路径，值为计数值。 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 # =================================================递归查找频繁项集=============================================== # 根据事务集获取FP数和频繁项。 # 遍历频繁项，生成每个频繁项的条件FP树和条件FP树的频繁项 # 这样每个频繁项与他条件FP数的频繁项都构成了频繁项集 # inTree和headerTable是由createTree()函数生成的事务集的FP树。 # minSup表示最小支持度。 # preFix请传入一个空集合（set([])），将在函数中用于保存当前前缀。 # freqItemList请传入一个空列表（[]），将用来储存生成的频繁项集。 def mineTree(inTree, headerTable, minSup, preFix, freqItemList): # 对频繁项按出现的数量进行排序进行排序 sorted_headerTable = sorted(headerTable.items(), key=lambda p: p[1][0]) #返回重新排序的列表。每个元素是一个元组，[（key,[num,treeNode],()） bigL = [v[0] for v in sorted_headerTable] # 获取频繁项 for basePat in bigL: newFreqSet = preFix.copy() # 新的频繁项集 newFreqSet.add(basePat) # 当前前缀添加一个新元素 freqItemList.append(newFreqSet) # 所有的频繁项集列表 condPattBases = findPrefixPath(basePat, headerTable[basePat][1]) # 获取条件模式基。就是basePat元素的所有前缀路径。它像一个新的事务集 myCondTree, myHead = createTree(condPattBases, minSup) # 创建条件FP数 if myHead != None: # 用于测试 print('conditional tree for:', newFreqSet) myCondTree.disp() mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList) # 递归直到不再有元素 # 生成数据集 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)] = 1 return retDict if __name__=='__main__': minSup =3 simpDat = loadSimpDat() # 加载数据集 initSet = createInitSet(simpDat) # 转化为符合格式的事务集 myFPtree, myHeaderTab = createTree(initSet, minSup) # 形成FP树 # myFPtree.disp() # 打印树 freqItems = [] # 用于存储频繁项集 mineTree(myFPtree, myHeaderTab, minSup, set([]), freqItems) # 获取频繁项集 print(freqItems) # 打印频繁项集FP-growth算法总结
其中“条件模式基”是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径（prefix path）。简而言之，一条前缀路径是介于所查找元素项与树根节点之间的所有内容。
（2）如果支持度和置信度闭值设置的过低，又有可能产生过多的规则，甚至产生大量冗余和无效的规则，同时由于算法存在的固有问题，会导致高负荷的计算量，大大增加挖掘时间。
从一棵FP树种挖掘频繁项集
FP-growth算法还需要一个称为头指针表的数据结构，其实很简单，就是用来记录各个元素项的总出现次数的数组，再附带一个指针指向FP树中该元素项的第一个节点。这样每个元素项都构成一条单链表。图示说明：
Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个元素的项集列表。接着扫描数据集来查看哪些项集满足最小支持度要求，那些不满足最小支持度的集合会被去掉。然后，对剩下来的集合进行组合以生成包含两个元素的项集。接下来，再重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉。
z {}: 5(4)：搜索引擎推荐，在用户输入查询时推荐同时相关的查询词项
简单关联关系可以从经典的购物中进行分析，购买面包的顾客80%都会购买牛奶，由于面包和牛奶是早餐搭配的必需品，二者搭配构成了早餐的组成部分，这就是一种简单的关联关系。
3. 对headerTable中的每个元素basePat（按计数值由小到大），递归：递归的过程是这样的：
元素项排序
适用数据类型：离散型数据。
eg: confidence(A->B) = support_count(A∪B) / support_count(A)
1. 初始化一个空列表preFix表示前缀对于单个项集的支持度，我们可以通过遍历每条记录并检查该记录是否包含该项集来计算。对于包含N中物品的数据集共有2N−1种项集组合，重复上述计算过程是不现实的。
Apriori算法是发现频繁项集的一种方法。
实现流程
(6)：图书馆信息的书籍推荐，对于学生的借书信息，不同专业学生的借书情况，来挖掘不同学生的借书情况，进行数目的推荐。
3.1 初始化空FP树发现规律了吗，z存在于路径{z}中，因此前缀路径为空，另添加一项该路径中z节点的计数值5构成其条件模式基；r存在于路径{r, z}、{r, y, x, z}、{r, s, x}中，分别获得前缀路径{z}、{y, x, z}、{s, x}，另添加对应路径中r节点的计数值（均为1）构成r的条件模式基；以此类推。
序列关联规则算法序列关联规则的核心就是找到事物发展的前后关联性，研究序列关联可以来推测事物未来的发展情况，并根据预测的发展情况进行事物的分配和安排。
y {z, x}: 3利用条件模式基，构建一个条件FP树；
r {x, s}: 1, {z, x, y}: 1, {z}: 1项集支持度：一个项集出现的次数与数据集所有事物数的百分比称为项集的支持度
关联分析（Association Analysis）：在大规模数据集中寻找有趣的关系。
在图3中，已知阴影项集{2,3}是非频繁的。利用这个知识，我们就知道项集{0,2,3}，{1,2,3}以及{0,1,2,3}也是非频繁的。也就是说，一旦计算出了{2,3}的支持度，知道它是非频繁的后，就可以紧接着排除{0,2,3}、{1,2,3}和{0,1,2,3}。
002 z, y, x, w, v, u, t, s创建条件FP树
支持度反映了A和B同时出现的概率，关联规则的支持度等于频繁集的支持度。
Apriori算法假设我们有一家经营着4种商品（商品0，商品1，商品2和商品3）的杂货店，2图显示了所有商品之间所有的可能组合：
免责声明：凡本网注明 “来源：XXX(非中国房产新闻网)” 的作品，均转载自其它媒体，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。
分享到：
