降维（Dimensionality Reduction）

数无形时少直觉。

降维分为以PCA为代表的线性降维和T-SNE为代表非线性降维。本文主要介绍这两种降维方式和代码实现，当然也会提及其他的降维算法比如LDA。

PCA

Principal component analysis (PCA) is a statistical procedure that uses an orthogonal transformation to convert a set of observations of possibly correlated variables (entities each of which takes on various numerical values) into a set of values of linearly uncorrelated variables called principal components. PCA（principal component analysis）主成分分析是一种通过正交变换，将原来可能相关的变量转换成线性不相关的变量。

PCA的优化目标：将一组$N$维向量降为$K$维度（$0< K < N $），选择$K$个单位正交基，使得原始数据变换到这组正交基上，各个特征之间协方差为0，单个特征的方差尽可能大。

（1）数学概念

均值表达式： $$ \begin{equation} \bar{X}=\frac{\sum_{i=1}^{n} X_{i}}{n} \end{equation} $$ 标准差（SD）是衡量单个数据离散程度的指标。 $$ \begin{equation} s=\sqrt{\frac{\sum_{i=1}^{n}(X-\bar{X})^{2}}{(n-1)}} \end{equation} $$

在统计学中，使用采样来预估总体的性质。分母是$n-1$而不是$n$，其中有比较复杂的数学证明，简单的结论就是，使用$n-1$计算出来的样本标准差和真实整体数据的标准差更加接近。

方差（Variance）：在一维空间中数据偏离均值的程度。 $$ \begin{equation} \sigma^{2}=\frac{\sum_{i=1}^{n}\left(X_{i}-\bar{X}\right)^{2}}{(n-1)} \end{equation} $$ 协方差（Covariance）：二维空间中，单个特征和其他的特征之间的关系。 $$ \begin{equation} \operatorname{cov}(X, Y) = s^2 =\frac{\sum_{i=1}^{n}\left(X_{i}-\bar{X}\right)\left(Y_{i}-\bar{Y}\right)}{(n-1)} \end{equation} $$ 解读协方差值：

Exact value is not as important as its sign.

• 数值的符号的意义大于具体数值意义
• 如果是正值，那么说明两个维度特征是同增同减
• 如果是负值，那么说明两个维度特征是异步，一增一减
• 如果是0，两个维度是线性独立

线性无关 数学表达为： $$ \begin{equation} c_{1} x_{1}+c_{2} x_{2}+\ldots+c_{k} x_{k}=0 \end{equation} $$

当且仅当 $c_1 =c_2= \dots =c_k =0$ 图形表达为： 可以发现，PCA消除的真的只是线性的相关性。

协方差矩阵（Covariance Matrix）将协方差矩阵话。该矩阵具有对称性。其中主对角线是方差。 $$ \begin{equation} C=\left[\begin{array}{ccc}{\operatorname{cov}(X, X)} & {\operatorname{cov}(X, Y)} & {\operatorname{cov}(X, Z)} \\
{\operatorname{cov}(Y, X)} & {\operatorname{cov}(Y, Y)} & {\operatorname{cov}(Y, Z)} \\ {\operatorname{cov}(Z, X)} & {\operatorname{cov}(Z, Y)} & {\operatorname{cov}(Z, Z)}\end{array}\right] \end{equation} $$

特征值 只有方阵才有特征值和特征向量。其中特征值和特征向量是成对出现的。其次并不是所有的方阵都有特征向量。

特征向量

A vector consists of both length and direction. 一个向量由长度和方向组成。

$$ \begin{equation} \mathbf{A} \cdot \mathbf{v}=\lambda \cdot \mathbf{v} \end{equation} $$

其中 $\mathbf{A} $是$m * m$矩阵， $\mathbf{v}$是特征向量， $\lambda$是特征值。所有的特征向量都是正交（相互垂直）的。

矩阵相乘的意义，不加解释的给出：两个矩阵相乘的意义是将右边矩阵中的每一列列向量变换到左边矩阵中每一行行向量为基所表示的空间去。数学表达为：

$$\begin{pmatrix} p_1 \\ p_2 \\ \vdots \\ p_R \end{pmatrix} \begin{pmatrix} a_1 & a_2 & \cdots & a_M \end{pmatrix} = \begin{pmatrix} p_1a_1 & p_1a_2 & \cdots & p_1a_M \\ p_2a_1 & p_2a_2 & \cdots & p_2a_M \\ \vdots & \vdots & \ddots & \vdots \\ p_Ra_1 & p_Ra_2 & \cdots & p_Ra_M \end{pmatrix}$$

在PCA中$R$表示降维之后的维度，如果$R$比原来的维数小，那么就达到了降维效果。

（2）PCA

既然是降维算法，那么需要去除一些维度，留下一些维度。留下的维度需要满足以下的要求

• 不依赖别的特征，具有独立性（低协方差）
• 具有较大的变化（和噪声不一样，是较高的方差）

算法步骤

1). 数据标准化（减均值，不是必须要除以标准差） 2). 计算协方差矩阵 3). 计算协方差矩阵的特征值和特征向量 4). 计算主成分 5). 降维

不是必须要除以标准差，如果数据特征都是在一个量纲，那么没有必要，否则话，需要。

（3）PCA的特点

简单的，无参数化的降维方法

对于离群点很敏感，因为PCA涉及到计算方差 无法处理非线性的依赖关系

（4）代码实现

1). 基于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

from numpy import array
from numpy import mean
from numpy import cov
from numpy.linalg import eig
# define a matrix
A = array([[1, 2], [3, 4], [5, 6]])
print(A)
# calculate the mean of each column
M = mean(A.T, axis=1)
print(M)
# center columns by subtracting column means
C = A - M
print(C)
# calculate covariance matrix of centered matrix
V = cov(C.T)
print(V)
# eigendecomposition of covariance matrix
values, vectors = eig(V)
print(vectors)
print(values)
# project data
P = vectors.T.dot(C.T)
print(P.T)

2). Sklearn实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# Principal Component Analysis
from numpy import array
from sklearn.decomposition import PCA
# define a matrix
A = array([[1, 2], [3, 4], [5, 6]])
print(A)
# create the PCA instance
pca = PCA(2)
# fit on data
pca.fit(A)
# access values and vectors
print(pca.components_)
print(pca.explained_variance_)
# transform data
B = pca.transform(A)
print(B)

t-SNE

t-SNE 中的 t 表示 t 分布， SNE 表示随机近邻嵌入。 t-SNE 主要的优势在于保持局部结构的能力，这意味着高维空间中相距近的点投影到低维空间中仍然相近。可以生成漂亮的可视化图。

算法原理

t-SNE 算法对每个数据点近邻的分布进行建模，其中近邻是指相互靠近数据点的集合。在原始高维空间中，我们将高维空间建模为高斯分布，而在二维输出空间中，我们可以将其建模为 t 分布。该过程的目标是找到将高维空间映射到二维空间的变换，并且最小化所有点在这两个分布之间的差距。与高斯分布相比 t 分布有较长的尾部，这有助于数据点在二维空间中更均匀地分布。

可以参考这个网站中最后的视频 什么是TSNE

t-sne 的缺点

• 计算量大，时间复杂度是 $O(n^2)$
• 专用于可视化，嵌入空间是 2 或者 3
• 需要尝试不同的初始化点，防止局部次优解

（1）PCA和 t-SNE的background：

我们有一堆数据并且想要知道这些数据 “looks like”， 然后建立了一个"map"，使这些数据投影到了二维或者三维平面上。但是PCA 是线性 mapping，

PCA learns a linear mapping, which is very restrictive. PCA focuses on preserving large pairwise distances. 对于 t-SNE 的定义 compute pairwise similarities between data with normalized Gaussian kernel

（2）计算步骤

1). 在高纬计算两点 with normalized Gaussian kernel(高斯分布) $$ p_{i,j}=\frac{\exp (-|x_{i}-x_{j}|^{2} / 2 \sigma^{2})}{\sum_{k} \sum_{l \neq k} \exp (-|x_{k}-x_{l}|^{2} / 2 \sigma^{2})} $$ 2). 在低维计算两点（使用 normalized Student-t similarities in the t-SNE map） $$ q_{i,j}=\frac{(1+\overline{|} y_{i}-y_{j} |^{2})^{-1}}{\sum_{k} \sum_{l \neq k}(1+|y_{k}-y_{l}|^{2})^{-1}} $$ 3). 计算KL 散度（尽可能的最小化两者之间的差异， kl尽可能的小） $$ K L(P | Q)=\sum_{i} \sum_{j \neq i} p_{i j} \log \frac{p_{i j}}{q_{i j}} $$

（3）数学补充

1). 为什么选择 KL divergence?

The KL divergence preserves local data structure： 如果在高维度 p中相差大，但是在低维q 中相差小，那么kl 的值非常大。如果再高纬度p 相差小，但是在低纬度相差大，那么kl 的值就非常小。所以说尽可能保存了 local information。

降维必然带来信息损失，这里更加保存的是局部信息，那么必然损失的全局信息。而 t 分布能够放大这种密度，因为t 分布更加长尾。

2). t分布和卡方分布

• 关于 $t$ 分布， 假设 $X \sim N(0, 1) $ ， $Y \sim \chi^{2}(n)$ ，那么 $ Z=\frac{X}{\sqrt{Y / n}} $ 的分布就被称为自由度为 $n$ 的 $t$ 分布， 记做 $Z \sim t(n)$。 但自由度$n$ 越大，那么越是接近正太分布。一般来说 $t$ 分布比 正太分布更加长尾。 如果是正太分布，那么就可以使用中心极限定理，但是 $t$ 分布就不可以了。$t$ 分布也被称为 学生t 分布。
• 若 $k$个随机变量 $Z_1, Z_2, … Z_n$是相互独立，符合标准正态分布的随机变量（数学期望为0、方差为1），则随机变量 $Z$的平方和

$$ X=\sum_{i=1}^{k} Z_{i}^{2} $$

被称为自由度为 $k$ 的卡方分布， 记做 $X \sim \chi^{2}(k)$。

（3）T-SNE特点

1). 可以被用来做

• Use t-SNE to get some qualitative hypotheses on what your features capture 这个是定性分析
• 在输入和输出形式上可以 more creative

2). 不可以被用来 Don’t

• 不是证明你的理论的工具
• assign meaning to distance across empty space（注意这个是局部的特征，not 全局的信息）
• think that t-sne will help you find outlier, or assign meaning to point densities in cluster
• forget the scale (perplexity) matters （ you can think of perplexity as the “effective” number of nearest neighbors， 所以说当这个 perplexity 越是接近原始一个簇的neighbors的个数，那么这个分类的效果是）
• forget that t-SNE 是解决一个 non-convex objective: there are local mimima
• local minima generally split a natural cluster into multiple parts （就是如何有这个效果，那么不要惊讶，有可能出现多个不同的parts）
• forget that low-dimentional metric spaces cannot caputure non-metric similarities

（4）How input similarities in t-SNE are actually computed

1). compute conditional similarities $$ p_{j |i}=\frac{\exp (-|x_{i}-x_{j}|^{2} / 2 \sigma_{i}^{2})}{\sum_{j^{\prime} \neq i} \exp (-|x_{i}-x_{j^{\prime}}|^{2} / 2 \sigma_{i}^{2})} $$ perform a binary search over $\sigma_{i}$ to obtain a target perplexity

( 从这里得到启发，如果某个指标是不对称的，那么 symmetrize 就是可以得到一个对称的指标， 想想从kl divergence 到JS divergence这个过程) 2). Symmetrize the conditions $$ p_{i |j}=\frac{p_{j | i}+p_{i | j}}{2 N} $$

t-sne 时间复杂度 $n^2$

naive implementations are quadratic in the number of data points

（5）Conclusion

t-SNE is a valuable tool in generating hypotheses and understanding, but does not produce conclusive evidence.

实践

sklearn 中的 TSNE

1
2
3
4

from sklearn.manifold import TSNE

tsne = TSNE(n_components=2, perplexity=35, learning_rate=200, n_iter=2000, n_jobs=-1)
X_transformed = tsne.fit_transform(embeddings)    

常见参数解释

t-sne 的参数

困惑度大致等价于在匹配每个点的原始和拟合分布时考虑的最近邻数，较低的困惑度意味着我们在匹配原分布并拟合每一个数据点到目标分布时只考虑最近的几个最近邻，而较高的困惑度意味着拥有较大的「全局观」。

常用的 method

1
2
3

fit # 将X 投影到一个嵌入空间
fit_transform # 将 x 投入到一个嵌入空间并返回结果

feature selection

定义：

feature selection 的过程就是dimension reduction的过程。就是说由较多的数据集 映射到 较少的数据集，这种方式就叫做降维。

Using dimensionality reduction techniques, of course. You can use this concept to reduce the number of features in your dataset without having to lose much information and keep (or improve) the model’s performance.

为什么? （必要性分析）

时间角度，空间（内存）角度。减少冗余信息，就减少了模型去拟合”噪声“数据的可能性。

常见的有以下几种方式：

** 可以归结成几类：特征本身（数据缺省值比较大，数据的波动性比较小），特征和特征之间（特征具有较高的相关性，使用PCA 进行降维），特征和最后的target的关系（机器学习模型的 feature importance，卡方分布检测特征和target 的重要性，Pearson 相关系数：-1 表示负相关，0 表示不相关，1表示正相关）。**

可以划分成三类：

一、独立于模型的特征选择（没有在入模时候进行的特征选择）或者叫做 filter：

1. 移除低方差的特征 (Removing features with low variance)

当特征值都是离散型变量的时候这种方法才能用，如果是连续型变量，就需要将连续变量离散化之后才能用。

2. 单变量特征选择 (Univariate feature selection)

对于分类问题(y离散)，可采用：卡方检验，f_classif, mutual_info_classif，互信息 对于回归问题(y连续)，可采用：皮尔森相关系数，f_regression, mutual_info_regression，最大信息系数

这里说的是特征选择，但是上面说的都是针对“特征重要性” 这点展开的，但是一个特征入模是一个复杂的过程，需要考虑的因素很多。比如：变量的预测能力，变量之间的相关性，变量的简单性（容易生成和使用），变量的强壮性（不容易被绕过），变量在业务上的可解释性（被挑战时可以解释的通）等等。当然，其中最主要和最直接的衡量标准是变量的预测能力。

尤其是当你使用LR 这类简单的模型的时候，是需要重点的在特征上下功夫的，因为模型是线性的，比较简单，引入特征，加入非线性，然后才能更好的表达实际问题。

二、基于模型选择的特征排序

有些机器学习方法本身就具有对特征进行打分的机制，或者很容易将其运用到特征选择任务中，例如回归模型，SVM，决策树，随机森林等等。这种方法的思路是直接使用你要用的机器学习算法，针对 每个单独的特征 和 响应变量建立预测模型。假如 特征 和 响应变量 之间的关系是非线性的，可以用基于树的方法(决策树、随机森林)、或者 扩展的线性模型 等。

三、无监督的模型选择

聚类，可以从降维的角度理解。可以在机器学习算法中的importance 不是很大，容易被忽略的特征。

SVD

SVD decomposes the original variables into three constituent matrices. It is essentially used to remove redundant features from the dataset. It uses the concept of Eigenvalues and Eigenvectors to determine those three matrices. We will not go into the mathematics of it due to the scope of this article, but let’s stick to our plan, i.e. reducing the dimensions in our dataset.

$$ \operatorname { Data } _ { m \times n } = U _ { m \times m } \Sigma _ { m \times n } V _ { n \times n } ^ { T } $$ SVD将原始的数据集矩阵Data分解成三个矩阵：U、Sigma、VT，如果原始矩阵是m行n列，那么U、Sigma和VT分别就是m行m列、m行n列、n行n列。比较值得一提的是矩阵Sigma，该矩阵只有对角元素，其他元素均为0，有一个惯例是：Sigma的对角元素是从大到小排列的。这些对角元素就称为奇异值.

PCA 是方阵是 $ m^2 $ 操作，那么SVD 是 $mn$ 就是更加广泛的矩阵操作。

特征分解只能分解方阵，奇异值分解可以分解任意矩阵，pca中的特征分解通常会使用svd。（方阵是一种特殊的矩阵，当行数和列数相同的时候就叫做方阵）

投影也是一种降维手段

这种思想真的是服气，虽然我也不是很懂，但是思想是很好的 By projecting one vector onto the other, dimensionality can be reduced.

当投影到另一个平面的时候，原来的平面维度就消失了，所以只剩下了投影面的维度。

T-sne

就是指出 t-sne 这个可以非线性降维。有local approaches 和 global approaches 两种方式，我大概的理解就是：类之间还能尽可能的远离，类内保持差异性。（不知道对不对） So far we have learned that PCA is a good choice for dimensionality reduction and visualization for datasets with a large number of variables. But what if we could use something more advanced? What if we can easily search for patterns in a non-linear way? t-SNE is one such technique. There are mainly two types of approaches we can use to map the data points: Local approaches : They maps nearby points on the manifold to nearby points in the low dimensional representation. Global approaches : They attempt to preserve geometry at all scales, i.e. mapping nearby points on manifold to nearby points in low dimensional representation as well as far away points to far away points.

LDA（有监督）

和上面最大的区别在于 LDA 是有监督的， LDA试图让不同类别样本之间的距离最大，同时让相同类别样本之间的距离最小。简单来说LDA是为了使降维后的数据点尽可能的可分。

上图中国提供了两种投影方式，哪一种能更好的满足我们的标准呢？从直观上可以看出，右图要比左图的投影效果好，因为右图的黑色数据和蓝色数据各个较为集中，且类别之间的距离明显。左图则在边界处数据混杂。以上就是LDA的主要思想了，当然在实际应用中，我们的数据是多个类别的，我们的原始数据一般也是超过二维的，投影后的也一般不是直线，而是一个低维的超平面

这个是关于该算法的一个讲解， 如果对于步骤感兴趣的话。

PCA vs. LDA

LDA用于降维，和PCA有很多相同，也有很多不同的地方，因此值得好好的比较一下两者的降维异同点。

首先我们看看相同点： 　　　　1）两者均可以对数据进行降维。 　　　　2）两者在降维时均使用了矩阵特征分解的思想。 　　　　3）两者都假设数据符合高斯分布。 我们接着看看不同点： 　　　　1）LDA是有监督的降维方法，而PCA是无监督的降维方法 　　　　2）LDA降维最多降到类别数k-1的维数，而PCA没有这个限制。 　　　　3）LDA除了可以用于降维，还可以用于分类。 　　　　4）LDA选择分类性能最好的投影方向，而PCA选择样本点投影具有最大方差的方向。

当类别特别多的时候，每个类中的样本就越少，此时更加适合使用PCA而不是LDA。