我們今天談?wù)勅绾未_定一個(gè)網(wǎng)頁(yè)和某個(gè)查詢(xún)的相關(guān)性。了解了這四個(gè)方面，一個(gè)有一定編程基礎的讀者應該可以寫(xiě)一個(gè)簡(jiǎn)單的搜索引擎了，比如為您所在的學(xué)?；蛟合到⒁粋€(gè)小的搜索引擎。]
我們還是看上回的例子，查找關(guān)于“原子能的應用”的網(wǎng)頁(yè)。我們第一步是在索引中找到包含這三個(gè)詞的網(wǎng)頁(yè)(詳見(jiàn)關(guān)于布爾運算的系列)?，F在任何一個(gè)搜索引擎都包含幾十萬(wàn)甚至是上百萬(wàn)個(gè)多少有點(diǎn)關(guān)系的網(wǎng)頁(yè)。那么哪個(gè)應該排在前面呢?顯然我們應該根據網(wǎng)頁(yè)和查詢(xún)“原子能的應用”的相關(guān)性對這些網(wǎng)頁(yè)進(jìn)行排序。因此，這里的關(guān)鍵問(wèn)題是如何度量網(wǎng)頁(yè)和查詢(xún)的相關(guān)性。
我們知道，短語(yǔ)“原子能的應用”可以分成三個(gè)關(guān)鍵詞:原子能、的、應用。根據我們的直覺(jué)，我們知道，包含這三個(gè)詞多的網(wǎng)頁(yè)應該比包含它們少的網(wǎng)頁(yè)相關(guān)。當然，這個(gè)辦法有一個(gè)明顯的漏洞，就是長(cháng)的網(wǎng)頁(yè)比短的網(wǎng)頁(yè)占便宜，因為長(cháng)的網(wǎng)頁(yè)總的來(lái)講包含的關(guān)鍵詞要多些。因此我們需要根據網(wǎng)頁(yè)的長(cháng)度，對關(guān)鍵詞的次數進(jìn)行歸一化，也就是用關(guān)鍵詞的次數除以網(wǎng)頁(yè)的總字數。我們把這個(gè)商稱(chēng)為“關(guān)鍵詞的頻率”，或者“單文本詞匯頻率”(Term Frequency)，比如，在某個(gè)一共有一千詞的網(wǎng)頁(yè)中“原子能”、“的”和“應用”分別出現了 2 次、35 次 和 5 次，那么它們的詞頻就分別是 0.002、0.035 和 0.005。 我們將這三個(gè)數相加，其和 0.042 就是相應網(wǎng)頁(yè)和查詢(xún)“原子能的應用”
相關(guān)性的一個(gè)簡(jiǎn)單的度量。概括地講，如果一個(gè)查詢(xún)包含關(guān)鍵詞 w1,w2,...,wN, 它們在一篇特定網(wǎng)頁(yè)中的詞頻分別是: TF1, TF2, ..., TFN。 (TF: term frequency)。 那么，這個(gè)查詢(xún)和該網(wǎng)頁(yè)的相關(guān)性就是:
TF1 + TF2 + ... + TFN。
讀者可能已經(jīng)發(fā)現了又一個(gè)漏洞。在上面的例子中，詞“的”站了總詞頻的 80% 以上，而它對確定網(wǎng)頁(yè)的主題幾乎沒(méi)有用。我們稱(chēng)這種詞叫“應刪除詞”(Stopwords)，也就是說(shuō)在度量相關(guān)性是不應考慮它們的頻率。在漢語(yǔ)中，應刪除詞還有“是”、“和”、“中”、“地”、“得”等等幾十個(gè)。忽略這些應刪除詞后，上述網(wǎng)頁(yè)的相似度就變成了0.007，其中“原子能”貢獻了0.002，“應用”貢獻了 0.005。
細心的讀者可能還會(huì )發(fā)現另一個(gè)小的漏洞。在漢語(yǔ)中，“應用”是個(gè)很通用的詞，而“原子能”是個(gè)很專(zhuān)業(yè)的詞，后者在相關(guān)性排名中比前者重要。因此我們需要給漢語(yǔ)中的每一個(gè)詞給一個(gè)權重，這個(gè)權重的設定必須滿(mǎn)足下面兩個(gè)條件:
1. 一個(gè)詞預測主題能力越強，權重就越大，反之，權重就越小。我們在網(wǎng)頁(yè)中看到“原子能”這個(gè)詞，或多或少地能了解網(wǎng)頁(yè)的主題。我們看到“應用”一次，對主題基本上還是一無(wú)所知。因此，“原子能“的權重就應該比應用大。
2. 應刪除詞的權重應該是零。
我們很容易發(fā)現，如果一個(gè)關(guān)鍵詞只在很少的網(wǎng)頁(yè)中出現，我們通過(guò)它就容易鎖定搜索目標，它的權重也就應該大。反之如果一個(gè)詞在大量網(wǎng)頁(yè)中出現，我們看到它仍然不很清楚要找什么內容，因此它應該小。概括地講，假定一個(gè)關(guān)鍵詞 w 在 Dw 個(gè)網(wǎng)頁(yè)中出現過(guò)，那么 Dw 越大，w 的權重越小，反之亦然。在信息檢索中，使用最多的權重是“逆文本頻率指數” (Inverse document frequency 縮寫(xiě)為IDF)，它的公式為log(D/Dw)其中D是全部網(wǎng)頁(yè)數。比如，我們假定中文網(wǎng)頁(yè)數是D=10億，應刪除詞“的”在所有的網(wǎng)頁(yè)中都出現，即Dw=10億，那么它的IDF=log(10億/10億)= log (1) = 0。假如專(zhuān)用詞“原子能”在兩百萬(wàn)個(gè)網(wǎng)頁(yè)中出現，即Dw=200萬(wàn)，則它的權重IDF=log(500) =6.2。又假定通用詞“應用”，出現在五億個(gè)網(wǎng)頁(yè)中，它的權重IDF = log(2)
則只有 0.7。也就只說(shuō)，在網(wǎng)頁(yè)中找到一個(gè)“原子能”的比配相當于找到九個(gè)“應用”的匹配。利用 IDF，上述相關(guān)性計算個(gè)公式就由詞頻的簡(jiǎn)單求和變成了加權求和，即 TF1*IDF1 + TF2*IDF2 +... + TFN*IDFN。在上面的例子中，該網(wǎng)頁(yè)和“原子能的應用”的相關(guān)性為 0.0161，其中“原子能”貢獻了 0.0126，而“應用”只貢獻了0.0035。這個(gè)比例和我們的直覺(jué)比較一致了。
TF/IDF(term frequency/inverse document frequency) 的概念被公認為信息檢索中最重要的發(fā)明。在搜索、文獻分類(lèi)和其他相關(guān)領(lǐng)域有廣泛的應用。講起 TF/IDF 的歷史蠻有意思。IDF 的概念最早是劍橋大學(xué)的斯巴克-瓊斯[注:她有兩個(gè)姓] (Karen Sparck Jones)提出來(lái)的。斯巴克-瓊斯 1972 年在一篇題為關(guān)鍵詞特殊性的統計解釋和她在文獻檢索中的應用的論文中提出IDF。遺憾的是，她既沒(méi)有從理論上解釋為什么權重IDF 應該是對數函數 log(D/Dw)(而不是其它的函數，比如平方根)，也沒(méi)有在這個(gè)題目上作進(jìn)一步深入研究，以至于在以后的很多文獻中人們提到 TF/IDF 時(shí)沒(méi)有引用她的論文，絕大多數人甚至不知道斯巴克-瓊斯的貢獻。同年羅賓遜寫(xiě)了個(gè)兩頁(yè)紙的解釋?zhuān)忉尩煤懿缓?。倒是后?lái)康乃爾大學(xué)的薩爾頓(Salton)多次寫(xiě)文章、寫(xiě)書(shū)討論 TF/IDF 在信息檢索中的用途，加上薩爾頓本人的大名(信息檢索的世界大獎就是以薩爾頓的名字命名的)。很多人都引用薩爾頓的書(shū)，甚至以為這個(gè)信息檢索中最重要的概念是他提出的。當然，世界并沒(méi)有忘記斯巴克-瓊斯的貢獻，2004年，在紀念文獻學(xué)學(xué)報創(chuàng )刊 60 周年之際，該學(xué)報重印了斯巴克-瓊斯的大作。羅賓遜在同期期刊上寫(xiě)了篇文章，用香農的信息論解釋 IDF，這回的解釋是對的，但文章寫(xiě)的并不好、非常冗長(cháng)(足足十八頁(yè))，把一個(gè)簡(jiǎn)單問(wèn)題搞復雜了。其實(shí)，信息論的學(xué)者們已經(jīng)發(fā)現并指出，其實(shí) IDF 的概念就是一個(gè)特定條件下、關(guān)鍵詞的概率分布的交叉熵(Kullback-Leibler Divergence)(詳見(jiàn)上一系列)。這樣，信息檢索相關(guān)性的度量，又回到了信息論。
現在的搜索引擎對 TF/IDF 進(jìn)行了不少細微的優(yōu)化，使得相關(guān)性的度量更加準確了。當然，對有興趣寫(xiě)一個(gè)搜索引擎的愛(ài)好者來(lái)講，使用 TF/IDF 就足夠了。 如果我們結合上網(wǎng)頁(yè)排名(Page Rank)，那么給定一個(gè)查詢(xún)，有關(guān)網(wǎng)頁(yè)綜合排名大致由相關(guān)性和網(wǎng)頁(yè)排名乘積決定。
本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請
點(diǎn)擊舉報。
