哈工大 模式识别第四章第五章

2023/2/1哈尔滨工业大学电信院宿富林1第四章特征的选择与提取2023/2/1哈尔滨工业大学电信院宿富林2§4.1基本概念

如何确定合适的特征空间是设计模式识别系统另一个十分重要，甚至更为关键的问题。如果所选用的特征空间能使同类物体分布具有紧致性，即各类样本能分布在该特征空间中彼此分割开的区域内，这就为分类器设计成功提供良好的基础。反之，如果不同类别的样本在该特征空间中混杂在一起，再好的设计方法也无法提高分类器的准确性。这一章要讨论的问题就是特征空间如何设计的问题2023/2/1哈尔滨工业大学电信院宿富林3

如何构造一个特征空间，即对要识别的事物用什么方法进行描述、分析的问题？1、物理量的获取与转换(原始测量）这是指用什么样的传感器获取电信号，如摄取景物则要用摄像机。可以称之为原始信息(原始测量，得到测量空间)。2、描述事物方法的选择与设计(特征形成)

在得到了原始信息之后，要对它进一步加工，以获取对分类最有效的信息。

设计所要信息的形式是十分关键的。2023/2/1哈尔滨工业大学电信院宿富林4例用RGB颜色空间和HSI颜色空间右边是原始图像，左边是用HSI空间描述的同一图像(但是为了显示出来，用H对应R，S对应G，I对应B，然后再以RGB的方式显示出来3、特征空间的优化这个层次的工作发生在已有了特征的描述方法之后，也就是已有了一个初始的特征空间，如何对它进行改造与优化的问题。一般说来要对初始的特征空间进行优化是为了降维。即初始的特征空间维数较高。能否改成一个维数较低的空间，称为优化，优化后的特征空间应该更有利于后续的分类计算，这就是本章着重讨论的问题。对特征空间进行优化有两种基本方法：一种为特征选择，一种为特征的组合优化----特征的提取。2023/2/1哈尔滨工业大学电信院宿富林52023/2/1哈尔滨工业大学电信院宿富林6特征选择已有D维特征向量空间，Y={y1,y2,…,yD}，从原有的D维特征空间，删去一些特征描述量，从而得到精简后的特征空间。在这个特征空间中，样本由d维的特征向量描述：X={x1,x2,…,xd}，d＜D。X只是Y的一个子集，每个分量xi必然能在原特征集中找到其对应的描述量xi＝yj。

2023/2/1哈尔滨工业大学电信院宿富林7特征提取找到一个映射关系：

A:Y→X

使新样本特征描述维数比原维数降低。其中每个分量xi是原特征向量各分量的函数，即

Xi=fi(y1,y2,…,yD)

这两种降维的基本方法是不同的。在实际应用中可将两者结合起来使用，比如先进特征提取，然后再进一步选择其中一部分，或反过来。

2023/2/1哈尔滨工业大学电信院宿富林8§4.2类别可分离性判据

对原特征空间优化，就要对优化结果进行评价实际的评价方法，是对系统性能进行测试，测试指标主要有正确率、计算速度、存储容量等。本章讨论的评价方法：目的在于找出对特征空间进行优化的具体算法。对特征空间进行优化是一种计算过程，它的基本方法仍然是模式识别的典型方法：找到一种准则(或称判据，通常用一种式子表示），以及一种优化计算方法，使这种准则达到一个极值。

2023/2/1哈尔滨工业大学电信院宿富林9判据理想的情况是与计算错误率有关的判据直接反映错误率的是贝叶斯公式，在实际中运用有困难采用其他判据2023/2/1哈尔滨工业大学电信院宿富林10可分性判据应满足的要求（1）与错误率有单调关系，这使判据取最大值时错误率也较小（2）当特征独立时

有可加性：

（Jij是第i类与第j类的可分性准则）

（3）度量特性：（4）单调性：加入新的特征时，判据不减小2023/2/1哈尔滨工业大学电信院宿富林11几种常用的可分性判据以计算样本在特征空间离散程度为基础的准则，称为基于距离的可分性判据（重点）基于概率密度分布的可分性判据。基于熵函数的可分性判据（不讲）

2023/2/1哈尔滨工业大学电信院宿富林12一、基于距离的可分性判据基于距离的度量是用来进行分类的重要依据。因为一般情况下同类物体在特征空间呈聚类状态，即从总体上说同类物体内各样本由于具有共性，因此类内样本间距离应比跨类样本间距离小。Fisher准则(也可看成是特征提取方法)正是以使类间距离尽可能大同时又保持类内距离较小这一种原理为基础的。同样在特征选择与特征提取中也使用类似的原理，这一类被称为基于距离的可分性判据。

2023/2/1哈尔滨工业大学电信院宿富林13两类之间的距离：ω1任一点与ω2中任一点的距离和的平均。多类：各类之间的平均距离

:ωi任一点xk(i)与ωj中任一点xj(

j)的距离Pi,Pj是第i类和第j类的先验概率度量类内、类间的距离，可用不同方法，如欧氏距离等。

2023/2/1哈尔滨工业大学电信院宿富林14欧氏距离下的可分性判据欧氏距离：每类均值：所有样本集总均值：平均距离：（判据）令：则得判据的矩阵形式：上述公式是有限样本集，是均值及散度的估计。对于无限样本，

tr：迹2023/2/1哈尔滨工业大学电信院宿富林152023/2/1哈尔滨工业大学电信院宿富林16考虑类内类间欧氏距离的其它判据判据Jd(X)是计算特征向量的总平均距离，以下一些判据则基于使类间离散度尽量大，类内离散度尽量小的考虑而提出。2023/2/1哈尔滨工业大学电信院宿富林17基于距离的可分性判据优缺点距离准则：是样本在特征空间的分布的距离作为特征提取的依据。优点：直观，计算简便。缺点：没有考虑概率分布，因此当不同类样本中有部分在特征空间中交迭分布时，简单地按距离划分，无法表明与错误概率之间的联系。2023/2/1哈尔滨工业大学电信院宿富林18基于概率分布的可分性判据：依据不同类别类分布概率密度函数来优化特征空间不考虑各类的先验概率，或假设两类样本的先验概率相等（如下图），可以看出：如果两类条件概率分布互不交迭，则这两类就完全可分；对所有X都有p(X|ω1)＝p(X|ω2)，则两类就完全不可分。

完全可分重合，完全不可分二、基于概率分布的可分性判据通俗的讲：若不同类别在特征空间的不同区域聚集，则分类就容易，它们重迭的程度越低，越有别于分类，因此这一类可分性判据就是用各种方式来度量它们之间重迭的程度。分布的交叠程度可用概率密度之间距离来描述2023/2/1哈尔滨工业大学电信院宿富林192023/2/1哈尔滨工业大学电信院宿富林20任何函数若满足下列条件，则用于做判据：

1、Jp≥02、当两类完全不交叠时，Jp取最大值若对所有x有：p(X|ω2)≠0时，p(x|ω1)=0，则Jp=max3、当两类分布相同时，Jp=0

若：p(X|ω2)=p(x|ω1)，则Jp=0一种是用p(x|ω1)，p(x|ω2)之间的乘法来计算其重迭程度，像Bhattacharya距离、Chernoff界限等Bhattacharyya距离、Chernoff界限与错误率的上界有直接关系（见第二章）。因此Bhattacharyya距离、Chernoff界限不仅用来对特征空间进行降维优化，而且也用来对分类器的错误率作出估计。另一种用两者间的比值，称为散度。2023/2/1哈尔滨工业大学电信院宿富林212023/2/1哈尔滨工业大学电信院宿富林221、Bhattacharyya距离

和Chernoff界限Bhattacharyya距离显然，当p(X|ω1)＝p(X|ω2)时，JB＝0；而当两者完全不交迭时JB为无穷大Chernoff界限2023/2/1哈尔滨工业大学电信院宿富林232、散度另一种常用的基于概率距离度量的判据是利用似然比或对数似然比。对两类问题，对数似然比为：

可提供ωi对ωj的可分性信息。如果对某个X，当p(X|ω1)＝p(X|ω2)时，则lij=0,反之若两者差异越大，则lij的绝对值也大。

2023/2/1哈尔滨工业大学电信院宿富林24对整个特征空间概率分布的差异程度作出评价，可将对ωi类及对ωj

的平均可分性信息定义为

总的平均可分信息则可表示成散度

2023/2/1哈尔滨工业大学电信院宿富林253、正态分布时可分性判据

若则一维：2023/2/1哈尔滨工业大学电信院宿富林26若则2023/2/1哈尔滨工业大学电信院宿富林274.3特征提取4.3.1按距离度量的特征提取方法

基于距离的可分性判据的实质是Fisher准则的延伸，即综合考虑不同类样本的类内聚集程度与类间的离散程度这两个因素。这种判据的优化体现出降维后的特征空间较好地体现类内密集、类间分离的要求。2023/2/1哈尔滨工业大学电信院宿富林28按欧氏距离度量的特征提取方法基于距离可分性判据的特征优化过程是通过一个线性变换实现的。设在原特征空间一个样本向量表示成X(D维)而在优化特征空间中，样本向量表示成Y(d维)而X与Y之间的关系是：

Y=WTX其中W是一个D×d维矩阵（d<D）目的：利用判据找出一种线性变换W，它可实现这种判据J(Y)=J(W)的极值化。1、J2判据下的特征提取将原特征空间X(D维)通过线性映射Y=WTX降维到特征空间Y中，若X空间的类内离散度矩阵和类间离散度矩阵分别为SW,Sb;则按J2判据的的最后特征提取矩阵W是按如下方式构造的：若矩阵SW-1Sb

的本征值λi按大小顺序列为则选择前d个本征值所对应的本征向量组成变换矩阵WD*d，都可使这些判据J2(W)达到最大值。2023/2/1哈尔滨工业大学电信院宿富林292023/2/1哈尔滨工业大学电信院宿富林30证明：因为：Y=WTX，

设：X的类内和类间离散度矩阵分别为SW,Sb则：Y的类内和类间离散度矩阵分别为SW‘,Sb‘为SW’=WSW’WT,Sb’=WSb’WT

（见第3章中，Fisher准则一节）在使用J2判据下，将其Y的可分性判据表示成变换W的函数：

J2(Y)=tr[(SW’)-1Sb’]则：J2(Y)=tr[(WSWWT)-1(WSbWT)]=J2(W)可以证明：在不降维条件下，即，设W是D*D维的，则J2判据不变J2(Y)=

J2(X)。哈尔滨工业大学电信院宿富林30J2(W)=tr[(WSWWT)-1(WSbWT)]=tr[(WT)-1SW-1W-1WSbWT)]=tr[(WT)-1SW-1SbWT]=tr[SW-1SbWT(WT)-1]=tr[SW-1Sb]=J2(X)设SW-1Sb的本征值为λ1>λ2>λ3>……>λD

，对应的本征向量矩阵为U=[u1，u2,….,uD]则UTSW-1SbU=Λ,其中：令W=UT=U-1则J2(W)=tr[UTSW-1SbU]

2023/2/1哈尔滨工业大学电信院宿富林312023/2/1哈尔滨工业大学电信院宿富林32上式表明D维特征空间中，J2判据的值是矩阵的全部本征值之和。令上式中WT=Ud=[u1，u2,….,ud]则则：如果矩阵的本征值按大小顺序列为那么由对应于d个最大的本征值的本征向量所组成的矩阵W(D×d)，就能使所得到的d维特征满足J2判据最大的要求。此结论对J4判据也适用2023/2/1哈尔滨工业大学电信院宿富林33例：给定先验概率相等的两类，其均值向量分别为：协方差矩阵是：

求用J2判据的最优特征提取。

2023/2/1哈尔滨工业大学电信院宿富林34解：应先求，再求此矩的特征矩阵。混合均值类间离散度矩阵：类内离散度矩阵2023/2/1哈尔滨工业大学电信院宿富林35求

的本征值矩阵。由于这是一个两类别问题，总均值向量μ值是两个均值向量μ1和μ2的线性求和，则

中只有一个是独立的，因此

的秩是一，换句话说它只有一个非零本征值，W是D×1矩阵，是一个向量W，求该向量需解

利用W向量对原始的两类两维样本进行线性变换得到新的一维分布，特征空间从二维降到一维，并满足J2判据。该特征空间实质上就是对应于Fisher准则求得的线性分类器的法向量。如果讨论的是多类别C问题，则优化后的维数至多为类别数减一(C-1)。2023/2/1哈尔滨工业大学电信院宿富林362、J5判据下的特征提取由于和是对称矩阵，因此，存在矩阵U使得：则：

2023/2/1哈尔滨工业大学电信院宿富林372023/2/1哈尔滨工业大学电信院宿富林38即：是的本征值矩阵或是对角阵的证明及计算方法：2023/2/1哈尔滨工业大学电信院宿富林39J5的另一种形式（与J2比较）又设的本征值矩阵是则：2023/2/1哈尔滨工业大学电信院宿富林404.3.2按概率距离判据提取特征

设原始特征为Y，而经变换后的特征为X，两者之间有映射关系

X=WTY

则原空间中一矩阵A经映射后为：A*=WTAW映射后概率距离判据：

JC(X)=JC(WTY)=JC(W)JD(X)=JD(WTY)=JD(W)2023/2/1哈尔滨工业大学电信院宿富林412023/2/1哈尔滨工业大学电信院宿富林41一、正态分布下基于Jc的特征提取当两类都是正态分布时：2023/2/1哈尔滨工业大学电信院宿富林422023/2/1哈尔滨工业大学电信院宿富林432023/2/1哈尔滨工业大学电信院宿富林44由于Jc在任何非奇异变换下具有不变性，因此，WU=VU-1U=V也是最优变换阵，是Σ-1M的本征向量。而M的秩是1，故只有一个非零本征值，此时：2023/2/1哈尔滨工业大学电信院宿富林45可证，只有一个非零本征值，此时，W是一维的：是的本征值矩阵W是其本征向量2023/2/1哈尔滨工业大学电信院宿富林462023/2/1哈尔滨工业大学电信院宿富林472023/2/1哈尔滨工业大学电信院宿富林48根据Jc对非奇异变换的不变性，W即是Σ2-1Σ1的本征向量。此时：2023/2/1哈尔滨工业大学电信院宿富林49为使Jc最大，应选择满足如下关系的d个本征值对应的本征向量组成的矩阵。2023/2/1哈尔滨工业大学电信院宿富林502023/2/1哈尔滨工业大学电信院宿富林50步骤不同s，结果不同。1、s=0.5，得：Vi,i=1,2,…,d。2、根据Vi,i=1,2,…,d,求最优S(使Jc最大)3、求最佳Vi,i=1,2,…,d4、用新的S重复1，2、3直至获得一组稳定Vi二、用散度准则JD的特征提取2023/2/1哈尔滨工业大学电信院宿富林51只有两类时：2023/2/1哈尔滨工业大学电信院宿富林52最佳W是对应下列次序的本征值对应的本征向量例：有两类样本：

W1:x11=(0,0,0)T,X12=(1,0,0)T,X13=(1,0,1)T,X14=(1,1,0)T

W2:x21=(0,0,1)T,X22=(0,1,0)T,X23=(0,1,1)T,X24=(11,1)T

试利用散度JD降低维数。2023/2/1哈尔滨工业大学电信院宿富林53特征提取结果：Y=WTXW1:y11=0,y12=-1,y13=0,y14=0W2:y21=1,y22=1,y23=2,y24=12023/2/1哈尔滨工业大学电信院宿富林54-1012*00*2023/2/1哈尔滨工业大学电信院宿富林55§4.4特征选择

特征选择在概念上十分简单，即对原有特征进行删选优化。通常，人们认为：只要逐个分析每个特征，判断它对分类的价值，然后根据其优值删去或保留，这是一个为人们常采用方法，但是这种方法并不能保证特征空间的最优组合优化，因此本节讨论了一些原理上更好的方法。2023/2/1哈尔滨工业大学电信院宿富林56两个问题一：选择特征的标准：也就是选择前面讨论过的可分离性判据，以这些判据为准则，使所选择的d维子空间具有最大的可分离性。二：是要找出较好的特征选择方法，以在允许的时间内选择出一组最优的特征。所谓最优的特征组，就是要找到合适的特征的组合。如果从逐个特征配组进行性能比较的话，即穷举的算法，特征配组的数量可能极大，组合配置的数目按下式计算

2023/2/1哈尔滨工业大学电信院宿富林57如果D＝100，d＝10，则q的数量级就是1013，即使D＝20，d＝10，则q也可达184756种。如果将所有可能的特征配组列举出来，按某选定的可分离性判据进行计算，从中择优，其计算量之大是可想而知的。任何非穷举的算法都不能确保所得结果是最优的，因此要得最优解，就必需采用穷举法，只是在搜索技术上采用一些技巧，使计算量有可能降低。2023/2/1哈尔滨工业大学电信院宿富林58“自上而下”与“自下而上”“自上而下”是指，从D维特征开始，逐步将其中某些特征删除，直到剩下所要求的d维特征为止。而“自下而上”则是从零维特征空间开始，逐个地从D维持征中选择特征，直至达到预定的维数指标为止。在选择的过程中，“自上而下”算法做到筛选剩下的特征组在每一步上都是最优的，而“自下而上”则在每一步都生成最优的特征空间。

2023/2/1哈尔滨工业大学电信院宿富林59

4.4.1最优搜索算法

“分支定界”算法：至今能得到最优解的唯一快速算法属于“自上而下”算法，但是具有回溯功能，可使所有可能的特征组合都被考虑到。其核心问题是通过合理组合搜索过程，可以避免一些计算而仍能得到最优的结果。关键是利用了判据的单调性。如果特征存在包含关系：æi是æj的子集

则有J(æi)≤J(æj)称该判据具有单调性分支定界算法（略）2023/2/1哈尔滨工业大学电信院宿富林604.4.2次优搜索法

上述分支定界算法虽然比盲目穷举法节省计算量，但计算量仍可能很大而无法实现，因此人们还是常用次优搜索法。4.4.2.1单独最优特征组合

这是一种最简单的方法，即将各特征按单独使用计算其判据值，然后取其前d个判据值最大的特征作为最优特征组合。这种做法的问题在于即使各特征是独立统计的，也不一定得到最优结果。

2023/2/1哈尔滨工业大学电信院宿富林61但如果可分性判据可写成如下形式

或

则用这种方法可以选出一组最优的特征来。例如当两类都是正态分布，各特征统计独立时，用Mahalanobis距离作为可分性判据，上述条件可以满足。

2023/2/1哈尔滨工业大学电信院宿富林62

4.4.2.2顺序前进法

(SequentialForwardSelection----SFS)

这是最简单的自下而上搜索方法。首先计算每个特征单独进行分类的判据值，并选择其中判据值最大的特性，作为入选特征。然后每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的J值为最大，直到特征数增至d个为止。

2023/2/1哈尔滨工业大学电信院宿富林63广义顺序前进法

(GeneralizedSequentialForwardSelection----GSFS)顺序前进法与前一小节的单独特征最优化组合相比，一般说来，由于考虑了特征之间的相关性，在选择特征时计算与比较了组合特征的判据值，要比前者好些。其主要缺点是，一旦某一特征被选入，即使由于后加入的特征使它变为多余，也无法再把它剔除。推广至每次入选

r个特征，而不是一个，称为广义顺序前进法(GSFS)。与SFS相比，该法在每次入选r个特征时，考虑了他们之间的相关性。缺点是计算量大大增加.CD-kr。2023/2/1哈尔滨工业大学电信院宿富林644.4.2.3顺序后退法

(SequentialBackwardSelection----SBS)

这是一种自上而下的方法。做法也很简单，从现有的特征组中每次减去一个不同的特征并计算其判据，找出这些判据值中之最大值，如此重复下去直到特征数达到予定数值d为止。与SFS相比，此法计算判据值是在高维特征空间进行的，因此计算量比较大。此法也可推广至每次剔除r个，称为广义顺序后退法(GeneralizedSequentialBackwardSelection----GSBS)。

2023/2/1哈尔滨工业大学电信院宿富林65

4.4.2.4增l减r法(l-r法)

前面两种方法都有一个缺点，即一旦特征入选(或剔除)，过程不可逆转。为了克服这种缺点，可采用将这两种方法结合起来的方法，即增l减r法。其原理是对特征组在增加l个特征后，转入一个局部回溯过程，又用顺序后退法，剔除掉r个特征。这种方法既可能是“自上而下”方法，也可能是“自下而上”的，这取决于l与r的数据大小。当l>r时，入选特征数逐渐增加，属“自下而上”型，反之属“自上而下”型。

l-r法1）用SFS法在未入选特征中逐个入选l个特征2）用SBS法在已入选特征中逐个剔除r个特征。3）若特征数是d，则终止算法。否则，转入（1）L>r时，是自下而上的算法，先执行第1步，起始时，入选特征是空集ΦL<r时，是自上而下的算法，先执行第2步，起始时，入选特征是原有特征集X={x1,x2,….,XD}2023/2/1哈尔滨工业大学电信院宿富林662023/2/1哈尔滨工业大学电信院宿富林67（ZL,Zr）法此法也可推广至用GSFS及GSBS代替SFS及SBS，并可在实现增加l特征时采用分几步实现。(ZL,Zr)法：增L个特征用ZL步，每步可入选li(i=1,2,…,ZL)个特征。ZL=（l1,l2,l3,……,lZL）；减r则用Zr步，每步可剔除ri(i=1,2,…,Zr)个特征。Zr=（r1,r2,r3,……,rZr）这种做法是为了既考虑入选(或剔除)特征之间的相关性，又不至因此引起计算量过大。合理地设置ZL与Zr，可以同时对两者，即计算复杂性及特征选择的合理性兼顾考虑。2023/2/1哈尔滨工业大学电信院宿富林68前面的各种方法可看作是（ZL,Zr）法的特例(ZL,Zr)法等效算法ZL=（1）Zr=（0）SFSZL=（0）Zr=（1）SBSZL=（d）Zr=（0）穷举法ZL=（L）Zr=（0）GSFSZL=（0）Zr=（r）GSBSZL=(1,1,1,…,1)Zr=(1,1,….,1)（l，r）2023/2/1哈尔滨工业大学电信院宿富林694.5基于Karhunen-Loeve变换

（K-L变换）的特征提取

K-L变换又称主分量分析，是一种正交变换，常用来作为数据压缩。这里我们用它作降维

2023/2/1哈尔滨工业大学电信院宿富林704.5.1傅立叶级数展开周期平稳随机过程x(t)的Fourier展开则：周期平稳过程的Fourier系数互不相关2023/2/1哈尔滨工业大学电信院宿富林71(X(t)周期------R(t)周期,周期也为T）2023/2/1哈尔滨工业大学电信院宿富林724.5.2K-L展开将一个非周期随机过程x(t)在区间[a,b]展开为其中：2023/2/1哈尔滨工业大学电信院宿富林73本征值本征函数则：两边同乘并积分，则：2023/2/1哈尔滨工业大学电信院宿富林74离散情况用完备正交向量(基)uj(j=1,2,…)展开若用有限项估计：则展开x’是x的一个近似均方误差为：2023/2/1哈尔滨工业大学电信院宿富林75本征分解2023/2/1哈尔滨工业大学电信院宿富林76误差因此，可对X的自相关做本征分解，若取前d个最大本征值对应的本征向量来展开X时，截断的均方误差最小(实际展开时，因为X的维数是D,只能求得D个本征值和本征向量)。这d个本征向量所组成的正交坐标系称为X在D维空间的d维K-L变换系。X在K-L坐标系uj上的展开系数称作X的K-L变换。2023/2/1哈尔滨工业大学电信院宿富林774.5.3K-L展开式的性质(1)K-L变换的展开系数是互相无关的。2023/2/1哈尔滨工业大学电信院宿富林78(2)K-L变换后的协方差阵为对角阵令K-L变换后的D维坐标系统中样本向量为

X’=(c1,c2,…,cD)T则：或：这表明经过K-L变换后，原向量各分量之间存在的相关性已被消除。2023/2/1哈尔滨工业大学电信院宿富林794.5.4K-L变换的一些典型应用

1．降维与压缩

例如：一幅人脸图象，大小为：M×N。

K-L变换后只用到30个基，那么维数就降至30。可见降维的效果是极其明显的。另一方面降维与数据压缩又是紧密联系在一起的。譬如原训练样本集的数量为V，现采用30个基，每个基实质上是一幅图象，再加上每幅图象的描述参数，数据量是大大降低。基图像Ui，i=1，…,d是通用的

=(c1,c2,……)T

2023/2/1哈尔滨工业大学电信院宿富林802．构造参数模型使用K-L变换不仅仅起到降维与压缩数据的作用，更重要的是每个描述量都有明确的意义，因而改变某一个参数就可让图象按所需要的方向变化。在没有使用K-L变换的原数据集中对图象的描述量是每个象素的灰度值，而弧立地改变某个象素的灰度值是没有意义的。

而在使用K-L变换后，每个描述量都有其各自的作用。因此通过改变这些参数的值就可实现对模型的有效描述，这在图象生成中是很有用的。因此利用K-L变换构造出可控制的，连续可调的参数模型在人脸识别与人脸图象重构采方面的应用是十分有效的。

2023/2/1哈尔滨工业大学电信院宿富林813．人脸识别利用K-L变换进行人脸图象识别是一个著名的方法。首先搜集要识别的人的人脸图象，建立人脸图象库。然后利用K-L变换确定相应的人脸基图象(特征脸)，再反过来用这些基图象对人脸图象库中的所有人脸图象进行K-L变换，从而得到每幅图象的参数向量并将每幅图的参数向量存起来。在识别时，先对一张所输入的脸图象进行必要的规范化，再进行K-L变换分析，得到其参数向量。将这个参数向量与库中每幅图的参数向量进行比较，找到最相似的参数向量，也就等于找到最相似的人脸，从而认为所输入的人脸图象就是库内该人的一张人脸,完成了识别过程。

2023/2/1哈尔滨工业大学电信院宿富林824．人脸图象合成用K-L变换构造参数模型的另一种典型用途是人脸图象合成。有目的的控制各个分量的比例，也就是通过调整参数向量。可以将一幅不带表情图象改变成带各种表情的图象，称为人脸表情图象合成。2023/2/1哈尔滨工业大学电信院宿富林832023/2/1哈尔滨工业大学电信院宿富林844.5.5使用K-L变换进行特征提取上面讨论K-L变换时得出K-L坐标系是由E[XXT]的本征值对应的本征向量产生，因而被称为K-L坐标系的产生矩阵。实际上使用不同的向量作为产生矩阵，会得到不同的K-L坐标系，从而满足不同的分类要求。一般，没有类别标签的样本集的均值向量u常常没有意义，因此，可用样本数据的协方差矩阵

E[(X-u)(X-u)T]作为产生矩阵。

2023/2/1哈尔滨工业大学电信院宿富林85对分类问题，如何形成产生矩阵?当样本集中各样本的类别标签已知时，可以得到不同的Σ，Σ有多个（不同类可有不同的Σ）,如何形成产生矩阵?1）如各类别先验概率为Pi

，均值为i，协方差矩阵为Σi=E[(X-ui)(X-ui)T]

则可以用类内离散矩阵SW=ΣPi

Σi作为产生矩阵，其效果相当于只按类内离散程度进行特征选取。2）如果只以某一类样本集的协方差矩阵Σi作为产生矩阵，则效果是对该类样本集有信息压缩的最优性。2023/2/1哈尔滨工业大学电信院宿富林861利用类均值向量提取特征类条件均值ui包含大量的分类信息。为了降低维数，且尽可能地保持原有特征的分类信息，应选择一种变换，是变换后的类条件均值向量的给分量比其他的变换保持更多的分类信息。基于欧氏距离特征提取：判据是从使类内尽可能密集，类间尽可能分开的思想出发的。但是，各类均值向量各分量的分类性能，不仅与取决于各均值向量各分量之间的距离，而且，还和其方差以及各分量的相关程度有关。如何在K-L变换方法中体现对这两者的兼顾?具体算法1）为了估计各分量（特征）对于分类的单独作用，先按类内离散度矩阵Sw作为产生矩阵产生相应的K-L坐标系统，从而把包含在原向量中各分量的相关性消除，并得到在新坐标系中各分量离散的程度。2）然后对均值向量在这些新坐标中分离的程度作出判断，决定在各坐标轴分量均值向量所能提供的相对可分性信息。据此选取K-L变换的基向量作为特征提取变换矩阵。2023/2/1哈尔滨工业大学电信院宿富林872023/2/1哈尔滨工业大学电信院宿富林88在uj轴上，原第i类特征向量Xik投影为：Xikj=ujTXik其类内离散度：其类间离散度2023/2/1哈尔滨工业大学电信院宿富林892023/2/1哈尔滨工业大学电信院宿富林90可设判据J(Xi)为类间离散度与类内离散度在uj坐标的分量之比:

其中:J(Xi)越大，表明在新坐标系中该坐标抽包含较多可分性信息。2023/2/1哈尔滨工业大学电信院宿富林913）为了降低特征空间的维数，可以将各分量按大小重新排列，使

J(X1)≥J(X2)≥J(X3)….≥J(XD)

取与前面d个最大的J(Xi)≥值相对应的本征向量uj，j=1,...,d;作为特征空间的基向量。W=[u1,u2,…,ud]

2023/2/1哈尔滨工业大学电信院宿富林92

例:设有两类问题，其先验概率相等，即:P(w1)=P(w2)=0.5，设样本的类均值向量分别为：

类协方差矩阵分别是：把维数从2压缩为12023/2/1哈尔滨工业大学电信院宿富林93解1）将SW作K-L变换的产生矩阵，求其本征矩阵得K-L变换的变换矩阵。可求得本征值矩阵和本征向量分别是：2023/2/1哈尔滨工业大学电信院宿富林94又2）求得：3）2023/2/1哈尔滨工业大学电信院宿富林952、包含在类平均向量中判别信息的最优压缩上面方法（利用类均值向量提取特征）为了兼顾类内离散度与类间离散度，包含在类均值向量内的分类信息并没有全部利用。即：类平均向量的判别信息在K-L坐标系的各个分量中都有反映，并没有得到最优压缩。

如图，如仅从类均值向量所包含的分类判别信息全部被利用出发，应选择包含两均值向量连线方向在内的坐标系。但是简单地从类均值向量来确定特征子空间，虽然实现很容易，但一般不能满足各分量间互不相关的要求。2023/2/1哈尔滨工业大学电信院宿富林96例外情况：如果类内离散度矩阵Sw是一个单位矩阵，即它在特征空间中以超球体分布，从类均值向量来确定特征子空间就可做到既保持各分量的不相关性，同时又能充分利用包含在类均值向量内的差别信息。从这种特殊情况得到启发，一种充分利用类均值向量所包含的判别信息的方法因此而产生。具体说来这种方法分成两步：1）白化处理2）特征提取2023/2/1哈尔滨工业大学电信院宿富林97第一步：白化处理1、先用原坐标系中Sw作为产生矩阵，实行K-L变换，将原有数据的相关性消除掉。

UTSw=ΛU，或UTSwU=Λ在K-L坐标系U上，新的特征向量为：Y1=UTX

Y1的类内离散度矩阵S’w=Λ是一个对角矩阵。2、进一步实行变换：Y2=Λ-1/2Y1，则Y2的类内离散度矩阵变为：Λ-1/2

UTSwUΛ-1/2=Λ-1/2ΛΛ-1/2=I

即：(UΛ-1/2)

Sw(UΛ-1/2)=I3、令:B=UΛ-1/2（白化矩阵），则：BTSwB=I（白化）

此时，

Y2=Λ-1/2Y1=Λ-1/2UTX=(UΛ-1/2)TX=BTX经过B变换后（Y2）的类间离散度矩阵S’b应有：S’b=BTSbB2023/2/1哈尔滨工业大学电信院宿富林98第二步:特征提取1）采用上节方法求最佳的变换。因S’W

=I则，Λ=I而且，U可以是任何正交矩阵。即UTIU=UTU=I则判据：由于U可以上任何正交矩阵，因此，可以以S’b作为产生矩阵，作第二次K-L变换，得到正交矩阵VTSb’=Λ’V则判据因此，按判据最大选择uj，就是按Sb’正交分解的本征值λ’j最大选择。由于S’b的秩最多是c-1，所以最多只有c-1个非零本征值。选择最大的d（≤c-1）个非零本征值

，则该d个非零本征值就可表示类均值向量所包含的全部信息。设这d个本征向量系统用V’表示，即

V’=[v1,v2,….,vd]（d≤c-1）则变换为:Y=V’TY22）将第一步得到的结果代入，整个变换为：Y=VTY2=VTBTX=(BV)TX=WTX因此变换矩阵为：W=BV=UΛ-1/2V2023/2/1哈尔滨工业大学电信院宿富林99具体算法1）对原特征向量计算类内离散度矩阵Sw和类间离散度矩阵Sb2）用Sw作为产生矩阵做KL变换求坐标系U及Λ：UTSwU=Λ3）计算变换矩阵:B=UΛ-1/24）计算经过B变换后的类间离散度矩阵S’b：S’b=BTSbB5）以S’b作为产生矩阵，作第二次K-L变换VTSb’=Λ’V6）选择Λ’中最大d个本征值对应的d（≤c-1）个本征向量

V’=[v1,v2,….,vd]7）计算最终的变换矩阵：W=BV’=UΛ-1/2V’W即是降维的变换矩阵。可将D维特征向量降维d维（前3步是白化过程）2023/2/1哈尔滨工业大学电信院宿富林1002023/2/1哈尔滨工业大学电信院宿富林1012023/2/1哈尔滨工业大学电信院宿富林101

例:数据同上例，求保持类均值向量中全部分类信息条件下压缩为一维特征空间的坐标轴。

设有两类问题，其先验概率相等，即:P(w1)=P(w2)=0.5，设样本的类均值向量分别为：

类协方差矩阵分别是：2023/2/1哈尔滨工业大学电信院宿富林102解：2023/2/1哈尔滨工业大学电信院宿富林103下图给出了两次变换步骤

以及变换对数据产生的作用由图中看出，样本原为椭圆形分布，经白化处理后转化为圆形分布，此时S’w为单位矩阵。均值向量也随之变化，最后得到的均值向量作为降维后的一维坐标。这种方法主要用在类别数C比原特征向量的维数D小得多的情况，由于Sb的秩最多为C-1，因此可使特征维数降至C维以下。2023/2/1哈尔滨工业大学电信院宿富林104第五章非监督学习法2023/2/1哈尔滨工业大学电信院宿富林105本章重点1.什么叫非监督学习方法，什么叫有监督学习方法？

2.非监督学习方法主要的用途

3.非监督学习方法的两种基本处理方法：按分布密集程度划分，与按相似度聚类划分

4.按分布密度程度划分的基本方法

5.动态聚类方法与分级聚类方法的概念

6.典型的动态聚类方法C-均值算法与ISODATA算法

7.使用非欧氏距离计算相似度的动态聚类方法

8.分级聚类方法2023/2/1哈尔滨工业大学电信院宿富林106本章难点

1.非监督学习方法与监督学习方法概念的区别

2.按分布密集程度划分的基本方法

3.动态聚类方法-迭代修正的概念

4.分级聚类方法2023/2/1哈尔滨工业大学电信院宿富林107本章学习目标

1.掌握非监督学习方法的概念、用途

2.了解非监督学习方法对数据划分有两种基本方法

3.掌握以c-均值算法，ISODATA算法为代表的动态聚类方法

2023/2/1哈尔滨工业大学电信院宿富林108§5.1引言以前讨论的分类器设计方法都是在样本集中的类别标签已知的条件下进行的，这些样本称为训练样本。在样本类别标签已知的情况下，可以统计出各类训练样本不同的描述量，如其概率分布，或在特征空间分布的区域等，利用这些参数进行分类器设计，称为有监督的学习方法。然而在实际应用中，不少情况下无法预先知道样本的标签，也就是说没有训练样本，因而只能从没有样本标签的样本集进行分类器设计，这就是非监督学习方法。2023/2/1哈尔滨工业大学电信院宿富林109一幅道路图像按路面与非路面分类其中左图是在图像中路面区与非路面中各找一个窗口，将其中每个象素分别作为这两类的训练样本集，用这两个样本集在特征空间的分布参数进行设计（有监督的学习）。右图，无法预先选择不同类别的样本集，而是将整幅图的像素都作为待分类样本集，通过它们在特征空间中表现出来的聚类现象，把不同类别划分开。（非监督学习）2023/2/1哈尔滨工业大学电信院宿富林110

有监督学习中，样本集分布呈现交迭情况，而无监督学习方法由于没有类别样本指导，无法确定它们的交迭情况，只能按分布的聚类情况进行划分。在类似于该例的实际应用问题中，预先选定不同类别的样本往往不可能，如时间不允许，或无法用人工干予等因素。

另外在某些有监督学习方法中（例如，局部训练法），也往往需要利用聚类方法将样本按其分布划分成若干子类等。聚类方法就是无监督学习方法的一个内容，它是经常应用的一门技术。非监督学习方法要解决的问题观察事物与分析事物，从中寻找其规律性，这就是非监督学习方法要解决的问题。2023/2/1哈尔滨工业大学电信院宿富林1112023/2/1哈尔滨工业大学电信院宿富林112非监督学习与有监督学习的不同点1．数据集不同：

有监督学习方法必须要有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；

非监督学习没有训练集，只有一组数据，在该组数据集内寻找规规律2．目的不同有监督学习方法的目的就是识别事物。识别的结果表现在给待识别数据加上了标号，因此训练样本集必须由带标号的样本组成。非监督学习方法的目的是寻找数据集中的规律性。只有要分析的数据集本身，预先没有什么标号。如果发现数据集呈现某种聚集性，则可按自然的聚集性分类，但不以与某种预先的分类标号对上号为目的。3.算法不同2023/2/1哈尔滨工业大学电信院宿富林113无监督学习算法分类两大类：基于概率密度函数估计的直接方法：指设法找到各类别在特征空间的分布参数再进行分类。如：单峰子类的分离方法（投影法等），基于样本间相似性度量的间接聚类方法：其原理是设法定出不同类别的核心或初始类核，然后依据样本与这些核心之间的相似性度量将样本聚集成不同类别。迭代的动态聚类算法（K均值聚类，ISODATA算法），非迭代的分级聚类算法

2023/2/1哈尔滨工业大学电信院宿富林114§5.2单峰子类的分离方法

样本概率密度分布在特征空间的分布是多峰的。每个单峰区域则被看作不同的决策域。落在同一单峰区域的待分类样本就被划分成同一类，称为单峰子类。5.2.1投影法高维空间寻找概率密度的“峰”是困难的。一维空间寻找概率密度的“峰”较容易。因此，可通过将高维空间样本投影到不同的一维空间ui上，xi=uiTY；然后，在此一维空间上估计边缘概率密度p(xi)，并在此概率密度上寻找各个峰，并确定每个峰的范围（即每个聚类），各个聚类的分解面与该坐标轴ui垂直，交点则是两个峰值之间的最小点。称为投影法。投影法的主要问题：一：如何设计合适的坐标系统（即投影方向）二、如何设计直方图（计算边缘概率密度）2023/2/1哈尔滨工业大学电信院宿富林115一、如何设计直方图1）将数据xi(k)=uiTY(k)按大小排列2）确定直方图上的单位间隔长度L3）根据L将数据xi(k)分成不同区间，统计；落在每个区间内的样本数。K

则pi(k)=K/NN:总的样本数2023/2/1哈尔滨工业大学电信院宿富林1162023/2/1哈尔滨工业大学电信院宿富林117二：如何设计合适的坐标系统目前还没有合适的准则用于确定坐标系。一种启发式的办法是使待分类的样本在某个坐标轴方向具有最大的分散性，可以采用K-L变换方法。具体说来是用混合样本协方差矩阵作为K-L变换的产生矩阵，找到其本征值，并按大小排序。对此混合样本来说，对应最大本征值的本征向量，离散程度最大，预期能发现明显的峰值。但是，在这些方向的投影，并不能保证分出各个聚类。2023/2/1哈尔滨工业大学电信院宿富林118可以分出各个聚类不能分出各个聚类2023/2/1哈尔滨工业大学电信院宿富林119投影法的具体算法步骤1：计算样本协方差矩阵具有最大本征值的本征向量Uj，把数据投影到Uj轴上。步骤2：用直方图方法求数据的边缘概率密度函数。步骤3：在直方图的峰值间求最小值，在这些最小点作垂直于Uj的超平面把数据划分为若干个聚类。步骤4：如果在这个轴上没有这样的最小值，则用下一个最大本征值对应的本征向量重复以上过程。步骤5：对每个得到的子集(聚类)重复上述过程，直到每个集不能再分(为单峰)为止。2023/2/1哈尔滨工业大学电信院宿富林1205.2.2单峰子集分离的其它方法基于对称集性质的单峰子集分离法单峰子集分离的迭代算法（略）2023/2/1哈尔滨工业大学电信院宿富林1215.3类别分离的间接方法

----聚类方法聚类方法：不通过对概率密度函数作出估计而直接按样本间的相似性，或彼此间在特征空间中的距离远近进行分类。

如何聚类取决于聚类准则，以使某种聚类准则达到极值为最佳。两类对数据集进行聚类的方法：迭代的动态聚类算法非迭代的分级聚类算法2023/2/1哈尔滨工业大学电信院宿富林1225.3.1动态聚类方法动态聚类方法的任务是将数据集划分成一定数量的子集，子集数目在理想情况现能体现数据集比较合理的划分。问题:

1．怎样才能知道该数据集应该划分的子集数目

2．如果划分数目已定，则又如何找到最佳划分

由于优化过程是从不甚合理的划分到“最佳”划分，是一个动态的过程，故这种方法称为动态聚类方法。2023/2/1哈尔滨工业大学电信院宿富林1235.3.1.1动态聚类方法3个要点1.选定某种距离度量作为样本间的相似性度量；

2.确定样本合理的初始分类，包括代表点的选择，初始分类的方法选择等。3.确定某种评价聚类结果质量的准则函数，用以调整初始分类直至达到该准则函数的极值。

2023/2/1哈尔滨工业大学电信院宿富林1245.3.1.2C-均值算法

也叫K-均值算法1.准则函数—误差平方和准则这个准则函数是以计算各类样本到其所属类均值点误差平方和为准则。若各类均值表示成

误差平方和准则可表示成

最佳的聚类是使Jc为最小的分类。这种类型的聚类通常称为最小方差划分。2023/2/1哈尔滨工业大学电信院宿富林1252.样本集初始划分初始划分的一般作法是（1）先选择一些代表点作为聚类的核心（2）把其余的样本按某种方法分到各类中去

2023/2/1哈尔滨工业大学电信院宿富林126（1）代表点的几种选择方法(a)凭经验选择代表点。根据问题的性质，用经验的办法确定类别数，从数据中找出从直观上看来是比较合适的代表点。(b)将全部数据随机地分为C类计算各类重心，将这些重心作为每类的代表点。（c）用前C个样本作为代表点

2023/2/1哈尔滨工业大学电信院宿富林127(d)“密度”法选择代表点。“密度”：对每个样本确定大小相等的邻域（如同样半径的超球体），统计落在其邻域的样本数，称为该点“密度”。确定一个距离d选“密度”为最大的样本点作为第一个代表点；然后，找次高“密度”的样本点作为第二个代表点；第2个代表点离第1个代表点的距离需大于d。依次选择其它代表点。其离选定的代表点的距离应大于d。使用这种方法的目的是避免代表点过分集中在一起。

2023/2/1哈尔滨工业大学电信院宿富林128(e)从c-1个聚类划分问题的解中产生C聚类划分问题的代表点首先，将所有样本集看作一个聚类，计算其总均值，然后找与该均值相距最远的点，由该点及原均值点构成2聚类的代表点。其次，依同样方法，对已有(c-1)个聚类代表点(由(c-1)个类均值点组成)找一样本点，使该样本点距所有这些均值点的最小距离为最大，这样就得到了第c个代表点。代表点的选择会影响迭代结果。因为迭代得到的结果往往是局部最优而非全局最优。2023/2/1哈尔滨工业大学电信院宿富林129(2)初始分类方法(a)对选定的代表点按距离最近的原则将样本划属各代表点代表的类别。(b)在选择样本的点集后，将样本按顺序划归距离最近的代表点所属类，并立即修改代表点参数，用样本归入后的重心代替原代表点。因此代表点在初始划分过程中作了修改。

2023/2/1哈尔滨工业大学电信院宿富林130(c)一种既选择代表点又同时确定初始分类的方法规定一阈值d，选w1={y1}计算样本y2与y1的距离D(y2,y1)，如其小于d，则y2归入w1；否则建立新的类别w2={y2}。当轮到样本yj时，已有了K类即，而每类第一个入类样本分别为y1,y2,…,yk（作为每类的代表点），则计算D(yi,yj),i=1,2,…,k；若有D(yi,yj)>d（对所有的i，i＝1,…，k），则建立新类。否则将yj归入与y1,y2,…,yk距离最近的类别中。重复上一步，直至所有样本分类

2023/2/1哈尔滨工业大学电信院宿富林131(d)标准化特征求和量化方法：i)先将数据标准化ii)若yij

表示标准化后第i个样本的第j个特征量，令：iii)求出SUM(i)的最大值与最小值

MA=max{SUM(i)},MI=min{SUM(i)}iv）如果欲将样本划分为c类，则对每个i计算

v)如所得结果非整数，则找到其最近整数K，将第i个样本归入第K类

2023/2/1哈尔滨工业大学电信院宿富林1323.迭代计算c-均值算法的迭代计算过程在原理上与梯度下降法是一样的，即以使准则函数值下降为准则。但是由于c-均值算法的准则函数值由数据划分的调整所决定，因此只能通过逐个数据从某个子集转移到另一子集计算准则函数值是否降低为准则。

2023/2/1哈尔滨工业大学电信院宿富林133对划分的修改规则如果原属Гk

中的一个样本y从Гk

移入Гj

时，它会对误差平方和产生影响,Гk类在抽出样本y后其相应均值为而样本y新加盟的Гj

集合均值

2023/2/1哈尔滨工业大学电信院宿富林134由于y的移动只影响到k与j这两类的参数改动，因此，计算Jc值的变动只要计算相应两类误差平方和的变动即可，此时

总误差变化：如果则即将样本y从Гk

移入至Гj

就会使误差平方总和Jc减小，它表明样本变动是合乎准则要求的2023/2/1哈尔滨工业大学电信院宿富林135算法(1)选择某种方法把样本分成C个聚类的初始划分，计算每个聚类的均值m1,…,mc和Jc(2)选择一个备选样本y，设其在wi中(3)若Ni=1，则转(2)（样本只有1个，不移出），否则继续下一步。(4)计算

2023/2/1哈尔滨工业大学电信院宿富林136(5)对于所有的j，若ek≤ej（表明ek<ei）则将y从wi移到wk中（否则，ei<ei,不用移）(6)重新计算mi和mk，并修改Jc。(7)若连续迭代N次(即所有样本都运算过)Jc不变，则停止，否则转到2。

2023/2/1哈尔滨工业大学电信院宿富林137确定类别数的实验方法上述C—均值算法都是在类别c已知条件下进行的。在类别数未知情况下，可以假设类别数是逐步增加的，准则函数随c的增加而单调地减小。可选择平缓时转折处的C值。2023/2/1哈尔滨工业大学电信院宿富林1385.3.1.3ISODATA算法

C—均值算法比较简单，但它的自我调整能力也比较差。这主要表现在类别数不能改变，受代表点初始选择的影响也比较大。全称‘迭代自组织数据分析技术’（IterativeSelf-OrganizingData

AnalysisTechniqueAlgorithm）。ISODATA算法的功能与C—均值算法相比的改进。

1.不是每调整一个样本的类别就重新计算一次各类均值（逐个样本修正），而是每次把全部样本都调整完毕后再重新计算样本均值（成批样本修正）。2.考虑了类别的合并与分裂，因而有了自我调整类别数的能力。从而可以得到较为合理的类别数。2023/2/1哈尔滨工业大学电信院宿富林139合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。为此设有最小类内样本数限制N，以及类间中心距离参数L。若出现两类聚类中心距离小于L或样本数小于N的情况，可将此两类合并分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。

给出一个对类内分量方差的限制参数S，用以决定是否需要将某一类分裂成两类。2023/2/1哈尔滨工业大学电信院宿富林140ISODATA算法的步骤步骤1：确定控制参数及设置代表点由于算法有自我调整的能力，因而需要设置若干个控制用参数。需确定的控制参数为：

K：聚类期望数；

QN：一个聚类中的最少样本数；

θs：标准偏差控制参数，用于控制分裂；

θc

：类间距离控制参数，用于控制合并；

L：每次迭代允许合并的最大聚类对数；

I：允许迭代的次数。

设初始聚类数为c及聚类中心mi,i=1,2,…,C。

2023/2/1哈尔滨工业大学电信院宿富林141步骤2(分类)

对所有样本，按给定的c个聚类中心，以最小距离进行分类，即

若

步骤3(撤消类内样本数过小类别)

若有任何一个类，其样本数，则舍去该类，令c＝c-1，将该类中原样本分配至其它类；步骤4（重新计算均值向量）

2023/2/1哈尔滨工业大学电信院宿富林142步骤5(计算类内平均距离)

每类各样本离开均值的平均距离

步骤6(计算整个样本集偏离均值的平均距离)

j2023/2/1哈尔滨工业大学电信院宿富林143步骤7(入口选择)

如这是最后一次迭代(取决于I)，则转步骤11，并设置θc=0，防止合并发生。

如果c<K/2，则转向步骤8，执行分裂步骤；

如果c≥2K或是偶数次迭代，则转向步骤11，执行合并步骤步骤8(求各类内各分类标准偏差)

对每个聚类j，求其标准偏差

2023/2/1哈尔滨工业大学电信院宿富林144步骤9(求每类具有最大标准偏差的分量)

步骤10(分裂计算步骤)

若对任一个有，并且有

(a)且，或有(b)C<k/2则把wj分裂成两个聚类，其中心相应为M+

j与M-

j

，把原来的Mj取消，且令c＝c+1，由于M+

j与M-

j设置不当将会导致影响到其它类别，可按以下步骤计算：

2023/2/1哈尔滨工业大学电信院宿富林145(a)给定一k值，0＜k＜1；

(b)令

(c)其中k值应使wj中的样本到M+

j与M-

j的距离不同，但又应使wj中的样本仍然在分裂后的新样本类中。步骤11(计算类间聚类中心距离)

i类与j类的类间距离

2023/2/1哈尔滨工业大学电信院宿富林146步骤12(列出类间距离过近者)

比较Dij

与θc

并将小于θc

的Dij按上升次序排列

该队列最大个数是控制合并对数的参数L步骤13(执行合并)

从类间距离最小的两类开始执行合并过程，此时需将miL与miL合并，得

2023/2/1哈尔滨工业大学