一種求解空間數(shù)據(jù)聚類的粒子動(dòng)力學(xué)演化算法
2009-01-01 00:00:00黃學(xué)雨季冰川潘偉豐劉琮徐紅偉
計(jì)算機(jī)應(yīng)用研究 2009年3期
(1.江西理工大學(xué) 信息工程學(xué)院， 江西 贛州 341000; 2.武漢大學(xué) 軟件工程國家重點(diǎn)實(shí)驗(yàn)室， 武漢 430072；3.上海大學(xué) 通信與信息工程學(xué)院， 上海 200072)
摘 要：從空間數(shù)據(jù)挖掘的基本概念出發(fā)，闡述了空間數(shù)據(jù)的特點(diǎn)及空間數(shù)據(jù)挖掘的常規(guī)方法，分析了用常規(guī)方法進(jìn)行數(shù)據(jù)挖掘的不足，提出了一種求解空間數(shù)據(jù)聚類的粒子動(dòng)力學(xué)演化算法——SDCPDEA。該方法有效地避免了用常規(guī)方法進(jìn)行空間數(shù)據(jù)聚類時(shí)的缺陷，增強(qiáng)了聚類分析方法的靈活性和有效性。實(shí)驗(yàn)結(jié)果表明，對(duì)于空間數(shù)據(jù)的聚類分析問題，該算法具有很好的性能。
關(guān)鍵詞：空間數(shù)據(jù)； 數(shù)據(jù)挖掘； 聚類
中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：10013695(2009)03086004
Novel particle dynamical evolutionary algorithm for spatial data clustering
HUANG Xueyu1， JI Bingchuan1， PAN Weifeng2， LIU Cong3， XU Hongwei1
(1.School of Information Engineering， Jiangxi University of Science Technology， Ganzhou Jiangxi 341000， China; 2.State Key Laboratory of Software Engineering， Wuhan University， Wuhan 430072， China; 3.School of Communication Information Engineering， Shanghai University， Shanghai 200072， China)
Abstract:This paper analyzed the features of the spatial data， giving a brief introduction to the challenges facing many researchers in spatial data mining and the difficulties and shortages of traditional methods in clustering analysis of spatial data. And finally proposed a novel particle dynamical evolutionary algorithm for spatial data clustering (SDCPDEA). It effectively solved the two main problems in clustering analysis of spatial data and effectively enhancedthe flexibility and efficiency of the clustering analysis. In numerical experiments， it used this method to solve some clustering problems in spatial data. Compared with the traditional methods， SDCPDEA has better performances.
Key words：spatial data; data mining(DM); clustering
0 引言
隨著數(shù)據(jù)庫技術(shù)的發(fā)展和Internet的迅速普及，信息量猛增，使數(shù)據(jù)庫中數(shù)據(jù)爆炸性增長(zhǎng)，導(dǎo)致傳統(tǒng)的統(tǒng)計(jì)技術(shù)和數(shù)據(jù)管理工具不足以分析海量數(shù)據(jù)，出現(xiàn)了“數(shù)據(jù)豐富，知識(shí)貧乏”的現(xiàn)象，使得如何發(fā)現(xiàn)有價(jià)值的信息或知識(shí)，成為數(shù)據(jù)處理的瓶頸。人們迫切需要有一種數(shù)據(jù)分析工具能從海量數(shù)據(jù)中獲取信息和知識(shí)，從而導(dǎo)致了數(shù)據(jù)挖掘（DM）技術(shù)這一全新技術(shù)領(lǐng)域的出現(xiàn)。它用數(shù)據(jù)庫來存儲(chǔ)數(shù)據(jù)，用自動(dòng)化工具、成熟算法或機(jī)器學(xué)習(xí)等方法來分析數(shù)據(jù)，從海量數(shù)據(jù)中發(fā)現(xiàn)隱藏的模型和結(jié)構(gòu)，挖掘數(shù)據(jù)背后隱含的知識(shí)。而聚類分析是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要的研究課題。迄今為止，人們已經(jīng)提出了很多聚類算法，但是很多都存在不能有效處理局部值的缺陷，特別當(dāng)聚類中心在樣本空間分布不平衡時(shí)，聚類結(jié)果對(duì)初始聚類中心的選取極其敏感。
粒子動(dòng)力學(xué)演化算法[1]是一種基于粒子輸運(yùn)理論的動(dòng)力學(xué)演化算法，是根據(jù)大量粒子（或抽象化為粒子的事物，如街道中的車輛、城市中的居民等）在相空間運(yùn)動(dòng)時(shí)，各粒子的位置、動(dòng)量和其他特征量的變化而引起的各種有關(guān)物理量隨時(shí)空動(dòng)態(tài)變化的過程建立的輸運(yùn)方程，以及粒子群的能量最小原理和熵增法則構(gòu)建一種演化算法。本文正是考慮了常規(guī)方法在處理聚類問題時(shí)的不足（如輸入敏感、效率低等）和粒子動(dòng)力學(xué)演化算法的優(yōu)點(diǎn)（如全局最優(yōu)化、本質(zhì)并行等），有效地將粒子動(dòng)力學(xué)演化算法與空間數(shù)據(jù)的聚類分析結(jié)合起來，提出了一種求解空間數(shù)據(jù)聚類的演化方法——SDCPDEA。
1 空間數(shù)據(jù)挖掘概述
空間數(shù)據(jù)挖掘（spatial data mining，SDM）[2]是指從空間數(shù)據(jù)庫中抽取隱含的知識(shí)、空間關(guān)系或是非顯示地存儲(chǔ)在空間數(shù)據(jù)庫中的有意義的特征或模式，它綜合了數(shù)據(jù)挖掘與空間數(shù)據(jù)庫技術(shù)，可用于對(duì)空間數(shù)據(jù)的理解，發(fā)現(xiàn)空間數(shù)據(jù)與非空間數(shù)據(jù)間的關(guān)系，構(gòu)建空間知識(shí)庫和獲取簡(jiǎn)明的總體特征等。這種技術(shù)是綜合了地理信息系統(tǒng)（GIS）、遙感、圖像數(shù)據(jù)庫、醫(yī)療影響處理、空間數(shù)據(jù)庫系統(tǒng)等領(lǐng)域的有關(guān)技術(shù)而形成的一個(gè)分支學(xué)科，也稱為空間數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)（spatial data mining and knowledge discovery， SDMKD）。
1.1 空間數(shù)據(jù)和空間數(shù)據(jù)挖掘的特點(diǎn)
空間數(shù)據(jù)是對(duì)空間實(shí)體的屬性、數(shù)量、位置及相互關(guān)系等的空間符號(hào)描述。與一般數(shù)據(jù)相比，空間數(shù)據(jù)具有自己獨(dú)特的特點(diǎn)[2]：a)空間數(shù)據(jù)均與某一對(duì)象(地點(diǎn))相關(guān)，空間數(shù)據(jù)中除包含以文字、字符為特征的非空間信息(屬性信息)外，還含有以拓?fù)潢P(guān)系、距離關(guān)系、方向關(guān)系為特征的空間信息；b)空間數(shù)據(jù)具有空間自相關(guān)性，即每一個(gè)事物都與其他事物相關(guān)，但鄰近事物間的相關(guān)性比距離較遠(yuǎn)的事物間的相關(guān)性要大得多。
空間數(shù)據(jù)挖掘技術(shù)作為數(shù)據(jù)挖掘技術(shù)在空間信息上的應(yīng)用，空間數(shù)據(jù)挖掘具有如下特點(diǎn)：a)傳統(tǒng)數(shù)據(jù)挖掘處理的是數(shù)字和列別，而空間數(shù)據(jù)處理一些更加復(fù)雜的數(shù)據(jù)類型，如點(diǎn)、線等對(duì)象；b)傳統(tǒng)數(shù)據(jù)挖掘通常具有顯示的輸入，而空間數(shù)據(jù)挖掘通常具有顯示的輸入；c)傳統(tǒng)數(shù)據(jù)挖掘以數(shù)據(jù)樣本獨(dú)立作為假設(shè)前提，而在空間數(shù)據(jù)挖掘中空間數(shù)據(jù)樣本是高度自相關(guān)的。
正是基于空間數(shù)據(jù)和空間數(shù)據(jù)挖掘各自的特點(diǎn)，使得空間數(shù)據(jù)挖掘比傳統(tǒng)數(shù)據(jù)挖掘更為困難，空間數(shù)據(jù)挖掘領(lǐng)域呼吁新的高效的數(shù)據(jù)挖掘技術(shù)的出現(xiàn)。
1.2 空間數(shù)據(jù)挖掘常規(guī)方法簡(jiǎn)介
空間數(shù)據(jù)挖掘可以分成四類挖掘方法[3~5]，即空間分類和預(yù)測(cè)、空間聚類、空間孤立點(diǎn)和空間關(guān)聯(lián)規(guī)則。本文中主要研究空間數(shù)據(jù)聚類的有關(guān)問題，提出利用演化算法進(jìn)行求解的方法，所以下面只對(duì)空間聚類作介紹，詳見文獻(xiàn)[3~5]。
聚類分析按照某個(gè)相似測(cè)試將未標(biāo)記的樣本集分成若干個(gè)類，使同一類中的樣本盡可能地相似，不同類中的樣本盡可能地不相似。按照聚類結(jié)果表現(xiàn)方式的不同，現(xiàn)有的聚類分析算法可以分為硬聚類算法、模糊聚類算法和可能性聚類算法。
在硬聚類算法中，分類結(jié)果用樣本對(duì)各類的隸屬度表示。樣本對(duì)某個(gè)類別的隸屬度只能是0或1。樣本對(duì)某個(gè)類別的隸屬度為1，表示樣本屬于該類；樣本對(duì)某個(gè)類別的隸屬度為0，則表示樣本不屬于該類。樣本只能屬于所有類別中的某一個(gè)類別。早期的聚類算法都是硬聚類算法。硬聚類算法容易陷入局部極值。
在模糊聚類算法中，分類結(jié)果仍用樣本對(duì)各類的隸屬度表示，只是樣本對(duì)某個(gè)類別的隸屬度在區(qū)是[0，1]內(nèi)取值，樣本對(duì)所有類別的隸屬度之和為1。模糊聚類產(chǎn)生于20世紀(jì)60年代末，是聚類分析與模糊集理論相結(jié)合的產(chǎn)物。模糊聚類算法與硬聚類算法相比，提高了算法的尋優(yōu)概率，但模糊聚類的速度要比硬聚類慢。
可能性聚類算法中，分類結(jié)果以樣本對(duì)各類的典型程度表示。樣本對(duì)某個(gè)類別的典型程度在[0，1]內(nèi)取值。可能性聚類算法是聚類分析與可能性理論的結(jié)晶，它極易陷入局部極值，但可能性聚類算法抑制噪聲能力很強(qiáng)。
總之，在上述的各種聚類分析方法中，聚類分析均無須背景知識(shí)，可以直接從空間數(shù)據(jù)庫中發(fā)現(xiàn)有意義的空間聚類結(jié)構(gòu)。但是，面臨著三大突出問題[3~5]：a）不能有效地處理局部值問題；b）初始聚類中心的選取對(duì)聚類結(jié)果有很大的影響；c）當(dāng)要聚類的數(shù)據(jù)量大時(shí)時(shí)間效率較低。正是為了解決傳統(tǒng)聚類方法存在的問題，提出了下面的基于粒子輸運(yùn)理論的求解空間數(shù)據(jù)聚類的動(dòng)力學(xué)演化算法。
2 空間數(shù)據(jù)聚類的粒子動(dòng)力學(xué)演化算法
文獻(xiàn)[1，6]中提出了一種用于復(fù)雜函數(shù)優(yōu)化的粒子動(dòng)力學(xué)演化算法（PDEA）和一種用于求解復(fù)雜約束優(yōu)化問題的粒子動(dòng)力學(xué)演化算法（CPDEA），作者分析了粒子動(dòng)力學(xué)演化算法的基本原理，并用實(shí)驗(yàn)驗(yàn)證了算法的有效性。下面本文主要論述如何構(gòu)造適合空間數(shù)據(jù)聚類的粒子動(dòng)力學(xué)演化算法，至于標(biāo)準(zhǔn)的粒子動(dòng)力學(xué)演化算法請(qǐng)參見文獻(xiàn)[1，6]。
2.1 SDCPDEA的設(shè)計(jì)
本文對(duì)標(biāo)準(zhǔn)的粒子動(dòng)力學(xué)演化算法進(jìn)行了改造，提出了一種求解空間數(shù)據(jù)聚類的演化方法——SDCPDEA，使其能有效地改進(jìn)常規(guī)聚類方法在空間數(shù)據(jù)聚類中的不足。將針對(duì)演化算法的各個(gè)主要部分，詳細(xì)論述SDCPDEA的設(shè)計(jì)過程。
2.1.1 個(gè)體編碼
個(gè)體的編碼技術(shù)是用演化算法求解聚類問題的第一步。在SDCPDEA算法中，不直接處理空間數(shù)據(jù)庫中的數(shù)據(jù)，而是將種群中的個(gè)體表示成形如{1，5，3，1，2，4，5}的形式。其中：最大的數(shù)字5表示聚類個(gè)數(shù)為5；位置1和4（從左到右）上是兩個(gè)1表示對(duì)應(yīng)的要進(jìn)行聚類處理的數(shù)據(jù)1和4屬于第1個(gè)簇；同理，數(shù)據(jù)5屬于第2個(gè)簇；數(shù)據(jù)3屬于第3個(gè)簇；數(shù)據(jù)6屬于第4個(gè)簇；數(shù)據(jù)2和數(shù)據(jù)7屬于第5個(gè)簇。程序具體實(shí)現(xiàn)時(shí)，用數(shù)組的大小表示進(jìn)行聚類的測(cè)試數(shù)據(jù)個(gè)數(shù)。例如上面的{1，5，3，1，2，4，5}表示數(shù)據(jù)個(gè)數(shù)為7；數(shù)組中的值表示與該元素下標(biāo)對(duì)應(yīng)的測(cè)試數(shù)據(jù)所屬的簇號(hào)，如數(shù)組位置1為1，表示1號(hào)數(shù)據(jù)位于的1號(hào)簇。
2.1.2 種群初始化
此處本文采用文獻(xiàn)[7]中提出的一種基于重復(fù)體統(tǒng)計(jì)的初始化種群方法來初始化本算法中的個(gè)體。這里就不再重復(fù)該方法的原理和細(xì)節(jié)，只是簡(jiǎn)要地給出其算法流程。
基于重復(fù)體統(tǒng)計(jì)的初始化種群方法：
初始化函數(shù) initial_population(void)
{//子程序開始
a)用一般的srand()和rand()組合產(chǎn)生SDCPDEA初始種群；
b)對(duì)上述初始化的每個(gè)個(gè)體的各基因位進(jìn)行判斷，并統(tǒng)計(jì)各個(gè)簇號(hào)在各個(gè)位置出現(xiàn)的次數(shù)。譬如用statistic[i][j]表示簇號(hào)i在群體中位置j出現(xiàn)的次數(shù)；
c)根據(jù)SDCPDEA種群中的個(gè)體數(shù)PopSize、要分成的聚類數(shù)目Num of Clusters、測(cè)試數(shù)據(jù)的個(gè)數(shù)Num of Testing Data，這三者共同來決定每個(gè)位置某簇號(hào)的平均出現(xiàn)概率AverageExist，即AverageExist=(NumOfClusters*PopSize*NumberOfTestingData)/NumOfClusters；
d)遍歷種群中每個(gè)個(gè)體和個(gè)體的每個(gè)位，統(tǒng)計(jì)某個(gè)簇號(hào)重復(fù)出現(xiàn)的次數(shù)；
e)再次遍歷種群中每個(gè)個(gè)體和個(gè)體的每個(gè)位，若該位置某簇號(hào)重復(fù)出現(xiàn)次數(shù)大于AverageExist，則查閱本位置其他簇號(hào)的出現(xiàn)情況，將其變異成相對(duì)小的那個(gè)簇號(hào)。
}//子程序結(jié)束
通過該方法，即兩次遍歷種群，調(diào)整簇號(hào)的分布，以達(dá)到是初始種群分布均勻的目的。為了說明問題，本文做了一個(gè)小實(shí)驗(yàn)，實(shí)驗(yàn)是在種群規(guī)模為50的情況下進(jìn)行的，分別用傳統(tǒng)的方法（srand()與rand()結(jié)合）和上述提出的方法進(jìn)行種群的初始化。圖1顯示了變化前后種群分布的變化。從圖1可以看到，用傳統(tǒng)方法時(shí)個(gè)體在空間上分布不是很均勻，但是用本文的方法后，種群在整個(gè)空間上分布相對(duì)均勻了。例如在T軸方向的[-1.592 9，-1.137 80]上只有3個(gè)個(gè)體，縱軸方向[0.227 6，0.682 7]上也只有3個(gè)個(gè)體，經(jīng)過調(diào)整后在上述兩個(gè)區(qū)間上分布個(gè)體數(shù)分別為5個(gè)和6個(gè)，基本上達(dá)到了平衡（總共50個(gè)個(gè)體，[-2.048，2.048]分成了9段，每段個(gè)體數(shù)50/9=5.5）。在其他的幾個(gè)區(qū)間個(gè)體數(shù)也基本都在4~6個(gè)，與每個(gè)區(qū)間的平均個(gè)體分布數(shù)5.5很接近。這說明本文提出的種群的初始化方法對(duì)種群的分布起到了一定的調(diào)節(jié)作用，是切實(shí)可行的。該方法當(dāng)個(gè)體種群規(guī)模很大，個(gè)體數(shù)多時(shí)效果將更加地明顯。
2.1.3 演化算子設(shè)計(jì)
演化算法一般涉及以下幾個(gè)演化算子的設(shè)計(jì)：選擇、交叉、變異、個(gè)體替換。下面將分別介紹在SDCPDEA中將用到的各個(gè)算子。
1）選擇算子
這種方法是對(duì)于每代中一定數(shù)量的最優(yōu)個(gè)體，使之直接進(jìn)入下一代。這樣可以防止優(yōu)秀個(gè)體由于復(fù)制、雜交或變異中的偶然因素而被破壞掉。這是增強(qiáng)算法穩(wěn)定性和收斂性的有效方法。本文在選擇個(gè)體時(shí)，將本代種群中的最好個(gè)體保留了下來，在交叉過程當(dāng)中充當(dāng)固定的一個(gè)父體，與本代中用輪盤賭選擇得到的其他個(gè)體進(jìn)行雜交。
2）雜交算子
在SDCPDEA中實(shí)行兩種雜交策略，即單點(diǎn)雜交和雙點(diǎn)雜交。
a)單點(diǎn)雜交。考慮下面的父代個(gè)體：
若它們?cè)谖恢?（從左到右）進(jìn)行單點(diǎn)雜交，則交叉后的新個(gè)體為{1，5，3，｜1，3，5，1}和{2，4，5｜，1，2，4，5}。
b)雙點(diǎn)雜交。考慮下面的父代個(gè)體：
若它們?cè)谖恢?（從左到右）和4（從左到右）進(jìn)行雙點(diǎn)雜交，則交叉后的新個(gè)體為{1，5，｜5，｜1，2，4，5}和{2，4，｜3｜，1，3，5，1}。
3)變異算子
變異選擇單點(diǎn)變異，將個(gè)體某個(gè)位置的值變成1到要分成的簇個(gè)數(shù)間的任意整數(shù)。其過程如下：
2.1.4 個(gè)體替換準(zhǔn)則
在SDCPDEA中實(shí)行個(gè)體的部分替換原則，將上一代PA比例的個(gè)體直接進(jìn)化到下一代，而1-PA的個(gè)體被替換掉。越小，進(jìn)化得越快，但算法的穩(wěn)定性和收斂性將受到影響；而PA越大，算法的穩(wěn)定性較好，但進(jìn)化速度將變慢。可見，應(yīng)該尋求運(yùn)行速度與穩(wěn)定性、收斂性之間的協(xié)調(diào)平衡。因此，在SDCPDEA中，在實(shí)行部分替換策略的同時(shí)實(shí)行精英保留策略，讓每代中一定數(shù)量numberOfeliets的最優(yōu)個(gè)體直接進(jìn)入下一代，這樣可以防止優(yōu)秀個(gè)體由于演化操作中的偶然因素而遭到破壞。
2.1.5 適應(yīng)值函數(shù)設(shè)計(jì)
下面的內(nèi)容是根據(jù)輸運(yùn)理論的粒子相空間的輸運(yùn)方程、能量極小原理和熵增法則來定義的，具體的相關(guān)理論請(qǐng)參考文獻(xiàn)[1，6]。在SDCPDEA中通過將初始化種群劃分為多個(gè)簇，求出各個(gè)簇的質(zhì)心，并求得空間其余點(diǎn)與該質(zhì)心的矢量距離，以此作為其與質(zhì)心的相似程度的標(biāo)準(zhǔn)，求得個(gè)體的適應(yīng)值。
1)基本概念定義
定義1 定義簇的質(zhì)心為
centroid(a1，a2，…，an)=(1/N ∑Ni=1P[i].a1，1/N ∑Ni=1P[i].a2，…，1/N ∑Ni=1P[i].an)
其中：centroid(a1，a2，…，an)為簇的質(zhì)心；n為數(shù)據(jù)具有的屬性個(gè)數(shù)；ai，i=1，2，…，n為數(shù)據(jù)的屬性分量；P[i]為個(gè)數(shù)具有的屬性個(gè)數(shù)；P[i].ai為第i個(gè)個(gè)體的ai屬性；N為個(gè)體數(shù)。
定義2 將個(gè)體的矢量距離為
vectorDistancekl=∑ni=1(P[k]i-P[l]i)2
其中：P[k]，k∈(0，1，…，n)為空間中的一個(gè)個(gè)體；n為個(gè)數(shù)據(jù)具有的屬性個(gè)數(shù)；vectorDistancekl即為第k個(gè)個(gè)體與第l個(gè)個(gè)體之間的矢量距離。
圖2描述的是本方法采用的簇個(gè)體分配方法。
下面講解具體的分配過程。如圖2所示，可以直觀地看到，簇Ⅱ中的數(shù)據(jù)O與簇Ⅱ質(zhì)心c2的矢量距離vectorDistanceOC2小于其與簇Ⅰ的質(zhì)心c1的矢量和其與簇Ⅲ、簇Ⅳ的矢量距離vectorDistanceOC3和vectorDistanceOC4，則將數(shù)據(jù)O歸入簇Ⅱ中；反之則歸入其他相應(yīng)的簇中。
定義3 定義p(t，xi，n)=f(t，xi，n)-f(t-1，x，n)為N個(gè)粒子x1，x2，…，xN的SDCPDEA差分輸運(yùn)方程。
其中：xi，x′i∈clustern，i=1，2，3，…，num，n=1，2，…，num of cluster，clustern表示簇號(hào)為n的簇；num表示簇n中含有的粒子個(gè)體數(shù)；num of cluster表示群體中粒子要分成的簇的個(gè)數(shù)；f(x)是定義在種群上的一個(gè)函數(shù)，用于表示粒子x本身，即f(t，xi，n)為第t代中第n簇中的粒子xi， f(t-1，x，n)為第t-1代第n簇的簇心；上式中x′i≠xi，即xi是在簇n中不同于x′i的個(gè)體；t表示種群進(jìn)化的代數(shù)；上述SDCPDEA輸運(yùn)方程中的p(t，xi，n)表示簇號(hào)為n的簇中粒子個(gè)體在第t代時(shí)距離上代簇心的矢量距離。
定義4 定義函數(shù)α(t，xi，n)為簇n中xi在代數(shù)t的活動(dòng)量為SDCPDEA熵。其值為：當(dāng)粒子xi在代數(shù)n參與演化操作時(shí)，α(t，xi，n)=a(t-1，xi，n)+1；否則，α(t，xi，n)=a(t-1，xi，n)，xi∈clustern，i=1，…，num of cluster。本式中，各變量的含義同上。
2)適應(yīng)值函數(shù)
根據(jù)上述輸運(yùn)方程、熵的定義，定義SDCPDEA中的適應(yīng)值函數(shù)。
定義5 SDCPDEA適應(yīng)值函數(shù)
fitness(t，xi，n)=λ1/∑num of clustern=1∑xi∈clusternp(t，xi)2+
λ2ln(α(t，xi，n))
其中：λi∈[0，1]，i=1，2，且λ1+λ2=1稱為SDCPDEA波耳茲曼常數(shù)，它的大小依賴于適應(yīng)值函數(shù)方程右邊∑num of clustern=1∑xi∈clusternp(t，xi)2、ln(α(t，xi，n))以及兩項(xiàng)的權(quán)重。也就是說，哪項(xiàng)的權(quán)重更大，其相應(yīng)項(xiàng)的SDCPDEA波耳茲曼常數(shù)就相應(yīng)要大一些，這樣就能保證整個(gè)微正則系統(tǒng)從非平衡狀態(tài)到平衡狀態(tài)，以達(dá)到幾率均衡，最終使得所有的粒子都有機(jī)會(huì)參與雜交和變異，從而求得所有全局最優(yōu)解。
2.2 SDCPDEA算法流程
a)初始化參數(shù)，包括種群規(guī)模popsize、每代被替換的個(gè)體概率PG、變異概率pm。對(duì)種群進(jìn)行初始化，隨機(jī)產(chǎn)生含有一定數(shù)目個(gè)體的初始種群P(popsize)={ind1，ind2，…，indpopsize}；代數(shù)t：=0。
b)先求得本代中各個(gè)簇的質(zhì)心，并據(jù)此得到各個(gè)個(gè)體的適應(yīng)值fitness，保存最優(yōu)個(gè)體pbest及其適應(yīng)值fitnessbest，保存最差個(gè)體pworst及其適應(yīng)值fitnessworst，并對(duì)個(gè)體按照適應(yīng)值升序排列。
c)對(duì)個(gè)體實(shí)行交叉、變異等演化操作。對(duì)產(chǎn)生的每個(gè)新的個(gè)體進(jìn)行適應(yīng)值判斷，若產(chǎn)生的個(gè)體較本代較差的若干個(gè)體好，則替換掉相應(yīng)個(gè)數(shù)較差個(gè)體，則轉(zhuǎn)d）；否則，轉(zhuǎn)b）。重復(fù)運(yùn)行，直到產(chǎn)生的個(gè)體比本代較差的個(gè)體好，或到了指定的代數(shù)，轉(zhuǎn)d）。重復(fù)運(yùn)行該步若干次，直到滿足替換的概率PG求得的個(gè)數(shù)。
d)重新計(jì)算各個(gè)簇的質(zhì)心，并對(duì)各個(gè)簇按照前文介紹的矢量距離進(jìn)行個(gè)體的重新調(diào)整，再次求得各個(gè)簇的質(zhì)心、各個(gè)個(gè)體的適應(yīng)值fitness、最優(yōu)個(gè)體pbest及其適應(yīng)值fitnessbest、最差個(gè)體pworst及其適應(yīng)值fitnessworst，并對(duì)個(gè)體按照適應(yīng)值升序排列。
e)判斷是否達(dá)到指定的運(yùn)行代數(shù)，若沒達(dá)到則轉(zhuǎn)b）繼續(xù)執(zhí)行；否則，轉(zhuǎn)f）繼續(xù)執(zhí)行。
f）輸出結(jié)果，結(jié)束算法。
3 數(shù)據(jù)實(shí)驗(yàn)
用演化算法求解空間數(shù)據(jù)聚類問題在目前的研究中很少見，所以能夠找到的對(duì)比數(shù)據(jù)有限。在本章中主要討論用上述提出的方法在解決空間數(shù)據(jù)聚類中存在的難題，得到正確的聚類結(jié)果的可行性方面。本文將上面構(gòu)造的用于空間數(shù)據(jù)聚類分析的算法SDCPDEA運(yùn)用于幾個(gè)二維數(shù)據(jù)聚類問題中，選取的例子均來自文獻(xiàn)[8]，意在證明本文所提出的SDCPDEA算法的可行性和有效性。
1)實(shí)驗(yàn)一
一個(gè)數(shù)據(jù)集為
數(shù)據(jù)1：(5，3)， 數(shù)據(jù)2： (1，0)， 數(shù)據(jù)3： (3，5)，
數(shù)據(jù)4：(0，1)，數(shù)據(jù)5： (2，7)， 數(shù)據(jù)6： (7，2)，
數(shù)據(jù)7：(3，3)，數(shù)據(jù)8： (3，4)， 數(shù)據(jù)9： (4，3)，
數(shù)據(jù)10：(6，4)，數(shù)據(jù)11：(4，6)， 數(shù)據(jù)12：(1，6)
程序運(yùn)行結(jié)果是
簇1為數(shù)據(jù)2數(shù)據(jù)4
簇2為數(shù)據(jù)3數(shù)據(jù)5數(shù)據(jù)11數(shù)據(jù)12
簇3為數(shù)據(jù)1數(shù)據(jù)6數(shù)據(jù)10
簇4為數(shù)據(jù)7數(shù)據(jù)8數(shù)據(jù)9
2)實(shí)驗(yàn)二
一個(gè)數(shù)據(jù)集為
數(shù)據(jù)1：(1，0)， 數(shù)據(jù)2：(0，1)， 數(shù)據(jù)3：(1，1)，
數(shù)據(jù)4：(2，1)，數(shù)據(jù)5：(1，2)， 數(shù)據(jù)6：(2，2)，
數(shù)據(jù)7：(3，1)，數(shù)據(jù)8：(1，3)， 數(shù)據(jù)9：(4，3)，
數(shù)據(jù)10：(5，4)，數(shù)據(jù)11：(4，6)， 數(shù)據(jù)12：(1，5)
程序運(yùn)行結(jié)果是
簇1為數(shù)據(jù)8數(shù)據(jù)12
簇2為數(shù)據(jù)4數(shù)據(jù)6數(shù)據(jù)7
簇3為數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)3數(shù)據(jù)5
簇4為數(shù)據(jù)9數(shù)據(jù)10數(shù)據(jù)11
3)實(shí)驗(yàn)結(jié)果分析
SDCPDEA與SDCEA[8]優(yōu)化結(jié)果如表1所示。
從表1可以看到，用SDCPDEA求解上面兩個(gè)實(shí)驗(yàn)，求得的最后結(jié)果與文獻(xiàn)[8]中的SDCEA聚類算法得到的結(jié)果相同。而且筆者在實(shí)驗(yàn)過程中發(fā)現(xiàn)，不論算法運(yùn)行多少次，輸入數(shù)據(jù)的排列順序如何，最終都可以得到正確的解，這說明SDCPDEA算法很好地避免了傳統(tǒng)聚類算法在空間數(shù)據(jù)挖掘過程碰到的問題。因?yàn)樗惴ㄟ\(yùn)行的過程中，實(shí)際操作的個(gè)體是由各個(gè)個(gè)體所處的簇號(hào)構(gòu)成的，演化算法種群初始的隨機(jī)性將導(dǎo)致初始聚類中心的隨機(jī)性，但算法在多次運(yùn)行下均能得到正確的結(jié)果，說明該SDCPDEA很好地糾正了聚類中心的不平衡問題，并且改進(jìn)的演化算法具有很強(qiáng)的跳出局部解的能力。而且SDCPDEA較SDCEA在算法求解的時(shí)間效率上有較大的提高。因此， SDCPDEA是一種進(jìn)行空間數(shù)據(jù)聚類的有效方法。
4 結(jié)束語
本文簡(jiǎn)要介紹了空間數(shù)據(jù)和空間數(shù)據(jù)挖掘的基本原理，并針對(duì)用常規(guī)方法進(jìn)行空間數(shù)據(jù)聚類分析的難點(diǎn)和不足，創(chuàng)造性地將粒子動(dòng)力學(xué)演化算法與空間數(shù)據(jù)的聚類分析結(jié)合起來，提出了一種求解空間數(shù)據(jù)聚類問題的粒子動(dòng)力學(xué)演化算法——SDCPDEA，有效地解決了用傳統(tǒng)方法進(jìn)行空間數(shù)據(jù)聚類分析時(shí)存在的問題。實(shí)驗(yàn)結(jié)果表明，對(duì)于空間數(shù)據(jù)的聚類分析問題，該算法是可行的、有效的。
參考文獻(xiàn)：
［1］李康順，李元香，湯銘端，等. 粒子動(dòng)力學(xué)演化算法及其在求解SOP上的應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào)，2005，17(3)：595598.
[2]胡彩平，秦小麟.空間數(shù)據(jù)挖掘研究綜述[J].計(jì)算機(jī)科學(xué)，2007，34(5):1419.
[3]LI D， CHENG Tao. KDGknowledge discovery from GIS[C]//Proc of Canadian Conference on GIS.Dttawa:[s.n.]，1994.
[4]KOPERSKI K. A progressive refinement approach to spatial data mining[D].British Columbia:Simon Fraser University，1999.
[5]DASU T. Exploratory data mining and data cleaning[M].New York：Wiley， 2003.
[6]李康順，李元香，康立山，等.一種求解復(fù)雜約束優(yōu)化問題的粒子動(dòng)力學(xué)演化算法[J].模式識(shí)別與人工智能，2006，19(4)：538545.
[7]李康順，潘偉豐，張文生，等. 基于統(tǒng)計(jì)分析和停滯速度的GEP自動(dòng)建模[J].計(jì)算機(jī)應(yīng)用研究，2008，25(8):23122315.
[8]蘭小機(jī)，徐紅偉，潘偉豐，等. 基于改進(jìn)演化算法的空間數(shù)據(jù)聚類方法[J].計(jì)算機(jī)工程， 2008，34（22）:2931.
