浅谈特征工程之降维

      在数据挖掘中，数据通常被表示为向量的形式进行训练，训练时常常会消耗大量资源和时间，会面临维数灾难的情况，同时过多的特征可能会导致泛化误差过大，导致过拟合。因此进行降维，用一个低维度的向量表示原始高维空间的特征就很重要，本文会介绍三种降维算法，分别是主成分分析法(PCA)、线性判别分析(LDA)、非负矩阵分解(NMF)。 （本文使用т作为矩阵或向量的转置，V  方差、X 矩阵、x 向量、〤投影后向量、ω  超平面、协方差矩阵C = XXт、 ∑n 从1到n累加、 ∝ 正比于 、^乘方 、dx微分、∂偏导、║║距离、s.t. 约束条件）

1. 主成分分析 PCA

      PCA是一种无监督降维算法，用来找到数据的主成分，并用这些主成分来表达数据，即减少特征的数量，同时又能表达原始数据的大部分有效信息。从而达到降维的目的。从方差的角度出发，数据的方差越大，数据携带越多的信息。我们期望的结果是存在一个低维空间(超平面)，能够从原始空间到超平面的投影点的方差最大，即最大投影方差。同时样本点到超平面的距离足够小，即最小重构距离。

     1. 从最大投影方差出发求解PCA. 我们需要找到一个投影面是投影方法最大.

     首先对原始数据x进行中心化处理，均值为ū，这样投影之后的均值也为零，

     假设投影方向为ω， 投影后的方差可以表示为 

   V  = 1/N * ∑((x-ū)тω)^2

         = ωт(∑1/N(x-ū)(x-ū)т)ω

      其中括号内的值即为原始样本的协方差矩阵记做 C

     V  = ωтCω   s.t. ωт ω = I 求V的最大值

      对于上式中的有约束条件的凸优化问题求解，有约束条件的最优化问题，即可引入拉格朗日乘子法

      L(ω ,λ) = ωтCω + λ(1-ωт ω)

      对L函数ω 求偏导，  得到 2Cω - 2λω = 0

      Cw = λw

      求出的λi即为协方差矩阵C的特征值，wi即为λi对应的特征向量，

      对协方差矩阵进行特征值分解，取前k大的特征值λ1-λk，以及特征值对应的特征向量w1-wk，这样就将n维特征降至k维。如何选择k的值，你可以选择一个降维后的信息占比来确定k值。ŋ <= ∑kλ₁ / ∑nλ₁ 

       2. 从最小重构距离求解PCA

       即原始数据点到超平面距离最小，x为原始样本点，〤为投影后的投影向量，

       距离d = ║xk - 〤k║^2 =  Σ(xxт -2 xт〤 + 〤тx)  ∝ -Σwтxxтw + xтx = -tr(ωтxxт ω) + xтx  其中xтx为常数，对结果不影响，可去掉。

       最小重构距离即是求解 argminΣ║xk - 〤k║ ∝ Σ -tr(ωтxx тω)  ∝  argmax(ωтXXтω)  s.t. ωт ω = I  使用拉格朗日乘子法求解

       从最小重构距离出发得出的结果和从最大投影距离的最终基本一样，PCA可以减少特征并减少其相关性，去除噪声。

2. 线性判别分析LDA

      线性判别分析是一种有监督降维算法，对于一些有类别的数据，使用PCA通常只能得到方差最大的投影，投影之后无法将类别分开，往往降维效果不佳，

使用LDA能够使降维后保留类别信息，我们需要找到一个超平面ω，使得投影之后的类间距离尽可能大，类内距离尽可能小，

如图，即找出一个超平面，能够使类间方差最大化，类内方差最小化。

针对2个类别的LDA求解如下

假设样本数量分别为N1 和N2，首先求样本x₁ x₂投影后为z₁ z₂，z= ωтx， 投影后的向量的均值ū₁，ū₂，

样本1的投影后的方差为 V ₁ = 1/N1*∑((z₁-ū₁)тω)∧2 = ωтC₁ω， 参照PCA中的解法，C₁ 为 样本类1的协方差矩阵

样本2的投影后的方差为 V 2 = 1/N2*∑((z₂-ū₂)тω)∧2 = ωтC₂ω， 参照PCA中的解法，C₂ 为 样本类2的协方差矩阵

用方法表示的最小类内距离即为 argmin(V ₁ + V ₂ ) = argmin(ωт(C₁ + C₂)ω)

最大类间距离数学表示为：

D = (ū₁-ū₂)^2 = (1/N1*∑ωтx₁ - 1/N2*∑ωтx₂)^2 = ωт (ū₁-ū₂) (ū₁-ū₂)тω

我们将最大类间距离初一最小类内距离相处来得到损失函数，

J = argmax (D  / (V ₁ + V ₂ ) ) =  argmax ((ū₁-ū₂)^2 / (ωт(C₁ + C₂)ω)) = argmax(ωт (ū₁-ū₂) (ū₁-ū₂)тω / ωт(C₁ + C₂)ω)

对J的w求偏导∂J/∂w = (∂ωт(C₁ + C₂)ω/∂ω *ωт(ū₁-ū₂) (ū₁-ū₂)тω ) - ∂ωт(ū₁-ū₂) (ū₁-ū₂)ω/∂ω *ωт(C₁ + C₂)ω)/ (ωт(C₁ + C₂)ω)^2 =0

=>(C₁ + C₂)ωωт (ū₁-ū₂) (ū₁-ū₂)тω = ωт(C₁ + C₂)ω(ū₁-ū₂) (ū₁-ū₂)тω => w  ∝ ((ū₁-ū₂) (ū₁-ū₂)т)-¹(C₁ + C₂)ω 

令 λ = J =》 (C₁ + C₂)ω =λ (ū₁-ū₂) (ū₁-ū₂)тω  =>  ((ū₁-ū₂) (ū₁-ū₂)т)-¹(C₁ + C₂)ω = λω 

 可以看出降维问题变成一个矩阵特征值特征向量的问题，((ū₁-ū₂) (ū₁-ū₂)т)-¹(C₁ + C₂)求解特征值，投影方向即是特征值对应的特征向量。和PCA一样，通过设定的信息占比来确定你要取得前k个特征值和特征向量

3. 非负矩阵分解 NMF

    对于一个非负矩阵V，NMF都可以找到一个非负矩阵W和一个非负矩阵H，使得V=WH，即Vm*n ≈ Wm*rHr*n, H 称为基矩阵，W称为系数矩阵，其中r〈〈 n, r 〈〈 m, NMF可以对原始矩阵的维数进行降维，同时可以对数据进行压缩。原矩阵V中的一列向量可以解释为对左矩阵W中所有列向量的加权和，而权重系数为右矩阵H中对应列向量中的元素。

    NMF可用欧式距离作为损失函数可以写为 J(W, H) = argmin(║V-WH║^2)  s.t. W,H≥0，对于噪声符合高斯分布的情况，使用梯度下降方法迭代求解。其中(WH)ij = ∑WikHkj,分别对W、H求偏导，

∂J/∂Wik = (VHт)ik - (WHHт)ik  ∂J/∂Hkj = (WтV)kj - (WтWH)kj

迭代：Wik = Wik* (VHт)ik/(WHHт)ik  Hkj = Hkj*(WтV)kj/(WтWH)kj  直至收敛。

4. 如何在sk-learn中使用

    上文中讲述了PCA、LDA、NMF的原理，不熟悉数学的同学可能看着有些困难，那如何在sk-learn中使用这三个算法呢，很简单，这三个算法都有在sk-learn提供实现，sk-learn三步走，1.实例化模型、传入需要的参数。 2.通过模型接口训练模型。3. 通过模型接口提取需要的信息。PCA和NMF在decomposition包下，LDA在discriminant_analysis包下。下面以PCA和NMF为例做个示范。

from sklearn.decomposition import PCA
from sklearn import datasets
# 使用鸢尾花数据集
iris = datasets.load_iris()
x = iris.data
y = iris.target

# PCA
# 1 实例化
pca = PCA(n_components=2  # 降維后的維度 也可以传入浮点数按信息占比降维, 其他参数如scd_solver可指定矩阵分解方式
          )
# 2 训练模型 并获得新矩阵
pca = pca.fit(x)
# 获得新矩阵
x = pca.transform(x)

# NMF
import numpy as np
X = np.array([[1, 1], [2, 1], [3, 1.2], [4, 1], [5, 0.8], [6, 1]])
from sklearn.decomposition import NMF
model = NMF(n_components=2, init='random', random_state=0)
W = model.fit_transform(X)
H = model.components_
X_new = np.array([[1, 0], [1, 6.1], [1, 0], [1, 4], [3.2, 1], [0, 4]])
W_new = model.transform(X_new)

5. 后记

     数据挖掘系列下一期会推出从决策树到GBDT。大数据时代，你会拥有大量数据，如何让你的算法运行的更快更好，所以来华为云 DLI 服务，这里会为你提供AI on spark AND AI on flink 最强算力。

参考：

     机器学习-周志华

     机器学习白板推导系列-shuhuai

     https://scikit-learn.org/stable/index.html