谷歌怎樣給搜索結(jié)果排序？

《谷歌怎樣給搜索結(jié)果排序？》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、谷歌怎樣給搜索結(jié)果排序？拉里?佩奇(LarryPage)和謝爾蓋?布林(SergeyBrin)正是依靠先進(jìn)的算法發(fā)家并創(chuàng)立谷歌google的。9月27日谷歌推出新款doodle，慶祝自己13歲生日。在這個(gè)世界上，谷歌幾乎無(wú)人不曉了。但鮮為人知的是，在13年前，拉里?佩奇(LarryPage)和謝爾蓋?布林(SergeyBrin)正是依靠先進(jìn)的算法發(fā)家并創(chuàng)立谷歌的。在這個(gè)世界上最自由和創(chuàng)新公司的生日里，來(lái)聽(tīng)聽(tīng)死理性派講述它當(dāng)年的數(shù)學(xué)故事吧。網(wǎng)頁(yè)排名和谷歌算法的誕生一個(gè)正常的搜索引擎，其核心功能自然是網(wǎng)頁(yè)搜索。那搜索結(jié)

2、果應(yīng)該怎樣排序才最好呢？實(shí)際上，在谷歌主導(dǎo)互聯(lián)網(wǎng)搜索之前，人們?yōu)榇藗改X筋。當(dāng)時(shí)人們認(rèn)為，通過(guò)判斷能夠得知哪個(gè)網(wǎng)頁(yè)更重要，對(duì)搜索引擎的發(fā)展十分有幫助——很顯然，搜索引擎應(yīng)該把重要的網(wǎng)頁(yè)放到搜索結(jié)果中比較靠前的地方。這個(gè)問(wèn)題看起來(lái)很容易，但是解決的方法卻沒(méi)有想象的那么簡(jiǎn)單。在谷歌誕生之前那段時(shí)間，流行的網(wǎng)頁(yè)排名算法都很類似，它們都使用了一個(gè)非常簡(jiǎn)單的思想：越是重要的網(wǎng)頁(yè)，訪問(wèn)量就會(huì)越大。許多大公司就通過(guò)統(tǒng)計(jì)網(wǎng)頁(yè)的訪問(wèn)量來(lái)進(jìn)行網(wǎng)頁(yè)排名。但是這種排名算法有兩個(gè)很顯著的問(wèn)題：一是因?yàn)橹荒軌虺闃咏y(tǒng)計(jì)，所以統(tǒng)計(jì)數(shù)據(jù)不一定準(zhǔn)確，

3、而且訪問(wèn)量的波動(dòng)會(huì)比較大，想要得到準(zhǔn)確的統(tǒng)計(jì)需要大量的時(shí)間和人力，還只能維持很短的有效時(shí)間；二是訪問(wèn)量并不一定能體現(xiàn)網(wǎng)頁(yè)的“重要程度”——可能一些比較早接觸互聯(lián)網(wǎng)的網(wǎng)民還記得，那時(shí)有很多人推出了專門“刷訪問(wèn)量”的服務(wù)。有沒(méi)有更好的方法，不統(tǒng)計(jì)訪問(wèn)量就能夠?yàn)榫W(wǎng)頁(yè)的重要度排序呢？就是在這種情況下,1996年初，谷歌公司的創(chuàng)始人，當(dāng)時(shí)還是美國(guó)斯坦福大學(xué)研究生的佩奇和布林開(kāi)始了對(duì)網(wǎng)頁(yè)排序問(wèn)題的研究。在1999年，一篇以佩奇為第一作者的論文發(fā)表了，論文中介紹了一種叫做PageRank的算法，這種算法的主要思想是：越“重要”的

4、網(wǎng)頁(yè)，頁(yè)面上的鏈接質(zhì)量也越高，同時(shí)越容易被其它“重要”的網(wǎng)頁(yè)鏈接。于是，算法完全利用網(wǎng)頁(yè)之間互相鏈接的關(guān)系來(lái)計(jì)算網(wǎng)頁(yè)的重要程度，將網(wǎng)頁(yè)排序徹底變成一個(gè)數(shù)學(xué)問(wèn)題，終于擺脫了訪問(wèn)量統(tǒng)計(jì)的框框。三個(gè)孩子和豌豆游戲在詳細(xì)講述這個(gè)算法之前，不妨讓我們用一個(gè)游戲，先來(lái)簡(jiǎn)單模擬一下PageRank算法的運(yùn)行過(guò)程，以便讀者更好地理解。三兄弟分30顆豌豆。起初每人10顆，他們每次都要把手里的豌豆全部平均分給自己喜歡的人。下圖表示了三兄弟各自擁有的初始豌豆數(shù)量，以及相互喜歡的關(guān)系（箭頭方向表示喜歡，例如老二喜歡老大，老大喜歡老二和老三

5、）。第一次分配后，我們會(huì)得到結(jié)果如下：就這樣，讓游戲一直進(jìn)行下去。直到他們手中的豌豆數(shù)不再變化為止。那么這個(gè)游戲到底是否可以結(jié)束呢，如果可以，最終的結(jié)果又是什么樣的？在此我們用電腦模擬了這個(gè)過(guò)程，得出的結(jié)果是：老大和老二的盤子里各有12顆豌豆，而老三的盤子里有6顆豌豆。這時(shí)候無(wú)論游戲怎么進(jìn)行下去，盤子里的豌豆數(shù)量都不會(huì)再變化。看到這里，讀者可能會(huì)問(wèn)：這個(gè)游戲和網(wǎng)頁(yè)排序有什么關(guān)系？實(shí)際上，PageRank會(huì)給每個(gè)網(wǎng)頁(yè)一個(gè)數(shù)值，這個(gè)數(shù)值越高，就說(shuō)明這個(gè)網(wǎng)頁(yè)越“重要”。而剛剛的游戲中，如果把豌豆的數(shù)量看作這個(gè)數(shù)值（可以不

6、是整數(shù)），把孩子們看作網(wǎng)頁(yè)，那么游戲的過(guò)程就是PageRank的算法，而游戲結(jié)束時(shí)豌豆的分配，就是網(wǎng)頁(yè)的PageRank值。PageRank的數(shù)學(xué)模型不同于之前的訪問(wèn)量統(tǒng)計(jì)，PageRank求解了這樣一個(gè)問(wèn)題：一個(gè)人在網(wǎng)絡(luò)上瀏覽網(wǎng)頁(yè)，每看過(guò)一個(gè)網(wǎng)頁(yè)之后就會(huì)隨機(jī)點(diǎn)擊網(wǎng)頁(yè)上的鏈接訪問(wèn)新的網(wǎng)頁(yè)。如果當(dāng)前這個(gè)人瀏覽的網(wǎng)頁(yè)x已經(jīng)確定，那么網(wǎng)頁(yè)x上每個(gè)鏈接被點(diǎn)擊的概率也是確定的，可以用向量Nx表示。在這種條件下，這個(gè)人點(diǎn)擊了無(wú)限多次鏈接后，恰好停留在每個(gè)網(wǎng)頁(yè)上的概率分別是多少？在這個(gè)模型中，我們用向量Ri來(lái)表示點(diǎn)擊了i次鏈接之

7、后可能停留在每個(gè)網(wǎng)頁(yè)上的概率（R0則為一開(kāi)始就打開(kāi)了每個(gè)網(wǎng)頁(yè)的概率，后面我們將證明R0的取值對(duì)最終結(jié)果沒(méi)有影響）。很顯然Ri的L1范式為1，這也是PageRank算法本身的要求。仍以上面的游戲?yàn)槔?，整個(gè)瀏覽過(guò)程的一開(kāi)始，我們有：其中，A表示每一次點(diǎn)擊鏈接概率的矩陣。A的第i列第j行Ai,j的含義是，如果當(dāng)前訪問(wèn)的網(wǎng)頁(yè)是網(wǎng)頁(yè)i，那么下一次點(diǎn)擊鏈接跳轉(zhuǎn)到網(wǎng)頁(yè)j的概率為Ai,j。這樣設(shè)計(jì)矩陣A的好處是，通過(guò)矩陣A和向量Rn-1相乘，即可得出點(diǎn)擊一次鏈接后每個(gè)網(wǎng)頁(yè)可能的停留概率向量Rn。例如，令R1=AR0，可以得到點(diǎn)擊一

8、次鏈接后停留在每個(gè)網(wǎng)頁(yè)的概率：之后一直迭代下去，有：對(duì)于上面的例子，迭代結(jié)果如下圖：可以看到，每個(gè)網(wǎng)頁(yè)停留的概率在振蕩之后趨于穩(wěn)定。在這種穩(wěn)定狀態(tài)下，我們可以知道，無(wú)論如何迭代，都有Rn=Rn-1。這樣我們就獲得了一個(gè)方程：而整個(gè)迭代的過(guò)程，就是在尋求方程R=AR的解。而無(wú)論R0是多少，迭代無(wú)限多次之后，一定會(huì)取得令R=AR成立的R值。整個(gè)求解R的過(guò)程，就如