楊 勇,宋娟萍
(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,甘肅 蘭州730070)
為解決現(xiàn)實(shí)中遇到的不確定問題,相繼產(chǎn)生了一系列的數(shù)學(xué)理論和工具,比如粗糙集理論[1]、概率論、模糊集理論[2]等。但是,以上理論都存在其不完善的方面,主要不足之處是參數(shù)化工具的不完備。Molodstov D[3]于1999 年 提 出 了 軟 集(Soft Set),成功解決了其它方法不能解決的參數(shù)化不足問題。軟集參數(shù)的無約束性,使其解決不確定性問題的應(yīng)用更廣,也簡化了決策過程。隨后Maji P K 等學(xué)者[4]對軟集理論作了進(jìn)一步研究并給出了軟集在決策問題中的應(yīng)用[5]。近年來,軟集的理論研究已經(jīng)在很多領(lǐng)域取得了豐碩的成果[6~10],與此同時(shí),軟集在許多實(shí)際問題尤其是決策問題中得到了廣泛的應(yīng)用[11~14]。在文獻(xiàn)[15]中作者定義了軟矩陣,提出了軟矩陣算子以及解決決策問題的新方法。Feng Q 等[16]研究軟集和信息系統(tǒng)之間的關(guān)系提出了軟區(qū)分矩陣,并將其成功地用于決策問題,提出了全新的決策算法。
現(xiàn)實(shí)世界中會(huì)因數(shù)據(jù)測量的誤差、對數(shù)據(jù)理解或獲取的限制等因素,導(dǎo)致得到的信息系統(tǒng)往往是不完備的,基于此原因,本文結(jié)合不完備信息系統(tǒng)、軟集以及區(qū)分矩陣,提出了不完備軟區(qū)分矩陣,同時(shí)討論其相關(guān)性質(zhì)和運(yùn)算。本文是對文獻(xiàn)[16]的進(jìn)一步學(xué)習(xí)和補(bǔ)充,部分地解決了不完備信息系統(tǒng)中的決策問題。最后,通過實(shí)例來驗(yàn)證新方法在解決決策不完備問題中的有效性。
定義1[17](信息系統(tǒng)) 四元組(U,A,V,f)稱為信息系統(tǒng),或者是信息表。其中U為非空有限對象集合,稱為論域;A為非空有限屬性集合;V=∪Vj,其中Vj表示屬性aj的值域;f:U×A→V是一個(gè)信息函數(shù),指明每個(gè)對象的屬性值。
在一個(gè)信息系統(tǒng)中,若存在xi∈U,aj∈A,使得f(xi,aj)=* ,這里的“*”表示未知值,則稱該系統(tǒng)為不完備信息系統(tǒng)。如表1所示的信息系統(tǒng)就是一個(gè)不完備信息系統(tǒng)。

Table 1 An incomplete information systemS=(U,A,V,f)表1 不完備信息系統(tǒng)S=(U,A,V,f)
定義2[17](劃分) 設(shè)R是U上的等價(jià)關(guān)系,由不可區(qū)分關(guān)系R決定的U上的一個(gè)劃分定義如下:A=U|R={[xi]R:xi∈U},其中[xi]R={xj:(xi,xj)∈R}為包含元素xi的一個(gè)等價(jià)類。
定義3[3](軟集) 設(shè)U為初始論域,E為參數(shù)集,P(U)為U上的冪集,A?E,F(xiàn):A→P(U),稱(F,A)為U上的軟集。
換句話說,一個(gè)U上的軟集就是U上的一些子集構(gòu)成的參數(shù)族。對于任意的參數(shù)e∈A,F(xiàn)(e)可看作軟集(F,A)的e-元素的集合或者是軟集e-近似元素的集合。
定義4[18](不完備軟集) 設(shè)U為初始論域,E為參數(shù)集,A?E,F(xiàn):A→ {0 ,1/2,1 }U,則稱(F,A)為U上的不完備軟集。
注:本定義中1/2 表示不完備軟集中的未知值,即“*”。
性質(zhì)1[19]任何軟集都是一個(gè)信息系統(tǒng)。
定義5[6](軟 二 元 關(guān) 系) 如 果F:A→P(U×U)是參數(shù)集A到冪集U×U上的映射,則U×U上的軟集(F,A)稱為U上的一個(gè)軟二元關(guān)系。
定義6[11](軟等價(jià)關(guān)系) 設(shè)(F,A)是U上的軟二元關(guān)系,如果對任意的e∈A,有F(e)≠?且是U上的一個(gè)等價(jià)關(guān)系,則稱(F,A)為U上的一個(gè)軟等價(jià)關(guān)系。
定義7[11](等價(jià)類) 設(shè)(F,A)是U上的一個(gè)軟等價(jià)關(guān)系,則等價(jià)關(guān)系F(e)中包含元素x的等價(jià)類定義為:[x]F(e)={y:(x,y)∈F(e),y∈U}。
由上可知,軟集(F,A)可確定一個(gè)不可區(qū)分關(guān)系,這個(gè)不可區(qū)分關(guān)系就是由參數(shù)決定的所有等價(jià)關(guān)系的交,即IND(F,A)=∩ei∈AF(ei)。
設(shè) (F,A)是U上 的 軟 集,其 中U={h1,h2,…,hm},則 由 不 可 區(qū) 分 關(guān) 系IND(F,A)決 定 的U上 的 劃 分 為:U|IND(F,A)={c1,c2,…,ck}(k≤m),其 中ci=[hj]IND(F,A),hj∈U。
文獻(xiàn)[11]提出了決策參數(shù)的概念,決策參數(shù)D=∑hij中的hij為第i個(gè)對象hi關(guān)于第j個(gè)參數(shù)ej的值。在軟集中條件參數(shù)和決策參數(shù)之間存在著很明確的關(guān)系,若使用粗糙集理論的屬性約簡方法可能會(huì)改變軟集中最優(yōu)對象的選擇。因此,本文不對屬性進(jìn)行約簡,通過建立區(qū)分矩陣來選擇最優(yōu)對象。為此介紹軟集一致決策表的相關(guān)基本概念,這些概念和粗糙集的相關(guān)概念類似。
定義8[5](軟集的選擇值) 設(shè)(F,A)是U上的軟集,則對象hi∈U的選擇值di=∑jhij,其中hij為軟集表中的元素。
決策參數(shù)值和每一個(gè)對象的選擇值是相等的,下文中兩者將不再區(qū)分。
定義9[16](一致決策表) 設(shè)(F,A)是U上的軟集,A?E,T=(U,A=C,D)是軟集確定的決策表。當(dāng)C?D,即IND(C)?IND(D),T稱為軟集的一致決策表,其中C是條件參數(shù)集,D是決策參數(shù)集。
定義10[11](決策表中的不必要參數(shù)集) 設(shè)T=(U,A,C,D)是一致決策表,Tγ=(U,A,Cγ,Dγ)是在條件屬性C中刪除屬性γ得到的決策表,其中Dγ表示刪除γ后的決策參數(shù)集,且滿足以下條件時(shí)稱γ在T中是不必要的:
(1)Tγ是一致的,即C-γ?Dγ;
(2)IND(D)=IND(Dγ)。
否則,稱γ是決策表的必要參數(shù)或核參數(shù)。
由以上定義可知,在不完備軟集中當(dāng)且僅當(dāng)C?D,即IND(C)?IND(D)時(shí),決策表是一致的,所以我們可得到以下性質(zhì)。
性質(zhì)2U上的任何一個(gè)不完備軟集都是一致的。
證明由粗糙集理論可知,對U上的一個(gè)等價(jià)關(guān)系R,有對任意的(xi,xj)∈R時(shí),f(xi)=f(xj)。由文獻(xiàn)[11]可知,(F,A)為U上的軟等價(jià)關(guān)系,在該關(guān)系中對任意的e∈A,F(xiàn)(e)是一個(gè)等價(jià)關(guān)系,因此,∩F(e)也是一個(gè)等價(jià)關(guān)系,它可以決定一個(gè)劃分。在不完備軟集(F,A)中決策參數(shù)D=∑hij是由條件參數(shù)計(jì)算得到的,由條件參數(shù)決定的在同一個(gè)等價(jià)類中的對象必屬于由決策參數(shù)決定的一個(gè)等價(jià)類中,所以IND(C)?IND(D),即C?D。因此,U上的任何一個(gè)不完備軟集都是一致的。
性質(zhì)3設(shè)(F,A)是U上的不完備軟集,則IND(D)=IND(Dγ)的必要條件是IND(Cγ)=IND(C),其中Dγ表示從條件參數(shù)C中刪除屬性γ后的決策參數(shù)。
區(qū)分矩陣最初是由Skowron A 和Rauszer C在文獻(xiàn)[20]中提出的,主要用于屬性約簡。本文利用不完備軟集確定的區(qū)分矩陣來解決決策問題。下面將介紹不完備軟集上的區(qū)分矩陣,即不完備軟區(qū)分矩陣。
為了方便解決不完備信息系統(tǒng)下的決策問題,給出了以下定義。
定義11設(shè)U是論域,E是參數(shù)集,S=(F,A)是U上的不完備軟集,A?E,則F是U×A到V上 的 函 數(shù),即F:U×A→V。因 此,F(xiàn)(hi,el)∈V,其中,hi∈U(i=1,2,…,|U|),el∈A(l=1,2,…,|A|),V= {0 ,1,1/2} 。當(dāng)F(hi,el)未知時(shí),F(xiàn)(hi,el)=1/2。
定義12(基于對象的區(qū)分矩陣) 設(shè)S=(F,A)是U上的不完備軟集,A?E,稱為(F,A)上 的 基 于 對 象 的區(qū) 分 矩 陣,其 中D(hi,hj)= {el∈A:F(hi,el)≠F(hj,el),hi,hj∈U}為元素hi和hj的不完備軟區(qū)分參數(shù)集,F(xiàn)(hi,el)和F(hj,el)是對象hi和hj關(guān)于參數(shù)el的值。
綜上可知,在同一個(gè)劃分類中的對象將位于同一個(gè)決策類中,即它們有相同的決策值。因此,我們可以通過定義不完備軟集(F,A)上條件參數(shù)劃分類的區(qū)分矩陣來縮小不完備軟集(F,A)上區(qū)分矩陣的規(guī)模。
定義13(基于劃分類的區(qū)分矩陣) 設(shè)S=(F,A)是U上的不完備軟集,A?E。S決定的劃分 為U|IND(F,A)={Ci:i≤|U|}。稱為(F,A)上的基于劃分類的區(qū) 分 矩 陣,其 中D(Ci,Cj)={el∈A:F(hi,el)≠)F(hj,el),?hi∈Ci,hj∈Cj}為Ci和Cj的不完備軟區(qū)分參數(shù)集,F(xiàn)(hi,el)和F(hj,el)是Ci中的對象hi和Cj中的對象hj關(guān)于參數(shù)el的值。
在下文中選用基于劃分類的區(qū)分矩陣。接下來將給出例子來說明不完備軟區(qū)分矩陣的相關(guān)概念。
例1[21]設(shè)U上的不完備軟集(F,E)如表2所示,其中U={h1,h2,h3,h4,h5,h6},條 件參數(shù)集E={e1,e2,e3,e4,e5,e6,e7},最后一列增 加 了決策參數(shù)D=∑hij,根據(jù)定義13來構(gòu)造區(qū)分矩陣。
F(e1)的 等 價(jià) 類 為:{h1,h4,h5},{h2,h6},{h3};
F(e2)的 等 價(jià) 類 為:{h6},{h1,h2,h4,h5},{h3};
F(e3)的等 價(jià) 類 為:{h1,h2,h6},{h3},{h4,h5};
F(e4)的等 價(jià) 類 為:{h2},{h3,h4,h5},{h1,h6};
F(e5)的 等 價(jià) 類 為:{h1},{h3,h4,h5,h6},{h2};
F(e6)的等 價(jià) 類 為:{h2,h6},{h4,h5},{h1,h3};
F(e7)的等價(jià)類為:{h2,h3},{h1,h4,h5,h6}。

Table 2 Incomplete soft set in example 1表2 例1中的不完備軟集

Table 3 Discernibility matrix of Table 2表3 表2的區(qū)分矩陣
因?yàn)閰^(qū)分矩陣是對稱的,所以我們只需表示出矩陣的一半元素,在本文中我們采用下三角的形式來表示區(qū)分矩陣。
軟集經(jīng)常被用來解決決策問題,從上面的定義中可知一個(gè)不完備軟集就是一個(gè)不完備信息系統(tǒng),而區(qū)分矩陣的定義形式也類似于信息系統(tǒng),因此可以利用區(qū)分矩陣來解決不完備軟集中的決策問題。
僅依據(jù)表3我們還是很難得到?jīng)Q策問題的答案。但是,由表3可知,決策值最大的對象將被選為最優(yōu)對象,決策值的大小是由值為1和1/2的那些條件參數(shù)決定的,從而最優(yōu)對象的條件參數(shù)的值為1和1/2的數(shù)量多于其它對象。由此可見,可以通過統(tǒng)計(jì)對象的參數(shù)值為1和1/2的那些參數(shù)的個(gè)數(shù)來確定最優(yōu)對象。下面將給出不完備軟區(qū)分矩陣的定義以及解決決策問題的算法。
定義14(不完備軟區(qū)分矩陣) 設(shè)(F,A)是U上的不完備軟集,A?E。(F,A)決定的劃分U|IND(F,A)={Ci:i≤|U|}。不完備軟區(qū)分矩陣 定 義 為:其 中i,j≤U}稱為Ci與Cj的不完備軟區(qū)分參數(shù)集,其中:


從以上定義我們可知Ei是在Ci中值為1且在Cj中值不為1的那些參數(shù)的集合,是在Ci中值為1/2且在Cj中值不為1/2的那些參數(shù)的集合;Ej是在Cj中值為1且在Ci中值不為1的那些參數(shù)的集合,是在Cj中值為1/2且在Ci中值不 為 1/2 的 那 些 參 數(shù) 的 集 合。 根 據(jù) 在D(Ci,Cj)中|Ei|、|Ej|、可以得到Ci和Cj的序關(guān)系。
根據(jù)定義14,通過再次分析Kong Z 在文獻(xiàn)[21]中的例1,得到例1的軟區(qū)分矩陣如表4所示。
根據(jù)例1,不可區(qū)分關(guān)系IND(F,E)將U劃分為五類:C1={h1};C2={h2};C3={h3};C4={h4,h5};C5={h6}。
我們只給出D(C2,C1)的計(jì)算,其它不完備軟區(qū)分矩陣參數(shù)的計(jì)算方式相同。在C1中只有一個(gè)對象h1,C2中只有一個(gè)對象h2。從表3中可知D(C2,C1)= {e1,e4,e5,e6,e7},從 表2 可 知F(h1,e1)=1且F(h2,e1)=0,F(xiàn)(h1,e5)=1且F(h2,e5)=1/2,因此F(h1,e4)=1/2 且F(h2,e4)= 1,F(xiàn)(h1,e6)= 1/2 且F(h2,e6)=1,所 以又F(h2,e4)=1且F(h1,e4)=1/2,F(xiàn)(h2,e5)=1/2且F(h1,e5)=1,F(xiàn)(h2,e6)=1 且F(h1,e6)=1/2,F(xiàn)(h2,e7)=1且F(h1,e7)=0,故所以,D(C2,C1)=E1∪根據(jù)定義14得到的不完備軟區(qū)分矩陣如表4所示。
注:對于C4,其中的對象h4和h5的決策值是相等的,因此可以選擇其中的任意一個(gè)元素和其它類進(jìn)行比較。

Table 4 Incomplete soft discernibility matrix of Table 2表4 表2的不完備軟區(qū)分矩陣
性質(zhì)4設(shè)(F,A)是U上的不完備軟集,其中U={h1,h2,…,hm},則(F,A)上的不完備軟區(qū)分矩陣有如下性質(zhì):
(1)D(Ci,Ci)=? (?i≤m);
(2)D(Ci,Cj)=(Cj,Ci)(?i,j≤m)。
性質(zhì)5設(shè)(F,A)是U上的不完備軟集,其中U={h1,h2,…,hm}。設(shè)d(Ci,Cj)=|D(Ci,Cj)|,其 中D(Ci,Cj)表 示 集 合D(Ci,Cj)的基數(shù)。則d(Ci,Cj)有如下性質(zhì):
(1)d(Ci,Ci)=0( ?i≤m);
(2)d(Ci,Cj)=d(Cj,Ci)(?i,j≤m)。
由 定 義14 和 性 質(zhì)5 可 知:d(Ci,Cj)=當(dāng)時(shí),為了更好地解決決策問題,令因此,在做決策時(shí)只需要計(jì)算和便可得到Ci和Cj的序關(guān)系,因此得到如下性質(zhì):
性質(zhì)6在不完備軟區(qū)分矩陣中,如果表示Ci與Cj在相同的決策類中;如果,則表示Ci與Cj之間有一個(gè)序關(guān)系,即Ci優(yōu)于Cj或Cj優(yōu)于Ci。
性質(zhì)7在不完備軟區(qū)分矩陣中,如果則有以下兩種情況:
算法基于不完備軟區(qū)分矩陣的決策
輸入:U上的不完備軟集S=(F,A),其中U={h1,h2,…,hm}。
輸出:所有對象的序關(guān)系。
步驟1計(jì)算U的劃分以及不完備軟區(qū)分矩陣=(D(Ci,Cj) )i.j≤U。

步驟3根據(jù)性質(zhì)7給出Ci和Cj的序關(guān)系。
步驟4根據(jù)步驟3輸出所有對象的序關(guān)系。
接下來將繼續(xù)使用例1來闡述上文給出的算法。
例2不完備軟集如表2所示,利用算法1給出所有對象的序關(guān)系。
步驟1從表2 我們得到U的劃分為:{{h1},{h2},{h3},{h4,h5},{h6}},這 五 個(gè) 類 分別標(biāo)記如下:C1={h1};C2={h2},C3={h3},C4={h4,h5}和C5={h6}。不完備軟區(qū)分矩陣如表4所示。

同理,









步驟3根據(jù)性質(zhì)7 以及步驟2 步可得:有知C2優(yōu)于C1,即h2>h1。同理:C1優(yōu)于C6,即h1>h6;C3優(yōu)于C4,即h3>{h4,h5};C5優(yōu)于C3,即h6>h3。其它一樣,這里將不再一一列出。
步驟4根據(jù)步驟3 得到對象的序關(guān)系為:h2>h1>h6>h3>{h4,h5}。因此,最優(yōu)對象為h2。
實(shí)際應(yīng)用中,有時(shí)候我們不僅需要得到最優(yōu)對象而且需要次優(yōu)對象,該方法可以獲得所有對象的序關(guān)系,在實(shí)際中將會(huì)有更廣泛的應(yīng)用價(jià)值。且該方法使用區(qū)分矩陣來解決不完備信息的決策問題,后期可以使用該方法來研究不完備信息系統(tǒng)下的屬性約等問題。接下來通過另一個(gè)例子來說明該方法的有效性。
例3設(shè)(F,E)是U上的不完備軟集,其中U={h1,h2,h3,h4,h5,h6,h7,h8},條件參數(shù)集E={e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12,e13,e14,e15},不完備軟集F,(E) 如表5所示。利用算法1給出所有對象的序關(guān)系。
觀察表5發(fā)現(xiàn),e3、e13和e15的值全是0和1,所以這三個(gè)參數(shù)不會(huì)出現(xiàn)在任何集合的區(qū)分矩陣中,因此刪除這三個(gè)參數(shù)對最后的決策沒有任何影響,即這三個(gè)參數(shù)是不必要的,并且在建立的不完備軟區(qū)分矩陣表6中也沒有出現(xiàn)。故該方法不僅可以用于解決決策問題,還可以用于屬性約簡,這將在后期加以研究。

Table 5 Incomplete soft set in example 3表5 例3的不完備軟集

Table 6 Incomplete soft discernibility matrix of example 3表6 例3的不完備軟區(qū)分矩陣
基于已提出的軟區(qū)分矩陣在決策問題中的應(yīng)用,本文首先提出了不完備軟區(qū)分矩陣概念及其相關(guān)性質(zhì),并給出了不完備軟區(qū)分矩陣的決策算法。最后通過實(shí)例表明,該算法僅需一次掃描不完備軟區(qū)分矩陣,便可得到所有對象的序關(guān)系,不僅可選擇出最優(yōu)對象也可得到次優(yōu)對象。在此基礎(chǔ)上,今后我們將通過實(shí)踐,進(jìn)一步研究不完備軟集在決策問題中的應(yīng)用以及將不完備軟區(qū)分矩陣用于屬性約簡。
[1] Pawlak Z.Rough sets[J].International Journal of Computer&Information Sciences,1982,11(5):341-356.
[2] Zadeh L A.Fuzzy sets[J].Information and Control,1965,8(3):338-353.
[3] Molodtsov D.Soft set theory-first results[J].Computers &Mathematics with Applications,1999,37(4):19-31.
[4] Maji P K,Biswas R,Roy A R.Soft set theory[J].Computers& Mathematics with Applications,2003,45(4):555-562.
[5] Maji P K,Roy A R,Biswas R.An application of soft sets in a decision making problem[J].Computers & Mathematics with Applications,2002,44(8):1077-1083.
[6] Ali M I.A note on soft sets,rough sets and fuzzy soft sets[J].Applied Soft Computing,2011,11(4):3329-3332.
[7] Ali M I,F(xiàn)eng F,Liu X Y,et al.On some new operations in soft set theory[J].Computers & Mathematics with Applications,2009,57(9):1547-1553.
[8] Babitha K V,Sunil J J.Soft set relations and functions[J].Computers & Mathematics with Applications,2010,60(7):1840-1849.
[9] Molodtsov D.The theory of soft sets[M].Moscow:URSS Publishers,2004.
[10] Pei D,Miao D.From soft sets to information systems[C]∥Proc of GrC,2005:617-621.
[11] Ali M I.Another view on reduction of parameters in soft sets[J].Applied Soft Computing,2012,12(6):1814-1821.
[12] ?agman N,Enginoglu S.Soft set theory and uni-int decision making[J].European Journal of Operational Research,2010,207(2):848-855.
[13] Chen D,Tsang E C C,Yeung D S,et al.The parameterization reduction of soft sets and its applications[J].Computers & Mathematics with Applications,2005,49(5):757-763.
[14] Geng Sheng-ling,Li Yong-ming,Liu Zhen.Incomplete soft sets and dominance credible reles mining[J].Computer Engineering &Scinece,2013,35(12):153-160.(in Chinese)
[15] ?agman N,Enginoglu S.Soft matrix theory and its decision making[J].Computers & Mathematics with Applications,2010,59(10):3308-3314.
[16] Feng Q,Zhou Y.Soft discernibility matrix and its applications in decision making[J].Applied Soft Computing,2014,24:749-756.
[17] Pawlak Z.Information systems theoretical foundations[J].Information Systems,1981,6(3):205-218.
[18] Han B H,Li Y M,Liu J,et al.Elicitation criterions for restricted intersection of two incomplete soft sets[J].Knowledge-Based Systems,2014,59:121-131.
[19] Zou Y,Xiao Z.Data analysis approaches of soft sets under incomplete information[J].Knowledge-Based Systems,2008,21(8):941-945.
[20] Skowron A,Rauszer C.The discernibility matrices and functions in information systems[M]∥Intelligent Decision Support,Netherlands:Springer Netherlands,1992:331-362.
[21] Kong Z,Gao L,Wang L,et al.The normal parameter reduction of soft sets and its algorithm[J].Computers & Mathematics with Applications,2008,56(12):3029-3037.
附中文參考文獻(xiàn):
[14] 耿生玲,李永明,劉震.不完備決策軟集與優(yōu)勢可信規(guī)則獲取[J].計(jì)算機(jī)工程與科學(xué),2013,35(12):153-160.