遥感影像识别-第三章 聚类分析 Part Ⅱ

1、遥感影像识别遥感影像识别 第三章第三章: 聚类分析聚类分析 Part 3-1 相似性准则相似性准则 3-2 聚类准则函数聚类准则函数 3-3 两种简单的聚类算法两种简单的聚类算法 3-4 动态聚类算法动态聚类算法 3-5 聚类的评价聚类的评价 课堂回顾课堂回顾 v广义线性判别函数广义线性判别函数 x y v非线性判别函数非线性判别函数 分段线性判别函数：距离均值分段线性判别函数：距离均值 二次判别函数：判别方程二次判别函数：判别方程 课堂回顾课堂回顾 v聚类分析符合聚类分析符合“物以类聚，人以群分物以类聚，人以群分“的原则的原则 ，它把相似性大的样本聚集为一个类型，在，它把相似性大的样本聚集为

2、一个类型，在 特征空间里占据着一个局部区域。每个局部特征空间里占据着一个局部区域。每个局部 区域都形成一个聚合中心，聚合中心代表相区域都形成一个聚合中心，聚合中心代表相 应类型。应类型。 v相似性准则相似性准则:包括距离相似性度量和角度相似包括距离相似性度量和角度相似 性度量。性度量。 v距离相似性度量：欧氏距离、马氏距离、明距离相似性度量：欧氏距离、马氏距离、明 氏距离。氏距离。 d i iie yxyxyxD 1 2 |),( 课堂回顾课堂回顾 v在样本相似性度量的基础上，聚类分析还需要在样本相似性度量的基础上，聚类分析还需要 一定的准则函数，才能把真正属于同一类的样一定的准则函数，才能把

3、真正属于同一类的样 本聚合成一个类型的子集，而把不同类的样本本聚合成一个类型的子集，而把不同类的样本 分离开来。分离开来。 v聚类准则函数聚类准则函数:包括误差平方和准则、加权平包括误差平方和准则、加权平 均平方距离和准则、类间距离和准则。均平方距离和准则、类间距离和准则。 v误差平方和准则（最常用）：误差平方和准则（最常用）： c j n k jkc j mxJ 11 2 | 课后思考课后思考 v线性判别函数的适用性？ v聚类分析的优缺点？ v ERDAS image Model 工具如何实现聚类？ 3-3 两种简单的聚类算法两种简单的聚类算法 v本节介绍两种简单的聚类分析方法，它是对某些

4、关键性的元素进行试探性的选取，使某种聚类准 则达到最优，又称为基于试探的聚类算法基于试探的聚类算法。 v采用最近邻规则的聚类算法 v最大最小距离聚类算法 1. 采用最近邻规则的聚类算法采用最近邻规则的聚类算法 假设已有混合样本集 ，按照最近邻原则进 行聚类，算法如下： l选取距离阈值 ，并且任取一个样本作为第一 个聚合中心 ，如： 。 l计算样本 到 的距离 ： ,., 21n xxxX T 1 Z 11 xZ 2 x 1 Z 21 D l按照某种聚类准则考察聚类结果，若不满意，则 重新选取距离阈值 、第一个聚合中心 ，返回 ，直到满意，算法结束。 l在样本分布一定时，该算法的结果在很大程度上

5、取 决于第一个聚合中心的选取和距离阈值的大小。 p66 l该算法的优点是简单，如果有样本分布的先验知识 用于指导阈值和起始点的选取，则可较快得到合理 结果。对于高维的样本集来说，则只有经过多次试 探，并对聚类结果进行验算，从而选择最优的聚类 结果。 T 1 Z 2. 最大最小距离聚类算法最大最小距离聚类算法 该算法以欧氏距离为基础，除首先辨识最远的聚 类中心外，与上述算法相似。用一个例子说明该 算法。 以类间欧式距离最大作为选择聚类中心的条件。 v 3-4 动态聚类算法动态聚类算法 l在聚类分析中，动态聚类法是较普遍采用的方法 ，该算法首先选择某种样本相似性度量和适当的 聚类准则函数，使用迭代

6、算法，在初始划分的基 础上，逐步优化聚类结果，使准则函数达到极值 。 l1C-均值聚类算法（即：均值聚类算法（即：K-均值聚类算法）均值聚类算法） l2ISODATA聚类算法聚类算法 算法要解决的关键问题： v 首先选择有代表性的点作为起始聚合中心。若 类型数目已知，则选择代表点的数目等于类型数 目；若未知，那么聚类过程要形成的类型数目， 就是一个值得研究的问题。 v 代表点选择好之后，如何把所有样本区分到 以代表点为初始聚合中心的范围内，形成初始划 分，是算法的另一个关键问题。 1C-均值聚类算法均值聚类算法 lC-均值聚类算法使用的聚类准则函数是误差平方 和准则 ： 为了使聚类结果优化，应

7、该使准则 最小化。 c J c j n k jkc j mxJ 11 2 | c J （1）C均值算法（一）均值算法（一） （1）C均值算法（一）均值算法（一） （1）C均值算法（一）均值算法（一） （1）C均值算法（一）均值算法（一） （1）C均值算法（一）均值算法（一） （1）C均值算法（一）均值算法（一） 算法特点： l 每次迭代中都要考查每个样本的分类是否正 确，若不正确，就要调整，在全部样本调整完之 后，再修改聚合中心，进入下一次迭代。如果在 某一个迭代运算中，所有的样本都被正确分类， 则样本不会调整，聚合中心也不会有变化，也就 是收敛了。 l c个初始聚合中心的选择对聚类结果有较大

8、影 响。 在算法迭代过程中，样本分类不断调整，因此 误差平方和 也在逐步减小，直到没有样本调 整为止，此时 不再变化，聚类达到最优。但 是上述算法中没有计算 值，也就是说 不是 算法结束的明显依据。 c J c J c J c J （2）C均值算法（二）均值算法（二） （2）C均值算法（二）均值算法（二） （2）C均值算法（二）均值算法（二） （3） 与与C的关系曲线的关系曲线 c J （3） 与与C的关系曲线的关系曲线 v图中，曲线的拐点A对应着接近最优的c值。 v并非所有的情况都容易找到 -C关系曲线的拐 点，此时c值将无法确定。 c J c J 2ISODATA聚类算法聚类算法 vISO

9、DATA算法：Iterative Self-Organizing Data Analysis Techniques Algorithm，迭代自组织的数 据分析算法。 vISODATA算法特点：可以通过类的自动合并（两 类合一）与分裂（一类分为二），得到较合理的 类型数目c。 具体算法步骤： v 给定控制参数 ：预期的聚类中心数目。 ：每一聚类中最少的样本数目，如果少于此数 就不能作为一个独立的聚类。 ：一个聚类域中样本距离分布的标准差（阈值 ）。 ：两个聚类中心之间的最小距离，如果小于此 数，两个聚类合并。 ：每次迭代允许合并的最大聚类对数目。 ：允许的最多迭代次数。 给定n个混合样本，令 (

10、迭代次数)，预选c个 起始聚合中心， ， 。 K n s c L I 1J )( JZ j cj,.,2 , 1 具体算法步骤： v 计算每个样本与聚合中心距离： 。 若： ，则： 。 把全部样本划分到c个聚合中去，且 表示各子 集 中的样本数目。 v 判断：若 ，则舍去子集 ，返 回。 v 计算修改聚合中心： 。 v 计算类内距离平均值 ： )(,(JZxD jk ,.,2 , 1),(,(min)(,( ,.,2, 1 nkJZxDJZxD jk cj jk ik wx j n j X j D j n k j j k j j JZxD n D 1 )( )(,( 1 cj,.,2 , 1

11、， 具体算法步骤： v 计算类内总平均距离 （全部样本对其相应聚 类中心的总平均距离）： v 判别分裂、合并及迭代运算等步骤。 （a）如迭代运算次数已达I次，即最后一次迭代， 置 ，跳到，运算结束。 （b）如 ，即聚类中心的数目等于或不到规定 值的一半，则转，将已有的聚类分裂。 （c）如迭代运算的次数是偶数，或 ，则不进 行分裂，跳到，若不符合上述两个条件，则进 入，进行分裂处理。 ， 具体算法步骤： v 计算每个聚合的标准偏差向量： 。 每个分量为： 。 表示x的第i个分量， 表示 的第i个分量。d为 维数。 v 求出每个聚合的最大标准偏差分量 ： 。 v 考查 ，若有 ，同时满足以下 两条

12、件之一， （a） ，(样本数目超过规定值一倍 以上)。 （b） 。 具体算法步骤： 则把该集合分为两个新的聚合，聚合中心分别 为 ： 其中： 令： 返回 其中，K的选择很重要，应使 中的样本 到 的距离不同，但又使样本全部在这两个集合 中。 v 计算两两聚合中心间的距离 ： v 比较 与 ，并把 小于 的按递增次序排 队： 为给定的合并参数。 具体算法步骤： v 考查中的不等式，对每一个 ，相应有两个 聚类中心 和 ，假使在同一次迭代中，还没把 和 合并，则把两者合并，合并后中心为： v 若 ，则 ，如果修改给定参数则返回 ，不修改参数返回，否则 ，算法结束。 注意：步为分裂，为合并。 ISODATA算法： ISODATA算法： ISODATA算法： ISODATA算法： ISODATA算法： ISODATA算法： ISODATA算法： ISODATA算法： vISODATA算法中，起始聚合中心的选取对聚类过 程和结果都有较大影响，如果选择的好，则算法收 敛快，聚类质量高。 注意：ISODATA与C-均值