第七讲 数据聚类(讲义).docVIP

第七讲 数据聚类 数据聚类的基本概念 数据聚类的定义： 聚类是指在模式空间S中，给定N个样本，按照样本间的相似程度，将S划分为k个决策区域Si（i＝1，2，…..，k）的过程，该过程使得各样本均能归入其中一个类，且不会同时属于两个类。 即 S1∪S2∪S3∪……∪Sk＝S， Si∩Sj＝0，i≠j 聚类Clustering； 聚类分析：Clustering Analysis 讨论： 聚类是对整个样本集的划分，而不是对单个样本的识别； 聚类的依据是“样本间的相似程度”； 聚类结果是“无遗漏”、“无重复”的。 数据聚类的特点： 特点一：聚类是典型的无监督学习 没有预先分好类的样本集 没有已知的分类决策规则 由待分类样本特征的内在规律来驱动分类过程 特点二：聚类结果多样化 受特征选取和聚类准则的影响 受相似度度量标准的影响 受各特征量纲标尺的影响 数据聚类的应用： （1）数据聚类的应用目标 获得初始的训练样本集，启动分类器的设计 揭示样本间的内在联系，获得数据中隐藏的知识和规律 对样本集中的大量样本进行合并和删减，以降低问题的复杂度 （2）数据聚类的具体应用领域 思考题：你能找到数据聚类在社会生活中的更多应用实例吗？ 数据聚类的完整过程 选取特征 聚类任务的需求 特征对聚类的有效性 维度和算法效率 （2）确定相似性度量标准 样本间的相似度 绝对值距离： 欧几里德距离： 明考夫斯基距离 切比雪夫距离 非距离相似度 绝对值距离：Dab＝1.5，Dac=2，Dbc=3.5； 欧几里德距离：Dab＝1.5，Dac=1.414，Dbc=2.693； 切比雪夫距离：Dab＝1.5，Dac=1，Dbc=2.5； 类间的相似度 最短距离：两类中相距最近的两样本间的距离。 最长距离：两类中相距最远的两样本间的距离。 重心距离：两类的均值点（重心）间的距离。 类平均距离：两类中各个元素两两之间的距离相加后取平均值 （3）设定聚类准则 紧致性准则：概念性的基本准则 误差平方和准则：几何准则，可计算简单，但与紧致性要求不完全一致 散布准则：类内散布矩阵和类间散布矩阵，能更好地表示样本分布 分布形式准则：不仅考虑紧致性，而且考虑各类别应具有相同的分布形式 选择聚类算法 试探法：直接算法，对每个样本至少处理一次； 层次法：按照层次完成聚类树； 迭代法：根据准则函数动态调整聚类结果，直至达到最优； 密度法：以样本分布密度的变化来完成聚类，使得围绕一个密度中心的样本聚到一个类中。 对聚类结果进行评价 聚类得到的各个类别分布是否合理 聚类结果是否能发现和适应样本集的样本分布特点； 是否存在大量的孤立样本或边界样本 聚类过程是否需要大量的人工干预 聚类后是否是否可以发现样本集中的分类规则，建立决策边界 基于试探的聚类算法 基本算法思路： 设定初始的聚类中心； 依次处理各样本； 按照某种聚类准则，将样本归入已有类别，或者建立新的类别； 完成全部数据聚类 优点：简单快速 缺点：对初始条件敏感，聚类顺序影响聚类结果，需要分类的先验知识，聚类结果需进行评估 2、基于最近邻规则的聚类算法 （1）选取阀值T，并任取一个样本作为初始聚类中心，如Z1＝X1； （2）取下一个样本X2，计算X2到Z1的距离D21； 若D21=T，则将X2归入以Z1为中心的类， 若D21T，则将X2作为新的类的聚类中心Z2； （3）继续取样本Xi，分别计算Xi到Zj（j＝1，…，k）的距离Dij， 如DijT， （j＝1，…，k），则将Xi作为第k+1个聚类中心Z k+1; 否则，将Xi归入距离最近的聚类中心所属的类中。 （4）以此类推，直至全部样本分到正确的模式类中。 分类结果受下列因素的影响： 第一个聚类中心的选择 待分类模式样本的排列顺序 阈值T的大小 样本分布的几何性质 3、最大最小距离聚类算法： （1）任取一个样本作为第一个聚类中心，如Z1＝X1； （2）计算其余样本到Z1的距离Di1，取Di1最大的样本为第二个聚类中心Z2； （3）计算其余样本到Z1，Z2的距离Di1，Di2，即 Di1＝ || Xi – Z1 ||,Di2＝ || Xi – Z2 ||, 取其最小值Min（Di1,Di2）； （4）若剩余各样本到已有聚类中心的最小距离中的最大值满足：（0 θ1，通常取1/2） Max{Min(Di1,Di2)，i＝1，2，…N-2}θ|| Z1 - Z2 ||； 则取对应样本为第三个聚类中心Z3 （5）若有Z3存在，则进一步计算余下各模式与三个中心的最小距离，并求 Max{Min(Di1，Di2，Di3)，i＝1，2，…N-3}θ||