利用遺傳思想進行數(shù)據(jù)劃分的DBSCAN算法研究.pdf

1、數(shù)據(jù)挖掘是從海量的數(shù)據(jù)中挖掘出隱含的、先前未知的、對決策有潛在價值的知識和規(guī)則。聚類分析是數(shù)據(jù)挖掘領域中的一個重要研究課題。所謂聚類是將物理或抽象的集合分組成為類似的對象組成的多個類的過程。由聚類所生成的類是一組數(shù)據(jù)對象的集合，這些對象與同一個類中的對象彼此相似，與其它類中的對象相異。在許多應用中，可將一個類中的數(shù)據(jù)對象作為一個整體處理。當分析一個較大的、復雜的、連續(xù)的、有許多變量的數(shù)據(jù)庫和完全未知的結構時，聚類是一個非常有用的工具。

2、 目前，聚類分析算法大體上分為劃分的方法，層次的方法，基于密度的方法，基于網(wǎng)格的方法和基于模型的方法。DBSCAN算法是一種典型的基于密度的方法，該算法的優(yōu)點是可以發(fā)現(xiàn)任意形狀的聚類，且聚類結果受噪音點影響小。但是該算法存在如下缺點：當數(shù)據(jù)量過大時，算法對主存的要求較高；算法中需使用到全局變量Eps和MinPts，若變量取值不當，會影響聚類質量；當數(shù)據(jù)分布不均勻時，采用全局統(tǒng)一的變量，會降低聚類質量。 針對DBSCAN算法

3、的缺點，本文提出了一種利用遺傳思想進行數(shù)據(jù)劃分的DBSCAN算法(Data Partition DBSCAN using Genetic Algorithm, DPDGA)。DPDGA算法采用基于遺傳算法的方法確定聚類中心。這種基于遺傳算法的初始聚類中心獲取方法采用了K-means算法的基本思想，但是它使用遺傳算法而不是一般的迭代來進行逐步的優(yōu)化?；谶z傳算法的聚類中心獲取方法的優(yōu)點是不需要關于待分類數(shù)據(jù)的先驗分布知識。實驗證明，基于遺

4、傳算法的聚類中心選擇方法所取得的聚類中心接近真實的聚類中心。 在使用基于遺傳算法的方法獲得較優(yōu)的初始聚類中心后，DPDGA算法根據(jù)獲得的初始聚類中心點劃分數(shù)據(jù)集。對于劃分得到的各個局部數(shù)據(jù)集，分別計算每個局部數(shù)據(jù)集的參數(shù)MinPts，然后對各個局部數(shù)據(jù)集分別使用DBSCAN算法進行聚類，最后合并各局部數(shù)據(jù)集的聚類結果。 DPDGA算法由于劃分了數(shù)據(jù)集，降低了對主存的要求。算法中提出了計算各局部數(shù)據(jù)集參數(shù)的方法，對于分布不