MD-KNN算法在高校精准资助中的应用

李 博，李 霞，张 晓，王艳秋，李 恒，张 勇，凌玉龙

(1.西北工业大学 计算机学院，陕西 西安 710129；2.西北工业大学 工信部大数据存储与管理重点实验室，陕西 西安 710129；3.西北工业大学 学生资助服务中心，陕西 西安 710129)

0 引 言

学生群体是社会中非常重要的群体，并且对社会的发展有重大影响，因此对学生行为的分析有很大的意义。但是由于学生群体是一个相似度比较高的群体，目前针对学生群体的数据挖掘算法还比较少。贫困学生的筛选与资助是很多高校的一项重要事务，通过分析学生的家庭情况、消费和学习行为，可以找到需要资助的贫困学生群体，还可以预防甄别生活规律有异常的学生，从而进行相应的帮助[1-5]。

基于马氏距离的KNN算法(Mahalanobis distance k-nearest neighbor algorithm，MD-KNN，马氏KNN)是一种改进的KNN算法。相比于传统的KNN算法，MD-KNN算法采用了马氏距离，可以更好地处理一些非数值型数据，比如：生源地、性别等因素。文中采用该算法，以西安某高校在校学生数据为样本，进行实验分析，探究MD-KNN算法在贫困学生资助工作中的效果。在通过MD-KNN算法筛选得到拟贫困学生名单后，与实际筛选名单进行对比，分析两者的匹配率，以及学生的消费水平。在分析学生数据时发现：贫困学生的在校就餐次数与就餐天数会有一定的规律，并通过实验分析验证了这一观点。此外还发现，学生吃早餐情况也与该生的学习成绩之间有正相关的联系[6-9]。

1 研究现状

KNN分类算法是一种经典且应用广泛的数据挖掘算法。随着科学技术的发展，为了适应一些新问题、新背景，在传统KNN算法的基础上也不断提出新的改进方法，比如：AHP-KNN(analytic hierarchy process KNN)、FCD-KNN(feature correlation difference KNN)等。MD-KNN算法是在原先KNN算法的基础上，采用马氏距离(Mahalanobis distance)来计算样本之间的距离，因此MD-KNN算法可以更多地考虑非数值型因素，从而提升算法的精度。根据在西安某高校收集的学生数据，其中以数值型数据为主，如经济消费数据、学习成绩、图书馆入馆记录、借书记录等，也有部分非数值数据，如生源地、性别、是否残疾单亲等。文中选用MD-KNN算法进行学生行为的分析，探索学生行为的规律，并筛选需要资助的学生，以及行为有异常的学生[10-12]。

国内外对于学生群体的行为分析由来已久，20世纪就有人开始进行研究。随着时代的发展，学生的行为也变得复杂化，但是学生群体内部依然具有较高的相似性。如何对贫困学生进行精确资助，以及分析学生行为，提高学生学习生活质量，保障学生生活安全，成为了各个高校关心的热点问题之一。随着大数据技术的发展，从2014年起，很多团队尝试将大数据分析与精准资助相结合，如西北工业大学学生资助服务中心的李霞老师团队。但是现有大部分高校的精准资助系统的算法具有局限性，过于主观，某些高校的贫困学生通过老师或学生人工筛选推荐，缺乏科学的理论分析。文中采用MD-KNN算法来进行学生行为的分析，从大数据角度探究学生行为，推动困难学生精准资助领域的发展[13-15]。

2 理论介绍

2.1 MD-KNN算法介绍

马氏距离是由印度统计学家马哈拉诺比斯(P. C. Mahalanobis)提出的，表示数据的协方差距离[14-15]。经典的KNN算法采用的是欧氏距离，欧氏距离单纯地考虑数值上的距离，但是当前在很多的实际场景中需要考虑非数值型的因素，并且很多因素之间并不是相互独立的。马氏距离认为属性之间是存在联系的，比如身高与鞋码之间就是存在联系的，所以在距离计算公式中引入了协方差。而如果是两个完全独立的变量，其协方差是0，在这种情况下就变成了欧氏距离。对于一个均值为μ=(μ1,μ2,…,μp)T，协方差矩阵为Σ的多变量向量x=(x1,x2,…,xp)T，其马氏距离为：

(1)

其中，T是指矩阵的转置。

在马氏距离的设计中，某一微小变量的作用可以被放大，这在某些应用环境中会导致过度拟合的状况。但不同于其他数据，学生群体是一个具有高相似性的群体，大部分成员内部之间生活作息规律比较相似，就餐时间、地点相对固定且有规律，不同学生样本的行为也是大致相似。而如果通过分析发现一些奇异点，或者某些方面存在异常，则需要学校的额外注意。因此文中根据马氏距离的这一特点，认为采用马氏距离的MD-KNN算法更为适合学生数据分析。

2.2 学生在食堂就餐天数与就餐次数的分析

马氏距离考虑了变量之间的相互联系，文中分析这一设计思想，着重分析了贫困学生在学校食堂的就餐次数与就餐天数之间的联系。通常而言，经济困难的在校大学生相比于经济富裕的在校大学生，其娱乐时间和消费水平会较低。而很多大学食堂会有补助，食堂饭菜的价格会略低于学校外饭店的价格。因此，潜在的困难大学生的在校天数和在食堂就餐次数可能更多。文中根据在校学生在学校食堂刷卡产生的消费记录进行分析，列出以下公式：

N=(X+Y)/Z

(2)

其中，X和Y分别表示午餐数和晚餐数，Z是根据该学生的就餐情况(午餐和晚餐)，推断出的该学生在校天数，再乘以2得到的数字(该生在食堂应该就餐次数)。最终N越大说明该学生在校天数以及食堂就餐数之间的比例高，该生在校食堂就餐的频率高，也更有可能是经济较为困难的同学。理论上，X和Y可以为不超过在校天数任意大的整数，也可以为0。文中默认设置每位学生每天只吃一顿午餐(晚餐)，即：某位学生在中午时段有多次刷卡记录(比如分开打菜和米饭)，文中也会将金额累计，认为是一次消费记录。

图1 学生在食堂就餐天数与就餐次数对比

根据式(2)，由每个学生在一段时间内的就餐情况得到N值(有对应的X+Y，Z)。所有学生消费行为所对应的点，都会落在阴影区域里，即：每个样本点得到N值的最大值不会超过1，最小值不会小于0.5,(0.5≤N≤1)。如图1所示，文中取一个分析区间为30天，则应该就餐数目为60顿(午餐和晚餐)。可以分析这条线上的A、B两点，A点是最理想状态，该生在校30天，就餐60顿，N=1。而B点，该生就餐30次，在校30天，N=0.5，这名同学的情况很极端，他是每天只吃午餐或晚餐，连续30天(比如连续30天只吃午餐)，则也可以推导出其在校30天，但是N=0.5。如果一位同学连续多天均不在食堂消费，则X与Y都会相应减少，他的数据点会位于该阴影区域的左下角部分，趋向于0点。

再沿平行x轴方向分析线B，线B上有两个点，B和C，这两点都是就餐次数为30次，但是由于点B的行为，他的在校天数是点C的两倍(点C的在校天数是15天)。但是分析推断样本B点学生的行为更有规律。通过进一步的分析，推测在学校内消费次数越多和越平均的学生样本更有可能是需要资助的贫困学生。当加入早餐的因素时，图1的变化如图2所示。

图2 学生在食堂就餐天数与就餐次数对比(含早餐)

此时Z的含义为：根据早中晚餐实际就餐次数推算出来的该生实际在校天数，再乘以3，得到的该生应当就餐次数。根据分析，经济困难的学生的数据点更有可能落在阴影区域的右上角区域范围(所有学生的数据点都会集中在这个阴影三角形区域)，即贫困学生的在校食堂消费次数更多，消费天数更多，消费次数也更均匀、更规律。

3 实验分析

文中搭建Eclipse+Tomcat实验环境，使用Java语言编程，以西安某高校2016和2017级硕士研究生，2012至2017级博士研究生在2017年11月至2018年4月(约180天)的学生行为数据(主要是食堂消费数据、图书馆进出信息、学习成绩等数据)进行实验分析。其中男生7 636人(约占68.36%)，女生3 534人(约占31.64%)，共计11 170人。该高校有2个校区，A校区位于西安大唐西市附近，整体消费水平较高；B校区位于郊区，物价相对较低；且该高校不同学院位于不同校区。在进行数据分析时，将校区、学院等差异考虑在内。针对所研究的问题，设计了如下三个实验：(1)使用该校实际贫困生名单的实际生活消费数据，对前述学生食堂就餐次数与在校天数的分析进行相应的验证；(2)使用MD-KNN算法，对该高校学生进行贫困学生的筛选，然后比较与已有的，由人工认定贫困学生的名单的差异；(3)为了更好地对比实验(2)和人工认定贫困学生的名单，将这两份名单中的学生进行经济消费水平的对比。

3.1 关于经济困难学生在食堂就餐次数、就餐天数的分析

通过分析，经济困难学生会更多地在校内食堂就餐，因此其校内食堂就餐次数与就餐天数会相对较高，获得资助的同学其数据实验结果会落在图1所示三角区域的右上角部分。文中通过采集西安某高校人工认定的200多名贫困学生在2017年11月至2018年4月间，学校食堂的早餐、午餐、晚餐的就餐情况的数据进行验证，结果如图3所示。

图3 贫困学生在食堂就餐天数与就餐次数对比图

如图3所示，该校人工筛选的贫困学生就餐情况是符合文中分析的，学生在食堂的就餐次数与就餐天数两种因素与学生的贫困与否是一种正相关的条件，贫困学生相比于非贫困学生会在学校食堂就餐次数更多，这也为今后贫困学生资助工作提供了一种新的参考因素。

3.2 MD-KNN算法的实验分析

根据收集到的实验样本数据，使用MD-KNN算法进行分析，设置经济、消费、学习、生源地、是否有生源地贫困证明、是否残疾等二十余项标签，然后进行迭代的实验分析。在得到初步的贫困学生名单后，再在结果中设置筛选学生名单条件，即：拟评选人数、助学金等级等，这样就得到了由MD-KNN算法筛选推荐的贫困学生名单，筛选出的部分学生名单见表1。将由MD-KNN算法筛选得到的名单与实际人工审核推荐的学生名单进行对比。两份名单的匹配率大致在50%左右，这一概率并不算高，但分析原因可能有两方面：(1)使用的MD-KNN算法或许还需要进行改进，以更好适应高校贫困学生筛选的应用环境；(2)人工筛选名单具有很大的不确定性，老师、学生很多情况下是通过申请表、平时的认知(甚至并不认识)来进行筛选推荐，人工筛选贫困学生也存在一些漏洞。因此通过实验3.3，对两份名单中的学生进行消费情况的分析。

表1 MD-KNN算法筛选得到的经济困难学生名单(部分)

3.3 MD-KNN算法与线下人工筛选名单的对比

针对3.2节实验分析的结果，对两份名单中的学生进行进一步的分析。还是以2017年11月至2018年4月之间的学生消费数据来进行对比，实验结果如图4所示。

图4 日均消费金额对比

通过对比发现，由文中筛选的学生名单的消费水平(图4)明显低于由学校提供的，由实际人员参与评审所得到的贫困学生名单，这就说明所设计的贫困学生筛选算法是有效的。虽然一些经济困难学生由于身体或疾病原因可能会有较高的消费数据，但总体而言，大部分经济困难的学生在学生群体中的消费数据应该是较低的。因此，MD-KNN算法在筛选困难学生的过程中是一种有效的算法，并值得进一步的分析研究。

4 结束语

学生群体是一个相似度较高的群体，具有很多共性，对学生群体进行行为分析，筛选出应该资助的贫困学生，是当前很多高校的一项重要事务。通过分析MD-KNN的特性，将其应用到贫困学生筛选资助的过程中，设置学生的属性标签、消费行为标签、学习行为标签(相同条件下最后考虑学习成绩)进行筛选，发现与实际得到的贫困学生名单相比，通过MD-KNN算法筛选出来的学生名单消费水平更低，有更高的精确度。同时发现，经济水平较低的学生的在校食堂消费天数与消费次数更高，以及学习成绩与吃早餐次数具有正相关的关系。因此该研究是有效的，有助于贫困学生资助工作的发展。