動態(tài)特征選擇算法對惡意行為檢測的優(yōu)化研究*

劉 云，肖 添，王梓宇

(昆明理工大學(xué)信息工程與自動化學(xué)院，云南 昆明 650500)

1 引言

在線社交網(wǎng)絡(luò)OSN(Online Social Net)擁有龐大的用戶群，吸引來自不同行業(yè)和年齡段的用戶。盡管大多數(shù)OSN主要用于各種良性用途，但其自身的開放性、龐大的用戶群和消息實時擴散使OSN成為網(wǎng)絡(luò)罪犯有利可圖的目標。OSN已經(jīng)被證明是一種新的具有復(fù)雜攻擊和威脅的孵化器，例如網(wǎng)絡(luò)欺凌、傳播謠言、網(wǎng)絡(luò)詐騙、發(fā)送垃圾郵件和其他非法活動[1]。如何自動分析用戶行為特征以檢測出在線社交網(wǎng)絡(luò)中惡意用戶行為，成為一項重要而具有挑戰(zhàn)性的研究任務(wù)。

劉勘等人[2]提出基于隨機森林分類的惡意用戶檢測算法，從多維度分析惡意用戶的特征指標，構(gòu)建對應(yīng)的特征向量，并用隨機森林算法設(shè)計惡意用戶識別模型。Zhang等人[3]通過研究用戶行為的各種區(qū)別屬性和特征，提出一個動態(tài)的惡意用戶行為檢測框架，能自動處理不斷變化的惡意用戶行為。

Zadeh[4]提出的模糊集，引入了隸屬函數(shù)和隸屬度的思想，并由Ruspini[5]成功地將其應(yīng)用于聚類中。在模糊聚類中，Dunn[6]提出的模糊C均值FCM(Fuzzy C-Means)算法是最著名的算法。模糊聚類在各種應(yīng)用中被認為是一種非常強大的工具，已被廣泛應(yīng)用于各個領(lǐng)域，在基于用戶行為特征的惡意用戶行為檢測中也卓有成效。Do等人[7]提出了基于模糊集的惡意用戶檢測SDAFS(Spammer Detection Algorithm based on Fuzzy Set)算法，通過使用網(wǎng)絡(luò)方法檢測惡意用戶行為，然后利用FCM聚類算法找到用戶所屬聚類。Pinandito等人[8]提出基于模糊聚類的極限學(xué)習(xí)ELAFC(Extreme Learning Algorithm Based on Fuzzy Clustering)算法，通過分析用戶個人資料、活動和相關(guān)文本等特征，采用具有特征加權(quán)的FCM聚類算法對用戶行為進行聚類。Xu 等人[9]提出了一種基于網(wǎng)絡(luò)方法檢測惡意行為NADMB(Network-based Algorithm for Detecting Malicious Behavior)算法，該算法利用K-means聚類識別惡意群體。

但是，SDAFS算法由于使用模糊C均值聚類算法使得所有特征權(quán)重相同，影響了聚類精度。ELAFC算法雖然使用特征加權(quán)技術(shù)優(yōu)化了在多維特征下的聚類精度，但沒有考慮特征選擇，冗余特征依然會影響系統(tǒng)性能。而NADMB算法由于使用的特征較少，導(dǎo)致算法只能應(yīng)用于特定網(wǎng)絡(luò)。

本文在已有研究工作的基礎(chǔ)上，綜合考慮以上算法的優(yōu)缺點，提出一種動態(tài)特征選擇算法DFSA(Dynamic Feature Selection Algorithm)。該算法使用具有特征加權(quán)熵的模糊C均值目標函數(shù)，為參數(shù)構(gòu)建一個學(xué)習(xí)模式，通過多次迭代計算得出每個特征權(quán)重，剔除不相關(guān)或冗余的特征，對特征進行動態(tài)選擇，迭代地更新隸屬函數(shù)、簇中心和特征權(quán)重直到最優(yōu)化為止，最終識別出具有高精度的惡意簇。仿真結(jié)果表明，對比SDAFS算法、ELAFC算法和NADMB算法，本文提出的DFSA算法在Rand指數(shù)[10]、Jaccard指數(shù)[10]和歸一化互信息量3個主要性能指標上均有改善。

2 聚類模型

2.1 模糊C均值聚類框架

圖1所示是典型的模糊C均值聚類框架圖，由特征提取、模糊C均值聚類算法和標記3部分組成。首先，使用特征提取器從數(shù)據(jù)集中提取特征，每個特征被數(shù)字化后由一個特征向量表示。然后，通過使用模糊C均值聚類算法對新的數(shù)據(jù)集進行聚類，得出預(yù)先設(shè)定好的簇數(shù)，對模糊簇進行標記得出最終結(jié)果。

Figure 1 Framework of fuzzy C-means clustering

在惡意用戶行為自動檢測方法中，可將定義特征的數(shù)據(jù)集類型分為基于元數(shù)據(jù)的特征、基于內(nèi)容的特征和基于社區(qū)交互的特征[3]。由于復(fù)雜的惡意用戶行為可以通過使用隨機數(shù)生成器算法輕松地避免基于元數(shù)據(jù)的特征，因此基于元數(shù)據(jù)的特征的區(qū)分效率較低，DFSA算法將對基于內(nèi)容和基于社區(qū)交互的特征進行特征提取?，F(xiàn)有自動檢測惡意用戶行為相關(guān)文獻中對多個具有識別能力的特征有明確的定義，其中包括唯一URL比率 (F1)[11]、唯一提及率(F2)[11]、標簽比例(F3)[12]、提及率(F4)[11]、URL比率(F5)[13]、聲譽(F6)[11]、粉絲數(shù)比率(F7)[12]和聚類系數(shù)(F8)[13]，在此基礎(chǔ)上本文又定義了4個基于社區(qū)交互的新特征,包含粉絲聲譽比(F9)、粉絲關(guān)注比(F10)、社區(qū)聲譽(F11)和社區(qū)聚類系數(shù)(F12)。下面詳細解釋這4個新特征：

(1)粉絲聲譽比(F9)：用戶的聲譽通常不是他們自己的，而是從追隨他們的粉絲那里繼承的。通常用戶無法控制其粉絲，并且難以逃避和篡改基于粉絲的特征。用戶的聲譽與其粉絲的聲譽成正比，此特征反映了用戶粉絲的聲譽。用戶u的粉絲的聲譽為粉絲的聲譽總量與粉絲總量之比。

(2)粉絲關(guān)注比(F10)：惡意用戶對每個請求都非常敏感，無論發(fā)件人的身份如何，他們都只是為了增加其關(guān)注者列表，而良性用戶則在響應(yīng)未知用戶的請求時會有意識地篩選。因此，為檢測用戶粉絲的連接行為，可根據(jù)用戶的粉絲模式來分析粉絲的關(guān)注者模式。用戶u的粉絲關(guān)注比為粉絲關(guān)注數(shù)的平均值與粉絲數(shù)之比。

(3)社區(qū)聲譽(F11)：用戶的聲譽取決于與用戶相關(guān)聯(lián)的社區(qū)及其成員的聲譽。為了計算用戶u的F11值，首先從u的附近網(wǎng)絡(luò)中找到社區(qū);然后，計算每個社區(qū)的每個用戶的聲譽;最終根據(jù)其成員的聲譽來計算每個社區(qū)的聲譽和。

(4)社區(qū)聚類系數(shù)(F12)：此特征研究用戶社區(qū)成員之間的連接密度。用戶u的社區(qū)聚類系數(shù)為用戶所在的所有社區(qū)聚類系數(shù)的均值。

對用戶特征提取和數(shù)字化后，數(shù)據(jù)集中每個用戶可用如式(1)所示的特征向量來表示:

ui=〈F1,F2,…,F12〉

(1)

根據(jù)用戶的關(guān)注者和粉絲之間的聯(lián)系來考慮社區(qū)交互，本文使用一種快速社區(qū)檢測算法[14]來識別用戶交互網(wǎng)絡(luò)中的社區(qū)。圖2展示了一個用戶交互網(wǎng)絡(luò)的案例，圖2b為用戶A所連接的用戶及其與其他用戶連接形成的社區(qū)，其中C1和C2表示可能存在的社區(qū)結(jié)構(gòu)。對于惡意用戶來說，由于粉絲和關(guān)注者的隨機性，交互網(wǎng)絡(luò)中的用戶幾乎相互不認識，從而導(dǎo)致形成的社區(qū)非常稀疏或沒有社區(qū)。因此，可以通過分析社區(qū)成員來分析用戶行為。

Figure 2 User interaction network

2.2 模糊C均值聚類算法

算法中使用的大多數(shù)符號總結(jié)如表1所示。

Table 1 Symbol list

令X={x1,…,xn}是d維空間中的數(shù)據(jù)集，F(xiàn)CM目標函數(shù)定義如式(2)所示：

(2)

使其服從

其中μik∈[0,1],1≤i≤n,1≤k≤c。

加權(quán)指數(shù)1

(3)

(4)

且滿足1≤i≤n。

FCM中所有的特征無論是否相關(guān)，其權(quán)重大小都是相等的，所以容易導(dǎo)致聚類結(jié)果不正確，其缺陷可通過例1來解釋。

Figure 3 Clustering results

2.3 模糊簇標記

最后將2個簇分別標記為惡意簇和良性簇?？紤]已知的用戶行為特征分布情況[ 12,13]，將對不同用戶行為區(qū)分度較大的特征F3和F7再次使用在此任務(wù)中。將以上特征平均值高的簇標記為良性簇，另一個簇相應(yīng)地被標記為惡意簇。

3 DFSA算法

3.1 DFSA算法介紹

圖4所示是動態(tài)特征選擇算法框架圖，由特征提取、DFSA算法和標記3部分組成。首先，使用特征提取器從用戶數(shù)據(jù)集中提取12個特征，每個用戶特征被數(shù)字化后由一個特征向量表示；然后，使用動態(tài)特征選擇算法對用戶特征向量數(shù)據(jù)集進行聚類；最終得出2個簇，并分別標記為良性簇和惡意簇。

Figure 4 Framework of DFSA algorithm

由于數(shù)據(jù)集可能包含一些冗余或不相關(guān)的特征，因此特征選擇在聚類算法中非常重要。本文提出了一種動態(tài)特征選擇算法，利用特征加權(quán)熵進行特征選擇，以改進模糊C均值聚類算法。在此算法中，每個特性都有自己的權(quán)重，這些權(quán)重將在每次迭代時更新，并剔除權(quán)重小于閾值的特征，動態(tài)選擇重要的特征分量。令X={x1,…,xn}為d維空間中的數(shù)據(jù)集，DFSA目標函數(shù)如式(5)所示:

(5)

使其服從

(6)

其中δj控制特征權(quán)重。

DFSA算法通過3個最小化步驟來求解。

(7)

對式(7)的μik求拉格朗日偏導(dǎo)數(shù)并使其值為0，可得出式(8):

(8)

從更新的式(8),可求得μik如式(9)所示：

(9)

(10)

由式(10)可得vkj的更新如式(11)所示:

(11)

(12)

由式(12)可得ωj的更新如式(13)所示:

(13)

(14)

其中，dnew表示更新后得到的特征成員數(shù)。

衡量離散度的一個著名指標是方差-均值比(VMR)，其定義為VMR=σ2/μ，用于觀察離散或聚集的數(shù)據(jù)集。離散度越小，表示數(shù)據(jù)集離簇中心越近;離散度越大，表示數(shù)據(jù)集離簇中心越遠。由于需要保留離散度小的特征，拋棄離散度大的特征，因此考慮VMR的倒數(shù)，即均值-方差比(MVR)[16]。

將MVR應(yīng)用在本文算法中，因為在DFSA算法中特征j的(mean(x)/var(x))j可以表示數(shù)據(jù)集中簇之間的離散度。因此,使用(mean(x)/var(x))j作為δj的值,如式(15)所示：

(15)

3.2 算法流程

DFSA算法流程如算法1所示:

算法1DFSA算法

輸入：固定ε>0，取簇數(shù)c=2，初始化簇中心V(0)，初始化特征權(quán)重W(0)，W(0)=[ωj]1×d，X={x1,…,xn},j=1,…,d，ωj=1/d，且令t=0。

輸出：最佳聚類結(jié)果C*。

1：輸入數(shù)據(jù)集X，通過式(15)計算出δj；

2：輸入δj,V(t-1)和W(t-1)，通過式(9)計算出隸屬函數(shù)U(t)；

3：輸入U(t)，通過式(11)更新簇中心V(t)；

4：輸入δj，U(t)和V(t)，通過式(13)更新W(t)；

5：forj≤ddo

6：dr=0;

8： 丟棄特征權(quán)重小于閾值的特征ωj；

9： 且設(shè)dr=dr+1；

10：end

11：end

12： 設(shè)共丟棄dr個特征，dnew=d-dr；

13： 根據(jù)式(14)調(diào)整W(t)；

14：if|‖W(t)‖-‖W(t-1)‖|<εthenstop

15： 得出最佳聚類結(jié)果C*；

16：else

17： 令t=t+1，dnew=d返回第1步；

DFSA算法首先固定ε和c的值，初始化簇中心V(0)和特征權(quán)重W(0)，進入第1次迭代計算，分別得出更新后的δj，U(t),V(t)和W(t)。然后判斷并丟棄權(quán)重小于閾值的特征，調(diào)整特征成員數(shù)得出新的W(t)值。最終判斷聚類結(jié)果是否達到最優(yōu)，若達到則退出循環(huán)并輸出最佳聚類結(jié)果C*，否則開始新的一次迭代計算過程。

3.3 算法復(fù)雜度分析與評價指標

為進一步研究算法的計算復(fù)雜度，可將DFSA算法分為3個部分:

(1)計算模糊隸屬度(μik)劃分需要O(nc2d)；

(2)更新簇中心(vk)需要O(nc)；

(3)更新特征權(quán)重wj需要O(ncd2)。

符號O(·)僅考慮函數(shù)增長率的上限，則DFSA算法的總計算復(fù)雜度為O(nc2d+ncd2),其中n為數(shù)據(jù)點的個數(shù)，c為簇數(shù)，d為數(shù)據(jù)點維數(shù)。

為測量聚類性能，本文選用Rand指數(shù)、Jaccard指數(shù)和歸一化互信息NMI(Normalized Mutual Information)作為評價指標，其定義如下所示：

設(shè)C是數(shù)據(jù)集中的原始簇，C*是通過聚類算法得到的簇集合。對于一對點(xi,xj)，E表示2個點在C和C*中屬于相同簇的對數(shù);F表示2個點在C中屬于相同簇，而在C*中屬于不同簇的對數(shù)；G表示2個點在C中屬于不同簇，而在C*中屬于相同簇的對數(shù)；L表示2個點在C和C*中都屬于不同簇的對數(shù)。

(1)Rand指數(shù)RI(Rand Index)如式(16)所示：

(16)

(2)Jaccard指數(shù)JI(Jaccard Index)如式(17)所示：

(17)

(3)歸一化互信息(NMI)如式(18)所示：

(18)

其中,H(X)是X的熵，I(X:Y)是H(X)和H(Y)之間的互信息量。

4 仿真分析

4.1 數(shù)據(jù)集及仿真環(huán)境

與類似論文一致，為了驗證DFSA算法的有效性，本文選取通用數(shù)據(jù)集，即從微博的登錄服務(wù)器上收集到的真實登錄事件的數(shù)據(jù)集[17]。該數(shù)據(jù)集中有11 000個帶有標簽的用戶，包含10 000個良性用戶和1 000個惡意用戶;還包含帶有標簽用戶的關(guān)注者和粉絲列表及其用戶文件信息，如用戶名、位置和用戶ID;還包含微博和相關(guān)的詳細信息，如微博ID、創(chuàng)建時間和已標記用戶的收藏計數(shù)等。

表2列出了數(shù)據(jù)集的簡要統(tǒng)計信息，其中用戶總和包括標記為良性用戶和惡意用戶的所有關(guān)注者和粉絲。在這個數(shù)據(jù)集中，大多數(shù)良性用戶沒有他們的粉絲者列表，因此他們基于社區(qū)交互的特征值為零，這將會導(dǎo)致算法在檢測時有所偏差。若只考慮有粉絲者列表的實例(218個良性用戶和1 000個惡意用戶)，就會導(dǎo)致數(shù)據(jù)不平衡問題。為了解決該問題，本文使用合成少數(shù)過采樣技術(shù)SMOTE(Synthetic Minority Oversampling Technique)[18]，以生成與數(shù)據(jù)集少數(shù)類相關(guān)的合成樣本。針對SMOTE中的樣本數(shù)據(jù)點，將識別其相鄰數(shù)據(jù)，并根據(jù)樣本點及其相鄰數(shù)據(jù)之間的差異生成合成樣本。通過SMOTE生成了782個良性類的實例來平衡數(shù)據(jù)集。在公有云平臺上使用具有2 GHz 64位QEMU(Quick EMUlator)虛擬CPU的虛擬主機，并使用Networkx Python Library提取連接的組件。

Table 2 Data set statistics

4.2 算法目標函數(shù)與收斂性分析

DFSA算法首先更新集群中心和成員矩陣，然后計算新的特征權(quán)值，并在聚類過程中丟棄權(quán)值較小的特征。選擇出高度關(guān)聯(lián)的特征后調(diào)整數(shù)據(jù)點和聚類中心，將新的特征權(quán)重、聚類中心和隸屬度矩陣代入算法第1步重新開始計算，迭代過程一直持續(xù)到目標函數(shù)最小化為止。

圖5顯示了DFSA算法迭代次數(shù)對應(yīng)的目標函數(shù)值和迭代時間，目標函數(shù)總共經(jīng)過12次迭代后收斂。經(jīng)過6次迭代后部分特征被丟棄，從那時起目標函數(shù)收斂速度明顯加快。同時，后幾次迭代的計算時間比前幾次迭代需要的時間更少。從第9次開始，迭代所需的時間比第1次迭代減少了75%以上。這意味著經(jīng)過前幾次迭代后，由于部分不重要的特征被丟棄，使得計算時間會迅速減少。

Figure 5 DFSA objective function convergence and iteration time

4.3 聚類精度及特征顯著性分析

圖6所示是DFSA算法每次迭代對應(yīng)RI、JI和NMI的變化情況。隨著迭代次數(shù)的增加，3個聚類性能指標均在提高，且第9次迭代后的聚類性能相比第6次有明顯提高。

Figure 6 DFSA iterative calculation time

12個特征最初具有相同的權(quán)重，經(jīng)過6次迭代之后F1、F2、F4、F5和F65個特征權(quán)重低于閾值，在聚類過程中被丟棄，算法最終保留了其余7個重要的特征。特征權(quán)重的變化也說明算法通過多次迭代后，因為特征減少明顯加快了后幾次迭代計算的速度。

通過統(tǒng)計顯著性分析來驗證算法所保留特征在用戶間的差異是否是隨機的，為了驗證這個假設(shè)，對4.1節(jié)討論的微博數(shù)據(jù)集[16]進行雙邊Z檢驗。在Z檢驗中，原假設(shè)下檢驗統(tǒng)計量服從正態(tài)分布，采用2種假設(shè)進行評估，即原假設(shè)(H0:μ=μ0)和備擇假設(shè)(H1:μ≠μ0)。

在原假設(shè)中，假設(shè)惡意用戶和良性用戶之間定義的特征值的總體均值沒有顯著差異，而在備擇假設(shè)中，假設(shè)2種不同用戶特征值的均值存在顯著差異。計算被算法保留的7個特征檢驗統(tǒng)計量，并與表3中在5%顯著性水平下的雙邊Z統(tǒng)計量臨界值(±1.96)進行比較。分析中發(fā)現(xiàn)，7個特征均拒絕原假設(shè)，如表3所示，因此可以看出惡意用戶和良性用戶的這7個特征均值存在顯著差異。且從表3中可以看出，惡意用戶和良性用戶之間F7和F12的平均值差異最大。根據(jù)Zhang等人[3]對用戶行為特征累計分布的統(tǒng)計及以上的顯著性分析可以推斷，DFSA算法所選擇的特征對于分離不同用戶行為是重要的。

Table 3 Z-test statistics for selected features

4.4 算法聚類性能對比分析

將本文所提出的DFSA算法與SDAFS算法、ELAFC算法和NADMB算法進行對比實驗，分別得出4種算法在不同迭代時間下的Rand指數(shù)(RI)、Jaccard指數(shù)(JI)和歸一化互信息(NMI)。

如圖7所示，4種算法的RI都隨著迭代次數(shù)的增加逐漸提高，直到最終收斂到最高值為止。DFSA算法的RI最高且收斂速度最快，SDAFS算法與ELAFC算法的RI相近，但ELAFC算法收斂速度更慢，而MADMB算法的RI最低且收斂速度也較慢。

Figure 7 RI changes with time of different algorithms

如圖8所示，DFSA算法的JI最高，ELAFC算法的JI次之，SDAFS算法的JI較低，而NADMB算法的JI最低。

Figure 8 JI changes with time of different algorithms

如圖9所示，仿真結(jié)果對比顯示DFSA算法的NMI值最高，ELAFC算法的NMI值次之，SDAFS算法的NMI值較低，NADMB算法的NMI值最低。

Figure 9 NMI changes with time of different algorithms

通過分析3個主要性能指標隨時間變化情況可知，本文所提的DFSA算法相比SDAFS算法、ELAFC算法和NADMB算法的聚類性能更好，且迭代次數(shù)更少，收斂速度明顯更快。結(jié)合特征權(quán)重變化，DFSA算法剔除了冗余或不相關(guān)的特征，輸出了與用戶行為高度相關(guān)聯(lián)的簇。SDAFS算法和NADMB算法不涉及特征選擇，雖然具有較快的收斂速度，但冗余特征影響了聚類性能。而ELAFC算法計算了特征權(quán)重，一定程度上使聚類性能有所提升，但也導(dǎo)致了計算復(fù)雜度的增加，收斂速度變慢。

5 結(jié)束語

為了發(fā)現(xiàn)在線社交網(wǎng)絡(luò)中進行復(fù)雜惡意活動的惡意用戶簇，本文提出一種動態(tài)特征選擇算法(DFSA)。不同于大多數(shù)的特征加權(quán)算法，該算法將動態(tài)特征選擇模式嵌入到聚類過程中，在第1次迭代中所有的特征都會被使用，然后在每次迭代中更新特征權(quán)值，并用閾值剔除權(quán)值較小的特征，后續(xù)步驟中使用的特征數(shù)量將逐漸減少，動態(tài)選擇出重要的特征分量，迭代地更新隸屬函數(shù)、集群中心和特征權(quán)重，直到優(yōu)化為止，最終識別出具有高聚類精度的惡意用戶簇。仿真結(jié)果表明，對比SDAFS算法、ELAFC算法和NADMB算法，DFSA算法在Rand指數(shù)(RI)、Jaccard指數(shù)(JI)和歸一化互信息量(NMI)3個主要性能指標上均有改善。DFSA算法相比傳統(tǒng)算法的優(yōu)勢在于能動態(tài)選擇重要的特征，不僅提高了收斂速度，而且通過剔除不相關(guān)的特征降低了特征維數(shù)，提高了聚類精度。在未來的工作中，將考慮使用多個社交網(wǎng)絡(luò)用戶數(shù)據(jù)集進行更多測試，包括檢測算法在不同特征和不同數(shù)據(jù)集大小情況下的聚類性能，以及算法的魯棒性。