改进模拟退火算法的K—means聚类方法在学生成绩上的应用

【摘 要】本文以学生管理系统中学生的成绩作为测试集，提出一种新的基于改进模拟退火的k-means算法的评价函数，挖掘学生成绩中的有效数据，用改进前后的算法来解决最优问题。实验证明改进模拟退火的k-means聚类算法收敛效果要优于传统的K-means算法，具有更好的聚类性能，其算法更加高效。

【关键词】模拟退火算法 数据挖掘 K-means聚类 学生成绩

【中图分类号】G 【文献标识码】A

【文章编号】0450-9889（2017）08C-0149-04

聚类（Clustering）是一种重要的数据分析手段，常用于数据挖掘领域，其主要用于实现对数据的深层次分析。它已经广泛应用于图像处理、模式识别、生物信息学等各个领域。K-means算法是数据挖掘中聚类问题的重要算法之一，也是现在公认的最有前景的数据分析算法。然而，由于随机初始聚类中心的选取，因此聚类算法得不到全局最优解，并且收敛时间过长，影响分类的效果，会导致聚类结果的极不稳定。

1953年，Metropolis等人提出一种基于概率的算法——模拟退火算法（Simulated Annealing）。利用模拟退火算法采用启发式搜索初始聚类中心，再结合K-means算法，可以解决局部最优解优解的问题；同时减少了迭代次数，提高了聚类划分的质量，让数据分析更科学化。

早已有一些学者研究模拟退火K-means聚类算法，并提出了一系列具有进步意义的观点，将其投入到实际应用中。李健等学者也进行了这一类研究，并将其跟镜头聚类相结合，进行了拓展性应用分析；陈慧萍等人将其跟UCI机器学习数据结合，提高了机器的运算能力；陈明等人将模拟退火K-means聚类算法跟多波段图像相结合，发现模拟退火K-means聚类算法能够从多波段图像中提取有价值的信息，提高对采集的数据的运算能力。本文以学生管理系统中学生的成绩作为测试集，提出一种新的基于改进模拟退火的K-means算法的评价函数，挖掘学生成绩中的有效数据，更准确地体现聚类的类内间距和类间间距，从而促进教学质量的提高。

一、模拟退火算法概述

模拟退火算法的基本思想最开始来源于固体物质退火学说中，其做法为：先加热某个物体，让其升温到一定的温度。当温度足够高时再进行缓慢降温。在使用模拟退火K-means聚类算法优化问题的时候，往往能够将内能E转化为我们需要的目标函数值f，也能够将在这个过程中的温度T转化为控制参数t，这样可以推算得到优化方法：先计算初始解与t，对解实施迭代，之后体系的t不断地减小，控制体系的温度T降低，当体系的控制参数t降到最低值的时候，我们就能够得到一个最优解，该数值也就是本次计算的理想数值。

模拟退火算法性质上属于启发式随机算法，相对于过去使用的算法来说，该种算法运算简单，应用范围广，计算起来比较容易，运算效率快，而且不容易受到初始条件的约束。从理论层面上来看，利用该种算法是能够获得最优解的，而且也有人证明该种方法计算得到最优解的概率为100%，同时该种方法也能够进行大规模运算量的操作，提高了人们对数据的分析能力。

模拟退火算法也有很多缺点，比如说当参数变化的时候，其运算结果也会发生变化。控制体系的温度T衰减参数若是选择的不好，或者是退火过程的收敛速度太慢，都会影响到解的精确性，影响了我们计算获得最优解。

二、聚类

聚类（Clustering）是一种重要的数据分析手段，常用于数据挖掘领域（Data Mining），其主要用于实现对数据的深层次分析。而K-means聚类算法又是聚类数据分析中最主要的一种，也是目前最科学化的一种算法。K-means聚类算法最早是Steinhaus（1955）、Loyd（1957）、Ball&Hall（1965）和McQueen（1967）在其相应的研究领域提出的。K-means聚类算法运算效率高、计算方法渐变、运算应用范围广，这些都让K-means聚类算法在诸多领域得到了应用，比如信息技术领域、医学领域、决策科学领域等，都展现出了K-means聚类算法的应用价值。

K-means聚类算法的优势在于能够找到该类准则下的最小k个划分，而这类算法的结合能力好，比較容易实现，同时各项指标也都发现K-means聚类算法具有很多优势，比如收敛能力强、运算效率高等。在K-means聚类算法中，如果各类之间区别明显，同时数据分布也比较密集，则使用K-means聚类算法处理数据能够得到最佳结果。若是处理一些大规模的数据，K-means聚类算法也能够很好地实现对数据的处理，不仅处理效率高，而且伸缩性较好。在K-means聚类算法中，算法的复杂度是O（nkm）。这三个字母有着不同的含义，n的含义是对象的数目，k的含义是聚类数目，m的含义是迭代次数。这三个指标的大小规律为k和m的数值一般要比n小很多。

然而，K-means聚类算法的应用范围也比较窄，主要是因为以下几个缺陷：一是最初的划分会显著影响最后的数据分析结果；二是k需要提前设定，无法自动生成或者是自动调整；三是无法用在一些非凸面形状的类运算中，也无法用在一些大小差别很大的类运算中；四是孤立点或噪声会影响到K-means聚类算法的运算结果；五是该类算法停止于局部最优解。

整体来看，“容易陷入局部最优解”正是模拟退火算法致力于解决的问题。

三、改进模拟退火算法在K-means聚类中的应用

基于模拟退火算法的K-means聚类方法的参数选择如下：

（一）目标函数。根据误差平方和准则函数JC，就能够将聚类进行划分，将其划分为离散距离和Js，而公式表示如下：

上述公式是这C个类的聚类中心，计算出样本的均值，计算公式如下：

在这里我们可以推算得到样本跟聚类中心的距离，其他指标的运算方式如下。

（二）初始温度。在设定初始温度的时候，应该设定一个相对较高的数值，这样对于一些运算得到的解都是可以接受的，但是若是温度设定过高也是没有意义的。最佳运算方法为，选择K-means聚类算法得到的结果作为本次研究的初始结果，而可以得到T0=Jd。但是需要注意的是，K-means聚类算法的K是用随机方法得出的。

（三）扰动方法。通过对之前求算获得的解进行扰动，可以产生新的解。一般来说，最佳方式就是K-means聚类算法单个样本扰动：将所有的聚类样本从所属于的类别中取出，将其放入到另一个类别中，形成一个全新的聚类方案。

（四）退火过程。具体做法为先乘以一个系数，也就是T（t）=aT（t-1），在上述公式中，a可能是介于0到1之间的任意值，而a数值越大，则退火时间也就越长，a数值越小，则退火时间也就越短；因此最好是选择a数值最大的退火方案，这样得到的数值解是我们需要的解。

改进K-means聚类算法的过程如下：

1.使用K-means聚类算法进行聚类分析，得到一系列的结果，将这个结果当作初始解，这样可以得到目标函数值。

2.将本次运算中的温度初始化成为目标函数值。

3.任意选择温度t，反复进行4-6步的运算操作，直到得到的温度低于某个给定数值为止，终止4-6步的运算操作，进行第七步运算。

4.因为聚类状态是在某个范围内进行波动的，将样本从某一类转移到另一类，是可以推算得到目标函数的。

5.计算两个函数之间的差值。

6.根据该算法的接受规则，若是差值≤0，则认为新算出来的数值是可以接受的；否则新算出来的数值是否可以接受以概率p来接受，并且返回到运算的第三步。

7.结束运算。

算法描述如下：

输入：x={x1，x2，…，xi}，y j =（y1，y2，…，yi）属于R50，聚类个数N

输出：最优的聚类划分的聚类中心S={a1，a2，…，aN}

1 初始化：

T0=Jd；

PN=Random_partition（x）； //随机划分x

Purity（Ω，C） object = Purity（Ω，C）（PN）； // Purity（Ω，C） object 为算法的评价函数，具体计算方法详见5.4节。

S=a（PN）；

Purity（Ω，C）best= Purity（Ω，C）object； // Purity（Ω，C）best为搜索中最优解的目标函数的取值。

2 改进模拟退火算法获取初始聚类中心：

While（100*n>0）

Begin

for（loop=N；loop>=1；loop--）

begin

num=0；

while（num

Begin

选取离聚类中心最远的实体，重新划分，得到新的PN

S=a（PN）； //S是模拟退火算法搜索过程中搜索到的聚类中心；

Purity（Ω，C） object = Purity（Ω，C）（PN）；

Δf= Purity（Ω，C） object- Purity（Ω，C） object；

if（Δf>0）

{ PN =PN；

Purity（Ω，C） object = Purity（Ω，C）（PN）；

S=S；

if（Purity（Ω，C）best> Purity（Ω，C）object））{ num=0；}

else{ num++；}}

else

{ if（random[0，1]<=min（1，exp[-（Δf）/ T0]））

{ PN =PN； S=S；}}

End

End

T（t） = a T（t-1）； //退火過程

End

3 Pk=K-means（x，S，k）； //运行K-means

S=a（Pk）； //更新聚类中心

改进模拟退火算法共有三个循环，第一层循环是模拟退火降温过程；中间循环是使用变换规则产生新解；最内层循环是维持初始数据的稳定。此算法将采用随机插入法产生新解，以概率的方式接受较差的解，从而能够跳出局部最优解，获得全局近似的最优解，从而得到的初始聚类中心接近于最优的聚类中心。再将此初始聚类中心进行聚类进行划分，克服了初始阶段K-means的盲目性，解决了K-means算法初始聚类中心敏感性问题，同时减少了迭代次数，提高了效率。而且模拟退火阶段属于横向搜索，会得到相对较优的聚类划分，对收敛标准要求较低，减少了时间复杂度；K-means算法阶段属于纵向搜索，容易得到最优的聚类划分，但收敛标准要求较高。利用模拟退火算法得到的初始聚类中心接近最优的聚类划分，需要较少的迭代次数就能收敛，同时降低了K-means算法的时间复杂度。

四、实验

（一）实验环境。硬件环境：CPU为P4 2.4GHz，内存为8GB，软件Matlab7.0。数据采用KDD cup_99。

（二）学生成绩数据描述。本实验中进行运算的数据来自广西政法管理干部学院的教务系统，只选择了信息工程系学生成绩。将学生成绩数据集分为150组，信息工程系总共有2个专业，这两个专业一个是司法信息专业，还有一个是计算机网络专业。平均每个专业有50个样本，计算统计的四门学科为：C语言、VB、JAVAR，VB+SQL。为了方便数据处理，本次运算的满分为10分。

表1 数据集截取片段示意图

专业 C VB JAVA VB+SQL

司法信息 6.2 8.2 5.5 3.0

司法信息 6.9 6.3 5.8 3.6

司法信息 4.8 7.3 4.2 3.6

司法信息 7.0 7.3 7.2 5.2

计算机网路 6.4 7.3 6.8 6.2

计算机网络 6.9 6.8 7.2 6.2

计算机网络 6.3 7.3 8.3 7.5

计算机网路 7.1 6.0 7.8 6.5

计算机网络 8.2 6.8 8.0 7.3

（三）改进K-means聚类解决学生成绩挖掘问题的必要性。整体来看，对学生的成绩处理比较容易，使用传统的K-means聚类方法就能够直接运算得到结论，但是实际运算的时候发现并非如此，主要归结为如下原因：

1.传统的K-means聚类方法中，初始值非常重要，但是要计算学生成绩则很难找到一种合适的初始值选取方法。若是选择的初始值数值有偏差的话，则很难通过传统的K-means聚类方法得到最优解，计算结果跟我们需要的存在差距。

2.因为学生的考试成绩呈现出连续分布的规律，成绩跨度大，样本上数量多，使用传统的K-means聚类方法难以分析这些数据。

3.虽然学生成绩信息是很直观，但是如何提取有用信息其实不是很容易。因为每一类学生中都存在着至少一名学生，这些学生的成绩有可能很好，也有可能很差，在而分析成绩的好坏不属于唯一信息。

上述实验结果可以帮助我们印证本文的分析结论：传统的K-means聚类方法分析学生的数据能力较差，分析结果不是很理想，因此使用改進K-means聚类算法能够提高结果的准确性，对我们分析学生成绩数据很有帮助，同时能够克服局部最优值的影响，从而更加接近全局最优解。

（四）算法评价标准。本文从多个角度作为切入点，来探讨改进K-means聚类算法的质量，首先我们使用Purity方法评估改进K-means聚类算法的正确率。

Purity方法是一种效率高、运算简单的方法，其运算理念如下：

这里的含义是改进K-means聚类算法的聚类集合，的含义是第k个聚类集合。而代表的是改进K-means聚类算法的样本集合，Cj代表的是第j个样本。上述体系中，N代表的是样本总数。

比如，我们计算得到的最优解数值为，而系统输出的聚类结果为，这样推算得到的分类正确的个体数值为1、2、5、7、8，这样可以推算得到正确率为（5/8=）62.5%。

Purity方法的优点在于操作方便，其数值在0-100%之间波动：若是结果完全错误，则Purity方法数值为0；若是结果完全正确，则Purity方法数值为100%。因此，Purity方法得出的结果简单明了，方便将这些结果进行比较，但是Purity方法的缺陷也是很明显的，使用该种方法聚类比较分散，因此得到的Purity数值一般都比较高，比如本次样本中的学生成绩，若是使用Purity方法还是比较可靠的。

其次，我们还得到了适应度函数Min-Jd，能够看出系统的收敛性是多少。

此外，使用收敛曲线衡量收敛速度。曲线比较陡峭，则表示系统的收敛速度也就越好，计算效果也越好。

（五）实验结果及结论。在分析学生成绩之前，现将学生的成绩按照考试科目分为若干个类簇，接着使用模拟退火的K-means聚类算法提高算法的稳定性，归纳出每个学科的特点，这样有利于提高运算效率，还有利于提高运算结果的正确率。

在该类方法中，T0设置为Jd，而a=0.99。

表2 两种算法数值对比结果

聚类算法 聚类正确率（Purity） Min-Jd

传统K-means算法 64.0000% 142.5174

模拟退火K-means 77.5000% 113.1462

其正确率和Min-Jd结果如表2。

图1 两种K-means算法聚类正确率对比

图2 两种算法的适应度函数对比

经过上述分析我们发现，传统的K-means算法效果不是很好，正确率不高，而使用了改进的K-means算法之后，正确率提高到了77.5%，Min-Jd从约142.5降到了约113.1。

为了更好地评估这两种算法的效果，我们绘制了收敛曲线，用来评估两种算法的科学性。

图3 两种聚类方法的收敛曲线对比

从收敛效果曲线我们发现，两种算法中，模拟退火的K-means聚类算法收敛性要更好一些。

着眼于学生成绩信息的挖掘，在实际学生成绩信息数据评估中，使用模拟退火的K-means聚类算法进行聚类。仿真实验采用实际的学生成绩数据信息。不同程度上改进了传统K-means聚类方法的性能，而且基于模拟退火的K-means聚类算法优势也很明显：运算简单，适用范围广。

五、小结

本文对模拟退火算法和K-means聚类方法进行了详细的总结，并归纳总结了所有关于模拟退火的K-means聚类算法的资料，提出了现有研究的不足，并根据现实提出了改进措施。本次研究的模拟退火的K-means聚类算法要比传统算法更有优势，科学合理，适用范围更广，能够科学地体现出学生对课程的掌握程度，教师也可以根据评估结果，查看学生的薄弱点，改进教学方法。

但是，随着大数据时代的到来，云计算登上了历史的舞台，而计算功能也变得日益强大，在这种运算背景下，支持种群规模也变得日益强大，迭代次数也提高了很多。在运算能力越来越强的时代中，如何结合云技术、并行计算技术，设计出一个合理的聚类方法，让数据运算能力大大提高，解决我们切实需要的问题，是未来研究发展趋势，也是现在讨论的最热门的一个话题。

【参考文献】

[1]梅方权.中国农业信息化建设的前景展望[J].计算机与农业，1997（3）

[2]Wikipedia：K-means clustering[EB/OL].https：//en.wikipedia.org/wiki/K-means_clustering

[3]杨忠明，黄道，王行愚.基于模拟退火的动态聚类算法[J].控制与决策，1997（12）

[4]李健，宋立新.模拟退火改进 K 均值算法在镜头聚类中的应用[J].哈尔滨理工大学学报，2010（6）

[5]陈慧萍，贺会景，陈岚峰，等.基于模拟退火思想的优化 k-means 算法[J].河海大学常州分校学报，2006（4）

[6]陈明，王行风，韩冰，等.基于模拟退火的k-means分类算法优化研究[EB/OL].（2011-08-27）[2016-01-01]. http：//www.paper.edu.cn/html/releasepaper/2011/08/277/

[7]史峰，王辉，胡斐，等.智能算法[M].北京：北京航空航天大学出版社，2011

[8]刘剑.改进聚类分析算法及其在成绩分析中的应用研究[D].大连：大连交通大学，2008

[9]Anil K J.Data clustering：50 years beyond K-Means[J].Pattern Recognition Letters，2010（8）

[10]刘寒梅，张鹏.基于模拟退火算法对 K-means 聚类算法的优化[J].中国西部科技，2013（6）

[11]胡艳维，秦拯，张忠志.基于模拟退火与 K 均值聚类的入侵检测算法[J].计算机科学，2010（6）

[12]李健，宋立新.模拟退火改进 K 均值算法在镜头聚類中的应用[J]，哈尔滨理工大学学报，2010（6）

[13]李梓，于海涛，贾美娟.基于改进模拟退火的优化K-means算法[J]，计算机工程与应用，2012（24）

[14]陶术松，陈兴蜀，尹学渊.基于数据挖掘的未知帧结构识别[J].四川大学学报（工程科学版），2014（S1）

【基金项目】广西重点研发计划项目“基于北斗多功能信息采集与监控终端的智能物流管理系统研发”（桂科AB16380351）；2016年广西教育厅教学改革立项项目“基于翻转课堂的C语言教学探索与研究”（GXGZJG2016B097）；国家自然基金：广西职业教育教学改革立项项目“基于增强现实与3D打印信息技术的职业教育人机互动教学模式研究”（JG15B09）

【作者简介】左倪娜（1983— ），女，硕士，广西政法管理干部学院信息工程系讲师，研究方向：计算机软件编程及大数据分析。

（责编 王 一）