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

1、基于網(wǎng)格的聚類方法研究摘要:已有的聚類算法對(duì)于發(fā)現(xiàn)任意形狀的聚類和處理離群點(diǎn)效果不理想,分析了現(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)格;聚類1引言數(shù)據(jù)挖掘是指從大型數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)中提取隱含的、未知的及有應(yīng)用價(jià)值的信息或形式。它是數(shù)據(jù)庫(kù)研究中的一個(gè)很有應(yīng)用價(jià)值的領(lǐng)域,交融了數(shù)據(jù)庫(kù)、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)等多個(gè)領(lǐng)域的理論和技術(shù)1。聚類分析是數(shù)據(jù)挖掘中廣為研究的課題之一,是從數(shù)據(jù)中尋找數(shù)據(jù)間的相似性,并依此對(duì)數(shù)據(jù)進(jìn)展分類,從而發(fā)現(xiàn)數(shù)據(jù)中隱含的有用信

2、息或知識(shí)。目前已經(jīng)提出了不少數(shù)據(jù)聚類算法,其中比擬著名的有l(wèi)arans2、birh3、dbsan4和lique5等。但對(duì)于高維、大規(guī)模數(shù)據(jù)庫(kù)的高效聚類分析仍然是一個(gè)有待研究的開放問題。網(wǎng)格方法是空間數(shù)據(jù)處理中常用的將空間數(shù)據(jù)離散化的方法。基于網(wǎng)格的聚類算法由于易于增量實(shí)現(xiàn)和進(jìn)展高維數(shù)據(jù)處理而被廣泛應(yīng)用于聚類算法中。研究人員已經(jīng)提出了很多基于網(wǎng)格的聚類算法,包括sting6,它利用了存儲(chǔ)在網(wǎng)格單元中的統(tǒng)計(jì)信息;aveluster7它用一種小波轉(zhuǎn)換方法來聚類數(shù)據(jù)對(duì)象;lique在高維數(shù)據(jù)空間中基于網(wǎng)格和密度的聚類方法等。本文對(duì)已有的基于網(wǎng)格的聚類算法進(jìn)展了研究,從網(wǎng)格的表示,劃分網(wǎng)格單元的方法,到

3、統(tǒng)計(jì)網(wǎng)格內(nèi)信息,搜索近鄰網(wǎng)格單元,聚類超過指定闕值的網(wǎng)格單元的各個(gè)步驟進(jìn)展了分析,最后對(duì)基于網(wǎng)格方法聚類的研究方向做了展望。2網(wǎng)格的定義與劃分網(wǎng)格的根本概念,設(shè)a1,a2,ar是數(shù)據(jù)集=1,2,n中數(shù)據(jù)對(duì)象的r個(gè)屬性的有界定義域,那=a1a2ar就是一個(gè)r維空間,將a1,a2,ar看成是的維(屬性、字段),那么對(duì)于一個(gè)包含n個(gè)數(shù)據(jù)點(diǎn)的r維空間中的數(shù)據(jù)集=1,2,n,其中i=i1,i2,ir(i=1,2,n),i的第j個(gè)分量ijaj。將的每一維等分,即把分割成個(gè)網(wǎng)格單元。基于網(wǎng)格聚類算法的第一步是劃分網(wǎng)格構(gòu)造,按搜索子空間的策略不同,主要有基于由底向上網(wǎng)格劃分方法的算法和基于自頂向下網(wǎng)格劃分方法

4、的算法。2.1由底向上的劃分方法由底向上的網(wǎng)格劃分方法按照用戶輸入的劃分參數(shù)(即每維段數(shù)ki,1id),將數(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)格單元。aveluster與lique是采用由底向上網(wǎng)格劃分方法的代表性算法。aveluster處理低維空間數(shù)據(jù),它的性能超越了birh、larans,與dbsan等優(yōu)秀的聚類算法15。lique考慮了高維子空間聚類,但它的時(shí)間復(fù)雜度較高,需要用戶指定全局密度閾值。算法afia8對(duì)lique進(jìn)展

5、了改良,為了減少聚類算法需要處理的網(wǎng)格單元數(shù)目,afia將均勻劃分網(wǎng)格中每一維上數(shù)據(jù)分布密度相似的相鄰段合并,由此得到一個(gè)不均勻劃分的網(wǎng)格。這個(gè)網(wǎng)格在數(shù)據(jù)分布較均勻的區(qū)域劃分粒度大,在數(shù)據(jù)分布不均勻的區(qū)域劃分粒度小,這種不均勻劃分網(wǎng)格的方法可以進(jìn)步聚類的質(zhì)量,被后續(xù)的許多算法所采用。采用由底向上的網(wǎng)格劃分方法的優(yōu)點(diǎn)在于,它能通過對(duì)數(shù)據(jù)的一遍掃描,將數(shù)據(jù)壓縮到一個(gè)網(wǎng)格數(shù)據(jù)構(gòu)造內(nèi),并基于這個(gè)網(wǎng)格數(shù)據(jù)構(gòu)造,發(fā)現(xiàn)任意形狀的簇。此外,假如網(wǎng)格單元的粒度較小(即體積較小),那么得到的聚簇的精度較高,但是算法的計(jì)算復(fù)雜度較大。此外,由底向上的網(wǎng)格方法存在不合適處理高維數(shù)據(jù)的問題。在高維空間,數(shù)據(jù)的分布是非常

6、稀疏的,網(wǎng)格方法失去其壓縮作用,而且屬于同一個(gè)簇的高密度網(wǎng)格單元也可能不相連,這使聚類算法不能發(fā)現(xiàn)合理數(shù)目的簇。2.2自頂向下的劃分方法自頂向下的網(wǎng)格劃分方法采取分治的策略(divideandnquerpriniple),對(duì)數(shù)據(jù)空間進(jìn)展遞歸劃分,使問題的規(guī)模不斷減校首先將原數(shù)據(jù)空間劃分為幾個(gè)較大的區(qū)域。對(duì)于每個(gè)得到的區(qū)域,劃分過程反復(fù)執(zhí)行,直到每個(gè)區(qū)域包含屬于同一個(gè)簇的數(shù)據(jù)點(diǎn),那么這些區(qū)域就是最終的網(wǎng)格單元。基于自頂向下網(wǎng)格方法的聚類算法直接將高密度網(wǎng)格單元識(shí)別為一個(gè)簇,或是將相連的高密度網(wǎng)格單元識(shí)別為簇。ptigrid9與ltree10是兩個(gè)典型的基于自頂向下網(wǎng)格劃分方法的聚類算法。其中,p

7、tigrid那么是用空間數(shù)據(jù)分布的密度信息來選擇最優(yōu)劃分。通過一個(gè)密度函數(shù)來決定切割平面,可以將數(shù)據(jù)空間劃分為規(guī)那么的或不規(guī)那么單元,與傳統(tǒng)的等間距的劃分相比,可以用此來解決高維聚類的問題。而ltree用劃分后的信息增益來選取最優(yōu)劃分。自頂向下劃分方法的主要優(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ì)噪音不敏感。但是

8、,由于這種方法得到的網(wǎng)格單元的體積遠(yuǎn)大于由底向上網(wǎng)格方法中的網(wǎng)格單元體積,因此方法產(chǎn)生的簇的描繪精度比由底向上的網(wǎng)格方法得到的簇的描繪精度要低。而且在自頂向下的劃分過程中,同一個(gè)簇可能被劃分到不同的區(qū)域中,最終得到的同一區(qū)域也可能包含不同的簇,這樣就進(jìn)一步降低了算法的正確度。這類劃分方法的另一個(gè)缺點(diǎn)是它在劃分過程中,需要對(duì)數(shù)據(jù)集進(jìn)展屢次掃描。而由底向上劃分方法在于只需對(duì)數(shù)據(jù)集進(jìn)展一次線性掃描以及較高的簇的描繪精度。因此,兩類方法適用于不同的問題。前者適于處理高維數(shù)據(jù)集,后者能有效處理存取代價(jià)較大的超大型數(shù)據(jù)集與動(dòng)態(tài)數(shù)據(jù)。3基于網(wǎng)格的聚類過程基于網(wǎng)格的聚類算法的根本過程是,首先將數(shù)據(jù)空間劃分為網(wǎng)

9、格單元,將數(shù)據(jù)對(duì)象集映射到網(wǎng)格單元中,并計(jì)算每個(gè)單元的密度。根據(jù)用戶輸入的密度閾值inpts判斷每個(gè)網(wǎng)格單元是否為高密度單元,由鄰近的稠密單元組形成簇11,如表1。算法1中的步驟1已經(jīng)在上文詳細(xì)說明,下面詳細(xì)介紹步驟2-4的內(nèi)容。3.1網(wǎng)格單元的密度簇就是一個(gè)區(qū)域,該區(qū)域中的點(diǎn)的密度大于與之相鄰的區(qū)域。在網(wǎng)格數(shù)據(jù)構(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)densi

10、ty時(shí),該網(wǎng)格單元是個(gè)密集網(wǎng)格單元。相對(duì)于稠密網(wǎng)格單元來說,大多數(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ù)的根底之上直接聚類,可以刪除稀疏網(wǎng)格單元,理論分析和實(shí)驗(yàn)證明刪除稀疏網(wǎng)格單元并不影響聚類的質(zhì)量12。3.2由稠密網(wǎng)格單元形成簇在基于網(wǎng)格的聚類算法中,根據(jù)以上分析,由鄰接的稠密單

11、元形成簇是相對(duì)直截了當(dāng)?shù)?這也是基于網(wǎng)格的方法的優(yōu)點(diǎn)之一。但是需要首先定義鄰接單元的含義。設(shè)n維空問中的存在任意兩個(gè)網(wǎng)格單元u1和u2,當(dāng)這兩個(gè)網(wǎng)格單元在個(gè)維上有交集或是具有一個(gè)公共面時(shí),稱它們?yōu)猷徑泳W(wǎng)格單元。在二維空間中,比擬常使用的是4-nnetin相鄰定義和8-nnetin相鄰定義(如圖1),4-nnetin更合適在聚類算法中使用。因?yàn)楫?dāng)尋找某個(gè)網(wǎng)格單元的鄰居時(shí),在4-nnetin定義下,一個(gè)網(wǎng)格單元只有2d個(gè)鄰居,而在8-nnetin定義下,有3d-1個(gè)鄰居,當(dāng)數(shù)據(jù)維度d較大時(shí),這個(gè)數(shù)目非常大。使用4-nnetin不僅參與計(jì)算的單元數(shù)目大為減少,而且單元增加與維數(shù)的關(guān)系由指數(shù)增長(zhǎng)變?yōu)榫€

12、性增長(zhǎng),所以能進(jìn)一步減少算法運(yùn)行所需的時(shí)間,具有較低的計(jì)算復(fù)雜度13。其外,只有在非常特殊的情況下,使用4-nnetin定義得到的聚類結(jié)果才會(huì)與使用8-nnetin定義得到的聚類結(jié)果不同14,這是因?yàn)?當(dāng)4-nnetin的網(wǎng)格單元是高密度網(wǎng)格單元時(shí),四個(gè)對(duì)角線上的網(wǎng)格單元不管是否是高密度網(wǎng)格單元,都能被正確的聚類;只有當(dāng)與對(duì)角線上的網(wǎng)格單元相鄰的2個(gè)網(wǎng)格單元同時(shí)為空且該單元本身是高密度網(wǎng)格單元時(shí),不能正確聚類,在劃分網(wǎng)格時(shí),通常都要求網(wǎng)格單元的大小遠(yuǎn)小于簇的大小,因此可以認(rèn)為這種情況出現(xiàn)的可能很校4結(jié)論及展望基于網(wǎng)格聚類方法的優(yōu)點(diǎn)是它的處理速度快,因?yàn)槠渌俣扰c數(shù)據(jù)對(duì)象的個(gè)數(shù)無關(guān),而只依賴于數(shù)據(jù)

13、空間中每個(gè)維上單元的個(gè)數(shù),發(fā)現(xiàn)任意形狀、任意大小的簇、計(jì)算結(jié)果與數(shù)據(jù)輸入順序無關(guān)、計(jì)算時(shí)間與數(shù)據(jù)量無關(guān),同時(shí)不要求像k均值一樣預(yù)先指定簇個(gè)數(shù)等。但是,基于網(wǎng)格方法的聚類算法的輸入?yún)?shù)對(duì)聚類結(jié)果影響較大,而且這些參數(shù)較難設(shè)置。當(dāng)數(shù)據(jù)中有噪音時(shí),假如不加特殊處理,算法的聚類質(zhì)量會(huì)很差。而且,算法對(duì)于數(shù)據(jù)維度的可伸縮性較差?；诰W(wǎng)格的聚類方法目前還存在一些急需解決的問題,主要有以下幾點(diǎn):(1)當(dāng)簇具有不同的密度時(shí),全局的密度參數(shù)不能有效發(fā)現(xiàn)這樣的簇,需要開發(fā)具有可變密度參數(shù)的算法。(2)對(duì)于不同類型數(shù)據(jù)的聚類問題,比方對(duì)于高維數(shù)據(jù),網(wǎng)格的數(shù)據(jù)將急劇增加,需要有效地技術(shù)發(fā)現(xiàn)近鄰單元。(3)當(dāng)數(shù)據(jù)集的規(guī)

14、模宏大以及數(shù)據(jù)具有地理分布特性時(shí),需要開發(fā)有效的并行算法來進(jìn)步處理的速度。(4)對(duì)現(xiàn)有網(wǎng)格算法的優(yōu)化,從不同方面進(jìn)步網(wǎng)格算法的有效性。比方開發(fā)稀疏網(wǎng)格的壓縮算法、密度相似網(wǎng)格的合并算法等。本文對(duì)基于網(wǎng)格的聚類方法的已有研究進(jìn)展了分析和總結(jié),包括網(wǎng)格的定義與劃分方法、網(wǎng)格單元密度確實(shí)定、由鄰接網(wǎng)格單元形成聚簇的聚類過程;最后對(duì)網(wǎng)格聚類方法優(yōu)點(diǎn)與局限性進(jìn)展總結(jié),在已有研究分析的根底上,提出后續(xù)需要重點(diǎn)解決的問題。參考文獻(xiàn)1hens,hanjiaei,yups.dataining:anverviefradatabaseperspetivej.ieeetransnknledgeanddataeng.1

15、996,8(6):866-883.2ngrt,hanj.effiientandeffetivelusteringethdsfrspatialdataining.prfthe20thvldbnferene.hile,santia.1994:144-155.3zhangt,raakrishnanr,livny.aneffiientdatalusteringethdfrverylargedatabases.prfasigdinternatinalnferenenanageentfdata.neyrk:apress,1996:103-114.4ester,kriegelhp,sanderj.adens

16、itybasedalgrithfrdisveringlustersinlargespatialdatabasesithnise.prfthe2ndinternatinalnferenenknledgedisveringindatabasesanddataining.regn,1996:122-128.5agraalr,gehrkej,gunplsd.autatisubspaelusteringfhighdiensinaldatafrdatainingappliatins.prfasigdinternatinalnferenenanageentfdata.neyrk:apress,1998:94

17、-105.6ang,yangj,untzr.sting:astatistialinfratingridapprahtspatialdataining.in:preedingsfthe23rdvldbnferene.athens,greee,1997.186-195.7sheikhleslaig,hatterjees,zhanga.aveluster:aulti-reslutinlusteringapprahfrverylargespatialdatabases.in:preedingsfthe24thvldbnferene.neyrk,usa,1998.428-439.8gils,nagesh

18、h,hudharya.afia:effiientandsalablesubspaelusteringfrverylargedatasets.tehnialreprtn.pd-tr-9906-010,enterfrparallelanddistributedputing,1999.9hinneburga,keida.ptialgrid-lustring:tardsbreakingtheursefdiensinalityinhigh-diensinallustering.in:preedingsfthe25thvldbnferene.1999.506-517.10liub,xiay,yups.lusteringthrughdeisintreenstrutin.in:preedingsftheninthinternatinalnfereneninfratinandknledgeanageent.2000.20-29.11pang-ningtan,ihaelste