本文目录

经典分类算法

感知机

感知机是根据输入实例的特征向量$x$对其进行二类分类的线性分类模型：

$f(x) = sign(w \cdot x + b)$

感知机模型对应于输入空间$($特征空间$)$中的分离超平面$w \cdot x + b = 0$

感知机学习的策略是极小化损失函数：

$\min _{w, b} L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)$

损失函数对应于误分类点到分离超平面的总距离。

感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有原始形式和对偶形式。算法简单且易于实现。原始形式中，首先任意选取一个超平面，然后用梯度下降法不断极小化目标函数。在这个过程中一次随机选取一个误分类点使其梯度下降。
当训练数据集线性可分时，感知机学习算法是收敛的。当训练数据集线性可分时，感知机学习算法存在无穷多个解，其解由于不同的初值或不同的迭代顺序而可能有所不同。

K-近邻算法

$k$近邻法是基本且简单的分类与回归方法。$k$近邻法的基本做法是：对给定的训练实例点和输入实例点，首先确定输入实例点的$k$个最近邻训练实例点，然后利用这$k$个训练实例点的类的多数来预测输入实例点的类。
$k$近邻模型对应于基于训练数据集对特征空间的一个划分。$k$近邻法中，当训练集、距离度量、$k$值及分类决策规则确定后，其结果唯一确定。
$k$近邻法三要素：距离度量、$k$值的选择和分类决策规则。常用的距离度量是欧氏距离及更一般的$pL$距离。$k$值小时，$k$近邻模型更复杂；$k$值大时，$k$近邻模型更简单。$k$值的选择反映了对近似误差与估计误差之间的权衡，通常由交叉验证选择最优的$k$。常用的分类决策规则是多数表决，对应于经验风险最小化。
$k$近邻法的实现需要考虑如何快速搜索$k$个最近邻点。$kd$树是一种便于对$k$维空间中的数据进行快速检索的数据结构。$kd$树是二叉树，表示对$k$维空间的一个划分，其每个结点对应于$k$维空间划分中的一个超矩形区域。利用$kd$树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

朴素贝叶斯

朴素贝叶斯法（naive Bayes）是基于贝叶斯定理与特征条件独立假设的分类方法，它是一种典型的生成学习方法。对于给定的训练数据集，首先基于特征条件独立假设学习输入/输出的联合概率分布；然后基于此模型，对给定的输入$x$，利用贝叶斯定理求出后验概率最大的输出$y$。朴素贝叶斯法实现简单，学习与预测的效率都很高，是一种常用的方法。

数学推导

朴素贝叶斯通过训练数据集学习联合概率分布$P(X, Y)$，然后求得后验概率分布$P(Y | X)$，具体来说，利用训练数据学习$P(X | Y)$和$P(Y)$的估计，得到联合概率分布：

$Ｐ(X, Y) = P(Y) P(X | Y)$

概率估计方法可以是极大似然估计或者贝叶斯估计。

由于条件概率分布

$P\left(X=x | Y=c_{k}\right)=P\left(X^{(1)}=x^{(1)}, \cdots, X^{(n)}=x^{(n)} | Y=c_{k}\right), \quad k=1,2, \cdots, K$

含有指数级数量的参数，其估计实际是不可行的。

因此朴素贝叶斯对条件概率分布作了条件独立性的假设，朴素贝叶斯法也是因此而得名。具体地，条件独立性假设是：

$\begin{aligned} P\left(X=x | Y=c_{k}\right) &=P\left(X^{(1)}=x^{(1)}, \cdots, X^{(n)}=x^{(n)} | Y=c_{k}\right) \\ &=\prod_{i=1}^{n} P\left(X^{(j)}=x^{(j)} | Y=c_{k}\right) \end{aligned}$

由于这一假设，模型包含的条件概率的数量大为减少，朴素贝叶斯法的学习与预测大为简化。因而朴素贝叶斯法高效，且易于实现。其缺点是分类的性能不一定很高。

有了先验概率分布$P(Y)$以及条件分布$P(X | Y)$的估计之后，对于给定的$x$，利用贝叶斯定理求出后验概率最大的输出$y$，以此进行分类预测：

$P(Y | X)=\frac{P(X, Y)}{P(X)}=\frac{P(Y) P(X | Y)}{\sum_{Y} P(Y) P(X | Y)}$

（注意上式中的分母，对不同的$ Y = c_k$，其大小是相同的，所以要使后验概率最大，只要最大化它的分子就行了）

将输入$x$分到后验概率最大的类$y$：

$y=\arg \max _{c_{k}} P\left(Y=c_{k}\right) \prod_{j=1}^{n} P\left(X_{j}=x^{(j)} | Y=c_{k}\right)$

后验概率最大等价于0-1损失函数时的期望风险最小化。

参数估计

使用极大似然法估计先验概率$P(Y = c_k)$：

$P\left(Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)}{N}, k=1,2, \cdots, K$

设第$j$个特征$x^{(j)}$可能取值的集合为${a_{j1}, a_{j2}, …., a_{jS_j}}$，条件概率$P(x^{(j)} = a_{j1} | Y = c_k)$的极大似然估计是：

$\begin{array}{c}{P\left(X^{(j)}=a_{j l} | Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(x_{i}^{(j)}=a_{j l}, y_{i}=c_{k}\right)}{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)}} \\ {j=1,2, \cdots, n ; \quad l=1,2, \cdots, S_{i} ; k=1,2, \cdots, K}\end{array}$

其中$I$为指示函数。

但是用极大似然估计可能会出现所要估计的概率值为0的情况。这时会影响到后验概率的计算结果，使分类产生偏差。解决这一问题的方法是采用贝叶斯估计。具体地，条件概率的贝叶斯估计是：

$P_{\lambda}\left(X^{(j)}=a_{j l} | Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(x_{i}^{(i)}=a_{j} y_{i}=c_{k}\right)+\lambda}{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)+S_{j} \lambda}$

式中，$\lambda \geq 0 $ 。等价于在随机变量各个取值的频数上赋予一个正数$\lambda > 0$。当$\lambda = 0$时就是极大似然估计。常取$\lambda = 1$，这时称为拉普拉斯平滑。同样，先验概率的贝叶斯估计是：

$P_{\lambda}\left(Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)+\lambda}{N+K \lambda}$

支持向量机

原理

支持向量机是建立在统计学习理论基础上的一种数据挖掘方法，能非常成功地处理回归问题（时间序列分析）和模式识别（分类问题、判别分析）等诸多问题，并可推广于预测和综合评价等领域和学科。

SVM的机理是寻找一个满足分类要求的最优分类超平面，使得该超平面在保证分类精度的同时，能够使超平面两侧的空白区域最大化。理论上，支持向量机能够实现对线性可分数据的最优分类。

以二分类数据分类为例，给定训练样本集$(x_i,y_i), i=1,2,…,l, x\in R^{n}, y \in {\pm1}$，超平面记作$(w \cdot x) + b = 0$，求一个几何间隔最大的分离超平面可以表示为下面的约束最优化问题：

$\begin{array}{ll}{\max _{w, b}} & {\gamma} \\ {\text { s.t. }} & {y_{i}\left(\frac{w}{\|w\|} \cdot x_{i}+\frac{b}{\|w\|}\right) \geqslant \gamma, \quad i=1,2, \cdots, N}\end{array}$

其中约束条件表示的是超平面(w,b)关于每个训练样本点的几何间隔至少是 $\gamma$　。

根据几何间隔和函数间隔的关系可进一步化简变成：

$\begin{array}{ll}{\min _{w, b}} & {\frac{1}{2}\|w\|^{2}} \\ {\text { s.t. }} & {y_{i}\left(w \cdot x_{i}+b\right)-1 \geqslant 0, \quad i=1,2, \cdots, N}\end{array}$

为了解决这个带有约束的最优化问题，引入Lagrange函数：

$L(w,b,a) = \frac{1}{2}\|w\|^2 - a(y((w\cdot x) + b)-1)$

式中， $a_i > 0$为Lagrange乘数。约束最优化问题的解由Lagrange函数的鞍点决定，并且最优化问题的解在鞍点处满足对$w$和$b$的偏导为0，将该QP问题转化为相应的对偶问题即：

$\begin{aligned} maxQ(a) = &\sum_{j=1}^{l}a_j - \frac{1}{2}\sum_{i=1}^{l}\sum_{j=1}^{l}a_ia_jy_iy_j(x_i \dot x_j) \\ &s.t. \sum_{j=1}^{l}a_jy_j = 0 \qquad j = 1,2,...,l, a_j \geq 0, j=1,2,...l \end{aligned}$

解得最优解$a^* = (a_1^,a_2^,…,a_l^)^T$。下面计算最优权值向量 $w^$和最优偏置$b^*$：

$w^* = \sum_{j=1}^{l}a_j^*y_jx_j \\ b^* = y_i - \sum_{j=1}^{l}y_ja_j^*(x_j \cdot x_i)$

式中，下标$j \in {j|a_j^* > 0}$。因此得到最优分类超平面$(w^* \cdot x)+b^* = 0$，而最优分类函数为：

$f(x) = sgn\{(w^* \cdot x) + b^*\} = sgn\{(\sum_{j=1}^{l}a_j^*y_j(x_j \cdot x_l)) + b^*\}, x \in R_n$

对于线性不可分的情况，SVM的做法是，利用核方法将输入向量映射到一个高位的特征向量空间， 并在该特征空间中构造最优分类面。具体步骤是，将$x$做从输入空间$R^n$到特征空间$H$的变换$\Phi$，得到：

$x \rightarrow \Phi(x) = (\Phi_1(x),\Phi_2(x),...,\Phi_l(x))^T$

然后以特征向量$\Phi(x)$代替输入向量$x$，则可以得到最优分类函数为：

$\begin{aligned} f(x) &= sgn(w \dot \Phi(x) + b) \\ &= sgn(\sum_{i=1}^{l}a_iy_i\Phi(x_i)\Phi(x)+b) \end{aligned}$

在上面的对偶问题中，通过应用核技巧，无论是目标函数还是决策函数都只涉及到了训练样本之间的内积运算，从而在高维空间避免了复杂的高位运算而只需要进行内积运算。

核技巧：在学习和预测中只定义核函数$K(x, z)$ ，而不显示地定义映射函数$\phi$，这是因为通常直接计算$K(x, z)$比较容易，而通过$\phi(x)$和$\phi(z)$计算$K(x, z)$并不容易。常用的核函数有：多项式核函数、高斯核函数等等。

要点

支持向量机最简单的情况是线性可分支持向量机，或硬间隔支持向量机。构建它的条件是训练数据线性可分。其学习策略是最大间隔法。可以表示为凸二次规划问题，其原始最优化问题为

$\begin{array}{ll}{\min _{w, b}} & {\frac{1}{2}\|w\|^{2}} \\ {\text { s.t. }} & {y_{i}\left(w \cdot x_{i}+b\right)-1 \geqslant 0, \quad i=1,2, \cdots, N}\end{array}$

求得最优化问题的解为$w^, b^$，得到线性可分支持向量机，分离超平面是：

$w^{*} \cdot x+b^{*}=0$

分类决策函数是：

$f(x)=\operatorname{sign}\left(w^{*} \cdot x+b^{*}\right)$

线性可分支持向量机的最优解存在且唯一。位于间隔边界上的实例点为支持向量。最优分离超平面由支持向量完全决定。

二次规划问题的对偶问题是：

$\begin{array}{l}{\min \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i}} \\ {\text { s.t. } \sum_{i=1}^{N} \alpha_{i} y_{i}=0} \\ {\alpha_{i} \geqslant 0, \quad i=1,2, \cdots, N}\end{array}$

通常，通过求解对偶问题学习线性可分支持向量机，即首先求解对偶问题的最优值$a^$，然后求最优值$w^$和$b^*$，得出分离超平面和分类决策函数。

现实中训练数据是线性可分的情形较少，训练数据往往是近似线性可分的，这时使用线性支持向量机，或软间隔支持向量机。线性支持向量机是最基本的支持向量机。

对于噪声或例外，通过引入松弛变量${\varepsilon_i}$ ，使其“可分”，得到线性支持向量机学习的凸二次规划问题。
对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个高维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。由于在线性支持向量机学习的对偶问题里，目标函数和分类决策函数都只涉及实例与实例之间的内积，所以不需要显式地指定非线性变换，而是用核函数来替换当中的内积。核函数表示，通过一个非线性转换后的两个实例间的内积。

具体地，$K(x, z)$是一个核函数，或正定核，意味着存在一个从输入空间$\mathcal{X}$的映射$\Phi(x): \mathcal{X} \rightarrow \mathcal{H}$

对任意$x, z \in \mathcal{X}$，有

$K(x, z) = \Phi(x) \cdot \Phi(z)$

对称函数$K(x, z)$为正定核的充要条件是：对任意$x_i \in \mathcal{X}, i = 1,2, …, m$，任意正整数$m$，对称函数$K(x, z)$对应的Gram矩阵是半正定的。

所以，在线性支持向量机学习的对偶问题中，用核函数$K(x$，$z)$替代内积，求解得到的就是非线性支持向量机。

$f(x)=\operatorname{sign}\left(\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} K\left(x, x_{i}\right)+b^{*}\right)$

$SMO$算法是支持向量机学习的一种快速算法，其特点是不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足$KKT$条件为止。这样通过启发式的方法得到原二次规划问题的最优解。因为子问题有解析解，所以每次计算子问题都很快，虽然计算子问题次数很多，但在总体上还是高效的。

拓展

SVM算法最初是为二值分类问题设计的，当处理多类问题时，就需要构造合适的多类分类器。

常见的通过SVM构造多类分类器有以下两种方法：

一对多法（one-versus-rest,简称OVR SVMs），训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。这种方法有种缺陷,因为训练集是1:M,这种情况下存在biased，因而不是很实用。
一对一法（one-versus-one,简称OVO SVMs或者pairwise），在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM，当对一个未知样本进行分类时，使用k(k-1)/2个SVM分别对它进行分类，最后得票最多的类别即为该未知样本的类别。

逻辑回归

二项逻辑回归模型

二项逻辑斯谛回归模型是如下的条件概率分布:

$\begin{array}{l}{P(Y=1 | x)=\frac{\exp (w \cdot x+b)}{1+\exp (w \cdot x+b)}} \\ {P(Y=0 | x)=\frac{1}{1+\exp (w \cdot x+b)}}\end{array}$

这里，$x \in R^n$是输入，$Y \in {0,1}$是输出，$ w \in R^n$和$b\in R$是参数，$w$称为权值向量，$b$称为偏置，$w \cdot x$为$w$和$x$的内积。

对于给定的输入实例$x$,按照上式可以求得$P(Y=1|x)$和$P(Y=0|x)$。逻辑斯谛回归比较两个条件概率值的大小,将实例$x$分到概率值较大的那一类。

有时为了方便,将权值向量和输入向量加以扩充,仍记作$w,x$，即$w=(w^{(1)},w^{(2)},…,w^{(n)},b)^T ,x=(x^{(1)},x^{(2)},…,x^{(n)} ,1)^T$。这时,逻辑斯谛回归模型如下:

$\begin{array}{l}{P(Y=1 | x)=\frac{\exp (w \cdot x)}{1+\exp (w \cdot x)}} \\ {P(Y=0 | x)=\frac{1}{1+\exp (w \cdot x)}}\end{array}$

逻辑回归函数与线性回归函数$w \cdot x $的关系：考虑对输入$x$进行分类的线性函数$w \cdot x$，其值域为实数域。注意，这里$x \in R^{N+1},w \in R^{N+1}$。通过逻辑斯谛回归模型定义式可以将线性函数$w \cdot x$转换为概率:

${P(Y=1 | x)=\frac{\exp (w \cdot x)}{1+\exp (w \cdot x)}}$

这时，线性函数的值越接近正无穷,概率值就越接近1；线性函数的值越接近负无穷，概率值就越接近0。这样的模型就是逻辑斯谛回归模型。

模型参数估计

逻辑斯谛回归模型学习时,对于给定的训练数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$,其中，$x_i \in R_n,y_i \in {0,1}$ ，可以应用极大似然估计法估计模型参数,从而得到逻辑斯谛回归模型。

设: $P(Y=1 | x)=\pi(x), \quad P(Y=0 | x)=1-\pi(x)$　

那么似然函数为：

$\prod_{i=1}^{N}\left[\pi\left(x_{i}\right)\right]^{y_{i}}\left[1-\pi\left(x_{i}\right)\right]^{1-y_{i}}$

对数似然函数为：

$\begin{aligned} L(w) &=\sum_{i=1}^{N}\left[y_{i} \log \pi\left(x_{i}\right)+\left(1-y_{i}\right) \log \left(1-\pi\left(x_{i}\right)\right)\right] \\ &=\sum_{i=1}^{N}\left[y_{i} \log \frac{\pi\left(x_{i}\right)}{1-\pi\left(x_{i}\right)}+\log \left(1-\pi\left(x_{i}\right)\right)\right] \\ &=\sum_{i=1}^{N}\left[y_{i}\left(w \cdot x_{i}\right)-\log \left(1+\exp \left(w \cdot x_{i}\right)\right]\right.\end{aligned}$

对对数似然函数$L(w)$求极大值，就得到$w$的估计值。

这样,问题就变成了以对数似然函数为目标函数的最优化问题。逻辑斯谛回归学习中通常采用的方法是梯度下降法及拟牛顿法。

假设$w$的极大似然估计值是$\hat{w}$，那么学到的逻辑回归模型为：

$\begin{array}{l}{P(Y=1 | x)=\frac{\exp (\hat{w} \cdot x)}{1+\exp (\hat{w} \cdot x)}} \\ {P(Y=0 | x)=\frac{1}{1+\exp (\hat{w} \cdot x)}}\end{array}$

多项逻辑回归

上面介绍的逻辑斯谛回归模型是二项分类模型,用于二类分类。可以将其推广为多项逻辑斯谛回归模型(multi-nominal logistic regression model),用于多类分类。假设离散型随机变量$Y$的取值集合是${1,2,…,K}$,那么多项逻辑斯谛回归模型是：

$\begin{array}{l}{P(Y=k | x)=\frac{\exp \left(w_{k} \cdot x\right)}{1+\sum_{k=1}^{K-1} \exp \left(w_{k} \cdot x\right)}, \quad k=1,2, \cdots, K-1} \\ {P(Y=K | x)=\frac{1}{1+\sum_{k=1}^{K-1} \exp \left(w_{k} \cdot x\right)}}\end{array}$

这里，$x \in R^{N + 1}，w_k \in R^{N+1}$ 。

二项逻辑斯谛回归的参数估计法也可以推广到多项逻辑斯谛回归。

决策树

决策树(decision tree)是一种基本的分类与回归方法。这里主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括3个步骤：

特征选择
决策树的生成
决策树的修剪

分类决策树的定义

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型：内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。

用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。

决策树的学习

决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个，也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。

决策树学习用损失函数表示这一目标。如下所述，决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。

以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。

如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

可以看出，决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。

决策树学习常用的算法有ID3、C4.5与CART，下面主要讲一下C4.5算法，在介绍这个算法之前，先介绍一下决策树的特征选择。

特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。

信息增益

为了便于说明，先给出熵与条件熵的定义。

在信息论与概率统计中，熵(entropy)是表示随机变量不确定性的度量。设$X$是一个取有限个值的离散随机变量，其概率分布为：

$P\left(X=x_{i}\right)=p_{i}, \quad i=1,2, \cdots, n$

则随机变量$X$的熵定义为：

$H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i}$

在上式中，若$p_i = 0 $，则定义$0log0 = 0$　。　

由定义可知，熵只依赖于$X$的分布，而与$X$的取值无关，所以也可将$X$的熵记作$H(p)$，即

$H(p)=-\sum_{i=1}^{n} p_{i} \log p_{i}$

熵越大，随机变量的不确定性就越大。

条件熵$H(Y|X)$表示在已知随机变量X的条件下随机变量$Y$的不确定性。随机变量$X$给定的条件下随机变量$Y$的条件熵(conditional entropy)$H(Y|X)$，定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望：

$H(Y | X)=\sum_{i=1}^{n} P(X=x_i) H\left(Y | X=x_{i}\right), i = 1,2,...,n$

当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。此时，如果有0概率，令0log0=0。

信息增益(information gain)表示得知特征$X$的信息而使得类$Y$的信息的不确定性减少的程度。

信息增益具体的定义如下：

特征$A$对训练数据集$D$的信息增益$g(D$，$A)$，定义为集合$D$的经验熵$H(D)$与特征$A$给定条件下$D$的经验条件熵$H(D|A)$之差，即

$g(D, A)=H(D)-H(D | A)$

一般地，熵$H(Y)$与条件熵$H(Y|X)$之差称为互信息$(mutualinformation)$。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

决策树学习应用信息增益准则选择特征。给定训练数据集$D$和特征$A$，经验熵$H(D)$表示对数据集$D$进行分类的不确定性。而经验条件熵$H(D|A)$表示在特征$A$给定的条件下对数据集$D$进行分类的不确定性。那么它们的差，即信息增益，就表示由于特征$A$而使得对数据集$D$的分类的不确定性减少的程度。显然，对于数据集$D$而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。

根据信息增益准则的特征选择方法是：对训练数据集$($或子集$)D$，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

设训练数据集为$D$，$|D|$表示其样本容量，即样本个数。设有$K$个类$C_k$，$k$=1，2，…，$K$，$|C_k|$为属于类$C_k$的样本个数。。设特征$A$有$n$个不同的取值{$a_1， $$ a_2$，…，$a_n$}，根据特征$A$的取值将$D$划分为$n$个子集$D_1, D_2, …, D_n$，$|D_i|$表示$D_i$的样本个数，记子集$D_i$中属于类$C_k$的样本的集合为$D_{ik}$，即$D_{ik}$=$D_i$⋂$C_k$，$|D_{ik}|$为$D_{ik}$的样本个数。于是信息增益的算法如下：

输入：训练数据集$D$和特征$A$；

输出：特征$A$对训练数据集$D$的信息增益$g(D$，$A)$。

计算数据集$D$的经验熵$H(D)$

$H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$

计算特征$A$对数据集$D$的经验条件熵$H(D|A)$

$H(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left | D_{i}\right | =-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{| D |} \sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}$

计算信息增益

$g(D, A)=H(D)-H(D | A)$

信息增益比

信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类问题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。使用信息增益比(informationgain　ratio)可以对这一问题进行校正。这是特征选择的另一准则。

特征$A$对训练数据集$D$的信息增益比$g_R(D，A)$定义为其信息增益$g(D$，$A)$与训练数据集$D$的经验熵$H(D)$之比：

$g_{R}(D, A)=\frac{g(D, A)}{H(D)}$

C4.5的生成算法

输入：训练数据集$D$，特征集$A$，阈值$\gamma$　，　输出：决策树$T$。

如果$D$中所有实例属于同一类$C_k$，则置$T$为单结点树，并将$C_k$作为该结点的类，返回$T$；
如果$A$=Ø，则置$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类，返回$T$；
否则，计算$A$中各特征对$D$的信息增益比，选择信息增益比最大的特征$A_g$；
如果$A$ 的信息增益比小于阈值$\gamma$ ，则置$T$为单结点树，并将$D_g$中实例数最大的类$C$ 作为该结点的类，返回$T$；
否则，对$A_g$的每一可能值$a_i$，依$A_g$=$a_i$将$D$分割为子集若干非空$D_i$，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$；
对结点$i$，以$D_i$为训练集，以$A-{A_g}$为特征集，递归地调用1-5步，得到子树$T_i$，返回$T_i$。

决策树的剪枝

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。

在决策树学习中将已生成的树进行简化的过程称为剪枝$(pruning)$。具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。

决策树的剪枝往往是将模型的复杂度引入损失函数，即叶结点越多，模型越复杂，损失越大，然后通过优化损失函数减小模型复杂度以实现剪枝的效果。

Ｋ均值算法(K-means)

K-Means算法是无监督的聚类算法，它实现起来比较简单，聚类效果也不错，因此应用很广泛。

原理

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

如果用数据表达式表示，假设簇划分为$(C_1,C_2,…C_k)$，则我们的目标是最小化平方误差$E$：

$E = \sum\limits_{i=1}^k\sum\limits_{x \in C_i} ||x-\mu_i||_2^2$

其中$\mu_i$是簇$C_i$的均值向量，有时也称为质心，表达式为：

$\mu_i = \frac{1}{|C_i|}\sum\limits_{x \in C_i}x$

如果我们想直接求上式的最小值并不容易，这是一个NP难的问题，因此只能采用启发式的迭代方法。

K-Means采用的启发式方式很简单，用下面一组图就可以形象的描述：

上图a表达了初始的数据集，假设k=2。在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图4所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。

当然在实际K-Mean算法中，我们一般会多次运行图c和图d，才能达到最终的比较优的类别。

算法流程

对于K-Means算法，首先要注意的是k值的选择，一般来说，我们会根据对数据的先验经验选择一个合适的k值，如果没有什么先验知识，则可以通过交叉验证选择一个合适的k值。

在确定了k的个数后，我们需要选择k个初始化的质心，就像上图b中的随机质心。由于我们是启发式方法，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心，最好这些质心不能太近。

传统的K-means算法流程如下：

输入是样本集$D={x_1,x_2,…x_m}$，聚类的簇数是$k$，最大迭代次数为$N$

输出是簇划分$C={C_1,C_2,…C_k}$

从数据集$D$中随机选择$k$个样本作为初始的$k$个质心向量：${\mu_1,\mu_2,…,\mu_k}$
对于$n = 1,2, …, N$
1. 将簇划分C初始化为$C_t = \varnothing ; t =1,2…k$
2. 对于$i = 1,2,…m$，计算样本$x_i$和各个质心向量$\mu_j(j=1,2,…k)$的距离：$d_{ij} = ||x_i - \mu_j||_2^2$
  
  将$x_i$标记最小的为$d_{ij}$所对应的类别$\lambda_i$。此时更新$C_{\lambda_i} = C_{\lambda_i} \cup {x_i}$
3. 对于$j=1，2，…，k$，对$C_j$中所有的样本点重新计算新的质心$\mu_j = \frac{1}{|C_j|}\sum\limits_{x \in C_j}x$
4. 如果所有的$k$个质心向量都没有发生变化，则转到步骤3
输出簇划分 $C=\{C_1,C_2,...C_k\}$

优缺点

K-Means的主要优点有：

原理比较简单，实现也是很容易，收敛速度快。　　　
聚类效果较优。　　　　
算法的可解释度比较强。
主要需要调参的参数仅仅是簇数$k$。

主要缺点有：

K值的选取不好把握
对于不是凸的数据集比较难收敛
如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。
采用迭代方法，得到的结果只是局部最优。
对噪音和异常点比较的敏感。
计算量很大，要计算所有的样本点到所有的质心的距离。如果样本量非常大，比如达到10万以上，特征有100以上，此时用传统的K-Means算法非常的耗时。此时可以使用Mini Batch K-Means，也就是用样本集中的一部分的样本来做传统的K-Means，这样可以避免样本量太大时的计算难题，算法收敛速度大大加快。当然此时的代价就是我们的聚类的精确度也会有一些降低。一般来说这个降低的幅度在可以接受的范围之内。

常见问题

SVM如何拓展到多分类？