隋心怡 王瑞剛 張鴻翔

（1.西安郵電大學(xué)計(jì)算機(jī)學(xué)院 西安 710061）（2.西安交通大學(xué)電子與信息工程學(xué)院 西安 710049）

1 引言

聚類(lèi)問(wèn)題是指依據(jù)樣本的某些屬性或按照某種標(biāo)準(zhǔn)，將樣本分為多個(gè)類(lèi)，并使相同類(lèi)中的樣本相似度盡可能大，不同類(lèi)中的樣本相似度盡可能?。?］。為解決聚類(lèi)問(wèn)題，研究人員提出了多種聚類(lèi)算法，主要有：基于劃分的算法、基于層次的算法、基于密度的算法、基于網(wǎng)絡(luò)的算法、基于模型的算法以及其他形式的算法［2～5］。

基于劃分的聚類(lèi)算法是最早提出，也是最常用的經(jīng)典聚類(lèi)算法［6］。該類(lèi)算法通過(guò)選擇k個(gè)初始聚類(lèi)中心（代表k個(gè)類(lèi)），然后根據(jù)其他樣本與中心點(diǎn)的距離，將每個(gè)樣本劃分到與它距離最近的類(lèi)中，從而實(shí)現(xiàn)樣本聚類(lèi)［7］。

K-均值聚類(lèi)算法就是一種基于劃分的聚類(lèi)算法［8］，由于其原理簡(jiǎn)單易于實(shí)現(xiàn)，在多個(gè)領(lǐng)域中都有廣泛的應(yīng)用。但是傳統(tǒng)的K-均值聚類(lèi)算法易受初始點(diǎn)影響，當(dāng)初始點(diǎn)選擇不當(dāng)時(shí)，甚至無(wú)法得到正確聚類(lèi)結(jié)果［9～10］，算法穩(wěn)定性較差。鑒于K-均值聚類(lèi)算法存在的缺陷，如何選取聚類(lèi)初始點(diǎn)一直是其算法改進(jìn)的重要方向［11］。

本文根據(jù)樣本的空間分布動(dòng)態(tài)選取初始聚類(lèi)中心，提出了一種改進(jìn)的K-均值聚類(lèi)算法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法提高了穩(wěn)定性，并取得了較高的分類(lèi)準(zhǔn)確率。

2 K-均值聚類(lèi)算法

K-均值聚類(lèi)算法首先需要輸入聚類(lèi)個(gè)數(shù)k，然后隨機(jī)選擇k個(gè)樣本作為聚類(lèi)中心；通過(guò)計(jì)算剩余樣本與聚類(lèi)中心的距離，將樣本歸入與其距離最近的類(lèi)；當(dāng)所有樣本計(jì)算結(jié)束后，根據(jù)當(dāng)前聚類(lèi)結(jié)果更新聚類(lèi)中心；通過(guò)循環(huán)迭代直到目標(biāo)函數(shù)［12］滿足一定要求或達(dá)到最大迭代次數(shù)時(shí)聚類(lèi)結(jié)束。

目標(biāo)函數(shù)用于度量聚類(lèi)結(jié)果的好壞，其定義如下

K-均值聚類(lèi)算法常采用歐氏距離［13］表示樣本與聚類(lèi)中心的遠(yuǎn)近，此時(shí)目標(biāo)函數(shù)也稱(chēng)為平方誤差準(zhǔn)則函數(shù)：

當(dāng)一次迭代結(jié)束后，需要更新聚類(lèi)中心，更新公式為

式中nj為第 j類(lèi)中的樣本個(gè)數(shù)，cj*為新的聚類(lèi)中心。

算法流程：

1）從樣本中隨機(jī)選取k個(gè)對(duì)象作為初始聚類(lèi)中心；

2）計(jì)算樣本與k個(gè)聚類(lèi)中心的距離，將樣本歸入距離最近的類(lèi)中；

3）根據(jù)式（3）計(jì)算新的聚類(lèi)中心；

客觀原因主要包括：由于溫度變化而引起變形、地基地質(zhì)構(gòu)造存在較大差別、地下水位上升或降低導(dǎo)致高速公路地基被侵蝕、土壤物理性質(zhì)存在較大差異，以上各項(xiàng)客觀因素都會(huì)對(duì)造成軟土地基發(fā)生沉降，從而會(huì)對(duì)高速公路最終質(zhì)量造成較為嚴(yán)重的影響，影響高速公路施工，以及工程竣工后的應(yīng)用。

4）重復(fù)步驟2）、3），直至滿足結(jié)束條件；

5）計(jì)算結(jié)束，得到聚類(lèi)結(jié)果。

3 改進(jìn)的K-均值聚類(lèi)算法

初始聚類(lèi)中心的選擇直接影響到K-均值聚類(lèi)算法的性能，這導(dǎo)致傳統(tǒng)的K-均值聚類(lèi)算法性能較不穩(wěn)定［14］。一方面，若隨機(jī)選取的初始聚類(lèi)中心距離較近，會(huì)導(dǎo)致算法迭代次數(shù)較多甚至聚類(lèi)出現(xiàn)偏差，因?yàn)榫嚯x較近的兩個(gè)樣本更有可能屬于同一類(lèi)而不是不同類(lèi)，所以選取相互之間距離較遠(yuǎn)的k個(gè)樣本作為初始點(diǎn)更具有代表性；另一方面，若一味地尋找相距較遠(yuǎn)的初始點(diǎn)，有可能會(huì)取到孤立點(diǎn)，也不利于聚類(lèi)。通過(guò)觀察數(shù)據(jù)樣本的空間分布發(fā)現(xiàn)，實(shí)際的聚類(lèi)中心所在的區(qū)域往往密度較高，即這一區(qū)域內(nèi)的樣本數(shù)量要大于其他區(qū)域。針對(duì)上述先驗(yàn)知識(shí)，本文改進(jìn)了初始聚類(lèi)中心的選取方法，根據(jù)樣本所在空間的分布密度，并結(jié)合樣本間最大距離選取初始聚類(lèi)中心。

設(shè)待聚類(lèi)的m個(gè)n維數(shù)據(jù)樣本為X，所處空間范圍為RN，可表示為

定義子空間r（r∈RN）的樣本密度為該子空間內(nèi)的樣本數(shù)量，記作ρr。如果一個(gè)子空間的樣本密度不小于ρmin，則該子空間為高密度子空間，ρmin為高密度子空間閾值。

兩個(gè) n維數(shù)據(jù) x1(α1，α2，…，αn)、x2(β1，β2，…，βn)間的距離定義為

改進(jìn)后的K-均值聚類(lèi)算法流程如下：

1）設(shè)定聚類(lèi)個(gè)數(shù)k、高密度子空間閾值ρmin；

2）選定正整數(shù)l，將輸入樣本所處的n維空間等分為ln（ln＞2k）個(gè)子空間，計(jì)算各子空間ri的樣本密度 ρri，并將密度不小于ρmin的子空間放入高密度子空間集合Dρ，統(tǒng)計(jì)高密度子空間數(shù)量；

3）若高密度子空間數(shù)量小于聚類(lèi)個(gè)數(shù)k，返回1），調(diào)整閾值 ρmin；

4）選取密度最高的子空間，計(jì)算該空間內(nèi)樣本點(diǎn)的平均距離，設(shè)為第一個(gè)初始聚類(lèi)中心c1；

5）計(jì)算c1與其他高密度子空間中心的距離，選取與其距離最遠(yuǎn)的高密度子空間，計(jì)算該空間內(nèi)樣本點(diǎn)的平均距離，得到第二個(gè)初始聚類(lèi)中心c2；

6）計(jì)算c1、c2與其他高密度子空間中心的距離和，按照最大距離準(zhǔn)則選取高密度子空間，并計(jì)算得到聚類(lèi)中心c3；

7）繼續(xù)按照6）的方法尋找聚類(lèi)中心，直到找到第k個(gè)聚類(lèi)中心ck；

8）將k個(gè)初始聚類(lèi)中心帶入傳統(tǒng)的K-均值聚類(lèi)算法進(jìn)行聚類(lèi)，得到聚類(lèi)結(jié)果。

4 實(shí)驗(yàn)結(jié)果及分析

本文使用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)［15］對(duì)傳統(tǒng)k均值算法和改進(jìn)算法進(jìn)行對(duì)比實(shí)驗(yàn)。選取Iris、Wine和Glass三組數(shù)據(jù)作為測(cè)試數(shù)據(jù)集。為了使結(jié)果更加直觀，首先將三個(gè)測(cè)試數(shù)據(jù)集不同屬性值做歸一化處理，并其降維至二維空間。

采用傳統(tǒng)k均值算法進(jìn)行30次實(shí)驗(yàn)，取平均值作為實(shí)驗(yàn)最終結(jié)果；由于改進(jìn)算法計(jì)算出的初始聚類(lèi)中心是固定的，所以只進(jìn)行一次試驗(yàn)，并將其結(jié)果作為最終結(jié)果。實(shí)驗(yàn)結(jié)果如表1所示。

由表1可以看出，采用本文提出的改進(jìn)算法得到的聚類(lèi)精度要好于傳統(tǒng)的k均值算法。

表1 算法精度比較

為對(duì)比兩算法的運(yùn)算效率，實(shí)驗(yàn)還統(tǒng)計(jì)了算法的迭代次數(shù)和運(yùn)行時(shí)間，結(jié)果如表2所示。由于本文提出的改進(jìn)算法根據(jù)樣本點(diǎn)的空間分布選取初始聚類(lèi)中心，算法迭代次數(shù)要明顯少于傳統(tǒng)k均值算法；但因?yàn)楦倪M(jìn)算法要統(tǒng)計(jì)所有樣本點(diǎn)的空間分布，會(huì)犧牲一定的時(shí)間，所以改進(jìn)算法的運(yùn)行時(shí)間要大于傳統(tǒng)的k均值算法。

表2 算法迭代次數(shù)與運(yùn)行時(shí)間比較

此外，通過(guò)觀察采用傳統(tǒng)k均值算法進(jìn)行的30次實(shí)驗(yàn)，發(fā)現(xiàn)各實(shí)驗(yàn)間結(jié)果相差較大，這也表明由于傳統(tǒng)k均值算法的初始聚類(lèi)中心是隨機(jī)選擇的，結(jié)果隨機(jī)性較強(qiáng)，算法穩(wěn)定性較差。而本文提出的改進(jìn)算法在參數(shù)設(shè)置確定的情況下，實(shí)驗(yàn)結(jié)果也是固定的，穩(wěn)定性好于傳統(tǒng)k均值算法。

5 結(jié)語(yǔ)

本文在傳統(tǒng)K-均值聚類(lèi)算法的基礎(chǔ)上，將樣本點(diǎn)分布密度與初始點(diǎn)選取相結(jié)合，提出了一種改進(jìn)的K-均值聚類(lèi)算法，實(shí)驗(yàn)結(jié)果表明，本算法的聚類(lèi)精度和穩(wěn)定性都要好于傳統(tǒng)的K-均值聚類(lèi)算法。

由于本文提出的算法需要分割樣本所處的n維空間，當(dāng)樣本屬性值較多時(shí)，會(huì)導(dǎo)致分割得到的子空間數(shù)量較多，不利于之后的處理。所以本算法適用于對(duì)屬性值較少的數(shù)據(jù)集進(jìn)行聚類(lèi)；當(dāng)屬性值較多時(shí)，需要先進(jìn)行預(yù)處理，舍棄部分相關(guān)屬性或?qū)傩灾低队暗降途S空間，然后再使用本算法進(jìn)行聚類(lèi)。此外，算法中的參數(shù)會(huì)影響數(shù)據(jù)集的聚類(lèi)效果，如何針對(duì)不同數(shù)據(jù)集設(shè)置合理的參數(shù)也是今后的研究方向之一。

［1］李桂林，陳曉云.關(guān)于聚類(lèi)分析中相似度的討論［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40（31）：64-65.LI Guilin，CHEN Xiaoyun.The Discussion on the Similar?ity of Cluster Analysis［J］.Computer Engineering and Ap?plications，2004，40（31）：64-65.

［2］席景科，譚海樵.空間聚類(lèi)分析及評(píng)價(jià)方法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（7）：1712-1715.XI Jingke，TAN Haiqiao.Spatial clustering analysis and its evaluation［J］.Computer Engineering and Design，2009，30（7）：1712-1715.

［3］賈璦瑋.基于劃分的聚類(lèi)算法研究綜述［J］.電子設(shè)計(jì)工程，2014（23）：38-41.JIA Aiwei.Survey on partitional clustering algorithms［J］.Electronic Design Engineering，2014（23）：38-41.

［4］李新良.基于層次聚類(lèi)算法的改進(jìn)研究［J］.軟件導(dǎo)刊，2007（19）：141-142.LI Xinliang.Improved Research of Hierarchical Cluster Algorithm［J］.Software Guide，2007（19）：141-142.

［5］羅軍鋒，鎖志海.一種基于密度的k-means聚類(lèi)算法［J］.微電子學(xué)與計(jì)算機(jī)，2014（10）：28-31.LUO Junfeng，SUO Zhihai.A Density Based k-means Clustering Algorithm［J］.Microelectronics&Computer，2014（10）：28-31.

［6］尹成祥，張宏軍，張睿，等.一種改進(jìn)的K-Means算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2014（10）：30-33.YI Chengxiang，ZHANG Hongjun，ZHANG Rui，et al.An Improved K-means Algorithm［J］.Computer Applications，2014（10）：30-33.

［7］段桂芹.基于均值與最大距離乘積的初始聚類(lèi)中心優(yōu)化K-means算法［J］.計(jì)算機(jī)與數(shù)字工程，2015（3）：379-382.DUAN Guiqin.Automatic Generation Cloud Optimization Based on Genetic Algorithm［J］.Computer&Digital Engi?neering，2015（3）：379-382.

［8］王千，王成，馮振元，等.K-means聚類(lèi)算法研究綜述［J］.電子設(shè)計(jì)工程，2012，20（7）：21-24.WANG Qian，WANG Cheng，F(xiàn)ENG Zhenyuan，et al.Re?view of K-means clustering algorithm［J］.Electronic De?sign Engineering，2012，20（7）：21-24.

［9］胡偉.改進(jìn)的層次K均值聚類(lèi)算法［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49（2）：157-159.HU Wei.Improved hierarchical K-means clustering algo?rithm.Computer Engineering and Applications［J］.2013，49（2：157-159.

［10］鄭丹，王潛平.K-means初始聚類(lèi)中心的選擇算法［J］.計(jì)算機(jī)應(yīng)用，2012，32（8）：2186-2188.ZHENG Dan，WANG Qianpin.Selection algorithm for K-means initial clustering center［J］.Journal of Comput?er Applications，2012，32（8）：2186-2188.

［11］王曉燕.常用的聚類(lèi)算法及改進(jìn)算法的研究［J］.辦公自動(dòng)化：學(xué)術(shù)版，2013，3（9）：49-52.WANG Xiaoyan.Commonly Used Clustering Algorithm and Improved Algorithm Research［J］.Office Automa?tion，2013，3（9）：49-52.

［12］Meng Jianliang，Shang Hai kun，Bian Ling.The applica?tion on intrusion detection based on K-means cluster al?gorithm［C］.International Forum on Information Technol?ogy and Applications，2009：150-152.

［13］Liu X M，Lei D.An improved K-Means clustering algo?rithm［J］.Journal of Networks，2014，9（1）：1-3.

［14］Wu J.K-means Based Consensus Clustering［J］.Knowl?edge&Data Engineering IEEE Transactions on，2015，27（1）：155-169.

［15］University B I.Uci machine learning.ftp.ics.uci.edu/pub/machine-learning-databases［J］.2010.