首页理论教育K-近邻分类方法简介

K-近邻分类方法简介

2023-06-16 理论教育版权反馈

【摘要】：当最近邻法应用于特定的一组样本时，所得到的错误率与样本的偶然有关。K-近邻法是最近邻法的一个显然的推广。无论是最近邻法还是K-近邻法，它们都有方法简单的优点，而且其错误率在贝叶斯错误率和两倍贝叶斯错误率之间。正是近邻法的这种优良性质，使它成为模式分类的重要方法之一。快速搜索近邻法考虑将样本分级分成一些不相交的子集，并在子集的基础上进行搜索。

最初的近邻法是由Cover和Hart于1968年提出的，由于对该方法在理论上进行了深入分析，直至现在仍是模式识别非参数法中最重要的方法之一[95]。

假定有c个类别ω1，ω2，…，ωc，的模式识别问题。每个类有标明类别的样本Ni个。如果设定ωi类的判别函数为：

式中：的角标i表示ωi类；k表示ωi类Ni个样本中的第k个。

按照式（2.15），决策规则可以写为：

若，则决策X属于类ωi。

这一决策方法称为最近邻法。就是说对未知样本x，只要比较x与c已知类别的样本之间的距离，并决策X为与它最近的样本同类[95]。当最近邻法应用于特定的一组样本时，所得到的错误率与样本的偶然有关。

K-近邻法是最近邻法的一个显然的推广。取未知样本x的K个近邻，看这K个近邻中多数属于哪一类，就把x归为哪一类。

无论是最近邻法还是K-近邻法，它们都有方法简单的优点，而且其错误率在贝叶斯错误率和两倍贝叶斯错误率之间。正是近邻法的这种优良性质，使它成为模式分类的重要方法之一。但近邻法存在下列问题[95]：

（1）需将所有样本存入计算机中，每次决策都要计算待识别样本x与全部训练样本之间的距离并进行比较，使存储量和计算量都很大。

（2）虽然在所有情况下，对未知样本x都可以进行决策，但当错误代价很大时，会产生较大的风险。

（3）要求样本趋于无穷大，这在任何实际场合都是无法实现的。

快速搜索近邻法考虑将样本分级分成一些不相交的子集，并在子集的基础上进行搜索。该算法对最近邻法和K-近邻法都适用。