一种蚁群聚类优化算法在成绩管理中的应用

薛景

摘 要： 学生成绩是评价学生是否掌握好所学知识的重要指标。传统的方法是基于绝对分数的评价，这种方法存在一定的缺陷，不能充分反映学生原始成绩中蕴涵的信息。本文提出了一种蚁群聚类优化算法，并用于高职高专的信息技术课程成绩管理当中。旨在挖掘成绩背后的信息，供教学参考，教务支持。

关键词： 蚁群； 聚类分析； 成绩评价

中图分类号： TP391 文献标志码： A 文章编号： 1671-2153（2016）05-0095-03

1 问题提出

随着蚁群算法研究的不断深入，人们发现在某些方面采用蚁群模型进行聚类分析会更接近于实际的聚类问题。通过模拟蚁群的行为，人们提出了很多基于蚁群的聚类分析模型[1]。Lumer和Faieta将蚁群聚类的基本模型推广应用到数据分析，提出了LF算法[2]。作为蚁群聚类算法的标准算法，LF算法在很多领域得到了广泛的应用。

在传统的LF算法中，未搬运东西的蚂蚁碰到对象时会以某个概率拾起它，而带有对象的蚂蚁遇到空单元时会以某个概率放下它。拾起和放下行为均依赖于当前对象和其领域对象之间的相似度。数据对象在空间的分布状态将影响聚类结果[3]。

传统的LF算法中容易遇到以下问题：

（1）蚂蚁在二维平面上的运动是完全随机的，如果运动到无对象区域，则无太大意义；并且当蚁群规模较大时，对象很难在较短时间内找到合适的邻域，导致聚类效果不准确或不明显。

（2）该算法容易出现停滞现象，即迭代到了一定程度后，可能出现局部最优解，导致更合适的对象不能被拾起。

2 带有记忆的蚁群聚类算法

基于上述问题，本文提出了一种蚁群聚类优化算法。与传统LF算法的区别主要有以下两点。

区别之一是，通过建立“历史位置记忆库”，记录所有蚂蚁放下数据的位置，供所有的蚂蚁进行比较。初始时“历史位置记忆库”中内容为空，蚂蚁走完一步或经历一条完整路径后，要对记忆库进行更新处理。这样经过不断的迭代更新，蚁群最终会找到最优路径[4]。通过设置“历史位置记忆库”，可以减少蚂蚁运动中的随机性，从而达到缩短搜索时间，提高聚类效率的目的。

鉴于原函数中当对象Oi和Oj水平偏离很大时，d（Oi，Oj）不能很好的反映出真实的相似度，所以调整后函数中设置了参数μ，μ为全部对象欧氏空间距离的平均值，d（Oi，Oj）/μ则反映了对象Oi和Oj相对于总体空间距离的偏离程度。通过此调整，以期改进原函数中存在的问题。

改进后的算法流程图如图1所示。

改进后的算法描述如下：

输入：待聚类的数据集。

输出：聚类结果。

（1）初始化蚁群，蚂蚁数记为N，最大迭代次数记为M。

（2）将所有待聚类的数据随机分配到二维网格单位中。

（3）初始时，蚂蚁空载，随机选择一个数据对象，并初始化“历史位置记忆库”，置为空。

（4）For i=1，2，…，M

For j=1，2，…，N

计算数据的平均相似性：

以一只蚂蚁为例，计算拾起概率PP。若PP大于随机概率，则蚂蚁拾起数据，并将自身的状态记为负载；若PP小于随机概率，则随机选择另一个数据对象。将蚂蚁拾起的数据与“历史位置记忆库”中的数据进行比较，计算放下概率Pd，若Pd小于随机概率，则随机选择一个无数据的网格单位，继续判断若Pd小于随机概率，直至最终放下数据，更新“历史位置记忆库”，蚂蚁状态记为卸载。

如一个数据对象的邻域个数小于某个常数，则记为孤立点；否则，给该数据对象和其领域对象分配相同的聚类序列号。

3 实 验

学生成绩在整个教学管理活动中，起着很好的指示作用[5]。本文选择扬州市职业大学2015级105名学生的信息技术课程成绩进行聚类分析。该课程属于高职高专院校的公共课课程，考试采用机考，考试题型和分值设置如下：第一项，选择题和填空题50题，计50分；第二项，操作题，主要是WORD，EXCEL，POWERPOINT三个软件的实际操作，计50分，满分100分。部分数据样本如表1所示。

传统的学生成绩标准主要是根据分数线进行划分。90～100分为优秀，80～90分（不含90）为良好，70～80分（不含80）为中等，60～70分（不含70）为及格，0～60分（不含60）为不及格。

先将105学生的信息技术考试成绩作为数据样本，按照传统等级标准进行统计，结果转换成折线图，如图2所示。

由图2可以看出，成绩分布没有呈正态分布，优秀和良好比率较低，说明本次考试对学生而言难度较大。再将105名学生的成绩数据作为输入，使用改进的蚁群聚类算法进行聚类，进行多次聚类后，结果如表2所示。在表2的基础上，将最后的四类归并，归类后的统计结果，如图3所示。

根据图3的折线图可看出，学生成绩的分布基本呈正态分布趋势，即两头低，中间高，左右基本对称。这样的聚类模型更加符合实际情况。

4 结 论

本文在标准蚁群聚类算法的基础上，提出了优化算法。经实验验证，相对于传统的评价标准，改进后的聚类结果呈正态分布趋势，更符合实际的应用情况。聚类所得的评价结果，也可为教学人员制定有针对性的教学策略提供有利的依据。

参考文献：

[1] HOE KM，LAIWK，TAIT S. Homogenous ants for documents similarity modeling and categorization. Proceedings of the 3th International Workshop on Ant Algorithms[C]. LNCS，2002：256-261.

[2] WU B，SHI Z. A clustering algorithm based on swarm intelligence[A]//Proceedings IEEE international conferences on info-tech & info-net proceeding[C]. Beijing，2001：58-66.

[3] 姜云龙. 面向日志分类的蚁群聚类算法研究[D]. 上海：华东理工大学，2014.

[4] 段海滨. 蚁群算法原理及其应用[M]. 北京：科学出版社，2005：34-35.

[5] 周颖. 基于蚁群算法的聚类分析在学生成绩中的研究[D]. 南昌：南昌大学，2015.

Abstract： Student achievement is an important indicator to evaluate whether students master the knowledge they have learned. Traditional approach is based on the absolute scores of the evaluation， this method has some shortcomings， does not fully reflect the achievements of students in the original implication of information. This paper presents an ant colony clustering algorithm， which is used in the management of information technology course in higher vocational colleges.Aims to dig the information behind the results for teaching reference， academic support.

Keywords： cluster analysis； ant algorithm； performance evaluation

（责任编辑：徐兴华）