Apriori 关联分析算法原理分析与代码实现

2015-01-09 来源: 空山悟 发布在  http://www.cnblogs.com/scut-fm/p/4207106.html

前言

  想必大家都听过数据挖掘领域那个经典的故事 - "啤酒与尿布" 的故事。

  那么,具体是怎么从海量销售信息中挖掘出啤酒和尿布之间的关系呢?

  这就是关联分析所要完成的任务了。

  本文将讲解关联分析领域中最为经典的Apriori算法,并给出具体的代码实现。

关联分析领域的一些概念

  1. 频繁项集: 数据集中经常出现在一起的物品的集合。例如 "啤酒和尿布"

  2. 关联规则: 指两个物品集之间可能存在很强的关系。例如 "{啤酒} -> {尿布}" 就是一条关联规则。

  3. 支持度: 数据集中,出现了某个物品集的数据项占总数据项的比重。

  4. 可信度: 这个概念是针对某条关联规则而定的。它是指两个物品集的支持度和其中某个物品集的支持度之比,如 "支持度{啤酒,尿布} / 支持度{尿布}"。

  因此,用这些属于来解释啤酒与尿布的故事,那就是:{啤酒,尿布}是一个频繁项集;"{啤酒} -> {尿布}" 就是一条关联规则;顾客买尿布的同时买啤酒的可能性为 "支持度{啤酒,尿布} / 支持度{尿布}"。

  那么对海量的数据,假如要得到支持度大于0.8的所有频繁项集,该怎么做?

  如果用蛮力法一个个统计,是根本不现实的,那样计算量实在太大。

  本文将要介绍的Apriori关联分析算法意义就在于能够大幅度减少这种情况的计算量,并从频繁项集中高效检索出关联规则,从而大大减少关联规则学习所需要消耗的计算量。

Apriori算法基本原理

  如果{0,1}是频繁项集,那么{0}和{1}也都是频繁项集。

  这显然是正确的命题。

  其逆否命题 - ”如果{0}和{1}不都是频繁项集,那么{0,1}不是频繁项集" 自然也是正确的。-> 这就是 Apriori 算法的核心思想之一。

  这样,一旦发现某个集合不是频繁项集,那么它的所有超集也都不是频繁项集,就不用浪费功夫去对它们进行检索了。

  检索出频繁项集之后,接下来检索出所有合乎要求的关联规则。

  如果某条规则不满足最小可信度要求,那么该规则的所有子集也不会满足。 -> 这是 Apriori 算法的核心思想的另一部分。

  PS:这里务必思考清楚规则是怎么划分的,什么叫某个规则的子集。

  这样,和上一步同理,也能高效的从频繁项集中检索出关联规则了。

  具体实现将分为频繁集检索和关联规则学习两个部分进行讲解。

频繁项集检索实现思路与实现代码

  一种经典的实现方法是 "分级法":

  算法框架是在两个大的步骤 - 筛选/过滤之间不断迭代,直到所有情况分析完毕。

  每次筛选的结果都要指定元素个数的情况,因此所谓分级,也就是依次讨论指定元素个数情况的项集。

  在筛选之后,就是过滤。

  过滤有两层意义,一个是项集必须在数据集中存在。这是第一层过滤;还有一层过滤,是指支持度过滤。只有满足支持度要求的项集才能保存下来。

  过滤之后,基于过滤集再进行筛选,每次筛选的元素个数都比上一次筛选的元素个数多一个。

  然后继续过滤。如此反复,直到最后一次筛选过滤完成。

  伪代码实现:

当集合中项的个数大于0时:
    构建一个 k 个项组成的候选项集的列表
    检查数据以确认每个项集都是频繁的
    保留频繁项集并构建 k+1 项组成的候选项集列表

  其中检查每个项集是否频繁部分的伪代码:

对数据集中的每条交易记录:
    对每个候选集元素:
        检查是否为数据集元素,是才保留。
对每个数据集
    如果支持度达到要求才保留
返回过滤后的频繁项集 - 也即过滤集

  Python实现及测试代码:

 def loadDataSet():
     '返回测试数据'

     return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

 #===================================
 # 输入:
 #        dataSet: 数据集
 # 输出:
 #        map(frozenset, C1): 候选集
 #===================================
 def createC1(dataSet):
     '创建候选集'

     C1 = []
     for transaction in dataSet:
         for item in transaction:
             if not [item] in C1:
                 C1.append([item])

     C1.sort()

     # 返回的集合元素都是frozenset类型 -> 因为以后要用来做键。
     return map(frozenset, C1)

 #=============================================
 # 输入:
 #        D: 数据集 (set格式)
 #        Ck: 候选集
 #        minSupport: 最小支持度
 # 输出:
 #        retList: 过滤集
 #        supportData: 支持集(挖掘关联规则时使用)
 #=============================================
 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

 #===================================
 # 输入:
 #        Lk: 过滤集
 #        k: 当前项集元素个数
 # 输出:
 #        retList: 候选集
 #===================================
 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

 #=============================================
 # 输入:
 #        dataSet: 数据集
 #        minSupport: 最小支持度
 # 输出:
 #        L: 频繁集
 #        supportData: 支持集(挖掘关联规则时使用)
 #=============================================
 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

 def main():
     'Apriori频繁集检索'

     L, s = apriori (loadDataSet())

     print L
     print s

  测试结果:

  

关联规则学习实现思路与实现代码

  上一部分的工作是从数据集中检索出频繁集;而这一部分是根据频繁集学习关联规则。

  上一部分的工作是通过筛选集中的元素个数进行分级;而这一部分是针对规则右部的元素个数进行分级。

  另外还要注意,只用检索单个频繁集之内的关联规则就可以了。

  实现代码:

 #===================================
 # 输入:
 #        L: 频繁集
 #        supportData: 支持集
 #        minConf: 最小可信度
 # 输出:
 #        bigRuleList: 规则集
 #===================================
 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]
             if (i > 1):
                 rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
             else:
                 calcConf(freqSet, H1, supportData, bigRuleList, minConf)
     return bigRuleList         

 #===================================
 # 输入:
 #        L: 频繁集
 #        supportData: 支持集
 #        minConf: 最小可信度
 # 输出:
 #        bigRuleList: 规则集
 #===================================
 def calcConf(freqSet, H, supportData, brl, minConf=0.7):
     '可信度过滤'

     prunedH = []
     for conseq in H:
         conf = supportData[freqSet]/supportData[freqSet-conseq]
         if conf >= minConf:
             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)):
         # 重组规则右部
         Hmp1 = aprioriGen(H, m+1)
         # 规则学习
         Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
         if (len(Hmp1) > 1):
             # 递归学习函数
             rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

 def main():
     '关联规则学习'

     L, s = apriori (loadDataSet())

     rules = generateRules(L, s)
     print rules

  测试结果:

  

  测试数据为: [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

  结果的意思也就是说:1->3,5->2,2->5 的概率为 1。

  显然这是和预计相吻合的。

小结

  1. Apriori关联算法在网络购物网站中用的非常多,可以基于此算法搭建商品推荐系统。

  2. 但Apriori算法也有一个缺点,那就是频繁集的检索速度还是不够快,因为每级都要重新检索一遍候选集(虽然候选集越来越小)。

  3. 针对 2 中的问题,下篇文章将介绍一个更为强大的发现频繁集的算法 - FP-growth。(但它不能用来发现关联规则)

相关文章