基于遺傳算法的聚類分析及其應(yīng)用

(成都理工大學(xué) 四川 成都 610059)

一、前言

(一)研究目的和意義。數(shù)據(jù)挖掘技術(shù)的目的就是為了從錯綜復(fù)雜的大數(shù)據(jù)中挖掘出有用的知識和數(shù)據(jù)，進(jìn)而應(yīng)用到科學(xué)決策中(趙艷麗，2009)。聚類分析(Clustering Method)是一類無監(jiān)督分類方法，是數(shù)據(jù)挖掘中極其關(guān)鍵的一個數(shù)據(jù)處理方式，使同一類內(nèi)里對象之間的相似程度最小，不同類內(nèi)對象之間的相似程度最大的目標(biāo)(李薈嬈，2014)。在地球化學(xué)數(shù)據(jù)的分析研究中，首要的是要研究地球化學(xué)元素的分布特征，再依據(jù)數(shù)據(jù)分類的方法找尋元素空間分布規(guī)律。

(二)國內(nèi)外研究現(xiàn)狀。k-means算法最早是由J.B.MacQueen于1967年提出來的，由于該算法不僅聚類時間快，而且聚類過程簡單，效率高，隨后該算法廣泛的開始傳播。但k-means算法也存在以下缺點:(1)聚類數(shù)據(jù)的要求很高；(2)初始聚類中心的選取不合適會導(dǎo)致聚類結(jié)果的不穩(wěn)定；(3)需要人為的去確定分類數(shù)k；許多專家對上述問題進(jìn)行了深入研究，已找出一些新的方法可以彌補k-means算法的缺陷。重點是通過以下兩個方面來改進(jìn)k-means算法。(1)傳統(tǒng)k-means算法的k值被替換為人為確定的k值；(2)初始聚類中心選擇的優(yōu)化排除了聚類初始點對聚類結(jié)果的影響。

遺傳算法最早由美國J.Holland教授在1975年提出的(劉建莊，1995)。其最顯著的特點是能夠直接對結(jié)構(gòu)對象進(jìn)行操作，并且沒有函數(shù)連續(xù)性的定義,它具有隱式并行性和全局尋優(yōu)能力。它應(yīng)用在許多問題上表現(xiàn)出簡單，通用，強大，適合并行處理等優(yōu)點，是當(dāng)前智能計算的核心技術(shù)之一。

近年來，k-means聚類分析和遺傳算法的發(fā)展十分迅猛，并且基于k-means聚類算法和遺傳算法已經(jīng)擴(kuò)展成一系列不同的算法，已被廣泛的應(yīng)用于生活。

(三)本文的主要研究內(nèi)容。k-means算法的最主要的兩個缺點是需要我們自己來確定分類數(shù)k以及初始聚類中心，因此在隨機選取聚類中心點上會很大程度上讓聚類結(jié)果接近于局部最優(yōu)值。遺傳算法最主要的特點是隱式并行性和有效利用全局信息，因此基于遺傳算法的聚類分析具有很強的魯棒性，很大程度上不會陷入局部最優(yōu)，進(jìn)而顯著的提升算法的聚類效果。本文實驗使用標(biāo)準(zhǔn)數(shù)據(jù)集來驗證算法的有限性，通過與傳統(tǒng)算法的結(jié)果進(jìn)行比較分析，證實算法是可行的。我們從發(fā)現(xiàn)問題，提出問題，分析問題和解決問題四個角度出發(fā)，通過對其自身改進(jìn)算法的研究，深入研究了該算法的優(yōu)劣性，提出了一種基于遺傳算法的k-means聚類算法。

二、實驗結(jié)果與分析

(一)數(shù)據(jù)分析。地球化學(xué)數(shù)據(jù)處理指的是通過某些方法或軟件對地球化學(xué)中的部分元素數(shù)據(jù)進(jìn)行分析研究，繪制成圖，得出結(jié)論的過程(管世明，2012)。本文就以地球化學(xué)元素作為聚類分析的數(shù)據(jù)對象，對地球化學(xué)采樣數(shù)據(jù)進(jìn)行了分析，這里選擇了一組銅的數(shù)據(jù),首先先對這組數(shù)據(jù)進(jìn)行分析，如表1所示，發(fā)現(xiàn)個體差異值很大，最大值和最小值差異明顯，如圖1所示，最大值跟均值差異也很明顯，所以很有可能對聚類產(chǎn)生影響，有可能產(chǎn)生異常值點。將數(shù)據(jù)代入遺傳k-means聚類算法程序中進(jìn)行分析，發(fā)現(xiàn)k值為4的時候聚類效果最好。

表1 元素特征

(二)結(jié)果分析。

利用surfer專業(yè)成圖軟件對聚類結(jié)果進(jìn)行分析產(chǎn)生聚類圖。把數(shù)據(jù)聚類結(jié)果做成分類圖，不同的類別點用不同的顏色表示，從聚類結(jié)果圖上可以明顯的看出存在分布特征特別明顯的幾個區(qū)域，特征表現(xiàn)在:(1)圖中區(qū)域內(nèi)同一顏色的點屬于同一個類;(2)圖中種群擁有相當(dāng)大的規(guī)模，有很大一部分的采樣點，而其他位置上也有其他類的分布。利用聚類分析的優(yōu)勢，依據(jù)地球化學(xué)元素作為聚類分析問題的研究對象，能夠直觀的展示元素的空間分布規(guī)律，指示找礦有利地段。

圖1 原始數(shù)據(jù)散點圖

圖2 聚類分析圖

結(jié)論

k-means聚類算法簡單易行，聚類速度快，但是隨機的初始化容易陷入局部最優(yōu)解。遺傳算法簡單通用，魯棒性高，適合并行處理，但是計算效率過低，同時對局部尋優(yōu)的過程不佳。本文結(jié)合兩種算法的優(yōu)缺點，改進(jìn)了遺傳k-means算法。通過仿真實驗和實際數(shù)據(jù)的處理驗證了算法的有效性。

聚類分析的研究由來已久，本文只是截取龐大體系中的很小一部分開展研究，雖有成果，但仍有需要改進(jìn)之處，如算法的效率方面仍可提高，結(jié)合神經(jīng)網(wǎng)絡(luò)或模糊聚類可能取得更好的效果，這些都是值得進(jìn)一步研究的方向。