数学建模社区-数学中国
标题:
网格聚类算法
[打印本页]
作者:
浅夏110
时间:
2018-10-31 11:15
标题:
网格聚类算法
在本文中，主要学习一下STING聚类算法。
$ J" t! I, R, M( S6 H2 \# m. W" G
% y# p) e, z* m H7 G
（1） STING：统计信息网格
9 M+ C8 W1 d% {. f& r
* K+ Y6 z1 L" i( }2 T
STING是一种基于网格的多分辨率的聚类技术，它将输入对象的空间区域划分成矩形单元，空间可以用分层和递归方法进行划分。这种多层矩形单元对应不同的分辨率，并且形成了一个层次结构：每个高层单元被划分成低一层的单元。关于每个网格单元的属性的统计信息（如均值，最大值和最小值）被作为统计参数预先计算和存储。对于查询处理和其他数据分析任务，这些统计参数是有效的。
* ^1 k) t7 ]5 R: n0 {' N
M' \8 \/ g/ D: r3 M4 C, B
STING算法：
4 Q( S" a- @( v8 O9 i3 O) L
' r8 B8 A1 o3 ?* d; J! o6 |
（1） 针对不同的分辨率，通常有多个级别的矩形单元。
8 z& F8 S( G S* s8 p/ f
/ R# [3 G6 k, Q7 l# \+ Y
（2） 这些单元形成了一个层次结构，高层的每个单元被划分成多个底一层的单元。
( F$ D' @& i: u1 c2 C1 \
$ ?. M8 {, e+ j1 l+ |/ Y
（3） 关于每个网格单元属性的统计信息（例如平均值，max,min）被预先计算和存储，这些统计信息用于回答查询。（统计信息是进行查询使用的）
$ g% B0 K3 R& V& Y |
( V4 T# M/ d; ~& `- l9 n
网格中常用的参数：
4 N; g* d7 O# Z& T8 E
2 z+ ~ j! r1 o9 U$ C1 w& v6 b5 d
（1） count 网格中对象数目
0 e) U2 u& M0 Q2 T* {3 d* a- {
! {( J* w4 z) u+ d5 b: |, R8 R
（2） mean网格中所有值的平均值
8 d/ ^! F6 }8 R
8 n4 X3 ]! Q% t' f* X. A
（3） stdev网格中属性值的标准偏差
" U5 ?$ @& R0 b C" ~
( |4 b h. C+ I: W# w
（4） min 网格中属性值的最小值
5 A% @. J, w3 a6 ^
; F4 R7 U- d3 O* D
（5） max 网格中属性值的最大值
- y1 u, k7 O& e
' m/ T: {4 _8 S
（6） distribution 网格中属性值符合的分布类型。如正态分布，均匀分布
9 ]7 H9 P( c2 j( [& K, e! ?
3 @$ y: X4 A" \5 v/ |( M
STING聚类的层次结构:
3 [) }3 Y3 g) m3 `: `
?. s" x$ F& g/ o0 V' l, x- P
通过上面两幅图，我们可以清晰的理解，STING的层次结构，上一层与下一层的关系。
; L. n3 {( J" }/ X
) ?5 S) g& r* w8 N3 K* o: n' f
注意：当数据加载到数据库时。最底层的单元参数直接由数据计算，若分布类型知道，可以用户直接指定。而较高层的单元的分布类型可以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程的合取来计算，若底层分布类型彼此不同，那么高层分布类型为none
5 d# V2 ]+ S' p6 ], c/ _
8 E' i4 z, _% l2 _ L. ~9 s
STING查询算法步骤：
5 x- x5 c/ x: U4 f6 a+ e
+ W. E+ K) v' g+ Y
（1） 从一个层次开始
( Q" j7 }+ h' |8 A
' ~5 C; e' c0 k
（2） 对于这一个层次的每个单元格，我们计算查询相关的属性值。
1 }, i, A4 X+ Y# J
2 T0 |7 \) z& Y ?1 r$ f* E+ B( s& I
（3） 从计算的属性值以及约束条件下，我们将每一个单元格标记成相关或者不想关。(不相关的单元格不再考虑，下一个较低层的处理就只检查剩余的相关单元)
$ y& b2 I) n6 C( {8 S
. [8 O3 z: @0 D& p( Y3 ~' |) }' b
（4） 如果这一层是底层，那么转（6），否则转（5）
0 `7 j! G3 n7 D9 q& P- a+ F
- R$ I2 A- P6 Y
（5） 我们由层次结构转到下一层，依照步骤2进行
4 B* s* | j4 `0 k
+ s4 r- A# U C+ Y6 v& m% X# X
（6） 查询结果得到满足，转到步骤8，否则（7）
: n* i* b3 Y5 f. P- i
/ E2 j$ @0 f* C' B
（7） 恢复数据到相关的单元格进一步处理以得到满意的结果，转到步骤（8）
* h- a9 d4 e: c! H
( c5 p5 U2 h: Y/ V/ |5 s& K" H
（8） 停止
8 f0 K* }) n. z' O' Q4 V- _
) d" w9 |/ W: e+ A/ {+ ^) p' S
到这儿，STING算法应该基本就差不多了，其核心思想就是：根据属性的相关统计信息进行划分网格，而且网格是分层次的，下一层是上一层的继续划分。在一个网格内的数据点即为一个簇。
7 F# k3 K0 l6 H9 C3 R4 Y
3 I/ F" T8 u# ^4 V8 i: t3 r
同时，STING聚类算法有一个性质：如果粒度趋向于0（即朝向非常底层的数据），则聚类结果趋向于DBSCAN聚类结果。即使用计数count和大小信息，使用STING可以近似的识别稠密的簇。
' r/ ]! Q4 M7 u7 M4 U) c
7 W! N* N/ T; k; X; H2 v8 Z
STING算法的优点：
$ h; {; O) r7 K1 Y3 L5 b+ n, L
* G0 h0 Q) I: }. x ?
（1） 基于网格的计算是独立于查询的，因为存储在每个单元的统计信息提供了单元中数据汇总信息，不依赖于查询。
* d- r1 c# S7 k5 q3 M
) |5 b, C/ W2 w5 h& {
（2） 网格结构有利于增量更新和并行处理。
" \9 K7 C8 c: e2 ?9 I( L3 J
, Y3 }) s: L7 @6 {5 {; l
（3） 效率高。STING扫描数据库一次开计算单元的统计信息，因此产生聚类的时间复杂度为O(n)，在层次结构建立之后，查询处理时间为）O(g),其中g为最底层网格单元的数目，通常远远小于n。
$ z6 m# R$ j9 z$ O7 G2 q9 [
8 o$ z2 M8 g7 f2 {3 ]2 f1 B
缺点：
) ^0 y9 `% v7 }' T4 z& v
0 [4 V3 [- `( K" s: ]. _
（1） 由于STING采用了一种多分辨率的方法来进行聚类分析，因此STING的聚类质量取决于网格结构的最底层的粒度。如果最底层的粒度很细，则处理的代价会显著增加。然而如果粒度太粗，聚类质量难以得到保证。
& M+ T( ^# n" W, @% f, \
1 @% G+ G y6 ]" p. B4 Z, a& u1 P$ n& \
（2） STING在构建一个父亲单元时没有考虑到子女单元和其他相邻单元之间的联系。所有的簇边界不是水平的，就是竖直的，没有斜的分界线。降低了聚类质量。
( w2 W* Y( R7 V0 U
d+ h# e( @( f# ]+ _6 G
# E9 O) h$ j3 f; [
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5