K-means聚类算法的改进与应用

刘建花

(晋中师范高等专科学校 数理科学系,山西 晋中 030600)

1 问题提出背景

随着计算机技术和网络技术的不断发展，我们身边大量的数据不断生成，如何利用这些数据显得尤为重要，数据挖掘就是我们要利用的工具.数据挖掘也称知识发现，采用科学的方法或手段，为人们从数据库中找出对自己有益信息或感兴趣的信息提供帮助.聚类分析属于数据挖掘技术的一种，在模式识别、图像处理等领域都有广泛应用，当中的聚类算法也有很多，如BRICCH，ROCK， DASCAN算法等.

基于K-means聚类算法属于聚类分析中基于划分的一种.它具有简洁高效和收敛性好的特点.K-means聚类算法中对初始聚类中心选择是非常重要的，选择不同的中心会造成完全不一样的聚类结果.此外在已有条件上分析确定聚类数目也很重要，事先给定的聚类数目同预期多多少少会有偏差，传统的K-means算法的选取中心点是随机的，如果选的不合适，有可能产生的是局部最优解，影响聚类正确性.为了弥补此缺陷，迫切需要对传统K-means聚类算法通过分析研究进行优化.

2 传统K-means聚类算法

2.1 算法思想

该算法的作用是解决聚类问题，把数据集的数据对象按照同一簇中的数据具有高相似度和与其他簇中的数据对象是低相似度划分条件将数据对象归类到不同的簇中[1].

算法分以下几个步骤：

第一步：首先输入n个数据对象.

第二步：先确定K，即聚类中簇的个数，然后从数据对象中随机选择聚类中心点K个.

第三步：计算其余数据对象与K个聚类中心点之间的距离，比较距离并将其归类到与之距离最近的聚类中心的簇当中.

第四步：通过计算，把K个聚类簇中所有数据对象的均值作为新的聚类中心.

第五步：判断是否满足收敛条件，满足则结束，输出结果，否则回到第三步循环[2].

对K-means聚类算法而言，初始聚类中心的选择是非常重要的，选择不同的初始聚类中心会造成完全不一样的聚类结果.此外在已有条件上分析确定聚类数目也很重要，事先给定聚类数目同预期会有偏差，传统的K-means算法的选取初始聚类中心点是随机的，如果选的不合适，不仅会降低算法效率，而且会导致错误的结果.

2.2 算法优缺点

该算法优点：1)实现简单；2)效率高；3)输入数据的顺序不会对结果造成影响.缺点：1)聚类集群数目需提前确定，数据分析困难时，比较难确定;2)聚类中心点的随机选取会影响聚类结果；3)采用欧式距离的方法适合球状簇的聚类分析.

3 算法改进

针对传统K-means聚类算法的缺点聚类中心随机选取，提出改进办法如下：增加新变量密度的方法确立初始的聚类中心点，密度变量定义是以数据值为圆心r为半径数据对象的总个数[3].

3.1 定义

定义1领域半径Eps=Avg(X)=1/(c_n^2)×∑[d(x_i，x_j)],Avg(X)是数据集x中所有数据距离的平均值，c_n2是n中任意取两个的数目.

定义2点x_i密度p(x_i)=∣x_i∣d(x_i，x_j)≤Eps，公式含义是与x_i之间的距离小于Eps的数据数.

定义3平均密度Ap(n)=(∑_(i=1)n[p(x_i)])/n

选择K方法：初始两点：选距离最远的两数据.

确定第三个点：与初始两点的最小距离中选择大的.

确定第四个点：与已确定的三个点的最小距离中选择最大的.重复一直选出K个点.

3.2 改进后选择K的算法步骤：

第一步：输入n个数据.

第二步：计算数据两两之间的距离d(x_i，x_j)，组成一个n*n矩阵.

第三步：求出每个数据的点密度p(x_i)和平均密度Ap(n)，把所有点密度大于平均密度的数据归到新集合Y中，作为聚类中心的参考点.

第四步：在集合Y中选择密度最大的对象，标记为y_1，放入集合Z中,Y中删去y_1.

第五步：在矩阵中找与y_1距离最大的数据对象.

第六步：判断此对象是否在集合Y中，是则标记为y2,放入集合Z中，执行第七步，不在，将对应的值从矩阵中删去,重复执行第五步.

第七步：在矩阵中找与Z中数据对象最小距离中的最大的.

第八步：根据上一步求出的数据对象判断是否在Y中，是标记为yj，放入集合Z中，否则循环到第七步，直到Z中个数为K.

第九步：将集合Z中的数据作为初始聚类中心.

第十步：聚类分析，输出结果[4].

4 实验分析

通过实验来对比传统K-means算法和改进K-means算法的聚类效果，并对结果进行统计与分析，下面的实验是先将学校校园网上的热点话题进行聚类然后对学校舆情进行预测和分析.

首先要进行数据采集，借助API文本抓取工具，在校园网上的论坛、贴吧、微博等系统上抓取数据，接着对抓取的数据进行文本去噪后存入数据库，然后利用NLPIR分词系统进行分词，停用词过滤、词性过滤，删去介词、连词、语气词之类的虚词只留下名词和动词，预处理结束后，为了将文本变为计算机可识别的格式，用于输入算法中.采用向量空间模型vsm的方法表示文本.

实验评价指标采用TDP评价标准：

准确率(P)：指正确归类的样本数据与全部样本数据的比例，P=TP/TP+FP.

召回率(R)指正确归类的样本数据在全部归类样本数据中所占比重，R=TP/TP+FN.

准确率和召回率加权调和平均(F1)：F1=2PR/(P+R).

TP：事实相关,结果相关的文档.

FP：事实不相关,结果为相关的文档.

FN：事实相关,结果为不相关的文档.

TN：事实不相关，结果不相关的文档[5].

表1 实验结果对比

由表1得出F1值对比图,如图1.

改进K-means算法F1值比传统K-means算法大，F1值高意味着召回率和准确率都比较高.由此得出结论改进K-means算法聚类效果好.

对结果再进一步地分析，看出学生感兴趣的项目有游戏、晚自习、旷课、美食、恋爱和周边游.学生对学习方面关注的太少，今后学校老师应注重学生对待学习态度的正确引导，学生对待爱情也很迷茫，也要注重学生培养正确的恋爱观.

5 总结

本文在传统K-means算法的基础上经过分析提出增加密度变量方法选取聚类中心的改进方法使算法提高了准确性，避免了孤立点的影响，但仍存在不足：K-means算法的K值确定困难，合适K值的选择，需要进一步的研究.