附加问题与算法.pptx

比较k 均值和DBSCANl DBSCAN 和k均值都是将每个对象指派到单个簇的划分聚类算法，但是K 均值一般聚类所有对象，而DBSCAN 丢弃被它识别为噪声的对象。l K 均值使用簇的基于原形的概念，而DBSCAN 使用基于密度的概念。l DBSCAN 可以处理不同大小和不同形状的簇，并且不太受噪声和离群点的影响。K 均值很难处理非球状的簇和不同大小的簇。当簇具有很不同的密度时，两种算法的性能都很差。第1 页/共108 页l K 均值只能用于具有明确定义的质心（如均值或中位数）的数据。DBSCAN 要求密度定义（基于传统的欧几里得密度概念）对于数据是有意义的。l K 均值可以用于稀疏的高维数据，如文档数据，DBSCAN 通常在这类数据上性能很差，因为对于高维数据，传统的欧几里得密度定义不能很好处理。l K 均值和DBSCAN 的最初版本都是针对欧几里得数据设计的，但是它们都被扩展，以便处理其他类型的数据。第2 页/共108 页l DBSCAN 不对数据的分布做任何假定。基本k均值算法等价于一种统计聚类方法（混合模型），假定所有的簇都来自球形高斯分布，具有不同的均值，但具有相同的斜方差矩阵。l DBSCAN 和k均值都寻找使用所有属性的簇，即它们都不寻找可能只涉及某个属性子集的簇。l K 均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN 会合并有重叠的簇。l K 均值算法的时间复杂度是O（m），而DBSCAN的时间复杂度是O（m2）.第3 页/共108 页l DBSCAN 多次运行产生相同的结果，而k均值通常使用随机初始化质心，不会产生相同的结果。l DBSCAN 自动地确定簇个数；对于k均值，簇个数需要作为参数指定。然而，DBSCAN 必须指定另外两个参数：Eps 和Minptsl K 均值聚类可以看作优化问题，即最小化每个点到最近的质心的误差的平方和，并且可以看作一种统计聚类的特例。DBSCAN 不基于任何形式化模型。第4 页/共108 页数据特性l 高维性 随着维度的增加，体积迅速增加，除非点的个数也随着维度指数增加，否则密度将趋向于0.处理该问题的方法是使用维归约技术l 规模 许多聚类算法对于小规模和中等规模的数据集运行良好，但是不能处理大型数据集l 稀疏性 稀疏数据通常由非对称的属性组成，其中零值没有非零值重要。.第5 页/共108 页l 噪声和离群点 非常见点可能严重地降低聚类算法的性能，特别是k均值这样的基于原型的算法 另一方面，噪声也可能导致单链等技术合并两个不应当合并的簇。l 属性和数据集类型 属性可能是分类的（标称的或序数的）或定量的（区间的或比率的），二元的、离散的或连续的。不同的近邻性和密度度量适合于不同类型的数据。l 尺度 不同的属性，如高度和重量，可能用不同的尺度度量。这些差别可能严重影响两个对象之间的距离或相似性，从而影响聚类分析的结果。第6 页/共108 页簇特性l 数据分布 某些聚类技术假定数据具有特定的分布。更具体的说，它们常常假定可以用混合分布对数据建模，其中每个簇对应于一个分布。l 形状 有些簇具有规则的形状，如矩形和球形。但是，更一般地，簇可以具有任意形状。如DBSCAN 和单链等技术可以处理任意形状。基于原型的方法和一些层次聚类技术不能进行这样的处理。Chameleon 和cure 是专门用来处理这一问题的技术第7 页/共108 页l 不同大小 许多聚类算法，如k均值，当簇具有不同的大小时不能很好的处理l 不同密度 具有很不相同的密度的簇可能对诸如DBSCAN 和k均值等算法造成影响 基于SNN 密度的聚类技术可以处理这个问题l 无明显分离的簇 当簇接触或重叠时，有些聚类技术将应当分开的簇合并。甚至有些发现不同簇的技术随意地将点指派到一个或另一个簇。模糊聚类可以处理这一问题第8 页/共108 页l 簇之间的联系 在大部分聚类技术中，都不考虑簇之间的联系，如簇的相对位置 自组织映射（SOM）是一种在聚类期间直接考虑簇之间联系的聚类技术。l 子空间簇 簇可能只在维（属性）的一个子集中存在，并且使用一个维集合确定的簇可能也使用另一个维确定的簇很不相同。第9 页/共108 页聚类算法的一般特征l 次序依赖性 对于某些算法，所产生的簇的质量和个数可能因数据处理的次序不同而显著地变化。如SOMl 非确定性 有些算法不是次序依赖的，但是它们每次运行都产生不同的结果，因为它们依赖于需要随机选择的初始化步骤。l 变换聚类问题到其他领域 将聚类问题映射到一个不同的领域。如，基于图的聚类第10 页/共108 页l 可伸缩性 包含数以百万计对象的数据集并不罕见，而用于这种数据集的聚类算法应当具有线性或接近线性的时间或空间复杂度。对于大型数据集，即使具有O(m2)复杂度也是不切实际的。此外，数据集聚类技术不能总是假定数据放在内存，或者数据元素可以随机的访问。这样的算法对于大型数据集是不可行的。第11 页/共108 页l 参数选择 大部分聚类算法需要用户设置一个或多个参数。选择合适的参数值可能是困难的；因此，通常的态度是“参数越少越好”。l 将聚类作为最优化问题处理 聚类常常被看作优化问题。将点划分成簇，根据用户指定的目标函数度量，最大化结果簇集合的优良度。如k均值试图发现簇的集合，使得每个点到最近的簇质心距离的平方和最小。第12 页/共108 页基于原型的聚类l 模糊聚类l 使用混合模型的聚类l 自组织映射第13 页/共108 页模糊聚类l 模糊集合l 1965 年，Lotfi Zadeh 引进模糊集合论（fuzzy set theory）和模糊逻辑（fuzzy logic）作为一种处理不精确和不确定性的方法。l 简要的说，模糊集合论允许对象以0 和1 之间的某个隶属度属于一个集合，而模糊逻辑允许一个陈述以0 和1 之间的确定度为真。l 传统的集合论和逻辑是对应的模糊集合论和模糊逻辑的特殊情况，它们限制集合的隶属度或确定度或者为0，或者为1.第14 页/共108 页l 考虑如下模糊逻辑的例子l 陈述“天空多云”为真的程度可以定义为天空被云覆盖的百分比。例如，天空的50%被云覆盖，则“天空多云”为真的程度是0.5。l 如果我们有两个集合“多云天”和“非多云天”，则我们可以类似地赋予每一天隶属于这两个集合的程度。l 这样，如果一天25%多云，则它在“多云天”集合中具有0.25 的隶属度，而在“非多云天”集合中具有0.75 的隶属度。第15 页/共108 页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）。第16 页/共108 页l 给定点xi 的所有权值之和为1：l 每个簇Cj 以非零权值至少包含一个点，但不以权值1 包含所有的点第17 页/共108 页l 尽管存在多种模糊聚类，我们只考虑k均值的模糊版本，称作模糊c均值。l 在聚类文献中，那些不采用簇质心增量更新方法的k均值版本有时称为c均值。模糊c均值算法有时称为FCMl 算法9.1 基本模糊c均值算法 选择一个初始模糊伪划分，即对所有的wij 赋值 Repeat 使用模糊伪划分，计算每个簇的质心 重新计算模糊伪划分，即wij Until 质心不发生变化第18 页/共108 页l FCM 的结构类似于K 均值。K 均值可以看作FCM 的特例。l K 均值在初始化之后，交替地更新质心和指派每个对象到最近的质心。具体地说，计算模糊伪划分等价于指派步骤。l 与k均值一样，FCM 可以解释为试图最小化误差的平方和（SSE），尽管FCM 基于SSE 的模糊版本。第19 页/共108 页l 计算SSE 公式：其中cj 是第j 个簇的质心，而p 是确定权值影响的指数，在1 和 之间取值l 初始化 通常使用随机初始化。特殊地，权值随机的选取，同时限制与任何对象相关联的权值之和等于1。第20 页/共108 页l 计算质心 公式：模糊质心的定义类似于传统的质心定义，不同之处在于所有点都考虑，并且每个点对质心的贡献要根据它的隶属度加权。第21 页/共108 页l 更新模糊伪划分 公式:如果p2，则该指数降低赋予离点最近的簇的权值。事实上，随着p 趋向于无穷大，该指数趋向于0，而权值趋向于1/k。另一方面，随着p 趋向于1，该指数加大赋予离点最近的簇的权值。随着p 趋向于1，关于最近簇的隶属权值趋向于1，而关于其他簇的隶属权值趋向于0。这时对应于k均值。第22 页/共108 页例子：三个圆形簇上的模糊c 均值第23 页/共108 页优点与局限性l FCM 产生指示任意点属于任意簇的程度的聚类。l 它比K 均值算法计算复杂性高。l 除此之外，它与k均值算法具有相同的优点和缺点。第24 页/共108 页基于原型的聚类l 模糊聚类l 使用混合模型的聚类l 自组织映射第25 页/共108 页使用混合模型的聚类l 基于统计模型的聚类。通常，假定数据是由一个统计过程产生的，并且通过找出最佳拟合数据的统计模型来描述数据，其中统计模型用分布和该分布的一组参数描述。l 混合模型（mixture models）：它使用若干统计分布对数据建模。每个分布对应于一个簇，而每个分布的参数提供对应于簇的描述，通常用中心和发散描述。第26 页/共108 页第27 页/共108 页算法l 估计数据分布：确定分布：一般假设数据取自高斯混合分布。然后，对分布的参数进行估计：利用EM算法进行最大似然估计 利用直方图估计分布l 对分布进行划分、分离。每个分布对应于一个簇。第28 页/共108 页优点和缺点l 混合模型比k均值或模糊c均值更一般，因为它可以使用各种类型的分布。l 利用简单的估计分布的方法（如直方图）可能会错误估计数据的原始分布，导致结果不好。l 利用复杂的方法（如EM算法），计算复杂性会大大增加。第29 页/共108 页基于原型的聚类l 模糊聚类l 使用混合模型的聚类l 自组织映射第30 页/共108 页自组织映射l Kohonen 自组织特征映射（SOFM 或SOM）是一种基于神经网络观点的聚类和数据可视化技术。l 尽管SOM 源于神经网络，但是它可以表示成一种基于原形的聚类的变形。l 与其他基于质心的聚类技术一样，SOM 的目标是发现质心的集合，并将数据集中的每个对象指派到提供该对象最佳近似的质心。用神经网络的术语，每个质心都与一个神经元相关联。第31 页/共108 页SOM 算法l 初始化质心。l Repeatl 选择下一个对象l 确定到该对象最近的质心l 更新该质心和附近的质心，即在一个特定邻域 内的质心l Until 质心改变不多或超过某个域值l 指派每个对象到最近的质心，并返回质心和簇第32 页/共108 页基于密度的聚类l 基于网格的聚类l 子空间聚类l DENCLUE第33 页/共108 页基于网格的聚类l 网格是一种组织数据集的有效方法，至少在低维空间中如此。l 其基本思想是，将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合。每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值。l 存在许多利用网格进行聚类的方法，大部分方法是基于密度的。第34 页/共108 页例子第35 页/共108 页基于网格的算法l 定义一个网格单元集l 将对象指派到合适的单元，并计算每个单元的密度l 删除密度低于指定的阈值的单元l 由邻近的稠密单元组形成簇第36 页/共108 页l 定义网格单元 对于连续属性，定义网格单元相当于连续属性离散化。可将值划分为等宽的区间、等频的区间、使用聚类确定的区间。l 网格单元的密度 定义网格单元密度的自然方法是：定义网格单元的密度为该区域中的点数除以区域的体积。如果使用具有相同体积的网格单元，使得每个单元的点数直接度量单元的密度。第37 页/共108 页l 邻近的稠密单元组形成簇 密度阈值的设定是关键。如图9-10 和表9-2，如果密度阈值为9，则大簇的4 个部分将丢失。邻近单元？一个二维网格单元有4 个还是8 个邻接单元？第38 页/共108 页例子第39 页/共108 页优点与局限性l 算法运行速度较快，可达o(mlogm)。这使得它成为许多聚类算法的基础，如STING、GRIDCLUS、waveCluster、Bang-Clustering、CLIQUE 和MAFIA。l 网格单元形状选择影响聚类效果。如矩形网格单元不能准确地捕获圆形边界区域的密度。l 对于高维数据，基于网格的聚类效果较差。l 密度阈值的选择对算法效果影响较大。第40 页/共108 页基于密度的聚类l 基于网格的聚类l 子空间聚类l DENCLUE第41 页/共108 页l 迄今为止，所考虑的聚类技术都是使用所有的属性来发现簇。然而，如果仅考虑特征子集，则我们发现的簇可能因子空间不同而很不相同。l 有两个理由，子空间的簇可能是有趣的。数据关于少量属性的集合可能可以聚类，而关于其余属性是随机分布的。在某些情况下，在不同的维集合中存在不同的簇。l 例子：考虑记录不同时间、不同商品销售情况的数据集（时间是维，商品是对象）。某些商品对于特定的月份集（如夏天）可能表现出类似行为，但是不同的簇可能被不同的月份（维）刻画。第42 页/共108 页第43 页/共108 页第44 页/共108 页CLIQUE 算法l CLIQUE（Clustering In QUEst）是系统地发现子空间簇的基于网格的聚类算法。检查每个子空间寻找簇是不现实的，因为这样的子空间的数量是维度的指数。l 基于密度的簇的单调性：如果一个点集在k维上形成一个基于密度的簇，则相同的点集在这些维的所有可能的子集上也是基于密度的簇的一部分。第45 页/共108 页CLIQUE 算法l 找出对应于每个属性的一维空间中的所有稠密区域。这是稠密的一维单元的集合。l K 2l Repeatl 由稠密的k-1 维单元产生所有的候选稠密k维单元l 删除点数少于域值的单元l k k+1l Until 不存在候选稠密k维单元l 通过取所有邻接的、高密度的单元的并发现簇l 使用一小组描述簇中单元的属性值域的不等式概括每一个簇。第46 页/共108 页CLIQUE 的优点与局限性l CLIQUE 最大特点是，它提供了一种搜索子空间发现簇的有效技术。由于这种方法基于关联分析的先验原理，它的性质能够被很好地解释。l CLIQUE 能够用一小组不等式概括构成一个簇的单元列表。l CLIQUE 的局限性与其他基于密度的方法和Apriori算法相同。如，CLIQUE 发现的簇可以共享对象。允许簇重叠可能大幅度增加簇的个数，并使得解释更加困难。Apriori 具有指数级的复杂度。第47 页/共108 页基于密度的聚类l 基于网格的聚类l 子空间聚类l DENCLUE第48 页/共108 页DENCLUE：基于密度聚类的一种基于核的方案l DENCLUE(DENsity CLUstEring)是一种基于密度的聚类方法，它用与每个点相关联的影响函数之和对点集的总密度建模。结果总密度函数将具有局部尖峰，并且这些局部尖峰用来以自然的方式定义簇。l 具体的说，对于每个数据点，一个爬山过程找出与该点相关联的最近的尖峰，并且与一个特定的尖峰（称作局部密度吸引点（local density attractor）相关联的所有数据点成为一个簇。l 如果局部尖峰处的密度太低，则相关联的簇中的点将被视为噪声而丢弃。l 如果一个局部尖峰通过一条数据点路径与另一个局部尖峰相连接，并且该路径上每个点的密度都高于最小密度阈值，则与这些局部尖峰相关联的簇合并在一起。第49 页/共108 页第50 页/共108 页DENCLUE 算法l 对数据点占据的空间推导密度函数l 识别局部最大点（即密度吸引点）l 通过沿密度增长最大的方向移动，将每个点关联到一个密度吸引点l 定义与特定的密度吸引点相关联的点构成的簇l 丢弃密度吸引点的密度小于用户指定阈值的簇l 合并通过密度大于或等于阈值的点路径连接的簇第51 页/共108 页核密度估计l 核密度估计用函数描述数据的分布。每个点对总密度函数的贡献用一个核函数表示。总密度函数仅仅是与每个点相关联的核函数之核l 核函数是对称的，并且它的值随到点的距离增加而下降。高斯函数常常用作核函数：第52 页/共108 页第53 页/共108 页DENCLUE 的优点与局限性l DENCLUE 具有坚实的理论基础，因为它基于统计学发展完善的领域-核密度函数和核密度估计。因此，DENCLUE 提供了比其他基于网络的聚类技术和DBSCAN 更加灵活、更加精确的计算密度的方法。（DBSCAN 是DENCLUE 的特例）l 基于核密度函数的方法本质上是计算昂贵的，但DENCLUE 使用基于网格的技术来处理该问题。尽管如此，DENCLUE 可能比其他基于密度的聚类技术的计算开销更大。l DENCLUE 具有其他基于密度的方法的优缺点。第54 页/共108 页基于图的聚类l 最小生成树聚类l OPOSSUMl Chameleonl Jarvis-Patrick 聚类算法l 基于SNN 密度的聚类第55 页/共108 页稀疏化l m 个数据点的mm 邻近度矩阵可以用一个稠密图表示，每个节点与其他所有点相连，权值反映邻近性。l 尽管每个对象与其他每个对象都有某种程度的近邻性，但是对于大部分数据集，对象只与少量对象高度相似，而与大部分其他对象的相似性很弱。这一性质用来稀疏化邻近度图。l 稀疏化可以这样进行：断开相似度低于指定阈值的边、或仅保留连接到点的k个近邻的边。第56 页/共108 页稀疏化的好处l 压缩了数据量l 可以更好的聚类 稀疏化技术保持了对象与最近邻的连接，断开与较远对象的连接。这与最近邻原理一致，对象的最近邻趋向于与对象在同一个类。这降低了噪声和离群点的影响，增强了簇之间的差别。l 可以使用图划分算法第57 页/共108 页l 应当把邻近度图的稀疏化看成使用实际聚类算法之前的初始化步骤。l 理论上讲，一个完美的稀疏化应当将邻近度图划分成对应于期望簇的连通分支，但实际中这很难做到。很容易出现单条边连接两个簇，或者单个簇被分裂成若干个不相连接的子簇的情况。第58 页/共108 页基于图的聚类l 最小生成树聚类l OPOSSUMl Chameleonl Jarvis-Patrick 聚类算法l 基于SNN 密度的聚类第59 页/共108 页最小生成树聚类（minimum spanning tree，MST）l 计算相异度图的最小生成树l Repeatl 断开对应于最大相异度的边，创建一个新的簇l Until 只剩下单个簇l 最小生成树聚类是一种基于分裂的层次聚类算法l 最小生成树聚类可以看作用稀疏化找出簇的方法第60 页/共108 页第61 页/共108 页基于图的聚类l 最小生成树聚类l OPOSSUMl Chameleonl Jarvis-Patrick 聚类算法l 基于SNN 密度的聚类第62 页/共108 页OPOSSUM：使用METIS 的稀疏相似度最优划分l OPOSSUM（Optimal Partitioning of Sparse Similarities Using METIS）是一种专门为诸如文档或购物篮数据等稀疏、高维数据设计的聚类技术。与MST 一样，它基于邻近度图的稀疏化进行聚类。然而，OPOSSUM 使用METIS 算法，该算法是专门为划分图设计的。l OPOSSUM 聚类算法l 1：计算稀疏化的相似度图l 2：使用METIS，将相似度图划分成k个不同的分支（簇）第63 页/共108 页 l 所使用的相似性度量是适合于稀疏、高维数据的度量，如扩充的Jaccard 度量或余弦度量。l METIS 图划分程序将稀疏图划分为k个不同的分支，其中k是用户指定的参数，旨在（1）最小化分支之间边的权值（2）实现平衡约束。OPOSSUM 使用如下两种约束中的一种：（1）每个簇中的对象个数必须粗略相等，或（2）属性值的和必须粗略相等。第64 页/共108 页优点与缺点l OPOSSUM 简单、速度快。l 它将数据划分大小粗略相等的簇。根据聚类的目标这可能看作优点或缺点。第65 页/共108 页基于图的聚类l 最小生成树聚类l OPOSSUMl Chameleonl Jarvis-Patrick 聚类算法l 基于SNN 密度的聚类第66 页/共108 页Chameleon第67 页/共108 页第68 页/共108 页l Chameleon 是一种凝聚聚类技术，它解决前两段提到的问题。它将数据的初始划分与一种新颖的层次聚类方案相结合。l 这种层次聚类使用接近性和互连性概念以及簇的局部建模。关键思想是：仅当合并后的结果簇类似于原来的两个簇时，这两个簇才应当合并。第69 页/共108 页确定合并哪些簇l 相对接近度（relative closeness，RC）：是被簇的内部接近度规范化的两个簇的绝对接近度。两个簇合并，仅当结果簇中的点之间的接近程度几乎与原来的每个簇一样。l mi 和mj 分别是簇ci 和cj 的大小。SEC（ci，cj）是连接簇ci和cj 的边的平均值；SEC（ci）是二分簇ci 的边的平均权值。第70 页/共108 页l 相对互连度（relative interconnectivity,RI）：是被簇的内部互连度规范化的两个簇的绝对互连度。如果结果簇中的点之间的连接几乎与原来的每个簇一样强，两个簇合并。l 其中，EC（Ci，Cj）是连接簇Ci 和Cj 的边之和；EC(Ci)是二分簇Ci 的割边的最小和；EC(Cj)是二分簇Cj 的割边的最小和。l RI和RC 可以用多种不同的方法组合，产生自相似性的总量。Chameleon 使用的方法是合并最大化RI(Ci,Cj)*RC(Ci,Cj)a簇对。其中a 值大于1.第71 页/共108 页Limitations of Current Merging SchemesRelative Closeness schemes will merge(a)and(b)(a)(b)(c)(d)Relative interconnectivity schemes will merge(c)and(d)第72 页/共108 页Chameleon 算法l 构造k-最近邻图l 使用多层图划分算法划分图l Repeatl 合并关于相对互连性和相对接近性而言，最好 地保持簇的自相似性的簇l Until 不再有可以合并的簇第73 页/共108 页例子第74 页/共108 页第75 页/共108 页第76 页/共108 页优点与局限性l Chameleon 能够有效地聚类空间数据，即便存在噪声和离群点，并且簇具有不同的形状、大小和密度。l Chameleon 假定由稀疏化和图划分过程产生的对象组群是子簇，即一个划分中的大部分点属于同一个真正的簇。如果不是，则凝聚层次聚类将混合这些错误，因为它绝对不可能再将已经错误地放到一起的对象分开。这样，当划分过程未产生子簇时，chameleon 就有问题，对于高维数据，常常出现这种情况。第77 页/共108 页共享最近邻相似性l SNN（shared nearest neighbor）相似度计算：l 1.找出所有点的k-近邻l 2.If 两个点x和y不是相互在对方的k-最近邻中 thenl 3.similarity(x,y)0l 4.Elsel 5.similarity(x,y)共享的近邻个数l 6.End if第78 页/共108 页第79 页/共108 页l SNN 相似度由于通过使用共享最近邻的个数考虑了对象的环境，SNN 相似度可以处理一个对象碰巧与另一对象相对接近，但属于不同的类。在这种情况下，对象一般不共享许多近邻，并且它们的SNN 相似度低。l SSN 相似度也能处理变密度簇的问题。在低密度区域，对象比高密度区域的对象分开得更远。然而，一对点之间的SNN 相似度只依赖于两个对象共享的最近邻的个数，而不是这些近邻之间的相距多远。SNN 关于点的密度进行自动缩放。第80 页/共108 页基于图的聚类l 最小生成树聚类l OPOSSUMl Chameleonl Jarvis-Patrick 聚类算法l 基于SNN 密度的聚类第81 页/共108 页Jarvis-Patrick（JP）聚类算法l 计算SNN 相似度图l 使用相似度阈值，稀疏化SNN 相似度图l 找出稀疏化的SNN 相似度图的连通分支第82 页/共108 页第83 页/共108 页优点与局限性l 因为JP 聚类基于SNN 相似度概念，它擅长于处理噪声和离群点，并且能够处理不同大小、形状和密度的簇。l 该算法对高维数据效果良好，尤其擅长发现强相关对象的紧密簇。l JP 聚类把簇定义为SNN 相似度图的连通分支。这样，一个对象集是分裂成两个簇还是作为一个簇留下，可能依赖于一条链。第84 页/共108 页第85 页/共108 页基于SNN 密度的聚类l 算法：l 计算SNN 相似度图l 以用户指定的参数Eps 和MinPts，使用DBSCANl SNN 密度的聚类算法比Jarvis-Patrick 聚类或DBSCAN 更加灵活。l 不象DBSCAN，它可以用于高维数据和簇具有不同密度的情况。l 不象Jarvis-Patrick 聚类简单地使用域值，然后取连通分支作为簇，基于SNN 密度的聚类使用基于SNN 密度和核心点概念的方法。第86 页/共108 页l 核心点：一个点是核心点，如果在该点给定邻域内的点数超过某个阈值MinPts。l 边界点。边界点不是核心点，但是它落在一个核心点的邻域内。l 噪声点是既非核心点，也非边界点的任何点。第87 页/共108 页SNN Density a)All Points b)High SNN Densityc)Medium SNN Density d)Low SNN Density第88 页/共108 页例子：解释该算法处理高维数据能力SNN Clusters of SLP.SNN Density of Points on the Globe.l 41 年期间，在2.5 度的经纬度网格的每个点上的月平均海平面气压（SLP）第89 页/共108 页优点与局限性l 基于SNN 密度的聚类的优点与局限性类似于JP 聚类。l 然而，核心点和SNN 密度的使用大大增加了该方法的能力和灵活性。第90 页/共108 页可伸缩：一般问题和方法l BIRCHl CURE第91 页/共108 页l 如果运行时间长得不可接受，或者需要的存储量太大，即使最好的聚类算法也没有多大价值。l 许多聚类算法所需要的存储量都是非线性的。例如：使用层次聚类，存储需求一般是O(m2)。类似地，有些聚类算法所需要的计算量也是非线性的。l 可伸缩性可以通过如下技术实现：多维或空间存取方法、邻近度约束、抽样、划分数据对象、汇总、并行与分布计算。第92 页/共108 页CUREl CURE（Clustering Using REpresentative）是一种聚类算法，它使用各种不同的技术创建一种能够处理大型数据、离群点、具有非球形和非均匀大小的簇的数据的方法。l CURE 使用簇中的多个代表点来表示一个簇。理论上，这些点捕获了簇的几何形状。l 具体来说，第一个代表点选择离簇中心最远的点，而其余的点选择离所有已经选取的点最远的点。这样，代表点相对分离。l 选取的点的个数是一个参数，但是一般取10 效果较好。第93 页/共108 页l 一旦选定代表点，它们就以因子a 向簇中心收缩。这有助于减轻离群点的影响。l 例如，一个到中心的距离为10 个单位的代表点将移动3 个单位（对于a=0.7），而到中心距离为1 个单位的代表点仅移动0.3 个单位。第94 页/共108 页l CURE 使用一种凝聚层次聚类方案进行实际的聚类。两个簇之间的距离是任意两个代表点（在它们向它们代表点的中心收缩之后）之间的最短距离。l 如果a=0，它等价于基于质心的层次聚类；a=1 时，它与单链层次聚类大致相同。l 注意，尽管使用层次聚类方案，但是CURE 的目标是发现用户指定个数的簇。第95 页/共108 页l CURE 在聚类过程的两个不同阶段删除离群点。首先，如果一个簇增长缓慢，则这意味它主要由离群点组成，因为根据定义，离群点远离其他点，并且不会经常与其他点合并。l 在CURE 中，离群点删除的第一个阶段一般出现在簇的个数是原来点数的1/3 时。第二个离群点删除阶段出现在簇的个数达到K 的量级时。此时，小簇又被删除。第96 页/共108 页l CURE 在最坏情况下复杂度为O(m2logm)，它不能直接用于大型数据集。因此，CURE 使用了两种技术来加快聚类过程。l 第一种技术是取随机样本，并在抽样的数据点上进行层次聚类。随后是最终扫描，将数据集中剩余的点指派到簇中。l 在某些情况下，聚类所需要的样本仍然太大，需要第二种技术解决。在这种情况下，CURE 划分样本数据，然后聚类每个划分中的点。这种预聚类步后通常紧随中间簇的聚类，以及将数据集中的每个点指派到一个簇的最终扫描。第97 页/共108 页CURE 算法l 由数据集抽取一个随机样本集。l 将样本集划分成p 个大小相同的划分。l 使用CURE 的层次聚类算法，将每个划分中的点聚类成m/pq 个簇，得到总共m/q 个簇。l 使用CURE 的层次聚类算法对上一步发现的m/q 个簇进行聚类，直到只剩下k个簇。l 删除离群点。l 将所有剩余的数据点指派到最近的簇，得到完全聚类。第98 页/共108 页l K 是期望的簇个数，m 是点的个数，p 是划分的个数，而q 是一个划分中的点的期望压缩，即一个划分中的簇的个数是m/pq，簇的总数是m/ql 例如，如果m=10000，p=10 并且q=100，则每个划分包含10000/10=1000 个点，每个划分有1000/100=10 个簇，而总共有10000/100=100 个簇。第99 页/共108 页CURE 的抽样l CURE 抽样尽力确保抽到每个簇的样本。为了保证这样的抽样，CURE 的作者推算出了能够实现这一保证的样本集大小的上界。l S 为我们应该抽取的样本大小l 假设有100000 个对象，我们的目标是以80%的可能性得到10%的Ci 簇对象，其中Ci 的大小是1000。在此情况下，f=0.1，=0.2，m=100000，这样s=11962。l S=11962是为了以80%的概率得到10%的Ci簇对象，需要抽取的样本大小第100 页/共108 页划分l 将点划分成p 个大小为m/p 的组，使用CURE 对每个划分聚类，将对象的个数压缩一个因子q1,其中q可以粗略地看作划分中的簇的平均大小。总共产生m/q 个簇。然后，预聚类后随m/q 个中间簇的最终聚类，产生期望的簇个数。两遍聚类都使用CURE的层次聚类算法，而最后一遍将数据集中的每个点指派到一个簇。l P 和q 的选取是关键。应尽力选择合适的p，使得整个划分可以以合理的时间在内存处理。此外，应尽力选择合适的p 和q 使得同一基本簇的对象最终在一个簇中。第101 页/共108 页第102 页/共108 页第103 页/共108 页l 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).第104 页/共108 页第105 页/共108 页使用哪种聚类算法？l 聚类的类型l 簇的类型l 簇的特性l 数据集和属性的特征噪声和离群点l 数据对象的个数l 属性的个数l 簇描述l 算法考虑第106 页/共108 页l 数据l 探索数据l 分类：基本概念、决策树与模型评估l 分类：其他技术l 关联分析：基本概念和算法l 关联分析：高级概念l 聚类分析：基本概念和算法l 聚类分析：附加问题与算法l 异常检测第107 页/共108 页感谢您的观看。第108 页/共108 页