王華秋，羅江，Michael GERNDT，Ventsislav PETKOV

1.重慶理工大學計算機學院，重慶 400054

2.慕尼黑工業(yè)大學信息系I10研究所，德國慕尼黑D- 85748

特征選擇的和聲模糊聚類研究與應用

王華秋1，羅江1，Michael GERNDT2，Ventsislav PETKOV2

1.重慶理工大學計算機學院，重慶 400054

2.慕尼黑工業(yè)大學信息系I10研究所，德國慕尼黑D- 85748

1 引言

用于高性能計算機的性能分析工具可以幫助使用者寫出高效的代碼。這些工具能夠提供程序性能評測值，并能發(fā)現(xiàn)一些瓶頸。瓶頸是指在程序執(zhí)行時，運行時間由于無效資源的占用而浪費掉了。只要識別出瓶頸，開發(fā)者就可以修改程序以提高運行效率。正如現(xiàn)如今有許多并行計算硬件和并行編程語言一樣，性能分析工具也是層出不窮，其中有代表性的是如下幾種：Paradyn、TAU、Periscope、Vampir、KOJAK、SCALASCA、mpiP。

聚類機制為這些工具提供了一種基本的多變量統(tǒng)計分析的方法，所有處理器的Performance和Region這兩個屬性對應的Severity值被提取出來，組成一個由處理器個數(shù)為行，Severity為列的高維矩陣。使用聚類算法對這些處理器進行分類，以檢測每一類處理器在不同代碼區(qū)域出現(xiàn)性能瓶頸的概率分布，以便對每一類處理器進行合理的資源調(diào)度。用于GENE代碼分析的處理器有1 024個，這些處理器產(chǎn)生的性能瓶頸維度有39列之多，這樣會產(chǎn)生1 024×39的矩陣。為了評價這些處理器的性能，對這樣的性能矩陣進行劃分，使其產(chǎn)生少數(shù)具有相似性能的處理器集合將是非常有意義的，聚類后的處理器將有利于發(fā)現(xiàn)隱藏在巨大數(shù)據(jù)集后的并行系統(tǒng)整體運行趨勢。

在諸多劃分、層次、密度、網(wǎng)格等聚類算法中，F(xiàn)CM聚類是最常用劃分聚類算法，它采用梯度下降的方法尋找最優(yōu)解，本質(zhì)上是一種局部搜索技術(shù)。對初值敏感及容易陷入局部極小的缺陷，使得該方法只適用于對均勻分布的團狀數(shù)據(jù)集聚類，對分布復雜的故障數(shù)據(jù)無法正確處理，而且FCM對所有特征采用相同權(quán)重，這樣處理并不合理，由于未對特征加權(quán)，就無法突出某些屬性特征對聚類的主導影響，使聚類效果受到了次要屬性特征的干擾，而這種缺陷在高維數(shù)據(jù)中尤為明顯。因此，這也成為了許多啟發(fā)式搜索算法首選的優(yōu)化目標，這些啟發(fā)式搜索算法已廣泛地用于聚類中心的發(fā)現(xiàn)中，并能在問題域內(nèi)找到所有可能解，如果算法運用得當就能避免陷入局部最優(yōu)解。例如，克隆選擇[1]、蟻群優(yōu)化[2]和粒子群優(yōu)化[3]。和聲算法是Geem提出的一種由音樂靈感激發(fā)的優(yōu)化算法[4]，受到廣泛關(guān)注。和聲搜索算法已經(jīng)用于許多工程和科學領(lǐng)域，比如：圖像分割[5]、Web文本聚類[6]、水處理[7]。本文使用和聲搜索算法實現(xiàn)了快速準確的聚類，無論數(shù)據(jù)分布、形狀、大小如何，性能好的搜索劃分算法都可以對其聚類。

通過對和聲搜索算法的研究，發(fā)現(xiàn)調(diào)音概率par和調(diào)音量bw都是憑經(jīng)驗或隨機設(shè)定的，而且在算法收斂過程中沒有變化。事實上，這兩個參數(shù)對算法收斂性能的影響比較大，特別是在運行的后期，原始的和聲搜索算法沒有對其加以關(guān)注，不利于算法快速收斂到全局最優(yōu)。因此，本文對和聲搜索算法進行改進之處就在于動態(tài)調(diào)整調(diào)音概率par和調(diào)音量bw，保證和聲算法快速收斂到全局最優(yōu)，有效地避免陷入局部極小。

眾所周知，每個都數(shù)據(jù)包含一定數(shù)量的維度（或者稱為屬性），聚類算法就是將這些多維數(shù)據(jù)進行劃分，在劃分之前并不知道需要劃分成為幾部分，只是將每一類內(nèi)部變量盡量聚集在一起，而類與類之間的距離盡量遠離，兩點之間的差異用相似度或者距離計算。聚類的這種不確定性正是在于聚類學習是無監(jiān)督的過程。

基本的劃分算法認為所有的維對于聚類同等重要，但事實上，一些維存在冗余、無關(guān)，甚至容易產(chǎn)生誤導的異常點。因此特征選擇技術(shù)出現(xiàn)了，這是一種用于高維數(shù)據(jù)聚類的最佳特征子集選擇技術(shù)[8]。

特征選擇不僅提高了聚類的性能，而且簡化了聚類模型。特征選擇一般是在聚類之前完成的過程，但是也有一些算法將其集成于聚類算法中，即在聚類的同時進行特征選擇。文獻[8]和[9]就是將特征選擇和EM聚類結(jié)合在一起，在其影響下，文獻[10]提出了一種利用和聲搜索算法的聚類和特征選擇同步進行的方法。該方法將特征選擇作為和聲搜索聚類過程的一部分，每次搜索的目標不僅包括聚類中心，還包括被選擇出來的屬性（維），而且為了獲得最佳的聚類中心數(shù)量，每次搜索需要不斷改變聚類的中心數(shù)量。這種集成模式的搜索采用的評價函數(shù)則是聚類誤差和屬性（維）相對中心的偏差兩部分之和。這些改進的確提高了劃分聚類的性能，但是同時帶來了一些問題：

（1）算法復雜度較高，隨機的聚類中心和隨機的特征屬性的組合將是非常龐大的，這對于高維度大數(shù)據(jù)而言，其算法復雜度是可想而知的。

（2）性能評價函數(shù)不太合理，將聚類誤差和屬性偏差結(jié)合在一起不利于評價總誤差究竟是由于聚類中心數(shù)量不適當而帶來的誤差，還是由于屬性特征選擇不合理而帶來的偏差，從而造成每次迭代無法正確調(diào)整三個目標值：聚類中心數(shù)、聚類中心、屬性維度。這將對算法的準確度產(chǎn)生不可忽視的影響。

以上的做法是對高維數(shù)據(jù)的屬性（特征）進行選擇，沒有被選上的屬性將被忽略或刪除，進一步，有研究人員提出屬性加權(quán)的思想對特征選擇進行泛化，即為每一維設(shè)置一個0到1之間的權(quán)值，而不是直接保留或刪除某些屬性（維）。換句話說，如果某一屬性的特征比較明顯，那么它的權(quán)值就較高，從而對聚類結(jié)果的影響就較大；反之，特征不顯著，則權(quán)值較小，而影響較小。這樣看來，特征選擇就是為每一維設(shè)置合理的權(quán)值。近年來，許多研究人員致力于研究這種特征加權(quán)的方法以提高聚類質(zhì)量。Huang[11]提出了一種用于K-means的特征屬性自動加權(quán)的機制，其利用迭代公式不斷修正權(quán)值，而K-means算法的有效性并沒有被影響。然而，該方法需要使用者主觀指定一些參數(shù)值，而且其獲得的權(quán)值無法顯著區(qū)分屬性是否具有代表性和不相關(guān)性。文獻[12]提出了用優(yōu)化的方法對屬性進行加權(quán)，首先測量不同特征屬性的分散度，然后構(gòu)造了凸K-means算法以決定最優(yōu)權(quán)值，同時保證簇內(nèi)部平均分散度最小以及簇之間的平均分散度最大。而在實踐中，對于所有屬性進行加權(quán)并不適合高維數(shù)據(jù)聚類。Friedman[13]提出了COSA方法用于對子屬性進行層次聚類，對于不同的簇類，COSA聚類方法構(gòu)造了一個非凸優(yōu)化目標函數(shù)為D×N個屬性分配各自的權(quán)值，但是求解這個優(yōu)化函數(shù)需要面臨巨大的算法復雜度。Mohamed[14]在MRI圖像分割的應用中，在傳統(tǒng)的FCM算法的基礎(chǔ)上改進了聚類目標函數(shù)，以彌補圖像像素強度的不均勻性。

根據(jù)以往研究的經(jīng)驗，結(jié)合需要解決的問題，提出了一種采用改進的和聲搜索模糊聚類的MHS-FCM算法。本文算法克服了文獻[10]算法的那兩點問題，而且采用一種基于統(tǒng)計學的特征屬性加權(quán)的方法區(qū)別各個維在聚類中的不同作用，而不是忽略某些屬性維，采用評價函數(shù)對不同的聚類中心個數(shù)進行評價，從而保證算法收斂時能夠得到最佳聚類中心。

2 算法思路

按照前文的論述，要解決的問題有三點：（1）特征屬性的加權(quán)，即數(shù)據(jù)維加權(quán)；（2）采用改進的和聲搜索算法進行數(shù)據(jù)聚類；（3）選擇最優(yōu)的聚類中心數(shù)。因此把算法分為三步完成：

步驟1在聚類之前先進行特征屬性的加權(quán)。任何一維的數(shù)據(jù)如果過于集中，數(shù)據(jù)之間失去了區(qū)別，就不利于聚類了，這樣的維所代表的屬性就應該具有較小的權(quán)值；反之，如果這一維數(shù)據(jù)比較散亂，數(shù)據(jù)之間便于區(qū)分，那么這一維對聚類結(jié)果影響較大，應該分配較大的權(quán)值。本文就是按照這樣的思路對每一維屬性進行加權(quán)。

步驟2利用和聲搜索算法計算聚類中心。聚類評價函數(shù)值作為和聲算法的適應度，并采用一種新的調(diào)音概率公式改進和聲算法，不斷調(diào)整和聲庫直到算法收斂，直至聚類評價函數(shù)值的改變量小于要求或者達到迭代次數(shù)。

步驟3選擇最優(yōu)的聚類中心數(shù)。不斷改變聚類中心數(shù)，利用步驟2計算其聚類中心和評價函數(shù)值，選擇評價函數(shù)值最小對應的聚類中心作為最后的輸出。

3 基于維度加權(quán)的特征選擇

現(xiàn)已知樣本：

λki代表了一個是否和其他數(shù)據(jù)沒有顯著性區(qū)別的分界值。

規(guī)則1如果Rki＞λki，那么該維的第j個數(shù)據(jù)就和其他數(shù)據(jù)沒有顯著區(qū)別，因此第i維數(shù)據(jù)的Samenessi就增加一個計數(shù)。

這樣就是可以對每一維進行特征選擇了，根據(jù)算法思路，本文采用如下方式對每一維屬性進行加權(quán)。

其中，i=1，2，…，d，這樣wi就代表了第i維對于聚類的權(quán)值；Samenessi是第i維數(shù)據(jù)的趨于一致的數(shù)據(jù)的數(shù)量，TotalNumber是第i維數(shù)據(jù)的總數(shù)量；Deferencei代表了每一維的具有顯著差異的數(shù)據(jù)點個數(shù)，用Deferencei除以每一維數(shù)據(jù)的總數(shù)量則可以將每一維的數(shù)據(jù)差異性歸一化，使得所有維之間的權(quán)值具有可比性。

4 和聲搜索模糊聚類算法

和K-means、K-mediods、FCM等算法一樣，和聲搜索聚類算法同樣離不開聚類中心反復“迭代”，只不過這時的“迭代”演變成了“演奏”。

4.1 初始化和設(shè)置參數(shù)

（2）和聲搜索算法也有一些參數(shù)需要確定：和聲存儲庫的行數(shù)(HMS=20)，和聲存儲庫的列數(shù)(COL=k×d)，和聲存儲庫的選擇概率(HMCR=0.9)，調(diào)音概率(par=0.25)，隨機帶寬(bw=0.2)，音演奏次數(shù)（即迭代次數(shù)ITERATION=100）或者停止條件（適應度變化量小于一個小數(shù)DELTA＜0.01）。

（1）數(shù)據(jù)歸一化：由于各維數(shù)據(jù)代表的意義不同，造成量綱不統(tǒng)一，這樣不利于計算彼此的距離。由于在屬性加權(quán)時已經(jīng)對每一維的數(shù)據(jù)計算了標準差和平均值了，這里就采用Z-Score歸一化方法，由下式計算：

4.2 初始化和聲存儲庫

在這一步中，和聲存儲庫HM矩陣最初由有上界Uxj∈d和下界Lxj∈d限制的隨機數(shù)組成：

調(diào)用聚類質(zhì)量評價函數(shù)計算各行和音的適應度，得到適應度列向量F=[f1，f2，…，fHMS]T，記錄其中最佳和最差的適應度及其對應的和聲變量。

和聲存儲庫的作用就是在每次迭代時，由此庫產(chǎn)生出新的和聲變量，并根據(jù)這新變量不斷更新和聲存儲庫，使之收斂到全局最優(yōu)解。

4.3 演奏新的和音

在第一種方法中，第一個類中心的第一維變量c′11將從和音存儲庫的第一列向量中隨機選擇，以此類推可以得到其他中心的各維變量c′ij。

HMCR的變化范圍是0到1，一般為0.6～0.9之間。本文為0.9，這是決定是否從和音存儲庫HM中選擇性的變量的概率，換句話說，(1-HMCR)就是決定是否從上下限范圍內(nèi)隨機產(chǎn)生新的變量的概率。選擇操作如下：

對于每一個從和聲存儲庫中得到的變量還要決定是否調(diào)音，par就是初始調(diào)音的概率，一般為0.1～0.4之間。本文為0.25，概率(1-par)就是不需要調(diào)音的概率。調(diào)音操作如下：

所謂調(diào)音，就是在原來的變量的基礎(chǔ)上增加或減少一個隨機帶寬量bw。

上述三種方法產(chǎn)生的新的和音將被返回，并用于更新和音存儲庫。

4.4 改進的調(diào)音策略

調(diào)音是避免和聲算法出現(xiàn)“早熟”的重要措施，在最初的和聲算法中，并沒有對調(diào)音概率par和隨機帶寬bw做調(diào)整，因此需要很多次迭代才能調(diào)出一個不同于其他的和聲。當庫中的和聲趨同時，以一個遠大于通常的調(diào)音概率par′執(zhí)行一次操作，同時增加隨機帶寬量bw，這樣就能夠隨機產(chǎn)生新的音符，從而使整個和音庫擺脫“早熟”。

這樣的改進可以增加算法的隨機搜索的幾率，提高算法的全局收斂性，但是考慮到收斂時間會延長，因此par和bw的增加系數(shù)均不太大。

4.5 更新和音存儲庫

其中，參數(shù)m∈[1，+∞)是每一個模糊中心的加權(quán)指數(shù)，它決定著樣本在模糊類之間的隸屬程度。

再由隸屬矩陣產(chǎn)生新的聚類中心：

4.6 聚類性能評價

需要定義聚類質(zhì)量評價函數(shù)，這個評價應該體現(xiàn)聚類的原則：簇內(nèi)樣本盡量靠近該簇中心，簇和另一個簇盡量遠離。因此，把盡量小的簇內(nèi)距離除以盡量大的簇間距離作為評價函數(shù)（也稱為適應度）：

其中，C是聚類中心的集合，k是聚類中心的個數(shù)，Ci和Cj分是第i個和第j個聚類中心，Xi為樣本的每一行向量，n是樣本數(shù)量，樣本以模糊隸屬度uij歸屬于某些類。這樣聚類的目標就是通過和聲搜索到使得f(C，k)達到最小的C和k，C用向量的方式存儲，C=(C1，C2，…，Ck)=(c11，…，c1d，…，ck1，…，ckd)，例如：第一個聚類中心就是c11，c12，…，c1d，第k個聚類中心就是ck1，ck2，…，ckd。

用新的聚類中心調(diào)用聚類質(zhì)量評價函數(shù)計算其f′，如果新的和音向量在適應度上優(yōu)于和音存儲庫中的最差的向量，那么和音存儲庫就需要更新了，新的和音向量將取代那個最差的向量。如果這個新的向量同時也是和音存儲庫中最優(yōu)的，那么保存這個新向量的適應度為和音存儲庫的最佳適應度，這時的最佳適應度對應的變量就是最終聚集成為k個中心時的聚類結(jié)果。

4.7 檢查終止條件

如果滿足終止條件，結(jié)束聚類中心的搜索；否則，轉(zhuǎn)到4.3節(jié)。終止條件是：（1）迭代次數(shù)達到最大值；（2）評價函數(shù)值（適應度）的變化量小于限定值。

5 算法復雜度

為了分析整個算法的復雜性，給出算法的流程，如圖1。

把整個算法分為了若干段，每一段完成一定的功能，也消耗一定的時間，外部循環(huán)讓這些程序段反復迭代直至收斂。從內(nèi)部開始分析，和聲搜索聚類中心需要的時間為：R（初始化）+k（中心數(shù)）×d（維度）×S（式（4）的演奏+式（5）和（6）的調(diào)音）+F（式（3）的適應度計算n×k）+U（更新和聲庫）+P（式（7）和（8）的大概率調(diào)音），由于有了尋找最佳聚類中心數(shù)的過程，該算法重復了n/2-1次和聲搜索聚類，另外還有公式（1）的維度加權(quán)和公式（2）數(shù)據(jù)歸一化，因此對于整個聚類而言，整個算法復雜度為O(W+(n/2-1)× (R+k×d×S+n×k+U+P))。除了適應度公式之外，和聲搜索的這些公式都不太復雜，計算速度可以得到保證。

圖1 算法流程圖

6 算法收斂性

定理1 HSFC會收斂于全局最優(yōu)。

證明當新解的適應度優(yōu)于和聲庫中最差解的適應度時，和聲庫狀態(tài)發(fā)生轉(zhuǎn)換。下列三種概率影響了新解的產(chǎn)生：選擇和聲庫的概率pMemory=HMCR×(1-par)，調(diào)音的概率pPitch=HMCR×par，以及隨機選擇概率pRandom= (1-HMCR)。

因此，定義一個轉(zhuǎn)移矩陣P來記錄和聲庫中新解的概率變化值。設(shè)有一個隨機狀態(tài)轉(zhuǎn)移矩陣P=MC·PA·RC，其中MC是pMemory的中間轉(zhuǎn)換矩陣，PA是pPitch的中間轉(zhuǎn)換矩陣，RC是pRandom的中間轉(zhuǎn)換矩陣。

啟發(fā)式算法在迭代過程中始終保持了最優(yōu)解，確?？梢允諗坑谌肿顑?yōu)，因此轉(zhuǎn)移矩陣P是穩(wěn)定的。從和聲搜索算法的定義中可知，每次迭代中和聲庫都會更新最優(yōu)解，因此矩陣P轉(zhuǎn)移到任何全局最優(yōu)狀態(tài)的概率也會收斂到1，定理得證。

7 并行性能分析

為了分析和識別大規(guī)?？茖W計算中各處理器性能瓶頸。這里用回旋電磁數(shù)值實驗代碼（Gyrokinetic Electromagnetic Numerical Experiment，GENE）進行并行計算，GENE代碼通過迭代求解具有五維相空間的非線性回旋方程，用于識別電磁等離子聚變產(chǎn)生的渦流特征。GENE可以運行在擁有大量處理器的超級計算機上，代碼用MPI并行化的Fortran95實現(xiàn)。數(shù)據(jù)采集實驗在ALTIX超級計算機上進行，GENE代碼其中的1 024核中運行。通過測試可以收集GENE的不同代碼區(qū)域的各種MPI屬性值和可伸縮性，比如：節(jié)點性能、負載能力、信息組織方式等等。

首先將這些數(shù)據(jù)進行分析，對于處理器由其編號Process唯一確定，由于ID唯一表示了該CPU出現(xiàn)性能瓶頸的名稱，而RegionID則唯一標示了GENE代碼中出現(xiàn)性能瓶頸的區(qū)域位置，ID和RegionID的結(jié)合就可以確定GENE的哪一部分代碼運行時出現(xiàn)了什么樣的性能問題，而嚴重程度就是Severity。因此上述XML文件中，需要提取出來進行用于聚類的屬性為：Process，ID，RegionID，Severity。對這些屬性進行構(gòu)造，就是由給定的屬性構(gòu)造和添加新的屬性，以有利于聚類。比如，根據(jù)屬性ID和RegionID可以構(gòu)造Performance屬性。通過這種組合屬性，屬性構(gòu)造可以發(fā)現(xiàn)關(guān)于數(shù)據(jù)屬性間聯(lián)系的丟失信息，這對知識發(fā)現(xiàn)是有用的。于是構(gòu)建了如表1的1 024行39列的數(shù)據(jù)矩陣Processor_ Performance。

表1 性能分析數(shù)據(jù)

利用這些數(shù)據(jù)對這1 024個處理器進行聚類分析，把本文的HSFC和FCM、PSO聚類、文獻[6]和文獻[10]算法進行比較，其中PSO和FCM聚類時根據(jù)相關(guān)文獻的經(jīng)驗指定分類數(shù)和參數(shù)。將瓶頸性能近似的處理器歸為同一類，聚類的結(jié)果就是這1 024個處理器被自動分為8類（如表2）。

表2 并行性能聚類結(jié)果

從上面的比較可以看出，本文這種算法聚類質(zhì)量比較高，而且耗時較少。雖然FCM算法速度也比較快，但是誤差較大。因此采用本文的算法進行并行處理器性能聚類。

圖2中的橫坐標是處理器的編號，縱坐標是類別。根據(jù)這樣的聚類，可以重新分配GENG的代碼區(qū)域到處理器上，取得更好的計算性能。

圖2 處理器聚類結(jié)果

例如：p1，p20，p140，p230，p663，p915，…，被歸為一類C1。

定義4Ci_Processor={Processorj}，其中j是屬于Ci類的處理器下標。

并行性能分析就是對于每一個處理器聚類組，找出對其具有較高嚴重程度Severity值的性能瓶頸集合。某處理器組的性能瓶頸集的計算需要借助Processor_Performance矩陣。根據(jù)數(shù)理統(tǒng)計中值理論，在該矩陣中某性能瓶頸Performancej在某處理器組Ci的Severity權(quán)值由下面公式計算。

定義5

其中，表示某處理器組Ci中處理器的個數(shù)；W(Performancej，Processor)表示Processor在Performancej性能上的嚴重程度Severity。由此，可以計算出每個性能瓶頸對于每個處理器組的權(quán)值。顯然，對每一處理器組而言，那些與之具有較高權(quán)值的性能瓶頸就構(gòu)成了針對它的并行性能分析結(jié)果集。對于前面所述回旋電磁數(shù)值實驗的Processor_ Performance矩陣及其ProcessorCluster聚類陣，利用權(quán)值計算公式，計算其權(quán)值矩陣ProcessorCluster-PerformanceWeight，結(jié)果如表3。

表3 并行性能加權(quán)聚類結(jié)果

設(shè)Severity權(quán)值的閥值S=5.00，則處理器組C1的性能分析結(jié)果集為{（7-511，7-689），（7-511，7-1051）}，C2的性能分析結(jié)果集為{（7-511，12-535），（7-511，7-689）}，C3的性能分析結(jié)果集為{（7-511，12-535）}，…

舉例解釋一下C1性能分析結(jié)果，按照Severity權(quán)值排序，這一類主要的瓶頸問題如下。

（1）Severity權(quán)值8.50：CALL_REGION程序段（7-511）出現(xiàn)了Excessive MPI communication time性能問題（7-689）；

（2）Severity權(quán)值6.00：CALL_REGION程序段（7-511）出現(xiàn)了Excessive MPI time in receive due to late sender性能問題（7-1051）。

定義6Ci_PerformanceWeight={Performancej}，其中j是Ci類包含的所有性能瓶頸下標。

在并行程序運行時，首先需要根據(jù)處理器信息找出其所屬的性能瓶頸組，然后參照該組的性能分析結(jié)果集。掌握了這些同一類處理器的性能瓶頸特征，程序管理員或開發(fā)者就可以預先知道某處理器可能會出現(xiàn)的性能瓶頸，從而及時重新分配任務(wù)或調(diào)度處理器，將可能出現(xiàn)的性能瓶頸防患于未然。

規(guī)則2IfProcessorj∈CithenProcessorj具有Performancej性能瓶頸。

比如：已知p1，p20，p140，p230，p663，p915，…被歸為一類C1，處理器p1可能僅僅在CALL_REGION程序段（7-511）出現(xiàn)了Excessive MPI communication time性能問題（7-689）。但是由于C1類的處理器普遍會出現(xiàn){（7-511，7-689），（7-511，7-1051）}這兩類瓶頸問題，因此，可以推斷處理器p1也會在CALL_REGION程序段（7-511）出現(xiàn)了Excessive MPI time in receive due to late sender性能問題（7-1051），程序員可以提前做出調(diào)整，以減少這種瓶頸帶來的不利影響。

8 結(jié)束語

將隨機啟發(fā)式搜索算法之一的和聲搜索算法運用于聚類中，僅僅保留了聚類的評價函數(shù)，改變了聚類的方式，從而提高了聚類的質(zhì)量，本文嘗試對其進行一些改進。和其他的算法相比，此HSFC的模糊聚類有如下優(yōu)點：

（1）通過循環(huán)地改變聚類中心數(shù)量，HSFC根據(jù)這些不同的聚類中心數(shù)量得到聚類中心點及其評價函數(shù)，取其評價函數(shù)最小的一組聚類中心作為算法最終的結(jié)果，從而能夠自動找到正確或合理的聚類中心數(shù)。

（2）通過特征屬性加權(quán)，改變了每一維對聚類結(jié)果的影響，提高了聚類準確性。

（3）在算法運行后期，采用大概率調(diào)音保證了算法不會收斂到局部極小。

本文算法用于并行程序計算過程中的性能分析，將高維的性能瓶頸數(shù)據(jù)進行聚類，將若干處理器按照性能瓶頸的類型和嚴重程度進行歸類，然后對每一類處理器組的性能瓶頸值進行加權(quán)并根據(jù)閾值進行篩選，最終得出每一類處理器組最有可能出現(xiàn)的性能瓶頸類型。這樣程序員可以針對每個處理器所屬的類別預知其可能出現(xiàn)的所有性能瓶頸，從而及時做出任務(wù)調(diào)整和處理器調(diào)度，提高并行程序運行效率。

[1]羅印升，李人厚，張維璽.一種基于克隆選擇的聚類算法[J].控制與決策，2005，20（11）：1261-1264.

[2]徐曉華，陳崚.一種自適應的螞蟻聚類算法[J].軟件學報，2006，17（9）：1884-1889.

[3]李帥，王新軍，高丹丹.基于內(nèi)部空間特性的PSO聚類算法[J].計算機工程，2009，35（5）：197-199.

[4]Geem Z W，Kim J H，Loganathan G V.A new heuristic optimization algorithm：harmony search[J].Simulation，2001，76（2）：60-68.

[5]Alia O，Mandava R，Aziz M.A hybrid harmony search algorithmforMRIbrainsegmentation[J].EvolutionaryIntelligence，2011，4（1）：31-49.

[6]Forsati R，Meybodi M R，Mahdavi M，et al.Hybridization of K-means and harmony search methods for Web page clustering[C]//Proceedings of International Conference on Web Intelligence and Intelligent Agent Technology，2008：329-335.

[7]Ayvaz M T.Simultaneous determination of aquifer parameters and zone structures with fuzzy C-means clustering and metaheuristicharmonysearchalgorithm[J].AdvancesinWater Resources，2007，30（11）：2326-2338.

[8]Law M H，F(xiàn)igueiredo M A，Jain A K.Simultaneous feature selection and clustering using mixture models[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2004，26（9）：1154-1166.

[9]Dy J，Brodley G C E，Mach J.Feature selection for unsupervised learning[J].Journal of Machine Learning Research，2004，5：845-889.

[10]Sarvari H，Khairdoost N，F(xiàn)etanat A.Harmony search algorithm forsimultaneousclusteringandfeatureselection[C]// Proceedings of International Conference on Soft Computing and Pattern Recognition，2010：202-207.

[11]Huang J Z，Ng M K，Rong H，et al.Automated variable weighting in K-means type clustering[J].IEEE Trans on Pattern Anal Mach Intell，2005，27：657-668.

[12]Modha D S，Spangler W S.Feature weighting in K-means clustering[J].Mach Learn，2003，52：217-237.

[13]Friedman J H，Meulman J J.Clustering objects on subsets of attributes[J].J R Stat Soc：Ser B Stat Methodol，2004，66：1-25.

[14]Mohamed N A，Sameh M Y，Aly A F，et al.A modified fuzzy C-means algorithm for bias field estimation and segmentation of MRI data[J].IEEE Transactions on Medical Imaging，2002，21（3）：193-199.

WANG Huaqiu1,LUO Jiang1,Michael GERNDT2,Ventsislav PETKOV2

1.School of Computer Science,Chongqing University of Technology,Chongqing 400054,China
2.Institute of Informatics I10,Technology University Munich,D-85748,Munich,Germany

Three methods are adopted to achieve a better clustering quality.Considering the different influences of each dimension attribute of data on the clustering effect,statistic method is used to weight each dimension to select feature.Some improvements are carried out for the probability of harmony search algorithm and combine fuzzy clustering algorithm with harmony search to rapidly find the optimal cluster centers.The iterative method is used to test clustering quality to get the best number of cluster center.The proposed algorithm is applied to parallel computing performance analysis to distinguish and identify the performance bottleneck category of various processors during parallel program running.Experimental results show that the proposed clustering algorithm outperforms other similar algorithms.This performance analysis method can improve the operating efficiency of the parallel program.

harmony search;fuzzy clustering;feature selection;parallel performance analysis

采取了3種必要的措施提高了聚類質(zhì)量：考慮到各維數(shù)據(jù)特征屬性對聚類效果影響不同，采用了基于統(tǒng)計方法的維度加權(quán)的方法進行特征選擇；對于和聲搜索算法的調(diào)音概率進行了改進，將改進的和聲搜索算法和模糊聚類相結(jié)合用于快速尋找最優(yōu)的聚類中心；循環(huán)測試各種中心數(shù)情況下的聚類質(zhì)量以獲得最佳的類中心數(shù)。該算法被應用于并行計算性能分析中，用于識別并行程序運行時各處理器運行性能瓶頸的類別。實驗結(jié)果表明該算法較其他算法更優(yōu)，這樣的性能分析方法可以提高并行程序的運行效率。

和聲搜索；模糊聚類；特征選擇；并行性能分析

A

TP301.6；TP338.6

10.3778/j.issn.1002-8331.1202-0447

WANG Huaqiu,LUO Jiang,Michael GERNDT,et al.Research and application of harmony search fuzzy clustering with feature selection.Computer Engineering and Applications,2013,49（19）：112-118.

教育部人文社會科學研究青年基金（No.10YJC870037）；重慶市教委科學研究資助項目（No.KJ100805）。

王華秋（1975—），男，博士，副教授，主要研究領(lǐng)域為人工智能，數(shù)據(jù)挖掘；羅江（1987—），女，碩士生；Michael GERNDT，男，博士，教授；Ventsislav PETKOV（1985—），男，博士生。E-mail：wanghuaqiu@163.com

2012-02-29

2012-05-08

1002-8331（2013）19-0112-07

CNKI出版日期：2012-06-15http://www.cnki.net/kcms/detail/11.2127.TP.20120615.1725.008.html