Madlib上关联规则的探讨

from zengxiaosen

Apriori algorithm是关联规则里一项基本算法。是由Rakesh Agrawal和Ramakrishnan Srikant两位博士在1994年提出的关联规则挖掘算法。关联规则的目的就是在一个数据集中找出项与项之间的关系，也被称为购物蓝分析 (Market Basket analysis)，因为“购物蓝分析”很贴切的表达了适用该算法情景中的一个子集。

　 　关于这个算法有一个非常有名的故事："尿布和啤酒"。故事是这样的：美国的妇女们经常会嘱咐她们的丈夫下班后为孩子买尿布，而丈夫在买完尿布后又要顺 手买回自己爱喝的啤酒，因此啤酒和尿布在一起被购买的机会很多。这个举措使尿布和啤酒的销量双双增加，并一直为众商家所津津乐道。


Apriori核心算法过程如下： 

  1. 过单趟扫描数据库D计算出各个1项集的支持度，得 到频繁1项集的集合。
  1. 连接步：为了生成，预先生成,由2个只有一个项不同的属于的频集做一 个（k-2）JOIN运算得到的。
  1. 剪枝步：由于是的超集，所以可能有些元素不是频繁的。在 潜在k项集的某个子集不是中的成员是，则该潜在频繁项集不可能是频繁的可以从中移去。
  1. 通过 单趟扫描数据库D，计算中各个项集的支持度，将中不满足支持度的项集去掉形成。


　 　通过迭代循环，重复步骤2～4，直到有某个r值使得为空，这时算法停止。在剪枝步中的每个元 素需在交易数据库中进行验证来决定其是否加入，这里的验证过程 是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库。可能产生大量的候选集，以及可能需要重复扫描数据库，是Apriori算法的两大缺 点。

　 　目前，几乎所有高效的发现关联规则的并行数据挖掘算法都是基于Apriori算法 的，Agrawal和Shafer 提出了三种并行算法：计数分发（Count Distribution）算法、数据分发（Data Distribution）算法和候选分发（Candidate Distribute）算法。



===

下面我们就使用上诉典型的例子在madlib上面做关联规则：

  1. DROP TABLE IF EXISTS test_data; 
  1. CREATE TABLE test_data (     trans_id INT,     product TEXT ); INSERT INTO test_data VALUES (1, 'beer'); 
  1. INSERT INTO test_data VALUES (1, 'diapers'); 
  1. INSERT INTO test_data VALUES (1, 'chips'); 
  1. INSERT INTO test_data VALUES (2, 'beer'); 
  1. INSERT INTO test_data VALUES (2, 'diapers'); 
  1. INSERT INTO test_data VALUES (3, 'beer'); 
  1. INSERT INTO test_data VALUES (3, 'diapers'); 
  1. INSERT INTO test_data VALUES (4, 'beer'); 
  1. INSERT INTO test_data VALUES (4, 'chips'); 
  1. INSERT INTO test_data VALUES (5, 'beer'); 
  1. INSERT INTO test_data VALUES (6, 'beer'); 
  1. INSERT INTO test_data VALUES (6, 'diapers'); 
  1. INSERT INTO test_data VALUES (6, 'chips'); 
  1. INSERT INTO test_data VALUES (7, 'beer'); 
  1. INSERT INTO test_data VALUES (7, 'diapers');


按照以上形式插入数据之后


Apriori解析：

在关联规则度量中有两个重要的度量值：支持度和置信度 。对于关联规则R:A=>B，则：

1. 支持度（suppport ）： 是交易集中同时包含A和B的交易数与所有交易数之比。

Support(A=>B)=P(A∪B)=count(A∪B)/|D|

2. 置信度（confidence ）： 是包含A和B交易数与包含A的交易数之比。

Confidence(A=>B)=P(B|A)=support(A∪B)/support(A)


  如上图中数据库D，包含4个事务，项集I={I1,I2,I3,I4,I5}，分析关联规则：I1=>I4，事务1、4

包含I1，事务4同时包含I1和I4。支持度support=1/4=25%（1个事务同时包含I1和I4,共有4个事务）指 在所有交易记录中有25%的交易记录同时包含I1和I4项目。置信度confidence=1/2=50%（1个事务同时包含I1和I4,2个事务包含I1）指 50%的顾客在购买

I1时同时还会购买I4。使用关联规则对购物篮进行挖掘，通常采用两个步骤进行： 下面将通超市购物的例子对关联规则挖掘进行分析。


使用关联规则对购物篮进行挖掘，通常采用两个步骤进行： 下面将通超市购物的例子对关联规则挖掘进行分析。

a.找出所有频繁项集（文章中我使用Apriori算法>=最小支持度的项集）

b.由频繁项集产生强关联规则（>=最小支持度和最小置信度）






阅读更多

更多精彩内容