机器学习

代码连接：

https://github.com/wumingyao/ML.git

决策树算法

基于树结构来进行决策(分类)的。

• 基本流程：

根据一个事物的不同属性来对事物进行划分。

举例：

“这是好瓜吗？”

“它的颜色是青绿色的、根蒂是蜷缩的、敲声是......，所以结论是：这是个好瓜”。

通过西瓜的不同属性来区分好瓜还是坏瓜。

• 划分选择

决策树学习的关键就是如何选择最优划分属性，也就是找到上面图中为什么要选择“色泽”属性作为根节点的理由，以及在接下来的划分中，为什么要选择该划分属性的理由。

信息增益

                            式（1-1）

式1-1用于计算随机变量的熵， 熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后样本集合熵的差值来衡量使用当前属性对于样本集合D划分效果的好坏。（使用这个属性划分样本之后，样本是不是更加确定了）

      HY|X=x∈XnPxH(Y|X=x)                 式（1-2）

式1-2用于计算在X取一定值的情况下随机变量Y不确定性的度量，即随机变量Y的条件熵，划分后的样本集合熵。

                                  式（1-3）

式1-3是在式1-1和式1-2的基础上计算随机变量的信息增益， 表示随机变量Y在X的作用下(y在x的划分下)集合的熵的差值，该差值即信息增益。

举例: 关于得病与否,计算age属性的信息增益，在14个样本中，yes=9个，no=5个。

划分前集合熵：H(Y)=-(9/14*log(9/14)+5/14*log(5/14))= 0.940286

划分后集合熵：H(Y|X)=5/14*0.97095+4/14*0+5/14*0.81=0.57856

信息增益：G(Y,X)=H(Y)-H(Y|X)= 0.361726

缺点：信息增益偏向取值较多的特征

1. 信息增益比

                                          式（1-4）

• 剪枝处理

剪枝是决策树算法对付“过拟合”的主要手段，通过主动去掉一些分支来降低过拟合的风险。根据泛化性能是否提升来判断和评估要不要留下这个分支。

1. 预剪枝

是否应该进行这个划分？预剪枝要对划分前和划分后的泛化性能进行估计。划分后的验证集精度如果比划分前的验证集精度高，那么，就决定划分，否则，预剪枝策略禁止这个结点被划分。

1. 后剪枝

后剪枝先从训练集上生成一棵完整的树，从最后一个分支来判断要不要剪枝。下面是根据训练集生成的一整棵树：

• 连续值处理

以上的属性值都是离散的，现实中通常会遇到连续的属性值。这个时候，可以使用连续属性离散化技术，C4.5决策树算法采用的是最简单的策略二分法来对连续值进行处理。考虑密度的属性，首先把不同样本的密度值按照从小到大排序，然后找到候选划分点，把每个候选划分点的信息增益算出来，取max的值作为密度的信息增益。第二次max就是找到最优划分属性了。

 

神经网络

目的：

           对自然界的某种函数的逼近。例如：一张图片和该图片的语义（即该图片的内容）之间是一种函数关系，只要能找到这个函数，机器就能识别一张图片内容。

    支撑点：

           能力+效率

 

/*********************************分割线******************************************/

如何模拟出这个函数呢？

       原理：可以对输入数据进行不同角度的分析，能得到对客观事物整体的认识。

 

       线性部分：w*x+b=z

       因为每个角度对认识事物的贡献值不同，因此需要有个权重w来衡量，同时需要偏置量b来调整该“线性函数“的位置，从而拟合目标函数。

      

       非线性部分/激活函数（必要性）：

       1、处理非线性模型。激活函数给神经元引入了非线性因素，使得神经网络可以任意逼近任何非线性函数，这样神经网络就可以应用到众多的非线性模型中。

2、进行数据归一化。想让y^表示实际值y等于1的机率的话,那么y^的取值应该是（0，1）

 

       线性部分+非线性部分：神经元/感知器。

       神经网络其实就是按照一定规则连接起来的多个神经元

 

网络架构：能力+效率

       为了提高该网络的表达能力，即模拟目标函数的能力，需要从两方面来考虑：

       1、增加神经元个数

       2、增加隐层数，如果是线性模型，只需一层就够了。

       从表达能力来讲，我们希望有效的神经元个数和有效的隐层数越多越好，但是这样意味着训练的w和b就越多，学习时间越长。

 

如何衡量该网络架构模型的能力呢？

       损失函数：每个样本的计算值和目标值的误差;

       代价函数是对m个样本的损失函数求和然后除以m;

       我们用代价函数表征该模型能力，总代价越小，能力越强，所以在训练模型时候，就是要找到合适的w和b，来让代价函数的总代价降到最低。

 

    如何提高该模型的学习效率？

       我们的目标是找到代价函数的最小值，且以较快的速度；

       函数在某点沿着梯度方向下降最快，因此我们需要知道当前在哪一点（正向传播），需要知道该点的梯度，即J对个变量的偏导（反向传播）。

      

 

/*********************************分割线******************************************/

 

卷积神经网络CNN：如何提高表达能力、学习效率

    问题：

       在图像识别任务中，如果使用全连接神经网络，会有以下几个方面的问题：

       1、参数数量太多

       2、没有利用到图像空间上的局部相关性

例如我们想要做一个房价预测，我们选取面积、卧室个数、邮政编码等作为特征，如果以同样的方法去识别图片，把每一个像素点的像素值作为我们的选取特征，每个像素点都有一个权值w,会有大量的参数，并且每个像素点是孤立的，并没有利用到图像空间上的局部相关性。

       3、网络层数限制

    解决：

       1、减少参数

          参数共享：特征检测如垂直边缘检测如果适用于图片的某个区域，那么它也可能适用于图片的其他区域。

          稀疏连接:  进行局部连接，每个神经元不再和上一层的所有神经元相连，而只和一小部分神经元相连。这样就减少了很多参数。

 

       2、增加网络层数

          Relu函数作为激活函数，有效解决梯度消失问题

 

    结构：

       卷积层+池化层+全连接层

      

       卷积层：

f(输入图像*filter+b)=Feature Map

过滤器用来检测图像中特定的特征的，如果图像的某一区域与过滤器检测的特征很相似，那么当过滤器经过该区域时,就会激活该过滤器，得到一个很高的值，反之，如果图像的某一区域与过滤器检测的特征很不相似时,就不会激活该过滤器或者得到的数值很低。

Feature Map反映的就是该特征在原图片的位置分布。

 

       池化层:

       Pooling层主要的作用是下采样，通过去掉Feature Map中不重要的样本，提取主要特征，进一步减少参数数量。

 

全连接层：

            连接所有的特征，得到输出值

 

/*********************************分割线******************************************/

循环神经网络RNN：处理序列模型，如何提高表达能力

 

    问题：

       以语音转文本为例，对于每个词，单单从该单词语音的各个角度数据进行分析，如音频、音幅、音高、响度等，来识别该单词可不可以呢？当然是可以的，但是我们发现对于某个词的识别，不仅可以从单词本身的发音进行推测，也能根据上下文推测，例如当前推测的单词可能是“言”、“盐”等，如果上一个词是“语”,那么“言”的可能性要比“盐”的可能性要大的多。

 

    解决：

       把上下文信息也作为推测该词的因素。

 

    结构：

       输入：语音Xt+上文St-1，St=f(UXt+WSt-1+b)

       输出：o=g(VSt)

 

/*********************************分割线******************************************/

长短时记忆网络LSTM：效率

    问题：

       RNN认为经过处理的信息对接下来的信息有影响,所以之前处理过的全都抛给接下来处理的程序，这样一来会造成梯度消失，使学习效率变低，所以RNN对短期的信息比较敏感，但对较前面的信息记不住

    解决：

       不能再像RNN那样把前面的信息都记住了，提取重要的信息

       增加一个状态c，让它来保存长期的关键信息

 

    结构：

       输入：语音Xt+短期ht-1+长期Ct-1

       输出：ht、Ct

     对于两种时态信息, LSTM是如何提取重要信息的呢?

        LSTM通过门来“提取”这两种时态的信息， 通过“门”结构来去除或者增加信息到细胞状态。门是一种让信息选择式通过的方法。他们包含一个 sigmoid神经网络层和一个按位的乘法操作。

        遗忘门：决定了上一时刻的Ct-1有多少保留到当前时刻Ct

        输入门：决定了当前时刻的输入Xt有多少保存到当前时刻Ct

         遗忘门+输入门举例：当前输入新的主语“它”，Ct就会把之前的主语“他”“遗忘”掉，”记忆“新的主语”它“

        输出门：控制当前时刻的Ct有多少输出到LSTM的当前输出值ht，即t 时刻的状态信息

 

对LSTM的疑问：

       1、梯度消失为何不用RELU函数，而要大费周章使用门设计出这么麻烦的结构？

       2、LSTM的门是如果解决梯度消失问题的？

 

。

支持向量机

基本思想可概括如下：首先，要利用一种变换将空间高维化，当然这种变换是非线性的，然后，在新的复杂空间取最优线性分类表面[8]。由此种方式获得的分类函数在形式上类似于神经网络算法。支持向量机是统计学习领域中一个代表性算法，但它与传统方式的思维方法很不同，输入空间、提高维度从而将问题简短化，使问题归结为线性可分的经典解问题。支持向量机应用于垃圾邮件识别，人脸识别等多种分类问题。

贝叶斯分类器

朴素贝叶斯算法

朴素贝叶斯算法是一种分类算法。它不是单一算法，而是一系列算法，它们都有一个共同的原则，即被分类的每个特征都与任何其他特征的值无关。朴素贝叶斯分类器认为这些“特征”中的每一个都独立地贡献概率，而不管特征之间的任何相关性。然而，特征并不总是独立的，这通常被视为朴素贝叶斯算法的缺点。简而言之，朴素贝叶斯算法允许我们使用概率给出一组特征来预测一个类。与其他常见的分类方法相比，朴素贝叶斯算法需要的训练很少。在进行预测之前必须完成的唯一工作是找到特征的个体概率分布的参数，这通常可以快速且确定地完成。这意味着即使对于高维数据点或大量数据点，朴素贝叶斯分类器也可以表现良好。

EM（期望最大化）算法

在进行机器学习的过程中需要用到极大似然估计等参数估计方法，在有潜在变量的情况下，通常选择EM算法，不是直接对函数对象进行极大估计，而是添加一些数据进行简化计算，再进行极大化模拟。它是对本身受限制或比较难直接处理的数据的极大似然估计算法 

集成学习

集成学习（ansemblelearning）通过构建并结合多个学习器来完成学习任务，也称为多分类器系统（multi-classifiersystem）、基于委员会的学习（committee-based learning）。

举例

在二分类任务中，假定三个分类器在三个测试样本的表现如图2，其中，√ 表示分类正确，× 表示分类错误，集成学习的结果通过投票法产生，即“少数服从多数”。在图2(a)中，每个分类器只有66.6%的精度，但集成学习却达到了100%。多个弱学习器集成起来做决策形成一个强学习器。

一、Boosting(AdaBoost、GBDT、XGBoost)

Boosting是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续收到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数达到事先指定的值T，最终将这T个基学习器进行加权结合。简单来说，就是基于同一训练集和同一个算法训练出T个基学习器，每一轮训练都针对上一轮的训练结果调整样本分布。

1. AdaBoost

对于这个算法需要介绍的是：

(1)算法开始前，需要将每个样本的权重初始化为1/m,这样一开始每个样本都是等概率的分布，每个样本分类器都会公正对待。

(2)开始迭代后，需要计算每个弱分类器的分类错误的误差，误差等于各个分错样本的权重和，这里就体现了样本权重的作用。如果一个分类器正确分类了一个权重大的样本，那么这个分类器的误差就会小，否则就会大。这样就对分类错误的样本更大的关注。

(3)获取最优分类器后，需要计算这个分类器的权重，然后再更新各个样本的权重，然后再归一化。

(4) 算法迭代的次数一般不超过弱分类器的个数，如果弱分类器的个数非常之多，那么可以权衡自己性价比来折中选择。

(5) 迭代完成后，最后的分类器是由迭代过程中选择的弱分类器线性加权得到的。

 

1. GBDT(Gradient Boosting Decision Tree：梯度提升决策树)

GBDT是一种基于boosting集成学习（ensemble method）的算法，但和传统的Adaboost有很大不同。在Adaboost，我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同, 其是通过不断迭代拟合样本真实值与当前分类器的残差y−yˆhm−1​​来逼近真实值的。GBDT的训练过程如下：

把所有树的结论累加起来做决策

举例：

假设小明的年龄是20岁，我们通过训练第一个弱分类器（目标值是20）得到预测结果比如是11岁，那么差值（残差）是9岁，那么在训练下一个弱分类器将9作为目标值，假如第二个弱分类器预测的结果是12，那么差值（残差）是-3岁，那么在训练第三个弱分类器将-3作为目标值，假如正确预测即-3。

那么最终预测结果便是三个弱分类器预测结果线性组合即相加11+12-3=20

每一棵树学的是之前所有树的残差，这个残差累加后能得到真实值。

回归问题提升树使用以下前向分布算法：

fm(x)代表的就是前m个弱分类器预测结果的累加值。

在前向分布算法的第m步，给定当前模型，需求解

是第m棵树的参数。

L代表的是损失函数,可以采用平方误差损失函数

则上面损失函数变为：

问题就成了对残差r的拟合了

用损失函数的负梯度来拟合本轮损失的近似值，即r约等于

在数学中代表的含义是求变量q使得f(x,q)最小，是一个最优化求参数问题。

步骤1：是一个初始化求的过程，公式的意思就是说，求一个，然后其分别和各个目标值带入到损失函数L中，使得总体损失最小，其实这里只是为了使得给出的算法更具普遍性才写的这么复杂，大多数的时候这里的就取所有的平均值。

步骤2：这里就是一个for循环，M代表的就是一共要生成M个弱分类器即最终的强分类器是由M个弱分类器线性组合而成的

步骤3：这里就是求负梯度值了，随着L函数的不同，所求出的结果也是不尽相同，比如：

                

                

步骤4：这里其实就是训练当前这一个分类器h，该树以x作为输入数据，以步骤3求得的负梯度值为拟合目标，然后训练得到构造该树的参数。

步骤5：该步骤的目的就是训练得到模型相加时权值，Boosting模型不是将多个弱分类器线性相加嘛，比如a,b,c就是系数对吧，其实就是这里的a,b,c，大多时候这里的可以看成是训练模型时需要一个调的一个超参数即学习率。

步骤6：就是更新得到第m次的值，即前m颗树预测值的线性累加和。

 

1. XGBoost

XGBoost的核心算法：

(1)加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数f(x)，去拟合上次预测的残差。

(2)当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数

(3)最后只需要将每棵树对应的分数加起来就是该样本的预测值。

GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开。

二、bagging

Bagging（bootstrap aggregating）采用的是随机有放回的选择训练数据构造分类器，最后组合。（一种根据均匀概率分布从数据中重复抽样（有放回）的技术）随机采样(bootsrap)就是从我们的训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。对于我们的Bagging算法，一般会随机采集和训练集样本数m一样个数的样本。这样得到的采样集和训练集样本的个数相同，但是样本内容不同。如果我们对有m个样本训练集做T次的随机采样，则由于随机性，T个采样集各不相同。

1. 随机森林

随机森林算法具体实现过程：

(1)从训练数据中选取n个数据作为训练数据的输入，一般情况下n是远远小于整体的训练数据N，这样就会造成有一部分数据是无法被去到的，这部分数据被称为袋外数据，可以使用袋外数据做误差分析。

(2)选取输入的训练数据后，构建决策树（方法：每一个分裂节点从整体的特征集M中选取m个特征构建，一般情况下m远小于M，通常是log2或者sqrt的数量），从这m个属性中根据某种策略（如gini减少或信息增益等）确定分裂属性。

(3)重复b步骤，直到不能分裂或达到我们设定的阈值（如叶子结点树或的树的深度），此时建立了一个决策树

(4)重复上面的(1)(2)(3)步骤，直到达到预定树的颗数为止。

 

随机森林有很多的优点：

a. 在数据集上表现良好，两个随机性的引入，使得随机森林不容易陷入过拟合。

b. 在当前的很多数据集上，相对其他算法有着很大的优势，两个随机性的引入，使得随机森林具有很好的抗噪声能力。

c. 它能够处理很高维度（feature很多）的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。

d. 在创建随机森林的时候，对generlization error使用的是无偏估计。

e. 训练速度快，可以得到变量重要性排序。

f. 在训练过程中，能够检测到feature间的互相影响。

g 容易做成并行化方法。

h. 实现比较简单。

 

聚类算法

一、原型聚类（k-means算法、学习向量量化LVQ、高斯混合聚类）

“原型”：代表着自身特征的形状，这里指样本空间中具有代表性的点。

原型聚类算法假设聚类结构可以通过一组原型刻画，通常算法选会对原型进行初始化，然后对原型进行迭代更新求解。不同的原型表示和不同的求解方式会产生不同的算法。下面主要介绍三种典型的原型聚类算法：k 均值、学习向量量化 和 高斯混合聚类。

1、K-means算法

“k均值”算法选定参数 k 将数据集划分为 k 个簇

算法步骤：

(1)随机初始化 k 个簇，随机选择 k 个样本作为 k 个簇的初始均值向量(中心点、原型向量)

(2)遍历所有数据，将每个数据划分到最近的簇中

(3) 对所有的簇集合，根据本次迭代得到的簇集合计算新的均值向量

(4)重复2-3，直到这k个均值向量不再变化（收敛了），或执行了足够多的迭代

 

2、学习向量量化算法

与 k 均值算法不同，学习向量量化（LVQ）的学习过程中会利用样本的类别信息，所以 LVQ 是一种监督式的聚类算法。其目标是学得一组原型向量，每一个原型向量代表一个聚类簇标记。

 

步骤12: 直至原型向量更新很小或者迭代次数到达上限为止。

通俗的解释：如果Pj与xi是同类的话（记住这里的类别是我们最初随机指定的），那就说明我们最初的指定是靠谱滴，他们两个确实距离近，所以我们要将原型向量Pj向xi移动，反之，如果他们两个不是一类，那么说明我们最初的假设不对，而他的距离确实最近的，所以那么我们就要将原型向量Pj向xi远离。

3、高斯混合聚类

二、密度聚类

密度聚类则是基于密度的聚类，它从样本分布的角度来考察样本之间的可连接性，并基于可连接性（密度可达）不断拓展疆域（类簇）。

1、DBSCAN

简单来理解DBSCAN便是：找出一个核心对象所有密度可达的样本集合形成簇。首先找出所有核心对象集合，从该集合任选一个核心对象A，找出所有A密度可达的样本集合，将这些样本形成一个密度相连的类簇，直到所有的核心对象都遍历完。

例子：

有一个样本D={x1, x2, x3, ……, x28, x29, x30, }，

DBSCAN算法先找出各样本的e-邻域并确定核心对象集合：Ω={ x3, x5, x6, x8, x9, x13, x14, x18, x19, x24, x25, x28, x29}，

然后从Ω中随机选择一个核心对象作为种子，找出它密度可达的所有样本，这样就构成了第一个聚类簇。

不失一般性，假设核心对象X8被选中作为种子，则DBSCAN生成的第一个聚类簇为C1={ x6, x7, x8, x10, x12, x18, x19, x20,x23}。

然后，DBSCAN将C1中包含的核心对象从Ω中去除: Ω={ x3, x5, x9, x13, x14, x24,x25,x28,x29}。

再从更新后的集合Ω中随机选取一个核心对象作为种子来生成下一个聚类簇.上述过程不断重复，直至Ω为空.最终结果如下：

C1={ x6, x7, x8, x10, x12, x18, x19, x20,x23}

C2={ x3, x4, x5, x9, x13, x14, x16, x17,x21}

C3={ x1, x2, x22, x26, x29 }

C4={ x24, x25, x27, x28, x30}

三、层次聚类

层次聚类是一种基于树形结构的聚类方法，常用的是自底向上的结合策略（AGNES算法）。假设有N个待聚类的样本，其基本步骤是：

(1).初始化–>把每个样本归为一类，计算每两个类之间的距离，也就是样本与样本之间的相似度；

(2).寻找各个类之间最近的两个类，把他们归为一类（这样类的总数就少了一个）；

(3).重新计算新生成的这个类与各个旧类之间的相似度；

(4).重复2和3直到所有样本点都归为一类，结束。

1、AGNES算法

AGNES是一种采用自底向上聚合策略的层次聚类算法，它先将数据集中的每个样本看作是一个聚类簇，然后再算法运行的每一步找出距离最近的两个聚类簇进行合并，该过程不断重复，直到达到预设的聚类簇个数。这里的关键是计算聚类簇之间的距离：

降维与度量学习

样本的特征数称为维数（dimensionality），当维数非常大时，也就是现在所说的“维数灾难”，具体表现在：在高维情形下，数据样本将变得十分稀疏，因为此时要满足训练样本为“密采样”的总体样本数目是一个触不可及的天文数字，谓可远观而不可亵玩焉…训练样本的稀疏使得其代表总体分布的能力大大减弱，从而消减了学习器的泛化能力；同时当维数很高时，计算距离也变得十分复杂，甚至连计算内积都不再容易，这也是为什么支持向量机（SVM）使用核函数“低维计算，高维表现”的原因。

缓解维数灾难的一个重要途径就是降维，即通过某种数学变换将原始高维空间转变到一个低维的子空间。在这个子空间中，样本的密度将大幅提高，同时距离计算也变得容易。这时也许会有疑问，这样降维之后不是会丢失原始数据的一部分信息吗？这是因为在很多实际的问题中，虽然训练数据是高维的，但是与学习任务相关也许仅仅是其中的一个低维子空间，也称为一个低维嵌入，例如：数据属性中存在噪声属性、相似属性或冗余属性等，对高维数据进行降维能在一定程度上达到提炼低维优质属性或降噪的效果。

一、KNN(K近邻学习)

 

k近邻算法简称kNN（k-Nearest Neighbor），是一种经典的监督学习方法，同时也实力担当入选数据挖掘十大算法。其工作机制十分简单粗暴：给定某个测试样本，kNN基于某种距离度量在训练集中找出与其距离最近的k个带有真实标记的训练样本，然后给基于这k个邻居的真实标记来进行预测，类似于前面集成学习中所讲到的基学习器结合策略：分类任务采用投票法，回归任务则采用平均法。

图中有两种类型的样本，一类是蓝色正方形，另一类是红色三角形。而那个绿色圆形是我们待分类的样本。基于kNN算法的思路，我们很容易得到以下结论：

如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形。

如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形。

可以发现：kNN虽然是一种监督学习方法，但是它却没有显式的训练过程，而是当有新样本需要预测时，才来计算出最近的k个邻居，因此kNN是一种典型的懒惰学习方法，再来回想一下朴素贝叶斯的流程，训练的过程就是参数估计，因此朴素贝叶斯也可以懒惰式学习，此类技术在训练阶段开销为零，待收到测试样本后再进行计算。相应地我们称那些一有训练数据立马开工的算法为“急切学习”，可见前面我们学习的大部分算法都归属于急切学习。

很容易看出：kNN算法的核心在于k值的选取以及距离的度量。k值选取太小，模型很容易受到噪声数据的干扰，例如：极端地取k=1，若待分类样本正好与一个噪声数据距离最近，就导致了分类错误；若k值太大， 则在更大的邻域内进行投票，此时模型的预测能力大大减弱，例如：极端取k=训练样本数，就相当于模型根本没有学习，所有测试样本的预测结果都是一样的。一般地我们都通过交叉验证法来选取一个适当的k值。

二、“多维缩放”（MDS）

维数灾难

要求原始空间中样本之间的距离在低维空间中得以保持。

当样本数量一定时，随着特征维数的增加，样本在维数空间中的密度越来越小，数据样本将变得十分稀疏，因为此时要满足训练样本为“密采样”（样本密度足够大）的总体样本数目是一个触不可及的天文数字，训练样本的稀疏使得其代表总体分布的能力大大减弱，从而消减了学习器的泛化能力。