[摘 要] 針對(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) 公式(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