面向不完备数据的改进C4.5算法研究

沈亮亮 蒙祖强 张兵 郭英明

摘 要：大数据时代，数据量呈现爆炸式增长，且在内容与形式上日益复杂化，造成数据质量下降、数据丢失等，即产生不完备数据。提出一种改进的C4.5算法，使其能更好地处理不完备数据。每次特征选择前对本次特征选择的数据子集使用子集匹配方法进行处理，通过比较数据清洗方法与子集匹配方法的结果，显示即便是在相同清洗规则下，子集匹配方法在算法分类准确率上也更有优势。实验结果证明，在利用C4.5算法进行特征选择时，在该数据子集上对不完备数据进行处理，可以得到较高的分类准确率，同时得到比数据清洗高的时间复杂度。

关键词：不完备数据；C4.5算法；分类算法

DOI：10.11907/rjdk.172181

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）006-0095-05

Abstract：In the era of big data， data not only presents explosive growth in quantity， but also becomes increasingly complex in content and form， resulting in the decline of data quality. An unavoidable problem is the loss of data， that is， incomplete data. In this paper， an improved C4.5 algorithm is proposed to deal with incomplete data better. The specific method is to use the subset matching method to process the incomplete data on the subset of the feature selection before each feature selection. By comparing the results of data cleaning method and subset matching method， it is shown that subset matching method has the advantage of classification accuracy even under the same cleaning rule. The experimental results show that it is reasonable to process the incomplete data on the subset of the data set when the C4.5 algorithm is used for feature selection， and it gets higher classification accuracy， but this method will also get higher time complexity than that of data cleaning.

Key Words：incomplete data； C4.5 algorithm； classification algorithm

0 引言

隨着计算机技术以及网络通信技术的快速发展，数据规模在全世界范围内以指数级快速增长。在我国，随着大数据时代的到来，数据规模正从每天TB级汇聚量向PB级发展，中国电信发布的信息显示，至2017年3月末，其每天的数据汇聚量就达到200TB[1]。面对如此庞大的数据，如何从其中获取知识正受到人们越来越多的关注。如何对现实领域中的大量数据进行有效处理，从而挖掘出潜在有用的知识，已成为当前数据挖掘、计算智能与机器学习的重要研究课题之一[2]。在大量数据中，有时会出现数据属性值丢失的情况，含有缺失属性值的数据称为不完备数据，由不完备数据构成的信息系统称为不完备信息系统。随着数据规模的快速发展，数据来源途径的多样化、干扰、误差、遗漏甚至人为因素等成为导致数据不完备的主要原因。不完备数据的出现是不可避免的，传递到不同的处理应用层次，体现为信息不完备、信息不确定、信息不准确、信息模糊、信息遗漏、信息冲突等互为交织的表现形式[3]。在数据挖掘、计算智能与机器学习等研究领域，分类算法是其核心。所以有必要对分类算法进行改进，以期扩展分类算法适用的数据范围。

1 数据处理常用方法

一般的数据处理方法是在数据分类之前通过对丢失值进行填补，再对数据完备化或直接将包含丢失值的样本删除。填补法是将不完备属性值填补成完备的属性值，主要有2种方法：一是利用已有的属性值填充，即不完备的属性值可能是其它数据同属性的属性值；二是不用已有的属性值填充，而用某种方法获得其它属性值填补。

为了提高数据质量，在具体应用上有许多种方法，比如使用数据清洗、聚类、粗糙集等填充不完备数据。文献[4]提出了一个基于限制容差关系的不完备信息系统，以及粗糙集模型面向不完备数据的数据挖掘系统模型。文献[5]以粗糙集为对象，提出了一种基于属性重要度的不完备数据填补算法，分析了属性重要度对于填补不完备数据缺失值的影响，并通过实验证明，与ROUSTIDA算法相比，该算法具有更高准确率。文献[6]以粗糙集理论为工具，针对动态不完备数据进行系统的特征选择研究，提出一种混合特征评估函数度量候选特征的区分能力，并设计出基于贪心向前搜索的特征选择算法。文献[7]提出基于不完备数据聚类的缺失数据填补方法（MIBOI），针对分类变量不完备数据集定义约束容差集合差异度，直接计算不完备数据对象集合内所有对象的总体相异程度，以不完备数据聚类的结果为基础进行缺失数据填补。

删除法的思想是直接去除包含不完备属性值的数据样本，不处理法的思想是将不完备属性值当成一个可以应用的属性值进行计算。在面对不完备数据时，应用不处理或者删除方法时，会造成有用信息损失；应用替补法时，无法保证替补的不完备数据完全正确，甚至替补上错误的数据，对该数据的算法或者应用会造成巨大影响。总之，这些方法的缺点是人为改变了数据包含的信息结构，扭曲了数据本来包含的有用信息。

除以上基于数据清洗的方法外，还有可以直接处理不完备数据而得到决策规则的方法。Jerzy W Grzymala-Busse等[8]根据缺失值的语义不同，将不完备信息系统中的缺失值分别定义为“丢失值”与“不关心值”，其中“丢失值”用“？”表示，不能用任何在该属性上的属性值替换，而“不关心值”用“*”表示，可用任意同属性上的属性值替换。根据缺失值的不同处理方式，有学者提出了一种新的基于特性关系面向不完备数据的粗糙集模型[9-10]。文献[11]提出了在面向不完备数据时，利用单体近似、子集近似与概念概率近似的性质进行数据挖掘，并通过实验证明，对于给定的数据集，3种方法都是高效的。

如果能在面向不完备数据时直接进行处理得到决策规则，最简单的方法是遍历决策树。Quinlan[12-13]在1986年提出的ID3算法是基于信息熵的决策树分类算法，还在1993年提出了ID3的改进版本C4.5算法，C4.5算法用信息增益率选择决策属性，它继承了ID3算法的优点，在ID3基础上增加了对连续属性的离散化、对未知属性的处理和产生规则等功能。C4.5算法在保留ID3算法优点的同时还改进了ID3的2个缺点：在对分支属性决策时，ID3使用信息增益这一指标进行度量，导致选择偏向于取值多的属性，这些属性是无效数据，而C4.5则使用信息增益率；ID3算法只能取离散数据，C4.5属性值既可以是离散值也可以是连续值，因为C4.5能够对连续数据进行离散化处理[14]。虽然C4.5的分类准确性高，但算法的效率比较低。

本文提出一种方法，在利用C4.5算法每次进行特征选择对不完备数据进行处理时，尝试应用数据预处理的思想对当前不完备数据中的缺失值进行替换，使C4.5算法能更好地适应不完备数据。

2 预备知识

2.1 不完备数据

在数据中，含有缺失属性值的数据称为不完备数据，由不完备数据构成的信息系统称为不完备信息系统。

以下原因经常导致不完备数据产生：①有的属性值是空值；②有些数据在当时认为不需要；③有些因误解而没有记录；④数据采集设备故障导致没有记录；⑤历史原因或忽略了修改数据；⑥有些数据性价比太低而被忽略。

在各种科学研究中，数据缺失现象非常普遍，不完备数据给数据的使用与分析带来了很大困难，是造成信息系统不确定的主要原因之一[15]，也是面向不完备数据处理方法越来越重要的原因。

丢失值的处理方法大体上分成3类：删除法、数据补齐法与不处理法。

删除法是将含有缺失值的样本删除，得到完备数据并加以利用，适用于含有缺失值的样本数在数据总样本数中所占比例非常小的情形。这种处理方法非常简单，但是会造成资源浪费，因此无法保证删除的样本中不包含重要信息。

数据补齐法是用某种方法将缺失值进行补齐，即是用某個值替换缺失值，具体的方法有人工填充、特殊值填充、平均值填充、热卡填充、K最近距离邻法、所有可能值填充、组合完整化法、回归、期望值最大化方法和多重填补法等。这些替换方法能提高数据挖掘的准确率，但无法保证替换是完全准确的，不正确的替换会带来噪声，也会产生错误的数据挖掘结果。

不处理法是不对数据进行完备化处理，直接利用不完备数据。除了一些能直接处理不完备数据的算法如贝叶斯网络与人工神经网络等之外，由于原理与数据类型等方面的原因，其它算法无法直接处理不完备数据，会产生不可靠的数据挖掘结果甚至错误的结果。

2.2 C4.5算法

信息熵[16]是由C E Shannon（信息论之父）在1948年发表的论文通信的数学理论（A Mathematical Theory of Communication）文中提出的，说明任何信息都存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者不确定性有关。C E Shannon将热力学的熵引入到信息论中，目的是将信息量化。信息中排除冗余后的平均信息量被称为“信息熵”，信息熵计算的数学表达式[17]如式（1）所示：

式（1）中，p-k表示数据集D中第k类样本所占的比例。Ent（D）的值越小，则D的纯度越高；信息量越小，度量值越小。

信息增益是一种能衡量样本特征重要性的方法，是有无样本特征对分类问题的影响差值。假设离散属性a有V个属性值{a1，a2，…，a-v}，如果使用a作为划分属性对样本D进行划分，则会产生V个分支节点，Dv则表示样本D在划分属性a上所有取值a-v的样本集合，各分支节点的权重|D-v|/|D|则可以计算出属性a对样本集D的“信息增益”了。计算公式如式（2）所示：

信息增益在分类算法上有非常重要的应用，决策树的ID3算法都使用信息增益理论选择划分属性或特征选择。信息增益越大，属性a对样本集D进行划分所获得的纯度提升越大，越有利于划分属性的选择，即选择划分的特征。

信息增益理论是有缺陷的，并不是信息增益高就可以作为划分属性。信息增益的计算方法是对属性值较多的属性有所偏好，比如标号属性。编号属性的信息增益远大于其它候选划分属性，每个编号都能生成1个节点，每个节点都只有一个样本，但这样的决策树并不具备泛化能力，对于新样本无法进行有效预测。

为了克服信息增益的缺陷，C4.5决策树算法忽略了直接使用信息增益，而是采用信息增益率[13]选择划分属性。如式（3）所示：

式（3）中，IV（a）如式（4）所示：

IV（a）称为属性a的固有值，属性a的属性值越多，即V越大，则IV（a）通常越大。

C4.5算法可以递归实现，其基本算法如下：读入训练集，构造属性集与样本序号集，作为算法对应的样本集、属性集与样本序号集参数。

Step 1：递归算法TreeGenerate（样本集、属性集、样本序号集）开始，生成节点node。

Step 2：判断算法递归返回。若参数所有样本决策属性相同，将node类别标记为该决策属性的叶子节点并返回node；若属性集为空或者所有样本在属性集中所有属性上的属性值相同而决策属性不同，将node标记为叶子节点，其类别标记为决策属性最多样本数的类并返回node。

Step 3：从属性集中选择信息增益率最高的属性作为特征属性。根据样本属性值的数据类型选择不同的计算信息增益率方法，若数据类型为离散型，则计算各属性值的信息增益率，信息增益率最高的属性作为特征属性；若数据类型为连续型，排序后取相邻2个值的中间值为候选特征属性值，取大于和小于该特征属性值的两个样本集计算信息增益率，取最大值作为该连续型候选特征属性的信息增益率，与其它候选特征属性进行比较，用信息增益率最高的属性作为特征属性。

Step 4：对特征属性的每一个属性值进行遍历，为node生成一个分支，其类别标记为属性值，分支样本集为node的样本集中所有特征属性为该属性值的样本集合，分支属性集为node去掉特征属性的集合，分支样本序号集为分支样本集中的样本在训练集中的序号集合；若分支样本集为空，标记分支节点为叶子节点，其类别标记为node样本集中样本最多的类。

Step 5：算法结束，输出以node为根节点的决策树。从该基本算法可得出，设定好输入与停止条件，算法可以自动生成一棵C4.5决策树，输入的训练集可以根据输入的属性集与样本序号集循环建树，也可以用整形数据表示决策属性。以UCI数据集为例，虽然每一个数据集都包含记录数据的数据文件和对数据各方面进行说明的说明文件，可以用于读入算法中要求的训练集和属性集，但是可以不用读入属性集，直接使用训练集中数据的属性编号作为分裂属性的属性名，其与读入内存数据表中属性的存储位置有关，样本序号集同样如此。其实只需要读入数据集就可以构建决策树。本质上C4.5算法在编程时也需要构建键-值对以对属性集中的属性名进行数字化。

因为C4.5算法的核心就是计算信息增益率，所以在面向不完备数据进行改进时，需要将改进的方法加入信息增益率的计算之前。

3 C4.5算法改进

本文提出一种方法，在C4.5算法每次进行特征选择对不完备数据处理时，应用数据预处理思想对当前不完备数据中的缺失值进行替换，使C4.5算法能更好地适应不完备数据。

在C4.5的递归算法Step 3中，每次选择特征属性前都会在当前样本集上计算信息增益率，在每次计算之前，对当前样本的不完备数据应用数据预处理思想进行一次处理，再计算信息增益率。每次处理的数据集都是开始输入的数据集子集，这种方法称为子集匹配。每个子集都是当前节点的父节点，利用信息增益率计算特征属性进行分支构建后得到的子集样本集，其样本在父节点的特征属性上是相同的，因此样本间存有關联，在这种情况下递归进行不完备数据缺失值的替换比使用数据预处理方法替换更好。使用这种方法得到完备数据能获得更高的分类准确率。用子集匹配得到的分类准确率与数据预处理之后得到的分类准确率进行比较，验证子集匹配方法的合理性。

为了证明面向不完备数据对C4.5算法的扩展，对数据集使用相同的数据预处理方法——最高频替换方法进行处理。在每一次清洗中，应用数据预处理与子集匹配2种方法，结果证明子集匹配的方法是合理的。在不完备数据中，如果在某个属性上出现缺失值，计算过程中使用在该属性上出现次数最多的属性值进行替代，即最高频属性值填充。用属性值（n）表示该属性值出现n次，则：

缺失值=属性值（MAX）

在C4.5算法的基础上，具体实验步骤如下：

第一步，对不完备数据集进行一次数据预处理，对数据集中的不完备数据用同属性数据中出现次数最高的数据进行替换。将数据集读入内存后，对读入的二维表进行遍历，首先遍历每一个属性，在遍历过程中，计算该属性中出现最高频率的样本（属性的属性值），对每一个属性中的样本再遍历一次，将其中不完备数据用最高频样本进行替换。将处理完成的完备数据表应用10折交叉验证方法，分为训练集与测试集，将训练集导入C4.5算法得到决策树，然后决策树对测试集进行分类，得到一次算法的分类正确率，重复10次得到10折交叉验证的平均分类正确率。

第二步，将训练集直接导入C4.5算法，每一次进行递归特征选择之前，对数据集中的不完备数据应用第一步中的最高频方法进行替换，用得到的完备数据集计算信息增益率，选信息增益率最高的属性作为特征属性，如此循环直到算法完成。用决策树对测试集进行分类，得到一次算法的分类正确率。重复10次得到10折交叉验证的平均分类正确率。

结果说明，子集匹配方法比数据预处理方法的分类准确率高，并且子集匹配方法也适用于不同的数据预处理方法。

4 实验分析

从UCI数据网（http：//archive.ics.uci.edu/ml/）随机挑选包含不完备数据的数据集Anneal、crx、 horse-colic、lung-cancer、sponge进行实验。

为了验证实验结果的有效性与可重复性，所有实验在个人计算机上实现，其配置为：Intel（R） Core（TM） i7-2640M CPU @ 2.80GHz，内存为4GB，操作系统是Windows 7，程序开发平台是EclipseSDK，编程语言是JAVA1.8。

从机器学习数据库中选取5个真实数据集分析算法的性能，数据集的详细情况如表1所示。

每一个数据集包含的样本数、属性数与包含不完备数据的不完备属性数都是在对数据集进行遍历时统计出来的。对于每一个属性来说，其包含的不完备样本数与该属性包含样本数的比是该不完备属性的不完备率或缺失率，而所有不完备属性的缺失率之和与不完备属性个数的比，是该数据集不完备属性的平均缺失率。

在Anneal数据集中，有5个属性的不完备缺失率是100%，即该属性中所有数据都是缺失的，缺失率在95%以上的不完备属性有9个，所以造成平均缺失率高达85.09%。对于不完备缺失率为100%的属性，由于其完全不具备区分度，对算法的结果没有影响，所以作删除处理。

早期工作发现，留一交叉验证虽然可以作为回归问题的渐近无偏估计，但是Shao Jun[18]的研究表明，在分类模型中不具有渐近无偏的良好性能。因此，Hastie[19]等使用5折交叉验证、10折交叉验证估计分类模型泛化误差以及对不同模型的性能差异进行检验。

本实验采用10折交叉验证方法计算算法的平均分类准确率，用于评估算法的分类准确度。对于每一个数据集，平均分成10份，取其中1份作为测试集，其它9份作为训练集，实验得到一次结果，即一次分类正确率。轮流取10份中的一份作为测试集做10次实验，其结果的平均正确率即是该算法的平均分类准确率。在实验时，还计算了方差和标准差用于衡量实验结果的分散情况及实验结果与其期望的偏差。

实验采用的评价标准是算法的分类准确率，分类准确率由测试集中分类正确的样本数与样本总数的比值得到，分类准确率越高，说明其对应的算法越合理。数据集通过本文设计的2组实验可以获得2组分类准确率，通过对比实验结果，可以了解哪种方法比较合理。在本实验中，使用了Anneal、crx、horse-colic、lung-cancer、sponge 5个数据集，实验的分类准确率如表2所示。

从表2可以看到，使用子集匹配方法相对于使用数据清洗的方法分类准确率要高。

对于子集匹配方法，其方差和标准差如表3所示。

从表3可以看到，分散情况和实验结果与其期望的偏差都不大，说明实验是有效的。

从以上两个实验结果中可以看出，在面向不完备数据进行C4.5分类算法的改进时，进行特征选择对不完备数据替换，尤其是在递归算法中，在每一个节点上的子集中对不完备数据进行替换，在同样的替换规则下可以获得比单纯数据清洗更高的分类正确率，说明对分类算法面向不完备数据的改进是成功的。而对于每一个数据集的分类结果，正确率都比较高，说明对C4.5分类算法的改进也是成功的。

5 结语

针对不完备数据，本文将最高频原理引入C4.5算法中，使得该算法能够更好地处理不完备数据。应用最简单的数据清洗思想：最高频属性值替换方法在进行特征选择的子集上对不完备数据进行替换。实验证明，本文算法在面向不完备数据时，能构造更简单的C4.5算法，而且精度较高。本文结果可以证明在分类算法中用数据清洗的思想扩大分类算法本身的适用数据范圍，使分类算法能更好地处理不完备数据。

参考文献：

[1] 吴章先.天翼大数据智能创未来数据共生态[EB/OL].http：//www.dca.org.cn/html/BDIC2017/index.html.

[2] 舒文豪.面向动态不完备数据的特征选择模型算法研究[D].北京：北京交通大学，2015.

[3] 崔伟正.面向分类决策的不完备信息处理方法研究[D].长沙：国防科技大学，2013.

[4] 梁美莲.不完备信息系统中数据挖掘的粗糙集方法[D].南宁：广西大学，2005.

[5] 徐雄英.基于粗糙集的不完备信息系统的处理方法研究[D].呼和浩特：内蒙古大学，2012.

[6] 舒文豪.面向动态不完备数据的特征选择模型与算法研究[D].北京：北京交通大学，2015.

[7] 武森，冯小东，单志广.基于不完备数据聚类的缺失数据填补方法[J].计算机学报，2012，8（35）：1726-1738.

[8] CLARK P， GRZYMALA-BUSSE J W， RZASA W. Consistency of incomplete data[J].Information Sciences，2015，322（5）：197-222.

[9] GRZYMALA-BUSSE J W. Characteristic relations for incomplete data：a generalization of the indiscemibility relation[C].Lecture Notes in Computer Science，2004：58-68.

[10] GRZYMALA-BUSSE J W， CLARK P G， KUEHUNHAUSEN M. Generalized probabilistic approximations of incomplete data[J].International Journal of Approximate Reasoning，2014，55（1）：180-196.

[11] CLARK P G， GRZYMALA-BUSSE J W， RZASA W. Mining incomplete data with singleton， subset and concept probabilistic approximations[J]. Information Sciences，2014，280：368-384.

[12] HAN J W， MICHELINE K.数据挖掘：概念与技术[M].范明，孟小峰，译.北京：机械工业出版社，2001.

[13] QUINLAN J R. C4.5：Programs for machine learning[M]. San Mateo： Morgan Kauffman，1993.

[14] 光峰，姚程宽，卢灿举，等.数据挖掘经典算法研究[J].商丘师范学院学报，2016，32（3）：44-47.

[15] 李然.粒计算的高效知识约简算法与缺失数据处理[D].兰州：兰州大学，2006.

[16] LIU C Y，GUO H，HU W. A Schr（o）dinger formulation research for light beam propagation[J]. Science China Mathematics，2000，43（3）：312-322.

[17] 许朝阳.文本分类中特征选择方法的分析和改进[J].计算机与现代化，2010（4）：37-39.

[18] SHAO J， RAO J N K. Standard errors for low income proportions estimated from stratified multi-stage samples[J]. The Indian Journal of Statistics， Series B（1960-2002），1993，55（3）：393-414.

[19] HASTIE T， TIBSHIRANI R， FRIEDMAN J. The elements of statistical learning[J]. Journal of the Royal Statistical Society，2009，167（1）：267-268.

（责任编辑：刘亭亭）