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