第5章近邻法则和集群

1、第第5 5章章 近邻法则和集群近邻法则和集群 近邻法则近邻法则 近邻法则的错误率近邻法则的错误率 K-近邻法则近邻法则 快速近邻算法快速近邻算法 集群的准则函数集群的准则函数 迭代最优化方法迭代最优化方法 等级集群方法等级集群方法 一一. 近邻法则近邻法则 设有一个已知类别的样本集：设有一个已知类别的样本集：样本集中的样本分别属于样本集中的样本分别属于 个类别个类别:设每类的样本数分别为设每类的样本数分别为:如果这如果这n个样本中与待分类样本个样本中与待分类样本X距离最近的距离最近的一个样本为一个样本为X，则把，则把X分到分到X所属的类别。所属的类别。12,.,nXXXc12,.,.ic 12

2、,.,.icnnnn近邻法则的判别函数为近邻法则的判别函数为:决策规则决策规则:若若 则把则把 分到分到 类。类。 可以看出近邻法则计算非常简单，但是这个方可以看出近邻法则计算非常简单，但是这个方法如何？法如何？（1）分类能力如何？）分类能力如何？（2）分类错误率如何？）分类错误率如何？能否给出定性与定量的解释？能否给出定性与定量的解释？nkciXXXgkii, 2 , 1, 2 , 1min)(,),()(jiXgXgjiXi二二. 近邻法则的分类能力近邻法则的分类能力 中有中有 个类别的样本个类别的样本,每个类别有每个类别有 个样本个样本,每次从每次从 中取出一个样本中取出一个样本,比较与

3、比较与 的的相近程度相近程度,由于每次取出的样本是随机的由于每次取出的样本是随机的,因而样本的类别因而样本的类别状态也是随机的。把状态也是随机的。把 的最近邻的最近邻 的类别状态看成一个的类别状态看成一个随机变量随机变量 （ 可能是可能是 中的任意一个）。中的任意一个）。 于是，于是， 的概率就是后验概率的概率就是后验概率 ，当样本，当样本的数目越来越多时，可以认为的数目越来越多时，可以认为 的最近邻的最近邻 离它越来越离它越来越近，从而：近，从而： 这样，就可以把近邻法则看成是由概率这样，就可以把近邻法则看成是由概率 来决定来决定 的类别。的类别。12,.,nXXXc,1,2,.,in ic

4、iXX X)|(XPi)|()|(XPXPiiXX )|(XPiXc,21（1）在近邻法则中，）在近邻法则中， 的最近邻的类别状态为的最近邻的类别状态为 的的概率为概率为 ，所以，所以 分到分到 类的概率类的概率为为 ，而不分到的概率为，而不分到的概率为（2）我们已经知道，在）我们已经知道，在Bayes决策中决策中,有有 取取 作为作为 的类别。的类别。 比较比较Bayes决策和近邻法则，可以看出：决策和近邻法则，可以看出： 按按Bayes决策法则：以概率决策法则：以概率1决策决策 按最近邻法则：以概率按最近邻法则：以概率 决策决策mmmmmXXX)|(XPm)|(XPm)|(1XPm)|(X

5、Pm)|(max)|(XPXPim举例说明举例说明:设在三个类别问题中，设在三个类别问题中， 的后验概率分别为：的后验概率分别为：按按Bayes决策：决策：因为因为所以所以按近邻法则决策：按近邻法则决策：有有0.4的概率的概率 有有0.3的概率的概率 有有0.3的概率的概率123|0.4|0.3|0.3pXpXpX123|0.4|0.3pXpXpX1X123XXXX（1 1）当）当 接近接近1 1时，近邻法则的错误概率时，近邻法则的错误概率, ,与与BayesBayes决策的结果几乎相同，说明这两种方法决策的结果几乎相同，说明这两种方法同样同样“好好”。（2 2）当）当 ，两者的错误概率都接，

6、两者的错误概率都接 近近 ，说明两种方法同样，说明两种方法同样“坏坏”。 由于由于BayesBayes分类器是最优分类器，与分类器是最优分类器，与BayesBayes分类分类器的比较可以看出，近邻法则有较好的分类性器的比较可以看出，近邻法则有较好的分类性质。质。|mPX1|mPXc11c5.1.2 近邻法则的错误率近邻法则的错误率回顾回顾:最小错误概率的最小错误概率的Bayes决策中的有关内容决策中的有关内容 模式特征模式特征 是一个随机变量，用后验概率是一个随机变量，用后验概率 作出分类决策时，会有错误分类的可能性作出分类决策时，会有错误分类的可能性,对于对于每个不同的每个不同的 值值,其其

7、 也不同也不同,从而分类错误从而分类错误概率也不同概率也不同,所以分类错误概率所以分类错误概率 可以看作是可以看作是 的函数的函数. 如果已知连续随机变量如果已知连续随机变量 的概率密度函数为的概率密度函数为 的数学期望的数学期望 为为:x|iPxx|iPx|P e xx|P e x p e |P eP e x p x dxx)(xp 对于模式向量对于模式向量 , ,由于由于 是一个是一个随机变量随机变量, , 所以有所以有: : 对于每个观察向量对于每个观察向量 ， 如果使如果使 尽可能尽可能小的话，则上式积分也必定尽可能小。从而错小的话，则上式积分也必定尽可能小。从而错误概率误概率 就达到

8、极小。若记就达到极小。若记 是是 的极小值，的极小值， 是是 的极小值，则：的极小值，则： |P eP e X p X dX*|Pe X P e|P e X|P e X*P P e*|1|mPe XPX *|PPe X p X dX12,.,TnXx xxXX 在什么情况下可以取得最小值？在什么情况下可以取得最小值？ 在在 ，A为小于为小于1的正常的正常数下，数下， 最小。最小。 也就是说，一个最大，其余都相等时，有最小值。也就是说，一个最大，其余都相等时，有最小值。这样就有：这样就有：miciAXPi, 2 , 1,)|()|(12XPcii*(|)1(|)( |)imi mPXPXP e

9、X )|(12XPcii对于近邻法则对于近邻法则,设设 是采用是采用 个样本时的错误个样本时的错误概率，并设概率，并设则有近邻法则错误率的上下限：则有近邻法则错误率的上下限：先求先求 limnnPP e*21cPPPPcn nPeP 设用某一组设用某一组N个已知类别的样本对个已知类别的样本对 分类，如分类，如果果 的最近邻样本为的最近邻样本为 ，则把，则把 分到分到 所属所属的类别。的类别。 如果用不同组的如果用不同组的N个样本对个样本对 分类，则分类，则 的最的最近邻近邻 可能是完全不同的可能是完全不同的 。由于近邻决策完全。由于近邻决策完全取决于取决于 的最近邻样本，所以错误概率与的最近邻

10、样本，所以错误概率与 ， 有关，即有关，即 。 每次取一组样本做最近邻决策，每次都有一定每次取一组样本做最近邻决策，每次都有一定的错误概率，如果对的错误概率，如果对 取平均，则有：取平均，则有：XXXXXXXnXnXnXnX),|(nnXXeP)|(),|()|(nnnnndXXXpXXePXePnX对于对于 数学表达式是难以获得的。数学表达式是难以获得的。如何考虑解决求如何考虑解决求 的问题呢？的问题呢？ )|(),|()|(nnnnndXXXpXXePXeP( |)nP e X 如果如果 能够趋近于一个中心在能够趋近于一个中心在 的的 函函数，则该式的计算就可以大大简化了。数，则该式的计算

11、就可以大大简化了。设想：设想：因为因为 是是 的最近邻，可以期望密度函数的最近邻，可以期望密度函数 在在 的附近有一个陡峭的峰，而在其它的附近有一个陡峭的峰，而在其它地方则很小。地方则很小。这是什么含义呢？这是什么含义呢？ 在已知在已知 的条件下，的条件下， 的最近邻的最近邻 在在 的附的附近的概率密度最大。近的概率密度最大。可以这样设想的依据：可以这样设想的依据： 相同类别的样本特征相同或相近，分布最集中。相同类别的样本特征相同或相近，分布最集中。X)|(XXpnnXX)|(XXpnXXXXnX举例说明：举例说明：XX)|(XXpn 为了证明当为了证明当n趋于无穷大时，趋于无穷大时， 可能趋

12、可能趋于一个中心在于一个中心在 的的 函数，我们设对于给定函数，我们设对于给定的的 ，概率密度是连续的且不为零。这样，任何，概率密度是连续的且不为零。这样，任何样本落在以样本落在以 为中心的一个超球为中心的一个超球S中的概率记为：中的概率记为： 落在落在S以外的概率为以外的概率为 , 当样本独立抽取时，全部当样本独立抽取时，全部n个独立抽取的样本落个独立抽取的样本落在在S以外的概率就为以外的概率就为 )|(XXpnXXX)(dXXpPSXS)1 (SPnSP )1 ( 当当 时时这就是说，总有一个以上的样本落在这就是说，总有一个以上的样本落在S内的概率为内的概率为1.由于由于S可以任意小，所以

13、当可以任意小，所以当S很小时，只要样本数很小时，只要样本数n足够大，总有足够大，总有 的近邻在的近邻在S内，所以，内，所以， 以概率以概率1收敛于收敛于 。 这就证明了当这就证明了当n趋于无穷大时，趋于无穷大时， 趋于趋于 函数。函数。 即即 n0)1 (nSP)()|(limXXXXpnnnnXX)|(XXpnX下面讨论错误概率下面讨论错误概率将将n个独立抽取的已知类别的样本表示成二元对的个独立抽取的已知类别的样本表示成二元对的形式：形式：其中其中 是是C个类别状态个类别状态 中的任意一个。中的任意一个。现在假定抽取一对现在假定抽取一对 ，并假定，并假定 是是 的最近的最近邻，类别为邻，类别

14、为 ，即，即 是是 的最近邻，的最近邻，由于由于 和和 是独立抽取的，是独立抽取的， 的类别状态和的类别状态和 的类别状态无关，因此就有：的类别状态无关，因此就有：当采用近邻法则时，如果当采用近邻法则时，如果 就会产生分类错误，就会产生分类错误，),|(nnXXeP),( ,),(),(2211nnXXXc,21i),(XnXXn),(nnX),(XXnXnXX)|()|(),|,(nnnnnXPXPXXPn因为当因为当 时有时有 （ 以概率以概率1收敛于收敛于 ）所以所以n),|,(1),|(1ninciinnXXPXXeP)|()|(11niciiXPXP)|()|(XPXPininXX)

15、|(1),|(12limXPXXePciinnn错误概率为错误概率为 对于对于当当 可以写成：可以写成：这样，近邻法则的错误率为这样，近邻法则的错误率为)|(),|()|(nnnnndXXXpXXePXePn)|(),|()|(limlimnnnnnnndXXXpXXePXeP12)()|(1 nnciidXXXXP)|(112XPcii( )( |) ()limlimnnnnPP eP e X p X dXdXXpXPcii)()|(1 12下面我们开始证明最近邻法则错误率下面我们开始证明最近邻法则错误率 的上下界。的上下界。要证明要证明 的下界为的下界为 ，只要指出在某些特定情况，只要指出

16、在某些特定情况下存在下存在 就可以了就可以了。（为什么，请思考）（为什么，请思考）1. 在在 时（时（ ， ） 所以在这种情况下成立。所以在这种情况下成立。P*PP*PP 1)|(XPm0)|(XPimi dXXpXPPcii)()|(1 12dXXp)( 11 0dXXpXPdXXpXePPm)()|(1 )()|(*02. 在在 时（各后验概率都相等）时（各后验概率都相等） 所以在这种情况下也成立。所以在这种情况下也成立。 CXPi1)|(dXXpXPPcii)()|(1 12dXXpCci)()1(1 212111() ()cip X dXCCC1dXXpCdXXpXePP)()11 (

17、)()|(*CC1 思考：思考： 通过通过P的下界的证明，可以采用在特殊情况有的下界的证明，可以采用在特殊情况有P=P*就可以。那么对于就可以。那么对于P的上界的证明可不可以的上界的证明可不可以也这样做？也这样做？ 下面证明下面证明P的上界。的上界。 要证明要证明P的上界，关键的问题是如何将最近邻法的上界，关键的问题是如何将最近邻法则的错误率则的错误率P和最小错误概率的贝叶斯错误率和最小错误概率的贝叶斯错误率P*联系起来。联系起来。由前面的推导已经知道了最近邻法则的错误率为：由前面的推导已经知道了最近邻法则的错误率为：由最小错误概率的由最小错误概率的Bayes决策决策( )可知最小错误概率为：

18、可知最小错误概率为：这两个公式对我们的启发是：这两个公式对我们的启发是：对已知的对已知的 而言，而言， 的最小值对应着的最小值对应着P的最大值，如果能求得的最大值，如果能求得P的最大值，就把的最大值，就把P*和和P联系起来了。联系起来了。dXXpXPPcii)()|(1 12)|(1)|(*XPXePm)|(XPm)|(12XPcii)|(max)|(, 2, 1XPXPicim由数学知识可知：由数学知识可知： 在在 ，A为小于为小于1的正常的正常数下，数下， 最小。最小。 这样就有：这样就有：而而所以，所以，miciAXPi, 2 , 1,)|()|(12XPcii)|() 1() 1()|

19、(XPcAcXPimii*(|)1(|)( |)imi mPXPXP e X miXePmicXePXPi),|(1,1)|()|(*从而可得：从而可得： )|()|()|(2212XPXPXPimimciimicXePXeP22*2*) 1()|()|(1 1)|()|(1 2*2*cXePXeP)|(1)|(212*XePccXeP极小时得出极小时得出即即整理得：整理得： 由于由于根据方差的定义：根据方差的定义： 有：有：)|(1)|(21)|(2*12XePccXePXPciidXXpXePP)()|(*)|(PXePEdXXpX)()(22dXXpPXePXePVar)()|()|(2

20、*)|(1)|(2)|(12*12XePccXePXPcii（5-15）把右式展开，把右式展开，dXXpPdXXpXePPdXXpXeP)()()|(2)()|(2*2*dXXpPXePPXeP)()|(2)|(2*2*2*2*2*2)()|(PPdXXpXeP2*2*)()|(PdXXpXeP由于方差非负，所以由于方差非负，所以从而，从而，如果如果 ，对下式（，对下式（5-15）两边取积分，）两边取积分，得得0)()|(2*2*PdXXpXePdXXpXePP)()|(2*2*dXXpXePccXePdXXpXPcii)()|(1)|(2)()|(1 2*12等号只在方差等号只在方差为为0时

21、成立时成立0)(Xp)|(1)|(2)|(12*12XePccXePXPcii可以看出，左式可以看出，左式=P，所以，所以dXXpXePccXePP)()|(1)|(22*dXXpXePccdXXpXeP)()|(1)()|(22*2*12PccP)12(*PccP*(2)1cPPPc5.1.3 K -近邻法则近邻法则 K- -近邻法是最近邻法的一个改进。近邻法是最近邻法的一个改进。 有有 个已知类别的样本，个已知类别的样本， 的的 个近邻中，个近邻中， N12,.,NXXX1212,.,.ccNNN12.cNNNNXk1212,.,.cckkk12.ckkkk1,2,.maxmiickkmX

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

23、虑决策的风险，如果错误代 价很大时，会产生很大风险。价很大时，会产生很大风险。 （3）错误率分析是）错误率分析是 情况下得出的，而情况下得出的，而 对有限样本集理论依据不充分。对有限样本集理论依据不充分。 可以看出，（可以看出，（2）和（）和（3）是近邻法则的固有问）是近邻法则的固有问题，题，那么通过什么方法可以改善缺点那么通过什么方法可以改善缺点(1)呢呢? N 5.1.5 快速近邻算法快速近邻算法 1.分量邻域法分量邻域法 思路：近邻法则思路：近邻法则与与 的近邻样本有的近邻样本有关，那就关注近邻关，那就关注近邻样本。样本。方法：方法： 是待分类的是待分类的模式，以模式，以 为中心，为中心

24、，构造边长为构造边长为 的邻域，的邻域， 逐渐扩大该邻域，逐渐扩大该邻域， 直直至有一个样本至有一个样本 落入这个邻域时为止。落入这个邻域时为止。X2dXXX算法：算法： 输入输入: 维训练样本集维训练样本集, ,待分类样本待分类样本 ；输出输出: 的最近邻的最近邻 ；步骤步骤:(1)以以 为中心为中心,构造一个构造一个 为边长的邻域为边长的邻域 。(2)在在 中找出落入的训练集中找出落入的训练集 的样本，如果的样本，如果 为空，为空，则增加则增加 一个级差一个级差 , 转步骤转步骤(1)。(3)对全部对全部 计算距离计算距离 ，最小者即为，最小者即为 的最近邻。的最近邻。该算法存在一个什么问

25、题？该算法存在一个什么问题？n12,.,mX XXXXXX2dCCC2dXXX X算法：算法： 输入输入: 维训练样本集维训练样本集, ,待分类样本待分类样本 ；输出输出: 的最近邻的最近邻 ；步骤步骤:(1)以以 为中心为中心,构造一个构造一个 为边长的邻域为边长的邻域 。(2)在在 中找出落入的训练集中找出落入的训练集 的样本，如的样本，如 为空，则增为空，则增加加 一个级差一个级差 ,转转(1)。(3)扩大邻域扩大邻域 到到 ，找出全部落入这个邻域中训练，找出全部落入这个邻域中训练集集 的样本，即的样本，即 的一个子集的一个子集 。(4)对全部对全部 计算距离计算距离 ，最小者即为，最小

26、者即为 的最近邻。的最近邻。算法优点：简单，快速。缺点：特征维数高时，效率低。算法优点：简单，快速。缺点：特征维数高时，效率低。n12,.,mX XXXXXX2dCCC2d2d2 ndXXX X2.列表法列表法(1)预处理阶段预处理阶段 在模式空间指定任意三个点在模式空间指定任意三个点 。分别。分别计算这三个点到训练样本集中全部成员的距离。计算这三个点到训练样本集中全部成员的距离。对对 以以从近到远从近到远的顺序列出所有的成员。的顺序列出所有的成员。 构成三个表构成三个表 。, ,A B C, ,A B C, ,A B C A1aX2aXiaX1bX1iaX1naXnaXB 2bXjbX1jb

27、X1nbXnbXC 1cX2cXkcX1kcX3cX2ncX1ncXncX计算待分类模式计算待分类模式 到到 的距离的距离, 。在表在表 中分别按中分别按 将将 嵌入相应的嵌入相应的位置上。位置上。 A1aX2aXiaXX1bX1iaX1naXnaXB 2bXjbXX1jbX1nbXnbXC 1cX2cXkcXX1kcX3cX2ncX1ncXncXX, ,A B C,ABCddd, ,A B C,ABCdddX(2)搜索阶段搜索阶段 在表在表 中取中取 的近邻形成三个子集的近邻形成三个子集 若若 非空非空,则交集中的元素就可能包含则交集中的元素就可能包含 的最近邻。的最近邻。若若 为空为空,

28、则逐步扩大则逐步扩大 的邻的邻域的范围。域的范围。直至直至 非空非空, 找到找到 的最近邻。的最近邻。, ,A B CX,ABC ABCXABCXABCX5.2 集群（聚类集群（聚类 clustering) 采用有类别标识的训练样本集来实现对待识别模采用有类别标识的训练样本集来实现对待识别模式式 的分类，称为的分类，称为有监督学习或有教师学习有监督学习或有教师学习。如线性判别函数，如线性判别函数，Bayes决策，近邻法则等。决策，近邻法则等。 把没有训练样本集时的分类方法，即无监督的把没有训练样本集时的分类方法，即无监督的或无教师的分类方法叫做或无教师的分类方法叫做集群集群。 集群问题中有两种

29、情况：集群问题中有两种情况：预先指定分群的数目预先指定分群的数目1.预先不知道分群的数目预先不知道分群的数目X 面对一组待分类的模式，根据什么分类呢？面对一组待分类的模式，根据什么分类呢？ 实际上，集群的目的就是要在一组数据中找出实际上，集群的目的就是要在一组数据中找出自然形成的数据群，而一群中的样本彼此之间应自然形成的数据群，而一群中的样本彼此之间应该比其它群的样本之间更相像一些。该比其它群的样本之间更相像一些。 也就是说，也就是说，根据各个待分类的模式特征的相似根据各个待分类的模式特征的相似程度进行分类，把相似的归为一类。程度进行分类，把相似的归为一类。 因此，集群应该解决两个问题：因此，

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

31、适当的距离来度量相似性。如果这个距离是相似性的一个好的度相似性。如果这个距离是相似性的一个好的度量，那么我们就可以期望在同一群内样本之间量，那么我们就可以期望在同一群内样本之间的距离将明显小于不同群的样本之间的距离。的距离将明显小于不同群的样本之间的距离。 12,.TnXx xx欧氏距离：欧氏距离：用距离来度量相似性，存在阈值用距离来度量相似性，存在阈值 的选择问题。的选择问题。 如果太大如果太大 ，则可能把全部，则可能把全部 样本归到同一个群中去。样本归到同一个群中去。 如果太小如果太小 ，则每个样本为，则每个样本为 一个群。一个群。 显然，上述两种情况都失去了分群显然，上述两种情况都失去了

32、分群 的意义。的意义。d1d21221,niiiSX XXXxx0d01dd02dd 为了得到合适的自然数据群，阈值为了得到合适的自然数据群，阈值 应当选得应当选得大于可作为代表的群内距离和小于可作为代表大于可作为代表的群内距离和小于可作为代表的群间距离。的群间距离。 （群内距离），（群内距离）， （群间距离）（群间距离） 两向量间的距离度量有许多种，除了欧氏距两向量间的距离度量有许多种，除了欧氏距离外还有几个常用距离：离外还有几个常用距离：dd 0dd 01. Mahalanobis距离距离 式中式中 为样本各特征的协方差矩阵。为样本各特征的协方差矩阵。2. Minkovsky距离距离 式中

33、式中 为样本维数。为样本维数。3. Camberra距离距离4. Chebychev距离距离121,TS X XXXWXXW1,diiiS X Xxxd1,diiiiixxS X Xxx,maxjjjS X Xxx5.2.2 集群的准则函数集群的准则函数 前面介绍了如何评定样本间的相似性，现在讨前面介绍了如何评定样本间的相似性，现在讨论如何根据样本间的相似性把一组样本划分为不同论如何根据样本间的相似性把一组样本划分为不同的群的方法。的群的方法。 假设有样本集假设有样本集 ，要求把它分成，要求把它分成 c 个不相交的子集个不相交的子集 ，每个子集表示一群样本。，每个子集表示一群样本。对这个划分的

34、要求是：对这个划分的要求是：在同一群内的样本比不同群在同一群内的样本比不同群的样本更相像一些。的样本更相像一些。 由于距离阈值由于距离阈值 的选取不同，分群的结果也不的选取不同，分群的结果也不同。同。群的划分具有人为规定性。群的划分具有人为规定性。12,.,nx xx 12,.c 0d 所以需要定义一个准则函数，利用它来度量数所以需要定义一个准则函数，利用它来度量数据划分所形成的群的性质，据划分所形成的群的性质，这样就把分群的问题这样就把分群的问题变成使这个准则函数取极值的问题。变成使这个准则函数取极值的问题。 误差平方准则误差平方准则设是设是 中样本的数目，中样本的数目， 是这些样本的均值是

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

36、间明显分当各群的样本都很密集，且彼此之间明显分开时，开时， 是一种合适的准则函数。是一种合适的准则函数。eJc12,.cm mmcceJeJeJeJ 当各群中样本数目相差很大时，用误差平方当各群中样本数目相差很大时，用误差平方和准则分群有时会产生一些问题，有可能把大和准则分群有时会产生一些问题，有可能把大的自然群拆成两个。的自然群拆成两个。迭代最优化方法迭代最优化方法 集群划分的准则函数选定后，就要找出样本集群划分的准则函数选定后，就要找出样本的一种划分，使准则函数取极值，这样集群问题的一种划分，使准则函数取极值，这样集群问题就变成了一个组合优化问题。就变成了一个组合优化问题。 由于样本数目有

37、限，所以可能的划分也是有由于样本数目有限，所以可能的划分也是有限的，我们首先想到的方法是限的，我们首先想到的方法是穷举法穷举法，即遍历各，即遍历各种划分，使准则函数取极值的划分为最优划分。种划分，使准则函数取极值的划分为最优划分。 穷举法只适合数据规模比较小的场合。穷举法只适合数据规模比较小的场合。 设有设有 个样本，要求分为个样本，要求分为 组，使每组都不组，使每组都不 为空的划分大约有为空的划分大约有 种，如果种，如果 将有将有 种分法，显然这时用穷举法是不可取的。种分法，显然这时用穷举法是不可取的。 迭代最优化方法是寻找最优分划的常用方法。迭代最优化方法是寻找最优分划的常用方法。 基本思

38、想：基本思想：是找一个合理的初始划分，然后试是找一个合理的初始划分，然后试探性地将样本从一个群搬到另一个群。只要某次探性地将样本从一个群搬到另一个群。只要某次搬动能使准则函数的值有所改进的话，就认为这搬动能使准则函数的值有所改进的话，就认为这次搬动是正确的，然后选择下一个样本继续如法次搬动是正确的，然后选择下一个样本继续如法进行。如果某次搬动使准则函数的值变坏，则样进行。如果某次搬动使准则函数的值变坏，则样本退回到原来的群中去。本退回到原来的群中去。 nc!ncc100,5nc6710如图示：如图示：初始划分初始划分搬动一个样本搬动一个样本 下面我们通过误差平方和准则函数的极小化下面我们通过误

39、差平方和准则函数的极小化来说明来说明迭代最优化算法迭代最优化算法。 其中其中 假定我们把原来在假定我们把原来在 中的一个样本中的一个样本 试探性试探性地搬到地搬到 中去，则中去，则 变成：变成： 1ceiiJJijixiimxJ2ixiixnm1x jmjxjjxxnm) (11*上式可写成：上式可写成：而而)(11) (11*jjjjjjjjjmxmmnnxmnnm1jjjnmxm2*2*jxjjmxmxJj2*2*jxjjmxmxJj22)1()1(jjjxjjjnmxmxnmxmxj222)(1)(1)(2)(11jjjjjjjjxjmxnnmxnmxmxnmxj22)(11jjjxjj

40、jmxnnnmxmxj 22222()1()()(1)1()1jjjjjjjxxxjjjjjxmxmxmxmnnnxmn22222) 1() 1(jjjjjjjmxnnmxnnJ2) 1(jjjjmxnnJ 对于对于 ，取，取 ，就是说，只有一个样本的，就是说，只有一个样本的群不要取消掉，则类似上面的推导方法，可得群不要取消掉，则类似上面的推导方法，可得 如果把如果把 从第从第 群搬到第群搬到第 群后，群后， 减少的量减少的量比比 增加的量多，即：增加的量多，即： 则说明对这次搬动改进了准则函数的值。则说明对这次搬动改进了准则函数的值。 1in ijiJjJ1*iiiinmxmmx 2211j

41、iijijnnxmxmnn2*1iiiiimxnnJJi算法步骤：算法步骤：Step1 选择把个样本分成个群的初始分划，选择把个样本分成个群的初始分划，计算计算 ；Step2 选择下一个备选样本，设从选择下一个备选样本，设从 中选出中选出 ；Step3 若若 ，则转向，则转向Step6，否则计算，否则计算Step4 对于一切对于一切 ，若，若 ，则将，则将 放到放到 中；中；nc,1,2,.,eiJ m icXX1in 22,1,1jjjjiiinXmjinnXmjinjkjikStep5 修改修改 和和 的值；的值；Step6 若经过若经过 次试验后，次试验后， 不变，则停止，不变，则停止，

42、 否则转否则转Step2 。这种方法的缺陷：这种方法的缺陷：（1）对初始划分敏感；）对初始划分敏感；（2）结果与备选样本的次序有关，会陷入）结果与备选样本的次序有关，会陷入局部局部极值极值。,eiJ mkmneJC-均值算法均值算法(基于最近距离的聚类方法基于最近距离的聚类方法)1. 根据指定群数根据指定群数 ，任选，任选 个代表点作为个代表点作为 群群的群心的群心 ， 一般以开头一般以开头 个样本作为初始群个样本作为初始群心。心。2. 逐个将样本集中的每个样本归入与之最近的群逐个将样本集中的每个样本归入与之最近的群心所代表的群，形成心所代表的群，形成 个群，即在第个群，即在第 次迭次迭代时，

43、代时， 若若 则则 表示第表示第 次迭代时，以第次迭代时，以第 个群心为代表群。个群心为代表群。cccc12(1),(1),(1)czzzcm( )( ) ,1,2,., ,jixzmxz mic ij( ),( )jjxfmfmmj3. 计算新的群心，即计算新的群心，即 为第为第 个群域中的样本个数。个群域中的样本个数。4. 若若 ，算法收敛，算法收敛，算法停止，否则转步骤算法停止，否则转步骤2。()1(1),1,2,.,iixfmiz mx icNiNi(1)( ),1,2,.,iiz mz m ic均值算法举例均值算法举例 C=2设样本集中的样设样本集中的样本为二维模式样本，表示如下：本

44、为二维模式样本，表示如下：12345678,x x x x x x x x 123456780,0,1,0,0,1,1,13,3,3, 4,4,3,4, 4TTTTTTTTxxxxxxxxx1x21x3x5x6x7x8x4x2x 22z 12z2.672.5Step 1 取取 Step 2 分群分群 112210,0,11,0TTzxzx 111211212222313231414242515252818282111111111111111111xzxzxfxzxzxfxzxzxfxzxzxfxzxzxfxzxzxfStep3 计算新的群心计算新的群心 11322456781,1,fx xfx

45、 x x x x x 111311112()(0,0.5)2TxfzxxxN 2224567812112()611,01,13,33,44,34,462.67,2.5xfTTTTTTTzxxxxxxxNStep4 判断判断 Step2 分群分群 112221212zzzzStep及返回 111211212221313231414241222222222222xzxzxfxzxzxfxzxzxfxzxzxf 11234256782,2,fx xx xfx x xx )2()2(2515zxzx)2(25fx )2()2(2616zxzx)2(26fx )2()2(2717zxzx)2(27fx

46、)2()2(2818zxzx)2(28fx Step 3 计算新的群心计算新的群心 Step 判断判断 12112343125678321130.5,0.541133.5,3.54TxfTxfzxxxxxNzxxxxxN 112232322zzzzStep及返回 Step 分群分群 Step 计算新的群心计算新的群心 Step 判断判断 因为因为 及及 所以所以 算法收敛，分群结束。算法收敛，分群结束。) 3()4(11zz) 3()4(22zzC-均值算法的结果受到下列因素的影响均值算法的结果受到下列因素的影响:vC个初始分群中心的选取；个初始分群中心的选取；v与样本的选取次序有关；与样本的

47、选取次序有关；v与样本的几何分布有关；与样本的几何分布有关；v与样本数量差异的大小有关；与样本数量差异的大小有关；一般地，对于给定样本集，分群结果是唯一的吗？一般地，对于给定样本集，分群结果是唯一的吗？等级集群方法等级集群方法问题：问题：当不知道要分成几群时，而要把一些未分当不知道要分成几群时，而要把一些未分类的样本分成若干合理的群时，如何做呢？类的样本分成若干合理的群时，如何做呢？在没有指定群数的情况下，在没有指定群数的情况下，n个样本至少可以个样本至少可以分成一个群，这就是样本的全体；最多可以把它分成一个群，这就是样本的全体；最多可以把它们分成们分成n个群，每个群只有一个样本。个群，每个群

48、只有一个样本。 显然，这显然，这样的分群没有意义。样的分群没有意义。 但是，我们可以由此考虑但是，我们可以由此考虑(n个群个群 一个群）的一个群）的过程，这样，我们就可以把集群看作是一个把过程，这样，我们就可以把集群看作是一个把 n个样本聚集成个样本聚集成 K个群的个群的集群序列集群序列的结果。的结果。 反之，把反之，把(一个群一个群 n个群），看做把个群），看做把n个样本划个样本划分成分成K个群的个群的划分序列划分序列的结果。的结果。 这样，可以有两种产生序列的方法：这样，可以有两种产生序列的方法：凝聚法凝聚法从从n个样本划分为个样本划分为n个群开始，每个群中只有个群开始，每个群中只有一个样

49、本，然后通过不断的合并而形成一个聚一个样本，然后通过不断的合并而形成一个聚合的序列，最后凝聚成一个包含全部样本的大合的序列，最后凝聚成一个包含全部样本的大群。群。 这种方法效果比较好，容易实现，是经常使这种方法效果比较好，容易实现，是经常使用的方法之一。用的方法之一。. 分解法凝聚法的反方向分解法凝聚法的反方向我们主要讨论凝聚法我们主要讨论凝聚法这种等级集群方法可以表示成一棵分类树，来这种等级集群方法可以表示成一棵分类树，来实现样本分群的过程。实现样本分群的过程。聚类聚类水平水平高高相似度相似度 相似聚类，用距离度量，距离可以有不同的相似聚类，用距离度量，距离可以有不同的度量方法，采用的类间距

50、离不同，聚类过程是度量方法，采用的类间距离不同，聚类过程是不一样的。不一样的。 （1）近点距离法）近点距离法 （2）远点距离法）远点距离法min, (,)minijijxxdxx max, (,)maxijijxxdxx （3）平均法）平均法 （4）离差平方和法）离差平方和法 关于近点距离法和远点距离法的性能请参考教关于近点距离法和远点距离法的性能请参考教材的材的87-89页的内容。页的内容。 1,ijavgijxxijdxxnn min,ijijdmm 基于近点距离的等级集群算法步骤基于近点距离的等级集群算法步骤 对于样本集对于样本集 ，设，设 表示第表示第 次次合并时的第合并时的第 类类（

51、1）初始分类，令）初始分类，令 , ，（2）计算各类间的距离）计算各类间的距离 ，由此生成一个对称的，由此生成一个对称的 距离矩阵距离矩阵 ， 为类的个数。为类的个数。 （初始时（初始时 ）（3）找出矩阵）找出矩阵 中的最小元素，设它是中的最小元素，设它是 和和 间的距离；间的距离；12,.,Nx xx kiGkiijD kijm mDDmmN1,2,.,iN kD kiG kjG(0) iiGx0k 将将 和和 两类合并成一类，于是产生新的聚两类合并成一类，于是产生新的聚类类（4）检查类的个数，如果类数）检查类的个数，如果类数 大于大于 2，转，转(2)， 否则停止。否则停止。 kiG kjG111121,.,kkkmGGGm 例例 六个样本六个样本 按近点距离法分类按近点距离法分类 解：解： （1）初始时）初始时10,3,1,2