（计算机软件与理论专业论文）基于c45算法的数据挖掘应用研究.pdf

哈尔滨理t 大学工学硕士学位论文 基于c 4 5 算法的数据挖掘应用研究 摘要 近几十年来，数据库技术和海量存储器等硬件的快速发展使得人们收集 数据的能力得到进一步的提高。面对信息时代海量数据的出现，如何有效地 利用大量的原始数据分析现状以预测未来，已经成为人类面临的一大挑战。 由此，数据挖掘技术应运而生并得以迅猛发展。目前，数据挖掘已经成为一 个研究热点，数据挖掘所得到的知识能够为决策支持提供依据。 i i 型糖尿病患病率在全球范围内呈上升趋势，其隐匿起病、患病率随年 龄增大而增加等特点表明这一疾病发展为渐进型疾病。针对这一疾病发生发 展的规律，本文尝试用数据挖掘算法来发现规律，将数据挖掘算法引入i i 型 糖尿病的发病规律研究中，希望从大量的数据中学习i i 型糖尿病的发病规 律，挖掘出需要的数据和规则，构造糖尿病的分类和预侧系统。 本文的原始数据来源于对患者的临床检验报告。临床检验报告的内容经 过适当的转换存入数据库中作为原始数据。针对这些数据的不完整性、有噪 声性和不一致性，本文用数据清理、数据变换、数据归约等数据挖掘的预处 理技术处理这些原始数据。 本文数据挖掘的任务是从众多的糖尿病数据中挖掘出致病规律，为糖尿 病的预防，诊断和预测构造决策系统。由挖掘任务的分类性和对挖掘算法的 要求，本文选用了决策树方法来进行数据挖掘。同时，由于糖尿病数据的连 续性，选用了决策树方法中的c 4 5 算法作为数据挖掘算法。 在实现c 4 5 算法的基础上，本文在糖尿病数据上进行了发病规律的学 习和规则提取，在预处理过的数据的基础上生成了一组糖尿病的诊断与预测 规则。并用分类法的保持评判方法评判其正确率。针对上述决策树对患病人 群的正确率不够理想的情况，提出了以训练集的比例因子变量为参数，试验 了患病人群的正确率和正确率均值随比例因子变量的变化关系给出了一个经 过改进的分类器和判定患病人群的解决方案。 关键词数据挖掘：决策树；c 4 5 算法；i i 型糖尿病 哈尔滨理工大学t 学硕士学位论文 a p p l i c a t i o na n dr e a s e a r c ho f d a t am i n i n gb a s e d o nc 4 5a l g o r i t h m a b s t r a c t i nt h el a s td e c a d e s ，t h ed a t a b a s et e c h n o l o g i e sa n dm a g n a n i m i t ym e m o r y t e c h n o l o g i e sh a v ed e v e l o p e dm u c h a ti n f o r m a t i o na g e ，o r i e n t e dt oag r e a td e a l o fd a t a ，h o wt ou t i l i z et h eh u g eo r i g i n a ld a t at oa n a l y s i st h ec u r r e n ts i t u a t i o na n d p r e d i c t t h ef u t u r ee f f e c t i v e l y , h a v ea l r e a d yb e c o m eag r e a tc h a l l e n g et h a tt h e m a n k i n dh a sf a c e d t h e r e f o r et h ed a t am i n i n gt e c h n o l o g yi sa r i s e da tt h eh i s t o r i c m o m e n ta n dc a n b ed e v e l o p e dr a p i d l y r e c e n t l y , d a t am i n i n gh a sb e e no n eo fh o t r e s e a r c ha r e a t h ek n o w l e d g ed i s c o v e r e db yd a t am i n i n gt e c h n o l o g i e sc a nb e u s e dt oo f f e rd e c i s i o n s u p p o r t t h et y p ei id i a b e t e sm e l l i t u sc a s e sa r ei n c r e a s e dr a p i d l yr e c e n t l yi nt h e w o r l d t h eg r o w i n go fa g ei n c r e a s e st h ei n c u b a t i o np e r i o da n di l l n e s sr a t eo f t y p ei i d i a b e t e sm e l l i t u sc a s e s ，w h i c hi n d i c a t e st h a tt h i sd i s e a s ei sak i n do f p r o g r e s s i v e d i a b e t e sm e l l i t u s i n r e s p o n s e t ot h i sd i s e a s ei nt h er u l e so f d e v e l o p m e n t ，w ea t t e m p t st ou s ed a t am i n i n ga l g o r i t h m st od i s c o v e rr u l e s ，w e i n t r o d u c ed a t am i n i n gi nt h ep a t h o g e n yr e s e a r c ho ft y p ei id i a b e t e sm e l l i t u s ，i n o r d e rt oo b t a i nt h ek n o w l e d g eo ft y p e2d i a b e t e sm e l l i t u sp a t h o g e n y , t od i s c o v e r t h er e q u i r e dd a t aa n dr u l e s ，a n dt h e nt os t r u c t u r et h ec l a s s i f i c a t i o na n d p r e d i c t i o n s y s t e mo fd i a b e t e sm e l l i t u s t h es o u r c ed a t ao fd i a b e t e sm e l l i t u so r i g i n a t e sf r o mt h eh e a l t he x a m i n a t i o n r e p o r t so np a t i e n t sa n dr a n d o ms a m p l i n g w i t ht h ea p p r o p r i a t et r a n s f o r m i n gt h e d a t ai nt h eh e a l t he x a m i n a t i o nr e p o r t sa n ds t o r i n gt h ed a t ai nt h ed a t a b a s e ，w e c a ng e tt h es o u r c ed a t a f o rt h ei n c o m p l e t e n e s s ，n o i s i n e s sa n di n c o n s i s t e n c yi n t h e s ed a t a ，w eu s es o m ep r e p r o c e s st e c h n o l o g i e so fd a t am i n i n g ，s u c ha sd a t a c l e a n i n g ，d a t at r a n s f o r m a t i o na n dd a t ar e d u c t i o n ，t op r o c e s st h e s es o u r c ed a t a t h ed a t am i n i n gt a s ki st of i n dt h ei l l n e s sr e g u l a r i t yf r o mh u g ed i a b e t e s m e l l i t u sd a t a ，t oo r g a n i z et h ed e c i s i o ns y s t e mt o p r e v e n t ，d i a g n o s ea n dp r e d i c t t h ed i a b e t e sm e l l i t u s d e p e n d i n go nt h em i n i n g m i s s i o nc l a s s i f i c a t i o na n dt h e 哈尔滨理t 大学工学硕十学位论文 m i n i n ga l g o r i t h mr e q u i r e m e n t ，w ec h o o s ed e c i s i o nt r e em e t h o dt o d od a t a m i n i n g a l s o ，f o rt h ec o n t i n u i t yi n d i a b e t e sm e l l i t u sd a t a ，c h o o s i n gt h ec 4 5 a l g o r i t h mi nd e c i s i o n t r e em e t h o dt ob et h ed a t am i n i n ga l g o r i t h m o nt h eb a s i so ft h ei m p l e m e n to fc 4 5a l g o r i t h m ，w el e a r nt h ek n o w l e d g eo f i l l n e s sr e g u l a r i t ya n dr u l e sf r o md i a b e t e sm e l l i t u sd a t a ，a n dg e n e r a t eas e to f r u l e so fd i a b e t e sm e l l i t u s d i a g n o s t i c s a n d p r e d i c t i o nd e p e n d i n g o nt h e p r e p r o c e s s e dd i a b e t e sm e l l i t u s d a t a i na d d i t i o n ，w i t ht h eh o l d o u tm e t h o di n c l a s s i f i c a t i o nt od e t e r m i n et h ea c c u r a t er a t e b e c a u s et h ea c c u r a t er a t eo fi l l n e s s g r o u pd e r i v e df r o mt h ed e c i s i o n t r e ea b o v ei sn o tp r e c i s ee n o u g h ，w eb r i n gu p t h er a t i oo ft h et r a i n i n gs e ta st h ep a r a m e t e r st ot e s tt h ea c c u r a t er a t eo fi l l n e s s g r o u pa n dt e s tt h ev a r i a t i o na s s o c i a t e dw i t ht h ea v e r a g ea c c u r a t er a t ev a r i e df r o m t h er a t i o f r o mt h i sm e t h o d ，w ec a np r o v i d ea ni m p r o v e dc l a s s i f i e ra n dab e s t s o l u t i o nt od e t e r m i n et h ei l l n e s sg r o u p k e y w o r d s d a t am i n i n g ，d e c i s i o nt r e e ，c 4 5a l g o r i t h m ，d i a b e t e sm e l l i t u s 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于c 4 5 算法的数据挖掘应用 研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研 究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或 撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以明确 方式注明。本声明的法律结果将完全由本人承担。 作者签名：云玉屏日期：如咕年；月厶日 哈尔滨理工大学硕士学位论文使用授权书 基于c 4 5 算法的数据挖掘应用研究系本人在哈尔滨理工大学攻读硕士学 位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学 所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工 人学天一_ j 二保存、使用学位沦义的规定，同意学校保留并向有关部fj 提交论文和ip 乜 j ，版奉，允以：论文铍台蒯和借蒯。本人授权哈尔滨理：一i ：人学町以采川影印、缩印 或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密 口， 在年解密后适用授权书。 不保密口。 ( 请在以上相应方框内打) 作者签名：云且屠 r 期：潲年5 月必同 导师签名： 袜磊 l | - l 期：又形 多 ，3h 哈尔滨理t 大学工学硕士学位论文 第1 章绪论 1 1 课题背景及研究意义 随着社会经济的进步与发展，威胁人类健康的疾病谱正在发生变化。慢性 非传染性疾病对国民尤其是老年人群的健康的威胁越来越大，最为明显的是i i 型糖尿病在全球范围内的几近流行的上升趋势。i i 型糖尿病的隐匿起病、患病 率随年龄增大而增加等特点表明这一疾病发展为渐进型糖尿病，对发病进行控 制首先涉及对这一疾病的了解。了解这一疾病发生发展的规律，针对重要途 径、重点人群入手，才能达到理想的预防和诊断效果。探讨i i 型糖尿病发病规 律是控制其发生的重要、基础的一步m 。 1 传统糖尿病研究的局限性对控制糖尿病这类非传染性疾病的传统研究 用的是线性还原式的研究方法，但这种方法现在看来，存在着相当的局限性， 至少现在i i 型糖尿病的患病率在全世界范围内仍在不断地上升就是一个急需解 决的现状。 多年来，对控制糖尿病这类非传染性疾病的研究延袭着来自控制传染性疾 病的思路。采用线性还原的思维方法试图搞清发病机制、重要关键的致病物质 之后最终达到有效的治疗与控制。在这种思想的指导下，无论在发病机制还是 在诊疗方法的研究上都投入了不可计数的人力与物力。i i 型糖尿病的患病率在 全世界范围内仍在不断地上升。这使得我们不得不对这样的研究方法提出疑 问，线性还原式的研究方法能否解决现在面对的由复杂因素综合致病的i i 型糖 尿病的发病规律问题。 2 将数据挖掘引入糖尿病研究由于线性还原式的研究方法的局限性，用 数据挖掘算法对i i 型糖尿病的发病规律进行研究，希望从大量的糖尿病数据中 学习i i 型糖尿病的发病规律的知识，挖掘出需要的数据和规则，构造糖尿病的 分类和预测系统。 计算机科学技术与生物信息学是密切相关的关系心1 。与生物信息学密切相 关的计算机科学技术主要有：网络技术和数据库( 特别是关系型数据库) 管理技 术，包括极为重要的实验室数据信息管理系统( l i m s ) 、数据整合和可视化、 数据挖掘( d a t am i n i n g ) 、基于操作系统的各种软件包以及人工智能，和一些重 要算法的复杂性研究。”。 数据挖掘作为生物信息学的一个主要技术，将挖掘算法引入i i 型糖尿病的 发病规律研究中。它能从巨大的糖尿病数掘中挖掘出需要的数据和规则。由f 哈尔滨理工大学工学硕上学位论文 数据挖掘可以从大规模数据中自动进行规则的提取，将数据挖掘应用于型糖 尿病发病规律的研究，一方面可以对大批量的糖尿病数据进行处理，找出其发 病规则，另一方面也可以仅从实际的糖尿病数据中获取的实用规则。用数据挖 掘可以从众多的糖尿病数据中挖掘出致病规律，为糖尿病的预防，诊断和预测 构造决策系统。 1 2 国内外研究情况综述 随着人们认识和管理水平的提高，对客观世界的描述越来越全面，存储的 数据量越来越大。但相当数量的数据具有很强的时效性，数据的价值随着时间 的推移而迅速降低。数据收集与维护的最终目的是供人们使用。简单的数据查 询或统计虽然可以满足某些低层次的需要，但人们更为需要的是从大量数据资 源中挖掘出对各类决策有指导意义的一般知识，这些知识是对大量数据的高度 概括和抽象。 大量的数据未能充分利用这一现象常常被描述为“数据丰富，但信息贫 乏”。数据的急剧增长和时效性、复杂性远远超出了人们的手工处理能力，迫 切需要高性能的数据分析工具来高速、全面、深入、有效地处理数据。数据挖 掘技术正是为满足上述要求而产生的。 数据挖掘( d a t am i n i n g ，简称d m ) 一词是在1 9 8 9 年8 月于美国底特律市 召开的第十一届国际联合人工智能学术会议上正式形成的，常常与知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 混用。从1 9 9 5 年开始，每年主办一 次k d d 国际学术会议，将k d d 和d m 方面的研究推向了高潮，从此，“数据 挖掘”一词开始流行“1 。 在中文文献中，d m 有时还被翻译为“数据采掘”、“数据开采”、“数据发 掘”等。还有很多和这一术语相近的术语，如数据库中知识发现，数据分析， 知识抽取，模式分析，数据采集，商业智能，数据融合，决策支持等。 1 数据挖掘的知识表示数据挖掘所获得知识的表示形式主要有5 种：规 则、决策树、知识基( 浓缩数据) 、网络权值和公式幅一1 。 ( 1 ) 规则。规则由前提条件和结论两部分组成。前提条件由属性取值的合 取和析取组合而成，结论为决策属性或类别属性的取值。例如： i fa g e = 3 0a n ds t u d e n t = ”n o ”t h e nb u y _ c o m p u t e r = ”n o ” 就是一条规则。 ( 2 ) 决策树。决策树是一种类似于流程图的树结构。它采用自顶向下的递 归方式，在决策树的内部节点进行属性值的比较，并根据不同的属性值从该节 哈尔滨理1 = 大学1 = 学硕士学位论文 点向下分支，叶节点是要学习划分的类。从根节点到叶节点的一条路径就对应 着一条合取规则，整个决策树就对应着一组析取表达式规则。 ( 3 ) 知识基。数据挖掘方法能计算出数据库中属性的重要程度。通过对不 重要的属性作删除处理，并对数据库中的元组按一定的原则合并，能够压缩数 据库中元组和属性的数目，最后得到浓缩的数据，称为知识基。 2 数据挖掘系统的发展数据挖掘系统按其发展可分为四代： 第一代数据挖掘系统支持一个或少数几个数据挖掘算法，这些算法设计用 来挖掘向量数据，该系统在挖掘时，般将要挖掘的数据一次性调入内存，系 统的成功依赖于数据的质量。 第二代数据挖掘系统支持数据库和数据仓库，具有良好的可扩展性。该系 统能够挖掘大型数据集、复杂数据集和高维数据。它通过支持数据挖掘模式 ( d a t a m i n i n gs c h e m e ) 和数据挖掘查询语言( d m q l ) 增加系统的灵活性。该系统 提供了与数据库和数据仓库之间的有效接口。 第三代数据挖掘系统能够挖掘i n t e m e t e x t r a n e t 的分布式和高度异质的数 据，并能够有效地和操作型系统集成。该系统的关键技术之一是提供对建立在 异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别 ( f i r s tc l a s s ) 的支持。此外，它还提供了数据挖掘系统和预言模型系统之间的 有效接口。该系统的一个重要的优点是由数据挖掘系统产生的预言模型能够自 动地被操作系统吸收，从而与操作型系统中的预言模块相联合提供决策支持的 功能。 第四代数据挖掘系统能够挖掘嵌入式系统、移动系统和普遍存在的 ( u b i q u i t o u s ) 计算设备产生的各种类型的数据。目前，移动计算越来越显得重 要，将数据挖掘和移动计算结合是当前的一个研究热点，它也是第四代数据挖 掘系统研究的重要课题之一。 目前，第一代数据挖掘系统仍在发展中，第二代、第三代数据挖掘系统己 经出现，第四代还处于研究阶段h ，。 3 数据挖掘的应用数据挖掘的应用及其广泛。针对特定领域的应用，人 们开发了许多专用的数据挖掘工具，包括天文学、生物医学、医疗保健、d n a 分析、银行、金融、零售业和电信业等【引。 数据挖掘在天文学上有一个非常著名的应用系统：s k i c a t ( s k v i m a g e c a t a l o g i n ga n da n a l y s i st 0 0 1 ) 。它是由加州理工学院开发的用于帮助天文 学家发现遥远的星体的工具。其任务是构造星体分类器对星体进行分类。 数据挖掘在生物医学上的应用主要集中于分子生物学，尤其是基因工程的 哈尔滨理工大学工学硕士学位论文 研究。它在分子生物学上的工作可分为两种：一是从各种生物体的d n a 序列 中定位出具有某种功能的基因串；二是在基因数据库中搜索与某种具有高阶结 构或功能的蛋白质相似的高阶结构序列。 数据挖掘在市场营销中的应用可分为两类：数据库市场营销和购物篮分 析。前者的任务是通过交互查询、数据分割和模型预测等方法来选择有潜力的 顾客以便向他们推销产品。后者的任务是分析市场销售数据( 如p o s 数据库) 以识别顾客的购买行为模式，从而帮助确定商店货架的布局，促进商品的销 售。 在银行业，数据挖掘主要用于信用欺诈的建模和预测、风险评估、趋势分 析、收益分析以及辅助直销活动。在金融市场，已将神经网络用于股票价格预 测、购买权交易、债券等级评定、资产组合管理、商品价格预测、合并和买进 以及金融危机预测等方面。 4 糖尿病研究意义糖尿病( d i a b e t e sm e l l i t u s ) 是一种由遗传和环境因素相 互作用而引起的临床综合症。糖尿病主要临床类型分为胰岛素依赖型糖尿病 ( i d d m ，i 型) 和非胰岛素依赖型糖尿病( n i d d m ，i i 型) 饽1 。 非胰岛素依赖型糖尿病( n i d d m ，i i 型) 也可发生在任何年龄，但多见于4 0 岁以后中、老年。大多数病人起病缓慢，临床症状相对较轻。无酮症酸中毒倾 向，但在一定诱因作用下，也可发生酮症酸中毒或高渗性昏迷。在饮食和口服 降糖药治疗效果欠佳时，或因并发症和伴发病的存在，有时亦需要用胰岛素控 制高血糖。胰岛细胞自身抗体阳性。空腹血浆胰岛素水平可正常、轻度降低或 高于正常。胰岛素对葡萄糖刺激的反应可稍低、基本正常或高于正常，分泌高 峰延迟。 i i 型糖尿病在我国的患病率也呈上升趋势。8 0 年代初，我国糖尿病的患病 率为0 6 7 ，而1 9 9 6 年却上升到3 2 1 ，在短短1 5 年的时间里上升了近5 倍。如果考虑到4 7 6 的糖耐量减低人群，我国已有近1 亿人群笼罩在糖尿病 的威胁阴影之下。 根据大量流行病学研究结论，i i 型糖尿病是冠心病、高血压等其它慢性非 传染性疾病发病的高危因素。i i 型糖尿病的特点是起病隐匿、终身治疗、并发 症后果严重，常是人致残、致死的主要原因。这一疾病第一个特点表明其发病 为一个渐进累计的过程，其后两个特点决定了这一疾病将消耗大量的医疗资 源。由于糖尿病的高患病率与严重后果及其高额医疗费用，这一疾病已构成了 对国民健康及国民经济可持续发展严重的威胁；进入了需要有效控制其发生的 重大疾病行列；对这疾病发生的控制研究己迫在眉睫。预防为t 是疾病控制 哈尔滨理工大学工学硕上学位论文 的主要策略，它的主要优势在于在疾病发生以前保护人群免受危害，而与诊疗 研究相比，它具有明显的投入小，收益大的特点。一个老年发病糖尿病人的治 疗费用可以覆盖至少2 5 0 人的预防费用。另外由于糖尿病与其它疾病发生的密 切关系使得对它发病控制的研究更具普遍意义。可以收到从一点上入手控制， 在多点上受益的效果，提高疾病控制的投入一产出效益。根据近二十年来中 国、芬兰及美国的工作，i i 型糖尿病的发生是可以延缓、预防的。 i i 型糖尿病的隐匿起病、患病率随年龄增大而增加等特点表明这一疾病发 展为一渐进型糖尿病发病进行控制首先涉及对这一疾病的了解。了解这一疾病 发生发展的规律，针对重要途径、重点人群入手，才能达到理想效果。探讨 型糖尿病发病规律是控制其发生的重要、基础的一步。 1 3 本文工作 本文从实测数据出发，学习糖尿病的发病规则，构造糖尿病的分类和预测 系统。选取了数据挖掘算法中的c 4 5 算法进行决策学习和规则提取，对原始 数据做了细致的预处理，并在预处理过的数据上进行数据挖掘，构造分类树， 学习分类规则，并用保持方法估计其预测准确性。针对决策树对患病人群的正 确率不够理想的情况，构造了一个改进的算法模型。 本文的工作主要包括如下几个方面： 1 针对传统糖尿病研究的局限性，用数据挖掘技术来发现规律，学习i i 型糖尿病的发病规律的知识，构造糖尿病的分类和预测系统。选取分类算法来 进行数据的挖掘。由于决策树方法在分类算法中的诸多优点和糖尿病数据的连 续性，选取决策树方法中的c 4 5 算法作为数据挖掘算法，并生成易于理解的 规则。 2 用c 4 5 算法迸行发病规律的学习和规则提取。在预处理过的数据的基 础上生成了一组糖尿病的诊断与预测规则，并用分类法的保持评判方法评判其 正确率。 3 针对原始数据，结合现在的数据预处理技术，对数据进行了数据清 理、数据变换和数据归约的预处理，并进行数据处理和结果分析。它将c 4 5 算法应用于经过预处理的数据中，生成决策树和分类规则。最后针对决策树对 患病人群的正确率不够理想的情况，提出了经过改进的分类器和判定患病人群 的解决方案。 4 提出了决策树算法c 4 5 的改进模型，通过对c 4 5 算法和其改进型的分 析和比较，说明了模型的有效性。 哈尔滨理工大学工学硕士学位论文 2 1 数据挖掘系统 第2 章数据挖掘 1 数据挖掘定义数据挖掘是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取出隐含在其中的、人们事先不知道的、但又是潜 在有用的信息和知识的过程。它是在没有明确假设的前提下去挖掘信息、发现 知识n q 1 。 它建立在数据库和数据仓库的基础上，面向非专业用户，支持即兴的联机 查询。数据挖掘技术能自动分析数据，进行归纳性推理和联想，寻找数据间内 在的某些关联，发掘潜在的、对信息预测和决策行为起着十分重要作用的模 式，从而建立新的业务模型，帮助决策者制定市场策略，做出正确的决策。 数据挖掘是数据库技术、人工智能、机器学习和统计学等学科相结合的产 物。简单地说，数据挖掘是从大量数据中提取或“挖掘 知识。数据挖掘有广 义和狭义之分，广义的数据挖掘是指从数据库的大量数据中揭示出隐含的、先 前未知的、潜在有用的信息的非平凡过程，它是由g p i a t e t s k y s h a p i o r w j f r a w l e y 等人提出的。狭义的数据挖掘则把数据挖掘作为知识发现( k d d ) 的一个基本步骤。数据库中知识发现的过程如图2 1 所示，它由下列步骤组 成。 图2 - 1 知识发现过程 f i g 2 - 1k d dp r o c e s s ( 1 ) 数据清理：消除噪声或不一致数据。 ( 2 ) 数据集成：将多种数据库中的数据组合在一起。 ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据。 ( 4 ) 数据变换：将数据变换或统一成适合挖掘的形式。 ( 5 ) 数据挖掘：它是基本步骤，使用智能方法提取数据模式。 ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式。 ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 从上述步骤可以看出，数据挖掘只是整个过程中的一个步骤。然而，在大 多数场合，人们采用广义数据挖掘观点，即把数据挖掘与k d d 视为同义词。 哈尔滨理工大学工学硕士学位论文 基于广义的数据挖掘观点，典型的数据挖掘系统如图2 2 所示。 清 困l 鍪望全堡l 图2 - 2 典型的数据挖掘系统结构 f i g 2 - 2t y p i c a ls t r u c t u r e o ft h ed a t am i n i n gs y s t e m ( 8 ) 数据库、数据仓库或其它信息库：这是一个或一组数据库、数据仓 库、电子表格或其它类型的信息库，可以对其进行数据清理和集成。 ( 9 ) 数据库或数据仓库服务器：根据用户的数据挖掘请求，服务器负责提 取相关数据。 ( 1 0 ) 知识库：领域知识用于指导搜索，或评估结果模式的兴趣度。 ( 1 1 ) 数据挖掘引擎：它是数据挖掘系统的基本部分，由一组数据挖掘模块 组成，用于特征化、关联、分类、聚类分析以及演变和偏差分析。 ( 1 2 ) 模式评估模块：通常，它使用兴趣度度量，并与数据挖掘模块交互， 以便将搜索聚焦在有趣的模式上。 ( 1 3 ) 图形用户界面：此模块在用户和数据挖掘系统之间通信，允许用户与 系统交互，指定数据挖掘查询，提供提示信息，帮助搜索聚焦。此外，它允许 用户浏览数据库和数据仓库模式或数据结构，评估挖掘的模式，以不同的形式 对模式可视化。 数据挖掘从一开始就是面向应用的。它不仅仅是面向特定数据库的简单检 索查询，而且要对这些数据进行微观或宏观的统计、分析、综合和推理，以指 导实际问题的求解，甚至利用各种数据分析工具在数据中发现模式和数据| 日j 的 关系，对未来的活动进行预测。 哈尔滨理工大学工学硕士学位论文 数据挖掘得到的知识会告诉人们“怎样做 ，而不会告诉人们“为什么这 样做”，至于“为什么这样做”需要人们去思考。 需要指出的是，数据挖掘所发现的知识不要求是放之四海而皆准的真理。 它所发现的知识是相对的，有特定前提和约束条件的，面向特定领域的，同时 还要求易于被用户理解。 2 数据挖掘系统的结构根据数据挖掘系统与数据库或数据仓库的藕合程 度，可以将数据挖掘系统分为不藕合、松散藕合、半紧藕合和紧密藕合4 种结 构n 引。 不藕合是指数据挖掘系统不利用数据库或数据仓库系统的任何功能。它可 能由特定的源( 如文件系统) 提取数据，使用某些数据挖掘算法处理数据，然后 将挖掘结果存放到另一个文件中。这种系统虽然结构简单，但有不少缺点。因 此，不藕合是一种很糟糕的设计。 松散藕合是指数据挖掘系统将使用数据库或数据仓库系统中的某些工具进 行数据挖掘，然后将挖掘的结果存放到文件、数据库或数据仓库中。松散藕合 比不藕合好，然而，许多松散藕合的系统是基于内存的，挖掘本身不使用数据 库或数据仓库提供的数据结构或查询优化方法，对于海量数据集，该系统很难 获得可伸缩性和良好的性能。 半紧密藕合是指除了将数据挖掘系统连接到一个数据库或数据仓库系统之 外，一些基本数据挖掘原语还可以在数据库或数据仓库系统中实现。在该系统 中，中间挖掘结果要么预计算，要么可以有效地计算，这种设计将提高数据挖 掘系统的性能。 紧密藕合是指数据挖掘系统平滑地集成到数据库或数据仓库系统中。数据 挖掘子系统被视为信息系统的一个部分。这种结构是高度期望的，但其实现并 非易事，许多问题还有待于进一步研究。 3 数据挖掘系统分类原则上讲，数据挖掘可以在任何类型的信息存储上 进行，包括关系数据库、事务数据库、数据仓库、高级数据库系统和面向特殊 应用的数据库系统( 如：面向对象数据库、对象一关系数据库、空间数据库、 时间数据库、时间序列数据库、文本数据库、多媒体数据库、w w w 等) 。 数据挖掘是一个交叉学科领域，受多个学科的影响。因此，产生了许多不 同类型的数据挖掘系统，根据不同的标准可以分类如。 ( 1 ) 根据挖掘的数据库类型分类。由于数据库系统本身可以根据不同的标 准分类，因此，数据挖掘系统可以相应分类。如果根据数据模型分类，可以分 为关系的、事务的、面向对象的、对象一关系的或数据仓库的数据挖掘系统： 哈尔滨理1 = 大学工学硕士学位论文 如果根据所处理数据的特定类型分类，可以分为空间的、时间序列的、文本 的、多媒体的或w w w 的数据挖掘系统。 ( 2 ) 根据挖掘的知识类型分类。知识的类型包括特征化、区分、关联、分 类、聚类、孤立点分析、演变分析、偏差分析或类似性分析等。一个完整的数 据挖掘系统应当提供多种和集成的数据挖掘功能。 此外，数据挖掘系统可以根据所挖掘的知识的粒度或抽象层来进行分类。 包括概化知识( 在高抽象层) 、原始层知识( 在原始数据层) 或多层知识，一个高 级的数据挖掘系统应当支持多层的知识发现。 ( 3 1 ) 根据所用的技术分类。这些技术可以根据用户交互程度( 例如自动系 统、交互查询系统、查询驱动系统) ，或所用的数据分析方法( 例如面向数据库 或数据仓库的技术、机器学习、统计学、可视化、模式识别、神经网络、模糊 集、粗糙集、遗传算法、决策树、最近邻技术等) 描述。复杂的数据挖掘系统 通常采用多种数据挖掘技术。 ( 4 ) 根据应用分类。不同的应用通常需要集成对于该应用特别有效的方 法。比如，金融、电信、d n a 、股票市场等等。通用的数据挖掘系统可能并不 适合特定领域的挖掘任务。 2 2 数据挖掘过程 数据挖掘的整个过程可粗略地分为：问题定义( t a s kd e f i n i t i o n ) 、数据准备 和预处理( d a t ap r e p a r a t i o na n dp r e p r o c e s s i n g ) 、数据挖掘( d a t am i n i n g ) ，以及 结果的解释和评估( 1 1 1 t e r p r e t a t i o na n de v a l u a t i o n ) n 3 “1 如图2 - 3 所示。 选 预 转挖分 择 处 被选理 预处换掘析 转换被抽 原始 l 择的 l理后l 后的取的 分析 数据 的数结果 数据数据数据 据 1 问题定义数据准备和预处理 1 _r 1r 数据挖掘评估与分析 图2 - 3 数据挖掘过程 f i g 2 3d a t am i n i n gp r o c e s s 1 问题定义数据挖掘是为了在大量数据中发现有用的令人感兴趣的信 息，因此发现何种知识就成为整个过程中第一个也是最重要的一个阶段。在问 题定义过程中，数据挖掘人员必须和领域专家以及最终用户紧密协作，一方面 明确实际工作对数据挖掘的要求：另一方面通过对各种学习算法的对比进而确 定可用的学习算法。后续的学习算法选择和数据集准备都是在此基础上进行 的。 2 数据收集和预处理数据准备又可分为三个子步骤：数据选取( d a t a s e l e c t i o n ) 、数据预处理( d a t a p r e p r o c e s s i n g ) 和数据变换( d a t a t r a n s f o r m a t i o n ) 。 数据选取的目的是确定发现任务的操作对象，即目标数据( t a r g e td a t a ) ， 是根据用户的需要从原始数据库中抽取的一组数据。数据预处理一般可能包括 消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换( 如把连续 值数据转换为离散型的数据，以便于符号归纳，或是把离散型的转换为连续值 型的，以便于神经网络) 等。当数据挖掘的对象是数据仓库时，一般来说，数 据预处理已经在生成数据仓库时完成了。数据变换的主要目的是消减数据维数 或降维( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中找出真正有用的特征以减少数 据挖掘时要考虑的特征或变量个数。 3 数据挖掘数据挖掘阶段首先根据对问题的定义明确挖掘的任务或目 的，如分类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就 要决定使用什么样的算法。选择实现算法有两个考虑因素：一是不同的数据有 不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的 要求，有的用户可能希望获取描述型的( d e s c r i p t i v e ) 、容易理解的知识( 采用规 则表示的挖掘方法显然要好于神经网络之类的方法) ，而有的用户只是希望获 取预测准确度尽可能高的预测型( p r e d i c t i v e ) 知识，并不在意获取的知识是否易 于理解。关于数据挖掘所采用的一些常用算法，在下面章节将给出详细的描 述。 4 评估与表示模式评估根据某种兴趣度度量，识别表示知识的真正有趣 的模式。知识表示阶段使用可视化和知识表示技术，向用户提供挖掘的知识。 数据挖掘阶段发现出来的模式，经过评估，可能存在冗余或无关的模式，这时 需要将其剔除；也有可能模式不满足用户要求，这时则需要整个发现过程回退 到前续阶段，如重新选取数据、采用新的数据变换方法、设定新的参数值，甚 至换一种算法等等。另外，数据挖掘由于最终是面向人类用户的，因此可能要 对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示，如把分 哈尔滨理下大学工学硕士学位论文 类决策树转换为“i f t h e n ”规则。 数据挖掘仅仅是整个过程中的一个步骤。数据挖掘质量的好坏有两个影响 要素：一是所采用的数据挖掘技术的有效性，二是用于挖掘的数据的质量和数 量( 数据量的大小) 。如果选择了错误的数据或不适当的属性，或对数据进行了 不适当的转换，则挖掘的结果不会好的。 整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘途中发现选择的 数据不太好，或使用的挖掘技术产生不了期望的结果；这时，用户需要重复先 前的过程，甚至从头重新开始。 可视化在数据挖掘的各个阶段都扮演着重要的作用。特别是，在数据准备 阶段，用户可能要使用散点图、直方图等统计可视化技术来显示有关数据，以 期对数据有一个初步的了解，从而为更好地选取数据打下基础。在挖掘阶段， 用户则要使用与领域问题有关的可视化工具。在表示结果阶段，则可能要用到 可视化技术以使得发现的知识更易于理解。 2 3 数据挖掘的主要方法和技术 数据挖掘技术包括三个主要部分：算法和技术、数据、建模能力。下面分 别从进行数据挖掘和知识发现的各个不同的角度来介绍数据挖掘的主要方法和 技术n 5 1 6 1 。 1 决策树利用信息论中的信息增益寻找数据库中具有最大信息量的字 段，建立决策树的一个节点，再根据字段的不同取值建立树的分支；在每个分 支子集中重复建立树的下层节点和分支的过程，即可建立起决策树。国际上最 有影响和最早的决策树算法有b a y e s 和q u i u l a n 的i d 3 算法，它对越大的数据 库效果越好n 7 墙1 。 在1 d 3 算法的基础上，后来又发展了多种决策树算法，c 4 5 算法就是其中 的一个。c 4 5 算法也是构造决策树分类器的算法，它是i d 3 算法的扩展。i d 3 算法只能处理离散型的描述性属性，而c 4 5 算法还能够处理描述性属性是连 续型的情况。这种算法利用比较各个描述性属性的g a i n 值的大小，来选择 g a i n 值最大的属性进行分类。如果存在连续型的描述性属性，那么首先要做的 是把这些连续型属性的值分成不同的区间，即“离散化 。 决策树方法的最大优点是直观。其缺点是随着数据复杂性的提高，分支数 将增加，管理的难度越来越大。此外，该方法也存在数据的缺值处理问题。 2 统计方法统计方法是从事物外在数量上的表现去推断该事物可能的规 律性”。通常是先通过统计从其数量表现 = 分析出一些线索，然后提出一定的 哈尔滨理工大学工学硕十学位论文 假说或学说，再作进一步深入的理论研究。当理论研究得出一些结论时，往往 还需要在实践中加以验证。统计方法的优点是精确、易理解，并且已广泛使 用。其缺点是很难有效使用。 统计方法主要考虑预想的假设是否与数据模型拟合。它依赖于显式的基本 概率模型。统计方法处理过程可以分为三个阶段：搜集数据阶段、分析数据阶 段和进行推理阶段。 常见的统计方法有回归分析( 多元回归、自回归等) 、判别分析( 贝叶斯判 别、费歇尔判别、非参数判别等) 、聚类分析( 系统聚类、动态聚类) 以及探索 性分析( 主元分析法、相关分析法等) 。目前流行的统计软件有s a s ( s t a t i s t i c s a n a l y s i ss y s t e m ) 和s p s s ( s t a t i s t i c a lp a c k a g ef o r t h es o c i a ls c i e n c e ) 等，其中美 国的s a s 软件以其强大的数据管理能力、全面的统计方法、高精度的计算和 独特的多平台自适应技术被国内外许多学者誉为最权威的统计软件包。 3 粗糙集算法在数据库中，将行元素看成对象，列元素是属性( 分为条 件属性和决策属性) 。等价关系r 定义为不同对象在某个( 或几个) 属性上取值 相同，这些满足条件关系的对象组成的集合称为该等价关系r 的等价类。条件 属性上的等价类e 与决策属性上的等价类y 之间有三种情况： ( 1 ) 下近似：y 包含e ； ( 2 ) 上