基于網(wǎng)格的多密度聚類算法

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