一种基于KNN的组件检索高效方法

魏爽

摘要：对于软件设计者来说，如何低成本并高效地开发软件一直是一个挑战。软件复用被广泛视为一种解决方案，但是复用的耗费似乎要比其潜在价值更高。软件复用涉及的工作包括建立和维护一个可复用的组件库、查找合适特定设计的可复用组件以及对组件进行适配等。为此，提出一个新的方法来进行组件分类和检索。该方法使用了K最近邻算法和矢量空间模型。该方法在进行组件选择和检索中相对现有的方法具有更高的准确率。

关键词：软件复用；组件；检索；向量空间；K最近邻

1概述

很多软件开发机构发现通过使用可复用组件进行软件开发可以极大地减少开发的工作量和成本，还可以加快软件交付。但是，由于缺少一个标准的搜索技术来搜索合适的组件，也没有一个这样的工具，这就导致了在搜索过程中经常会失败。在这个领域，以往的研究很多偏向于使用不同的方法来改进组件的可适配性，很少有研究改进组件检索。模糊语言方法是信息检索中常用的一种方法。本文使用了一种代数方法，即矢量空间模型。这个方法将文本文档用标识符矢量来表示。这些矢量使用的标识符，如标引词，用来进行信息过滤、信息检索、建立索引、相关排序以及用K最近邻（K-Nearest Neighbor，KNN）算法进行文档分类等。

2软件复用

软件复用的基本观念就是通过使用现有的信息、组件或产品来设计、实现新的系统或产品。怎么样才能算作真正的软件复用这个问题上有很多不同的看法。复制整个软件程序并不能算作复用。有价值的复用依赖于使用组件构建的应用的相似度和不同来判断。

很多软件机构已经在一定程度上进行了复用。例如，大多数开发者会使用在以前的工程中开发的一些组件库，或者使用编程语言自带的标准库。对于约30%的应用开发，复用是一种特别的方法，它可以较好地应用在小规模开发上，但是并不适用于整个组织。对于企业来讲，要最大化利用复用的有点，就必须建立一个系统化的复用程序。

可复用组件是专门设计的适用于多种情况的组件。不仅仅只是代码，系统的生命周期中的其他产品也可以复用，如说明书、需求等。可见，组件可以包括系统生命周期中所有潜在的可被复用的产品，如代码、文档、设计、需求等。

要成功地复用一个组件，需要满足几个标准。这些标准可分为一般要求、功能性要求以及技术要求。一般要求集中于满足相关标准、完整性、模块化和简单性。所有的组件必须满足一般要求。功能性要求主要关注纵向或者面向域的组件，对于每个信息领域都有具体要求。技术性要求涉及互操作性、可移植性、通信、安全等标准。

复用可以分为几个层次：最高层，整个应用可以复用在不同的平台上，前提是应用是可移植的；子系统可以在不同的应用、域中复用；可复用组件也可以在内部进行构建，或者从先前的系统中获取，也可以从外部购买。

3组件检索的研究现状

当前，软件组件检索的方法涵盖的范围很广，包括组件编码方法、算法查找匹配等。不同的编码方法在可靠性、完整性以及修改组件所需的工作量等方面存在差异。基于文本的组件编码和检索既不健全也不完整。其缺点跟文献信息检索完全一致。基于词汇描述符的编码方法在生成和使用分类词汇上也存在很多的问题。软件开发的挑战是在软件开发领域，很难对单个词或单个语句进行抽象。从组件的用户的角度来看，不能熟练掌握词汇也是高效使用组件检索系统的一种障碍。本文提出的矢量空间模型对于组件检索过程是一个比较有力的解决方案。

4使用的方法

4.1矢量空间模型

矢量空间模型是一种代数方法。使用这种方法时，文档和查询都用矢量来表示，如下所示：

每一个维度对应一个单独的项目。如果某一项目出现在文档中，这个矢量中对应的数值就为非零值。编入索引的文档的集合可以用一个项目表来表示，该项目表中将文档以域和词的形式作为每一行记录的主键值。项目表的第（D）i唧ord）i条记录记录了第i个索引项在第i个文档中出现的次数。图1所示为空间矢量模型的例子。

矢量空间搜索模型最重要的一个因素市项目空间的概念。项目空间由文档集中出现的不同的词组成。其次，就是项目的数量，即每个项目在单个的文档中出现的次数。这些可以用一个表格来表示。将项目空间映射到坐标系统中，将项目数也作为坐标系统的一项，这样就可以为每个文档创建一个矢量。随着项目种类的增加，矢量空间模型的维度也会跟着增加。

通过记录等级、排序，项目之间可以进行比较。这样就可以根据查询的标准对复杂的信息进行计算数值。在此，矢量空间搜索模型将通过相关性检索到的文档进行等级划分、排序，这样使用者就可以根据需要快速选择组件。

表1显示了词数据库的结构，其中记录了每个词在各个文档中出现的频率。

表2显示了文档等级表结构，文档和对应的等级记录在等级表中。

搜索某个关键词时，文档的相关度可以通过文档相似度来进行计算。首先，将查询的矢量记作q；然后将查询到的文档对应的矢量，即文档矢量记作di；那么，通过计算查询矢量和文档矢量的角度差e，就可以计算相关度。通过计算角度差的余弦值可以更简单地表示相关度：

余弦值越高，表示相关度越高。如果余弦值为0时，表示查询矢量和文档矢量是互相垂直的，即不匹配，也就是说文档中没有出现查询的项目。

4.2文档分类算法

KNN分类器是一种基于实例的学习算法，该算法的基础是计算关注对象对之间的距离函数，如欧式距离、余弦等。KNN分类器算法已经被广泛应用。在进行分类计算时，首先计算训练数据的K最近邻，然后根据近邻的分类，将测试数据的样本到其K近邻的相似度合在一起来判断，将测试样本归为与其相似度最高的类。在这里，将每个近邻文档相对测试文档的相似度作为近邻文档分类的权重值。如果训练数据中，有K最近邻的数篇文档属于同一个类别，那么该类别的权重值就更高。本文利用前面提到的余弦距离来计算文档的相似度。

KNN算法的分类决策是基于相似对象的少量近邻，这就使得它非常适合多模态。即使目标类是多模态的，使用KNN算法的准确率仍然很高。使用KNN算法计算相似度的主要缺点就是在计算相似度的时候，对象的所有特征都有相同的权重值。这就使得在只使用特征的一个很小的子集的时候，计算相似度时产生较大偏差，进而导致分类错误。

使用平均余弦的KNN算法的步骤如下：

第一步，选择K最近邻训练文档，相似度通过计算测试文档和训练文档的余弦值来计算。

第二步，根据K最近邻的余弦值和K最近另里每个类别i里文档的频率，计算每个类别i的平均余弦值，即Avg_Cosine（i）。

第三步，将测试文档类别归到其对应平均余弦值最大的类中。

在保留有用信息的前提下，为了减少矢量空间模型的维度，先计算出给定类别的概念矢量。然后，将这些概念矢量作为投影矩阵，分别对训练数据和测试数据进行投影。最后，将KNN算法应用于经过投影减少了維度的空间矢量模型。

基于矢量算法和KNN算法的混合方法的步骤如下：

第一步，通过训练文档的原始标签信息为每个类别计算一个概念矢量，然后构建一个w行c列的概念矢量矩阵C，c即为类别的数量。

第二步，用概念矢量矩阵C对矢量空间模型A进行投影，A为w行d列，得到一个c行d列的矩阵。

第三步，将KNN算法应用于经过投影的矢量空间模型。

5小结

本文提出了一个基于KNN的新算法和模型。该方法不仅消除了传统KNN算法即时学习的主要缺点，还考虑了目标样本和K近邻样本间的距离。同时，该方法消除了未知样本无法识别的情况。通过实验，将该分类算法应用到文档识别中，结果显示该方法完全满足识别率的要求，并且识别速度快。