模式识别导论6.pptVIP

第六章 聚类分析 §6－1 分类与聚类的区别 分类：用已知类别的样本训练集来设计分类器（监督学习） 聚类（集群）：用事先不知样本的类别，而利用样本的先验 知识来构造分类器（无监督学习） §6-2 系统聚类 系统聚类：先把每个样本作为一类，然后根据它们间的相 似性和相邻性聚合。 相似性、相邻性一般用距离表示 （1）两类间的距离 1、最短距离：两类中相距最近的两样品间的距离。 6、 离差平方和： 设N个样品原分q类，则定义第i类的离差平方和为： 离差平方和增量：设样本已分成ωp,ωq两类，若把ωp,ωq合为ωr类，则定义离差平方： 3、求最小元素： 4、把ω1,ω3合并ω7=(1,3) ω4,ω6合并ω8=(4,6) 5、作距离矩阵D(1) 6、若合并的类数没有达到要求，转3。否则停止。 3、求最小元素： 4、ω8,ω5,ω2合并, ω9=（2,5,4,6） §6-2 分解聚类 分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。 目标函数 两类均值方差 分解聚类框图： 例：已知21个样本，每个样本取二个特征，原始资料矩阵如下表： 第10次迭代x1划入G2时，E最大。于是分成以下 　两类： ∴ 作业： 样本 1 2 3 4 5 6 7 8 0 2 1 5 6 5 6 7 0 2 1 3 3 4 4 5 用对分法编程上机，分成两类画出图形。 §6-3 动态聚类——兼顾系统聚类和分解聚类 一、动态聚类的方法概要 ① 先选定某种距离作为样本间的相似性的度量; ② 确定评价聚类结果的准则函数; ③ 给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。 初始分类 三、初始分类和调整 １． 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。 ２． 选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。 ３． 直接用样本进行初始分类，先规定距离d,把第一个样品 作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于d，决定分裂还是合并。 ４．最佳初始分类 初始分类数k的确定有时是不准确的。假设k是逐渐增加的。如图所示， 准则函数下降很快，经过拐点A后，下降很慢。说明拐点附近对应的k，比较接近最佳的初始分类。就是最佳初始分类。 上式表明， Gj类的聚类中心应选在该类样本的均值 第一步：任选k个初始聚类中心Z1 (l) , Z2 (l),….. Zk (l) 第二步：计算每个样本到k个聚类中心的距离，并按最近规则 归类。 其中Gj (k)为聚类中心Zj(k)的样本聚类。在第k次迭代，分配各个样本x到k个聚类中心。 第三步：从第二步的结果，计算新的聚类中心。 上面已经证明，该新聚类中心可以使准则函数的Jj值最小。 第四步：若新聚类中心与前一个聚类中心相等，即 Zj(k+1) = Zj(k) j=1,2,…..k 则算法收敛，聚类结束。否则，转第二步。 例：已知有20个样本，每个样本有2个特征，数据分布 　如下图 第三步：根据新分成的两类建立新的聚类中心 第三步，更新聚类中心 第四步， 第二步， 第三步，更新聚类中心 上机作业 已知十个样本，每个样本2个特征，数据如下： 用K次平均算法和ISODATA算法分成3类，编程上机，并画出分类图。 五、ISODATA算法(迭代自组织数据分析算法） ISODATA算法与K均值算法有相似之处，即聚类中心根据样 本的均值来修改。不同的是，这种算法进行的过程中聚类中心的 数目不是固定不变而是反复进行修改。聚类既有合并也有分裂， 合并与分裂是在一组预先选定的参数指导下进行的。此外，一些 经验结果也包含在算法中。 ISODATA算法共分十