一種引入參數無需確定聚類數的聚類算法

周其林，雷菊陽，王昱棟，張蘭蘭

（上海工程技術大學機械工程學院，上海 201620）

聚類分析是一種將沒有類別標記的對象集按照某種規則分為若干個類，同一類中各對象的屬性盡可能相似，不同類中各對象的屬性會有較大差異。聚類分析是一種無監督學習方法，能夠通過特征數據挖掘出對象的相似性，它在模式識別、特征提取、數據挖掘等領域都有廣泛應用［1－3］。

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

1 傳統k－均值聚類算法及其缺陷

1.1 k－均值聚類算法

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

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

k－ 均值聚類算法的實現：

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

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

步驟：

Step1 從樣品x中隨機選取k個數據作為初始聚類中心μ1，μ2，…，μk。

Step2 對于每個點xi，計算其到各中心的距離。

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

Step3 計算各類中所有樣品特征值的平均值作為新的聚類中心，對于每個簇

Step4 重復Step2和Step3直到聚類中心不再發生改變，算法結束。

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

k－均值聚類算法最大的缺陷就是要知道確定的聚類數k，但在實際中聚類數k往往是不易得到的，這就使得算法在解決很多聚類問題上有很大的局限性［11－12］。此外，這種算法的初始種群是隨機選取的，而初始種群的選取對聚類結果又會產生很大的影響，使得聚類結果不穩定，甚至導致聚類結果失真。這種算法還有一個缺陷，就是易陷入局部最優，使得聚類結果偏離全局最優。

2 新聚類算法

2.1 算法綜述

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

這種算法最大的特色是事先不需要知道聚類數k，而只需確定懲罰參數λ的值即可（λ值的確定方法將會在后文中介紹），這就解決了傳統k－ 均值聚類算法的最大缺陷，拓展了其應用范圍。其次，這種算法的初始聚類中心為所有樣品特征值的平均值，而且對于新增的類，其聚類中心的選取也是根據一定的算法得到確定的點，使聚類結果具有很大的穩定性，這就避免了傳統k－均值聚類算法初始中心隨機選擇而導致聚類結果不穩定，甚至會出現失真的情形。此外，這種算法具有全局性，可以很好地避免聚類陷入局部最優。

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

算法的實現：

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

輸出 每個類中所含樣品λ1，λ2，…，λn，以及簇的個數k。

步驟：

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

Step2 計算每個樣品點到各中心的距離dic＝‖xi－μc‖，μc為第c個聚類中心，其中c＝1，2，…，k。

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

Step4 重復Step2和Step3，直到收斂。

2.2 懲罰參數λ 的確定

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

新的算法和傳統的k－均值聚類算法一樣，都對球形簇有較好的聚類效果，所以下面就以2個球形簇的聚類問題來進一步說明這樣選取λ的合理性。假設這2個球形簇中較大的一個球形簇的半徑為r，當λ小于r時，隨著λ的增大k的變化是明顯的，而當λ大于r時，此時k等于2，而且在很大范圍內，k的值是不變化的，直到λ足夠大時，k變為1，在這個很大范圍內即可選取對應的一個λ值作為合適的懲罰參數。

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

3 實驗一：茶葉分類實驗與分析

3.1 實驗數據

實驗針對不同地區的紅茶和綠茶，包含6個分類特征，分別是：纖維素、半纖維素、木質素、多酸、咖啡因、氨基酸，對23個樣品進行聚類。數據如表1所示。

表1 兩種茶葉的化學分析數據Tab.1 Data of the two kinds of tea’s chemical analysis

3.2 數據預處理

一個樣品中不同的特征值往往采用不同的度量單位，其值可能相差較大，因此有必要對數據進行預處理以提高數據質量［13］，首先對這23 個樣品的各特征的化學分析數據進行預處理，對數據進行最小－最大規范化：

3.3 參數的確定

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

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

3.4 實驗結果

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

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

3.5 聚類結果分析

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

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

4 實驗二：各地區各行業工資水平分析

實驗對中國31個不同省、市（不含港、澳、臺）的平均工資水平進行了分析，包括15個主要行業的平均工資水平，這15個行業分別是企業、非農企業、事業、農林牧漁業、采礦業、制造業、電力燃氣和水的供應業、建筑業、交通運輸業、信息傳輸業、批發和零售業、住宿和餐飲業、金融業、房地產業以及租賃和商務服務業。數據來源于《中國勞動統計年鑒—2010》，具體數據略。

4.1 參數λ 的確定

從圖2中可以看出，λ可取0.347 5，此時對應的聚類數k為3。

4.2 實驗結果

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

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

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

表5 聚類結果Tab.5 Final result of clustering

4.3 聚類結果分析

實驗的正確率達到100%，實驗結果與事實相符，從表5的聚類結果中可知，上海、北京屬于第1類，各行業的平均工資水平都高。而天津、浙江、江蘇、廣東、西藏各行業的平均水平居中，屬于第2類。其他的屬于第3類，各行業平均工資水平較低。至于為何西藏和另外4個經濟較好的省份歸為一類，這是因為西藏的物價和人工成本較高，導致平均工資水平較高，符合事實。

5 結 論

傳統的k－均值聚類算法是劃分聚類算法中最基本的算法，其最大的優點就是簡單和高效，因此被廣泛應用于各個領域［14］，但這種算法有其固有的致命缺陷，因此其使用受到一定的限制，本文也是針對其最大的2個缺陷對其進行了改進，同時也最大限度地降低改進對其本身優點的影響［15］。改進后算法的特點如下。

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

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

將這種算法應用到茶葉分類以及各地區各行業平均工資水平分析實驗中，也表現出了很好的聚類效果，同時也很好地驗證了該算法中懲罰參數選取方法的可行性。

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

／References：

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

［2］ 謝娟英，蔣帥，王春霞，等.一種改進的全局k－均值聚類算法［J］.陜西師范大學學報（自然科學版），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］ 胡偉.改進的層次K均值聚類算法［J］.計算機工程與應用，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算法的學生試卷成績分析［J］.寧波大學學報（理工版），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］ 龍鈞宇.基于均值聚類和決策樹算法的學生成績分析［J］.計算機與現代化，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，FANG 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］ 王莉，周獻中，沈捷.一種改進的粗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.