模式识别-第3章 聚类分析.ppt

聚类分析 主要内容： 什么是聚类？ 如何度量样本间的“相似性”。 如何构建聚类准则函数。 基本的聚类方法。 什么是聚类（Clustering）？ 根据某种“相似度”（similarity），将数据分成不同种类。 聚类和分类有什么不同？ 聚类有什么用？ 文本聚类 数据挖掘 图像分割 多标准样本学习 图象分割 聚类中的两个关键问题 对称性： 常用的距离函数 欧氏距离：(Eucidean Distance) 常用的距离函数 街市距离： （Manhattan/city block/taxicab distance） 常用的距离函数 明氏距离：(Minkowski Distance) 仅当 时，明氏距离具有旋转平移不变性 常用的距离函数 马氏距离：(Mahalanobis Distance) 角度相似函数：(Angle Distance) 聚类中的两个关键问题 误差平方和准则 将样本分成K个子集D1, …, DK，Nk为第k个子集的样本数，mk为样本均值： 误差平方和准则： 聚类算法需要考虑的问题（一） 准则函数的选择 聚类算法需要考虑的问题（二） 特征量纲的影响（缩放坐标轴） 误差平方和准则适用范围： 数据点能划分成能很好区分的几类。 类内数据稠密 各类样本数量差异不大 散布准则 第i类内散布矩阵： 类内散布矩阵： 类间散布矩阵： 总体散布矩阵： 散布准则 基于迹的准则： 散布准则 基于行列式的散布准则： 基于不变量的散布准则： 准则函数的优化 穷举法优化：聚类准则函数的优化是组合最优问题，是一个NP难题，将n个样本分到c个类别有cn/c!种分法，穷举计算是不现实的，只能寻找次优方法解决； 迭代最优化：随机设置初始聚类，计算将样本x从Di聚类移到Dj聚类是否能够使准则函数减小，减小则做此修改，否则不修改。 聚类分析 简单聚类法 层次聚类法 动态聚类法 一、简单聚类法（试探法） 优点：计算比较简单。 缺点：对初始的第一个聚类中心的选择依赖性比较强。聚类效果还要受到阈值T的影响。 实际问题中，需要对不同的初始聚类中心和不同的阈值进行试探，直到得到一个满意的聚类结果为止。 2，最大最小距离算法： 基本思想：在样本集中以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。 二，合并法层次聚类法，Hierarchical Clustering  基本思路：首先每一个样本自成一类，然后按照距离准则逐步合并，类别数由多到少，达到合适的类别数为止。 已知：N个待识模式{x1，x2，…，xN}，类别数c。 第一步 建立N个初始类别，每个样本一个类别，计算距离矩阵D=(Dij)； 第二步 寻找D中的最小元素，合并相应的两个类别，建立新的分类，重新计算距离矩阵D； 重复第二步，直到类别数为c为止。 类与类之间相似性度量 最短距离： 层次聚类的特点 层次聚类不用初始化聚类中心，因此聚类结果不受初始聚类中心的影响； 需要定义类别之间的相似性度量； 当样本数较多时，算法的计算量大。 聚类结果是对平方误差准则函数的贪心优化结果。 三、动态聚类法（修改法） 首先选择若干个样本点作为聚类中心，然后按照某种聚类准则使各样本点向各个中心聚集，从而得到初始分类； 然后判断初始分类是否合理，如果不合理，则修改聚类中心，反复进行修改，直到分类合理为止。 动态聚类有多种算法，其中比较著名： K -均值算法和ISODATA 算法。 K-均值算法 第一步：任选K个初始聚类中心； k-均值聚类的特点 k-均值算法可以看作是对平方误差准则函数的贪心有哪些信誉好的足球投注网站算法； 聚类结果受初始聚类中心的选择影响很大，不同的初始聚类中心会导致不同的聚类结果。 小结 什么是聚类？根据某种“相似度”，将数据分成不同种类。 聚类的两个关键问题：度量样本间的“相似性”、构建聚类准则函数。 常用的样本相似性“距离”：街市、欧氏、明氏、马氏。 常用的准则函数：误差平方和准则、散布准则 基本的聚类方法：简单聚类法、层次聚类法、动态聚类法（k均值） 最长距离： 平均距离： 为第i 类中所有样本与第j 类中所有样本之间距离的最小值 为第i 类中所有样本与第j 类中所有样本之间距离的最大值 第四步：检验新的聚类中心与旧的聚类中心是否相等，相等则算法结束；否则转第二步； 第二步：将每一个 待分类样本分到K 个类别中。 第三步：计算各类的聚类中心； 1 2 3 4 * * 类别数 K = 2 通过标签推测相似性 通过相似性推测标签 给出标签（Labels ） 给出/构造相似性测度（Similarity measure ） 分类（Classification） 聚类（Clustering） 收集并标记大型样本集非常