决策树
决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。分类树（决策树）是一种十分常用的分类方法。它是一种监督学习，所谓监督学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。
一、决策树概述
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性(features)，叶结点表示一个类(labels)。
1. 决策树算法思想
决策树(decision tree)是机器学习中常见的分类与回归方法，是一种呈树形结构的判别模型。决策树可以看做一个互斥且完备的if-then规则集合。同时决策树还表示定义在特征条件下类的条件概率分布，条件概率分布将特征空间划分为互不相交的单元(cell)或区域(region)，每个单元定义一个类的概率分布就构成了一个条件概率分布。用决策树对需要测试的实例进行分类：从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。
决策树学习本质上是从训练集中归纳出一组分类规则，是训练数据矛盾较小，同时具有很好的泛化性能。决策树的损失函数通常是正则化的极大似然函数，学习的目标是以损失函数为目标函数的最小化。决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。
2. 决策树的基本流程
决策树学习通常是一个递归选择最优特征，并根据该特征对训练数据机型分割，使得对各个之数据集有一个最好的分类的过程。其算法可以描述为如下过程：
step0：如果特征数量很多，可以先在决策树学习开始之前对特征进行筛选，只留下对训练数据有足够分类能力的特征，其实就是数据降维（此步不是必须的！）
step1：构建根结点，将所有训练数据都放在根结点
step2：选择一个最优特征，按照这一特征把当前结点的数据分割成子集。如果这些子集已经能够基本正确分类，转step3；否则，对于每一个结点，转step2
step3：将该节点构建成叶结点
step4：在决策树构造完成之后，需要对决策树自下而上进行剪枝，将树变得更加简单，从而使得它具有更好的泛化能力（具体就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点）
经过上述过程之后，所有训练数据都被分到叶结点上，即都有了明确的分类，这就生成了一颗决策树。注意到，对于训练集能够进行正确分类的决策树可能有多个，也可能没有，我们需要的只是一个与训练集矛盾较小的决策树，同时具有很好的泛化能力（不仅仅对训练集有好的拟合，对测试集也应该有很好的预测）。从所有可能的决策树中选取最优决策树是NP完全问题，因此在实际中的决策树学习算法通常采用启发式方法，近似求解这一最优化问题，这样子得到的决策树是次最优的。
3. 决策树计算示例
生活中的决策树。今天我想网购台电脑，刷到一台看着挺带劲的机子，在决定买不买之前，我心路历程是这样的：这台笔记本价格还可以，7000 多，没超过 8000 ，在我的可接受范围内；emmm，牌子是 xxx ，名牌值得信赖；再看看配置i7，固态+机械，显存 8G，内存16G，这个配置一看就是游戏本，我喜欢。看看评价如何？这么多差评，差评率也太高了...告辞告辞。看到没，刚刚的心路历程就是一个决策过程。我通过品牌、价格、配置、差评率等属性来决定“买还是不买 ”。再举一个例子：给出如下的一组数据，一共有十个样本（学生数量），每个样本有分数，出勤率，回答问题次数，作业提交率四个属性，最后判断这些学生是否是好学生。
然后用这一组附带分类结果的样本可以训练出多种多样的决策树，最后一列给出了人工分类结果。
二、 决策树R实现
1. 决策树的数据结构
决策树用到的数据结构如下图所示。
Sepal.Length Sepal.Width Petal.Length Petal.Width Species
1 5.1 3.5 1.4 0.2 setosa
2 4.9 3.0 1.4 0.2 setosa
3 4.7 3.2 1.3 0.2 setosa
4 4.6 3.1 1.5 0.2 setosa
5 5.0 3.6 1.4 0.2 setosa
6 5.4 3.9 1.7 0.4 setosa
7 4.6 3.4 1.4 0.3 setosa
8 5.0 3.4 1.5 0.2 setosa
9 4.4 2.9 1.4 0.2 setosa
10 4.9 3.1 1.5 0.1 setosa
2. R处理程序
rm(list = ls())
install.packages("party")
library(party)
data(iris) #数据输入
head(iris,5)
#建构决策树模型
output<-ctree(Species~Sepal.Length+Sepal.Width+Petal.Length+Petal.Width,iris)
plot(output)
plot(output,type="simple")
3. 计算结果
predtree<-predict(output,iris) #利用预测集进行预测
table(iris$Species,predtree,dnn=c("真实值","预测值")) #输出混淆矩阵
预测值
真实值 setosa versicolor virginica
setosa 50 0 0
versicolor 0 49 1
virginica 0 5 45 #决策树模型的评估
4.泛化外推预测
row1=c(4.5,2.7,3.1,4.2,0)
names(row1)<-c("Sepal.Length","Sepal.Width","Petal.Length","Petal.Width","Species")
row1=t(row1)
row1=as.data.frame(row1) #泛化数据
lei<-predict(output,row1)
[1] virginica #所属类别
Levels: setosa versicolor virginica
三、总结
决策树（Decision Tree）算法是一种基本的分类与回归方法，是最经常使用的数据挖掘算法之一。我们这章节只讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。决策树学习通常包括 3 个步骤：特征选择、决策树的生成和决策树的修剪。这些基于树的学习算法被认为是最好和最常用的监督学习方法之一：决策树、随机森林、梯度提升等方法在各种数据科学问题中得到了广泛应用。对于每一个机器学习的初学者来说，学习这些算法并将其用于建模非常重要。
参考文献
(R语言——决策树模型)[https://blog.csdn.net/weixin_45387160/article/details/103335715]
