由于公司架構調整和業(yè)務方向的轉變，我所在的項目組即將接手一個機器學習和數(shù)據(jù)挖掘的項目，為了后續(xù)更好地開展工作，也為了能提高自己的專業(yè)技能，我決定開始學習機器和數(shù)據(jù)挖掘方面的知識。
那么，問題就來了：到底應該從哪里開始學起呢？最開始我也買了一些機器學習相關的入門書籍，跟著聽一些網(wǎng)絡課程，但是我發(fā)現(xiàn)所有的課程都特別偏重理論，雖然機器學習、數(shù)據(jù)挖掘需要很強的理論基礎才能做好，但是我個人更喜歡理論聯(lián)系實際的學習方式，比如可以在了解某種基本原理的基礎上，立刻用代碼來實現(xiàn)它。
無意間從同事口中得知機器學習與數(shù)據(jù)挖掘的十大經(jīng)典算法，我決定就從十大經(jīng)典算法開始學習。
下面是我的學習路線：逐個掌握每種經(jīng)典算法的算法思想、數(shù)學模型及Python代碼實現(xiàn)，爭取各個擊破并融匯貫通。
好了，廢話不多說了，我們先看第一種經(jīng)典算法：PageRank算法。
一、PageRank算法的簡介
PageRank算法即網(wǎng)頁分級排名算法，它的提出者是谷歌的創(chuàng)始人之一拉里·佩奇（Larry Page），所以算法的名字就以Page命名。拉里·佩奇提出該算法時還是一名斯坦福大學的學生，（真是自古英雄出少年啊?。┎⑶以撍惴ㄔ?001年9月獲得美國國家專利。
PageRank算法是google算法的重要內容之一，可以說它就是Google算法的降龍十八掌和倚天屠龍劍?。?/p>
二、PageRank算法的核心思想
PageRank根據(jù)網(wǎng)站的外部鏈接和內部鏈接的數(shù)量和質量，衡量網(wǎng)站的價值。PageRank隱含的思想就是：每個到頁面的鏈接都是對該頁面的一次投票， 被鏈接的越多，就意味著被其他網(wǎng)站投票越多。一個網(wǎng)頁所獲得"投票"越多，說明這個網(wǎng)頁越重要，它的被訪問的概率越大，自然分級排名就越高，那么搜索結果它就越靠前。這就好比是一篇學術論文，論文被引用的次數(shù)越多，論文的影響因子越高，自然論文就越權威啦！
PageRank的核心思想歸納起來就兩條：
1.如果一個網(wǎng)頁被很多其他網(wǎng)頁鏈接到的話說明這個網(wǎng)頁比較重要，也就是PageRank值會相對較高。
2.如果一個PageRank值很高的網(wǎng)頁鏈接到一個其他的網(wǎng)頁，那么被鏈接到的網(wǎng)頁的PageRank值會相應地因此而提高。
三、PageRank算法的數(shù)學模型
1、相關概念
出鏈：網(wǎng)頁A中附加了網(wǎng)頁B的鏈接，用戶瀏覽A時可以通過點擊該鏈接進入網(wǎng)頁B，此時我們稱A出鏈B。
入鏈：上面通過點擊網(wǎng)頁A中B-Link進入B，表示由A入鏈B。如果用戶自己在瀏覽器輸入欄輸入網(wǎng)頁B的URL，然后進入B，表示用戶通過輸入URL入鏈B。
無出鏈：如果一個網(wǎng)頁A中沒有附加任何的URL，則稱A無出鏈。
只對自己出鏈：如果一個網(wǎng)頁A中沒有附加任何其他頁面的URL，只有附加自己的URL，則稱A只對自己出鏈。
PR值：就是指一個網(wǎng)站被訪問的概率，PR值越高，被訪問的概率越高，自然排名就高。
2、簡單數(shù)學模型（不帶a的數(shù)學模型）
首先，我們對網(wǎng)絡上的所有網(wǎng)頁做一個抽象，每個網(wǎng)頁代表一個節(jié)點，如果從網(wǎng)頁A中附加了網(wǎng)頁B的鏈接，則表示從節(jié)點A指點節(jié)點B的有向邊。那么整個WEB就被抽象成一張有向圖?，F(xiàn)在我們假設世界上只有四個網(wǎng)頁，它們之間關系如下圖：
圖 1
之前我們說過PageRank的思想就是，誰被引用的越多，誰的PR值越高。那么我們假設當用戶停留在某個頁面上時，他跳轉到頁面上任意一個鏈接的概率相同。
對任意一個網(wǎng)頁我們用I(p)描述其重要性，稱之為網(wǎng)頁排序值（就是PR值）。假定網(wǎng)頁Pj有Lj個鏈接，其中一個鏈接指向網(wǎng)頁Pi,那么Pj將其重要性的1/Lj分給Pi,即Pi的網(wǎng)頁重要性就是所有指向這個網(wǎng)頁的其他網(wǎng)頁所貢獻的重要性之和。公式表示如下：
公式中，Bi表示所有鏈接到Pi的網(wǎng)頁集合。
為了方便數(shù)學分析，我們定義一個超鏈矩陣M[Mij]：
其中第i行j列的值Mij表示用戶從頁面j轉到頁面i的概率。
按照這個定義，圖1的超鏈矩陣為
設初始時每個頁面的rank值為1/N，這里就是1/4。按A—D順序得到向量v：v=[1/4,1/4,1/4,1/4]
此時如果做矩陣乘法，使M*v就得到一個新的rank陣v'：M第一行分別是A、B、C和D轉移到頁面A的概率，而v的第一列分別是A、B、C和D當前的rank，因此用M的第一行乘以v的第一列，所得結果就是頁面A最新rank的合理估計，故M*v的結果v'就分別代表A、B、C、D新rank值。
然后用M再乘以這個新的rank向量v'，又會產(chǎn)生一個rank向量。迭代這個過程，可以證明v最終會收斂，即v≈Mv，此時計算停止，最終得到的v'就是rankpage的排序結果：
V'=M*V----------(1)
3、復雜數(shù)學模型（帶a的數(shù)學模型）
但是我們也注意到，要想上述迭代結果最終收斂，必須滿足一個條件：圖是強連通的，即從任意網(wǎng)頁可以到達其他任意網(wǎng)頁。假設我們把上面圖中C到D的鏈接丟掉，C變成了一個終止點。再進行迭代，那么迭代的最終結果是v'=[0,0,0,0]，顯然算法失效了。除了終止點問題外，還有一個陷阱問題，即將圖1中D到C的鏈接刪除后，再加一條C指向C自身的鏈接。那么按上述迭代過程，最終v'=[0,0,1,0]，此時算法也是失效的。
圖2 終止點問題
圖3 陷阱問題
為了解決終止點問題和陷阱問題，我們需要對算法進行改進：假設用戶在選擇下一個跳轉的頁面時，選擇當前頁及當前頁上的鏈接的概率為a，選擇其他頁面的概率為（1-a）,選擇其他頁面中每個頁面的概率都相同為1/n，則計算PR值的公式演變?yōu)椋?/p>
v′=αMv+(1?α)(1/n)-----(2)
四、PageRank算法的Python實現(xiàn)
下面我們以圖3為例，分別用代碼實現(xiàn)公式（1）和公式（2）的排序結果：
import numpy as np
M = [[0,1/2,0,1/2], [1/3,0,0,1/2], [1/3,1/2,1,0],[1/3,0,0,0]
U = [1/4,1/4,1/4,1/4]
U0 = np.array(U)
U_past_none_alpha = []
while True:
U = np.dot(M,U)
if str(U) == str(U_past_none_alpha):
Break
U_past_none_alpha = U
print('公式1的結果:',U)
U_past_has_alpha = []
while True:
U = 0.8*(np.dot(M,U))+0.2*U0
if str(U) == str(U_past_has_alpha):
Break
U_past_has_alpha = U
print('公式2的結果:',U)
輸出結果如下：
C:Users1009PycharmProjects20190329venvIncludeIncludeScriptsPython.exe C:/Users/1009/PycharmProjects/20190329/pagerank.py
公式1的結果：[0. 0. 1. 0.]
公式2的結果：[0.13172043 0.11917563 0.6639785 0.08512545]
Process finished with exit code 0
顯然，公式（2）的結果更加科學準確！
五、后記：
PageRank算法就介紹到這里了，我的感覺就是按公式編碼實現(xiàn)其實并不難，難的在于公式背后的數(shù)學邏輯思維。通過和做算法開發(fā)的同事交流，我才知道原來算法最最重要的就是思維，沒有思維的算法就如同沒有靈魂的軀體一樣，完全不能適應復雜的現(xiàn)實場景的需求。謹以此文為開端，開始我的算法之旅，希望與廣大測試同行一起進步！
