人工智能知识全面讲解：K近邻学习法

10.1.1 “人以群分”的算法

在现实生活中，我们经常遇到需要快速分辨陌生人身份的场景。在某些情
况?，我们会用富有逻辑性的“决策树”思维做判断。例如求职者去一家新公
司面试，面试官可能是同级员工也可能是人力资源主管或者部门主管，总之是
这三种职位中的某一个。通常面试官职能不同，提问的问题也不同，因此通过
面试官提出的问题就能够逐步确定他的职位。而在另一些情况?，我们会用推
测式的“朴素贝叶斯”思维去判断，例如，走在路上遇见一个黑色皮肤的人，
因为他的肤色以及长相特点，我们会推测他大概率是从非洲来的。
还有一种情况，我们对这个人的信息一无所知，仅仅因为他跟某些人走得
很近，就判断他们属于同一类人。例如我们在报纸上看到某人和学校校长在某
地开会，我们能够判断这个人大概率也是教育界人士。这也是我们常说的“物
以类聚，人以群分”，这种判断方式虽然很简单但是看起来似乎有理有据，并
且也能猜个“八九不离十”，因此很自然会有人想到将其转变为一种机器学习
的方法，即K近邻学习法。
K近邻学习法（K-Nearest Neightbor，KNN）是一种较古老的机器学习算
法，主要用于解决分类问题，在特定场景?也能够用于回归问题。 KNN的核心
思想是通过测量不同样本之间的距离进行分类，简单理解就是看某个人和哪些
人走得更近一些，我们就认为这个人和这些人都是属于同一类人。
KNN 算法的解决思路是：一个样本在特征空间中，将这个样本的特征与和
它最相似（最邻近）的K个样本的特征进行对比，如果这K个样本中的大多数样
本都属于同一个类别，则我们判断该样本也属于这个类别。一般来说，我们只
选择样本集中前K个最相似的数据，这就是K近邻算法中K的出处，通常K是不大
于20的整数。显然，对于当前待分类样本的分类，需要大量已知分类的样本的
支持，因此KNN是一种“有监督学习算法”。
10.1.2 如何实现KNN算法
如图 10-1 所示，所有样本可以在二维空间中表示。图中，黑色样本和灰
色样本为已知分类样本，白色样本为新加入的样本。若使用KNN算法对图中白
色样本进行分类，则当K=3时，其最邻近的样本中有2个灰色样本和1个黑色样
本，因此判断该待分类样本为灰色样本；当K=5时，其最近邻的样本中有3个黑
色样本和2个灰色样本，因此判断该待分类样本为黑色样本。

通过这个例子可以看出，对于KNN算法来说，有两个关键点：一个是分类
结果受K值影响，选取的近邻样本点个数不同，分类结果可能不同；另一个是
图中的“近邻”都是我们肉眼判断的结果，这显然是不合理的。因此不管是当
前已知的样本数据集，还是将来可能出现的待分类样本，都必须用向量的形式
加以表征。向量的每一个维度，刻画样本的每一个特征，只有构建向量才有办
法定?距离公式，计算距离。
K 值的选择没有一个固定的标准。但是 K 值的选取会影响待分类样本的
分类结果，进而影响算法的偏差与方差。因此我们需要用“交?验证法”——
多试验几次，寻找最合适的 K 值。对于距离的度量，我们有很多的距离度量
方式，常用的距离计算方法有：欧氏距离、余弦距离、汉明距离、曼哈顿距离
等，各个距离的区别及公式在此不再展开?述，通常我们选择使用欧式距离。
KNN算法步骤如图10-2所示，主要为：
（1）计算已知类别数据集中的样本点特征与新的样本点特征之间的距
离。
（2）按照距离递增次序排序。
（3）选取与当前点距离最小的K个点。
（4）确定前K个点所属类别的出现频率。
（5）返回前K个点所出现频率最高的类别作为当前点的预测分类。

 

KNN 算法的优势在于简单、训练的时间复杂度较低，适用于非线性分类场
景，并且对异常数据点不敏感。但该算法同样有不足之处，例如在样本不平衡
的情况?，如一个类的样本容量很大，而其他类的样本容量很小，这有可能导
致当输入一个新样本时，该样本的 K 个邻居中某个大容量类的样本占多数，
因此判断为该类，可实际上在 K 值小的情况?它应该属于小容量那一类。对
于这个问题可以采用权值的方法来改进。但是该方法的计算量较大，对每一个
待分类的样本都要计算它到全体已知样本的距离，才能求得它的 K 个最近邻
点。目前常用的解决方法是事先对已知样本点修剪，事先除去对分类作用不大
的样本。该算法适用于样本容量比较大的类域的自动分类，而样本容量较小的
类域采用这种算法比较容易产生误分。
然而在实际项目中，直接使用KNN算法，效果并没有想象中那么突出。主
要原因在于，平时我们面对的数据维度相当高，例如某银行在做客户流失预测
模型时使用的特征达到 15 000 个。在如此高的维度下想要做到数据足够密
集非常难，高维度下的数据十分稀疏并且距离计算复杂度相当高 。因此，要
想模型运行更快，使KNN算法能够发挥应有的优势，首先我们要想办法处理高
维数据。
10.2 从高维到低维的转换
10.2.1 维数过高带来的问题
在分类问题中，我们常常会遇到样本集看似不可线性区分的情况。解决这
类问题通常需要根据数据特点，将低维数据映射到高维空间，看看能否找到一
个“划分超平面”。在某些情况?，原本在二维平面不可线性区分的数据被转
换到三维空间时，就能够找到一个平面将不同类别的数据分开，如图10-3所
示。

 

维度表示数据特征的多少，二维表示样本数据有2个特征。上述方式实际
上是利用现有特征去构造新的特征以区分数据，是一种在特征太少，不足以进
行分类时，增加特征的方法。当数据特征太少时，获取的信息不足，比较难分
类；当数据特征太多时，又会变成一团乱麻，无从处理。既然数据特征太少
时，我们可以用“升维”的方式构造新的特征来解决问题，那么在数据特征太
多时，我们也可以尝试使用“降维”的方式，来减少特征，留?对我们有用的
信息。
对于维度大的数据，维度之间往往会存在相关性，这种相关性导致数据产
生了冗余。例如有两条数据，一条说这个人是男性，另一条说这个人不是女
性，那么这两条信息就是相关并且冗余的，可以去掉其中一条。降维的目的就
是为了消除这种冗余信息 。进一步来说，降维还可以剔去信息量小的信息，
实现信息的压缩。例如在图像处理领域就可以使用降维算法压缩图像，虽然压
缩后的图像清?度?降，但是图像的大小?大幅度?降，如图10-4所示。

 

降维是一种无监督学习算法，其根本目的是将数据从高维降低到低维层
次，也是对输入特征的一种精简。当我们通过数据处理得到了一组变量之后，
我们并不会直接将这些数据丢到模型中训练。因为这些数据之间可能存在关联
关系，如果不顾后果将全部数据都输入模型训练，可能会影响模型的精度。在
个别情况?，数据的特征量有可能比数据样本量还要大，如100条数据中的每
条数据包含200个特征，这时候难以得到一个准确的模型。
为了更好地理解数据，阅读数据间的有效信息，我们会采用一些数据降维
的办法对特征数目进行一定程度的缩减，在不丢失绝大多数信息的前提?尽可
能地生成解释力更强的特征，同时去除不必要的特征。
例如跑步比赛，我们可以用“时间”与“距离”这两个变量描述不同选手
的快慢程度，小梁同学跑100米只需要14秒，小李同学能够用15秒跑106米。在
这种情况?，我们很难比较哪个同学跑得更快。但是如果把变量转换为“速度
=距离/时间”，使用一个新的变量“速度”，就比较容易看出来小梁同学的平
均速度更快。这就是一次降维的过程，将二维的变量转换到一维表示。
上述例子中的降维，减少的维度非常少，同时压缩后也不会损失信息。如
果数据特征多到没有办法直接观察数据，或者包含冗余的特征，降维算法也能
工作。目前所使用的降维方法从数学上可证明，在将数据从高维压缩到低维的
过程中，能够最大限度地保留数据的有效信息。因此，不必担心降维会造成信
息丢失从而导致结果有很大的偏差。
降维算法的主要作用是压缩数据，提升学习算法的效率。通过降维，可以
降低特征的数量级。常见的降维方法有主成分分析法、线性判别分析法等。?
面我们从最基础的主成分分析法入手，逐步理解降维的方法与思路。

10.3 主成分分析法
10.3.1 PCA原理
主成分分析法（Principal Component Analysis，PCA）是统计学中最常
用的数据降维方法之一，该方法主要是用较少数量的特征对样本进行描述，以
达到降低特征空间维数的目的。该算法的原理是将一个高维向量x ，通过一个
特殊的特征向量矩阵U ，投影到一个低维的向量空间中，并表示为低维向量 y
，这仅仅损失了一些次要信息。也就是说，通过降维得到的低维特征向量不
但去掉了噪声信息，而且基本上保留了原始高维特征所描述的关键信息 。
从本质上讲，PCA 是一种空间映射的方法。将一个在二维坐标系中的变量
通过矩阵变换操作映射到另一个正交坐标系中，也就是将数据投射到一个低维
子空间实现降维。例如，二维数据集降维就是把平面上的点投射成一条线，数
据集的每个样本只需要用一个值就可以表示，不再需要两个值。三维数据集可
以降成二维，方法就是找到一个平面反映数据关系。一般情况?，n 维数据集
可以通过映射降成 k 维子空间，其中k≤n。
假如我们是一个摄影师，正在为一款鼠标产品拍摄?传图片。这款鼠标的
?传图片需要表达三个关键点：第一是商家的标志；第二是鼠标的滚轮；第三
是符合人体力学的手握设计。鼠标是一个三维的物体，而图片是一种二维的表
达方式，为了更全面地表达出鼠标的特点，我们需要从不同的角度拍照，尽量
还原鼠标的外观。以?是从不同角度拍摄的图片，如图10-5所示。

 

第一张图片能看到鼠标的侧面，但是看不到手握设计也看不到商家的标
志；第二张图片从上面拍，这次能看到商家的标志也能看到滚轮，但是依然看
不到手握设计；第三张图片从前面拍，这次能看到手握设计也能看到滚轮，但
是看不到商家的标志；第四张图片从侧方拍摄，这次终于能够展示出滚轮、标
志与手握设计。
PCA 算法的设计理念与这个例子十分相似。它可以将高维数据集映射到低
维空间，数据从原来的坐标系转换到新的坐标系，并且尽可能地保留较多有用
信息。PCA旋转数据集，让数据集尽量落到一个低维空间的过程在专业上称为
将数据集与其主成分对齐，保留变量到第一主成分中。假设有图10-6所示的数
据集。

 

以上数据集散落在一个二维平面中。要降低整个数据集的维度，我们必须
把数据点映射成一条直线。图10-7中的4条直线表示不同的映射关系，映射到
哪条线最为合适呢？

 

在通常情况?，我们所采用的方式是让原始数据在转换之后，相距尽量
大，也就是数据差异性最明显。两种映射方式都会不同程度地丢失数据点之间
的距离关系，图中d线丢失的数据关系要比c线多，因此c线才是更合适的映射
关系。在信号处理领域，普遍认为信号具有较大的方差，噪声有较小的方差。
信噪比就是普通信号与噪声的方差比，越大越好。我们认为，最好的k维特征
是将n维样本点变换为k维后，让每一维上的样本方差尽可能大。c线是原始数
据中方差最大的方向，而以这些方向所表示出的数据特征被称为“主成分”
。
怎么求出这些主成分呢？由线性代数的知识可知，通过数据集的协方差矩
阵及其特征值分析，就可以求得这些主成分的值。一旦得到协方差矩阵的特征
向量，就可以保留最大的N个值。然后可以通过把数据集乘以这N个特征向量将
它们转换到新的空间。在这里我们简单介绍一?方差、协方差与协方差矩阵这
三个数学概念。
● 方差：方差是衡量随机变量或一组数据离散程度的量。
● 协方差：协方差是指属性与属性间的相关程度，就是一个值变化时，
另一个值发生多大变化。
● 协方差矩阵：由数据集中两两变量的协方差组成的计算矩阵。
至此，我们得到了PCA降维的目标：将一组n维向量降为k维（0<k<n），其
目标是选择k个单位正交基，使得原始数据在变换到这组基上时，各字段两两
之间的协方差为0，而各字段之间的方差尽可能大。 于是我们可以总结PCA算
法的主要步骤，如图10-8所示。

 

（1）数据标准化处理。求每个属性的均值，然后将整个矩阵减去均值，
为计算协方差做准备。
（2）计算数据的协方差矩阵。
（3）计算协方差矩阵的特征值和特征向量。
（4）选择与前k个最大特征值对应的特征向量，其中k为新的特征子空间
的维度。通过对特征值进行排序，获取前k个特征值。计算单个方差的贡献和
累计方差的贡献，方差贡献率是指单个特征值与所有特征值和的比值。
（5）通过前k个特征向量构建转换矩阵W ，并且将k维数据通过转换矩阵W
映射到d维空间上。

10.3.2 PCA的特点与作用
由上述过程可看出，PCA 不仅仅是将数据从高维转换到低维那么简单，它
还可以消除评估指标之间的相关影响。PCA 对原始指标变换后形成了彼此相互
独立的主成分，实践表明，指标间相关程度越高，算法降维的效果越好。一般
情况?，如果把所有的样本点都映射到一起，那么几乎所有的信息都丢失了，
因为样本点都揉成了一团，看不出样本之间的差异。但是如果映射后方差很
大，数据点则会分散开来，以此来保留更多的信息。因此可以证明，PCA 是丢
失原始数据信息量最少的一种线性降维方式。
同时PCA也能够减少指标选择。其他的评估方法由于难以消除评估指标间
的相关性影响，所以需要做不少这方面的试验。而PCA直接消除了这种相关影
响，在指标选择上更简单。并且PCA是无监督学习算法，完全无参数限制。PCA
的计算过程完全不需要人为地设定参数或根据任何经验对计算结果进行干
预，最后的结果只与数据相关，与模型选择无关 。
诚然，这是PCA的优点，但是从某种程度上来说这也成了PCA算法最大的缺
点。如果用户对观测对象已经有一定的先验知识，掌握了数据的一些特征，?
无法通过参数化等方法对处理过程进行干预，那么可能会得不到预期的效果，
运算效率也会因此降低。在使用PCA时，首先应保证所提取的前几个主成分的
累积贡献率达到一个较高的水平，即变量被降维后信息量必须保持在一个较高
水平上。其次这些主成分必须能够给出符合实际业务含?的解释，否则主成分
将缺失有效信息或空有信息而无实际含?。
PCA 算法最著名的应用是在人脸识别中的特征提取及数据降维。一幅 200
像素×200像素大小的人脸图像，仅提取它的灰度值作为原始特征，这个原始
特征将达到40 000维。这给后面分类器的处理带来很大的难度。许多著名的人
脸识别算法就是采用PCA的方式，用一个低维子空间描述人脸图像，同时又保
留了识别所需要的信息。图10-9显示了一个PCA图像降维的例子。         

在实际项目中，通过PCA降维，产品经理更容易发现数据之间的关系。在
金融领域，用户购买某个理财产品需要经过诸多环节，主要有注册、风险?受
评估、条款告知、封闭期告知、转入资金这几个任务。我们可以收集100名用
户在购买理财产品时，在各个任务上花费的时间和整体任务失败率，以此分析
这款产品的易用性以及用户转化率。通过PCA降维，我们可以将以上五个维度
的数据转换为一个维度，然后再绘制散点图寻找其中的规律，或者将降维后的
数据再通过聚类的方法集合成不同类别，达到用户分群的目的。这种分群方式
相较以往以年龄段、收入等外部特征为分类依据显得更为准确。
值得注意的是，PCA 不适合用于高阶相关性的数据，只适合用于线性相关
的数据。但对于一般的人脸识别、用户行为估计分析或者网页埋点分析，PCA
已经能应对绝大多数情况。如果存在高阶相关性的数据，则可以考虑采用核主
成分分析，通过核函数先将非线性相关数据转换为线性相关数据，这个方法与
SVM求解非线性相关的数据时采用的方法原理相同，在此我们不再展开?述。
10.4 线性判别分析法
LDA原理
线性判别分析（Linear Discriminant Analysis，LDA）也是目前常用的
数据降维方法之一，它与PCA降维最大的不同在于，LDA是一种“有监督学习算
法”。LDA的核心思想是将高维的数据样本映射到低维向量空间中，以达到抽
取分类信息和压缩特征空间维数的目的，映射后保证数据样本在新的子空间内
有最大的类间距离和最小的类内距离，即数据在该空间中有最佳的可分离性。
也就是说，LDA 是一种带有分类结果的升级版PCA降维 。
PCA 是一种无监督的数据降维方法，它不关心类别标签，而是致力于寻找
数据集中最大化方差的方向。而LDA是一种有监督的数据降维方法，它计算的
是另一类特定的方向，这些方向刻画了最大化类间区分度。即使我们的训练样
本带有类别标签，但在使用PCA模型的时候，是不需要用到类别标签的，而LDA
在进行数据降维的时候，需要使用样本的类别标签。
上面这两段定?我们可以从几何的角度去理解。从几何的角度看，PCA和
LDA都是把数据投影到新的相互正交坐标轴上的方法。两者的区别在于，投影
的目标不同。PCA 只需要将样本投影到方差最大的相互正交方向上即可，这样
做可以尽可能保留最多的样本信息。样本的方差越大，表示样本越多样，降维
后保留的信息越多。因此在训练模型时，我们希望数据之间的差别越大越好，
否则即使得到的样本很多，但它们提供的信息都是无用的或是重复的，相当于
只有很少的样本提供了有效信息。这两种不同的设计思路在不同场景?各有所
长，例如图10-10所示的这种数据集。
对于这个样本集，通过PCA的方法可以找到一个最佳的投影方向，降维后
依然清?地描述了数据的分布趋势。投影后若数据方差最大，则保留的信息最
多。但是对于另外一些不同分布的数据集来说，PCA 这个投影后方差最大的特
点就不太好了。如图10-11所示的数据集。

 

 

对于这个数据集，如果继续使用PCA算法，我们在降维时依旧选择方差最
大的方向作为投影方向。PCA 算法得出的投影方向是图中直线所示的方向，此
时直线方差最大。但从图中可以看出来，这样投影之后，两类样本被混合在一
起了，数据不再可分，这不是我们想要的结果。
如果投影后的直线如图10-12所示，则使用这条直线做投影即能达到数据
降维的目的，并且还能保证两类数据依然可分。实际上，这条直线就是使用
LDA降维后找到的投影方向。仔细观察这条直线就会发现，这条线使得投影后
的同类样本能够互相分开。这也是LDA降维的目标。将带有标签的数据降维、
投影到低维空间，同时需要满足以?三个条件：
（1）尽可能多地保留数据样本的信息，选择对应的特征向量所代表的方
向。
（2）寻找使样本易分的最佳投影方向。
（3）投影后使得同类样本之间的距离尽可能近，不同类样本之间的距离
尽可能远。
LDA的核心思想可以用一句话概括，就是“投影后类内方差最小，类间方
差最大”，也就是说我们要将数据在低维度上进行投影，投影后希望每一种
类别数据的投影点尽可能地接近，而不同类别的数据的类别中心之间的距离
尽可能远。

LDA 的特点使得其既能完成分类任务又能解决降维问题，但更多的时候我
们希望在保持原有类别特点的基础上实现降维，构建新的数据特征。假设原有
数据样本类别为C，则LDA降维后一般会生成C-1个维度，例如样本数据有苹果
和香蕉两类图片，每个图片有10 000维特征，经过LDA降维之后，只有1维特
征，并且这个维度的分类效果最好。
LDA 降维在实现上并不复杂，主要是计算类间、类内的散度矩阵，过程比
较烦琐，这里不再展开?述。值得注意的是，LDA 对数据的分布做了很强的假
设，例如每个类的数据都符合高斯分布，各个类的协方差相等。虽然很可能实
际数据并不满足这些强假设，但是依然不妨碍LDA的使用。在很多场景下LDA已
经被证明是非常有效的降维算法，其中最主要的原因在于线性模型对于噪声
的鲁棒性比较好，不容易过拟合 。并且LDA在分类样本信息时依赖均值而不是
方差，这一点比PCA之类的算法表现更为优秀。通常来说LDA作为一个独立的算
法存在，给定了训练数据后，将得到一系列的判别函数。后面对于新的输入数
据，就可以进行预测了。而PCA更像是一个预处理的方法，它可以将原本的数
据维度降低，使得降低维度后的数据之间方差最大。
LDA 算法现已被广泛应用于人脸识别、生物医学图像研究、宏观经济调控
分析等不同领域。在人脸识别中，每一张图像都由大量的像素点组成，LDA 的
主要作用是把特征的数量降到可处理的量级后再进行分类，使得每一个新的维
度都是模板里像素值的线性组合。
10.5 流形学习算法
降维算法中还有一种比较特殊的算法被称为“流形学习算法”（Mani?old
Learning，也称流行学习），它是一种非线性降维方法。在流形学习的概念
中，假设某些高维数据，实际是以一种低维的流形结构嵌入在高维空间中。由
于数据内部特征的限制，一些高维数据会产生维度上的冗余，实际上只需要比
较低的维度就能表示。流形学习的目的是将高维数据映射回低维空间，找到
这种低维的“流形”结构，以便于更清楚地解释其本质 。
看到这里可能很多读者会充满疑问，什么是“流形”呢？流形其实很好理
解，就是指一般的几何对象的总称，其包含了具有各种维数的曲线曲面。例如
我们常见的一条直线或一条曲线就是一维流形，球面就是一个三维流形。和一
般的降维分析一样，流形学习的目标也是将一组高维空间中的数据映射到低维
空间中来重新表示。和其他方法的不同点在于，流形学习做了一个假设，就是
所处理的数据样本都在一个潜在的流形上，或者说对于这组数据存在一个潜在
的流形。不同形态的流形有不一样的性质，需要用不同的方法解决，因此也诞
生了很多流形学习的派系。
首先我们用一个例子直观地解释什么是流形学习。假设我们在一张纸上画
了一个圆形，如果想要描述这个圆形里某两个点之间的关系，我们可以再在纸
上画一个平面直角坐标系，那么这个圆形里的点都可以用二维点表示，如图
10-13所示。

 

从图中可以看到，点(1,1)、(1,2)都在圆形里，但是还有像(1,5)、(5,3)
等大量的点都不在圆形内。如果我们用平面直角坐标系来表示这个圆形，则会
产生大量冗余的数据，因为我们没有办法让这个坐标系上所有的点都落在这个
圆形内。
在理想情况?，我们希望有一种描述方法，这个描述方法所描述的所有点
都在圆内。恰好在数学上有这么一个方法能够满足我们的需求，即极坐标系。
如图10-14所示，在平面上取一定点，该定点称为极点，由极点出发的一条射
线称为极轴，再取一个长度单位。这样圆形上任一点的位置都可以被表示出来
并且没有任何冗余的数据。

 

前文提到，流形学习认为高维数据实际是以一种低维的流形结构嵌入在高
维空间中。由于数据内部特征的限制，一些高维数据会产生维度上的冗余，实
际上只需要比较低的维度就能唯一地表示这些数据。流形学习的目的是将其映
射回低维空间，以便于更清楚地解释其本质。对应到这个例子中也就是说，实
际上一个圆形用极坐标表示就完全足够了，但是如果用平面直角坐标系来表示
就会产生大量的冗余点，我们希望通过流形学习能够将数据回归成低维。流形
学习相比前面的PCA、LDA而言，最大的不同在于它是一种非线性降维方式，非
线性降维因为考虑到了流形的问题，所以在降维的过程中不但考虑到了距离，
同时也考虑到生成数据的拓扑结构。
我们来看看，为什么PCA、LDA这类算法不适合解决非线性样本集。以PCA
为例，PCA以方差的大小来衡量信息的量级。PCA认为方差正比越高，数据提供
的信息量越大，其基本思想是通过线性变换尽可能地保留方差大的数据。如果
用PCA算法对“环形”数据集进行降维，则很可能得到如图10-15所示的结果。

 

假设在“环形”数据集上有 A、B两点，经过 PCA降维后两点之间的“距
离”非常近，并且两点的方差相近，这时它们可能会被认为是同一类型的数
据。但是如果将原本的“环形”结构展开来看，会发现实际上A、B两点的间隔
非常远。由此可以看出，用传统的降维方法很容易抛弃数据的内部特征，如果
测量一个曲线上两个点的直线距离，会忽略这两个点在这个曲面上的事实。因
此，我们需要一种特殊的定?“距离”的方式。
在流形学习中有一种经典的方法称为等度量映射（Isomap）。该方法利用
流形在局部上与欧式空间同胚这个性质，对每个点基于欧式距离找出其最近邻
点，然后建立一个近邻连接图。于是计算两点之间的测地距离的问题，就转变
成为计算近邻连接图上两点之间的最短路径问题。简单理解就是计算邻近点之
间的以最短距离连接成的序列，如图10-16所示。要计算空间中远距离两点a与
g之间的距离，需要计算从a到b、从b到c……之间的距离，沿着路径依次类推
直到到达目的地g。

 等度量算法是全局算法，它要找到所有样本的全局最优解。当数据量很大
或者样本维度很高时，等度量算法的计算量非常大。因此在实际项目中更常用
的算法是局部线性嵌入（Locally Linear Embedding，LLE）算法，LLE放弃所
有样本全局最优的降维，只保证局部最优的降维。
LLE的核心思想是保持领域内样本之间的潜在关系。如图10-17所示，样本
从高维空间映射到低维空间后，各个领域内样本之间的线性关系不变。即样本
点x i 的坐标能通过它的领域样本 x j 、x l 、x k 重构出来，而这里的权值参数
在低维和高维空间是一致的。
除了 Isomap、LLE 这两种算法以外，流形学习领域还有很多不同的距离
测量方法，但它们的原理大致相同，在此不再逐个介绍。流形学习的解决思路
很美好，但是其最大的瓶颈就是计算复杂度太高，这点阻碍了流形学习在实际
项目中的应用。虽然流形学习对非线性数据有较好的降维效果，但如何有效降
低计算量，甚至推广其线性化算法一直是一个待解决的重要问题。线性化是很
好的方法，但是线性化以后对于高度的非线性问题一样束手无策。业界很多学
者一直在研究如何找到可处理非线性数据的线性化流形学习方法。

 

在处理分类问题时，多数情况?流形学习算法的性能较传统方法要差。因
为流形学习算法在恢复数据内部关系时采用了局部邻域思想，算法本身的稳定
性与邻域选择有关。另外，如果样本中的噪声较大，则降维后产生的投影偏差
可能较大。
目前在机器学习领域，多数算法还是属于“有监督学习算法”，这就要求
我们必须使用有标签的数据才能训练模型。然而在实际项目中还存在大量没有
标签的数据，这些没有标签的数据在模型训练时就被白白浪费掉了。这些数据
难道说没有标签就没有任何价值了吗？降维算法的意?除了简化计算复杂度，
快速挖掘数据间的关系以外，借助特定的降维算法，使我们对这些无标签数据
有更深入的认识，从而挖掘出有效信息，使这些信息与有标签数据互为补充，
这样才能对数据有更全面的分析，从而提升模型的应用效果。