（计算机应用技术专业论文）关联规则与超团挖掘算法研究.pdf

关联规则与超团挖掘算法研究 摘要 数据挖掘技术是近年来数据库和人工智能等领域研究的热点课 题，它引起了科学界和产业界的广泛关注。数据挖掘的主要目的是从 数据集合中发现隐含的、事先未知的、对决策有潜在价值的用户感兴 趣的知识。关联规则最初来源于对超市购物篮的分析，主要用于发现 数据集中项与项之间的相关联系，是数据挖掘最先研究的问题之一， 也是数据挖掘的一个热点研究方向。关联规则可以广泛地应用于各个 领域，既可以检验行业内长期形成的知识模式，也能够发现隐藏的新 规律。如何有效地发现、理解并运用关联规则，是数据挖掘任务中的 一个重要研究方面。 本文在数据挖掘研究和关联规则挖掘研究的背景下，展开了对关 联规则挖掘算法的研究工作。首先分析讨论了数据挖掘技术的产生与 发展现状、数据挖掘的基本过程、数据挖掘的主要任务；接着介绍了 关联规则挖掘的基本概念、关联规则挖掘的算法研究现状、关联规则 挖掘工作的扩展和应用，数据集的水平和垂直分布，分析了经典关联 规则挖掘方法a p r i o r i 算法及另一个易于实现的r e l i m 算法。 本文接着重点讨论了h 一置信度度量及其产生的超团模式，论述 了交叉支持的概念及其相关的扩展问题。在此基础上提出超团挖掘中 可以应用事务拆分的方法对事务集进行预处理，并探讨了事务拆分的 方法及其正确性的证明。通过进一步的分析，证明在基于兴趣度度量 的关联规则挖掘中，如果度量具备交叉支持性质，则都可以应用事务 拆分的方式对数据集做预处理。 本文提出了基于r e l i m 算法的超团挖掘算法h r e l i m 和极大超团 挖掘算法m h r e l i m 。以超团挖掘算法为基础，通过实验，探讨了事务 拆分及事务压缩对h r e l i m 算法带来的效率提高。通过实验，说明 m h r e li m 算法在稀疏数据集上具有良好的挖掘性能。 通过在算法a p r i o r i ，r e l i m ，f p g r o w t h 上做的大量实验，得到 算法在数据集的项不同排序方式下的效率差异结果，由此猜测在关联 规则挖掘算法中，如果频繁项集的获取顺序是这样的，即总是先产生 含有支持度最低的项的频繁集，并且由此使得每个频繁项产生的频繁 项集数量均较为接近，则算法速度最快，称之为均衡法则。均衡法则 在算法的效率改进和新算法的寻找上具有很好的指导意义。 关键词：数据挖掘关联规则超团模式事务拆分交叉支持 均衡法则 i i i 己e s e a r c ho nt h ea l g o r 【t h m so fa s s o c l a t i o n r u l e sa n dh y p e r c l i q u em i n i n g a bs t r a c t d a t am i n i n gt e c h n o l o g yh a sb e e nah o tt a s ki nt h ea r e a so fd a t a b a s e a n da r t i f i c i a li n t e l l i g e n c ei nr e c e n ty e a r s ，a n di th a sa t t r a c t e de x t e n s i v e a t t e n t i o ni ns c i e n c ea n di n d u s t r yf i e l d t h em a i np u r p o s eo fd a t am i n i n g i st oe x t r a c ti m p l i c i t ，p r e v i o u s l yu n k n o w n ，a n d p o t e n t i a l l y u s e f u l i n f o r m a t i o no u to fl a r g ea m o u n t so fc o l l e c t e dd a t a a s s o c i a t i o nr u l e s o r i g i n a t e df r o mt h ea n a l y s i so f ft h es u p e r m a r k e ts h o p p i n gc a r t ，a n da r e m a i n l yu s e d t os e a r c hf o rr e l a t i o n s h i p a m o n gi t e m si n ad a t as e t a s s o c i a t i o nr u l e si so n eo ft h ei s s u e st h a ts t u d ya th e a d m o s ti nd a t a m i n i n g ，a n da l s o ah o tr e s e a r c hd i r e c t i o n a s s o c i a t i o nr u l e sc a nb e e x t e n s i v e l ya p p l i e di nm a n yf i e l d s ，i ti sn o to n l yc a nc h e c kt h ep a t t e r n so f k n o w l e d g ew h i c ha r el o n g e s t a b l i s h e di nt h ei n d u s t r y ，b u ta l s oc a nf i n d s o m en e wr u l e sw h i c ha r eh i d d e nb e f o r e o n eo ft h ei m p o r t a n tr e s e a r c h a s p e c t so fd a t am i n i n g i sh o wt of i n de f f e c t i v ew a yt o d i s c o v e r ， a p p r e h e n da n da p p l ya s s o c i a t i o nr u l e s i nt h eb a c k g r o u n do fd a t am i n i n ga n da s s o c i a t i o nr u l e sm i n i n g ，t h i s p a p e rd e v e l o p sr e s e a r c ho nt h em e t h o do fa s s o c i a t i o nr u l e sm i n i n g f i r s t ， w ea n a l y z e da n dd i s c u s s e dt h ee m e r g e n c ea n dd e v e l o p m e n to ft h ed a t a m i n i n gt e c h n o l o g y ，t h eb a s i cp r o c e s so fd a t am i n i n g ，t h em a i nt a s ko f d a t am i n i n g ；t h e ni n t r o d u c et h eb a s i cc o n c e p to fa s s o c i a t i o nr u l e s ，t h e a l g o r i t h m r e s e a r c ho fa s s o c i a t i o nr u l e s m i n i n g ，t h ee x p a n s i o na n d a p p l i c a t i o n o fa s s o c i a t i o nr u l e s m i n i n g ，t h eh o r i z o n t a l a n dv e r t i c a l d i s t r i b u t i o no fd a t as e t ；a n a l y s i so ft h ec l a s s i c a lm e t h o d so fa s s o c i a t i o n r u l e sm i n i n ga l g o r i t h ma p r i o r ia l g o r i t h ma n dr e l i ma l g o r i t h mw h i c hi s e a s i l yi m p l e m e n t e d w ef o c u so nt h eh c o n f i d e n c em e a s u r e si na s s o c i a t i o nr u l e sm i n i n g i i i a n dd i s c u s st h ec o n c e p to ft h eh c o n f i d e n c e ，h y p e r c l i q u ep a t t e m sa n d c r o s s - s u p p o r t t h e np r e s e n taw a yo ft r a n s a c t i o ns p l i t t i n gi nh y p e r c l i q u e m i n i n g t o p r e p r o c e s s t r a n s a c t i o n d a t a b a s e ，d i s c u s s h o wt om a k e t r a n s a c t i o ns p l i t t i n ga n di t sc o r r e c t n e s sp r o v e i nf a c t ，w h e nw em i n e a s s o c i a t i o nr u l e sb a s e do ni n t e r e s t i n gm e a s u r e s ，w ec o u l du s et r a n s a c t i o n s p l i r i n g t o p r e p r o c e s st h et r a n s a c t i o nd a t a b a s ei ft h em e a s u r eh a st h e c r o s s 。s u p p o r tp r o p e r t y i nt h i sp a p e r ，w ep r e s e n tt h eh y p e r c l i q u ea n dm a x i m a lh y p e r c l i q u e m i n i n ga l g o r i t h mw h i c ha r ei m p r o v e df r o ma l g o r i t h mr e l i m a n do u r e x p e r i m e n t ss h o w t h a tt r a n s a c t i o ns p l i t t i n gi sa l le f f e c t i v ew a yt oi m p r o v e t h eh y p e r c l i q u em i n i n ga l g o r i t h m o u rm a x i m a lh y p e r c l i q u em i n i n g a l g o r i t h mh a sag o o dp e r f o r m a n c ei ns p a r s ed a t as e tt o l db ye x p e r i m e n t s a f t e ra l a r g e n u m b e ro fe x p e r i m e n t so n a p r i o r i ，r e l i m a n d f p - g r o w t hb yd i f f e r e n to r d e ro fi t e m si nat r a n s a c t i o n ，a n ds t u d yt h e r e s u l to fe x p e r i m e n t s ，w ep r e s e n tab a l a n c er u l e si na s s o c i a t i o nr u l e s m i n i n g ，t h em o r ec l o s et oa v e r a g eo ft h eo u t p u to ff r e q u e n ti t e m s e t s w h i c hi sd i v i d e db yi t sf i r s ti t e m ，t h em o r ee f f e c t i v eo ft h ea l g o r i t h m t h i sr u l eh e l p su st oi m p r o v ee x i s t i n ga l g o r i t h ma n df i n dn e wa l g o r i t h m k e yw o r d s ：d a t am i n i n g ；a s s o c i a t i o nr u l e s ；h y p e r c l i q u ep a t t e r n s , t r a n s a c t i o ns p l i t t i n g ；c r o s s - s u p p o r t ；b a l a n c er u l e s 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：名煎 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密 论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：霹丝 日期：2 型z ：2 ：丛 导师签名： 北京邮电人学硕士学位论文关联规则与超团挖掘算法研究 1 1研究背景 第一章绪论 数据收集和数据存储技术的快速进步使得各组织机构可以积累海量数据。如 何自动、充分利用这些海量数据，提取有用的信息已经成为巨大的挑战。通常， 由于数据量太大，无法使用传统的数据分析工具和技术处理它们。有时，即使数 据集相对较小，由于数据本身的非传统特点，也不能使用传统的方法处理。在另 一些情况下，需要回答的问题不能使用已有的数据分析技术来解决n 1 。数据挖掘 技术( d m ，d a t am i n i n g ) 正是在这样的背景下孕育而生的，它通常也被称为数据 库中知识发现技术( k d d ，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 ) 。关联规则是数据挖 掘研究中最活跃，最深入的领域之一。本文在数据挖掘背景下展开了对关联规则 挖掘算法的一些研究及其相关工作，取得了一些积极有意义的成果。 1 1 1 数据挖掘的产生与发展 数据挖掘比较公认的定义是由u m f a y y a d 等人提出的：数据挖掘就是从大 型数据集( 可能是不完全的、有噪声的、不确定的、各种存储形式的) 中提取出 人们感兴趣的知识，这些知识是隐含的、先前未知的、对决策有潜在价值的，提 取的知识表示为概念、规则、规律和模式等形式。简单而言就是从数据中提取或 挖掘知识。它兴起于上世纪八十年代末，并于上世纪九十年代获得重大发展。当 前相关的国际顶尖重要学术会议有：s i g k d d 、i e e ei c d m 、p a k d d 、p k d d 、 i e e ei c m l 、v l d b 、i c d e 、s i a m d m 等。 随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储的 数据量急剧增大。在大量的数据背后隐藏着许多重要信息，而这些重要信息可以 很好地支持人们的决策。目前数据库系统所能做到的只是对数据库中已有的数据 进行存取，人们通过这些数据所获得的信息量仅仅是整个数据库所包含的信息量 的一部分，隐藏在这些数据之后的更重要的信息是关于这些数据的整体特征的描 述及其发展趋势的预测，这些信息在决策生成的过程中具有重要的参考价值。因 此人们对数据处理技术的要求也不断提高，需要能够对数据进行更深层次的处 理，以得到关于数据的总体特征以及对发展趋势的预测。 例如：超市的经营者希望将经常被同时购买的商品放在一起，以增加销售量： 保险公司想知道购买保险的客户一般具有哪些特征；医学研究人员希望从已有的 北京邮电大学硕二l 学位论文关联规则与超团挖掘算法研究 成千上万份病例中找出患某种疾病的病人的共同特征，从而为治愈这种疾病提供 一些帮助。对于上述问题，传统的数据库管理系统来说是无法做到的，并且目前 用于对这些数据进行分析处理的工具也很少。 事实上，数据仅仅是人们观察客观世界所得到的原始材料，本身没有太多意 义，它只是描述发生了什么事情，并不能构成决策的可靠基础。通过对数据进行 分析找出其中的关系，并赋予数据某种意义和关联，即形成所谓的信息。信息虽 然给出了数据中一些有一定意义的东西，但是它往往和人们需要完成的任务没有 直接联系，也还不能作为决策的依据。对信息进行再加工，进行更深入的分析， 方能获得更有用的信息，即知识乜1 。因此从数据到信息，再到知识，是需要经过 分析加工处理精炼的过程。然而数据量的爆炸性增长使得现在的用户很难再像从 前那样依靠经验、大量的计算和人脑的指挥来人工找出关于数据较为全面的知 识，许多知识仍然隐含在数据中而不能被发现和利用，造成数据资源的浪费。正 如j o h nn a i s b e t t 所说：“我们已被信息所淹没，但是却正在忍受缺乏知识的煎熬。 二十世纪八十年代，数据仓库和数据挖掘( d a t am i n i n g , d m ) 等信息处理技术 正是为解决这一问题而产生并迅速发展起来的。 历经了十几年的发展，基于统计学、人工智能等在内的理论与技术性成果已 经被成功的应用到商业处理和分析中。这些应用从某种程度上为数据挖掘技术的 提出和发展起到了极大地推动作用。数据挖掘系统的核心模块技术和算法都离不 开这些理论和技术的支持。从某种意义上讲，这些理论本身的发展和应用为数据 挖掘提供了有价值的理论和应用积累。数理统计是一个有着几百年发展历史的应 用数学学科，然而它和数据库技术的结合性研究应该说最近十几年才被重视。以 前的数理统计方法的应用大多是通过专用程序来实现的。而且，大多数的统计分 析技术是基于严格的数学理论和高超的应用技巧的，这使得一般的用户很难从容 的驾驭它。数据挖掘技术实际上是数理统计分析应用的延伸和发展1 ，而概率论 和数理统计则为数据挖掘技术提供了理论基础。 人工智能是计算机科学研究中争议最多但仍始终保持强大生命力的研究领 域。机器学习应该说是得到了充分的研究和发展，并且数据挖掘技术继承了机器 学习解决问题的思想。专家系统( e x p e r ts y s t e m ) 曾经被认为是人工智能向着实 用性方向发展的最有希望的技术，但是，这种技术也逐渐表现出投资大、主观性 强、应用面窄等致命弱点。例如，知识获取被普遍认为是专家系统研究中的瓶颈 问题。另外，由于专家系统是主观整理知识，因此这种机制不可避免地带有偏见 和错误。数据挖掘继承了专家系统的高度实用性特点，并且以数据为基本出发点， 客观地挖掘知识。因此，可以说，数据挖掘研究在继承已有的人工智能相关领域 的研究成果的基础上，摆脱了以前象牙塔式的研究模式，真正开始客观地从数据 2 北京邮电大学硕十学位论文关联规则与超团挖掘算法研究 集中发现蕴藏的知识。特别的，数据挖掘可看作数据库理论和机器学习的交叉学 科，数据库技术侧重于对数据存储处理的高效率方法的研究，而机器学习则侧重 于设计新的方法从数据中提取知识。数据挖掘利用数据库技术对数据进行前端处 理，而利用机器学习方法从处理后的数据中提取有用的知识。 因此，数据挖掘作为一门新兴的研究领域，涉及到诸如机器学习、模式识别、 统计学、数据库、人工智能、数学和可视化技术等众多学科，是一个多学科相互 交叉融合所形成的一个新兴的具有广泛应用前景的研究领域。二十世纪九十年代 数据挖掘成为数据库界的热门话题。1 9 9 1 、1 9 9 3 和1 9 9 4 年又接连举行数据挖掘 专题讨论会。随着参加会议人数的增多，1 9 9 5 年，a c m 成立了s i g k d d 专业组， 并开始每年举办一次有关数据挖掘技术的国际会议。另外从1 9 9 7 年开始，数据 挖掘也拥有了自己的专门杂志 k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) ) 。数据挖 掘虽然只有十几年的历史，然而由于其极大的潜在使用价值，使得数据挖掘技术 已经深入到许多领域，并已经开发出了许多成功的产品，得到了业界的广泛关注。 较有代表性的数据挖掘工具主要有：美国k a n s a s 大学开发的l e r s 系统；美国 s p s s 公司著名的数据挖掘工具箱c l e m e n t i n e ；加拿大s i m o nf r a s e r 大学的 d b m i n e r ；i b m 公司的q u e s t 系统；s a s 公司的s a se m ( e n t e r p r i s em i n e r ) 系统等。数据挖掘广泛用于下列领域：科学研究、市场营销、金融投资、风险评 估、欺诈识别、产品制造、通信网络管理、医学应用、网络应用等。 1 1 2 数据挖掘的基本过程 数据挖掘是从大量数据中抽取未知的，有价值的模式或规律等知识的复杂过 程。简单的说，一个典型的数据挖掘过程可以分成四个阶段，即数据预处理、数 据挖掘、模式评估及知识表示。数据预处理阶段又可再分为数据清理，数据集成， 数据选择，数据变换四个方面。数据挖掘阶段包括挖掘算法的选择和算法参数的 确定等。模式评估阶段是对得到的模式进行评价、训练和测试。这三个阶段是循 环往复的过程，直到得到用户满意的模式为止。数据挖掘过程是交互的，需要用 户特别是领域专家的参与。 具体地说，我们可以把数据挖掘过程细分为以下几个步骤n 3 ： 1 ) 数据清理( 消除噪声或不一致数据) 2 ) 数据集成( 多种数据源组合在一起) 3 ) 数据选择( 从数据库中提取与分析任务相关的数据) 4 ) 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作) 5 ) 数据挖掘( 基本步骤，使用智能方法提取数据模式) 北京邮电大学硕： ：学位论文 关联规则与超团挖掘算法研究 6 ) 模式评估( 根据某种兴趣度度量、识别表示知识的真正有趣的模式) 7 ) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 1 1 3 数据挖掘的任务挖掘什么类型的模式 通常，数据挖掘的任务分为两大类：预测任务和描述任务。预测任务的目 标是根据其他属性的值，预测特定属性的值。被预测的属性一般称为目标变量 ( t a r g e tv a r i a b l e ) 或因变量( d e p e n d e n tv a r i a b l e ) ，而用来做预测的属性称为说明 变量( e x p l a n a t o r yv a r i a b l e ) 或自变量( i n d e p e n d e n tv a r i a b l e ) 。描述任务的目标是 导出概括数据中潜在联系的模式( 相关、趋势、聚类、轨迹和异常) 。本质上， 描述性数据挖掘任务通常是探查性的，并且常常需要后处理技术的验证和结果解 释。 具体而言，数据挖掘任务又可分为概念类描述( c o n c e p t c l a s sd e s c r i p t i o n ) 、 关联分析( a s s o c i a t i o na n a l y s i s ) 、分类和预测( c l a s s i f i c a t i o na n dp r e d i c t i o n ) 、聚 类分析( c l u s t e r i n ga n a l y s i s ) 、孤立点分析( o u t l i e ra n a l y s i s ) 、演变分析( e v o l u t i o n a n a l y s i s ) 等钔。 1 1 3 1 概念类描述 数据可以与类或概念相关联。用汇总的、简洁的和精确的方式描述各个类和 概念是有用的，这种类或概念的描述称为类概念描述。这种描述可以通过下述 方法得到：数据特征化，对目标类数据的一般特性或特征的汇总，描述目标类的 共同特征；数据区分，将目标类与一个或多个可比较类进行比较，描述不同目标 类之间的区别。 1 1 3 2 关联分析 从广义上讲，关联分析是数据挖掘的本质。既然数据挖掘的目的是发现潜藏 在数据背后的知识，那么这种知识一定是反映不同对象之间的关联。它集中在数 据库中对象之间关联及其关联程度的刻画。 关联知识反映一个事件和其他事件之间的依赖或关联。数据库中的数据一般 都存在着关联关系，也就是说，两个或多个变量的取值之间存在某种规律性。数 据库中的数据关联是现实世界中事物联系的表现。数据库作为一种结构化的数据 组织形式，利用其依附的数据模型可能刻画了数据问的关联。但是，数据之间的 4 北京邮电大学硕十学位论文关联规则与超团挖掘算法研究 关联是复杂的、有时是隐含的。 关联分析的目的就是要找出数据库中隐藏的关联信息。这种关联关系有简单 关联、时序关联、因果关联、数量关联等。这些关联并不总是事先知道的，而是 通过数据库中数据的关联分析获得的，因而对商业决策具有新价值。简单关联， 例如：购买面包的顾客中有9 0 的人同时购买牛奶。时序关联，例如若a t & t 股票连续上涨两天且d e c 股票不下跌，则第三天i b m 股票上涨的可能性为7 5 。 它在简单关联中增加了时间属性。 关联规则挖掘晦1 是关联知识发现的最常用方法。最为著名的是a g r a w a l 等人 提出的a p r i o r i 及其改进算法。为了发现有意义的关联规则，需要给定两个阈值： 最小支持度( m i n i m u ms u p p o r t ) 和最小置信度( m i n i m u mc o n f i d e n c e ) 。挖掘出 的关联规则必须满足用户规定的最小支持度，它表示了一组项目关联在一起需要 满足的最低联系程度。挖掘出的关联规则也必须满足用户规定的最小置信度，它 反映了一个关联规则的最低可靠程度。在这个意义上，数据挖掘系统的目的就是 从数据库中挖掘出满足最小支持度和最小置信度的关联规则。关联规则的研究和 应用是数据挖掘中最活跃和比较深入的分支，已经提出了许多关联规则挖掘的理 论和算法。 1 1 3 3 分类和预测 分类是数据挖掘中的一个重要的目标和任务。目前的研究在商业上应用最 多。分类就是对数据的过滤、抽取、压缩以及概念提取等。分类的目的是学会一 个分类函数或分类模型( 也常常称作分类器) 。由于数据挖掘是从数据中挖掘知 识的过程，因此要构造这样一个分类器。分类器的作用就是能够根据数据的属性 将数据分派到不同的组中，即：分析数据的各种属性，并找出数据的属性模型， 确定哪些数据属于哪些组。这样我们就可以利用该分类器来分析已有数据，并预 测新数据将属于哪一个组，即数据对象的类标记。然而，在某些应用中，人们可 能希望预测某些空缺的或不知道的数据值，而不是类标记。当被预测的是数值数 据时，通常称之为预测。分类模式可以采用多种形式表示，如分类( i f t h e n ) 规则，判定树，数学公式或神经网络n 3 。可以应用于分类知识挖掘的一些有代表 性的技术有：决策树、贝叶斯分类、神经网络分类、遗传算法、类比学习和案例 学习，以及粗糙集和模糊集等方法。 分类应用的实例很多。例如，我们可以将银行网点分为好、一般和较差三种 类型，并以此分析这三种类型银行网点的各种属性，特别是位置、盈利情况等属 性，并决定它们分类的关键属性及相互间关系。此后就可以根据这些关键属性对 北京邮电大学硕1 ：学位论文关联规则0 超团挖掘算法研究 每一个预期的银行网点进行分析，以便决定预期银行网点属于哪一种类型。 1 1 3 4 聚类分析 一般把学习算法分成有导师( 或监督) 和无导师学习两种方式，主要区别是 有没有类信息作为指导。聚类是典型的无导师学习算法，一般用于自动分类。数 据挖掘的目标之一就是进行聚类分析。聚类就是将数据对象分组成为多个类或 簇，同一个类中的对象相似度最大化，而不同的类中的对象差别最大化。一般情 况下，聚类分析不要求训练数据提供类标记，聚类可以用于产生这种标记。聚类 分析生成的类标记( 可能以某种容易理解的形式展示给用户) 刻画了数据所蕴含 的类知识。聚类按照某个特定标准( 通常是某种距离) ，最终形成的每个类，在空 间上都是一个稠密的区域。所形成的每个类可以导出规则。通过聚类技术可以把 数据划分为一系列有意义的子集，进而实现对数据的分析。例如，一个商业销售 企业，可能关心哪些( 同类) 客户对制定的促销策略更感兴趣。聚类分析与分类 和预测的不同在于，前者通过对数据的分析比较生成新的类标记；而后者总是在 类标记下寻求新元素属于哪个类。 当然，数据挖掘中的分类和聚类技术都是在已有的技术基础上发展起来的， 它们互有交叉和补充。聚类技术主要是以统计方法、机器学习、神经网络等方法 为基础的。常用的聚类算法有基于划分、层次、密度、网格和模型的五大类聚类 算法。作为统计学的一个重要分支。聚类分析有很广泛的应用，包括市场或客户 分割、模式识别、生物学研究、空间数据分析、互联网文档分类及许多其它方面。 1 1 3 5 孤立点分析 孤立点分析也翻译为离群点分析，在数据挖掘领域也称为异常检测。一个数 据库中的数据一般不可能都符合分类预测或聚类分析所获得的模型。那些不符合 大多数数据对象所构成的规律或模型的数据对象就被称为孤立点。在挖掘正常类 知识时，通常总是把它们作为噪音来处理。因此以前许多数据挖掘方法都在正式 进行数据挖掘之前就将这类孤立点数据作为噪声或者意外而将其排除在数据挖 掘的分析处理范围之外。然而在一些应用场合中，如信用欺诈、入侵检测等小概 率发生的事件往往比经常发生的事件更有挖掘价值。因此当人们发现这些数据可 以为某类应用提供有用信息时，就为数据挖掘提供了一个新的研究课题，即孤立 点分析。 发现和检测孤立点的方法目前主要有基于概率统计、基于距离度量和基于偏 6 北京邮电大学硕十学位论文关联规则与超团挖掘算法研究 差检测技术这三类方法。基于概率统计的，先假定一个数据分布或概率模型，再 使用统计检验检测孤立点；基于距离度量的，将远离任何簇的对象视为孤立点； 基于偏差的方法则通过考察一群对象主要特征上的差别来识别孤立点。 1 1 3 。6 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。尽管 这可能包括时间相关数据的特征化、区分、关联和相关分析、分类、预测或聚类， 这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于相似性 的数据分析。 例如你有纽约股票交易所过去几年的主要股票市场交易( 时间序列) 数据， 并希望投资高科技产业公司的股票。股票交易数据挖掘研究可以识别整个股票市 场和特定公司的股票演变规律。这种规律可以帮助预测股票市场价格的未来走 向，帮助你对股票投资做出决策。 1 1 4 关联规则挖掘 条形码技术的发展以及商场p o s 机的设置使得超级市场存储了数以万计的 数据记录，这些记录详细记录了每个客户每次交易的时间、商品、数量和价格等 信息，从而为关联规则挖掘提供了充足的数据基础。关联规则挖掘最初由 r a g r a w a l ，t i m i e l i n s k i 和a s w a m i 提出踊1 ，主要应用于事务数据库，用来发现 超级市场中用户购买的商品之间的隐含关系，即关联规则，以便为商场的决策提 供依据。这些规则用于找出顾客的购买行为模式，如购买了某一商品对购买其他 商品的影响。决策者可以根据关联规则提供的信息进行合理的商品货架设计和货 存安排来优化商场布置( 例如：把用户经常购买的商品摆放在一起) ，在商品销 售方面做各种促销活动和广告宣传，以及根据购买模式对用户进行分类，再对不 同用户采用不同的宣传策略。 关联规则虽然来源于p o s 机中，但是可以应用于很多其他领域。例如在商 场的顾客购物分析、商品广告邮寄分析、网络故障分析等领域应用关联规则提供 的知识。沃尔玛零售商的“尿布与啤酒”的故事是关联规则挖掘的一个成功典型 案例。总部位于美国阿肯色州的沃尔玛零售公司拥有世界上最大的数据仓库系 统，它利用数据挖掘工具对数据仓库中的原始交易数据进行分析，得到了一个意 外发现：跟尿布一起购买最多的商品竟然是啤酒。如果不是借助于数据仓库和数 据挖掘，商家决不可能发现这个隐藏在背后的事实：在美国，一些年轻的父亲下 7 北京邮电人学硕上学位论文关联规则与超团挖掘算法研究 班后经常要到超市去买婴儿尿布，而他们中有3 0 4 0 的人同时也为自己买一 些啤酒。有了这个发现后，超市调整了货架的摆放，把尿布和啤酒放在一起，明 显增加了啤酒的销售额。 1 1 4 1关联规则挖掘概念 关联规则是形如x y 的规则，关联规则挖掘找出支持度和置信度分别大于 或等于用户指定的最小支持度和最小置信度的关联规则。关联规则的挖掘工作可 以分成两个步骤，第一个步骤是从事务数据集合中发现所有满足用户给定的最小 支持度的频繁项集；第二个步骤是在频繁项集的基础上生成所有满足用户给定的 最小置信度的关联规则。第一个步骤几乎集中了所有的计算量，第二个子问题的 解决是直截了当的，所以目前的大部分工作都集中在第一个子问题上。其主要原 因是数据量巨大所造成的，算法的效率以及可扩展性都具有很强的挑战性，解决 这一问题的最著名算法是r a g r a w a l 提出的a p r i o r i 算法以及它的变种a p r i o r i t i d 和a p r i o r i h y b r i d 算法。此外，人们提出了如d h p 、p a r t i t i o n 、s a m p l i n g 和f p - g r o w t h 等多种关联规则挖掘算法。第二步虽然很简单，但通常算法所返回的结果都非常 庞大，而且还可能伴随着错误信息，如何从大量规则中找到有意义的规则，让用 户更方便地解释和理解规则也非常重要。现在通常称第一个子问题为经典关联规 则挖掘问题。关联规则挖掘问题主要集中在对经典关联规则挖掘算法的改进方 面，主要集中在以下几个方面：减少候选项集的生成数量；挖掘频繁集的紧凑表 示形式( 闭频繁项集，最大频繁项集) ；采用不需要候选项集的思路提高算法挖 掘效率等。 1 1 4 2 关联规则挖掘算法 关联规则挖掘工作的一个关键问题就是从事务数据库中发现所有满足用户 给定的最小支持度的频繁项集，这一步骤几乎集中了所有的计算量。解决关联规 则问题的原始算法是r a k e s ha g r a w a l 等人提出的a i s 算法。为改进a i s 算法， h e i k k im a n n i l a 等人提出了o c d 算法，o c d 算法利用上一次搜索的组合信息来 减少本次候选项集的产生数量。后来，r a k e s ha g r a w a l 提出了关联规则挖掘中最 著名的a 研o d 算法以及它的变种a p r i o r i t i d 和a p r i o r i h y b r i d 算法来发现频繁项 集。 其后，许多学者都提出了关联规则频繁项集的发现算法，但大多数算法都是 a p r i o r i 算法的变种或者是其改进。j s p a r k 等人提出了一个基于h a s h 技术的d h p 8 北京邮电大学硕士学位论文关联规则- j 超团挖掘算法研究 算法嘲，利用h a s h 技术有效改进候选项集的生成过程，减少i o 的存取时间， 其效率高于a p r i o r i 算法。a s a v a s e r e 等人提出了对事务数据进行分区的p a r t i t i o n 算法口1 ，p a r t i t i o n 算法首先把数据库分成多个分区，然后在每个分区上寻找频繁 项集，最后得到整个数据库上的频繁项集，算法只需要对数据库扫描2 遍。 h t o i v o n e n 等人提出了基于随机抽样技术的s a m p l i n g 算法跚，从数据库中随机抽 样出一部分数据寻找频繁项集，再在整个数据集合中寻找频繁项集，算法最多对 数据库扫描2 遍。s b r i n 等人提出了对候选集进行动态计算的d i c 算法嘲，该算 法比s a m p l i n g 计算更少的频繁项集，效率更高。 由于a p r i o r i 算法是一个多趟搜索算法，对于海量数据集合，每搜索一次， 都要读取外存一次，i o 开销很大。因此大多改进算法，都在如何减少搜索次数 上做文章。事实上，真正影响以a p r i o r i 算法为基础的经典关联规则发现算法效 率的原因是对项集及其支持度的计算问题，如果在事务数据集合中存在包含n 个 不同项组成的频繁项集，以a 砸嘶为基础的频繁项集发现算法将要计算2 n 个项 集。当n 比较大时，将会产生组合爆炸，变为n p 难的问题。因而只有从本质上 减少生成不必要的候选项集，减少对项集的支持度的计算时间，才能大大减少频 繁项集生成的数量和缩短数据挖掘时间。 为此，一系列的学者提出了不同于a p r i o r i 方法且可伸缩的频繁项集发现算 法。j w h a n 等人提出的f p 增长是一种挖掘频繁项集而不产生候选项集的模式 增长算法n 0 1 。h m i n e 是由j p e i 等人提出的一种频繁模式的混合结构探查算法n u 。 k b o r g e l t 提出了非常类似于h m i n e 的但却非常易于实现的r e l i m 算法n 羽。 e c l a t 是由z a k i 提出的一种通过探查垂直数据格式来挖掘频繁项集的算法n 3 1 。 上述这些算法虽然不需要产生候选项集，在一定程度上减轻了项集支持度的计算 时间，但在含有长度为n 的频繁项集的事务集中，还是存在得到2 n 个频繁子项 集的问题。 为了解决长模式挖掘导致的组合爆炸这一问题，学者们又提出了闭频繁项集 n 4 1 和最大频繁项集n 5 1 这两个概念，它们是频繁模式的一种紧凑表示，避免了组合 爆炸问题。p a s q u i e r 提出了一个基于a p r i o r i 的闭频繁项集的挖掘算法a c l o s e 算 法引。c l o s e t 是一种基于频繁模式增长的有效的闭频繁项集挖掘算法n 引，由 p e i ，h a n 和m a o 提出，并在w a n g ，h a n 和p e i 中进一步提炼为c l o s e t + n 引。 一种使用模式增长方法挖掘闭项集的基于前缀树的算法称作f p c i o s e n9 l ，由 g r a h n e 和z h u 提出。一种使用垂直数据格式挖掘闭频繁项集的算法扩展称作 c h a r m 啪，由z a k i 和h s i a o 提出。b a y a r d o 首先提出并研究了最大频繁项集的 挖掘方法，一种使用垂直数据格式挖掘最大频繁项集的有效方法称作m a f i a 心， 由b u r d i c k ，c a l i m l i m 和g e h r k e 提出。 9 北京邮电人学硕士学位论文关联规则0 超团挖掘算法研究 1 1 4 3 关联规则挖掘工作的扩展和应用 关联规则挖掘问题还包含对经典关联规则的扩展和应用方面( 例如：规则的 约束和限制、新的判断标准和兴趣尺度、与其它数据挖掘算法的结合等) 。 1 ) 意外或例外关联规则的挖掘 传统的关联规则挖掘算法，一般用来发现数据库中大多数数据所遵循的规 律，但同时在数据库中还存在另外一些规律，这些规律是由少数数据所维持的， 其支持度要小于一般关联规则的支持度，用传统的关联规则挖掘算法无法发现这 些规则，而这些规则又常常容易被人们所忽视。由于这些规则出乎人们的意料之 外，所以称它们为意外或例外规则( e x c e p t i o nr u l e s ) ，例外关联规则在某些场合 常常有很大的价值。 2 ) 数字属性或量化关联规则的挖掘研究 经典的关联规则挖掘是指布尔类型的规则，然而现实生活中除了布尔属性 外，还有数字属性( 或量化属性，例如：年龄、工资、生产量和工程量等) 和分 类属性( 例如：民族、国籍和职业等) 的数据。为处理这类属性的数据，提出了 数字属性的关联规则挖掘问题。 3 ) 基于限制和约束的关联规则挖掘 传统的关联规则存在如下缺点：缺乏用户的参与和控制。用户没有一定的目 的，用户只能被动地等待挖掘结果，对海量数据集合来讲，使用一般的关联规则 挖掘算法挖掘出来的规则数量将会很大，甚至成千上万，这对用户理解、解释和 使用规则将带来不便，而且其中大多数规则对用户来讲是无用的或者是用户不感 兴趣的。所以简单利用最小支持度和最小置信度来限制关联规则便显得有点力不 从心了，于是学者提出了许多限制或约束关联规则的方法，以减少算法生成的规 则的数量心副。 4 ) 并行关联规则的挖掘算法研究 数据库一般规模很大而且经常分布在若干站点上，为了加快关联规则的挖掘