基于分離優(yōu)勢(shì)覆蓋集的Pythagorean模糊決策信息系統(tǒng)的屬性約簡(jiǎn)

張 鑫， 張少譜， 馮 濤， 季紅艷

(1.石家莊鐵道大學(xué) 數(shù)理系,河北 石家莊 050043； 2.河北科技大學(xué) 理學(xué)院,河北 石家莊 050018； 3.中國(guó)人民武裝警察部隊(duì)士官學(xué)校 基礎(chǔ)部,浙江 杭州 311400)

粗糙集理論是由波蘭科學(xué)家Pawlak提出的[1],近年來(lái),無(wú)論是在理論方面還是在應(yīng)用實(shí)踐方面都取得了很大的進(jìn)展,它不僅為信息科學(xué)和認(rèn)知科學(xué)提供了新的科學(xué)邏輯和研究方法,而且為智能信息處理提供了有效的處理技術(shù).

模糊集是由美國(guó)學(xué)者Zadeh提出的[2],它通過(guò)采用模糊集合論將待考察的對(duì)象及反映它的模糊概念聯(lián)系起來(lái),建立適合的隸屬函數(shù),通過(guò)運(yùn)算和變換對(duì)現(xiàn)象進(jìn)行分析.Pythagorean模糊集是由Yager[3-4]提出的,通過(guò)隸屬度和非隸屬度的方式描述對(duì)象,能更好地表示不確定性信息.同時(shí),Pythagorean模糊集也可看作直覺(jué)模糊集[5-7]的推廣,它可以描述隸屬度和非隸屬度之和大于1的情形,擴(kuò)展了應(yīng)用空間.

屬性約簡(jiǎn)是指從原始的屬性集中去除冗余的屬性且保持核心屬性不變,這在信息處理方面有著重要的作用.去除冗余數(shù)據(jù),不僅減少干擾決策的影響因素,還能充分利用運(yùn)行空間,避免不必要的浪費(fèi).由此可見(jiàn),屬性約簡(jiǎn)是數(shù)據(jù)分析的重要組成部分.對(duì)于基于正域的屬性約簡(jiǎn),鄧大勇等[8]提出了可變正域的約簡(jiǎn),即允許正域在一定范圍內(nèi)發(fā)生變化,因此提高了泛化能力; 對(duì)于基于商集的屬性約簡(jiǎn),Thuy等[9]提出了分離商集及D-分離商集,并將其用于決策信息系統(tǒng)的屬性約簡(jiǎn)中,提高了處理大規(guī)模數(shù)據(jù)的效率.

在Pythagorean模糊信息系統(tǒng)的屬性約簡(jiǎn)方面,張少譜等[10]將Pythagorean模糊信息系統(tǒng)的約簡(jiǎn)問(wèn)題轉(zhuǎn)化為圖論中的最小頂點(diǎn)覆蓋問(wèn)題,提高了約簡(jiǎn)的效率; 張嬌嬌等[11]通過(guò)定義Pythagorean模糊決策信息系統(tǒng)上2個(gè)全新的優(yōu)勢(shì)關(guān)系,得到2個(gè)廣義粗糙集模型,并應(yīng)用其研究了Pythagorean模糊決策信息系統(tǒng)的屬性約簡(jiǎn)問(wèn)題,進(jìn)而說(shuō)明了所提出方法的實(shí)用性和有效性;郝江鋒等[12]針對(duì)決策信息為區(qū)間值的Pythagorean模糊決策信息系統(tǒng)，提出了一種基于區(qū)間值Pythagorean 模糊交叉熵的多屬性決策方法.

受到Thuy等[9]提出的分離商集和D-分離商集的啟發(fā),本文中，筆者在Pythagorean模糊決策信息系統(tǒng)中,將形成商集的等價(jià)關(guān)系替換為優(yōu)勢(shì)關(guān)系[13],從而給出了優(yōu)勢(shì)覆蓋集、分離優(yōu)勢(shì)覆蓋集、D-分離優(yōu)勢(shì)覆蓋集等概念.進(jìn)而分別基于分離優(yōu)勢(shì)覆蓋集、D-分離優(yōu)勢(shì)覆蓋集構(gòu)建Pythagorean模糊決策信息系統(tǒng)的屬性約簡(jiǎn)算法，并通過(guò)對(duì)比實(shí)驗(yàn)驗(yàn)證所得到的算法的優(yōu)勢(shì).

1 基礎(chǔ)概念

1.1 Pythagorean模糊決策信息系統(tǒng)

定義1[4，14]設(shè)U為給定的非空論域,集合X={〈x,μX(x),vX(x)〉|x∈U}稱為一個(gè)Pythagorean模糊集,若滿足

定義2[4，14]設(shè)S=(U,AT=C∪D,VPF,f)表示一個(gè)Pythagorean模糊決策信息系統(tǒng),其中U={x1,…,xn}為對(duì)象的集合,AT為屬性集合,C={c1,…,cm}為條件屬性集,D=j5i0abt0b為決策屬性集(本文只考慮決策屬性集只有一個(gè)元素的情形),且C∩D=?,VPF=Vc∪VD,其中Vc,VD分別為條件屬性和決策屬性的值域,f:U×(C∪D)→VPF為論域與屬性集到值域的映射,對(duì)任意的x∈U和a∈AT,有f(x,a)=〈μa(x),va(x)〉, 其中μa(x)為對(duì)象x關(guān)于屬性a的隸屬度;va(x)為對(duì)象x關(guān)于屬性a的非隸屬度,且滿足

μX(x),vX(x)∈[0,1].

則xi關(guān)于條件屬性集B?C的優(yōu)勢(shì)類定義為

xi關(guān)于決策屬性集D的優(yōu)勢(shì)類定義為

1.2 分離優(yōu)勢(shì)覆蓋集及其相關(guān)性質(zhì)

根據(jù)定義4中上、下近似的定義及條件屬性集C與決策屬性集D,可以構(gòu)造出基于正域的協(xié)調(diào)度[15],即

(1)

例1如表1，S=(U,AT=C∪D,VPF,f)為一個(gè)優(yōu)勢(shì)Pythagorean模糊決策信息系統(tǒng),論域U={x1,x2,x3,x4,x5,x6,x7,x8,x9,x10},條件屬性集C={c1,c2,c3,c4,c5},決策屬性集D=j5i0abt0b.根據(jù)上述相關(guān)定義,可得

表1 優(yōu)勢(shì)Pythagorean模糊決策信息系統(tǒng)

{x6,x7,x9,x10},{x3,x6,x8,x9,x10}};

U/≤D={{x1,x10},{x2,x3,x10},{x3},{x1,x3,x4,x10},{x1,

x2,x3,x5,x6,x7,x10},{x2,x3,x6,x10},{x1,x2,

x3,x7,x10},{x1,x2,x3,x4,x5,x6,x7,x8,x10},

{x1,x2,x3,x4,x7,x9,x10},{x10}};

x5,x6,x7,x10},{x2,x3,x6,x10},{x1,x2,x3,x7,x10},

{x1,x2,x3,x4,x5,x6,x7,x8,x10},{x1,x2,x3,x4,x7,x9,x10}}.

性質(zhì)1S=(U,AT=C∪D,VPF,f)為一個(gè)優(yōu)勢(shì)Pythagorean模糊決策信息系統(tǒng),設(shè)C1和C2為C的子集,若C1?C2,則

性質(zhì)2S=(U,AT=C∪D,VPF,f)為一個(gè)優(yōu)勢(shì)Pythagorean模糊決策信息系統(tǒng)，

不妨設(shè)U/≤D={X1,X2,…,Xp}.可得

2 基于分離優(yōu)勢(shì)覆蓋集的屬性約簡(jiǎn)算法

設(shè)S=(U,AT=C∪D,VPF,f)為一個(gè)優(yōu)勢(shì)Pythagorean模糊決策信息系統(tǒng),稱屬性c∈C為C中的必要屬性,當(dāng)且僅當(dāng)PC(D)≠P(C{c})(D); 否則,屬性c為C中的不必要屬性.如果B中的全部屬性均為必要屬性,那么B被稱為C的必要屬性集.

B?C被稱為C的約簡(jiǎn),當(dāng)且僅當(dāng)PB(D)=PC(D)且B為C的必要屬性集.顯然， 根據(jù)(1),即基于正域的協(xié)調(diào)度,屬性子集B?C稱為C的約簡(jiǎn),等價(jià)于γ(B,D)=γ(C,D)且B為C的必要屬性集.B中的元素也被稱為核心屬性.

(2)

(3)

基于內(nèi)外重要度,可以得到一個(gè)啟發(fā)式屬性約簡(jiǎn)算法,即算法1.首先通過(guò)性質(zhì)3得到核心屬性集,然后選取外重要度最大的屬性放入核心屬性集,重復(fù)這個(gè)步驟,直至得到一個(gè)約簡(jiǎn).

算法1基于分離優(yōu)勢(shì)覆蓋集的屬性約簡(jiǎn)算法(簡(jiǎn)稱RED-SDS).

輸入:優(yōu)勢(shì)Pythagorean模糊決策信息系統(tǒng)S=(U,AT=C∪D,VPF,f);

輸出:C的屬性約簡(jiǎn)子集B.

1) 令B=?;

2) for(i=1;i≤|C|;i++)

3) 計(jì)算|P(C,D)|，|P(B,D)|;

4) while|P(C,D)|≠|(zhì)P(B,D)|do

{計(jì)算B關(guān)于C的補(bǔ)集CB;

for(k=1;k≤|CB|;k++)

選取

B=B∪{b0};

計(jì)算|P(B,D)|; }

5) 輸出屬性約簡(jiǎn)結(jié)果B.

例2(續(xù)接例1) 根據(jù)算法1，可以得到例1給出的優(yōu)勢(shì)Pythagorean模糊決策信息系統(tǒng)的屬性約簡(jiǎn).

首先,基于性質(zhì)3,對(duì)C內(nèi)5個(gè)屬性進(jìn)行遍歷,得到內(nèi)重要度大于0的有c1,約簡(jiǎn)子集B={c1},此時(shí)

約簡(jiǎn)停止,得到C的約簡(jiǎn)子集B={a1,a2}.

3 基于D-分離優(yōu)勢(shì)覆蓋集的屬性約簡(jiǎn)算法

這一節(jié),考慮基于D-分離優(yōu)勢(shì)覆蓋集的屬性約簡(jiǎn)算法.

定理1設(shè)S=(U,AT=C∪D,VPF,f)為一個(gè)優(yōu)勢(shì)Pythagorean模糊決策信息系統(tǒng),于是有

令η(C,D)=1-γ(C,D),稱η(C,D)為C對(duì)D的協(xié)調(diào)度.

證根據(jù)性質(zhì)3,由(2)可得,

η(B,D)-η(B,D)=

(4)

(5)

基于上述的內(nèi)外重要度,可以得到基于D-分離優(yōu)勢(shì)覆蓋集的屬性約簡(jiǎn)算法.

算法2基于D-分離優(yōu)勢(shì)覆蓋集的屬性約簡(jiǎn)算法(簡(jiǎn)稱RED-DSDS).

輸入:優(yōu)勢(shì)Pythagorean模糊決策信息系統(tǒng)S=(U,AT=C∪D,VPF,f);

輸出:C的屬性約簡(jiǎn)子集B.

1) 令B=?;

2) for(i=1;i≤|C|;i++)

{計(jì)算B關(guān)于C的補(bǔ)集CB;

for(k=1;k≤|CB|;k++)

選取

B=B∪{b0};

5) 輸出屬性約簡(jiǎn)結(jié)果B.

例3(續(xù)接例1) 根據(jù)算法2,可以得到例1給出的優(yōu)勢(shì)Pythagorean模糊決策信息系統(tǒng)的屬性約簡(jiǎn).

首先,計(jì)算每個(gè)屬性ci對(duì)于C的內(nèi)重要度,對(duì)C內(nèi)5個(gè)屬性進(jìn)行遍歷,得到內(nèi)重要度大于0的有c1,約簡(jiǎn)子集B={c1},此時(shí)η(B,D)=0.5,而η(C,D)=0.4,故繼續(xù)約簡(jiǎn);CB={c2,c3,c4,c5},計(jì)算ci(i= 2,3,4,5)對(duì)于屬性集B的外重要度.可得當(dāng)取c2時(shí),取得最大外重要度,故B=B∪{c2}={c1,c2},此時(shí)η(B,D)=0.4,與η(C,D)相同,約簡(jiǎn)停止,得到C的約簡(jiǎn)子集B={c1,c2}.

該結(jié)果與例2所得結(jié)果相同.

4 實(shí)驗(yàn)分析

為了驗(yàn)證算法1和算法2的有效性,將其與文獻(xiàn)[11]所提出的Pythagorean模糊決策信息系統(tǒng)的屬性約簡(jiǎn)算法進(jìn)行比較.從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中挑選了數(shù)據(jù)集Forestfires，DryBean，Predictive Maintenance (簡(jiǎn)稱PdM)并進(jìn)行處理使其符合要求,分別截取其中4個(gè)數(shù)據(jù)集,數(shù)據(jù)集具體信息如表2所示.下面,分別就RED-SDS算法、RED-DSDS算法、廣義β粗糙集模型的約簡(jiǎn)算法(取β=0.5)[11]進(jìn)行比較.

表2 數(shù)據(jù)集

表2所示的12個(gè)數(shù)據(jù)集截取自UCI數(shù)據(jù)集Forestfires，DryBean，Predictive Maintenance,通過(guò)隸屬度,隨機(jī)生成滿足條件的非隸屬度,組成Pythagorean模糊決策信息系統(tǒng).圖1至圖6分別給出了3種算法對(duì)12個(gè)數(shù)據(jù)集進(jìn)行約簡(jiǎn)后屬性的個(gè)數(shù)及約簡(jiǎn)時(shí)間.

圖1 Forestfires數(shù)據(jù)集約簡(jiǎn)后屬性的個(gè)數(shù)

圖2 PdM數(shù)據(jù)集約簡(jiǎn)后屬性的個(gè)數(shù)

圖3 DryBean數(shù)據(jù)集約簡(jiǎn)后屬性的個(gè)數(shù)

圖4 Forestfires數(shù)據(jù)集的約簡(jiǎn)時(shí)間

圖5 PdM數(shù)據(jù)集的約簡(jiǎn)時(shí)間

圖6 DryBean數(shù)據(jù)集的約簡(jiǎn)時(shí)間

分析圖表可知,RED-DSD與RED-DSDS算法的約簡(jiǎn)效果在12個(gè)數(shù)據(jù)集上是相同的,但是約簡(jiǎn)效率不同.當(dāng)屬性個(gè)數(shù)相同,增加對(duì)象的個(gè)數(shù)時(shí),RED-SDS算法、RED-DSDS算法與廣義β粗糙集模型的約簡(jiǎn)算法(取β=0.5)運(yùn)行時(shí)間長(zhǎng)短的次序不發(fā)生改變,但廣義β粗糙集模型的約簡(jiǎn)算法(取β=0.5)在Forestfires-3數(shù)據(jù)集和Forestfires-4數(shù)據(jù)集中沒(méi)有進(jìn)行任何約簡(jiǎn),在Forestfires-1數(shù)據(jù)集、Forestfires-2數(shù)據(jù)集、PdM-1數(shù)據(jù)集、PdM-2數(shù)據(jù)集、PdM-3數(shù)據(jù)集、PdM-4數(shù)據(jù)集、DryBean-1數(shù)據(jù)集、DryBean-2數(shù)據(jù)集和DryBean-4數(shù)據(jù)集中也僅僅約去1個(gè)屬性,即廣義β粗糙集模型的約簡(jiǎn)算法(取β=0.5)在約簡(jiǎn)的過(guò)程中區(qū)分度弱于其他2種算法.當(dāng)對(duì)象的個(gè)數(shù)相同,增加屬性的個(gè)數(shù)時(shí),RED-DSDS算法增加的運(yùn)行時(shí)間要大于RED-SDS算法,而廣義β粗糙集模型的約簡(jiǎn)算法(取β=0.5)增加的運(yùn)行時(shí)間要大于其他2種算法,且在增加相同屬性個(gè)數(shù)的情況下,RED-SDS算法運(yùn)行時(shí)間的變化最小,廣義β粗糙集模型的約簡(jiǎn)算法(取β=0.5)運(yùn)行時(shí)間的變化最大.由此可見(jiàn),在需要一定的區(qū)分度且約簡(jiǎn)效果不變的情況下,當(dāng)對(duì)象個(gè)數(shù)較少,屬性個(gè)數(shù)較多時(shí),RED-SDS算法更加合適; 當(dāng)對(duì)象個(gè)數(shù)較多,屬性個(gè)數(shù)較少時(shí),RED-DSDS算法更加合適; 當(dāng)對(duì)于區(qū)分度不做過(guò)多要求的時(shí)候,廣義β粗糙集模型的約簡(jiǎn)算法更加合適.

5 結(jié) 論

通過(guò)優(yōu)勢(shì)關(guān)系對(duì)Pythagorean模糊決策信息系統(tǒng)構(gòu)建優(yōu)勢(shì)類,定義了分離優(yōu)勢(shì)覆蓋集及D-分離優(yōu)勢(shì)覆蓋集,得到了基于分離優(yōu)勢(shì)覆蓋集的RED-SDS算法和基于D-分離優(yōu)勢(shì)覆蓋集的RED-DSDS算法.根據(jù)2種算法的特點(diǎn),針對(duì)不同情況的Pythagorean模糊決策信息系統(tǒng),選取合適的算法,具有較好的約簡(jiǎn)效果和約簡(jiǎn)時(shí)間.此外,當(dāng)對(duì)象及屬性個(gè)數(shù)都很多時(shí),降低運(yùn)行時(shí)間并提高整體約簡(jiǎn)效果是下一步需要著力解決的問(wèn)題.