一種應(yīng)用SAVBP神經(jīng)網(wǎng)絡(luò)的僵尸粉判別方法

王越，張劍金

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

一種應(yīng)用SAVBP神經(jīng)網(wǎng)絡(luò)的僵尸粉判別方法

王越，張劍金

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

微博僵尸粉干擾了微博的正常社交環(huán)境，對(duì)微博用戶影響巨大。首先，闡述了微博僵尸粉的發(fā)展趨勢(shì)與最新特點(diǎn)，分析了微博僵尸粉與正常用戶的不同特征;其次，針對(duì)微博數(shù)據(jù)量大、使用BP神經(jīng)網(wǎng)絡(luò)判別僵尸粉易陷入局部極小點(diǎn)、收斂速度慢、無法收斂等缺點(diǎn)，提出基于模擬退火算法的可變速率BP神經(jīng)網(wǎng)絡(luò)－SAVBP，并建立僵尸粉判別模型;最后，使用新浪微博數(shù)據(jù)對(duì)系統(tǒng)進(jìn)行評(píng)估。結(jié)果顯示:該系統(tǒng)對(duì)微博僵尸粉有93%的判別準(zhǔn)確率與93%的召回率。

僵尸粉;BP神經(jīng)網(wǎng)絡(luò);模擬退火;可變速率

自2009年8月新浪微博正式推出以來，微博在中國迅速發(fā)展，成為最流行的社交網(wǎng)絡(luò)之一。微博用戶的粉絲數(shù)在一定程度上反映了用戶的影響力與受歡迎程度。為了快速提高粉絲數(shù)量，市場上出現(xiàn)了大規(guī)模的買粉現(xiàn)象。但隨著用戶粉絲需求量的增加，使用真實(shí)用戶作為粉絲進(jìn)行交易已經(jīng)無法滿足需求，一種全新的微博僵尸粉開始出現(xiàn)。目前學(xué)術(shù)界對(duì)僵尸粉并沒有統(tǒng)一的定義。百度百科定義為:微博上的虛假粉絲，指花錢可以買到“關(guān)注”，有名無實(shí)的微博粉絲，通常是由系統(tǒng)自動(dòng)產(chǎn)生的惡意注冊(cè)用戶;維基百科定義為:一些長期沒有動(dòng)態(tài)、同一IP地址申請(qǐng)多個(gè)微博賬號(hào)的用戶。隨著僵尸粉的不斷發(fā)展，這些定義已經(jīng)過時(shí)。本文根據(jù)僵尸粉的最新發(fā)展特點(diǎn)，對(duì)僵尸粉進(jìn)行了重新定義:出現(xiàn)于微博平臺(tái)上，以提高用戶粉絲數(shù)為目的，由軟件自動(dòng)產(chǎn)生、維護(hù)的一類虛假用戶。僵尸粉具有操作簡單、維護(hù)成本低等特點(diǎn)，在短短幾年時(shí)間內(nèi)迅速發(fā)展并遍布整個(gè)微博網(wǎng)絡(luò)，給微博造成了諸如誠信危機(jī)、用戶影響力無法正確計(jì)算、用戶社交網(wǎng)絡(luò)關(guān)系模糊不清等問題［1－2］。因此，準(zhǔn)確判別出微博僵尸粉，剔除僵尸粉對(duì)微博的影響具有現(xiàn)實(shí)意義。

1 僵尸粉特征分析

僵尸粉由軟件自動(dòng)產(chǎn)生并維護(hù)，并沒有實(shí)際真人使用。故僵尸粉在個(gè)人信息、微博內(nèi)容等方面都有聚團(tuán)相似性且與普通用戶特征差別明顯。

1.1 個(gè)人信息特征

在微博網(wǎng)絡(luò)中，用戶粉絲與關(guān)注代表了用戶的社交關(guān)系。假設(shè)用戶A是用戶B的粉絲(也可以說用戶A關(guān)注了用戶B)，則認(rèn)為用戶A認(rèn)同用戶B為自己的朋友。僵尸粉通過買賣手段提高其他用戶的粉絲數(shù)。商家為了節(jié)約成本，通常一個(gè)僵尸粉充當(dāng)幾百甚至幾千用戶的粉絲，故僵尸粉的關(guān)注數(shù)較多。而僵尸粉自身沒有社交關(guān)系，粉絲數(shù)極少。人氣指數(shù)是用戶粉絲數(shù)與關(guān)注數(shù)的比值［3］，可以很好地反映用戶社交關(guān)系的組成。

普通用戶的粉絲數(shù)與關(guān)注數(shù)較為接近，反映了現(xiàn)實(shí)生活中“對(duì)等”的社交關(guān)系，即我認(rèn)識(shí)的和認(rèn)識(shí)我的人的數(shù)量相差不大。而僵尸粉的關(guān)注數(shù)遠(yuǎn)遠(yuǎn)大于他的粉絲數(shù)，偏離了實(shí)際的社交關(guān)系網(wǎng)絡(luò)。個(gè)人信息定義的僵尸粉特征如表1所示。

表1 僵尸粉個(gè)人信息特征

1.2 微博內(nèi)容特征

早期的僵尸粉并不會(huì)發(fā)送微博，但為了逃避新浪微博封殺，僵尸粉開始升級(jí)，大量更新微博，其微博數(shù)遠(yuǎn)遠(yuǎn)超過了普通用戶的微博數(shù)。僵尸粉能發(fā)送大量微博，但并不能發(fā)送原創(chuàng)微博，只能大量轉(zhuǎn)發(fā)其他用戶的微博。本文定義微博轉(zhuǎn)發(fā)率計(jì)算轉(zhuǎn)發(fā)微博數(shù)在總微博數(shù)中所占的比例:

表2 僵尸粉微博內(nèi)容特征

2 基于模擬退火算法的可變速率BP神經(jīng)網(wǎng)絡(luò)－SAVBP

神經(jīng)網(wǎng)絡(luò)擁有較好的非線性能力與泛化能力，只要有足夠的訓(xùn)練樣本，BP神經(jīng)網(wǎng)絡(luò)就能自學(xué)習(xí)與自適應(yīng)。本文選取BP神經(jīng)網(wǎng)絡(luò)作為基本判別模型。

2.1 BP神經(jīng)網(wǎng)絡(luò)及其缺陷

在人工神經(jīng)網(wǎng)絡(luò)出現(xiàn)后的很長一段時(shí)間里，并沒有找到一種能解決連接權(quán)值調(diào)整問題的有效算法，直到BP算法出現(xiàn)，成功地解決了求解非線性連續(xù)函數(shù)的神經(jīng)網(wǎng)絡(luò)權(quán)重調(diào)整問題［4］。BP算法實(shí)質(zhì)為最速下降法迭代循環(huán)求解權(quán)值，網(wǎng)絡(luò)被分為輸入層、隱藏層、輸出層3層。文獻(xiàn)［5］指出:只要隱藏層中擁有足夠多的神經(jīng)元，BP神經(jīng)網(wǎng)絡(luò)就可以以任意精度逼近任何函數(shù)。

BP神經(jīng)網(wǎng)絡(luò)一般使用均方誤差作為性能指標(biāo)。假設(shè)使用的數(shù)據(jù)集為:

這里pQ是目標(biāo)的輸入，tQ是對(duì)應(yīng)的目標(biāo)輸出。

每輸入一個(gè)樣本，將神經(jīng)網(wǎng)絡(luò)的實(shí)際輸出與目標(biāo)輸出做比較，調(diào)整均方誤差的權(quán)值與偏置以使其最小化［6］。為便于計(jì)算，把輸入輸出矩陣化:這里a為實(shí)際輸出矩陣，t為目標(biāo)輸出矩陣，n為第n次迭代。

BP算法使用以下式子修改權(quán)值與偏置［2］:

其中:Wm為第m層對(duì)應(yīng)權(quán)值矩陣;bm為第m層對(duì)應(yīng)偏置矩陣;k為第k次迭代;?為學(xué)習(xí)速度;am－1為第m－1層網(wǎng)絡(luò)輸出;Fm(nm)為關(guān)聯(lián)函數(shù)。

BP神經(jīng)網(wǎng)絡(luò)采用最速下降法(梯度法)計(jì)算性能函數(shù)的最小值，因而存在著易陷入局部極小點(diǎn)、無法收斂、收斂速度慢等缺點(diǎn)［7］。

1)易陷入局部極小點(diǎn):BP網(wǎng)絡(luò)從某一初始點(diǎn)開始尋找使均方誤差下降且下降最快的點(diǎn)，但如圖1所示誤差函數(shù)是一個(gè)多維空間曲面，可能存在著多個(gè)凸點(diǎn)與凹點(diǎn)。在搜尋過程中，算法可能陷入某一小凹面區(qū)無法跳出，從而無法找出全局最小點(diǎn)。

圖1 誤差函數(shù)曲面

2)收斂速度慢、無法收斂:由Wm(k+1)= Wm(k)－?Sm(am－1)T可知:學(xué)習(xí)速度?直接影響收斂速度。當(dāng)?過小時(shí)，收斂速度較慢;當(dāng)?變大時(shí)，網(wǎng)絡(luò)又將變得振蕩、無法收斂。

2.2 BP神經(jīng)網(wǎng)絡(luò)的改進(jìn)

微博數(shù)據(jù)量龐大，使用傳統(tǒng)的BP神經(jīng)網(wǎng)絡(luò)判別僵尸粉計(jì)算緩慢，且當(dāng)計(jì)算陷入局部極小點(diǎn)時(shí)，判別效果較差。

由式(5)可知:學(xué)習(xí)速度?是個(gè)定值，直接影響收斂的速度，BP神經(jīng)網(wǎng)絡(luò)運(yùn)行的各時(shí)期對(duì)學(xué)習(xí)速度有著不同要求。當(dāng)距極小點(diǎn)較遠(yuǎn)時(shí)，要求較大的學(xué)習(xí)速度以提高收斂速度;當(dāng)越接近極小點(diǎn)時(shí)，要求越小的學(xué)習(xí)速度以提高收斂精度。文獻(xiàn)［7－9］引入學(xué)習(xí)因子與動(dòng)量項(xiàng)實(shí)現(xiàn)可變速率的神經(jīng)網(wǎng)絡(luò)，動(dòng)態(tài)改變學(xué)習(xí)速度。

模擬退火算法是一種優(yōu)秀的全局尋優(yōu)算法，其出發(fā)點(diǎn)是把現(xiàn)實(shí)生活中固體物質(zhì)的退火過程用于組合優(yōu)化問題。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在陷入局部最優(yōu)解時(shí)能以一定概率跳出并最終趨于全局最優(yōu)［10］。其中:k是常數(shù);exp表示自然指數(shù)，且dE＜ 0;T為初始溫度。

由式(7)可知:溫度T越高，dE的降溫的概率就越大;溫度越低，則出現(xiàn)降溫的概率就越小。又由于dE＜0，kT＞0，所以dE/kT＜0，P(dE)的函數(shù)取值范圍為(0，1)。隨著溫度T的降低，P(dE)會(huì)逐漸降低，并最終趨于穩(wěn)定。模擬退火算法能很好地解決BP算法易陷入局部最小點(diǎn)的缺點(diǎn)，理論上只要初始溫度T足夠大，則一定能找出全局最小點(diǎn)。

本文結(jié)合模擬退火算法與可變速率的BP神經(jīng)網(wǎng)絡(luò)，提出一種基于模擬退火算法的可變速率BP神經(jīng)網(wǎng)絡(luò)SAVBP，用以提高計(jì)算速度并尋找全局最優(yōu)解。

具體算法如下:

1)初始化:初始溫度T(充分大);

2)BP網(wǎng)絡(luò)開始訓(xùn)練，每一組數(shù)據(jù)輸入完畢，計(jì)算均方誤差Fn(X)。如Fn(X)－Fn－1(X)小于ε(ε為以極小值)，則判斷網(wǎng)絡(luò)陷入了局部最小點(diǎn)區(qū)間。當(dāng)溫度T小于ρ(ρ為一極小值)時(shí)轉(zhuǎn)8)。否則轉(zhuǎn)3)進(jìn)行模擬退火;

3)在原有權(quán)值W上添加一個(gè)隨機(jī)權(quán)值，在原有偏置b上添加一個(gè)隨機(jī)偏置，重新計(jì)算均方誤差F'(X);

4)計(jì)算增量Δt=F'(X)－Fn(X);

5)若Δt＜0則接受F'(X)作為新的當(dāng)前解，否則以概率exp(－Δt/T)接受F'(x)作為新的當(dāng)前解。T為當(dāng)前的溫度，當(dāng)T＜T0(T0為臨界溫度)時(shí)算法終止;

6)降溫退火T=r*T，0＜r＜1，如第5)步新解接受則轉(zhuǎn)7)，否則轉(zhuǎn)3);

7)以現(xiàn)有權(quán)值、偏置作為BP算法的起始點(diǎn)重新訓(xùn)練BP網(wǎng)絡(luò)，轉(zhuǎn)2);

8)所有局部極小點(diǎn)區(qū)間都已找出，判斷全局最小區(qū)間，使用可變速率BP神經(jīng)網(wǎng)絡(luò)繼續(xù)尋找全局最優(yōu)點(diǎn)。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)獲取與標(biāo)注

本文使用新浪微博提供的API對(duì)微博數(shù)據(jù)進(jìn)行抓取，新浪微博自身擁有一套簡單判別僵尸粉的方法。已被新浪判別出的僵尸粉在抓取數(shù)據(jù)時(shí)會(huì)被自動(dòng)過濾，無法抓取，故只研究未被新浪識(shí)別的新型僵尸粉，并最終成功抓取5 000個(gè)用戶數(shù)據(jù)、232 357條微博數(shù)據(jù)。抓取到的微博數(shù)據(jù)并未標(biāo)注普通用戶與僵尸粉，故本文根據(jù)用戶信息、微博內(nèi)容、鏈接關(guān)系等特征對(duì)用戶類別進(jìn)行手工標(biāo)注。此外，為了便于有效分類，需對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。在人氣指數(shù)、微博轉(zhuǎn)發(fā)率的計(jì)算中，有可能出現(xiàn)除數(shù)為0的情況，無法計(jì)算。該類用戶大多為新注冊(cè)用戶，無法分辨是普通用戶還是僵尸粉，故把該類用戶從數(shù)據(jù)集中排除。最終本文人工分類了4 500個(gè)用戶，其中普通用戶為4 111個(gè)，僵尸粉為389個(gè)。取其中1/3數(shù)據(jù)作為訓(xùn)練樣本，其余作為測試樣本。

3.2 實(shí)驗(yàn)結(jié)果

經(jīng)過多次實(shí)驗(yàn)表明:針對(duì)本文使用的數(shù)據(jù)集，在模擬退火中選取初始溫度T為3 000，降溫參數(shù)r為0.99，臨界溫度T0為0.01。在BP神經(jīng)網(wǎng)絡(luò)中選取激活函數(shù)為S型激活函數(shù)，網(wǎng)絡(luò)層數(shù)為3，隱含層神經(jīng)元數(shù)為6，學(xué)習(xí)速率?為0.1時(shí)具有較好的收斂性與較高的判別準(zhǔn)確率。

采用5－6－2的SAVBP網(wǎng)絡(luò)建立僵尸粉判別模型，如圖2所示。

圖2 SAVBP網(wǎng)絡(luò)建立僵尸粉判別模型

其中:ZF表示僵尸粉，NU表示普通用戶。

當(dāng)限定收斂精度為0.03時(shí)，不限制迭代次數(shù)，比較3類神經(jīng)網(wǎng)絡(luò)的收斂性曲線。由結(jié)果可知:傳統(tǒng)BP網(wǎng)絡(luò)無法收斂到0. 03;模擬退火改進(jìn)的BP網(wǎng)絡(luò)迭代13 360次可達(dá)到指定精度，如圖3所示;SAVBP網(wǎng)絡(luò)迭代6 820次可達(dá)到指定精度，如圖4所示。

圖3 模擬退火改進(jìn)的BP網(wǎng)絡(luò)迭代曲線

圖4 SAVBP網(wǎng)絡(luò)迭代曲線

由仿真結(jié)果可知:傳統(tǒng)的BP神經(jīng)網(wǎng)絡(luò)陷入了局部極小點(diǎn)，無法跳出，導(dǎo)致無法達(dá)到指定精度;模擬退火B(yǎng)P網(wǎng)絡(luò)與SAVBP網(wǎng)絡(luò)均能達(dá)到指定精度，但SAVBP網(wǎng)絡(luò)收斂速度明顯快于模擬退火改進(jìn)的BP網(wǎng)絡(luò)。

本文比較了3類神經(jīng)網(wǎng)絡(luò)算法迭代次數(shù)在50 000次之內(nèi)時(shí)的最小收斂精度。實(shí)驗(yàn)結(jié)果如表3所示。

表33 類神經(jīng)網(wǎng)絡(luò)最小精度對(duì)比

由表3可以看出:BP神經(jīng)網(wǎng)絡(luò)易陷入局部最小點(diǎn)，收斂精度最低;SAVBP網(wǎng)絡(luò)能達(dá)到最好的收斂精度。

使用SAVBP網(wǎng)絡(luò)分類僵尸粉，實(shí)驗(yàn)結(jié)果如表4所示。

對(duì)2 740個(gè)普通用戶進(jìn)行分類，分類正確的用戶為2 586個(gè)，準(zhǔn)確率為94.4%，并具有94.4%的召回率，F(xiàn)1－Measure達(dá)到了0.931。通過分析分類錯(cuò)誤的用戶信息，發(fā)現(xiàn)把普通用戶判別為僵尸粉的主要原因是微博網(wǎng)絡(luò)中某些用戶喜歡大量關(guān)注名人，并喜歡轉(zhuǎn)發(fā)名人用戶微博，導(dǎo)致微博轉(zhuǎn)發(fā)率、關(guān)注數(shù)等屬性皆與僵尸粉相似。但從其所發(fā)的原創(chuàng)微博與微博評(píng)論上可以看出其為普通用戶。

對(duì)260個(gè)僵尸粉進(jìn)行分類，分類正確的用戶為238個(gè)，準(zhǔn)確率為91.6%，并具有91.6%的召回率，F(xiàn)1－Measure達(dá)到了0.929。通過分析分類錯(cuò)誤的用戶信息，發(fā)現(xiàn)把僵尸粉誤判為普通用戶的主要原因?yàn)榻┦蹚拈_始使用微博到穩(wěn)定需要一個(gè)發(fā)展的過程，某些剛開始使用微博的僵尸粉在個(gè)人信息方面與穩(wěn)定時(shí)的僵尸粉特征差別較大。但從其所發(fā)微博中已經(jīng)表現(xiàn)出僵尸粉轉(zhuǎn)發(fā)多、無原創(chuàng)等特征。

4 結(jié)束語

微博在快速發(fā)展的同時(shí)產(chǎn)生了僵尸粉問題。本文首先對(duì)僵尸粉進(jìn)行了概念上的定義，分析了僵尸粉與普通用戶的不同特征，并針對(duì)微博網(wǎng)絡(luò)數(shù)據(jù)量大，使用普通BP神經(jīng)網(wǎng)絡(luò)計(jì)算緩慢、容易陷入局部極小等缺點(diǎn)，提出了SAVBP神經(jīng)網(wǎng)絡(luò)算法。最后實(shí)現(xiàn)了僵尸粉判別模型，使用新浪微博數(shù)據(jù)進(jìn)行測試，取得了較為滿意的結(jié)果。

隨著僵尸粉的不斷變異升級(jí)，本文所選取的特征可能會(huì)漸漸失效，同時(shí)僵尸粉也會(huì)產(chǎn)生更加復(fù)雜的特征。跟蹤僵尸粉的變異升級(jí)過程并使用新的特征判別僵尸粉將是一項(xiàng)長期的工作。此外，由于SAVBP基于模擬退火算法，具有不穩(wěn)定性，故選取更加優(yōu)秀的全局尋優(yōu)算法將是下一步的研究方向。

［1］Shen Yang，Li Shuchen，Ye Xiaoxiao，et al.Content mining and network analysis of microblog spam［J］.JCIT，2010，5(1):135－140.

［2］Ghosh S，Korlam G，Ganguly N.Spammers’Networks within Online Social Networks:A Case－Study on Twitter［J］.ACM WWW 2011，2011.

［3］郭浩，陸余良，王宇，等.多特征微博垃圾互粉檢測方法［J］.中國科技論文，2012，7(7):548－551.

［4］Hornik K M，Stinchcombe M，White H.Multilayer feedforward networks are universal approximators［J］.Neural Networks，1989，2(5):359－366.

［5］Vogl T P，Mangis J K，Zigler A K，et al.Accelerating the convergence of the backpropagation method［J］.Biological Cybernetics，1988，59:256－264.

［6］Martin T Hagan，Howard BDemuth.Neural Network Design［Z］.PWS Pub.Co，2002.

［7］唐艷，付存君，魏建新.基于自適應(yīng)學(xué)習(xí)速率的改進(jìn)BP神經(jīng)網(wǎng)絡(luò)［J］.計(jì)算機(jī)光盤軟件與應(yīng)用，2012(4): 48－49.

［8］羅勝琪，付金勇.對(duì)BP神經(jīng)網(wǎng)絡(luò)算法傳遞函數(shù)的改進(jìn)［J］.中國科技博覽，2011(28):418－418.

［9］馬玉梅，武玉厚.動(dòng)量因子對(duì)BP算法的影響［J］.中央民族大學(xué)學(xué)報(bào)，2008，17(4):312－313.

［10］孟力，陳少雄.基于模擬退火神經(jīng)網(wǎng)絡(luò)的高科技成果轉(zhuǎn)化評(píng)估研究［J］.科技管理研究，2011，31(15):91－93.

(責(zé)任編輯 楊黎麗)

Discrimination Method of Zombie Fans Based on SAVBP Neural Network

WANG Yue，ZHANG Jian－jin
(School of Computer Science and Engineering，
Chongqing University of Technology，Chongqing 400054，China)

:Zombie fans of microblogging interfere normal social environment and have enormous impact on microblogging users.First，this paper expounded microblogging zombie fans with the latest trends，analyzed microblogging zombie fans with different characteristics of normal users.Then，by the large amount of data for the microblogging，the use of BP neural network discriminant zombie fans is easy to fall into local minima，convergence slow convergence and other shortcomings.We proposed variable rate BP neural network－SAVBP based on simulated annealing algorithm，and established the zombie fans discriminant model.Sina microblogging data were used to evaluate the system.The results show that the system can identify microblogging zombie fans with 93%accuracy and 93%recall rate.Key words:zombie fans;BP neural network;simulated annealing;variable rate

10.3969/j.issn.1674－8425(z).2014.04.016

2013－12－10

重慶理工大學(xué)研究生創(chuàng)新基金資助項(xiàng)目(YCX2012317)

王越(1961—)，男，博士，教授，主要從事數(shù)據(jù)挖掘、數(shù)據(jù)庫技術(shù)、嵌入式系統(tǒng)及應(yīng)用研究;張劍金(1988—)，男，浙江湖州人，碩士研究生，主要從事社交網(wǎng)絡(luò)數(shù)據(jù)挖掘研究。

王越，張劍金.一種應(yīng)用SAVBP神經(jīng)網(wǎng)絡(luò)的僵尸粉判別方法［J］.重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版，2014 (4):72－76.

format:WANG Yue，ZHANG Jian－jin.Discrimination Method of Zombie Fans Based on SAVBP Neural Network［J］.Journal of Chongqing University of Technology:Natural Science，2014(4):72－76.

TP391

A

1674－8425(2014)04－0072－05