PageRank算法在孤立點檢測中的應用

陳 謙

(暨南大學 信息科學技術學院計算機系，廣東 廣州 510632)

在數據挖掘和圖像分析中，孤立點的檢測是一個重要的內容。在很多情況下，發現孤立點比發現普通情況更有意義，如：KNORR E M和NG R T把孤立點檢測方法應用到運動員數據NHL(National Hockey League)的分析中，從而找到那些特別的運動員；YAMANISHI K和TAKEUCHI J將檢測方法應用到股票的變動檢測中等等。另一方面，PageRank(頁面分級)算法是PAGE L和BRIN S在就讀斯坦福大學研究生院時研發出來的,他們后來創建了著名的Google公司，現在分別擔任該公司的CEO和總經理。而PageRank算法就是Google搜索服務的一個核心技術。事實證明該算法在搜索服務上是非常成功的。

頁面分級的思想與在二維平面上作孤立點檢測的思想非常相近,于是本文把PageRank算法運用到孤立點檢測中，并給出實驗結果和本文算法與其他的主流算法的比較。

1 PageRank算法

1.1 PageRank算法的核心思想

對于世界上眾多的網頁，這些網頁有的十分重要，而有的重要性十分輕微。當想要快速地在這么多的網頁中找到想要的網頁時，無論想查關于哪一方面的信息，都會希望別人給出的查找結果是那些重要的網頁，而不是微乎其微的網頁。所以在查找之前就應該把網頁(或者稱為頁面)進行重要性排序。用什么來衡量一個頁面的重要性呢？計算機能否由頁面的內容來判斷頁面的重要性呢？答案是不能，計算機還沒先進到這個程度。但PageRank算法給出了一個行之有效的思想：從許多優質的頁面鏈接過來的頁面，必定還是優質的頁面[5]。這一思想容易理解，如果有很多的頁面鏈接到A頁面，那么就認為A頁面是比較重要的，那如果B頁面被A頁面鏈接 (反過來說也就是A頁面鏈出到B頁面），因為A頁面被一個認為重要的頁面鏈接，所以也就把B頁面的重要性作一個大幅度的提高，認為B頁面也是重要的。通過互聯網中頁面間本身就存在的鏈接，是容易算得頁面的重要性的。

但另一方面，有些頁面為了提高重要性，相互間做一種商業上的鏈接，為了杜絕這一種情況，PageRank在計算頁面重要性的時候，對于鏈接進來的頁面也是要考慮其重要性的，即重要性高的頁面鏈接進來，則對當前頁面重要性的提高有很大幫助；重要性低的頁面鏈接進來，則對當前頁面重要性的提高幫助很小。

1.2 PageRank算法的簡略步驟

假設有N 個頁面，這些頁面間有相互鏈接。

(1)制作一個N×N的矩陣S，如果頁面a鏈出到頁面 b，則 S(a,b)=1；

(2)將矩陣S轉置，得到矩陣S′，因為這里關心的不是該頁面鏈出到多少其他的頁面，而是有多少其他的頁面鏈進來當前頁面；

(3)對S′的每一列，算出非零元的總數sum，在把該列中的每一個非零元除以sum。這樣就得到一個新的矩陣M；

(4)算出M的特征值和特征向量;

(5)找出最大特征值所對應的特征向量，并把該特征向量標準化。標準化后的結果就是各個頁面對應的重要性的度量值，稱為PageRank值。

2 PageRank算法在孤立點檢測中的應用

2.1 應用思想

把各個不同的頁面看成是二維平面上的點，按孤立點檢測的定義，也就找出了那些離群的點，即這個點周圍的其他點很稀疏。

有必要把點按密度值進行排列,在這里，點的密度值就對應于頁面的PageRank值，即重要性。當一個點所處位置的一定范圍內出現的其他點越多，則這個點的密度值就越大，反之則越小。

是否基于密度的聚類分析就可以解決這個問題了呢？可是基于密度聚類分析算法最終得出的結果是受人為因素干擾比較大，當所選的半徑不同時，得出的結果有很大的差別。本文使用PageRank算法判斷一個點周圍其他點的數目時，選取的半徑可以為任意值(當然，不能離譜)。

以點a為中心、r為半徑畫圓，當出現在這個圓中其他點的數目達到一定量時，就說明點a與出現在這個圓的其他點是有鏈接的，即對應于頁面a鏈接到其他的頁面。接下來的操作就與頁面分級算法基本一樣了。

2.2 應用步驟

(1)算出二維平面上任意兩點間的距離；

(2)建造一個 N×N的矩陣 S，選擇半徑 r，當 a、b兩點間的距離小于r時，S(a,b)=1；

(3)將矩陣 S轉置，得到矩陣 S′;

(4)對S′的每一列算出非零元的總數sum，再把該列中的每一個非零元除以sum,這樣就得到一個新的矩陣M;

(5)算出M的特征值和特征向量;

(6)找出最大特征值所對應的特征向量,并把該特征向量標準化。標準化后的結果就是各個頁面對應的重要性的度量值，稱為PageRank值;

(7)把PageRank值排列,再利用穩健的孤立點檢測方法把孤立點檢測出來。

3 實驗以及分析

該實驗是在Matlab環境下實現的。點群如圖1所示。

從圖1可以看到，共有156個點，點的分布類型有逼近高斯分布（左邊用箭頭指的兩個），有均勻分布（右邊圈起來的）和其他的不規則矢量分布（右邊剩下的上下兩個）。把PageRank值算出來，并標在xoy面上，如圖2所示。

從圖2中挑出3個特征向量很小的地方，如箭頭所標，這里雖然標了3個箭頭，但有5個點，第一個箭頭處有 3個點。 這 5個點的序號分別是 95、96、97、140和156，而這幅點群的序號和坐標如表1所示。

表1 所測孤立點的坐標

這5個點的位置如圖3所示。

可以看到這5個點明顯都是孤立點，其他的孤立點也可以由同樣的方法找出，這里就不一一找出來了。值得注意的是，這幅點群中的分布情況是多種的，但PageRank算法都能很好地把孤立點找出來。

4 實驗結果比較

與其他的孤立點檢測算法相比較，PageRank算法有如下優點：

(1)與基于密度的檢測方法相比較，它不受給定的半徑影響。

因為在該算法中，半徑的確定只是為了判斷該點與其他點是否有“鏈接”而已，就像判斷各個頁面之間是否有鏈接，而處于稀疏群的點與處于密集群的點，無論半徑畫得大小，只要畫得不要太離譜，那處于密集群里的點與其他點的鏈接數肯定要比處于稀疏群里的點與其他點的鏈接數多，而最后是根據鏈接數的比重來排序的，也就是說半徑的大小不影響排序的位置，當然對檢測也就沒什么影響了。

(2)考慮如圖4所示的這幅圖，當用同樣的半徑去畫圓時，圓1里的點只有3個，圓2中的點有4個，但能說左邊箭頭所指的點是孤立點而右邊箭頭所指的點不是孤立點嗎？

顯然，從整幅圖來看，左邊的是一個群體，而右邊的4個點才是孤立點，或者說是一小群孤立點。其原因就在于與左邊的點1鄰近的點都是密集度高的點，即它背后有一整個群體做支持，而與右邊的點2鄰近的點都不是密集度高的點。

這樣就把鄰近點的密集度也考慮進來了，這就像“從許多優質的頁面鏈接過來的頁面，必定還是優質的頁面。”這句話所說的那樣，而在這里就是“與許多密集度高的點鄰近的點，必定也是密集度高的點”。

(3)由特征向量的圖(如圖2所示)可以看出，有許多的 “波谷”，這些點都是特征向量值小的點，當然，“波谷”凹的程度也有大小，這樣，就能通過選擇一個尺度來找不同的孤立點，當選一個大尺度的時候，孤立點就少一些，反之，孤立點則多一些。

本文首先簡略介紹了PageRank算法的思想，其在Google上的成功應用證明這種算法是高效的；再由網頁與二維平面上的點的相似性到把該算法應用在孤立點檢測上，當然在具體算法上，要稍加改變，例如用什么方法來確定兩點間是否有“鏈接”等。文中還給出了一個實驗結果和分析，圖中共有156個點，當然這在實際應用中是不夠的，這里不過只是為了說明PageRank算法能在孤立點檢測上運用而已。

[1]蔡利棟，傅瑜.穩健的孤立點檢測——從中位數求方差[J].計算機科學，2006，33(8)(增刊)：185.

[2]范結.數據挖掘中孤立點檢測算法的研究[D].長沙：中南大學計算機應用技術,2009.

[3]陸聲鏈，林士敏.基于聚類的孤立點檢測及其應用[D].桂林：廣西師范大學數學與計算機科學學院，2003.

[4]Hajime BABA.Ph.D.Google的秘密——PageRank的徹底解說(2004-02-24)[2010-03-20].http://www.kreny.com/pager-ank_cn.htm.

[5]PAGE L,SERGEY B,RAJEEV M,et al.The PageRank citation ranking bringing order to the Web[D].Technical Report.Stanford：Univ.of Stanford InfoLab.1998.

[6]HAVELIWALA T H.Efficent computation of PageRank technical report.Technical Report[D].Univ.of Stanford Info-Lab,1999.