基于Voronoi的平面數(shù)據(jù)的聚類分析.pdf

1、聚類是數(shù)據(jù)挖掘中用來發(fā)現(xiàn)數(shù)據(jù)分布和隱含模式的一項(xiàng)重要技術(shù)。論文首先總結(jié)了數(shù)據(jù)挖掘中的聚類算法,并著重分析了幾種經(jīng)典的聚類算法:KMeans、DBSCAN、CLIQUE,分析了它們的各自的優(yōu)缺點(diǎn)及算法的各種改進(jìn)措施。
　　論文接著簡要介紹了Voronoi圖。作為計(jì)算幾何中的一個(gè)重要分支,Voronoi具有很多優(yōu)良的特性,特別是它的最近鄰特性,因此它在諸多領(lǐng)域都有應(yīng)用。而它的這個(gè)特性,與基于原型的聚類算法有著理論上的相似性,因此利用V

2、oronoi圖進(jìn)行聚類是可行的。論文簡要介紹了各種Voronoi圖的構(gòu)造方法,并給出了增量構(gòu)造法的一般過程。
　　為了利用Voronoi圖進(jìn)行聚類,必須構(gòu)造封閉區(qū)域的Voronoi圖。論文提出一種構(gòu)造封閉區(qū)域的Voronoi圖的方法:先在整個(gè)空間上構(gòu)造Voronoi圖,并構(gòu)造出封閉區(qū)域(一般是矩形),然后找出Voronoi圖中非封閉單元,然后循環(huán)一周求出這些非封閉單元與封閉曲線的交點(diǎn),其它的單元不發(fā)生改變,這樣就可以得到封閉區(qū)域上

3、的Voronoi圖。并可得到每個(gè)單元的頂點(diǎn)序列,還可以計(jì)算每個(gè)單元的面積。
　　在著重分析了基于密度與網(wǎng)格的聚類算法的基礎(chǔ)上,提出了基于Voronoi圖的聚類算法。算法利用Voronoi圖構(gòu)建平面上不規(guī)則的網(wǎng)格,利用Voronoi圖的最近鄰特性將不同網(wǎng)格中的點(diǎn)歸于不同的類。利用網(wǎng)格點(diǎn)密度來自動(dòng)調(diào)整最終的聚類數(shù),利用前后質(zhì)心變化來調(diào)整Voronoi母點(diǎn)的位置,最終的Voronoi單元就是聚類結(jié)果。算法能自動(dòng)確定聚類數(shù),還能自動(dòng)識別低