Simple Classification

二分类与多分类问题

分类是一种朴素而又深刻的思想，要是人工智能成为现实，解决分类问题是必须的。分类可以更好的挖掘数据中的信息，也便于对数据的捆绑加工。分类可以降低世界的复杂度，将世界中复杂的关系简化为类与类之间的联系，从而有可能通过机器来认知刻画这个世界。

线性判别分析

线性判别分析（Linear Discriminant Analysis）是一种经典的线性学习方法，用于解决二分类问题。LDA的基本思想是将样例投影到一条直线上，并使同类样例的投影点尽可能接近，使异类样例的投影点尽可能远离。在对新的样本进行分类时根据其投影点在直线上的位置进行分类。如下图为一个二维示例：

LDA模型详析

当给定数据集$D=\{(x_{i},y_{i})\}_{i=1}^{m},\ y_{i}\in\{0,1\}$，令$X_{i}、\mu_{_{i}}、\sum_{i}$分别表示第i$\in\{0,1\}$类样例的集合、均值向量、协方差矩阵。若将数据点投影到直线上，两类样例的中心分别在$w^{T}\mu_{0}和w^{T}\mu_{1}$，两类样本的协方差分别为$w^{T}\sum_{0}w和w^{T}\sum_{1}w$，由于直线是一维的，因此$w^{T}\mu_{0}、w^{T}\mu_{1}、w^{T}\sum_{0}w\ 和 \ w^{T}\sum_{1}w$

均为实数。

想要使同类样例尽可能接近，可以让同类样例投影点的协方差尽可能小，即$w^{T}\sum_{0}w-w^{T}\sum_{1}w$尽可能小；想要使异类投影点之间的距离尽可能大，则要让$||w^{T}\mu_{0}+w^{T}\mu_{1}||_{2}^{2}$尽可能大，同时考虑上述两个因素，我们可以得到我们要最大化的目标：

$$J=\frac{||w^{T}\mu_{0}-w^{T}\mu_{1}||_{2}^{2}}{w^{T}\sum_{0}w+w^{T}\sum_{1}w}\\ =\frac{w^{T}(\mu_{0}-\mu_{1})(\mu_{0}-\mu_{1})^{T}w}{w^{T}(\sum_{0}+\sum_{1})w}$$

定义”类内散度矩阵”（within-class scatter matrix）

$$S_{w}=\sum_{0}+\sum_{1}\\ =\sum_{x\in X_{0}}(x-\mu_{0})(x-\mu_{0})^{T}+\sum_{x\in X_{1}}(x-\mu_{1})(x-\mu_{1})^{T}$$

同样的，定义类间散度矩阵（between-class scatter matrix）

$$S_{b}=(\mu_{0}-\mu_{1})(\mu_{0}-\mu_{1})^{T}$$

则式（1）可以重写为

$$J=\frac{w^{T}S_{b}w}{w^{T}S_{w}w}$$

这就是LDA的最大化目标，即$S_{b}与S_{w}$的广义瑞利商（generalized Rayleigh quotient)。

式（4）等价于

$$\underset{w}min\ -w^{T}S_{b}w\\ s.t.\ w^{T}S_{w}w=1$$

由拉格朗日乘子法可得

$$-w^{T}S_{b}w+\lambda w^{T}S_{w}w=0 \quad 求导\Rightarrow\\ S_{b}w=\lambda S_{w}w$$

通过观察我们可以发现$S_{b}w$的方向恒为$\mu_{0}-\mu_{1}$，因为

$$S_{b}w=(\mu_{0}-\mu_{1})\underset{这是一个数}{\underline{(\mu_{0}-\mu_{1})^{T}w}}\\ 不妨令\\ S_{b}w=\lambda (\mu_{0}-\mu_{1})\\ 则由（6）可得\\ w=\frac{1}{\lambda}S_{w}^{-1}S_{b}w=S_{w}^{-1}(\mu_{0}-\mu_{1})$$

考虑到数值解的稳定性，在实践中通常对$S_{w}$进行奇异值分解，即$S_{w}=U\sum V^{T}$，其中$\sum$是一个实对角矩阵它的对角线上的元素是$S_{w}$的奇异值，由此可以得到

$$S_{w}^{-1}=V{\sum}^{-1}U^{T}$$

LDA的多分类形式

现在假设存在N个类，且第i类样例数为$m_{i}$。现在我们来定义全局散度矩阵

$$S_{t}=S_{b}+S_{w}\\ =\sum_{i=1}^{m}(x_{i}-\mu)(x_{i}-\mu)^{T}$$

其中$\mu$是所有样例的均值向量。我们将类内散度矩阵$S_{w}$重新定义为每个类别的散度矩阵之和，即

$$S_{w}=\sum_{i=1}^{N}S_{w_{i}}\\ 其中\\ S_{w_{i}}=\sum_{x\in X_{i}}(x-\mu_{i})(x-\mu_{i})^{T}$$

由式（9）和（10）可得

$$S_{b}=S_{t}-S_{w}\\ =\sum_{i=1}^{N}m_{i}(\mu_{i}-\mu)(\mu_{i}-\mu)^{T}$$

多分类LDA采用优化目标如下：

$$\frac{tr(W^{T}S_{b}W)}{tr(W^{T}S_{W}W)}$$

其中$W\in R^{d*(N-1)}$，tr(.)表示矩阵的迹，式（12）可以通过如下广义特征值方程求解，得

$$S_bW=\lambda S_{W}W$$

若将W视为一个投影矩阵，则多分类LDA将样本投影到N-1维空间，N-1通常远小于数据原有的属性数。因此通过这个投影可以减少样本点的维数，可以起到降维的作用。