基于改進(jìn)CART算法的退役動力電池等級篩選方法

劉永成 劉杰文 楊茜 宋汶秦 郭永吉 王興貴

摘要：針對退役動力電池存在一致性差、等級篩選效率低的難題，提出了一種基于改進(jìn)CART算法的退役動力電池等級篩選方法。首先，分析了傳統(tǒng)CART算法的基本原理，為克服算法計算量大的缺陷，將Fayyad邊界點判定定理與CART算法相結(jié)合，通過選取屬性最優(yōu)閾值點來減少計算量，提高分類效率；其次，基于代價復(fù)雜度后剪枝算法，采用交叉驗證法對算法進(jìn)行進(jìn)一步優(yōu)化；最后，將改進(jìn)CART算法用于退役動力電池篩選分類，實驗結(jié)果表明改進(jìn)CART算法在保持較高準(zhǔn)確率的情況下，可以有效提高退役動力電池的等級篩選效率。

關(guān)鍵詞：退役動力電池；等級篩選；改進(jìn)CART算法；最優(yōu)閾值點

中圖分類號： TP399文獻(xiàn)標(biāo)識碼： ADOI：10.3969/j.issn.1007-791X.2024.01.0060

引言

近年來，以化石能源為燃料的汽車產(chǎn)業(yè)對環(huán)境的污染已經(jīng)達(dá)到了環(huán)境所能承受的臨界點，如何替代化石燃料將成為一個刻不容緩的問題[1]。在此背景下，國家開始大力推動電動汽車的發(fā)展。電動汽車的大量使用，既可以減少對環(huán)境的污染，也可以降低化石能源的消耗。但電動汽車使用幾年之后，電池性能會逐漸降低，當(dāng)它無法滿足電動汽車使用要求時，就會退役下來。預(yù)計從2020 年到2025 年，退役動力電池的數(shù)量將會從36萬噸激增至百萬噸[2]。

由于退役動力電池仍有70%～80%的剩余容量，如果直接將其報廢，不僅會浪費(fèi)資源，甚至還會產(chǎn)生嚴(yán)重的環(huán)境污染問題[3-5]。為提高動力電池利用率，減少環(huán)境污染，將退役動力電池應(yīng)用在電網(wǎng)儲能電站、光伏電站和家庭用電等場合，延長使用壽命，使其剩余價值得到充分發(fā)揮[6]。

另外，動力電池退役后，不僅容量會發(fā)生衰減，而且在外觀、自放電率和內(nèi)阻等方面會表現(xiàn)出較大的不一致性。在梯次利用前，若不經(jīng)過篩選分類直接利用，可能會導(dǎo)致動力電池的過充或過放，甚至爆炸等危險[7]。因此，對退役動力電池進(jìn)行篩選分類具有重要意義。

現(xiàn)有篩選方法主要有單參數(shù)篩選、多參數(shù)篩選和特征曲線篩選法等。為提高退役動力電池一致性，有效降低篩選成本，文獻(xiàn)[8]提出了一種容量和自放電率相結(jié)合的分組方法；文獻(xiàn)[9]采用總因子法對動力電池進(jìn)行分選，并在分選結(jié)果基礎(chǔ)上用模糊C均值聚類算法進(jìn)行動態(tài)特性分選；文獻(xiàn)[10]通過充放電曲線識別，將性能近似程度高的單體電池聚集在一起，提高了電池的一致性。以上篩選方法雖然可以實現(xiàn)退役動力電池的篩選分類，但存在篩選效率低、成本較高等問題。

決策樹算法是數(shù)據(jù)挖掘領(lǐng)域最為普遍的分類算法之一，相比其他分類算法，具有執(zhí)行速度快、計算量小和準(zhǔn)確率高等優(yōu)點，常用算法有ID3、C4.5和分類與回歸樹（Classification and Regression Tree，CART）等算法[11-12]。但這些方法都有一定的缺點：ID3算法無法直接處理具有缺失值的連續(xù)屬性；C4.5算法在數(shù)據(jù)集較大時分類效果不佳；CART算法在ID3和C4.5的基礎(chǔ)上有了進(jìn)一步的提升，但算法計算量大，分類效率不高。

本文將CART算法與Fayyad邊界點判定定理相結(jié)合，克服了傳統(tǒng)CART算法計算量大的問題。然后，將改進(jìn)CART算法用于退役動力電池等級篩選。由于電池容量、內(nèi)阻和二次循環(huán)壽命對電池成組影響較大，因此選取這三個主要參數(shù)為指標(biāo)進(jìn)行篩選分類，為之后退役動力電池的梯次利用奠定一定的基礎(chǔ)。

1CART算法及其改進(jìn)

1.1CART算法基本原理

CART算法選擇具有最小Gini系數(shù)的屬性作為節(jié)點分裂屬性。根據(jù)節(jié)點分裂屬性，采用二元遞歸法，將決策樹每個內(nèi)部節(jié)點分為兩個子節(jié)點，依次遞歸，生成一顆結(jié)構(gòu)簡單的二叉樹[13]。構(gòu)建CART決策樹的步驟如下：

步驟1：計算數(shù)據(jù)集S中各個特征屬性的Gini系數(shù)，并將具有最小Gini系數(shù)的屬性作為決策樹的根節(jié)點，其計算公式為[14]

式中，pk為S中屬于類別Ck （k =1， 2， …， n）的概率，n為總類別數(shù)。

步驟2：根據(jù)S中屬性A的某個特征值a，把S分為兩個樣本子集S1和S2。此時，Gini系數(shù)的計算公式變?yōu)?/p>

步驟3：將S1和S2繼續(xù)采用與步驟2相同的方法遞歸建立決策樹的子節(jié)點，按照這種方式依次進(jìn)行，直到所有子節(jié)點中的樣本屬于同一類為止，就得到了CART決策樹。

1.2改進(jìn)CART算法

傳統(tǒng)CART算法在連續(xù)屬性離散化過程中，如果樣本集很大，且具有的連續(xù)屬性很多時，節(jié)點數(shù)將會增加，計算量也會隨之增大，這會導(dǎo)致算法分類效率不高。

針對CART算法的缺陷，在選取屬性分裂點時，結(jié)合Fayyad邊界點判定定理選取最優(yōu)分裂點，以減少算法計算量。即若T使得E（A，T；S）最小，則T是一個邊界點[15]。其中， T為屬性A的分裂點；E為屬性A上劃分S 的平均類熵。

由以上定理可知，屬性最優(yōu)分裂點位于A的邊界點T處。要得到屬性最優(yōu)分裂點，就要使得平均類熵E達(dá)到最小。熵的定義為

對于某一屬性A的一個分裂點，則樣本集S的平均類熵E的計算公式為

式中，S1為S在A上小于等于T的樣本子集，S1為S在A上大于T的樣本子集。圖1給出了熵和Gini系數(shù)的關(guān)系。

由圖1可知，在同一二元分裂條件下，熵和Gini系數(shù)的變化趨勢基本相同，熵越小，Gini系數(shù)也越小。因此，結(jié)合Fayyad邊界點判定定理，在選擇內(nèi)部分裂屬性時，則不需要計算所有分割閾值點處的Gini系數(shù)，只需要計算邊界點處的Gini系數(shù)即可。

2退役動力電池等級篩選流程

為減少算法計算量，提高分類效率。在生成CART決策樹時，結(jié)合Fayyad邊界點判定定理來選擇屬性最優(yōu)閾值點。生成基于改進(jìn)CART算法的退役動力電池等級篩選決策樹的流程如下：

步驟1：對退役動力電池樣本數(shù)據(jù)集進(jìn)行劃分，將60 %的樣本用于模型訓(xùn)練，40 %的樣本用于模型性能評估。

步驟2：選取容量A1、內(nèi)阻A2和二次循環(huán)壽命A3作為退役動力電池的分類依據(jù)。以此為基礎(chǔ)，在選擇退役動力電池屬性分割點時，對于連續(xù)屬性A1、A2、A3，為找到使得退役動力電池樣本集平均類熵E達(dá)到最小值的閾值點，分別將所有樣本按照屬性A1、A2、A3的具體數(shù)值升序排列后，兩個相鄰異類樣本之間的分界點即為屬性A1、A2、A3的最優(yōu)閾值點。

步驟3：計算退役動力電池屬性最優(yōu)閾值點處的Gini系數(shù)。將具有最小Gini系數(shù)的屬性閾值點作為決策樹的根節(jié)點，把初始退役動力電池樣本集S分為兩個子集S1和S2，并對S1和S2繼續(xù)遞歸，建立退役動力電池決策樹的子節(jié)點，直到所有子節(jié)點中的退役動力電池屬于同一類為止，生成退役動力電池等級篩選決策樹。

步驟4：當(dāng)退役動力電池樣本集很大，特征量很多時，決策樹容易過擬合。為抑制過擬合，需要找到最大決策樹深度，圖2為不同決策樹深度下退役動力電池的分類準(zhǔn)確率。

由圖2可知，當(dāng)決策樹深度到5左右時，準(zhǔn)確率達(dá)到97.5 %，隨著決策樹深度增大，準(zhǔn)確率不再發(fā)生明顯變化。因此，設(shè)定最大決策深度為5。

步驟5：為提高決策樹泛化性能，基于代價復(fù)雜度后剪枝算法，采用交叉驗證法來減少決策樹的誤分類誤差[16]。具體實現(xiàn)步驟如下：

首先要構(gòu)建決策樹剪枝后各個子樹序列T，T是用來評估CART決策樹復(fù)雜度的一棵子樹，其代價復(fù)雜度函數(shù)為

其中，Aα（T）為在剪枝閾值變量α下，T的代價復(fù)雜度；A（T）為誤分類損失值；NT為決策樹葉子結(jié)點數(shù)。以決策樹葉子結(jié)點t作為代價復(fù)雜度函數(shù)A的自變量，則NT變?yōu)?，可以得到下式：

將α從0一直增加，會出現(xiàn)滿足Aα（t）= Aα（T）條件的節(jié)點，得到子樹T2。重復(fù)上述步驟，不斷增加α值就可以得到所有子樹序列Ti （i =1， 2， …， n）。此時，剪枝閾值αi變?yōu)?/p>

其中，A（t）為決策樹剪枝后Ti節(jié)點的誤分類損失值，A（Ti）為未剪枝時Ti節(jié)點的誤分類損失值。

得到了αi之后，采用交叉驗證法評估子樹的分類誤差，得到代價復(fù)雜度最小的子樹Tk（α），確定最優(yōu)剪枝成本復(fù)雜性參數(shù)p，從而得到誤分類誤差最小的決策樹。成本復(fù)雜性參數(shù)p與葉節(jié)點總不純度的關(guān)系如圖3所示。

由上述理論的實驗驗證可得，當(dāng)p為0.017時，葉節(jié)點總不純度最低且不為0，此時決策樹的泛化性能最好。

步驟6：輸入以上最優(yōu)參數(shù)，分析對比改進(jìn)前后CART決策樹算法的準(zhǔn)確率和運(yùn)行效率。改進(jìn)CART算法流程如圖4所示。

3實驗驗證及分析

實驗數(shù)據(jù)來自電動大巴車運(yùn)行三年后的退役動力電池組[17]。抽取其中1 000組數(shù)據(jù)作為樣本集。考慮到電池特征性能的重要性，選取容量、內(nèi)阻和二次循環(huán)壽命作為篩選的特征依據(jù)，退役動力電池樣本集數(shù)據(jù)分布如圖5所示。

由圖5可知，與新出廠動力電池相比，退役動力電池內(nèi)阻顯著增大，容量顯著減少，它們的分布離散性較大，一致性很差。

將改進(jìn)CART決策樹算法用于退役動力電池等級篩選后得到了屬性最優(yōu)閾值點。以屬性容量為例，將所有退役動力電池按容量升序排列，若前h個退役動力電池屬于類別C1，中間m-h個屬于類別C2，最后n-m個屬于類別C3，只需考察第h和第m個邊界點處的Gini系數(shù)，然后選擇兩個邊界點中使得樣本平均類熵E達(dá)到最小的點作為最優(yōu)閾值點。按照上述方法可以得到最優(yōu)容量閾值點為186.612 Ah，最優(yōu)內(nèi)阻閾值點為1.213 Ω，最優(yōu)二次循環(huán)壽命為538.191次。結(jié)合屬性最優(yōu)閾值點，生成退役動力電池等級篩選決策樹，如圖6所示。

由圖6可知，退役動力電池等級篩選決策樹除了根節(jié)點，有5層子樹，它將整個退役動力電池樣本集分成了4類，分類結(jié)果如表1所示。

為驗證改進(jìn)CART算法的準(zhǔn)確率和分類效率，在退役動力電池數(shù)據(jù)集S相同的情況下，分別將改進(jìn)前后兩種CART算法用于退役動力電池等級篩選，并對算法的準(zhǔn)確率和分類效率進(jìn)行了對比分析，分別如圖7和圖8所示。

分析實驗結(jié)果可知，在不同數(shù)據(jù)集S下，改進(jìn)CART算法相比于傳統(tǒng)CART算法，在保持較高準(zhǔn)確率的前提下，顯著提高了退役動力電池等級篩選的效率。

根據(jù)以上分類結(jié)果，將退役動力電池容量劃分為3個子區(qū)間：高容量（187 Ah ～250 Ah）、中等容量（125 Ah～187 Ah）和低容量（0～125 Ah）。其中動力電池出廠容量為250 Ah左右，內(nèi)阻為0.4 Ω左右，則125 Ah和187 Ah分別為額定容量衰減程度為50%和80 %下的退役動力電池剩余容量。此外，根據(jù)內(nèi)阻相對于額定內(nèi)阻的增量進(jìn)行分類[18]。額定內(nèi)阻為0.4 Ω，則小于0.72 Ω為低電阻，反之則為高電阻。

由此，將篩選后的4類退役動力電池分別應(yīng)用于性能指標(biāo)要求低于車用動力電池的場景。A類和B類退役動力電池容量均高于額定容量的80%，且內(nèi)阻相對較低，故將其用于新能源發(fā)電或電網(wǎng)儲能等場合；C類退役動力電池屬于中等容量和高內(nèi)阻區(qū)間的電池，將其用于路燈和家庭用電等場合；D類退役動力電池容量低于額定容量的50%，該類電池?zé)o法再投入使用，只能將其拆解資源化重組，循環(huán)利用。將不同類別的退役動力電池應(yīng)用于不同場所，可以充分利用退役動力電池的剩余容量，來提高其經(jīng)濟(jì)價值。

4結(jié)論

為實現(xiàn)退役動力電池的篩選分類，提高其篩選效率，本文將Fayyad邊界點判定定理與傳統(tǒng)CART算法相結(jié)合，通過選取屬性最優(yōu)閾值點來減少算法計算量，提出了一種最優(yōu)閾值選擇的改進(jìn)方法，并基于此方法建立了退役動力電池等級篩選CART決策樹模型。此外，針對CART決策樹容易出現(xiàn)過擬合的現(xiàn)象，利用代價復(fù)雜度剪枝算法進(jìn)行后剪枝，獲得最優(yōu)子樹，有效降低決策樹的復(fù)雜程度。通過實驗驗證得出以下結(jié)論：改進(jìn)CART算法克服了傳統(tǒng)CART算法計算量大的缺陷，在保持較高分類準(zhǔn)確率的情況下，提高了退役動力電池的等級篩選效率；同時，也為退役動力電池的梯次利用打下了一定的基礎(chǔ)。

參考文獻(xiàn)

[1] YANG D X， QIU L S， YAN J J， et al. The government regulation and market behavior of the new energy automotive industry[J]. Journal of Cleaner Production， 2019， 210： 1281-1288.

[2] 李建林， 李雅欣， 呂超， 等. 碳中和目標(biāo)下退役電池篩選聚類關(guān)鍵技術(shù)研究[J]. 電網(wǎng)技術(shù)， 2022， 46（2）： 429-431.

LI J L， LI Y X， L? C， et al. Research on key technologies of screening and clustering retired batteries under the target of carbon neutrality[J]. Power System Technology， 2022， 46（2）： 429-431.

[3] 吳星宇， 阮丁山， 唐盛賀， 等. 退役動力鋰離子電池梯次利用概述[J]. 電池， 2020， 50（6）： 594-596.

WU X Y， RUAN D S， TANG S H， et al. Overview on echelon utilization of retired power Li-ion battery[J]. Battery Bimonthly， 2020， 50（6）： 594-596.

[4] ZHANG H M， HUANG J V， HU R H， et al. Echelon utilization of waste power batteries in new energy vehicles： review of Chinese policies[J]. Energy， 2020， 206：118178.

[5] 馬玲， 魏成偉， 謝麗蓉， 等. 基于退役動力電池的風(fēng)儲有功功率協(xié)調(diào)控制策略[J]. 太陽能學(xué)報， 2021， 42（10）： 437-440.

MA L， WEI C W， XIE L R， et al. Coordinated control strategy of wind storage active power based on retired power batteries[J]. Acta Energiae Solaris Sinica， 2021， 42（10）： 437-440.

[6] 李建林， 李雅欣， 呂超， 等. 退役動力電池梯次利用關(guān)鍵技術(shù)及現(xiàn)狀分析[J]. 電力系統(tǒng)自動化， 2020， 44（13）： 172-175.

LI J L， LI Y X， L? C， et al. Key technology and research status of cascaded utilization in decommissioned power battery[J]. Automation of Electric Power Systems， 2020， 44 （13）： 172-175.

[7] 張雷， 劉穎琦， 張力， 等. 中國儲能產(chǎn)業(yè)中動力電池梯次利用的商業(yè)價值[J]. 北京理工大學(xué)學(xué)報（社會科學(xué)版）， 2018， 20（6）： 34-38.

ZHANG L， LIU Y Q， ZHANG L， et al. Commercial value of power battery echelon utilization in China′s energy storage industry[J]. Journal of Beijing Institute of Technology （Social Sciences Edition）， 2018， 20 （6）： 34-38.

[8] 安富強(qiáng). 電動車用鋰離子電池的一致性研究[D]. 北京：北京科技大學(xué)， 2017：31-57.

AN F Q. Research on the consistency of lithium-ion batteries for electric vehicles[D]. Beijing： University of Science and Technology Beijing， 2017：31-57.

[9] 陳燕虹， 吳偉靜， 劉宏偉， 等. 電動汽車鋰離子動力電池分選方法研究[J]. 湖南大學(xué)學(xué)報（自然科學(xué)版）， 2016， 43（10）： 23-21.

CHEN Y H， WU W J， LIU H W， et al. Study on sorting technology for lithium-ion power battery of electric vehicle[J]. Journal of Hunan University （Natural Sciences）， 2016， 43 （10）： 23-21.

[10] 李加升， 吳兔利， 劉玉芳， 等. 基于充放電曲線的鋰電池智能分選系統(tǒng)研究[J]. 電源技術(shù)， 2011， 35（8）： 912-914..

LI J S， WU T L， LIU Y F， et al. Research of Li-ion battery intelligent classifying system based on charge and discharge curve[J]. Chinese Journal of Power Sources， 2011， 35（8）： 912-914.

[11] 王雅輝， 錢宇華， 劉郭慶. 基于模糊優(yōu)勢互補(bǔ)互信息的有序決策樹算法[J]. 計算機(jī)應(yīng)用， 2021， 41（10）： 2785-2787.

WANG Y H， QIAN Y H， LIU G Q. Ordinal decision tree algorithm based on fuzzy advantage complementary mutual information[J]. Journal of Computer Applications， 2021， 41（10）： 2785-2787.

[12] 張敏， 彭紅偉， 顏曉玲. 基于神經(jīng)網(wǎng)絡(luò)的模糊決策樹改進(jìn)算法[J]. 計算機(jī)工程與應(yīng)用， 2021，57（21）： 174-176.

ZHANG M， PENG H W， YAN X L. Improved algorithm of fuzzy decision tree based on neural network[J]. Computer Engineering and Applications， 2021，57（21）： 174-176.

[13] SANG X， GUO Q Z， WU X X， et al. Intensity and stationarity analysis of land use change based on CART algorithm[J]. Scientific Reports， 2019， 9（1）： 1209-1213.

[14] 姚岳松， 張賢勇， 陳帥， 等. 基于屬性純度的決策樹歸納算法[J]. 計算機(jī)工程與設(shè)計， 2021， 42（1）： 142-149.

YAO Y S， ZHANG X Y， CHEN S， et al. Decision tree induction algorithm based on attribute purity degree[J]. Computer Engineering and Design， 2021， 42（1）： 142-149.

[15] 姚亞夫， 邢留濤. 決策樹C4.5連續(xù)屬性分割閾值算法改進(jìn)及其應(yīng)用[J]. 中南大學(xué)學(xué)報（自然科學(xué)版）， 2011， 42（12）： 3772-3776.

YAO Y F， XING L T. Improvement of C4.5 decision tree continuous attributes segmentation threshold algorithm and its application[J]. Journal of Central South University （Science and Technology）， 2011， 42（12）： 3772-3776.

[16] 劉傳澤， 陳龍現(xiàn)， 劉大偉， 等. 基于剪枝決策樹的人造板表面缺陷識別[J]. 計算機(jī)系統(tǒng)應(yīng)用， 2018， 27（11）： 168-173.

LIU C Z， CHEN L X， LIU D W， et al. Defect recognition of wood-based panel surface using pruning decision tree[J]. Computer Systems & Applications， 2018， 27 （11）： 168-173.

[17] 王剛. 動力鋰電池梯次利用與回收處理[M]. 北京： 中國電力出版社， 2015： 120-123.

WANG G. Echelon utilization and recycling of power lithium battery[M]. Beijing： China Electric Power Press， 2015： 120-123.

[18] LAI X， QIAO D D， ZHENG Y J， et al. A rapid screening and regrouping approach based on neural networks for large-scale retired lithium-ion cells in second-use applications[J]. Journal of Cleaner Production， 2019， 213： 776-791.

Grade classification method of decommissioned power

battery based on improved CART algorithm

LIU Yongcheng1， LIU Jiewen2， YANG Qian1， SONG Wenqin1， GUO Yongji2， WANG Xinggui2

（1.Economics and Technology Research Institute of State Grid Gansu Electric Power Company， Lanzhou，Gansu 730050， China;

2. College of Electrical and Information Engineering， Lanzhou University of Technology， Lanzhou， Gansu 730050， China）

Abstract：Aiming at the problems of poor consistency and low efficiency of grade classification of decommissioned power battery， a grade classification method of decommissioned power battery based on improved CART algorithm is proposed. Firstly， the basic principle of the traditional CART algorithm is analyzed. In order to overcome the defect of large amount of computation， Fayyad boundary point determination theorem is combined with the CART algorithm， and the optimal threshold point of attributes is selected to reduce the amount of computation and improve the classification efficiency. Secondly， based on the cost complexity post pruning algorithm， the cross validation method is used to further optimize the algorithm。Finally， the improved CART algorithm is applied to the screening and classification of decommissioned power batteries. The experimental results show that the improved CART algorithm can effectively improve the grade classification efficiency of decommissioned power battery while maintaining a high accuracy.

Keywords：decommissioned power battery; grade classification; improved CART algorithm; optimal threshold point