基于分形理論的異質網(wǎng)絡中局部離群點檢測

蔣 斌，黃恩銘

(南京中醫(yī)藥大學，江蘇 南京 210023)

1 引言

隨著互聯(lián)網(wǎng)中發(fā)布信息量的增加，互聯(lián)網(wǎng)逐漸發(fā)展為全球最龐大的知識資源庫。異質網(wǎng)絡是現(xiàn)實世界的抽象代表，包含各類對象與鏈接，且存在很多區(qū)別于正常數(shù)據(jù)的局部離群點[1]。在整個異質網(wǎng)絡中，局部離群點雖然僅占一小部分，但蘊含很多重要信息，相對于采集正常數(shù)據(jù)中的信息，檢測出局部離群點中的隱藏信息具有更高的研究價值。目前，局部離群點檢測被廣泛應用于各個領域，對數(shù)據(jù)分析以及發(fā)展趨勢預測起著關鍵作用，例如在軍事領域，能對設備異常狀況進行分析；在安防領域，可預測極端天氣，從而為人們的生命以及財產(chǎn)安全提供保障；在工業(yè)領域，能用于檢測機器故障；在醫(yī)療領域，可對患者檢查結果內的異常指標進行判斷[2]。因此，研究異質網(wǎng)絡中局部離群點檢測方法意義十分重大。

許多相關專家學者都在該領域的研究中取得豐碩的成果，如彭濤[3]等人使用排序與聚類方法完成局部離群點檢測，該方法需對數(shù)據(jù)集執(zhí)行多次掃描，對增量與動態(tài)數(shù)據(jù)的處理能力較弱；牛少章[4]等人使用網(wǎng)絡查詢方法完成局部離群點檢測，該方法檢測用時較短，但內存使用狀況緊張。

分形理論以分形幾何學作為基礎，從分數(shù)維度視角出發(fā)，使用數(shù)學方法對客觀事物進行表示與分析，可描述客觀事物真實屬性及狀態(tài)能力，所得結果與研究對象的真實狀態(tài)及屬性非常接近。因此，本文提出基于分形理論的異質網(wǎng)絡中局部離群點檢測方法，通過分形理論將局部離群點檢測問題轉化為優(yōu)化分割問題，利用FDOM算法求得最優(yōu)解，實現(xiàn)局部離群點的精準、快速檢測。

2 基于分形理論的異質網(wǎng)絡中局部離群點檢測

2.1 基于Z-ordering的多重分形維數(shù)

通常利用一個分形維數(shù)，可以對淺顯分形集合的特征及復雜度進行較為精確的表示。利用多重分形維數(shù)表示復雜對象的層次及特征，是因為很多非線性因素在該對象形成過程中對其產(chǎn)生巨大影響，導致特征差異性顯著，無法只利用一個分形維數(shù)表示[5，6]。設置多重分形維數(shù)，用Dq描述，稱其為q次廣義維數(shù)，能夠用于表示多重分形(即復雜對象)。

2.1.1 廣義維數(shù)

數(shù)據(jù)點以概率形式分散于空間Rd中，假設劃分空間為d維超矩形，邊長為ε，各超矩形有數(shù)據(jù)點光臨的幾率用pi描述，次數(shù)q的信息量用Iq(ε)描述，q為正數(shù)，且不等于1，式(1)描述了Iq(ε)的定義

(1)

式內，超矩形的數(shù)量用M描述。在ε→0的情況下，多重分形維數(shù)定義用式(2)描述

(2)

式內，若要表明Dq為信息維數(shù)(D1)，則q的值等于1；若要表明Dq為容量維數(shù)(D0)，則q的值等于0；若要表明Dq為關聯(lián)維數(shù)(D2)，則q的值等于2。

2.1.2 多重分形

對數(shù)據(jù)集進行分割，使其變?yōu)镹個小區(qū)域，假定第i個小區(qū)域線度規(guī)模，用Li描述，分形體生長界面小區(qū)域的生長概率，用Pi描述，使用不一樣的標度指數(shù)αi描述生長概率，是因為不一樣的小區(qū)域生長概率具有差異[7]，Pi的計算過程用式(3)描述

(3)

如果是在Li→0的情況下，可以將式(3)轉化為式(4)所描述的形式

(4)

式內，在分形體中，任意小區(qū)域的分維用α描述。能夠獲得譜f(α)，它由包含不同α的無窮序列組成，因為小區(qū)域的規(guī)模非常龐大，所以α與f(α)是一套參量，可用于對多重分形進行表示。

將式(3)左右兩端分別乘q次方，再進行求和操作，可得到如式(5)所描述的表達式

(5)

通過式(6)描述基于式(2)得到的廣義維數(shù)定義

(6)

式內，利用q值的變化情況，能夠對包含不同αi的子集進行區(qū)分。通常利用分形譜Dq-q、f(α)-α表示多重分形，兩者之間的關聯(lián)用Legendre變換描述，如式(7)所示

(7)

根據(jù)式(7)可得，Dq可由α與f(α)求得。根據(jù)式(5)、(6)可以看出，在已知Pi的情況下也可以求得Dq，進而使用式(8)求出α

(8)

利用式(8)可在計算獲得Dq的條件下，求出α與f(α)。

2.1.3 基于Z-ordering的多重分形維數(shù)算法

利用尺度δ量度數(shù)據(jù)集F，即大多數(shù)分形維數(shù)定義的指導思想[8]。測量值Nδ(F)滿足的冪定律對F的維數(shù)具有決定作用，在δ趨于0的情況下，若常數(shù)c、s滿足式(9)所示表達式，那么F存在維數(shù)，F(xiàn)的δ-維長度用c描述。

Nδ(F)∝cδ-s

(9)

式(10)為對式(9)左右兩端取對數(shù)所獲得的表達式

lnNδ(F)?lnc-slnδ

(10)

式內，在δ不斷接近于0的條件下，兩側的差值逐漸趨于0，因此，可得到如式(11)描述的表達式

(11)

lnNδ(F)和lnδ的雙對數(shù)圖，可基于合適的δ區(qū)間繪制出來，通過圖中無標度區(qū)斜率，對維數(shù)s進行預估。

計算分形維數(shù)時，分割數(shù)據(jù)空間，使其轉化為邊長一致的網(wǎng)格，對網(wǎng)格內具有的數(shù)據(jù)點個數(shù)，以及總數(shù)比率進行合計，并統(tǒng)計其總和，對于邊長不一樣的網(wǎng)格結構均需重復執(zhí)行該過程。為減少內存空間占用，使用Z-ordering執(zhí)行最小網(wǎng)格的編碼處理，利用動態(tài)更新網(wǎng)格編碼，將底層網(wǎng)格映射至高層網(wǎng)格，并根據(jù)底層網(wǎng)格結構，對邊長不一樣的網(wǎng)格具有的數(shù)據(jù)點個數(shù)進行統(tǒng)計[9，10]。

2.2 分形局部離群點檢測優(yōu)化模型

各種實體與鏈接包含于異質網(wǎng)絡中，若使用向量形式描述全部實體，在執(zhí)行離群計算時難以獲得理想的計算效果，因此基于上述分形理論，對異質網(wǎng)絡中的實體進行處理，完成局部離群點檢測。

2.2.1 異質網(wǎng)絡定義

設置G=(V，E；τ，φ；A，R)，表示有向圖；節(jié)點集與邊集分別用V、E描述；關系類型映射函數(shù)，用φ描述；對象類型映射函數(shù)，用τ描述；各關系e∈E均隸屬某給定的關系類，用φ(e)∈R描述；各對象v∈V均隸屬某給定的對象類，用τ(v)∈A描述。節(jié)點類型個數(shù)用|A|描述，邊類型個數(shù)用|R|描述，若|A|的值大于1，或者|R|的值大于1，則此種網(wǎng)絡為異質網(wǎng)絡。

2.2.2 基于分形理論的局部離群點定義

設置數(shù)據(jù)集D，其分形維數(shù)用DIM(D，D)描述；該數(shù)據(jù)集將數(shù)據(jù)點p刪除后的分形維數(shù)，用DIM(D-p，D)描述。式(12)為p的離群程度表達式

(12)

式內，若要說明p具有局部離群點的幾率較高，OD(p，D)的值應越大。

設置數(shù)據(jù)子集Si，其離群程度用OD(Si，D)描述，若要表明Si中包含局部離群點，那么OD(Si，D)的值應大于1，若要表明局部離群點是d內的點，OD(Si-d，D)的值應最小。

2.2.3 局部離群點檢測優(yōu)化模型

根據(jù)2.2.2小節(jié)可得，局部離群點不同于數(shù)據(jù)集內的其它點，且與之差異性極大。出于對大部分數(shù)據(jù)集復雜度的考慮，將異質網(wǎng)絡中局部離群點檢測問題轉化為優(yōu)化分割問題[11]。

設置數(shù)據(jù)集D內屬性數(shù)量為M，該數(shù)據(jù)集的屬性集合用A={A1，A2，…，Ad}描述。Si?D表示隨機的子數(shù)據(jù)集，其分形維數(shù)用Dim(Si，D)描述，可用于對數(shù)據(jù)集進行分割求解。

如果數(shù)據(jù)集被分解成n個子數(shù)據(jù)集，那么可用式(13)描述優(yōu)化分割模型的表達式

[OD(S1-O，D)，OD(S2-O，D)，…，OD(Sn-O，D)]

(13)

式內，最佳局部離群點集合，用O描述，清除O內的點之后，該集合能夠最小化數(shù)據(jù)集在每個子集的離群程度。

2.3 基于FDOM算法的模型求解

根據(jù)貪婪算法的理念，提出FDOM算法對局部離群點檢測優(yōu)化模型進行求解。算法的輸入為數(shù)據(jù)集，將其內數(shù)據(jù)的初始類別設置完成后執(zhí)行該算法，進行數(shù)據(jù)集的遍歷，若需要修正某條數(shù)據(jù)類別，是在其修正后可使離群程度減小的條件下，完成修正后對下一條數(shù)據(jù)進行驗證，循環(huán)執(zhí)行該操作，停止條件為數(shù)據(jù)集中不包含需修正類別的數(shù)據(jù)，從而獲得最優(yōu)解以最小化離群程度。

數(shù)據(jù)集用D描述，其內數(shù)據(jù)點數(shù)量為N，各數(shù)據(jù)點屬性數(shù)量為M，可將其當作M維向量。將基礎數(shù)據(jù)保存于哈希表中，各哈希表的關鍵字為屬性值，其呈現(xiàn)次數(shù)為參考值。以下為FDOM算法求解模型的過程：

1)滿意的局部離群點數(shù)量用K描述，以K與數(shù)據(jù)集D作為算法輸入；

2)分割數(shù)據(jù)集D，將其轉化為S個子集；

3)通過各數(shù)據(jù)集內的數(shù)據(jù)點t，對哈希表進行初始化操作，將各數(shù)據(jù)點記作非離群點，用0描述；

4)如果未遍歷完整個子集，采集下一個子集的數(shù)據(jù)，并對該子集的離群程度進行計算，若結果大于1，將子集內的數(shù)據(jù)清除，停止條件為得到該子集最小的離群程度，將符合該條件時清除的數(shù)據(jù)點作為局部離群點，用1描述；

5)重復執(zhí)行步驟4)，停止條件為檢測到的局部離群點數(shù)量為K；

6)將檢測到的K個局部離群點數(shù)據(jù)輸出。

3 結果分析

將AMiner與Movie dataset兩個真實異質網(wǎng)絡數(shù)據(jù)集作為實驗對象，利用本文方法檢測其內局部離群點，以驗證該方法的檢測性能，兩個數(shù)據(jù)集所含數(shù)據(jù)類別及局部離群點數(shù)量詳情分別用表1、表2描述。

表1 AMiner異質網(wǎng)絡數(shù)據(jù)集詳情

表2 Movie dataset異質網(wǎng)絡數(shù)據(jù)集詳情

檢測AMiner異質網(wǎng)絡數(shù)據(jù)集中局部離群點，將離群程度最大的m個局部離群點中，稀有類數(shù)據(jù)占全部稀有類數(shù)據(jù)的比重當作評價指標，占比越高，方法的檢測性能越優(yōu)異。設計對比實驗，選擇文獻[3]的排序聚類檢測方法與文獻[4]的網(wǎng)格查詢檢測方法作為本文方法的對比方法，在不同局部離群點數(shù)量下，三種方法的局部離群點中稀有類數(shù)據(jù)的占比情況用圖1描述。

分析圖1可以看出，隨著局部離群點數(shù)量的增加，三種方法檢測出的局部離群點中，存在的稀有類數(shù)據(jù)均呈上升趨勢。相對于其它兩種方法，本文方法的稀有類占比始終保持最高，且上升速率較快，當局部離群點數(shù)量增加至100時，稀有類占比高達95%；當局部離群點數(shù)量小于60時，排序聚類檢測方法的稀有類占比相對較高；當局部離群點數(shù)量大于50時，網(wǎng)格查詢檢測方法的稀有類占比上升速率加快，且超過排序聚類檢測方法的稀有類占比。對比這些數(shù)據(jù)可得，本文方法的異質網(wǎng)絡中局部離群點檢測效果最佳。

圖1 AMiner異質網(wǎng)絡數(shù)據(jù)集檢測結果

使用F-Measure評價指標(召回率及精確率的調和平均數(shù))，進一步驗證異質網(wǎng)絡中局部離群點檢測能力，該指標的值越高，方法的檢測能力越強，以Movie dataset異質網(wǎng)絡數(shù)據(jù)集作為測試對象，在不同數(shù)據(jù)類別下，三種方法的F-Measure結果用圖2描述。

分析圖2可得，本文方法檢測不同數(shù)據(jù)類別中局部離群點所得的F-Measure值始終高于0.9，檢測結果十分穩(wěn)定；排序聚類檢測方法的F-Measure值與本文方法的F-Measure值較為接近，無明顯起伏，最大F-Measure值接近0.9；網(wǎng)格查詢檢測方法的F-Measure值在0.4-0.8區(qū)間內起伏劇烈，最大F-Measure與最小F-Measure之間的差值較大，檢測結果穩(wěn)定性較差。對比這些數(shù)據(jù)可以說明，本文方法對于異質網(wǎng)絡中不同數(shù)據(jù)類別的局部離群點檢測都能獲得理想的檢測效果。

圖2 三種方法的F-Measure結果

4 結論

異質網(wǎng)絡中局部離群點檢測是從大量數(shù)據(jù)集中獲取少量隱藏信息的過程，本文在分形理論的基礎上，將局部離群點檢測問題轉化為優(yōu)化分割問題，基于貪婪算法的思想設計FDOM算法求得最優(yōu)解，實現(xiàn)異質網(wǎng)絡中局部離群點檢測。該方法的實際應用不僅對安防、醫(yī)療等領域的網(wǎng)絡化發(fā)展具有重要意義，還能極大地促進社會經(jīng)濟的發(fā)展，日后可進一步完善該研究方法，使其更好地為國家服務。