机器学习经典算法 - KNN

这段时间在考虑下一步的学习计划，在地铁上完成了 Andrew Ng 的机器学习的课程，感觉非常棒，从未知到知晓的过程总是带给我快乐。只不过观看视频只能对可能需要的知识有一个大概的框架，还需要在项目中应用才能真正的理解。

在这里记录一些常用的机器学习的算法知识，算是做一个初步的总结，以备自己随时查看，后续还是要在应用中继续深入学习和补充完善。这段时间以来一个很深的体会是在算法学习中，一个很重要的原则是：先建立直觉，再勾勒细节。在此基础上，相应的数学和代码就都是水到渠成的事了。

KNN, K Nearest Neighbors

K 邻近算法是基于实例的学习方法 Instance based learning，其核心观点在于我们不再采用对于已有数据的曲线拟合来完成新的样本的分类或回归，而是基于与新样本最近的某 K 个样本的分类中出现最多的分类来对新样本进行分类，或者在回归问题中，取最近的 K 个标签值的均值作为预测值。由于算法只有在执行预测时才进行学习，因此也被称为 Lazy Learning，与此相对应的预先学习的算法称为 Eager Learning。

在 KNN 中，由于预先假设不同样本点之间具有一定的相似性 Similarity defined by locality，并且通常在进行距离计算时一般会假定不同特征的差异再决定分类时具有相同的重要性，例如对于两个二维样本 x, y 的曼哈顿距离进行计算时，由于其可以表示为 |x₁ - y₁| + |x₂ - y₂|，此时我们假定样本的不同特征之间可以简单的线性相加。而如果真实的函数关系为 z = x₁² + x₂，则选择曼哈顿距离作为评价标准时 KNN 无法准确的给出预测值，算法准确度会随着特征维数的增加而愈加下降，尽管采用加权计算一定程度上可以减少 Curse of Dimensionality 的影响，算法也比较容易受到异常值的影响。

Curse of Dimensionality

As the number of features or dimensions grows, the amount of data we need to generalize accurately grows exponentially.

KNN 算法的核心原理非常简单，在实际使用中实际输出结果根据算法执行中距离的判断标准（欧式距离、曼哈顿距离等）、对于距离相同时的处理方式、K 的选择等不同的细节会有所不同。

• To be added: locally weighted regression

参考阅读

1. VGG 作者 Andrew Zisserman 的一个 Machine Learning 资源库