付 媛，全書海

(武漢理工大學(xué) 自動化學(xué)院，湖北 武漢 430070)

改進模糊C均值聚類算法及鋰電池配組應(yīng)用

付 媛，全書海

(武漢理工大學(xué) 自動化學(xué)院，湖北 武漢 430070)

在鋰電池化成管理的智能配組過程中，當處理大規(guī)模數(shù)據(jù)或鋰電池結(jié)構(gòu)較復(fù)雜時，速度和準確度不高。因此，提出了一種基于遺傳算法與密度加權(quán)的改進模糊C均值聚類算法。首先，由遺傳算法優(yōu)化得到初始聚類中心。然后，將樣本對象的高斯密度函數(shù)作為其權(quán)值，并采用Xie-Beni有效性指標改進目標函數(shù)。將改進的算法通過標準測試數(shù)據(jù)集Iris和鋰電池配組進行實驗驗證。驗證結(jié)果表明：本文算法改善了聚類效果，與模糊C均值聚類算法相比，鋰電池配組的正確率提高了0.8%，并且計算迭代次數(shù)從14次降低到8次。

模糊C均值聚類算法；遺傳算法；高斯密度加權(quán)；Xie-Beni指標；鋰電池配組

0 引言

鋰電池的化成檢測是鋰電池生產(chǎn)和應(yīng)用中十分重要的環(huán)節(jié)，在單體鋰電池成組前采用合適的方法配組，能提高其循環(huán)壽命與容量利用率。常用的配組方法[1-3]有單參數(shù)配組法、多參數(shù)配組法和動態(tài)特性配組法。其中，動態(tài)特性配組法[3]最有效，該方法根據(jù)充放電過程中的電壓和電流等變量與時間的關(guān)系曲線來進行配組，以特性曲線聚集成簇的緊密程度來判別鋰電池間性能的近似程度，利用聚類算法進行歸類，從而提高電池組的性能。

模糊C均值聚類(fuzzy C-means，F(xiàn)CM)算法是文獻[4]提出的一種基于目標函數(shù)的非監(jiān)督模式識別算法，采用該算法對鋰電池進行配組更能客觀地反映分類結(jié)果，但也存在很大的局限性[5-7]。該算法是一種局部搜索算法，對聚類中心的初值十分敏感，初始聚類中心的選擇極大地影響聚類效果，尤其在處理大規(guī)模數(shù)據(jù)時，很容易陷入局部最優(yōu)的問題。FCM算法具有對樣本集進行等劃分趨勢的缺陷，沒有考慮實際應(yīng)用中樣本的分布密度對分類的貢獻值不同的影響。為此，文獻[8]提出了一種基于相似性閾值和最小距離原則的方法，進行粗聚類得到聚類中心，但過程中需要反復(fù)調(diào)整最小距離T和系數(shù)α，增加了計算量，而且不適合聚類數(shù)目已經(jīng)確定的計算。文獻[9]提出了使用密度函數(shù)法進行聚類中心初始化的方法，但忽略了分類數(shù)的影響。文獻[10]提出了基于屬性加權(quán)的模糊聚類算法。文獻[11]進行了密度函數(shù)加權(quán)FCM算法的聚類有效性研究。文獻[10-11]分別從不同角度對樣本權(quán)值進行了改進，但在應(yīng)用中需要根據(jù)實際樣本的特征來判斷。此外，F(xiàn)CM算法的目標函數(shù)僅體現(xiàn)了類內(nèi)部樣本對象的聚集程度，卻忽略了類之間的離散程度。

針對上述局限，本文提出一種基于遺傳算法與密度加權(quán)的改進模糊C均值聚類(genetic algorithm and density weighted improved fuzzy C-means,GDFCM)算法。利用遺傳算法全局尋優(yōu)和快速收斂等優(yōu)點初始化聚類中心。根據(jù)樣本集分布，對樣本對象采用高斯密度函數(shù)計算作為該對象的權(quán)值，結(jié)合Xie-Beni有效性指標[12]進行精確估計?；阡囯姵亟M化成得到的采樣數(shù)據(jù)進行配組實驗驗證。

1 GDFCM算法

模糊C均值聚類算法，是一種通過隸屬度來表示每個數(shù)據(jù)點屬于某個聚類程度的聚類算法[13]。本文在FCM 算法基礎(chǔ)上，設(shè)計一種GDFCM算法。利用遺傳算法對上述聚類中心的初始值進行選取和優(yōu)化，提高了算法的尋優(yōu)能力?？紤]到樣本對象的實際分布密度對聚類貢獻效果的影響，為了減小聚類誤差，采用高斯密度函數(shù)值作為每個樣本對象的權(quán)值進行加權(quán)處理，進而改進聚類中心與隸屬度函數(shù)。并且引用Xie-Beni有效性指標[12]更精確地描述聚類目標函數(shù)，提高聚類的準確性。

1.1 基于遺傳算法的改進FCM算法

遺傳算法[14-15]模擬自然界生物進化過程選擇與遺傳的機理來尋找最優(yōu)解，把問題參數(shù)編碼為染色體，再利用迭代方式進行選擇、交叉和變異等運算來交換種群中染色體的信息，最終生成符合優(yōu)化目標的染色體。

以各聚類中心組合進行編碼，采用實數(shù)編碼，根據(jù)有c個聚類中心，且每個聚類中心是一個p維的實數(shù)向量，則編碼長度為p×c，每個個體可表示為p11p12…p1pp21p22…p2p…pc1pc2…pcp。

聚類的關(guān)鍵依賴于聚類中心的確定，因此，選取聚類中心作為種群中的個體，其初始值是一個p×c維的實數(shù)向量。所有的個體構(gòu)成一個初始種群，然后作為初始點開始進化。

遺傳算法中，以個體適應(yīng)度的大小來評定個體的優(yōu)劣程度。FCM算法中，求目標函數(shù)的最小值為優(yōu)化目標，即聚類效果越好，目標函數(shù)值就越小，而此時對應(yīng)的個體適應(yīng)度應(yīng)越大。因此，個體的適應(yīng)度函數(shù)f可用目標函數(shù)J(U,V,c)的倒數(shù)來進行定義：

(1)

選擇遺傳操作(復(fù)制)的目的是把當前群體中適應(yīng)度較高的個體，按某種規(guī)則或模型遺傳到下一代群體中。本文采用保留最優(yōu)策略的錦標賽法，錦標賽規(guī)模為3個。即每次隨機選取3個個體，比較其適應(yīng)度，保留較大的作為父本，并保留每代的最優(yōu)個體直接遺傳到下一代。

交叉操作是遺傳算法中產(chǎn)生新個體的主要操作過程，采用部分匹配交叉法，對選擇出的N個父本按隨機方式兩兩配對交叉操作。首先，產(chǎn)生由1到N的無重復(fù)整數(shù)隨機排列，確定兩兩隨機配對的配對表；然后，根據(jù)隨機產(chǎn)生的從1到p×c-1的均勻分布整數(shù)，設(shè)定兩兩隨機交叉的位置；最后，交換配對個體之間部分信息，得到兩個新的個體。通過交叉操作后產(chǎn)生2N個下一代個體，合并父本中的N個個體，共得到3N個個體。再通過選擇操作選出N個最優(yōu)個體作為交叉操作的結(jié)果。

變異操作是對個體的某一個或某一些信息值按某一較小的概率進行改變，是產(chǎn)生新個體的另一種方法。本文選用單點高斯變異的方法[16]，變異率pm為0.01。在交叉后的群體中找出優(yōu)選個體，記錄其位置，并保證不在此優(yōu)選個體上發(fā)生變異，對群體中其他個體以變異率pm進行高斯變異操作。

遺傳算法是一種迭代搜索方法，經(jīng)過反復(fù)多次進化逐步優(yōu)化逼近最優(yōu)解，因此，需要設(shè)置迭代終止條件。常用的終止條件有：達到設(shè)定的最大進化世代數(shù)、最優(yōu)個體適應(yīng)度和群體適應(yīng)度保持不變。本文通過設(shè)定最大進化世代數(shù)來終止遺傳操作。

通過以上的遺傳算法，最終得到c個聚類中心的編碼，形成一種對初始條件有導(dǎo)向性的聚類迭代過程，然后將其代入到FCM算法中進行模糊聚類。

1.2 基于密度函數(shù)加權(quán)的改進FCM算法

規(guī)定樣本集X=(x1,x2,x3,…,xn)中每個樣本對象xj(j=1,2,…,n)存在一個分布密度：

(2)

(3)

將加權(quán)系數(shù)wj帶入到FCM算法中，得到改進的新目標函數(shù)：

(4)

構(gòu)造拉格朗日乘數(shù)法求解極值，得uij和vi分別為：

(5)

(6)

由此得知，引入加權(quán)系數(shù)后，可以更全面、更準確地選取聚類中心vi。

1.3 目標函數(shù)的改進

判定一個模糊C劃分是否為最佳分類，必須要滿足劃分后類中的樣本盡可能聚攏，類與類之間盡可能分散。然而，F(xiàn)CM算法中目標函數(shù)僅計算了類中距，并沒有重視類間距的影響，因此，引用文獻[12]提出的一種兼顧類內(nèi)一致性和類間差異性的Xie-Beni聚類有效性指標來作為迭代條件：

(7)

對目標函數(shù)進行改進，式(1)改進為：

(8)

1.4 GDFCM算法的實現(xiàn)

改進后的算法步驟如下：

(Ⅰ)確定算法參數(shù)：聚類個數(shù)、樣本集、種群規(guī)模、最大進化世代數(shù)、變異概率和迭代停止閾值等。

(Ⅱ)根據(jù)式(2)和式(3)計算樣本集每個對象的密度加權(quán)系數(shù)。

(Ⅲ)初始化種群，對個體數(shù)據(jù)進行正規(guī)化處理及編碼。

(Ⅳ)根據(jù)式(5)，計算初始種群中聚類中心樣本的隸屬度，然后代入式(7)和式(8)，計算出每個個體的適應(yīng)度，從中選出最優(yōu)個體。

(Ⅴ)對種群進行遺傳操作，包括選擇、交叉和變異，產(chǎn)生優(yōu)選的下一代。

(Ⅵ)根據(jù)式(5)、式(7)和式(8)，計算新一代種群中各樣本的隸屬度、目標函數(shù)以及新個體的適應(yīng)度，判斷是否滿足達到最大進化世代數(shù)的終止條件，如果滿足則算法結(jié)束，否則轉(zhuǎn)到步驟(Ⅴ)繼續(xù)。

(Ⅶ)將遺傳算法得到的初始聚類中心代入到FCM算法中，執(zhí)行標準的FCM算法過程，根據(jù)式(5)～式(7)，迭代更新隸屬度矩陣、聚類中心和目標函數(shù)，對樣本集模糊聚類。當新的目標函數(shù)值相對于上次目標函數(shù)值的改變量小于設(shè)定的閾值時，則算法停止，得到聚類結(jié)果。

2 仿真實驗驗證

2.1 標準測試數(shù)據(jù)集實驗

為檢驗改進的GDFCM算法是否能提高聚類性能，采用標準測試數(shù)據(jù)集Iris作為測試樣本集[18]。Iris數(shù)據(jù)由四維空間中的150個樣本組成，分別隸屬于Setosa類、Versicolor類和Virginica類3 個不同類別，每類各50個樣本。文獻[19]給出了Iris測試數(shù)據(jù)的實際類中心位置，分別為：p1=(5.00,3.42,1.46,0.24)，p2=(5.93,2.77,4.26,1.32)，p3=(6.58,2.97,5.55,2.02)。將改進的GDFCM算法與FCM算法進行對比，對Iris數(shù)據(jù)樣本進行分類，測試兩種算法的誤分樣本數(shù)。設(shè)置種群規(guī)模為300，最大進化世代數(shù)為50，迭代停止閾值為1×e-4，權(quán)重指數(shù)m=2[20]，Iris數(shù)據(jù)聚類結(jié)果如表1所示。Iris數(shù)據(jù)的聚類目標函數(shù)變化曲線如圖1所示。

表1 Iris數(shù)據(jù)聚類結(jié)果

圖1 Iris數(shù)據(jù)的聚類目標函數(shù)變化曲線

由表1和圖1可以看出：相較于FCM算法，經(jīng)過遺傳算法改進之后，GDFCM算法在初始聚類中心的選擇上誤差減少了許多，并且在相同迭代終止誤差的條件下，總迭代次數(shù)(平均值)從16次降到9次。在聚類效果上，改進后的GDFCM算法不僅減少了誤分樣本數(shù)，提高了聚類正確率，而且得到的聚類中心也更加精確地接近實際的類中心位置。對各樣本采用高斯密度函數(shù)加權(quán)處理，取密度參數(shù)σ=1.6，Setosa類、Versicolor類和Virginica類(每類各50組數(shù)據(jù))權(quán)重的密度均值分別為0.005 5、0.007 7和0.006 8，并且在各類中密度值近似，在Versicolor類與Virginica類中個別偏差較大。權(quán)重相近的數(shù)據(jù)更易聚為一類，可見采用高斯密度函數(shù)構(gòu)成的加權(quán)合理。

2.2 鋰電池化成數(shù)據(jù)實驗

本實驗選用額定容量為40 Ah 的磷酸鐵鋰電池為研究對象，先經(jīng)過初始容量和電池內(nèi)阻參數(shù)分選出一致性較高的10節(jié)鋰電池，使得容量差異率≤3%，內(nèi)阻差異率≤5%[21]。將鋰電池串聯(lián)成電池組，在室溫環(huán)境下，采用相同倍率的電流對其進行循環(huán)充放電50次，每間隔3 s實時采集化成數(shù)據(jù)并保存。將鋰電池的放電電壓按放電容量均分得到的90個采樣點進行曲線擬合，然后選取各單體鋰電池的電壓曲線作為待聚類樣本，共構(gòu)成500組數(shù)據(jù)。鋰電池循環(huán)放電數(shù)據(jù)如表2所示。表2中：ID0001～ID0010分別為10節(jié)單體鋰電池的編號；U(a,b)為電池組在循環(huán)放電過程中按容量平分測量得到的電壓值，a為循環(huán)次數(shù)，b為測量的采樣點。

分別采用改進的GDFCM算法和FCM算法進行聚類對比，將數(shù)據(jù)分成10組，測試兩種算法的精確度。設(shè)置遺傳算法的種群規(guī)模為300，最大進化世代數(shù)為50，迭代停止閾值為1×e-4，權(quán)重指數(shù)m=2。鋰電池聚類結(jié)果如表3所示。

表2 鋰電池循環(huán)放電數(shù)據(jù) V

表3 鋰電池聚類結(jié)果

從表3的聚類結(jié)果可以看出：對于鋰電池化成過程中出現(xiàn)的個別噪聲干擾數(shù)據(jù)，改進后的GDFCM算法在排除局部誤差樣本的性能方面更為優(yōu)越，分類的正確率得到了提高，相比于FCM算法，正確率上升了0.8%，迭代次數(shù)從14次降低到8次，減少了6次，具有更好的聚類效果。

3 結(jié)束語

本文基于遺傳算法與高斯密度加權(quán)，對FCM算法進行了改進，解決了初始聚類中心局部最優(yōu)問題以及對樣本對象的權(quán)值等劃分缺點，并且引用Xie-Beni有效性指標改進了聚類效果。GDFCM算法不僅優(yōu)化了聚類中心，減少了計算量，而且在數(shù)據(jù)結(jié)構(gòu)較復(fù)雜的情況下，能達到更好的聚類效果。在針對大規(guī)模的鋰電池配組應(yīng)用中，GDFCM算法能夠較快地收斂于全局最優(yōu)點，提高配組的精確度，相比于FCM算法具有更加廣泛的實用性。

[1] 吳偉靜.電動汽車鋰動力電池分選及成組技術(shù)研究[D].長春:吉林大學(xué),2015.

[2] 酈柏金.電池配組算法研究與系統(tǒng)實現(xiàn)[D].杭州:杭州電子科技大學(xué),2014.

[3] WU Y M,ZHAO M Y,LU Z Y.Study on the reuse of electric vehicle batteries in energy storage system[J].Advanced materials research,2013,608:1613-1617.

[4] BEZEDK J C,CHRISTIAN J.Fuzzy mathematics in pattern classification[D].Ithaca:Cornell University,1973.

[5] 姚紫陽.半監(jiān)督中心最大化模糊C均值算法[J].計算機工程與應(yīng)用,2012,48(33):188-193.

[6] JIANG H,LIU Y,YE F.Study of clustering algorithm based on fuzzy C-means and immunological partheno genetic[J].Journal of software,2013,8(1):134-141.

[7] KANNAN S R,RAMATHILAGAM S,CHUNG P C.Effective fuzzy C-means clustering algorithms for data clustering problems[J].Expert systems with applications,2012,39(7): 6292-6300.

[8] 張新波.兩階段模糊C-均值聚類算法[J].電路與系統(tǒng)學(xué)報,2005,10(2):117-120.

[9] 韓凌波,王強,蔣正鋒,等.一種改進的K-means初始聚類中心選取算法[J].計算機工程與應(yīng)用,2010,46(17):150-152.

[10] LI R,LU C.Attribute weighted optimization of fuzzy C-means clustering algorithm[J].Metallurgical and mining industry,2015,7(6):454-459.

[11] LU C,XIAO S,GU X.Improving fuzzy C-means clustering algorithm based on a density-induced distance measure[J/OL].The journal of engineering,2014.DOI:10.1049/joe.2014.0053.

[12] XIE X L,BENI G.A validity measure for fuzzy clustering[J]. IEEE transactions on pattern analysis and machine intelligence,1991,13(8):841-847.

[13] BEZEDK J C,EHRLICH R,FULL W.FCM:the fuzzy C-means clustering algorithm[J]. Computers & geosciences,1984,10(2/3):191-203.

[14] HOLLAND J H. Adaptation in nature and artificial systems[M].Michigan: the University of Michigan Press,1975.

[15] 吳迪,劉循.基于遺傳算法思想的加權(quán)模糊C均值聚類分析[J].現(xiàn)代計算機(專業(yè)版),2014(23):3-6,11.

[16] 張永庫,尹靈雪,孫勁光.基于改進的遺傳算法的模糊聚類算法[J].智能系統(tǒng)學(xué)報,2015,10(4):627-635.

[17] 王祥斌,楊柳,鄧倫治.一種利用高斯函數(shù)的聚類算法[J].河南科技大學(xué)學(xué)報(自然科學(xué)版),2014,35(5):33-36.

[18] KIRA K,RENDELL L A.A practical approach to feature selection[C]//Proceedings of the 9th International Workshop on Machine Leaning.San Francisco,CA:Morgan Kaufmann,1992:249-256.

[19] HATHAWAY R J,BEZDEK J C.Nerf C-means:non-euclidean relational fuzzy clustering[J]. Pattern recognition,1994,27(3):429-437.

[20] 肖滿生,陽娣蘭,張居武,等.基于模糊相關(guān)度的模糊C均值聚類加權(quán)指數(shù)研究[J].計算機應(yīng)用,2010,30(12):3388-3390.

[21] 李國欣.新型化學(xué)電源技術(shù)概論[M].上海:上?？茖W(xué)技術(shù)出版社,2007.

國家“973”計劃基金項目(2013CB632505);國家自然科學(xué)基金項目(51477125);湖北省科技支撐計劃基金項目(2014BEC074)

付媛(1992-),女,湖北荊州人,碩士生;全書海(1955-),男,湖北武漢人,教授,博士,博士生導(dǎo)師，主要研究方向為智能信息處理與智能控制、汽車電子與電動汽車控制、現(xiàn)場總線與網(wǎng)絡(luò)通信技術(shù)、模式識別與圖像處理.

2016-11-24

1672-6871(2017)04-0043-06

10.15926/j.cnki.issn1672-6871.2017.04.010

TP312

A