数据挖掘CHAPTER6挖掘大型数据库中的关联规则(4)

（即，buys）的多次出现（即，谓词在规则中出现多次）。正如我们在本章的前几节看到的，这种规则通常由事务数据挖掘。

然而，假定不是使用事务数据库，销售和相关数据存放在关系数据库或数据仓库中。根据定义，这种存储是多维的。例如，除记录购买的商品之外，关系数据库可能记录与商品有关的其它属性，如购买数量，或价格，或销售分店的地址。另外，关于购物顾客的信息，如顾客的年龄、职业、信誉度、收入和地址等也可能存储。将数据库的每个属性或数据仓库的每个维看作一个谓词，这样就能挖掘多维关联规则，如

age(X,\20...29\)?occupation(X,\student\)?buys(X,\laptop\) (6.12)

涉及两个或多个维或谓词的关联规则称为多维关联规则。规则(6.12)包含三个谓词（age, occupation和buys），每个在规则中仅出现一次。因此，我们称它具有不重复谓词。具有不重复谓词的关联规则称作维间关联规则。我们也对挖掘具有重复谓词的关联规则感兴趣。这种规则包含某些谓词的多次出现，称作混合维关联规则。这种规则的一个例子是规则(6.13)，其中谓词buys是重复的。

age(X, “20...29”) ? buys(X, “laptop”) ? buys(X, “b/w printer”) (6.13)

注意，数据库属性可能是分类的或量化的。分类属性具有有限个不同值，值之间无序（例如，occupation, brand, color）。分类属性也称标称属性，因为它们的值是“事物的名字”。量化属性是数值的，并在值之间具有一个蕴涵的序（例如，age, income, price）。挖掘多维关联规则的技术可以根据量化属性的处理分为三类。

第一种方法，使用预定义的概念分层对量化属性离散化。这种离散化在挖掘之前进行。例如，income的概念分层可以用于以区间值，如“0...20K”、“21...30K”、“31...40K”等，替换属性的原来的数值值。这里，离散化是静态的、预确定的。离散化的数值属性具有区间值，可以象分类属性一样处理（每个区间看作一类）。我们称这种方法为使用量化属性的静态离散化挖掘多维关联规则。

第二种方法，根据数据的分布，将量化属性离散化到“箱”。这些箱可能在挖掘过程中进一步组合。离散化的过程是动态的，以满足某种挖掘标准，如最大化所挖掘的规则的置信度。由于该策略将数值属性的值处理成量，而不是预定义的区间或分类，由这种方法挖掘的关联规则称为量化关联规则。

第三种方法，量化属性离散化，以紧扣区间数据的语义。这种动态离散化过程考虑数据点之间的距离。因此，这种量化关联规则称作基于距离的关联规则。

让我们逐个研究这些挖掘多维关联规则方法。为简明起见，我们将讨论限于维间关联规则。注意，不是搜索频繁项集（象单维关联规则挖掘那样），在多维关联规则挖掘中，我们搜索频繁谓词集。k-谓词集是包含k个合取谓词的集合。例如，规则(6.12)中的谓词集{age, occupation, buys}是3-谓词集。类似于项集使用的记号，我们用Lk表示频繁k-谓词集的集合。 6.4.2 使用量化属性的静态离散化挖掘多维关联规则

在这种情况下，量化属性使用预定义的概念分层，在挖掘之前离散化，数值属性的值用区间替代，如果期望的话，分类属性可以泛化到较高的概念层。如果任务相关的结果数据存放在关系表中，则Apriori算法只需要稍加修改就可以找出所有的频繁谓词，而不是频繁项集（即，通过搜索所有的相关属性，而不是仅搜索一个属性，如buys）。找出所有的频繁k-谓词将需要k或k+1次表扫描。其它策略，如散列、划分和选样可以用来改进性能。

替换地，变换后的任务相关的数据可以存放在数据方中。数据方很适合挖掘多维关联规则，由于根据定义，它们是多维的。数据方和它们的计算已在第2章详细讨论。回顾一下，数据方由方体的格组成，方体是多维数据结构。这种结构可以存放任务相关的数据，以及聚集、分组信息。图6.17给出了一个方体的格，定义维age, income和buys的数据方。n-维方体的单元用于存放对应n-谓词集的计数或支持度。基本方体按age, income和buys聚集了任务相关的数据；2-D方体(age, income)按age和income聚集；0-D（顶点）方体包含任务相关数据中事务的总数，等等。

图6.17 方体的格，形成3-D数据方。每个方体代表一个不同

分组。基本方体包含三个谓词age, income和buys

由于数据仓库和OLAP技术的日益增长的使用，包含用户感兴趣的维的数据方可能已经存在，并完全物化。“如果是这种情况，我们如何去找频繁谓词集？”可以使用一种类似于Apriori所用的策略，基于先验知识：频繁谓词集的每个子集也必须是频繁的。这个性质可以用于减少产生的谓词集候选数量。

在没有挖掘任务相关数据方存在时，必须创建。第2章介绍了数据方快速、有效计算的算法。这些算法可以修改，在数据方构造时搜索频繁项集。 6.4.3 挖掘量化关联规则

量化关联规则是多维关联规则，其中数值属性动态离散化，以满足某种挖掘标准，如最大化挖掘规则的置信度或紧凑性。在本小节，我们将特别关注如何挖掘左部有两个量化属性，右部有一个分类属性的量化关联规则，例如

Aquan1?Aquan2?Acat 其中，Aquan1和Aquan2是在量化属性的区间（其中，区间动态地确定）上测试，Acat测试任务相关数据的分类属性。这种规则称作2-维量化关联规则，因为它们包含两个量化维。例如，假定我们关心象age和income这样的量化属性对和这样的顾客喜欢什么类型的电视机之间的关联关系。这种2-D量化关联规则的一个例子是

age(X,”30...39”) ? income(X ,”42K...48K”) ? buys(X,”high resolution TV”) (6.15)

“如何找出这种规则？”让我们看看系统ARCS（Association Rule Clustering System，关联规则聚类系统）使用的方法，其思想源于图形处理。本质上，该方法将量化属性对映射到满足给定分类属性条件的2-D栅格上。然后，搜索栅格点的聚类，由此产生关联规则。下面是ARCS涉及的步骤：

分箱。量化属性可能具有很宽的取值范围，定义它们的域。如果我们以age和income为轴，每个age的可能值在一个轴上赋予一个唯一的位置；类似地，每个income的可能值在另一个轴上赋予一个唯一的位置；想想2-D栅格会有多么大！为了使得栅格压缩到可管理的尺寸，我们将量化属性的范围划分为区间。这些区间是动态的，在挖掘期间它们可能进一步合并。这种划分过程称作分箱；即，区间被看作“箱”。三种常用的分箱策略是：

? 等宽分箱：每个箱的区间长度相同，

? 等深分箱：每个箱赋予大致相同个数的元组，和

? 基于同质的分箱：箱的大小这样确定，使得每个箱中的元组一致分布。

在ARCS中，使用等宽分箱，每个量化属性的箱尺寸由用户输入。对于涉及两个量化属性的每种可能的箱组合，创建一个2-D数组。每个数组单元存放规则右部分类属性每个可能类的对应的计数分布。通过创建这种数据结构，任务相关的数据只需要扫描一次。基于相同的两个量化属性，同样的2-D数组可以用于产生分类属性的任何值的规则。分箱在第3章也进行了讨论。

找频繁谓词集。一旦包含每个分类计数分布的2-D数组设置好，就可以扫描它，以找出也满足最小置信度的频繁谓词集（满足最小支持度）。然后，使用类似于6.2.2小节介绍的规则产生算法，由这些谓词集产生关联规则。

关联规则聚类。将上一步得到的强关联规则映射到2-D栅格上。图6.18显示给定量化属性age和income，预测规则右端条件buys(X,”high resolution TV”)的2-D量化关联规则。四个“?”对应于规则

age(X,34) ? income(X,”31K...40K”) ? buys(X,”high resolution TV”) (6.15) age(X,35) ? income(X,”31K...40K”) ? buys(X,”high resolution TV”) (6.16) age(X,34) ? income(X,”41K...50K”) ? buys(X,”high resolution TV”) (6.17) age(X,35) ? income(X,”41K...50K”) ? buys(X,”high resolution TV”) (6.18)

“我们能找到一个更简单的规则替换上面四个规则吗？”注意，这些规则都相当“接近”，在栅格中形成聚类。的确，这些规则可以组合或“聚”在一起，形成下面的规则(6.19)，它更简单，将上面四个规则汇总在一起，并取代它们。

age(X,”34...35”) ? income(X,”31K...50K”) ? buys(X,”high resolution TV”) (6.20)

ARCS使用聚类算法做这件事。该算法扫描栅格，搜索规则的矩形聚类。用这种方法，出现在规则聚类中的量化属性的箱可能进一步合并，从而对量化属性动态地离散化。

图6.18 表示购买高分辨TV的顾客元组的2-D栅格

这里介绍的基于栅格的技术假定初始关联规则可以聚集到矩形区域。在进行聚集前，可以使用平滑技术，帮助消除数据中噪音和局外者。矩形聚类可能过分简化数据。已经提出了一些替换技术，基于其它形状的区域，看来能够更适合数据，但需要更大的计算量。

已经提出了一种非基于栅格的技术，发现更一般的关联规则，其中任意个数的量化属性和分类属性可以出现在规则的两端。在这种技术下，量化属性使用等深分箱动态划分，划分根据部分完全性度量组合，该度量量化由于划分而导致的信息丢失。关于这些ARCS替代方法的引文，参见文献注释。

6.4.4 挖掘基于距离的关联规则

前一小节我们介绍了量化关联规则，其量化属性开始用分箱的方法离散化，然后将结果区间组合。然而，这种方法可能不能紧扣区间数据的语义，因为它未考虑数据点之间或区间之间的相对距离。

例如，考虑表6.3中属性price的数据，根据等宽和等深分箱与基于距离的划分对比。基于距离的划分看来最直观，因为它将接近的值分在同一区间内（例如，[20, 22]）。相比之下，等深划分将很远的值放在一组（例如，[22, 50]）。等宽划分可能将很近的值分开，并创建没有数据的区间。显然，基于距离的划分既考虑稠密性或区间内的点数，又考虑一个区间内点的“接近性”，这帮助产生更有意义的离散化。每个量化属性的区间可以通过聚集该属性的值建立。

关联规则的一个缺点是它们不允许近似的属性值。考虑关联规则

item_type(X,”electronic”) ? manufacture(X,”foreign”) ? price(X,$200) (6.20)

在现实中，更可能的是国外的电子产品的价格大约$200，而不是恰好$200。使得关联规则可以表达这种接近性是有用的。注意，支持度和置信度度量不考虑属性值的接近性。这导致基于距离的关联规则挖掘。这种规则紧扣区间数据的语义，并允许数据值的近似。一个两遍算法可以用于

挖掘基于距离的关联规则。第一遍使用聚类找出区间或聚类。第二遍搜索频繁地一起出现的聚类组得到基于距离的关联规则。

表6.3 分箱方法，如等宽和等深，不能总是紧扣区间数据的语义

price($) 7 20 22 50 51 53 等宽 （宽度$10） 等深 （深度2） 基于距离 [7,7] [20,22] [50,53] [0,10] [11,20] [21,30] [31,40] [41,50] [51,60] [7,20] [22,50] [51,53] “如何在第一遍形成聚类？”这里，我们给出如何形成聚类的直观介绍。感兴趣的读者可以阅读第8章，以及本章文献注释中给出的关于基于距离的关联规则的引文。设S[X]是N个元组t1, t2 ,..., tN投影到属性集X的集合。定义一个直径度量，评估元组的接近性。S[X]的直径是投影到X的元组两两距离的平均值。距离度量可以使用诸如欧几里德距离或曼哈坦距离8。S[X]的直径越小，其元组投影到X上时越接近。因此，直径度量评估聚类的稠密性。聚类CX是定义在属性集X上的元组的集合；其中，元组满足稠密度阈值和频繁度阈值。频繁度阈值限定聚类中元组的最少个数。聚类方法，如第8章介绍的那些，可以修改，用于该挖掘过程的第一遍。

第二遍，将聚类组合，形成基于距离的关联规则。考虑一个简单的形如CX ? CY的基于距离的关联规则。假定X是属性集{age}，而Y是属性集{income}。我们想确保age的聚类CX和income的聚类CY之间的蕴涵是强的。这意味当age聚类的元组投影到属性income上时，它们对应的值落在income聚类CY之内，或接近它。聚类CX投影到属性集Y上记作CX[Y]。这样，CX[Y]和CY[Y]之间的距离必须很小。该距离度量CX和CY之间的关联程度。CX[Y]和CY[Y]之间的距离越小，CX和CY之间的关联程度越强。关联程度度量可以使用标准统计度量定义，如平均内聚类距离，质心曼哈坦距离。其中，聚类的质心代表聚类的“平均”元组。

一般地，可以组合聚类，找出如下形式的基于距离的关联规则

CX1CX2...CXx?CYCY2...CYy

1其中，Xi和Yj是两两不相交的属性集，并满足以下三个条件：（1）规则前件的每个聚类与后件的每个聚类是强关联的；（2）前件中的聚类一起出现；（3）后件中的聚类一起出现。关联程度取代了非基于距离的关联规则框架下的置信度，而稠密度阈值取代了支持度。

6.5 由关联挖掘到相关分析

“挖掘了关联规则之后，数据挖掘系统如何指出哪些规则是用户感兴趣的？”大部分关联规则挖掘算法使用支持度-置信度框架。尽管使用最小支持度和置信度阈值排除了一些无兴趣的规则的探查，仍然会产生一些对用户来说不感兴趣的规则。本节，我们首先看看即便是强关联规则为何也可能是无兴趣的并可能误导；然后，讨论基于统计独立性和相关分析的其它度量。 6.5.1 强关联规则不一定是有趣的：一个例子

“在数据挖掘中，所有的强关联规则（即，满足最小支持度和最小置信度阈值）都有兴趣，值得向用户提供吗？”并不一定。规则是否有兴趣可能用主观或客观的标准来衡量。最终，只有用户能够确定规则是否是有趣的，并且这种判断是主观的，因不同用户而异。然而，根据数据“支持”的统计，客观兴趣度度量可以用于清除无兴趣的规则，而不向用户提供。

“我们如何识别哪些强关联规则是真正有兴趣的？”让我们考查下面的例子。 8

两个元组t1=(x11,x12,...,x1m)和t2=(x21,x22,...,x2m)之间的欧几里德距离和曼哈坦距离分别是

Euclidean_d(t1,t2)??m(x1ii?1?x2i)和Manhattan_d (t1,t2)??|x1i?x2i|。

i?12m例6.6 假定我们对分析AllElectronics的事务感兴趣，涉及计算机游戏和录像。设事件game表示包含计算机游戏的事务，而video表示包含录像的事务。在所分析的10,000个事务中，数据显示6000个顾客事务包含计算机游戏，7500个事务包含录像，而4000个事务包含计算机游戏和录像。假定发现关联规则的数据挖掘程序在该数据上运行，使用最小支持度30%，最小置信度60%。将发现下面的关联规则

buys(X,\computergames\)?buys(X,\videos\)4,00010,000

4,0006,000[support = 40%,confidence = 66%] (6.21)

规则(6.21)是强关联规则，因而向用户报告，因为其支持度为

?40%，置信度为

?

66%，分别满足最小支持度和最小置信度阈值。然而，规则(6.21)是误导，因为购买录像的可能性是75%，比66%还大。事实上，计算机游戏和录像是负相关的，买一种实际上减少了买另一种的可能性。不完全理解这种现象，可能根据导出的规则作出不明智的决定。? 上面的例子也表明规则A ? B的置信度有一定的欺骗性，它只是给定A，B的条件概率的估计。它并不度量A和B之间蕴涵的实际强度。因此，寻求支持度-置信度框架的替代，对挖掘有趣的数据联系可能是有用的。 6.5.2 由关联分析到相关分析

使用支持度-置信度框架的关联规则挖掘对于许多应用是有用的。然而，支持度-置信度框架可能误导，当A的出现事实上并不蕴涵B的出现时，识别出A ? B是有趣的。本小节，我们考虑一种替代框架，根据相关性挖掘数据项之间有趣的联系。

项集A的出现独立于项集B的出现，如果P(A ? B) = P(A)P(B)；否则，项集A和B是依赖的和相关的。这个定义容易推广到多于两个项集。A和B的出现之间的相关性通过计算下式度量

P(A?B) (6.22)

P(A)P(B)如果(6.22)式的值小于1，则A的出现和B的出现是负相关的。如果结果值大于1，则A和B是正相关的，意味每一个的出现都蕴涵另一个的出现。如果结果值等于1，则A和B是独立的，它们之间没有相关性。

让我们回头看例6.6计算机游戏和录像。

例6.7 为了帮助过滤掉形如A ? B的误导的“强”关联，我们需要研究两个项集A和B怎样才是相关的。设game表示例6.6中不包含计算机游戏的事务，video表示不包含录像的事务。事务可以汇总在相依表中。例6.6的数据的相依表如表6.4所示。由该表可以看出，购买计算机游戏的概率P({game}) = 0.60，购买录像的概率P({video}) = 0.75，而购买二者的概率P({game, video}) = 0.40。根据(6.22)式，P({game, video}) / (P({game}) ? P({video})) =0.40 / (0.75?0.60) = 0.89。由于该值明显比1小，{game}和{video}之间存在负相关。分子是顾客购买二者的可能性，而分母是如果两个购买是完全独立的可能性。这种负相关不能被支持度-置信度框架识别。?

表6.4 汇总关于购买计算机游戏和录像事务的2 ? 2相依表

video

game 4,000 2,000

6,000

game

3,500 500 4,000

?row 7,500 2,500 10,000

video

?col

这激发了识别相关性规则或相关规则的挖掘。相关规则形如{i1, i2, ..., im}，其中，项{i1, i2 ,..., im}的出现是相关的。给定由(6.22)式确定的相关值，?2统计可以确定相关是否是统计意义上的相关。?2统计也可以确定负蕴涵。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据挖掘CHAPTER6挖掘大型数据库中的关联规则(4)在线全文阅读。