直覺模糊偏好度量序決策表的近似約簡(jiǎn)

張曉燕，劉崢，侯江龍

西南大學(xué) 人工智能學(xué)院， 重慶 400715

粗糙集理論[1-2]最早由波蘭科學(xué)院院士Pawlak于1982年提出， 該理論是研究不確定性問題的重要工具， 且已經(jīng)被廣泛應(yīng)用于數(shù)據(jù)挖掘、 信息處理、 模式識(shí)別等領(lǐng)域． 該理論的主要思想是用確定的信息和可能的信息來近似不確定的信息． 在現(xiàn)實(shí)生活中， 研究人員從樣本的二元關(guān)系出發(fā)結(jié)合粗糙集理論， 將研究樣本區(qū)分開， 從而完成不同任務(wù)的分類問題． 而屬性約簡(jiǎn)是粗糙集理論的重要研究?jī)?nèi)容， 其目的就是在不削弱知識(shí)庫分類能力的前提下， 刪減掉冗余的屬性． 屬性約簡(jiǎn)正是利用了二元關(guān)系下形成的樣本類在特定的任務(wù)下形成特有的不可區(qū)分關(guān)系， 并建立不可區(qū)分矩陣或?qū)傩灾匾龋?以對(duì)必要和重要屬性進(jìn)行提?。?在當(dāng)今大數(shù)據(jù)時(shí)代， 通過屬性約簡(jiǎn)[3-10]可以精簡(jiǎn)知識(shí)， 從而減少運(yùn)算量， 特別是在聚類分析、 分類學(xué)習(xí)， 以及不確定性分析等領(lǐng)域展現(xiàn)出了良好的效果． 在屬性約簡(jiǎn)的研究中， 選用不同的關(guān)系模型會(huì)對(duì)約簡(jiǎn)結(jié)果產(chǎn)生不同程度的影響， 因此模型的優(yōu)劣也對(duì)屬性約簡(jiǎn)的效果具有舉足輕重的作用．

另一方面， 模糊集理論[11-13]是由美國(guó)學(xué)者Zadehl于1965年提出的， 該理論將經(jīng)典集合進(jìn)行了擴(kuò)充、 推廣， 引入了元素的隸屬度這一概念， 從而能夠?qū)ι钪械牟淮_定性問題進(jìn)行量化、 建模和研究． 模糊集是研究不確定性問題的一個(gè)重要工具， 該理論的主要思想重點(diǎn)考慮樣本并不是非黑即白的情況， 生活的很多環(huán)境中， 元素對(duì)于集合的關(guān)系并不是單純的屬于或不屬于的關(guān)系， 而是一種模糊概念或狀態(tài)， 如高個(gè)子、 紅蘋果、 下大雨等． 模糊集理論便可以利用一個(gè)介于0到1之間的隸屬度來表示和刻畫這些模糊語言或情況． 后來， 保加利亞學(xué)者Atanassov于1986年提出了直覺模糊集[14-16]， 是對(duì)模糊集的進(jìn)一步延伸， 該理論在經(jīng)典模糊集隸屬度的基礎(chǔ)上進(jìn)一步考慮了元素的非隸屬度和猶豫度， 從而能夠更好地貼合實(shí)際， 模擬現(xiàn)實(shí)中更加復(fù)雜的問題．

另外， 在現(xiàn)實(shí)生活中， 很多的不確定性問題是基于序關(guān)系[17-22]的， 即對(duì)象之間存在優(yōu)劣之分， 并且其對(duì)象的屬性值往往是直覺模糊數(shù)． 為了更好地研究此類問題， 本文引入了直覺模糊偏好度量序決策表， 在序決策表的基礎(chǔ)上引入了隸屬度、 非隸屬度和猶豫度， 并對(duì)其加權(quán)得到得分函數(shù)， 進(jìn)一步根據(jù)得分函數(shù)研究了在直覺模糊偏好度量序決策表的基礎(chǔ)上如何進(jìn)行近似約簡(jiǎn)， 從而進(jìn)一步拓展知識(shí)約簡(jiǎn)的應(yīng)用范圍．

1 直覺模糊偏好度量序決策表

決策表作為一種特殊的信息系統(tǒng)， 同時(shí)具有條件屬性和決策屬性， 下面給出決策表的相關(guān)概念．

令DT=(U，C∪D，F(xiàn)，G)為一個(gè)五元組， 稱I為決策表． 其中U為非空有限對(duì)象集，U={x1，x2， …，xn}；C為有限條件屬性集；D為有限決策屬性集，D={d1，d2， …，dq}；F是U與C的關(guān)系集，F(xiàn)={fi：U→Vi，i≤n}，Vi為ai的有限值域；G是U與D的關(guān)系集，G={gi：U→V′j，j≤q}，V′j為dj的有限值域．

在決策表的基礎(chǔ)上， 進(jìn)一步有直覺模糊決策表．

給定I=(U，C∪j5i0abt0b，F(xiàn)，G)為決策表， 對(duì)任意f∈F，g∈G，a∈C和x∈U有：f(x，a)=(μa(x)，νa(x))，g(x，d)∈R(R為實(shí)數(shù)集)， 其中μa(x)和νa(x)分別為x(x∈U)在條件屬性a下的隸屬度和非隸屬度，μa：U→[0， 1]，νa：U→[0， 1]且滿足0≤μa(x)+νa(x)≤1． 若記f(a)={f(x，a)|a∈AT}， 稱f(a)為U上的直覺模糊集， 并稱(U，C∪j5i0abt0b，F(xiàn)，G)為直覺模糊決策表， 記作DT*．

下面給出“偏好度量”的概念， 由此便可擴(kuò)充為直覺模糊偏好度量序決策表．

若DT*=(U，C∪j5i0abt0b，F(xiàn)，G)為直覺模糊決策表，x∈U，a∈C， 定義對(duì)象x對(duì)屬性a的得分函數(shù)為Sa(x)=αμa(x)-βνa(x)-γπa(x)， 其中μa(x)、 和νa(x)分別為對(duì)象x在條件屬性a下的隸屬度和非隸屬度， 而πa(x)表示對(duì)象x在條件屬性a下的猶豫度， 且πa(x)=1-μa(x)-νa(x)， 權(quán)重α，β，γ的值域?yàn)閇0， 1]， 且滿足α+β+γ=1． 這里α，β，γ取值都是根據(jù)具體的任務(wù)需求給定，α為隸屬度的權(quán)重， 越看重隸屬度， 則α的值越大；β為隸屬度的權(quán)重， 越看重非隸屬度， 則β的值越大；γ為隸屬度的權(quán)重，γ的值則可根據(jù)α，β的值來確定．

設(shè)DT*=(U，C∪j5i0abt0b，F(xiàn)，G)為直覺模糊決策表， 對(duì)任意的a∈C，f∈F，g∈G，xi，xj∈U有：

f(xi，a)≥f(xj，a)?Sa(xi)≥Sa(xj)

f(xi，a)≤f(xj，a)?Sa(xi)≤Sa(xj)

g(xi，d)≥g(xj，d)

則根據(jù)得分函數(shù)的大小確立了條件屬性上的偏序關(guān)系， 根據(jù)決策屬性值的大小確立了決策屬性上的偏序關(guān)系．

設(shè)DT*=(U，C∪j5i0abt0b，F(xiàn)，G)為直覺模糊決策表， 若存在屬性a的值域具有偏序關(guān)系， 則稱該屬性a為此系統(tǒng)中的一個(gè)準(zhǔn)則， 由若干個(gè)準(zhǔn)則組成的集合稱為準(zhǔn)則集．

于是， 優(yōu)勢(shì)關(guān)系的上、 下近似定義為

至此， 給出了直覺模糊偏好度量序決策表的相關(guān)定義， 得到了該決策表基于得分函數(shù)優(yōu)勢(shì)關(guān)系的上、 下近似．

2 直覺模糊偏好度量序決策表的近似約簡(jiǎn)理論

不同于經(jīng)典的Pawlak粗糙集理論， 本文討論的直覺模糊偏好度量序決策表所研究的背景關(guān)系為偏序關(guān)系， 而基于偏序關(guān)系的優(yōu)勢(shì)類構(gòu)成了論域的覆蓋而非劃分， 因此基于帶偏好度量的直覺模糊序決策信息系統(tǒng)的近似約簡(jiǎn)與經(jīng)典信息系統(tǒng)下的近似約簡(jiǎn)也有所不同．

下面給出直覺模糊偏好度量序決策表的上、 下近似約簡(jiǎn)函數(shù)及約簡(jiǎn)．

顯然， 由上面定義可知下述性質(zhì)成立．

該定理說明在協(xié)調(diào)集中不僅僅只保留了各個(gè)決策類中對(duì)象的信息， 而且還保留了包含不同決策類的對(duì)象之間的交互信息， 以此來保證約簡(jiǎn)之后與原決策表信息相對(duì)完整．

證1) 必要性： 使用反證法．

充分性： 使用反證法．

2)與1)同理可證．

3 直覺模糊偏好度量序決策表的近似約簡(jiǎn)方法

由于直接利用定義5求解上、 下近似的過程比較復(fù)雜， 效率低下， 所以本節(jié)給出求上、 下近似約簡(jiǎn)的具體判別方法， 即利用辨識(shí)矩陣求上、 下近似約簡(jiǎn)．

定義：

2)與1)同理可證．

2)與1)同理可證．

4 案例分析

通過上文得到了求解直覺模糊偏好度量序決策表近似約簡(jiǎn)的具體方法， 下面通過一個(gè)實(shí)例來說明具體近似約簡(jiǎn)的求解過程．

設(shè)某藝術(shù)公司收到了員工交納的一批畫作， 為了考察其價(jià)值將作品分成上、 中、 下3個(gè)等級(jí)， 公司委派10位專家從4個(gè)方面(色調(diào)、 意蘊(yùn)、 畫功、 風(fēng)格)對(duì)這批畫作進(jìn)行評(píng)判， 評(píng)判結(jié)果如表1所示．

表1列出的直覺模糊偏好度量序決策表中的直覺模糊數(shù)是通過專家的判斷確定的． 例如對(duì)于畫作x3， 要確定其畫工a3的隸屬度和非隸屬度， 讓10位專家對(duì)其投票， 有2位專家覺得畫作x3的畫功好， 而有7位專家覺得x3的畫工不好， 還有1位專家持保留意見， 不做評(píng)價(jià)， 這時(shí)就可以取畫作x3對(duì)畫功a3的隸屬度為0.2， 非隸屬度為0.7， 猶豫度為0.1． 而隸屬度權(quán)重α和非隸屬度權(quán)重β則是根據(jù)不同的問題， 不同的需求來設(shè)定， 這里設(shè)定隸屬度權(quán)重α=0.5， 非隸屬度權(quán)重β=0.3， 猶豫度權(quán)重γ=1-α-β=0.2．

下面分別用定義和辨識(shí)矩陣兩種不同方法來求解該系統(tǒng)的近似約簡(jiǎn)．

方法1

計(jì)算屬性AT下的各優(yōu)勢(shì)類：

再求出上、 下近似：

如果取A={a1}， 則：

此時(shí)

且

所以{a1}既不是上近似協(xié)調(diào)集也不是下近似協(xié)調(diào)集．

如果取A={a3}， 則：

此時(shí)

且

所以{a3}既是上近似協(xié)調(diào)集， 也是下近似協(xié)調(diào)集．

同理可以驗(yàn)證{a1，a2，a3}， {a2，a3，a4}， {a1，a3，a4}， {a1，a3}， {a2，a3}， {a3，a4}， {a3}都是上、 下近似協(xié)調(diào)集， 而{a1，a2，a4}， {a1，a2}， {a1，a4}， {a2，a4}， {a1}， {a2}， {a4}都不是上、 下近似協(xié)調(diào)集． 由此， 根據(jù)定義5可以求得該直覺模糊偏好度量序決策表的上近似約簡(jiǎn)和下近似約簡(jiǎn)都為{a3}．

方法2

首先， 計(jì)算該信息系統(tǒng)的上、 下近似辨識(shí)矩陣如表2、 表3所示．

表2 決策表的上近似辨識(shí)矩陣

表3 決策表的下近似辨識(shí)矩陣

于是， 由辨識(shí)矩陣可得：

Fσ=AT∧(a1，a3，a4)∧(a3，a4)∧(a3)=a3

Fρ=AT∧(a1，a2，a3)∧(a2，a3，a4)∧(a1，a3，a4)=a3

故得出該直覺模糊偏好度量序決策表的上、 下近似約簡(jiǎn)為{a3}． 與方法1求得的結(jié)果一致， 這說明了10位專家判斷畫作好壞的最主要的標(biāo)準(zhǔn)是畫功， 這也完全符合人們的認(rèn)知．

通過以上求解過程可以看出， 方法2的復(fù)雜度明顯要小于方法1， 方法1相對(duì)來看非常繁雜， 方法2比較簡(jiǎn)潔， 容易理解．

5 算法與實(shí)驗(yàn)

利用上節(jié)給出的直覺模糊偏好度量序決策表近似約簡(jiǎn)的辨識(shí)矩陣方法， 進(jìn)行算法設(shè)計(jì)(以下近似的約簡(jiǎn)為例， 上近似類似， 本文不再贅述)并給出詳細(xì)數(shù)值實(shí)驗(yàn)．

算法1直覺模糊偏好度量序決策表的下近似約簡(jiǎn)算法

輸出： 下近似約簡(jiǎn)Red

1.選擇屬性子集Red←?，red←?；

2.計(jì)算得分函數(shù)Sa(x)=αμa(x)-βνa(x)-γπa(x)；

3.fori=1 to |U| do

4.dec←?

5.forj=1 to |U| do

6.ifg(xi，d)≥g(xj，d) then

7.dec←xj

8.end if

9.end for

10.Dec←Dec∪dec

11.end for

12.end for//3至12步為求解決策類的過程//

13.fori=1 to |U| do

14.forj=1 to |U| do

15.Mij←?

18.Mij←A//(A={ak∈C|Sak(xi)>Sak(xj)})//

19.break

20.end if

21.end for

22.end for

23.end for//13至23步為求辨識(shí)矩陣的過程//

24.fori=1 to |U| do

25.forj=1 to |U| do

26.ifMij≠? then

27.red←red∪Mij

28.end if

29.ifi=1 then

30.Red←red

31.end if

32.Red←Red∩red

33.end for

34.end for//24至34步為根據(jù)辨識(shí)矩陣求約簡(jiǎn)的過程//

35.end

接下來， 我們通過系列實(shí)驗(yàn)來驗(yàn)證算法的有效性． 實(shí)驗(yàn)使用的計(jì)算機(jī)的配置如下： CPU為Intel(R) Cor e(TM) i5-6200U @ 2.30GHz， 內(nèi)存為4GB， 操作系統(tǒng)為64位Windows 10． 環(huán)境采用Python平臺(tái)． 數(shù)據(jù)集為UCI machine learning repository的8個(gè)數(shù)據(jù)集， 如表4所示．

表4 數(shù)據(jù)集總覽

根據(jù)算法1， 求出以上數(shù)據(jù)集的約簡(jiǎn)， 并使用該約簡(jiǎn)分別通過KNN和SVM兩個(gè)分類器進(jìn)行分類， 求出其分類的精度， 得到的精度如表5所示．

表5 在KNN與SVM下所得約簡(jiǎn)的分類精度 %

通過表5中的實(shí)驗(yàn)結(jié)果可以看到， 對(duì)算法1得到的約簡(jiǎn)進(jìn)行分類， 不論采用是KNN算法分類還是采用SVM算法分類， 分類精度都保持在一個(gè)較高的水平， 其平均精度分別為78.24和86.61， 結(jié)果較可觀．

6 結(jié)論

本文在序決策表的基礎(chǔ)上引入了直覺模糊集以及偏好度量， 從而序決策表拓展為直覺模糊偏好度量序決策表． 本文進(jìn)一步研究了基于直覺模糊偏好度量序決策表的近似約簡(jiǎn)， 并得出了近似約簡(jiǎn)的判定定理、 性質(zhì)及其辨識(shí)矩陣， 給出了求解直覺模糊偏好度量序決策表的近似約簡(jiǎn)的具體方法步驟， 最后通過案例對(duì)比分析了兩種求近似約簡(jiǎn)的方法， 并且通過實(shí)際數(shù)值實(shí)驗(yàn)驗(yàn)證了其有效性， 為對(duì)這類復(fù)雜的決策表進(jìn)行數(shù)據(jù)分析提供了新的理論基礎(chǔ)．