基于VSM的潛在語(yǔ)義索引

王 瑛

(閩江學(xué)院教務(wù)處, 福建 福州 350108)

0 前 言

現(xiàn)在主流搜索引擎，如Google、百度等采用的都是存典型的搜索引擎排序技術(shù)，主要采用超鏈分析排序技術(shù).Web檢索采用的是基于布爾模型(Boolean Model)的關(guān)鍵詞的檢索技術(shù)，采用“and ”、“or”、“ not”等布爾關(guān)系來(lái)組合各個(gè)關(guān)鍵詞進(jìn)行檢索，然后對(duì)檢索結(jié)果文檔進(jìn)行倒排序.這樣很容易產(chǎn)生由于關(guān)鍵詞的機(jī)械字符匹配和一詞多義問題很容易造成漏檢和錯(cuò)檢，檢索的查全率和查準(zhǔn)率比較低，造成的后果是檢索結(jié)果往往不是檢索者的本意.

例如：在多義詞檢索時(shí)，輸入檢索內(nèi)容為“蘋果”，輸出的檢索結(jié)果可能是“蘋果”牌的電腦，也可能是“蘋果”這種水果的介紹，甚至可能是“蘋果”這部電影的宣傳資料.再例如在同義詞檢索時(shí)，輸入內(nèi)容為“微機(jī)”，輸入檢索內(nèi)容有“微機(jī)原理”這門課程的介紹，有“微機(jī)”考試的介紹，搜索引擎是不理解檢索者對(duì)“微機(jī)”、“計(jì)算機(jī)”、“個(gè)人電腦”、“個(gè)人計(jì)算機(jī)”等詞匯是同一個(gè)潛在含義的不同表示方式，而檢索者個(gè)人的習(xí)慣輸入方式是各不相同的，這也就造成了檢索結(jié)果的多樣性和不確定性.同時(shí)關(guān)鍵詞的語(yǔ)義蘊(yùn)涵擴(kuò)展性也十分機(jī)械，不能達(dá)到檢索詞的相關(guān)語(yǔ)義擴(kuò)展，如查詢“研究生”這個(gè)關(guān)鍵詞時(shí)，“碩士研究生”、“博士研究生”、甚至“Graduate”這個(gè)外文詞匯都應(yīng)該是這個(gè)關(guān)鍵詞的蘊(yùn)涵檢索內(nèi)容.

由于布爾模型的不足，現(xiàn)在發(fā)展出向量空間模型(Vector Space Model，VSM)[1]、概率模型(Probabilistic Model)[2]、 潛在語(yǔ)義索引(LSI) (Latent Semantic Indexing)[3]等.其中潛在語(yǔ)義索引(LSI) 是近年來(lái)比較有效的一種智能型的信息檢索模式，它可以解決基于關(guān)鍵詞檢索中遇到的同義詞和多義詞的問題.

1 信息檢索方法

1.1 潛在語(yǔ)義索引

潛在語(yǔ)義索引最初是一種知識(shí)的自動(dòng)提取和表示的方法，近年來(lái)廣泛地應(yīng)用到文本檢索中，LSI模型的優(yōu)點(diǎn)是克服了VSM模型不考慮詞間依賴關(guān)系的缺點(diǎn)，一定程度上解決了一詞多義的問題，將原始的向量空間轉(zhuǎn)化為體現(xiàn)特征項(xiàng)之間潛在語(yǔ)義關(guān)系的語(yǔ)義空間，查詢內(nèi)容在語(yǔ)義空間上進(jìn)行表示和比較，使得孤立的關(guān)鍵詞包含了一定的語(yǔ)義關(guān)系，從而達(dá)到自然語(yǔ)言層面的檢索.但LSI模型也有不足，它需要通過奇異值分解(Singular Valued Decomposition，SVD)來(lái)模擬關(guān)鍵詞與文獻(xiàn)之間的關(guān)系，其算法比較耗時(shí)，特別是當(dāng)原始的文本-特征矩陣維數(shù)比較大時(shí)，計(jì)算量和存儲(chǔ)空間更大，另外由于該方法的本質(zhì)只是數(shù)據(jù)在幾何空間上的變換，只是自然語(yǔ)句單詞的匯總，和自然語(yǔ)言的整句語(yǔ)義所表達(dá)的信息還有一定的差別，并沒有包含整個(gè)自然語(yǔ)句中更深層次的語(yǔ)義關(guān)聯(lián)信息.針對(duì)這些問題，本文提出了一種基于向量空間模型的潛在語(yǔ)義索引的改進(jìn)算法.

1.2 向量空間模型

基于向量空間模型的檢索基本工作原理如下：

將Web頁(yè)面文檔所具有的各個(gè)特征項(xiàng)作為文檔表示的坐標(biāo)，以向量形式把文檔表示為多維空間中的一個(gè)點(diǎn)，向量空間由一組線性無(wú)關(guān)的基本向量組成，并以特定的方式為每個(gè)特征項(xiàng)賦予不同的權(quán)重系數(shù)，向量維數(shù)與向量空間維數(shù)一致，并可以通過向量空間進(jìn)行描述，這樣就將Web頁(yè)面文檔用空間中的一個(gè)特征向量來(lái)進(jìn)行描述.

數(shù)學(xué)模型描述如下[4,5]：

定義1 文檔D(Document)為Web 頁(yè)面上的一個(gè)文檔或一個(gè)文檔的片段，或者為一個(gè)數(shù)據(jù)庫(kù)中的全部字段信息.

定義2 特征t(Term)為文檔中能夠代表文檔屬性的信息的基本評(píng)議單位，可以是字、詞等，也就是檢索中的關(guān)鍵詞，文檔D可以表示成為D(t1,t2,…,tn)，其中n為檢索關(guān)鍵詞的數(shù)量，t為特征項(xiàng).在Web頁(yè)面進(jìn)行檢索時(shí)，每一個(gè)向量對(duì)應(yīng)一個(gè)URL.

圖1 文檔向量空間及相似度計(jì)算

定義3 特征項(xiàng)權(quán)重W(Weight)為特征項(xiàng)tn能夠代表文檔D能力的大小，體現(xiàn)了特征項(xiàng)t在文檔D中的重要程度.在檢索查詢過程中，用戶輸入檢索的關(guān)鍵詞表達(dá)式，對(duì)輸入表達(dá)式進(jìn)行特征項(xiàng)分析，賦予每一個(gè)特征項(xiàng)不同的權(quán)重W，當(dāng)檢索查詢內(nèi)容匹配時(shí)，給予D對(duì)應(yīng)的特征項(xiàng)t的權(quán)重W值為1，否則給予權(quán)重W值為0.

定義4 相似度S(Similarity)為文檔D與其它文檔內(nèi)容相關(guān)程度的多少，使用特征向量來(lái)表示時(shí)，可以使用向量文檔D之間的距離來(lái)衡量，用內(nèi)積或夾角θ的余弦值來(lái)衡量.夾角θ越小說明相似度S越高，否則相似度S越小，通過計(jì)算每個(gè)文檔向量與查詢向量的相似度，將排序結(jié)果與設(shè)立的閾值進(jìn)行比較，取大于閾值的Web頁(yè)面進(jìn)行倒排序，即可輸出最終的Web頁(yè)面檢索結(jié)果，如圖1所示.

2 改進(jìn)的算法

2.1 算法描述

基于向量空間模型在潛在語(yǔ)義索引，其主要思想是對(duì)文檔向量空間進(jìn)行降維，即使用一個(gè)超平面將兩類文檔的數(shù)據(jù)點(diǎn)正確分開，且兩類數(shù)據(jù)點(diǎn)與分類面距離最遠(yuǎn)[6].

其算法描述如下：

任意一個(gè)的檢索關(guān)鍵詞的語(yǔ)句表達(dá)式集合：

(xk,yk)k=1, 2, …,N,xk∈Rn,yk∈R

其中xk為輸入值，yk為映射點(diǎn).利用高維特征空間中的線性函數(shù)可以將特征空間表示為：

y(x)=wTφ(x)+b

其中非線性映射φ(x)將輸入向量映射成一個(gè)高維特征空間，b為其偏離值，w為特征空間同一方向的加權(quán)向量.

(ak,S為拉格朗日函數(shù)的乘數(shù)，頂點(diǎn)可以通過設(shè)偏導(dǎo)數(shù)為零求得)

根據(jù)Karush-Kuhn-Tucker(KKT)必要性條件可以消除ek和ω得到以下線性方程組：

在這里因?yàn)槭褂昧撕撕瘮?shù)，高斯核函數(shù)變換為K(x′)=exp(-‖x-x′‖2/2σ2).

2.2 算法驗(yàn)證

當(dāng)使用N個(gè)向量數(shù)據(jù)來(lái)建立模型時(shí)，首先令：

則根據(jù)KKT條件消除ek和ω后得到的線性方程組：

可以得到如下推論：

2.3 檢索步驟

基于向量空間模型的潛在語(yǔ)義索引主要步驟如下:

步驟1 建立文檔關(guān)鍵詞的向量矩陣,并對(duì)其進(jìn)行歸一化，利用高維特征空間中的線性函數(shù)可以將特征空間進(jìn)行表示；

步驟2 對(duì)文檔關(guān)鍵詞向量矩陣進(jìn)行奇異值分解，并將用戶查詢向量投影到變換后的文檔向量矩陣空間中；使用低維的關(guān)鍵詞文檔向量替代原有的關(guān)鍵詞的文檔向量，以處理大規(guī)模文檔集，提高信息檢索的精確度和效率.

步驟3 根據(jù)某種向量間的相似性度S量(向量距離公式或向量夾角θ的余弦公式),查找和用戶查詢最相似的文檔集合,即夾角θ值最小的文檔集，并按相似度取大于閾值的Web頁(yè)面進(jìn)行倒排序[7].

步驟4 根據(jù)用戶對(duì)查詢結(jié)果的關(guān)注程度，挑選出用戶所關(guān)注的關(guān)鍵詞集，并根據(jù)該關(guān)鍵詞集的內(nèi)容進(jìn)行語(yǔ)義擴(kuò)展，找出用戶潛在的語(yǔ)義信息集，重新構(gòu)造查詢，查找和新查詢最相似的文檔，這一過程可以循環(huán)進(jìn)行下去，直到用戶滿意為止.

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

使用MATLAB進(jìn)行驗(yàn)證計(jì)算，對(duì)一個(gè)有10 000篇文檔的小規(guī)模網(wǎng)絡(luò)數(shù)據(jù)庫(kù)進(jìn)行測(cè)試，數(shù)據(jù)庫(kù)容量約為10 MB，系統(tǒng)運(yùn)行硬件環(huán)境為Pentium(R)4 CPU 3.00 GHz，內(nèi)存為1 G；軟件環(huán)境為Microsoft Windows XP(Service Pack 3).經(jīng)過檢索實(shí)驗(yàn)，產(chǎn)生的查詢文件約2 MB，整個(gè)計(jì)算過程耗時(shí)5 min左右.

表1 對(duì)比實(shí)驗(yàn)結(jié)果

對(duì)比傳統(tǒng)的關(guān)鍵詞查詢，該算法查準(zhǔn)率在不限定輸入的情況下，檢索結(jié)果只有10%左右，在限定輸入的情況下也只能達(dá)到目的55%左右；查全率在兩種情況下都可以達(dá)到90%以上.該實(shí)驗(yàn)結(jié)果比傳統(tǒng)的關(guān)鍵詞查詢的查準(zhǔn)率有所提高，查全率基本相當(dāng).

4 結(jié)束語(yǔ)

基于向量空間模型的潛在語(yǔ)義索引技術(shù)與傳統(tǒng)的檢索技術(shù)相比，在實(shí)際應(yīng)用中具有一定的優(yōu)越性，它反映的不再是詞的簡(jiǎn)單出現(xiàn)頻度和分布關(guān)系，而是強(qiáng)化的語(yǔ)義關(guān)系，本文提出了該技術(shù)的一種算法關(guān)鍵技術(shù)，但由于在查詢語(yǔ)句的自然語(yǔ)言語(yǔ)句包括有一些虛詞(不包括內(nèi)容含義的詞)，或者在分割單詞時(shí)出現(xiàn)的錯(cuò)誤，部分影響了檢索的查準(zhǔn)率，還不能完全解決潛在語(yǔ)義的檢索問題，因此今后應(yīng)在如何提高查準(zhǔn)率上進(jìn)行更深入的研究，以解決潛在語(yǔ)義索引的實(shí)際效果問題.

參考文獻(xiàn)

[1] Salton G, Wang A, Yang C S A. Vector space model for information retrieve[J]. Journal of the American Society for Information Science, 1975,18(11):613-620.

[2] 陶 蕾.一種智能型的信息檢索方法:隱含語(yǔ)義索引法[J].情報(bào)理論與實(shí)踐,2004,27(3):308-309.

[3] 蓋 杰.基于潛在語(yǔ)義分析的信息檢索[J].計(jì)算機(jī)工程,2004,30(1):58-60.

[4] 朱華宇,孫正興,孫福炎.一個(gè)基于向量空間模型的中文文本自動(dòng)分類系統(tǒng)[J].計(jì)算機(jī)工程,2001,27(2)：15-17.

[5] 張?jiān)?趙仲孟,沈鈞毅.一種基于空間模型的個(gè)性化搜索引擎研究[J].微電子學(xué)與計(jì)算機(jī),2003,(11)：52-55.

[6] 戚 涌,徐永紅,劉鳳玉.基于潛在語(yǔ)義標(biāo)引的 WEB 文檔自動(dòng)分類[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(22):28-31.

[7] 周 文,龔禮明,蔣 嵐.隱含語(yǔ)義檢索及中文樣本分析實(shí)例[J].計(jì)算機(jī)應(yīng)用,2004,24(1):273-276.