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

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

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

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

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