机器学习 - 第一讲作业

试分析 K-NN 近邻分类器中，(1)K 取不同值对分类结果的影响。用具体的分类事例来说明。(2) 距离计算对 K-NN 近邻分类器有直接影响，试分析不同距离计算在不同数据分类中的优势。距离包括 Lp 距离，欧式距离和曼哈顿距离等。

1. K 取不同值对分类结果的影响

以最基本的二维平面上的分类例子（训练集大小 $N\gg k$）来分析：

• 当 K=1 时,新样本的类别完全取决于距离其最近的那个训练样本的类别。这可能会导致过拟合,因为单个噪声点就会影响整个决策边界。
• 当 K 较小时 (如 K=3),决策边界会非常紧贴局部数据分布,呈现出更多的不规则曲线。这对于很多复杂分布的数据集可能是合适的,但也可能会过度拟合噪声。
• 当 K 取一个中等值时 (如 K=10),新样本的类别将取决于其 10 个最近邻的投票结果。相比于 K 较小时,中等 K 值可以使决策边界更平滑,减小噪声的影响。
• 当 K 值很大时 (如 K=100),算法会将大部分训练样本都当作 ” 近邻 ” 来投票,导致新样本类别取决于全局占主导的那一类。这相当于做出一个非常粗糙和简单的分类,决策边界将近似于线性的或低阶曲面。
• 在极端情况下,如果 K 等于训练集大小,所有新样本将被分到占多数的那一类中,相当于朴素的多数投票分类器。

2 距离计算对 K-NN 近邻分类器的影响

1. Lp 距离 (Minkowski distance):

$L_p(x,y)=({\sum }_{i=1}^n|x_i-y_i{|}^p{)}^{1/p}$

其中 p>=1, n 为特征维数。当 p=2 时为欧几里得距离。当 p=1 时为曼哈顿距离。

2. 欧几里得距离 (Euclidean distance):

$d(x,y)=\sqrt{{\sum }_{i=1}^n(x_i-y_i{)}^2}$

3. 曼哈顿距离 (Manhattan distance):

$d(x,y)={\sum }_{i=1}^n|x_i-y_i|$

不同距离度量的优缺点:

• 欧几里得距离对异常值较为敏感,但在大多数情况下表现良好,尤其是在数据分布接近球形时。

• 曼哈顿距离对异常值的影响较小,当特征之间存在一定关联时,曼哈顿距离可能更加合适。如在分类文本文档主题时,单词两两之间存在一定关联。

• 当 p>2 时,Lp 距离对异常值的敏感程度会降低,当数据存在高维 sparse 时会更稳健。

• 当 p<1 时,Lp 距离会给予较大权重影响更多维度,对于很多应用场景并不合适。

• 对于低维密集数据,如果没有异常值,欧氏距离通常是首选。

• 对于高维空数据,如文本等,曼哈顿距离或小于 2 的 Lp 距离可能更合适。

• 如果数据存在明显的异常值,可以尝试曼哈顿距离或 Lp 距离 (p>2) 来减小异常值的影响。

• 对于离群数据点较多的数据集,使用 p 在 1~2 之间的 Lp 距离可能会更稳健。

---

其它常见距离

1. 闵可夫斯基距离 (Minkowski Distance)

$D(x,y)=({\sum }_{i=1}^n|x_i-y_i{|}^r{)}^{1/r}$

其中 r>=1 是一个参数,当 r=1 时就是曼哈顿距离,r=2 时就是欧氏距离。通过调节 r 的值,可以权衡不同维度特征的影响。

2. 切比雪夫距离 (Chebyshev Distance)

$D(x,y)={\max }_{i=1,...,n}|x_i-y_i|$

切比雪夫距离实际上是向量无穷范数,常用于寻找两个样本最大的分量差值。对于高维数据或异常值比较敏感的场景,切比雪夫距离可能更合适。

3. 加权距离 (Weighted Distance)

$D(x,y)=\sqrt{{\sum }_{i=1}^n{w}_i(x_i-y_i{)}^2}$

加权距离通过对不同特征赋予不同权重,能更好地反映各个特征对分类的重要程度。这对异构数据或具有冗余特征的数据集非常有用。

4. 核函数 (Kernel) 距离

$K(x,y)=\exp (-\gamma ||x-y|{|}^2)$

核函数距离是在原空间中定义的距离,但在核函数所诱导的再生核希尔伯特空间中运算。常见的核函数有高斯核、多项式核等,不同的核函数对应不同的距离。在处理非线性数据时,使用核函数距离可能更有效。