（计算机应用技术专业论文）数据挖掘技术的研究与应用.pdf

武汉理工大学硕士学位论文 摘要 随着数据库技术的逐渐成熟和计算机网络的迅速普及，人们采集数据的能 力得到了极大的提高，导致全球范围的信息急剧膨胀，为了对这些海量信息的 隐藏知识进行开发，数据挖掘技术应运而生。目前，数据挖掘技术愈来愈成熟， 应用范围也日趋广阔，但是，在港口信息领域还缺乏专门的研究。伴随着我国 经济的发展，我国港口的规模也不断扩大，货物吞吐量也跟随着急剧增长。在 各大港口采取信息化运作的背景下，港口信息已经由以往的手工操作转化为目 前依靠网络技术的自动化操作，并且已经积累了一定数量的信息。跟其它领域 一样，港口信息中也蕴含着潜在的有价值的知识有待于发现，这些知识能够为 企业良好经营和决策部门做出重要决策提供帮助，所以对数据挖掘技术在港口 信息管理中应用的研究就成为了当务之急。 本文是数据挖掘技术在港口信息管理系统领域的一个初步尝试，试图验证 数据挖掘技术在这个领域中的可行性。 首先，介绍了数据挖掘技术的基本原理与概念，以及数据挖掘的任务，方 法和步骤。着重研究了关联规则挖掘技术，本文在原始a p f i o f i 算法的基础上进 行了改进，在生成新的项集的同时，减小原始数据库的规模，降低了算法扫描 数据库的次数，有效地提高了算法的效率。 其次，介绍了本文的数据挖掘对象一航道养护费征稽管理系统的设计模型 和数据库结构，讨论了基于信息管理系统的数据挖掘应用，并分析了在关系型 数据库中进行数据挖掘的可能性以及方法。 最后，论文按照数据挖掘的标准步骤，对数据库原始表依次进行了数据选 取，数据清洗，数据转化，使其成为适合于数据挖掘的文本数据源。并用a p f i o f i 算法进行挖掘，输入最小支持度阈值和最小置信度阈值，输出所有的频繁项集 和强关联规则。根据强关联规则，发现了隐藏在港口信息中的一些规律。 关键词：数据挖掘，关联规则，信息系统，a p f i o f i 算法 武汉理工大学硕士学位论文 a b s t r a c t a sd bt e c h n o l o g yb e c o m e sm a t u r ea n dc o m p u t e rn e t w o r k sb e c o m ep o p u l a r , p e o p l e sa b i l i t yo fc o l l e c t i n gd a t ah a sb e e ng r e a t l yi m p r o v e d ，w h i c hc a u s e st h er a p i d 羽o b a le x p a n s i o no fi n f o r m a t i o n i no r d e rt of i n dt h eh i d d e nk n o w l e d g eo ft h e i m m e n s ea m o u n to fi n f o r m a t i o n ，d a t am i n i n gt e c h n o l o g ya p p e a r s a tp r e s e n t ，d a t a m i n i n gt e c h n o l o g yh a sb e c o m em o r ea n dm o r em a t u r ea n di t sa p p l i c a t i o nr a n g ei s b e c o m i n gb r o a d e r b u t ，i tl a c k ss p e c i a lr e s e a r c hi np o r ti n f o r m a t i o nf i e l d w i t ht h e d e v e l o p m e n to fo u rc o u n t r y se c o n o m i c , t h es c a l eo fp o r ti se x t e n d i n ga n dt h e t h r o u g h p u to fc a r g oi sr a p i d l yi n c r e a s i n g t h em a j o rp o r t sh a v et a k e ni n f o r m a t i o n o p e r a t i o n t h ep o r ti n f o r m a t i o nw a sm a n u a l l yo p e r a t e d ，a n dn o wi ti sa u t o m a t i c a l l y o p e r a t e db yn e t w o r kt e c h n o l o g y i na d d i t i o n ，ac e r t a i na m o u n to fi n f o r m a t i o nh a s b e e na c c u m u l a t e d a so t h e rf i e l d s ，t h ep o r ti n f o r m a t i o na l s oi n c l u d e s p o t e n t i a l v a l u a b l e k n o w l e d g e ，w h i c hc a n b e g o o d f o rb u s i n e s s o p e r a t i o n sa n dh e l p d e c i s i o n m a k i n gd e p a r t m e n t st om a k ei m p o r t a n td e c i s i o n s s o ，d o i n gs o m er e s e a r c h o nt h ea p p l i c a t i o no fd a t am i n i n gt e c h n o l o g yi np o r ti n f o r m a t i o nm a n a g e m e n th a s b e c o m eat o pp r i o r i t y t h i st h e s i si sap r e l i m i n a r ya t t e m p to fd a t am i n i n gt e c h n o l o g ya p p l i e dt op o r t i n f o r m a t i o nm a n a g e m e n ts y s t e m i ta i m st ov a l i d a t et h ef e a s i b i l i t yo fd a t am i n i n g t e c h n o l o g ya p p l i e dt ot h i sf i e l d f i r s t l y , b yi n t r o d u c i n gt h eb a s a lp r i n c i p l ea n dc o n c e p to fd a t am i n i n g ，t h i s t h e s i sa l s oi n t r o d u c e dt h em i s s i o n ，m e t h o da n dp r o c e s so fd a t am i n i n g t h e n r e s e a r c h e da s s o c i a t i o nr u l e sm i n i n gt e c h n o l o g ye m p h a t i c a l l y t h i st h e s i si m p r o v e d t h ea l g o r i t h mb a s e do na p r i o r i w h e n g e n e r a t i n gt h en e wi t e ms e t s ，t h en e w a l g o r i t h mr e d u c e st h es i z eo fd a t a b a s ea n dd e c r e a s e st h et i m e st os c a nd a t a b a s ew h i c h l e a d st oah i g h e re f f i c i e n c y s e c o n d l y , i ti n t r o d u c e st h ed e s i g nm o d e la n dd bs t r u c t u r eo ft h ed a t am i n i n g o b j e c ti nt h i st h e s i s ，t h a ti s ，y a n g t z ec h a n n e lf e e sl e v y i n ga n df i n a n c i a lm a n a g e m e n t s y s t e m i ta l s od i s c u s s e st h ea p p l i c a t i o no fd a t am i n i n gb a s e do nt h ei n f o r m a t i o n m a n a g e m e n ts y s t e ma n da n a l y z e st h ef e a s i b i l i t ya n dm e t h o d so fd a t am i n i n gi n l i r e l a t i o nd b f i n a l l y , t h e t h e s i s i m p l e m e n t e d d a t ae x t r a c t i o n , d a t ac l e a n i n ga n d d a t a t r a n s f o r m a t i o ni nt u r no no r i g i n a ld a t a b a s et a b l ea c c o r d i n gt ot h es t a n d a r ds t e p so f d a t ar u i n g at e x td a t as o u r c ef i t sf o rd mw a sc o m eo u t n e x t ，t h ea u t h o rm i n e dt h e d a t as o u r c eu s i n ga p r i o r ia l g o r i t h m ，w h o s ei n p u t sa r em i n i m u ms u p p o r tt h r e s h o l d a n dm i n i m u mc o n f i d e n c et h r e s h o l da n do u t p u t sa r ef r e q u e n ti t e ms e t sa n ds t r o n g a s s o c i a t i o nr u l e s a c c o r d i n gt ot h es t r o n ga s s o c i a t i o nr u l e s ，w ec a nf i n ds o m er u l e s h i d i n gi nt h ep o r ti n f o r m a t i o n k e y w 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 ，i n f o r m a t i o ns y s t e m ， a p r i o r ia l g o r i t h m i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得武汉理工大学和其它教育机构的学位和证书而使用过的材 料。与我一同工作的同志对本研究所作的任何贡献均已在论文中作 了明确的说明并表示了感谢。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即学校有权保留交向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位 论文的全部内容编入有关数据库进行检索，可以采用影印、缩印或 其他复制手段保存或汇编本学位论文。同时授权经武汉理工大学认 可的国家有关机构或论文数据库使用或收录本学位论文，并向社会 公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( ：参秀- 导师( 日期 、 武汉理t 大学硕士学位论文 第1 章绪论 本章主要介绍数据挖掘兴起的背景和研究意义，综述了数据挖掘的基本概 念、挖掘过程和数据挖掘的功能，列举了本文的主要研究工作，并给出了全文 的内容和结构。 1 1 研究背景 数据挖掘是人们多年来对数据库技术进行大量研究和开发的成果，在2 0 世 纪8 0 年代末有了很大的发展。数据挖掘是指从数据仓库的大量数据中揭示出隐 含的、先前未知的、潜在有用的信息的过程。它的目标是将大容量数据转化为 有用的知识和信息。数据挖掘不但可以帮助人们从数据库特别是数据仓库的相 关数据中提取出所感兴趣的知识、规律或更高层次的信息，而且也可以帮助人 们从不同程度上去分析它们，从而可以更有效地利用数据；它不仅可以用于描 述过去数据的发展过程，而且还能进一步预测未来的发展趋势。因此，数据挖 掘正成为一个新的、日益受到重视的热点研究领域。 与数据挖掘息息相关的是数据库中的知识发现( k d d ：k n o w l e d g ed i s c o v e r y i n d a t a b a s e s ) ，k d d 是于1 9 8 9 年在美国召开的第1 1 届国际人工智能联合会议的 专题讨论会上提出的。k d d 泛指所有从源数据中发现模式或联系的方法，常用 来描述整个数据挖掘的过程，包括最开始的制定业务目标到最终的结果分析【l j 。 关于k d d 与数据挖掘的关系有许多不同的观点，代表了不同的数据挖掘技术含 义。 第一种观点认为k d d 是数据挖掘的一个特例。这种看法认为既然数据挖掘 系统可以在关系数据库、事务数据库、空间数据库、时序数据库、文本数据库、 多媒体数据库以及w e b 等多种数据组织形式中发现知识，那么数据库中的知识 发现k d d 只是数据挖掘的一个方面。它是早期比较流行的观点，这种描述强调 了数据挖掘在数据形式上的多样性。 第二种观点认为数据挖掘是k d d 过程的一个步骤。这种观点的思想是： k d d 是从数据中发现知识的全部过程，而数据挖掘则是此全部过程中的一个特 定的、关键的步骤。虽然数据挖掘可以从多种数据库及数据仓库中挖掘知识， 武汉理工大学硕士学位论文 但是这些数据都是和数据库技术相关的。而k d d 的过程包括数据清洗、数据集 成、数据选择、数据转换、数据挖掘、模式生成及评估等一系列步骤，它是一 个更广义的范畴。把数据挖掘作为k d d 的一个重要步骤看待，可以使我们聚焦 研究重点，有效解决问题。目前，人们对数据挖掘算法的研究基本属于这样的 范畴。 还有一部分人认为，k d d 与数据挖掘的含义基本相同，只是叫法不一样。 事实上，在许多的文献中以及许多场合中，这两个术语都不加区分被人们所使 用。因此也有人称知识发现为数据挖掘，一般可以不加区别地使用两者。 用数据库来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后 的知识，这两者的结合促成了数据挖掘的产生。数据挖掘是数据库中知识发现 不可缺少的一部分，实际上，数据挖掘是一门交叉性学科，涉及到数据库、统 计学、人工智能与机器学习等多个领域。数据挖掘发现的知识可以用在信息管 理、过程控制、科学研究、决策支持等许多方面【2 1 。 1 2 选题意义 随着计算机应用的普及，功能强大的信息系统己经在各个企业领域变得越 来越普遍。特别是步入网络时代以后，信息的交流变得尤为方便，大量的信息 由此产生。但对于数据分析，人们还未完全认识到它的重要性。随着数据挖掘 技术的出现，逐渐出现了能够对已有数据进行二次开发和利用的分析系统，从 已有的大量数据中挖掘更深入的观点与论据，乃至总结出有事实基础的可利用 的信息知识，帮助进行决策。 在各大港口，管理信息系统已经广泛使用，并累积了大量的企业数据，但 管理人员很少能够直接使用这些已经存在的数据进行查询、分析并作为决策依 据 3 , 4 1 。企业一方面投入大量的人力物力进行信息化建设，另一方面管理人员还 是按照传统的方式和方法来进行工作，阅读部门经理提供的汇总或明细报表， 每到月底各个部门常夜以继同的忙于为各部门提供这样或那样的数据。可以说， 信息化并没有给工作人员带来完全的便利。 目前，与港口相关的数据量大而分散，数据仓库恰恰是解决这种杂乱低效 的现状，把大量的历史数据经过处理转化为有用的信息 9 1 。随着数据量的急剧增 长，用户很难凭感觉从海量数据找出其内在规律，并据此规律进行分析预测。 因此，必须借助相应的数据挖掘工具，自动地发现数据中隐藏的规律，为用户 2 武汉理t 大学硕十学位论文 的决策分析提供智能的、自动化的辅助手段。 本文在充分研究国内外目前港口企业发展现状的基础上，针对港口信息系 统中存储的大量分散的、极具丰富价值的信息进行了专门研究，利用数据挖掘 技术，对港口企业的货物种类建立分析模型。在数据挖掘方法研究中，通过运 用关联规则的a 研谢算法发现货物之间的关联关系。通过这些研究，为港口在 进行经营决策过程中提供更为科学的决策方法和支持理论，增强管理者决策的 科学性和有效性。 1 3 数据挖掘的发展以及国内外研究现状 1 3 1 数据挖掘的发展 当前，数据挖掘研究正兴起，随着需求的不断扩大和研究的深入，今后势 必还会形成更大的高潮，而以下几方面问题可能会成为研究的焦点： ( 1 ) 专门用于知识发现的数据挖掘语言的研究，也许会象s q l 语言一样走 向形式化和标准化。目前已提出的d m q l 语言即是着眼于上述思想研究开发的。 ( 2 ) 数据挖掘过程可视化方法的研究，一方面使知识发现的过程能够或者易 于用户理解，另一方面也能提高知识发现过程中的人机交互水平。 ( 3 ) 网络环境下数据挖掘方法的研究，一方面可以借助网络研究分布式数据 挖掘算法，以提高挖掘效率；另一方面可以在网络上建立数据挖掘服务器，与 数据库服务器配合，实现数据挖掘。 ( 4 ) 对各种半结构化甚至是非结构化数据源进行挖掘的深入研究，如文本数 据、图形图像数据、多媒体数据等。 数据挖掘技术是在信息时代面向用户需求提出的知识获取技术，因此，研 制开发基于数据挖掘的决策支持系统工具将是数据挖掘研究首当其充的重要任 务。 目前有很多通用的数据挖掘系统趋向于提供适用于各种商业应用的横向解 决方案( h o r i z o n t a ls o l u t i o n ) ，而不是针对某个特定的应用的解决方案。对某个特 定领域的一些数据或应用可能需要特定的算法来查找模式，而通用的数据挖掘 系统对这些特定领域的数据有其固有的局限性，有可能不能满足要求。因此， 研制基于某个特定领域的数据挖掘工具将显得尤为重要。专用的数据挖掘系统 能够提供纵向解决方案( v e r t i c a ls o l u t i o n ) 【5 】，把特殊领域的业务逻辑和数据挖掘 3 武汉理工大学硕士学位论文 系统集成起来，将数据分析技术与特定领域知识结合以完成特定的任务。现在 数据挖掘的应用领域多集中于生物医学，d n a 分析，金融，零售业和电信部门 竺【6 1 寸o 1 3 2 数据挖掘的研究现状和面i 临的问题 1 3 2 1 数据挖掘的研究现状 目前，国外数据挖掘的发展趋势及其研究方面主要有：对知识发现方法的 研究进一步发展，如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研 究和提高、传统的统计学回归法在k d d 中的应用、k d d 与数据库的紧密结合。 在应用方面包括：k d d 商业软件工具不断产生和完善，注重建立解决问题的整 体系统，而不是孤立的过程【j 7 1 。用户主要集中在大型银行、保险公司、电信公司 和销售业。国外很多计算机公司非常重视数据挖掘的开发应用，i b m 和微软都 成立了相应的研究中心进行这方面的工作，此外，一些公司的相关软件也开始 在国内销售，如p l a t i n u m ，b o 以及i b m 。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所 涉及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及 有关数据挖掘理论方面的研究。目前进行的大多数研究项目是由政府资助进行 的，如国家自然科学基金、8 6 3 计划、“九五 计划等，但还没有关于国内数据 挖掘产品的报道。 可以看出，数据挖掘的研究和应用受到了学术界和实业界越来越多的重视。 进行数据挖掘的开发并不需要太多的积累，国内软件厂家如果进入该领域，将 处于和国外公司实力相差不很多的起跑线上。并且，现在关于数据挖掘的一些 研究成果可以在i n t e r n e t 上免费获取，这更是一个可以利用的条件。我们希望数 据挖掘能够引起国内实业界更多的重视，同时也希望能够有更多的国内软件厂 商进入该领域，一起促进数据挖掘技术在中国的应用。 当前，世界上比较有影响的典型数据挖掘系统有：s a s 公司的e n t e r p r i s e m i n e r ，i b m 公司的i n t e l l i g e n tm i n e r , s g i 公司的s e t m i n e r ，s p s s 公司的c l e m e n t i n e , s y b a s e 公司的w r a r e h o u s es t u d i o ，r u l e q u e s tr e s e a r c h 公司的s e e s 、c o v e r s t o r y 、 e x p l o r a 、k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d b m i n e r 、q u e s t 等。 4 武汉理t 大学硕士学位论文 1 3 2 2 数据挖掘面临的挑战和发展趋势 数据挖掘语言的设计、高效的数据挖掘方法和集成的数据挖掘环境的建立 以及应用数据挖掘技术解决大型应用问题，都是目前数据挖掘研究和应用开发 所面临的主要问题。 鉴于数据、数据挖掘任务和数据挖掘方法的多样性，给数据挖掘提出了许 多挑战性的课题，下面是数据挖掘的主要发展趋势，它反映了面对这些挑战的 应对策略【8 1 。 ( 1 ) 算法效率和可伸缩性。目前，数据库的规模呈指数增长。据统计，数据 和计算资源的增长速度符合摩尔定理，每1 8 个月翻一番。因此，海量数据挖掘 的最大挑战不仅仅在于数据库的绝对规模，还在于数据挖掘系统能够处理这些 持续增长的数据集合。为了保证高效率，数据挖掘系统必须能有效地处理海量 数据，其算法必须是高效率和可伸缩的。 ( 2 ) 处理不同类型的数据和数据源。目前数据挖掘系统处理的数据库大多是 关系数据库。随着数据库应用范围的日益扩大和规模、功能的日益完善，数据 库中将包含大量复杂的数据类型。如结构化的数据，复杂的数据对象：混合文 本，多媒体数据，时空数据，事务数据及历史数据等，甚至出现新的数据库模 型。因此，保证数据挖掘系统能有效地处理此类数据库中的数据是至关重要的。 ( 3 ) 数据挖掘系统的交互性。数据挖掘中操作者的适当参与能加速数据挖掘 过程。一方面，交互界面接收用户的检索、查询要求和数据挖掘策略，为用户 表达要求和策略提供了方便；另一方面，交互界面又把生成的结果传递给用户， 由于生成的结果可以是多种多样，因此，准确而直观地描述挖掘结果和友好而 高效的用户界面一直是研究的重要课题。 ( 4 ) w e b 挖掘。由于w e b 上存在大量信息，并且w 曲在当今社会扮演越来 越重要的角色，有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数据挖掘服务， 将成为数据挖掘中一个最为重要和繁荣的子领域。 ( 5 ) 数据挖掘中的隐私保护与信息安全。数据挖掘能从不同的角度、不同的 抽象层上看待数据，这将潜在地影响数据的私有性和安全性。随着计算机网络 的日益普及，研究数据挖掘可能导致的非法数据入侵是实际应用中需要解决的 问题之一。 ( 6 ) 探索新的应用领域。早期的数据挖掘主要集中在帮助企业提高竞争能 力。随着数据挖掘的日益普及，它的应用领域也在不断扩大。信息产业的发展 为数据挖掘提供了广阔的空间，数据挖掘技术的应用范围将不断得到拓宽，特 5 武汉理工大学硕士学位论文 别是在生物工程、商业智能、网络服务等领域的应用将成为新的研究热点。同 时由于通用数据挖掘系统在处理特定应用问题时有其局限性，因此，目前的一 种趋势是开发针对特定应用的数据挖掘系统。 ( 7 ) 数据挖掘语言的标准化。标准的数据挖掘语言或有关方面的标准化工作 将有助于数据挖掘系统的研究和开发，有利于用户学习和使用数据挖掘系统。 研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和 标准化。 ( 8 ) 可视化数据挖掘。可视化数据挖掘是从大量数据中发现知识的有效途 径。目前数据挖掘的可视化仅体现在结果的简单描述，而数据可视化、挖掘过 程和结果可视化，将揭开数据挖掘神秘的面纱，使其变得更为生动、形象和具 体。数据和结果的图形展示可以放大、缩小、平移、旋转和变换角度，使分析 人员和用户更加容易理解，将大大推动数据挖掘工具在发现知识和数据分析中 的应用。因此，数据挖掘的可视化具有重要的理论意义和应用价值。 随着计算机计算能力的发展和业务复杂性的提高，数据的类型会越来越多、 越来越复杂，数据挖掘将发挥出越来越大的作用。 1 4 本文研究内容和结构 第1 章是绪论，首先介绍了论文选题背景和研究意义，然后介绍数据挖掘 技术和目前的研究现状，说明了本文的研究内容及其意义。 第2 章是数据挖掘技术研究。首先概述了数据挖掘的定义，然后介绍常用 技术和方法，最后介绍数据挖掘技术的应用范围。 第3 章介绍了数据挖掘技术中的关联规则挖掘，研究了a p r i o r i 算法，并对 其进行优化。 第4 章介绍了数据挖掘的对象，长江航道局信息管理系统，并讨论了数据 挖掘在信息管理系统中的应用技术。 第5 章实现了数据挖掘在长江航道局管理信息系统中的应用。首先进行原 始数据的清洗，然后使用改进a p r i o r i 算法进行数据挖掘并分析结果。 第6 章全文总结和展望。总结本文所完成的工作，并提出我步研究的方向 和问题。 6 武汉理工大学硕士学位论文 第2 章数据挖掘技术研究 在上一章的基础上，本章节探讨了数据挖掘技术，首先介绍数据挖掘的概 念，然后介绍了数据挖掘的过程，和常用挖掘方法，最后介绍了数据挖掘的一 些常用算法。 2 1 数据挖掘概述 数据挖掘( d a t a m i n i n g ，d m ) ，是一种决策支持过程，它主要基于人工智能、 机器学习、统计学技术，高度自动化地分析企业原有的数据，做出归纳性的推 理，从中挖掘出潜在的模式，帮助决策者做出j 下确的决策 1 9 1 。一般认为数据挖 掘是数据库中知识发现k d d 的一个环节，是k d d 中采用具体的数据挖掘算法 从数据中自动高效地提取有用模式的最重要的步骤。然而，在产业界、媒体和 数据库研究界，“数据挖掘 比“数据库中知识发现”更流行，由于d m 的广泛 使用，我们也对d m 和k d d 不作严格区分，而认为是等价的概念，在这种意义 下它们的定义是一致的。从1 9 8 9 年到现在，数据挖掘的定义随着人们研究的不 断深入也在不断完善，目前比较公认的定义是f a y y a d 等给出的【i o 】：k d d ( d m ) 是从数据集中识别出有效的、新颖的、潜在有用的并最终易于被人们理解的模 式的非平凡处理过程。 大规模数据集合是数据挖掘的研究对象，被人们形象地描述为“知识的源 泉”，它可以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文 本、图形、图像数据，甚至是分布在网络上的异构数据。数据挖掘技术是始于 面向应用的，它是对特定的数据进行微观或宏观的统计、分析、综合和推理， 以指导实际问题的求解，企图发现事件问的相互关系，甚至利用已有的数据对 未来的活动进行预测。这样，它就把人们对数据的应用，从低层次的术端查询 操作提高到为各级经营决策者提供决策支持。需要指出的是，这里所说的知识 是相对的，它应是在特定的前提和约束条件下，面向特定领域、有实际应用价 值的，同时还要易于被用户理解，甚至可以用自然语言表达和描述。 7 武汉理工大学硕士学位论文 2 2 数据挖掘过程 数据挖掘是一个多阶段数据处理过程【n 】，主要包括以下几个步骤： 第一步：了解应用领域的知识。在开始知识发现之前首先进行的同时也是 最重要的就是了解你的数据和业务问题。 第二步：数据集成与数据清洁。数据集成将与研究问题相关的多文件或多 数据库运行环境的数据进行合并处理，数据清洁则解决数据中的语义模糊性， 纠正不一致，处理数据中的遗漏、噪声和脏数据等。 第三步：数据归约与预处理。数据归约将得到数据集的压缩表示，在归约 后的数据集上挖掘将更有效，并产生相同或几乎相同的分析结果，从而提高数 据挖掘的质量。预处理则是针对特定的算法对数据进行有序的组织和排列。 第四步：选择数据挖掘功能。根据挖掘任务的需要选择相应的挖掘功能， 例如分类、聚类或关联规则挖掘等。 第五步：选择适合的数据挖掘算法进行数据挖掘。 第六步：模式评估。对挖掘出来的模式进行评估，可视化、转换和知识的 表达。 第七步：知识的表达。 图2 1 显示了数据挖掘的基本过程。 图2 1 数据挖掘的基本过程 8 武汉理工大学硕士学位论文 2 3 数据挖掘的任务和常用方法 2 3 1 数据挖掘的任务 比较典型的数据挖掘任务有概念描述( c o n c e p td 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 rm i n i n g ) 等。 ( 1 ) 概念描述 概念描述本质上就是对某类对象的内涵特征进行概括。一个概念常常是对 一个包含大量数据的数据集合总体情况的概述。如对一个商店所售电脑基本情 况的概述总结就会获得所售电脑基本情况的一个整体概念。对一含有大量数据 的数据集合进行概述性的总结并获得简明、准确的描述，这种描述就称为概念 描述【1 2 1 。概念描述分为特征化描述和区别性描述。前者描述目标类数据的一般 特征和特性的汇总，后者是将目标类对象的一般特性与个或多个对比类对象 的特性比较。 获得概念描述的方法主要有两种：( 1 ) 利用更为广义的属性，对所分析数据 进行概要总结，其中被分析的数据就称为目标数据集；( 2 ) 对两类所分析的数据 特点进行对比并对对比结果给出概要性总结，而其中两类被分析的数据集分别 被称为目标数据集和对比数据集。 ( 2 ) 关联分析 从广义上讲，关联分析是数据挖掘的本质。既然数据挖掘的目的是发现潜 藏在数据背后的知识，那么这种知识一定是反映不同对象之间的关联。关联知 识反映一个事件和其他事件之间的依赖或关联。数据库中的数据一般都存在着 关联关系，这种关联是复杂的，有时是隐含的。关联分析的目的就是要找出数 据库中隐藏的关联信息。关联分析发现关联规则，这些规则展示属性一值频繁 地在给定数据集中一起出现的条件。这种关联关系有简单关联、时序关联、因 果关联、数量关联等。这些关联并不总是事先知道的，而是通过数据库中数据 的关联分析获得的，因而对商业决策具有新价值【1 3 】。简单关联，例如：购买面 包的顾客中有9 0 的人同时购买牛奶。时序关联，例如：若a t & t 股票连续上 涨且d e c 股票不下跌，则第三大i b m 股票上涨的可能性为7 5 。它在简单关联 中增加了时间属性。关联分析广泛应用于购物篮或事务数据分析。 关联规则挖掘是关联知识发现的最常用方法，其中最为著名的是a g r a w a l 9 武汉理工大学硕+ 学位论文 等提出的a 研o r i 及其改进算法，关联挖掘的目的就是从数据库中挖掘出满足最 低支持度和最低可信度的关联规则。关联规则的研究和应用是数据挖掘中比较 活跃和深入的分支，已经提出了许多关联规则挖掘的理论和算法。 ( 3 ) 分类和预测 分类是数据挖掘中的一个重要的目标和任务。目前的研究在商业上应用最 多。分类就是找出描述并区分数据类或概念的模型，以便能够使用模型预测类 标记未知的对象类。分类的目的是学会一个分类函数或分类模型( 也常常称作分 类器) 。要构造这样一个分类器，需要有一个训练样本数据作为输入。分类器的 作用就是能够根据数据的属性将数据分派到不同的组中。这样我们就可以利用 该分类器来分析已有数据，并预测新数据将属于哪一个组，即数据对象的类标 记，然而，在某些应用中，人们可能希望预测某些空缺的或不知道的数据值， 而不是类标记。当被预测的是数值数据时，通常称之为预测。分类模式可以采 用多种形式表示，如分类规则，判定树，数学公式或神经网络【l 引。分类知识挖 掘的一些有代表性的技术有：决策树、贝叶斯分类、神经网络分类、遗传算法、 类比学习和案例学习，以及粗糙集和模糊集等方法。 分类应用的实例很多。例如，可以将银行网点分为好、一般和较差三种类 型，并以此分析这三种类型银行网点的各种属性，特别是位置、盈利情况等， 并决定它们分类的关键属性及相互间关系。此后就可以根据这些关键属性对每 一个预期的银行网点进行分析，以便决定预期银行网点属于哪一种类型。 ( 4 ) 聚类分析 一般把学习算法分成有导师( 或监督) 和无导师学习两种方式，主要区别是有 没有类信息作为指导。聚类是典型的无导师学习算法。聚类分析数据对象，而 不考虑已知的类标记，它将数据对象分组成为多个类或簇，同一个类中的对象 具有较高的相似度，而不同类中的对象差别较大。一般情况下，训练数据中不 提供类标记，聚类可以用于产生这种标记。聚类按照某个特定标准( 通常是某种 距离1 ，最终形成的每个类，在空间上都是一个稠密的区域。所形成的每个类可 以导出规则【1 5 4 l 】。通过聚类技术可以把数据划分为一系列有意义的子集，进而实 现对数据的分析。例如，一个商业销售企业，可能关心哪些客户对制定的促销 策略更感兴趣。聚类分析与分类和预测不同，前者总是在类标识下寻求新元素 属于哪个类；而后者通过对数据的分析比较生成新的类标识，它以某种容易理 解的形式展示给用户，刻画了数据所蕴含的类知识。 l o 武汉理工大学硕士学位论文 分类和聚类技术互有交叉和补充。聚类技术主要是以统计方法、机器学习、 神经网络等方法为基础的。常用的聚类算法有基于划分、层次、密度、网格和 模型的五大类聚类算法。聚类分析有很广泛的应用，包括市场或客户分割、模 式识别、数据分析、图像处理及许多其它方面。 ( 5 ) 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致， 这些数据对象是孤立点。在挖掘正常类知识时，通常总是把它们作为噪音来处 理。因此以前许多数据挖掘方法都在正式进行数据挖掘之前就将这类孤立点数 据作为噪声或者意外而将其排出在数据挖掘的分析处理范围之外。然而在一些 应用场合中，如信用欺诈、入侵检测等小概率发生的事件往往比经常发生的事 件更有挖掘价值。因此当人们发现这些数据可以为某类应用提供有用信息时， 就为数据挖掘提供了一个新的研究课题，即孤立点分析。孤立点探测和分析对 于欺诈探测、定制市场、医疗分析及许多其他的任务是非常有用的。发现和检 测孤立点的方法主要有基于概率统计、基于距离和基于偏差等检测技术的三类 方法。 2 3 2 数据挖掘的方法 主要的数据挖掘方法有遗传算法、粗集方法、决策树方传、神经网络方法【l 6 1 。 ( 1 ) 遗传算法的基本原理是：类比生物进化过程，每一代同时存在许多不同 的种群个体( 染色体) 。这些染色体的适应性以适应性函数f 【x ) 表征，染色体的保 留与淘汰取决于它们对环境的适应能力，优胜劣汰。适应性函数坟x ) 的构成与目 标函数密切相关，往往是目标函数的变种。遗传算子主要有3 种：选择( 复制) 算子、交叉( 重组) 算子和变异( 突变) 算子。遗传算法可起到产生优良后代的作用， 经过若干代遗传，将会得到满足要求的后代( 问题的解) 。 ( 2 ) 粗集方法的基本原理是：将数据库中的行元素看成对象，将列元素看成 属性。设r 为等价关系，定义为不同对象在某个( 或几个) 属性上取值相同。那些 满足等价关系的对象构成集合，称为该等价关系r 的等价类。设e 为条件属性 上的等价类，设y 为决策属性上的等价类，则e 和y 存在3 种情况：y 包含e 称为下近似；y 与e 的交非空，称为上近似；y 与e 的交为空，称为无关。对 下近似建立确定性规则，对上近似建立不确定规则( 含可信度) ，对无关情况则不 存在规则。 武汉理工大学硕士学位论文 ( 3 ) 决策树方法是以信息论原理为基础，利用信息论中互信息( 信息增益) 寻 找数据库中具有最大信息量的字段，建立决策树的一个结点。然后再根据字段 的不同取值建立树的分支，在每个分支集中重复建立树的下层结点和分支。这 种方法实际上是依循信息论原理对数据库中存在的大量数据进行信息量分析， 在计算数据特征的互信息或信道容量的基础上提取出反映类别的重要特征。 ( 4 ) 神经网络方法的原理是：模拟人脑的神经元结构，以m p 模型和h e b b 学习规则建立起前馈式网络、反馈式网络和自组织网络3 大类多种神经网络模 型。基于神经网络的数据挖掘工具对于非线性数据具有快速建模能力，其挖掘 的基本过程是先将数据聚类，然后分类计算权值，神经网络的知识体现在网络 连接的权值上。 2 4 数据挖掘的算法 目前，数据挖掘工具采用的主要方法包括决策树、相关规则、神经元网络、 遗传算法，以及可视化、o l a p 联机分析处理掣1 7 】。这些数据挖掘算法可以按其 功能分为以下几类： ( 1 ) 关联规则挖掘算法 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。a p r i o r i 算 法是一种最有影响的挖掘布尔关联规则频繁项集的算法，其它的还有f p t r e e 算 法。 ( 2 ) 分类算法 分类是从数据中选出已经分好类的训练集建立分类模型。分类算法包括： 1 决策树分类 决策树是一个类似于流程图的树结构；其中，每个内部结点表示在一个属 性上的测试或决策，每个分枝代表一个测试输出，而每个树叶结点代表类或类 分布。树的最顶层结点是根结点。i d 3 、c 4 5 都是一些经典的决策树算法。决策 树算法一般对于相对小的数据集是很有效的。 2 贝叶斯分类 贝叶斯分类是统计学分类方法，它是一类利用概率统计知识进行分类的算 法。它包括朴素贝叶斯( n a i v eb a y e s ，n b ) 分类算法和t a n ( t r e ea u g m e n t e db a y c s n e t w o r k ) 算法。贝叶斯分类最大的优点是易于理解，预测效果好，还结合了其它 算法的优点。例如t a n 算法，它就同时具有决策树和神经网络的优点。 1 2 武汉理t 大学硕士学位论文 3 网络分类算法 神经网络最早是由心理学家和神经学家提出的，旨在寻求开发和测试神经 的计算模拟。神经网络的缺点是靠经验确定，其可解释性差；其优点包括对噪 音数据的高承受能力，以及它对未经训练的数据的分类能力。而此优点非常适 用于数据挖掘分类，于是就出现了一些由训练过的神经网络提取规则的算法。 最流行的神经网络算法是8 0 年代提出的后向传播算法。 4 k - 最邻近点分类 最临近分类基于类比学习。最临近分类是基于要求的或懒散的学习法：即， 它存放所有的训练样本，并且直到新的样本需要分类是才建立分类。最临近分 类也可以用于预测。 5 遗传算法 遗传算法试图结合自然进化的思想，是人工智能领域中举足轻重的算法之 一。遗传算法易于并行，并且也已用于分类和其它优化问题。在数据挖掘，它 们可能用于评估其它算法的适合度。 6 粗糙集分类 粗糙集理论可以用于分类，发现不准确数据或噪音数据内在的结构联系。 粗糙集也可以用于特征归约( 可以识别和删除无助于给定训练数据分类的属性) 和相关分析( 根据分类任务评估每个属性的贡献或意义) 。 ( 3 ) 聚类算法 目前在文献中存在大量的聚类算法。算法的选择取决于数据的类型，聚类 的目的和应用。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝 试多种算法，以发现数据可能揭示的结果。 1 划分方法 其划分思想是：给定一个n 个对象或元组的数据库，一个划分方法构建数 据的k 个划分，每个划分表示一个聚类，并且k y 的规则，其中x c i ，y c i ，并且x n y - 彩。在事务 集d 中，如果包含x 的事务中c 同时包含y ，我们说规则x 专吖的可信度为 c 。如果d 中s 的事务包含x u y ，我们说规则x = y 的支持度为s 。支持度 和置信度除了百分比的形式外，也可以是绝对数值( 如3 0 表示3 0 个事务) 或相对 数值( 如0 4 表示4 0 ) 。 给定一个事务集d ，用户给出一个最小置信度和最小支持度，我们称为置信 度门槛值和支持度门槛值。关联规则的挖掘任务就是要生成所有支持度和置信 度都高于置信度门槛值和支持度门槛值的关联规则。具体描述如下： 支持度：s u p p o r t ( a = b ) = p ( aub ) 置信度：c o n f i d e n c e ( a = b ) = p ( b l a ) 满足最小支持度门槛值和最小置信度门槛值的关联规则称为强规则。支持 度和置信