久久国产成人av_抖音国产毛片_a片网站免费观看_A片无码播放手机在线观看,色五月在线观看,亚洲精品m在线观看,女人自慰的免费网址,悠悠在线观看精品视频,一级日本片免费的,亚洲精品久,国产精品成人久久久久久久

分享

淺析PageRank算法

 心不留意外塵 2013-09-13
淺析PageRank算法
作者 張洋 | 發(fā)布于 2012-07-02
Google PageRank 搜索引擎 算法
from http://blog./articles/intro-to-pagerank.html

很早就對(duì)Google的PageRank算法很感興趣,,但一直沒(méi)有深究,只有個(gè)輪廓性的概念,。前幾天趁團(tuán)隊(duì)outing的機(jī)會(huì),,在動(dòng)車上看了一些相關(guān)的資料(PS:在動(dòng)車上看看書(shū)真是一種享受),趁熱打鐵,,將所看的東西整理成此文,。

本文首先會(huì)討論搜索引擎的核心難題,同時(shí)討論早期搜索引擎關(guān)于結(jié)果頁(yè)面重要性評(píng)價(jià)算法的困境,,借此引出PageRank產(chǎn)生的背景,。第二部分會(huì)詳細(xì)討論P(yáng)ageRank的思想來(lái)源,、基礎(chǔ)框架,并結(jié)合互聯(lián)網(wǎng)頁(yè)面拓?fù)浣Y(jié)構(gòu)討論P(yáng)ageRank處理Dead Ends及平滑化的方法,。第三部分討論Topic-Sensitive PageRank算法,。最后將討論對(duì)PageRank的Spam攻擊方法:Spam Farm以及搜索引擎對(duì)Spam Farm的防御。

搜索引擎的難題

Google早已成為全球最成功的互聯(lián)網(wǎng)搜索引擎,,但這個(gè)當(dāng)前的搜索引擎巨無(wú)霸卻不是最早的互聯(lián)網(wǎng)搜索引擎,,在Google出現(xiàn)之前,曾出現(xiàn)過(guò)許多通用或?qū)I(yè)領(lǐng)域搜索引擎,。Google最終能擊敗所有競(jìng)爭(zhēng)對(duì)手,,很大程度上是因?yàn)樗鉀Q了困擾前輩們的最大難題:對(duì)搜索結(jié)果按重要性排序。而解決這個(gè)問(wèn)題的算法就是PageRank,。毫不夸張的說(shuō),,是PageRank算法成就了Google今天的低位。要理解為什么解決這個(gè)難題如此重要,,我們先來(lái)看一下搜索引擎的核心框架,。

搜索引擎的核心框架

雖然搜索引擎已經(jīng)發(fā)展了很多年,但是其核心卻沒(méi)有太大變化,。從本質(zhì)上說(shuō),,搜索引擎是一個(gè)資料檢索系統(tǒng),搜索引擎擁有一個(gè)資料庫(kù)(具體到這里就是互聯(lián)網(wǎng)頁(yè)面),,用戶提交一個(gè)檢索條件(例如關(guān)鍵詞),,搜索引擎返回符合查詢條件的資料列表。理論上檢索條件可以非常復(fù)雜,,為了簡(jiǎn)單起見(jiàn),,我們不妨設(shè)檢索條件是一至多個(gè)以空格分隔的詞,而其表達(dá)的語(yǔ)義是同時(shí)含有這些詞的資料(等價(jià)于布爾代數(shù)的邏輯與),。例如,,提交“張洋 博客”,意思就是“給我既含有‘張洋’又含有‘博客’詞語(yǔ)的頁(yè)面”,,以下是Google對(duì)這條關(guān)鍵詞的搜索結(jié)果:

可以看到我的博客出現(xiàn)在第五條,,而第四條是我之前在博客園的博客。

當(dāng)然,,實(shí)際上現(xiàn)在的搜索引擎都是有分詞機(jī)制的,,例如如果以“張洋的博客”為關(guān)鍵詞,搜索引擎會(huì)自動(dòng)將其分解為“張洋 的 博客”三個(gè)詞,,而“的”作為停止詞(Stop Word)會(huì)被過(guò)濾掉,。關(guān)于分詞及詞權(quán)評(píng)價(jià)算法(如TF-IDF算法)是一個(gè)很大的話題,這里就不展開(kāi)討論了,,為了簡(jiǎn)單此處可以將搜索引擎想象為一個(gè)只會(huì)機(jī)械匹配詞語(yǔ)的檢索系統(tǒng),。

這樣看來(lái),建立一個(gè)搜索引擎的核心問(wèn)題就是兩個(gè):1,、建立資料庫(kù),;2、建立一種數(shù)據(jù)結(jié)構(gòu),,可以根據(jù)關(guān)鍵詞找到含有這個(gè)詞的頁(yè)面,。

第一個(gè)問(wèn)題一般是通過(guò)一種叫爬蟲(chóng)(Spider)的特殊程序?qū)崿F(xiàn)的(當(dāng)然,專業(yè)領(lǐng)域搜索引擎例如某個(gè)學(xué)術(shù)會(huì)議的論文檢索系統(tǒng)可能直接從數(shù)據(jù)庫(kù)建立資料庫(kù)),,簡(jiǎn)單來(lái)說(shuō),,爬蟲(chóng)就是從一個(gè)頁(yè)面出發(fā)(例如新浪首頁(yè)),通過(guò)HTTP協(xié)議通信獲取這個(gè)頁(yè)面的所有內(nèi)容,,把這個(gè)頁(yè)面url和內(nèi)容記錄下來(lái)(記錄到資料庫(kù)),,然后分析頁(yè)面中的鏈接,再去分別獲取這些鏈接鏈向頁(yè)面的內(nèi)容,,記錄到資料庫(kù)后再分析這個(gè)頁(yè)面的鏈接……重復(fù)這個(gè)過(guò)程,,就可以將整個(gè)互聯(lián)網(wǎng)的頁(yè)面全部獲取下來(lái)(當(dāng)然這是理想情況,要求整個(gè)Web是一個(gè)強(qiáng)連通(Strongly Connected),,并且所有頁(yè)面的robots協(xié)議允許爬蟲(chóng)抓取頁(yè)面,,為了簡(jiǎn)單,我們?nèi)匀患僭O(shè)Web是一個(gè)強(qiáng)連通圖,,且不考慮robots協(xié)議),。抽象來(lái)看,可以將資料庫(kù)看做一個(gè)巨大的key-value結(jié)構(gòu),,key是頁(yè)面url,,value是頁(yè)面內(nèi)容。

第二個(gè)問(wèn)題是通過(guò)一種叫倒排索引(inverted index)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的,,抽象來(lái)說(shuō)倒排索引也是一組key-value結(jié)構(gòu),,key是關(guān)鍵詞,,value是一個(gè)頁(yè)面編號(hào)集合(假設(shè)資料庫(kù)中每個(gè)頁(yè)面有唯一編號(hào)),表示這些頁(yè)面含有這個(gè)關(guān)鍵詞。本文不詳細(xì)討論倒排索引的建立方法,。

有了上面的分析,就可以簡(jiǎn)要說(shuō)明搜索引擎的核心動(dòng)作了:搜索引擎獲取“張洋 博客”查詢條件,,將其分為“張洋”和“博客”兩個(gè)詞,。然后分別從倒排索引中找到“張洋”所對(duì)應(yīng)的集合,假設(shè)是{1,, 3,, 6, 8,, 11,, 15},;“博客”對(duì)應(yīng)的集合是{1, 6,, 10,, 11, 12,, 17,, 20, 22},,將兩個(gè)集合做交運(yùn)算(intersection),,結(jié)果是{1, 6,, 11},。最后,從資料庫(kù)中找出1,、6,、11對(duì)應(yīng)的頁(yè)面返回給用戶就可以了。

搜索引擎的核心難題

上面闡述了一個(gè)非常簡(jiǎn)單的搜索引擎工作框架,,雖然現(xiàn)代搜索引擎的具體細(xì)節(jié)原理要復(fù)雜的多,,但其本質(zhì)卻與這個(gè)簡(jiǎn)單的模型并無(wú)二異。實(shí)際Google在上述兩點(diǎn)上相比其前輩并無(wú)高明之處,。其最大的成功是解決了第三個(gè),、也是最為困難的問(wèn)題:如何對(duì)查詢結(jié)果排序。

我們知道Web頁(yè)面數(shù)量非常巨大,,所以一個(gè)檢索的結(jié)果條目數(shù)量也非常多,,例如上面“張洋 博客”的檢索返回了超過(guò)260萬(wàn)條結(jié)果。用戶不可能從如此眾多的結(jié)果中一一查找對(duì)自己有用的信息,,所以,,一個(gè)好的搜索引擎必須想辦法將“質(zhì)量”較高的頁(yè)面排在前面。其實(shí)直觀上也可以感覺(jué)出,,在使用搜索引擎時(shí),,我們并不太關(guān)心頁(yè)面是否夠全(上百萬(wàn)的結(jié)果,全不全有什么區(qū)別,?而且實(shí)際上搜索引擎都是取top,,并不會(huì)真的返回全部結(jié)果。),,而很關(guān)心前一兩頁(yè)是否都是質(zhì)量較高的頁(yè)面,,是否能滿足我們的實(shí)際需求。

因此,對(duì)搜索結(jié)果按重要性合理的排序就成為搜索引擎的最大核心,,也是Google最終成功的突破點(diǎn),。

早期搜索引擎的做法

不評(píng)價(jià)

這個(gè)看起來(lái)可能有點(diǎn)搞笑,但實(shí)際上早期很多搜索引擎(甚至包括現(xiàn)在的很多專業(yè)領(lǐng)域搜索引擎)根本不評(píng)價(jià)結(jié)果重要性,,而是直接按照某自然順序(例如時(shí)間順序或編號(hào)順序)返回結(jié)果,。這在結(jié)果集比較少的情況下還說(shuō)得過(guò)去,但是一旦結(jié)果集變大,,用戶叫苦不迭,試想讓你從幾萬(wàn)條質(zhì)量參差不齊的頁(yè)面中尋找需要的內(nèi)容,,簡(jiǎn)直就是一場(chǎng)災(zāi)難,,這也注定這種方法不可能用于現(xiàn)代的通用搜索引擎。

基于檢索詞的評(píng)價(jià)

后來(lái),,一些搜索引擎引入了基于檢索關(guān)鍵詞去評(píng)價(jià)搜索結(jié)構(gòu)重要性的方法,,實(shí)際上,這類方法如TF-IDF算法在現(xiàn)代搜索引擎中仍在使用,,但其已經(jīng)不是評(píng)價(jià)質(zhì)量的唯一指標(biāo),。完整描述TF-IDF比較繁瑣,本文這里用一種更簡(jiǎn)單的抽象模型描述這種方法,。

基于檢索詞評(píng)價(jià)的思想非常樸素:和檢索詞匹配度越高的頁(yè)面重要性越高,。“匹配度”就是要定義的具體度量,。一個(gè)最直接的想法是關(guān)鍵詞出現(xiàn)次數(shù)越多的頁(yè)面匹配度越高,。還是搜索“張洋 博客”的例子:假設(shè)A頁(yè)面出現(xiàn)“張洋”5次,“博客”10次,;B頁(yè)面出現(xiàn)“張洋”2次,,“博客”8次。于是A頁(yè)面的匹配度為5 + 10 = 15,,B頁(yè)面為2 + 8 = 10,,于是認(rèn)為A頁(yè)面的重要性高于B頁(yè)面。很多朋友可能意識(shí)到這里的不合理性:內(nèi)容較長(zhǎng)的網(wǎng)頁(yè)往往更可能比內(nèi)容較短的網(wǎng)頁(yè)關(guān)鍵詞出現(xiàn)的次數(shù)多,。因此,,我們可以修改一下算法,用關(guān)鍵詞出現(xiàn)次數(shù)除以頁(yè)面總詞數(shù),,也就是通過(guò)關(guān)鍵詞占比作為匹配度,,這樣可以克服上面提到的不合理。

早期一些搜索引擎確實(shí)是基于類似的算法評(píng)價(jià)網(wǎng)頁(yè)重要性的,。這種評(píng)價(jià)算法看似依據(jù)充分,、實(shí)現(xiàn)直觀簡(jiǎn)單,但卻非常容易受到一種叫“Term Spam”的攻擊,。

Term Spam

其實(shí)從搜索引擎出現(xiàn)的那天起,,spammer和搜索引擎反作弊的斗法就沒(méi)有停止過(guò),。Spammer是這樣一群人——試圖通過(guò)搜索引擎算法的漏洞來(lái)提高目標(biāo)頁(yè)面(通常是一些廣告頁(yè)面或垃圾頁(yè)面)的重要性,使目標(biāo)頁(yè)面在搜索結(jié)果中排名靠前,。

現(xiàn)在假設(shè)Google單純使用關(guān)鍵詞占比評(píng)價(jià)頁(yè)面重要性,,而我想讓我的博客在搜索結(jié)果中排名更靠前(最好排第一)。那么我可以這么做:在頁(yè)面中加入一個(gè)隱藏的html元素(例如一個(gè)div),,然后其內(nèi)容是“張洋”重復(fù)一萬(wàn)次,。這樣,搜索引擎在計(jì)算“張洋 博客”的搜索結(jié)果時(shí),,我的博客關(guān)鍵詞占比就會(huì)非常大,,從而做到排名靠前的效果。更進(jìn)一步,,我甚至可以干擾別的關(guān)鍵詞搜索結(jié)果,,例如我知道現(xiàn)在歐洲杯很火熱,我就在我博客的隱藏div里加一萬(wàn)個(gè)“歐洲杯”,,當(dāng)有用戶搜索歐洲杯時(shí),,我的博客就能出現(xiàn)在搜索結(jié)果較靠前的位置。這種行為就叫做“Term Spam”,。

早期搜索引擎深受這種作弊方法的困擾,,加之基于關(guān)鍵詞的評(píng)價(jià)算法本身也不甚合理,因此經(jīng)常是搜出一堆質(zhì)量低下的結(jié)果,,用戶體驗(yàn)大大打了折扣,。而Google正是在這種背景下,提出了PageRank算法,,并申請(qǐng)了專利保護(hù),。此舉充分保護(hù)了當(dāng)時(shí)相對(duì)弱小Google,也使得Google一舉成為全球首屈一指的搜索引擎,。

PageRank算法

上文已經(jīng)說(shuō)到,,PageRank的作用是評(píng)價(jià)網(wǎng)頁(yè)的重要性,以此作為搜索結(jié)果的排序重要依據(jù)之一,。實(shí)際中,,為了抵御spam,各個(gè)搜索引擎的具體排名算法是保密的,,PageRank的具體計(jì)算方法也不盡相同,,本節(jié)介紹一種最簡(jiǎn)單的基于頁(yè)面鏈接屬性的PageRank算法。這個(gè)算法雖然簡(jiǎn)單,,卻能揭示PageRank的本質(zhì),,實(shí)際上目前各大搜索引擎在計(jì)算PageRank時(shí)鏈接屬性確實(shí)是重要度量指標(biāo)之一。

簡(jiǎn)單PageRank計(jì)算

首先,我們將Web做如下抽象:1,、將每個(gè)網(wǎng)頁(yè)抽象成一個(gè)節(jié)點(diǎn),;2、如果一個(gè)頁(yè)面A有鏈接直接鏈向B,,則存在一條有向邊從A到B(多個(gè)相同鏈接不重復(fù)計(jì)算邊),。因此,整個(gè)Web被抽象為一張有向圖,。

現(xiàn)在假設(shè)世界上只有四張網(wǎng)頁(yè):A,、B、C,、D,,其抽象結(jié)構(gòu)如下圖:

顯然這個(gè)圖是強(qiáng)連通的(從任一節(jié)點(diǎn)出發(fā)都可以到達(dá)另外任何一個(gè)節(jié)點(diǎn))。

然后需要用一種合適的數(shù)據(jù)結(jié)構(gòu)表示頁(yè)面間的連接關(guān)系,。其實(shí),PageRank算法是基于這樣一種背景思想:被用戶訪問(wèn)越多的網(wǎng)頁(yè)更可能質(zhì)量越高,,而用戶在瀏覽網(wǎng)頁(yè)時(shí)主要通過(guò)超鏈接進(jìn)行頁(yè)面跳轉(zhuǎn),,因此我們需要通過(guò)分析超鏈接組成的拓?fù)浣Y(jié)構(gòu)來(lái)推算每個(gè)網(wǎng)頁(yè)被訪問(wèn)頻率的高低。最簡(jiǎn)單的,,我們可以假設(shè)當(dāng)一個(gè)用戶停留在某頁(yè)面時(shí),,跳轉(zhuǎn)到頁(yè)面上每個(gè)被鏈頁(yè)面的概率是相同的。例如,,上圖中A頁(yè)面鏈向B,、C、D,,所以一個(gè)用戶從A跳轉(zhuǎn)到B,、C、D的概率各為1/3,。設(shè)一共有N個(gè)網(wǎng)頁(yè),,則可以組織這樣一個(gè)N維矩陣:其中i行j列的值表示用戶從頁(yè)面j轉(zhuǎn)到頁(yè)面i的概率。這樣一個(gè)矩陣叫做轉(zhuǎn)移矩陣(Transition Matrix),。下面的轉(zhuǎn)移矩陣M對(duì)應(yīng)上圖:

M=?????01/31/31/31/201/2000011/21/200?????

然后,,設(shè)初始時(shí)每個(gè)頁(yè)面的rank值為1/N,這里就是1/4,。按A-D順序?qū)㈨?yè)面rank為向量v:

v=?????1/41/41/41/4?????

注意,,M第一行分別是A、B,、C和D轉(zhuǎn)移到頁(yè)面A的概率,,而v的第一列分別是A、B、C和D當(dāng)前的rank,,因此用M的第一行乘以v的第一列,,所得結(jié)果就是頁(yè)面A最新rank的合理估計(jì),同理,,Mv的結(jié)果就分別代表A,、B、C,、D新rank:

Mv=?????1/45/245/241/3?????

然后用M再乘以這個(gè)新的rank向量,,又會(huì)產(chǎn)生一個(gè)更新的rank向量。迭代這個(gè)過(guò)程,,可以證明v最終會(huì)收斂,,即v約等于Mv,此時(shí)計(jì)算停止,。最終的v就是各個(gè)頁(yè)面的pagerank值,。例如上面的向量經(jīng)過(guò)幾步迭代后,大約收斂在(1/4, 1/4, 1/5, 1/4),,這就是A,、B、C,、D最后的pagerank,。

處理Dead Ends

上面的PageRank計(jì)算方法假設(shè)Web是強(qiáng)連通的,但實(shí)際上,,Web并不是強(qiáng)連通(甚至不是聯(lián)通的),。下面看看PageRank算法如何處理一種叫做Dead Ends的情況。

所謂Dead Ends,,就是這樣一類節(jié)點(diǎn):它們不存在外鏈,。看下面的圖:

注意這里D頁(yè)面不存在外鏈,,是一個(gè)Dead End,。上面的算法之所以能成功收斂到非零值,很大程度依賴轉(zhuǎn)移矩陣這樣一個(gè)性質(zhì):每列的加和為1,。而在這個(gè)圖中,,M第四列將全為0。在沒(méi)有Dead Ends的情況下,,每次迭代后向量v各項(xiàng)的和始終保持為1,,而有了Dead Ends,迭代結(jié)果將最終歸零(要解釋為什么會(huì)這樣,,需要一些矩陣論的知識(shí),,比較枯燥,,此處略)。

處理Dead Ends的方法如下:迭代拿掉圖中的Dead Ends節(jié)點(diǎn)及Dead Ends節(jié)點(diǎn)相關(guān)的邊(之所以迭代拿掉是因?yàn)楫?dāng)目前的Dead Ends被拿掉后,,可能會(huì)出現(xiàn)一批新的Dead Ends),,直到圖中沒(méi)有Dead Ends。對(duì)剩下部分計(jì)算rank,,然后以拿掉Dead Ends逆向順序反推Dead Ends的rank,。

以上圖為例,首先拿到D和D相關(guān)的邊,,D被拿到后,,C就變成了一個(gè)新的Dead Ends,于是拿掉C,,最終只剩A,、B。此時(shí)可很容易算出A,、B的PageRank均為1/2,。然后我們需要反推Dead Ends的rank,最后被拿掉的是C,,可以看到C前置節(jié)點(diǎn)有A和B,,而A和B的出度分別為3和2,因此C的rank為:1/2 * 1/3 + 1/2 * 1/2 = 5/12,;最后,D的rank為:1/2 * 1/3 + 5/12 * 1 = 7/12,。所以最終的PageRank為(1/2, 1/2, 5/12, 7/12),。

Spider Traps及平滑處理

可以預(yù)見(jiàn),如果把真實(shí)的Web組織成轉(zhuǎn)移矩陣,,那么這將是一個(gè)極為稀疏的矩陣,,從矩陣論知識(shí)可以推斷,極度稀疏的轉(zhuǎn)移矩陣迭代相乘可能會(huì)使得向量v變得非常不平滑,,即一些節(jié)點(diǎn)擁有很大的rank,,而大多數(shù)節(jié)點(diǎn)rank值接近0。而一種叫做Spider Traps節(jié)點(diǎn)的存在加劇了這種不平滑,。例如下圖:

D有外鏈所以不是Dead Ends,,但是它只鏈向自己(注意鏈向自己也算外鏈,當(dāng)然同時(shí)也是個(gè)內(nèi)鏈),。這種節(jié)點(diǎn)叫做Spider Trap,,如果對(duì)這個(gè)圖進(jìn)行計(jì)算,會(huì)發(fā)現(xiàn)D的rank越來(lái)越大趨近于1,,而其它節(jié)點(diǎn)rank值幾乎歸零,。

為了克服這種由于矩陣稀疏性和Spider Traps帶來(lái)的問(wèn)題,,需要對(duì)PageRank計(jì)算方法進(jìn)行一個(gè)平滑處理,具體做法是加入“心靈轉(zhuǎn)移(teleporting)”,。所謂心靈轉(zhuǎn)移,,就是我們認(rèn)為在任何一個(gè)頁(yè)面瀏覽的用戶都有可能以一個(gè)極小的概率瞬間轉(zhuǎn)移到另外一個(gè)隨機(jī)頁(yè)面。當(dāng)然,,這兩個(gè)頁(yè)面可能不存在超鏈接,,因此不可能真的直接轉(zhuǎn)移過(guò)去,心靈轉(zhuǎn)移只是為了算法需要而強(qiáng)加的一種純數(shù)學(xué)意義的概率數(shù)字,。

加入心靈轉(zhuǎn)移后,,向量迭代公式變?yōu)椋?/p>

v=(1?β)Mv+eβN

其中β往往被設(shè)置為一個(gè)比較小的參數(shù)(0.2或更小),,e為N維單位向量,,加入e的原因是這個(gè)公式的前半部分是向量,因此必須將β/N轉(zhuǎn)為向量才能相加,。這樣,,整個(gè)計(jì)算就變得平滑,因?yàn)槊看蔚慕Y(jié)果除了依賴轉(zhuǎn)移矩陣外,,還依賴一個(gè)小概率的心靈轉(zhuǎn)移,。

以上圖為例,轉(zhuǎn)移矩陣M為:

M=?????01/31/31/31/201/2000010001?????

設(shè)β為0.2,,則加權(quán)后的M為:

M=?????04/154/154/152/502/500004/50004/5?????

因此:

v=?????04/154/154/152/502/500004/50004/5?????v+?????1/201/201/201/20?????

如果按這個(gè)公式迭代算下去,,會(huì)發(fā)現(xiàn)Spider Traps的效應(yīng)被抑制了,從而每個(gè)頁(yè)面都擁有一個(gè)合理的pagerank,。

Topic-Sensitive PageRank

其實(shí)上面的討論我們回避了一個(gè)事實(shí),,那就是“網(wǎng)頁(yè)重要性”其實(shí)沒(méi)一個(gè)標(biāo)準(zhǔn)答案,對(duì)于不同的用戶,,甚至有很大的差別,。例如,當(dāng)搜索“蘋(píng)果”時(shí),,一個(gè)數(shù)碼愛(ài)好者可能是想要看iphone的信息,,一個(gè)果農(nóng)可能是想看蘋(píng)果的價(jià)格走勢(shì)和種植技巧,而一個(gè)小朋友可能在找蘋(píng)果的簡(jiǎn)筆畫(huà),。理想情況下,,應(yīng)該為每個(gè)用戶維護(hù)一套專用向量,但面對(duì)海量用戶這種方法顯然不可行,。所以搜索引擎一般會(huì)選擇一種稱為Topic-Sensitive的折中方案,。Topic-Sensitive PageRank的做法是預(yù)定義幾個(gè)話題類別,例如體育,、娛樂(lè),、科技等等,,為每個(gè)話題單獨(dú)維護(hù)一個(gè)向量,然后想辦法關(guān)聯(lián)用戶的話題傾向,,根據(jù)用戶的話題傾向排序結(jié)果,。

Topic-Sensitive PageRank分為以下幾步:

1、確定話題分類,。

一般來(lái)說(shuō),,可以參考Open Directory(DMOZ)的一級(jí)話題類別作為topic。目前DMOZ的一級(jí)topic有:Arts(藝術(shù)),、Business(商務(wù)),、Computers(計(jì)算機(jī))、Games(游戲),、Health(醫(yī)療健康),、Home(居家)、Kids and Teens(兒童),、News(新聞),、Recreation(娛樂(lè)修養(yǎng))、Reference(參考),、Regional(地域),、Science(科技)、Shopping(購(gòu)物),、Society(人文社會(huì)),、Sports(體育)。

2,、網(wǎng)頁(yè)topic歸屬,。

這一步需要將每個(gè)頁(yè)面歸入最合適的分類,具體歸類有很多算法,,例如可以使用TF-IDF基于詞素歸類,也可以聚類后人工歸類,,具體不再展開(kāi),。這一步最終的結(jié)果是每個(gè)網(wǎng)頁(yè)被歸到其中一個(gè)topic。

3,、分topic向量計(jì)算,。

在Topic-Sensitive PageRank中,向量迭代公式為

v=(1?β)Mv+sβ|s|

首先是單位向量e變?yōu)榱藄,。s是這樣一個(gè)向量:對(duì)于某topic的s,,如果網(wǎng)頁(yè)k在此topic中,則s中第k個(gè)元素為1,,否則為0,。注意對(duì)于每一個(gè)topic都有一個(gè)不同的s,。而|s|表示s中1的數(shù)量。

還是以上面的四張頁(yè)面為例,,假設(shè)頁(yè)面A歸為Arts,,B歸為Computers,C歸為Computers,,D歸為Sports,。那么對(duì)于Computers這個(gè)topic,s就是:

s=???0110???

而|s|=2,。因此,,迭代公式為:

v=?????04/154/154/152/502/500004/50004/5?????v+????01/101/100????

最后算出的向量就是Computers這個(gè)topic的rank。如果實(shí)際計(jì)算一下,,會(huì)發(fā)現(xiàn)B,、C頁(yè)在這個(gè)topic下的權(quán)重相比上面非Topic-Sensitive的rank會(huì)升高,這說(shuō)明如果用戶是一個(gè)傾向于Computers topic的人(例如程序員),,那么在給他呈現(xiàn)的結(jié)果中B,、C會(huì)更重要,因此可能排名更靠前,。

4,、確定用戶topic傾向。

最后一步就是在用戶提交搜索時(shí),,確定用戶的topic傾向,,以選擇合適的rank向量。主要方法有兩種,,一種是列出所有topic讓用戶自己選擇感興趣的項(xiàng)目,,這種方法在一些社交問(wèn)答網(wǎng)站注冊(cè)時(shí)經(jīng)常使用;另外一種方法就是通過(guò)某種手段(如cookie跟蹤)跟蹤用戶的行為,,進(jìn)行數(shù)據(jù)分析判斷用戶的傾向,,這本身也是一個(gè)很有意思的話題,按時(shí)這個(gè)話題超出本文的范疇,,不再展開(kāi)細(xì)說(shuō),。

針對(duì)PageRank的Spam攻擊與反作弊

上文說(shuō)過(guò),Spammer和搜索引擎反作弊工程師的斗法從來(lái)就沒(méi)停止過(guò),。實(shí)際上,,只要是算法,就一定有spam方法,,不存在無(wú)懈可擊的排名算法,。下面看一下針對(duì)PageRank的spam。

Link Spam

回到文章開(kāi)頭的例子,,如果我想讓我的博客在搜索“張洋 博客”時(shí)排名靠前,,顯然在PageRank算法下靠Term Spam是無(wú)法實(shí)現(xiàn)的,。不過(guò)既然我明白了PageRank主要靠?jī)?nèi)鏈數(shù)計(jì)算頁(yè)面權(quán)重,那么我是不是可以考慮建立很多空架子網(wǎng)站,,讓這些網(wǎng)站都鏈接到我博客首頁(yè),,這樣是不是可以提高我博客首頁(yè)的PageRank?很不幸,,這種方法行不通,。再看下PageRank算法,一個(gè)頁(yè)面會(huì)將權(quán)重均勻散播給被鏈接網(wǎng)站,,所以除了內(nèi)鏈數(shù)外,,上游頁(yè)面的權(quán)重也很重要。而我那些空架子網(wǎng)站本身就沒(méi)啥權(quán)重,,所以來(lái)自它們的內(nèi)鏈并不能起到提高我博客首頁(yè)P(yáng)ageRank的作用,,這樣只是自?shī)首詷?lè)而已。

所以,,Spam PageRank的關(guān)鍵就在于想辦法增加一些高權(quán)重頁(yè)面的內(nèi)鏈,。下面具體看一下Link Spam怎么做。

首先明確將頁(yè)面分為幾個(gè)類型:

1,、目標(biāo)頁(yè)

目標(biāo)頁(yè)是spammer要提高rank的頁(yè)面,,這里就是我的博客首頁(yè)。

2,、支持頁(yè)

支持頁(yè)是spammer能完全控制的頁(yè)面,,例如spammer自己建立的站點(diǎn)中頁(yè)面,這里就是我上文所謂的空架子頁(yè)面,。

3,、可達(dá)頁(yè)

可達(dá)頁(yè)是spammer無(wú)法完全控制,但是可以有接口供spammer發(fā)布鏈接的頁(yè)面,,例如天涯社區(qū),、新浪博客等等這種用戶可發(fā)帖的社區(qū)或博客站。

4,、不可達(dá)頁(yè)

這是那些spammer完全無(wú)法發(fā)布鏈接的網(wǎng)站,,例如政府網(wǎng)站、百度首頁(yè)等等,。

作為一個(gè)spammer,,我能利用的資源就是支持頁(yè)和可達(dá)頁(yè),。上面說(shuō)過(guò),,單純通過(guò)支持頁(yè)是沒(méi)有辦法spam的,因此我要做的第一件事情就是盡量找一些rank較高的可達(dá)頁(yè)去加上對(duì)我博客首頁(yè)的鏈接,。例如我可以去天涯,、貓撲等地方回個(gè)這樣的貼:“樓主的帖子很不錯(cuò),!精彩內(nèi)容:http://”。我想大家一定在各大社區(qū)沒(méi)少見(jiàn)這種帖子,,這就是有人在做spam,。

然后,再通過(guò)大量的支持頁(yè)放大rank,,具體做法是讓每個(gè)支持頁(yè)和目標(biāo)頁(yè)互鏈,,且每個(gè)支持頁(yè)只有一條鏈接。

這樣一個(gè)結(jié)構(gòu)叫做Spam Farm,,其拓?fù)鋱D如下:

其中T是目標(biāo)頁(yè),,A是可達(dá)頁(yè),S是支持頁(yè),。下面計(jì)算一下link spam的效果,。

設(shè)T的總rank為y,則y由三部分組成:

1,、可達(dá)頁(yè)的rank貢獻(xiàn),,設(shè)為x。

2,、心靈轉(zhuǎn)移的貢獻(xiàn),,為β/n。其中n為全部網(wǎng)頁(yè)的數(shù)量,,β為轉(zhuǎn)移參數(shù),。

3、支持頁(yè)的貢獻(xiàn):

設(shè)有m個(gè)支持頁(yè),,因?yàn)槊總€(gè)支持頁(yè)只和T有鏈接,,所以可以算出每個(gè)支持頁(yè)的rank為:

(1?β)ym+βn

則支持頁(yè)貢獻(xiàn)的全部rank為:

m(1?β)((1?β)ym+βn)

因此可以得到:

y=m(1?β)((1?β)ym+βn)+x+βn

由于相對(duì)β,,n非常巨大,,所以可以認(rèn)為β/n近似于0。 簡(jiǎn)化后的方程為:

y=m(1?β)((1?β)ym)+x

解方程得:

y=x12β?β2

假設(shè)β為0.2,,則1/(2β-β^2) = 2.77則這個(gè)spam farm可以將x約放大2.7倍,。因此如果起到不錯(cuò)的spam效果,。

Link Spam反作弊

針對(duì)spammer的link spam行為,搜索引擎的反作弊工程師需要想辦法檢測(cè)這種行為,,一般來(lái)說(shuō)有兩類方法檢測(cè)link spam,。

網(wǎng)絡(luò)拓?fù)浞治?/h3>

一種方法是通過(guò)對(duì)網(wǎng)頁(yè)的圖拓?fù)浣Y(jié)構(gòu)分析找出可能存在的spam farm。但是隨著Web規(guī)模越來(lái)越大,,這種方法非常困難,,因?yàn)閳D的特定結(jié)構(gòu)查找是時(shí)間復(fù)雜度非常高的一個(gè)算法,不可能完全靠這種方法反作弊。

TrustRank

更可能的一種反作弊方法是叫做一種TrustRank的方法,。

說(shuō)起來(lái)TrustRank其實(shí)數(shù)學(xué)本質(zhì)上就是Topic-Sensitive Rank,,只不過(guò)這里定義了一個(gè)“可信網(wǎng)頁(yè)”的虛擬topic。所謂可信網(wǎng)頁(yè)就是上文說(shuō)到的不可達(dá)頁(yè),,或者說(shuō)沒(méi)法spam的頁(yè)面,。例如政府網(wǎng)站(被黑了的不算)、新浪,、網(wǎng)易門戶首頁(yè)等等,。一般是通過(guò)人力或者其它什么方式選擇出一個(gè)“可信網(wǎng)頁(yè)”集合,組成一個(gè)topic,,然后通過(guò)上文的Topic-Sensitive算法對(duì)這個(gè)topic進(jìn)行rank計(jì)算,,結(jié)果叫做TrustRank。

TrustRank的思想很直觀:如果一個(gè)頁(yè)面的普通rank遠(yuǎn)高于可信網(wǎng)頁(yè)的topic rank,,則很可能這個(gè)頁(yè)面被spam了,。

設(shè)一個(gè)頁(yè)面普通rank為P,TrustRank為T,,則定義網(wǎng)頁(yè)的Spam Mass為:(P – T)/P,。

Spam Mass越大,說(shuō)明此頁(yè)面為spam目標(biāo)頁(yè)的可能性越大,。

總結(jié)

這篇文章是我對(duì)一些資料的歸納匯總,,簡(jiǎn)單介紹了PageRank的背景、作用,、計(jì)算方法,、變種、Spam及反作弊等內(nèi)容,。為了突出重點(diǎn)我簡(jiǎn)化了搜索引擎的模型,,當(dāng)然在實(shí)際中搜索引擎遠(yuǎn)沒(méi)有這么簡(jiǎn)單,真實(shí)算法也一定非常復(fù)雜,。不過(guò)目前幾乎所有現(xiàn)代搜索引擎頁(yè)面權(quán)重的計(jì)算方法都基于PageRank及其變種,。因?yàn)槲覜](méi)做過(guò)搜索引擎相關(guān)的開(kāi)發(fā),因此本文內(nèi)容主要是基于現(xiàn)有文獻(xiàn)的客觀總結(jié),,稍加一點(diǎn)我的理解,。

文中的圖使用PGF/TikZ for Tex繪制:http://www./tikz/

參考文獻(xiàn)

[1] Anand Rajaraman, Jeffrey D. Ullman, Mining of Massive Datasets. 2010-2011

[2] S. Brin and L. Page, “Anatomy of a large-scale hypertextual web search engine,” Proc. 7th Intl. World-Wide-Web Conference, pp. 107–117, 1998.

[3] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Weiner, “Graph structure in the web,” Computer Networks 33:1–6, pp. 309–320, 2000.

[4] T.H. Haveliwala, “Topic-sensitive PageRank,” Proc. 11th Intl. World-Wide-Web Conference, pp. 517–526, 2002

[5] Z. Gy¨ongi, H. Garcia-Molina, and J. Pedersen, “Combating link spam with trustrank,” Proc. 30th Intl. Conf. on Very Large Databases, pp. 576–587, 2004.

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間,,所有內(nèi)容均由用戶發(fā)布,,不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購(gòu)買等信息,,謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請(qǐng)點(diǎn)擊一鍵舉報(bào),。
    轉(zhuǎn)藏 分享 獻(xiàn)花(0

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多