數(shù)據(jù)挖掘算法

1、分類Classification:分類是指將目標對象按照不同的標記進行分組，所有的標記都是已知的，這些對象往往都具有不同的特點。也就是說對于一個 classifier ，通常需要你告訴它“這個東西被分為某某類”這樣一些例子。理想情況下，一個 classifier 會從它得到的訓練集中進行“學習”，從而具備對未知數(shù)據(jù)進行分類預測的能力，這種提供訓練數(shù)據(jù)的過程通常叫做 supervised learning (監(jiān)督學習)。應用場景：銀行貸款安全和風險、信用卡持卡用戶進行分類KNN算法：K最鄰近分類算法（K-Nearest Neighbor），最簡單的機器學習算法之一。思路是：如

2、果一個樣本在特征空間中的k個最相似的樣本中的大多數(shù)屬于某個類，則該樣本也屬于某個類別。如上圖所示，綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由于藍色四方形比例為3/5，因此綠色圓被賦予藍色四方形類。決策樹分類算法ID3：ID3算法是由Quinlan首先提出的。該算法是以信息論為基礎，以信息熵和信息增益度為衡量標準，從而實現(xiàn)對數(shù)據(jù)的歸納分類。具體流程如下：輸入：樣本集合S,屬性集合A輸出：ID3決策樹若所有種類的屬性都處理完畢，返回：否則執(zhí)行2計算出信息增益最大屬性a，把該屬性作為一個節(jié)點，如果僅

3、憑屬性a就可以對樣本進行分類，則返回；否則執(zhí)行3。對屬性a的每個可能的取值v，執(zhí)行下一操作：將所有屬性a的值是v的樣本作為S的一個子集Sv；生產(chǎn)新的屬性集合AT=A-a以樣本集合Sv和屬性集合AT為輸入，遞歸執(zhí)行id3算法。分類系統(tǒng)的信息熵和信息增益：對分類系統(tǒng)來說，類別C是變量，可能的取值是C1，C2，C3.Cn，而每個類別出現(xiàn)的概率為P(C1),P(C2),P(C3).P(Cn)，N就是系統(tǒng)的類別，因此分類系統(tǒng)的熵代表包含系統(tǒng)所有特征屬性時系統(tǒng)的信息量（熵），就可以表示為：HC=-i=1nP(Ci)×log2P(Ci) ; P(Ci)即類別Ci出現(xiàn)的概率對分類系統(tǒng)來說，一個特征屬

4、性，系統(tǒng)有它和沒它時信息量將發(fā)生變化，而前后信息量的差值就是這個特征給系統(tǒng)帶來的信息量，即信息增益。系統(tǒng)包含特征屬性時的信息量有了，那么就要求系統(tǒng)不包含該特征屬性時的信息量，這個問題等價于系統(tǒng)包含了特征屬性X，但特征屬性X已經(jīng)固定不能變化時的信息量，此時的信息量即條件熵需要用特征屬性X每個可能的值出現(xiàn)的概率來表示：HCX=P1HCX=x1+P2HCX=x2+PnHCX=xn=i=1nPiH(C|X=Xi)具體到分類系統(tǒng)，分類系統(tǒng)的特征屬性T的固定值t只可能取兩個值（即t出現(xiàn)或t不出現(xiàn)），例如濕度這個特征屬性的固定值（高）只可能取兩個值，即高要么出現(xiàn)，要么不出現(xiàn)。HCT=PtHCt+PtHCt=

5、-Pti=1nP(Ci|t)×log2P(Ci|t)-Pti=1nP(Ci|t)×log2P(Ci|t)因此特征T給系統(tǒng)帶來的信息增益就可以寫成系統(tǒng)原本的熵與固定特征T后的條件熵之差：IG(C)=H(C)-H(C|T)應用舉例：使用ID3分類算法預測未知樣本的類標號。給定球隊球類比賽結(jié)果的訓練樣本集見下表。根據(jù)天氣（Outlook），溫度（Temperature），濕度（Humidity），風強度（Windy）來判斷該球隊比賽結(jié)果是否會贏。類標號屬性比賽結(jié)果具有兩個不同值Win, Lose。設C1對應于類 Result=“Win”,而C2 對應于類Result =“Lose

6、”。使用ID3分類算法來預測樣本為Outlook=Sunny, Temperature=Hot, Humidity=High, Wind=Strong的情況下，比賽的輸贏結(jié)果。首先，類別是（輸贏結(jié)果）。取值yes的記錄有9個，取值為no的記錄有5個，那么P(C1)=9/14，P(C2)=5/14，那么計算分類系統(tǒng)的熵:Entropy(S)=-(9/14)*log2(9/14) -(5/14)*log2(5/14);然后分別計算以各個屬性作為根節(jié)點的信息增益Outlook的信息增益：Entropy(Sunny)=-(2/5)*log2(2/5)-(3/5)*log2(3/5)=0.971Entr

7、opy(Rain)=-(2/5)*log2(2/5)-(3/5)*log2(3/5) =0.971Entropy(Overcast)=-(4/4)*log2(4/4)=0Gain(Outlook)=Entropy(S)-(5/14)*Entropy(Sunny)-(5/14)*Entropy(Rain)- (4/14)* Entropy(Overcast)=0.247Temperature的信息增益：Entropy(Hot)=-(2/4)*log2(2/4)-(2/4)*log2(2/4)=1Entropy(Mild)=-(4/6)*log2(4/6)-(2/6)*log2(2/6)=0.91

8、8Entropy(Cool)=-(3/4)*log2(3/4)-(1/4)*log2(1/4)=0.811Gain(Temperature)= Entropy(S)-(4/14)*Entropy(Hot)-(6/14)* Entropy(Mild) -(4/14)* Entropy(Cool)=0.247Humidity的信息增益： Entropy(High)=-(3/7)*log2(3/7)-(4/7)*log2(4/7)=0.985Entropy(Normal)=-(6/7)*log2(4/6)-(6/7)*log2(1/7)=0.592Gain(Humidity)= Entropy(S)

9、-(7/14)*Entropy(High)-(7/14)* Entropy(Normal) =0.151Wind的信息增益：Entropy(Strong)=-(3/6)*log2(3/6)-(3/6)*log2(3/6)=1Entropy(Weak)=-(6/8)*log2(6/8)-(2/8)*log2(2/8)=0.811Gain(Wind)= Entropy(S)-(6/14)*Entropy(Strong)-(8/14)* Entropy(Weak) =0.048這樣我們就得到以上4個屬性相應的信息增益值，最后安裝信息增益值最大的原則選擇outlook為根節(jié)點。子節(jié)點也重復以上的步驟。

10、就可以建立下以下這可決策樹：OutlookHumidityWindWinWinWinLoseWinSunnyOvercastRainHighNormalStrong掃描所有的交易記錄對每個候選計數(shù)Weak因此，將樣本X 指派給類C1：Result =“Win”。即在Outlook = Sunny,Temperature = Hot, Humidity = High, Wind = Strong的情況下這場比賽會贏。 樸素貝葉斯分類算法： 樸素貝葉斯分類基于貝葉斯定理,假設一個屬性值對給定類的影響獨立于其他屬性的值。設X是類標號未知的數(shù)據(jù)樣本。設H為某種假定，如，數(shù)據(jù)樣本X屬于某特定的類C。因此

11、我們希望確定P(H|X)，即給定觀測數(shù)據(jù)樣本X,假定H成立的概率（后驗概率）。貝葉斯定理（公式）：PHX=PXHP(H)P(X)樸素貝葉斯分類的工作過程如下： 1、用n 維特征向量X=x1, x2, xn表示每個數(shù)據(jù)樣本，用以描述對該樣本的n 個屬性A1, A2, , An 的度量。2、假定數(shù)據(jù)樣本可以分為m 個類C1, C2, , Cm。給定一個未知類標號的數(shù)據(jù)樣本X，樸素貝葉斯分類將其分類到類Ci ，當且僅當P(Ci|X) > P(Cj|X) 1jm，ji P(Ci|X)最大的類Ci 稱為最大后驗假定。由貝葉斯公式可知PCiX=PXCiP(Ci)P(X) 3、由于P(X) 對于所有類

12、都為常數(shù)，只需要P(X|Ci)P(Ci )最大即可。如果類的先驗概率未知，通常根據(jù)貝葉斯假設，可取P(C1)=P(C2)=P(Cm)，從而只需P(X|Ci)最大化。也可以用P(Ci )=si /s 計算，其中si 是類Ci 中的訓練樣本數(shù)，s 是訓練樣本總數(shù)。4. 當數(shù)據(jù)集的屬性較多時，計算P(X|Ci)的開銷可能非常大。如果假定類條件獨立，可以簡化聯(lián)合分布，從而降低計算P(X|Ci)的開銷。給定樣本的類標號，若屬性值相互條件獨立，即屬性間不存在依賴關(guān)系，則有：PXCi=k=1nP(Xk|Ci)其中，概率P(x1|Ci), P(x2|Ci), P(xn|Ci)可以由訓練樣本進行估值。如果Ak

13、是離散值屬性，則P(xk|Ci)=sik/si 。其中，sik 是類Ci 中屬性Ak 的值為xk 的訓練樣本數(shù)，而si 是Ci 中的訓練樣本數(shù)。如果Ak 是連續(xù)值屬性，通常假定該屬性服從高斯分布（正態(tài)分布）。從而有PXkCi=gXk,Ci,Ci=12Ciexp(-12Ci2(Xk-Ci)2)其中，給定類 Ci的訓練樣本屬性 Ak的值，gXk,Ci,Ci是屬性 Ak的高斯密度函數(shù)，Ci,Ci分別為均值和標準差。5. 對每個類Ci ，計算P(X|Ci)P(Ci)。把樣本X指派到類Ci 的充分必要條件是P(X|Ci)P(Ci)>P(X|Cj)P(Cj) 1jm，ji 也就是說，X 被分配到使P

14、(X|Ci)P(Ci)最大的類Ci中。應用舉例：使用樸素貝葉斯分類預測未知樣本的類標號。給定PlayTennis 的訓練樣本集見下表。使用樸素貝葉斯分類來預測樣本為Outlook=Sunny, Temperature=Hot, Humidity=High, Wind=Strong的情況下，是否打球。要分類的未知樣本為：X =Outlook=Sunny, Temperature=Hot, Humidity=High, Wind=Strong。根據(jù)樸素貝葉斯分類方法，需要最大化P(X|Ci)P(Ci)，i =1, 2。每個類的先驗概率P(Ci)可以根據(jù)訓練樣本計算：P(PlayTennis=“Ye

15、s”) = 9/14 = 0.643P(PlayTennis=“No”) = 5/14 = 0.357為計算P(X |Ci)，i=1, 2，先計算下面的條件概率：P(Outlook=“Sunny”| PlayTennis =“Yes”) = 2/9 = 0.222P(Outlook=“Sunny”| PlayTennis =“No”) = 3/5 = 0.600P(Temperature=“Hot”| PlayTennis =“Yes”) = 2/9 = 0.222P(Temperature=“Hot”| PlayTennis =“No”) = 2 /5 = 0.400P(Humidity=“

16、High”| PlayTennis =“Yes”) = 3/9 = 0.333P(Humidity=“High”| PlayTennis =“No”) = 4/5 = 0.800P( Windy=“Strong”| PlayTennis =“Yes”) = 3/9 = 0.333P( Windy=“Strong”| PlayTennis =“No”) = 3/5 = 0.600利用以上概率，可以得到：P(X | PlayTennis =“Yes”) = 0.222×0.222×0.333×0.333 = 0.005P(X | PlayTennis =“No”) =

17、 0.600×0.400×0.800×0.600 = 0.115P(X | PlayTennis =“Yes”) P(PlayTennis =“Yes”) = 0.005×0.643 = 0.003P(X | PlayTennis =“No”) P(PlayTennis =“No”)= 0.115×0.357 = 0.041因此，將樣本X 指派給類C2：PlayTennis =“No”。即在Outlook = Sunny,Temperature = Hot, Humidity = High, Wind = Strong的情況下不去打球。支持向量

18、機（SVM）算法： 支持向量機（support vector machine），是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，其學習策略便是間隔最大化，最終可轉(zhuǎn)化為一個凸二次規(guī)劃問題的求解。支持向量機將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。因此最大化幾何間隔成了我們訓練階段的目標。如下圖所示：為了簡化問題，我們用二維空間來解釋這個分類問題。要將圖中黑白圓圈分類，中間的直線就是一個分類函數(shù)，它可以完全

19、將這些樣本分開。一般的，如果一個線性函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的，否則稱為非線性可分的。實際上，一個線性函數(shù)是一個實值函數(shù)（即函數(shù)的值是連續(xù)的實數(shù)），而我們的分類問題（例如這里的二元分類問題回答一個樣本屬于還是不屬于一個類別的問題）需要離散的輸出值，例如用1表示某個樣本屬于類別C1，而用0表示不屬于，這時候只需要簡單的在實值函數(shù)的基礎上附加一個閾值即可，通過分類函數(shù)執(zhí)行時得到的值大于還是小于這個閾值來確定類別歸屬。 例如我們有一個線性函數(shù)g(x)=wx+b我們可以取閾值為0，這樣當有一個樣本xi需要判別的時候，我們就看g(xi)的值。若g(xi)>0，就判別為類

20、別C1，若g(xi)<0，則判別為類別C2（等于的時候我們就拒絕判斷）。但實際上這個線性函數(shù)（分類函數(shù)）可以平移或者稍微旋轉(zhuǎn)，同樣可以將樣本分割成兩類，所以就需要有個度量標準來判斷哪個分類函數(shù)更好。通常使用“分類間隔”，即我們要求最大化這個分類間隔。在二元的線性分類中，這個表示分類的標記只有兩個值，1和-1（用來表示屬于還是不屬于這個類）。有了這種表示法，我們就可以定義一個樣本點到某個超平面的間隔：i=yi(wxi+b)現(xiàn)在把w和b進行一下歸一化，即用w/|w|和b/|w|分別代替原來的w和b，那么間隔就可以寫成，歸一化w和b之后得到的間隔稱為幾何間隔，即：那么由于間隔：=y(wx+b)

21、=|g(x)|幾何間隔：，可以得出=|w|幾何 ，這樣w和幾何是成反比的，這樣求幾何間隔的最大化問題就轉(zhuǎn)成求最小化|w|。Adaboost算法：Adaboost是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個更強的最終分類器 (強分類器)。其算法本身是通過改變數(shù)據(jù)分布來實現(xiàn)的，它根據(jù)每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進行訓練，最后將每次訓練得到的分類器最后融合起來，作為最后的決策分類器。使用adaboost分類器可以排除一些不必要的訓

22、練數(shù)據(jù)特徵，并將關(guān)鍵放在關(guān)鍵的訓練數(shù)據(jù)上面。算法的具體步驟如下：1、給定訓練樣本集S，其中X和Y分別對應于正例樣本和負例樣本；T為訓練的最大循環(huán)次數(shù)；2、初始化樣本權(quán)重為1/n，即為訓練樣本的出事概率分布；3、第一次迭代：（1）訓練樣本的概率分布相當，訓練弱分類器；（2）計算弱分類器的錯誤率；（3）選取合適閾值，是的誤差最小；（4）更新樣本權(quán)重。經(jīng)過T此循環(huán)后，得到T個弱分類器，按更新的權(quán)重疊加，最終的到強分類器。具體步驟如下：給定m個樣本(x1,y1),.(xm,ym)，其中xiX，yiY=-1,+1 Xi表示X中的第i個元素，yi表示與Xi對應元素的屬性值，+1表示Xi屬于某個分類，-1表

23、示Xi不屬于與某個分類。初始化訓練樣本xi的權(quán)重D(i): i=1,.,m;（1）若正負樣本數(shù)目一致，D1(i) = 1/m（2）若正負樣本數(shù)目m+，m-則正樣本D1(i)=1/m+, 負樣本D1(i)=1/m-.進行多次迭代，用t=1,2.,T表示迭代的輪次。（1）計算該弱分類器的權(quán)值Dt下的錯誤率：t=i=1mDt(Xi) (yiht(xi)。若劃分正確，則不計入誤差；若劃分錯誤，則計入誤差。（2）IF t0.5, then stop（3）更新分類器權(quán)重：t=12ln1-tt（4）根據(jù)上述錯誤率更新樣本權(quán)值： Dt+1i=Dt(i)Zt×exp-t, htxi=yiexpt, h

24、t(xi)yi Zt是規(guī)范化因子（5）最后得到強分類器：HX=sign(t=1Ttht(x)應用于二分類或者多分類的應用場景以及一些特征選擇（目前有基于Haar特征的Adaboost人臉檢測技術(shù)）分類回歸樹（CART）：預測： 預測是構(gòu)造和使用模型評估無標號的樣本，或評估給定樣本可能具有的屬性值或值區(qū)間。分類和回歸是兩類主要預測的問題。其中，分類是預測離散或者標稱值，而回歸用于預測連續(xù)或者有序值。觀點任務：預測類標號為分類，預測連續(xù)值（例如：使用回歸方法）為預測。連續(xù)值的預測一般用回歸統(tǒng)計技術(shù)建模?；貧w方法包括線性回歸（LinearRegression）、多元回歸（Multiple Regre

25、ssion）、非線性回歸（Polynomial Regression）、泊松回歸（Poisson Regression）、對數(shù)回歸（Log-linear Regression，有的稱為邏輯線性回歸）等。許多問題可以用線性回歸解決，不能解決的需要將非線性問題轉(zhuǎn)換成線性問題來處理。回歸分析算法：確定兩種或兩種以上變量間相互依賴的定量關(guān)系的統(tǒng)計分析算法。在預測系統(tǒng)中的應用主要是根據(jù)訓練樣本中的數(shù)據(jù)，分析屬性間的相互關(guān)系（線性或者非線性關(guān)系），從而可以預測新樣本數(shù)據(jù)相關(guān)的屬性值。如線性回歸算法，多元回歸算法，非線性回歸算法。這里舉最簡單的線性算法為例，在線性回歸中，用直線建模，將一個隨機變量Y看做另一

26、個隨機變量X的線性函數(shù)。Y=+X，其中Y的方差為常數(shù)，和為回歸系數(shù)，可以用最小平方法求解。給定s個樣本(x1,y1)，(x2,y2). (xn,yn)，回歸系數(shù)的計算公式如下：=i=1nxi-x(yi-y)i=1nxi-x2=y-x , x,y是平均數(shù)。應用舉例：預測年薪下圖給出了一組年薪數(shù)據(jù)以及對應相關(guān)的數(shù)據(jù)點，X,Y分別表示工作年數(shù)與收入，可以發(fā)現(xiàn)X和Y之間存在線性關(guān)系（如圖）。用公式Y(jié)=+X表示。 那么根據(jù)回歸系數(shù)的計算公式，就可以得到方程Y=23.6+3.5X。那么就可以求得例如具有10年工作經(jīng)驗的員工的年薪。關(guān)聯(lián)規(guī)則分析算法：發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)或者相關(guān)關(guān)系。布爾關(guān)聯(lián)規(guī)則

27、Apriori算法Apriori性質(zhì)：頻繁項集的所有非空子集都必須是頻繁的。如果項集I不滿足最小支持度閾值，則I不是頻繁項，那么如果項A添加到I，結(jié)果項集IA不可能比I更頻繁出現(xiàn)。因此IA也不是頻繁的，即，則。Apriori算法：使用候選項集找頻繁項集的逐層搜索的迭代方法，即K項集用于探索（k+1）項集。過程由連接和剪枝組成。連接：為找Lk，通過Lk-1*Lk-1(與自身的連接)產(chǎn)生候選k項集的集合。要求連接的項集共享k-1=0個項。剪枝：根據(jù)Apriori性質(zhì)，頻繁項集的所有子集都必須是頻繁的，刪除自身連接產(chǎn)生的不頻繁項集。（我們只需要檢查它們的k-1項子集是否頻繁）重復連接和剪枝的過程，直

28、到不能再產(chǎn)生頻繁k項集的集合，算法終止，即找出了所有的頻繁項集。Apriori算法的應用實例：下圖為某商場的交易記錄，共有9個事務。假定最小事務支持計數(shù)為2，即min_sup=2/9=22%，利用Apriori算法尋找頻繁項集的過程如下：頻繁項集L1C候選集C1C項集比較候選支持度計數(shù)與最小支持度計數(shù)支持度計數(shù)I16I27I36I42I52項集支持度計數(shù)I16I27I36I42I52掃描所有的交易記錄對每個候選計數(shù)候選集C2C候選集C2C頻繁項集L2C項集(I1,I2)掃描事務，對每個候選計數(shù)(I1,I3)(I1,I4)(I1,I5)(I2,I3)(I2,I4)(I2,I5)(I3,I4)(I

29、3,I5)(I4,I5)項集(I1,I2)4(I1,I3)比較候選支持度計數(shù)與最小支持度計數(shù)4(I1,I4)1(I1,I5)2(I2,I3)4(I2,I4)2(I2,I5)2(I3,I4)0(I3,I5)1(I4,I5)0項集(I1,I2)4(I1,I3)4(I1,I5)2(I2,I3)4(I2,I4)2(I2,I5)2由L1產(chǎn)生候選C2頻繁項集L2C候選集C2C候選集C2C比較候選支持度計數(shù)與最小支持度計數(shù)掃描事務，對每個候選計數(shù)由L1產(chǎn)生候選C2項集(I1,I2,I3)(I1,I2,I5)項集(I1,I2,I3)2(I1,I2,I5)2項集(I1,I2,I3)2(I1,I2,I5)2由上過

30、程可得到事務系統(tǒng)的頻繁項集，因此我們可以由頻繁項集生成事務系統(tǒng)的強關(guān)聯(lián)規(guī)則（強關(guān)聯(lián)規(guī)則滿足最小支持度和最小置信度）。最小置信度公式表示如下：confidenceA=>B=PBA=support_count(AB)support_count(A)其中，support_count(AB)和support_count(A)表示包含項集AB、A的事務計數(shù)，根據(jù)以上公式，可以產(chǎn)生關(guān)聯(lián)規(guī)則如下：1、對于每個頻繁項集L，產(chǎn)生L的所有非空子集2、對于每個非空子集S，如果support_count(L)support_count(S)min_conf，則輸入規(guī)則：“S=>(L-S)”那么例子中的頻繁

31、項集將產(chǎn)生以下關(guān)聯(lián)規(guī)則：I1I2=> I5confidence=2/4I1I5=> I5confidence=2/2I2I5=> I5confidence=2/2I1=>I2 I5confidence=2/6 I2=>I1 I5confidence=2/7I5=>I1 I2confidence=2/2假設置信度為70%，那么只有第2,3,6條滿足強關(guān)聯(lián)規(guī)則。聚類Clustering分析算法：一種無監(jiān)督的機器學習算法，對沒有標記（分類）的訓練樣本進行學習，以發(fā)現(xiàn)訓練樣本集中的結(jié)構(gòu)性知識。這里，所有的標記（分類）是未知的。而聚類則是指將物理或抽象對象的集合分到不

32、同組的分析過程。這些組內(nèi)成員具有很大的相似性，而組間成員具有很大的相異性。同分類（Classification）不同，聚類不依賴事先預定義的類標記，而需要自己標識。K-Means算法：K-means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大。算法過程如下：1）從N個集合對象隨機選取K個對象作為圓心；2）對剩余的每個集合對象測量其到每個質(zhì)心的距離，并把它歸到最近的圓心的類；3）重新計算已經(jīng)得到的各個類的圓心；4）迭代23步直至新的圓心與原圓心相等或小于指定閾值，即算法收斂結(jié)束。PageRank算法：Google的網(wǎng)頁排名算法，是一種由

33、根據(jù)網(wǎng)頁之間相互的超鏈接計算等級（PR值）的排序算法。其基本思想如下：如果網(wǎng)頁T存在一個指向網(wǎng)頁A的連接，則表明T的所有者認為A比較重要，從而把T的一部分重要性得分賦予A。這個重要性得分值為：PR（T）/L(T)。其中PR（T）為T的PageRank值，L(T)為T的出鏈數(shù)。即一個頁面的得票數(shù)由所有鏈向它的頁面的重要性來決定，到一個頁面的超鏈接相當于對該頁投一票。一個頁面PageRank值是由所有鏈向它的頁面（鏈入頁面）的重要性經(jīng)過遞歸算法得到的。簡單的PageRank模型如下，A,B,C,D分別代表網(wǎng)頁節(jié)點，如果網(wǎng)頁A存在鏈接到網(wǎng)頁B，則存在一條有向邊A->B（有向圖如下：）。 BCC

34、DA 如上圖的話，我們可以得到4個網(wǎng)頁的PR值如下：PRA=PRB2+PRCPRB=PRA3+PRD2PRC=PRA3+PRD2 PRD=PRA3+PRB2也可以用n*n的矩陣表示該有向圖，其中每行代表的是元素指向的節(jié)點，如第一行表示存在A節(jié)點指向B、C和D的鏈接。列表示對于指定的節(jié)點有多少個指向該節(jié)點的節(jié)點，如第一列則表示指向A節(jié)點的有B和C節(jié)點。因為PR值要平均到每個鏈接，因此將矩陣每行除以每行的鏈接數(shù)可以得到新的矩陣如下：將矩陣M'轉(zhuǎn)置后得到MT由此我們可以得到PageRank的計算公式： PR(i)=(1-d)/n+dj=1nPR(j)L(j)用矩陣的形式表示如下：PR=(1-d)/n(1-d)/n+dL(1,1)L(1,n)L(n,1)L(n,n)PR（PR代表PageRank值，這里引入了d阻尼因素，是為了解決終止點和陷阱問題）PageRank算法的計算是一個迭代的過程，遞歸直到最