线性分类方法

感知机和线性判别分析/Fisher分析是非常经典的硬分类线性模型，模型提出都比较早。

感知机

感知机是二类分类的线性分类模型。
感知机只在求出线性可分的分类超平面，通过梯度下降法对损失函数极小化建立感知机模型。
感知机1957年由Rosenblatt提出，是神经网络和支持向量机的基础

模型

输入空间是实例向量组成的空间，输出空间是-1和+1（正负两类）。建立如下函数：

\begin{align*} f(x)&=sign(\omega \cdot x+b)\\ \omega&:weight\quad or\quad weight\quad vector\\ b&:bias \end{align*}

策略

感知机学习算法是错误驱动的，刚开始提出时以误分类样本点数量为损失函数，但因为该函数不连续，所以后来变成了最小化样本点到直线的距离。
image.png
image.png

算法（原始形式）

具体采用随机梯度下降法(SGD)。
image.png

收敛性

Novikoff定理告诉我们线性可分数据集经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。

对偶形式

image.png
image.png

线性判别分析

线性判别分析是Fisher提出的一种分类方法，其核心思想是将寻找一个合适的投影方向，使得投影后的样本“类间差异尽可能大，类内差异尽可能小”。线性判别分析是一种监督学习算法，也是一种经典的降维算法。即数据集投影到低维空间后，希望每一种类别数据的投影点尽可能的接近，而不同类别的数据的类别中心之间的距离尽可能的远。
对于一个样本点xx，其投影后的长度y=wTxy=w^Tx(这里记为ziz_i，其中ww为投影方向（模长为1，也是直线的系数向量)。定义类内方差:

\begin{align*} S&=\frac{1}{N} \sum_i(z_i-\bar{z})(z_i-\bar{z})^T\\ &=\frac{1}{N}\sum_i w^t((X_i-\bar{X})(X_i-\bar{X})^T)w\\ &=w^TSw \end{align*}

其中S为不同特征之间的样本协方差矩阵。
类间差异定义为不同类别投影均值的差的平方和，以二分类为例，类间差异定义为:

\begin{align*} (\bar{z_1}-\bar{z_2})^2&=w^T(\bar{X_1}-\bar{X_2})(\bar{X_1}-\bar{X_2})^Tw\\ \end{align*}

其中X1ˉ\bar{X_1}和X2ˉ\bar{X_2}分别为两个类别的均值向量。
接着定义类间方差和类内方差之比为目标函数(二分类):

\begin{align*} J(w)&=\frac{w^T(\bar{X_1}-\bar{X_2})(\bar{X_1}-\bar{X_2})^Tw}{w^T(S_1+S_2)w}\\ &=\frac{w^TS_bw}{w^TS_ww}\\ S_b&: between-class\\ S_w&: with-class\\ \end{align*}

接着最大化目标函数得到:

\begin{align*} S_bw&=\lambda S_ww\\ \lambda&:\frac{w^TS_bw}{w^TS_ww}\\ w&\propto S_w^{-1}S_b(\text{实数不影响优化方向}) \end{align*}

PCA 和 LDA 有很多的相似点，其本质是要将原始的样本映射到维度更低的样本空间中，但是 PCA 和 LDA 的映射目标不一样：PCA 是为了让映射后的样本具有最大的发散性；而 LDA 是为了让映射后的样本有最好的分类性能。所以说 PCA 是一种无监督的降维方法，而 LDA 是一种有监督的降维方法。
它经常被用于人脸识别、客户识别和医学领域，以识别病人的疾病状况。

非线性方法

逻辑回归

逻辑回归是一种常用的二分类方法，广泛应用于医学疾病诊断和电商数据领域，具体介绍见Logistic Regression

多分类问题的二分类方法

OvR（One vs Rest），一对剩余的意思，有时候也称它为 OvA（One vs All）；一般使用 OvR，更标准；n 种类型的样本进行分类时，分别取一种样本作为一类，将剩余的所有类型的样本看做另一类，这样就形成了 n 个二分类问题，使用逻辑回归算法对 n 个数据集训练出 n 个模型，将待预测的样本传入这 n 个模型中，所得概率最高的那个模型对应的样本类型即认为是该预测样本的类型；
OvO（One vs One），一对一的意思；n 类样本中，每次挑出 2 种类型，两两结合，一共有Cn2C_n^2 种二分类情况，使用Cn2C_n^2种模型预测样本类型，有 Cn2 个预测结果，种类最多的那种样本类型，就认为是该样本最终的预测类型；
改造方法不是指针对逻辑回归算法，而是在机器学习领域有通用性，所有二分类的机器学习算法都可使用此方法进行改造，解决多分类问题；