一種基于KNN的組件檢索高效方法

魏爽

摘要：對于軟件設計者來說，如何低成本并高效地開發軟件一直是一個挑戰。軟件復用被廣泛視為一種解決方案，但是復用的耗費似乎要比其潛在價值更高。軟件復用涉及的工作包括建立和維護一個可復用的組件庫、查找合適特定設計的可復用組件以及對組件進行適配等。為此，提出一個新的方法來進行組件分類和檢索。該方法使用了K最近鄰算法和矢量空間模型。該方法在進行組件選擇和檢索中相對現有的方法具有更高的準確率。

關鍵詞：軟件復用；組件；檢索；向量空間；K最近鄰

1概述

很多軟件開發機構發現通過使用可復用組件進行軟件開發可以極大地減少開發的工作量和成本，還可以加快軟件交付。但是，由于缺少一個標準的搜索技術來搜索合適的組件，也沒有一個這樣的工具，這就導致了在搜索過程中經常會失敗。在這個領域，以往的研究很多偏向于使用不同的方法來改進組件的可適配性，很少有研究改進組件檢索。模糊語言方法是信息檢索中常用的一種方法。本文使用了一種代數方法，即矢量空間模型。這個方法將文本文檔用標識符矢量來表示。這些矢量使用的標識符，如標引詞，用來進行信息過濾、信息檢索、建立索引、相關排序以及用K最近鄰（K-Nearest Neighbor，KNN）算法進行文檔分類等。

2軟件復用

軟件復用的基本觀念就是通過使用現有的信息、組件或產品來設計、實現新的系統或產品。怎么樣才能算作真正的軟件復用這個問題上有很多不同的看法。復制整個軟件程序并不能算作復用。有價值的復用依賴于使用組件構建的應用的相似度和不同來判斷。

很多軟件機構已經在一定程度上進行了復用。例如，大多數開發者會使用在以前的工程中開發的一些組件庫，或者使用編程語言自帶的標準庫。對于約30%的應用開發，復用是一種特別的方法，它可以較好地應用在小規模開發上，但是并不適用于整個組織。對于企業來講，要最大化利用復用的有點，就必須建立一個系統化的復用程序。

可復用組件是專門設計的適用于多種情況的組件。不僅僅只是代碼，系統的生命周期中的其他產品也可以復用，如說明書、需求等?？梢?，組件可以包括系統生命周期中所有潛在的可被復用的產品，如代碼、文檔、設計、需求等。

要成功地復用一個組件，需要滿足幾個標準。這些標準可分為一般要求、功能性要求以及技術要求。一般要求集中于滿足相關標準、完整性、模塊化和簡單性。所有的組件必須滿足一般要求。功能性要求主要關注縱向或者面向域的組件，對于每個信息領域都有具體要求。技術性要求涉及互操作性、可移植性、通信、安全等標準。

復用可以分為幾個層次：最高層，整個應用可以復用在不同的平臺上，前提是應用是可移植的；子系統可以在不同的應用、域中復用；可復用組件也可以在內部進行構建，或者從先前的系統中獲取，也可以從外部購買。

3組件檢索的研究現狀

當前，軟件組件檢索的方法涵蓋的范圍很廣，包括組件編碼方法、算法查找匹配等。不同的編碼方法在可靠性、完整性以及修改組件所需的工作量等方面存在差異?；谖谋镜慕M件編碼和檢索既不健全也不完整。其缺點跟文獻信息檢索完全一致?；谠~匯描述符的編碼方法在生成和使用分類詞匯上也存在很多的問題。軟件開發的挑戰是在軟件開發領域，很難對單個詞或單個語句進行抽象。從組件的用戶的角度來看，不能熟練掌握詞匯也是高效使用組件檢索系統的一種障礙。本文提出的矢量空間模型對于組件檢索過程是一個比較有力的解決方案。

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近鄰樣本間的距離。同時，該方法消除了未知樣本無法識別的情況。通過實驗，將該分類算法應用到文檔識別中，結果顯示該方法完全滿足識別率的要求，并且識別速度快。