（计算机软件与理论专业论文）海量数据库中的小模式发现.pdf

海量数据库中的小模式发现 摘要 摘要 随着信息时代的到来，科学研究、商业、行政等事务逐步计算机化，作为全 球信息系统的万维网开始流行，数据呈爆炸性增长，我们已经被淹没在了数据和 信息的汪洋大海中。作为大规模数据处理和决策支持的关键步骤之一，数据挖掘 受到了人们的广泛关注。小模式发现是数据挖掘中一个非常重要的研究课题，其 研究重点是有效高效地从大量复杂数据中获得小部分数据呈现的异常信息。 本文归纳了海量数据库中小模式发现的研究现状及热点问题，并在此基础上 分别对例外规则和离群点展开了研究和探索，提出了自己的定义，同时给出了适 合于大规模复杂数据集的挖掘算法。 具体地说，本文的贡献如下： 1 提出了一种快速有效的例外规则挖掘算法。该算法预先去除了类关联规 则中大量的虚假规则，减少了计算量。它不需要进行偏移量计算，避免 了偏移阈值取值不当的问题，能够找到所有的例外规则。由于例外规则 与有用的关联规则成对出现，用户对挖掘结果的理解更加简单直观。 2 提出了一种基于超图的高维数据的离群点检测算法。该算法根据频繁项 集来确定相对稠密的子空间，部分克服了维度灾难和组合爆炸问题，并 很好地体现了离群点的局部性。同时，该算法避免了传统的基于距离的 相似度计算，因此能够处理种属属性的数据和属性缺失的数据。实验和 分析表明，该算法能够快速有效地发现高维数据中的离群点。 3 提出了一种基于估计的子空间局部离群点检测算法。该算法针对基于距 离的离群点检测算法效率低下的问题，提出了根据高维离群系数估计低 维离群系数的技术，预先过滤掉大量不可能成为离群点的对象，极大地 提高了算法的效率。由于吸收了局部离群点发现和子空间数据处理的优 点，该算法能够找到所有子空间中的局部离群点。 关键词：数据挖掘，小模式，例外规则，离群点 海量数据库中的小模式发现 a b s t r a c t w 吼t h ec o m i n go fi n f o r m a t i o n a g e ，s c i e n t i f i c ，b u s i n e s s a n d g o v e r n m e n t t r a n s a c t i o n sa r eg r a d u a l l yc o m p u t e r i z e d ，a n dw o r l d w i d ew e bi sp o p u l a r i z e da sa g l o b a l i n f o r m a t i o ns y s t e m t h ee x p l o s i v eg r o w t ho fd a t ah a sf l o o d e du sw i t ha t r e m e n d o u sa m o t m to fi n f o r m a t i o n a so n eo ft h ek e ys t e p so fl a r g e s c a l ed a t a p r o c e s s i n ga n dd e c i s i o ns u p p o r t ，d a t am i n i n gh a sa t t r a c t e dag r e a td e a io f a t t e n t i o n s m a l lp a t t e r nd i s c o v e r yi sas i g n i f i c a n tr e s e a r c ht o p i ci nt h i sf i e l d ，w h i c hf o c u s e so n f i n d i n g a b n o r m a li n f o r m a t i o n a p p l i c a b l e t oas m a l l p o r t i o n o fd a t af r o m l a r g e ， c o m p l e x d a t as e te f f e c t i v e l ya n de f f i c i e n t l y a f t e rp r o v i d i n gas u r v e yo fc u r r e n tr e s e a r c ha n dp r o b l e m so ns m a l lp a a e m d i s c o v e r y , t h i st h e s i sd i g si n t ot h es t u d yo fe x c e p t i o nr u l ea n do u t l i e r , r e s p e c t i v e l y i t p r o p o s e s i t so w nd e f i n i t i o n sa n d a l g o r i t h m sf o rl a r g ea m o u n t ，c o m p l e xd a t a s e t s t h ec o n t r i b u t i o no f t h i st h e s i si ss u m m a r i z e da sf o l l o w s ： 1 a ne f f i c i e n ta n de r i e c t i v ee x c e p t i o nr u l em i n i n ga l g o r i t h mi s p r e s e n t e d i t r e d u c e st h e c o m p u t a t i o n a lc o m p l e x i t yg r e a t l yb yp r u n i n gs p u r i o u s c l a s s i f i c a t i o na s s o c i a t i o nr u l e si na d v a n c e d e v i a t i o nc o m p u t a t i o ni sn o t n e c e s s a r yi nt h ea l g o r i t h m ，s oi t c a l lf i n da l le x c e p t i o nr u l e se x e m p t e df r o m t h e p r o b l e m o ft h r e s h o l d c h o o s i n g s i n c ee x c e p t i o n r u l e sa n du s e f u l c l a s s i f i c a t i o nr u l e s a p p e a r i n p a i r s ，u s e r s c a n e a s i l yg e t a p r o f o u n d u n d e r s t a n d i n go f t h em i n i n gr e s u l t s 2 a h y p e r g r a p h - b a s e d o u t l i e rd e t e c t i o n a l g o r i t h m i s p r o v i d e d f o r h i 曲 d i m e n s i o n a ld a t as e t s i tu s e sf r e q u e n ti t e m s e t st od e c i d er e l a t i v e l yd e n s e a r e a s ，w h i c hc a l lp a r t i a l l yc o n q u e rt h ep r o b l e m so fc u r s eo fd i m e n s i o n a l i t y a n dc o m b i n a t i o n a i e x p l o r a t i o n a v o i d i n gt r a d i t i o n a ld i s t a n c e b a s e ds i m i l a r i t y m e a s u r e m e n tm a k e st h ea l g o r i t h mr o b u s tt o c a t e g o r i c a ld a t aa n dd a t aw i t h m i s s i n ga t t r i b u t e s e x p e r i m e n t sa n da n a l y s i ss h o wt h a tt h i sm e t h o dc a nf i n d o u t l i e r si nh i g h d i m e n s i o n a ls p a c e e f f e c t i v e l ya n de f f i c i e n t l y 3 a ne s t i m a t i o n - b a s e ds u b s p a c el o c a io u t l i e rd e t e c t i o na l g o r i t h mi sd e s c r i b e d t os o l v et h ee f f i c i e n c y p r o b l e mo f d i s t a n c e b a s e dm e t h o d s ，i tb r i n g sf o r w a r d t h et e c h n i q u eo f e s t i m a t i n gl o c a lo u t l i e rf a c t o ri nt h el o w e rs u b s p a c e sb a s e d o nt h ei n f o r m a t i o ni nt h eu p p e r s u b s p a c e s l a r g ea m o u n to f u n r e l a t e do b j e c t s a r ep r u n e di na d v a n c e ，t h u st 1 1 e c o m p u t a t i o n a lc o s ti sr e d u c e dd r a m a t i c a l l y s i n c ei tt a k e sa d v a n t a g e so fb o t hl o c a lo u t l i e rd e t e c t i o na n ds u b s p a c ed a t a p r o c e s s i n g ，1 tc a nf i n di n t e r e s t i n gl o c a lo u t l i e r si na 1 1s u b s p a c e s k e y w o r d s ：d a t am i n i n g ，s m a l l p a t t e r n ，e x c e p t i o nr u l e ，o u t l i e r i i 海量数据库中的小模式发现 g 【言 第一章引言 1 1 数据挖掘的定义和分类 我们正处在一个信息爆炸的时代! 在商务管理、金融贸易、生产控制、市场 分析、工程设计和科学探索等各种应用中，都存在着大量的数据。数据的快速增 长已经远远超出了人们理解它们的能力，“数据丰富、信息贫乏”的问题不可避 免地产生了，人们迫切需要强有力的数据分析工具帮助他们从海量数据中提取有 价值的知识。在这一背景下，数据挖掘( d a t am i n i n g ) 应运而生，并逐渐发展成为 信息产业界极为关注的一门单独技术。 目前对数据挖掘的理解分为广义的和狭义的两种。 广义的理解将数据挖掘等同于数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，k d d ) ，即从大规模的数据库中抽取非平凡的、隐含的、未知的、有 潜在使用价值的信息的过程【p 8 9 6 。”。 狭义的理解将数据挖掘视为k d d 的一个基本步骤。k d d 是从大量数据中发 现正确的、新颖的、潜在有用并能够被理解的知识的过程f p 8 9 6 。2 】。它由数据清洗、 数据集成、数据选择、数据变换、数据挖掘、模式评估、知识表示等多个步骤组 成。数据挖掘只是其中的一个步骤，它使用各种智能的方法，从预处理过的数据 中抽取知识。 这两种理解尽管有差异，但它们对以下两个问题的认识是统一的：1 ) 数据 挖掘的对象是大规模的数据，因此必须具有高效性和良好的可伸缩性。2 ) 数据 挖掘的最终目的是辅助用户进行决策支持，因此挖掘结果必须是准确的、可用的、 未知的、可理解的知识。 数据挖掘是一个交叉学科领域，受数据库系统、统计学、机器学习、可视化 和信息科学等多个学科的影响，相应的研究也非常多，且各自有不同的侧重点。 根据不同的标准，数据挖掘可以分类如下： 根据挖掘的数据库类型分类“0 0 ：数据库系统本身可以根据不同的标准分 类，每一类可能都有相应的数据挖掘技术。例如，根据数据模型分类，有关 系的、事务的、面向对象的、对象一关系的或数据仓库的数据挖掘技术等；根 海量数据库中的小模式发现 引言 据处理的数据的特定类型分类，有空间的、时间序列的、文本的、多媒体的 或w e b 数据挖掘技术等。 根据挖掘的知识类型分类h k 0 0 】：根据数据挖掘发现的模式类型的不同，可分 为分类( c l a s s m c a t i o n ) 和预测( p r e d i c t i o n ) 、关联分析( a s s o c j a t i o na n a l y s i s ) 、聚 类分析( c l u s t e r i n ga n a l y s i s ) 、偏差检测( d e v i a t i o nd e t e c t i 日n ) 獭1 ；根据 挖掘结果的数据规则性，可分为大模式( 1 a r g ep a t t e r n ) 和小模式( s m a l lp a t t e r n ) 两种。 根据所用的技术分类 b s 9 7 1 】，可以分为基于统计的方法、决策树方法、神经元 网络方法、最近邻方法、遗传算法、规则归纳方法等。复杂的数据挖掘系统 通常采用多种数据挖掘技术，或将多种方法结合使用，因此这种分类不是绝 对的。 根据应用分类c h 8 + 9 8 】，可以分为市场管理、风险管理、欺诈管理等。普通的 数据挖掘系统可能并不适合特定领域的挖掘任务，需要针对特定应用开发相 应的数据挖掘方法。 1 2 数据挖掘研究的发展 自2 0 世纪6 0 年代以来，数据库和信息技术已经从原始的文件处理演化为复 杂的、功能强大的数据库系统。至7 0 年代，关系数据库系统的相关技术日趋成 熟，用户可通过查询语言、优化处理和事务管理来方便灵活地访问数据。自8 0 年代中期以来，各种各样新的、规模大、功能强的数据库系统和数据仓库开始出 现，基于i n t e m e t 的全球信息系统如w w w 逐渐成为世晃上最大的数据库。这些 技术大大推动了信息产业的发展。 数据的丰富给人们理解、利用它们带来了困难。在数据挖掘技术兴起以前， 数据分析通常是用统计的方法手工完成的。随着数据规模、维数和复杂度的增长， 手工的方法不再适用，而统计的方法因为较为专业，难以为用户掌握。数据库、 数据仓库中的大量数据往往因此变成了“数据坟墓”难得再访问的数据档案。 数据和信息间的鸿沟要求开发出自动从大量数据中抽取有用知识的数据挖掘工 具，将“数据坟墓”转换成知识金块。 数据挖掘的研究就是在这一需求下产生的，并逐渐成为了数据库系统和新的 数据库应用的一个充满希望的学科前沿，同时也有越来越多的研究者投身这一领 域。1 9 9 5 年，第一届“知识发现与数据挖掘”国际学术会议f f i r s ti n t e m a t i o n a l 海量数据库中的小模式发现 引言 c o n f e r e n c eo nk n o w l e d g ed i s c o v e r ya n dd a t a m i n i n g ) 在加拿大的蒙特利尔召开。该 会议是由1 9 8 9 年至1 9 9 4 年举行的四次“数据库中的知识发现”国际研讨会发展 而来的。a c m 于1 9 9 8 年成立了一个新的学术组织s l g k d d ( s p e c i a li n t e r e s t e d g r o u p o nk n o w l e d g e d i s c o v e r y i nd a t a b a s e s l ，这是a c m 下的一个数据库中的 知识发现专业组。之后，数据挖掘专题杂志陆续出版，其它一些国际或地区性数 据挖掘会议也逐渐多起来。现在，每年包含数据挖掘或知识发现主题的学术会议 超过十个，参加者涉及统计、人工智能、数据库、机器学习等多个领域。 随着数据挖掘技术的成熟和发展，许多应用开始采用数据挖掘技术进行决策 支持，软件提供商们也纷纷开始开拓数据挖掘市场。s a s ，s p s s ，i b m ，o r a c l e ， m i c r o s o f t 等软件公司都已推出了相应的数据挖掘产品或面向特定领域的数据挖 掘应用软件。 数据挖掘是个新兴的领域，有很多问题需要深入研究。目前的研究热点主 要集中在以下方面： 提高数据挖掘算法的性能，包括算法的有效性、可伸缩性和并行处理能力等。 数据挖掘算法的处理对象多为大规模的数据，因此算法必须是有效的和可伸 缩的，也就是说，算法的运行时间必须是可预计的和可接受的。同时，数据 的大规模、数据的广泛分布和数据挖掘算法的高复杂性促使人们去研究开发 并行分布式数据挖掘算法以及增量数据挖掘算法。 提高数据挖掘算法处理不同类型数据的能力。现实应用的数据是多种多样 的，它们可能是超文本数据、多媒体数据、空间数据、时间数据或事务数据， 它们可能是简单数据，也可能包含复杂的数据对象，它们可能是结构化的， 也可能是半结构化或无结构的数据。为特定类型的数据构造特定的数据挖掘 系统，是数据挖掘中一个具有挑战性的课题。 提高数据挖掘结果的可理解性和可使用性。数据挖掘的最终目的是为用户提 供决策支持，因此挖掘结果必须是简洁的，易于用户理解的，并且能够被应 用的。数据挖掘系统可能发现数以干计的模式，但用户感兴趣的只是其中的 - d , 部分。数据挖掘系统应该允许与用户交互，从不同的粒度和角度观察数 据，以找到用户感兴趣的模式。数据挖掘结果应当用高级语言、可视化表示 或其它简洁的方式来表示，使得知识易于理解。能够直接被用户使用。需要 有处理噪声、异常情况或不完全对象的分析方法，以保证发现的模式的精确 度。 海量数据库中的小模式发j | ! l l 引言 1 3 本文组织 本文总共分为五章，第一章为引言，第五章为总结，第二章到第四章为本文 的研究内容。其中，第二章简单描述了数据挖掘中的新兴课题小模式发现的 研究内容、研究现状以及亟待解决的问题。第三章针对例外规则发现问题展开研 究，提出了一种新颖有效的例外规则发现方法。第四章着重研究高维空间中的离 群点发现问题，提出了两个算法，个是基于超图的高维种属属性离群点检测算 法，一个是基于估计的高效子空间局部离群点发现算法。最后，在第五章，作者 对本文进行了总结。 海量数据库中的小模式发现 小模式发现 2 1 小模式发现简介 第二章小模式发现 数据挖掘是从大规模数据库中发现未知的、有用的、非平凡的知识的过程， 它可能产生数以千计，乃至数以万计的模式或规则。数据挖掘的结果可以分为 大模式和小模式两大类。大模式是适用于大部分数据的常规模式，是大量数据 所共有的特征，如，关联分析发现的是大量数据中项集之间出现频繁的关联或 联系，聚类分析将数据集中的大部分数据分成多个类，每个类由相似的对象组 成。小模式是隐藏在小规模数据背后的信息，是数据集中少量数据呈现的异常 现象，如游离于大部分数据之外的离群点( o u t l i e r ) ，与关联规则相反的例外规则 ( e x c e p t i o nr u l e ) ，由自身或外界的一些不确定因素引起的噪声( n o i s e ) 等。 并非所有的模式都是有趣的。一个模式是有的( i n t e r e s t i n g ) e “k 0 0 1 ，如果1 ) 它易于被人理解；2 ) 在某种程度上，对于新的或测试数据是有效的；3 ) 是潜 在有用的；4 ) 是新颖的。有些模式反映的是人们已经预料到的知识，因而实际 上并不令人感兴趣。大模式中的很多知识就是这类常识性知识。相比之下，小 模式往往更加出乎意料，能够提供一些经常被用户忽略的信息，因而在决策支 持方面更有价值。传统的数据挖掘专注于大模式的发现，很多情况下只是将小 模式作为大模式发现的副产品，甚至直接忽略小模式。然而在实际应用中，如 电子商务、网络监控、金融服务等，用户感兴趣的不是常规模式，而是隐藏了 更多信息的小模式。如何从海量数据中快速有效地发现小模式，是数据挖掘领 域亟待解决的一个新问题。 2 2 研究现状 小模式发现是数据挖掘领域研究的新课题。目前国际上对小模式的研究主 要分为三个方面：例外规则、离群点和噪声。 例外规则属于关联规则( a s s o c i a t i o nr u l e ) ，是少量数据背后隐藏的与常规规 则相反的有趣规则。关联规则发现一直是数据挖掘领域中一项重要的研究内容。 近来，一些研究者对于少量数据背后隐藏的高可信度的或有趣的规则展开了研 海量数据库中的小模式发现 小模式发现 究，包括：小类别学习【a k o “、例外规则学习 y j o o 、有趣意外规则学习 r t o o 等。 这些研究工作都是建立在规则推导的基础上的。研究者们各自遵照不同的标准， 至今仍然没有统一的定义和衡量方法，也没有研究者将例外规则的研究和其它 小模式的研究进行比较或者进行整合。 离群点发现是近年来数据挖掘领域研究的热点。从1 9 9 8 年开始，研究者们 逐步就空间离群点的高效寻找算法 r a q 9 8 ，k n 9 9 ，k n 7 0 0 ，8 r s 0 0 l 、局部离群点发现8 k n + 0 0 ， 1 7 h 0 1 1 和高维离群点发现 k n 9 9 ，a y 叭l 展开了研究。与例外规则的研究相似，至今为 止，离群点仍然缺乏公认的定义和质量评判标准。而且，对于高维空间的离群 点发现，现有方法无论从定义角度，还是从效率角度，离实用都还有相当长的 距离。海量数据库中的离群点发现仍有待深入研究。 噪声分析是统计中的经典问题。与统计学研究的对象不同数据挖掘分析 的对象是离散的、无序的数据。更进一步，数据挖掘的对象往往是高维数据。 传统的统计方法无论从效果上还是性能上都不能满足要求。数据挖掘中专门针 对噪声的研究还比较少，噪声与离群点之间的联系与差异也未得到明确。 2 3 几个简单例子 目前对例外规则和离群点等小模式的研究还比较少，数据挖掘界对它们的 定义也未达成共识，这里仅举几个简单的例子来给读者一个直观的概念。 简单来说，例外规则是与常识相反的出人意料的、有趣的关联规则。如下 例中给出的支持度( s u p p o r o 低，但置信度( c o n f i d e n c e ) 高的规则。 例2 1 假定有一个包含8 1 2 4 条记录的蘑菇数据集，如图2 1 所示。其中6 0 是毒 蘑菇，用黑点表示，剩下的4 0 是可以食用的，用灰点表示。取最小支持 度为3 0 ，最小置信度为5 0 ，可以找到这样的一条关联规则，佃e a u t i f u ，= y e s = e d i b l e = n o ，其支持度为7 0 ，置信度为8 0 。这也即是人们常 说的“长得漂亮的蘑菇有毒”。通过例外规则挖掘，我们将得到规则 b e a u t i f u ， 2 y e s ，g i l l - s i z e = b r o a d = e d i b l e = y e s 。这是一条例外规则，因为它出现 的可能性很低( 支持度仅为5 ) ，且与人们的常规认识相反。但这条例外 规则是可靠的( 其置信度高达9 0 ) ，也是可用的( 野外生存时，根据这条 规则可能可以找到不少能吃的蘑菇) 。 一 海量数据库中的小模式发现小模式发现 图2 1 例外规则的一个例子 离群点，又称为孤立点或奇异点，是与数据集中其它大部分对象的行为、 特征有很大差别的对象，它们不符合数据的一般模型。如下例中给出的散落在 簇( c l u s t e r ) 之外的点。 图2 2 离群点示意图 海量数据库中的小模式发现 小模式发现 例2 2 图2 2 给出了一个简单的二维数据集，其中的大部分数据对象聚集成了四个 大小不同、稀疏程度不同的簇。但是，有几个数据对象游离于四个簇之外， 它们就是人们直观印象中的离群点。 2 4 本文的研究内容 本文旨在研究海量数据库中的小模式发现理论与方法。研究内容包括： 离群、例外和噪声三种不同小模式的定义、性质、区别和联系 小模式又可细分为离群点、例外和噪声三类。离群、例外和噪声都是少量 数据表现的行为，但离群点和例外蕴含着某些规律，而噪声则完全是由错误或 干扰造成的，不能提供有价值的信息。离群点和例外分别对应于大模式发现中 的“聚类”和“分类”，前者是无监督学习的结果，后者是有监督学习的结果。 与“聚类”和“分类”不同的是，离群点和例外都是局部( 1 0 c a l ) 概念，很多适 应于大模式的性质对它们不再成立。因此需要专门研究离群点和例外自身的特 点，为定义和算法提供理论基础。本文力求分别给出三者的合理的、广义的定 义，分析它们各自的特性，横向探索三者的联系和区别。 小模式含义的解释和度量 数据挖掘研究是面向实际应用的，挖掘结果的可理解性和可用性非常重要。 对于用户来说，挖掘结果只不过是另一堆数据，如果不理解其含义，仍然很难 在实际应用中发挥其价值。本文的一个研究重点是提供恰当的方法( 如给出与 例外规则对应的常识规则、给出离群点的离群属性、离群程度等) 和形式( 如 可视化) 对挖掘出的小模式信息进行解释，使用户能直观地了解到挖掘结果的 特殊程度以及造成它们特殊的原因。 海量数据库中的小模式发现算法 处理大规模数据是数据挖掘最基本的要求之一，而处理海量数据库则是对 数据挖掘研究的更大挑战。总体说来，现有的小模式发现算法的效率离实用还 有相当距离。本文的一个研究内容是，利用数据库提供的查询技术，利用其它 数据挖掘操作( 如分类和聚类) 的中间结果，利用有效的数据结构( 如树) ，利 用一些数学特性等，来提高算法效率。 复杂数据的小模式发现 数据挖掘的最终结果是为实际应用提供决策支持，研究的重点应放在真实 海量数据库中的小模式发现 小模式发现 的商用数据上，如网络日志、电话记录和健康数据等。真实数据通常比较复杂， 如数据量大、维数高、数据不完全等。本文对这些问题进行了研究，针对不同 数据，采用特殊的技术来辅助小模式发现。例如，针对种属属性或属性缺失的 数据，采用新的相似度衡量方法，避免传统距离定义的影响；针对高维数据分 布稀疏的特性，采用子空间小模式发现方法，以得到更有意义的结果。 海量数据库中的小模式发现 例外规则发现 3 1 问题的提出 第三章例外规则发现 煳1 ( c l a s s 九l l 曲挖掘和关联规则挖掘是数据挖掘中比较重要，而且比较相 似的两种操作。它们的区别在于挖掘目标不同。类规则挖掘要得到数据库中推导 出某一特定类的规则，而关联规则挖掘则是要找出数据库中所有满足最小支持度 和置信度闽值的规则a i s 9 3 , a s 9 4 。在实际应用中，类规则和关联规则都是很重要的。 将两者结合起来，就得到类关联规则( c l 嬲s a s s o c i a t i o n r u l e c a r ) 。“m 9 8 ，l l 0 0 1 的 概念。 类关联规则是关联规则的一个子集，推导式子的右边必须是类属性( c l a s s l a b e l l ，即表明对象类别的属性。例如，对蘑菇数据集m m 9 6 1 进行实验，可以得到 这样的一条类关联规则： 操凭箭缰擎萤等= 方萄。类关联规则是很有用的，它 能够帮助人们方便地根据数据对象的一些特性判断出其类别，可作为一种有效的 分类方法。但是，未经任何处理的类关联规则挖掘结果中往往包含大量虚假的类 关联规则( s p u r i o u s c i a s s o e i a t i r u l e s c a r ) l a y 9 8 1 。下面是一个例子。 例3 1 假定有人对某校5 0 0 0 名学生的早餐及早锻炼情况进行调查。数据显示，其 中有3 7 5 0 名学生打篮球，3 0 0 0 名学生吃麦片，4 5 0 0 名学生喝牛奶，3 0 0 0 名 学生既喝牛奶又吃麦片，3 2 5 0 名学生既喝牛奶又打篮球，2 0 0 0 名学生既吃 麦片又打篮球，2 0 0 0 名学生三件事都做。取最小支持度为4 0 ，最小置信度 为6 0 ，可以发现以下三条类关联规则： ，打登毋= 碍学垂刃( 支持度为6 5 ，置信度为8 6 7 ) ，碍锄= 呓麦片0 ( 支持度为6 0 ，置信度为6 6 7 ) ，碍笋扔，办盗i 笋= 磋：枣聊( 支持度为4 0 ，置信度为6 1 5 ) 第一条类关联规则是一条虚假的类关联规则，因为所有学生中有9 0 喝 牛奶，高于这条规则的置信度8 6 7 。因此，打篮球和喝牛奶是负关联的一 一打篮球不但不增加喝牛奶的概率，可能还有降低的嫌疑。 第三条类关联规则也是一条虚假的类关联规则，因为，碍学奶= 吃麦 力的置信度是6 6 7 ，大于，田锄，办= 笸谚= 呓芜，舟的置信度6 1 5 。 也就是说，加上打篮球这一活动后，喝牛奶推出吃麦片的概率并没有增加， 1 0 海量数据库中的小模式发现 例外规则发现 反而降低了，因此这是一条虚假的规则。 一 从这个例子可以看出，一条规则即使满足了支持度和置信度的限制，也不一 定能正确地反映数据中蕴含的规律。我们认为，存在两种虚假的类关联规则，形 式化定义将在3 2 中给出。如果一条类关联规则不是虚假的类关联规则，我们就 称其为有用的类关联规 1 ( u s e f n lc l a s s i f i c a t i o na s s o c i a t i o nr u l e u c a r ) 。不幸 的是，类关联规则中有很大一部分是虚假的类关联规则。在产生类关联规则后， 很难直接对其进行浏览并得到有用的信息。用户可能被其中虚假的类关联规则所 蒙蔽，从而做出错误的判断。因此对类关联规则进行“去伪存真”的处理是很有 必要的。 类关联规则挖掘得到的规则具有高支持度和置信度。这些规则是重要的，但 它们通常与专家的预测是一致的是“已知的”规律。研究者们希望找到更有 趣的、出乎人们意料的规则。例外类关联规则( e x c e p t i o n c l a s s i f i c a t i o n a s s o c i a t i o nr u l e e c a r ) 就是这样的一类规则，它们的置信度高但支持度低。 它们的结果往往与类关联规则的结果不一致，能够给我们提供额外的知识，因此 这类规则是重要的。然而由于它们的支持度低，不能通过传统的数据挖掘技术产 生，因此需要专门的技术来挖掘它们。下面的例子可以说明这个问题。 例3 2 假定我们对银行数据进行挖掘操作，以决定给哪些申请者授予信用卡。如果 最小支持度设为5 0 ，可以得到一条支持度为7 0 的规则，狰青工萨= 石 授于借用向，这表明“多数没有工作的申请者不能被授予信用卡”。然而， 我们并不能得到另外两条重要的规则，发青工，彭女烂； 授于售劈1 和 ，验方工，只职员膨：杀属= 授于佶劈匍，因为它们的支持度只有1 5 。这 些规则是未知的、未预想到的，有时甚至是与人们的经验相反的。它们能够 帮助银行的管理人员注意到一些以前一直被忽视的情况。例如，账户经理可 能由此产生警觉，并进步去调查为什么会有这样的情况出现。这些申请者 可能被银行忽视的客户，也可能是一些技巧高超的欺诈者。 3 2 问题描述 假定数据集是一张有n 条记录，个属性的关系表。已知这n 条记录属于g 个类( 由类属性来标示) 。属性可以是种属属性( c a t e 9 0 r i c a la t t r i b u t e ) ，也可以是 海量数据库中的小模式发现 例外规则发现 数值属r 生( n u m e r i c a la t t r i b u t e ) 。对于一个种属型的属性，其所有属性值将被映射 为一组连续的正整数。对于一个数值型的属性，其属性值域将被离散化为几个区 间，所有区间映射成一组连续的正整数。目前已有多种对连续属性进行离散化的 算法，如d o u g h e r t y 等的工作【o “5 9 ”，这里不再赘述。映射完毕以后，数据集可 阻被看成是偈拦，登鼋盱固对和类属性的集合。每个霄筮，型j 嚣匈被称为一个 项( i t e m ) 。项的集合称为项集( i t e m s e t ) 。 我们的目标是： 根据用户给定的最小支持度和置信度限制，产生完整的类关联规则集合： 去除类关联规则中虚假的类关联规则，以得到有用的类关联规则； 为每条有用的类关联规则产生相应的例外类关联规则。 首先我们给出类关联规则、虚假的类关联规则、有用的类关联规则以及例外 类关联规则的形式化定义： 定义3 1 ：类关联规贝u ( c l a s s a s s o c i a t i o nr u l e - c a r ) 设有数据集d ，是d 中所有的项的集合，y 是类属性的集合。一条类关联 规则是形如= 纠的推导，其中xe ，y y 。这条规则的支持度为s 如果d 中s 乡6 的记录同时包含x 和y ，置信度为c 如果d 中包含的记录有 c 属于类别y 。 定义3 2 ；虚假的类关联规s f j ( s p u r i o u sc l a s s a s s o c i a t i o nr u l e s c a r ) 设类关联规则为= y 一则虚假的类关联规则有两种形式：一种是s u p p o r t c o n f i d e n c e = ，这表明结论在条件不成立的情况下仍然是真的， 我们称之为强结论虚假类关联规则( s t r o n g c o n c l u s i o ns c a r s cs c a r ) 。 另一种是j * 使c o n f i d e n c e = 叫 c o n f i d e n c e 陋= 刃，这意味着 我们只需要比x 小的集合爿就可以推出结论y ，条件的某些部分是多余的， 这种规则我们称之为冗余条件虚假类关联规则( r e d u n d a n tc o n d i t i o ns c a r - r cs c a r ) 。根据定义，例3 1 中的第一条规则是强结论虚假类关联规则， 第三条规则是冗余条件虚假类关联规则。 定义3 3 ：有用的类关联规则f u s e f u l c l a s s a s s o c i a t i o n r u l e u c a r ) 如果一条类关联规则不属于任何一种虚假类关联规则，我们称之为有用的类 关联规则。 定义3 4 ：例外类关联规则( e x c e p t i o nc l a s sa s s o c i a t i o nr u l e e c a r ) 假定j ，是一条有用的类关联规则，则例外类关联规则的形式为z 海量数据库中的小模式发现 例外规则发现 = 儿7 ，其中xz e lx n z = ，y ，y 2 e r y l y 2 。例外类关联规则满足最 小置信度的要求，但不满足最小支持度的要求。否则它就是一条有用的类关 联规则。 c a r s c a r ，u c a r 和e c a r 的关系如图3 1 所示。给定一个数据集，数据当 中可能会存在一些联系，即我们所说的关联规则，用图3 1 中的矩形框表示。我 们希望能找到所有的关联规则，但实际上，这太难做到了。a p r i o r i a s 9 4 是一种强 大的关联规则挖掘算法，它能找到数据中存在的大多数联系，用图中的大椭圆表 示。由于c a r 是关联规则的一种特殊形式，因此表示它的椭圆包含在表示用 a p r i o r i 得到的关联规则的椭圆的内部。注意到c a r 中有很大一部分是s c a r ， 去除了s c a r 以后，就得到了u c a r 。除此以外，还存在一些不满足最小支持度 和置信度限制的例外规则。有些例外规则是对应于u c a r 的，我们称之为e c a r 。 从图31 中可以清楚地看到这些关系。 3 3 算法 图3 1c a r ，s c a r ，u c a r 和e c a r 之间的关系示意图 挖掘e c a r 的过程分为三步，如图3 2 所示。第一步，得到所有满足最小支 持度和置信度要求的c a r ；第二步，去除c a r 中的s c a r ，得到u c a r ；第三步， 为u c a r 生成对应的e c a r 。 发现c a r sl 去除s c a r s 以得到i 为每条u c a r 生f j 厂_ 1 竺! r _ 叫壁兰! 竺 l 图3 2 挖掘e c a r 的步骤 海量数据库中的小模式发现 3 3 1 产生c a r 这一步的目标是从数据集中产生完整的c a r 集。我们提出的算法叫做 c a r g e n 。假定数据集中所有可能的属性值都被映射成了连续的正整数。所有记 录共属于g 个类，被映射为0 到g 。的g 个整数。相应的，算法c a r g e n 找到的 c a r 可以分成q 个组，记为c a r o 到c a r 国一u 。同一个组c a r d 中的规则都 属于类别y 。 - c a r g e n 算法中使用的符号 一个规则项( r u l e i t e m ) 型如= y ，其中x 是数据集的项的一个子集，y 是 一个类属性。x 称为规则项的项集。满足最小支持度的项集称为频繁项集 f f r e q u e n ti t e m s e t ) ，包含频繁项集的规则项称为频繁规则项( f r e q u e n tr u l e i t e m ) 。 如果一个规则项的项集包含k 个项，我们称其为k 规则项( k _ r u l e i t e m ) 。凡刀表 示类属性为f 的频繁k 规则项的集合。c 矾7 表示类属性为i 的候选k 规9 1 u 项 ( c a n d i d a t ek _ r u l e i t e m ) 的集合。 - c a r g e n 算法 我们采用a p r i o r i a s 9 4 1 算法的框架来产生候选的c a r ，不同的是仅对同一个 组内的项集作连接( i o i n ) 。算法需要对数据进行多次扫描。第一次扫描，计算单 个规则项的出现次数并判断它是否是频繁的。接下来对第一次扫描得到的频繁规 则项集进行扫描，生成新的可能的频繁规则项，又叫做候选规则项。最后进行一 次扫描，得到真正频繁的规则项，并根据类属性将它们插入到相应的树中。根据 得到的频繁规则项集合，可以很方便地生成c a r ( 因为我们的目标是得到u c a r ， 所以在这里并不急于直接求出c a r ) 。c a r g e n 算法如图3 3 所示。 p r o c e d u r ec a r g e n 输入：数据集d ，最小支持度5 ，最小置信度c ，记录种类g 输出：节点为满足最小支持度的频繁项集的一组树w e e o , t r e e i , ，t r e e q u l f o r ( i = 0 j i q ji + + ) d o 2 c l i 】= a l lf r e q u e n t 1 一r u l e i t e m s w i t hc l a s sl a b e l i j 3 e n df o r 4 c - = u c 。 f j 5 f o r ( k = l jc k 中jk + + ) d o 6f o re a c hd a t a c a s ed dd o 海量数据库中的小模式发现 例外规则发现 图3 3 c a r g e n 算法 1 4 行表示的是算法的第一遍扫描。它对项和类的出现次数计数，并将所有 类强性为i 哟频繁l 规烫0 顼集弧入融候选频繁l 项集c l m 郜。c l 是瓯奄c l 嘲 的并。 在接下来的第k 次扫描中，算法主要进行以下两个操作： 扫描数据库( 6 - 1 1 行) ，计算g 中所有候选项的支持度。因为g 是所有 c d i 的并，这意味着对所有的c d i 都要进行计算。 如果c t 中类属性为i 的一个规则项的支持度大于最小支持度，则该项被 加入到频繁规则项集取彤中。函数c a n d i d a t e g e n 根据删产生候选规则 项集g ( 第1 5 行) 。之后r 埘被插入t r e e i ( t r e e i 中的节点是类属性为 i 的频繁项集) 。 一c a r g e n 算法的正确性 定理3 1 ：某个类别的痧己透t 赢嬲够通过连接该类别中的频繁( k - # j t 拓y g n 得到。 证明： v x 。x 2 x 3 以q 川，项集葺屯屯砩的支持度大于最小支持度s ，由 此可知项集一乇+ ，x 。x 2 x 3 一：的支持度也都大于s ，因此