C4.5算法在民族地区高校毕业生追踪调查中的应用研究

梁达友 董荣胜 王泓刚

摘 要：部分民族地区高校毕业生就业是个难点问题。本文介绍了ID3、C4.5和CART三种决策树算法，并选取河池学院毕业生追踪调查数据，分别建立ID3、C4.5和CART分类器进行预测比较。结果表明，C4.5预测分类器具有最小计算量和最高准确率。通过测试，C4.5分类器预测分类准确度和精度与实测数据相符，能够较好地满足应用要求。C4.5分类器分类规则表明，道德素养、专业素质和实践能力是用人单位录用毕业生的主要标准。预测结果同时也为学校创新人才培养模式，提高毕业生就业能力提供一定的决策支持。

关键词：教育数据挖掘 追踪调查 预测分类 C4.5算法

中图分类号：TP301.6 文献标识码：A 文章编号：1674-098X（2014）04（a）-0252-05

目前，我国经济飞速发展，产业结构高度化，社会岗位需求不断增多，高校扩招后毕业生人数也逐年增加，然而，由于就业结构性矛盾不断加剧，出现招工与就业“两难并行”的局面[1]。究其根本原因在于高校培养人才与社会需求脱节，人才供给与社会需求错位。作为一所新建的民族地区高校，河池学院处于发展阶段，人才培养体系还未完善，毕业生质量与社会需求尚有较大差距。为了缩短人才培养与社会需求间的差距，使毕业生符合社会需求，需要准确地了解用人单位对人才的需求标准。

本文以河池学院毕业生追踪调查信息数据为基础，利用数据挖掘技术对用人单位评价毕业生的信息数据进行推测和估计，探索用人单位录用毕业生的规律及发展趋势[2]，找出学校培养目标与社会需求的差距，为学校进行教育改革，提高毕业生就业能力提供依据。

1 教育数据挖掘

数据挖掘（Data Mining，DM）是从大量数据中寻找规律的技术，广泛应用到市场推广、医疗、房地产、客户关系管理、工程、网络信息挖掘等各个领域。在教育领域，越来越多的研究者使用数据挖掘技术。应用在数据相关教育领域的数据挖掘技术称为教育数据挖掘（Education Data Mining，EDM）。教育数据挖掘是一种新兴的数据挖掘技术，侧重于从教育环境中的数据挖掘知识，根据教育体系中教学、管理和科研三个业务，将教育数据挖掘细分为E-Learning数据挖掘、E-Management数据挖掘和E-Research数据挖掘三个范畴[3]。E-Management数据挖掘使用教育机构数字化管理系统收录的数据，挖掘包括教师绩效评估、人才引进、招生决策、就业预测、毕业生就业追踪等多方面信息，为教育管理部分做出决策提供有效支持。常见的数据挖掘方法有决策树、神经网络、朴素贝叶斯、粗糙集、模糊集、K近邻法、遗传算法等。综合Romero[4]和Baker[5]对教育数据挖掘的分类，这些方法可分成统计分析与可视化、聚类（聚类分析等）、预测挖掘（决策树等）、关系挖掘（关联规则挖掘等）、文本挖掘五类。

2008年，针对毕业生和求职人员共存环境下的就业问题现状，屈百达[6]等人建立动态对策模型，并给出H∞控制解法。通过求取反馈增益矩阵，得到在职人员、失业待业人员数名的优化组合结构关系，预测当期毕业生新增就业人数，缓解就业冲突。2009年，刘斓[7]等人转化决策树数据，利用二进制关联规则挖掘算法分析大学生就业竞争力，提取有效规则，在培养学生就业能力上有一定指导作用。张稳[8]等人以新疆农业大学毕业生数据为例，采用多项式回归和多元线性回归两种不同的算法對其数据建模，实现对该校就业率的预测。韦丽梅[9]等人从管理系统和课程设置的角度出发，经过调查问卷、访谈、座谈会等方式，分析影响中职院校计算机类专业学生就业的因素。2010年，针对毕业生就业预测存在的不可靠性问题，程昌品[10]等人以广东教育学院毕业生就业情况为例，使用基于信息增益比的决策树方法构建毕业生就业预测模型。实验测试表明，C4.5决策树较ID3算法的预测效果有更好的可靠性和健壮性。2011年，牛丽[11]等人提出基于层次分析法和高斯隶属函数的模糊综合评价方法，以大学生就业能力评价的层次性、模糊性为例，评估大学生就业能力。缺点是没有和计算机结合建立相应的评价系统。针对学生就业问题中出现噪声造成不一致数据问题，常志玲[12]等人提出基于变精度粗糙集的决策树模型，分析学生就业数据，简化决策树结构。贺爱香[13]等人分析C4.5算法建立流程及结构，并以安徽新华学院毕业数据为基础，运用C4.5算法建立应用型本科高校就业模型，并验证模型的正确性和实用性，为学校提高就业率提供决策支持。

综上所述，大学生就业问题的研究方法有矩阵模型、决策树模型、事务数据库模型、管理学方法。决策树模型依赖迭代或递归算法[4]，原理计算和实现较矩阵模型简单，建立的决策树较事务数据库模型易于理解，且比管理学问卷调查等方法易实施。由于决策树模型能够将复杂的决策过程化简成简单决策的集合，并能够提供容易解释的解决方案。被广泛应用于医疗诊断、专家系统、语音识别、遥感等各个领域[14]。

在教育挖掘领域使用这些技术，可以挖掘出很多方面的知识。本文将以河池学院毕业生追踪调查信息数据为基础，构建决策树预测模型，从用人单位的角度，发现用人单位录用毕业生的潜在标准，进一步预测毕业生的就业能力。预测目的主要是发现未被用人单位录用的毕业生存在的问题。如果在大学生未毕业前，预测发现其将不会被用人单位录用，学校就可以找出其原因所在，及时采取措施，调整培养计划，提高他的就业能力，并帮助他顺利就业。

2 决策树算法

决策树是一个树型预测模型，代表的是对象属性与对象值之间的一种映射关系。决策树开始于一个根节点上，树中节点表示某个对象；每个分叉路径则代表某个可能的属性值；叶结点是从根节点到该叶节点的路径所表示对象的值。决策树是运用概率分析进行评估、预测的一种树型图解算法，是预测分类的一个重要方法，常用于分析数据和评估预测。常用的决策树方法有ID3算法、C4.5算法和CART算法等。

2.1 ID3（迭代二叉树3代）

ID3是J.Ross Quinlan于1986年在奥卡姆剃刀基础上开发的，基于信息熵的决策树算法。ID3使用信息增益度量选择分裂属性，运用自顶向下的贪心策略建立决策树，选择具有最高信息增益的属性为根节点，计算所有属性可能的值以确定分支、节点和叶节点。树的建立分两阶段，分别是树构建和修剪。ID3算法原理如下：

定义1：假设数据集合S有s个数据样本，类别标识属性C可分为m个不同类Ci（i=1，2…，m），设si为Ci样本数，则集合S分类的期望信息量为

（1）

式中pi表示Ci类在数据集合S中的概率，。

定义2：如果A是集合S的属性，A有n个值，则集合S可分为n个子集Si（i=1，2，…，n），设sij为子集Si的样本数，则由属性A划分成n个子集后集合S的信息量为：

（2）

式中E（Si）是属性A划分出的子集Si按类别标识属性分类的信息量，s是集合S的样本数。则属性A分枝上的信息增益为：

Gain（S，A）=E（S）-E（S，A） （3）

迭代计算每个属性的信息增益，选择信息增益大的属性为分裂属性建立决策树。

ID3算法不能处理连续属性，需要离散化才能使用，在选择最佳分离属性的时候容易选择那些属性值多的一些属性。

2.2 C4.5算法

C4.5算法是ID3的改进算法。C4.5采用信息增益率为度量来选择决策属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足。C4.5使用悲观剪枝法，消除不必要的分支，以提高分类的准确性。该算法在继承ID3的同时，具有产生的分类规则易于理解，准确率较高的优点，能够完成对连续属性的离散化和不完整数据进行处理。信息增益率算法原理如下：

（4）

其中Gain（S，A）为属性A的增益，由（3）式给出；SplitInfo（S，A）为分裂信息，代表属性A分裂样本集的广度和均匀性。

（5）

2.3 CART（分类与回归树）

CART（Classification And Regression Trees）分类算法最早由Breiman 等人提出，已经在统计领域和数据挖掘技术中普遍使用。CART选择Gini指数作为测试属性，和ID3和C4.5算法不同的是，CART算法生成的决策树是结构简洁的二叉树。CART算法使用后剪枝法，从决策树中移除不可靠的分支，以改善精度。CART算法可以同时处理分类和连续属性，也可以处理缺失值。不过，Gini指数是以分类纯度来划分节点的，因此，CART算法最初建立的树也有错误率，因为有些叶子节点并不是纯的。

3 预测挖掘过程

3.1 数据预处理

本文从河池学院历年收集的毕业生追踪调查信息中，提取了2009年至2013年用人单位对河池学院毕业生的评价信息数据，经与学校统计的毕业生就业状况数据合并，集成了用人单位对河池学院毕业生的评价数据集，一共477条评价记录，每条记录包含的属性有毕业生的个人基本信息，数据采集日期，用人单位对毕业生德、智、能等方面的评价。在这些属性中，抽取用人单位录用毕业生影响较大的4个属性，分别为用人单位对毕业生评价选项中的道德素养、专业素质、实践能力和创新能力，加标识属性“是否录用”，泛化后形成了如表1所示的数据集结构。

各属性定义如下：

DD（道德素养）：包括毕业生的思想道德、社会责任感、团队合作精神、敬业精神、心理素质等，分为优、良、一般、差四个等级。

ZY（专业素质）：指毕业生具备的相关专业素质，包括专业知识、学习新知识能力、语言表达能力、计算机能力和外语水平等，主要以学习综合成绩来描述，分为优、良、一般、差四个等级。

SJ（实践能力）：指毕业生的实践动手能力、独立工作能力、人际交往能力、组织管理能力等，分为强、较强、一般、差四个等级。

CX（创新能力）：指毕业生创新运用知识和理论的能力，分为强、较强、一般、差四个等级。

LY（是否录用）：指毕业生是否被用人单位录用，包含被用人单位辞退的毕业生。分为YES、NO两种。

集成数据集如表2。把数据集按年度分为两个子數据集：其中2009-2012年的385条数据记录作为训练数据集，用于预测分类建模；2013年的92条数据记录作为测试数据集，用于测试预测模型的准确度。

3.2 算法选择

评价分类器通常有预测准确度、计算机复杂度和模型描述简洁度三方面来。预测准确度是使用最多的比较尺度，特别是对于预测型分类任务；计算复杂度依赖于具体的实现细节和硬件环境，操作对象越是巨大的数据库，空间和时间的复杂度问题越重要；模型描述越简洁越受欢迎，尤其是对于描述型的分类任务。目前普遍认为，同时适用于各种特点数据的分类器是不存在的。

C4.5算法具有准确率较高、模型描述简单和产生分类规则易于理解的优点。根据本文数据的特性和挖掘任务，选用C4.5算法作为本文数据预测挖掘算法。

3.3 C4.5预测模型构建

训练数据集合中属性“LY（是否录用）”为类别标识属性，其他DD（道德素养）、ZY（专业素质）、SJ（实践能力）和CX（创新能力）为决策属性。类别标识属性“LY（是否录用）”有385个值，其中“YES”319个，“NO”66个，则集合分类的期望信息量为：

3.3.1 计算决策属性的信息量

对属性DD（道德素养）

当DD（道德素养）=“优”时，有153个值：153个“YES”，0个“NO”，则

当DD（道德素养）=“良”时，有92个值：92个“YES”，0个“NO”，则

当DD（道德素养）=“一般”时，有74个值：53个“YES”，21个“NO”，则

当DD（道德素养）=“差”时，有66个值：21个“YES”，45个“NO”，则

由此得出属性“DD（道德素养）”的信息量

3.3.2 计算决策属性的信息增益

属性DD（道德素养）的信息增益为：

Gain（S，DD）=E（S）-E（S，DD）=0.6610-0.3201=0.3409

3.3.3计算决策属性的信息增益率

属性DD（道德素养）的分裂信息为：

所以属性DD（道德素养）的信息增益率为：

同理可计算出属性ZY（专业素质）、SJ（实践能力）、CX（创新能力）的信息增益率，分别为

GainRatio（S，ZY）=0.0755

GainRatio（S，SJ）=0.0260

GainRatio（S，CX）=0.0055

3.3.4 确定根节点

比较属性DD（道德素养）、ZY（专业素质）、SJ（实践能力）、CX（创新能力）四个属性的信息增益率，属性DD（道德素养）具有最大信息增益，所以选择DD（道德素养）作为测试属性，得到如图1所示的决策树根节点。

3.3.5 建立决策树

属性DD（道德素养）为根节点时，得到“优”、“良”、“一般”和“差”四个分支，利用递归方法，对每个分支迭代计算信息增益率，最后得出决策树，如图2。

通过上述计算方法得到的决策树，详细而庞大，每个属性都被详细地加以考虑，是一颗完美的树，但实用性差，存在过拟合现象，实际使用中会导致数据失真。因此，需要对决策树进行剪枝，采用悲观剪枝法剪枝后决策树如图3。

3.4 ID3、C4.5和CART比较

WEKA是一个集合了ID3、 C4.5和CART等机器学习算法的开源应用软件，广泛应用于数据挖掘。导入训练数据集，在WEKA平台分别建立基于十折交叉验证评估方法的ID3、C4.5和CART分类器。比较结果如表3、表4和表5。

从以上比較可以看出，准确度最高和计算时间最少的分类器是C4.5。虽然C4.5分类器对类“YES”分类准确度稍低于ID3和CART，但C4.5分类器对类“NO”分类准确度最高，且C4.5分类器对类“YES”和“NO”分类准确度相差最小，说明C4.5分类器对噪声数据正确预测能力较强。综合上述比较，在本文的数据挖掘研究中，C4.5分类器优于ID3和CART。

3.5 测试C4.5分类器

用测试数据集代入C4.5分类器进行测试，准确测出90条记录，2条记录预测错误，准确率达到97.8261%，如表6。

预测模型对“YES”类的预测准确率达98.7%， 对“NO”类预测准确率达92.9%，如表7。

从测试结果看，建立的分类器预测精度较高，预测已录用（YES）类准确率高于未录用（NO）。把预测结果和学校历年的就业统计数据相比较，结果基本相符。

3.6 C4.5分类器规则

通过以上测试和评价，C4.5预测模型能较地应用本文数据挖掘分类预测，且有较高预测准确度。根据图3所示决策树得出以下预测分类规则：

（1）IF DD（道德素养）=“优”OR DD（道德素养）=“良” THEN LY（是否录用）=“YES”。

（2）IF DD（道德素养）=“一般” AND ZY（专业素质）=“优”THEN LY（是否录用）=“YES”。

（3）IF DD（道德素养）=“一般” AND ZY（专业素质）= “良” THEN LY（是否录用）=“YES”。

（4）IF DD（道德素养）=“一般” AND ZY（专业素质）= “一般” THEN LY（是否录用）=“YES”。

（5）IF DD（道德素养）=“一般”AND ZY（专业素质）=“差” THEN LY（是否录用）=“NO”。

（6）IF DD（道德素养）=“差”AND ZY（专业素质）=“优” AND SJ（实践能力）=“强”THEN LY（是否录用）=“YES”。

（7）IF DD（道德素养）=“差”AND ZY（专业素质）=“优” AND SJ（实践能力）=“较强” THEN LY（是否录用）=“YES”。

（8）IF DD（道德素养）=“差”AND ZY（专业素质）=“优” AND SJ（实践能力）=“一般” THEN LY（是否录用）=“YES”。

（9）IF DD（道德素养）=“差”AND ZY（专业素质）=“优” AND SJ（实践能力）=“差” THEN LY（是否录用）=“NO”。

（10）IF DD（道德素养）=“差”AND ZY（专业素质）=“良” AND SJ（实践能力）=“强” THEN LY（是否录用）=“YES”。

（11）IF DD（道德素养）=“差”AND ZY（专业素质）=“良” AND SJ（实践能力）=“较强” THEN LY（是否录用）=“YES”。

（12）IF DD（道德素养）=“差”AND ZY（专业素质）=“良” AND SJ（实践能力）=“一般” THEN LY（是否录用）=“NO”。

（13）IF DD（道德素养）=“差”AND ZY（专业素质）=“良” AND SJ（实践能力）=“差” THEN LY（是否录用）=“NO”。

（14）IF DD（道德素养）=“差”AND ZY（专业素质）=“一般” THEN LY（是否录用）=“NO”。

（15）IF DD（道德素养）=“差”AND ZY（专业素质）=“差” THEN LY（是否录用）=“NO”。

分析以上分类规则可以得出，道德素养好、专业素质优秀、实践能力较强的毕业生，符合用人单位录用标准，能顺利就业；如果道德素养较差，则须在毕业生的专业素质和实践能力上较为优秀，用人单位才会录用；对于道德素养和专业素质都较差的毕业生，用人单位一般不会录用。

4 结语

该文提取了河池学院毕业生追踪调查信息数据，通过与ID3和CART分类预测算法对比，选取决策树算法中的C4.5算法构建预测分类器，从用人单位的角度，进行预测用人单位的录用规则。通过对原始数据进行整合、集成等预处理，利用决策树技术，对预处理过的数据进行数据挖掘，构造分类决策树，产生分类规则，并测试其准确性。从决策树预测分类器选取的属性指标来看，以毕业生的德、智、能作为判断分类属性指标，具有普遍性，有较强的说服力。从测试结果看，该决策树预测模型具有生成规则易于理解、计算量较小和预测分类准确度较高等优点，能较好地识别用人单位对录用毕业生的能力和素质要求，从而能方便快速准确地预测用人单位录用毕业生的潜在标准，有利于部分民族地区高校及时准确地了解掌握用人单位对毕业生的需求标准，从而及时采取措施，调整培养目标，促进教育改革，提高毕业生就业能力。

参考文献

[1] 人力资源和社会保障部，中国就业促进会.关于就业结构性问题的研究[N].中国就业促进会网站，2014

[2] 高传勇，沈延兵.用人单位对高校畢业生录用标准的调查分析[J].中国青年研究，2005（6）：42-45.

[3] 魏顺平.教育数据的挖掘、分析、应用[J].中小学信息技术教育，2013（10）： 18-21.

[4] C.ROMERO，S.VENTURA.EDUCATIONAL. data mining： A survey from 1995 to 2005[J].Expert Systems with Applications，2007（33）：135-146.

[5] RYAN S.J.d. BAKER， KALINA YACEF. The State of Educational Data Mining in 2009： A Review and Future Visions[J].JEDM - Journal of Educational Data Mining，2009，1（1）：3-16.

[6] 屈百达，徐保国.就业问题的对策模型及其H_∞控制.控制工程[J].2008（15）：29-41.

[7] 刘斓，徐健锋.基于二进制关联规则提取算法的大学生就业竞争力分析[J].计算机科学，2009，36（3）：295-297.

[8] 张稳.恰汗·合孜尔.毕业生就业率预测及质量评估研究[J].计算机工程与科学，2009，31（5）：141-143.

[9] 韦丽梅.计算机类专业课程设置对就业情况的影响[J].计算机应用与软件，2009，26（10）：111-135.

[10] 程昌品，陈强.基于信息增益比的决策树用于毕业生就业预测[J].计算机仿真，2010，27（2）：299-302.

[11] 牛丽，陈珂，程媛.改进的层次分析法在就业综合评价中的应用[J].计算机仿真，2011，28（5）：376-375.

[12] 常志玲，王岚.一种新的决策树模型在就业分析中的应用[J].计算机工程与科学，2011，33（5）：144-145.

[13] 贺爱香.决策树在应用型本科高校就业管理中的应用研究[D].安徽：安徽大学，2011.

[14] S.RASOUL SAFAVIAN. DAVID LANDGREBE.A Survey of Decision Tree Classifier Methodology[J].IEEE TRANS ON SYSTEM，1991，21（3）：660-674.