第9章附加问题与算法.ppt

《第9章附加问题与算法.ppt》由会员分享，可在线阅读，更多相关《第9章附加问题与算法.ppt（109页珍藏版）》请在三一文库上搜索。

1、聚类分析：附加的问题与算法,第9章 聚类分析：附加的问题与算法,在各种领域，针对不同的应用类型，已经开发了大量聚类算法。在这些算法中没有一种算法能够适应所有的数据类型、簇和应用。 事实上，对于更加有效或者更适合特定数据类型、簇和应用的新的聚类算法，看来总是有进一步的开发空间。 我们只能说我们已经有了一些技术，对于某些情况运行良好。其原因是，在许多情况下，对于什么是一个好的簇集，仍然凭主观解释。此外，当使用客观度量精确地定义簇时，发现最优聚类问题常常是计算不可行的。,比较k均值和DBSCAN,DBSCAN和k均值都是将每个对象指派到单个簇的划分聚类算法，但是K均值一般聚类所有对象，而DBSCAN

2、丢弃被它识别为噪声的对象。 K均值使用簇的基于原形的概念，而DBSCAN使用基于密度的概念。 DBSCAN可以处理不同大小和不同形状的簇，并且不太受噪声和离群点的影响。K均值很难处理非球状的簇和不同大小的簇。当簇具有很不同的密度时，两种算法的性能都很差。,K均值只能用于具有明确定义的质心（如均值或中位数）的数据。DBSCAN要求密度定义（基于传统的欧几里得密度概念）对于数据是有意义的。 K均值可以用于稀疏的高维数据，如文档数据，DBSCAN通常在这类数据上性能很差，因为对于高维数据，传统的欧几里得密度定义不能很好处理。 K均值和DBSCAN的最初版本都是针对欧几里得数据设计的，但是它们都被扩展

3、，以便处理其他类型的数据。,DBSCAN不对数据的分布做任何假定。基本k均值算法等价于一种统计聚类方法（混合模型），假定所有的簇都来自球形高斯分布，具有不同的均值，但具有相同的斜方差矩阵。 DBSCAN和k均值都寻找使用所有属性的簇，即它们都不寻找可能只涉及某个属性子集的簇。 K均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN会合并有重叠的簇。 K均值算法的时间复杂度是O（m），而DBSCAN的时间复杂度是O（m2）.,DBSCAN多次运行产生相同的结果，而k均值通常使用随机初始化质心，不会产生相同的结果。 DBSCAN自动地确定簇个数；对于k均值，簇个数需要作为参数指定

4、。然而，DBSCAN必须指定另外两个参数：Eps和Minpts K均值聚类可以看作优化问题，即最小化每个点到最近的质心的误差的平方和，并且可以看作一种统计聚类的特例。DBSCAN不基于任何形式化模型。,数据特性,高维性 随着维度的增加，体积迅速增加，除非点的个数也随着维度指数增加，否则密度将趋向于0. 处理该问题的方法是使用维归约技术 规模 许多聚类算法对于小规模和中等规模的数据集运行良好，但是不能处理大型数据集 稀疏性 稀疏数据通常由非对称的属性组成，其中零值没有非零值重要。.,噪声和离群点 非常见点可能严重地降低聚类算法的性能，特别是k均值这样的基于原型的算法 另一方面，噪声也可能导致单链

5、等技术合并两个不应当合并的簇。 属性和数据集类型 属性可能是分类的（标称的或序数的）或定量的（区间的或比率的），二元的、离散的或连续的。 不同的近邻性和密度度量适合于不同类型的数据。 尺度 不同的属性，如高度和重量，可能用不同的尺度度量。这些差别可能严重影响两个对象之间的距离或相似性，从而影响聚类分析的结果。,簇特性,数据分布 某些聚类技术假定数据具有特定的分布。更具体的说，它们常常假定可以用混合分布对数据建模，其中每个簇对应于一个分布。 形状 有些簇具有规则的形状，如矩形和球形。但是，更一般地，簇可以具有任意形状。 如DBSCAN和单链等技术可以处理任意形状。基于原型的方法和一些层次聚类技术

6、不能进行这样的处理。 Chameleon和cure是专门用来处理这一问题的技术,不同大小 许多聚类算法，如k均值，当簇具有不同的大小时不能很好的处理 不同密度 具有很不相同的密度的簇可能对诸如DBSCAN和k均值等算法造成影响 基于SNN密度的聚类技术可以处理这个问题 无明显分离的簇 当簇接触或重叠时，有些聚类技术将应当分开的簇合并。甚至有些发现不同簇的技术随意地将点指派到一个或另一个簇。 模糊聚类可以处理这一问题,簇之间的联系 在大部分聚类技术中，都不考虑簇之间的联系，如簇的相对位置 自组织映射（SOM）是一种在聚类期间直接考虑簇之间联系的聚类技术。 子空间簇 簇可能只在维（属性）的一个子集

7、中存在，并且使用一个维集合确定的簇可能也使用另一个维确定的簇很不相同。,聚类算法的一般特征,次序依赖性 对于某些算法，所产生的簇的质量和个数可能因数据处理的次序不同而显著地变化。如SOM 非确定性 有些算法不是次序依赖的，但是它们每次运行都产生不同的结果，因为它们依赖于需要随机选择的初始化步骤。 变换聚类问题到其他领域 将聚类问题映射到一个不同的领域。如，基于图的聚类,可伸缩性 包含数以百万计对象的数据集并不罕见，而用于这种数据集的聚类算法应当具有线性或接近线性的时间或空间复杂度。 对于大型数据集，即使具有O(m2)复杂度也是不切实际的。 此外，数据集聚类技术不能总是假定数据放在内存，或者数据

8、元素可以随机的访问。这样的算法对于大型数据集是不可行的。,参数选择 大部分聚类算法需要用户设置一个或多个参数。选择合适的参数值可能是困难的；因此，通常的态度是“参数越少越好”。 将聚类作为最优化问题处理 聚类常常被看作优化问题。将点划分成簇，根据用户指定的目标函数度量，最大化结果簇集合的优良度。如k均值试图发现簇的集合，使得每个点到最近的簇质心距离的平方和最小。,基于原型的聚类,模糊聚类 使用混合模型的聚类 自组织映射,模糊聚类,模糊集合 1965年，Lotfi Zadeh引进模糊集合论（fuzzy set theory）和模糊逻辑（fuzzy logic）作为一种处理不精确和不确定性的方法。

9、 简要的说，模糊集合论允许对象以0和1之间的某个隶属度属于一个集合，而模糊逻辑允许一个陈述以0和1之间的确定度为真。 传统的集合论和逻辑是对应的模糊集合论和模糊逻辑的特殊情况，它们限制集合的隶属度或确定度或者为0，或者为1.,考虑如下模糊逻辑的例子 陈述“天空多云”为真的程度可以定义为天空被云覆盖的百分比。例如，天空的50%被云覆盖，则“天空多云”为真的程度是0.5。 如果我们有两个集合“多云天”和“非多云天”，则我们可以类似地赋予每一天隶属于这两个集合的程度。 这样，如果一天25%多云，则它在“多云天”集合中具有0.25的隶属度，而在“非多云天”集合中具有0.75的隶属度。,模糊簇 假定我们

10、有一个数据点的集合X=x1,x2,xm，其中每个点xi是一个n维点，即xi=（xi1,xi2,xin) 。模糊簇集C1,C2,Ck是X的所有可能模糊子集的一个子集。 这简单地意味着对于每个点xi和每个簇Cj，隶属权值（度）wij已经赋予0和1之间的值。 然而，我们还想将以下合理的条件施加在簇上，以确定簇形成模糊伪划分（fuzzy psuedo-partition）。,给定点xi的所有权值之和为1： 每个簇Cj以非零权值至少包含一个点，但不以权值1包含所有的点,尽管存在多种模糊聚类，我们只考虑k均值的模糊版本，称作模糊c均值。 在聚类文献中，那些不采用簇质心增量更新方法的k均值版本有时称为c均值

11、。模糊c均值算法有时称为FCM 算法9.1 基本模糊c均值算法 选择一个初始模糊伪划分，即对所有的wij赋值 Repeat 使用模糊伪划分，计算每个簇的质心 重新计算模糊伪划分，即wij Until 质心不发生变化,FCM的结构类似于K均值。 K均值可以看作FCM的特例。 K均值在初始化之后，交替地更新质心和指派每个对象到最近的质心。具体地说，计算模糊伪划分等价于指派步骤。 与k均值一样，FCM可以解释为试图最小化误差的平方和（SSE），尽管FCM基于SSE的模糊版本。,计算SSE 公式： 其中cj是第j个簇的质心，而p是确定权值影响的指数，在1和之间取值 初始化 通常使用随机初始化。特殊地，

12、权值随机的选取，同时限制与任何对象相关联的权值之和等于1。,计算质心 公式： 模糊质心的定义类似于传统的质心定义，不同之处在于所有点都考虑，并且每个点对质心的贡献要根据它的隶属度加权。,更新模糊伪划分 公式: 如果p2，则该指数降低赋予离点最近的簇的权值。事实上，随着p趋向于无穷大，该指数趋向于0，而权值趋向于1/k。 另一方面，随着p趋向于1，该指数加大赋予离点最近的簇的权值。随着p趋向于1，关于最近簇的隶属权值趋向于1，而关于其他簇的隶属权值趋向于0。这时对应于k均值。,例子：三个圆形簇上的模糊c均值,优点与局限性,FCM产生指示任意点属于任意簇的程度的聚类。 它比K均值算法计算复杂性高。

13、 除此之外，它与k均值算法具有相同的优点和缺点。,基于原型的聚类,模糊聚类 使用混合模型的聚类 自组织映射,使用混合模型的聚类,基于统计模型的聚类。通常，假定数据是由一个统计过程产生的，并且通过找出最佳拟合数据的统计模型来描述数据，其中统计模型用分布和该分布的一组参数描述。 混合模型（mixture models）：它使用若干统计分布对数据建模。每个分布对应于一个簇，而每个分布的参数提供对应于簇的描述，通常用中心和发散描述。,算法,估计数据分布： 确定分布：一般假设数据取自高斯混合分布。然后，对分布的参数进行估计：利用EM算法进行最大似然估计 利用直方图估计分布 对分布进行划分、分离。每个分布

14、对应于一个簇。,优点和缺点,混合模型比k均值或模糊c均值更一般，因为它可以使用各种类型的分布。 利用简单的估计分布的方法（如直方图）可能会错误估计数据的原始分布，导致结果不好。 利用复杂的方法（如EM算法），计算复杂性会大大增加。,基于原型的聚类,模糊聚类 使用混合模型的聚类 自组织映射,自组织映射,Kohonen自组织特征映射（SOFM或SOM）是一种基于神经网络观点的聚类和数据可视化技术。 尽管SOM源于神经网络，但是它可以表示成一种基于原形的聚类的变形。 与其他基于质心的聚类技术一样，SOM的目标是发现质心的集合，并将数据集中的每个对象指派到提供该对象最佳近似的质心。用神经网络的术语，每

15、个质心都与一个神经元相关联。,SOM算法,初始化质心。 Repeat 选择下一个对象 确定到该对象最近的质心 更新该质心和附近的质心，即在一个特定邻域 内的质心 Until 质心改变不多或超过某个域值 指派每个对象到最近的质心，并返回质心和簇,基于密度的聚类,基于网格的聚类 子空间聚类 DENCLUE,基于网格的聚类,网格是一种组织数据集的有效方法，至少在低维空间中如此。 其基本思想是，将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合。每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值。 存在许多利用网格进行聚类的方法，大部分方法是基于密度的。,例子,基于网格的算法,定义

16、一个网格单元集 将对象指派到合适的单元，并计算每个单元的密度 删除密度低于指定的阈值的单元 由邻近的稠密单元组形成簇,定义网格单元 对于连续属性，定义网格单元相当于连续属性离散化。可将值划分为等宽的区间、等频的区间、使用聚类确定的区间。 网格单元的密度 定义网格单元密度的自然方法是：定义网格单元的密度为该区域中的点数除以区域的体积。 如果使用具有相同体积的网格单元，使得每个单元的点数直接度量单元的密度。,邻近的稠密单元组形成簇 密度阈值的设定是关键。如图9-10和表9-2，如果密度阈值为9，则大簇的4个部分将丢失。 邻近单元？一个二维网格单元有4个还是8个邻接单元？,例子,优点与局限性,算法运

17、行速度较快，可达o(mlogm)。这使得它成为许多聚类算法的基础，如STING、GRIDCLUS、waveCluster、Bang-Clustering、CLIQUE和MAFIA。 网格单元形状选择影响聚类效果。如矩形网格单元不能准确地捕获圆形边界区域的密度。 对于高维数据，基于网格的聚类效果较差。 密度阈值的选择对算法效果影响较大。,基于密度的聚类,基于网格的聚类 子空间聚类 DENCLUE,迄今为止，所考虑的聚类技术都是使用所有的属性来发现簇。然而，如果仅考虑特征子集，则我们发现的簇可能因子空间不同而很不相同。 有两个理由，子空间的簇可能是有趣的。 数据关于少量属性的集合可能可以聚类，而关

18、于其余属性是随机分布的。 在某些情况下，在不同的维集合中存在不同的簇。 例子：考虑记录不同时间、不同商品销售情况的数据集（时间是维，商品是对象）。某些商品对于特定的月份集（如夏天）可能表现出类似行为，但是不同的簇可能被不同的月份（维）刻画。,CLIQUE算法,CLIQUE（Clustering In QUEst）是系统地发现子空间簇的基于网格的聚类算法。检查每个子空间寻找簇是不现实的，因为这样的子空间的数量是维度的指数。 基于密度的簇的单调性：如果一个点集在k维上形成一个基于密度的簇，则相同的点集在这些维的所有可能的子集上也是基于密度的簇的一部分。,CLIQUE算法,找出对应于每个属性的一维空

19、间中的所有稠密区域。这是稠密的一维单元的集合。 K2 Repeat 由稠密的k-1维单元产生所有的候选稠密k维单元 删除点数少于域值的单元 kk+1 Until 不存在候选稠密k维单元 通过取所有邻接的、高密度的单元的并发现簇 使用一小组描述簇中单元的属性值域的不等式概括每一个簇。,CLIQUE的优点与局限性,CLIQUE最大特点是，它提供了一种搜索子空间发现簇的有效技术。由于这种方法基于关联分析的先验原理，它的性质能够被很好地解释。 CLIQUE能够用一小组不等式概括构成一个簇的单元列表。 CLIQUE的局限性与其他基于密度的方法和Apriori算法相同。如，CLIQUE发现的簇可以共享对象

20、。允许簇重叠可能大幅度增加簇的个数，并使得解释更加困难。Apriori具有指数级的复杂度。,基于密度的聚类,基于网格的聚类 子空间聚类 DENCLUE,DENCLUE：基于密度聚类的一种基于核的方案,DENCLUE(DENsity CLUstEring)是一种基于密度的聚类方法，它用与每个点相关联的影响函数之和对点集的总密度建模。结果总密度函数将具有局部尖峰，并且这些局部尖峰用来以自然的方式定义簇。 具体的说，对于每个数据点，一个爬山过程找出与该点相关联的最近的尖峰，并且与一个特定的尖峰（称作局部密度吸引点（local density attractor）相关联的所有数据点成为一个簇。 如果局

21、部尖峰处的密度太低，则相关联的簇中的点将被视为噪声而丢弃。 如果一个局部尖峰通过一条数据点路径与另一个局部尖峰相连接，并且该路径上每个点的密度都高于最小密度阈值，则与这些局部尖峰相关联的簇合并在一起。,DENCLUE算法,对数据点占据的空间推导密度函数 识别局部最大点（即密度吸引点） 通过沿密度增长最大的方向移动，将每个点关联到一个密度吸引点 定义与特定的密度吸引点相关联的点构成的簇 丢弃密度吸引点的密度小于用户指定阈值的簇 合并通过密度大于或等于阈值的点路径连接的簇,核密度估计,核密度估计用函数描述数据的分布。每个点对总密度函数的贡献用一个核函数表示。总密度函数仅仅是与每个点相关联的核函数之

22、核 核函数是对称的，并且它的值随到点的距离增加而下降。高斯函数常常用作核函数：,DENCLUE的优点与局限性,DENCLUE具有坚实的理论基础，因为它基于统计学发展完善的领域-核密度函数和核密度估计。因此，DENCLUE提供了比其他基于网络的聚类技术和DBSCAN更加灵活、更加精确的计算密度的方法。（DBSCAN是DENCLUE的特例） 基于核密度函数的方法本质上是计算昂贵的，但DENCLUE使用基于网格的技术来处理该问题。尽管如此，DENCLUE可能比其他基于密度的聚类技术的计算开销更大。 DENCLUE具有其他基于密度的方法的优缺点。,基于图的聚类,最小生成树聚类 OPOSSUM Cham

23、eleon Jarvis-Patrick聚类算法 基于SNN密度的聚类,稀疏化,m个数据点的mm邻近度矩阵可以用一个稠密图表示，每个节点与其他所有点相连，权值反映邻近性。 尽管每个对象与其他每个对象都有某种程度的近邻性，但是对于大部分数据集，对象只与少量对象高度相似，而与大部分其他对象的相似性很弱。这一性质用来稀疏化邻近度图。 稀疏化可以这样进行：断开相似度低于指定阈值的边、或仅保留连接到点的k个近邻的边。,稀疏化的好处,压缩了数据量 可以更好的聚类 稀疏化技术保持了对象与最近邻的连接，断开与较远对象的连接。这与最近邻原理一致，对象的最近邻趋向于与对象在同一个类。这降低了噪声和离群点的影响，增

24、强了簇之间的差别。 可以使用图划分算法,应当把邻近度图的稀疏化看成使用实际聚类算法之前的初始化步骤。 理论上讲，一个完美的稀疏化应当将邻近度图划分成对应于期望簇的连通分支，但实际中这很难做到。很容易出现单条边连接两个簇，或者单个簇被分裂成若干个不相连接的子簇的情况。,基于图的聚类,最小生成树聚类 OPOSSUM Chameleon Jarvis-Patrick聚类算法 基于SNN密度的聚类,最小生成树聚类（minimum spanning tree，MST）,计算相异度图的最小生成树 Repeat 断开对应于最大相异度的边，创建一个新的簇 Until 只剩下单个簇 最小生成树聚类是一种基于分裂

25、的层次聚类算法 最小生成树聚类可以看作用稀疏化找出簇的方法,基于图的聚类,最小生成树聚类 OPOSSUM Chameleon Jarvis-Patrick聚类算法 基于SNN密度的聚类,OPOSSUM：使用METIS的稀疏相似度最优划分,OPOSSUM（Optimal Partitioning of Sparse Similarities Using METIS）是一种专门为诸如文档或购物篮数据等稀疏、高维数据设计的聚类技术。与MST一样，它基于邻近度图的稀疏化进行聚类。然而，OPOSSUM使用METIS算法，该算法是专门为划分图设计的。 OPOSSUM聚类算法 1：计算稀疏化的相似度图 2：

26、使用METIS，将相似度图划分成k个不同的分支（簇）,所使用的相似性度量是适合于稀疏、高维数据的度量，如扩充的Jaccard度量或余弦度量。 METIS图划分程序将稀疏图划分为k个不同的分支，其中k是用户指定的参数，旨在（1）最小化分支之间边的权值（2）实现平衡约束。OPOSSUM使用如下两种约束中的一种：（1）每个簇中的对象个数必须粗略相等，或（2）属性值的和必须粗略相等。,优点与缺点,OPOSSUM简单、速度快。 它将数据划分大小粗略相等的簇。根据聚类的目标这可能看作优点或缺点。,基于图的聚类,最小生成树聚类 OPOSSUM Chameleon Jarvis-Patrick聚类算法 基于S

27、NN密度的聚类,Chameleon,Chameleon是一种凝聚聚类技术，它解决前两段提到的问题。它将数据的初始划分与一种新颖的层次聚类方案相结合。 这种层次聚类使用接近性和互连性概念以及簇的局部建模。关键思想是：仅当合并后的结果簇类似于原来的两个簇时，这两个簇才应当合并。,确定合并哪些簇,相对接近度（relative closeness，RC）：是被簇的内部接近度规范化的两个簇的绝对接近度。两个簇合并，仅当结果簇中的点之间的接近程度几乎与原来的每个簇一样。 mi和mj分别是簇ci和cj的大小。SEC（ci，cj）是连接簇ci和cj的边的平均值；SEC（ci）是二分簇ci的边的平均权值。,相对

28、互连度（relative interconnectivity, RI）：是被簇的内部互连度规范化的两个簇的绝对互连度。如果结果簇中的点之间的连接几乎与原来的每个簇一样强，两个簇合并。 其中，EC（Ci，Cj）是连接簇Ci和Cj的边之和；EC(Ci)是二分簇Ci的割边的最小和；EC(Cj)是二分簇Cj的割边的最小和。 RI和RC可以用多种不同的方法组合，产生自相似性的总量。Chameleon使用的方法是合并最大化RI(Ci,Cj)*RC(Ci,Cj)a簇对。其中a值大于1.,Limitations of Current Merging Schemes,Relative Closeness sch

29、emes will merge (a) and (b),(a),(b),(c),(d),Relative interconnectivity schemes will merge (c) and (d),Chameleon算法,构造k-最近邻图 使用多层图划分算法划分图 Repeat 合并关于相对互连性和相对接近性而言，最好 地保持簇的自相似性的簇 Until 不再有可以合并的簇,例子,优点与局限性,Chameleon能够有效地聚类空间数据，即便存在噪声和离群点，并且簇具有不同的形状、大小和密度。 Chameleon假定由稀疏化和图划分过程产生的对象组群是子簇，即一个划分中的大部分点属于同一个

30、真正的簇。如果不是，则凝聚层次聚类将混合这些错误，因为它绝对不可能再将已经错误地放到一起的对象分开。这样，当划分过程未产生子簇时，chameleon就有问题，对于高维数据，常常出现这种情况。,共享最近邻相似性,SNN（shared nearest neighbor）相似度计算： 1.找出所有点的k-近邻 2.If 两个点x和y不是相互在对方的k-最近邻中 then 3. similarity(x,y) 0 4.Else 5. similarity(x,y)共享的近邻个数 6.End if,SNN相似度由于通过使用共享最近邻的个数考虑了对象的环境，SNN相似度可以处理一个对象碰巧与另一对象相对接

31、近，但属于不同的类。在这种情况下，对象一般不共享许多近邻，并且它们的SNN相似度低。 SSN相似度也能处理变密度簇的问题。在低密度区域，对象比高密度区域的对象分开得更远。然而，一对点之间的SNN相似度只依赖于两个对象共享的最近邻的个数，而不是这些近邻之间的相距多远。SNN关于点的密度进行自动缩放。,基于图的聚类,最小生成树聚类 OPOSSUM Chameleon Jarvis-Patrick聚类算法 基于SNN密度的聚类,Jarvis-Patrick（JP）聚类算法,计算SNN相似度图 使用相似度阈值，稀疏化SNN相似度图 找出稀疏化的SNN相似度图的连通分支,优点与局限性,因为JP聚类基于S

32、NN相似度概念，它擅长于处理噪声和离群点，并且能够处理不同大小、形状和密度的簇。 该算法对高维数据效果良好，尤其擅长发现强相关对象的紧密簇。 JP聚类把簇定义为SNN相似度图的连通分支。这样，一个对象集是分裂成两个簇还是作为一个簇留下，可能依赖于一条链。,基于SNN密度的聚类,算法： 计算SNN相似度图 以用户指定的参数Eps和MinPts，使用DBSCAN SNN密度的聚类算法比Jarvis-Patrick聚类或DBSCAN更加灵活。 不象DBSCAN，它可以用于高维数据和簇具有不同密度的情况。 不象Jarvis-Patrick聚类简单地使用域值，然后取连通分支作为簇，基于SNN密度的聚类使

33、用基于SNN密度和核心点概念的方法。,核心点：一个点是核心点，如果在该点给定邻域内的点数超过某个阈值MinPts。 边界点。边界点不是核心点，但是它落在一个核心点的邻域内。 噪声点是既非核心点，也非边界点的任何点。,SNN Density,a) All Points b) High SNN Density,c) Medium SNN Density d) Low SNN Density,例子：解释该算法处理高维数据能力,SNN Clusters of SLP.,SNN Density of Points on the Globe.,41年期间，在2.5度的经纬度网格的每个点上的月平均海平面气压

34、（SLP）,优点与局限性,基于SNN密度的聚类的优点与局限性类似于JP聚类。 然而，核心点和SNN密度的使用大大增加了该方法的能力和灵活性。,可伸缩：一般问题和方法,BIRCH CURE,如果运行时间长得不可接受，或者需要的存储量太大，即使最好的聚类算法也没有多大价值。 许多聚类算法所需要的存储量都是非线性的。例如：使用层次聚类，存储需求一般是O(m2)。类似地，有些聚类算法所需要的计算量也是非线性的。 可伸缩性可以通过如下技术实现：多维或空间存取方法、邻近度约束、抽样、划分数据对象、汇总、并行与分布计算。,CURE,CURE（Clustering Using REpresentative）是

35、一种聚类算法，它使用各种不同的技术创建一种能够处理大型数据、离群点、具有非球形和非均匀大小的簇的数据的方法。 CURE使用簇中的多个代表点来表示一个簇。理论上，这些点捕获了簇的几何形状。 具体来说，第一个代表点选择离簇中心最远的点，而其余的点选择离所有已经选取的点最远的点。这样，代表点相对分离。 选取的点的个数是一个参数，但是一般取10效果较好。,一旦选定代表点，它们就以因子a向簇中心收缩。这有助于减轻离群点的影响。 例如，一个到中心的距离为10个单位的代表点将移动3个单位（对于a=0.7），而到中心距离为1个单位的代表点仅移动0.3个单位。,CURE使用一种凝聚层次聚类方案进行实际的聚类。两

36、个簇之间的距离是任意两个代表点（在它们向它们代表点的中心收缩之后）之间的最短距离。 如果a=0，它等价于基于质心的层次聚类；a=1时，它与单链层次聚类大致相同。 注意，尽管使用层次聚类方案，但是CURE的目标是发现用户指定个数的簇。,CURE在聚类过程的两个不同阶段删除离群点。首先，如果一个簇增长缓慢，则这意味它主要由离群点组成，因为根据定义，离群点远离其他点，并且不会经常与其他点合并。 在CURE中，离群点删除的第一个阶段一般出现在簇的个数是原来点数的1/3时。第二个离群点删除阶段出现在簇的个数达到K的量级时。此时，小簇又被删除。,CURE在最坏情况下复杂度为O(m2logm)，它不能直接用

37、于大型数据集。因此，CURE使用了两种技术来加快聚类过程。 第一种技术是取随机样本，并在抽样的数据点上进行层次聚类。随后是最终扫描，将数据集中剩余的点指派到簇中。 在某些情况下，聚类所需要的样本仍然太大，需要第二种技术解决。在这种情况下，CURE划分样本数据，然后聚类每个划分中的点。这种预聚类步后通常紧随中间簇的聚类，以及将数据集中的每个点指派到一个簇的最终扫描。,CURE算法,由数据集抽取一个随机样本集。 将样本集划分成p个大小相同的划分。 使用CURE的层次聚类算法，将每个划分中的点聚类成m/pq个簇，得到总共m/q个簇。 使用CURE的层次聚类算法对上一步发现的m/q个簇进行聚类，直到只

38、剩下k个簇。 删除离群点。 将所有剩余的数据点指派到最近的簇，得到完全聚类。,K是期望的簇个数，m是点的个数，p是划分的个数，而q是一个划分中的点的期望压缩，即一个划分中的簇的个数是m/pq，簇的总数是m/q 例如，如果m=10000，p=10并且q=100，则每个划分包含10000/10=1000个点，每个划分有1000/100=10个簇，而总共有10000/100=100个簇。,CURE的抽样,CURE抽样尽力确保抽到每个簇的样本。为了保证这样的抽样，CURE的作者推算出了能够实现这一保证的样本集大小的上界。 S为我们应该抽取的样本大小 假设有100000个对象，我们的目标是以80%的可能

39、性得到10%的Ci簇对象，其中Ci的大小是1000。在此情况下，f=0.1，=0.2，m=100000，这样s=11962。 S=11962是为了以80%的概率得到10%的Ci簇对象，需要抽取的样本大小,划分,将点划分成p个大小为m/p的组，使用CURE对每个划分聚类，将对象的个数压缩一个因子q1,其中q可以粗略地看作划分中的簇的平均大小。总共产生m/q个簇。然后，预聚类后随m/q个中间簇的最终聚类，产生期望的簇个数。两遍聚类都使用CURE的层次聚类算法，而最后一遍将数据集中的每个点指派到一个簇。 P和q的选取是关键。应尽力选择合适的p，使得整个划分可以以合理的时间在内存处理。此外，应尽力选择

40、合适的p和q使得同一基本簇的对象最终在一个簇中。,A subnetwork is defined as a gene set that induces a single connected component in the proteinprotein interaction network. Given a particular subnetwork M, let a represent its vector of activity scores over the tumor samples, and let c represent the corresponding vector of class labels (metastatic or non-metastatic).,使用哪种聚类算法？,聚类的类型 簇的类型 簇的特性 数据集和属性的特征噪声和离群点 数据对象的个数 属性的个数 簇描述 算法考虑,数据 探索数据 分类：基本概念、决策树与模型评估 分类：其他技术 关联分析：基本概念和算法 关联分析：高级概念 聚类分析：基本概念和算法 聚类分析：附加问题与算法 异常检测,