哈工大模式识别第四章第五章讲解.ppt

* (5) 对于所有的j，若ek≤ej （表明ekei）则将y从wi移到 wk中（否则， eiei ,不用移） (6) 重新计算mi和mk，并修改Jc 。 (7) 若连续迭代N次(即所有样本都运算过) Jc不变，则停止，否则转到2。　　 * 确定类别数的实验方法 上述C—均值算法都是在类别c已知条件下进行的。 在类别数未知情况下，可以假设类别数是逐步增加的，准则函数随c的增加而单调地减小。可选择平缓时转折处的C值。 * 5.3.1.3 ISODATA算法 　　C—均值算法比较简单，但它的自我调整能力也比较差。这主要表现在类别数不能改变，受代表点初始选择的影响也比较大。 全称‘迭代自组织数据分析技术’（Iterative Self-Organizing Data Analysis Technique Algorithm）。 ISODATA算法的功能与C—均值算法相比的改进。 1. 不是每调整一个样本的类别就重新计算一次各类均值（逐个样本修正），而是每次把全部样本都调整完毕后再重新计算样本均值（成批样本修正） 。 2.考虑了类别的合并与分裂，因而有了自我调整类别数的能力。从而可以得到较为合理的类别数。　 * 5.3.2 分级聚类方法 分级聚类方法的目的并不把N个样本分成某一个预定的类别数C，而是把样本集按不同的相似程度要求分成不同类别的聚类。 最极端的情况: (1)每个样本各自为一类.相似性最大 (2)将所有样本归一类。相似性最小 在这两个极端之间的是：类别数从N逐渐减少，每类的数量相应增加，而类内样本的相似程度也随之下降。 分级聚类的两种途径 分级聚类可通过两种途径实现：合并、分裂 合并：开始时，每个样本自成一类，然后通过合并类别减少类 分裂：开始时，所有样本是一类，然后通过分裂类别样本增加类 合并方法较简单，后续重点介绍 * 基于合并的分级聚类 1）第一次划分（称为1水平），每个样本各自为一类，N个样本，共N类；总的相似性最大 2）第2次划分（称为2水平），按类别相似性最大原则，合并2个类，此时，共N-1类；相似性减小 3）若是第k次划分（称为k水平），按类别相似性最大原则，合并k-1水平下的2个类，则有N-k+1类 4）最后一次划分（N水平），将所有样本归1类，只有1类。总的相似性最小 这种分级聚类，一经合并成一类的样本不再分裂，类别数也随之逐渐减少，类内相似程度逐渐降低。可用一树形结构表示（如下图所示）。 * * 例：6个样本的分类树 100 90 80 70 60 50 40 30 20 10 0 相似度(%) * 相似性度量方法 分级聚类方法的关键问题是相似度如何定义的问题，分级聚类方法的算法是比较简单的。 分级聚类是对数据集进行划分，在这些数据之间只有度量值之间的差别，因此只能按度量值之间的差异来定义相似度。 不同的相似性度量方法，对聚类也有不同效果。 * 三种相似性度量方法 两个聚类Гi与Гj之间的相似性度量，用 Δ(Гi,Гj)表示 （值越小表明两个类别越相似）。 　 1.最近距离　　　　 　2.最远距离　　　　 　3.均值距离　　　　 * 分级聚类算法 初始时设置Гj, j ∈I, I={j|j=1,2,…,N}及距离阈值d（可以取无穷大）。 Гj表示各个聚类集合，N是样本数，初始时每个样本自成一类。 步骤1： 在集合Гj, j ∈I中找到一对满足下列条件的聚类集合Гi与Гk。 Δ(Гi,Гj)=min {Δ(Гi, Гj), i, j ∈I} 步骤2： 若距离超过设定的阈值d，则算法终止； 否则，把Гi 并入Гk ，并去掉Гi。 步骤3： 把i从指标集I中除掉，若I的基数仅等于2时，则终止计算，否则转向步骤1。 　　 * 最近距离作相似性度量时聚类结果 * 图中红色和黑色数据点来自两个正态过程 左：聚类结果和正态模型的结果一致（两个大类和3个孤立点小类） 右，有一个在两个点集交叠区的点（红色），则聚类错误（链接效应） 结论： 1）对长条形分布聚类正确，可以出现细长条的类。 2）聚类结果对噪声或数据点波动非常敏感。 下图：对于长条形分布：聚类正确 最远距离作相似性度量时聚类结果 * A）分布紧密的两类，交叠区无点，正确聚类 B）分布紧密的两类，但交叠区有点（p1,p2），也能正确聚类 C）长条形分布：聚类错误（说明个别远离点对聚类结果影响大，该度量方法不能得到长条形的聚类） * 最远距离作相似性度量时不同距离阈值（d）的影响 * 左：较大的距离阈值（ 将两类聚成4类） 过大的阈值，所有的数据点可能归入一类 右：较小的距离阈值（ 将两类分