基于改進和聲算法的有序樣本聚類及其應(yīng)用

李曉康

(陜西理工學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院， 陜西 漢中 723000)

[摘要]標準和聲算法只能解決連續(xù)型優(yōu)化問題，而有序樣本聚類屬于離散型優(yōu)化問題。將Fisher算法和和聲算法相結(jié)合，提出一種改進和聲算法，使之能夠用于離散型優(yōu)化問題，并利用其對有序樣本進行分類。數(shù)值仿真實驗結(jié)果表明，該算法分類結(jié)果符合實際。結(jié)論表明改進和聲算法是一種全局最優(yōu)算法，分類結(jié)果優(yōu)于Fisher算法。

[關(guān)鍵詞]和聲算法；有序樣本；自相關(guān)系數(shù)；離差平方和；聚類

[文章編號]1673-2944(2015)03-0065-06

[中圖分類號]TP301.6

收稿日期：2014-12-31

基金項目：陜西省教育廳科學(xué)研究計劃項目(2013JK0616)；陜西理工學(xué)院科研基金資助項目(SLGKY14-19)

作者簡介：李曉康(1973—)，男，陜西省漢中市人，陜西理工學(xué)院講師，碩士，主要研究方向為應(yīng)用概率統(tǒng)計。

聚類分析是研究分類的數(shù)理統(tǒng)計方法。聚類的關(guān)鍵是定義一個合適的距離，不同的距離定義會產(chǎn)生不同的聚類結(jié)果，常用的有最短距離法、最長距離法、重心法、類平均法、離差平方和法等[1]。聚類方法已廣泛應(yīng)用于金融、經(jīng)濟領(lǐng)域，取得了較好的結(jié)果[2-4]。

有序樣本是指按照時間或其它指標排列的一組樣本，在分類過程中不允許打亂原有的樣本順序，只能將相鄰的樣本聚為一類。有序樣本聚類問題求解采用的算法主要有：系統(tǒng)聚類法、傳統(tǒng)的Fisher算法、遺傳算法等。

和聲搜索(Harmony Search，HS)算法[5]是一種新的啟發(fā)式優(yōu)化算法，通過模擬音樂家創(chuàng)作音樂和調(diào)節(jié)和聲的過程反復(fù)調(diào)整和聲記憶庫中的解，從而完成優(yōu)化過程。HS全局搜索能力強，并且結(jié)構(gòu)簡單，很容易在各種軟件和硬件中實現(xiàn)，引起很多科學(xué)研究者和工程設(shè)計人員的關(guān)注，近年來，已經(jīng)廣泛應(yīng)用于實踐優(yōu)化問題中[6-9]。

本文在Fisher算法的基礎(chǔ)上，引進樣本一階自相關(guān)系數(shù)為分類指標，將有序樣本聚類問題轉(zhuǎn)化為一個離散型優(yōu)化問題，對標準和聲算法進行改進，利用和聲搜索算法的全局最優(yōu)求解能力，在不打亂原有樣本順序的條件下，對有序樣本進行分類，并確定最終分類數(shù)及分類結(jié)果。所得結(jié)果不同于Fisher算法的近似解，為全局最優(yōu)解。

1　Fisher算法與和聲算法

1.1　Fisher算法

Fisher算法的思想為二分法，即首先將所有樣本分為兩類，再將其中一類(包含2個以上樣本)分為兩類，如此遞推。故其給出的是局部最優(yōu)解。

1.2　自相關(guān)系數(shù)

傳統(tǒng)聚類的指標是樣本間的距離，常用的有絕對值距離、歐氏距離、馬氏距離等。有序樣本的聚類是按相鄰樣本間的相依關(guān)系，在不打亂原有樣本次序的前提下，將相依關(guān)系最強的相鄰樣本聚為一類，依次進行，直到所有樣本聚為一類。但是，傳統(tǒng)的距離并不能夠真實反映樣本間的相依關(guān)系強弱，如有4個有序樣本，其樣本觀測值分別為1、2、101、102，若按照絕對值距離，則1、2號樣本的距離為1、3、4號樣本的距離也為1，顯然，3、4號樣本的相依關(guān)系要強于1、2號樣本。可見，傳統(tǒng)的距離并不能真實反映樣本間的相依關(guān)系。受物理中相對誤差概念的啟發(fā)，可考慮定義描述相鄰樣本間相依關(guān)系的相對指標。

一階自相關(guān)系數(shù)反映前后樣本相依關(guān)系程度，即：

(1)

1.3　標準和聲算法

標準和聲算法的基本思想：(1)產(chǎn)生隨機和聲記憶庫；(2)利用和聲調(diào)節(jié)規(guī)則產(chǎn)生新和聲；(3)更新操作，即新和聲優(yōu)于和聲記憶庫中最差和聲時，用新和聲進行替換，否則重新產(chǎn)生新和聲，直至滿足終止條件。

標準的和聲搜索算法主要用于求解實數(shù)優(yōu)化問題，而有序樣本聚類問題是離散組合優(yōu)化問題，還要求解元素具有有序性。

2　改進和聲算法

對于有序樣本的聚類問題，可以轉(zhuǎn)換為一個全局優(yōu)化問題，模型如下：

(2)

該模型要求找到一個最佳的k值及一個有序樣本分割點(j0，j1，j2，…，jk)，其中，j0=1，jk=L(L是樣本個數(shù))，且j0

該問題是一個組合優(yōu)化問題，但不同于傳統(tǒng)組合優(yōu)化問題的是該問題要求分割點必須有序。因此，本文提出一種解決有序樣本聚類問題的改進和聲搜索算法，算法流程如圖1所示。

圖1　改進和聲搜索算法流程圖

在流程圖1中，Hnew表示新產(chǎn)生的和聲，HM(a，i)表示從HM中隨機選取的第a個和聲的第i維。HM(idxworst，：)表示和聲記憶庫(HM)中最差和聲向量，idxworst是最差和聲在和聲記憶庫HM中的索引。

本文算法具體步驟如下：

(1)初始化算法參數(shù)，設(shè)置HMS=15，HMCR=0.98，PAR=0.3；

(2)和聲記憶庫初始化，參與隨機算法進行初始化，為了保證分割點有序，將其從小到大進行排序；

(3)根據(jù)適應(yīng)值函數(shù)(2)式計算個體的適應(yīng)值；

(4)產(chǎn)生一個新個體；

(5)判斷是否滿足終止條件，如果是，輸出最優(yōu)結(jié)果，否則，轉(zhuǎn)至(4)繼續(xù)。

實現(xiàn)該算法的源程序代碼如下：

Hnew(0)=1；

Hnew(k)=n；

For i=1 to k-1

If Rand

Hnew(i)=HM(a，i)，a∈{1，2，…，HMS}

If Rand

Hnew(i)=Round(HM(a，i)+(rand-1)*2)；//在當前點左右進行微調(diào)

EndIf

Else

Hnew(i)=Rand(Hnew(i-1)，n)；//在Hnew(i-1)和n之間隨機產(chǎn)生一個點

EndIf

EndFor

Hnew=sort(Hnew)；//進行排序修正，使得分割點有序

If Hnew<=HM(idxworst，：)

HM(idxworst，：)=Hnew；

End

不同于Fisher算法的是，改進HS算法是基于目標函數(shù)進行全局優(yōu)化，并不依賴于前面的分解結(jié)果。由此可見，改進和聲搜索算法通過對所有樣本點進行綜合判斷，進行全局搜索，故能夠獲得全局最優(yōu)解。

3　算例分析

以下給出兩個基于和聲算法的有序樣本聚類的算例。

3.1　一維有序樣本聚類

為研究兒童的生長規(guī)律，統(tǒng)計男孩從出生至11歲每年平均增加的體重，數(shù)據(jù)見表1。分析表中數(shù)據(jù)，希望從中找出兒童體重變化規(guī)律，將相鄰的某些年齡段分為一個階段，得出兒童體重變化各階段特征。為此，利用有序樣本聚類方法對其分類。

表1　各不同年齡段兒童體重增重數(shù)據(jù)

首先，做出其數(shù)據(jù)散點圖如圖2所示?？梢钥闯觯簝和诓煌挲g階段的增重具有明顯變化，故可根據(jù)在不同年齡段的增重特征將其分為幾個階段。所以可采用有序樣本的分類方法處理。

圖2　年齡與體重增重關(guān)系圖

按照(1)式定義，對所給數(shù)據(jù)，計算其一階自相關(guān)系數(shù)，結(jié)果如表2所示。采用(1)式定義相鄰樣本間的距離，利用Fisher算法和本文提出算法，對本例樣本的聚類過程如表3所示。

表2　相鄰樣本一階自相關(guān)系數(shù)

表3　兩種算法的分類結(jié)果

注：括號內(nèi)數(shù)字為每一類包含的樣本序號，如：k=3時，分為3類：{1}、{2，3，4，5，6}、{7，8，9，10，11}。

改進和聲算法各次分類的聚類距離(自相關(guān)系數(shù))和離差平方和e[P(11，k)](k=1，2，…，10)如表4所示，圖形如圖3、圖4。

表4　改進和聲算法各次聚類距離(自相關(guān)系數(shù))和離差平方和

圖3　各次聚類的自相關(guān)系數(shù)　　　　　　　圖4　各次聚類的離差平方和

比較兩種分類方法的過程和結(jié)果可以看出：(1)改進和聲算法的分類過程是“分”，即每次將有序樣本在某點“斷開”，而Fisher算法的分類過程是“合”，即每次將距離最近的相鄰樣本“聚攏”；(2)Fisher算法的后一次聚類是在前一次的基礎(chǔ)上，而改進和聲算法的后一次“分”與前一次結(jié)果無關(guān)，是在全局范圍內(nèi)重新搜索，故給出的是全局最優(yōu)解。

最佳分類數(shù)的確定一方面依賴于專業(yè)知識，根據(jù)兒童生長發(fā)育規(guī)律及特點，可分為以下幾個階段：出生后的迅速生長階段0~2歲，平穩(wěn)生長階段3~7歲，二次發(fā)育階段8~11歲；另一方面，可結(jié)合分類過程的自相關(guān)系數(shù)及離差平方和的變化規(guī)律確定分類數(shù)。綜合以上兩方面，由圖3和圖4可以看出，經(jīng)過7次分類(類的個數(shù)為4)，類間的自相關(guān)系數(shù)和離差平方和均有比較明顯的增加，故確定的最優(yōu)分類數(shù)為4，最終分類結(jié)果為：1，{2，3，4}，{5，6，7}，{8，9，10，11}。分類結(jié)果符合兒童生長發(fā)育特點和規(guī)律，分類結(jié)果合理。

3.2　多維有序樣本聚類

表5　某路段路面性能檢測數(shù)據(jù)

公路養(yǎng)護單元xi(i=1，2，…，n)是一多維向量，每一維代表該單元的一個屬性。現(xiàn)考慮5種路面屬性：路面結(jié)構(gòu)性能(PCI)、路面功能性能(RQI)、結(jié)構(gòu)承載能力(SSI)、路面安全性能(SFC)、抗車轍指數(shù)(ARI)。每一養(yǎng)護單元可用1×5向量xi=(xi1，…，xi5)(i=1，2，…，n)表示，其中xij(j=1，2，…，5)表示第i路段的第j項指標值。其原始數(shù)據(jù)如表5[10]所示。

此問題的8個路段為連續(xù)有序路段，相鄰路段具有一定程度的相似性，在分類時，不允許打亂原有順序，只能將相鄰路段分為一類。對其按照如上介紹的和聲算法進行有序樣本聚類，聚類結(jié)果如表6所示。

對于本例，兩種分類結(jié)果一致。在實際應(yīng)用中，結(jié)合公路路面養(yǎng)護要求，通常將路段分為3個類型，結(jié)合本文算法結(jié)果，最終分類如下。第一類：{1，2，3}，此類為路面性能較好路段，各路面性能指標較好；第二類：{4，5}，此類為路面性能中等路段，各路面性能指標中等；第三類：{6，7，8}，此類為路面性能較差路段，各路面性能指標較差。

表6　兩種算法的分類結(jié)果

4　結(jié)　論

將有序樣本的Fisher算法與傳統(tǒng)的系統(tǒng)聚類法相結(jié)合，引入樣本一階自相關(guān)系數(shù)描述相鄰樣本的相依關(guān)系，相對傳統(tǒng)樣本間的距離，能夠更好地描述相鄰樣本間的相依關(guān)系，以此作為分類指標，利用和聲算法的全局最優(yōu)搜索能力求解分類過程，所得結(jié)果與傳統(tǒng)Fisher算法相比，為全局最優(yōu)解。運用各次分類的離差平方和確定最終分類數(shù)及分類結(jié)果，能夠得到更加合理的分類結(jié)果。

[參考文獻]

[1]張堯庭，方開泰.多元統(tǒng)計分析引論[M].北京：科學(xué)出版社，1999：444-452.

[2]嚴廣松，路允芳.多維有序樣本的聚類方法研究[J].統(tǒng)計與決策，2008(4)：29-30.

[3]毛定祥.基于因子分析與有序樣本最優(yōu)分割的商業(yè)銀行盈利性流動性安全性綜合評價[J].上海大學(xué)學(xué)報：自然科學(xué)版，2007，13(1)：105-110.

[4]蘇慶利.有序樣本聚類法在經(jīng)濟分析中的應(yīng)用[J].統(tǒng)計研究，2006(7)：76-77.

[5]PAN Q K，SUGANTHAN P N，LIANG J J，et al.A local-best harmony search algorithm with dynamic subpopulations[J].Engineering Optimization，2010，42(2)：101-117.

[6]PAN Q K，SUGANTHAN P N，TASGETIREN M F，et al.A self-adaptive global best harmony search algorithm for continuous optimization problems[J].Applied Mathematics and Computation，2010，216(3)：830-848.

[7]PARIKSHIT Y，RAJESH K，PANDA S K，et al.An Intelligent Tuned Harmony Search algorithm for optimization[J].Information Sciences，2012，196(1)：47-72.

[8]DAS S，MUKHOPADHYAY A，ROY A，et al.Exploratory Power of the Harmony Search Algorithm：Analysis and Improvements for Global Numerical Optimization[J].Systems，Man，and Cybernetics，Part B：Cybernetics，2011，41(1)：89-106.

[9]TUO Shou-heng，YONG Long-quan.An improved harmony search algorithm with chaos[J].Journal of Computational Information Systems，2012，8(10)：4269-4276.

[10]王佳，胡列格.養(yǎng)護路段的有序聚類劃分[J].系統(tǒng)工程，2008，26(11)：71-74.

[責任編輯：謝 平]

Cluster of ordered sample and its application based on harmony search algorithm

LI Xiao-kang

(School of Mathematics and Computer Science， Shaanxi University of Technology，

Hanzhong 723000， China)

Abstract:The standard harmony search algorithm can only solve continuous optimization problems，whereas the ordered sample cluster belongs to discrete optimization problems. Combining the Fisher algorithm and the harmony search algorithm，an improved harmony search algorithm is proposed to be used for discrete optimization problems，and for classifying ordered sample. The experimental results show that classification result is consistent with the actual. The conclusion shows that the improved harmony search algorithm is a global optimal algorithm and its result is better than the Fisher algorithm.

Key words:harmony search algorithm；ordered sample；self-correlation coefficient；square deviation；cluster