第6章聚类分析 本章目标 ◆辨别类有不同表示法和相似度的不同量度标 准。 ◆比较凝聚聚类和分区聚类算法的基本特征 ◆用相似度的单链接或全链接度量标准实现凝 聚算法。 推导分区聚类的K平均法并分析其复杂性 ◇解释增量聚类算法的实现和它的优缺点
第6章 聚类分析 本章目标 ◆辩别类有不同表示法和相似度的不同量度标 准。 ◆比较凝聚聚类和分区聚类算法的基本特征。 ◆用相似度的单链接或全链接度量标准实现凝 聚算法。 ◆推导分区聚类的K-平均法并分析其复杂性。 ◆解释增量聚类算法的实现和它的优缺点
◆聚类分析是依据样本间关联的量度标 准将其自动分成几个群组,且使同 群组内的样本相似,而属于不同群组 的样本相异的一组方法。聚类分析的 附加的结果是对每个类的综合描 述,这种结果对于更进一步深入分析 数据集的特征是尤其重要
◆聚类分析是依据样本间关联的量度标 准将其自动分成几个群组，且使同一 群组内的样本相似，而属于不同群组 的样本相异的一组方法。聚类分析的 一个附加的结果是对每个类的综合描 述，这种结果对于更进一步深入分析 数据集的特征是尤其重要
61聚类概 聚类的样本是用度量指标的一个向量表示或 更正式的说法是用多维空间的一个点来表示 同类中的样本比属于不同类的样本彼此具有 更高的相似性。聚类方法尤其适合用来探讨 样本间的相互关联关系从而对一个样本结构 做一个初步的评价。人们能够对一维、二维 或三维的样本进行聚类分析,但是大多数现 实问题涉及到更高维的聚类
6.1 聚类概念 ◆聚类的样本是用度量指标的一个向量表示,或 更正式的说法是,用多维空间的一个点来表示。 同类中的样本比属于不同类的样本彼此具有 更高的相似性。聚类方法尤其适合用来探讨 样本间的相互关联关系从而对一个样本结构 做一个初步的评价。人们能够对一维、二维 或三维的样本进行聚类分析，但是大多数现 实问题涉及到更高维的聚类
◆例如:下表是一个简单聚类例子,包含了9个 顾客的信息,分三类,两个特征值(数量价 格) 类1:购少量高价商品,类2:购大量的高价品, 表6-1包含相似对象的类的样本集 商品的数量 价格 2000 2300 1800 类2 12 ;:4…;:2100 2500 士地0: 类3 2004 ::小:19m9:3501
◆例如：下表是一个简单聚类例子，包含了9个 顾客的信息，分三类，两个特征值(数量,价 格) 类1:购少量高价商品，类2：购大量的高价品， 类3：购小量的低价商品
聚类是一个非常难的问题因为在一个n维的 样本空间数据可以以不同的形状和大小揭示 类。 ◆下面基于欧几里得二维空间的聚类过程的 个示例。 初始数据 b)数据的三个类 数据的四个类 图6-1二维空间的点的聚类分析
◆聚类是一个非常难的问题,因为在一个n维的 样本空间数据可以以不同的形状和大小揭示 类。 ◆下面基于欧几里得二维空间的聚类过程的一 个示例
上面数据可以分类三个类也可以分为四个类, 类的数量的任意性是聚类过程中的主要问题。 ◆另一方面,上面的类是能够直接观察到的。 对于高维欧几里得空间里的组点,就无法 从视觉上观察到 ◆聚类分析输入可以用一组有序数对(X,s减或 (×,d)表示。聚类系统的输出是一个分区 N,其中Gk(k=1N)是 的子集。 GG G称为类,每一个类用一些特征 描述。聚类结果是类和它的特征或描述
◆上面数据可以分类三个类也可以分为四个类， 类的数量的任意性是聚类过程中的主要问题。 ◆另一方面，上面的类是能够直接观察到的。 对于高维欧几里得空间里的一组点，就无法 从视觉上观察到。 ◆ 聚类分析输入可以用一组有序数对(X,s)或 (X,d)表示。聚类系统的输出是一个分区 ∧={G1 ,G2 ,…,GN}，其中Gk (k=1,…,N)是 X的子集。 ◆ G1 ,G2 ,…,GN称为类，每一个类用一些特征 描述。聚类结果是类和它的特征或描述
◆规范化的描述有以下几种图式 1通过它们的重心或类中关系远的(边界) 点表示n维空间的一类点 2.使用聚类树中节点图形化地表示一个类 3使用样本属性的逻辑表达式表示类。 XX x12 C: X X·C C2X1≥2∧X2x5 C3:X≥2∧X25 a)重心 b)聚类树 c)逻辑表达 图62聚类表达的不同示范
◆规范化的描述有以下几种图式： 1.通过它们的重心或类中关系远的（边界） 点表示n维空间的一类点。 2. 使用聚类树中节点图形化地表示一个类。 3.使用样本属性的逻辑表达式表示类
◆现有的用于数据挖掘的聚类方法分为 四类分割法分层法密度法和网格法。 ◆分割聚类法一般是通过优化一个评价 函数把数据分割成K个部分,主要有两 种方法:K- means聚类法和K medoid聚类法K- means法在处理海 量数据库方面很有效,特别是对数值 属性处理。K prototypes是 K means和 K-modiod的优点,可以同 时处理数值与符号属性和聚类法
◆现有的用于数据挖掘的聚类方法分为 四类:分割法,分层法,密度法和网格法。 ◆分割聚类法一般是通过优化一个评价 函数把数据分割成K个部分，主要有两 种方法：K-means聚类法和Kmedoid聚类法.K-means法在处理海 量数据库方面很有效，特别是对数值 属性处理。K-prototypes是结合Kmeans和K-modiod的优点，可以同 时处理数值与符号属性和聚类法
◆分层聚类法是由不同层次的分割聚类 组成,层次之间的分割具有嵌套关系 分层聚类法不必事先输入娶类块数 基于模糊相似关系的模糊聚类属于这 种聚类法。 ◆密度聚类法是利用数据密度函数进行 聚类 ◆网格聚法利用空间量子化方法把数据 分到有限个单元进行聚类,这种方法 效率高,与数据大小无关,仅与单元 数有关
◆分层聚类法是由不同层次的分割聚类 组成，层次之间的分割具有嵌套关系。 分层聚类法不必事先输入聚类块数K， 基于模糊相似关系的模糊聚类属于这 种聚类法。 ◆密度聚类法是利用数据密度函数进行 聚类。 ◆网格聚法利用空间量子化方法把数据 分到有限个单元进行聚类，这种方法 效率高，与数据大小无关，仅与单元 数有关
◆值得注意的是:没有哪一种聚类技术对揭示 多维数据集中的构造种类是普遍适用的。使 用者对问题的理解和与其相应的数据类型是 选择合适方法的最好标准,大多数聚类算法 基于下面两种常见方法 1层次聚类 2迭代的平方误差分区聚类 ◇层次方法按群组的嵌套顺序组织数据,以树 状图或树形结构来表示。 ◇平方误差分区算法试图得到一个使类内分 最小而类间分散最大的分区。它是非层次的
◆值得注意的是：没有哪一种聚类技术对揭示 多维数据集中的构造种类是普遍适用的。使 用者对问题的理解和与其相应的数据类型是 选择合适方法的最好标准，大多数聚类算法 基于下面两种常见方法： 1.层次聚类 2.迭代的平方误差分区聚类 ◆层次方法按群组的嵌套顺序组织数据，以树 状图或树形结构来表示。 ◆平方误差分区算法试图得到一个使类内分散 最小而类间分散最大的分区。它是非层次的