加权k-means算法及其在高校贫困生判别中的应用

□张 轶 高雪冬 郭亚伟 赵丙贺

党中央、国务院高度重视家庭经济困难学生资助工作。尤其是党的十八大以来，国家对高校贫困生的资助越来越多。不断建立健全家庭经济困难学生资助政策体系，是实施科教兴国和人才强国战略，优化教育结构，促进教育公平和社会公正的有效手段。目前，高校贫困生的判别方式为人工判别，并不存在统一标准，基本过程是首先由学生主动填写《高等学校学生及家庭情况调查表》，再出示相关困难证明，如《最低生活保障证》《特困证》等。其次，根据辅导员和班级内部同宿舍室友组成判别小组进行判别。这样的判别方式难免存在信息错误、虚假的问题，造成贫困生判别与实际情况误差较大。另外，由于一些同学自尊心等缘由，即便是家庭情况比较艰难但也不愿意去申报改善自己的生活条件。

大数据[1]时代的到来，学生消费的财务状况反映在生活中的方方面面，如日常使用校园卡就餐消费，网购次数以及金额，奢侈品使用情况等。如果对这些数据进行分析和挖掘，将有助于分析和识别贫困生。但是当前存在诸多方法，如分类方法[2～3]和概念漂移检测的方法[4]，这些方法需要预先标定大量训练数据，然后训练出分类器，最后才能实现对其他数据进行分类。对于贫困生判别问题而言，预先获得大量标注数据难度较大，因此分类方法不适宜求解本文问题。序列模式挖掘方法[5]是数据挖掘中一类重要的分析方法[6～7]，可以通过挖掘负序列的行为特征[8]，进而实现负样本识别。然而这同样需要预先标定大量数据，因而难以取得良好的效果。

聚类分析作为一种无监督学习方法[9]，无需预先标定数据，是数据挖掘[10]中常用的方法之一。k-means作为最常用的基于划分的聚类算法，具有原理简单、收敛速度快、能有效处理大量数据等优点。但其也存在一些问题，如：算法对初始中心点的选取较为敏感，当初始中心点选取不合理时，算法容易陷入局部最优解；
k值需要人为给定；
算法没有考虑样本各维特征的权重。针对以上问题，已有学者提出了一系列的改进。汪中等人[11]提出基于密度的初始中心点选取方法，但在密度分布较为均匀的数据集中效果不佳。郭靖[12]提出基于变异系数的加权欧式距离方法，从而提高了聚类精度，但稳定度不佳。Xiong等人[13]提出基于平均密度与最远距离的初始中心点选取方法，有效提高了聚类稳定度，但聚类精度不高。这些研究或存在迭代收敛速度慢，聚类结果不稳定，或存在聚类精度不高等问题。

为了增加聚类的稳定度，提高聚类结果的精度，本文采用将基于变异系数的加权权重与基于平均密度与最远距离的初始中心点选取算法结合，形成基于平均密度与最远距离的变异加权k-means算法(以下简称DDCVK-means算法)。将改进后的算法应用在UCI标准数据集中多种数据集上进行聚类，实验结果表明，本文算法无论是精确度还是聚类稳定度，都有了一定程度的提高，从而验证了本文方法的有效性，进而实现了贫困生判别。

传统的k-means聚类算法是基于划分的聚类算法，给定样本集D={X1,X2,…,Xm}，k-means的任务是将样本集D中的样本划分为k个不相交的类簇，使类内间距尽可能小，类间间距尽可能大，从而使所得的划分的误差平方和SSE(sum of squared errors)最小化。假设聚类分析后产生的类别集合为C={C1,C2,…,Ck}，则SSE定义如下：

(1)

其中ck为簇Ck心点，计算方法为：

(2)

k-means算法的任务是找到能最小化SSE的聚类结果，这是一个NP难问题[14]。k-means算法[15]的基本流程为：

算法1 传统k-means算法

输入:样本集D，聚类个数k。

输出:k个聚类中心点，k个划分。

a)随机选取k个样本点作为初始的中心点。

b)计算每个样本点与各个中心点之间的距离，将该点并入到与其距离最近的中心点所属的类簇中。

c)根据公式(2)更新各类簇的中心点。

d)重复(2)，(3)两步，直至中心点不再发生变化或者达到指定的迭代次数。

e)输出k个聚类中心点以及k个划分。

本文算法在前人的基础上进行研究改进，提出DDCVK-means算法。该算法分三个阶段，第一个阶段是计算各个特征的权重；
第二个阶段是确定初始聚类中心；
第三个阶段是聚类过程，并对孤立点做出处理。设样本数据集为X={xi|xi∈Rp,i=1,2,…,n}，p是维数，wj为各维特征权重。

(一)特征的权重。在特征权重计算阶段，本文采用基于变异系数的欧式距离实现特征加权。

在统计学中，用来描述数据离散程度的指标有：标准差(Standard Deviation)，方差(Variance)，变异系数(Coefficient of Variation)，平均绝对偏差(Mean Absolute Deviation)。文献[12]所做的研究指出，变异系数不但能反映数据的离散程度，还能消除测量尺度和量纲的影响，故采用变异系数作为加权系数。

变异系数(Coefficient of Variation)的定义为标准差与平均数的比。定义样本中各维特征加权系数为w1,w2,…,wj为样本数据维度)。

则加权系数为:

(3)

(二)初始聚类中心。在确定初始聚类中心阶段，本文采用基于平均密度与最远距离的选取方法实现初始聚类中心点的选取。

初始中心点选取首先需要计算所有样本点两两之间的加权欧式距离，本文采用加权欧式距离进行计算，其计算公式如下：

(4)

然后根据公式(5)计算出平均距离。

(5)

再根据公式(6)计算出所有样本点的密度参数。

(6)

(7)

求得平均密度后，便可根据孤立点的判定方法，将样本集中满足不等式(8)的样本点放入孤立点集N中。

Dens(xi)<α×AverDens(D)

(8)

在除去孤立点的样本集S中，选取密度最大的点作为第一个初始聚类中心，然后在大于平均密度β倍的点集中选取距离初始聚类中心点集最远的点作为下一个聚类中心，划入初始聚类中心点集合。点xi合的距离如公式(9)所示：

d(xi,C)=min(d(xi,xj),xj∈C)

(9)

即将点与集合的距离定义为点与集合中的点的最近距离。

(三)本文算法描述。与传统k-means算法相比，本算法先计算了各维特征的权重，在后续的过程中所有的距离计算上均使用加权的欧式距离，改进了传统k-means算法权重相同这一不足；
之后通过计算得出初始中心点，改进了传统k-means算法的不稳定性这一不足；
算法还对孤立点进行处理，有效减小了孤立点对聚类结果的影响，最后将孤立点划入最近的类簇中，得出最终划分。综合以上过程，下面给出本文算法描述：

算法2 本文算法

输入:样本集D，聚类个数k，参数α，参数β。

输出:k个聚类中心点，k个划分。

a)根据3.1节的内容计算各维特征的权重。

b)根据3.2节的内容计算出k个初始聚类中心、孤立点集N和除去孤立点的样本集S。

c)根据加权欧式距离公式(4)计算样本S中每个样本点与各个中心点之间的距离，将该点并入到与其距离最近的中心点所属的类簇中。

d)根据公式(2)更新各类簇的中心点。

e)重复c)，d)两步，直至中心点不再发生变化或者达到指定的迭代次数。

f)计算出当前聚类中心点，将孤立点集N中的点划入与之距离最近的中心点所在的类簇中。

g)输出k个聚类中心点以及k个划分。

(一)标准数据集验证与分析。本文将文献[13]中的算法称为DDK-means，将文献[12]中的算法称为CVK-means算法。为了验证本文DDCVK-means算法的性能，我们选取了传统k-means算法、k-means++算法、DDK-means算法和CVK-means算法进行对比，实验数据选取了UCI中的Iris、Seeds、Wine、Vertebral Column和Wholesale Customers数据集。表1给出了本文算法及对比算法在五个数据集下执行若干次的最高精确度、最低精确度和平均精确度。

表1 聚类算法对比

从表1可以看出，除了本文提出的算法，其他的聚类算法在精度或稳定度上都稍有欠缺；
例如k-means算法在Iris数据集平均准确率仅为81.44%，而这是所有算法中聚类效果最差的，其他四种数据集也有类似现象，造成这样现象的原因是传统k-means算法聚类中心点的选取方式为随机选取，受孤立点的影响较大，容易陷入局部最优解，且样本各维特征权重相同；
改进的k-means++算法在五种数据集上的平均精度与最高精度非常接进，说明其稳定度大有提高，但由于其存在随机因素，所以仍然存在不稳定现象，且精度不高；
CVK-means算法在五种数据集上的最高精度都有了一定程度的提高，在Iris数据集上的最高精度达到了96%，但因为其初始聚类中心点的选取为随机选取，故造成最低精度只有50.67%的现象，稳定度差；
DDK-means算法通过计算获得初始中心点，故聚类结果相同，稳定度好，但是相同的权重使得其精度不高。本文DDCVK-means算法取得了最好的效果。由于本文算法是计算产生初始聚类中心，而非随机生成初始聚类中心，因此本文算法聚类结果是稳定不变的。更为重要的是，从表1可以看出，本文算法聚类效果最好，例如在Iris数据集上，本文算法的平均准确率取得了96.00%的效果，这是优于其他所有方法的，并且其他四种数据集均呈现同样的结果。造成这样现象的原因是本文算法结合了DDK-means算法和CVK-means算法的优点，具有较高的聚类精度和稳定度。

(二)贫困学生识别结果与分析。使用DDCVK-means算法，选取某大学的学生为样本进行实验。

图1 当前学生经济情况

1.当前贫困生现状。首先对数据进行抓取以及预处理，即从现有数据库找到样本学生在校期间的消费情况，主要包括在食堂消费的次数以及单次金额。图1展现的是样本学生当前平均消费金额，消费次数与登记在贫困生库中学生的贫困程度散点图。图中“+”代表家庭经济条件正常的学生，“×”代表家庭经济条件困难的学生，其中绿色为一般贫困、蓝色为贫困、黄色为特殊贫困。从图上这些散点来看，学生的分布较为杂乱，不同贫困程度的学生的分布与其在食堂消费的次数和平均金额关系不明显，表明当前的贫困生很有可能存在假贫困。样本数据也没有明显的分簇，用传统的k-means算法很有可能会陷入局部最优解，聚类精度不高等问题中。

2.聚类结果。综合考虑学生的消费能力和学习成绩，最终使用如下属性字段进行聚类。

表2 聚类属性字段

通过多次试验，当k为3时，聚类结果与贫困生资助比例更为贴切，且与学生真实消费情况拟合度更高。故采用k的值为3进行实验。

聚类后得到如图2的结果。

图2 基于消费数据的聚类结果

据经验数据将类1划分为贫困学生；
类2平均消费金额较高，且在食堂消费次数少，故将类2划分为富裕学生，类3为一般学生。

为了验证平均消费金额-消费次数可以有效地用于识别贫困情况，而其他数据难以正确识别家庭情况是否贫困问题，为此我们又选择了专业排名比率-GPA信息。如图3所示。

图3 基于GPA数据的聚类结果

图3中类1贫困学生，类2富裕学生和类3一般学生混合分布，发现学生成绩和家庭贫困情况并无明显相关性，故学习成绩并不能反映学生家庭贫困状况，更多的还是由学生的消费水平直接反映。

3.结果分析。实验随机选取10名学生，通过当面交谈，咨询监护人，咨询室友等方式调查其家庭经济的真实状况，并与聚类结果以及当前记录在贫困生库的情况进行对比，对比结果见表3。

表3 实验结果验证

聚类结果将学生分为3类：贫困、一般、富裕。而贫困生又分为3类：一般贫困、贫困和特殊贫困。故三类贫困生都应在聚类所得到的贫困类簇中，也就是类1中。忽略不同贫困等级的区别，10个学生中真实贫困状况和记录在贫困生库中的情况不符的有学生1、2、9。而真实贫困情况和聚类结果不符的仅有学生7。

实验表明聚类结果能将家庭贫困的学生较好地区分出来，通过随机调查的结果显示聚类算法的准确度大约为90%。实验误差可能是由于部分贫困生是在外实习无法进入食堂点餐、学校周边小吃店或外卖价格较低、自身生活习惯、体重等因素造成。而现有的贫困生库中不符合实际情况的信息大约为30%，不符合情况较为严重，一方面可能是因为存在虚假申报，另一方面可能是部分富裕家庭孩子由于平时生活比较节俭，错被认为是贫困家庭。若评选贫困生时使用本实验所提供的方法作为参考，则可提高贫困生判别精准度。

因此，根据研究统计和分析结果，推测出识别贫困生的两个步骤：第一，经过算法识别满足两种消费特征，即不仅每月在食堂的就餐次数高，而且平均消费低。第二，在通过算法识别贫困生后，为进一步提高准确性，需要通过得到周围人的证明确认。

研究通过改进后的算法，基本能达到提高识别贫困生的准确率目的。具体而言，文中针对传统k-means对聚类中心点敏感，样本各维特征权重相同这两点进行改进，结合基于平均密度与最远距离的初始聚类中心点选取方法和基于变异系数的加权方法提出了DDCVK-means算法。并将本文算法与多种算法进行对比，结果显示本文DDCVK-means算法提高了聚类精度和稳定度。

以高校学生校园食堂消费数据为基础，本文研究了如何根据适当的判断标准通过算法识别进而识别、确认贫困生名单以及在贫困生中找出假贫困生的办法，并且提出了采用加权k-means算法应用于贫困生识别的新思路。在研究过程中，通过判别贫困生以及识别贫困生等级，发现了贫困生在消费行为上较为鲜明的特点。比如一些学生为了省午饭费用，会在早上多买一些食物；
在校外的消费费用比在校内更低；
几乎很少消费含蛋白质较高的鱼肉类以及补充维生素的水果类。这类同学往往对伙食费控制得非常严格，长期以来，很可能对同学的身体发育、心理健康、学业成就等都产生不良影响。因此，学校可以定期通过算法估算来对这些同学实施经济补助，进而引导他们逐步改变消费习惯。

对比传统的人工判别以及传统k-means算法，改进后的算法能够更有效应用于贫困生判别上，通过对校园卡日常消费数据进行聚类，分析学生的贫困程度，极大缩小了学校调查认证的工作量，维护了贫困同学的自尊心，并且能够帮助到一批由于自尊心或面子问题不愿申请的贫困同学，最终达到辅助学校科学公平地进行贫困生资助工作的目的。

在本文的算法中，尽管对数据各维特征进行变异系数加权会使聚类结果精确度提高，但由于高校贫困生认定是一个庞大的系统工作，因而可能并不适用于所有样本数据，在今后的工作中，将对加权算法做进一步研究，大量采集多维度、多方面的高质量数据，以期望获得更适用的样本数据，从而适用更恰当的科学评判方法，让更多真正需要资助的大学生享受到资助政策的利益。