《模式识别导论六.pptx》由会员分享，可在线阅读，更多相关《模式识别导论六.pptx（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1模式识别导论六模式识别导论六6-2 系统聚类系统聚类n n系统聚类：先把每个样本作为一类，然后根据它们间的相似性和相邻性聚合。n n相似性、相邻性一般用距离表示n n（1）两类间的距离n n1 1、最短距离：两类中相距最近、最短距离：两类中相距最近的两样品间的距离。的两样品间的距离。第1页/共33页 2、最长距离 ：两类中相距最远的两个样本间的距离。3、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。设1类和23类间的最短距离为d12，最长距离为d13，23类的长度为d23，则中间距离为：上式推广为一般情况：第2页/共33页4、重心距离：均值间的距离5、类平均距离：两类中各
2、个元素两两之间的距离平方相加后取平均值 第3页/共33页n n6、离差平方和：n n设设NN个样品原分个样品原分q q类，则定义第类，则定义第i i类的离差平方和为：类的离差平方和为：n n离差平方和增量：设样本已分离差平方和增量：设样本已分成成 p p,q q两类，若把两类，若把 p p,q q合为合为 r r类，类，则定义离差平方：则定义离差平方：第4页/共33页（2）系统聚类的算法（略）例：如下图所示 1、设全部样本分为6类，2、作距离矩阵D(0)第5页/共33页1234529311644916645254364664258119第6页/共33页n n3、求最小元素：n n4、把1,3合
3、并7=(1,3)n n 4 4,6 6合并合并 8 8=(4,6)=(4,6)n n5、作距离矩阵D(1)728298491652544第7页/共33页n n6、若合并的类数没有达到要求，转3。否则停止。n n3、求最小元素：n n4、8,5,2合并,9=（2,5,4,6）第8页/共33页6-2 分解聚类分解聚类n n分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。n n目标函数 两类均值方差 N：总样本数，：1类样本数 ：2类样本数，第9页/共33页v分解聚类框图：分解聚类框图：初始分类调整分类方案最终结果目标函数达到最优先？第10页/共33页n n对分算法：略 例：已知21个样本
4、，每个样本取二个特征，原始资料矩阵如下表：样本号 12345678910 x10022445667x2655343121011 12 13 14 15 16 17 18 19 20 21-4-2-3-3-5100-1-1-3322021-1-2-1-3-5第11页/共33页目标函数解：第一次分类时计算所有样本，分别划到时的E值，找出最大的。1、开始时，第12页/共33页 2、分别计算当 划入 时的E值把 划入时有第13页/共33页n n 然后再把 划入 时对应的E值，找出一个最大的E值。把 划为 的E值最大。E(1)=56.6再继续进行第二，第三次迭代计算出 E(2),E(3),第14页/共3
5、3页 次数 E值 1 56.6 2 79.16 3 90.90 4 102.61 5 120.11 6 137.15 7 154.10 8 176.15 9 195.26 10 213.07 11 212.01第15页/共33页n n 第第1010次迭代次迭代 划入划入 时，时，E E最大。于是分最大。于是分成以下两类：成以下两类：n n每次分类后要重新计算 的值。可用以下递推公式：第16页/共33页第17页/共33页 作业：样本 1 2 3 4 5 6 7 8 0 2 1 5 6 5 6 7 0 2 1 3 3 4 4 5 用对分法编程上机，分成两类画出图形。第18页/共33页6-3 动态聚
6、类动态聚类兼兼顾系统聚类和分解聚类顾系统聚类和分解聚类一、动态聚类的方法概要 先选定某种距离作为样本间的相似性的度量;确定评价聚类结果的准则函数;给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。第19页/共33页选代表点初始分类分类合理否最终分类修改分类YN动态聚类框图动态聚类框图第20页/共33页 二、代表点的选取方法：代表点就是初始分类的聚类中心数k 凭经验选代表点，根据问题的性质、数据分布，凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的代表点从直观上看来较合理的代表点k;k;将全部样本随机分成将全部样本随机分成k k类，计算每类重心，把这些类，计算每类重心
7、，把这些重心作为每类的代表点重心作为每类的代表点;第21页/共33页 按密度大小选代表点：以每个样本作为球心，以d为半径做球形;落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于d1（人为规定的正数）则把第二大密度点作为第二代表点，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于d1。d1太小，代表点太多，d1太大，代表点太小，一般选d12d。对代表点内的密度一般要求大于T。T0为规定的一个正数。用前k个样本点作为代表点。第22页/共33页n n三、初始分类和调整 选
8、一批代表点后，代表点就是聚类中心，计算其它样选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。形成初始分类，再重新计算各聚类中心，称为成批处理法。选一批代表点后选一批代表点后,依次计算其它样本的归类，当计算完第依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，新的聚类中心，再计算第二个样本到新的聚类中心的距
9、离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。此法称为逐个处理法。直接用样本进行初始分类，先规定距离直接用样本进行初始分类，先规定距离d,d,把第一个样品作把第一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于一个聚类中心距离小于d d，就把第二个样本归于第一类，否，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是
10、小于根据样本到聚类中心距离大于还是小于d d，决定分裂还是合，决定分裂还是合并。并。第23页/共33页最佳初始分类。最佳初始分类。如图所示，随着初始分类如图所示，随着初始分类k k的增大，准则函数下降很快，经的增大，准则函数下降很快，经过拐点过拐点A A后，下降速度减慢。拐点后，下降速度减慢。拐点A A就是最佳初始分类。就是最佳初始分类。第24页/共33页n n四、K次平均算法：成批处理法（算法略）例：已知有例：已知有2020个样本，每个样本有个样本，每个样本有2 2个特征，数据分布如下个特征，数据分布如下图图第一步：令K=2，选初始聚类中心为样本序号x1x2x3x4x5x6x7x8x9x10
11、特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x2086789789896777788899第25页/共33页第26页/共33页第27页/共33页第28页/共33页n n第三步：根据新分成的两类建立新的聚类中心第三步：根据新分成的两类建立新的聚类中心第四步：转第二步。第二步：重新计算 到z1(2),z2(2)的距离，把它们归为最近聚类中心，重新分为两类，第29页/共33页n n第三步，更新聚类中心第30页/共33页n n第四步，n n第二步，n n第三步，更新聚类中心第31页/共33页上机作业上机作业n n已知十个样本，每个样本2个特征，数据如下：n n用K次平均算法和ISODATA算法分成3类，编程上机，并画出分类图。样本序号1 2 3 4 5 6 7 8 9 10 x10 1 2 4 5 5 6 1 1 1 x20 1 1 3 3 4 5 4 5 6第32页/共33页