Apriori Algorithm

在大规模数据集中寻找关系：

  • 频繁项集：经常出现在一块的物品的集合
  • 关联规则：暗示两种物品之间可能存在很强的关系

如何定量地定义关系？如何定义频繁？

以啤酒，尿布的故事为例，

  • 支持度：数据集中包含该项集的记录所占的比例。比如一共有5条交易记录，其中4条出现了{尿布}，则尿布的支持度就为4/5。再比如，如果数据集中有3条同时出现了{尿布，啤酒}，则项集{尿布，啤酒}的支持度就为3/5。

  • 置信度：针对关联规则定义。我们现在知道了{尿布}的支持度为4/5，{尿布，啤酒}的支持度为3/5，呢么{尿布}->{啤酒}的关联规则的可信度可以被定义为“支持度({尿布，啤酒})/支持度({尿布})”，也就是3/4 = 0.75。这个更容易理解的表示方法是，对着这条推出式，对于我们数据集中75%的规则都适用。

假设我们要通过Apriori算法计算出数据集中的关联规则，我们就可能要计算所有商品所组成集合的所有子集，如果我们只出售100件商品，我们就可能要计算1.26 * 10^30中可能的项集组合。对于现代计算机而言，需要很长时间才能运行完成。

Apriori原理

如果某个项集是频繁的，那么他的所有子集也是频繁的。 相反，如果一个项集是非频繁项集，那么他的所有超集都是非频繁的。

apriori

利用Apriori原理，我们可以减少大量的支持度计算，避免项集数目的指数级增长，从而在合理的时间内计算出频繁项集。这个原理也会在之后的求解关联规则的方法中用到。

算法表述

首先我们需要一些数据，我们将我们所用到的商品编上号，使用数字在算法中表示：

  1. 豆奶
  2. 莴苣
  3. 尿布
  4. 葡萄酒
  5. 橙汁

然后我们有这样4条数据：

  1. [1,3,4] ==> [豆奶，尿布，葡萄酒]
  2. [2,3,5] ==> [莴苣，尿布，橙汁]
  3. [1,2,3,5] ==> [豆奶，莴苣，尿布，橙汁]
  4. [2,5] ==> [莴苣，橙汁]
发现频繁项集

首先我们所获得的数据集中只有记录：所以我们需要先获得单个商品的集合：

def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    return map(frozenset, C1)

这个集合主要有两个作用，第一取得第一次迭代计算支持度的集合，这些集合中的单个元素均需要计算支持度，并且在后续的计算中，利用Apriori原理，如果C1中的单元素集合无法符合最小支持度的要求，之后由其组成的Cn集合就不用再计算其支持度。而第二个作用，我们需要知道这次计算中所有相关的商品，即获得商品的全集。

在计算完C1过后我们就需要对已有的集合进行支持度的计算了，我们使用以下scanD函数对已有的集合进行支持度计算：

def scanD(D, Ck, minSupport):
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                if not ssCnt.has_key(can):ssCnt[can] = 1
                else: ssCnt[can] += 1
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key] / numItems
        if support >= minSupport:
            retList.insert(0, key)
        supportData[key] = support

    return retList, supportData

该函数的输入参数有数据集D，本次需要使用到的所有候选集，以及我们所定的最小支持度。返回的是本次计算中支持度在最小支持度之上的所有候选集的集合。还会返回所有的计算过支持度的候选集以备之后如果需要我们去挖掘频繁项集之间的关联规则。

之后我们需要去计算下一层的候选集的支持度，我们所需要做的就是用过上一层所用到的候选项集进行合并，我们用到了aprioriGen这个函数来完成这次工作：

def aprioriGen(Lk, k):
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i + 1, lenLk):
            L1 = list(Lk[i])[:k - 2]
            L2 = list(Lk[j])[:k - 2]
            L1.sort()
            L2.sort()
            if L1 == L2:
                retList.append(Lk[i] | Lk[j])
    return retList

这个函数所需要的一个是上一层的所有符合最小支持度的集合，另一个是本层需要的元素个数。返回的是这一层需要计算支持度的所有候选集。

这样我们基本上就可以使用Apriori算法进行对数据集中频繁项集的挖掘工作了：

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

首先我们使用createC1函数计算出初始候选项集，然后我们利用scanD函数计算出初始候选项集的支持度，然后我们通过一个while循环对现有的候选项集的数量进行判断，如果在本次计算过后候选项集的个数已经为0个，那么之后的计算就不必要了，因为通过Apriori原理，我们可以肯定之后的所有项集均不为频繁项集。我们在昨晚这个简单的判定之后，我们可以通过aprioriGen函数对已有的项集进行下一代项集的计算，然后继续通过scanD函数对该代的候选项集进行支持度计算及筛选，并且将所有的支持度有关信息更新到supportData字典，并将该代的所有频繁项集以列表的形式加入到L中。这样我们就获得了所有的可以被发掘的频繁项集。

挖掘关联规则

接下来，我们就可以开始挖掘关联规则了。首先我们需要一个计算置信度的函数，只有符合我们所确定的最小置信度的关联规则才是我们需要的。

def calcConf(freqSet, H, supportData, brl, minConf = 0.7):
    pruneH = []
    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))
            pruneH.append(conseq)
    return pruneH

calcConf函数给出了计算置信度的函数，该函数有5个输入参数，freqSet主要的作用是目标的频繁项集，H为该目标项集的本次计算中位于右侧推导位置的项集，这里的选择很多，我们需要一个递归的函数才能更好地展现这个过程。后面的supportData就是我们之前在计算频繁项集的过程中所附加产生的每一个项集的支持度数据。brl是用来传入来统计所有在最小置信度的关联规则的。最后一个minConf即为我们所定的最小置信度。

不知道这里的H大家理解了没有，这里H为需要在关联规则右侧出现的推导项，那么我们为什么需要这个作为函数的输入参数呢？ 我先给出置信度的定义：

置信度：针对关联规则定义。我们现在知道了{尿布}的支持度为4/5，{尿布，啤酒}的支持度为3/5，呢么{尿布}->{啤酒}的关联规则的可信度可以被定义为“支持度({尿布，啤酒})/支持度({尿布})”，也就是3/4 = 0.75。这个更容易理解的表示方法是，对着这条推出式，对于我们数据集中75%的规则都适用。

我们计算关联规则的基础是这样的：我们首先要保证这条关联规则中所有出现的项所组成的集合是在整个数据中有一定数量基础的，如果这个集合在数据集中所出现的次数很少，但是偶尔的一次机会，我们发现这个关联规则正好成立，那么纵然其置信度很高，甚至为100%，但是我们依旧无法相信其为真，因为他实在太偶然了，我们必须去发掘那些有普遍性的规则。

所以我们一定是在频繁项集中来考虑可能存在的关联规则的。

那我们需要在这些频繁项集中，挖掘关联规则，我们为什么不以等式左边的单个项集作为目标，而是要把右边可能为不同数量的项集作为目标呢？即我们为什么不选择看起来更加简单的能够获得的分母上的单个元素，而去考虑更加复杂的可能出现多项的去除的集合部分。

~~这是因为如果我们使用所有频繁项集中的每个项作为目标来写程序，算法的复杂度就太大了，这个和我们不适用apriori原理来计算所有的接下来的集合是一样的，但是如果我们使用右边的项集作为目标的话，我们就可以利用之前已经写好的aprioriGen函数来生成下一层需要在右边出现的项集了。~~

这个作为一个问题问老师吧！ 说法不是很对，我也没有理解，复杂度是一样的，并且左侧也可能会出现多项项集。

我好像又知道了。

def rulesFromConseq(freqSet, H, supportData, brl, minConf = 0.7):
    m = len(H[0])
    if len(freqSet) > (m + 1):
        Hmp1 = aprioriGen(H, m + 1)
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        if len(Hmp1) > 1:
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

这里给出的函数就是我们遇到大于两项的频繁项集的处理方法。输入的参数与calcConf函数的参数相同，我们会先判断需要减去的项集的长度是否小于给出的频繁项集的长度，因为如果已经等于或者甚至已经超过了，说明我们对该频繁项集已经挖掘完毕了。然后如果我们荏苒能够挖掘出其他可能的关联规则的话，我们就是用aprioriGen的函数计算需要在右侧出现的大于一项的项集。然后对这些项集进行支持度的计算。最后如果返回的剩余的需要被减去的项集数量大于1，则继续发掘可能的关联规则。

自此，所有的关联规则发掘完成。

blogroll

social