燕京京，王　鵬，范家兵，黃　焱

(1．中國科學(xué)院成都計(jì)算機(jī)應(yīng)用研究所，四川成都610041; 2．成都信息工程學(xué)院并行計(jì)算實(shí)驗(yàn)室，四川成都610225; 3．中國科學(xué)院大學(xué)，北京100049)

?

基于量子諧振子模型的聚類中心選取算法

燕京京1，3，王鵬2，范家兵1，3，黃焱1，3

(1．中國科學(xué)院成都計(jì)算機(jī)應(yīng)用研究所，四川成都610041; 2．成都信息工程學(xué)院并行計(jì)算實(shí)驗(yàn)室，四川成都610225; 3．中國科學(xué)院大學(xué)，北京100049)

摘要:提出了一種基于量子諧振子模型的聚類中心選取算法．該算法以量子諧振子波函數(shù)從高能態(tài)到基態(tài)過程中的概率變化過程為理論模型來描述聚類問題中數(shù)據(jù)對象向聚類中心點(diǎn)的聚集行為，能夠快速查找到最優(yōu)的聚類個(gè)數(shù)及較好的聚類中心點(diǎn)所在的網(wǎng)格;數(shù)據(jù)讀入網(wǎng)格結(jié)構(gòu)之后，算法的處理時(shí)間與數(shù)據(jù)集規(guī)模無關(guān)．實(shí)驗(yàn)結(jié)果表明: CCSA-QHOM算法較適合于處理每個(gè)子類局部區(qū)域的網(wǎng)格密度分布呈單峰特性的數(shù)據(jù)集的聚類中心選擇問題．

關(guān)鍵詞:聚類中心;量子諧振子;聚類個(gè)數(shù);網(wǎng)格;單峰特性

1　引言

聚類分析也稱為“無師可學(xué)”的分類［1］，是根據(jù)物理或抽象對象之間的相似性將它們聚為若干類的過程．屬于同一類的對象之間的相似性高，不屬于同一類的對象之間的相異性高［2，3］．聚類分析發(fā)展至今，產(chǎn)生的聚類方法主要可以分為以下幾類:基于劃分的方法，基于密度的方法，基于網(wǎng)格的方法，基于層次的方法，基于模型的方法及基于約束的方法［2］．其中，基于劃分的方法以聚類中心點(diǎn)來表征數(shù)據(jù)集的位置，如K-means聚類算法．K-means聚類算法以其簡單，有效性廣泛地應(yīng)用于工程研究之中．但是，K-means聚類算法從產(chǎn)生之時(shí)就面臨著一個(gè)重要問題:初始聚類中心點(diǎn)的選擇不當(dāng)會使算法過早的收斂于局部最優(yōu)解［4］．此后，很多學(xué)者對K-means聚類算法的初始中心點(diǎn)的選擇方法進(jìn)行了研究．到目前為止，初始中心選擇方法大概可以分為三種［5］:隨機(jī)選擇法，距離優(yōu)化法，密度估計(jì)法．這三種方法中的典型代表分別是傳統(tǒng)K-means算法［6］，簡易中心搜索法［7］，KR方法［8］．當(dāng)前，還有一些學(xué)者將研究方向轉(zhuǎn)向智能算法來解決初始中心點(diǎn)隨機(jī)選擇導(dǎo)致的局部極值問題，如將粒子群算法［9～11］等優(yōu)化算法運(yùn)用于該問題的研究．這些算法雖然能夠在很大程度上降低結(jié)果陷入局部最優(yōu)的概率，但是不能自動發(fā)現(xiàn)聚類的數(shù)目．同粒子群算法相比，量子諧振子算法［12］不僅具有全局尋優(yōu)能力，通過參數(shù)的合理調(diào)整，其還有較強(qiáng)的局部尋優(yōu)能力．

本文基于文獻(xiàn)［12］提出了一種基于量子諧振子模型的聚類中心選取算法(Clustering Center Selecting Algorithm Based on Quantum Harmonic Oscillator Model，CCSA-QHOM)，來解決初始中心點(diǎn)選擇不當(dāng)導(dǎo)致局部極值及在運(yùn)算過程中不能自適應(yīng)的確定聚類個(gè)數(shù)的問題．該算法以量子諧振子從高能態(tài)到低能態(tài)躍遷過程中的波函數(shù)概率收斂過程為理論模型來描述聚類問題中數(shù)據(jù)對象向聚類中心點(diǎn)的聚集行為．CCSA-QHOM能夠快速的定位到聚類中心的位置，并在合理的參數(shù)設(shè)置下自動得到實(shí)際的聚類個(gè)數(shù)．實(shí)驗(yàn)階段通過七組實(shí)驗(yàn)來說明CCSA-QHOM算法的適用性和有效性．

2　量子諧振子模型

量子力學(xué)是現(xiàn)代物理學(xué)的理論基礎(chǔ)，而量子諧振子是其中重要的模型系統(tǒng)之一．量子諧振子波函數(shù)可以采用高斯分布函數(shù)來解釋從高能態(tài)向基態(tài)的收斂過程．在一維諧振子中，粒子的理想運(yùn)動模型是指一個(gè)質(zhì)量為m的粒子被置于勢能無窮大的阱中，沿著某一方向(如x軸方向)運(yùn)動，以平衡位置為坐標(biāo)原點(diǎn)，則一維諧振子的勢能表示為［13］:

利用薛定諤方程來求一維諧振子的波函數(shù)，可得:

量子諧振子模型中波函數(shù)的概率密度函數(shù)與能級之間的關(guān)系如圖1．

從圖1中可以看出，隨著量子諧振子波函數(shù)從高能態(tài)到基態(tài)，其概率密度函數(shù)從多個(gè)高斯函數(shù)疊加逐漸收斂到一個(gè)高斯函數(shù)．在基態(tài)時(shí)的概率密度函數(shù)為:

量子諧振子物理模型是根據(jù)圖1中的概率變化規(guī)律來建立的模型．其主要思想是:開始時(shí)量子諧振子處于運(yùn)動活躍的高能態(tài)．此時(shí)的波函數(shù)概率密度函數(shù)是多個(gè)高斯函數(shù)的疊加．隨著能級的降低，概率密度函數(shù)的個(gè)數(shù)逐漸減少，量子諧振子的運(yùn)動逐漸趨于穩(wěn)定．到達(dá)基態(tài)時(shí)，概率密度函數(shù)收斂到一個(gè)高斯函數(shù)，此時(shí)量子諧振子處于穩(wěn)定狀態(tài)．當(dāng)前，對量子諧振子的物理模型應(yīng)用的研究如下:文獻(xiàn)［14］將量子諧振子模型用于解決粒子群算法的全局收斂問題，文獻(xiàn)［15］提出了量子諧振子蟻群算法，來解決組合優(yōu)化中旅行商尋優(yōu)問題，文獻(xiàn)［12］中的量子諧振子算法是根據(jù)量子諧振子物理模型設(shè)計(jì)的一種解決高維函數(shù)全局優(yōu)化問題的算法．其主要包括兩個(gè)收縮過程:一個(gè)是高斯采樣函數(shù)的尺度從大到小的收斂過程，來獲得優(yōu)化函數(shù)的信息．另一個(gè)是在同一尺度下高斯采樣函數(shù)的個(gè)數(shù)從多到少的收斂過程，該過程是在多維優(yōu)化函數(shù)信息引導(dǎo)下的量子諧振子向能量基態(tài)的運(yùn)動過程．CCSA-QHOM算法主要是根據(jù)該算法中同一尺度下多個(gè)高斯采樣函數(shù)的收縮聚焦過程是一種聚集區(qū)間的定位過程來設(shè)計(jì)的．

3　CCSA-QHOM算法原理

量子諧振子向基態(tài)的物理變化過程與聚類算法中聚類中心的逐步確定過程非常相似．類比于量子諧振子的物理過程，CCSA-QHOM算法用量子諧振子的物理模型解釋如下:算法起始時(shí)，初始化l組初始中心點(diǎn)，由于此時(shí)整個(gè)聚類系統(tǒng)中的初始中心點(diǎn)分布是雜亂、無序的，此時(shí)中心點(diǎn)所在的網(wǎng)格可以看作是量子諧振子模型中諧振子運(yùn)動比較頻繁的高能態(tài)．在網(wǎng)格空間中，從多個(gè)初始中心點(diǎn)開始的高斯函數(shù)經(jīng)過多次迭代收斂到網(wǎng)格密度局部最大處的過程，類比于圖1中所展示的在目標(biāo)函數(shù)指引下的量子諧振子向能量基態(tài)運(yùn)動過程中的概率收斂過程．由于CCSA-QHOM算法最終要定位到的位置是所有的網(wǎng)格密度局部最大處，到達(dá)這些位置時(shí)，高斯函數(shù)的迭代過程結(jié)束，所以高斯函數(shù)收斂到密度局部最大網(wǎng)格時(shí)的狀態(tài)類比于量子諧振子模型中的穩(wěn)定態(tài)-基態(tài)．

為了下文描述的方便，本文給出了以下四個(gè)定義和一個(gè)定理．

定義1網(wǎng)格密度S指每個(gè)網(wǎng)格中包含的原始數(shù)據(jù)集中的點(diǎn)數(shù)．

定義2網(wǎng)格尺度scale指的是每一維上一段網(wǎng)格的長度．

定義3采樣尺度σ指的是高斯函數(shù)的方差，描述了高斯函數(shù)采樣區(qū)間的范圍．

定義4網(wǎng)格密度閾值是指該網(wǎng)格區(qū)域成為稠密網(wǎng)格區(qū)域所包含的最少數(shù)據(jù)對象數(shù)目．

定理若Si代表第i次高斯采樣迭代到的網(wǎng)格對應(yīng)的密度，則下一步的移動方向評判函數(shù)ΔSi= Si－Si－1．

CCSA-QHOM算法的收斂過程

量子諧振子模型向基態(tài)的收斂過程在網(wǎng)格空間上的描述如下:首先，在數(shù)據(jù)集中隨機(jī)選擇l個(gè)點(diǎn)，這些點(diǎn)在每一維上的坐標(biāo)值分別作為該維上高斯采樣的初始均值位置，以該l個(gè)均值位置分別構(gòu)造標(biāo)準(zhǔn)差為σ的高斯函數(shù)N(Xi，σ2) (i =1，…，l)，形成l個(gè)采樣區(qū)域，從而構(gòu)造了高能態(tài)的量子諧振子．然后，每個(gè)區(qū)域分別按N (Xi，σ2)在定義域上采樣產(chǎn)生l個(gè)解;將所有維度上第j次迭代產(chǎn)生的解構(gòu)成的向量對應(yīng)到一個(gè)網(wǎng)格，若移動方向評判函數(shù)ΔSj0，則以第j次迭代產(chǎn)生的解作為每一維上新的均值位置．否則，分別重新進(jìn)行第j次迭代采樣．這相當(dāng)于量子諧振子模型中諧振子向低能態(tài)躍遷時(shí)的概率選擇過程．這樣，l個(gè)標(biāo)準(zhǔn)差為σ的高斯函數(shù)，隨著高斯采樣區(qū)域均值位置的改變而逐漸向聚合中心點(diǎn)所在的網(wǎng)格處聚集．該過程對應(yīng)于l個(gè)高斯函數(shù)疊加形成的波函數(shù)逐漸收斂于m(m≤l)個(gè)高斯分布N (im，σ2)的能量基態(tài)．聚集在聚合中心處的高斯函數(shù)構(gòu)造了基態(tài)的量子諧振子．該收斂過程用2維數(shù)據(jù)集來描述如圖2所示．

在圖2中，以量子諧振子中一個(gè)高斯采樣的運(yùn)動過程為例來描述CCSA-QHOM算法收斂過程．圖中每個(gè)網(wǎng)格中的數(shù)據(jù)代表的是原始數(shù)據(jù)集被劃分到該網(wǎng)格中的數(shù)據(jù)點(diǎn)數(shù)．圖2中的收斂過程描述如下:首先，隨機(jī)選取初始中心點(diǎn)(x0，y0)，點(diǎn)(x0，y0)所對應(yīng)的網(wǎng)格密度S0為3，如圖2(a)所示．然后，分別以x0，y0作為x，y軸上高斯函數(shù)的均值，在x軸上得到高斯函數(shù)x～N(x0，σ2x)，以此高斯函數(shù)在x軸上進(jìn)行采樣，選出x1．在y軸上得到高斯函數(shù)y～N(y0，σ2y)，以此高斯函數(shù)在y軸上進(jìn)行采樣，選出y1．點(diǎn)(x1，y1)對應(yīng)的網(wǎng)格密度S1為63，該過程如圖2(b)所示．比較S0，S1，由于ΔS10，則x1，y1分別作為x，y軸上新的均值．然后，以高斯函數(shù)N(x1，分別在x，y軸上進(jìn)行采樣，選出x2，y2．點(diǎn)(x2，y2)對應(yīng)的網(wǎng)格密度S2為245，該過程如圖2(c)所示．由于ΔS20，則以x2，y2分別作為新的均值的取值，繼續(xù)高斯采樣，由于點(diǎn)(x2，y2)對應(yīng)的網(wǎng)格密度是局部最大的，此后高斯采樣選出的作為新的均值的點(diǎn)都將出現(xiàn)在點(diǎn)(x2，y2)對應(yīng)的網(wǎng)格中，整個(gè)迭代過程結(jié)束．

4　CCSA-QHOM算法過程

CCSA-QHOM算法分為以下幾個(gè)部分: (1)網(wǎng)格劃分階段，該階段是整個(gè)算法的基礎(chǔ)，網(wǎng)格劃分的是否合理直接關(guān)系到算法最終定位的位置的合理性; (2)數(shù)據(jù)投影; (3)算法的量子諧振子收斂階段，該階段采用高斯函數(shù)來進(jìn)行數(shù)據(jù)對象的采樣與網(wǎng)格位置的定位．主要過程是對當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算移動方向評判函數(shù)→接受或舍棄”的迭代．

4.1網(wǎng)格劃分階段

已知數(shù)據(jù)集為2維數(shù)據(jù)集D(數(shù)值型數(shù)據(jù)的數(shù)據(jù)集)劃分網(wǎng)格空間S，CCSA-QHOM算法采用以下的網(wǎng)格劃分方法:由用戶設(shè)定每一維網(wǎng)格的尺度scale，若每一維數(shù)據(jù)取值的最大值為imax，最小值為imin(i代表第幾維)，則每一維的網(wǎng)格段數(shù)mi為網(wǎng)格總數(shù)為:

4.2數(shù)據(jù)投影階段

已知在2-維數(shù)據(jù)集D中，xij代表數(shù)據(jù)集中的第i個(gè)數(shù)據(jù)點(diǎn)的第j維坐標(biāo)的取值，jmin代表第j維數(shù)據(jù)中的最小值R，?jmin」表示小于R的最大整數(shù)值．則xij的數(shù)據(jù)投影方法為經(jīng)過投影后的數(shù)據(jù)集的聚類問題就類似于求解函數(shù)f(m，n) (m，n分別為網(wǎng)格的第一維、第二維坐標(biāo))的優(yōu)化問題．文獻(xiàn)［12］中的量子諧振子算法是一種能夠得到完善的全局最優(yōu)解或局部最優(yōu)解的函數(shù)優(yōu)化算法，其具有高效的搜索區(qū)域收縮定位能力．鑒于此，設(shè)計(jì)了下面的量子諧振子收斂階段的算法．

4.3算法的量子諧振子收斂階段

該階段用對2維數(shù)據(jù)的處理過程來描述，這一階段對應(yīng)于量子諧振子從高能態(tài)向基態(tài)的能量變化過程．

按照4.1、4.2所示方法劃分網(wǎng)格并將數(shù)據(jù)集D中的點(diǎn)投影到網(wǎng)格空間中，記錄每個(gè)網(wǎng)格的坐標(biāo)及其密度．

Step1從數(shù)據(jù)集D中隨機(jī)選取l組點(diǎn)(xi0，yi0) (其中i代表第幾個(gè)對象，i的取值范圍為0到l-1)作為初始聚類中心．并分別記錄每組(xi0，yi0)所對應(yīng)的網(wǎng)格密度Si0．

Step2以xi0，yi0分別作為x，y軸上高斯隨機(jī)采樣函數(shù)的均值，設(shè)定x，y軸的標(biāo)準(zhǔn)差σx，σy，在x軸上構(gòu)造以xi0為均值的高斯函數(shù)N(xi0，)，可以在x軸上形成l個(gè)采樣區(qū)域．同理，在y軸上構(gòu)造以yi0為均值的高斯函數(shù)N(yi0，)，在y軸上形成l個(gè)采樣區(qū)域．類比于圖1，該過程構(gòu)造了高能態(tài)的量子諧振子．

Step3在x軸上的l個(gè)采樣區(qū)域內(nèi)分別以相應(yīng)的高斯函數(shù)N(xi0，)進(jìn)行高斯采樣，選出xi1．然后，在y軸上的l個(gè)采樣區(qū)域內(nèi)分別以高斯函數(shù)N(yi0，)進(jìn)行高斯采樣，選出yi1．記錄點(diǎn)(xi1，yi1)所對應(yīng)的網(wǎng)格密度Si1．

Step4分別比較Si0，Si1，若ΔSi10，則xi1，yi1分別作為x軸，y軸上新的高斯采樣函數(shù)的均值，即新的xi0，yi0，繼續(xù)步驟Step2．否則，仍以原來的xi0，yi0作為高斯采樣函數(shù)的均值，繼續(xù)Step2．

Step5重復(fù)上述步驟Step2，Step3，Step4的過程，直到連續(xù)迭代多次定位到的網(wǎng)格位置不變?yōu)橹梗藭r(shí)，多個(gè)高斯函數(shù)疊加到密度局部最大的網(wǎng)格處，類比于圖1，構(gòu)造了基態(tài)的量子諧振子．

Step6對所得到的l組聚類結(jié)果進(jìn)行比較，將網(wǎng)格位置相鄰近的結(jié)果進(jìn)行合并，以其中密度最大的網(wǎng)格位置為代表．

Step7程序自動設(shè)定網(wǎng)格密度閾值，來屏蔽掉噪聲數(shù)據(jù)．

經(jīng)由以上幾步，輸出聚類最終個(gè)數(shù)及聚類中心所在的網(wǎng)格位置．

Step2到Step5整個(gè)過程相當(dāng)于圖1中描述的波函數(shù)從高能態(tài)到基態(tài)過程中的概率收斂過程．Step6類比于每一組初始中心點(diǎn)到達(dá)的基態(tài)位置的最終確定．

4.4算法復(fù)雜度分析

在數(shù)據(jù)投影階段，從數(shù)據(jù)對象投影到相應(yīng)網(wǎng)格的計(jì)算方法分析知，該階段的時(shí)間復(fù)雜度為O(n)，其中n為數(shù)據(jù)集中的點(diǎn)數(shù)．在核心算法階段，初始化聚類數(shù)為l，分別以每組初始聚類中心點(diǎn)的位置為起始位置進(jìn)行高斯采樣重定位，該過程主要是高斯采樣的迭代過程及網(wǎng)格的選擇與比較．則該過程的時(shí)間復(fù)雜度為，其中mi為以第i個(gè)初始值為起始位置所進(jìn)行的所有高斯采樣的迭代次數(shù)．將高斯采樣迭代重定位后所得到的l組聚類結(jié)果中位置相鄰的歸并為一個(gè)結(jié)果，這一過程主要是將結(jié)果進(jìn)行兩兩比較，在最壞情況下所需要的計(jì)算次數(shù)是，則時(shí)間復(fù)雜度為O (l2)．若是比較過程選出p個(gè)網(wǎng)格位置，由于每一個(gè)被選出的網(wǎng)格附近的網(wǎng)格數(shù)為3q－1(其中q的取值為1 或2或3)，則對以該p個(gè)網(wǎng)格位置為中心進(jìn)行一次遍歷的時(shí)間復(fù)雜度為O(pq)．最后，在所得的聚類結(jié)果中查找大于密度閾值的網(wǎng)格單元，并將其輸出，時(shí)間復(fù)雜度為O(p)．由于l，p，q都為常數(shù)，所以該算法核心階段的時(shí)間復(fù)雜度為．由于每組初始聚類中心位置的隨機(jī)選擇導(dǎo)致不同初始聚類中心開始的高斯采樣次數(shù)mi是一個(gè)不確定的值，但是該值通常情況下不大于網(wǎng)格劃分?jǐn)?shù)．在l較大的情況下，即時(shí)，該算法的整體時(shí)間復(fù)雜度集中在核心算法階段，為．否則，該算法的整體時(shí)間復(fù)雜度集中在數(shù)據(jù)投影階段，為O(n)．

5　實(shí)驗(yàn)分析

5.1數(shù)據(jù)集及實(shí)驗(yàn)說明

本文所采用的數(shù)據(jù)來源于標(biāo)準(zhǔn)數(shù)據(jù)集和仿真生成，數(shù)據(jù)集Data1來自于聯(lián)合程序開發(fā)網(wǎng)，數(shù)據(jù)集Data2 和Data3由仿真生成．Data1中有10000組數(shù)據(jù)和3個(gè)類，用于說明噪聲數(shù)據(jù)對算法結(jié)果的影響．Data2中有8829組數(shù)據(jù)和四個(gè)大小不一樣的類，用于說明類大小多樣的數(shù)據(jù)對CCSA-QHOM算法結(jié)果的影響．Data3中有6175組數(shù)據(jù)和3個(gè)分布密度不同的類，用來檢驗(yàn)CCSA-QHOM算法對密度多樣數(shù)據(jù)的聚類中心定位情況．本文還采用UCI數(shù)據(jù)庫中的Iris數(shù)據(jù)集，Haberman數(shù)據(jù)集，Wilt數(shù)據(jù)集(實(shí)驗(yàn)時(shí)對Wilt數(shù)據(jù)集進(jìn)行了降維處理)來驗(yàn)證CCSA-QHOM算法的有效性．通過經(jīng)典DBSCAN算法的數(shù)據(jù)集來驗(yàn)證CCSA-QHOM算法的適用性．圖3描述的是數(shù)據(jù)集Data1到Data3的二維網(wǎng)格分布圖．此外，本文中的所有實(shí)驗(yàn)都是在同一臺機(jī)器上完成的，具體的軟硬件參數(shù)如下:操作系統(tǒng)為Windows XP，CPU為Intel Core i3，主頻2.26GHz．

5.2實(shí)驗(yàn)中參數(shù)設(shè)定對結(jié)果的影響

在CCSA-QHOM算法中，由于網(wǎng)格尺度scale，初始化聚類數(shù)與采樣尺度都是未知的，它們的實(shí)驗(yàn)數(shù)據(jù)隨著數(shù)據(jù)集的不同而有所改變，需要根據(jù)經(jīng)驗(yàn)給出大概取值．其中網(wǎng)格尺度與采樣尺度之間的關(guān)系是:網(wǎng)格尺度與采樣尺度取值之間是正相關(guān)的，當(dāng)網(wǎng)格尺度較大時(shí)，較大的采樣尺度才更容易得到較好的結(jié)果．由于兩者之間的這種關(guān)系，所以在下面的分析中只分析了初始化聚類數(shù)和采樣尺度對結(jié)果正確率的影響．

5．2．1初始化聚類數(shù)對結(jié)果正確率的影響

從算法的原理分析知:初始化聚類數(shù)l最小要大于實(shí)際的聚類個(gè)數(shù)．在實(shí)際的聚類個(gè)數(shù)未知的情況下，l的取值應(yīng)盡量大．文獻(xiàn)［16］通過對k近鄰分類算法中參數(shù)k設(shè)置的研究，給出了如下規(guī)則:(n為樣本中點(diǎn)的總數(shù))，在CCSA-QHOM算法中，由于網(wǎng)格是度量的最小單位，所以l的取值不僅與數(shù)據(jù)點(diǎn)的總數(shù)有關(guān)，還跟網(wǎng)格的劃分尺度有關(guān)．

對CCSA-QHOM算法進(jìn)行多次實(shí)驗(yàn)發(fā)現(xiàn):當(dāng)網(wǎng)格尺度scale劃分合適時(shí)，上面的規(guī)則也是適用的．當(dāng)網(wǎng)格尺度足夠小時(shí)，較大的l才能使聚類結(jié)果較優(yōu)．

表1描述的是對于數(shù)據(jù)集Data1，Data2，Data3，不同的初始化聚類數(shù)l對結(jié)果正確率的影響情況．

對表1中的數(shù)據(jù)進(jìn)行分析發(fā)現(xiàn):在100次算法調(diào)試中，隨著l的增大，算法CCSA-QHOM對這三組數(shù)據(jù)調(diào)試的結(jié)果正確率都在逐漸增加．當(dāng)l增大到一定程度時(shí)，對結(jié)果正確數(shù)的影響將不再明顯．出現(xiàn)這種現(xiàn)象的原因是在CCSA-QHOM算法中，雖然初始中心點(diǎn)的位置是隨機(jī)選取的，采樣過程也是隨機(jī)的，但是由于量子諧振子模型中基態(tài)的“引力”作用導(dǎo)致從不同的初始中心點(diǎn)開始的采樣最后匯聚在同一位置處．這種情況雖然是CCSAQHOM算法的基本思想過程，但是當(dāng)l較小時(shí)，l與實(shí)際的聚類數(shù)相差不大，導(dǎo)致這種情況的發(fā)生對結(jié)果聚類數(shù)的影響非常顯著．當(dāng)l較大時(shí)，l遠(yuǎn)遠(yuǎn)大于實(shí)際聚類數(shù)，這種情況發(fā)生的次數(shù)越多，導(dǎo)致聚類結(jié)果質(zhì)量越優(yōu)．

表1　初始化聚類數(shù)l與結(jié)果正確率之間的關(guān)系

5．2．2采樣尺度σ的影響

采樣尺度σ的選擇關(guān)系到搜索最優(yōu)解要進(jìn)行的采樣次數(shù)的多少，所以要慎重．經(jīng)過多次實(shí)驗(yàn)發(fā)現(xiàn):當(dāng)初始化聚類數(shù)，網(wǎng)格尺度一定時(shí)，隨著σ的增大，高斯隨機(jī)采樣的計(jì)算次數(shù)會減小．如圖4所示．

圖4描述了對于不同數(shù)據(jù)集Data1，Data2，Data3，采樣尺度σ對高斯采樣函數(shù)迭代次數(shù)的影響．從圖中可以看出，對于數(shù)據(jù)集Data1，Data2，Data3，隨著高斯函數(shù)采樣尺度的增加，高斯采樣的迭代次數(shù)在逐漸減少．

這是由于當(dāng)高斯函數(shù)的采樣尺度σ較小時(shí)，采樣跨度較小，歷經(jīng)整個(gè)網(wǎng)格區(qū)間需要行走很多步，即生成很多點(diǎn)．σ較大時(shí)，采樣跨度較大，采樣頻率較低，導(dǎo)致所需的計(jì)算次數(shù)相對較少．從圖中可以看出σ= 2處是變化趨勢快慢的分水嶺，所以，CCSA-QHOM算法對于Data1，Data2，Data3這三種數(shù)據(jù)集進(jìn)行調(diào)試時(shí)，采樣尺度選擇的都是2．

5.3算法結(jié)果評估

5．3．1仿真數(shù)據(jù)的結(jié)果研究

在下面的實(shí)驗(yàn)中，將CCSA-QHOM算法與隨機(jī)選擇法這兩種K-means初始化方法對數(shù)據(jù)集Data1，Data2，Data3的聚類結(jié)果分別用圖5中的圖(a)～(f)表示．其中的隨機(jī)選擇法展示的是10次隨機(jī)選取出現(xiàn)次數(shù)最多的結(jié)果．圖5中，圖(a)，(c)，(e)中標(biāo)出的區(qū)域是CCSA-QHOM算法找到的中心點(diǎn)的位置．圖5(b)，(d)，(f)中標(biāo)出的位置是進(jìn)行隨機(jī)選擇初始中心點(diǎn)的K-means運(yùn)算最終得到的聚類中心的位置．可以看出CCSA-QHOM算法對于噪聲數(shù)據(jù)，類的大小相差很大的數(shù)據(jù)，類的密度相差較大的數(shù)據(jù)等隨機(jī)選擇法不善于處理的數(shù)據(jù)類型找到的聚類中心點(diǎn)位置更準(zhǔn)確．這是由于CCSA-QHOM算法中采用的量子諧振子模型以收斂到密度局部最大的網(wǎng)格處為終止條件，而密度局部最大的區(qū)域一般都在子類的聚合中心附近．

表2，表3描述的是對于不同的數(shù)據(jù)集Data1，Data2，Data3; CCSA-QHOM，Canopy算法和傳統(tǒng)的K-means算法的平均運(yùn)行時(shí)間和最后得到的聚類中心結(jié)果與實(shí)際聚合中心的距離比較．對于CCSA-QHOM算法中的聚合中心用最終定位到的網(wǎng)格的幾何中心代表．Canopy算法是根據(jù)文獻(xiàn)［17］描述的第一階段進(jìn)行的設(shè)計(jì)．K-means算法的數(shù)據(jù)取自10次運(yùn)算中出現(xiàn)次數(shù)最多的聚類結(jié)果，對于數(shù)據(jù)集Data1，Data2，Data3，K的取值分別為4，4，3．從表2可以看出: Canopy算法對數(shù)據(jù)集Data1，Data2，Data3的平均運(yùn)行時(shí)間最短，但是表3表明CCSA-QHOM算法定位到的聚合中心效果最優(yōu)．其平均運(yùn)行時(shí)間雖比Canopy算法長，但依然在一個(gè)數(shù)量級上，相差不大．

對于Data1，Data2，Data3這三種特殊的數(shù)據(jù)集，CCPA-QHOM算法最終定位到的聚類中心最優(yōu)的原因是: CCPA-QHOM算法由于其基本思想是始終向網(wǎng)格密度局部最大處(量子諧振子中的基態(tài))靠攏，只有定位到密度局部最大處時(shí)迭代過程才停止，而密度局部最大處都是在類的聚合中心附近，導(dǎo)致了初始中心點(diǎn)的隨機(jī)選擇只影響了其找到網(wǎng)格密度最大處時(shí)的迭代次數(shù)及采樣的初始范圍，對聚類結(jié)果質(zhì)量影響不大．但是，在CCPA-QHOM算法中網(wǎng)格的劃分，采樣尺度的設(shè)置是否合理直接關(guān)系著算法最終定位到的位置的合理性．

表2　不同聚類算法對三種數(shù)據(jù)集的平均運(yùn)行時(shí)間(s)的比較

表3　不同聚類算法得到的聚合中心與實(shí)際聚合中心的距離

5．3．2真實(shí)數(shù)據(jù)集的結(jié)果研究

表4描述了不同的初始聚類中心選擇方式對真實(shí)數(shù)據(jù)集進(jìn)行處理得到的聚類中心與實(shí)際聚合中心的距離．表4說明了CCSA-QHOM算法始終以找到網(wǎng)格密度最大的區(qū)域?yàn)槟繕?biāo)，由于網(wǎng)格劃分尺度的影響，其找的中心位置與隨機(jī)選擇算法的某些結(jié)果相比并不是最好的，但是其定位到的中心位置始終比Canopy算法要好，且在網(wǎng)格尺度、采樣尺度不變的情況下，其定位到中心位置始終不變，穩(wěn)定性比較好．從而說明CCSA-QHOM算法進(jìn)行中心點(diǎn)的確定是可行的．

表4　不同初始中心選擇方式對真實(shí)數(shù)據(jù)集得到的聚類中心與實(shí)際聚合中心的比較

表5描述的是:對于不同的初始聚類中心選擇方法產(chǎn)生的初始聚類中心，分別作為K-means算法的初始聚類中心進(jìn)行K-means聚類運(yùn)算得到的結(jié)果中數(shù)據(jù)點(diǎn)被正確劃分所占比率．從表中可以看出: CCSA-QHOM算法的結(jié)果作為K-means算法的初始聚類中心來進(jìn)行K-means算法有相對較優(yōu)的數(shù)據(jù)點(diǎn)劃分正確率．

表5　不同初始中心選擇方式的k-means算法性能比較

5．3．3算法的適用性說明

上文中的仿真數(shù)據(jù)集和真實(shí)數(shù)據(jù)集在網(wǎng)格空間上的密度分布都是每個(gè)子類中有唯一的密度最大處，轉(zhuǎn)換成函數(shù)優(yōu)化問題是一種單個(gè)子類的網(wǎng)格密度呈單峰分布的多極值函數(shù)優(yōu)化問題．量子諧振子算法［12］由于其高斯函數(shù)聚集收縮的特性導(dǎo)致其對于單峰的函數(shù)優(yōu)化問題有較好的效率，對于子類局部區(qū)域中有多個(gè)峰值的函數(shù)優(yōu)化問題效果不好．從而暗示了根據(jù)量子諧振子模型設(shè)計(jì)的CCSA-QHOM算法對于在網(wǎng)格空間上的每個(gè)子類的密度分布呈單峰特性的數(shù)據(jù)集的聚類問題效果較好，不適合處理均勻分布的數(shù)據(jù)集的聚類中心定位問題，如圖6所示．對于均勻分布的數(shù)據(jù)集等某一子類的局部區(qū)域中的多極值現(xiàn)象需要進(jìn)一步網(wǎng)格劃分或者進(jìn)行極值處理，即需要更進(jìn)一步的研究．

6　總結(jié)

CCSA-QHOM算法通過以量子諧振子模型中波函數(shù)從高能態(tài)到基態(tài)過程中的概率變化為理論模型來描述數(shù)據(jù)對象向聚類中心移動的過程，最終定位到密度局部最大的網(wǎng)格位置．該算法在合理的參數(shù)設(shè)置下，不需要先驗(yàn)知識給出實(shí)際的聚類個(gè)數(shù)，運(yùn)算過程中會自動聚為若干類．本文通過對三種具有顯著特征的數(shù)據(jù)集的實(shí)驗(yàn)研究，說明了CCSA-QHOM算法對于噪聲數(shù)據(jù)，類大小差別較大，密度多樣等數(shù)據(jù)類型在參數(shù)設(shè)置合理時(shí)都不太敏感，聚類中心定位較準(zhǔn)確．通過對真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)研究說明該方法能夠定位到離實(shí)際的聚合中心比較近的網(wǎng)格位置，從而說明量子諧振子模型收斂過程的有效性．通過對CCSA-QHOM算法所采用的數(shù)據(jù)集及運(yùn)算結(jié)果分析發(fā)現(xiàn):該算法較適合于網(wǎng)格空間上的每個(gè)子類的密度分布呈單峰特性的數(shù)據(jù)集的聚類問題，對于網(wǎng)格空間上密度分布相對均勻及發(fā)散分布的數(shù)據(jù)集不太適合．通過對該算法的原理及結(jié)果進(jìn)行分析發(fā)現(xiàn):該算法可以作為類似于K-means算法的需要選取初始聚類中心點(diǎn)的動態(tài)聚類算法的預(yù)處理過程，也可以用于對離群點(diǎn)的檢測等．

參考文獻(xiàn)

［1］徐利治．?dāng)?shù)學(xué)辭海(第四卷)［M］．山西太原:山西教育出版社，2002．444－447．

［2］Han J W，Micheline K．Data Mining Concepts and Techniques［M］．San Francisco: Morgan Kaufmann，2006．383 －464．

［3］孫吉貴，劉杰，趙連宇．聚類算法研究［J］．軟件學(xué)報(bào)，2008，19(1) : 48－61．Sun Ji-gui，Liu Jie，Zhao Lian-yu．Clustering algorithms research［J］．Journal of Software，2008，19(1) : 48－61．(in Chinese)

［4］Rana S，Jasola S，Kumar R．A boundary restricted adapti-ve particle swarm optimization for data clustering［J］．International Journal of Machine Learning and Cybernetics，2013，4(4) : 391－400．

［5］Ji He，Man Lan et al．Initialization of cluster refinement algorithms: A review and comparative study［A］．IEEE International Joint Conference on Neural Networks［C］．Budapest: IEEE，2004．1－6．

［6］Mac Q J．Some methods for classification and analysis of multivariate observations［A］．Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability［C］．Berkeley，CA: University of California Press，1967．281－297．

［7］Toy J T，Gonzalez R C．Pattern Recognition Principles ［M］．Massachusetts: Addison-Wesley，1974．

［8］Kaufman L，Rousseeuw P J．Finding Groups in Data: An Introduction to Cluster Analysis［M］．Hoboken NJ: John Wiley＆Sons，2009．

［9］Omran M，Salman A，Engelbrecht A P．Image classification using particle swarm optimization［A］．Proc of the 4th Asia-Pacific Conference on Simulated Evolution and Learning［C］．Singapore: 2002．18－22．

［10］Merwe D W，Engelbrecht A P．Data clustering usingparticle swarm optimization［A］．Proc of IEEE Congresson E-volution Computation［C］．Piscataway，NJ: IEEE，2003．215－220．

［11］Omran M，Salman A，Engelbrecht A P．Dynamic clustering using particle swarm optimization with application in unsupervised image classification［A］．Fifth World Enformatika Conference (ICCI 2005)［C］．Prague: Czech Republic，2005．199－204．

［12］王鵬，黃焱，任超，郭又銘．多尺度量子諧振子高維函數(shù)全局優(yōu)化算法［J］．電子學(xué)報(bào)，2013，41(12) :2468－247．Wang Peng，Huang Yan et al．Multi-scale quantum harmonic oscillator for high dimensional function global optimization algorithm［J］．Acta Electronica Sinica，2013，41 (12) : 2468－2473．(in Chinese)

［13］曾謹(jǐn)言．量子力學(xué)教程［M］．北京:科學(xué)出版社，2003．47－50．

［14］馮斌，須文波．基于粒子群算法的量子諧振子模型［J］．計(jì)算機(jī)工程，2006，32(20) : 18－21．Feng Bo，Xu Wen-bo．Quantum oscillator model of particle swarm system［J］．Computer Engineering，2006，32 (20) : 18－21．(in Chinese)．

［15］秦永波，王鵬，肖黎彬，江炳坤，任超，孟玉．量子諧振子蟻群算［J］．計(jì)算機(jī)應(yīng)用，2011，31(z2) : 54－69．Qin Yong-bo，Wang Peng，Xiao Li-bin et al．Ant colony optimization of quantum harmonic oscillators［J］．Journal of Computer Applications，2011，31 (z2) : 54－69．(in Chinese)

［16］Hand DJ，Vinciotti V．Choosing k for two-class nearest neighbor classifiers with unbalanced classes［J］．Pattern Recognition Letters，2003，24(9) : 1555－1562．

［17］Mc Callum A，Nigam K，Ungar L H．Efficient clustering of high-dimensional data sets with application to reference matching［A］．Proceedings of theSixth ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining［C］．New York: ACM，2000．169－178．

燕京京女，1989年生于河南安陽．碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘．

王鵬(通信作者)男，1975年生于四川樂山．教授，博士生導(dǎo)師，CCF高級會員，主要研究領(lǐng)域?yàn)椴⑿杏?jì)算，信號處理，智能算法．

Email: wp002005@163．com

Clustering Center Selecting Algorithm Based on Quantum Harmonic Oscillator Model

YAN Jing-jing1，3，WANG Peng2，F(xiàn)AN Jia-bing1，3，HUANG Yan1，3
(1．Chengdu Institute of Computer Application，Chinese Academy of Sciences，Chengdu，Sichuan 610041，China; 2．Parallel Computing Laboratory，Chengdu University of Information Technology，Chengdu，Sichuan 610225，China; 3．University of Chinese Academy of Sciences，Beijing 100049，China)

Abstract:This article puts forward a clustering center selecting algorithm based on quantum harmonic oscillator model (CCSA-QHOM)．The algorithm describes the way of data objects finding center of the cluster in clustering problem by taking the change of wave function’s probability in the process of high energy level to a lower energy level for theoretical model．It can quickly find the optimal number of clusters and cluster center，computing time has nothing to do with the size of the data set after the dataset being got in grid space．Experiments show that CCSA-QHOM is more suitable for processing the clustering center selection question of dataset in which grid density distribution of each subclass haves a single peak characteristic．

Key words:cluster center; quantum harmonic oscillator; number of clusters; grid; peak characteristic

作者簡介

基金項(xiàng)目:國家自然科學(xué)基金(No．60702075) ;廣東省科技廳高新技術(shù)產(chǎn)業(yè)化科技攻關(guān)項(xiàng)目(No．2011B010200007) ;四川省青年科學(xué)基金(No．09ZQ026-068) ;成都市科技局創(chuàng)新發(fā)展戰(zhàn)略研究項(xiàng)目(No．11RXYB016ZF)

收稿日期:2014-07-01;修回日期: 2014-12-06;責(zé)任編輯:藍(lán)紅杰

DOI:電子學(xué)報(bào)URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．023

中圖分類號:TP301.6

文獻(xiàn)標(biāo)識碼:A

文章編號:0372-2112 (2016) 02-0405-08