Association Rule Mining 关联规则挖掘

关联规则挖掘的任务为:尝试在数据集中自动发现简单的“如果—则”规则。

例如著名的:“如果一个人买了尿布,则他有较高的概率会顺带买啤酒。”

对于关联的解读是重中之重,如上面的关联可以有多种解读。。。:

如,1:某人想去酒吧喝酒,但是无奈被派去超市买尿布,于是他顺带买了啤酒,准备回家喝去。

如,2:某人想痛快地喝酒,不想频繁地去厕所解决问题,于是他买了尿布,穿着喝酒。

 

关联规则本身蕴涵着因果关系(如果—则),但是这个因果关系可以是任何方向的(A则B,B则A)。

关联规则也可以是复杂的,如: 如果A且B则C;或者,如果A则B且C。

 

关联规则挖掘的用途在于:生成一些供进一步研究的有趣假说。

 

关联规则挖掘主要有两个重要步骤:

  1. 发现规则
  2. 评价规则

1 评价规则

评价规则即判断什么样的规则是“好”的规则。

主要有三个指标:

  1. 支持程度(support)
  2. 置信程度(confidence)
  3. 有趣程度(interestingness)

 

1.1 支持程度 support

即:(满足规则的数据点的数量)除以(所有数据点的数量)。

例1:每一行代表一个学生,第一列代表学生选修数据挖掘课,第二列代表学生选修统计课。

QQ截图20131205120040

规则为:如果一个学生选修数据挖掘课,那么他也选修过统计课。

则支持程度为:2/11=0.2222。(第一列个第二列都为1的情况)除以(总数)。

 

1.2 置信程度 confidence

即:(满足规则的数据点数量)除以(所有满足“如果”条件的数据点的数量)。

如,例1中,对于同样的规则,置信程度为2/6=0.33。(第一列个第二列都为1的情况)除以(第一列为1的情况)

 

1.3 有趣程度 interestingness

有非常多的有趣程度衡量指标,如:

 

1 余弦(Cosine): P(A^B)/sqrt(P(A)×P(B))

即:(AB同时出现的概率)除以((A、B分别出现的概率的乘机)的平方根)

该值约接近1,则规则越有趣。

如,例1中,对于同样的规则,Cosine值为:(2/11)/sqrt((6/11)*(7/11))=0.309。

 

2 Lift: confidence(A –> B)/P(B):

即:(规则“如果A则B”的置信程度)除以(B出现的概率)。

如,例1中,对于同样的规则,Lift值为:(2/6)/(7/11)=0.524

 

除此以外还有非常多的有趣程度衡量指标,如gini index,odds ratio等。


2 发现规则

经典的算法为Apriori算法,主要过程为:

  1. 生成常见项集合(frequent itemset)
  2. 从常见项集合中生成规则

见 Agrawal et al., 1996

2.1 生成常见项集合

设定一个支持程度(support)值作为阀值:

  1. 以此阀值作为依据,筛选生成一个全部由单一项构成的集合,称为{i1}
  2. 从{i1}出发,生成(两项的对),以同样的阀值作为依据,筛选生成一个全部由(两项的对)构成的集合,称为{i2}
  3. 从{i2}出发,生成(三个项构成的三元组),以同样的阀值作为依据,筛选生成一个全部由三元组构成的集合,称为{i3}。

如此下去,最后将所有的集合进行联合。

 

2.2 从常见项集合中生成规则

  1. 对于一个给定的常见项集合,取出其中所有至少包含两个成分的项。
  2. 利用这些项生成规则。
  3. 以置信程度作为阀值对生成的规则进行筛选。
  4. 将筛选后得到的规则,按照有趣程度进行排序。

例如:生成的常见项集合为{A,B,C,D,{A,B},{A,C},{A,D},{B,D},{C,D},{A,B,C}….{A,B,C,D}},取出的项为{A,B,C,D},则生成的规则有:

{A,B,C} –> {D},{A,B,D} –> {C},{A,B} –> {C,D}等。


3 其他:

关联规则挖掘还有一些其他算法,区别在于搜索的方式和筛选依据。

另外还有消极关联规则(negatice association rule)的挖掘,即(如果—则不会)。

例见 Brin. et al. 1997

Leave a Reply

Your email address will not be published. Required fields are marked *