K最近邻(kNN，k-NearestNeighbor)分类算法

　　是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。
　　kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。

k-NN classification problem

　　取一个新的观测向量x，将它分到 K 个离散的类 Ck (k=1,2,…,K) 之一。一般来说，类之间是互不相容的，因此，每一个观测只能被分到一个类中。

大间隔最近邻居(Large margin nearest neighbor，LMNN)

　　大间隔最近邻居分类算法是统计学的一种机器学习算法。该算法是在k近邻分类其中学习一种欧式距离度量函数。基于欧式距离度量学习函数的大间隔最近邻居分类算法能够很好的改善k近邻算法分类效果。

为什么KNN分类中为什么有白色区域？

　　答：没有获得任何一个区域的投票
　　这白色区域应该是KNN无法决策的区域，比如KNN的类中有2个或2个以上的是最近的，要减少白色区域可以调整K值，或者修改最近邻的决策条件，再或者修正距离公式。

课件中的demo

　　地址：http://vision.stanford.edu/teaching/cs231n-demos/knn/
　　1）k=1，其他参数任选，基本上不会有白色区域，因为总能在training data中找到最邻近的sample和相应的class，如果有两个sample的距离相等，那就对应了classes之间的边界。
　　如下图所示。但是k=1时，很容易出现过拟合。

　　2）k>1，如下图所示，出现了该问题中的白色区域。回答这个问题先要弄清楚，k>1时，如何预测。
　　若k=2，那么先计算得到与test sample相距最邻近的两个training samples，如果这两个samples属于相同的class，比如A，那么该test sample将被划为class A所在的区域。 但是如果这两个samples分别属于不同的class，比如A和B，那么在课程的例子中，就会被划为白色区域。 但是可以通过一些策略打破，比如当k=7，结果中3个A class的samples，3个B class的samples和1个C class的samples，那么必须从A和B中选择一个，而非划为White region。
　　另外，k=2非常特殊，与k=7相比，更容易出现White region。比较k=2和k=7的结果，可以看出来，也很容易理解。
　　如下图，k=2，很容易出现大面积的白色区域

　　如下图，k=7，相比k=2，不容易出现白色区域