附加问题与算法

《附加问题与算法》由会员分享，可在线阅读，更多相关《附加问题与算法（109页珍藏版）》请在装配图网上搜索。

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

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

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

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

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

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

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

8、O(m2)复杂度也是不切实际的。 此外，数据集聚类技术不能总是假定数据放在内存，或者数据元素可以随机的访问。这样的算法对于大型数据集是不可行的。l参数选择 大部分聚类算法需要用户设置一个或多个参数。选择合适的参数值可能是困难的；因此，通常的态度是“参数越少越好”。l将聚类作为最优化问题处理 聚类常常被看作优化问题。将点划分成簇，根据用户指定的目标函数度量，最大化结果簇集合的优良度。如k均值试图发现簇的集合，使得每个点到最近的簇质心距离的平方和最小。基于原型的聚类基于原型的聚类l模糊聚类l使用混合模型的聚类l自组织映射模糊聚类模糊聚类l模糊集合l1965年，Lotfi Zadeh引进模糊集合论（

9、fuzzy set theory）和模糊逻辑（fuzzy logic）作为一种处理不精确和不确定性的方法。l简要的说，模糊集合论允许对象以0和1之间的某个隶属度属于一个集合，而模糊逻辑允许一个陈述以0和1之间的确定度为真。l传统的集合论和逻辑是对应的模糊集合论和模糊逻辑的特殊情况，它们限制集合的隶属度或确定度或者为0，或者为1.l考虑如下模糊逻辑的例子l陈述“天空多云”为真的程度可以定义为天空被云覆盖的百分比。例如，天空的50%被云覆盖，则“天空多云”为真的程度是0.5。l如果我们有两个集合“多云天”和“非多云天”，则我们可以类似地赋予每一天隶属于这两个集合的程度。l这样，如果一天25%多云，

10、则它在“多云天”集合中具有0.25的隶属度，而在“非多云天”集合中具有0.75的隶属度。l模糊簇l假定我们有一个数据点的集合X=x1,x2,xm，其中每个点xi是一个n维点，即xi=（xi1,xi2,xin) 。模糊簇集C1,C2,Ck是X的所有可能模糊子集的一个子集。l这简单地意味着对于每个点xi和每个簇Cj，隶属权值（度）wij已经赋予0和1之间的值。l然而，我们还想将以下合理的条件施加在簇上，以确定簇形成模糊伪划分（fuzzy psuedo-partition）。l给定点xi的所有权值之和为1：l每个簇Cj以非零权值至少包含一个点，但不以权值1包含所有的点kjwij11mwijmi10l

11、尽管存在多种模糊聚类，我们只考虑k均值的模糊版本，称作模糊c均值。l在聚类文献中，那些不采用簇质心增量更新方法的k均值版本有时称为c均值。模糊c均值算法有时称为FCMl算法9.1 基本模糊c均值算法 选择一个初始模糊伪划分，即对所有的wij赋值 Repeat 使用模糊伪划分，计算每个簇的质心 重新计算模糊伪划分，即wij Until 质心不发生变化lFCM的结构类似于K均值。 K均值可以看作FCM的特例。lK均值在初始化之后，交替地更新质心和指派每个对象到最近的质心。具体地说，计算模糊伪划分等价于指派步骤。l与k均值一样，FCM可以解释为试图最小化误差的平方和（SSE），尽管FCM基于SSE的

12、模糊版本。l计算SSE 公式： 其中cj是第j个簇的质心，而p是确定权值影响的指数，在1和之间取值l初始化 通常使用随机初始化。特殊地，权值随机的选取，同时限制与任何对象相关联的权值之和等于1。kjmijipijkcxdistwCCCSSE11221),(),.,(l计算质心 公式： 模糊质心的定义类似于传统的质心定义，不同之处在于所有点都考虑，并且每个点对质心的贡献要根据它的隶属度加权。mipijmiipijjwxwc11l更新模糊伪划分 公式: 如果p2，则该指数降低赋予离点最近的簇的权值。事实上，随着p趋向于无穷大，该指数趋向于0，而权值趋向于1/k。 另一方面，随着p趋向于1，该指数加

13、大赋予离点最近的簇的权值。随着p趋向于1，关于最近簇的隶属权值趋向于1，而关于其他簇的隶属权值趋向于0。这时对应于k均值。kqpqipjiijcxdistcxdistw1112112),(/1 (),(/1 (例子：三个圆形簇上的模糊例子：三个圆形簇上的模糊c均值均值优点与局限性优点与局限性lFCM产生指示任意点属于任意簇的程度的聚类。l它比K均值算法计算复杂性高。l除此之外，它与k均值算法具有相同的优点和缺点。基于原型的聚类基于原型的聚类l模糊聚类l使用混合模型的聚类l自组织映射使用混合模型的聚类使用混合模型的聚类l基于统计模型的聚类。通常，假定数据是由一个统计过程产生的，并且通过找出最佳拟

14、合数据的统计模型来描述数据，其中统计模型用分布和该分布的一组参数描述。l混合模型（mixture models）：它使用若干统计分布对数据建模。每个分布对应于一个簇，而每个分布的参数提供对应于簇的描述，通常用中心和发散描述。算法算法l估计数据分布： 确定分布：一般假设数据取自高斯混合分布。然后，对分布的参数进行估计：利用EM算法进行最大似然估计 利用直方图估计分布l对分布进行划分、分离。每个分布对应于一个簇。优点和缺点优点和缺点l混合模型比k均值或模糊c均值更一般，因为它可以使用各种类型的分布。l利用简单的估计分布的方法（如直方图）可能会错误估计数据的原始分布，导致结果不好。l利用复杂的方法（

15、如EM算法），计算复杂性会大大增加。基于原型的聚类基于原型的聚类l模糊聚类l使用混合模型的聚类l自组织映射自组织映射自组织映射lKohonen自组织特征映射（SOFM或SOM）是一种基于神经网络观点的聚类和数据可视化技术。l尽管SOM源于神经网络，但是它可以表示成一种基于原形的聚类的变形。l与其他基于质心的聚类技术一样，SOM的目标是发现质心的集合，并将数据集中的每个对象指派到提供该对象最佳近似的质心。用神经网络的术语，每个质心都与一个神经元相关联。SOM算法算法l初始化质心。lRepeatl 选择下一个对象l 确定到该对象最近的质心l 更新该质心和附近的质心，即在一个特定邻域 内的质心lUn

16、til 质心改变不多或超过某个域值l指派每个对象到最近的质心，并返回质心和簇基于密度的聚类基于密度的聚类l基于网格的聚类l子空间聚类lDENCLUE基于网格的聚类基于网格的聚类l网格是一种组织数据集的有效方法，至少在低维空间中如此。l其基本思想是，将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合。每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值。l存在许多利用网格进行聚类的方法，大部分方法是基于密度的。例子例子基于网格的算法基于网格的算法l定义一个网格单元集l将对象指派到合适的单元，并计算每个单元的密度l删除密度低于指定的阈值的单元l由邻近的稠密单元组形成簇l定义网格单

17、元 对于连续属性，定义网格单元相当于连续属性离散化。可将值划分为等宽的区间、等频的区间、使用聚类确定的区间。l网格单元的密度 定义网格单元密度的自然方法是：定义网格单元的密度为该区域中的点数除以区域的体积。 如果使用具有相同体积的网格单元，使得每个单元的点数直接度量单元的密度。l邻近的稠密单元组形成簇 密度阈值的设定是关键。如图9-10和表9-2，如果密度阈值为9，则大簇的4个部分将丢失。 邻近单元？一个二维网格单元有4个还是8个邻接单元？例子例子优点与局限性优点与局限性l算法运行速度较快，可达o(mlogm)。这使得它成为许多聚类算法的基础，如STING、GRIDCLUS、waveClust

18、er、Bang-Clustering、CLIQUE和MAFIA。l网格单元形状选择影响聚类效果。如矩形网格单元不能准确地捕获圆形边界区域的密度。l对于高维数据，基于网格的聚类效果较差。l密度阈值的选择对算法效果影响较大。基于密度的聚类基于密度的聚类l基于网格的聚类l子空间聚类lDENCLUEl迄今为止，所考虑的聚类技术都是使用所有的属性来发现簇。然而，如果仅考虑特征子集，则我们发现的簇可能因子空间不同而很不相同。l有两个理由，子空间的簇可能是有趣的。 数据关于少量属性的集合可能可以聚类，而关于其余属性是随机分布的。 在某些情况下，在不同的维集合中存在不同的簇。l例子：考虑记录不同时间、不同商品

19、销售情况的数据集（时间是维，商品是对象）。某些商品对于特定的月份集（如夏天）可能表现出类似行为，但是不同的簇可能被不同的月份（维）刻画。CLIQUE算法算法lCLIQUE（Clustering In QUEst）是系统地发现子空间簇的基于网格的聚类算法。检查每个子空间寻找簇是不现实的，因为这样的子空间的数量是维度的指数。l基于密度的簇的单调性：如果一个点集在k维上形成一个基于密度的簇，则相同的点集在这些维的所有可能的子集上也是基于密度的簇的一部分。CLIQUE算法算法l找出对应于每个属性的一维空间中的所有稠密区域。这是稠密的一维单元的集合。lK2lRepeatl 由稠密的k-1维单元产生所有的

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

21、复杂度。基于密度的聚类基于密度的聚类l基于网格的聚类l子空间聚类lDENCLUEDENCLUE：基于密度聚类的一种基于核的方案：基于密度聚类的一种基于核的方案lDENCLUE(DENsity CLUstEring)是一种基于密度的聚类方法，它用与每个点相关联的影响函数之和对点集的总密度建模。结果总密度函数将具有局部尖峰，并且这些局部尖峰用来以自然的方式定义簇。l具体的说，对于每个数据点，一个爬山过程找出与该点相关联的最近的尖峰，并且与一个特定的尖峰（称作局部密度吸引点（local density attractor）相关联的所有数据点成为一个簇。l如果局部尖峰处的密度太低，则相关联的簇中的点将

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

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

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

25、于与对象在同一个类。这降低了噪声和离群点的影响，增强了簇之间的差别。l可以使用图划分算法l应当把邻近度图的稀疏化看成使用实际聚类算法之前的初始化步骤。l理论上讲，一个完美的稀疏化应当将邻近度图划分成对应于期望簇的连通分支，但实际中这很难做到。很容易出现单条边连接两个簇，或者单个簇被分裂成若干个不相连接的子簇的情况。基于图的聚类基于图的聚类l最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法l基于SNN密度的聚类最小生成树聚类（最小生成树聚类（minimum spanning tree，MST）l计算相异度图的最小生成树lRepeatl 断开对应于最大相异度

26、的边，创建一个新的簇lUntil 只剩下单个簇l最小生成树聚类是一种基于分裂的层次聚类算法l最小生成树聚类可以看作用稀疏化找出簇的方法基于图的聚类基于图的聚类l最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法l基于SNN密度的聚类OPOSSUM：使用：使用METIS的稀疏相似度最优划分的稀疏相似度最优划分lOPOSSUM（Optimal Partitioning of Sparse Similarities Using METIS）是一种专门为诸如文档或购物篮数据等稀疏、高维数据设计的聚类技术。与MST一样，它基于邻近度图的稀疏化进行聚类。然而，OPOS

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

28、或缺点。基于图的聚类基于图的聚类l最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法l基于SNN密度的聚类ChameleonlChameleon是一种凝聚聚类技术，它解决前两段提到的问题。它将数据的初始划分与一种新颖的层次聚类方案相结合。l这种层次聚类使用接近性和互连性概念以及簇的局部建模。关键思想是：仅当合并后的结果簇类似于原来的两个簇时，这两个簇才应当合并。确定合并哪些簇确定合并哪些簇l相对接近度（relative closeness，RC）：是被簇的内部接近度规范化的两个簇的绝对接近度。两个簇合并，仅当结果簇中的点之间的接近程度几乎与原来的每个簇一样

29、。lmi和mj分别是簇ci和cj的大小。SEC（ci，cj）是连接簇ci和cj的边的平均值；SEC（ci）是二分簇ci的边的平均权值。)()(),(),(jECjiiiECjiijiECjiCSmmmCSmmmCCSCCRCl相对互连度（relative interconnectivity, RI）：是被簇的内部互连度规范化的两个簇的绝对互连度。如果结果簇中的点之间的连接几乎与原来的每个簇一样强，两个簇合并。l其中，EC（Ci，Cj）是连接簇Ci和Cj的边之和；EC(Ci)是二分簇Ci的割边的最小和；EC(Cj)是二分簇Cj的割边的最小和。lRI和RC可以用多种不同的方法组合，产生自相似性的总

30、量。Chameleon使用的方法是合并最大化RI(Ci,Cj)*RC(Ci,Cj)a簇对。其中a值大于1.)()(21),(),(jijijiCECCECCCECCCRILimitations of Current Merging SchemesRelative Closeness schemes will merge (a) and (b)(a)(b)(c)(d)Relative interconnectivity schemes will merge (c) and (d)Chameleon算法算法l构造k-最近邻图l使用多层图划分算法划分图lRepeatl 合并关于相对互连性和相对接近性

31、而言，最好 地保持簇的自相似性的簇lUntil 不再有可以合并的簇例子例子优点与局限性优点与局限性lChameleon能够有效地聚类空间数据，即便存在噪声和离群点，并且簇具有不同的形状、大小和密度。lChameleon假定由稀疏化和图划分过程产生的对象组群是子簇，即一个划分中的大部分点属于同一个真正的簇。如果不是，则凝聚层次聚类将混合这些错误，因为它绝对不可能再将已经错误地放到一起的对象分开。这样，当划分过程未产生子簇时，chameleon就有问题，对于高维数据，常常出现这种情况。共享最近邻相似性共享最近邻相似性lSNN（shared nearest neighbor）相似度计算：l1.找出所

32、有点的k-近邻l2.If 两个点x和y不是相互在对方的k-最近邻中 thenl3. similarity(x,y) 0l4.Elsel5. similarity(x,y)共享的近邻个数l6.End iflSNN相似度由于通过使用共享最近邻的个数考虑了对象的环境，SNN相似度可以处理一个对象碰巧与另一对象相对接近，但属于不同的类。在这种情况下，对象一般不共享许多近邻，并且它们的SNN相似度低。lSSN相似度也能处理变密度簇的问题。在低密度区域，对象比高密度区域的对象分开得更远。然而，一对点之间的SNN相似度只依赖于两个对象共享的最近邻的个数，而不是这些近邻之间的相距多远。SNN关于点的密度进行自

33、动缩放。基于图的聚类基于图的聚类l最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法l基于SNN密度的聚类Jarvis-Patrick（JP）聚类算法）聚类算法l计算SNN相似度图l使用相似度阈值，稀疏化SNN相似度图l找出稀疏化的SNN相似度图的连通分支优点与局限性优点与局限性l因为JP聚类基于SNN相似度概念，它擅长于处理噪声和离群点，并且能够处理不同大小、形状和密度的簇。l该算法对高维数据效果良好，尤其擅长发现强相关对象的紧密簇。lJP聚类把簇定义为SNN相似度图的连通分支。这样，一个对象集是分裂成两个簇还是作为一个簇留下，可能依赖于一条链。基于基于

34、SNN密度的聚类密度的聚类l算法：l计算SNN相似度图l以用户指定的参数Eps和MinPts，使用DBSCANlSNN密度的聚类算法比Jarvis-Patrick聚类或DBSCAN更加灵活。l不象DBSCAN，它可以用于高维数据和簇具有不同密度的情况。l不象Jarvis-Patrick聚类简单地使用域值，然后取连通分支作为簇，基于SNN密度的聚类使用基于SNN密度和核心点概念的方法。l核心点：一个点是核心点，如果在该点给定邻域内的点数超过某个阈值MinPts。l边界点。边界点不是核心点，但是它落在一个核心点的邻域内。l噪声点是既非核心点，也非边界点的任何点。SNN Density a) All

35、 Points b) High SNN Densityc) Medium SNN Density d) Low SNN Density例子：解释该算法处理高维数据能力例子：解释该算法处理高维数据能力26 SLP Clusters via Shared Nearest Neighbor Clustering (100 NN, 1982-1994) longitudelatitude-180-150-120-90 -60 -30 0 30 60 90 120 150 180 90 60 30 0 -30-60-9013 26 24 25 22 14 16 20 17 18 19 15 23 1 9

36、 6 4 7 10 12 11 3 5 2 8 21 SNN Clusters of SLP.SNN Density of SLP Time Series Datalongitudelatitude-180 -150 -120-90 -60 -30 0 30 60 90 120 150 180 90 60 30 0 -30-60-90SNN Density of Points on the Globe.l41年期间，在2.5度的经纬度网格的每个点上的月平均海平面气压（SLP）优点与局限性优点与局限性l基于SNN密度的聚类的优点与局限性类似于JP聚类。l然而，核心点和SNN密度的使用大大增加了该

37、方法的能力和灵活性。可伸缩：一般问题和方法可伸缩：一般问题和方法lBIRCHlCUREl如果运行时间长得不可接受，或者需要的存储量太大，即使最好的聚类算法也没有多大价值。l许多聚类算法所需要的存储量都是非线性的。例如：使用层次聚类，存储需求一般是O(m2)。类似地，有些聚类算法所需要的计算量也是非线性的。l可伸缩性可以通过如下技术实现：多维或空间存取方法、邻近度约束、抽样、划分数据对象、汇总、并行与分布计算。CURElCURE（Clustering Using REpresentative）是一种聚类算法，它使用各种不同的技术创建一种能够处理大型数据、离群点、具有非球形和非均匀大小的簇的数据的

38、方法。lCURE使用簇中的多个代表点来表示一个簇。理论上，这些点捕获了簇的几何形状。l具体来说，第一个代表点选择离簇中心最远的点，而其余的点选择离所有已经选取的点最远的点。这样，代表点相对分离。l选取的点的个数是一个参数，但是一般取10效果较好。l一旦选定代表点，它们就以因子a向簇中心收缩。这有助于减轻离群点的影响。l例如，一个到中心的距离为10个单位的代表点将移动3个单位（对于a=0.7），而到中心距离为1个单位的代表点仅移动0.3个单位。 lCURE使用一种凝聚层次聚类方案进行实际的聚类。两个簇之间的距离是任意两个代表点（在它们向它们代表点的中心收缩之后）之间的最短距离。l如果a=0，它等

39、价于基于质心的层次聚类；a=1时，它与单链层次聚类大致相同。l注意，尽管使用层次聚类方案，但是CURE的目标是发现用户指定个数的簇。lCURE在聚类过程的两个不同阶段删除离群点。首先，如果一个簇增长缓慢，则这意味它主要由离群点组成，因为根据定义，离群点远离其他点，并且不会经常与其他点合并。l在CURE中，离群点删除的第一个阶段一般出现在簇的个数是原来点数的1/3时。第二个离群点删除阶段出现在簇的个数达到K的量级时。此时，小簇又被删除。lCURE在最坏情况下复杂度为O(m2logm)，它不能直接用于大型数据集。因此，CURE使用了两种技术来加快聚类过程。l第一种技术是取随机样本，并在抽样的数据点

40、上进行层次聚类。随后是最终扫描，将数据集中剩余的点指派到簇中。l在某些情况下，聚类所需要的样本仍然太大，需要第二种技术解决。在这种情况下，CURE划分样本数据，然后聚类每个划分中的点。这种预聚类步后通常紧随中间簇的聚类，以及将数据集中的每个点指派到一个簇的最终扫描。CURE算法算法l由数据集抽取一个随机样本集。l将样本集划分成p个大小相同的划分。l使用CURE的层次聚类算法，将每个划分中的点聚类成m/pq个簇，得到总共m/q个簇。l使用CURE的层次聚类算法对上一步发现的m/q个簇进行聚类，直到只剩下k个簇。l删除离群点。l将所有剩余的数据点指派到最近的簇，得到完全聚类。lK是期望的簇个数，m

41、是点的个数，p是划分的个数，而q是一个划分中的点的期望压缩，即一个划分中的簇的个数是m/pq，簇的总数是m/ql例如，如果m=10000，p=10并且q=100，则每个划分包含10000/10=1000个点，每个划分有1000/100=10个簇，而总共有10000/100=100个簇。CURE的抽样的抽样lCURE抽样尽力确保抽到每个簇的样本。为了保证这样的抽样，CURE的作者推算出了能够实现这一保证的样本集大小的上界。lS为我们应该抽取的样本大小l假设有100000个对象，我们的目标是以80%的可能性得到10%的Ci簇对象，其中Ci的大小是1000。在此情况下，f=0.1，=0.2，m=10

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

43、在一个簇中。lA 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).使用哪种聚类算法？使用哪种聚类算法？l聚类的类型l簇的类型l簇的特性l数据集和属性的特征噪声和离群点l数据对象的个数l属性的个数l簇描述l算法考虑l数据l探索数据l分类：基本概念、决策树与模型评估l分类：其他技术l关联分析：基本概念和算法l关联分析：高级概念l聚类分析：基本概念和算法l聚类分析：附加问题与算法l异常检测