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

魏爽

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

關(guān)鍵詞：軟件復(fù)用；組件；檢索；向量空間；K最近鄰

1概述

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

2軟件復(fù)用

軟件復(fù)用的基本觀念就是通過使用現(xiàn)有的信息、組件或產(chǎn)品來設(shè)計(jì)、實(shí)現(xiàn)新的系統(tǒng)或產(chǎn)品。怎么樣才能算作真正的軟件復(fù)用這個(gè)問題上有很多不同的看法。復(fù)制整個(gè)軟件程序并不能算作復(fù)用。有價(jià)值的復(fù)用依賴于使用組件構(gòu)建的應(yīng)用的相似度和不同來判斷。

很多軟件機(jī)構(gòu)已經(jīng)在一定程度上進(jìn)行了復(fù)用。例如，大多數(shù)開發(fā)者會(huì)使用在以前的工程中開發(fā)的一些組件庫，或者使用編程語言自帶的標(biāo)準(zhǔn)庫。對(duì)于約30%的應(yīng)用開發(fā)，復(fù)用是一種特別的方法，它可以較好地應(yīng)用在小規(guī)模開發(fā)上，但是并不適用于整個(gè)組織。對(duì)于企業(yè)來講，要最大化利用復(fù)用的有點(diǎn)，就必須建立一個(gè)系統(tǒng)化的復(fù)用程序。

可復(fù)用組件是專門設(shè)計(jì)的適用于多種情況的組件。不僅僅只是代碼，系統(tǒng)的生命周期中的其他產(chǎn)品也可以復(fù)用，如說明書、需求等?？梢姡M件可以包括系統(tǒng)生命周期中所有潛在的可被復(fù)用的產(chǎn)品，如代碼、文檔、設(shè)計(jì)、需求等。

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

復(fù)用可以分為幾個(gè)層次：最高層，整個(gè)應(yīng)用可以復(fù)用在不同的平臺(tái)上，前提是應(yīng)用是可移植的；子系統(tǒng)可以在不同的應(yīng)用、域中復(fù)用；可復(fù)用組件也可以在內(nèi)部進(jìn)行構(gòu)建，或者從先前的系統(tǒng)中獲取，也可以從外部購買。

3組件檢索的研究現(xiàn)狀

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

4使用的方法

4.1矢量空間模型

矢量空間模型是一種代數(shù)方法。使用這種方法時(shí)，文檔和查詢都用矢量來表示，如下所示：

每一個(gè)維度對(duì)應(yīng)一個(gè)單獨(dú)的項(xiàng)目。如果某一項(xiàng)目出現(xiàn)在文檔中，這個(gè)矢量中對(duì)應(yīng)的數(shù)值就為非零值。編入索引的文檔的集合可以用一個(gè)項(xiàng)目表來表示，該項(xiàng)目表中將文檔以域和詞的形式作為每一行記錄的主鍵值。項(xiàng)目表的第（D）i唧ord）i條記錄記錄了第i個(gè)索引項(xiàng)在第i個(gè)文檔中出現(xiàn)的次數(shù)。圖1所示為空間矢量模型的例子。

矢量空間搜索模型最重要的一個(gè)因素市項(xiàng)目空間的概念。項(xiàng)目空間由文檔集中出現(xiàn)的不同的詞組成。其次，就是項(xiàng)目的數(shù)量，即每個(gè)項(xiàng)目在單個(gè)的文檔中出現(xiàn)的次數(shù)。這些可以用一個(gè)表格來表示。將項(xiàng)目空間映射到坐標(biāo)系統(tǒng)中，將項(xiàng)目數(shù)也作為坐標(biāo)系統(tǒng)的一項(xiàng)，這樣就可以為每個(gè)文檔創(chuàng)建一個(gè)矢量。隨著項(xiàng)目種類的增加，矢量空間模型的維度也會(huì)跟著增加。

通過記錄等級(jí)、排序，項(xiàng)目之間可以進(jìn)行比較。這樣就可以根據(jù)查詢的標(biāo)準(zhǔn)對(duì)復(fù)雜的信息進(jìn)行計(jì)算數(shù)值。在此，矢量空間搜索模型將通過相關(guān)性檢索到的文檔進(jìn)行等級(jí)劃分、排序，這樣使用者就可以根據(jù)需要快速選擇組件。

表1顯示了詞數(shù)據(jù)庫的結(jié)構(gòu)，其中記錄了每個(gè)詞在各個(gè)文檔中出現(xiàn)的頻率。

表2顯示了文檔等級(jí)表結(jié)構(gòu)，文檔和對(duì)應(yīng)的等級(jí)記錄在等級(jí)表中。

搜索某個(gè)關(guān)鍵詞時(shí)，文檔的相關(guān)度可以通過文檔相似度來進(jìn)行計(jì)算。首先，將查詢的矢量記作q；然后將查詢到的文檔對(duì)應(yīng)的矢量，即文檔矢量記作di；那么，通過計(jì)算查詢矢量和文檔矢量的角度差e，就可以計(jì)算相關(guān)度。通過計(jì)算角度差的余弦值可以更簡單地表示相關(guān)度：

余弦值越高，表示相關(guān)度越高。如果余弦值為0時(shí)，表示查詢矢量和文檔矢量是互相垂直的，即不匹配，也就是說文檔中沒有出現(xiàn)查詢的項(xiàng)目。

4.2文檔分類算法

KNN分類器是一種基于實(shí)例的學(xué)習(xí)算法，該算法的基礎(chǔ)是計(jì)算關(guān)注對(duì)象對(duì)之間的距離函數(shù)，如歐式距離、余弦等。KNN分類器算法已經(jīng)被廣泛應(yīng)用。在進(jìn)行分類計(jì)算時(shí)，首先計(jì)算訓(xùn)練數(shù)據(jù)的K最近鄰，然后根據(jù)近鄰的分類，將測試數(shù)據(jù)的樣本到其K近鄰的相似度合在一起來判斷，將測試樣本歸為與其相似度最高的類。在這里，將每個(gè)近鄰文檔相對(duì)測試文檔的相似度作為近鄰文檔分類的權(quán)重值。如果訓(xùn)練數(shù)據(jù)中，有K最近鄰的數(shù)篇文檔屬于同一個(gè)類別，那么該類別的權(quán)重值就更高。本文利用前面提到的余弦距離來計(jì)算文檔的相似度。

KNN算法的分類決策是基于相似對(duì)象的少量近鄰，這就使得它非常適合多模態(tài)。即使目標(biāo)類是多模態(tài)的，使用KNN算法的準(zhǔn)確率仍然很高。使用KNN算法計(jì)算相似度的主要缺點(diǎn)就是在計(jì)算相似度的時(shí)候，對(duì)象的所有特征都有相同的權(quán)重值。這就使得在只使用特征的一個(gè)很小的子集的時(shí)候，計(jì)算相似度時(shí)產(chǎn)生較大偏差，進(jìn)而導(dǎo)致分類錯(cuò)誤。

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

第一步，選擇K最近鄰訓(xùn)練文檔，相似度通過計(jì)算測試文檔和訓(xùn)練文檔的余弦值來計(jì)算。

第二步，根據(jù)K最近鄰的余弦值和K最近另里每個(gè)類別i里文檔的頻率，計(jì)算每個(gè)類別i的平均余弦值，即Avg_Cosine（i）。

第三步，將測試文檔類別歸到其對(duì)應(yīng)平均余弦值最大的類中。

在保留有用信息的前提下，為了減少矢量空間模型的維度，先計(jì)算出給定類別的概念矢量。然后，將這些概念矢量作為投影矩陣，分別對(duì)訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)進(jìn)行投影。最后，將KNN算法應(yīng)用于經(jīng)過投影減少了維度的空間矢量模型。

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

第一步，通過訓(xùn)練文檔的原始標(biāo)簽信息為每個(gè)類別計(jì)算一個(gè)概念矢量，然后構(gòu)建一個(gè)w行c列的概念矢量矩陣C，c即為類別的數(shù)量。

第二步，用概念矢量矩陣C對(duì)矢量空間模型A進(jìn)行投影，A為w行d列，得到一個(gè)c行d列的矩陣。

第三步，將KNN算法應(yīng)用于經(jīng)過投影的矢量空間模型。

5小結(jié)

本文提出了一個(gè)基于KNN的新算法和模型。該方法不僅消除了傳統(tǒng)KNN算法即時(shí)學(xué)習(xí)的主要缺點(diǎn)，還考慮了目標(biāo)樣本和K近鄰樣本間的距離。同時(shí)，該方法消除了未知樣本無法識(shí)別的情況。通過實(shí)驗(yàn)，將該分類算法應(yīng)用到文檔識(shí)別中，結(jié)果顯示該方法完全滿足識(shí)別率的要求，并且識(shí)別速度快。