K最近邻算法
K 最近邻算法（KNN）：原理、应用与实现
K 最近邻算法（K-Nearest Neighbours，KNN）是一种简单直观的监督学习算法，核心思想是 “物以类聚”—— 通过样本周围最近的 K 个邻居的信息来预测其类别或数值。它无需训练过程，属于 “惰性学习”（Lazy Learning），适用于分类和回归任务。
KNN 的核心原理
基本思想
对于未知样本，KNN 通过以下步骤进行预测：
- 计算距离：计算未知样本与训练集中所有已知样本的距离（如欧氏距离、曼哈顿距离）。
- 找邻居：选取距离最近的K 个样本（K 为超参数，通常为奇数，如 3、5、7）。
- 投票 / 平均：
- 分类任务：K 个邻居中出现次数最多的类别即为未知样本的预测类别（多数投票）。
- 回归任务：K 个邻居的数值的平均值即为未知样本的预测值。
关键概念
- K 值选择：
- K 过小：易受噪声影响，模型过拟合（决策边界复杂）。
- K 过大：邻居中可能包含其他类别的样本，模型欠拟合（决策边界模糊）。
- 通常通过交叉验证选择最优 K 值（如 3、5）。
- 距离度量：
- 欧氏距离（最常用）：适用于连续特征，公式为 (d(x,y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2})。
- 曼哈顿距离：适用于高维数据，公式为 (d(x,y) = \sum_{i=1}^{n}|x_i - y_i|)。
KNN 的分类与回归应用
分类任务（离散结果）
示例：预测鸢尾花类别（Setosa、Versicolor、Virginica）。
- 已知样本：不同鸢尾花的花瓣长度、宽度等特征及对应类别。
- 未知样本：计算其与所有已知样本的距离，选最近的 5 个邻居，若其中 3 个为 Versicolor，则预测为 Versicolor。
回归任务（连续结果）
示例：预测房价。
- 已知样本：房屋面积、房间数等特征及对应房价。
- 未知样本：选最近的 5 个邻居，计算其房价的平均值作为预测值。
KNN 的实现步骤（以分类为例）
1. 数据准备
- 训练集：包含特征（如花瓣长度、宽度）和标签（如鸢尾花类别）。
- 未知样本：仅含特征，需预测标签。
2. 距离计算
以欧氏距离为例，计算未知样本与每个训练样本的距离：
// 计算两个样本的欧氏距离（features1和features2为特征数组）
public static double euclideanDistance(double[] features1, double[] features2) {
double sum = 0.0;
for (int i = 0; i < features1.length; i++) {
sum += Math.pow(features1[i] - features2[i], 2);
}
return Math.sqrt(sum);
}3. 寻找 K 个最近邻居
- 对所有距离排序，选取前 K 个最小距离对应的样本。
4. 多数投票预测
- 统计 K 个邻居中出现次数最多的类别，作为未知样本的预测结果。
完整代码示例（简化版）
import java.util.*;
public class KNNClassifier {
private List<double[]> trainFeatures; // 训练集特征
private List<String> trainLabels; // 训练集标签
private int k; // K值
public KNNClassifier(List<double[]> features, List<String> labels, int k) {
this.trainFeatures = features;
this.trainLabels = labels;
this.k = k;
}
// 预测单个样本的类别
public String predict(double[] sample) {
// 1. 计算与所有训练样本的距离
List<DistanceLabel> distances = new ArrayList<>();
for (int i = 0; i < trainFeatures.size(); i++) {
double dist = euclideanDistance(sample, trainFeatures.get(i));
distances.add(new DistanceLabel(dist, trainLabels.get(i)));
}
// 2. 按距离排序，取前K个邻居
Collections.sort(distances);
List<String> topKLabels = new ArrayList<>();
for (int i = 0; i < k; i++) {
topKLabels.add(distances.get(i).label);
}
// 3. 多数投票
return majorityVote(topKLabels);
}
// 欧氏距离计算
private double euclideanDistance(double[] a, double[] b) {
double sum = 0.0;
for (int i = 0; i < a.length; i++) {
sum += Math.pow(a[i] - b[i], 2);
}
return Math.sqrt(sum);
}
// 多数投票
private String majorityVote(List<String> labels) {
Map<String, Integer> count = new HashMap<>();
for (String label : labels) {
count.put(label, count.getOrDefault(label, 0) + 1);
}
// 找到出现次数最多的标签
return count.entrySet().stream()
.max(Map.Entry.comparingByValue())
.get()
.getKey();
}
// 辅助类：存储距离和对应的标签
private static class DistanceLabel implements Comparable<DistanceLabel> {
double distance;
String label;
DistanceLabel(double distance, String label) {
this.distance = distance;
this.label = label;
}
public int compareTo(DistanceLabel other) {
return Double.compare(this.distance, other.distance);
}
}
// 测试
public static void main(String[] args) {
// 训练集：假设为鸢尾花数据（特征：花瓣长度、宽度）
List<double[]> features = Arrays.asList(
new double[]{1.4, 0.2}, // Setosa
new double[]{1.3, 0.2}, // Setosa
new double[]{4.5, 1.5}, // Versicolor
new double[]{4.9, 1.5}, // Versicolor
new double[]{6.0, 2.5} // Virginica
);
List<String> labels = Arrays.asList("Setosa", "Setosa", "Versicolor", "Versicolor", "Virginica");
// 初始化KNN分类器（K=3）
KNNClassifier knn = new KNNClassifier(features, labels, 3);
// 预测未知样本（花瓣长度2.0，宽度0.3）
double[] sample = {2.0, 0.3};
System.out.println("预测类别：" + knn.predict(sample)); // 输出：Setosa
}
}KNN 的优缺点与优化
优点
- 简单直观：无需训练过程，易于理解和实现。
- 适应性强：可处理多分类问题，且对异常值不敏感（当 K 较大时）。
- 无需假设数据分布：适用于非线性数据。
缺点
- 计算成本高：预测时需与所有训练样本计算距离，时间复杂度为 O (n)（n 为训练样本数），不适用于大规模数据。
- 对 K 值敏感：K 值选择不当会严重影响结果。
- 受特征尺度影响：如 “身高（米）” 和 “体重（千克）” 的尺度差异会导致距离计算偏差，需先标准化特征。
优化方向
- 降维：减少特征数量（如 PCA），降低距离计算成本。
- KD 树 / 球树：高效的近邻搜索数据结构，加速 KNN 查询。
- 特征标准化：将所有特征缩放到同一尺度（如 Z-score 标准化）。
适用场景
- 小规模数据集（如医学诊断、客户分类）。
- 对模型可解释性要求高的场景（邻居可直观展示决策依据）。
- 非线性问题（如手写数字识别、推荐系统）。
总结
KNN 是一种 “懒惰却有效” 的算法，通过 “近朱者赤” 的逻辑实现预测，无需复杂的训练过程。其核心在于 K 值选择和距离度量，适用于小规模、非线性的数据任务。尽管计算效率较低，但凭借简单性和适应性，KNN 在实际应用中仍被广泛使用（如推荐系统、模式识别）