研究生课程：机器学习-第4章 非线性分类

《机器学习》课程笔记：第4章 非线性分类

第4章 非线性分类

概述

非线性问题：对于线性不可分数据，采用非线性决策的方法

线性扩展的思想：线性扩展模型，核函数方法

非线性的思想：最近邻、决策树、神经网络、集成学习

决策树

决策问题一定是一个二判决问题

样本根据问题一定可以分成两部分，两部分之间没有交集，两部分的并集包括所有的情况

决策树的目标：在树结构上，根据节点的判断，搜索类别。

树结构的优点：可以不必测试所有特征和区域。

问题数

1. 离散值情况：以特征或特征的可能离散值作为问题：

设属性的可能离散取值个数为

• 方法1：每个特征可以作为候选问题，例如ID3、C4.5，属性产生的候选问题数为（切分太快，容易过拟合）
• 方法2：每个特征的每个离散值作为候选问题，例如CART，属性产生的候选问题数为

2. 连续值情况：以每个维度的样本特征值作为问题

属性上出现的样本特征值个数为

方法：每个特征上的样本特征值作为候选问题，属性产生的候选问题数为

无论特征值是连续还是离散，确定每个属性所产生的候选问题，候选的问题总数为

划分（问题）选择

非纯度（Impurity Measure）需要满足两条性质：

• IM最大值时，各类别概率相等
• IM最小时为0，只有一类（期望的目标）

非纯度的熵度量（C4.5）：

非纯度的基尼度量（CART）：

划分目标：选择最大减少类别非纯度的问题作为划分节点。

基于非纯度变化量的三个指标：

• 信息增益（ID3）：越大越好
• 增益率（C4.5）：越大越好
• 基尼指数：越小越好

信息增益（熵度量）：，是问题导致的决策划分数目

倾向于选择划分集合个数多的节点。区间划分的越细，区间内纯度越高，极端情况每个区间只有一个样本，则熵为0。

增益率（信息增益与数据集关于问题的熵值之比）

，

增益率改善信息增益：对划分集合个数少的属性有所偏好，越小则越小

基尼指数（基尼度量）：

节点类别设置：叶子节点纯度达到预设阈值后，停止划分，并对叶子节点进行类别设置。（按概率最大的类别设定）

决策树生成

决策树生成过程

从顶向下（不断增加一个节点）

• 准则：所有划分中选择一个使（非纯度减少量）最大的划分为节点，加入决策树。
• 贪婪学习：根据划分准则，在问题集上进行划分，直到Impurity不能再改善，或达到较小的改善。
• 停止规则：设定阈值

ID3 决策树：属性特征作为结点问题，划分选择实际是特征选择过程，最大化信息增益作为划分选择依据

C4.5 决策树：属性特征作为结点问题，划分选择实际是特征选择过程，最大化信息增益率作为划分选择依据

CART 决策树：属性特征离散值作为结点问题，本质是二叉树，最小化基尼指数作为划分选择依据

连续值二叉决策树

剪枝处理

ID3、C4.5决策树剪枝

• 代价函数
• 剪枝算法

泛化性能评估法

最近邻方法

最近邻法

原理：将样本分类为离之最近的样本类别

类判别函数：

决策规则：

最近邻分类隐含的决策边界是非线性的

k-近邻法

原理：将样本分给个近邻中类别样本个数最多的类

为的个近邻中属于的样本数

判别函数：

决策规则：

误差讨论

近邻法的缺点：

• 存储量大：训练样本需要存到内存
• 计算量大：每次决策都要计算所有样本的相似性

近邻法的快速算法

快速算法一：快速搜索近邻法（不减少的情况下怎么样才能更快）

原理：将样本分成不相交的子集，基于子集的搜索

1. 样本分级分层为多个子集
2. 逐层搜出一个最优子集
3. 在最后的子集中局部找最近样本点

规则1-找最近子集：如果到的距离 > 当前最近子集距离，则被忽略。

规则2-找最近样本：如果到的距离>已存在的最近点，则样本被忽略。

k 近邻快速搜索推广：子集搜索过程与最近邻一致，样本搜索时，存有个最近距离值。

快速算法二：剪辑近邻法

原理：通过剪掉边界样本（错误分类样本），缩减样本规模

剪辑规则：两分剪辑近邻法

• 将训练样本集，分成两个子集，
• 做分类参考，对进行剪辑（错分样本被剪掉）
• 剪辑后的作为最终的训练集训练近邻分类器

快速算法三：压缩近邻法

原理：去掉中心附近样本，保留错误样本，在剪辑基础上进行压缩

基本思想：分类中通常被正确分类的样本，较少支持决策，将常分误的样本保留。

压缩规则：

1. 初始化，训练集分为，，中仅个样本；中个
2. 作为训练，分类中第个样本；如果错误，将该样本放入中
3. 对每一个样本重复2
4. 直到无错分样本，或为空
5. 将中样本放弃，是最终压缩样本集

拒绝决策近邻法

原理：对于与各类别相似度较低的样本，不做判断

优点：在样本压缩时，给可是可非的样本机会。

• 算法1：可拒绝的k近邻法（分类决策）-k近邻中，各类样本的个数小于 , 拒绝分类
• 算法2：可拒绝的编辑近邻法（样本压缩）-与编辑近邻法比较的不同之处：除保留正确分类样本外，还保留了拒绝样本。

集成学习

结合策略

原理：不同的分类器对样本有不同的鉴别力；综合优势，使错误率最小。

问题描述：已知一组训练分类器，分类器的类别后验为，其中为索引类别，为索引分类器.

目标是对进行分类，求

概率分布相似性的计算：

1. 期望之间的相似度：
2. 在每个维度上的log比值：和
3. 内积运算：

几种集成学习准则

Geometric Average Rule

• 目标函数：最小化KL平均
• 集成方法：
• 决策规则：

Arithmetic Average Rule

• 目标函数：最小化Alternative KL平均
• 集成方法：
• 决策规则：

Majority Voting Rule

• 原理：对两类问题，多个分类器进行决策投票，票数过半的类别为样本最终标签。
• 基分类器要求相互独立且正确率p>50%，且最好具有多样性

Bagging和随机森林

Bagging：通过随机采样，训练分类器，保证分类器的差异。从训练集中不断随机抽取样本构造分类器，分类时通过投票进行类别判断。

随机森林：多决策树的Bagging；决策树随机属性选择；从训练集中不断随机构造决策树分类器，分类时通过投票进行类别判断。

随机森林较一般Bagging效果好

Boosting: AdaBoost

Boosting原理：一系列弱分类器，在不同子集上学习，得到增强分类器。

AdaBoost加权分类器

AdaBoost 目标函数

非线性SVM

SVM 原理

两个核心思想

• 最大间隔：找到最大间隔分类超平面；
• 核函数方法：样本升维映射到高维空间后，采用线性决策。升维映射由核技巧实现。

数学问题

KKT：任何目标函数有解的充要条件

一个原始问题总有它的对偶问题

对于特殊的凸优化来说，原始问题的对偶问题是，两个函数的极值相等，也就是最优解是相等的

如果原始问题和它的对偶问题都满足KKT条件，对于条件好的凸优化，可以构造与的关系，从而将不好求解的原始问题转化为好求的对偶问题

最大间隔

目标：找到最大间隔分类超平面（类别集合到分类超平面的最小距离最大化）

函数间隔：给定的训练数据集和超平面

• 超平面关于样本的函数间隔定义为
• 超平面关于训练数据集的函数间隔定义为，即所有样本点的函数间隔的最小值。
• 存在问题：只要成比例的改变和，函数间隔会相应变化。

几何间隔：给定的训练数据集和超平面

• 超平面关于样本的几何间隔定义为
• 超平面关于训练数据集的几何间隔定义为，即所有样本点的几何间隔的最小值。
• 成比例的改变和，几何间隔不会相应变化。

最大几何间隔等价的问题：

函数间隔的取值并不影响最优化问题的解。

支撑向量（SV）：支撑最小距离最大化的样本

支撑超平面：通过支持向量，平行于分类面的超平面

间隔：支撑向量到分类面的距离

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

对偶问题

问题的求解

根据KKT条件成立求解

核函数方法

避免直接求非线性映射，由核函数替代内积运算

SVM 算法

硬间隔SVM

软间隔SVM