一種應用SAVBP神經網絡的僵尸粉判別方法

王越，張劍金

(重慶理工大學計算機科學與工程學院，重慶 400054)

一種應用SAVBP神經網絡的僵尸粉判別方法

王越，張劍金

(重慶理工大學計算機科學與工程學院，重慶 400054)

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

僵尸粉;BP神經網絡;模擬退火;可變速率

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

1 僵尸粉特征分析

僵尸粉由軟件自動產生并維護，并沒有實際真人使用。故僵尸粉在個人信息、微博內容等方面都有聚團相似性且與普通用戶特征差別明顯。

1.1 個人信息特征

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

普通用戶的粉絲數與關注數較為接近，反映了現實生活中“對等”的社交關系，即我認識的和認識我的人的數量相差不大。而僵尸粉的關注數遠遠大于他的粉絲數，偏離了實際的社交關系網絡。個人信息定義的僵尸粉特征如表1所示。

表1 僵尸粉個人信息特征

1.2 微博內容特征

早期的僵尸粉并不會發送微博，但為了逃避新浪微博封殺，僵尸粉開始升級，大量更新微博，其微博數遠遠超過了普通用戶的微博數。僵尸粉能發送大量微博，但并不能發送原創微博，只能大量轉發其他用戶的微博。本文定義微博轉發率計算轉發微博數在總微博數中所占的比例:

表2 僵尸粉微博內容特征

2 基于模擬退火算法的可變速率BP神經網絡－SAVBP

神經網絡擁有較好的非線性能力與泛化能力，只要有足夠的訓練樣本，BP神經網絡就能自學習與自適應。本文選取BP神經網絡作為基本判別模型。

2.1 BP神經網絡及其缺陷

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

BP神經網絡一般使用均方誤差作為性能指標。假設使用的數據集為:

這里pQ是目標的輸入，tQ是對應的目標輸出。

每輸入一個樣本，將神經網絡的實際輸出與目標輸出做比較，調整均方誤差的權值與偏置以使其最小化［6］。為便于計算，把輸入輸出矩陣化:這里a為實際輸出矩陣，t為目標輸出矩陣，n為第n次迭代。

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

其中:Wm為第m層對應權值矩陣;bm為第m層對應偏置矩陣;k為第k次迭代;?為學習速度;am－1為第m－1層網絡輸出;Fm(nm)為關聯函數。

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

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

圖1 誤差函數曲面

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

2.2 BP神經網絡的改進

微博數據量龐大，使用傳統的BP神經網絡判別僵尸粉計算緩慢，且當計算陷入局部極小點時，判別效果較差。

由式(5)可知:學習速度?是個定值，直接影響收斂的速度，BP神經網絡運行的各時期對學習速度有著不同要求。當距極小點較遠時，要求較大的學習速度以提高收斂速度;當越接近極小點時，要求越小的學習速度以提高收斂精度。文獻［7－9］引入學習因子與動量項實現可變速率的神經網絡，動態改變學習速度。

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

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

本文結合模擬退火算法與可變速率的BP神經網絡，提出一種基于模擬退火算法的可變速率BP神經網絡SAVBP，用以提高計算速度并尋找全局最優解。

具體算法如下:

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

2)BP網絡開始訓練，每一組數據輸入完畢，計算均方誤差Fn(X)。如Fn(X)－Fn－1(X)小于ε(ε為以極小值)，則判斷網絡陷入了局部最小點區間。當溫度T小于ρ(ρ為一極小值)時轉8)。否則轉3)進行模擬退火;

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

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

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

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

7)以現有權值、偏置作為BP算法的起始點重新訓練BP網絡，轉2);

8)所有局部極小點區間都已找出，判斷全局最小區間，使用可變速率BP神經網絡繼續尋找全局最優點。

3 實驗與結果分析

3.1 實驗數據獲取與標注

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

3.2 實驗結果

經過多次實驗表明:針對本文使用的數據集，在模擬退火中選取初始溫度T為3 000，降溫參數r為0.99，臨界溫度T0為0.01。在BP神經網絡中選取激活函數為S型激活函數，網絡層數為3，隱含層神經元數為6，學習速率?為0.1時具有較好的收斂性與較高的判別準確率。

采用5－6－2的SAVBP網絡建立僵尸粉判別模型，如圖2所示。

圖2 SAVBP網絡建立僵尸粉判別模型

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

當限定收斂精度為0.03時，不限制迭代次數，比較3類神經網絡的收斂性曲線。由結果可知:傳統BP網絡無法收斂到0. 03;模擬退火改進的BP網絡迭代13 360次可達到指定精度，如圖3所示;SAVBP網絡迭代6 820次可達到指定精度，如圖4所示。

圖3 模擬退火改進的BP網絡迭代曲線

圖4 SAVBP網絡迭代曲線

由仿真結果可知:傳統的BP神經網絡陷入了局部極小點，無法跳出，導致無法達到指定精度;模擬退火BP網絡與SAVBP網絡均能達到指定精度，但SAVBP網絡收斂速度明顯快于模擬退火改進的BP網絡。

本文比較了3類神經網絡算法迭代次數在50 000次之內時的最小收斂精度。實驗結果如表3所示。

表33 類神經網絡最小精度對比

由表3可以看出:BP神經網絡易陷入局部最小點，收斂精度最低;SAVBP網絡能達到最好的收斂精度。

使用SAVBP網絡分類僵尸粉，實驗結果如表4所示。

對2 740個普通用戶進行分類，分類正確的用戶為2 586個，準確率為94.4%，并具有94.4%的召回率，F1－Measure達到了0.931。通過分析分類錯誤的用戶信息，發現把普通用戶判別為僵尸粉的主要原因是微博網絡中某些用戶喜歡大量關注名人，并喜歡轉發名人用戶微博，導致微博轉發率、關注數等屬性皆與僵尸粉相似。但從其所發的原創微博與微博評論上可以看出其為普通用戶。

對260個僵尸粉進行分類，分類正確的用戶為238個，準確率為91.6%，并具有91.6%的召回率，F1－Measure達到了0.929。通過分析分類錯誤的用戶信息，發現把僵尸粉誤判為普通用戶的主要原因為僵尸粉從開始使用微博到穩定需要一個發展的過程，某些剛開始使用微博的僵尸粉在個人信息方面與穩定時的僵尸粉特征差別較大。但從其所發微博中已經表現出僵尸粉轉發多、無原創等特征。

4 結束語

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

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

［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］唐艷，付存君，魏建新.基于自適應學習速率的改進BP神經網絡［J］.計算機光盤軟件與應用，2012(4): 48－49.

［8］羅勝琪，付金勇.對BP神經網絡算法傳遞函數的改進［J］.中國科技博覽，2011(28):418－418.

［9］馬玉梅，武玉厚.動量因子對BP算法的影響［J］.中央民族大學學報，2008，17(4):312－313.

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

(責任編輯 楊黎麗)

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

重慶理工大學研究生創新基金資助項目(YCX2012317)

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

王越，張劍金.一種應用SAVBP神經網絡的僵尸粉判別方法［J］.重慶理工大學學報:自然科學版，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