祝仰凱，高茂庭

（上海海事大學(xué)信息工程學(xué)院，上?！?00000）

基于增量式潛在語義分析的構(gòu)件檢索算法

祝仰凱，高茂庭

（上海海事大學(xué)信息工程學(xué)院，上海200000）

針對基于潛在語義分析的構(gòu)件檢索算法，在應(yīng)用與問題規(guī)模逐漸增大時，空間和時間復(fù)雜度也隨之提高的問題，提出一種增量式潛在語義分析的構(gòu)件檢索算法，在進(jìn)行增量矩陣的奇異值分解時，利用增量前矩陣的分解結(jié)果進(jìn)行運算，從而避免重復(fù)運算。實驗結(jié)果表明，該算法能夠提高構(gòu)件檢索效率。

潛在語義分析；增量式；構(gòu)件檢索；向量空間模型

0　引言

軟件復(fù)用是在軟件開發(fā)中，避免重復(fù)勞動的解決方案，通過復(fù)用已有的高質(zhì)量開發(fā)成果，避免重新開發(fā)可能引入的錯誤，可以降低開發(fā)費用、提高軟件開發(fā)的效率和質(zhì)量。其中，軟件構(gòu)件技術(shù)是實現(xiàn)軟件復(fù)用的重要環(huán)節(jié)，構(gòu)件庫管理是其一項主要研究內(nèi)容。構(gòu)件庫管理中有兩個核心問題：構(gòu)件分類和構(gòu)件檢索，而且，對構(gòu)件進(jìn)行合理的分類可以提高構(gòu)件的檢索效率。

每個構(gòu)件在發(fā)布時，都會有該構(gòu)件相應(yīng)描述信息，根據(jù)這些描述信息，采用某種構(gòu)件表示方法表示構(gòu)件，這樣就會產(chǎn)生一個用來描述構(gòu)件的文本。通過計算這些文本間的相似度就來得到構(gòu)件之間的相似度，來實現(xiàn)軟件構(gòu)件的檢索。

對文本的表示，Salton等人于20世紀(jì)70年代提出了向量空間模型（Vector Space Model，VSM），VSM把文本內(nèi)容表示為多維空間的向量，計算文本的相似度就轉(zhuǎn)化為了計算兩個向量。但是基于向量空間模型的文本處理方法存在高維稀疏、同義詞和多義詞的問題。1988年S.T.Dumais等人提出潛在語義分析模型（Latent Semantic Analysis，LSA），把用向量空間模型表示的文本映射到低維潛在語義空間中，通過映射實現(xiàn)了對矩陣降維，同時去除原始向量空間中的一些“噪音”，凸顯文本的語義特征，這個映射通過對文檔-詞條矩陣進(jìn)行奇異值分解（Singular Value Decomposition，SVD）來實現(xiàn)[1]。

使用潛在語義分析模型來處理構(gòu)件文本，實現(xiàn)構(gòu)件檢索，可以提高信息檢索精度。但是構(gòu)件庫中的構(gòu)件數(shù)量是不斷增多的，隨著構(gòu)件庫規(guī)模逐漸增大，需要經(jīng)常性地進(jìn)行奇異值分解，而奇異值分解的空間和時間復(fù)雜度較高，將導(dǎo)致構(gòu)件的檢索效率不高。因此，本文提出增量式潛在語義分析的構(gòu)件檢索算法，在進(jìn)行增量矩陣的奇異值分解時，利用增量前矩陣的分解結(jié)果進(jìn)行運算，減少計算量，提高檢索效率。

1　基本概念

1.1構(gòu)件表示

目前構(gòu)件檢索大部分都是基于刻面分類表示的，刻面具有靈活的多角度描述的特點，可以全面地描述構(gòu)件。其中，刻面分類方法[2-3]以刻面的完整性和獨立性定義了4個刻面：

（1）構(gòu)件類別：如系統(tǒng)工具、數(shù)據(jù)庫相關(guān)、用戶界面等；

（2）構(gòu)件功能：構(gòu)件功能描述，應(yīng)用領(lǐng)域；

（3）運行環(huán)境：軟件環(huán)境和硬件環(huán)境；

（4）表示方法：構(gòu)件形態(tài)（如類、構(gòu)架、框架、模式）和開發(fā)語言。

采用構(gòu)件文本來標(biāo)識構(gòu)件后，就可以用文本信息檢索的方法來實現(xiàn)檢索構(gòu)件。在構(gòu)件VSM模型中，每個構(gòu)件文本被描述成由特征詞組成的特征向量，每個特征詞被視為特征空間中的一維。這樣，構(gòu)件文本的相似度計算問題轉(zhuǎn)化為特征向量空間中的向量相似度計算問題，兩個文本間的相似程度可以用對應(yīng)向量間的夾角余弦來度量，夾角越小，余弦值越大，說明文本間相似度越高，反之則相似度越低。VSM是基于特征詞之間關(guān)系相互獨立的假設(shè)，文本向量空間具有高維性和稀疏性的特點，而在文本中出現(xiàn)的詞通常存在一定的相關(guān)性，所以VSM也無法解決同義詞和多義詞的問題。

LSA是一種新的信息檢索代數(shù)模型[4]，解決了檢索中的同義詞、多義詞問題，減小了問題的規(guī)模，并且使得原本稀疏的數(shù)據(jù)不再稀疏。潛在語義分析中可以通過對文檔-詞條矩陣的奇異值分解（SVD）來實現(xiàn)的映射。

對一個文本集D=（d1，d2，…，dm）T，進(jìn)行潛在語義分析的過程如下：

（1）將文本集D用一個m×n的文檔-詞條矩陣A [aij]，m>>n，1≤i≤m，1≤j≤n表示，其中，m表示文本個數(shù)，n表示文本集中所包含的詞條數(shù)，即列代表詞條向量，行代表文本向量；aij代表詞條在文本集中的權(quán)重；

（2）對文檔-詞條矩陣A進(jìn)行奇異值分解（SVD），此時矩陣A可表示為3個矩陣的乘積：A=UΣVT；

（3）對奇異值分解后的矩陣進(jìn)行降維，把矩陣Σ對角線上的值由大到小排列，保留Σ的前K個奇異值，得到ΣK，相應(yīng)的保留U、V的前K個列向量，分別為UK、VK；

下面對LSA中用到的奇異值分解進(jìn)行簡單介紹：

①奇異值的定義

定義設(shè)A∈Rm×n，且ATA的特征值為：

②奇異值分解定理

LSA利用了奇異值分解對文檔-詞條矩陣進(jìn)行降維的方法處理文檔和詞條，然而奇異值分解的空間和時間復(fù)雜度較高，隨著問題規(guī)模逐漸增大，需經(jīng)常性地進(jìn)行奇異值分解，將導(dǎo)致構(gòu)件的檢索效率降低。

1.2構(gòu)件相似度計算

用戶輸入一個查詢字符串q，要比較查詢字符串與已有文檔的相似性，需要把查詢字符串映射到語義空間，本文采用余弦相似度。計算過程如下：

（1）將查詢字符串以處理構(gòu)件文本的同樣方式構(gòu)造查詢向量，然后將其映射到語義空間：

（2）計算q*和dj的相似度：

式（1）中，q*為查詢向量，dj為矩陣UK中的第j個文本向量，k為語義空間的維數(shù)，aqm、ajm分別為q*、dj中的第m維權(quán)值。

2　基于增量式潛在語義分析的構(gòu)件檢索算法

潛在語義分析利用奇異值分解將文檔映射到低維的潛在語義空間中。由于奇異值分解的時間復(fù)雜度較高，隨著問題規(guī)模的逐漸增大，重新進(jìn)行奇異值分解，會影響構(gòu)件的檢索效率。因此，本文提出一種增量式潛在語義分析的構(gòu)件檢索算法，在計算增量后矩陣的奇異值分解時，利用增量前矩陣的分解結(jié)果進(jìn)行運算，從而避免重復(fù)運算，提高檢索效率。利用增量式奇異值分解的潛在語義分析我們稱之為增量式潛在語義分析算法。

2.1增量式奇異值分解

設(shè)矩陣A是m×n的矩陣，當(dāng)矩陣A增加一行時，得到矩陣A'，此時需要計算矩陣A'的奇異值分解，若對矩陣A'重新進(jìn)行SVD分解，則復(fù)雜度較高，為此，考慮利用已有的矩陣A的SVD分解結(jié)果。

文獻(xiàn)[5]中介紹了矩陣A增加一行以及增加一列之后的奇異值分解算法，對于大型構(gòu)件庫而言，由于構(gòu)件文本的個數(shù)遠(yuǎn)大于詞條的個數(shù)，因此，本文只考慮矩陣A增加一行的情況。假定在矩陣A的最后增加一行，即

利用矩陣A的奇異值分解的結(jié)果，來計算A'的奇異值，計算過程如下：

（3）利用1.2小節(jié)中的方法，對矩陣M進(jìn)行奇異值分解：

（4）對矩陣A'進(jìn)行奇異值分解：

2.2矩陣M的奇異值分解

本文引用文獻(xiàn)[6]中計算矩陣M的奇異值分解的方法，通過計算矩陣的奇異值分解來近似的計算矩陣M的奇異值分解。

（1）計算矩陣M的奇異向量

公式（3）稱為久期函數(shù)[7]，通過求解它的根，計算出矩陣M的近似奇異值，然后利用公式（4）構(gòu)建矩陣：

（2）計算矩陣M的奇異值

1）當(dāng)1≤j≤n-1時，

通過計算方程組：

得到奇異值sj（1≤j≤n-1）。

得到奇異值sj（1≤j≤n-1）。

2）當(dāng)j=n時，通過計算方程組

得到奇異值sn。

通過這種方法來計算矩陣M的奇異值分解的復(fù)雜度為O（n2）。

增量式潛在語義分析算法首先對文檔集進(jìn)行中文分詞、權(quán)重計算生成文檔-詞匯矩陣，然后對該矩陣進(jìn)行奇異值分解，并保留分解結(jié)果，當(dāng)有新的文檔加入時，利用上次奇異值分解結(jié)果進(jìn)行運算，構(gòu)造潛在語義空間。增量式潛在語義分析算法的流程圖如圖1。

2.3基于增量式潛在語義分析的構(gòu)件檢索算法

基于增量式潛在語義分析的構(gòu)件檢索算法通過增量式奇異值分解算法，利用上一步分解結(jié)果來提高構(gòu)件檢索的效率，其處理過程分為以下七步：

Step1采用刻面分類方法表示構(gòu)件，使每個構(gòu)件對應(yīng)于一個文檔，從而形成一個構(gòu)件文檔集，并將其作為輸入數(shù)據(jù)；

Step2利用增量式潛在語義分析算法處理構(gòu)件文檔集，構(gòu)造潛在語義空間；

Step3根據(jù)公式（1）對用戶輸入的查詢字符串建立提問式；

Step4根據(jù)公式（2）計算查詢字符串向量與構(gòu)件間的相似度值Sim（q*，dj）；

Step5根據(jù)相似度由高到低對構(gòu)件文檔進(jìn)行排序，輸出結(jié)果。

圖1　增量式潛在語義分析算法的流程圖

3　實驗結(jié)果及分析

為了驗證本文算法有效性，將本文提出的基于增量式潛在語義分析構(gòu)件檢索算法與基于潛在語義分析構(gòu)件檢索算法進(jìn)行性能實驗對比。

實驗數(shù)據(jù)為從網(wǎng)上搜集構(gòu)建的一個包含1500個構(gòu)件的構(gòu)件庫，包含三大主題：數(shù)據(jù)庫相關(guān)、用戶界面、系統(tǒng)工具。獲取構(gòu)件庫中描述構(gòu)件的文本集，利用Python進(jìn)行文本分詞及關(guān)鍵詞提取，對于構(gòu)件文本中關(guān)鍵詞權(quán)重的計算采用TF-IDF方法[4]。

3.1構(gòu)件檢索性能評價指標(biāo)

采用查準(zhǔn)率，查全率以及算法的時間復(fù)雜度3個指標(biāo)對本文算法進(jìn)行評估。

查全率（R）：檢索系統(tǒng)在進(jìn)行某一檢索時，檢索出正確匹配的構(gòu)件文本數(shù)與系統(tǒng)中所有正確構(gòu)件文本數(shù)的比率，它反映了該構(gòu)件庫中實有的相關(guān)構(gòu)件量在多大程度上可以被正確檢出。

其中，Dr表示檢索出的正確構(gòu)件文本數(shù)，Dt表示所有正確構(gòu)件文本數(shù)。

查準(zhǔn)率（P）：檢索系統(tǒng)在進(jìn)行某一檢索時，檢索出的正確構(gòu)件文本數(shù)與檢索出的構(gòu)件文本數(shù)的比率，它反映了每次從該構(gòu)件庫中實際檢出的全部構(gòu)件中有多少是相關(guān)的。

P=Dr/Da（12）

其中，Dr表示檢索出的正確構(gòu)件文本數(shù)，Da表示檢索出的構(gòu)件文本數(shù)。

3.2實驗結(jié)果與分析

該實驗是當(dāng)構(gòu)件庫中新增加一個構(gòu)件時，基于LSA構(gòu)件檢索算法和基于增量式LSA構(gòu)件檢索算法對構(gòu)件庫中構(gòu)件檢索的查準(zhǔn)率、查全率和查詢效率的比較，結(jié)果分別見圖1、圖2、圖3。

從圖1和圖2可以看出，基于增量式LSA構(gòu)件檢索算法與基于LSA構(gòu)件檢索算法的查準(zhǔn)率和查全率基本相似。從圖3可以看出，本文提出的基于增量式LSA構(gòu)件檢索算法時間性能上明顯優(yōu)于基于LSA構(gòu)件檢索算法。原因主要是對更新后的文檔-詞條矩陣進(jìn)行奇異值分解時，利用了更新前的分解結(jié)果，避免了重新進(jìn)行一次奇異值分解的重復(fù)計算。

4　結(jié)語

本文提出了一種增量式潛在語義分析的構(gòu)件檢索算法，克服了當(dāng)構(gòu)件庫的規(guī)模逐漸增大時，運算復(fù)雜度較高的弊端。實驗結(jié)果表明，該算法能夠提高構(gòu)件檢索效率，有利于軟件復(fù)用。但是本文只考慮了向構(gòu)件庫中添加構(gòu)件的情況，因此，下一步將研究從構(gòu)件庫中刪除構(gòu)件的情況。

圖1　兩種構(gòu)件檢索算法查準(zhǔn)率的比較

圖2　兩種構(gòu)件檢索算法查全率的比較

圖3　兩種構(gòu)件檢索算法效率的比較

[1]任姚鵬,陳立潮等.基于潛在語義分析的構(gòu)件聚類改進(jìn)方法[J].計算機工程,2011,37(4):67-68.

[2]張玉芳,彭時名,呂佳.基于文本分類的TFIDF方法的改進(jìn)與應(yīng)用[J].計算機工程,2006,32(19):76-78.

[3]劉大昕,趙磊,王卓.一種基于刻面分類和聚類分析的構(gòu)件分類檢索方法[J].計算機應(yīng)用,2004,24(2):89-90.

[4]Dumais S T.Using Latent Semantic Analysis to Improve Information Retrieval[C].Proceedings of the ACM Conference on Human Factors in Computing Systems.Washington D.C.USA:ACM Press,1988:281-285.

[5]James R.Bunchand Christopher P.Nielsen.Updating the Singular Value Decomposition.Numer.Math,1978,31:111-129.

[6]M.Gu,S.C.Eisenstat.A Stable and Fast Algorithm for Updating the Singular Value Decomposition.Tech.Report,RR-966,Yale University,1994.

[7]趙鑠乂.基于MapReduce的奇異值分解方法研究[D].武漢:華中科技大學(xué),2014.

Latent Semantic Analysis;Incremental;Component Retrieval;VSM

Component Retrieval Algorithm Based on Incremental Latent Semantic Analysis

ZHU Yang-kai，GAO Mao-ting

（College of Information Engineering,Shanghai Maritime University,Shanghai 200000）

The spatial and time complexity of the component retrieval method based on latent semantic analysis is increased while the application scale is gradually increasing.Proposes an incremental latent semantic analysis method to avoid duplication by using the result of the decomposition of the last step to do the singular value decomposition for the incremental matrix.Experimental results show that this method can improve the retrieval efficiency of the component.

1007-1423（2016）32-0020-06

10.3969/j.issn.1007-1423.2016.32.005

祝仰凱（1991-），男，河南濮陽人，碩士研究生，研究方向為為軟件工程

高茂庭（1963-），男，博士，教授，系統(tǒng)分析員，CCF高級會員，研究方向為智能信息處理、數(shù)據(jù)庫與信息系統(tǒng)

2016-08-16

2016-10-16