1. K近邻算法的基本实现过程?

    答:

    输入:训练数据集:

    其中$x_i \in R^n$, $y_i \in {c_1, c_2, …, c_k}$为实例的类别,$i = 1,2,…,N$, 实例特征向量x:

    输出:实例$x$ 所对应的类别$y$.

    1. 根据给定的距离度量,在训练集 $T$ 中找出与$x$最近邻的k个点,涵盖这k个点的邻域记作$N_k(x)$.

    2. 在$N_k(x)$中根据分类决策规则(如多数表决)决定$x$的类别$y$:

  2. K近邻常用的距离度量,以及各种不同度量之间的关系?

    答:常用的距离为$L_p$ 距离, 其中定义为: 当$p=2$ 称为欧式距离,$p=1$ 为曼哈顿距离,$p=\inf$也很常见。

  3. k值的选择与模型复杂度之间的关系?

    答: k值越大,模型复杂度越低。如果选择较大的$k$值,例如$k=N$, 则无论输入什么$x$预测值都不变。

  4. 多数表决规则与经验风险最小化之间的关系?

    答:多数表决规则等价于经验风险最小化。

  5. kd树的构造方法*