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

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

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

2 算法思路

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

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

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

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

3 基于維度加權的特征選擇

現已知樣本：

λki代表了一個是否和其他數據沒有顯著性區別的分界值。

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

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

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

4 和聲搜索模糊聚類算法

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

4.1 初始化和設置參數

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

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

4.2 初始化和聲存儲庫

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

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

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

4.3 演奏新的和音

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

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

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

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

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

4.4 改進的調音策略

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

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

4.5 更新和音存儲庫

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

再由隸屬矩陣產生新的聚類中心：

4.6 聚類性能評價

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

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

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

4.7 檢查終止條件

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

5 算法復雜度

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

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

圖1 算法流程圖

6 算法收斂性

定理1 HSFC會收斂于全局最優。

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

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

啟發式算法在迭代過程中始終保持了最優解，確保可以收斂于全局最優，因此轉移矩陣P是穩定的。從和聲搜索算法的定義中可知，每次迭代中和聲庫都會更新最優解，因此矩陣P轉移到任何全局最優狀態的概率也會收斂到1，定理得證。

7 并行性能分析

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

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

表1 性能分析數據

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

表2 并行性能聚類結果

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

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

圖2 處理器聚類結果

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

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

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

定義5

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

表3 并行性能加權聚類結果

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

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

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

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

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

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

規則2IfProcessorj∈CithenProcessorj具有Performancej性能瓶頸。

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

8 結束語

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

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

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

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

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

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

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

[3]李帥，王新軍，高丹丹.基于內部空間特性的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，Figueiredo 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，Fetanat 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種必要的措施提高了聚類質量：考慮到各維數據特征屬性對聚類效果影響不同，采用了基于統計方法的維度加權的方法進行特征選擇；對于和聲搜索算法的調音概率進行了改進，將改進的和聲搜索算法和模糊聚類相結合用于快速尋找最優的聚類中心；循環測試各種中心數情況下的聚類質量以獲得最佳的類中心數。該算法被應用于并行計算性能分析中，用于識別并行程序運行時各處理器運行性能瓶頸的類別。實驗結果表明該算法較其他算法更優，這樣的性能分析方法可以提高并行程序的運行效率。

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

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—），男，博士，副教授，主要研究領域為人工智能，數據挖掘；羅江（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