学习了机器学习和模式识别之后发现两门课有一些相通的以及互补的地方，想总结一下。

一、k-近邻法：

（一）算法原理：在给定训练数据集中找到与待预测实例最近的k个训练实例，结合这k个训练实例的类别，采用多数投票法决定待预测实例的类别。

（二）基本要素：k值选择、距离度量、决策规则

1、k值选择：①选择奇数为佳。防止出现相同“票数”的情况，影响决策。②k值的大小可以类比于图像处理中的邻域大小。若k比较大，则选择的是较大的邻域，考虑全局信息，这样的话距离实例较远的训练实例也会对预测结果起作用，但实际上距离较远的训练实例与待预测实例已经没那么“相似”了，使得预测出错。若k比较小，则选择较小的领域，考虑局部信息，只有近的几个训练实例对分类结果起作用，同时也会使得预测结果对近邻点十分敏感，若近邻点恰好有噪声，则使得预测出错，也使得模型过拟合，因为模型对于近邻点的微小变化都很敏感，对近邻点有很强的依赖性。③使用交叉验证选择效果较好的k值。

当k=1是也称为最近邻算法，最近邻规则是真实概率的有效近似，因为在样本数N很大时，训练实例与预测实例可以看作无限接近，这时两者后验概率近似相等。此时的分类面是各相邻训练样本距离的垂直中心线，最近邻决策面是分段线性的。最近邻是次优方法，误差率比贝叶斯误差率大。

2、距离度量：在knn算法中，样本特征之间差异主要通过特征之间的“距离”来体现，距离体现了他们之间的相似性。

（1）欧氏距离：最常见的距离度量，衡量空间中各个点之间的绝对距离。有量纲，不考虑变量之间的相关性。

（2）马氏距离：考虑了各自变量间的线性相关关系，根据协方差矩阵消除了相关性。不受量纲影响，两点间的马氏距离与原始数据的测量单位无关。

（3） 曼哈顿距离：

（4）切比雪夫距离：

【注意】由不同距离度量所确定的最近邻点是不同的。

3、决策规则：多数投票法，即测试样本的类别由其个近邻样本中类别数最多的类决定。

, 则决策 

有了近邻数、相似度度量准则以及决策规则就可以对待预测样本进行计算，然后根据计算结果决策分类了。对于任何一个输入实例，其所属的类唯一确定，因此近邻法的决策过程相当于根据这三个要素将特征空间划分为一些子空间，然后确定子空间里每个点所属的类。

（三）一些改进方法：

k近邻算法每预测一个样本点的分类都会重新进行一次全局运算，对于样本容量大的数据集计算量比较大，因此有一些旨在减小计算量的改进算法。这里以最近邻算法的改进为例。

1、快速算法：

（1）基本思想：将样本分级得到一些不相交的子集，在子集的基础上进行搜索。

（2）基本方法：

①样本分级分解得到树结构，求出样本子集中的样本均值，以及从到的最大距离，如下图所示：（其中是当前与其最近邻样本间的距离）

②对分级得到的树结构，基于如下两个准则进行搜索：

A. 若，则说明以为原点，以为半径的圆与以为原点，以为半径的圆不相交，与中心离得太远，不是的最近邻。

B. 针对最后一层节点，若，则不是的最近邻，然后将剔除，这样可以避免把最后一层的所有节点都计算一遍距离

我认为这个方法的精髓在于每次删掉的都是包括了许多样本的一个节点，从而对最近邻进行“筛选剔除”，进而减少计算量。

2、剪辑近邻法：

（1）基本思想：处在两类交界处或分布重合区的样本可能会影响近邻法的决策，应将他们从样本集中去掉。

（2）基本方法：

①将样本集分为和两个子样本集，且

②用对进行近邻法分类，去掉中被错分的样本，其剩余的样本构成新样本集

③用新样本集和近邻法对未知样本进行分类

【简言之，把边界上的样本区分开】

3、压缩近邻法：

（1）基本思想：远离分类边界的样本（比如靠近中心的样本）对最后的分类决策没有用处，因此只要找出各类样本中最有利于用来与其他类别区分的代表性样本，就可以简化计算。

（2）基本方法：

①将样本集分为和，开始时中只有一个样本，中为剩余样本

②对中每个样本，若用可正确分类则保留，否则移入，说明现有的不能达到好的分类效果，需要增添样本

③用作为最近邻法的数据集

【简言之，挑选最有利于分类的样本】

法二、法三实际上是对数据集大小进行修改，减少数据样本从而减少计算量；法一是从对“可能的最近邻进行筛选”这个角度入手，对计算量进行缩减。