摘 要： 在傳統向量空間模型的基礎上，提出一種新的信息檢索算法模型——N層向量模型。此模型應用在Web信息檢索上，能較好地適應文檔集合的動態擴充。
關鍵詞： 搜索引擎 向量空間模型 查準率 查全率
Internet使人類社會步入了以網絡為中心的信息時代。隨著Web信息爆炸性的增長，如何從大量的信息中迅速、有效、準確地提取所需信息已成為一個極富挑戰性的課題，并已成為學術界和企業界十分關注的問題。
半個多世紀以來，人們提出了許多種信息檢索的算法模型。Salton等人提出的一種向量空間模型的算法是使用TFIDF將文檔轉化為向量形式，其計算簡單并且有效，因此得到了較廣泛的應用。在經典的向量空間檢索模型的算法中，文檔和查詢都是用其所包含的特征項(通常認為以詞為特征項比較合理）組成的向量來表示的，并且用文檔與查詢的向量之間夾角的余弦作為相似性的度量，夾角越小，相似度越大。針對特定的查詢向量，比較它與所有文檔向量的相似度，并依相似度將文檔降序排序，提交檢索結果。這種方法具有簡單直觀、處理速度快等優點。但是文檔集合中特征項的數量遠遠大于每一篇文檔或查詢中特征項的個數，因此文檔和查詢的向量表示形式中的大部分項都為零。這些零項將會在計算特征項的權重和相似度時帶來很大的時間和空間復雜度，導致數據稀疏現象。另外在特征項抽取以及查詢匹配過程中，同一個特征項出現在文檔的不同區域時，它所表達文檔內容的能力是不同的。而且在文檔同一區域，不同的特征項所表達文檔內容的能力也是有差別的。使用傳統的向量空間模型則會認為這些特征項所表達文檔的能力完全相同，不能加以區分。
本文在傳統向量空間模型的基礎上提出一種新的檢索方法，將N層向量空間模型應用在Web信息檢索上，使之能較好地適應文檔集合的動態擴充。理論分析和實驗結果表明，此方法能夠進一步提高向量空間模型的性能，節省存儲空間，加快檢索速度，具有較高的精度和召回率。
1 向量空間模型
1.1 傳統向量空間模型
向量空間模型的出發點是：每篇文檔和查詢都包含一些用概念詞表達的、揭示其內容的獨立屬性，而每個屬性都可以看成是概念空間的一個維數。因此，文檔和查詢就可以表示為這些屬性的集合，從而忽略了文本結構中段落、句子及詞語之間的復雜關系。這樣，文檔和查詢可以分別用空間的一個點表示，并且文檔矢量與查詢矢量之間就存在空間上的不同距離，而這種距離關系在信息檢索中的意義就是文檔與查詢之間的相似度。所以，文檔與查詢之間的相似度可以用矢量間的距離來衡量。相似度的計算方法有很多種，本文采用余弦系數法，即用二個矢量之間的夾角的余弦來表示文檔與查詢間的相關度。夾角越大，距離越遠，余弦越小，相關度越小，反之相關度越大。下面介紹向量空間模型的量化方法。
tfij為特征項tj在文檔di中出現的頻率；dfj為在整個文檔集中，包含特征項tj的文檔數；idfj為反轉文檔頻數，其值為：
可見，傳統的向量空間模型是以文本特征項的頻率tf和反轉文檔頻率idf作為其量化基礎的。其乘積作為特征項的權重，再通過計算文檔與查詢之間的相似度即可判斷文檔與查詢是否相關。權重值大的特征項是那些在文檔中出現頻率足夠高，但在整個文檔集的其他文檔中出現頻率足夠少的詞語，也是對區別文檔最有意義的詞語。
1.2 N層向量空間模型
將一篇文檔從組織結構上劃分為N層，基于每層的文本內容建立相應的特征項向量和權值。其中特征項抽取和權重計算等同傳統向量空間模型相同。這樣，對于文檔進行N層劃分得到的向量空間模型就成為N層向量空間模型。
本文針對Web信息檢索進行考慮，由于Web頁面的特殊格式，要求一篇文檔最少是由指向該文檔的鏈接、文檔標題和文檔正文三部分組成。而這三部分的內容對于這篇文檔的表達能力是不同的。鏈接的文字是吸引別人點擊文檔進行閱讀的通道，所以鏈接的內容表達文檔的能力最強，其次是標題，正文的內容表達文檔的能力最弱。
因此，將N層向量空間模型應用在Web信息檢索時，可將一篇Web文檔按照指向文檔的鏈接、標題和正文劃分成3層（若Web頁面中有<meta keyword>等標記的關鍵字部分，則可劃分為4層向量空間模型。）。
2 應用N層向量空間模型進行Web信息檢索
2.1 文本向量表示形式的改進
向量空間模型在建完索引以后，要根據每一個特征項求其對于每一篇文檔和查詢的權重值。其計算量非常大，并且每一篇文檔和查詢的向量表示式為
，其中大多數項都為零，所以導致了數據稀疏現象。另外由于Web頁面的超鏈性（hyperlink），頁面上顯示的信息有很多是和本頁內容無關的，例如別的頁面的鏈接、版權信息、欄目導航等，在每個頁面上都有重復出現，這干擾了相似度計算。為解決這些問題，首先引入停用詞表，例如文檔中很多不能說明文檔內容的語法詞，還有虛詞、感嘆詞、連詞等或各個文檔共有的詞，所有這些詞作為描述文檔的向量效率是非常低的。因此可以考慮降維處理，把它們作為停用詞，不計算其權重；其次，采用壓縮矩陣的辦法來解決數據稀疏問題，定義文檔和查詢的向量表示形式為：<……，(ti，ωdi)，……>，其中ti為第i個特征項，ωdi為其對應的權重值且ωdi≠0。這樣既減少了計算量，又加快了計算速度，同時節省了存儲空間。
2.2 特征項頻率統計的改進
在統計每個區域的特征項頻率得到tfij后，要乘以一個反映其重要程度的比例系數來加以修正和調整，則特征項tj在文檔di中出現的頻率為：
其中：tfiji為第i個區域的頻率（i為1、2、3時分別對應鏈接區域、標題區域、正文區域），α＞β＞γ≥1為比例系數。
同樣，在文檔同一區域中，不同的特征項所表達文檔內容的能力也是有差別的。例如同在正文區域的不同的特征項所代表文檔的內容就有可能不同。在計算特征項頻率tfij時再乘以一個比例因子log2(M/mi)，其中M為該特征項在本文檔中共出現的次數，mi為該特征項在文檔第i次出現的次數。這樣，特征項tj在文檔di中出現的頻率調整為：
2.3 傳統向量空間模型與N層向量空間模型的算法復雜度比較
表1為傳統向量空間模型與N層向量空間模型的算法復雜度比較結果。
3 實驗設置
(1)信息檢索實驗系統。信息檢索實驗系統選用了Smart系統。Smart系統是基于向量空間檢索模型實現的信息檢索系統。在本實驗中，為便于實現對向量空間模型算法的修改，使用的是經過修改的Smart信息檢索系統。
(2)測試集。測試集分為文檔和查詢（query）二部分：文檔部分采用新浪網站（www.sina.com.cn）的新聞部分Web版（32，145篇）。查詢部分使用新浪網站的新聞討論標題，共50個。
(3)評價方法。本系統使用精度和召回率來評價。精度是檢索出來的相關文檔數和檢索出來的總文檔數的比值；召回率是檢索出來的相關文檔數和總的相關文檔數的比值。通常，召回率越高，精度越低；反之精度越高，召回率越低。所以最有說服力的是11個點的平均精度。世界上最權威的文本檢索評測會議TREC（Text Retrieval Conference）的評測依據就是這個值。本系統將只提供這個值。
4 實驗結果
這里對傳統的向量空間模型算法和改進后的向量空間算法進行了比較，并統計了對應于每一條查詢的11個點處的平均精度值。其結果如表2所示。
因為平均精度值僅僅是11個點處的精度值的平均值，為了進一步說明問題，圖1給出了這幾次檢索的精度-召回率曲線。
從圖1中可以看出，改進向量空間模型在索引時間和精度上都要優于傳統向量空間，性能有了很大的提高。
本文提出了一種應用N層向量空間模型算法用于Web信息檢索的辦法。理論分析和實驗結果表明，改進后的方法大大提高了Web信息檢索的性能，節省了存儲空間，加快了計算速度，具有較高的精度和召回率。
參考文獻
1 Salton G.The SMART retrieval system-experiments in automatic document processing.USA：Prentice Hall，1971
2 陶躍華.基于向量的相似度計算方案.云南師范大學學報，2001；21（10）
3 陸玉昌，魯明羽.向量空間法中單詞權重函數的分析和構造.計算機研究與發展，2002；39（10）
4 劉芳，盧正鼎.有效地檢索HTMl文檔.小型微型計算機系統，2000；21（9）