基于MapReduce框架的一種并行大數(shù)據(jù)算法的研究

摘? 要：為了在社交媒體數(shù)據(jù)中找出相應內容，可以通過大數(shù)據(jù)挖掘的算法對社交媒體數(shù)據(jù)進行處理。文章提出了一種處理Twitter數(shù)據(jù)挖掘的大數(shù)據(jù)算法，為保證可擴展性，基于MapReduce框架提出并行數(shù)據(jù)挖掘的大數(shù)據(jù)算法。通過實驗證明了該算法是高效的，在計算上，盡管數(shù)據(jù)集大小增加，執(zhí)行速度仍然可以顯著增加，并且加速比隨著數(shù)據(jù)集大小的增加和數(shù)據(jù)節(jié)點數(shù)量的增加而增大。

關鍵詞：社會媒體;數(shù)據(jù)挖掘;大數(shù)據(jù)算法;推特數(shù)據(jù);MapReduce

中圖分類號：TP311 文獻標識碼：A 文章編號：2096-4706（2021）18-0031-04

Abstract： In order to find out the corresponding content in the social media data， the social media data can be processed through the algorithm of big data mining. This paper proposes a big data algorithm for Twitter data mining. In order to ensure the scalability， we propose a parallel big data algorithm based on MapReduce framework. Experimental results show that the algorithm is efficient. Although the size of the data set increases， the execution speed can still significantly increase， and the speedup ratio increases with the increase of the size of the data set and the number of data nodes.

Keywords： social media; data mining; big data algorithm; twitter data; MapReduce

0? 引? 言

最近的一些研究表明，在社交媒體上表達的輿論可能與各種社會問題相關。為了找出在社交媒體數(shù)據(jù)中實際發(fā)現(xiàn)的內容，通過數(shù)據(jù)挖掘可以處理大量數(shù)據(jù)，稱為大數(shù)據(jù)算法[1，2]。本文中提出了一個處理Twitter數(shù)據(jù)挖掘的大數(shù)據(jù)算法。此外，為了保證可擴展性，采用Map Reduce框架來并行化所提出的算法。在過去十年中，隨著Web 2.0技術和通信工程的快速發(fā)展，社交媒體的普及和擴展已經(jīng)相當驚人[3]。社交媒體產(chǎn)生的大量數(shù)據(jù)有可能為市場和消費者行為提供一些新見解。這同樣適用于政治、環(huán)境、娛樂業(yè)、股票市場等其他社會學問題。數(shù)據(jù)挖掘的關鍵功能是從數(shù)據(jù)中提取知識，而社交媒體就像一個廣闊的未曾觸動過的而充滿價值的數(shù)據(jù)土地，在這塊土地上使用數(shù)據(jù)挖掘技術有一個明顯的動機，例如，作為社交媒體的典型例子，Twitter是一個微博應用程序，允許感興趣的用戶對其他用戶的想法或生活中的某些事件實時跟蹤和評論。作為最受歡迎的社交媒體之一，每天有數(shù)百萬用戶發(fā)布超過1.4億條推文。這種情況意味著Twitter數(shù)據(jù)是一種把有價值的數(shù)據(jù)作為一種集體知識的語料庫，最近引起了各個領域的研究者的廣泛關注。

在數(shù)據(jù)挖掘領域，已經(jīng)有一些優(yōu)秀的作品通過不同的興趣點對Twitter數(shù)據(jù)進行了分析。這包括預測票房收入和工業(yè)平均指數(shù)的走勢等[4-7]。他們的研究表明，嵌入在社交媒體中的數(shù)據(jù)有很大的力量，確實可以用來做出準確的預測。與人工專家系統(tǒng)不同，來自社交媒體的龐大數(shù)量的信息代表了挖掘數(shù)據(jù)的極好機會，以提取具有特定結果預測的知識。這種社交媒體數(shù)據(jù)可以用來建立模型，以匯總來自集體社區(qū)的意見，并獲得一些有用的針對他們的行為的洞察，這可以用來預測未來的趨勢。此外，它可以用來收集人們對特定產(chǎn)品的評論信息?？梢宰C明這些評論的分析對于營銷和廣告活動的設計非常具有價值。

通過對過去社會化媒體數(shù)據(jù)挖掘工作的評估，我們發(fā)現(xiàn)社會化媒體數(shù)據(jù)挖掘最迫切需要解決的研究問題是準確地學習能夠揭示情感的觀點。在社交媒體上發(fā)布的大規(guī)模模糊和非結構化內容，具有快速處理社交媒體中大數(shù)據(jù)的能力。本文提出了一種大數(shù)據(jù)算法，同時也提出了一種并行算法，以處理大數(shù)據(jù)，從大量的Twitter數(shù)據(jù)中挖掘有用的見解。

1? 本文提出的大數(shù)據(jù)挖掘算法

1.1? 情感詞的情感分類

首先給出以下定義，使問題形式化：

定義1：（記錄集LD）設LD={d1，d2，…，dn}是收集的社會媒體文本數(shù)據(jù)的集合，由m個句子組成。

定義2：（同義詞集列表SL）設SL={a1，a2，…，am}是媒體環(huán)境中的同義詞集列表，由m標記的單詞數(shù)組成。

定義3：（情緒值集SV）設SV={x1，x2，…，xm}是同義詞集列表SL的每個元素的情感價值的收藏品，由m個分類數(shù)或數(shù)值或向量組成。

定義的隸屬函數(shù)的輸入應該是數(shù)字值或數(shù)字矢量，并且應該相對地包含語言術語的實際含義。情感同義詞列表中用于隸屬函數(shù)條目初始情感值已經(jīng)通過SentiWordNet 3.0查詢[8]。在所提出的方法中，模糊分區(qū)被定義為[正+，正，中，負，負-]，也被定義為語言術語{l1，l2，…，ln}。通過這種方式，可以使用這些模糊分區(qū)來定義和確定具有清晰數(shù)值的隸屬函數(shù)。由于輸入數(shù)據(jù)的性質和定義的語言術語經(jīng)常會產(chǎn)生符合高斯分布的隨機情感組合，所以如式（1）所示的高斯函數(shù)被用于定義隸屬函數(shù)。在同義詞集列表的基礎上，可以選擇特定同義詞集的初始情感值作為定義的隸屬函數(shù)的輸入，并且對于不同的語言學術語，高斯函數(shù)的參數(shù)根據(jù)選擇的同義詞集標簽被不同地定義。

特殊語言術語li的隸屬函數(shù)μFsi（x;μi，σi）可以定義為式（2）：

在上面的定義式中，參數(shù)σi是高斯分布的標準偏差，它被定義為固定值[0.25，0.15，0.125]，以符合情感值的理論平均分布。

1.2? Twitter數(shù)據(jù)集轉換為矩陣

為了充分表示社會媒體中確定的非結構化和嵌入的觀點，使用2.1節(jié)計算出的模糊值向量。本節(jié)提出了一種使用矩陣操作的新方法，將采集到的數(shù)據(jù)集轉換成多級矩陣。

首先，介紹了增加維度的過程：

定義4：（頂層屬性）設：UA=是通用屬性集，它總結了描述社交媒體數(shù)據(jù)的所有屬性。設子集Ec={Ec1，Ec2，…，Ep}，Ec∈UA是社會媒體數(shù)據(jù)本質特征的頂層屬性集。

定義5：（中間分層屬性）設子集E′=，E′∈UA是直接構成和補充Ec元素的中間分層屬性集。

定義6：（底部分層屬性）設子集E={E1，E2，…，En}，E∈UA是底層屬性集，間接描述E′的每個元素的特性。

使用上述定義，所提出的方法的總體思想遵循了增加維度的過程。它將嵌入在社交媒體中的所有關系定義為一個圖形，頂層屬性是要分析的目標屬性，例如“蘋果公司”，中間層屬性是屬于頂層屬性的屬性，例如目標公司生產(chǎn)的“iPhone 5s”等產(chǎn)品，與目標直接相關。定義底層分層屬性來描述中間層的屬性，以豐富目標的隱藏信息。例如，諸如“電池”等術語是產(chǎn)品的特征。結合直接和間接的劃分操作，所提出的維度提升過程可以顯著地測量目標對象丟失和隱藏的信息，它明顯優(yōu)于其他現(xiàn)有的直接社交媒體挖掘方法。

1.3? 定義數(shù)據(jù)集和LDij數(shù)據(jù)塊作為矩陣

整個收集社交媒體數(shù)據(jù)可先初步轉化為多級矩陣的子矩陣，并進一步給出了以下定義：

定義7：（數(shù)據(jù)塊）假設記錄集可以劃分為m×n數(shù)據(jù)塊LDij，使用底部分層屬性集E={E1，E2，…，En}作為列;使用一組有序的序列對象S={S1，S2，…，Sm}作為行。

因此，對于LD中的任何數(shù)據(jù)塊，LDij表示與屬性Ei相關的數(shù)據(jù)記錄，并按對象Sj進行分類。

然后，根據(jù)定義（4）中，記錄集的任何元素都可以表示為dj=a1×X1+a2×X2+…ag×Xg。為了更好地從每個數(shù)據(jù)塊LDij分組記錄，一個補充的信息因子ξi被定義為適合社交媒體數(shù)據(jù)中重復和不完整的信息，目的是降低后期矩陣操作的計算代價。

定義8：（補充信息因子）設ξ={ξ1，ξ2，…，ξn}為補充信息因子，根據(jù)每條記錄將所有出現(xiàn)的同義詞信息記錄為矩陣。

ξj可以測量任何一個補充信息，比如它在句子中的順序，或者它的出現(xiàn)時間是1。因此，例子中的語言情感極性[P+，P Ne N N-]的定量矢量對每個特征是唯一的，與特征的值相同，因此對每個記錄依次使用每個特征的這些定量向量來構造數(shù)據(jù)塊LDij的數(shù)據(jù)矩陣是合理的，如下所示，一個示例性描述中假設在LDij中存在一定數(shù)量的p記錄與許多K補充信息因子：

從上面的數(shù)據(jù)矩陣可以看出，行數(shù)等于數(shù)據(jù)記錄的數(shù)量，說明它是一個相當巨大的矩陣。從前面的例子可以看出，在真實的社交媒體環(huán)境中，所定義的特征與例子中的情感詞匯一樣重復。此外，為了將選擇的數(shù)據(jù)塊的問題進行分類為幾個類別，僅關注測量預定義的特征就足夠了，但是不一定要將每個數(shù)據(jù)記錄進行分類并全部包括在數(shù)據(jù)塊中，因此，從上面開始，一種應用二進制系統(tǒng)的方法被提出，它顯著地減少數(shù)據(jù)矩陣中的行數(shù)，這可以降低數(shù)據(jù)矩陣的復雜度和計算成本。

首先，該方法對所有數(shù)據(jù)塊中的特征向量進行了歸納，刪除其他相同的特征，構造出整個數(shù)據(jù)集的歸納特征集，例如，這個歸納特征集可以包括在記錄集LD中找到的所有情緒詞匯。然后，由于不需要順序地保留數(shù)據(jù)矩陣的所有記錄，下一步是確定每個數(shù)據(jù)記錄中是否存在特定特征。二進制數(shù)字系統(tǒng)用于標記每個數(shù)據(jù)記錄中的每個特征。在二進制系統(tǒng)中，計數(shù)只使用兩個符號0和1，當數(shù)字達到1時，增量將其重置為0，并且還向左增加下一個數(shù)字。

在發(fā)現(xiàn)感興趣的模糊關聯(lián)規(guī)則的基礎上，通過度量所有相關規(guī)則，將該算法擴展到目標預測中。更具體地說，任何模糊規(guī)則lq-lc的置信度可定義為：

2? 實驗分析與結果

為了評價所提出的大數(shù)據(jù)算法是否可以處理社交媒體數(shù)據(jù)的大規(guī)模收集，采用MapReduce框架并行化，以提高處理速度。實驗中使用的Twitter數(shù)據(jù)集是由OACM設計的網(wǎng)絡爬蟲系統(tǒng)Twitter.com收集的數(shù)據(jù)[9]，它包括2015年3月至2016年3月的所有推文，其中包含了超過5億條文本記錄。實驗的環(huán)境是Intel i7 3720QM和2 GB RAM的CPU;操作系統(tǒng)是Ubuntu12.04 X86_64 GNU/Linux;以及SUN Java jdk 1.7.0_25。Hadoop集群由4個節(jié)點組成，端到端TCP套接字的帶寬可達100 MB/s，對于每個NodeData，最大線程數(shù)為8。

2.1? 基于并行化的大數(shù)據(jù)算法的MapReduce框架

基于該算法的處理過程，本文設計了兩個Map Reduce作業(yè)來有效地并行化作業(yè)，是生成候選屬性作業(yè)和生成模糊規(guī)則作業(yè)。生成候選屬性作業(yè)的目的是基于兩個屬性對之間的關系來推斷多個屬性之間的關系。使用生成候選屬性作業(yè)的輸出，生成模糊規(guī)則作業(yè)被設計為優(yōu)化所識別的興趣模糊規(guī)則并計算每個規(guī)則權重以訓練分類模型。更具體地說，生成候選屬性作業(yè)包含一個Map函數(shù)，其偽碼在算法1所示。輸入數(shù)據(jù)集作為<key，value>對的序列文件存儲在HDFS上，其中關鍵字是將該記錄從序列文件移動到起始點偏移量，并且該值是記錄集LD的內容。整個社交媒體數(shù)據(jù)集LD被分割并廣播到所有的數(shù)據(jù)節(jié)點，并被并行掃描。對于每個映射任務，輸出<key’，value’>對，其中key’是候選屬性的值，value’是具有模糊值VBi的相應屬性矩陣。

算法1：生成候選屬性作業(yè)<key，value>的Map函數(shù)

Input： the offset as key， the record set LD as value.

Output： <key’， value’> pair

1.Map<attribute， vector> map= split（value.toString（））;

2. for（attribute： map.getkey（））{

3. take name as key’;

4.matrix=new SimpleMatrix（attribute.getFuzzySetSize（）， aimAttr. getFuzzySetSize（））;

5. i=0;

6. for（double value ： map.get（attribute））{

7.matrix.insertRow（i++，0，min（value，aimAttr.getFuzzy Vector（）））;}

8. take matrix as value’;

9. output <key’， value’>}

在同一個數(shù)據(jù)節(jié)點中，中間數(shù)據(jù)的處理不會涉及過多的通信成本。因此，根據(jù)映射函數(shù)的輸出，組合函數(shù)也被用來組合相同數(shù)據(jù)節(jié)點的中間數(shù)據(jù)和屬性的模糊度。Combine函數(shù)的偽代碼如算法2所示，其輸出<key'，value'>對的序列文件，其中key’是候選屬性之間的組合的名稱，并且value’由屬性矩陣與相同數(shù)據(jù)節(jié)點中的模糊值{VBi，VBi+1，…，VBi+m}組成。

算法2：生成候選屬性作業(yè)（KEY， V）的Combine函數(shù)

Input： key is the name of combinations between candidate attributes， V is the list of according attribute matrix with fuzzy values assigned to the same DataNode.

Output： <key’， value’> pair

1. Initiation a new Matrix argument（outMatrix）;

2. while（V.hasNext（））{

3. Matrix m = V.next（）;

4. outMatrix = outMatrix.add（m）;}

5. Take key as key’;

6. Take outMatrix as value’

7. output < key’， value’> pair;

合并動作完成后，使用約簡函數(shù)對所有數(shù)據(jù)節(jié)點訓練數(shù)據(jù)中同一屬性的模糊度進行求和，生成所有候選屬性關聯(lián)，并存儲在MongoDB中。

2.2? 提出的大數(shù)據(jù)算法的評價

將所收集的Twitter數(shù)據(jù)集應用于所提出的并行大數(shù)據(jù)算法的實驗表明，如圖1所示，借助于Map Reduce框架，大量樣本的處理速度遠大于沒有Map Reduce的版本，并且隨著樣本數(shù)量的增加，執(zhí)行時間也逐漸增加，而非MapReduce版本的執(zhí)行時間則迅速增加。增加數(shù)據(jù)集的大小說明代碼的非通信部分占用更多的時間，因為有更多的I/O和事務處理。說明并行版本可以減少總體通信時間的百分比。當線程數(shù)量從8個變?yōu)?2個時，另一個評估所提出的算法的性能的實驗說明處理速度隨著線程數(shù)量的增加而增加。此外，通過設置不同的卡方檢驗閾值來確定符合條件的候選人，與第一輪掃描相比，該算法在啟動多屬性挖掘過程時，可以顯著減少掃描數(shù)據(jù)庫所需的時間。

一般而言，結果表明所提出的并行算法具有次線性性能，隨著數(shù)據(jù)庫規(guī)模的增大，程序實際上變得更有效率，這意味著所提出的大數(shù)據(jù)算法具有處理大型社交媒體數(shù)據(jù)集的能力。在Map Reduce框架的幫助下，將整個數(shù)據(jù)集劃分為若干個按照數(shù)據(jù)節(jié)點處理的子集，以保存程序掃描數(shù)據(jù)集時的大小，并將算法過程生成的中間數(shù)據(jù)存儲在HDFS中，以節(jié)約程序掃描數(shù)據(jù)集的時間。這些處理也可以提高所提出的算法的處理速度，并且可以通過實驗結果來證明。

將所提出的大數(shù)據(jù)算法應用于收集到的Twitter數(shù)據(jù)，通過計算Twitter消息中表達的情感來挖掘社交媒體的觀點。

3? 結? 論

通過對近期社交網(wǎng)絡輿情挖掘的最新評價，本文已確定并強調了最引人注目的研究問題，即準確地了解可能揭示在社交媒體上發(fā)布的大量模糊和非結構化內容的觀點，并具有處理社交媒體大數(shù)據(jù)的快速處理能力。通過提出的大數(shù)據(jù)算法，通過提出的大數(shù)據(jù)算法，本文研究得到高效的實驗結果。為了確?？蓴U展性，采用Map Reduce框架來并行化所提出的算法，通過使用社交媒體數(shù)據(jù)集，可以證明該算法的潛力。在計算上，盡管數(shù)據(jù)集大小增加，但是執(zhí)行速度可以顯著增加。事實上，隨著數(shù)據(jù)集大小的增加以及數(shù)據(jù)節(jié)點數(shù)量的增加，加速比也隨之增加。

參考文獻：

[1] KAPLAN A M，HAENLEIN M. Users of the world，unite！ The challenges and opportunities of Social Media [J].Business Horizons，2010，53（1）：59-68.

[2] WANG F Y，CARLEY K M，ZENG D，et al. Social Computing：From Social Informatics to Social Intelligence [J].IEEE Intelligent Systems，2007，22（2），79-83.

[3] ULICNY B，KOKAR M，MATHEUS C. Metrics for monitoring a social political blogosphere：A Malaysian case study [J].IEEE Internet Computing，2010，14（2），34-44.

[4] JOSHI M，DAS D，GIMPEL K，et al. Movie Reviews and Revenues：An Experiment in Text Regression [C]//HLT'10 Human Language Technologies：The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics.Los Angeles：Association for Computational Linguistics，2010：293-296.

[5] BOLLEN J，MAO H N，ZENG X J. Twitter mood predicts the stock market [J]. Journal of Computational Science，2011，2（1）：1-8.

[6] ZHU F D，SUN H，YAN X F. Network mining and analysis for social applications [C]//KDD'14：Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining.New York：Association for Computing Machinery，2014.

[7] LI J，QIN Q M，HAN J W，et al. Mining Trajectory Data and Geotagged Data in Social Media for Road Map Inference [J/OL].Transactions in GIS，2014，19（1）：1-18.[2021-06-16].https：//onlinelibrary.wiley.com/doi/10.1111/tgis.12072.

[8] BACCIANELLA S，ESULI A，SEBASTIANI F. SentiWordNet 3.0： An Enhanced Lexical Resource for Sentiment Analysis and Opinion Mining [J/OL].LREC，2010，10：2200-2204.[2021-06-16].http：//citeseerx.ist.psu.edu/viewdoc/summary？doi=10.1.1.180.4108.

[9] CHAN K C C，WONG A K C，CHIU D K Y. Learning Sequential Patterns for Probabilistic Inductive Prediction [C]//IEEE Transactions on Systems，Man，and Cybernetics，1994，24（10）：1532-1547.

作者簡介：馮占偉（1981—），男，漢族，黑龍江巴彥人，講師，碩士，研究方向：軟件工程。