Skywind Inside

kNN （k-nearest neighbors）作为一个入门级模型，因为既简单又可靠，对非线性问题支持良好，虽然需要保存所有样本，但是仍然活跃在各个领域中，并提供比较稳健的识别结果。

说到这里也许你会讲，kNN 我知道啊，不就是在特征空间中找出最靠近测试样本的 k 个训练样本，然后判断大多数属于某一个类别，那么将它识别为该类别。

这就是书上/网络上大部分介绍 kNN 的说辞，如果仅仅如此，我也不用写这篇文章了。事实上，kNN 用的好，它真能用出一朵花来，越是基础的东西越值得我们好好玩玩，不是么？

第一种：分类

避免有人不知道，还是简单回顾下 kNN 用于分类的基本思想。

针对测试样本 Xu，想要知道它属于哪个分类，就先 for 循环所有训练样本找出离 Xu 最近的 K 个邻居（k=5），然后判断这 K个邻居中，大多数属于哪个类别，就将该类别作为测试样本的预测结果，如上图有4个邻居是圆形，1是方形，那么判断 Xu 的类别为 “圆形”。

第二种：回归

根据样本点，描绘出一条曲线，使得到样本点的误差最小，然后给定任意坐标，返回该曲线上的值，叫做回归。那么 kNN 怎么做回归呢？

Read more…

学习 SVM 的最好方法是实现一个 SVM，可讲理论的很多，讲实现的太少了。

假设你已经读懂了 SVM 的原理，并了解公式怎么推导出来的，比如到这里：

SVM 的问题就变成：求解一系列满足约束的 alpha 值，使得上面那个函数可以取到最小值。然后记录下这些非零的 alpha 值和对应样本中的 x 值和 y 值，就完成学习了，然后预测的时候用：

上面的公式计算出 f(x) ，如果返回值 > 0 那么是 +1 类别，否则是 -1 类别，先把这一步怎么来的，为什么这么来找篇文章读懂，不然你会做的一头雾水。

那么剩下的 SVM 实现问题就是如何求解这个函数的极值。方法有很多，我们先找个起点，比如 Platt 的 SMO 算法，它后面有伪代码描述怎么快速求解 SVM 的各个系数。

第一步：实现传统的 SMO 算法

现在大部分的 SVM 开源实现，源头都是 platt 的 smo 算法，读完他的文章和推导，然后照着伪代码写就行了，核心代码没几行：

Read more…