KNN--k-NearestNeighbor可以是是分类法中最简单的算法了。

大致的idea为：找出k各跟新数据点最像的点，看这些点主要属于哪类，那么新数据点也就属于哪类的了。

其伪代码如下：

1. 拿到一个新的数据点

2. 计算其到training set中每个点的距离

3. 对距离排序

4. 对距离新数据点最近的前k个点的label数进行统计，出现次数最多的种类则为新数据点的label

在本篇随笔中，我们最要对距离函数进行讨论。

标准的kNN是使用二范数进行计算距离的，其实我们也还可以使用其他范数（1范数~无穷范数）等范数进行距离计算。

同时，我们也可以考虑参考SVM的kernel trick使用gaussian kernel来算距离。也可以考虑使用余弦函数算距离。

那么，实际应用中我们怎么选取合适的距离函数呢？

可以考虑是用k-fold的方法来试错得出。

简单的说，就是对使用以上各种距离函数的kNN：把data set分成k组。重复k次，每次选第k组为training set，剩下的为testing set。

计算总的错误数，然后排序，找到能使错误数最小的距离函数。

KNN距离函数的简单拓展