周愛國， 于江洋， 施金磊， 王嘉立， 魏榕慧

(同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804)

新能源智能車監(jiān)控?cái)?shù)據(jù)中部分連續(xù)屬性的取值精度過高，導(dǎo)致后續(xù)挖掘算法會(huì)占用過多的空間和時(shí)間，且訓(xùn)練出的模型容易出現(xiàn)過擬合的情況。數(shù)據(jù)離散化的目的是將連續(xù)的屬性取值轉(zhuǎn)換為離散的區(qū)間值[1]，以降低屬性的取值精度，斷點(diǎn)集合則是算法劃分離散區(qū)間的依據(jù)。對(duì)于新能源智能車來說，理想的離散化算法應(yīng)在保證故障分類效果的前提下，獲得盡可能小的斷點(diǎn)集合。

離散化算法可分為無監(jiān)督離散化和有監(jiān)督離散化。其中，無監(jiān)督離散化不考慮類信息，因此這類算法效率高，但是離散化后數(shù)據(jù)的分類精度較差；而有監(jiān)督離散化則使用故障類別信息作為啟發(fā)條件，例如信息熵、方差等，從而有偏向性地設(shè)置斷點(diǎn)，可以獲得較好的離散化效果[2]。目前，常用的有監(jiān)督離散化算法可分為：基于統(tǒng)計(jì)的離散化算法、基于類和屬性相關(guān)度的離散化算法以及基于信息熵的離散化算法等[3]。其中，基于統(tǒng)計(jì)的離散化算法[4-6]雖然具有較強(qiáng)的數(shù)據(jù)理論基礎(chǔ)，但計(jì)算過于復(fù)雜，故不宜采用；基于類和屬性相關(guān)性的離散化[7]則需要保證離散區(qū)間不小于類別數(shù)，且容易丟失信息；而謝宏等[8]提出的基于粗糙集和信息熵的離散化算法，將信息熵和粗糙集理論結(jié)合起來，使用決策表的信息熵來描述斷點(diǎn)的重要性，算法在連續(xù)屬性取值較多時(shí)也具有較高的計(jì)算效率，適用于數(shù)據(jù)量較大的場(chǎng)景，是一種經(jīng)典的數(shù)據(jù)離散化算法。

但謝宏等提出的算法存在候選斷點(diǎn)數(shù)量較多、結(jié)果集無用斷點(diǎn)較多的問題。高原等[9]提出了改進(jìn)的快速數(shù)據(jù)離散化算法，該算法根據(jù)決策屬性D的等價(jià)類定義了連續(xù)屬性a的等價(jià)類數(shù)值串，并根據(jù)等價(jià)類數(shù)值串對(duì)之間的關(guān)系來判斷是否存在可能的候選斷點(diǎn)，實(shí)驗(yàn)結(jié)果表明所選的候選斷點(diǎn)數(shù)量大幅減少。然而，構(gòu)建等價(jià)類數(shù)值串并進(jìn)行判斷的時(shí)間復(fù)雜度為O(UlogU/U+UD)，對(duì)于數(shù)據(jù)量較大的新能源智能車來說，會(huì)花費(fèi)太多的時(shí)間用于構(gòu)建等價(jià)類數(shù)值串。楊海鵬[10]在粗糙集以及信息熵的基礎(chǔ)上，集成了模糊聚類的方法，采用特征空間重組方法進(jìn)行粗糙集連續(xù)屬性離散數(shù)據(jù)的模糊特征重構(gòu)，提取粗糙集連續(xù)屬性離散數(shù)據(jù)的信息熵，并對(duì)所提取的信息熵進(jìn)行聚類分析，實(shí)現(xiàn)離散檢驗(yàn)優(yōu)化。實(shí)驗(yàn)表明采用該方法進(jìn)行粗糙集連續(xù)屬性離散檢驗(yàn)的數(shù)據(jù)聚類性較好，但隨著迭代次數(shù)的增加，收斂程度出現(xiàn)了明顯的下降。徐東等[11]提出一種基于森林優(yōu)化的粗糙集離散化算法，該算法依據(jù)變精度粗糙集理論，對(duì)多維連續(xù)屬性離散化，通過設(shè)計(jì)適宜的值函數(shù)，構(gòu)建森林尋優(yōu)網(wǎng)絡(luò)，迭代搜索最優(yōu)斷點(diǎn)子集。實(shí)驗(yàn)表明，相比于傳統(tǒng)算法，該算法能避免局部最優(yōu)問題，具有一定的通用性，但是受參數(shù)預(yù)設(shè)值影響較大，需進(jìn)行相關(guān)實(shí)驗(yàn)來選擇參數(shù)預(yù)設(shè)值。

因此，如何在保證分類效果的前提下兼顧算法的計(jì)算效率，以盡可能少的斷點(diǎn)完成新能源智能車故障類別的劃分是數(shù)據(jù)離散化的關(guān)鍵?；诖耍疚奶岢鲆环N基于分辨矩陣和信息增益率的有監(jiān)督離散化算法，通過決策表的條件屬性與決策屬性構(gòu)建候選斷點(diǎn)分辨矩陣，以此判斷相鄰屬性取值之間是否有可能的斷點(diǎn)，從而減少不必要的結(jié)果斷點(diǎn)劃分。在此基礎(chǔ)上，利用信息增益率作為評(píng)價(jià)指標(biāo)，優(yōu)先選擇劃分效果較好的斷點(diǎn)集合，并設(shè)置閾值改善原來較為嚴(yán)格的停止條件以進(jìn)一步提高算法效率。不管是在實(shí)際數(shù)據(jù)測(cè)試中，還是在不同數(shù)據(jù)集上的實(shí)驗(yàn)中，改進(jìn)后的算法在不影響分類效果的前提下，效率明顯提升，為新能源智能車連續(xù)屬性的離散化提供了技術(shù)支撐。

1 經(jīng)典算法

筆者提出的算法是在謝宏等[8]提出的算法上改進(jìn)而來的，這里首先對(duì)該算法進(jìn)行詳細(xì)介紹。

(1)

(2)

(3)

(4)

(5)

(6)

算法的具體步驟如下。

① 初始化P={U},Res=?,Cand=?,H=H(U)。

② 根據(jù)UACC算法計(jì)算Cand。

⑥ 若P中所有等價(jià)類中的決策值相等，則結(jié)束，否則轉(zhuǎn)步驟③。

該算法的整體流程圖如圖1所示。

圖1 基于粗糙集和信息熵的離散化算法流程圖[8]

綜上，基于粗糙集和信息熵的離散化算法可分為3個(gè)步驟：① 選取候選斷點(diǎn)集合；② 從候選斷點(diǎn)集合中篩選結(jié)果斷點(diǎn)集合；③ 根據(jù)結(jié)果斷點(diǎn)集合離散化連續(xù)屬性。其中，步驟③只是按照固定的規(guī)則離散化連續(xù)屬性，因此，算法效果的好壞主要取決于前兩步。然而，該算法雖然計(jì)算效率高，但在候選斷點(diǎn)和結(jié)果斷點(diǎn)選取過程仍有以下不足之處：① UACC算法選區(qū)的候選斷點(diǎn)數(shù)量較多，存在較多無用的斷點(diǎn)；② 基于信息熵的結(jié)果斷點(diǎn)選取不夠合理，僅考慮了決策表的整體信息熵，而未考慮劃分后子集的情況；③P中等價(jià)類的決策屬性相等這個(gè)停止條件過于理想，算法不能及時(shí)停止。因此，本文針對(duì)這3點(diǎn)不足之處，提出對(duì)應(yīng)的改進(jìn)措施，并最終完成新能源智能車的監(jiān)控?cái)?shù)據(jù)離散化。

2 基于分辨矩陣和信息增益率的連續(xù)屬性離散化算法

2.1 基于分辨矩陣的候選斷點(diǎn)改進(jìn)選取策略

理想的候選斷點(diǎn)選取策略，應(yīng)當(dāng)在保證原有信息系統(tǒng)的分辨關(guān)系的前提下，選擇最少的候選斷點(diǎn)。ChiMerge系列算法[4-6]以及基于粗糙集[12-14]和信息熵的離散化算法都使用UACC算法選擇候選斷點(diǎn)，其流程如圖2所示。

圖2 UACC算法選取候選斷點(diǎn)的流程圖[8]

可見，該算法在選取候選斷點(diǎn)時(shí)沒有考慮類的信息，但由于將所有不同的取值都劃分到了不同的區(qū)間，因此仍能保證原有信息系統(tǒng)的分辨關(guān)系。然而，該算法會(huì)選取過多無用的斷點(diǎn)。以表1所示的新能源智能車監(jiān)控?cái)?shù)據(jù)為例，若采用UACC算法選取候選斷點(diǎn)，則Cand={293.25,294.875,295.125,295.375,295.625,295.875}。然而，{293.25,295.375,295.875}的相鄰記錄均屬于同一個(gè)故障類別，在這些記錄之間加入候選斷點(diǎn)，并不能幫助分辨故障的類別，反而會(huì)占用過多的內(nèi)存，并且會(huì)增加后續(xù)結(jié)果斷點(diǎn)選取花費(fèi)的時(shí)間。

表1 新能源監(jiān)控?cái)?shù)據(jù)的連續(xù)屬性取值

為了既保證實(shí)例的分辨關(guān)系又能獲得較少的候選斷點(diǎn)，可考慮在選取候選斷點(diǎn)過程中引入樣本的類別信息，從而減少候選斷點(diǎn)集合規(guī)模。為此，提出一種基于分辨矩陣的候選斷點(diǎn)選取策略。為了便于描述，定義映射函數(shù)fd(i,j)為

(7)

表2 根據(jù)屬性a的等價(jià)類構(gòu)建的候選斷點(diǎn)分辨矩陣

文獻(xiàn)[9]中定義的等價(jià)類數(shù)值串其實(shí)是通過該矩陣的列向量來構(gòu)建的，列向量dj中所有取值為1所對(duì)應(yīng)的屬性取值就構(gòu)成了dj的等價(jià)類數(shù)值串。本文則借助該矩陣中的相鄰行來判斷是否存在可能的候選斷點(diǎn)，對(duì)于相鄰行ri和ri+1來說，可能的取值情況分為以下3種。

結(jié)合上述分辨矩陣相鄰行的取值分析可知，若屬性a的相鄰等價(jià)類均屬于同一個(gè)決策等價(jià)類，則不存在可選的候選斷點(diǎn)，否則，就應(yīng)當(dāng)添加候選斷點(diǎn)。因此，基于分辨矩陣的候選斷點(diǎn)選取策略的步驟如下。

① 對(duì)任意一個(gè)連續(xù)型條件屬性a∈C，初始化候選斷點(diǎn)集合Cand={}。

③ 由屬性值序列Lva得到屬性a的基本集U/IND(a)={A0,A1,…,Ana}。

④ 根據(jù)屬性a的基本集以及決策屬性建立CCM。

⑤ 遍歷CCM的相鄰行，若為情況①，則忽略該候選斷點(diǎn)；否則，將相鄰屬性值的中值加入候選斷點(diǎn)集合。

基于分辨矩陣的候選斷點(diǎn)選取流程如圖3所示。

圖3 基于分辨矩陣的候選斷點(diǎn)選擇流程

該算法的時(shí)間復(fù)雜度取決于CCM的構(gòu)建和相鄰行的對(duì)比，設(shè)數(shù)據(jù)集的記錄總數(shù)為n，屬性a的取值個(gè)數(shù)為na，決策屬性取值個(gè)數(shù)為nd。CCM構(gòu)建過程主要記錄屬性a的等價(jià)類所包含的決策屬性取值，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(na)×O(nd)。最終得到的CCM共有na行，相鄰行則有na-1對(duì)，則對(duì)比相鄰行的時(shí)間復(fù)雜度為O(na)。因此，基于CCM的候選斷點(diǎn)選取算法的整體時(shí)間復(fù)雜度為O(n)×O(na)，與O(n)同階。另外，使用bitmap來存儲(chǔ)CCM可大大減小存儲(chǔ)空間，即用一個(gè)int型的變量來存儲(chǔ)一個(gè)基本集所含有的類別情況，因此CCM整體占用空間大小為(na-1)×32-bit。

2.2 基于信息增益率的結(jié)果斷點(diǎn)改進(jìn)選取策略

(8)

(9)

綜上，基于信息增益的選取策略僅考慮了斷點(diǎn)給整體帶來的不純度下降，而沒有考慮到斷點(diǎn)對(duì)子集劃分的影響。在C4.5決策樹中，算法使用分裂信息熵來衡量測(cè)試屬性取值數(shù)量的混亂度，從而改善了ID3算法對(duì)取值個(gè)數(shù)較多的測(cè)試屬性的傾向性。而基于信息增益的選取策略本質(zhì)上與ID3算法類似，只是每次新增斷點(diǎn)后，劃分的子集數(shù)量恒為兩個(gè)。因此，本文提出基于信息增益率的結(jié)果斷點(diǎn)選取策略。

(10)

(11)

此外，在C4.5決策樹中，為了避免由于屬性取值過少導(dǎo)致信息增益率過大，使得算法傾向于選取取值較少的屬性，算法將首先選取信息增益大于平均增益的屬性，然后再選取信息增益率最大的屬性。類似地，本文首先將信息增益小于平均值的候選斷點(diǎn)排除，而后再選取信息增益率最大的斷點(diǎn)。

2.3 改進(jìn)的停止條件

離散化算法的停止條件在很大程度上決定了最終的離散區(qū)間數(shù)量，停止條件過于嚴(yán)格，會(huì)導(dǎo)致算法選取過多的結(jié)果斷點(diǎn)，離散化效果一般；反之，如停止條件過于寬松，選取的結(jié)果斷點(diǎn)將過少，難以保證分類效果。因此，理想的停止條件應(yīng)在保證分類效果的前提下，獲得盡可能少的結(jié)果斷點(diǎn)。

由圖1可知，基于粗糙集和信息熵的離散化算法共有兩個(gè)停止條件。

為了改善原算法中過于嚴(yán)格的停止條件，結(jié)合基于信息增益率的結(jié)果斷點(diǎn)選取策略，設(shè)置如下停止條件。

① 當(dāng)決策表的信息熵H(P)小于Hstop時(shí)，停止選取。原有的第一個(gè)停止條件是為了保證結(jié)果斷點(diǎn)能夠保留原有信息系統(tǒng)的分辨關(guān)系，然而，由于受不相容樣本和不相關(guān)屬性的影響，這種停止條件過于嚴(yán)格，有時(shí)難以觸發(fā)。實(shí)際情況中，當(dāng)決策表的信息熵下降到一定閾值時(shí)，說明此時(shí)依靠斷點(diǎn)已經(jīng)能將樣本劃分到純度較高的子集中，故可以提前停止結(jié)果斷點(diǎn)選取。

② 當(dāng)最大信息增益率低于0時(shí)，停止選取。

綜上，基于分辨矩陣和信息增益率的離散化算法步驟如下。

① 初始化P={U};Res=?;Cand=?;H=H(U)。

② 屬性a升序排列求解基本集U/IND(a)，并建立CCM。

③ 根據(jù)CCM選取候選斷點(diǎn)集合Cand。

⑦ 若P中所有等價(jià)類中除了不相容樣本外的決策值均相等，則結(jié)束算法，否則轉(zhuǎn)至步驟④。

改進(jìn)后的算法流程如圖4所示。

圖4 基于分辨矩陣和信息增益率的離散化算法流程圖

3 算法性能測(cè)試

3.1 與經(jīng)典算法對(duì)比實(shí)驗(yàn)

為了對(duì)比經(jīng)典算法和改進(jìn)算法的離散化效果，本文以新能源智能車的電池管理系統(tǒng)屬性為例，分別采用謝宏等提出的傳統(tǒng)離散化算法和改進(jìn)后的離散化算法進(jìn)行離散化。算法離散化過程中，二者選取的候選斷點(diǎn)結(jié)果如圖5所示。

圖5 候選斷點(diǎn)對(duì)比圖

可見，傳統(tǒng)算法共選取了1487個(gè)候選斷點(diǎn)，改進(jìn)算法選取了351個(gè)候選斷點(diǎn)，減少了76.4%的無效斷點(diǎn)。由于算法選取候選斷點(diǎn)的過程很快，故改進(jìn)算法在選取候選斷點(diǎn)過程中節(jié)省的時(shí)間不明顯。然而，后續(xù)的結(jié)果斷點(diǎn)選取需要不斷遍歷每個(gè)斷點(diǎn)計(jì)算信息熵，因此改進(jìn)算法在結(jié)果斷點(diǎn)選取上花費(fèi)的時(shí)間相應(yīng)地減少了76.4%，隨著數(shù)據(jù)集的不斷增長，改進(jìn)算法的效率將明顯優(yōu)于傳統(tǒng)算法。

二者選取的結(jié)果斷點(diǎn)數(shù)量如圖6所示，傳統(tǒng)算法選取了349個(gè)結(jié)果斷點(diǎn)，改進(jìn)算法選取了138個(gè)結(jié)果斷點(diǎn)，改進(jìn)算法減少了60.5%的結(jié)果斷點(diǎn)。原始數(shù)據(jù)中所有屬性的取值個(gè)數(shù)為1505，改進(jìn)算法將電池屬性的取值減少為原來的9.17%，從而極大地減少了后續(xù)分類算法的計(jì)算時(shí)間和內(nèi)存占用。

圖6 結(jié)果斷點(diǎn)對(duì)比圖

圖7 結(jié)果斷點(diǎn)選取中的信息熵變化圖

3.2 與近年提出的算法對(duì)比實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證本文提出的基于分辨矩陣和信息增益率的離散化算法的有效性，從UCI數(shù)據(jù)庫中選取含有連續(xù)型屬性的數(shù)據(jù)集Iris、Wine、Shuttle、Ecoli，分別采用3種離散化算法進(jìn)行離散化：算法A，謝宏等[8]提出的經(jīng)典算法，即基于信息熵的粗糙集離散化算法；算法B，于宏濤等[15]提出的基于粗糙集理論與CAIM準(zhǔn)則的C4.5改進(jìn)算法；算法C，筆者提出的改進(jìn)算法，即基于分辨矩陣和信息增益率的離散化算法。其中，算法B是近年提出的數(shù)據(jù)離散化算法，在不同數(shù)據(jù)集上均取得了不錯(cuò)的效果。實(shí)驗(yàn)結(jié)果如表3所示。

表3 UCI數(shù)據(jù)庫離散化結(jié)果

由公共數(shù)據(jù)集的離散化結(jié)果可知，改進(jìn)算法對(duì)多個(gè)數(shù)據(jù)庫的離散化結(jié)果均具有最少的候選斷點(diǎn)數(shù)量和最少的結(jié)果斷點(diǎn)數(shù)量，且從測(cè)試集的預(yù)測(cè)精度來看，改進(jìn)算法離散化后模型的預(yù)測(cè)精度有所提升。與經(jīng)典算法以及近年提出的算法相比，筆者提出的改進(jìn)措施在保證了離散化后數(shù)據(jù)的預(yù)測(cè)精度前提下，降低了候選斷點(diǎn)數(shù)量和結(jié)果斷點(diǎn)數(shù)量，其有效性得到了驗(yàn)證。

4 結(jié)束語

本文主要針對(duì)新能源智能車連續(xù)屬性過多導(dǎo)致后續(xù)挖掘算法會(huì)占用過多的空間和時(shí)間，且訓(xùn)練出的模型容易出現(xiàn)過擬合的情況，在粗糙集理論和信息熵的基礎(chǔ)上提出了基于分辨矩陣和信息增益率的離散化算法，主要內(nèi)容如下。

① 針對(duì)傳統(tǒng)離散化算法選取候選斷點(diǎn)過多的問題，提出了基于分辨矩陣的候選斷點(diǎn)選取策略，使用條件屬性的等價(jià)類構(gòu)建候選斷點(diǎn)分辨矩陣，以此來判斷相鄰屬性取值之間是否存在可能的候選斷點(diǎn)，公共數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，該策略能夠有效地減少候選斷點(diǎn)數(shù)量，相比傳統(tǒng)的UACC算法，將候選斷點(diǎn)由1487個(gè)減少至了351個(gè)，減少了76.4%的無用斷點(diǎn)，后續(xù)的結(jié)果斷點(diǎn)選取也相應(yīng)地節(jié)省了76.4%的時(shí)間。

② 為了使離散化算法選取更為合理的結(jié)果斷點(diǎn)，借鑒C4.5算法對(duì)取值數(shù)量較多屬性的平衡措施，提出了基于信息增益率的結(jié)果斷點(diǎn)選取策略，并對(duì)傳統(tǒng)算法中較為嚴(yán)格的停止條件進(jìn)行了改進(jìn)，新能源智能車的離散化結(jié)果表明，改進(jìn)后的結(jié)果斷點(diǎn)選取策略將結(jié)果斷點(diǎn)數(shù)量由349個(gè)降低至了138個(gè)，減少了60.5%的結(jié)果斷點(diǎn)，且斷點(diǎn)劃分后的子集信息熵和傳統(tǒng)的結(jié)果斷點(diǎn)選取策略相差不大。

改進(jìn)后的算法在保持原來的分類效果的基礎(chǔ)上，大幅減少了結(jié)果斷點(diǎn)集的數(shù)量，提高了計(jì)算效率，對(duì)新能源智能車連續(xù)屬性的離散化具有借鑒和參考價(jià)值。