第5章-近邻法分析课件

第第5 5章章 近邻法近邻法第第5 5章章 近邻法近邻法5.1最近邻法最近邻法 5.2k近邻法近邻法5.3 剪辑近邻法剪辑近邻法5.4可做拒绝决策的近邻法可做拒绝决策的近邻法第5章 近邻法5.1最近邻法 第第5 5章章 近邻法近邻法前面我们介绍了前面我们介绍了前面我们介绍了前面我们介绍了BayesBayes方法和概率密度函数的估计。可方法和概率密度函数的估计。可方法和概率密度函数的估计。可方法和概率密度函数的估计。可以看出，以看出，以看出，以看出，BayesBayes方法的应用受到很大限制。事实上，非方法的应用受到很大限制。事实上，非方法的应用受到很大限制。事实上，非方法的应用受到很大限制。事实上，非参数模式识别方法更为实用。由于能解决许多实际的模参数模式识别方法更为实用。由于能解决许多实际的模参数模式识别方法更为实用。由于能解决许多实际的模参数模式识别方法更为实用。由于能解决许多实际的模式识别问题，虽然在许多情况下它们不是最优的，但却式识别问题，虽然在许多情况下它们不是最优的，但却式识别问题，虽然在许多情况下它们不是最优的，但却式识别问题，虽然在许多情况下它们不是最优的，但却是应用的最多的有效的方法。统计模式识别中常用的基是应用的最多的有效的方法。统计模式识别中常用的基是应用的最多的有效的方法。统计模式识别中常用的基是应用的最多的有效的方法。统计模式识别中常用的基本非参数方法除了前面介绍的线性判别函数外，本非参数方法除了前面介绍的线性判别函数外，本非参数方法除了前面介绍的线性判别函数外，本非参数方法除了前面介绍的线性判别函数外，还有本还有本还有本还有本章将要介绍的近邻法和集群。近邻法属于有监督学习，章将要介绍的近邻法和集群。近邻法属于有监督学习，章将要介绍的近邻法和集群。近邻法属于有监督学习，章将要介绍的近邻法和集群。近邻法属于有监督学习，集群属于无监督学习。集群属于无监督学习。集群属于无监督学习。集群属于无监督学习。近邻法是由近邻法是由近邻法是由近邻法是由CoverCover和和和和HartHart于于于于19681968年提出来的。年提出来的。年提出来的。年提出来的。它是在已知模式类别的训练样本的条件下，绕开概率的它是在已知模式类别的训练样本的条件下，绕开概率的它是在已知模式类别的训练样本的条件下，绕开概率的它是在已知模式类别的训练样本的条件下，绕开概率的估计，按最近距离原则对待识别模式直接进行分类。估计，按最近距离原则对待识别模式直接进行分类。估计，按最近距离原则对待识别模式直接进行分类。估计，按最近距离原则对待识别模式直接进行分类。返回本章首页返回本章首页前面我们介绍了Bayes方法和概率密度函数的估计。可以看出，第第5 5章章 近邻法近邻法5.1 最近邻法最近邻法返回本章首页返回本章首页最近邻决策规则最近邻决策规则最近邻决策规则最近邻决策规则给定给定给定给定c 个类别个类别个类别个类别 ，每类有标明类别的样本，每类有标明类别的样本，每类有标明类别的样本，每类有标明类别的样本 个，个，个，个，近邻法的判别函数为近邻法的判别函数为近邻法的判别函数为近邻法的判别函数为决策法则为决策法则为决策法则为决策法则为直观的说，就是对待识别的模式向量直观的说，就是对待识别的模式向量直观的说，就是对待识别的模式向量直观的说，就是对待识别的模式向量 ，只要比较，只要比较，只要比较，只要比较 与所与所与所与所有已知类别的样本之间的欧式距离，并决策有已知类别的样本之间的欧式距离，并决策有已知类别的样本之间的欧式距离，并决策有已知类别的样本之间的欧式距离，并决策 与离它最近与离它最近与离它最近与离它最近的样本同类。的样本同类。的样本同类。的样本同类。5.1 最近邻法返回本章首页最近邻决策规则第第5 5章章 近邻法近邻法返回本章首页返回本章首页返回本章首页第第5 5章章 近邻法近邻法返回本章首页返回本章首页下面我们先定性的比较一下最近邻分类法与最小错误率下面我们先定性的比较一下最近邻分类法与最小错误率下面我们先定性的比较一下最近邻分类法与最小错误率下面我们先定性的比较一下最近邻分类法与最小错误率的的的的BayesBayes分类方法的分类能力。分类方法的分类能力。分类方法的分类能力。分类方法的分类能力。我们把我们把我们把我们把 的最近邻的最近邻的最近邻的最近邻 的类别看成是一个随机变量的类别看成是一个随机变量的类别看成是一个随机变量的类别看成是一个随机变量 ，的概率为后验概率的概率为后验概率的概率为后验概率的概率为后验概率最近邻法则可以看成是一个随机化决策最近邻法则可以看成是一个随机化决策最近邻法则可以看成是一个随机化决策最近邻法则可以看成是一个随机化决策 按照概率按照概率按照概率按照概率 来决定来决定来决定来决定 的类别。的类别。的类别。的类别。定义：定义：定义：定义：返回本章首页下面我们先定性的比较一下最近邻分类法与最小错误率第第5 5章章 近邻法近邻法返回本章首页返回本章首页按最小错误率的按最小错误率的按最小错误率的按最小错误率的BayesBayes决策法则：以概率决策法则：以概率决策法则：以概率决策法则：以概率1 1决策决策决策决策 ；按最近邻决策法则：以概率按最近邻决策法则：以概率按最近邻决策法则：以概率按最近邻决策法则：以概率 决策决策决策决策 ；这里假设在三类问题中，这里假设在三类问题中，这里假设在三类问题中，这里假设在三类问题中，的后验概率分别为的后验概率分别为的后验概率分别为的后验概率分别为按最小错误率的按最小错误率的按最小错误率的按最小错误率的BayesBayes决策法则：以概率决策法则：以概率决策法则：以概率决策法则：以概率1 1决策决策决策决策 ；按最近邻决策法则：以概率按最近邻决策法则：以概率按最近邻决策法则：以概率按最近邻决策法则：以概率 决策决策决策决策 ；以；以；以；以概率概率概率概率 决策决策决策决策 。当当当当 时，最近邻法的决策结果与最小错误率的时，最近邻法的决策结果与最小错误率的时，最近邻法的决策结果与最小错误率的时，最近邻法的决策结果与最小错误率的BayesBayes决策的决策结果相同，它们的错误率都是比较小的，决策的决策结果相同，它们的错误率都是比较小的，决策的决策结果相同，它们的错误率都是比较小的，决策的决策结果相同，它们的错误率都是比较小的，两种方法同样的好，当两种方法同样的好，当两种方法同样的好，当两种方法同样的好，当 ，两者的错误概率，两者的错误概率，两者的错误概率，两者的错误概率接近于接近于接近于接近于 ，两种方法同样的坏。下面我们将进一步分，两种方法同样的坏。下面我们将进一步分，两种方法同样的坏。下面我们将进一步分，两种方法同样的坏。下面我们将进一步分析近邻法的错误率。析近邻法的错误率。析近邻法的错误率。析近邻法的错误率。返回本章首页按最小错误率的Bayes决策法则：以概率1决策 第第5 5章章 近邻法近邻法返回本章首页返回本章首页最近邻法的错误率分析最近邻法的错误率分析最近邻法的错误率分析最近邻法的错误率分析在前面我们曾给出平均错误率的在前面我们曾给出平均错误率的在前面我们曾给出平均错误率的在前面我们曾给出平均错误率的在最小错误率的在最小错误率的在最小错误率的在最小错误率的BayesBayes决策中，决策使条件错误率决策中，决策使条件错误率决策中，决策使条件错误率决策中，决策使条件错误率 尽可能小，从而平均错误率尽可能小，从而平均错误率尽可能小，从而平均错误率尽可能小，从而平均错误率 也一定最小。这里，设也一定最小。这里，设也一定最小。这里，设也一定最小。这里，设采用采用采用采用N N个样本的最近邻法的平均错误率个样本的最近邻法的平均错误率个样本的最近邻法的平均错误率个样本的最近邻法的平均错误率 ，并设，并设，并设，并设返回本章首页最近邻法的错误率分析第第5 5章章 近邻法近邻法返回本章首页返回本章首页则有以下的不等式成立：则有以下的不等式成立：则有以下的不等式成立：则有以下的不等式成立：证明：最近邻法属于随机化决策，待分类模式证明：最近邻法属于随机化决策，待分类模式证明：最近邻法属于随机化决策，待分类模式证明：最近邻法属于随机化决策，待分类模式 的近邻的近邻的近邻的近邻随样本集的变化而随机变化，设其最近邻为随样本集的变化而随机变化，设其最近邻为随样本集的变化而随机变化，设其最近邻为随样本集的变化而随机变化，设其最近邻为 ，错误的，错误的，错误的，错误的条件错误率为条件错误率为条件错误率为条件错误率为 。对于。对于。对于。对于 取平均取平均取平均取平均返回本章首页则有以下的不等式成立：第第5 5章章 近邻法近邻法返回本章首页返回本章首页返回本章首页第第5 5章章 近邻法近邻法返回本章首页返回本章首页下面我们看一下上面的两个表达式。下面我们看一下上面的两个表达式。下面我们看一下上面的两个表达式。下面我们看一下上面的两个表达式。设对于给定的设对于给定的设对于给定的设对于给定的 ，概率密度是连续的且不为零。那么，概率密度是连续的且不为零。那么，概率密度是连续的且不为零。那么，概率密度是连续的且不为零。那么，任何样本落入以任何样本落入以任何样本落入以任何样本落入以 为中心的一个超球为中心的一个超球为中心的一个超球为中心的一个超球 S S 中的概率为中的概率为中的概率为中的概率为N N个独立的样本落在个独立的样本落在个独立的样本落在个独立的样本落在 S S 外的概率为外的概率为外的概率为外的概率为即是，一个样本也不落在即是，一个样本也不落在即是，一个样本也不落在即是，一个样本也不落在 S S 内的概率为内的概率为内的概率为内的概率为0 0，也就是说总有，也就是说总有，也就是说总有，也就是说总有一个样本落在一个样本落在一个样本落在一个样本落在 S S 内的概率为内的概率为内的概率为内的概率为1 1。无论。无论。无论。无论S S多么小，这个结论多么小，这个结论多么小，这个结论多么小，这个结论也是成立的，所以也是成立的，所以也是成立的，所以也是成立的，所以返回本章首页下面我们看一下上面的两个表达式。第第5 5章章 近邻法近邻法返回本章首页返回本章首页上式即是最近法错误率的计算公式，先看下界的证明，这里指出下上式即是最近法错误率的计算公式，先看下界的证明，这里指出下面的面的 两种特殊情况。两种特殊情况。（1）（2）返回本章首页上式即是最近法错误率的计算公式，先看下界的证明，第第5 5章章 近邻法近邻法返回本章首页返回本章首页现在在来求最近邻法分类错误率的精确上现在在来求最近邻法分类错误率的精确上界。界。返回本章首页现在在来求最近邻法分类错误率的精确上界。第第5 5章章 近邻法近邻法返回本章首页返回本章首页返回本章首页第第5 5章章 近邻法近邻法返回本章首页返回本章首页例题例题例题例题1 1 设在一个二维空间，设在一个二维空间，设在一个二维空间，设在一个二维空间，A A类有三个训练样本，图中用类有三个训练样本，图中用类有三个训练样本，图中用类有三个训练样本，图中用红点表示，红点表示，红点表示，红点表示，B B类四个样本，图中用蓝点表示。试问：类四个样本，图中用蓝点表示。试问：类四个样本，图中用蓝点表示。试问：类四个样本，图中用蓝点表示。试问：（1 1）按近邻法分类，这两类最多有多少个分界面按近邻法分类，这两类最多有多少个分界面按近邻法分类，这两类最多有多少个分界面按近邻法分类，这两类最多有多少个分界面（2 2）画出实际用到的分界面画出实际用到的分界面画出实际用到的分界面画出实际用到的分界面（3 3）A A1 1与与与与B B4 4之间的分界面没有用到之间的分界面没有用到之间的分界面没有用到之间的分界面没有用到 返回本章首页例题1 设在一个二维空间，A类有三个训练样本，第第5 5章章 近邻法近邻法返回本章首页返回本章首页答：按近邻法，对任意两个由不同类别的训练样本构成的样本对，答：按近邻法，对任意两个由不同类别的训练样本构成的样本对，答：按近邻法，对任意两个由不同类别的训练样本构成的样本对，答：按近邻法，对任意两个由不同类别的训练样本构成的样本对，如果它们有可能成为测试样本的近邻，则它们构成一组最小距离分如果它们有可能成为测试样本的近邻，则它们构成一组最小距离分如果它们有可能成为测试样本的近邻，则它们构成一组最小距离分如果它们有可能成为测试样本的近邻，则它们构成一组最小距离分类器，它们之间的中垂面就是分界面，因此由三个类器，它们之间的中垂面就是分界面，因此由三个类器，它们之间的中垂面就是分界面，因此由三个类器，它们之间的中垂面就是分界面，因此由三个A A类与四个类与四个类与四个类与四个B B类训类训类训类训练样本可能构成的分界面最大数量为练样本可能构成的分界面最大数量为练样本可能构成的分界面最大数量为练样本可能构成的分界面最大数量为34341212。实际分界面如下图所示，由实际分界面如下图所示，由实际分界面如下图所示，由实际分界面如下图所示，由9 9条线段构成：条线段构成：条线段构成：条线段构成：返回本章首页答：按近邻法，对任意两个由不同类别的训练样本构成第第5 5章章 近邻法近邻法返回本章首页返回本章首页例题例题例题例题2 2当当当当 时，时，时，时，（1 1）证明一维问题的）证明一维问题的）证明一维问题的）证明一维问题的BayesBayes错误率错误率错误率错误率（2 2）证明此时最近邻法渐近平均错误率）证明此时最近邻法渐近平均错误率）证明此时最近邻法渐近平均错误率）证明此时最近邻法渐近平均错误率返回本章首页例题2第第5 5章章 近邻法近邻法返回本章首页返回本章首页解：解：解：解：返回本章首页解：第第5 5章章 近邻法近邻法返回本章首页返回本章首页课后习题课后习题P160：6.3 6.4 6.5P81：3.1 3.4 3.15 返回本章首页课后习题第第5 5章章 近邻法近邻法5.2 k近邻法近邻法返回本章首页返回本章首页k k k k近邻法是在近邻法的基础上加以改进而来的，这个法近邻法是在近邻法的基础上加以改进而来的，这个法近邻法是在近邻法的基础上加以改进而来的，这个法近邻法是在近邻法的基础上加以改进而来的，这个法则就是在则就是在则就是在则就是在 的的的的 k k k k 个近邻中，按出现最多的样本类别来作个近邻中，按出现最多的样本类别来作个近邻中，按出现最多的样本类别来作个近邻中，按出现最多的样本类别来作为为为为 的类别。前面我们详细讨论了近邻法的错误率的表的类别。前面我们详细讨论了近邻法的错误率的表的类别。前面我们详细讨论了近邻法的错误率的表的类别。前面我们详细讨论了近邻法的错误率的表达式及其上下界。同样，对于达式及其上下界。同样，对于达式及其上下界。同样，对于达式及其上下界。同样，对于k k k k近邻法则，我们也讨论近邻法则，我们也讨论近邻法则，我们也讨论近邻法则，我们也讨论一下错误率的问题，这里以一下错误率的问题，这里以一下错误率的问题，这里以一下错误率的问题，这里以 和和和和 二类问题为例。为二类问题为例。为二类问题为例。为二类问题为例。为避免出现避免出现避免出现避免出现 而不能判决的情况，我们取而不能判决的情况，我们取而不能判决的情况，我们取而不能判决的情况，我们取 为为为为奇数。对待识别模式奇数。对待识别模式奇数。对待识别模式奇数。对待识别模式 误分类有以下两种情况：误分类有以下两种情况：误分类有以下两种情况：误分类有以下两种情况：5.2 k近邻法返回本章首页k近邻法是在近邻法的基础上第第5 5章章 近邻法近邻法返回本章首页返回本章首页前面我们已经说过，当前面我们已经说过，当前面我们已经说过，当前面我们已经说过，当 ，的的的的 k k k k 个已知类别的个已知类别的个已知类别的个已知类别的最近邻样本最近邻样本最近邻样本最近邻样本 以概率以概率以概率以概率 1 1 1 1 收敛于收敛于收敛于收敛于 ，所以这，所以这，所以这，所以这k k k k 个样本可以不标出下标，统记为个样本可以不标出下标，统记为个样本可以不标出下标，统记为个样本可以不标出下标，统记为 。对于给定的。对于给定的。对于给定的。对于给定的 的条的条的条的条件错误率为件错误率为件错误率为件错误率为返回本章首页前面我们已经说过，当 ，的 k 第第5 5章章 近邻法近邻法返回本章首页返回本章首页返回本章首页第第5 5章章 近邻法近邻法返回本章首页返回本章首页渐近平均错误率渐近平均错误率渐近平均错误率渐近平均错误率这里定义这里定义这里定义这里定义BayesBayesBayesBayes条件错误率条件错误率条件错误率条件错误率 的函数的函数的函数的函数 为为为为大于大于大于大于 的最小凹函数，即对所有的的最小凹函数，即对所有的的最小凹函数，即对所有的的最小凹函数，即对所有的 返回本章首页渐近平均错误率第第5 5章章 近邻法近邻法返回本章首页返回本章首页近邻法则讨论近邻法则讨论近邻法则讨论近邻法则讨论返回本章首页近邻法则讨论第第5 5章章 近邻法近邻法返回本章首页返回本章首页从上面可以看出近邻法有方法简单的优点，但也存在这从上面可以看出近邻法有方法简单的优点，但也存在这从上面可以看出近邻法有方法简单的优点，但也存在这从上面可以看出近邻法有方法简单的优点，但也存在这一些缺点：一些缺点：一些缺点：一些缺点：（1 1 1 1）存储量和计算量都很大；）存储量和计算量都很大；）存储量和计算量都很大；）存储量和计算量都很大；（2 2 2 2）没有考虑决策的风险，如果决策的错误代价很大时，）没有考虑决策的风险，如果决策的错误代价很大时，）没有考虑决策的风险，如果决策的错误代价很大时，）没有考虑决策的风险，如果决策的错误代价很大时，会产生很大的风险；会产生很大的风险；会产生很大的风险；会产生很大的风险；（3 3 3 3）以上的分析）以上的分析）以上的分析）以上的分析渐近平均错误率，都是建立在样本渐近平均错误率，都是建立在样本渐近平均错误率，都是建立在样本渐近平均错误率，都是建立在样本数趋向无穷大的条件下得来的，在实际应用时大多是无数趋向无穷大的条件下得来的，在实际应用时大多是无数趋向无穷大的条件下得来的，在实际应用时大多是无数趋向无穷大的条件下得来的，在实际应用时大多是无法实现的。法实现的。法实现的。法实现的。返回本章首页从上面可以看出近邻法有方法简单的优点，但也存在这第第5 5章章 近邻法近邻法5.3 剪辑近邻法剪辑近邻法返回本章首页返回本章首页这种方法的思想是这种方法的思想是这种方法的思想是这种方法的思想是,清理两类间的边界，去掉类别混杂的清理两类间的边界，去掉类别混杂的清理两类间的边界，去掉类别混杂的清理两类间的边界，去掉类别混杂的样本，使两类边界更清晰。这种方法的性能在理论上明样本，使两类边界更清晰。这种方法的性能在理论上明样本，使两类边界更清晰。这种方法的性能在理论上明样本，使两类边界更清晰。这种方法的性能在理论上明显好于一般的最近邻法。显好于一般的最近邻法。显好于一般的最近邻法。显好于一般的最近邻法。1 1 1 1 剪辑最近邻法剪辑最近邻法剪辑最近邻法剪辑最近邻法 对于两类问题，设将已知类别的样本集对于两类问题，设将已知类别的样本集对于两类问题，设将已知类别的样本集对于两类问题，设将已知类别的样本集 分成参照集分成参照集分成参照集分成参照集 和考试集和考试集和考试集和考试集 两部分，这两部分没有公共元素，两两部分，这两部分没有公共元素，两两部分，这两部分没有公共元素，两两部分，这两部分没有公共元素，两部分的样本数分别为部分的样本数分别为部分的样本数分别为部分的样本数分别为 和和和和 ，且，且，且，且 。第一步：利用参照集中的样本第一步：利用参照集中的样本第一步：利用参照集中的样本第一步：利用参照集中的样本 采用最近邻采用最近邻采用最近邻采用最近邻法对考试集中的样本法对考试集中的样本法对考试集中的样本法对考试集中的样本 进行分类，剪辑掉进行分类，剪辑掉进行分类，剪辑掉进行分类，剪辑掉 中被错分类的样本，具体的说就是：中被错分类的样本，具体的说就是：中被错分类的样本，具体的说就是：中被错分类的样本，具体的说就是：是是是是 的最近邻元，剪辑掉的最近邻元，剪辑掉的最近邻元，剪辑掉的最近邻元，剪辑掉 中不与中不与中不与中不与 同类同类同类同类 余下的部分构成剪辑样本集余下的部分构成剪辑样本集余下的部分构成剪辑样本集余下的部分构成剪辑样本集 。5.3 剪辑近邻法返回本章首页这种方法的思想是,清理两类间第第5 5章章 近邻法近邻法返回本章首页返回本章首页第二步：利用剪辑样本集第二步：利用剪辑样本集第二步：利用剪辑样本集第二步：利用剪辑样本集 和最近邻法对待分类模式和最近邻法对待分类模式和最近邻法对待分类模式和最近邻法对待分类模式 作分类决策。作分类决策。作分类决策。作分类决策。定理定理定理定理：当样本数：当样本数：当样本数：当样本数 时，时，时，时，。如果。如果。如果。如果 是是是是 和和和和 的连续点，设的连续点，设的连续点，设的连续点，设 在在在在 中的最近邻为中的最近邻为中的最近邻为中的最近邻为 ，则，则，则，则 在在在在 中的最近邻中的最近邻中的最近邻中的最近邻 有有有有那么我们可以得到那么我们可以得到那么我们可以得到那么我们可以得到 的近邻的近邻的近邻的近邻 属于属于属于属于 的渐近概率为的渐近概率为的渐近概率为的渐近概率为返回本章首页第二步：利用剪辑样本集 和最近邻法对待分第第5 5章章 近邻法近邻法返回本章首页返回本章首页误判的情况误判的情况误判的情况误判的情况：属于属于属于属于 类而其近邻元属于类而其近邻元属于类而其近邻元属于类而其近邻元属于 ，或，或，或，或 属于属于属于属于 类但其近邻元属于类但其近邻元属于类但其近邻元属于类但其近邻元属于 类，因此没有剪辑的最近邻法的类，因此没有剪辑的最近邻法的类，因此没有剪辑的最近邻法的类，因此没有剪辑的最近邻法的渐近条件错误率为渐近条件错误率为渐近条件错误率为渐近条件错误率为剪辑了的最近邻法的渐近条件错误了率为剪辑了的最近邻法的渐近条件错误了率为剪辑了的最近邻法的渐近条件错误了率为剪辑了的最近邻法的渐近条件错误了率为返回本章首页误判的情况：属于 类而其近邻元属于 ，或第第5 5章章 近邻法近邻法返回本章首页返回本章首页返回本章首页第第5 5章章 近邻法近邻法返回本章首页返回本章首页返回本章首页第第5 5章章 近邻法近邻法返回本章首页返回本章首页2 2 2 2 重复剪辑近邻法重复剪辑近邻法重复剪辑近邻法重复剪辑近邻法 只要样本足够多，就可以重复地执行剪辑程序，以提高只要样本足够多，就可以重复地执行剪辑程序，以提高只要样本足够多，就可以重复地执行剪辑程序，以提高只要样本足够多，就可以重复地执行剪辑程序，以提高分类性能。这里从理论上对二类问题重复剪辑最近邻法分类性能。这里从理论上对二类问题重复剪辑最近邻法分类性能。这里从理论上对二类问题重复剪辑最近邻法分类性能。这里从理论上对二类问题重复剪辑最近邻法的错误率进行分析。经过第一次剪辑后，的错误率进行分析。经过第一次剪辑后，的错误率进行分析。经过第一次剪辑后，的错误率进行分析。经过第一次剪辑后，的最近邻样本的最近邻样本的最近邻样本的最近邻样本 属于属于属于属于 的概率为的概率为的概率为的概率为返回本章首页2 重复剪辑近邻法 第第5 5章章 近邻法近邻法返回本章首页返回本章首页第二次剪辑后，第二次剪辑后，第二次剪辑后，第二次剪辑后，的最近邻样本属于的最近邻样本属于的最近邻样本属于的最近邻样本属于 的概率为的概率为的概率为的概率为返回本章首页第二次剪辑后，的最近邻样本属于 的概第第5 5章章 近邻法近邻法返回本章首页返回本章首页第第第第MM次剪辑后，次剪辑后，次剪辑后，次剪辑后，的最近邻样本属于的最近邻样本属于的最近邻样本属于的最近邻样本属于 的概率为的概率为的概率为的概率为返回本章首页第M次剪辑后，的最近邻样本属于 的概第第5 5章章 近邻法近邻法返回本章首页返回本章首页返回本章首页第第5 5章章 近邻法近邻法5.4 可做拒绝决策的近邻法可做拒绝决策的近邻法返回本章首页返回本章首页在运用在运用在运用在运用k k k k近邻法时，为克服近邻法时，为克服近邻法时，为克服近邻法时，为克服k k k k个近邻元属于不同类别的个近邻元属于不同类别的个近邻元属于不同类别的个近邻元属于不同类别的样本数的偶然性，采用的方法之一是增大样本数的偶然性，采用的方法之一是增大样本数的偶然性，采用的方法之一是增大样本数的偶然性，采用的方法之一是增大k k k k ，然而这仍，然而这仍，然而这仍，然而这仍然不能完全消除然不能完全消除然不能完全消除然不能完全消除k k k k个近邻元类别的偶然性。我们说若个近邻元类别的偶然性。我们说若个近邻元类别的偶然性。我们说若个近邻元类别的偶然性。我们说若k k k k个个个个近邻元中某一类的样本数占很大的优势，则误判的可能近邻元中某一类的样本数占很大的优势，则误判的可能近邻元中某一类的样本数占很大的优势，则误判的可能近邻元中某一类的样本数占很大的优势，则误判的可能性就较小；如果是微弱优势，则作出判别决策，误判的性就较小；如果是微弱优势，则作出判别决策，误判的性就较小；如果是微弱优势，则作出判别决策，误判的性就较小；如果是微弱优势，则作出判别决策，误判的可能性就很大。进一步，在某些实际问题中误判的风险可能性就很大。进一步，在某些实际问题中误判的风险可能性就很大。进一步，在某些实际问题中误判的风险可能性就很大。进一步，在某些实际问题中误判的风险很大的话，则会付出很大的代价，因此在这种情况下引很大的话，则会付出很大的代价，因此在这种情况下引很大的话，则会付出很大的代价，因此在这种情况下引很大的话，则会付出很大的代价，因此在这种情况下引入拒绝决策就很有必要了，一般记为入拒绝决策就很有必要了，一般记为入拒绝决策就很有必要了，一般记为入拒绝决策就很有必要了，一般记为 类。类。类。类。下面我们结合前面讲述的下面我们结合前面讲述的下面我们结合前面讲述的下面我们结合前面讲述的k k k k近邻法和剪辑近邻法进行分近邻法和剪辑近邻法进行分近邻法和剪辑近邻法进行分近邻法和剪辑近邻法进行分析。析。析。析。5.4 可做拒绝决策的近邻法返回本章首页在运用k近邻法时第第5 5章章 近邻法近邻法返回本章首页返回本章首页1 1 1 1 具有拒绝决策的具有拒绝决策的具有拒绝决策的具有拒绝决策的k近邻法近邻法近邻法近邻法 对于两类问题，引入了拒绝决策对于两类问题，引入了拒绝决策对于两类问题，引入了拒绝决策对于两类问题，引入了拒绝决策k k近邻法的思想是，根近邻法的思想是，根近邻法的思想是，根近邻法的思想是，根据可信性要求选定一个据可信性要求选定一个据可信性要求选定一个据可信性要求选定一个 值，应使值，应使值，应使值，应使 ，如果待识，如果待识，如果待识，如果待识别模式别模式别模式别模式 的的的的k k个近邻中有大于或等于个近邻中有大于或等于个近邻中有大于或等于个近邻中有大于或等于 个样本属于某一个样本属于某一个样本属于某一个样本属于某一类类类类 ,则判则判则判则判 ，否则拒绝作出类别决策。，否则拒绝作出类别决策。，否则拒绝作出类别决策。，否则拒绝作出类别决策。的的的的k k k k个近邻元至少有个近邻元至少有个近邻元至少有个近邻元至少有 个来自个来自个来自个来自 类的渐近概率为类的渐近概率为类的渐近概率为类的渐近概率为 返回本章首页1 具有拒绝决策的k近邻法 第第5 5章章 近邻法近邻法返回本章首页返回本章首页当当当当 的的的的 个近邻中有少于个近邻中有少于个近邻中有少于个近邻中有少于 个属于同一类时，则考虑拒个属于同一类时，则考虑拒个属于同一类时，则考虑拒个属于同一类时，则考虑拒绝，这时的概率为绝，这时的概率为绝，这时的概率为绝，这时的概率为返回本章首页当 的 个近邻中有少于 个属于同一类时，第第5 5章章 近邻法近邻法返回本章首页返回本章首页决策的错误率决策的错误率决策的错误率决策的错误率决策的拒绝率决策的拒绝率决策的拒绝率决策的拒绝率2 2 具有拒绝决策的剪辑近邻法具有拒绝决策的剪辑近邻法具有拒绝决策的剪辑近邻法具有拒绝决策的剪辑近邻法 拒绝决策的近邻法推广到剪辑近邻法。拒绝决策的近邻法推广到剪辑近邻法。拒绝决策的近邻法推广到剪辑近邻法。拒绝决策的近邻法推广到剪辑近邻法。首先选定首先选定首先选定首先选定 和和和和 ，然后我们按以下的步骤对样，然后我们按以下的步骤对样，然后我们按以下的步骤对样，然后我们按以下的步骤对样本集进行剪辑，然后用剪辑样本集对待识别模式进行分本集进行剪辑，然后用剪辑样本集对待识别模式进行分本集进行剪辑，然后用剪辑样本集对待识别模式进行分本集进行剪辑，然后用剪辑样本集对待识别模式进行分类。类。类。类。返回本章首页决策的错误率第第5 5章章 近邻法近邻法返回本章首页返回本章首页步骤如下：步骤如下：步骤如下：步骤如下：（1 1）对于训练集）对于训练集）对于训练集）对于训练集 中的每个样本中的每个样本中的每个样本中的每个样本 ，从，从，从，从 中找出它中找出它中找出它中找出它的的的的 个近邻元；个近邻元；个近邻元；个近邻元；（2 2）如果）如果）如果）如果 的的的的 个近邻至少有个近邻至少有个近邻至少有个近邻至少有 个属于个属于个属于个属于 类，类，类，类，则记类别标签则记类别标签则记类别标签则记类别标签 ，否则，否则，否则，否则 。（3 3）在）在）在）在 中只保留中只保留中只保留中只保留 和和和和 的样本，即去掉被错分类的样本。的样本，即去掉被错分类的样本。的样本，即去掉被错分类的样本。的样本，即去掉被错分类的样本。（4 4）将）将）将）将 的那些样本的那些样本的那些样本的那些样本 归为拒绝类归为拒绝类归为拒绝类归为拒绝类 ，从而组，从而组，从而组，从而组成含有三类剪辑样本集成含有三类剪辑样本集成含有三类剪辑样本集成含有三类剪辑样本集 。（5 5）利用）利用）利用）利用 和最近邻规则对待识别模式和最近邻规则对待识别模式和最近邻规则对待识别模式和最近邻规则对待识别模式 进行分类决进行分类决进行分类决进行分类决策。策。策。策。返回本章首页步骤如下：第第5 5章章 近邻法近邻法THANK YOU VERY MUCH！本章到此结束本章到此结束下一章下一章“特征选择和特征提取特征选择和特征提取”返回本章首页返回本章首页结结 束放映束放映THANK YOU VERY MUCH！本章到此结束返回本