譚 侃 高 旻 李文濤 田仁麗 文俊浩 熊慶宇

基于雙層采樣主動學(xué)習(xí)的社交網(wǎng)絡(luò)虛假用戶檢測方法

譚 侃1,2高 旻1,2李文濤1,3田仁麗1,4文俊浩1,2熊慶宇1,2

社交網(wǎng)絡(luò)的飛速發(fā)展給用戶帶來了便捷,但是社交網(wǎng)絡(luò)開放性的特點使得其容易受到虛假用戶的影響.虛假用戶借用社交網(wǎng)絡(luò)傳播虛假信息達到自身的目的,這種行為嚴(yán)重影響著社交網(wǎng)絡(luò)的安全性和穩(wěn)定性.目前社交網(wǎng)絡(luò)虛假用戶的檢測方法主要通過用戶的行為、文本和網(wǎng)絡(luò)關(guān)系等特征對用戶進行分類,由于人工標(biāo)注用戶數(shù)據(jù)需要的代價較大,導(dǎo)致分類器能夠使用的標(biāo)簽樣本不足.為解決此問題,本文提出一種基于雙層采樣主動學(xué)習(xí)的社交網(wǎng)絡(luò)虛假用戶檢測方法,該方法使用樣本不確定性、代表性和多樣性3個指標(biāo)評估未標(biāo)記樣本的價值,并使用排序和聚類相結(jié)合的雙層采樣算法對未標(biāo)記樣本進行篩選,選出最有價值的樣本給專家標(biāo)注,用于對分類模型的訓(xùn)練.在Twitter、Apontador和Youtube數(shù)據(jù)集上的實驗說明本文所提方法在標(biāo)簽樣本數(shù)量不足的情況下,只使用少量有標(biāo)簽樣本就可以達到與有監(jiān)督學(xué)習(xí)接近的檢測效果;并且,對比其他主動學(xué)習(xí)方法,本文方法具有更高的準(zhǔn)確率和召回率,需要的標(biāo)簽樣本數(shù)量更少.

社交網(wǎng)絡(luò),虛假用戶,主動學(xué)習(xí),樣本多樣性

Twitter、Facebook、Renren等社交媒體網(wǎng)絡(luò)發(fā)展迅速,已成為人們交流、分享的熱門平臺[1?2].然而,在線社交網(wǎng)絡(luò)蓬勃發(fā)展的同時,也面臨著虛假信息和虛假用戶泛濫的問題[3].虛假用戶,也叫做垃圾用戶,是指在網(wǎng)絡(luò)中傳播垃圾信息和錯誤信息來達到某種目的的一類用戶,如推送廣告、網(wǎng)絡(luò)釣魚、傳播惡意軟件、損壞他人信譽等[3?4].這種行為嚴(yán)重影響著社交網(wǎng)絡(luò)的安全性和穩(wěn)定性.據(jù)統(tǒng)計,Facebook上有8300萬(8.7%)的虛假用戶1http://www.bbc.com/news/technology-19093078,Twitter中最受歡迎的10個用戶的追隨者中有27%以上的虛假用戶2http://www.webpronews.com/.為了逃避社交網(wǎng)絡(luò)中的防御系統(tǒng),虛假用戶采取各種策略進行偽裝,如竊取正常用戶的用戶概貌,模仿正常用戶的各種行為等.由于社交網(wǎng)絡(luò)本身具有開放性,社交網(wǎng)絡(luò)中的用戶不僅與現(xiàn)實世界中的親人、朋友建立關(guān)系,同時還與其他陌生用戶建立關(guān)系、分享信息.在Twitter、新浪微博等有向社交網(wǎng)絡(luò)中,虛假用戶更是能夠輕易地與其他用戶建立關(guān)系,虛假用戶之間還能通過互相關(guān)注提高雙方在網(wǎng)絡(luò)中的可信度[5].另外也有一些正常用戶出于禮貌,對他的所有追隨者同樣予以關(guān)注[6].社交網(wǎng)絡(luò)的這些特征使得虛假用戶的檢測比其他網(wǎng)絡(luò)更難.

盡管社交網(wǎng)絡(luò)虛假用戶檢測存在諸多挑戰(zhàn),國內(nèi)外仍有不少研究者對此提出了有效的解決辦法.監(jiān)督型的檢測方法旨在從大量的已標(biāo)記的正常用戶和虛假用戶集中提取能夠有效區(qū)分兩者的特征,例如文本特征[7?9]、網(wǎng)絡(luò)結(jié)構(gòu)特征[10?12]、關(guān)系圖特征[13]等,并利用機器學(xué)習(xí)分類方法對未標(biāo)記的用戶進行分類.然而,這種監(jiān)督型檢測方法需要大量已標(biāo)記數(shù)據(jù),人工標(biāo)注大量數(shù)據(jù)又是耗時耗力的,因而難以實施.無監(jiān)督的檢測方法則存在假陽性高,并且魯棒性差的問題[14].針對已有方法存在的問題,本文提出使用主動學(xué)習(xí)方法檢測虛假用戶.主動學(xué)習(xí)[15]使用極少量的標(biāo)簽樣本訓(xùn)練初始分類器,迭代選擇信息量最大的未標(biāo)記樣本加入訓(xùn)練集,以此提高分類器的泛化能力.然而,文獻[16]表明傳統(tǒng)的主動學(xué)習(xí)采樣方法容易選出樣本中的離群點,并且存在信息冗余問題.

為了解決離群點問題,本文提出基于不確定性和代表性的采樣算法選擇未標(biāo)記數(shù)據(jù)集中的樣本.樣本的代表性,是指樣本與其他未標(biāo)記樣本或近鄰樣本的平均相似度,通常使用樣本密度進行衡量.一般來說,離群點樣本與其他樣本的距離較遠,因而樣本密度較非離群點小,根據(jù)這一特性,可將樣本密度與不確定性線性組合,從而選出不確定性高的非離群點樣本.除此之外,代表性強的樣本能夠有效提高訓(xùn)練集對整體樣本空間的覆蓋率,更好地提升分類器的泛化能力.傳統(tǒng)主動學(xué)習(xí)方法的另一個問題是信息冗余.主動學(xué)習(xí)的每一次迭代都將選擇多個新的樣本加入訓(xùn)練集,由于評估樣本價值的標(biāo)準(zhǔn)和方式相同,容易造成新樣本彼此之間的相似度過高,產(chǎn)生信息冗余.為了解決信息冗余問題,本文提出基于多樣性的采樣算法,通過評估多個樣本點間的平均距離來保證新樣本的整體多樣性.因此,本文方法使用雙層采樣選擇未標(biāo)記數(shù)據(jù)集中的樣本.第一層采樣結(jié)合樣本不確定性和代表性,選擇出不確定性高且代表性高的樣本,剔除未標(biāo)記樣本集中的離群點;第二層通過整體多樣性考量來減少信息冗余,選擇出整體多樣性最大的一組樣本集合作為最終的選擇樣本.

本文的組織結(jié)構(gòu)如下:第1節(jié)介紹社交網(wǎng)絡(luò)虛假用戶檢測的研究現(xiàn)狀和常用的主動學(xué)習(xí)策略;第2節(jié)詳細描述本文提出的檢測框架和算法;第3節(jié)則對本文實驗過程和實驗結(jié)果進行闡述與分析;最后,在第4節(jié)總結(jié)本文的工作,并對后續(xù)研究進行展望.

1 相關(guān)研究

社交網(wǎng)絡(luò)虛假用戶檢測從本質(zhì)上來說是一個二類分類問題[13],本節(jié)分析了基于監(jiān)督型、無監(jiān)督和半監(jiān)督學(xué)習(xí)的檢測方法.針對已有方法的不足,本文提出使用主動學(xué)習(xí)方法來檢測虛假用戶.因此,本節(jié)還對主動學(xué)習(xí)中常用的選擇策略進行了介紹.

1.1 社交網(wǎng)絡(luò)虛假用戶檢測的研究現(xiàn)狀

近年來,社交網(wǎng)絡(luò)中虛假用戶的檢測研究已經(jīng)獲得了國內(nèi)外研究者的關(guān)注,研究者們提出了多種針對不同的社交網(wǎng)絡(luò)平臺上的虛假用戶檢測研究,包括Twitter[17?18]、Facebook[3]、Youtube[19]和MySpace[20].已有的檢測算法可以分為有監(jiān)督、無監(jiān)督和半監(jiān)督3類.

基于監(jiān)督學(xué)習(xí)的檢測方法通過提取社交網(wǎng)絡(luò)用戶的各種特征來訓(xùn)練分類模型.Benevenuto等[19]基于用戶特征和視頻特征對Youtube的用戶進行建模.類似地,Lee等[20]通過向網(wǎng)絡(luò)中加入誘捕節(jié)點引誘虛假用戶主動關(guān)注,分析出虛假用戶不同于正常用戶的行為特征,并據(jù)此提出一種基于誘捕系統(tǒng)的檢測框架識別MySpace和Twitter中的虛假用戶.除了行為特征和文本特征,許多研究者也從社交網(wǎng)絡(luò)圖入手,提出了不同的檢測方法.Song等[21]監(jiān)督用戶發(fā)送消息的行為軌跡,通過分析發(fā)送者和接收者之間的距離和連通性來識別虛假用戶.Hu等[11]則提出一種結(jié)合文本特征和網(wǎng)絡(luò)結(jié)構(gòu)的框架用于檢測Twitter網(wǎng)絡(luò)中的虛假用戶.程曉濤等[13]運用Web信息挖掘技術(shù)[22]挖掘社交網(wǎng)絡(luò)中的關(guān)系圖特征,對檢測虛假用戶提出新的方案.盡管監(jiān)督型的檢測方法準(zhǔn)確率高,但其需要大量的樣本標(biāo)簽,人工標(biāo)注大量樣本又是耗時耗力的,導(dǎo)致實施成本過高.于是又有研究者提出了非監(jiān)督的監(jiān)測模型.

非監(jiān)督的檢測模型主要利用社交網(wǎng)絡(luò)的拓撲關(guān)系識別網(wǎng)絡(luò)中的異常點.Gao等[3]提出利用文本和 URLs相似度對 Facebook中的帖子進行聚類的方法,其假設(shè)虛假用戶和正常用戶之間不存在相關(guān)關(guān)系.Tan等[23]對這種假設(shè)提出了異議,他們認(rèn)為虛假用戶需要通過和正常用戶建立關(guān)系來提高自身的可信度,為此Tan等提出了一種結(jié)合社交關(guān)系圖和用戶鏈接圖的非監(jiān)督檢測方法.該方法先通過社交關(guān)系圖確定部分正常用戶,然后根據(jù)這些用戶的鏈接圖識別虛假用戶.Zhao等[24]則從Twitter中的推文內(nèi)容入手,基于動態(tài)查詢擴展的方法構(gòu)造推文圖,并使用異常檢測的方法識別虛假推文,從而檢測虛假用戶.相比監(jiān)督型的檢測方法,非監(jiān)督的方法盡管不需要人工標(biāo)注數(shù)據(jù),但假陽性率高,并且魯棒性沒有監(jiān)督型算法好[14].

最近,Li等[14]結(jié)合監(jiān)督型和非監(jiān)督型的方法,提出一種結(jié)合信任傳播的半監(jiān)督檢測框架.與該框架中利用PageRank傳播樣本標(biāo)簽的方法不同,本文提出的雙層采樣主動學(xué)習(xí)方法通過評估樣本的不確定性、代表性和多樣性從未標(biāo)記樣本中選擇少量樣本,并對選擇出的樣本進行人工標(biāo)注.

1.2 主動學(xué)習(xí)策略概述

主動學(xué)習(xí)是為了解決現(xiàn)實中標(biāo)簽數(shù)據(jù)不足,標(biāo)注數(shù)據(jù)耗時耗力的問題而提出的.與傳統(tǒng)的被動學(xué)習(xí)不同,主動學(xué)習(xí)能夠控制分類器對輸入樣本的選擇,從未標(biāo)記樣本中選擇出信息量最高的數(shù)據(jù),從而獲得更好的學(xué)習(xí)效率與學(xué)習(xí)效果.

一個主動學(xué)習(xí)模型可以建模成5個部分[16]:

其中C為一個或一組分類器,Q為選擇引擎,用來查詢未標(biāo)記樣本中的高信息量樣本,L、U分別表示已標(biāo)記數(shù)據(jù)集和未標(biāo)記數(shù)據(jù)集,O為專家,負責(zé)確定未標(biāo)記樣本的標(biāo)簽.主動學(xué)習(xí)的過程如圖1所示.

主動學(xué)習(xí)根據(jù)選擇未標(biāo)記樣本方式的不同,可以分為成員查詢綜合(Membership query synthesis)、基于流(Stream-based)的主動學(xué)習(xí)和基于池(Pool-based)的主動學(xué)習(xí)[25].其中,基于池的主動學(xué)習(xí)是當(dāng)前應(yīng)用最廣泛的采樣策略.根據(jù)選擇未標(biāo)記樣例的標(biāo)準(zhǔn)不同,基于池的采樣策略又可以分為以下幾種:基于不確定性的采樣策略、基于版本空間縮減的采樣策略、基于模型改變期望的采樣策略以及基于誤差縮減的采樣策略.

基于不確定性的采樣(Uncertainty sampling)使用概率型分類器直接估計未標(biāo)記樣本的后驗概率值,選擇最難被分類器區(qū)分的樣本.信息熵[26]是不確定性采樣中最常用的度量樣本不確定性的方法,計算公式如式(2):

其中,y?表示樣本x的預(yù)測標(biāo)簽,P(y?|x)表示樣本x被預(yù)測為某一特定標(biāo)簽的概率.

圖1 主動學(xué)習(xí)整體流程Fig.1 The whole fl ow of active learning

基于版本空間縮減的采樣策略的主導(dǎo)思想是選擇能最大程度縮減版本空間的未標(biāo)記樣本進行標(biāo)記.委員會投票選擇算法(Query-by-committee, QBC)[26]是這類采樣策略中應(yīng)用最廣泛的算法.該算法主要分為2個步驟:首先是構(gòu)建多個學(xué)習(xí)模型組成委員會,然后由委員會中的學(xué)習(xí)模型分別對未標(biāo)記樣本的預(yù)測標(biāo)簽進行投票,選出投票最不一致的樣本.Tuia等[27]提出的EQB(Entropy queryby-bagging)算法利用式(3)評估這種不一致性.

其中,N 表示委員會預(yù)測樣本 x的標(biāo)簽個數(shù), P(y?=ω|x)表示樣本x被預(yù)測為某一特定標(biāo)簽的投票概率.

模型改變期望(Expected model change)[28]的主動學(xué)習(xí)框架基于決策理論,通過評估未標(biāo)記樣本對當(dāng)前模型的影響程度,選擇出對模型影響最大的樣本進行標(biāo)記.代表性方法是EGL(Expected gradient length),該方法可應(yīng)用于任意基于梯度下降方法的訓(xùn)練模型.令fθ為基于梯度的學(xué)習(xí)模型,L表示原本的訓(xùn)練數(shù)據(jù)集,▽fθ(L)代表學(xué)習(xí)模型在參數(shù)θ時的梯度,則▽fθ(L∪(x,y))代表加入新的標(biāo)記樣本后學(xué)習(xí)模型的梯度.該算法使用式(4)對樣本進行選擇,‖·‖表示梯度向量在歐氏空間中的長度.

基于誤差縮減的采樣策略(Expected error reduction)[28]通過減少分類器誤差提高學(xué)習(xí)算法的泛化能力.算法的思路是將每一個未標(biāo)記樣本標(biāo)記后加入訓(xùn)練集,并重新訓(xùn)練分類器,計算分類器的誤差變化結(jié)果,最終選擇能夠最大程度縮減分類器誤差的樣本.令L表示原本的訓(xùn)練數(shù)據(jù)集, L+=L+(x,y)表示加入樣本(x,y)后的數(shù)據(jù)集.由于樣本x的標(biāo)簽是未知的,所以我們需要對y的所有取值進行概率化.式(5)、(6)分別描述使用0/1誤差和log誤差函數(shù)下的樣本選擇標(biāo)準(zhǔn):

由于這種直接估計模型誤差的方法復(fù)雜度高、計算量大,因而部分研究者提出了一些替代的標(biāo)準(zhǔn). Zhang等[29]引入Fisher信息函數(shù)來計算每一個樣本的Fisher得分并構(gòu)造Fisher矩陣,判別模型中樣本標(biāo)記對模型誤差的影響程度.Roy等[30]通過比較概率分布函數(shù)的變化來估計樣本的未來期望誤差,并在樸素貝葉斯模型下大幅度提高了分類器的精度.

上述主動學(xué)習(xí)算法,除了基于誤差縮減的采樣之外,都存在離群點問題[16].為解決離群點問題, Settles等提出了結(jié)合信息密度(Information density,ID)的主動學(xué)習(xí)算法[31],如式(7)所示.該算法根據(jù)樣本間的相似度評估樣本密度,結(jié)合不確定性對樣本價值進行評估,如式(7)所示:

其中,H(x)表示樣本x的信息量,可根據(jù)不確定性采樣和委員會投票選擇算法求得.sim?x,x(u)￠表示樣本x與其他未標(biāo)記樣本的平均相似度,即樣本密度.參數(shù)β用來調(diào)節(jié)式中不確定性和密度的權(quán)重.

Zhu等[32]在此基礎(chǔ)上提出一種基于密度的重排序算法(Density-based re-ranking,DBRR),該算法分為兩層.第一層根據(jù)樣本的不確定性對未標(biāo)記樣本進行排序,選擇出部分不確定性高的候選樣本;第二層使用樣本密度對候選樣本排序,選擇密度大的樣本作為新樣本進行標(biāo)注.Xu等[33]提出一種基于代表性的采樣算法(Representative sampling, RS).該算法首先使用K-means聚類算法對未標(biāo)記數(shù)據(jù)進行劃分,然后選擇簇中心點作為新的訓(xùn)練樣本進行標(biāo)注.

以上三種方法都是圍繞樣本代表性進行采樣,目的在于解決離群點問題.而本文的方法除了考慮離群點之外,也針對信息冗余問題對主動學(xué)習(xí)采樣方式進行了改進.

2 基于雙層采樣主動學(xué)習(xí)的虛假用戶檢測模型

本文提出的基于雙層采樣主動學(xué)習(xí)的社交網(wǎng)絡(luò)虛假用戶檢測方法的整體框架結(jié)構(gòu)如圖2所示.首先,使用少量的標(biāo)簽用戶作為訓(xùn)練集,學(xué)習(xí)一個初始分類器;接著用該分類器預(yù)測未標(biāo)記數(shù)據(jù)集中的用戶標(biāo)簽,并使用雙層采樣算法對無標(biāo)簽用戶進行選擇,選擇出“價值”最大的多個用戶;然后,借助人工標(biāo)注的手段進行標(biāo)簽標(biāo)注,并將其加入訓(xùn)練集重新學(xué)習(xí)一個新的分類器;重復(fù)上述過程,直到分類器性能不再提升.

圖2 雙層采樣主動學(xué)習(xí)檢測框架Fig.2 Detection framework based on active learning with two-layer sampling

雙層采樣主動學(xué)習(xí)的第一層采樣將樣本的不確定性和代表性作為樣本價值的評估標(biāo)準(zhǔn),樣本不確定性可采用任一簡單的主動學(xué)習(xí)算法計算得到,樣本代表性采用Zhu等提出的樣本密度[32]進行評估.第二層采樣基于第一層采樣的結(jié)果對候選樣本進行聚類,然后以簇為單位對樣本的不確定性進行重排序,從而選擇出“價值”最大的未標(biāo)記樣本.

2.1 符號定義

本文使用的符號定義見表1.使用用戶特征向量表示網(wǎng)絡(luò)中的用戶,形如其中xi表示用戶i的特征向量,n表示網(wǎng)絡(luò)中的用戶總數(shù).有標(biāo)簽的用戶集合表示為X?L為無標(biāo)簽的用戶集合,其中yi∈{+1,?1}表示用戶的標(biāo)簽(+1為虛假用戶,–1為真實用戶),?為有標(biāo)簽的用戶的數(shù)目,μ=n??為無標(biāo)簽的用戶數(shù)目,??n.主動學(xué)習(xí)中涉及到計算樣本的不確定性,表示為H(x),樣本的代表性表示為AS(x),第一層采樣選擇出的候選用戶集合表示為Ucandidates.

表1 符號定義Table 1 De fi nition of symbols

2.2 用戶特征

提取用戶特征對于訓(xùn)練檢測模型十分重要,社交網(wǎng)絡(luò)中的用戶具有高維的特征,但并不是每一個特征都能對虛假用戶檢測問題產(chǎn)生影響.本文將社交網(wǎng)絡(luò)用戶的特征分成以下5類[14,34]:

屬性特征(Pro fi le-based feature,FP):屬性特征是直接從用戶概貌中提取的特征,通常包括關(guān)注數(shù)、粉絲數(shù)、賬戶年齡、發(fā)表文章數(shù)目等.

內(nèi)容特征(Content-based feature,FC):內(nèi)容特征即文本特征,是從用戶發(fā)表的文本中提取的,包括單詞數(shù)、URLs數(shù)、垃圾詞匯數(shù)、評論數(shù)、特殊字符數(shù)等.

行為特征(Activity-based features,FA):行為特征衡量用戶在社交網(wǎng)絡(luò)中的活躍程度,通常較為活躍的用戶被檢測成虛假用戶的概率很小,而活躍程度低或者行為周期化的用戶有較大的概率被檢測成虛假用戶.

鄰居特征(Neighbor-based features,FN):從用戶的鄰居用戶中提取的特征,通常包括鄰居用戶的粉絲數(shù)、關(guān)注數(shù)、鄰居用戶發(fā)表的文章數(shù)目、評論數(shù)目等.

關(guān)系圖特征(Graph-based features,FG):從社交網(wǎng)絡(luò)關(guān)系圖中提取的特征,包括聚類系數(shù)、節(jié)點核數(shù)、雙向關(guān)注比、PageRank值等.

本文參照其他研究者的研究成果[13,35],分別賦予5類用戶特征不同的權(quán)重占比.處理后的用戶特征見式(8).

FP,FC,FA,FN,FG分別代表上述5類特征.關(guān)系圖特征FG在檢測虛假用戶問題上具有最高的魯棒性和準(zhǔn)確性[13],因而賦予最高的權(quán)重.而屬性特征FP和內(nèi)容特征FC不能有效地區(qū)分正常用戶和虛假用戶[35],所以權(quán)重最低.

用戶特征向量經(jīng)過上述處理后將用于訓(xùn)練分類器模型,并通過雙層采樣算法對分類器進行優(yōu)化,最終用于虛假用戶的檢測.

2.3 基于不確定性和代表性的加權(quán)采樣

針對傳統(tǒng)主動學(xué)習(xí)可能選出離群點的問題,本文考慮將樣本的代表性加入樣本價值的度量中,并使用加權(quán)算法將其與樣本的不確定性相結(jié)合,形成一種基于不確定性和代表性的采樣(Sampling by uncertainty and representativeness,SUR),形式化定義如式(9):

其中H(x)為樣本x的信息熵,AS(x)為樣本x的代表性,SUR(x)表示不確定性和代表性的加權(quán)值, α為加權(quán)系數(shù),α∈(0,1),α=1時算法變?yōu)閮H考慮樣本代表性的主動學(xué)習(xí)采樣,α=0時即為基于不確定性的采樣算法.

樣本代表性反映該樣本與樣本集合中的其他樣本的整體相似度,本文采用Zhu等提出的樣本密度[32]衡量樣本的代表性.樣本間的相似度采用標(biāo)準(zhǔn)化的皮爾森相關(guān)系數(shù)計算(如式(10)),樣本代表性形式化定義為式(11).

式中,rp(xi,xj)表示兩個向量的皮爾遜相關(guān)系數(shù), sim(xi,xj)表示標(biāo)準(zhǔn)化到[0,1]區(qū)間的用戶相似度. S(x)={s1,s2,···,sK}表示與用戶x相似度最高的K個樣本.

2.4 基于多樣性和代表性的雙層采樣

SUR算法可以有效地避免離群點,但是仍然不能解決信息冗余問題.為此,本文提出一種基于多樣性和代表性的雙層采樣算法(Two-layer sampling based on diversity and density,DDTLS).

DDTLS算法的第一層采樣與上述SUR算法步驟一致,根據(jù)SUR(x)的大小對未標(biāo)記樣本進行排序,從中選擇Top-N的未標(biāo)記樣本作為第二層采樣的候選樣本,如式(12)所示.

得到N個候選樣本之后,算法的第二層采樣使用多樣性聚類和不確定性重排兩個步驟保證樣本集合的多樣性:

步驟1. 使用K-means方法對候選樣本集合進行聚類,得到k個不同的簇,C={c1,c2,···,ck}.根據(jù)聚類的性質(zhì),可以認(rèn)為聚成同一類的樣本距離小,不同類間的樣本距離大[36].這樣能夠有效地保證被選樣本集合整體多樣性大.

步驟2. 以簇為單位,對每一個簇中的樣本按照不確定性進行排序,從每個簇中選擇出不確定性最大的一個樣本組成最終的樣本集合,如式(13)所示.

其中,CL(ui)=c表示樣本ui聚類后屬于簇c, H(ui)表示樣本的信息熵或投票熵,可由式(2)、(3)計算得到.ΔL即為最終選擇的樣本集合.由于第一層采樣已剔除了離群點,所以不確定性重排能夠在保證樣本集合多樣性的基礎(chǔ)上,盡可能多地提高新樣本的信息量.

基于多樣性和代表性的雙層采樣主動學(xué)習(xí)方法的整體思路見算法1.雙層采樣算法可以避免選擇出樣本中的離群點,因為算法在第一層采樣中考慮了樣本的代表性,如果該樣本是離群點,代表性過小,即使不確定性足夠大也不會被選擇為候選樣本.除此之外,雙層采樣算法還能保證被選擇出來的樣本集合的整體多樣性較大,因為在第二層采樣中,候選樣本被聚類之后,不同類之間的樣本距離較大,則選出的樣本整體的平均距離也較大,從而樣本間的相似度較低,減少了信息冗余.

算法1.基于雙層采樣的主動學(xué)習(xí)檢測算法

3 實驗結(jié)果及分析

本文的實驗分為對比實驗和參數(shù)評估實驗2個部分.對比實驗首先使用監(jiān)督型機器學(xué)習(xí)算法與本文方法進行對比,驗證本文提出的方法是否能夠使用少量標(biāo)簽樣本達到和監(jiān)督型算法近似的效果.然后,將本文提出的方法與其他主動學(xué)習(xí)方法進行比較,驗證DDTLS算法和SUR算法是否比其他基于代表性的主動學(xué)習(xí)算法性能更優(yōu).并對DDTLS算法和SUR算法進行比較,驗證雙層采樣對分類器性能的影響是否大于單層采樣.參數(shù)評估實驗則是對本文提出的算法進行參數(shù)敏感性分析,根據(jù)參數(shù)對實驗效果的影響,給出每一個參數(shù)的最優(yōu)取值.

3.1 實驗設(shè)計

3.1.1 數(shù)據(jù)集

本文將使用4個數(shù)據(jù)集進行實驗,具體描述如下:

表2 Apontador數(shù)據(jù)集用戶特征(粗體表示Apontador-49包含而Apontador-33不包含的特征)Table 2 The user features of Apontador data set (Bold show features only in Apontador-49.)

Twitter[17]:包含1065個用戶,每個用戶都有一個表示用戶類型(真實用戶或虛假用戶)的標(biāo)簽,其中有710個真實用戶,355個虛假用戶.每個用戶包含62個字段,26個不同的特征.用戶特征的具體描述見表3.

表3 Twitter數(shù)據(jù)集用戶特征Table 3 The user features of Twitter data set

Youtube[39]:包含829個用戶,每個用戶都有一個表示用戶類型(真實用戶或虛假用戶)的標(biāo)簽,其中有641個真實用戶,188個虛假用戶.每個用戶包含62個不同的特征.用戶特征的具體描述見表4.

表4 Youtube數(shù)據(jù)集用戶特征Table 4 The user features of Youtube data set

3.1.2 Baseline

本文首先使用監(jiān)督型機器學(xué)習(xí)算法與本文方法進行比較,說明本文方法僅使用少量的標(biāo)簽樣本能夠達到和監(jiān)督型算法相近甚至更優(yōu)的實驗效果.另外,將本文方法與以下3種Baseline方法進行對比,說明SUR算法和DDTLS算法的合理性和有效性.并對SUR和DDTLS算法進行了比較,說明雙層采樣算法對分類器性能的影響優(yōu)于單層采樣算法.

結(jié)合信息密度的主動學(xué)習(xí)算法[31]:Settles等為解決離群點問題提出的主動學(xué)習(xí)采樣方法,使用樣本平均相似度代表樣本的密度,具體公式見式(7).本文的實驗中,令β=1.

基于密度的重排序算法[32]:Zhu等在樣本密度的基礎(chǔ)上提出的改進方法,首先基于樣本的不確定性確定候選樣本集合,然后選出樣本密度大的樣本作為新樣本進行標(biāo)注.

基于聚類的代表性采樣算法[33]:Xu等提出一種基于聚類的主動學(xué)習(xí)算法,該算法首先使用K-means聚類算法對未標(biāo)記數(shù)據(jù)集進行劃分,然后選擇簇中心點作為新的訓(xùn)練樣本進行標(biāo)注.

本文提出的SUR算法和DDTLS算法都涉及樣本不確定性的計算,根據(jù)所選的計算方式的不同,本文方法可以與不確定采樣主動學(xué)習(xí)結(jié)合形成SUR-UNC和DDTLS-UNC,同樣的,結(jié)合委員會投票選擇算法形成SUR-QBC和DDTLS-QBC.

實驗使用4種不同的機器學(xué)習(xí)算法,分別是支持向量機、決策樹、邏輯回歸和樸素貝葉斯.使用5折交叉驗證,主動學(xué)習(xí)模型做50次隨機試驗.

3.1.3 評價指標(biāo)

實驗使用準(zhǔn)確率、召回率、F值作為評估分類器性能標(biāo)準(zhǔn),計算公式分別如式(14)～(16).其中, truePositives表示被正確預(yù)測為虛假用戶的用戶個數(shù),falsePositives表示真實用戶被錯誤預(yù)測為虛假用戶的個數(shù),falseNegatives表示虛假用戶被錯誤預(yù)測為真實用戶的個數(shù).

3.2 對比實驗結(jié)果分析

3.2.1 與監(jiān)督型機器學(xué)習(xí)算法的比較

本文先使用監(jiān)督型機器學(xué)習(xí)算法與本文提出的SUR、DDTLS兩種算法進行比較.Twitter和Youtube數(shù)據(jù)集上的實驗結(jié)果見表5,Apontador數(shù)據(jù)集上的實驗結(jié)果見表6.Twitter和Youtube數(shù)據(jù)集上的實驗最終所用的訓(xùn)練數(shù)據(jù)為初始未標(biāo)記樣本總數(shù)的20%,Apontador數(shù)據(jù)集上的實驗最終所用的訓(xùn)練數(shù)據(jù)為初始未標(biāo)記樣本總數(shù)的10%.

從表5和表6中可以看出,無論是結(jié)合不確定性采樣還是委員會投票選擇,本文提出的SUR算法和DDTLS算法的準(zhǔn)確率都非常逼近監(jiān)督型機器學(xué)習(xí)方法,甚至更高.例如,表5中樸素貝葉斯模型下的DDTLS-QBC在Twitter數(shù)據(jù)集上能夠達到89.43%的準(zhǔn)確率,而監(jiān)督學(xué)習(xí)只能達到83.82%.Youtube數(shù)據(jù)集上使用邏輯回歸模型作為基本分類算法的情況下,本文方法的3項指標(biāo)都優(yōu)于監(jiān)督學(xué)習(xí).

表5 Twitter和Youtube數(shù)據(jù)集上的實驗結(jié)果(%)Table 5 Experimental results on Twitter and Youtube data set(%)

表6 Apontador數(shù)據(jù)集上的實驗結(jié)果(%)Table 6 Experimental results on Apontador data set(%)

3.2.2 與多種主動學(xué)習(xí)算法的比較

SUR算法和DDTLS算法對比Baseline算法的實驗結(jié)果顯示在圖3～6中.實驗使用支持向量機模型作為基礎(chǔ)的分類算法,初始標(biāo)簽樣本數(shù)設(shè)定為樣本總數(shù)的1%,每次迭代選擇的新樣本數(shù)為總數(shù)的1%.Twitter和Youtube數(shù)據(jù)集上的結(jié)果(圖3、圖4)顯示訓(xùn)練數(shù)據(jù)集達到總樣本的15%之后分類器的各項性能就趨于穩(wěn)定,Apontador數(shù)據(jù)集上的結(jié)果(圖5、圖6)顯示訓(xùn)練數(shù)據(jù)集達到6%之后分類器的各項指標(biāo)就趨于基本穩(wěn)定狀態(tài),只出現(xiàn)了小幅的波動.這說明將主動學(xué)習(xí)算法應(yīng)用到社交網(wǎng)絡(luò)領(lǐng)域中能夠很好地解決標(biāo)簽用戶不足的問題.

對比圖3～6中不同主動學(xué)習(xí)方法的準(zhǔn)確率和召回率的增加速度和穩(wěn)定值可以發(fā)現(xiàn),本文提出的SUR算法和DDTLS算法比其他主動學(xué)習(xí)方法對分類器性能的影響更快且更好.如圖3所示,SUR和DDTLS算法的準(zhǔn)確率(圖3(a))和F值(圖3(c))增加較其他算法更快,并且最終穩(wěn)定在一個較高的值.圖3(b)中雖然RS算法的召回率上升速度快,但隨著訓(xùn)練樣本的增加RS的召回率出現(xiàn)小幅下降,最終的召回率反而比SUR和DDTLS小.

相較于單層的采樣算法SUR,雙層采樣算法DDTLS在3項指標(biāo)上都有所領(lǐng)先,特別是在召回率指標(biāo)上,DDTLS的提升尤為明顯.這說明第二層的聚類算法能夠有效地保證樣本集合的多樣性,減少信息冗余,從而提升分類器的泛化能力.

圖3 Twitter數(shù)據(jù)集的實驗結(jié)果Fig.3 Experimental results on Twitter data set

圖4 Youtube數(shù)據(jù)集的實驗結(jié)果Fig.4 Experimental results on Youtube data set

圖5 Apontador-33數(shù)據(jù)集的實驗結(jié)果Fig.5 Experimental results on Apontador-33 data set

3.3 參數(shù)敏感性分析

這一部分分析雙層采樣模型的參數(shù)敏感性,模型中待確定的參數(shù)有加權(quán)系數(shù)α、近鄰個數(shù)K、候選樣本數(shù)N以及初始標(biāo)簽樣本數(shù).參數(shù)敏感性分析實驗使用信息熵(式(2))計算樣本的不確定性,用邏輯回歸模型作為基礎(chǔ)的分類算法,在Twitter數(shù)據(jù)集上對DDTLS算法進行單因素的敏感分析.圖7分別展示了上述4種參數(shù)對實驗準(zhǔn)確率、召回率和F值的影響.

圖6 Apontador-49數(shù)據(jù)集的實驗結(jié)果Fig.6 Experimental results on Apontador-49 data set

圖7 參數(shù)敏感性實驗結(jié)果Fig.7 Experimental results of parameter sensitivity analysis

加權(quán)系數(shù)α用于第一層采樣(基于不確定性和代表性的加權(quán)采樣)中計算樣本的SUR值,通過調(diào)節(jié)α值可以得到不同偏重的加權(quán)組合.根據(jù)式(9),加權(quán)系數(shù)越大,樣本的不確定性對第一層采樣的影響越大,反之,則第一層采樣會優(yōu)先選擇代表性高的樣本.從圖7(a)中可以看出,α＜0.5的情況下,準(zhǔn)確率、召回率都隨著α值單調(diào)遞增.當(dāng)α＞0.5,準(zhǔn)確率和召回率趨向相對穩(wěn)定狀態(tài),F在α=0.8時取得最優(yōu).這說明盡管樣本代表性可以有效地剔除離群點樣本,但是樣本代表性對分類器性能的影響比樣本不確定性低,因此在SUR計算中應(yīng)使不確定性的權(quán)重高于代表性.此外,當(dāng)α=0或1.0時,該方法變成僅考慮代表性或不確定性的采樣.

圖8描述了當(dāng)α取值分別為0、0.8和1.0時,分類器的準(zhǔn)確率和召回率隨主動學(xué)習(xí)迭代過程的變化.從圖8(a)中可以看出,α=0時分類器的準(zhǔn)確率非常低,這說明單純基于代表性的采樣不能有效地提高分類器的精度.同樣地,圖8(b)顯示α=0時分類器的召回率也較低,并且提升緩慢,當(dāng)標(biāo)簽樣本接近20%時召回率才與其他兩種α取值時相近.對比α=0.8和α=1.0的情況,α=0.8時準(zhǔn)確率和召回率明顯較好,這一結(jié)果說明結(jié)合代表性的加權(quán)采樣是有效的,對分類器的精度和泛化能力都有提升作用.

近鄰個數(shù)K 對雙層采樣算法的影響如圖7(b)所示.近鄰個數(shù)為20時,雙層采樣算法的召回率和F值最大,并且這個最大值遠高于其他近鄰個數(shù)下的結(jié)果.這是因為,過大或者過小的近鄰個數(shù)值都不能準(zhǔn)確地反映樣本在未標(biāo)記樣本空間中的代表性,近鄰個數(shù)過小,容易選出離群點,近鄰個數(shù)過大,則所有樣本的代表性值十分相近.所以,本文使用20個近鄰的平均相似度計算樣本密度.

候選樣本數(shù)對實驗結(jié)果的影響如圖7(c)所示,候選樣本數(shù)指的是第一層采樣選擇出的樣本個數(shù).這個值同樣不宜過大或過小,如果候選樣本數(shù)過大,則第一層采樣的作用將被減少,無法篩選掉不確定性和代表性都不高的樣本,并且過大的候選樣本量將會增加算法的時間復(fù)雜度.相反,如果候選樣本的數(shù)量過小,容易漏掉有價值的樣本,使得最終選擇出的樣本信息量小,不能快速提升分類器的性能.圖7(c)中的結(jié)果驗證了這一結(jié)論.值得注意的是,算法的準(zhǔn)確率在候選樣本數(shù)為200時,即未標(biāo)記樣本總數(shù)的20%時,取得最優(yōu)值,之后隨著候選樣本的增大,準(zhǔn)確率呈下降趨勢.而召回率則是在候選樣本為400,也就是未標(biāo)記樣本總數(shù)的40%開始取得較高值.可能的原因是,加權(quán)系數(shù)設(shè)定為0.8,導(dǎo)致第一層采樣會先選擇出不確定性高的一批樣本,不確定性高的樣本全部選出來之后,再根據(jù)樣本的代表性選擇另外的樣本,而這類代表性高的樣本加入訓(xùn)練集后,有利于提高分類器的召回率,同時也會適當(dāng)降低分類器的準(zhǔn)確率.因此,本文的實驗選擇N=300,即在第一層采樣中剔除2/3的無價值樣本,保留1/3價值較高的樣本.

從圖7(d)中,明顯可以看出初始樣本數(shù)對實驗結(jié)果沒有影響.為了減少人工標(biāo)注的成本,實驗選擇盡可能少的初始樣本,即初始樣本數(shù)為10(樣本總數(shù)的1%).

4 結(jié)論

本文針對社交網(wǎng)絡(luò)中標(biāo)簽用戶量少,并且人工標(biāo)注大量標(biāo)簽用戶費時又費力的問題,提出了一種基于雙層采樣主動學(xué)習(xí)的虛假用戶檢測框架.該框架的第一層,從未標(biāo)記樣本空間中挑選出不確定性大且代表性高的部分樣本作為候選樣本;第二層則使用聚類重排序的方法選擇出樣本集合整體多樣性高的樣本進行人工標(biāo)注,標(biāo)注后的樣本用于新一輪的訓(xùn)練.

圖8 加權(quán)系數(shù)對雙層采樣算法效果的影響Fig.8 In fl uence of the weighted coefficient on experimental results

本文在4個數(shù)據(jù)集上的對比實驗說明基于主動學(xué)習(xí)的虛假用戶檢測方法只需要少量的標(biāo)簽用戶即可達到和監(jiān)督型機器學(xué)習(xí)方法接近的,甚至更好的檢測效果.并且,相較于其他考慮樣本代表性和多樣性的主動學(xué)習(xí)方法,本文提出的基于雙層采樣主動學(xué)習(xí)方法具有更優(yōu)的檢測精度,所需要的標(biāo)簽用戶數(shù)量更少.

然而,本文方法仍然存在可以改進的地方.1)在實驗中我們發(fā)現(xiàn)SUR和DDTLS的準(zhǔn)確率和召回率可能會出現(xiàn)振蕩.出現(xiàn)這一現(xiàn)象的可能原因是,基于近鄰相似度計算的樣本代表性有時不能有效地反映樣本對未標(biāo)記樣本集合的整體覆蓋率,導(dǎo)致這一類代表性高的樣本加入訓(xùn)練集后,不能提供分類器更多的有效信息.因此,在以后的研究中,可以就如何評估樣本的整體代表性方面對算法進行改進,從而進一步提高分類器的泛化能力.2)本文方法仍然需要人工對未標(biāo)記樣本進行標(biāo)注,針對這個問題,后續(xù)的研究將會考慮主動學(xué)習(xí)和半監(jiān)督的結(jié)合,一方面可以利用半監(jiān)督算法代替主動學(xué)習(xí)的人工標(biāo)注步驟,另一方面結(jié)合半監(jiān)督可以充分利用未標(biāo)記數(shù)據(jù)集中的最大量價值,提高檢測的準(zhǔn)確率和召回率.

1 Huang Zhen-Hua,Zhang Jia-Wen,Tian Chun-Qi,Sun Sheng-Li,Xiang Yang.Survey on learning-to-rank based recommendatio algorithms.Journal of Software,2016,27(3): 691?713 (黃震華,張佳雯,田春岐,孫圣力,向陽.基于排序?qū)W習(xí)的推薦算法研究綜述.軟件學(xué)報,2016,27(3):691?713)

2 Xin Yu,Yang Jing,Xie Zhi-Qiang.An overlapping semantic community structure detecting algorithm by label propagation.Acta Automatica Sinica,2014,40(10):2262?2275 (辛宇,楊靜,謝志強.基于標(biāo)簽傳播的語義重疊社區(qū)發(fā)現(xiàn)算法.自動化學(xué)報,2014,40(10):2262?2275)

3 Gao H Y,Hu J,Wilson C,Li Z C,Chen Y,Zhao B Y.Detecting and characterizing social spam campaigns.In:Proceedings of the 17th ACM Conference on Computer and Communications Security.Chicago,Illinois,USA:ACM, 2010.681?683

4 Wang G,Wilson C,Zhao X H,Zhu Y B,Mohanlal M,Zheng H T,Zhao B Y.Serf and turf:crowdtur fi ng for fun and pro fi t.In:Proceedings of the 21st International Conference on World Wide Web.Lyon,France:ACM,2012.679?688

5 Stringhinl G,Wang G,Fgele M,Kruegel C,Vigna G,Zheng H T,Zhao B Y.Follow the green:growth and dynamics in Twitter follower markets.In:Proceedings of the 2013 Conference on Internet Measurement Conference.Barcelona, Spain:ACM,2013.163?176

6 Ghosh S,Viswanath B,Kooti F,Sharma N K,Korlam G, Benevenuto F,Ganguly N,Gummadi K P.Understanding and combating link farming in the Twitter social network. In:Proceedings of the 21st International Conference on World Wide Web.Lyon,France:ACM,2012.61?70

7 Gupta A,Kumaraguru P,Castillo C,Meier P.TweetCred: real-time credibility assessment of content on Twitter.In: Proceedings of the 6th International Conference on Social Informatics.Barcelona,Spain:Springer,2014.228?243

8 Amleshwaram A A,Reddy N,Yadav S,Gu G F,Yang C. CATS:characterizing automation of Twitter spammers.In: Proceedings of the 5th International Conference on Communication Systems and Networks(COMSNETS).Bangalore, India:IEEE,2013.1?10

9 Prasetyo P K,Lo D,Achananuparp P,Tian Y,Lim E P. Automatic classi fi cation of software related microblogs.In: Proceedings of the 28th IEEE International Conference on Software Maintenance(ICSM).Trento,Italy:IEEE,2012. 596?599

10 Hu X,Tang J L,Liu H.Online social spammer detection. In:Proceedings of the 28th Conference on Arti fi cial Intelligence.Qu′ebec,Canada:AAAI,2014.59?65

11 Hu X,Tang J L,Zhang Y C,Liu H.Social spammer detection in microblogging.In:Proceedings of the 23rd International Joint Conference on Arti fi cial Intelligence.Beijing, China:AAAI,2013.2633?2639

12 Ravikumar S,Talamadupula K,Balakrishnan R,Kambhampati S.RAProp:ranking tweets by exploiting the tweet/user/web ecosystem and inter-tweet agreement.In: Proceedings of the 22nd ACM International Conference on Information and Knowledge Management.San Francisco, CA,USA:ACM,2013.2345?2350

13 Cheng Xiao-Tao,Liu Cai-Xia,Liu Shu-Xin.Graph-based features for identifying spammers in microblog networks. Acta Automatica Sinica,2015,41(9):1533?1541 (程曉濤,劉彩霞,劉樹新.基于關(guān)系圖特征的微博水軍發(fā)現(xiàn)方法.自動化學(xué)報,2015,41(9):1533?1541)

14 Li Z X,Zhang X C,Shen H,Liang W X,He Z Y.A semisupervised framework for social spammer detection.In:Proceedings of the 19th Paci fi c-Asia Conference in Knowledge Discovery and Data Mining(PAKDD).Ho Chi Minh City, Vietnam:Springer,2015.177?188

15 Cohn D A,Ghahramani Z,Jordan M I.Active learning with statistical models.Journal of Arti fi cial Intelligence Research,1996,4:129?145

16 Hajmohammadi M S,Ibrahim R,Selamat A,Fujita H.Combination of active learning and self-training for cross-lingual sentiment classi fi cation with density analysis of unlabelled samples.Information Sciences,2015,317:67?77

17 Benevenuto F,Magno G,Rodrigues T,Almeida V.Detecting spammers on Twitter.In:Proceedings of the 7th Annual Collaboration,Electronic Messaging,Anti-Abuse and Spam Conference.Redmond,Washington,USA,2010.

18 Jeong S，Noh G,Oh H，Kim C K.Follow spam detection based on cascaded social information.Information Sciences, 2016,369:481?499

19 BenevenutoF,RodriguesT,AlmeidaV,AlmeidaJ, Go?calves M A.Detecting spammers and content promoters in online video social networks.In:Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval.Boston,MA,USA: ACM,2009.620?627

20 Lee K,Caverlee J,Webb S.Uncovering social spammers: social honeypots+machine learning.In:Proceeding of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval.Geneva,Switzerland: ACM,2010.435?442

21 Song J,Lee S,Kim J.Spam filtering in Twitter using senderreceiver relationship.In:Proceedings of the 14th International Symposium,Recent Advances in Intrusion Detection. Menlo Park,CA,USA:Springer,2011.301?317

22 Cao Jian-Ping,Wang Hui,Xia You-Qing,Qiao Feng-Cai, Zhang Xin.Bi-path evolution model for online topic model based on LDA.Acta Automatica Sinica,2014,40(12): 2877?2886 (曹建平,王暉,夏友清,喬鳳才,張鑫.基于LDA的雙通道在線主題演化模型.自動化學(xué)報,2014,40(12):2877?2886)

23 Tan E H,Guo L,Chen S Q,Zhang X D,Zhao Y H.UNIK: unsupervised social network spam detection.In:Proceedings of the 22nd ACM International Conference on Information and Knowledge Management.San Francisco,USA: ACM,2013.479?488

24 Zhao L,Chen F,Dai J,Hua T,Lu C T,Ramakrishnan N. Unsupervised spatial event detection in targeted domains with applications to civil unrest modeling.PLoS One,2014, 9(10):e110206

25 Wu Jian,Sheng Sheng-Li,Zhao Peng-Peng,Cui Zhi-Ming. Minimal di ff erence sampling for active learning image classifi cation.Journal on Communications,2014,35(1):107?114 (吳健,盛勝利,趙朋朋,崔志明.最小差異采樣的主動學(xué)習(xí)圖像分類方法.通信學(xué)報,2014,35(1):107?114)

26 Zhu J B,Ma M.Uncertainty-based active learning with instability estimation for text classi fi cation.ACM Transactions on Speech and Language Processing,2012,8(4):Article No.5

27 Tuia D,Ratle F,Paci fi ci F,Kanevski M F,Emery W J. Active learning methods for remote sensing image classi fi cation.IEEE Transactions on Geoscience and Remote Sensing, 2009,47(7):2218?2232

28 Settles B.Active Learning Literature Survey,Computer Sciences Technical Report 1648,University of Wisconsin-Madison,Wisconsin,2010.

29 Zhang T,Oles F J.A probability analysis on the value of unlabeled data for classi fi cation problems.In:Proceedings of the 17th International Conference on Machine Learning.San Francisco,CA,USA:Morgan Kaufmann,2000.1191?1198

30 Roy N,McCallum A.Toward optimal active learning through sampling estimation of error reduction.In:Proceedings of the 18th International Conference on Machine Learning.Williams College,Williamstown,MA,USA:Morgan Kaufmann Publishers Inc.,2001.441?448

31 Settles B,Craven M.An analysis of active learning strategies for sequence labeling tasks.In:Proceedings of the Conference on Empirical Methods in Natural Language Processing. Honolulu,Hawaii,USA:ACL,2008.1070?1079

32 Zhu J B,Wang H Z,Tsou B K,Ma M.Active learning with sampling by uncertainty and density for data annotations.IEEE Transactions on Audio,Speech,and Language Processing,2010,18(6):1323?1331

33 Xu Z,Yu K,Tresp V,Xu X W,Wang J Z.Representative sampling for text classi fi cation using support vector machines.In:Proceedings of the 25th European Conference on IR Research.Pisa,Italy:Springer,2003.393?407

34 Yang C,Harkreader R,Gu G F.Empirical evaluation and new design for fi ghting evolving Twitter spammers.IEEE Transactions on Information Forensics and Security,2013, 8(8):1280?1293

35 Freitas C,Benevenuto F,Ghosh S,Veloso A.Reverse engineering socialbot in fi ltration strategies in Twitter.In:Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.Paris, France:ACM,2015.25?32

36 Chen Jin-Yin,He Hui-Hao.Research on density-based clustering algorithm for mixed data with determine cluster centers automatically.Acta Automatica Sinica,2015,41(10): 1798?1813 (陳晉音,何輝豪.基于密度的聚類中心自動確定的混合屬性數(shù)據(jù)聚類算法研究.自動化學(xué)報,2015,41(10):1798?1813)

37 Costa H,Benevenuto F,Merschmann C D.Detecting tip spam in location-based social networks.In:Proceedings of the 28th Annual ACM Symposium on Applied Computing. Coimbra,Portugal:ACM,2013.724?729

38 Costa H,Merschmann L H C,Barth F,Benevenuto F. Pollution,bad-mouthing,and local marketing:the underground of location-based social networks.Information Sciences,2014,279:123?137

39 Benevenuto F,Rodrigues T,Almeida J,Goncalves M, Almeida V.Detecting spammers and content promoters in online video social networks.In:Proceedings of the 28th IEEE International Conference on Computer Communications Workshops.Rio de Janeiro,Brazil:IEEE,2009. 337?338

Two-layer Sampling Active Learning Algorithm for Social Spammer Detection

TAN Kan1,2GAO Min1,2LI Wen-Tao1,3TIAN Ren-Li1,4WEN Jun-Hao1,2XIONG Qing-Yu1,2

With the rapid development of social network,more and more people join in social network to make friends and share their views.However,social network is always su ff ering from fake accounts due to its openness.Fake accounts, also called spammers,always spread spam information to achieve their own purpose,which have destroyed the security and reliability of social network.Existing detection methods extract behaviour,text and relationship features of users, and then use machine learning algorithms to identify social spammers.But machine learning algorithms often su ff er from insufficiently labeled training data.Aiming to solve this problem,we propose an efficient algorithm,called two-layer sampling active learning,to construct an accurate classi fi er with minimum labeled samples.We present three criteria (uncertainty,representative and diversity)to quantity the value of unlabeled samples,using the combination of sorting and clustering to actively select samples with max uncertainty,max representative and max diversity.Experimental results on Twitter,Apontador,and Youtube datasets prove the efficiency of our approach,and better precision and recall of our approach than other active learning methods.

Social network,spammer,active learning,diversity of samples

譚 侃 重慶大學(xué)軟件學(xué)院碩士研究生.主要研究方向為虛假用戶檢測,數(shù)據(jù)挖掘.E-mail:188313135@163.com(TAN Kan Masterstudentat the School of Software Engineering, Chongqing University.Her research interest covers spammer detection and data mining.)

高 旻 重慶大學(xué)軟件學(xué)院副教授.分別于2005年和2010年獲得重慶大學(xué)計算機學(xué)院碩士和博士學(xué)位.雷丁大學(xué)商學(xué)院訪問學(xué)者.主要研究方向為推薦系統(tǒng),服務(wù)計算,數(shù)據(jù)挖掘.本文通信作者. E-mail:gaomin@cqu.edu.cn (GAO Min Associate professor at the School of Software Engineering,Chongqing University.She received the master and Ph.D. degrees in computer science from Chongqing University in 2005 and 2010,respectively.She was a visiting researcher atthe School of Business,University of Reading.Her researchinterest covers recommendation system,service computing, and data mining.Corresponding author of this paper.)

李文濤 悉尼科技大學(xué)工程與信息技術(shù)學(xué)院量子計算與智能系統(tǒng)研究中心博士研究生.主要研究方向為社交媒體挖掘與大圖處理.E-mail:wentao.li@student.uts.edu.au (LI Wen-Tao Ph.D.candidate at the Centre for Quantum Computation and Intelligent Systems,Faculty of Engineering and Information Technology,University of Technology Sydney.His research interest covers social media mining and big graph processing.)

田仁麗 廣州博冠信息科技有限公司運營數(shù)據(jù)分析師.主要研究方向為個性化推薦與數(shù)據(jù)挖掘.E-mail:tianrenli1@163.com(TIAN Ren-Li Operating data analyst at Guangzhou Boguan Telecommunication Technology Limited.Her research interest covers personal recommendation and data mining.)

文俊浩 重慶大學(xué)軟件學(xué)院教授.主要研究方向為計算智能與推薦系統(tǒng).E-mail:jhwen@cqu.edu.cn(WEN Jun-Hao Professorat the School of Software Engineering, Chongqing University. His research interest covers computing and recommendation systems.)

熊慶宇 重慶大學(xué)軟件學(xué)院教授.分別于1986年和1991年獲得重慶大學(xué)學(xué)士和碩士學(xué)位.2002年獲得日本九州大學(xué)博士學(xué)位.主要研究方向為神經(jīng)網(wǎng)絡(luò)及其應(yīng)用.E-mail:xiong03@cqu.edu.cn(XIONG Qing-Yu Professorat the School of Software Engineering, Chongqing University.He received his bachelor and master degrees from the School of Automation,Chongqing University in 1986 and 1991,respectively,and the Ph.D.degree from Kyushu University of Japan in 2002.His research interest covers neural networks and their application.)

譚侃,高旻,李文濤,田仁麗,文俊浩,熊慶宇.基于雙層采樣主動學(xué)習(xí)的社交網(wǎng)絡(luò)虛假用戶檢測方法.自動化學(xué)報, 2017,43(3):448?461

Tan Kan,Gao Min,Li Wen-Tao,Tian Ren-Li,Wen Jun-Hao,Xiong Qing-Yu.Two-layer sampling active learning algorithm for social spammer detection.Acta Automatica Sinica,2017,43(3):448?461

2016-04-05 錄用日期2016-08-08

Manuscript received April 5,2016;accepted August 8,2016國家重點基礎(chǔ)研究發(fā)展計劃(973計劃)(2013CB328903),重慶市基礎(chǔ)與前沿研究計劃(cstc2015jcyjA40049),國家自然科學(xué)基金(71102065),國家科技支撐計劃(2015BAF05B03),中央高?；A(chǔ)研究基金(106112014CDJZR095502)資助

Supported by National Key Basic Research Program of China (973 Program)(2013CB328903),Basic and advanced research projects in Chongqing(cstc2015jcyjA40049),National Natural Science Foundation of China(71102065),National Science and Technology Ministry(2015BAF05B03),and Fundamental Research Funds for the Central Universities(106112014CDJZR095502)本文責(zé)任編委周志華

Recommended by Associate Editor ZHOU Zhi-Hua 1.信息物理社會可信服務(wù)計算教育部重點實驗室 重慶 400044中國2.重慶大學(xué)軟件學(xué)院 重慶 400044中國 3.悉尼科技大學(xué)工程與信息技術(shù)學(xué)院量子計算與智能系統(tǒng)研究中心悉尼NSW 2007澳大利亞4.廣州博冠信息科技有限公司廣州501665中國

1.Key Laboratory of Dependable Service Computing in Cy-ber Physical Society,Ministry of Education,Chongqing 400044, China 2.School of Software Engineering,Chongqing University,Chongqing 400044,China 3.Centre for Quantum Computation and Intelligent Systems,Faculty of Engineering and Information Technology,University of Technology Sydney,Sydney, NSW 2007,Australia 4.Guangzhou Boguan Telecommunication Technology Limited,Guangzhou 501665,China

DOI10.16383/j.aas.2017.c160308