0%

各类降维方法总结

发表于 分类于

在现实生活中很多机器学习问题有上千维，甚至上万维特征，这不仅影响了训练速度，通常还很难找到比较好的解。这样的问题成为维数灾难（curse of dimensionality）

幸运的是，理论上降低维度是可行的。比如 MNIST 数据集大部分的像素总是白的，因此可以去掉这些特征；相邻的像素之间是高度相关的，如果变为一个像素，相差也并不大。

需要注意：降低维度肯定会损失一些信息，这可能会让表现稍微变差。因此应该先在原维度训练一次，如果训练速度太慢再选择降维。虽然有时候降为能去除噪声和一些不必要的细节，但通常不会，主要是能加快训练速度。

降维除了能提高训练速度以外，还能用于数据可视化。把高维数据降到 2 维或 3 维，然后就能把特征在 2 维空间（3 维空间）表示出来，能直观地发现一些规则。

降维的方法主要为两种：projection 和 Manifold Learning。

1.1 投影（Projection）

在大多数的真实问题，训练样例都不是均匀分散在所有的维度，许多特征都是固定的，同时还有一些特征是强相关的。因此所有的训练样例实际上可以投影在高维空间中的低维子空间中，下面看一个例子。

可以看到 3 维空间中的训练样例其实都分布在同一个 2 维平面，因此我们能够将所有样例都投影在 2 维平面。对于更高维的空间可能能投影到低维的子空间中。

然而投影（projection）不总是降维最好的方法在，比如许多情况下，空间可以扭转，如著名的瑞士卷（Swiss roll）数据。

如果简单的使用投影（project）降维（例如通过压平第 3 维），那么会变成如下左图的样子，不同类别的样例都混在了一起，而我们的预想是变成右下图的形式。

1.2 流形学习（Manifold Learning）

瑞士卷（Swiss roll）是二维流形的例子。它可以在高维空间中弯曲。更一般地，一个 d 维流形在 n 维空间弯曲（其中 d ＜ n）。在瑞士卷的情况下，D ＝ 2 和 n ＝ 3。

基于流行数据进行建模的降维算法称为流形学习（Manifold Learning）。它假设大多数现实世界的高维数据集接近于一个低维流形。

流行假设通常隐含着另一个假设：通过流形在低维空间中表达，任务（例如分类或回归）应该变得简单。如下图第一行，Swiss roll 分为两类，在 3D 的空间看起来很复杂，但通过流行假设到 2D 就能变得简单。

但是这个假设并不总是能成立，比如下图第二行，决策线为 x=5，2D 的的决策线明显比 3D 的要复杂。因此在训练模型之前先降维能够加快训练速度，但是效果可能会又增有减，这取决于数据的形式。

下面介绍几种降维方法

原理：

PCA 是一个线性方法，由于 PCA 只是简单对输入数据进行变换，所以它既可以用在分类问题，也可以用在回归问题。非线性的情况可以使用核方法 kernelized PCA，但是由于 PCA 有良好的数学性质、发现转换后特征空间的速度、以及再原始和变换后特征间相互转换的能力，在降维或者说特征抽取时，它已经可以满足大部分情况。
给定原始空间，PCA 会找到一个到更低维度空间的线性映射。因为需要使所有样本的投影尽可能分开，则需要最大化投影点的方差。
它具有如下性质：

  1. 保留方差是最大的
  2. 最终的重构误差（从变换后回到原始情况）是最小的

PCA

图片来自：

http://markus.com/deep-learning-101/

保留最大方差：
   首先需要选择一个好的超平面。先看下图的例子，需要将 2D 降为 1D，选择不同的平面得到右图不一样的结果，第 1 个投影以后方差最大，第 3 个方差最小，选择最大方差的一个感觉上应该是比较合理的，因为这样能保留更多的信息。

另外一种判断的方式是：通过最小化原数据和投影后的数据之间的均方误差。

2.1 流程：

  1. 去除平均值（每个元素减去自己特征的平均值）
  2. 计算协方差矩阵

协方差. png

协方差介绍（摘自百度百科）：
协方差表示的是两个变量的总体的误差，这与只表示一个变量误差的方差不同。 如果两个变量的变化趋势一致，也就是说如果其中一个大于自身的期望值，另外一个也大于自身的期望值，那么两个变量之间的协方差就是正值。 如果两个变量的变化趋势相反，即其中一个大于自身的期望值，另外一个却小于自身的期望值，那么两个变量之间的协方差就是负值。

协方差可以理解判断成两条线的趋势是否一致，线 a 线 b，线 a 变大时线 b 也变大，线 a 变小是线 b 也变小，协方差则为正（可以理解成正相关）。协方差的值大小代表相关性的强弱。线 a 和自己的协方差即自己本身的方差。

两个特征的协方差计算例子：
Xi 1.1 1.9 3
Yi 5.0 10.4 14.6
E(X) = (1.1+1.9+3)/3=2
E(Y) = (5.0+10.4+14.6)/3=10
E(XY)=(1.1×5.0+1.9×10.4+3×14.6)/3=23.02
Cov(X,Y)=E(XY)-E(X)E(Y)=23.02-2×10=3.02

  1. 计算协方差矩阵的特征值和特征向量
    一个向量 v 是方阵 A 的特征向量，将一定可以表示成下面的形式：

特征分解. png

其中 A 为方阵，V 是特征向量，lambda 是特征值。
λ 为特征向量 v 对应的特征值。特征值分解是将一个矩阵分解为如下形式：

特征分解

Q 是这个矩阵 A 的特征向量组成的矩阵，Σ 是一个对角矩阵，每一个对角线元素就是一个特征值，里面的特征值是由大到小排列。

特征值表示的是这个特征到底有多重要，而特征向量表示这个特征是什么

  1. 将特征值从大到小排列
  2. 保留最上面的 N 个特征向量
  3. 将数据转换到上述 N 个特征向量构建的新的空间中

2.2 numpy 中实现 PCA（【机器学习实战】）：

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
import numpy as np

def loadDataSet(fileName, delim='\t'):
    fr = open(fileName)
    stringArr = [line.strip().split(delim) for line in fr.readlines()]
    datArr = [map(float,line) for line in stringArr]
    return mat(datArr)

def pca(dataMat, topNfeat=n):
    meanVals = np.mean(dataMat, axis=0)

    meanRemoved = dataMat - meanVals


    covMat = np.cov(meanRemoved, rowvar=0)


    eigVals,eigVects = np.linalg.eig(mat(covMat))




    eigValInd = np.argsort(eigVals)

    eigValInd = eigValInd[:-(topNfeat+1):-1]



    redEigVects = eigVects[:,eigValInd]

    lowDDataMat = meanRemoved * redEigVects

    reconMat = (lowDDataMat * redEigVects.T) + meanVals

    return lowDDataMat, reconMat

2.3 使用 sklearn 中的 PCA：

2.3.1. 参数说明：

n_components:
意义：PCA 算法中所要保留的主成分个数 n，也即保留下来的特征个数 n
类型：int 或者 string，缺省时默认为 None，所有成分被保留。

copy:
类型：bool，True 或者 False，默认为 True。意义：表示是否在运行算法时，将原始训练数据复制一份。若为 True，则运行 PCA 算法后，原始训练数据的值不会有任何改变，因为是在原始数据的副本上进行运算；若为 False，则运行 PCA 算法后，原始训练数据的值会改，因为是在原始数据上进行降维计算。

whiten:
类型：bool，默认为 False
意义：白化，使得每个特征具有相同的方差。就是对降维后的数据的每个特征进行归一化，一般不需要白化。

2.3.2.PCA 对象的属性

components ：返回具有最大方差的成分。
explained_variance：所保留的 n 个成分各自的方差
explainedvariance_ratio：返回 所保留的 n 个成分各自的方差百分比。
ncomponents：返回所保留的成分个数 n。
noise variance：噪声方差大小
mean_: 特征均值

2.3.3.PCA 对象的方法

fit(X,y=None)
fit() 是 scikit-learn 中通用的方法。因为 PCA 是无监督学习算法，此处 y 等于 None。

fit(X)，表示用数据 X 来训练 PCA 模型。

fit_transform(X)
用 X 来训练 PCA 模型，同时返回降维后的数据。

inverse_transform()
将降维后的数据转换成原始数据，X=pca.inverse_transform(newX)

transform(X)
将数据 X 转换成降维后的数据。

2.3.4. 使用

这里只挑几个比较重要的参数进行说明。

1
sklearn.decomposition.PCA(n_components=None, copy=True, whiten=False)
  • n_components: int, float, None 或 string，PCA 算法中所要保留的主成分个数，也即保留下来的特征个数，如果 n_components = 1，将把原始数据降到一维；如果赋值为 string，如 n_components=’mle’，将自动选取特征个数，使得满足所要求的方差百分比；如果没有赋值，默认为 None，特征个数不会改变（特征数据本身会改变）。
  • copy：True 或 False，默认为 True，即是否需要将原始训练数据复制。
  • whiten：True 或 False，默认为 False，即是否白化，使得每个特征具有相同的方差。
  • explainedvariance_ratio：返回所保留各个特征的方差百分比，如果 n_components 没有赋值，则所有特征都会返回一个数值且解释方差之和等于 1。
  • ncomponents：返回所保留的特征个数。
  • fit(X): 用数据 X 来训练 PCA 模型。
  • fit_transform(X)：用 X 来训练 PCA 模型，同时返回降维后的数据。
  • inverse_transform(newData) ：将降维后的数据转换成原始数据，但可能不会完全一样，会有些许差别。
  • transform(X)：将数据 X 转换成降维后的数据，当模型训练好后，对于新输入的数据，也可以用 transform 方法来降维。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import numpy as np
from sklearn.decomposition import PCA
X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
pca = PCA(n_components=2)
newX = pca.fit_transform(X)
print(X)
Out[365]:
[[-1 -1]
 [-2 -1]
 [-3 -2]
 [ 1  1]
 [ 2  1]
 [ 3  2]]
print(newX)
Out[366]:
array([[ 1.38340578,  0.2935787 ],
       [ 2.22189802, -0.25133484],
       [ 3.6053038 ,  0.04224385],
       [-1.38340578, -0.2935787 ],
       [-2.22189802,  0.25133484],
       [-3.6053038 , -0.04224385]])
print(pca.explained_variance_ratio_)
[ 0.99244289  0.00755711]

可以发现第一个特征可以 99.24% 表达整个数据集，因此我们可以降到 1 维：

1
2
3
4
pca = PCA(n_components=1)
newX = pca.fit_transform(X)
print(pca.explained_variance_ratio_)
[ 0.99244289]

通常来说使用 PCA 降维以后需要保留 95% 以上的方差，因此 sklearn 中的 PCA 有三种种使用方式：
第一种：手动设置维度 int 类型，即降维后的维度，查看保留的方差百分比（explainedvariance_ratio）来调整合适的 n_components，此时 n_components 大于 1。
第二种：手动设置保留的方差百分比 int 类型，系统会自动选择维度，此时 n_components 范围在（0,1], 例如 0.95。
第三种：还可以将参数设置为 string 类型 “mle”, 此时 PCA 类会用 MLE 最大似然算法根据特征的方差分布情况自己去选择一定数量的主成分特征来降维。

通常使用 pandas 读取数据的时候得到的 dataframe 可能需要处理一下, 变成 array 格式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import numpy as np
import pandas as pd

df =pd.read_excel('data')

matrix1 = df.values
matrix2 = df.as_matrix()
matrix3 = np.array(df)


from sklearn.decomposition import PCA
pca1 = PCA(n_components=30)
pca2 = PCA(n_components=0.3)
pca3= PCA(n_components="mle")
matrix_pca = pca.fit_transform(matrix)
print (explained_variance_ratio_)
variance_pca = pca.explained_variance_ratio_.sum()

print (variance_pca)

2.4 PCA 的一些变种以及 KPCA（Kernel PCA）的小例子

2.4.1 增量 PCA（IPCA）

当数据量较大时，使用 SVD 分解会耗费很大的内存以及运算速度较慢。幸运的是，可以使用 IPCA 算法来解决。先将训练样本分为 mini-batches，每次给 IPCA 算法一个 mini-batch，这样就能处理大量的数据，也能实现在线学习（当有新的数据加入时）。

下面是使用 Numpy 的 array_split() 方法将 MNIST 数据集分为 100 份，再分别喂给 IPCA，将数据降到 154 维。需要注意，这里对于 mini-batch 使用 partial_fit() 方法，而不是对于整个数据集的 fit() 方法。

1
2
3
4
5
6
7
8
9
10
from sklearn.datasets import fetch_mldata
mnist = fetch_mldata('MNIST original')
X = mnist["data"]

from sklearn.decomposition import IncrementalPCA
n_batches = 100
inc_pca = IncrementalPCA(n_components=154)
for X_batch in np.array_split(X, n_batches):
    inc_pca.partial_fit(X_batch)
X_mnist_reduced = inc_pca.transform(X)

还可以使用 Numpy 的 memmap 类来操纵储存在硬盘上的二进制编码的大型数据，只有当数据被用到的时候才会将数据放入内存。由于 IPCA 每次只需将一部分数据，因此能通过 memmap 来控制内存。由于使用的是输入的是整个数据集，因此使用的是 fit() 方法。

1
2
3
4
X_mm = np.memmap(filename, dtype="float32", mode="readonly", shape=(m, n))
batch_size = m
inc_pca = IncrementalPCA(n_components=154, batch_size=batch_size)
inc_pca.fit(X_mm)
2.4.2 随机 PCA

随机 PCA 是个随机算法，能快速找到接近前 d 个主成分, 它的计算复杂度与 d 相关而不与 n 相关。

1
2
rnd_pca = PCA(n_components=154, svd_solver="randomized")
X_reduced = rnd_pca.fit_transform(X_mnist)
2.4.3 核 PCA(Kernel PCA)

了解 SVM 都应该知道核技巧，即通过数学方法达到增加特征类似的功能来实现非线性分类。类似的技巧还能用在 PCA 上，使得可以实现复杂的非线性投影降维，称为 KPCA。该算法善于保持聚类后的集群 (clusters) 后投影，有时展开数据接近于扭曲的流形。下面是使用 RBF 核的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from sklearn.datasets import make_swiss_roll
data=make_swiss_roll(n_samples=1000, noise=0.0, random_state=None)
X=data[0]
y=data[1]

import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
ax = plt.subplot(111, projection='3d')
ax.scatter(X[:,0], X[:,1], X[:,2],c=y)
plt.show()

from sklearn.decomposition import KernelPCA
rbf_pca = KernelPCA(n_components = 2, kernel="rbf", gamma=0.04)
X_reduced = rbf_pca.fit_transform(X)

需要注意，此方法要使用大量内存，可能会使内存溢出。

选择合适的核与参数

由于 kPCA 是非监督算法，因此无法判断性能的好坏，因此需要结合分类或回归问题来判断。通过 GridSearch 来选择合适的核与参数，下面是一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from sklearn.datasets import fetch_mldata
mnist = fetch_mldata('MNIST original')
X,y = mnist["data"],mnist["target"]

from sklearn.decomposition import KernelPCA
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_)

3.1 基本原理（【t-SNE 完整笔记】）

SNE 是通过仿射 (affinitie) 变换将数据点映射到概率分布上，主要包括两个步骤：
SNE 构建一个高维对象之间的概率分布，使得相似的对象有更高的概率被选择，而不相似的对象有较低的概率被选择。
SNE 在低维空间里在构建这些点的概率分布，使得这两个概率分布之间尽可能的相似。
我们看到 t-SNE 模型是非监督的降维，他跟 kmeans 等不同，他不能通过训练得到一些东西之后再用于其它数据（比如 kmeans 可以通过训练得到 k 个点，再用于其它数据集，而 t-SNE 只能单独的对数据做操作，也就是说他只有 fit_transform，而没有 fit 操作）

3.2 T-SNE 算法流程：

有空再补

3.3 PCA 和 T-SNE：

PCA 和 T-SNE 同为降维工具，主要区别在于：
机制和原理不同，所以不在同一个包内

1
2
from sklearn.decomposition import PCA
from sklearn.manifold import TSNE

因为原理不同，导致，tsne 保留下的属性信息，更具代表性，也即最能体现样本间的差异；
T-SNE 运行极慢，PCA 则相对较快；
因此通常来说，T-SNE 只能用于展示（可视化）高维数据，由于速度慢常常先用 PCA 进行降维，再使用 tsne：

1
2
3
4
from sklearn.manifold import TSNE
from sklearn.decomposition import PCA
data_pca = PCA(n_components=50).fit_transform(data)
data_pca_tsne = TSNE(n_components=2).fit_transform(data_pca)

也称作多维缩放，类似 T-SNE，经常用于数据可视化，维度大多是时候是 2-3，他在降维的同时尽可能保留样本间的相对距离。
MDS 算法通过距离函数 d0 对所有 N 个 k 维数据计算距离矩阵，它衡量的是原始特征空间中的距离（大多数时候是欧式距离）

1
2
3
from sklearn.manifold import MDS
mds = manifold.MDS(n_components=3)
Xtrans = mds.fit_transform(X)

多维标度法解决的问题是：当 n 个对象（object）中各对对象之间的相似性（或距离）给定时，确定这些对象在低维空间中的表示，并使其尽可能与原先的相似性（或距离）“大体匹配”，使得由降维所引起的任何变形达到最小。多维空间中排列的每一个点代表一个对象，因此点间的距离与对象间的相似性高度相关。也就是说，两个相似的对象由多维空间中两个距离相近的点表示，而两个不相似的对象则由多维空间两个距离较远的点表示。多维空间通常为二维或三维的欧氏空间，但也可以是非欧氏三维以上空间。

5.1. 原理：

scipy 和 numpy 中都有奇异值分解
R=UΣV^T
R 为 m n 的矩阵
U 为 m m 的矩阵
V 为 n n 的矩阵
Σ(sigma) 为 mn 的矩阵, 除了对角元素不为 0，其他元素都为 0，并且对角元素是从大到小排列的，前面的元素比较大，后面的很多元素接近 0。这些对角元素就是奇异值。

5.2. 使用：

numpy 中调用方式和求特征值特征向量类似 (实际上特征分解是一种特殊的奇异值分解,

特征分解只能分解方阵，奇异值分解可以分解任意矩阵，pca 中的特征分解通常会使用 svd)

1
2
import numpy as np
U,Sigma,VT = linalg.svd(matrix)

5.3. 降维：

5.3.1TruncatedSVD（截断 SVD）：

sklearn 中代替 PCA 来给稀疏矩阵降维，稀疏矩阵具体查看库 scipy，原理和 sklearn 中的 PCA 一样是舍去了较小的奇异值，我试验了几次发现相同参数下稠密矩阵非稀疏矩阵降维的结果和 PCA 完全一样。
也就是说 sklearn 中的 pca 就是使用 svd 分解再选取三个在矩阵中间的对角矩阵中最大的一部分值，再还原这个矩阵。

5.3.2 SVD 的应用：

利用 SVD 降维实际上是用来简化数据，使用了奇异值分解以后仅需保留着三个比较小的矩阵，就能表示原矩阵，不仅节省存储量，在计算的时候更是减少了计算量。SVD 在信息检索（隐性语义索引）、图像压缩、推荐系统等等领域中都有应用。

经典的线性学习方法，也被称为 “Fisher” 判别分析。
LDA 试图让不同类别样本之间的距离最大，同时让相同类别样本之间的距离最小。简单来说 LDA 是为了使降维后的数据点尽可能的可分。

6.1. 原理和例子：

有空再补

6.2. LDA 和 PCA

当类别特别多的时候，每个类中的样本就越少，此时更加适合使用 PCA 而不是 LDA。PCA 不像 LDA 那样敏感，应该首先考虑 pca, 再根据具体情况来分析。
另外：PCA 是无监督的特征抽取方法，LDA 是一个有监督的方法。

1、Multidimensional Scaling (MDS) 降维的同时保留样本之间的距离，如下图。
2、Isomap 通过连接每个样本和它的最近邻居来创建一个图，然后降低维的同时尝试保留样本间的测地距离 (两个样本之间最少经过几个点)。
3、t-Distributed Stochastic Neighbor Embedding (t-SNE)，减少维度的同时试图保持相似的样本靠近和不同的样本分离。它主要用于可视化，特别是可视化高维空间中的聚类。
4、Linear Discriminant Analysis (LDA)，是一种分类算法，但是在训练定义了一个超平面来投影数据。投影使得同一类的样本靠近，不同一类的样本分开，所以在运行另一分类算法（如 SVM 分类器）之前，LDA 是一种很好的减少维数的技术。

image.png

【机器学习系统设计】
【机器学习—周志华】
【机器学习实战】
http://blog.csdn.net/baimafujinji/article/details/79407478