知网链接
原文链接
张京坤， 王怡怡
软件导刊 2022年21卷第6期 页码:141-146
DOI：10.11907/rjdk.211889 中图分类号：TP274
纸质出版日期：2022-06-15，收稿日期：2021-07-05
摘要： 为提高对舆情信息的分析能力，设计并实现基于Spark框架的均值漂移算法。使用Ansj分词、Word2vec算法对舆情信息进行特征提取，然后基于Spark并行计算框架和均值漂移算法原理进行聚类分析。实验结果显示，均值漂移算法在Iris和Wine两组数据集下的准确率均超过90%，聚类结果明显优于K-means算法，具有较好的适应性。性能实验结果表明，增加运行程序的并行化程度可以提高均值漂移算法的运行效率。基于Spark框架的均值漂移算法能有效提高舆情信息的分析能力，助力建立健康的网络环境。
关键词： 舆情；Spark；均值漂移；聚类；并行化
DOI：10.11907/rjdk.211889 开放科学（资源服务）标识码（OSID）：
中图分类号：TP274 文献标识码： A 文章编号：1672-7800（2022）006-0141-06
Analysis of Mean Shift Algorithm Based on Spark Framework in Public Opinion Clustering
Abstract： To improve the analysis ability of public opinion information， we design a mean shift algorithm based on the Spark framework. For public opinion， using the Ansj word segmentation and Word2vec algorithm feature extraction， finally clustering based on the Spark framework parallel computing model and the principle of mean shift algorithm. The numerical results show that， in both Iris and Wine data sets， the accuracy of the mean shift algorithm is over 90%， the clustering result is significantly better than the K-means algorithm， then the mean shift algorithm has better adaptability. In the performance experiment， it can effectively improve the operation efficiency of the algorithm and has better data scalability by increasing the degree of parallelization of the algorithm operation program. Therefore， the algorithm can effectively improve the analysis ability of public opinion，and help establish a healthy network environment.
Key Words： public opinion； Spark； mean shift； clustering； parallelization
0 引言
网络舆情潜移默化地影响着社会发展和人们的日常生活，由于其具有快捷性、开放性、突发性和隐蔽性的传播特点，加强舆情分析、监测和研判能力对于打造健康的网络环境具有重要意义。
在舆情分析监测中，使用聚类分析技术可以快速发现舆论热点并预测其发展趋势，有效辅助舆情决策。聚类是将物理或抽象对象的集合分类成由类似对象组成的多个簇的过程［1］。根据舆情信息的特征对舆情数据集进行聚类分析，使得同类舆情数据对象置于同一簇中，可揭示数据之间的内在关联，发掘其潜在规律与应用价值。
1 相关研究
近年来，许多类型的聚类分析算法与大数据处理技术相结合，被应用于文本分析研究中，如高维多视图智能聚类算法［2］ 、并行K-Means文本聚类算法［3］、矩阵优化与数据降维的文本聚类算法［4］等。Spark作为目前主流的大数据处理分析框架，采用内存计算模式，结合大数据查询分析计算（SQL and Data Frames）、流式计算（Spark Streaming）、机器学习（Spark MLlib）和Spark GraphX等多种计算范式，同时使用弹性分布式数据集（Resilient Distributed Datasets，RDD）和有向无环图（Directed Acyclic Graph，DAG）的抽象计算流程，极大提升了机器学习和数据挖掘的计算性能［5］。目前，基于Spark框架的聚类分析研究有很多，例如何倩等［6］基于Spark框架实现并行计算，设计了一种海量数据快速聚类算法；刘鹏等［7］设计了Spark框架下的K-means并行聚类算法；Lei等［8］基于Spark框架下的聚类算法研究了民族文化资源分类；Zhou等［9］利用TF-IDF算法结合Spark框架优化了新闻主题聚类方法；Qing等［10］利用K-Means聚类算法结合Spark框架分析了高校学生大数据信息；Xiao等［11］对现有基于Spark框架的并行聚类算法进行了分类和总结；于苹苹等［12］针对文本分类算法计算量大、处理速度慢的问题，优化了基于Spark框架的K-近邻算法；徐宁等［13］提出基于Spark并行预处理的方法分析配电网大数据。
然而，传统K-means聚类算法需要事先设定类别数量k值，聚类结果受k值影响较大。均值漂移（Mean Shift）算法无需指定聚类数目，是无参密度估计算法，其根据数据概率密度不断移动均值质心，最终将聚类中心漂移到该簇类样本点集合的高密度区域［14］。 文献［15］详细分析了Spark框架的特性和Mean Shift算法的原理，并阐述了该算法在Spark框架中的并行化实现原理。本文基于文献［15］的研究结果，将大量舆情信息数据集储存在分布式文件系统HDFS上，通过Ansj中文分词库对其进行分词，然后采用Spark MLlib中的Word2vec算法抽取分词后的舆情信息特征，最后利用Spark框架并行计算模型和Mean Shift算法原理对舆情信息的特征数据集进行聚类，以获取舆情信息聚类结果。
2 舆情聚类流程与关键技术
2.1 舆情聚类流程
舆情信息聚类主要根据同类文档相似度较大、不同类文档相似度较小的假设，将一系列舆情信息分为若干个簇［16］，是一种无监督机器学习方法，无需训练过程和预先类别标注，具有较强的灵活性和自动化处理能力，是分析舆情信息的有效手段。舆情信息的聚类流程包括信息预处理、特征提取和聚类分析3个阶段，具体如图1所示。
2.2 舆情聚类关键技术
2.2.1 舆情信息预处理
舆情信息预处理是聚类分析的第一个步骤，处理结果的好坏会直接影响聚类分析效果。该阶段包括多媒体信息处理、分词、去停用词等步骤，可将舆情信息统一转换为计算机可识别的结构化数据［15］。
2.2.2 向量空间模型构建
向量空间模型（Vector Space Model，VSM）是指将预处理后的舆情信息映射为欧氏空间中的向量，利用向量距离计算相似度。每个向量由特征项和特征权值表示，其中特征项表示欧氏空间中的维度［17］，而特征权值采用Word2Vec算法结合VSM构建［18］。
Fig. 1 Public opinion clustering process
图1 舆情信息聚类流程
2.2.3 聚类分析
使用Spark框架结合Mean Shift算法进行舆情聚类。Spark作为一种基于内存计算的开源框架，可将计算过程的中间结果保存到内存中，因此在处理需要频繁迭代的数据挖掘和机器学习算法时能有效缩短运行时间［19］。而Mean Shift算法的优势在于不需要任何先验条件， 可以选取任意一点作为起始点，不受维度和样本点分布的影响，具有较强的抗干扰能力［20-21］。
3 聚类流程设计与实现
3.1 分词和去停用词
Spark框架不支持分词和去停用词的功能，本文使用Ansj中文分词项目对舆情信息进行分词和去停用词处理。Ansj为中国自然语言处理开源组织（NLPChina）下的项目，分词速度达到每秒200万字，准确率高达96%。该项目具有中文分词、停用词过滤、姓名识别、关键字提取、自动摘要、关键字标记等功能［22］。使用Ansj进行舆情信息处理的Scala关键代码为：
Input： 舆情信息数据集；
Output： 舆情信息分词结果集；
- /*使用构造函数创建过滤规则对象*/
val filter = new StopRecognition（）
/*批量增加停用词词性*/
filter.insertStopNatures（"停用词词性"）
/*使用标准分词处理中文文本*/
val Output = ToAnalysis.parse（Input）
.recognition（filter）
3.2 特征提取
使用Spark MLlib中提供的Word2vec算法进行特征提取，将分词和去停用词后的舆情信息表示为分布式向量的形式，即将每条舆情信息映射为欧氏空间中的唯一向量，然后将该向量用于舆情信息的相似度计算［23-24］。基于Spark Mllib中的Word2vec算法提取舆情信息特征的Scala代码为：
Input： 舆情信息分词结果集；
Output： 舆情信息特征向量集；
- /*创建并构造待训练模型的参数*/
val word2Vec = new Word2Vec（）
/*设置输入输出列名*/
word2Vec.setInputCol（"输入列名"）
word2Vec.setOutputCol（"输出列名"）
/*设置特征向量集的维度*/
word2Vec.setVectorSize（正整数）
/*构造模型并得到输出结果*/
val model = word2Vec.fit（Input）
val Output = word2VM.transform（Input）
3.3 聚类
文献［15］中给出了基于Spark框架的Mean Shift算法实现原理，即利用Spark的并行化特点迭代计算同一簇中舆情样本点到基准点的距离，然后求出均值，并根据均值更新基准点［25-26］。本文在此基础上实现了基于Spark框架的Mean Shift算法，具体伪代码为：
Input： 舆情信息特征向量集；
Output： 聚类结果；
- 数据集归一化
where（收敛条件）：
分布式遍历样本点：
计算样本点到基准点的距离
提取距离小于阈值的样本点
计算新的基准点
判断新基准点到已有簇类中心点的距离
if（距离<阈值）：
合并到已有的簇
else：
记为新的簇
验证收敛条件
4 实验方法与结果分析
4.1 实验环境
采用Ambari + HDP（Hortonworks Data Platform）的部署模式，其中Ambari为Hortonworks推出的管理监控Hadoop生态圈的Web工具，可以对整个大数据平台进行动态管理，包括部署、修改、删除、扩展等，并能实时监控内存、CPU使用率、磁盘、网络IO状态。HDP是一款基于Apache Hadoop的开源数据平台，可提供大数据云存储、处理和分析等服务，平台包括HDFS、Yarn、Pig、Hive、HBase、Zookeeper、Kafka等组件。集群的服务器节点配置和各软件版本如表1所示。
Table 1 Server node settings and software version
表1 服务器节点配置和软件版本
4.2 实验数据集
实验采用4组数据集，分别为Iris（鸢尾花卉）数据集［27］、Wine（葡萄酒）数据集［27］、News（新闻）数据集、THUCNews（中文文本）数据集［28］。聚类效果评价选取Iris、Wine、News 3组数据集，性能测试使用THUCNews数据集。所有数据集的信息如表2所示。
Table 2 Data set information
表2 数据集信息
4.3 实验评价指标
4.3.1 聚类效果
采用精准率（Precision）、召回率（Recall）和F-Measure值对Mean Shift算法的聚类效果进行评价。其中精准率表示被正确划分到对应类别中的比例，召回率表示每个聚类类别中被正确划分的比例；F-Measure为准确率与召回率的调和平均数， 其值越接近1，聚类效果越好，计算公式［29］表示为：
（1）
式中，P表示Precision，R表示Recall，F表示F-measure。聚类结束后，通过比较聚类形成的簇与数据集中原始标注的类别判定聚类结果正确性。
4.3.2 聚类性能
采用运行时间、加速比、节点可扩展性和时间复杂度4个指标对Mean Shift算法的聚类性能进行评价。
（1）运行时间。运行时间谓聚类算法在不同线程数下处理舆情数据时程序运行的总时长，是最直观的性能评价指标，算法的运行时间越短，效率越高。
（2）加速比。加速比是指同一个数据集在单线程和多线程下消耗的时间比，是衡量并行计算性能的重要指标，表示为：
（2）
式中，Ts表示单线程下算法消耗的时间，Tm表示同一测试数据集在m线程下算法消耗的时间。加速比Sp (m)越大，表示算法的并行化效率越高［29-30］。
（3）节点可扩展性。节点可扩展性是随着线程数增加，聚类算法效率提高的比例，用于度量并行算法能否有效利用可扩展节点个数，表示为：
（3）
式中，m表示线程数，Sp (m)表示m线程上的加速比。节点可扩展性值越接近1，说明节点可扩展性越好［4］。
（4）时间复杂度。时间复杂度［31］是指算法的运行时间T(n)关于数据规模n的函数，用于分析T(n)随n的变化情况，并确定T(n)的数量级，表示为：
T(n)=O(f(n)) （4）
式中，f(n)为数据规模n的某个函数，O()为算法时间复杂度的表示方法。一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。常用的时间复杂度类型包括：①常数阶O(1)表示程序运行时间不随数据规模的增加而变化；②对数阶O(logn)表示随着数据规模的增长，程序运行时间呈对数增长；③线性阶O(n)表示随着数据规模的增长，程序运行时间呈线性增长；④平方阶O(n^2)表示程序的运行时间与数据规模呈乘方关系。
4.4 实验结果与分析
4.4.1 聚类效果比较
Mean Shift算法和传统K-means算法聚类效果比较如表3所示。可以看出，Means Shift算法在Iris和Wine两组数据集下的准确率均超过90%，其中对Wine数据集的准确率高达93.04%，召回率为92.47%，F值为0.927 5，而K-means聚类算法的准确率为41.06%，召回率为46.36%，F值为0.435 5。在Iris和News数据集下，两种算法的聚类效果相当，但在Wine数据集下，Means Shift算法的聚类效果明显优于K-means算法。总体来说，Means Shift算法相较于K-means算法具有更好的适应性。
Table 3 Comparison of algorithm clustering effect
表3 算法聚类效果比较
4.4.2 聚类性能考察
Mean Shift算法聚类性能实验分两组进行，第一组为运行时间、加速比和节点可扩展性考察，第二组为时间复杂度考察。第一组实验结果如表4所示，图2、图3、图4分别为对应线程数的运行时间折线图、加速比折线图、节点可扩展性折线图。第二组实验结果如表5所示，图5为程序运行时间折线图。
Table 4 Experimental results of algorithm performance
表4 算法性能实验结果
Table 5 Experimental results of time complexity
表5 时间复杂度实验结果
由图2可知，运行时间的缩短分为3个阶段，第一阶段线程数从1增加到11，程序运行时间由25.31h缩短至3.58h；第二阶段线程数从11增加到19，运行时间缩短缓慢；第三阶段当线程数超过19时，运行时间反而有所增加。图3结果显示加速比前两个阶段的变化趋势与运行时间变化基本一致，第三阶段当线程数超过19时，加速比有下降趋势。从图4可以看出，随着线程数的增加，节点的可扩展性越来越小。
如图5所示，在线程数不变的情况下，随着数据规模的增加，运行时间呈线性增长，其时间复杂度为。因此，Mean Shift聚类算法具有较好的数据可扩展性。
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聚类算法节点可扩展性
Fig. 5 Time complexity of Mean Shift clustering algorithm
图5 Mean Shift聚类算法时间复杂度
综上可知，当线程为11时，Mean Shift算法运行时间、加速比和节点可扩展性均达到了较好效果，这是由于随着线程数的增加，Spark框架的并行化计算功能可有效提高算法运行效率，但过多地增加线程数需要消耗更多硬件资源。同时，数据集在HDFS中是分块（Block）存储的，在Spark任务启动时每个Block块都会有对应的Task任务需要处理，当可用的线程数较少时，会出现单个线程依次处理多个Block块的情况。当逐渐增加可用线程数时，单个线程处理的Block块数量会相应减少，因此在线程数从1增加到19时，算法的运行时间一直在缩短。当线程数超过19时，Yarn平台为了创建更多Task任务而占用更多的服务器资源，因此线程数超过19时Mean Shift聚类算法的加速比不再增加。综上所述，针对THUCNews数据集，线程数设置为11~19之间较为合适。
5 结语
本文基于Spark框架研究设计Mean Shift算法，并在舆情数据集中进行了性能验证。实验结果表明，该算法的聚类效果和聚类性能优于传统的K-means算法，且适当增加运行线程数可以有效提高其运行效率。未来将继续优化舆情信息的分词和特征提取效果，以及算法的抗干扰能力，进一步提高其聚类准确率。
参考文献：
［1］ HUANG X H，WANG C，XIONG L Y，et al. A weighting k-means clustering approach by integrating intra-cluster and inter-cluster distances ［J］. Chinese Journal of Computers，2019，42（12）： 248-260. 黄晓辉，王成，熊李艳，等. 一种集成簇内和簇间距离的加权k-means聚类方法［J］.计算机学报，2019，42 （12）：248-260.
［2］ TAO Q，GU C Q，WANG Z Y，et al. An intelligent clustering algorithm for high-dimensional multiview data in big data applications ［J］. Neurocomputing，2019，393：234-244.
［3］ LI X Y，YU L Y，LEI H，et al. The parallel implementation and application of an improved K-means algorithm ［J］. Journal of University of Electronic Science and Technology of China，2017， 46（1）： 61-68. 李晓瑜，俞丽颖，雷航，等. 一种K-means改进算法的并行化实现与应用［J］. 电子科技大学学报，2017，46（1）： 61-68.
［4］ CHEN W，LU J W. Text clustering algorithm based on feature matrix optimization and data dimensionality reduction ［J］. Journal of Data Acquisition and Processing，2021，36（3）： 587-594. 陈玮，卢佳伟. 基于特征矩阵优化与数据降维的文本聚类算法［J］. 数据采集与处理，2021，36（3）： 587-594.
［5］ ZHU G H，HUANG S B，YUAN C F，et al.SCoS：the design and implementation of parallel spectral clustering algorithm based on Spark ［J］. Chinese Journal of Computers，2018，41（4）： 868-885. 朱光辉，黄圣彬，袁春风，等. SCoS： 基于Spark的并行谱聚类算法设计与实现［J］.计算机学报，2018，41（4）： 868-885.
［6］ HE Q，LI S F，HUANG H，et al. A fast clustering algorithm for massive data ［J］. Journal of Beijing University of Posts and Telecommunications，2020，43（3）：118-124. 何倩，李双富 黄焕，等.一种海量数据快速聚类算法［J］.北京邮电大学学报，2020，43（3）： 118-124.
［7］ LIU P，TENG J Y，DING E J，et al. Study of parallelized K-means algorithm on massive text based on Spark ［J］. Journal of Chinese Information Processing，2017，31（4）： 145-153. 刘鹏，滕家雨，丁恩杰，等. 基于Spark的大规模文本K-means并行聚类算法［J］.中文信息学报，2017，31（4）： 145-153.
［8］ LEI M，WEN B，GAN J，et al. Clustering algorithm of ethnic cultural resources based on Spark［J］. International Journal of Performability Engineering，2019，15（3）：756-762.
［9］ ZHOU Z，QIN J H，XIANG X Y，et al. News text topic clustering optimized method based on TF-IDF algorithm on Spark ［J］. Computers，Materials and Continua，2019，61（3）： 217-231.
［10］ QING H，WANG G J，WANG X Z，et al. Research and application on spark clustering algorithm in campus big data analysis ［J］. Journal of Computer Science Research，2020，2（1）：16-20.
［11］ XIAO W，HU J. A survey of parallel clustering algorithms based on Spark［J］.Scientific Programming，2020（5）： 1-12.
［12］ YU P P，NI J C，YAO B X，et al. Highly efficient Chinese text classification algorithm of KNN based on spark framework ［J］. Journal of Computer Applications，2016，36（12）： 3292-3297. 于苹苹，倪建成，姚彬修，等.基于Spark框架的高效KNN中文文本分类算法［J］. 计算机应用，2016，36（12）： 3292-3297.
［13］ XU N，WANG Y Q，DONG Z，et al. Research on distribution system big data preprocessing technology based on Apache Spark ［J］. Journal of North China Electric Power University（Natural Science Edition），2021，48（2）： 40-46，54. 徐宁，王艳芹，董祯，等. 基于Apache Spark的配电网大数据预处理技术研究［J］. 华北电力大学学报（自然科学版），2021，48（2）： 40-46，54.
［14］ LI X R，WU F Z，HU Z Y. Convergence of a mean shift algorithm ［J］. Journal of Software，2005（3）： 365-374. 李乡儒，吴福朝，胡占义. 均值漂移算法的收敛性［J］.软件学报，2005（3）： 365-374.
［15］ ZHANG J K，WANG Y Y. Application of Spark-based mean shift algorithm in network public opinion clustering ［J］. Software Guide，2020，19（9）： 196-201. 张京坤，王怡怡.基于Spark的均值漂移算法在网络舆情聚类中的应用［J］. 软件导刊，2020，19（9）： 196-201.
［16］ ZHANG Y L，ZHOU Y J.Review of clustering algorithms［J］.Journal of Computer Applications，2019，39（7）： 1869-1882. 章永来，周耀鉴. 聚类算法综述［J］.计算机应用，2019，39（7）： 1869-1882.
［17］ DU K，LIU H L，WANG B J. Research on Chinese text clustering method based on semantic relevance ［J］. Information Theory and Practice，2016，39（2）：129-133. 杜坤，刘怀亮，王帮金. 基于语义相关度的中文文本聚类方法研究［J］. 情报理论与实践，2016，39（2）： 129-133.
［18］ SALTON G M，WONG A，YANG C. A vector space model for automatic indexing ［J］. Communications of the ACM，1975，18（11）： 613-620.
［19］ AHMED N，BARCZAK A L C，SUSNJAK T，et al. A comprehensive performance analysis of Apache hadoop and Apache Spark for large scale data sets using HiBench ［J］. Journal of Big Data，2020，7（1）： 1-18.
［20］ COMANICIU D，MEER P. Mean shift analysis and applications ［C］//The Proceedings of the Seventh IEEE International Conference on Computer Vision，1999： 1197-1203.
［21］ COMANICIU D，MEER P. Distribution free decomposition of multivariate data ［J］. Pattern Analysis & Applications，1999，2（1）： 22-30.
［22］ NLPChina. Ansj Chinese word segme ［EB/OL］. https：//github.com/NLPchina/ansj_seg. 中国自然语言处理开源组织. Ansj中文分词［EB/OL］. https：//github.com/NLPchina/ansj_seg.
［23］ MIKOLOV T，CHEN K，CORRADO G，et al. Efficient estimation of word representations in vector space ［DB/OL］. https：//arxiv.org/pdf/1301.3781.pdf.
［24］ MIKOLOV T，SUTSKEVER I，KAI C，et al. Distributed representations of words and phrases and their compositionality ［C］//Proceedings of the 26th International Conference on Neural Information Processing Systems，2013：3111-3119.
［25］ COMANICIU D，MEER P. Mean shift： a robust approach toward feature space analysis［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（5）： 603-619.
［26］ DUDARIN P，SAMOKHVALOV M，YARUSHKINA N. An approach to feature space construction from clustering feature tree ［C］//Moscow： Russian Conference on Artificial Intelligence，2018.
［27］ DUA D，GRAFF C. UCI machine learning repository ［EB/OL］. http：//archive.ics.uci.edu/ml.
［28］ SUN M，LI J Y，GUO Z P，et al.THUCTC：an efficient Chinese text classifier［EB/OL］. http：//thuctc.thunlp.org. 孙茂，李景阳，郭志芃，等.THUCTC： 一个高效的中文文本分类工具包［EB/OL］. http：//thuctc.thunlp.org.
［29］ WANG L，JIA J C. Research on parallelization based on improved Canopy-K-means algorithm ［J］. Computer Measurement & Control，2021，29（2）：176-179，186. 王林，贾钧琛.基于改进Canopy-K-means算法的并行化研究［J］.计算机测量与控制，2021，29（2）：176-179，186.
［30］ HAI M，ZHANG Y.Performance comparison of clustering algorithms in Spark ［J］. Computer Science，2017，44（6A）：414-418. 海沫，张游. Spark平台下聚类算法的性能比较［J］. 计算机科学，2017，44（6A）： 414-418.
［31］ FU X H，ZHENG H H. Time complexity analysis of K-bisection search ［J］. Computer Technology and Development，2021，31（2）： 175-179. 傅晓航，郑欢欢. K分搜索的时间复杂度分析［J］. 计算机技术与发展，2021，31（2）： 175-179.
