1.3 十大數(shù)據(jù)挖掘算法簡介

本節(jié)給出對數(shù)據(jù)挖掘的十大算法的簡要介紹。有些比較常用的算法可能會在不同的應(yīng)用案例中被多次使用到。

數(shù)據(jù)挖掘十大算法源自于2016年一篇發(fā)表在《IEEE International Conference on Data Mining （ICDM）》的論文，并收錄在2007年12月的《Journal of Knowledge and Information Systems》雜志上。

ICDM 2006的會議邀請ACM SIGKDD發(fā)明獎得主和IEEE ICDM研究貢獻(xiàn)獎得主作為數(shù)據(jù)挖掘十大算法提名委員會專家。十大數(shù)據(jù)挖掘算法首先經(jīng)過委員會專家的提名，然后再查閱其引用次數(shù)（要求至少50 次以上），選出18個算法。最后再邀請ACM SIGKDD 2006、IEEE ICDM 2006、SIAM DM 2006 3個國際會議的程序委員會委員投票選出前十大數(shù)據(jù)挖掘算法。

這十大算法見表1-2。

這里，作者只簡述這十大算法的思想。關(guān)于這十大算法的詳細(xì)介紹，讀者可以在數(shù)據(jù)挖掘和機器學(xué)習(xí)的教科書上查閱。另外，《Machine Learning in Action》這本書也針對這十大算法的實現(xiàn)做了詳細(xì)的代碼講解。十大數(shù)據(jù)挖掘算法里，k近鄰（k-Nearest Neighbors）、C4.5、支持向量機（Support Vector Machine）、AdaBoost、CART、樸素貝葉斯用于解決分類任務(wù)。k-均值（k-means）是最常見的聚類算法。Apriori 是關(guān)聯(lián)規(guī)則挖掘算法。Expectation Maximization 是一種估計概率模型參數(shù)的算法。PageRank是一種鏈接分析的算法，主要用于圖數(shù)據(jù)里，對節(jié)點重要性進(jìn)行排名。

k近鄰算法的思想是通過找事物屬性上的相似性，去揣測類別上的相同，簡單來說就是類比法。k 近鄰算法從訓(xùn)練數(shù)據(jù)集里找出和待分類的數(shù)據(jù)對象最相近的 k個對象。這k個對象中出現(xiàn)次數(shù)最多的那個類別，就可以被當(dāng)作這個待分類的數(shù)據(jù)對象的類別。例如，我們對一個植物樣本進(jìn)行分類的時候，通過對比這個樣本和實驗室的標(biāo)本之間的各個特征，例如長度、直徑、顏色等屬性，然后找到最相似的幾個標(biāo)本。這幾個標(biāo)本的類別就應(yīng)該是這個植物樣本的類別。如果這幾個標(biāo)本的類別也不同，我們?nèi)±锩娉霈F(xiàn)次數(shù)最多的那個類別。

通過調(diào)節(jié)k值的大小，能夠改變分類結(jié)果，進(jìn)而改變分類準(zhǔn)確率。在圖1-3所示的例子中，當(dāng)設(shè)置k值為3時，該點分類結(jié)果為三角形（鄰居分布：2個三角形， 1個正方形）；當(dāng)設(shè)置k值為5時，該點分類結(jié)果為正方形（鄰居分布：3個正方形， 2個三角形）。

由于在計算某待分樣本的過程中，需要計算該樣本與所有樣本點的距離，進(jìn)而找到最近鄰居，k近鄰算法被稱作基于條目（Instance-Based）的分類算法。因此，區(qū)別于很多訓(xùn)練好模型便可以丟棄訓(xùn)練數(shù)據(jù)的方法，k近鄰算法需要保留訓(xùn)練數(shù)據(jù)。

C4.5和CART （Classification and Regression Tree） 都是基于決策樹（Decision Tree）的分類算法。決策樹本質(zhì)上是一個對訓(xùn)練數(shù)據(jù)進(jìn)行劃分的數(shù)據(jù)結(jié)構(gòu)。決策樹中每個節(jié)點代表一個關(guān)于屬性的問題。對這個問題的不同回答決定了一個數(shù)據(jù)對象被分到樹的不同分支。最終所有的訓(xùn)練數(shù)據(jù)都會被塞入某個葉子節(jié)點。這和常見的二分搜索樹、B+樹等數(shù)據(jù)結(jié)構(gòu)沒有本質(zhì)的區(qū)別。與其他樹的數(shù)據(jù)結(jié)構(gòu)用途不同的是，決策樹最終的目的是要回答一個數(shù)據(jù)對象的類別。如果一個未知類別的數(shù)據(jù)對象被決策樹劃分到某個葉子節(jié)點，這個葉子節(jié)點內(nèi)的數(shù)據(jù)類別就可以被當(dāng)作這個數(shù)據(jù)的類別標(biāo)記。如果葉子節(jié)點的數(shù)據(jù)有幾個不同的類別，與k近鄰算法一樣，我們?nèi)〕霈F(xiàn)次數(shù)最多的那個類別。

在圖1-4所示的例子中，橢圓形表示屬性節(jié)點，用于劃分?jǐn)?shù)據(jù)，矩形表示葉節(jié)點，用于指定分類結(jié)果。假設(shè)一條訓(xùn)練數(shù)據(jù)的屬性取值為{天氣=涼爽，刮風(fēng)=是}，那么按照給定的決策樹，該條數(shù)據(jù)的分類結(jié)果應(yīng)為“不打球”。

為了盡可能保持回答的一致性，我們希望每個葉子節(jié)點內(nèi)的數(shù)據(jù)類別盡量保持一致。直觀來說，這樣決策樹在回答一個數(shù)據(jù)類別的時候，就更加有把握。因此，我們希望決策樹每個葉子節(jié)點的類別分布越純越好（或越單調(diào)越好）。當(dāng)一個節(jié)點內(nèi)所有數(shù)據(jù)的類別都一致的時候，純度最高。當(dāng)一個節(jié)點所有數(shù)據(jù)的類別都兩兩不相同的時候，純度最低。此時，類別分布最混亂，簡單理解就是類別分布過于平均，不傾向任何一個類別。可以說，此時的類別分布最混亂、最不純。

純度可以用不同的指標(biāo)來測量，常見的純度指標(biāo)包括熵（Entropy）和基尼指數(shù)（Gini Index）。一個節(jié)點的純度越高，熵和基尼指數(shù)就越小。將數(shù)據(jù)集按照某屬性取值劃分后，得到的新的純度估計叫作條件熵（Conditional Entropy），因此純度的提升可以表示為劃分后條件熵與劃分前熵的差異，這個差異值叫作信息增益（Information Gain）。在決策樹構(gòu)建中，選取使當(dāng)前信息增益最大的屬性進(jìn)行分支構(gòu)建。當(dāng)下一步劃分引發(fā)的信息增益很小，或者已經(jīng)沒有屬性再供劃分之時，將節(jié)點轉(zhuǎn)換為葉節(jié)點，并將該節(jié)點內(nèi)數(shù)量最多的類別標(biāo)記作為該節(jié)點的類別標(biāo)記。通過這樣遞歸地構(gòu)建分支（即葉節(jié)點）生成的樹叫作ID3決策樹。但是，由于ID3算法無法處理連續(xù)（數(shù)值）屬性，并沒有入選十大挖掘算法。

但是，C4.5（或CART）算法，均與ID3算法有著相似的遞歸樹構(gòu)建理念。除能處理連續(xù)屬性和樣本缺省值外，C4.5算法利用信息增益比（Information Gain Ratio）評估分支屬性，在信息增益的基礎(chǔ)上，除以屬性本身取值的分散性（用熵表示），用以修正在使用信息增益的過程中選擇結(jié)果偏向取值較多的屬性的偏差。另外，在C4.5中引入了剪枝（Pruning）操作，通過停止樹生長，或去除某個子樹的方式，減少決策過程劃分過細(xì)引起的過擬合（Overfitting）問題。

對比而言，CART將基尼指數(shù)與條件基尼指數(shù)的差異，作為評估屬性重要性依據(jù)。同時，CART能夠處理回歸任務(wù)，因此，在算法用途上更加廣泛。

Na?ve Bayes是通過貝葉斯定理（Bayesian Theorem）來進(jìn)行分類的。樸素貝葉斯將數(shù)據(jù)的屬性和類別看作兩個隨機變量（X和Y），然后問題轉(zhuǎn)換成為給定屬性X，找出哪個Y出現(xiàn)的概率最大，即貝葉斯定理中的后驗概率P（Y|X）。

根據(jù)貝葉斯定理，后驗概率可以由先驗概率和條件概率計算出來。而先驗概率和條件概率可以由訓(xùn)練數(shù)據(jù)統(tǒng)計而得。因此分類的過程被轉(zhuǎn)換為一系列計算后驗概率P（Y1|X）,…,P（Yc|X）的過程，后驗概率最大對應(yīng)的類別標(biāo)記即分類結(jié)果。

樸素貝葉斯之所以叫樸素，是因為這個算法假設(shè)對于給定的數(shù)據(jù)對象的類別Y來說，不同屬性的出現(xiàn)是互相獨立的（Conditionally Independent），這種樸素假設(shè)大大簡化了運算。假定X有f個屬性，那么對于類別標(biāo)記Y而言，在獨立性假設(shè)下， P(Y|X)的取值可用式（1-2）進(jìn)行評估。因為無須考慮各個屬性X1,…,Xf之間的相關(guān)性，因此運算被大大簡化。

支持向量機是近年來使用得最廣的分類算法，因為它在高維數(shù)據(jù)，例如圖像和文本上的表現(xiàn)都好過其他很多算法。與Na?ve Bayes的不同之處在于，它不關(guān)心這個數(shù)據(jù)是如何產(chǎn)生的，它只關(guān)心如何區(qū)分這個數(shù)據(jù)的類別。所以也稱這種分類算法是判別式（Discriminative）的。在 SVM 算法內(nèi)，任何一個數(shù)據(jù)都被表示成一個向量，也就是高維空間中的一個點，每個屬性代表一個維度。SVM和大多數(shù)分類算法一樣，假設(shè)一堆數(shù)據(jù)的類別相同，那么它們的其他屬性值也應(yīng)該相近。因此，在高維空間上，不同的類別數(shù)據(jù)應(yīng)該處于不同的空間區(qū)域。SVM的訓(xùn)練算法就是找出區(qū)分這幾個區(qū)域的空間分界面。能找到的分界面可能有很多個，SVM算法中選擇的是兩個區(qū)域之間最靠近正中間的那個分界面，或者說離幾個區(qū)域都最遠(yuǎn)的那個分界面（Maximum-Margin Hyperplane）。因此，相比邏輯斯特回歸（Logistic Regression）而言，SVM中的分界面只有一個，即最大間隔分界面。

因為現(xiàn)實數(shù)據(jù)可能是有噪聲的。如果有了噪聲，一個數(shù)據(jù)可能會在觀測空間位置的周圍區(qū)域都出現(xiàn)。離幾個區(qū)域最遠(yuǎn)的那個分界面能夠盡量保證有噪聲的數(shù)據(jù)點不至于從一個區(qū)域跳到另外一個區(qū)域去。這個最佳的分界面尋找問題在 SVM 中被表示成一個有約束的優(yōu)化問題（Constrained Optimization）。通過優(yōu)化算法里的拉格朗日法可以求得最優(yōu)的分界面。

如圖1-5所示，SVM通過求解帶約束優(yōu)化問題，尋找深、淺兩組數(shù)據(jù)分布之間的最大間隔，這個最大間隔由間隔邊界（圖1-5中虛線表示）上的數(shù)據(jù)點來支持，這些點是原數(shù)據(jù)樣本中的特殊點。由于這些點支持了間隔邊界，又用向量表示，因此這些點被稱為支持向量（Support Vector）。通常，支持向量在樣本中所占的比例很小。

在硬間隔（Hard Margin）支持向量機中，不容忍數(shù)據(jù)點分布在分界面（圖1-5中實線表示）和間隔邊界之間。而在一些特殊情況下，例如深、淺數(shù)據(jù)分布有重疊，樣本數(shù)據(jù)近似線性可分（Approximately Linear Separable）時，為保證模型的泛化性（Generalization），需要容忍分界面和間隔邊界中的某些點，如圖1-6所示，這些點要么是錯分點，要么就是劃分置信度（Confidence）不夠。這種情況下的SVM叫作軟間隔（Soft Margin）支持向量機。

另外一種情況是，數(shù)據(jù)根本就線性不可分（Non-Linear Separable），SVM對這種情況引入核技巧（Kernel Trick）。核技巧的基本思想是通過升維的方式將原本線性不可分的數(shù)據(jù)轉(zhuǎn)化為線性可分?jǐn)?shù)據(jù)，再類似地求解最大分界面。在圖1-7所示的例子中，原本線性不可分的數(shù)據(jù)，在映射到核空間后，能夠很好地進(jìn)行劃分。

AdaBoost（Adaptive Boosting）是一種集成學(xué)習(xí)算法。其核心思想是在同一個訓(xùn)練集上，通過考察上一次實驗中每個樣本的分類是否正確以及總體分類的準(zhǔn)確率，自適應(yīng)地調(diào)整每個樣本的權(quán)值，迭代地生成若干個不同的分類器（弱分類器），最終將這些分類器組合起來，提升為一個強分類器。

AdaBoost的基本過程如下：

步驟1 對訓(xùn)練數(shù)據(jù)每個樣本初始化一個權(quán)重（初始權(quán)重均相等），構(gòu)成權(quán)重向量；

步驟2 利用弱分類器進(jìn)行訓(xùn)練，并計算加權(quán)錯誤率；

步驟3 依據(jù)求得的錯誤率調(diào)整樣本權(quán)重，同時，依據(jù)求得的錯誤率調(diào)整分類器系數(shù)；

步驟4 不斷迭代步驟2和步驟3，直到指定迭代次數(shù)或錯誤率為0時，停止迭代。

AdaBoost并不是指集成不同的分類算法，而是對不同訓(xùn)練數(shù)據(jù)集創(chuàng)造分類器。AdaBoost為了減少分錯的情況，有意識專門針對分錯的數(shù)據(jù)進(jìn)行訓(xùn)練。這種思想就如中學(xué)時期的試卷練習(xí)一樣。同一份試卷的考題可以讓學(xué)生做多次，但每次只需要重復(fù)上次學(xué)生做錯的題；而上次做對了的題目，就不需要反復(fù)練習(xí)了。這樣的練習(xí)可以突出重點，同時又節(jié)約時間。

在 AdaBoost 算法中，每一步迭代中均涉及兩個權(quán)重的更新，一是樣本權(quán)重，二是分類器權(quán)重。在樣本權(quán)重更新中，傾向于賦更大權(quán)重給上一步錯分樣本，以提高其在本次迭代中的“發(fā)言權(quán)”；在分類器權(quán)重更新中，傾向于將更大權(quán)重給錯誤率小的分類器，以突出“優(yōu)秀”分類的作用。最終的分類器表示為弱分類器的線性組合，用以給出集成后的分類結(jié)果。

k-means是最常見的聚類算法。k-means先隨機在數(shù)據(jù)集里找k個簇中心點，把每個數(shù)據(jù)分到離它最近的中心所在的那個簇；然后再計算新的簇中心點。由此不斷循環(huán)，直到所有簇中心不再變化。k-means 背后的思想其實屬于 Expectation Maximization的一種。Expectation Maximization算法專門針對含有隱藏變量的模型進(jìn)行估計。在k-means里，這個模型的參數(shù)就是k個簇的中心。隱藏的變量就是每個數(shù)據(jù)點的類標(biāo)。如果我們知道每個數(shù)據(jù)點的類標(biāo)，那么只需要針對每個簇的數(shù)據(jù)點求算數(shù)平均，就可以估計出這個簇的中心。但問題是，每個數(shù)據(jù)點的類標(biāo)是隱藏的（未知的），所以我們無法直接估計出每個簇的簇中心。因此，需要隨機選定幾個簇質(zhì)心，再通過迭代更新簇質(zhì)心，從而最小化簇內(nèi)相似性，最大化簇間相似性。

在圖 1-8（a）中，初始質(zhì)心（表示為+號）隨機指定，在經(jīng)過k-means 算法訓(xùn)練后，質(zhì)心為各個簇的中心點，參見圖1-8（b）。

k-means算法是最簡單，也是最常用的聚類算法，然而由于初始質(zhì)心隨機指定，算法最終結(jié)果可能收斂為局部最小。

期望最大化（Expectation Maximization，EM）算法解決的問題是，在隱變量（Latent Variable）存在的情況下，對隱變量進(jìn)行估計。在EM算法中，通過求解最大似然（Maximum Likelihood）找出模型參數(shù)，以使這個模型最能描述當(dāng)前觀察數(shù)據(jù)。換句話說，這個估計方法希望讓觀察的數(shù)據(jù)在這個估計的模型里出現(xiàn)的概率最高。

最大似然是統(tǒng)計學(xué)中一個參數(shù)估計原則。至于為什么要用最大似然這個原則，這源于概率論與數(shù)理統(tǒng)計的一個直觀假設(shè)：觀察到的事件總比沒有觀察到的事件發(fā)生的概率高；多次觀察到的事件出現(xiàn)的概率總比很少觀察到的事件出現(xiàn)的概率高。

EM算法是兩個不同步驟的不斷循環(huán)。一個步驟叫作Expectation，也就是固定當(dāng)前模型的參數(shù)，估計最有可能隱藏變量的值。另外一個步驟叫作 Maximization，即通過當(dāng)前估計隱藏變量的值，估計模型的參數(shù)。EM 算法不斷迭代隱變量和模型參數(shù)的求解，直到模型的參數(shù)不再變化，算法即停止。在圖 1-9 中給出了一個 EM算法的實例[3]。拋擲兩枚硬幣A、B：每次實驗拋擲硬幣10次，重復(fù)5次實驗，當(dāng)前拋擲的硬幣為A或B是未知的（隱變量）。依據(jù)5次實驗結(jié)果，估計硬幣A與B正面朝上（用H表示，同理背面朝上用T表示）的概率θA與θB。

首先估計初始狀態(tài)硬幣A、B朝上的概率分別為0.6和0.5，按照二項分布估計硬幣為A或B的概率分別為0.45和0.55。利用求得的概率乘以觀察到的5次實驗的結(jié)果，得到估計出的硬幣A和B分別正面朝上的分布情況，例如對硬幣A而言， 2.2枚正面朝上，2.2枚背面朝上；對硬幣 B 而言，2.8枚正面朝上，2.8枚背面朝上。依據(jù)這樣的結(jié)果更新θA與θB（更新的方向為在估計的隱變量下，得到的結(jié)果最接近觀察到的實驗結(jié)果，即求解實驗結(jié)果在隱變量取值概率下的期望最大化，亦即Maximization步驟），那么更新后的θA與θB分別為0.71和0.58。將得到的估計再次傳遞給 Expectation 步驟，重復(fù)以上步驟，直到θA與θB不再明顯變化為止。

Expectation和Maximization都是基于最大似然方法找隱藏變量的值和模型的參數(shù)值。在k-means里，把每個數(shù)據(jù)點塞進(jìn)k個簇中，尋找離簇中心最近的那個步驟就是 Expectation。通過計算簇內(nèi)所有數(shù)據(jù)點的算術(shù)平均得到簇中心的步驟就是Maximization。k-means 的目的是讓每個簇內(nèi)的數(shù)據(jù)點盡量靠近簇中心。從最大似然的角度來看，一個數(shù)據(jù)點越靠近其簇中心，它出現(xiàn)的概率就越高。因此在步驟Expectation中，k-means把每個數(shù)據(jù)點塞給距離最近的那個簇中心的簇。Maximization步驟的簇中心是通過算術(shù)平均求得的。算術(shù)平均就是最大似然的估計。

Apriori 算法的最早提出是為了尋找關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則最著名的例子莫過于“啤酒與尿布”，在超市貨籃數(shù)據(jù)分析中，人們發(fā)現(xiàn)年輕爸爸在超市買尿布時，常常也會順帶為自己買啤酒。因此，從營銷的角度來看，超市可以將尿布和啤酒綁定銷售，或者給一點小小的折扣，以此刺激消費。這種促銷方案類似于現(xiàn)在很多電信運營商的套餐服務(wù)。

關(guān)聯(lián)規(guī)則通常表示成，意思是如果A、B出現(xiàn)了，那么C也有很大可能出現(xiàn)。關(guān)聯(lián)規(guī)則依據(jù)歷史數(shù)據(jù)求得。顯然，不能因為歷史數(shù)據(jù)中出現(xiàn)了一條數(shù)據(jù)同時包含A、B、C就認(rèn)為成立。只有足夠的數(shù)據(jù)記錄都包含A、B、C 時，才認(rèn)為這個規(guī)則是有一定置信度（Confidence）的。所以，關(guān)聯(lián)規(guī)則第一步就是找出頻繁的項集（Frequent Item Set）。項（Item）就是指這里的A、B、C等。項集（Item Set）就是包含這些項的集合。在這個例子里，{A,B,C}就是一個頻繁的項集，A、B、C 屬于項。如果數(shù)據(jù)庫里有n個不同的項，那么總共可能有2n個項集。顯然我們不能一個一個去試，看其是否頻繁。Apriori算法要解決的問題就是如何快速找出頻繁項集。Apriori 的核心思想就是認(rèn)為如果項集{A,B,C}是頻繁的，那么它的子集也必須是頻繁的。這就是 Apriori 算法里所描述的遞減性質(zhì)（Anti-Monotonic Property）。

頻繁的定義就是指出現(xiàn)的次數(shù)大于某個預(yù)先定義的閾值。因此，可以從只含一個項的集合開始搜索，剔除非頻繁項。然后通過自拼接的方式，尋找只含2個項的集合，再剔除非頻繁項。依次類推，即可找到所有的頻繁項集。

如果把算法的搜索看作一個搜索樹，那么每次的剔除都是剔除一棵樹的分支，所以就可以大大減小搜索空間。因為Apriori算法有很清晰和簡單的算法邏輯結(jié)構(gòu)，所以Apriori逐步成為一種搜索算法思想，有點類似動態(tài)規(guī)劃、貪心算法的概念。在很多相關(guān)論文里，算法以Apriori-like來修飾，但是算法的目的跟關(guān)聯(lián)規(guī)則挖掘并沒有關(guān)系。

Apriori算法的其他應(yīng)用還包括告警的關(guān)聯(lián)挖掘、用戶行為關(guān)聯(lián)分析以及崩潰和錯誤的關(guān)聯(lián)分析等。處理任務(wù)描述參見表1-3。

PageRank因為谷歌搜索引擎而出名。該算法以Google創(chuàng)始人之一Larry Page的姓命名，他將學(xué)術(shù)論文的評分方法（按照引用量對論文質(zhì)量進(jìn)行評估）引入網(wǎng)頁評分中。合作者Sergey Brin將算法轉(zhuǎn)換為矩陣迭代運算的形式并證明其收斂性。該算法的思想可以用圖1-10形象地表示。

滿足一個關(guān)鍵詞的網(wǎng)頁通常有很多，如何安排這些網(wǎng)頁顯示的前后順序呢？PageRank的想法就是，如果這個網(wǎng)頁被很多其他網(wǎng)頁引用，那么網(wǎng)頁重要程度就很高，理應(yīng)放得靠前一些。如果一個網(wǎng)頁只被很少網(wǎng)頁引用甚至沒有被引用，那么這個網(wǎng)頁就不重要，可以放得靠后一些。這里的引用和論文之間的引用類似。評價一篇論文的好壞也是看其引用數(shù)量。在網(wǎng)頁里，引用可以是一個超鏈接。當(dāng)然， PageRank 還可以用在其他圖數(shù)據(jù)上，只要它們存在某種鏈接，就可以認(rèn)為是這里的引用。除此之外，PageRank還認(rèn)為，如果一個網(wǎng)頁被重要的網(wǎng)頁引用，那么這個網(wǎng)頁肯定比被不重要網(wǎng)頁引用的網(wǎng)頁更重要。如果把每個網(wǎng)頁的重要分?jǐn)?shù)看成一個未知變量，這 2個直觀的假設(shè)可以整理成一個線性方程，那么 PageRank 根據(jù)此方程解出每個網(wǎng)頁的重要分?jǐn)?shù)。最后網(wǎng)頁的排名就是按照這個重要分?jǐn)?shù)由大到小排列。同時，針對有向圖中的死胡同問題（Dead End Problem）和陷阱問題（Trap Problem）， PageRank算法引入阻尼因子（Damping Factor），使得算法能以一定概率隨機跳出到外部任意頁面。

換句話說，PageRank算法綜合考慮鏈接的數(shù)量和網(wǎng)頁的質(zhì)量兩個因素,將二者結(jié)合起來對網(wǎng)頁進(jìn)行排序。需要特別指出的是，PageRank計算出的網(wǎng)頁重要性排名是完全基于鏈接結(jié)構(gòu)的，與用戶輸入的查詢關(guān)鍵字無關(guān)。所以，很多時候，PageRank是可以離線計算的。

PageRank算法原理簡單，具有簡潔之美。然而，PageRank也有諸多缺點：PageRank無法抵御鏈接攻擊（例如在權(quán)威頁面下評論，并添加自身頁面引用，提高自身PageRank值）；對新網(wǎng)頁不公平，新網(wǎng)頁到來時沒有引用量，但并不代表質(zhì)量不好。