第5章 近邻分类器

# 第 5 章 近邻分类器

# 最近邻规则

• 按照未知样本离哪个已知样本更近或更相似，来确定应该把它划分到哪一类。
• 维诺图：最近邻分类器的分类决策区域是由任意两个相邻不同类样本点连接线的垂直平分线所分割成为的网格状图形。

# 最近邻法

• 对于 c 类问题，每类有$N_{i}$ 个样本，i=1，2，……，c，对于第 i 类$\omega_{i}$ 的判别函数，待分类样本$x$ 到训练集样本$x_{i}$ 的最小距离为：

$$d_{i}(x)=\underset{k}{min}||x-x^{k}_{i}||,k=1,2,…,N_{i}$$

其中$x^{k}_{i}$ 表示$\omega_{i}$ 类$N_{i}$ 个样本中的第$k$ 个。

• 决策规则为：

$$if\space d_{j}(x)=\underset{i=1,2,…,c}{min}d_{i}(x), then\space x\in \omega_{j}$$

• 最近邻法的渐进平均错误率介于一倍贝叶斯错误率到两倍贝叶斯错误率之间。

# k - 近邻法（KNN 算法）

• 定义：从训练集中找出待识别样本的 k 个最近邻，然后依据这 k 个最近邻分别所属的类别来决定应当把待识别样本划分到哪个类别中。
• 决策规则：随大流
  k 个最近邻，其中各类别所占个数表示成$k_i$，i=1,2,…,c，且$d_{i}(x)=k_{i}$，则有：

$$if\space d_{j}(x)=\underset{i=1,2,…,c}{max}d_{i}(x), then\space x\in \omega_{j}$$

# 近邻快速算法（快速 KNN 算法）

• 定义：通过对原始样本集的整理，将其组织为分层的树形结构，计算待分类样本到样本集中样本的距离时，先利用三角关系考虑某一组样本是否有计算的必要，从而大幅度地减少 k - 近邻分类器的计算量。

# 剪辑近邻法

# 压缩近邻法

• 定义：相比于快速 KNN 算法改进搜索路径来提高算法计算速度，压缩近邻法则是通过对原始样本集中样本的删减，寻找到一个分类效果与原始样本集相当，但样本数量更少的新样本集，从而同步提升最近邻算法在速度和存储量两方面的性能。