1. 概述
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。
K近邻法（k-NN）是一种分类与回归的算法。
优点：简单，直观，训练时间开销为0，待收到测试样本后再进行处理
思路： 给定一个训练集，对新输入的实例，在训练数据集中找到与该实例最邻近的K个实例。采用少数服从多数的方法，寻找实例所在的类。
1.1. 适用范围
- 类域的交叉或重叠较多的样本
KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。 该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
实现 K 近邻算法时，主要考虑的问题是如何对训练数据进行快速 K 近邻搜索，这在特征空间维数大及训练数据容量大时非常必要。
K近邻算法：（没有显式的学习过程）
input ：训练集 $T={(xi,yi) |i=1..n}$，预测集 实例x。
output ：实例x的分类y
步骤：
- 由距离度量找到T中与x最近的k个点，（k的个数可以由交叉验证确定）
- 多数表决法，k个点中那个类别的点多，x就被分为哪一类
注意：不同距离度量（具体距离算法在聚类中有详细介绍）所确定的最近邻点会有所不同
2. 如果寻找最近的k个点？
2.1. 怎么评价最近--距离描述
Metrics intended for real-valued vector spaces:
identifier
class name
args
distance function
“euclidean”
EuclideanDistance
sqrt(sum((x - y)^2))
“manhattan”
ManhattanDistance
sum(|x - y|)
“chebyshev”
ChebyshevDistance
max(|x - y|)
“minkowski”
MinkowskiDistance
p
sum(|x - y|^p)^(1/p)
“wminkowski”
WMinkowskiDistance
p, w
sum(|w * (x - y)|^p)^(1/p)
“seuclidean”
SEuclideanDistance
V
sqrt(sum((x - y)^2 / V))
“mahalanobis”
MahalanobisDistance
V or VI
sqrt((x - y)' V^-1 (x - y))
2.2. 怎么找--kd树
（k近邻实现的线性扫描）
构造根节点，使根节点对应于k维空间中所包含的实例点的超矩形区域。通过递归的方法，不断对k维空间进行切分成子节点。
构造平衡的kd树：
依次选择坐标进行切分，选择训练的实例点，在选定的坐标轴上的中位数为切分点，向坐标轴做垂线。
搜索kd树
优点：省去对大部分数据的搜索，从而减少搜索的计算量
kd树的最近邻搜索算法：
input：已构造的kd树，实例目标点x
output：实例点x的最近邻
步骤：
（1）在kd树中找包含目标点x的叶节点，从根节点出发，地递归的向下访问kd树，若x当前维的坐标小于切分点的坐标，则移动到左侧子节点，反之，移动到右侧子节点。直到子节点为叶节点为止
（2）递归的向上回退
3. 实践
neighbors.KNeighborsClassifier(n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None, n-jobs=1)
参数说明
- n_neighbors[defual=5]: int ,我们选取问题点最近的多少个最近邻。
- weights[defual=’uniform’]
- algorithm=’auto’,
是分类时采取的算法，有 'brute'、kd_tree和 ball_tree,默认的 'auto' 选项会在学习时自动选择最合适的算法，所以一般来讲选择 auto 就可以。
- leaf_size=30,
- p=2,
- metric=’minkowski’,
默认的 metric='minkowski'（默认）和 p=2（默认）就可以满足大部分需求。
metric_params=None,n-jobs[defual=1]:
计算的进程数量 ，默认1，-1为 cores of CPU
3.1. 调参策略
K 近邻算法使用的模型实际上对应于对特征空间的划分。该算法的三个基本要素：
1. K 值的选择，
2. 距离度量
3. 分类决策规则
k 值
K 值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误。
在实际应用中，K 值一般
1. 选择一个较小的数值，
2. 通常采用交叉验证的方法来选择最优的 K 值。
随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。
距离
距离度量一般采用 Lp 距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。
分类决策规则
该算法中的分类决策规则往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别
