祝仰凱，高茂庭

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

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

祝仰凱，高茂庭

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

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

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

0　引言

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

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

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

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

1　基本概念

1.1構(gòu)件表示

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

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

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

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

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

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

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

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

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

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

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

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

①奇異值的定義

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

②奇異值分解定理

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

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

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

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

（2）計(jì)算q*和dj的相似度：

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

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

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

2.1增量式奇異值分解

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

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

利用矩陣A的奇異值分解的結(jié)果，來(lái)計(jì)算A'的奇異值，計(jì)算過(guò)程如下：

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

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

2.2矩陣M的奇異值分解

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

（1）計(jì)算矩陣M的奇異向量

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

（2）計(jì)算矩陣M的奇異值

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

通過(guò)計(jì)算方程組：

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

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

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

得到奇異值sn。

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

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

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

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

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

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

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

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

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

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

3　實(shí)驗(yàn)結(jié)果及分析

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

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

3.1構(gòu)件檢索性能評(píng)價(jià)指標(biāo)

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

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

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

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

P=Dr/Da（12）

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

3.2實(shí)驗(yàn)結(jié)果與分析

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

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

4　結(jié)語(yǔ)

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

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

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

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

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

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

[3]劉大昕,趙磊,王卓.一種基于刻面分類和聚類分析的構(gòu)件分類檢索方法[J].計(jì)算機(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-），男，河南濮陽(yáng)人，碩士研究生，研究方向?yàn)闉檐浖こ?/p>

高茂庭（1963-），男，博士，教授，系統(tǒng)分析員，CCF高級(jí)會(huì)員，研究方向?yàn)橹悄苄畔⑻幚?、?shù)據(jù)庫(kù)與信息系統(tǒng)

2016-08-16

2016-10-16