基于奇異值分解的ｗｅｂ信息檢索模式

[摘 要] 針對(duì)傳統(tǒng)信息檢索搜索時(shí)間慢、空間占用量大的問(wèn)題，提出了一種基于奇異值分解和歐氏距離算法的信息檢索算法。該算法降低了信息檢索時(shí)間復(fù)雜度和空間復(fù)雜度，實(shí)驗(yàn)證明了該算法的有效性。

[關(guān)鍵詞] 信息檢索 奇異值分解 歐氏距離 Salton向量空間模型

隨著因特網(wǎng)上信息資源種類及數(shù)量不斷擴(kuò)大，研究高效的信息檢索方法成了一個(gè)非常重要的課題。信息檢索就是借助一定的設(shè)備與工具，采用一系列方法與策略從數(shù)據(jù)庫(kù)中查找出所需信息。基于查詢串的文檔信息檢索接收用戶從瀏覽器提交的信息串，經(jīng)網(wǎng)絡(luò)傳輸后提交相關(guān)的信息檢索，并將最終結(jié)果按照一定排序規(guī)則排序后傳輸給用戶，這種檢索方式具有較好的用戶交互能力。

近年來(lái)很多科研工作者致力于基于關(guān)鍵字的文檔檢索領(lǐng)域方面研究，并成功應(yīng)用于各種Web應(yīng)用中。Salton等人提出的向量空間模型將文檔和用戶查詢轉(zhuǎn)化為向量形式，根據(jù)向量之間的相似程度對(duì)所有返回結(jié)果進(jìn)行排序，并在搜索引擎系統(tǒng)中得到了較為廣泛的應(yīng)用。

一、利用Salton向量空間模型實(shí)現(xiàn)信息檢索的算法

第一，構(gòu)造特征項(xiàng)庫(kù)。輸入文檔集合中的特征項(xiàng)，并建立特征項(xiàng)庫(kù)；

第二，建立文檔信息。將文檔內(nèi)容輸入數(shù)據(jù)庫(kù)，建立文檔信息庫(kù)；

第三，構(gòu)造文檔向量信息庫(kù)。對(duì)每個(gè)文檔信息依據(jù)公式(1)，計(jì)算每一個(gè)特征項(xiàng)的權(quán)值，并構(gòu)建相應(yīng)的文檔向量；

第四，查詢文檔。用戶輸入查詢條件，利用布爾模型得到查詢條件的文檔向量，再利用公式(2)與每一個(gè)文檔向量進(jìn)行計(jì)算得到該查詢條件與文檔的相似度；

第五，排序輸出結(jié)果。按照第四步所計(jì)算出來(lái)的相似度大小排序輸出查詢結(jié)果。

定義1 特征項(xiàng)t:是指出現(xiàn)在文檔d中且能夠代表該文檔性質(zhì)的基本語(yǔ)言單位。

定義2 特征項(xiàng)權(quán)值Wik:是指特征項(xiàng)tk代表文檔di的能力大小。Wik的計(jì)算采用特征項(xiàng)頻率tfik和反比頻率idfk計(jì)算。

wik=tfik+idfk=tfik *(log2 (N/nk)+1) 公式（１）

其中，tfik表示特征項(xiàng)tk在文檔di(i=1，……，N)中出現(xiàn)的頻率，N代表文檔集合中的文檔數(shù)量，nk代表在文檔集合中出現(xiàn)特征項(xiàng)tk的文檔數(shù)目。

定義3 文檔向量:設(shè)文檔集合中共有m個(gè)不同的特征項(xiàng)t1，t2，……tm，分別計(jì)算文檔di(i=1，……，N)的特征項(xiàng)t1，t2，……，tm的特征項(xiàng)權(quán)值，由這些特征項(xiàng)權(quán)值所構(gòu)成的向量(wi1，wi2，……，wim，.)成為文檔di的向量。

由于特征項(xiàng)t1，t2，……tm互不相同，可以將文檔向量看作是m維歐氏空間的向量。這樣，文檔之間的相似程度通過(guò)向量的形式轉(zhuǎn)化為向量之間的數(shù)學(xué)計(jì)算模式，使得在進(jìn)行文檔歸類以及查詢匹配過(guò)程中的計(jì)算過(guò)程比較簡(jiǎn)單、快速。

定義4 相似度:兩文檔向量之間相似的距離程度記為相似度。文檔di、dj相似度定義為di、dj所對(duì)應(yīng)的文本向量之間的夾角余弦：

公式(2）

在進(jìn)行查詢匹配時(shí)，查詢條件QS的向量化過(guò)程可采用布爾模型進(jìn)行：

即特征向量tj出現(xiàn)在查詢條件QS中，則Qj為1，否則為0。

二、問(wèn)題提出

利用傳統(tǒng)向量空間模型可以定量計(jì)算查找字符串和數(shù)據(jù)庫(kù)字符串的相似程度，但隨著數(shù)據(jù)庫(kù)表記錄的增大，特征值變得很大，對(duì)應(yīng)文檔向量的維數(shù)急劇上升，嚴(yán)重影響查找效率。

三、基于奇異值分解的信息檢索算法

奇異值分解通過(guò)數(shù)據(jù)降維方法發(fā)現(xiàn)高維數(shù)據(jù)之間的潛在關(guān)系，得到的奇異值向量(σ1，σ2，…，σr)是惟一的，它刻畫了矩陣數(shù)據(jù)的分布特征，保留了矩陣的代數(shù)本質(zhì)，因此可以將奇異值向量作為文檔矩陣的代數(shù)特征。而奇異值向量將文檔向量映射到一個(gè)子空間，提高了運(yùn)算效率，因此可以將奇異值向量作為文檔向量矩陣的代數(shù)特征。

引理1 奇異值分解:對(duì)于任一實(shí)矩陣Am×n，秩(A)=r，則存在兩個(gè)標(biāo)準(zhǔn)正交矩陣Um×m和Vn×n以及對(duì)角陣Dm×n，使得A=UDVT。其中，，=diag(σ1，σ2，…，σr)，Um×m=(u1，u2，…，ur，ur+1，…，um)，Vn×n=(V1，V2，…，vr，vr+1，…，vn)。

稱為矩陣A的奇異值，λ1≥λ2≥…≥λr≥0，λr+1=λr+2=…=λn=0是矩陣ATA和AAT的特征值。ui，vi(i=1，2，…，r)分別是ATA和AAT對(duì)應(yīng)于非零特征值λi的特征向量。

在Salton向量空間模型實(shí)現(xiàn)信息檢索算法的第三步構(gòu)造文檔向量信息庫(kù)之后，對(duì)每個(gè)文檔特征向量進(jìn)行奇異值分解，然后在文檔查詢時(shí)，對(duì)查詢條件的文檔向量也要進(jìn)行奇異值分解，然后利用歐氏距離計(jì)算奇異值分解后的文檔特征向量與查詢條件的文檔向量的相似度，最后排序輸出結(jié)果。

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

從萬(wàn)方數(shù)字化期刊中隨機(jī)抽取期刊論文20篇，得到文檔集合的關(guān)鍵字特征項(xiàng)共50個(gè)。

由Salton向量空間模型算法得到文檔向量。因?yàn)閷?duì)文本信息處理過(guò)程中，一般基于單詞與單詞之間互相獨(dú)立的假設(shè)來(lái)降低文本信息處理的復(fù)雜度，所以把文檔向量轉(zhuǎn)換成m×n的矩陣。結(jié)果如下圖所示：

文檔矩陣經(jīng)過(guò)奇異值分解后，得到對(duì)應(yīng)的奇異值向量如下：

文檔1的特征值向量:（1.4862）

文檔5的特征值向量:（2.1478，0.5503）。

在查詢條件中先后輸入文檔1、文檔2、文檔4、文檔5，進(jìn)行實(shí)驗(yàn)，得到歐式距離結(jié)果如下：

可見，如果在查詢算法可靠的情況下，當(dāng)查詢條件中輸入文檔1的關(guān)鍵字時(shí)，文檔1對(duì)應(yīng)的歐氏距離是最小的。同樣當(dāng)查詢條件中輸入文檔2的關(guān)鍵字時(shí)，文檔2對(duì)應(yīng)的歐氏距離是最小的。從上表的實(shí)驗(yàn)結(jié)果可以看出，當(dāng)在查詢條件中輸入文檔1的關(guān)鍵字時(shí)，得到的文檔1歐氏距離在文檔集合中排第二；當(dāng)在查詢條件中輸入文檔2的關(guān)鍵字時(shí)，得到的文檔2歐氏距離在文檔集合中排第二；當(dāng)在查詢條件中輸入文檔4的關(guān)鍵字時(shí)，得到的文檔4歐氏距離在文檔集合中排第一。所以當(dāng)按相似度的大小顯示滿足一定閾值的一系列文章時(shí)，奇異值分解具有很高的查全率和查準(zhǔn)率。

五、結(jié)論

上述實(shí)驗(yàn)證明，本文提出的基于奇異值分解和歐氏距離算法的信息檢索算法和傳統(tǒng)算法相比，在保證查全率和查準(zhǔn)率的前提下，大幅度的降低了運(yùn)算量，提高了運(yùn)算效率。

參考文獻(xiàn)：

[1]焦玉英 符紹宏:信息檢索[M].武漢:武漢大學(xué)出版社，2001

[2]GERARD SALTON A. WONG and C.S.YANG. A Vector space model for information Retrieval. Communications of the ACM 1975.18(11):613～620

[3]雷景生 林冬雪 符淺挽:基于改進(jìn)向量空間模型的Web信息檢索技術(shù)研究[J].計(jì)算機(jī)工程，2005，1.vol31

[4]劉志為:N層向量空間模型在web信息檢索中的應(yīng)用[J].微型機(jī)與應(yīng)用，2004年第12期

[5]史榮昌:矩陣分析[M].北京:北京理工大學(xué)出版社，1996.149～153

[6]屠伯塤:線性代數(shù):方法導(dǎo)引[M].上海:復(fù)旦大學(xué)出版社，1986.

[7]Shi RC.Matrix Analysis[M].Beijing:Beijing Institute of Technology Press， 1996.149～153(in Chinese)

[8]Han JW， Kamber M. Data Mining:Concepts and Techniques[M]. Beijing:High Education Press， 2001，38～388