本文關(guān)鍵詞：Google搜索引擎的數(shù)學(xué)模型及其應(yīng)用，由筆耕文化傳播整理發(fā)布。

【原創(chuàng)】機(jī)器學(xué)習(xí)之PageRank算法應(yīng)用與C#實(shí)現(xiàn)(1)算法介紹

考慮到知識的復(fù)雜性，連續(xù)性，將本算法及應(yīng)用分為3篇文章，請關(guān)注，將在本月逐步發(fā)表。

1.機(jī)器學(xué)習(xí)之PageRank算法應(yīng)用與C#實(shí)現(xiàn)(1)算法介紹

2.機(jī)器學(xué)習(xí)之PageRank算法應(yīng)用與C#實(shí)現(xiàn)(2)球隊(duì)排名應(yīng)用與C#代碼

3.機(jī)器學(xué)習(xí)之PageRank算法應(yīng)用與C#實(shí)現(xiàn)(3)球隊(duì)實(shí)力排名應(yīng)用與C#代碼 

　　Pagerank是Google排名運(yùn)算法則（排名公式）的一部分，是Google用于用來標(biāo)識網(wǎng)頁的等級/重要性的一種方法，是Google用來衡量一個(gè)網(wǎng)站的好壞的唯一標(biāo)準(zhǔn)。在揉合了諸如Title標(biāo)識和Keywords標(biāo)識等所有其它因素之后，Google通過PageRank來調(diào)整結(jié)果，使那些更具“等級/重要性”的網(wǎng)頁在搜索結(jié)果中令網(wǎng)站排名獲得提升，從而提高搜索結(jié)果的相關(guān)性和質(zhì)量。鑒于Google的巨大成功和PageRank的巨大作用，已經(jīng)入學(xué)了機(jī)器學(xué)習(xí)的十大算法之一。今天就帶大家走近PageRank，簡述其原理以及應(yīng)用的C#實(shí)現(xiàn)。由于個(gè)人是專業(yè)做足球賽事預(yù)測，所以應(yīng)用就拿足球勝平負(fù)的預(yù)測作為例子了。原理和過程都差不多，看大家如何分析問題了。

　　鑒于PageRank算法的資料很多，也很成熟，所以相關(guān)的介紹和原理部分就直接引用了相關(guān)著作上面的話，在應(yīng)用部分是個(gè)人的代碼和思路，引用原始出處已經(jīng)標(biāo)明。

本文： 

　　PageRank，簡稱為PR值，又稱網(wǎng)頁級別、Google左側(cè)排名或佩奇排名。Pagerank取自Google的創(chuàng)始人LarryPage，它是Google排名運(yùn)算法則的一部分，Pagerank是Google對網(wǎng)頁重要性的評估，是Google用來衡量一個(gè)網(wǎng)站的好壞的唯一標(biāo)準(zhǔn)。Google通過PageRank來調(diào)整結(jié)果，使那些更具“重要性”的網(wǎng)頁在搜索結(jié)果中另網(wǎng)站排名獲得提升，從而提高搜索結(jié)果的相關(guān)性和質(zhì)量。PR值的級別從1到10級，10級為滿分。PR值越高說明該網(wǎng)頁越受歡迎。

　　PageRank這個(gè)概念引自學(xué)術(shù)中一篇論文的被引述的頻度——即被別人引述的次數(shù)越多，一般判斷這篇論文的權(quán)威性就越高。Google有一套自動(dòng)化方法來計(jì)算這些投票。Google的PageRank分值從0到10；PageRank為10表示最佳，但非常少見，類似里氏震級（Richterscale），PageRank級別也不是線性的，而是按照一種指數(shù)刻度。這是一種奇特的數(shù)學(xué)術(shù)語，意思是PageRank4不是比PageRank3好一級——而可能會(huì)好6到7倍。因此，一個(gè)PageRank5的網(wǎng)頁和PageRank8的網(wǎng)頁之間的差距會(huì)比你可能認(rèn)為的要大的多。PageRank較高的頁面的排名往往要比PageRank較低的頁面高，而這導(dǎo)致了人們對鏈接的著魔。在整個(gè)SEO社區(qū)，人們忙于爭奪、交換甚至銷售鏈接，它是過去幾年來人們關(guān)注的焦點(diǎn)，以至于Google修改了他的系統(tǒng)，并開始放棄某些類型的鏈接。比如，被人們廣泛接受的一條規(guī)定，來自缺乏內(nèi)容的“linkfarm”（鏈接工廠）網(wǎng)站的鏈接將不會(huì)提供頁面的PageRank，從PageRank較高的頁面得到鏈接但是內(nèi)容不相關(guān)（比如說某個(gè)流行的漫畫書網(wǎng)站鏈接到一個(gè)叉車規(guī)范頁面），也不會(huì)提供頁面的PageRank。Google選擇降低了PageRank對更新頻率，以便不鼓勵(lì)人們不斷的對其進(jìn)行監(jiān)測。

　　PageRank算法是Google搜索引擎對檢索結(jié)果的一種排序算法．它的基本思想主要是來自傳統(tǒng)文獻(xiàn)計(jì)量學(xué)中的文獻(xiàn)引文分析，即一篇文獻(xiàn)的質(zhì)量和重要性可以通過其它文獻(xiàn)對其引用的數(shù)量和引文質(zhì)量來衡量，也就是說，一篇文獻(xiàn)被其它文獻(xiàn)引用越多，并且引用它的文獻(xiàn)的質(zhì)量越高，則該文獻(xiàn)本身就越重要．Google在給出頁面排序時(shí)也有兩條標(biāo)準(zhǔn)：一是看有多少超級鏈接指向它；二是要看超級鏈接指向它的那個(gè)頁面重要不重要．這兩條直觀的想法就是PageRank算法的數(shù)學(xué)基礎(chǔ)，也是Google搜索引擎最基本的工作原理．PageRank算法利用了互聯(lián)網(wǎng)獨(dú)特的超鏈接結(jié)構(gòu)．在龐大的超鏈接資源中，Google提取出上億個(gè)超級鏈接頁面進(jìn)行分析，制作出一個(gè)巨大的網(wǎng)絡(luò)地圖．具體的講，就是把所有的網(wǎng)頁看作圖里面相應(yīng)的頂點(diǎn)，如果網(wǎng)頁A有—個(gè)指向網(wǎng)頁B的鏈接，則認(rèn)為一條從頂點(diǎn)A到頂點(diǎn)B的有向邊．這樣就可以利用圖論來研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)．PageRank算法正是利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來判斷網(wǎng)頁的重要性．具體來說，假如網(wǎng)頁A有—個(gè)指向網(wǎng)頁B的超鏈接，Google就認(rèn)為網(wǎng)頁A投了網(wǎng)頁B一票，說明網(wǎng)頁A認(rèn)為網(wǎng)頁B有鏈接價(jià)值，因而B可能是—個(gè)重要的網(wǎng)頁．Google根據(jù)指向網(wǎng)頁B的超鏈接數(shù)及其重要性來判斷頁面B的重要性，并賦予相應(yīng)的頁面等級值(PageRank)．網(wǎng)頁A的頁面等級值被平均分畫己給網(wǎng)頁A所鏈接指向的網(wǎng)頁，從而當(dāng)網(wǎng)頁A的頁面等級值比較高時(shí)，則網(wǎng)頁B可從網(wǎng)頁A到它的超鏈接分得一定的重要性．根據(jù)這樣的分析，，得到了高評價(jià)的重要頁面會(huì)被賦予較高的網(wǎng)頁等級，在檢索結(jié)果內(nèi)的排名也會(huì)較高．頁面等級值(PageRank)是Google表示網(wǎng)頁重要性的綜合性指標(biāo)，而且不會(huì)受到不同搜索引擎的影響．當(dāng)然，重要性高的頁面如果和檢索關(guān)鍵詞無關(guān)同樣也沒有任何意義．為此，Google使用了完善的超文本匹配分析技術(shù)，使得能夠檢索出重要而且正確的網(wǎng)頁．

[1].上述引用“趙國，宋建成.Google搜索引擎的數(shù)學(xué)模型及其應(yīng)用,西南民族大學(xué)學(xué)報(bào)自然科學(xué)版.2010,vol(36),3”

　　這一節(jié)我們還是采用趙國那篇論文的簡單例子，介紹PageRank的簡單過程以及對應(yīng)的隨機(jī)沖浪模型，可以讓你加深對算法的理解，同時(shí)這也是編寫代碼的重要依據(jù)。

PageRank算法的具體實(shí)現(xiàn)可以利用網(wǎng)頁所對應(yīng)的圖的鄰接矩陣來表達(dá)超鏈接關(guān)系。因此要先寫出所對應(yīng)圖的鄰接矩陣 A ，為了能將網(wǎng)頁的頁面等級值平均分配給該網(wǎng)頁所鏈接指向的網(wǎng)頁，需要對各個(gè)行向量進(jìn)行歸一化處理，得到矩陣A1。PageRank算法的矩陣是將歸一化矩陣A1轉(zhuǎn)置所得矩陣W，稱之為 轉(zhuǎn)移概率矩陣(是不是和馬爾可夫鏈有點(diǎn)像，的確是與馬爾可夫鏈過程有著密切的關(guān)系)，其特征是各個(gè)列列向量之和為全概率1，各個(gè)行矢量表示狀態(tài)之間的轉(zhuǎn)移概率，轉(zhuǎn)置的原因是PageRank算法重視的某個(gè)頁面被多少個(gè)頁面鏈接，而不是鏈接到多少個(gè)頁面。各個(gè)網(wǎng)頁的頁面等級制就是求這個(gè)轉(zhuǎn)義概率矩陣W的最大特征值所屬的特征向量。因此可以看出，PageRank的應(yīng)用也主要是對某些過程對象進(jìn)行重要等級排名。

　　例如，先假設(shè)有下面的圖鄰接矩陣：

為了能將網(wǎng)頁的頁面等級值平均分配給該網(wǎng)頁所鏈接指向的網(wǎng)頁，對各個(gè)行向量進(jìn)行歸一化處理，得：

將歸一化所得的矩陣轉(zhuǎn)置，所得到的轉(zhuǎn)移概率矩陣W：

 根據(jù)上述公式和轉(zhuǎn)移概率矩陣，可以求得其最大特征值為：

對應(yīng)的非負(fù)特征向量為：

因此可以確定網(wǎng)頁的排序?yàn)镃,A,B，而A，C的排序并沒有很顯著的差別，但是由于指向C的鏈接多一些，所以可以考慮排在前面。至于其中的特征值計(jì)算和非負(fù)特征向量，是一個(gè)比較簡單的線性代數(shù)問題，如果不懂的可以去查下資料，本博客也有相應(yīng)的Math.NET數(shù)學(xué)組件可以借鑒，可以很容易的解決這些基礎(chǔ)的問題，鏈接看菜單導(dǎo)航。

　　隨機(jī)沖浪模型(Random Surfer Model)是為了更加的符合實(shí)際情況而對上述PageRank基本模型進(jìn)行的改進(jìn)。PageRank算法原理中假設(shè)所有的網(wǎng)頁形成一個(gè)閉合的鏈接圖，除了這些文檔以外沒有其他任何鏈接的出入，并且每個(gè)網(wǎng)頁能從其他網(wǎng)頁通過超鏈接達(dá)到．但是在現(xiàn)實(shí)的網(wǎng)絡(luò)中，并不完全是這樣的情況．當(dāng)一個(gè)頁面沒有出鏈的時(shí)候，它的PageRank值就不能被分配給其它的頁面。同樣道理，只有出鏈接而沒有入鏈接的頁面也是存在的。但PageRank并不考慮這樣的頁面．在現(xiàn)實(shí)中的頁面，無論怎樣順著鏈接前進(jìn)，僅僅順著鏈接是絕對不能進(jìn)入的頁面群總歸是存在的。所以為了解決這個(gè)問題，提出了用戶的隨機(jī)沖浪模型：用戶雖然在大多數(shù)情況下都順著當(dāng)前頁面中的鏈接前進(jìn)，但也有少數(shù)情況會(huì)突然重新打開瀏覽器隨機(jī)進(jìn)入到完全無關(guān)的頁面。這樣就可以用公式表示相應(yīng)的概率矩陣:

還是考慮第3節(jié)中的問題，我們?nèi)=0.5，可以計(jì)算相應(yīng)的概率轉(zhuǎn)移矩陣為：

計(jì)算得到其最大特征值為1，相應(yīng)的特征向量為：

所以排序的結(jié)果C，A，B合理一些，也更加符合實(shí)際情況。

接下來我們將通過上述論文中的一個(gè)例子來介紹PageRank的實(shí)際應(yīng)用與C#實(shí)現(xiàn)過程，請關(guān)注博客。

下一篇文章地址：機(jī)器學(xué)習(xí)之PageRank算法應(yīng)用與C#實(shí)現(xiàn)(2)在足球隊(duì)排名中的應(yīng)用

posted @

  本文關(guān)鍵詞：Google搜索引擎的數(shù)學(xué)模型及其應(yīng)用，由筆耕文化傳播整理發(fā)布。