前言
机器学习为什么有趣呢？我的理解是因为它拟物、拟人，能够给人以一种难以名状神奇的真实感。它学习着人类的思考方式，试图去像人类一样去感受世界。抑或是帮脆弱的人类去执行危险的任务。今天给大家介绍的机器学习算法就是大家耳熟能详的 K近邻算法 (K-Nearest-Neighbors)
正文
K近邻算法 (K-Nearest-Neighbors)
这个算法滴概念很简单：“物以类聚，人以群分”。 即当前样本点 $x_i$ 周围最近的 $K$ 个样本点的主类别是 $C$，那么这个样本点的类别也就为 $C$。 其中 “主类别” 的意思就是这最近的 $K$ 个样本点里数量最多的类别。
那么我们该怎么去度量样本之间的距离呢？通常来说会使用 欧氏距离(Euclidean Distance) 去度量样本的远近，但也可以用其他距离，如更一般的 $L_p$距离 ($L_{p}$ distance) 或 $Minkowski$距离 (Minkowski distance)。
设特征空间 $\chi$ 是 $n$ 维实数向量空间 $R^n, x_i,x_j\in \chi,x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T,x_j=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^T,x_i,x_j$ 的 $L_P$ 距离定义为：
\[L_p(x_i,x_j) = (\sum_{l=1}^{n}\mid x_i^{(l)}-x_j^{(l)}\mid ^p)^{\frac{1}{p}} \tag{1}\]这里 $p\ge1$。当 $p=2$ 时，称之为欧氏距离 (Euclidean distance)，即：
\[L_2(x_i,x_j) = (\sum_{l=1}^{n}\mid x_i^{(l)}-x_j^{(l)}\mid ^2)^{\frac{1}{2}} \tag{2}\]当 $p=1$ 时，称之为曼哈顿距离 (Manhattan distance)，即：
\[L_1(x_i,x_j) = \sum_{l=1}^{n}\mid x_i^{(l)}-x_j^{(l)}\mid \tag{3}\]当 $p=\infty$ 时，它是各个坐标距离的最大值，即
\[L_{\infty}(x_i,x_j) = \max_l \mid x_i^{(l)}-x_j^{(l)}\mid \tag{4}\]接下来举一个例子
如上图所示，图中心绿色圆点是未知的样本点。问题来了，那么这个点是属于红色三角类还是属于蓝色方框类呢？
如果选择一个 近距离视角，即是黑色实线圈内，它应属于 红色三角 类，因为它离那两个红色更近，并且 红色三角 在这个区域是 主导类别 因为其数量最多。然而 如果将眼光再放远一点，即黑色虚线圈内，我们将会得到一个完全不一样的答案，绿点将被划分为 蓝色方块 类。
什么导致了上述情况的发生呢？答案就是算法名称中的 $K$值。$K$值越大，那么表示我们更加注重 “宏观” 层面，反之 $K$值越小即表示我们关心的是 “微观” 层面。
哪种层面更好呢？换句话说我们应该怎么决定 $K$值的选取呢？很遗憾，没有一个确定的答案，因为现实生活中事物往往具有多面性。举个栗子，我16年买了一部 iPhone 7刚刚到手2天就坏了直接返厂去维修了。但是在我们宿舍 iPhone 的故障率是100%，因为只有我一个人使用 iPhone，然而放眼整个学校 iPhone 的故障率可能就会降到5%左右。这两个数字有着天壤之别，其原因就是样本所选取的范围不同，即$K$值的不同。
Specifically，$K$值的选择我们只能根据实际情况来选择。在应用中，$K$值一般取一个比较小的数值。通常采用 交叉验证法 来选取最优的$K$值。
$K$值的选择会对 $K$ 近邻法的结果产生重大的影响。
- 如果选择较小的 $K$ 值，就相当于用小范围的邻域中的训练样本去预测未知样本，导致预测结果对近邻的训练样本非常敏感。如果周围的实例点中噪声恰巧占据了多数席位，那么预测就会出错。换句话说，$K$ 值的减小意味着整体模型变得复杂，容易发生过拟合。
- 另一方面，如果选择较大的 $K$ 值，就相当于用较大范围中的训练样本进行预测。此时离未知样本较远的（相似程度较低的）训练实例也会对预测起作用，使预测发生错误。 $K$ 值的增大就意味着整体的模型变得简单。
接下来描述 K近邻算法 (K-Nearest-Neighbors) 的步骤：
输入： 训练数据集 $T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$。其中，$x_i\in \chi \subseteq R^n$ 为实例的特征向量，$y_i\in \gamma = {c_1,c_2,…,c_K}$为实例的类别。
输出： 样本 $x^{test}$ 的类别。
- 选择一个距离度量标准，在训练集 $T$ 中找出与待预测样本 $x^{test}$ 最近邻的 $K$ 个训练样本。
- 在这最近的 $K$ 个训练样本中根据分类决策规则来确定 $x^{test}$ 的类别 $y$。分类决策规则自行决定，但对于 $KNN$ 通常采用 多数表决 的规则：
式 $(5)$ 中 $I$ 为指示函数，即当 $y_i=c_j$ 时 $I$ 为 $1$，否则为 $0$。
从上面的描述我们可以得知，$KNN$ 模型是通过直接学习最终的判别函数 $y=f(x)$，因此属于判别模型。
至此，$K$近邻算法的原始版本就讲完啦，之后还有采用 $kd$树 的方法来实现 $KNN$,未完待续！
:)
