基本方法
关联分析的目标包括两项：发现频繁项集和发现关联规则。
首先需要找到频繁相机，然后才能获得关联规则。
关联分析的主要目的是寻找频繁项集，如果通过暴力搜索，运算量会呈几何性增长。为了减少频繁项集的计算量，可以采用Apriori算法和FP-Growth算法。
Apriori算法
原理：如果某个项集是频繁的，那么它的所有子集也是频繁的。这个原理反过来看对实际操作更有作用，即如果一个项集是非频繁项集，那么它的所有超集也是非频繁的。
步骤：
根据数据集生成候选项，首先生成单物品候选项集。设定最小支持度和最小置信度过滤掉数据项集占比低于最小支持度的项，形成频繁项。根据步骤3形成的频繁项集结果，进行项集之间的组合形成新的项集集合。重复步骤3、4.直到没有新的项集满足最小支持度。根据步骤5形成的最终频繁集合，计算频繁集合所含物品之间的置信度，过滤掉小于最小置信度的项集根据步骤6的结果生成关联规则，并计算其置信度。
上述步骤中体现了Apriori算法的两个重要过程：连接步和剪枝步。
连接步的目的是找到K项集，从满足约束条件的1项候选项集，逐步连接并检测约束条件产生高一级候选项集，直到得到最大的频繁项集。
剪枝步是在产生候选项Ck的过程中起到减小搜索空间的目的。
根据Apriori原理，频繁项集的所有非空子集也是频繁的，反之，不满足该性质的项集不会存在与Ck中，因此这个过程称为剪枝。
从单元素项集开始，通过组合满足最小支持度要求的项集来形成更大的集合，每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集。当数据集很大时，会显著降低频繁项集发现的速度。 FP-Growth算法
在Apriori原理的基础上，采用FP树数据结构对原始数据进行压缩，大大加快了计算速度。
FP-Growth算法把数据集中的事务映射到一棵FP-Tree上，再根据这棵树找出频繁项集，FP-Tree的构建过程只需要扫描两次数据集，特别是在大型数据集上具有很高的效率。
步骤：构建FP树和挖掘频繁项集。
算法的瓶颈在FP-Tree的递归挖掘上。
1.FP树的数据结构：上去和其他树结构类似，但是它通过链接来连接相似的元素，被连起来的元素项可以看成一个链表。一个元素项可以在一棵FP树中出现多次。
2.构建FP树： 需扫描两次数据集
第一次扫描用来统计各元素项的出现频率，第二遍扫描只考虑频繁项集。
（1）遍历数据集，统计各元素项出现的次数，创建头指针表。
（2）移除头指针表中不满足最小值尺度的元素项
（3）第二次遍历数据集，创建FP树。对每个数据集中的项集进行如下操作。
① 初始化空FP树
② 对每个项集进行过滤和重排序
③ 使用这个项集更新FP树，从FP树的根节点开始进行
a.如果当前项集的第一个元素存在于FP树当前节点的子节点中，则更新这个子节点的计数值。
b.否则,创建新的子节点,更新头指针表。
c.对当前项集的其余元素项和当前元素项的对应子节点递归③的过程
3.从FP树中挖掘频繁项集
有了FP树之后，就可以抽取频繁项集了。从单元素项集合开始，然后在此基础上逐步构建更大的集合。步骤如下：
（1）从FP树中获得条件模式基
从头指针表中最下面的频繁元素项开始，构造每个元素项的条件模式基。条件模式基是以所查找元素项为结尾的路径集合，这里每一条路径都是该元素项的前缀路径。条件模式基的频繁度为路径上该元素项的频繁度计数。
（2）利用条件模式基，构建一个条件FP树
对于灭一个频繁项，都需要创建一棵条件FP树。使用刚才创建的条件模式基作为输入，累加每个条件模式基上的元素项频繁度，过滤低于阈值的元素项，采用同样的建树代码构建FP树。递归发现频繁项、条件模式基和另外的条件树。
（3）迭代重复步骤（1）和步骤（2），知道树包含一个元素项，这样就获得了所有的频繁项集
以下为FP树的测试代码。
# FP树的数据结构class treeNode: def __init__self, nameValue, numOccur, parentNode): self.name = nameValue self.count = numOccur self.nodeLink = None self.parent = parentNode self.children = {} def incself, numOccur): self.count += numOccur def dispself, ind=1): print’ ‘ * ind, self.name, ‘ ‘, self.count) for child in self.children.values): child.dispind + 1)# 构建FP树def createTreedataSet, minSup=1): headerTable = {} for trans in dataSet: for item in trans: headerTable[item] = headerTable.getitem, 0) + dataSet[trans] for k in listheaderTable): if headerTable[k] < minSup: del headerTable[k]) freqItemSet = setheaderTable.keys)) if lenfreqItemSet) == 0: return None, None for k in headerTable: headerTable[k] = [headerTable[k], None] retTree = treeNode’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 lenlocalD) > 0: orderedItems = [v[0] for v in sortedlocalD.items), key=lambda p: p[1], reverse=True)] updateTreeorderedItems, retTree, headerTable, count) return retTree, headerTabledef updateTreeitems, inTree, headerTable, count): if items[0] in inTree.children: inTree.children[items[0]].inccount) else: inTree.children[items[0]] = treeNodeitems[0], count, inTree) if headerTable[items[0]][1] == None: headerTable[items[0]][1] = inTree.children[items[0]] else: updateHeaderheaderTable[items[0]][1], inTree.children[items[0]]) if lenitems) > 1: updateTreeitems[1::], inTree.children[items[0]], headerTable, count)def updateHeadernodeToTest, targetNode): while nodeToTest.nodeLink != None): nodeToTest = nodeToTest.nodeLink nodeToTest.nodeLink = targetNode# 挖掘频繁项集def ascendTreeleafNode, prefixPath): if leafNode.parent != None: prefixPath.appendleafNode.name) ascendTreeleafNode.parent, prefixPath)def findPrefixPathbasePat, treeNode): condPats = {} while treeNode != None: prefixPath = [] ascendTreetreeNode, prefixPath) if lenprefixPath) > 1: condPats[frozensetprefixPath[1:])] = treeNode.count treeNode = treeNode.nodeLink return condPatsdef mineTreeinTree, headerTable, minSup, preFix, freqItemList): bigL = [v[0] for v in sortedheaderTable.items), key=lambda p: strp[1]))] for basePat in bigL: newFreqSet = preFix.copy) newFreqSet.addbasePat) freqItemList.appendnewFreqSet) condPathBases = findPrefixPathbasePat, headerTable[basePat][1]) myCondTree, myHead = createTreecondPathBases, minSup) if myHead != None: print’conditional tree for:’, newFreqSet) mineTreemyCondTree, myHead, minSup, newFreqSet, freqItemList)# 生成数据集def loadSimpDat): simDat = [ [‘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 simDatdef createInitSetdataSet): retDict = {} for trans in dataSet: retDict[frozensettrans)] = 1 return retDictif __name__ == ‘__main__’: minSup = 3 simDat = loadSimpDat) initSet = createInitSetsimDat) myFPtree, myHeaderTab = createTreeinitSet, minSup) myFPtree.disp) myFreqList = [] mineTreemyFPtree, myHeaderTab, minSup, set[]), myFreqList) printmyFreqList)
两个算法的思路都是采用的枚举式方法，然后通过统计其频率，按照我们的需求返回结果。
这一类算法比较适合用于包含具体的枚举项的场景，例如超市，商场。而如果是其他场景，比如，预测天气，分析影响天气的影响因素，则需采用其他更适合场景的方法了。