1. 最邻近分类算法（nearest neighbor classification）

原理很简单，就是把标记好的图像都储存下来，预测的时候计算新图像和库中的每幅图像的L1距离，找到距离最近的图像即为最邻近。

code解析：时间复杂度train： O(1)， predict： O(n)，train的耗时少，predict耗时长，而我们理想的或者需要的是predict耗时少，train可以耗时长一些。

其效果如下，对于整幅图像的每个像素来说，找到训练数据中与其最近的样本，并标记为此样本的类，这种分类方法比较粗糙，存在很多问题，比如下图中绿色区域中间有一个黄色斑块，这个黄色斑块很可能是被错分的，也许其类别也应该是绿色的，还有绿色和蓝色的边界可以看到有一块像手指一样的绿色伸到了蓝色区域，这很可能是由于噪声或失真信号造成的。

由此产生了k-近邻算法

2. k-近邻算法（k-nearest neighbor KNN）

具体做法是：对分类图像，找到其k个最邻近的实例，然后在这k个最邻近的实例中按类进行投票，选出票数最大的类作为最终的分类结果。

可以看出，k越大，获得的分类边缘越平滑。

距离度量

除了L1距离（曼哈顿距离），还有L2距离（欧式距离）。
特点：
L1距离取决于你选择的坐标系统，如果转动坐标系统，将会改变点的L1距离。
而转动坐标系统，L2距离不会发生变化
如何选择？
如果某些输入特征对任务有特殊意义，也就是特征值是有特定意义的，那么L1距离更合适，否则选择L2距离更好。

超参选择

如何选择k以及合适的距离度量？

策略一：最简答的做法就是选择几组不同的超参组合去尝试，选择表现最好的那组。
策略二：交叉验证

如何衡量表现好坏？

把数据集分成三类，训练集、验证集和测试集，在训练集上进行训练，选择在验证集上表现最好的参数，这几步可以反复去做，最后是在测试集上验证，注意在确认最佳参数之前，不要使用测试集，以确保实验结果的无偏性和可靠性。

交叉验证

具体做法：选定一组参数，将数据集分成n份，其中一份始终作为测试集，其余的n-1份中每次选出一份作为验证集，其余作为训练集，计算其误差。最后将多次训练的误差结果求平均。
如上图，先用fold 5作为验证集，其余四份合起来作为训练集，计算其误差error1，然后用fold 4作为验证集，其余四份合起来作为训练集，计算其误差error2……，最后计算平均误差：
error= (error1 + error2 + error3 + error4 + error5) / 5
通过尝试不同的超参组合，选择error最小的作为最优参数。

注意，此方法计算量太大，不适合数据量较大的深度学习算法。

缺点

1. L2距离不太适合表示图像之间的视觉相似度

2. 维度灾难，最邻近分类如果想要有比较好的表现，那么就需要训练集的数据密集均匀的分布在样本空间。所以随着维度的增加，需要指数倍的增加训练数据。如上图假如在一维空间可以用4个训练样本实现密集均匀分布，那么在二维空间就需要4*4=16个，在三维空间就需要4*4*4=64个。

总结：最近邻算法仅做了解，实际图像处理中效果不好，基本不用。

3 线性分类器

最终训练得到参数W，预测的时候不再需要训练数据集。

缺点：不适用于非线性可分的情况