相关性的一个优点是它是向上封闭的。这意味,如果项集S是相关的(即,S中的项是相关的),则S的超集也是相关的。换句话说,添加项到相关集合中,不影响已存在的相关性。?2统计在每个有意义的层也是向上封闭的。
在搜索相关集,形成相关规则时,可以使用相关性和?2的向上封闭性。由空集开始,考察项集空间(或项集的格),一次添加一个项,寻找最小相关项集——相关的项集,其子集都不相关。这些项集形成格的边界。由于封闭性,边界以下的项集都不是相关的。由于最小相关项集的所有超集都是相关的,我们可以停止向上搜索。在项集空间进行这种一系列“行走”的算法称作随机行走算法。这种算法可以与支持度测试结合,以进行进一步的剪枝。随机行走算法容易使用数据方实现。将这里介绍的过程用于超大规模数据库是一个尚待解决的问题。另一个限制是,当相依表数据稀疏时,?2统计不够精确,并且对于大于2 ? 2相依表可能误导。替代支持度-置信度框架评估关联规则兴趣度的提议在文献注释中给出。
6.6 基于限制的关联挖掘
对于给定的任务相关的数据集,数据挖掘过程可能发现数以千计的规则,其中许多用户并不感兴趣。在基于限制的挖掘中,挖掘在用户提供的各种限制的指导下进行。这些限制包括
? ? ? ? ?
知识类型限制:指定要挖掘的知识类型,如关联规则。 数据限制:指定任务相关的数据集。
维/层限制:指定所用的维或概念分层结构的层。
兴趣度限制:指定规则兴趣度阈值或统计度量,如支持度和置信度。
规则限制:指定要挖掘的规则形式。这种限制可以用元规则(规则模板)表示,如可以出现在规则前件或后件中谓词的最大或最小个数,或属性、属性值和/或聚集之间的联系。
以上限制可以用高级数据挖掘查询语言说明,如用第4章介绍的语言。
上面的前4种限制已在本书或本章的前面讨论。本节,我们讨论使用规则限制对挖掘任务聚焦。这种基于限制的挖掘允许用户根据他们关注的目标,说明要挖掘的规则,因此使得数据挖掘过程更有功效。此外,可以使用复杂的挖掘查询优化程序,以便利用用户指定的限制,从而使得挖掘过程更有效率。基于限制的挖掘促进交互式探查挖掘与分析。在6.6.1小节,你将学习元规则制导的挖掘,那里用规则模板的形式说明了语法规则限制。6.6.2小节讨论进一步的规则限制使用,指定集合/子集联系、变量的常量初始化和聚集函数。 6.6.1 关联规则的元规则制导挖掘
“元规则有什么作用?”元规则使得用户可以说明他们感兴趣的规则的语法形式。规则的形式可以作为限制,帮助提高挖掘过程的性能。元规则可以根据分析者的经验、期望或对数据的直觉,或者根据数据库模式自动产生。
例6.8 假定作为AllElectronics的市场分析员,你已经访问了描述顾客的数据(如,顾客的年龄、地址和信誉度等),以及顾客事务的列表。你对找出顾客的特点和他购买的商品之间的关联关系感兴趣。然而,不是要找出反映这种联系的所有关联规则,你特别对什么样的一对顾客特点促进教育软件的销售感兴趣。可以使用一个元规则来说明你感兴趣的规则形式。这种元规则的一个例子是
P1(X,Y) ? P2(X,W) ? buys(X,”education software”) (6.23)
其中,P1和P2是谓词变量,在挖掘过程中被例示为给定数据库的属性;X是变量,代表顾客;Y和W分别取赋给P1和P2的属性值。典型地,用户要说明一个例示P1和P2需考虑的属性列表;否则,将使用省缺的属性集。
一般地,元规则形成一个关于用户希望探查或证实的、他感兴趣联系的假定。然后,挖掘系统可以寻找与给定元规则匹配的规则。例如,规则(6.24)匹配或遵守元规则(6.23)。
age(X,”30...39”) ) ? income(X,”41...60K”) ? buys(X,”education software”) (6.24)
?
“元规则如何用于指导挖掘过程?”让我们进一步考察这个问题。假定我们希望挖掘维间关联规则,如上例所示。元规则是形如
P1 ? P2 ?...? Pl ? Q1 ? Q2 ?...? Qr (6.31)
的规则模板。其中,Pi (i = 1, 2 ,..., l) 和Qj (j = 1, 2, ...,r )是例示谓词或谓词变量。设元规则中谓词的个数为p = l + r。为找出满足该模板的维间关联规则
? ?
我们需要找出所有的频繁p-谓词集Lp。
我们还必须有Lp中的l-谓词子集的支持度或计数,以计算由Lp导出的规则的置信度。
这是挖掘多维关联规则的典型情况,我们在6.4节已介绍。正如在那里看到的,数据方很适合多维关联规则的挖掘,因为它们具有存放聚集维值的能力。由于数据仓库和OLAP技术的流行,适合给定挖掘任务的、完全物化的n-D数据方可能已经存在。这里,n是被考虑的对谓词变量例示的属性数,加上在给定元规则中已经例示的谓词数,并且n ? p。通常,这种n-D数据方用方体的格表示,类似于图6.17中的那种。在这种情况下,我们只需要扫描p-D方体,将每个单元中的计数与最小支持度计数比较,以找出Lp。由于l-D方体已经计算,并包含Lp的l-D谓词子集的计数,然后调用规则产生过程,返回与元规则匹配的强规则。我们称这种方法为缩减的n-D方体搜索,因为它只考察p-D和l-D方体,而不是搜索整个n-D数据方。
如果用于元规则制导的挖掘任务的n-D数据方不存在,我们必须构造和搜索它。只需要计算p-D和l-D方体,而不是整个数据方。数据方的构造方法已在第2章讨论。 6.6.2 用附加的规则限制制导的挖掘
用户可以说明集合/子集联系,变量的常量初始化和聚集函数。这些可以与元规则制导的挖掘一起使用,或作为它的替代。本节,我们考察规则限制,看看怎样使用它们,使得挖掘过程更有效。让我们研究一个例子,其中规则限制用于挖掘混合维关联规则。
例6.9 假定AllElectronics有一个销售多维数据库,包含以下相互关联的关系:
? ? ? ?
sales(customer_name, item_name, transaction_id) lives(customer_name, region, city) item(item_name, category, price)
transaction(transaction_id, day, month, year)
其中,lives, item和transaction是三个维表,通过三个关键字customer_name, item_name和transaction_id分别链接到事实表sales。
我们的关联挖掘查询是“找出这样的销售,对于Vancouver的1999年的顾客,什么样的便宜商品(价格和低于$100)能够促进同类贵商品(最低价为$500)的销售?”该查询可以用DMQL数据挖掘查询语言表达如下。为方便讨论,查询的每一行已经编号。
(1) mine associations as (2) lives(C,_, “vancouver”) ? sales+(C,?{I},{S})? sales+(C,?{J},{T}) (3) from sales
(4) where S.year = 1999 and T.year = 1999 and I.category = J.category (5) group by C,I.category
(6) having sum(I.price) < 100 and min(J.price)?500 (7) with support threhold = 1% (8) with confidence threhold = 50%
在讨论规则限制之前,让我们仔细看看上面的查询。行1是知识类型限制,说明要发现关联模式。行2说明了元规则。这是下面混合维关联规则(多维关联规则,其中重复谓词是sales)的元规则的缩写形式:
lives(C,_,\Vacouver\)?sales(C,?I1,S1)?...?sales(C,?Ik,Sk)?I?{I1,...,Ik}?S?{S1,...,Sk) ?sales(C,?J1,T1)?...?sales(C,?Jm,Tm)?J?{J1,...,Jm}?T?{T1,...,Tm)这意味一个或多个sales记录以“sales(C,?I1,S1) ? ... ? sales(C,?Ik,Sk) ” 形式驻留在规则的前件(左部),问号“?”表示只有项的名字I1 ,..., Ik需要打印。“I={ I1 ,..., Ik }”意味出现在前件的所有的I取集合形式,由行4的类SQL的where-子句得到。类似的记号用于后件(右端)。
该元规则可能允许类似于下面的关联规则产生
lives(C,_,\Vancouver\)?sales(C,\Census_CD\,_)?sales(C,\MS/Office\,_)?sales(C,\MS/SQLServer\,_),[1.5%,68%] (6.26)
该规则意味, 如果顾客住在Vancouver,买了“Census_CD”和“MS/Office”,他多半会买“MS/SQLServer”(概率68%),并且所有顾客的1.5%买这三样。
数据限制在元规则的“lives(_,_,”Vancouver”)”部分指定(即,住在Vancouver的所有顾客),并在行3指出只有事实表sales需要显示引用。在多维数据库中,变量的引用被简化。例如,“S.year=1999”等价于SQL语句“from sales S, transaction R where S.transaction_ID = R.transaction_ID and R.year = 1999”。所有三个维(lives, item和transaction)都使用。层限制如下:对于lives,我们只考虑customer_name,因为只有city = “Vancouver”在选择中使用;对于item,我们考虑item_name和category,因为它们在查询中使用;对于transaction,我们只考虑transaction_ID,因为day和month未被引用,而year只在选择中使用。
规则限制包含在where(行4)和having(行6)子句的大部分,如“S.year = 1999”、 “T.year = 1999”、“ I.category = J.category”、“sum(I.price) < 100 ”和“min(J.price) ? 500”。最后,行7和8说明了两个兴趣度限制(即,阈值):1%的最小支持度和50%的最小置信度。? 知识类型和数据限制在挖掘前使用。其它类型的限制可以在挖掘后使用,以便过滤发现的规则。然而,这可能使得挖掘过程非常低效,代价昂贵。维/层限制在6.3.2小节已讨论,而兴趣度限制在本章已广泛讨论。现在,让我们把注意力放在规则限制上。
“什么类型的规则限制可以在挖掘过程中使用,以缩小规则搜索空间?”你可能会问。“更特殊地,什么类型的规则限制可以‘推进’到挖掘过程,并且仍然保证回答挖掘查询的完全性?”
对于频繁项集挖掘,规则限制可以分为如下五类:(1)反单调的,(2)单调的,(3)简洁的,(4)可变的,(5)不可变的。对于每一类,我们将使用一个例子展示它的特性,并解释如何将这类限制用在挖掘过程中。
第一类限制是反单调性。考虑例6.9的规则限制”sum(I.price) < 100”。假定我们使用类似于Apriori的方法(逐层),对于每次迭代k,探查k-项集。其价格和不小于100的任何项集都可以由搜索空间剪去,因为向该项集中进一步添加项将会使它更贵,因此不可能满足限制。换一句话说,如果一个项集不满足该规则限制,它的任何超集也不可能满足该规则限制。如果一个规则具有这一性质,则称它是反单调的。根据反单调规则限制进行剪枝可以用于类-Apriori算法的每一次迭代,以帮助提高整个挖掘过程的性能,而保证数据挖掘任务的完全性。
注意,Apriori性质是说频繁项集的任何非空子集也必然是频繁的,它也是反单调的。如果给定的项集不满足最小支持度,则它的任何超集也不可能满足。这个性质用于Apriori算法的每次迭代,以减少考察的候选项集的个数,从而压缩关联规则的搜索空间。
反单调限制的其它例子包括”min(J.Price) ? 500”和”count(I) ? 10”等。任何违反这些限制的项集都可以丢弃,因为向这种项集中添加更多的项不可能满足限制。诸如”avg(I.price) ? 100”的限制不是反单调的。对于一个不满足该限制的项集,通过添加一些(便宜的)项得到的超集可能满足该限制。因此,将这种限制推进到挖掘过程之中,将不保证挖掘任务的完全性。表6.5的第二列给出刻画反单调性特性的基于SQL原语限制列表。为简化我们的讨论,只给出了存在性操作符(例如,?、?,但没有?、?)和带等号的比较(或包含)操作符(例如,?、?)。
第二类限制是单调性。如果例6.9中的规则限制是“sum(I.price) ? 100”,则基于限制的处理方法将很不相同。如果项集I满足该限制,即,集合中的单价和不少于100,进一步添加更多的项到I将增加价格,并且总是满足该限制。因此,在项集I上进一步检查该限制是多余的。换言之,如果一个项集满足这个规则限制,它的所有超集也满足。如果一个规则具有这一性质,则称它是单调的。类似的规则单调限制包括“min(I.price) ? 10”,“count(I) ? 10”等。表6.5的第三列给出刻画单调性特性的基于SQL原语限制列表。
表6.5 常用的基于SQL的限制的特性
限制 v?S S ? V S ? V min(S) ? v min(S) ? v max(S) ? v max(S) ? v count(S) ? v count(S) ? v
sum(S) ? v (?a?S,a ? 0) sum(S) ? v (?a?S,a ? 0) range(S) ? v range(S) ? v avg(S)? v, ??{=,?,?} support(S) ? ? support(S) ? ?
反单调的 否 否 是 否 是 是 否 是 否 是 否 是 否 可变的 是 否
单调的 是 是 否 是 否 否 是 否 是 否 是 否 是 可变的 否 是
简洁的 是 是 是 是 是 是 是 弱 弱 否 否 否 否 否 否 否
第三类是简洁性限制。对于这类限制,我们可以列出、并且仅仅列出所有确保满足该限制的集合。即,如果一个规则限制是简洁的,我们可以直接精确地产生满足它的集合,甚至在支持计数开始之前。这避免了产生-测试方式的过大开销。换言之,这种限制是计数前可剪枝的。例如,例6.9中的限制“min(J.price) ? 500”是简洁的。这是因为我们能够准确无误地产生满足该限制的所有项集。特殊地,这种集合至少包含一个项,其单价不低于$500。它是这种形式:S1 ? S2,其中S1 ? ?是集合中价格不低于$500的项的子集;而S2可能为空,是集合中价格不超过$500的项的子集。因为有一个精确“公式”,产生满足简洁限制的所有集合,在挖掘过程中不必迭代地检验规则限制。表6.5的第四列给出刻画简洁性特性的基于SQL原语限制列表。
第四类限制是可变的限制。有些限制不属于以上三类。然而,如果项集中的项以特定的次序排列,则对于频繁项集挖掘过程,限制可能成为单调的或反单调的。例如,限制“avg(I.price)”既不是反单调的,也不是单调的。然而,如果事务中的项以单价的递增序添加到项集中,则该限制就成了反单调的,因为如果项集I违反了该限制(即,平均单价大于$100),更贵的商品进一步添加到该项集中不会使它满足该限制。类似地,如果事务中的项以单价的递减序添加到项集中,则该限制就成了单调的,因为如果项集I违反了该限制(即,平均单价不超过$100),添加更便宜的商品到当前项集将使得平均单价不大于$100。除表6.5给出的“avg(S) ? v”和“avg(S) ? v”外,还有一些其它可变的限制,如“variance(S) ? v”和“standard_variation(S) ? v”等。
注意,以上讨论并不意味每种限制都是可变的。例如,“sum(S) ? v”不是可变的,其中, ??{?, ?}并且S中的元素可以是任意实数。因此,还有第五类限制,称作不可变的限制。一个好消息是:尽管有一些难处理的限制是不可变的,大部分使用SQL内部聚集的简单SQL表达式都属于前四类之一,对于它们可以使用有效的限制挖掘方法。
6.7 总结
?
大量数据之间的关联关系的发现在选择购物、决策分析和商务管理方面是有用的。一个流行的应用领域是购物篮分析,通过搜索经常一块购买的商品的集合(或序列),研究顾客的购买习惯。关联规则挖掘首先找出频繁项集(项的集合,如A和B,满足最小支持度阈值,或任务相关元组的百分比),然后,由它们产生形如A ? B的强关联规则。这些规则也满足最小置信度阈值(预定义的、在满足A的条件下满足B的概率)。 根据不同的标准,关联规则可以分成若干类型,如:
?
(1) 根据规则所处理的值的类型,关联规则可以分为布尔的和量化的。布尔关联规则表现离散
(分类)对象之间的联系。量化关联规则是多维关联规则,涉及动态离散化的数值属性。它也可能涉及分类属性。 (2) 根据规则中数据涉及的维,关联规则可以分成单维和多维的。单维关联规则涉及单个谓词
或维,如buys;而多维关联规则涉及多个(不同的)谓词或维。单维关联规则展示的是维内联系(即,同一个属性或维内的关联);而多维关联规则展示的是维间联系(即,属性/维之间的关联)。 (3) 根据规则涉及的抽象层,关联规则可以分为单层和多层的。在单层关联规则中,项或谓词
的挖掘不考虑不同的抽象层;而多层关联规则考虑多个抽象层。 (4) 根据对关联挖掘的不同扩充,关联挖掘可以扩充为相关分析和最大频繁模式(“最大模
式”)与频繁闭项集挖掘。相关分析指出相关项的存在与否。最大模式是一个频繁模式p,使得p的任何真超集都不是频繁的。频繁闭项集是指:项集c是闭的,如果不存在c的真超集c’,使得包含c的子模式的每个事务也包含c’。
?
Apriori算法是一种有效的关联规则挖掘算法,它逐级探查,进行挖掘。Apriori性质:频繁项集的所有非空子集都必须是频繁的。在第k次迭代,它根据频繁k-项集,形成频繁(k+1)-项集候选,并扫描数据库一次,找出完整的频繁(k+1)-项集L k+1。
涉及散列和事务压缩的变形可以用来使得过程更有效。其它变形涉及划分数据(在每一部分上挖掘,然后合并结果)和数据选样(在数据子集上挖掘)。这些变形可以将数据扫描次数减少到一或两次。
频繁模式增长(FP-增长)是一种不产生候选的挖掘频繁项集方法。它构造一个高度压缩的数据结构(FP-树),压缩原来的事务数据库。不是使用类Apriori方法的产生-测试策略,它聚焦于频繁模式(段)增长,避免了高代价的候选产生,获得更好的效率。
多层关联规则可以根据每个抽象层上的最小支持度阈值如何定义,使用多种策略挖掘。当在较低层使用递减的支持度时,剪枝方法包括层交叉按单项过滤,层交叉按k-项集过滤。冗余的(后代)关联规则可以删除,不向用户提供,如果根据其对应的祖先规则,它们的支持度和置信度接近于期望值的话。
挖掘多维关联规则可以根据对量化属性处理分为若干类。第一,量化属性可以根据预定义的概念分层静态离散化。数据方非常适合这种方法,因为数据方和量化属性都可以利用概念分层。第二,可以挖掘量化关联规则,其量化属性根据分箱动态离散化,“临近的”关联规则可以用聚类组合。第三,可以挖掘基于距离的关联规则,其中区间根据聚类定义。 并非所有的强关联规则都是有趣的。对于统计相关的项,可以挖掘相关规则。
基于限制的挖掘允许用户聚焦,按提供的元规则(即,模式模板)和其它挖掘限制搜索规则。这种挖掘促进了说明性数据挖掘查询语言和用户界面的使用,并对挖掘查询优化提出了巨大挑战。规则限制可以分五类:反单调的、单调的、简洁的、可变的和不可变的。前四类限制可以在关联挖掘中使用,指导挖掘过程,导致更有功效和更有效率的挖掘。
关联规则不应当直接用于没有进一步分析或领域知识的预测。它们不必指示因果关系。然而,对于进一步探查,它们是有帮助的切入点。这使得它们成为理解数据的流行工具。
?
?
?
? ?
?
习题
6.1 Apriori算法使用子集支持度性质的先验知识。
(a) 证明频繁项集的所有非空子集必须也是频繁的。
(b) 证明项集s的任意非空子集s’的支持度至少和s的支持度一样大。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说综合文库数据挖掘CHAPTER6挖掘大型数据库中的关联规则(5)在线全文阅读。
相关推荐: