分类问题（Classification）

引入

开始前先回顾一下贝叶斯决策理论。

给定观测变量$x$，我们要找到类别$C_k$的后验概率，有如下关系：

决策的条件是：
如果$p(C_1|x)>p(C_2|x)$，则选择$C_1$，否则$C_2$。用上面的条件概率则可以写成：

遵从这一规则的分类器称为贝叶斯最优分类器（Bayes optimal classifier）。 \
以前我们要计算计算这个分类后验的话，需要根据贝叶斯公式，建立模型并估计条件密度$p(x|C_k)$和类别先验$p(C_k)$，通过最大化$p(C_k|x)$来使错误概率最小。\
但现在我们不再需要对密度进行建模，而是直接编码决策边界，然后最小化错误概率。

判别函数（Discriminant Functions）

基本知识

大概就是通过比较法对数据进行分类。现有数据$x$，以及$K$个类别，对应有$K$个判别函数：$y_1(x),...,y_k(x)$当$y_k(x)>y_j(x)$时，将数据$x$分类给$C_k$。
举个例子，根据贝叶斯分类器，判别函数可有如下几种形式：$y_k(x)=p(C_k|x)$ $y_k(x)=p(x|C_k)p(C_k)$ $y_k(x)=\log(x|C_k)+\log p(C_k)$
再举个例子，当$K=2$，即是说只有两个类别时，判断为类别$1$的标准有以下几种形式：$y_1(x)>y_2(x)$ $y(x)>0$ 其中$y(x)$可以为以下两种形式：$y(x)=p(C_1|x)-p(C_2|x)$ $y(x)=\log \frac{p(x|C_1)}{p(x|C_2)}+\log \frac{p(C_1)}{p(C_2)}$

线性判别函数（Linear Discriminant Functions）

二分类

在线性判别器中，决策面是（超）平面，其线性决策方程为：

$$y(x)=w^Tx+w_0$$ 此处$w$是法向量，$w_0$是偏置。 假设数据维度是2的话，其图示为：  上图那些写得复复杂杂的东西就是在计算距离。稍微写得清楚一点的话就是，假设现有一点$x_0$，其到分离（超）平面的距离为：$r=\frac{|w*x_0+b|}{||w||}$，其中$||w||$为2范数。 ### 多分类 对于多分类，如果我们只是简单地运用二分类地决策规则，则可能会产生争议数据（区间），比如说下面两种情况：  运用判别函数则可以知道每个数据属于某一标签的”可信度“，毕竟”距离“有长有短容易比较。其实跟上面的二分类类似，只是这里比较的东西多一点。如下图：  如果判别函数是线性的，则决策区域是互相连接且是凸的。 # Fisher 判别分析（Fisher Discriminant Analysis） Fisher线性判别分析是线性判别分析（LDA模型）的一种，它的目的大概就是：给定一个投影向量$w$，将数据$x$投影到$w$向量上，使得不同类别的$x$投影后的值$y$尽可能互相分开。 ## 一个例子用作引出 在讲解这个判别分析前先来看个例子： 以二维数据为例，也就是上面提过的：  其数据形式以及分类标准如下：$$y(x)=+1 \leftrightarrow x\in C_1$$ $$y(x)=-1 \leftrightarrow x\in C_2$$ 训练输入：$X=\left\{x_1 \in \mathcal{R}^d,...,x_n\right\}$\ 训练标签：$Y=\left\{y_1\in[-1,+1],...,y_n\right\}$\ **最小二乘法**\ 我们先尝试用最小二乘法。\ 先写出线性判别函数：$$x_i^Tw+w_0=y_i,\forall i=1,...,n$$每个训练数据点及标签都有一个线性方程。\ 把偏置$w_0$整合进权重$w$里比较好看，训练数据点也要因此多一个维度，即是：$$\hat{x}_i=(x_i \quad1)^T\in\mathcal{R}^{d\times1}$$ $$\hat{w}=(w \quad w_0)^T\in\mathcal{R}^{d\times1}$$所以方程改成：$$\hat{x}_i^T\hat{w}=y_i,\quad \forall i=1,...,n$$表示成矩阵向量形式则如下：$$\hat{X}^T\hat{w}=y$$此处$\hat{X}=[\hat{x}_1,...,\hat{x}_n]\in \mathcal{R}^{d\times n},\quad y=[y_1,...,y_n]^T$\ 这里有$n$个方程和$d+1$个未知数，属于超定方程（因为一般来说$n$总是大于$d+1$的）。\ 用最小二乘法求解如下：  这部分和上一篇的线性回归里的是一样的。 用最小二乘法有个问题，就是这种方法对于异常值特别敏感，下面两幅图就很直观了：  ## 正式开始 对数据进行投影，这有一幅形象的图：  这里大抵还是跟前面类似，不过换个名字比较好说明。\ 投影（Projection）：$y=w^Tx$\ 对照阈值进行分析：$w^Tx\ge -w_0$ 或$w^Tx+w_0\ge0$\ 怎样的投影$w$才是一个好的投影呢？可以最大限度地扩大两类之间的 "距离"，以实现良好的分离。那怎么做？ ### 尝试最大化两个类的均值（效果不好） 首先我们可以试试两个类的均值，让其距离最大：  将均值投影到一维线上，如下：  然后最大化两均值距离的平方：$$\max(m_1-m_2)^2$$即是：  这里据说有个明显的问题，这个距离会随着$w$的norm的增加而无限增加，为了限制这种情况，我们加个约束条件，就有了如下式子：  这是一个带约束条件的优化问题，第一想法肯定是用拉格朗日了，加入拉格朗日算子，各种计算，就有下面的过程：  解出：$$w=\frac{m_1-m_2}{||m_1-m_2||}$$

我们能得出下图的结果：

这又有个问题，由图可以看出，两个类有很大一部分重合了。下面这个图才是我们想要的：

但要怎么做？
一波自问自答：在尽可能远得分离两均值得同时，也要让每个类得方差尽量小。

同时考虑均值和方差（正式引入Fisher线性判别法）

定义每个类的方差：

然后是Fisher标准：

将分子展开：

这就引入了类别间的协方差。
然后再将分母展开：

综合以上两个展开，Fisher标准可以写成：

对$w$进行微分并等于0则有：$(w^TS_Bw)S_Ww=(w^TS_Ww)S_Bw$
在这里$(w^TS_Bw)$和$(w^TS_Ww)$都是标量，所以有：$S_Ww ||S_Bw$这里$||$表共线（collinearity）。
然后由上面的式子我们可以知道：$S_Bw=(m_1-m_2)(m_1-m_2)^Tw\rightarrow S_Bw||(m_1-m_2)$(还是因为标量的关系所以共线)。
同理可得：$S_Ww\quad ||\quad(m_1-m_2)$ $w\quad || \quad S_W^{-1}(m_1-m_2)$
所以就引出了Fisher 线性判别（Fisher’s Linear Discriminant）：$w\propto S_W^{-1}(m_1-m_2)$
这个线性判别只提供了投影，我们还需要找到阈值，方法有不少，比如贝叶斯分类器和高斯分类条件。\
当类条件分布相等，且协方差是对角矩阵，则Fisher线性判别是贝叶斯最优的。\
值得注意的是，Fisher线性判别法是最小二乘法的一个特例。另外，这种方法对于噪声依旧很敏感

感知器算法（Perceptron Algorithm）

感知器算法是一种可以直接得到线性判别函数的线性分类方法，是基于样本线性可分的要求下使用的。\
如果我们的类别线性可分，则我们肯定可以找到一个分离（超）平面。\
感受器判别函数（Perceptron discriminant function）为：$y(x)=sign(w^Tx+b)$此处的$sign(x)=\left\{+1,x>0;0,x=0;-1,x<0\right\}$\
即是下图的函数：

感知器算法的基本步骤如下：

现在就出现了一个优化问题了，这里最直接的想法是计算误分类的点总数，但这种方法不好微分，就用另一种，计算点到分离（超）平面的距离，就引出了下面这个优化函数：

在很多地方更常见的是计算最小值，但都一样，只是他们事先加了个负号，这里没加。稍微解释一下，对于误分类的点，比如点$x_i$，不管是把这个点误分到了哪一类，$y_i(wx_i+b)$都是小于0的，毕竟如果大于0就意味着同号即是分类正确了。\
把下面那个式子写完全的话应该是这样子：$$\sum_{x\in X:\left\langle w,x \right\rangle <0}\left\langle w,x \right\rangle =\sum_{…}\frac{1}{||w||}y_i(wx_i+b)$用gradient的方法求解如下：$\frac{\partial J}{\partial w}=\sum_{…}x$$

注意，经典的感知器只能做线性二分类。

逻辑回归（Logistic Regression）

（这部分接触过很多，就简单记了）

Generative vs. Discriminative

对解决分类问题一般有两种方向，Generative 和 Discriminative，这里对两种方法做个大概的对比：

Generative modelling:
我们先构造条件分布模型$p(x|C_2)$和$p(x|C_1)$
运用贝叶斯规则计算其后验分布
例子：Navie Bayes

Discriminative modelling:
我们直接构造类的后验比如说$p(C_1|x)$
我们只关心分类是否正确，而不关心是否符合类的条件。
例子：逻辑回归

概率判别模型（Probabilistic Discriminative Models）

Sigmoid函数的引出

运用贝叶斯定理：

其图像如下，呈$S$型，将传入的实数压在$[0,1]$区间内。

假设里面这个$\alpha$是线性的话（当然也可以是其它），后验就可以写为：$p(C_1|x)=\sigma(w^Tx+w_0)$然后就是求权重和偏置了。
求这两个东西的方法也有不少，印象中梯度下降应该是比较常见的，因为太常见了，所以这里不记录，而是记录最大似然：

（附）作业相关代码

import numpy as np
import matplotlib.pyplot as plt

def load_split_data(path):
    data = np.loadtxt(path)
    C_1 = data[:50]
    C_2 = data[50:93]
    C_3 = data[93:]
    return C_1, C_2, C_3, data


def linear_discriminant_analysis(c_1, c_2):
    """
    params:
        c_1(ndarray): (n, 2)
        c_2(ndarray): (n, 2)
    return:
        w(ndarray): (2,1)
    """
    n1, d1 = c_1.shape
    n2, d2 = c_2.shape
    m1 = np.mean(c_1, axis=0)#(1,2)
    m2 = np.mean(c_2, axis=0)

    sw_1 = np.zeros((d1,d1))
    sw_2 = np.zeros((d2,d2))

    for i in range(n1):
        temp_sw = (c_1[[i]] - m1).T @ (c_1[[i]] - m1)
        sw_1 += temp_sw
    for j in range(n2):
        temp_sw = (c_2[[j]] - m2).T @ (c_2[[j]] - m2)
        sw_2 += temp_sw
    sw = sw_1 + sw_2
    inv_sw = np.linalg.inv(sw)
    w = inv_sw @ (m1 - m2).T#(2,1)
    return w
    
def decide(w, x, m1, m2, N1, N2):
    """
    params:
        w(ndarray): weight, (2,1)
        x(ndarray): data, (1,2)
        m1(ndarray): mean of class1, (1,2)
        m2(ndarray): mean of class2, (1,2)
        N1(int): nums of class1
        N2(int): nums of class2
    return:
        True: c1
        False: c2
    """
    y = w.T @ x.T
    #w0 = (N1 * (w.T @ m1.T) + N2 * (w.T @ m2.T)) / (N1 + N2)
    w0 = (w.T @ m1.T + w.T @ m2.T) / 2 
    if y > w0:
        return True
    else:
        return False



def main():
    path = "./dataSets/ldaData.txt"
    C_1, C_2, C_3, data = load_split_data(path)

    w_12 = linear_discriminant_analysis(C_1, C_2)
    w_23 = linear_discriminant_analysis(C_2, C_3)
    w_13 = linear_discriminant_analysis(C_1, C_3)

    c1 = []
    c2 = []
    c3 = []

    N1 = len(C_1)
    N2 = len(C_2)
    N3 = len(C_3)

    m1 = np.mean(C_1, axis=0)
    m2 = np.mean(C_2, axis=0)
    m3 = np.mean(C_3, axis=0)

    N, d = data.shape
    for i in range(N):
        if decide(w_12, data[i], m1, m2, N1, N2):
            # not c2
            if decide(w_13, data[i], m1, m3, N1, N3):
                # c1
                c1.append(data[i])
            else:
                # c3
                c3.append(data[i])
        else:
            # not c1
            if decide(w_23, data[i], m2, m3, N2, N3):
                # c2
                c2.append(data[i])
            else:
                # c3
                c3.append(data[i])

    #plot orignal_data
    for i in range(len(C_1)):
        plt.scatter(C_1[i, 0], C_1[i, 1], marker = "v", color = "r")
    for i in range(len(C_2)):
        plt.scatter(C_2[i, 0], C_2[i, 1], marker = "x", color = "y")
    for i in range(len(C_3)):
        plt.scatter(C_3[i, 0], C_3[i, 1], marker = "o", color = "b")
    plt.title("orignal_data")
    plt.show()

    #plot LDA
    for sub_data in c1:
        plt.scatter(sub_data[0], sub_data[1], marker = "v", color = "r")
    for sub_data in c2:
        plt.scatter(sub_data[0], sub_data[1], marker = "x", color = "y")
    for sub_data in c3:
        plt.scatter(sub_data[0], sub_data[1], marker = "o", color = "b")
    plt.title("LDA")
    plt.show()    
            
    
if __name__ == "__main__":
    main()

效果如下：