机器学习：维度打击

这个机器学习系列其实主要是自己学习周志华老师的《机器学习》的一些个人思考和感悟。发现研究算法有时候很容易看懂了一个伪代码、理解了一个算法设计者的idea，但是当自己从头开始编写的时候，才发现许多细化的问题被忽略掉了。

所以每次学习后的心得体会打算收集起来，我自己也在努力将书中所出现的每个算法都用最原始的Python语言来重新写一遍，而不是简单去调用一些sklearn库。当然当大家都很理解每个算法的trick和核心思想后，后期用这些算法解决自己问题的时候，去调用现成的库是完全没问题的。

既然打算要做好算法，那就不怕花时间和精力慢慢雕琢。

文章是个人的理解，代码也是通过理解自己编写的，所以必然会有诸多片面甚至错误的观点，欢迎大家指出，欢迎交流讨论。

漫漫长路，那就从降维开始谈起吧！

本文中所涉及和编写的代码，大家可以在我的GitHub中查看

https://github.com/buaaguotong/Machine-Learning

机器学习之降维与度量学习

（一）、为何要进行数据的降维？——从k邻近学习谈起

k邻近学习是一种非常原始和简单的监督学习算法，它的核心思想是，通过选定的某个样本它周围的“邻居”（通常由满足一定范围内距离测度内的样本组成）的标签，来预测该选定样本的标签。预测的计算过程通常是“投票”过程或取平均过程，一些考虑更周全的方法，还会考虑和“邻居”的远近，并以距离测度的远近作为权重，进行加权平均进行预测。

这里的k，是超参数，其意义是考虑该被选中样本周围的k个“邻居”。显然，超参数k是一个对模型学习效率影响极大的因子，不同的k，会使模型的学习能力迥然不同。

可见，k邻近学习模型是一个非常简陋的模型，读者很容易轻易质疑它的表现能力，但是令人惊讶的时，在某些寻常的假设下，这个“简陋学习模型”的表现效果（泛化错误）居然不超过复杂的贝叶斯最优分类器的错误率的两倍！

假设：

样本独立同分布：

该假设是统计机器学习的寻常假设，这个假设大多都是由于我们在简化计算的过程中，不约而同认可的一个化简方法：

可以看出，由独立同分布，我们可以将n维联合概率密度分布转化为重积分，大大简化了数学计算上的难度；除此，还将乘法转化为了加法，这在计算机处理中有大有裨益的。

任意的样本x和任意小的正数，在x的附近距离的范围内总能找到一个训练的样本：

该假设似乎承认了样本足够的密集

证明：

为何要谈到k邻近学习？通过上面的分析，我们看到了，如果样本密度足够的稠密，即使是简陋的学习模型，泛化能力居然可以达到某种程度上的“好”。

这给了我们莫大的启示：倘若我们在对模型进行训练中，如果能保证我提供的样本足够的密集，那么会让我们的模型表现能力更好！而且这种模型上的改观甚至是数量级的！

这其实是我们长久所想达到的境界：仅仅去改善训练集，不用绞尽脑汁去优化我model的算法，就能让model的表现能力飙升。颇有一些降龙十八掌的感觉。

（二）、低维嵌入

遗憾的是，实际中许多数据都是高维的，因为许多研究的问题对象，都有诸多的特征，况且特征的重要性不一样，这两点都导致高维数据的稀疏性；当维度足够高，例如：对一张灰度图片，将其展开成向量，维度特征轻而易举就会达到万级的，此时连距离的计算都会出现问题，甚至是最简单的欧式距离的计算，就会消耗巨大的计算资源和时间，我们无法接受。

高维数据表现出的稀疏性、距离无法计算性，是机器学习领域著名的“维度灾难”的概念。缓解“维度灾难”的一个有效方法是降维。

这就是低维嵌入的概念，虽然我们观测到的一组数据是高维空间的，但是与模型学习任务息息相关的，可能就是最重要的几个维度，即，我们care的其实是高维空间中的一个低维子空间。举个简单的例子：假设我们当前的学习任务是3D场景中，做一个地面的路径规划，实际上，障碍物的高度信息是没有意义的，我们只关心障碍物的范围和所谓的安全距离。因此，这个3D数据实际上对任务有帮助的只有两维。

除此之外，降维还有某种滤波的作用（原谅我曾经一直把通信作为我毕生所追求的的事业），这点我们会在下面提到。

（三）

算法1：多维缩放（MultipleDimensional Scaling-MDS）:

算法的核心思想：

我们承认对某个需要降维的高维空间，存在着一个低维嵌入，我们是从目标函数出发进行降维。假设,总共有m个样本，每个样本的维度为dim[1,d],我们在寻常的欧式空间进行度量距离，原始的距离矩阵为：

容易地，距离矩阵是对阵矩阵。我们的目标是在d’维的低维空间（d’

低维空间的内积矩阵为

~dim[m,m]。

对目标的约束也很简单，我们只要求，在低维空间能够保持高维空间的距离，也就是说，样本在高维空间和低维空间的距离一样

目标函数：

取绝对值在数学运算上具有难操作性，常见的操作是把取绝对值换成平方加减，以下所有的运算都是以此为出发点，进行算式上的统一：

可见，可以通过降维后距离不变的条件，求得低维嵌入空间的内积矩阵。对内积矩阵进行特征值分解，可以得到

的特征值向量，对该向量从大到小排列，往往会发现，许多特征值的值为0，或者为特别小的数。

这些小值对应的特征向量是可以被删除掉的，这也是目前诸多降维算法的共同之处，这些小值很有可能是由数据原本的数据噪声产生的，并不会反应原始数据所在的高维空间的特征。这点有待于深入学习高等代数，再回头继续理解。

基于此，得到MDS算法的伪代码：

在不调用任何Python机器学习模块的编程过程中，对算法有了更深入的理解，当然也发现了一些问题。

在实现MDS的过程中，最大的一个问题，在于对低维嵌入空间内积矩阵B的分解。

B~dim[m,m]，对B进行特征值分解会出现m个特征值，但是算法中一直强调是d个特征值。实际上，在实现该算法的过程中，原始空间的维度已经被嵌入在距离矩阵中了，无法获得。这也是我对MDS算法的最大疑虑之处。朋友们若有高见，愿不吝赐教。

算法2：主成分分析（PrincipalComponent Analysis-PCA）

PCA算法是大家最为耳熟能详的一个降维算法。之所以它很有名，并不是它的效果有多么好，实际上，它的效果很一般。它最大的特点是：简单。

降维，在数学里可以当做一种运算。线性降维，则是线性变换，它的基本思想便是通过矩阵乘法，将高维空间线性映射到一个低维空间。由于线性变换对空间具有封闭作用，所以线性变换后最大的保持了数据的特征。

非线性变化则无法通过常规的矩阵加减乘除来实现。实际中的诸多问题，数据空间都复杂的，有流面形、凸形、甚至有的是间断行的，简单的线性映射，会让大部分的高维数据点在低维空间里面严重交织，无法处理。所以线性映射其实实际用处并不是特别大。

但是作为降维最为著名的一个算法，我们仍然有必要了解它的前世今生。

线性映射在数学上表示为：

我们的目标是求解变换核矩阵。当对低维空间的性质有不同的要求时，相对于对的约束不同。

PCA对低维子空间的要求时：映射后的样本最大可分。

这很符合我们的直觉，如果映射后所有的样本都聚集在一起，这显然不是个合理的降维，因为数据特征的差异性太小了。

若要求最大可分，则是变换后数据的方差最大，所以目标函数为：

对上式使用拉格朗日乘子法，可以求得：

显然，变换核矩阵，是原始数据协方差矩阵的特征向量。

容易给出伪代码：

原始数据是四维的，样本示例(5.6,1.2,1.5,3.3)在PCA算法下被映射到了二维平面上。可以看出，原来无法想象的四维空间，降维后可以进行可视化，并且每个样本点分开的距离我们尚能接受。

这里需要额外说明，低维空间的维度是用户指定的，一般为了数据可视化，都会把他们设置为2或3。无论是MDS还是PCA，都对特征值进行了舍弃。但是舍弃的过程往往是必要的，一方面，舍弃这部分信息可以让样本的采样密度变大；另一方面，当数据本身存在噪声的影响时，这种舍弃操作对数据进行了滤波。

PCA另一个不被线性条件约束的算法是所谓的核化线性降维，它引入了核函数，因此，映射的部分不必是线性映射。实际上，这种求解仍然归于线性的，这里的非线性承认的是变换核矩阵是无法通过乘法来设计的。有兴趣的读者可以自己查阅相关文献。

我们只讨论，那些“骨子里”就是非线性的降维算法。

算法3：流行学习（Manifold Learning）：等度量映射（Isometric Mapping-Isomap）：

这一系列算法借鉴了拓扑流行概念。“流行”是一种空间结构，一类很易于理解的流行形状，类似于三维空间中s形曲面，注意不可闭合：

流行学习降维的过程可以下图很形象地表示：

两个小人拉开曲面所依据准则的不同，诞生了不同的流行降维算法。

“流行”空间在局部上是欧式空间的同胚空间，它在局部就有欧式空间的性质，也就是说，我们可以在局部进行欧式距离的计算，再在整个构型上，累加获得流行曲面上的距离。这是很有启发性的，由此诞生了著名的等度量映射算法。

流行学习理论认为，在高维空间直接计算距离是不合适的，例如：在地球上，我要计算北京到西雅图的距离，如果用欧式距离的概念，那就是穿过地心的一条直线，但这显然在地球上是做不到的；所以更合理的距离是，贴近地球表面的一条曲线距离。

这便是流行学习的最重要的概念，我们所求得距离，是在曲面上的本真距离。

对于每个样本点，基于欧式距离，选取该点的k邻近的k个点。把该样本点和邻近k个点的距离定义为欧式距离，而与非临近点的距离定义为无穷（不可达）。

所有的样本点以及它们的临近点共同构成了一个structure，把它摊平，实际上是一个无权重，单源的图，所以对这张图执行经典最短路径算法，例如：Dijkstra、Floyd等算法，便可获得所有流行曲面上点之间的距离。

将得到的这个距离矩阵输入到MDS算法里，就可以得到降维后的数据。

值得说明的是Isomap算法仅仅得到了样本数据在低维空间的分布，对于新的样本，如何进行降维？一个容易想到的思路是训练一个分类器，再对新的样本的低维空间表示直接进行预测。

算法4：流行学习（Manifold Learning）：局部线性嵌入（Locally Linear Embedding-LLE）：

LLE的想法又是一个不同的出发点。Isomap基于同胚空间的欧式特性，从距离的角度来谈；而LLE则是更类似于k邻近学习的一种思路，假设在高维空间里，样本可以通过它邻近的几个样本，通过线性加权得出：,我们希望在低维空间里面，这种线性能够保持：

所以，LLE算法是从保持数据之间的相关性来出发的。

离样本比较远的样本对局部的线性关系没有影响，所以相比Isomap，他的时间复杂度和空间复杂度都小的多。

Qi是每个样本的邻近下标集合，目的是为了基于该下标集合，对每个样本点计算出重构权重系数：

LLE算法保证了在低维空间中的重构关系不变，所以：

最小化重构代价，就可以获得低维样本数据；

重构代价公式等价于下式：

不同降维算法之间的比较：

(1)不同算法对流行曲面的拉伸效果

从不同的角度看，每个算法都有它的优缺点。因为映射到低维空间上的空间迥然不同。

(2)对手写数字体的降维：

sklearn中手写数字体的dataset是8*8的灰度图，我们将其拉伸为dim[1,64]的高维数据，对他们进行降维，不同的算法表现出来不同的效果：

通过对比我们发现，进行数据降维后，对目标进行可视化，样本出现了某种物以类聚的性质，这其实就是原始数据中的某种难以描述的结构，这才是无监督学习最大魅力所在。

降维是一种无监督学习。有的读者可能会疑惑，对数字手写图像的降维明明存在着标签呀，为何还是无监督。事实上，我们在训练降维model的时候，没有利用到任何标签的信息，这些标签的信息只是在我们完成降维后，通过对比原始数据集中的标签，进行对他们自然形成的每一个簇进行命名。

这引发了我本人的一些简单浅显的思考：

1.什么样的数据才具有流行的特性。即，是否存在某种基于我的数据的，最优的模型？比如上面手写数字图像的降维，t-SNE算法表现的足够卓越（t-SNE算法的核心思想这里不再特别强调，详细论文可查：

http://www.jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf）

2.当我的数据中不存在标签时，对于降维形成的簇，我如何去命名，或者如何发现他们的共同规律呢？