徐菲菲

(上海電力學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 200090)

區(qū)間值決策表的決策風(fēng)險(xiǎn)最小化屬性約簡(jiǎn)

徐菲菲

(上海電力學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 200090)

針對(duì)目前海量數(shù)據(jù)分析較多情況下從傳統(tǒng)的單條記錄轉(zhuǎn)變?yōu)橐粋€(gè)區(qū)間對(duì)象,將決策粗糙集中風(fēng)險(xiǎn)的概念引入至區(qū)間值決策表中,給出了區(qū)間值決策表決策風(fēng)險(xiǎn)的定義,并提出了決策風(fēng)險(xiǎn)最小化的屬性約簡(jiǎn)方法.該方法可以保證所得到的約簡(jiǎn)集合相對(duì)于決策屬性具有較強(qiáng)的分類能力,同時(shí)保證約簡(jiǎn)集合的決策風(fēng)險(xiǎn)最小.區(qū)間值決策表的決策風(fēng)險(xiǎn)最小化約簡(jiǎn)使得定義的約簡(jiǎn)具有更強(qiáng)的理論性和可解釋性.

區(qū)間值決策表; 決策粗糙集; 風(fēng)險(xiǎn)最小化; 屬性約簡(jiǎn)

現(xiàn)實(shí)生活中獲得的數(shù)據(jù)集通常復(fù)雜多樣,特別對(duì)于很多測(cè)量值數(shù)據(jù),大多表現(xiàn)為一定范圍內(nèi)的連續(xù)值.對(duì)于這類數(shù)據(jù)來說,如果需要構(gòu)建某種分類模型,僅依靠某一條數(shù)據(jù)判定其類別信息,不僅物理意義難以解釋,而且耗費(fèi)大量的時(shí)間.處理這類數(shù)據(jù)應(yīng)主要考慮時(shí)間段內(nèi)的整體數(shù)據(jù)特征,將一條數(shù)據(jù)單獨(dú)作為一個(gè)對(duì)象的傳統(tǒng)數(shù)據(jù)處理方式已不適合用來處理這類數(shù)據(jù).有學(xué)者提出采用均勻時(shí)間段內(nèi)的最大值和最小值來近似替代該連續(xù)區(qū)間中的所有對(duì)象,將整個(gè)數(shù)據(jù)集轉(zhuǎn)換成區(qū)間值形式.

經(jīng)典粗糙集理論是PAWLAK Z[1]于1982年提出的一種處理不精確、不一致、不完整數(shù)據(jù)的數(shù)學(xué)工具,已在人工智能、機(jī)器學(xué)習(xí)、模式識(shí)別等領(lǐng)域得到廣泛應(yīng)用,并獲得普遍認(rèn)可,成為研究熱點(diǎn).然而PAWLAK Z粗糙集模型所要求的條件過于嚴(yán)格,導(dǎo)致容錯(cuò)能力較差,并不能處理復(fù)雜的實(shí)際問題.因此,有學(xué)者將嚴(yán)格的等價(jià)關(guān)系變成概率包含關(guān)系,提出了概率粗糙集模型[2-6].變精度粗糙集[2](Variable Pawlak Rough Sets,VPRS)作為概率粗糙集的典型代表之一,受到了眾多學(xué)者的關(guān)注.VPRS通過調(diào)整參數(shù),大大提高了分類精度.然而對(duì)VPRS參數(shù)的語義缺乏合理的解釋.YAO Y Y引入了Bayes風(fēng)險(xiǎn)理論,通過Bayes風(fēng)險(xiǎn)理論對(duì)VPRS的參數(shù)進(jìn)行了解釋,并給出相應(yīng)的推導(dǎo)方法,從而提出了決策粗糙集(Decision-Theoretic Rough Sets,DTRS)模型[3].

屬性約簡(jiǎn)是粗糙集理論所要研究的核心內(nèi)容之一.YAO Y Y等人[7]最早對(duì)DTRS的屬性約簡(jiǎn)進(jìn)行了探討,得出了DTRS約簡(jiǎn)過程中正域、負(fù)域和邊界域均不具備單調(diào)性的結(jié)論;JIA X Y等人[8]指出DTRS應(yīng)以風(fēng)險(xiǎn)代價(jià)作為約簡(jiǎn)的啟發(fā)式因子;LI H X等人[9]定義了一種新的α-正域約簡(jiǎn),指出約簡(jiǎn)前后的正域只需要保持非減性;MA X A等人[10]研究了決策粗糙集的多類問題;CHEBROLU S和SANJEEVI S G[11]將遺傳算法引入到DTRS中,通過優(yōu)化算法得到參數(shù)值;LIU J B等人[12]提出了測(cè)試代價(jià)最優(yōu)下的正域?qū)傩约s簡(jiǎn)算法.

上述所有的研究和方法都是基于傳統(tǒng)的數(shù)據(jù).而在實(shí)際生活中存在大量的區(qū)間值數(shù)據(jù),本文將DTRS理論引入至區(qū)間值決策表中,構(gòu)建區(qū)間值決策表下的DTRS模型,繼而給出區(qū)間值決策表中風(fēng)險(xiǎn)損失的計(jì)算方法以及約簡(jiǎn)的定義,最后以風(fēng)險(xiǎn)損失最小化作為啟發(fā)式信息提出其相應(yīng)的屬性約簡(jiǎn)方法.

1 區(qū)間值決策表的相關(guān)概念和性質(zhì)

對(duì)于大多數(shù)區(qū)間值數(shù)據(jù)集,類別信息通常都是離散的.因此,本文討論的是條件屬性為區(qū)間值、而決策屬性為離散值的情況.

定義1設(shè)有區(qū)間值決策表[13]DT=,其中C∪D表示非空有限屬性集合,包括條件屬性集C={a1,a2,a3,…,am}和決策屬性集D=xhfnxxr兩部分;V=VC∪VD,其中VC表示條件屬性值集合,VD表示決策屬性值集合;f:U×C→VC是區(qū)間值映射,f:U×D→VD為單值映射.

表1 區(qū)間值決策

在區(qū)間值決策表中,如果采用經(jīng)典粗糙集的嚴(yán)格等價(jià)關(guān)系,很難對(duì)論域形成合理的劃分,完全取值相同的區(qū)間最大最小值才能形成一個(gè)等價(jià)類,由此得到的等價(jià)關(guān)系過于苛刻.因此,我們將相似度的概念引入?yún)^(qū)間值決策表中,用來度量區(qū)間之間的相似程度,從而采用相似關(guān)系替代嚴(yán)格的等價(jià)關(guān)系,增強(qiáng)模型的實(shí)際應(yīng)用能力.

2 區(qū)間值決策表下的決策粗糙集

有了上述區(qū)間值決策表的基本概念和性質(zhì),我們可以將決策粗糙集引入至區(qū)間值決策表中,給出區(qū)間值決策表的上下近似概念.

定義4設(shè)有區(qū)間值決策表DT=,給定一參數(shù)水平λ∈[0,1],任意屬性子集A?C,X?U,定義X關(guān)于A的粗糙上、下近似為:

?};

根據(jù)區(qū)間值決策表上下近似的概念,我們可以定義區(qū)間值對(duì)象子集X關(guān)于任意屬性子集A的正域、負(fù)域、邊界域.

λPP≤λBP<λNP,且λNN≤λBN<λPN

(1)

令:

(2)

(3)

(4)

由于損失函數(shù)滿足式(1)的關(guān)系,根據(jù)YAO Y Y的三支決策語義規(guī)則[3],可以推導(dǎo)出α∈(0,1],γ∈(0,1),β∈[0,1).

(5)

因此,我們可以推導(dǎo)出如下決策規(guī)則:

定義6設(shè)有區(qū)間值決策表DT=,給定一參數(shù)水平λ∈[0,1],對(duì)屬性子集A?C的決策風(fēng)險(xiǎn)定義為:

由于正確分類的風(fēng)險(xiǎn)為零,即λPP=λNN=0,則有:

定義6表示區(qū)間值決策表中的決策風(fēng)險(xiǎn)應(yīng)該是每個(gè)區(qū)間值對(duì)象ul在參數(shù)水平λ下根據(jù)規(guī)則劃分到相應(yīng)區(qū)域產(chǎn)生的所有風(fēng)險(xiǎn)的總和.

定義7設(shè)有區(qū)間值決策表DT=,給定一參數(shù)水平λ∈[0,1],屬性子集A?C是C的一個(gè)決策風(fēng)險(xiǎn)最小化約簡(jiǎn),當(dāng)且僅當(dāng):

(1)A=arg(minA?C(CostA));

(2) ?A′?A,CostA′>CostA.

在經(jīng)典粗糙集下,我們對(duì)屬性約簡(jiǎn)的定義基本都保持整個(gè)決策表正域不變.實(shí)際上,保持正域不變,而負(fù)域又為空集,也就相當(dāng)于保證了整個(gè)決策表的邊界域不變,即3個(gè)區(qū)域均不變.而在決策粗糙集中,無論正域、邊界域還是負(fù)域在屬性增減過程中的變化都是非單調(diào)的.通過分析發(fā)現(xiàn),決策粗糙集中,每一個(gè)對(duì)象被劃分的區(qū)域應(yīng)該由風(fēng)險(xiǎn)決定.劃分到哪一個(gè)區(qū)域的風(fēng)險(xiǎn)最小,就將該對(duì)象劃到相應(yīng)的區(qū)域.因此,我們應(yīng)該依據(jù)風(fēng)險(xiǎn)最小化原則進(jìn)行決策.同樣,在區(qū)間值決策表中研究約簡(jiǎn)問題,也應(yīng)以風(fēng)險(xiǎn)最小化原則為基準(zhǔn),計(jì)算約簡(jiǎn)時(shí)不必關(guān)注約簡(jiǎn)前后區(qū)域的變化,而應(yīng)考慮區(qū)域變化后所帶來的決策風(fēng)險(xiǎn)是否減小.即添加一個(gè)屬性使得整個(gè)區(qū)間值決策表的決策風(fēng)險(xiǎn)總和減少,則認(rèn)為該屬性屬于約簡(jiǎn)子集.

3 區(qū)間值決策表屬性約簡(jiǎn)方法

3.1 屬性重要度

條件屬性子集相對(duì)于決策屬性的分類能力可以通過屬性重要度反映,屬性重要度越高,條件屬性子集對(duì)決策屬性的分類能力應(yīng)該越強(qiáng),反之亦然.已有學(xué)者基于風(fēng)險(xiǎn)最小提出了決策粗糙集的屬性約簡(jiǎn)算法.如文獻(xiàn)[8]給出了決策風(fēng)險(xiǎn)最小化的定義,并以此作為啟發(fā)式算子提出了相應(yīng)的約簡(jiǎn)算法,然而該定義并沒有考慮所選屬性的分類能力,僅考慮了決策風(fēng)險(xiǎn)因子.文獻(xiàn)[15]在文獻(xiàn)[8]的基礎(chǔ)上增加了屬性重要度的概念,考慮風(fēng)險(xiǎn)代價(jià)的同時(shí)考慮到所選屬性的分類能力,然而該方法僅僅考慮單個(gè)屬性的重要性,并沒有考慮到屬性之間的強(qiáng)相關(guān)性.兩個(gè)具有強(qiáng)分類能力的屬性在一起并不一定能增加其分類能力.文獻(xiàn)[16]給出了聯(lián)合屬性重要度的定義.以上研究均是針對(duì)傳統(tǒng)的決策粗糙集模型,無法直接用于區(qū)間值決策表.因此,本文給出區(qū)間值決策表下的屬性重要度定義.

(6)

P(u)反映的是在條件屬性子集A下的λ-相容類對(duì)決策屬性分類能力的大小.式(6)中取最大值是希望確定性程度最大,這樣取值符合概率統(tǒng)計(jì)的實(shí)際意義.

j=1,2,3,…,v,l=1,2,3,…,n

(7)

定義8表明區(qū)間值決策表中的屬性重要度的計(jì)算是通過求論域中所有區(qū)間值對(duì)象的λ-相容類相對(duì)于決策的分類能力總和.即考察的對(duì)象是整個(gè)論域U,因此對(duì)每個(gè)區(qū)間值對(duì)象的條件概率P(ul)求和.

3.2 區(qū)間值決策表的決策風(fēng)險(xiǎn)最小化啟發(fā)式約簡(jiǎn)算法

在現(xiàn)實(shí)應(yīng)用中,計(jì)算約簡(jiǎn)往往采用啟發(fā)式屬性約簡(jiǎn)算法.相比于差別矩陣方法,雖然啟發(fā)式約簡(jiǎn)只能得到一個(gè)約簡(jiǎn)結(jié)果,但可以大大地提高約簡(jiǎn)效率.啟發(fā)式約簡(jiǎn)主要有前向添加,后向刪除,以及兩者結(jié)合3種方法.當(dāng)條件屬性較多時(shí),采用后向刪除法耗費(fèi)大量的時(shí)間.因此,本文采用前向添加屬性的方法,提出了一種區(qū)間值決策表的決策風(fēng)險(xiǎn)最小化屬性約簡(jiǎn)算法(Attribute Reduction Based on Minimum Decision Cost in Interval-Valued Decision Tables).算法的主要思想是:首先根據(jù)定義8,選擇屬性重要度最大的一個(gè)條件屬性添加到約簡(jiǎn)子集中,計(jì)算決策表的風(fēng)險(xiǎn)代價(jià)總和.在該屬性基礎(chǔ)上,計(jì)算每個(gè)屬性聯(lián)合該屬性的整體重要度,選出重要度最大的聯(lián)合屬性子集,計(jì)算代價(jià).如果添加后決策表的風(fēng)險(xiǎn)代價(jià)比未添加前的小,說明此屬性可以幫助減小決策表的風(fēng)險(xiǎn)代價(jià),同時(shí)該屬性對(duì)決策具有強(qiáng)分類能力.反之,算法結(jié)束,得到的屬性子集即為約簡(jiǎn)結(jié)果.算法描述如下.

輸入:區(qū)間值決策表DT=,參數(shù)α,β,λ.

輸出:屬性約簡(jiǎn)集合A.

步驟1 置A=?.

步驟2 根據(jù)定義8和輸入的λ,先計(jì)算單個(gè)條件屬性ak∈C的重要度SGF({ak}),k=1,2,3,…,m,將SGF({ak})值最大的條件屬性ak添加到約簡(jiǎn)集合A中(若存在多個(gè)區(qū)間值屬性同時(shí)達(dá)到最大值,則選λ-相容類個(gè)數(shù)最少的屬性作為ak).

步驟3 計(jì)算CostA:

(1) 計(jì)算論域U中的每個(gè)區(qū)間值對(duì)象ul的P(ul)值,l=1,2,3,…,n;

(2) 根據(jù)決策規(guī)則以及輸入的α和β值將區(qū)間值對(duì)象ul劃分到正域,邊界域,負(fù)域中;

(3) 根據(jù)式(6)計(jì)算CostA.

步驟4 對(duì)區(qū)間值條件屬性集C-A重復(fù):

(1) 對(duì)每個(gè)區(qū)間值條件屬性ak∈C-A,計(jì)算聯(lián)合重要度SGF(A∪{ak});

(2) 選擇SGF(A∪{ak})值最大的條件屬性ak(若存在多個(gè)條件屬性同時(shí)達(dá)到最大值,則將λ-相容類個(gè)數(shù)最少的屬性作為ak);

(3) 令A(yù)′=A∪{ak},計(jì)算CostA′;

(4) 如果CostA′≤CostA,則A=A′;否則終止.

步驟5 最后得到的A就是區(qū)間值條件屬性C相對(duì)于D的一個(gè)決策風(fēng)險(xiǎn)最小化約簡(jiǎn).

該算法從空集開始,逐個(gè)添加區(qū)間值條件屬性至約簡(jiǎn)集合中.在添加區(qū)間值條件屬性時(shí),同時(shí)考慮到已有的約簡(jiǎn)子集,保證每次添加的屬性都是在現(xiàn)有約簡(jiǎn)子集條件下最重要的,并且保證添加該條件屬性后該決策表的風(fēng)險(xiǎn)代價(jià)比未添加前的要小,即該屬性的添加不會(huì)增加決策表的風(fēng)險(xiǎn)代價(jià);否則算法結(jié)束,得到的條件屬性子集A即為最終的約簡(jiǎn)結(jié)果.

4 結(jié) 論

(1) 本文給出了區(qū)間值決策表下的屬性重要度計(jì)算方法,通過對(duì)每個(gè)區(qū)間值對(duì)象的條件概率P(ul)求和,得到論域中所有區(qū)間值對(duì)象的λ-相容類相對(duì)于決策的分類能力總和,符合概率統(tǒng)計(jì)的實(shí)際意義.

(2) 本文所提方法不僅可以保證所得到的約簡(jiǎn)集合相對(duì)于決策屬性具有較強(qiáng)的分類能力,同時(shí)保證約簡(jiǎn)集合的決策風(fēng)險(xiǎn)最小.區(qū)間值決策表的決策風(fēng)險(xiǎn)最小化約簡(jiǎn)使得定義的約簡(jiǎn)具有更強(qiáng)的理論性和可解釋性.

[1] PAWLAK Z.Rough sets[J].International Journal of Computer & Information Sciences,1982,11(5):341-356.

[2] ZIAKO W.Variable precision rough set mode[J].Journal of Computer and System Sciences,1993,46(1):39-59.

[3] YAO Y Y.Decision-theoretic rough set models[C]//Proceedings of the 2th International Conference on Rough Sets and Knowledge Technology.LNAI.Heidelberg:Springrt,2007:1-12.

[4] HU Q H,ZHANG L,CHEN D G,etal.Gaussian kernel based fuzzy rough sets:model,uncertainty measures and applications[J].International Journal of Approximate Reasoning,2010,51(4):453-471.

[5] SLZAK D.Rough sets and bayes factor[M]//SKOWRONA P J F.Transactions on Rough Sets.Berlin:Springer,2005:202-229.

[6] HERBERT J P,YAO J T.Game-theoretic risk analysis in decision-theoretic rough sets[C]//Proceedings of the 3th International Conference on Rough Sets and Knowledge Technology,Chengdu,China,2008:132-139.

[7] YAO Y Y,ZHAO Y.Attribute reduction in decision-theoretic roughset models[J].Information Sciences,2008,178(17):3 356-3 373.

[8] JIA X Y,LIAO W H,TANG Z M,etal.Minimum cost attributereduction in decision-theoretic rough set models[J].Information Sciences,2013,219(1):151-167.

[9] LI H X,ZHOU X Z,ZHAO J B,etal.Attribute reduction in decision-theoretic rough set model:a further investigation[C]//Proceedings of the 6th International Conference on Rough Sets and Knowledge Technology,Banff,Canada,2011:466-475.

[10] MA X A,WANG G Y,YU H,etal.Decision region distribution preservation reduction in decision-theoretic rough set model[J].Information Sciences,2014,278(10):614-640.

[11] CHEBROLU S,SANJEEVI S G.Attribute reduction in decision-theoretic rough set models using genetic algorithm[C]//Proceedings of the 2th International Conference on the Swarm Evolutionary and Memetic Computing,Visakhapatnam,India,2011:307-314.

[12] LIU J B,MIN F,LIAO S J,etal.Minimal test cost feature selection with positive region constraint[C]//Proceedings of the 8thInternational Conference on Rough Sets and Current Trends in Computing,Chengdu,China,2012:259-266.

[13] 徐菲菲,雷景生,畢忠勤,等.大數(shù)據(jù)環(huán)境下多決策表的區(qū)間值全局近似約簡(jiǎn)[J].軟件學(xué)報(bào),2014,25(9):2 119-2 135.

[14] 郭慶,劉文軍,焦賢發(fā),等.一種基于模糊聚類的區(qū)間值屬性約簡(jiǎn)算法[J].模糊系統(tǒng)與數(shù)學(xué).2013,27(1):149-153.

[15] 徐菲菲,畢忠勤,雷景生.基于聯(lián)合屬性重要度的決策風(fēng)險(xiǎn)最小化屬性約簡(jiǎn)[J].計(jì)算機(jī)科學(xué),2016,43(s1):40-43.

[16] 于洪,姚園,趙軍.一種有效的基于風(fēng)險(xiǎn)最小化的屬性約簡(jiǎn)算法[J].南京大學(xué)學(xué)報(bào)(自科科學(xué)版),2013,49(2):133-141.

AttributeReductionBasedonMinimumDecisionRiskinInterval-ValuedDecisionTables

XU Feifei

(SchoolofComputerScienceandTechnology,ShanghaiUniversityofElectricPower,Shanghai200090,China)

It is found that it is more reasonable when the study objects are treated as intervals than as single records in many circumstances.An attribute reduction method in interval-valued decision tables is proposed.The concept of risk in decision-theoretic rough sets is introduced into interval-valued decision tables,and the definition of decision risk is given.The corresponding reduction method is also proposed,which can not only guarantee that the obtained reduction set has stronger classification ability relative to the decision attributes,but also make sure the minimum decision risk.The defined reduction of decision risk in interval-valued decision tables is more theore-tical and interpretable.

interval-valued decision tables; decision-theoretic rough sets; minimum risk; attribute reduction

10.3969/j.issn.1006-4729.2017.05.012

2017-03-09

徐菲菲(1983-),女,博士,副教授,江西南昌人.主要研究方向?yàn)榇植诩?數(shù)據(jù)挖掘,大數(shù)據(jù)等.E-mail:xufeifei1983@hotmail.com.

國(guó)家自然科學(xué)基金(61272437,61305094);上海市教育發(fā)展基金會(huì)和上海市教育委員會(huì)“晨光計(jì)劃”(13CG58);上海市自然科學(xué)基金(13ZR1417500).

TP18;TP273.24

A

1006-4729(2017)05-0471-06

(編輯 桂金星)