工具类服务
编辑部专用服务
作者专用服务
基于 MapReduce的并行聚类算法设计与实现
针对目前聚类算法对大数据处理效率较低的问题，研究云平台上高效并行化的聚类算法十分必要。在HDFS分布式文件系统基础上，设计一种并行聚类算法P-ISODATA，利用MapReduce编程框架的执行机制将传统ISODATA聚类算法并行化，并在Map阶段之后加入Combine阶段以减少网络传输开销，进一步提高执行效率。实验从著名UCI机器学习库上选取若干数据集作为测试数据，分析了新并行算法P-ISODATA性能，结果表明基于P-ISODATA算法具有优良的加速比、数据伸缩率和扩展率，可以有效地应用于大规模数据的处理。
Abstract：
In light of the problem that current clustering algorithms are inefficient in efficiency when processing big data, it is necessary to study efficient parallel clustering algorithms on cloud platform.We design a new parallel clustering algorithm P-ISODATA based on HDFS ( Hadoop distributed file system) , it parallelises traditional ISODATA clustering algorithm by utilising the execution mechanism of MapReduce programming framework, and introduces Combine phase following behind the Map phase to reduce network transmission overhead and to further improve the execution efficiency.In experiments we select different datasets from famous UCI machine learning repository as the testing data, and analyse the performance of P-ISODATA algorithm.Results show that P-ISODATA-based algorithm has good speed-up ratio, data scale-up rate and size-up ratio, therefore it can be effectively applied to large-scale data processing.
Liu Xiangdong
Hu Feixiang
Wang Cuirong
作者单位：
东北大学秦皇岛分校计算机与通信工程学院 河北 秦皇岛 066004
东北大学信息工程学院 辽宁 沈阳110000
年，卷(期)：
Keywords：
机标分类号：
在线出版日期：
基金项目：
国家自然科学基金项目(071028)。
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社数据挖掘（7）
一、聚类综述
& & 聚类分析提供由个别数据对象到数据对象所指派到簇的抽象。此外，一些聚类技术使用簇原型（即代表簇中其他对象的数据对象）来刻画簇的特征。聚类分析是研究发现最具有代表性的簇原型的技术。回归和PCA的时间复杂度都是O(m2)。注意：簇的定义是不精确的，而最好的定义依赖于数据的特征和期望的结果。聚类分析与其他将数据对象分组的技术有关。监督学习（也叫监督分类或分类）：使用一个由类标号已知的对象开发的模型，对新的、无标记的对象赋予一个类标号。非监督学习（也叫非监督分类或聚类）。在数据挖掘中，不附加任何条件使用术语分类时，通常是指监督分类。尽管术语分割和划分有时也作聚类的同义词，但是这些术语通常用来表示传统的聚类分析之外的方法。
1&聚类类型
& & 不同的聚类类型：层次的（嵌套的）与划分的（非嵌套的），互斥的，重叠的与模糊的，完全的与部分的。
& & 划分聚类：简单地将数据对象划分成不重叠的子集（簇），使得每个数据对象恰在一个子集中。
& & 层次聚类：允许簇具有子簇，层次聚类是嵌套簇的集簇，组织成一棵树。层次聚类可以看作划分聚类的序列，划分聚类可以通过取序列的任意成员得到，即通过在一个特定层剪断层次树得到。
& & 互斥聚类：每个对象都指派到单个簇。重叠的或非互斥的聚类用来反映一个对象同时属于多个组（类）这一事实。
& & 模糊聚类：每个对象以一个0（绝对不属于）和1（绝对属于）之间的隶属权值属于每个簇。
& & 完全聚类：将每一个（全部的对象）指派到一个簇，而部分聚类是有些对象没有被聚类。
& & 不同的簇类型：
& & 明显分离的：不同组中的任意两点之间的距离都大于组内任意两点之间的距离。明显分离的簇不必是球形的，可以具有任意形状。
& & 基于原型的：簇是对象的集合，其中每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近（或更加相似）。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。这种簇倾向于呈球状。基于原型的聚类技术创建数据对象的单层划分。
& & 基于图的：如果数据用图表示，其中节点是对象，而边代表对象之间的联系，则簇可以定义为连通分支，即互相连通但不与组外对象连通的对象组。当簇不规则或缠绕时，簇的这种定义是有用的。但是，当数据具有噪声时就可能出现问题。也存在其他类型的基于图的簇。一种方法是定义簇为团，即图中相互之间完全连接的节点的集合。
& & 基于密度的：簇是对象的稠密区域，被低密度的区域环绕。当簇不规则或互相盘绕，并且有噪声和离群点时，常常使用基于密度的簇定义。
& & 共同性质的（概念簇）：把簇定义为有某种共同性质的对象的集合。发现这样的簇的过程称作概念聚类。
二、聚类算法详述
1 K均值
& & K均值是基于原型的、划分的聚类技术。它试图发现用户指定个数（K）的簇（由质心代表）。
& & K均值聚类用于n维连续空间中的对象。K中心点使用中心点定义原型，其中中心点是一组点中最有代表性的点。K中心点聚类可以用于广泛的数据，因为它只需要对象之间的邻近性度量。尽管质心几乎从来不对应实际的数据点，但是根据定义，中心点必须是一个实际的数据点。
& & K均值的算法步骤：首先选择K个初始质心，其中K是用户指定的参数，即所期望的簇的个数。每个点指派到最近的质心，而指派到一个质心的点集为一个簇。然后，根据指派到簇的点，更新每个簇的质心。重复指派和更新步骤，直到簇不发生变化，或等价的，直到质心不发生变化。
& & 算法流程如下：
& & 为了将点指派到最近的质心，我们需要邻近性度量来量化所考虑的数据的“最近”概念，通常，对欧式空间中的点使用欧几里得距离，对文档用余弦相似性。第四步“重新计算每个簇的质心”，因为质心可能随数据邻近性度量和聚类目标不同而改变。聚类的目标通常用一个目标函数表示，该函数依赖于点之间，或点到簇的质心的邻近性；如：最小化每个点到最近质心的距离的平方。然而，关键点是：一旦我们选定了邻近性度量和目标函数，则应当选择的质心可以从数学上确定。考虑邻近性度量为欧几里得距离的数据。我们使用误差的平方和（SSE也称散布）作为度量聚类质量的目标函数。换言之，我们计算每个数据点的误差，即它到最近质心的欧几里得距离，然后计算误差的平方和。给定由两次运行K均值产生的两个不同的簇集，我们更喜欢误差平方和最小的那个，因为这意味聚类的原型（质心）是簇中点的更好代表。假设数据是文档数据，相似度用余弦来度量。我们的目标是最大化簇中文档与簇的质心的相似性；该度量称作凝聚度。对于该目标，可以证明，与欧几里得数据一样，簇的质心是均值。曼哈顿距离的质心是中位数。Bregman散度也是一种邻近性度量，该散度函数的重要性为质心的K均值类型的聚类算法的基础。用该散度作为邻近性度函数，则聚类算法的收敛性、局部最小等性质与通常的K均值相同。
& & 当质心随机初始化，K均值的不同运行将产生不同的总SSE。选择适当的初始质心是基本K 均值过程的关键步骤。一种常见的方法是随机地选取初始质心，但是簇的质量常常会很差的。处理选取初始质心问题的一种常见技术是：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE的簇集。该策略虽然简单，但是效果可能不好，这依赖于数据集合寻找的簇的个数。另外还有的技术包括：取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取K个簇，并用这些簇的质心作为初始质心。该方法只在下列条件下有效（1）样本相对较小（层次聚类开销较大）；（2）K相对于样本大小较小。还有一种选择初始质心的方法：随机地选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心较远的点。通常该方法用于点样本。由于离群点很少，他们多半不会在随机样本中出现。
& & 前面介绍的基本K均值存在一个问题：如果所有的点在指派步骤都未分配到某个簇，就会得到空簇。如果这种情况发生，则需要某种策略来选择一个替补质心，否则的话，平方误差将会偏大。一种方法是选择一个距离当前任何质心最远的点。另一种方法是从具有最大SSE的簇中选择一个替补质心。我们还可能删除那些很小的簇，因为它们常常代表离群点的组。一种降低SSE的明显方法是找出更多簇，即使用很大的K。然而，在许多情况下，我们希望降低ＳＳＥ，但并不想增加簇的个数。因为Ｋ均值常常收敛于局部最小。一种常用的方法是交替地使用簇分裂和簇合并。
& & 增量的更新质心：可以在点到簇的每次指派之后，增量地更新质心，而不是在所有的点都指派到簇中之后才更新簇的质心，每次需要零次或两次质心更新。使用增量更新策略确保不会产生空簇。因为所有的簇都从单个点开始；并且一个簇只有单个点，则该点总是被指派到相同的簇。增量更新还有两个优点：（１）可以调整点的相对权值。（２）使用不同于“最小化ＳＳＥ”的目标。缺点：增量的更新质心可能导致次序的依赖性，即：所产生的簇可能依赖于点的处理次序。Ｋ均值收敛相当快。
& & 二分Ｋ均值：为了得到Ｋ个簇，将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生Ｋ个簇。待分裂的簇有许多不同的选择方法。可以选择最大的簇，选择具有最大SSE的簇，或者使用一个基于大小和SSE的标准进行选择。二分K均值算法最终的簇集并不代表使SSE局部最小的聚类。二分K均值不太受初始化的困扰，因为它执行了多次二分试验并选取具有最小SSE的试验结果，还因为每步只有两个质心。通过记录K均值二分簇所产生的聚类序列，我们还可以使用二分K均值产生层次聚类。当簇具有非球形形状或具有不同尺寸或密度时，K均值很难检测到“自然的”簇。K均值的目标函数是最优化等尺寸和等密度的球形簇，或者明显分离的簇。所以K均值只适合与上面的三种情况的聚类。
& & 优缺点：K均值简单并且可以用于各种数据类型。它也相当有效，尽管常常多次运行。然而，K均值并不适合所有的数据类型。它不能处理非球形簇、不同尺寸和不同密度的簇，尽管指定足够大的簇个数时它通常可以发现纯子簇。对包含离群点的数据进行聚类时，K均值也有问题。K均值仅限于具有中心（质心）概念的数据。K中心点没有这种限制，但是开销更大。
& & 最后，给定一个诸如“最小化SSE”这样的目标函数，可以把聚类视为优化问题。
2 凝聚的层次聚类
& & 它通过如下的步骤产生层次聚类：开始，每个点作为一个单元簇，然后，重复地合并两个最靠近的簇，直到产生单个的、包含所有点的簇。有两种产生层次聚类的基本方法：
（1）凝聚的：从点作为个体簇开始，每一合并两个最接近的簇。这需要定义簇的邻接性的概念。
（2）分裂的：从包含所有点的一个簇开始，每一步分裂一个簇，直到仅剩下单点簇。这种情况下，我们需要确定每一步分裂哪个簇，以及如何分裂。
& & 其中凝聚层次聚类技术是常见的。层次聚类常常使用一种称作树状图的类似于树的图显示。对于二维点的集合，层次聚类也可以使用嵌套图表示。层次聚类的关键操作是计算两个簇之间的邻近度，并且正是簇的邻近性定义区分了我们将讨论的各种凝聚层次技术。簇的邻近性通常用特定的簇类型定义。通常的方法有MIN、MAX和组平均，都源于簇的基于图的观点。MIN（也叫做单链）定义簇的邻近度为不同簇的两个最近的点之间的邻近度，使用图的术语即：不同结点子集中两个结点之间的最短边。单链技术擅长于处理非椭圆形状的簇，但对噪声和离群点很敏感。MAX（也叫全链）取不同簇中两个最远的点之间的邻近度作为簇的邻近度，使用图的术语即：不同结点子集中两个结点之间的最长边。完全连接对噪声和离群点不太敏感，但是它可能使大的簇破裂，并且偏好于球形。组平均：定义簇邻近度为取自不同簇的所有点的平均逐对邻近度。如果我们取基于原型的观点，簇用质心代表，则不同的簇邻近度定义就更加自然。使用质心时，簇的邻近度一般定义为簇质心之间的邻近度，另一种技术，Ward方法，也假定簇用其质心代表，但它使用合并两个簇导致的SSE增加来度量两个簇之间的邻近性，像K均值一样，Ward方法也试图最小化点到其簇质心的距离的平方和。当两个点之间的邻近度取它们之间距离的平方时，Ward方法与组平均非常相似。
& & 质心方法：通过计算簇质心之间的距离来计算两个簇之间的邻近度。质心方法具有一种其他层次聚类不具备的特性（常被认为是坏的）：倒置的可能性。即合并的两个簇可能比前一步合并的蔟对更相似。对于其他方法，被合并的簇之间的距离随层次聚类进展单调地增加。
上面的所有方法都可以合并到一个叫Lance-Williams公式中去。任何使用该公式表示的层次聚类技术都不需要保留原来的数据点。替换地，邻近度矩阵随聚类而更新。
层次聚类的主要问题：
（1）缺乏全局目标函数。凝聚层次聚类不能视为全局优化一个目标函数。这样的方法没有局部最小问题或很难选择初始点的问题。
（2）处理不同大小的聚类能力。即如何处理待合并的蔟对的相对大小。有两种方法：加权，平等的对待所有簇，非加权，考虑每个簇的点数。注意：术语加权和非加权是对数据而言，而不是对簇。即，平等的对待不同大小的簇意味着赋予不同簇中的点不同的权值，而考虑簇的大小则赋予不同簇中的点相同的权值。一般地，非加权的方法更可取，除非有理由相信个体点具有不同的权值：例如，或许对象类非均匀地抽样。
（3）合并决策是最终的。对于合并两个簇，凝聚层次算法倾向于作出好的局部决策，因为它们可以使用所有点的逐对相似度信息。然而，一旦作出合并两个簇的决策，以后就不能撤销。有一些技术试图克服“合并是最终的”这一限制。一种方法试图通过如下方法来修补层次聚类，移动树的分支以改善全局目标函数。另一种方法使用划分聚类技术（如K均值）来创建许多小簇，然后从这些小簇出发进行层次聚类。
& & 优点和缺点：使用这类聚类算法是因为基本应用（如创建一种分类法）需要层次结构。凝聚层次聚类算法是昂贵的，所有合并是最终的，对于噪声、高维数据（如文档数据），这也可能造成问题。先使用其他技术（如K均值）进行部分聚类，这两个问题都可以在某种程度上加以解决。
层次聚类的空间复杂度O(m2)。总时间复杂度O(m2logm)。
& & 这是一种产生划分聚类的基于密度的聚类算法，簇的个数由算法自动的确定。低密度区域中的点被视为噪声而忽略，因而DBSCAN不产生完全聚类。
& & 基于密度的聚类寻找被低密度区域分离的高密度区域。定义密度的方法有很多，在DBSCAN中使用的是基于中心的方法，在该方法中，数据集中特定点的密度通过对该点的\Eps半径之内的点计数（包括点本身）来估计。核心点：这些点在基于密度的簇内部。一个点是核心点，如果该点的给定邻域内的点的个数超过给定的阈值MinPts，其中MinPts也是一个用户指定的参数。边界点：边界点不是核心点，但他落在某个核心点的邻域内。噪声点：噪声点是既非核心点也非边界点的任何点。DBSCAN算法可以非形式化的描述如下：任何两个足够靠近（相互之间的距离在Eps之内）的核心点将放在同一簇中。类似的，任何与核心点足够靠近的边界点也放到核心点相同的簇中。（如果一个边界点靠近不同簇的核心点，则可能需要解决平局问题）。噪声点被丢弃。
（1）该算法的时间复杂度是O(m2)，然而，在低维空间，有一些数据结构，如kd树，使得可以有效的检索特定点给定距离内的所有点，时间复杂度可以降低到O(mlogm)。
（2）选择DBSCAN的参数（Eps和MinPts）。基本方法是观察点到它的k个最近邻的距离（称为k-距离）的特性。对于属于某个簇的点，如果k不大于簇的大小的话，则k-距离将很小。然而，对于不在簇中的点（如噪声点），k-距离将相对较大。因此，如果我们对某个k，计算所有点的k-距离，以递增的次序将他们排序，然后绘制排序后的值，则我们预期会看到k-距离的急剧变化，对应于合适的Eps值。
（3）变密度的簇：如果簇的密度变化很大，DBSCAN可能会有问题。
（4）DBSCAN优缺点。因为该方法使用簇的基于密度的定义，因此它是相对抗噪声的，并且能够处理任意形状和大小的簇。它可以发现使用K均值不能发现的许多簇。缺点：不适合密度变化太大。对于高维数据，该方法也有问题，因为密度定义困难。最后，当邻近计算需要计算所有的点对邻近度时（对于高维数据，常常如此），DBSCAN可能是开销很大的。
& & 由于簇的特性，簇评估技术未能很好开发，或者说不是聚类分析普遍使用的。尽管如此，簇评估，或者簇确认是重要的。由于存在大量不同的簇类型（在某种意义下，每种聚类算法都定义了子集的簇类型），似乎每种情况都可能需要一种不同的评估度量。例如，K均值簇可能需要用SSE来评估，但是基于密度的簇不必是球形的，SSE全然不起作用。尽管如此，簇评估应该是聚类分析中的一部分。一个主要动机是，几乎每种聚类算法都会在数据集中发现簇，即便该数据集根本没有自然的簇结构。
& & 簇确认的一些任务：
（1）确定数据集的聚类趋势，即识别数据中是否实际存在非随机结构。
（2）确定正确的簇个数；
（3）不引用附加的信息，评估聚类分析结果对数据拟合情况；
（4）将聚类分析结果与已知的客观结果（如，外部提供的类标号）比较；
（5）比较两个簇集，确定哪个更好。
& & 注意：第1、2、3项不适用任何外部信息（他们是非监督技术），而第4项使用外部信息。第5项可以用监督或非监督的方式执行。
& & 评估的挑战：
（1）簇的有效性度量可能受限于它的可用范围;例如：聚类趋势度量方面的大部分工作都是针对二、三维空间数据
（2）我们需要一个框架来解释任意度量。匹配的优良度可以通过考察该值的统计分布来度量，即这样的值偶然出现的几率多大。
（3）如果度量太复杂，难以使用或难以理解，则很少有人愿意使用它。
& & 传统的，用于评估簇的各方面的评估度量或指标分成如下三类：
（1）非监督的：聚类结构的优良性度量，不考虑外部信息。如SSE。簇的有效性的非监督度量常常可以进一步分为两类：（A）簇的凝聚性（紧凑性、紧致性）度量确定簇中对象如果密切相关。（B）簇的分离性（孤立性）：度量确定一个簇如何不同于其他簇。非监督度量通常称为内部指标，因为它们仅使用出现在数据集中的信息。
（2）监督的：度量聚类算法发现的聚类结构与某种外部结构的匹配程度。如熵，它度量簇标号与外部提供的标号的匹配程度。监督度量通常称为外部指标，因为他们使用了不在数据集中出现的信息。
（3）相对的：比较不同的聚类和簇。
4.1&非监督簇评估：使用凝聚度和分离度
& & 如果有效性函数是凝聚度，则值越高越好。如果是分离度，则越低越好。对于基于图的簇，簇的凝聚度可以定义为连接簇内点的邻近度图中边的加权和；两个簇之间的分离度可以用从一个簇的点到另一个簇的点的边的加权和来度量。对于基于原型的簇，簇的凝聚度可以定义为关于簇原型（质心或中心点）的邻近度的和；两个簇之间的分离度可以用两个簇原型的邻近度度量。簇原型与总原型的分离度有时与簇原型之间的分离度直接相关。对于簇的凝聚度和分离度，通过使用加权和可以将它们组合成簇的有效性的总度量。尽管度量簇的凝聚性和分离性的基于图的方法与基于原型的方法看上去截然不同，但是对于某些邻近性度量它们是等价的。当邻近度用欧几里得距离度量时，簇之间分离性的传统度量是组平方和（SSB），总SSB越高，簇之间的分离性越好。我们也可以使用对象对簇的总凝聚度或分离度的贡献，来评估簇中的对象。对凝聚度和分离度贡献越大的对象就越靠近簇的“内部”，反之，对象可能离簇的“边缘”很近。
& & 轮廓系数：结合了凝聚度和分离度。下面是如何计算个体点的轮廓系数（我们使用距离，但是类似的方法可以使用相似度）：
（1）对于第i个对象，计算它到簇中所有其他对象的平均距离。该值记为。
（2）对于第i个对象和不包含该对象的任意簇，计算该对象到给定簇中所有对象的平均距离，关于所有的簇，找出最小值；该值记为bi。
（3）对于第i个对象，
& & 因为负值表示点到簇内点的平均距离 大于点到其他簇的最小平均距离bi。我们希望轮廓系数是正的（ &bi），并且 越靠近0越好，因为当 =0时轮廓系数取其最大值1.我们可以简单地取簇中点的轮廓系数的平均值，计算簇的平均轮廓系数。通过计算所有点的平均轮廓系数，可以得到聚类优良性的总度量。
4.2&非监督簇评估：使用邻近度矩阵
有两种：（1）比较实际的邻近度矩阵和理想的邻近度矩阵；
& & & & （2）使用可视化技术。理想的簇是这样的簇，它的点与簇内所有点的相似度为1，而与其他簇的所有点的相似度为0。这样，如果将相似度矩阵的行和列排序，使得属于相同的簇的对象在一起，则理想的相似度矩阵具有块对角结构。邻近度矩阵对于许多基于密度和基于近邻的簇，这不是好的度量，因为它们不是球形的，并且常常与其他簇紧密地盘绕在一起。从理论上讲，如果有明显分离的簇，则相似度矩阵粗略地是块对角的。如果不是，则邻近度矩阵所显示的模式可能揭示簇之间的联系。所有这些也可以用于相异度矩阵。
4.3&层次聚类的非监督簇评估
& & 基于层次聚类的流行的评估度量——共性分类相关。两个对象之间的共性分类距离是凝聚层次聚类技术首次将对象放在同一簇时的邻近度。例如：如果两个合并簇之间的最小距离是0.1，则一个簇中的所有点关于另一个簇中的各点的共性分类距离都是0.1。在共性分类距离矩阵中，项是每对对象之间的共性分类距离。点集的每个层次聚类的共性分类距离不同。共性相关系数是该矩阵与原来的相异度矩阵的项之间的相关度，是（特定类型的）层次聚类对数据拟合程度的标准度量。该度量的最常见应用时评估对于特定的数据类型，哪种类型的层次聚类最好。
& & 确定正确的簇个数:多种非监督评估度量都可以用来近似地确定正确的或自然的簇个数。我们可以通过寻找簇个数的评估度量曲线图中的拐点、尖峰或下降点，试图发现簇的自然个数。
& & 聚类趋势。确定数据集中是否包含簇的一种明显的方法是试着对他聚类。我们可以评估结果簇，至少有些簇具有好的质量，才能说数据集中包含簇。然而，事实是数据集中可能存在不同于我们的聚类算法所能发现的簇类型。聚类趋势度量：试图估计数据集中是否包含簇，而不进行聚类。最常用的方法（特别对于欧几里得空间数据）是使用统计检验来检验空间的随机性。如Hopkins（霍普金斯）统计量。
4.4&簇有效性的监督度量
& & 考虑划分聚类的两类不同的方法：
（1）使用分类的度量，如熵、纯度、精度、召回率和F度量。这些度量评估簇包含单个类的对象的程度。
（2）涉及二元数据的相似性度量。如：Jaccard系数。这些方法度量在多大程度上，同一类的两个对象在同一个簇中，或相反。
& & 层次聚类的监督评估更加困难，这里，我们给出一个根据类标号集评估层次聚类方法的例子。类标号集可能比先前存在的簇结构更容易得到。该方法的关键思想是：评估层次聚类是否对于每个类，至少有一个簇相对较纯，并且包含了该类的大部分对象。为了根据此目标评估层次聚类，我们对每个类，计算簇层次结构中每个簇的F度量，对于每个类，取最大的F度量。最后，通过计算每类的F度量的加权平均，计算层析聚类的总F度量，其中，权值基于类的大小。
4.5&评估簇有效性度量的显著性
& & 一种常用的方法是同统计学术语解释有效性度量值。具体的说，我们试图确定观测值随机得到的可能性有多大。值是好的，如果它是不寻常的。即它不像是随机结果。这种显著性有两个方面：差别是否是统计显著的（可重复的），差别的量级对于应用是否具有意义。
5 聚类分析：附加的问题和算法
& & 没有一种算法能够适应所有的数据类型、簇和应用。在许多情况下，对于什么是一个好的簇集，仍然凭主观解释。
& & K均值聚类可以看作一种统计聚类（混合模型）的特例，所以它假定所有的数据都来自球形高斯分布，具有不同的均值，但是具有相同的协方差矩阵。DBSCAN不基于任何形式化模型，所以它不对数据的分布做任何假定。K均值和DBSCAN，当簇具有很不相同的密度时，两种算法的性能都很差。K均值可以用于稀疏的高维数据，如文档数据。DBSCAN通常在这类数据上性能很差，因为多域高维数据，传统的欧几里得密度定义不能很好的处理。K均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN会合并有重叠的簇。K均值算法的时间复杂度是O（m）而DBSCAN是O(m2)，除非用于诸如低维欧几里得数据这样的特殊情况。DBSCAN多次运行产生相同的结果，而K均值通常使用随机初始化质心。不会产生相同的结果。注意：噪声可能导致单链等技术合并两个不应当合并的簇。Chameleon、基于SNN密度的聚类和CURE在聚类的过程中显式的处理噪声和离群点。
& & 簇特性：
（1）某些聚类算法假定数据具有特定的分布。更具体的说，他们常常假定可以用混合分布对数据建模，其中每个簇对应于一个分布。
（2）形状：DBSCAN和单链技术可以处理任意形状的簇，但是基于原型的方法和诸如全链和组平均这样的层次聚类技术不能进行这样的处理。Chameleon和CURE是专门用来处理这一问题的技术的例子。
（3）不同的密度：具有很不相同的密度的簇可能对DBSCAN和K均值算法造成问题，SNN密度聚类技术就是处理这一问题的。（4）无明显分离的簇。模糊聚类是一种旨在处理未形成明显分离的簇的数据的技术。
（4）簇之间的联系。在大部分聚类技术中，都不明显地考虑簇之间的联系，如簇的相对位置。自组织映射（SOM）是一种在聚类期间直接考虑簇之间联系的聚类技术。具体的，点到簇的指派影响邻近簇的定义。
（5）子空间簇。簇可能只在维（属性）的一个子集中存在，并且使用一个维集合确定的簇可能与使用另一个维集合确定的簇很不相同。简单地在所有可能的维子集中寻找簇是不可行的。
& & 聚类算法的一般特性：
（1）次序依赖性。对于某些算法，所产生的簇的质量和个数可能因数据处理的次序不同而显著地变化。SOM是次序依赖算法的一个例子。
（2）非确定性。每次运行都产生不同的结果，因为它们依赖于需要随机选择的初始化步骤。
（3）可伸缩性。包含数以百万计对象的数据集并不罕见，而用于这种数据集的聚类算法应当具有线性或接近线性的时间和空间复杂度。
（4）参数选择。通常的态度是参数越少越好。
5.1&基于原型的聚类
& & 本节讨论的聚类方法以一种或多种方式扩展基于原型的概念，如下所述：
（1）允许对象属于多个簇，更具体的说，对象以某个权值属于每一个簇，这样的方法针对这样的事实，某些对象与多个簇原型一样近。（有模糊聚类）
（2）用统计分布对簇进行建模，即对象通过一个随机过程，有一个被若干统计参数（如均值和方差）刻画的统计分布产生。（有混合模型聚类）
（3）簇被约束为具有固定的联系。就常见地，这些联系是指定近邻关系的约束，即两个簇互为邻居的程度。约束簇之间的联系可以简化对数据的解释和可视化。
& & 模糊c均值(也叫FCM)使用模糊逻辑和模糊集合论的概念，提出一种聚类方案，它很像K均值，但是不需要硬性的将某个对象只指派到一个簇中。混合模型聚类采用这样的聚类方法，簇集合可以使用一个混合分布建模，每一个分布对应一个簇。基于自组织映射（SOM）的聚类方法在一个框架（例如二维网格结构）内进行聚类，该框架要求簇具有预先指定的相互联系。
5.1.1 模糊c均值
& & 模糊集合论和模糊逻辑作为一种处理不精确和不确定的方法。简要的说，模糊集合论允许对象以0和1之间的某个录属度属于一个集合，而模糊逻辑允许一个陈述以0和1之间的确定度为真。存在多种模糊聚类（事实上，许多数据分析算法都可以“模糊化”），我们只考虑K均值的模糊版本，称作模糊c均值（FCM）。前提：对每个对象和每个簇赋予一个权值，指明该对象属于该簇的程度。从数学上讲，wij是对象Xi属于簇Cj的权值。
算法步骤：
（1）选择一个初始模糊伪划分，即对所有的wij赋值；
（2）使用模糊伪划分，计算每个簇的质心（即依据质心（保证了变化性）更新模糊伪划分）；
（3）重新计算模糊伪划分，即wij；
（4）重复（2）（3），直到质心不发生变化（替换的终止条件是“如果误差的变化低于指定的阈值”或“如果所有wij的变化的绝对值都低于指定的阈值”）。
算法中，重新计算模糊伪划分等价于指派步骤。
将以下合理的条件施加在簇上，以确保簇形成模糊伪划分：
& & 与K均值一样，FCM可以解释为试图最小化误差的平方和，尽管FCM基于SSE的模糊版本，事实上，K均值可以看作FCM的特例。
& & 初始化：通常使用随机初始化。特殊地，权值随机地选取，同时限定与任何对象相关联的权值之和必须等于1（但是，随机选取也和K均值一样，有他的有点和缺点）。
& & 优缺点：优点：它产生指示任意点属于任意簇的程度的聚类。除此之外，它具有与K均值相同的优缺点，尽管它的计算密集程度更高一些。
5.1.2 使用混合模型的聚类
& & 假定数据是由一个统计过程产生的，并且通过找出最佳拟合数据的统计模型来描述数据，其中统计模型中用分布和该分布的一组参数描述。在高层，该过程涉及确定数据的统计模型，并由数据估计该模型的参数。混合模型，它使用若干统计分布对数据建模，每一个分布对应于一个簇，而每个分布的参数提供对应簇的描述，通常用中心和发散描述。
& & 混合模型将数据看作从不同的概率分布得到的观测值的集合，概念上讲，混合模型对应于如下数据产生过程，给定几个分布（通常类型相同但参数不同），随机地选取一个分布并由产生一个对象。重复过程m次，其中m是对象的个数。对于混合模型，每个分布描述一个不同的组，即一个不同的簇。通过使用统计方法，我们可以由数据估计这些分布的参数，从而描述这些分布（簇）。我们也可以识别哪个对象属于哪个簇。然而，混合模型并不产生对象的明确指派，而是给出具体对象属于特定簇的概率。
& & EM算法的聚类：假设我们已经知道整体数据集是由几个相同类型的分布（只是参数不同）（每个分布对应一个簇）组成的，我们将每个分布组合起来成一个混合的模型（比如简单的，将每个分布（假设是高斯分布）的分布概率函数相加）。为了将数据分类就需要估计混合模型中的参数找到参数后可以知道每个分布，每一分布对应一个簇，聚类就完成。而估计参数的方法流行的有两种：（1）最大似然估（MLE）计：这个主要用在（A）整体数据集只有一个分布；（2）当用最大似然估计来估计混合模型的参数时，我们知道哪个数据对象来自哪个分布，于是问题又归结为给定符合某分部的数据，估计单个分布的参数。
& & 然而实际情况是我们不知道哪个点由哪个分布产生。这样我们就不能直接计算每一个点的概率，因此我们不能使用最大似然原理来估计参数。解决这个问题的方案是使用EM算法（期望最大化）。算法思想：先给定参数值的一个猜测，EM算法计算每个点属于每个分布的概率，然后使用这些概率，计算参数的新的估计（这些参数是最大化该似然估计的参数）。该迭代继续下去，直到参数的估计不再改变或改变很小。这样，我们通过一个迭代搜索，仍然使用了最大似然估计。
& & EM算法步骤：
（1）选择模型参数的初始集（与K均值一样，可以随机地做，也可以用各种方法。
（2）期望步&&对于每个对象，计算每个对象属于每个分布的概率。
（3）最大化步&&&给定期望步得到的概率（保证了动态性），找出最大化该期望的新的参数估计。
（4）重复（2）（3）步，直到参数不再改变（替换地，如果参数的改变低于预先指定的阈值则停止）。
& & 事实上，欧几里得数据的K均值算法是具有相同协方差矩阵，但具有不同均值的球形高斯分布的EM算法的特殊情况。期望步对应于K均值将每个对象指派到一个簇的步骤，但将每个对象以某一概率指派到每个簇（分布）。最大化步对应于计算簇的质心，但是选取分布的所有参数以及权值参数来最大化似然。这一过程常常是直截了当的，因为参数一般使用由最大似然估计推导出来的公式进行计算。每个点最后指派到它具有最大录属权值的簇中。
（1）EM算法可能很慢，对于具有大量分量的模型可能不切实际；当簇只包含少量数据点，或者数据点近似线性时，他也不能很好处理。
（2）在估计簇的个数，或更一般地，在选择正确的模型形式方面也存在问题。这个问题通常使用贝叶斯方法处理。简单的说，贝叶斯聚类方法基于由数据得到的估计，给出一个模型相对于另一个模型的概率。
（3）混合模型在有噪声和离群点时也可能有问题。
（1）混合模型比K均值或模糊K均值更一般，因为它可以使用各种类型的分布。
（2）混合模型可以发现不同大小或椭球形状的簇。
（3）基于模型的方法提供了一种消除与数据相关联的复杂性的方法。
（4）可以简化数据。如果模型是数据的一个好的匹配，用数据拟合一个模型是一种简化数据的好方法。
（5）模型更容易刻画所产生的簇，因为它们可以用少量的参数描述。
（6）很多数据实际上是随机处理的结果，因此应当满足这些模型的统计假设。
5.1.3 自组织映射（SOM）
& & SOM是一种基于神经网络观点的聚类和数据可视化技术。尽管SOM源于神经网络，但它更容易表示成一种基于原型的聚类的变形，与其他基于质心的聚类一样，SOM的目标是发现质心的集合（用SOM的术语，参考向量），并将数据集中的每个对象指派到提供该对象最佳近似的质心。用神经网络的术语，每一质心都与一个神经元相关联。与增量K均值一样，每次处理一个数据对象并更新质心。与K均值不同，SOM赋予质心地形序，也更新附近的质心。此外，SOM不记录对象的当前簇录属情况：并不像K均值，如果对象转移簇，并不明确地更新簇质心。当然，旧的簇质心可能是新的簇质心的近邻，这样它可能因此而更新。继续处理点，直到达到某个预先确定的界限，或者质心变化不大为止。SOM最终的输出是一个隐式定义的质心的集合。每个簇由最靠近某个特定质心的点组成。
& & SOM算法的显著特征是它赋予质心（神经元）一种地形（空间）组织。SOM使用的质心具有预先确定的地形序关系，这是不同于其他基于原型的聚类的根本差别。在训练的过程中，SOM使用每个数据点更新最近的质心和在地形序下邻近的质心。以这种方式，对于任意给定的数据集，SOM产生一个有序的质心集合。换言之，在SOM网格中互相靠近的质心比远离的质心更加密切相关。由于这种约束，可以认为二维点SOM质心在一个尽可能好地拟合n维数据的二维曲面上。SOM质心也可以看做关于数据点的非线性回归的结果。
SOM算法步骤：
（1）初始化质心；
（2）选择下一个对象；
（3）确定带该对象最近的质心；
（4）更新该质心和附近的质心，即在一个邻域内的质心；
（5）重复（2）到（4）直到质心改变不多或超过某个阈值；
（6）指派每个对象到最近的质心。
初始化：有多种方法：
（1）对每个分量，从数据中观测到的值域随机地选择质心的分量值。尽管该方法可行，但不一定是最好的，特别是对于快速收敛；
（2）从数据中随机地选择初始质心。
选择对象：由于算法可能需要许多步才收敛，每个数据对象可能使用多次，特别是对象较少时。然而如果对象较多，则并非需要使用每个对象。
优点：它将相邻关系强加在簇质心上，所以，互为邻居的簇之间比非邻居的簇之间更相关。这种联系有利于聚类结果的解释和可视化。
（1）用户必选选择参数、邻域函数、网格类型和质心个数；
（2）一个SOM簇通常并不对应单个自然簇，可能有自然簇的合并和分裂。例如：像其他基于原型的聚类技术一样，当自然簇的大小、形状和密度不同时，SOM倾向于分裂或合并它们。
（3）SOM缺乏具体的目标函数。SOM受限于质心之间的地形约束(为了更好的近似数据的质心的集合)；但是SOM的成功不能用一个函数来表达。这可能使得比较不同的SOM聚类的结果是困难的。
（4）SOM不保证收敛，尽管实际中它通常收敛。
5.2&基于密度的聚类
5.2.1&基于网格的聚类。
& & 基本思想：将数据空间划分成网格单元（方法：将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合。每个对象落入一个网格单元。网格单元对应的属性区间包含对象值）。然后由足够稠密的网格单元形成簇。这样的方法是有效地，至少对于低维数据如此。
算法步骤：
（1）定义一个网格单元集；
（2）将对象指派到合适的单元，并计算每个单元的密度；
（3）删除密度低于指定的阈值的单元；
（4）由邻近的稠密单元形成簇。
& & 定义网格单元：存在许多方法将每个属性的可能值分割成许多相邻的区间，如：等宽、等频、聚类等。网格的定义对聚类结果有很大的影响。
网格单元的密度定义：一种自然的方法是：定义网格单元（或更一般形状的区域）的密度为该区域中的点数除以区域的体积。一种常见的方法是使用具有相同体积的网格单元，使得每个单元的点数直接度量单元的密度。
& & 由邻接的稠密单元形成簇：问题是我们需要定义邻接单元的含义以及需要有效的技术发现邻接单元。
优点:可能是非常有效的。给定每个属性的划分，单遍数据扫描就可以确定每个对象的网格单元和网格单元的计数。此外，尽管潜在的网格单元数量可能很高，但是只需要为非空单元创建网格。这样，定义网格、将每个对象指派到一个单元并计算每个单元的密度的时间复杂度和空间复杂度为O(m)，其中，m是点的个数。如果邻接的、已占据的单元可以有效的访问（例如，通过使用搜索树）则整个聚类过程将非常高效，例如具有O(mlogm)的时间复杂度。
（1）像大多数基于密度的聚类算法一样、基于网格的聚类非常依赖于密度阈值的选择。（太高，簇可能或丢失；太低，本应分开的簇可能被合并）；
（2）如果存在不同密度的簇和噪声，则也许不可能找到适合于数据空间所有部分的值；
（3）随着维度的增加，网格单元个数迅速增加（指数增长）。即对于高维数据，基于网格的聚类倾向于效果很差。
5.2.2 子空间聚类
& & 基本思想：在所有维的子空间中寻找簇（稠密区域），由于子空间太多，因此需要有效的技术。目标是：发现簇和它们存在的维。CLIQUE是一种基于网格的聚类算法，它基于如下观察提供了一种有效的子空间聚类方法：高维空间的稠密区域暗示低维空间稠密区域的存在性。CLIQUE依赖于以下性质(该性质基于以下事实：低维单元的密度大于等于高维（维可以理解成属性的个数）单元的密度，即低维单元除了包含所有高维单元的点还包含其他的点。)：
基于密度的簇的单调性：如果一个点集在k维（属性）上形成一个基于密度的簇，则相同的点集在这些维的所有可能子集上也是基于密度的簇的一部分。
（1）提供了一种搜索子空间发现簇的有效技术（相似与Apriori）。
（2）用一小组不等式概括构成一个簇的单元列表的能力。缺点：它的缺点和其他基于网格的密度算法相同，其他缺点和Apriori相同，例如：（1）指数复杂度（2）正如频繁项集可以共享项一样，CLIQUE发现的簇也可以共享对象。允许簇重叠可能大幅度增加簇的个数，并使得解释更加困难。
5.2.3 DENCLUE
基本思想：
& & 使用核密度函数用个体数据对象影响之和对点集总密度建模，尽管DENCLUE本质上不是基于网格的技术，但是它使用基于网格的方法提高性能。 & & & DENCLUE也是一种基于密度的方法。结果总密度函数具有局部尖峰（称作局部吸引点），并且这些局部尖峰用来以自然的方式定义簇。集体的说，对于每个数据点，一个爬山过程找出与该点相关联的最近的尖峰，并且与一个特定的尖峰相关联的所有数据称为一个簇。
DENCLUE算法步骤：
（1）对数据点占据的空间推导密度函数；
（2）识别局部最大点（这是局部吸引点）；
（3）通过沿密度增长最大的方向移动，将每个点关联到一个密度吸引点；
（4）定义与特定的密度吸引点相关联的点构成的簇；
（5）丢弃密度吸引点的密度小于用户指定阈值的簇；
（6）合并通过密度大于或等于的点路径连接的簇。
核密度估计：
& & 核密度估计的目标是用函数描述数据的分布。对于核密度估计，每个点对总密度函数的贡献用一个影响或核函数表示。总密度函数仅仅是与每个点相关联的影响函数之和。核密度的计算可能相当昂贵，为了降低时间复杂度，DENCLUE使用一种基于网格的实现来有效地定义近邻，并借此限制定义点的密度所需要考虑的点的数量。首先，预处理步创建网格单元集。仅创建被占据的单元，并且这些单元及其相关信息可以通过搜索树有效地访问。然后计算点的密度，并找出其最近的密度吸引点。DENCLUE只考虑近邻中的点，即相同单元或者与该点所在单元相连接的单元中的点。即牺牲精度加快时间。
（1）DENCLUE提供了比其他基于网格的聚类技术和DBSCAN更加灵和、更加精确的计算密度的方法（DBSCAN是DENCLUE的特例）；
（2）DENCLUE擅长处理噪声和离群点，并且可以发现不同形状和不同大小的簇；
（1）DENCLUE可能比其他基于密度的聚类技术的计算开销更大；
（2）网格的使用对于密度估计的精度可能产生负面的影响；并且这使得DENCLUE容易受基于网格的方法共同存在的问题的影响，例如：很难选择合格的网格尺寸；
（3）对于高维数据和包含密度很不相同的簇的数据，DENCLUE可能有问题。
5.3&基于图的聚类
& & 数据的基于图的观点：数据对象用节点表示，而两个对象之间的邻近度用对应结点之间边的权值表示，簇用图的连通分支表示。
& & 本节介绍的基于图的聚类利用了下面的一些重要的性质：
（1）稀疏化邻近度图，只保留对象与其最近邻之间的连接。这种稀疏化对于处理噪声和离群点时有用的。稀疏化使得我们可以利用稀疏图开发有效的图划分算法；
（2）基于共享的最近邻个数，定义两个对象之间的相似度性度量。该方法基于如下观察：对象和它的最近邻通常属于同一个类。该方法有助于克服高维和变密度的问题。
（3）定义核心对象并构建环绕它们的簇。与DBSCAN一样，围绕核心对象构建簇导致一种聚类技术，可以发现不同形状和大小的簇。
（4）使用邻近度图中的信息，提供两个簇是否应当合并的更复杂的评估。具体地，两个簇合并，仅当结果簇具有类似于原来的两个簇的特性。（Chameleon算法的主要思想）。
5.3.1&稀疏化
& & 基于如下事实：对于大部分数据集，对象只与少量对象高度相似，而与大部分其他对象的相似性很弱。这一性质可以用来稀疏化邻近度图（矩阵）：在实际的聚类过程开始之前，将许多低相似性（高相异度）的值置0。例如，稀疏化可以这样进行，断开相似度（相异度）低于（高于）指定阈值的边，或仅保留连接到点的k个最近邻的边。后一种方法创建所谓k-最近邻图。邻近图的稀疏化使得使用图划分算法进行聚类称为可能。例如，Opossum和Chameleon都使用图划分。应该把邻近度图的稀疏化看成使用实际聚类算法之前的初始化步骤。我们常常将稀疏邻近度图修改，产生新的邻近度图，新的邻近度图还可以被稀疏化。正如我们在算法Jarvis-Patrick和基于SNN密度的聚类时看到的。
5.3.2 最小生成树聚类（MST）
& & MST（一种分裂层次聚类技术）从邻近度图的最小生成树开始，可以看作用稀疏化找出簇的应用。MST也产生与单链凝聚聚类相同的聚类。最小生成树可以看作一种特殊类型的稀疏化图。
算法步骤：
（1）计算相异度图的最小生成树；
（2）断开对应于最大相异度的边，创建一个新的簇；
（3）重复第（2）步直到只剩下单个簇。第二步也可以看作图的稀疏化。因此，MST可以看作一种基于相异度图稀疏化的聚类算法。
问题：MST怎么是个层次聚类呢？
5.3.3&Opossum:使用METIS的稀疏度相似度最优划分。
& & Opossum是一种专门为诸如文档或购物篮数据等稀疏、高维数据设计的聚类技术。与MST一样，它基于邻近度图的稀疏化进行聚类。然而， &Opossum使用METIS算法，该算法是专门为划分稀疏图设计的。
算法步骤如下：
（1）计算稀疏化的相似度图；
（2）使用METIS，将相似度图划分成k个不同的分支（簇）。算法中k参数是用户指定的参数，所使用的相似性度量是适合于稀疏、高维数据的度量，如扩充的Jaccard度量或余弦度量。 & & & &&
METIS图划分程序旨在
（1）最小化分支之间边的权值（相似度）；
（2）实现平衡约束。Opossum使用如下两种平衡约束中的一种：（1）每个簇中的对象个数必须粗略相等；或（2）属性值的和必须粗略相等。
（1）简单、速度快；
（2）将数据划分大小粗略相等的簇。
（1）由于簇被约束为大小粗略相等，因此簇可能被分裂或合并；
（2）如果使用Opossum产生大量簇，则这些簇通常是更大簇的相对纯的片段。事实上Opossum类似于Chameleon聚类过程的初始化步骤。
5.3.4 Chameleon：使用动态建模的层次聚类
& & 前面的凝聚层次聚类存在的问题：
（1）簇的相似性定义依赖于具体的算法。如组平均，将其相似性概念建立在两个簇之间的连接强度上（例如，两个簇中点的逐对相似性）。而单链使用簇的接近性（例如：不同簇中点的最小距离）来度量簇的相似性。尽管有两种基本方法，但是仅使用其中一种方法可能导致错误的簇合并。
（2）大部分聚类技术都有一个全局（静态）簇模型。例如，K均值假定簇是球形的，而DBSCAN基于单个密度阈值定义簇。使用这样一种全局模型的聚类方案不能处理诸如大小、形状和密度等簇特性在簇间变化很大的情况。
& & Chameleon是一种凝聚聚类技术，它解决前面提到的两个问题。它将数据的初始划分（使用一种有效的图划分算法）与一种新颖的层次聚类方案相结合。这种层次聚类使用接近性和互连性概念以及簇的局部建模。
& & 关键思想是：仅当合并后的结果簇类似于原来的两个簇时，这两个簇才应当合并。因为这种方法依赖于蔟对而不是全局模型（所以称作动态建模），Chameleon能够处理包含具有各种不同特性的簇的数据。相对接近度（RC）：是被簇的内部接近度规范化的两个簇的绝对接近度。连个簇合并，仅当结果簇中的点之间的接近程度几乎与原来的每个簇一样。相对互连度（RI）：是被簇的内部互连度规范化的两个簇的绝对互连度。如果结果簇中的点之间的连接几乎与原来的每个簇一样强，两个簇合并。RI和RC可以用多种不同的方法组合，产生自相似性的总度量。Chameleon就是使用合并最大化自相似性的蔟对。
算法步骤：
（1）构造k-最近邻图；
（2）使用多层图划分算法划分图；
（3）合并关于相对互连性和相对接近性而言，最好地保持簇的自相似性的簇；
（4）重复（3）直到不再有可以合并的簇。
& & 在算法Chameleon中可以用参数指定，让Chameleon一步合并多个簇对，并且在所有的对象都合并到单个簇之前停止。步骤的第二步——图划分：一旦得到稀疏化图，就可以使用METIS等有效的多层图划分算法来划分数据集。Chameleon从一个全包含的图（簇）开始。然后，二分当前最大的子图（簇），直到没有一个簇多于MIN_SIZE个点，其中MIN_SIZE是用户指定的参数。这一过程导致大量大小相等的、良连接的顶点（高度相似的数据点）的集合。目标是确保每个划分包含的对象都大部分来自一个真正的簇。
& & 算法时间复杂度（假设m是数据点数，p是划分的个数）：在p个划分进行凝聚层次聚类需要O(p2logp)时间，划分图需要的时间总量是O(mp+mlogm)。建立k-邻近图如果使用k-d 树或类似的数据结果，需要O(mlogm)时间。但是这种数据结构只适用于低维数据，因此，对于高维数据，稀疏化的时间复杂度是O(m2)。空间复杂度：由于只需要存放k-最近邻表，空间复杂度是O(km)加上存放数据所需要的空间。
能够很好的聚类空间数据，即便存在噪声和离群点，并且簇具有不同的形状、大小和密度。
（1）算法假定有稀疏化和图划分过程产生的对象组群是子簇，即一个划分中的大部分点属于同一个真正的簇。如果不是，则凝聚层次聚类将混合这些错误，因为它绝对不可能再将已经错误地放到一起的对象分开。这样，当划分过程未产生子簇时，Chameleon就有问题，对于高维数据，常常出现这种情况。
（2）Chameleon并不丢弃噪声点，而是把它们指派到簇中。
共享最近邻相似度。
& & 本节引入一种相似度的间接方法，它基于以下原理：如果两个点与相同的点中的大部分都相似，则即使直接的相似性度量不能指出，它们也相似。一个对象的大多数最近邻通常仍然属于同一个类。
& & 相似性的SNN版本解决的两个问题：低相似性和不同密度。
& & SNN相似度计算。关键思想是：在定义相似性度量时考虑点的环境。点的环境可以用相似性的共享最近邻（SNN）定义量化。本质上讲，只要两个对象都在对方的最近邻列表中，SNN相似度就是它们共享的近邻个数。
计算共享最近邻相似度的算法步骤：
（1）找出所有点的k-最近邻；
（2）if 两个点x 和
5.3.5&&&&&&&度图称作SNN相似度图。
& & 由于许多对象之间的SNN相似度为0，所以相似度图非常稀疏。SNN相似度可以处理如下情况：一个对象碰巧与另一个对象相对接近，但属于不同的类。在这种情况下，对象一般不共享许多近邻，并且它们的SNN相似度低。SNN相似度也能处理变密度的问题。由于SNN相似度只依赖于两个对象共享的最近邻的个数，而不是这些近邻相距多远。所以，SNN相似度关于点的密度进行自动缩放。
5.3.6&&&&&&&Jarvis-Patrick聚类算法
& & JP聚类算法用SNN相似度取代两个点之间的邻近度。然后使用一个阈值来稀疏化SNN相似度矩阵。使用图的术语就是，创建并稀疏化SNN相似度图。簇是SNN图的连通分支。
JP聚类算法步骤：
（1）计算SNN相似度图；
（2）使用相似度阈值，稀疏化相似度图；
（3）找出稀疏化的SNN相似度图的连通分支（簇）。JP算法的存储需求仅为O(km)，因为即便在初始阶段也不需要存放整个相似度矩阵。JP聚类的基本时间复杂度是O(m2)。因为k-最近邻列表的创建可能需要计算O(m2)个邻近度。然而，如果对低维欧几里得数据，可以使用像k-d树来有效地找出k-最近邻，而不必计算整个相似度矩阵。时间复杂度就为O(mlogm,)。
（1）删除处理噪声和离群点，并且能够处理不同大小、形状和密度的簇；
（2）该算法对高维数据效果良好，尤其擅长发现强相关对象的紧致簇。
（1）算法优点脆弱，即它可能分裂真正的簇，或者合并本应该分开的簇；
（2）并非所有的对象都被聚类（剩下的对象可以添加到已有的簇中）；
（3）与其他聚类算法一样，选择好的参数值可能是一个挑战。
5.3.7 SNN密度。
& & 解决的问题：传统的欧几里得密度在高维空间变得没有意义。由于SNN相似性度量反映了数据空间中点的局部结构，因此它对密度的变化和空间的维度都相对不太敏感。所以可以基于它定义高维空间的密度。SNN密度度量一个点被类似的点（关于最近邻）包围的程度。这样，在高密度和低密度区域的点一般具有相对较高的SNN密度，而在从低密度到高密度过度的区域中的点（簇间的点）将倾向于具有低SNN密度。这样的方法可能更适合这样的数据集，其中密度变化很大，但是低密度的簇仍然是有趣的。具有高SNN密度（即SNN图中的高连接性）的点是候选代表点或核心点，因为它们倾向于在簇的内部；而具有低连接性的点是候选噪声点或离群点，因为它们多半在环绕簇的区域中。
5.3.8 基于SNN密度的聚类
& & 是一种将SNN密度与DBSCAN算法结合在一起的算法。类似于JP算法，都以SNN相似度图开始。然而，基于SNN密度的聚类算法简单地使用DBSCAN，而不是使用阈值稀疏化SNN相似度图，然后取连通分支作为簇。
算法步骤：
（1）计算SNN相似度图；
（2）以用户指定的参数Eps和MinPts，使用DBSCAN。算法自动地确定数据中的簇的个数。注意并非所有的点都被聚类。被丢弃的点包括噪声和离群点，以及没有很强地连接到一组点的那些点。基于SNN密度的聚类发现这样的簇，簇中的点相互之间都是强连接的。依赖于应用，我们可能希望丢弃许多点。例如：基于SNN密度的聚类对于发现文档组中的主题效果很好。
优缺点：优缺点类似于JP聚类，然而，核心点和SNN密度的使用大大增加了该方法的能力和灵活性，不像DBSCAN，它可以用于高维数据和簇具有不同密度的情况。不像JP聚类简单地使用阈值，然后取连通分支作为簇，基于SNN密度的聚类使用SNN密度和核心点概念的方法。
5.4&可伸缩的聚类算法
& & 层次聚类的存储需求一般是O(m2)，其中m是对象的个数。使用k-d树或R*树，一般产生数据空间的层次划分，可以用来减少发现点的最近邻所需要的时间。注意，基于网格的聚类方法也划分数据空间。使用抽样可以降低时间复杂度，但是，抽样的问题是小簇可能丢失。另一种降低时间复杂度的方法是，使用某种有效的技术，将数据划分成不相交的集合，然后分别对这些集合聚类。最终的簇的集合是这些分离的簇的集合的并，或者通过合并和对分离的簇的集合求精得到。一个例子是二分K均值，所以二分K均值显著地比一般的K均值快。另一种角力方法：首先汇总数据（通过一遍扫描），然后在汇总数据上聚类。特殊地，领导者算法或者将一个数据对象放进最近的簇（如果该簇足够近），或者创建一个包含当前对象的新簇。这种方法关于对象个数是线性的，可以用来汇总数据，以便使用其他聚类技术。BIRCH算法使用了类似的概念。
5.4.1&BIRCH
& & 它用于欧几里得向量空间数据，即平均值是有意义的数据。BIRCH能够用一遍扫描有效地对这种数据进行聚类，并可以使用附加的扫描改进聚类。 & &&BIRCH还能够有效的处理离群点。BIRCH不要求数据都在内存中。BIRCH基于聚类特征（CF）和CF树的概念。
& & 其基本思想是：数据点（向量）的簇可以用三元组(N,LS,SS)表示。N：簇中点的个数；LS：点的线性和；SS点的平方和。这些量可以增量的更新。CF树是一颗高度平衡的树。叶节点由一个聚类特征序列CFi组成，叶节点的直径必须小于参数化的阈值T。可以通过调整阈值参数T，可以控制树的高度。目标是通过调整参数T，将CT树保存在内存中。CF树在扫描时创建。BIRCH在每次分裂后跟随一个合并步。这一步的目的是提高空间利用率，避免不对称的数据输入顺序带来的问题。BIRCH还有一个删除离群点的过程。当用尽内存而需要重建树时，可以将离群点写到磁盘。（离群点定义为包含的点远小于平均情况的结点）。在该过程的特定点，扫描离群点，看是否可以将它们吸收到树中，而不导致树增长。如果可以，则吸收它们，如果不可以，则删除它们。&
算法步骤：
（1）通过创建汇总数据的CF树，将数据转入内存；
（2）根据第3阶段的需要，构造一颗较小的CF树。T增值，然后重新插入叶顶点项（簇）。由于T已增加，某些簇将合并；
（3）进行全局聚类。可以使用不同形式的全局聚类（使用所有簇之间的逐对距离的聚类）。然而，我们选取一种凝聚的层次技术，因为聚类特征存放了对于特定聚类类型很重要的汇总信息，可以使用全局聚类算法，就像它用于CF代表的簇中的所有点上一样；
（4）使用步骤（3）发现的簇质心，重新分布数据点，从而发现新的簇集合。这克服了可能在BIRCH第一阶段发现的问题。由于页面大小的限制和参数T的缘故，应当在一个簇中的点有时可能被分裂，而应当在不同簇中的点有时可能被合并。此外，如果数据集中包含重复点，则这些点根据出现次序的不同，有时可能被聚类到不同的类。通过多次重复本阶段，过程将收敛到一个局部最优解。
5.4.2 CURE
& & 它能够处理大型数据、离群点和具有非球形和非均匀大小的簇的数据的方法。CURE使用簇中的多个代表点来表示一个簇。理论上，这些点捕获了簇的几何形状。选取的点的个数是一个参数，但是业已发现10或更大的值效果很好。CURE使用一种凝聚层次聚类方案进行实际的聚类。两个簇之间的距离是任意两个代表点（在它们向它们代表的中心收缩之后）之间的最短距离。尽管这种方法与我们看到的其他层次聚类方案不完全一样。但是如果 =0，它等价于基于质心的层次聚类；而
=1时它与单链层次聚类大致相同。注意，尽管使用层次聚类方案，但是CURE的目标是发现用户指定个数的簇。CURE利用层次聚类过程的特性，在聚类过程的两个阶段删除离群点。首先，如果一个簇增长缓慢，则这意味它主要由离群点组成，因为根据定义，离群点远离其他点，并且不会经常与其他点合并。在CURE中，离群点删除的第一个阶段一般出现在簇的个数是原来点数的1/3时。第二个离群点删除阶段出现在簇的个数达到K（期望的簇的个数）的量级时。此时，小簇又被删除。由于CURE在最坏情况下复杂度为O(m2logm)，它不能直接用于大型数据集。因此CURE使用了两种技术来加快聚类过程。第一种技术是取随机样本，并在抽样的数据点上进行层次聚类。随后是最终扫描，通过选择具有最近代表点的簇，将数据集中剩余的点指派到簇中。在某些情况下，聚类所需要的样本仍然太大，需要第二种技术。在这种情况下，CURE划分样本数据，然后聚类每个划分中的点。这种预聚类步后通常紧随中间簇的聚类，以及将数据集中的每个点指派到一个簇的最终扫描。
CURE算法步骤：
（1）由数据集抽取一个随机样本。值得注意的是，CURE的文章明确地推出一个公式，指出为了以较高的概率确保所有的簇都被最少的点代表，样本应当多大；
（2）将样本划分成p个大小相等的划分；
（3）使用CURE的层次聚类算法，将每个划分中的点聚类成个簇，得到总共个簇。注意，在此处理过程中将删除某些离群点；
（4）使用CURE的层次聚类算法对上一步发现的个簇进行聚类，直到只剩下K个簇；
（5）删除离群点。这是删除离群点的第二阶段；
（6）将所有剩余的数据点指派到最近的簇，得到完全聚类。CURE抽样：关键问题是样本是否具有代表性，即它是否捕获了感兴趣的特征。对于聚类，该问题是我们是否能够在样本中发现与整个样本对象集中相同的簇。CURE的创建者推导出了一个样本大小的界，指出为了（以较高的概率）确保我们从每个簇至少得到一定数量的点，
数。再次说明，以如下方式使用抽样。首先抽取一个样本，然后使用对该样本进行聚类。找到簇之后，将每个未聚类的点指派到最近的簇。
划分：关键问题是如何选择和。的时间复杂度是2)或更高，并且还需要将所有的数据放在内存。因此，我们希望选择尽可能小的，使得整个划分可以以“合理的”时间在内存处理。选择和的另一个因素涉及聚类质量。具体的说，目标是选取和的值，使得同一个基本簇的对象最终在一个簇中。
&使用哪种聚类算法
& & 常见生物学分类法，层次是首选。对于旨在汇总的聚类，划分聚类是常用的。基于原型的聚类方案以及某些基于图的聚类方案（全链、质心和）倾向于产生全局簇。相比之下，基于密度的聚类技术和某些基于图的聚类技术（如单链）倾向于产生非全局的簇，因而包含许多相互之间不很相似的对象。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：151711次
积分：2319
积分：2319
排名：第12714名
原创：75篇
评论：18条
(10)(11)(2)(2)(2)(32)(1)(12)(14)