资源描述：
《《模式识别导论》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章聚类分析§6－1分类与聚类的区别分类：用已知类别的样本训练集来设计分类器（监督学习）聚类（集群）：用事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）1§6-2系统聚类系统聚类：先把每个样本作为一类，然后根据它们间的相似性和相邻性聚合。相似性、相邻性一般用距离表示（1）两类间的距离1、最短距离：两类中相距最近的两样品间的距离。22、最长距离：两类中相距最远的两个样本间的距离。3、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。设ω1类和ω23类间的最短距离为d12，最长距离为d13，ω23类的长度为d23，则中间距
2、离为：上式推广为一般情况：34、重心距离：均值间的距离5、类平均距离：两类中各个元素两两之间的距离平方相加后取平均值46、离差平方和：设N个样品原分q类，则定义第i类的离差平方和为：离差平方和增量：设样本已分成ωp,ωq两类，若把ωp,ωq合为ωr类，则定义离差平方：5（2）系统聚类的算法设参加聚类的样本共N个，先选定样本间距离和类间距离的计算公式，再按以下步骤聚类。1、假定N个样本各成一类，记作ω1,ω2,……ωN。2、作距离矩阵D(0),因D(0)矩阵是对称的N×N矩阵，我们 只计算下三角部分，第i行第j列处的元素dij用i和j两样本的距
3、离平方表示。63、求D(0)的最小元素dpq＝mindijp≠q因此，ωp和ωq是目前最近的两类。4、把ωp与ωq合并成新的类，并求新类与原有其它各类间的距离。5、作下一距离矩阵D(1)。6、若分的类数已满足预先要求或全部样本已合成一类，则算法结束。否则，重复以上步骤。ω1ω2……ω2ω3d2ij….7例：有六个样本X={x1,x2,x3,x4,x5,x6}其分布如下图所示：1、设全部样本分为6类，2、作距离矩阵D(0)ω1ω2ω3ω4ω5ω29ω3116ω4491664ω5254364ω66425811983、求最小元素：4、把ω1,ω3合并ω7
4、=(1,3)ω4,ω6合并ω8=(4,6)5、作距离矩阵D(1)ω7ω2ω8ω29ω84916ω5254496、若合并的类数没有达到要求，转3。否则停止。3、求最小元素：4、ω8,ω5,ω2合并,ω9=（2,5,4,6）10§6-2分解聚类分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。目标函数两类均值方差N：总样本数，：ω1类样本数：ω2类样本数，11分解聚类框图：初始分类调整分类方案最终结果目标函数达到最优否？12对分算法：1、选取目标函数，把全体样品分成两类2、分别计算把x1,x2,……,xN并入G2类时的E值，设当xi并入G2时的
5、E值最大，则把它并入G2得:3、再分别计算把x1,…,xi-1,xi+1……,xN并入G2的E值，若当xj并入G2时E最大，则并入G2得：134、若E(k+1)≥E(k),则重复上述步骤，直到某个E(K)达到最大值为止。这时最好的分类是G1(k)共有n-k个样品，G2(k)有k个样品。每次分类后都要重新计算之值。可用以下递推公式：14例：已知21个样本，每个样本取二个特征，原始资料矩阵如下表：样本号12345678910x10022445667x265534312101112131415161718192021-4-2-3-3-5100-1-1-3
6、322021-1-2-1-3-515解：第一次分类时计算所有样本，分别划到G2时的E值，找出最大的。1、开始时，∴目标函数2、分别计算当x1,x2,….x21划入G2时的E值。把x1划入G2时有：利用递推公式16然后再把x2,….x21划入G2时对应的E值，计算出来进行比较，找出一个最大的E值。即把x21划为G2的E值最大。∴再继续进行第二，第三次迭代……计算出E(2),E(3),……如下表：1718第10次迭代x1划入G2时，E最大。于是分成以下两类：∴19作业：样本123456780215656702133445用对分法编程上机，分成两类画出图
7、形。20§6-3动态聚类——兼顾系统聚类和分解聚类一、动态聚类的方法概要①先选定某种距离作为样本间的相似性的度量;②确定评价聚类结果的准则函数;③给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。21选代表点初始分类分类合理否最终分类修改分类YN动态聚类框图二、代表点的选取方法代表点就是初始分类的聚类中心数k。①凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的代表点k;②将全部样本随机分成k类，计算每类重心，把这些重心作为每类的代表点;22③按密度大小选代表点：以每个样本作为球心，以d为半径做球形;落在球内的样本数称为该
8、点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代
