基于改進(jìn)K均值聚類算法的星點(diǎn)聚類研究

夏永泉，孫靜茹，WU Xin-wen，支 俊，王 兵，謝希望

?

基于改進(jìn)K均值聚類算法的星點(diǎn)聚類研究

夏永泉1，孫靜茹1，WU Xin-wen2，支 俊1，王 兵1，謝希望1

(1. 鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院，河南 鄭州 450000； 2.格里菲斯大學(xué)工程信息技術(shù)學(xué)院，昆士蘭 布里斯班 4000)

針對高分辨率天文圖像中的星點(diǎn)聚類研究中存在的2個問題：①天文圖像的分辨率較高，且圖像處理速度較慢；②選取何種聚類算法對天文圖像中的星點(diǎn)進(jìn)行聚類分析效果較好。在研究中，問題1采用圖像分塊的方法提高圖像的處理速度；問題2提出了一種改進(jìn)的K均值聚類算法，以解決傳統(tǒng)的K均值聚類算法的聚類結(jié)果易受到值和初始聚類中心隨機(jī)選擇影響的問題。該算法首先在用K均值聚類算法對數(shù)據(jù)初步聚類的基礎(chǔ)上確定合適的值，其次用層次聚類對數(shù)據(jù)聚類確定初始聚類中心，最后在此基礎(chǔ)上再采用K均值聚類算法進(jìn)行聚類。通過MATLAB仿真實(shí)驗(yàn)的結(jié)果表明，該算法的聚類結(jié)果與效率優(yōu)于其他聚類算法。

k值；初始聚類中心；K均值聚類算法；層次聚類

對于天文圖像中星點(diǎn)的提取識別，國內(nèi)外眾多專家學(xué)者都進(jìn)行了研究，其中，王龍等[1]提出一種星敏感器星點(diǎn)聚類提取方法；全偉和房建成[2]提出一種基于蟻群聚類算法的快速星圖識別方法；王春歆等[3]提出一種基于層次聚類的弱小目標(biāo)檢測算法。雖然這些文獻(xiàn)通過聚類算法提取識別星點(diǎn)，但是很少對星點(diǎn)進(jìn)行聚類分析的研究。

本文主要對天文圖像中星點(diǎn)作聚類分析。星點(diǎn)聚類分析可采用的算法有很多，其中K均值聚類算法是最著名和最常用的方法之一。但是，由于傳統(tǒng)的K均值聚類算法必須在聚類前設(shè)定值和隨機(jī)選取聚類中心，最后得到的聚類結(jié)果會受到值和聚類中心的影響。若選取的值和聚類中心不合適，不僅會增加迭代的次數(shù)還會導(dǎo)致聚類結(jié)果不理想。張素潔和趙懷慈[4]提出一種算法，基于SSE (sum of the squared error)選取聚類個數(shù)，基于聚類中心點(diǎn)所在的周圍區(qū)域相對比較密集、聚類中心點(diǎn)之間距離相對較遠(yuǎn)的選取原則來選取初始聚類中心；GUPTA等[5]提出一種混合PSO和K均值聚類的算法，用PSO算法優(yōu)化K均值聚類的結(jié)果。魏建東等[6]提出基于DBI度量的層次初始的聚類個數(shù)自適應(yīng)的聚類算法；陶瑩等[7]通過全局化思想對K均值算法的改進(jìn)，避免選取出初始聚類中心；CHAKRABARTY[8]提出一種質(zhì)心初始化技術(shù)，用于K均值聚類算法；AKTHAR等[9]提出2種選取K均值聚類的初始聚類中心的方法，一種是從高密度區(qū)域選擇最遠(yuǎn)距離的點(diǎn)作為初始聚類中心，另一種是從高密度區(qū)域選擇最近距離的點(diǎn)作為初始聚類中心；CHOUHAN和PUROHIT[10]提出了基于PSO和K均值算法的文檔聚類方法，通過在K均值聚類之前使用PSO方法進(jìn)行尋找最優(yōu)點(diǎn)并作為K均值聚類的初始聚類中心；丁明月和莊曉東[11]提出了自適應(yīng)K均值算法，利用灰度直方圖來確定初始聚類中心；于化龍和韓雪峰[12]提出改進(jìn)K均值聚類算法的銀行分類算法，根據(jù)類間最大相似度均值選擇初始聚類中心；張紅云和李萍萍[13]提出基于層次聚類的K均值算法研究，采用層次方法對文檔進(jìn)行初始聚類，得到的聚類總數(shù)作為K均值算法中的值，在此基礎(chǔ)上，通過K均值聚類對聚類結(jié)果進(jìn)行修訂。

上述文獻(xiàn)用到了各種方法來確定值和優(yōu)化初始聚類中心，但本文提出一種新的方法來確定初始聚類中心，①通過K均值聚類算法的聚類準(zhǔn)則函數(shù)值來確定合適的值；②使用經(jīng)過層次聚類算法聚類后的結(jié)果計(jì)算出對應(yīng)的聚類中心作為初始聚類中心；③在此基礎(chǔ)上進(jìn)行K均值聚類。

1 算法描述

由于天文圖像的分辨率一般都比較大，所以直接對天文圖像進(jìn)行星點(diǎn)聚類效率很低甚至不能實(shí)現(xiàn)，因此本文進(jìn)行聚類算法前先對天文圖像進(jìn)行分塊，之后再對每一塊子圖像進(jìn)行特征提取，確定合適的值和初始聚類中心，其次完成每一塊子圖像的星點(diǎn)聚類，最后以每一塊子圖像的聚類中心作為新的數(shù)據(jù)，采用本文聚類算法進(jìn)行聚類得到整幅天文圖像的聚類結(jié)果。

1.1 圖像分塊

一般圖像分塊是將1幅圖像分為若干個圖像塊，如2×2，4×4，8×8。而本文采用的分塊機(jī)制與之不同。本文采用的是按照一定大小的對圖像依行列的方式直接進(jìn)行分塊，即將1幅高分辨率的天文圖像按照分辨率的大小分成若干塊。假定原始圖像I經(jīng)過灰度轉(zhuǎn)換后分辨率大小為，設(shè)置子圖像的寬高大小為，取值為2(=1,2,3,4,···)，則天文圖像被分成()×()塊。

1.2 星點(diǎn)聚類特征的選取

本文選取顏色及紋理2類特征。其原因是從直觀上觀察每個星點(diǎn)的大小、明暗度、顏色以及光芒如何發(fā)散的不同，而顏色特征可以反映星點(diǎn)的明暗度和顏色，紋理特征可以反映星點(diǎn)的大小和光芒如何發(fā)散的。

1.2.1 顏色特征

大部分的彩色圖像是基于RGB顏色3基色模型，但是RGB顏色空間體制并不適應(yīng)人的視覺特點(diǎn)。所以本文采用更加符合人眼視覺特征的HIS顏色空間。HSI顏色空間模型是色調(diào)(ue)、飽和度(Saturation)和強(qiáng)度(Identity)首字母的簡稱。H表示顏色的種類，S表示顏色的純度，I表示亮度信息。HSI顏色空間是由RGB顏色空間轉(zhuǎn)換得來的，轉(zhuǎn)換關(guān)系如下

其中

1.2.2 紋理特征

紋理特征提取有多種方法，如灰度差分統(tǒng)計(jì)、自相關(guān)函數(shù)、灰度共生矩陣等。本文使用灰度共生矩陣描述紋理。1幅圖像的灰度共生矩陣能反映圖像灰度方向，相鄰間隔和變化幅的綜合信息。為了能夠更加直觀地以共生矩陣描述紋理狀況，選取以下5個標(biāo)量來表征灰度共生矩陣的特征。

(1) 能量。是灰度共生矩陣元素值的平方和，反映了圖像灰度分布均勻程度和紋理粗細(xì)度。

(2) 對比度。反映了圖像的清晰度和紋理溝紋深淺的程度。返回整幅圖像中像素和其相鄰像素之間的亮度反差。

(3) 相關(guān)性。是度量灰度共生矩陣元素在行列方向上的相似程度，因此，相關(guān)性的值反映了圖像中局部灰度相關(guān)性。返回整幅圖像中像素與其相鄰像素是如何相關(guān)的度量值。

(4) 熵。是圖像所具有的信息量的度量。表示圖像中紋理的非均勻程度或復(fù)雜程度。

(5) 平穩(wěn)度。反映圖像紋理的同質(zhì)性，度量圖像紋理局部變化的多少。返回度量灰度共生矩陣中元素的分布到對角線緊密程度。

綜合以上2種特征，可以定義一個樣本有8個特征值，則可以看作是一個8維的特征向量，即

其中，1為對比度；2為相關(guān)性；3為熵；4為均勻度；5為能量；6為，7為，8為。

1.3 k值(聚類個數(shù))的確定

傳統(tǒng)的K均值聚類算法中的值必須是用戶人為最先確定，即分成多少類。但是合適的值，用戶是不可知的。因此本文通過對星點(diǎn)進(jìn)行不同值下的K均值聚類算法，選取合適的值。選取適當(dāng)?shù)闹档囊粋€普遍方法是通過遍歷得到某一范圍聚類數(shù)的誤差平方和。誤差平方和準(zhǔn)則是一種簡單而又廣泛應(yīng)用的聚類準(zhǔn)則，以評價聚類的優(yōu)劣。

1.4 初始聚類中心的確定

傳統(tǒng)的K均值聚類算法在聚類前隨機(jī)選取聚類中心，并根據(jù)初始聚類中心進(jìn)行循環(huán)迭代，直到聚類中心不在變化停止。因此，初始聚類中心的不同可能導(dǎo)致聚類結(jié)果的不穩(wěn)定，會產(chǎn)生多個局部最優(yōu)值。

本文算法通過以層次聚類作為前期處理，得到初步聚類結(jié)果，根據(jù)聚類結(jié)果選擇相應(yīng)的聚類中心的方法優(yōu)化初始聚類中心。以此聚類中心作為K均值聚類的算法的初始聚類中心，進(jìn)行K均值聚類算法。

前期處理中層次聚類是首先定義樣本之間和類與類之間的距離，在各自成類的樣本中，將距離最近的2類合并，重新計(jì)算新類與其他類間的距離，并按最小距離歸類。重復(fù)此過程，每次減少一類，直到所有的樣本稱為一類為止。

根據(jù)式(4)定義包含個數(shù)據(jù)的特征值矩陣可用一個行8列的矩陣表示。那么第個樣品和第個樣品的特征值向量見式(7)，2個樣品的距離可根據(jù)歐式距離式(8)求得d，即

類與類之間的距離選取的是ward距離，用D表示第個類G到第個類G的距離。先計(jì)算1，2，···中各樣本與類重心(即均值)的歐氏距離，然后將之取平方求和，得出結(jié)果稱為離差平方和。若通過計(jì)算，把距離最近的2個類(G和G)合并，使之成一個新的類(G)，那么這2個類(G和G)和合并后的新類G的離差平方和分別為[14]式(9)~(11)，即

其中，

μ，μ，μ分別為類G，G，G的重心；W，W，W為各自類內(nèi)樣本分散程度的度量。G和G之間平方距離表示為

根據(jù)歐氏距離和ward距離完成層次聚類，并根據(jù)層次聚類的聚類結(jié)果計(jì)算出相應(yīng)的聚類中心。聚類中心以某一類中的所有樣本特征的平均值表示，根據(jù)式(13)可計(jì)算出其特征值，即

1.5 星點(diǎn)聚類

由于圖像分辨率較大，所以在聚類分析時，需對每塊子圖像進(jìn)行星點(diǎn)聚類分析，再對子圖像之間進(jìn)行聚類分析從而得到整幅天文圖像的聚類分析。

1.5.1 子圖像的星點(diǎn)聚類

首先通過腐蝕膨脹提取出每個圖像塊中的星點(diǎn)，并提取其紋理特征和顏色特征。其次對同1幅圖像作3種方法的聚類分析，且分別記錄聚類時間和誤差平方和的值。

(1) 傳統(tǒng)的K均值聚類算法。首先在整個數(shù)據(jù)集中任意選取個數(shù)據(jù)作為初始聚類中心，然后根據(jù)其他數(shù)據(jù)對象與個聚類中心的距離大小，將數(shù)據(jù)對象劃分到距離最近的相似類中。所有數(shù)據(jù)劃分后，重新計(jì)算個聚類中每個聚類的全部數(shù)據(jù)對象的平均值，該平均值所在的數(shù)據(jù)點(diǎn)作為新的聚類中心，經(jīng)過多次迭代，直到連續(xù)2次的聚類中心相同，說明此時數(shù)據(jù)對象類別劃分完畢，即得到個聚類。

(2) 文獻(xiàn)[5]方法。一種混合PSO和K均值聚類的算法，用PSO算法優(yōu)化K均值聚類的結(jié)果。先進(jìn)行一次傳統(tǒng)的K均值聚類算法，再對得到的聚類結(jié)果運(yùn)用PSO算法優(yōu)化。

(3) 本文方法也稱改進(jìn)的K均值聚類算法。通過算法確定值和初始聚類中心。將傳統(tǒng)的K均值聚類算法改進(jìn)成了一種自適應(yīng)選取值的并優(yōu)化了初始聚類中心的K均值聚類算法。

1.5.2 整幅圖像的星點(diǎn)聚類

若對整幅圖像直接進(jìn)行聚類分析，時間過長甚至得不到結(jié)果，所以需要通過對子圖像之間的聚類分析得到整幅圖像的值，即可將整幅圖像中的星點(diǎn)分成若干類。本文算法如下：

(1) 對每塊子圖像進(jìn)行聚類分析。根據(jù)式(4)，式(5)和式(11)得到每塊圖像的值和每一類的聚類中心的特征值。通過循環(huán)得到所有的子圖像的聚類中心的特征值矩陣；

(2) 對聚類中心的特征值矩陣采用本文算法進(jìn)行聚類分析，得到的聚類結(jié)果中的值就是整幅圖像的值。

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)平臺

實(shí)驗(yàn)平臺選取matlabR2013b，4核CPU i5-3470，內(nèi)存4 GB，操作系統(tǒng)Windows 8。

2.2 實(shí)驗(yàn)結(jié)果與分析

聚類實(shí)驗(yàn)中將分辨率為40000×30131的天文圖像按照2048×2048大小的分塊分辨率分成圖像塊，對每一個圖像塊中的星點(diǎn)進(jìn)行3種方法的聚類分析，得到3種算法的聚類準(zhǔn)則函數(shù)值和聚類時間，并根據(jù)所有的圖像塊的聚類中心的聚類結(jié)果得到天文圖像的值。

(1)值的確定。根據(jù)不同的值，對同一幅圖像進(jìn)行多次傳統(tǒng)的均值聚類，分別得到聚類準(zhǔn)則函數(shù)值。以一張圖像為例，值與聚類準(zhǔn)則函數(shù)值的關(guān)系變化如圖1所示。

從圖1可看出，隨著值的增加，聚類準(zhǔn)則函數(shù)值越小。其中在=3之后，聚類準(zhǔn)則函數(shù)值的減少速度越來越平緩，而=3之前，聚類準(zhǔn)則函數(shù)值的急劇減少，即星點(diǎn)分成3類比較合適。

(2) 分析3種算法聚類結(jié)果的優(yōu)劣。選取多幅圖像實(shí)驗(yàn)，證明改進(jìn)后的算法得到的結(jié)果的優(yōu)越性。由于傳統(tǒng)的K均值聚類的結(jié)果具有不穩(wěn)定性，所以選用多次結(jié)果的平均值作為最終結(jié)果。圖像的分辨率較大所以分成的塊數(shù)較多，因此任意選取其中的16組進(jìn)行實(shí)驗(yàn)結(jié)果顯示(表1)。選取的原則是對角線選取。實(shí)驗(yàn)結(jié)果見。

圖1 k值與聚類準(zhǔn)則函數(shù)值的關(guān)系變化圖

表1 聚類準(zhǔn)則函數(shù)值表

聚類結(jié)果折線圖如圖2所示。

圖2 聚類結(jié)果圖

從表1可以看出，3種聚類算法的準(zhǔn)則函數(shù)值相差的不大，只有幾個數(shù)值相差較大，說明3種聚類算法在一些圖像上進(jìn)行聚類分析時差異性較大，但大部分圖像的差異性較小。

從圖2可以看出，改進(jìn)的K均值聚類的每個結(jié)點(diǎn)的值都小于傳統(tǒng)的K均值和文獻(xiàn)[5]方法的聚類準(zhǔn)則函數(shù)值，由于聚類準(zhǔn)則函數(shù)值越小，代表聚類的效果越好，所以說明改進(jìn)后的聚類結(jié)果優(yōu)于傳統(tǒng)的聚類結(jié)果和文獻(xiàn)[5]的聚類結(jié)果。圖3顯示了部分聚類效果圖。

(A1)(B1)(C1) (A2)(B2)(C2)

(3) 分析3種算法的速度。對同一幅圖像分別采用3種算法聚類，分別記錄其聚類時間。表2根據(jù)條件(2)中的圖像所運(yùn)行的聚類時間。

聚類時間折線圖如圖4所示。

從圖4可以看出改進(jìn)的K均值聚類時間和傳統(tǒng)的K均值聚類時間均小于文獻(xiàn)[5]方法的聚類時間，雖然文獻(xiàn)[5]的聚類結(jié)果優(yōu)于傳統(tǒng)的K均值聚類算法，但是時間要高于傳統(tǒng)的K均值聚類算法，因?yàn)槲墨I(xiàn)[5]方法使用PSO算法優(yōu)化K均值聚類結(jié)果，增加了時間消耗。改進(jìn)的K均值聚類算法和傳統(tǒng)的K均值聚類算法的聚類時間相差較小，但還是低于傳統(tǒng)的K均值聚類算法，由于初始聚類中心的優(yōu)化而減少了迭代次數(shù)，從而減少了聚類時間。故改進(jìn)的K均值聚類算法優(yōu)于其他兩種方法。

表2 聚類時間表

圖4 聚類時間圖

綜上，改進(jìn)的K均值聚類算法的聚類結(jié)果和效率優(yōu)越于其他聚類算法。

3 結(jié)束語

本文針對高分辨率天文圖像中星點(diǎn)聚類問題進(jìn)行研究，利用改進(jìn)的K均值聚類算法進(jìn)行聚類分析。改進(jìn)的K均值聚類算法通過不同值下的K均值聚類算法找到合適的值，采用層次聚類算法得到初步聚類結(jié)果，并計(jì)算出聚類中心，以此為K均值算法的初始聚類中心，在得到的值和初始聚類中心時進(jìn)行K均值聚類算法。通過實(shí)驗(yàn)結(jié)果證明改進(jìn)的K均值聚類算法的聚類結(jié)果和效率均比其他聚類算法優(yōu)越，說明改進(jìn)的K均值聚類算法更適用于星點(diǎn)聚類。

[1] 王龍, 楊孟飛, 鐘紅軍, 等. 星敏感器星點(diǎn)聚類提取方法[J]. 中國科學(xué): 技術(shù)科學(xué), 2015(3): 257-262.

[2] 全偉, 房建成. 一種基于蟻群聚類算法的快速星圖識別方法[J]. 宇航學(xué)報, 2008, 29(6): 1814-1818.

[3] 王春歆, 沈同圣, 張玉葉. 基于層次聚類的弱小目標(biāo)檢測算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2006, 44(19): 24-27.

[4] 張素潔, 趙懷慈. 最優(yōu)聚類個數(shù)和初始聚類中心點(diǎn)選取算法研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2017, 34(6): 1617-1620.

[5] GUPTA A, PATTANAIK V, SINGH M. Enhancing K means by unsupervised learning using PSO algorithm [C]//2017 International Conference on Computing, Communication and Automation. New York: IEEE Press, 2017: 228-233.

[6] 魏建東, 陸建峰, 彭甫镕. 一種層次初始的聚類個數(shù)自適應(yīng)的聚類方法研究[J]. 電子設(shè)計(jì)工程, 2015(6): 5-8.

[7] 陶瑩, 楊鋒, 劉洋, 等. K均值聚類算法的研究與優(yōu)化[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2018, 28(6): 96-98.

[8] CHAKRABARTY A. An empirical seed initialization idea for K-Means algorithm inspired by CLIQUE algorithm [C]//2017 International Conference on Information Technology (ICIT). New York: IEEE Press, 2017: 21-23.

[9] AKTHAR N, AHAMAD M V, AHMAD S. MapReduce model of improved K-means clustering algorithm using Hadoop MapReduce [C]//Second International Conference on Computational Intelligence and Communication Technology. New York: IEEE Press, 2016: 192-198.

[10] CHOUHAN R, PUROHIT A. An approach for document clustering using PSO and K-means algorithm [C]//2018 2nd International Conference on Inventive Systems and Control (ICISC).New York: IEEE Press, 2018: 19-20.

[11] 丁明月, 莊曉東. 基于數(shù)據(jù)融合的K均值聚類彩色圖像分割方法[J]. 青島大學(xué)學(xué)報: 工程技術(shù)版, 2018, 33(2): 46-50, 62.

[12] 于化龍, 韓雪峰. 基于改進(jìn)K均值聚類的銀行客戶分類算法[J]. 湘潭大學(xué)自然科學(xué)學(xué)報, 2018, 40(3): 129-132.

[13] 張紅云, 李萍萍. 一種基于層次聚類的K均值算法研究[J]. 微計(jì)算機(jī)信息, 2010, 26(12): 228-229.

[14] 王學(xué)民. 應(yīng)用多元分析[M]. 上海: 上海財經(jīng)大學(xué)出版社, 2009.

Star Point Clustering Based on Improved K-Means Clustering Algorithm

XIA Yong-quan1, SUN Jing-ru1, WU Xin-wen2, ZHI Jun1, WANG Bing1, XIE Xi-wang1

(1. School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou Henan 450000, China; 2. Faculty of Engineering and Information Technology, Griffith University, Brisbane Queensland 4000, Australia)

Two problems in the study of star point clustering in high resolution astronomical images: ① The resolution of the astronomical image is higher, and the image processing speed is slower. ② Which clustering algorithm is selected to cluster the star points in the astronomical image is better. In the research, problem 1 uses image segmentation method to improve image processing speed. problem 2 proposes an improved K-means clustering algorithm to solve the traditional K-means clustering algorithm clustering results are susceptible to-value and The initial clustering center randomly selects the problem of impact. Firstly, the K-means clustering algorithm is used to determine the appropriate-value based on the preliminary clustering of data. Secondly, the clustering is used to determine the initial clustering center by data clustering. Finally, K-means clustering is used. The algorithm performs clustering. The simulation results of MATLAB show that the clustering results and efficiency of the algorithm are better than other clustering algorithms.

k-value; initial cluster center; K-means clustering algorithm; hierarchical clustering

TP 391.41

10.11996/JG.j.2095-302X.2019020358

A

2095-302X(2019)02-0358-06

2018-10-18；

2019-01-13

國家自然科學(xué)基金項(xiàng)目(81501547)；河南省科技攻關(guān)項(xiàng)目(172102410080)

夏永泉(1972-)，男，遼寧綏中人，副教授，博士。主要研究方向?yàn)閳D像處理、計(jì)算機(jī)視覺、模式識別與人工智能研究。 E-mail：694473762@qq.com