數學之美 系列九 -- 如何確定網頁和查詢的相關性

2006年6月27日 上午 09:53:00

發表者：吳軍，Google 研究員

[我們已經談過了如何自動下載網頁、如何建立索引、如何衡量網頁的質量(Page Rank)。我們今天談談如何確定一個網頁和某個查詢的相關性。了解了這四個方面，一個有一定編程基礎的讀者應該可以寫一個簡單的搜索引擎了，比如為您所在的學校或院系建立一個小的搜索引擎。]

我們還是看上回的例子，查找關于“原子能的應用”的網頁。我們第一步是在索引中找到包含這三個詞的網頁（詳見關于布爾運算的系列）。現在任何一個搜索引擎都包含幾十萬甚至是上百萬個多少有點關系的網頁。那么哪個應該排在前面呢？顯然我們應該根據網頁和查詢“原子能的應用”的相關性對這些網頁進行排序。因此，這里的關鍵問題是如何度量網頁和查詢的相關性。

我們知道，短語“原子能的應用”可以分成三個關鍵詞：原子能、的、應用。根據我們的直覺，我們知道，包含這三個詞多的網頁應該比包含它們少的網頁相關。當然，這個辦法有一個明顯的漏洞，就是長的網頁比短的網頁占便宜，因為長的網頁總的來講包含的關鍵詞要多些。因此我們需要根據網頁的長度，對關鍵詞的次數進行歸一化，也就是用關鍵詞的次數除以網頁的總字數。我們把這個商稱為“關鍵詞的頻率”，或者“單文本詞匯頻率”（Term Frequency)，比如，在某個一共有一千詞的網頁中“原子能”、“的”和“應用”分別出現了 2 次、35 次 和 5 次，那么它們的詞頻就分別是 0.002、0.035 和 0.005。 我們將這三個數相加，其和 0.042 就是相應網頁和查詢“原子能的應用”
相關性的一個簡單的度量。概括地講，如果一個查詢包含關鍵詞 w1,w2,...,wN, 它們在一篇特定網頁中的詞頻分別是: TF1, TF2, ..., TFN。 （TF: term frequency)。 那么，這個查詢和該網頁的相關性就是:
TF1 + TF2 + ... + TFN。

讀者可能已經發現了又一個漏洞。在上面的例子中，詞“的”站了總詞頻的 80% 以上，而它對確定網頁的主題幾乎沒有用。我們稱這種詞叫“應刪除詞”（Stopwords)，也就是說在度量相關性是不應考慮它們的頻率。在漢語中，應刪除詞還有“是”、“和”、“中”、“地”、“得”等等幾十個。忽略這些應刪除詞后，上述網頁的相似度就變成了0.007，其中“原子能”貢獻了0.002，“應用”貢獻了 0.005。

細心的讀者可能還會發現另一個小的漏洞。在漢語中，“應用”是個很通用的詞，而“原子能”是個很專業的詞，后者在相關性排名中比前者重要。因此我們需要給漢語中的每一個詞給一個權重，這個權重的設定必須滿足下面兩個條件：

1. 一個詞預測主題能力越強，權重就越大，反之，權重就越小。我們在網頁中看到“原子能”這個詞，或多或少地能了解網頁的主題。我們看到“應用”一次，對主題基本上還是一無所知。因此，“原子能“的權重就應該比應用大。

2. 應刪除詞的權重應該是零。

我們很容易發現，如果一個關鍵詞只在很少的網頁中出現，我們通過它就容易鎖定搜索目標，它的權重也就應該大。反之如果一個詞在大量網頁中出現，我們看到它仍然不很清楚要找什么內容，因此它應該小。概括地講，假定一個關鍵詞 ｗ 在 Ｄｗ 個網頁中出現過，那么 Ｄｗ 越大，ｗ 的權重越小，反之亦然。在信息檢索中，使用最多的權重是“逆文本頻率指數” （Inverse document frequency 縮寫為ＩＤＦ），它的公式為ｌｏｇ（Ｄ／Ｄｗ）其中Ｄ是全部網頁數。比如，我們假定中文網頁數是Ｄ＝１０億，應刪除詞“的”在所有的網頁中都出現，即Ｄｗ＝１０億，那么它的ＩＤＦ＝log(10億/10億）= log (1) = ０。假如專用詞“原子能”在兩百萬個網頁中出現，即Ｄｗ＝２００萬，則它的權重ＩＤＦ＝log(500) =6.2。又假定通用詞“應用”，出現在五億個網頁中，它的權重ＩＤＦ = log(2)
則只有 0.7。也就只說，在網頁中找到一個“原子能”的比配相當于找到九個“應用”的匹配。利用 IDF，上述相關性計算個公式就由詞頻的簡單求和變成了加權求和，即 TF1*IDF1 +　TF2*IDF2 ＋... + TFN*IDFN。在上面的例子中，該網頁和“原子能的應用”的相關性為 0.0161，其中“原子能”貢獻了 0.0126，而“應用”只貢獻了0.0035。這個比例和我們的直覺比較一致了。

ＴＦ／ＩＤＦ（term frequency/inverse document frequency) 的概念被公認為信息檢索中最重要的發明。在搜索、文獻分類和其他相關領域有廣泛的應用。講起 TF/IDF 的歷史蠻有意思。IDF 的概念最早是劍橋大學的斯巴克－瓊斯[注：她有兩個姓］ (Karen Sparck Jones)提出來的。斯巴克－瓊斯 １９７２ 年在一篇題為關鍵詞特殊性的統計解釋和她在文獻檢索中的應用的論文中提出ＩＤＦ。遺憾的是，她既沒有從理論上解釋為什么權重ＩＤＦ 應該是對數函數 ｌｏｇ（Ｄ／Ｄｗ）（而不是其它的函數，比如平方根），也沒有在這個題目上作進一步深入研究，以至于在以后的很多文獻中人們提到 ＴＦ／ＩＤＦ 時沒有引用她的論文，絕大多數人甚至不知道斯巴克－瓊斯的貢獻。同年羅賓遜寫了個兩頁紙的解釋，解釋得很不好。倒是后來康乃爾大學的薩爾頓（Salton)多次寫文章、寫書討論 TF/IDF 在信息檢索中的用途，加上薩爾頓本人的大名（信息檢索的世界大獎就是以薩爾頓的名字命名的）。很多人都引用薩爾頓的書，甚至以為這個信息檢索中最重要的概念是他提出的。當然，世界并沒有忘記斯巴克－瓊斯的貢獻，2004年，在紀念文獻學學報創刊 60 周年之際，該學報重印了斯巴克-瓊斯的大作。羅賓遜在同期期刊上寫了篇文章，用香農的信息論解釋 IDF，這回的解釋是對的，但文章寫的并不好、非常冗長（足足十八頁），把一個簡單問題搞復雜了。其實，信息論的學者們已經發現并指出，其實 IDF 的概念就是一個特定條件下、關鍵詞的概率分布的交叉熵（Kullback-Leibler Divergence)（詳見上一系列）。這樣，信息檢索相關性的度量，又回到了信息論。

現在的搜索引擎對 TF/IDF 進行了不少細微的優化，使得相關性的度量更加準確了。當然，對有興趣寫一個搜索引擎的愛好者來講，使用 TF/IDF 就足夠了。 如果我們結合上網頁排名(Page Rank)，那么給定一個查詢，有關網頁綜合排名大致由相關性和網頁排名乘積決定。