14  分类：基本概念与应用

从一个随机变量到另一个离散随机变量的问题称为是分类，或者是有指导性的学习，或称为是模式识别。 比如在一个独立同分布的数据 \((X_1,Y_1),\cdots,(X_n,Y_n)\) 下其中 \[ X_i=(X_{i1},\cdots,X_{id})\in \mathcal{X}\subset \mathbb{R}^d \] 为一个d维向量且 \(Y_i\) 在某个有限集 \(\mathcal{Y}\) 中取值，其中可能就存在一个分类规则，可以用函数\(h\)来表示 \(\mathcal{X}\to\mathcal{Y}\) ，当观测到一个新的\(X\)时候，就会有对应的一个Y，预测为 \(h(X)\) 。

分类是一种重要的数据分析方法，用于提取重要的数据模型。这种模型称为是分类器，预测分类的类标号。

比如在银行处理贷款时候，需要判断这笔贷款的安全性，医学研究人员研究乳腺癌数据，以便分析使用哪一种的治疗方案，销售部门需要对顾客特征数据分析来判断哪一类群体更有可能进行购买。这些任务所进行都是分类，实际上，是进行数值预测，其中所预测的是一个有序数值或连续数值，而不是类标号，这称为是预测器。回归分析是最为常见的数值预测的统计学方法。分类和数值预测是预测问题的两种主要类型。

14.1 分类方法

• 第一阶段（学习阶段）：建立描述预先定义的数据类或概念集的分类器；
• 第二阶段：使用模型进行分类，再对评估的准确度进行评价。

14.2 决策树

决策树是一种基本的分类与回归的算法。分类中，对于基于特征对实例进行分类的过程。可以认为是if-then规则的集合。也可以是定义在特征空间与类空间上的概率分布。

14.2.1 信息熵

• 信息量： 越不可能的事件发生的，信息量越大 \(I(x_0)=-\log(p(x_0))\)
  
• 信息熵： 越大的期望表示的是系统越混乱。
• 相对熵： 衡量两个概率分布的差异程度

\[ KLD=D_{KL}(p||q)=\sum p(x_i)-\log (\frac{p(x_i)}{q(x_i)}) \]

• 交叉熵：衡量差异的量

假设px是真实的分布，qx是算法计算的分布。逻辑回归就是用交叉熵度量损失函数。

用交叉熵来衡量： \[L(w)=-\sum_{i=1}^N(y_i\log(p_1(x_i))+(1-y_i)\log (p_0(x_i)))\]

该损失函数无法得到一个闭式解，因此使用迭代方法来求解最优函数。 迭代方法：通过梯度下降的方法来实现，GD

\[ w^{i+1}=w^i-\alpha\Delta L(w) \]

证明可以不断地进行迭代更优； 下降是最快的； 泰勒展开：

\[ f(x+\Delta x)=f(x)+(\triangledown f(x))^T\Delta x+o(\Delta x)\\ f(x+\Delta x)-f(x)=(\triangledown f(x))^T\Delta x+o(\Delta x) \] 若\(\Delta x\)与\(\triangledown f(x)\)同向，则 同时通过内积的定义可以得到：

\[ (\triangledown f(x))^T\Delta x=||\triangledown f(x)||\cdot ||\Delta x||\cdot \cos \theta \]

显然当\(\cos \theta =-1\)时候，绝对值最大。

14.2.2 决策树模型与学习

分类决策树模型是一种描述分类的树形结构。决策树由node和directed edge组成。结点有两种：内部结点和叶节点。内部节点表示一个特征或属性，叶节点表示一个类。

在每一条从根节点到叶节点上构建一个规则，内部节点对应的是规则的条件，叶节点是规则的结论，决策树的路径或其对应的if-then规则集合具有：互斥且完备性。每一个实例是被一条规则所覆盖。

14.2.3 决策树与条件概率分布

决策树是给定特征下的类的条件概率分布，定义在特征空间中的一个划分(partition)上，将特征空间分为几个不相交的单元(cell)或区域(region).

14.2.4 决策树学习

在给定的训练数据集\(D\)

\[ D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\} \]

其中\(x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})\)为输入实例，\(n\)为特征个数。 \(y\in \{1,2,3,\cdots,K\}\)为类标记。

决策树学习的本质是从训练数据集中学习关于一条分类规则。这些分类规则能够帮助进行预测和标记等作用。

决策树算法，递归的选择最优特征，并根据该特征对训练集进行分割，使得对各个子训练集有一个最好的分类过程。 最终每个实例都能被分到叶节点上，都有了明确的类，生成了一个决策树。

14.2.4.1 特征选择

特征的选择在于对训练数据具有分类能力的特征，可以提高决策树的学习效率。

14.2.4.2 信息增益

熵度量的是随机变量的不确定性的度量，设X是一个有限值的离散随机变量，其概率分布为 \[P(X=x_i)=p_i,i=1,2,\cdots,n\] 则随机变量X的熵定义为 \[ H(X)=-\sum_{i=1}^np_i\log_2p_i \] 熵只依赖于X的分布与X的取值无关。 熵越大，随机变量的不确定性越大。

\[ 0\leq H(X)\leq \log n \]

信息增益是知道特征X的信息，能够使得Y的信息的不确定性降低的程度。特征A对训练数据集D的信息增益\(g(D,A)\)，定义集合D的经验熵\(H(D)\)与特征A给定条件下D的经验条件熵\(H(D|A)\)之差，即

\[ g(D,A)=H(D)-(D|A) \]

最终降低的不确定性\(g(D,A)\)称为互信息(mutual infomation)，决策树学习中的信息增益等价于训练集中类与特征的互信息。

14.2.5 信息增益比

信息增益值是相对于训练数据集而言的。 特征A对训练数据集D的信息增益比\(g_R(D,A)\)是其信息增益\(g(D,A)\)与训练数据集D的经验熵之比

\[ g_R(D,A)=\frac{g(D,A)}{H(D)} \]

14.2.6 决策树生成

14.2.6.1 ID3算法

在决策树的各个节点使用信息增益选择特征，递归地构建。 算法：从根结点开始，计算所有可能的信息增益，选择信息增益最大的特征作为结点的特征。

14.2.6.2 CART算法

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。 算法步骤： - 决策树生成：基于训练集生成

• 决策树剪枝：用验证集进行剪枝并选择最优的 回归树的生成： 假设X与Y为输入和输出变量，且Y是连续变量，给定训练集 \[ D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\} \]

一个回归树对应输入空间的一个划分以及在划分单元上的输出值。

\[ f(x)=\sum_{m=1}^Mc_mI(x\in R_m) \]

输入空间给定时候，可以用平方误差\(\sum_{x_i\in R_m}(y_i-f(x_i))^2\)进行表示回归树对于训练集的预测误差。 对于如何切分，主要采用的是启发式算法，随机选择第j个变量\(x_j^{(1)}\)和其值s，作为切分变量(splitting variable)和切分点(splitting point) 并定义两个区域：

\[ R_1(j,s)=\{x|x^{(j)}\leq s\}和R_2(j,s)=\{x|x^{(j)}> s\} \] 这样就得到了一个划分。 进一步需要遍历所有可能的切分然后找到最优的切分点，具体的实现方式是

\[ \min[\min_{c_1} \sum(y_i-c_1)^2+\min_{c_2}\sum(y_i-c_2)^2] \]

对固定输入变量j可以找到最优切分点s。

14.2.7 分类树的生成

分类树采用Gini最优特征选取。

Gini index（基尼指数）假设有k类，样本点属于第k类的概率为\(p_k\)，则该样本的Gini指数为 \[ Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2 \]

对于一个二分类问题，样本点属于第1类的概率为p，则该概率的Gini指数为 \[ Gini(p)=2p(1-p) \]

对于样本集合D，其Gini指数为

\[ Gini(D)=1-\sum_{k=1}^K(\frac{{|C_k|}}{|D|})^2 \]

基尼指数同样可以表示不确定性，\(Gini(D)\)表示集合D的不确定性，\(Gini(D,A)\)表示经过\(A=a\)分割之后，D的不确定性。Gini指数越大不确定越大。 具体的代码实现。

14.2.8 决策树回归

也称为回归树，用于分类时候就称为分类树。

14.2.8.1 boosting回归

各种的boosting方法都是一个组合方法，将各种的学习器组合起来形成强学习器。

14.3 K近邻法

14.3.1 k近邻算法

给定一个训练集，找到附近的输入实例，在训练集中找到最邻近的k个实例。在这k个实例的多数属于某个类。就将该输入实例分为这个类。在分类任务中可使用”投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；在回归任务中可以使用”平均法”，即将这k个样本的实值输出标记的平均值作为预测结果；同样可以使用加权的投票方法。

14.3.2 评价准则

评估的方法是按照判断的错误率： \[ P(err)=1-\sum_{c\in\mathcal{Y}}P(c|x)P(c|z) \] 假设样本独立同分布，对任意\(x\)和任意小正数\(\delta\)，在\(x\)附近\(\delta\)距离内总能找到一个训练样本；对任意测试样本，总能在任意近的范围内找到训练样本\(z\)。令\(c^*=\arg\max_{c\in\mathcal{Y}}P(c|x)\)，表示最优分类器的结果。有

\[ \begin{aligned}P(err)&= 1-\sum P(c|x)P(c|z)\\&\le1-P^2(c|x)\\&=(1+P(c^*|x))(1-P(c^*|x))\\&\le2\times(1-P(c^*|x))\end{aligned}\] 最终我们会发现：泛化误差不超过贝叶斯最优分类的错误率的两倍。

14.4 贝叶斯分类方法

贝叶斯定理： \[ P(H|X)=\frac{P(X|H)P(H)}{P(X)} \]

同时我们需要知道，贝叶斯规则与贝叶斯推断是无关的，即可用频率学派（frequentist）的方法，又可以用贝叶斯方法来估计贝叶斯准则。

用数学形式来表示贝叶斯分类器：

\[ h^*(x)=\begin{cases} 1, \quad P(Y=1|X=x)>P(Y=0|X=x)\\ 0,\quad otherwise \end{cases} \]

Theorem 14.1 贝叶斯准则是最优的，即对于h是任何其他分类规则，则\(L(h^*)\le L(h)\)

1. 经验风险最小化
2. 回归：找出一个回归函数r的一个估计 \(\hat{r}\) 并且定义 \[ \hat{h}(x)=\begin{cases}1,\quad \hat{r}(x)>\frac12\\0,\quad otherwise\end{cases} \]
3. 密度估计：对于\(Y_i=0\) 从\(X_i\)来估计\(f_0\)，对于\(Y_i=1\)从\(X_i\)来估计\(f_1\)，同时令\(\hat{\pi}=n^{-1}\sum Y_i\)定义 \[ \hat r(x)=\hat P(Y=1|X=x) \]

14.5 高斯分类器与线性分类器

14.5.1 朴素贝叶斯分类

• 假设D是训练元组和类标号的集合。每个元组用\(n\)维属性类标号\(X=\{x_1,\cdots,x_n\}\)来表示，描述\(n\)个属性\(A_1,A_2,\cdots,A_n\)对元组的n个测量。
• 假定有\(m\)个类，给定元组\(X\)，朴素贝叶斯将\(X\)预测为\(C_i\)，当且仅当

\[P(C_i|X)>P(C_j|X),\quad 1\le j\le m,j\neq i\]

如此，最大化的\(P(C_i|X)\)，其中的类\(C_i\)称为最大后验假设。