基于训练集局部加权的C4.5算法改进研究

张扬武

摘要：C4.5算法采用信息增益率来构造决策树，克服了选择较多值的属性的趋向，具有处理连续属性的能力。在处理大数据集时，表现出效率较低，忽略样本集中的不同样本与测试数据的距离差异。该文提出了一种基于训练集局部加权的C4.5改进算法，根据欧式距离或汉明距离来定义样本的权值，将权值更新到训练集中，重新计算的信息增益率反映了训练样本的差异对测试数据的影响，并且在处理大数据集时，根据权值排序和设置的阈值简化数据集，降低了计算复杂度，提高效率。

关键词：C4.5；信息增益比；局部加权；数据集；邻近距离

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）16-0202-03

Abstract： C4.5 algorithm uses information gain-ratio to construct a decision tree， and overcome the tendency to select the attribute onmore values， with the ability to handle continuous attributes.But it showless efficient when dealing with large data sets and ignoring the differences of distance from the sample set and test data set.Based on training set weighted locally， This paper proposes a suite of algorithm of improvement for C4.5algorithm.The sample weights ，which are defined according to the Euclidean distance or Hamming distance， update to the training set.On this basis， information gain-ratio which is recalculated reflects the impact of the differences of distance from the sample set and test data set.Therefore，the proposed algorithm can reduces the computational complexity and improves efficiencywhen dealing with large data sets，using the simplifiedsample set based onweight sorting and the threshold.

Key words：C4.5； information gain-ratio； weighted locally； data set； near distance

1 概述

ID3算法根据计算信息增益，选择有较高信息增益的属性进行节点分裂，对于离散属性集Values来说，增加一个ID属性，每条属性都有不同的ID，计算信息增益时，属性ID产生的信息增益是最大的。如果选择属性ID分裂节点，将为每条数据产生一个分支，这是没有意义的。C4.5算法是ID3的改进算法，其核心思想是根据属性的信息增益率（Gain-ratio）代替信息增益（Information Gain）来选择属性分裂节点来构造决策树，信息增益率由选取属性的信息增益和按照选取的属性划分样本集的均匀性共同决定，克服了ID3算法趋于选择较多值的属性的缺点，通过断点来处理连续数据，在决策树构造过程中进行剪枝来解决过拟合问题，产生的规则易于理解[1]。

在实际应用中，样本集的分布情况会影响分类器的分类效果。有的样本集类别不均衡，存在大类和小类，有些属性对大类分类效果较好，有些属性对小类分类效果较好[2]。有的样本集属性不均衡，有的属性取值较多，而有的属性值取值较少。因此，分类器的好坏与训练集中的样本数据质量密切相关。数据集的选择应该分布较均衡，尽量选择具有代表性的数据。数据集中的不同样本对于测试数据的作用是不一样，例如，对于用来预测2015年房价的数据集，2014年的样本显然比2004年的样本更有用[3]。 C4.5算法基于统计学规律，根据信息熵来选择属性分裂节点，考虑的是静态的整体性，不是动态的整体性，它没有考虑测试集和训练集之间的距离关系。在K最近邻（k-Nearest Neighbor，KNN）算法中，如果一个测试数据在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别。这说明与测试数据邻近的样本对分类结果影响较大，在C4.5算法中，训练集中样本被同等对待，其差异并没有反映到决策树的构造过程中。因此，基于C4.5的改进算法在计算信息增益率时增加了样本的权值参数，使样本空间分布随测试数据的不同而发生变化，反映了训练集中的不同样本对待预测的测试数据影响也不相同，与测试数据距离较近的训练样本对预测结果影响较大，而远离测试数据的样本对预测结果影响较小[4]。

2 一种改进的C4.5算法

2.1 距离的衡量

3 结语

C4.5算法在构造决策树过程中，需要多次对数据集进行扫描和排序，导致效率较低。如果考虑训练集较大，受到内存容量限制无法装入到内存时，程序将无法运行。因此，C4.5算法适用于能够驻留内存的数据集使用。本文提出了一种基于训练集局部加权的信息增益率的计算方法，根据测试数据与训练样本之间的距离来定义样本的权值，更新的训练集导致信息增益率计算发生改变，反映了较近的训练样本对分类的重要影响。并且在处理大数据集时，根据权值排序调整数据集大小，降低了计算复杂度和树的复杂度。

参考文献：

[1] Witten IH，Frank E .Data Mining：Practical Machine Learning Toolsand Techniques[M].2nd ed.， San Francisco ：Elsevier Inc.，2005.

[2] AlmuallimH .On handling tree-structured attributes[C]// AshburnerM . Proc of the 12th IntConf on Machine Learning. San Fransisco ：Morgan Kaufmann ， 1995. 12-20.

[3] Wu Xindong，Kumar V，Quinlan J .Top 10 algorithms in data mining[J].Knowledge and Information Systems， 2008，14（1）：1-37.

[4] Moore AW， Zuev D， Crogan M. Discriminators for use in flow—based classification[R]. Technical Report， RR-05-13，London ：Queen Mary University of London，2005.

[5] Pawlak Z D，Quinlan J .Rough set theory and itsapplicationto data analysis[J].Cybernetics and Systems，1998，29（9）：611-668.

[6] Ghosh A K， Chaudhuri P，Murthy C A. Multiscale classification using nearest neighbor density estimates[J]. IEEE Transactionson Systems，Man，and Cybernetics，PartB：Cybernetics， 2006，36（5）：1139-1148.