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

王成宇 林名馳

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

1 引言

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

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

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

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

2 粗糙集及離散化的相關(guān)概念

2.1 粗糙集理論

決策表是一個由四元組（U，R，V，f）構(gòu)成的信息表知識表達系統(tǒng)，其中U=｛x1，…，xn｝是有限的對象集合即論域。R=C∪｛d｝是屬性集合，子集C和｛d｝分別被稱為條件屬性集合決策屬性集。是屬性值的集合，VA表示屬性A∈R的屬性值范圍，即屬性A的值域；f：U×A→V是一個信息函數(shù)，它指定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），則該決策表成為相容決策表，或一致決策表，表中所有的規(guī)則均為確定性規(guī)則；對于?ci∈C，x，y∈U，若存在f（x，ci）=f（y，ci），但f（x，D）≠f（y，D），則稱該決策表為不相容決策表，或不一致決策表，其不一致項所構(gòu)成的規(guī)則為不確定性規(guī)則。

3 傳統(tǒng)的無監(jiān)督離散化算法及其改進算法的問題

傳統(tǒng)的無監(jiān)督離散化算法有等距法和等頻法，其中等距法離散化的步驟如下。

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

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

表1 數(shù)據(jù)表

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

表2 離散化后的決策表

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

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

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

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

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

4.1 決策表的相容度

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

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

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

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

4.2 斷點設(shè)置原則和基于屬性重要度的條件屬性排序依據(jù)

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

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

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

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

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

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

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

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

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

若dP（Q）≠dP0（Q），則轉(zhuǎn)至第四步；

若dP（Q）=dP0（Q），則算法終止，轉(zhuǎn)至第五步；

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

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

5 例證分析

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

表3 某型艦船小修費用預(yù)測值數(shù)據(jù)表

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

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

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

表4 決策表

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

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

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

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

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

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

表6 最終決策表

由實例分析可知，經(jīng)調(diào)整后的決策表是相容的，保持了原有的不可分辨關(guān)系，避免了重要數(shù)據(jù)表中重要信息的損失，為后續(xù)的篩選和組合環(huán)節(jié)奠定了良好的基礎(chǔ)。

6 結(jié)語

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