一、线性判别分析LDA原理

（一）线性判别分析LDA简介

线性判别分析LDA(Linear Discriminant Analysis)又称为Fisher线性判别，是一种监督学习的降维技术，也就是说它的数据集的每个样本都是有类别输出的，这点与PCA（无监督学习）不同。LDA在模式识别领域（比如人脸识别，舰艇识别等图形图像识别领域）中有非常广泛的应用，因此我们有必要了解下它的算法原理。

（二） LDA的思想

LDA的思想是：最大化类间均值，最小化类内方差。意思就是将数据投影在低维度上，并且投影后同种类别数据的投影点尽可能的接近，不同类别数据的投影点的中心点尽可能的远。

我们先看看最简单的情况。假设我们有两类数据
分别为红色和蓝色，如下图所示，这些数据特征是二维的，我们希望将这些数据投影到一维的一条直线，让每一种类别数据的投影点尽可能的接近，而红色和蓝色数据中心之间的距离尽可能的大。

上图提供了两种投影方式，哪一种能更好的满足我们的标准呢？从直观上可以看出，右图要比左图的投影效果好，因为右图的黑色数据和蓝色数据各个较为集中，且类别之间的距离明显。左图则在边界处数据混杂。以上就是LDA的主要思想了，当然在实际应用中，我们的数据是多个类别的，我们的原始数据一般也是超过二维的，投影后的也一般不是直线，而是一个低维的超平面。

（三） 瑞利商(Rayleigh quotient)与广义瑞利商(genralized Rayleigh quotient)

瑞利商的定义，瑞利商是指这样的函数


广义瑞利商是指这样的函数

（四） LDA的原理及推导过程

假设样本共有K类，每一个类的样本的个数分别为


第K 类样本的方差：

各个类别的样本方差之和：



所有类别之间的距离之和为：

证明

为对称矩阵：

注意: (1)选取特征值时，如果一些特征值明显大于其他的特征值，则取这些取值较大的特征值，因为它们包含更多的数据分布的信息。相反，如果一些特征值接近于0，我们将这些特征值舍去。
(2)由于 W 是一个利用了样本类别得到的投影矩阵，因此它能够降维到的维度d的最大值为 K-1

（五）LDA算法流程

（六）LDA算法优缺点

优点

• 1.在降维过程中可以使用类别的先验知识经验，而像PCA这样的无监督学习则无法使用类别先验知识。

• 2.LDA在样本分类信息依赖均值而不是方差的时候，比PCA之类的算法较优。

缺点

• 1.LDA不适合对非高斯分布样本进行降维，PCA也有这个问题。

• 2.LDA降维最多降到类别数k-1的维数，如果我们降维的维度大于k-1，则不能使用LDA。当然目前有一些LDA的进化版算法可以绕过这个问题。

• 3.LDA在样本分类信息依赖方差而不是均值的时候，降维效果不好。

• 4.LDA可能过度拟合数据。

二、线性分类算法（支持向量机SVM）

（一）SVM简介

支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。

（二）支持向量

1, 线性可分

首先我们先来了解下什么是线性可分。

在二维空间上，两类点被一条直线完全分开叫做线性可分。

2.最大间隔超平面

为了使这个超平面更具鲁棒性，我们会去找最佳超平面，以最大间隔把两类样本分开的超平面，也称之为最大间隔超平面。

• 两类样本分别分割在该超平面的两侧；
• 两侧距离超平面最近的样本点到超平面的距离被最大化了。

3. 支持向量

样本中距离超平面最近的一些点，这些点叫做支持向量。

4.SVM 最优化问题

SVM 想要的就是找到各类样本点到超平面的距离最远，也就是找到最大间隔超平面。任意超平面可以用下面这个线性方程来描述：


如图所示，根据支持向量的定义我们知道，支持向量到超平面的距离为 d，其他点到超平面的距离大于 d。

于是我们有这样的一个公式：

稍作转化可以得到：



每个支持向量到超平面的距离可以写为：


最大化这个距离：

（三）对偶问题

1. 拉格朗日乘数法

（1） 等式约束优化问题

本科高等数学学的拉格朗日程数法是等式约束优化问题：


（2）不等式约束优化问题
而我们现在面对的是不等式优化问题，针对这种情况其主要思想是将不等式约束条件转变为等式约束条件，引入松弛变量，将松弛变量也是为优化变量。

以我们的例子为例：


由等式约束优化问题极值的必要条件对其求解，联立方程：

2.强对偶性

对偶问题其实就是将：

变成了：

（四） SVM 优化

我们已知 SVM 优化的主问题是：

那么求解线性可分的 SVM 的步骤为：
（1）构造拉格朗日函数：

（2）利用强对偶性转化：

现对参数 w 和 b 求偏导数：

得到：

我们将这个结果带回到函数中可得：

也就是说

（3）SMO算法求解。

SMO(Sequential Minimal Optimization)，序列最小优化算法，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值。

（4）求 w 和 b

（5）构造出最大分割超平面和分类决策函数
最大分割超平面：

分类决策函数

（五）软间隔

1.解决问题

在实际应用中，完全线性可分的样本是很少的，如果遇到了不能够完全线性可分的样本，我们应该怎么办？比如下面这个：

于是我们就有了软间隔，相比于硬间隔的苛刻条件，我们允许个别样本点出现在间隔带里面，比如：

2.优化目标及求解

（1）构造拉格朗日函数：

（2）求偏导


（3）求w和b

（六）核函数

1.线性不可分

我们刚刚讨论的硬间隔和软间隔都是在说样本的完全线性可分或者大部分样本点的线性可分。

但我们可能会碰到的一种情况是样本点不是线性可分的，比如：

这种情况的解决方法就是：将二维线性不可分样本映射到高维空间中，让样本点在高维空间线性可分，比如：

2.核函数的作用

3.常见核函数

（七）优缺点

1.优点

• 有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；
• 能找出对任务至关重要的关键样本（即：支持向量）；
• 采用核技巧之后，可以处理非线性分类/回归任务；
• 最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。

2.缺点

• 训练时间长。当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为 [公式] ，其中 N 为训练样本的数量；
• 当采用核技巧时，如果需要存储核矩阵，则空间复杂度为 [公式] ；
• 模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。

因此支持向量机目前只适合小批量样本的任务，无法适应百万甚至上亿样本的任务。

三、LDA算法代码实现

（一）python编程实现

1.引入相关库

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

#计算均值,要求输入数据为numpy的矩阵格式，行表示样本数，列表示特征    
def meanX(data):return np.mean(data, axis=0) #axis=0表示按照列来求均值，如果输入list,则axis=1

2.LDA算法实现

#计算类内离散度矩阵子项si
def compute_si(xi):n = xi.shape[0]ui = meanX(xi)si = 0for i in range(0, n):si = si + ( xi[i, :] - ui).T * (xi[i, :] - ui )   return si#计算类间离散度矩阵Sb
def compute_Sb(x1, x2):dataX=np.vstack((x1,x2))#合并样本   print ("dataX:", dataX)#计算均值u1=meanX(x1)u2=meanX(x2)    u=meanX(dataX) #所有样本的均值Sb = (u-u1).T * (u-u1) + (u-u2).T * (u-u2)return Sbdef LDA(x1, x2):#计算类内离散度矩阵Sws1 = compute_si(x1)s2 = compute_si(x2)     #Sw=(n1*s1+n2*s2)/(n1+n2)Sw = s1 + s2#计算类间离散度矩阵Sb#Sb=(n1*(m-m1).T*(m-m1)+n2*(m-m2).T*(m-m2))/(n1+n2)Sb = compute_Sb(x1, x2)#求最大特征值对应的特征向量    eig_value, vec = np.linalg.eig(np.mat(Sw).I*Sb)#特征值和特征向量index_vec = np.argsort(-eig_value)#对eig_value从大到小排序，返回索引eig_index = index_vec[:1] #取出最大的特征值的索引w = vec[:, eig_index] #取出最大的特征值对应的特征向量return w

3.构造数据集

def createDataSet():  X1 = np.mat(np.random.random((8, 2)) * 5 + 15)  #类别AX2 = np.mat(np.random.random((8, 2)) * 5 + 2)   #类别Breturn X1, X2  x1, x2 = createDataSet()print(x1,x2)

4.LDA训练

w = LDA(x1, x2)
print("w:",w)

# 编写一个绘图函数
def plotFig(group):  fig = plt.figure()  plt.ylim(0, 30)  plt.xlim(0, 30)  ax = fig.add_subplot(111)  ax.scatter(group[0,:].tolist(), group[1,:].tolist())  plt.show()  

#绘制图形
plotFig(np.hstack((x1.T, x2.T)))  

5.）实例测试

test2 = np.mat([2, 8]) 
g = np.dot(w.T, test2.T - 0.5 * (meanX(x1)-meanX(x2)).T)  
print("Output: ", g  )

（二）sklearn 库实现

#coding=utf-8import pandas as pd
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn import datasets
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
import numpy as npdef main():iris = datasets.load_iris() #典型分类数据模型#这里我们数据统一用pandas处理data = pd.DataFrame(iris.data, columns=iris.feature_names)data['class'] = iris.target#这里只取两类
#     data = data[data['class']!=2]#为了可视化方便，这里取两个属性为例X = data[data.columns.drop('class')]Y = data['class']#划分数据集X_train, X_test, Y_train, Y_test =train_test_split(X, Y)lda = LinearDiscriminantAnalysis(n_components=2)lda.fit(X_train, Y_train)#显示训练结果print lda.means_ #中心点print lda.score(X_test, Y_test) #score是指分类的正确率print lda.scalings_ #score是指分类的正确率X_2d = lda.transform(X) #现在已经降到二维X_2d=np.dot(X-lda.xbar_,lda.scalings_)#对于二维数据，我们做个可视化#区域划分lda.fit(X_2d,Y)h = 0.02x_min, x_max = X_2d[:, 0].min() - 1, X_2d[:, 0].max() + 1y_min, y_max = X_2d[:, 1].min() - 1, X_2d[:, 1].max() + 1xx, yy = np.meshgrid(np.arange(x_min, x_max, h),np.arange(y_min, y_max, h))Z = lda.predict(np.c_[xx.ravel(), yy.ravel()])Z = Z.reshape(xx.shape)plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)#做出原来的散点图class1_x = X_2d[Y==0,0]class1_y = X_2d[Y==0,1]l1 = plt.scatter(class1_x,class1_y,color='b',label=iris.target_names[0])class1_x = X_2d[Y==1,0]class1_y = X_2d[Y==1,1]l2 = plt.scatter(class1_x,class1_y,color='y',label=iris.target_names[1])class1_x = X_2d[Y==2,0]class1_y = X_2d[Y==2,1]l3 = plt.scatter(class1_x,class1_y,color='r',label=iris.target_names[2])plt.legend(handles = [l1, l2, l3], loc = 'best')plt.grid(True)plt.show()if __name__ == '__main__':main()

四、月亮数据集算法可视化

（一）使用线性LDA对月亮数据集聚类

#基于线性LDA算法对月亮数据集进行分类
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from mpl_toolkits.mplot3d import Axes3D
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)mju1 = np.mean(X1, axis=0)#求中心点mju2 = np.mean(X2, axis=0)cov1 = np.dot((X1 - mju1).T, (X1 - mju1))cov2 = np.dot((X2 - mju2).T, (X2 - mju2))Sw = cov1 + cov2w = np.dot(np.mat(Sw).I,(mju1 - mju2).reshape((len(mju1),1)))# 计算wX1_new = func(X1, w)X2_new = func(X2, w)y1_new = [1 for i in range(len1)]y2_new = [2 for i in range(len2)]return X1_new, X2_new, y1_new, y2_new
def func(x, w):return np.dot((x), w)
if '__main__' == __name__:X, y = make_moons(n_samples=100, noise=0.15, random_state=42)X1_new, X2_new, y1_new, y2_new = LDA(X, y)plt.scatter(X[:, 0], X[:, 1], marker='o', c=y)plt.show()

（二）使用k-means对鸢尾花数据集聚类

# -*- coding:utf-8 -*-
from sklearn.datasets import make_moons
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans# 导入月亮型数据(证明kmean不能很好对其进行聚类)
X,y = make_moons(n_samples=200,random_state=0,noise=0.05)
print(X.shape)
print(y.shape)
plt.scatter(X[:,0],X[:,1])
kmeans = KMeans(n_clusters=2)
kmeans.fit(X)
y_pred = kmeans.predict(X)
cluster_center = kmeans.cluster_centers_
plt.scatter(X[:,0],X[:,1],c=y_pred)
plt.scatter(cluster_center[:,0],cluster_center[:,1],marker='^',linewidth=4)
plt.show()

（三）使用SVM对月亮数据集聚类

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm
from sklearn.datasets import make_moons# 导入数据集
X,y = make_moons(n_samples=200,random_state=0,noise=0.05)h = .02  # 网格中的步长# 创建支持向量机实例，并拟合出数据
C = 1.0  # SVM正则化参数
svc = svm.SVC(kernel='linear', C=C).fit(X, y) # 线性核
rbf_svc = svm.SVC(kernel='rbf', gamma=0.7, C=C).fit(X, y) # 径向基核
poly_svc = svm.SVC(kernel='poly', degree=3, C=C).fit(X, y) # 多项式核
lin_svc = svm.LinearSVC(C=C).fit(X, y) #线性核# 创建网格，以绘制图像
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),np.arange(y_min, y_max, h))# 图的标题
titles = ['SVC with linear kernel','LinearSVC (linear kernel)','SVC with RBF kernel','SVC with polynomial (degree 3) kernel']for i, clf in enumerate((svc, lin_svc, rbf_svc, poly_svc)):# 绘出决策边界，不同的区域分配不同的颜色plt.subplot(2, 2, i + 1) # 创建一个2行2列的图，并以第i个图为当前图plt.subplots_adjust(wspace=0.4, hspace=0.4) # 设置子图间隔Z = clf.predict(np.c_[xx.ravel(), yy.ravel()]) #将xx和yy中的元素组成一对对坐标，作为支持向量机的输入，返回一个array# 把分类结果绘制出来Z = Z.reshape(xx.shape) #(220, 280)plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8) #使用等高线的函数将不同的区域绘制出来# 将训练数据以离散点的形式绘制出来plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired)plt.xlabel('Sepal length')plt.ylabel('Sepal width')plt.xlim(xx.min(), xx.max())plt.ylim(yy.min(), yy.max())plt.xticks(())plt.yticks(())plt.title(titles[i])plt.show()

四、总结

本次实验了解了LDA算法的思想和优缺点。SVM算法的原理优缺点，以及两类算法的代码实现过程。LDA算法的核心是对数据集进行分类降维；而SVM是找到几何间距，找到几何间距margin，处理线性可分问题，对应的非线性问题处理方法是：非线性VM。

五、参考资料

知乎/线性判别分析LDA原理及推导过程（非常详细）-<陈楠>
知乎/【机器学习】支持向量机 SVM（非常详细）-<阿泽>
知乎/支持向量机（SVM）——原理篇-<野风>
线性判别分析（LDA）基本原理及实现
sklearn LDA降维算法
对鸢尾花数据集和月亮数据集，分别采用线性LDA、k-means和SVM算法进行二分类可视化分析