如果这篇博客帮助到你,可以请我喝一杯咖啡~
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树的构造方法*