Spark框架下均值漂移算法對輿情聚類的分析

張京坤，王怡怡

（1.中國電子科技集團太極計算機股份有限公司，北京 100020；2.陜西師范大學數(shù)學與信息科學學院，陜西西安 710100）

0 引言

網(wǎng)絡(luò)輿情潛移默化地影響著社會發(fā)展和人們的日常生活，由于其具有快捷性、開放性、突發(fā)性和隱蔽性的傳播特點，加強輿情分析、監(jiān)測和研判能力對于打造健康的網(wǎng)絡(luò)環(huán)境具有重要意義。

在輿情分析監(jiān)測中，使用聚類分析技術(shù)可以快速發(fā)現(xiàn)輿論熱點并預(yù)測其發(fā)展趨勢，有效輔助輿情決策。聚類是將物理或抽象對象的集合分類成由類似對象組成的多個簇的過程［1］。根據(jù)輿情信息的特征對輿情數(shù)據(jù)集進行聚類分析，使得同類輿情數(shù)據(jù)對象置于同一簇中，可揭示數(shù)據(jù)之間的內(nèi)在關(guān)聯(lián)，發(fā)掘其潛在規(guī)律與應(yīng)用價值。

1 相關(guān)研究

近年來，許多類型的聚類分析算法與大數(shù)據(jù)處理技術(shù)相結(jié)合，被應(yīng)用于文本分析研究中，如高維多視圖智能聚類算法［2］、并行K-Means 文本聚類算法［3］、矩陣優(yōu)化與數(shù)據(jù)降維的文本聚類算法［4］等。Spark 作為目前主流的大數(shù)據(jù)處理分析框架，采用內(nèi)存計算模式，結(jié)合大數(shù)據(jù)查詢分析計算（SQL and Data Frames）、流式計算（Spark Stream?ing）、機器學習（Spark MLlib）和Spark GraphX 等多種計算范式，同時使用彈性分布式數(shù)據(jù)集（Resilient Distributed Datasets，RDD）和有向無環(huán)圖（Directed Acyclic Graph，DAG）的抽象計算流程，極大提升了機器學習和數(shù)據(jù)挖掘的計算性能［5］。目前，基于Spark 框架的聚類分析研究有很多，例如何倩等［6］基于Spark 框架實現(xiàn)并行計算，設(shè)計了一種海量數(shù)據(jù)快速聚類算法；劉鵬等［7］設(shè)計了Spark 框架下的K-means 并行聚類算法；Lei 等［8］基于Spark 框架下的聚類算法研究了民族文化資源分類；Zhou 等［9］利用TFIDF 算法結(jié)合Spark 框架優(yōu)化了新聞主題聚類方法；Qing等［10］利用K-Means 聚類算法結(jié)合Spark 框架分析了高校學生大數(shù)據(jù)信息；Xiao 等［11］對現(xiàn)有基于Spark 框架的并行聚類算法進行了分類和總結(jié)；于蘋蘋等［12］針對文本分類算法計算量大、處理速度慢的問題，優(yōu)化了基于Spark 框架的K-近鄰算法；徐寧等［13］提出基于Spark 并行預(yù)處理的方法分析配電網(wǎng)大數(shù)據(jù)。

然而，傳統(tǒng)K-means 聚類算法需要事先設(shè)定類別數(shù)量k 值，聚類結(jié)果受k 值影響較大。均值漂移（Mean Shift）算法無需指定聚類數(shù)目，是無參密度估計算法，其根據(jù)數(shù)據(jù)概率密度不斷移動均值質(zhì)心，最終將聚類中心漂移到該簇類樣本點集合的高密度區(qū)域［14］。文獻［15］詳細分析了Spark 框架的特性和Mean Shift 算法的原理，并闡述了該算法在Spark 框架中的并行化實現(xiàn)原理。本文基于文獻［15］的研究結(jié)果，將大量輿情信息數(shù)據(jù)集儲存在分布式文件系統(tǒng)HDFS 上，通過Ansj 中文分詞庫對其進行分詞，然后采用Spark MLlib 中的Word2vec 算法抽取分詞后的輿情信息特征，最后利用Spark 框架并行計算模型和Mean Shift 算法原理對輿情信息的特征數(shù)據(jù)集進行聚類，以獲取輿情信息聚類結(jié)果。

2 輿情聚類流程與關(guān)鍵技術(shù)

2.1 輿情聚類流程

輿情信息聚類主要根據(jù)同類文檔相似度較大、不同類文檔相似度較小的假設(shè)，將一系列輿情信息分為若干個簇［16］，是一種無監(jiān)督機器學習方法，無需訓練過程和預(yù)先類別標注，具有較強的靈活性和自動化處理能力，是分析輿情信息的有效手段。輿情信息的聚類流程包括信息預(yù)處理、特征提取和聚類分析3個階段，具體如圖1所示。

2.2 輿情聚類關(guān)鍵技術(shù)

2.2.1 輿情信息預(yù)處理

輿情信息預(yù)處理是聚類分析的第一個步驟，處理結(jié)果的好壞會直接影響聚類分析效果。該階段包括多媒體信息處理、分詞、去停用詞等步驟，可將輿情信息統(tǒng)一轉(zhuǎn)換為計算機可識別的結(jié)構(gòu)化數(shù)據(jù)［15］。

2.2.2 向量空間模型構(gòu)建

向量空間模型（Vector Space Model，VSM）是指將預(yù)處理后的輿情信息映射為歐氏空間中的向量，利用向量距離計算相似度。每個向量由特征項和特征權(quán)值表示，其中特征項表示歐氏空間中的維度［17］，而特征權(quán)值采用Word2Vec算法結(jié)合VSM 構(gòu)建［18］。

Fig.1 Public opinion clustering process圖1 輿情信息聚類流程

2.2.3 聚類分析

使用Spark 框架結(jié)合Mean Shift 算法進行輿情聚類。Spark 作為一種基于內(nèi)存計算的開源框架，可將計算過程的中間結(jié)果保存到內(nèi)存中，因此在處理需要頻繁迭代的數(shù)據(jù)挖掘和機器學習算法時能有效縮短運行時間［19］。而Mean Shift 算法的優(yōu)勢在于不需要任何先驗條件，可以選取任意一點作為起始點，不受維度和樣本點分布的影響，具有較強的抗干擾能力［20-21］。

3 聚類流程設(shè)計與實現(xiàn)

3.1 分詞和去停用詞

Spark 框架不支持分詞和去停用詞的功能，本文使用Ansj 中文分詞項目對輿情信息進行分詞和去停用詞處理。Ansj 為中國自然語言處理開源組織（NLPChina）下的項目，分詞速度達到每秒200 萬字，準確率高達96%。該項目具有中文分詞、停用詞過濾、姓名識別、關(guān)鍵字提取、自動摘要、關(guān)鍵字標記等功能［22］。使用Ansj 進行輿情信息處理的Scala關(guān)鍵代碼為：

3.2 特征提取

使用Spark MLlib 中提供的Word2vec 算法進行特征提取，將分詞和去停用詞后的輿情信息表示為分布式向量的形式，即將每條輿情信息映射為歐氏空間中的唯一向量，然后將該向量用于輿情信息的相似度計算［23-24］?；赟park Mllib 中的Word2vec 算法提取輿情信息特征的Scala代碼為：

3.3 聚類

文獻［15］中給出了基于Spark 框架的Mean Shift 算法實現(xiàn)原理，即利用Spark 的并行化特點迭代計算同一簇中輿情樣本點到基準點的距離，然后求出均值，并根據(jù)均值更新基準點［25-26］。本文在此基礎(chǔ)上實現(xiàn)了基于Spark 框架的Mean Shift算法，具體偽代碼為：

4 實驗方法與結(jié)果分析

4.1 實驗環(huán)境

采用Ambari+HDP（Hortonworks Data Platform）的部署模式，其中Ambari 為Hortonworks 推出的管理監(jiān)控Hadoop生態(tài)圈的Web 工具，可以對整個大數(shù)據(jù)平臺進行動態(tài)管理，包括部署、修改、刪除、擴展等，并能實時監(jiān)控內(nèi)存、CPU 使用率、磁盤、網(wǎng)絡(luò)IO 狀態(tài)。HDP 是一款基于Apache Hadoop 的開源數(shù)據(jù)平臺，可提供大數(shù)據(jù)云存儲、處理和分析等服務(wù)，平臺包括HDFS、Yarn、Pig、Hive、HBase、Zoo?keeper、Kafka 等組件。集群的服務(wù)器節(jié)點配置和各軟件版本如表1所示。

Table 1 Server node settings and software version表1 服務(wù)器節(jié)點配置和軟件版本

4.2 實驗數(shù)據(jù)集

實驗采用4 組數(shù)據(jù)集，分別為Iris（鳶尾花卉）數(shù)據(jù)集［27］、Wine（葡萄酒）數(shù)據(jù)集［27］、News（新聞）數(shù)據(jù)集、THUCNews（中文文本）數(shù)據(jù)集［28］。聚類效果評價選取Iris、Wine、News 3 組數(shù)據(jù)集，性能測試使用THUCNews 數(shù)據(jù)集。所有數(shù)據(jù)集的信息如表2所示。

Table 2 Data set information表2 數(shù)據(jù)集信息

4.3 實驗評價指標

4.3.1 聚類效果

采用精準率（Precision）、召回率（Recall）和F-Measure值對Mean Shift 算法的聚類效果進行評價。其中精準率表示被正確劃分到對應(yīng)類別中的比例，召回率表示每個聚類類別中被正確劃分的比例；F-Measure 為準確率與召回率的調(diào)和平均數(shù)，其值越接近1，聚類效果越好，計算公式［29］表示為：

式中，P表示Precision，R表示Recall，F(xiàn)表示F-mea?sure。聚類結(jié)束后，通過比較聚類形成的簇與數(shù)據(jù)集中原始標注的類別判定聚類結(jié)果正確性。

4.3.2 聚類性能

采用運行時間、加速比、節(jié)點可擴展性和時間復(fù)雜度4個指標對Mean Shift算法的聚類性能進行評價。

（1）運行時間。運行時間謂聚類算法在不同線程數(shù)下處理輿情數(shù)據(jù)時程序運行的總時長，是最直觀的性能評價指標，算法的運行時間越短，效率越高。

（2）加速比。加速比是指同一個數(shù)據(jù)集在單線程和多線程下消耗的時間比，是衡量并行計算性能的重要指標，表示為：

式中，Ts表示單線程下算法消耗的時間，Tm表示同一測試數(shù)據(jù)集在m線程下算法消耗的時間。加速比Sp(m)越大，表示算法的并行化效率越高［29-30］。

（3）節(jié)點可擴展性。節(jié)點可擴展性是隨著線程數(shù)增加，聚類算法效率提高的比例，用于度量并行算法能否有效利用可擴展節(jié)點個數(shù)，表示為：

式中，m表示線程數(shù)，Sp(m)表示m線程上的加速比。節(jié)點可擴展性值越接近1，說明節(jié)點可擴展性越好［4］。

（4）時間復(fù)雜度。時間復(fù)雜度［31］是指算法的運行時間T(n)關(guān)于數(shù)據(jù)規(guī)模n的函數(shù)，用于分析T(n)隨n的變化情況，并確定T(n)的數(shù)量級，表示為：

式中，f(n)為數(shù)據(jù)規(guī)模n的某個函數(shù)，O()為算法時間復(fù)雜度的表示方法。一般情況下，隨著n的增大，T(n)增長最慢的算法為最優(yōu)算法。常用的時間復(fù)雜度類型包括：①常數(shù)階O(1)表示程序運行時間不隨數(shù)據(jù)規(guī)模的增加而變化；②對數(shù)階O(logn)表示隨著數(shù)據(jù)規(guī)模的增長，程序運行時間呈對數(shù)增長；③線性階O(n)表示隨著數(shù)據(jù)規(guī)模的增長，程序運行時間呈線性增長；④平方階O(n2)表示程序的運行時間與數(shù)據(jù)規(guī)模呈乘方關(guān)系。

4.4 實驗結(jié)果與分析

4.4.1 聚類效果比較

Mean Shift 算法和傳統(tǒng)K-means 算法聚類效果比較如表3 所示。可以看出，Means Shift 算法在Iris 和Wine 兩組數(shù)據(jù)集下的準確率均超過90%，其中對Wine 數(shù)據(jù)集的準確率高達93.04%，召回率為92.47%，F(xiàn) 值為0.927 5，而Kmeans 聚類算法的準確率為41.06%，召回率為46.36%，F(xiàn) 值為0.435 5。在Iris 和News 數(shù)據(jù)集下，兩種算法的聚類效果相當，但在Wine 數(shù)據(jù)集下，Means Shift 算法的聚類效果明顯優(yōu)于K-means 算法?？傮w來說，Means Shift 算法相較于K-means 算法具有更好的適應(yīng)性。

Table 3 Comparison of algorithm clustering effect表3 算法聚類效果比較

4.4.2 聚類性能考察

Mean Shift 算法聚類性能實驗分兩組進行，第一組為運行時間、加速比和節(jié)點可擴展性考察，第二組為時間復(fù)雜度考察。第一組實驗結(jié)果如表4 所示，圖2、圖3、圖4 分別為對應(yīng)線程數(shù)的運行時間折線圖、加速比折線圖、節(jié)點可擴展性折線圖。第二組實驗結(jié)果如表5 所示，圖5 為程序運行時間折線圖。

Table 4 Experimental results of algorithm performance表4 算法性能實驗結(jié)果

Table 5 Experimental results of time complexity表5 時間復(fù)雜度實驗結(jié)果

由圖2 可知，運行時間的縮短分為3 個階段，第一階段線程數(shù)從1 增加到11，程序運行時間由25.31h 縮短至3.58h；第二階段線程數(shù)從11 增加到19，運行時間縮短緩慢；第三階段當線程數(shù)超過19 時，運行時間反而有所增加。圖3 結(jié)果顯示加速比前兩個階段的變化趨勢與運行時間變化基本一致，第三階段當線程數(shù)超過19 時，加速比有下降趨勢。從圖4 可以看出，隨著線程數(shù)的增加，節(jié)點的可擴展性越來越小。

如圖5 所示，在線程數(shù)不變的情況下，隨著數(shù)據(jù)規(guī)模的增加，運行時間呈線性增長，其時間復(fù)雜度為O(n)。因此，Mean Shift聚類算法具有較好的數(shù)據(jù)可擴展性。

綜上可知，當線程為11 時，Mean Shift 算法運行時間、加速比和節(jié)點可擴展性均達到了較好效果，這是由于隨著線程數(shù)的增加，Spark 框架的并行化計算功能可有效提高算法運行效率，但過多地增加線程數(shù)需要消耗更多硬件資源。同時，數(shù)據(jù)集在HDFS 中是分塊（Block）存儲的，在Spark 任務(wù)啟動時每個Block 塊都會有對應(yīng)的Task 任務(wù)需要處理，當可用的線程數(shù)較少時，會出現(xiàn)單個線程依次處理多個Block 塊的情況。當逐漸增加可用線程數(shù)時，單個線程處理的Block 塊數(shù)量會相應(yīng)減少，因此在線程數(shù)從1增加到19 時，算法的運行時間一直在縮短。當線程數(shù)超過19 時，Yarn 平臺為了創(chuàng)建更多Task 任務(wù)而占用更多的服務(wù)器資源，因此線程數(shù)超過19 時Mean Shift 聚類算法的加速比不再增加。綜上所述，針對THUCNews 數(shù)據(jù)集，線程數(shù)設(shè)置為11～19之間較為合適。

Fig.2 Running time of Mean Shift clustering algorithm圖2 Mean Shift聚類算法運行時間

Fig.3 Speedup ratio of Mean Shift clustering algorithm圖3 Mean Shift聚類算法加速比

Fig.4 Node scalability of Mean Shift clustering algorithm圖4 Mean Shift聚類算法節(jié)點可擴展性

Fig.5 Time complexity of Mean Shift clustering algorithm圖5 Mean Shift聚類算法時間復(fù)雜度

5 結(jié)語

本文基于Spark 框架研究設(shè)計Mean Shift 算法，并在輿情數(shù)據(jù)集中進行了性能驗證。實驗結(jié)果表明，該算法的聚類效果和聚類性能優(yōu)于傳統(tǒng)的K-means 算法，且適當增加運行線程數(shù)可以有效提高其運行效率。未來將繼續(xù)優(yōu)化輿情信息的分詞和特征提取效果，以及算法的抗干擾能力，進一步提高其聚類準確率。