一種基于用戶需求協作修正的構件檢索方法

鐘鳴，張堯學，周悅芝，田鵬偉，翁林開

(1. 清華大學 信息科學與技術國家實驗室，北京，100084；2. 清華大學 計算機科學與技術系，北京，100084)

一種基于用戶需求協作修正的構件檢索方法

鐘鳴1,2，張堯學1,2，周悅芝1,2，田鵬偉1,2，翁林開1,2

(1. 清華大學 信息科學與技術國家實驗室，北京，100084；2. 清華大學 計算機科學與技術系，北京，100084)

針對當前主流的構件檢索方法只從構件分類和索引的角度出發研究提高構件檢索效率，卻忽略用戶理解與構件描述之間差異的現狀，提出一種基于用戶需求協作修正的構件檢索方法。該方法采用向量對構件功能和用戶需求進行統一描述，并基于向量內積相似度實現構件檢索；并在此基礎上引入反饋機制，根據用戶的歷史檢索記錄創建和維護用戶需求協作修正模型，通過該模型來對新的用戶需求進行協作修正，以此縮小用戶理解與構件分類描述之間的差異，提高構件檢索效率。在構件庫原型系統中分別以平均檢索時間和平均目標位置為標準對該方法進行性能評測。研究結果表明：在基于向量的構件檢索方法中，對用戶需求進行協作修正能有效提高構件檢索的準確度，縮短構件檢索時間。

軟件復用；構件檢索；向量；協作修正

隨著計算機技術的發展，軟件開發的模式逐漸由“以計算機為中心”向“以人為中心”轉變。用戶對各種程序和服務提出了更加智能化、個性化、綜合化的需求。從這種發展趨勢中可以看出，面向終端用戶的應用程序個性化定制將是未來主要的軟件和服務開發模式之一，因此，軟件復用[1]和基于構件的軟件開發技術[2]以及主動服務的思想[3]逐漸成為軟件工程的主流。軟件復用過程中的一個重要環節是構件檢索，快速準確的構件檢索技術能大大提高軟件復用的效率。傳統的構件檢索方法[4?8]主要基于刻面分類[9]與匹配來實現，在 REBOOT等[10?12]上都被采納使用，能保證一定的查全率和查準率。Gibb等[13]在可復用軟件構件研究項目中引進了 XML作為構件描述的標記語言，并應用XML檢索語言XML-SQL來完成構件檢索的任務。王淵峰等[14]將樹匹配的方法結合進構件刻面描述的匹配，提出了一個包含3 個層次和5 種匹配類型的可復用構件刻面描述的匹配模型，擴展了刻面檢索的匹配空間。上述方法雖然在一定程度上能滿足用戶的構件檢索需求，但仍存在一些問題。一方面，現有方法大都只注重于將滿足用戶需求的構件返回給用戶，由于刻面分類的粒度較大，對用戶需求的描述也不夠細化，所以構件檢索系統無法根據用戶需求對檢索結果集合中的構件進行有效的區分；另一方面，上述方法默認構件庫的構件分類描述模式與大眾用戶的理解方式是完全一致的，沒有采用用戶反饋機制來對構件描述或者用戶需求進行引導修正，當出現用戶理解與構件功能描述模式出現差異時，用戶將很難從大量的返回結果中檢索到自己真正想要的構件。隨著構件數目逐漸增多，構件功能逐漸細化，使得上述問題日趨嚴重。因此，為了細化構件功能和用戶需求的描述粒度，增加各個構件之間的功能區分度，同時縮小用戶理解與構件功能描述模式出現差異，以提高構件檢索的準確率，本文作者提出一種基于用戶需求協作修正的構件檢索方法。采用向量空間模型[15]對構件和用戶需求進行功能描述，以向量之間的內積相似度作為判斷構件是否滿足用戶需求的標準。在此基礎上，為了盡可能提高用戶需求描述的準確性，設計了基于用戶檢索歷史的用戶需求協作修正算法，通過記錄構件庫的歷史檢索信息并從中提取協作修正模型，對新到來的檢索需求進行協作修正，以達到縮小用戶需求和實際目標構件描述之間的自然語言理解共性差異的目的，便于用戶快速定位和篩選所需要的構件。

1 構件檢索總體框架

要實現基于構件的軟件復用，最基本的因素是有豐富的構件資源和快速準確的構件檢索方法，保證在構件檢索過程中有較高的查全率和查準率。構件檢索的過程一般包括 3步：1) 用戶提交檢索請求；2) 檢索系統逐個匹配構件判斷是否滿足用戶需求；3) 系統返回檢索結果列表并由用戶挑選所需要的構件進行復用。顯然，其中最關鍵的就是將用戶需求與各個構件進行匹配的過程。構件分類與描述是否準確、是否能被用戶理解，用戶所提出的需求是否完善合理，這些都會直接影響系統查全率和查準率的高低。為解決上述問題，作者主要采用基于向量空間模型的構件檢索方法，通過專家評估和實踐檢驗的方式，不斷完善用于構件分類與描述的功能特征關鍵詞體系，使之盡量合理準確；在此基礎上引入反饋機制，依據用戶的歷史有效檢索記錄對用戶的新檢索需求進行協作修正，以此提高用戶需求描述相對于構件分類體系的準確性。引入用戶需求協作修正機制后的構件檢索過程如圖1所示。

圖1 基于用戶需求協作修正的構件檢索流程圖Fig.1 Process of component retrieval based on collaborative revision of user requirement

1.1 基于向量空間模型的構件檢索過程

構件功能是構件檢索的重要指標，也是用戶理解構件的基礎。這里主要采用向量空間模型來表示構件功能描述和用戶需求。用 1組功能特征關鍵詞f1，f2，…，fn作為空間的基準，則構件庫的構件功能向量空間F可以表示為：F=(f1，f2，…，fn)(其中，n為關鍵詞向量的維度)。根據每個構件的功能描述文本信息，采用歸一化詞頻統計規則可以計算各個功能特征關鍵詞的權重，在經過歸一化處理以后就形成構件的功能描述向量ci=(ci1，ci2，…，cin)(其中，cij為構件ci與第j個功能特征關鍵詞fi的相關度)。同樣，每次用戶提出的檢索需求也可以用向量來表示：q0=(q01，q02，…，q0n)(其中，q0i為用戶在第i個功能特征關鍵詞fi下的需求強度)。顯然，所有構件描述向量和用戶需求向量的維度為n。用向量內積計算向量之間的相似度，設vi=(vi1，vi2，…，vjn)，vj=(vj1，vj2，…，vjn)分別表示構件功能描述向量和用戶需求向量，則兩者之間的向量相似度為：

構件功能向量和用戶需求向量之間的向量相似度可以作為判斷構件是否滿足用戶需求的標準，以此實現構件檢索。對于每個構件ci，相對于當前用戶需求q0的匹配度Yi的計算公式為：

對于匹配度大于一定閾值的構件，認為滿足用戶需求，將這些構件與用戶需求的匹配度按從大到小排序。排在前面的構件，表示其與用戶的復用需求更接近，被用戶選擇的可能性越大。

1.2 用戶需求協作修正過程

采用向量空間模型來表示構件和用戶需求并實現構件檢索的方法，能比較準確地提取出構件的功能特征，在功能層面上對構件和用戶需求進行量化表示，在一定程度上細化了兩者的描述粒度，以此在構件檢索時增加各個構件之間的功能區分度，提高構件的檢索效率。但是，在基于向量空間模型的構件檢索過程中，用戶最終所選擇的構件，其功能描述向量一般不會與用戶需求向量完全一致，這反映了用戶對構件功能的理解和構件實際功能描述之間的差異。這種差異越大，構件檢索的效率就會越低。因此，為了盡可能提高構件描述和用戶需求描述的準確性，從而提高構件檢索的效率，在基于向量空間模型的構件檢索方法基礎上增加了對用戶需求進行協作修正的模塊，根據構件庫的歷史有效檢索信息，對用戶檢索需求進行協作修正，以縮小用戶需求和實際目標構件之間的差異。用戶需求協作修正模塊主要由檢索日志庫、協作修正模型和協作修正引擎3部分組成。

檢索日志庫主要對構件庫進行的有效檢索操作進行記錄。用戶每一次成功的構件檢索操作都包括提出構件檢索需求和篩選提取構件2個動作。檢索系統會將最匹配用戶需求的構件按照向量匹配程度從高到低列出，用戶從中選擇所需要的構件；因此，用戶的需求和所挑選的構件就作為1條反饋記錄被保存到檢索日志庫中。

協作修正模型是根據檢索日志庫中的歷史記錄信息所提取出來的，其核心思想是用統計大眾用戶在檢索構件過程中所反映出來的需求描述與構件描述之間的差異，以便于在今后的檢索中消除這種差異，提高構件檢索的準確度。

協作修正引擎負責對用戶新需求進行協作修正。將協作修正模型作用到用戶新需求中，得到1個協作修正向量，按照一定的權重融合到用戶需求中，使用戶檢索需求更加貼近用戶實際所需構件。

2 基于檢索歷史的需求協作修正方法

2.1 用戶需求協作修正模型

在基于向量空間模型的構件檢索過程中，用戶每次成功檢索都會產生用戶需求向量和最終用戶所提取構件的構件功能描述向量。在構件檢索系統中，將上述信息記錄下來，創建 1個檢索日志庫，記為R={r1，r2，…，rm}(其中，m為歷史檢索記錄的數目)。日志中的每項ri(i=1，2，…，m)均是 1條有效的歷史檢索記錄，定義為：ri=(qi，wi)(其中，qi=qi1，qi2，…，qin)，是第i條記錄中的用戶需求向量；wi=(wi1，wi2，…，win)，是第i條記錄中的構件描述向量)。

為了避免將無意義的檢索記錄添加到檢索日志庫中，規定：如果用戶在其檢索需求所對應的檢索結果的前100個構件中篩選出所需要的構件，則是一次有效的構件檢索過程；否則，表示用戶并不是真正依靠其所提出的檢索需求找到的構件，這樣的檢索記錄會影響日志庫的總體參考價值，不能被添加到檢索日志庫中。另外，在構件檢索過程中，用戶需求向量是否歸一化都不會影響檢索結果的排序，但是在將檢索記錄放入檢索日志庫之前，每個歷史需求向量都必須進行歸一化處理，以保證各個記錄重要程度的一致性。

用戶需求協作修正是根據檢索日志庫中的記錄對新到來的用戶需求進行修正改進，使其更加接近實際目標構件。其設計思想是從構件庫的歷史檢索記錄中找出用戶共性的檢索習慣，統計用戶各類檢索需求與目標構件之間的平均差異，并作用到新的檢索需求中以削弱這種差異。記用戶提出的新檢索需求為q0=(q01，q02，…，q0n)。通過向量內積計算，將q0與記錄表中的所有歷史用戶需求進行相似度比較。若新用戶需求與歷史記錄中的需求向量相似度越高，則表示該歷史用戶需求向量所對應的構件功能描述向量越接近用戶的真實需求，也就越具有構件檢索的參考價值。將新檢索需求與各個歷史需求進行相似度計算，其結果作為權重用于對應的構件描述向量中，再將所得向量全部累加起來，就可以得到1個新的用戶檢索需求向量，定義為修正需求向量qrev，其計算公式如下：

這里需要將用戶原始需求向量q0和修正需求向量qrev分別進行歸一化，得到q′0和q′rev。最后，將歸一化修正需求向量以一定的比例t整合到用戶原始歸一化需求向量中，得到最終的用戶檢索需求向量q′rev。

其中：t是 0～1之間的一個數字，代表修正需求向量在最終檢索請求中的權重，其取值范圍為 0～1，可以由用戶根據實際情況決定。若用戶對當前所需要的構件比較熟悉，能提出比較準確的檢索需求，則可以將t設置得較小，甚至為0；而當用戶對當前構件庫的功能特征關鍵詞分類不熟悉，無法確定自己所提出的需求是否合適時，一般將t設置得比較高，可獲得較大程度的協作修正。

上述對用戶檢索需求進行協作修正的過程，在每次用戶檢索時都需要與庫中的所有記錄進行比較，這樣，當檢索歷史逐漸增多時，計算修正向量qrev所需要的時間會越來越長，不滿足實際操作的實時性，因此，對上述計算公式進行推導和演化，從中提取用戶需求協作修正模型。過程如下：

因此，得到向量集合U={uj，j=1，2，…，n}為用戶需求的協作修正模型。可以發現，模型U與歷史檢索記錄數目m無關，其規模只與向量的維度n相關。這意味著將歷史檢索記錄進行建模以后，能有效地降低用戶需求協作修正的計算量，使操作時間保持在一個恒定較短的時間內，且模型占用的空間也不會變大。

2.2 模型維護

用戶需求協作修正模型U根據構件庫的檢索歷史記錄創建，當構件庫完成1次新的有效檢索過程之后，需要將新的檢索記錄融合到協作修正模型中，保證該模型實時更新。采用增量學習機制對用戶需求協作修正模型U進行維護。步驟及證明過程如下。

(1) 假設原始模型U根據m條歷史檢索記錄創建，新出現p條有效檢索記錄R′={rm+1，rm+2，…，rm+p}。則需要根據這p條新的檢索記錄，采用上述建模方法創建協作修正增量模型U′={uj′，j=1，2，…，n}，其中第j個分量為：

(2) 將增量模型中的每一項uj′以向量加法的形式，加到相應的原始模型各項中，得到新的協作修正模型Unew。對于Unew中的第j個分量unew?j，可得：

由上述推導可知：該模型U具有可加性，可以采用增量學習機制對用戶需求協作修正模型進行維護，只針對新保存下來的用戶有效檢索記錄創建增量模型，將增量模型直接疊加到原有模型上以得到新的協作修正模型。這樣，就不需要在新記錄到來時對整個模型重新計算，能有效地控制模型維護代價。

3 實驗分析

設計了一個構件庫原型系統 LCRS(Local component retrieval system)(Microsoft NET 2003 +SQL2000)，實現了本文所提出的基于向量空間模型的構件檢索方法，并根據歷史檢索記錄對新到來的用戶需求的協作進行修正。該構件庫選擇了構件功能描述中常用的且區分度較明顯的500多個詞作為功能特征關鍵詞，對從 Active-X，Alphaworks，ComponentSource以及MFC和STL等庫中選取出來的14 061個構件進行了統一的向量化功能描述。

實驗設計為：參與實驗的10人分別在基于向量空間模型的構件檢索系統中完成對 10個目標構件的 2組檢索。這10個構件的概要描述都提供給這些實驗人員。第1組實驗中，系統不支持對用戶需求的協作修正，直接用實驗人員提出的檢索需求查找相關構件，并排序返回給用戶篩選目標構件；第2組實驗中，系統開啟用戶需求協作修正功能，該系統的檢索日志庫中已經保存8 000多條歷史檢索記錄信息，并創建協作修正模型。實驗人員用同樣的檢索需求重新查找這10個目標構件，系統在進行構件檢索之前會將實驗人員的需求進行協作修正。

在實驗中，主要記錄以下2個方面信息作為實驗比較的指標：

(1) 用戶檢索目標構件所需要的平均時間(ART)。用戶檢索到目標構件的過程，包括用戶提出檢索需求、檢索系統匹配計算并反饋結果以及用戶從結果中順序查找目標構件。通過統計用戶找到目標構件的平均時間，可以比較構件檢索方法的檢索效率；平均時間越短，則檢索效率越高。

(2) 目標構件在用戶檢索結果中所處的平均位置(ATP)。在不同的檢索方法下，當用戶提出針對同一目標構件的檢索需求時，目標構件會出現在檢索結果序列的不同位置。目標構件位置越靠前，越容易被用戶找到，則表示該檢索方法的準確度越高。

在實驗中，根據實踐經驗，將協作修正的參數t設為0.3。10名實驗人員分別用無協作修正的方法和有協作修正的方法檢索10個構件，將每個構件的平均位置和平均檢索時間記錄下來，實驗結果如圖2和圖3所示。

從圖2和圖3可見：經過對用戶需求進行協作修正操作以后，構件檢索的平均時間明顯縮短，由原來的40～80 s范圍減少到30～50 s；同時，目標構件在檢索結果列表中的位置也大大提前，由原來的平均排名4～7位提高到2～4位。這說明有協作修正構件檢索與沒有協作修正的構件檢索準確度相比提高幅度較大。對于上述實驗結果，在增加了用戶需求協作修正操作的檢索實驗中，系統進行檢索操作前需要先對用戶需求進行修正，這個過程需要多消耗一個恒定的時間；但修正后的用戶需求使得目標構件在檢索結果列表中的位置提前，基本出現在列表的前10位，有利于用戶快速定位目標構件，有效縮短了整個構件檢索過程的時間。

圖2 2種方法的平均檢索時間比較Fig.2 Comparisons of ART between two methods

圖3 2種方法的目標構件位置比較Fig.3 Comparisons of ATP between two methods

實驗結果還表明：用戶在不十分了解構件的分類與描述機制時，所提出的檢索需求向量會與其實際所需要的構件向量存在一定的差異。這種差異導致并非用戶需要的構件排名靠前，影響用戶最終從結果列表中篩選構件的效率。而本文作者所提出的用戶需求協作修正方法有效地削弱了這種差異，使得用戶需求更加接近目標構件，目標構件在結果列表中的排名明顯提升，大大提高了構件的檢索效率。

4 結論

(1) 為了提高軟件復用過程中構件檢索的效率，提出了一種基于用戶需求協作修正的構件檢索方法。

(2) 采用向量對構件功能和用戶需求進行描述，以向量之間的內積相似度來檢索構件，并對檢索結果進行排序。在此基礎上，引入檢索反饋機制，基于用戶檢索歷史對用戶需求進行協作修正，并針對協作修正過程計算開銷較大的情況，推導和提取了用戶需求協作修正模型，通過增量學習機制對該模型進行維護。

(3) 基于用戶需求協作修正的構件檢索方法能明顯縮短構件檢索的時間，有效提高了構件檢索準確率，便于用戶快速定位所需構件，為構件檢索提供了新的思路。

[1]Mili H, Mili F, MILI A. Reusing software: Issues and research direction[J]. IEEE Transactions on Software Engineering, 1995,21(6): 222?232.

[2]Wolfgang P. Component-based software development: A new paradigm in software engineering?[C]//Proceedings of the 4th Asia-Pacific Software Engineering and International Computer Science Conference. Hong Kong: Springer Verlag, 1997:523?524.

[3]張堯學, 方存好. 主動服務: 概念、結構與實現[M]. 北京: 科學出版社, 2004: 29?41.

ZHANG Yao-xue, FANG Cun-hao. Active service: Concept,architecture and implementation[M]. Beijing: Science Press,2004: 29?41.

[4]Frakes W B, Pole TP. An empirical study of representation methods for reusable software components[J]. IEEE Transactions on Software Engineering. 1994, 120(8): 617?630.

[5]DOU Yu-hong, ZHANG Yao-xue, LI Xing: An XML-based software component description method for program mining[J].Chinese Journal of Electronics, 2004, 13(1): 100?104.

[6]YANG Yong, ZHANG Wei-shi, ZHANG Xiu-guo, et al. A weighted ranking algorithm for facet-based component retrieval system[C]//Proceedings of the 25th International Conference on Software Engineering. Portland: IEEE Computer Society, 2006:274?279.

[7]Shasha D, Tsong J, Wang L. Exact and approximate algorithm for unordered tree matching[J]. IEEE Trans on Systems Man and Cybernetics, 1994, 24(4): 668?678.

[8]姚全珠, 丁新村, 雷西玲, 等. 基于遺傳算法的刻面權重構件檢索方法的實現[J]. 計算機工程與應用, 2008, 44(6): 127?129.

YAO Quan-zhu, DING Xin-cun, LEI Xi-ling, et al. Implement of component retrieval method based on genetic algorithm with facet-weight[J]. Computer Engineering and Applications, 2008,44 (6): 127?129.

[9]Poulin J S, Yglesias K P. Organization and component classification in the IBM reuse library[R]. New York:Technology Support Center International Business Machines Corporation, 1993: 6?20.

[10]Morel J M, Faget J. The REBOOT environment[C]//Proceedings of the 2nd International Workshop on Software Reusability Advances in Software. Lucca: IEEE Computer Society Press,1993: 80?88.

[11]NEC Software Engineering Laboratory. NATO standard for management of a reusable software component library[C]//NATO Communications and Information Systems Agency.Tokyo, 1991: 32?43.

[12]常繼傳, 李克勤, 郭立峰, 等. 青鳥系統中可復用軟件構件的表示與檢索[J]. 電子學報, 2000, 28(8): 20?24.

CHANG Ji-chuan, LI Ke-qin, GUO Li-feng, et al. Representing and retrieving reusable software components in JB (Jadebird)system[J]. Electronica Journal, 2000, 28(8): 20?24.

[13]Gibb K, McCartan C, O’Donnell R, et al. The integration of information retrieval techniques within a software reuse environment[J]. Journal of Information Science, 2000, 26(4):520?539.

[14]王淵峰, 薛云皎, 張涌, 等. 刻面分類構件的匹配模型 [J].軟件學報, 2003, 14(3): 401?408.

WANG Yuan-feng, XUE Yun-jiao, ZHANG Yong, et al. A matching model for software component classified in faceted scheme[J]. Journal of Software, 2003, 14(3): 401?408.

[15]Salton G, Lesk M E. Computer evaluation of indexing and text processing[J]. Journal of ACM, 1968, 15(1): 8?36.

(編輯 陳愛華)

A novel component retrieval method based on collaborative revision of user requirement

ZHONG Ming1,2, ZHANG Yao-xue1,2, ZHOU Yue-zhi1,2, TIAN Peng-wei1,2, WENG Lin-kai1,2

(1. Tsinghua National Laboratory of Information Science and Technology, Tsinghua University, Beijing 100084, China;2. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)

Current methods of component retrieval focus mainly on improving the retrieval efficiency by using advanced classification and index, but ignores the discrepancy between user understanding and component description, thus a novel method for component retrieval based on collaborative revision of user requirement was proposed, which describes both components and user requirements in the format of vectors, and calculates their inner product to get the matching degree of each component. Furthermore, a model of collaborative revision was presented to collaboratively revise user’s new requirement according to the feed-back of user retrieval history, leading to minifying the discrepancy between user understanding and component description and improving the efficiency of component retrieval. Several experiments were made on the component repository prototype by the metrics of average retrieval time and average target position. The results show that, using the user requirement of collaborative revision, the vector based component retrieval method has higher retrieval accuracy and takes shorter time to find the target component.

software reuse; component retrieval; vector; collaborative revision

TP311

A

1672?7207(2011)02?0398?06

2009?11?07；

2010?03?25

國家自然科學基金資助項目(90604027)；國家“十五”計劃項目(2005BA115A02)

鐘鳴(1983?)，男，浙江紹興人，博士研究生，從事軟件復用和軟構件技術研究；電話：13810091575；E-mail：zhongm83@gmail.com

book=403,ebook=97