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

龙源期刊网算法研究作者：沈亮亮蒙祖强张兵郭英明来源：《软件导刊》2018年第06期摘要：大数据时代，数据量呈现爆炸式增长，且在内容与形式上日益复杂化，造成数据质量下降、数据丢失等，即产生不完备数据。提出一种改进的C4.5算法，使其能更好地处理不完备数据。每次特征选择前对本次特征选择的数据子集使用子集匹配方法进行处理，通过比较数据清洗方法与子集匹配方法的结果，显示即便是在相同清洗规则下，子集匹配方法在算法分类准确率上也更有优势。实验结果证明，在利用C4.5算法进行特征选择时，在该数据子集上对不完备数据进行处理，可以得到较高的分类准确率，同时得到比数据清洗高的时间复杂度。关键词：不完备数据；C4.5算法；分类算法DOI：10.11907/rjdk.172181中图分类号：TP312文献标识码：A文章编号：1672-7800（2018）006-0095-05Abstract：Intheeraofbigdata，datanotonlypresentsexplosivegrowthinquantity，butalsobecomesincreasinglycomplexincontentandform，resultinginthedeclineofdataquality.Anunavoidableproblemisthelossofdata，thatis，incompletedata.Inthispaper，animprovedC4.5algorithmisproposedtodealwithincompletedatabetter.Thespecificmethodistousethesubsetmatchingmethodtoprocesstheincompletedataonthesubsetofthefeatureselectionbeforeeachfeatureselection.Bycomparingtheresultsofdatacleaningmethodandsubsetmatchingmethod，itisshownthatsubsetmatchingmethodhastheadvantageofclassificationaccuracyevenunderthesamecleaningrule.TheexperimentalresultsshowthatitisreasonabletoprocesstheincompletedataonthesubsetofthedatasetwhentheC4.5algorithmisusedforfeatureselection，anditgetshigherclassificationaccuracy，butthismethodwillalsogethighertimecomplexitythanthatofdatacleaning.KeyWords：incompletedata；C4.5algorithm；classificationalgorithm0引言随着计算机技术以及网络通信技术的快速发展，数据规模在全世界范围内以指数级快速增长。在我国，随着大数据时代的到来，数据规模正从每天TB级汇聚量向PB级发展，中国电信发布的信息显示，至2017年3月末，其每天的数据汇聚量就达到200TB[1]。面对如此庞大的数据，如何从其中获取知识正受到人们越来越多的关注。如何对现实领域中的大量数据进行龙源期刊网有效处理，从而挖掘出潜在有用的知识，已成为当前数据挖掘、计算智能与机器学习的重要研究课题之一[2]。在大量数据中，有时会出现数据属性值丢失的情况，含有缺失属性值的数据称为不完备数据，由不完备数据构成的信息系统称为不完备信息系统。随着数据规模的快速发展，数据来源途径的多样化、干扰、误差、遗漏甚至人为因素等成为导致数据不完备的主要原因。不完备数据的出现是不可避免的，传递到不同的处理应用层次，体现为信息不完备、信息不确定、信息不准确、信息模糊、信息遗漏、信息冲突等互为交织的表现形式[3]。在数据挖掘、计算智能与机器学习等研究领域，分类算法是其核心。所以有必要对分类算法进行改进，以期扩展分类算法适用的数据范围。1数据处理常用方法一般的数据处理方法是在数据分类之前通过对丢失值进行填补，再对数据完备化或直接将包含丢失值的样本删除。填补法是将不完备属性值填补成完备的属性值，主要有2种方法：一是利用已有的属性值填充，即不完备的属性值可能是其它数据同属性的属性值；二是不用已有的属性值填充，而用某种方法获得其它属性值填补。为了提高数据质量，在具体应用上有许多种方法，比如使用数据清洗、聚类、粗糙集等填充不完备数据。文献[4]提出了一个基于限制容差关系的不完备信息系统，以及粗糙集模型面向不完备数据的数据挖掘系统模型。文献[5]以粗糙集为对象，提出了一种基于属性重要度的不完备数据填补算法，分析了属性重要度对于填补不完备数据缺失值的影响，并通过实验证明，与ROUSTIDA算法相比，该算法具有更高准确率。文献[6]以粗糙集理论为工具，针对动态不完备数据进行系统的特征选择研究，提出一种混合特征评估函数度量候选特征的区分能力，并设计出基于贪心向前搜索的特征选择算法。文献[7]提出基于不完备数据聚类的缺失数据填补方法（MIBOI），针对分类变量不完备数据集定义约束容差集合差异度，直接计算不完备数据对象集合内所有对象的总体相异程度，以不完备数据聚类的结果为基础进行缺失数据填补。删除法的思想是直接去除包含不完备属性值的数据样本，不处理法的思想是将不完备属性值当成一个可以应用的属性值进行计算。在面对不完备数据时，应用不处理或者删除方法时，会造成有用信息损失；应用替补法时，无法保证替补的不完备数据完全正确，甚至替补上错误的数据，对该数据的算法或者应用会造成巨大影响。总之，这些方法的缺点是人为改变了数据包含的信息结构，扭曲了数据本来包含的有用信息。除以上基于数据清洗的方法外，还有可以直接处理不完备数据而得到决策规则的方法。JerzyWGrzymala-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.2C4.5算法信息熵[16]是由CEShannon（信息论之父）在1948年发表的论文通信的数学理论（AMathematicalTheoryofCommunication）文中提出的，说明任何信息都存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者不确定性有关。CEShannon将热力学的熵引入到信息论中，目的是将信息量化。信息中排除冗余后的平均信息量被称为“信息熵”，信息熵计算的数学表达式[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算法可以递归实现，其基本算法如下：读入训练集，构造属性集与样本序号集，作为算法对应的样本集、属性集与样本序号集参数。Step1：递归算法TreeGenerate（样本集、属性集、样本序号集）开始，生成节点node。龙源期刊网：判断算法递归返回。若参数所有样本决策属性相同，将node类别标记为该决策属性的叶子节点并返回node；若属性集为空或者所有样本在属性集中所有属性上的属性值相同