模型
k近邻算法可以用于分类和回归问题，这里对其在分类方面的应用进行讨论。作为一种分类问题的解决方法，k近邻法接收待分类实例特征的向量作为输入，对该实例的分类结果作为输出。具体定义如下：
存在训练集：
\[T = \lbrace (x_1, y_1), ..., (x_N, y_N) \rbrace\]输入实例 $ x $，其中 $ x, x_i \subseteq R^n, y \in \lbrace c_1, …, c_K \rbrace $，$ K $ 为类别的个数，k近邻算法会根据样本集中，与 $ x $ 距离最接近的 $ k $ 个样本，通过某种策略（例如多数表决法）判断出其类别 $ y $。
如果采用多数表决法，则 $ y $ 的取值可以表示为：
\[y = \arg\max_{c_j} \sum_{x_i \in N_k(x)} I(y_i = c_j)\]其中， $ N_k(x) $表示 $ x $ 的邻域，即和 $ x $ 最接近的 $ k $ 个样本构成的集合； $ I(y_i == c_j) $ 为指示函数，当 $ y_i = c_j $ 时为1，否则为0。
k近邻算法没有显式的训练过程。
要素
距离度量
两个向量的距离反映了它们之间的相似度（参考余弦相似度)。k近邻算法一般接受 $ x \in R^n $作为参数，所以可以选用 $ p $ 范数作为距离，一般采用 $ p = 2$，但 $ p $也可以取其他值（ $ p \ge 1 $ ）。
一般的 $ p $ 范数表示如下：
\[L_p(x_i, x_j) = \Bigg( \sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p \Bigg)^{\frac{1}{p}}\]其中，$ x_i， x_j \subseteq R^n $。
当 $ p = 1 $ 时，称为曼哈顿距离：
\[L_1(x_i, x_j) = \sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|\]当 $ p = 2 $ 时，称为欧几里得距离：
\[L_2(x_i, x_j) = \Bigg( \sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^2 \Bigg)^{\frac{1}{2}}\]当 $ p = \infty $ 时，范数表示所有坐标中距离的最大值：
\[L_\infty(x_i, x_j) = \max_l |x_{i}^{l}-x_{j}^{l}|\]$ k $ 值的选择
$ k $ 值的选取一定程度上反映了模型的复杂度， $ k $ 越大表明模型越简单，$ k $越小表明模型越复杂。
当 $ k $ 较小时，k近邻算法会从样本集中选取和输入实例距离最接近的较少几个样本通过某种策略对输入实例的类型进行估计，这种方式对样本集中的噪音极为敏感，如果邻域中的样本恰好为噪音，则预测结果不可靠。
当 $ k $ 较大时，算法会根据较大的邻域中样本的类别对输入实例的类型进行估计，这种情况下样本的噪声会被平均，影响较小，但如果邻域选择较大，其它不相似的样本也会参与决策，使得预测结果不可靠。
考虑两种极端情况：
- 当 $ k = 1 $ 时，输入实例的类型仅有离它最近的样本决定，此时称为最近邻算法。
- 当 $ k = N $ 时，所有的样本均参与决策，如果采用多数表决法，则输出为训练集中存在最多的类别。
决策规则
k近邻算法一般采用多数表决（等权），即将在邻域中出现最多的类别作为实例类别输出。
k近邻算法还可以采用加权算法，例如对邻域中距离实例较远的点赋予较低的权重，距离较近的点赋予较高的权重。
