基于改進CART算法的退役動力電池等級篩選方法

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

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

關鍵詞：退役動力電池；等級篩選；改進CART算法；最優閾值點

中圖分類號： TP399文獻標識碼： ADOI：10.3969/j.issn.1007-791X.2024.01.0060

引言

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

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

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

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

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

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

1CART算法及其改進

1.1CART算法基本原理

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

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

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

步驟2：根據S中屬性A的某個特征值a，把S分為兩個樣本子集S1和S2。此時，Gini系數的計算公式變為

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

1.2改進CART算法

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

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

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

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

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

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

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

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

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

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

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

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

由圖2可知，當決策樹深度到5左右時，準確率達到97.5 %，隨著決策樹深度增大，準確率不再發生明顯變化。因此，設定最大決策深度為5。

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

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

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

將α從0一直增加，會出現滿足Aα（t）= Aα（T）條件的節點，得到子樹T2。重復上述步驟，不斷增加α值就可以得到所有子樹序列Ti （i =1， 2， …， n）。此時，剪枝閾值αi變為

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

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

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

步驟6：輸入以上最優參數，分析對比改進前后CART決策樹算法的準確率和運行效率。改進CART算法流程如圖4所示。

3實驗驗證及分析

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

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

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

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

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

分析實驗結果可知，在不同數據集S下，改進CART算法相比于傳統CART算法，在保持較高準確率的前提下，顯著提高了退役動力電池等級篩選的效率。

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

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

4結論

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

參考文獻

[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] 李建林， 李雅欣， 呂超， 等. 碳中和目標下退役電池篩選聚類關鍵技術研究[J]. 電網技術， 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] 馬玲， 魏成偉， 謝麗蓉， 等. 基于退役動力電池的風儲有功功率協調控制策略[J]. 太陽能學報， 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] 李建林， 李雅欣， 呂超， 等. 退役動力電池梯次利用關鍵技術及現狀分析[J]. 電力系統自動化， 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] 張雷， 劉穎琦， 張力， 等. 中國儲能產業中動力電池梯次利用的商業價值[J]. 北京理工大學學報（社會科學版）， 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] 安富強. 電動車用鋰離子電池的一致性研究[D]. 北京：北京科技大學， 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]. 湖南大學學報（自然科學版）， 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] 李加升， 吳兔利， 劉玉芳， 等. 基于充放電曲線的鋰電池智能分選系統研究[J]. 電源技術， 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] 王雅輝， 錢宇華， 劉郭慶. 基于模糊優勢互補互信息的有序決策樹算法[J]. 計算機應用， 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]. 計算機工程與應用， 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]. 計算機工程與設計， 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連續屬性分割閾值算法改進及其應用[J]. 中南大學學報（自然科學版）， 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] 劉傳澤， 陳龍現， 劉大偉， 等. 基于剪枝決策樹的人造板表面缺陷識別[J]. 計算機系統應用， 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