基于改进K-means,算法的微平台舆情分析研究——以UK-means,聚类算法为例

赵立坤 吴东领 韩灿灿

(唐山职业技术学院，河北 唐山 063000)

在国内，网络舆情规范的法律体制相对健全，文本聚类舆情监控研究有不少，比如：北大方正技术研究院推出的方正智思舆情预警辅助决策支持系统[1]，该系统有效地解决了地方政府部门以传统的人工方式进行舆情监测的难题，但在音频、视频等多媒体信息方面还不能对不确定性数据进行挖掘，挖掘的识别率和数据效率性较低。

在国外，许多西方国家已制定了与互联网舆情相关的法律规章。

美国TDT（Topic Detection and Tracking）系统是国外最有名的与互联网热点舆情发现与监控有关的系统，初衷只是为了研究出一些能够发现和跟踪来自数据流中重要信息和内容的算法[2]。

目前，国内外舆情分析管理方面虽然取得了较好的研究成果，Hamdan 与Govaert 通过运用EM 算法解决不确定性数据聚类的混合密度问题。然而，这个模型却不能任意地应用于其他聚类算法。

K-means算法是一种最经典、广泛的划分聚类算法，经常被用于网络舆情的聚类中分析中，因检测、识别不精确、抽样误差、过时数据来源等条件因素，舆情数据往往挖掘不足，导致部分舆情数据遗漏。假设实际位置是有效的，仅仅依靠记录的数据值，很多的目标可能被置于错误的数据集群中，从过时数据值中得到的数据集群有明显差异。

因此，本文提出一种基于UK-means 聚类算法对传统的初始聚类中心选择方法进行改进，通过不确定性因素与数据挖掘相结合的算法，用于微平台的聚类中，以期能更快、更准确地对近期微平台数据进行聚类，实现热点话题识别与追踪。

如图1 所示，提出一种分类法来区分出硬聚类和模糊聚类的两种数据聚类类型。硬聚类旨在通过考虑预 期的数据来提高聚类的准确性和有效性。模糊聚类表示每个数据项被赋予分配给数据簇的任意成员的概率，聚类的结果为一个“模糊”表格。

图1 不确定性数据挖掘的一种分类

传统算法未考虑数据不确定性而导致部分数据挖掘遗漏。在数据分类和数据聚集中，通过改进K-means算法对聚类质心、两个目标的距离或目标与质心的距离等重要度量作重新定义和进行更深的研究[3]。

为了在聚类过程中提取数据不确定性，我们提出一种实现最小化平方误差总和的E(SSE)目标算法。一个数据对象xi由一个带有不确定性概率密度f(xi)的不确定性区域决定。假设给定一组数据群集，期望平方误差总和计算如下：

数据集平均值如公式：

由此，我们将提出一种UK-means 聚类算法，来实现不确定性数据聚类。

1.Assign initial values for cluster means c1 to cK

2.repeat

3.for i=1 to n do

4.Assign each data point xito cluster Cj where E(||cj-xi||)is the minimum.

5.end for

6.for j=1 to K do

7.Recalculate cluster mean cj of cluster Cj

8.end for

9.until convergence

10.return C

通过UK-means 基于数据不确定性模型计算预期的距离和数据集质心，收敛性可按照不同的标准来定义。如果收敛性依赖于下平方误差，公式（1）中E(SSE)替代SSE。在第4 步中采用代数方法来确定E(||cj-xi||)，采用数值积分法确定线，圆等几何图形不确定性区域和不确定性概率密度。鉴于此，获得的E(||cj-xi||2)用来替代E(||cj-xi||)。

3.1 线性移动不确定性数据聚类

UK-means 算法适用于任意一个不确定性区域和概率密度函数。为了证明方法的可行性，我们假设在一个质心C=(z,q)和一个数据对象x 被指定在一个线性不确定的均匀分布的区域中。线性不确定性线段的终结点为（a,b）和（c,d），则参数δ 表示的线性方程式为(a+(c-a)t,b+(d-b)t)，其中t取值范围属于[0,1]。f(t)表示不确定性概率密度函数。

不确定性线段的距离公式为：

由此，可以得到：

其中B=2[(c-a)(a-z)+(d-b)(b-q)]

C=(z-a)2+(q-b)2

函数f(t)是均匀分布时，且f(t)=1 时，计算公式如下：

公式（4）、（5）计算为均匀分布的线性移动不确定性的平方距离。当概率密度函数不是均匀分布时（如，高斯分布），采样技术用来估计取值E(||cj-xi||)。

3.2 UK-means 算法的评估实验

为了评估UK-means 算法的可行性，我们采用100×100 的二维空间所组成的一组随机数据点作为记录。对于每个数据点根据单向线性不确定性模型为其随机产生不确定性。根据记录和不确定性模拟记录中的原始位置的偏移来表示目标的真实位置。对于每个数据点位置记录在案，目标可能的移动距离由随机产生一个数据来决定。计算和比较以下数据集的聚类输出结果：

（1）记录（传统K-means）

（2）记录+不确定性（改进UK-means）

（3）真实值（传统K-means）

为核实UK-means 算法产生的数据群集接近真实数据中数据群集，采用调整相似度的兰德指数（ARI）进行比较聚类结果[4]，计算两个数据群集之间的相似度来对聚类结果进行评估。ARI 取值范围为[−1,1]，值越大意味着聚类结果与真实情况越近似。

通过（2）与（3）数据群集间的ARI 指数和（1）与（3）数据群集间的ARI 指数比较，在不同的参数组合下，允许K-means 算法（（1）和（3））和UK-means算法（2）在一直运行至迭代次数达到10000 次或群集中的所有目标在两次连续迭代中没有发生任何变化时结束，n=1000 和K=20 时，从表1 可以看出D 值的不同实验结果。

表1 实验结果

研究表明：当不确定性程度增加时，UK-means 算法改进度就越高。当群集的个数非常小时，目标的个数和群集的个数对UK-means 算法的作用基本无影响。从表1 记录数据中可以看到UK-means 算法中兰德指数（ARI）的调整近似度始终高于传统的K-means 算法。因此，UK-means 算法得到的数据群集更接近于从真实世界的数据群集。

传统数据挖掘算法无法挖掘固有的不确定性，产生的挖掘结果与真实世界的数据不相符。在本论文中，提出了在不确定性数据挖掘领域研究的一个分类方法，提高网络舆情信息聚类结果的识别率、有效性，实现热点话题识别与追踪，从而准确高效地管理互联网信息[5]，防患于未然，对推动精神文明建设实现高质量发展有着较为重要的使用价值和应用价值。

猜你喜欢 不确定性舆情数据挖掘 法律的两种不确定性法律方法(2022年2期)2022-10-20改进支持向量机在特征数据挖掘中的智能应用九江学院学报(自然科学版)(2022年2期)2022-07-02探讨人工智能与数据挖掘发展趋势大众投资指南(2021年35期)2021-02-16基于事故数据挖掘的AEB路口测试场景北京航空航天大学学报(2020年10期)2020-11-14全球不确定性的经济后果英语文摘(2019年6期)2019-09-18英镑或继续面临不确定性风险中国外汇(2019年7期)2019-07-13英国“脱欧”不确定性增加 玩具店囤货防涨价玩具世界(2019年6期)2019-05-21数字舆情领导决策信息(2017年13期)2017-06-21数字舆情领导决策信息(2017年9期)2017-05-04软件工程领域中的异常数据挖掘算法电子技术与软件工程(2016年24期)2017-02-23

推荐访问:算法 舆情 分析研究