改进的K-近邻算法及其在学习预警中的应用

宗晓萍，陶泽泽

(河北大学 电子信息工程学院，河北 保定 071002)

大数据时代的到来，使海量的数据资源在各个领域彰显其优势，驱动着其运营和管理模式的创新.教育数据挖掘(educational data mining,简称EDM)是指利用不断发展的数据挖掘技术和方法，分析、探索特定教育环境中的各类数据，挖掘出有价值的信息，帮助学校和教师更好地了解学生的学习、成长过程，为教育者、学习者、管理者等提供参考与建议[1]，以改善其学习环境，提高学习效率.近年来，随着信息技术与教学的深度融合，特别是慕课、翻转课堂、混合式教学等新兴教学模式的发展，使教育数据挖掘被越来越多的研究者所关注[2].

学生在线学习行为的分类和预测是目前教育数据挖掘及应用所研究的重要内容之一[3].众多的国内外学者建立不同的预测模型，通过分析网络在线学习数据，预测其学习效果，并对学习过程进行干预与评估.研究学习预警中常用的经典方法包括谱聚类法[4]、贝叶斯网络理论[5]、过程表现度量法[6]、C4.5算法[7]、多个模型比较法[8]等.Mayilvaganan等[9]通过实验发现K-近邻(K-NN)算法在学习预警中是一个非常有效的方法.K-NN算法原理简单且容易实现，当面对海量数据时，具有明显的优势.但是该算法存在一些较大的缺点：首先K-近邻算法的K值和距离度量的方式通常是根据个人经验来选择，给分类结果带来了一定的影响.同时，在计算待测样本与训练样本之间的距离时，所有的特征拥有等效的地位，而在实际应用中，每个特征对分类结果所起的重要程度不同，分为重要特征、次要特征和冗余特征.这样往往容易导致样本间的距离会被许多的冗余特征所控制,产生维度灾难.因此，特征选择决定着分类的时间效率及预测结果的准确性.

针对以上问题，本文提出了改进的K-近邻算法以及在学生预警中的应用.针对传统K-NN算法存在的问题,首先利用网格搜索和交叉验证相结合的方法对模型参数进行优选,其次，计算每一个特征的基尼增益来确定特征的重要程度，并且引入缩放因子放大和缩小权重系数,并且根据权重系数将特征划分为重要特征、次要特征和冗余特征,在计算欧氏距离时引入权重系数,使各个特征的作用受其权重系数的约束.通过实验对比，改进后的K-近邻算法(DT-K-NN)比传统K-NN算法在模型分数上有了极大的提高.

1 K-近邻算法

K-近邻(K-nearest neighbors,K-NN)是一种基本的机器学习算法，其本质源于相似理论，相当于一种用于样本分类的非参数方法[10].K-NN在分类预测时，一般采用多数表决法，即依据距离度量公式计算出离待测样本最近的K个样本数据.通过投票法来得到这K个样本数据的类别，那么该待测样本被划分为投票数量多的那一类别,其中，距离的度量主要有欧氏距离、曼哈顿距离.

1)根据个人经验给定K的值.

2)计算新数据到每个训练样本的距离(p=1为曼哈顿距离，p=2为欧氏距离)

.

(1)

对求得的所有距离按照从小到大进行排序，越小代表越相似.

3)在n个距离值中取前K个样本数据对应的分类标签.

4)统计K个数据中出现次数最多的分类标签作为新数据的分类.

2 K-NN算法的改进

2.1 基于网格搜索和交叉验证的参数寻优

根据K-近邻算法原理可知，超参数K和距离度量参数p对模型的预测效果有很大的影响.网格搜索法(grid search,GS)是处理有约束非线性极值问题的一种数字规划法，也可以称其为枚举搜索法.它将K与p组成的参数空间等距划分为若干网络，根据枚举网络交叉点处的全部参数组合，计算出其对应训练模型的分数，直到遍历网格平面的每一个交叉点，找到训练分数最大的参数组合，即为最优参数.同时，网格搜索法对2个参数进行寻优时，可以确保搜索解是划分网格中的全局最优解，消除了个人经验法确定参数时带来的庞大误差[11].

另外，训练数据对参数组合的性能评价有一定的影响，当选取的训练集不一样时，同一组(k,p)所对应的K-NN预测模型的拟合性一般会发生改变.为了模型的泛化和推广，本文在网格搜索中引入K-fold交叉验证法，对每一组(k，p)的性能进行评价.通过网格搜索和K-fold交叉验证相结合的方法对K-NN的模型参数k、p进行寻优，其步骤如下：

1)网格坐标的建立.令a=[1,2,…，11,12]，b=[1,2]，步长为1，可知模型参数的网格交叉点(k,p).其中k=αi,i=1,2,…，11,12.p=bj,j=1,2.另外，αi代表a中的第i个元素，bj表示b中的第j个元素.

2)将训练集均分为K个子集，K的取值往往为4～10，以保证测试样本远小于训练样本.此外，本文令K=10，因为10倍的交叉验证会有较好的效果[12].

3)针对网格中每一组参数(k，p)，随机取一个子集作为测试集，剩下的K-1个子集作为训练集，训练模型后对测试集进行预测，统计训练模型的分数.

图1 网格参数优化过程Fig.1 Grid parameter optimization process

4)取另外一个子集为测试集，再将其余K-1个子集看作训练集，再次计算训练模型的分数，直到对每一个子集都进行一次模型评分后，取K组训练模型分数的平均值作为该组(k，p)的最终训练模型分数.

5)取另外一个参数组合(k，p)，重复步骤2)～4)，依次计算出网格中每个参数组合下的模型分数，通过对比选出最大的平均训练模型分数，其对应的参数组合就是网格区间内最优的参数组合.本文选取的最优参数组合为(k=4，p=2).

通过网格搜索与交叉验证相结合的方法，当训练模型的平均分数最大时所对应的参数为最优参数.避免了个人经验法在选取参数时对K-NN模型分数带来重大的影响，同时，在很大程度上减少了训练样本的抽取随机性对模型拟合性能的影响.在结果展示方面呈现等间距的网格搜索结果.如图1，其高度代表训练模型的分数.

2.2 特征选择和特征权重的确定

在传统的K-NN算法中，每个特征对分类的贡献是同等重要的.但在实际应用中，每个特征对分类的贡献是不相同的，一部分起重要作用，另一部分则起次要作用或者没有起作用.例如，当预测学生的成绩时，学生的学习时间、课堂缺勤次数是重要特征，而性别、身体健康状况为次要特征，而身高、体重等特征对成绩预测基本无关.为了突出重要特征的作用，消除冗余特征对预测结果的干扰，必须找出每个特征的贡献程度并以此进行特征选择.本文对贡献比较大的特征进行适当的增大，对贡献比较小的特征进行适当的减小，此外把没有贡献的特征删除掉.另外为了确定每个特征的贡献程度，本文引入了基尼系数和基尼增益的概念，并利用基尼增益来确定每个特征的重要性，并引入缩放因子确定所选特征的最终重要程度.

2.3 基尼增益的计算[13-14]

在决策树的生成中，获得信息量的度量方法是从反方向来定义的：如果一种划分能使数据的“不确定性”减少的多，则该划分能获得更多的信息.其信息量可以使用其基尼系数来度量.y的基尼系数定义为

(2)

对于具体的、随机变量y生成的数据集D= {y1,y2,…,yN}而言，在实际中一般会选择经验基尼系数来估计

(3)

假设y的取值空间为{c1,c2,…,ck}，pk表示y取Ck的概率：pk=p(y=Ck)；|Ck|代表由y中类别为ck的样本数，|D|代表D的总样本数(即|D|=N).

,

(4)

其中

(5)

可以用经验条件基尼系数来进行估计

,

(6)

公式中的|Djk|代表着Dj中第k类样本的个数.基尼增益则自然地定义为

G(y,A)=Gini(y)-Gini(y|A).

(7)

2.4 利用基尼增益确定特征的贡献程度

在本文中,基尼增益比较大的特征称为主要特征，基尼增益比较小的特征称为次要特征，没有获得基尼增益的特征称为冗余特征.依据每一个特征基尼增益的大小，建立一个向量βj(特征权重系数)来表达每个特征的贡献程度.基尼增益很小的特征对应的权重比较小，较大的特证对应的权重比较大[16].根据特征的重要程度再进行特征选择，选出权重比较大的特征.

假设每个训练样本有m个特征，计算各个特征的基尼增益，得到一个基尼增益向量[G1,G2,…，Gm].

利用基尼增益向量算出特征权重系数

(8)

其中，j=(1,2,…,m).ln(e+Gj)为权重系数缩放因子，如果基尼增益较小时，它会稍微压缩特征权重系数.如果基尼增益较大时，它稍微放大特征权重系数.所以，通过权重系数优化后的欧氏距离公式为

(9)

2.5 改进的K-近邻算法

假设有一个带有标签的数据集x有n个样本，每个样本有h个特征.

第1步：利用网格搜索和交叉验证法找出最优的超参数k和距离度量方式.

第2步：在决策树生成中，利用基尼系数和基尼增益算出每个特征的重要程度[G1,G2,…,Gm].

第3步：利用基尼增益向量算出最终特征权重系数.

(10)

第4步：计算新数据到每个训练样本的欧氏距离

(11)

对求得的所有距离按照从小到大进行排序，越小代表越相似.

第5步：在n个距离值中取前k个样本数据对应的分类标签.

第6步：统计k个数据中出现次数最多的分类标签作为新数据的分类.

3 实验方法和结果

3.1 实验数据

3.1.1 Student Performance数据集

“Student Performance”为UCI提供的公开数据.该数据集提供了2个不同学科的成绩:数学(mat)和葡萄牙语(por),一共包含1 044个学生，与学生成绩有关的特征一共32个.但是目标特征G3与特征G2和G1有很强的相关性.其中，G1和G2是前2个学期的成绩，G3是最终期末成绩.G1、G2、G3的分数是0～20，本文设定了新的目标列G，G为G1、G2、G3的平均值，将目标列G分成3类(合格、优秀、不及格).

3.1.2 情绪管理课程数据集

此数据来源于河北大学网络教学平台于2017年下半年开设的《情绪管理》这门课程的数据，收集到的原始数据共有624个学生数据，数据包括7种学习行为：课程视频得分(50%)、课程视频进度、课程测验得分(20%)、课程测验进度、考试得分(30%)、讨论数、访问数、任务点完成百分比.另外，按照学生的综合成绩将学生的成绩划分为3个等级(合格、优秀、不及格).

3.2 特征预处理

数据预处理已经成为教育大数据实现过程中的关键步骤，它直接影响着最后的结果.在实际中收集来的数据是不干净的、模糊的而且冗余的.为了提高算法的效率，必须通过数据预处理来提供准确、干净和简洁的数据.在这2个数据集中，有几个特征的记录都是非数字的.通常情况下，学习算法期望输入是数字的，这要求非数字的特征(称为类别变量)被转换.转换类别变量的一种流行的方法是使用独热编码方案.独热编码为每一个非数字特征的每一个可能的类别创建一个“虚拟”变量.例如，学生的性别特征sex有2个取值female或者male.把这个特征编码成sex_female和sex_male，详细的转换方法见表1.

表1 非数值特征转化为数值特征

3.3 评价指标

考虑到该研究的实质，即决定哪些学生需要进行干预.在这种情况下，往往更关心失败学生的正确分类，而这些学生正是想要关注的对象，而不是通过学生的标签[17].如：一个通过学生被贴上失败学生的标签，这不是一个令人担忧的问题，因为老师们只是花了一点额外的时间来验证这个学生，实际上并不是一个有风险的学生.然而，一个被贴上通过标签的失败学生将会是一个更大的问题，因为老师们会跳过他们，而那个学生可能会错过一个干预的机会.因此，在所有实际上失败的学生中，成功预测出失败的学生是非常重要的，使用Fβ作为评价指标，这样能够同时考虑精准率和召回率，尤其是，当β=0.5时，更多的强调召回率(即更加关注失败学生的正确分类)，简写为F0.5.

在所有预测有风险的学生中，实际上有风险的学生的比例，简称精准率

在所有实际上有风险的学生中，成功预测有风险的学生的百分比，简称召回率

精准率和召回率的平衡

公式中的TP代表低分的学生被判为有风险；FP代表高分的学生被判为有风险；FN代表低分的学生被判为没有风险.

3.4 模型分数对比

在时间效率上，改进的K-近邻算法对训练集做了预处理.通过基尼增益进行特征选择，选出了基尼增益最大的前几个特征.通过特征选择减少了特征的数量，大大节省了计算时间和空间.

在分类的精确度上，首先利用网格搜索和交叉验证相结合的方法对模型参数进行优选，其次，在计算欧式距离时引入了权重系数βi，使每个特征受到权重系数的约束，使模型的分数明显提高.

当训练集分别为总数据集的40%、60%、80%时，比较了改进的K-NN算法(DT-K-NN)、个人经验法K=5时的传统K-NN算法以及最优参数下其他常用机器学习算法(随机森林、朴素贝叶斯、决策树、支持向量机(SVM)等).在Student Performance数据集和情绪管理数据集上，改进的K-近邻算法比传统K-NN算法在F0.5分数上提高了约7%,并且稍微高于其他机器学习算法，实验结果见表2和表3.

表2 在Student Performance数据集上不同算法的F0.5分数

表3 在情绪管理数据集上不同算法的F0.5分数

4 结语

本文给出了一种改进的K-NN算法及其在学习预警中的应用，首先利用网格搜索和交叉验证相结合的方法对模型参数进行优选，避免了个人经验法在选取参数时，对K-NN的模型分数带来的影响.另外，通过计算每一个特征的基尼增益来确定特征的权重系数并进行特征选择,并且根据权重系数将特征划分为重要特征、次要特征和冗余特征,在计算欧氏距离时引入权重系数,使各个特征的作用受其权重系数的约束，显著地提高了预测的准确率.最后，本文采用了F0.5分数作为评价指标，因为在学习预警中往往更加关注失败学生的正确分类.本文提出的学生预警方法可用于对学生在线学习结果的预测，根据预测结果及时对有风险的学生进行干预.但在改进算法的实现步骤中，缺乏对关键步骤的理论分析，如关键步骤的代价分析，算法复杂度分析等，后续还需要对其中某些技术难题进行更深入的研究.