彭 丹 張曙霞

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

?

基于改進(jìn)K-Means算法的雷電脈沖分類研究*

彭 丹 張曙霞

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

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

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

Class Number TP301.6

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

2) 計(jì)算S中各數(shù)據(jù)對(duì)象到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ù)對(duì)象分配完成后,計(jì)算各類簇?cái)?shù)據(jù)對(duì)象的平均值作為各類簇新的質(zhì)心Qi(i=1,2,…,k);

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

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

2.2 K-均值算法的不足

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

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

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

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

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

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

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

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

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

對(duì)于確定K值的改進(jìn)如下:

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

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

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

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

3 改進(jìn)的K-均值算法

本文提出的改進(jìn)算法不需要用戶輸入聚類數(shù)目K,此算法中,首先在數(shù)據(jù)集中選取相距最遠(yuǎn)的兩個(gè)點(diǎn)作為初始聚類中心,數(shù)據(jù)集被分為兩類,因?yàn)槌跏贾行氖窍嗑嘧钸h(yuǎn)的兩點(diǎn),所以這兩類所包含的數(shù)據(jù)對(duì)象具有最大的不相似度。具體步驟如下:

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

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

1) 計(jì)算每個(gè)數(shù)據(jù)對(duì)象所有屬性值的和,為尋找數(shù)據(jù)集中相距最遠(yuǎn)的兩個(gè)數(shù)據(jù)點(diǎn)做準(zhǔn)備;

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

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

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

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

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

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

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

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

(2)按6)中的準(zhǔn)則找到B中的離群點(diǎn);

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

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

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

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

4 實(shí)驗(yàn)測(cè)試與分析

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

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

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

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

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

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

圖4 歸一化后的雷電脈沖

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

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

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

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

5 結(jié)語(yǔ)

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

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

[2] 王慧,申石磊.基于改進(jìn)的K均值聚類彩色圖像分割方法[J].電腦知識(shí)與技術(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ù)、甚低頻信道探測(cè)技術(shù)。張曙霞,女,副教授,研究方向:通信技術(shù)。

TP301.6

10.3969/j.issn.1672-9730.2015.10.012