張宇翔，孫菀，楊家海，周達磊，孟祥飛，肖春景

（1. 中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院，天津 300300；2. 清華大學(xué)網(wǎng)絡(luò)科學(xué)與網(wǎng)絡(luò)空間研究院，北京 100084；3. 清華信息科學(xué)與技術(shù)國家實驗室，北京 100084；4. 北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院，北京 100876；5. 北京航空航天大學(xué)虛擬現(xiàn)實技術(shù)與系統(tǒng)國家重點實驗室，北京 100876）

新浪微博反垃圾中特征選擇的重要性分析

張宇翔1,2,3，孫菀1，楊家海2,3，周達磊4，孟祥飛5，肖春景1

（1. 中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院，天津 300300；2. 清華大學(xué)網(wǎng)絡(luò)科學(xué)與網(wǎng)絡(luò)空間研究院，北京 100084；3. 清華信息科學(xué)與技術(shù)國家實驗室，北京 100084；4. 北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院，北京 100876；5. 北京航空航天大學(xué)虛擬現(xiàn)實技術(shù)與系統(tǒng)國家重點實驗室，北京 100876）

微博中的垃圾用戶非常普遍，其異常行為及生產(chǎn)的垃圾信息顯著降低了用戶體驗。為了提高識別準(zhǔn)確率，已有研究或是盡可能多地定義特征，或是不斷嘗試提出新的分類檢測方法；那么，微博反垃圾問題的突破點優(yōu)先置于尋找分類特征還是改進分類檢測方法，是否特征越多檢測效果越好，新的方法是否可以顯著提高檢測效果。以新浪微博為例,試圖通過不同的特征選擇方法與不同的分類器組合實驗回答以上問題，實驗結(jié)果表明特征組的選擇較分類器的改進更為重要，需從內(nèi)容信息、用戶行為和社會關(guān)系多側(cè)面生成特征，且特征并非越多檢測效果越好，這些結(jié)論將有助于未來微博反垃圾工作的突破。

新浪微博；特征生成；特征選擇；垃圾用戶檢測

1 引言

微博是一種近年來新興的在線社交網(wǎng)絡(luò)(online social network)，用戶可通過Web、WAP等各種客戶端在其上組建個人社區(qū)，并允許發(fā)布140字左右的文字更新信息，用戶之間通過建立單向或雙向的友好關(guān)系實現(xiàn)信息即時分享。

在微博成為人們?nèi)粘＝涣鞯闹匾绞街畷r，同時也成為垃圾用戶(spammer)發(fā)布非法廣告和垃圾消息的平臺。2013年7月，新華網(wǎng)報道[1]“新浪微博社區(qū)公約體系上線運行約一年時間，微博管理中心共接到超過1 500萬次的用戶舉報，其中垃圾廣告達到1 200多萬次，淫穢色情危害信息達到100多萬次”。根據(jù)人民網(wǎng)報道[2]，大量虛假粉絲嚴(yán)重侵害用戶利益并影響微博生態(tài)，2015年1月起新浪微博根據(jù)用戶舉報和數(shù)據(jù)分析清除垃圾粉絲。微博中垃圾問題非常嚴(yán)重，垃圾用戶的異常行為及生產(chǎn)的垃圾信息顯著降低了用戶體驗，增添了社會風(fēng)險。

學(xué)術(shù)界開展較早的反垃圾研究包括垃圾網(wǎng)頁檢測[3]、垃圾郵件過濾、虛假在線評論過濾[4]、網(wǎng)絡(luò)眾包(crowdsourcing)中的欺騙檢測[5]、傳統(tǒng)社交網(wǎng)絡(luò)(如人人網(wǎng)[6])中的垃圾過濾等，研究中用到的反垃圾方法對于微博中垃圾用戶檢測有一定的借鑒意義，但因為微博的構(gòu)成要件及其功能均不同于前述應(yīng)用，故不能將其直接應(yīng)用于微博反垃圾。

微博反垃圾問題的解決非常困難，其原因主要有以下幾個方面：1)微博文字信息非常短，并且?guī)в写罅康牟灰?guī)范用語，因此微博文字內(nèi)容具有噪聲多、特征詞少等特點；2)簡短的文字信息中可包含頁面、圖片、音頻、視頻的鏈接，非法用戶將鏈接指向與文字信息不一致的垃圾內(nèi)容，加之目前廣泛使用的 URL縮短服務(wù)，很難做到機器自動鑒別鏈接指向內(nèi)容；3)垃圾制造者不斷創(chuàng)新，以更高明的方式躲避檢測，且更新周期越來越短[7]。

微博反垃圾研究起步較晚，研究成果不多，而且已有研究絕大多數(shù)均是針對Twitter，少部分針對Myspace[8,9]、Facebook[8,10]、Foursquare[11]等。目前，鮮有針對新浪微博的反垃圾研究工作，盡管新浪微博與 Twitter在基本功能上較為相似，但在網(wǎng)民構(gòu)成、傳播內(nèi)容、轉(zhuǎn)發(fā)模式、開放性、好友管理、擴展功能等方面均存在較大差異[12～15]，加之針對Twitter的反垃圾研究也處于研究初期，因此不能將 Twitter中的反垃圾方法直接用于新浪微博反垃圾中。

在微博垃圾用戶檢測研究中，先要確定待檢測垃圾用戶所指的具體對象，是發(fā)布垃圾內(nèi)容(如虛假信息、垃圾鏈接等)者，還是僵尸、水軍等；接著通過微博提供的 API接口等方式采集檢測所需的數(shù)據(jù)；最后選取有利于垃圾檢測的特征，利用機器學(xué)習(xí)方法對所有用戶進行分類檢測，確定垃圾用戶。

微博反垃圾研究大都圍繞上述步驟展開，方法上的差異主要體現(xiàn)在最后一步。研究初期采用的方法是試圖找到能較好地區(qū)分正常用戶與垃圾用戶的少數(shù)幾個特征，通過設(shè)定恰當(dāng)?shù)拈撝祦韰^(qū)分，如2011年，文獻[16]針對Twitter選取用戶發(fā)布連續(xù)消息的時間間隔(Timestamp gaplt;10 s)和文本內(nèi)容相似性(Levenshteinlt;5或Jaccard＞0.6)2個特征，通過設(shè)置閾值來識別自動程序垃圾用戶，檢測結(jié)果的檢測精度為81.48%，召回率為82.07%。這種方法簡單易操作，但檢測效果不理想。

隨后的研究從2個方面展開，一方面選取盡可能多的特征，然后利用分類算法對微博用戶進行分類檢測。如文獻[17]針對Twitter定義39個文本內(nèi)容和23個用戶行為特征，采用支持向量機(SVM，support vector machine)對用戶進行分類檢測，大約有70%的垃圾用戶和96%的正常用戶被正確檢測。文獻[9]針對Twitter選出1.2萬個文本內(nèi)容特征，分別采用 5種分類器進行檢測，決策樹(C4.5)的準(zhǔn)確率為99.4%，檢測效果最佳。另一方面，針對所定義的特征不斷嘗試各種分類方法，除上述之外，包括樸素貝葉斯(Na?ve Bayes)[9]、k-最近鄰(k-NN,k-nearest neighbor)[18]、AdaBoost[19]、神經(jīng)網(wǎng)絡(luò)(neural network)[20]、隨機森林(random forest)[21]、數(shù)據(jù)流聚類方法(StreamKM++、Den-Stream)[22]等、混合馬爾可夫模型(mixture of Markov models)[23]等。

研究結(jié)果存在如下2種現(xiàn)象：1)針對同一個社交網(wǎng)絡(luò)，同一個分類算法在不同的文獻中分類效果迥異，如針對Twitter反垃圾，貝葉斯方法在文獻[24]效果最佳，而在文獻[9]效果最差；2)針對不同的社交網(wǎng)絡(luò)，同一個分類算法的分類效果均為最佳，如針對Twitter和MySpace，Decorate分類器的檢測效果均最佳[25]。于是會有如下問題，解決微博反垃圾問題的突破點優(yōu)先置于尋找分類特征還是改進分類檢測方法，特征越多檢測效果是否越好，新穎的方法是否可以顯著提高檢測效果。

本研究將以新浪微博為實例對該問題進行深入探討。首先，通過調(diào)用新浪微博開放的API接口收集新浪微博中山大學(xué)社區(qū)用戶的個人頁面信息，包括用戶個人資料、粉絲數(shù)、關(guān)注數(shù)、微博創(chuàng)建時間、微博內(nèi)容、微博數(shù)量，共計獲取了9萬個微博用戶的信息。接著，結(jié)合已有研究提出的區(qū)分度大的特征，從內(nèi)容信息、用戶行為和社會關(guān)系3個方面生成17個極具代表性的特征。最后，將7個特征選擇算法(其中6個為經(jīng)典算法，另外一個為本文提出的綜合特征選擇算法)與10個典型的分類識別學(xué)習(xí)算法組合進行實驗，從而回答上述問題。

2 相關(guān)工作

如前所述，早期的研究試圖找到少數(shù)幾個有利于分類檢測的關(guān)鍵特征(如文獻[16])，然而檢測效果非常不理想。鑒于此，研究者將特征的選取擴大到某個單一方面，常常會伴隨提出一些新穎的檢測方法。如文獻[26]檢測Twitter中熱門話題中的不相關(guān)內(nèi)容，僅選取文本特征，發(fā)現(xiàn)在5個典型的分類器中SVM的檢測準(zhǔn)確率最高。文獻[27]檢測人人網(wǎng)中的垃圾用戶，僅考慮用戶的社會活動行為，引入活動數(shù)量矩陣(user-activity count matrix)，矩陣的行向量表示一個特定用戶的活動數(shù)量，列向量對應(yīng)不同類型的社會活動，采用矩陣分解和支持向量機相結(jié)合方法對用戶進行了分類檢測。文獻[28]僅局限于Twitter中推文內(nèi)容的情感特征，利用結(jié)合矩陣分解的優(yōu)化模型來識別垃圾。文獻[29]針對商業(yè)網(wǎng)站在線評論，根據(jù)文本內(nèi)容中 URL連接關(guān)系的變化使用無監(jiān)督方法識別垃圾。文獻[30]限于Twitter中推文中包括的URL，共定義9個相關(guān)特征，利用SVM進行分類檢測。2015年，SIGKDD中的文獻[23]針對Tagged.com中用戶在時序上的相關(guān)關(guān)系特征，利用混合馬爾可夫模型來識別垃圾用戶。2015年，SIGIR中的文獻[31]專注于Twitter中的Hashtag特征，先選用k-NN算法過濾掉明顯的垃圾信息，后利用最大期望算法(EM,expectation-maximization)識別剩余的難于識別的垃圾信息。

僅使用少數(shù)幾個特征或某一特定方面的特征的反垃圾檢測不夠準(zhǔn)確，因為垃圾用戶易于推斷反垃圾檢測的主要依據(jù)特征，進而有針對性地偽裝為合法用戶，從而避免檢測[29,32,33]。

另一條研究主線是從多個側(cè)面定義盡可能多的特征，然后借助機器學(xué)習(xí)分類方法來檢測垃圾用戶。文獻[34]針對Twitter從文本內(nèi)容、用戶跟隨關(guān)系2個方面定義特征，利用優(yōu)化模型檢測垃圾用戶。文獻[35]對Twitter中新聞的可信度展開檢測，從文本內(nèi)容、用戶行為、主題和傳播 4類方面生成 74個特征，采用決策樹分類器對每條新聞的可信度進行檢測。文獻[36]從用戶拓?fù)?、文本?nèi)容和眾包 3方面生成18個特征，采用AdaBoost和支持向量機對垃圾信息進行分類檢測。文獻[25]針對 MySpace和Twitter中的垃圾用戶進行檢測，針對前者從個人注冊信息和私信文本內(nèi)容生成特征，針對后者從用戶行為和信息文本內(nèi)容生成特征，然后采用標(biāo)準(zhǔn)分類器對進行分類檢測，實驗表明不管是前者還是后者，Decorate分類器的檢測效果最佳。文獻[37]針對新浪微博垃圾用戶檢測，除了使用常用的特征(如URL鏈接比、關(guān)注粉絲比等)之外，還關(guān)注社交網(wǎng)絡(luò)傳播的有向特性，在此基礎(chǔ)上提出了基于統(tǒng)計特征與雙向投票的垃圾用戶檢測算法。2014年SIGIR中的文獻[38]利用 Web、郵件等中的垃圾信息進行特征映射遷移學(xué)習(xí)，采用矩陣分解與優(yōu)化模型結(jié)合的方式檢測Twitter等社交網(wǎng)絡(luò)中的垃圾。

特征選取的范圍不同，采用的分類方法也不同。當(dāng)特征類型單一時，有利于提出新穎的、高技術(shù)難度的分類方法，但受特征源單一的局限使容易被垃圾用戶識破，從而避免被檢測到。當(dāng)特征類型多時，垃圾用戶不易于躲避檢測，同時也不利于提出新的分類方法?？傊?，已有研究通常以用戶分類檢測效果好壞為唯一目標(biāo)，并沒有深入探討將研究重點優(yōu)先置于尋找分類特征還是改進分類方法會更有利于提高分類效果，本文以新浪微博為實例，對上述問題進行詳細(xì)討論。

3 問題形式化描述

3.1 問題形式化

設(shè)微博用戶集為U={u1,u2,…,uN}，其中，N為用戶數(shù)目。用戶ui擁有個人頁面Pi，包括個人資料、微博、關(guān)注/粉絲等信息。垃圾用戶檢測定義為根據(jù)事先抓取的用戶個人頁面 Pi和分類器Classifier預(yù)測用戶ui是正常用戶還是垃圾用戶，形式化為：Classifier∶ ui→{spammer,legitimate user}。

3.2 垃圾用戶

垃圾用戶通常是指在微博中展示、發(fā)表和傳播垃圾信息的用戶。通常不同的研究會從不同的角度賦予垃圾用戶不同的內(nèi)涵。

本文根據(jù)微博的實情將垃圾用戶分為內(nèi)容垃圾、僵尸垃圾、封號垃圾3類。內(nèi)容垃圾主要傳播黃色信息、虛假中獎信息、不良網(wǎng)站鏈接。僵尸垃圾可分為文本僵尸和異常轉(zhuǎn)發(fā)用戶，主要以兜售粉絲為目的。封號垃圾是指被官方關(guān)停的垃圾用戶，多數(shù)是由自動程序產(chǎn)生。

4 特征生成與分析

對于微博，人們在其上瀏覽、發(fā)布、轉(zhuǎn)發(fā)和評論信息，而信息傳播主要依賴于用戶間社會性的交往與互動，在微博中這種社會關(guān)系是由用戶間的“關(guān)注—被關(guān)注”體現(xiàn)出來，它是現(xiàn)實世界中社會關(guān)系在社交網(wǎng)絡(luò)中的復(fù)制和重構(gòu)?；诖耍鴳?yīng)該產(chǎn)生于內(nèi)容信息、用戶行為和社會關(guān)系3方面，故本文從這3個方面定義特征。

選取特征的基本原則是：根據(jù)統(tǒng)計指標(biāo)，挑揀區(qū)分度大的特征；使特征之間的相關(guān)性最??；保留中性特征。借鑒相關(guān)文獻中有代表性的特征，結(jié)合新浪微博的實際情況，經(jīng)過反復(fù)計算與分析，最終選取了17個特征，其統(tǒng)計指標(biāo)如表1所示。

4.1 社會特征

關(guān)注數(shù)(F1)為相關(guān)微博關(guān)注其他微博總數(shù)。垃圾用戶的關(guān)注數(shù)遠(yuǎn)遠(yuǎn)高于正常用戶，且垃圾用戶的關(guān)注數(shù)的離散度較正常用戶的小，其原因很可能是正常用戶常會根據(jù)自己的興趣有選擇地關(guān)注其他用戶，而以獲得更多粉絲為目的垃圾用戶，必然會大量關(guān)注其他用戶，期待所關(guān)注用戶回粉。

粉絲數(shù)(F2)為相關(guān)微博的粉絲總數(shù)，表明垃圾用戶的粉絲數(shù)要明顯少于正常用戶，且它的粉絲數(shù)的離散度較正常用戶的小很多，很可能因為垃圾用戶沒有正常的社會關(guān)系，導(dǎo)致很少有人會關(guān)注它。

互粉數(shù)(F3)為互為粉絲的數(shù)量，反映用戶的真實好友數(shù)量。正常用戶的互粉數(shù)遠(yuǎn)多于垃圾用戶的，且它的離散度較垃圾用戶的小很多。很可能因為真實的社會關(guān)系會給正常用戶帶來許多互粉數(shù)，而垃圾用戶即使主動關(guān)注了其他用戶，因其不在真實的社交關(guān)系中，故其他用戶回粉的概率很小。

關(guān)注粉絲比(F4)為關(guān)注數(shù)與粉絲數(shù)的比值。正常用戶的關(guān)注數(shù)少、粉絲多，而垃圾用戶的恰與其相反，故二者的比值更大，有利于提升檢測效果。

關(guān)注互粉比(F5)為關(guān)注數(shù)與互粉數(shù)的比值， 較F4更能放大正常用戶與垃圾用戶之間的差距，其原因可根據(jù)F1和F3的定義簡單推得。

4.2 用戶行為特征

用戶名復(fù)雜度(F6)為用戶名字的復(fù)雜度。部分垃圾用戶有著極其相似的命名特征，名字長度較長并且較復(fù)雜，定義如下(該特征和特征F15～F17均需先經(jīng)過分詞處理，采用了 NLPIR(natural language processing amp; information retrieval)中文分詞工具[39])。

其中，n表示詞的數(shù)量，k表示數(shù)詞的個數(shù)，lengthi表示第i個數(shù)詞的長度。正常用戶與垃圾用戶的名字復(fù)雜度的統(tǒng)計特征差距并不明顯，說明許多垃圾用戶常會起與正常用戶相近的名字，但該特征能夠較準(zhǔn)確地檢測出少部分垃圾用戶。

微博數(shù)(F7)為發(fā)布的微博總數(shù)。較正常用戶，內(nèi)容垃圾用戶通常會發(fā)布較多的博文，僵尸為了避免檢測也會發(fā)布適當(dāng)數(shù)量的微博。

月均微博(F8)為數(shù)據(jù)采集期間用戶每月所發(fā)的微博數(shù)，可衡量用戶所發(fā)微博的活躍頻度。垃圾用戶的活躍度要高于正常用戶的，特別是內(nèi)容垃圾用戶最為活躍，而僵尸最不活躍。

時間間隔(F9)為用戶最近一次發(fā)布微博距數(shù)據(jù)采集結(jié)束時刻的時間間隔(單位為天)。垃圾用戶的時間間隔均比較大，其原因是它會為某種利益目的進行短暫非法活動，當(dāng)活動結(jié)束就不再發(fā)送博文，如有些廣告用戶可能賣完某一商品就停用。

轉(zhuǎn)發(fā)比(F10)為轉(zhuǎn)發(fā)的微博與微博總數(shù)之比。較正常用戶，垃圾用戶常會轉(zhuǎn)發(fā)其他用戶的微博，以達到其擴散某些非法信息的目的。

4.3 內(nèi)容特征

URL鏈接比(F11)為含有URL的微博數(shù)量與微博總數(shù)之比。內(nèi)容垃圾用戶的 URL鏈接比最大且變異系數(shù)最小，其原因很可能是在微博中放置鏈接誘使用戶進入，從而達到某些惡意目的。

微博評論比(F12)為收到的評論數(shù)與微博總數(shù)之比。正常用戶會與好友就所發(fā)微博進行交流，而垃圾用戶由于其微博的信息價值低且沒有真正的“好友”，故所發(fā)的微博一般不會有用戶去評論。

原創(chuàng)微博評論比(F13)為收到的評論數(shù)與原創(chuàng)微博總數(shù)之比。較F12更具區(qū)別性。

微博平均長度(F14)為博文的平均長度。從統(tǒng)計指標(biāo)上看，正常用戶與垃圾用戶的差別不大，其原因可能是因內(nèi)容垃圾的平均長度較大造成的，但在特征選擇算法中該特征的排名相對靠前。

表1 特征的統(tǒng)計指標(biāo)

因垃圾用戶發(fā)布的微博具有很強的相關(guān)性，故文本內(nèi)容相似性是非常重要的反垃圾檢測特征，本文采用基于詞語級別的博文之間的余弦相似度(F15)、模相似度(F16)和詞語共享率(F17)3個特征，分別來從不同的時間粒度來度量微博之間的相似性。其中，F(xiàn)15計算用戶在相鄰兩天所發(fā)微博的相似程度，F(xiàn)16計算用戶在一天內(nèi)所發(fā)微博的相似程度，而F17沒有強調(diào)時間上的相似度。

5 特征選擇算法與分類器

5.1 特征選擇算法

特征選擇(feature selection)是指從原始特征集中選出與任務(wù)最相關(guān)的特征子集，使任務(wù)達到和特征選擇前近似甚至更好的效果。通過特征選擇，一些與任務(wù)無關(guān)和相互冗余的特征被刪除，無關(guān)和冗余特征不僅增加特征空間的維數(shù)，降低學(xué)習(xí)的效率，而且還增加噪聲數(shù)據(jù)的可能，從而干擾學(xué)習(xí)算法的學(xué)習(xí)過程，并最終影響分類模型的構(gòu)造。

特征選擇通常選擇與類別相關(guān)性強、且特征彼此間相關(guān)性弱的特征子集，由特征子集生成、子集評價、終止條件判斷和子集驗證4個步驟組成[40]。根據(jù)特征子集評價與分類學(xué)習(xí)算法的結(jié)合方式，特征選擇算法可主要分為Filter、Wrapper 2大類，前者使用獨立于學(xué)習(xí)算法的評估準(zhǔn)則來濾去任務(wù)無關(guān)特征和冗余特征，后者使用后續(xù)的分類準(zhǔn)確率作為評價函數(shù)?？傮w來說，前者識別精度較低，但識別效率高；后者與其相反。

本文選用的特征選擇算法如表2所示，F(xiàn)S1～FS5是有代表性的輸出特征權(quán)重的有監(jiān)督特征選擇算法，F(xiàn)S6是本文提出的綜合特征排名算法，F(xiàn)S7是以選擇最小特征組為輸出的有監(jiān)督特征選擇算法。

FS1～FS5特征選擇算法，因其評價標(biāo)準(zhǔn)的專一性分別有其最佳適用范圍，由于事先并不能預(yù)知哪個算法適合本文所涉及的應(yīng)用環(huán)境，為此本文提出了綜合特征排名算法FS6，基本思想是綜合考慮每個特征在不同的特征選擇算法中的貢獻，將在各個選擇算法結(jié)果中排名靠前的特征的權(quán)值加大，這樣既克服了每個利用了特征選擇算法因?qū)Ｒ恍远鴰淼娜秉c，又利用了其優(yōu)點，其計算過程如下。

已知特征集F={F1,F2,…,FM}，設(shè)第i個特征選擇算法的特征排名FRi=(Fi,1,Fi,2,…,Fi,M)(1≤i≤L,L為特征選擇算法數(shù)目)，在L個特征選擇算法的結(jié)果排名中，將前k(1≤k≤M)名的所有特征組成特征集Topk={Fi,j|1≤i≤L,1≤j≤k}。算法如下。

表2 特征選擇算法

1)計算特征Fj在 Topk中的出現(xiàn)概率，公式為為特征 Fj在 Topk中出現(xiàn)次數(shù)，sizeof(·)為Topk中特征數(shù)目。

2)計算特征Fj在Topk(F)中的出現(xiàn)概率的平均值，計算公式為

5.2 分類器

基于機器學(xué)習(xí)的分類檢測是通過學(xué)習(xí)訓(xùn)練出一個分類模型，其將數(shù)據(jù)集中的樣本映射到給定類別中的某一個類別。由于分類器對樣本數(shù)量的敏感度、特征之間相關(guān)度的敏感度等均不相同，故選擇不同的分類器得到的分類效果往往不同。本文使用了10個經(jīng)典的分類器（如表3所示），包括了相關(guān)文獻已驗證識別效果最好的分類器。

6 實驗與評估

6.1 數(shù)據(jù)標(biāo)注

基于對多次實驗結(jié)果的分析，共隨機抽取4 300個用戶，進行人工標(biāo)注，正常用戶為3 710個(包括199個新浪微博身份實名認(rèn)證的用戶)，約占總數(shù)的86.3%，垃圾用戶為590個(約13.7%)。在垃圾用戶中，內(nèi)容垃圾為208個(約4.8%)；僵尸垃圾為111個(約2.6%)；封號垃圾為271個(約6.3%)。

6.2 實驗設(shè)置

為了得到可信的結(jié)果，實驗采用 10折交叉驗證方法[54]來驗證分類性能，將原來樣本隨機分成10等份互不相交的樣本子集，每等份樣本的類別比例近似等于總樣本的，其中用9份樣本子集作為訓(xùn)練集建立分類檢測模型，而用剩下的1份樣本子集作為驗證集，然后交叉驗證重復(fù) 10次，使得每份樣本都被驗證一次。最終模型的預(yù)測分類性能評估指標(biāo)就是這10次分類評估指標(biāo)的平均值。

表3 分類器

6.3 特征選擇實驗

設(shè)包含M個特征的集合為F，C為類別特征，數(shù)據(jù)集中正樣本(正常用戶)與負(fù)樣本(垃圾用戶)比例為δ，數(shù)據(jù)集記為Dδ(F,C)。

實驗包括特征選擇、用戶分類檢測和實驗結(jié)果評估3部分。特征選擇是采用不同的特征選擇算法(FS)對數(shù)據(jù)集 Dδ(F,C)進行計算，按照特征對分類的貢獻計算出特征排名FR，或從M個特征中選出m(1≤m≤M)個最佳特征子集Fbest。

分別將δ=1(共 1 184條)和δ=5.9(共 4 101條)樣本數(shù)據(jù)輸入不同的特征選擇算法中，分別得到每個樣本比例對應(yīng)的特征選擇結(jié)果。其中，δ取不同的值是為了考察不平衡數(shù)據(jù)集對特征選擇結(jié)果的影響。

表4分別給出了6個經(jīng)典特征選擇算法的不同結(jié)果，其中CFS方法計算出最小數(shù)目的特征子集(用來與第6.4.2節(jié)的實驗結(jié)果對比分析)，而其他特征選擇算法均給出了特征排名。表5給出了綜合特征排名算法(CR)的結(jié)果。

6.4 分類檢測實驗

用戶分類檢測是將不同的分類器(Classifier)與不同的特征選擇算法(FS)進行組合lt;FS,Classifier＞對用戶進行識別，也即將特征選擇的結(jié)果作為分類器的輸入，然后根據(jù)度量指標(biāo)對分類結(jié)果進行評估分析，包括特征選擇算法對分類器的影響、特征數(shù)目對分類效果的影響、樣本數(shù)量對分類器的影響。

6.4.1 特征選擇對分類器影響分析

分別將δ=1和δ=5.9的6個不同特征選擇算法的結(jié)果與新浪微博中正常用戶與垃圾用戶真實比例δ=5.9的4 101條樣本數(shù)據(jù)輸入至10個經(jīng)典的分類器中，共計120組實驗，然后記錄每個實驗的6個分類結(jié)果評價指標(biāo)。本節(jié)使用準(zhǔn)確率(Acc)來衡量分類器對整個樣本的識別能力。由于不同分類檢測實驗結(jié)果的準(zhǔn)確率之間的絕對差距不是很大，為了在圖上將其顯著區(qū)分開，引入了準(zhǔn)確率之間的比率表示每組實驗中每個實驗結(jié)果的準(zhǔn)確率與最小者的比值。

圖1和圖2分別給出δ=1和δ=5.9的同一個特征選擇算法組合不同分類器的檢測結(jié)果的準(zhǔn)確率，從圖中可知，無論是δ=1還是δ=5.9，就單個特征選擇算法而言，其與不同分類器組合后的分類效果之間存在一定差異，但差異非常微小，如前所述，為了使差異顯著，圖中縱軸采用了準(zhǔn)確率之間的比率Ratio；就所有的特征選擇算法而言，分類器的性能較為穩(wěn)定，一些分類器無論與哪個特征選擇算法結(jié)合，其分類效果均表現(xiàn)出色。

表4 特征選擇實驗結(jié)果

表5 綜合特征算法實驗結(jié)果及特征在Topk中出現(xiàn)的平均概率

圖1 特征選擇方法與分類器組合的檢測性能(δ=1)

圖2 特征選擇方法與分類器組合的檢測性能(δ=5.9)

此外，就所有的特征選擇算法而言，特征選擇算法對分類器的支持在很大程度上具有穩(wěn)定性。具體來說，任意給定一個特征選擇算法FSx和一個分類器Classifiery，其組合的分類結(jié)果準(zhǔn)確率Acclt;FSx,Classifiery＞在 Acclt;FSi,Classifiery＞(i=1,…,6)中的排名與對于某一分類器 Classifierj(j=1,…,10且j≠y)Acclt;FSx,Classifierj＞在 Acclt;FSi,Classifierj＞(i=1,…,6)的排名基本一致。也即對于某個特征選擇算法，其與某個分類器組合的準(zhǔn)確率在該分類器與所有特征選擇算法組合的準(zhǔn)確率中的排名，大致可以代表該特征選擇算法與其他任一分類器組合在該分類器與所有特征選擇算法組合的準(zhǔn)確率中的排名。直觀而言，在圖2中，ReliefF與每個分類器組合的分類結(jié)果的準(zhǔn)確率排名均靠前。這一現(xiàn)象表明，新浪微博中反垃圾分類檢測效果在一定程度上依賴于特征組的選擇。

在特征選擇實驗中δ=5.9，其實驗結(jié)果較δ=1有明顯差別，在δ=1中，同一個分類器與不同特征選擇算法組合的分類準(zhǔn)確率較為接近，而在δ=5.9中，差距較為明顯，特別是與ReliefF特征選擇算法組合的分類器的分類效果更為突出，這表明在用戶比例接近真實的環(huán)境下新浪微博中特征選擇對分類器的影響較為明顯。此外，在δ=1中，分類效果整體上較好的排名前3位的特征選擇算法分別是IG、CR和SU，而在δ=5.9中，排名前 3位的特征選擇算法分別是ReliefF、CR和IG；無論δ=1還是δ=5.9，分類效果整體上較好的排名前2位的均是LR和LMT，排名第3位的分別為 ABM1(δ=1)和 BA(δ=5.9)。該現(xiàn)象說明在不同的用戶比例下特征的選擇對分類器的影響不完全相同，另外，本文提出的CR方法排名第2，雖不是最好的方法，但起到了均衡其他特征選擇方法的效果。

總之，整體而言，對于新浪微博的垃圾用戶檢測，特征組的選擇較分類器的選擇更為重要，也即特征組的選取較分類器的改進更為重要。

6.4.2 特征數(shù)目對分類效果影響分析

探尋特征數(shù)目對分類效果的影響，是否存在最小特征數(shù)目。實驗針對δ=5.9，選取排名前3的特征選擇算法(分別為ReliefF、CR和IG)與排名前3的分類器(LR、LMT和BA)進行組合，從而得到特征重要性排名及數(shù)目與準(zhǔn)確率指標(biāo)之間的關(guān)系，如圖3所示，橫坐標(biāo)為特征的數(shù)目且根據(jù)特征對分類結(jié)果的貢獻程度由大至小排列(在圖中，因在所有特征選擇方法中，第17個特征相同，為了降低計算量，該特征沒有參與分類計算)，縱坐標(biāo)為3個不同分類器與不同的特征選擇算法組合的準(zhǔn)確率的平均值，及圖中l(wèi)t;ReliefF,.＞表示 ReliefF特征選擇算法分別與分類器LR、LMT和BA組合的準(zhǔn)確率的平均值。

圖3 特征數(shù)目對準(zhǔn)確率的影響(δ=5.9)

如果忽略局部的波動，總體來說，準(zhǔn)確率隨著特征數(shù)目的逐漸增加呈現(xiàn)拋物線形狀，隨著特征數(shù)目的增加準(zhǔn)確率會逐漸升高，達到峰值(從圖3知特征數(shù)目為10個時準(zhǔn)確率達到峰值)，然后下降。該結(jié)果表明在分類檢測中僅有少數(shù)幾個關(guān)鍵特征是不夠的，只有特征數(shù)目達到一定的數(shù)量，準(zhǔn)確率才能達到峰值；當(dāng)然，過多的冗余特征又會導(dǎo)致準(zhǔn)確率的降低。此外，值得一提的是，此處的最小特征數(shù)目10個與第6.3節(jié)采用CFS算法選出的最小特征數(shù)目5個(如表4所示)所示不盡一致，需進一步討論。

6.4.3 最佳特征來源分布分析

旨在分析最佳特征的來源分布。在6.4.2節(jié)實驗中，對于δ=5.9樣本，取排名第 1的特征選擇算法(ReliefF)中的最佳特征子集Fbest={F5,F1,F10,F4,F17,F14,F9,F11,F13,F3}。其中{F5,F1,F4,F3}屬于社會特征，{F10,F9}屬于用戶行為特征，{F17,F14,F11,F13}屬于內(nèi)容特征，也即最佳特征來源于內(nèi)容信息、用戶行為和社會關(guān)系 3個方面。這一結(jié)果表明需要從多側(cè)面生成特征，這將有助于提高識別準(zhǔn)確率。

6.4.4 樣本數(shù)量對分類效果影響分析

旨在分析樣本數(shù)量對分類器性能的影響，掌握分類器性能收斂與樣本數(shù)量之間的關(guān)系，并探尋實驗中所需的最佳訓(xùn)練樣本數(shù)量，進一步說明之前的實驗對樣本數(shù)量的假設(shè)是合理的。

根據(jù) 6.4.2節(jié)實驗，從所有樣本集中隨機抽取不同數(shù)量的樣本，以200為步長使樣本數(shù)量從400逐漸增加到 4 000。將不同的樣本數(shù)目輸入至不同的分類器中，進行分類檢測實驗，觀察樣本數(shù)量與準(zhǔn)確率之間的變化關(guān)系。圖4給出了10個分類檢測算法準(zhǔn)確率的統(tǒng)計曲線，從圖中可以看出，雖然不同分類器的準(zhǔn)確率各有差異，但是總體的趨勢都是特征數(shù)目在1 000到2 000之間時準(zhǔn)確率的變化發(fā)生由快到慢的轉(zhuǎn)折。

圖4 10個分類檢測算法的準(zhǔn)確率

由于圖中所有曲線的變化趨勢相似，因此計算每個樣本數(shù)目下 10個分類檢測算法準(zhǔn)確率的平均值，如圖 5所示的 avgAcc曲線，其擬合結(jié)果為fitCurve曲線。對于擬合曲線，當(dāng)樣本數(shù)目達到3 000以上時，只增大樣本數(shù)目已經(jīng)很難使分類器的準(zhǔn)確率得到提高。這說明有關(guān)樣本數(shù)量假設(shè)合理可行。

圖5 樣本數(shù)量對準(zhǔn)確率的影響

7 結(jié)束語

本文旨在回答在微博反垃圾中優(yōu)先將研究重點投入到尋找分類特征還是改進分類方法。以新浪微博為例，實驗結(jié)果表明特征組的選擇較分類器的改進更為重要，需從內(nèi)容信息、用戶行為和社會關(guān)系多側(cè)面定義特征，且特征并非越多檢測效果越好。鑒于此，希望未來在特征的選取方面投入更多的工作，以便在反垃圾研究中有進一步的突破。盡管實驗是以新浪微博為例展開，但其結(jié)果同樣適用于騰訊微博、搜狐微博等微博的反垃圾。

[1]Available online[EB/OL]. http://news.xinhuanet.com/2013-07/04/c_116410610.htm.

[2]Available online[EB/OL]. http://it.people.com.cn/n/2015/0212/c1009-26552746.html.

[3]SPIRIN N,HAN J W. Survey on web spam detection: principles and algorithms[J]. ACM SIGKDD Explorations Newsletter,2012,13(2):50-64.

[4]MUKHERJEE A,LIU B,GLANCE N S. Spotting fake reviewer groups in consumer reviews[C]//The WWW. c2012: 191-200.

[5]WANG T Y,WANG G,LI X. Characterizing and detecting malicious crowdsourcing[C]//The ACM SIGCOMM. c2013: 537-538.

[6]WANG G,WILSON C,ZHAO X H. Serf and turf: crowdturfing for fun and profit[C]//The WWW. c2012: 679-688.

[7]SRIDHARAN V,SHANKAR V,GUPTA M. Twitter games: how successful spammers pick targets[C]//The ACSAC. c2012: 389-398.

[8]STRINGHINI G,KRUEGEL C,VIGNA G. Detecting spammers on social networks[C]//The ACSAC. c2010: 1-9.

[9]IRANI D,WEBB S,PU C. Study of static classification of social spam profiles in MySpace[C]//The ICWSM. c2010: 82-89.

[10]GAO H Y,HU J,WILSON C. Detecting and characterizing social spam campaigns[C]//The CCS. c2010: 681-683.

[11]AGGARWAL A,ALMEIDA J M,KUMARAGURU P. Detection of spam tipping behaviour on foursquare[C]//The WWW. c2013:641-648.

[12]GAO Q,ABEL F,HOUBEN G J. A comparative study of user’s microblogging behavior on Sina weibo and Twitter[C]//The 20th International Conference on User Modeling. c2012: 88-101.

[13]YU L,ASUR S,HUBERMAN BA. What trends in Chinese social media[C]//SNA-KDD Workshop. c2011: 1-10.

[14]YU LL,ASUR S,HUBERMAN B A. Artificial inflation: the real story of trends and trend-setters in Sina weibo[C]//The International Con-fernece on Social Computing. c2012: 514-519.

[15]樊鵬翼,王暉,姜志宏,等. 微博網(wǎng)絡(luò)測量研究[J]. 計算機研究與發(fā)展,2012,49(4):691-699.FAN P Y,WANG H,JIANG Z H,et al. Measurement of microblogging network[J]. Journal of Computer Research Development,2012,49(4):691-699.

[16]SHARMA P,BISWAS S. Identifying spam in Twitter trending topics.technical report[R]. USC(University of Southern California)Information Sciences Institute,2011.1-4.

[17]BENEVENUTO F,MAGNO G,RODRIGUES T. Detecting spammers on Twitter[C]//The 7th Collaboration,Electronic messaging,Anti-Abuse and Spam Conference. c2010: 1-9.

[18]HASTIE T,TIBSHIRANI R. DISCRIMINANT adaptive nearest neighbor classification[J]. IEEE Trans. on Pattern Analysis and Machine Intelligence. 1996,18(6):607-616.

[19]FREUND Y,SCHAPIRE RE. A decision-theoretic generalization of on-line learning and an application to boosting[J]. Journal of Computer and System Sciences,1997,55(1):119-139.

[20]ORR M J L. Regularization in the selection of radial basis function centres[J]. Neural Computation,1995,7(3):606-623.

[21]HO T K. The random subspace method for constructing decision forests[J]. IEEE Trans. on Pattern Analysis and Machine Intelligence,1998,20(8):832-844.

[22]MILLER Z,DICKINSON B,DEITRICK W,et al. Twitter spammer detection using data stream clustering[J]. Information Sciences,2014,260(1): 64-73.

[23]SHOBEIR F,JAMES F,MADHUSHDANA S,et al. Collective spammer detection in evolving multi-relation social networks[C]//The KDD.c2015: 1769-1778.

[24]WANG A H. Detecting spam bots in online social networking sites: a machine learning approach[C]//DBSec. c2010: 335-342.

[25]LEE K,CAVERLEE J,WEBB S. Uncovering social spammers: social honeypots+machine learning[C]//The SIGIR. c2010: 435-442.

[26]MARTINEZ R J,ARAUJO L. Detecting malicious tweets in trending topics using a statistical analysis of language[J]. Expert Systems with Applications,2013 40(8): 2992-3000.

[27]ZHU Y,WANG X,ZHONG E H. Discovering spammers in social networks[C]//The AAAI. c2012: 1-7.

[28]HU X,TANG J L,GAO HJ,et al. Social spammer detection with sentiment information[C]//The ICDM. c2014: 180-189.

[29]TAN E,GUO L,CHEN S,et al. Unik: unsupervised social network spam detection[C]//The CIKM. c2013: 479-488.

[30]ZHANG X,ZHU S,LIANG W. Detecting spam and promoting campaigns in the twitter social network[C]//The ICDM. c2012: 1194-1199.

[31]SURENDRA S,AIXIN S. HSpam14: a collection of 14 million tweets for hashtag-oriented spam research[C]//The SIGIR. c2015: 9-13.

[32]YANG C,HARKREADER R C,ZHANG J. Analyzing spammers'social networks for fun and profit: a case study of cyber criminal ecosystem on twitter[C]//The WWW. c2012: 71-80.

[33]HU X,TANG J L,LIU H. Online social spammer detection[C]//The AAAI. c2014: 1-7.

[34]HU X,TANG J L,ZHANG Y C,et al. Social spammer detection in microblogging[C]//The IJCAI. c2013: 177-188.

[35]CASTILLO C,MENDOZA M,POBLETE B. Information credibility on twitter[C]//The WWW. c2011: 675-684.

[36]RATKIEWICZ J,CONOVER M,MEISS M. Detecting and tracking political abuse in social media[C]//The ICWSM. c2011: 1-8.

[37]丁兆云,周斌,賈焰,等. 微博中基于統(tǒng)計特征與雙向投票的垃圾用戶發(fā)現(xiàn)[J]. 計算機研究與發(fā)展,2013,50(11): 2336-2348.DING Z Y,ZHOU B,JIA Y,et al. Detecting spammers with a bidirectional vote algorithm based on statistical features in microblogs[J].Journal of Computer Research and Development,2013,50(11):2336-2348.

[38]HU X,TANG J L,ZHANG Y C,LIU H. Leveraging knowledge across media for spammer detection in microblogging[C]//The ACM SIGIR. c2014: 547-556.

[39]Available online[EB/OL]. http://ictclas.nlpir.org/.

[40]DASH M,LIU H. Feature selection for classifications[J]. Intelligent Data Analysis,1997,16(21):131-156.

[41]LIU H,SETIONO R. CHI2: feature selection and discretization of numeric attributes[C]//The ICTAI. c1995: 338-391.

[42]NOWOZIN S. Improved information gain estimates for decision tree induction[C]//ICML. c2012: 1-8.

[43]KONONENKO I. Estimating attributes: analysis and extensions of RELIEF[C]//The ECML-PKDD. c1994: 171-182.

[44]GUYON I,WESTON J,BARNHILL SMD. Gene selection for cancer classification using support vector machines[J]. Machine Learning,2002,46(1-3):389-422.

[45]STECK J B. Netpix: a method of feature selection leading to accurate sentiment-based classification models[D]. Central Connecticut State University,2005.

[46]HALL M A. Correlation-based feature selection for discrete and numeric class machine learning[C]//The ICML. c2000: 359-366.

[47]JOHN GH,EDU S,LANGLEY P. Estimating continuous distributions in Bayesian classifiers[C]//The UAI. c1995: 338-345.

[48]KEERTHI S S,DUAN K,SHEVADE S K. A fast dual algorithm for kernel logistic regression[J]. Machine Learning,2005,61(1):151-165.

[49]CORTES C,VAPNIK V N. Support-vector networks[J]. Machine Learning,1995,20(3):273-297.

[50]ORR M J L. Regularization in the selection of radial basis function centres[J]. Neural Computation,1995,7(3):606-623.

[51]BREIMAN L. Bagging predictors[J]. Machine Learning,1996,24(2):123-140.

[52]QUINLAN J R. C4.5: programs for machine learning[M]. Morgan Kaufmann Publishers,San Mateo,California,1993.

[53]LANDWEHR N,HALL M,FRANK E. Logistic model trees[J]. Machine Learning,2005,59(1):161-205.

[54]KOHAVI R. A study of cross-validation and bootstrap for accuracy estimation and model selection[C]//The IJCAI. c1995: 1137-1143.

Feature importance analysis for spammer detection in Sina Weibo

ZHANG Yu-xiang1,2,3,SUN Yu1,YANG Jia-hai2,3,ZHOU Da-lei4,MENG Xiang-fei5,XIAO Chun-jing1

(1.College of Computer Science,Civil Aviation University of China,Tianjin 300300,China;2.Institute for Network Sciences and Cyberspace,Tsinghua University,Beijing 100084,China;3.Tsinghua National Laboratory for Information Science and Technology (TNList),Beijing 100084,China;4.Institue of Network Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China;5. State Key Laboratory of Virtual Reality Technology and Systems,Beihang University,Beijing 100876,China)

Microblog has drawn attention of not only legitimate users but also spammers. The garbage information provided by spammers handicaps users’ experience significantly. In order to improve the detection accuracy of spammers,most existing studies on spam focus on generating more classification features or putting forward new classifiers. Which kind of issues would be put the high priority of an enormous amount of research effort into? Are extensive features or novel classifiers better for the detection accuracy of spammers? It is tried to address these questions through combining different feature selection methods with different classifiers on a real Sina Weibo dataset. Experimental results show that selected features are more important than novel classifiers for spammer detection. In addition,features should be derived from a wide range,such as text contents,user behaviors,and social relationship,and the dimension of features should not be too high. These results will be useful in finding the breakpoint of Microblog anti-spam works in the future.

Sina Weibo,feature definition,feature selection,spammer detection

s:The National Basic Research Program of China (973 Program)(No.2009CB320505),The National Key Technology Ramp;D Program of China(No.2008BAH37B05),The National Natural Science Foundation of China (No.61170211,No.U1533104,No.61301245),Ph.D. Programs Foundation of Ministry of Education of China (No.20110002110056)

TP391

A

2015-11-23；

2016-04-24

國家重點基礎(chǔ)研究發(fā)展計劃(“973”計劃)基金資助項目(No.2009CB320505)；國家科技支撐計劃基金資助項目(No.2008BAH37B05)；國家自然科學(xué)基金資助項目(No.61170211,No.U1533104,No.61301245)；教育部博士點基金資助項目(No.20110002110056)

10.11959/j.issn.1000-436x.2016152

張宇翔（1975-），男，山西五寨人，博士，中國民航大學(xué)副教授，主要研究方向為社會網(wǎng)絡(luò)分析、推薦技術(shù)。

孫菀（1991-），女，山東煙臺人，中國民航大學(xué)碩士生，主要研究方向為社會網(wǎng)絡(luò)分析與推薦技術(shù)。

楊家海（1966-），男，浙江云和人，清華大學(xué)教授、博士生導(dǎo)師，主要研究方向為計算機網(wǎng)絡(luò)管理與測量、云計算與大數(shù)據(jù)等。

周達磊（1992-），男，江蘇連云港人，北京郵電大學(xué)碩士生，主要研究方向為網(wǎng)絡(luò)分析。

孟祥飛（1993-），男，山西太原人，北京航空航天大學(xué)碩士生，主要研究方向為數(shù)據(jù)分析技術(shù)。

肖春景（1978-），女，河北唐山人，中國民航大學(xué)講師，主要研究方向為數(shù)據(jù)挖掘與推薦系統(tǒng)。