模式识别课件8.pdf

第十章 非监督学习方法 10.1 引言 监督模式识别：（已知）样本集 训练（学习）识别（分类）分类器设计 非监督模式识别：（未知）样本集 非监督学习（聚类分析）后处理 举例说明现实中的非监督模式识别问题?通过寻找可能存在的分类来理解某一对象?将复杂多样的对象用有限典型来代表 根据：某种假设（对聚类应具有的性质的认识）结果：聚类（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+=.kNl1 其中k应满足：=kNlim 0lim=NkN =NkNloglim 通常可选 Nak=&，a为一定的常数 问题：如何选择投影方向？-方差最大的准则有时并不一定最有利于聚类。10.2.2 基于对称集性质的单峰子集分离法 对称集：对集合 y=，设)(yp的峰点出现在0y，即 )(sup)(0ypypy=若 jiyy,，),(),(00yyyyii)()(jiypyp 则称为对称集?对称集一定是单峰的?划分单峰子集划分对称集 算法：（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 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 Y（2）对每个样本ky，Nk,1L=，逐一计算)|(ikyf，并归入使)|(ikyf最大的子集中。（3）重复（2），直到不再有样本发生转移。10.2.4 参数化方法 以上介绍方法均属非参数方法，在对数据分布没有先验知识的情况下采用。如果已知（或可假设）数据分布的概率密度函数的形式，则可采用参数化方法。回顾：3.4 非监督参数估计 非监督参数估计指样本类别未知，但各类条件概率密度函数的形式已知，根据所有样本估计各类密度函数中的参数。-混合概率模型 3.4.1 非监督参数估计的最大似然法 3.4.2 非监督参数估计示例：正态分布情况-局限：需要较强的先验假设，需要较多的样本 10.3 类别分离的间接方法 回顾：直接方法：1.估计概率密度函数 困难 2.寻找密度函数中的单峰 间接方法：考查样本这间的相似性，根据相似性把样本集划分为若干子集，使某种表示聚类质量的准则函数最优。不同的聚类方法实际上反映了对聚类（及数据）的不同理解：?混合模型：数据服从混合分布，聚类对应于各分布?单峰子集：聚类即概率分布中的单峰，即样本分布相对集中的区域?间接方法：相似的样本聚类，不同聚类的样本不相似 相似性度量：以某种距离定义 直观理解：同一类的样本的特征向量应是相互靠近的。前提：特征选取合理，能反映所求的聚类关系。与基于密度函数的方法的关系：概念上相互关联，因密度估计也是在样本间距离的基础上的。具体关系取决于具体数据情况。10.3.1 动态聚类方法 多次迭代，逐步调整类别划分，最终使某准则达到最优。三个要点：选某种距离作为样本相似性度量 定义某个准则函数，用于评价聚类质量。初始分类方法及迭代算法 （一）C 均值算法（k均值，C-means or k-means）误差平方和聚类准则 iciiycieJmyJi=121 其中，i是第i个聚类，ci,1L=，其中样本数为iN，i中样本均值为 =iyiiyNm1 直观理解：eJ反映了用c个聚类中心代表c个样本子集所带来的总的误差平方和。eJ是样本集Y Y与类别集的函数。C 均值算法的目标：最小化eJ 最小方差划分 另一种角度来看 C 均值方法：用 c 个码本来代表整个样本集，使这种表示带来的总体误差最小。-向量量化 Vector Quantisation 算法研究：设已有一个划分方案，考查k中的样本y，若把y移入j，此时k变成k，j变成j，有 ymNmmkkkk+=11 jjjjmyNmm+=11 21kkkkkmyNNJJ=21jjjjjmyNNJJ+=若 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.用1c聚类求c个代表点：各类中心外加离它们最远的样本点，从1 类开始。初始分类方法：1.最近距离法。离哪个代表点近就归入哪一类。2.最近距离法归类，但每次都重新计算该类代表点。3.直接划分初始分类：每一个样本自成一类，第二个样本若离它小于某距离阈值则归入此类，否则建新类，4.将特征归一化，用样本各特征之和作为初始分类依据。ijDjyiSUM=1)(，Ni,1L=.DiRy )(maxiSUMMAi=，)(miniSUMMIi=1)()1(+=MIiSUMMIMAck取整 说明：?初始划分无一定之规，多为启发式方法。?C 均值方法结果受初值影响，是局部最优解。关于类别数c，多假定已知，根据先验知识确定。一种实验确定方法：对L,3,2,1=c，取类，求)(cJe，如图找其中的拐点（图中3=c）（此方法并不总有效）Je(c)c C 均值聚类方法用于非监督模式识别的问题：均值聚类方法用于非监督模式识别的问题：1.要求类别数已知；2.是最小方差划分，并不一定能反映内在分布；3.与初始划分有关，不保证全局最优。（二）ISODATA 方法 特点：成批样本修正，把所有样本调整完后才重新计算均值。可进行类别合并与分裂。算法步骤：（1）初始化，聚类数c，中心im，ci,1L=（期望聚类数k）（2）把所有样本分到距离最近的类中，i，ci,1L=（3）若某个类j中样本数过少()NjNmax（标准偏差参数）且 j且)1(2+NjN 或 2/kc 则j分裂为两类，中心分别为+jm和jm，置1+=cc jjjmm r+=+，jjjmm r=其中 maxjjkr=，10 k（8）（合并）8-1 计算各类中心之间的距离 jiijmm=，cji,1,L=，ji 8-2 比较ij与c（合并参数），对小于c者排序：lljijiji+=maxmaxmaxmaxmaxmaxmaxmaxmaxmaxmaxmaxmaxmax,if,if,ifif)()(kiiikiikiiikikiiiiikiiiikiiii 其中maxi、maxk是同一类中样本间的最大连接损失。总类间损失：iciIRL=1 对i的解释：若两类间的最小近邻函数值小于其中任一类内的最大近邻函数值，则这种分类有损失，可合并。近邻函数准则：IRIANNLLJ+=算法：（1）计算样本间的距离矩阵 （2）计算样本间的近邻系数矩阵 （3）计算样本间的近邻函数矩阵L （4）根据矩阵L，把每个点与和它有最小近邻函数值的点连接 起来，形成初始聚类。（5）对每一类，计算i，若0i，则合并i与k。重复（5），直到所有0i 10.4 分级聚类方法（Hierachical Clustering）思想：从各类只有一个样本点开始，逐级合并，每级只合并两类，直到最后所有样本都归到一类。Hierarchical tree -dendrogram 聚类过程中逐级考查类间相似度，依此决定类别数。树枝长度：反映结点/树枝之间的相似度或距离 树枝位置：在不改变树的结构的情况下可以任意调整，调整方法需研究 距离/相似性度量：多种选择，如欧式距离、相关、City Block、例 距离（相似性度量）：?样本之间的度量?聚类之间的度量 两种聚类策略：?bottom-up:agglomerative algorithm?top-down:divisive algorithm 算法（从底向上）：（1）初始化，每个样本形成一类 （2）把相似性最大（距离最小）的两类合并 （3）重复（2），直到所有样本合并为两类。常用的几种类间似性度量：1.最近距离（single-link）(),(min,yyjiyyji=2.最远距离（complete-link）(),(max,yyjiyyji=3.均值距离（average-link）(),(,jijimm=不同相似性度量对结果的影响 10.5 非监督学习方法中的一些问题 尺度问题：直接方法：概率密度函数的估计问题 间接方法：常用、效率高、易实现 受初值影响 对数据分布情况有依赖 有盲目性：不一定能反映真实存的聚类 事先确定类别数 对相似性度量的依赖性 根本原因：已知信息的不足 解决办法：先验知识 多次试算 改进算法。（如 SOM，Fuzzy C-means）