（计算机应用技术专业论文）决策树在软构件检索中的应用研究.pdf

摘要 软构件技术是支持软件复用的核心技术，在基于构件的软件开发过程中，构件 库系统扮演着一个重要角色。在构件库的管理中，检索和提取满足用户需求的构件 一直是构件库系统的核心问题。构件库的检索效率不仅包括对构件本身的检索效率， 而且还包括构件查询者对构件的理解效率。而一般的构件库系统只是从描述性信息 方面提供对构件的理解，却很少从实际复用方面提供对构件的理解。数据挖掘技术 为解决上述问题提供了一条可行的途径。 本文对如何利用决策树分类方法进行可复用构件的复用规则挖掘作一探讨。首 先讨论了软构件复用和数据挖掘理论，其中重点讨论了软构件检索理论和决策树分 类方法。在此理论基础上，针对传统软构件检索研究的局限性，提出了将数据挖掘 技术应用到软构件检索中的思想。尝试利用数据挖掘技术来发现软构件复用规律， 为构件库的相关人员提供辅助决策支持。然后结合实际应用，建立一个将数据挖掘 技术应用于软构件检索管理中的应用模型，并分析了该应用模型的实施步骤。最后 通过实验验证了这个模型，从而证明了这种策略的可行性与有效性。 关键词软件复用；构件库：构件检索：数据挖掘；决策树 i a b s t r a c t s o r w a r ec o m p o n e n tt e c h n o l o g yi st h ek e yt e c h n o l o g yo fs u p p o r t i n gt h es o 矗 w a l e r e t i e ，i nt h ep r o c e s so ft h es o f t w a r ed e v e l o p m e n tb a s e do nc o m p o n e n t ，c o m p o n e n t l i b r a r yp l a y sak e yr o l e t or e t r i e v ea n de x t r a c tt h em o s ts a r i s f y i n gc o m p o n e n ta m o n gt h e l i b r a r yo fc o m p o n e n t si si m p o r t a n ti nc o m p o n e n tl i b r a r ym a n a g e m e n ts y s t e m t h e r e t r i e v a le f f i c i e n c yo ft h ec o m p o n e n tl i b r a r yn o to n l yi n c l u d e st h er e t r i e v a lo ft h e c o m p o n e n ti t s e l f , b u ta l s oi n c l u d e st h eu n d e r s t a n d i n go ft h ec o m p o n e n t t h eg e n e r a l c o m p o n e n tr e t r i e v a ls y s t e mp r o v i d e sd e s c r i p t i v ei n f o r m a t i o na b o u tu n d e r s t a n d i n gt h e c o m p o n e n ts i m p l y , b u ts e l d o mp r o v i d e si n f o r m a t i o na b o u tr e s p e c to fr e u s e da c t u a l l y d a t am i n i n gt e c h n o l o g yp r o v i d e saf e a s i b l ea p p r o a c ht oa b o v ep r o b l e m i nt h ep a p e r , h o wt ou s et h ea p p l i c a t i o no fc l a s s i f i c a t i o nm e t h o dd e c i s i o n - t r e e b a s e d t ot h ec o m p o n e n tr e u s ew a sd i s c u s s e d f i r s t l y , t h et h e o r yo fs o f t w a r ec o m p o n e n tr e u s e a n dd a t am i n i n gw e r ed i s c u s s e d ，w el a i ds t r e s su p o nt h er e t r i e v a lo fs o f t w a r ec o m p o n e n t a n dt h ec l a s s i f i c a t i o nm e t h o dd e c i s i o n - t r e e b a s e d o n 也eb a s i so ft h et h e o r y , i n a c c o r d a n t ew i t ht h el i m i t a t i o no fr e s e a r c ho nt r a d i t i o n a ls o f t w a r ec o m p o n e n tr e u s e r e t r i e v a l ，w ep r o p o s e dt h ei d e at oa p p l yd a t am i n i n gt e c h n o l o g yt ot h e r e t r i e v a lo f s o f t w a r ec o m p o n e n tr e u s e ，p r o v i d e da u x i l i a r yd e c i s i o ns u p p o r tt ot h er e l e v a n tp e r s o n n e l o ft h ec o m p o n e n tl i b r a r y s e c o n d l y , i na c c o r d a n c ew i t ha c t u a la p p l i c a t i o n ，b u i l ta n a p p l i e dm o d e lo fs o f t w a r ec o m p o n e n tr e t r i e v a lm a n a g e m e n tb yd a t am i n i n gt e c h n o l o g y , a n da n a l y z e dt h ee x e c u t i o ns t e po ft h ea p p l i e dm o d e l l a s t l y , t h em o d e lh a db e e n v e r i f i e dt h r o u g he x p e r i m e n t ，t h u st h ef e a s i b i l i t ya n dv a l i d i t yo ft h i ss t r a t e g yh a db e e n v e r i f i e d k e yw o r d ss o r w a r er e u s e ；c o m p o n e n tl i b r a r y ；c o m p o n e n tr e t r i e v a l ；d a t am i n i n g ； d e c i s i o nt r i i 河北大学 学位论文原创性声明 本人郑重声明： 所呈交的学位论文，是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了致谢。 作者签名： 至毯l 一肇 日期：兰竺年月堡一日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他 复制手段保存论文。 本学位论文属于 1 、保密口，在年月臼解密后适用本授权声明a 2 、不保密口。 ( 请在以上相应方格内打“4 ”) 作者签名：翌丝空 导师签名：g 至互趟 导师签名： 兰聋型趟 日期：兰堕年互_ 月盟日 日期：之! 兰年上月兰一日 1 1 研究背景 第1 章绪论 自从1 9 6 8 年n a t o 软件工程学术会议上提出“软件危机”以来，软件工程己经取 得了很大进展，然而这一危机并投有消失。随着计算机应用的迅速扩大，软件规模及复 杂性的不断提高，软件危机更加明显地暴露出来。目前，软件所面临的主耍问题之一是 如何提高软件生产率和质量【】。软件复用被视为解决软件危机，提高软件生产效率和质 量的现实可行的途径【2 j 。软件复用是在软件开发中避免重复劳动的解决方案，其出发点 是应用系统的开发不再采用一切“从零开始”的模式，而是以己有的工作为基础，充分 利用过去应用系统开发中积累的知识和经验( 如需求分析结果、设计方案、源代码、测 试计划及测试实例等) ，从而将开发的重点集中于应用的特有构成成分。通过软件复用， 在应用系统开发中可以充分地利用己有的开发成果，消除包括分析、设计、编码、测试 等在内的许多重复劳动，提高了软件的开发效率；同时，通过复用高质量的开发成果， 避免了重新开发可能引八的错误，从而提高了软件的质量c 3 】- ”。 软件复用可以从多个角度进行考察依据复用的对象，软件复用分为对产品的复用 和对过程的复用。过程复用依赖于软件自动化技术的发展，目前只适用于一些特殊的应 用领域；产品复用是目前现实的、主流的途径1 8 1 。软构件技术是支持软件复用的核心技 术f ”，要支持基于软构件复用的软件开发过程，就必须要有支持整个软件生存周期并包 含有大量可复用软构件豹构件库系统，构件库系统是支持款件复用的必要设施c 然而随 着构件库中构件数目的增加，复用者在检索和选取构件时就会遇到困难，因此就要求必 须对构件库进行有效的组织和管理，这直接关系到复用实践的成功与否。 1 2 国际国内研究现状 针对不同的构件描述形式，研究人员已提出了许多相应的检索方法e 例如p c t t d y p o d 聃r s h 等人针对构件的行为表示提出的基于构件行为采样的检索1 1 ；a ”ym o o r m a n n 等人针对构件的形式化规格说明提出的基调匹配( 接口规约) m 1 和规约匹配( 功能规约) 等人针对构件的形式化规格说明提出的基调匹配( 接口规约) m 1 和规约匹配( 功能规约) 河北入学工学硕士学位论文 ! i ii i i i l l l ir i _ _ - 兰 ”2 j 。目前，构件的刻面描述是一种正逐步得到重视与应用的描述方法 1 3 j ，r e b o o t 、 n a t o 提出的构件分类方法都是基于刻面的。青鸟构件库的构件也是采用以刻面分类为 主、多种分类模式相结合的方法对构件进行分类描述的【1 4 。 其中，r e b o o t ( r e u s eb a s e d0 1 3o b j e c t o r i e n t e dt e c h n i q u e s ) 是一个包括储存可复用 构件的数据库和一组产生、认证、插入、提取、评价和适配可复用构件的环境。在对构 件进行分类时它采用了刻面分类策略，但是它的刻面分类模式主要针对的是源代码级别 的构件，不能描述粒度较大、结构较复杂的构件( 如模式、框架) 。 n a t o ( n o r t ha t l a n t i ct r e a t yo r g a n i z a t i o n ) 提出了一种刻面分类模式，其中的刻面不 必彼此独立或适用于所有的构件。因此在对一个构件进行分类时，未必用所有的刻面来 描述。刻面术语之间或者没有关系或者是同义词关系，术语空间是非结构化的。 此外，国内对构件库的研究也有了相应的成果。其中，以我国北京大学的青鸟工程 为软件复用及相关技术的研究工作水平的代表。膏鸟工程在“九五”期间开发了基于异 构平台、具有多信息源接口的应用系统集成( 组装) 环境青鸟型( j b 3 ) 系统。在相应构 件模型的基础上，建立了青乌构件库数据模型，并与其它c a s e 工具相结合，支持对构 件的描述( 使用青鸟构件描述语言m c d l ) 、分类、管理、存储、检索和复合，满足了 基于“构件。构架”复用的软件开发过程的需要。 上述的各种方法，都是针对检索构件本身的。然而在实际的软构件复用过程中，构 件的检索不仅应该能够高效检索出相关的构件集，关键是如何使复用者快速地理解所检 索到的构件，从而在这个构件集中找到自己的真正所需，这是一个复杂的决策过程，一 般都依赖于复用者的复用经验以及通过浏览构件描述信息对构件的理解和主观评判。数 据挖掘技术可以从构件库的大量数据中获得决策支持所需的多种知识，尝试采用数据挖 掘技术，从构件的复用历史信息和复用者复用构件的反馈信息出发建立挖掘数据集，采 用相应的数据挖掘方法挖掘出构件复用的若干规律，最大限度地排除人为的因素，变盲 目的、凭印象或凭经验的复用为建立在数据分析基础上的科学量化分析；变孤立的、分 散的复用为在科学计算分析基础上对规律性和趋势性的判断。 1 3 课题的提出及研究的主要内容和创新点 在基于构件的软件复用过程中，构件库系统扮演着一个重要角色。其中，构件的有 第1 章绪论 效管理和检索是构件库系统的关键技术之一。尽管构件库系统的检索主要借助于数据库 管理系统完成，但与数据库检索不同的是：构件库的检索不仅应该能够高效检索出相关 的构件集，关键是如何使复用者快速地理解所检索到的构件，从而在这个构件集中找到 自己的真正所需。由此可见，构件库的检索效率不仅包括对构件本身的检索效率，还应 包括构件复用者对构件的理解效率。复用者对于构件的理解：一方面，通过浏览构件库 中的构件描述信息准确地理解构件的功能性以及非功能性指标；另一方面，在构件的复 用历史数据和复用者复用构件的反馈数据中，隐含着大量事先不知道的但又潜在的有用 信息。如何从相关数据中找出这些潜在的有用信息，使复用者能够从其它复用者复用构 件的危度来理解构件，从而了解所关注的构件在实际应用方面的信息，这是一般的构件 检索系统所不能提供的。数据挖掘技术可以从数据库或数据仓库以及其它各种数据库的 大量各种类型数据中，自动抽取或发现有用的模式知识【”】，从而正好能够满足这一需求。 数据挖掘( d a t am i n i n g ) 1 6 1 就是从大量的、不完全的、有噪声的、模糊的、随机的原 始数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用、可信、新颖的信 息和知识的过程。从广义角度讲数据、信息是知识的表现形式，但在数据挖掘中更多地 把概念、规则、模式、规律和约束等看作知识。数据挖掘的原始数据可以是结构化的， 如关系型数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分 布在网络上的异构型数据。发现知识的方法可以是数学的或非数学的、演绎的或归纳的。 数据挖掘的成果可以用在信息管理、过程控制、科学研究、决策支持等许多方面1 1 7 l 。总 之，数据挖掘是- - f - j 广义的交叉学科，它的发展和应用涉及到不同的领域，尤其是数据 库、人工智能、数理统计、可视化、并行计算【1 9 1 等，例如零售目标市场营销、客户保 持、欺诈检测和医疗诊断等。但是在软构件查询管理中的应用目前还没有。本文尝试采 用数据挖掘技术中的分类方法，从构件的复用历史信息和复用者复用构件的反馈信息出 发建立挖掘数据集，提出了一个将数据挖掘技术应用于软构件检索管理中的应用模型。 根据特定的挖掘数据，采用数据挖掘中的分类方法挖掘隐含在其中的信息，以便为构件 库系统的相关人员提供辅助决策支持。从而提高构件库系统的管理水平和构件复用水 平。为复用的成功提供技术保障。 本文的主要内容和创新点包括： ( 1 ) 本文讨论了软件复用理论和数据挖掘技术，针对传统软构件检索研究的局限性， 提出了将数据挖掘技术应用到软构件检索中的思想。尝试利用数据挖掘技术来发现软构 3 河北大学工学硕士学位论文 件复用规律，为构件库的相关人员提供辅助决策支持； ( 2 ) 结合实际应用，建立一个将数据挖掘技术应用于软构件检索管理中的应用模型： ( 3 ) 采用构建一个复用构件库使用的模拟平台的方法，给出一组模拟复用库平台上的 实验数据，用以验证这个应用模型，从而证明这种方法的可行性与有效性。 1 4 论文的组织 本文探讨了数据挖掘中的决策树方法在软构件检索中的辅助决策支持，文章内容组 织如下： 第1 章绪论：介绍课题的研究背景、研究现状，提出本文的研究目标； 第2 章软构件检索：介绍软构件检索技术、现存问题，指出解决方案； 第3 章数据挖掘中的分类技术：介绍数据挖掘分类技术、各种分类方法以及各自 的优缺点： 第4 章决策树在软构件检索中的应用：提出了一个应用模型，并通过实例进行验 证，从而证明了这种策略的可行性与有效性； 第5 章总结与展望：对本文所做的工作进行总结，并对下一步的工作进行展望。 4 第2 章软构件检索 第2 章软构件检索 软件复用是指重复使用“为了复用目的而设计的软件”的过程 2 0 j 。相应地，可复用 软件是指为了复用目的而设计的软件。 软件复用可以从多个角度进行考察【2 l 】，依据对可复用信息进行复用的方式，可以将 软件复用区分为黑盒( b l a c k - b o x ) 复用和白盒( w h i t e b o x ) 复用。黑盒复用指对已有构件不 需作任何修改，直接进行复用。这是理想的复用方式。白盒复用指已有构件并不能完全 符合用户需求，需要根据用户需求进行适应性修改后才使用。依据复用的对象，可以将 软件复用分为产品复用和过程复用【2 2 】：产品复用指复用已有的软构件，通过构件集成( 组 装) 得到新系统；过程复用指复用已有的软件开发过程，使用可复用的应用生成器来自 动或半自动地生成所需系统。过程复用依赖于软件自动化技术的发展，目前只适用于一 些特殊的应用领域；产品复用是目前现实的、主流的途径。基于构件的复用是产品复用 的主要形式，也是当前复用研究的焦点1 2 3 ，软构件技术是支持软件复用的核心技术。 2 1 软件构件技术 基于构件的开发技术通过复用原有构件、开发少量新构件，可以快速地组装出一个 新的系统，就如同计算机硬件工程师用集成电路板快速组装出一台新的计算机一样。构 件技术已经成为当前软件开发技术的主流。 2 1 1 软件构件技术概述 软件行业的工业化趋势导致了软构件的产生。所谓构件( c o m p o n e n t ) 是指软件产品 中可以明确辨识的组成成分，可分为分析件、设计件、代码件、测试件等。可复用构件 ( r e u s a b l ec o m p o n e n t ) ：是指具有相对独立功能和可复用价值的构件。 可复用构件应具备以下属性： ( 1 ) 有用性( u s e f u l n e s s ) ：构件必须提供有用的功能； ( 2 ) 可用性( u s a b i l i t y ) ：构件必须易于理解和使用； ( 3 ) 质量( q u a l i t y ) ：构件及其变形必须能正确工作； 河北大学工学硕士学位论文 ( 4 ) 适应性( a d a p t a b i l i t y ) 构件应该易于通过参数化等方式在不同语境中进行配置； ( 5 ) 可移植性( p o r t a b i l i t y ) ：构件应能在不同硬件运行平台和软件环境中工作。 随着对软件复用理解的深入，构件的概念已不再局限于源代码构件，而是延伸到需 求、系统和软件的需求规约、系统和软件的构架、文档、测试计划、测试案例和数据以 及其它对开发活动有用的信息，这些信息都可以称为可复用软构件。 软构件技术是支持软件复用的核心技术，是近几年来迅速发展并受到高度重视的一 个学科分支。其主要研究内容包括： ( 1 ) 构件获取：有目的的构件生产和从已有系统中挖掘提取构件； ( 2 ) 构件模型：研究构件的本质特征及构件问的关系； ( 3 ) 构件描述语言：以构件模型为基础，解决构件的精确描述、理解及组装问题； ( 4 ) 构件分类与检索：研究构件分类策略、组织模式及检索策略，建立构件库系统， 支持构件的有效管理； ( 5 ) 构件复合组装：在构件模型的基础上研究构件组装机制，包括源代码级的组装和 基于构件对象互操作性的运行及组装： ( 6 ) 标准化：构件模型的标准化和构件库系统的标准化。 2 1 2 构件库在软构件复用中充当的角色 基于软构件复用的软件开发主要分为两个方面：可复用软件( 构件) 的开发 ( d e v e l o p m e n tf o rr e u s e ) 和基于可复用软件( 构件) 的应用系统构造( 集成和组装) ( d e v e l o p m e n tw i t hr e u s e ) ( 如图2 - 1 所示) 。 图2 1 基于软构件复用的软件开发 6 基于可复用软构件的应用系统构造 -t。1 。+ 可复用软构件的开发 第2 章软构件检索 由图2 - 1 可以看出，要支持基于软构件复用的软件开发过程，就必须要有支持整个 软件生存周期并包含有大量可复用软构件的构件库，构件库是支持软件复用的必要设 施。 构件库是一种组织、收集、访问与管理若干构件的手剧洲，它由构件库数据和构件 库系统组成。构件库数据包括构件本身及其描述性信息和组织性信息，这些信息总称为 构件目录，其中描述性信息称为构件描述，组织信息称为库信息模型：构件库系统由构 件库框架和构件库工具组成，构件库包含了大量信息，包括构件、构件描述信息、构件 库数据模型和描述数据模型的模型。构件库的存在使得一般意义上的软构件可以实现复 用，可复用构件库中存储、查询、获取构件是复用的关键技术之一【2 5 1 。 软件复用可以定义为：软件工程师之间思想和成果的交流。事实上，为了避免对己 经存在的软件构件进行再开发，软件工程师应该了解其他工程师的成果。然而，如果没 有一个过程用于系统地记录软件和相关软件的构造，在以后的项目开发中抽取可利用的 知识就会变得相当困难。这就表明：构件库除了存储和管理构件之外( 普通数据库的作 用) ，关键是在构件的创建者和使用者之间架起一座“理解构件含义”的桥梁。构件库 的基本功能是存储软件工程师的思想和成果，并方便他们进行交流，其本质是充当软件 工程师之间思想交流的工具，使基于构件、构架的开发过程中的构件能够得到正确的理 解和复用。然而，即使构件库对工程师思想系统地进行组织，不同的工程师之间成功地 交流思想也需要付出很大的努力。 2 2 软构件检索 与软件构件库相关的中心问题是构件的检索问题：如何在库中找到合适的构件用于 构造目标应用系统。构件的分类、检索一直是一个制约构件复用的主要因素。 2 2 1 软构件检索步骤 软件复用被视为软件开发走上工程化和产业化道路的希望，软构件技术则是支持软 件复用的核心技术。用户对构件的复用必须包括三个步骤： ( 1 ) 检索构件：根据用户需要找到仅需做最小修改的复用构件； ( 2 ) 理解构件：清楚构件的功能及其细节，以便进行修改和扩充，最终达到复用的目 河北大学工学硕士学位论文 的： ( 3 ) 接受构件：把构件的实现部分加到自己的系统中，因此实现软件复用。 其中构件检索是最为关键的一步，它直接影响到用户能否对构件进行复用。 一个软件开发者在系统开发的过程中，决定是否采用可复用构件取决于复用成本和 重新开发成本的比较，如果满足条件：复用成本 开发成本，那么就决定了他会选择复 用构件以减少系统开发的成本。我们把复用成本理解为： 复用成本= 检索成本+ 理解成本+ 修改成本+ 使用成本 其中使用成本指的是从商业构件库中购买构件的成本。 针对不同的构件描述形式，研究人员已提出了许多相应的检索方法，大大降低构件 检索的成本，促进了软构件的复用。然而这些方法都往往忽略了构件的理解成本，而 p d g ( r e u $ el i b r a r yh a t e r o p e r a b i l i t yc , r o u p ) 贝o 认为：软件复用中的理解问题是影响复用成 功的一个关键问题。也就是说，在实际的软构件复用过程中，复用者不仅应该能够高效 检索出相关的构件集，关键是如何使复用者快速地理解所检索到的构件，从而在这个构 件集中找到自己的真正所需，这是一个复杂的决策过程，一般都依赖于复用者的复用经 验以及通过浏览构件描述信息对构件的理解和主观评判。 2 2 。2 软构件检索过程中存在的困难 构件库是实现软件复用的重要依托，软件复用的成功与否在很大程度上取决于构件 库的结构、成分、管理方式等口6 1 。研究表明：检索和选取满足用户需求说明的构件一直 是构件库构造的核心问题。随着构件的增多，构件库的不断膨胀，为构件库的管理带来 了诸多不便，在大型的软件构件库中检索符合用户需求的构件变得越来越困难。除了与 信息系统相似的问题外，构件库中有许多不同于信息系统的问题。用户在检索和选取构 件时会碰到以下一些困难1 2 7 】： ( 1 ) 在检索过程中，可能有多个满足用户检索条件的构件，如何快速有效地从众多的 候选构件中准确地判断并选取所需的构件，这是一个复杂的决策过程，一般都依赖于用 户的复用经验以及对构件的理解和主观评判； ( 2 ) 通常用户是通过刻面、属性、关键词、关系等表达所需构件的特征以进行构件的 检索。然而，访问构件库的用户具有不同的层次，有可能并不熟悉构件的刻面模式等， 第2 章软构件检索 对构件的理解比较困难： ( 3 ) 用户在查询前也许并没有一个明确的目标，只是想通过检索软构件库看是否有能 够利用和复用的构件，因而如何通过构件的复用历史和其他用户的复用经验为用户提供 一定程度的帮助是很必要的； ( 4 ) 对需求规约、设计、模式、测试计划等文档型知识的构件复用属于间接复用，需 要复用者首先进行分析和理解。而且，在大多数情况下，对构件的复用均是白盒复用， 也即要根据构件复用者的反馈，对构件进行适应性修改。如何跟踪构件复用的经验和复 用历史，辅助用户选取相应的分析设计件以及改动最小的构件很关键； ( 5 ) 即使在找到相关的构件时，对构件所提供的功能不了解和构件文档的缺乏使得复 用者经常误用构件。 2 2 3 解决方案 由上述问题可见，构件的复用历史信息( 描述该构件或构件系统的拨复用的历史) 和复用反馈信息( 复用者对构件复用情况的反馈评价) 很重要：一方面，它不仅可以帮 助构件提交者进行构件再工程，改进原构件，而且还可以对构件进行深化，开发出新的 构件；另一方面，构件反馈信息可以使构件复用者从以前的构件复用者那里得到一些复 用经验信息，增强对构件的理解，减少复用工作量。数据挖掘技术可以从构件库的相关 数据中获得决策支持所需的多种知识。本文尝试采用数据挖掘技术，从构件的复用历史 数据和复用者复用构件的反馈数据出发建立挖掘数据集，采用相应的数据挖掘方法挖掘 出构件复用的若干规律，最大限度地排除人为的因素，变盲目的、凭印象或凭经验的复 用为建立在数据分析基础上的科学量化分析；变孤立的、分散的复用为在科学计算分析 基础上对规律性和趋势性的判断。 河北大学工学硕士学位论文 第3 章数据挖掘中的分类技术 信息科学的发展引起数据的高度膨胀，如何有效地处理大规模的数据信息，得出有 用知识，便成为目前值得关注的问题。数据挖掘一从大规模数据中发现非平凡模式，正 是应此要求迅速发展起来的- - i 、 科学。本章简要介绍了数据挖掘及分类技术，并对其中 的决策树分类作较为详细的介绍。 3 1 数据挖掘概述 数据挖掘就是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣的 知识的过程，而这些知识是隐含的、事先未知的潜在有用信息。它可以使用智能的方法 提取数据模式，有趣的模式可提供给用户或者作为新的知识存放在知识库中。数据挖掘 是一门交叉学科，它涉及的学科领域包括：数据库技术、人工智能、机器学习、神经网 络、统计学、模式识别、知识库系统、知识获取、信息检索、高性能计算和数据可视化 等。数据挖掘的成果可以用在信息管理、过程控制、科学研究、决策支持等许多方面。 数据挖掘过程是一个多次的循环反复的过程，每一个步骤一旦与预期目标不符，都 要回到前面的步骤，重新调整，重新执行。其主要步骤如下： 1 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最后 结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖掘则带有盲 目性，是不会成功的。 2 数据准备 ( 1 ) 数据选择。搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用 于数据挖掘应用的数据。 ( 2 ) 数据预处理。研究数据的质量，为进一步的分析做准备。并确定将要进行的挖掘 操作的类型。 ( 3 ) 数据转换。将数据转换成一个分析模型。这个分析模型是针对挖掘算法建立的。 建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 1 0 第3 章数据挖掘中的分类技术 3 数据挖掘 对所得到的经过转换的数据进行挖掘。除了完善选择合适的挖掘算法外，其余一切 工作都能自动地完成。 4 结果分析 解释并评估结果，其使用的分析方法一般因数据挖掘操作而定，通常会用到可视化 技术。 5 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 3 2 分类技术 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用非常广泛【2 钔。分类的 目的是学会一个分类函数或分类模型( 也常常称作分类器) ，该模型能把数据库中的数 据项映射到给定类别中的某一个。例如：可以建立一个分类模型，对银行贷款的安全或 风险进行分类。许多分类的方法己被机器学习、专家系统、统计学和神经生物学方面的 研究者提出。 本节将讨论分类的基本技术，比较几种典型的分类算法。 3 2 1 分类的基本概念 分类是数据挖掘中一项非常重要的任务，分类的目的是提出一个分类函数或分类模 型( 分类器) ，该模型能把数据库中的数据项映射到给定类别中的某一个。我们可以举 一个简单的例子，信用卡公司的数据库中保存着各持卡人的记录，公司根据信誉程度将 持卡人记录分成三类：良好、一般、较差，并且类别标记已赋给了各个记录。分类分析 就是分析该数据库的记录数据，对每个信誉等级做出准确描述，如“信誉良好的客户是 指那些年收入在5 万元以上，年龄在4 0 5 0 岁之间的人士”，然后根据这些描述对其它 具有相同属性的数据库记录进行分类。 分类的过程可分为以下两步： 第一步，建立一个模型，描述预定的数据类或概念集。 第二步，使用模型进行分类。 河北人学上学硕士学位论文 皇i l l 目t 目目j e e e | 自e e 目$ 日e 自_ 3 2 2 分类技术 在分类分析中，分类模型的构造方法有统计方法、神经网络方法及机器学习方法等。 统计方法包括贝叶斯法和非参数法( 近邻学习或基于事例的学习) ，对应的知识表示为 判别函数和原型事例。神经网络方法主要是多层前向神经网络的误差反向传播( e r r o r b a c k p r o p a g a t i o n ，b p ) 算法，用模型表示是前向反馈神经网络模型，该算法的实质是一种 非线性的判别函数。机器学习方法包括决策树法和规则归纳法，前者对应的表示是决策 树或判别树，后者则一般为产生式规则。另外，近年来又出现了一种称为粗糙集( r o u g h s e o 新的理论方法，它将知识表示为产生式规则。 下面将简要介绍一些常用的分类技术，如决策树分类、贝叶斯分类、基于神经网络 的分类。 1 决策树分类 基于决策树的分类方法是一种监督学习的方法 2 9 】【3 3 1 ，树的数量由分类的精度和树 的大小决定。决策树分类采用自项向下的递归方式，在决策树的内部结点进行属性值的 比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以 从根到时结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式 规则。 关于决策树分类在第三节中详细介绍。 2 贝叶斯分类 贝叶斯分类是统计学分类方法，它基于贝叶斯定理。可以预测类成员关系的可能性， 如给定样本属于一个特定类的概率。 贝叶斯网络的研究在国外十分广泛，它可以对不确定性知识进行推理。例如：医生 看病，根据病人的症状，判断病人是否得了某种疾病，往往是一种不确定的推理( 带概 率的推理) ，多数情况下没有百分之百的把握。运用贝叶斯网络进行推理，可以达到较 好的效果。 3 基于神经网络的分类 神经网络最早是由心理学家和神经学家提出的，旨在寻求开发和测试神经的计算模 拟。粗略地说，神经网络是一组连接的输入输出单元，其中每个连接都与一个权相联a 在学习阶段，通过调整神经网络的权，利用预测输入样本的正确类标号来学习。由于单 第3 章数据挖掘中的分类技术 元之间的连接，神经网络学习又称连接者学习 3 4 1 。 神经网络的优点包括其对噪音数据的高承受能力，以及它对未经训练的数据的分类 能力。此外，最近己提出了一些由训练过的神经网络提取规则的算法，这些因素推动了 神经网络在数据挖掘分类方面的应用。 3 2 3 分类算法的比较标准 分类算法可以根据下列标准进行比较和评估： 1 预测准确度 预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务，露前公认的 方法是1 0 番分层交叉验证法。 2 计算复杂度 计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨 量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。 3 强壮性 这涉及对于数据集中噪声数据或空缺值的处理，在有噪声数据或空缺值的情况下模 型是否具有正确预测的能力。 4 可伸缩性 大部分的分类算法是内存驻留算法，通常假定数据量很小。对于海量的数据，是否 具有有效的构造模型的能力，即算法的可伸缩性是很重要的。 5 模型简洁度和可理解性 对于描述型的分类任务，模型描述越简洁并且越容易理解则越受欢迎。例如，采用 规则表示的分类器构造法比较有用，而神经网络方法产生的结果就比较难以理解。 3 3 决策树分类 决策树分类是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的事 例中推出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部结 点进行属性的比较并根据不同属性值判断从该结点向下的分支，在决策树的叶结点得到 结论。所以从根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组 河北火学工学硕士学位论文 析取表达式规则【3 5 1 。 3 3 1 决策树 决策树( d e c i s i o nt r e e ) 是运用于分类的一种类似于流程图的树结构。决策树的顶层节 点是树的根节点，每个分支代表一个测试输出，每个非叶节点表示一个属性的测试，每 个叶节点代表个类或一个类的分布。决策树可以很容易地转换成分类规则，即从根节 点到叶节点的每条路径均可以转换成一条型为“i f n e n ”的分类规则，其中i f 部分是沿 着某条路径上的每个内部节点的属性值对形成的一个合取项，t h e n 部分是包含类预测 的叶节点。一个典型的决策树模型如图3 - 1 所示，用来预测某地区“小麦产量”的高低。 图3 - 1 预测菜地区“小麦产量”的高低 用决策树进行分类分两步走。第一步是利用训练数据集建立一棵决策树模型。这个 过程实际上是一个从数据中获取知识，进行机器学习的过程。第二步是利用生成完毕的 决策树模型对未知的数据样本进行分类。对未知的数据样本，从根节点依次测试样本的 属性值，直到到达某个叶子节点，从而找到该数据样本所在的类。 3 3 2 决策树分类算法 决策树学习采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根 据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以从根到叶 结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。 1 决策树分类算法描述 决策树的基本算法是贪心算法，算法的基本策略如下： ( 1 ) 树以代表训练样本的单个结点开始； ( 2 ) 如果样本都在同一个类，则该结点成为树叶，并用该类标记； ( 3 ) 否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将 1 4 第3 章数据挖掘中的分类技术 _ _ _ _ | _ - _ _ _ 墨墨墨墨墨墨鼍_ _ 蕾墨审岛罡墨墨墨_ 置圈 样本分类的属性。该属性成为该结点的“测试”或“决策”属性； ( 4 ) 对测试属性的每个己知的值，创建一个分支，并据此划分样本； ( 5 ) 算法使用同样的过程，递归地形成每个划分上的样本决策树。一旦一个属性出现 在一个结点上，就不必在该结点的任何后代上考虑它； ( 6 ) 递归划分步骤仅当下列条件之一成立时停止： 给定结点的所有样本属于同一类； 没有剩余属性可以用来进一步划分样本。在此情况下，使用多数表决。这涉及将 给定的结点转换成树叶，并用样本中的多数所在的类标记它，或者说，可以存放结点样 本的类分布； 分支t e s t a t t r i b u t e = a i 没有样本。在这种情况下，以样本中的多数类创建一个树叶。 在树的每个结点上使用信息增益( i n f o r m a t i o ng a j n ) 度量选择测试属性。这种度量称 作属性选择度量或分裂的优劣度量。选择具有最高信息增益( 或最大消压缩) 的属性作 为当前结点的测试属性，该属性使得对结果划分中的样本分类所需的信息量最小，并反 映划分的最小随机性或“不纯性”。这种信息理论方法使得对一个对象分类所需的期望 测试数目最小，并确保找到一棵简单的树。 2 典型的决策树算法 常用的决策树算法主要包括c a r t , c h a i d ，i d 3 ，c 4 5 ，c 5 0 1 3 6 1 1 3 7 1 等。c a r t 算法【3 8 】 是由l e ob r e i m a n , j e r o m ef r i e d m a n 等专家提出的一种数据勘测和预测算法。在建立 c a r t 树时，每个预测属性的选择是根据它在不同情况下对记录划分的好坏程度来进行 的；c h a i d 算法t a g j t px 检验法自动交感侦察器，也用于生成决策树，但是它不使用信 息增益来度量最佳分裂，而是采用列联表中使用的x 检验法来决定哪个类别预测属性与 预测值能最大程度地独立；i d 3 算法【4 0 】是1 9 8 6 年由q u i n l a n 提出的最具影响力的一种决 策树算法，它以自顶向下递归的各个击破的方式构造决策树。i d 3 算法具有描述简单、 分类速度快、计算量小的特点，且适用于大规模数据集的学习问题f 4 1 】f 4 2 】，但i d 3 算法只 能处理离散型的描述性属性；c 4 5 算法是q u i n l a n 在1 9 9 3 年提出的构造决策树分类器 的一种算法【4 引，它是i d 3 算法的后续算法 4 4 1 ，能够处理连续型数据，不仅分类准确率高 而且速度快。c 4 5 在以下几个重要的方面对i d 3 进行了改进： ( 1 ) 缺少值的预测属性仍然可用； ( 2 ) 有连续值的预钡4 属性可用； 河北大学工学硕士学位论文 ( 3 ) 提出了剪枝； ( 4 ) 规则推导。 与i d 3 算法不同，c 4 5 采用基于信息增益率( i n f o r m a t i o ng a i nr a t i o ) 的方法选择测试 属性。信息增益率等于信息增益对分割信息量( s p l i ti n f o r m a t i o n ) 的比值，求出当前候选 属性集中所有属性的信息增益率，比较它们找出信息增益率最高的属性，若为离散属性， 则按照该属性的不同取值分割当前样本集；若为连续属性，则依据它的分割阈值，将当 前样本集分为两个子样本集。对每个子样本集用同样的方法继续分割直到不可分割或达 到停止条件为止。生成决策树是c 4 5 算法的第一阶段，之后，就是计算每个节点的分 类错误( c l a s s i f i c a t i o ne r r o r ) ，进行树剪枝。 c 5 ，0 是c 4 5 由r u l eq u e s tr e s e a r c h 研究的后期改进算法。c 5 0 是实现了将多棵决策 树融合成一棵决策树的分类器。其算法思想是在分类时产生多次分类，先从训练集中产 生决策树，然后在第二遍分类的时候预估计第一次分类时候的错误，然后加以考虑，按 预定的次数反复进行分类。s e e5 ( w i n d o w s9 8 m e 2 0 0 0 x p 版本) 是c 5 o ( u n i x 版本) 的 对应版本，本文将采用s e e5 进行数据挖掘。 3 3 3 决策树的优缺点 1 优点： ( 1 ) 树形结构的模型很易于理解； ( 2 ) 由树形模型提取分类规则很容易； ( 3 ) 计算量相对来说不是很大： ( 4 ) 可以处理多种数据类型。 2 缺点： ( 1 ) 随着数据复杂性的提高，其分支数也增多，增加了管理上的困难； ( 2 ) 分类数据的预处理工作，不仅增加了算法的额外开销，而且降低了分类准确性； ( 3 ) 存在缺值处理问题。 1 6 第4 章数据分发策略的设计与实现 第4 章决策树在软构件检索中的应用 构件复用者复用构件的反馈信息提交后通过验证保存在构件库的构件反馈信息表 中，同时在构件库中还保存有构件的复用历史信息。利用数据挖掘技术，根据构件库的 复用历史信息表和构件反馈信息表建立挖掘数据集，从中挖掘出构件的复用规则，为构 件库的相关人员提供一定的辅助决