張京坤，王怡怡

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

0 引言

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

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

1 相關(guān)研究

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

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

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

2.1 輿情聚類流程

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

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

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

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

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

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

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

2.2.3 聚類分析

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

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

3.1 分詞和去停用詞

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

3.2 特征提取

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

3.3 聚類

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

4 實(shí)驗(yàn)方法與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

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

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

4.2 實(shí)驗(yàn)數(shù)據(jù)集

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

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

4.3 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

4.3.1 聚類效果

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

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

4.3.2 聚類性能

采用運(yùn)行時(shí)間、加速比、節(jié)點(diǎn)可擴(kuò)展性和時(shí)間復(fù)雜度4個(gè)指標(biāo)對(duì)Mean Shift算法的聚類性能進(jìn)行評(píng)價(jià)。

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

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

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

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

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

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

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

4.4 實(shí)驗(yàn)結(jié)果與分析

4.4.1 聚類效果比較

Mean Shift 算法和傳統(tǒng)K-means 算法聚類效果比較如表3 所示?？梢钥闯觯琈eans Shift 算法在Iris 和Wine 兩組數(shù)據(jù)集下的準(zhǔn)確率均超過90%，其中對(duì)Wine 數(shù)據(jù)集的準(zhǔn)確率高達(dá)93.04%，召回率為92.47%，F(xiàn) 值為0.927 5，而Kmeans 聚類算法的準(zhǔn)確率為41.06%，召回率為46.36%，F(xiàn) 值為0.435 5。在Iris 和News 數(shù)據(jù)集下，兩種算法的聚類效果相當(dāng)，但在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 算法聚類性能實(shí)驗(yàn)分兩組進(jìn)行，第一組為運(yùn)行時(shí)間、加速比和節(jié)點(diǎn)可擴(kuò)展性考察，第二組為時(shí)間復(fù)雜度考察。第一組實(shí)驗(yàn)結(jié)果如表4 所示，圖2、圖3、圖4 分別為對(duì)應(yīng)線程數(shù)的運(yùn)行時(shí)間折線圖、加速比折線圖、節(jié)點(diǎn)可擴(kuò)展性折線圖。第二組實(shí)驗(yàn)結(jié)果如表5 所示，圖5 為程序運(yùn)行時(shí)間折線圖。

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

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

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

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

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

Fig.2 Running time of Mean Shift clustering algorithm圖2 Mean Shift聚類算法運(yùn)行時(shí)間

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é)點(diǎn)可擴(kuò)展性

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

5 結(jié)語

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