（应用数学专业论文）数据挖掘中的分类和预测及其在决策支持系统中的应用研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 ， ，当今社会是一个信息爆炸的时代，如何充分利用各种各样的信息为人类 服务已显得越来越重要。作为新兴的知识发现技术数据挖掘以及辅助决 策工具一一决策支持系统已越来越受到人们的关注，它们为人们从大量数据 中获取感兴趣的、有用的信息提供了便捷之道。) 夕 在数据挖掘众多的研究分支中，分类和预测问题一直是一个十分引入注 目的主要分支，许多学者从各个角度如统计、信息理论、神经网络等方面做 了大量的研究，取得了一系列的重要成果。本文基于已有的研究成果，主要 做了如下的工作： l 、探讨了分类和预测的处理模型，对现有分类和预测算法进行分类，比 较了各自的优缺点及适用性，分析了现存算法的不足之处。 2 、针对现存算法的不足，提出了构建概念层次的方法，对空缺值的处理 方法也进行了探讨。 3 、提出一种基于概念分层的分类挖掘算法，通过偏序、格构建概念层次， 利用信息增益选择最佳属性集，并且探讨了算法的增量学习版本，最后针对 该算法在超大型数据处理方面的不足，还给出了一种解决方法。 数据挖掘作为一种新的信息获取技术，为了将之更好的应用于生产生活 实践，本文还探讨了它在决策支持系统中的应用。具体来说，主要做了如下 的工作： l 、分析了传统决策支持系统的研究落入低谷的原因，指出了其不足之处， 探讨了数据挖掘技术在决策支持系统中的地位和作用 2 、介绍了数据仓库的体系结构以及国内外应用状况，研究了数据挖掘技 术和数据仓库技术结合的有效性。 3 、提出了一种新的基于数据仓库和数据挖掘的决策支持系统，并指出了 这种新型决策支持系统的体系结构和关键技术，分析了这种框架构成的特点， 最后对在银行决策支持系统中的应用进行了初步探讨。) 卫一、 ，一 一 厂 关键字：数据挖掘；圆类；预$ 晒决策支持系统；数据仓库， 亘蜜窒婆盔堂亟主塑塞皇兰焦迨塞蔓翌夏 a b s t r a c t n o w a d a y st h es o c i e t yi s f u l lo fa l lk i n d so fi n f o r m a t i o n i tb e c o m e sm o r e a n dm o r ei m p o r t a n tt om a k et h eb e s to ft h ei n f o r m a t i o n a sar e s u l t ，m o r ea n d m o r ep e o p l ef o c u sd a t am i n i n ga n dd e c i s i o ns u p p o r ts y s t e m ，a sab u r g e o n i n g k n o w l e d g ed i s c o v e r yt e c h n o l o g y a n da na s s i s t a n t d e c i s i o n - m a k i n g t o o l r e s p e c t i v e l y a m o n gn u m e r o u sr e s e a r c he m b r a n c h m e n t s o fd a t am i n i n g ，c l a s s i f i c a t i o n a n df o r e c a s t i n gh a v eb e e nt h eh o tr e s e a r c ht o p i c sa l la l o n g m a n ya u t h o r sd i da m a s so fw o r kf r o ma l lk i n d so fv i e w s ，s u c ha ss t a t ，i n f o r m a t i o nt h e o r ya n d n e u r a ln e t w o r ke t c a n do b t a i nas e r i e so fi m p o r t a n tf r u i t s b a s e do nt h ee x i s t i n g r e s e a r c hf r u i t s ，s o m ej o bi sd o n ei nt h e p a p e r a sf o l l o w s ： 1 t h ep r o c e s sm o d e lo fc l a s s i f i c a t i o na n df o r e c a s t i n ga r ed i s c u s s e d t h e e x i s t i n g a r i t h m e t i ci sc l a s s i f i e d b a s e do n c o m p a r i n g t h e i r a d v a n t a g e s a n d d i s a d v a n t a g e s ，t h e i ra p p l i c a b i l i t ya n dd e f i c i e n c y a r ea n a l y z e d 2 a p p r o a c h i n gt ot h ed e f i c i e n c yo f t h ep r e s e n ta r i t h m e t i c ，t h ep a p e rb r i n g s f o r w a r dam e t h o do fc o n s t r u c t i n g c o n c e p t i o nh i e r a r c h y t h ep r o c e s s a b o u t v a c a n c y v a l u ei sd i s c u s s e dt o o 。 3 ac l a s s i f i c a t i o nm i n i n ga r i t h m e t i cb a s e do nc o n c e p t i o nh i e r a r c h yi s p u t f o r w a r d t h ea r i t h m e t i cc o n s t r u c t sh i e r a r c h yb yp a r t i a lo r d e r i n ga n dl a t t i c e ，a n d c h o o s e st h eb e s ta t t r i b u t es e t b y i n f o r m a t i o n p l u s ，t h e n d i s c u s s e si t s i n c r e m e n t l e a r n i n ge d i t i o n ；f i n a l l yg i v eas o l u t i o n t op r o c e s sl a r g ed a t a d a t a m i n i n g ，a sa k i n do fn e wi n f o r m a t i o na c q u i r e m e n t t o o l s ，w i l lb eu s e di n p r a c t i c ea n dp e o p l e sl i f e i nab e t t e rd e g r e ei fa p p l y i n gi tt od e c i s i o ns u p p o r t s y s t e m i nt h ep a p e r , s o m ew o r k i sd o n ea sf o l t o w s ： 1 t h er e a s o nt h a tt h er e s e a r c ha b o u tt r a d i t i o n a ld e c i s i o ns u p p o r ts y s t e m f e l lb e h i n di s a n a l y z e d ，a n dd a t am i n i n g ss t a t u sa n de f f e c ti nd e c i s i o ns u p p o r t s y s t e m a r ed i s c u s s e d 2 t h es y s t e mf r a m e w o r ko fd a t aw a r e h o u s ea n di t s a p p l i c a t i o ns t a t u s i n c h i n aa n do v e r s e a sa r ei n t r o d u c e d ，t h ec o n j o i n tv a l i d i t yo fd a t am i n i n ga n dd a t a w a r e h o u s ei sp r o b e di n t o 3 。an e wk i n do fd e c i s i o ns u p p o r ts y s t e mb a s e do nd a t aw a r e h o u s ea n dd a t a 西南交通大学硕士研究生学位论文第1 l l 页 m i n i n g i sp u tf o r w a r d ，a n di t sf r a m e w o r ka n dk e yt e c h n o l o g ya l ed i s c u s s e d ，t h e n t h es p e c i a l t yo ft h ed s si s a n a l y z e d ，f i n a l l yt h ea p p l i c a t i o no fd s si nb a n ki s d i s c u s s e d e l e m e n t a r i l y , k e y w o r d s ：d a t am i n i n g ；c l a s s i f i c a t i o n ；f o r e c a s t i n g ；d e c i s i o ns u p p o r ts y s t e m ；d a t a w a r e h o u s e 第一章绪论 近年来，随着微电子和计算机技术渗透到各个技术领域，人类正在步入 一个技术迅猛发展的新时期。这个新时期的主要标志是计算机和信息处理的 广泛应用，它不仅大大提高了社会生产力的发展，而且引起了经济结构、社 会结构和生活方式的深刻变化和变革，加快了人类进入信息社会的节奏。在 这一伟大变革中，对信息的获取、分析、加工和利用有着更迫切的需要和更 高的要求。 数据挖掘技术是当今信息科学领域中一门新兴的学科，也是十分活跃的 研究方向之一，它为人类获取有价值的信息提供了新的渠道。由于数据挖掘 技术是一门新兴的技术，也就有很多尚未成熟之处，本文将对其中十分重要 的一个分支一一分类技术迸行研究。另外，通过数据挖掘获取信息的目的是 为了帮助人们更好的进行决策，因此本文还对数据挖掘在决策支持系统的应 用也进行了比较深入的研究。本章将介绍本文的写作背景和主要工作。 1 1 数据挖掘概述 计算机技术发展的历史在某种意义上也是数据自动采集、生成和处理的 历史。目前，全球为各行各业服务的数据库至少有几百万个，数据库不仅在 数量上快速增长，而且在规模上也越来越大。例如，美国宇航部门发射的一 系列地球观察卫星每年发回的数据就有约3 0 万g b 。面对如此庞大的数据资 源，一般管理系统的查询检索机制和统计分析方法已无法有效的满足应用的 需要，形成了“数据丰富，知识贫乏”这一状况。数据挖掘正是在这样的应 用需求背景下产生并迅速发展起来的一个重要的研究领域。通过对数据进行 分析，数据挖掘可以发现重要的数据模式，对商务决策、知识库、科学和医 学研究做出了巨大的贡献。同时，数据挖掘的研究和应用对于人工智能这门 学科的发展又注入了新的活力，有力的促进了计算机科学与技术朝着纵深方 向发展。 西南交通大学硕士研究生学位论文第2 页 1 1 1 数据挖掘的定义 简单说，数据挖掘( d a t am i n i n g ，d m ) 就是从大量数据中提取或“挖 掘”知识。因为与数据库密切相关，又称为数据库中的知识发现( k 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 ，k d d ) 。数据挖掘不但能够学习已有的知识，而且更 着重于设计高效的算法以达到从巨量数据中发现未知的知识。 从数据挖掘诞生至今，人们对于数据挖掘还没有一个统一的定义，但是 随着数据挖掘研究的不断深入，其定义也在不断修改，其中一种比较公认的 的定义是由w j f r a w l e y 、g p i a t e t s k y 、s h a p i r o 1 1 等人提出的： 数据挖掘就是从大量的数据中提取出入们感兴趣的知识。这些知识是隐 含的、事先未知的潜在有用信息，并将提取的知识表示为概念、规则、规律、 模式等形式。 这种定义把数据挖掘的对象定义为大量数据，其中，数据指的是一个有 关事实的集合，如超市销售数据库中的销售信息。它是用来描述事务有关方 面的信息，是我们进一步发现知识的原材料。 数据挖掘的一个显著特征是它所提取的模式是隐含的、事先未知的。这 不同于专家系统仅是对已有知识的学习。并且要将这些新颖的知识以容易被 人理解的形式表现出来，因此挖掘过程也是一个入机交互、螺旋上升的过程， 它需要反复调整，从而挖掘出质量更高更有效的知识】。 1 1 2 数据挖掘的发展简史 数据挖掘于1 9 8 9 年3 月在美国底特律召开的第u 届国际人工智能联合 会议的专题讨论会上被首次提出。它是- - n 新兴的、交叉性学科，涉及到机 器学习、模式识别、统计学、数据库、专家系统等多个领域。但数据挖掘更 强调与数据库的联系。有学者认为数据挖掘是k d d 其中的一个步骤，但本 文将不加区别的使用。 1 9 9 3 年i e e e 的k n o w l e d g e a n d d a t a e n g i n e e r i n g 率先出版了k d d 专刊。 随后，各类k d d 会议、研讨会纷纷涌现，许多领域的国际会议也将k d d 列 为专题讨论。 数据挖掘界于1 9 9 5 年召开了第一届知识发现和数据挖掘国际学术会议 西南交通大学硕士研究生学位论文第3 页 4 1 ，该会议是由1 9 8 9 至1 9 9 4 年举行的四次数据库中知识发现国际研讨会发 展起来的。数据挖掘界于1 9 9 8 年建立起一个新的学术组织a c m - s i g k d d ， 即a c m 下的数据库中的知识发现专业组( s p e c i a li n t e r e s t e dg r o u p o n 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 s ) 。近两年i e e e 和a c m 也分别推出了k d d 专刊，介绍数据挖掘在各个领域的应用成果。 与国外相比，国内对数据挖掘的研究稍晚。1 9 9 3 年国家自然科学基金开 始对数据挖掘研究进行支持。1 9 9 9 年4 月在北京召开的第三届亚太地区k d d 国际会议( p a k d d 9 9 ) 以及2 0 0 1 年的第五届亚太地区k d d 国际会议 ( p a k d d 0 1 ) 极大的推动了数据挖掘在我国的发展。 目前国内有许多高校和科研单位正在从事数据挖掘的基础理论和应用研 究，如清华、北大、复旦、浙江大学等。国内一些年轻的学者还发起并设立 了数据挖掘论坛的n e w s l e t t e r 和网站，如数据挖掘讨论组 h t t p ：w w w d m g r o u p o r g c r d ，已有l o 多万人访问。总之，数据挖掘已越来越 受到重视，无论是学术界还是商业界，数据挖掘都是当前的研究热点之一。 1 1 3 数据挖掘的研究现状 数据挖掘就是从大量数据中发现隐含的知识和规律。经过十几年的发展， 对数据挖掘的研究已从最初表面的、孤立的问题向系统的、全面的方向发展。 b 5 1 。目前，对数据挖掘的研究主要表现在以下几方面： 1 数据挖掘的理论研究。这主要涉及到两方面：一个是数据挖掘的体系 研究，其目的是建立完整的数据挖掘理论体系，建立通用、有效的处理模型， 用科学的方法论指导发现知识的过程，使之成为一种主流技术。近年来在这 方面涌现了许多处理模型【6 , 7 , 8 】、系统框架1 9 , 1 0 和原型系统 1 0 , 1 1 。另一个是数据 挖掘技术的基础理论工具的研究。如新的知识表现的方法、知识发现的逻辑 和方法学以及k d d 中的人为因素的研究等。 2 挖掘技术和算法的研究。这也是目前最集中的研究领域。这一方面的 文献、资料也是最丰富的。由于数据挖掘是应用需求推动下跨学科发展的产 物，所以各个学科中的许多技术成果也都可以移植到数据挖掘中来。传统的 统计方法1 2 1 、决策树【1 3 , 1 4 1 、聚类15 1 、集合论、关联规则f 1 6 1 9 1 ，近年来，还有 些软计算方法也引入到数据挖掘领域中来，如粗糙集理论 2 0 - 2 5 】、人工神经 网络2 6 2 9 1 、遗传算法和进化算法【3 0 】等等。但是数据挖掘又有其自身的特性， 西南交通大学硕士研究生学位论文第4 爱 他面对的是大量数据甚至是海量的数据，因此这些领域中的技术不能全部照 搬。如神经网络，由于获取的知识以权值的形式隐含在网络中虽然可以解 决其传统领域中的控制以及预测的功能，但由于其知识表示的难以理解性， 在数据挖掘中，往往需要和其它技术结合起来使用，如已有学者提出了基于 神经网络和决策树的算法u 1 1 。另外，数据挖掘与数据库系统和数据仓库系统 的集成也是个研究方向。 3 应用研究。主要针对应用将数据挖掘系统进行特化。按照应用系统处 理豹数据类型可划分为时间序列数撂挖蔼f 3 2 , 3 z l 、空阉数据挖掘f 3 4 ”i 、文本数 据挖掘 3 4 】等：按照应用的领域分类，可以划分为证券分析与预测系统【3 7 1 、 信再3 风险分析i 弛l 、信用卡欺诈分析、生物工程【强 等。随着i n t e r n e t 的普及和 发展，对i n t e m e t 数据的挖掘，如站点访问模式分析，成为当今一个十分活 跃的应用领域研究方向p “。 1 1 ，4 处理过程模型 由于数据挖掘是一个需要重复调整、反复的多次处理过程因此有必要 对其处理过程模型进行探讨，为数据挖掘提供宏观指导和实现方法。合理的 处理过程模型可以将各个处理阶段有机的结合在一起，更好的发挥整个数据 挖掘系统的效能。从数据挖掘进入应用领域起。就有人对数据挖掘的过程归 纳和总结，现在比较通用的是由u m f a y y e d 、g p i a t e t s k y s h a p i r o 等人提出 的多处理阶段模型【1 1 ，其基本过程说明如下： f 1 ) 数摆准备 了解k d d 相关领域的有关情况熟悉有关的背景知识，并弄清楚用户 的要求。 ( 2 ) 数据选择 根据用户的要求从数据库中提取与k d d 相关的数据，k d d 将主要从这 些数据中进行知识提取，在此过程中，会利用一些数据库操作对数据进行处 理。 ( 3 ) 数据预处理 主要是对阶段2 ) 产生的数据进行再加工，检查数据的完整性及数据的一 致性，对其中的噪音数据进行处理，对丢失的数据可以利用统计方法进行填 补。 西南交通大学硕士研究生学位论文第5 页 f 4 1 数据转换 对经过预处理的数据，根据知识发现的任务对数据进行再处理，使之转 换为有效形式，以使数据挖掘更有效。这主要是通过投影或数据库中的其他 操作进行数据变换或数据约筒。 ( 5 ) 数据挖掘 根据知识发现任务的要求，选择合适的数据挖掘算法( 包括选取合适的 模型和参数) ，从数据中提取出用户感兴趣的知识，这些知识可以用一种特定 的方式表示或使用一些常用的表示方式如产生式规则等等。 f 6 ) 模式解释 对发现的模式进行解释，在此过程中，为了取得更为有效的知识，可能 会返回到前面处理过程中的某些步骤以反复提取，从两挖掘出更有效的知识。 ( 7 ) 知识评价 将发现的知识以用户能理解的方式呈现给用户。这期间也包含对知识的 一致性的检查，以确信本次发现的知识不与以前发现的知识相抵触。 在上述的每个处理阶段，k d d 系统会提供处理工具完成相应的工作。在 对挖掘的知识进行评测后，根据结果可以决定是否重新进行某些处理过程， 在处理的任意阶段都可以返回以前的阶段进行再处理。这也再一次说明了数 据挖掘过程不是简单的线性流程，步骤之间包含了循环和反复。 1 1 5 数据挖掘的功能 数据挖掘的功能用于指定数据挖掘可阱挖掘什么类型的模式。数据挖掘 任务一般可以分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的 一般特性，预测性挖掘任务在当前数据上进行推断，以进行预测。 在某些情况下，用户不知道它们的数据中什么类型的模式是有趣的，因 此可能想并行的搜索多种不同的模式。这样，数据挖掘系统要能够挖掘多种 类型的模式，以适应不同的用户需求或不同的应用。此外，数据挖掘系统应 能够发现不同j 宜度( 即不同抽象层) 的模式。 数据挖掘功能以及它们可以发现的模式主要有以下几类： 概念类描述：特征化和区分。这主要是指用汇总的、简洁的、精确的方 式描述每个类和概念。 关联分析：关联分析即时发现关联规则，这些规则展示属性一值频繁的在 西南交通大学硕士研究生学位论文第6 页 给定数据集中一起出现的条件。关联分析广泛应用于购物篮或事务数据分析。 分类和预测：分类指找出描述并区分数据类或概念的模型( 或函数) ，以 便能够使用模型预测类标记未知的对象类。导出模型是基于对训练数据集( 即 其类标记已知豹数据对象) 的分析。 聚类分析：与分析和预测不同，聚类分析数据对象，而不考虑已知的类 标记。对象根据最大化类内的相似性、最小化类间的相似性的原则进行聚类 或分组，使得每个组内的对象具有很高的相似性，而与其它组中的对象很不 相似。 孤立点分析：数据库中包含的一些与其它数据的一般行为或模型不一致 的数据对象称为孤立点，在一些应用中，罕见的事件可能比正常出现的那些 更有价值，孤立点分析即是对孤立点进行挖掘。 演变分析：数据演变分析描述行为随时间变化的对象的规律或趋势，并 对其建模。尽管这可能包括前述的一些功能，但这类分析的不同特点包括时 间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 1 1 6 数据挖掘和相关学科的区别与联系 数据挖掘是一门交叉学科领域，受多个学科的影响( 如图l - 1 ) ，包括机 器学习、统计学、数据库技术、可视化和信息科学等等【l 。- 1 3 】。 图l - 1 数据挖掘的相关学科 机器学习被认为与数据挖掘的关系最为密切，它们都是可以自学习的技 术，但二者存在着一个主要的区别：数据挖掘的任务是发现可以理解的知识， 而机器学习更注重于提高系统的性能。如训练神经网络来对控制某个工业流 亘蜜窒望盔堂塑主堡塞生堂垡迨窒蔓! 夏 程是一种机器学习的过程但不是数据挖掘，它没有提供可以为用户所理解 的知识。另外，数据挖掘与机器学习处理的数据集大小也有区别，数据挖掘 要处理的数据量非常巨大，而机器学习处理的数据集要小得多，通常只需用 内存即可全韶处理。所以数据挖握算法鲍效率和可扩展牲就显褥至关重要。 、数据挖掘和统计学也有某些相通之处，它们都是从数据中得到知识，但 它们依旧存在着不同点：统计学在进行数据分析时更多的是依靠给定模型， 参数估计，假设检验等，而数据挖掘主要考虑的是模型的复杂性，挖掘的复 杂性，挖掘速度和耩度，可概括性等。 数据库技术为数据挖掘提供了强大的数据来源，虽然数据库也可以对数 据进行处理和分析，但其主要功能是存储数据，对于数据的分析只是简单的 报表汇总和查询。面数据挖掘主要是对隐含在数据背后的特征和趋势进行分 析，最终给出用户需要的相关知识。另外，数据挖掘与数据库的查询机制也 有所区别，传统的数据库查询有蘅严格的查询表达式，建立在s q l 体系之上。 而数据挖掘常常表现出即时、随即的特点。挖掘过程往往基于统计规律，产 生的规则并不要求对所有的数据项总是成立，而是只要到达一定的阈值即可。 最后，数据挖掘还可能在数据库的不同层次上进行挖掘。 其它几门技术主要是为数据挖掘提供辅助工具，如高性能计算机技术的 发展为数据挖掘在超大型数据库或数据仓库上进行挖掘提供了可能性，可视 化技术使数据挖掘开采的知识具有更强的可理解性。最大程度上让用户参与 到数据挖掘系统中来。 1 ，1 7 数据挖掘的应用与发展方向 数据挖掘是如此重要的策略应用，以至于许多公司不会透露他们的计划。 根据美国t w og r o w s 公司睁】所做的一项调查表明。数据挖掘的3 令最重要的 终端应用是在销售领域：客户概况、目标市场和购买方式分析。 在客户概况中，通过预测谁将会帮助商家发现新的前景来确定好顾客的 特点。数据挖掘可以在客户数据库中发现一种模式将它应用到一个期望的 数据库中，就能够使获得客户的目标得以实现。饼如，通过鍪尉可以提供邮 寄和目录的候选人，邮购商可以降低成本和增加销售，针对已有客户和潜在 客户的促销活动可以获得相应的效益。 购买方式分析可以帮助零售商了解顾客会同时购买哪些商品，使用数据 一一一 亘壹窑亟盔堂塑主堑窒圭堂丝迨塞 星! 垂 _ _ _ - - - - _ _ _ - _ - _ - 。= 一 挖掘，零售商能够确定哪些商品应放在哪些商店，甚至在商店中如何摆放这 些商品，数据挖掘还可以用来评估促销和优惠券的效果。 数据挖掘在许多毒几构中的另一通常用途是帮助管理顾客关系，通过分析 确定那些可能离开并走向竞争对手的顾客特点，公司可以采取行动留住这些 顾客，因为这样做比招徕新顾客的花费要小的多。 企业由于被诈骗而遭受的损失是非常巨大的。因此，通信公司、信用卡 公司、保险公司、股票交易所、政府机构等对诈骗侦测有极高的兴趣和热情 使用数据挖掘技术，这些机构可以识别潜在的诈骗交易，进而控制可能发生 的伤害。金融公司可以使用数据挖掘技术来确定市场和工业特征，并预测某 一公司和股票的运作情况：数据挖掘技术另一个有趣的应用是医药行业：它 能够帮助预测手术过程的效率、诊断测试、药物治疗、服务管理和过程控制。 数据挖掘作为一门新兴的学科，其成功应用案例已是枚不胜举。但鉴于 数据、数据挖掘任务和数据挖掘方法的多样性，数据挖掘还面临着许多挑战 性的课题p q ： 应用领域的探索：这是数据挖掘最吸引入的地方，也是推动数据挖掘发 展的根本动力。一方面，数据挖掘需要向更多的应用领域渗透。随着电子商 务和电子市场逐渐成为零售业的主流因素，数据挖掘也在不断扩展其在商业 领域的应用面。另一方面，需要开发更多面向应用的数据挖掘系统和产品， 建立行业内的数据标准和通用数据挖掘平台，建立可交换信息和共享知识的 通用数据仓库是今后要解决的问题。 挖掘技术和算法的研究：它包括为各种各样的挖掘任务寻找好的算法以 及算法的改进与优化、新技术新方法在数据挖掘中的应用、并行算法的设计 与实现等。此外，数据挖掘往往直接面对的是现实数据，因此对不完整、不 确定或有噪声的数据以及各种不同类型的数据进行处理也是数据挖掘必须解 决的问题。其中数据挖掘还要着重解决如下的两个问题： ( 1 ) 用户参与和领域知识：数据挖掘的对象是某一专业领域积累的数据： 挖掘过程是个人机交互、多次反复的过程：挖掘的结果要应用于该专业。 因此数据挖掘的整个过程都离不开应用领域的专业知识。目前的数据挖掘系 统或工具很少能真正做到让用户参与到挖掘过程中，用户的背景知识和指导 作用可以加快挖掘的进程，并且保证发现的知识的有效性，将相关领域的背 景知识融入到数据挖掘系统中是一个重要但还没有很好解决的问题。 ( 2 ) 知识的维护和更新：新的数据积累可能导致以前发现的知识失效，这 亘妻室望盔兰塑主塑塞兰堂焦遥窒兰! 要 些知识需要动态维护和动态更新。如何有效瑰利用已有的知识和信息来更新 知识将是今后研究的重点。 数据挖掘与数据库系统、数据仓库系统和w e b 数据库系统的集成：数 据库系统、数据仓库系统和w e b 数据库系统已经成为信息处理系统的主流 保证数据挖掘作为基本的数据分析模块能够顺利的集成到此类信息处理环境 中，是十分重要的。这将保证数据的可获得性，数据挖掘的可移植性，可伸 缩性，高性能，以及对多维数据分析和探查的集成信息处理环境一 复杂数据类型挖掘的新方法：这是数据挖掘中一顼重要的前沿研究课题。 虽然在地理空间挖掘、多媒体挖掘、时序挖掘以及文本挖掘方面取得一些进 展，但它们与实际应用的需要仍存在很大的距离t 对此需要进一步的研究， 尤其是把针对上述数据类型的现存数据分析技术与数据挖掘方法集成起来的 研究。 数据挖掘中的隐私保护与信息安全：随着数据挖掘工具和电信与计算机 网络的日益普及，数据挖掘要面对的个重要问题是隐私保护与信息安全。 需要迸一步开发有关方法，以便在适当的信息访闻积挖掘过程中确保隐私保 护与信息安全。 1 ，2 本文工作简介 1 2 1 研究思路 分类和预测是数据挖掘中一个十分重要的研究领域，有着几乎最广泛的 应用范围，在商务领域中普遍存在。有很多成功的应用案例，如客户购买行 为分析、信用评级、畅销商品分类、医疗诊断、客户忠诚度分析、股票预测、 客户关系管理等等。目前对分类和预测的研究比较集中于挖掘算法的研究， 已出现了许多的挖掘算法，包括来自机器学习、专家系统、统计学和神经生 物学方面的各种技术，每种算法各有其优缺点，由于在理论上还没有发现有 一种方法对所有数据都优于其他方法。如准确性。训练时间、鲁棒性、可解 释性和可伸缩性都必须考虑在内，因此对现有众多的算法进行分类研究就显 得很有必要。在对现有分类和预测研究的不足进行分析的基础之上，集合考 虑提取模式的有效性，提出种改进的分类挖掘算法以提高原有算法的性能， 另一方面，考虑到数据挖掘最根本的功熊是提取对用户有用的模式( 或 _ _ _ _ _ _ _ _ _ _ _ _ _ _ o o o _ o _ - _ o 一i i i i _ _ o o _ - - 。_ _ _ _ _ _ _ _ _ 一 西南交通大学硕士研究生学位论文第1 0 页 知识) ，以及数据挖掘当今的一个发展方向一一与数据库系统、数据仓库系统 的集成，因此对数据挖掘在决策支持系统中的应用研究也显得自然并且很重 要，它不仅可以使决策支持系统注入新的活力，也使数据挖掘自身的应用在 很大范围上进行了扩展。 1 2 2 主要工作 鉴于以上的研究思路，本文主要做了以下的工作： 一、数据挖掘中分类和预测的研究 1 探讨了分类和预测的处理模型，对现有分类和预测算法进行分类，比 较了各自的优缺点及适用性，分析了现存算法的不足之处。 2 针对现存算法的不足，提出了构建概念层次的方法，对空缺值的处理 方法也进行了探讨。 3 提出种基于概念分层的分类挖掘算法，它通过偏序、格构建概念层 次，利用信息增益选择最佳属性集，并且探讨了算法的增量学习版本，最后 针对该算法在超大型数据处理方面的不足，给出了一种解决方法。 二、 数据挖掘在决策支持系统中的应用研究 1 ，分析了传统决策支持系统研究落入低谷的原因，指出了其不足之处， 探讨了数据挖掘技术在决策支持系统中的地位和作用 2 介绍了数据仓库的体系结构以及国内外应用状况，探讨了数据挖掘技 术和数据仓库技术结合的有效性。 3 提出了一种新的基于数据仓库和数据挖掘技术的决策支持系统，指出 了其体系结构和关键技术，分析了这种框架构成的特点，最后给出了一个应 用实例。 1 2 3 结构安排 本文共分为五章。第一章介绍了数据挖掘的基本思想和它的研究现状。 第二章对现有各种分类和预测算法进行了比较和分析，指出了不足之处。第 三章在第二章的基础上，提出了一种基于概念分层的分类挖掘算法，研究了 它的一些特点，并对其在处理超大数据集方面的不足，给出了一种基于数据 仓库的解决方法。第四章针对传统决策支持系统( d s s ) 的不足，结合数据仓 西南交通大学硕士研究生学位论文第l1 页 库技术的特点和数据挖掘以及决策支持系统的联系，给出了一种新的决策支 持系统框架。第五章是本文的结论和一些尚需要进一步研究的问题，也指出 了数掘挖掘和决策支持系统的发展趋势。结构如图1 - 2 所示。 图1 - 2 本文的组织结构 ，。l 亘壹奎夔盔堂塑主堡塞生堂丝迨塞 整! ! 夏 第二章分类和预测研究 分类和预测是数据挖掘的主要方法之一，用于提取描述重要数据类的 模型或预测未来的数据趋势。其本质是通过分析数据为每个类做出准确的 描述或建立模型，然后用它对数据库中的数据进行分类，或将之上升为分 类规则。不同的是，分类是预测分类标号( 或离散值) ，而预测建立连续值 函数模型。 本章抽象出分类和预测的过程，对分类算法依据其执行特征和所采用 的技术进行了分类，分析和比较了不同算法的优缺点，并探讨了推广的分 类和预测问题，最后指出了现有分类和预测算法的不足。 2 1 分类和预测的过程 数据分类是一个两步过程。 第一步，建立一个模型，描述预定的数据类集或概念集。通过分析由属 性描述的数据库元组来构造模型。假定每一条记录都属于一个确定的类别， 由一个称作类标号属性的属性确定，为建立模型而被分析的数据元组形成训 练数据集。训练数据集中的单个元组称作训练样本。通常，学习模型用分类 规则、判定树或数学公式的形式提供。例如，给定一个顾客信用信息的数据 库，可以学习分类规则，根据他们的信誉度优良或相当好来识别顾客( 见图 2 1 a ) 。 第二步( 见图2 - i b ) ，使用模型进行分类。首先评估模型( 分类法) 的 预测准确率。如果模型的准确率可以接受，就用它对类标号未知的数据元组 或对象进行分类。例如，在图2 1 a 通过分析现有顾客数据学习得到的分类规 则可以用来预测薪的或未来顾客的信誉度。 预测是构造和使用模型评估无标号样本类，或评估给定样本可能具有的 属性值或值区间。在这种观点下，分类和回归是两类主要预测问题，其中分 类是预测离散或标称值，而回归用于预测连续或有序值。然而，在本文中的 观点是：用预测法预测类标号为分类，用预测法预测连续值为预测。这种观 点在数据挖掘界被广泛接受。 a ) 学习：训练集( t r a i n i n gd a t a ) 被分类算法( c l a s s i f i c a t i o na l g o r i t h m ) 分析进而生成分类舰则 ( c l a s s i f i c a t i o n r u l e s ) a 样本向量；( n a m e ，a g e ，i n c o m e ；c r e d i tr a t i n g ) ，类标签c r e d i tr a t i n g e x c e l l e n t b ) 分类：测试数据( t e s td a t a ) 用来建立准确的分类规则，如果准确性能被接受，则分类规则将 用来对鞒数撂进 亍分类， 图2 - 1 数据分类过程 堕蜜窑堕盔堂亟主丛塞生兰篁迨塞蔓! 兰夏 2 2 算法分类 用于分类和预测的算法有很多，涉及的技术面在数据挖掘的各种方 法中也最广。 从采用的技术来看，可以分为以下几大类： 基于信息论 主要包括决策树系列算法，如i d 3 ，c 4 5 ，s l i q ，s p r i n t 。这些算法主要依 据信息论中的熵理论进行属性选择，从而对数据分类。 基于概率统计 主要包括贝叶斯，贝叶斯网络，回归算法，贝叶斯分类基于贝叶斯定理进 行属性选择，回归预测依据统计技术建立模型对连续值属性进行预测。 基于人工智能 主要包括向后传播、遗传算法。向后传播分类利用神经网络构造模型对 数据进行分类和预测，遗传算法利用生物进化豹思想达到优化。 基于要求 主要包括最临近分类、基于案例的推理。最临近技术通过k 个最与之相 近的历史纪录的组合来辨析新的纪录：基于案例的推理通过搜索最贴近的案 例对未知样本进行分类和预测。 从算法的执行特点来分，以上算法可以归为两大类： 急切分类 急切分类的算法又称为贪心算法，包括决策树、贝叶斯、神经网络等算 法。它的策略是寻求局部最优，以期代替全局最优，在实践中这类算法很有 效。 懒散分类 懒散分类包括缸最邻近、基于案例的推理等算法，它的策略是存放所有 的训练样本，并且直到新的( 为标记的) 样本需要分类时才建立分类。这与 诸如判定树归纳和向后传播这样的急切分类形成鲜明对比，后者在接受待分 类的新样本之前构造一个般模型。 两类算法的比较 当与给定的无标号样本比较的可能的临近者( 即存放的训练样本) 数量 很大时，懒散学习法可能导致很高的计算开销。懒散学习法在训练时比急切 西南交通大学硕士研究生学位论文第1 5 页 学习快，但在分类时慢，因为所有的计算都推迟到那时。另外，与判定树归 纳和后向传播不同，最临近分类对每个属性指定相同的权。当数据中存在许 多不相关属性时，可能引起混乱。 2 3 典型算法介绍与分析 分类和预测中的算法虽然有很多，但最基本最典型的是决策树算法、向 后传播算法、贝叶斯算法、回归建模。下面分别对其进行介绍。 ( 1 ) 决策树分类决策树是一个类似于流程图的树结构，其中每个内部节 点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个叶结点代 表类或类分布。决策树生成算法分成两个步骤，第一步是树的生成，开始数 据都在根节点，递归的进行数据分片；第二步是树的修剪，去掉一些可能是 噪音或者异常的数据。 决策树生成算法是一种自上而下分而制之的方法( 见图2 - 2 ) ，其基本策 略如下： 开始时，所有的数据都在根节点 属性都是种类字段f 如果是连续的，将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量( 如， i n f o r m a t i o ng a i n ) 停止分割的条件 ( a ) 一个节点上的数据都是属于同一个类别 ( b ) 没有属性可以再用于对数据进行分割 p r o c e d u r eb u i l d t r e e ( s ) 用数据集s 初始化根节点r 用根结点r 初始化队列q w h i l e q i sn o t e m p t yd o 取出队列q 中的第一个节点n i f n 不纯( p u r e ) f f o r 每一个属性a 估计该节点在a 上的信息增益 西南交通大学硕士研究生学位论文第1 6 页 选出最佳的属性，将n 分裂为n i 、n 2 ) ) 图2 - 2 决策树生成的基本算法 树剪枝是为了消除决策树的过适应( o v e r f i t t i n g ) i n l 题，其实质是消除训 练集中的异常和噪声，常用的有先剪枝和后剪枝两种方法，其剪枝原则也有 两种， 最小描述长度原则( m d l ) 思想：最简单的解释最期望的 做法：对d e c i s i o n t r e e 进行二进位编码，编码所需二进位最少的树 即为“最佳剪枝树” 期望错误率最小原则 思想：选择期望错误率最小的子树进行剪枝 做法：对树中的内部节点计算其剪枝不剪枝可能出现的期望错误 率，比较后加以取舍 一颗训练好的决策树可用来对未知数据进行分割，只要按照决策树上采 用的分割属性逐层往下，直到一个叶子节点，即得到该未知数据的预测值。 决策树方法的优点是直观、易学，缺点是随着数据复杂性的提高，其分 支树也增多，因此管理也就越困难。另外，还存在数据缺值问题，这个问题 在大多数决策树产品中都涉及到，只是大多数都没有解决好。 ( 2 ) 向后传播分类向后传播是一种神经网络学习算法。粗略的说，神经 网络是一组连接的输入输出单元，其中每个连接都与一个权相联。向后转播 传播通过迭代的处理一组训练样本，将每个样本的网络预测与实际知道的类 标号比较，进行学习。对于每个训练样本，修改权，使得网络预测和实际类 之间的均方误差最小。一般的，权将最终收敛，学习过程停止。算法冤图2 3 。 输入：训练样本s a m p l e s ，学习率，多层前馈网络n e t w o r k 。 输出：一个训练的、对样本分类的神经网络。 方法： 初始化n e 舢。船的权和偏置。 w h i l e 终止条件不满足 f o rs a m p l e s 中的每个训练样本f 西南交通大学硕士研究生学位论文第! ! 夏 ，向前传播输入 f o r 隐藏或输出层每个单元j ，= ，o j + q ； 0 = l ( 1 + e 1 协 f o r 输出层每个单元j e r r , = o j ( 1 一o j ) ( t o j ) ； f o r 由最后一个到第一个隐藏层，对于隐藏层每个单元j e r r i = o i q oj k 勖r k m f o rn e t w o r k 中每个权国“ 既= ( 1 ) e r r j o j ； = + ；) f o rn e t w o r k 中每个偏差口， q = ( ，) 吼； b = 嘭+ a o j ： 图2 - 3 向后传播算法 神经网络适用于无指导的学习，尤其作为预测模型，在商业界得到广泛 应用。一般说来，要在神经网络复杂性、精确度和建立神经网络所花费的时 间之间进行综合考虑。神经网络的优点是可以精确的对复杂问题进行预测、 评估，但它也有一些缺点：第一，难于理解；第二，易于受训练过度的影响： 第三，训练速度比较慢。 ( 3 ) 贝叶斯分类贝叶斯分类基于贝叶斯定理，假定一个属性值对给定类 的影响独立于其他属性的值，这一假定称作类条件独立。做此假定是为了简 化所需计算，并在此意义下称为“朴素的”。朴素贝叶斯分类的工作过程如图 2 4 。 输入：数据样本