《模式识别》课件-第6讲数据聚类

PatternRecognition模式识别第6讲

数据聚类

DataClustering样本预处理与特征生成特征降维分类器训练分类决策模式采集无监督有监督半监督聚类PCA聚类的数学定义和特点x2x1聚类是指在模式空间S中，给定N个样本，按照样本间的相似程度，将S划分为k个决策区域Si（i＝1，2，…..，k）的过程，该过程使得各样本均能归入其中一个类，且不会同时属于两个类。即

S1∪S2∪S3∪……∪Sk＝S，Si∩Sj＝0，i≠j聚类的数学定义和特点聚类是指在模式空间S中，给定N个样本，按照样本间的相似程度，将S划分为k个决策区域Si（i＝1，2，…..，k）的过程，该过程使得各样本均能归入其中一个类，且不会同时属于两个类。即

S1∪S2∪S3∪……∪Sk＝S，Si∩Sj＝0，i≠j没有预先分好类的样本集没有已知的分类决策规则由待分类样本特征的内在规律来驱动分类过程特点一：数据聚类是典型的无监督学习受特征选取和聚类准则的影响受相似度度量标准的影响受各特征量纲标尺的影响特点二：聚类结果多样化归一化聚类的流程选定特征确定相似度设定聚类准则选择聚类算法聚类结果评估聚类任务的需求对聚类的有效性维度和算法效率样本间的相似度：距离和非距离类别间的相似度紧致性准则散布准则误差平方和准则分布形式准则试探法层次法迭代法（动态）密度法各类别统计分布合理性发现和适配样本集的统计分布孤立样本或边界样本数量人工干预的强弱利于发现分类规则和决策边界试探聚类算法设定初始聚类中心处理一个样本需要建立新类别吗？处理完所有样本了吗？归入已有类别建立新的类别是否是否设定阈值T和初始聚类中心处理一个样本xixi到已有聚类中心距离都大于T？处理完所有样本了吗？以最近邻规则将xi归入已有类别以xi为聚类中心建立新的类别是否是否最近邻聚类试探聚类算法设定初始聚类中心处理一个样本需要建立新类别吗？处理完所有样本了吗？归入已有类别建立新的类别是否是否最大最小距离聚类设定初始聚类中心zi将距zi最远的样本作为第2个聚类中心z2，并将zi和z2之间的距离设为D12max(Dmin)>θD12以最近邻规则将所有样本归入到已有聚类中心代表的类别中取对应样本建立新的聚类中心是否计算剩余一个样本到现有所有聚类中心的距离中的最小值Dmin计算所有样本的Dmin中的最大值max(Dmin)层次聚类算法按聚类类别数，组成一棵二叉树每次分叉都追求紧致性最好的聚类结果类别数确定时的聚类结果：水平截取层次聚类树类别数不确定时的最优聚类结果：紧致性最好的那个层次x2x1x6x3x4x51个类2个类3个类4个类6个类5个类层次聚类算法融合算法流程：（1）对于含n个样本的样本集，先令每个样本自成一类，总分类数k=n；（2）计算类间距离，将距离最小（最相似）的两个类合并，总分类数减少为k=n-1；（3）继续合并类，直至总分类数k或类间距离Dij满足要求。

12345678910

层次聚类算法分解算法流程：（1）对于含n个样本的样本集，先将所有样本作为一类，总分类数k=1；（2）将已得到的类分成两类，计算类间距离，将类间距离最大（最不相似）的分类方法作为本级分类结果，总分类数增加为k=2；（3）对每一个得到的类再分类，直至总分类数k或类间距离Dij满足要求。

12345678910

层次聚类算法

12345678910融合算法分解算法动态（迭代）聚类算法设定初始聚类中心完成样本集聚类准则函数取得极值？聚类结束调整聚类中心是否设定k个初始聚类中心使用最近邻规则完成所有样本的聚类聚类中心与上次有变化？聚类结束是否计算每一类的均值，并作为新的聚类中心k-均值聚类动态（迭代）聚类算法ISODATA聚类初始化设定控制参数选定初始聚类中心各类重心类内平均距离总平均距离样本分类某类中样本数