1.理论背景

        在美国，著名的沃尔玛超市发现啤酒与尿布总是共同出现在购物车中，于是沃尔玛超市经过分析发现许多美国年轻的父亲下班之后经常要去购买婴儿的尿布，而在购买尿布的同时，他们往往会顺手购买一些啤酒；因此沃尔玛超市将啤酒与尿布放在相近的位置，方便顾客购买，并明显提高了销售额。这是频繁模式挖掘的一个经典例子——"啤酒和尿布"。简单来说，频繁模式就是当出现物品A时也经常出现物品B，比如在分析超市的购物清单时，发现买啤酒的人经常也买尿布。

        购物篮分析（或是亲密性分析）是介绍频繁模式挖掘的最佳案例，它是众所周知的频繁模式挖掘应用之一。购物篮分析试图从消费者加入购物篮的商品中挖掘出某种模式或者关联，可以是真实的购物篮，也可以是虚拟的，并且给出支持度或是置信度。这一方法在用户行为分析中存在巨大的价值。将购物篮分析推而广之就成了频繁模式挖掘，实际上它与分类非常类似，只是通过相互的关联来预测属性或是属性的组合（不仅仅是预测类别）。因为关联不需要有标签的数据集，所以它属于无监督式学习。

 2.基本概念

2.1频繁模式定义

        频繁模式指的就是频繁出现在数据集中的模式，比如子序列、项集、子结果。研究频繁模式的目的是得到关联规则和其他的联系，并在实际中应用这些规则和联系。比如，频繁地同时出现在交易数据集中的商品（比如牛奶和面包）的集合是频繁项集；频繁的出现的一个购买顺序（先买笔记本，再买杀毒软件）是频繁子序列。

2.2相关概念定义

       频繁项集一般是指频繁地在事务数据集中一起出现的商品的集合，如小卖部中被许多顾客频繁地一起购买的牛奶和面包。

        频繁子序列，如顾客倾向于先购买便携机，再购买数码相机，然后再购买内存卡这样的模式就是一个(频繁）序列模式。

       频繁子结构是指从图集合中挖掘频繁子图模式。子结构可能涉及不同的结构形式（例如，图、树或格），可以与项集或子序列结合在一起。如果一个子结构频繁地出现，则称它为（频繁）子结构模式。

       关联规则是形如的蕴含式，其中l且，则X称为规则的条件，Y称为规则的结果。如果事务数据库D中有s%的事务包含，则称关联规则的支持度为s%。例如 牛奶=>鸡蛋【支持度=2%，置信度=60%】。关联规则意味着元素项之间“如果…那么…”的关系。

       事务是由一组物品组成，可看作一个订单中的物品集合。
       支持度是某几个物品一起出现在事物中的次数或在数据库中所占的比例。

       置信度是在出现A时出现B的概率，就是P(B|A) = P(A B) / P(A)

       频繁项集是满足最小支持度要求的项集，它给出经常在一起出现的元素项。

       项集表示包含0个或者多个项的集合。如果一个项集包含k个项，则称为k项集 。

       强关联规则表示同时满足最小支持度和最小置信度阈值要求的所有关联规则。

       例如：假设最小置信度阈值为30%，最小置信度阈值为70%，而关联规则：购买面包⇒购买牛奶[支持度=50%，置信度=100%]的支持度和置信度都满足条件，则该规则为强关联规则。 

2.3先验性质

• 关联规则挖掘的任务

        ①根据最小支持度阈值，找出数据集中所有的频繁项集；

        ②挖掘出频繁项集中满足最小支持度和最小置信度阈值要求的规则，得到强关联规则；

        ③对产生的强关联规则进行剪枝，找出有用的关联规则。

• 频繁项集的先验性质

        1.如果某个项集是频繁的，那么它的所有子集也是频繁的。例如如果{B，C}是频繁的，那么{B}，{C}也一定是频繁的。

        2.如果一个项集是非频繁集，那么它的所有超集（包含该非频繁集的父集）也是非频繁的。如果{A, B}是非频繁的，那么{A, B, C}，{A, B, C, D}也一定是频繁的。

2.4 关联规则挖掘的步骤

1. 找出所有频繁项集，即大于或等于最小支持度阈值的项集。
2. 由频繁项集产生强关联规则，这些规则必须大于或等于最小支持度阈值和最小置信度阈值。

3 Apriori算法

3.1算法概述

       Apriori算法是布尔关联规则挖掘频繁项集的原创性算法，该算法使用频繁项集性质的先验知识。Apriori使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描数据库，累积每个项（数据集不重复的元素）的计数，并收集满足最小支持度的项，找出频繁1项集的集合，并将集合记作L1。然后，L1用于找频繁2项集的集合L2，L2用于找L3，如此迭代，直到不能再找到频繁k项集。找每个Lk需要一次数据库全扫描。

3.2实现原理

        算法实现过程分为两步，一步是连接，一步是剪枝。

        输入：项集I，事务数据集D，最小支持度计数阈值Min_sup

        输出：D中的所有频繁项集的集合L。

        实现步骤：

        (1)求频繁1项集L1 首先通过扫描事务数据集D，找出所有1项集并计算其支持度，作为候选1项集C1 然后从C1中删除低于最小支持度阈值Min_sup的项集，得到所有频繁1项集的集合L1 。

        (2）For k=2,3,4，分别得到L2、L3、L4...Lk。

        (3）连接：将Lk-1进行自身连接生成候选k项集的集合Ck，连接方法如下：对于任意p,q∈Lk-1，若按字典序有p={p1,p2,…,pk-2,pk-1}, q={p1,p2,…,pk-2,qk-1},且满足pk-1<qk-1,则把p和q连接成k项集   {p1,p2,…,pk-2,pk-1,qk-1}作为候选k项集Ck中的元素。

        (4）剪枝：删除Ck中的非频繁k项集，即当Ck中一个候选k项集的某个k-1项子集不是Lk-1中的元素时，则将它从Ck中删除。

        (5）计算支持数：通过扫描事务数据集D，计算Ck中每个k项集的支持数。

        (6）求Lk：删除Ck中低于最小支持度阈值Min_sup的k项集，得到所有频繁k项集的集合Lk。         (7）若Lk=Ø，则转第（9）步

        (8）END FOR

         (9）另L=L1∪L2∪…∪Lk，并输出L。

        强关联规则的生成过程包括两个步骤：

        ①对于所有频繁项集的集合L中的每个频繁项集X，生成X所有的非空真子集Y；

        ②对于X中的每一个非空真子集Y，构造关联规则Y⇒(X−Y) 。 构造出关联规则后，计算每一个关联规则的置信度，如果大于最小置信度阈值，则该规则为强关联规则。

 --------------------------------------------------------------------------------------------------------------------------------

         【注意】可以通过枚举频繁项集生成所有的关联规则，并通过计算关联规则的置信度来判断该规则是否为强关联规则。但当一个频繁项集包含的项很多时，就会生成大量的候选关联规则，1个频繁项集X能够生成个（即除去空集及自身之外的子集）候选关联规则。

 3.3案例分析

        假设使用表中的事务数据，该数据库具有9个事务，设最小支持度为2，试使用Apriori算法挖掘表1的事务数据中的频繁项集。

TID	Items
1	面包、可乐、麦片
2	牛奶、可乐
3	牛奶、面包、麦片
4	牛奶、可乐
5	面包、鸡蛋、麦片
6	牛奶、面包、可乐
7	牛奶、面包、鸡蛋、麦片
8	牛奶、面包、可乐
9	面包、可乐

实现过程：

         对于上述例子中L中的频繁3项集{牛奶，面包，麦片}，可以推导出非空子集：

        {{牛奶}，{面包}，{麦片}，{牛奶，面包}，{牛奶，麦片}，{面包，麦片}}。

        可以构造的关联规则及置信度如下：

         {牛奶} ⇒ {面包，麦片}，置信度=2/6=33%

        {面包} ⇒{牛奶，麦片}，置信度=2/7=29%

        {麦片} ⇒ {牛奶，面包}，置信度=2/4=50%

        {牛奶，面包} ⇒ {麦片}，置信度=2/4=50%

        {牛奶，麦片} ⇒ {面包}，置信度=2/2=100%

        {面包，麦片} ⇒ {牛奶}，置信度=2/4=50%

        如果令最小置信度为70%，则得到的强关联规则有：

        {牛奶，麦片} ⇒ {面包}，置信度=2/2=100%

3.4算法特点

3.5算法Python实现

可以通过模块efficient_apriori实现apriori算法，需要另外安装，输入如下命令安装，模块链接

pip install efficient-apriori

• 案例1 

from efficient_apriori import apriori
transactions = [('eggs', 'bacon', 'soup'),
                ('eggs', 'bacon', 'apple'),
                ('soup', 'bacon', 'banana')]
itemsets, rules = apriori(transactions, min_support=0.5, min_confidence=1)
print(rules)  # [{eggs} -> {bacon}, {soup} -> {bacon}]

【注意】在每笔有鸡蛋的交易中，也有培根。 因此，规则 {eggs} -> {bacon} 以 100% 的置信度返回。

• 案例2

from efficient_apriori import apriori
transactions = [('eggs', 'bacon', 'soup'),
                ('eggs', 'bacon', 'apple'),
                ('soup', 'bacon', 'banana')]
itemsets, rules = apriori(transactions, min_support=0.2, min_confidence=1)

# Print out every rule with 2 items on the left hand side,
# 1 item on the right hand side, sorted by lift
rules_rhs = filter(lambda rule: len(rule.lhs) == 2 and len(rule.rhs) == 1, rules)
for rule in sorted(rules_rhs, key=lambda rule: rule.lift):
    print(rule)  # Prints the rule and its confidence, support, lift, ...

可以对返回的关联规则列表进行筛选和排序。

• 案例3

rom efficient_apriori import apriori
transactions = [('eggs', 'bacon', 'soup'),
                ('eggs', 'bacon', 'apple'),
                ('soup', 'bacon', 'banana')]
itemsets, rules = apriori(transactions, output_transaction_ids=True)
print(itemsets)
# {1: {('bacon',): ItemsetCount(itemset_count=3, members={0, 1, 2}), ...

可以自己编写apriori算法实现过程，参考代码如下：

# -*- coding: utf-8 -*-
#加载数据集
def loadDataSet():
    return [[1,3,4],[1,3,5],[2,3,4,5],[3,5],[2,3,5],[1,2,3,5],[2,5]]

#选取数据集的非重复元素组成候选集的集合C1
def createC1(dataSet):
    C1=[]
    for transaction in dataSet: #对数据集中的每条购买记录
        for item in transaction: #对购买记录中的每个元素
            if [item] not in C1: #注意，item外要加上[]，便于与C1中的[item]对比
                C1.append([item])
    C1.sort()
    return list(map(frozenset,C1)) #将C1各元素转换为frozenset格式，注意frozenset作用对象为可迭代对象

#由Ck产生Lk：扫描数据集D，计算候选集Ck各元素在D中的支持度，选取支持度大于设定值的元素进入Lk
def scanD(D,Ck,minSupport):
    ssCnt={}
    for tid in D: #对数据集中的每条购买记录
        for can in Ck: #遍历Ck所有候选集
            if can.issubset(tid): #如果候选集包含在购买记录中，计数+1
                ssCnt[can]=ssCnt.get(can,0)+1
    numItems=float(len(D)) #购买记录数
    retList=[] #用于存放支持度大于设定值的项集
    supportData={} #用于记录各项集对应的支持度
    for key in ssCnt.keys():
        support=ssCnt[key]/numItems
        if support>=minSupport:
            retList.insert(0,key)
        supportData[key]=support
    return retList,supportData

#由Lk产生Ck+1
def aprioriGen(Lk,k): #Lk的k和参数k不是同一个概念，Lk的k比参数k小1
    retList=[]
    lenLk=len(Lk)
    for i in range(lenLk):
        for j in range(i+1,lenLk): #比较Lk中的每一个元素与其他元素
            L1=list(Lk[i])[:k-2];L2=list(Lk[j])[:k-2]
            L1.sort();L2.sort()
            if L1==L2: #若前k-2项相同，则合并这两项
                retList.append(Lk[i]|Lk[j])
    return retList

#Apriori算法主函数
def apriori(dataSet,minSupport=0.5):
    C1=createC1(dataSet)
    D=list(map(set,dataSet))
    L1,supportData=scanD(D,C1,minSupport)
    L=[L1]
    k=2
    while len(L[k-2])>0: #当L[k]为空时，停止迭代
        Ck=aprioriGen(L[k-2],k) #L[k-2]对应的值是Lk-1
        Lk,supK=scanD(D,Ck,minSupport)
        supportData.update(supK)
        L.append(Lk)
        k+=1
    return L,supportData

# 主函数，由频繁项集以及对应的支持度，得到各条规则的置信度，选择置信度满足要求的规则为关联规则
# 为了避免将所有数据都对比一遍，采用与上述相同的逻辑减少计算量——一层一层计算筛选
def generateRules(L,supportData,minConf=0.7):
    bigRuleList=[]
    for i in range(1,len(L)):
        for freqSet in L[i]:
            H1=[frozenset([item]) for item in freqSet] # H1是频繁项集单元素列表，是关联规则中a->b的b项
            if i>1:
                rulesFromConseq(freqSet,H1,supportData,bigRuleList,minConf)
            else:
                calConf(freqSet,H1,supportData,bigRuleList,minConf)
    return bigRuleList

# 置信度计算函数
def calConf(freqSet,H,supportData,brl,minConf=0.7):
    prunedH=[] # 用于存放置信度满足要求的关联规则的b项，即“提纯后的H”
    for conseq in H:
        conf=supportData[freqSet]/supportData[freqSet-conseq]
        if conf>=minConf:
            print (freqSet-conseq,'-->',conseq,'conf:',conf)
            brl.append([freqSet-conseq,conseq,conf])
            prunedH.append(conseq)
    return prunedH

# 关联规则合并函数
def rulesFromConseq(freqSet,H,supportData,brl,minConf=0.7):
    m=len(H[0])
    if len(freqSet)>(m+1): #查看频繁项集freqSet是否大到可以移除大小为m的子集
        Hmp1=aprioriGen(H,m+1) # 从Hm合并Hm+1
        Hmp1=calConf(freqSet,Hmp1,supportData,brl,minConf)
        if len(Hmp1)>1: #若合并后的Hm+1的元素大于1个，则继续合并
            rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf)

dataset=loadDataSet()
C1=createC1(dataset)
D=list(map(set,dataset))
L1,supportData0=scanD(D,C1,0.5)
L,supportData=apriori(dataset,minSupport=0.5)
print(L)

L,supportData=apriori(dataset,minSupport=0.5)
rules=generateRules(L,supportData,minConf=0.5)

4 FP-growth算法

4.1 算法概述

        作为一个挖掘频繁项集的算法，Apriori算法需要多次扫描数据，I/O是很大的瓶颈。FP-growth算法是基于Apriori原理的，通过将数据集存储在FP（Frequent Pattern)树上发现频繁项集，但不能发现数据之间的关联规则。FP树是一种存储数据的树结构，如右图所示，每一路分支表示数据集的一个项集，数字表示该元素在某分支中出现的次数。如下图所示：

于是FP-Growth算法发现频繁项集的过程是：

(1)项头表的建立； 

(2)构建FP树；

(3)从FP树中挖掘频繁项集。

【注意】无论多少数据，只需要扫描两次数据集，因此提高了算法运行的效率。

4.2 算法描述

 4.3实现过程

第1步：项头表的建立。

第2步：FP 树的建立。

        有了项头表和排序后的数据集，就可以开始FP树的建立。      

        开始时FP树没有数据，建立FP树时我们一条条的读入排序后的数据集，插入FP树，插入时按照排序后的顺序，插入FP树中，排序靠前的节点是祖先节点，而靠后的是子孙节点。        

        如果有共用的祖先，则对应的共用祖先节点计数加1。插入后，如果有新节点出现，则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后，FP树的建立完成。

 详细的实现过程如下：

第3步：从FP树里挖掘频繁项集。

        得到了FP树和项头表以及节点链表，我们首先要从项头表的底部项依次向上挖掘。对于项头表对应于FP树的每一项，我们要找到它的条件模式基。所谓条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。得到这个FP子树，我们将子树中每个节点的的计数设置为叶子节点的计数，并删除计数低于支持度的节点。从这个条件模式基，我们就可以递归挖掘得到频繁项集。

 

 

 

 FP-growth算法实现步骤：

 4.4案例分析

        该数据集具有9个事务，设最小支持度为2，频繁项集的极大长度为3。试使用FP-growth算法挖掘表2的事务数据中的频繁项集。

TID	Items
1	面包、可乐、麦片
2	牛奶、可乐
3	牛奶、面包、麦片
4	牛奶、可乐
5	面包、鸡蛋、麦片
6	牛奶、面包、可乐
7	牛奶、面包、鸡蛋、麦片
8	牛奶、面包、可乐
9	面包、可乐

 

 

 

 

4.5算法特点

 4.6 FP-Growth算法Python实现

 根据算法实现步骤，不调用模块实现Fp-growth算法参考代码：

# -*- coding: utf-8 -*-

import operator
class treeNode:
    def __init__(self,nameValue,numOccur,parentNode):
        self.name=nameValue #节点名
        self.count=numOccur #节点元素出现次数
        self.nodeLink=None #存放节点链表中，与该节点相连的下一个元素
        self.parent=parentNode
        self.children={} #用于存放节点的子节点,value为子节点名
    
    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) #对于子节点，深度+1

# 构造FP树
# dataSet为字典类型，表示探索频繁项集的数据集,keys为各项集，values为各项集在数据集中出现的次数
# minSup为最小支持度，构造FP树的第一步是计算数据集各元素的支持度，选择满足最小支持度的元素进入下一步
def createTree(dataSet,minSup=1):
    headerTable={}

    #遍历各项集,统计数据集中各元素的出现次数
    for key in dataSet.keys():
        for item in key:
            headerTable[item]=headerTable.get(item,0)+dataSet[key] 
            
    #遍历各元素，删除不满足最小支持度的元素
    for key in list(headerTable.keys()):
        if headerTable[key]<minSup:
            del headerTable[key]
    freqItemSet=set(headerTable.keys())
    
    #若没有元素满足最小支持度要求，返回None，结束函数
    if len(freqItemSet)==0:
        return None,None
    for key in headerTable.keys():
        headerTable[key]=[headerTable[key],None] #[元素出现次数，**指向每种项集第一个元素项的指针**]
    retTree=treeNode("Null Set",1,None) #初始化FP树的顶端节点
    
    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=operator.itemgetter(1),reverse=True)] #根据元素全局出现次数对每个项集(tranSet)中的元素进行排序
            updateTree(orderedItems,retTree,headerTable,count) #使用排序后的项集对树进行填充
    return retTree,headerTable


#树的更新函数
#items为按出现次数排序后的项集，是待更新到树中的项集；count为items项集在数据集中的出现次数
#inTree为待被更新的树；headTable为头指针表，存放满足最小支持度要求的所有元素
def updateTree(items,inTree,headerTable,count):
    #若项集items当前最频繁的元素在已有树的子节点中，则直接增加树子节点的计数值，增加值为items[0]的出现次数
    if items[0] in inTree.children: 
        inTree.children[items[0]].inc(count)
    else:#若项集items当前最频繁的元素不在已有树的子节点中（即，树分支不存在），则通过treeNode类新增一个子节点
        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]])
    #对于项集items元素个数多于1的情况，对剩下的元素迭代updateTree
    if len(items)>1:
        updateTree(items[1::],inTree.children[items[0]],headerTable,count)


#元素链表更新函数
#nodeToTest为待被更新的元素链表的头部
#targetNode为待加入到元素链表的元素节点
def updateHeader(nodeToTest,targetNode):
    #若待被更新的元素链表当前元素的下一个元素不为空，则一直迭代寻找该元素链表的末位元素
    while nodeToTest.nodeLink!=None: 
        nodeToTest=nodeToTest.nodeLink #类似撸绳子，从首位一个一个逐渐撸到末位
    #找到该元素链表的末尾元素后，在此元素后追加targetNode为该元素链表的新末尾元素
    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 simpDat

#将列表格式的数据集转化为字典格式
def createInitSet(dataSet):
    retDict={}
    for trans in dataSet:
        retDict[frozenset(trans)]=1
    return retDict

#由叶节点回溯该叶节点所在的整条路径
#leafNode为叶节点，treeNode格式；prefixPath为该叶节点的前缀路径集合，列表格式，在调用该函数前注意prefixPath的已有内容
def ascendTree(leafNode,prefixPath):
    if leafNode.parent!=None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent,prefixPath)
        
#获得指定元素的条件模式基
#basePat为指定元素；treeNode为指定元素链表的第一个元素节点，如指定"r"元素，则treeNode为r元素链表的第一个r节点
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树挖掘频繁项集
#inTree: 构建好的整个数据集的FP树
#headerTable: FP树的头指针表
#minSup: 最小支持度，用于构建条件FP树
#preFix: 新增频繁项集的缓存表，set([])格式
#freqItemList: 频繁项集集合，list格式

def mineTree(inTree,headerTable,minSup,preFix,freqItemList):
    #按头指针表中元素出现次数升序排序，即，从头指针表底端开始寻找频繁项集
    bigL=[v[0] for v in sorted(headerTable.items(),key=lambda p:p[1][0])] 
    for basePat in bigL:
        #将当前深度的频繁项追加到已有频繁项集中，然后将此频繁项集追加到频繁项集列表中
        newFreqSet=preFix.copy()
        newFreqSet.add(basePat)
        print("freqItemList add newFreqSet",newFreqSet)
        freqItemList.append(newFreqSet)
        #获取当前频繁项的条件模式基
        condPatBases=findPrefixPath(basePat,headerTable[basePat][1])
        #利用当前频繁项的条件模式基构建条件FP树
        myCondTree,myHead=createTree(condPatBases,minSup)
        #迭代，直到当前频繁项的条件FP树为空
        if myHead!=None:
            mineTree(myCondTree,myHead,minSup,newFreqSet,freqItemList)

simpDat=loadSimpDat()
dataSet=createInitSet(simpDat)
myFPtree1,myHeaderTab1=createTree(dataSet,minSup=3)
myFPtree1.disp(),myHeaderTab1
freqItems=[]
mineTree(myFPtree1,myHeaderTab1,3,set([]),freqItems)
freqItems

 5 压缩频繁项集

 5.1 真超集与真子集

        如果一个集合S2中的每个元素都在集合S1中，且集合S1中可能包含S2中没有的元素，则集合S1就是S2的一个超集，反过来，S2是S1的子集。 S1是S2的超集，若S1中一定有S2中没有的元素，则S1是S2的真超集，反过来S2是S1的真子集。

5.2 频繁闭项集

        如果在数据集中不存在频繁项集X的真超项集Y，使得X、Y的支持度相等，那么称项集X是这个数据集的频繁闭项集。

5.3极大（最大）频繁项集

        如果在数据集中不存在频繁项集X的真超项集Y，使得X属于 Y并且Y也是频繁项集，那么称项集X是这个数据集的极大（最大）频繁项集。

        可以推导出极大频繁项集是闭频繁项集，而闭频繁项集不一定是极大频繁项集。

6关联模式评

6.1支持度与置信度

        支持度用于筛选出频繁项集，但是该度量有一个缺点，一些支持度较低、但让人感兴趣的模式会被忽略掉，模式毕竟是只出现在部分数据中的，因此使用支持度度量可能会出现这种情况。

        置信度用于评估规则的可信程度，但是该度量有一个缺点，没有考虑规则后件的支持度问题。

6.2相关性分析

 

5.3模式评估度量

 

 

【参考资料】

[1]Apriori | 挖掘关联规则

[2]FP-Growth|高效挖掘频繁项集

[3]FP Tree算法原理总结

[4]Apriori算法原理总结

[5]天津大学公开课：数据分析与数据挖掘

注：参考多篇CSDN文章所得

一、实验内容

巩固频繁模式挖掘的基本算法原理及特点，设计程序，基于不同特征的数据集比较不同方法的优缺点，并基于算法原理和特点分析造成这种现象的原因。

二、算法原理

1 Apriori

对于Apriori算法，通过限制候选产生发现频繁项集，使用支持度来作为判断频繁项集的标准。Apriori算法的目标是找到最大的K项频繁集。这里有两层意思，首先，我们要找到符合支持度标准的频繁集。但是这样的频繁集可能有很多。第二层意思就是我们要找到最大个数的频繁集。比如我们找到符合支持度的频繁集AB和ABE，那么我们会抛弃AB，只保留ABE，因为AB是2项频繁集，而ABE是3项频繁集。

Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。

2.FP-growth

FP-growth算法是基于Apriori原理的，通过将数据集存储在FP（Frequent Pattern)树上发现频繁项集，但不能发现数据之间的关联规则。FP-growth是一种以自底向上方式探索树，由FP树产生频繁项集的算法，通过模式增长挖掘频繁模式。给定上面构建的FP树，算法首先查找以e结尾的频繁项集，接下来是b,c,d，最后是a，由于每一个事务都映射到FP树中的一条路径，因为通过仅考察包含特定节点（例如e）的路径，就可以发现以e结尾的频繁项集，使用与节点e相关联的指针，可以快速访问这些路径。

算法发现频繁项集的过程是：(1)构建FP树；(2)从FP树中挖掘频繁项集。

FPGrowth算法的主要思想：1. 构造频繁1项集：遍历初始数据集构造频繁1项集，并作为项头表，建立将指向fpTree节点对应元素的引用 2. 构造FPTree：再次遍历初始数据集，对于每一条事务中的元素，根据频繁1项集中元素的顺序排序， 由此建立FPTree，记录每条事务的节点在同一条路径上出再的节点次数;  3. 逆序遍历在步骤1中构造的项头表，根据其提供的引用指针，找出fpTree中由该节点到根节点的路径， 即生成每个频繁元素的条件模式基 4.根据每个频繁元素对应的条件模式基，生成其对应的条件fpTree，并删除树中节点记数不满足给定的最小支持度的节点  5.对于每一颗条件fpTree，生成所有的从根节点到叶子节点的路径，由路径中的集合生成其所有非空子集 ，所有这些非空子集和每一个频繁1项集中的元素共同构成了原始数据集中的频繁集。

3.Eclat

Eclat算法使用垂直格式挖掘频繁项集。其过程为：（1）通过扫描一次数据集，把水平格式的数据转换成垂直格式；（2）项集的支持度计数简单地等于项集的TID集的长度；（3）从k=1开始，可以根据先验性质，使用频繁k项集来构造候选（k+1）项集；（4）通过取频繁k项集的TID集的交，计算对应的（k+1）项集的TID集。（5）重复该过程，每次k增加1，直到不能再找到频繁项集或候选项集。Eclat算法加入了倒排的思想，具体就是将事务数据中的项作为key，每个项对应的事务ID作为value。只需对数据进行一次扫描，算法的运行效率会很高。

主要步骤：将数据倒排{ item：TID_set }，然后通过求频繁k项集的交集来获取k+1项集。特点：仅需要一次扫描数据库，TID集合很长的话需要消耗大量的内存和计算时间。

4.不同算法的特点

Apriori算法：需要多次扫描数据库，对于大规模数据效率很低。

FPGrowth算法：两次扫描数据库，采用分治的策略有效降低了搜索开销。

Eclat算法：仅需要一次扫描数据库，如果TID集合很长，需要消耗大量的内存和计算时间。

三、算法代码实现

1.Apriori

def init_c1(data_set_dict, min_support):
    c1 = []
    freq_dic = {}
    for trans in data_set_dict:
        for item in trans:
            freq_dic[item] = freq_dic.get(item, 0) + data_set_dict[trans]
    # 优化初始的集合，使不满足最小支持度的直接排除
    c1 = [[k] for (k, v) in freq_dic.iteritems() if v >= min_support]
    c1.sort()
    return map(frozenset, c1)

def scan_data(data_set, ck, min_support, freq_items):
    """
    计算Ck中的项在数据集合中的支持度，剪枝过程
    :param data_set:
    :param ck:
    :param min_support: 最小支持度
    :param freq_items: 存储满足支持度的频繁项集
    :return:
    """
    ss_cnt = {}
    # 每次遍历全体数据集
    for trans in data_set:
        for item in ck:
            # 对每一个候选项集， 检查是否是 term中的一部分（子集），即候选项能否得到支持
            if item.issubset(trans):
                ss_cnt[item] = ss_cnt.get(item, 0) + 1
    ret_list = []
    for key in ss_cnt:
        support = ss_cnt[key]  # 每个项的支持度
        if support >= min_support:
            ret_list.insert(0, key)  # 将满足最小支持度的项存入集合
            freq_items[key] = support  #
    return ret_list


def apriori_gen(lk, k):
    """
    由Lk的频繁项集生成新的候选项集  连接过程
    :param lk:  频繁项集集合
    :param k:  k 表示集合中所含的元素个数
    :return: 候选项集集合
    """
    ret_list = []
    for i in range(len(lk)):
        for j in range(i+1, len(lk)):
            l1 = list(lk[i])[:k-2]
            l2 = list(lk[j])[:k-2]
            l1.sort()
            l2.sort()
            if l1 == l2:
                ret_list.append(lk[i] | lk[j])  # 求并集
    # retList.sort()
    return ret_list

def apriori_zc(data_set, data_set_dict, min_support=5):
    """
    Apriori算法过程
    :param data_set: 数据集
    :param min_support: 最小支持度，默认值 0.5
    :return:
    """
    c1 = init_c1(data_set_dict, min_support)
    data = map(set, data_set)  # 将dataSet集合化，以满足scanD的格式要求
    freq_items = {}
    l1 = scan_data(data, c1, min_support, freq_items)  # 构建初始的频繁项集
    l = [l1]
    # 最初的L1中的每个项集含有一个元素，新生成的项集应该含有2个元素，所以 k=2
    k = 2
    while len(l[k - 2]) > 0:
        ck = apriori_gen(l[k - 2], k)
        lk = scan_data(data, ck, min_support, freq_items)
        l.append(lk)
        k += 1  # 新生成的项集中的元素个数应不断增加
    return freq_items

2.FP-growth

def create_tree(data_set, min_support=1):
    """
    创建FP树
    :param data_set: 数据集
    :param min_support: 最小支持度
    :return:
    """
    freq_items = {}  # 频繁项集
    for trans in data_set:  # 第一次遍历数据集
        for item in trans:
            freq_items[item] = freq_items.get(item, 0) + data_set[trans]

    header_table = {k: v for (k, v) in freq_items.iteritems() if v >= min_support}  # 创建头指针表
    # for key in header_table:
    #     print key, header_table[key]

    # 无频繁项集
    if len(header_table) == 0:
        return None, None
    for k in header_table:
        header_table[k] = [header_table[k], None]  # 添加头指针表指向树中的数据
    # 创建树过程
    ret_tree = treeNode('Null Set', 1, None)  # 根节点

    # 第二次遍历数据集
    for trans, count in data_set.items():
        local_data = {}
        for item in trans:
            if header_table.get(item, 0):
                local_data[item] = header_table[item][0]
        if len(local_data) > 0:
            ##############################################################################################
            # 这里修改机器学习实战中的排序代码：
            ordered_items = [v[0] for v in sorted(local_data.items(), key=lambda kv: (-kv[1], kv[0]))]
            ##############################################################################################
            update_tree(ordered_items, ret_tree, header_table, count)  # populate tree with ordered freq itemset
    return ret_tree, header_table

def update_tree(items, in_tree, header_table, count):
    '''
    :param items: 元素项
    :param in_tree: 检查当前节点
    :param header_table:
    :param count:
    :return:
    '''
    if items[0] in in_tree.children:  # check if ordered_items[0] in ret_tree.children
        in_tree.children[items[0]].increase(count)  # incrament count
    else:  # add items[0] to in_tree.children
        in_tree.children[items[0]] = treeNode(items[0], count, in_tree)
        if header_table[items[0]][1] is None:  # update header table
            header_table[items[0]][1] = in_tree.children[items[0]]
        else:
            update_header(header_table[items[0]][1], in_tree.children[items[0]])
    if len(items) > 1:  # call update_tree() with remaining ordered items
        update_tree(items[1::], in_tree.children[items[0]], header_table, count)

def update_header(node_test, target_node):
    '''
    :param node_test:
    :param target_node:
    :return:
    '''
    while node_test.node_link is not None:  # Do not use recursion to traverse a linked list!
        node_test = node_test.node_link
    node_test.node_link = target_node

def ascend_tree(leaf_node, pre_fix_path):
    '''
    遍历父节点，找到路径
    :param leaf_node:
    :param pre_fix_path:
    :return:
    '''
    if leaf_node.parent is not None:
        pre_fix_path.append(leaf_node.name)
        ascend_tree(leaf_node.parent, pre_fix_path)

def find_pre_fix_path(base_pat, tree_node):
    '''
    创建前缀路径
    :param base_pat: 频繁项
    :param treeNode: FP树中对应的第一个节点
    :return:
    '''
    # 条件模式基
    cond_pats = {}
    while tree_node is not None:
        pre_fix_path = []
        ascend_tree(tree_node, pre_fix_path)
        if len(pre_fix_path) > 1:
            cond_pats[frozenset(pre_fix_path[1:])] = tree_node.count
        tree_node = tree_node.node_link
    return cond_pats

def mine_tree(in_tree, header_table, min_support, pre_fix, freq_items):
    '''
    挖掘频繁项集
    :param in_tree:
    :param header_table:
    :param min_support:
    :param pre_fix:
    :param freq_items:
    :return:
    '''
    # 从小到大排列table中的元素，为遍历寻找频繁集合使用
    bigL = [v[0] for v in sorted(header_table.items(), key=lambda p: p[1])]  # (sort header table)
    for base_pat in bigL:  # start from bottom of header table
        new_freq_set = pre_fix.copy()
        new_freq_set.add(base_pat)
        # print 'finalFrequent Item: ',new_freq_set    #append to set
        if len(new_freq_set) > 0:
            freq_items[frozenset(new_freq_set)] = header_table[base_pat][0]
        cond_patt_bases = find_pre_fix_path(base_pat, header_table[base_pat][1])
        my_cond_tree, my_head = create_tree(cond_patt_bases, min_support)
        # print 'head from conditional tree: ', my_head
        if my_head is not None:  # 3. mine cond. FP-tree
            # print 'conditional tree for: ',new_freq_set
            # my_cond_tree.disp(1)
            mine_tree(my_cond_tree, my_head, min_support, new_freq_set, freq_items)


def fp_growth(data_set, min_support=1):
    my_fp_tree, my_header_tab = create_tree(data_set, min_support)
    # my_fp_tree.disp()
    freq_items = {}
    mine_tree(my_fp_tree, my_header_tab, min_support, set([]), freq_items)
    return freq_items

3.​​​​​Eclat

import sys
import time
type = sys.getfilesystemencoding()


def eclat(prefix, items, min_support, freq_items):
    while items:
        # 初始遍历单个的元素是否是频繁
        key, item = items.pop()
        key_support = len(item)
        if key_support >= min_support:
            # print frozenset(sorted(prefix+[key]))
            freq_items[frozenset(sorted(prefix+[key]))] = key_support
            suffix = []  # 存储当前长度的项集
            for other_key, other_item in items:
                new_item = item & other_item  # 求和其他集合求交集
                if len(new_item) >= min_support:
                    suffix.append((other_key, new_item))
            eclat(prefix+[key], sorted(suffix, key=lambda item: len(item[1]), reverse=True), min_support, freq_items)
    return freq_items


def eclat_zc(data_set, min_support=1):
    """
    Eclat方法
    :param data_set:
    :param min_support:
    :return:
    """
    # 将数据倒排
    data = {}
    trans_num = 0
    for trans in data_set:
        trans_num += 1
        for item in trans:
            if item not in data:
                data[item] = set()
            data[item].add(trans_num)
    freq_items = {}
    freq_items = eclat([], sorted(data.items(), key=lambda item: len(item[1]), reverse=True), min_support, freq_items)
    return freq_items

四、不同规模、最小支持度以及方法对结果的影响及适用性

1.不同规模大小数据对各方法结果影响

1）数据集：unxiData8     规模：900-1500

 

2）数据集：kosarakt    规模：6000-10000

 

结论：一般情况下，数据规模越大，Apriori算法效率越低。因为该算法需要多次扫描数据库，数据量越大，扫描数据库带来的消耗越多。

2.最小支持度大小对各方法结果的影响

1）数据集：unixData8    支持度：4% - 20%

 

2）数据集：kosarakt    支持度：1% - 2%

 

结论：

1）最小支持度越小，各个算法所花费的时间越多,且Apriori算法效率最差；Apriori算法候选项集较多，扫描数据库次数较多;FP-Growth算法FP树较茂盛，求解模式更多;Eclat算法求交集次数较多

2）随着最小支持度的增加，各个算法的效率逐渐接近，相当于数据量较小的情况。

3.不同方法对长事务数据的适用性分析

数据集：movieItem          DataSize = 943

结论：对于长事物的数据集来说

1)最小支持度较大时，生成的FP树深度较大，求解的子问题较多，FP算法性能显著下降，适用性降低；

2)最小支持度较小时，Apriori算法生成大量候选项，扫描数据库次数显著增加，Apriori算法性能显著下降，适用性降低

 

五、实验总结及结果讨论分析

1、Apriori算法的效率最低，因为其需要很多次的扫描数据库；

2、FP—Growth算法在长事物数据上表现很差，因为当事物很长时，树的深度也很大，需要求解的子问题就变得特别多，因此效率会迅速下降；

3、Eclat算法的效率最高，但是由于我们事先使用了递归的思想，当数据量很大的时候会给系统带来巨大的负担，因此不适合数据量很大的情况

 

目录

算法简介

算法逻辑

案例

Spark程序实现例子（Java语言）

---

 

算法简介

FP-Growth是频繁模式挖掘的一种算法，由韩家炜等在2000年提出，算法通过建立一棵频繁项集树来实现频繁项集的搜索，同时能实现事务的压缩，相比Apriori能减少数据的扫描次数。

算法逻辑

1、扫描数据，统计项目（item）在数据集中出现的频数，例如苹果出现（被购买）了4次、牛奶出现（被购买）了5次等

2、再次扫描数据，构建频繁树（FP-Tree），并生成头表。将每条事物中的项目按照步骤1中的频数由高到底排列后，依次放到树中，并用头表记录每个项目在树中的位置

3、依据头表和支持度，在频繁树种搜索频繁项集

案例

数据：

交易ID（TID）	item(项)
1	苹果,牛奶,香蕉
2	苹果,烤串
3	牛奶,香蕉,啤酒
4	牛奶,啤酒
5	香蕉,啤酒,尿布
6	香蕉
7	苹果,牛奶,香蕉,啤酒,尿布,烤串
8	香蕉
9	牛奶
10	啤酒

1、扫描数据，统计项目的频数，按照频数由大到小排序结果如下：

item(项)	频数
香蕉	6
牛奶	5
啤酒	5
苹果	3
烤串	2
尿布	2

2、再次扫描数据，构建频繁树（FP-Tree），并生成头表。构建FP-Tree时首先建立根节点root（或者叫NULL），根节点不保存数据

TID=1：苹果,牛奶,香蕉

根据频数对事务中的项目进行排序，得到：香蕉,牛奶,苹果

根据排序后的事务创建FP-Tree：根据频数倒序生成，香蕉紧跟在root节点后面，然后是牛奶在香蕉后面，苹果在牛奶后面，并在节点上记录项目的频数，生成头表指向各节点，如下图：

TID=2：苹果,烤串

根据频数对事务种项目进行排序，得到：苹果,烤串

插入到FP-Tree中，因root节点只有一个香蕉节点，没有苹果节点，因此root下面新增一个苹果节点；苹果节点之间增加指针，增加烤串指针

TID=3：牛奶,香蕉,啤酒

根据频数对事务种项目进行排序，得到：香蕉，牛奶，啤酒

插入到FP-Tree中，相同节点上的频数相加，如下图黑色文字部分

TID=4：牛奶,啤酒

根据频数对事务种项目进行排序，得到：牛奶,啤酒

插入到FP-Tree中，从root节点下面新增“牛奶”节点，建立啤酒之间的指针，如下图黑色文字部分

 

TID=5：香蕉,啤酒,尿布

根据频数对事务种项目进行排序，得到：香蕉,啤酒,尿布

插入到FP-Tree中，如下图黑色文字部分

TID=6：香蕉

插入到FP-Tree中，香蕉节点的频数由3增加到4，如下图黑色文字部分

TID=7：苹果,牛奶,香蕉,啤酒,尿布,烤串

根据频数对事务种项目进行排序，得到：香蕉,牛奶,啤酒,苹果,烤串,尿布

插入到FP-Tree中，如下图黑色文字部分

 

TID=8：香蕉

插入到FP-Tree中，如下图黑色文字部分

 

TID=9：牛奶

插入到FP-Tree中，如下图黑色文字部分

TID=10：啤酒

插入到FP-Tree中，如下图黑色文字部分。完整的FP-Tree如下图，从root开始生长的一棵频繁树，除root节点外，每个节点存储一个item（项目），以及item（项目）在事务数据中的频数，以及指向相同项目其他节点的指针；还有一张存储节点指针的头表。

3、挖掘频繁模式

从头表底部开始，由下到上挖掘频繁模式，最底部是尿布，在频繁树中，有两条路径：（香蕉6-牛奶3-啤酒2-苹果1-烤串1-尿布1）、（香蕉6-啤酒1-尿布1）；

假如最小支持度设为2，即项目或项目组合大于等于2才算是频繁项，则以上两条路径被裁剪为（香蕉6-啤酒2-尿布1）、（香蕉6-啤酒1-尿布1）。苹果、烤串和尿布组合的数量只有1 ，不满足最小支持度，因此被裁剪掉；建立如下子树：

根据子树，得到频繁项集：以“尿布”结尾的频繁项集有：（尿布）（尿布，啤酒）（尿布，香蕉）（尿布，啤酒，香蕉）

然后根据指针的头表，继续向上挖掘以“烤串”、“苹果”，“啤酒”，“牛奶”，“香蕉”结尾的频繁项集
 

 

Spark程序实现例子（Java语言）

Spark中实现了FP-Growth算法，官方例子点这里，下面是代码

public class JavaFPGrowthExample {
  public static void main(String[] args) {
    //创建SparkSession
    SparkSession spark = SparkSession
      .builder()
      .appName("JavaFPGrowthExample")
      .master("local")
      .getOrCreate();

    // 创建List数据
    List<Row> data = Arrays.asList(
      RowFactory.create(Arrays.asList("1 2 5".split(" "))),
      RowFactory.create(Arrays.asList("1 2 3 5".split(" "))),
      RowFactory.create(Arrays.asList("1 2".split(" ")))
    );
    StructType schema = new StructType(new StructField[]{ new StructField(
      "items", new ArrayType(DataTypes.StringType, true), false, Metadata.empty())
    });
    // 创建DataFrame
    Dataset<Row> itemsDF = spark.createDataFrame(data, schema);
    // 显示原始数据
    System.out.println("原始数据在同一列里面，这是Spark的规则，数据框如下：");
    itemsDF.show(false);

    // 创建FPGrowth实例
    FPGrowthModel model = new FPGrowth()
      .setItemsCol("items") // 设置输入列，交易数据需要进行拆分后，将项目（item）数据放在同一列中，这是Spark的要求
      .setMinSupport(0.5) // 设置最小支撑度
      .setMinConfidence(0.6) // 设置最小置信度
      .fit(itemsDF);  // 拟合数据，返回一个FPGrowthModel

    // 展示频繁项
    System.out.println("频繁项集如下，第一列是项集组合，第二列是频数：");
    model.freqItemsets().show();

    // 生成关联规则
    System.out.println("关联规则如下，第一列是前项，第二列是后项，第三列是置信度");
    model.associationRules().show();

    //
    System.out.println("得到模型后，可以调用模型的transform方法，对数据集进行预测，得到规则。第一列是项集，第二列是推出的结果");
    model.transform(itemsDF).show();
    System.out.println("例如：1、2组合能够推出5");
    // $example off$

    spark.stop();
  }
}

执行代码后得到以下结果

 

原始数据在同一列里面，这是Spark的规则，数据框如下：
+------------+
|items       |
+------------+
|[1, 2, 5]   |
|[1, 2, 3, 5]|
|[1, 2]      |
+------------+

2021-03-02 17:16:57 WARN [org.apache.spark.mllib.fpm.FPGrowth] - Input data is not cached.
频繁项集如下，第一列是项集组合，第二列是频数：
+---------+----+
|    items|freq|
+---------+----+
|      [5]|   2|
|   [5, 1]|   2|
|[5, 1, 2]|   2|
|   [5, 2]|   2|
|      [1]|   3|
|   [1, 2]|   3|
|      [2]|   3|
+---------+----+

关联规则如下，第一列是前项，第二列是后项，第三列是置信度
+----------+----------+------------------+
|antecedent|consequent|        confidence|
+----------+----------+------------------+
|    [1, 2]|       [5]|0.6666666666666666|
|    [5, 1]|       [2]|               1.0|
|       [2]|       [5]|0.6666666666666666|
|       [2]|       [1]|               1.0|
|       [5]|       [1]|               1.0|
|       [5]|       [2]|               1.0|
|       [1]|       [5]|0.6666666666666666|
|       [1]|       [2]|               1.0|
|    [5, 2]|       [1]|               1.0|
+----------+----------+------------------+

得到模型后，可以调用模型的transform方法，对数据集进行预测，得到规则。第一列是项集，第二列是推出的结果
+------------+----------+
|       items|prediction|
+------------+----------+
|   [1, 2, 5]|        []|
|[1, 2, 3, 5]|        []|
|      [1, 2]|       [5]|
+------------+----------+

例如：1、2组合能够推出5