本文内容参考了机器学习实战: 基于Scikit-Learn和Tensorflow一书。

维度的诅咒

在高维空间中,许多事物的行为都迥然不同。例如, 如果你在一个单位平面(1×1的正方形)内随机选择一个点,那么这 个点离边界的距离小于0.001的概率只有约0.4%(也就是说,一个随 机的点不大可能刚好位于某个维度的“极端”)。但是,在一个10000 维的单位超立方体(1×1…×1立方体,一万个1)中,这个概率大于 99.999999%。高维超立方体中大多数点都非常接近边界

还有一个区别:如果你在单位平面中随机挑两个点,这 两个点之间的平均距离大约为0.52。如果在三维的单位立方体中随机 挑两个点,两点之间的平均距离大约为0.66。但是,如果在一个100 万维的超立方体中随机挑两个点呢?不管你相信与否,平均距离大约 为408.25(约等于100000/ 6的开平方)!这是非常违背直觉的:位于同一 个单位超立方体中的两个点,怎么可能距离如此之远?这个事实说明 高维数据集有很大可能是非常稀疏的:大多数训练实例可能彼此之间 相距很远。当然,这也意味着新的实例很可能远离任何一个训练实 例,导致预测跟低维度相比,更加不可靠,因为它们基于更大的推 测。简而言之,训练集的维度越高,过度拟合的风险就越大
理论上来说,通过增大训练集,使训练实例达到足够的密度,是 可以解开维度的诅咒的。然而不幸的是,实践中,要达到给定密度所 需要的训练实例数量随着维度增加呈指数式上升。。仅仅100个特征下 (远小于MNIST问题),要让所有训练实例(假设在所有维度上平 均分布)之间的平均距离小于0.1,你需要的训练实例数量就比可观 察宇宙中的原子数量还要多。

数据降维的主要方法

降维的两种具体方法:投影流形学习

投影

在大多数问题中,训练实例在所有维度上并不是均匀 分布的。许多特征几乎是不变的,也有许多特征是高度相关联的。因此,高维空间的所有训练实例实际 上(或近似于)受一个低得多的低维子空间所影响。如下图的高维(3D)空间的低维(2D)子空间。
投影到子空间:
不过投影并不总是降维的最佳方法。在许多情况下,子空间可能 会弯曲或转动,比如图8-4所示的著名的瑞士卷玩具数据集。
简单地进行平面投影(例如放弃x3)会直接将瑞士卷的不同层压 扁在一起,如图8-5的左图所示。但是你真正想要的是将整个瑞士卷 展开铺平以后的2D数据集,如图8-5的右图所示。
##### 流形学习
2D流形就是一个 能够在更高维空间里面弯曲和扭转的2D形状,如上面的图形所示。d维流形 就是n(其中,d<n)维空间的一部分,局部类似于一个d维超平面。瑞士卷的例子中,d=2,n=3,局部类似一个2D平面,在第三个维度上卷起。
流形学习:对训练实例进行流形建模,认为高维度的数据集存在一个低维度的流形表示。这是基于经验观察的,也称为流形假设。
流形假设还有一个隐含的假设:能用低维空间的流形表示,手头的任务将变得简单。但这个假设并不总是成立。简而言之,在训练模型之前降低训练集的维度,肯定可以加快训 练速度,但这并不总是会导致更好或更简单的解决方案,它取决于数 据集。

PCA

主成分分析(PCA)是迄今为止最流行的降维算法。它先是识别 出最接近数据的超平面,然后将数据投影其上。

保留差异性

选择保留最大差异性的轴看起来比较合理,因为它看起来可能比其他两种投影丢失的信息更少。要证明这一选择,可以比较原始数据集在其轴上的投影之间的俊峰距离,使这个军方距离最小的轴是理想选择。也即是PCA背后的简单思想。

主成分

主成分分析可以在训练集中识别出哪条轴对差异性贡献度最高。同时它也找出了第二条轴,它对剩余差异性的贡献度最高,与第一条轴垂直。轴的数量与数据集维度相同,它们之间是正交的
定义第i条轴的单位向量就叫作第i个主成分(PC)。图8-7中, 第一个主成分是c1,第二个主成分是c2。
主成分的方向是不稳定的:如果你稍微打乱训练集,然后重 新运行PCA,部分新的主成分可能指向跟原来的主成分相反的方向。 但是,它们通常还是在同一条轴上。。在某些情况下,两条主成分可能 会旋转甚至互换,但是它们定义的平面还是不变。
主成分矩阵:
使用奇异值分解(SVD):将训练集矩阵X分解为三个矩阵点积U·∑·VTV^T^是包含所有主成分的矩阵

X_centered = X - X.mean(axis=0)                # 数据集围绕原点集中
U, s, V = np.linalg.svd(X_centered)
c1 = V.T[:, 0]
c2 = V.T[:, 2]
低维度投影

确定所有主成分后,可以将数据集投影到由前d个主成分定义的超平面上,从而将数据集的维度降到d维。这个超平面的选择,能确保投影尽可能保留差异性。
将训练集投影到低维度:Wd是包含前d个主成分的矩阵,即由矩阵VT前d列组 成的矩阵。
X d p r o j = X W d {X_{d - proj}} = X \cdot {W_d} Xdproj=XWd
将训练集投影到前两个主成分定义的平面上。

W2 = V.T[:, :2]
 X2D = X_centered.dot(W2)
使用Scikit-Learn

Scikit-Learn的PCA类也使用SVD分解来实现主 成分分析。

from sklearn.decomposition import  PCA

pca=PCA(n_components=2)        # 数据降到二维,会自动处理数据集中
X2D=pca.fit_transform(X)
# 通过变量components_访问主成分(包含的主成分是水平向量)
pca.components_.T[:,0])。
方差解释率

通过变量explained_variance_ratio_获的每个主成分的方差解释率,它表示每个主成分轴对整个数据集的方差贡献度。

 print(pca.explained_variance_ratio_)
选择正确数量的维度

将靠 前的主成分方差解释率依次相加,直到得到足够大比例的方差(例如 95%),这时的维度数量就是很好的选择。

pca=PCA()
pca.fit(X)    # 不降维
cumsum=np.cumsum(pca.explained_variance_ratio_)
d=np.argmax(cumsum>=0.95)+1

设置n_components=d即可,

pca = PCA(n_components=0.95)                # 保留95%方差比
X_reduced = pca.fit_transform(X)

还可以将解释方差绘制成关于维度数量的函数(绘制 cumsum即可,见图8-8)。曲线通常都会有一个拐点,说明方差停止 快速增长。你可以将其视为数据集的本征维数

PCA压缩

降维之后训练集占用的空间要小得多。例如,对MNIST 数据集应用主成分分析,然后保留其方差的95%。你会发现,原来每 个实例的784个特征变得只有150多个特征。所以这保留了绝大部分差 异性的同时,数据集的大小变为不到原始的20%!
在PCA投影上运行投影的逆转换,也可以将缩小的数据集解压缩 回784维数据集。当然,你得到的并非原始的数据,因为投影时损失 了一部分信息(5%被丢弃的方差),但是它很大可能非常接近于原 始数据。原始数据和重建数据(压缩之后解压缩)之间的均方距离, 被称为重建误差。使用inverse_transform()方法。

pca = PCA(n_components = 154) 
X_mnist_reduced = pca.fit_transform(X_mnist) 
X_mnist_recovered = pca.inverse_transform(X_mnist_reduced)

PCA逆转换,回到原始维度
X r e c o v e r e d = X d p r o j W d T {{\rm{X}}_{re{\mathop{\rm cov}} ered}} = {X_{d{\rm{ - proj}}}}W_d^{\rm{T}} Xrecovered=XdprojWdT

增量PCA

增量主成分分析 (IPCA)算法:你可以将训练集分成一个个小批量,一次给IPCA算 法喂一个。

from sklearn.decomposition import  IncrementalPCA

n_batches=100
inc_pca=IncrementalPCA(n_components=154)
for X_batch in np.array_split(X_train,n_batches):
    inc_pca.partial_fit(X_batch)

X_reduced=inc_pca.transform(X_train)

你也可以使用NumPy的memmap类,它允许你巧妙地操控 一个存储在磁盘二进制文件里的大型数组,就好似它也完全在内存里 一样,而这个类(memmap)仅在需要时加载内存中需要的数据。

X_mm=(filename,dtype="float32",mode="readonly",shape=(m,n))
batch_size=m//n_batches
inc_pca=IncrementalPCA(n_components=154,batch_size=batch_size)
inc_pca.fit(X_mm)
随机PCA

这 是一个随机算法,可以快速找到前d个主成分的近似值。它的计算复 杂度是O(m×d2)+O(d3),而不是O(m×n2)+O(n3),所以当d 远小于n时,它比前面提到的算法要快得多。

rnd_pca=PCA(n_components=154,svd_solver="randomized")
X_reduced=rnd_pca.fit(X_train)

核主成分分析

核主成分分析使复杂的非线性投影降维成为可能,它擅长在投影后保留实例的集群,有时 甚至也能展开近似于一个扭曲流形的数据集。

from sklearn.decomposition import KernelPCA

rbf_pca = KernelPCA(n_components=2, kernel='rbf', gamma=0.04)
X_Reduced = rbf_pca.fit_transform(X)

图8-10显示了使用不同核函数降到二维的瑞士卷,包括线性核函 数(相当于直接使用PCA类)、RBF核函数,以及sigmoid核函数 (Logistic)。

选择核函数和调整超参数

由于kPCA是一种无监督的学习算法,因此没有明显的性能指标 来帮你选择最佳的核函数和超参数值。而降维通常是监督式学习任务 (例如分类)的准备步骤,所以可以使用网格搜索,来找到使任务性 能最佳的核和超参数。

from sklearn.model_selection import GridSearchCV
from sklearn.linear_model import LogisticRegression
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ('kpca', KernelPCA(n_components=2)),
    ('log_reg', LogisticRegression())
])

param_grid = [{
    'kpca__gamma': np.linspace(0.03, 0.05, 10),
    'kpca__kernel': ['rbf', 'sigmoid']
}]

grid_search = GridSearchCV(clf, param_grid, cv=3)
grid_search.fit(X, y)
print(grid_search.best_params_)

还有一种完全不受监督方法,就是选择重建误差最低的核和超参 数。但是这个重建不像线性PCA重建那样容易。如 果我们对一个已经降维的实例进行线性PCA逆转换,重建的点将存在 于特征空间,而不是原始空间中(例如,图中x表示的那个点)。而 这里特征空间是无限维度的,所以我们无法计算出重建点,因此也无 法计算出真实的重建误差。幸好,我们可以在原始空间中找到一个 点,使其映射接近于重建点。这被称为重建原像。一旦有了这个原像,你就可以测量它到原始实例的平方距离。最后,便可以选择使这 个重建原像误差最小化的核和超参数。要执行重建,训练一个监督式回归模型, 以投影后的实例作为训练集,并以原始实例作为目标。

rbf_pca = KernelPCA(n_components = 2, kernel="rbf", gamma=0.0433,fit_inverse_transform=True)                
X_reduced = rbf_pca.fit_transform(X)
 X_preimage = rbf_pca.inverse_transform(X_reduced)

默认情况下为fit_inverse_transform=False,并且KernelPCA没有inverse_transform()方法。只有在设fit_inverse_transform=True时才会创建该方法。

from sklearn.metrics import mean_squared_error
 mean_squared_error(X, X_preimage) 

局部线性嵌入

局部线性嵌入(LLE)是另一种非常强 大的非线性降维(NLDR)技术。不像之前的算法依赖于投影,它是 一种流形学习技术。简单来说,LLE首先测量每个算法如何与其最近 的邻居(c.n.)线性相关,然后为训练集寻找一个能最大程度保留这 些局部关系的低维表示。这使得它特别擅长展开弯 曲的流形,特别是没有太多噪声时。
如,对瑞士卷展开,瑞士 卷完全展开,实例之间的距离局部保存得很好。不过从整体来看,距 离保存得不够好:展开的瑞士卷右侧被挤压,而左侧被拉长。

from sklearn.manifold import LocallyLinearEmbedding

lle = LocallyLinearEmbedding(n_components=2, n_neighbors=10)
X_reduced = lle.fit_transform(X)

LLE第一步:对局部关系线性建模
第二步就是要将训练实例映射到一 个d维空间(d<n),同时尽可能保留这些局部关系。
LLE第二步:保留关系并降维
Z(i)是X^(i)在d维空间的映像。
Scikit-Learn的LLE实现,计算复杂度如下:寻找k个最近邻为 O(m log(m)n log(k));优化权重为O(mnk3);构建低维表 示,为O(dm2)。

其他降维技巧

  • 多维缩放(MDS)算法,保持实例之间的距离,降低维度(见 图8-13)。
  • 等度量映射(Isomap)算法,将每个实例与其最近的邻居连接 起来,创建连接图形,然后保留实例之间的这个测地距离,降低维 度。
  • t-分布随机近邻嵌入(t-SNE)算法在降低维度时,试图让相似 的实例彼此靠近,不相似的实例彼此远离。它主要用于可视化,尤其 是将高维空间中的实例集群可视化(例如,对MNIST图像进行二维 可视化)。
  • 线性判别(LDA)实际上是一种分类算法,但是在训练过程 中,它会学习类别之间最有区别的轴,而这个轴正好可以用来定义投 影数据的超平面。这样做的好处在于投影上的类别之间会尽可能的分 开,所以在运行其他分类算法——比如SVM分类器之前,LDA是一 个不错的降维手段。