基于決策表相容度和屬性重要度的連續屬性離散化算法*

王成宇 林名馳

（1.海軍工程大學管理工程與裝備經濟系 武漢 430033）（2.92690部隊施工管理室 三亞 572000）

1 引言

粗糙集理論（Rough Sets）是波蘭數學家Pawlak教授[1]于1982年提出的一種處理不精確、不完全與不相容知識的數學理論，其屬性約簡和屬性重要度的概念在預測模型的篩選和組合[2]具有較強的應用價值，對于艦船維修費預測意義重大。粗糙集理論只能用于處理離散型數據，對于連續型數據難以有效應用，然而實際的艦船維修費用數據卻是連續型數據，所以，對于連續型數據的離散化處理便成為了對該類問題進行數據預處理的重要環節，且連續屬性的最優離散化問題是一個NP-hard問題[3]，其對于其他功能的實現具有重要意義。

針對連續屬性離散化問題，按照離散化過程是否考慮決策表中條件屬性與決策屬性之間的關系可以分為無監督離散化和有監督離散化，其中無監督離散化的常用方法有等距法、等頻法等，該類方法易于理解、計算簡便，但是離散化過程可能改變原決策表的不可分辨關系，導致決策表不相容的問題。有監督離散化算法在過程中對條件屬性與決策屬性的關系予以考慮，避免了決策表不相容問題的出現，衣曉等[4]提出一種改進的基于斷點重要性的離散化方法，通過對每個條件屬性逐一判斷其斷點的重要性以達到離散化的目的，通過實例分析證明了該方法的有效性；劉靜等[5]提出基于斷點辨別力的離散化算法，以斷點辨別力表征斷點的重要性，以加入斷點后各等價類中實例是否相同作為算法終止條件，能夠保證決策表的分辨關系且不改變其相容度。部分學者以無監督離散化算法為基礎，同樣得到了較好的離散化效果，陶志等[6]提出一種領域獨立的基于決策屬性支持度的連續屬性離散化算法，通過實例分析比較，說明了該算法的有效性；苗奪謙[7]利用決策表的不相容度作為反饋信息，提出一種基于動態層次聚類的連續屬性離散化算法，該算法通過在過程中對決策表及各條件屬性不相容度的判別避免了離散化處理后決策表不相容的情況。

屬性約簡是粗糙集理論的重要功能之一，決策表中各條件屬性對于決策屬性的重要性是不同的，屬性約簡的目的是在保持決策表分類能力不變的前提下，剔除掉冗余的條件屬性，保留對于決策屬性更重要的條件屬性，最終簡化決策表。在基于粗糙集理論的艦船維修費用預測模型篩選和組合預測問題中，需要在多個單項預測模型中篩選出若干預測模型進行組合預測模型的構建，若采用常用的有監督的離散化算法進行處理則可能存在一個問題，即離散化后的每一個條件屬性均能保證在原有分類能力不變的情況下完成對于決策屬性的分類，且各條件屬性對于決策屬性的重要度相同，難以對決策表進行屬性約簡，便無法達到簡化決策表并篩選模型進行組合預測的目的。無監督離散化算法對于決策表中條件屬性和決策屬性的離散過程是相互獨立的，不考慮二者之間的相對關系，故不會出現前述情況，所以本文以無監督離散化算法為基礎進行改進來處理此類數據表。除常用的無監督離散化算法存在的可能導致決策表不相容的問題以外，文獻[4]中的改進算法在初次離散化時取最大分割點數，且采用逐個將條件屬性加入到決策表后判別決策屬性支持度再調整分割點數的方法，可能產生冗余的分割點，導致離散化結果不夠簡化；文獻[7]中所提改進算法需要分別對決策表的不相容度、各條件屬性的不相容度進行計算與判別，計算過程較為復雜。

針對無監督離散化算法自身存在的可能造成決策表不相容的問題以及文獻[4]、[7]中存在的諸多問題，本文嘗試引入決策表相容度的概念作為反饋信息，從決策表的整體出發來計算相容度，首先選取數值合理的斷點數對數據表進行初始離散化，同時以各模型的屬性重要度作為表征其重要程度的度量對條件屬性進行排序，通過對決策表相容度的判別，依排序情況逐個地對各條件屬性的離散化斷點數進行調整，并結合實例進行應用分析。

2 粗糙集及離散化的相關概念

2.1 粗糙集理論

決策表是一個由四元組（U，R，V，f）構成的信息表知識表達系統，其中U=｛x1，…，xn｝是有限的對象集合即論域。R=C∪｛d｝是屬性集合，子集C和｛d｝分別被稱為條件屬性集合決策屬性集。是屬性值的集合，VA表示屬性A∈R的屬性值范圍，即屬性A的值域；f：U×A→V是一個信息函數，它指定U中每個對象x的屬性值。

2.2 離散化問題的描述

2.3 決策表的相容性

在一個決策表S=（U，C，D，V，f）中，對于 ?ci∈C，x，y∈U，若所有f（x，ci）=f（y，ci），均有f（x，D）=f（y，D），則該決策表成為相容決策表，或一致決策表，表中所有的規則均為確定性規則；對于?ci∈C，x，y∈U，若存在f（x，ci）=f（y，ci），但f（x，D）≠f（y，D），則稱該決策表為不相容決策表，或不一致決策表，其不一致項所構成的規則為不確定性規則。

3 傳統的無監督離散化算法及其改進算法的問題

傳統的無監督離散化算法有等距法和等頻法，其中等距法離散化的步驟如下。

取各條件屬性對應屬性值的最大值ximax和最小值ximin（i=1，2，…，m，表示條件屬性的序號），確定類別數k，將屬性值的取值范圍進行劃分，得到分段區間，則每個劃分區段的斷點值為ximin+lΔi（l=1，2，…，k），將各屬性值分別歸入相應劃分區段內并賦予特征值l（l=1，2，…，k），即得到離散化后的決策表。

但是由于在該離散化過程中不考慮條件屬性與決策屬性之間的關系，所以可能改變決策表的原有不可分辨關系，造成決策表不相容的問題?，F舉例對該問題進行簡要說明?，F有數據表見表1。

表1 數據表

采用等距法對其進行離散化處理，為使離散化后類別不致過于集中或過于分散，選取k=2，得到決策表見表2。

表2 離散化后的決策表

由決策表可知，對象1和2、3和4具有相同的條件屬性值，但是對象1、2與對象3、4的決策屬性值不同，該決策表不相容，故經過等距法離散化后改變了原決策表的不可分辨關系，造成了原決策表信息的損失，若直接根據屬性約簡的定義進行計算，可得屬性b的支持度r=rC=0.2，所以屬性b是該決策表約簡結果，而屬性a和c均為冗余屬性，但是如果｛a，b｝或｛b，c｝構成約簡屬性集時，對象1、4和對象2、3之間是可以區分的，而屬性b卻無法單獨區分對象1、4和對象2、3，顯然a、c又不應該被約簡掉，故不相容決策表可能會產生錯誤的約簡結果。

文獻[4]在等距法的基礎上引入了決策表支持度的概念，并以此為反饋信息對決策表的相容性進行控制，但是該方法在初次離散化時選取最大分割點數，再通過逐次對決策表支持度進行判別，減少各條件屬性分割點的數量，這種方法能夠達到簡化離散化類別的目的，但是也可能造成分割點的冗余。

文獻[7]以層次聚類法為基礎，引入了決策表不相容度的概念，并以此為反饋信息對決策表的相容性進行控制，但是該方法需要分別對決策表的不相容度以及各條件屬性的不相容度進行計算并判別，計算過程相對復雜。

根據已有的無監督離散化算法及其改進算法存在的諸多問題，本文嘗試進一步對前述算法進行改進，使新的算法能夠符合艦船維修費預測值數據表的離散化及約簡要求。

4 基于決策表相容度和屬性重要度的連續屬性離散化算法

4.1 決策表的相容度

針對前述問題，本文首先引入決策表相容度[8]的概念。

假設X是由決策表中各條件屬性按屬性值相等確定的等價關系簇，X中等價關系的交仍是一個等價關系，用P表示。用Q表示由決策屬性按屬性值相等確定的等價關系，且由Q確定的等價類子集簇為｛Y1，Y2，…，Yr（d）｝，則決策表的相容度定義如下：

其中，|U|表示論域的基礎；P—(Yi)表示子集Yi在等價關系P下的下近似集；|P—(Yi)|表示P—(Yi)的基數，0 ≤dP（Q）≤ 1，當dP（Q）=1時決策表是相容的。

有效的連續屬性離散化的前提是保證決策表的不可分辨關系不變，即保證決策表整體的規則不發生變化，也即決策表的整體信息不產生損失，由決策表相容度的概念可知，保證決策表的不可分辨關系不變就是保持決策表相容度不變。由此，本文擬將決策表相容度作為反饋信息，從決策表整體出發來計算相容度，通過判別相容度是否發生變化來確定是否需要對離散化過程進行調整。從整體出發計算決策表相容度的做法可以有效地簡化計算過程，避免了對決策表和各條件屬性分別進行運算，同時能夠從整體上保證決策表中的不可分辨關系不發生變化、信息不產生損失。

4.2 斷點設置原則和基于屬性重要度的條件屬性排序依據

根據連續屬性離散化的原則“在不改變原有不可分辨關系的前提下，利用盡可能少的斷點集對連續屬性值構成的空間進行劃分”，為了控制斷點數量，同時保證各條件屬性的斷點數相對均勻，不致出現斷點分布極端不均的情況，本文嘗試采用如下措施進行離散化處理。

首先，在確定初次離散化的斷點數時，根據數據表規模確定較為合理的數值，使離散化后的類別不致過于集中或過于分散，該原則不同于文獻[4]選取最大斷點數進行劃分，同時，根據決策表相容性的判定結果，擬采用逐個調整的方法增加各條件屬性的斷點數，為避免選取條件屬性的盲目性，需要對所有條件屬性進行排序，對于重要性較高的條件屬性，優先增加其斷點數。屬性重要度的度量眾多，如信息熵[9]、互信息[10]、依賴度[11]等，此處同樣采用屬性重要度作為排序依據，因屬性頻率[12]計算簡便、易于理解，故此處采用屬性頻率作為屬性重要度的度量。文獻[12]對屬性頻率的概念進行了詳細的介紹，屬性頻率指單個條件屬性在差別矩陣中出現的頻率，單個條件屬性若在差別矩陣中出現，則表示該屬性可以區分某對對象，即構成對象在決策屬性中的分類，屬性出現的頻率越高，其中差別矩陣的定義如下：

然而不相容對象的存在會對屬性重要度的計算造成干擾，因此在計算屬性重要度時，暫時將不相容對象從決策表中剔除，再進行屬性頻率的計算，重新離散化時一并參與調整，當出現所有對象均不相容的情況時，則對所有對象重新進行離散化，再進行后續計算。

先選取較為合理的斷點數進行劃分，再依據決策表相容度的判別情況增加斷點數可以保證斷點的數量一直處于可控狀態，從而有效控制斷點數量；以屬性重要度為依據對條件屬性排序后再按排序情況逐個對條件屬性的斷點數進行調整，對于重要度較高的條件屬性，優先增加其斷點數，這樣可以使重要程度較高的條件屬性更充分地離散化，同時使斷點分布更加均勻，不致出現極端不均的情況，避免了屬性重要度相差過大從而影響后續屬性約簡過程的問題。

4.3 基于決策表相容度和屬性重要度的連續屬性離散化算法的具體步驟

基于決策表相容度和屬性重要度的連續屬性離散化算法的具體步驟如下。

第一步：根據式（2）計算原數據表的初始相容度dP0（Q）；

第二步：根據數據表規模確定離散化類別數k，采用等距法對各條件屬性及決策屬性進行離散化處理，構建決策表；

第三步：根據決策表，由式（2）計算決策表的相容度dP（Q），并與原數據表的相容度dP0（Q）進行比較：

若dP（Q）≠dP0（Q），則轉至第四步；

若dP（Q）=dP0（Q），則算法終止，轉至第五步；

第四步：根據式（3）和所得差別矩陣計算各條件屬性的屬性重要度，并按屬性重要度對條件屬性進行降序排列，同時取k=k+1，按排序對各條件屬性重新進行離散化處理，并逐次計算相容度，當所有條件屬性均重新離散化后，轉至第三步；

第五步：所得決策表即為離散化后的決策表。

5 例證分析

采用某型艦船小修費用數據為樣本，分別采用移動平均法、一元線性回歸法、ARIMA法、多層感知器和RBF神經網絡進行預測，各單項預測方法標記為 a，b，c，d，e，實際值序列標記為 f，同上取2012-2020年間的數據進行分析，預測結果見表3。

表3 某型艦船小修費用預測值數據表

采用本文提出的改進算法對表3中數據進行離散化處理。

第一步：根據式（2）計算原數據表的相容度dP0（Q）=1。

第二步：根據決策表規模，為了使離散化后類別不致過于分散或過于集中，取k=3，采用等距法對各條件屬性及決策屬性進行離散化處理，構建決策表見表4。

表4 決策表

第三步：根據式（2）計算所得決策表的相容度dP（Q）=0.625，可知該決策表不相容，不相容對象為4、5、6，則將這三個對象從決策表中剔除后得到決策表見表5。

表5 剔除不相容對象后的決策表

同時計算得到各條件屬性的屬性重要度為θ=[0.142857，0.178571，0.214286，0.214286，0.25]，得到條件屬性按屬性重要度的排序結果為E=｛e，c，d，b，a｝；

第四步：判別可得dP（Q）≠1，則取k=4，再次對條件屬性e進行離散化，并重復前述步驟，直到dP（Q）=1，算法終止。

此處，若采用文獻[4]中算法，所得決策表的斷點總數為26，而本文算法所得決策表的斷點總數為16，故本文提出的改進算法可以得到更少的斷點數，離散化效果更好；若采用文獻[7]中算法，則計算步驟更為繁瑣，需要逐次對各條件屬性和整個決策表的不相容度進行判定，而本文方法只需從整個決策表出發進行判定便可達到充分離散化的目的，計算過程更為簡潔。

第五步：最終得到的決策表見表6。

表6 最終決策表

由實例分析可知，經調整后的決策表是相容的，保持了原有的不可分辨關系，避免了重要數據表中重要信息的損失，為后續的篩選和組合環節奠定了良好的基礎。

6 結語

針對基于粗糙集理論的艦船維修費單項預測模型篩選和組合預測模型構建過程中涉及到的連續屬性離散化問題，本文對有監督與無監督離散化算法的適用性及特點進行了分析，指出有監督離散化算法在處理該類數據表的局限性以及無監督離散化算法的可行性，同時指出傳統的無監督離散化算法存在的可能導致決策表不相容的問題和兩種改進算法[2～3]存在的分割點冗余及計算過程復雜的問題。引入決策表相容度的概念，并以此作為反饋信息，從整體上對決策表的相容性進行判別，通過判別決策表的相容性，決定是否對條件屬性進行調整，在保證決策表整體相容性不變的前提下，簡化了計算過程；在初次對各條件屬性進行離散化時，根據數據表規模確定較為合理的斷點數值，而不是選取最大值在逐漸刪減，避免了斷點的冗余；以屬性重要度為依據對條件屬性進行排序，并依據決策表相容性判別情況逐個對條件屬性的離散化斷點數進行調整，使重要程度較高的條件屬性得到更充分的離散化，同時能夠保證斷點分布更為均勻，不致出現斷點分布極端不均的情況，便于后續屬性約簡的順利進行。通過實例分析，驗證了改進算法對于此類數據表處理的有效性。