（计算机应用技术专业论文）基于蚁群分类算法的构件检索方法研究.pdf

哈尔滨工程大学硕十学何论文 摘要 基于构件的软件开发是解决软件危机的有效途径。在基于构件复用的 软件开发过程中，如何从构件库系统中检索和提取满足用户需求的构件一 直是构件库系统最核心的问题。构件库的检索效率不仅包括对构件本身的 检索效率，而且还包括构件查询者对构件的理解效率。而目前常见构件检 索只是从构件的描述信息来提供对构件的理解，很少根据复用者对构件的 实际复用情况来提供对构件的理解。数据挖掘技术为解决这个问题提供了 可能性。 本文通过对如何利用蚁群算法进行构件复用规则的挖掘进行了探讨， 讨论了构件复用和数据挖掘的相关理论与技术。其中重点讨论了构件检索 理论和蚁群分类算法。在此基础上，尝试利用数据挖掘技术来发现构件的 复用规律，为构件库的复用者理解构件提供了辅助支持。提出一个基于蚁 群分类的构件检索方法，解决了可复用构件复用规则挖掘获取问题。并且 建立了一个基于蚁群算法的构件检索模型。最后通过实验验证了这个模型， 证明了这种方法的可行性与有效性。 关键词：软件；软件复用；构件库；构件检索；数据挖掘；蚁群算法；分 类规则 哈尔滨1 = 程大学硕士学位论文 ；ii 昌 i t- 一- - ；i 置暑宣宣暑i i ；盲i 宣i 昌i ；宣i i 暑宣昌宣； a b s tr a c t t h es o f t w a r ed e v e l o p m e n tm e t h o db a s e do nc o m p o n e n tr e u s ei so n eo ft h e a v a i l a b l ew a y st or e s o l v et h ec r i s i so fs o f t w a r e i nt h ep r o c e s so ft h es o f t w a r e d e v e l o p m e n tb a s e do nc o m p o n e t ，h o wt or e t r i e v ea n de x t r a c tt h em o s ts a t i s f y i n g c o m p o n e n ti nt h el i b r a r yo fc o m p o n e n ti si m p o r t a n ti nc o m p o n e n tl i b r a r y m a n a g e m e n ts y s t e m t h er 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 y i 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 t a l s oi n c l u d e st h e u n d e r s t a n d i n go ft h ec o m p o n e n t h o w e v e r , t h eg e n e r a lc o m p o n e n tr e t r i e v a l s 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 nf o ru n d e r s t a n d i n gt h ec o m p o n e n t ，b u t s 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 t r 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 g t e c h n o l o g yp r o v i d e sa f e a s i b l em e t h o df o rt h 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 fa n tc o l o n ya l g o r i t h mt om i n e r u l e so fc o m p o n e n tr e u s ei sd i s c u s s e d f i r s t l y , t h et h e o r ya n dt e c h n o l o g yo f c o m p o n e n tr e u s ea n dd a t am i n i n ga r ed i s c u s s e d e s p e c i a l l y , t h et h e o r yo f c o m p o n e n tr e t r i e v a la n dt h ea n tc o l o n yc l a s s i f i c a t i o na l g o r i t h ma r ed i s c u s s e d s e c o n d l y ，b a s e do nt h ew o r k ，d a t am i n i n gt e c h n o l o g yi su s e dt od i s c o v e rt h er u l e o fc o m p o n e n tr e u s e t h er u l ep r o v i d e sa u x i l i a r yd e c i s i o ns u p p o r tt oc o m p o n e n t r e u s e r s t h ec o m p o n e n tr e t r i e v a lm e t h o db a s e do na n tc o l o n yc l a s s i f i c a t i o n a l g o r i t h mi sp r o p o s e di no r d e rt or e s o l v et h ep r o b l e m st h a tt h er e u s er u l e sa r e a c q u i r e d a n da l la 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 v a lb a s e do na n t c o l o n ya l g o r i t h mi sc r e a t e d l a s t l y , t h em o d e lh a sb e e nv e r i f i e dt h r o u g h e x p e r i m e n t ，s 0t 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 sb e e np r o v e d k e y w o r d s ：s o f t w a r e ；s o f t 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 t r e t r i e v a l ；d a t am i n i n g ；a n tc o l o n ya l g o r i t h m ；c l a s s i f i c a t i o nr u l e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：絮瘸一 日期：硼，年弓月仁日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。啥尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。m h , 1 - 本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 留在授予学位后即可 口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关 作者( 签字) ：专塘 日期：砷年；月肛日 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 课题的研究背景及意义 随着计算机应用的逐步扩大，软件的需求量迅速增加，规模也日益扩大， 这种现状一方面带来了软件的复杂程度的增加和程序代码的几何级增长，最 终导致软件开发成本增加，开发周期延长，产品的质量不高；而另一方面， 已经积累的一些优秀成熟的软件产品却没有得到充分的利用 1 】。为了解决这 些问题，必须真正实现软件的工业化生产方式。而基于软件复用的软件开发 被认为是有效提高软件生产率，缩短软件产品交付时间和提高软件质量的新 途径f 2 】。目前，软件复用技术的己成为软件工程界的热f - j 石j t 究对象。 软件复用本质上是运用现存软件系统的产品或工程知识构造新的软件系 统，在软件开发中避免重复劳动。其出发点是以已有的工作为基础，充分利 用过去应用系统开发中积累的知识和经验，从而将丌发的重点集中于应用的 特有构成成分i 引。 随着面向对象和软件复用技术的发展，软件构件技术得到了越来越多的 重视和应用。所谓软件构件( s o f t w a r ec o m p o n e n t ) 是指可被用来构造其他软 件的软件组成成份【4 】。随着对构件理解的深入，构件的概念己经不再局限于 源代码构件，而是延伸扩大到软件生产过程中任何活动所产生的制成品的复 用，如项目计划、可行性报告、需求定义、分析模型、设计模型、详细说明、 源程序、测试用例等i5 j 1 6 j 。 然而，在实际的开发中，软件的复用程度并不理想。软件复用面临一个 矛盾，一方面存在大量的可复用构件，另一方面复用者却很难找到真正需要 的构件。因此就要求必须对构件库进行有效的组织和管理，这直接关系到复 用实践的成功与否1 7 j 。 哈尔滨：r = 程大学硕十学何论文 1 2 国内外研究现状 针对不同的构件描述形式，研究人员已提出了许多相应的检索方法。例 如a n d y 即p o d g u r s k i 等人针对构件的行为表示提出的基于构件行为采样的检 索【8 】；a m ym o o r m a n n 等人针对构件的形式化规格说明提出的基调匹配【明( 接 口规约) 和规约匹配w ( 功能规约) 。目前，构件的刻面描述是一种正逐步得到 重视与应用的描述方法，r e b o o t t l 、n a t o 1 2 1 提出的构件分类方法都是基 于刻面【1 6 】的。青鸟构件库f 1 3 】的构件也是采用以刻面分类为主，多种分类模式 相结合的方法对构件进行分类描述的f l2 1 。 其中，r e b o o t ( r e u s eb a s e do no b j e c t o r i e n t e dt e c h n i q u e s ) 是一个包括 储存可复用构件的数据库和一组产生、认证、插入、提取、评价和适配可复 用构件的环境。在对构件进行分类时它采用了刻面分类策略，但是它的刻面 分类模式主要针对的是源代码级别的构件，不能描述粒度较大、结构较复杂 的构件( 如模式、框架) l l 。 n a t o ( n o r t h a t l a n t i ct r e a t yo r g a n i z a t i o n ) 提出了一种刻面分类模式，其中 的刻面不必彼此独立或适用于所有的构件。因此在对一个构件进行分类时， 未必用所有的刻面来描述。刻面术语之间或者没有关系或者是同义词关系， 术语空间是非结构化的【1 3 】1 1 4 】。 a g o r a 是c m us e i 开发的一个构件搜索引擎。a g o r a 通过对w e b 页面的 搜索来获取构件u r l 等相关信息，采用和普通搜索引擎相同的方式管理构件 信息。a g o r a 搜索的构件种类有限，由于构件模型的差异，对j a v a a p p l e t 和 a c t i v e x 的搜索效果较好，而对其他种类的构件搜索效果较差。而且构件的 描述信息和分类信息不够充分。缺乏构件功能的语义描述信息，复用者只能 通过方法，事件和属性名称进行检索，不便于用户准确定位和使用构件。库 中构件的唯一性和存在性也得不到保证。 c o d e b r o k e r 是美国c o l o r a d o 大学所开发的一个构件库原型，其特色是构 件库与源程序编辑工具实现无缝集成，为用户提供主动检索服务。c o d e b r o k e r 存储的构件是j a v a 的类和方法，辅助j a v a 程序员的开发。系统通过三个a g e n t 实现组件的主动检索。c o d e b r o k e r 的检索条件完全依赖于用户在编写程序过 2 哈尔滨工程大学硕+ 学位论文 程中的文本输入，查准率较低。为此，c o d e b r o k e r 提供了一套构件过滤机制 帮助用户快速删除不相关的构件。 此外，国内对构件库的研究也有了相应的成果。其中，以北京大学的青 鸟工程为软件复用及相关技术的研究工作水平的代表。青鸟工程在“九五”期 间开发了基于异构平台、具有多信息源接1 3 的应用系统集成( 组装) 环境青鸟 i i i 型( j b 3 ) 系统。在相应构件模型的基础上，建立了青鸟构件库数据模型，并 与其它c a s e 工具相结合，支持对构件的描述( 使用青鸟构件描述语言 j b c d l 、分类、管理、存储、检索和复合，满足了基于“构件构架”复用的 软件开发过程的需要【l 引。 1 3 论文研究的主要工作 在构件复用过程中，构件的有效管理和检索是构件复用成功与否的关键 技术之一。尽管对构件库的检索主要借助于数据库管理系统完成，但与数据 库检索不同的是构件库的检索不仅应该能够高效检索出相关的构件集，关键 是如何使复用者快速地理解所检索到的构件，从而在这个构件集中找到自己 的真正所需。由此可见，构件库的检索效率不仅包括对构件本身的检索效率， 还应包括构件复用者对构件的理解效率。复用者对于构件的理解，一方面通 过浏览构件库中的构件描述信息准确地理解构件的功能性以及非功能性指 标：另一方面，在构件的复用历史数据和复用者复用构件的反馈数据中，隐 含着大量事先不知道的但又潜在的有用信息。如何从相关数据中找出这些潜 在的有用信息，使复用者能够从其它复用者复用构件的角度来理解构件，从 而了解所关注的构件在实际应用方面的信息，这是一般的构件检索系统所不 能提供的。数据挖掘技术可以从数据库或数据仓库以及其它各种数据库的大 量各种类型数据中，自动抽取或发现有用的模式知识i l8 1 ，从而正好能够满足 这一需求。本文尝试采用数据挖掘技术中的分类方法，从构件的描述信息和 复用者复用构件的反馈信息出发建立挖掘数据集，提出一个将数据挖掘技术 应用于构件检索管理中的应用模型。根据特定的挖掘数据，采用数据挖掘中 的分类方法挖掘隐含在其中的信息，以便为构件库系统的相关人员提供辅助 决策支持。从而提高构件库系统的管理水平和构件复用水平，为复用的成功 3 哈尔滨丁程大学硕十学位论文 提供技术保障。 本文研究的主要内容包括如下几个方面。 ( 1 ) 讨论软件复用理论和数据挖掘技术，针对传统构件检索的局限性， 尝试采用蚁群算法进行数据挖掘来发现构件复用规则，并将其应用到构件检 索中，为构件库的使用人员提供辅助决策支持； ( 2 ) 结合应用，建立一个基于蚁群分类的构件检索应用模型，并给出其 处理过程； ( 3 ) 验证这个应用模型，证明这种方法的可行性与有效性。 1 4 论文组织结构 本文探讨了数据挖掘中的蚁群分类方法在构件检索中的辅助决策支持， 文章内容组织如下所示。 第1 章绪论。介绍课题的研究背景、研究现状，提出本文的研究目标； 第2 章构件及其相关技术。介绍构件，以及构件检索技术； 第3 章数据挖掘中的分类技术。介绍数据挖掘分类技术、各种分类方法 以及各自的优缺点； 第4 章基于蚁群分类的构件检索。提出一种基于蚁群分类的构件检索方 法，给出检索模型。并且，通过实例对模型进行验证，证明了这种策略的可 行性与有效性。 4 哈尔滨工程大学硕十学位论文 第2 章构件及其检索方法的相关技术 2 1 构件定义与特点 构件是指应用系统中可以明确辨识的构成成分。而可复用构件是指具有 相对独立的功能和可复用价值的构件。一般来说，只要是软件系统中可以明 确识别的、可被他人复用的成分，都可以称为构件【2 0 1 。 从构件本身的特征来说，构件是可重用的、自包含的、独立于具体运用 的构件对象模块。构件作为系统的一个特定的功能单位，主要由四部分来组 成：构件标识符、构件说明、构件体、接口【2 1 】。把构件说明和构件体分开的 原因是考虑到同一个构件说明可以由不同的程序设计语言来实现。即使同一 个构件也可以有多个不同语言实现的构件体。构件的接口不仅要提供外部物 理实现接口，而且还要提供一个外部逻辑接口，外部逻辑接口是给用户提供 一个非形式化的该构件的功能描述，这样更能方便用户了解和使用构件。构 件模型是关于开发可重用构件和实现构件之间相互通信的一组标准的描述。 有了构件及构件模型的出现，使得软件开发者可以快速地构造出所需的应用 软件。以便减少软件开发所需的经费、缩短开发周期和提高效率，并且可以 在重用已有开发的基础上得到高质量的、完全可靠的软件产品。 软件构件应该具备如下所示几个特征f 2 刭。 ( 1 ) 自描述构件必须能够识别其属性、存取方法和事件，这些信息可以 使开发环境将第三方软件构件无缝地结合起来； ( 2 ) 可定制提供一个典型的图形方式环境，软件构件的属性只能通过控 制面板来设置； ( 3 ) 可集成构件必须可以被编程语言直接控制。构件也可以和脚本语言 连接或者从代码级访问构件的环境连接，这个特性使得构件可以在非可视化 开发项目中使用； ( 4 ) 连接机制构件必须能产生事件或者具有让程序员从语义上实现相互 哈尔滨下程大学硕士学位论文 i im 连接的其它机制。这意味着程序员可以很容易地向按钮添加代码，使点中按 钮就可以影响其它构件的动作。 由构件的特点可以看出，都强调了构件的独立性、互换性和功能性，即 构件不依存于某一个系统，它可以被相同功能的构件所替换，并且具有实际 的功能意义。 2 2 构件存储方式 构件库的构件存储系统可以采用多种方式：面向对象数据库o o d b s m s ， 关系数据库r d b m s 和文件系统f i l e s 2 3 1 。 o o d b s m s 具有存储数据量大、易于维护、易于扩充、易于格式动态变 动等优点，但它目前尚无成熟产品，尤其在标准化和性能上令人不满意，并 且有些构件又不支持面向对象技术，因而o o d b s m s 不能满足构件库对构件 的存储要求。 相比之下，关系数据库i b m s 具有储存和管理大量数据的高效性、理 论的严密性和技术的成熟性，它不仅可以支持存储不同的数据类型和复杂的 数据结构，而且能够表示结构化的数据，可以方便地表达出数据之间的关系， 并且还可以提供多种线索进行查询，具有很高的查询效率，所以是构件存储 系统的首选。但是，在实际应用中，构件的结构极其复杂，存在形式多种多 样，且构件的体积可能很大，这与关系数据库对所保存的数据项一般都有尺 寸限制，不宜过大的要求不相符合。所以，仅用r d b m s 来存储构件显然是 可能的，但又是不够的。 另一种可用来存储的系统是文件系统f i l e s 。f i l e s 系统的存储特点是存储 容量大，对存储的数据体积无限制，且可以存储多种不同形式的构件。这点 刚好符合对构件存储的要求。目前，已也有许多软件产品都采用了文件系统 来存储构件，如b o r l a n d 公司的d e l p h i 和p o w e r s o f t 公司的p o w e r b u i l d e r 的 对象仓库等，它们就是使用的f i l e s 文件系统。但f i l e s 不利于大量数据的存 储，因为它的查询效率低，缺少有效快捷的检索途径，查找构件不方便。同 时，由于文件系统操作的基本单位是文件，文件与文件之间不能建立复杂关 系。显然，这与对构件检索高效率的要求不符，同样也与对在构件之间建立 6 哈尔滨二i ：程大学硕十学何论文 各种关系的要求不符。因此，文件系统f i l e s 也不完全符合对构件存储的需要。 从上述的分析可以知道，数据库主要适合存放具有复杂结构和相互关系 并且对检索效率有较高要求的数据，而文件系统适合存放对检索效率没有很 高要求，但尺寸较大的数据。由此可见，任何一种单一的存储方式都不能高 效、灵活地储存和管理构件，因此在实际应用中往往是结合多种方式来实现 构件的存储。 2 3 构件的分类与检索 构件复用技术的关键问题就是构件的检索问题：如何在库中找到合适的 构件用于构造目标应用系统。构件的分类和检索一直是一个制约构件复用的 主要因素。 2 3 1 构件分类方法 对大量构件进行分类有三个好处，便于组织管理、方便查询和辅助理解。 构件分类是建立和维护构件目录信息的活动，构件的检索方法依赖于构件的 表示和分类。从不同的角度可以对分类模式进行不同的划分，h m i l i 根据构 件检索的复杂度将构件分为基于文本的、基于词法描述子的和基于规约的描 述方法三类【2 4 1 ；w f r a k e s 从构件的表示出发将现有构件表示方法分为人工智 能分类方法、超文本分类方法，以及信息科学分类方法三类【2 5 1 。基于人工智 能的构件分类方法又可以细分为基于构件行为的分类方法，基于知识库的构 件分类方法和基于神经网络的构件分类方法等。信息科学方法在实际构件库 的项目中应用较为成功，一般分为基于受控词汇表( 如枚举、刻面) 分类和基 于不受控词汇表( 如关键词) 分类两种形式。在信息科学分类方式中，基于受 控词汇表的分类方法为研究的重点，它的主要特点就是用来进行分类检索的 词汇表是一个有限集合，主要包括枚举分类方式、刻面分类方式和关键词分 类方式。基于不受控词汇表的分类方法，一般是对构件描述信息的全文进行 处理的方式，如从正文抽取术语，词汇表是一个无限集合。对几种常用分类 方式【2 6 】【2 7 】【2 8 1 的简要介绍以下所示。 7 哈尔滨工程大学硕十学位论文 1 枚举分类 通常将一个被关注的领域严格划分为若干不相交的子领域，构件按照某 些性质分成若干大类，每个大类又可分为若干小类，经过若干次分解形成构 件的层次结构，实际的构件位于层次结构的最低层，其它层次则表示构件所 属的父类或祖先类。该方法对问题域进行清晰的高度结构化的划分，概念清 晰，易于理解和使用。但是该方法比较严格，通常只提供一种视角，使得分 类模式难以伴随领域的变化而演化，所能够表示的关系也受到限制。枚举结 构的创建者必须具有完整的领域知识，在建立层次结构之前，必须进行领域 分析以寻找合适的供分类的性质，因此建立恰当的枚举结构需要花费相当的 代价。 2 层次分类 这种分类方法的本质是层次型的一先把所有的构件划分为一些高层的 ( 大的) 种类，再把每个种类划分为一些层次较低的( 较小的) 种类，层次结构的 最低层就是构件。层次结构的中间层实际上是一组构件所属的种类。使用者 在寻找构件时从高到低逐层判断自己要找的构件应该属于哪一类，可以较快 地收敛到所要寻找的目标。这类方法的主要缺点是：按照某种标准划分构件的 种类可能只适合一部分构件，而另一些构件可能不适合按这种标准分类。 3 关键词分类 每个构件以一组与之相关的关键词编目，用主题进行描述，主题多为短 语。每个主题下可有多个描述子，多为单词。查询者给出关键词来描述所需 的构件。该方法能够根据构件文档自动抽取术语补充到术语空间中，可节省 人力。其难点在于抽取术语的精确度，例如出现频率高的术语不一定是描述 构件的本质术语。对术语的抽取一般需要人力进行判断，工作量较大。 4 属性值分类 该方法为所有构件定义一组属性，每个构件都用一组“属性值 进行描 述，开发人员通过指定一组“属性值”，对构件库进行检索。“属性值”描述 方法与下面将要介绍的刻面描述方法非常类似，不同的是刻面对应的术语空 间是有限的不定空间( f i n i t ea n di n d e f i n i t et e r ms p a c e ) ，而属性的值域往往是 无限的确定空间( i n f i n i t ea n dd e f i n i t ev a l u es p a c e ) ，刻面的选择也远比属性要 8 哈尔滨t 稃大学硕士学位论文 慎重，刻面一般不超过7 个，而“属性值”法没有限制，属性没有优先级， 刻面则可设置优先级，“属性值”方法中不使用同义词功能，而刻面的术语 可定义同义词关系。 5 刻面分类 该机制是将术语置于一定的语境中，并通过特定的反映构件本质特性的 视角( 刻面) 进行精确的描述。构件管理者通过将刻面与对应的术语相联结， 可以在构件间建立复杂的联系。与一般的分类策略相比，刻面分类策略更易 于修改，更富有弹性，因为对一个刻面的修改不会影响到其它的刻面，同时 每个刻面对应一个结构化的术语空间，避免了一般的关键词分类策略的杂乱 无章，使得对关键词的管理更为方便和有序。 在上述各种分类模式中，刻面分类方法从若干不同的维度描述复杂对象， 弥补了关键词分类策略的杂乱无章，结构上比属性值分类更为合理，也没有 枚举分类方法开销大，并且容易扩展，具有枚举、属性值和关键词分类几种 方法的优点。也正是因为它的诸多优点，它被n a t o 组织采纳和推荐使用， 是目前使用最为广泛的一种分类模式。 2 3 2 构件检索方法 构件的检索机制是构件库系统的核心，本质上，构件检索是寻求区别问 题空间到解空间的一种映射关系。构件检索方法主要归结为三类，基于外部 索引的检索、基于内部静态索引的检索和基于内部动态索引的检索。 1 。基于外部索引的检索 比如常见的关键词检索，刻面检索等。关键字检索是给出术语空间中的 术语，查找和该术语相关的构件。如果在直接与该术语相关的构件中找不到 实用的构件，还可以参见其他相关术语下的构件。这种方法也不复杂。其缺 点是该方法要求复用者对构件库的术语空间有一定的了解。当然，可以通过 扩大词汇量来解决这个问题。然而，建立一个完善的词汇表是一个长期的过 程。同时维护这样一个词汇表也不容易。刻面检索是最常用的软件构件检索 方法，该方法是由p r i e t o d i a z 等人首次提出的。后来，该方法又被其他人作 9 哈尔滨工程大学硕士学何论文 i i 了改进。其基本思想是抽取软件构件的某些属性( 即刻面) 来作为软件构件的 描述符，如软件构件的动作以及构件操纵的对象等。构件的分类和检索是通 过对构件按刻面赋值( 关键字) 来实现的。改进后引入了关键词和同义词典以 提高刻面方法的分类和查询效率。这种方法的优点是，按符合人们的抽取习 惯进行属性分类。但是由于这种方法是建立在领域分析产生的限制词汇表之 上的，因为构件按刻面赋值需要手工完成，领域词汇也需要手工产生，因此， 这种方法代价较大。另外，由于限制词汇表的使用会为不熟练用户带来不便。 2 基于内部静态索引的检索 根据构件自身的结构元素进行检索构件，其中构件规约的语法和语义匹 配、结构匹配等是主要方法。到目前为止，规约的语义匹配已经研究的比较 充分，语义匹配也形成了一般性的方法。 3 基于内部动态索引的检索 利用构件的可执行特性来进行检索，比如利用构件的输入与输出空间来 检索所需的构件，基于行为的检索是目前这类检索中常见的方法。由于实际 应用的复杂性，基于行为的检索目前只停留在研究阶段。 2 3 3 构件检索过程模型 构件的检索模型如图2 1 所示。首先，复用者通过对实际的问题需求进行 分析，将其形成查询条件。构件库中的构件根据构件的描述模型，从构件的 功能出发，组织特定领域的接口列表，对接口进行描述并建立索引。然后， 由匹配算法对查询条件和构件描述进行比较，找出精确匹配或近似匹配的构 件。图2 1 中复用者对问题的理解以及对需求的表达依赖于复用者的知识和经 验。而匹配算发的精确性和效率则是构件库考虑的重点。 1 0 哈尔滨丁程大学硕士学位论文 图2 1 构件检索过程模型 2 3 4 构件分类检索的评价标准 一种构件分类表示和检索方法提出以后，作为分析比较的依据，需要有 一个标准来考察该分类方法。分类方法的评价标准包括，成本、可理解性、 检索效率。分类成本包括生成、维护分类方案、升级数据库的费用，可由总 费用与总构件数之比来计算。可理解性是显示分类方法对用户理解可复用构 件的影响度。一般分类方法不能过于复杂，否则会增加理解的难度，阻碍用 户检索。分类方法的关键指标是检索效率。检索效率是指用来度量一种检索 方法在构件库中找到相关构件匹配程度，即检索的结果包括有用的和无用的 构件信息的数量，通常使用查全率和查准率进行度量。所谓查全率是指具备 用户指定特征的构件都能够反馈给用户挑选。所谓查准率是指尽量反馈精确 具备用户指定特征的构件，不相关的构件不要反馈给用户，以减小用户筛选 适合自己需要构件的工作量。 2 4 构件复用过程 复用者要想对构件的进行复用必须包括三个步骤，检索构件、理解构件、 以及接受构件。具体含义如下。 ( 1 ) 检索构件。根据用户需要找到仅需做最小修改的复用构件； ( 2 ) 理解构件。清楚构件的功能及其细节，以便进行修改和扩充，最终 1 1 哈尔滨下挥大学硕士学位论文 达到复用的目的； ( 3 ) 接受构件。将构件的实现部分加到自己的系统中，因此实现软件复 用。 在这三步中检索构件是最为关键的一步，它直接影响到用户能否对构件 进行复用。 一个软件开发者在系统开发的过程中，决定是否采用可复用构件取决于 复用成本和重新开发成本的比较。如果满足如下条件， 复用成本 开发成本 那么就决定了他会选择复用构件以减少系统开发的成本。这里将复用成 本理解为如下的关系， 复用成本= 检索成本+ 理解成本+ 修改成本+ 使用成本 其中，使用成本指的是从商业构件库中购买构件的成本。 针对不同的构件描述形式，研究人员已提出了许多相应的检索方法，大 大降低构件检索的成本，促进了构件的复用。然而这些方法都往往忽略了构 件的理解成本，而r i g ( r e u s el i b r a r yi n t e r o p e r a b i l i t yg r o u p ) 1 ) l , l j 认为，软件复 用中的理解问题是影响复用成功的一个关键问题。也就是说，在实际的构件 复用过程中，复用者不仅应该能够高效检索出相关的构件集，关键是如何使 复用者快速地理解所检索到的构件，从而在这个构件集中找到自己的真正所 需，这是一个复杂的决策过程，一般都依赖于复用者的复用经验以及通过浏 览构件描述信息对构件的理解和主观评判。 2 5 本章小结 本章主要介绍的是构件及构件检索的相关理论和技术。首先介绍了构件 的定义及其特征，分析了构件的存储方式。然后，描述了构件的分类，检索 及其检索过程模型。讨论了构件分类检索的评价标准。最后，总结了构件复 用过程中的涉及到关键问题。 1 2 哈尔滨工程大学硕十学位论文 第3 章数据挖掘中的分类技术 信息科学的发展引起数据的高度膨胀，如何有效地处理大规模的数据信 息，得出有用知识，便成为目前值得关注的问题。数据挖掘是从大规模数据 中发现非平凡模式，正是应此要求迅速发展起来的- i - j 科学。本章简要介绍 了数据挖掘及分类技术，并对其中的决策树分类作较为详细的介绍。 3 1 数据挖掘概述 数据挖掘就是从存放在数据库、数据仓库或其他信息库中的大量数据中 挖掘有趣的知识的过程，而这些知识是隐含的、事先未知的潜在有用信息。 它可以使用智能的方法提取数据模式，有趣的模式可提供给用户或者作为新 的知识存放在知识库中p 。数据挖掘是- i - j 交叉学科，它涉及的学科领域包 括数据库技术、人工智能、机器学习、神经网络、统计学、模式识别、知识 库系统、知识获取、信息检索、高性能计算和数据可视化等。数据挖掘的成 果可以用在信息管理、过程控制、科学研究、决策支持等许多方面【3 2 1 。 数据挖掘过程是一个多次的循环反复的过程，每一个步骤一旦与预期目 标不符，都要回到前面的步骤，重新调整，重新执行。其主要步骤【3 3 】如下。 ( 1 ) 确定业务对象。清晰地定义出业务问题，认清数据挖掘的目的是数 据挖掘的重要一步。挖掘的最后结构是不可预测的，但要探索的问题应是有 预见的，为了数据挖掘而数据挖掘则带有自目性，是不会成功的。 ( 2 ) 数据准备。数据准备过程分为数据选择，数据预处理和数据转换三 步，每一步具体说明如下。 数据选择。搜索所有与业务对象有关的内部和外部数据信息，并从中 选择出适用于数据挖掘应用的数据； 数据预处理。研究数据的质量，为进一步的分析做准备。并确定将要 进行的挖掘操作的类型： 数据转换。将数据转换成一个分析模型。这个分析模型是针对挖掘算 1 3 哈尔滨t 程大学硕士学位论文 法建立的。建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 ( 3 ) 数据挖掘。对所得到的经过转换的数据进行挖掘。除了完善选择合 适的挖掘算法外，其余一切工作都能自动地完成。 ( 4 ) 结果分析。解释并评估结果，其使用的分析方法一般根据数据挖掘 操作来确定，通常会用到可视化技术。 ( 5 ) 知识同化。将分析所得到的知识集成到业务信息系统的组织结构中 去。 3 2 数据挖掘中的分类技术 3 2 1 分类的基本概念 分类是数据挖掘中一项非常重要的任务，分类的目的是提出一个分类函 数或分类模型1 3 4 1 ( 分类器) ，该模型能将数据库中的数据项映射到给定类别中 的某一个。可以举一个简单的例子，信用卡公司的数据库中保存着各持卡人 的记录，公司根据信誊程度将持卡人记录分成三类，良好、一般、较差，并 且类别标记已赋给了各个记录。分类分析就是分析该数据库的记录数据，对 每个信誊等级做出准确描述，如“信誊良好的客户是指那些年收入在5 万元以 上，年龄在4 0 多j 5 0 岁之间的人士”，然后根据这些描述对其它具有相同属性的 数据库记录进行分类。 分类的过程可分为以下两步。 ( 1 ) 建立一个模型，描述预定的数据类或概念集； ( 2 ) 使用模型进行分类。 3 2 2 分类规则挖掘 分类规则挖掘是数据挖掘的一个重要研究领域。在分类规则挖掘中人们 通过对历史或已知数据的分析，获得对未来或未知情况判断和预测的依据。 1 4 哈尔滨工程大学硕十学何论文 暑暑宣昌置鼍昌宣；暑宣暑宣i ；暑置；昌暑i 一 - - i 1 1 分类规则挖掘的概念 分类就是判断某一事物或对象的类别。其实人们每时每刻都在为周围的 事物进行着分类。他们所做的任何一个判断都是基于分类。只是日常判断所 用的知识大多来自于经验数据。从周围环境、从经验数据获得决策规则的能 力，无论对自然界还是对人类来说都是很重要的。在人工智能领域，这种能 力可通过归纳学习获得。分类规则挖掘也是基于归纳学习的思想，通过研究 已知其类别的诸多对象，发现对象属性与其类别间的关系，也即分类规则。 分类规则挖掘是数据挖掘最重要的研究领域之一。分类规则挖掘就是研究一 组已知其类别的数据对象( 训练数据集) 的属性与其类别间的关系，发现其规 律( 分类规则) ，以用来对未知类别的数据对象做出类别判断。 2 分类规则挖掘的研究内容 分类规则挖掘过程的主要环节是挖掘出可以利用的决策规则、数量( 连续) 属性的离散化与属性约简，即分类规则的提取。因此，当前分类规则挖掘的 研究主要围绕着这三个方面。 第一个方面，采用各种先进技术挖掘出简明、准确、易于理解的决策规 则。目前常用的分类规则挖掘研究方法有这几种，基于决策树的分类规则挖 掘方法，基于遗传算法的分类规则挖掘方法，基于神经网络的分类规则挖掘 方法，遗传算法与神经网络相结合的方法，基于粗糙集理论的分类规则挖掘， 基于模糊集的分类规则挖掘，粗糙集与遗传算法相结合的分类规则挖掘等等。 第二个方面，围绕属性离散化展开的研究，包括数量属性的离散化，以 及最新的符号属性值的划分。 第三个方面，围绕属性约简的研究。这几个方面的研究不能截然分开， 通常后两个方面的研究是第一个方面研究的基础，并且经常交叉研究。 3 。分类规则挖掘基本步骤 分类规则挖掘的基本步骤主要有两步，首先，建立一个描述已知数据集 类别或概念的模型。然后，利用所获得的模型进行分类操作。 ( 1 ) 建立一个描述己知数据集类别或概念的模型。如图3 1 所示，该模型 是通过对数据库中内容的分析而获得的。每一数据行都可认为是属于一个确 定的数据类别，其类别值是由一个属性描述( 被称为类别标记属性) 。分类学 哈尔滨工程大学硕士学位论文 i i 习方法所使用的数据集称为训练样本集合，因此分类学习又可称为监督学 o e a m i n gb ye x a m p l e ) ，它是在己知训练样本类别情况下，通过学习建立相应 模型。而无监督学习则是训练样本的类别与类别个数均未知情况下进行的通 常分类学所获得的模型可以表示为分类规则形式、决策树形式或数学公式形 式。例如，给定一个顾客信用信息库，通过学习所获得的分类规则可用于识 别客户是否是具有良好的信用等级或一般的信用等级。分类规则也可用于对 未知( 所属类别) 的数据进行识别判断，同时也可以帮助用户更好地了解数据 库中的内容。 图3 1 数据分类过程中的学习建模 ( 2 ) 利用所获得的模型进行分类操作。如图3 2 所示，首先对模型分类准 确率进行估计。对于一个给定数据集所构造出模型的准确率可以通过由该模 型所正确分类的( 测试) 数据样本个数所占总测试样本比例得到。对于每一个 测试样本，其已知的类别与学习所获模型的预测类别进行比较。若模型的准 确率是通过对学习数据集的测试所获得的，这样由于学习模型倾向于逼近训 练数据，从而造成对模型测试准确率的估计过于乐观。因此需要使用一个测 试数据集来对学习所获模型的准确率进行测试工作。 1 6 哈尔滨t 程大学硕十学位论文 3 2 3 分类方法 图3 。2 数据分类过程中的分类测试 数据库中隐藏着许多可以为商业、科研等活动的决策提供所需要的知识。 分类可用来抽取能够描述重要数据集合的模型。分类方法用于预测数据对象 的离散类别。分类是数据挖掘的一个主要方法，人们在分类这个领域做了大 量的工作，获得了很多行之有效的方法，以下是一些常用算法的简单介绍。 1 决策树分类 基于决策树【3 5 】【3 6 】的分类方法是一种监督学习的方法，树的数量由分类的 精度和树的大小决定。决策树分类采用自顶向下的递归方式，在决策树的内 部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在 决策树的叶结点得到结论。所以从根到叶结点的一条路径就对应着一条合取 规则，整个决策树就对应着一组析取表达式规则。 决策树分类【3 7 】是以实例为基础的归纳学习算法。它着眼于从一组无次 序、无规则的事例中推出决策树表示形式的分类规则。它采用自顶向下的递 归方式，在决策树的内部结点进行属性的比较并根据不同属性值判断从该结 点向下的分支，在决策树的叶结点得到结论。所以，从根到叶结点的一条路 径就对应着条合取规则，整棵决策树就对应着一组析取表达式规则。 2 贝叶斯分类 贝叶斯分类方法【3 8 】是基于贝叶斯网络的统计学分类方法。贝叶斯网络是 1 7 哈尔滨工程大学硕士学位论文 一个带有概率注释的有向无环图，图中的每一个结点均表示个随机变量， 图中两结点间若存在着一条弧，则表示这两结点相对应的随机变量是概率相 依的，反之则说明这两个随机变量是条件独立的。网络中任意一个结点x 均 有一个相应的条件概率表( c o n d i t i o n a lp r o b a b i l i t yt a b l e ，c p t ) ，用以表示结点 x 在其父结点取各可能值时的条件概率。若结点x 无父结点，则x 的c p t 为其 先验概率分布。这里，贝叶斯网络的结构及各结点的c p t 定义了网络中各变 量的概率分布。 应用贝叶斯网络分类器进行分类主要分成两阶段。第一阶段是贝叶斯网 络分类器的学习，即从样本数据中构造分类器，包括结构学习$ 1 1 c p t 学习。第 二阶段是贝叶斯网络分类器的推理，即计算类结点的条件概率，对分类数据 进行分类。这两个阶段的时间复杂性均取决于特征值间的依赖程度，甚至可 以是n p 完全问题，因而在实际应用中，往往需要对贝叶斯网络分类器进行简 化。根据对特征值间不同关联程度的假设，可以得出各种贝叶斯分类器。 使用贝叶斯网络分类可以预测类成员关系的可能性，对不确定性知识进 行推理。例如，医生看病，根据病人的症状，判断病人是否得了某种疾病， 往往是一种不确定的推理( 带概率的推理) ，多数情况下没有百分之百的把握。 运用贝叶斯网络进行推理，可以达到较好的效果。 3 基于神经网络的分类 神经网络1 3 9 】最早是由心理学家和神经学家提出的，旨在寻求开发和测试 神经的计算模拟。粗略地说，神经网络是一组连接的输入输出单元，其中每 个连接都与一个权相联。在网络学习阶段，通过调整权重来实现输入样本与 其相应( 正确) 类，利用预测输入样本的正确类标号来学习。由于单元之间的 连接，神经网络学习又称连接者学习。鉴于神经网络学习时间较长，因此它 仅适用于时间容许的应用场合。此外它们还需要一些关键参数，如网络结构 等。这些参数通常需要经验才能有效确定由于神经网络的输出结点较难理解 因而受到用户的冷落，也使得神经网络较难成为理想的数据挖掘方法。 神经网络的优点包括其对噪音数据的高承受能力，以及它对未经训练的 数据的分类能力。此外，最近已提出了一些由训练过的神经网络提取规则的 算法，这些因素推动了神经网络在