机器学习算法之线性判别分析(LDA二分类)

蔚落 2023-05-31 03:24 8阅读 0赞

# 算法原理 #

线性判别分析(Linear Discriminant Analysis, LDA)的原理比较简单，就是我们希望寻找到一条直线，然后我们将数据投影到这条直线上，使得这两种数据之间尽可能远离，并且同类数据尽可能聚集在一起。  
假设我们有两类数据，也就是说这里是针对二分类问题以及对应的标签。数据表示为 D = ( x i , y i ) i = 1 m , m = 2 , y i ∈ ( 0 , 1 ) D=\{(x\_i,y\_i)\}\_\{i=1\}^m,m=2,y\_i\\in\{(0,1)\} D=(xi,yi)i=1m,m=2,yi∈(0,1)。我们希望可以找到一条直线 y = w 1 x 1 + w 2 x 2 = w x y=w\_1x\_1+w\_2x\_2=wx y=w1x1\+w2x2=wx把两种样本分开。为了达到这个目的，我们首先要让同类的样本投影点尽可能小，即希望 w T ∑ w w^T\\sum w wT∑w小，同时我们还想让两个类的中心 u 1 , u 2 u\_1,u\_2 u1,u2投影后的距离尽量大，即 ∣ ∣ w T u 1 − w T u 2 ∣ ∣ ||w^Tu\_1-w^Tu\_2|| ∣∣wTu1−wTu2∣∣尽量大。  
定义“类内散度矩阵”：  
 S w = Σ 1 + Σ 2 = ∑ x ∈ X 1 ( x − μ 1 ) ( x − μ 1 ) T + ∑ x ∈ X 2 ( x − μ 2 ) ( x − μ 2 ) T S\_\{w\}=\\Sigma \_\{1\}+\\Sigma \_\{2\}=\\sum\_\{x \\in X1\}(x-\\mu\_\{1\} )(x-\\mu\_\{1\} )^\{T\}+\\sum\_\{x \\in X2\}(x-\\mu\_\{2\} )(x-\\mu\_\{2\} )^\{T\} Sw=Σ1\+Σ2=∑x∈X1(x−μ1)(x−μ1)T\+∑x∈X2(x−μ2)(x−μ2)T

定义“类间散度矩阵”：  
 S b = ( μ 1 − μ 2 ) ( μ 1 − μ 2 ) T S\_\{b\}=(\\mu\_\{1\}-\\mu\_\{2\} )(\\mu\_\{1\}-\\mu\_\{2\} )^\{T\} Sb=(μ1−μ2)(μ1−μ2)T  
则我们的代价函数可写为：  
 J = w T S b w w T S w w （ 1 ） J=\\frac\{w^\{T\}S\_\{b\}w\}\{w^\{T\}S\_\{w\}w\} （1） J=wTSwwwTSbw（1）  
这个等式叫“广义瑞利商”，这部分的仔细推导需要参考西瓜书第61页。

最后，我们希望最大化上述代价函数，由于代价函数的分子分母都有2个w，因此J的最大解与w的长度无关，只与方向有关，我们令：  
 w T S w w = 1 w^TS\_ww=1 wTSww=1，则(1)式等价于：

m i n w − w T S b w min\_\{w\}-w^\{T\}S\_\{b\}w minw−wTSbw  
 s . t . w T S w w = 1 s.t. w^\{T\}S\_\{w\}w=1 s.t.wTSww=1  
使用拉格朗日乘子法：  
 c ( w ) = w T S b w − λ ( w T S w w − 1 ) c(w)=w^\{T\}S\_\{b\}w-\\lambda (w^\{T\}S\_\{w\}w-1) c(w)=wTSbw−λ(wTSww−1)  
 ⇒ d c d w = 2 S b w − 2 λ S w w = 0 \\Rightarrow \\frac\{dc\}\{dw\}=2S\_\{b\}w-2\\lambda S\_\{w\}w=0 ⇒dwdc=2Sbw−2λSww=0  
 ⇒ S b w = λ S w w ( 2 ) \\Rightarrow S\_\{b\}w=\\lambda S\_\{w\}w (2) ⇒Sbw=λSww(2)

这里观察可知 S b w S\_bw Sbw的方向恒为 μ 1 − μ 2 \\mu\_1-\\mu\_2 μ1−μ2。  
所以令： S b w = λ ( μ 1 − μ 2 ) S\_\{b\}w=\\lambda (\\mu\_\{1\}-\\mu\_\{2\}) Sbw=λ(μ1−μ2)  
带入(2)得： w = S w − 1 ( μ 1 − μ 2 ) w=S\_\{w\}^\{-1\}(\\mu \_\{1\}-\\mu \_\{2\}) w=Sw−1(μ1−μ2)  
有了这个式子，我们就可以写出代码来可视化看看了。

# 代码实现 #

#coding=utf-8
    import numpy as np
    import matplotlib.pyplot as plt
    from sklearn.datasets.samples_generator import make_classification
    
    def LDA(X, y):
        X1 = np.array([X[i] for i in range(len(X)) if y[i] == 0])
        X2 = np.array([X[i] for i in range(len(X)) if y[i] == 1])
    
        len1 = len(X1)
        len2 = len(X2)
    
        # 求均值向量u1,u2
        miu1 = np.mean(X1, axis=0)
        miu2 = np.mean(X2, axis=0)
    
        # 求S_w
        # \sum_0
        conv1 = np.dot((X1 - miu1).T, (X1 - miu1))
        # \sum_1
        conv2 = np.dot((X2 - miu2).T, (X2 - miu2))
        Sw = conv1 + conv2
    
        # 计算w
        w = np.dot(np.mat(Sw).I, (miu1 - miu2).reshape((len(miu1), 1)))
        X1_new = np.dot(X1, w)
        X2_new = np.dot(X2, w)
        y1_new = [0 for i in range(len1)]
        y2_new = [1 for i in range(len2)]
        return X1_new, X2_new, y1_new, y2_new
    
    def main():
        X, y = make_classification(n_samples=500, n_features=2, n_redundant=0, n_classes=2,
                                   n_informative=1, n_clusters_per_class=1, class_sep=0.5, random_state=10)
    
        X1_new, X2_new, y1_new, y2_new = LDA(X, y)
    
        # 可视化原始数据
        plt.scatter(X[:, 0], X[:, 1], marker='o', c=y)
        plt.show()
        # 可视化LDA降维后的数据
        plt.plot(X1_new, y1_new, "bo")
        plt.plot(X2_new, y2_new, "ro")
        plt.show()
    
    main()

# 数据 #

使用sklearn的make\_classification产生两个分类的随机数据，可视化如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3Rfc29ydA_size_16_color_FFFFFF_t_70]  
经过LDA之后，我们将每个数据的标签可视化出来：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3Rfc29ydA_size_16_color_FFFFFF_t_70 1]  
可以看到LDA算法将我们的数据集很好的分开了，由此可以说明LDA是有效的。  
这里有个最大的缺点是这里的算法只能处理二分类，要处理多分类的话，需要在这个算法的基础上进行推广。请看下文。

# 参考文章 #

https://blog.csdn.net/z962013489/article/details/79871789

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3Rfc29ydA_size_16_color_FFFFFF_t_70]: /images/20230531/af17d0f3c6c147ba886e73aecce97deb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3Rfc29ydA_size_16_color_FFFFFF_t_70 1]: /images/20230531/5411ebb800274fbba2d678e213343e0d.png