基于信息增益的KNN 社交網(wǎng)絡(luò)異常用戶檢測

武海燕，李坤明

（鐵道警察學(xué)院圖像與網(wǎng)絡(luò)偵查系，河南鄭州 450053）

0 引言

隨著社交網(wǎng)絡(luò)平臺的迅速發(fā)展，國內(nèi)的微信、微博，國外的Twitter、Facebook 等已經(jīng)成為人們?nèi)粘Ｉ钪兄匾纳缃还ぞ撸絹碓蕉嗟娜藗冊谏缃痪W(wǎng)絡(luò)平臺上獲取信息［1-2］。當(dāng)前社交網(wǎng)絡(luò)中存在著大量異常用戶，這些異常用戶通過創(chuàng)建大量的虛假賬號和盜用正常用戶的賬號，發(fā)布虛假廣告、散布謠言等行為擾亂社會穩(wěn)定。同時，也存在著發(fā)布釣魚信息，操縱大量用戶進(jìn)行互粉、點贊的惡意行為。因此，社交網(wǎng)絡(luò)平臺上的非法用戶檢測具有重要意義，不僅讓用戶在社交網(wǎng)絡(luò)上獲得真實信息、提升上網(wǎng)體驗，同時也是公安輿情和社交網(wǎng)絡(luò)研究領(lǐng)域的一個重要課題。

1 相關(guān)工作

近年來，研究者主要采用機(jī)器學(xué)習(xí)算法對社交網(wǎng)絡(luò)異常用戶進(jìn)行檢測，比較常用的方法分為3 種：有監(jiān)督學(xué)習(xí)的檢測方法、無監(jiān)督學(xué)習(xí)的檢測方法和圖模型的檢測方法。其中，圖模型檢測方法是一種特殊的無監(jiān)督檢測方法。

1.1 無監(jiān)督學(xué)習(xí)的檢測方法

當(dāng)樣本數(shù)據(jù)集不含標(biāo)簽或者是僅僅擁有少量用戶的標(biāo)簽時，研究者提出利用無監(jiān)督學(xué)習(xí)算法解決異常用戶檢測問題。無監(jiān)督學(xué)習(xí)檢測方法是基于聚類思想，將正常用戶和異常用戶聚集為不同簇的方法。Husna［3］等將垃圾郵件的發(fā)送者所發(fā)送郵件的內(nèi)容、時間、頻率等作為特征，然后使用K 均值聚類算法進(jìn)行聚類分析；為了提高聚類效果，陳莊等［4］通過引入信息熵，將各屬性權(quán)重進(jìn)行排序后計算相似度，提升了檢測率；Miller 等［5］通過使用兩種聚類算法相結(jié)合的方式對Twitter 上的用戶進(jìn)行聚類分析，以識別出正常用戶和異常用戶；Beutel 等［6］設(shè)計出CopyCatch 模型，該方法通過構(gòu)建出社交網(wǎng)絡(luò)時間矩陣，最大化TNBC 核心中的異常用戶數(shù)量，以此進(jìn)行聚類，檢測出Facebook 中的異常用戶。使用無監(jiān)督方法的優(yōu)點是不需要對數(shù)據(jù)進(jìn)行標(biāo)注，也不用提前訓(xùn)練，可以很方便地構(gòu)建出社交網(wǎng)絡(luò)異常用戶檢測模型。但是，構(gòu)建出的模型準(zhǔn)確率低、算法設(shè)計復(fù)雜。

1.2 圖模型檢測方法

基于網(wǎng)絡(luò)連接的圖模型檢測方法主要根據(jù)異常用戶與正常用戶所具有的不同拓?fù)浣Y(jié)構(gòu)，一般采用無監(jiān)督學(xué)習(xí)檢測方法［7］。常用的兩種檢測方法是基于譜分解的檢測方法和基于隨機(jī)游走的檢測方法［8-10］。圖模型的優(yōu)點是不需要提前訓(xùn)練，只需要圖數(shù)據(jù)，由于對理論假設(shè)條件要求高，因而模型準(zhǔn)確率較低。

1.3 有監(jiān)督學(xué)習(xí)的檢測方法

使用機(jī)器學(xué)習(xí)監(jiān)督算法對社交網(wǎng)絡(luò)異常用戶進(jìn)行檢測是研究者常采用的一種方式。此時的數(shù)據(jù)集含有標(biāo)簽并利用這些數(shù)據(jù)集訓(xùn)練出分類模型，然后使用訓(xùn)練好的模型對其他未被標(biāo)注的數(shù)據(jù)集進(jìn)行預(yù)測。Chu 等［11］通過提取社交網(wǎng)絡(luò)用戶的內(nèi)容、行為和屬性特征，并結(jié)合信息熵使用貝葉斯（Naive Bayesian，NB）算法構(gòu)建出分類模型，該方法對異常用戶檢測的準(zhǔn)確率較高，但是計算量大，而且該方法假設(shè)所有的屬性之間互相獨立，普適性有所欠缺。孟祥飛等［12］通過將社交網(wǎng)絡(luò)用戶的粉絲數(shù)量、評論數(shù)、互粉數(shù)等作為特征，使用C4.5 決策樹（Decision Tree，DT）算法構(gòu)建分類模型，實現(xiàn)對用戶的檢測，這兩種方法在分類精度上均存在不足；袁麗欣等［13］使用XGboost 方法對特征進(jìn)行選擇，構(gòu)建集成分類器實現(xiàn)對異常用戶的檢測；徐華露等［14］使用蜜罐收集數(shù)據(jù)集，然后使用隨機(jī)森林算法對社交網(wǎng)絡(luò)中的僵尸用戶進(jìn)行檢測；Bo 等［15］對微博數(shù)據(jù)集的內(nèi)容以及用戶行為進(jìn)行抽取并將其作為特征，使用支持向量機(jī)（Support Vector Machine，SVM）構(gòu)建分類模型，該方法可達(dá)到較高的分類精度；王越等［16］將微博的數(shù)量、轉(zhuǎn)發(fā)率等內(nèi)容特征和用戶信息特征，如粉絲數(shù)量、人體指數(shù)等作為特征，使用模擬退火算法對特征進(jìn)行處理，然后用BP 神經(jīng)網(wǎng)絡(luò)構(gòu)建分類模型，通過對5 000 個測試集進(jìn)行測試得到該模型準(zhǔn)確率達(dá)93%。使用SVM 和神經(jīng)網(wǎng)絡(luò)時算法時間復(fù)雜度較高。

對此，本文提出一種基于信息增益的KNN 社交網(wǎng)絡(luò)異常用戶檢測模型，首先使用信息增益特征選擇方法對數(shù)據(jù)集進(jìn)行屬性約簡，選擇出重要性較高的特征屬性，去除冗余屬性，然后使用特征選擇后的數(shù)據(jù)集訓(xùn)練出KNN 分類器模型，該方法有效提高了分類精確率和召回率。

2 相關(guān)概念

2.1 信息增益特征選擇

在使用機(jī)器學(xué)習(xí)方法對社交網(wǎng)絡(luò)中的異常用戶進(jìn)行檢測時，需要其準(zhǔn)確地發(fā)現(xiàn)異常行為，但是在文本數(shù)據(jù)處理過程中會產(chǎn)生很多冗余特征，這就需要使用特征選擇方法去除重復(fù)多余的特征，挑選出關(guān)鍵特征。當(dāng)前屬性約簡算法有主成分分析（PCA）法、奇異值分解（SVD）法和信息增益（IG）等，其中PCA 和SVD 可能會損失部分重要信息。信息增益是一種過濾式特征選擇方法。數(shù)據(jù)樣本屬性特征之間的信息越多，則這些特征之間的聯(lián)系也越緊密，同時特征之間的信息增益也就越大。一般情況下，屬性特征的信息增益越大，其對分類結(jié)果的影響也越大［17］。因此，可以通過信息增益的方法確定數(shù)據(jù)集中較重要的屬性特征，并選擇信息增益大的屬性特征。此外，信息增益主要通過信息熵實現(xiàn)，信息熵是熵在衡量信息變量中無序度的度量。對于一個給定的數(shù)據(jù)集D，假設(shè)D 中第i類樣本所占比例為pi(i=1,2,...,|Y|)，假定樣本屬性均為離散型。對于每個屬性A，假定根據(jù)其取值將D 分成了V 個子集{D1,D2,D3,...,Dv}，每個子集中的樣本在A 上取值相同，則屬性A 的信息增益為：

對于任何一個離散的數(shù)據(jù)集，可以通過計算每個屬性在該數(shù)據(jù)集中的信息增益，然后根據(jù)需要選擇相應(yīng)的屬性。

Fig.1 Flow of feature selection based on information gain圖1 基于信息增益的特征選擇流程

2.2 KNN 算法

K 近鄰算法（K-Nearest Neighbor，KNN）是一種常見的分類算法。其基本思想是：假設(shè)給定一個訓(xùn)練數(shù)據(jù)集，其中的實例類別已定，KNN 算法通過計算待分類樣本相似度最大的K 個鄰近樣本，然后通過這K 個鄰居樣本的類別采用投票方法確定待分樣本所屬類別。這K 個實例的多數(shù)據(jù)屬于某個類，就將該實例分為這個類［18-19］。其算法如下：

輸入：訓(xùn)練數(shù)據(jù)集T={(x1,y1),(x2,y2)…(xN,yN)}

其中，xi∈χ?Rn為實例的特征向量，xi∈y={c1,c2...ck}為實例類別，i=1，2，…，N；實例特征向量x；

輸出：實例x所屬的類y。

（1）根據(jù)給定的距離度量，在訓(xùn)練集T 中找出與x最近鄰的k個點，涵蓋這k 個點的x的鄰域記作Nk(x)；

（2）在Nk(x)中根據(jù)分類決策規(guī)則（如多數(shù)表決）決定x的類別y：

式（2）中，I 為指示函數(shù)，即當(dāng)yi=cj時I 為1，否則為0。

3 檢測模型

由于社交網(wǎng)絡(luò)異常用戶的多類特征均與正常用戶有所區(qū)別，傳統(tǒng)的特征提取方法會對用戶原始數(shù)據(jù)進(jìn)行提取，沒有對初始數(shù)據(jù)集的特征作約簡處理，在所保留的特征屬性中存在著很多冗余屬性。這對高維特征的檢測效果非常有限，不僅影響分類器的工作效率，同實也降低了分類器的分類精度。鑒于此，本文通過對社交網(wǎng)絡(luò)用戶初始數(shù)據(jù)集進(jìn)行特征選擇，刪除特征集中的冗余特征。

Fig.2 Classification module after feature selection圖2 特征選擇后的分類模塊

分類算法設(shè)計是文本分類全部流程中最重要的環(huán)節(jié)，分類算法的優(yōu)劣，將直接影響到分類性能的高低。一方面，隨著機(jī)器學(xué)習(xí)技術(shù)的不斷發(fā)展，越來越多高精度的分類算法被提出，分類準(zhǔn)確性越來越逼近文本的真實類別分布，當(dāng)然這些復(fù)雜算法的時間開銷也很可觀；另一方面，隨著在線應(yīng)用的普及，互聯(lián)網(wǎng)對處理算法的時間開銷要求越來越苛刻，決策樹、樸素貝葉斯等輕量級的文本分類算法，分類效率較高，但在分類準(zhǔn)確率上的不足使它們很難適應(yīng)高性能應(yīng)用場景。深度學(xué)習(xí)等人工神經(jīng)網(wǎng)絡(luò)方法和支持向量機(jī)等高準(zhǔn)確率算法的時間復(fù)雜度較高，很難給在線應(yīng)用帶來滿意的用戶體驗。KNN 算法作為一種典型的基于實例的分類方法，可以通過非常簡單的分類機(jī)制達(dá)到可媲美復(fù)雜算法的分類準(zhǔn)確率，是社交網(wǎng)絡(luò)文本挖掘領(lǐng)域值得深入研究的算法。

信息增益特征選擇算法既可以對社交網(wǎng)絡(luò)用戶初始數(shù)據(jù)集進(jìn)行特征降維處理，刪除數(shù)據(jù)集中的冗余屬性，避免高維特征引發(fā)噪聲，同時又能保留初始數(shù)據(jù)中的關(guān)鍵要素。因此，本文提出了一種基于信息增益的KNN 社交網(wǎng)絡(luò)異常用戶檢測模型，如圖3 所示。

具體步驟如下：

輸入：社交網(wǎng)絡(luò)用戶數(shù)據(jù)集D。

輸出：分類結(jié)果。

Step1：對原始數(shù)據(jù)集進(jìn)行特征抽取。

Step2：計算數(shù)據(jù)集D 的經(jīng)驗熵H（D）：

Step3：計算特征A 對數(shù)據(jù)集D 的經(jīng)驗條件熵H(D|A)。

可進(jìn)一步優(yōu)化為：

Step4：計算信息增益。

Step5：通過信息增益對數(shù)據(jù)集進(jìn)行屬性約簡，確定優(yōu)化后最終的特征集。

Step6：使用優(yōu)化后的數(shù)據(jù)集構(gòu)建KNN 分類器模型。

Step7：測試分類模型效果，得到測試結(jié)果。

Fig.3 Information gain-based abnormal user detection model in KNN social network圖3 基于信息增益的KNN 社交網(wǎng)絡(luò)異常用戶檢測模型

4 實驗分析

4.1 實驗數(shù)據(jù)集

實驗過程中使用的數(shù)據(jù)集來自Apontador 數(shù)據(jù)集［20］，該數(shù)據(jù)集包含了正常用戶和異常用戶，其中異常用戶又被分為3 種。表1 展示了本次實驗數(shù)據(jù)集情況，在實驗過程中將數(shù)據(jù)集分為正常用戶和異常用戶兩類，對于Apontador中的廣告發(fā)布者（LM）、內(nèi)容污染者（PL）和不良言論發(fā)布者（BM）統(tǒng)一定義為異常用戶。

Table 1 User classification of Apontador dataset表1 Apontador 數(shù)據(jù)集用戶分類

4.2 評價指標(biāo)

在使用機(jī)器學(xué)習(xí)算法構(gòu)建分類模型進(jìn)行二分類時，常用評價指標(biāo)有準(zhǔn)確率、召回率、F 值。對于社交網(wǎng)絡(luò)用戶檢測而言，在實驗過程中更希望檢測出更多的異常用戶，避免異常用戶逃避分類模型檢測，因此需要將召回率作為評價指標(biāo)。同時為了所構(gòu)建模型的可用性，還需考慮分類結(jié)果的準(zhǔn)確率。為此，將分類模型的精確率和召回率作為此次實驗的評價指標(biāo)。分類結(jié)果混淆矩陣如表2 所示。

其中，準(zhǔn)確率表示為：

Table 2 Confusion matrix of classification results表2 分類結(jié)果混淆矩陣

4.3 實驗結(jié)果

實驗在開源的機(jī)器學(xué)習(xí)分析工具Weka3.9.2 環(huán)境下進(jìn)行，分類結(jié)果比較如表3 所示。

Table 3 Comparison of classification results表3 分類結(jié)果比較

可以看出，使用信息增益對數(shù)據(jù)集進(jìn)行特征選擇后，所構(gòu)建的分類模型在分類精確度和召回率上均優(yōu)于傳統(tǒng)的KNN 分類模型。其中，精確度由最初的91.3%上升到92.9%，提升了1.6%；召回率提升了2.3%。可以得出，本文提出的方法能夠有效提升對社交網(wǎng)絡(luò)異常用戶的效果。

5 結(jié)語

本文將信息增益特征選擇方法與KNN 算法相結(jié)合，提出了一種基于信息增益的KNN 社交網(wǎng)絡(luò)異常用戶檢測模型。該模型在對社交網(wǎng)絡(luò)異常用戶的檢測效果上優(yōu)于傳統(tǒng)檢測方法，在使用機(jī)器學(xué)習(xí)算法對社交網(wǎng)絡(luò)異常用戶進(jìn)行檢測時，需要去除數(shù)據(jù)集中的冗余屬性以達(dá)到提升分類效果的目的。

本文所構(gòu)建的模型僅僅考慮了社交網(wǎng)絡(luò)中的常規(guī)數(shù)據(jù)集，模型魯棒性問題未予以考慮，在接下來的研究中可將多種算法相結(jié)合以構(gòu)建分類模型，提升模型魯棒性，使得模型的可用性更加廣泛。