陳 謙

(暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院計(jì)算機(jī)系，廣東 廣州 510632)

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

頁(yè)面分級(jí)的思想與在二維平面上作孤立點(diǎn)檢測(cè)的思想非常相近,于是本文把PageRank算法運(yùn)用到孤立點(diǎn)檢測(cè)中，并給出實(shí)驗(yàn)結(jié)果和本文算法與其他的主流算法的比較。

1 PageRank算法

1.1 PageRank算法的核心思想

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

但另一方面，有些頁(yè)面為了提高重要性，相互間做一種商業(yè)上的鏈接，為了杜絕這一種情況，PageRank在計(jì)算頁(yè)面重要性的時(shí)候，對(duì)于鏈接進(jìn)來(lái)的頁(yè)面也是要考慮其重要性的，即重要性高的頁(yè)面鏈接進(jìn)來(lái)，則對(duì)當(dāng)前頁(yè)面重要性的提高有很大幫助；重要性低的頁(yè)面鏈接進(jìn)來(lái)，則對(duì)當(dāng)前頁(yè)面重要性的提高幫助很小。

1.2 PageRank算法的簡(jiǎn)略步驟

假設(shè)有N 個(gè)頁(yè)面，這些頁(yè)面間有相互鏈接。

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

(2)將矩陣S轉(zhuǎn)置，得到矩陣S′，因?yàn)檫@里關(guān)心的不是該頁(yè)面鏈出到多少其他的頁(yè)面，而是有多少其他的頁(yè)面鏈進(jìn)來(lái)當(dāng)前頁(yè)面；

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

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

(5)找出最大特征值所對(duì)應(yīng)的特征向量，并把該特征向量標(biāo)準(zhǔn)化。標(biāo)準(zhǔn)化后的結(jié)果就是各個(gè)頁(yè)面對(duì)應(yīng)的重要性的度量值，稱為PageRank值。

2 PageRank算法在孤立點(diǎn)檢測(cè)中的應(yīng)用

2.1 應(yīng)用思想

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

有必要把點(diǎn)按密度值進(jìn)行排列,在這里，點(diǎn)的密度值就對(duì)應(yīng)于頁(yè)面的PageRank值，即重要性。當(dāng)一個(gè)點(diǎn)所處位置的一定范圍內(nèi)出現(xiàn)的其他點(diǎn)越多，則這個(gè)點(diǎn)的密度值就越大，反之則越小。

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

以點(diǎn)a為中心、r為半徑畫圓，當(dāng)出現(xiàn)在這個(gè)圓中其他點(diǎn)的數(shù)目達(dá)到一定量時(shí)，就說(shuō)明點(diǎn)a與出現(xiàn)在這個(gè)圓的其他點(diǎn)是有鏈接的，即對(duì)應(yīng)于頁(yè)面a鏈接到其他的頁(yè)面。接下來(lái)的操作就與頁(yè)面分級(jí)算法基本一樣了。

2.2 應(yīng)用步驟

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

(2)建造一個(gè) N×N的矩陣 S，選擇半徑 r，當(dāng) a、b兩點(diǎn)間的距離小于r時(shí)，S(a,b)=1；

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

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

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

(6)找出最大特征值所對(duì)應(yīng)的特征向量,并把該特征向量標(biāo)準(zhǔn)化。標(biāo)準(zhǔn)化后的結(jié)果就是各個(gè)頁(yè)面對(duì)應(yīng)的重要性的度量值，稱為PageRank值;

(7)把PageRank值排列,再利用穩(wěn)健的孤立點(diǎn)檢測(cè)方法把孤立點(diǎn)檢測(cè)出來(lái)。

3 實(shí)驗(yàn)以及分析

該實(shí)驗(yàn)是在Matlab環(huán)境下實(shí)現(xiàn)的。點(diǎn)群如圖1所示。

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

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

表1 所測(cè)孤立點(diǎn)的坐標(biāo)

這5個(gè)點(diǎn)的位置如圖3所示。

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

4 實(shí)驗(yàn)結(jié)果比較

與其他的孤立點(diǎn)檢測(cè)算法相比較，PageRank算法有如下優(yōu)點(diǎn)：

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

因?yàn)樵谠撍惴ㄖ校霃降拇_定只是為了判斷該點(diǎn)與其他點(diǎn)是否有“鏈接”而已，就像判斷各個(gè)頁(yè)面之間是否有鏈接，而處于稀疏群的點(diǎn)與處于密集群的點(diǎn)，無(wú)論半徑畫得大小，只要畫得不要太離譜，那處于密集群里的點(diǎn)與其他點(diǎn)的鏈接數(shù)肯定要比處于稀疏群里的點(diǎn)與其他點(diǎn)的鏈接數(shù)多，而最后是根據(jù)鏈接數(shù)的比重來(lái)排序的，也就是說(shuō)半徑的大小不影響排序的位置，當(dāng)然對(duì)檢測(cè)也就沒(méi)什么影響了。

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

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

這樣就把鄰近點(diǎn)的密集度也考慮進(jìn)來(lái)了，這就像“從許多優(yōu)質(zhì)的頁(yè)面鏈接過(guò)來(lái)的頁(yè)面，必定還是優(yōu)質(zhì)的頁(yè)面。”這句話所說(shuō)的那樣，而在這里就是“與許多密集度高的點(diǎn)鄰近的點(diǎn)，必定也是密集度高的點(diǎn)”。

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

本文首先簡(jiǎn)略介紹了PageRank算法的思想，其在Google上的成功應(yīng)用證明這種算法是高效的；再由網(wǎng)頁(yè)與二維平面上的點(diǎn)的相似性到把該算法應(yīng)用在孤立點(diǎn)檢測(cè)上，當(dāng)然在具體算法上，要稍加改變，例如用什么方法來(lái)確定兩點(diǎn)間是否有“鏈接”等。文中還給出了一個(gè)實(shí)驗(yàn)結(jié)果和分析，圖中共有156個(gè)點(diǎn)，當(dāng)然這在實(shí)際應(yīng)用中是不夠的，這里不過(guò)只是為了說(shuō)明PageRank算法能在孤立點(diǎn)檢測(cè)上運(yùn)用而已。

[1]蔡利棟，傅瑜.穩(wěn)健的孤立點(diǎn)檢測(cè)——從中位數(shù)求方差[J].計(jì)算機(jī)科學(xué)，2006，33(8)(增刊)：185.

[2]范結(jié).數(shù)據(jù)挖掘中孤立點(diǎn)檢測(cè)算法的研究[D].長(zhǎng)沙：中南大學(xué)計(jì)算機(jī)應(yīng)用技術(shù),2009.

[3]陸聲鏈，林士敏.基于聚類的孤立點(diǎn)檢測(cè)及其應(yīng)用[D].桂林：廣西師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，2003.

[4]Hajime BABA.Ph.D.Google的秘密——PageRank的徹底解說(shuō)(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.