关联规则挖掘的简介

现在的位置: 首页 > 综合 > 正文

关联规则挖掘的简介

2013年03月12日 ⁄ 综合 ⁄ 共 4587字 ⁄ 字号小中大 ⁄ 评论关闭

1 关联规则的基本概念

1.1 关联规则的意义

世间万物的事情发生多多少少会有一些关联。一件事情的发生，很可能是也会引起另外一件事情的发生。或者说，这两件事情很多时候很大程度上会一起发生的。那么人们通过发现这个关联的规则，可以由一件事情的发生来，来推测另外一件事情的发生，从而更好地了解和掌握事物的发展，动向等等。这就是数据挖掘中，寻找关联规则的基本意义。

在高校教务管理中，我们也可以发现这样的规律。比如说，计算机学院的《C++程序设计语言》和《C程序设计语言》两门课程。一般大一的时候《C程序设计语言》拿优的学生，在大二学习《C++程序设计语言》的时候，多半也会拿优。而《C程序设计语言》不及格而补考的学生，在大二学习的《C++程序设计语言》课程里面，多半不会拿到优。道理很简单，因为《C程序设计语言》是《C++程序设计语言》的先行课程，如果没有良好的C语言功底，对于更加的复杂C++学习，肯定是很困难的。于是，这里就存在一个两门课程成绩的关联规则。

但是，我们也不能说，《C程序设计语言》不及格的学生，100％不会在其后的《C++程序设计语言》中拿到优。所以，从严谨的角度来阐述这条关联规则的时候，都是附带了规则发生的一系列概率参数。比如说，计算机学院02级里面10%的学生《C语言设计语言》和《C++程序设计语言》都拿到了优，而其中75%在《C程序设计语言》中拿到优的学生，在大二的《C++程序设计语言》课程中也拿到了优。由于我们不可能得到事情发生的概率，所以很多时候，我们都是以频率来接近概率。那么这条关联规则，可以阐述成：

C程序设计语言(优) à C++程序设计语言(优), support=10%, confidence=75%

其中，support代表支持度，confidence代表置信度。通过这两个参数，人们可以大致了解一条关联规则的作用于现实世界的情况和偏差等等。

数据挖掘技术中的关联规则挖掘是通过计算机自动从一大对真实数据中发现这样的关联规则出来。对于计算机而言，它需要知道所有的事情发生情况，并且把相应的事情合并成一个事务，通过对各个事务的扫描，来确定事情的关联规则。

1.2 关联规则的定义

设I={i₁, i₂,…, i_m}是项的集合，其中的元素称为项(item)。记D为事务(transaction)T的集合，这里事务T是项的集合，并且TI
。对应每一个事务有唯一的标识，如事务号，记作TID。设X是一个I中项的集合，如果XT，那么称事务T包含X。

一个关联规则是形如XY的蕴涵式，这里XI, YI，并且XY=F。规则XY在事务数据库D中的支持度（support）是事务集中包含X和Y的事务数与所有事务数之比，记为support(XY)，即

support(XY)=
P(X Y)

规则XY在事务集中的可信度（confidence）是指包含X和Y的事务数与包含X的交易数之比，记为confidence(XY)，即

confidence(XY)=
P(X|Y)

给定一个事务集D，挖掘关联规则问题就是寻找支持度和可信度分别大于用户给定的最小支持度(minsupp)和最小可信度(minconf)的关联规则。

1.3 关联规则的相关性分析

比如，计算机学院学生成绩库中，有15%的同学的《数据结构》和《离散数学》都是优，其中70%《数据结构》得优的同学《离散数学》的成绩是优。用数学公式表达这个关联规则就是:

数据结构(优) à 离散数学(优),support=15%,confidence=70%

这样一个关联规则能够启示我们，数据结构作为计算机学院十分重要的必修课，要取得好的教学成果，必须加强其先行课程《离散数据》的重视程度。

同时，实际挖掘出来的一些关联规则，并非都是有用的，甚至是有一定的误导性。比如，40%的计算机学院02级同学的《法律基础》和《大学体育4》都是优，其中86%《法律基础》为优的同学，《大学体育4》是得的优。如果我们认为《大学体育4》是十分依靠先行课程《法律基础》，那么就是错误的。实际情况是《大学体育4》是游泳课，因为考核十分容易，90%以上的同学都拿到优。所以，《大学体育4》的成绩其实跟《法律基础》这门课程是没有必然联系的。

针对这类情况，标准的做法是通过简单的相关性分析^[11]，来排除这类蕴涵关系的规则。相关性的度量:

Corr_A,B = P(A∪B) / (P(A)*P(B)) = P(B|A)/P(B)

很容易计算出来，区别事务A和事务B之间的相关性，将其结果小于1的，既是称之为负相关。在最后的规则产生的时候，需要删除负相关的规则。

比如上面的《法律基础》和《大学体育4》的例子。以A表示《法律基础》课程为优的事务，B表示《大学体育4》为优的事务。

P(B|A)/P(B) = P(大学体育4 | 法律基础) / P(大学体育4)
= 86% / 90% < 1。则它们是负相关的，应该是没有实际意义的关联规则。

2 关联规则的基本算法Apriori

关联规则的挖掘可以分成两个步骤：
1. 根据最小的支持度，在大量事务寻找高频率出现的频繁项集(Itemset)。

2. 根据最小的置信度，找到的频繁项集产生关联规则。

其中第二个步骤比较容易，一般经过第一步的筛选后的频繁项集都不会很多，通过子集产生法就可以产生关联规则。第一个步骤是需要在大量的事务数据集中寻找高频率出现的项集Itemset，所以就需要一个比较高效的搜索查找方法。

Rakesh Agrawal等在1993年提出了第一步搜索频繁项集的经典Apriori算法^[12,13]。通过遍历一大堆事务数据中，从一个一个的单个项开始记数，每次遍历完所有的事务后，裁减掉支持度记数少于用户给定的支持度的项，然后逐步扩展到多项事务。最后保留下来的频繁项集，通过子集产生法来产生关联规则，然后去掉其中置信度低于用户指定的最低置信度的关联规则，最后剩下的就是满足用户需要的关联规则。

Apriori算法的特点就是在于从单项开始，每次剪裁一点，利用Apriori性质^[13],有效避免了对很多不可能的项的搜索过程。

2.1 Apriori性质

Apriori性质：频繁项集的所有非空子集都必须也是频繁的。如果项集I不满足最小支持度阈值s，则I不是频繁的，即P(I) < s。如果项A添加到I，则结果项集(I ∪ A）不可能比I更频繁出现。因此，(I,A)也不是频繁的，即P(I ∪ A) < s。

Apriori性质主要是用于搜索频繁项集的时候对候选式的筛选过程。Apriori算法中利用Apriori性质，能够比较好地避免盲目的搜索，提高频繁项集的查找效率。

6.2.2 Apriori算法

Apriori算法的频繁项集查找是一个逐层迭代的方法。每层查找分成项集itemset的连接和剪枝两个步骤。连接步骤是在为找k-项频繁项集L_k，通过k-1项频繁项集L_{k

- 1}与自己连接产生候选k-项集的集合C_k。剪枝步骤是扫描事务数据集，去掉那些支持度小于指定最小支持度的事务项。

算法开始从最简单的1-项开始进行筛选，找出L₁后，L₁与L₁自身连接产生C₂，然后对C₂的所有事务项进行筛选后，产生L₂，由此，不断迭代下去，直到最后L_k为空集。

下面是引用参考文献13中的Apriori算法伪代码参考。

算法Apriori 使用逐层迭代找出频繁项集

输入：事务数据库D；最小支持度阈值。

输出：D中的频繁项集L。

方法：

1) L₁ = find_frequent_1_itemsets(D);

2) for (k = 2; L_k-1
; k++) {

3) C_k = aproiri_gen(L_k-1,min_sup);

4) for each transaction tD{ //scan D for count

5) C_t = subset(C_k,t);
//get subsets of t that are candidates

6) for each candidate cC_t

7)
c.count++;

8) }

9) L_k={cC_k | c.count
min_sup}

10) }

11) return L = _kL_k；

procedure apriori_gen(L_k-1: frequent (k-1)-itemset; min_sup: support)

1) for each itemset l₁L_k-1

2) for each itemset l₂L_k-1

3) if (l₁[1]=l₂[1])...(l₁[k-2]=l₂[k-2])(l₁[k-1]<l₂[k-2])
then {

4)
c = l₁l₂; //join step: generate candidates

5) if has_infrequent_subset(c,L_k-1) then

6) delete c; // prune step: remove unfrequent cadidate

7) else add c to C_k;

8) }

9) return C_k;

procedure has_infrequent_subset(c:candidate k-itemset; L
_k-1:frequent (k-1)-itemset)

// use priori knowledge

1) for each (k-1)-subset s of c

2) if cL_k-1then

3) return TRUE;

4) return FALSE;

2.3 根据频繁项集产生关联规则

设找到的某个频繁事务项A，其某个真子集为B{I_j1,I_j2,I_j3,…,I_jm}，可以计算B的补集C = A - B

,设C为{I_k1,I_k2,I_k3,…,I_kn}。
那么，如果confidence(B => C) = P(B | C) = support_count(A) / support_count(B) > min_confidence，则可以产生强关联规则B => C，既是:

2.4 Apriori基本算法的缺陷

数据挖掘作为OLAP的数据分析处理，数据I/O效率往往都是其算法实现的瓶颈。Apriori算法在寻找频繁项集的时候，需要多次重复扫描数据库，所以其效率并不理想。同时，Apriori逐步迭代产生候选项集规模也可能十分巨大，呈现组合式的增长速度。比如，当长度为1的频繁项集有10000个的时候，长度为2的候选项集个数将会超过10M。

文章来自：http://maocom.com/resources/program/html/2006716/2781.htm

【上篇】jdk6.0中webservice新特性应用
【下篇】汉字交换码和机内码

作者: fissure

该日志由 fissure 于11年前发表在综合分类下，最后更新于 2013年03月12日.
转载请注明: 关联规则挖掘的简介 | 学步园 +复制链接

抱歉!评论已关闭.

学步园