结论

• 作为一个挖掘频繁项集的算法，Apriori算法需要多次扫描数据，I/O是很大的瓶颈。为了解决这个问题，FP Tree算法（也称FP Growth算法）采用了一些技巧，无论多少数据，只需要扫描两次数据集，因此提高了算法运行的效率.

原理

• 为了减少I/O次数，FP Tree算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分

    ![nDnisu](<https://raw.githubusercontent.com/errolyan/tuchuang/master/uPic/nDnisu.png>)
  

• 步骤

  • 1）扫描数据，得到所有频繁一项集的的计数。然后删除支持度低于阈值的项，将1项频繁集放入项头表，并按照支持度降序排列。
  • 2）扫描数据，将读到的原始数据剔除非频繁1项集，并按照支持度降序排列。
  • 3）读入排序后的数据集，插入FP树，插入时按照排序后的顺序，插入FP树中，排序靠前的节点是祖先节点，而靠后的是子孙节点。如果有共用的祖先，则对应的公用祖先节点计数加1。插入后，如果有新节点出现，则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后，FP树的建立完成。
  • 4）从项头表的底部项依次向上找到项头表项对应的条件模式基。从条件模式基递归挖掘得到项头表项项的频繁项集（可以参见第4节对F的条件模式基的频繁二项集到频繁5五项集的挖掘）。
  • 5）如果不限制频繁项集的项数，则返回步骤4所有的频繁项集，否则只返回满足项数要求的频繁项集。

示例

import pyfpgrowth
transactions=[]

with open("./data/KnowledgeGraph/sample7.txt") as f:
    for line in f:
        line=line.strip('\\\\n')
        ip,ua,target=line.split(',')
        print "Add (%s %s %s)" % (ip,ua,target)
        transactions.append([ip,ua,target])

patterns = pyfpgrowth.find_frequent_patterns(transactions, 3)
rules = pyfpgrowth.generate_association_rules(patterns, 0.9)

print rules