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

《基于網(wǎng)格的聚類方法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

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ù)庫或數(shù)據(jù)倉庫中提取隱含的、未知的及有應(yīng)用價(jià)值的信息或模式。它是數(shù)據(jù)庫研究中的一個(gè)很有應(yīng)用價(jià)值的領(lǐng)域，融合了數(shù)據(jù)庫、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)等多個(gè)領(lǐng)域的理論和技術(shù)［1］。聚類分析是數(shù)據(jù)挖掘中廣為研宄的課

2、題之一，是從數(shù)據(jù)中尋找數(shù)據(jù)間的相似性，并依此對(duì)數(shù)據(jù)進(jìn)行分類，從而發(fā)現(xiàn)數(shù)據(jù)中隱含的有用信息或知識(shí)。目前己經(jīng)提出了不少數(shù)據(jù)聚類算法，其中比較著名的有CLARANS［2］、BIRCH［3DBSCAN［4］和CLIQUE［5］等。但對(duì)于高維、大規(guī)模數(shù)據(jù)庫的高效聚類分析仍然是一個(gè)有待研宄的開放問題。網(wǎng)格方法是空間數(shù)據(jù)處理中常用的將空間數(shù)據(jù)離散化的方法?；诰W(wǎng)格的聚類算法由于易于增量實(shí)現(xiàn)和進(jìn)行高維數(shù)據(jù)處理而被廣泛應(yīng)用于聚類算法中。研宄人員已經(jīng)提出了很多基于網(wǎng)格的聚類算法，包括STING[6]，它利用了存儲(chǔ)在網(wǎng)格單元中的統(tǒng)計(jì)信

3、息;WaveCluster[7]它用一種小波轉(zhuǎn)換方法來聚類數(shù)據(jù)對(duì)象;CLIQUE在高維數(shù)據(jù)空間中基于網(wǎng)格和密度的聚類方法等。本文對(duì)己有的基于網(wǎng)格的聚類算法進(jìn)行了研究，從網(wǎng)格的表示，劃分網(wǎng)格單元的方法，到統(tǒng)計(jì)網(wǎng)格內(nèi)信息，搜索近鄰網(wǎng)格單元，聚類超過指定闕值的網(wǎng)格單元的各個(gè)步驟進(jìn)行了分析，最后對(duì)基于網(wǎng)格方法聚類的研究方向做了展望。2網(wǎng)格的定義與劃分網(wǎng)格的基本概念，設(shè)Al，A2,…，Ar是數(shù)據(jù)集0={01,02，…，On}中數(shù)據(jù)對(duì)象的r個(gè)屬性的有界定義域，那W=A1XA2X-XAr就是一個(gè)r維空間，將Al,A2,…,Ar

4、看成是W的維（屬性、字段），則對(duì)于一個(gè)包含n個(gè)數(shù)據(jù)點(diǎn)的r維空間中的數(shù)據(jù)集0={01,02，…，On},其中0i={0il，0i2，…，Oir}（i=l，2,…，n），0i的第j個(gè)分量OijGAj。將W的每一維M等分，即把W分割成個(gè)網(wǎng)格單元?；诰W(wǎng)格聚類算法的第一步是劃分網(wǎng)格結(jié)構(gòu)，按搜索子空間的策略不同，主要有基于由底向上網(wǎng)格劃分方法的算法和基于自頂向下網(wǎng)格劃分方法的算法。由底向上的劃分方法由底向上的網(wǎng)格劃分方法按照用戶輸入的劃分參數(shù)（即每維段數(shù)ki,l

5、一網(wǎng)格單元內(nèi)的所有數(shù)據(jù)點(diǎn)都屬于同一個(gè)簇，每個(gè)網(wǎng)格單元保存落入其內(nèi)數(shù)據(jù)的統(tǒng)計(jì)信息，比如數(shù)據(jù)點(diǎn)個(gè):據(jù)點(diǎn)之和。包含一定數(shù)目數(shù)據(jù)點(diǎn)的網(wǎng)格單元被稱為高密度網(wǎng)格單元。WaveCluster與CLIQUE是采用由底向上網(wǎng)格劃分方法的代表性算法。WaveCluster處理低維空間數(shù)據(jù)，它的性能超越了BIRCH、CLARANS，與DBSCAN等優(yōu)秀的聚類算法[15]CLIQUE考慮了高維子空間聚類，但它的時(shí)間復(fù)雜度較高，需要用戶指定全局密度閾值。算法MAF1A[8]對(duì)CLIQUE進(jìn)行了改進(jìn)，為了減少聚類算法需要處理的網(wǎng)格單元數(shù)目，

6、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)在于，它能通過對(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)格單元的粒度較?。大w積較?。敲吹玫降木鄞氐木容^高但是算法的計(jì)算復(fù)雜度較大。此外，由底向上的網(wǎng)格方法存在不適合處理高維數(shù)據(jù)的

7、問題。在高維空間，數(shù)據(jù)的分布是非常稀疏的，網(wǎng)格方法失去其壓縮作用，而且屬于同一個(gè)簇的高密度網(wǎng)格單元也可能不相連，這使聚類算法不能發(fā)現(xiàn)合理數(shù)目的簇。自頂向下的劃分方法自頂向下的網(wǎng)格劃分方法采取分治的策略(divideandconquerprincipie)，對(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(wǎng)格方法的聚類算法直接將高密度網(wǎng)格單元識(shí)別為一個(gè)簇，或是將

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