Day2 KNN算法

简介

Image Classification Pipeline

KNN算法

---

1. 核心思想：如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。

2. 试用范围：对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合；适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好

Distance Matrix： 简单来说就是用来计算两张图片之间的差异性大小。提到了最常用的 L1 曼哈顿距离（绝对值差）和 L2欧式距离（平方根）

hyper-parameters (K and Distance Matrix):  choices about the algorithm that we set rather than learn。 我们需要设置不同的K值，选择某个Distance Matrix，验证到底哪一个更合适。这时就引入了

Cross-validation. 交叉验证

CV是用来验证分类器的性能一种统计分析方法，基本思想是把在某种意义下将原始数据(dataset)进行分组,一部分做为训练集(train set)，另一部分做为验证集(validation set)，首先用训练集对分类器进行训练，在利用验证集来测试训练得到的模型(model)，以此来做为评价分类器的性能指标。

CV中最有名的就是K-Folder CV：将原始数据分成K组（一般是均分），将每个子集数据分别做一次验证集，其余的K-1组子集数据作为训练集，这样会得到K个模型，用这K个模型最终的验证集的分类准确率的平均数作为此K-CV下分类器的性能指标。K一般大于等于2，实际操作时一般从3开始取，只有在原始数据集合数据量小的时候才会尝试取 2。K-CV可以有效的避免过学习以及欠学习状态的发生，最后得到的结果也比较具有说服性。下图就是一个5折交叉检验

其他类型的交叉验证

CV

Summary

k-Nearest Neighbor on images never used.

Very slow at test time / Distance metrics on pixels are not informative / Curse of dimensionality

Same distance KNN Summary

这有一篇详细介绍KNN的文章，有两个问题在使用KNN时需要考虑，摘录如下：

2、类别如何判定最合适？投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。

3、如何选择合适的距离衡量？高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。

下文附了一个KNN Demo的链接，可以手动感受一下，挺有意思的。:)

KNN Demo演示：选择不同Num classes和Num Points生成初始数据，然后设置不同的Metric和不同的K来看分类结果。动手试一下，还是挺有意思的。

KNN Demo