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

[摘 要] 針對傳統信息檢索搜索時間慢、空間占用量大的問題，提出了一種基于奇異值分解和歐氏距離算法的信息檢索算法。該算法降低了信息檢索時間復雜度和空間復雜度，實驗證明了該算法的有效性。

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

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

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

一、利用Salton向量空間模型實現信息檢索的算法

第一，構造特征項庫。輸入文檔集合中的特征項，并建立特征項庫；

第二，建立文檔信息。將文檔內容輸入數據庫，建立文檔信息庫；

第三，構造文檔向量信息庫。對每個文檔信息依據公式(1)，計算每一個特征項的權值，并構建相應的文檔向量；

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

第五，排序輸出結果。按照第四步所計算出來的相似度大小排序輸出查詢結果。

定義1 特征項t:是指出現在文檔d中且能夠代表該文檔性質的基本語言單位。

定義2 特征項權值Wik:是指特征項tk代表文檔di的能力大小。Wik的計算采用特征項頻率tfik和反比頻率idfk計算。

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

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

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

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

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

公式(2）

在進行查詢匹配時，查詢條件QS的向量化過程可采用布爾模型進行：

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

二、問題提出

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

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

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

引理1 奇異值分解:對于任一實矩陣Am×n，秩(A)=r，則存在兩個標準正交矩陣Um×m和Vn×n以及對角陣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對應于非零特征值λi的特征向量。

在Salton向量空間模型實現信息檢索算法的第三步構造文檔向量信息庫之后，對每個文檔特征向量進行奇異值分解，然后在文檔查詢時，對查詢條件的文檔向量也要進行奇異值分解，然后利用歐氏距離計算奇異值分解后的文檔特征向量與查詢條件的文檔向量的相似度，最后排序輸出結果。

四、實驗與結果分析

從萬方數字化期刊中隨機抽取期刊論文20篇，得到文檔集合的關鍵字特征項共50個。

由Salton向量空間模型算法得到文檔向量。因為對文本信息處理過程中，一般基于單詞與單詞之間互相獨立的假設來降低文本信息處理的復雜度，所以把文檔向量轉換成m×n的矩陣。結果如下圖所示：

文檔矩陣經過奇異值分解后，得到對應的奇異值向量如下：

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

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

在查詢條件中先后輸入文檔1、文檔2、文檔4、文檔5，進行實驗，得到歐式距離結果如下：

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

五、結論

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

參考文獻：

[1]焦玉英 符紹宏:信息檢索[M].武漢:武漢大學出版社，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]雷景生 林冬雪 符淺挽:基于改進向量空間模型的Web信息檢索技術研究[J].計算機工程，2005，1.vol31

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

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

[6]屠伯塤:線性代數:方法導引[M].上海:復旦大學出版社，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