第三章判别式分类器

分类器

定义

分类器通过条件概率分布 $P(y|x)$ 或判别函数 $f(x)$ 定义。

条件概率分布：比较并得出概率最大的类为所属类。
判别函数：通过阈值比较判定所属类。

生成式模型和判别式模型

生成式模型

利用条件概率密度预测所属分类。

判别式模型

根据估计的函数确定输出的类别。

区别

生成式模型注重相似度，判别式模型注重边界。
一般情况下，生成式模型收敛速度更快，判别式模型效果更好。

判别函数

线性判别函数

模式分类若可用任一个线性函数来划分，则这些模式就称为线性可分的，否则就是非线性可分的。

线性可分的判定

将 $d$ 维的 $N$ 个样本投影到 $d - 1$ 维空间中，可观察得到其相应方向的线性可分性。

多类情况1

每个线性判别函数将一类模式与其他模式分开。即， $c$ 个线性判别函数决定 $c$ 类问题。

又称为二分法。

多类情况2

每个线性判别函数将制定的某两类模式分开。即， $c$ 类问题需要 $\frac{c(c - 1)}{2}$ 个线性判别函数来解决。

与多类情况1相比：

缺点：需要更多的判别函数。
优点：更可能是线性可分的。

多类情况3

每两个相邻的类由一个线性判别函数分开。解决问题时取最大值。

广义线性判别函数

将数据通过非线性变化，映射到高维空间中，使其在高维空间中线性可分。

分段线性判别函数

分段线性判别函数比一般的线性判别函数的错误率小，但又比非线性判别函数简单。

可以理解为线性和升维的折中操作。

最小距离分类

构造最小距离分类器，使决策面为两类期望连线的垂直平分面。

Fisher 线性判别

考虑把 $d$ 维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。

基本问题

如何根据实际情况找到一条最好的、最易于分类的投影线，使在这个方向的直线上，样本的投影能分得开。

准则函数

$J(\omega) = \frac{\omega^TS_B\omega}{\omega^TS_W\omega}$

用于评估投影向量的优劣。

最优投影向量

$\omega = S_W^{-1}(\mu_1 - \mu_2)$

表示沿着 $\omega$ 的方向投影后，类间距离相对于类内距离最大，从而实现最佳的分类效果。

感知器算法

通过对已知样本的训练和学习来得到确定判别函数的系数。

确定性的方法

感知器算法不需要对各类别中模式的统计性质做任何假设，因此称为确定性的方法。

流程

对权向量，分类正确的模式进行奖赏（即不惩罚），分类错误的模式进行惩罚。
对样本进行多轮训练，只要仍有分类错误的模式，便用全部样本重新训练。
不断反复直到全部模式样本进行训练都能得到正确的分类结果。

收敛性

只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。

但是，感知器算法本身无法区别模式类别是否线性可分。

多类感知器算法

得出的函数针对多类情况3。

多类情况增广向量不需要变为负数，要求这个类别的比其他的类别都要大，否则这个类别+样本，其他的类别-样本。

可训练的确定性分类器的迭代算法

梯度法

梯度

指向函数在变量增加时最大增长率的方向的向量，也称上升方向。

固定增量的逐次调整算法

若模式不是线性可分的，算法的结果就会来回摆动，无法收敛。

最小平方误差(LMSE)算法

可以指出类别不可分的情况。

H-K算法属于LMSE算法的一种。

势函数法

用势函数的概念来确定判别函数和划分类别界面。

决策树

使用二叉树结构分类器，把一个复杂的多类别分类问题转化为多级多个两类问题来解决，在每个非终止节点都把样本集分成左右两个子集。

每个节点只选择一个特征，并给出相应的决策阈值。

—–

第三章 判别式分类器

分类器

定义