机器学习

• 六、经典机器学习方法
• • 1. 支持向量机（Support Vector Machines）
  • • 1.1 支持向量机的简介和由来
    • 1.2 支持向量机的数学原理
    • 1.3 支持向量机的优缺点
    • 1.4 支持向量机在python中的分类应用
    • 1.5 支持向量机在python中的回归应用
  • 2. 隐式马尔可夫链（Hidden Markov Model）
  • • 2.1 序列数据
    • 2.2 马尔可夫链
    • 2.3 隐式马尔可夫链
    • 2.4 隐式马尔可夫链的最大似然概率
    • 2.5 隐式马尔可夫链的后验分布
    • 2.6 隐式马尔可夫链的python应用
  • 3. 决策树和随机森林
  • • 3.1 决策树
    • 3.2 决策树的优缺点
    • 3.3 决策树的python应用
    • 3.4 随机森林
    • 3.5 随机森林的优缺点
    • 3.6 随机森林的python应用

六、经典机器学习方法

1. 支持向量机（Support Vector Machines）

1.1 支持向量机的简介和由来

支持向量机（Support Vector Machines，SVM）是一种有监督性机器学习模型，是一般化线性分类器。支持向量机的特点是同时最小化经验误差与最大化几何边缘区，所以支它也称为最大边缘区分类器。支持向量机使用一个超平面将实验数据分类成为两组。通俗的讲，把实验数据的点映射在一个空间（比如一个二维空间平面）内，支持向量机将会找到一个次级空间（二维空间下为一条线），这个次级空间（也就是超平面）将作为一个分界线，把这个空间中的数据点分成两组，每组中的点对应一个类别，这样就把原来的数据集分成了两类。与简单的线性分类不同，支持向量机的分界线不是一条直线，而是一段空间（超平面）。而且支持向量机可以接受软标签，即一个数据点同时按比例属于两个类别。在将数据点映射到空间的过程中，支持向量机可以利用核函数将线性不可分的数据点群转换为线性可分的，以此支持向量机也可以进行非线性分类。比如原本数据分布是下图

使用核函数进行映射之后可以变成下面可以线性分类的：

这种使用非线性内核的方法可以将非线性问题化成线性问题。在算法中使用内积的任何地方，都可以用内核（核矩阵）替换它。内核充当一种“相似性”度量，并且可以在图形，集合，字符串和文档上进行定义。而这种使用核函数（核矩阵）的算法叫做稀疏内核机（Sparse Kernel Machines），支持向量机只是稀疏内核机中最为著名的一种代表性算法。

支持向量机是在简单的线性分类上进行的一种改进。在线性分类中，边界线可能存在多个，如下图，三条分界线都可以对实验数据进行准确分类

而为了找到更加精准的分界线，使用支持向量机寻找边界间距（margin）最大的分界线。边界间距（margin）是决策边界与任何样本之间的最小距离，如下图。支持向量机通过寻找最大化的边界间距，来找到最优的分界线。

1.2 支持向量机的数学原理

支持向量机要使得边界间距最大，首先在作为边界线的超平面（hyperplane）的斜率为w，常数项为b。对于每一个点x_n，理性的分类结果是t_n * y(x_n)>0，而点x_n到分界线的距离为
。
寻找最大边界问题就变成了求解下述式子取到最大值时的w和b值

假设上面式子中括号部分的最小值为γ，那么式子就化为

对于所有可能的w和b对应下的上面式子都除以γ，那么不改变何时取到最大值，所以可以假设γ=1。原本中括号部分要大于等于γ，现在变为大于等于1。那么决策边界的规范表示（canonical representation）是
通过变换将求解最大值转化为求解最小值即

然后引入拉格朗日乘数（Lagrange Multipliers）进行求解。最优化问题中，拉格朗日乘数法是一种寻找多元函数在其变量受到一个或多个条件的约束时的极值的方法，即在g(x₁,x₂)=0的条件下寻找函数f(x₁,x₂)的极值点。数学表示为
为了求解上面式子，引入新变量拉格朗日乘数λ，求解下列拉格朗日函数的极值
对拉格朗日函数对x求偏导数使其为0，来求得极值点x，
对拉格朗日函数对λ求偏导数使其为0可以得到原来的限制条件，
使用拉格朗日函数求解极值点x和λ要满足KKT限制条件（Karush-Kuhn-Tucker ），数学表达为
一般情况下，对于具有不同限制条件个g(x)和k个h(x)，求解f(x)的极大值点，有下面拉格朗日函数
对应的KKT条件是

现在回到支持向量机的超平面求解，目的是求解下面式子

构造成拉格朗日函数为

上面式子对w和b分布求解偏导数得到
将这两个偏导数的式子代入之前的L(w,b,a)中得到消减去w和b的拉格朗日函数，原来的最大化求解问题转化为求解下面L(a)的最大值（原问题的Dual representation）

由偏导数式子中的w式子可以得到分界线的斜率，此时分界线函数可以表示为（仍带有未知数b）

而KKT条件变为

现在求解分界线的另一个参数b。对于支持向量满足t_n * y(x_n)=1，所以代入y的表达式得到

此时可以通过任意一个支持向量来求解b值，但是为了结果的问题和正确，将上面式子乘以t_n以便使用所有支持向量的均值，如此得到b的值为

1.3 支持向量机的优缺点

• 优点

1. 适用于高维空间：在维数大于样本数的情况下仍然有效。
2. 支持向量机是内存高效，因为它在决策函数中使用训练点的子集（称为支持向量）。
3. 强大的通用性：支持向量机可以通过为决策函数指定不同的内核函数来处理非线性问题。支持向量机提供了通用内核，但也可以指定自定义内核。

• 缺点

1. 当特征数量远大于样本数量，支持向量机容易过拟合。在选择核函数时需要考虑避免过度拟合，加入合适的正则化项。
2. 支持向量机不直接提供概率估计，为了计算结果的概率需要进行交叉验证计算。
3. 支持向量机支持密集数据和稀疏数据，但要是对稀疏数据进行预测，那么输入（fit）的也要是稀疏数据。

1.4 支持向量机在python中的分类应用

支持向量机在python中可以进行分类，对应函数是sklearn中的SVC函数，即sklearn.svm.SVC()。SVC全称是C-Support Vector Classification，实现基于libsvm（一个支持向量机的苦函数）。 SVC训练中的拟合时间至少与样本数量成二次方关系，所以SVC不适用大数量的样本训练。 对于大型数据集，可以使用LinearSVC 或着使用梯度下降方法即SGDClassifier。SVC函数具体为sklearn.svm.SVC(*, C=1.0, kernel='rbf', degree=3, gamma='scale', coef0=0.0, shrinking=True, probability=False, tol=0.001, cache_size=200, class_weight=None, verbose=False, max_iter=- 1, decision_function_shape='ovr', break_ties=False, random_state=None)，其中C代表正则化参数，正则化的强度与 C的值 成反比，而且C必须严格为正；kernel代表在支持向量机算法中使用的内核类型，可以是“linear”、“poly”、“rbf”、“sigmoid”、“precomputed”中一个；degree是核函数的维度；gamma设置内核“rbf”、“poly”和“sigmoid”的核系数；probability代表是否启用概率估计；tol是停止拟合的阈值；max_iter是迭代的最大次数；decision_function_shape代表返回的决策函数形状；random_state控制伪随机数生成。下面是具体实例。

import numpy as np
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
X = np.array([[-1, -1], [-2, -1], [1, 1], [2, 1]]) #训练集数据
y = np.array([1, 1, 2, 2]) #训练集的目标值
from sklearn.svm import SVC #导入支持向量机函数
clf = make_pipeline(StandardScaler(), SVC(gamma='auto'))
clf.fit(X, y) #向支持向量机函数中输入训练集数据
#生成支持向量机模型 Pipeline(steps=[('standardscaler', StandardScaler()), ('svc', SVC(gamma='auto'))])
print(clf.predict([[-0.8, -1]])) #打印支持向量机预测分类的结果
#预测分类的结果是[1]

#也可以使用clf.score(X, y[, sample_weight])计算测试集数据和标签的平均准确率。

对于支持向量机中的模型选择，可以根据训练的样本数量和每个样本的特征数量进行判断。使用m表示训练集的样本个数，n表示每个样本特征数，那么当n>=m，比如n=10000，m=1000时，建议用逻辑回归模型（logistic regression）， 或者内核为linear kernel的SVM；当n比较小，m的值适中时，比如n=100，m=1000时可以使用内核为Gaussian Kernel的SVM模型；当n很小，m很大，如n=100，m>50000，要想办法增加更多的特征并使用逻辑回归（logistic regression,）或者内核为linear的SVM。

1.5 支持向量机在python中的回归应用

支持向量机在python中可以进行回归应用，对应函数是sklearn中的SVR函数，即sklearn.svm.SVR()。SVR的全称是Epsilon-Support Vector Regression，同样基于libsvm实现。与SVC一样，SVR的时间复杂度也超过样本数量的二次方，同样不适用于大样本的数据训练。对于大型数据集，考虑使用线性模型的支持向量机LinearSVR 或着是使用梯度下降求解回归的方法SGDRegressor。SVR函数具体为sklearn.svm.SVR(*, kernel='rbf', degree=3, gamma='scale', coef0=0.0, tol=0.001, C=1.0, epsilon=0.1, shrinking=True, cache_size=200, verbose=False, max_iter=- 1)，其中kernel指定要在算法中使用的内核类型；degree是核函数的维度；gamma设置内核“rbf”、“poly”和“sigmoid”的核系数；tol是停止拟合的阈值；C是正则化参数；epsilon代表epsilon-SVR 模型中的 Epsilon值，它指定了 epsilon 管（epsilon-tube），在该 epsilon 管中，训练损失函数中没有与实际值距离 epsilon 内预测的点相关的惩罚；cache_size指定内核缓存的大小；verbose如果为true，则可能无法在多线程上下文中正常工作；max_iter是迭代的最大次数。下面是一个简单实例。

from sklearn.svm import SVR
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
import numpy as np
n_samples, n_features = 10, 5 #训练集的样本数量和每个样本的特征数量
rng = np.random.RandomState(0) #用于随机生成数据
y = rng.randn(n_samples) #生成训练数据的目标值，即标签
X = rng.randn(n_samples, n_features) #生成训练数据
regr = make_pipeline(StandardScaler(), SVR(C=1.0, epsilon=0.2)) #使用make_pipeline构建SVR模型
regr.fit(X, y) #向模型输入数据
#回归向量机的结果是 Pipeline(steps=[('standardscaler', StandardScaler()),('svr', SVR(epsilon=0.2))])
#可以使用regr.predict(X)对测试集进行预测

2. 隐式马尔可夫链（Hidden Markov Model）

2.1 序列数据

许多数据，比如心率，股票价格等，当前的数据可能与之前的数据有关，并不是互相独立的。观察到的数据的分布可能会随着序列的进行而改变。这种类型的数据称为序列数据（Sequential data）。有一点要注意，使用“过去”和“未来”来描述观察的顺序，但序列的概念不限于时间序列。序列数据分为固定式序列数据（Stationary Sequential data）和非固定序列数据（Nonstationary Sequential data）。固定式序列数据是指数据随时间演变，但数据的分布保持不变。非固定序列数据是指数据生成分布随时间而变化。这一节主要处理固定式序列数据。

对于研究序列数据的模型，目标是预测序列上下一个时间点的数据值。为了简化模型，统称要假设不是之前所有数据都会对下一个数据点产生影响。但是即便如此，随着序列时间进行，依旧要存储大量的历史数据观测值，否则之前的数据就会遗失。这种假设最简单的情况就是当前数据仅会被上一个数据影响，和之前其他数据无关，这时候可以引入马尔可夫链（Markov process）建立模型。

2.2 马尔可夫链

马尔可夫链是一种描述一系列可能事件的随机模型，其中每个事件的概率仅取决于前一个事件中获得的状态。普通的序列数据每个数据点的概率可以使用之前数据点的条件概率的乘法链式法则得到，数学表达为

如果我们假设当前数据仅会被上一个数据影响，即每个条件概率仅取决于最近的数据，那么上面式子就变为，也就是一阶马尔可夫链（First-order Markov chain）

使用图像表示一阶马尔可夫链为（一阶马尔可夫链的graphical D-separation）

如果先前观察中的趋势变化为预测下一个值提供了重要信息，那么为了表示趋势，至少需要两个先前的观察结果，即当前数据点和之前最近的两个数据点有关系。这个假设中的条件概率取决于之前两个数据点，是二阶马尔可夫链（Second-order Markov Chain），它的数学表达式和图像表示为

依此类推，可以有M阶马尔可夫链（M^th-order Markov chain），它的数学式子为

2.3 隐式马尔可夫链

在介绍隐式马尔可夫链之前，要先引入状态空间模型（State Space Model）。对于每一个观察变量x_n，都可以加入一个对应的隐藏变量（latent variable）z_n。z_n的数据类型和数据维度都可以与x_n不同。如果隐藏变量是一个马尔可夫链，那么x_n和z_n的联合概率可以使用x_n和z_n之前时刻的条件概率相乘得到，即

如果使用D-separation图像表示为
引入状态空间模型后，如果观测值和隐藏值都是连续的（continuous），此时这个模型为线性动量系统（Linear Dynamical System）。特别情况下，隐藏值和观察到的变量都是高斯的，条件分布对它们的父变量具有线性高斯依赖性。如果隐藏值是离散的（discrete），无论观测值是连续的还是离散的，此时的模型都成为隐式马尔可夫链（Hidden Markov Model），简称HMM。

隐式马尔可夫链就是带有离散隐藏变量的状态空间模型，它的数学表达为（观测变量x_n对应的隐藏变量是离散可乘变量z_n）
假设隐式马尔可夫链为1-in-K编码方案，即每个隐藏变量z_n有K个不同状态。最初的隐藏变量为z₁，它的边沿分布（marginal distribution）取决于K维概率向量π，其中π_k=p(z_1k=1)，所以有
对于条件概率p(z_n|z_n-1)则是一个K * K的矩阵，记为A，也称为转移概率（transition probabilities）。对于A中每一个值都有A_jk=p(z_n,k=1|z_n-1,j=1)且满足每个值在0到1之间，而它们的和为1。为了使用图像表示转移概率A，有两种方法：Transition Diagram和Unfolded Transition Diagram。以一个3 * 3的转移矩阵为例，转移矩阵的数学表达为
下面图为Transition Diagram法，其中红色，绿色和蓝色三种方框代表三个隐藏变量的状态，黑色箭头指向了对应两种状态间的转换。
而下面这个图为Unfolded Transition Diagram法，下面的每一列都对应一种隐藏变量z_n，每一步中的格子（lattice或trellis）对应一种状态中三个分量。

为了完成隐式马尔可夫链的定义，还要引入发射概率（emission probabilities）p(x_n|z_n, φ) ，其中φ是控制条件分布的参数的集合。对于每个观察到的x_n，对应的φ也是确定的，而对于隐藏变量z_n的K个状态，排放概率p(x_n|z_n, φ)是一个K维的向量，使用数学表达为
对于隐式马尔可夫链，要注意它的转移概率（Transition probability）A是一个马尔可夫链，即它的隐藏变量z_n满足T(z_n-1, z_n)=p(z_n|z_n-1)。如果一个隐式马尔可夫链的转移概率满足p(z_n|z_n-1)=p(z_n-1|z_n-2)，即每一步的转移概率一样，这个隐式马尔可夫链称为同质的（homogeneous）。对于一个homogeneous的隐式马尔可夫链，它的联合概率分布（Joint probability distribution）满足（其中θ ={π,A, φ} ）
隐式马尔可夫链还可以有其他特定限制，比如Left-to-right的HMM，即从k=1的初始状态开始，从左到右进行序列，每一个状态的左边是无法重新到达的。

2.4 隐式马尔可夫链的最大似然概率

对于一个给定的隐式马尔可夫链，它的节点数和发射概率格式都是固定的，已经得到观测值X，那么它的似然概率是
这个联合分布是无法对于n因式分解的（factorise）。N个变量，每个有K种状态，总共是K^N个项（terms）。项数随着链的长度呈指数增长。为了简化计算，可以使用隐藏变量的条件独立性来重新排序它们的计算，而计算最大似然概率（Maximum Likelihood）的另一个困难是计算不同状态 z_n 的发射概率。实际计算中，采用EM算法计算隐式马尔可夫链的最大似然概率。初始化步骤为初始化θ^old ={π,A, φ} 参数。E步为计算隐藏变量的后验分布（posterior distribut=ion ）p(Z|X,θ^old)。M步为计算将下面式子最大化下的θ值
使用γ(z_n)表示 z_n 的边沿后验分布，ξ(z_n-1,z_n)表示两个连续隐藏变量的联合后验分布，且有γ(z_n)是K个和为1的非负数，ξ(z_n-1,z_n)是K * K的和为1的非负数。γ(z_n)和ξ(z_n-1,z_n)的定义为

基于二元随机变量的期望是它为 1 的概率，γ(z_n)和ξ(z_n-1,z_n)的每个分量为
将γ(z_n)和ξ(z_n-1,z_n)的表达式代入EM算法中M步的Q(θ,θ^old)值求解中得到
在M步通过将Q(θ,θ^old）最大化，求解得到A和π的值为
此时虽然φ值还没求得，但是 φ 只出现在最后一项，并且在所有 φ^k相互独立的假设下，这一项可以解耦为一个和。那么最大化Q(θ,θ^old)中最后一项是可以独立进行的。当发射概率（emission densities）是高斯分布时，有
其中这个高斯分布的均值和标准差满足

2.5 隐式马尔可夫链的后验分布

通过EM算法，隐式马尔可夫链最大似然概率求解的重点变成求解边沿后验分布和联合后验分布即γ(z_n)和ξ(z_n-1,z_n)。隐式马尔可夫链的图像是一棵树。一般情况下，可以使用两阶消息传递（two-stage message passing）算法来计算隐藏变量的后验分布。对于隐式马尔可夫链，这种方法称为前-后向算法（Forward-Backward算法）。前-后向算法存在其他变体，仅在传播的消息形式上有所不同。现在使用最广的变体方法是alpha-beta算法。

首先定义所有n个观测值x₁到x_n和隐藏变量z_n的联合概率为α(z_n)=p(x₁, … ,x_n,z_n)。定义所有基于隐藏变量z_n得到的未来数据x_n+1到x_N的概率为β(z_n)=p(x_n+1, … ,x_N|z_n)。因为从观测状态集合x₁到x_n，达到未来状态集合x_n+1到x_N，必须通过隐藏变量z_n，所以这两个集合在z_n的条件下是相互独立的。基于此可以得到下面两个递归式子（α recursion）：

可以使用上面式子在第n步基于α(z_n-1)计算得到α(z_n)，同时还可以根据下面式子计算得到β(z_n)，
对于β(z_N)=p(x_N+1, … ,x_N|z_n)，总是存在β(z_N)=1，可以将其作为beta递归过程的开始。下面进行每一步中α(z_n)和β(z_n)。根据之前γ(z_n)的定义和贝叶斯公式可以得到
根据之前提到的从观测状态集合x₁到x_n，达到未来状态集合x_n+1到x_N的条件独立，和α(z_n)和β(z_n)的定义，可以把γ(z_n)分成1到n状态和n+1到N状态，然后分别用α(z_n)和β(z_n)表示，得到

γ(z_n)在z_N上边沿概率之和为1，所以上面式子求和为1，得到
为了便于计算，在N步将β(z_n)看为1，得到简化版的式子
最后再计算z_n-1和z_n的在观测值X条件下联合后验分布ξ(z_n-1, z_n)，可以直接代入α(z_n)和β(z_n)的值，得到
总结一下，使用EM算法求解隐式马尔可夫链的最大似然概率和后验分布过程为：

1. 初始化θ^old ={π,A, φ} 参数。常见的初始化为A和π参数使用统一初始化，比如全部为1，或者使用随机化。φ参数初始化依赖于发射概率（emission probabilities），对于高斯分布的概率可以使用K均值方法得到高斯分布的均值与标准差。
2. 进行E步。通过前向递归计算α(z_n)。
3. 通过后向递归计算β(z_n)。
4. 通过α(z_n)和β(z_n)的值计算得到γ(z_n)和ξ(z_n-1, z_n)。
5. 计算p(X)的似然概率。
6. 进行M步。通过最大化Q(θ,θ^old)找到新的参数θ^new，重新设置π,A, φ的值。
7. 重复进行E步和M步循环直到收敛。

2.6 隐式马尔可夫链的python应用

隐式马尔可夫链在python中应用，对应函数是sklearn中的sklearn.hmm模型，该模型可以解决下面三个问题：

1. 给定模型参数和观测数据，估计隐藏状态的最优序列。
2. 给定模型参数和观测数据，计算数据的似然性。
3. 仅给定观察到的数据，估计模型参数。

HMM模型中又分为MultinomialHMM, GaussianHMM, and GMMHMM。其中最常用的就是高斯分布的隐式马尔可夫链GaussianHMM模型。具体为sklearn.hmm.GaussianHMM(n_components=1, covariance_type='diag', startprob=None, transmat=None, startprob_prior=None, transmat_prior=None, means_prior=None, means_weight=0, covars_prior=0.01, covars_weight=1)，其中n_components是隐藏状态的个数；covariance_type描述要使用的协方差参数类型的字符串，可以是‘spherical’, ‘tied’, ‘diag’, ‘full’中之一；其他参数可以参考下面的hmmlearn模型参数介绍。简单例子如下，因为于 EM 算法是基于梯度的优化方法，它通常会陷入局部最优，所以应该尝试使用各种初始化运行拟合并选择得分最高的模型。

import numpy as np
from sklearn import hmm

startprob = np.array([0.6, 0.3, 0.1]) #初始状态的分布。
transmat = np.array([[0.7, 0.2, 0.1], [0.3, 0.5, 0.2], [0.3, 0.3, 0.4]]) #状态之间的转移概率矩阵
means = np.array([[0.0, 0.0], [3.0, -3.0], [5.0, 10.0]])
covars = np.tile(np.identity(2), (3, 1, 1))
model = hmm.GaussianHMM(3, "full", startprob, transmat)
model.means_ = means #设置每个状态的平均参数
model.covars_ = covars #设置每个状态的协方差参数
X, Z = model.sample(100)
model2 = hmm.GaussianHMM(3, "full") #另一个HMM模型
#通过调用fit方法来训练HMM模型
model2.fit([X]) 
Z2 = model2.predict(X) #通过调用predict方法获得推断出的最佳隐藏状态
#模型的分数可以通过score方法来计算

不过sklearn.hmm模型是上一版本，已经不再使用，如今更常用的隐式马尔可夫链模型是hmmlearn模型。高斯分布的HMM模型具体为hmmlearn.hmm.GaussianHMM(n_components=1, covariance_type='diag', min_covar=0.001, startprob_prior=1.0, transmat_prior=1.0, means_prior=0, means_weight=0, covars_prior=0.01, covars_weight=1, algorithm='viterbi', random_state=None, n_iter=10, tol=0.01, verbose=False, params='stmc', init_params='stmc')，其中n_components还是状态数；covariance_type描述要使用的协方差参数类型的字符串；min_covar设定协方差矩阵对角线上的下限以防止过度拟合；startprob_prior设置狄利克雷先验分布参数；transmat_prior设置转移概率矩阵transmat_每一行的Dirichlet先验分布参数；mean_weight和means_prior分别是均值和均值先验分布的精度；covars_weight和covars_prior分别是协方差矩阵的权重和先验分布参数；algorithm代表解码器算法，“viterbi”或“map”；random_state代表随机种子；n_iter是要执行的最大迭代次数；tol是收敛阈值；params控制在训练过程中更新哪些参数，可以包含 startprob 的“s”、transmat 的“t”、均值的“m”和协变量的“c”的任意组合；init_params控制在训练之前初始化哪些参数，也是stmc的组合。具体实例为

import numpy as np
from hmmlearn import hmm
np.random.seed(42)
model = hmm.GaussianHMM(n_components=3, covariance_type="full")
model.startprob_ = np.array([0.6, 0.3, 0.1])
model.transmat_ = np.array([[0.7, 0.2, 0.1],[0.3, 0.5, 0.2],[0.3, 0.3, 0.4]])
model.means_ = np.array([[0.0, 0.0], [3.0, -3.0], [5.0, 10.0]])
model.covars_ = np.tile(np.identity(2), (3, 1, 1))
X, Z = model.sample(100)

3. 决策树和随机森林

3.1 决策树

决策树（Decision tree）起源于决策论，是指由一个决策图和可能的结果组成用来创建到达目标的模型。决策树是一种特殊的树结构，帮助在决策分析中确定一个最有可能实现目标的策略。在机器学习中，决策树是一个预测模型。它在对象属性与对象值之间建立一种映射关系，以树中每个节点表示某个对象，又将每个分叉路径代表一个可能的属性值，而最终到达的叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有一个输出，如果要处理多输出问题，应该同时使用多个决策树，即随机森林。

决策树的图形表示一般是一颗包含三种节点的树状图。其中决策节点通常用矩形框来表示；机会节点通常用圆圈来表示；终结点通常用三角形来表示。下面图示为一个决策树例子，用于决策根据所收集的数据（比如公司花费的钱、关系的长度等）给客户送什么礼物。其中最左边矩形框代表决策节点，即用来决策送给顾客的礼物。中间部分的圆圈节点代表可能的机会节点，将顾客的数据属性进行分类。最右边的三角形节点代表终结点，对应不同的礼物。

使用决策树一般有三个过程：特征选择，决策树生成和决策树剪枝。特征选择决定了使用哪些特征输入进模型进行学习和使用，实际训练中每个样本的属性可能有很多，其中属性的作用有轻有重，筛选出跟分类结果相关性较高的特征，具体方法可以参考机器学习从入门到死亡(上)一文中预处理小节中的特征选择。选择好特征后，进行决策树生成，就从根节点触发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点使用相同的方式生成新的子节点，直到信息增益很小或者没有特征可以选择为止。最后需要进行决策树剪枝，减小模型复杂度，降低过拟合程度，通过主动去掉部分分支来降低过拟合的风险。

经典的决策树算法有：ID3 算法，C4.5 算法和CART（Classification and Regression Tree）算法。ID3 算法是最早的决策树算法，C4.5 算法使用“信息增益比”指标作为特征的选择依据对ID3 算法进行改进，CART算法则使用了基尼系数作为特征的选择依据。CART算法可以处理分类问题，也可以处理回归问题，是目前最常用的决策树算法。

分类和回归树 (CART) 是一种非参数决策树学习技术，它生成分类树或回归树，具体取决于因变量是分类变量还是数值变量。决策树由基于建模数据集中变量的规则集合形成，该规则为：选择基于变量值的规则以获得最佳分割，以根据因变量区分观测值。一旦选择了规则并将节点分成两个，相同的过程将应用于每个“子”节点。此过程为递归过程，当 CART 检测到没有进一步的增益或者满足阈值时，分裂停止。树的每个分支都以终端节点结束，每个观察都落入一个且恰好是一个终端节点，每个终端节点由一组规则唯一定义。进行完所有分支后再进行剪枝。

3.2 决策树的优缺点

决策树的优点是：

1. 决策树易于理解和实现，可以通过简单解释后都有快速理解决策树所表达的意义。
2. 决策树可以处理数据型和常规型属性。
3. 决策树是白盒模型，根据所产生的决策树很容易推出相应的逻辑表达式。
4. 可以通过静态测试来对模型进行评测，可以测量该模型的可信度。
5. 可以在短时间内处理大数据。

决策树的缺点是：

1. 如果数据的各类别样本数量不一致，决策树当中信息增益的结果偏向于那些具有更多数值的特征，必须进行归一化和标准化。
2. 决策树只有单一输出，如果要处理多输出问题，需要使用随机森林。

3.3 决策树的python应用

决策树在sklearn中可以进行回归模型学习，对应函数为sklearn.tree.DecisionTreeRegressor()，具体为sklearn.tree.DecisionTreeRegressor(*, criterion='mse', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, ccp_alpha=0.0)。其中criterion代表，可以是“mse”，“friedman_mse”，“mae”，“poisson”中的一个，默认为“mse”即使用方差减少作为特征选择标准；max_depth是决策树的最大深度；min_samples_split是分裂一个内部节点所需的最小样本数；min_samples_leaf是叶节点所需的最小样本数；min_weight_fraction_leaf是叶节点所需的权重总和（所有输入样本的）的最小加权分数，默认样本具有相同的权重；max_features是寻找最佳分割时要考虑的特征数量，但是在找到至少一个节点样本的有效分区之前，即便搜索超过max_features个特征，分割的搜索也不会停止；random_state控制估计器的随机性；max_leaf_nodes是以最佳优先方式用max_leaf_nodes个节点种植一棵树，而最佳节点定义为杂质相对减少的节点；min_impurity_decrease代表如果此分裂导致杂质减少大于或等于该值，则该节点将被分裂；min_impurity_split是提前停止树木生长的阈值，现在已经弃用这个功能；ccp_alpha用于设置最小成本复杂度修剪的复杂度参数。下面是一个简单例子。

from sklearn.datasets import load_diabetes
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeRegressor
X, y = load_diabetes(return_X_y=True) #生成训练数据
regressor = DecisionTreeRegressor(random_state=0)
cross_val_score(regressor, X, y, cv=10)
#交叉验证的结果是array([-0.39..., -0.46...,  0.02...,  0.06..., -0.50..., 0.16...,  0.11..., -0.73..., -0.30..., -0.00...])

决策树在sklearn中可以进行分类模型学习，对应函数为sklearn.tree.DecisionTreeClassifier()，具体为sklearn.tree.DecisionTreeClassifier(*, criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, ccp_alpha=0.0)，其中参数意义和DecisionTreeRegressor()函数相同，参见上一段。具体应用如下。

from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(random_state=0)
iris = load_iris()
cross_val_score(clf, iris.data, iris.target, cv=10)
#交叉验证的结果是array([ 1.     ,  0.93...,  0.86...,  0.93...,  0.93..., 0.93...,  0.93...,  1.     ,  0.93...,  1.      ])

3.4 随机森林

随机森林是一个包含多个决策树的分类器它属于集成学习中的Bagging（Bootstrap AGgregation）方法中的一种。分类任务时，对于每个输入的样本数据，让随机森林中所有的决策树分别进行处理和分类，每个决策树都会得到各自的结果，最后统计那种分类结果最多，作为这个随机森林最终的分类结果。训练随机森林时，要先从训练集中进行有放回的随机抽样，使用选择的样本训练一个决策树，作为决策树根节点处的样本。对于每个样本的不同属性，同样进行特征选择，然后采用某种策略（比如CART树会使用基尼系数）来选择属性作为该节点的分裂属性。重复这一步分裂形成决策树的所有节点，进行递归过程直到没有进一步的增益或者满足阈值时，分裂停止。决策树可以进行完整成长，无需进行剪枝处理。接下来再重复上述过程，生成大量的决策树，形成随机森林。随机森林可以应用分类问题，回归问题，无监督学习聚类以及异常点检测。

3.5 随机森林的优缺点

随机森林的优点：

1. 随机森林处理高维度多特征的数据，并且无需降维或特征选择。
2. 随机森林可以判断每个特征的重要程度，以及不同特征之间的相互影响。
3. 随机森林可以有效避免过拟合。
4. 随机森林训练速度，实现简单，可以处理大数据。
5. 当数据集不平衡或者有特征遗失，随机森林依旧可以保持高准确度。
6. 随机森林可以处理未标记的数据，进行无监督学习聚类。

随机森林的缺点是：

1. 随机森林会在某些噪音较大的分类或回归问题上出现过拟合现象。
2. 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的。

3.6 随机森林的python应用

随机森林在机器学习中同样可以进行回归任务和分类任务。在python的sklearn库中，使用随机森林处理回归问题的函数是sklearn.ensemble.RandomForestRegressor()，具体为sklearn.ensemble.RandomForestRegressor(n_estimators=100, *, criterion='mse', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features='auto', max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, bootstrap=True, oob_score=False, n_jobs=None, random_state=None, verbose=0, warm_start=False, ccp_alpha=0.0, max_samples=None)。其中n_estimators代表随机森林中决策树的数量；criterion是测量分割质量的函数，与上一小节的决策树中对应参数内容一致；max_depth是决策树的最大深度；min_samples_split是分裂一个内部节点所需的最小样本数；min_samples_leaf是叶节点所需的最小样本数；min_weight_fraction_leaf是叶节点所需的权重总和（所有输入样本的）的最小加权分数，默认样本具有相同的权重；max_features是寻找最佳分割时要考虑的特征数量；max_leaf_nodes是以最佳优先方式用max_leaf_nodes个节点种植一棵树，而最佳节点定义为杂质相对减少的节点；min_impurity_decrease代表如果此分裂导致杂质减少大于或等于该值，则该节点将被分裂；min_impurity_split是提前停止树木生长的阈值；bootstrap决定构建决策树时是否使用引导样本；oob_score用于决定是否使用袋外样本来估计泛化分数；n_jobs是并行运行的作业数；random_state控制估计器的随机性；verbose用来控制拟合和预测时的详细程度；warm_start如果为 True 时，重用之前调用 fit 的解决方案并向集成添加更多估计器；ccp_alpha用于设置最小成本复杂度修剪的复杂度参数；max_samples代表如果 bootstrap 为 True，则从训练集X中抽取的样本数用于训练每个基估计量。下面是一个简单应用。

from sklearn.ensemble import RandomForestRegressor
from sklearn.datasets import make_regression
X, y = make_regression(n_features=4, n_informative=2,random_state=0, shuffle=False) #构建训练集数据
regr = RandomForestRegressor(max_depth=2, random_state=0)
regr.fit(X, y) #向模型输入训练数据
print(regr.predict([[0, 0, 0, 0]]))
#回归预测的结果是[-8.32987858]

在python的sklearn库中，使用随机森林处理分类问题的函数是sklearn.ensemble.RandomForestClassifier()，具体为sklearn.ensemble.RandomForestClassifier(n_estimators=100, *, criterion='gini', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features='auto', max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, bootstrap=True, oob_score=False, n_jobs=None, random_state=None, verbose=0, warm_start=False, class_weight=None, ccp_alpha=0.0, max_samples=None)，其中参数设置和上面的RandomForestRegressor()函数一致。下面为一个简单实例。

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import make_classification
X, y = make_classification(n_samples=1000, n_features=4,n_informative=2, n_redundant=0,random_state=0, shuffle=False) #生成训练集数据
clf = RandomForestClassifier(max_depth=2, random_state=0)
clf.fit(X, y)
print(clf.predict([[0, 0, 0, 0]]))
#分类结果是[1]