数据降维

发表于
字数统计: 2.2k | 阅读时长 ≈ 9

嵌套（Embedding）

通常，嵌套是指将高维度向量映射到低维度空间。

例如，您可以采用以下两种方式之一来表示英文句子中的单词。

  • 表示成包含百万个元素（高维度）的稀疏向量，其中所有元素都为整数。向量中的每个单元格都表示一个单独的英文单词，单元格中的值表示相应单词在句子中出现的次数。由于单个英文句子包含的单词不太可能超过 50 个，因此向量中几乎每个单元格都包含 0。少数非 0 的单元格中将包含一个非常小的整数（通常为 1），该整数表示相应单词在句子中出现的次数。
  • 表示成包含数百个元素（低维度）的密集向量，其中每个元素都包含一个介于0到1之间的浮点值。

    嵌套本质上是降维度，化稀疏为密集。

k-近邻（k-nearest neighbor, k-NN）

懒惰学习（lazy learning）

训练时间开销为0，待收到测试样本后再进行处理。相应的，那些在训练阶段就对样本进行学习处理的方法，称为“急切学习”(eager learning)

算法原理

给定测试样本，基于某种距离度量找出训练集与其最靠近的k个训练样本，基于k个“邻居”的信息进行预测。通常，在分类任务中可使用投票法，在回归任务中使用平均法。

维数灾难（curse of dimensionality）

k-近邻基于一条重要假设，即任何测试样本 $x$ 的附近任意小的 $\delta$ 距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为 “密度采样”(dense sample)。

假设属性维度为20，若要求样本满足迷采样条件（ $\delta$ = 0.001），则至少需要 $(10^{3})^{20}=10^{60}$ 个样本。除外，当维度很高时，距离计算、内积计算都不再容易。

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

多维缩放（Multople Dimensional Scaling，MDS）

假设 $m$ 个样本在原始空间的距离矩阵为 $\mathbf{D} \in R^{m \times m}$ ，其第 $i$ 行 $j$ 列的元素 $dist{ij}$ 为样本 $x{i}$ 到 $x{j}$ 的距离。我们的目标是获得样本在 $d^{\prime}$ 维空间的表示 $\mathbf{Z} \in R^{d^{\prime} \times m}$ ， $d^{\prime} \leq d$ ，且任意两个样本在 $d^{\prime}$ 维空间的欧式距离等于原始空间中的距离，即 $\vert| z{i} - z{j} \vert| = dist{ij}$ 。

令 $\mathbf{B} =\mathbf{Z}^\mathrm{T}\mathbf{Z} \in R^{m \times m}$ ，其中 $\mathbf{B}$ 为降维后样本的内积矩阵， $b{ij} = z{i}^\mathrm{T}z_{j}$ ，有

若给定距离矩阵 $\mathbf{D}$ ，为实对陈矩阵，若不加任何条件约束，不可能得到矩阵 $\mathbf{B}$ ，因为整体移动平移和旋转样点是不改变样点间距离的，即我们可以得到无数个满足要求的矩阵 $\mathbf{B}$ 。

为了便于讨论，令降维后的样本 $\mathbf{Z}$ 被中心化，即 $\sum{i=1}^{m}z{i} = 0$ 。显然，矩阵 $\mathbf{B}$ 的行与列之和均为零，即

易知

其中 $tr(\cdot)$ 表示矩阵的迹（trace）， $tr(\mathbf{B})=\sum{i=1}^{m}||z{i}||^{2}$ 。令

由此可得

由此即可通过降维前后保持不变的距离矩阵 $\mathbf{D}$ 求取内积矩阵 $\mathbf{B}$ 。
对矩阵 $\mathbf{B}$ 做特征值分解（eigenvalue decomposition）， $\mathbf{B}=\mathbf{V}\mathbf{\Lambda}\mathbf{V}^\mathrm{T}$ ，其中 $\mathbf{\Lambda}=diag(\lambda{1},\lambda{2},…,\lambda{d})$ 为特征值构成的对角矩阵， $\lambda{1} \geq \lambda{2} \geq … \geq \lambda{d}$ ， $\mathbf{V}$ 为特征向量矩阵，假定其中有 $d^{\ast}$ 个非零特征值，他们构成对角矩阵 $\mathbf{\Lambda}{\ast}=diag(\lambda{1},\lambda{2},…,\lambda{d^{\ast}})$ ，令 $\mathbf{V}_{\ast}$ 表示相应的特征向量矩阵，则 $\mathbf{Z}$ 可表达为

在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必严格相等，此时可取$d^{\prime} \leq d$个最大特征值。

主成分分析（Principal Component Analysis, PCA）

如何利用超平面（直线的高维推广）对所有样本进行恰当的表达？

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

从最近重构性推导，假定数据样本进行了中心化，即 $\sum{i}x{i}=\mathbf{0}$ ，再假定投影变换后得到的新坐标系为 ${w{1},w{2},…,w{d}}$ ，其中 $w{i}$ 是标准正交基向量， $||w{i}||{2}=1$ , $w{i}^\mathrm{T}w{j}=0 (i \not= j)$ 。若丢弃新坐标系中的部分坐标，即将维度降低到 $d^{\prime} \le d$ ,则样本点 $x{i}$ 在低维坐标系中的投影是 $z{i}=(z{i1};z{i2};…;z{id^{\prime}})$ ，其中 $z{ij}=w{j}^\mathrm{T}x{i}$ 是 $x{i}$ 在低维坐标系下第 $j$ 维的坐标。若基于 $z{i}$ 来重构 $x{i}$ ，则会得到 $\hat x{i}=\sum{j=1}^{d^{\prime}}z{ij}w_{j}$ 。

原样本点 $x{i}$ 与基于投影重构的样本点 $\hat x{i}$ 之间的距离为

其中 $\mathbf{W}=(w{1},w{2},…,w{d})$。根据最近重构性，上式最小化，考虑到 $w{j}$ 是标准正交基， $\sum{i}x{i}x_{i}^\mathrm{T}$ 是协方差矩阵，有

这就是主成分分析的优化目标。

从最大可分性出发，样本点 $x{i}$ 在新空间中超平面上的投影是 $\mathbf{W}^\mathrm{T}x{i}$ ，若所有样本点的投影尽可能分开，则应该使投影后样本点的方差最大化。

投影后样本点的协方差矩阵是 $\sum{i}\mathbf{W}^\mathrm{T}x{i}x_{i}^\mathrm{T}\mathbf{W}$ ，于是优化目标可以写作为

对优化目标使用拉格朗日乘子法可得

于是，只需对协方差矩阵 $\mathbf{X}\mathbf{X}^\mathrm{T}$ 进行特征值分解，将求得的特征值排序： $\lambda{1} \geq \lambda{2} \geq …\geq \lambda{d}$ ，再取前 $d^{\prime}$ 个特征值对应的特征向量构成 $\mathbf{W}^{\ast}=(w{1},w{2},…,w{d^{\prime}})$ 。这就是主成分分析的解。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#-*- coding:utf-8 -*-

import numpy as np
from sklearn import datasets
import matplotlib.pyplot as plt
import matplotlib.cm as cmx
import matplotlib.colors as colors


class PCA():
    def calculate_covariance_matrix(self, X, Y=None):
        m = X.shape[0]
        X = X - np.mean(X, axis=0)
        Y = X if Y == None else Y - np.mean(Y, axis=0)
        # 这里为啥不直接return matmul(X.T, X)
        return 1/m*np.matmul(X.T, Y)

    def transform(self, X, n_components):
        covariance_matrix = self.calculate_covariance_matrix(X)

        # 计算特征值，特征向量
        eigenvalues, eigenvectors = np.linalg.eig(covariance_matrix)

        # 取n_components个最大的特征值
        idx = eigenvalues.argsort()[::-1]

        eigenvectors = eigenvectors[:, idx]
        eigenvectors = eigenvectors[:, :n_components]

        return np.matmul(X, eigenvectors)


def main():
    # load the dataset，手写字体数据集
    data = datasets.load_digits()
    X = data.data
    y = data.target

    X_trans = PCA().transform(X, 2)


    # 以下为绘图演示
    x1 = X_trans[:, 0]
    x2 = X_trans[:, 1]

    cmap = plt.get_cmap('viridis')
    colors = [cmap(i) for i in np.linspace(0, 1, len(np.unique(y)))]

    class_distr = []
    # Plot the different class distributions
    for i, l in enumerate(np.unique(y)):
        _x1 = x1[y == l]
        _x2 = x2[y == l]
        _y = y[y == l]
        class_distr.append(plt.scatter(_x1, _x2, color=colors[i]))

    # Add a legend
    plt.legend(class_distr, y, loc=1)

    # Axis labels
    plt.suptitle("PCA Dimensionality Reduction")
    plt.title("Digit Dataset")
    plt.xlabel('Principal Component 1')
    plt.ylabel('Principal Component 2')
    plt.show()


if __name__ == "__main__":
    main()

运行结果

采用手写字体数据集，每个元素64个特征，PCA降维为2个特征

可以看到，数据分类为两维后很直观地看出各类之间的差别。

参考资料

机器学习西瓜书

Github RRdmlearning/Machine-Learning-From-Scratch

Google机器学习速成课程

0%