文本信息检索基本知识【转】
文本信息檢索是針對文本的信息檢索技術。在技術社區中，文本信息檢索常常被等同于信息檢索技術本身。
相對視頻、音頻檢索而言，文本信息檢索是發展較快也較成熟的，其他模態的信息檢索技術，往往也要仰賴文本信息檢索的支持。
雖然網絡搜索引擎目前已不僅僅局限于對文本進行檢索，文本信息檢索仍然是大部分網絡搜索引擎的基礎。
目錄
|
歷史介紹
自人類的文字產生起，如何快速地從大量的，記錄在各種各樣的存儲媒體中查找或獲取信息就成為一個引人注目的問題。這個問題關系到人類如何能夠主動地獲取自己需要的知識。因此，文本信息檢索技術甚至可以追述到古代的書籍編目。但是直到近一個世紀，隨著人類的知識以前所未有的速度急劇膨脹，信息存儲方式越來越豐富，使得在海量的，多模態的信息庫中進行快速、準確的檢索成為急迫的需求。1945年，Vannevar Bush的論文《就像我們可能會想的……》[1]第一次提出了設計自動的，在大規模的存儲數據中進行查找的機器的構想。這被認為是現在信息檢索技術的開山之作。進入50年代后，研究者們開始為逐步的實現這些設想而努力。在50年代中期，在利用電腦對文本數據進行檢索的研究上，研究者取得了一些成果。其中最有代表性的是Luhn在IBM公司的工作[2]，他提出了利用詞對文檔構建索引并利用檢索與文檔中詞的匹配程度進行檢索 的方法，這種方法就是目前常用的倒排文檔技術的雛形。
在60年代，信息檢索技術的一些關鍵技術取得了突破。其間出現了一些優秀的系統以及評價指標。在評價指標方面，由Cranfield的研究組組織的Cranfield評測[3]提出了許多目前仍然被廣泛采用的評價指標，而在系統方面，Gernard Salton開發的SMART系統[4]構建了一個很好的研究平臺，在此平臺上，研究者可以定義自己的文檔相關性測度，以改進檢索性能。這樣，作為一個研究課題，信息檢索技術擁有了較為完善實驗平臺與評價指標，其研究理所當然地步入了快車道。也正因為如此，在70年代到80年代，許多信息檢索的理論與模型被提出，并且被證明對當時所能獲得的數據集是有效的。其中最為著名的是Gerard Salton提出的矢量空間模型[5][6][7]。至今該模型還是信息檢索領域最為常用的模型之一。但是，檢索的對象——文本集合的缺乏使得這些技術在海量文本上的可靠性無法得到驗證。當時的研究大多針對數千篇的文檔組成的集合。這時，美國國家標準技術研究所(NIST)組織的文本檢索會議(Text Retrieval Conference, TREC)的召開改變了這一情況。TREC是一個評測性質的會議，為參評者提供了大規模的文本語料，從而大大推動了信息檢索技術的快速發展。會議的第一次召開是1992年，不久后，互聯網興起為信息檢索技術提供了一個巨大的實驗場。從Yahoo到Google，大量實用的文本信息檢索系統開始出現并得到廣泛應用。這些系統從事實上改變了人類獲取信息與知識的方式。
目前，在文本檢索領域，簡單的信息檢索已經開始向更加復雜且人性化的垂直搜索演化，引入了信息抽取技術以提取文檔中的結構化信息。
模型
早期的信息檢索系統采用“布爾查詢”的方法來進行全文檢索。這種方法無疑將構造一個合適的查詢的責任推到用戶身上。用戶必須詳細的規劃自己的查詢，其復雜程度不亞于編程語言。這種檢索方式并不提供任何的文檔相關性測度，對于文檔與查詢的評價就只有“匹配”，“不匹配”兩種而已。這兩點問題決定了布爾查詢不能被廣泛應用。但是，由于布爾檢索能夠給用戶提供更多的可控制性，今天我們仍然可以在搜索引擎的“高級搜索”中找到布爾查詢的身影。
對于大規模的語料庫，任何檢索都可能返回數量眾多的結果，因此對檢索結果進行排序是必須的。因此，一個好的信息檢索模型必須提供文檔相關性測度。一個好的測度應該使與用戶查詢需求最相關的那些結果，排在最前面，同時允許盡可能多的，與用戶查詢有一定關系的結果被包括進來。目前，最為常用的信息檢索模型有三種：
- 矢量空間模型 (Vector Space Model, VSM)
- 概率模型 (Probabilistic Model)
- 推理網絡模型 (Inference Network Model)
?矢量空間模型
矢量空間模型最早由Gerard提出[5]。在此模型中，一個文檔(Document)被描述成由一系列關鍵詞(Term)組成的矢量。模型并沒有規定關鍵詞如何定義，但是一般來說，關鍵詞可以是字，詞或者短語。在語音文檔檢索中，還可以是混淆類、音子、音子串等等單元。假設我們用“詞”作為Term，那么在詞典中的每一個詞，都定義矢量空間中的一維。如果一篇文檔包含這個詞，那么表示這個文檔的矢量在這個詞所定義的維度上應該擁有一個非0值（對絕大多數系統來說，是正值）。
當一個查詢被提交時，由于這個查詢也是由文本構成，所以也可以被矢量空間所表示。模型將對查詢與文檔，計算一個相似度需要注意的是，模型也沒有對相似度給出確切的定義。它可以使歐氏距離，也可以是兩個矢量的夾角的余弦。
假設表示文檔矢量，而表示查詢矢量，文檔與查詢的相關性可以用余弦距離表示如下：
如果我們用和表示和中的第i維的值，并且對每個文檔矢量進行歸一化，即令，那么上式有可以表示為
在此，究竟如何取值是一個重要的問題，其取值一般被稱為關鍵詞i在文檔D中的權重。關鍵詞權重問題將在隨后進行專門的討論。
傳統矢量空間模型的一個問題是各個維度間缺乏相關性，因而無法對文檔中各個詞的相關性提供信息。從宏觀上看，仍然沒有擺脫“關鍵詞匹配”的窠臼。一個自然的想法就是對文檔特征——文檔矢量進行降維，將維數巨大的文檔矢量投影到某個較小維度的空間中，使得關鍵詞之間即使不完全匹配，也能夠根據語義發生關系。這就誕生了潛語義索引(Latent Semantic Indexing)[8]，它通過對矢量空間進行奇異值分解，將高維文檔矢量投射到低維潛語義空間中。潛語義索引隨后被融入概率模型框架中，形成了基于概率模型的PLSI(Probabilistic Latent Semantic Indexing)[9]， 和LDA(Latent Dirichlet Allocation)[10]。
?概率模型
概率模型的基本思想是估計文檔與查詢相關聯概率，并對所有文檔根據關聯概率進行排序。這一模型最早由Maron和Kuhn在1960年提出。[11]在給定查詢Q的情況下，用P(R | D)表示文檔與查詢相關的概率，而用表示文檔與查詢不相關的概率。 那么，就可以用
對文檔進行排序。利用貝葉斯公式，可以很容易的將上面的公式變為產生式的形式：
由于P(R)和同文檔無關，上面的公式可以最終表示為：
概率模型的主要任務就集中在估計P(D | R)和上。
?推理網絡模型
推理網絡模型是一種較上述兩中模型更為一般化的模型，上述模型都可以歸結為推理網絡模型的一種實現。在此模型下，僅僅規定文檔以某種 “力度”產生某個來自查詢的關鍵詞，至于力度如何定義，則完全沒有規定，即可以是概率，也可以是關鍵詞權重。
倒排文檔索引技術
在信息檢索系統的具體實現中，需要快速地找到文檔中所包含的關鍵詞。相比文檔來說，關鍵詞的個數是較少的，因此，以關鍵詞為核心對文檔進行索引是更加可行的方法。這就是信息檢索領域常用的常用的“倒排文檔索引”技術。倒排文檔索引可以被看成一個鏈表數組，每個鏈表的表頭包含關鍵詞，其后續單元則包括所有包括這個關鍵詞的文檔標號，以及一些其他信息。這些信息可以是文檔中該詞的頻率，也可以是文檔中該詞的位置等信息。
倒排文檔示例倒排文檔索引的優勢不僅在于關鍵詞個數少帶來的檢索效率提高，還在于其特別易于同信息檢索技術結合。在實際應用中，查詢中所包含的關鍵詞往往是很少的，完全不包含查詢中的所有關鍵詞的文檔，一般來說是不會被列入結果集的。因此，以關鍵詞為主鍵進行索引，只需要用查詢中包括的關鍵詞，進行幾次簡單的查詢就能夠找出所有可能的文檔。
倒排文檔索引的具體數據結構可以進行進一步的優化。在關鍵詞查詢上，往往采用B-Tree或哈希表進行快速查詢。而文檔列表的數據結構則可以采用簡單的無串行表進行存儲，但是此種無串行表存在一個問題，就是當多個關鍵詞對應的文檔集需要進行比較的時候，比較效率將比較低。因此，在實際應用中往往采用二叉搜索樹組織文檔列表。
關鍵詞權重
關鍵詞對于區分文檔的作用是不同的。例如一些虛詞對于區分文檔的內容與查詢是否相關并沒有多大的意義。
對于概率模型而言，可以有完備的理論來估計每篇文檔生成某個詞的概率，因而其主要工作集中于如何確定較好的概率估計方法。而對于矢量 空間模型來說，確定關鍵詞權重在很大程度上依賴于研究者的經驗及對文檔特性的分析。
目前，對關鍵詞權重的確定方法一般都需要獲取一些關于關鍵詞的統計量，而后根據這些統計量，應用某種認為規定的計算公式來得到權重。 最常用的統計量包括：
- tf，Term Frequency的縮寫，表示某個關鍵詞在某個文檔中出現的頻率。
- qtf，Query Term Frequency的縮寫。表示查詢中某關鍵詞的出現頻率。
- N，集合中的文檔總數
- df，Document Frequency的縮寫，表示文檔集合中，出現某個關鍵詞的文檔個數。
- idf，Inversed Document Frequency的縮寫。
- dl，文檔長度
- adl，平均文檔長度
在矢量空間模型下，構造關鍵詞權重計算公式有三個基本原則：
早期的權重往往直接采用tf，但是顯然這種權重并沒有考慮上述第二條原則，因此在大規模系統中是不適用的。目前，常用的關鍵詞權重計算公式大多基于tf和df進行構建，同時，一些較為復雜的計算公式也考慮了文檔長度。現簡要列舉如下：
TF-IDF得分。嚴格地說，TF/IDF得分并不特指某個計算公式，而是一個計算公式集合。其中TF與IDF都可以進行各種變換，究竟何種變換較能符合實際需求，需要由實驗和應用來驗證。常見的變換方法有：
其中，最后一個公式，即:被大量系統證明是最有效的。
此外，較為常用的關鍵詞權重算法還包括Okapi權重[12]和Pivoted Normalization 權重(PNW)[13]。這些公式綜合考慮了查詢和文檔中的詞頻，以及文檔的長度。Okapi權重需要預設三個參數：
- k1，在1.0-2.0之間
- b,通常為0.75
- k3,在0-1000之間
而PNW則需要預設一個參數s，大部分情況下取0.20。
評價指標
任何研究都需要有一個客觀的評價體系，信息檢索系統也不例外。但是對于一項需要在實際生產生活中應用的系統，其評價導向又必須包含一定的主觀性。信息檢索系統性能的兩個基本客觀指標是召回率(Recall Rate)和準確率(Precision Rate)，這與絕大多數的模式識別技術相同。用表示檢索系統所針對的檢索集合，Q表示一個查詢，而表示查詢所返回的相關文檔集， 表示文檔集中與查詢相關的所有文檔。并定義算符為集合中元素的個數，有召回率、準確率的定義如下：
由于信息檢索系統返回的是一個排序的文檔集合，因此召回率與準確率是互補的。設定不同的相關性得分門限就能夠得到相應的準確率與 召回率。如果我們在以準確率為Y軸，召回率為X軸的圖上畫出不同門限下的準確率與召回率，一般它會程下面的形狀：
那么，對于系統的評價指標就存在一個問題，如果一個系統偏重與給用戶最準確的結果，那么高的準確率是必要的，反之，如果系統 希望包括盡可能多的相關結果，又會偏好召回率。系統如果簡單的用召回率或準確率對系統性能作評價，無法評估系統的理想性能的。
模式識別中常用F值作為性能的評價指標，其定義為
F值可以平衡地反映召回率與準確率，但是在信息檢索中仍然不是非常實用，因為它仍然是一個單點的指標，沒有反映全局特性。為了得到 一個能夠反映全局性能的指標，可以看考察下圖，其中兩條曲線分布對應了兩個檢索系統的準確率-召回率曲線。
可以看出，雖然兩個系統的性能曲線有所交疊但是以圓點標示的系統的性能在絕大多數情況下要遠好于用方塊標示的系統。從中我們可以 發現一點，如果一個系統的性能較好，其曲線應當盡可能的向上突出。更加具體的，曲線與坐標軸之間的面積應當越大。最理想的系統， 其包含的面積應當是1，而所有系統的包含的面積都應當大于0。這就是用以評價信息檢索系統的最常用性能指標，平均準確率(mean Average Precision, mAP)。其規范的定義是，設P(R)為系統在召回率為R時的準確率，
當然，一般在做評價時取得的準確率與召回率都是離散值，因此一般在計算時都采用求和而非積分。
mAP是一個較好的客觀評價指標，但是它也有一個缺陷，那就是缺乏直觀性。因此在系統評測時常常還是要附帶上準確率-召回率曲線。在實際 應用中，還有一些單值評價指標，能夠反映系統的主觀性能。其中最常用的是N-Best準確率。一般系統的返回結果都采用分頁顯示，用戶一般 不會翻看太多頁，因此前幾個結果在檢索中是最為重要的。N-Best準確率可以很好的反映這個性能。[14]
參閱
倒排索引
參考文獻
外部鏈接
- Google 檢索系統
- Lucene，Apache 基金會的開源文本信息檢索系統
- ACM信息檢索興趣小組
- 信息檢索評測 TREC
- 中文信息檢索論壇
轉載于:https://www.cnblogs.com/wintergrass/archive/2011/10/24/2222528.html
總結
以上是生活随笔為你收集整理的文本信息检索基本知识【转】的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： PHP文件包含漏洞原理分析和利用方法
- 下一篇： [转载] 后台进程符的使用 [文摘]