基于DBSCAN的自適應(yīng)非均勻密度聚類算法研究.pdf

1、隨著信息技術(shù)的高速發(fā)展，數(shù)據(jù)的規(guī)模呈現(xiàn)爆炸式增長。從錯綜復(fù)雜的數(shù)據(jù)中挖掘出有價值的信息具有巨大的實際意義。聚類算法作為數(shù)據(jù)挖掘領(lǐng)域中的一類重要方法，被廣泛應(yīng)用于數(shù)據(jù)分析與挖掘中。DBSCAN算法是一種典型的聚類算法，以數(shù)據(jù)密度為度量，可以識別數(shù)據(jù)集中任意形狀的類及噪音點。本論文以DBSCAN算法為研究對象，針對其對數(shù)據(jù)參數(shù)Eps和MinPts敏感、在處理非均勻密度數(shù)據(jù)集時效果不理想等問題進行研究，提出了改進方法，并給出了一種適合于大規(guī)模

2、數(shù)據(jù)的聚類方法。
　　論文的研究工作得到了國家自然科學(xué)基金項目(No.61172072、61271308)、北京市自然科學(xué)基金項目(No.4112045)和高等學(xué)校博士學(xué)科點專項科研基金(No.20100009110002)的支持。論文的主要工作如下:
　　首先，為了提高DBSCAN算法對非均勻密度數(shù)據(jù)集聚類的準確性，本文提出了自適應(yīng)的非均勻密度聚類算法(Adaptive Varied-Density-Based Spati

3、al Clustering of Applications with Noise，AV-DBSCAN)。該算法改變了DBSCAN算法的鄰域及類的定義，將DBSCAN算法中的Eps-鄰域改為MinPts-鄰域;并通過M-近鄰有向圖間接得到全局密度參數(shù)Eps和MinPts的值，減少了人為選擇密度參數(shù)的困難。算法將一個類定義為類核心集與類邊界集的組合。在聚類中引入有向圖的最大連通分量思想，用以識別數(shù)據(jù)集中的類核心集;再利用有向圖的弱連通性識別

4、剩余數(shù)據(jù)集中的類邊界集。與DBSCAN算法相比，該算法在保持相同時間復(fù)雜度的前提下，不僅提高了對非均勻密度數(shù)據(jù)聚類的準確性，也降低了對密度參數(shù)的敏感性。
　　然后，為了適應(yīng)當今數(shù)據(jù)集規(guī)模不斷加大，本文提出了基于平衡迭代歸約的自適應(yīng)非均勻密度聚類算法(Balanced Iterative Reducing-Adaptive Varied-Density-Based Spatial Clustering of Applications

5、 with Noise,BIRAV-DBSCAN)。該算法綜合了BIRCH算法簡單高效與AV-DBSCAN算法準確性高的優(yōu)勢。它可以利用有限的內(nèi)存資源及較少I/O消耗，以較小的誤差對大規(guī)模的非均勻密度數(shù)據(jù)集進行高效率聚類，并且可以識別數(shù)據(jù)集中任意形狀的類和異常點。由于該算法擴展性較好，如果將該算法與并行化技術(shù)結(jié)合可以增大對大規(guī)模數(shù)據(jù)集的處理能力。
　　最后，為了評估AV-DBSCAN和BIRAV-DBSCAN算法的有效性及可靠性，