K-Nearest Neighbors

K-nearest neighbors, or KNN, classifies a query by first defining closeness through a distance rule and feature representation, then finding the k nearest labeled training points and combining their votes. It is a lazy learner: fitting mainly means storing the examples, while most computation happens when a prediction is requested.

What k controls

At k = 1, the label of the single nearest example determines the prediction. The plane is divided into ordinary Voronoi cells, so one mislabeled or noisy point can create a small island of predictions. With larger k, several neighbors vote and the boundary becomes less sensitive to any one example.

If k approaches the size of the dataset, local structure is averaged away and the majority class can dominate most of the space. KNN therefore has no learned coefficients, but it still has important hyperparameters: k, the distance metric, feature scaling, and whether nearby votes receive greater weight.

Small k often gives low bias and high variance. Large k often gives higher bias and lower variance. The useful value depends on sample size, noise, class balance, geometry, and the metric used to define nearness.

Geometry determines what similarity means

KNN can form curved and irregular boundaries without specifying an equation for the boundary. It works well on the two-moons example because local neighbors follow the curved groups. On overlapping classes, no setting can create information that the features do not contain. A smooth uncertain boundary may be more honest than a jagged one that follows every sample.

Feature scale matters. A feature measured in thousands can dominate one measured between zero and one even when it is not more important. Standardization, a meaningful distance metric, and feature selection are therefore part of the model design. In high dimensions, distances often become less discriminative, a difficulty known as the curse of dimensionality.

What this model leaves out

This applet computes distances to every stored point, which costs O(n) per query. K-d trees, ball trees, approximate-nearest-neighbor indexes, and vector databases can reduce search work in favorable settings. Exact tree search is often sublinear in low dimensions but can degrade toward a full scan in high dimensions or difficult distributions. Real systems also address missing values, imbalanced classes, calibration, and memory cost.

For teachers

Curriculum: Supervised classification, distance metrics, hyperparameters, decision boundaries, feature scaling, weighted voting, and the bias-variance tradeoff.

Pre-exploration prompts:

What numerical rule could make two examples count as similar?
Should one nearest example or a larger neighborhood be trusted near a noisy boundary?
What could go wrong if two features use very different units?

Post-exploration prompts:

At k = 1, add one mislabeled point. Which region changes and why?
Increase k on two moons. At what point is stable structure smoothed away?
Compare uniform and distance-weighted voting near a boundary.
Use noisy overlap. Which errors come from model choice, and which come from ambiguous data?

Misconceptions to test: KNN has no hyperparameters; larger k is always safer; nearest means whichever point looks closest on the screen; changing the distance rule changes only the displayed number, not which neighbors are selected; distance weighting selects a different neighbor set; tree indexes guarantee O(log n) queries; all KNN boundaries are ordinary Voronoi boundaries.

K 最近邻 KNN 通过寻找距离查询点最近的 k 个带标签训练点，并组合它们的投票来进行分类。它属于惰性学习：拟合阶段主要是保存样本，大部分计算发生在请求预测时。

k 控制什么

当 k = 1 时，单个最近样本的标签决定预测。平面被划分为普通 Voronoi 区域，因此一个错误标签或噪声点就可能产生一小块异常预测区域。增大 k 后，多个邻居共同投票，边界对单一样本的敏感性降低。

如果 k 接近数据集大小，局部结构会被平均掉，多数类别可能支配大部分空间。KNN 没有学习到的系数，但仍有重要超参数：k、距离度量、特征缩放，以及是否让更近邻居获得更大权重。

较小的 k 通常意味着低偏差和高方差，较大的 k 通常意味着更高偏差和更低方差。有效取值取决于样本量、噪声、类别平衡、几何结构和用于定义邻近的度量。

几何结构决定相似性的含义

KNN 无需先写出边界方程，就能形成弯曲和不规则的决策边界。它能处理双月数据，是因为局部邻居会沿弯曲群组分布。对于类别重叠的数据，任何 k 都无法创造特征中不存在的信息。平滑且承认不确定性的边界，可能比追随每个样本的锯齿边界更诚实。

特征尺度很重要。一个以千为单位的特征可能压倒一个取值在零到一之间的特征，即使前者并不更重要。因此，标准化、有意义的距离度量和特征选择都属于模型设计。在高维空间中，各点之间的距离常变得不易区分，这称为维度灾难。

这个模型省略了什么

本工具对每个存储点都计算距离，每次查询成本为 O(n)。K-d 树、球树、近似最近邻索引和向量数据库可以在合适条件下降低搜索工作量。精确树搜索在低维中常为次线性，但在高维或困难分布下可能退化为接近完整扫描。真实系统还要处理缺失值、类别不平衡、概率校准和内存成本。

教师指导

课程目标：监督分类、距离度量、超参数、决策边界、特征缩放、加权投票和偏差方差权衡。

探索前问题：

什么数值规则可以定义两个样本相似？
在有噪声的边界附近，应相信一个最近样本还是较大邻域？
两个特征使用差异很大的单位时可能出现什么问题？

探索后问题：

在 k = 1 时加入一个错误标签点。哪个区域发生变化，为什么？
在双月数据上增大 k。稳定结构从什么时候开始被平滑掉？
在边界附近比较均匀投票和距离加权投票。
使用噪声重叠数据。哪些错误来自模型选择，哪些来自数据本身的歧义？

需要检验的误解：KNN 没有超参数；更大的 k 总是更安全；树索引保证 O(log n) 查询；所有 KNN 边界都是普通 Voronoi 边界。

Scenario 1: Two separated groups with k equal to five

Scenario 2: Small and large k make different errors

Scenario 3: The distance rule changes the neighborhood

Scenario 4: Feature scale can distort distance

Scenario 5: Distance weighting changes a noisy vote

Keyboard path

Text state summary

Reduced motion and non-visual support

What k controls

Geometry determines what similarity means

What this model leaves out

For teachers

k 控制什么

几何结构决定相似性的含义

这个模型省略了什么

教师指导

Scenario 1: Two separated groups with k equal to five

Scenario 2: Small and large k make different errors

Scenario 3: The distance rule changes the neighborhood

Scenario 4: Feature scale can distort distance

Scenario 5: Distance weighting changes a noisy vote

Text and keyboard support

Keyboard path

Text state summary

Reduced motion and non-visual support

What k controls

Geometry determines what similarity means

What this model leaves out

For teachers

k 控制什么

几何结构决定相似性的含义

这个模型省略了什么

教师指导