β

Apriori算法简介及实现(python)

TianJun . Machine Learning 430 阅读

Apriori这个词的意思是“先验的”,从priori这个词根可以猜出来~;) 。该算法用于从数据中挖掘频繁项数据集以及关联规则。其核心原理是基于这样一类“先验知识”: 

如果一个数据项在数据库中是频繁出现的,那么该数据项的子集在数据库中也应该是频繁出现的(命题1)

$$     \forall X,Y\in J:(X\subseteq Y)\rightarrow f(X)\leq f(Y)  $$

反之亦然,其逆否命题为:

如果一个数据项在数据库中很少出现,那么包含该数据项的父集(superset)在数据库中也应该很少出现。(命题2)

  $$ f(X)\geq f(Y)\rightarrow \forall X,Y\in J:(X\supseteq Y) $$

背景知识:

①假设我们要从数据库中找到如下一种关联规则:

$$ x\rightarrow y $$

也就是说,当某一数据项包含包含集合X时,该数据项肯定包含集合Y。

②既然说有X的地方必定有Y,那么我们需要大量的数据来说明这一点。用X和Y同时出现的次数除以数据库中数据项的总数得到“支持度”的概念:

  $$    Support,s(X\rightarrow Y) = \frac {\delta (X \cup Y)}{N};  $$

③在集合X出现的数据项中,是否一定会出现集合Y呢?我们用X和Y同时出现的次数除以X出现的全部次数,得到“置信度”的概念:

   $$   Confidence,c(X\rightarrow Y) = \frac {\delta (X \cup Y)}{\delta (X)}; $$

深入理解apriori算法:

分析“支持度”和“置信度”的概念可知,在给定“支持度”和“置信度”的条件下为了找到关联规则,首先需要找到符合“支持度”条件的X和Y的并集{X,Y}。由命题1可知,如果集合{X,Y}满足“支持度”条件(即频繁出现),那么集合中的每个元素也应该是频繁出现的。集合的构成可以用树来表示,下面用图1来说明。

 

图 1 若{c,d,e}频繁出现,则{cd}{ce}{de},{c}{d}{e}也频繁出现

 

图 2如果{a,b}不是频繁集,那么{abc}{abd}{abe}{abcd}{abce}{abde}{abcde}也都不是频繁集。

由此可见,如果我们从单一元素所构成的集合下手(也就是上图中树的第一层,记为C1),根据“支持度”判别条件对该树进行“剪枝”,将大大降低计算的次数。

得到C1后,如果根据组合原理直接生成C2然后对每个可能的组合计算“支持度”,计算量依然很大。这里再次进行剪枝。为了不失一般性,对于Ck-1层中的每个集合先排序,然后将满足以下条件的集合融合,构成Ck层

$$ a_{i}=b_{i} (for\quad i=1,2,...,k-2) and a_{k-1}\neq b_{k-1} $$

之所以这样做是因为,根据命题2,如果集合C4层的{acde}是频繁集,那么C3层中必定要存在{acd}和{ace}。因此只需在C3成对这两个集合融合即可,不必再将{ace}和{ade}融合,在C3层对元素排序的目的也正是在此,快速地找到满足条件的子集并融合,避免重复计算。

优化:

在得到Ck层后,计算其中每个集合的“支持度”时,需要从数据库中遍历所有的数据项看是否包含该集合。这里可以采用Hash表将所有的数据映射到一张表上,以后就不用遍历整个数据库而是只遍历Hash值相同的所有数据项。

生成规则:

对于前面得到的频繁项集合中每个元素,其可能生成的规则可以表示为下图

 

图3 从频繁项生成规则

以上图为例来说明,假设由{bcd}生成{a}这一规则不满足置信度公式,回顾“置信度”的公式,也就是说{bcd}在数据库中出现的次数偏多,而{a}出现的次数偏少,根据命题1,{bcd}的子集也是频繁项,根据命题2,{a}的父集也很少出现,从而{bc}生成{ad}等规则的置信度更低,然后将其从集合树上减去。

总结:

将以上过程联系起来,就得到了书上的伪代码,我将其用通俗的语言解释一下:

1. 遍历数据库,得到所有数据项构成的并集(也就是得到图1的C1层)

2. 计算Ck层中每个元素的支持度(该过程可用Hash表优化),删除不符合的元素,将剩下的元素排序,并加入频繁项集R

3. 根据融合规则将Ck层的元素融合得到Ck+1,

4. 重复2,3步直到某一层元素融合后得到的是空集

5. 遍历R中的元素,设该元素为A={a1,a2......,ak}

6. 按照图 所示方法先生成I1层规则,即{x|x属于A且≠ai} →{ai}

7. 计算该层所有规则的“置信度”,删除不符合的规则,将剩下的规则作为结果输出。

8. 生成下一层的规则,计算“置信度”,输出结果。

参考文献:

      Machine Learning in Action:http://pan.baidu.com/s/1Gc4ss

      Introduction to Data Mining chapter 6 :http://pan.baidu.com/s/1oskIS

Python源码:

去GitHub下载该文件源码

 from numpy import *
 import itertools
 
 support_dic = {}
 
 #生成原始数据,用于测试
 def loadDataSet():
     return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
 
 #获取整个数据库中的一阶元素
 def createC1(dataSet):
     C1 = set([])
     for item in dataSet:
         C1 = C1.union(set(item))
     return [frozenset([i]) for i in C1]
 
 #输入数据库(dataset) 和 由第K-1层数据融合后得到的第K层数据集(Ck),
 #用最小支持度(minSupport)对 Ck 过滤,得到第k层剩下的数据集合(Lk)
 def getLk(dataset, Ck, minSupport):
     global support_dic
     Lk = {}
     #计算Ck中每个元素在数据库中出现次数
     for item in dataset:
         for Ci in Ck:
             if Ci.issubset(item):
                 if not Ci in Lk:
                     Lk[Ci] = 1
                 else:
                     Lk[Ci] += 1
     #用最小支持度过滤
     Lk_return = []
     for Li in Lk:
         support_Li = Lk[Li] / float(len(dataSet))
         if support_Li >= minSupport:
             Lk_return.append(Li)
             support_dic[Li] = support_Li
     return Lk_return
 
 #将经过支持度过滤后的第K层数据集合(Lk)融合
 #得到第k+1层原始数据Ck1
 def genLk1(Lk):
     Ck1 = []
     for i in range(len(Lk) - 1):
         for j in range(i + 1, len(Lk)):
             if sorted(list(Lk[i]))[0:-1] == sorted(list(Lk[j]))[0:-1]:
                 Ck1.append(Lk[i] | Lk[j])
     return Ck1
 
 #遍历所有二阶及以上的频繁项集合
 def genItem(freqSet, support_dic):
     for i in range(1, len(freqSet)):
         for freItem in freqSet[i]:
             genRule(freItem)
 
 #输入一个频繁项,根据“置信度”生成规则
 #采用了递归,对规则树进行剪枝
 def genRule(Item, minConf=0.7):
     if len(Item) >= 2:
         for element in itertools.combinations(list(Item), 1):
             if support_dic[Item] / float(support_dic[Item - frozenset(element)]) >= minConf:
                 print str([Item - frozenset(element)]) + "----->" + str(element)
                 print support_dic[Item] / float(support_dic[Item - frozenset(element)])
                 genRule(Item - frozenset(element))
 
 #输出结果
 if __name__ == '__main__':
     dataSet = loadDataSet()
     result_list = []
     Ck = createC1(dataSet)
     #循环生成频繁项集合,直至产生空集
     while True:
         Lk = getLk(dataSet, Ck, 0.5)
         if not Lk:
             break
         result_list.append(Lk)
         Ck = genLk1(Lk)
         if not Ck:
             break
     #输出频繁项及其“支持度”
     print support_dic
     #输出规则
     genItem(result_list, support_dic)
作者:TianJun . Machine Learning
自由~ 分享~~ 交流~~~
原文地址:Apriori算法简介及实现(python), 感谢原作者分享。

发表评论