聚类算法

浅夏110

一.串行聚类算法
' K3 J/ J7 m. a) e) a4 ^9 f6 _
$ S, ^2 c2 `+ w- G2 D3 u1.1 划分方法（partitioning method）
" q& T) ^7 C, V, j0 N. }  b5 R
& h8 j8 R) Q( H划分方法首先根据给定要构建划分的数目k创建一个初始划分，然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是：在同一类中的对象之间尽可能“接近”或相关，而不同类中的对象之间尽可能“远离”或不同。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方法：
1 h4 H9 z4 Y( n6 I+ n
0 u5 {7 ]& S  M（a）K-平均（K-MEANS）算法，在该算法中，每个簇用该簇中对象的平均值来表示。
- {) ~- N3 a' ]
（b）K-中心点（K-MEDOIDS）算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。

1. K-means算法
4 Y2 w; ]& @# I, d: Y2 u
4 x+ V6 N5 [/ ^; v/ C, a0 nK-means算法首先随机选择k个对象，每个对象代表一个聚类的质心。对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚类中。然后，计算每个聚类的新质心。重复上述过程，直到准则函数会聚。通常采用的准则函数是平方误差准则函数。


/ p  a( L4 b2 V- \- v. [' UK-means聚类算法的具体步骤如下：

1) 从数据集中选择k个质心C1，C2，… ，Ck作为初始的聚类中心；

2) 把每个对象分配到与之最相似的聚合。每个聚合用其中所有对象的均值来代表，“最相似”就是指距离最小。对于每个点Vi，找出一个质心Cj，使它们之间的距离d(Vj，Cj)最小，并把Vi分配到第j组；
% p0 n$ z. b/ Z+ O
3) 把所有的点都分配到相应的组之后，重新计算每个组的质心Cj；

4) 循环执行第2)步和第3)步，直到数据的划分不再发生变化。

# |  [- j) y3 q该算法具有很好的可伸缩性，其计算复杂度为O(nkt)，其中，t是循环的次数。K-means聚类算法的不足之处在于它要多次扫描数据库，此外，它只能找出球形的类，而不能发现任意形状的类。还有，初始质心的选择对聚类结果有较大的影响，该算法对噪声很敏感。

2. K-medoids算法
4 l2 o0 T' ]2 }: l/ N
% m3 ~: ?, @) U; ?K-medoids算法的过程和上述k-means的算法过程相似，唯一不同之处是：k-medoids算法用类中最靠近中心的一个对象来代表该聚类，而k-means算法用质心来代表聚类。在k-means算法中，对噪声非常敏感，因为一个极大的值会对质心的计算带来很大的影响。而k-medoid算法中，通过用中心来代替质心，可以有效地消除该影响。

K-medoids算法首先随机选择k个对象，每个对象代表一个聚类，把其余的对象分别分配给最相似的聚类。然后，尝试把每个中心分别用其他非中心来代替，检查聚类的质量是否有所提高。若是，则保留该替换。重复上述过程，直到不再发生变化。
+ k' q$ F4 [: {( y3 f; r) G" B
常见的k-medoids算法有PAM(Partitioning Around Medoids)算法、CLARA(Clustering LARge Application)算法、CLARANS(Clustering LARge Application based upon Randomized Search)算法。当存在“噪声”和孤立点数据时，k-medoids算法比可k-means更健壮，这是因为中心点不像平均值那么容易被极端数据影响。但是，k-medoids算法的执行代价比k-means高。
. b# A3 d- f- [2 {5 Z5 y/ P
总结：划分方法具有线性复杂度，聚类的效率高的优点。然而，由于它要求输入数字k确定结果簇的个数，并且不适合于发现非凸面形状的簇，或者大小差别很大的簇，所以这些启发式聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。
7 A/ D- y0 ~/ Q0 |, x
+ y0 [  q* A- {' r, Z1 Z1.2 层次方法（hierarchical method）
层次方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的[30]。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个（层次的最上层），或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。

主要的凝聚聚类算法有CURE,CHAMELEON,BIRCH,ROCK等。
5 N1 Y' B7 o$ H/ B! Z
  M: z7 N5 z) p9 g9 Y! h1．BIRCH算法
, T3 u5 a0 J: f% ]* D
1 Z* p  q) V( fBIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)算法使用了一种叫做CF-树(聚类特征树，即Clustering Feature Tree)的分层数据结构，来对数据点进行动态、增量式聚类。CF-树是存储了层次聚类过程中的聚类特征信息的一个加权平衡树，树中每个节点代表一个子聚类，并保持有一个聚类特征向量CF。每个聚类特征向量是一个三元组，存储了一个聚类的统计信息。聚类特征向量中包含了一个聚类的三个统计信息：数据点的数目N，这N个数据点的线性和，以及这N个数据点的平方和SS。一个聚类特征树是用于存储聚类特征CF的平衡树，它有两个参数：每个节点的最大子节点数和每个子聚类的最大直径。当新数据插入时，就动态地构建该树。与空间索引相似，它也用于把新数据加入到正确的聚类当中。

BIRCH算法的主要目标是使I/0时间尽可能小，原因在于大型数据集通常不能完全装入内存中。BIRCH算法通过把聚类分为两个阶段来达到此目的。首先通过构建CF-树对原数据集进行预聚类，然后在前面预聚类的基础上进行聚类。

2 E% @7 ]* l% l& k+ y8 k! q7 A% t2．CURE算法
1 b6 l; B: `/ R" e
1 g( Z3 B8 \% K4 M* YCURE(Clustering Using Representative)算法选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。针对大型数据库，CURE采用随机取样和划分两种方法的组合：一个随机样本首先被划分，每个划分再被部分聚类。

. o$ V4 H. u0 e, m. T0 @7 n3．ROCK算法
) _; {6 ?, P$ T+ _" J
CURE算法不能处理枚举型数据，而ROCK算法是在CURE基础之上适用于枚举数据的聚结分层聚类算法。通过把两个聚类的聚集相互连接度(aggregate interconnectivity)与用户定义的静态相互连接模型相比较，从而度量两个聚类之间的相似度。其中，两个聚类的相互连接度是指两个聚类之间的交叉连接数目，而连接link(pi,pj)是指这两点之间的共同邻居数。换句话说，聚类相似度是用不同聚类中又共同邻居的点的数目来确定的。

% m  p# Q, S. i% k/ a  RROCK算法首先用相似度阀值和共同邻居的概念，从给定的数据相似度矩阵中构建一个稀疏图，然后对该稀疏图使用分层聚类算法进行聚类。
  s3 c# ^' w* \% G7 m" W9 V& E7 i
! k! a2 w2 D9 p$ z5 [: Y4．Chameleon算法

2 Q5 [9 g; U; C& j! HChameleon（变色龙）是一个利用动态模型的层次聚类算法。算法思想是：首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类，然后用一个凝聚的层次聚类算法通过反复地合并子类来找到真正的结果簇。它既考虑了互连性，又考虑了簇间的近似度，特别是簇内部的特征，来确定最相似的子簇[31]。
! r' Y+ c& c! T! b) ^+ v) @
' r( s1 w1 Y' F! Z9 bChameleon跟CURE和DBSCAN相比，在发现高质量的任意形状的聚类方面有更强的能力。但是，在最坏的情况下，高维数据的处理代价可能对n个对象需要O(n2)的时间。
0 b" _1 o. k; V; T+ A/ I# C3 Z
总结：层次的方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果：（a）在每层划分中，仔细分析对象间的“联接”，例如CURE中的做法。（b）综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。
( X/ g" m4 Z: I7 |1 @# M
1.3 基于密度的方法（density-based method）
绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法，其主要思想是：只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。常见的基于密度的聚类算法有DBSCAN,OPTICS,DENCLUE等。

- W; d3 }7 a% e1. DBSCAN算法
  w8 [  r2 z! L9 [" {
DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一个基于高密度连接区域的密度聚类方法。DBSCAN通过检查数据库中每个点的ε-邻域来寻找聚类。如果一个点p的ε-邻域包含多于MinPts个点，则创建一个以p作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。
; h0 W3 I" E9 Q& U8 k; V
2. OPTICS算法
  a: ]. _. g3 G- V9 R" {. q. ~" }
6 \3 Y9 \$ Q3 t9 P9 {3 t% wOPTICS(Ordering Points To Identify the Clustering Structure)通过对象排序识别聚类结构。OPTICS没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇次序（cluster ordering）。这个次序代表了数据的基于密度的聚类结构。它包含的信息，等同于从一个宽广的参数设置范围所获得的基于密度的聚类。也就是说，对于一个恒定的参数MinPts值，可以同时处理一组距离参数值。

* H, C6 x- F: y) n* {) V+ I; O5 jOPTICS在选择参数方面具有比DBSCAN较高的灵活性，在采用空间索引时，复杂度为O(nlogn)，和DBSCAN时间复杂度相同。但是，它需要额外的空间存储每个对象的核心距离和一个适当的可达距离。

3． DENCLUE算法

4 o8 l' n  q: k- ?! Z& Y4 ^; ^. c& _DENCLUE(DENsity based CLUstEring)是一个基于一组密度分布函数的聚类算法。它是对k-means聚类算法的一个推广：k-means算法得到的是对数据集的一个局部最优划分，而DENCLUE得到的是全局最优划分。
, V. q: F" i3 |% e2 ~  D
DENCLUE算法有一个坚实的数学基础，概括了其他的聚类方法，包括基于划分的、层次的、及基于位置的方法；同时，对于有大量“噪声”的数据集合，它有良好的聚类特征；对于高维数据集合的任意形状的聚类，它给出了一个基于树的存储结构来管理这些单元，因此比一些有影响的算法（如DBSCAN）速度要快。但是，这个方法要求对密度参数σ和噪声阈值ξ进行仔细的选择，如果选择不当则可能显著地影响聚类结果的质量。

1.4 基于网格的方法（grid-based method）
2 a* q4 M% O* l0 y: N$ E基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构（即量化的空间）上进行。基于网格的聚类算法主要有STING, WaveCluster, CLIQUE等。

2 O( [# B9 I  x: I1 _' s( ^1．STING算法

STING(Statistical Information Grid-based method)是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先计算和存储。这些统计信息用于回答查询。

8 {$ O& x$ W1 F# F4 K9 N7 G! O6 WSTING有几个优点：（i）由于存储在每个单元中的统计信息提供了单元中的数据不依赖于查询的汇总信息，所以基于网格的计算是独立于查询的；（ii）网格结构有利于并行处理和增量更新；（iii）该方法的主要优点是效率很高：STING扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O(n)，其中n是对象的数目。在层次结构建立后，查询处理时间是O(g)，这里g是最低层网格单元的数目，通常远远小于n。该算法的缺点：由于STING采用了一个多分辨率的方法进行聚类分析，STING聚类的质量取决于网格结构的最低层的粒度。如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的力度太粗，将会降低聚类分析的质量；而且，STING在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的形状是isothetic，即所有的聚类边界或者是水平的，或者是竖直的，没有对角的边界。尽管该技术有快速的处理速度，但可能降低簇的质量和精确性。
5 E6 D+ D" v4 i) u4 K1 _
2． WaveCluster算法

# R5 s& G, _8 ~- `+ q) Q3 j5 cWaveCluster(Clustering with Wavelets)采用小波变换聚类，它是一种多分辨率的聚类算法，它首先通过在数据空间上加一个多维网格结构来汇总数据，然后采用一种小波变换来变换原特征空间，在变换后的空间中找到密集区域。

WaveCluster的计算复杂度是O(n)，能有效地处理大数据集合；发现任意形状的簇；成功地处理孤立点；对于输入的顺序不敏感；不要求指定诸如结果簇的数目或邻域的半径等输入参数；在实验分析中，WaveCluster在效率和聚类质量上优于BIRCH，CLARANS和DBSCAN；实验分析也发现WaveCluster能够处理多达20维的数据。但是，对数学建模的知识要求较高[33]。
5 ~' j6 i7 B; b$ ^5 X; \
3． CLIQUE算法
, g' ^2 b  g4 `; c8 p
. X; b0 h  L- kCLIQUE(Clustering In QUEst)算法综合了基于密度和基于网格的聚类方法,它的中心思想是:首先，给定一个多维数据点的集合，数据点在数据空间中通常不是均衡分布的。CLIQUE区分空间中稀疏的和“拥挤的”区域（或单元），以发现数据集合的全局分布模式。接着，如果一个单元中的包含数据点超过了某个输入模型参数，则该单元是密集的。在CLIQUE中，簇定义为相连的密集单元的最大集合。
! X% y. k9 w  [* R5 Z5 `3 n
1 z0 ~# o2 H- B3 }) |CLIQUE算法能自动发现最高维中所存在的密集聚类；它对输入数据元组顺序不敏感；也不需要假设（数据集中存在）任何特定的数据分布；它与输入数据大小呈线性关系；并当数据维数增加时具有较好的可扩展性。但是，在追求方法简单化的同时往往就会降低聚类的准确性。
, v+ Y0 @- j* p$ ?# B! Z
, P- j6 m5 |& M* Q9 a5 H3 J1.5 基于模型的方法（model-based method）
基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类方法。基于模型聚类方法主要有两种：统计学方法和神经网络方法。
4 w7 [6 p9 Z6 [  b% Y( P- y9 x
1．统计学方法
  ?$ Z4 P" n2 i& G
' [8 E: X# G+ w7 O机器学习中的概念聚类就是一种形式的聚类分析。给定一组无标记数据对象，它根据这些对象产生一个分类模式。与传统聚类不同，后者主要识别相似的对象；而概念聚类则更进一步，它发现每组的特征描述；其中每一组均代表一个概念或类，因此概念聚类过程主要有两个步骤：首先完成聚类；然后进行特征描述。因此它的聚类质量不再仅仅是一个对象的函数；而且还包涵了其它因素，如所获特征描述的普遍性和简单性。

+ M: u1 C4 Z6 h7 R% A大多概念聚类都采用了统计方法，也就是利用概率参数来帮助确定概念或聚类。每个所获得的聚类通常都是由概率描述来加以表示[34]。

COBWEB是一种流行的简单增量概念聚类算法。它的输入对象用分类属性-值对来描述。它以一个分类树的形式创建层次聚类。分类树的每个节点对应一个概念，包含该概念的一个概率描述，概述被分在该节点下的对象。在分类树某个层次上的兄弟节点形成了一个划分。为了用分类树对一个对象进行分类，采用了一个部分匹配函数沿着“最佳”匹配节点的路径在树中向下移动。寻找可以分类该对象的最好节点。这个判定基于将对象临时置于每个节点，并计算结果划分的分类效用。产生最高分类效用的位置应当是对象节点一个好的选择。但如果对象不属于树中现有的任何概念，则为该对象创建一个新类。

/ G2 l+ H. Q( o2 I3 p0 h; wCORWEB的优点在于：他不需要用户输入参数来确定分类的个数，它可以自动修正划分中类的数目。缺点是：首先，它基于这样一个假设：在每个属性上的概率分布是彼此独立的。由于属性间经常是相关的，这个假设并不总是成立。此外，聚类的概率分布表示使得更新和存储类相当昂贵。因为时间和空间复杂度不只依赖于属性的数目，而且取决于每个属性的值的数目，所以当属性有大量的取值时情况尤其严重。而且，分类树对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂性的剧烈变化。

# ~" [$ A! B& h, w' f, L; q' t2．神经网络方法

1 M. ^; H+ @9 U( l; i神经网络聚类方法是将每个簇描述成一个标本。标本作为聚类的一个“原型”；它不一定对应一个特定的数据实例或对象。可以根据新对象与哪个标本最相似（基于某种距离计算方法）而将它分派到相应的聚类中。可以通过聚类的标本来预测分派到该聚类的一个对象的属性。上一章对此已经作了详细描述，这里不再详述。
$ c4 B% u5 r2 ]* E) x
; F# z' h; l; u) b+ p# X二 、并行聚类算法

! ~8 g" R1 _( a8 i; F对于并行算法而言，由于数据量非常庞大，通常情况下，数据挖掘算法对内存和硬盘的需求非常大。特别是对内存的需求，经常会出现内存不能一次装载所需的数据，需要备用存储设备的情况，此时如果处理不好就会严重降低算法的性能。
! p) c5 j: O& j1 y+ T9 f: j& c" S
开发数据挖掘并行方法有两种途径[35]：
9 z6 Q. C7 M0 Q9 r6 ]- g2 N
其一是对已有的串行算法进行改进，挖掘其中的并行性质并加以利用，使得串行程序并行化；
6 n) \( O/ u: S0 i7 {4 Y, x' ]7 A
5 w3 e( R% ]) g, `9 X. I$ ^其二是对问题的本质重新审视，设计全新的并行算法。

; N' C8 y' q) c第一种途径相对容易一些，但是并行粒度较小，通信量较大。第二种途径需要全新设计，但如果成功，就会得到粗粒度并行算法，适合于在分布式并行机上应用。其实，数据挖掘算法天生就具有丰富的并行性能。但是，对于给定的串行算法，却很难找到一个理想的并行化方案，硬件特征和问题的性质对于并行化有重要影响。几乎所有的数据挖掘算法以组合最优化过程为特征，其模型建立以训练集上的启发式贪婪搜索为基础。

在数据挖掘算法中有两种形式的并行性质：任务并行和数据并行。对于任务并行，计算模型被划分到各个处理器中，并分别计算模型的一部分，然后再同其它处理器通过消息通信等方式进行协调，以得到一个全局模型。其实，这里的“任务并行”就是“串行程序并行化”。负载均衡可能是任务并行关注的主要问题[36]。对于数据并行，训练集首先被划分到各个处理器中（或者数据集本身就是分布式存储的），然后各个处理器同时工作，建立各自的局部模型。最后各个局部模型被整合为一个全局模型。其实，这里的“数据并行”就是“分布式并行”。