638 非监督学习方法

第十章非监督学习方法10.1引言监督模式识别：（已知）样本集→训练（学习）→识别（分类）分类器设计非监督模式识别：（未知）样本集→非监督学习（聚类分析）→后处理举例说明现实中的非监督模式识别问题z通过寻找可能存在的分类来理解某一对象z将复杂多样的对象用有限典型来代表根据：某种假设（对聚类应具有的性质的认识）结果：聚类（clusters）属中间结果（数学结果），需经解释赋予物理含义（后处理）两大类方法基于样本间相似性度量间接聚类方法基于概率密度函数估计直接方法::10.2单峰子集（类）的分离方法基本假定：各类样本的分布是单峰的，根据总体分布中的单峰来划分子集10.2.1投影方法基本思路：把样本投影到某一一维坐标轴（按某种准则），在这一维上求样本的概率密度（边缘概率密度），根据这一概率密度函数的单峰划分子集。（如果这一维上只有一个峰，则寻找下一个投影方向。）投影方向：使方差最大的方向，即协方差阵本征值最大的本征向量方向。算法步骤：（1）计算样本协方差矩阵的最大本征值对应的本征向量ju，把样本投影到ju上。（---KL变换）（2）估计投影后样本xuvTjj=的概率密度函数)(jvp。（用直方图方法或其它方法）（3）求)(jvp中的极小点（波谷），在这些极小点上作垂直于ju的超平面作为分类超平面，得到子集划分。（4）如果)(jvp上没有这种极小点，则用下一个本征值对应的本征向量作为投影方向，重复（2）～（3）。（5）对划分出的第一个子集重复上述过程，直到不能再分（所有方向上都是单峰）。直方图法求概率密度函数：N个样本ijv，Ni,,1L=，按小到大排队，组成{}Njlv)(，其中)()(ilvlvjj+≤，0,∀il，Nil≤+将jv划分为若干间隔，统计每个间隔内样本的数目，用它（占样本总数的比例）作为对概率密度函数值的估计间隔长度ρ的确定：对某个k，求{})()(minlvklvjjl−+=ρ.kNl−≤≤1其中k应满足：∞=∞→kNlim0lim=∞→NkN∞=∞→NkNloglim通常可选Nak=&，a为一定的常数问题：如何选择投影方向？-----方差最大的准则有时并不一定最有利于聚类。10.2.2基于对称集性质的单峰子集分离法对称集：对集合{}y=Γ，设)(yp的峰点出现在0y，即)(sup)(0ypypyΓ∈=若Γ∈∀jiyy,，),(),(00yyyyiiδδ≤)()(jiypyp≥⇒则称Γ为对称集z对称集一定是单峰的z划分单峰子集→划分对称集算法：（1）初始化。按概率密度值从大到小把样本排序，形成序列{}jkypypyyySjkN∀≥=),()(|,,,21L置}{11y=Γ，当前已形成子集数1=i，已考虑样本数0=r。对已形成的子集，按候选样本中离本类第一样本（峰值点）的距离从近到远排序。（离该子集的距离）（2）对S中的第1+r个样本1+ry，考查它与已有各子集的关系，即考查它是否是剩余候选样本中离该子集距离最近的样本。可能有三种情况：(a)若对所有已有子集jΓ，ij,,1L=，1+ry都不是下一个离它最近的样本，则用1+ry开始一个子集1+iΓ，置1+=ii；(b)若对某个jΓ，1+ry是候选点中离它最近的样本，而对其它子集都不是候选最近样本，则令jryΓ∈+1；(c)若对一个以上的子集，1+ry都是候选点中离它们最近的样本，则选择其中与1+ry距离最近的子集jΓ，使jryΓ∈+1。（3）从候选样本中去掉1+ry，更新候选样本距离排序，置1+=rr，重复（2），直到Nr==。（4）这样找出的子集数可能多于单峰子集数，因此：根据)(yp的极大点是哪些子集jΓ的内点确定出单峰子集的核jy。（5）对于其余（非核）子集，根据其峰值点距各核中最近样本（或中心）的距离合并到最近的单峰子集（核）中。10.2.3单峰子集分离的迭代算法设数据集Y划分为c个子集iΓ，ci,,2,1L=每个子集中样本数为iN，总样本数为N。考查类条件概率密度的加权估计值：)|()|(iiiypNNyfΓΓ=定义指标[]dyypyfyfJjicjci)()|()|(21211ΓΓ−=∑∑∫==它反映了)|(iyfΓ和)|(jyfΓ之间的“距离”。目标：求使J最大的子集划分),(1)|(1iNjiiyykNypi∑==Γ，ijyΓ∈（Parzen窗法）考查某个样本ky，若它原属于jΓ，从jΓ移入iΓ，得新的jΓ~和iΓ~，则显然)|()~|(iiyfyfΓΓ≥)|()~|(jjyfyfΓΓ≥记iiifyfyf∆ΓΓ+=)|()~|(，则),(1kiiyykNff=−=∆∆把ky从jΓ移入iΓ引起的指标变化量：[][]{∫−−−=22))|()|(~|()~|(jijiyfyfyfyfJΓΓΓΓ∆[22,1))|()|(())~|()|((jkjkcjikkyfyfyfyfΓΓΓΓ−−−+∑≠=]}dyypyfyfyfyfikik)())|()|(())~|()|((22ΓΓΓΓ−−−+[][]dyypfyfyfcdyypfcijii)()|()|(2)(22∆ΓΓ∆−+=∫∫目标：通过把ky从jΓ移入iΓ，使J增大，故应选择使J∆尽可能大的iΓ移入，即选择)|(max)|(lklikyfyfΓΓ=以使[])|()|(jiyfyfΓΓ−最大，从而使J∆最大。若存在两个（或以上）子集的)|(ikyfΓ最大（相等），则可移入其中任一类。算法步骤：（1）初始划分Y（2）对每个样本ky，Nk,,1L=，逐一计算)|(ikyfΓ，并归入使)|(ikyfΓ最大的子集中。（3）重复（2），直到不再有样本发生转移。10.2.4参数化方法以上介绍方法均属非参数方法，在对数据分布没有先验知识的情况下采用。如果已知（或可假设）数据分布的概率密度函数的形式，则可采用参数化方法。回顾：3.4非监督参数估计非监督参数估计指样本类别未知，但各类条件概率密度函数的形式已知，根据所有样本估计各类密度函数中的参数。----混合概率模型3.4.1非监督参数估计的最大似然法3.4.2非监督参数估计示例：正态分布情况------局限：需要较强的先验假设，需要较多的样本10.3类别分离的间接方法回顾：直接方法：1.估计概率密度函数——困难2.寻找密度函数中的单峰间接方法：考查样本间的相似性，根据相似性把样本集划分为若干子集，使某种表示聚类质量的准则函数最优。不同的聚类方法实际上反映了对聚类（及数据）的不同理解：z混合模型：数据服从混合分布，聚类对应于各分布z单峰子集：聚类即概率分布中的单峰，即样本分布相对集中的区域z间接方法：相似的样本聚类，不同聚类的样本不相似相似性度量：以某种距离定义直观理解：同一类的样本的特征向量应是相互靠近的。——前提：特征选取合理，能反映所求的聚类关系。与基于密度函数的方法的关系：概念上相互关联，因密度估计也是在样本间距离的基础上的。具体关系取决于具体数据情况。10.3.1动态聚类方法多次迭代，逐步调整类别划分，最终使某准则达到最优。三个要点：①选某种距离作为样本相似性度量②定义某个准则函数，用于评价聚类质量。③初始分类方法及迭代算法（一）C均值算法（k均值，C-meansork-means）误差平方和聚类准则iciiycieJmyJi∑∑∑=∈==−=121Γ其中，iΓ是第i个聚类，ci,,1L=，其中样本数为iN，iΓ中均值为∑Γ∈=iyiiyNm1直观理解：eJ反映了用c个聚类中心代表c个样本子集所带来的总的误差平方和。eJ是样本集Y与类别集Ω的函数。C均值算法的目标：最小化eJ——最小方差划分另一种角度来看C均值方法：用c个码本来代表整个样本集，使这种表示带来的总体误差最小。----向量量化VectorQuantisation算法研究：设已有一个划分方案，考查kΓ中的样本y，若把y移入jΓ，此时kΓ变成kΓ~，jΓ变成jΓ~，有[]ymNmmkkkk−−+=11~[]jjjjmyNmm−++=11~21~kkkkkmyNNJJ−−=−21~jjjjjmyNNJJ−++=若2211kkkjjjmyNNmyNN−−−+则把y从kΓ移入jΓ会使eJ减小。C均值算法：（1）初始划分c个聚类，iΓ，ci,,1L=计算im，ci,,1L=和eJ（2）选样本y，设iyΓ∈（3）若1=iN，则转（2）；否则继续。（4）计算jρ：21jjjjmyNN−+=ρ，ij≠21iiiimyNN−+=ρ（5）选jρ中的最小者，即若jkρρ，j∀，则把y从iΓ移到kΓ中。（6）重新计算im，ci,,1L=和eJ（7）若连续N次迭代eJ不改变，则停止；否则转（2）。初始划分：一般可先代表点，再进行初始分类。代表点选择方法：1.经验选择2.随机分成c类，选各类重心作为代表点3.“密度”法。计算每个样本的一定球形邻域内的样本数作为“密度”，选“密度”最大的样本点作为第一个代表点，在离它一定距离之外选最大“密度”点作为第二个代表点，…，依次类推。4.用前c个样本点作为代表点。5.用1−c聚类求c个代表点：各类中心外加离它们最远的样本点，从1类开始。…初始分类方法：1.最近距离法。离哪个代表点近就归入哪一类。2.最近距离法归类，但每次都重新计算该类代表点。3.直接划分初始分类：每一个样本自成一类，第二个样本若离它小于某距离阈值则归入此类，否则建新类，……4.将特征归一化，用样本各特征之和作为初始分类依据。ijDjyiSUM∑==1)(，Ni,,1L=.DiRy∈)(maxiSUMMAi=，)(miniSUMMIi=[]1)()1(+−−−=MIiSUMMIMAck取整说明：z初始划分无一定之规，多为启发式方法。zC均值方法结果受初值影响，是局部最优解。关于类别数c，多假定已知，根据先验知识确定。一种实验确定方法：对L,3,2,1=c，取类，求)(cJe，如图找其中的拐点（图中3ˆ=c）（此方法并不总有效）Je(c)cC-均值算法（另一种算法）⒈条件及约定设待分类的模式特征向量集为，类的数目C是事先取定的。⒉算法思想该方法取定C个类别和选取C个初始聚类中心，按最小距离原则将各模式分配到C类中的某一类，之后不断地计算类心和调整各模式的类别，最终使各模式到其判属类别中心的距离平方之和最小。{}NxxxGGG,,,2110.3.1动态聚类方法⒊算法原理步骤⑴任选C个模式特征矢量作为初始聚类中心：,令。)0()0(2)0(1,,,czzzGGG0k=⑵将待分类的模式特征向量集中的模式逐个按最小距离原则分划给C类中的某一类，即:如果则,式中表示和的中心的距离，上角标表示迭代次数。于是产生新聚类{}ixG()()min[]kkilijjdd=,1,2,,,iN=(1)kilxω+∈G)(kijdixG()kjω)(kjzG(1)kjω+,1,2,jc=(3)计算重新分类后的各类心式中为类中所含模式的个数。(1)(1)(1)1,kijkjikxjzxnω+++∈=∑GGG1,2,,jc=)1(+kjn(1)kjω+⒊算法原理步骤(4)如果,则结束,否则,转至(2)。(1)(),kkjjzz+=GGcj,,2,1=1kk=+选代表点初始分类分类合理否最终分类修改分类YN4.动态聚类框图•例已知有20个样本，每个样本有2个特征，数据分布如下图,使用C－均值法实现样本分类（C=2）。令C=2，选初始聚类中心为1122(1)(0,0);(1)(1,0)TTZxZx====GGGG样本序号x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x20867897898967777888991x5461098765109872x9xG10xG11xG12xG13xG14xG15xG16xG17xG18xG19xG20xG311243201xG2xG3xG4xG6xG7xG8xG5xG1x5461098765109872x9xG10xG11xG12xG13xG14xG15xG16xG17xG18xG19xG20x