『IR 信息檢索入門必看』#9 網(wǎng)頁排序（簡明）

訪問博客查看 本文 最新內(nèi)容，排版更美觀ヾ(?ω?`)o 如有錯誤歡迎指出~

IR 信息檢索系列筆記：

當(dāng)我們在一個小的文檔庫中查詢時修然，即使 query 很模糊徊哑，我們只要返回所有相關(guān)文檔即可袜刷，甚至不需要猜測用戶的查詢需求。

但如果在一個大的文檔集中查詢時（比如谷歌）莺丑，往往可以返回大量的相關(guān)文檔著蟹。如果基于相關(guān)度的 ranking，往往無法區(qū)分哪些文檔該呈現(xiàn)在最前面梢莽，甚至可能時一些低質(zhì)量的網(wǎng)頁對于某些詞的詞頻很高萧豆，從而排在了前面。

此時我們就不能只聚焦與「相關(guān)度」昏名，PageRank 算法通過計算一個頁面的「重要度」涮雷，從而判別網(wǎng)頁質(zhì)量，得到排序轻局。

基本思想

如何衡量「重要度」洪鸭？用點擊率、權(quán)威性仑扑？然而览爵，這些數(shù)據(jù)都是爬蟲無法爬取到的，同時也難以正確衡量镇饮。

科學(xué)家們從 Bibliometrics (文獻計量學(xué)) 中借鑒了如下觀點：

  • Bibliographic coupling (引文耦合)：兩篇文章具有相近的引用蜓竹。
  • Co-citation (協(xié)同引用)：兩篇文章被大量其他文章同時引用该互。
  • Impact factor (影響因子)：一個期刊中的文章的年平均被引次數(shù)，衡量了一個期刊的「重要度」奔穿。

例如番挺，最權(quán)威的 SCI 往往只收錄其認(rèn)為重要的期刊，也只記錄其中的期刊相互引用的次數(shù)簇秒。當(dāng)一篇文章被 SCI 收錄的文章引用時，通常也可以說明其有一定的影響力——即重要度的「傳遞」。

對于文獻引用的可視化肺缕，我們通常稱為 Citation Graph，通常是一個 Directed Acyclic Graph (有向無環(huán)圖，DAG)同木，因為較早的文章無法修改而引用后來的文章浮梢。

在網(wǎng)頁中，我們可以 Hyperlinks (超鏈接) 來類比引用彤路，從而形成一個 Hyperlink Graph秕硝，區(qū)別是這類圖中可以有環(huán)路。

從而引出網(wǎng)頁排序的基本假設(shè)：

  • The rank of a web page is higher if many pages link to it.
  • Links from highly ranked pages are given greater weight than links from less highly ranked pages.

PageRank Algorithm

基于上述假設(shè)洲尊，我們很容易可以得到當(dāng)前頁面的鏈入远豺、鏈出數(shù)。但是坞嘀，要怎么知道鏈入當(dāng)前頁面的前序頁面躯护，其重要度是多少呢？

隨機游走模型 | Random Walk Model

在一個封閉的 Hyperlink Graph 中丽涩，隨機選取一個頁面作為訪問起點棺滞，隨機選取其鏈出的頁面進行訪問，再對下一個頁面重復(fù)上述操作矢渊。

大量重復(fù)后继准，統(tǒng)計每個結(jié)點被訪問的頻率，用頻率近似概率后矮男，我們可以發(fā)現(xiàn)訪問概率較大者通常有著較多的鏈入锰瘸，或者其鏈入頁面也有著較大的訪問概率。用公式表示就是：
\mathrm{Pr}\left( P_i \right) =\mathrm{Pr}\left( P_i\mid P_1 \right) \mathrm{Pr}\left( P_1 \right) +\mathrm{Pr}\left( P_i\mid P_2 \right) \mathrm{Pr}\left( P_2 \right) +\cdots +\mathrm{Pr}\left( P_i\mid P_N \right) \mathrm{Pr}\left( P_N \right)
其中 \mathrm{Pr}\left( P_i\mid P_1 \right) 表示從編號為 1 的網(wǎng)頁跳轉(zhuǎn)到編號為 i 的網(wǎng)頁的概率昂灵，其計算方式為：
\mathrm{Pr}\left( P_i\mid P_1 \right) =\begin{cases} 0\text{避凝，如果}P_1\text{到}P_i\text{沒有鏈入}\\ \frac{1}{m}\text{，}m\text{為}P_1\text{的鏈出數(shù)}\\ \end{cases}

矩陣表示 | Matrix Representation

令 w_i=\mathrm{Pr}\left( P_i \right)眨补，則 \boldsymbol{w}=\left[ \mathrm{Pr}\left( P_1 \right) ,\mathrm{Pr}\left( P_2 \right) ,\cdots ,\mathrm{Pr}\left( P_N \right) \right] ^T管削，再令 \boldsymbol{B}_i=\left[ \mathrm{Pr}\left( P_i\mid P_1 \right) ,\mathrm{Pr}\left( P_i\mid P_2 \right) ,\cdots ,\mathrm{Pr}\left( P_i\mid P_N \right) \right]，則有：

w_{i}=B_i\cdot \boldsymbol{w}

特別地撑螺，當(dāng) i 取遍 1 到 N 的所有值后含思， 得到矩陣形式：
\boldsymbol{w}=B\cdot \boldsymbol{w}
其中 B 稱作標(biāo)準(zhǔn)化鏈接矩陣，矩陣中的每個元素代表列號對應(yīng)的 Page 鏈入行號對應(yīng)的 Page 的概率甘晤，每列之和為 1含潘。當(dāng)一個頁面沒有鏈出時，這一列全為 0线婚。

于是我們可以用迭代方法求解這個方程的穩(wěn)定解 \boldsymbol{w}_k——即我們想求的訪問概率向量遏弱，也就是重要度向量。只需要將 \boldsymbol{w}_0 設(shè)為全 1 向量（因為一開始隨機訪問到每個頁面的概率都相同）塞弊，不斷代入即可漱逸。

阻尼迭代 | PageRank with Damping

然而泪姨，現(xiàn)在存在的問題是，上面的所有推導(dǎo)都是建立在理想狀態(tài)下的饰抒，即假設(shè)所有網(wǎng)頁組成的這個有向圖是強連通的肮砾。

當(dāng) Hyperlink Graph 存在 link loops (循環(huán)陷阱)，即存在一個小的子圖袋坑，只有鏈入沒有鏈出仗处，所有隨機游走的用戶到了這幾個網(wǎng)頁后，就如同進了黑洞一般枣宫，一直在里面“打轉(zhuǎn)”婆誓，出不來了。

這樣就使得當(dāng)游走次數(shù)趨于無窮時镶柱，最終陷阱中結(jié)點的訪問次數(shù)遠大于其他結(jié)點旷档。這樣會使得計算出的 \boldsymbol{w} 向量中，陷阱外的結(jié)點訪問概率都為 0歇拆。

PageRank 算法最終采用了阻尼因子（damping factor）的修正鞋屈，使得進入陷阱后仍有機會跳出循環(huán)。
\boldsymbol{w}_k=d\boldsymbol{w}_0+\left( 1-d \right) B\cdot \boldsymbol{w}_{k-1}
其中 \boldsymbol{w}_0 為全 1 向量故觅，d 是實驗確定的常數(shù)厂庇，通常取 0.15。

結(jié)合相關(guān)度 | Combined Method

有了重要度向量后输吏，當(dāng)有查詢時权旷，我們只需要先確定命中文檔（至少有一個 term 與 query 相同的文檔），再將其用重要度排序即可贯溅。

然而拄氯，這樣做的缺點是，沒有考慮到查詢和文檔的相關(guān)性——即它浅，有可能一篇文檔雖然有相同的 term译柏，但主題卻相去甚遠。

于是姐霍，有人提出了結(jié)合 Term Weighting 和 PageRank 的方法鄙麦，在確定命中文檔后，利用傳統(tǒng)的權(quán)重計算方法镊折，計算出 query 和每個 doc 的相似度 s_j胯府。再和重要度 p_j 線性加權(quán)算出排序指標(biāo)：
c_j=\lambda s_j+\left( 1-\lambda \right) p_j
其中 \lambda 為實驗確定的常數(shù)。

PageRank 算法缺點

  1. 忽略了查詢恨胚，則忽略了 query 和 doc 主題相關(guān)性骂因，導(dǎo)致結(jié)果的相關(guān)性降低。

  2. 沒有過濾廣告鏈接和功能鏈接（例如常見的分享鏈接）与纽。這些鏈接通常沒有什么實際價值侣签，前者鏈接到廣告頁面塘装，后者常常鏈接到某個社交網(wǎng)站首頁急迂。

  3. 對新網(wǎng)頁不友好影所。因為即使是非常好的新頁面也不會有很多鏈入，要成為一個高重要度的頁面仍需要很長時間的推廣僚碎。

主題敏感 PR | Topic-Sensitive PageRank

在實際的網(wǎng)絡(luò)中猴娩，PageRank 算法還存在「主題漂移」問題，特別對于大量隨意交互外鏈的站點勺阐，會導(dǎo)致搜索引擎返回主題無關(guān)結(jié)果卷中。

同時，前面的討論提到渊抽，PageRank 忽略了 query 的主題相關(guān)性蟆豫，也導(dǎo)致了結(jié)果的相關(guān)性降低。同一查詢詞在不同語境下懒闷，語義上指向的可能是不同的主題十减，但 PageRank 無論如何都是返回「重要度」最高的頁面。

理想情況下愤估，應(yīng)為每個用戶的偏好維護一套專用的「主題重要度」向量帮辟，但面對海量用戶這種方法顯然不可行。所以搜索引擎一般會選擇一種稱為主題敏感的折中方案玩焰。

基本思想 | Basic Idea

基本假設(shè)：在 PageRank 的隨機游走模型中由驹，用戶傾向于選擇具有同一個主題的鏈出網(wǎng)頁。

基于這個假設(shè)昔园，可以預(yù)定義幾個話題類別蔓榄，例如體育、娛樂默刚、科技等等甥郑，對于某個網(wǎng)頁來說，對應(yīng)某個主題類型都有相應(yīng)的 PageRank 分值羡棵，然后想辦法關(guān)聯(lián)用戶的話題傾向壹若，根據(jù)用戶的話題傾向排序結(jié)果。

矩陣形式 | Matrix Form

與原始的 PageRank 不同皂冰，新的算法對出度為 0 的網(wǎng)站加以處理以保證收斂性店展。引入了向量 \boldsymbolm3maa38 來指示某一個網(wǎng)頁是否出度為 0，若為 0 則對應(yīng)項為 1秃流。
d_{i}= \begin{cases}1 & \text { if } \operatorname{deg}(j)=0 \\ 0 & \text { otherwise }\end{cases}

向量 \boldsymbol{p} 來表示訪問各個網(wǎng)頁的概率均等赂蕴，代替 \boldsymbol{w}_0 的寫法：

\boldsymbol{p}=\left[\frac{1}{n}\right]_{n \times 1}

兩個矩陣的乘積所得的矩陣 D 表示出度為 0 的網(wǎng)頁將以均等概率訪問其他網(wǎng)頁。與前述提到的矩陣 B 具有互補的特性舶胀，補充了在隨機游走模型中概说，一個網(wǎng)頁出度為 0 時的訪問頁面的情況碧注。這樣做使得最終矩陣的每一列之和都為 1。
D=\boldsymbol{p} \times \boldsymbolbaapzb2^{T}
則最終排名的計算方法為：
\boldsymbol{Rank} =d \boldsymbol{p} + (1-d)(B+D) \cdot \boldsymbol{Rank}

偏置向量 | ODP-Biasing

主題的預(yù)定義參考了 ODP (Open Directory Project) 網(wǎng)站糖赔，利用 ODP 中 16 個頂級分類下的 URLs 生成了 16 組偏置 PageRank 向量 (biased PageRank vectors)萍丐。

為了實現(xiàn)這一點，算法中采用了新的向量 \boldsymbol{v_j}=\boldsymbol{p}放典，針對每個主題有：
v_{j i}=\left\{\begin{array}{cl} \frac{1}{\left|T_{j}\right|} & i \in T_{j} \\ 0 & i \notin T_{j} \end{array}\right.
其中 T_{j} 表示在契合第 j 個主題的網(wǎng)頁集合逝变。包含在這些網(wǎng)頁中的頁面被賦予較大的跳轉(zhuǎn)概率值，而其他網(wǎng)站則相對減少奋构。

查詢打分 | Query-Time Importance Score

此外壳影，還需要在給定一個查詢 q 的時候，估算出該查詢落在某個主題 c_j 的概率弥臼。文章使用了樸素貝葉斯分類器（naive-Bayes classifier）宴咧，將查詢 q 中的每個 term 分詞記作 q_i，利用貝葉斯公式：
P\left(c_{j} \mid q\right)=\frac{p\left(c_{j}\right) \cdot P\left(q \mid c_{j}\right)}{P\left(q\right)} \propto P\left(c_{j}\right) \cdot \prod_{i} P\left(q_{i} \mid c_{j}\right)
而 P\left(q_{i} \mid c_{j}\right) 則容易用統(tǒng)計的方法估計出來径缅，對于 P\left(c_{j}\right) 則采用先驗概率的方法掺栅，根據(jù)用戶的查詢歷史（上下文）進行動態(tài)調(diào)整。

計算出了查詢落在各個主題的概率后芥驳，再用這個概率對各個主題下的 Rank 向量進行線性加權(quán)柿冲，即可得到最終排序用的評分：
s_{q d}=\sum_{j} P\left(c_{j} \mid q^{\prime}\right) \cdot r_{j d}

HITS: Hyperlink-Induced Topic Search

這里再介紹一種基礎(chǔ)的網(wǎng)頁排序算法——基于超鏈接追敏的主題排序，對于一個查詢兆旬，不再返回單一的網(wǎng)頁排名假抄，而是同時返回兩個列表：

  • 包含鏈接的 Hub 網(wǎng)頁，收錄了主題相關(guān)的權(quán)威網(wǎng)頁鏈接丽猬。
  • 包含內(nèi)容的 Authority 網(wǎng)頁宿饱，有著與主題相關(guān)的高質(zhì)量內(nèi)容。

那么脚祟，如何排序這兩個列表呢谬以？

基本假設(shè)：

  • 一個好的 Hub 網(wǎng)頁指向該主題的許多 Authority 網(wǎng)頁。
  • 一個好的 Authority 網(wǎng)頁被許多好的 Hub 網(wǎng)頁指向由桌。

基于這兩個假設(shè)为黎，我們可以提出兩個指標(biāo)來衡量每個頁面：樞紐值（Hub Scores）和權(quán)威值（Authority Scores），這兩種值是互相依存行您、互相影響的铭乾。

  • 樞紐值，指的是頁面上所有出鏈指向頁面的權(quán)威值之和娃循。
  • 權(quán)威值炕檩，指的是頁面的所有入鏈所在的原頁面的樞紐值之和。

算法步驟 | HITS Algorithm

  1. 找出 root set：根據(jù)用戶 query 中的 term捌斧，在文檔集中找出包含至少一個 term 的的文檔笛质，使他們構(gòu)成 root set泉沾。

  2. 找出 base set：在 root set 的基礎(chǔ)上，找出集合中網(wǎng)頁鏈入或鏈出并且不在 root set 中的網(wǎng)頁妇押，并把他們加入到集合中跷究，從而構(gòu)成 base set。

  3. 計算每一個網(wǎng)頁的樞紐值 h(x) 和權(quán)威值 a(x)舆吮，初始時揭朝，所有 h 值和 a 值均為 1队贱。

  4. 迭代更新兩個值直至收斂色冀。為了防止兩個值太大，可以在每次迭代后歸一化柱嫌。歸一化的指標(biāo)不重要锋恬，因為我們只關(guān)注相對排名。

  5. 返回兩個值分別排序的列表编丘。

HITS 算法缺點

  1. 盡管限制了計算對象在 base set 中与学，但在線計算效率還是太低，不如 PR 快嘉抓。
  2. 主題漂移現(xiàn)象仍未解決索守。如果在集合里包含與查詢主題無關(guān)的頁面，且含有大量相互鏈接抑片，可能會排到前列卵佛。這種現(xiàn)象被稱為緊密鏈接社區(qū)現(xiàn)象。
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末敞斋，一起剝皮案震驚了整個濱河市截汪，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌植捎，老刑警劉巖衙解，帶你破解...
    沈念sama閱讀 219,589評論 6贊 508
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異焰枢，居然都是意外死亡蚓峦，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,615評論 3贊 396
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門济锄，熙熙樓的掌柜王于貴愁眉苦臉地迎上來暑椰，“玉大人，你說我怎么就攤上這事拟淮「绍裕” “怎么了？”我有些...
    開封第一講書人閱讀 165,933評論 0贊 356
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵很泊，是天一觀的道長角虫。 經(jīng)常有香客問我沾谓，道長，這世上最難降的妖魔是什么戳鹅？ 我笑而不...
    開封第一講書人閱讀 58,976評論 1贊 295
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任均驶，我火速辦了婚禮，結(jié)果婚禮上枫虏，老公的妹妹穿的比我還像新娘妇穴。我一直安慰自己，他們只是感情好隶债，可當(dāng)我...
    茶點故事閱讀 67,999評論 6贊 393
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布腾它。 她就那樣靜靜地躺著，像睡著了一般死讹。 火紅的嫁衣襯著肌膚如雪瞒滴。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 51,775評論 1贊 307
  • 城市分裂傳說
    那天赞警，我揣著相機與錄音妓忍，去河邊找鬼。 笑死愧旦，一個胖子當(dāng)著我的面吹牛世剖，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播笤虫，決...
    沈念sama閱讀 40,474評論 3贊 420
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼旁瘫，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了耕皮？” 一聲冷哼從身側(cè)響起境蜕，我...
    開封第一講書人閱讀 39,359評論 0贊 276
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎凌停，沒想到半個月后粱年，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 45,854評論 1贊 317
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡罚拟，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,007評論 3贊 338
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年台诗，在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片赐俗。...
    茶點故事閱讀 40,146評論 1贊 351
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡拉队，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出阻逮，到底是詐尸還是另有隱情粱快，我是刑警寧澤，帶...
    沈念sama閱讀 35,826評論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站事哭，受9級特大地震影響漫雷，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜鳍咱，卻給世界環(huán)境...
    茶點故事閱讀 41,484評論 3贊 331
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一降盹、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧谤辜，春花似錦蓄坏、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,029評論 0贊 22
  • 一樁弒父案涡戳，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至渠欺，卻和暖如春妹蔽，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背挠将。 一陣腳步聲響...
    開封第一講書人閱讀 33,153評論 1贊 272
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留编整，地道東北人舔稀。 一個月前我還...
    沈念sama閱讀 48,420評論 3贊 373
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像掌测，于是被迫代替她去往敵國和親内贮。 傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,107評論 2贊 356

推薦閱讀更多精彩內(nèi)容