' `: c5 Y. V) B# g5 _" C- S# v" K总结:层次的方法的缺陷在于,一旦一个步骤(合并或分裂)完成,它就不能被撤消,该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果:(a)在每层划分中,仔细分析对象间的“联接”,例如CURE中的做法。(b)综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法,然后用迭代的重定位来改进结果。 / w# o/ c4 k/ [8 s" l + W- f3 d* N+ d3 h# C) V" r! I1.3 基于密度的方法(density-based method)$ b, l5 X/ ~$ q; ]% y+ N$ e
绝大多数划分方法基于对象之间的距离进行聚类,这样的方法只能发现球状的簇,而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法,其主要思想是:只要邻近区域的密度(对象或数据点的数目)超过某个阈值,就继续聚类。也就是说,对给定类中的每个数据点,在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据,发现任意形状的簇。常见的基于密度的聚类算法有DBSCAN,OPTICS,DENCLUE等。 1 B. L9 ?4 U+ _8 n Z7 Y0 e+ D* c ( @" y7 Y% f, M3 _8 R. T3 g1. DBSCAN算法 + t' _* O+ G/ }* F. v( _: ?9 R* l# g5 i* {- [
DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一个基于高密度连接区域的密度聚类方法。DBSCAN通过检查数据库中每个点的ε-邻域来寻找聚类。如果一个点p的ε-邻域包含多于MinPts个点,则创建一个以p作为核心对象的新簇。然后,DBSCAN反复地寻找从这些核心对象直接密度可达的对象,这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时,该过程结束。. i- b1 _; ?3 L# U- t! C
5 p6 T% P0 e. M3 Q- _2. OPTICS算法, v' k$ m8 S: C' _0 R2 S: ~
: N. f' {" H) W& D8 W2 uOPTICS(Ordering Points To Identify the Clustering Structure)通过对象排序识别聚类结构。OPTICS没有显式地产生一个数据集合簇,它为自动和交互的聚类分析计算一个簇次序(cluster ordering)。这个次序代表了数据的基于密度的聚类结构。它包含的信息,等同于从一个宽广的参数设置范围所获得的基于密度的聚类。也就是说,对于一个恒定的参数MinPts值,可以同时处理一组距离参数值。 2 F3 D% ?8 \! s0 P Y! Y 8 S; n- `; F. m8 h- BOPTICS在选择参数方面具有比DBSCAN较高的灵活性,在采用空间索引时,复杂度为O(nlogn),和DBSCAN时间复杂度相同。但是,它需要额外的空间存储每个对象的核心距离和一个适当的可达距离。( v# H) \. d6 n- s5 F
- w" F! @8 o3 K ?% `) uDENCLUE算法有一个坚实的数学基础,概括了其他的聚类方法,包括基于划分的、层次的、及基于位置的方法;同时,对于有大量“噪声”的数据集合,它有良好的聚类特征;对于高维数据集合的任意形状的聚类,它给出了一个基于树的存储结构来管理这些单元,因此比一些有影响的算法(如DBSCAN)速度要快。但是,这个方法要求对密度参数σ和噪声阈值ξ进行仔细的选择,如果选择不当则可能显著地影响聚类结果的质量。1 v* k( ?; {# B l
& e G" @& ~' }# U4 _9 q1.4 基于网格的方法(grid-based method) 8 `. h# D( i. ^基于网格的方法把对象空间量化为有限数目的单元,形成了一个网格结构。所有的聚类操作都在这个网格结构(即量化的空间)上进行。基于网格的聚类算法主要有STING, WaveCluster, CLIQUE等。1 [% s% e0 x1 h8 M
% _( z0 C s# c* B* H( O
1.STING算法) g; ]5 q+ R- Z. L% v
7 k$ g! _' S' ^/ } Y4 }STING(Statistical Information Grid-based method)是一种基于网格的多分辨率聚类技术,它将空间区域划分为矩形单元。针对不同级别的分辨率,通常存在多个级别的矩形单元,这些单元形成了一个层次结构:高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息(例如平均值、最大值和最小值)被预先计算和存储。这些统计信息用于回答查询。 / W5 H r- ?, o4 d' p) E( G6 o2 W2 ?% R ~- s: a! j+ |. V' U8 i
STING有几个优点:(i)由于存储在每个单元中的统计信息提供了单元中的数据不依赖于查询的汇总信息,所以基于网格的计算是独立于查询的;(ii)网格结构有利于并行处理和增量更新;(iii)该方法的主要优点是效率很高:STING扫描数据库一次来计算单元的统计信息,因此产生聚类的时间复杂度是O(n),其中n是对象的数目。在层次结构建立后,查询处理时间是O(g),这里g是最低层网格单元的数目,通常远远小于n。该算法的缺点:由于STING采用了一个多分辨率的方法进行聚类分析,STING聚类的质量取决于网格结构的最低层的粒度。如果粒度比较细,处理的代价会显著增加;但是,如果网格结构最低层的力度太粗,将会降低聚类分析的质量;而且,STING在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系,因此,结果簇的形状是isothetic,即所有的聚类边界或者是水平的,或者是竖直的,没有对角的边界。尽管该技术有快速的处理速度,但可能降低簇的质量和精确性。 7 s% B2 k8 _% w# G# ]0 @ * K( Q1 m) B7 ^' n8 n. u2. WaveCluster算法6 Z" r8 u; F* C2 ^- V
9 H; V! g8 B- `, [
WaveCluster(Clustering with Wavelets)采用小波变换聚类,它是一种多分辨率的聚类算法,它首先通过在数据空间上加一个多维网格结构来汇总数据,然后采用一种小波变换来变换原特征空间,在变换后的空间中找到密集区域。 ! W' ?: W a% d/ w7 x/ X: ]' m8 O' V2 ~. y5 g$ B
WaveCluster的计算复杂度是O(n),能有效地处理大数据集合;发现任意形状的簇;成功地处理孤立点;对于输入的顺序不敏感;不要求指定诸如结果簇的数目或邻域的半径等输入参数;在实验分析中,WaveCluster在效率和聚类质量上优于BIRCH,CLARANS和DBSCAN;实验分析也发现WaveCluster能够处理多达20维的数据。但是,对数学建模的知识要求较高[33]。8 v: l I O3 _5 F y
+ ]0 a5 }3 D" U
3. CLIQUE算法 g0 j7 E6 {/ c M$ x; [7 l9 N2 }
, z0 y2 y1 g3 R$ |% m
CLIQUE(Clustering In QUEst)算法综合了基于密度和基于网格的聚类方法,它的中心思想是:首先,给定一个多维数据点的集合,数据点在数据空间中通常不是均衡分布的。CLIQUE区分空间中稀疏的和“拥挤的”区域(或单元),以发现数据集合的全局分布模式。接着,如果一个单元中的包含数据点超过了某个输入模型参数,则该单元是密集的。在CLIQUE中,簇定义为相连的密集单元的最大集合。- D! o5 E& \9 ]
' i3 K! n$ w3 A, eCLIQUE算法能自动发现最高维中所存在的密集聚类;它对输入数据元组顺序不敏感;也不需要假设(数据集中存在)任何特定的数据分布;它与输入数据大小呈线性关系;并当数据维数增加时具有较好的可扩展性。但是,在追求方法简单化的同时往往就会降低聚类的准确性。 3 i# d. z! b1 c+ i6 { m$ T7 `% ~; N' N0 f' \
1.5 基于模型的方法(model-based method) # G9 v5 O4 _# B, @! E* j基于模型的方法为每个簇假定了一个模型,寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目,考虑“噪声”数据或孤立点,从而产生健壮的聚类方法。基于模型聚类方法主要有两种:统计学方法和神经网络方法。 : {# Y3 V/ \& } + W2 l' k$ C4 h. V8 L0 f, C1.统计学方法 6 S" l' X* y y, X- c7 f- `* z5 u8 f V v/ z* l) ?
机器学习中的概念聚类就是一种形式的聚类分析。给定一组无标记数据对象,它根据这些对象产生一个分类模式。与传统聚类不同,后者主要识别相似的对象;而概念聚类则更进一步,它发现每组的特征描述;其中每一组均代表一个概念或类,因此概念聚类过程主要有两个步骤:首先完成聚类;然后进行特征描述。因此它的聚类质量不再仅仅是一个对象的函数;而且还包涵了其它因素,如所获特征描述的普遍性和简单性。 * o5 U1 x* Q3 X5 L2 w9 U' ] 3 K$ J( Z) i g- v8 F2 f9 M大多概念聚类都采用了统计方法,也就是利用概率参数来帮助确定概念或聚类。每个所获得的聚类通常都是由概率描述来加以表示[34]。 & |& L( W2 s& O; X- Q: L* i. x' d( A( F( E
COBWEB是一种流行的简单增量概念聚类算法。它的输入对象用分类属性-值对来描述。它以一个分类树的形式创建层次聚类。分类树的每个节点对应一个概念,包含该概念的一个概率描述,概述被分在该节点下的对象。在分类树某个层次上的兄弟节点形成了一个划分。为了用分类树对一个对象进行分类,采用了一个部分匹配函数沿着“最佳”匹配节点的路径在树中向下移动。寻找可以分类该对象的最好节点。这个判定基于将对象临时置于每个节点,并计算结果划分的分类效用。产生最高分类效用的位置应当是对象节点一个好的选择。但如果对象不属于树中现有的任何概念,则为该对象创建一个新类。( E: Z+ U9 V" e: S! t. }( E! h: |
2 A. e9 W0 p$ H% }4 l$ u: t
CORWEB的优点在于:他不需要用户输入参数来确定分类的个数,它可以自动修正划分中类的数目。缺点是:首先,它基于这样一个假设:在每个属性上的概率分布是彼此独立的。由于属性间经常是相关的,这个假设并不总是成立。此外,聚类的概率分布表示使得更新和存储类相当昂贵。因为时间和空间复杂度不只依赖于属性的数目,而且取决于每个属性的值的数目,所以当属性有大量的取值时情况尤其严重。而且,分类树对于偏斜的输入数据不是高度平衡的,它可能导致时间和空间复杂性的剧烈变化。8 N6 ^1 q+ z; G8 }; b3 F
% o z' Y* _. S+ f, t; v( C
2.神经网络方法% f# D$ S( l1 o) B+ r) A
7 ^$ t7 d6 y& y7 E; [. _* N1 h# A
神经网络聚类方法是将每个簇描述成一个标本。标本作为聚类的一个“原型”;它不一定对应一个特定的数据实例或对象。可以根据新对象与哪个标本最相似(基于某种距离计算方法)而将它分派到相应的聚类中。可以通过聚类的标本来预测分派到该聚类的一个对象的属性。上一章对此已经作了详细描述,这里不再详述。: r+ X' K; z! \( s0 P