知网链接
原文链接
张京坤， 王怡怡
软件导刊 2020年19卷第9期 页码:190-195
DOI：10.11907/rjdk.192529
出版日期：2020-9-15
摘 要： 为了改善网络舆情态势感知和预警中舆情信息分析不准确的问题，提出基于Spark技术的均值漂移（Mean Shift, MS）算法，利用Mean Shift算法原理分析Spark框架的特性，给出Mean Shift算法在Spark框架中的实现过程，包括舆情信息的预处理、特征提取、特征向量模型的构建和Mean Shift算法聚类的设计。实验结果显示，在相同数据集下进行Mean Shift算法和K-means算法的聚类效果对比，本文提出的基于Spark的Mean Shift算法聚类结果符合预期期望， K-means算法聚类结果受值选取的影响，存在聚类结果不准确的问题。基于Spark的Mean Shift算法在没有任何先验条件下在舆情聚类中优于K-means聚类算法。
关键词：网络舆情；聚类；均值漂移；Spark；K-means
开 放 科 学（资 源 服 务）标 识 码（OSID）：
Application of Spark-based Mean Shift Algorithm in Network Public Opinion Clustering
Abstract: In order to improve the inaccurate analysis of public opinion information and the analysis of public opinion information in early warning, a Mean Shift (MS) algorithm based on Spark technology is proposed. Based on the principle of mean shift algorithm, this paper analyzes the characteristics of spark framework, and gives the realization process of mean shift algorithm in spark framework, including the preprocessing of public opinion information, feature extraction, construction of feature vector model and design of clustering of mean shift algorithm.The experimental results show that the clustering results of mean shift algorithm and K-means algorithm are compared under the same data set. The clustering results of the proposed spark based mean shift algorithm meet the expectations. The clustering results of K-means algorithm are affected by the selection of K value, and there is the problem of inaccurate clustering results. The Mean Shift algorithm based on spark is better than the K-means algorithm in public opinion clustering without any prior conditions.
Key words: network public opinion; clustering; Mean Shift; spark; K-means
0 引言
网络舆情作为社会舆情的重要组成部分，是社会舆情在网络空间中的反映，围绕社会事件的发生、发展和变化体现广大网民对社会事件的态度、情感、意见、观点以及传播与互动的方式方法，其六大要素为：网络、事件、网民、情感、传播互动和影响力。由于网络舆情的直接性、突发性、隐蔽性和偏差性，容易成为社会事件的"放大器"和"助推器"，进而引发舆论热点。因此，加强对网络舆情的分析监测和及时妥善控制，是化解网络舆情危机的重要手段。而网络舆情信息在传播过程中，并不会事先对其进行类别标注，也无法确定含有的类别总数，因此很难采用基于类别标注的挖掘算法对舆情信息进行处理，而聚类算法不需要先验知识，也不需要模型训练，可以直接对待处理的网络舆情信息进行挖掘处理，操作更加高效，快捷，因此聚类算法已作为数据挖掘的重要方法之一[1]。聚类算法结合大数据平台技术在网络舆情聚类中的研究应用也越来越多，如邓先均[2]等人，研究了网络舆情热点话题监测的聚类算法；陈雪刚[3]研究了基于大数据技术的微博舆情快速自聚类方法；李海明[4]研究了基于 SSDKmeans 算法的微博热点话题发现；马梅[5]等基于MapReduce技术，结合 K-means 改进算法分析网络舆情，提高了网络舆情分析的准确率和效率。
在大数据环境中，大都基于MapReduce并结合K-means算法来分析网络舆情，但K-means聚类算法[6]需要事先设定值，从待聚类的样本中随机取个元素作为中心点进行聚类，聚类结果受值的设定等因素的影响，导致聚类结果不稳定。传统的Hadoop架构处理迭代运算时要从磁盘中频繁读取数据造成效率低下。Mean Shift算法因其计算简单、收敛速度快、对噪声的鲁棒性强等优点在很多领域中被广泛应用，如聚类分析[7]、对象轮廓检测[8]、滤波[9]、图像分割[7,10,11]、跟踪[7,10,12]等，同时Spark框架具有计算速度快、易用性高、通用性广、可融合性强等优点。针对上述启发，本文提出一种基于Spark平台的Mean Shift算法进行网络舆情聚类，解决Mean Shift算法频繁迭代的效率问题。
本文剩余内容安排如下：第一节是对Spark框架和Mean Shift算法的简介。第二节给出基于Spark框架的Mean Shift算法的设计，包括舆情信息的预处理、特征提取、聚类分析三个阶段，同时给出本文主要算法设计。第三节设计实验，结果显示Mean Shift算法较K-means算法有更高的准确率。
1 Spark框架和Mean Shift算法的简介
1.1 Spark框架简介
Spark是在MapReduce的基础上实现的分布式内存计算框架[13]，具备MapReduce优点[14]的同时还具有很强的易用性和通用性，比MapReduce性能更加优异。在Spark框架中，核心抽象概念是弹性分布式数据集（Resilient Distributed Datasets，RDD）[15]，它是分布在集群上的只读型可恢复数据集的抽象，具体是利用Spark中的转换（transformation）和动作（action）两种类型的操作，可将数据长期保存在内存中不被回收，当再次使用这部分数据时，不需要再次创建此RDD， 这也是Spark在迭代问题中性能高于MapReduce的重要原因。 RDD通过血统（lineage）关系来完成容错：如果一个RDD丢失，丢失的RDD数据集通过所谓的血统关系记住了它是如何从其它RDD中演变过来的，因此可以重新运算恢复丢失的RDD。相较于分布式存储器，RDD可更高效地实现容错，其具有的不变性可实现MapReduce的推测式执行，同时它的数据分区特性可通过数据的本地性来提高性能，并且RDD都可进行序列化，当内存不足时会自动降级为磁盘存储[16]。实验表明[17]，Spark比Hadoop在处理迭代运算时的速度提高20多倍，计算数据分析类报表的性能提高了40多倍，在交互式查询GB级数据集时Spark可以达到次秒级响应时间。
1.2 Mean Shift算法原理
Mean Shift算法，最早由Fukunage和Hosteler提出[18]，Cheng[19]对其主要提出了两点的改进：其一定义了核函数，其二增加了权重系数。2005年由李乡儒等[20]人对Mean Shift算法的收敛性进行了严格的证明。下面给出Mean Shift向量的定义：
定义1：给定维空间中的个样本点，对于其中一个样本，其Mean Shift向量为：
(1)
其中是一个半径为的高维球状区域，。
为了方便下文讨论，本文以二维圆形区域为例，则圆型区域形式为：
(2)
表示区域内的所有样本点，表示在个样本点中，有个点落入区域中。
式(1)中是样本点的偏移向量，定义的Mean Shift向量是对落在区域中的个样本点相对于点的偏移向量求和后平均。如果样本点从概率密度函数中采样得到，由于非零点概率密度梯度指向概率密度增加的方向，理论上来说，区域内的样本点更多的落在沿着概率密度梯度的方向，则相应的，Mean Shift向量指向概率密度梯度的方向。这里用图1进行说明。图1中大圆圈所圈定的范围是，大圆圈所圈定的实心小圆点代表落入区域内的样本点，空心大圆点是Mean Shift的基准点，基准点指向样本点的箭头表示样本点相对于基准点的偏移量，由图可以看出偏移向量会指向样本分布最多的区域，即概率密度函数的梯度方向，对应图1中的箭头方向。
图1 Mean Shift向量
接下来给出Mean Shift算法原理，用图2所示过程分析其算法步骤：假设某一次迭代的起始位置搜索区域半径为，也就是图2-a中的圆形区域半径，图中的实心点均为样本数据，具体实现Mean Shift算法的步骤如下：
- 找出图2-a中以基准点半径为内的所有样本点，记为集合；
计算图2-a起始位置处半径为内所有样本点相对于基准点的偏移向量，如图2-b，2-c所示；
将基准点沿着偏移向量的方向移动，移动距离为偏移向量的模，得到新的基准点，如图2-d所示；
按照1-3的过程进行迭代，直到满足迭代次数或限制条件的要求，如图2-e；
最终得到的基准点即为聚类的中心点，如图2-f所示。
图2 Mean Shift算法原理
从上述的步骤可以看出，Mean Shift 算法的过程即：从起始点开始，基准点到达样本特征点的密度中心，整个过程实际上不是从图2-a起始值漂移到了图2-f中的位置，而是图2-a和图2-f处的特征值归为了一类。简单的说，Mean Shift就是沿着密度上升的方向寻找同属一个簇的数据点。
2 基于Spark的Mean Shift算法设计
Mean Shift算法是利用支持向量机相关的性质进行的聚类算法，其基本思想是通过反复迭代搜索特征空间中样本点最密集的区域。本文将Mean Shift算法在Spark框架下并行化实现网络舆情聚类的过程分为3个阶段：预处理阶段、特征提取阶段、并行化聚类分析阶段。
2.1 网络舆情信息的预处理
网络舆情信息的预处理是聚类分析的第一个步骤，预处理的结果会直接影响聚类分析的效果。目前网络舆情信息的记录和储存方式多种多样，包括文字，图片，音频，视频等，属于非结构化的数据，计算机不能直接识别。因此需要先对网络舆情信息进行预处理，包括解压、解码、无效、去重、合并、提取、清洗、分词等过程，将图片，音频，视频等多媒体信息先转为文本信息，然后再统一把文本信息转为计算机能够识别的结构化数据，之后才能进行聚类操作。其中包含多媒体形式的网络舆情信息转换为纯文本形式的舆情信息的流程如图3所示：
图3 包含多媒体形式舆情信息处理流程
预处理的关键步骤是分词，所谓分词，就是将舆情信息按照词的含义进行切分，使得分词后的舆情信息既能够包含足够的信息，又能够得到较合适的特征维数[21]。经过文本分词后得到的单词集还不能作为特征集来表示舆情信息，因为它可能包含各类网络舆情文本中普遍出现的通用词和弱性词，即停用词，这些词更多的作用是在语法上，几乎出现在任何一个网络舆情文本信息中，但是对舆情信息的表达几乎没有任何价值。因此，需要按照停用词表从单词集中过滤掉所有的停用词，从而降低特征空间维数，减少噪声。目前常用的停用词表有哈工大停用词表、百度停用词表等。
2.2 特征提取阶段
特征提取阶段是将预处理后的舆情信息，根据特征提取算法计算出特征向量，本文采用TF-IDF算法结合向量空间模型[22]（Vector Space Model，VSM）来构建舆情信息的特征向量。其中TF-IDF的公式为[23]：
(3)
其中， 为特征项在舆情信息中的权重，为特征项在舆情信息中的词频，为舆情信息总数，为出现特征项的舆情信息数量，分母为归一化因子，舆情信息的向量化表示为
(4)
其中表示第个舆情信息的第个特征项，表示该特征项的权重，表示向量中特征项的个数，。
计算TF-IDF值的主要代码如下：
- # article_list：经过预处理后的单词集
# folder_list：舆情信息列表
# corpus 语料库
def tf_idf(article_list, folder_list, corpus):
out_dic = {}
fre_word = {}
for i in article_list:
if str(i) in fre_word:
count = fre_word[str(i)]
fre_word[str(i)] = count + 1
else:
fre_word[str(i)] = 1
for i in set(article_list):
# 某个词在一条网络舆情信息中出现的次数/网络舆情总词数
tf = fre_word[str(i)] / len(article_list)
# log(语料库的网络舆情总数/(包含该词的网络舆情数+1))
idf = math.log(len(folder_list) / (word_doc_num(str(i), corpus) + 1))
# 计算TF-IDF
tf_idf_value = tf * idf
out_dic[str(i)] = tf_idf_value
# 字典排序
order_dic = sorted(out_dic.items(), key=operator.itemgetter(1), reverse=True)
# 返回字典数据的TF-IDF值
return order_dic
经过特征提取处理后的舆情信息由文本信息转变为键值对数据，键表示的是每个特征词，值表示的是该特征词在单条舆情信息中的权重，根据所有的特征词库可以建立一个欧氏空间，而每一个舆情信息则表示欧氏空间中的一个向量。
2.3 舆情聚类分析阶段
利用Spark并行化实现Mean Shift算法是采用"Map"和"Reduce"的思想，迭代过程先用"Map"计算所有网络舆情样本点和基准点的距离，再用"Reduce"分类求均值计算新的基准点，在进行舆情聚类时，首先获取舆情数据(已经转换为特征向量的舆情数据)并切分成多个RDD对象，之后进行Map操作，即对每个RDD中的局部数据按类划分，然后Reduce操作进行汇总数据，计算得到每个基准点。聚类算法的并行化由Spark框架自动完成，即自动将舆情数据集和执行任务分配到不同的节点，并行执行聚类计算。以下的设计分析需要用到聚类的定义，在这里给出其定义[24]：
定义2 给定数据集合，其中是数据点，根据其相似度将数据集合分成组：的过程称为聚类，其中称为簇。
文本相似度可用欧氏距离公式来计算：
(5)
其中，和是数据集中两个维的数据对象。
基于以上分析，则舆情聚类分析的流程如图4所示：
图4 舆情聚类分析流程图
通过对舆情数据的并行化聚类之后，舆情数据在每个分片（RDD）中分别局部聚类，那么合并后的聚类个数是所有分片中的聚类个数之和即个类，最后对个类再次聚类分析，最终得到个类。
Mean Shift算法在Spark框架下并行化实现网络舆情聚类过程的具体流程如图5所示：
图5 Mean Shift算法的Spark并行化实现网络舆情聚类
3 设计与分析
常见的聚类算法有K-Means算法[14]、Mean Shift算法，中心点算法[25]，Birch算法[26]，Dbscan算法[27]等。其中K-means算法应用最为广泛，被添加到各个数据挖掘软件包中。本文将对K-means和Mean Shift两种算法在相同的人工模拟数据集下的聚类效果进行对比，其中K-means算法需要指定值，将选取不同的值对比聚类效果。模拟数据集包含3个簇，其中心的坐标分别为、、 ，随机生成1000个二维样本数据。如图6所示，图6-a为Mean Shift算法聚类结果，图6-b为值为2的K-means聚类结果，图6-c为值为3的K-means聚类结果, 图6-d为值为4的K-means聚类结果，每种聚类结果得到的中心点坐标如表1所示。
图6 K-means和Mean Shift聚类结果对比
由图6可以看出，Mean Shift算法自动聚为3类，符合预期结果。K-means聚类中，值为3时符合预期聚类结果，而值为2和4时，虽然算法收敛，但并不符合预期聚类结果。在K-means算法中值的选取对聚类结果的准确性有很大的影响，Mean Shift算法则不存在此种情况。
表1 聚类结果中心点的坐标
|
算法 |
聚类结果中心点 |
|
Mean Shift |
(0.92398641, -0.99498673) (-0.93532476, -0.99447027) (-0.93532476, -0.99447027) |
|
K-means(k=2) |
(1.07559475, 0.81950881) (-0.18243842, -1.11160236) |
|
K-means(k=3) |
(-1.02177393, -1.00022259) (0.99443631, 1.11514591) ( 1.04739089, -1.04086713) |
|
K-means(k=4) |
(-1.04287799, -0.99535218) (1.15077312, 0.20424437) (0.93262472, 1.40797709) ( 0.98357807, -1.25686545) |
实验主要代码如下：
- # 生成人工模拟数据
centers = [[1, 1], [-1, -1], [1, -1]]
data, _ = make_blobs(n_samples=1000, centers=centers, cluster_std=0.6)
# Mean Shift聚类代码
bandwidth = estimate_bandwidth(data, quantile=0.2, n_samples=500)
# 设置均值偏移函数
ms = MeanShift(bandwidth=bandwidth, bin_seeding=True)
# Mean Shift 聚类
ms.fit(data)
# 获取所有点的标签，即每条数据所属的簇
labels = ms.labels_
# 获取聚类得到的中心点
cluster_centers = ms.cluster_centers_
# 获取标签集合
labels_unique = np.unique(labels)
# 获取中心点数或聚类个数
MS_clusters_ = len(labels_unique)
# K-means 聚类核心代码
# 创建K-means聚类模型，n_clusters为k值
estimator = cluster.KMeans(n_clusters=3)
# K-means 聚类
res = estimator.fit_predict(data)
# 获取所有点的标签，即每条数据所属的簇
label_pred = estimator.labels_
# 获取聚类得到的中心点
centroids = estimator.cluster_centers_
# 获取中心点数或聚类个数
K_clusters_ = len(centroids)
4 结语
准确、快速地分析网络舆情是舆情态势感知和预警的基础，本文通过基于Spark的均值漂移算法在网络舆情聚类中的应用研究，可以看出，K-means算法的值选取往往会影响聚类效果的准确率，基于Spark的Mean Shift算法进行网络舆情聚类的结果优于K-means算法。未来将继续研究基于Spark框架的均值漂移算法在网络舆情聚类中的稳定性和效率问题，同时增加实验数据量并添加噪音数据测试算法的抗干扰性能。
参考文献：
[1]刘鹏，滕家雨，丁恩杰，et al. 基于Spark的大规模文本K-means并行聚类算法[J]. 中文信息学报，2017，31(4)：145-153.
[2]邓先均，杨雅茜，罗昭，et al. 网络舆情热点话题检测聚类算法研究[J]. 数字技术与应用，2018，335(5)：156-159.
[3]陈雪刚. 基于大数据技术的微博舆情快速自聚类方法的研究[J]. 情报杂志，2017，36(5)：113-117.
[4]李海明. 基于SSDKmeans算法的微博热点话题发现研究[J]. 软件导刊, 2019,18(9)：.173-175
[5]马梅，刘东苏，李慧. 基于大数据的网络舆情分析系统模型研究[J]. 西安电子科技大学，2014(3)：25-28．
[6]周爱武，于亚飞，et al. K-means聚类算法的研究[J]. 计算机技术与发展，2011，21(2)：62-65.
[7]周芳芳，樊晓平，叶榛. 均值漂移算法的研究与应用[J]. 控制与决策，2007，22(8)：841-847.
[8] WINK O，NIESSEN W，VIERGEVER M A. Fast delination and visualization of vessels in 3-D angiographic images[J]. IEEE Trans on Medical Imaging，2000，19(4)：337-346.
[9]NUMMIARO K，KOLLER-MEIER E，GOOL L V. An adaptive color-based particle filter[J]. Image and Vision Computing，2003，21(1)：99-110.
[10]曹玉华，吴小俊，段先华，et al. 基于背景提取和扩展均值漂移算法的目标跟踪[J]. 计算机工程与应，2009，45(13)： 194-196.
[11]李艳，灵孟庆伟，邬长安. 基于相关性比较算法的均值漂移图像分割[J]. 计算机应用研究，2010，27(1)： 342-344.
[12]谢晶梅，宋亚男，徐荣华. 基于均值漂移的车辆追踪研究[J]. 电子世界，2016，(2)：136-139 .
[13]高官涛，郑小盈，宋应文，et al. 基于Spark MapReduce框架的分布式渲染系统研究[J]. 软件导刊，2013, (12)：26-29.
[14]周婷，张君瑛，罗成. 基于 Hadoop 的 K-means聚类算法的实现[J]. 计算机技术与发展，2013，(7):18-21．
[15]ZAHARIA M，CHOWDHURY M，DAS T，et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[C]. Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association，2012，1−14.
[16]XIE X，XIONG Z，HU X，et al. On massive spatial data retrieval based on spark [C]. International Conference on Web-age Information Management. 2014：200-208.
[17]何海林，皮建勇. 大数据处理平台比较与分析[J]. 微型机与应用，2015，34(11)：7-9.
[18]FUKUNAGA K，HOSTETLER L. The estimation of the gradient of a density function, with applications in pattern recognition[J]. IEEE Transactions on Information Theory，1975，21(1)：32-40..
[19]YIZONG CHENG. Mean Shift，mode seeking, and clustering [J]. IEEI Trans on Pattern Analysis and Machine Intelligence, 1995，17(8)：790-799.
[20]李乡儒，吴福朝，胡占义. 均值漂移算法的收敛性[J]. 软件学报，2005，16(3)：365-373.
[21]黄昌宁，赵海. 中文分词十年回顾[J]. 中文信息学报，2007，21(3)：8-19.
[22]SALTON G. A Vector space model for automatic indexing [J]. Communications of the Acm，1975，18(11)：613-620.
[23]刘鹏，滕家雨，丁恩杰，et al. 基于Spark的大规模文本K-means并行聚类算法[J]. 中文信息学报，2017，31(4)：145-153.
[24]程国建，赵倩倩. K-means聚类算法在Spark平台上的应用[J]. 软件导刊，2016，15(2)：146-148.
[25]谢娟英, 郭文娟, 谢维信. 基于邻域的K中心点聚类算法[J]. 陕西师范大学学报，2012，40(4)：16-22.
[26]蒋盛益, 李霞. 一种改进的BIRCH聚类算法[J]. 计算机应用, 2009，29(1)：293-296.
[27]荣秋生, 颜君彪, 郭国强. 基于DBSCAN聚类算法的研究与实现[J]. 计算机应用，2004，24(4) ：45-46.
