（计算机软件与理论专业论文）决策树id3算法的改进研究.pdf

哈尔滨工程大学硕士学位论文 摘要 数据挖掘是通过仔细分析大量数据来揭示有意义的新的关系、趋势和模 式的过程，是信息处理技术研究领域的一项重要课题。它是指从大型数据库 或数据仓库中提取隐含的、未知的、非平凡的以及有潜在应用价值的信息或 模式的过程。它融合了数据库、人工智能、机器学习等多个领域的理论和技 术。分类分析是数据挖掘技术研究的一个重要方向。数据挖掘中分类算法在 商业应用最为广泛，而决策树算法又是数据挖掘分类的核心技术算法之一。 q u i n l a n 于1 9 8 6 年提出的i d 3 算法在决策树算法中最为著名。本文主要研究 决策树i d 3 算法及其改进算法。 本文首先详细地介绍了i d 3 算法，然后对其进行了深入地研究。i d 3 算 法有两大缺点：第一，i d 3 算法由于使用l o g 进行计算，所以运算起来并不简 单；第二，算法往往偏向于选择取值较多的属性，而取值较多的属性却不总 是最优的属性。其次，为了解决i d 3 算法运算复杂的缺点，引入麦克劳林公 式，在i d 3 算法的基础上提出了i d 3 简化算法，使运算变得简洁；为解决i d 3 算法偏向于选择取值较多的属性的不足，通过使用数据结构中的二叉树来存 储决策树，在i d 3 算法基础上提出了将i d 3 简化算法与普通二叉树算法相结 合的i d 3 简化算法的二叉树存储算法。然后通过使用同- - n 练集的实例进行 具体计算，分别得到其对应的决策树。 最后对不同算法建立的决策树进行比较研究，得到结论：通过对i d 3 算 法、i d 3 简化算法和i d 3 简化算法的二叉树存储算法三种决策树算法的比较， 证明应用i d 3 简化算法的二叉树存储算法比i d 3 算法和i d 3 简化算法得到的 决策树更为理想。 关键词：决策树；i d 3 算法；1 1 ) 3 简化算法；二叉树存储算法 哈尔滨工程大学硕士学俄论文 a b s tr a c t d a t am i n i n gi sap r o c e s sw h i c hr e v e a l sn e wr e l a t i o n s h i p s ，t r e n d sa n dp a t t e r n s t h r o u g hc a r e f u la n a l y s i so fs u b s t a n t i a ld a t a i ti sa ni m p o r t a n tt o p i co fi n f o r m a t i o n t e c h n o l o g yr e s e a r c hf i e l d d a t am i n i n gi sap r o c e s sw h i c he x t r a c t si m p l i c i t , u n k n o w n ，n o n - t r i v i a la n dp o t e n t i a li n f o r m a t i o no rp a t t e r nf r o mal a r g ed a t a b a s eo r d a t aw a r e h o u s e 。i tc o m b i n e s 诚t l lt h e o r ya n dt e c h n o l o g yo fd a t a b a s e , a r t i f i c i a l i n t e l l i g e n c e ，m a c h i n el e a r n i n ga n do t h e rf i e l d s c l a s s i f i c a t i o na n a l y s i so fd a t a m i n i n gt e c h n o l o g yi sa l li m p o r t a n td i r e c t i o no fr e s e a r c h 。c l a s s i f i c a t i o na l g o r i t h m o fd a t am i n i n gi sm o s tw i d e l yu s e di nc o m m e r c i a l ，w h i l ed e c i s i o nt r e ea l g o r i t h m i sac o r et e c h n o l o g yo fc l a s s i f i c a t i o na l g o r i t h m 。i nd e c i s i o nt r e ea l g o r i t h m ，t h e f a m o u so n ei si d 3a l g o r i t h mw h i c hw a sp r e s e n t e db yq u i n l a ni n19 8 6 t h e i m p o r t a n c eo ft h i sp a p e ri s t os t u d y1 1 ) 3 a l g o r i t h mo fd e c i s i o nt r e ea n di t s i m p r o v e m e n t 。 f i r s to fa l l ，t h ep a p e ri n t r o d u c e di d 3a l g o r i t h m t h e n ，f u r t h e rr e s e a r c ho n i d 3a l g o r i t h mi sd o n e i d 3a l g o r i t h mh a st w om a j o rd r a w b a c k s ：o n ei st h a tu s i n g l o gi sn o te a s yt oc a l c u l a t e t h eo t h e r ：a l g o r i t h ms e l e c t i o ni so f t e nb i a s e di nf a v o r o ft h em o r ep r o p e r t yv a l u e s ，b u tp r o p e r t yv a l u e so fm o r ep r o p e r t ya r en o ta l w a y s o p t i m a l i no r d e rt os o l v et h ep r o b l e mo fc o m p l e xc o m p u t i n g ，t h ep a p e ru s e s m a c l a u r i nf o r m u l a 。i d 3s i m p l i f i e da l g o r i t h mi sp r o p o s e db a s e do ni d 3a l g o r i t h m i nt h ep a p e r , s ot h a tt h ec o m p u t i n gb e c o m e se a s y f o rs o l v i n gt h eo t h e rp r o b l e m ， b i n a r yt r e es t o r a g eo fi d 3s i m p l i f i e da l g o r i t h mi sp u tf o r w a r db a s e do ni d 3 a l g o r i t h mi nt h ep a p e rb yu s i n gb i n a r yt r e eo fd a t as t r u c t u r e t h e n ，像e 蠢d e c i s i o n t r e e se m e r g e dt h r o u g ht h ec a l c u l a t i o no ft h es a m ee x a m p l e sw h i c hu s et h es a m e t r a i n i n gs e t f i n a l l y , t h ep a p e rd o e sac o m p a r a t i v es t u d yo ft h ed e c i s i o nt r e e so fd i f f e r e n t a l g o r i t h m si no r d e r t os u mu pt h ec o n c l u s i o n s ：b i n a r yt r e e s t o r a g eo fi d 3 s i m p l i f i e da l g o r i t h mi sp r o v e dm o r ee f f i c i e n tt h r o u g hc o m p a r i n gi d 3a l g o r i t h m w i t hi d 3s i m p l i f i e da l g o r i t h ma n db i n a r yt r e es t o r a g eo fl d 3s i m p l i f i e da l g o r i t h m 哈尔滨丁程大学硕士学位论文 k e yw o r d s ：d e c i s i o nt r e e ；i d 3a l g o r i t h m ；i d 3s i m p l i f i e da l g o r i t h m ；b i n a r yt r e e s t o r a g ea l g o r i t h m 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ： 主l 聿嚷 日期：i 年月厂3 日 | 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 ， 作者( 签字) ： 麦1 名袭导师( 签字) ：尹1 乙布钇侈 日期：乙确年月化日乙邴年月，? 日 | 。 。 哈尔滨丁程大学硕士学位论文 第1 章绪论 随着计算机科学与技术的发展，越来越多的人们开始使用计算机，大量 的信息给人们带来方便的露时，也给人们带来了许多新豹闯题。匿际互联霹 的高速发展和电子商务的广泛应用，使人们利用信息技术生产数据的能力大 幅度提高，成千上万的数据库被用于商业管理、政府办公、科学研究和工程 开发等等。 1 1 研究背景和意义 企业、政府部门和科学鞠体由于需要大量的信息和数据，因此产生了信 息积累这一问题，每天都有大量的数据产生，信息量凡乎以每二十个月翻一 番的速度剧增。如何从大量的数据中提取并发现有用信息以提供决策的依据， 数据挖掘这一新型的数据分析技术诞生了。数据挖掘就是然大量的、不完全 的、有噪声的数据中，提取新颖的、有效的和潜在有用的信息过程。数据挖 掘的任务是扶数据集中发现模式。 另一方面，由于数据库技术的发展和数据存储成本的降低以及数据库管 理系统的广泛应用，大型数据库系统已经在各行各业普及。数据库和联机事 务处理( o l 卯) 已经被广泛应用于金融、证券、保险、销售以及天气预报、工 业生产、分子生物学、基因王程研究、税务、海关等各行名业。对于这些积 累的大量数据，人们己经不满足于传统的统计分析手段，而需要发现更深层 次的规律，提供更高层次的数据分析功能，更加方便和有效的获取能带来效 益的信息。在大量的数据背羼隐藏着谗多重要的不被人所知的倍息，这些信 息可以很好地辅助人们进行决策。可是目前用于对这些数据进行分析处理的 王具却很少。大量的数据使得数据挖掘成为选案的必要技术手段，数据挖掘 技术也就应运而生。现在，数据挖掘已经作为一种从数据中发现隐含有用信 息或知识的技术，伴随着数据仓库应用的增加也得到了进一步发展。 数据挖掘是在没有明确假设的前提下去挖掘信息，发现知识，得到的是 预先未曾预料到的、有效的和实用的信息，因此它可以有效的解决当前“数 据太多，信息不足”这一困扰分析决策人员的难题。另外，通过数据挖掘， 1 哈尔滨工程大学硕士学位论文 可以处理高维的数据，为用户提供可视化工具，帮助用户发现隐藏在高维空 间的模式。对数据进行可视化的一种有效方法是借助于数据挖掘方法实现。 1 2 数据挖掘及决策树研究现状与发展趋势 1 2 1 国内外研究现状 1 改进的c 4 5 算法在天然气输差分析中的应用 随着采集输井站和用户的不断增多，以及天然气管网的不断延伸、扩张， 天然气采输配管网系统内部的采输差越来越难以控制。由于目前输差监控网 络不能完全有效地监控输差，当每日采气量与输气量出现较大差异时，往往 不能及时判断哪一条管线或与哪一个用户之间出现了采输差，这不仅造成了 计量人员工作上的被动，还使分公司蒙受了很大的经济损失。因此，一旦管 网输差出现后，很难分析判断问题出在哪里，在解决输差的问题上盲目且受 主观因素的影响。数据挖掘提供了进行输差分析的环境，数据挖掘的多种方 法可用来进行输差分析。通过使用决策树分类器方法，在天然气公司建立的 生产数据库和销售数据库以及计量数据库的基础上寻找影响输差较大的因 素，从而得出一些实用的控制输差的规则，以便对天然气公司的工作起到指 导作用。 将数据挖掘技术应用于天然气数据中的一种模式，运用改进的决策树 c 4 5 算法分析了一些参数对输差造成的影响。决策树分类器方法为输差分析 提供了有力的决策支持，数据挖掘这一技术领域必将在我国得到广泛的应用。 2 基于改进的决策树c a r t 选择拼接单元的英语语音合成 基于决策树的改进c a r t 算法。该算法由树生长和树剪枝两部分构成， 具有辨识相关输入的能力，由于引入了递归最小二乘估计器，对线性模型可 降低计算量，并采用模糊技术处理不连续边界问题。 为了有效地进行语音拼接单元的选择，同时又不影响实时性，在英语t t s 系统的开发中，引入了决策树c a r t ( c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e ) 对大语 料库进行语音单元的预选，得到反映上下文环境与韵律信息之间映射关系的 一系列决策树。在语音合成时，用c a r t 根据目标单元的上下文环境在对应 决策树中找到数量较少的、韵律特征比较合适的候选单元，通过计算目标代 2 嗡尔滨工程大学硕士学位论文 价和连接代价，得到一个全局最优的语音单元序列。实验表明，利用这种方 法进行语音合成能得到清晰、自然的合成效果，同时提高了单元选择的效率。 基于决策树c a r t 的英语t t s 系统的构成本系统所采用的语音库包括6 万多 单词、9 万多音节、2 5 万多p h o n e 的语音。语音利用h t k 进行自动切分，并 人_ i 校正籍整理为句子、单谲、音节、p h o n 0 4 级互联的语料痒。 3 c h a i d 算法在手机市场细分中的应用 c h a l d 分析方法的核心思想是：根据给定的结果变量和经筛选的特征指 标对样本进行最优分割，按照卡方检验的显著性进行多元列联表的自动判断 分组。 首先选定分类的目标变量( 结果变量) ，然后用分类变量与结采变量进行 交叉分类，产生一系列二维分类表，分别计算二维分类表的值x 2 ，比较p 值 的大小，以p 值最小的二维表 # 为最佳初始分类表，在最佳二维分类的基础 上继续使用分类变量对结果变量进行分类，重复上述过程直到p 值大于显著 性水平疆值为止。通过对众多分类检验结果加以比较并找到最佳分类变薰和 最佳分类结果，并按照最优分类线索找到的最佳结果，成为继续进行最优分 类的依据。在分类过程中，随着分类维数的增加，对样本特征的描述越来越 准确，同时，样本对目标的反映也越来越突出。 随着我国手机市场竞争的发展，客户选择手机产品及款式的余地越来越 大，各企业之间对客户的争夺也越来越激烈。面对吕益激烈的市场竞争环境， 不同企业传统的营销服务体系已无法满足客户需要，同时传统的技术等优势 难以在手机市场拉殍差距，无法形成差异化的竞争优势。因此，为了在新豹 市场形势下培育和创造出新的差异化竞争优势，各企业应以客户为中心，深 入了解客户，引导客户，根据消费者的不同特征，尽量通过手机强大的功能， 个性化设计和服务来赢得市场，使得公司的产品能够覆盖高中低端各个档次， 提高产品的市场占有率，以获得更高的市场份额。为此，企业必须从消费者 的特征、手机的功能、购买的价格等方面来剖析手机市场，细分手机市场。 市场细分作为企业战略营销的平台，企业的各项营销战略，都必须建立 在市场缨分的基础上。决策檐技术可以帮助市场分析人员细分市场，c h a i d 则是决策树技术中原理便于理解，操作性强的种算法，它将在今后的现实 研究中得到更广泛的瘟用。 3 哈尔滨下程大学硕士学位论文 4 基予k p c a 的决策树方法在客户流失分析中的应用 基于k p c a 的决策树方法决策树是数据挖掘中研究最为广泛的一种方 法。决策信息系统涉及的属 生往往很多，属性间又往往有相关性，这就给数 据处理带来很大困难。因此需要在尽可能少丢失信息的前提下降低信息系统 的维数。p c a 能够把多个属性化为少数几个互相独立的主成分，最终达蓟数 据约简，消除数据相关性的目的。如果数据间存在明显的非线性成分，还可 以弓| 入核函数进行处理。 在实际应用中许多决策树构造过于庞大，不利于人们理解，修剪时往往 代价很大。通过对k p c a 的研究，提取用核方法锝到的主成分来构造决策树， 降低了决策信息系统的维数。通过保险客户流失分析的实验，表明了该方法 是可行的和有效的，大大降低了决策树的复杂度和提高了分类精度，且在分 类精度、方差贡献率等方面优子基于p c a 的决策树。 5 i b l e 决策树算法在牙病案例诊断中的应用 i b l e 是基于信息论酶示铡学习方法，尽管在数据挖掘孛i d 3 算法占有j 暑 常重要的位置。但是，在应用中i d 3 算法存在不能够处理连续属性、计算信息 增益时偏向于选取取值较多的属性等不是。隽此，一种改进型决策树算法 i b l e 被提出，它主要是利用信息论中信道容量的概念作为对实体中选择重要 特征的度量。用多个特征组合成规则的结点来判别实例，能够更有效地正确 判别。将此算法应用于口腔疾病的诊断中，具有缀强的识别能力，对牙病案例 的诊断起到很好的辅助诊断作用。 牙病的检测与诊断一直是爨腔医学的一个重要的内容。多年来，对予西 腔疾病的检查与诊断一直是由医生凭经验并结合各种检测手段来进行的。但 由予牙瘸种类繁多，尤其有些牙病之间的差异纲微，因此很容易造成误诊。 因此基于数据仓库技术与数据挖掘技术的计算机辅助诊断在近年内形成了研 究热潮。应用数据挖掘技术中的i b l e 决策树算法应用于牙病案例的医疗诊 断中，取得了较好的效果，降低了误诊率。 目前，世界上比较有影响的典型数据挖掘系统有：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 l 公司的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 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 5 、 还宥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 、 4 哈尔滨1 = 程大学硕十学位论文 q u e s t 等。 与国外相比，国内对d m k d 的研究稍晚，没有形成整体力量。1 9 9 3 年 国家自然科学基金首次支持对该领域的研究项目。目前，国内的许多科研单 位和高等院校竞相开展知识发现的基础理论及其应用研究，这些单位包括清 华大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。 其中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的 研究，北京大学也在开展对数据立方体代数的研究，华中理工大学、复旦大 学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展了 对关联规则开采算法的优化和改造；南京大学、四川联合大学和上海交通大 学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘。 1 2 2 发展趋势 经过十几年的发展，对数据挖掘的研究已经从最初表面的、孤立的问题 向系统的、全面的方向发展。以决策树作为数据挖掘技术在各种领域的应用 仍将是人们研究的热点，因为对数据挖掘的研究目前主要集中在数据挖掘技 术和算法的研究、数据挖掘的理论研究以及数据挖掘的应用研究三个方面。 当前，数据挖掘知识发现的研究方兴未艾，数据挖掘研究人员、系统合 应用开发人员所面临的主要问题是高效而有效的数据挖掘方法和系统的开 发，交互和集成的数据挖掘环境的建立，以及如何应用挖掘技术解决大型应 用问题。研究的焦点可能会聚集在以下几方面： 数据挖掘语言的形式化描述：即研究专门用于知识发现的数据挖掘语言， 也许会像s q l 语言一样走向形式化和标准化。 可视化数据挖掘：是从大量数据中发现知识的有效途径，它使数据挖掘 的过程能够被用户理解，也便于在数据挖掘过程中进行人机交互，该技术将 有助于推进数据挖掘作为数据分析的基本工具。 多媒体数据挖掘：是指从大量的文本数据、图形数据、视频图像数据、 音频数据乃至综合多媒体数据的开采中，通过分析语义和视听特征，发现其 中隐含的、有价值的模式。它和传统的数据挖掘方法中处理的数据不同，传 统的数据挖掘处理的数据是数据库中表格形式中的记录和条目，属于结构型 哈尔滨工程大学硕士学位论文 数据，而多媒体数据挖掘处理的是非结构化的数据。 w e b 数据挖掘：主要是利用数据挖掘技术从w e b 文档及w e b 服务器中自 动发现并提取有用信息的过程。w e b 上有海量数据，这些数据最大特点是半 结构化。那么开发新的w e b 挖掘技术以及对w e b 文档进行预测处理以得到 关于文档的特征表示，就成为w e b 挖掘的重点。 数据挖掘中的隐私与信息安全：随着数据挖掘工具和电信与计算机网络 的日益普及，数据挖掘要面对的一个重要问题就是隐私保护和信息安全。需 要进一步开发有关方法，以便在适当的信息访问和挖掘中确保隐私保护与安 全。 现在，许多企业都把数据看成宝贵的财富，纷纷利用商务智能发现其中 隐藏的信息，借此获得巨额的回报。国内数据挖掘的在各个行业都有一定的 研究，据国外专家预测，在今后，随着数据量的日益积累以及计算机的广泛 应用，数据挖掘将在中国形成一个产业。 1 3 论文的研究内容 本文采用数据挖掘中的决策树技术，通过对决策树i d 3 算法进行改进并 将其应用到实际生活中，把收集到的大量数据信息转换成知识，进而利用这 些知识更好地辅助人们进行决策即是本文的研究目的。正文的研究内容如下： 第l 章，绪论。首先阐述了本课题的研究背景、意义，其次研究了国内 外研究动态，最后介绍了论文的研究结构。 第2 章，介绍了数据挖掘与决策树的相关知识。首先介绍数据挖掘相关 理论。分别从以下角度进行研究：从研究数据挖掘体系结构开始，其次研究 了数据挖掘的步骤；接着，介绍了几种常用数据挖掘算法，这其中包括分类 算法、聚类算法等。第二节对决策树算法进行了研究，主要研究了常用的决 策树分类算法；并对数据分类中的决策树算法进行了研究。最后介绍了高数 中的麦克劳林公式，这也是本文研究i d 3 算法改进所需的公式。 第3 章，以决策树算法中的i d 3 算法为中心展开研究。首先介绍信息论 相关概念，包括熵，信息熵，条件熵；其次具体研究了i d 3 算法，详细介绍 了i d 3 算法，并举例对i d 3 算法进行说明。然后是本章的重点：研究i d 3 算 6 哈尔滨工程大学硕士学能论文 法存在的问题及改进方案。通过分析i d 3 算法的优缺点，找到其不足之处， 经过研究思考，找到有效解决方案，并对方案进行整理，最终提出对i d 3 算 法的改进方案。 第4 章，对i d 3 算法的改进研究。本章包括i d 3 简化算法，i d 3 简化算 法的二叉树存储算法以及算法的比较研究三部分内容。善先是对原i d 3 算法 的改进，通过应用近似公式改进i d 3 算法，使运算变得更加简单。然后继续 对改进的i d 3 简化算法进行研究，通过应用数据结构中的二叉树来改进i d 3 算法，生成的决策树最终以二叉树的形式出现，从而避免了i d 3 算法偏向取 值较多属性的缺点。最后，对原算法和改进后的算法进行了比较研究。 第5 章，实验测试结果分析。通过分析测试结果，对几种算法进行比较， 证明其正确性及优化性，最终得出结论。 7 哈尔滨工程大学硕十学位论文 i 第2 章数据挖掘与决策树相关知识 数据挖掘【l 】是通过仔细分析大量数据来揭示有意义的新的关系、趋势和 模式的过程。其出现于2 0 世纪8 0 年代后期，是数据库研究中一个很有应用 价值的新领域，它是- - f - j 交叉性学科，融合了人工智能、数据库技术、模式 识别、机器学习、统计学和数据可视化等多个领域的理论和技术。数据挖掘 作为一种技术，它的生命周期正处于沟坎阶段，需要时间和精力去研究、开 发和逐步成熟，并最终为人们所接受。 2 1 数据挖掘相关理论 数据挖掘( d a t am i n i n g ) 就是从大量数据中发现潜在规律、提取有用知识 的方法和技术。因为与数据库密切相关，又称为数据库知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e s ，k d d ) 。数据挖掘不但能够学习已有的知识，而且能 够发现未知的知识；得到的知识是“显式 的，既能为人所理解，又便于存 储和应用，因此一出现就得到各个领域的重视。 通常数据挖掘被视作以提取有用信息为目的的“数据簇聚 或“数据产 生 的过程，数据为信息处理者提取新的和有用规则服务，并能够根据己有 的信息对实际未发生行为的结果做出预测。数据挖掘从大量数据中挖掘出隐 含的、先前未知的、对决策有潜在价值的知识和规则。这些规则蕴涵了数据 库中一组对象之间的特定联系，揭示出一些有用的信息，为经营决策、市场 策划、工业控制、领导决策提供依据，通过数据挖掘，有价值的知识、规则 或高层次的信息就能从数据库的相关数据集合中抽取出来，并从不同角度来 显示，从而使大型数据库作为一个丰富可靠的资源为知识归纳服务。与传统 信息处理方法相比，数据挖掘技术有其自身的特点： ( 1 ) 处理对象为大规模数据库，数据规模十分巨大，待处理的数据规模 可能达到g b 、t b ，甚至更大； ( 2 ) 信息查询一般是由决策制定者( 用户) 提出的即时随机查询，往往 没有精确的查询要求，需要靠数据挖掘技术寻找其可能感兴趣的东西； 哈尔滨工程大学硕士学位论文 ( 3 ) 在一些应用中，某些行动并没有实际发生或很少发生，因而他们对 输出所造成的影响没有在数据库中体现出来，需要剥用数据挖掘技术从数据 库中提取有用的规则，为这种情况提出预测； 2 董。l 数据挖掘体系结构 数据挖掘系统共分为三层结构，如图2 1 所示。第一层是数据源层，包 括数据库、数据仓库及其他信息存储瘁。第二层是数据挖掘层，利用数据挖 掘算法分析数据库中的数据。第三层是用户界面层，将获取的信息以便于用 户理解的方式展现给震户。 1 数据源层 数据源层直接负责数据的加工、存储、提取等管理工作。数据挖掘的数 据主要有两个来源，一是未经处理的数据源数据，如各种联机事务处理系统 豹数据，这些数据被用于挖掘煎，要进行质量增强处理。二是数据库中的数 据，这类数据可经过格式转换等简单处理，处理后可应用于数据挖掘。 2 数据挖掘层 数据挖掘层进行实际的挖掘操俸，利用各种挖掘技米，从预处理完的数 据中发现模式、规则。 3 。用力羿垂屡 用户界面层完成用户与系统之间的交互作用。所有用户操作如控制数据 挖掘过程、数据库和知识库的管理都在这个层次通过用户应用接豳与系统进 行通讯。用户界面完成用户在挖掘过程中数据的选择与审查、挖掘工具的选 择与分配、知识库的运用等各种操作的对话。界匿应直观、容易理解和操作， 同时应各种工具特点建立有特色的知识表达方式。数据挖掘需要用户大量的 介入，用户往往提出一些具体的要求，通常这个要求限定了数据的来源、应 用的范围、结果的形式、评判的标准，甚至雹括应该使用什么样的算法。由 于用户提出的问题是千差万别的，所以相对应的结果模式就存在着很大不同。 9 哈尔滨t 程大学硕士学位论文 图2 1 数据挖掘系统 2 1 2 数据挖掘步骤 数据挖掘步骤如图2 2 所示： 图2 2 数据挖掘步骤 1 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。 1 0 哈尔滨工程大学硕十学位论文 暑i i i i i i i i ll te宣i i i i i i i 暑i i i i i 葺i i i i i 宣i i 青 挖掘的最后结果是不可预测的，但要探索的问题应是有预见的，为了数据挖 掘而数据挖掘则带有盲目性，是不会成功的。 2 数据准备 ( 1 ) 数据的选择 搜索所有与业务对象有关的内部和外部的数据信息，并从中选择出适用 于数据挖掘应用的数据。 ( 2 ) 数据的预处理 研究数据的质量，为进一步的分析做准备，并确定将要进行的挖掘操作 的类型。 ( 3 ) 数据的转换 将数据转换成一个分析模型。这个分析模型是针对挖掘算法建立的。 3 数据挖掘 对所得到的经过转换的数据进行挖掘，除了完善并选择合适的挖掘算法 外，其余一切工作都能自动地完成。 4 结果分析 解释并评估结果。其使用的分析方法一般应作数据挖掘操作而定，通常 会用到可视化技术。 5 知识同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 2 1 3 数据挖掘算法 1 分类算法 分类在数据挖掘中是一项非常重要的任务，目前在商业中应用最多。分 类的目的是学会一个分类函数或分类模型( 分类器) 。该模型能把数据库中的 数据映射到给定类别中的某一个。分类和回归都可用于预测。预测的目的是 从利用历史数据记录中自动推导出给定数据的推广描述，从而能对未来数据 进行预测。 要构造分类器，需要有一个训练样本数据集作为输入。训练样本数据集 亦称训练集( t r a i n i n gs e 0 ，是一条条数据记录( r e c o r d ) 组成的。每一条记录包 哈尔滨丁程大学硕士学能论文 j i i i i i hihii 含若干条属性( a t t r i b u t e ) ，组成一个特征向量。训练集的每条记录还有一个特 定的类标签( c l a s s 1 a b e l ) 与之对应，该类标签是系统的输入，通常是以往的 些经验数据。一个具体样本的形式可以为样本向量：f 嚣，瑶咒；c 。这里k 表 示字段符，c 表示类标签属憔的值。分类的目的是：分析输入数据，通过在 训练集中的数据体现窭来的特性，为每个类找到一种准确的撼述或模型。 这种描述常常用谓词表示。由此生成的类描述用来对未来的测试数据进行分 类。尽管这些未来的测试数据豹类标签是未知鹃，仍可以由此预测这些新数 据所属的类。我们也可以由此对数据中的每一个类有更好的理解。 2 聚类算法 聚类【z 】通过把爵标数据放入少数相对同源的组或“类( c l u s t e r ) 里。分 析表达数据，( 1 ) 通过一系列的检测将待测的一组基因的变异标准化，然后 成对毙较线性协方差。( 2 ) 通过把震最紧密关联的谱来放基因进行样本聚类， 例如用简单的层级聚类( h i e r a r c h i c a lc l u s t e r i n g ) 方法。这种聚类亦可扩展到 每个实验样本，利爝一组基因总的线性相关进行聚类。( 3 ) 多维等级分析 ( m u l t i d i m e n s i o n a ls c a l i n ga n a l y s i s m d s ) 是一种在二维e u c l i d e a n “距离中 显示实验样本相关的大约程度。( 4 ) k - m e a n s 方法聚类，通过重复再分配类 成员来使“类 内分散度最小化的方法。 聚类用于从数据集中找出相似的数据并分成不同的组。与分类分析不同， 聚类分析输入的是一组未分类记录，并且这些记录应分成几类事先也不知道。 聚类分析就是通过分析数据库中的记录数据，根据一定的分类规则，合理地 划分记录集合，确定每个记录所在类别。它所采用豹分类规则是由聚类分析 工具决定的。聚类分析是把一组物理对象或抽象对象( 未分类的记录) 按相似 性归为若干类别，也称为“无指导分类 ，其目的是使同一类别中的对象闻的 距离尽可能小，而不同类别中对象间的距离尽可能大。对于一个很大的多维 数据集，在数据空间中数据点通常不会均匀分布，数据聚类方法可以找出稀 疏和稠密的位置，进而发现数据集的整个分布模式。聚类分析方法适合予在 所分析的数据缺乏描述信息，或者是无法组织成任何分类模式时采用，可以 盘动得到类别结果。 数据挖掘领域主要研究面向大型数据库、数据仓库的高效实用的聚类分 析算法。聚类分析是数据挖掘中的一个很活跃的研究领域，并提出了许多聚 1 2 哈尔滨下程大学硕士学何论文 类分析的方法，其中包括系统聚类法、分解法、加入法、动态聚类法、模糊 聚类法、运筹方法等。 3 关联规则 关联规则，即利用关联规则进行挖掘。在数据挖掘研究领域，对于关联 规则分析的研究开展得比较深入，人们提出了多种关联规则的挖掘算法，如 a p r i o r i 、抽样算法、d i c 等算法。关联分析的目的是挖掘隐藏在数据间的 相互关系，它能发现数据库中形如“9 0 的顾客在一次购买活动中购买商品 a 的同时购买商品b 之类的知识。 关联规则挖掘的形式描述是：设i = f l ，之，毛，) 是聊个不同项目的集 合，每个称为数据项，数据项的集合称为数据项集，d 是针对，的事务集 合，每一笔事务包含若干项目，f 2 ，丘，其中i ，若r 是，中一组项目的 集合，即t i ，一条关联规则就是形如x _ 】，的蕴涵式，其中z ，y ， x r 、】，= a 。如果d 中c 的包含x 的交易同时包含】，则关联规则x 一】，在 d 中置信度c 成立。如果d 中s 的交易包含x u y ，则关联规则x y 在d 中具有支持度s 。在进行关联分析时、用户需要输入两个参数：最小置信度 和最小支持度。关联分析就是生成所有具有用户指定的最小置信度和最小支 持度的关联规则。 关联规则发现的研究趋势一是从单一概念层次关联规则的发现发展到多 概念层次的关联规则的发现，即在具体应用中采掘规则可以作用到数据库不 同的层面上，比如在分析超市销售事务数据库过程中，从数据库原始字段如 面包、牛奶提升到更抽象的概念：食品，就有可能发现更为抽象的规则；二 是通过采用减少数据库扫描次数、采样、并行数据挖掘等技术提高算法效率。 4 数据可视化 随着数据仓库技术、网络技术、电子商务技术等的发展，可视化技术涵 盖了更广泛的内容。所谓数据可视化( d a t av i s u a l i z a t i o n ) 是对大型数据库或 数据仓库中的数据的可视化，它是可视化技术在非空间数据领域的应用，使 人们不再局限于通过关系数据表来观察和分析数据信息，还能以更直观的方 式看到数据及其结构关系。数据可视化技术的基本思想是将数据库中每一个 数据项作为单个图元元素表示，大量的数据集构成数据图像，同时将数据的 各个属性值以多维数据的形式表示，可以从不同的维度观察数据，从而对数 1 3 哈尔滨工程大学硕士学位论文 据进行更深入的观察和分析。 数据可视化技术包含以下几个基本概念： ( 1 ) 数据空间：是由n 维属性和m 个元素缀成的数据集所构成的多维信 息空间； ( 2 数据开发：是指利用一定的算法和_ 工具对数据进行定量的推演和计 算； ( 3 ) 数据分析：指对多维数据进行切片、块、旋转等动作剖析数据，从 而能多角度多侧面观察数据； ( 4 ) 数据可视化：是指将大型数据集中的数据以图形图像形式表示，并 利用数据分析和开发工具发现其中未知信息的处理过程。 目前数据可视化已经提出了许多方法，这些方法根据其可视化的原理不 同可以划分为基于凡何的技术、面向像素技术、基于图标的技术、基于层次 的技术、基于图像的技术和分布式技术等等。 5 。时阉序列 时间序列规则可以认为是一类特殊规则，主要研究的是时间序列中重复 发生概率较高的模式。时间序列规则的挖掘需要找出在某个最小时间内出现 比率一直高于闽值的规则，难点主要在于数据量大和发掘模式的算法选择。 一般来说，数据立方和相关时序是解决时间序列规则常用的方法。 时序模式是指透过时间序罗| l 搜索出的重复发生概率较高的模式。与回嬲 一样，它也是用己知的数据预测未来的值，但这些数据的区别是变量所处时 闻的不同。 2 2 数据分类中的决策树算法 2 2 1 数据分类及其标准 分类在数据挖掘中是一项焉摹常重要的任务，謦翦在商进中应用最多。分 类的目的是学会一个分类函数或分类模型( 分类器) 。该模型能把数据库中 的数据映射到给定类裂孛的某今。分类和露归都可用于预测。预测的曩的 是从利用历史数据记录中自动推导出给定数据的推广描述，从而能对未来数 据进行预测。 1 4 哈尔滨工程大学硕士学位论文 要构造分类器，需要有个训练样本数据集作为输入。训练样本数据集 亦称训练集( t r a i n i n gs e t ) ，是一条条数据记录( r e c o r d ) 组成的。每一条记录包 含若干条属性( a t t r i b u t e ) ，组成一个特征向量。训练集的每条记录还有一个特 定的类标签( c l a s s 1 a b e l ) 与之对应，该类标签是系统的输入，通常是以往的一 些经验数据。一个具体样本的形式可以为样本向量：一，圪；c ) 。这里鬈表 示字段符，c 表示类标签属性的值。 分类的璺的是：分析输入数据，遥过在谶练集中的数据体现出来的特性， 为每一个类找到一种准确的描述或模型。这种描述常常用谓词表示。由此生 成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类 标签是未知的，我们仍可以c l l 此预测这些新数据所属的类。只是预测，而不 能肯定。我们也可以由此对数据中的每一个类有更好的理解。也就是说，我 们获得了这个类酶知识。 分类器评价或比较尺度主要有三种： ( 1 计算复杂度依赖予舆体的实瑗细节和硬件环境，在数据挖掘中，由 于操作对象是巨量的数据库。因此空间和时间的复杂度问题将是非常重要的 一个环节。 ( 2 ) 预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于 预测型分类任务，躁前公认的方法是分层交叉验证法。 ( 3 ) 模型描述的简洁度对于描述型的分类任务，模型描述越简洁越受欢 迎；例如，采用规则表示的分类器构造法就比较简单，而神经网络方法产生 的结果就难以理解。 2 2 2 决策树分类算法 决策树方法自2 0 世纪6 0 年代以来，在分类、预测、规则提取等领域有 着广泛应用。尤其是在q u i l a n 于1 9 8 6 年提出i d 3 算法以后，在机器学习、 知识发现领域得到了进一步应用及巨大的发展。决策树是一树状结构，它的 每一个树结点可以是叶节点，对应着某一类，也可以对应着一个划分，将该 节点对应的样本集划分成若干个子集，每个子集对应一个节点。对一个分类 问题或规则学习问题，决策树的生成是一个从上至下、分而治之的过程。决 1 5 哈尔滨工程大学硕士学位论文 i i 麓置葺i i i i i 鼍皇i i i i i 葺麓t t t t t tt s t t t t t t t t t t i lt ill i 嗣 策树从根节点开始，对数据样本进行测试，根据不同的结果将数据样本划分 成不同的数据样本子集，每个数据样本子集构成一个子节点。对每个子节点 再进行划分，生成新的子节点。不断反复，直至达到特定的终止准则。生成 的决策树每个叶节点对应一个分类。对于生成的决策树，可以从根节点开始， 由主至下，提取规则：也爵对数据点进行分类或预报。对一个样本进行分类 时，从树的根节点开始，根据每个节点对应的划分将其归到相应的子节点， 壹至叶节点。叶节点所对应的类剐就是该样本对应的分类。 基于决策树的分类模型之所以被人们采用是因为其特有的优点。首先， 决策树模型效率高，对训练集数据量较大的情况较为适合；其次，决策树方 法结构简单，生成便于人们理解的规刘；再者，决策树算法的计算量相对来 说不是很大；然后，决策树方法通常不需要受训数据外的知识，擅长处理非 数值型数据。最后，决策树方法具有较高的分类精确度。“谶练集 作为分类 器中的输入，它的每一个元组的属性和数据库的元组的属性相同，并且每个 元组都有一个类标志。分类的骞标是通过分析训练集中的数据，对类进行准 确的描述或者建立模型，然后用它对数据库中的其它数据分类或者上升为分 类规则。 决策树数据分类操作通常有以下两个步骤： 第一步，根据给定的训练集，找到合适的映射函数：f ( x 1o c 的表示 模型。这一部通常称为模型调练阶段。