基于K近邻相似的决策树算法在学生就业管理中的应用

韦金日　李雪萍

[摘 要] 由于现在的就业形势越来越严峻，就业压力越来越大，因此需要学校对大量历届学生就业的历史数据进行挖掘，发现内在的规律和联系，为就业指导提供决策依据，对学生做出针对性的指导，以提高学生的就业率和就业质量。文章基于K近邻相似的决策树算法可以较好地根据学生的基本信息进行挖掘，对学生潜在的工作做出预测，使不同的学生可以根据自己的情况对工作进行针对性的准备，从而可以更好的就业。

[关键词] 决策树；K近邻；就业管理；就业预测

[作者简介] 韦金日， 广西工业职业技术学院讲师，广西大学计算机与电子信息学院在职研究生学历，研究方向：计算机网络与并行分布式计算，广西 南宁，530003；李雪萍，广西工业职业技术学院讲师，硕士研究生，研究方向：网络与并行计算，广西 南宁，530003

[中图分类号] G64 [文献标识码] A [文章编号] 1007-7723（2013）05-0073-0003

随着我国高等教育由精英教育向大众教育的转变，高等学校的招生规模不断扩大，各高校纷纷开始利用信息化手段对教学、就业工作进行管理，并收到良好的效果。但是，由于招生人数的扩大使得学生信息系统数据库存储的数据量急剧扩增，面对巨大的数据集合，传统的数据分析手段已经日渐力不从心。这是因为传统的信息系统是基于查询的，数据库可以很好地实现对数据的存储和查询等功能，但是这些数据之间的内在关系和隐含的有用信息无法被获取，数据中存在的关系和规则无法被发现，无法利用现在的数据预测未来的发展趋势，缺乏挖掘数据背后隐藏知识的手 段[1]。

数据挖掘技术就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先未知的但又是潜在有用的信息和知识的过程[2]。对于存在着的庞大的历史信息，可以使用数据挖掘技术挖掘出毕业生就业信息中隐藏的有用因素和内在联系，从而促进学校进行教学改革，指导学生提高自身素质和知识结构，从而最大程度地提高毕业生的就业率和就业质量[3]。

本文将以从某高校学生管理信息系统中获取的实际数据作为样本数据集，利用K近邻相似的决策树算法进行挖掘和分析，从而预测出学生可能的就业情况。

一、决策树算法

决策树是一种基本的分类方法，决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程[4]。

决策树的建树过程是从根节点开始，对每个非叶子节点，找出其对应样本集中的一个属性，称为测试属性，对样本集进行测试，根据不同的测试结果将训练样本集划分成若干个子样本集，每个子样本集构成一个新叶节点，对新叶节点再重复上述划分过程，这样不断循环，直至达到特定的终止条件。其中，测试属性的选择和如何划分样本集是构建决策树的关键环节。不同的决策树算法使用不同的技术。从根节点到叶子节点的路径描述了各种分类规则，可以认为是if-then规则的集合。因此，决策树模型具有良好的可读性且分类速度快，是一种简单易行的分类方法[5]。

决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的剪枝。根据属性选择度量方法的不同，可以给出不同的决策树算法。建树的过程通常分为两个阶段：建树阶段和剪枝阶段。修剪按其进行的时间顺序可分为先剪枝和后剪枝。先剪枝是在决策树的构建过程中利用一定的技术进行判断，比如可以设置一定的阀值，若可能生成异常分枝，则停止此分枝的生成，即将此生成的分枝剪去；后剪枝则是待决策树完全生成后，运用特定的剪枝算法对整棵树进行修剪。

构建决策树模型大致可以分为两步，第一步是利用训练集建立决策树模型。这个过程实际上是一个从训练集中获取知识，进行机器学习的过程。第二步是利用生成的决策树对输入数据进行分类。对输入的纪录，从根节点依次测试记录的属性值，直到到达某个叶子节点，从而找到该记录所属的类。

常用的属性选择度量有：信息增益、信息增益率和Gini指标。信息增益来自于信息论中的概念，表示已知特征的信息使得类的信息不确定性减小的程度[6]。

（一）信息增益

设数据集S包含n个数据样本，类别集合为 C■，C■…，C■。记Si为类别Ci中的样本个数，显然有■S■=n 。对一个给定数据对象进行分类的期望信息为：

I（s■，s■，…s■）=-■p■log■（p■）

其中p■是类别Ci发生的概率，可以由式子Si/n估计。

若属性A有互不相同的v个值a■，a■，…a■，根据属性A将S划分为v个子集S■，S■，…S■ ，Sj中数据样本取值均为aj，记Sj的样本数为Sj=n■，则S■（a■）的发生概率为nj/n。记子集S■中属于Ci类的样本数为S■，则集合S■中具有类别Ci的条件概率为Sij/n。如果A被选做测试属性，根据A产生划分的熵由下式计算：

E（A）=■■I（S■，…，S■）=■■n■I（S■，…，S■）

其中I（S■，…，S■）=-■P■log■■（P■） =-■■log■■。

利用属性A对当前分支结点进行样本集合划分所获得的信息增益为：

Gain（A）=I（S■，S■，…，S■）-E（A）

本文选择具有最高信息增益Gain（A）的属性A作为节点的分裂属性。

（二）信息增益率

信息增益率是在信息增益的基础上，引入属性 的信息熵Split（A）：

Split（A）=-■■log■■

并定义属性的信息增益率为：

GainRatio（A）=■

本文选择具有最大信息增益率GainRatio（A）的属性A作为节点的分裂属性。

信息增益偏向于多值属性，信息增益率在此基础上调整了多值属性，但是倾向于不平衡的分裂，而Gini指标不仅偏向于多值属性，而且当类的数量很大时会有困难，并且还倾向于导致相等大小的划分和纯度。考虑到数据集的实际情况，本文采用信息增益率作为属性度量选择方法。

二、K近邻相似的决策树算法

（一）数据的预处理

在数据挖掘中，数据集的数据好坏对最后的结果有很大的影响，因此很大的一部分精力都要用于数据的预处理。从数据库中导出的原始数据有62个维度，这其中有很多的维度与我们最终要分析的结果无关，为了不让这些数据影响到最终处理结果，因此要手动进行降维，最后要分析的维度为30个维度。其中的类标识是就业单位性质，为了进行数据的处理，将这些不同的类别分别用数字表示，总共有九个类别，分别是无业、自主创业、营企业、国有企业、读书深造、公务员、部队、事业单位与合资企业，分别对应着0～8这八个数字。

由于选择的剩余29个维度都是分类属性的数据，因此不需要进行数据的离散化，但是需要对这些数据进行数值化的处理，每个属性的值为P■（i=1...n），其中n是每个属性含有的不同的分类属性值。

（二）K近邻相似的决策树算法

数据集中有一些缺失的数据，因此需要对这些缺失数据进行填充，通常处理缺失数据的方式是设定一些默认值或者取某个属性的众数，但是这样会造成最终数据的失真率比较高，因此本文采用一种近邻填充缺失值的方法：对于特征空间中的每个训练实例xi，距离该点比其他点更近的所有点组成一个区域，叫作单元。每个训练实例点拥有一个单元，所有训练实例点的单元构成特征空间的一个划分。最近邻法将实例xi的类yi作为其单元中所有点的类标记，其中每个区域中有k个实例。

采用余弦相似函数作为两个不同实例的距离度量，将每个实例看作是一个向量，将每个属性的值看作向量的一个元素，两个向量分别记作X和Y，X和Y的距离为 ，其中 和 分别是向量X和Y的范数，取与每个向量最接近的k个向量，本文中k设为100，对缺失值做以下的处理：找出k个向量中当前属性下有值的n个向量，缺失值填充为这n个向量当前属性的和的n分之一。当填充完所有的缺失值之后，就进行决策树的构建。采用经典的C4.5算法来构建决策树，并通过信息增益率进行每次的分裂属性选择。

三、结果分析

（一）实验环境及软件

本文的实验环境如下：Intel（R） Core（TM） i7 CPU，4G内存，500G硬盘；开发语言为Java，环境为JDK 1.6，编程工具为Eclipse；所用数据库为：MySQL 5.5.10。

（二）数据属性和数据集

数据来源于学校学生管理信息系统中的实际数据，由于某些数据对我们的目标没有帮助，所以在实验前必须对所需数据进行归纳整理。选取的数据集中含有三年的数据，因此将前两年的数据作为训练数据，第三年的数据作为预测数据。总共的样本大小是9598，其中训练集大小是6308，测试集大小是3295。

样本的维度总共有25个，分别是学号、入学时间、毕业时间、性别、民族、政治面貌、考生类别、生源地、系部名称、班级、专业方向、家庭经济情况、个人身高、个人特长、在校任职、所获奖励、能力证书、就业意向、意向月薪、学籍变动、就业时间、就业形式、就业区域、派遣单位名称和就业单位性质。

其中的个人身高需要进行离散化的处理，将具体的身高划分为150～155、156～160、161～165、166～170、171～175、176～180以及180以上这七个类别，由于其中有些数据在统计时缺失了，因此使用本文提出的K近邻相似进行缺失值的填充。对于就业意向和意向月薪也进行类似的处理。

通过程序分别计算每个属性的信息增益率，由每个属性的信息增益率大小可知，专业方向的信息增益率最大，从而将专业方向作为决策树的根节点。分别进行迭代计算可以构建出整个决策树。

（三）实验结果

通过采用众数进行缺失值填充和采用最近邻法进行填充的预测效果进行比较，如表所示：

通过数据可以发现，使用了最近邻填充缺失数据的方法精度有了比较大的提高，因此证明本方法是切实有效的。

不过，由于进行k近邻比较的时候需要两层扫描训练集，其复杂度达到了O（n■） ，因此需要借助于MapReduce进行并行化的操作。

四、结 论

在目前就业形势严峻的环境下，本文将K近邻相似的决策树算法应用于高校就业，挖掘学生数据与就业有关的关系，为就业指导提供决策依据。利用这些预测信息，学生可以合理规划就业方向，学校就业指导者可以在毕业生就业宣传，就业计划投放等方面做出正确的决策，提高学生的就业率、增强学校竞争力。

[参考文献]

[1]金莹.决策树算法在高校学生就业中的应用研究[D].合肥工业大学计算机与信息学院，2009.

[2]张嘉赢.基于数据挖掘技术的高校毕业生就业管理信息系统的设计与实现[D].东北大学信息科学与工程学院，2009.

[3]贺爱香，袁雪松.C4.5决策树算法在应用型本科高校就业管理中的应用研究[J].滁州学院学报，2012，14（5）.

[4]李航.统计学习方法[M].北京：清华大学出版社，2012.

[5]Jiawei Han， Micheline Kamber. Data Mining Concepts and Techniques， Second Edition[M].范明，孟小峰，译.北京：机械工业出版社，2007.

[6]S. B. Kotsiantis. Decision trees： a recent overview[J]. Artificial Intelligence Review， 2013， 39， 261-283.