第5章近邻法则和集群

第5章近邻法则和集群

近邻法则近邻法则的错误率

K-近邻法则快速近邻算法集群的准则函数迭代最优化方法等级集群方法一.近邻法则设有一个已知类别的样本集：样本集中的样本分别属于个类别:设每类的样本数分别为:如果这n个样本中与待分类样本X距离最近的一个样本为X’，则把X分到X’所属的类别。近邻法则的判别函数为:决策规则:若则把分到类。

可以看出近邻法则计算非常简单，但是这个方法如何？（1）分类能力如何？（2）分类错误率如何？能否给出定性与定量的解释？二.近邻法则的分类能力中有个类别的样本,每个类别有个样本,每次从中取出一个样本,比较与的相近程度,由于每次取出的样本是随机的,因而样本的类别状态也是随机的。把的最近邻的类别状态看成一个随机变量（可能是中的任意一个）。于是，的概率就是后验概率，当样本的数目越来越多时，可以认为的最近邻离它越来越近，从而：这样，就可以把近邻法则看成是由概率来决定的类别。（1）在近邻法则中，的最近邻的类别状态为的概率为，所以分到类的概率为，而不分到的概率为（2）我们已经知道，在Bayes决策中,有取作为的类别。比较Bayes决策和近邻法则，可以看出：按Bayes决策法则：以概率1决策按最近邻法则：以概率决策举例说明:设在三个类别问题中，的后验概率分别为：按Bayes决策：因为所以按近邻法则决策：有0.4的概率有0.3的概率有0.3的概率（1）当接近1时，近邻法则的错误概率,与Bayes决策的结果几乎相同，说明这两种方法同样“好”。（2）当，两者的错误概率都接近，说明两种方法同样“坏”。

由于Bayes分类器是最优分类器，与Bayes分类器的比较可以看出，近邻法则有较好的分类性质。5.1.2近邻法则的错误率回顾:最小错误概率的Bayes决策中的有关内容模式特征是一个随机变量，用后验概率作出分类决策时，会有错误分类的可能性,对于每个不同的值,其也不同,从而分类错误概率也不同,所以分类错误概率可以看作是的函数.

如果已知连续随机变量的概率密度函数为的数学期望为:

对于模式向量,由于是一个随机变量,所以有:

对于每个观察向量，如果使尽可能小的话，则上式积分也必定尽可能小。从而错误概率就达到极小。若记是的极小值，是的极小值，则：

在什么情况下可以取得最小值？

在，A为小于1的正常数下，最小。

也就是说，一个最大，其余都相等时，有最小值。这样就有：对于近邻法则,设是采用个样本时的错误概率，并设则有近邻法则错误率的上下限：先求

设用某一组N个已知类别的样本对分类，如果的最近邻样本为，则把分到所属的类别。如果用不同组的N个样本对分类，则的最近邻可能是完全不同的。由于近邻决策完全取决于的最近邻样本，所以错误概率与，有关，即。每次取一组样本做最近邻决策，每次都有一定的错误概率，如果对取平均，则有：对于数学表达式是难以获得的。如何考虑解决求的问题呢？

如果能够趋近于一个中心在的函数，则该式的计算就可以大大简化了。设想：因为是的最近邻，可以期望密度函数在的附近有一个陡峭的峰，而在其它地方则很小。这是什么含义呢？在已知的条件下，的最近邻在的附近的概率密度最大。可以这样设想的依据：相同类别的样本特征相同或相近，分布最集中。举例说明：

为了证明当n趋于无穷大时，可能趋于一个中心在的函数，我们设对于给定的，概率密度是连续的且不为零。这样，任何样本落在以为中心的一个超球S中的概率记为：落在S以外的概率为,

当样本独立抽取时，全部n个独立抽取的样本落在S以外的概率就为当时这就是说，总有一个以上的样本落在S内的概率为1.由于S可以任意小，所以当S很小时，只要样本数n足够大，总有的近邻在S内，所以，以概率1收敛于。这就证明了当n趋于无穷大时，趋于函数。即下面讨论错误概率将n个独立抽取的已知类别的样本表示成二元对的形式：其中是C个类别状态中的任意一个。现在假定抽取一对，并假定是的最近邻，类别为，即是的最近邻，由于和是独立抽取的，的类别状态和的类别状态无关，因此就有：当采用近邻法则时，如果就会产生分类错误，因为当时有（以概率1收敛于）所以错误概率为

对于当可以写成：这样，近邻法则的错误率为下面我们开始证明最近邻法则错误率的上下界。要证明的下界为，只要指出在某些特定情况下存在就可以了。（为什么，请思考）1.在时（，）所以在这种情况下成立。2.在时（各后验概率都相等）

所以在这种情况下也成立。

思考：通过P的下界的证明，可以采用在特殊情况有P=P*就可以。那么对于P的上界的证明可不可以也这样做？下面证明P的上界。

要证明P的上界，关键的问题是如何将最近邻法则的错误率P和最小错误概率的贝叶斯错误率P*联系起来。由前面的推导已经知道了最近邻法则的错误率为：由最小错误概率的Bayes决策()可知最小错误概率为：这两个公式对我们的启发是：对已知的而言，的最小值对应着P的最大值，如果能求得P的最大值，就把P*和P联系起来了。由数学知识可知：

在，A为小于1的正常数下，最小。

这样就有：而所以，从而可得：

极小时得出即整理得：

由于根据方差的定义：有：（5-15）把右式展开，由于方差非负，所以从而，如果，对下式（5-15）两边取积分，得等号只在方差为0时成立可以看出，左式=P，所以5.1.3K-近邻法则

K-近邻法是最近邻法的一个改进。有个已知类别的样本，

的个近邻中，

用判别函数表示：决策规则为：若则取待识别样本的个近邻，看这个近邻中多数样本属于哪一类，就把归为那一类。最近邻法则和K-近邻法则的优缺点：优点：算法简单缺点：（1）每次需要计算x与全部样本间的距离并进行比较。计算机存储容量和计算量都很大。

（2）没有考虑决策的风险，如果错误代价很大时，会产生很大风险。（3）错误率分析是情况下得出的，而对有限样本集理论依据不充分。可以看出，（2）和（3）是近邻法则的固有问题，那么通过什么方法可以改善缺点(1)呢?

5.1.5快速近邻算法

1.分量邻域法思路：近邻法则与的近邻样本有关，那就关注近邻样本。方法：是待分类的模式，以

为中心，构造边长为的邻域，逐渐扩大该邻域，直至有一个样本落入这个邻域时为止。算法：输入:

维训练样本集,

,待分类样本

；输出:

的最近邻

；步骤:(1)以

为中心,构造一个

为边长的邻域。(2)在

中找出落入的训练集

的样本，如果

为空，则增加

一个级差

,转步骤(1)。(3)对全部

计算距离

，最小者即为的最近邻。该算法存在一个什么问题？算法：输入:

维训练样本集,

,待分类样本

；输出:

的最近邻

；步骤:(1)以

为中心,构造一个

为边长的邻域。(2)在

中找出落入的训练集

的样本，如

为空，则增加

一个级差

,转(1)。(3)扩大邻域

到

，找出全部落入这个邻域中训练集

的样本，即

的一个子集

。(4)对全部

计算距离

，最小者即为的最近邻。算法优点：简单，快速。缺点：特征维数高时，效率低。2.列表法(1)预处理阶段在模式空间指定任意三个点。分别计算这三个点到训练样本集中全部成员的距离。对

以从近到远的顺序列出所有的成员。构成三个表

。………………

………计算待分类模式到的距离,。在表中分别按将嵌入相应的位置上。…………

……(2)搜索阶段在表中取的近邻形成三个子集若非空,则交集中的元素就可能包含的最近邻。若为空,

则逐步扩大的邻域的范围。直至非空,找到的最近邻。5.2集群（聚类clustering)

采用有类别标识的训练样本集来实现对待识别模式的分类，称为有监督学习或有教师学习。如线性判别函数，Bayes决策，近邻法则等。把没有训练样本集时的分类方法，即无监督的或无教师的分类方法叫做集群。集群问题中有两种情况：预先指定分群的数目预先不知道分群的数目

面对一组待分类的模式，根据什么分类呢？

实际上，集群的目的就是要在一组数据中找出自然形成的数据群，而一群中的样本彼此之间应该比其它群的样本之间更相像一些。也就是说，根据各个待分类的模式特征的相似程度进行分类，把相似的归为一类。

因此，集群应该解决两个问题：（1）如何评定样本之间的相似程度？（2）如何根据相似程度将给定样本集划分为不同的群？样本间相似性的度量一个模式向量是特征空间的一个点，如果两个样本在特征空间相距很近，它们的各个特征也应该相差不大，因此，两个样本在特征空间的距离可以作为样本间相似性的一种度量。常用的方法是先定义一个适当的距离来度量相似性。如果这个距离是相似性的一个好的度量，那么我们就可以期望在同一群内样本之间的距离将明显小于不同群的样本之间的距离。

欧氏距离：用距离来度量相似性，存在阈值的选择问题。

如果太大，则可能把全部样本归到同一个群中去。如果太小，则每个样本为一个群。

显然，上述两种情况都失去了分群的意义。d1d2

为了得到合适的自然数据群，阈值应当选得大于可作为代表的群内距离和小于可作为代表的群间距离。

（群内距离），（群间距离）

两向量间的距离度量有许多种，除了欧氏距离外还有几个常用距离：1.Mahalanobis距离式中为样本各特征的协方差矩阵。2.Minkovsky距离式中为样本维数。3.Camberra距离4.Chebychev距离5.2.2集群的准则函数

前面介绍了如何评定样本间的相似性，现在讨论如何根据样本间的相似性把一组样本划分为不同的群的方法。假设有样本集，要求把它分成c个不相交的子集，每个子集表示一群样本。对这个划分的要求是：在同一群内的样本比不同群的样本更相像一些。由于距离阈值的选取不同，分群的结果也不同。群的划分具有人为规定性。

所以需要定义一个准则函数，利用它来度量数据划分所形成的群的性质，这样就把分群的问题变成使这个准则函数取极值的问题。

误差平方准则设是中样本的数目，是这些样本的均值向量，

总的误差平方和为：

度量了用个群的中心来代表个样本子集时所产生的总的误差的平方。个群的划分可能是不同的，对应于每一种划分，都有一个误差平方和。所以，的值依赖于样本的划分，使最小的一种划分就定义为最小误差划分。误差平方准则函数的性能：

当各群的样本都很密集，且彼此之间明显分开时，是一种合适的准则函数。

当各群中样本数目相差很大时，用误差平方和准则分群有时会产生一些问题，有可能把大的自然群拆成两个。迭代最优化方法集群划分的准则函数选定后，就要找出样本的一种划分，使准则函数取极值，这样集群问题就变成了一个组合优化问题。由于样本数目有限，所以可能的划分也是有限的，我们首先想到的方法是穷举法，即遍历各种划分，使准则函数取极值的划分为最优划分。

穷举法只适合数据规模比较小的场合。

设有个样本，要求分为组，使每组都不为空的划分大约有种，如果将有种分法，显然这时用穷举法是不可取的。迭代最优化方法是寻找最优分划的常用方法。基本思想：是找一个合理的初始划分，然后试探性地将样本从一个群搬到另一个群。只要某次搬动能使准则函数的值有所改进的话，就认为这次搬动是正确的，然后选择下一个样本继续如法进行。如果某次搬动使准则函数的值变坏，则样本退回到原来的群中去。

如图示：初始划分搬动一个样本

下面我们通过误差平方和准则函数的极小化来说明迭代最优化算法。其中假定我们把原来在中的一个样本试探性地搬到中去，则变成：上式可写成：而

对于，取，就是说，只有一个样本的群不要取消掉，则类似上面的推导方法，可得

如果把从第群搬到第群后，减少的量比增加的量多，即：

则说明对这次搬动改进了准则函数的值。

算法步骤：Step1选择把个样本分成个群的初始分划，计算；Step2选择下一个备选样本，设从中选出；Step3若，则转向Step6，否则计算Step4对于一切，若，则将放到中；Step5修改和的值；Step6若经过次试验后，不变，则停止，否则转Step2。这种方法的缺陷：（1）对初始划分敏感；（2）结果与备选样本的次序有关，会陷入局部极值。C-均值算法(基于最近距离的聚类方法)1.根据指定群数，任选个代表点作为群的群心，一般以开头个样本作为初始群心。2.逐个将样本集中的每个样本归入与之最近的群心所代表的群，形成个群，即在第次迭代时，若则表示第次迭代时，以第个群心为代表群。3.计算新的群心，即

为第个群域中的样本个数。4.若，算法收敛，算法停止，否则转步骤2。Ｃ－均值算法举例C=2设样本集中的样本为二维模式样本，表示如下：１１２３４５２３４５x1x2··2.672.5Step1

取

Step2

分群Step3计算新的群心Step4判断

Step2分群

Step3计算新的群心

Step４判断

Step２分群

Step３计算新的群心

Step４判断

因为及所以算法收敛，分群结束。C-均值算法的结果受到下列因素的影响:C个初始分群中心的选取；与样本的选取次序有关；与样本的几何分布有关；与样本数量差异的大小有关；

一般地，对于给定样本集，分群结果是唯一的吗？等级集群方法问题：当不知道要分成几群时，而要把一些未分类的样本分成若干合理的群时，如何做呢？

在没有指定群数的情况下，n个样本至少可以分成一个群，这就是样本的全体；最多可以把它们分成n个群，每个群只有一个样本。显然，这样的分群没有意义。但是，我们可以由此考虑(n个群一个群）的过程，这样，我们就可以把集群看作是一个把n个样本聚集成K个群的集群序列的结果。反之，把(一个群n个群），看做把n个样本划分成K个群的划分序列的结果。这样，可以有两种产生序列的方法：１．凝聚法

从n个样本划分为n个群开始，每个群中只有一个样本，然后通过不断的合并而形成一个聚合的序列，最后凝聚成一个包含全部样本的大群。

这种方法效果比较好，容易实现，是经常使用的方法之一。２.分解法凝聚法的反方向

我们主要讨论凝聚法这种等级集群方法可以表示成一棵分类树，来实现样本分群的过程。聚类水平高相似度

相似聚类，用距离度量，距离可以有不同的度量方法，采用的类间距离不同，聚类过程是不一样的。（1）近点距离法（2）远点距离法

（3）平均法

（4）离差平方和法

关于近点距离法和远点距离法的性能请参考教材的87-89页的内容。

基于近点距离的等级集群算法步骤

对于样本集，设表示第次合并时的第类（1）初始分类，令,，（2）计算各类间的距离，由此生成一个对称的距离矩阵，为类的个数。（初始时）