王成宇 林名馳
(1.海軍工程大學(xué)管理工程與裝備經(jīng)濟(jì)系 武漢 430033)(2.92690部隊(duì)施工管理室 三亞 572000)
粗糙集理論(Rough Sets)是波蘭數(shù)學(xué)家Pawlak教授[1]于1982年提出的一種處理不精確、不完全與不相容知識(shí)的數(shù)學(xué)理論,其屬性約簡(jiǎn)和屬性重要度的概念在預(yù)測(cè)模型的篩選和組合[2]具有較強(qiáng)的應(yīng)用價(jià)值,對(duì)于艦船維修費(fèi)預(yù)測(cè)意義重大。粗糙集理論只能用于處理離散型數(shù)據(jù),對(duì)于連續(xù)型數(shù)據(jù)難以有效應(yīng)用,然而實(shí)際的艦船維修費(fèi)用數(shù)據(jù)卻是連續(xù)型數(shù)據(jù),所以,對(duì)于連續(xù)型數(shù)據(jù)的離散化處理便成為了對(duì)該類問(wèn)題進(jìn)行數(shù)據(jù)預(yù)處理的重要環(huán)節(jié),且連續(xù)屬性的最優(yōu)離散化問(wèn)題是一個(gè)NP-hard問(wèn)題[3],其對(duì)于其他功能的實(shí)現(xiàn)具有重要意義。
針對(duì)連續(xù)屬性離散化問(wèn)題,按照離散化過(guò)程是否考慮決策表中條件屬性與決策屬性之間的關(guān)系可以分為無(wú)監(jiān)督離散化和有監(jiān)督離散化,其中無(wú)監(jiān)督離散化的常用方法有等距法、等頻法等,該類方法易于理解、計(jì)算簡(jiǎn)便,但是離散化過(guò)程可能改變?cè)瓫Q策表的不可分辨關(guān)系,導(dǎo)致決策表不相容的問(wèn)題。有監(jiān)督離散化算法在過(guò)程中對(duì)條件屬性與決策屬性的關(guān)系予以考慮,避免了決策表不相容問(wèn)題的出現(xiàn),衣曉等[4]提出一種改進(jìn)的基于斷點(diǎn)重要性的離散化方法,通過(guò)對(duì)每個(gè)條件屬性逐一判斷其斷點(diǎn)的重要性以達(dá)到離散化的目的,通過(guò)實(shí)例分析證明了該方法的有效性;劉靜等[5]提出基于斷點(diǎn)辨別力的離散化算法,以斷點(diǎn)辨別力表征斷點(diǎn)的重要性,以加入斷點(diǎn)后各等價(jià)類中實(shí)例是否相同作為算法終止條件,能夠保證決策表的分辨關(guān)系且不改變其相容度。部分學(xué)者以無(wú)監(jiān)督離散化算法為基礎(chǔ),同樣得到了較好的離散化效果,陶志等[6]提出一種領(lǐng)域獨(dú)立的基于決策屬性支持度的連續(xù)屬性離散化算法,通過(guò)實(shí)例分析比較,說(shuō)明了該算法的有效性;苗奪謙[7]利用決策表的不相容度作為反饋信息,提出一種基于動(dòng)態(tài)層次聚類的連續(xù)屬性離散化算法,該算法通過(guò)在過(guò)程中對(duì)決策表及各條件屬性不相容度的判別避免了離散化處理后決策表不相容的情況。
屬性約簡(jiǎn)是粗糙集理論的重要功能之一,決策表中各條件屬性對(duì)于決策屬性的重要性是不同的,屬性約簡(jiǎn)的目的是在保持決策表分類能力不變的前提下,剔除掉冗余的條件屬性,保留對(duì)于決策屬性更重要的條件屬性,最終簡(jiǎn)化決策表。在基于粗糙集理論的艦船維修費(fèi)用預(yù)測(cè)模型篩選和組合預(yù)測(cè)問(wèn)題中,需要在多個(gè)單項(xiàng)預(yù)測(cè)模型中篩選出若干預(yù)測(cè)模型進(jìn)行組合預(yù)測(cè)模型的構(gòu)建,若采用常用的有監(jiān)督的離散化算法進(jìn)行處理則可能存在一個(gè)問(wèn)題,即離散化后的每一個(gè)條件屬性均能保證在原有分類能力不變的情況下完成對(duì)于決策屬性的分類,且各條件屬性對(duì)于決策屬性的重要度相同,難以對(duì)決策表進(jìn)行屬性約簡(jiǎn),便無(wú)法達(dá)到簡(jiǎn)化決策表并篩選模型進(jìn)行組合預(yù)測(cè)的目的。無(wú)監(jiān)督離散化算法對(duì)于決策表中條件屬性和決策屬性的離散過(guò)程是相互獨(dú)立的,不考慮二者之間的相對(duì)關(guān)系,故不會(huì)出現(xiàn)前述情況,所以本文以無(wú)監(jiān)督離散化算法為基礎(chǔ)進(jìn)行改進(jìn)來(lái)處理此類數(shù)據(jù)表。除常用的無(wú)監(jiān)督離散化算法存在的可能導(dǎo)致決策表不相容的問(wèn)題以外,文獻(xiàn)[4]中的改進(jìn)算法在初次離散化時(shí)取最大分割點(diǎn)數(shù),且采用逐個(gè)將條件屬性加入到?jīng)Q策表后判別決策屬性支持度再調(diào)整分割點(diǎn)數(shù)的方法,可能產(chǎn)生冗余的分割點(diǎn),導(dǎo)致離散化結(jié)果不夠簡(jiǎn)化;文獻(xiàn)[7]中所提改進(jìn)算法需要分別對(duì)決策表的不相容度、各條件屬性的不相容度進(jìn)行計(jì)算與判別,計(jì)算過(guò)程較為復(fù)雜。
針對(duì)無(wú)監(jiān)督離散化算法自身存在的可能造成決策表不相容的問(wèn)題以及文獻(xiàn)[4]、[7]中存在的諸多問(wèn)題,本文嘗試引入決策表相容度的概念作為反饋信息,從決策表的整體出發(fā)來(lái)計(jì)算相容度,首先選取數(shù)值合理的斷點(diǎn)數(shù)對(duì)數(shù)據(jù)表進(jìn)行初始離散化,同時(shí)以各模型的屬性重要度作為表征其重要程度的度量對(duì)條件屬性進(jìn)行排序,通過(guò)對(duì)決策表相容度的判別,依排序情況逐個(gè)地對(duì)各條件屬性的離散化斷點(diǎn)數(shù)進(jìn)行調(diào)整,并結(jié)合實(shí)例進(jìn)行應(yīng)用分析。
決策表是一個(gè)由四元組(U,R,V,f)構(gòu)成的信息表知識(shí)表達(dá)系統(tǒng),其中U={x1,…,xn}是有限的對(duì)象集合即論域。R=C∪{d}是屬性集合,子集C和{d}分別被稱為條件屬性集合決策屬性集。是屬性值的集合,VA表示屬性A∈R的屬性值范圍,即屬性A的值域;f:U×A→V是一個(gè)信息函數(shù),它指定U中每個(gè)對(duì)象x的屬性值。
在一個(gè)決策表S=(U,C,D,V,f)中,對(duì)于 ?ci∈C,x,y∈U,若所有f(x,ci)=f(y,ci),均有f(x,D)=f(y,D),則該決策表成為相容決策表,或一致決策表,表中所有的規(guī)則均為確定性規(guī)則;對(duì)于?ci∈C,x,y∈U,若存在f(x,ci)=f(y,ci),但f(x,D)≠f(y,D),則稱該決策表為不相容決策表,或不一致決策表,其不一致項(xiàng)所構(gòu)成的規(guī)則為不確定性規(guī)則。
傳統(tǒng)的無(wú)監(jiān)督離散化算法有等距法和等頻法,其中等距法離散化的步驟如下。
取各條件屬性對(duì)應(yīng)屬性值的最大值ximax和最小值ximin(i=1,2,…,m,表示條件屬性的序號(hào)),確定類別數(shù)k,將屬性值的取值范圍進(jìn)行劃分,得到分段區(qū)間,則每個(gè)劃分區(qū)段的斷點(diǎn)值為ximin+lΔi(l=1,2,…,k),將各屬性值分別歸入相應(yīng)劃分區(qū)段內(nèi)并賦予特征值l(l=1,2,…,k),即得到離散化后的決策表。
但是由于在該離散化過(guò)程中不考慮條件屬性與決策屬性之間的關(guān)系,所以可能改變決策表的原有不可分辨關(guān)系,造成決策表不相容的問(wèn)題?,F(xiàn)舉例對(duì)該問(wèn)題進(jìn)行簡(jiǎn)要說(shuō)明?,F(xiàn)有數(shù)據(jù)表見(jiàn)表1。
表1 數(shù)據(jù)表
采用等距法對(duì)其進(jìn)行離散化處理,為使離散化后類別不致過(guò)于集中或過(guò)于分散,選取k=2,得到?jīng)Q策表見(jiàn)表2。
表2 離散化后的決策表
由決策表可知,對(duì)象1和2、3和4具有相同的條件屬性值,但是對(duì)象1、2與對(duì)象3、4的決策屬性值不同,該決策表不相容,故經(jīng)過(guò)等距法離散化后改變了原決策表的不可分辨關(guān)系,造成了原決策表信息的損失,若直接根據(jù)屬性約簡(jiǎn)的定義進(jìn)行計(jì)算,可得屬性b的支持度r=rC=0.2,所以屬性b是該決策表約簡(jiǎn)結(jié)果,而屬性a和c均為冗余屬性,但是如果{a,b}或{b,c}構(gòu)成約簡(jiǎn)屬性集時(shí),對(duì)象1、4和對(duì)象2、3之間是可以區(qū)分的,而屬性b卻無(wú)法單獨(dú)區(qū)分對(duì)象1、4和對(duì)象2、3,顯然a、c又不應(yīng)該被約簡(jiǎn)掉,故不相容決策表可能會(huì)產(chǎn)生錯(cuò)誤的約簡(jiǎn)結(jié)果。
文獻(xiàn)[4]在等距法的基礎(chǔ)上引入了決策表支持度的概念,并以此為反饋信息對(duì)決策表的相容性進(jìn)行控制,但是該方法在初次離散化時(shí)選取最大分割點(diǎn)數(shù),再通過(guò)逐次對(duì)決策表支持度進(jìn)行判別,減少各條件屬性分割點(diǎn)的數(shù)量,這種方法能夠達(dá)到簡(jiǎn)化離散化類別的目的,但是也可能造成分割點(diǎn)的冗余。
文獻(xiàn)[7]以層次聚類法為基礎(chǔ),引入了決策表不相容度的概念,并以此為反饋信息對(duì)決策表的相容性進(jìn)行控制,但是該方法需要分別對(duì)決策表的不相容度以及各條件屬性的不相容度進(jìn)行計(jì)算并判別,計(jì)算過(guò)程相對(duì)復(fù)雜。
根據(jù)已有的無(wú)監(jiān)督離散化算法及其改進(jìn)算法存在的諸多問(wèn)題,本文嘗試進(jìn)一步對(duì)前述算法進(jìn)行改進(jìn),使新的算法能夠符合艦船維修費(fèi)預(yù)測(cè)值數(shù)據(jù)表的離散化及約簡(jiǎn)要求。
針對(duì)前述問(wèn)題,本文首先引入決策表相容度[8]的概念。
假設(shè)X是由決策表中各條件屬性按屬性值相等確定的等價(jià)關(guān)系簇,X中等價(jià)關(guān)系的交仍是一個(gè)等價(jià)關(guān)系,用P表示。用Q表示由決策屬性按屬性值相等確定的等價(jià)關(guān)系,且由Q確定的等價(jià)類子集簇為{Y1,Y2,…,Yr(d)},則決策表的相容度定義如下:
其中,|U|表示論域的基礎(chǔ);P—(Yi)表示子集Yi在等價(jià)關(guān)系P下的下近似集;|P—(Yi)|表示P—(Yi)的基數(shù),0 ≤dP(Q)≤ 1,當(dāng)dP(Q)=1時(shí)決策表是相容的。
有效的連續(xù)屬性離散化的前提是保證決策表的不可分辨關(guān)系不變,即保證決策表整體的規(guī)則不發(fā)生變化,也即決策表的整體信息不產(chǎn)生損失,由決策表相容度的概念可知,保證決策表的不可分辨關(guān)系不變就是保持決策表相容度不變。由此,本文擬將決策表相容度作為反饋信息,從決策表整體出發(fā)來(lái)計(jì)算相容度,通過(guò)判別相容度是否發(fā)生變化來(lái)確定是否需要對(duì)離散化過(guò)程進(jìn)行調(diào)整。從整體出發(fā)計(jì)算決策表相容度的做法可以有效地簡(jiǎn)化計(jì)算過(guò)程,避免了對(duì)決策表和各條件屬性分別進(jìn)行運(yùn)算,同時(shí)能夠從整體上保證決策表中的不可分辨關(guān)系不發(fā)生變化、信息不產(chǎn)生損失。
根據(jù)連續(xù)屬性離散化的原則“在不改變?cè)胁豢煞直骊P(guān)系的前提下,利用盡可能少的斷點(diǎn)集對(duì)連續(xù)屬性值構(gòu)成的空間進(jìn)行劃分”,為了控制斷點(diǎn)數(shù)量,同時(shí)保證各條件屬性的斷點(diǎn)數(shù)相對(duì)均勻,不致出現(xiàn)斷點(diǎn)分布極端不均的情況,本文嘗試采用如下措施進(jìn)行離散化處理。
首先,在確定初次離散化的斷點(diǎn)數(shù)時(shí),根據(jù)數(shù)據(jù)表規(guī)模確定較為合理的數(shù)值,使離散化后的類別不致過(guò)于集中或過(guò)于分散,該原則不同于文獻(xiàn)[4]選取最大斷點(diǎn)數(shù)進(jìn)行劃分,同時(shí),根據(jù)決策表相容性的判定結(jié)果,擬采用逐個(gè)調(diào)整的方法增加各條件屬性的斷點(diǎn)數(shù),為避免選取條件屬性的盲目性,需要對(duì)所有條件屬性進(jìn)行排序,對(duì)于重要性較高的條件屬性,優(yōu)先增加其斷點(diǎn)數(shù)。屬性重要度的度量眾多,如信息熵[9]、互信息[10]、依賴度[11]等,此處同樣采用屬性重要度作為排序依據(jù),因?qū)傩灶l率[12]計(jì)算簡(jiǎn)便、易于理解,故此處采用屬性頻率作為屬性重要度的度量。文獻(xiàn)[12]對(duì)屬性頻率的概念進(jìn)行了詳細(xì)的介紹,屬性頻率指單個(gè)條件屬性在差別矩陣中出現(xiàn)的頻率,單個(gè)條件屬性若在差別矩陣中出現(xiàn),則表示該屬性可以區(qū)分某對(duì)對(duì)象,即構(gòu)成對(duì)象在決策屬性中的分類,屬性出現(xiàn)的頻率越高,其中差別矩陣的定義如下:
然而不相容對(duì)象的存在會(huì)對(duì)屬性重要度的計(jì)算造成干擾,因此在計(jì)算屬性重要度時(shí),暫時(shí)將不相容對(duì)象從決策表中剔除,再進(jìn)行屬性頻率的計(jì)算,重新離散化時(shí)一并參與調(diào)整,當(dāng)出現(xiàn)所有對(duì)象均不相容的情況時(shí),則對(duì)所有對(duì)象重新進(jìn)行離散化,再進(jìn)行后續(xù)計(jì)算。
先選取較為合理的斷點(diǎn)數(shù)進(jìn)行劃分,再依據(jù)決策表相容度的判別情況增加斷點(diǎn)數(shù)可以保證斷點(diǎn)的數(shù)量一直處于可控狀態(tài),從而有效控制斷點(diǎn)數(shù)量;以屬性重要度為依據(jù)對(duì)條件屬性排序后再按排序情況逐個(gè)對(duì)條件屬性的斷點(diǎn)數(shù)進(jìn)行調(diào)整,對(duì)于重要度較高的條件屬性,優(yōu)先增加其斷點(diǎn)數(shù),這樣可以使重要程度較高的條件屬性更充分地離散化,同時(shí)使斷點(diǎn)分布更加均勻,不致出現(xiàn)極端不均的情況,避免了屬性重要度相差過(guò)大從而影響后續(xù)屬性約簡(jiǎn)過(guò)程的問(wèn)題。
基于決策表相容度和屬性重要度的連續(xù)屬性離散化算法的具體步驟如下。
第一步:根據(jù)式(2)計(jì)算原數(shù)據(jù)表的初始相容度dP0(Q);
第二步:根據(jù)數(shù)據(jù)表規(guī)模確定離散化類別數(shù)k,采用等距法對(duì)各條件屬性及決策屬性進(jìn)行離散化處理,構(gòu)建決策表;
第三步:根據(jù)決策表,由式(2)計(jì)算決策表的相容度dP(Q),并與原數(shù)據(jù)表的相容度dP0(Q)進(jìn)行比較:
若dP(Q)≠dP0(Q),則轉(zhuǎn)至第四步;
若dP(Q)=dP0(Q),則算法終止,轉(zhuǎn)至第五步;
第四步:根據(jù)式(3)和所得差別矩陣計(jì)算各條件屬性的屬性重要度,并按屬性重要度對(duì)條件屬性進(jìn)行降序排列,同時(shí)取k=k+1,按排序?qū)Ω鳁l件屬性重新進(jìn)行離散化處理,并逐次計(jì)算相容度,當(dāng)所有條件屬性均重新離散化后,轉(zhuǎn)至第三步;
第五步:所得決策表即為離散化后的決策表。
采用某型艦船小修費(fèi)用數(shù)據(jù)為樣本,分別采用移動(dòng)平均法、一元線性回歸法、ARIMA法、多層感知器和RBF神經(jīng)網(wǎng)絡(luò)進(jìn)行預(yù)測(cè),各單項(xiàng)預(yù)測(cè)方法標(biāo)記為 a,b,c,d,e,實(shí)際值序列標(biāo)記為 f,同上取2012-2020年間的數(shù)據(jù)進(jìn)行分析,預(yù)測(cè)結(jié)果見(jiàn)表3。
表3 某型艦船小修費(fèi)用預(yù)測(cè)值數(shù)據(jù)表
采用本文提出的改進(jìn)算法對(duì)表3中數(shù)據(jù)進(jìn)行離散化處理。
第一步:根據(jù)式(2)計(jì)算原數(shù)據(jù)表的相容度dP0(Q)=1。
第二步:根據(jù)決策表規(guī)模,為了使離散化后類別不致過(guò)于分散或過(guò)于集中,取k=3,采用等距法對(duì)各條件屬性及決策屬性進(jìn)行離散化處理,構(gòu)建決策表見(jiàn)表4。
表4 決策表
第三步:根據(jù)式(2)計(jì)算所得決策表的相容度dP(Q)=0.625,可知該決策表不相容,不相容對(duì)象為4、5、6,則將這三個(gè)對(duì)象從決策表中剔除后得到?jīng)Q策表見(jiàn)表5。
表5 剔除不相容對(duì)象后的決策表
同時(shí)計(jì)算得到各條件屬性的屬性重要度為θ=[0.142857,0.178571,0.214286,0.214286,0.25],得到條件屬性按屬性重要度的排序結(jié)果為E={e,c,d,b,a};
第四步:判別可得dP(Q)≠1,則取k=4,再次對(duì)條件屬性e進(jìn)行離散化,并重復(fù)前述步驟,直到dP(Q)=1,算法終止。
此處,若采用文獻(xiàn)[4]中算法,所得決策表的斷點(diǎn)總數(shù)為26,而本文算法所得決策表的斷點(diǎn)總數(shù)為16,故本文提出的改進(jìn)算法可以得到更少的斷點(diǎn)數(shù),離散化效果更好;若采用文獻(xiàn)[7]中算法,則計(jì)算步驟更為繁瑣,需要逐次對(duì)各條件屬性和整個(gè)決策表的不相容度進(jìn)行判定,而本文方法只需從整個(gè)決策表出發(fā)進(jìn)行判定便可達(dá)到充分離散化的目的,計(jì)算過(guò)程更為簡(jiǎn)潔。
第五步:最終得到的決策表見(jiàn)表6。
表6 最終決策表
由實(shí)例分析可知,經(jīng)調(diào)整后的決策表是相容的,保持了原有的不可分辨關(guān)系,避免了重要數(shù)據(jù)表中重要信息的損失,為后續(xù)的篩選和組合環(huán)節(jié)奠定了良好的基礎(chǔ)。
針對(duì)基于粗糙集理論的艦船維修費(fèi)單項(xiàng)預(yù)測(cè)模型篩選和組合預(yù)測(cè)模型構(gòu)建過(guò)程中涉及到的連續(xù)屬性離散化問(wèn)題,本文對(duì)有監(jiān)督與無(wú)監(jiān)督離散化算法的適用性及特點(diǎn)進(jìn)行了分析,指出有監(jiān)督離散化算法在處理該類數(shù)據(jù)表的局限性以及無(wú)監(jiān)督離散化算法的可行性,同時(shí)指出傳統(tǒng)的無(wú)監(jiān)督離散化算法存在的可能導(dǎo)致決策表不相容的問(wèn)題和兩種改進(jìn)算法[2~3]存在的分割點(diǎn)冗余及計(jì)算過(guò)程復(fù)雜的問(wèn)題。引入決策表相容度的概念,并以此作為反饋信息,從整體上對(duì)決策表的相容性進(jìn)行判別,通過(guò)判別決策表的相容性,決定是否對(duì)條件屬性進(jìn)行調(diào)整,在保證決策表整體相容性不變的前提下,簡(jiǎn)化了計(jì)算過(guò)程;在初次對(duì)各條件屬性進(jìn)行離散化時(shí),根據(jù)數(shù)據(jù)表規(guī)模確定較為合理的斷點(diǎn)數(shù)值,而不是選取最大值在逐漸刪減,避免了斷點(diǎn)的冗余;以屬性重要度為依據(jù)對(duì)條件屬性進(jìn)行排序,并依據(jù)決策表相容性判別情況逐個(gè)對(duì)條件屬性的離散化斷點(diǎn)數(shù)進(jìn)行調(diào)整,使重要程度較高的條件屬性得到更充分的離散化,同時(shí)能夠保證斷點(diǎn)分布更為均勻,不致出現(xiàn)斷點(diǎn)分布極端不均的情況,便于后續(xù)屬性約簡(jiǎn)的順利進(jìn)行。通過(guò)實(shí)例分析,驗(yàn)證了改進(jìn)算法對(duì)于此類數(shù)據(jù)表處理的有效性。