K近邻算法学习笔记
一、算法简介
K近邻算法（K - Nearest Neighbors，简称KNN）是一种简单而有效的分类和回归算法。它的核心思想是“近朱者赤，近墨者黑”，即一个数据点的类别或值可以通过其周围最近的K个邻居来判断。KNN算法不需要复杂的模型训练过程，而是直接基于数据点之间的距离来做出决策。
二、算法原理
- 距离度量
- 欧氏距离：最常用的距离度量方式，计算两个点在各维度差值的平方和的平方根。例如，对于两个点 (x) 和 (y)，其欧氏距离为 (\sqrt{\sum_{i=1}^{n}(x_i - y_i)^2})，其中 (n) 是特征的维度。
- 曼哈顿距离：计算两个点在各维度差值的绝对值之和，适用于网格状数据。公式为 (\sum_{i=1}^{n}|x_i - y_i|)。
- 明可夫斯基距离：是欧氏距离和曼哈顿距离的推广形式，公式为 (\left(\sum_{i=1}^{n}|x_i - y_i|p\right){1/p})，当 (p=2) 时为欧氏距离，当 (p=1) 时为曼哈顿距离。
- K值的选择
- K值的选择对算法性能至关重要。如果K值过小，模型容易受到噪声数据的影响，导致过拟合；如果K值过大，模型可能会将远离目标点的数据也纳入考虑范围，导致欠拟合。
- 通常需要通过交叉验证等方法来选择合适的K值。例如，可以尝试不同的K值，计算每个K值下的模型性能指标（如准确率、召回率等），选择性能最优的K值。
- 投票机制
- 分类任务：对于分类问题，算法会统计目标点周围最近的K个邻居中每个类别的数量，然后选择数量最多的类别作为目标点的预测类别。例如，如果K=5，目标点周围有3个邻居属于类别A，2个邻居属于类别B，那么目标点将被预测为类别A。
- 回归任务：对于回归问题，算法会计算目标点周围最近的K个邻居的值的平均值或加权平均值作为目标点的预测值。例如，如果K=3，目标点周围3个邻居的值分别为1、2、3，那么目标点的预测值可以是 ((1+2+3)/3=2)。
三、算法流程
- 数据预处理
- 归一化：由于KNN算法依赖距离计算，因此特征值的范围对结果影响很大。需要对数据进行归一化处理，将所有特征值缩放到相同的范围（如0 - 1或 - 1到1）。常用的归一化方法有最小 - 最大归一化 ((x - \text{min})/(\text{max} - \text{min})) 和Z - score标准化 ((x - \mu)/\sigma)，其中 (\mu) 是均值，(\sigma) 是标准差。
- 去除噪声数据：噪声数据可能会干扰KNN算法的预测结果，因此需要通过数据清洗等方法去除噪声数据。
- 计算距离
- 对于每个测试样本，计算其与训练集中所有样本之间的距离。根据选择的距离度量方式（如欧氏距离、曼哈顿距离等），计算每个样本之间的距离值。
- 选择最近的K个邻居
- 根据计算出的距离，对训练集中的样本进行排序，选择距离最近的K个样本作为目标点的邻居。
- 投票或平均
- 对于分类问题，统计这K个邻居中每个类别的数量，选择数量最多的类别作为预测结果；对于回归问题，计算这K个邻居的值的平均值或加权平均值作为预测结果。
四、优缺点
- 优点
- 简单易实现：KNN算法原理简单，实现起来也非常容易，不需要复杂的数学推导和优化过程。
- 无需训练模型：KNN算法不需要像其他算法（如神经网络、决策树等）那样进行复杂的模型训练，直接基于数据点之间的距离进行预测，适合小规模数据集。
- 对数据的适应性强：KNN算法对数据的分布没有假设，可以很好地适应各种类型的数据，包括线性和非线性数据。
- 缺点
- 计算效率低：KNN算法需要计算测试样本与训练集中所有样本之间的距离，对于大规模数据集，计算量非常大，效率较低。
- 存储要求高：KNN算法需要存储整个训练数据集，占用大量的存储空间。
- 对特征的权重不敏感：KNN算法对所有特征一视同仁，没有考虑不同特征对目标变量的重要性，可能会受到无关特征的干扰。
五、应用场景
- 图像识别：KNN算法可以用于图像分类任务，例如手写数字识别。通过计算图像像素之间的距离，可以将新的图像与已知的数字图像进行对比，从而识别出数字的类别。
- 文本分类：在文本分类中，KNN算法可以用于判断文本的类别。例如，将文本转换为向量形式（如TF - IDF向量），然后计算文本之间的距离，根据最近的K个邻居的类别来判断文本的类别。
- 推荐系统：KNN算法可以用于基于用户的推荐系统。通过计算用户之间的相似度（如购买行为、评分等），找到与目标用户最相似的K个用户，然后将这些用户喜欢的物品推荐给目标用户。
六、代码实现（Python示例）
以下是使用Python实现KNN算法的简单示例：
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
# 示例数据
X = [[0], [1], [2], [3]]
y = [0, 0, 1, 1]
# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=42)
# 创建KNN模型
knn = KNeighborsClassifier(n_neighbors=3)
# 训练模型
knn.fit(X_train, y_train)
# 进行预测
y_pred = knn.predict(X_test)
# 计算准确率
accuracy = accuracy_score(y_test, y_pred)
print(f"准确率：{accuracy}")
七、总结
KNN算法是一种简单而有效的机器学习算法，适用于分类和回归任务。它基于数据点之间的距离进行预测，具有简单易实现、对数据适应性强等优点，但也存在计算效率低、存储要求高等缺点。在实际应用中，需要根据数据的特点和任务需求选择合适的K值和距离度量方式，并对数据进行预处理，以提高算法的性能。