基于PSO-SVM算法的炒作微博識別研究

王恩賢， 陶宏才

(西南交通大學信息科學與技術學院，四川成都611756)

0 引言

隨著互聯網應用的快速發展和移動終端的大規模普及，以微博為代表，國內外微博用戶數量急劇增長，微博已經逐漸成為人們進行社交的工具。與此同時，微博的炒作現象嚴重影響用戶體驗及用戶安全，“網絡水軍”、“網絡推手”等利用微博散布謠言和虛假信息，操控網絡輿論，嚴重干擾了網絡秩序，也影響了社會的安定［1］。微博炒作的基本方式是通過微博營銷公司，雇傭名人微博、草根大號及水軍團等廣泛評論、轉發微博，在短時間內造成熱門微博的假象，以此向世界各地傳播信息。

目前，在對微博炒作的研究方面，主要集中在微博問政、微博傳播倫理研究和少量的微博炒作［2］。大部分研究停留在理論層面上，還沒有在技術層面上進行深層次的探討。隨著Web的發展，社交類網站的影響能力和輻射人群日益壯大，消息的真偽以及是否存在人為的操控言論的走向，逐漸成為網絡輿情研究的新熱點。結合理論和技術研究，對炒作微博的特征進行分析，構建特征集，基于SVM(support vector machine)算法，加入粒子群PSO(particle swarm optimization)算法對SVM模型中的誤差懲罰因子參數和核函數參數進行優化，分析對比得到最佳分類模型，對炒作微博進行有效的識別和檢測。研究開發高效的炒作微博的識別方法，對微博的健康發展具有重要的意義和應用價值。

1 SVM概述及PSO算法

1．1 SVM 概述

支持向量機根據有限的樣本信息，在模型的學習能力和復雜性之間尋求最佳結合［3］，通過選擇適當的函數使學習機的期望風險達到最小，保證通過有限訓練樣本得到小誤差分類器對獨立測試集的測試誤差比較小，從而得到一個具有最優分類能力和推廣泛化能力的學習機［4］，通過利用Lagrange優化方法可以把支持向量機最優分類面問題轉化為對偶問題［5］。

對于非線性可分的情況，SVM利用核函數將低維輸入空間映射到高維特征空間使線性可分，在低維、高維、小樣本和大樣本等情況下，RBF核函數都表現出了很好的學習能力，得到了廣泛的應用［6］。，文中選擇RBF函數作為SVM的核函數，最優化問題就取決于核參數g和懲罰因子c的選擇，這樣選擇較佳的參數可使分類模型具有較優的性能和推廣能力。

1．2 粒子群算法

1995 年，Kennedy 和 Eberhart［7］提出了基于種群的粒子群算法(particle swarm optimization，PSO)。其基本思想［8］是模擬鳥群飛行過程中的群體協作避免迷失方向，由此實現群體目的最優。PSO算法中所有的粒子都擁有一個由被優化函數產生的適應值(fitness)，以及決定飛行方向和距離的速度。PSO首先初始化一群隨機粒子，粒子追隨最優粒子在解空間中不斷更新自己的位置、速度和適應度值，從而產生下一代粒子。粒子飛行經過的最好位置為局部最優值，整個群體所經歷過的最好位置為群體的最優值。

文中將利用粒子群算法，優化SVM中的核參數g和誤差懲罰因子c。首先，根據種群數量的設置，為參數c和g分別初始化一組粒子群，并隨機生成種群中粒子的速度和位置。然后，使用目標函數計算種群中粒子的適應度值，并根據計算出的適應度值更新粒子種群的局部最優的和全局最優的c和g。最終，利用得到的較優c和g參數對，構造出PSO-SVM模型以識別炒作微博。

2 炒作微博特征分析與提取

2．1 社團模塊度

熱門微博榜是通過微博的轉發、評論數量及頻率等進行綜合排名的，為達到炒作的目的，炒作用戶一般聚集一群用戶，操作微博的輿論傳播。提取微博傳播網絡中的節點信息，通過網絡分析工具Pajek作網絡信息傳播，其傳播結構如圖1、圖2所示。從圖1可見，熱門微博信息傳播方式是逐層擴散出去的，并且傳播力度逐層減弱，呈現出核爆式的傳播。圖2為一條典型的炒作微博的信息傳播結構圖，此微博的傳播完全圍繞著幾個大V(粉絲數10萬以上)關鍵用戶進行傳播，很少有離散的節點傳播路徑，具有典型的群體策劃現象。

圖1 熱門微博信息傳播結構

圖2 炒作微博信息傳播結構

為能夠衡量網絡社團結構的劃分程度和聚集程度，Girvan和 Newman［9］定義了模塊性函數，定量地描述網絡社團的劃分和緊密程度。所謂模塊性，即網絡中連接社團結構內部節點的邊所占的比例與另外一個隨機網絡中連接社團結構內部節點的邊所占比例的期望值相減得到的差值。隨機網絡的構造，通過保持每個節點的社團屬性不變，節點的邊根據節點的度隨機連接來進行。如果隨機網絡的稠密程度期望值低于現實的社團內部連接稠密程度值，說明得到較好的社團結構劃分。通常用Q函數對社團模塊度水平進行描述。

假設已劃分出網絡社團結構，節點vi所屬的社團編號為σi，則網絡中社團內部的連邊所占比例為

在式(1)中，aij表示網絡鄰接矩陣中的元素，若vi和vj2節點無邊相連，aij=0，否則aij=1;若vi和vj是同一社團的節點，即 σi= σj時，δ(σi，σj)=1 ，否則為0。網絡中邊的數目M=0．5∑ aij。在社團結構固定時，構建出隨機連接邊的網絡，節點vi和vj之間存在連接邊的可能性為kikj/2M，其中ki和kj分別為節點vi和vj的度。由此，Q函數可以定義為

若社團內部節點間的邊數小于隨機連接得到的邊數，則Q小于0。若Q函數值接近1，表明社團結構內部連接高度緊密。在實際應用中，Q一般在0.3～0.7。

2．2 平均最短路徑

網絡信息傳播不僅依賴于小世界網絡中的最短路徑，還與網絡行為的多次社會性強化相關［10］。最短路徑是指2個節點間最小值的路徑，平均最短路徑是指社團網絡中任意兩節點最短路徑的均值。若2條微博的傳播數相同，而傳播節點間的平均最短路徑相差較大，則認為平均最短路徑大的微博，其傳播層數多，影響力大;而平均最短路徑小的微博，傳播多集中在某個或某幾個轉發者的粉絲之間，以至于傳播層數少，影響力小。利用平均最短路徑來判斷微博的擴散范圍，通過計算微博傳播中節點平均最短路徑，判斷節點間的緊密程度，以此識別出炒作微博。

文中采用Floyd算法計算最短路徑，基本思想是從任意節點i到任意節點j的最短路徑存在2種可能，一是直接從節點i到j，二是從節點i經過若干個節點k到j。設dpv表示節點p到節點v的最短路徑距離，對于網絡中的每一個節點k，檢查dik+dkj＜dij是否成立。如果成立，說明從節點i經過k到節點j的路徑比i直接到j的路徑更短，便設置dij=dik+dkj。循環遍歷完所有的節點k，dij存儲的值就是節點i到節點j的最短路徑距離。具體算法描述為:

(1)從任意一條單邊的路徑開始。設2點之間的距離是邊的權值，若2點之間沒有直接的邊相連，則權值設為無窮大。

(2)對每一對頂點p和v，查看是否存在一個頂點w使從頂點p到w再到v的路徑比己知的路徑更短。

(3)如果路徑更短，則更新。若存在未搜索節點，繼續步驟(2)，否則結束。

2．3 關鍵用戶屬性

在微博的傳播過程中，存在一些大V用戶，其轉發、評論等行為對微博的傳播起到至關重要的影響，這些重要的傳播節點稱為關鍵用戶。相關研究［11］發現，賬戶關注好友的質量和賬戶狀態特征最能體現正常賬戶和炒作賬戶之間的區別。為了能夠衡量賬戶及其關注好友的質量，定義聲望值FM反映賬戶的影響力。FM定義為

其中，Nf(u)和Ng(u)分別表示賬戶u的粉絲數和關注數。

提取炒作微博傳播過程中的關鍵用戶的屬性信息并作累積分布函數曲線(CDF)如圖3～6所示。

圖3 關鍵用戶平均關注數

圖4 關鍵用戶平均聲望值

圖5 關鍵用戶關注好友的平均聲望值

圖6 關鍵用戶關注好友的平均粉絲數

由圖3可以看出，正常微博中絕大部分的關鍵用戶平均關注數高于550，炒作微博中絕大部分的關鍵用戶平均關注數不足450。由圖4和圖5可以看出，絕大多數正常微博中關鍵用戶和關注好友的平均聲望值高于炒作微博的關鍵用戶和關注好友的平均聲望值。

由圖6可以看出，炒作微博中85%以上的關鍵用戶關注好友的平均粉絲數數量級為105，而正常微博中85%以上的關鍵用戶關注好友的平均粉絲數數量級為106。

炒作微博中的節點用戶質量與正常微博中的節點用戶質量有著明顯的區別，可以用反映賬戶質量的相關特征加以區分炒作微博和正常微博。關鍵用戶關注好友的質量通過好友平均粉絲數和平均聲望值反映，而關鍵用戶的狀態特征通過用戶平均聲望值和平均關注數體現。

3 基于SVM優化算法的炒作微博識別方法

炒作微博識別框架基本流程圖如圖7所示，識別框架主要包括數據預處理、特征提取、模型建立及訓練測試和決策分類等幾個主要步驟組成。數據預處理主要是對原始數據進行分類、節點關系提取以及節點粉絲和關注數的計算。特征是通過微博的節點傳播途徑和節點信息來提取，提取出的特征包括社團模塊度、平均最短路徑、關鍵用戶關注好友的平均聲望值和平均粉絲數以及關鍵用戶的平均聲望值和平均關注數。

在模型的建立過程中，通過粒子群算法PSO對SVM中的核參數g和懲罰因子c進行優化，PSO優化SVM參數流程圖如圖8所示。Vapnike等［12］研究表明，核參數g和懲罰因子c是影響SVM性能的關鍵因素，設置c的取值范圍為［0.1，100］，g的取值范圍為［0.01，1000］。由于需要優化的參數較少，所以種群粒子數目設為20，迭代步數為200。加速度因子c1和c2表示向局部最優和全局最優推進的加速度權值，c1一般等于 c2，取值范圍在［0，4］［13］，文中都取 2。為能夠提高算法的搜索能力和分類能力，針對PSO算法容易早熟和后期容易在全局最優解附近振蕩的現象，采用線性遞減權重法對慣性權重ω進行調整，ωmax取值0.9，ωmin取值0.4。

圖7 識別框架流程圖

圖8 PSO優化SVM參數流程圖

炒作微博的識別分為訓練階段和測試階段，首先使用訓練數據訓練模型，分析訓練結果和準確率。然后使用模型測試數據，得出測試數據對應的分類結果，最后通過對比預先人工標注的測試數據分類標簽得出最終的分類準確率。

4 實驗結果與分析

4．1 數據集的獲取及分析

基于新浪微博實驗平臺，利用API接口和網絡爬蟲工具相結合，提取微博的傳播路徑和節點信息，計算每條微博關鍵節點的屬性信息和傳播節點之間的緊密程度，以判斷是否有社團存在的可能性。從熱門微博中選擇飲品、娛樂等話題獲取實驗數據集，剔除變量缺失的樣本數據，共獲得610個樣本。數據主要包括微博用戶的屬性信息(關注、粉絲和微博等)，好友屬性信息，轉發用戶屬性信息。

由于目前沒有標準的炒作微博數據集，所以需要以人工標注的形式對微博進行標注。在標注過程中，選擇房價、飲品和娛樂等話題數據標注，以使數據集的標注具有多樣性。每條熱門微博同時由2個人標注，只有標注結果一致才加入到數據集中，盡可能避免標注時的人為主觀性因素。

使用SVM模型對數據進行分類，發現2類數據具有明顯的區別。由圖9可見，炒作微博的社團模塊度集中于0.8～0.9，超出了正常社團的范圍［0.3，0.7］，并且平均最短路徑值集中于3～5，明顯背離了六度分隔理論，傳播層次少，傳播主要集中在某幾個轉發者的粉絲之間，體現出了節點間具有較強的緊密程度。對于炒作微博和正常微博，用戶的平均聲望值、平均關注數以及好友的平均聲望值和平均聲望值有著較為明顯的區別，反映出炒作微博的關鍵節點用戶及其好友的質量與正常微博的賬戶質量之間有著明顯的區別。

圖9 炒作微博與正常微博的分類

4．2 評價指標

通過模型預測微博分類，為了能夠反映出分類結果的優劣，定義以下幾個評價指標衡量分類的質量。

表1 炒作微博識別結果

表1所示為炒作微博識別結果。常用的評價指標有準確率(P)，召回率(R)是正確識別出的炒作微博數量占總炒作微博數量的比例，誤報率(FP)是正常微博被識別為炒作微博的數量占總正常微博數量的比例，F1度量值是對P和R的加權調和平均，F1較高時說明實驗方法比較理想，計算公式如下:

準確率

4．3 結果對比與分析

為驗證模型的識別準確率，基于Matlab R2012a和LibSVM實驗平臺進行實驗。每條微博提取出了6個特征，即:社團模塊度、平均最短路徑、關鍵用戶關注好友平均粉絲數、關鍵用戶關注好友平均聲望值、關鍵用戶平均聲望值、關鍵用戶平均關注數。提取社團模塊度和平均最短路徑構成2維特征向量Fcls2，微博的6個特征構成6維特征向量Fall。

實驗使用PRO算法對支持向量機的模型的核參數和懲罰因子進行優化，為衡量PRO算法優化SVM的有效性，采用基于網格搜索法優化的SVM作為參比模型進行比較，然后以特征向量Fcls2和Fall作為2種模型的輸入，采用十折交叉驗證的方式進行評估，并依據3個評價指標比較分類結果的優劣，得到結果見表2和表3。

表2 采用不同的特征組合對炒作微博的SVM分類結果

表3 采用不同的特征組合對炒作微博的PSO-SVM分類結果

由表2和表3可以看出，使用6維組合特征向量的分類效果要優于2維特征向量。主要原因在于，一些明星粉絲之間的口水戰和娛樂明星為了突出微博重要性而重復轉發，造成微博在傳播過程中的參與人群相對單一，傳播層次少，從而使社團模塊度較大和平均最短路徑較小，最終被誤識別為炒作微博，因此使用2維特征向量Fcls2分類效果較差。炒作微博中的節點用戶質量與正常微博中的節點用戶質量有著明顯的區別，因此提取傳播網絡中的關鍵用戶屬性信息，組成6維特征向量Fall，用于衡量傳播網絡中用戶和好友的質量，區分被誤識別為炒作微博的正常微博，從而使分類準確率有較大提高。實驗說明社團模塊度和平均最短路徑與關鍵用戶屬性特征具有優勢互補的特性，兩者結合更能體現炒作微博的特性，提高分類準確率。

對比SVM，使用PSO-SVM分類模型可以使炒作微博的分類準確率達到90%以上，并且誤報率不到1%，F1度量值達到90%以上，說明PSO對SVM的參數優化具有明顯的效果，PSO-SVM分類模型比較理想，能夠高效地解決炒作微博的識別問題，為微博的健康發展提供支持。

5 結束語

對炒作微博的傳播網絡節點進行分析，基于社團模塊度、平均最短路徑和關鍵用戶屬性等特征，得出識別準確率較高的PSO-SVM分類模型，該模型使用PSO對SVM中的參數進行優化，避免了人為選擇的隨機性，使參數選擇更合理。實驗結果表明，文中方法能有效地識別出炒作微博，準確率達到90%以上，具有一定的合理性和適用性，并且對明星或官方微博的影響因子進行了深度細化，能夠較好克服微博名人效應對識別準確率的干擾。

［1］ 任一其，王雅雷，王國華，等.微博謠言的演化機理研究［J］.情報雜志，2012，31(5)：50-54.

［2］ 齊海鳳.網絡輿情熱點發現與事件跟蹤技術研究［D］.哈爾濱：哈爾濱工程大學，2008.

［3］ Dimitrios C，Takis K.Wavelet-based rotational invariant roughness features for texture classification and segmentation［J］.IEEE Transactions on Image Processing a Publication of the IEEE Signal Processing Society，2002，11(8)：825-837.

［4］ Cortes C，Vapnik V.Support-Vector Networks［J］.Machine Learning，1995，20(3)：273-297.

［5］ Burges C J C.A Tutorial on Support Vector Machines for Pattern Recognition［J］.Data Mining ＆Knowledge Discovery，1998，2(2)：121-167.

［6］ 高錦.基于SVM的圖像分類［D］.西安：西北大學，2010.

［7］ KENNEDY J，EBERHART R.Particle swarm optimization［C］.Proc of IEEE International Conference on Neural Networks.Piscataway：IEEE Press，1995：1942-1948.

［8］ MATLAB中文論壇.MATLAB神經網絡30個案例分析［M］.北京：北京航空航天大學出版社，2010.

［9］ Newman M E J，Girvan M.Finding and evaluating community structure in networks［J］.Physical Review E Statistical Nonlinear＆Soft Matter Physics，2004，69：026-113.

［10］ LüL，Chen D B，Zhou T.Small world yields the most effective information spreading ［J］.New Journal of Physics，2011，(9-10)：825-834.

［11］ 張進，劉琰，羅軍勇，等.基于特征分析的微博炒作賬戶識別方法［J］.計算機工程，2015，(4)：48-54.

［12］ 鄧乃揚.數據挖掘中的新方法［M］.北京：科學出版社，2004.

［13］ 周輝仁，鄭丕諤，王嵩，等.基于粒子群優化算法LS-SVM財務預警［J］.計算機工程，2009，35(10)：280-282.

［14］ Girvan M，Newman M E J.Community structure in social and biological networks［J］.Proceedings of the National Academy of Sciences of the United States of America，2001，99(12)：7821-7826.

［15］ Newman M E J，Watts D J.Renormalization group analysis of the small-world network model［J］.Physics Letters A，1999，263(4)：341-346.

［16］ Bu Z，Xia Z，Wang J.A sock puppet detection algorithm on virtual spaces［J］.Knowledge-Based Systems，2013，37(2)：366-377.

［17］ 袁立庠.微博的傳播模式與傳播效果［J］.安徽師范大學學報：人文社會科學版，2011，39(6)：678-683.

［18］ 汪小帆，劉亞冰.復雜網絡中的社團結構算法綜述［J］.電子科技大學學報，2009，38(5)：537-543.