提出了一種多密度網(wǎng)格聚類(lèi)算法GDD。該算法主要采用密度閾值遞減的多階段聚類(lèi)技術(shù)提取不同密
度的聚類(lèi)，使用邊界點(diǎn)處理技術(shù)提高聚類(lèi)精度，同時(shí)對(duì)聚類(lèi)結(jié)果進(jìn)行了人工干預(yù)。GDD 算法只要求
對(duì)數(shù)據(jù)集進(jìn)行一遍掃描。實(shí)驗(yàn)表明，該算法可擴(kuò)展性好，能處理任意形狀和大小的聚類(lèi)，能夠很好
的識(shí)別出孤立點(diǎn)或噪聲，在處理多密度聚類(lèi)方面有很好的精度。
關(guān)鍵詞：密度閾值遞減；多階段聚類(lèi)；邊界點(diǎn)提取
聚類(lèi)是數(shù)據(jù)挖掘中的一種重要技術(shù)，它的目標(biāo)是將數(shù)據(jù)集分成若干個(gè)子集，同一個(gè)子集
中的對(duì)象是相似的，不同子集中的對(duì)象不相似。在幾何方面，聚類(lèi)是在整個(gè)數(shù)據(jù)集中確定由
稀疏區(qū)域分開(kāi)的密集區(qū)域。由于其無(wú)指導(dǎo)學(xué)習(xí)能力，聚類(lèi)算法能在數(shù)據(jù)集中發(fā)現(xiàn)隱藏的數(shù)據(jù)模式，所以對(duì)聚類(lèi)算法的研究一直很活躍?；谙嗨菩砸呀?jīng)有很多聚類(lèi)算法，這些聚類(lèi)算法大體上可分為基于劃分的聚類(lèi)算法、基于密度的聚類(lèi)算法、基于層次的聚類(lèi)算法和基于網(wǎng)格的聚類(lèi)算法等。其中基于網(wǎng)格的聚類(lèi)算法由于只考慮網(wǎng)格單元而不是考慮每個(gè)點(diǎn)，它的計(jì)算效率比較高?；诰W(wǎng)格的聚類(lèi)算法認(rèn)為：當(dāng)網(wǎng)格劃分的比較細(xì)時(shí)，每個(gè)網(wǎng)格內(nèi)的點(diǎn)可看作是相似的。但是對(duì)多密度的數(shù)據(jù)集，這些算法很難得到滿(mǎn)意的聚類(lèi)結(jié)果。本文的主要目的就是利用網(wǎng)格技術(shù)解決對(duì)多密度數(shù)據(jù)集的聚類(lèi)。
聚類(lèi)分析所使用的數(shù)據(jù)集中，各個(gè)類(lèi)的密集往往不盡相同，甚至差別很大。大多數(shù)現(xiàn)有
的聚類(lèi)算法都是致力于如何發(fā)現(xiàn)任意形狀和大小的類(lèi)，但很難有效的處理密度差別較大的數(shù)據(jù)集。能夠處理多密度數(shù)據(jù)集的聚類(lèi)算法有Chameleon[1]、共享近鄰S(chǎng)NN 算法[2]、多階段等密度線(xiàn)算法[3]等。
Chameleon 算法可以用來(lái)處理多密度的數(shù)據(jù)集，但當(dāng)數(shù)據(jù)集較大時(shí)其算法的時(shí)間復(fù)雜度
太高。共享近鄰S(chǎng)NN 算法的主要思想是：對(duì)于數(shù)據(jù)集中每個(gè)點(diǎn)，找出距離其最近的K 個(gè)鄰近點(diǎn)，形成一個(gè)集合。然后考慮數(shù)據(jù)集中的任意兩個(gè)點(diǎn)，若對(duì)應(yīng)于這兩個(gè)點(diǎn)的K 個(gè)鄰近點(diǎn)集合交集部分的點(diǎn)數(shù)超過(guò)一個(gè)閾值，則將這兩個(gè)點(diǎn)歸于一類(lèi)。SNN 算法的優(yōu)點(diǎn)是可以對(duì)不同密度和形狀的數(shù)據(jù)集進(jìn)行聚類(lèi)，缺點(diǎn)是在多密度聚類(lèi)和處理孤立點(diǎn)或噪聲方面精度都不高（見(jiàn)圖1(a)和圖2(a)）。多階段等密度線(xiàn)算法采用多階段的方式，利用等密度線(xiàn)的思想對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)，它的缺點(diǎn)是不能有效地分離出多個(gè)類(lèi)。文獻(xiàn)[2]給出了SNN 算法和一些現(xiàn)有的聚類(lèi)算法的比較結(jié)果，結(jié)果表明SNN 算法表現(xiàn)出了較好的性能。本文只給出GDD 算法和SNN 算法聚類(lèi)結(jié)果的比較，從比較結(jié)果可以看出GDD 算法在多密度聚類(lèi)、孤立點(diǎn)或噪聲處理方面顯示出了很高的精度。
現(xiàn)有的聚類(lèi)算法大都忽視了聚類(lèi)過(guò)程中的人工參與，很難在聚類(lèi)過(guò)程中充分利用專(zhuān)家
關(guān)于領(lǐng)域的知識(shí)指導(dǎo)聚類(lèi)過(guò)程，所以得不到滿(mǎn)意的聚類(lèi)結(jié)果。在GDD 算法中，對(duì)聚類(lèi)結(jié)果就進(jìn)行了人工干預(yù)。