C4.5主要思想与决策树实例

原文地址：http://blog.sina.com.cn/s/blog_6934cecb0101a7kc.html

ICDM于2006年底评选数据挖掘十大经典算法，C4.5（分类决策树）居首，前五名算法分别是C4.5, k-Means, SVM, Apriori, EM。大部分的算法对我们都很熟悉。C4.5居首主要因为其简单易懂，可解释性强。特别是在企业的具体业务应用过程中，模型的可解释性占有相当大的权重。

本文主要基于R介绍决策树，并简单介绍一下随机森林。

1、决策树简介：

决策树是一颗倒长的树，主要由根节点、分支、叶节点组成，每一个分支是一条规则，主要用于分类。

决策树的算法主要有ID3、C4.5、CART，其中最为流行的事C4.5算法。针对每一种决策树的算法都要解决两个主要问题：

1、选择哪个属性来分裂？

2、什么时候树停止生长？

C4.5之所以流行的原因是：

1、用信息增益率来选择属性分裂

2、构造树的过程中进行剪枝

3、能处理连续型数据和不完整数据

这里主要介绍一下如何选择属性（第一条）分裂对于规则来说是合适的，这就引出“熵”的概念。简而言之，“熵”是对混乱程度的度量，越乱熵越大，这也是为什么我让办公桌乱的原因。与之相对应的概念是“序”，就是有规律。越有序，越纯，熵越小；越乱，熵越大，越不纯；（这对后面理解很有帮助）。

我们从数学的角度来看，(以下图片均来自Introduction to data mining)

熵的计算公式：

其中，p(i|t)表示节点t中属于类i所占的比例；

以下为熵和Gini的图表，可以看出在熵和Gini在0.5处值最大，也可以说，数据类别分布倾斜，熵和Gini越少；

一个计算实例：



为了确定选择属性的分裂结果，我们用划分前（父节点）的不纯度和划分后（子女节点）的不纯度的差来来衡量属性分裂的测试结果，该指标成为信息增益，也就是熵的差，计算公式如下：

I(parent)是节点的值不纯性，k是属性的个数，决策树归纳通常选择最大化信息增益的属性做分裂；但是这样做有一个缺点：基于熵和Gini的不纯性的度量趋向于选择类别多的属性做分裂。可以这样理解，二元划分实际上相当于合并了多路属性，这个也可以用公式计算证明。那如何解决这个问题呢？有两种方法：一是限制测试属性只能是二元划分（这是CART的思想），二是修改衡量规则，于是C4.5提出采用信息增益率来划分（终于把第一条说完了），把属性测试产生的输出数也考虑进去，计算公式如下：

其中，

以上就是C4.5采用信息增益率做属性划分的思想。

2、实例：

以下实例参考了;
数据集iris包含五个指标萼片长度、萼片宽度、花瓣长度、花瓣宽度、三种花类型；

str(iris)
set.seed(1234)

#从iris数据集中随机抽70%定义为训练数据集，30%为测试数据集

ind <- sample(2, nrow(iris), replace=TRUE, prob=c(0.7, 0.3))
trainData <- iris[ind==1,]
testData <- iris[ind==2,]

library(party)

#建立决策树模型预测花的种类
myFormula <- Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width
iris_ctree <- ctree(myFormula, data=trainData)

# 查看预测的结果

table(predict(iris_ctree), trainData$Species)

               setosa versicolor virginica
  setosa         40          0         0
  versicolor      0         37         3
  virginica       0          1        31
通过训练数据测试，模型的预测准确性为96.4%;

#输出决策树图

plot(iris_ctree, type="simple")

 

testPred <- predict(iris_ctree, newdata = testData)
table(testPred, testData$Species)

在测试集上的准确性为94.4%，模型有较好的泛化能力。

也可以用rparty包做决策树，用rparty代替ctree

rpart(myFormula, data=trainData）

3.模型的误差

一般情况下，我们会把数据分成训练数据集合测试数据集，通过训练数据集训练模型，然后通过测试数据集测试模型。模型在训练数据上的误差叫训练误差，模型在测试数据上的误差成为泛化误差，泛化误差是模型在未知记录上的期望误差。一个好的模型应该有低训练误差和低泛化误差。

一种最常见的情况是，模型在训练数据集上误差小，但是泛化误差大，常称为模型的过度拟合。导致模型过度拟合的原因主要有以下两点：

1、噪声； 2、样本缺乏代表性；

为解决模型的过度拟合问题，我们经常使用对决策树后剪枝的方法，这样需要我们在建立模型的过程中，尽量建立一棵大树，然后基于数据的支持度和业务的理解对树进行剪枝。

在模型选择过程中，相同条件下，我们更倾向于选择简单易解释的模型。 
在标注样本量较大的情况下，我们可以通过建立多个模型，并采用N折交叉进行检验，具体可以参考吴老师的《基于R的复杂数据统计方法》。