引言
k近邻算法（k-Nearest Neighbors，简称KNN）是一种直观且易于理解的监督学习算法。它的核心思想非常简单：相似的样本在特征空间中距离更近。本文将通过手写数字识别这一经典场景，用Java完整实现KNN算法，并深入讲解欧氏距离、曼哈顿距离等度量方法。
算法原理
KNN算法的分类决策过程可分为三步：
- 计算距离：对于待分类样本，计算它与训练集中每个样本的距离
- 选取邻居：按距离从小到大排序，选取前k个最近邻样本
- 投票决策：统计k个邻居中各类别的出现次数，出现最多的类别即为预测结果
距离度量是KNN的核心。最常用的欧氏距离公式为：
$$d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i – y_i)^2}$$
手写数字数据集设计
为了便于演示，我们设计一个简化的8×8像素手写数字数据集。每个数字用8行8列的0和1表示，其中1表示笔画经过的像素。
/**
* 手写数字样本类
* 每个样本包含64维特征向量（8x8像素展平）和标签（0-9）
*/
public class DigitSample {
public final double[] features; // 64维特征
public final int label; // 真实数字标签
public DigitSample(double[] features, int label) {
this.features = features;
this.label = label;
}
}
KNN分类器核心实现
import java.util.*;
/**
* KNN分类器
* 支持欧氏距离和曼哈顿距离两种度量方式
*/
public class KNNClassifier {
private final List<DigitSample> trainSet;
private final int k;
private final DistanceMetric metric;
/**
* 距离度量接口，便于扩展不同的距离计算方式
*/
public interface DistanceMetric {
double compute(double[] a, double[] b);
}
// 欧氏距离实现
public static final DistanceMetric EUCLIDEAN = (a, b) -> {
double sum = 0.0;
for (int i = 0; i < a.length; i++) {
double diff = a[i] - b[i];
sum += diff * diff;
}
return Math.sqrt(sum);
};
// 曼哈顿距离实现
public static final DistanceMetric MANHATTAN = (a, b) -> {
double sum = 0.0;
for (int i = 0; i < a.length; i++) {
sum += Math.abs(a[i] - b[i]);
}
return sum;
};
public KNNClassifier(List<DigitSample> trainSet, int k, DistanceMetric metric) {
if (k <= 0 || k > trainSet.size()) {
throw new IllegalArgumentException("k值必须在1到训练集大小之间");
}
this.trainSet = new ArrayList<>(trainSet);
this.k = k;
this.metric = metric;
}
/**
* 预测单个样本的类别
*/
public int predict(double[] features) {
// 使用优先队列维护最近的k个邻居，按距离升序
PriorityQueue<Neighbor> maxHeap = new PriorityQueue<>(
(a, b) -> Double.compare(b.distance, a.distance)
);
for (DigitSample sample : trainSet) {
double dist = metric.compute(features, sample.features);
maxHeap.offer(new Neighbor(sample.label, dist));
if (maxHeap.size() > k) {
maxHeap.poll(); // 移除距离最远的邻居
}
}
// 统计k个邻居中各标签的出现次数
int[] votes = new int[10];
for (Neighbor n : maxHeap) {
votes[n.label]++;
}
// 找出得票最多的标签
int bestLabel = 0;
int maxVotes = -1;
for (int i = 0; i < votes.length; i++) {
if (votes[i] > maxVotes) {
maxVotes = votes[i];
bestLabel = i;
}
}
return bestLabel;
}
/**
* 评估模型在测试集上的准确率
*/
public double evaluate(List<DigitSample> testSet) {
int correct = 0;
for (DigitSample sample : testSet) {
int pred = predict(sample.features);
if (pred == sample.label) {
correct++;
}
}
return (double) correct / testSet.size();
}
private static class Neighbor {
final int label;
final double distance;
Neighbor(int label, double distance) {
this.label = label;
this.distance = distance;
}
}
}
数据加载与预处理
/**
* 手写数字数据集加载器
* 生成模拟的8x8像素数字图像数据
*/
public class DigitDataset {
/**
* 生成训练集和测试集
* 每个数字生成多组带随机噪声的样本
*/
public static List<DigitSample>[] loadDataset(int samplesPerDigit, double noiseRate) {
List<DigitSample> allSamples = new ArrayList<>();
Random rand = new Random(42); // 固定随机种子保证可复现
// 基础数字模板（简化版8x8）
double[][][] templates = generateTemplates();
for (int digit = 0; digit <= 9; digit++) {
for (int s = 0; s < samplesPerDigit; s++) {
double[] features = templates[digit].clone();
// 添加随机噪声模拟手写差异
for (int i = 0; i < features.length; i++) {
if (rand.nextDouble() < noiseRate) {
features[i] = features[i] > 0.5 ? 0.0 : 1.0;
}
}
allSamples.add(new DigitSample(features, digit));
}
}
// 随机打乱并划分训练集(80%)和测试集(20%)
Collections.shuffle(allSamples, rand);
int split = (int) (allSamples.size() * 0.8);
List<DigitSample> trainSet = new ArrayList<>(allSamples.subList(0, split));
List<DigitSample> testSet = new ArrayList<>(allSamples.subList(split, allSamples.size()));
@SuppressWarnings("unchecked")
List<DigitSample>[] result = new List[2];
result[0] = trainSet;
result[1] = testSet;
return result;
}
/**
* 生成简化的数字模板（8x8=64维）
*/
private static double[][] generateTemplates() {
double[][][] raw = {
{ // 0
{0,1,1,1,1,1,1,0},
{1,1,0,0,0,0,1,1},
{1,1,0,0,0,0,1,1},
{1,1,0,0,0,0,1,1},
{1,1,0,0,0,0,1,1},
{1,1,0,0,0,0,1,1},
{1,1,0,0,0,0,1,1},
{0,1,1,1,1,1,1,0}
},
{ // 1
{0,0,0,1,1,0,0,0},
{0,0,1,1,1,0,0,0},
{0,0,0,1,1,0,0,0},
{0,0,0,1,1,0,0,0},
{0,0,0,1,1,0,0,0},
{0,0,0,1,1,0,0,0},
{0,0,0,1,1,0,0,0},
{0,1,1,1,1,1,1,0}
},
{ // 2
{0,1,1,1,1,1,1,0},
{1,1,0,0,0,0,1,1},
{0,0,0,0,0,0,1,1},
{0,0,0,0,0,1,1,0},
{0,0,0,1,1,0,0,0},
{0,1,1,0,0,0,0,0},
{1,1,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1}
},
{ // 3
{0,1,1,1,1,1,1,0},
{1,1,0,0,0,0,1,1},
{0,0,0,0,0,0,1,1},
{0,0,0,1,1,1,1,0},
{0,0,0,0,0,0,1,1},
{0,0,0,0,0,0,1,1},
{1,1,0,0,0,0,1,1},
{0,1,1,1,1,1,1,0}
},
{ // 4
{0,0,0,0,1,1,0,0},
{0,0,0,1,1,1,0,0},
{0,0,1,1,0,1,0,0},
{0,1,1,0,0,1,0,0},
{1,1,0,0,0,1,0,0},
{1,1,1,1,1,1,1,1},
{0,0,0,0,0,1,0,0},
{0,0,0,0,0,1,0,0}
},
{ // 5
{1,1,1,1,1,1,1,1},
{1,1,0,0,0,0,0,0},
{1,1,0,0,0,0,0,0},
{1,1,1,1,1,1,1,0},
{0,0,0,0,0,0,1,1},
{0,0,0,0,0,0,1,1},
{1,1,0,0,0,0,1,1},
{0,1,1,1,1,1,1,0}
},
// 6-9省略，实际使用时补充完整
};
double[][] result = new double[10][64];
for (int d = 0; d < Math.min(10, raw.length); d++) {
int idx = 0;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
result[d][idx++] = raw[d][i][j];
}
}
}
return result;
}
}
主程序与测试
public class KNNMain {
public static void main(String[] args) {
// 加载数据集：每个数字20个样本，噪声率10%
List<DigitSample>[] datasets = DigitDataset.loadDataset(20, 0.1);
List<DigitSample> trainSet = datasets[0];
List<DigitSample> testSet = datasets[1];
System.out.println("训练集大小: " + trainSet.size());
System.out.println("测试集大小: " + testSet.size());
// 测试不同的k值
int[] kValues = {1, 3, 5, 7, 9};
for (int k : kValues) {
KNNClassifier knn = new KNNClassifier(trainSet, k, KNNClassifier.EUCLIDEAN);
double accuracy = knn.evaluate(testSet);
System.out.printf("k=%d 时，欧氏距离准确率: %.2f%%%n", k, accuracy * 100);
}
// 对比曼哈顿距离
KNNClassifier manhattanKnn = new KNNClassifier(trainSet, 5, KNNClassifier.MANHATTAN);
double manhattanAcc = manhattanKnn.evaluate(testSet);
System.out.printf("k=5 时，曼哈顿距离准确率: %.2f%%%n", manhattanAcc * 100);
}
}
复杂度分析
| 阶段 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 训练阶段 | O(1) | O(n*d) |
| 预测阶段 | O(nd + nlog(k)) | O(k) |
| 批量评估 | O(mnd) | O(k) |
其中n为训练样本数，d为特征维度，m为测试样本数，k为邻居数。
总结
KNN算法的优点在于简单直观、无需训练过程、对数据分布没有假设。缺点也很明显：预测时需要遍历整个训练集，时间开销大；对高维数据效果差（维度灾难）；对异常值敏感。实际应用中，可以结合k-d树、球树等空间索引结构加速近邻搜索。
