基于K近邻相似的决策树算法在学生就业管理中的应用
2022-06-09
[作者简介]韦金日，广西工业职业技术学院讲师，广西大学计算机与电子信息学院在职研究生学历，研究方向：计算机网络与并行分布式计算，广西南宁，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作为节点的分裂属性。
[中图分类号]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作为节点的分裂属性。