机器学习 学习笔记（15） 低维嵌入 主成分分析

低维嵌入

在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为维数灾难。

缓解维数灾难的一个重要途径是降维，亦称为维数约简，即通过某种数学变换将原始高维属性空间转变为一个低维子空间。在这个子空间中样本密度大幅提高，距离计算也更为容易。

若要求原始空间中样本之间的距离在低维空间中得以保持，即多维缩放（Multiple Dimensional Scaling,MDS）。

假定m个样本在原始空间的距离矩阵为

D \in R^{m \times m}

，其第i行j列的元素

dist_{ij}

为样本

x_i

到

x_j

的距离。我们的目标是获得样本在

d'

维空间的表示

Z \in R^{d' \times m}

，

d'\ll d

，且任意两个样本在

d'

维空间中的欧式距离等于原始空间中的距离，即

||z_i-z_j||=dist_{ij}

。

令

B=Z^TZ \in R^{m \times m}

，其中B为降维后的样本内积矩阵，

b_{ij}=z^T_iz_j

，有

dist^2_{ij}=||z_i||^2+||z_j||^2-2z^t_iz_j=b_{ii}+b_{jj}-2b_{ij}

令降维后的样本Z被中心化，即

\sum_{i=1}^m z_i=0

，显然，矩阵B的行与列之和均为0，即

\sum_{i=1}^m b_{ij}=\sum_{j=1}^m b_{ij}=0

，则：

\sum_{i=1}^m dist^2_{ij}=tr(B)+mb_{jj}

\sum_{j=1}^m dist^2_{ij}=tr(B)+mb_{ii}

\sum_{i=1}^m \sum_{j=1}^m dist^2_{ij}=2m tr(B)

其中

tr(\cdot )

表示矩阵的迹，

tr(B)=\sum_{i=1}^m||z_i||^2

，令：

dist^2_{i\cdot }=\frac{1}{m} \sum_{j=1}^m dist^2_{ij}

dist^2_{\cdot j}=\frac{1}{m} \sum_{i=1}^m dist^2_{ij}

dist^2_{\cdot \cdot }=\frac{1}{m^2} \sum_{i=1}^m \sum_{j=1}^m dist^2_{ij}

则

b_{ij}=-\frac{1}{2}(dist^2_{ij}-dist^2_{i\cdot }-dist^2_{\cdot j}+dist^2_{\cdot \cdot })

由此可以通过降维前后保持不变的距离矩阵D求取内积矩阵B.

对矩阵B做特征值分解，

B=V\Lambda V^T

，其中

\Lambda=diag(\lambda _1,\lambda _2,...,\lambda _d)

为特征值构成的对角矩阵，

\lambda _1\geqslant \lambda _2\geqslant ...\geqslant \lambda _d

，V为特征向量矩阵，假定其中有

d^*

个非零特征值，它们构成对角矩阵

\Lambda _*=diag(\lambda _1,\lambda _2,...,\lambda _{d^*})

，令

V_*

表示相应的特征向量矩阵，则Z可以表达为：

Z=\Lambda ^{1/2}_*V^T_* \in R^{d^* \times m}

MDS算法描述：

输入：距离矩阵

D \in R^{m \times m}

，其元素

dist_{ij}

为样本

x_i

到

x_j

的距离。低维空间维数

d'

过程：根据

dist^2_{i\cdot }=\frac{1}{m} \sum_{j=1}^m dist^2_{ij}

，

dist^2_{\cdot j}=\frac{1}{m} \sum_{i=1}^m dist^2_{ij}

，

dist^2_{\cdot \cdot }=\frac{1}{m^2} \sum_{i=1}^m \sum_{j=1}^m dist^2_{ij}

分别计算出

dist^2_{i\cdot }

，

dist^2_{\cdot j}

，

dist^2_{\cdot \cdot }

           根据

b_{ij}=-\frac{1}{2}(dist^2_{ij}-dist^2_{i\cdot }-dist^2_{\cdot j}+dist^2_{\cdot \cdot })

计算矩阵B

           对矩阵B做特征值分解

           取

\tilde{\Lambda }

为

d'

个最大特征值所构成的对角矩阵，

\tilde{V}

为相应的特征向量矩阵

输出：

\tilde{V}\tilde{\Lambda }^{1/2} \in R^{m \times d'}

，每行是一个样本的低维坐标

一般来说，想要获得低维子空间，最简单的是对原始高维空间进行线性变换。基于线性变换来进行降维的方法称为线性降维方法。

主成分分析

主成分分析（Principal Component Analysis，简称PCA）是最常用的一种降维方法。

对于正交属性空间中的样本点，如何用一个超平面（直线的高维推广）对所有的样本进行恰当的表达？应该具有两个性质：

• 最近重构性：样本点到这个超平面的距离足够近
• 最大可分性：样本点在这个超平面上的投影能尽可能分开

PCA算法描述：

输入：样本集

D=\{x_1,x_2,...,x_m\}

，低维样本空间数

过程：对所有样本进行中心化：

x_i=x_i-\frac{1}{m}\sum_{i=1}^mx_i

           计算样本的协方差矩阵

XX^T

           对协方差矩阵

XX^T

做特征值分解

           取最大的

d'

个特征值所对应的特征向量

w_1,w_2,...,w_{d'}

输出：投影矩阵

W^*=(w_1,w_2,...,w_{d'})

PCA仅需保留

W^*

与样本的均值向量即可通过简单的向量减法和矩阵-向量乘法将新样本投影至低维空间中。显然，低维空间与原始高维空间必有不同，因为对应于最小的

d-d'

个特征值的特征向量被舍弃了，这是降维导致的结果，但是舍弃这部分信息往往是必要的：一方面，舍弃这部分信息之后能使样本的采样密度增大，这正是降维的重要动机；另一方面，当数据收到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，将它们舍弃能在一定程度上起到去燥的效果。

# 代码来自于机器学习实战
# 2个参数：一个参数是用于进行PCA操作的数据集，第二个参数是可选参数，即应用N个特征
# 首先计算并减去原始数据集的平均值，然后计算协方差矩阵及其特征值
# 然后利用argsort函数对特征值进行从小到大排序
# 根据特征值排序的逆序就可以得到最大的N个向量
# 这些向量将构成后面对数据进行转换的矩阵
# 该矩阵则利用N个特征将原始数据转换到新空间中
# 最后原始数据被重构后返回
# 同时，降维之后的数据集也被返回
def pca(dataMat,topNfeat=9999999):
    meanVals=mean(dataMat,axis=0)
    meanRemoved=dataMat-meanVals # 去除平均值
    covMat=cov(meanRemoved,rowvar=0)
    eigVals,eigVects=linalg.eig(mat(covMat))
    eigValInd=argsort(eigVals)
    # 从大到小对N个值排序
    eigValInd=eigValInd[:-(topNfeat+1):-1]
    redEigVects=eigVects[:,eigValInd]
    # 将数据转换到新空间
    lowDDataMat=meanRemoved*redEigVects
    reconMat=(lowDDataMat*redEigVects.T)+meanVals
    return lowDDataMat,reconMat

非线性降维的一种常用方法就是基于核技巧对线性降维方法进行核化

参考：

1. 《机器学习》
2. 《机器学习实战》