关联规则

Apriori算法

购物篮：

交易号	商品
0	豆奶，莴笋
1	莴笋，尿布，葡萄酒，甜菜
2	豆奶，尿布，葡萄酒，橙汁
3	莴笋，豆奶，尿布，葡萄酒
4	莴笋，豆奶，尿布，橙汁

相关概念

1. 频繁项集：频繁项集是指那些经常出现在一起的商品集合，图中的集合{葡萄酒,尿布,豆奶}就是频繁项集的一个例子。从这个数据集中也可以找到诸如尿布->葡萄酒的关联规则，即如果有人买了尿布，那么他很可能也会买葡萄酒。

2. 支持度：一个项集的支持度（support）被定义数据集中包含该项集的记录所占的比例。如上图中，{豆奶}的支持度为4/5，{豆奶,尿布}的支持度为3/5。支持度是针对项集来说的，因此可以定义一个最小支持度，而只保留满足最小值尺度的项集。

3. 可信度或置信度：可信度或置信度（confidence）是针对关联规则来定义的。规则{尿布}➞{啤酒}的可信度被定义为"支持度({尿布,啤酒})/支持度({尿布})"，由于{尿布,啤酒}的支持度为3/5，尿布的支持度为4/5，所以"尿布➞啤酒"的可信度为3/4。这意味着对于包含"尿布"的所有记录，我们的规则对其中75%的记录都适用。

假设我们有一家经营着4种商品（商品0，商品1，商品2和商品3）的杂货店，所有商品之间所有的可能组合为15种，对于单个项集的支持度，我们可以通过遍历每条记录并检查该记录是否包含该项集来计算。对于包含N中物品的数据集共有2N−1种项集组合，重复上述计算过程是不现实的。所以用Apriori原理来解决。

Apriori原理

Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。更常用的是它的逆否命题，即如果一个项集是非频繁的，那么它的所有超集也是非频繁的。例如：若知道项集{2,3}是非频繁的，那么它的超集{0,2,3}，{1,2,3}，{0,1,2,3}也是非频繁的。

关联分析的目标包括两项：发现频繁项集和发现关联规则。首先需要找到频繁项集，然后才能获得关联规则（计算关联规则的可信度需要用到频繁项集的支持度）。

Apriori算法是发现频繁项集的一种方法。Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个元素的项集列表。接着扫描数据集来查看哪些项集满足最小支持度要求，那些不满足最小支持度的集合会被去掉。然后，对剩下来的集合进行组合以生成包含两个元素的项集。接下来，再重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉。

计算频繁项集及其支持度的代码：

# /usr/bin/env python
# -*- coding:utf-8 -*-

#def loadDataSet():
#    '''
#    假设该小卖部一共有5种商品出售
#    该方法构造了4条交易记录(dataSet)
#    '''
#    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]


def createC1(dataSet):
    '''
    该方法是为了得到元素个数为1的项集，即一项集。
    '''
    C1 = [] #元素个数为1的项集（非频繁项集，因为还没有同最小支持度比较）
    for transaction in dataSet:
        for item in transaction:
            if [item] not in C1:
                C1.append([item])
    C1.sort()
    return map(frozenset, C1) #将C1由Python列表转换为不变集合（frozenset，Python中的数据结构）


def scanD(D, Ck, minSupport):
    '''
    其中D为全部数据集（所有交易记录的集合）。
    Ck为大小为k（包含k个元素）的候选项集，比如包含一个元素，那么Ck就是C1，以此类推。
    minSupport为设定的最小支持度。
    该方法用于筛选出那些大于minsupport的频繁项集
    '''
    ssCnt = {} #存储所有物品随机组合后（1项集，2项集等）并且是交易记录的子集的出现的次数
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                ssCnt[can] = ssCnt.get(can, 0) + 1
    numItems = float(len(D))
    retList = [] #retList为在Ck中找出的频繁项集（支持度大于minSupport的）
    supportData = {} #supportData记录各频繁项集的支持度
    for key in ssCnt:
        if support >= minSupport:
            retList.insert(0, key)
            supportData[key] = support
    return retList, supportData


def aprioriGen(Lk, k):
    '''
    该函数通过频繁项集列表Lk和项集个数k生成候选项集C(k+1)。
    一项集自由组合构成的所有二项集,若两个二项集的第一个元素相等，则生成三项集。
    注意其生成的过程中，首先对每个项集按元素排序，然后每次比较两个项集，
    只有在前k-1项相同时才将这两项合并。这样做是因为函数并非要两两合并各个集合，
    那样生成的集合并非都是k+1项的。
    在限制项数为k+1的前提下，只有在前k-1项相同、最后一项不相同的情况下合并才为所需要的新候选项集。
    '''
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i + 1, lenLk):
            # 前k-2项相同时，将两个集合合并
            L1 = list(Lk[i])[:k-2] #把set变成list，在取分片。比如set([1,3])变成list后为[1,3]
            L2 = list(Lk[j])[:k-2]
            L1.sort()
            L2.sort()
            if L1 == L2:
                retList.append(Lk[i] | Lk[j]) #求集合的并集并添加到retList中
    return retList


def apriori(dataSet,minSupport=0.5):
    '''
    总函数
    '''
    C1 = createC1(dataSet)
    D = map(set, dataSet)
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2], k)
        Lk, supK = scanD(D, Ck, minSupport)
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L,supportData

解决了频繁项集问题，下一步就可以解决相关规则问题。

要找到关联规则，我们首先从一个频繁项集开始。从杂货店的例子可以得到，如果有一个频繁项集{豆奶, 莴苣}，那么就可能有一条关联规则“豆奶➞莴苣”。这意味着如果有人购买了豆奶，那么在统计上他会购买莴苣的概率较大。注意这一条反过来并不总是成立，也就是说，可信度(“豆奶➞莴苣”)并不等于可信度(“莴苣➞豆奶”)。

一条规则P➞H的可信度定义为support(P | H)/support(P)，其中“|”表示P和H的并集。可见可信度的计算是基于项集的支持度的。

如果某条规则并不满足最小可信度要求，那么该规则的所有子集(左边的子集)也不会满足最小可信度要求。

# /usr/bin/env python
# -*- coding:utf-8 -*-
import apriori
def generateRules(L, supportData, minConfident=0.5):
    '''
    这个函数是主函数，调用其他两个函数。其他两个函数是rulesFromConseq()和    calcConf()，分别用于生成候选规则集合以及对规则进行评估（计算支持度）。
    函数generateRules()有3个参数：
    频繁项集列表L、包含那些频繁项集支持数据的字典supportData、最小可信度阈值minConf。
    函数最后要生成一个包含可信度的规则列表bigRuleList，后面可以基于可信度对它们进行排序。
    L和supportData正好为函数apriori()的输出。
    该函数遍历L中的每一个频繁项集，并对每个频繁项集构建只包含单个元素集合的列表H1。
    代码中的i指示当前遍历的频繁项集包含的元素个数，
    freqSet为当前遍历的频繁项集（回忆L的组织结构是先把具有相同元素个数的频繁项集组织成列表，再将各个列表组成一个大列表，所以为遍历L中的频繁项集，需要使用两层for循环）。
    '''
    bigRuleList = []
    for i in range(1, len(L)):
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet] #例如对于freqSet(频繁项集)frozenset([a, b, c, …])，H1的值为[a, b, c, …]（列表中的a,b,c等为frozenset类型）
            rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConfident)
    return bigRuleList



def calcConf(freqSet, H, supportData, brl, minConfident=0.5):
    '''
    对候选规则集进行评估
    计算规则的可信度以及找出满足最小可信度要求的规则。
    函数返回一个满足最小可信度要求的规则列表，并将这个规则列表添加到主函数的bigRuleList中（通过参数brl）。
    返回值prunedH保存规则列表的右部，这个值将在下一个函数rulesFromConseq()中用到。
    '''
    prunedH = []
    for conseq in H:
        conf = supportData[freqSet] / supportData[freqSet - conseq]
        if conf >= minConfident:
            print freqSet - conseq, '-->', conseq, 'conf:', conf
            brl.append((freqSet - conseq, conseq, conf))
            prunedH.append(conseq)
    return prunedH


def rulesFromConseq(freqSet, H, supportData, brl, minConfident=0.5):
    '''
    生成候选规则集,例如{2,3}生成的候选规则有{2}➞{3}、{3}➞{2}。
    根据当前候选规则集H生成下一层候选规则集
    从最初的项集中生成更多的关联规则。
    该函数有两个参数：频繁项集freqSet，可以出现在规则右部的元素列表H。
    其余参数：supportData保存项集的支持度，brl保存生成的关联规则，minConf同主函数。
    函数先计算H中的频繁项集大小m。接下来查看该频繁项集是否大到可以移除大小为m的子集。
    如果可以的话，则将其移除。使用函数aprioriGen()来生成H中元素的无重复组合，结果保存在Hmp1中，这也是下一次迭代的H列表。
    '''
    m = len(H[0])
    while (len(freqSet) > m ): # 判断长度 > m，这时即可求H的可信度
        H = calcConf(freqSet, H, supportData, brl, minConfident)
        if (len(H) > 1): # 判断求完可信度后是否还有可信度大于阈值的项用来生成下一层H
            H = apriori.aprioriGen(H, m + 1)
            m +=1
        else: # 不能继续生成下一层候选关联规则，提前退出循环
            break

END