在安全領(lǐng)域，“圖分析”廣泛應(yīng)用在賬戶交易異常、不同事件關(guān)聯(lián)等各種場(chǎng)景下。與其他機(jī)器學(xué)習(xí)算法類比較，其特有的優(yōu)點(diǎn)在于分析方法符合人的思維方式，分析過程能直觀地可視化。
舉例來說，下圖是把瀚思某客戶企業(yè)中幾類安全事件：登陸、使用USB盤、檢測(cè)到病毒、機(jī)器IP、用戶使用機(jī)器-綜合到一起做關(guān)聯(lián)分析。
圖中“邊”代表發(fā)生過事件;點(diǎn)(機(jī)器、用戶、IP、病毒、USB盤五類之一)的大小代表事件多少。一張圖上我們可以快速定位爆發(fā)次數(shù)最多的病毒、哪些用戶違規(guī)使用同臺(tái)機(jī)器、哪些機(jī)器使用過同一個(gè)USB盤。
下圖是另一類例子，瀚思幫銀行客戶做的交易異常分析：點(diǎn)大小與出度成正比，顏色隨著入度大小按藍(lán)色⇒白色⇒紅色方向變化。用金融術(shù)語(yǔ)來說：出度過大的叫火山，入度過大的叫黑洞。這類情況往往和詐騙洗錢相關(guān)。
但是，圖一旦變大，分析過程會(huì)變慢，需要分析的邊數(shù)量，即使最壞不會(huì)到全連通有向圖中等于節(jié)點(diǎn)數(shù)N的N*(N-1)/2，也往往遠(yuǎn)大于N。而且可視化因?yàn)槠聊淮笮『鸵鬃x性的限制，不宜再把成千上萬個(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ù)不敏感。
很多算法無法滿足2和3，教科書中算法大多是把圖均分，而且假設(shè)知道圖要分為多少類。
根據(jù)前文所述，瀚思利用“圖計(jì)算”在實(shí)際應(yīng)用中，幫助客戶解決了有關(guān)異常行為檢測(cè)的工作。而本文將重點(diǎn)針對(duì)三類應(yīng)用廣泛、效率較高并可以應(yīng)用于異常檢測(cè)的圖劃分算法進(jìn)行詳述。
譜劃分
譜劃分算法：它是最早用于解決圖劃分的一類算法，其思想來源于譜圖劃分理論。矩陣的譜就是它的特征值和特征向量。求圖劃分準(zhǔn)則的最優(yōu)解是一個(gè)NP難問題。一個(gè)很好的求解方法是考慮問題的連續(xù)松弛形式，將原問題轉(zhuǎn)換成求解Laplacian矩陣的譜分解，因此將這類方法統(tǒng)稱為譜劃分。
假定將每個(gè)數(shù)據(jù)樣本看作圖中的頂點(diǎn)V，根據(jù)樣本間的相似度將頂點(diǎn)間的邊E賦權(quán)重值，便可得到一個(gè)基于相似度的無向加權(quán)圖G=(V,E).相似矩陣通常用W或A表示，有時(shí)也稱為親和矩陣(AffinityMatrix)，往往是通過計(jì)算高斯核得到。
將相似度矩陣的每行元素相加，即得到對(duì)應(yīng)點(diǎn)的度，以所有度值為對(duì)角元素構(gòu)成的對(duì)角矩陣稱為度矩陣，通常記為D。定義好相似矩陣W及度矩陣D，便可得如下的Laplacian矩陣：
根據(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)則，常見的有MinimumCut，RatioCut，NormalizedCut等。
譜劃分算法，首先通過引入Laplacian矩陣，運(yùn)用LaplacianEigenmap進(jìn)行降維，再對(duì)這些低維數(shù)據(jù)利用聚類算法進(jìn)行劃分，使得運(yùn)算量大大較少.下圖是用譜劃分算法實(shí)現(xiàn)的效果圖：
但譜劃分算法也有一些不足之處：
1)構(gòu)建特征向量矩陣Q無疑是該算法中最耗時(shí)間的，在高維情況下,不說求解特征向量就是求解特征值都非常困難;
2)需要借助先驗(yàn)知識(shí)定義遞歸終止條件，即不具備智能識(shí)別圖類別總數(shù)的能力;
3)現(xiàn)實(shí)世界中的復(fù)雜網(wǎng)絡(luò)圖往往包含多個(gè)類，而遞歸的二分策略不能保證得到的劃分是最優(yōu)的劃分。
多層劃分算法
第二類圖劃分算法，稱為*多層劃分(MultilevelPartitioning，1995，Karypis)*。
以高效及運(yùn)算時(shí)間快著稱，比譜劃分算法快10%-50%，計(jì)算千萬數(shù)級(jí)的圖，時(shí)間基本是以秒計(jì)算。其主要實(shí)現(xiàn)步驟通常分為圖的粗化階段(Coarseningphase),初始劃分階段(Initialpartitioningphase)和細(xì)化階段(Uncoarseningphase)三個(gè)階段。
簡(jiǎn)言之，如下圖所示，該算法就是將原始圖經(jīng)粗化階段一層一層壓縮變“小”，得到頂點(diǎn)數(shù)目足夠小的圖，再將這個(gè)數(shù)目足夠小的圖經(jīng)過初始劃分階段和細(xì)化階段一層一層還原變“大”，直到還原成原始圖，完成劃分。
粗化階段主要是為了減少原始圖的復(fù)雜性，構(gòu)建圖的多級(jí)層次.它對(duì)原始圖的點(diǎn)和邊進(jìn)行壓縮合并，構(gòu)造了一個(gè)層次化的較小的圖序列,最終將原始圖壓縮成一個(gè)頂點(diǎn)數(shù)目足夠小的圖。這種壓縮的思想(詳見下圖)可以形式化地定義為匹配(Matching)，圖的匹配是指邊的集合，其中任意兩條邊都沒有公共頂點(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í)。也不是多層算法的核心部分，其算法與接下來的細(xì)化階段算法聯(lián)系比較相似，這里不再贅述.
細(xì)化階段，也可稱為圖的還原優(yōu)化階段，該階段按照粗化層次一層一層將圖還原成原始圖，并在還原過程中利用某些精細(xì)的算法逐層優(yōu)化，直到得到對(duì)原始圖的劃分.
這其中的常見的劃分算法有譜二分法算法有SpectralBisection(SB)，GraphGrowingAlgorithm(GGP),GreedyRefinement(GR)，Kernighan-LinRefinement(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)的過程。
如何實(shí)現(xiàn)將紫色類別中的點(diǎn)和黑色類別中的點(diǎn)進(jìn)行交換，則是通過計(jì)算不同類別損失權(quán)重的差值來判斷的，即交換前的內(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í)來產(chǎn)生一個(gè)較好的初始類。
MCL
最后談?wù)?，MarkovClusterAlgorithm(2000,StijnvanDongen),簡(jiǎn)稱MCL算法，是一種快速可擴(kuò)展的無監(jiān)督圖形聚類算法，有時(shí)也可以用于圖的劃分，其思想非常簡(jiǎn)單，主要是基于隨機(jī)游走(Randomwalk)和馬爾科夫鏈(Markovchain)。先簡(jiǎn)單說一下這兩個(gè)概念.
隨機(jī)游走說的是，如果我們從圖中的某一個(gè)點(diǎn)開始“瞎轉(zhuǎn)”，那么很可能就會(huì)在某一個(gè)子圖里面轉(zhuǎn)悠，而不是在子圖間來回游蕩.而隨機(jī)游走的計(jì)算是通過Markov鏈來實(shí)現(xiàn)的.Markov鏈指的是一個(gè)隨機(jī)序列，該序列滿足“無后效性”，即將來的狀態(tài)只依賴當(dāng)前狀態(tài)，而與過去的狀態(tài)無關(guān)。
MCL算法的關(guān)鍵思想就是：”隨機(jī)漫游者抵達(dá)稠密的類后，不會(huì)輕易的離開該類”.前者是隨機(jī)游走的過程，后者依據(jù)是Markov鏈的“無后效性”。MCL算法中隨機(jī)漫游的過程，其實(shí)是一個(gè)不斷修改轉(zhuǎn)移概率矩陣的過程，該過程重復(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ì)無權(quán)圖及有權(quán)圖均試用，劃分的子圖個(gè)數(shù)無需事先設(shè)定，這是該算法的最大優(yōu)勢(shì);劃分的子圖是非均勻的，試用于長(zhǎng)尾分布的數(shù)據(jù)。下圖就是利用MCL進(jìn)行圖劃分的結(jié)果：
但是MCL算法對(duì)圖的直徑較大的情況不適用.(直徑是指兩個(gè)點(diǎn)之間的距離最大值，距離是兩個(gè)點(diǎn)之間的所有路的長(zhǎng)度的最小值)
轉(zhuǎn)型的最終目的 -提質(zhì)降本增效
分享到微信 ×
打開微信，點(diǎn)擊底部的“發(fā)現(xiàn)”，
使用“掃一掃”即可將網(wǎng)頁(yè)分享至朋友圈。