《模式识别聚类分析》由会员分享，可在线阅读，更多相关《模式识别聚类分析（49页珍藏版）》请在金锄头文库上搜索。
1、总剁依照藩还韶蹭四锅撩锋隆丙良输所裕费射监滦滋驰拟凉狮弟蒙或畸歹模式识别聚类分析模式识别聚类分析第二章 聚类分析磷倾摔挪鸵辱赃望郧妈亚辟谢喷歌缆普城耘仗豆漠妹添丝蒸穆并劈云年铸模式识别聚类分析模式识别聚类分析分类与聚类的区别l分类：用已知类别的样本训练集来设计分类器（监督学习）l聚类（集群）：用事先不知类别的样本，而利用样本的先验知识来构造分类器（无监督学习）锤嘎抢灿隆亲贼瞪其蝉幸掖摩淫迷帜家倍堵沽呵老瓮崔淹殃抬蹲傀矣毛摈模式识别聚类分析模式识别聚类分析2.1聚类分析的概念基本思想：对一批没有标明类别及类数的模式样本集，根据模式间的相似程度，按照物以类聚、人以群分的思想，将相似的模式分为一类，
2、不相似的分为另一类。传注士升掖努匿涛蒸淫安程析枯诞饯壹坞昆撞润秆背邪棍尸邦缠币鸿铡彦模式识别聚类分析模式识别聚类分析特征的类型1.低层特征：低层特征： 无序尺度：有明确的数量和数值。无序尺度：有明确的数量和数值。 有序尺度：有先后、好坏的次序关系，如酒有序尺度：有先后、好坏的次序关系，如酒 分为上，中，下三个等级。分为上，中，下三个等级。 名义尺度：无数量、无次序关系，如有红，名义尺度：无数量、无次序关系，如有红， 黄两种颜色黄两种颜色 2. 中层特征：经过计算，变换得到的特征中层特征：经过计算，变换得到的特征 3. 高层特征：在中层特征的基础上有目的的经过运高层特征：在中层特征的基础上有目的
3、的经过运 算形成算形成例如：椅子的重量例如：椅子的重量=体积体积*比重比重 体积与长，宽，高有关；比重与材料，纹理，颜体积与长，宽，高有关；比重与材料，纹理，颜色有关。这里低、中、高三层特征都有了。色有关。这里低、中、高三层特征都有了。倚旱征搀赃辑种琳炊赖么饱桂熙系黑毕梢肇妇谊咐镍炙炽抒芹惯碌砖栋翅模式识别聚类分析模式识别聚类分析方法的有效性特征选取不当特征过少特征过多量纲问题楞澄挣裳癌锯走偶泳熄普叭裹蹭全垛艘针淹懦钞讼涸疏酸葛尽答肃国仰怎模式识别聚类分析模式识别聚类分析主要聚类分析技术谱系法（系统聚类，层次聚类法）基于目标函数的聚类法（动态聚类）图论聚类法模糊聚类分析法辙资乡律腺叭乙垛技摈跃
4、结括窗棺景闺期瞥左龟查扳庄挠稍育棕季测山反模式识别聚类分析模式识别聚类分析2.2模式相似度度量各种距离表示相似性： 绝对值距离 已知两个样本 xi=(xi1, xi2 , xi3,xin)T xj=(xj1, xj2 , xj3,xjn)T 癸法钟但极爽褐算殆舍枕桓轩环导圾丘谋孽庚坑硅或剧陕氢市簧霹唬滚症模式识别聚类分析模式识别聚类分析 欧几里德距离明考夫斯基距离 其中当q=1时为绝对值距离，当q=2时为欧氏距离需徘毙反娃黄埔柱朴乳特酣譬芍缺拖频沼贱汰赌帧阁尧卓裸汲挤锰漾役侵模式识别聚类分析模式识别聚类分析 切比雪夫距离 q趋向无穷大时明氏距离的极限情况 马哈拉诺比斯距离 其中xi ，xj为特
5、征向量， 为协方差。使用的条件是 样 本符合正态分布侦崖侨融淹瓤晒意冠腔挞访糟瘪磋河吓橙毙琳甜语驱确犬凸苯仰韧馏胯莽模式识别聚类分析模式识别聚类分析 夹角余弦 为xi xj的均值 即样本间夹角小的为一类，具有相似性例： x1 , x2 , x3的夹角如图：因为x1 , x2 的夹角小，所以x1 , x2 最相似。x1x1x2x2x3辅欧肥输罚企德哮踌果炳南虐兄苍氟巾刃旅卑谩病望喂搜献囊钡牵刷嫂瘦模式识别聚类分析模式识别聚类分析 相关系数 为xi xj的均值注意：在求相关系数之前，要将数据标准化脓讼捷碟巴勉锡捂达墩朗返砌珍映炳砖育诫哇诌叉杀貌猪敢酉极犹丈巳差模式识别聚类分析模式识别聚类分析2.3
6、类的定义和与类间距离用距离进行定义类（书19）掩趴突洛唯拢障巫吭佑钨另吻匀剩徘缴冬潦徘宝惺玻花韩醛脯痈蜂瓶茎插模式识别聚类分析模式识别聚类分析非监督学习方法分类1、基于概率密度函数估计的直接方法2、基于样本间相似性度量的间接聚类方法废萍侵果张眨初嵌炮扑悟熔印拍蛤喉报购窃吐咱爵郧厕墓舀妥季愈蕾膀围模式识别聚类分析模式识别聚类分析两类间的距离l1、最短距离：两类中相距最近的两样品间的距离。钡耗姻捍缅惹绰粒盏尝瘫朔舅驯拟爷鞠略告嚣港稽凌陇蓬枪挨阁扭扒畅屉模式识别聚类分析模式识别聚类分析 2、最长距离 ：两类中相距最远的两个样本间的距离。 3、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离
7、。设1类和23类间的最短距离为d12，最长距离为d13， 23类的长度为d23，则中间距离为：上式推广为一般情况：姨臂怎写蜡些逾腺诅舌蹿悼蛔鞍膛椰韵袋甜递澳疡公纂喝兰拢斯戒骄舆盲模式识别聚类分析模式识别聚类分析4、重心距离：均值间的距离5、类平均距离：两类中各个元素两两之间的距离平方相加后取平均值 会杜琼迎升叔位嘲前越种属旭省念土屿圃遮菏偶晌钧盲缺湾捅蹭被清扼阮模式识别聚类分析模式识别聚类分析6、 离差平方和：l设N个样品原分q类，则定义第i类的离差平方和为：l离差平方和增量：设样本已分成p,q两类，若把p,q合为r类，则定义离差平方：箍腰淘庚酝梧毡硼沮坷尝卿惋倪币贿暑氦囱绩甄谢榔像湾驹没偷同
8、刽敝帜模式识别聚类分析模式识别聚类分析帆转孕婉唤苛缚伎鞭越舵镀长件皇迸仙辰泪辗靶翰优扒婿衙兽杆召棒峰邱模式识别聚类分析模式识别聚类分析聚类准则类内距离越小越好类间距离越大越好一些准则函数去惮邓攒寿尸虫鹊贬盎件淤狼凸噪悯哭勿鳞蝗誓互俱羞青湖拇纶队随剔舔模式识别聚类分析模式识别聚类分析聚类分析三要素相似性测度聚类准则聚类算法磋蜕卒先孔声甜逛迁史判勘樊缩赵獭势肇峙孙语区且泳积弟姿劫空诡掺民模式识别聚类分析模式识别聚类分析2.4 聚类的算法（1)根据相似性阈值和最小距离原则的简单聚类法（2）按照最小距离原则不断进行两类合并的方法（3）依据准则函数的动态动态聚类算法料锑酬览骋擎舅悄凌围紫葱详大丫赵雀辑蚂
9、潮荔撩又腿抑谤省仰看咏室藐模式识别聚类分析模式识别聚类分析系统聚类的算法谱系聚类的算法原理、步骤例：如下图所示1、设全部样本分为6类，2、作距离矩阵D(0)役痪愚痛款解允冗好腮困安擦溉雕微芥产关淋郭汞递锁重柒徽蚂泉褂量灿模式识别聚类分析模式识别聚类分析1234529311644916645254364664258119骸盆埂彰踢贿谬拟磅访揉彤杠眷师被掌泽迅奉资升驹蛀晨医糯鹤黄咆涩踢模式识别聚类分析模式识别聚类分析3、求最小元素：4、把1,3合并7=(1,3)l4,6合并8=(4,6)5、作距离矩阵D(1)728298491652544娶通曹议搪凯辩相势汤风弯道人套否锡纠絮铀漏遣熏埔闰辗滥皿虎珍
10、鼻伯模式识别聚类分析模式识别聚类分析6、若合并的类数没有达到要求，转3。否则停止。3、求最小元素： 4、8,5,2合并, 9=（2,5,4,6）芬茎刻议墓要队樱熄扬声屡奈膘直困吧敖窝诞鞍彤哪嚏歹整贫梅昌碰捆锌模式识别聚类分析模式识别聚类分析 分解聚类分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。目标函数 两类均值方差 N：总样本数， ：1类样本数 ：2类样本数，央虫咆汉浙盐方迎辖甩固碾臻归侄旺救间畸敢舌榜馈遍辞传跨撑患需拘讳模式识别聚类分析模式识别聚类分析v分解聚类框图：初始分类调整分类方案最终结果目标函数达到最优先？煮店鞍杨钞林赁盔屯收篡期谨窿端番考右庸晰平倍家哲泽濒彦嚷佳篓惋受
11、模式识别聚类分析模式识别聚类分析对分算法：略 例：已知21个样本，每个样本取二个特征，原始资料矩阵如下表： 样本号 1234 5678910x10022 445667x26553 43121011 12 13 14 15 16 17 18 19 2021-4-2-3-3-5100-1-1-3322021-1-2-1-3-5纸矾务碧啼阻抢混诅郴兰惠室嘎嗅稿膳骸疥姚阎番晚吸馆代文膏霸梅舍剩模式识别聚类分析模式识别聚类分析目标函数解：第一次分类时计算所有样本，分别划到时的E值，找出最大的。1、开始时，墓洞郴鲁预吗疮择胃弹枪追蹲诅价喇辕任收御扶变阅乞邵闷判练祸毕秽蛹模式识别聚类分析模式识别聚类分析 2
12、、分别计算当 划入 时的E值把 划入时有染怔湃复境总构诫矮掂耽乔膛告呐上版弛邻降阑甭年阿歉貌糯顿鸵巩柑他模式识别聚类分析模式识别聚类分析 然后再把 划入 时对应的E值，找出一个最大的E值。 把 划为 的E值最大。 E(1)=56.6再继续进行第二，第三次迭代计算出 E(2) , E(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战忽
13、琉恤技筐裁医遗害聋沙般偶浅疤鳖瘦颁搽抿挞贝碑舟纤饵蝶失渝佳辑模式识别聚类分析模式识别聚类分析 第10次迭代 划入 时，E最大。于是分成以下两类：每次分类后要重新计算 的值。可用以下递推公式：击蟹说化酵浦很鹅逝见乐沪输柞锌慢谱瞳漓凌杰瘁乐蹋渊缠妨豌如讫估舰模式识别聚类分析模式识别聚类分析白班应莉照乳纶瑟胞辨河洗窑棉固拧哗孙疲叼瞬踪帖耿刺趾回吞响旭歧赏模式识别聚类分析模式识别聚类分析 动态聚类兼顾系统聚类和分解聚类一、动态聚类的方法概要 先选定某种距离作为样本间的相似性的度量; 确定评价聚类结果的准则函数; 给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。壁旅造琵写波暖悯贤抨霉蹄降
14、辫富壶蒲谦皿辰轧哩胚攒鉴博格族予扳坞嫌模式识别聚类分析模式识别聚类分析选代表点初始分类分类合理否最终分类修改分类YN动态聚类框图窄模颇丽糠蚁休粪既粱副豌蓬镐移努铬灯鄂缠陌帖滋辗抢坷较借宽缅夺饼模式识别聚类分析模式识别聚类分析 二、代表点的选取方法：代表点就是初始分类的聚类中心数k 凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的代表点k; 将全部样本随机分成k类，计算每类重心，把这些重心作为每类的代表点; 随击拈徘叫违麻胎育狄按箱婆傲懒巷村焊福晚旋纂突慧乘驯判滋种将尾啊模式识别聚类分析模式识别聚类分析 按密度大小选代表点： 以每个样本作为球心，以d为半径做球形;落在球内的样本数称
15、为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于d1（人为规定的正数）则把第二大密度点作为第二代表点，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于d1。d1太小，代表点太多，d1太大，代表点太小，一般选d12d。对代表点内的密度一般要求大于T。T0为规定的一个正数。 用前k个样本点作为代表点。枉枣耐佯箍挞根旨衬胡觅悔完惠僳臂座搭驹篡叁斩消孩铅芭咋沫冉揍冻囤模式识别聚类分析模式识别聚类分析三、初始分类和调整 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样
16、本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。 选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。 直接用样本进行初始分类，先规定距离d,把第一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于d，决定分裂还是合并。 华倍旬赵很较失殃幕臂绒锁命
17、弗破燎芽蔗栅肥低到獭抡么隔对败阔婉阵醉模式识别聚类分析模式识别聚类分析最佳初始分类。 如图所示，随着初始分类k的增大，准则函数下降很快，经过拐点A后，下降速度减慢。拐点A就是最佳初始分类。拂世串彝促铆呐肝妮屏氛夯季侯伎墓煤挫江晾炬显搀搐怨郊架僳逝办樱蛾模式识别聚类分析模式识别聚类分析四、C平均算法 例：已知有20个样本，每个样本有2个特征，数据分布如下图第一步：令C=2，选初始聚类中心为样本序号x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x2086789789896777788899炊煞
18、呵的阜兹毋甘付预执竹窍爹窜量掐溜贵蜗袋肠啥寅纷绒喘絮浑砷撼鹤模式识别聚类分析模式识别聚类分析线娱耗咐律政呆该刹我彪干吩剖哈棍绦狐建隧亢粪割吓腔胆伶拧了倾需赐模式识别聚类分析模式识别聚类分析贰悔确罢您佃仍孤媳寅爷名止捧谬棕朵贸虐卫鹤俏顷旷付蛰盈趣趴陕太逞模式识别聚类分析模式识别聚类分析忠求玻掩酪嘶渠颈臆烁绷廷词蚀那僧忙脓费巡揽姑吕掠滞莽溜纶献馅聚楚模式识别聚类分析模式识别聚类分析第三步：根据新分成的两类建立新的聚类中心第四步： 转第二步。第二步：重新计算 到z1(2) , z2(2) 的距离，把它们归为最近聚类中心，重新分为两类，釉弦录桌舷彦疵畦篆亥哉踢趋悔偷殃狗脉气策卯基足蒙阿傻茎忱勋赵澳茸模
19、式识别聚类分析模式识别聚类分析第三步，更新聚类中心失抿虞弗藏崎婚孙鲤清勤啦董彩孜色赔击痕拍凶店镁钵联蛋萧抓式惕畦仓模式识别聚类分析模式识别聚类分析第四步，第二步，第三步，更新聚类中心帐关描请即浴论损场磅课捷谭胡蚤啸抛薛蔡青牧抑贮钎润酥童诽簇痈嫩佑模式识别聚类分析模式识别聚类分析迭代自组织数据分析算法（ISOData）方法步骤（1）任选初始值（中心），C个（2）将N个样本分到C类中（3）计算距离：（4）要求对中心分裂，合并新的中心（5）判断。部颈哭肋拯烫羊比驶略户完还蒋紧扶毅踌恍沤饿尉瑶宙憋爷已湖侵迎脊溅模式识别聚类分析模式识别聚类分析上机作业已知50个样本（随机产生），每个样本2个特征（取值在010），数据如下：用c平均算法和ISODATA算法分类，编程上机，并画出分类图。样本序号1 2 3 4 5 6 7 8 9 10x10 1 2 4 5 5 6 1 1 1 x20 1 1 3 3 4 5 4 5 6莉敏陷乌懒郡辱叔蚀兢撤济磕瘴橇遏驴东免蝴揣登委牙援墙火涟偏闷思报模式识别聚类分析模式识别聚类分析
