基于改進K-Means算法的雷電脈沖分類研究*

彭 丹 張曙霞

(海軍工程大學(xué)電子工程學(xué)院 武漢 430033)

?

基于改進K-Means算法的雷電脈沖分類研究*

彭 丹 張曙霞

(海軍工程大學(xué)電子工程學(xué)院 武漢 430033)

K-均值聚類算法因具有實現(xiàn)簡單、快速有效、適合處理大數(shù)據(jù)集等優(yōu)點而被廣泛應(yīng)用。但是由于初始聚類中心是隨機選擇的,K-均值聚類的結(jié)果對初始中心值具有很大的依賴性。另一方面,聚類的類數(shù)K也對聚類結(jié)果具有重要影響,一般情況下K是未知的,需要相關(guān)的專業(yè)知識對K進行預(yù)測,如果不能事先確定合適的K值,聚類的結(jié)果也會很不理想。本文提出一種改進的K-均值算法,避開了初始中心點的隨機選擇,只需計算數(shù)據(jù)集合中相距最遠的兩個點將其設(shè)為初始中心,同時不需要預(yù)先猜測聚類的數(shù)目,大大減小了用戶的使用難度,聚類效果也顯著提高。論文將改進的K-均值算法應(yīng)用到自然雷電脈沖的分類中,并與傳統(tǒng)K-均值算法的分類結(jié)果進行了比較。

K-均值聚類; 初始聚類中心; 聚類數(shù)目; 自然雷電脈沖

Class Number TP301.6

1 引言

甚低頻通信是指利用頻率為3kHz～30kHz的無線電波進行遠距離信號傳輸?shù)囊环N通信方式[1]。由于甚低頻電波較高頻電波而言在海水中的衰減較弱、能深入巖層,且具有傳播較穩(wěn)定、損耗較小的特點,因而甚低頻通信具有重要的軍事應(yīng)用價值,甚低頻對潛通信已成為海軍遠程指揮通信的主要手段之一。

甚低頻通信的關(guān)鍵技術(shù)就在于甚低頻接收機的設(shè)計。甚低頻信道噪聲主要成份是脈沖型大氣噪聲即雷電噪聲,目前甚低頻接收機性能測試都是在高斯噪聲環(huán)境下進行,其性能指標只反映接收機在高斯噪聲中的檢測能力。由于甚低頻信道的特殊性,接收機在真實環(huán)境中的性能指標與上述測量值相差很大,即接收機抗雷電干擾的能力無法評估。甚低頻信道噪聲模擬器產(chǎn)生以混合非高斯噪聲模型為基礎(chǔ)的大氣噪聲,可通過參數(shù)設(shè)定模擬不同氣象環(huán)境和不同地域的實時噪聲,構(gòu)建接近真實的參數(shù)化甚低頻信道測量環(huán)境,以有效地評估接收機在真實環(huán)境中的信號檢測能力。另一方面,通過構(gòu)建雷電噪聲發(fā)生器,可以進一步研究改進接收機性能的抗雷電算法,可以大幅度地提高接收機的檢測性能,減少漏報錯報的概率。

構(gòu)建雷電噪聲發(fā)生器的一個重要環(huán)節(jié)就是對自然雷電脈沖的聚類研究。將收集到的自然雷電脈沖按特征進行分類,得到具有代表性的幾類雷電脈沖的平均波形,將平均波形的值作為系數(shù)輸入到成形濾波器。常用的聚類方法有基于劃分、基于層次、基于密度、基于網(wǎng)格的聚類方法,基于劃分的K均值聚類算法具有其他算法所不具有的高效性,并且實現(xiàn)簡單,應(yīng)用廣泛。

2 K-均值算法及其研究現(xiàn)狀

2.1 K-均值算法的基本思想

K-均值聚類算法由J. B. Mac Queen于1967年提出,用來處理數(shù)據(jù)聚類的問題,由于該算法實現(xiàn)簡單,快速高效,適于處理大數(shù)據(jù)集,因此在科學(xué)研究和工業(yè)領(lǐng)域中都得到了廣泛應(yīng)用[2]。該算法解決的是將數(shù)據(jù)集合中的數(shù)據(jù)對象劃分為K個類簇的問題。其基本思想是在數(shù)據(jù)集合中隨機選取K個數(shù)據(jù)對象作為K個類簇的初始中心,計算各數(shù)據(jù)對象到各初始中心的距離,按距離最近原則,各數(shù)據(jù)對象被分到距離最近的那個中心所在的類簇中,形成初始的K個類簇;然后分別計算各類簇中數(shù)據(jù)對象的平均值作為各類簇新的中心,若新的中心與上一次的中心相比沒有發(fā)生變化,則說明各數(shù)據(jù)對象已全部分配到自己所在的類簇中,聚類完成,否則繼續(xù)重復(fù)上述過程,直到聚類中心不再發(fā)生變化。

K-均值聚類算法是一種典型的基于距離的聚類算法,采用距離作為相似性的評價指標,即認為兩個對象的距離越近,其相似度就越大。該算法認為簇是由距離靠近的對象組成的,因此把得到緊湊且獨立的簇作為最終目標。一般采用聚類誤差平方和函數(shù)作為聚類準則函數(shù),聚類誤差平方和函數(shù)的定義為:

其中,K表示類簇的個數(shù),s表示數(shù)據(jù)對象,Ci表示第i個類簇,mi為Ci的質(zhì)心。E值越小,得到的聚類效果越好。

K-均值聚類算法的主要流程如下:

輸入:數(shù)據(jù)對象集合S={s1,s2,…,sn}(每個數(shù)據(jù)對象具有r維特征),類簇的個數(shù)K。

輸出:K個類簇Ci(i=1,2,…,K)。

1) 在數(shù)據(jù)對象集合S中隨機選擇K個數(shù)據(jù)對象作為K個初始簇的初始質(zhì)心;

2) 計算S中各數(shù)據(jù)對象到Oi的距離

i=1,2,…,k,j=1,2,…,n

若滿足

d(sj,Oi)=min(d(sj,Oi),i=1,2,…,k)

則sj∈Ni;

3) 各數(shù)據(jù)對象分配完成后,計算各類簇數(shù)據(jù)對象的平均值作為各類簇新的質(zhì)心Qi(i=1,2,…,k);

4) 計算聚類誤差平方和函數(shù)

若E值收斂,則聚類完成;否則,返回步驟2)。

2.2 K-均值算法的不足

K-均值聚類算法雖然流程簡易,快速有效,但仍然存在一些不足,主要存在以下兩個方面的問題:

1) K-均值聚類算法中的類簇個數(shù)K需要用戶預(yù)先給定,若K值選取的不合適,會使聚類結(jié)果很不理想。但是在實際應(yīng)用中,一般很難預(yù)先確定K值的大小,需要相關(guān)的專業(yè)知識才能對K進行一定的預(yù)測,而預(yù)測的結(jié)果也不一定準確,這顯然給用戶的使用帶來了很大的不便。

2) 由于K個初始中心的選擇是隨機的,K-均值聚類算法對初始中心點的選取具有很大的依賴性,不同的初始值會產(chǎn)生不同的聚類結(jié)果,導(dǎo)致聚類結(jié)果波動較大。另一方面,K-均值聚類算法作為聚類準則的誤差平方和函數(shù)為非凸函數(shù),非凸函數(shù)往往存在多個局部極小值,而全局極小值只有一個。誤差平方和函數(shù)總是按著使其減小的方向進行搜索,不同的初始中心會使搜索沿著不同的路徑進行,搜索到函數(shù)的值不再減小時算法就結(jié)束,得到的往往是局部最優(yōu),而非全局最優(yōu)。

2.3 現(xiàn)有的對于K-均值算法的改進

K-均值聚類算法是數(shù)據(jù)挖掘技術(shù)中應(yīng)用最為廣泛的一種聚類算法?，F(xiàn)有對K-均值聚類算法的改進主要從上面討論的兩個不足點入手,對于初始中心點的改進如下:

Shehroz等[3]提出了聚類中心初始化算法(CCIA)用來確定初始聚類中心。CCIA通過計算各數(shù)據(jù)對象屬性的平均值和標準差來進行劃分,然后將具有正態(tài)曲線的數(shù)據(jù)分到特定的類。實驗測試證明,此算法與隨機選取初始中心的傳統(tǒng)K均值算法相比,聚類結(jié)果準確性更高,但其局限在于其中包含大量復(fù)雜的統(tǒng)計計算。

M.AlDauod[4]提出的算法是選取一系列具有最大方差的中間值,這些中間值從數(shù)據(jù)對象的某一維中提取。他們對不同的數(shù)據(jù)集合進行測試,此算法比其它算法產(chǎn)生更好的聚類結(jié)果。但是由于用到了中間值,此算法容易受離群點影響。

Kohei Arai等[5]利用分層算法來決定初始聚類中心的選取,聚類效果比K-均值算法有所提高。此算法適用于處理具有多維屬性值的大數(shù)據(jù)集。此算法錯分的概率比使用CCIA算法要高。

Mohammed El Agha等[6]利用ElAgha初始化算法,此算法根據(jù)數(shù)據(jù)的整體形狀來確定初始聚類中心,能處理屬性維度大的數(shù)據(jù)。

對于確定K值的改進如下:

Yiu-Ming Cheung[7]提出了一種新的聚類算法—步進式自動競爭—處罰K均值算法(STAR),該算法是傳統(tǒng)K-均值算法的一種歸納,但又克服了以上討論的傳統(tǒng)算法的兩個主要局限。此算法分兩步完成,首先為每個類簇分配至少一個中心,然后按一個具有競爭—處罰機制的規(guī)則來進行調(diào)整。該算法的不足就在于復(fù)雜的計算。

V. Leela等[8]在K-均值算法的基礎(chǔ)上提出了Y-均值算法。它首先對數(shù)據(jù)集執(zhí)行K-均值算法,然后對類簇依次進行分離,刪除,合并操作。此算法的缺陷在于需要先依賴K-均值算法進行聚類。

Mohamed Abubaker等[9]提出的一種新方法能同時解決初始中心點和K值的問題。此算法是基于最近鄰法的原則,有兩種版本,第一種需要同時輸入最近鄰數(shù)據(jù)對象的數(shù)目Kn和聚類數(shù)目K,數(shù)據(jù)點的分類列表將不斷更新直到K到達指定的值,然后算法終止;另一種版本只需要輸入最近鄰數(shù)據(jù)對象的數(shù)目Kn,將同時得到聚類數(shù)目和分類列表。此算法的缺點是需要輸入最近鄰數(shù)據(jù)對象數(shù)目Kn。

B M Shafeeq等[10]提出的算法不需要事先確定K值而是在算法執(zhí)行的過程中找到最佳K值。此算法的缺點是在處理大數(shù)據(jù)集時比傳統(tǒng)K-均值算法花費更多的計算時間,同時用戶在第一次執(zhí)行時需要將K值設(shè)為2。

3 改進的K-均值算法

本文提出的改進算法不需要用戶輸入聚類數(shù)目K,此算法中,首先在數(shù)據(jù)集中選取相距最遠的兩個點作為初始聚類中心,數(shù)據(jù)集被分為兩類,因為初始中心是相距最遠的兩點,所以這兩類所包含的數(shù)據(jù)對象具有最大的不相似度。具體步驟如下:

輸入:具有n個數(shù)據(jù)對象的數(shù)據(jù)集,數(shù)據(jù)對象具有m維屬性A1,A2,…,Am

輸出:n個數(shù)據(jù)對象被合理分配的適當(dāng)個類簇

1) 計算每個數(shù)據(jù)對象所有屬性值的和,為尋找數(shù)據(jù)集中相距最遠的兩個數(shù)據(jù)點做準備;

2) 選取屬性值和最大和最小的兩個數(shù)據(jù)點作為兩個初始聚類中心;

3) 創(chuàng)建初始的兩個類簇,通過計算各數(shù)據(jù)點到各初始聚類中心的距離將數(shù)據(jù)分配到距離最近的中心所在的類簇中;

4) 在兩個初始類簇中尋找數(shù)據(jù)點到初始中心的最小距離,設(shè)其為d(d不等于0);

5) 分別計算步驟3)中兩個初始類簇的數(shù)據(jù)平均值,將其分別設(shè)為兩個類的新質(zhì)心;

6) 計算各數(shù)據(jù)對象到新質(zhì)心的距離,按以下準則找到離群點:若數(shù)據(jù)對象到質(zhì)心的距離小于d,則此數(shù)據(jù)對象不是離群點;

7) 按6)中的準則找到離群點后,將離群點從兩個類中刪掉,形成兩個新的類,重新計算兩個類的平均值,得到新的質(zhì)心;

8) 再分別計算7)中刪掉的離群點到新的質(zhì)心的距離,若滿足6)中的準則,則將此離群點歸入相應(yīng)的類中,將剩余的離群點歸為一類B,設(shè)B={Y1,Y2,…,YP};

9) (1)計算數(shù)據(jù)集B的平均值作為質(zhì)心;

(2)按6)中的準則找到B中的離群點;

(3)如果離群點個數(shù)等于P,選取其中一個離群點作為一個新類C,計算其余離群點到C的距離,若距離小于d,則歸入C中,形成新的類D,其余的依然為離群點;

(4)計算D的平均值得到新的質(zhì)心,計算每個離群點到D的質(zhì)心的距離,若符合6)中準則的則將其歸入D中;

(5)此時B中剩余的離群點為B={Z1,Z2,…,Zq};

10) 重復(fù)9)中的步驟,直到B為空集。

4 實驗測試與分析

為了測試算法的有效性,我們在Matlab中先隨機地生成五個數(shù)據(jù)中心,然后圍繞這五個數(shù)據(jù)中心生成隨機的五組數(shù)據(jù),五組數(shù)據(jù)組成一個大的數(shù)據(jù)集,如圖1所示,然后分別用傳統(tǒng)K-均值算法和改進后的K均值算法對其進行分類,分類結(jié)果分別如圖2和圖3所示。

圖中的星號代表生成的五個數(shù)據(jù)中心,圓圈代表聚類后的五個質(zhì)心,對比圖2和圖3可以明顯地看出改進后的K-均值算法比傳統(tǒng)K均值算法聚類效果好,而且改進K-均值算法不需要用戶手動輸入聚類數(shù)目K,減小了用戶的使用難度。

圖1 Matlab生成的數(shù)據(jù)集

圖2 傳統(tǒng)K-均值算法的聚類結(jié)果

圖3 改進K-均值算法的聚類結(jié)果

為了實現(xiàn)對自然雷電波形的分類并進一步驗證改進K-均值聚類算法的準確性,分別用傳統(tǒng)K-均值算法和改進后的K均值算法對自然雷電波形進行分類。由于自然雷電脈沖的幅值差別較大,若直接采用原始雷電脈沖進行分類,峰值大的雷電個體將占有極大的權(quán)重,在聚類過程中,這些雷電會很自然的聚在一起,而忽略了波形的相似程度,所以我們將原始雷電脈沖進行歸一化后再進行聚類。我們總共采集到153個雷電脈沖,每個雷電脈沖大約持續(xù)800個樣點,通過觀察可以發(fā)現(xiàn)最具代表性的雷電沖擊集中在第250到500個樣點之間,所以提取出每個波形的第250～第500個樣點作為實驗數(shù)據(jù),如圖4所示,相當(dāng)于用于聚類的數(shù)據(jù)集合中共有153個數(shù)據(jù)對象,每個數(shù)據(jù)對象的維數(shù)為251。

圖4 歸一化后的雷電脈沖

使用傳統(tǒng)K-均值算法和改進后的K均值算法進行聚類后的結(jié)果分別如圖5和圖6所示。

圖5 傳統(tǒng)K-均值算法的雷電脈沖聚類結(jié)果

圖6 改進K-均值算法的雷電脈沖聚類結(jié)果

每組的三個波形為聚類后每個類簇的平均波形,對比圖5和圖6可以看出,使用改進K-均值算法所得到的三個類簇差異性更大,聚類的本質(zhì)就是要使相近的數(shù)據(jù)對象分到同一個類簇,而不同類簇中的數(shù)據(jù)對象保持高的差異度,所以改進后的K-均值算法得到的聚類結(jié)果更為合理。

5 結(jié)語

傳統(tǒng)K-均值聚類算法易受初始中心點選擇的影響而且需要手動輸入聚類的個數(shù)K,給用戶帶來極大的不便,同時,若初始中心和K值選擇不當(dāng),聚類效果會很差。本文提出的改進K-均值聚類算法避開了初始中心點的隨機選擇,只需計算數(shù)據(jù)集合中相距最遠的兩個點將其設(shè)為初始中心,同時也避開了K值的設(shè)定,聚類效果較傳統(tǒng)K-均值聚類算法更為理想。本算法的局限在于只適合處理數(shù)值型數(shù)據(jù),所以還需要繼續(xù)研究,使其能對多種類型的數(shù)據(jù)進行聚類。

[1] 梁高權(quán).甚低頻波和超低頻波的輻射與傳播[M].武漢:海軍工程大學(xué)出版社,2002:3-5.

[2] 王慧,申石磊.基于改進的K均值聚類彩色圖像分割方法[J].電腦知識與技術(shù),2010,6(4):962-964.

[3] Shehroz, Ahmad. Cluster center initiation algorithm for K-means clustering[J]. Pattern Recognition Letters 25,2004,2(1):1293-1302.

[4] M. AlDauod. A New Algorithm for Cluster Initialization[J]. World Academy of Science, Engineering and Technology,2007,4(1):102-107.

[5] Kohei Arai, Ali Ridho Barakha. Hierarchical K-means: An algorithm for centroids initialization for K-means[J]. Reports of the Faculty of Science and Engineering,2007,36(1):25-31.

[6] Mohammed El Agha, Wesam M. Ashour. Efficient and Fast Initializtion Algorithm for K-means Clustering[J]. I. J. Intelligent Systems and Applications,2012,4(1):21-31.

[7] Yiu-Ming Cheung. k*-Means: A new generalized kmeans clustering algorithm[J]. Pattern Recognition Letters 24,2003,3(2):2883-2893.

[8] V. Leela, K. Sakthipriya, R. Manikandan. A comparative analysisbetween k-mean and y-means Algorithms in Fisher’s Iris data sets[J]. International Journal of Engineering and Technology,2013,5(1):245-249.

[9] Mohamed Abubaker, Wesam Ashour. Efficient Data Clustering Algorithms: Improvements over K-means[J]. International Journal of Intelligent Systems and Applications,2013,5(3):37-49.

[10] B M AhamedShafeeq, K S Hareesha. DynamicClustering of Data with Modified K-Means Algorithm[J]. International Conference on Information and Computer Networks(ICICN 2012),2012,27:221-225.

Classification of Lightning Pulses Based on Improved K-Means Clustering Algorithm

PENG Dan ZHANG Shuxia

(College of Electronic Engineering, Naval University of Engineering, Wuhan 430033)

K-means has gained popularity because of its simplicity and rapid speed of classifying massive data rapidly and efficiently. However, the output of K-Means clustering algorithm highly depends upon the selection of initial cluster centers because the initial cluster centers are chosen randomly. The other limitation ofthe algorithm is to input the required number of clusters. This requires some sort of intuitive knowledge about appropriate value ofKwhich is sometimes difficult to predict as it requires domainknowledge. If the value ofKis not appropriate, the output of K-Means clustering algorithm will be bad. In this paper, we have proposed an algorithm based on the K-Means, but it avoids randomly choosing of the initial cluster centers, only setting the farthest two points in the data set as theinitial cluster centers. On the other hand, it does not require the number of clustersKas input. It greatly reduces the user’s difficulty and increases the quality of the result. This paper applys the improved K-means clustering algorithm to the classification of natural lightning pulses and makes a comparison with traditional K-means clustering algorithm.

K-means clustering, initial cluster centers, number of clusters, natural lightning pulses

2015年4月4日,

2015年5月27日

彭丹,女,碩士研究生,研究方向:通信理論與技術(shù)、甚低頻信道探測技術(shù)。張曙霞,女,副教授,研究方向:通信技術(shù)。

TP301.6

10.3969/j.issn.1672-9730.2015.10.012