摘   要: 簡略介紹了PageRank算法，給出其在孤立點(diǎn)檢測(cè)應(yīng)用中的算法及實(shí)驗(yàn)結(jié)果和分析，最后將該算法與其他算法進(jìn)行比較。結(jié)果證明，該方法能較準(zhǔn)確地檢測(cè)到孤立點(diǎn)，并能適應(yīng)各種圖形。
關(guān)鍵詞: PageRank; 算法; 孤立點(diǎn)檢測(cè)

    在數(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(頁面分級(jí))算法是PAGE L和BRIN S在就讀斯坦福大學(xué)研究生院時(shí)研發(fā)出來的,他們后來創(chuàng)建了著名的Google公司，現(xiàn)在分別擔(dān)任該公司的CEO和總經(jīng)理。而PageRank算法就是Google搜索服務(wù)的一個(gè)核心技術(shù)。事實(shí)證明該算法在搜索服務(wù)上是非常成功的。
    頁面分級(jí)的思想與在二維平面上作孤立點(diǎn)檢測(cè)的思想非常相近,于是本文把PageRank算法運(yùn)用到孤立點(diǎn)檢測(cè)中，并給出實(shí)驗(yàn)結(jié)果和本文算法與其他的主流算法的比較。
1 PageRank算法
1.1 PageRank算法的核心思想
    對(duì)于世界上眾多的網(wǎng)頁，這些網(wǎng)頁有的十分重要，而有的重要性十分輕微。當(dāng)想要快速地在這么多的網(wǎng)頁中找到想要的網(wǎng)頁時(shí)，無論想查關(guān)于哪一方面的信息，都會(huì)希望別人給出的查找結(jié)果是那些重要的網(wǎng)頁，而不是微乎其微的網(wǎng)頁。所以在查找之前就應(yīng)該把網(wǎng)頁(或者稱為頁面)進(jìn)行重要性排序。用什么來衡量一個(gè)頁面的重要性呢？計(jì)算機(jī)能否由頁面的內(nèi)容來判斷頁面的重要性呢？答案是不能，計(jì)算機(jī)還沒先進(jìn)到這個(gè)程度。但PageRank算法給出了一個(gè)行之有效的思想：從許多優(yōu)質(zhì)的頁面鏈接過來的頁面，必定還是優(yōu)質(zhì)的頁面[5]。這一思想容易理解，如果有很多的頁面鏈接到A頁面，那么就認(rèn)為A頁面是比較重要的，那如果B頁面被A頁面鏈接(反過來說也就是A頁面鏈出到B頁面），因?yàn)锳頁面被一個(gè)認(rèn)為重要的頁面鏈接，所以也就把B頁面的重要性作一個(gè)大幅度的提高，認(rèn)為B頁面也是重要的。通過互聯(lián)網(wǎng)中頁面間本身就存在的鏈接，是容易算得頁面的重要性的。
    但另一方面，有些頁面為了提高重要性，相互間做一種商業(yè)上的鏈接，為了杜絕這一種情況，PageRank在計(jì)算頁面重要性的時(shí)候，對(duì)于鏈接進(jìn)來的頁面也是要考慮其重要性的，即重要性高的頁面鏈接進(jìn)來，則對(duì)當(dāng)前頁面重要性的提高有很大幫助；重要性低的頁面鏈接進(jìn)來，則對(duì)當(dāng)前頁面重要性的提高幫助很小。
1.2  PageRank算法的簡略步驟
    假設(shè)有N個(gè)頁面，這些頁面間有相互鏈接。
    (1) 制作一個(gè)N×N的矩陣S，如果頁面a鏈出到頁面b，則S(a,b)=1；
    (2) 將矩陣S轉(zhuǎn)置，得到矩陣S′，因?yàn)檫@里關(guān)心的不是該頁面鏈出到多少其他的頁面，而是有多少其他的頁面鏈進(jìn)來當(dāng)前頁面；
    (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è)頁面對(duì)應(yīng)的重要性的度量值，稱為PageRank值。
2 PageRank算法在孤立點(diǎn)檢測(cè)中的應(yīng)用
2.1 應(yīng)用思想
    把各個(gè)不同的頁面看成是二維平面上的點(diǎn)，按孤立點(diǎn)檢測(cè)的定義，也就找出了那些離群的點(diǎn)，即這個(gè)點(diǎn)周圍的其他點(diǎn)很稀疏。
    有必要把點(diǎn)按密度值進(jìn)行排列,在這里，點(diǎn)的密度值就對(duì)應(yīng)于頁面的PageRank值，即重要性。當(dāng)一個(gè)點(diǎn)所處位置的一定范圍內(nèi)出現(xiàn)的其他點(diǎn)越多，則這個(gè)點(diǎn)的密度值就越大，反之則越小。
    是否基于密度的聚類分析就可以解決這個(gè)問題了呢？可是基于密度聚類分析算法最終得出的結(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í)，就說明點(diǎn)a與出現(xiàn)在這個(gè)圓的其他點(diǎn)是有鏈接的，即對(duì)應(yīng)于頁面a鏈接到其他的頁面。接下來的操作就與頁面分級(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è)頁面對(duì)應(yīng)的重要性的度量值，稱為PageRank值;
    (7) 把PageRank值排列,再利用穩(wěn)健的孤立點(diǎn)檢測(cè)方法把孤立點(diǎn)檢測(cè)出來。
3 實(shí)驗(yàn)以及分析
    該實(shí)驗(yàn)是在Matlab環(huán)境下實(shí)現(xiàn)的。點(diǎn)群如圖1所示。

    從圖1可以看到，共有156個(gè)點(diǎn)，點(diǎn)的分布類型有逼近高斯分布（左邊用箭頭指的兩個(gè)），有均勻分布（右邊圈起來的）和其他的不規(guī)則矢量分布（右邊剩下的上下兩個(gè)）。把PageRank值算出來，并標(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所示。
    這5個(gè)點(diǎn)的位置如圖3所示。

    可以看到這5個(gè)點(diǎn)明顯都是孤立點(diǎn)，其他的孤立點(diǎn)也可以由同樣的方法找出，這里就不一一找出來了。值得注意的是，這幅點(diǎn)群中的分布情況是多種的，但PageRank算法都能很好地把孤立點(diǎn)找出來。
4 實(shí)驗(yàn)結(jié)果比較
    與其他的孤立點(diǎn)檢測(cè)算法相比較，PageRank算法有如下優(yōu)點(diǎn)：
    (1)與基于密度的檢測(cè)方法相比較，它不受給定的半徑影響。
    因?yàn)樵谠撍惴ㄖ?，半徑的確定只是為了判斷該點(diǎn)與其他點(diǎn)是否有“鏈接”而已，就像判斷各個(gè)頁面之間是否有鏈接，而處于稀疏群的點(diǎn)與處于密集群的點(diǎn)，無論半徑畫得大小，只要畫得不要太離譜，那處于密集群里的點(diǎn)與其他點(diǎn)的鏈接數(shù)肯定要比處于稀疏群里的點(diǎn)與其他點(diǎn)的鏈接數(shù)多，而最后是根據(jù)鏈接數(shù)的比重來排序的，也就是說半徑的大小不影響排序的位置，當(dāng)然對(duì)檢測(cè)也就沒什么影響了。
    (2) 考慮如圖4所示的這幅圖，當(dāng)用同樣的半徑去畫圓時(shí)，圓1里的點(diǎn)只有3個(gè)，圓2中的點(diǎn)有4個(gè)，但能說左邊箭頭所指的點(diǎn)是孤立點(diǎn)而右邊箭頭所指的點(diǎn)不是孤立點(diǎn)嗎？

    顯然，從整幅圖來看，左邊的是一個(gè)群體，而右邊的4個(gè)點(diǎn)才是孤立點(diǎn)，或者說是一小群孤立點(diǎn)。其原因就在于與左邊的點(diǎn)1鄰近的點(diǎn)都是密集度高的點(diǎn)，即它背后有一整個(gè)群體做支持，而與右邊的點(diǎn)2鄰近的點(diǎn)都不是密集度高的點(diǎn)。
    這樣就把鄰近點(diǎn)的密集度也考慮進(jìn)來了，這就像“從許多優(yōu)質(zhì)的頁面鏈接過來的頁面，必定還是優(yōu)質(zhì)的頁面。”這句話所說的那樣，而在這里就是“與許多密集度高的點(diǎn)鄰近的點(diǎn)，必定也是密集度高的點(diǎn)”。
    (3) 由特征向量的圖(如圖2所示)可以看出，有許多的“波谷”，這些點(diǎn)都是特征向量值小的點(diǎn)，當(dāng)然，“波谷”凹的程度也有大小，這樣，就能通過選擇一個(gè)尺度來找不同的孤立點(diǎn)，當(dāng)選一個(gè)大尺度的時(shí)候，孤立點(diǎn)就少一些，反之，孤立點(diǎn)則多一些。
    本文首先簡略介紹了PageRank算法的思想，其在Google上的成功應(yīng)用證明這種算法是高效的；再由網(wǎng)頁與二維平面上的點(diǎn)的相似性到把該算法應(yīng)用在孤立點(diǎn)檢測(cè)上，當(dāng)然在具體算法上，要稍加改變，例如用什么方法來確定兩點(diǎn)間是否有“鏈接”等。文中還給出了一個(gè)實(shí)驗(yàn)結(jié)果和分析，圖中共有156個(gè)點(diǎn)，當(dāng)然這在實(shí)際應(yīng)用中是不夠的，這里不過只是為了說明PageRank算法能在孤立點(diǎn)檢測(cè)上運(yùn)用而已。
參考文獻(xiàn)
[1] 蔡利棟，傅瑜. 穩(wěn)健的孤立點(diǎn)檢測(cè)——從中位數(shù)求方差[J].計(jì)算機(jī)科學(xué)，2006，33(8)(增刊)：185.
[2] 范結(jié). 數(shù)據(jù)挖掘中孤立點(diǎn)檢測(cè)算法的研究[D]. 長沙：中南大學(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的徹底解說(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.