k近邻算法
knn算法原理
在分类任务中，目的是判断样本 $x$ 的类别 $y$。KNN首先会观察距离该样本点最近的 $K$ 个样本，统计这些样本类别，并将该样本归类为出现次数最多的样本。即“物以类聚，人以群分”。因此，knn算法中的 $k$ 值作为超参数对结果影响非常明显，太小的 $k$ 值可能会导致最近的噪声样本影响，太大的 $k$ 值可能会引入太远的样本点影响。
具体的数学语言表示如下，设已分类的样本集合为 $x_0$ 。对于一个待分类的样本 $x$ ，定义其邻居 $ N_K(x) $ 为 $x_0$ 中与 $x$ 距离最近的 $K$ 个样本 $x_1, x_2, ..., x_K$ 组成的集合，这些样本对应的分类分别为 $y_1, y_2, ..., y_K$ 。统计集合 $N_K(x)$ 中类别为 $j$ 的样本数量，记为 $G_j(x)$：
$$ G_j(x) = \sum_{x_i \in N_K(x) } \mathbb{I}(y_i = j) $$其中，$\mathbb{I}(p)$ 是示性函数，其自变量 $p$ 是一个命题，当 $p$ 为真时， $\mathbb{I}(p)$ 为1，否则为 0。最后，将 $x$ 的类别判断为：
$$ \hat y(x) = argmax_j \ G_j(x) $$此外还可以将 KNN 应用于回归任务。对于样本 $x$ ，我们需要预测其对应的实数值 $y$ 。同样的，考虑 $K$ 个相邻样本点，将这些样本点对应的实数值 $y_i$ 做加权平均即可。
$$ \hat y(x) = \sum_{x_i \in N_K(x)} w_iy_i \ , \sum_{i = 1}^K w_i = 1 $$其中，权重 $w$ 可以通过预定义的方式，也可以作为模型参数通过学习得到。