基于改进的算法的新闻聚类的研究(2)

分级聚类实际上将产生一棵树，底部叶子结点代表n个样本，根结点为最后聚为一类的情况，中间的某层代表其中的一种聚类。

2 改进的k-means算法

传统的k-means算法对初始聚类中心敏感，聚类结果随不同的初始聚类中心而波动。针对k-means聚类算法中随机选取初始聚类中心的缺陷，本文提出了一种改进的方法，步骤如下：

(1) 准备好数据集D={d0,d1,d2,...,dn-1}，数据集中共有n 条数据。

(2)对簇的数目k 取2 到19，对于每一次聚类结果，计算惯性权重，画出k 值-惯性权重折线图，根据肘点法，选择最合适的簇的数目k1。

(3)使用k-means聚类算法对数据集进行多次聚类，每次聚类，k 从区间[k1-m,k1+j]随机取值(m>0,j>0 且m+j<8)，每一次聚类完成后，遍历所有数据点所在簇的标签，簇标签集合为{0,1,2,3,...,k-1}。

表1 数据与簇标签?

(4) 记录具有相同标签的两个数据点的位置，创建共协矩阵：

(5)多次运行k-means算法，把每一次迭代得到的共协矩阵相加，矩阵中的数值表示两个数据点被分到同一簇的次数。

(6) 使用分级聚类对第一步得到的共协矩阵进行聚类分析。构造共协矩阵的最小生成树。

图1 最小生成树

生成树中的节点对应数据集中的个体，边的权重对应两个节点被分到同一簇的次数，也就是共协矩阵所记录的值。

(7) 遍历最小生成树矩阵中的每一条边，删除低于阈值的边。

(8)最后，找到所有连通分支，也就是寻找移除低权重边以后仍然连接在一起的节点。连通分支的数量就是簇的数量，连通分支中的节点就是被分到同一簇的数据。

图2 删除低于阈值的边之后的连通分支

3 新闻数据聚类实验与结果分析

3.1 实验数据集

本文的实验数据集来源于网络搜狐新闻，数据集包含了9个类别的新闻：娱乐、财经、房地产、旅游、科技、体育、健康、教育、汽车，共4500条。新闻类别名与数量如下表所示。

表2 新闻数据集?

3.2 评价指标

本文的主要工作是提升新闻聚类的准确率，对于聚类产生的k个簇的新闻，采用准确率A来评价算法的正确性，准确率A的计算方法如下：

公式(3)中，Ca表示新闻数据集中所有新闻类别的集合，Ck表示使用k-means算法聚类后得到的类别集合。

3.3 实验分析

3.3.1 实验过程

首先对数据集进行分词、去除停用词处理。本文采用了jieba分词工具对数据集进行分词，采用哈工大停用词表去除数据集中的停用词。

对经过分词、去除停用词预处理之后的4500 条数据进行聚类，k 依次取区间[2,20)内的值，每次运行算法都计算惯性权重。

图3 中，横轴是k 的值，纵轴是惯性权重。由折线图可知，随着簇数量的增加，质心点和其他数据点位置的调整逐渐减少，惯性权重逐渐降低。簇数量为9 时，惯性权重进行了最后一次大的调整。

图3 k值-惯性权重折线图

使用k-means 算法对新闻数据集进行聚类，运行12 次，每次k 值在区间[6,12]上随机取值，将聚类结果保存到共协矩阵中。然后，将12次运行得到的共协矩阵相加，使用分级聚类算法对共协矩阵进行聚类分析，构造最小生成树，删除低于阈值的边后，连通分支就是聚类得到的各个簇。

对聚类结果中的每个簇，对该簇中的词语按权重由大到小排序，选取权重最大的10个词作为该簇关键词，聚类结果如下表所示。

表3 新闻聚类结果?

对聚类结果进行分析，可以得出结论：本文所提出的基于k-means的聚类方法能够准确、有效地对新闻进行分类，获取的聚类中心附近的高频关键词可以较好地反映该簇所包含新闻的内容、主题、类别。

3.3.2 对比分析

在同等条件下，用传统的k-means聚类算法对本文所使用的新闻数据集进行聚类分析。为保证结果的客观性，用传统kmeans算法进行了5次聚类，取平均值作为最终结果，实验结果的对比如表4所示。

表4 本文方法与传统k-means算法聚类的结果?

k-means 算法对初始聚类中心敏感，选择不同的聚类中心会产生不同的聚类结果和不同的准确率。随机选取初始聚类中心的做法会导致算法的不稳定性，有可能陷入局部最优的情况。实验表明，与传统k-means 聚类算法相比，本文使用证据累积算法对多次运行k-means算法得到的结果进行融合，能够平滑算法多次运行所得到的不同结果，可以减少波动。

文章来源：《新闻大学》 网址: http://www.xwdxzz.cn/qikandaodu/2021/0430/1399.html