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

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

粗糙集理論是由波蘭科學家Pawlak提出的[1],近年來,無論是在理論方面還是在應用實踐方面都取得了很大的進展,它不僅為信息科學和認知科學提供了新的科學邏輯和研究方法,而且為智能信息處理提供了有效的處理技術.

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

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

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

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

1 基礎概念

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

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

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

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

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

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

1.2 分離優(yōu)勢覆蓋集及其相關性質

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

(1)

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

表1 優(yōu)勢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}}.

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

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

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

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

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

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

(2)

(3)

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

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

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

輸出:C的屬性約簡子集B.

1) 令B=?;

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

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

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

{計算B關于C的補集CB;

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

選取

B=B∪{b0};

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

5) 輸出屬性約簡結果B.

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

首先,基于性質3,對C內5個屬性進行遍歷,得到內重要度大于0的有c1,約簡子集B={c1},此時

約簡停止,得到C的約簡子集B={a1,a2}.

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

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

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

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

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

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

(4)

(5)

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

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

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

輸出:C的屬性約簡子集B.

1) 令B=?;

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

{計算B關于C的補集CB;

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

選取

B=B∪{b0};

5) 輸出屬性約簡結果B.

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

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

該結果與例2所得結果相同.

4 實驗分析

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

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

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

圖1 Forestfires數(shù)據(jù)集約簡后屬性的個數(shù)

圖2 PdM數(shù)據(jù)集約簡后屬性的個數(shù)

圖3 DryBean數(shù)據(jù)集約簡后屬性的個數(shù)

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

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

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

分析圖表可知,RED-DSD與RED-DSDS算法的約簡效果在12個數(shù)據(jù)集上是相同的,但是約簡效率不同.當屬性個數(shù)相同,增加對象的個數(shù)時,RED-SDS算法、RED-DSDS算法與廣義β粗糙集模型的約簡算法(取β=0.5)運行時間長短的次序不發(fā)生改變,但廣義β粗糙集模型的約簡算法(取β=0.5)在Forestfires-3數(shù)據(jù)集和Forestfires-4數(shù)據(jù)集中沒有進行任何約簡,在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個屬性,即廣義β粗糙集模型的約簡算法(取β=0.5)在約簡的過程中區(qū)分度弱于其他2種算法.當對象的個數(shù)相同,增加屬性的個數(shù)時,RED-DSDS算法增加的運行時間要大于RED-SDS算法,而廣義β粗糙集模型的約簡算法(取β=0.5)增加的運行時間要大于其他2種算法,且在增加相同屬性個數(shù)的情況下,RED-SDS算法運行時間的變化最小,廣義β粗糙集模型的約簡算法(取β=0.5)運行時間的變化最大.由此可見,在需要一定的區(qū)分度且約簡效果不變的情況下,當對象個數(shù)較少,屬性個數(shù)較多時,RED-SDS算法更加合適; 當對象個數(shù)較多,屬性個數(shù)較少時,RED-DSDS算法更加合適; 當對于區(qū)分度不做過多要求的時候,廣義β粗糙集模型的約簡算法更加合適.

5 結 論

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