数据挖掘原理与算法课程学习(2)

st1\:*{behavior:url(#ieooui) }

第三章：关联规则挖掘理论和算法

 

关联规则挖掘是数据挖掘中最活跃的研究方法之一，最早是由Agrawal等人提出的（1993）。

 

当前对关联规则挖掘问题的研究主要有：关联规则挖掘理论的探索；原有算法的改进和新算法的设计；并行关联规则挖掘（Parallel Association Rule Mining）；数量关联规则挖掘（Quantitive Association Rule Mining）等。

 

3.1、基本概念与解决办法

一个事务数据库中的关联规则挖掘可以描述如下：

设I={i₁，i₂，... ，i_m}是一个项目集合，事务数据库D={t₁，t₂，…，t_n}是由一系列具有唯一标识TID的事务组成，每个事务t_i（i=1，2，…，n）都对应I上的一个子集。

 

定义1：设项目集I₁?I，I₁在数据集D上的支持度是包含I₁的事务在D中所占的百分比，即

support（I₁）= || {t∈D | I₁?t } || / || D ||

 

定义2：对项目集I和事务数据库D，T中所有满足用户指定的最小支持度（Minsupport）的项目集，成为频繁项目集（Frequent Itemsets）或大项目集（Large Itemsets）。在所有频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集（Maximum Frequent Itemsets）或最大项目集（Maximum Large Itemsets）。

 

定义3：一个定义在I和D上的形如I₁?I₂ 的关联规则通过满足一定的可信度（Confidence）来给出。所谓规则的可信度是指包含I₁ 和I₂的事务数与包含I₁的事务数之比，即

confidence（I₁?I₂）= support（I₁∪I₂）/ support( I₁ )

其中I₁、I₂  ? I，I₁∩I₂ = F。

 

定义4：D在I上满足最小支持度和最小信任度（Minconfidence）的关联规则称为强关联规则。通常我们所说的关联规则一般是指强关联规则。

 

关联规则挖掘问题可以划分为两个子问题：

1、  发现频繁项目集（近年来的研究重点）；

2、  生成关联规则；

 

3.2、经典的频繁项目集生成算法分析

 

3.2.1、项目集空间理论（Agrawal）

定理1：如果项目集X是频繁项目集，那么它的所有非空子集都是频繁项目集。

定理2：如果项目集X是非频繁项目集，那么它的所有超级都是非频繁项目集。

 

3.2.2、经典的发现频繁项目集算法

Agrawal等提出的Apriori算法，通过项目集元素数目的不断增长来逐步完成频繁项目集的发现。

 

算法1：Apriori（发现频繁项目集）

输入：数据集D；最小支持数minsup_count

输出：频繁项目集L

（1）       L1 = { large1–itemsets };  //所有支持度不小于minsupport的1-项目集

（2）       FOR （k = 2；L_k-1≠F；k++） DO  BEGIN

（3）           Ck = apriori–gen（L_k-1）;   //C_k是k个元素的候选集

（4）           FOR  all transactions  t∈D  DO  BEGIN

（5）               C_t = subset（C_k，t）;   // C_t是所有t包含的候选集元素

（6）               FOR  all transactions  c∈C_t  DO  c.count++;

（7）           END

（8）       L_k = { c∈C_k | c.count ≥ minsup_count }

（9）       END

（10）   L = ∪L_k;

 

算法1中调用了apriori–gen（L_k-1），它是通过(k-1)-频繁项目集产生k-候选集。

算法2：apriori–gen（L_k-1）  （候选集产生）

输入：(k-1)-频繁项目集L_k-1

输出：k-候选集C_k

（1）       FOR  all itemset p∈ L_k-1  DO

（2）           FOR all itemset q∈ L_k-1  DO

（3）               IF p.item₁ = q. item₁, p.item₂ = q. item₂, … , p.item_k-2 = q. item_k-2, p.item_k-1 < q. item_k-1  THEN  BEGIN

（4）                     c = p∞q;  //吧q的第k-1个元素连到p后

（5）                     IF  has_infrequent_subset (c, L_k-1)  THEN

（6）                         delete  c;  //删除含有非频繁项目子集的候选元素

（7）                     ELSE  add  c  to  C_k

（8）                END

（9）       Return  C_k

 

算法2中调用了has_infrequent_subset (c, L_k-1)，作用是判断c是否需要加入到k-候选集中。

算法3：has_infrequent_subset (c, L_k-1) （判断候选集的元素）

输入：一个k-候选项目集c，（k-1）频繁项目集L_k-1

输出：c是否从候选集中删除的布尔判断

（1）       FOR  all (k-1)-subsets of c  DO

（2）           IF  S?L_k-1  THEN  return TRUE

（3）       Return  FALSE

 

3.2.3、关联规则生成算法

在得到了所有的频繁项目集之后，可以按照下面的步骤生成关联规则：

（1）       对于每个频繁项目集l，生成其所有其所有的非空子集；

（2）       对于l的每个非空子集x，计算confidence（x），如果configdence（x）≥minconfidence，那么x?（l-x）成立。

 

算法4：从给定的频繁项目集中生成强关联规则

输入：频繁项目集；最小信任度minconf

输出：强关联规则。

Rule-generate (L, minconf )

（1）       FOR  each frequent itemset l_k in L

（2）       genrules（l_k , l_k）;

 

算法4的核心是genrules递归过程，它实现一个频繁项目集中所有强关联规则的生成。

算法5：递归测试一个频繁项目集中的关联规则

genrules（l_k: frequent k-itemset,  x_m: frequent m-itemset）

（1）X = { (m-1)-itemsets x_m-1 | x_{m-1 in xm} };

（2）FOR  each x_{m-1 in X  BEGIN}

（3）    conf = support（l_k）/ support（x_m-1）;

（4）    IF（conf≥minconf）THEN  BEGIN

（5）        print the rule “x_m-1?( l_k -x_m-1), with support = support (l_k), confidence = conf”;

（6）    IF （m-1>1） THEN  //generate rules with subsets of x_m-1 as antecedents

（7）    END

（8）END；

 

关联规则生成算法的优化问题主要集中在减少不必要的规则生成方面；

定理3：设项目集X，X₁是X的一个子集，如果规则X?（l-X）不是强规则，那么X₁?（l-X₁）一定不是强规则。

这个定理告诉我们，在生成关联规则尝试中可以利用已知的结果来有效避免测试一些肯定不是强规则的尝试。

定理4：设项目集X，X₁是X的一个子集，如果规则Y?X是强规则，那么规则Y? X₁一定是强规则。

这个定理告诉我们，在生成关联规则尝试中可以利用已知的结果来有效避免测试一些肯定是强规则的尝试。

 

3.3、Apriori算法的性能瓶颈问题

Apriori算法有两个致命的性能瓶颈：

（1）       多次扫描事务数据库，需要很大的I/O负载；

（2）       可能产生庞大的候选集。

 

3.4、Apriori算法的改进算法

为了提高Apriori算法的效率，出现了一系列改进算法，这些算法都是引入了相关技术，如数据分割、抽样等，在一定程度上改善了Apriori算法的适应性和效率。

 

3.4.1、基于数据分割（Partition）的方法

它的基本思想是，首先把大容量数据库从逻辑上分成几个互不相交的块，对每块应用挖掘算法生成局部的频繁项目集，然后把这些局部的频繁项目集作为候选的全局频繁项目集，通过测试它们的支持度来得到最终的全局频繁项目集。

 

该方法至少在两个方面有所提高：

（1）       合理利用主存空间；

（2）       支持并行挖掘算法。

 

该方法的理论基础可以通过下面的定理来保证：

定理5：设数据集D被分割成分块D₁、D₂、… 、D_n，全局最小支持度为minsupport，假设对应的最小支持数为minsup_count。如果一个数据分块D_i的局部最小支持数为minsup_conut_i的话，那么局部最小支持数minsup_conut_i应按如下方法生成：

minsup_conut_i = minsup_count *|| D_i || / || D ||

可以保证所有的局部频繁项目集成为全局频繁项目集的候选（即所有的局部频繁项目集涵盖全局频繁项目集）。

 

3.4.2、基于散列（hash）的方法

1995年，Park等提出了一个基于散列（hash）技术的产生频繁项目集的算法。由于寻找频繁项目集的主要计算是在生成2-频繁项目集L₂上，因此，Park等引入散列技术来改进产生2-频繁项目集的方法。但是，理论上说，这种方法可以扩展到产生k-项目集（k>2）中。

 

算法思想是，把扫描的项目放在不同的Hash桶中，每队项目最多只能在一个特定的桶中，这样可以对每个桶中的项目子集进行测试，减少了候选集生成的代价。

 

3.4.3、基于采样（sampling）的方法

1996年，Toivonen提出了一个基于采样技术产生频繁项目集的算法。

 

算法思想是：先使用数据库的抽样数据得到一些可能成立的规则，然后利用数据库的剩余部分验证这些关联规则是否正确。

 

从本质上说，使用一个抽样样本而不是使用整个数据集的原因是效率问题。但是，它的最大问题是抽样数据的选取以及由此而产生的结果偏差过大，即存在所谓的数据扭曲（Data Skew）问题。

 

3.5、对项目集空间理论的发展

随着数据库容量的增大，重复访问数据库将导致性能下降。因此目前的研究集中在一下几个方面：

（1）       探索新的关联规则挖掘理论：突破Apriori算法，利用新的理论生成新的算法。

（2）       提高裁减项目集格空间的效率：如Close算法。

（3）       分布和并行环境下的关联规则挖掘问题。

 

3.5.1、Close算法

1999年，Pasquier等提出了闭合项目集挖掘理论，并给出了基于这种理论的Close算法。实验证明，它对特殊数据是可以减少数据库扫描次数的。

 

Close算法基于这样的原理：一个频繁闭合项目集的所有闭合子集一定是频繁的；一个非频繁闭合项目集的所有闭合超集一定是非频繁的。

 

算法6：Close算法

（1）       generators in FCC₁ = { 1-itemsets }  //候选频繁闭合1-项目集

（2）       FOR （i=1;  FCC_i.grnerators = F;  i++） DO　BEGIN

（3）           closures in FCC_i = F;

（4）           supports in FCC_i = 0;

（5）           FCC_i = Gen_Closure (FCC_i)  //计算FCC的闭合

（6）           FOR all candidate closed itermsets c ? FCC_i  DO  BEGIN

（7）               IF(c.support ≥ minsupport)  THEN FC_i= FC_i∪{c}; 

         //修剪小于最小支持度的项

（8）           END

（9）           FCC_i+1 = Gen_Generator(FC_i);  //生成FCC_i+1

（10）   END

（11）   FC = ∪_iFC_i(FC_i.closure, FC_i.support);  //返回FC

（12）   Deriving frequent itemsets(FC, L);

 

函数Gen_Closure (FCC_i)产生候选的闭合项目集，用于频繁项目集的生成。

算法7：Gen_Closure函数

（1）       FOR  all transactions t?D  DO  BEGIN

（2）           Go = Subset (FCC_i.generator, t );

（3）           FOR  all generators p?Go  DO  BEGIN

（4）               IF (p.closure = F)  THEN  p.closure=t;

（5）               ELSE  p.closure = p.closure ∩t;

（6）               p.support++;

（7）           END

（8）       END

（9）       Answer = ∪{c? FCC_i  | c.closure ≠ F};

 

函数Gen_Generator(FC_i)实现Apriori算法的两个重要步骤：连接和修剪。

算法8：Gen_Generator函数

（1）       FOR  all generators p? FCC_i+1  DO　BEGIN

（2）           Sp = Subset(FC_i.generator, p);  //取得p的所有i-项目子集

（3）           FOR  all s?Sp  DO  BEGIN

（4）               IF(p?s.closure)  THEN  //如果p是它的i-项子集闭合的子集

（5）                   Delete p from FCC_i+1.generator;  //将它删除

（6）           END

（7）       END

（8）       Answer = ∪{c? FCC_i+1}

 

函数Deriving frequent itemsets(FC, L)通过频繁闭合项目集得到频繁项目集

算法9：Deriving frequent itemsets(FC, L)

（1）       k=0；

（2）       FOR  all frequent closed itemsets c? FC  DO  BEGIN

（3）           L_||c|| = L_||c||∪{c}  //按项的个数归类

（4）           IF（k<||c||） THEN  k=||c||;  //记下项目集包含的最多的个数

（5）       END

（6）       FOR (i=k; i>1; i--)  DO  BEGIN

（7）           FOR  all itemsets  c? L_i   DO

（8）               FOR  all (i-1)-subsets of c  DO  //分解所有（i-1）-项目集

（9）                   IF（s! ?L_i-1） THEN  BEGIN  //不包含在L_i-1中

（10）                   S.support = c.support;  //支持度不变

（11）                   L_i-1 =L_i-1 ∪{s};  //添加到L_i-1中

（12）               END

（13）   L = ∪L_i

 

3.5.2、FP-tree算法

2000年，Han等提出了FP-tree算法，这个算法只进行2次数据库扫描，不使用候选集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成关联规则。

 

FP-tree算法由两个步骤完成：

1、  利用事务数据库中的数据构造FP-tree。

FP-tree的构造过程中，将出现频度高的项目放在靠近根节点。

算法10：FP-tree构造算法

输入：事务数据库DB；最小支持度阀值Minsup

输出：FP-tree，简称T

Build_FP-tree (DB, Minsup, T)

（1）       扫描事务数据库DB一次，形成1-频繁项表L（按照支持度降序排列）；

（2）       创建T的根节点，以“root”标记。对于DB中的每个事务执行如下操作：对事务中的频繁项按照L中的顺序进行排序，排序后的频繁项表记为[p|P]，其中p是第一个元素,P是剩余元素的表。调用insert_tree([p|P], T)将此元组对应的信息加入到T中。

 

insert_tree是对数据库的一个元组对应的项目集的处理，它对排序后的一个项目集的所有项目进行递归式处理直到项目表为空。

算法11：insert_tree([p|P], T)

（1）       IF（T有子女N使得N.项名 = p.项名） THEN  N的计数加1；

（2）       ELSE 创建一个新结点N，将其计数设置为1，链接到它的父结点T，并且通过结点链结构将其链接到具有相同项名的结点；

（3）       如果p非空，递归地调用insert_tree( P, N )。

 

2、  从FP-tree中挖掘频繁模式的方法

用FP-tree挖掘频繁集的基本思想是分而治之，大致过程如下：

（1）       对每个项，生成它的条件模式基（一个“子数据库”，有FP-tree中与后缀模式一起出现的前缀路径集组成），然后是它的条件FP-tree；

（2）       对每个新生成的条件FP-tree，重复这个步骤；

（3）       直到FP-tree为空，或者只含有唯一的一个路径（此路径的每个子路径对应的项目集都是频繁集）。

 

算法12：在FP-tree中挖掘频繁模式

输入：构造好的FP-tree；事务数据库DB；最小支持度阀值Minsup

输出：频繁模式的完全集

方法：Call FP-growth（FP-tree, null）.

 

FP-growth通过递归调用方式实现频繁模式

算法13：FP-growth（Tree, a）

（1）IF（Tree只含单位路径P） THEN  FOR路径P中结点的每个组合（记为b） DO

     产生模式b∪a，其支持度support = b中结点的最小支持度；

（2）ELSE FOR each a_i在FP-tree的项头表（倒序） DO  BEGIN

（2-1）产生一个模式b=a_i∪a，其支持度support = a_i。support;

（2-2）构造b的条件模式基，然后构造b的条件FP-tree Tree b;

（2-3）if Tree b≠F  THEN  call FP-growth(Tree b, b);

 

3.6、项目集格空间和它的操作

3.6、3.7是本书作者提出的一种关联规则挖掘的新理论，原始文献为：

毛国君，刘椿年。基于项目集格操作的关联规则挖掘算法。计算机学报，第25卷，第4期。2002。

 

为了重复利用对数据库的扫描信息，把来自数据库的信息组织成项目集格（Set of Itemsets）形式，并且对项目集格及其操作代数化。

 

定义5：（项目集格）一个项目集格空间可以用三元组（I，S，p）来刻画，其含义如下：

项目定义域I：I = {i₁, i₂, … , i_m}为所涉及项目的定义范围；

项目集变量集S：S中的每个项目集变量形式为ISS = {IS₁, IS₂, … , IS_n}，其中IS_i是定义在I上的项目集；

操作p：关于S中的项目集变量的操作集。

 

定义6：（项目集格上的集合操作）项目集间（上）的属于（?）、包含（?）、并（U）、交（∩）、差（-）等操作和普通的集合操作相同。

 

定义7：（项目集上的亚操作）设ISS₁和ISS₂是定义在I上的来两个项目集的集合，IS是定义在I上的一个项目集，定义如下操作：

亚属于（?_sub）：IS_I ?_subSS₁当且仅当$IS₁?ISS₁，使得IS?IS₁；

亚包含（? _sub）：ISS₁ ? _sub ISS₂ 当且仅当"IS₁? ISS₁? IS₁?_sub ISS₂；

亚交（∩_sub）：ISS₁∩_sub ISS₂ = {IS | IS?_sub ISS₁且IS?_sub ISS₂}；

亚并（U _sub）：ISS₁ U _sub ISS₂ = {IS | IS?_sub ISS₁或IS?_sub ISS₂}；

 

亚操作的性质：类似集合间的性质，不难理解。

 

3.7、基于项目集操作的关联规则挖掘算法

3.7.1、关联规则挖掘空间

定义8：（关联规则挖掘空间）关联规则挖掘空间定义为一个五元组W=（I，D，O，U，R），其含义如下：

I = {i₁, i₂, … , i_m}，为W所涉及的全体项目；

D = {t₁, t₂, … , t_n},为W所基于的事务数据库；

O = {o₁, o₂, … , o_k},为W上关于D的元素的操作集合；

U = {u₁, u₂, … , u_p},为W上用户给定的限制参数及约束条件；

R = {r₁, r₂, … , r_q},为D中所蕴含的关联规则集。

 

3.7.2、三个实用算子

定义9：（考虑支持度下的项目集加入项目集格的操作）一个项目集IS加入项目集格ISS的操作算子join（IS，ISS）描述为：

（1）       项目集格为ISS = ISS_原U {IS};

（2）       IS在ISS中的支持度按如下方法给出：

如果IS?ISS_原，则sup_conut(IS) = 1;

如果IS?ISS_原，则sup_conut(IS)++。

算法14：join(IS, ISS)

（1）       sup_count(IS) = 1; flog = 0;

（2）       FOR  all  IS₁?ISS  DO

（3）           IF  IS = IS₁  THEN BEGIN

（4）               sup_count(IS₁)++;

（5）               Flag = 1;

（6）           END

（7）       IF flag = 0 THEN ISS = ISS U {IS}

 

定义10（频繁项目集格生成操作）利用IS在ISS中挑选频繁项目集并加入到频繁项目集格ISS^*的操作算子make_fre(IS, ISS, ISS^*)描述为：

" ISS^*?_sub {IS}，如果IS^*的支持数≧minsup_count，则IS^*可能作为频繁项目集加入ISS^*中。

算法15：make_fre(IS, ISS, ISS^*)

（1）       FOR  all IS^*?_sub{IS}  DO  BEGIN

（2）           sup_count(IS^*) = 0;

（3）           FOR  all IS^**?ISS  DO

（4）               IF IS^* ?IS^**  THEN

（5）                   sup_count(IS^*) += sup_count(IS^**);

（6）           IF sup_count(IS^*) ≧ minsup_count  THEN

（7）               IF IS^*?_sub ISS^*  THEN BEGIN

（8）                   prune (IS^*, ISS^*);   //把不需要的项目集从ISS^*中裁减掉

（9）                   ISS^* = ISS^* U {IS^*}

（10）           END

（11）       prune(IS^*, ISS);  //把不需要的项目集从ISS中裁减掉

（12）   END

 

定义11：（频繁项目集格的裁减操作）利用项目集IS₁裁减项目集格ISS₁的操作算子prune（IS₁，ISS₁）描述为：

对"IS?ISS₁，如果IS?_sub{IS₁}，把IS从ISS₁中剔除。

算法16：prune（IS₁，ISS₁）

（1）       FOR  all IS?ISS₁  DO

（2）           IF IS?_sub{IS₁} THEN  ISS₁ = ISS₁ - {IS}；

 

3.7.3、最大频繁项目集格的生成算法

算法17：ISS-DM  Algorithm(最大频繁项目集生成算法)

输入：数据库D

输出：最大频繁项目集格ISS^*

（1）       Input(minsup_count);

（2）       ISS?F; ISS^*?F;

（3）       FOR  all IS?D  DO  BEGIN  //取D的一个项目集IS

（4）           join（IS，ISS）；

（5）           make_fre(IS, ISS, ISS^*);

（6）       END

（7）       Answer = ISS^*;

 

3.8、改善关联规则挖掘质量问题

衡量关联规则挖掘结果的有效性应该从多种综合角度来考虑：

（1）       准确性；

（2）       实用性；

（3）       新颖性；

可以在用户主观和系统客观两个层面上考虑关联规则挖掘的质量问题。

 

在用户主观层面上，约束数据挖掘可以为用户参与知识发现工作提供一种有效的机制。

在系统客观层面上，除了使用“支持度-可信度”的关联规则挖掘度量框架外，还需要研究引入新的度量机制。

 

3.9、约束数据挖掘问题

3.9.1、约束在数据挖掘中的作用

（1）聚焦挖掘任务，提高挖掘效率；

（2）保证挖掘的精确性；

（3）控制系统的使用规模。

 

3.9.2、约束的类型

1、单调性约束（Monotone Constraint）

定义15：所谓一个约束Cm是单调性约束是指满足Cm的任何项目集S的超集也能满足Cm。

 

2、反单调性约束（Anti-monotone Constraint）

定义16：约束Ca是反单调约束是指对于任意给定的不满足Ca的项目集S，不存在S的超集能够满足Ca。

 

3、  可转变的约束（Convertible Constraint）

定义17：如果一个约束C满足下面的条件，那么称它为反单调可转变的：

（1）       C（S）既不是单调性约束，也不是反单调性约束；

（2）       若存在顺序R，使得经R排序后的I满足：任给S^*?{suffix_S}，有C（S）?C(S^*)。

 

定义18：如果一个约束C满足下面的条件，那么称它为单调可转变的：

（1）       C（S）既不是单调性约束，也不是反单调性约束；

（2）       若存在顺序R，使得经R排序后的I满足：任给S^*?{suffix_S}，有C（S^*）?C(S)。

 

4、  简洁性约束（Succinct Constraint）

没看懂。

 

3.10、时态约束关联规则挖掘

参考资料：

毛国君，刘椿年。时态约束下的数据挖掘问题与算法。电子学报，2003，Vol.31，No.11:1690～1694

欧阳为民，蔡庆生。在数据库中发现具有时态约束的关联规则。软件学报，1999。Vol.10，NO.5

 

时态约束可以起到过滤过时数据、聚焦用户目标以及加速形成关联规则生成等作用。

 

3.11、关联规则挖掘中的一些更深入的问题

3.11.1、多层次关联规则挖掘

根据规则中涉及的层次，多层次关联规则可以分为同层次关联规则和层间关联规则：

如果一个关联规则对应的项目是在同一个粒度层次上，那么它是同层关联规则；

如果一个关联规则对应的项目是在不同的粒度层次上，那么它是层间关联规则。

 

目前，多层次关联规则挖掘的度量方法基本沿用了“支持度-可信度”的框架，对支持度的设置一般有两种：

（1）       统一的最小支持度；

（2）       不同层次使用不同的最小支持度。

 

多层次关联规则挖掘方法有以下几种：

（1）       自上而下方法：先找高层规则，再找它的下一层规则；

（2）       自下而上方法：

（3）       在一个固定层次上挖掘：

 

3.11.2、多维关联规则挖掘

在OLAP中挖掘多维、多层关联规则是一个很自然的过程。

有两种常见形式：

（1）       维内的关联规则；

（2）       混合维关联规则。

 

3.11.3、数量关联规则挖掘

对于数值型的数据而言，在处理方法、技术和难度上都和布尔关联规则有差距，因此需要针对相关问题进行专门讨论。

目前数量关联规则挖掘问题重要集中在以下三个方面：

（1）       连续数值属性的处理：

两种基本方法：离散化方法；统计或模糊方法。

（2）       规则的优化：

对产生的大量冗余规则进行优化，找出用户真正感兴趣的规则集。

（3）       提高挖掘效率：

 

3.12、数量关联规则挖掘方法

目前对数量关联规则挖掘的研究主要基于两条技术路线：

（1）       通过对比较成熟的布尔关联规则算法的改进来解决数量关联规则问题；

（2）       用一种全新的思路和算法来解决数量关联规则挖掘问题。

讨论比较多和比较成熟的是第一种方法。