第9章附加问题与算法ppt课件

聚类分析：附加的问题与算法聚类分析：附加的问题与算法第第9章章 聚类分析：附加的问题与算法聚类分析：附加的问题与算法l在各种领域，针对不同的运用类型，曾经开发了大量聚类算法。在这些算法中没有一种算法可以顺应一切的数据类型、簇和运用。l现实上，对于更加有效或者更适宜特定数据类型、簇和运用的新的聚类算法，看来总是有进一步的开发空间。l我们只能说我们曾经有了一些技术，对于某些情况运转良好。其缘由是，在许多情况下，对于什么是一个好的簇集，依然凭客观解释。此外，当运用客观度量准确地定义簇时，发现最优聚类问题经常是计算不可行的。比较比较k均值和均值和DBSCANlDBSCAN和k均值都是将每个对象指派到单个簇的划分聚类算法，但是K均值普通聚类一切对象，而DBSCAN丢弃被它辨以为噪声的对象。lK均值运用簇的基于原形的概念，而DBSCAN运用基于密度的概念。lDBSCAN可以处置不同大小和不同外形的簇，并且不太受噪声和离群点的影响。K均值很难处置非球状的簇和不同大小的簇。当簇具有很不同的密度时，两种算法的性能都很差。lK均值只能用于具有明确定义的质心如均值或中位数的数据。DBSCAN要求密度定义基于传统的欧几里得密度概念对于数据是有意义的。lK均值可以用于稀疏的高维数据，如文档数据，DBSCAN通常在这类数据上性能很差，由于对于高维数据，传统的欧几里得密度定义不能很益处置。lK均值和DBSCAN的最初版本都是针对欧几里得数据设计的，但是它们都被扩展，以便处置其他类型的数据。lDBSCAN不对数据的分布做任何假定。根本k均值算法等价于一种统计聚类方法混合模型，假定一切的簇都来自球形高斯分布，具有不同的均值，但具有一样的斜方差矩阵。lDBSCAN和k均值都寻觅运用一切属性的簇，即它们都不寻觅能够只涉及某个属性子集的簇。lK均值可以发现不是明显分别的簇，即使簇有重叠也可以发现，但是DBSCAN会合并有重叠的簇。lK均值算法的时间复杂度是Om，而DBSCAN的时间复杂度是Om2.lDBSCAN多次运转产生一样的结果，而k均值通常运用随机初始化质心，不会产生一样的结果。lDBSCAN自动地确定簇个数；对于k均值，簇个数需求作为参数指定。然而，DBSCAN必需指定另外两个参数：Eps和MinptslK均值聚类可以看作优化问题，即最小化每个点到最近的质心的误差的平方和，并且可以看作一种统计聚类的特例。DBSCAN不基于任何方式化模型。数据特性数据特性l高维性l随着维度的添加，体积迅速添加，除非点的个数也随着维度指数添加，否那么密度将趋向于0.l处置该问题的方法是运用维归约技术l规模l许多聚类算法对于小规模和中等规模的数据集运转良好，但是不能处置大型数据集l稀疏性l稀疏数据通常由非对称的属性组成，其中零值没有非零值重要。.l噪声和离群点l非常见点能够严重地降低聚类算法的性能，特别是k均值这样的基于原型的算法l另一方面，噪声也能够导致单链等技术合并两个不该当合并的簇。l属性和数据集类型l属性能够是分类的标称的或序数的或定量的区间的或比率的，二元的、离散的或延续的。l不同的近邻性和密度度量适宜于不同类型的数据。l尺度l不同的属性，如高度和分量，能够用不同的尺度度量。这些差别能够严重影响两个对象之间的间隔或类似性，从而影响聚类分析的结果。簇特性簇特性l数据分布l某些聚类技术假定数据具有特定的分布。更详细的说，它们经常假定可以用混合分布对数据建模，其中每个簇对应于一个分布。l外形l有些簇具有规那么的外形，如矩形和球形。但是，更普通地，簇可以具有任不测形。l如DBSCAN和单链等技术可以处置任不测形。基于原型的方法和一些层次聚类技术不能进展这样的处置。lChameleon和cure是专门用来处置这一问题的技术l不同大小l许多聚类算法，如k均值，当簇具有不同的大小时不能很好的处置l不同密度l具有很不一样的密度的簇能够对诸如DBSCAN和k均值等算法呵斥影响l基于SNN密度的聚类技术可以处置这个问题l无明显分别的簇l当簇接触或重叠时，有些聚类技术将该当分开的簇合并。甚至有些发现不同簇的技术随意地将点指派到一个或另一个簇。l模糊聚类可以处置这一问题l簇之间的联络l在大部分聚类技术中，都不思索簇之间的联络，如簇的相对位置l自组织映射SOM是一种在聚类期间直接思索簇之间联络的聚类技术。l子空间簇l簇能够只在维属性的一个子集中存在，并且运用一个维集合确定的簇能够也运用另一个维确定的簇很不一样。聚类算法的普通特征聚类算法的普通特征l次序依赖性l对于某些算法，所产生的簇的质量和个数能够因数据处置的次序不同而显著地变化。如SOMl非确定性l有些算法不是次序依赖的，但是它们每次运转都产生不同的结果，由于它们依赖于需求随机选择的初始化步骤。l变换聚类问题到其他领域l将聚类问题映射到一个不同的领域。如，基于图的聚类l可伸缩性l包含数以百万计对象的数据集并不稀有，而用于这种数据集的聚类算法该当具有线性或接近线性的时间或空间复杂度。l对于大型数据集，即使具有O(m2)复杂度也是不真实践的。l此外，数据集聚类技术不能总是假定数据放在内存，或者数据元素可以随机的访问。这样的算法对于大型数据集是不可行的。l参数选择l大部分聚类算法需求用户设置一个或多个参数。选择适宜的参数值能够是困难的；因此，通常的态度是“参数越少越好。l将聚类作为最优化问题处置l聚类经常被看作优化问题。将点划分成簇，根据用户指定的目的函数度量，最大化结果簇集合的优良度。如k均值试图发现簇的集合，使得每个点到最近的簇质心间隔的平方和最小。基于原型的聚类基于原型的聚类l模糊聚类l运用混合模型的聚类l自组织映射模糊聚类模糊聚类l模糊集合l1965年，Lotfi Zadeh引进模糊集合论fuzzy set theory和模糊逻辑fuzzy logic作为一种处置不准确和不确定性的方法。l简要的说，模糊集合论允许对象以0和1之间的某个隶属度属于一个集合，而模糊逻辑允许一个陈说以0和1之间确实定度为真。l传统的集合论和逻辑是对应的模糊集合论和模糊逻辑的特殊情况，它们限制集合的隶属度或确定度或者为0，或者为1.l思索如下模糊逻辑的例子l陈说“天空多云为真的程度可以定义为天空被云覆盖的百分比。例如，天空的50%被云覆盖，那么“天空多云为真的程度是0.5。l假设我们有两个集合“多云天和“非多云天，那么我们可以类似地赋予每一天隶属于这两个集合的程度。l这样，假设一天25%多云，那么它在“多云天集合中具有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虽然存在多种模糊聚类，我们只思索k均值的模糊版本，称作模糊c均值。l在聚类文献中，那些不采用簇质心增量更新方法的k均值版本有时称为c均值。模糊c均值算法有时称为FCMl算法9.1 根本模糊c均值算法l选择一个初始模糊伪划分，即对一切的wij赋值lRepeatl 运用模糊伪划分，计算每个簇的质心l 重新计算模糊伪划分，即wijlUntil 质心不发生变化lFCM的构造类似于K均值。K均值可以看作FCM的特例。lK均值在初始化之后，交替地更新质心和指派每个对象到最近的质心。详细地说，计算模糊伪划分等价于指派步骤。l与k均值一样，FCM可以解释为试图最小化误差的平方和SSE，虽然FCM基于SSE的模糊版本。l计算SSEl公式：l其中cj是第j个簇的质心，而p是确定权值影响的指数，在1和之间取值l初始化l通常运用随机初始化。特殊地，权值随机的选取，同时限制与任何对象相关联的权值之和等于1。kjmijipijkcxdistwCCCSSE11221),(),.,(l计算质心l公式：l模糊质心的定义类似于传统的质心定义，不同之处在于一切点都思索，并且每个点对质心的奉献要根据它的隶属度加权。mipijmiipijjwxwc11l更新模糊伪划分l公式:l假设p2，那么该指数降低赋予离点最近的簇的权值。现实上，随着p趋向于无穷大，该指数趋向于0，而权值趋向于1/k。l另一方面，随着p趋向于1，该指数加大赋予离点最近的簇的权值。随着p趋向于1，关于最近簇的隶属权值趋向于1，而关于其他簇的隶属权值趋向于0。这时对应于k均值。kqpqipjiijcxdistcxdistw1112112),(/1(),(/1(例子：三个圆形簇上的模糊例子：三个圆形簇上的模糊c均值均值优点与局限性优点与局限性lFCM产生指示恣意点属于恣意簇的程度的聚类。l它比K均值算法计算复杂性高。l除此之外，它与k均值算法具有一样的优点和缺陷。基于原型的聚类基于原型的聚类l模糊聚类l运用混合模型的聚类l自组织映射运用混合模型的聚类运用混合模型的聚类l基于统计模型的聚类。通常，假定数据是由一个统计过程产生的，并且经过找出最正确拟合数据的统计模型来描画数据，其中统计模型用分布和该分布的一组参数描画。l混合模型mixture models：它运用假设干统计分布对数据建模。每个分布对应于一个簇，而每个分布的参数提供对应于簇的描画，通常用中心和发散描画。算法算法l估计数据分布：l确定分布：普通假设数据取自高斯混合分布。然后，对分布的参数进展估计：利用EM算法进展最大似然估计l利用直方图估计分布l对分布进展划分、分别。每个分布对应于一个簇。优点和缺陷优点和缺陷l混合模型比k均值或模糊c均值更普通，由于它可以运用各种类型的分布。l利用简单的估计分布的方法如直方图能够会错误估计数据的原始分布，导致结果不好。l利用复杂的方法如EM算法，计算复杂性会大大添加。基于原型的聚类基于原型的聚类l模糊聚类l运用混合模型的聚类l自组织映射自组织映射自组织映射lKohonen自组织特征映射SOFM或SOM是一种基于神经网络观念的聚类和数据可视化技术。l虽然SOM源于神经网络，但是它可以表示成一种基于原形的聚类的变形。l与其他基于质心的聚类技术一样，SOM的目的是发现质心的集合，并将数据集中的每个对象指派到提供该对象最正确近似的质心。用神经网络的术语，每个质心都与一个神经元相关联。SOM算法算法l初始化质心。lRepeatl 选择下一个对象l 确定到该对象最近的质心l 更新该质心和附近的质心，即在一个特定邻域 l 内的质心lUntil 质心改动不多或超越某个域值l指派每个对象到最近的质心，并前往质心和簇基于密度的聚类基于密度的聚类l基于网格的聚类l子空间聚类lDENCLUE基于网格的聚类基于网格的聚类l网格是一种组织数据集的有效方法，至少在低维空间中如此。l其根本思想是，将每个属性的能够值分割成许多相邻的区间，创建网格单元的集合。每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值。l存在许多利用网格进展聚类的方法，大部分方法是基于密度的。例子例子基于网格的算法基于网格的算法l定义一个网格单元集l将对象指派到适宜的单元，并计算每个单元的密度l删除密度低于指定的阈值的单元l由临近的稠密单元组构成簇l定义网格单元l对于延续属性，定义网格单元相当于延续属性离散化。可将值划分为等宽的区间、等频的区间、运用聚类确定的区间。l网格单元的密度l定义网格单元密度的自然方法是：定义网格单元的密度为该区域中的点数除以区域的体积。l假设使器具有一样体积的网格单元，使得每个单元的点数直接度量单元的密度。l临近的稠密单元组构成簇l密度阈值的设定是关键。如图9-10和表9-2，假设密度阈值为9，那么大簇的4个部分将丧失。l临近单元？一个二维网格单元有4个还是8个邻接单元？例子例子优点与局限性优点与局限性l算法运转速度较快，可达o(mlogm)。这使得它成为许多聚类算法的根底，如STING、GRIDCLUS、waveCluster、Bang-Clustering、CLIQUE和MAFIA。l网格单元外形选择影响聚类效果。如矩形网格单元不能准确地捕获圆形边境区域的密度。l对于高维数据，基于网格的聚类效果较差。l密度阈值的选择对算法效果影响较大。基于密度的聚类基于密度的聚类l基于网格的聚类l子空间聚类lDENCLUEl迄今为止，所思索的聚类技术都是运用一切的属性来发现簇。然而，假设仅思索特征子集，那么我们发现的簇能够因子空间不同而很不一样。l有两个理由，子空间的簇能够是有趣的。l数据关于少量属性的集合能够可以聚类，而关于其他属性是随机分布的。l在某些情况下，在不同的维集合中存在不同的簇。l例子：思索记录不同时间、不同商品销售情况的数据集时间是维，商品是对象。某些商品对于特定的月份集如夏天能够表现出类似行为，但是不同的簇能够被不同的月份维描写。CLIQUE算法算法lCLIQUEClustering In QUEst是系统地发现子空间簇的基于网格的聚类算法。检查每个子空间寻觅簇是不现实的，由于这样的子空间的数量是维度的指数。l基于密度的簇的单调性：假设一个点集在k维上构成一个基于密度的簇，那么一样的点集在这些维的一切能够的子集上也是基于密度的簇的一部分。CLIQUE算法算法l找出对应于每个属性的一维空间中的一切稠密区域。这是稠密的一维单元的集合。lK2lRepeatl 由稠密的k-1维单元产生一切的候选稠密k维单元l 删除点数少于域值的单元l kk+1lUntil 不存在候选稠密k维单元l经过取一切邻接的、高密度的单元的并发现簇l运用一小组描画簇中单元的属性值域的不等式概括每一个簇。CLIQUE的优点与局限性的优点与局限性lCLIQUE最大特点是，它提供了一种搜索子空间发现簇的有效技术。由于这种方法基于关联分析的先验原理，它的性质可以被很好地解释。lCLIQUE可以用一小组不等式概括构成一个簇的单元列表。lCLIQUE的局限性与其他基于密度的方法和Apriori算法一样。如，CLIQUE发现的簇可以共享对象。允许簇重叠能够大幅度添加簇的个数，并使得解释更加困难。Apriori具有指数级的复杂度。基于密度的聚类基于密度的聚类l基于网格的聚类l子空间聚类lDENCLUEDENCLUE：基于密度聚类的一种基于核的方案：基于密度聚类的一种基于核的方案lDENCLUE(DENsity CLUstEring)是一种基于密度的聚类方法，它用与每个点相关联的影响函数之和对点集的总密度建模。结果总密度函数将具有部分尖峰，并且这些部分尖峰用来以自然的方式定义簇。l详细的说，对于每个数据点，一个爬山过程找出与该点相关联的最近的尖峰，并且与一个特定的尖峰称作部分密度吸引点local density attractor相关联的一切数据点成为一个簇。l假设部分尖峰处的密度太低，那么相关联的簇中的点将被视为噪声而丢弃。l假设一个部分尖峰经过一条数据点途径与另一个部分尖峰相衔接，并且该途径上每个点的密度都高于最小密度阈值，那么与这些部分尖峰相关联的簇合并在一同。DENCLUE算法算法l对数据点占据的空间推导密度函数l识别部分最大点即密度吸引点l经过沿密度增长最大的方向挪动，将每个点关联到一个密度吸引点l定义与特定的密度吸引点相关联的点构成的簇l丢弃密度吸引点的密度小于用户指定阈值的簇l合并经过密度大于或等于阈值的点途径衔接的簇核密度估计核密度估计l核密度估计用函数描画数据的分布。每个点对总密度函数的奉献用一个核函数表示。总密度函数仅仅是与每个点相关联的核函数之核l核函数是对称的，并且它的值随到点的间隔添加而下降。高斯函数经常用作核函数：222/),(tan)(yxcediseykDENCLUE的优点与局限性的优点与局限性lDENCLUE具有坚实的实际根底，由于它基于统计学开展完善的领域-核密度函数和核密度估计。因此，DENCLUE提供了比其他基于网络的聚类技术和DBSCAN更加灵敏、更加准确的计算密度的方法。DBSCAN是DENCLUE的特例l基于核密度函数的方法本质上是计算昂贵的，但DENCLUE运用基于网格的技术来处置该问题。虽然如此，DENCLUE能够比其他基于密度的聚类技术的计算开销更大。lDENCLUE具有其他基于密度的方法的优缺陷。基于图的聚类基于图的聚类l最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法l基于SNN密度的聚类稀疏化稀疏化lm个数据点的mm临近度矩阵可以用一个稠密图表示，每个节点与其他一切点相连，权值反映临近性。l虽然每个对象与其他每个对象都有某种程度的近邻性，但是对于大部分数据集，对象只与少量对象高度类似，而与大部分其他对象的类似性很弱。这一性质用来稀疏化临近度图。l稀疏化可以这样进展：断开类似度低于指定阈值的边、或仅保管衔接到点的k个近邻的边。稀疏化的益处稀疏化的益处l紧缩了数据量l可以更好的聚类l稀疏化技术坚持了对象与最近邻的衔接，断开与较远对象的衔接。这与最近邻原理一致，对象的最近邻趋向于与对象在同一个类。这降低了噪声和离群点的影响，加强了簇之间的差别。l可以运用图划分算法l该当把临近度图的稀疏化看成运用实践聚类算法之前的初始化步骤。l实际上讲，一个完美的稀疏化该当将临近度图划分成对应于期望簇的连通分支，但实践中这很难做到。很容易出现单条边衔接两个簇，或者单个簇被分裂成假设干个不相衔接的子簇的情况。基于图的聚类基于图的聚类l最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法l基于SNN密度的聚类最小生成树聚类最小生成树聚类minimum spanning tree，MSTl计算相异度图的最小生成树lRepeatl 断开对应于最大相异度的边，创建一个新的簇lUntil 只剩下单个簇l最小生成树聚类是一种基于分裂的层次聚类算法l最小生成树聚类可以看作用稀疏化找出簇的方法基于图的聚类基于图的聚类l最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法l基于SNN密度的聚类OPOSSUM：运用：运用METIS的稀疏类似度最优划分的稀疏类似度最优划分lOPOSSUMOptimal Partitioning of Sparse Similarities Using METIS是一种专门为诸如文档或购物篮数据等稀疏、高维数据设计的聚类技术。与MST一样，它基于临近度图的稀疏化进展聚类。然而，OPOSSUM运用METIS算法，该算法是专门为划分图设计的。lOPOSSUM聚类算法l1：计算稀疏化的类似度图l2：运用METIS，将类似度图划分成k个不同的分支簇 l所运用的类似性度量是适宜于稀疏、高维数据的度量，如扩展的Jaccard度量或余弦度量。lMETIS图划分程序将稀疏图划分为k个不同的分支，其中k是用户指定的参数，旨在1最小化分支之间边的权值2实现平衡约束。OPOSSUM运用如下两种约束中的一种：1每个簇中的对象个数必需粗略相等，或2属性值的和必需粗略相等。优点与缺陷优点与缺陷lOPOSSUM简单、速度快。l它将数据划分大小粗略相等的簇。根据聚类的目的这能够看作优点或缺陷。基于图的聚类基于图的聚类l最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法l基于SNN密度的聚类ChameleonlChameleon是一种凝聚聚类技术，它处理前两段提到的问题。它将数据的初始划分与一种新颖的层次聚类方案相结合。l这种层次聚类运用接近性和互连性概念以及簇的部分建模。关键思想是：仅当合并后的结果簇类似于原来的两个簇时，这两个簇才该当合并。确定合并哪些簇确定合并哪些簇l相对接近度relative closeness，RC：是被簇的内部接近度规范化的两个簇的绝对接近度。两个簇合并，仅当结果簇中的点之间的接近程度几乎与原来的每个簇一样。lmi和mj分别是簇ci和cj的大小。SECci，cj是衔接簇ci和cj的边的平均值；SECci是二分簇ci的边的平均权值。)()(),(),(jECjiiiECjiijiECjiCSmmmCSmmmCCSCCRCl相对互连度relative interconnectivity,RI：是被簇的内部互连度规范化的两个簇的绝对互连度。假设结果簇中的点之间的衔接几乎与原来的每个簇一样强，两个簇合并。l其中，ECCi，Cj是衔接簇Ci和Cj的边之和；EC(Ci)是二分簇Ci的割边的最小和；EC(Cj)是二分簇Cj的割边的最小和。lRI和RC可以用多种不同的方法组合，产生自类似性的总量。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 合并关于相对互连性和相对接近性而言，最好 l 地坚持簇的自类似性的簇lUntil 不再有可以合并的簇例子例子优点与局限性优点与局限性lChameleon可以有效地聚类空间数据，即使存在噪声和离群点，并且簇具有不同的外形、大小和密度。lChameleon假定由稀疏化和图划分过程产生的对象组群是子簇，即一个划分中的大部分点属于同一个真正的簇。假设不是，那么凝聚层次聚类将混合这些错误，由于它绝对不能够再将曾经错误地放到一同的对象分开。这样，当划分过程未产生子簇时，chameleon就有问题，对于高维数据，经常出现这种情况。共享最近邻类似性共享最近邻类似性lSNNshared nearest neighbor类似度计算：l1.找出一切点的k-近邻l2.If 两个点x和y不是相互在对方的k-最近邻中 thenl3.similarity(x,y)0l4.Elsel5.similarity(x,y)共享的近邻个数l6.End iflSNN类似度由于经过运用共享最近邻的个数思索了对象的环境，SNN类似度可以处置一个对象碰巧与另一对象相对接近，但属于不同的类。在这种情况下，对象普通不共享许多近邻，并且它们的SNN类似度低。lSSN类似度也能处置变密度簇的问题。在低密度区域，对象比高密度区域的对象分开得更远。然而，一对点之间的SNN类似度只依赖于两个对象共享的最近邻的个数，而不是这些近邻之间的相距多远。SNN关于点的密度进展自动缩放。基于图的聚类基于图的聚类l最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法l基于SNN密度的聚类Jarvis-PatrickJP聚类算法聚类算法l计算SNN类似度图l运用类似度阈值，稀疏化SNN类似度图l找出稀疏化的SNN类似度图的连通分支优点与局限性优点与局限性l由于JP聚类基于SNN类似度概念，它擅长于处置噪声和离群点，并且可以处置不同大小、外形和密度的簇。l该算法对高维数据效果良好，尤其擅长发现强相关对象的严密簇。lJP聚类把簇定义为SNN类似度图的连通分支。这样，一个对象集是分裂成两个簇还是作为一个簇留下，能够依赖于一条链。基于基于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 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 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密度的运用大大添加了该方法的才干和灵敏性。可伸缩：普通问题和方法可伸缩：普通问题和方法lBIRCHlCUREl假设运转时间长得不可接受，或者需求的存储量太大，即使最好的聚类算法也没有多大价值。l许多聚类算法所需求的存储量都是非线性的。例如：运用层次聚类，存储需求普通是O(m2)。类似地，有些聚类算法所需求的计算量也是非线性的。l可伸缩性可以经过如下技术实现：多维或空间存取方法、临近度约束、抽样、划分数据对象、汇总、并行与分布计算。CURElCUREClustering Using REpresentative是一种聚类算法，它运用各种不同的技术创建一种可以处置大型数据、离群点、具有非球形和非均匀大小的簇的数据的方法。lCURE运用簇中的多个代表点来表示一个簇。实际上，这些点捕获了簇的几何外形。l详细来说，第一个代表点选择离簇中心最远的点，而其他的点选择离一切曾经选取的点最远的点。这样，代表点相对分别。l选取的点的个数是一个参数，但是普通取10效果较好。l一旦选定代表点，它们就以因子a向簇中心收缩。这有助于减轻离群点的影响。l例如，一个到中心的间隔为10个单位的代表点将挪动3个单位对于a=0.7，而到中心间隔为1个单位的代表点仅挪动0.3个单位。lCURE运用一种凝聚层次聚类方案进展实践的聚类。两个簇之间的间隔是恣意两个代表点在它们向它们代表点的中心收缩之后之间的最短间隔。l假设a=0，它等价于基于质心的层次聚类；a=1时，它与单链层次聚类大致一样。l留意，虽然运用层次聚类方案，但是CURE的目的是发现用户指定个数的簇。lCURE在聚类过程的两个不同阶段删除离群点。首先，假设一个簇增长缓慢，那么这意味它主要由离群点组成，由于根据定义，离群点远离其他点，并且不会经常与其他点合并。l在CURE中，离群点删除的第一个阶段普通出如今簇的个数是原来点数的1/3时。第二个离群点删除阶段出如今簇的个数到达K的量级时。此时，小簇又被删除。lCURE在最坏情况下复杂度为O(m2logm)，它不能直接用于大型数据集。因此，CURE运用了两种技术来加快聚类过程。l第一种技术是取随机样本，并在抽样的数据点上进展层次聚类。随后是最终扫描，将数据集中剩余的点指派到簇中。l在某些情况下，聚类所需求的样本依然太大，需求第二种技术处理。在这种情况下，CURE划分样本数据，然后聚类每个划分中的点。这种预聚类步后通常紧随中间簇的聚类，以及将数据集中的每个点指派到一个簇的最终扫描。CURE算法算法l由数据集抽取一个随机样本集。l将样本集划分成p个大小一样的划分。l运用CURE的层次聚类算法，将每个划分中的点聚类成m/pq个簇，得到总共m/q个簇。l运用CURE的层次聚类算法对上一步发现的m/q个簇进展聚类，直到只剩下k个簇。l删除离群点。l将一切剩余的数据点指派到最近的簇，得到完全聚类。lK是期望的簇个数，m是点的个数，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=100000，这样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使得同一根本簇的对象最终在一个簇中。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异常检测