（计算机应用技术专业论文）信息检索系统的算法库研究.pdf

中文摘要 伴随着万维同的发展，越来越多的人开始以网络进行生活、工作和学习。信 息检索已经构成网络的一个不可或缺的因素。在进行信息检索时，用户希望能够 检索出所有感兴趣的信息，这就需要滤掉不相关的信息，从而获得最有价值的信 息。在这种情形下，w e b 数据挖掘应运而生。而挖掘算法种类繁多，每种算法 都有其适用的情形。如何选择合适的算法进行数据处理成为人们面临的问题。 本文针对上述问题及挖掘算法应用的普遍性，构建了算法库系统。该系统旨 在为信息检索提供算法支持。我们给出了算法调用和管理的框架。通过映像和元 对象协议实现算法库的核心功能和系统控制功能的分离。这样，可以通过添加新 的元对象来引入新的调用机制，而基本算法保持稳定。从而使系统具有良好的扩 展性。 在算法的选取中，考虑项目所要处理的数据特点，针对当前x m l 文档结构 聚类算法的一些不足，提出采用段匹配的概念来计算两棵x m l 文档树中的路径 相似性。在整个聚类过程中，算法还把一组相关文档与一个x m l 聚类代表相关 联，并给出了聚类代表的计算方法。进而，通过比较聚类代表，发现新的聚类时 更新聚类代表来完成文档的聚类。 在上述工作的基础上，设计和开发了一个图形界面化算法库原型体统来实现 算法的示例调用和管理。 关键词；w e b 数据挖掘文档聚类文档分类信息检索映像元对象协议 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to f w o r l dw i d ew e b ，t h ew a yi nw h i c hp e o p l ea c q u i r e u s e f u li n f o r m a t i o nh a sb e e nc h a n g i n gd r a s t i c a l l y m o r ea n dm o r ep e o p l eb e g i nt o m a k eu s eo fw e bt ol i v e , w o r ka n ds t u d y i n f o r m a t i o nr e t r i e v a lh a sb e c o l l l ea l l e v i t a b l ee l e m e n to f t h ew e b w h e ns e c x c h i n gi n f o r m a t i o nw i t hs e a r c he n g i n e ，p e o p l e w a n tt og e tt h em o s tc o n c e r n e di n f o r m a t i o nb ym e a l 略o fd i m i n a t i n gt h ei r r e l e v a n t m o r e o v e r , w h a tt h e yo b t a i ns h o u l db em o s tv a l u a b l et ot h e m a l lt h e s er e s u l ti nt h e b i r t ho fw e bd a t am i n i n g w h e l - e a st h e r e 他s om a n yt y p e so fa l g o r i t h m sa n de a c h o n ea p p l i e st oas p e c i f i cc a s e t oc h o o s et h eb e s to n et op r o c e s s i n gd a t ab e c o m e sa p r o b l e m i nt h ep a p e r , w ed e v e l o pa na l g o r i t h m sl i b r a r y s y s t e mt op r o v i d ea l g o r i t h m s u p p o r tf o rt h ei n f o r m a t i o nr e t r i e v a ls y s t e m ，w h i c hp r o v i d e st h ef r a m e w o r kf o r f u n c t i o nc a l la n dm a n a g e m e n t b a s e do nr e f l e c t i o na n dm e t a - o b j e c tp r o t o c o l ，w e r e a l i z et h es e p a r a t i o no fs p e c i f i cf u n c t i o nc o n c e r n sa n ds y s t e m c o n t r o l l i n go n 嚣 u s i n gm e t a - o b j e c tp r o t o c o l ，w ec a na d dn e wm e t a - o b j e e t si n t ot h i ss y s t e m s u c ha s y s t e mi se a s yt oe x p a n d w h e nc h o o s i n gt h ea l g o r i t h m st ob er e a l i z e d , w ea n a l i z et h ec h a r a c t e r i s t i c so f t h e d a t at ob ep r o c e s s e di no u rp r o j e c ta n dp r o p o s et h ec o n c e p t i o no fs e g m e n tm a t c h i n g a g a i n s tt h ed e f e c t so ft h em e t h o d si ne x i s t e n c e w eu s i n gt h i sc o n c e p t i o nt oc a l c u l a t e t h es i m i l a r i t yb e t w e e nt w o 仃e 鹤t h e ni nt h ew h o l ec l u s t e r i n gp r o c e s s i o n , w ee q u i p e a c hd u s t e rw i i ha nx m lc l u s t e rr c p l - 嚣e n t a t i v e , w h i c hs u b s u m e st h em o s tt y p i c a l s t r u c t u r a ls p e c i f i c so fas e to fx m ld o c u m e n t s a l s ow eg i v et h ea r i t h m e t i cf o r c o n s t r u c t i n gt h er e p r e s e n t a t i v e t h e nc l u s t e r i n gi sa c e n m p l i s h e db yc o m p a r i n gc l u s t e r r e p r e s e n t a t i v e s a n du p d a t i n gt h er e p r e s e n t a t i v e sa ss o o na sl l e wc l u s t e r sa l ed e t e c t e d i na d d i t i o n , t h i sp a p e rd e s c r i b e sag u is y s t e md e v e l o p e db yt h ea u t h o r , w h i c hi s u s e dt od i s p l a yad a m ec a l lp r o c e s s i o nd i r e c t l y k e yw o r d s ：w e bd a t am i n i n g , d o c u m e n tc l u s t e r i n g , d o c u m e n tc l a s s i f i c a t i o n , i n f o r m a l t o nr e t r i e v a l ，r e f l e c t i o n , m e t a - o b j e c tp r o t o c a l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫凄盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文储签名。穹 签字日期：御【) 6 年，月，6 日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘堂有关保留、使用学位论文的规定。 特授权叁鲞盘茎可以将学位论文的全部或部分内容编入有关数据库迸行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 靴做储魏咿彻 签字日期：2 0 ( 1 箨r 月，6 日 导师签名： 签字日期：。( 年月，7 日 第一章引言 1 1 研究背景 1 1 1 问题出现 第一章引言 万维网自诞生以来，迅猛发展，已经成为人类交流的重要媒体、人类数据的 巨大仓库和人类知识的潜在源泉。但是因i n t e m e t 所固有的大容量、开放性、动 态性和异构性等特点，使得i n t e m e t 这个“数字时代的图书馆”并不像真正的图 书馆那样支持有组织的信息管理和检索。伴随而来的一个问题便是面对如此庞大 的分布式信息库，用户怎样才能快速地找到所需要的信息。为了帮助用户检索和 获取网络上的丰富信息，一大批w e b 信息检索系统应运而生。但是限于技术上 的原因，目前大部分w e b 信息检索系统仍然无法完全满足人们对信息检索的需 求。这是因为： ( 1 ) 这类信息检索技术单纯依靠用户输入的关键字来查找信息，存在很大 的信息冗余。 ( 2 ) 每次的检索结果会返回成千上万的记录，没有任何的信息过滤，让人 面对众多的查询结果感到无所适从。一 ( 3 ) 目前的搜索引擎无法记录用户的浏览习惯，这种非智能搜索引擎，一 方面加大了用户查询的操作复杂性，另一方面又因为重复查询而降低了搜索效 率。 。 1 1 2 解决途径 对上述问题的研究形成了网络数据挖掘( w e bd a t am i n i n g ) 【1 】这个新的学 科方向，它涉及到了众多学科领域，如人工智能、概率统计、机器学习、计算复 杂性理论、控制论、信息论、哲学等。这些领域的发展对网络挖掘都起到了积极 的推动作用，其中一个很重要并且最直接相关的领域是机器学习。 机器学习的传统技术聚类和分类是将大量的文档进行分门别类，依据文 档的意义将它们划归为不同的类别，从而可以更好的把握整个文档集合。对于信 息检索，运用聚类分类技术的益处体现在以下三个方面： ( 1 ) 组织检索结果。起初w w w 仅仅是一些主页的无组织的杂乱集合，用户 第一章引言 没有一个访问这个庞大资源的有效入口，为了满足这方面的需求，人们构建了 a l t av i s t a 、i n f o s e e k 、e x c i t e 等大量的搜索引擎。然而这些搜索引擎的检索结果 却不尽如人意，使用者输入一些关键词，一般都会得到成千上万的检索结果，而 起其中大部分页面都是不需要的无关资料。虽然有一些技巧试图给那些有较多关 键词或者罕见关键词的页面赋予更大的权重，却仍然不能保证和用户意图最相关 的页面一定被排在最前面。m a r t ia h e a r s t 等开发了一种称为“s c a t t e r g a t h e r 2 的技术，试图更合理的组织检索结果。这种技术对检索到的结果页面进行聚 类分类处理，按照页面彼此之间的相似程度分为若干组，每组都有一个比较明 确的主题，用户可以迅速地浏览每一组并选择那些和他的目标最相关的组。进而 使得更容易在搜索结果中浏览与查找；更容易以合适地新关键词来细化搜索；使 得每次搜索结果得到充分展示与利用。 ( 2 ) 加速检索过程。自然语言中词形和词义并不是一一对应的，有很多一词 多义和多词义的现象，这种现象使得仅仅依靠关键词的比较不足以获得满意的 检索结果。针对这种现象，d m n a i s 提出了一种称为隐性语义检索( l s i ：l a t 髓t s e m a n t i ci n d e x i n g ) 的算法 3 】，在大规模文本集合中提取出隐含的概念，进而使 用在概念空间中的投影表示文本。检索过程把用户输入的检索项视为一个虚拟文 本，按照同样的方式计算其在概念空间中的投影，将这个虚拟文本和文本库中的 所有文本逐个比较，然后返回那些距离比较小的文本。如果文本库中文本数目过 多，这个过程将是非常耗时的。一种可行的加速方案就是事前对原始文本进行聚 类，把那些近似程度较高的文本分在同一组内，每个组都形成一个中心，检索时 只需要和这些类中心比较就可以了，这会大大加速整个检索过程。 ( 3 ) 个性化信息推送。传统的获取信息的技术中用户是主动方，因此可以称 之为“拉”( p u l l ) ，与之相反的另一种方式则称为“推”( p u s h ) ，由信息发布方 主动地将信息推送给感兴趣的用户。要想快速完成信息分发步骤，就要对用户进 行分类僳类，类中诸用户拥有共同的兴趣。用户的兴趣可以使用用户自己提交 地p r o f i l e ，或者用户访问过的文本集合来描述。文本聚类分类技术可以把用户 分为对不同事物感兴趣地各个小团体。进而，根据用户群的不同访问模式，为用 户提供个性化的页面，开展有针对性的服务，以便更好的满足用户的需求。也可 以通过分析用户的访问模式和倾向，来改进站点的组织结构。 但是由于待处理数据的特点不同，有些噪声大，有些有缺省值，有些分布稀 疏，有些属性间的相关性强，有些属性是离散的而有些是连续值或是混和类型的。 因此不可能存在一种方法能适合于各种特点的数据。例如，b i r c h , ) 算法从算 法的时间和空间复杂度，数据输入顺序的敏感性和聚类效果而言，都被认为是处 第一章引言 理大数据量的好方法，同时，b i r c h 算法结构也易于被转化为并行算法，而且 在执行过程中，可以动态地、交互地利用已有知识进行算法的调节。然而它只能 处理数值型属性。针对k - m e a n s 5 算法对“噪声”和“孤立点”敏感，不能处理 分类属性，不适合发现非凸面形状或大小差别很大的聚类。提出了k - p r o t o t y p e 6 】 算法，该算法不但可以处理数值属性，也可以处理符号属性。但是它对于大数据 集合没有良好的可伸缩性。对于分类方法存在类似的问题，例如，大部分神经网 络和设计样本的统计分类与大部分判定树方法相比，趋向于计算量大。对于描述 型的分类任务，采用规测表示的分类器构造方法就更加有效，而神经网络方法产 生的结果则是难以理解的。 针对w e b 数据挖掘算法应用的广泛性和使用情况的复杂性，本文将构建算 法库系统。这样就可以针对待处理数据的特征来调用库中的相应算法进行数据的 处理。同时考虑到系统扩展性，我们将基于映像和元对象协议来分离系统的关注 点，从而使得系统核心功能与系统控制功能相分离，便于系统的维护和扩展。 1 2 研究内容 本文旨在构建信息检索系统的算法库支持。它能够为系统中的其它模块提供 算法调用的统一接口。同时为方便用户的示例操作处理，提供了图形化的操作界 面。考虑到系统的可变性和可扩展性。我们以映像和元对象协议为基础，分离了 系统的核心功能和系统控制功能，实现了可扩展的算法调用架构。本课题的内容 可以综述为以下几点： 基于映像和元对象协议( m o p ) 实现算法调用。映像和元程序设计 7 是对 传统的面向对象编程的一种扩展，并采用分层的机制实现了功能的分离。采 用元程序设计的应用系统分为两层，即元层和基本层。基本层由基本对象构 成，元层则由元对象构成。基本层实现系统的基本功能和算法，元层则通过 元关联实现对基本层执行机制的修正 8 。元层跟基本层之间的通信接口是 由元对象协议定义的，元对象协议为用户提供了语言接口，使用户可以增量 式( i n c r e m e n t a l l y ) 修改基本层对象的行为和实现。 夺利用x m l 配置文件简化算法参数配置。用户选定相应算法后，针对数据的 特征可以对算法的参数进行设置，以便得到好的处理效果。用户对算法的了 解有限，为了简化参数设置的操作，各算法需设置的参数类型，参数的默认 值，都是通过x m l 配置文件进行的。这样不仅为不同的算法提供了相同的 配置界面，也方便了用户的操作。 第一章引言 基于遵循视图控制器模式的j s pm o d e l 2 模式，即j s p + j a v a b e a n + s e r v l e t 实现 了算法库的管理功能。进而，用户可以查看算法的描述信息，了解算法的适 用情况及其功能。 改进了x m l 结构聚类算法。自动文档聚类研究中最重要的概念是文本间的 距离( 相似性) 。目前常采用的定义距离的方法有欧氏距离法、数量积法、 相关系数法、指数相似系数法、夹角余弦法等。这些方法大都是建立在向量 空间模型( v e c t o rs p a c em o d e l ) 之上，基于文本内容展开的。具有效果不高， 结果不易评价等缺点。而本文针对x m l 的结构特征，提出了段匹配的概念 度量x m l 文档树间的相似性。并给出了“聚类代表”的计算方法。采用层 次聚类方法把x m l 文档分组为结构相似的簇。基于“聚类代表”可以去掉 那些特征原型和用户查询相去甚远的类别来缩小搜索空间，提高查询的质量 和效率，提出了新的思路。 1 3 论文组织 第一章，阐明本文课题的选题背景、研究意义及本人开展的工作。 第二章，对课题研究中研读的信息检索和映像和元对象协议相关论文的综 述。本章简单说明了有关信息检索的内容，基于映像和元对象协议的元程序架构 的相关概念。 第三章，详细阐述了算法库系统的设计。首先提出了课题的整体设计及相应 算法的实现。然后按照算法库的调用和管理分别阐述了相应模块的设计。 第四章，作者给出了硕士期间所完成的一个算法库原型系统。 第五章，对本文的研究工作的总结和今后工作的展望。 第二章文献综述 2 1 信息检索系统 第二章文献综述 信息检索m ( i n f o r m a t i o nr e m w a l ) ，是指从大量文档资源集合中自动地找 到与用户查询请求相关的各种信息。但是信息检索并不是w e b 特有的研究课题。 早在上世纪五十年代，当计算机被图书馆等部门用于存储和管理文档时，信息检 索就吸引了人们浓厚的兴趣。到八十年代，信息检索的研究已经在检索模型、索 引结构、性能评价等方面取得了丰富成果。并成功开发了一些系统，如c o m d l 大学的s m a r t 9 系统和m a s s a c h u s e t t s 大学的i n q u e r y 1 0 系统等。w e b 的出 现为信息检索提供了一个前所未有的实验环境和应用场景，许多w e b 信息检索 系统应运而生，例如y a h o o 、a l t a v i s t a 、m e t a c r a w l e r 等。目前最流行的系统模型 是布尔( b o o l e a n ) 或向量空间( v e c t o r s p a c e ) 1 l j ，概率模型( p r o b a b i l i s f i c m o d e l ) 1 2 。适当的逻辑能给i r 系统的不同功能提供所有的必需概念，因此v a n r i j s b e r g e n 1 3 提出基于逻辑的i r 系统模型。检索文档和相关文档之间的积极 对应是i r 系统的主要目标，即好的i r 系统应该检索到尽可能多的相关文档，且 仅是相关文档。 2 1 1 基于搜索引擎的信息检索系统 搜索引擎通常提前爬行于w e b 页面，建立该页面在本地的拷贝和或索引， 本地索引随后用于辨识相关页面并快速答复用户的查询请求。 目前的搜索引擎主要是基于关键词的全文匹配或者基于主题分类进行检索 1 4 。主要有两种广泛使用的信息检索技术 1 5 ：一是基于编码过程，即用特定 的观点或分类方法描述给定的内容，对术语进行预处理；二是进行全文分析，即 搜索包含用户给定关键词的信息源。但是编码的描述仅能反映部分的内容，单个 词汇的出现亦不能反映整个信息源的内容，因此这两种方法都不能保证检索信息 的精确匹配。 t h c i l m a n n 等人 1 6 提出了基于领域专家的信息检索方法，领域专家通过现 有的搜索引擎来查看w c b 站点上文档的增减；随后把移动过滤主体派到相应 w 曲上的移动主体平台；该过滤主体基于所掌握的领域知识，判断新文档是否 属于该领域专家所在的范畴，如果成立就将该文档带回；领域专家对返回文档进 第二章文献综述 一步分析，处理后将其插入文档知识库中；当用户查询时，大多数情况下可以直 接从本地文档知识库中获取自己所需的信息。该系统实现了对文档知识的预过 滤，用户可以快速地获得更加精确的结果。但是此系统利用搜索引擎来获取w e b 站点上的变化信息，因此存在搜索引擎固有的缺陷问题；同时需要w c b 信息服 务器本身或者附近的站点提供支持移动主体的平台。g e h m e y r 等人 1 7 采用向 量空间模型进行检索，把用户按爱好或兴趣进行分组，将移动主体派往信息源以 便进行信息搜集和过滤。该系统比搜索引擎查询更大的信息范围；降低了获取信 息的费用；提高了检索信息的质量；保证了灵活性和可扩展性。但是此系统需要 信息源提供支持移动主体的平台；不能及时地响应用户；仅从平均的角度提供了 一种较为经济的方法，对于单用户来讲，该方法并没有什么改善。 因此，目前的搜索引擎滞后于网络上信息的变化，且搜索范围有限，这就要 求对搜索引擎进行内部改造或引入新的检索机制。 2 1 2 基于本体的信息检索系统 在进行信息检索瓜时，用户不仅希望能够检索出所有感兴趣的信息，并过 滤掉不相关的信息，同时也希望获得最有价值的信息，以便以最快的速度来高效 地解决问题。对此已经出现多种研究方法，例如基于机器学习的方法，以及近年 逐步发展起来基于多主体技术并将本体论当作系统核心构件的m 方法。 o n t o b r o k c r 1 8 是用来处理h t m l 、x m l 和r d f 格式的信息源和信息源的 语义描述的系统，并提供信息检索、查询应答和维护支持等服务。该系统的核心 是用形式化本体描述背景知识，并将w e b 文档的语义明确化，以便综合利用本体 论的表达能力和推理机制。 o n t o s e 圯k 1 9 是基于内容从在线黄页和产品目录中进行信息检索的系统，该 系统把本体用作具有语义信息的领域词汇表，将本体驱动的内容匹配机制与一个 具有中等表达能力的形式化系统相结合，试图将本体论和大词典库相互集成，以 便为用户提供一个可以使用领域内任意词汇进行交互式语义查询的系统。 万捷等 2 0 针对信息检索中关键词所包含的语义内容，提出基于内容的信息 检索原型系统，利用本体论对检索需求进行语义扩充，并用文档分析器对检索文 档进行过滤，因此有效阻止了无用信息的人工筛选，增加了检索结果的准确性， 只提供给用户有用的检索结果，在较大程度上更加符合用户的查询需求。但在自 由文档分析中术语提取过程的效率偏低，因此该原型系统还存在着不足。 t r i a s 2 1 是基于m h s 架构可学习的信息助手，此系统中的a g e n t 与用户相 第二章文献综述 互扶持共同完成特定的检索目标，用户通过演示问题的解决方法和步骤来扩展 a g e n t 的能力。领域相关的本体在该系统的知识表示中起着重要的作用，为系统 中的所有组成部分提供共同的语言，成为一种灵活而有效的系统集成方法。 徐振宁等人 2 2 通过把本体论视为智能信息检索系统的核心，提出基于本体 论的智能信息检索系统的体系架构。采用m u l t i - a g e n t 技术对多层次用户偏好模 式建模，并采用多种相关反馈学习算法等方法，有效地解决了特定领域范围内精 确语义的查询，用户兴趣和信息源的自适应变化，以及系统的可扩展性等问题。 武成岗等人 2 3 提出基于本体论和多智能主体的信息检索服务器，并给出了 该服务器的体系架构，以及基本功能和工作流程。该系统利用本体论协助智能主 体对i n t c m c t 上的各类文档信息进行领域分类，并规范用户信息检索的模式，仅 提供给用户所关注领域的文档索引信息。此系统的信息搜索主体仅在提供移动主 体服务平台的信息检索服务器之间移动，因此信息源不必对移动主体提供平台支 持；能够快速地从其它的信息检索服务器的索引库中获取与本地用户偏好有关的 索引信息；预处理主体能将新文档转换成统一的文本格式，故能对多种异构文档 进行处理；用户所需的大部分信息来源于系统依据用户偏好设置的本地索引库和 信息库。 目前现有信息检索系统存在的问题是当前的搜索引擎不能达到深层的w e b ， 因此几乎排他的依赖于预先计算的结果 2 4 ：爬行于w c b 并建立索引结构，查 询处理大多归结到一些快速的索引查找。 2 2 映像式系统架构 映像和元程序设计 7 是对传统的面向对象编程的一种扩展，并采用分层的 机制实现了功能的分离。 映像和元对象协议的层次结构和基于元关联的元对象组合机制为应用系统 功能的分离和重新组合提供了一个强大的工具 2 5 。但是系统在获得强大功能的 同时，也付出了性能上的代价。首先由于元对象协议允许系统在运行时可以动态 调整其实现过程，因此系统必须为运行时代码的动态访问提供语言实现，这种实 现过程大大降低了系统的性能 2 6 。其次，由于元层对象和基本层对象之间频繁 的具体化( r c i f i e a t i o n ) 和映像( r e f l e c t i o n ) 过程的发生，也在很大程度上使得系 统运行时的负载过重，降低了系统的性能 2 7 。 第二章文献综述 2 2 1 映像 映像( r e f l e c t i o n ) 是指系统能监控并改变自身执行过程地能力 2 8 。一种语 言如果能够提供一种结构实体来描述程序的构造模块( 如类、方法) 和执行机制 ( 如解释器、垃圾收集器) ，就称这种语言是映像式的。使用映像式编程语言， 人们可以分别定义系统的功能( f u n c t i o n a l i t i e s ) 和这些功能的执行机制( e x e c u t i o n m e c h a n i s m ) ，并能很自然地实现它们的分离 2 9 。映像为动态地改变软件系统的 结构和行为提供了一种机制。它支持诸如类型结构和函数调用机制等基本方面地 修改。 在映像式系统中，元层次提供系统属性的相关信息并使软件含自述信息，基 本层次包括应用程序逻辑，由元对象实现对基本对象的自动控制。这个过程称为 映像过程 3 0 3 3 1 。要达到这个目标，需要在元对象和基本对象之间实现一种强 关联一元关联。这种关联允许基对象向元对象请求服务，由元对象改变基对象 的执行过程。通常来讲，一个映像过程分为两步： 1 、具体化( r e i f i c a t i o n ) ：基对象根据特定语义( s e m a n t i c ) 向元对象发送 服务请求以改变程序的执行过程。这个过程被称为实现( i m p l e m e n t ) 或者语义 的具体化。此时程序的控制流由基对象进入元对象。 2 、映像( r e f l e c t i o n ) ：控制流由元对象返回基对象。因为元对象改变了基 对象的部分实现，基对象的行为和表现形式随之发生了变化，元对象提供的服务 被映像( r e f l e c t ) 到了基对象中。映像操作包括元层对基本层的解释和改变。 元层 基本层次 图2 - 1 映像式系统 需要注意的是，元关联是不对称的 3 2 。要将语义的变化映像到基对象中， 元对象应该知道基对象的实现及工作方式。而基对象则不必知道元对象的任何实 第二章文献综述 现细节。事实上，基对象改变自身的语义和执行过程，只需要知道元对象提供服 务的接口即可。 实际上，具体化( r e i f i c a t i o n ) 和映像( r e t l e c t i o n ) 在表示元关联时通常是 不加任何区别的。如何使用这两个概念依赖于作者强调的重点，从映像的观点来 说，元层修改了基本层；从具体化的观点来说，基本层被元层修改。o v e nc - h v l 使用关键字r e f l e c t 实现元对象和基对象之间的元关联，而在i g u a n a 却使用了 r e i f y 关键字来表达相同的观点。在本文中，我们基于映像的观点。 2 2 2 元层和基本层 “元”( m e 国表示较高层次对较低层次的控制，是对信息更高层次的抽象。 本节基于面向对象解释这一观点。 在面向对象的系统中，系统是由一系列对象构成的。对象行为包括两个层次： 底层的跟特定的应用程序逻辑相关的功能性行为和高层的对功能性行为进行管 理和控制的系统行为。在映像式程序设计中，系统行为作为对底层功能性行为的 监控者和管理者，因而，映像式系统就是通过定义系统行为的元层( m e t a - l e v e l ) ， 对定义功能行为的基本层( b a s el e v e l ) 进行管理和控制的。 由于功能行为和系统行为的分离，系统被分成了不同的层次。一方面，基本 层次( b a s e - l e v e l ) 用来定义系统的功能行为，其实现使用元对象来保持可能要更 改的方面的独立性。另一方面，元层次( m e t a - l e v e l ) 提供了一个系统的自表示 来给出系统自身结构和行为的知识，元层次由所谓的元对象( m e t a - o b j e e t s ) 组成。 元对象用来对基本层次进行描述，并实现某些执行机制( 如函数调用机制、类型 结构) 的具体化( r e i f i c a t i o n ) 。 图2 - 2 映像式系统的元层和基本层 巨 第二章文献综述 图2 2 所示的映像式系统由元层和基本层构成，基本层由基对象构成，实现 系统的核心功能。元层则由元对象构成，每个元对象实现不同的系统行为，元对 象之间相互协作，实现对基对象不同系统行为的监控和管理。这种监控和管理是 通过元对象和基对象之间的元关联( m c ：t a - l i n k ) 实现的。 因为殃像式系统能够对自身的构造模块和执行机制进行监控和修改，而元层 次作为系统的一部分，有时元对象之间相互依赖。为了协调这些调用关系，可以 引入独立的元对象，以及概念上的元层次的一个元层次，或者换句话说，一个元 一元层次( m e t a - m e t a - l e v e l ) ，对元层次进行管理。因而，大多数映像式系统多于 两层。这就形成了映像式系统的塔式层次模型 3 3 ，如图2 - 3 所示。 理论上可以是一个无穷的映像塔。这样的软件系统有无穷多个元层次，其中 每个元层次都由它上层的元层次控制，每一个元层次都有它自己的元对象协议。 但是过多的层次会导致系统性能的下降以及设计复杂度的提高，而且系统可用的 资源是有限的，系统必须在有限的时间和硬件资源下完成特定的功能，因而，绝 大多数映像软件只有l 2 个元层次。 图2 - 3 映像式系统的塔式层次模型 2 2 3 元对象协议( m o p ) 在元程序体系架构中，我们最关心的是元层跟基本层的通信方式以及两者之 间的交换信息，而这些都是在元层次中定义的。因此，我们称面向对象的元层体 系架构为元对象协议 3 4 ( m e t a o b j e c t 阳洳c o l ，筒称m o p ) 。具体来说，元对 象协议就是系统或语言提供的接口。也就是元层次体系架构中基对象跟元对象通 信的接口。它使一个映像式系统的实现以一种己定义的方式来获得。 元对象协议通常设计为一个独立的组件。这样就可以支持对几个元对象操作 第二章文献综述 的函数的实现。元对象协议对这样执行的每一次修改都有一个较好的控制，实现 了与元对象分离。如果把这种变更的责任委托给元对象本身，则它们之间的一致 性就难以维护。 为执行变更，元对象协议需要进入元对象的内部。如果被进一步授权改变基 本层次对象与元对象间的关联，也需要访问基本对象。提供这种访问的方法之一 是允许元对象协议直接操作它们的内部状态。另一种较安全的方法是提供这种访 问的方法是为元对象和基本对象提供一个用于操作它们的特别接口，只有通过元 对象协议才能访问。 第三章算法库系统实现 第三章算法库系统设计 算法库设计中，最重要的是它的扩展性和灵活性。本章给出了算法库系统的 整体架构，并着重针对该架构中的算法调用模块和作者改进的x m l 结构聚类算 法进行了详尽的阐述。 3 1 算法库整体设计 算法库系统旨在提供数据处理的算法支持，它包括两个组件模块：算法调用 模块和算法管理模块。算法调用模块提供了一些j a v a 的a p i ，分析输入数据的 特征，匹配规则库中的相应规则来智能的选择最佳算法进行数据处理。它包括数 据的聚类处理、数据的分类处理、算法预处理、配置文件的设置和解析。同时， 为简化用户的数据处理操作，提供了图形化的操作界面。这样用户就可以方便地 进行算法的选择、参数的设置以及处理结果的查看。算法管理模块主要负责维护 算法描述信息的数据库，包括了算法的更新、添加、删除、浏览等例程来更新数 据库中的相关记录。算法库系统的总体框架如下图3 1 所示： 图3 - 1 总体架构 第三章算法库系统实现 3 2 基于映像和元对象协议实现算法的调用 在本小节，我们将基于映像及元程序设计思想实现算法库调用。映像是指系 统能够描述自身结构并动态改变自身执行机制的能力。因此，使用映像式语言， 开发人员不仅能够定义系统的核心功能，还能够定义这些功能的执行机制，实现 功能和执行机制的分离e 3 5 3 3 6 。在映像式系统中，基本层次对象定义系统中与 某个特定业务逻辑相关的核心功能，元层次对象定义某功能的执行机制，实现与 该功能相关的不同的控制，由元对象协议管理不同元对象之间的协作及元对象与 基本对象的交互。基本对象之间的相互分离实现不同的功能模块之间的相互分 离，元层跟基本层的分离实现控制跟功能模块之间的分离。因此映像提供了一种 好的解决方案来描述一个可随时修改和扩展的体系结构。即系统可以按照要求适 应更改需求。 某些映像式系统为了使系统有更好的重用性，不仅实现元对象与基本对象的 相互分离，在元对象的内部也采用了分离机制 3 7 3 。这样，元对象包括两个部分： 即用于修改元对象特定语义的元对象类( m e t a - o b j e c - tc l a s s ) 定义和用于建立元关 联的配置脚本定义。进而，只需要修改配置脚本的定义，一个应用系统中的相应 代码就可以被其它系统重用。 ， 例如，在一个典型的分布式的商务应用系统中，开发者通常要注意几个方面： 分布式，系统可能要跟远程的实体交互( 如客户、银行) ；并发控制，当系统管 理人员正在处理订单或者更新价格列表时可能有多个客户正在执行某项查询或 定购；持久化，实现某些对象( 比如订单、商品) 状态的持久化是很重要的，特 别是在系统维护或者崩溃的时候。权限控制，系统管理人员和客户的权限是不同 的，详细而严格的权限控制可以保证系统的安全性。下图3 - 2 就描述了该应用系 统的解决方案。 3 2 1 算法调用模块分析 算法调用模块应当完成以下功能： 夺分析输入数据特征，基于规则匹配关系自动选择相应算法进行数据处 理； 提供算法调用的统一接口，并且用户可以选择库中算法进行数据处理； 定制算法参数； 呤处理结果的保存、处理； 课题中算法库旨在为检索和偏好处理提供算法支持，这就需要算法库对外界 第三章算法库系统实现 提供统一的接1 3 ，以便于调用和扩展。同时考虑到算法的通用性，算法库能够作 m o p 层 持久化元对象霪l 梦并发控制元对象， 权限控制元对象。基对象 一映像继承协作控制流转移 图3 2 基于映像的应用系统解决方案 为一个独立的组件来运行，为用户的数据处理提供算法支持。但是用户对各个算 法的了解是有限的，因而算法库应该能够根据用户输入数据的特征自动选择相应 的算法进行数据处理。这就需要分析各类算法本身的特性，例如，对数据量的要 求、能处理的文档属性的类型等等。量化这些算法的特征，并根据这些特征来定 义算法的调用规则。进而，基于这些规则实现算法的智能选择与调用。但由于时 间关系，我们并没有实现算法的智能选择和调用，我们仍需要用户选定算法库中 存在的算法，实现半自动化的数据处理。在整个系统的实现过程中，我们必须要 注意以下几点： 夺简化算法调用的接口，只需指定算法的名称就可以调用相应算法来进行 数据的处理。这里，我们提供了算法配置文件，通过解析配置文件进行 算法参数的设置。 夺考虑算法库的扩展性，实现其核心功能和系统控制功能的分离。进而， 系统扩展或修改时，核心处理功能可以保持相对稳定。 第三章算法库系统实现 3 2 2 定义系统框架 我们是基于j a v a 语言实现算法库调用模块的，j a v a 语言为映像提供了良好 的支持，j 2 s e 开发包中包含了一个特殊的部分：j a v a 反射接口，放置在 j a v a 1 a n g r e f l e c t 包中。反射使得j a v a 的类、包和接1 ：3 实现了自我描述和动态操作 的功能，通过反射，j a v a 提供了一种非直接调用的方式，使我们可以取得运行时 类的相关信息。打破了一些固有的限制。为了能更清晰的阐述系统的具体设计过 程，对整个系统的功能分离的实现有一个整体的把握和认识。首先我们将分析问 题域并把它分解成一个适当的软件结构，对调用模块的整体架构做一简单介绍。 图3 3 算法调用架构 图3 - 2 所示的塔式的层次模型为我们的解决方案提供了必要的参考。该方案 将系统分为了基本层次、m o p 控制层、元层次等几层。基本层由基对象构成， 主要实现系统内领域相关的特定算法和业务逻辑。基对象之间可能存在继承关 系，也可能通过消息传递实现彼此之间的合作。元层次是由元对象来构成的。不 同的元对象可以被分为不同的类( 如图中元层次对象被分为以下几类：持久化元 对象、并发控制元对象、权限控制元对象) 。相同类内的元对象一般是互斥的， 分别定义了系统控制信息的某一策略。而不同类的元对象之间可以相互协作，共 第三章算法库系统实现 同完成对基本对象的控制。这个过程是由m o p 控制层来完成的。m o p 层读取配 置文件，对配置文件中与某基本对象控制相关的所有元对象进行协作方式的组合 控制。总之，元对象之间的协作以及元对象对基对象的控制，都是由m o p 控制 层来实现的。m o p 不仅定义了元层次和基本层次通信的接口，还定义了元对象 操作的接口。m o p 层的定义将直接影响着映像的执行过程。所以m o p 控制层不 仅仅存在于元层次和基本层次之间，而是存在于解决方案的任意两层之间。 图3 - 3 就描述了算法调用模块的架构。在图3 3 中，基本算法、相应的数据 预处理就构成了系统的一般关注点，它们之间的分离都是由基本对象来实现的， 每一个基本对象都封装了相应的核心处理功能。而非功能性的系统行为一一函数 调用机制、持久化分别由元层的某个元对象来实现的，不同元对象集合之间是相 互分离的，他们共同实现对基本对象的控制。函数调用元对象根据算法名称实现 对相应算法的调用。持久化元对象负责处理结果的保存。而m o p 控制层实现对 两层的沟通。具体来说，包括对元对象的创建、销毁、协作等的控制以及元对象 和基本算法对象之间参数的传递。这种定义方式下，元对象提供了特定系统功能 ( 如，函数调用机制、持久化) 的处理过程，m o p 负责元层次和基本层次连接， 两者之间是分离的。从而使系统具有更好的重用性和可扩展性。 3 2 3 系统功能分离 首先，分析系统原型确定系统服务中哪些可能要发生变化，那些服务保持稳 定。当系统变更时，确定系统中不影响基本层次实现的结构方面，例如函数调用 组件的实现必须独立于特定应用的类型。这就需要取得运行时的相关信息，比如 算法名称、算法参数配置等。基于以上分析所确定的服务可变性和结构化细节的 无关性，我们就可以来分离系统的功能。 夺定义元对象 我们可以为通过上述步骤明确的每一方面定义适当的元对象。封装由几个领 域无关的设计模式所支持的行为。我们是以策略对象来实现函数调用机制的元对 象。 策略模式【3 8 】体现了两个非常基本的面向对象设计得基本原则：封装变化的 概念；编程中使用接口，而不是对接1 2 实现。它的基本思想是：定义一系列得算 法、把它们一个个封装起来，并使得它们可以相互替换。从而使得这些算法可以 独立于使用它得客户而变化。它就使得开发人员能够开发出许多可替换得部分组 成的软件，并且各个部分之间是弱连接的关系。弱连接的特性使软件具有更强的 可扩展性，易于维护，更重要的是，它大大提高了软件的可重用性。其结构如下 第三章算法库系统实现 图3 - 4 所示。 其中，策略对象( s t r a t e g y ) 就定义了所支持的算法的公共接口，c o n t e x t 使 用这个公共接口来调用某一c o n c r e t e s t r a t e g y 定义的算法；具体策略对象 ( c o