> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/lihang-tongjixuexifangfa/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/lihang-tongjixuexifangfa/knn.md).

# 第3章 k近邻算法

## K近邻算法

KNN，k-nearest neighbor

给定一个训练数据集，对新的输入实例，在训练数据集找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

分类算法，也可以作回归算法

## 模型

模型由三个基本要素 --- 距离度量、k值的选择、分类决策规则\
当距离度量、k值的选择、分类决策规则确定后，其分类结果唯一确定。

## 算法

kd树。\
kd树是一种便于对k维空间中的数据进行快速检索的数据结构。\
kd树是二叉树，表示对k维空间的一个划分。\
kd树每个结点对应于k维空间划分中的一个超矩形区域。\
复用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。