机器学习中分类算法之决策树

本期和大家共同学习五种常见机器学习分类算法之决策树(Decision tree)，能力有限，可能只涉及其表面，有待感兴趣的童鞋深入挖掘。

顾名思义，决策树学习算法以树形结构建立模型，类似于流程图，该模型本身包含一系列逻辑决策，带有根据某一属性特征作出决定的决策节点(如下图中的椭圆形)，从这些决策节点引出的分枝表示可作出的选择，数据中每一条记录都会汇集到叶节点(如下图中的矩形)终止，并在叶节点被分配一个预测类。

从代表整个数据集的根节点开始，决策树算法选择最能预测目标类的特征，也即对分类贡献最大的变量特征，然后训练案例将被划分到这一特征的不同取值组中，这一决定形成了第一组树枝；该算法继续分而治之其他决策节点，每次选择最佳的候选特征，直至达到停止的标准：

节点上几乎所有的案例都属于同一类

没有剩余的特征来分辨案例之间的区别

决策树已经达到预先定义的大小限制

那么，怎么在每个决策节点选取到最佳的候选特征呢？别怕，有构建决策树的行业标准——C5.0算法来帮你自动完成这个听起来很头大的过程，害怕看原理的童鞋可以直接拉到最后看实例演练。

C5.0算法的原理是利用熵度量包含不同分类的一组数据的纯度，最小值0表示的样本是完全同质的，而1表示样本最凌乱。定义公式如下：

对于给定的数据分割S，常数c代表类的水平数，pi代表落入类的水平i中的特征值的比例。举个例子！比如现在有1000个体检者的血清检查数据，其中乙肝表面抗原(HBsAg)阳性者占比8%，阴性者占比92%，则该数据的熵为：(-0.08*log2(0.08)-0.92*log2(0.92))=0.4021792。假如，现在根据体检者的血小板压积的阈值将体检人群分为两大类，那么每一类中都包括HBsAg阳性和阴性，分别计算两大类的熵值并加和，得到按照血小板压积这个特征分割后的数据分区S1的熵值，那么特征“血小板压积”的信息增益InfoGain=Entropy(S1)-Entropy(S)。每次选取信息增益最大的特征进行决策节点的再次分割依据即可。

显然，只要可用于分割的特征足够多，一棵决策树可以无限制地增长，分割成越来越小的分区直到每一个案例完全归类。然而，如果决策树增长过大，将会使许多决策过于具体，模型将会过度拟合训练数据，而修剪一棵决策树的过程涉及减小它的大小，以使决策树能更好地推广到未知的数据。两种修剪策略：①预剪枝：一旦决策树达到一定数量的决策或者决策节点仅含有少量的案例，就提前停止树的增长；②后剪枝：生成一棵决策树后，根据节点处的错误率使用修剪准则将决策树减小到更合适的大小。后剪枝通常更有效，因为如果没有事先生成决策树，要决定一棵决策树生长的最佳程度是相当困难的，而事后修剪肯定可以使算法查到所有重要的数据结构。C5.0算法可以采用事后修剪策略进行自动修剪。

实例演练

数据包含1000名体检者的人口学和血常规、尿常规及乙肝表面抗原血清学检查结果，共35个特征变量，最后一列为HBsAg阴性阳性的标识。

#设置工作目录

setwd("D:\\学海拾贝之统计\\数据源")

#读取数据

data=read.csv("decision tree.csv")

#随机排序

set.seed(20180606)

data=small[order(rnorm(1000)),]

#选取900例为训练数据，100例为测试数据

train=small[1:900,]

test=small[901:1000,]

install.packages("C50")

library(C50)

#构建决策树模型

model=C5.0(train[,-35],train$HBsAg)

model

summary(model)

plot(model)

prediction=predict(model,test)

install.packages("gmodels")

library(gmodels)

CrossTable(test$HBsAg,prediction,prop.chisq = F,prop.c =F,prop.r = F,

dnn=c("actual","predicted"))

这里我们可以看到，相较于上期分享的朴素贝叶斯分类算法，决策树算法可以同时处理数值型、名义特征及缺失，且准确度达87%也是不错的表现。后期模型性能的提升可通过boosting算法，设置trials=10尝试采用自助法，综合10棵树的表现来预测分类；或者设置代价矩阵costs，比如临床上普遍认为假阴性的损失较假阳性惨重10倍，令costs=matrix(c(0,1,10,0),nrow=2)等。

本期分享到这里结束，请读者朋友们批评指正！

参考文献：BrettLantz, 兰兹, 李洪成,等. 机器学习与R语言[M].机械工业出版社, 2015.