基于優(yōu)勢關(guān)系的正協(xié)調(diào)模糊決策形式背景的規(guī)則融合

張曉鶴,陳德剛,米據(jù)生

(華北電力大學(xué) 1.控制與計算機工程學(xué)院;2.數(shù)理學(xué)院,北京 102200;河北師范大學(xué) 3.數(shù)學(xué)科學(xué)學(xué)院;4.河北省計算數(shù)學(xué)與應(yīng)用重點實驗室,河北 石家莊 050024)

知識表示的重要方式之一就是規(guī)則,通常包含兩部分內(nèi)容,即條件與結(jié)論。條件是結(jié)論產(chǎn)生的必要條件,所以規(guī)則能夠幫助完成對象分類、獲取決策等任務(wù)。規(guī)則挖掘的一個重要工具就是形式概念分析理論。形式概念分析[1]于1982年由Wille教授提出,Ganter等[2]在其專著中進一步總結(jié)了形式概念分析相關(guān)知識。形式概念分析理論將對象與屬性的內(nèi)在聯(lián)系用數(shù)學(xué)語言進行描述,進而獲取規(guī)則。該理論已在信息檢索[3-6]、故障診斷[7]、數(shù)據(jù)挖掘[8-9]、氣象分析[10]等領(lǐng)域得到了廣泛應(yīng)用。

概念格的節(jié)點之間可以進行相互推理,在此基礎(chǔ)上能夠?qū)崿F(xiàn)規(guī)則提取,它被認(rèn)為是概念內(nèi)涵之間的一種誘導(dǎo)關(guān)系[11-12]。在形式概念分析中,更為一般的規(guī)則通過蘊涵刻畫屬性之間的依賴關(guān)系。目前,已經(jīng)有諸多學(xué)者針對形式背景中決策規(guī)則獲取進行研究,形成了完整的理論體系[13]。Ishibuchi等[14]提出了一種從數(shù)值數(shù)據(jù)中生成模糊規(guī)則的算法,并利用產(chǎn)生的模糊規(guī)則進行模糊推理。於東軍等[15]利用SOM對原始樣本進行學(xué)習(xí),再使用Wang-Mendel方法從SOM的原型向量中提取規(guī)則。王麗娟等[16]將多粒度理論與不完備決策系統(tǒng)結(jié)合,提出多粒度近似分布約簡與規(guī)則獲取方法。Kuznetsov[17]通過分析屬性集之間的隱含關(guān)系提出了一種概念構(gòu)造算法從而生成所有可能的基于概念的分類規(guī)則,也稱假設(shè)。Wu等[18]將粒計算與概念格理論進行結(jié)合,提出了粒概念與粒決策規(guī)則。為了獲取更為簡便的決策規(guī)則,基于決策規(guī)則的約簡模型被陸續(xù)提出,Shao等[19]給出了在形式背景中“if-then”規(guī)則的獲取方法,并提出了保持最大規(guī)則不變的屬性約簡方法,且進一步在模糊形式背景中提出了一種基于可變閾值概念格的知識約簡方法[20]。Li等[21]提出了在保持由全體對象集構(gòu)造的決策規(guī)則不變的決策形式背景的約簡方法。Li等[22]提出了保持最大規(guī)則的決策形式背景中的兩種新型約簡方法。Yang等[23]基于蘊涵映射,研究了實數(shù)集決策形式背景中的屬性約簡與規(guī)則獲取。林藝東等[24]提出了基于矩陣的模糊-經(jīng)典概念格屬性約簡。Ren等進一步研究了三支概念格的屬性約簡[25]與規(guī)則提取[26]。Zhang等[27]在具有模糊決策的格值信息系統(tǒng)上給出了復(fù)雜系統(tǒng)中所有對象的排序方法并討論了近似約簡和規(guī)則獲取問題。張文修等[28]提出了協(xié)調(diào)近似表示空間的規(guī)則融合方法。為進一步提升規(guī)則提取效率,王志海等[29]利用增量式建格實現(xiàn)規(guī)則動態(tài)提取。謝志鵬等[30]借助概念格與內(nèi)涵縮減技術(shù)挖掘關(guān)聯(lián)規(guī)則。梁吉業(yè)等[31]給出閉項集概念,只提取核心規(guī)則,基于規(guī)則推理誘導(dǎo)形成剩余規(guī)則。

目前研究的決策形式背景中的決策規(guī)則大部分是基于條件概念外延與決策概念外延之間的包含關(guān)系給出,而這些決策規(guī)則不能夠解決條件屬性所有可能取值的決策問題。本文首先基于優(yōu)勢關(guān)系獲取決策類,然后基于確定性的粒決策規(guī)則獲取各個決策類對應(yīng)的條件屬性最小取值,給出規(guī)則融合方法,通過該方法可以獲取全部條件屬性取值對應(yīng)的決策規(guī)則。

1 預(yù)備知識

首先對形式背景中的相關(guān)知識進行簡單介紹。

定義4[28]設(shè)Vl(l≤m) 是非空有限集,記P={(u1,u2,…,um):ul?Vl(l≤m)},稱P為集合向量空間。對于P中的兩個集合向量E=(u1,u2,…,um),S=(v1,v2,…,vm),若l≤m,均有ul?vl,記E≤S,則(P,≤)為偏序集。且有

E∧S=(u1,u2,…,um)∧(v1,v2,…,vm)=

(u1∧v1,u2∧v2,…,um∧vm)

2 基于優(yōu)勢關(guān)系的模糊決策形式背景的協(xié)調(diào)性

本節(jié)給出模糊決策形式背景中3種不同協(xié)調(diào)性的定義,并對其關(guān)系進行討論。

從而獲得U上的一個覆蓋并按決策值排序有

U/RD={RD(x):x∈U}={D1,D2,…,Dr}

式中:RD(x)={y∈U:(x,y)∈RD}。

定理2正協(xié)調(diào)的模糊決策形式背景必為序協(xié)調(diào)的。

從定理1可知,正協(xié)調(diào)的模糊決策形式背景同樣也是粒協(xié)調(diào)的。

例1表1給出了一個模糊決策形式背景,其中對象集U={x1,x2,x3,x4,x5},D=j5i0abt0b為決策屬性集。A={a1,a2,a3}為條件屬性集。

表1 模糊決策形式背景

計算可知:

根據(jù)RD={(x,y)∈U×U:d(x)≤d(y)}可產(chǎn)生U上的覆蓋。

D1={x1,x2,x3,x4,x5},D2={x1,x2,x3,x4},D3={x2}。

而

f(x1)=(0.7,0.7,0.8)

f(x2)=(0.9,0.8,0.9)

f(x3)=(0.7,0.7,0.8)

f(x4)=(0.7,0.8,0.9)

f(x5)=(0.6,0.7,0.8)

f(x5)≤f(x1)=f(x3)≤f(x4)≤f(x2)

d(x5)≤d(x1)=d(x3)≤d(x4)≤d(x2)

則F1是一個正協(xié)調(diào)模糊決策形式背景。

僅有f(x1)=f(x3),此時d(x1)=d(x3),則F1是一個序協(xié)調(diào)模糊決策形式背景。

繼續(xù)計算可知

gf(x1)={x1,x2,x3,x4}?RD(x1)=D2

gf(x2)={x2}?RD(x2)=D3

gf(x3)={x1,x2,x3}?RD(x3)=D2

gf(x4)={x2,x4}?RD(x4)=D2

gf(x5)={x1,x2,x3,x4,x5}?RD(x5)=D1

所以F1是一個粒協(xié)調(diào)模糊決策形式背景。

3 基于優(yōu)勢關(guān)系的正協(xié)調(diào)模糊決策形式背景上的規(guī)則融合

本節(jié)給出正協(xié)調(diào)決策形式背景中粒決策規(guī)則獲取算法,進一步討論基于優(yōu)勢關(guān)系的正協(xié)調(diào)決策形式背景上規(guī)則融合算法,并給出相關(guān)實例。

3.1 粒決策規(guī)則獲取

算法1給出了具體算法。

算法1正協(xié)調(diào)模糊決策形式背景的粒決策規(guī)則獲取算法

2: 1≤l≤|D|

3: 如果dl(x)≤dl(y)

4:(x,y)∈RD

5:U/RD={RD(x):x∈U}={D1,D2,…,Dr}

6: 計算(Dt,Tt)

7: 對1≤k≤|U|

8: 計算(gf(xk),f(xk))?(RD(xk),Tt)

該算法最壞復(fù)雜度為O(|U|(|U||D|+|U|r+|A|r))。

3.2 規(guī)則融合

對于正協(xié)調(diào)模糊決策形式背景來說,對x∈U,必有g(shù)f(x)?RD(x)。于是可得到|U|條決策規(guī)則,這些決策規(guī)則都是確定性規(guī)則。但顯然決策形式背景中還存在其他不確定性規(guī)則,下面給出用|U|條確定性規(guī)則得到全部規(guī)則的規(guī)則融合方法。

U/RD={D1,D2,…,Dr}

(2)對于決策類Dj(j≤r),記

Mj={(f(xi)(a1),f(xi)(a2),…,

f(xi)(a|A|)):xi∈Dj}

S1≤S2≤…≤Sr

即決策類越大,對象的條件屬性隸屬度向量越大。用S1

S1

①若f(x)≥Sr,則d(x)=r。

②若f(x)≥Sj,且f(x)≯Sj+1時d(x)=j(1≤j≤r-1)。

③若f(x)≯S1時d(x)=0。

規(guī)則①表示當(dāng)對象的條件屬性隸屬度向量不小于Sr的時候,其決策值與Dr的決策值相同。規(guī)則②表示當(dāng)對象的條件屬性隸屬度向量處于Sj和Sj+1之間的時候,其決策值與Dj的決策值相同。規(guī)則③表示當(dāng)對象的條件屬性隸屬度向量不大于S1的時候,其決策值與D1的決策值相同,也可以根據(jù)具體情況進行調(diào)整,使d(x)=1,總表示最差的一類。用這些決策規(guī)則就能夠得到所有決策。

算法2給出了具體算法。

算法2正協(xié)調(diào)模糊決策形式背景的規(guī)則融合算法

輸出:決策規(guī)則;

2:如果dl(x)≤dl(y)

3:(x,y)∈RD

4:U/RD={RD(x):x∈U}={D1,D2,…,Dr}

5:計算(Dj,Tj)

6:對Dj(j≤r)

7:Mj={(f(xi)(a1),…,f(xi)(a|A|)):xi∈Dj}

∧(f(xi)(a2)),…,∧(f(xi)(a|A|)),xi∈Dj

10:如果f(x)≥Sr,則d(x)=r;

如果f(x)≥Sj,f(x)≯Sj+1則d(x)=j(1≤j≤r-1);

如果f(x)≯S1則d(x)=0。

該算法最壞復(fù)雜度為O(|U|2(|D|+|A|+r)+|U||A|r)。

表2 模糊決策形式背景

計算可知:U/RD={D1,D2,D3},其中D1={x1,x2,x3,x4,x5,x6,x7,x8,x9,x10},D2={x1,x2,x3,x4,x7,x9,x10},D3={x2,x7,x10}。則所有決策概念計算如下:

({x1,x2,x3,x4,x5,x6,x7,x8,x9,x10},{d=1})

({x1,x2,x3,x4,x7,x9,x10},{d=2})

({x2,x7,x10},{d=3})

可計算出所有的經(jīng)典-模糊對象概念,如表3所示。

表的經(jīng)典-模糊對象概念

從而可以獲取所有的粒決策規(guī)則如下:

根據(jù)算法2繼續(xù)計算

M1={(0.6,0.7,0.9,0.6),(0.6,0.7,0.6,0.6),

(0.7,0.7,0.6,0.6),(0.7,0.9,0.8,0.9),

(0.9,0.9,0.6,0.9)}

M2={(0.7,0.7,0.6,0.6),(0.7,0.9,0.8,0.9),

(0.9,0.9,0.6,0.9)}

M3={(0.9,0.9,0.6,0.9)}

故

S1=(0.6,0.7,0.6,0.6)

S2=(0.7,0.7,0.6,0.6)

S3=(0.9,0.9,0.6,0.9)

可知S1

①若f(x)≥S3,則d(x)=3;

②若f(x)≥S2,且f(x)≯S3時d(x)=2;

③若f(x)≥S1,且f(x)≯S2時d(x)=1;

④若f(x)≯S1,則d(x)=0。

根據(jù)以上方法可以得到全部的決策規(guī)則:

4 結(jié)束語

規(guī)則提取是決策形式背景中的重要問題,其目的是為了獲取最優(yōu)決策。本文在模糊決策形式背景中僅條件屬性部分構(gòu)造概念格模型,在決策部分基于優(yōu)勢關(guān)系獲取關(guān)于對象集的覆蓋,從而確定決策類,能夠縮短計算時間。針對這一模型提出了基于優(yōu)勢關(guān)系的模糊決策形式背景的粒協(xié)調(diào)、序協(xié)調(diào)及正協(xié)調(diào)的定義,并對其關(guān)系進行討論。

本文在基于優(yōu)勢關(guān)系的正協(xié)調(diào)模糊決策形式背景中基于確定性的粒決策規(guī)則給出規(guī)則融合方法,獲取了正協(xié)調(diào)模糊決策形式背景的全部規(guī)則,其中不僅包括粒決策規(guī)則這樣的確定性規(guī)則,也包括不確定性規(guī)則,甚至可以給出和原形式背景中對象取值不同的對象的決策規(guī)則。目前本文只針對正協(xié)調(diào)模糊決策形式背景的決策規(guī)則融合進行談?wù)?在實際問題中,有很多數(shù)據(jù)是不符合這一協(xié)調(diào)性的,因此,在今后的工作中將進一步探討不協(xié)調(diào)的模糊決策形式背景上的規(guī)則融合問題。