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

徐菲菲

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

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

徐菲菲

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

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

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

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

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

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

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

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

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

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

表1 區(qū)間值決策

在區(qū)間值決策表中,如果采用經(jīng)典粗糙集的嚴(yán)格等價關(guān)系,很難對論域形成合理的劃分,完全取值相同的區(qū)間最大最小值才能形成一個等價類,由此得到的等價關(guān)系過于苛刻.因此,我們將相似度的概念引入?yún)^(qū)間值決策表中,用來度量區(qū)間之間的相似程度,從而采用相似關(guān)系替代嚴(yán)格的等價關(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ū)間值對象子集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],對屬性子集A?C的決策風(fēng)險定義為:

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

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

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

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

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

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

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

3.1 屬性重要度

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

(6)

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

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

(7)

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

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

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

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

輸出:屬性約簡集合A.

步驟1 置A=?.

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

步驟3 計算CostA:

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

(2) 本文所提方法不僅可以保證所得到的約簡集合相對于決策屬性具有較強(qiáng)的分類能力,同時保證約簡集合的決策風(fēng)險最小.區(qū)間值決策表的決策風(fēng)險最小化約簡使得定義的約簡具有更強(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ū)間值全局近似約簡[J].軟件學(xué)報,2014,25(9):2 119-2 135.

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

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

[16] 于洪,姚園,趙軍.一種有效的基于風(fēng)險最小化的屬性約簡算法[J].南京大學(xué)學(xué)報(自科科學(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-),女,博士,副教授,江西南昌人.主要研究方向為粗糙集,數(shù)據(jù)挖掘,大數(shù)據(jù)等.E-mail:xufeifei1983@hotmail.com.

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

TP18;TP273.24

A

1006-4729(2017)05-0471-06

(編輯 桂金星)