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

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

李曉康

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

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

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

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

[中圖分類(lèi)號(hào)]TP301.6

收稿日期：2014-12-31

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

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

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

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

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

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

1　Fisher算法與和聲算法

1.1　Fisher算法

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

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

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

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

(1)

1.3　標(biāo)準(zhǔn)和聲算法

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

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

2　改進(jìn)和聲算法

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

(2)

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

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

圖1　改進(jìn)和聲搜索算法流程圖

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

本文算法具體步驟如下：

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

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

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

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

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

實(shí)現(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)；//在當(dāng)前點(diǎn)左右進(jìn)行微調(diào)

EndIf

Else

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

EndIf

EndFor

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

If Hnew<=HM(idxworst，：)

HM(idxworst，：)=Hnew；

End

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

3　算例分析

以下給出兩個(gè)基于和聲算法的有序樣本聚類(lèi)的算例。

3.1　一維有序樣本聚類(lèi)

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

表1　各不同年齡段兒童體重增重?cái)?shù)據(jù)

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

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

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

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

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

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

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

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

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

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

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

3.2　多維有序樣本聚類(lèi)

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

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

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

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

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

4　結(jié)　論

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

[參考文獻(xiàn)]

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

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

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

[4]蘇慶利.有序樣本聚類(lèi)法在經(jīng)濟(jì)分析中的應(yīng)用[J].統(tǒng)計(jì)研究，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)護(hù)路段的有序聚類(lèi)劃分[J].系統(tǒng)工程，2008，26(11)：71-74.

[責(zé)任編輯：謝 平]

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