如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
K近邻算法的基本实现过程？
答：
输入：训练数据集：
\[T=\{(x_1, y_1), ..., (x_n, y_n)\}\]其中$x_i \in R^n$, $y_i \in {c_1, c_2, …, c_k}$为实例的类别，$i = 1,2,…,N$, 实例特征向量x：
输出：实例$x$ 所对应的类别$y$.
根据给定的距离度量，在训练集 $T$ 中找出与$x$最近邻的k个点，涵盖这k个点的邻域记作$N_k(x)$.
在$N_k(x)$中根据分类决策规则（如多数表决）决定$x$的类别$y$:
\[y = argmax_{c_j}\sum_{x_i \in N_k(x)} I(y_i=c_j), i=1,2,...,N;j=1,2,...,K.\]
K近邻常用的距离度量，以及各种不同度量之间的关系？
答：常用的距离为$L_p$ 距离， 其中定义为： \(L_p(x_i, x_j) = (\sum_{l=1}^{n}|x_i^{l}-x_j^{l}|^p)^{\frac{1}{p}}\) 当$p=2$ 称为欧式距离，$p=1$ 为曼哈顿距离，$p=\inf$也很常见。
k值的选择与模型复杂度之间的关系？
答: k值越大，模型复杂度越低。如果选择较大的$k$值，例如$k=N$, 则无论输入什么$x$预测值都不变。
多数表决规则与经验风险最小化之间的关系？
答：多数表决规则等价于经验风险最小化。
kd树的构造方法*