出自：Google黑板報

　　我們今天談?wù)勅绾未_定一個網(wǎng)頁和某個查詢的相關(guān)性。了解了這四個方面，一個有一定編程基礎(chǔ)的讀者應(yīng)該可以寫一個簡單的搜索引擎了，比如為您所在的學(xué)?；蛟合到⒁粋€小的搜索引擎。]

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

　　我們知道，短語“原子能的應(yīng)用”可以分成三個關(guān)鍵詞:原子能、的、應(yīng)用。根據(jù)我們的直覺，我們知道，包含這三個詞多的網(wǎng)頁應(yīng)該比包含它們少的網(wǎng)頁相關(guān)。當(dāng)然，這個辦法有一個明顯的漏洞，就是長的網(wǎng)頁比短的網(wǎng)頁占便宜，因為長的網(wǎng)頁總的來講包含的關(guān)鍵詞要多些。因此我們需要根據(jù)網(wǎng)頁的長度，對關(guān)鍵詞的次數(shù)進(jìn)行歸一化，也就是用關(guān)鍵詞的次數(shù)除以網(wǎng)頁的總字?jǐn)?shù)。我們把這個商稱為“關(guān)鍵詞的頻率”，或者“單文本詞匯頻率”(Term Frequency)，比如，在某個一共有一千詞的網(wǎng)頁中“原子能”、“的”和“應(yīng)用”分別出現(xiàn)了 2 次、35 次 和 5 次，那么它們的詞頻就分別是 0.002、0.035 和 0.005。 我們將這三個數(shù)相加，其和 0.042 就是相應(yīng)網(wǎng)頁和查詢“原子能的應(yīng)用”

　　相關(guān)性的一個簡單的度量。概括地講，如果一個查詢包含關(guān)鍵詞 w1,w2,...,wN, 它們在一篇特定網(wǎng)頁中的詞頻分別是: TF1, TF2, ..., TFN。 (TF: term frequency)。 那么，這個查詢和該網(wǎng)頁的相關(guān)性就是:

　　TF1 + TF2 + ... + TFN。

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

　　細(xì)心的讀者可能還會發(fā)現(xiàn)另一個小的漏洞。在漢語中，“應(yīng)用”是個很通用的詞，而“原子能”是個很專業(yè)的詞，后者在相關(guān)性排名中比前者重要。因此我們需要給漢語中的每一個詞給一個權(quán)重，這個權(quán)重的設(shè)定必須滿足下面兩個條件:

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

　　2. 應(yīng)刪除詞的權(quán)重應(yīng)該是零。

　　我們很容易發(fā)現(xiàn)，如果一個關(guān)鍵詞只在很少的網(wǎng)頁中出現(xiàn)，我們通過它就容易鎖定搜索目標(biāo)，它的權(quán)重也就應(yīng)該大。反之如果一個詞在大量網(wǎng)頁中出現(xiàn)，我們看到它仍然不很清楚要找什么內(nèi)容，因此它應(yīng)該小。概括地講，假定一個關(guān)鍵詞 w 在 Dw 個網(wǎng)頁中出現(xiàn)過，那么 Dw 越大，w 的權(quán)重越小，反之亦然。在信息檢索中，使用最多的權(quán)重是“逆文本頻率指數(shù)” (Inverse document frequency 縮寫為IDF)，它的公式為log(D/Dw)其中D是全部網(wǎng)頁數(shù)。比如，我們假定中文網(wǎng)頁數(shù)是D=10億，應(yīng)刪除詞“的”在所有的網(wǎng)頁中都出現(xiàn)，即Dw=10億，那么它的IDF=log(10億/10億)= log (1) = 0。假如專用詞“原子能”在兩百萬個網(wǎng)頁中出現(xiàn)，即Dw=200萬，則它的權(quán)重IDF=log(500) =6.2。又假定通用詞“應(yīng)用”，出現(xiàn)在五億個網(wǎng)頁中，它的權(quán)重IDF = log(2)

　　則只有 0.7。也就只說，在網(wǎng)頁中找到一個“原子能”的比配相當(dāng)于找到九個“應(yīng)用”的匹配。利用 IDF，上述相關(guān)性計算個公式就由詞頻的簡單求和變成了加權(quán)求和，即 TF1*IDF1 +　TF2*IDF2 +... + TFN*IDFN。在上面的例子中，該網(wǎng)頁和“原子能的應(yīng)用”的相關(guān)性為 0.0161，其中“原子能”貢獻(xiàn)了 0.0126，而“應(yīng)用”只貢獻(xiàn)了0.0035。這個比例和我們的直覺比較一致了。

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

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