1、遥感影像识别遥感影像识别第三章第三章: 聚类分析聚类分析 Part 3-1 相似性准则相似性准则 3-2 聚类准则函数聚类准则函数 3-3 两种简单的聚类算法两种简单的聚类算法 3-4 动态聚类算法动态聚类算法 3-5 聚类的评价聚类的评价课堂回顾课堂回顾v广义线性判别函数广义线性判别函数 x yv非线性判别函数非线性判别函数 分段线性判别函数：距离均值分段线性判别函数：距离均值 二次判别函数：判别方程二次判别函数：判别方程课堂回顾课堂回顾v聚类分析符合聚类分析符合“物以类聚，人以群分物以类聚，人以群分“的原则的原则，它把相似性大的样本聚集为一个类型，在，它把相似性大的样本聚集为一个类型，在特
2、征空间里占据着一个局部区域。每个局部特征空间里占据着一个局部区域。每个局部区域都形成一个聚合中心，聚合中心代表相区域都形成一个聚合中心，聚合中心代表相应类型。应类型。 v相似性准则相似性准则:包括距离相似性度量和角度相似包括距离相似性度量和角度相似性度量。性度量。v距离相似性度量：欧氏距离、马氏距离、明距离相似性度量：欧氏距离、马氏距离、明氏距离。氏距离。diiieyxyxyxD12|),(课堂回顾课堂回顾v在样本相似性度量的基础上，聚类分析还需要在样本相似性度量的基础上，聚类分析还需要一定的准则函数，才能把真正属于同一类的样一定的准则函数，才能把真正属于同一类的样本聚合成一个类型的子集，而把
3、不同类的样本本聚合成一个类型的子集，而把不同类的样本分离开来。分离开来。v聚类准则函数聚类准则函数:包括误差平方和准则、加权平包括误差平方和准则、加权平均平方距离和准则、类间距离和准则。均平方距离和准则、类间距离和准则。v误差平方和准则（最常用）：误差平方和准则（最常用）：cjnkjkcjmxJ112|课后思考课后思考v线性判别函数的适用性？v聚类分析的优缺点？v ERDAS image Model 工具如何实现聚类？ 3-3 两种简单的聚类算法两种简单的聚类算法v本节介绍两种简单的聚类分析方法，它是对某些关键性的元素进行试探性的选取，使某种聚类准则达到最优，又称为基于试探的聚类算法基于试探的
4、聚类算法。 v采用最近邻规则的聚类算法v最大最小距离聚类算法1. 采用最近邻规则的聚类算法采用最近邻规则的聚类算法 假设已有混合样本集 ，按照最近邻原则进行聚类，算法如下： l选取距离阈值 ，并且任取一个样本作为第一个聚合中心 ，如： 。 l计算样本 到 的距离 ： ,.,21nxxxX T1Z11xZ2x1Z21Dl按照某种聚类准则考察聚类结果，若不满意，则重新选取距离阈值 、第一个聚合中心 ，返回，直到满意，算法结束。l在样本分布一定时，该算法的结果在很大程度上取决于第一个聚合中心的选取和距离阈值的大小。 p66l该算法的优点是简单，如果有样本分布的先验知识用于指导阈值和起始点的选取，则可
5、较快得到合理结果。对于高维的样本集来说，则只有经过多次试探，并对聚类结果进行验算，从而选择最优的聚类结果。 T1Z2. 最大最小距离聚类算法最大最小距离聚类算法 该算法以欧氏距离为基础，除首先辨识最远的聚类中心外，与上述算法相似。用一个例子说明该算法。 以类间欧式距离最大作为选择聚类中心的条件。v 3-4 动态聚类算法动态聚类算法l在聚类分析中，动态聚类法是较普遍采用的方法，该算法首先选择某种样本相似性度量和适当的聚类准则函数，使用迭代算法，在初始划分的基础上，逐步优化聚类结果，使准则函数达到极值。l1C-均值聚类算法（即：均值聚类算法（即：K-均值聚类算法）均值聚类算法）l2ISODATA聚
6、类算法聚类算法 算法要解决的关键问题：v 首先选择有代表性的点作为起始聚合中心。若类型数目已知，则选择代表点的数目等于类型数目；若未知，那么聚类过程要形成的类型数目，就是一个值得研究的问题。v 代表点选择好之后，如何把所有样本区分到以代表点为初始聚合中心的范围内，形成初始划分，是算法的另一个关键问题。 1C-均值聚类算法均值聚类算法lC-均值聚类算法使用的聚类准则函数是误差平方和准则 ： 为了使聚类结果优化，应该使准则 最小化。 cJ cjnkjkcjmxJ112|cJ （1）C均值算法（一）均值算法（一） （1）C均值算法（一）均值算法（一） （1）C均值算法（一）均值算法（一） （1）C均
7、值算法（一）均值算法（一） （1）C均值算法（一）均值算法（一） （1）C均值算法（一）均值算法（一） 算法特点：l 每次迭代中都要考查每个样本的分类是否正确，若不正确，就要调整，在全部样本调整完之后，再修改聚合中心，进入下一次迭代。如果在某一个迭代运算中，所有的样本都被正确分类，则样本不会调整，聚合中心也不会有变化，也就是收敛了。l c个初始聚合中心的选择对聚类结果有较大影响。 在算法迭代过程中，样本分类不断调整，因此误差平方和 也在逐步减小，直到没有样本调整为止，此时 不再变化，聚类达到最优。但是上述算法中没有计算 值，也就是说 不是算法结束的明显依据。 cJcJcJcJ （2）C均值算法
8、（二）均值算法（二） （2）C均值算法（二）均值算法（二） （2）C均值算法（二）均值算法（二） （3） 与与C的关系曲线的关系曲线cJ （3） 与与C的关系曲线的关系曲线v图中，曲线的拐点A对应着接近最优的c值。v并非所有的情况都容易找到 -C关系曲线的拐点，此时c值将无法确定。cJcJ2ISODATA聚类算法聚类算法vISODATA算法：Iterative Self-Organizing Data Analysis Techniques Algorithm，迭代自组织的数据分析算法。vISODATA算法特点：可以通过类的自动合并（两类合一）与分裂（一类分为二），得到较合理的类型数目c。 具
9、体算法步骤：v 给定控制参数 ：预期的聚类中心数目。 ：每一聚类中最少的样本数目，如果少于此数就不能作为一个独立的聚类。 ：一个聚类域中样本距离分布的标准差（阈值）。 ：两个聚类中心之间的最小距离，如果小于此数，两个聚类合并。 ：每次迭代允许合并的最大聚类对数目。 ：允许的最多迭代次数。 给定n个混合样本，令 (迭代次数)，预选c个起始聚合中心， ， 。KnscLI1J)( JZjcj,.,2 , 1 具体算法步骤：v 计算每个样本与聚合中心距离： 。 若： ，则： 。 把全部样本划分到c个聚合中去，且 表示各子集 中的样本数目。v 判断：若 ，则舍去子集 ，返回。v 计算修改聚合中心： 。v
10、 计算类内距离平均值 ： )(,(JZxDjk,.,2 , 1),(,(min)(,(,.,2, 1nkJZxDJZxDjkcjjkikwx jnjXjDjnkjjkjjJZxDnD1)()(,(1cj,.,2 , 1， 具体算法步骤：v 计算类内总平均距离 （全部样本对其相应聚类中心的总平均距离）：v 判别分裂、合并及迭代运算等步骤。 （a）如迭代运算次数已达I次，即最后一次迭代，置 ，跳到，运算结束。 （b）如 ，即聚类中心的数目等于或不到规定值的一半，则转，将已有的聚类分裂。 （c）如迭代运算的次数是偶数，或 ，则不进行分裂，跳到，若不符合上述两个条件，则进入，进行分裂处理。 ， 具体算
11、法步骤：v 计算每个聚合的标准偏差向量： 。 每个分量为： 。 表示x的第i个分量， 表示 的第i个分量。d为维数。v 求出每个聚合的最大标准偏差分量 ： 。v 考查 ，若有 ，同时满足以下两条件之一， （a） ，(样本数目超过规定值一倍以上)。 （b） 。 具体算法步骤： 则把该集合分为两个新的聚合，聚合中心分别 为： 其中： 令： 返回 其中，K的选择很重要，应使 中的样本 到 的距离不同，但又使样本全部在这两个集合中。v 计算两两聚合中心间的距离 ： v 比较 与 ，并把 小于 的按递增次序排队： 为给定的合并参数。 具体算法步骤：v 考查中的不等式，对每一个 ，相应有两个聚类中心 和
12、，假使在同一次迭代中，还没把 和 合并，则把两者合并，合并后中心为： v 若 ，则 ，如果修改给定参数则返回，不修改参数返回，否则 ，算法结束。 注意：步为分裂，为合并。 ISODATA算法： ISODATA算法： ISODATA算法： ISODATA算法： ISODATA算法： ISODATA算法： ISODATA算法： ISODATA算法： vISODATA算法中，起始聚合中心的选取对聚类过程和结果都有较大影响，如果选择的好，则算法收敛快，聚类质量高。 注意：ISODATA与C-均值算法的异同点： 都是动态聚类算法。 C-均值简单，ISODATA复杂。 C-均值中，类型数目固定，ISODATA中， 类型数目可变。 ISODATA算法流程框图如下图所示： 3-5 聚类的评价聚类的评价l聚类几何分布的显示l 图表分析 各聚类中心间的距离 各聚类域中样本数目的分析 各聚类域样本方差的分析l 屏幕显示与实地抽样检核l 借助有关文献、图件和已有成果评价聚类结果谢 谢！
