摘要：准确认定贫困学生资格是关系到资助资源流向和教育公平的实现，在教学管理中，校园卡消费数据的准确聚类对于贫困生评定工作具有重要参考价值。近邻传播对于离群点不敏感，也能保持模型的较好鲁棒性的特点。将近邻传播算法应用到校园卡消费数据的聚类，实现学生消费能力的分类。实例分析的结果表明，该算法聚类结可为贫困生评定提供科学的参考依据。
关键词：近邻传播；聚类算法；评估模型；案例研究
1概述
高校贫困生分级认定就是从在校学生集合中选择经济困难的学生子集，并判别其经济困难级别。准确认定贫困学生资格是高校合理、公平分配资助资源的先决条件，是高校学生获得国家困难补助、社会资助及助学贷款的重要依据[1]。目前国内外的研究主要以家庭经济状况调查作为贫困生认定的主要手段。代祖华等[2]利用层次分析法与案例推理原理建构高校贫困生分级认定模型，采用向量定义法，给出了案例库和贫困生分级认定问题的形式化描述，研究了以案例检索为基础的贫困生分级认定算法。毕鹤霞等[1]运用“模糊综合评判法与模糊层次分析法的集成”，依据层次分析法和加权平均法分别对致贫因素一级指标和二级指标进行权重测算，并根据抛物线型隶属函数测算底层因素的隶属度，构建贫困程度综合判别模型。以家庭经济状况调查数据为基础的研究存在调查指标有差异大等缺陷，而且，实际操作中，由于学生自尊心强，很多需要学校补助的学生不愿意公开家庭资料，造成学校收集的贫困生情况存在缺漏或不真实的情况。学生校园卡消费记录对分析学生的行为有很大的价值。电子科技大学从3万名在校生中，采集到了2亿多条包含学生选课记录、进出图书馆、寝室以及食堂用餐、超市购物等行为数据，通过对不同的校园一卡通记录进行分析，发现一个学生在学校有多少亲密朋友，通过这个课题找到了800多个校园中最孤独的人。周口师范学院建立了较为详细的大数据分析系统，能够实现对学生出勤、就餐、图书阅读等方面的大数据分析。南京理工大学通过数据分析，每个月在食堂吃饭超过60顿、一个月总消费不足420元的，被列为受资助对象，采取直接将补贴款打入学生饭卡的方式，学生无需填表申请，不用审核。通过学生平时校园卡的花费情况，运用数据挖掘的手段，找出真正在基础生活上比较困难的同学，并向学生发放相关补助。通过近邻传播算法将学生群体进行分类，确定学生的消费类型，在一定程度上真实地反映了学生的经济状况，而且不依赖学生调查数据，能够客观地反映学生的经济状况，从而辅助学校决策层制定相应的补助方案。
2近邻传播算法
近邻传播（affinitypropagation，AP）算法是最近发展的一种采用最大和置信传播[3]的聚类算法[4]。输入样本点之间的相似性，它产生一个中心点集合及将每个样本点分配给最合适的中心点。其中，中心点定义为最佳表达样本点集合的代表性样本点。发表于2007年Science杂志的文章[4]指出，近邻传播相比于其他基于中心点的聚类算法，具有3个优势：（1）它是非常高效的；（2）它对初始化不敏感；（3）它能够得到比k-中心点（k-center）算法[5]更优的聚类结果。从而它被广泛运用于各种实际应用场合，例如图像、文本、生物信息学、人脸识别、基因发现、搜索最优航线、码书设计以及实物图像识别等领域。由于近邻传播算法不是用均值做质心计算规则，因此对于离群点和异常值不敏感，同时其初始值不敏感的特性也能保持模型的较好鲁棒性[6]。给定N个样本点的相似性矩阵，AP算法通过最大化下面的目标函数来得到一个有效的类标向量[7]。AP算法是一个建立在因子图（factorgraph）上的最大和置信传播算法[6]。如图1所示，该算法的主要思想是，初始化阶段将所有的样本点当成潜在的中心点，然后不断地在样本点之间传递实数值消息，直至产生高质量的中心点。如图1所示，其中两种类型的消息分别是：一种是从样本点i发送到候选中心点k，用于反映样本点k能够作为样本点i的中心点的累积置信度，记为r（i,k）；另一种是从候选中心点k发送到样本点i，用于反映样本点i选择样本点k作为中心点的累积置信度，记为a（i,k）。这两种消息都初始化为0，并分别按照如下的方式不断迭代更新：直至这些消息的值收敛到不再改变为止。最终的类标向量可以通过计算得到。
3案例分析
实验都运行在一个移动图形工作站，基本配置为：64位Fedora操作系统，Intel(R)Corei7-6500U2.50GHz处理器，32GB内存，软件环境使用Anaconda5.1，Python3.6，算法基于Scikit-learn框架实现。采集了某高校4个校区共23112个学生在4个月（122天）内的消费记录，共计5572316条饭堂的POS机刷卡记录，记录包含下面的字段：卡号、学号、姓名、饭堂名称、POS机号、入账时间、金额。3.1数据分析采集到的数据是学生每一次在饭堂刷卡记录，数据来源比较单一，原始数据不能直观地反映学生在饭堂的消费水平。因此，按照食堂的时间段将学生的打卡时间分为早餐、午餐、晚餐和宵夜，不在这些时间范围内的打卡记为其他时间消费，并分别计算在这5个时间段内学生消费的均值、消费总次数和消费的标准差。通过统计学生人均吃早、午、晚餐的天数，发现在4个月中，绝大多数同学早午晚3餐在饭堂吃饭的天数不足一半，可见学生外出吃饭或叫外卖的现象非常频繁。如图2所示。午餐是最能够反映学生整体消费水平的一餐饭，因为减肥的同学会更多选择少吃晚餐，早餐又因为学生起床时间和吃饭时间难以确定而存在较大误差，因此午餐就变成3餐中最具有参考价值的一餐。分析发现4个校区午餐消费低于6元和6~9元之间的学生比例几乎一致，这说明虽然每个校区的整体消费可能存在偏差，但是生活贫困的学生的消费水平几乎是维持在6~9元之间的。观察学生消费在9~11元的比例和11~15元的比例，这部分学生绝大多数是在学校消费水平普通的学生，最能够反映饭堂午餐的均价。对比午餐和晚餐的消费情况，午餐在9~11元和11~15元的比例在晚餐段有明显的降低，而午餐在6元以下和6~9元的比例在晚餐时段则都存在不同程度的增长。这说明更多的学生倾向于晚上吃更便宜的东西。宵夜的分布与早餐很类似，可见宵夜时段学生的选择不是很多，或者说宵夜整体比较便宜。由于学校周边外卖众多，严重影响对学生消费额的估计。校园食堂内还有下午茶或者小超市，打卡记录无法分辨学生是在饭堂吃饭还是进行额外的消费，我们难以直接根据学生花费的总额或者均值来估计学生是否贫困，因此通过聚类的方法找出真正符合贫困生的消费指标。3.2划分学生类型根据上述得到的学生的消费情况，计算每两个学生之间的相似程度，如果两个学生的消费情况非常类似（比如几乎每天都在饭堂吃饭，午晚餐消费水平在6~9元，从不吃早餐和宵夜），那么就认为这两个学生是一个类别的。上述划分学生类别的方法可以通过AP聚类算法来自动完成，实验代码使用Scikit-Learn[8]编写。通过计算每两个学生之间的相似度和聚类后，将4个校区的学生分别分为86、229、161和231个类。分别记录了4个校区的每一个学生类别中的学生名单和学生的消费记录。许多类别中的学生数量非常少，这样的类别不具有代表性，不是我们需要的。筛选掉包含人数少的类别后，逐一分析每个类别的特性，总结出了8类有代表性的学生，并结合实际情况给出了下面的经验性的学生类别划分标准，如表1所示。其中A类和B类学生是推荐的贫困生（名单），通过筛选条件保证了：（1）这批学生绝大多数时间是在饭堂吃饭尽管学校周边外卖很多而且价格不贵，但是最便宜的外卖也会在10元以上起送，真正贫困的学生仍然会更多地选择在饭堂消费。（2）消费水平在每餐饭9元以下（校平均午晚餐消费是在10~11块）（3）午晚餐的标准差限制在3.5元标准差是围绕着每餐饭的平均值的一个波动，它约束了学生每餐饭之间的差异不会太大。这样就筛选出了部分大多数时间只是在饭堂买瓶饮料的学生，他们每天都在饭堂有小额的消费，平均消费水很低，在饭堂消费的次数也很高，但是这批学生往往每次消费差异比较大。而贫困生则会尽量保持一个比较低的水平维持，因此标准差会非常小。（4）早餐的均值在5元以下通过对早餐的限制来筛选减肥的学生，这群学生往往也吃得非常少，而且又以素食为主，消费水平也很低，但是这群学生通常早餐会吃得非常好。当然这中间也存在有些贫困生会将更多的金钱投放在早餐上，因此限制并不严格。全校平均早餐消费在4.5元左右，这里用5元限制，只会筛选出具有早餐高消费特征的学生。通过表1的筛选条件，对这8大类学生的消费情况作图分析，如图3所示。通过筛选了午餐、晚餐消费次数高，午餐、晚餐平均消费水平低，早餐消费不是特别高，消费偏差不是特别高的学生为目标学生（即A、B类学生）。但是通过图3可以发现，需要补贴的学生早餐的消费水平也是8类消费者中最低的，每餐饭的偏差都非常小（比较有计划地花销），并且早餐也在饭堂吃，吃宵夜和买零食的次数相比于在校吃饭次数低很多，这一切特征都满足实际印象中的贫困生的判断指标。
4结语
以学生在校的消费打卡数据为基础，通过近邻传播算法将学生群体进行分类，确定学生的消费类型。分类结果不依赖学生经济情况调查数据，在一定程度上能够客观地反映学生的经济状况。进一步，可以通过比对给出的贫困生名单和学生处人工统计的贫困生名单来判断方法是否准确。当然考虑到学生处的名单也存在调查难的问题，如果能加以追踪调查则会得到更好的评估结果。另外，此次研究只考虑了典型的指标，存在边界模糊的情况，后续将继续改进算法，提高结果的可靠性。下一步工作，拟将开发基于此模型的应用系统，应用到高校家庭经济困难学生信息系统认定的开发中，为学校的贫困生评定做决策支持。
作者：曾青松 魏斌 单位：广州番禺职业技术学院信息工程学院 广东外语外贸大学英语教育学院