【Python算法】关联规则算法——Apriori算法

1.关联规则
　　所谓关联，反映的是一个事件和其他事件之间依赖或关联的知识。当查找某些东西的时候，可以发现有两个或两个以上都有关联的含义。第一个是相关性relevance，第二个是关联性association，两者都可以用来描述事件之间的关联程度。

2.Apriori算法简介
　　Apriori算法是经典的挖掘频繁项集和关联规则的数据挖掘算法。其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集，它使用一种称为逐层搜索的迭代方法，其中k项集用于探索(k+1)项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为L1。然后，使用L1找出频繁2项集的集合L2，使用L2找出L3，如此下去，直到不能再找到频繁 k 项集。每找出一个Lk需要一次数据库的完整扫描。Apriori算法使用频繁项集的先验性质来压缩搜索空间。在Apriori算法中，有以下几个关键概念：
　　(1)项与项集：设itemset={item1, item_2, …, item_m}是所有项的集合，其中，item_k(k=1,2,…,m)成为项。项的集合称为项集（itemset），包含k个项的项集称为k项集(k-itemset)；
　　(2)事务与事务集：一个事务T是一个项集，它是itemset的一个子集，每个事务均与一个唯一标识符Tid相联系。不同的事务一起组成了事务集D，它构成了关联规则发现的事务数据库；
　　(3)关联规则：关联规则是形如A=>B的蕴涵式，其中A、B均为 itemset的子集且均不为空集，而A交B为空；

　　支持度(support)：关联规则的支持度定义如下：

• support(A⇒ B) = P(AUB)

　　其中P(AUB) 表示事务包含集合A和B的并（即包含A和B中的每个项）的概率。注意与P（A or B）的区别，后者表示事务包含A或B的概率。

　　 (1) 置信度（confidence）：关联规则的置信度定义如下：

confidence(A\Rightarrow B)=P(B|A)=\frac {support(A\bigcup B)}{support(A)}=\frac{support \\_count(A\bigcup B)}{support\\_count(A)}

       (2) 项集的出现频度（support count）：包含项集的事务数，简称为项集的频度、支持度计数或计数；
　　(3) 频繁项集（frequent itemset）：如果项集 1 的相对支持度满足事先定义好的最小支持度阈值（即 1 的出现频度大于相应的最小出现频度（支持度计数）阈值），则 1 是频繁项集；
　　(4) 强关联规则：满足最小支持度和最小置信度的关联规则，即待挖掘的关联规则。

3.挖掘项集相关定义
　　连接步骤：
　　频繁（k-1）项集Lk-1的自身连接产生候选 k 项集Ck。
　　Apriori算法假定项集中的项按照字典序排序。如果Lk-1中某两个的元素（项集）itemset1和itemset2的前（k-2）个项是相同的，则称itemset1和itemset2是可连接的。所以 itemset1与itemset2连接产生的结果项集是{itemset1[1], itemset1[2], …, itemset1[k-1], itemset2[k-1]}。连接步骤包含在create_Ck函数中。

　　剪枝策略 :
　　由于存在先验性质：任何非频繁的（k-1）项集都不是频繁k项集的子集。因此，如果一个候选k项集Ck的（k-1）项子集不在Lk-1中，则该候选也不可能是频繁的，从而可以从Ck中删除，获得压缩后的Ck。（is_apriori）函数用于判断是否满足先验性质，（create_Ck）函数中包含剪枝步骤，即若不满足先验性质，剪枝。

　　删除策略 :
　　基于压缩后的Ck，扫描所有事务，对Ck中的每个项进行计数，然后删除不满足最小支持度的项，从而获得频繁k项集。删除策略包含在下文代码中的（generate_Lk_by_Ck）函数中。

　　每个项都是候选1项集的集合C1的成员。算法扫描所有的事务，获得每个项，生成C1。然后对每个项进行计数。然后根据最小支持度从C1中删除不满足的项，从而获得频繁1项集L1。 对L1的自身连接生成的集合执行剪枝策略产生候选2项集的集合C2，然后，扫描所有事务，对C2中每个项进行计数。同样的，根据最小支持度从C2中删除不满足的项，从而获得频繁2项集L2。
　　对L2的自身连接生成的集合执行剪枝策略产生候选3项集的集合C3，然后，扫描所有事务，对C3每个项进行计数。同样的，根据最小支持度从C3 中删除不满足的项，从而获得频繁3项集L3。
　　以此类推，对Lk-1的自身连接生成的集合执行剪枝策略产生候选k项集Ck，然后扫描所有事务，对Ck中的每个项进行计数。然后根据最小支持度从Ck中删除不满足的项，从而获得频繁k项集。

　　由频繁项集产生关联规则一旦找出了频繁项集，就可以直接由它们产生强关联规则。产生步骤如下：对于每个频繁项集itemset，产生itemset的所有非空子集（这些非空子集一定是频繁项集）； 对于 itemset 的每个非空子集 s，如果则输出s ⇒ (l−s) ，其中min_conf是最小置信度阈值。

关联分析

　　关联分析是一种在大规模数据集中寻找有趣关系的任务。 这些关系可以有两种形式:
　　(1) 频繁项集（frequent item sets）: 经常出现在一块的物品的集合。
　　(2) 关联规则（associational rules）: 暗示两种物品之间可能存在很强的关系。

相关术语
　　关联分析（关联规则学习): 从大规模数据集中寻找物品间的隐含关系被称作关联分析(associati analysis) 或者关联规则学习（association rule learning） 。 下面是用一个杂货店 例子来说明这两个概念，如图1所示:

　　频繁项集: {葡萄酒, 尿布, 豆奶} 就是一个频繁项集的例子。

　　关联规则: 尿布 -> 葡萄酒 就是一个关联规则。这意味着如果顾客买了尿布，那么他很可能会买葡萄酒。

　　那么频繁的定义是什么呢？怎么样才算频繁呢？度量它们的方法有很多种，这里我们来简单的介绍下支持度和可信度。

　　支持度: 数据集中包含该项集的记录所占的比例。例如上图中，{豆奶} 的支持度为 4/5。{豆奶, 尿布} 的支持度为 3/5。
可信度: 针对一条诸如 {尿布} -> {葡萄酒} 这样具体的关联规则来定义的。这条规则的 可信度 被定义为 支持度({尿布, 葡萄酒})/支持度({尿布})，从图中可以看出 支持度({尿布, 葡萄酒}) = 3/5，支持度({尿布}) = 4/5，所以 {尿布} -> {葡萄酒} 的可信度 = 3/5 / 4/5 = 3/4 = 0.75。

　　支持度和可信度是用来量化关联分析是否成功的一个方法。 假设想找到支持度大于0.8的所有项集，应该如何去做呢？一个办法是生成一个物品所有可能组合的清单，然后对每一种组合统计它出现的频繁程度，但是当物品成千上万时，上述做法就非常非常慢了。我们需要详细分析下这种情况并讨论下Apriori原理，该原理会减少关联规则学习时所需的计算量。

3.Apriori原理
　　假设我们一共有4个商品: 商品0, 商品1, 商品2, 商品3。 所有可能的情况如图2所示:

　　如果我们计算所有组合的支持度，也需要计算15次。即2^N-1=2^4-1=15。
随着物品的增加，计算的次数呈指数的形式增长 ...
　　为了降低计算次数和时间，研究人员发现了一种所谓的Apriori原理，即某个项集是频繁的，那么它的所有子集也是频繁的。例如，如果{0, 1}是频繁的，那么{0}, {1}也是频繁的。该原理直观上没有什么帮助，但是如果反过来看就有用了，也就是说如果一个项集是非频繁项集，那么它的所有超集也是非频繁项集，如图3所示:

　　在图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}的支持度，因为我们知道这些集合不会满足我们的要求。使用该原理就可以避免项集数目的指数增长，从而在合理的时间内计算出频繁项集。

操作系统
　　操作机： Linux_Ubuntu　
　　操作机默认用户：root

步骤1：Apriori算法分块讲解

　　1.1 首先了解一下算法中导入的模块及其简介。其中，sys是system的缩写，用来获取操作系统和编译器的一些配置，设置及操作。如判断文件和文件夹是否存在，创建文件文件夹，获取系统版本之类的操作。itertools库，迭代器（生成器）在Python中是一种很常用也很好用的数据结构，比起列表(list)来说，迭代器最大的优势就是延迟计算，按需使用，从而提高开发体验和运行效率。collections是集合模块，optparse模块可以用用来定义option参数。

import sys  

from itertools import chain, combinations
from collections import defaultdict
from optparse import OptionParser

　　1.2 主函数的部分，其中定义了三个程序功能选项，-f是使用数据文件，-s用来设置最小支持度(默认是0.15)，-c用来设置最小可信度(默认是0.6)。

if __name__ == "__main__":

    optparser = OptionParser()  #创建一个OptionParser对象
    optparser.add_option('-f', '--inputFile',
                         dest='input',
                         help='filename containing csv',
                         default=None)  #添加待定义命令行参数，及其帮助文档。
    optparser.add_option('-s', '--minSupport',
                         dest='minS',
                         help='minimum support value',
                         default=0.15,
                         type='float') #添加待定义命令行参数，及其帮助文档。
    optparser.add_option('-c', '--minConfidence',
                         dest='minC',
                         help='minimum confidence value',
                         default=0.6,
                         type='float') #添加待定义命令行参数，及其帮助文档。

    (options, args) = optparser.parse_args()  #接收参数

    inFile = None  
    if options.input is None:  #文件内容为空的情况
            inFile = sys.stdin
    elif options.input is not None:  #文件内容不为空的情况
            inFile = dataFromFile(options.input)  #把文件内容读到inFile中
    else:
            print ('No dataset filename specified, system with exit\n')
            sys.exit('System will exit')

    minSupport = options.minS   #设置最小支持度
    minConfidence = options.minC   #设置最小可信度

    items, rules = runApriori(inFile, minSupport, minConfidence)  #运行算法，其中三个参数分别是从文件中读出的数据、最小支持度和最小可信度

    printResults(items, rules)  #调用结果显示函数

步骤1：Apriori算法分块讲解

　　1.1 首先了解一下算法中导入的模块及其简介。其中，sys是system的缩写，用来获取操作系统和编译器的一些配置，设置及操作。如判断文件和文件夹是否存在，创建文件文件夹，获取系统版本之类的操作。itertools库，迭代器（生成器）在Python中是一种很常用也很好用的数据结构，比起列表(list)来说，迭代器最大的优势就是延迟计算，按需使用，从而提高开发体验和运行效率。collections是集合模块，optparse模块可以用用来定义option参数。

import sys  

from itertools import chain, combinations
from collections import defaultdict
from optparse import OptionParser

　　1.2 主函数的部分，其中定义了三个程序功能选项，-f是使用数据文件，-s用来设置最小支持度(默认是0.15)，-c用来设置最小可信度(默认是0.6)。

if __name__ == "__main__":

    optparser = OptionParser()  #创建一个OptionParser对象
    optparser.add_option('-f', '--inputFile',
                         dest='input',
                         help='filename containing csv',
                         default=None)  #添加待定义命令行参数，及其帮助文档。
    optparser.add_option('-s', '--minSupport',
                         dest='minS',
                         help='minimum support value',
                         default=0.15,
                         type='float') #添加待定义命令行参数，及其帮助文档。
    optparser.add_option('-c', '--minConfidence',
                         dest='minC',
                         help='minimum confidence value',
                         default=0.6,
                         type='float') #添加待定义命令行参数，及其帮助文档。

    (options, args) = optparser.parse_args()  #接收参数

    inFile = None  
    if options.input is None:  #文件内容为空的情况
            inFile = sys.stdin
    elif options.input is not None:  #文件内容不为空的情况
            inFile = dataFromFile(options.input)  #把文件内容读到inFile中
    else:
            print ('No dataset filename specified, system with exit\n')
            sys.exit('System will exit')

    minSupport = options.minS   #设置最小支持度
    minConfidence = options.minC   #设置最小可信度

    items, rules = runApriori(inFile, minSupport, minConfidence)  #运行算法，其中三个参数分别是从文件中读出的数据、最小支持度和最小可信度

    printResults(items, rules)  #调用结果显示函数

　　1.3 Apriori函数通过计算频繁项集计算支持度，再通过支持度计算可信度，从而空值阈值。代码如下:

def runApriori(data_iter, minSupport, minConfidence):
    """
    run the apriori algorithm. data_iter is a record iterator
    Return both:
     - items (tuple, support)
     - rules ((pretuple, posttuple), confidence)
    """
    itemSet, transactionList = getItemSetTransactionList(data_iter)   #itemSet是一个集合，用来保存都有哪些商品(集合不会出现重复，所以这里使用集合)，transactionList用来保存商品的组合

    freqSet = defaultdict(int)   #保存出现频率
    largeSet = dict()   #保存所有的商品组合
    # 存储的全局字典(key=n-itemSets,value=support)，满足minSupport

    assocRules = dict()    #存储关联规则的字典
    # Dictionary which stores Association Rules

    oneCSet = returnItemsWithMinSupport(itemSet,
                                        transactionList,
                                        minSupport,
                                        freqSet)  #得到满足最小支持度的集合

    currentLSet = oneCSet
    k = 2
    while(currentLSet != set([])):  #循环用来获得largeSet字典，分别对应商品数量为1-n的商品组合
        largeSet[k-1] = currentLSet
        currentLSet = joinSet(currentLSet, k)
        currentCSet = returnItemsWithMinSupport(currentLSet,
                                                transactionList,
                                                minSupport,
                                                freqSet)
        currentLSet = currentCSet
        k = k + 1

    def getSupport(item):  #计算支持度
            """local function which Returns the support of an item"""
            return float(freqSet[item])/len(transactionList)

    toRetItems = []
    for key, value in largeSet.items():
        toRetItems.extend([(tuple(item), getSupport(item))
                           for item in value])

    toRetRules = []
    for key, value in list(largeSet.items())[1:]:
        for item in value:
            _subsets = map(frozenset, [x for x in subsets(item)])
            for element in _subsets:
                remain = item.difference(element)
                if len(remain) > 0:
                    confidence = getSupport(item)/getSupport(element)
                    if confidence >= minConfidence:
                        toRetRules.append(((tuple(element), tuple(remain)),
                                           confidence))
    return toRetItems, toRetRules