随着互联网的高速发展，人们已经迈向了一个信息化的时代，互联网上的信息交流和获取逐渐取代了传统的电视、报纸、书信等传统媒体。截至2019 年6 月，中国网民规模为8.54 亿人，互联网普及率达61.2%，网站数量518万个。人们每天通过浏览器或者新闻APP看新闻产生大量点击记录，对人们点击的海量新闻进行分析，可以获知特定时间和特定范围内公众最关心的热门事件，进而可以在信息爆炸的互联网时代帮助人们更快、更好、更有效地获取有用的信息。如何快速、有效地在海量新闻浏览记录中发现其中的趋势和主题，不仅能够帮助个人更准确地了解全社会关注的热点事件，同时还能辅助国家及时发现网络舆情事件、趋势，在网络舆情分析、重大网络事件监测防御、信息网络安全等领域具有极其重要的现实意义。

聚类分析旨在分析数据过程中发现数据对象之间的相互关系，将数据依据一定原理进行分组，各分组结果内的相似性越大，各分组之间的差别就越大，聚类效果越好。k 均值(kmeans)聚类算法具有快速、简单的特点，对大数据集有较高的分析效率。

本文提出了一种结合k-means算法与分级聚类算法的方法，利用k-means算法对预处理过的新闻数据集进行多次聚类，然后用证据累积算法融合多次聚类得到的结果，减少波动。本文对搜狐新闻数据进行分析，考查本文方法的聚类效果，并与传统kmeans算法的聚类效果进行比较，体现本文方法的优势。

1 算法简介

1.1 k-means算法

k-means 算法采用迭代更新的思想，该算法的目标是根据输入的参数k将数据对象聚成k簇，其基本思想为：首先指定需要划分的簇的个数k 值，随机地选择k 个初始数据对象作为初始聚类或簇的中心；然后计算其余的各个数据对象到这k个初始聚类中心的距离，并把数据对象划分到距离它最近的那个中心所在的簇中，然后根据公式：

重新计算每个簇的中心作为下一次迭代的聚类中心。公式(1)中，Ci表示聚类所得簇C={C1,C2,...,Ck}中第i个簇[1]。

不断重复这个过程，直到达到规定的最大迭代次数或者聚类准则函数(误差平方和函数)收敛。收敛函数如下：

公式(2)中：E 为k-means 算法针对样本D={x1,x2,...,xk}聚类所得簇C={C1,C2,...,Ck}划分的最小化平方误差。通常E 值越小则簇内样本相似度越高[2]。

迭代使得选取的聚类中心越来越接近真实的簇中心，所以聚类效果越来越好，最后把所有对象划分为k个簇[3]。

1.2 k-means算法步骤

k-means算法步骤如下[4][5]：

输入：数据集D={x1,x2,x3,...,xn}，k值。

输出：簇集C={C1,C2,...,Ck}。

(1)从数据集中随机选择k 个数据对象作为初始聚类中心C={C1,C2,...,Ck}；

(2)Repeat

(3) 针对数据集中的每个样本xi，计算它到k个聚类中心的欧式距离，并将其分到距离最小的聚类中心所对应的簇中；

(4) 针对每个簇Ci，更新聚类中心(即计算该样本的质心)， ||Ci为该类样本个数；

(5)Until聚类中心不再变化，聚类准则函数收敛。

1.3 k-means算法优缺点

k-means 算法是解决聚类问题的经典算法，这种算法简单快速。当结构集是密集的，簇与簇之间区别明显时，聚类的结果比较好。在处理大量数据时，该算法具有较高的可伸缩性和高效性。

但是，目前传统的k-means算法也存在着许多缺点[6,7]：

(1)k-means 聚类算法需要用户事先指定聚类的个数k值。在很多时候，在对数据集进行聚类的时候，用户起初并不清楚数据集应该分为多少类合适，对k值难以估计。

(2)对初始聚类中心敏感，选择不同的聚类中心会产生不同的聚类结果和不同的准确率。随机选取初始聚类中心的做法会导致算法的不稳定性，有可能陷入局部最优的情况。

1.4 分级聚类算法

分级聚类是一种自底向上的聚类方法。它的主要思想是：首先将每个样本自定义为一类，然后逐步合并，直到最后聚为一类或者达到要求为止[8,9]。

对于给定的n 个样本集合X={x1,x2,...,xn}，分级聚类方法的具体步骤如下：

(1)X 中每个样本xi均自成一类ci，这样就构建了一个初始聚类C={c1,c2,...,cn}；

(2)计算C中每对类(ci,cj)之间的相似度sim(ci,cj)；

(3)选择最大相似度的类对Max(sim(ci,cj))，并将其合并为一个新类ck=ci?cj，构成一个新的聚类C={c1,c2,...,ck,...,cn-1}；

(4)如果C 中只有一个类或C 已经达到要求，则结束；否则转到(2)。

上一篇：基于技术的新闻信息聚类与热点研究
下一篇：没有了