周其林，雷菊陽(yáng)，王昱棟，張?zhí)m蘭

（上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院，上海 201620）

聚類分析是一種將沒有類別標(biāo)記的對(duì)象集按照某種規(guī)則分為若干個(gè)類，同一類中各對(duì)象的屬性盡可能相似，不同類中各對(duì)象的屬性會(huì)有較大差異。聚類分析是一種無監(jiān)督學(xué)習(xí)方法，能夠通過特征數(shù)據(jù)挖掘出對(duì)象的相似性，它在模式識(shí)別、特征提取、數(shù)據(jù)挖掘等領(lǐng)域都有廣泛應(yīng)用［1－3］。

k－均值聚類算法是聚類分析中的經(jīng)典算法，具有算法簡(jiǎn)單、收斂速度快等特點(diǎn)［4］。但也有2個(gè)缺點(diǎn)：第一是需要事先知道聚類數(shù)；第二是初始種群的選取是隨機(jī)的。近年來，為了解決這兩大缺陷，對(duì)k－均值聚類算法進(jìn)行了很多改進(jìn)，如結(jié)合智能優(yōu)化算法對(duì)k－均值聚類算法進(jìn)行改進(jìn)，但改進(jìn)后的算法通常比較復(fù)雜，這就使傳統(tǒng)k－均值聚類算法簡(jiǎn)單高效的特點(diǎn)不復(fù)存在，算法的收斂性方面也存在不足［5－7］。

1 傳統(tǒng)k－均值聚類算法及其缺陷

1.1 k－均值聚類算法

k－均值聚類算法簡(jiǎn)單，且聚類速度快，這是其最大的優(yōu)點(diǎn)。k－均值聚類算法包括2個(gè)獨(dú)立的步驟：第1步就是隨機(jī)地選擇k個(gè)數(shù)據(jù)作為聚類中心，其中k值是已知的；第2步就是計(jì)算每個(gè)點(diǎn)到這k個(gè)中心的距離，距離的計(jì)算通常采用歐氏距離，如果第i個(gè)點(diǎn)到第j個(gè)中心的距離最短，則這第i個(gè)點(diǎn)就被劃分到第j個(gè)類中，當(dāng)所有點(diǎn)都被劃分好后，修改中心點(diǎn)的值為該類所有樣本的均值，然后再重新計(jì)算距離，重新劃分，重新計(jì)算中心，直到這k個(gè)聚類中心不再變化，算法結(jié)束［8－10］。

對(duì)于向量x＝（x1，x2，…，xn）和向量y＝（y1，y2，…，yn）的歐氏距離定義為

k－ 均值聚類算法的實(shí)現(xiàn)：

輸入 聚類數(shù)k以及樣品x＝｛x1，x2，…，xn｝；

輸出k個(gè)類中每個(gè)類所含的樣品λ1，λ2，…，λk。

步驟：

Step1 從樣品x中隨機(jī)選取k個(gè)數(shù)據(jù)作為初始聚類中心μ1，μ2，…，μk。

Step2 對(duì)于每個(gè)點(diǎn)xi，計(jì)算其到各中心的距離。

dic＝‖xi－μc‖2，其中c＝1，2，…，k。將它們歸于距離最近的類，直到所有的樣品都?xì)w類完畢。

Step3 計(jì)算各類中所有樣品特征值的平均值作為新的聚類中心，對(duì)于每個(gè)簇

Step4 重復(fù)Step2和Step3直到聚類中心不再發(fā)生改變，算法結(jié)束。

1.2 k－ 均值聚類算法的缺陷

k－均值聚類算法最大的缺陷就是要知道確定的聚類數(shù)k，但在實(shí)際中聚類數(shù)k往往是不易得到的，這就使得算法在解決很多聚類問題上有很大的局限性［11－12］。此外，這種算法的初始種群是隨機(jī)選取的，而初始種群的選取對(duì)聚類結(jié)果又會(huì)產(chǎn)生很大的影響，使得聚類結(jié)果不穩(wěn)定，甚至導(dǎo)致聚類結(jié)果失真。這種算法還有一個(gè)缺陷，就是易陷入局部最優(yōu)，使得聚類結(jié)果偏離全局最優(yōu)。

2 新聚類算法

2.1 算法綜述

算法中引入懲罰參數(shù)λ，這種算法是基于遞增思想的聚類算法。首先讓聚類數(shù)k為1，則所有的樣品都屬于這一個(gè)類，該類的中心為所有樣品特征值的平均值，對(duì)于每個(gè)點(diǎn)，計(jì)算其到該中心的距離。當(dāng)檢測(cè)到存在點(diǎn)到該中心的距離大于λ時(shí)，聚類數(shù)k加1，然后重新計(jì)算每個(gè)點(diǎn)到這k個(gè)中心的距離，將每個(gè)點(diǎn)劃分到距其距離最短的中心的類中，然后根據(jù)每類中的樣品修改聚類中心，然后再計(jì)算每個(gè)點(diǎn)到這k個(gè)中心的距離；當(dāng)檢測(cè)到存在點(diǎn)到這k個(gè)中心的最短距離大于λ時(shí)，聚類數(shù)k再加1，以此迭代下去，直到k收斂，即k的值不再發(fā)生變化，此時(shí)所有的樣品點(diǎn)到這k個(gè)中心的最短距離都小于λ，算法結(jié)束。

這種算法最大的特色是事先不需要知道聚類數(shù)k，而只需確定懲罰參數(shù)λ的值即可（λ值的確定方法將會(huì)在后文中介紹），這就解決了傳統(tǒng)k－ 均值聚類算法的最大缺陷，拓展了其應(yīng)用范圍。其次，這種算法的初始聚類中心為所有樣品特征值的平均值，而且對(duì)于新增的類，其聚類中心的選取也是根據(jù)一定的算法得到確定的點(diǎn)，使聚類結(jié)果具有很大的穩(wěn)定性，這就避免了傳統(tǒng)k－均值聚類算法初始中心隨機(jī)選擇而導(dǎo)致聚類結(jié)果不穩(wěn)定，甚至?xí)霈F(xiàn)失真的情形。此外，這種算法具有全局性，可以很好地避免聚類陷入局部最優(yōu)。

對(duì)于向量x＝（x1，x2，…，xn）和向量y＝（y1，y2，…，yn）的歐氏距離定義為

算法的實(shí)現(xiàn)：

輸入 樣品x＝｛x1，x2，…，xn｝，懲罰參數(shù)λ；

輸出 每個(gè)類中所含樣品λ1，λ2，…，λn，以及簇的個(gè)數(shù)k。

步驟：

Step1 初始化k＝1，λ1＝｛x1，x2，…，xn｝，初始聚類中心為全局均值μ1。

Step2 計(jì)算每個(gè)樣品點(diǎn)到各中心的距離dic＝‖xi－μc‖，μc為第c個(gè)聚類中心，其中c＝1，2，…，k。

Step3 如果mincdic＞λ，令k＝k＋1，且μk＝xi，重復(fù)Step2，然后將各點(diǎn)劃分到距其最近的簇，屬于第j類的樣品放在?i中，并根據(jù)來修改聚類中心，其中｜?j｜表示?i中樣品的個(gè)數(shù)。本次計(jì)算結(jié)束條件是聚類中心不再發(fā)生變化或者是達(dá)到設(shè)定的最大迭代次數(shù)，否則進(jìn)入下一步。

Step4 重復(fù)Step2和Step3，直到收斂。

2.2 懲罰參數(shù)λ 的確定

懲罰參數(shù)λ的確定是這種算法的難點(diǎn)，本文給出了確定λ的一種方法。算法中每給定一個(gè)λ就可以得到一個(gè)k，這樣就能得到隨λ變化k也變化的趨勢(shì)，進(jìn)而通過觀察k的變化特征來確定λ的值。不難理解，當(dāng)λ很小時(shí)，聚類數(shù)k就會(huì)很大，特別地，對(duì)于n個(gè)樣品，當(dāng)λ為0時(shí)，k等于n，而隨著λ的增大k會(huì)越來越小，而且k變小的趨勢(shì)會(huì)越來越平緩，其中會(huì)有很長(zhǎng)一段k的值是不變化的，這一段對(duì)應(yīng)的k值就是合理的聚類數(shù)，然后在這一段中選取一個(gè)合適的λ值。

新的算法和傳統(tǒng)的k－均值聚類算法一樣，都對(duì)球形簇有較好的聚類效果，所以下面就以2個(gè)球形簇的聚類問題來進(jìn)一步說明這樣選取λ的合理性。假設(shè)這2個(gè)球形簇中較大的一個(gè)球形簇的半徑為r，當(dāng)λ小于r時(shí)，隨著λ的增大k的變化是明顯的，而當(dāng)λ大于r時(shí)，此時(shí)k等于2，而且在很大范圍內(nèi)，k的值是不變化的，直到λ足夠大時(shí)，k變?yōu)?，在這個(gè)很大范圍內(nèi)即可選取對(duì)應(yīng)的一個(gè)λ值作為合適的懲罰參數(shù)。

本文采用的方法是作出聚類數(shù)k隨參數(shù)λ變化的趨勢(shì)圖，從而確定參數(shù)λ的值。為了提高計(jì)算的速度，可適當(dāng)限定λ的范圍。當(dāng)λ很小，甚至為0時(shí)，聚類數(shù)k就等于樣本的個(gè)數(shù)，這樣計(jì)算量就很大，很耗時(shí)，對(duì)計(jì)算時(shí)間影響最大的就是λ的下限，因此有必要對(duì)λ的最小值進(jìn)行限制。首先計(jì)算出所有樣本點(diǎn)到初始聚類中心的歐氏距離，記最小距離為dmin，最大距離為dmax。λ的下限取為dmin，這樣對(duì)判斷λ的值沒有影響，而且大大縮短了計(jì)算時(shí)間。為了進(jìn)一步縮短計(jì)算時(shí)間，對(duì)λ的上限也進(jìn)行限制，根據(jù)實(shí)際情況，λ的取值一定不會(huì)超過dmax，因此可取λ的上限為dmax。

3 實(shí)驗(yàn)一：茶葉分類實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)針對(duì)不同地區(qū)的紅茶和綠茶，包含6個(gè)分類特征，分別是：纖維素、半纖維素、木質(zhì)素、多酸、咖啡因、氨基酸，對(duì)23個(gè)樣品進(jìn)行聚類。數(shù)據(jù)如表1所示。

表1 兩種茶葉的化學(xué)分析數(shù)據(jù)Tab.1 Data of the two kinds of tea’s chemical analysis

3.2 數(shù)據(jù)預(yù)處理

一個(gè)樣品中不同的特征值往往采用不同的度量單位，其值可能相差較大，因此有必要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理以提高數(shù)據(jù)質(zhì)量［13］，首先對(duì)這23 個(gè)樣品的各特征的化學(xué)分析數(shù)據(jù)進(jìn)行預(yù)處理，對(duì)數(shù)據(jù)進(jìn)行最小－最大規(guī)范化：

3.3 參數(shù)的確定

實(shí)驗(yàn)采用Matlab R2008A 開發(fā)環(huán)境編程實(shí)現(xiàn)，如圖1所示，以λ為橫軸，聚類數(shù)k為縱軸建立坐標(biāo)系，從圖1中可以看出，隨著λ的增大，聚類數(shù)k的值總體上在逐漸減小，當(dāng)λ的值大于0.14之后，聚類數(shù)k的值就穩(wěn)定在2類，即實(shí)驗(yàn)中茶葉的分類數(shù)為2類，這與實(shí)際情況也是符合的，此時(shí)就可以在橫軸（0.14，0.22）上選取一個(gè)值作為λ的值，不妨取λ等于0.18。

圖1 聚類數(shù)k隨λ 變化的趨勢(shì)圖Fig.1 Trend of k with the increase ofλ

3.4 實(shí)驗(yàn)結(jié)果

將3.3中得到的λ值0.18輸入到Matlab程序中，得到的聚類結(jié)果如表2和表3所示。類1代表紅茶，類2代表綠茶。

表2 最終聚類中心Tab.2 Final cluster center

3.5 聚類結(jié)果分析

由表3的聚類分析最終結(jié)果可以看出，這種聚類算法的正確率為91.3%，表現(xiàn)出很好的聚類效果。從表2的最終聚類中心可以看出，紅茶（類1）的半纖維素、木質(zhì)素、氨基酸含量較高，而綠茶（類2）的多酸含量較高，而兩種茶的咖啡因和纖維素的含量相差不大。

表3 聚類分析最終結(jié)果Tab.3 Final result of cluster analysis

4 實(shí)驗(yàn)二：各地區(qū)各行業(yè)工資水平分析

實(shí)驗(yàn)對(duì)中國(guó)31個(gè)不同省、市（不含港、澳、臺(tái)）的平均工資水平進(jìn)行了分析，包括15個(gè)主要行業(yè)的平均工資水平，這15個(gè)行業(yè)分別是企業(yè)、非農(nóng)企業(yè)、事業(yè)、農(nóng)林牧漁業(yè)、采礦業(yè)、制造業(yè)、電力燃?xì)夂退墓?yīng)業(yè)、建筑業(yè)、交通運(yùn)輸業(yè)、信息傳輸業(yè)、批發(fā)和零售業(yè)、住宿和餐飲業(yè)、金融業(yè)、房地產(chǎn)業(yè)以及租賃和商務(wù)服務(wù)業(yè)。數(shù)據(jù)來源于《中國(guó)勞動(dòng)統(tǒng)計(jì)年鑒—2010》，具體數(shù)據(jù)略。

4.1 參數(shù)λ 的確定

從圖2中可以看出，λ可取0.347 5，此時(shí)對(duì)應(yīng)的聚類數(shù)k為3。

4.2 實(shí)驗(yàn)結(jié)果

將λ＝0.347 5輸入到Matlab程序中，可得到聚類結(jié)果，如表4和表5所示。結(jié)果分成3類，由表4可以看出，第1類的平均工資水平很高，第2類居中，第3類較低。

圖2 聚類數(shù)k隨λ 變化的趨勢(shì)圖Fig.2 Trend of k with the increase ofλ

表4 最終聚類中心Tab.4 Final cluster center

表5 聚類結(jié)果Tab.5 Final result of clustering

4.3 聚類結(jié)果分析

實(shí)驗(yàn)的正確率達(dá)到100%，實(shí)驗(yàn)結(jié)果與事實(shí)相符，從表5的聚類結(jié)果中可知，上海、北京屬于第1類，各行業(yè)的平均工資水平都高。而天津、浙江、江蘇、廣東、西藏各行業(yè)的平均水平居中，屬于第2類。其他的屬于第3類，各行業(yè)平均工資水平較低。至于為何西藏和另外4個(gè)經(jīng)濟(jì)較好的省份歸為一類，這是因?yàn)槲鞑氐奈飪r(jià)和人工成本較高，導(dǎo)致平均工資水平較高，符合事實(shí)。

5 結(jié) 論

傳統(tǒng)的k－均值聚類算法是劃分聚類算法中最基本的算法，其最大的優(yōu)點(diǎn)就是簡(jiǎn)單和高效，因此被廣泛應(yīng)用于各個(gè)領(lǐng)域［14］，但這種算法有其固有的致命缺陷，因此其使用受到一定的限制，本文也是針對(duì)其最大的2個(gè)缺陷對(duì)其進(jìn)行了改進(jìn)，同時(shí)也最大限度地降低改進(jìn)對(duì)其本身優(yōu)點(diǎn)的影響［15］。改進(jìn)后算法的特點(diǎn)如下。

1）算法在聚類時(shí)不需要知道聚類數(shù)k的值，而是引進(jìn)了參數(shù)λ，同時(shí)也給出了選擇參數(shù)λ的具體方法，本文的2個(gè)實(shí)驗(yàn)也驗(yàn)證了這種方法的可行性。參數(shù)λ確定后，將該值輸入到Matlab程序中，即可得到聚類數(shù)k和聚類結(jié)果。

2）算法初始種群的選取不是隨機(jī)的，而是以全局均值作為初始聚類中心，新增加類的初始中心也是確定的，得到的聚類結(jié)果是穩(wěn)定的。

將這種算法應(yīng)用到茶葉分類以及各地區(qū)各行業(yè)平均工資水平分析實(shí)驗(yàn)中，也表現(xiàn)出了很好的聚類效果，同時(shí)也很好地驗(yàn)證了該算法中懲罰參數(shù)選取方法的可行性。

然而，不得不提出的是這種算法和傳統(tǒng)的k－均值聚類算法一樣，都比較適宜于球形簇的聚類。

／References：

［1］ 李晶皎，趙麗紅，王愛俠.模式識(shí)別［M］.北京：電子工業(yè)出版社，2010.LI Jingjiao，ZHAO Lihong，WANG Aixia.Pattern Recognition［M］.Beijing：Electronic Industry Press，2010.

［2］ 謝娟英，蔣帥，王春霞，等.一種改進(jìn)的全局k－均值聚類算法［J］.陜西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，38（2）：18－22.XIE Juanying，JIANG Shuai，WANG Chunxia，et al.An improved globalk－means clustering algorithm ［J］.Journal of Shaanxi Normal University（Natural Science Edition），2010，38（2）：18－22.

［3］ LIKAS A，VLASSIS M，VERBEEK J.The globalK－means clustering algorithm［J］.Pattern Recognition，2003，36（2）：451－461.

［4］ CHAKRABORTY S J，NAGWANI N K.Analysis and study of incrementalK－means clustering algorithm ［A］.2011 International Conference on communications and Information Science［C］.Chandigarh：Springer－Verlag，2011：338－341.

［5］ ZHONG Wei，ALTUN G，HARRISON R，et al.ImprovedK－means clustering algorithm for exploring local protein sequence motifs representing common structural property［J］.IEEE Transactions on NanoBio Science，2005，4（3）：255－265.

［6］ WANG J T，SU X L.An improvedK－means clustering algorithm［A］.2011IEEE 3rd International Conference on Communication Software and Networks［C］.Xi’an：［s.n.］，2011：44－46.

［7］ 胡偉.改進(jìn)的層次K均值聚類算法［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49（2）：157－159.HU Wei.Improved hierarchicalK－means clustering algorithm［J］.Computer Engineer and Applications，2013，49（2）：157－159.

［8］ 張曉翊，孟德欣，余翠蘭.基于K－means算法的學(xué)生試卷成績(jī)分析［J］.寧波大學(xué)學(xué)報(bào)（理工版），2010，23（4）：67－70.ZHANG Xiaoyu，MENG Dexin，YU Cuilan.Examination grade analysis based onK－means methods［J］.Journal of Ningbo University（Natural Science and Engineering Edition），2010，23（4）：67－70.

［9］ TIAN Jinlan，ZHU Lin，ZHANG Suqin，et al.Improvement and parallelism ofk－means clustering algorithm［J］.Tsinghua Science and Technology，2005，10（3）：277－281.

［10］ 龍鈞宇.基于均值聚類和決策樹算法的學(xué)生成績(jī)分析［J］.計(jì)算機(jī)與現(xiàn)代化，2014（6）：79－83.LONG Junyu.Analysis of student’s achievement based on mean cluster and decision tree algorithm［J］.Computer and Modernization，2014（6）：79－83.

［11］ ZHANG Chunfei，F(xiàn)ANG Zhiyi.An improvedK－means clustering algorithm［J］.Journal of Information and Computational Science，2013，10（1）：193－199.

［12］ HUANG Xiuchang，SU Wei.An improvedK－means clustering algorithm［J］.Journal of Networks，2014，9（1）：161－167.

［13］ ZHANG Yuhua，WANG Kun，LU Heng，et al.An improvedk－means clustering algorithm over data accumulation in delay tolerant mobile sensor network［A］.2013 8th International Conference on Communications and Networking in China（CHINACOM）［C］.Guilin：［s.n.］，2013：34－39.

［14］ ALIAS M F，ISA N A M，SULAIMAN S A，et al.Modified movingk－means clustering algorithm ［J］.International Journal of Knowledge－based and Intelligent Engineering Systems.2012，16（2）：79－86.

［15］ 王莉，周獻(xiàn)中，沈捷.一種改進(jìn)的粗k均值聚類算法［J］.控制與決策，2012，27（11）：1711－1714.WANG Li，ZHOU Xianzhong，SHEN Jie.An improved roughk－means clustering algorithm［J］.Control and Decision，2012，27（11）：1711－1714.