计算机视觉
图像处理

机器学习(八)Apriori算法学习

学习Apriori算法建议用Python,因为python的集合函数功能相当强大,而Apriori涉及到集合的合并等运算。开始学习Apriori算法之前,我们先来搞一个简单的问题,这个问题在Apriori算法中非常重要。问题是这样的:

假设现在有三个集合C2(1)={0,1}、C2(2)={0,2}、C2(3)= {1,2},这些集合都是不相等的,因为每个集合中有且只有两个元素,所以这里我们记为C2。现在求把这3集合进行两两组合,使得组合结果包含3个不重复 的元素,记为C3,那么可以得到哪些组合结果呢?理论上来说,根据数学的组合,组合结果的个数应该是,即为3种组合结果,分别为:1-2组合{0,1,2}      1-3组合{0,1,2}     2-3组合{0,1,2}

然而其实3种组合结果中,是有重复的。其实最后的组合结果只有1种,即: {0,1,2}。那么怎么样进行组合才能减小计算,避免进行重复的组合呢?比如说我们1-2已经组合过了,得到组合结果{0,1,2},那么我们1-3就 没有必要进行再次组合了,因为组合出来的结果是重复的,因此为了避免计算。下面讲解一下,如何进行组合,才能避免重复。在Apriori算中,有这样的一 个避免重复组合的算法:

1、寻找与C2(k)待组合的集合,我们从C2(k+1)、C2(k+2)……开始寻找到最后一个,我们把C2(k+1)、C2(k+2)……统计记为C2(i),其中i>k。

2、如果C2(i)的前面N-2个元素,与C2(k)相同,则进行组合,求取并集。在这里N指的是这些待组合集合中元素的个数,这边N=3,因为这些待组合的集合每个中有且只有三个元素,因此N-2=1

根据这个算法,我们进行组合:

第一步:从首个集合开始遍历,寻找与C2(1)待组合的集合,分别为C2(2)、C2(3),然而C2(2)、C2(3)中,与C2(1)的前1个元素相同的只有C2(2),因此我们进行组合,组合结果为{0,1,2} 。

第二步:寻找与C2(2)待组合的集合,分别为C2(3),然而C2(3)中第一个元素与C2(3)不同,因此我们没有必要进行组合。

第三步:由于C2(3)已然是最后一个了,没有集合与它组合,因此程序就算做结束了

因此最后的合并结果只有:{0,1,2}。

OK,接着用python写一下代码,试一下:

  1.  def combination(dataset,k):
  2.     b=map(set,dataset);
  3.     result=[];
  4.     for i in range(len(dataset)):
  5.         for j in range(i+1,len(dataset)):
  6.             if dataset[i][:k-2]==dataset[j][:k-2]:
  7.                 result.append(list(b[i]|b[j]));
  8.     return result;
  9. #测试一下上面的函数写的对不对
  10. dataset=[[0],[1],[2]]
  11. result1=combination(dataset,2)
  12. print result1
  13. result2=combination(result1,3)
  14. print result2

 

ok,代码写完了,运行是试一下,得到如下结果:

可以看到,集合{0},{1},{2}将组合出{0,1},{0,2},{1,2}

然后{0,1},{0,2},{1,2} 将组合出{0,1,2}

到这里可以说,如果你亲手把代码敲过一遍,那么恭喜你,你已经把Apriori算法的代码写完了一半了,因为combination函数就是Apriori算法的上半部分,是不是感觉Apriori算法的实现轻轻松松,写完这个函数,保存起来。

接着正式开始讲Apriori算法,我没打算讲太多理论的东西,因为网上查一查理论一 大堆,我这个人喜欢实践,理论的东西,只要稍微看一下,基本上就懂了,Apriori算法的理论感觉很简单,什么叫支持度、置信度,还有什么叫频繁项集, 有好几个概念,需要先百度搜一下,明白了问题以后,就直接开始算法,Apriori算法分为两步进行:

1、连接步 ,这一步就是上面所讲的combination函数,给定频繁项集Lk-1(combination函数中的参数dataset),及其即将组合的新候选集中,每个集合元素的个数k,然后进行组合连接得到CK

2、剪枝步,这一步要实现的就是对CK进行修剪,说的简单一点就是删除那些不符合频繁 项集条件的子集。假设Ck=[{0,1},{0,2},{1,2}],那么假设经过这一步{0,2}在所有记录中,出现的概率小于小于给定的概率 Pmin,即如果P(CK(i))<Pmin就不符合条件,那么就把它删了。因此实现这一步涉及到两个问题:(1)计算频繁项集出现的概率 P(CK(i)),(2)比较大小P(CK(i))<Pmin。OK,据此,我们先写一个函数实现这一步骤:

  1. def scanCK(D,ck,pmin):
  2.     count={}
  3.     result=[];
  4.     for i in ck:
  5.         for j in D:
  6.             if i.issubset(j):
  7.                 if not count.has_key(i):#统计
  8.                     count[i]=1
  9.                 else:
  10.                     count[i]+=1
  11.     #扫描统计结果
  12.     support={}
  13.     nitem=float(len(D));
  14.     for k in ck:
  15.         support[k]=count[k]/nitem;
  16.         print ‘计算频繁集发生的概率’,support[k];
  17.         if support[k]>pmin:
  18.             result.append(k);
  19.     return result;

 

#测试函数是否正确

>>>dataset=[[0],[1],[2]]
>>>c1=[[1]]
>>>result0=scanCK(dataset,map(frozenset,c1),0.5)

因为我们总目录是[[0],[1],[2]],而项集为[[1]],因此发生的概率为三份之一,计算结果正确。以上两个函数都写完了,接着我们的目标就是把它们整合在一起,完成算法:

  1. def combination(dataset,k):
  2.     b=map(set,dataset);
  3.     result=[];
  4.     for i in range(len(dataset)):
  5.         for j in range(i+1,len(dataset)):
  6.             if dataset[i][:k-2]==dataset[j][:k-2]:
  7.                 result.append(list(b[i]|b[j]));
  8.     return result;
  9. def scanCK(D,ck,pmin):
  10.     print ck
  11.     count={}
  12.     result=[];
  13.     pro=[]
  14.     for i in ck:
  15.         for j in D:
  16.             if i.issubset(j):
  17.                 if not count.has_key(i):#统计
  18.                     count[i]=1
  19.                 else:
  20.                     count[i]+=1
  21.     #扫描统计结果
  22.     support={}
  23.     nitem=float(len(D));
  24.     if nitem>0:
  25.         for k in ck:
  26.             support[k]=count[k]/nitem;
  27.             if support[k]>pmin:
  28.                 pro.append(support[k]);
  29.                 result.append(list(k));
  30.     return result,pro;
  31. def createc1(dataset):
  32.     c1=[];
  33.     for i in dataset:
  34.         for j in i:
  35.             if not [j] in c1:
  36.                 c1.append([j]);
  37.     return c1;
  38. def apriori(dataset,pmin):
  39.     c1=createc1(dataset);
  40.     c1.sort()
  41.     maxlength=0;
  42.     for i in dataset:
  43.         if len(i)>maxlength:
  44.             maxlength=len(i);#计算元素最大的项目集
  45.     i=1;
  46.     result=[];
  47.     ck=c1;
  48.     while i<=maxlength:
  49.         b=map(frozenset,ck)
  50.         lk,pro=scanCK(dataset,b,pmin)
  51.         result.append(lk);
  52.         i=i+1
  53.         ck=combination(lk,i)
  54.     return result;
  55. dataset=[[1,3,4],[2,3,5],[1,2,3,5],[2,5]]
  56. result0=apriori(dataset,0.7)
  57. print result0

 

算法就这样 ,但是不知道在学习Apriori算法的过程中,有没有疑问:在某一次循环的过程中combination函数的输入有没有可能是:C2(1)= {0,1}、C2(2)={0,2}、C2(3)={1,2}、C2={1,3}。这是完全可能存在的,那么这个时候是不是可以:1-4组合,合成 {0,1,3}呢?而根据combination函数的结果,肯定最后的组合结果只有{0,1,2}。这就得从Apriori算法的原理说起:如果某个项 集是频繁的,那么它的所有子集也是频繁的;反过来,如果子集是非频繁的,那么超集肯定是非频繁的。上面的问题,我们知道{0,3}没有在C2中 ,代表{0,3}是非频繁集,也就是说:{0,1,3}绝对是非频繁项集,因此我们组合C3的时候,就完全没有必要去合成{0,1,3},即便是合成了, 到了下一步的剪枝步,也会被去除。

参考文献:1、《机器学习实战》

转载注明来源:CV视觉网 » 机器学习(八)Apriori算法学习

分享到:更多 ()
扫描二维码,给作者 打赏
pay_weixinpay_weixin

请选择你看完该文章的感受:

0不错 0超赞 0无聊 0扯淡 0不解 0路过

评论 3

评论前必须登录!