注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

行走的馒头

Stay Hungry, Stay Foolish

 
 
 

日志

 
 

十三、Association Rule  

2012-10-08 23:05:30|  分类: 统计学习初探索 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Association Rule

Definition

    Generally来看,association rule是在的取值空间上找到一些点,使得这些点的概率密度函数都比较大,这种问题又被称之为mode finding或者bump hunting。这个问题其实非常困难,对于进行估计,一个非常自然的想法就是用样本中满足的那些样本点的数目除以样本点总数目,即。如果的维度比较大,而且每个维度上都可以取很多不同的值,那么可以推测满足的样本的数量其实会非常至少,常常会不足以进行可靠的密度估计。

    前面提到要在取值空间上找到某些点使得其概率密度较大,为了使问题得以简化,需要在对细节的追求上做出一些牺牲,把对点的追逐改为对区域的评价。这时目的就是找出取值空间上的某些区域使得这些区域上的概率都比较大。令表示所有可能的取值,,那么这时我们的目标就是使得比较大。其中被称之为conjunctive rule。对于是连续变量的情况,那么此时就是一段连续的区域。如果满足,那么其实没有发挥什么作用,因此目标中就会把变量抹去。

    都很大的时候,比如,上面提出的简化问题仍然非常难以求解,因为这些的区间太多了,在计算上是intractable的。这时我们需要对于问题进一步的简化,这时可以使得要么是一个特定的值,即;么等于,即。根据前面的,这时我们的目标为找出和相对应的,使得比较大。这时我们可以通过使用dummy variables把问题变为binary-value可以解决的。假设每个集合是有限的,令,可以通过设置新的变量来表示原空间上的值。这时问题就可以转化为找到一些集合,使得比较大。这就是Data Mining的经典问题market basket problem的表现形式。其中被称之为item set,可看作是购买了商品,反之则是没有购买。目标的估计可表示如下

 。

称之为item set 的support或者prevalence。如果一个样本点满足,就可以说这个样本点contain这个item set 。在association rule中,我们的目标是找出

 (13.1)

这里是某个阈值,被称之为lower support bound。

 

The Apriori Algorithm

    式子(13.1)中一共包括种可能的item sets,当很大的时候,分别计算这种可能的是不现实的,而Apriori Algorithm则通过对数据库进行几次扫描来避免这种维数灾难,算法基于以下两点

  1. 集合的势是非常小的。
  2. 对于任何

Apriori Algorithm可以描述为

    Step 1. 首先找到那些并满足的item sets,。

    Step 2. 用那些满足的的item sets来产生的candidates,再从这些candidates中筛选出那些满足的item sets。

    Step 3. 迭代进行Step 2直至产生的candidates的support都小于阈值时停止。

    从算法中可以看出,对于的每一个值,在算法中只需要进行一次数据库的扫描。

    Apriori Algorithm找出的这些这些item sets 被转化为一系列的association rules。对于,可以写成association rule的形式。其中被称之为antecedent,被称之为consequent。其中称之为这条rule的support;,称之为这条rule的confidence或者predictability;被称之为expected confidence;最后被称之为这条rule的lift。

    前面提到的Apriori Algorithm只是找到那些满足满足support大于某一阈值的item sets,而通常我们的目标是找出那些support和confidence都比较大的association rules,即我们的目标为

。对于每个找到的满足support大于阈值的item set ,可以产生种可能的association rules,这时可以通过对Apriori Algorithm进行稍微的改进使其能够快速的找出满足confidence大于阈值的那些association rules。


  评论这张
 
阅读(629)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017