黃林昊, 郭昆

(1.福建廣播電視大學 電子信息與計算機系， 福建 福州 350012; 2.福州大學 數學與計算機科學學院， 福建 福州 350116)

基于并行決策樹的微博互動數預測

黃林昊1, 郭昆2

(1.福建廣播電視大學 電子信息與計算機系， 福建 福州 350012; 2.福州大學 數學與計算機科學學院， 福建 福州 350116)

社交網絡的快速發(fā)展，微博成為主要的社交媒體平臺，針對如何預測微博文本的未來互動數，對微博進行有效的分發(fā)控制的問題，提出一種基于并行決策樹的微博互動數所屬級數預測的方法。首先，對用戶以往發(fā)表的微博進行用戶特征和微博文本特征的處理；然后，使用并行決策樹分類算法對訓練數據進行分類模型的構建；最后使用得到的分類模型對新微博文本的互動數所屬級數進行分類預測。通過對比算法的實驗，驗證了所提方法具有較高的分類精度和較好的可擴展性，能夠對微博所屬級數進行有效的分類預測。

微博; 互動數; 并行; 決策樹; 預測

近年來，隨著互聯網技術、移動端技術的快速發(fā)展，特別是移動網絡為代表的移動互聯網技術的迅速發(fā)展，根據第36次《中國互聯網絡發(fā)展狀況統(tǒng)計報告》的報告，截止2015年6月，中國網民的規(guī)模已經達到了6.68億，其中互聯網的普及率達到48.8%，這個發(fā)展速度還在不斷增加，其中手機網民規(guī)模達到了5.94億，是互聯網網民的主力軍。這也帶動了社交網絡的迅速發(fā)展，而目前對于社交網絡的研究主要集中在個性化內容推薦[1]、社群挖掘[2]、熱點話題檢測[3]等方面。

微博作為社交網絡中一個主要的社交媒體平臺，可幫助用戶發(fā)布的公開內容進行快速傳播互動，它以較短的文字消息，在較短的時間內通過用戶的傳播達到信息的快速傳播、共享，用以提高用戶和內容的影響力，受到很多人的熱愛。以國內主要的微博平臺——新浪微博為例，目前已經超過5億個注冊用戶，截止2015年9月，其微博的月活躍用戶人數已經達到2.22億，與2014年9月同比增長33%，而日活躍用戶達到了1億，比2014年同期增長30%。微博平臺的發(fā)展完善，使其使用率不斷提高，用戶量持續(xù)增長，每天產生數以億計的微博文本數量。如何對這些微博進行快速的分析挖掘[4]，找到受眾認可度高的微博文本，對這些文本進行有效的分發(fā)控制，以提高受眾認可度高的微博文本的曝光量和內容傳播的互動量，具有重要的研究意義。

微博用一種短文本的形式表達用戶的狀態(tài)或心情，這些微博文本會被其他用戶進行轉發(fā)分享提高其傳播量，同時用戶也可以對微博進行評論、點贊等行為操作。一條微博若被用戶大量的轉發(fā)或評論或點贊等操作，可見其是一條比較有意義、有價值、受眾認可度高的微博文本。若能提前發(fā)現這些互動數即微博轉發(fā)數、微博評論數和微博點贊數高的微博文本，進行有效的分發(fā)控制，這對提高這些微博文本的曝光量具有重要的意義。

近年來，國內外專家、學者也對社交網絡中的微博文本的挖掘分析進行了廣泛的研究。Boyd等人對Twitter即類似國內的新浪微博的一個社交平臺進行研究，研究人們對Twitter上的Retweet操作即轉發(fā)操作，研究其Retweet的動機，并對Retweet的文本內容進行主題傾向等方面的研究[5-6]。Zan 等人選取用戶名、關注人數、Twitter包含的單詞個數等特征，然后基于一種概率的協同過濾模型Matchbox[7]，對用戶轉發(fā)Twitter的行為進行預測[8]，該方法簡單地將用戶特征和微博特征抽取出來進行預測，沒有考慮用戶興趣和微博內容之間的關系。楊子等對Twitter中用戶轉發(fā)行為提取了22個影響因素，使用因子圖模型進行了轉發(fā)行為的預測，獲得了比較高的精度，但其對特征的量化處理過程比較簡單，導致信息傳播路徑預測的精度比較低[9]。Liben-Nowell等人對真實的社會網絡中的傳播特征和一些相關的問題進行了比較全面的研究，明確指出想要精確地預測信息的傳播路徑是比較困難的，用簡單的模型進行預測得到的結果與真實的結果相差比較大[10]。Fan等人通過對新浪微博的拓撲結構和信息擴散情況進行研究，指出新浪微博具有小世界和無標度特性的拓撲結構，其中熱門事件的擴散拓撲結構呈現星形或兩級的結構[11]。Webberley等人對微博中的傳播擴散進行研究，指出微博的信息傳播和擴散主要是依靠用戶轉發(fā)產生的，且一條微博的轉發(fā)鏈具有一定的長度，隨著微博的一次次轉發(fā)，其被轉發(fā)的概率隨著微博鏈的長度的增加而減小[12]。謝婧等人研究微博用戶中的轉發(fā)人群和未轉發(fā)人群的微博內容、粉絲數、關注數等特征，基于貝葉斯預測模型提出一種新的預測用戶轉發(fā)行為的方法[13]?？餂_等人根據貝葉斯個性化排序優(yōu)化標準和分解機制，提出了一種對微博轉發(fā)者進行預測的方法[14]。

目前研究者對國外的Twitter研究比較多，而對國內的微博研究相對較少，且更多的是對微博文本被轉發(fā)的行為進行預測研究，對于微博本身的互動數的研究相對較少。本研究以國內的新浪微博為例，利用微博發(fā)表用戶的特征和微博文本自身的特征，提出一種基于決策樹的微博互動數預測方法。同時為了適應海量微博文本數據的挖掘分析，利用Spark框架將方法進行并行化處理，以提高方法處理海量微博的能力。在真實的新浪微博數據上和對比不同算法進行實驗分析，驗證所提出方法的有效性和可擴展性。

1 相關理論基礎

1.1 新浪微博互動行為

新浪微博是國內主要的用戶進行交流、分享的社交媒體平臺，，受到大眾的喜愛。新浪微博文本以短信息的形式進行傳播，其要求一條博文長度不能超過140個字符，用戶可以對微博進行轉發(fā)、評論、點贊的操作。新浪微博文本的價值信息可以通過其他用戶對該微博文本的評價情況進行體現，而對微博文本的評價方面主要可以從微博的轉發(fā)數、評論數和點贊數3方面即微博的互動數進行體現。一條原創(chuàng)的微博，通過其轉發(fā)、評論、點贊等互動行為能夠體現其他用戶對該原創(chuàng)微博內容的興趣程度。

微博轉發(fā)，用戶通過點擊轉發(fā)按鈕即可實現對原創(chuàng)微博的轉發(fā)。微博轉發(fā)行為是微博能夠快速傳播的主要原因，轉發(fā)時用戶可以對微博加以評論，形成新的微博文本，如圖1所示。同時轉發(fā)會使該微博的轉發(fā)數進行累加，這樣微博被一個用戶接一個用戶地轉發(fā)，形成一條轉發(fā)微博鏈，微博格式如：//@username:微博內容//@username:微博內容。

圖1 微博轉發(fā)Fig.1 Micro-blog forwarding

微博評論，用戶可以直接在某條微博文本的下方進行評論，表達自己對該微博文本的認識。同時被評論微博的評論數會相應地累加。

微博點贊，用戶可以直接點擊微博的“贊”的按鈕，即可對該微博進行點贊，以表達用戶對該微博的認可度。同時被點贊的微博的點贊數會相應地累加。

1.2 Spark分布式并行計算

Spark是Apache的一個開源項目，是近年來發(fā)展較快的分布式并行數據處理框架，是伯克利大學在2012年提出的一種基于內存的分布式計算框架[15]，它允許重復地使用加載到內存中的數據，并且可以將計算的中間結果持久地保存在內存中[16]，從而減少磁盤IO操作，提高數據運算效率。Spark采用了一種新的數據抽象模型即彈性分布式數據集(resilient distributed dataset，RDD)，使其能夠在多次迭代計算過程中重復利用內存數據，這也是Spark的核心，是一個不可變的帶分區(qū)的記錄集合。RDD的基本操作包括Transformation和Action[17]，其中Transformation是得到一個新的RDD，可以從數據源或是RDD中生成，而Action是得到一個結果。Transformation是采用懶策略，只有當Action提交時才執(zhí)行相應計算。

Spark廣泛應用在計算量大、效率要求高的場景當中，通常在互聯網廣告、報表、推薦系統(tǒng)等業(yè)務中做應用分析、效果分析與優(yōu)化。例如騰訊大數據精準推薦利用Spark快速迭代實現實時并行高維算法；淘寶技術團隊將Spark應用于淘寶推薦相關算法，還利用GraphX解決生產問題。

1.3 決策樹分類

決策樹分類方法是一個比較經典的分類算法，它通過使用樹的結構來記錄數據分類的規(guī)則，即每個樹的葉節(jié)點代表某個條件下的一個數據記錄集。根據數據屬性字段的不同取值建立樹的分支，然后在每個分支子集上重復建立下層的分支節(jié)點，最終生成一顆樹。對生成的原始的決策樹進行修剪，可以很快地得到具有商業(yè)價值的信息，以供決策者決策時參考。決策樹分類一般分為兩個步驟[18]：(1)使用訓練數據集合進行學習，形成決策樹分類模型的構建；(2)利用已經得到的分類模型對未知的數據進行分類。

決策樹分類最重要的是選擇屬性進行樹的分裂。其中引用率較高的決策樹算法ID3算法使用信息增益來進行屬性的劃分。信息增益是基于信息熵進行屬性選擇的，一棵決策樹對一個記錄數據進行判斷所需要的信息熵如式(1)所示：

(1)

其中D是用于存放數據記錄的，pi是數據記錄D中任意記錄屬于Ci的非零概率，用|Ci|/|D|進行估計[19]。而信息增益是原來的信息需求與新的信息需求(對屬性A進行劃分之后)之間的差，如式(2)所示：

(2)

信息增益的決策樹使用信息增益最大的屬性作為樹節(jié)點的劃分，即最小化InfoA(D)。

2 互動數預測

2.1 數據描述與特征提取

數據選取天池大數據科研平臺(https://tianchi.shuju.aliyun.com)提供的新浪微博文本數據，包含了2015-02-01～2015-07-31部分用戶發(fā)表的微博文本數據，共計1 626 750條微博文本。其中微博數據包含的內容如表1所示。微博文本互動數預測是預測一條微博發(fā)表1周之后，被用戶轉發(fā)、評論、點贊的數量，同時對于數量的預測關注的是這個數量所屬的一個數量級，高級別的互動數受到大眾認可度高，具有較高的價值。因此將微博的互動數量分為5級，分別是第1級互動數最少，幾乎沒有互動數，即互動數為0到5的微博；第2級互動數較少，為6到10的微博；第3級互動數一般為11到50的微博；第4級的互動數較高，為51到100；第5級的互動數最高，具有最高的大眾認可度，即互動數大于100的微博。

表1 微博數據格式

由于數據中只有微博文本的發(fā)表時間等信息，其所具有的特征信息比較稀少，難以直接進行有效的分析，需要提取用戶發(fā)表的微博文本背后的一些特征信息，主要分為用戶特征和微博特征。用戶特征指的是用戶發(fā)表微博所得到的互動數的特點，而微博特征指的是微博文本本身的特點使其互動數發(fā)生變化的特性。

用戶發(fā)表的微博特性，主要關注于用戶自身是否是一個比較受歡迎，被大量用戶關注的用戶，即其具有的粉絲數量等，可以從用戶以往發(fā)表的微博的互動數情況進行側面反映。本研究提取了用戶的11個特性如表2所示。

表2 用戶特征

微博文本的特征，主要是通過識別微博文本本身的特性，判斷其是否是一條受大眾認可喜歡的微博文本，對以往的微博文本進行挖掘提取，判斷微博是否是原創(chuàng)微博，微博中“@”符號的個數，微博中是否有網頁鏈接等特點。本研究提取微博文本7個主要特征，如表3所示。

表3 微博文本特征

2.2 流程設計

基于Spark框架對所設計的微博互動數預測流程如下：

(1)對原始數據進行采集劃分，得到訓練數據和測試數據兩個數據集；

(2)對數據進行特征的提取轉化等預處理操作；

(3)使用基于Spark的分類算法對訓練數據集進行訓練，得到分類模型；

(4)使用得到的分類模型對測試集數據進行分類以預測其未來的互動數所屬級數；

(5)對分類得到的結果進行驗證，得到分類模型的準確度，具體流程如圖2所示。

2.3 評估指標

對分類模型的準確性與有效性指標的判定可以通過其混淆矩陣進行計算得到[20]。通過混淆矩陣(表4)可以計算分類模型的正確率如公式3所示，正確率越高代表模型分類結果越好。

圖2 決策樹訓練測試流程Fig.2 Parallel decision tree training testing process

表4 分類結果混淆矩陣

(3)

由于對微博文本的互動數的預測是預測其所屬的級數，通過不同的級數可看出該微博的一個受認可度情況，對不同的微博文本預測結果更看重互動數級數高的微博能否被分類正確。對微博互動數預測結果根據不同的級數賦予不同的權重值如表5所示，最后計算所有微博的分類結果的加權分數，分數越高代表分類結果越好，如公式4所示。

表5 權重系數

(4)

3 實驗結果分析

3.1 精度分析

由于微博文本的時效性特征，對微博文本的互動數預測，應從距離微博文本較近的時間段內的數據進行用戶特征的提取，所以選取2015年4月到6月共3個月的微博文本數據作為訓練集，用以構建分類模型，用2015年7月份的數據作為測試數據，以驗證分類模型的準確度。

通過與基于Spark的決策樹(decision trees，DT)、基于Spark的樸素貝葉斯(naive Bayes，NB)和基于Spark的邏輯回歸(logistic regression，LG)在訓練數據集上進行構建分類模型，在測試集上驗證分類模型得到的結果如表6所示。

表6 實驗結果

圖3 互動數平均實驗結果Fig.3 The average of interaction experimental result

從實驗結果可以看出，從微博文本中提出的用戶特征和微博文本特征，能夠使分類算法有效地對新的微博文本進行預測分類，3個算法均有較高的正確率，但本研究所提出的基于決策樹的分類結果具有最高的正確率。同時通過對不同的微博文本級數的分類，本研究所提出的決策樹方法分類的結果的Score得分最高，能夠對微博互動數級數高的文本進行正確的分類，而另外兩個分類算法雖然有較高的正確率，但在級數高的微博文本中未能有效地識別，導致其Score得分不高。

3.2 擴展性實驗

為進一步驗證算法的可擴展性能力，通過使用不同的集群規(guī)模對所提出的方法進行擴展性實驗，計算算法運行時的加速比，公式如5所示：

(5)

其中Ts表示單機版算法運行所消耗的時間，Tp表示并行版算法運行所消耗的時間，p表示并行的節(jié)點個數。算法的加速比結果如圖4所示。

圖4 不同集群規(guī)模加速比Fig.4 Different clusters scale acceleration ratios

從圖4不同集群規(guī)模加速比的實驗結果可以發(fā)現，隨著集群規(guī)模的增加，算法運行的速度加快，加速比增加。當集群規(guī)模從1增加到4時，加速比增長迅速，因為算法將數據分散到各個節(jié)點進行運行，進而減少了算法處理所需要的時間，大大提高了整體的運行速度。但隨著集群規(guī)模的不斷增加，加速比的增長速度變慢，這是因為隨著集群規(guī)模的增加，算法需要耗費更多的時間在數據傳輸和調度上，從而導致了加速比增長緩慢?？梢娝岢龅幕赟park的并行決策樹方法具有較好的可擴展性能力。

4 結語

新浪微博作為國內主要的社交媒體平臺，如何對一條微博文本的互動數進行有效的預測，進而根據互動數級數對微博文本進行有效的分發(fā)控制管理具有非常重要的意義。本研究首先通過對用戶發(fā)表的微博進行有效的用戶特征和微博文本自身特征的提取。然后基于Spark分布式框架使用決策樹分類算法對數據進行分類模型的構建。最后在新的微博文本上使用分類模型進行分類以驗證分類模型的有效性。通過與并行的樸素貝葉斯和邏輯回歸分類算法的對比實驗，驗證所提出的基于決策樹分類算法的微博互動數預測的有效性與可擴展性能力，能夠對微博文本未來的互動數級數進行正確的分類。接下來，將對微博的文本內容進行內容挖掘分析研究，提取更多有價值的特征，以進一步提高互動數級數高的微博文本的分類正確率。

[1] 王潔,湯小春.基于社區(qū)網絡內容的個性化推薦算法研究[J].計算機應用研究,2011,28(4):1248-1250.

[2] Yang B, Cheung W, Liu J. Community mining from signed social networks[J].IEEE Transactions on Knowledge and Data Engineering,2007,19(10):1333-1348.

[3] Phuvipadawat S,Murata T.Breaking news detection and tracking in Twitter[C]//2010IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT),Aug.31-Sept.3,2010,Toronto,Ontario,Canada.Washington:IEEE Computer Society,2010,3:120-123.

[4] 曹玖新,吳江林,石偉,等.新浪微博網信息傳播分析與預測[J].計算機學報,2014,37(4):779-790.

[5] Boyd D, Golder S, Lotan G. Tweet, tweet, retweet: Conversational aspects of retweeting on twitter[C]//43rd Hawaii International Conference on System Sciences (HICSS),Koloa, Kauai,Havaii.Jan 5-8,2010.Washington：IEEE,2010:1-10.

[6] Kwak H, Lee C, Park H, et al.What is Twitter, a social network or a news media?[C]//Proceedings of the 19th International Conference on World Wide Web. Apr 26-30,2010, Raleigh,North Carolina,USA.New York:ACM,2010:591-600.

[7] Stern D H, Herbrich R, Graepel T. Matchbox: large scale online Bayesian recommendations[C]//Proceedings of the 18th International Conference on World Wide Web. Apr 20-24,2009, Madrid,Spain. New York:ACM,2009:111-120.

[8] Zaman T R, Herbrich R, Van Gael J, et al. Predicting information spreading in twitter[J]. Computational Social Science and the Wisdom of Crowds. Citeseer,2010,104(45):17599-17601.

[9] Yang Z,Guo J,Cai K, et al. Understanding retweeting behaviors in social networks[C]//Proceedings of the 19th ACM International Conference on Information and Knowledge Management. Oct 26-30,2010, Toronto,ON,Canada. New York: ACM,2010:1633-1636.

[10] Liben-Nowell D, Kleinberg J. Tracing information flow on a global scale using Internet chain-letter data[J].Proceedings of the National Academy of Sciences,2008,105(12):4633-4638.

[11] Fan P, Li P, Jiang Z, et al. Measurement and analysis of topology and information propagation on Sina-Microblog[C]//2011 IEEE International Conference on Intelligence and Security Informatics(ISI), July 9-12,2011, Beijing China. Washington:IEEE,2011:396-401.

[12] Webberley W,Allen S,Whitaker R.Retweeting: A study of message-forwarding in twitter[C]//2011 Workshop on Mobile and Online Social Networks (MOSN), Sept 8,2011, Milan,Italy. Washington:IEEE,2011:13-18.

[13] 謝婧,劉功申,蘇波,等.社交網絡中的用戶轉發(fā)行為預測[J].上海交通大學學報,2013,47(4):585-588.

[14] 匡沖,劉知遠,孫茂松.微博轉發(fā)者的個性化排序[J].山東大學學報(理學版),2014,49(11):31-36.

[15] 嚴玉良,董一鴻,何賢芒,等.FSMBUS:一種基于Spark 的大規(guī)模頻繁子圖挖掘算法[J].計算機研究與發(fā)展,2015,52(8):1768-1783.

[16] 丁圣勇,閔世武,樊勇兵.基于Spark平臺的NetFlow流量分析系統(tǒng)[J].電信科學,2014,30(10):48-51.

[17] 牛海玲,魯慧民,劉振杰.基于Spark 的Apriori算法的改進[J].東北師大學報(自然科學版),2016,48(1):84-89.

[18] 徐鵬,林森.基于 C4.5 決策樹的流量分類方法[J].軟件學報,2009,20(10):2692-2704.

[19] 韓家煒,坎伯.數據挖掘:概念與技術[M].北京:機械工業(yè)出版社,2012：213-222.

[20] 陳羽中,郭松榮,陳宏,等.基于并行分類算法的電力客戶欠費預警[J].計算機應用,2016,36(6):1757-1761.

(特約編輯：黃家瑜)

Interaction number prediction of micro-blog based on parallel decision tree

Huang Linhao1, Guo Kun2

(1. Electronic Information and Computer Department, Fujian Radio and TV University, Fuzhou 350012, China； 2. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China)

To predict the future interaction number of micro-blog texts to implement effective distribution control of micro-blogs, a method of forecasting the series number of micro-blog interaction numbers based on parallel decision tree was proposed. Firstly, the user characteristics and micro-blog text features of the user’s previous micro-blog were processed. Then, a classification model of the training data was constructed via a parallel decision tree classification algorithm. Finally, the series number of the interaction number of new micro-blog texts was classified via the classification model. The experimental results show that the proposed method has high classification accuracy and good scalability and can effectively forecast micro-blog series.

micro-blog; interaction number; parallel decision tree; forecast

10.3969/j.issn.1672-4348.2017.03.019

2017-03-22

國家自然科學基金資助項目(61300104)；福建省教育廳資助項目(JA14349)

黃林昊(1979-),男，福建福州人，講師，碩士，研究方向：移動應用、信息安全與數據挖掘。

TP 311.5

A

1672-4348(2017)03-0294-07