k 近邻法（ k -nearest neighbor， k -NN）是一种基本分类与回归方法。本书只讨论分类问题中的 k 近邻法。 k 近邻法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。 k 近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其 k 个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此， k 近邻法不具有显式的学习过程。 k 近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。 k 值的选择、距离度量及分类决策规则是 k 近邻法的三个基本要素。 k 近邻法1968年由Cover和Hart提出。

本章首先叙述 k 近邻算法，然后讨论 k 近邻法的模型及三个基本要素，最后讲述 k 近邻法的一个实现方法—— kd 树，介绍构造 kd 树和搜索 kd 树的算法。 +0HOWi1ymx69y35LGO4CaXjQkGpNOduOgVbkgzY7yCP//nyOTGZuXf1OXqu7bkoo