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

(同濟大學 機械與能源工程學院，上海 201804)

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

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

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

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

1 經典算法

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

(1)

(2)

(3)

(4)

(5)

(6)

算法的具體步驟如下。

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

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

⑥ 若P中所有等價類中的決策值相等，則結束，否則轉步驟③。

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

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

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

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

2.1 基于分辨矩陣的候選斷點改進選取策略

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

圖2 UACC算法選取候選斷點的流程圖[8]

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

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

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

(7)

表2 根據(jù)屬性a的等價類構建的候選斷點分辨矩陣

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

結合上述分辨矩陣相鄰行的取值分析可知，若屬性a的相鄰等價類均屬于同一個決策等價類，則不存在可選的候選斷點，否則，就應當添加候選斷點。因此，基于分辨矩陣的候選斷點選取策略的步驟如下。

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

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

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

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

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

圖3 基于分辨矩陣的候選斷點選擇流程

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

2.2 基于信息增益率的結果斷點改進選取策略

(8)

(9)

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

(10)

(11)

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

2.3 改進的停止條件

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

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

為了改善原算法中過于嚴格的停止條件，結合基于信息增益率的結果斷點選取策略，設置如下停止條件。

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

② 當最大信息增益率低于0時，停止選取。

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

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

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

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

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

改進后的算法流程如圖4所示。

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

3 算法性能測試

3.1 與經典算法對比實驗

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

圖5 候選斷點對比圖

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

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

圖6 結果斷點對比圖

圖7 結果斷點選取中的信息熵變化圖

3.2 與近年提出的算法對比實驗

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

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

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

4 結束語

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

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

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

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