当前位置：首页 > java >正文

DAY02：【ML 第一弹】KNN算法

java 2025/7/14 21:02:28

一、算法简介

1.1 算法思想

如果一个样本在特征空间中的 k 个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别。

1.2 样本相似性

样本都是属于一个任务数据集的，样本距离越近则越相似。

二维平面上点的欧氏距离
二维平面上点 $a(x_1, y_1)$ 与 $b(x_2, y_2)$ 间的欧氏距离：
$d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
三维空间点的欧氏距离
三维空间点 $a(x_1, y_1, z_1)$ 与 $b(x_2, y_2, z_2)$ 间的欧氏距离：
$d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}$
n维空间点（向量）的欧氏距离
n维空间点 $a(x11,x12,…,x1n)a(x_{11}, x_{12}, \dots, x_{1n})$ 与 $b(x21,x22,…,x2n)b(x_{21}, x_{22}, \dots, x_{2n})$ 间的欧氏距离（两个n维向量）：
$d_{12} = \sqrt{\sum_{k=1}^{n} (x_{1k} - x_{2k})^2}$

1.3 K值的选择

1.3.1 大小选择

K值过小：

即用较小领域中的训练实例进行预测
易受到异常点的影响
意味着整体模型变得复杂，容易发生过拟合

K值过大：

即用较大领域中的训练实例进行预测
易受到样本均衡的问题
意味着整体模型变得简单，容易发生欠拟合

1.3.2 方法选择

交叉验证
网格搜索

1.4 应用方式

1.4.1 分类问题

计算未知样本到每一个训练样本的距离
将训练样本根据距离大小升序排列
取出距离最近的 K 个训练样本
进行多数表决，统计 K 个样本中哪个类别的样本个数最多
将未知的样本归属到出现次数最多的类别

1.4.2 回归问题

计算未知样本到每一个训练样本的距离
将训练样本根据距离大小升序排列
取出距离最近的 K 个训练样本
把这个 K 个样本的目标值计算其平均值
作为将未知的样本预测的值

二、API简介

2.1 分类问题

class sklearn.neighbors.KNeighborsClassifier( n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None 
)

2.1.1 参数说明

n_neighbors (int, default=5) ：表示K值，即预测样本时考虑的最近邻的数量。
weights ({‘uniform’, ‘distance’} or callable, default=‘uniform’) ：权重函数，用于确定在预测时，近邻样本对预测结果的影响程度。
- 'uniform'：所有邻居的权重相同，即每个近邻样本在预测中具有同等的影响力。
- 'distance'：权重与距离成反比，意味着距离预测样本越近的邻居，对预测结果的影响越大。
- 自定义一个可调用的函数，根据距离来计算每个邻居的权重。
algorithm ({‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}, default=‘auto’) ：计算最近邻的算法。
- 'brute'：暴力搜索算法，它会计算所有样本之间的距离，然后找出K个最近邻。
- 'kd_tree'：KD树算法，是一种对k维空间中的实例点进行存储以便快速检索的树形数据结构，适用于低维数据，一般维数小于20时效果较好。
- 'ball_tree'：球树算法，通过超球体来划分样本空间，每个节点对应一个超球体，相比KD树在高维数据上表现更优。
- 'auto'：自动选择最合适的算法，算法会根据训练数据的规模、特征维度等因素来选择。
leaf_size (int, default=30) ：仅在使用'kd_tree'或'ball_tree'算法时生效，表示KD树或球树的叶子节点大小。
p (int, default=2) ：距离度量的参数，仅当metric='minkowski'时有效。
- p=1：表示曼哈顿距离（L1范数），计算公式为 $d(x,y)=∑i=1n∣xi−yi∣d(x,y)=\sum_{i=1}^{n}|x_i - y_i|$ 。
- p=2：表示欧氏距离（L2范数），计算公式为 $d(x,y)=∑i=1n(xi−yi)2d(x,y)=\sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$ 。
metric (str or callable, default=‘minkowski’) ：距离度量类型。
- 'euclidean'（欧氏距离）
- 'manhattan'（曼哈顿距离）
- 'chebyshev'（切比雪夫距离）
- 'minkowski'（闵可夫斯基距离）
- 自定义一个可调用的函数，计算样本之间的距离。
metric_params (dict, default=None) ：距离度量的额外参数，当使用自定义距离度量函数或者某些需要额外参数的距离度量时使用。
n_jobs (int, default=None) ：并行计算数。
- -1，表示使用所有可用的处理器进行并行计算，以加快计算速度。
- 具体的整数，表示使用指定数量的处理器进行并行计算。

2.1.2 常用方法

fit(X, y) ：用于拟合模型，将训练数据X（特征矩阵，形状为(n_samples, n_features)）和对应的标签y（形状为(n_samples,)）输入该方法，模型会存储训练数据。
predict(X) ：预测输入数据X（特征矩阵）的类别标签，返回一个数组，数组中的每个元素是对应样本的预测类别。
predict_proba(X) ：返回输入数据X属于各类别的概率，返回一个形状为(n_samples, n_classes)的数组，n_samples是样本数量，n_classes是类别数量，数组中每个元素[i][j]表示第i个样本属于第j个类别的概率。
kneighbors((X, n_neighbors, return_distance)) ：查找点的K近邻。
- X：需要查找近邻的样本点（特征矩阵）。
- n_neighbors：指定查找的近邻数量，如果不指定，则使用构造函数中设置的n_neighbors值。
- return_distance：布尔值，默认为True，表示是否返回距离信息。如果为True，会返回两个数组，第一个数组是查询点与近邻点之间的距离，第二个数组是近邻点在训练数据中的索引；如果为False，只返回近邻点在训练数据中的索引。
score(X, y) ：返回给定测试数据X和标签y的平均准确率，即预测正确的样本数占总样本数的比例，用于评估模型在测试集上的性能。

2.1.3 代码实操

# 1. 工具包
from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor# 2. 数据
# 分类
x = [[0,2,3],[1,3,4],[3,5,6],[4,7,8],[2,3,4]]
y = [0,0,1,1,0]# 3. 实例化
# 分类
model_1 = KNeighborsClassifier(n_neighbors=3)# 4. 训练
model_1.fit(x,y)# 5. 预测
print("分类：", model_1.predict([[4,4,5]]))

2.2 回归问题

class sklearn.neighbors.KNeighborsRegressor(n_neighbors=5,weights='uniform',algorithm='auto',leaf_size=30,p=2,metric='minkowski',metric_params=None,n_jobs=None
)

2.2.1 代码实操

# 1. 工具包
from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor# 2. 数据
# 回归
m = [[0,1,2],[1,2,3],[2,3,4],[3,4,5]]
n = [0.1,0.2,0.3,0.4]# 3. 实例化
# 回归
model_2 = KNeighborsRegressor(n_neighbors=3)# 4. 训练
model_2.fit(m,n)# 5. 预测
print("回归：", model_2.predict([[4,4,5]]))

三、距离度量方法

3.1 欧氏距离

3.1.1 定义

Euclidean Distance 欧氏距离
两个点在空间中的距离

3.1.2 数学公式

二维平面上点的欧氏距离
二维平面上点 $a(x_1, y_1)$ 与 $b(x_2, y_2)$ 间的欧氏距离：
$d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
三维空间点的欧氏距离
三维空间点 $a(x_1, y_1, z_1)$ 与 $b(x_2, y_2, z_2)$ 间的欧氏距离：
$d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}$
n维空间点（向量）的欧氏距离
n维空间点 $a(x11,x12,…,x1n)a(x_{11}, x_{12}, \dots, x_{1n})$ 与 $b(x21,x22,…,x2n)b(x_{21}, x_{22}, \dots, x_{2n})$ 间的欧氏距离（两个n维向量）：
$d_{12} = \sqrt{\sum_{k=1}^{n} (x_{1k} - x_{2k})^2}$

3.2 曼哈顿距离

3.2.1 定义

Manhattan Distance 曼哈顿距离
City Block Distance 城市街区距离
横平竖直

3.2.2 数学公式

二维平面两点 $a(x_1,y_1)$ 与 $b(x_2,y_2)$ 间的曼哈顿距离：
$d_{12} =|x_1 - x_2| + |y_1 - y_2|$
n维空间点 $a(x11,x12,…,x1n)a(x_{11},x_{12},\dots,x_{1n})$ 与 $b(x21,x22,…,x2n)b(x_{21},x_{22},\dots,x_{2n})$ 的曼哈顿距离：
$d_{12} = \sum_{k=1}^{n} |x_{1k} - x_{2k}|$

3.3 切比雪夫距离

3.3.1 定义

Chebyshev Distance 切比雪夫距离
国际象棋中，国王可以直行、横行、斜行，所以国王走一步可以移动到相邻8个方格中的任意一个。国王从格子 $x_1,y_1)$ 走到格子 $x_2,y_2)$ 最少需要的步数

3.3.2 数学公式

二维平面两点 $a(x1,y1)\text{a}(x_1,y_1)$ 与 $b(x2,y2)\text{b}(x_2,y_2)$ 间的切比雪夫距离：
$d_{12} = \max\left(|x_1 - x_2|, |y_1 - y_2|\right)$
n维空间点 $a(x11,x12,…,x1n)\text{a}(x_{11},x_{12},\dots,x_{1n})$ 与 $b(x21,x22,…,x2n)\text{b}(x_{21},x_{22},\dots,x_{2n})$ 的切比雪夫距离：
$d_{12} = \max\left(|x_{1i} - x_{2i}|\right) \quad (i = 1,2,\dots,n)$

3.4 闵氏距离

3.4.1 定义

Minkowski Distance 闵可夫斯基距离
根据 p 的不同，闵氏距离可表示某一种类的距离

3.4.2 数学公式

两个n维变量 $a(x11,x12,…,x1n)\boldsymbol{a}(x_{11}, x_{12}, \dots, x_{1n})$ 与 $b(x21,x22,…,x2n)\boldsymbol{b}(x_{21}, x_{22}, \dots, x_{2n})$ 间的闵可夫斯基距离定义为：
$d_{12} = \sqrt[p]{\sum_{k=1}^{n} \left| x_{1k} - x_{2k} \right|^p}$

变参数 p：
- 当 $p = 1$ 时，退化为曼哈顿距离（Manhattan Distance）
- 当 $p = 2$ 时，退化为欧氏距离（Euclidean Distance）
- 当 $\to \infty$ 时，退化为切比雪夫距离（Chebyshev Distance）