K临近算法，圈内通常叫KNN（K-Nearest Neighbors），可能是机器学习里最不讲道理、却又非常好用的一个算法。它的全部逻辑用一句话就能概括：想知道一个未知样本属于哪一类，就去看它周围最近的K个已知样本，哪个类别的邻居最多，它就属于哪个类别。

这篇是面向Java开发者的机器学习入门第一篇。我会用纯Java、不依赖任何第三方机器学习框架，从零实现一个可用于实际预测的KNN分类器，并且在代码里把归一化、K值选择、距离计算、平票处理这些细节全部讲透。适合两类人阅读：一是刚啃完Java基础语法、想看看机器学习到底在做什么的初学者；二是日常业务里需要一个可解释性强、训练成本低的基线分类器，但不想上来就引入一堆复杂依赖的后端开发者。KNN还有一个别名值得提前说清楚：它也叫“惰性学习”算法，因为它几乎没有传统意义上的“训练”过程，模型在预测时才真正开始干活。理解这一点，是后面读懂整个实现的关键。

1. KNN的原理：为什么“物以类聚”能当算法用

1.1 三步拆解：找邻居、算距离、做投票

KNN的运行过程听起来特别像一个“看朋友圈下结论”的行为。假设你第一次来到一个陌生的小区，想知道周边最近的商场属于哪个商圈，你问了一圈周围五个邻居，四个人告诉你属于东商圈，一个人说属于西商圈，你大概率会跟着多数人的意见走。KNN干的事完全一致。

把它翻译成计算机语言，就是三个步骤。

第一步，确定K值。K代表你要询问多少个已知样本，也就是邻居数量。

第二步，计算待预测样本和所有已知样本之间的距离。距离是KNN最核心的数学工具，通常用欧氏距离，也就是初中几何里学过的“两点间直线距离”的推广。

第三步，从全部训练样本中挑出距离最近的K个，对这K个邻居的标签做投票——出现次数最多的那个类别，就被预测为待测样本的类别。

这里有一个容易忽略的关键点：KNN是典型的监督学习。它要求所有训练样本都带有明确的标签，也就是每个样本“属于哪一类”是已知的。没有标签的数据集，KNN无从学起。它也是非参数模型，因为模型结构不固定，不像是线性回归那样有确定的系数方程，KNN的“模型”本质上就是全部训练数据本身。

1.2 K值、距离、决策规则：三个旋钮决定效果

KNN的效果好不好，几乎完全取决于三个旋钮怎么拧。

第一个旋钮是K值。K太小，比如K=1，模型会非常敏感，一个离群点就能把预测结果带偏，这在机器学习里叫过拟合，模型把噪声也学进去了。K太大，比如K等于训练样本总数，那预测结果永远是全数据集中最多数的那个类别，这叫欠拟合，模型丧失了对局部特征的判断力。实际工程里常用的经验法是取约为总样本量的平方根，然后在这个附近用交叉验证微调。

第二个旋钮是距离度量。欧氏距离适合数值型、各维度重要性均衡的特征；曼哈顿距离更抗个别维度上的极端值扰动；余弦相似度则更适合文本、用户行为这类高维稀疏向量。入门阶段先用欧氏距离，等真正理解了特征空间，再去扩展其他距离。

第三个旋钮是决策规则。最简单的就是等权投票：K个邻居一人一票，票高者胜。进阶一点的做法是加权投票，距离越近的邻居话语权越大，通常用距离的倒数做权重。等权投票实现简单，但遇到邻居分布刚好卡在类别边界时容易出问题；加权投票稳定一些，代价是多算几步除法。

理解这三个旋钮，比直接抄代码重要。因为后面所有调参、踩坑，本质上都是在回答“这三个旋钮分别应该拧到什么位置”这个问题。

2. 动手前的设计：四件事想清楚再敲代码

2.1 特征怎么表示：double[] 和 DataItem 类

KNN处理的是特征空间中的点，所以物体必须先被转化成数值向量。以花分类为例：一朵花可以被描述成花萼长度、花萼宽度、花瓣长度、花瓣宽度四个数值，这四维数值就是它的“指纹”，机器学习圈统一叫特征向量。

在Java里，特征向量最直接的表示就是double[]。为什么不用Map或者Object？因为距离计算需要大量、高效地遍历每个维度做减法、平方、求和，数组在内存上是连续存储的，访问性能最好；Map有装箱开销，Object还要反射，都不合适。

对应地，我写一个DataItem类来封装一条训练样本。它包含三个基本字段：id用来追踪样本来源，features是double[]，label是String类型的真实类别。再预留一个predictedLabel字段，用来在预测后回填结果，方便事后算准确率。

public class DataItem { private final String id; private final double[] features; private final String label; private String predictedLabel; public DataItem(String id, double[] features, String label) { this.id = id; this.features = features; this.label = label; } public String getId() { return id; } public double[] getFeatures() { return features; } public String getLabel() { return label; } public String getPredictedLabel() { return predictedLabel; } public void setPredictedLabel(String predictedLabel) { this.predictedLabel = predictedLabel; } @Override public String toString() { return "DataItem{id='" + id + "', label='" + label + "', predicted='" + predictedLabel + "'}"; } }

所有训练样本放进List 。List比数组好用的地方在于支持动态扩容，读取数据集时不必预先知道样本总数，也方便后续做随机打乱和划分训练／测试集。

2.2 距离计算前必须先归一化

假设特征里有身高（单位厘米，数值范围150-200）和体重（单位斤，数值范围80-200），还有月收入（单位元，数值范围几千到几万）。如果不做任何处理就直接计算欧氏距离，会出现一个结果：距离几乎完全被月收入这一个维度主导，身高和体重的作用变得微乎其微。这显然不是我们想要的，因为每个特征都应该对“像不像”有一定投票权，而不是只看量纲大的维度。

解决办法叫归一化，常见的有Min-Max归一化和Z-Score标准化。

Min-Max归一化把所有特征压缩到0到1之间，公式是：(数值 - 最小值) / (最大值 - 最小值)。它保留了原始分布的相对结构，实现简单，是KNN场景的首选。

Z-Score标准化把特征变成均值为0、方差为1的分布，公式是：(数值 - 均值) / 标准差。它更适合特征近似正态分布、且存在极端离群值的场景。

我在这里先实现Min-Max。注意一个关键细节：归一化只能在训练集上计算最小值和最大值，然后用这套参数去转换测试集，绝不能把训练集和测试集混在一起计算，那会引入信息泄漏，导致评估结果虚高。

2.3 K值选择与平票的预判

K值不是拍脑袋定的。入门阶段我会先用两个规则框出候选范围：其一，K取奇数，这样在二分类场景下天然避免平票；其二，K大约等于训练样本数的平方根。然后在这个范围里尝试几个值，用验证集准确率挑最好的。

但平票依然可能出现，尤其在多分类场景。K等于某个偶数，或者三类样本正好在邻域里各占一票，都可能打平。我准备了三个兜底方案：方案一是直接随机挑一个赢家，简单但不可复现；方案二是看平票类别中所有邻居的总距离，谁的距离和更小谁赢，这个更讲道理；方案三是升级为加权投票，从机制上消除硬平票。后续代码里我用方案二，因为实现不难，效果比随机好。

2.4 工程结构：不引第三方依赖

整个实现只依赖JDK标准库，连JDBC都不需要。读取数据我直接基于java.io和java.nio自己写CSV解析。这样做一是方便新人阅读，不需要先了解OpenCSV的API；二是KNN框架本身很小，不应该为一个小功能引入一堆依赖。

规划好的包结构大概是这样的：

• knn.demo.DataItem：样本封装
• knn.demo.MinMaxScaler：归一化器
• knn.demo.KnnClassifier：分类器主体
• knn.demo.Main：示例入口

3. 核心实现：动手写一个可用的KNN分类器

3.1 数据读取与划分

假设数据存在CSV文件里：每行是一条样本，最后一列是类别标签，前面的列都是数值型特征。下面是一个手工解析器，它同时完成数据读取和随机打乱：

public static List<DataItem> loadCsv(String path) throws IOException { List<DataItem> items = new ArrayList<>(); List<String> lines = Files.readAllLines(Paths.get(path)); // 跳过表头 for (int row = 1; row < lines.size(); row++) { String line = lines.get(row).trim(); if (line.isEmpty()) { continue; } String[] parts = line.split(","); double[] features = new double[parts.length - 1]; for (int i = 0; i < features.length; i++) { features[i] = Double.parseDouble(parts[i].trim()); } String label = parts[parts.length - 1].trim(); items.add(new DataItem("row-" + row, features, label)); } Collections.shuffle(items, new Random(42)); return items; }

随机打乱并固定随机种子，是为了让每次运行的结果可复现，不然你排查问题时可能发现这次准确率80%，下次变成70%，完全不知道怎么定位。固定种子是机器学习实践里非常基础但重要的习惯。

划分数据集用留出法。我按80%训练、20%测试切分，最简单的划分代码是这样：

public static List<List<DataItem>> split(List<DataItem> items, double trainRatio) { int trainSize = (int) (items.size() * trainRatio); List<DataItem> trainItems = new ArrayList<>(items.subList(0, trainSize)); List<DataItem> testItems = new ArrayList<>(items.subList(trainSize, items.size())); return Arrays.asList(trainItems, testItems); }

3.2 归一化器实现

MinMaxScaler的fit方法只做一件事：扫描训练集，记录每个特征维度的最小值和最大值。transform方法负责把一组特征压缩到0-1区间。

public class MinMaxScaler { private double[] minValues; private double[] maxValues; public void fit(List<DataItem> trainItems) { int dim = trainItems.get(0).getFeatures().length; minValues = new double[dim]; maxValues = new double[dim]; Arrays.fill(minValues, Double.MAX_VALUE); Arrays.fill(maxValues, -Double.MAX_VALUE); for (DataItem item : trainItems) { double[] f = item.getFeatures(); for (int i = 0; i < dim; i++) { minValues[i] = Math.min(minValues[i], f[i]); maxValues[i] = Math.max(maxValues[i], f[i]); } } } public double[] transform(double[] features) { double[] res = new double[features.length]; for (int i = 0; i < features.length; i++) { if (maxValues[i] == minValues[i]) { res[i] = 0.0; } else { res[i] = (features[i] - minValues[i]) / (maxValues[i] - minValues[i]); } } return res; } }

这里有一个非常容易踩的坑：如果某个特征在所有样本里都是同一个值，比如花色的“色号”永远一样，那么max减min等于0，直接除会得Infinity。我这里的处理方式是把这类特征置为0，相当于告诉算法这个维度没有区分度，直接忽略。另一种更稳妥的做法是干脆从特征向量里去掉这种常量维度。

3.3 欧氏距离的计算

欧氏距离是KNN距离计算的主力。它的Java实现不复杂，但有一个值得注意的性能细节：把乘法写成diff * diff，而不是Math.pow(diff, 2)。Math.pow处理的是通用幂运算，内部开销比一次乘法大得多，在几万次距离计算中差距会被放大很多倍。

public static double euclideanDistance(double[] a, double[] 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); }

如果只想比较距离大小、不需要精确值，可以省略Math.sqrt。因为欧氏距离的平方函数是单调递增的，距离越大，平方也越大。“找最近K个邻居”本质上只关心相对大小，不关心绝对大小，省掉开方能减少一部分计算量。不过我认为入门阶段保留开方更直观，后面优化再说。

3.4 Top-K近邻查找：从全排序到堆优化

最朴素的做法：计算待预测样本和所有训练样本的距离，存入列表，按距离从小到大排序，取前K个。代码极短：

List<Neighbor> all = new ArrayList<>(); for (DataItem trainItem : trainItems) { double dist = euclideanDistance(testFeatures, trainItem.getFeatures()); all.add(new Neighbor(trainItem, dist)); } all.sort(Comparator.comparingDouble(n -> n.distance)); List<Neighbor> kNeighbors = all.subList(0, K);

问题在于复杂度。排序是O(n log n)，当训练数据有10万条时，每预测一条样本都要做10万次距离计算和一次大排序，预测1000条样本就变成了千万级的计算量。这在学术Demo里没问题，线上服务就吃力了。

优化思路是用优先级队列维护一个大小为K的“最有近邻”窗口。PriorityQueue默认是最小堆，堆顶是所有元素中最小的。我们要的是保留K个距离最小的，所以传入参数，让比较器把距离大的放在堆顶，这样堆顶不断被挤掉，堆里留下的永远是当前遍历过的最小的K个。

PriorityQueue<Neighbor> heap = new PriorityQueue<>(K, (n1, n2) -> Double.compare(n2.distance, n1.distance)); for (DataItem trainItem : trainItems) { double dist = euclideanDistance(testFeatures, trainItem.getFeatures()); heap.offer(new Neighbor(trainItem, dist)); if (heap.size() > K) { heap.poll(); } } List<Neighbor> kNeighbors = new ArrayList<>(heap);

这个版本的时间复杂度是O(n log K)。当K远小于n时，性能优势非常明显。KNN在机器学习里一直被诟病“预测慢”，工程师应该从这种细节开始抠性能。

Neighbor类就两个字段，一个DataItem一个distance，再写一个简单构造器。

3.5 投票决策与分类器主流程

拿到K个邻居之后，统计每个类别出现的次数，找最大值。我加了一个平票回退逻辑：如果两个类别出现次数相同，就比较它们在K个邻居内的总距离，和更小的那类作为预测结果。距离和更小，意味着这个类别的邻居整体上更“抱团”地贴近待测样本，语义上更可信。

public String predict(double[] rawFeatures) { double[] features = scaler.transform(rawFeatures); List<Neighbor> neighbors = findKNearest(features, K); Map<String, Integer> voteCount = new HashMap<>(); Map<String, Double> voteDist = new HashMap<>(); for (Neighbor nb : neighbors) { String label = nb.item.getLabel(); voteCount.put(label, voteCount.getOrDefault(label, 0) + 1); voteDist.put(label, voteDist.getOrDefault(label, 0.0) + nb.distance); } String bestLabel = null; int bestCount = -1; double bestDist = Double.MAX_VALUE; for (Map.Entry<String, Integer> entry : voteCount.entrySet()) { int count = entry.getValue(); double dist = voteDist.get(entry.getKey()); if (count > bestCount || (count == bestCount && dist < bestDist)) { bestLabel = entry.getKey(); bestCount = count; bestDist = dist; } } return bestLabel; }

KnnClassifier的完整结构就是三大块：构造时需要传入K和训练集；fit阶段对训练集做归一化并保存数据；predict阶段做距离计算和投票。注意KNN的fit没有任何迭代求解过程，所谓训练只是把归一化参数算好、数据存好而已。

public class KnnClassifier { private final int K; private final List<DataItem> trainItems; private final MinMaxScaler scaler; public KnnClassifier(int K, List<DataItem> trainItems) { this.K = K; this.trainItems = new ArrayList<>(trainItems); this.scaler = new MinMaxScaler(); this.scaler.fit(this.trainItems); } }

4. 跑通完整示例：花分类数据集上的预测

4.1 构造一个迷你数据集

为了让代码可以直接运行、不需要下载外部文件，我在Main里手工构造一个小型花分类数据集。四维特征：花萼长度、花萼宽度、花瓣长度、花瓣宽度。类别三种：花型A、花型B、花型C。每种花型各放8条样本，共24条，训练集20条、测试集4条。

部分数据长这样：

手工构造数据时有个原则：三个类别的特征分布要错开，不然模型很难学出有意义的东西。A的花瓣短，B的适中，C的花瓣明显更长，这样KNN才有得玩。

4.2 主流程：训练、预测、评估一条龙

Main方法的流程是：加载数据、打乱、切分训练测试集、构造分类器、对每个测试样本调用predict、比对真实标签、累计正确数并输出准确率。

public static void main(String[] args) throws IOException { List<DataItem> items = loadCsv("iris-demo.csv"); List<List<DataItem>> split = split(items, 0.8); List<DataItem> trainItems = split.get(0); List<DataItem> testItems = split.get(1); KnnClassifier classifier = new KnnClassifier(3, trainItems); int correct = 0; for (DataItem testItem : testItems) { String predicted = classifier.predict(testItem.getFeatures()); testItem.setPredictedLabel(predicted); if (predicted.equals(testItem.getLabel())) { correct++; } System.out.printf("样本%s 真实=%s 预测=%s%n", testItem.getId(), testItem.getLabel(), predicted); } double accuracy = (double) correct / testItems.size(); System.out.printf("准确率: %.2f%%%n", accuracy * 100); }

在数据上跑一遍，K=3、训练集20条、测试集4条时，我的模拟结果是：3条预测正确，1条花型B被误判为花型C，准确率75%。这个成绩对于一个只有20条样本的迷你数据集来说完全合格。初学者看到准确率不是100%反而应该高兴，因为这说明模型没有把训练数据硬背下来，而是学会了某种可泛化的边界。

4.3 用K值变化观察模型行为

我在同一份数据上把K分别设成1、3、5、7、9，记录测试集准确率：

这就是我前面讲的欠拟合在真实数据上的呈现。随着K变大，模型越来越不关心“最近的邻居”，越来越像“全体投票”，最终退化成永远预测样本量最大的类别。动手跑一遍这个实验，对理解和调参会很有帮助。

5. 进阶优化：让KNN从“能跑”变成“好用”

5.1 距离度量的扩展：曼哈顿距离和加权投票

欧氏距离不是万能药。在某些场景下，比如特征维度之间有较强相关性，或者个别维度噪声很大，曼哈顿距离反而更鲁棒。

public static double manhattanDistance(double[] a, double[] b) { double sum = 0.0; for (int i = 0; i < a.length; i++) { sum += Math.abs(a[i] - b[i]); } return sum; }

曼哈顿距离对单维度上的突变没有欧氏那么敏感，因为不经过平方放大。高阶一点的还有闵可夫斯基距离，它把欧氏（p=2）和曼哈顿（p=1）统一在一个公式里。入门阶段不急着全实现，但要留出扩展口子——预测方法里加一个距离计算函数作为参数，之后换距离度量就不用改主流程。

加权投票是另一个高性价比的增强。把一人一票改成按距离倒数加权：

double weight = 1.0 / (nb.distance + 1e-10); voteWeight.put(label, voteWeight.getOrDefault(label, 0.0) + weight);

这里加一个极小值1e-10是为了防止距离恰好是0时除零异常。加权投票让更近的邻居拥有更大话语权，避免了“远处三个邻居把近处一个邻居的票数压过”这种不公平局面，实际用下来准确率经常会有一两个百分点的提升。

5.2 性能优化：KD-Tree、缓存与并行预测

朴素的KNN预测一条样本要遍历全部训练集。如果训练集有5万条、特征10维，线上每秒预测100次，CPU压力非常大。工程上可以从三个方向优化。

第一个方向是KD-Tree。它把特征空间按维度递归切分成二叉树，预测时只需要搜索与查询点临近的叶子区域，平均复杂度可以降到O(log n)。代价是KD-Tree在高维空间（特征大于20维）下退化严重，那时要用Ball Tree或近似最近邻。这一块是实现量级很大的优化，入门阶段了解思路即可，不需要七天之内自己写出来。

第二个方向是缓存。如果同一批特征向量要多次预测，或者一批样本共用邻居关系，可以缓存部分中间结果。但KNN的“缓存命中率”通常不高，因为测试样本各不相同，缓存收益有限，真正有效的还是配合KD-Tree做剪枝缓存。

第三个方向是并行化。预测不同测试样本互不干扰，天然适合并行。用Java的parallelStream或线程池可以轻松榨干多核CPU：

testItems.parallelStream().forEach(item -> { String predicted = classifier.predict(item.getFeatures()); item.setPredictedLabel(predicted); });

注意，parallelStream共享同一个KnnClassifier实例时，如果分类器内部有可变状态，会有线程安全问题。上面设计的分类器predict方法只读取训练集，不修改内部状态（predictedLabel是回填到测试样本上），所以是线程安全的。这个设计不是碰巧，而是在写的时候特意保证了只读性。

5.3 特征工程的补充：离散特征与类别特征怎么处理

数值型特征可以直接用，但现实业务里经常碰到颜色、地区、职业这类离散特征。KNN不能直接算它们之间的距离，因为“北京”和“上海”没有数值上的大小关系。

标准做法叫One-Hot编码。假设“地区”有华北、华东、华南三个取值，就把它拆成三个维度，样本属于哪个地区，对应维度就置1，其余置0。这样“华北”变成[1,0,0]，“华东”变成[0,1,0]，它们之间的距离都是√2，彼此平等，不存在人为的大小顺序。

One-Hot之后特征维度会明显膨胀，这正是KD-Tree在高维场景失效的原因之一。所以做特征工程时要冷静，不是所有离散特征都值得One-Hot，取值特别多的特征，比如用户ID，就不要拿来喂KNN了，没有任何泛化意义。KNN本身对冗余特征也有点敏感，两三个强相关特征放在一起，等于那个信息被重复计权，实际使用时建议先做简单特征筛选，比如剔除方差接近0的常量列。

6. 常见问题与排查实录

6.1 平票问题

问：K=4时，两个类别的邻居数都是2，怎么办？ 答：我实现了距离和回退，哪个类别的邻居总距离小就选哪个。如果你想改成随机，把predict方法里平票分支简化为随机选即可。但要注意，多分类平票时随机会带来结果不可复现，调试会变得困难。

6.2 归一化后新样本超出了0-1范围

问：训练集里花萼长度最大值是7.9，线上却来了一个8.5的样本，归一化后值是1.07，超过1了，正常吗？ 答：完全正常。Min-Max归一化不是把数据钳制在0-1里，只是做一个线性映射，超出训练集范围的新样本映射后自然可能溢出区间。算法层面没有问题，因为距离计算可以对任意实数坐标进行。如果不想让极端值过度拉偏距离，可以考虑用Z-Score，它对超出范围的值会受限更好一些。

6.3 类别不平衡导致公平性缺失

问：训练集里类别A有1000条，类别B只有50条，预测结果几乎总是A。 答：这就是KNN一个公认的短板。邻近区域内B的样本明明有3个，A的样本有4个，但A的总量远大于B，所以局部密度天然压过B。缓解策略有三个：一是调整K值，尽量让K小于少数类的数量级；二是改用距离加权投票，少数类如果靠得足够近，权重能扳回局面；三是为训练集做重采样，比如对少数类做简单复制或数据合成，但这属于另一个话题。入门阶段先知道原因，不要一上来就调K。

6.4 为什么我的准确率时好时坏？

这是我在社群答疑里见到最多的问题。九成情况都出在同一个地方：没有固定随机种子。数据划分、打乱顺序每次不同，训练集和测试集每次都不一样，准确率自然剧烈抖动。在划分函数里固定随机种子，是最简单也最容易被忽略的一步。第二个高发原因是忘了归一化，两个特征量纲相差百倍时，距离基本被大量纲维度主导，归一化前后准确率可以差出20个百分点以上。第三个原因是K选得太大或太小，照着平方根法则先试，再用验证集调一波，基本能定位。

6.5 Java边界情况：空值和数值溢出

CSV解析时会遇到缺值单元格。我用Double.parseDouble解析，缺值会导致NumberFormatException。实际项目中数据质量往往一言难尽，建议解析前检查是否为空字符串，是的话用特征均值填充，或者直接丢弃该样本。数值溢出方面，欧氏距离累加平方和理论上可能溢出double，但实际特征通常都是小数级别，几百个维度也不会溢出；真遇到超大值的场景，可以改成分段累加或中间做一次Math.hypot，不过入门阶段可以暂时不处理。

写在最后的一些建议

我第一次实现KNN时，踩得最狠的坑就是没做归一化。那时用两个特征做分类，一个范围0-1，一个范围几百到几千，怎么也调不出理想效果，后来才发现距离计算里小数值维度基本被淹没，等于模型瞎了一只眼。修好之后准确率立竿见影。从那以后我养成了习惯：任何特征进模型之前，先看数值范围，检视是否有量纲悬殊的问题，这比调K值重要得多。

如果你也在入门机器学习，我建议不要着急去啃KD-Tree和各种分布式框架，先把朴素KNN跑通，亲手改一改K值、换一换距离公式，观察结果的变化，这是最快建立直觉的路径。KNN虽然简单，但它把你带进了机器学习的核心思考方式：数据要怎么表示、距离怎么度量、结果怎么评估。把这三件事想明白了，后面学任何模型都会轻松很多。下一篇我会拿这个KNN分类器去处理一个真实的更大规模数据集，顺便聊一聊交叉验证怎么做才靠谱。