（计算机应用技术专业论文）基于图的关联规则挖掘算法研究.pdf

硕士学位论文 m a s t e r st h e s i s 中文摘要 随着计算机科学技术的飞速发展，数据挖掘技术成为数据库、数据仓库领域最 前沿的研究方向之一，它作为信息科学领域的前沿研究课题之一，是解决数据丰富 而知识贫乏的有效途径，关联规则挖掘是数据挖掘中的一个重要领域，它在各个领 域广泛应用，既可以发现隐藏的新规律，也能够检验长期形成的知识模式，有效的 发现、理解、运用关联规则是完成数据挖掘重要手段。随着市场新需求不断提出， 关联规则挖掘技术需要可靠的、有效的数据挖掘评估体系。 在关联规则挖掘中，挖掘频繁项目集是最关键的问题，所以我们的主要目标就 是去发现最大频繁项目集。本文主要对如果有效的挖掘频繁项目集做了研究。 本文首先介绍了数据挖掘的基本概念、分类和主要任务，其次介绍了关联规则 的相关定义、挖掘步骤及其分类。然后详细描述分析了经典关联规则挖掘算法 a p r i o r i 算法和f p g r o w t h 算法，分析了各自的应用领域和优缺点，并对二者作了对 比。 本文的主体部分主要是研究基于图的关联规则挖掘，为了解决a p r i o r i 算法在 候选项目集和执行时间方面存在的问题，根据已有基于图关联规则挖掘算法d l g ， 提出了改进的算法，通过三个方面的改进，提高了挖掘频繁项目集的效率。达到了 算法改进的目的。 关键词：数据挖掘；关联规则；频繁项目集：频繁候选集 a b s t r a c t a st h er a p i dd e v e l o p m e n to ft h ec o m p u t e rt e c h n o l o g y , d a t am i n i n gt e c h n o l o g yi s o n eo ft h em o s ta d v a n c e dr e s e a r c hd i r e c t i o i l si nd a t a b a s ea n dd a t aw a r e h o u s ef i e l d s i ti s a l le f f e c t i v ea p p r o a c ht or e s o l v et h ep r o b l e mo fa b u n d a n td a t aa n ds c a n t yi n f o r m a t i o na n d i ti sc u r r e n t l yt h ef r o n t i e ri nt h ei n f o r m a t i o ns c i e n c ef i e l d t h ea s s o c i a t i o nr u l e sm i n i n gi s a ni m p o r t a n tr e s e a r c hs u b j e c ti nd a t am i n i n gf i e l d i ti sw i d e l yu s e di ne a c hf i e l dw h i c h c a nb o t hd i s c o v e rt h eh i d d e nn e wr u l e sa n de x a m i n et h el ( n o w l e d g ep a t t e r no fl o n g t e r m i n f o r m a t i o ni n s i d et h ep r o f e s s i o nf i e l d t od i s c o v e re f f e c t i v e l y , c o m p r e h e n da n du s et h e a s s o c i a t i o nr u l ei st h ei m p o r t a n tm e t h o dt of i n i s hm i n i n gd a t a a sn e wr e q u i r e m e n t c o n t i n u o u s l ya l o n gw i t ht h em a r k e tb r i n gf o r w a r d , d a t am i n i n gt e c h n o l o g yn e e d sah i g h p e r f o r m a n c ea n dd e p e n d a b l ed a t am i n i n ga l g o r i t h m i nt h ef i e l do fm i n i n ga s s o c i a t i o nr u l e f i d i n gm a x i m a lf r e q u e n ti t e m s e t si st h ek e y p r o b l e mw em u s tf a c e s oo u rm a i ng o a li st o f i n dm a x i m u mf r e q u e n ti t e m s e t si n t r a n s a c t i o nd a t a b a s e ，t h i sp a p e rm a i n l yd i s c u s sh o wt om i n i n gm a x i m u mf r e q u e n t i t e m s e t se f f e c t i v e l yi nd a t a b a s e t h i sp a p e rf i r s t l yi n t r o d u c e st h eb a s i cc o n c e p t i o n , s o r t sa n dm i s s i o no fd a t am i n i n g ， a n dt h ed e f i n i t i o n , m i n i n gp r o c e d u r e sa n dk i n d so fa s s o c i a t i o nr u l e s t h e n , t h ep a p e r e x p a t i a t e so nt h ec l a s s i c a la s s o c i a t i o nr u l e sm i n i n ga l g o r i t h m s ：a p r i o r ia l g o r i t h ma n d f p g r o w t ha l g o r i t h m t h e na n a l y s i z et h e i ra p p l i c a t i o na r e a , a d v a n t a g e sa n dd i s a d v a n t a g e s ， a n dm a k eac o m p a r i s o nb e 帆e e nt h e m t h em a i np a r t so ft h i sp a p e rr e f e r st ot h er e s e a r c ho fa s s o c i a t i o nr u l e sm i n i n g a l g o r i t h mb a s e do ng r a p h t oo v e r c o m et h ep r o b l e m sw h i c he x i s ti na p f i o f ia l g o r i t h m s ， t h i sp a p e rp r e s e n t si m p r o v e d1 0 d l ga l g o r i t h mb a s e do ne x i s t i n ga s s o c i a t i o nr u l e s m i n i n ga l g o r i t h m sd l g ，i tw a si m p r o v e do nt h r e ea s p e c t sw h i c he n h a n c e t h ee f f i c i e n c y o fm i n i n gf r e q u e n ti t e m s e t s t h e no u rp u r p o s ei sa c h i e v e d 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 ；f r e q u e n ti t e m s e t s ；t h ec a n d i d a t e so f t h e f r e q u e n tp a t t e r n 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 肆矸欠 日期：m ? 年月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名：霞钦 日期：如p 7 年6 月7 日 导师叛截叩 嘲川卜月夕日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程中的 规定享受相关权益。圃童途塞握交卮进卮! 旦坐生l 旦二生；旦三生发查! 器：，粤肌嚣二熟日 日期：知。1 年6 月c 日 日期： o7 年6 月7 日 硕士学位论文 m a s t e r st h e s i s 第一章绪论 数据挖掘( d a t am i n i n g ) 包括了各种各样的学科研究成果在里面，牵涉到的行业 也非常的多，集合了各个行业的成果在里面。而且它在过去多年的研究和发展中， 有了很好的基础了，在未来可言发展的比较深入。第一章绪论首先提到了本文的课 题背景，另外讲到了数据挖掘的中的重要的一部分，那就是关联规则挖掘，提到了 其研究的现实状况，在最后部分列出了结构和主要内容。 1 1 课题背景 计算机技术、数据库等等技术在过去的大半个世纪里有了高速迅猛的发展。各 个领域都积累了海量的数据，虽说人们的数据收集能力有了很大的提高，然而另一 方面，人们并没有有效的提高对大规模数据的理解能力。 但是我们平常的生活中对很多涉及到的行业信息的处理都是停留在表面阶段。 隐藏在背后的大量的、对我们用处极大的知识、规律等等都没有被我们发现。我们 基于那样的情况，非常想拥有一种强大有效的软件，通过它我们可以从海量信息背 后抽取出对我们有意义的知识，从而促进我们生活方式的改变。 数据挖掘( d a t am i n i n g ，简称d m ) 就是从上面的形势下人们慢慢的提出来的。 它可以顺应我们上面提到的一些要求，来得到对我们比较方便实用的信息。 d a t am i n i n g 这项技术可以从我们日常的使用的海量数据中，这些数据的表现形 式多种多样、比较繁杂，而且毫无规律。找到对我们有用的知识，这样可以科学的 指导我们日常生活，帮助人们有效的做出判断和决定。还可以利用原来的数据提出 对将来要发生什么的征兆，这样就避免了很多危险发生的可能性。从而给我们带来 许多方便，更加快了各行业的运营效率。 我们的数据分析工具现在在企业中运用很少，有待进一步推广，而且分析工具 都不完善。但是这个现象马上就会有改变了，因为慢慢的有很多公司开始利用这些 工具来帮助其提高效益，这样形势就马上会好起来。 在我们国家和许多其他国家的很多专家都从事着分析数据这一行业，研究这一 方面已经有些年头了，并且获得了一定的成效。特别是国外的其他国家，他们获得 了非常有成效的效果。在很多应用研究行业都向数据挖掘这边靠拢。出现了许多新 的技术分析工具，我们可以在他们的基础上进行技术研究。而且我们的行业非常多， 前途是一片光明，非常值得期待。 硕士学位论文 m a s t e r st h e s i s 本文所研究的重点是关联规则的挖掘，它是寻找知识( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) 的研究的重要内容。在数据挖掘这个领域占有非常重要的地位。我们日常 的数据量大大的增加，日积月累，针对这个情况，很多行业的人对从海量的数据中 找到感兴趣的知识非常的渴望。a g r a w a l 等人于1 9 9 3 年提出了关联规则的挖掘者个 概念。原来是针对“购物篮分析这个问题提出来的。主要是用作发现许多不同信 息或数据之间存在的联系。我们可以举不少例子，比如说可以经过购物篮的新分析 技术，可以发现这样一条规律“很多客户购买了面粉和豆油的时候购买了酱油， 这样可以促使商家或者经理更加了解客户的特性，从而科学的做到生产和销售方面 的调整，获得最大的效益。 a s s o c i a t i o nr u l e s 的适用范围非常的广，并不只是在零售这个行业才起作用的， 只是它的产生跟销售这个行业带来的要求来推动的。到现在a s s o c i a t i o nr u l e s 技术 除了保险行业、银行业务以及电子商务等行业之外，还体现在银行业、制造业、经 纪业和安全交易、保险业、计算机硬件和软件、政府和防卫、医药、交通、电信、 公安等，所以展开对关联规则的研究，对我们来说具有重大意义。在随后的发展中， 很多研究者又把它扩展到保护秘密、搜寻网页、教育学等领域。表现了很旺盛的生 命力和前途。在将来它的使用范围会越来越广，所以在这方面做深入的探讨和探寻 非常的有意义。 1 2 关联规则研究现状 a s s o c i a t i o nr u l e sm i n i n g 这个说法和相关的算法是有a g r a w a l 等学者在一九九 三年创造的。针对购物篮分析问题是最初提出此概念的动机所在，主要目的是帮助 人们去发掘商品库中不同商品之间的联系规则。发掘出来的联系规则充分体现了顾 客的购买行为模式，这样就可以用来指导零售商合理的、方便的储存、进货和销售。 在a s s o c i a t i o nr u l e sm i n i n g 中非常有名的一个例子就是“酒和尿布的故事 ，其中 的酒和尿布不同两个方面的信息，通过我们挖掘工作的分析，我们可以在这两者中 提取有用的知识，这些信息对我们都有指导作用，我们可以合理的科学的安排售货 布局，从而促进商品的销售。 国内和国外很多的专家学者对a s s o c i a t i o nr u l e sm i n i n g 这个领域做了广泛的探 讨和摸索，主要就是包括理论方面的研究、设计一些高效率的工具，对原来的工具 的改变和完善。但一般更多是主要进行理论研究、工具的改变和完善等等。研究出 了很多实用和高效率的算法，这些算法可以适用于各个不同的领域，对我们生活方 式产生了非常大的影响，有效的改善了人们的生活。 2 硕士学位论文 m a s t e r st h e s i s 我们自己国家也有这一方面的研究，很多高校都开发了自己的数据挖掘工具或 系统，这些系统中间运用到了a s s o c i a t i o nr u l e sm i n i n g 相关的算法，有的甚至对这 些算法做了很大的完善，具有非常好的成效。但是这些研究项目虽说取得了一定的 进展，但在处理海量数据时表现出了效率不佳的问题，所以我们就如何提高算法效 率、用户如何同系统进行可视化的交互，是我们亟待研究的课题。 在大量的数据集中挖掘出的关联规则适用于非常多的行业，既包含某个行业内 部的专业知识，页可以从数据中发现背后隐藏的模式。越来越多的企业、事业单位 还有服务业已经越来越多运用关联规则挖掘，显示出了其旺盛的生命力。我们预测 关联规则挖掘技术必将广泛的应用在我国的各个领域。 1 3 关联规则挖掘的未来趋势 国内外在关联规则挖掘方面的研究已经取得了不小的成就，但关联规则挖掘技 术仍然存在着某些方面的缺陷，需要我们研究者提出更优的解决方法。 l 、确立关联规则算法标准体系。 关联规则的定义非常简洁但表现形式多样化，但本质和原理几乎不会变。所以 我们可以建立一个标准的算法体系，并且有一个统一的输入和输入格式将现有的各 种各种的算法容纳进去。算法的各个部分可以是相互独立的；并且测试的方法，工 具都可以统一。 2 、对非结构化数据库的处理。 流式、多媒体、文本等等数据都不是具有明确取值或属性的结构化的数据，我 们今后会在数据库中大量使用此类数据，这样必然会将关联规则的研究带到这个领 域来。 3 、用于辅助其他学科进行研究。 关联规则可以提供高效的识别效率来发现全新的模式和规律，这样可以较好的 辅助其它许多自然科学研究领域。将是一个高性能的辅助工具。 4 、用于辅助各界人士进行决策。 关联规则在许多工业或科学领域展示了其旺盛的生命力和价值。将关联规则和其 他方法融合为决策者提供合理的、有价值的决策将是一个非常有现实意义的新课题。 1 4 本文的主要内容 d m 的最终目的就是要找到合适高效的工具可以从海量的信息中找到隐藏的知 硕士学位论文 m a s t e r st h e s i s 识，这些知识可以被我们接受，而且对我们有用处，还可以简单的进行表达。我们 的这个目标跟我们能不能找到合适的高效的算法有很大的关系，所以，工具在d m 当中起关键性的作用。 下面列举一下本文的主要工作，体现在以下几个方面： ( 1 ) 第一部分绪论主要对d a t am i n i n g 下的关联规则挖掘的背景作了介绍，另外就是 对d a t am i n i n g 研究状况做了分析，并列举了国内和国外的现状。还介绍了关联规 则的研究现状，并简单讨论了数据挖掘中关联规则挖掘的未来趋势。 ( 2 ) 第二部分对数据挖掘技术做了概括性的综述，包括d a t am i n i n g 的定义，d a t a m i n i n g 的任务，d a t am i n i n g 的流程和d a t am i n i n g 的技术介绍，以及数据挖掘的应 用领域及未来的研究方向。 ( 3 ) 第三部分开始就阐述了d a t am i n i n g 中的关联规则挖掘，介绍了关联规则挖掘的 的来由，a s s o c i a t i o nr u l e sm i n i n g 的基本概念及相关定义、关联规则挖掘的基本步 骤和关联规则挖掘的分类，其次介绍了经典的关联规则算法a p f i o d , a p f i o f i 算法步 骤和特点，并通过实例对a p f i o f i 算法做了性能分析，就如何提高a p d o f i 算法的有 效性做了探讨。另外对不产生候选挖掘频繁项集的f p g r o w t h 算法做了详细描述， 指出其创新点，并对其性能和适用范围作了分析，最后对这两种经典算法作了简单 对比。 ( 4 ) 第四部分讨论了基于图的关联规则的挖掘算法，在已有的d i r e c t el i n k e dg r a p h i c 算法的基础上，提出了改进的算法。并通过实例验证和性能分析，突出了改进算法 的优越性。 ( 5 ) 对论文进行总结，并展望后续可能的研究工作。 1 5 本章小结 首先对d a t am i n i n g 中a s s o c i a t i o nr u l e sm i n i n g 作了大体的介绍，并对d a t a m i n i n g 及其中的a s s o c i a t i o nr u l e sm i n i n g 的研究现状做了概述。其次讨论了关联规 则挖掘的未来趋势。最后对本文的结构和主要内容作了描述。 4 硕士学位论文 m a s t e r st h e s i s 2 1 数据挖掘的定义 第二章数据挖掘 数据挖掘跨越了非常多的学科。包含了数据库、人工智能、机器学习、并行计 算、数理统计、可视化等多个领域的理论和技术，如图2 1 所示： 图2 - 1 数据挖掘是一门交叉学科 我们用数据库管理系统存储海量数据时，通过机器学习的方法分析数据进而去 发现大量数据背后隐藏的模式和知识，前面两者的结合导致了数据挖掘的产生。 数据挖掘，也称数据库中的知识发现，是指从海量的数据中找到对我们有用的 规律或模式，而且这些规律我们事先并不知道的、是些隐藏的知识。我们提取的这 些知识可以有如下的表现形式，比如概念( c o n c e p t s ) 、规律( r e g u l a r i t i e s ) 、模式 ( p a t t e r n s ) 、规贝, l j ( r u l e s ) 等。我们要讲的数据挖掘有两个层面的意思。 ( 1 ) 第一层是技术上的。技术上的数据挖掘就是从海量的模糊不完全的数据中 找到隐藏在背后的模式或者知识这样一个过程。这样可以就可以利用找到的知识更 好的为我们生活服务。我们可以找到与数据挖掘的很多同义词，意思都相差不大， 比如决策支持、数据分析和数据融合等。这个层面上的定义包含了几个方面的规定： 原数据库的量要非常大，而且要客观，并且没多少规律；我们找到的知识可以被我 们很方便的去利用和理解。不是去发现某条真理适用于各个领域，只要在某个业内 适用就可以。 规律、知识的表现形式多种多样，表面上讲，一般的信息和数据都可以看做知 识，如果深层次的定义的话，我们更是把知识看成日常生活中的定律、规则等。数 据是我们发现知识的来源，形似在大海中淘宝一样。知识的来源也就是数据源可以 5 硕士学位论文 m a s t e r st h e s i s 是非常有规律的数据，例如我们常用的表格表达的关系数据库，非常没有规律的数 据也是可以的，我们用的记事本、多媒体流等等；分散在网络上的各种类型的数据 也都是可以的。我们可以利用统计学、数学、运筹、规划等等许多办法去找到有用 的知识。发现的知识可以更好的帮助我们做出决定，知识本身可以自我保护。从上 面的论述中可以了解到数据挖掘是融合了许多学科的，人们可以利用数据查询，进 而到挖掘，最后可以做出比较科学的决策在这样的形式背景下，各式各样行业的人 都去研究这个新兴的学科，特别是跟数据打交道比较多的学者。 我们这里不是去发现某条真理适用于各个领域，只要在某个业内适用就可以。 更不是去发现通用的规律而需要去推导。我们要找到的知识只需要面向某一个行业 就可以了，如果能很形式化的去表达出来更好，但是我们可以方便的接受这些知识。 ( 2 ) 第二层是商业上的。d a t am i n i n g 是可以从商业上处理数据的。最大的特 征就是要对平时工作中的海量数据数据进行标准化的提取，这样我们可以用来指导 商业上的决策。 d a t am i n i n g 是现代形成的比较深层次的数据处理技术。数据处理在过去多年的 历史中只是用于数据收集然后整理归纳，在研究方面不够深入。 再者，以往的科技水平欠缺，数据的处理能力和条件水平的低下导致了处理归 纳总结能力的局限。但是现在各个行业的技术进步非常快，在处理数据方面的能力 有了大的改观，这样这些技术就可以很好的指导企业的经营管理。而且我们规律总 结也不光是纯粹为了做研究工作。更多是想到可以帮助产生有用的知识，更好的指 导我们的生产和销售，从而得打丰厚的收益。我们企业遇到的阻碍就是，平时的经 营管理当中产生了非常多的数据而对我们有用的数据太少了，所以这就需要研究者 和专家对数据进行深度处理，得到对企业有用的信息。从而提高企业的经营效率和 收入水平。数据挖掘就是在上述的过程中出现的。 所以，我们可以给数据挖掘下的简单定义就是：按初步的目的来对海量信息进 行刷选，最后找到合适的规律或知识。 2 2 数据挖掘的任务 d m 的主要任务包括下列几个方面：关联分析、聚类分析、分类、预测、时序 模式和偏差分析等。 ( 1 ) 关联分析 所谓的关联分析，就是要找到两个或者是多个信息之间的相关性或者规律。我 们这里般都是招到数据之间的关联，它是可以被我们发现的一类知识，存在于各 6 硕士学位论文 m a s t e r st h e s i s 种结构的数据中。有一般的关联、根据时间产生的关联还有原因与结果的关联。最 终的目标是要找到许多不同结构数据中隐藏的关联关系。我们通常通过两个指标来 衡量关联规则的相关程度，一个是支持度，一个是置信度。为了完善数据挖掘评估 体系，我们需要更多的引入参数，比如兴趣度和相关性等等，这样有利于我们更好 的面对新的需求。 ( 2 ) 聚类分析 所谓聚类就是把很多相似的信息等划分到一块，同一类中的数据彼此相似，不 同类中的数据彼此不一样。在聚类分析上可以建立宏观的概念，通过它可以找到数 据所在的分布规律，还有可能找到数据之间的某些联系。 ( 3 ) 分类 分类就是要找出某个类别的总体特征，从概念上来进行描述，但必须要描述其 本质特征。构造出来的模型以规则或者决策树模式来呈现。但是在分类之前，得有 初始数据，可以通过这些初始数据再加上算法，从而得到模型。 ( 4 ) 预测 预测是在以往的数据中找出某些有用的规律，建立模型，根据构建的模型对未 来进行推断。关键点是精度和不确定性。 ( 5 ) 时序模式 时序模式是指随着时间的推移，找到多次发生的事件或者模式。和回归类似， 就是通过我们知道的信息来判断将来的情况。但这些信息中未知因素在时间上有 差异。 ( 6 ) 偏差分析 在偏差中包括很多有用的知识，数据库中的很多数据有冗余和异常，我们发现 存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观察结果与参照之间 的差别。 2 3 数据挖掘的流程 数据挖掘过程主要有以下几个阶段，确定挖掘对象、数据准备、模型建立、数 据挖掘、结构分析表述和挖掘应用。数据挖掘可以描述为这几个阶段的反复过程， 如图2 - 2 。 7 硕士学位论文 m a s t e r st h e s i s 图2 - 2 数据挖掘流程 ( 1 ) 数据准备阶段 这个阶段我们可以细分一下，可以划分成四个阶段：数据集成、数据选择、数据 预处理和数据转换。 1 数据集成。 数据集成就是将分布在不同地方的数据进行融合，这些数据可以是不同文件夹 里的，或者不同数据库里的。另外融合的时候要考虑到语义的变化，注意数据的完 整性以及简洁性。 2 数据选择。 数据选择是数据挖掘过程中的必备步骤，主要是对数据的刷选以及数据的汇总 等等。 3 数据预处理。 数据预处理主要是要保证我们选择的数据的准确性和完整性，预处理在某种程 度上是挖掘过程的一个补充。 4 数据转换。 数据转换主要是对数据进行合理的编码，可以将字段等转换成容易搜索的表现 形式。 ( 2 ) 数据挖掘 这个阶段进行实际的挖掘操作，即利用机器学习、统计分析等方法，从数据库 中发现有用的模式或知识( 这里，模式是浓缩数据的信息形式，如精炼数据库、表格、 产生式规则、决策树、神经网络的权值等) 。 1 选择数据挖掘方法。 一般有统计分析、机器学习、模式识别方法和人工神经元方法等。 2 选择数据挖掘算法。 选择合适的算法，确定合适的模型和参数。另外，数据挖掘方法必须和目标相 匹配。 3 数据挖掘。 8 硕士学位论文 m a s t e r st h e s i s 查找感兴趣的模式。模式一般表示为一种特殊的形式或一套表达方式，如关联 规则、分类规则或分类树、回归结构和聚类集等。要我们自己挑选适用的工具与合 适的算法，其他的我们需要考虑。 ( 3 ) 处理结果的描述和挖掘应用 1 结果表达。 表达出来的结果可以是可视化的，这样方面用户使用，还可以使用户更加深刻 的理解。 2 结果评价。 筛选和评价挖掘结果中的有用部分，查找可接受的结果。可定义兴趣指标，考 虑结果的正确度、新颖度、有用性和简单性，把信息从输出中过滤出来。利用可视 化方法帮助用户解决所提出知识的有效性或对基本的数据或现象做出结论。 3 知识巩固。 把挖掘出的信息结合到执行系统中，理清楚这些知识各自的职能和其准确性。 预选知道且可信的信息来检查和验证所挖掘出的信息，解决可能存在的矛盾。 当然，在有些情况下，也可以只是简单的记录所挖掘出的信息并把它报告给用 户，由用户进一步分析。 数据挖掘步骤可以与用户或知识库交互。有趣的模式提供给用户，或作为新的 只是存放在知识库中。我们同意数据挖掘是知识发现的一个步骤。在本文中，选用 术语数据挖掘，我们对数据挖掘的表述一般是：数据挖掘是从隐藏在数据仓库中的 大量信息中找到我们感兴趣的知识。 基于这种观点，典型的数据挖掘形同具有以下主要部分( 如图2 3 ) ： 9 硕士学位论文 m a s t e r st h e s i s 图2 3 典型的数据挖掘系统结构 2 4 数据挖掘的技术 d m 技术有如下的九个部分：概念描述、关联分析、分类、聚类、偏差检测、 时序演变分析、信息摘要、概念分析和元数据挖掘。总的可以归结为两大类，一个 是描述性的，另外一个是预测性的。具体见( 图2 4 ) 。描述性的来描述大量数据的 基本特征，预测性的主要是依据过去的数据或者当前的数据来推导出具有预测性质 的规律。 图2 4 数据挖掘技术分类 1 0 硕士学位论丈 m a s t e r st h e s i s ( 1 ) 概念性的描述 主要是对一类具有某个特征的大量数据进行关联比较、归纳，最后概括出这类 数据的相关特性。这种描述可以提取出有价值的知识，它是概括性的、可以很简洁、 但是很准确。概念性的描述可以分成两种，一是特征描述，这个是描述一类数据具 有的相似的特征的。二是区别性描述，这个主要是描述不同数据集之间的不同。 ( 2 ) 数据关联性分析 所谓的关联分析，就是要找到两个或者是多个信息之间的相关性或者规律。我 们这里一般都是招到数据之间的关联，它是可以被我们发现的一类知识，存在于各 种结构的数据中。有一般的关联、根据时间产生的关联还有原因与结果的关联。最 终的目标是要找到许多不同结构数据中隐藏的关联关系。一般可以用支持度和可信 度两个阀值来度量关联规则的相关性，还不断引入兴趣度、相关性等参数，使得所 挖掘的规则更符合需求。关联的数据说明某个对象和其他对象产生了依赖，我们用 到的很多数据库中的对象几乎都存在某种程度的关联性。这种关联表现为它们之间 的某种规律。我们刚才所说的数据库中的关联是现实生活中关联的很小一个部分， 数据或对象之间的关联关系很隐蔽，有的甚至很微妙，这就需要我们利用有效的工 具。这正是我们为什么要进行关联规则挖掘的原因。找到背后隐藏的规则之后，可 以对我们的生产和生活带来好处。 ( 3 ) 积聚在一起的数据 我们可以把数据仓库中的海量数据进行划分，形成相对较小的聚类。这样我们 可以更方便的快速的去了解数据特征，这一方式促进了我们对现实世界的了解方式 的转变。 聚集在一起的数据有个特点就是，在区分不同的数据集的时候不仅要认识他们 离的范围，而且要有对数据集的本质特征概括。这就降低了盲目性。 ( 4 ) 分类和预测 在数据挖掘中有一个任务就是要把具有各种特征的数据进行分组，按照各自不 同的特点来划分。这在各行业中运用较广。我们要进行分类，首先要找到我们分类 的依据，即我们按照什么样的规定来分，或者有什么样的准则值得我们来遵守，这 都是非常重要的。 在这样的情况下进行数据挖掘，我们毕业要获得种分析工具，还要取得一些 可以利用的数据源。这样一种工具称作分类器。它能依据原来的数据特别产生不同 的准则，进而可以将数据划分到不同的组里面去，还可以产生通用的分类依据。另 外我们可以以多种形式来表示分类后的结果。并且随着研究的逐步深入，产生了非 、 硕士学位论文 m a s t e r st h e s i s 常有名的技术。 我们所讲的预测，是要根据原来数据中的训练数据产生某种规律，我们可以利 用规律，在更新自己的数据，从而可以对将来的许多未知因素做出预测。举个例子， 可以预测那些客户下个月不再进行交易，或是预测哪些客户在明年会跟我们公司建 立关系。 ( 5 ) 检验出现的异常 所讲的偏差检测可以理解为对数据集中的不一致数据进行处理和检查。我们用 到的很多数据库中的对象都存在偏差情况，而且这种情况很容易看出来，它们明显 的与其他表现形式不同。偏差就是指这样的数据。也叫做孤立点。存在的异常情况 有可能是人为的，也可以是系统导致的误差。我们进行这项分析很有价值。也非常 的有意思。比如说在某些不文明行为的检查中，这样的误差就表示有欺骗。当然我 们这里说的偏差也包含了很多种表述形式，里面包含了很多的隐藏规律。我们主要 的难点就是定一个准则来区分哪些是异常，哪些算是正常的。还有的困难就是怎么 样很快速的去找到所谓的异常。 ( 6 ) 根据时间序列演变 我们去分析时间序列演变的事件，主要是研究这些数据随着岁月的推进发生的 未来方向。关于这方面的应用，有许多例子，我们对股票市场的分析，它是随着时 间的推移发生变化的，但我们可以利用规律来预测未来走势。 ( 7 ) 浓缩处理信息 我们可以将大篇幅的信息进行浓缩，但要保持整体意思不改变。信息摘要正是 这样的浓缩技术。可以利用工具自动的压缩。而且可以全部概括出原来长篇文章中 的本质意思。这样我们就可以方便快速的去搜寻对我们有用的消息，大大的提高了 效率。特别是我们这样每天产生巨大信息量的时候。 然而现实中并不是很多事情都很规范，非常多的书籍文献等等都是没有文摘 的。如果我们把所有的文摘都去人为补充的话，将是非常艰巨的任务，并且在工作 过程中存在失误，最后可能导致结果不如意。 因此将来会出现这样一个新的方向，就是利用自动化工具来自动的为文章产生 文摘。这项技术正在发展当中。 ( 8 ) 提取信息 这里也叫做信息抽取，它是运用我们已经有的模式，从许多不规则的数据中提 取我们感兴趣的知识。这项技术可以提高我们的办事效率，高效的查到对我们有益 的文本。更为有效的为我们剔除了很多冗余的不规则的信息。 1 2 硕士学位论文 h t a s t e r st h e s i s ( 9 ) 挖掘特征数据 挖掘某种特征的数据可以叫做元数据挖掘。即是要找出数据的特征。我们这里 要重点提到文本元数据。它里面包含一个是描述性元数据，另一个是语义性元数据。 我们对文本的元数据挖掘其他挖掘的是个基础工作，为我们将来要迸行的深度 挖掘奠定良好的基础。另外一个用的比较多的就是w e b 挖掘。w e b 挖掘是对元数据 掘而不是对一般数据的挖掘，这也是目前比较新的研究热点。 2 5 数据挖掘的应用领域和未来的研究方向 数据挖掘技术几乎是在各行各业都有广泛的运用，现将使用比较广泛的行业列 举一下： ( 1 ) 用于研究 在很多高科技行业，数据量大的惊人导致我们很多一半的分析工具应付不了， 我们强烈需要一种强大的软件来帮助我们做数据分析。知识发现技术的发展正是顺 应这样的需求而发展的。这在很多个研究领域都有非常实用的成果。 ( 2 ) 在金融行业的应用 我们接触比较多的金融行业就是保险、银行、证券之类的企业，我们可以利用 d m 这项技术来帮助我们更好的做出商业决策。并且在这样的一些企业中数据的完 备性和准确性都很高，这就有利于d m 技术在这些领域的应用，可以发展的较其他 领域成熟。很明显的好处就是为社会创造了更多的效益，为人民带了更多的好处。 另外一点就是应用在金融投资方面，如果没决策好，带来的后果会很严重，而我们 这样的技术可以帮助我们合理的分析，从而选择适合自己的投资策略。这样降低了 我们心里压力，同时也减少了风险。 ( 3 ) 应用于零售行业 数据挖掘这样的技术的来源就是零售业，并且在这行业已经显得非常的成熟。 比如在顾客行为分析，货物的入库，储存，销售等等方面。 在这个行业上的数据挖掘主要有利于了解顾客的习性，对未来走势作预测，提 高服务效率和质量。从而创造更多的效益。 ( 4 ) 应用于保险行业 我们国家的保险行业在这几年发展的非常迅速，对人们生活产生重要影响，这 是在社会保障越来越好的情况下取得的成绩。 保险是一个特殊的行业，需要业内人士的专业知识，其中一项工作就是要评价 一下可能产生的风险。 硕士学位论文 m a s t e r st h e s i s 而我们的d m 技术可以用来做这一项工作，我们可以利用保险行业的相关的， 已有的数据，在原来的数据上加以分析。这样可以总结和归纳出对我们有利的规则， 更好的帮助我们工作。对于保险公司进行业绩、预算、市场风险等方面有巨大的作 用。 ( 5 ) 应用于电信业 电信业在这几年发展迅速，服务形式转变较快，对人们的生产或者生活方式产 生巨大影响。已经由通话服务变为综合服务了。可以跟计算机网络等等新兴的通信 方式结合起来，这是目前的潮流。伴随着我们国对电信业的重视，这个市场的竞争 变得异常火爆。基于这样的环境，我们可以利用数据挖掘技术帮助我们，它可以较 好的为我们确定运作行为，对于我们提高效率和水平具有现实意义。 ( 6 ) 其他的一些行业 比如我们关注的医学治疗。我们的d m 技术可以运用在病号的状况检查，另外 可以预测一些状况，还可以进行一些判断。 其次还有犯罪分析。可以根据各式各样的犯罪特征进行挖掘，总结出某方面的 经验，进而准确的找到犯罪人员。 还有就是日常的制造行业。d m 技术可以对我们的生产流程和出现的阻碍进行 检查，从而有利于企业的正常运营。另外可以在产品质量方面抓住主要特征，对于 破坏产品的很多方面可以进行有效的监控。这样就提高了我们企业的运作效率。 最后，d m 技术在我们日常中还要考虑到以下的方面： 1 要考虑算法的执行效率 我们在做数据挖掘的时候，数据的来源的都是海量级的数据库，而且数据的特 征形态千差万别以及其中的关系非常杂乱。这样的状况使我们的挖掘过程变得异常 困难。而且在此过程中很多未知因素的存在，可能导致结果的错误。鉴于此情况， 我们必要要考虑算法的效率问题，以及怎样把算法进行扩充。 2 考虑到处理不同类型的数据结构 我们现在进行的数据挖掘效率一般都很好，主要是因为我们用到的数据模型几 乎都是有特定结构的。但是日常生活中的数据激增，不可能完全都是有结构的，会 出现没有明显结构的数据，而且类型都形态各异。我们的d m 技术系统必须要有效 的应对这一点。我们的研究方向就可以扩展了，可以把国内或者国际上大型的、数 据类型差别极大的数据库的数据源连接起来，形成一个异构体。而从这些有结构和 没有结构的数据中挖掘规律是对我们现在技术的重大考验。 3 提供良好的操作界面 1 4 硕士学位论丈 m a s t e r st h e s i s 这里说的提供友好的操作界面是指人机交互的这个过程必须顺利。这当中的两 个角色：人和系统。是必不可少的。交互过程是：系统提示用户要输入哪些方面的 数据，以及哪些要求及额外条件等等。这一过程必须考虑到用户的方便性，还有一 过程就是系统给用户结果的过程。处理结果的表现形式有很多种，但如何确切和形 象的表达这一处理结果是我们要考虑的重要问题。 4 数据的保密性 d m 技术可以将数据在不同的平台上进行形象的表达，这就需要我们对数据进 行保密，另外在运用的过程中可能会有一些不合理的数据掺和进来，所以安全性也 必须要考虑。 5 不同网络、不同结构的数据库融合 网络的发展给我们生活带来巨大改变，网络中可利用的资源越来越多，我们要 考虑到把不同网络、还有不同结构的数据库进行融合，那样可以高效的进行挖掘。 另外还要加强散布在各处研究者的协调性。 2 6 本章小结 本章概述了数据挖掘技术，形象的描述了数据挖掘的定义，另外说明了数据挖 掘的任务，解释了数据挖掘的流程，阐释了数据挖掘的功能，最后对数据挖掘的应 用领域及未来的研究方向做了总结。 硕士学位论文 m a s t e r st h e s i s 第三章关联规则挖掘 关联规则挖掘发现大量数据中项集之间有趣的关联。 我们在日常生活中积累了大量的数据，所以很多各行各业的专家学者都想从大 量的数据中挖掘出对我们有用的知识来。而且这是非常有意义的。从大量的数据中 找到对我们有利的信息，给们的生活带来了极大的方便。另外在商务上可以帮我们 制定许多决策。 3 1 购物篮分析：引发关联规则挖掘的例子 如果你是一个零售商，你想了解顾客的购买习惯，想知道顾客多半会在一次购 物时同时购买什么样的商品组合，为了回答你的问题，你可以在你的商店顾客事务 零售数据上，运行购物篮分析，就可以得到你想要的结果。 通过分析购物篮分析得到的结果可以用于市场规划、广告策划和分类设计等。 例如，购物篮分析可以帮助经理设计不同的展场和商店布局。一种策略是：将顾客 经常一块购买的商品放近一些，以便进一步刺激这些商品一起销售。例如：一个超 市中顾客购买面包的同时一般要购买牛奶或者其他饮料，那么可以把销售牛奶或者 饮料的展台放在销售面包的展台附近，这样就促进增加二者的销售。另一种策略是： 将面包和牛奶分别放在展场的两端，在两者之间放上销售情况一般或者是销量不好 的商品，那么顾客在决定购买面包以后从一端的面包展场走向另一端牛奶展场的路 上，他可能看到果酱，就有可能产生购买果酱的愿望。关联规则挖掘正是基于这样 的背景下产生的。 3 2 关联规则的基本概念 3 2 1 关联规则挖掘的定义 我们前面提到过，a s s o c i a t i o nr u l e sm i n i n g 在d m 中占有非常重要的地位，而 发展迅速。 a s s o c i a t i o nr u l e sm i n i n g ，是从海量的、没有规律的、结构多样化的数据库中 找到未知的、对我们有价值的信息。a s s