基于網(wǎng)格的聚類方法研究

【文章摘要】

文章分析了現(xiàn)有基于網(wǎng)格的聚類算法。使用網(wǎng)格方法的數(shù)據(jù)分析方法將空間劃分為由（超）矩形網(wǎng)格單元組成的網(wǎng)格，然后在網(wǎng)格單元上進(jìn)行聚類。最后，總結(jié)全文并提出基于網(wǎng)格的聚類需要進(jìn)一步研究的方向。

【關(guān)鍵詞】

數(shù)據(jù)挖掘；網(wǎng)格；聚類

0 引言

聚類分析是數(shù)據(jù)挖掘中廣為研究的課題之一，是從數(shù)據(jù)中尋找數(shù)據(jù)間的相似性，并依此對(duì)數(shù)據(jù)進(jìn)行分類，從而發(fā)現(xiàn)數(shù)據(jù)中隱含的有用信息或知識(shí)。

1 網(wǎng)格的定義與劃分

網(wǎng)格的基本概念，設(shè)A1，A2，…，Ar 是數(shù)據(jù)集O={O1，O2，…，On }中數(shù)據(jù)對(duì)象的r 個(gè)屬性的有界定義域，那W=A1 ×A2 ×…×Ar 就是一個(gè)r 維空間，將A1，A2，…，Ar 看成是W 的維（屬性、字段），則對(duì)于一個(gè)包含n 個(gè)數(shù)據(jù)點(diǎn)的r 維空間中的數(shù)據(jù)集O={O1，O2，…，On }，其中Oi ={Oi1，Oi2，…，Oir }（i=1，2，…，n），Oi 的第j 個(gè)分量Oij ∈Aj。將W的每一維M等分，即把W分割成個(gè)網(wǎng)格單元。

基于網(wǎng)格聚類算法的第一步是劃分網(wǎng)格結(jié)構(gòu)，按搜索子空間的策略不同，主要有基于由底向上網(wǎng)格劃分方法的算法和基于自頂向下網(wǎng)格劃分方法的算法。

1.1 由底向上的劃分方法

由底向上的網(wǎng)格劃分方法按照用戶輸入的劃分參數(shù)（即每維段數(shù)ki，1 ≤i ≤d），將數(shù)據(jù)空間均勻劃分為相等大小的網(wǎng)格單元，假設(shè)落入同一網(wǎng)格單元內(nèi)的所有數(shù)據(jù)點(diǎn)都屬于同一個(gè)簇，每個(gè)網(wǎng)格單元保存落入其內(nèi)數(shù)據(jù)的統(tǒng)計(jì)信息，比如數(shù)據(jù)點(diǎn)個(gè)數(shù)，數(shù)據(jù)點(diǎn)之和。包含一定數(shù)目數(shù)據(jù)點(diǎn)的網(wǎng)格單元被稱為高密度網(wǎng)格單元。

WaveCluster與CLIQUE是采用由底向上網(wǎng)格劃分方法的代表性算法。WaveCluster處理低維空間數(shù)據(jù)，它的性能超越了BIRCH、CLARANS，與DBSCAN等優(yōu)秀的聚類算法。CLIQUE考慮了高維子空間聚類，但它的時(shí)間復(fù)雜度較高，需要用戶指定全局密度閾值。算法MAFIA對(duì)CLIQUE進(jìn)行了改進(jìn)，為了減少聚類算法需要處理的網(wǎng)格單元數(shù)目，MAFIA將均勻劃分網(wǎng)格中每一維上數(shù)據(jù)分布密度相似的相鄰段合并，由此得到一個(gè)不均勻劃分的網(wǎng)格。這個(gè)網(wǎng)格在數(shù)據(jù)分布較均勻的區(qū)域劃分粒度大，在數(shù)據(jù)分布不均勻的區(qū)域劃分粒度小，這種不均勻劃分網(wǎng)格的方法能夠提高聚類的質(zhì)量，被后續(xù)的許多算法所采用。

采用由底向上的網(wǎng)格劃分方法的優(yōu)點(diǎn)在于，它能通過(guò)對(duì)數(shù)據(jù)的一遍掃描，將數(shù)據(jù)壓縮到一個(gè)網(wǎng)格數(shù)據(jù)結(jié)構(gòu)內(nèi)，并基于這個(gè)網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，發(fā)現(xiàn)任意形狀的簇。此外，如果網(wǎng)格單元的粒度較小（即體積較小），那么得到的聚簇的精度較高，但是算法的計(jì)算復(fù)雜度較大。此外，由底向上的網(wǎng)格方法存在不適合處理高維數(shù)據(jù)的問(wèn)題。

1.2 自頂向下的劃分方法

自頂向下的網(wǎng)格劃分方法采取分治的策略（divide and conquer principle），對(duì)數(shù)據(jù)空間進(jìn)行遞歸劃分，使問(wèn)題的規(guī)模不斷減小。首先將原數(shù)據(jù)空間劃分為幾個(gè)較大的區(qū)域。對(duì)于每個(gè)得到的區(qū)域，劃分過(guò)程反復(fù)執(zhí)行，直到每個(gè)區(qū)域包含屬于同一個(gè)簇的數(shù)據(jù)點(diǎn)，那么這些區(qū)域就是最終的網(wǎng)格單元。基于自頂向下網(wǎng)格方法的聚類算法直接將高密度網(wǎng)格單元識(shí)別為一個(gè)簇，或是將相連的高密度網(wǎng)格單元識(shí)別為簇。

OptiGrid與CLTree是兩個(gè)典型的基于自頂向下網(wǎng)格劃分方法的聚類算法。其中，OptiGrid則是用空間數(shù)據(jù)分布的密度信息來(lái)選擇最優(yōu)劃分。通過(guò)一個(gè)密度函數(shù)來(lái)決定切割平面，可以將數(shù)據(jù)空間劃分為規(guī)則的或不規(guī)則單元，與傳統(tǒng)的等間距的劃分相比，可以用此來(lái)解決高維聚類的問(wèn)題。

自頂向下劃分方法的主要優(yōu)點(diǎn)在于不需要用戶指定劃分參數(shù)，而是根據(jù)數(shù)據(jù)的分布對(duì)空間進(jìn)行劃分，因此這種劃分更為合理。數(shù)據(jù)空間維度對(duì)自頂向下網(wǎng)格方法的影響較小，可以快速將大型高維數(shù)據(jù)集中的簇分隔開。這一類方法的計(jì)算復(fù)雜度與數(shù)據(jù)集大小和維度都呈線性關(guān)系適合于處理高維數(shù)據(jù)。由于劃分是基于數(shù)據(jù)分布的，而通常認(rèn)為噪音是在整個(gè)空間均勻分布的，所以自頂向下劃分方法對(duì)噪音不敏感。但是，由于這種方法得到的網(wǎng)格單元的體積遠(yuǎn)大于由底向上網(wǎng)格方法中的網(wǎng)格單元體積，因此方法產(chǎn)生的簇的描述精度比由底向上的網(wǎng)格方法得到的簇的描述精度要低。而且在自頂向下的劃分過(guò)程中，同一個(gè)簇可能被劃分到不同的區(qū)域中，最終得到的同一區(qū)域也可能包含不同的簇，這樣就進(jìn)一步降低了算法的正確度。這類劃分方法的另一個(gè)缺點(diǎn)是它在劃分過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次掃描。

而由底向上劃分方法在于只需對(duì)數(shù)據(jù)集進(jìn)行一次線性掃描以及較高的簇的描述精度。因此，兩類方法適用于不同的問(wèn)題。前者適于處理高維數(shù)據(jù)集，后者能有效處理存取代價(jià)較大的超大型數(shù)據(jù)集與動(dòng)態(tài)數(shù)據(jù)。

2 基于網(wǎng)格的聚類過(guò)程

基于網(wǎng)格的聚類算法的基本過(guò)程是，首先將數(shù)據(jù)空間W劃分為網(wǎng)格單元，將數(shù)據(jù)對(duì)象集O 映射到網(wǎng)格單元中，并計(jì)算每個(gè)單元的密度。根據(jù)用戶輸入的密度閾值MinPts 判斷每個(gè)網(wǎng)格單元是否為高密度單元，由鄰近的稠密單元組形成簇。

2.1 網(wǎng)格單元的密度

簇就是一個(gè)區(qū)域，該區(qū)域中的點(diǎn)的密度大于與之相鄰的區(qū)域。在網(wǎng)格數(shù)據(jù)結(jié)構(gòu)中，由于每個(gè)網(wǎng)格單元都有相同的體積，因此網(wǎng)格單元中數(shù)據(jù)點(diǎn)的密度即是落到單元中的點(diǎn)的個(gè)數(shù)。據(jù)此可以得到稠密網(wǎng)格單元的密度是，設(shè)在某一時(shí)刻t一個(gè)網(wǎng)格單元的密度為density，定義density=單元內(nèi)的數(shù)據(jù)點(diǎn)數(shù)/數(shù)據(jù)空間中總的數(shù)據(jù)點(diǎn)數(shù)，設(shè)密度閾值為，為用戶輸入的密度闕值，當(dāng)density> 時(shí)，該網(wǎng)格單元是—個(gè)密集網(wǎng)格單元。

相對(duì)于稠密網(wǎng)格單元來(lái)說(shuō)，大多數(shù)的網(wǎng)格單元包含非常少甚至空的的數(shù)據(jù)，這一類網(wǎng)格單元被稱為稀疏網(wǎng)格單元。大量的稀疏網(wǎng)格單元的存在會(huì)極大的降低聚類的速度，需要在聚類之前對(duì)稀疏網(wǎng)格單元進(jìn)行處理，定義稀疏密度閾值為，當(dāng)density>時(shí)，該網(wǎng)格單元是—個(gè)稀疏單元。對(duì)于稀疏網(wǎng)格單元的處理方法一般采用壓縮的方法或者直接刪除的方法，如果需要保留稀疏網(wǎng)格單元用于后續(xù)處理，可以使用壓縮的方法；如果在現(xiàn)有數(shù)據(jù)的基礎(chǔ)之上直接聚類，可以刪除稀疏網(wǎng)格單元，理論分析和實(shí)驗(yàn)證明刪除稀疏網(wǎng)格單元并不影響聚類的質(zhì)量。

2.2 由稠密網(wǎng)格單元形成簇

在基于網(wǎng)格的聚類算法中，根據(jù)以上分析，由鄰接的稠密單元形成簇是相對(duì)直截了當(dāng)?shù)模@也是基于網(wǎng)格的方法的優(yōu)點(diǎn)之一。但是需要首先定義鄰接單元的含義。設(shè)n維空問(wèn)中的存在任意兩個(gè)網(wǎng)格單元U1和U2，當(dāng)這兩個(gè)網(wǎng)格單元在—個(gè)維上有交集或是具有一個(gè)公共面時(shí)，稱它們?yōu)猷徑泳W(wǎng)格單元。

在二維空間中，比較常使用的是4-connection相鄰定義和8-connection相鄰定義，4-connection更適合在聚類算法中使用。因?yàn)楫?dāng)尋找某個(gè)網(wǎng)格單元的鄰居時(shí)，在4-connection定義下，一個(gè)網(wǎng)格單元只有2d個(gè)鄰居，而在8-connection定義下，有3d-1個(gè)鄰居，當(dāng)數(shù)據(jù)維度d較大時(shí)，這個(gè)數(shù)目非常大。使用4-connection不僅參與計(jì)算的單元數(shù)目大為減少，而且單元增加與維數(shù)的關(guān)系由指數(shù)增長(zhǎng)變?yōu)榫€性增長(zhǎng)，所以能進(jìn)一步減少算法運(yùn)行所需的時(shí)間，具有較低的計(jì)算復(fù)雜度。

3 結(jié)論

基于網(wǎng)格的聚類方法目前還存在一些急需解決的問(wèn)題，主要有以下幾點(diǎn)：（1）當(dāng)簇具有不同的密度時(shí)，全局的密度參數(shù)不能有效發(fā)現(xiàn)這樣的簇，需要開發(fā)具有可變密度參數(shù)的算法。（2）對(duì)于不同類型數(shù)據(jù)的聚類問(wèn)題。（3）當(dāng)數(shù)據(jù)集的規(guī)模巨大以及數(shù)據(jù)具有地理分布特性時(shí)，需要開發(fā)有效的并行算法來(lái)提高處理的速度。（4）對(duì)現(xiàn)有網(wǎng)格算法的優(yōu)化，從不同方面提高網(wǎng)格算法的有效性。

【參考文獻(xiàn)】

孫玉芬.基于網(wǎng)格方法的聚類算法研究[J].華中科技大學(xué).2006.

【作者簡(jiǎn)介】

王運(yùn)強(qiáng)（1987—），男，遼寧省沈陽(yáng)人，同濟(jì)大學(xué)軟件學(xué)院碩士研究生。