一種基于網(wǎng)格密度的自適應(yīng)聚類分析算法

摘要：在結(jié)合基于密度和基于網(wǎng)格的聚類算法優(yōu)點(diǎn)的基礎(chǔ)上，提出一種新的聚類算法。該算法能夠在海量、高緯數(shù)據(jù)下發(fā)現(xiàn)任意形狀的聚類并對(duì)噪聲數(shù)據(jù)不敏感，具有較低的時(shí)間和空間復(fù)雜性及較高的識(shí)別率。通過實(shí)驗(yàn)對(duì)該算法進(jìn)行了性能比較和測(cè)試，顯示了它在各方面的優(yōu)越性。

關(guān)鍵詞：聚類； 密度； 網(wǎng)格； 連通性

中圖分類號(hào)：TP311.13文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2007)08－0056－02

聚類分析[1]是數(shù)據(jù)挖掘研究領(lǐng)域中一個(gè)非常活躍的研究課題，已被廣泛應(yīng)用于許多領(lǐng)域。聚類能夠在潛在的數(shù)據(jù)中發(fā)現(xiàn)令人感興趣的數(shù)據(jù)分布模式。它將數(shù)據(jù)對(duì)象的集合分組為多個(gè)類或簇；同一個(gè)簇中的對(duì)象彼此相似，而與其他簇中的對(duì)象相異。通過聚類，能夠識(shí)別出稀疏的或稠密的區(qū)域，從而發(fā)現(xiàn)全局分布模式以及數(shù)據(jù)屬性之間有趣的相互關(guān)系。

對(duì)于大規(guī)模、高維數(shù)據(jù)庫來說，其數(shù)據(jù)空間中數(shù)據(jù)的分布是不均勻的，已有的聚類算法大多不能有效地處理海量、高維數(shù)據(jù)。因此，本文結(jié)合密度算法和網(wǎng)格算法各自的優(yōu)點(diǎn)提出了一種新算法。該算法將數(shù)據(jù)空間劃分成固定大小的網(wǎng)格單元，根據(jù)網(wǎng)格密度的相似性及網(wǎng)格的連通性進(jìn)行快速有效的聚類；同時(shí)該算法也適合于空間區(qū)域查詢，在增加或刪除數(shù)據(jù)時(shí)只需要考慮這個(gè)增加或刪除的數(shù)據(jù)所影響到的相應(yīng)網(wǎng)格，并根據(jù)該網(wǎng)格與相鄰網(wǎng)格的關(guān)系來進(jìn)行聚類，具有良好的伸縮性。

1相關(guān)研究 

1．1基于密度的算法

M. Ester和M. Ankerst等人提出了基于密度的聚類算法[2，3]，該算法將具有足夠高密度的區(qū)域劃分為簇，并可以在帶有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。該算法采用一個(gè)密度閾值來控制簇的增長(zhǎng)，但是這個(gè)參數(shù)值的設(shè)置需由用戶來決定，設(shè)置的細(xì)微不同可能導(dǎo)致差別很大的聚類結(jié)果。真實(shí)的高緯數(shù)據(jù)集合經(jīng)常分布不均，全局密度參數(shù)不能反映出其內(nèi)在的聚類結(jié)構(gòu)。

1．2基于網(wǎng)格的算法

A. Rakesh等人提出了基于網(wǎng)格的聚類算法[4]，它對(duì)于大型數(shù)據(jù)庫中的高緯數(shù)據(jù)的聚類非常有效。該算法采用一個(gè)統(tǒng)一的網(wǎng)格大小來劃分問題空間，每個(gè)網(wǎng)格保存了落在其內(nèi)部的數(shù)據(jù)統(tǒng)計(jì)信息，然后在網(wǎng)格上進(jìn)行聚類操作。由于網(wǎng)格的數(shù)量遠(yuǎn)小于數(shù)據(jù)點(diǎn)的數(shù)量，其運(yùn)行時(shí)間很快。網(wǎng)格的大小決定了聚類效果，精細(xì)的網(wǎng)格可能導(dǎo)致網(wǎng)格數(shù)量的急劇增加，有時(shí)甚至超過了數(shù)據(jù)點(diǎn)的數(shù)量，這將導(dǎo)致計(jì)算時(shí)間的增加；粗糙的網(wǎng)格導(dǎo)致了聚類質(zhì)量的下降，有時(shí)甚至不能找出不同的聚類。

2基于網(wǎng)格密度的自適應(yīng)聚類算法

通過前面的分析可知，基于密度的算法能夠較好地發(fā)現(xiàn)任意形狀的聚類結(jié)果，而基于網(wǎng)格的算法則能夠較好地發(fā)現(xiàn)最高緯的子空間。綜合這兩種聚類算法的優(yōu)點(diǎn)提出了一種新的聚類算法。該算法不需要用戶指定密度閾值，具有良好的自適應(yīng)性。算法也適合于進(jìn)行動(dòng)態(tài)聚類，當(dāng)增加或刪除數(shù)據(jù)時(shí)，算法不用重新聚類，只需要考慮這個(gè)增加或刪除的數(shù)據(jù)所影響到的那部分網(wǎng)格單元并進(jìn)行處理即可。

定義8類。根據(jù)連通性，網(wǎng)格單元所能達(dá)到的最大單元集合稱為一個(gè)類。

2．2 算法實(shí)現(xiàn)

由于網(wǎng)格單元在本算法中起著關(guān)鍵性作用，先說明一下其數(shù)據(jù)結(jié)構(gòu)。每個(gè)網(wǎng)格單元包含四個(gè)方面的信息：該網(wǎng)格單元在n維空間中的位置、網(wǎng)格單元的密度、落入該網(wǎng)格單元中的點(diǎn)集、參考點(diǎn)的坐標(biāo)。為簡(jiǎn)單起見，以二維空間為例來說明一下網(wǎng)格單元的存儲(chǔ)信息，如圖3所示。

本算法分為以下三個(gè)步驟：

a)將n維空間數(shù)據(jù)對(duì)象劃分成Nn個(gè)網(wǎng)格單元，N為每一緯上劃分的區(qū)間數(shù)；然后統(tǒng)計(jì)落入每個(gè)單元中點(diǎn)的個(gè)數(shù)并得出相應(yīng)的參考點(diǎn)。

b)將這些網(wǎng)格單元按密度降序排列，以最大密度的單元為中心，分別向四個(gè)方向展開。設(shè)中心單元的密度為m，那么密度在[m/2，m]范圍內(nèi)的所有連通單元都可以劃為一類；接著對(duì)其邊界單元進(jìn)行分析處理。如果其屬于該類，則去除邊界噪聲；如果不屬于該類，就忽略掉。對(duì)于剩下的網(wǎng)格單元，也依照這個(gè)方法進(jìn)行下一個(gè)聚類，直到所有網(wǎng)格單元都處理完為止。這一步驟的實(shí)現(xiàn)偽代碼如下：

3實(shí)驗(yàn)結(jié)果及分析

4結(jié)束語

本文提出的算法是一種基于空間單元網(wǎng)格密度的聚類算法。該算法只需對(duì)數(shù)據(jù)集進(jìn)行一次掃描，得到每個(gè)網(wǎng)格單元的信息；再通過對(duì)這些網(wǎng)格單元進(jìn)行處理得到最終的聚類結(jié)果。由于生成的網(wǎng)格單元數(shù)遠(yuǎn)小于數(shù)據(jù)點(diǎn)數(shù)，算法的時(shí)間復(fù)雜度是線性的，效率很高。試驗(yàn)結(jié)果證明該方法能夠準(zhǔn)確有效地完成聚類任務(wù)，可應(yīng)用于圖像分析、空間數(shù)據(jù)聚類、商業(yè)數(shù)據(jù)聚類等多個(gè)領(lǐng)域的數(shù)據(jù)挖掘。

參考文獻(xiàn)：

［1］韓家煒，坎伯.數(shù)據(jù)挖掘:概念與技術(shù)[M].范明，等譯.北京：機(jī)械工業(yè)出版社，2001：223－262.

[2］ESTER M，KRIEGEL H P， SANDER J， et al. A densitybased algorithm for discovering clusters in large spatial databases[C]//Proc of Int Conf Knowledge Discovery and Data Mining. Newport Beach， CA:[s.n.]，1997:1015.

[3］ANKERST M， BREUNIG M M， KRIEGEL H P， et al. OPTICS: ordering points to identify the clustering structure[C]//Proc of ACM SIGMOD Int’l Conf Management of Data. Philadelphia， PA:[s.n.]，1999:49－60.

[4］RAKESH A，JOHANNERS G，DIMITRIOS G， et al. Automatic subspace clustering of high dimensional data for data mining applications[C]//Proc of ACM SIGMOD Int’l Conf on Management of Data. Minneapolis: ACM Press，1994:94105.

[5］BECKMANN N， KRIEGEL H， SCHNEIDER R， et al. The R*tree: an efficient and robust access method for points and rectangles[C]//Proc of ACM SIGMOD Int’l Conf on Management of Data.Atlantic City，NJ:[s.n.]，1990:322－331.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”