在安全領(lǐng)域,“圖分析”廣泛應(yīng)用在賬戶交易異常、不同事件關(guān)聯(lián)等各種場(chǎng)景下。與其他機(jī)器學(xué)習(xí)算法類比較, 其特有的優(yōu)點(diǎn)在于分析方法符合人的思維方式,分析過(guò)程能直觀地可視化。
舉例來(lái)說(shuō),下圖是把瀚思某客戶企業(yè)中幾類安全事件 : 登陸、使用USB盤、檢測(cè)到病毒、機(jī)器IP、 用戶使用機(jī)器 - 綜合到一起做關(guān)聯(lián)分析。
圖中“邊”代表發(fā)生過(guò)事件;點(diǎn)(機(jī)器、用戶、IP、病毒、USB盤五類之一) 的大小代表事件多少。一張圖上我們可以快速定位爆發(fā)次數(shù)最多的病毒、哪些用戶違規(guī)使用同臺(tái)機(jī)器、哪些機(jī)器使用過(guò)同一個(gè)USB盤。
下圖是另一類例子,瀚思幫銀行客戶做的交易異常分析:點(diǎn)大小與出度成正比, 顏色隨著入度大小按藍(lán)色⇒白色⇒紅色方向變化。用金融術(shù)語(yǔ)來(lái)說(shuō):出度過(guò)大的叫火山,入度過(guò)大的叫黑洞。這類情況往往和詐騙洗錢相關(guān)。
但是,圖一旦變大,分析過(guò)程會(huì)變慢,需要分析的邊數(shù)量,即使最壞不會(huì)到全連通有向圖中等于節(jié)點(diǎn)數(shù)N的N*(N-1)/2, 也往往遠(yuǎn)大于N。而且可視化因?yàn)槠聊淮笮『鸵鬃x性的限制,不宜再把成千上萬(wàn)個(gè)節(jié)點(diǎn)和對(duì)應(yīng)的邊放到一張圖上。
這種情況下,我們采用分而治之策略:利用實(shí)際經(jīng)驗(yàn)中圖的社區(qū)性特征,把圖分割成若干個(gè)強(qiáng)聯(lián)通的區(qū)域, 對(duì)每一個(gè)區(qū)域做分析和可視化。
好的圖劃分算法在實(shí)際應(yīng)用中要額外有三個(gè)特征:
1、高速度,最好能并行化或者能用GPU加速。
2、能處理小世界網(wǎng)絡(luò)特征(也就是節(jié)點(diǎn)度數(shù)呈肥尾分布)。
3、對(duì)參數(shù)不敏感。
很多算法無(wú)法滿足2和3,教科書中算法大多是把圖均分,而且假設(shè)知道圖要分為多少類。
根據(jù)前文所述,瀚思利用“圖計(jì)算”在實(shí)際應(yīng)用中,幫助客戶解決了有關(guān)異常行為檢測(cè)的工作。而本文將重點(diǎn)針對(duì)三類應(yīng)用廣泛、效率較高并可以應(yīng)用于異常檢測(cè)的圖劃分算法進(jìn)行詳述。
譜劃分
譜劃分算法:它是最早用于解決圖劃分的一類算法,其思想來(lái)源于譜圖劃分理論。 矩陣的譜就是它的特征值和特征向量。 求圖劃分準(zhǔn)則的最優(yōu)解是一個(gè)NP難問(wèn)題。 一個(gè)很好的求解方法是考慮問(wèn)題的連續(xù)松弛形式,將原問(wèn)題轉(zhuǎn)換成求解Laplacian 矩陣的譜分解, 因此將這類方法統(tǒng)稱為譜劃分。
假定將每個(gè)數(shù)據(jù)樣本看作圖中的頂點(diǎn)V,根據(jù)樣本間的相似度將 頂點(diǎn)間的邊 E 賦權(quán)重值,便可得到一個(gè)基于相似度的無(wú)向加權(quán)圖 G=(V,E). 相似矩陣通常用 W 或 A 表示,有時(shí)也稱為親和矩陣(Affinity Matrix), 往往是通過(guò)計(jì)算高斯核得到。
將相似度矩陣的每行元素相加,即得到對(duì)應(yīng)點(diǎn)的度,以所有度值為對(duì)角元素構(gòu)成的對(duì)角矩陣稱為度矩陣,通常記為 D。定義好相似矩陣W及度矩陣D,便可得如下的 Laplacian 矩陣:L=D – W
根據(jù)不同的準(zhǔn)則函數(shù)及譜映射方法,譜劃分算法發(fā)展了很多不同的具體實(shí)現(xiàn)方法,但都可以歸納為下面的三個(gè)主要步驟:
對(duì)于給定的圖G=(V,E),計(jì)算圖的 Laplacian 矩陣L;
對(duì)L矩陣進(jìn)行特征值分解,取其前 k 個(gè)特征值對(duì)應(yīng)的特征向量,構(gòu)建特征向量矩陣Q;
利用K-means算法或其他經(jīng)典聚類算法對(duì)矩陣Q進(jìn)行劃分,每一行代表一個(gè)樣本點(diǎn), 即原圖的頂點(diǎn)所屬的類別.
上述步驟只是譜劃分的一個(gè)框架,在具體實(shí)現(xiàn)中,還存在著不同的劃分準(zhǔn)則,常見的有 Minimum Cut,Ratio Cut,Normalized Cut等。
譜劃分算法,首先通過(guò)引入 Laplacian 矩陣,運(yùn)用 Laplacian Eigenmap 進(jìn)行降維,再對(duì)這些 低維數(shù)據(jù)利用聚類算法進(jìn)行劃分,使得運(yùn)算量大大較少.下圖是用譜劃分算法實(shí)現(xiàn)的效果圖:
但譜劃分算法也有一些不足之處:
1)構(gòu)建特征向量矩陣Q無(wú)疑是該算法中最耗時(shí)間的, 在高維情況下, 不說(shuō)求解特征向量就是求解特征值都非常困難;
2)需要借助先驗(yàn)知識(shí)定義遞歸終止條件,即不具備智能識(shí)別圖類別總數(shù)的能力;
3)現(xiàn)實(shí)世界中的復(fù)雜網(wǎng)絡(luò)圖往往包含多個(gè)類,而遞歸的二分策略不能保證得到的劃分是最優(yōu)的劃分。
多層劃分算法
第二類圖劃分算法,稱為*多層劃分(Multilevel Partitioning,1995,Karypis)*。
以高效及運(yùn)算時(shí)間快著稱,比譜劃分算法快10%-50%, 計(jì)算千萬(wàn)數(shù)級(jí)的圖,時(shí)間基本是以秒計(jì)算。其主要實(shí)現(xiàn)步驟通常分為圖的 粗化階段(Coarsening phase), 初始劃分階段(Initial partitioning phase)和細(xì)化階段 (Uncoarsening phase)三個(gè)階段。
簡(jiǎn)言之,如下圖所示,該算法就是將原始圖經(jīng)粗化階段一層一層壓縮變“小”,得到頂點(diǎn)數(shù)目足夠小的圖, 再將這個(gè)數(shù)目足夠小的圖經(jīng)過(guò)初始劃分階段和細(xì)化階段一層一層還原變“大”,直到還原成原始圖,完成劃分。
粗化階段主要是為了減少原始圖的復(fù)雜性,構(gòu)建圖的多級(jí)層次. 它對(duì)原始圖的點(diǎn)和邊進(jìn)行壓縮合并, 構(gòu)造了一個(gè)層次化的較小的圖序列, 最終將原始圖壓縮成一個(gè)頂點(diǎn)數(shù)目足夠小的圖。 這種壓縮的思想(詳見下圖)可以形式化地定義為匹配 (Matching),圖的匹配是指 邊的集合,其中任意兩條邊都沒(méi)有公共頂點(diǎn)。 在一個(gè)圖的所有匹配中,所含匹配邊數(shù)最多的匹配,稱為這個(gè)圖的最大匹配.
在整個(gè)粗化階段,原始圖的所有點(diǎn)以及權(quán)重都會(huì)累計(jì),最終反應(yīng)在最小規(guī)模圖。 將最小規(guī)模圖進(jìn)行簡(jiǎn)單的劃分,稱為初始劃分階段,該階段由于結(jié)點(diǎn)數(shù)目較少,運(yùn)算非???,基本不耗時(shí)。 也不是多層算法的核心部分,其算法與接下來(lái)的細(xì)化階段算法聯(lián)系比較相似,這里不再贅述.
細(xì)化階段,也可稱為圖的還原優(yōu)化階段,該階段按照粗化層次一層一層將圖還原成原始圖,并在還原過(guò)程中 利用某些精細(xì)的算法逐層優(yōu)化,直到得到對(duì)原始圖的劃分.
這其中的常見的劃分算法有譜二分法算法有Spectral Bisection(SB),Graph Growing Algorithm(GGP), Greedy Refinement(GR), Kernighan-Lin Refinement(KLR)等, 其中比較著名的是Kernighan-Lin劃分算法。
*Kernighan-Lin劃分算法*,簡(jiǎn)稱KL算法,由Kernighan和Lin在1970年提出,是一個(gè)局部搜索優(yōu)化算法, 優(yōu)化的目標(biāo)函數(shù)是連接不同類的邊權(quán)之和最小。
舉個(gè)簡(jiǎn)單的例子,如下圖,紫色的點(diǎn)屬于一類,黑色的點(diǎn)屬于一類,KL算法是實(shí)現(xiàn)將下圖(a)轉(zhuǎn)換成下圖(b)的過(guò)程。
如何實(shí)現(xiàn)將紫色類別中的點(diǎn)和黑色類別中的點(diǎn)進(jìn)行交換,則是通過(guò)計(jì)算不同類別損失權(quán)重的差值來(lái)判斷的, 即交換前的內(nèi)外權(quán)重差(如下圖(a)的數(shù)字所示)減去交換后的內(nèi)外權(quán)重的值。當(dāng)且僅當(dāng)該值為正進(jìn)行交換,否則拒絕交換。 重復(fù)以上步驟,直至該值為負(fù)。
KL算法,較易理解,但得到的解往往是局部最優(yōu)。下圖,是利用多層劃分算法進(jìn)行圖劃分的例子:
多層劃分算法最大的局限在于它最大的局限性在于需要先驗(yàn)知識(shí)來(lái)產(chǎn)生一個(gè)較好的初始類。
MCL
最后談?wù)?,Markov Cluster Algorithm(2000, Stijn van Dongen), 簡(jiǎn)稱MCL算法,是一種快速可擴(kuò)展的 無(wú)監(jiān)督圖形聚類算法,有時(shí)也可以用于圖的劃分,其思想非常簡(jiǎn)單,主要是基于 隨機(jī)游走(Random walk) 和馬爾科夫鏈 (Markov chain)。 先簡(jiǎn)單說(shuō)一下這兩個(gè)概念.
隨機(jī)游走說(shuō)的是,如果我們從圖中的某一個(gè)點(diǎn)開始“瞎轉(zhuǎn)”,那么很可能就會(huì)在某一個(gè)子圖里面轉(zhuǎn)悠,而不是在子圖間來(lái)回游蕩. 而隨機(jī)游走的計(jì)算是通過(guò) Markov鏈來(lái)實(shí)現(xiàn)的. Markov鏈指的是一個(gè)隨機(jī)序列,該序列滿足“無(wú)后效性”,即 將來(lái)的狀態(tài)只依賴當(dāng)前狀態(tài),而與過(guò)去的狀態(tài)無(wú)關(guān)。
MCL算法的關(guān)鍵思想就是:”隨機(jī)漫游者抵達(dá)稠密的類后,不會(huì)輕易的離開該類”. 前者是隨機(jī)游走的過(guò)程,后者依據(jù)是 Markov鏈的“無(wú)后效性”。 MCL算法中隨機(jī)漫游的過(guò)程,其實(shí)是一個(gè)不斷修改轉(zhuǎn)移概率矩陣的過(guò)程,該過(guò)程 重復(fù)執(zhí)行擴(kuò)展(Expansion)和膨脹(Inflation)兩個(gè)操作。
擴(kuò)展就是前面提到的馬爾科夫鏈的轉(zhuǎn)移矩陣的極限分布, 這個(gè)步驟不斷地對(duì)轉(zhuǎn)移概率矩陣進(jìn)行自乘直到它不再改變?yōu)橹埂?目的是連接圖的不同區(qū)域。膨脹是對(duì)每一個(gè)元素進(jìn)行冪操作,再將每一列歸一化,目的是為了強(qiáng)鄰居的連接更強(qiáng), 弱鄰居的連接更弱,也就是讓轉(zhuǎn)移矩陣中概率大的概率更大,而小的更小。 這兩個(gè)操作重復(fù)執(zhí)行一直到概率轉(zhuǎn)移矩陣收斂為止,得到最終的矩陣,根據(jù)最終的矩陣便可得結(jié)果。
MCL算法對(duì)無(wú)權(quán)圖及有權(quán)圖均試用,劃分的子圖個(gè)數(shù)無(wú)需事先設(shè)定,這是該算法的 最大優(yōu)勢(shì); 劃分的子圖是非均勻的,試用于長(zhǎng)尾分布的數(shù)據(jù)。 下圖就是利用 MCL 進(jìn)行圖劃分的結(jié)果:
但是MCL算法對(duì)圖的直徑較大的情況不適用。(直徑是指兩個(gè)點(diǎn)之間的距離最大值,距離是兩個(gè)點(diǎn)之間的所有路的長(zhǎng)度的最小值)