数据挖掘导论完整版中文PPT.ppt

聚类分析 附加的问题与算法 第9章聚类分析 附加的问题与算法 在各种领域 针对不同的应用类型 已经开发了大量聚类算法 在这些算法中没有一种算法能够适应所有的数据类型 簇和应用 事实上 对于更加有效或者更适合特定数据类型 簇和应用的新的聚类算法 看来总是有进一步的开发空间 我们只能说我们已经有了一些技术 对于某些情况运行良好 其原因是 在许多情况下 对于什么是一个好的簇集 仍然凭主观解释 此外 当使用客观度量精确地定义簇时 发现最优聚类问题常常是计算不可行的 比较k均值和DBSCAN DBSCAN和k均值都是将每个对象指派到单个簇的划分聚类算法 但是K均值一般聚类所有对象 而DBSCAN丢弃被它识别为噪声的对象 K均值使用簇的基于原形的概念 而DBSCAN使用基于密度的概念 DBSCAN可以处理不同大小和不同形状的簇 并且不太受噪声和离群点的影响 K均值很难处理非球状的簇和不同大小的簇 当簇具有很不同的密度时 两种算法的性能都很差 K均值只能用于具有明确定义的质心 如均值或中位数 的数据 DBSCAN要求密度定义 基于传统的欧几里得密度概念 对于数据是有意义的 K均值可以用于稀疏的高维数据 如文档数据 DBSCAN通常在这类数据上性能很差 因为对于高维数据 传统的欧几里得密度定义不能很好处理 K均值和DBSCAN的最初版本都是针对欧几里得数据设计的 但是它们都被扩展 以便处理其他类型的数据 DBSCAN不对数据的分布做任何假定 基本k均值算法等价于一种统计聚类方法 混合模型 假定所有的簇都来自球形高斯分布 具有不同的均值 但具有相同的斜方差矩阵 DBSCAN和k均值都寻找使用所有属性的簇 即它们都不寻找可能只涉及某个属性子集的簇 K均值可以发现不是明显分离的簇 即便簇有重叠也可以发现 但是DBSCAN会合并有重叠的簇 K均值算法的时间复杂度是O m 而DBSCAN的时间复杂度是O m2 DBSCAN多次运行产生相同的结果 而k均值通常使用随机初始化质心 不会产生相同的结果 DBSCAN自动地确定簇个数 对于k均值 簇个数需要作为参数指定 然而 DBSCAN必须指定另外两个参数 Eps和MinptsK均值聚类可以看作优化问题 即最小化每个点到最近的质心的误差的平方和 并且可以看作一种统计聚类的特例 DBSCAN不基于任何形式化模型 数据特性 高维性随着维度的增加 体积迅速增加 除非点的个数也随着维度指数增加 否则密度将趋向于0 处理该问题的方法是使用维归约技术规模许多聚类算法对于小规模和中等规模的数据集运行良好 但是不能处理大型数据集稀疏性稀疏数据通常由非对称的属性组成 其中零值没有非零值重要 噪声和离群点非常见点可能严重地降低聚类算法的性能 特别是k均值这样的基于原型的算法另一方面 噪声也可能导致单链等技术合并两个不应当合并的簇 属性和数据集类型属性可能是分类的 标称的或序数的 或定量的 区间的或比率的 二元的 离散的或连续的 不同的近邻性和密度度量适合于不同类型的数据 尺度不同的属性 如高度和重量 可能用不同的尺度度量 这些差别可能严重影响两个对象之间的距离或相似性 从而影响聚类分析的结果 簇特性 数据分布某些聚类技术假定数据具有特定的分布 更具体的说 它们常常假定可以用混合分布对数据建模 其中每个簇对应于一个分布 形状有些簇具有规则的形状 如矩形和球形 但是 更一般地 簇可以具有任意形状 如DBSCAN和单链等技术可以处理任意形状 基于原型的方法和一些层次聚类技术不能进行这样的处理 Chameleon和cure是专门用来处理这一问题的技术 不同大小许多聚类算法 如k均值 当簇具有不同的大小时不能很好的处理不同密度具有很不相同的密度的簇可能对诸如DBSCAN和k均值等算法造成影响基于SNN密度的聚类技术可以处理这个问题无明显分离的簇当簇接触或重叠时 有些聚类技术将应当分开的簇合并 甚至有些发现不同簇的技术随意地将点指派到一个或另一个簇 模糊聚类可以处理这一问题 簇之间的联系在大部分聚类技术中 都不考虑簇之间的联系 如簇的相对位置自组织映射 SOM 是一种在聚类期间直接考虑簇之间联系的聚类技术 子空间簇簇可能只在维 属性 的一个子集中存在 并且使用一个维集合确定的簇可能也使用另一个维确定的簇很不相同 聚类算法的一般特征 次序依赖性对于某些算法 所产生的簇的质量和个数可能因数据处理的次序不同而显著地变化 如SOM非确定性有些算法不是次序依赖的 但是它们每次运行都产生不同的结果 因为它们依赖于需要随机选择的初始化步骤 变换聚类问题到其他领域将聚类问题映射到一个不同的领域 如 基于图的聚类 可伸缩性包含数以百万计对象的数据集并不罕见 而用于这种数据集的聚类算法应当具有线性或接近线性的时间或空间复杂度 对于大型数据集 即使具有O m2 复杂度也是不切实际的 此外 数据集聚类技术不能总是假定数据放在内存 或者数据元素可以随机的访问 这样的算法对于大型数据集是不可行的 参数选择大部分聚类算法需要用户设置一个或多个参数 选择合适的参数值可能是困难的 因此 通常的态度是 参数越少越好 将聚类作为最优化问题处理聚类常常被看作优化问题 将点划分成簇 根据用户指定的目标函数度量 最大化结果簇集合的优良度 如k均值试图发现簇的集合 使得每个点到最近的簇质心距离的平方和最小 基于原型的聚类 模糊聚类使用混合模型的聚类自组织映射 模糊聚类 模糊集合1965年 LotfiZadeh引进模糊集合论 fuzzysettheory 和模糊逻辑 fuzzylogic 作为一种处理不精确和不确定性的方法 简要的说 模糊集合论允许对象以0和1之间的某个隶属度属于一个集合 而模糊逻辑允许一个陈述以0和1之间的确定度为真 传统的集合论和逻辑是对应的模糊集合论和模糊逻辑的特殊情况 它们限制集合的隶属度或确定度或者为0 或者为1 考虑如下模糊逻辑的例子陈述 天空多云 为真的程度可以定义为天空被云覆盖的百分比 例如 天空的50 被云覆盖 则 天空多云 为真的程度是0 5 如果我们有两个集合 多云天 和 非多云天 则我们可以类似地赋予每一天隶属于这两个集合的程度 这样 如果一天25 多云 则它在 多云天 集合中具有0 25的隶属度 而在 非多云天 集合中具有0 75的隶属度 模糊簇假定我们有一个数据点的集合X x1 x2 xm 其中每个点xi是一个n维点 即xi xi1 xi2 xin 模糊簇集C1 C2 Ck是X的所有可能模糊子集的一个子集 这简单地意味着对于每个点xi和每个簇Cj 隶属权值 度 wij已经赋予0和1之间的值 然而 我们还想将以下合理的条件施加在簇上 以确定簇形成模糊伪划分 fuzzypsuedo partition 给定点xi的所有权值之和为1 每个簇Cj以非零权值至少包含一个点 但不以权值1包含所有的点 尽管存在多种模糊聚类 我们只考虑k均值的模糊版本 称作模糊c均值 在聚类文献中 那些不采用簇质心增量更新方法的k均值版本有时称为c均值 模糊c均值算法有时称为FCM算法9 1基本模糊c均值算法选择一个初始模糊伪划分 即对所有的wij赋值Repeat使用模糊伪划分 计算每个簇的质心重新计算模糊伪划分 即wijUntil质心不发生变化 FCM的结构类似于K均值 K均值可以看作FCM的特例 K均值在初始化之后 交替地更新质心和指派每个对象到最近的质心 具体地说 计算模糊伪划分等价于指派步骤 与k均值一样 FCM可以解释为试图最小化误差的平方和 SSE 尽管FCM基于SSE的模糊版本 计算SSE公式 其中cj是第j个簇的质心 而p是确定权值影响的指数 在1和 之间取值初始化通常使用随机初始化 特殊地 权值随机的选取 同时限制与任何对象相关联的权值之和等于1 计算质心公式 模糊质心的定义类似于传统的质心定义 不同之处在于所有点都考虑 并且每个点对质心的贡献要根据它的隶属度加权 更新模糊伪划分公式 如果p 2 则该指数降低赋予离点最近的簇的权值 事实上 随着p趋向于无穷大 该指数趋向于0 而权值趋向于1 k 另一方面 随着p趋向于1 该指数加大赋予离点最近的簇的权值 随着p趋向于1 关于最近簇的隶属权值趋向于1 而关于其他簇的隶属权值趋向于0 这时对应于k均值 例子 三个圆形簇上的模糊c均值 优点与局限性 FCM产生指示任意点属于任意簇的程度的聚类 它比K均值算法计算复杂性高 除此之外 它与k均值算法具有相同的优点和缺点 基于原型的聚类 模糊聚类使用混合模型的聚类自组织映射 使用混合模型的聚类 基于统计模型的聚类 通常 假定数据是由一个统计过程产生的 并且通过找出最佳拟合数据的统计模型来描述数据 其中统计模型用分布和该分布的一组参数描述 混合模型 mixturemodels 它使用若干统计分布对数据建模 每个分布对应于一个簇 而每个分布的参数提供对应于簇的描述 通常用中心和发散描述 算法 估计数据分布 确定分布 一般假设数据取自高斯混合分布 然后 对分布的参数进行估计 利用EM算法进行最大似然估计利用直方图估计分布对分布进行划分 分离 每个分布对应于一个簇 优点和缺点 混合模型比k均值或模糊c均值更一般 因为它可以使用各种类型的分布 利用简单的估计分布的方法 如直方图 可能会错误估计数据的原始分布 导致结果不好 利用复杂的方法 如EM算法 计算复杂性会大大增加 基于原型的聚类 模糊聚类使用混合模型的聚类自组织映射 自组织映射 Kohonen自组织特征映射 SOFM或SOM 是一种基于神经网络观点的聚类和数据可视化技术 尽管SOM源于神经网络 但是它可以表示成一种基于原形的聚类的变形 与其他基于质心的聚类技术一样 SOM的目标是发现质心的集合 并将数据集中的每个对象指派到提供该对象最佳近似的质心 用神经网络的术语 每个质心都与一个神经元相关联 SOM算法 初始化质心 Repeat选择下一个对象确定到该对象最近的质心更新该质心和附近的质心 即在一个特定邻域内的质心Until质心改变不多或超过某个域值指派每个对象到最近的质心 并返回质心和簇 基于密度的聚类 基于网格的聚类子空间聚类DENCLUE 基于网格的聚类 网格是一种组织数据集的有效方法 至少在低维空间中如此 其基本思想是 将每个属性的可能值分割成许多相邻的区间 创建网格单元的集合 每个对象落入一个网格单元 网格单元对应的属性区间包含该对象的值 存在许多利用网格进行聚类的方法 大部分方法是基于密度的 例子 基于网格的算法 定义一个网格单元集将对象指派到合适的单元 并计算每个单元的密度删除密度低于指定的阈值的单元由邻近的稠密单元组形成簇 定义网格单元对于连续属性 定义网格单元相当于连续属性离散化 可将值划分为等宽的区间 等频的区间 使用聚类确定的区间 网格单元的密度定义网格单元密度的自然方法是 定义网格单元的密度为该区域中的点数除以区域的体积 如果使用具有相同体积的网格单元 使得每个单元的点数直接度量单元的密度 邻近的稠密单元组形成簇密度阈值的设定是关键 如图9 10和表9 2 如果密度阈值为9 则大簇的4个部分将丢失 邻近单元 一个二维网格单元有4个还是8个邻接单元 例子 优点与局限性 算法运行速度较快 可达o mlogm 这使得它成为许多聚类算法的基础 如STING GRIDCLUS waveCluster Bang Clustering CLIQUE和MAFIA 网格单元形状选择影响聚类效果 如矩形网格单元不能准确地捕获圆形边界区域的密度 对于高维数据 基于网格的聚类效果较差 密度阈值的选择对算法效果影响较大 基于密度的聚类 基于网格的聚类子空间聚类DENCLUE 迄今为止 所考虑的聚类技术都是使用所有的属性来发现簇 然而 如果仅考虑特征子集 则我们发现的簇可能因子空间不同而很不相同 有两个理由 子空间的簇可能是有趣的 数据关于少量属性的集合可能可以聚类 而关于其余属性是随机分布的 在某些情况下 在不同的维集合中存在不同的簇 例子 考虑记录不同时间 不同商品销售情况的数据集 时间是维 商品是对象 某些商品对于特定的月份集 如夏天 可能表现出类似行为 但是不同的簇可能被不同的月份 维 刻画 CLIQUE算法 CLIQUE ClusteringInQUEst 是系统地发现子空间簇的基于网格的聚类算法 检查每个子空间寻找簇是不现实的 因为这样的子空间的数量是维度的指数 基于密度的簇的单调性 如果一个点集在k维上形成一个基于密度的簇 则相同的点集在这些维的所有可能的子集上也是基于密度的簇的一部分 CLIQUE算法 找出对应于每个属性的一维空间中的所有稠密区域 这是稠密的一维单元的集合 K 2Repeat由稠密的k 1维单元产生所有的候选稠密k维单元删除点数少于域值的单元k k 1Until不存在候选稠密k维单元通过取所有邻接的 高密度的单元的并发现簇使用一小组描述簇中单元的属性值域的不等式概括每一个簇 CLIQUE的优点与局限性 CLIQUE最大特点是 它提供了一种搜索子空间发现簇的有效技术 由于这种方法基于关联分析的先验原理 它的性质能够被很好地解释 CLIQUE能够用一小组不等式概括构成一个簇的单元列表 CLIQUE的局限性与其他基于密度的方法和Apriori算法相同 如 CLIQUE发现的簇可以共享对象 允许簇重叠可能大幅度增加簇的个数 并使得解释更加困难 Apriori具有指数级的复杂度 基于密度的聚类 基于网格的聚类子空间聚类DENCLUE DENCLUE 基于密度聚类的一种基于核的方案 DENCLUE DENsityCLUstEring 是一种基于密度的聚类方法 它用与每个点相关联的影响函数之和对点集的总密度建模 结果总密度函数将具有局部尖峰 并且这些局部尖峰用来以自然的方式定义簇 具体的说 对于每个数据点 一个爬山过程找出与该点相关联的最近的尖峰 并且与一个特定的尖峰 称作局部密度吸引点 localdensityattractor 相关联的所有数据点成为一个簇 如果局部尖峰处的密度太低 则相关联的簇中的点将被视为噪声而丢弃 如果一个局部尖峰通过一条数据点路径与另一个局部尖峰相连接 并且该路径上每个点的密度都高于最小密度阈值 则与这些局部尖峰相关联的簇合并在一起 DENCLUE算法 对数据点占据的空间推导密度函数识别局部最大点 即密度吸引点 通过沿密度增长最大的方向移动 将每个点关联到一个密度吸引点定义与特定的密度吸引点相关联的点构成的簇丢弃密度吸引点的密度小于用户指定阈值的簇合并通过密度大于或等于阈值的点路径连接的簇 核密度估计 核密度估计用函数描述数据的分布 每个点对总密度函数的贡献用一个核函数表示 总密度函数仅仅是与每个点相关联的核函数之核核函数是对称的 并且它的值随到点的距离增加而下降 高斯函数常常用作核函数 DENCLUE的优点与局限性 DENCLUE具有坚实的理论基础 因为它基于统计学发展完善的领域 核密度函数和核密度估计 因此 DENCLUE提供了比其他基于网络的聚类技术和DBSCAN更加灵活 更加精确的计算密度的方法 DBSCAN是DENCLUE的特例 基于核密度函数的方法本质上是计算昂贵的 但DENCLUE使用基于网格的技术来处理该问题 尽管如此 DENCLUE可能比其他基于密度的聚类技术的计算开销更大 DENCLUE具有其他基于密度的方法的优缺点 基于图的聚类 最小生成树聚类OPOSSUMChameleonJarvis Patrick聚类算法基于SNN密度的聚类 稀疏化 m个数据点的m m邻近度矩阵可以用一个稠密图表示 每个节点与其他所有点相连 权值反映邻近性 尽管每个对象与其他每个对象都有某种程度的近邻性 但是对于大部分数据集 对象只与少量对象高度相似 而与大部分其他对象的相似性很弱 这一性质用来稀疏化邻近度图 稀疏化可以这样进行 断开相似度低于指定阈值的边 或仅保留连接到点的k个近邻的边 稀疏化的好处 压缩了数据量可以更好的聚类稀疏化技术保持了对象与最近邻的连接 断开与较远对象的连接 这与最近邻原理一致 对象的最近邻趋向于与对象在同一个类 这降低了噪声和离群点的影响 增强了簇之间的差别 可以使用图划分算法 应当把邻近度图的稀疏化看成使用实际聚类算法之前的初始化步骤 理论上讲 一个完美的稀疏化应当将邻近度图划分成对应于期望簇的连通分支 但实际中这很难做到 很容易出现单条边连接两个簇 或者单个簇被分裂成若干个不相连接的子簇的情况 基于图的聚类 最小生成树聚类OPOSSUMChameleonJarvis Patrick聚类算法基于SNN密度的聚类 最小生成树聚类 minimumspanningtree MST 计算相异度图的最小生成树Repeat断开对应于最大相异度的边 创建一个新的簇Until只剩下单个簇最小生成树聚类是一种基于分裂的层次聚类算法最小生成树聚类可以看作用稀疏化找出簇的方法 基于图的聚类 最小生成树聚类OPOSSUMChameleonJarvis Patrick聚类算法基于SNN密度的聚类 OPOSSUM 使用METIS的稀疏相似度最优划分 OPOSSUM OptimalPartitioningofSparseSimilaritiesUsingMETIS 是一种专门为诸如文档或购物篮数据等稀疏 高维数据设计的聚类技术 与MST一样 它基于邻近度图的稀疏化进行聚类 然而 OPOSSUM使用METIS算法 该算法是专门为划分图设计的 OPOSSUM聚类算法1 计算稀疏化的相似度图2 使用METIS 将相似度图划分成k个不同的分支 簇 所使用的相似性度量是适合于稀疏 高维数据的度量 如扩充的Jaccard度量或余弦度量 METIS图划分程序将稀疏图划分为k个不同的分支 其中k是用户指定的参数 旨在 1 最小化分支之间边的权值 2 实现平衡约束 OPOSSUM使用如下两种约束中的一种 1 每个簇中的对象个数必须粗略相等 或 2 属性值的和必须粗略相等 优点与缺点 OPOSSUM简单 速度快 它将数据划分大小粗略相等的簇 根据聚类的目标这可能看作优点或缺点 基于图的聚类 最小生成树聚类OPOSSUMChameleonJarvis Patrick聚类算法基于SNN密度的聚类 Chameleon Chameleon是一种凝聚聚类技术 它解决前两段提到的问题 它将数据的初始划分与一种新颖的层次聚类方案相结合 这种层次聚类使用接近性和互连性概念以及簇的局部建模 关键思想是 仅当合并后的结果簇类似于原来的两个簇时 这两个簇才应当合并 确定合并哪些簇 相对接近度 relativecloseness RC 是被簇的内部接近度规范化的两个簇的绝对接近度 两个簇合并 仅当结果簇中的点之间的接近程度几乎与原来的每个簇一样 mi和mj分别是簇ci和cj的大小 SEC ci cj 是连接簇ci和cj的边的平均值 SEC ci 是二分簇ci的边的平均权值 相对互连度 relativeinterconnectivity RI 是被簇的内部互连度规范化的两个簇的绝对互连度 如果结果簇中的点之间的连接几乎与原来的每个簇一样强 两个簇合并 其中 EC Ci Cj 是连接簇Ci和Cj的边之和 EC Ci 是二分簇Ci的割边的最小和 EC Cj 是二分簇Cj的割边的最小和 RI和RC可以用多种不同的方法组合 产生自相似性的总量 Chameleon使用的方法是合并最大化RI Ci Cj RC Ci Cj a簇对 其中a值大于1 LimitationsofCurrentMergingSchemes RelativeClosenessschemeswillmerge a and b a b c d Relativeinterconnectivityschemeswillmerge c and d Chameleon算法 构造k 最近邻图使用多层图划分算法划分图Repeat合并关于相对互连性和相对接近性而言 最好地保持簇的自相似性的簇Until不再有可以合并的簇 例子 优点与局限性 Chameleon能够有效地聚类空间数据 即便存在噪声和离群点 并且簇具有不同的形状 大小和密度 Chameleon假定由稀疏化和图划分过程产生的对象组群是子簇 即一个划分中的大部分点属于同一个真正的簇 如果不是 则凝聚层次聚类将混合这些错误 因为它绝对不可能再将已经错误地放到一起的对象分开 这样 当划分过程未产生子簇时 chameleon就有问题 对于高维数据 常常出现这种情况 共享最近邻相似性 SNN sharednearestneighbor 相似度计算 1 找出所有点的k 近邻2 If两个点x和y不是相互在对方的k 最近邻中then3 similarity x y 04 Else5 similarity x y 共享的近邻个数6 Endif SNN相似度由于通过使用共享最近邻的个数考虑了对象的环境 SNN相似度可以处理一个对象碰巧与另一对象相对接近 但属于不同的类 在这种情况下 对象一般不共享许多近邻 并且它们的SNN相似度低 SSN相似度也能处理变密度簇的问题 在低密度区域 对象比高密度区域的对象分开得更远 然而 一对点之间的SNN相似度只依赖于两个对象共享的最近邻的个数 而不是这些近邻之间的相距多远 SNN关于点的密度进行自动缩放 基于图的聚类 最小生成树聚类OPOSSUMChameleonJarvis Patrick聚类算法基于SNN密度的聚类 Jarvis Patrick JP 聚类算法 计算SNN相似度图使用相似度阈值 稀疏化SNN相似度图找出稀疏化的SNN相似度图的连通分支 优点与局限性 因为JP聚类基于SNN相似度概念 它擅长于处理噪声和离群点 并且能够处理不同大小 形状和密度的簇 该算法对高维数据效果良好 尤其擅长发现强相关对象的紧密簇 JP聚类把簇定义为SNN相似度图的连通分支 这样 一个对象集是分裂成两个簇还是作为一个簇留下 可能依赖于一条链 基于SNN密度的聚类 算法 计算SNN相似度图以用户指定的参数Eps和MinPts 使用DBSCANSNN密度的聚类算法比Jarvis Patrick聚类或DBSCAN更加灵活 不象DBSCAN 它可以用于高维数据和簇具有不同密度的情况 不象Jarvis Patrick聚类简单地使用域值 然后取连通分支作为簇 基于SNN密度的聚类使用基于SNN密度和核心点概念的方法 核心点 一个点是核心点 如果在该点给定邻域内的点数超过某个阈值MinPts 边界点 边界点不是核心点 但是它落在一个核心点的邻域内 噪声点是既非核心点 也非边界点的任何点 SNNDensity a AllPointsb HighSNNDensity c MediumSNNDensityd LowSNNDensity 例子 解释该算法处理高维数据能力 SNNClustersofSLP SNNDensityofPointsontheGlobe 41年期间 在2 5度的经纬度网格的每个点上的月平均海平面气压 SLP 优点与局限性 基于SNN密度的聚类的优点与局限性类似于JP聚类 然而 核心点和SNN密度的使用大大增加了该方法的能力和灵活性 可伸缩 一般问题和方法 BIRCHCURE 如果运行时间长得不可接受 或者需要的存储量太大 即使最好的聚类算法也没有多大价值 许多聚类算法所需要的存储量都是非线性的 例如 使用层次聚类 存储需求一般是O m2 类似地 有些聚类算法所需要的计算量也是非线性的 可伸缩性可以通过如下技术实现 多维或空间存取方法 邻近度约束 抽样 划分数据对象 汇总 并行与分布计算 CURE CURE ClusteringUsingREpresentative 是一种聚类算法 它使用各种不同的技术创建一种能够处理大型数据 离群点 具有非球形和非均匀大小的簇的数据的方法 CURE使用簇中的多个代表点来表示一个簇 理论上 这些点捕获了簇的几何形状 具体来说 第一个代表点选择离簇中心最远的点 而其余的点选择离所有已经选取的点最远的点 这样 代表点相对分离 选取的点的个数是一个参数 但是一般取 10效果较好 一旦选定代表点 它们就以因子a向簇中心收缩 这有助于减轻离群点的影响 例如 一个到中心的距离为10个单位的代表点将移动3个单位 对于a 0 7 而到中心距离为1个单位的代表点仅移动0 3个单位 CURE使用一种凝聚层次聚类方案进行实际的聚类 两个簇之间的距离是任意两个代表点 在它们向它们代表点的中心收缩之后 之间的最短距离 如果a 0 它等价于基于质心的层次聚类 a 1时 它与单链层次聚类大致相同 注意 尽管使用层次聚类方案 但是CURE的目标是发现用户指定个数的簇 CURE在聚类过程的两个不同阶段删除离群点 首先 如果一个簇增长缓慢 则这意味它主要由离群点组成 因为根据定义 离群点远离其他点 并且不会经常与其他点合并 在CURE中 离群点删除的第一个阶段一般出现在簇的个数是原来点数的1 3时 第二个离群点删除阶段出现在簇的个数达到K的量级时 此时 小簇又被删除 CURE在最坏情况下复杂度为O m2logm 它不能直接用于大型数据集 因此 CURE使用了两种技术来加快聚类过程 第一种技术是取随机样本 并在抽样的数据点上进行层次聚类 随后是最终扫描 将数据集中剩余的点指派到簇中 在某些情况下 聚类所需要的样本仍然太大 需要第二种技术解决 在这种情况下 CURE划分样本数据 然后聚类每个划分中的点 这种