基于改進k-means算法的數(shù)字圖像聚類

高 西， 胡子牧

(重慶醫(yī)科大學 附屬大學城醫(yī)院，重慶 401331)

1 引 言

隨著互聯(lián)網(wǎng)、5G等技術(shù)的飛速進步，可收集的圖片數(shù)據(jù)種類、數(shù)量越來越多，數(shù)據(jù)特征的維度也越來越高。為了從海量圖片中快速檢索、分類有用的圖片，許多研究者將聚類方法用于該領(lǐng)域[1-5]。聚類是模式識別和數(shù)據(jù)挖掘中的一個重要方向，是一類無監(jiān)督學習算法，它遵循相似規(guī)則將數(shù)據(jù)樣本劃分為不同的類，在同一類中的對象之間相似性較高，而在不同類中對象之間相似性較低。到目前為止，很多研究者提出了一些有效的聚類方法，例如k-means[6]、FCM[7]、SOM聚類[8]、AP算法[9]、譜聚類算法[10-13]。其中k-means算法以其對大型數(shù)據(jù)集的高處理效率而得到了最為廣泛的應用。該算法的優(yōu)點有很多，缺點主要在于：第一，只考慮類內(nèi)距離，未考慮類間距離；第二，對包含海量樣本的數(shù)據(jù)集的聚類數(shù)目上界的確定主要依靠經(jīng)驗，而人為設置的聚類數(shù)目上界往往偏大，導致了算法運行效率被降低。

有鑒于k-means算法的第一個缺陷，黃曉輝等[14]提出了一種類內(nèi)-類間距離加權(quán)的k-means算法，該算法的基本思路是，通過在子空間內(nèi)最大化類中心與其他類內(nèi)樣本點的距離來融合類內(nèi)和類間距離進行聚類。黃曉輝等在算法中設計了一個目標函數(shù)，然后通過求解目標函數(shù)來對算法參數(shù)進行迭代更新。在真實數(shù)據(jù)集上的表現(xiàn)證實了該算法相比于現(xiàn)有k-means類算法的優(yōu)越性。針對傳統(tǒng)k-means算法的第二個缺陷導致的聚類數(shù)目上界設置偏大，進而導致算法運行效率偏低的問題，周世兵等[15]通過合理設置AP算法的初始參數(shù)確定了聚類數(shù)目的上界，該方法比傳統(tǒng)的經(jīng)驗估計更為有效，大大提升了k-means算法的執(zhí)行效率。本文提出了一種改進型的k-means算法，在該算法中，周世兵等提出的最小聚類上界確定方法與黃曉輝等提出的類內(nèi)-類間距離加權(quán)k-means算法被合并使用。本文所提出的方法被用于一個標準聚類圖像數(shù)據(jù)集的聚類中。實驗結(jié)果顯示，本文所提出的改進型k-means相比于傳統(tǒng)k-means和另外幾種K-means類算法，達到了更高的性能，同時執(zhí)行效率也大為提升。

2 理 論

2.1 類內(nèi)-類間距離加權(quán)k-means算法

與其他加權(quán)k-means 算法類似，類內(nèi)-類間距離加權(quán)k-means算法也包含3個計算步驟：更新分配矩陣U、更新類中心矩陣Z和更新特征權(quán)重矩陣W。

設有一包含n個m維樣本的數(shù)據(jù)集X={X1,X2,…,Xn}。數(shù)據(jù)對象分配矩陣U∈Rnk為一個只包含0和1的矩陣。Z={Z1,Z2,…,Zk}為類中心矩陣，其中Zp={zp1,zp2,…,zpm}為第p個類中心。W={W1,W2,…,Wk}為權(quán)重向量，其中Wp={wp1,wp2,…,wpm}代表第p個類的特征權(quán)重，wpj為第p類中第j個特征的權(quán)重。該算法的目標函數(shù)如公式(1)所示。

，

(1)

其中：η是類內(nèi)-類間距離調(diào)整參數(shù)，γ是權(quán)重分布控制參數(shù)。

固定權(quán)重矩陣W和類中性能矩陣Z，式(1)在滿足式(2)時可以最小化。

，

(2)

固定數(shù)據(jù)對象分配矩陣U和特征權(quán)重矩陣W，P(W,U,Z)可以最小化當且僅當:

，

(3)

固定數(shù)據(jù)對象分配矩陣U和類中心矩陣Z，P(W,U,Z)可以最小化當且僅當：

,(4)

類內(nèi)-類間距離加權(quán)k-means算法的運行流程如下：

步驟1：輸入數(shù)據(jù)集X，類數(shù)目k，參數(shù)η和γ；

步驟2：隨機初始化類中心Z和特征權(quán)重W；

步驟3：固定W和Z，由式(2)求解U；

步驟4：固定W和U，由式(3)求解Z；

步驟5：固定U和Z，由式(4)求解W；

步驟6：重復步驟3～5直到目標函數(shù)(1)收斂或U不再改變。

2.2 基于近鄰傳播聚類算法的類數(shù)量上界確定方法

在運用k-means算法時，一般難以直接確定數(shù)據(jù)集的最佳聚類數(shù)目，因此一般的做法是根據(jù)經(jīng)驗確定聚類數(shù)目上限，在該數(shù)目上限之內(nèi)，依次按照逐漸增大的聚類數(shù)目進行k-means聚類。由于經(jīng)驗估計往往導致聚類數(shù)目上限偏大，因此這種做法在實際應用中效率不高。文獻[15]采用近鄰傳播算法(Affinity Propagation clustering, AP)來確定聚類數(shù)目上限，大大提高了效率。其詳細的運行步驟如下：

步驟1：將所有AP偏向參數(shù)pi(i=1,2,…,n)統(tǒng)一設定為吸引度中值pm，然后通過AP算法確定聚類數(shù)目的搜索上界kAP;

步驟2：在聚類數(shù)目范圍[2,kAP]內(nèi)依次進行k-means算法，得到每個聚類數(shù)目下的聚類結(jié)果；

步驟3:按照設定好的評價指標確定最優(yōu)聚類數(shù)目。

3 圖像聚類方案設計及實驗

3.1 圖像聚類方案設計

本文所提出的圖像聚類算法的整體流程框圖其詳細運行流程如下：

步驟1：將待聚類的彩色圖片數(shù)據(jù)集中圖片通過雙線性插值法進行縮放，縮放后尺寸統(tǒng)一為50×50；

步驟2：將待聚類的彩色圖片數(shù)據(jù)集中已縮放圖片的亮度分量逐個進行局部二值模式(Local Binary Pattern, LBP)圖生成；

步驟3：將步驟2生成的所有LBP圖由二維矩陣按行展開成一個一維行向量，每張LBP圖像對應一個行向量。所有的行向量構(gòu)成圖片樣本的聚類數(shù)據(jù)集；

步驟4：將所有AP偏向參數(shù)pi(i=1,2,…,n)統(tǒng)一設定為吸引度中值pm，然后通過AP算法確定聚類數(shù)目的搜索上界kAP;

步驟5：在聚類數(shù)目范圍[2,kAP]內(nèi)依次進行類內(nèi)-類間距離加權(quán)k-means算法，得到每個聚類數(shù)目下的聚類結(jié)果；

步驟6：按照平均Silhouette指標值確定最優(yōu)聚類數(shù)目；

步驟7：輸出最優(yōu)聚類數(shù)目下的聚類結(jié)果。

其中平均Silhouette指標值[16]的定義如公式(5)所示。

，

(5)

其中:bi為第i個樣本到其他每個類中樣本平均距離的最小值，ai為第i個樣本與類內(nèi)所有其他樣本的平均距離。

圖1 算法整體運行流程

3.2 實驗

3.2.1 實驗條件

本文中所涉及算法均使用MATLAB R2019a軟件平臺實現(xiàn)，實驗所用計算機配置為：CPU使用AMD Ryzen 5 3600X 4 GHz，內(nèi)存64 GHz，顯卡為NVIDIA GeForce RTX 2070，系統(tǒng)為 Linux Ubuntu系統(tǒng)。

圖2 本地圖像數(shù)據(jù)集中部分樣本

圖3 GHIM10-K圖像數(shù)據(jù)集中部分樣本

本文在實驗中所使用的圖片數(shù)據(jù)集共計兩個。第一個為本地圖片數(shù)據(jù)集，包含4 200張彩色圖片，共分為6類：球類、景物類、建筑類、熊貓類、人臉類和汽車類。每類圖片均包含700張，每張圖片的大小均為320×320。本地圖片數(shù)據(jù)集的部分樣本數(shù)據(jù)如圖2所示。第二個圖片數(shù)據(jù)集為GHIM10-K圖片數(shù)據(jù)集。該數(shù)據(jù)集中包含共計10 000張彩色圖片，分為煙花、日落、船、花、建筑、高山和昆蟲等20個類，每類包含500張尺寸為300×400的圖片。GHIM10-K圖片數(shù)據(jù)集中的部分圖片樣本如圖3所示。

3.2.2 聚類效果評價指標

在實驗中，調(diào)整蘭德系數(shù)(Adjusted Rand Index, ARI)、宏F1度量(Marco-F1)和聚類時間用于進行算法聚類效果的評價指標。ARI的計算公式如式(6)所示。

，

(6)

宏F1度量的計算公式如式(7)所示。

，

(7)

其中KMacro-P和KMacro-R分別為宏查準率和宏查全率。這兩個指標的計算公式如式(8)所示。

，

(8)

其中KTPi為第i類樣本被正確分類的數(shù)目，KFPi為其他類樣本被錯誤分類至第i類的數(shù)目，KFNi為第i類樣本被錯誤分類至其他類別的數(shù)目。

3.2.3 試驗結(jié)果及分析

將待聚類的彩色圖片數(shù)據(jù)集中圖片通過雙線性插值法進行縮放，縮放后尺寸統(tǒng)一為50×50，然后將待聚類的彩色圖片數(shù)據(jù)集中已縮放圖片的亮度分量逐個進行LBP圖生成。部分樣本的LBP圖如圖4所示。

圖4 部分圖片樣本對應的LBP圖

將所有的LBP圖按行展開成一維行向量，每個向量作為一個樣本，所有的樣本構(gòu)成聚類數(shù)據(jù)集，通過本文所提出的改進型k-means算法所確定的聚類數(shù)目搜索上界kAP和經(jīng)驗估計確定的聚類數(shù)目搜索上界ke，以及通過平均Silhouette指標值確定的最優(yōu)聚類數(shù)目如表1所示。在范圍[2，kAP]內(nèi)不同聚類數(shù)目對應的平均Silhouette指標值變化情況如圖5所示。通過表1可以看出，相比于經(jīng)驗估計，AP算法所確定的聚類數(shù)目上界更為準確，這將大大減少算法的執(zhí)行時間，提高算法的執(zhí)行效率。同時，也可以發(fā)現(xiàn)，通過平均Silhouette指標值確定的最優(yōu)聚類數(shù)目達到了實際類數(shù)目的最優(yōu)無偏估計。

為了證實本文所提出的圖像聚類算法的優(yōu)越性，將文獻[17-18]中的方法與本文方法進行比較。這3種算法各自將3.2.1小節(jié)中介紹的兩個圖像數(shù)據(jù)集進行50次聚類，50次實驗得到的平均ARI、平均宏F1度量和平均執(zhí)行時間列于表2。通過表2可以看出，與兩種參考算法相比，本文所提出的算法具有更高的執(zhí)行效率，更具有實用性，這主要是因為本文方法將聚類數(shù)目搜索上界縮小所致。同時，相比于兩種參考算法，更高的平均宏F1度量也證實了本文所提算法的優(yōu)異聚類精確度。

表1 兩種數(shù)據(jù)集的聚類數(shù)目搜索上界和最優(yōu)聚類數(shù)目

圖5 本地數(shù)據(jù)集(左)和GHIM10-K數(shù)據(jù)集(右)在范圍[2，kAP]內(nèi)的聚類數(shù)目-平均Silhouette值圖

表2 3種算法的比較

4 結(jié) 論

針對海量彩色圖像高效精確聚類問題, 本文引入了一種改進型k-means算法并將其應用于彩色圖像聚類中。該算法由類內(nèi)-類間距離加權(quán)k-means算法和基于近鄰傳播聚類算法的聚類數(shù)量上界確定方法組成。在實驗中，彩色圖像通過雙線性插值縮放，縮放后尺寸統(tǒng)一為50×50?？s放后彩色圖像的亮度分量的LBP圖被重組成行向量然后構(gòu)成樣本特征數(shù)據(jù)集，本文所提出的改進型k-means算法被用于對樣本集進行聚類處理。實驗結(jié)果顯示，在平均宏F1度量和ARI的測試中，本方法相比于傳統(tǒng)方法達到了更高的水平，證實了本文所提方法優(yōu)異的聚類準確度。同時，由于聚類數(shù)目上界的準確確定，相比于傳統(tǒng)方法，本方法也更具有執(zhí)行效率。