基于奇異值分解的信息檢索

《基于奇異值分解的信息檢索》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、http://www.paper.edu.cn基于奇異值分解的信息檢索1，211仲兆滿，高維春，李元金(1天津工業(yè)大學計算機學院，天津300160；2連云港師范高等?？茖W校計算機系，江蘇222003）摘要：針對web信息檢索的特點，提出了一種基于奇異值分解和歐氏距離算法的信息檢索算法。該算法能解決傳統(tǒng)信息檢索搜索時間慢、空間占用量大的問題。實驗證明了該算法的有效性。關(guān)鍵字：信息檢索；奇異值分解；歐氏距離；Salton向量空間模型1引言隨著www在全球范圍內(nèi)的不斷普及和應用，www上的信息資源種類及其數(shù)量不斷擴大，因此，研究高效的信息搜索方法成了一個非常重要的課題。信息檢索是從任何信息集合中

2、識別和獲取所需信息的過程及其所采取的一系列方法和策略。從原理上看，它包括存儲和檢索兩個方面。信息的存儲主要是指對在一定范圍內(nèi)的信息選擇基礎(chǔ)上進行信息特征描述、加工并使其有序化，即建立數(shù)據(jù)庫;檢索是借助一定的設(shè)[1]備與工具，采用一系列方法與策略從數(shù)據(jù)庫中查找出所需信息。目前信息檢索主要有兩種方式：基于目錄結(jié)構(gòu)的檢索和基于關(guān)鍵字的文檔檢索?；谀夸浗Y(jié)構(gòu)的檢索是一種被動的處理方式，用戶只能通過系統(tǒng)所提供的分類情況進行檢索。缺少必要的用戶交互手段，并不知道用戶真正所需要的文章，因此，在許多搜索引擎的實現(xiàn)過程中，并不提供基于目錄的服務。而基于查詢串的文檔信息檢索則屬于一種主動的處理方式。它所完成的

3、任務是接收用戶從客戶端(主要是瀏覽器)所提交的信息串，經(jīng)網(wǎng)絡(luò)傳輸后提交相關(guān)的信息檢索機制，并將最終的結(jié)果按照一定的排序規(guī)則排序后傳輸給用戶。這種檢索方式具有較好的用戶交互能力。近年來，不少科研工作者致力于這方面的研究，并成功應用于各種Web的應用中。Salton[2]等人提出的向量空間模型(VectorSpaceModel,VSM)將文檔和用戶查詢式轉(zhuǎn)化為向量形式，根據(jù)向量之間的相似程度對所有返回結(jié)果進行排序，并在搜索引擎系統(tǒng)中得到了較為廣泛的應用。但是，隨著文檔集合的擴充，數(shù)據(jù)庫表的記錄的會增大，特征值也會變得很大。對應的文檔向量空間大小的維數(shù)會急劇上升，直接影響查快率。[3]雷景生等人

4、提出了一種改進的向量空間模型。該模型將一篇文檔的相關(guān)信息從邏輯上劃分為多個相對獨立的文本段，按照不同位置的文本段確定相應的索引項權(quán)重，并給出了該模型的相似度計算方法。[4]劉志為等人提出一種N層向量模型，它能較好地適應文檔集合的動態(tài)擴充。-1-http://www.paper.edu.cn本文針對傳統(tǒng)向量空間模型在Web信息檢索中存在的缺陷，采用奇異值分解和歐氏距離算法的信息檢索，能夠減少文檔的維數(shù)，提高查找的速度。2Salton向量空間模型的算法向量空間模型使用以下的一些知識：在對文本進行處理時，由于一個文本所包含的屬性非常多，因此，為了簡化文本處理的計算過程，需要對文本信息進行預處理，

5、通過特征選取的方法，盡可能降低文本處理過程中的計算量。由于所涉及到的文本向量和詞頻矩陣非常大，而且單詞與單詞的依賴性將會使得文本信息處理無法完成，因此在對文本信息進行處理的過程中，一般都基于單詞與單詞之間互相獨立的假設(shè)來降低文本信息處理的復雜度。同時考慮到文本向量空間過大的問題，需要對文本信息進行預處理，過濾到一些無關(guān)的屬性，以降低文本向量空間的維數(shù)并減少無關(guān)信息對文本信息處理過程的干擾，使文本信息處理的精度得到提高。常用的預處理方法是特征選取方法。定義1特征項t：也稱為索引項，是指出現(xiàn)在文檔d中且能夠代表該文檔性質(zhì)的基本語言單位。定義2特征項權(quán)值Wik：是指特征項tk代表文檔di的能力大

6、小。Wik的計算采用特征項頻率tfik和反比頻率idfk計算：wik=tfik+idfk=tfik*(log2(N/nk)+1)（１）其中，tfik表示特征項tk在文檔di中出現(xiàn)的頻率，N代表文檔集合中的文檔數(shù)量，nk代表在文檔集合中出現(xiàn)特征項tk的文檔數(shù)目。從公式(1)可知，tfik越大，wik值越大；同樣nk越小，wik值也越大，說明該特征項tk更能夠代表文檔d的內(nèi)容。定義3文檔向量：設(shè)文檔集合中共有m個不同的特征項t1，t2，……tm，分別計算文檔di(i=1，……，N)的特征項t1，t2，……，tm的特征項權(quán)值，由這些特征項權(quán)值所構(gòu)成的向量(wi1，Wi2，……，wim,.)成為文

7、檔d,的向量。由于特征項t1，t2，……tm互不相同，我們可以將文檔向量看作是m維歐氏空間的向量。這樣，文檔之間的相似程度通過向量的形式轉(zhuǎn)化為向量之間的數(shù)學計算模式，使得在進行文檔歸類以及查詢匹配過程中的計算過程比較簡單、快速。定義4相似度：兩文檔向量之間相似的距離程度記為相似度。文檔di、dj相似度定義為di、dj所對應的文本向量之間的夾角余弦：-2-http://www.paper.edu.cnm∑wik*wjkk=