基于Hadoop的微群活躍用戶查詢策略實現

摘要：針對在大規模微博用戶群中尋找并計算出最活躍的幾個用戶的活躍度非常耗時的問題，利用Hadoop系統框架的HDFS將數據分塊存儲的特性和整體數據分割后局部篩選最優可體現整體最優的特性，提出了一種結合MapReduce編程技術和堆排序技術的高效查詢計算策略。并通過仿真實驗，對該策略進行了模擬實現，實驗結果證明了該策略可高效的計算出微群中最活躍用戶的活躍度。

關鍵詞：Hadoop；堆排序；微群；用戶活躍度；MapReduce

中圖分類號：TP31 文獻標識碼：A 文章編號：1674-7712 （2015） 02-0000-03

微博就是微型博客（Micro-Blogging），是基于有線和無線互聯網終端發布精短信息供其他網友共享的即時信息網絡[1]。微博以能夠實時和方便的分享信息的特性，吸引了很多的用戶。據調查發現，國外的微博Twitter在全球多個國家已用了近2億的用戶。根據中國互聯網絡信息中心（CNNIC）第34次統計報告，截至2014年6月，我國微博客用戶規模為2.75億。微博龐大的用戶數量以及便捷迅速的消息發布與傳遞方式使其成為了當前信息傳播及輿論擴散的重要平臺，造就了眾多影響力巨大的用戶。微博中具有影響力的用戶值得重點關注，這部分用戶在信息傳播、輿論形成中起到關鍵性的作用。解決微博網絡中的影響力最大化問題，對于市場營銷、輿論管控等方面具有重要意義，對于微博網絡傳播的研究已成為當前研究的熱點領域。目前有很多關于這方面的研究成果，如基于行為預測的微博網絡信息傳播建模[2]，基于微博的企業網絡輿情社會影響力評價研究[3]和基于微博網絡的影響力最大化算法等相關研究[4]。這些文獻提及的算法模型，通常都會涉及到一個稱為微群中最活躍用戶的活躍度[5]的計算。隨微博用戶數量的增多，最活躍用戶的活躍度的計算也會變得非常耗時。這對這個問題，本文提出了一種高效的查詢計算策略MHeap，用來對其進行較快速的計算。MHeap利用Hadoop系統框架的分布式文件存儲系統HDFS把文件數據分塊存儲的特性和所有的局部最優可體現整體數據集最優的特性，是結合MapReduce編程技術和數據結構中的建堆排序技術而形成的一種高效查詢策略。

一、背景

（一） Hadoop

Hadoop是Apache下的一個頂級開源項目，是模仿Google核心技術而成的一個開源的分布式計算機系統框架。Hadoop可以運行在由成千上萬廉價的PC搭建的集群上，通過分布式的計算模型和存儲模型來處理海量的數據集[6，7]。Hadoop有很多優良特性，如高容錯性、強擴展性等眾多優點，是處理海量數據集的首選工具。MapReduce分布式編程框架和分布式文件系統HDFS是其最主要的組建，圖1和圖2分別展示了這兩個組建的架構圖。

HDFS是一種分布式文件系統，采用master/slaver的主從式設計架構。實際工作中master節點把要存儲的大數據集分割為很多較小的數據塊（默認為32M），按照一定的分配策略把數據塊分配到slaver節點上存儲。MapReduce引擎的根源由JobTracker和TaskTracker組成：JobTracker整個系統分配任務的核心，負責管理調度所有作業，TaskTracker負責執行用戶定義的Map任務和Reduce任務，執行過程中需要向JobTracker發送心跳報告任務的執行狀態，以使JobTracker收集作業執行的整體情況[8]。

（二）堆排序

堆是一種極其有用的數據結構，它的定義為具有n個元素的序列 ，對于列表中位置為i（編號從1開始）處的記錄的關鍵字 滿足關系式（1）或（2）。其中，每個結點關鍵字都不小于其子孫結點關鍵字的堆稱為大頂堆；而每個結點的關鍵字都不大于其子孫結點關鍵字的堆稱為小頂堆。

（1）

（2）

根據選擇排序的思想，利用堆的結構特來完成對序列的排序，稱之為堆排序。堆排序概括來說分為兩個步驟，第一步把無序的序列構建一個大頂堆或小頂堆；第二步根據構建堆按照一定策略輸出為一個有序的序列。建堆的方法為，首先把數據元素放入某數組A[n+1]中（A[0]不存儲數據元素，方便建堆），并將數組A視為一顆尚未滿足堆性質的完全二叉樹；此時節點數為n的二叉樹A中， 是完全二叉樹的葉子節點，因此 是 個單節點堆。然后從節點 到1自右向左，自下向上反向層序遍歷二叉樹的所有非葉子結點并從小到大的各棵子樹通過篩運算使之成為堆。7，5，8，2，6構建堆的過程如圖3。輸出堆的方法，在輸出堆頂的最大（最小）值后，使得剩余的n-1個記錄的序列重新調整為一個堆，于是又得到次大（或次小）值……如此反復執行，直到所有記錄為一個有序序列[9，10]。

二、MHeapSort算法

MHeapSort算法核心思想為，首先把大數據集S分割為一個個小的數據集 。然后，從數據 中篩選出最優的前m個最優數據，再歸并 選出的 個數據到新的數據集N。最后，從數據集N中篩選出最優的前m個數據，基本上就是數據集S中最優的前m個數據。MHeapSort是一種結合Hadoop的MapReduce框架技術和小頂堆排序技術的一種在微群中尋找最活躍用戶的策略方法。首先，使用Map任務對用戶評論、發表和轉發微博數進行統計。然后，使用Reduce任務根據統計數據的數據數目進行建堆排序，并把堆中的數據進行輸出。最后，把Reduce輸出數據文件歸并，輸出數據建立的堆中數據。

（一）算法設計思路

算法設計主要利用了Hadoopp框架把數據文件分割為一個個數據塊的特點，把大的數據集劃分為一個個小的數據集；對數據塊中數據進行建堆，進行局部最優篩選的特點。算法總體分為兩個MapReduce任務，第一個MapReuce任務主要完成指定時間段內數據的過來，以及統計用戶評論、轉發和發表微博數量，最后根據該數值和用戶ID構建規模為m的小頂堆，并輸出堆中的數據作為下一MapReduce任務的數據輸入。第二個MapReduce任務主要完成歸并最優數據，以及統計用戶評論、轉發和發表微博的數量，最后根據該數值和用戶ID構建規模為m的小頂堆，輸出數據即最活躍的用戶ID和他們的轉發，發表和評論微博的數量。

（二）算法流程圖

圖4 算法流程框架圖

根據圖4的描述算法的詳細處理流程：

（1）獲取原始數據集S，數據存儲格式文本中記錄行，記錄形式如：用戶ID 用戶評論 評論時間。

（2）將待處理的數據集S劃分為等大小的r份（默認為32M），分割后的數據集Si被發送到DataNodei上。

（3）Haddoop的MapReduce框架，通過JobTracker任務通知TaskTracker任務，在DataNode節點上啟動Map任務，把評論時間不在指定時間段內的數據過濾掉，然后把用戶ID和用戶評論分別作為key和value輸出。

（4）Map任務結束后，JobTracker任務通知TaskTracker任務，在DataNode節點上啟動Reduce任務，并不對Map輸出的數據進行排序處理，只是統計Key（用戶ID）對應的value的個數（評論數）count并存入到自定義對象UserWritable里面（UserWritable對象只有兩個屬性，id和count）。然后把該對象存入到大小為11的數組中（為了方便建堆，數組0對應的下標是不存數據的），數組存滿時按照user對象的count值對數組進行建小頂堆。后面再有數據產生時，只是跟堆頂數據對象的count值進行比較大小，若大于堆頂對象的count值，則把堆頂對象替換為該對象并調整為小頂堆，否則不進行處理。最后把堆中的對象的id和count分別作為Reduce的key和value輸出。

（5）獲取上階段MapReduce任務的輸出結果數據，通過MapReduce框架把數據切割為等同大小的數據塊。數據塊被分發到各個DataNode節點上，JobTracker任務通知TaskTracker任務，在DataNode節點上啟動Map任務，把用戶ID和用戶評論數分別作為key和value輸出。

（6）Map任務結束后，Reduce任務雷同步驟（4）進行建立一個小頂堆，把小頂堆中對象的id和count分別作為Reduce的key和value輸出。

（7）獲得的數據即最活躍的用戶。

三、實驗仿真

（一）數據集描述

為驗證本文提出的查詢計算策略MHeap的有效性，使用新浪微博中的微群數據對MHeap進行實驗。數據的獲取方式：首先使用網絡爬蟲程序采集一個微群中所有用戶成員的ID，然后根據新浪微博平臺提供的API接口獲取用戶ID相應的數據信息：用戶ID對應的用戶基本信息，如用戶名稱、關注用戶數、用戶評論數、發布微博數、轉發微博數等；用戶的轉發及評論信息，包括被轉發的消息ID，被轉發及評論的用戶ID僅限制在收集該微群內的用戶。采集到的數據集中包含了8239個用戶ID基本信息和該用戶群中大量的用戶評論，發表和轉發微博等數據信息。

（二）設計實驗

實驗實施在由5結點搭建的Hadoop集群上。PC機硬件環境：Cpu Intel? Core? i3-2100 3.10GHz，內存4G，硬盤為500G；軟件環境：每個節點均裝載CentOS Linux6.3操作系統，Hadoop版本為0.20.2，Java開發工具包為JDK1.6_0_27版本，程序開發工具為MyEclipse10.0，算法全部由Java語言實現。

首先設計實驗，在不同Hadoop集群規模下，分別運行了MHeap程序，實驗運行結果如下圖5。然后設計實驗，用一個串行處理的程序計算最活躍用戶的活躍度，運行結果如6。該串行程序核心處理步驟：首現根據用戶ID對原始數據集排序，對排序數據逐個統計用戶評論、轉發和發表微博數。實驗結果如下：

圖5顯示了隨著集群規模的擴大，算法的執行效率逐步提升，顯示了算法的良好擴展性。圖6顯示了兩種計算策略的計算結果（前10個最活躍用戶的活躍度）一致，顯示了算法有較高的準確率。串行處理時間 相較于三節點下的MHeap處理時間稍長，顯示了MHeap有較高的執行效率。

通過以上實驗分析，可以看出MHeap算法具有良好的擴展性，在保證準確率的前提下具備較高的執行效率。

四、結束語

為了高效獲取微群中最活躍用戶及其活躍度，本文使用數據結構中的建堆排序的方法結合Hadoop系統框架，提出了MHeap算法。通過實驗仿真對算法進行了模擬驗證。實驗結果表明MHeap在集群上具有良好的擴展性，并且在保證較高準確率的前提下具有較高效率。由此證明了該策略可高效的計算出微群中最活躍用戶的活躍度。本研究也為以后的微博節點影響力研究奠定了基礎。

參考文獻：

[1]吳凱.基于微博的信息傳播建模與節點影響力研究[J].解放軍信息工程大學信息技術研究所，2013.

[2]吳凱，季新生，劉彩霞.基于行為預測的微博網絡信息傳播建模[J].計算機應用研究，2013（06）.

[3]肖麗妍，齊佳音.基于微博的企業網絡輿情社會影響力評價研究[J].情報雜志，2013（05）.

[4]吳凱，季新生，劉彩霞.基于微博網絡的影響力最大化算法[J].計算機應用研究，2013（08）.

[5]張鑫.深入云計算Hadoop源碼分析[M].北京：中國鐵道出版社，2013（06）.

[6]National Institute of Standards and Technology，Valiated FIPS 140-1 and FIPS 140-2 Cryptographic Modules，2011.

[7]郝樹魁.Hadoop HDFS和MapReduce架構淺析[J].郵電設計技術，2012（07）.

[8]朱明方，吳及.數據結構與算法[M].北京：清華大學出版社，2010（03）.

[9]侯風巍.數據結構要點精析[M].北京：航空大學出版社，2009（03）.

[10]National Institute of Standards and Technology，Valiated FIPS 140-1 and FIPS 140-2 Cryptographic Modules，2011.

[作者簡介]黃琴琴（1987-），女，碩士，主要從事社會計算與云計算方向的研究；安俊秀（1970-），女，教授，碩士，中國計算機學會高級會員，在科研工作方面，一直從事云計算、信息智能搜索與處理、社會計算、并行與分布式軟件研究工作。