Pythagorean模糊信息系統(tǒng)屬性約簡(jiǎn)的圖論方法

張少譜， 孫 品， 馮 濤

(1. 石家莊鐵道大學(xué) 數(shù)理系 河北 石家莊 050043； 2. 河北科技大學(xué) 理學(xué)院 河北 石家莊 050018)

0 引言

粗糙集[1]是一種刻畫不完整性和不確定性的數(shù)學(xué)工具, 主要思想是利用已知知識(shí)庫(kù)來(lái)刻畫不確定或不精確的知識(shí)，被廣泛應(yīng)用于專家系統(tǒng)、圖像處理、模式識(shí)別、決策分析和風(fēng)險(xiǎn)評(píng)估等領(lǐng)域。

經(jīng)典的粗糙集方法有一定的局限性, 在處理實(shí)值信息系統(tǒng)時(shí), 往往需要將數(shù)據(jù)離散化, 這可能導(dǎo)致一些信息的丟失。 為了解決這個(gè)問題, 文獻(xiàn)[2]提出了模糊粗糙集, 用來(lái)解決數(shù)據(jù)集中存在的不確定性和模糊性, 將模糊集與粗糙集結(jié)合, 給出了實(shí)值數(shù)據(jù)不確定性推理的關(guān)鍵方法。 文獻(xiàn)[3]提出了直覺模糊集, 考慮到了隸屬度、非隸屬度與猶豫度, 可以更好地處理不確定性, 具有更強(qiáng)的處理信息系統(tǒng)的能力。 考慮到其只能描述隸屬度與非隸屬度小于和等于1的情況, 文獻(xiàn)[4]提出了畢達(dá)哥拉斯模糊集, 要求隸屬度與非隸屬度的平方和小于等于1即可, 可行域?yàn)榘霃綖?的1/4圓域, 是非常有現(xiàn)實(shí)意義的。 目前, 畢達(dá)哥拉斯模糊集主要應(yīng)用于多準(zhǔn)則(屬性)決策中[5-6]。 屬性約簡(jiǎn)是粗糙集理論研究的核心內(nèi)容之一, 它是在保持知識(shí)庫(kù)分類能力不變的條件下, 刪除其中不相關(guān)或不重要的屬性。 文獻(xiàn)[7]提出的辨識(shí)矩陣是求最小約簡(jiǎn)的有力工具。 文獻(xiàn)[8]提出了基于辨識(shí)矩陣的屬性集求核算法, 減少了對(duì)象之間不必要的比較以及矩陣中的空值存儲(chǔ)。 文獻(xiàn)[9]提出將形式背景中的屬性約簡(jiǎn)與圖論相結(jié)合, 將形式背景的屬性約簡(jiǎn)問題轉(zhuǎn)化為圖論中的最小頂點(diǎn)覆蓋問題, 并證明這種方法大大減少了算法的時(shí)間復(fù)雜度。 因此我們考慮將辨識(shí)矩陣和最小頂點(diǎn)覆蓋應(yīng)用到Pythagorean模糊信息系統(tǒng)的屬性約簡(jiǎn)中。

本文定義了Pythagorean模糊信息系統(tǒng)中的辨識(shí)矩陣, 將辨識(shí)矩陣的布爾推理問題轉(zhuǎn)化為圖論中的最小頂點(diǎn)覆蓋問題, 給出了屬性約簡(jiǎn)的算法, 并通過實(shí)例表明該算法的有效性, 最后定義了Pythagorean模糊決策信息系統(tǒng)中的屬性約簡(jiǎn)算法, 用實(shí)例證明算法的可行性, 并進(jìn)行了對(duì)比分析。

1 基礎(chǔ)概念

1.1 基于加權(quán)歐幾里得距離的相似度

相似度的定義有很多種方法, 應(yīng)用比較廣泛的是文獻(xiàn)[10]提出的模糊相似關(guān)系。

定義1[10]若F=(U,A,I,f)為一個(gè)模糊信息系統(tǒng),U為對(duì)象集,A為屬性集,I為所有模糊集的集合,f：U×A→I為映射, ?a∈A, 相似度定義為sima(xi,xj)=1-|μa(xi)-μa(xj)|/|μamax-μamin|，其中：μa(xi)、μa(xj)分別為對(duì)象xi、xj對(duì)于屬性a的隸屬度；μamax、μamin分別為所有對(duì)象對(duì)于屬性a的最大和最小隸屬度。 文獻(xiàn)[11]定義了直覺模糊信息系統(tǒng)基于加權(quán)歐幾里得距離的相似關(guān)系。

定義2[11]若F=(U,A,I,f)為直覺模糊信息系統(tǒng),U為對(duì)象集,A為屬性集,I為所有直覺模糊集的集合,f:U×A→I為映射, ?xi,xj∈U,a∈A, 兩個(gè)直覺模糊集分別為f(xi,a)=〈μa(xi),νa(xi)〉和f(xj,a)=〈μa(xj),νa(xj)〉，基于加權(quán)歐幾里得距離的相似度定義為

其中α、β、γ為加權(quán)因子。

1.2 Pythagorean模糊信息系統(tǒng)

1.3 辨識(shí)矩陣的簡(jiǎn)化

當(dāng)數(shù)據(jù)維數(shù)較大時(shí), 辨識(shí)矩陣中邏輯運(yùn)算的計(jì)算量較大, 需要對(duì)辨識(shí)矩陣進(jìn)行簡(jiǎn)化。

定義5[14](1) ?(x,y)∈U×U,M(x,y)≠??MS(x,y)≠?,且MS(x,y)?M(x,y);(2) ?(x,y)∈U×U,M(x,y)=??MS(x,y)=?。倘若滿足以上兩個(gè)條件時(shí)，矩陣MS稱為辨識(shí)矩陣M的簡(jiǎn)化辨識(shí)矩陣。

元素吸收[14]指若矩陣中一元素M(x′,y′)≠?, 滿足M(x,y)：?≠M(fèi)(x′,y′)?M(x,y)。 此矩陣中M(x,y)的值被M(x′,y′)代替。

矩陣吸收[14]：矩陣吸收運(yùn)算的規(guī)則是, 在滿足?≠M(fèi)(x′,y′)?M(x,y)的情況下, 對(duì)矩陣中所有可能的元素對(duì)都進(jìn)行吸收操作。 簡(jiǎn)化后的辨識(shí)矩陣得到的約簡(jiǎn)與原辨識(shí)矩陣得到的約簡(jiǎn)相同。

2 Pythagorean模糊信息系統(tǒng)的圖表示

對(duì)于一些維數(shù)較大的數(shù)據(jù)集來(lái)說(shuō),辨識(shí)矩陣的析取與合取的算法過程復(fù)雜度較大, 考慮將辨識(shí)矩陣的約簡(jiǎn)轉(zhuǎn)化為圖的最小頂點(diǎn)覆蓋來(lái)簡(jiǎn)化計(jì)算量。 首先定義Pythagorean模糊信息系統(tǒng)中基于加權(quán)歐幾里得距離的相似度和辨識(shí)矩陣。

2.1 Pythagorean模糊信息系統(tǒng)中的加權(quán)歐幾里得距離及相似關(guān)系

由于Pythagorean模糊信息系統(tǒng)是直覺模糊信息系統(tǒng)的推廣，因此將直覺模糊集的一些性質(zhì)推廣到Pythagorean模糊集中。 首先給出Pythagorean模糊信息系統(tǒng)中的相似關(guān)系并討論它的性質(zhì)。

性質(zhì)1設(shè)λ1=〈μ1,ν1〉,λ2=〈μ2,ν2〉,λ3=〈μ3,ν3〉為3個(gè)Pythagorean模糊數(shù), 則D(λi,λj)為一個(gè)度量, 其中i,j=1,2,3。 對(duì)于任意的Pythagorean模糊數(shù)λ1、λ2、λ3, 則(1)D(λ1,λ2)≥0, 且D(λ1,λ2)=0，當(dāng)且僅當(dāng)λ1=λ2;(2)D(λ1,λ2)=D(λ2,λ1); (3)D(λ1,λ2)≤D(λ1,λ3)+D(λ3,λ2)。

下面定義Pythagorean模糊信息系統(tǒng)中兩個(gè)對(duì)象的相似度。

定義7設(shè)S=(U,A,VPF,f)為Pythagorean模糊信息系統(tǒng), 若(xi,xj)∈U,ak∈A,f(xi,ak)=〈μak(xi),νak(xi)〉與f(xj,ak)=〈μak(xj),νak(xj)〉為兩個(gè)Pythagorean模糊數(shù),α、β、γ為加權(quán)因子。 關(guān)于ak的基于加權(quán)歐幾里得距離的相似度sim定義為

性質(zhì)2設(shè)S=(U,A,VPF,f)為Pythagorean模糊信息系統(tǒng), 對(duì)于任意xi,xj∈U,ak∈A, 關(guān)于ak的基于加權(quán)歐幾里得距離的相似度滿足性質(zhì)：(1) 0≤simak(xi,xj)≤1;(2)simak(xi,xj)=simak(xj,xi);(3)f(xi,ak)=f(xj,ak)?simak(xi,xj)=1;(4) 若f(xi,ak)=〈1,0〉,f(xj,ak)=〈0,1〉, 且α+β=1, 則simak(xi,xj)=0, 也就是說(shuō),xi和xj在性質(zhì)ak上的表現(xiàn)完全不同。

定義8設(shè)S=(U,A,VPF,f)為Pythagorean模糊信息系統(tǒng), 對(duì)于任意ak∈A,δ∈[0,1], 兩個(gè)對(duì)象的δ-相似關(guān)系定義為Rδ(A)={(xi,xj)∈U×U|simak(xi,xj)≥δ,?ak∈A}。

性質(zhì)3設(shè)S=(U,A,VPF,f)為Pythagorean模糊信息系統(tǒng),Rδ(A)為由屬性A決定的二元關(guān)系, 則以下性質(zhì)成立：(1) 對(duì)任意xi∈U,Rδ(A)(xi,xi)=1;(2) 對(duì)任意xi,xj∈U,Rδ(A)(xi,xj)=Rδ(A)(xj,xi)。 對(duì)任意的C?A,δ∈[0,1], 有Rδ(C)=∩ck∈CRδ(ck), 且Rδ(A)?Rδ(C)。

參數(shù)δ往往根據(jù)數(shù)據(jù)集的分布特征進(jìn)行取值, 不同的δ代表對(duì)象xi與xj之間不同的相似度和信息系統(tǒng)中不同的相似關(guān)系。 當(dāng)數(shù)據(jù)集的相似程度較大時(shí), 應(yīng)選擇更大的δ值, 反之亦然。

定義9若S=(U,A,VPF,f)為Pythagorean模糊信息系統(tǒng),δ∈[0,1],Rδ(A)為由屬性集A決定的二元關(guān)系,C?A, 稱C為屬性集A的約簡(jiǎn)(記為red(A)), 滿足條件：(1)Rδ(A)=Rδ(C); (2) 對(duì)任意元素c∈C,Rδ(A)≠Rδ(C-{c})。

2.2 基于相似關(guān)系的辨識(shí)矩陣

為了得到Pythagorean模糊信息系統(tǒng)的屬性約簡(jiǎn), 引入基于相似關(guān)系的辨識(shí)矩陣。

定義10設(shè)S=(U,A,VPF,f)為Pythagorean模糊信息系統(tǒng)。 記MS(x,y)={ak∈A:simak(x,y)<δ}為x與y的辨識(shí)屬性集, 其中(x,y)∈U×U, 稱矩陣MS=MS(x,y)為信息系統(tǒng)S的辨識(shí)矩陣。

表1 4個(gè)病人的信息表Table 1 An information table of four patients

根據(jù)兩對(duì)象相似度的定義可得sima1(x1,x2)=0.505 ,sima2(x1,x2)=0.714 ,sima3(x1,x2)=0.518 ,sima4(x1,x2)=0.916,M(x1,x2)={ak∈A:sim(x1,x2)<0.8}={a1,a2,a3}。 同理可計(jì)算M(x1,x3)={a3},M(x1,x4)=A,M(x2,x3)=A,M(x2,x4)={a1,a4},M(x3,x4)={a3,a4}。 進(jìn)而得到辨識(shí)矩陣MS為red(A)=(a1∨a2∨a3)∧(a1∨a2∨a3∨a4)∧a3∧(a1∨a4)∧(a3∨a4)=(a3∧a1)∨(a3∧a4), 即得到兩個(gè)約簡(jiǎn)集{a1,a3}和{a3,a4}。 任何一個(gè)約簡(jiǎn)集都含有的元素稱為核心元素, 記為core(A), 即core(A)=∩red(A)。 例1中core(A)={a3}。

定理1若S=(U,A,VPF,f)為一個(gè)Pythagorean模糊信息系統(tǒng),C?A,δ∈[0,1],MS為此信息系統(tǒng)的辨識(shí)矩陣, 則有core(A)={a∈A:M(x,y)={a}}。

即核心屬性為辨識(shí)矩陣中所有單個(gè)元素的集合。

2.3 辨識(shí)矩陣的圖表示方法

下面我們將辨識(shí)矩陣的約簡(jiǎn)與圖中最小頂點(diǎn)覆蓋聯(lián)系起來(lái)。

定義13設(shè)MS為Pythagorean模糊信息系統(tǒng)S=(U,A,VPF,f)的辨識(shí)矩陣, 令V=A,E={e∈MS:e≠?}, 稱GS=〈V,E〉為Pythagorean模糊信息系統(tǒng)S的生成圖。

圖1 由S生成的圖GSFigure 1 Graph GS induced from S

例2以例1中的簡(jiǎn)化后的辨識(shí)矩陣為例。生成圖中頂點(diǎn)集為V={a1,a3,a4}, 邊集E={e1,e2}, 如圖1所示,e1與a3關(guān)聯(lián),e2與a1和a4關(guān)聯(lián), 關(guān)聯(lián)矩陣用MG表示。

定理3設(shè)GS=〈V,E〉為由Pythagorean模糊信息系統(tǒng)S=(U,A,VPF,f)的辨識(shí)矩陣生成的圖,red(S)為Pythagorean模糊信息系統(tǒng)S的約簡(jiǎn),v(GS)為S產(chǎn)生的圖GS的最小頂點(diǎn)覆蓋, 則v(GS)=red(S)。

性質(zhì)4若S=(U,A,VPF,f)為Pythagorean模糊信息系統(tǒng),δ∈[0,1],Rδ(A)為由屬性集A決定的二元關(guān)系,MS為辨識(shí)矩陣, 若MS中元素MS(x,y)由A中的單個(gè)元素a組成, 那么在生成圖中,a為一個(gè)含有環(huán)的頂點(diǎn)。

2.4 基于相似度的屬性約簡(jiǎn)算法(算法1)

輸入：Pythagorean模糊信息系統(tǒng)S=(U,A,VPF,f),δ, 加權(quán)因子α,β,γ。

輸出：S的約簡(jiǎn)red(A)。

1. 根據(jù)相似關(guān)系的定義計(jì)算辨識(shí)矩陣MS并簡(jiǎn)化。 /*刪掉重復(fù)行, 滿行及零行*/

2. 找到所有含有環(huán)的頂點(diǎn), 這些頂點(diǎn)構(gòu)成的集合定義為red。

3. 對(duì)任意頂點(diǎn)v∈red, 刪除所有與頂點(diǎn)v關(guān)聯(lián)的邊。 /*刪除關(guān)聯(lián)矩陣MG中的某些行*/

4. WhileMG≠? do

5. 找度最大的頂點(diǎn)v0, 令red=red∪{v0}。

6. 刪除所有與頂點(diǎn)v0相關(guān)聯(lián)的邊。

7. End while

8. 對(duì)任意v∈red, 若與頂點(diǎn)v關(guān)聯(lián)的邊都被點(diǎn)集red-{v}覆蓋, 則刪除頂點(diǎn)v。

9. 返回red。

此算法在最壞情況下的時(shí)間復(fù)雜度為O(|U|(|U|-1)|A|+|U|(|U|-1)/2+2|A|+|U|),為多項(xiàng)式時(shí)間復(fù)雜度, 可記為O(|U|2|A|), 經(jīng)過簡(jiǎn)化矩陣之后, 矩陣運(yùn)算的維度降低, 使算法的效率更高。

2.5 實(shí)例分析

為了驗(yàn)證基于圖論的Pythagorean模糊信息系統(tǒng)的屬性約簡(jiǎn)算法的可行性和有效性, 在目前已有的Pythagorean模糊集數(shù)據(jù)上, 進(jìn)行排列組合得到較大規(guī)模數(shù)據(jù)集，如表2所示。 數(shù)據(jù)集中含有50個(gè)對(duì)象, 7個(gè)條件屬性和4個(gè)決策屬性。 data1、data2、data3分別由數(shù)據(jù)集中的前10、20、50個(gè)對(duì)象以及條件屬性構(gòu)成。 用不同的數(shù)據(jù)集, 不同的約簡(jiǎn)方法以及不同的參數(shù)得到的約簡(jiǎn)結(jié)果及約簡(jiǎn)時(shí)間見表3和表4。 表3中α、β、γ分別為0.4、0.4、0.2, 在表4中分別為0.5、0.4、0.1。 通過對(duì)比可見, 隨著參數(shù)δ的增大, 得到的約簡(jiǎn)基數(shù)變小。 本文的算法得到的約簡(jiǎn)包含在原始算法得到的約簡(jiǎn)中, 且在一定條件下等于原始算法的最小約簡(jiǎn), 原始算法可得到所有可能的約簡(jiǎn)結(jié)果， 但是圖論方法可以節(jié)省算法的時(shí)間。

表2 數(shù)據(jù)集Table 2 Data sets

表3 不同數(shù)據(jù)集的約簡(jiǎn)結(jié)果及約簡(jiǎn)時(shí)間對(duì)比Table 3 Comparison of reduction results and reduction time for different data sets

表4 不同數(shù)據(jù)集的約簡(jiǎn)結(jié)果及約簡(jiǎn)時(shí)間對(duì)比Table 4 Comparison of reduction results and reduction time for different data sets

在約簡(jiǎn)的過程中, 若出現(xiàn)度數(shù)相同的頂點(diǎn)(條件屬性), 總是優(yōu)先考慮角標(biāo)較小的點(diǎn), 在實(shí)際應(yīng)用中可根據(jù)決策者的偏好, 優(yōu)先選擇相對(duì)重要的屬性。

3 Pythagorean模糊決策信息系統(tǒng)約簡(jiǎn)的圖解法

3.1 Pythagorean模糊決策信息系統(tǒng)的辨識(shí)矩陣

定義14Pythagorean模糊決策信息系統(tǒng)是一個(gè)五元組F=(U,A,V,D,I),A為條件屬性集,D為決策屬性集,δ∈[0,1], 則Pythagorean模糊決策信息系統(tǒng)中的δ-相似關(guān)系Rδ(A|D)定義為

Rδ(A|D)={(xi,xj)∈U×U|?ak∈A,simak(xi,xj)≥δ∨ID(xi)=ID(xj)}。

定義15令F=(U,A,V,D,I)為Pythagorean模糊決策信息系統(tǒng),δ∈[0,1],C?A為屬性集A關(guān)于D的一個(gè)約簡(jiǎn), 滿足條件:(1)Rδ(C|D)=Rδ(A|D);(2)?C′?C,Rδ(C′|D)≠Rδ(A|D)。

定義16令F=(U,A,V,D,I)為Pythagorean模糊決策信息系統(tǒng), (x,y)∈U×U, 則稱

3.2 辨識(shí)矩陣的圖表示

定義17令F=(U,A,V,D,I)為Pythagorean模糊決策信息系統(tǒng),MF為辨識(shí)矩陣,GF=〈V,E〉稱為Pythagorean模糊決策信息系統(tǒng)的生成圖, 若V=A,E={e∈MF,e≠?}。

通過定理2中信息系統(tǒng)的約簡(jiǎn)與生成圖中頂點(diǎn)覆蓋的關(guān)系, 可以得到關(guān)于Pythagorean模糊決策信息系統(tǒng)的相關(guān)結(jié)論。

定理4若GF=〈V,E〉為Pythagorean模糊決策信息系統(tǒng)F=(U,A,V,D,I)的生成圖, 則有red(F)=v(GF)。

以上結(jié)果對(duì)于超圖依然成立。

例3表5為一個(gè)Pythagorean模糊決策信息系統(tǒng)F=(U,A,V,D,I), 其中：U={x1,x2,x3,x4}；A={a1,a2,a3,a4}；D=j5i0abt0b。 令δ=0.7,α=0.4,β=0.4,γ=0.2。

表5 Pythagorean模糊決策信息系統(tǒng)決策表Table 5 Decision table of pythagorean fuzzy decision information system

根據(jù)定義10, 利用辨識(shí)函數(shù)得到約簡(jiǎn){a1,a3}, {a1,a4}, {a3,a4}, {a2,a4}。 通過辨識(shí)矩陣可得生成圖GF=〈V,E〉, 關(guān)聯(lián)矩陣如表6所示。得到辨識(shí)矩陣MS為

表6 關(guān)聯(lián)矩陣MGTable 6 Incidence matrix MG

生成圖GF=〈V,E〉中,V={a1,a2,a3,a4},E={{a1,a2,a3},{a1,a4},{a3,a4}},顯然red(F)=v(GF)={{a1,a4},{a1,a3},{a2,a4},{a3,a4}}。

性質(zhì)5令F=(U,A,V,D,I)為Pythagorean模糊決策信息系統(tǒng), 稱SF(U,A,V)為由F生成的Pythagorean模糊信息系統(tǒng),MS為SF的辨識(shí)矩陣,MF為F的辨識(shí)矩陣, 對(duì)任意x,y∈U, 可得關(guān)系

根據(jù)定義10和16可證上式成立，由此可見, 對(duì)任意x,y∈U, 恒有MF(x,y)=MS(x,y)。

3.3 Pythagorean模糊決策信息系統(tǒng)的屬性約簡(jiǎn)算法(算法2)

輸入：Pythagorean模糊決策信息系統(tǒng)F=(U,A,V,D,I),δ, 加權(quán)因子α,β,γ。

輸出：F的約簡(jiǎn)red(A)。

1. 根據(jù)算法1, 找到Pythagorean模糊信息系統(tǒng)SF(U,A,V)生成圖的辨識(shí)矩陣MS。

2. ifID(x)=ID(y)

3.MF(x,y)=MS(x,y)

4. elseMF(x,y)=?

5. 產(chǎn)生圖的關(guān)聯(lián)矩陣MG。

6. 利用算法1中步驟3～9, 得到約簡(jiǎn)red(A)。

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

選取表2中的前10、20、50個(gè)數(shù)據(jù)以及對(duì)應(yīng)的條件和決策屬性作為data4、data5、data6。 算法的約簡(jiǎn)結(jié)果及運(yùn)行時(shí)間見表7(參數(shù)α、β、γ分別為0.4、0.4、0.2)和表8(參數(shù)α、β、γ分別為0.5、0.4、0.1)。 可見在約簡(jiǎn)結(jié)果相同的條件下，本文提出的算法大大減少了算法復(fù)雜度。

表7 不同數(shù)據(jù)集的約簡(jiǎn)結(jié)果及約簡(jiǎn)時(shí)間對(duì)比Table 7 Comparison of reduction results and reduction time for different data sets

表8 不同數(shù)據(jù)集的約簡(jiǎn)結(jié)果及約簡(jiǎn)時(shí)間對(duì)比Table 8 Comparison of reduction results and reduction time for different data sets

4 結(jié)論

本文主要討論了Pythagorean模糊信息系統(tǒng)和Pythagorean模糊決策信息系統(tǒng)中的屬性約簡(jiǎn)問題。 利用加權(quán)歐幾里得距離定義了對(duì)象之間的相似度, 然后利用信息系統(tǒng)中的約簡(jiǎn)與圖論中頂點(diǎn)覆蓋之間的關(guān)系, 將辨識(shí)矩陣轉(zhuǎn)化為圖論中的關(guān)聯(lián)矩陣, 將NP-Hard問題簡(jiǎn)化為多項(xiàng)式復(fù)雜度的問題, 減少了約簡(jiǎn)算法的時(shí)間復(fù)雜度, 給出了Pythagorean模糊信息系統(tǒng)和Pythagorean模糊決策信息系統(tǒng)中屬性約簡(jiǎn)的算法, 最后分別用實(shí)例驗(yàn)證了其可行性, 并進(jìn)行了對(duì)比分析。