微博演化網絡的負信息分類方法*

趙 一，何克清，李 昭，黃貽望

1.武漢大學 計算機學院 軟件工程國家重點實驗室，武漢 430072

2.三峽大學 計算機與信息技術學院，湖北 宜昌 443002

微博演化網絡的負信息分類方法*

趙 一1，何克清1，李 昭2+，黃貽望1

1.武漢大學 計算機學院 軟件工程國家重點實驗室，武漢 430072

2.三峽大學 計算機與信息技術學院，湖北 宜昌 443002

ZHAO Yi,HE Keqing,LI Zhao,et al.Micro blog evolutionary network to classification method of negative information.Journal of Frontiers of Computer Science and Technology,2017,11(1)：91-98.

序列最小優化（SMO）；支持向量機（SVM）；演化網絡；UCI數據集；負信息

1 引言

隨著Web2.0的興起，不僅是電子郵件成為人們生活中不可缺少的部分，微博和微信等也成為人們彼此交流的主要工具。自從2006年Williams創建了Twitter以來，微博對整個互聯網產生了巨大的影響。據美國財經雜志《商業周刊》稱，Twitter已經成為世界最大同時也是信息速度傳遞最快的虛擬社區，擁有著超乎想象的社會和政治影響力。信息交流主要是通過關注和轉帖等互動形式來進行，因此用戶消息會在Twitter中呈幾何級數增長，并在用戶間迅速傳播。而信息的多元化也將影響到未來社會和政治的發展[1]。因此微博這樣一個互聯網新生事物已經成為文本挖掘、網絡輿情分析與垃圾信息處理等重要研究方向[2]。以SNS（social networking services）和微博為代表的Web2.0應用占整個互聯網流量的比重越來越高，它們與互聯網用戶的聯系越來越密切，網民花費大量的時間上網，主要集中在SNS網站（如人人網、開心網）和發布微博（新浪微博、騰訊微博、搜狐微博等），但是有用數據中夾雜著眾多的無用信息或者是有危害的信息，從而它對互聯網上人們的影響日趨增強。因此對微博進行分類在用戶個性化推薦、微博社群以及垃圾信息過濾中都至關重要。而有些微博屬于長文本，有些微博屬于短文本，包含各式各樣的信息量，傳統的文本分類方式并不能很好地用在微博上。目前主流的分類垃圾信息的方法有以下幾種：第一種是利用Navie Bayes[3]（后驗概率）計算特征所屬空間的概率，取其最大者為判定結果。它通過訓練數萬封電子郵件內容，包含垃圾郵件/非垃圾郵件，提取郵件內單詞，輸入字典，過濾出現設定次數的單詞，具體公式為：

式（1）中p表示概率；?表示所屬類別。然后定義probSPAM=probHAM=1，完成4步統計后，兩個prob變量分別乘以對應類別的郵件數，然后除以所有郵件總數，即得到Prior。比較probSPAM和probHAM，如果probSPAM大就分到垃圾信息類，如果probHAM大就分到正常信息類。但是此方法對信息分類太過于考慮一個詞匯的垃圾性，如果垃圾信息發送者插入通常與垃圾郵件無關的隨機無害詞，從而降低電子郵件的垃圾郵件分數，使得它更有可能在Prior值上更接近于正常信息。

近年來，有關短文本分類及應用的研究不斷推出很多新的方法，并已經成為自然語言領域和文本挖掘的一個熱點研究課題。同時，在很多知名的國內外會議和期刊上都有這方面的論文發表。其中，有使用LDA（latent Dirichlet allocation）聚類來找到同一主題的類別[4]，這種使用聚類的方法缺點是無法準確定義類簇。比如文獻[5]提出了兩類垃圾評論的類型：（1）顯式垃圾評論；（2）隱式垃圾評論。文章雖然利用LDA找出了隱藏的垃圾評論，擴大了垃圾評論的范圍，但是因為作者使用一般的LDA模型，所以對topic話題個數K取值無法明確分出話題個數,它能否代表準確的垃圾評論類別是值得深入研究的。但是LDA聚類缺點是如果處理短文本，比如特征稀疏的評論處理，聚類效果就會打折扣。另外，當發現整個博客垃圾評論后，并不能及時地控制整個網絡的傳播路徑，因此要想準確地定位垃圾評論最有效的方法還是對評論文本進行分類，日前只能利用機器學習的方法分辨出垃圾郵件以及它們的特征。

文獻[6]試圖通過對微博平臺上廣告傳播的分析，發現微博廣告傳播的模式特征；并且收集了一些廣告信息的傳播數據，將每條信息的傳播途徑用一個傳播樹表示；針對每個傳播樹，共提取了包括傳播參與者的數量、傳播途徑的拓撲結構和時間的傳播特征3個方面共33個特征，并使用K-Means聚類算法對這些傳播樹進行了聚類，驗證了名人效應在信息傳播中的推動作用，從而證明了網絡微博的傳播網絡不是隨機網絡結構。但是文章中并沒有對微博拓撲結構隨時間變化進行驗證，也沒有提出有效的控制垃圾廣告軟件傳播的防御機制，說明微博垃圾信息處理與管理在國內大數據信息化研究中是一個亟待解決的問題?；谝陨闲枨蟊疚闹饕鉀Q了垃圾信息分類問題和跟蹤垃圾信息發送者ID，依據微博轉發形成的演化網絡，從源頭隔離垃圾發送者。第2章主要介紹了一些相關準備工作；第3章介紹本文的核心算法——基于SMO（sequential minimal optimization）的SVM（support vector machine）垃圾信息的分類算法，并對UCI數據集構建演化網絡模型，利用SVM分類算法找出垃圾信息發送者，并根據演化網絡結構，在關鍵節點標記垃圾發送者ID，并根據轉發內容是否為垃圾信息，來判定是否應該隔離它；第4章是實驗流程以及結果分析和驗證；最后，總結全文并計劃下一步的工作。

2 UCI數據集以及分類

2.1 UCI新浪微博數據集

UCI數據庫是CaliforniaIrvine大學提出的用于機器學習的數據庫[7]，這個數據庫在2015年5月進行了更新，新增了各行各業的數據集12個，加上原來數據庫的200多個數據集，基本覆蓋知識領域。每個數據文件（*.data）包含以“屬性-值”對形式描述的很多個體樣本的記錄。對應的*.info文件包含大量的文檔資料。

本文數據集來源UCI官網[8]，2015年3月17日更新。此數據集提供者爬取新浪微博，這些數據適合用于研究和學習，以及做一些社會網絡研究。其中weibo_user.csv文件描述屬性如下：user_id是新浪微博用戶ID；user_name是賬戶昵稱；account registration gender包括男和女；class是微博賬戶等級；message是賬號注冊地點或其他個人信息；post_num是到現在為止發帖數量；follower_num是此賬號微博粉絲的數量；followee_num是此賬號關注過的微博；follow ratio是博客A關注過微博數/A關注的微博；is_spammer是手動標注標簽，1指垃圾信息發送者，0指正常信息發送者。user_post.csv文件描述屬性如下：post_id是發新浪微博的用戶ID；微博發送的時間；微博帖子接收者ID；repost_num是帖子通過別人的轉發數。Commnet_num是別人評論的次數。followefollowee.csv文件描述屬性如下：follower是粉絲（關注者）的昵稱；follower_id是粉絲的ID；followee是關注的微博昵稱；followee_id是關注的微博ID。

2.2 構造演化網絡

通過以上分析，可以得出，如果微博用戶A的帖子被用戶B轉發，記為eAB；或者微博用戶A的帖子被用戶B關注，記為eBA。最終構成無向圖，記為G(V,E)。邊權[9]是網絡中用來衡量節點A和節點B共享的邊的關聯度大小的量，記A轉發B的次數即出度為repost_num，B發給A的次數即入度為post_num；N=repost_num+post_num。則A和B鏈接的權重構建出新浪微博社交網絡中具有互粉關系[10]的無向權重圖G′=(V,E)。

依據UCI新浪微博數據集，得到所構建的復雜系統擁有共同的重要特性：大部分節點只有少數幾個鏈接，而某些節點卻擁有與其他節點的大量鏈接。這些具有大量鏈接的節點稱為“集散節點”，從圖1可知，“集散節點”所擁有的鏈接數可能高達數百、數千甚至數萬，由此得出，這一特性似乎能說明新浪微博的演化網絡是無尺度的。從而也會擁有無尺度網絡具有的某些重要特性，比如它們都可以承受意外的故障，但面對協同式攻擊卻很脆弱。

由于篇幅所限，本文提供的新浪微博演化網絡圖，只是隨機抽取用戶昵稱節點，并且使用Gephi工具畫出UCI數據集中用戶的帖子轉發關系圖。從中可以看出，演化網絡中存在著一些“集散節點”，比如“新百倫商城”，“孚禾靜靜_”“積奇薄荷少女懷亦”，“手機用戶1779439745”等。圖1中也有一些離散的節點，這些用戶只發過微博，出度和入度都為0，比如“IT經濟學”“戰刀_騎士”等孤立節點，轉發關系和出度與入度可以清晰觀測。

2.3 中文分詞算法

對用戶帖子內容的分詞，本文使用的是改進的中科院中文分詞算法[11]。本文舉例“新百倫商城”和“孚禾靜靜_”，對微博帖子的分詞改進效果如表1所示。

兩位微博用戶發帖，對帖子正文進行分詞。從表1中可以得出，使用改進后的分詞算法可以在幾次迭代運算識別出準確的名詞，并且能夠識別出符號中的特有名詞，如[]中的“奧汀羽酵素反饋”名詞。

2.4 SMO SVM模型

本文分析博客所發帖子是否為垃圾信息的分類算法選用的是SMO優化算法[12]，該算法是Platt在1998年提出，被認為是很快的二次規劃優化算法，對線性SVM和數據稀疏能更好地處理。SMO SVM模型已經成功應用到文本分類、信息檢索等諸多文本相關的領域[13-14]。圖2為SMO SVM模型算法流程。

Fig.1 Evolving network user of forwarding relationship圖1 用戶轉發關系的演化網絡

Table 1 Improved Chinese word segmentation method表1 改進中文分詞法

Fig.2 SMO SVM model algorithm圖2 SMO SVM模型算法

SMO SVM需要把文本信息分為有用文本和負面文本，該問題是基本的線性可分。

如果用x表示數據點，用y表示類別（y取值可以為1或者-1），分解方程可以表示為：

根據文獻[9]得知，

當SVM模型建立完成后，第3章將詳細描述本文如何對UCI數據集文本進行分類。

3 SMO SVM模型分類

3.1 特征抽取

本文認為負面信息可以通過情感詞典來輔助抽取特征項，利用情感詞典HowNet[15]作為基礎詞表，并融入當今熱點網絡流行情感詞匯構成的新情感詞典，例如“代理產品”、“減肥產品”等，具有明顯特征色彩的詞匯，用于篩選出這些關鍵詞語。

針對UCI用戶發送帖子進行預處理后只留下了名詞、動詞、形容詞，這些帶有特征的詞匯，設正面信息記為POS，負面信息記為NEG，再進行特征提取，其步驟如下。

（1）計算每個詞特征t的觀測值：

A為包含t且屬于POS的文本個數。

B為包含t且屬于NEG的文本個數。

C為不包含t且屬于POS的文本個數。

D為不包含t且屬于NEG的文本個數。

（2）對每個特征t計算它的卡方值x2：

（3）取x2排序前5個值作為t的特征項。

訓練集的建立，以“新百倫商城”用戶為例，他發布了一條微博，其內容包括“專賣”詞匯，則“專賣”屬于正面類別的文檔數為2篇，包含“專賣”屬于負面類別的文檔數為10，不包含“專賣”，卻屬于正面文檔數為12，既不包含“專賣”又不屬于正面文檔數為8。代入式（4）中可以得到卡方驗證的值，然后生成SVM分類的特征數據。

3.2 用戶節點屏蔽

通過上述分析，判斷當前用戶所發信息是否屬于負面信息，如果是負面信息則屏蔽用戶。從圖1可以知道，“新百倫商城”用戶是一個集散節點，他與另外一個集散節點“積奇薄荷少女懷亦”互粉過，從分類結果得知，“新百倫商城”是一個負面信息發送者，他所發微博基本被分到負面類中，而“積奇薄荷少女懷亦”是一個主要發送正面信息為主的用戶。正是因為這種原因，他們的follower（粉絲）眾多。本文引入演化網絡方法，并結合SMO SVM分類算法，能夠準確地分辨誰是負面信息（主要以廣告信息為主）的發送者，因此屏蔽了“新百倫商城”，如圖3所示。

Fig.3 Evolving network after SVM classifying圖3 SVM分類后生成的演化網絡

從圖3中可以看到“新百倫商城”和“積奇薄荷少女懷亦”節點已經過處理，屏蔽了“新百倫商城”。可以自動完成負面節點邊的刪除，從而實現對負面信息來源的屏蔽功能。

算法1演化網絡分類算法

4 實驗結果及驗證

本文實驗數據全部來源于“2015年UCI自然語言處理和機器學習”提供的測評數據集，它包含142 369位用戶，發布近20萬篇帖子。測評數據以CVS格式存儲，總數據大小為27.2 MB。

本文對測試數據分別進行3種方法的實驗，包括現在流行的負面信息分類法貝葉斯分類法、SVM分類法、SMO SVM分類法[16]。

在對SVM分類方法的有效性進行評估時，本文使用的評估指標是準確率（Precision）、召回率（Recall）、F值（F-measure）。對SVM分類法與SMO SVM分類法的分類情況進行人工觀測。

通過圖4和圖5得知，針對二分類數據（微博負面信息數據集），SMO SVM分類算法比一般的SVM分類算法要更加準確。圖中紅色點代表微博中的負面信息，藍色點代表微博中的正面信息，褐黃色點代表未知準確分類信息。圖4使用SMO SVM分類算法，其中只有6個點的文本特征沒有準確分類。圖5使用SVM分類算法，可以得知，未分類的褐黃色點有8個，這比SMO算法效率要低20%左右。

Fig.4 SMO SVM classification algorithm圖4 SMO SVM分類算法

Fig.5 SVM classification algorithm圖5 SVM分類算法

從圖6中可以知道，對于微博短文本SMO SVM算法在傾向于負面信息的文本分詞上性能有一定的提高，它較前兩個方法都有較高的正確率、召回率、精度值。

Fig.6 Distinguish results of negative information圖6 負面信息識別結果

實驗表明，基于UCI數據集的SMO SVM分類算法結合用戶轉發微博連接的演化網絡分類方法，能夠有效地分辨微博用戶發帖子的性質，如果該用戶所發帖子為正面信息，則不屏蔽該貼，若是用戶發送負面信息，如廣告、謠言等信息時，能立刻分辨出，并且屏蔽用戶。

5 結論及展望

本文以UCI最新微博數據集為實驗基礎，使用卡方驗證抽取特征向量，并使用SMO SVM算法與貝葉斯和SVM分類算法在處理二分類問題上進行比較。最后在正確率、召回率、F值方面對以上3種算法進行比較，得到SMO SVM檢測負面信息文本有較高的準確率，并且能提供更好的微博屏蔽效果。下一步工作，將完善情感詞典，改進SMO SVM算法，來提高自動識別新興詞匯，加強短語樣本的學習，繼續優化特征向量的選取，加強實時數據爬取，希望能做到實時監控用戶發送信息等功能。

[1]Bowles C.TwitterCore data library team Hadoop optimization experience[EB/OL].Twitter Job Bole[2015-07-02].http:// blog.jobbole.com/88283/.

[2]Peng Xixian,Zhu Qinghua,Liu Xuan.Research on behavior characteristics and classification of micro-blog users-taking“Sina Micro-blog”as an example[J].Information Science, 2015,33(1):69-75.

[3]Hui Bei,Wu Yue.Anti-spam model based on semi-na?ve Bayesian classification model[J].Journal of Computer Applications,2009,29(3):903-904.

[4]Wang Peng,Gao Cheng,Chen Xiaomei.Research on LDA model based on text clustering[J].Information Science, 2015,33(1):63-68.

[5]Diao Yufeng,Yang Liang,Lin Hongfei.LDA-based opinion spam discovering[J].Journal of Chinese Information Processing,2011,25(1):41-47.

[6]Chen Xiao,Huang Shuguang,Qin Li.Social network model based on micro-blog transmission[J].Journal of Computer Applications,2015,35(3):638-642.

[7]Li Dahua.Probability model and computer vision[EB/OL]. MIT Courser[2015-07-02].http://www.sigvc.org/bbs/thread-165-1-1.html.

[8]Sina mirco-blog.UCI data sites[EB/OL].(2015-03)[2015-07-02].http://www.archive.ics.uci.edu/ml.

[9]Kernighan B W,Lin S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal,1970, 49(2):291-307.

[10]Zhao Yi,He Keqing,Chen Jingliang,et al.Evolution knowledge tree for services computing domain in Wikipedia[J].Journal of Wuhan University:Natural Science Edition,2015,61 (4):331-338.

[11]Plantt J C.Sequential minimal optimization:a fast algorithm for training support vector machines,MSR-TR-98-14 [R].Microsoft Research,1998.

[12]Han Zhongming,Zhang Hui,Xie Xiaomeng.Effective sentiment classification method based on SVM for microblogging text[D].Beijing:Beijing Technology and Business University,2013.

[13]Yang Chao,Feng Shi,Wang Daling,et al.Analysis on Web public opinion orientation based on extending sentiment lexicon[J].Journal of Chinese Computer Systems,2010,31 (4):44-49.

[14]Ding Jianli,Ci Xian,Huang Jianxiong.Orientation analysis of Web reviews[J].Journal of Computer Applications,2010, 30(11):2937-2940.

[15]Wang Zhenyu,Wu Zeheng,Hu Fangtao.Words sentiment polarity calculation based on HowNet and PMI[J].Computer Engineering,2012,38(15):187-193.

[16]Li Yingle,Yu Hongtao,Liu Lixiong.Predict algorithm of micro-blog retweet scale based on SVM[J].Application Research of Computers,2013,30(9):2594-2597.

附中文參考文獻：

[2]彭希羨,朱慶華,劉璇.微博客用戶特征分析及分類研究——以“新浪微博”為例[J].情報科學,2015,33(1):69-75.

[3]惠孛,吳躍.基于不完全樸素貝葉斯分類模型的垃圾郵件分類模型[J].計算機應用,2009,29(3):903-904.

[4]王鵬,高鋮,陳曉美.基于LDA模型的文本聚類研究[J].情報科學,2015,33(1):63-68.

[5]刁宇峰,楊亮,林鴻飛.基于LDA模型的博客垃圾評論發現[J].中文信息學報,2011,25(1):41-47.

[6]陳驍,黃曙光,秦李.基于微博轉發的社交網絡模型[J].計算機應用,2015,35(3):638-642.

[10]趙一,何克清,陳荊亮,等.面向維基百科服務計算領域的演化知識樹[J].武漢大學學報:理學版,2015,61(4):331-338.

[12]韓忠明,張慧,解筱夢.基于SVM的微博文本情感傾向性識別[D].北京:北京工商大學,2013.

[13]楊超,馮時,王大玲,等.基于情感詞典擴展技術的網絡輿情傾向性分析[J].小型微型計算機系統,2010,31(4):44-49.

[14]丁建立,慈祥,黃劍雄.網絡評論傾向性分析[J].計算機應用,2010,30(11):2937-2940.

[15]王振宇,吳澤衡,胡方濤.基于HowNet和PMI的詞語情感極性計算[J].計算機工程,2012,38(15):187-193.

[16]李英樂,于洪濤,劉力雄.基于SVM的微博轉發規模預測方法[J].計算機應用研究,2013,30(9):2594-2597.

ZHAO Yi was born in 1984.He is a Ph.D.candidate at Computer School,Wuhan University,and the member of CCF.His research interests include service computing,software engineering and complex network,etc.

趙一（1984—），男，湖北荊門人，武漢大學計算機學院博士研究生，CCF會員，主要研究領域為服務計算，軟件工程，復雜網絡等。

HE Keqing was born in 1947.He is a professor at Wuhan University,and the member of CCF.His research interests include service computing,software engineering and complex network,etc.

何克清（1947—），男，湖北武漢人，博士，武漢大學教授，CCF會員，主要研究領域為服務計算，軟件工程，復雜網絡等。

LI Zhao was born in 1986.He is a lecturer at College of Computer and Information Technology,Three Gorges University.His research interests include service computing,software engineering and complex network,etc.

李昭（1986—），男，湖北宜昌人，博士，三峽大學計算機與信息技術學院講師，主要研究領域為服務計算，軟件工程，復雜網絡等。

HUANG Yiwang was born in 1978.He is an associate professor at Computer School,Wuhan University,and the member of CCF.His research interests include service computing,business process management and formal method,etc.

黃貽望（1978—），男，湖南懷化人，博士，武漢大學計算機學院副教授，CCF會員，主要研究領域為服務計算，業務流程管理，形式化方法等。

Micro Blog Evolutionary Network to Classification Method of Negative Information*

ZHAO Yi1,HE Keqing1,LI Zhao2+,HUANG Yiwang1
1.State Key Laboratory of Software Engineering,Computer School,Wuhan University,Wuhan 430072,China
2.College of Computer and Information Technology,Three Gorges University,Yichang,Hubei 443002,China
+Corresponding author:E-mail:zhaoli@ctgu.edu.cn

Aiming at the relationship of the Sina micro blogging,this paper establishes the evolving network by user's transmit blog,which classifies blog by SMO SVM(sequential minimal optimization support vector machine)algorithm,and implements the classification of malicious posts,spam,trash marketing information.The method enables users to accurately block the unwanted posts and blogger.The first step,classifying the entire Sina micro blogs based on the evolving network of transmit relationship and SVM classification algorithm;The second step,annotating the bloggers of often sending malicious advertisements by using the complex network technology;When the malicious bloggers sending message,blocking them in the network;Finally,finding out the source of spam,and discerning the blogger malicious or not,on the macro to better curb the spread of spam.The results of this paper are compared with user feedback actual situation from the UCI data set,the experimental results of machine learning classification reaches 89%.

sequential minimal optimization(SMO);support vector machine(SVM);evolutionary network;UCI data set;negative information

A

：TP393.092

10.3778/j.issn.1673-9418.1509090

*The National Basic Research Program of China under Grant No.2014CB340401(國家重點基礎研究發展計劃(973計劃)).

Received 2015-08,Accepted 2015-10.

CNKI網絡優先出版:2015-10-30,http://www.cnki.net/kcms/detail/11.5602.TP.20151030.1618.004.html

摘 要：針對Sina微博博文的轉發關系，建立起用戶轉發博文之間的演化網絡，從而利用SMO SVM（sequential minimal optimization support vector machine）分類算法對博文進行分類，篩選出惡意博文、垃圾廣告、垃圾營銷信息，使用戶能夠精確地屏蔽不想要的博文和博主。第一步基于微博轉發關系的演化網絡和SVM分類算法對整個Sina微博進行分類；第二步利用復雜網絡等技術對經常發送惡意廣告的博主進行標注，從而在網絡中對他們進行屏蔽；最后找出垃圾信息的來源以及分辨出博主是不是惡意轉發者，在宏觀上能更好地遏制垃圾信息的傳播。與用戶從UCI數據集中實際反饋情況進行比較，實驗結果表明，機器學習分類的實驗結果吻合度達到89%。