含參模糊決策蘊涵

王 琪 李德玉,2 翟巖慧,2 張少霞

1(山西大學(xué)計算機與信息技術(shù)學(xué)院 太原 030006)

2(計算智能與中文信息處理教育部重點實驗室(山西大學(xué)) 太原 030006)

(chai_yanhui@163.com)

在哲學(xué)視角下，概念由外延和內(nèi)涵2個部分組成,外延被定義為屬于這個概念的所有對象的集合,而內(nèi)涵則是所有這些對象所共有的特征(屬性)集合.1982年，Wille等人[1]基于此提出了形式概念分析(formal concept analysis, FCA)理論.該理論根據(jù)概念之間的包含關(guān)系構(gòu)成的概念格來反映數(shù)據(jù)的代數(shù)結(jié)構(gòu).近年來，F(xiàn)CA以其具有堅實的數(shù)學(xué)理論支撐、獲取的知識層次清晰且邏輯性強等優(yōu)點，逐漸吸引了廣大研究者的興趣[2-15].目前，F(xiàn)CA已經(jīng)廣泛應(yīng)用于機器學(xué)習[2]、軟件工程[3]、社會網(wǎng)絡(luò)分析[4]、概念認知學(xué)習[5-6]、知識獲取[7]和知識約簡[8]等領(lǐng)域.

產(chǎn)生式規(guī)則是知識的主要表現(xiàn)形式，F(xiàn)CA對知識獲取的研究就是對蘊涵的研究.由于獲得的蘊涵數(shù)量龐大，無法滿足用戶的需求，因此如何獲得完備的無冗余的蘊涵成為研究熱點.Ganter等人[1]研究了蘊涵的語義特征和語構(gòu)特征，并且給出一種在所有蘊涵基中蘊涵個數(shù)最少的蘊涵基，稱為自然基.文獻[16]進一步從邏輯角度出發(fā)，提出了一種用于判別蘊涵集是否為完備集的充要條件，并且給出一種生成蘊涵完備集的算法.

為了進一步減少蘊涵的數(shù)目，Qu等人通過限制蘊涵的前件和后件分別為條件屬性和決策屬性提出了決策蘊涵的概念[17]，并完整討論了決策蘊涵的邏輯特征[18].基于決策蘊涵的邏輯研究，文獻[19]提出了決策前提的概念，并據(jù)此生成一種完備無冗余且最優(yōu)的知識基：決策蘊涵規(guī)范基.文獻[20]對決策蘊涵與粒規(guī)則[21]和概念規(guī)則[22]進行了比較研究，發(fā)現(xiàn)與決策蘊涵相比，粒規(guī)則和概念規(guī)則存在信息損失.另外，文獻[23]也從邏輯角度研究了具有支持度和可信度的決策蘊涵.文獻[24]將決策蘊涵拓展到模糊形式背景上，提出了模糊決策蘊涵的概念，并討論其語義特征和語構(gòu)特征.文獻[25]提出模糊決策蘊涵規(guī)范基的概念，并證明模糊決策蘊涵規(guī)范基的完全性、無冗余性和最優(yōu)性.

模糊決策蘊涵可以基于語氣真值算子(hedge)進行簡化知識[24-25]，但并沒有考慮閾值這一參數(shù)化策略.在現(xiàn)實生活中，閾值在簡化知識方面具有重要的作用.例如，在知識“如果1個女性年輕的程度超過0.8，那么該用戶喜歡愛情喜劇類電影的程度將會超過0.5”中，0.8和0.5均為閾值，但模糊決策蘊涵理論并不適用挖掘此類具有閾值的知識.事實上，模糊決策蘊涵理論只能挖掘諸如“年輕女性喜歡愛情喜劇類電影”不帶有閾值的知識，其中年輕和愛情喜劇類均為模糊集.可以發(fā)現(xiàn)，模糊決策蘊涵僅僅是閾值為1時的特例，因此，研究含有閾值的模糊決策蘊涵不僅具有應(yīng)用意義，而且具有理論意義，即含有閾值的模糊決策蘊涵是模糊決策蘊涵的擴展理論.

本文對模糊決策蘊涵進行拓展，定義了含參模糊決策蘊涵，并研究了其語義特征和語構(gòu)特征.

1 模糊邏輯

本節(jié)簡要介紹相關(guān)的基礎(chǔ)背景知識.

定義1[26].在Pavelka邏輯中，真值結(jié)構(gòu)是形如(L,∧,∨,?,→,0,1)的完備剩余格，滿足3個性質(zhì)：

1) (L,∧,∨,0,1)是以0和1為最小元和最大元的完備格；

2) (L,?,1)為交換幺半群，即?滿足交換律和結(jié)合律，且有?a∈L,a?1=1?a=a；

3) ?，→為伴隨對，滿足伴隨條件a?b≤c當且僅當a≤b→c，其中a,b,c∈L.

運算?，→分別表示模糊合取和模糊蘊含，L中的元素稱為真實度.

常見的完備剩余格的例子是單位區(qū)間[0,1]，∧和∨運算分別是最小值和最大值.3個單位區(qū)間上重要的伴隨對如下.

a?b=max(a+b-1,0)，
a→b=min(1-a+b,1).

Godel：

Goguen：

a?b=a·b，

語氣真值算子(hedge)可以增加推理的靈活性.

定義2[24].模糊集L上的語氣真值算子定義為映射*:L→L，滿足：

1) 1*=1,a*≤a，

2) (a→b)*≤a*→b*，

3)a**=a*，

其中，a,b∈L.

最大的語氣真值算子為Identity，即對任意的a∈L，都有a*=a.

最小的語氣真值算子為Globalization，即

性質(zhì)1[24].完備剩余格主要具有10條性質(zhì).對于a,b,c,yi∈L：

1)a≤b?a→b=1；

2)a≤b→c?b≤a→c；

3) (a?b)→c=(a→(b→c))；

4)a→∧yi=∧(a→yi)；

5) 1→a=a；

6)a?(a→b)≤b；

7)a≤(b→(a?b))；

8)a*?b*=(a?b)*；

9)a≤(b→(a?b))*；

10)a?∨yi=∨(a?yi).

定義3[24].模糊集A是定義在論域X上的一個映射，它賦予每個x∈X一個隸屬度A(x)∈L.論域X上的所有模糊集記為LX.

定義4[24].L-模糊集之間的包含關(guān)系定義為

性質(zhì)2[24].模糊集之間的包含關(guān)系主要有4個性質(zhì)：

1)a→S(A,B)=S(a?A,B)=S(A,a→B)；

2)S(A∪B,C)=S(A,C)∧S(B,C)；

3)S(A,B∩C)=S(A,B)∧S(A,C)；

4)S(A,B)?S(B,C)≤S(A,C).

2 含參模糊決策蘊涵的語義、語構(gòu)及其性質(zhì)

類似于模糊決策蘊涵[24]，含參模糊決策蘊涵的研究內(nèi)容包括語義和語構(gòu)2個方面.

1) 語義方面的研究包括：①含參模糊決策蘊涵的合理性，即含參模糊決策蘊涵是否合法；②含參模糊決策蘊涵的無冗余性，即含參模糊決策蘊涵能否被其他含參模糊決策蘊涵導(dǎo)出；③含參模糊決策蘊涵的完備性，即含參模糊決策蘊涵是否包含完整的信息.

2) 語構(gòu)方面的研究包括：①推理規(guī)則的合理性，即含參模糊決策蘊涵能否使用推理規(guī)則得出；②推理規(guī)則的完備性，即是否能用這些推理規(guī)則推出所有可能的含參模糊決策蘊涵.

2.1 含參模糊決策蘊涵的語義特征

本文使用Bělohlávek等人[14]提出的同時考慮閾值和語氣真值算子的概念構(gòu)成算子，并將其引入到模糊決策蘊涵中.

定義5.C∪D上的含參模糊決策蘊涵為公式A?B，其中A∈LC，B∈LD分別是條件屬性和決策屬性的模糊集.設(shè)模糊屬性集T∈LC∪D，TC={t/l∈T|t∈T∩C}，TD={t/l∈T|t∈T∩D}，則其對含參模糊決策蘊涵A?B的滿足程度定義為

其中,δ=(δ1,δ2)∈L×L，δ1和δ2是2個閾值參數(shù).

例1.令L={0,0.25,0.5,0.75,1}，C={s,l}，D={f,n}，δ1=δ2=0.5，使用ukasiewicz伴隨對和Identity語氣真值算子，令

A?B={0.5/s,0.5/l}?{0.5/f,0.5/n}，
T={0.75/s,0/l,0.25/f,0.5/n}，
TC={0.75/s,0/l}，
TD={0.25/f,0.5/n}，

則

這表明數(shù)據(jù)T滿足含參模糊決策蘊涵“若對象含有屬性s和l的程度均超過0.5，則其含有屬性f和n的程度也均超過0.5”的程度為1.

定理1.設(shè)模糊屬性集T∈LC×LD，含參模糊決策蘊涵為A?B，A∈LC，B∈LD，則有

證明.由定義5及伴隨對的性質(zhì)容易證明該結(jié)論成立.

證畢.

定理1的第1個等式表明，在閾值δ=(δ1,δ2)下，數(shù)據(jù)T滿足含參模糊決策蘊涵的程度與(δ1→TC)∪(δ2→TD)滿足模糊決策蘊涵的程度相同.定理1的第2個等式表明，數(shù)據(jù)T滿足含參模糊決策蘊涵的程度等于數(shù)據(jù)T滿足前件為δ1?A、后件為B的模糊決策蘊涵的程度超過δ2的程度.

定理2.設(shè)模糊屬性集T∈LC∪D，則對含參模糊決策蘊涵A?B，A∈LC，B∈LD有

證明.由定理1以及文獻[22]中定理1的證明可證.

證畢.

定義6.T={T1,T2,…,Tn}?LC∪D滿足含參模糊決策蘊涵A?B，A∈LC，B∈LD的程度定義為

定義6表明，含參模糊決策蘊涵在數(shù)據(jù)集T中成立的程度是其在所有數(shù)據(jù)中Ti∈T成立程度的最小值.

定義7.設(shè)L為含參模糊決策蘊涵集，L的所有模型定義為

其中,L(A?B)是A?B屬于L的程度.含參模糊決策蘊涵從L中語義導(dǎo)出的程度定義為

即A?B從L導(dǎo)出的程度等于L的全部模型滿足A?B的程度.

例2.令含參模糊決策蘊涵集L為

L={({0.5/s,0.25/l}?{0.25/f,0.5/n})/0.75,
({0/s,0.5/l}?{0.5/f,0/n})/0.75}，

令δ1=δ2=0.5.對于T={0.5/s,0/l,0/f,0.5/n}，使用ukasiewicz伴隨對和Identity語氣真值算子計算可得

可以發(fā)現(xiàn)，T滿足L中含參模糊決策蘊涵的程度均為1，從而T是L的模型.

定理3.對于含參模糊決策蘊涵集L和含參模糊決策蘊涵A?B，A∈LC，B∈LD有

1)Modδ(L)={T|(δ1→TC)∪(δ2→TD)∈Mod1(L)}；

證明.類似于文獻[22]可證.

證畢.

定理3的1)和2)相當于定理1的第1個等式的推論，定理3的3)是2)的推論.值得注意的是，由定理3的2)并不能得出含參模糊決策蘊涵的語義導(dǎo)出程度關(guān)于參數(shù)δ是遞減的，只能得出該語義導(dǎo)出程度的2個極值.參數(shù)的引入，使得語義導(dǎo)出程度的變化更加復(fù)雜，不再是單純的單調(diào).

給定一個條件屬性模糊集以及參數(shù)δ1和δ2，該條件屬性模糊集可以從給定的含參模糊決策蘊涵集中得出的所有結(jié)論，即該條件屬性模糊集的閉包.

定義9.對于含參模糊決策蘊涵集L和A∈LC，定義A相對于L的閉包為

例3.設(shè)A={0.5/s,0/l}，δ1=δ2=0.5，使用ukasiewicz伴隨對和Identity語氣真值算子.令

L={(A1?B1)/0.75,(A2?B2)/0.75}=
{({0.5/s,0.25/l}?{0.25/f,0.5/n})/0.75,
({0/s,0.5/l}?{0.5/f,0/n})/0.75}，

則

L(A1?B1)?S(δ1?A1,A)*?B1=
0.75?1?B1={0/f,0.25/n}，
L(A2?B2)?S(δ1?A2,A)*?B2={0/f,0/n}.

對于不在模糊決策蘊涵集中的模糊決策蘊涵，有

L(A1?B1)?S(δ1?A1,A)*?B1=
0?S(δ1?A1,A)*?B1={0/f,0/n}，

證明.對于任意的A1?B1∈L，記

c=L(A1?B1)?S(δ1?A1,A)*，

顯然有

(c?B1(u)?δ2)→(c?B1(u)?δ2)=1.

由性質(zhì)1的結(jié)論3)和4)有

(c?B1?δ2)→(c?B1?δ2)=
c→S(δ2?B1,δ2?c?B1)=1，

從而c≤S(δ2?B1,δ2?c?B1)，即

L(A1?B1)?S(δ1?A1,A)*≤
S(δ2?B1,δ2?L(A1?B1)?
S(δ1?A1,A)*?B1).

又因為

從而可得

即

證畢.

例4.(續(xù)例3)令A(yù)={0.5/s,0/l}，由例3可得

對于L中的含參模糊決策蘊涵有

因此有T0∈Modδ(L).

證畢.

證明.對于任意的T∈Modδ(L)和A1?B1有

由伴隨對的性質(zhì)有

L(A1?B1)?S(δ1?A1,TC)*≤
S(δ2?B1,TD)?L(A1?B1)?
S(δ1?A1,TC)*→
S(δ2?B1,TD)=1.

由性質(zhì)1的結(jié)論8)和性質(zhì)2的結(jié)論4)有

S(δ1?A1,δ1?A)*?
S(δ1?A,TC)*≤S(δ1?A1,TC)*，

兩邊同乘L(A1?B1)可得

L(A1?B1)?S(δ1?A1,δ1?A)*?S(δ1?
A,TC)*≤L(A1?B1)?S(δ1?A1,TD)*，

由→的性質(zhì)有

L(A1?B1)?S(δ1?A1,δ1?A)*?
S(δ1?A,TC)*→S(δ2?B1,TD)≥
L(A1?B1)?S(δ1?A1,TC)*→
S(δ2?B1,TD)=1，

從而

L(A1?B1)?S(δ1?A1,δ1?A)*?
S(δ1?A,TC)*≤S(δ2?B1,TD)，

由性質(zhì)1的結(jié)論3)有

S(δ1?A,TC)*≤L(A1?B1)?
S(δ1?A1,δ1?A)*→
S(B1,δ2→TD)=
S(δ2?L(A1?B1)?
S(δ1?A1,δ1?A)*?B1,TD)，

由性質(zhì)2的2)和性質(zhì)1的4)，上式等價于

由定義9可得

從而

即

證畢.

定理6.對于含參模糊決策蘊涵集L，可得

證明.由定理4容易得

進而

反過來，設(shè)T∈Modδ(L)，有

L(A1?B1)≤S(δ1?A1,TC)*→
S(δ2?B1,TD)?L(A1?B1)?
S(δ1?A1,TC)*≤S(δ2?B1,TD)?
L(A1?B1)?S(δ1?A1,TC)*≤
δ2?B1(d)→TD(d),?d∈D
?L(A1?B1)?S(δ1?A1,TC)*?
δ2?B1(d)≤TD(d),?d∈D?
L(A1?B1)?S(δ1?A1,TC)*?
δ2?B1?TD，

證畢.

例5.設(shè)C={a}，D={z}，真值結(jié)構(gòu)采用L={0,0.25,0.5,0.75,1}，δ1=0.75，δ2=1，采用ukasiewicz算子和Identity語氣真值算子.設(shè)含參模糊決策蘊涵集為L={{1/a}?{1/z}/1}.計算閉包及其模型如表1所示：

Table 1 Closure and Models表1 閉包及其模型

因此有

Modδ(L)={{0/a,0.25/z},{0/a,0.5/z},
{0/a,0.75/z},{0/a,1.0/z},{0.25/a,0.75/z},
{0.25/a,1/z},{0.5/a,0.75/z},{0.5/a,1/z},
{0.75/a,0.75/z},{0.75/a,1/z},{1/a,1/z}}.

定理7.對于含參模糊決策蘊涵集L和含參模糊決策蘊涵A?B，有

另一方面，設(shè)T∈Modδ(L)，由定理5有

即

因此

從而由性質(zhì)2的結(jié)論4)可知

因此

等價于

證畢.

定理7同時也給出了含參模糊決策蘊涵從含參模糊決策蘊涵集中導(dǎo)出程度的計算方法.

2.2 含參模糊決策蘊涵的語構(gòu)特征

其中φ1,φ2,…,φn,φ是n+1條含參模糊決策蘊涵，a1,a2,…,an,a∈L，ai可以為L(φi)，即φi的隸屬度，也可以為使用推理規(guī)則從含參模糊決策蘊涵集推導(dǎo)的φi的程度.

推理規(guī)則的含義為：若含參模糊決策蘊涵φi具有隸屬度或者導(dǎo)出程度ai，i∈{1,2,…,n}，則可推導(dǎo)出程度為a的含參模糊決策蘊涵φ.

針對含參模糊決策蘊涵，本文提出3條推理規(guī)則.

1) 含參模糊變換推理規(guī)則：

2) 含參模糊擴增推理規(guī)則：

3) 含參模糊轉(zhuǎn)換推理規(guī)則：

定義10[24].模糊推理規(guī)則

是合理的，若

Mod({a1/φ1,a2/φ2,…,an/φn})=
Mod({a1/φ1,a2/φ2,…,an/φn,a/φ}).

定理8.上述3條規(guī)則是合理的.

證明.含參模糊變換推理規(guī)則：設(shè)T是A?B,a的模型，即‖A?B≥a，要證明T也是A1?B1,a?S(δ1?A,δ1?A1)*?S(δ2?B1,δ2?B)的模型，即證

這等價于證明

a?S(δ1?A,δ1?A1)*?S(δ2?B1,δ2?B)?
S(δ1?A1,TC)*≤S(δ2?B1,TD)，

由性質(zhì)2的結(jié)論4)可得

S(δ2?B1,δ2?B)?S(δ2?B,TD)≤
S(δ2?B1,TD)，

(1)

另外，由性質(zhì)1的結(jié)論6)有

(S(δ1?A,TC)*→S(δ2?B,TD))?
S(δ1?A,TC)*≤S(δ2?B,TD)，

(2)

聯(lián)立式(1)和式(2)可得

(S(δ1?A,TC)*→S(δ2?B,TD))?
S(δ1?A,TC)*?S(δ2?B1,δ2?B)≤
S(δ2?B,TD)?S(δ2?B1,δ2?B)≤
S(δ2?B1,TD)，

上式可變形為

另外，由性質(zhì)1的結(jié)論6)又有

S(δ1?A,δ1?A1)*?S(δ1?A1,TC)*≤
S(δ1?A,TC)*，

因此可得

即有

這說明T也是A1?B1,a?S(δ1?A,δ1?A1)*?S(δ2?B1,δ2?B)的模型.

證畢.

含參模糊擴增推理規(guī)則和含參模糊變換推理規(guī)則的合理性證明類似.

定理9.上述3條模糊推理規(guī)則相對于含參模糊決策蘊涵的語義特征是完備的.

其中bi=L(Ai?Bi).由含參模糊轉(zhuǎn)換推理規(guī)則有

再由含參模糊擴增推理規(guī)則合并得到的所有含參模糊決策蘊涵可得

證畢.

3 結(jié) 論

本文在模糊決策蘊涵中引入了閾值，提出了含參模糊決策蘊涵，提升了模糊決策蘊涵的可調(diào)節(jié)性和應(yīng)用價值.在語義方面，研究了含參模糊決策蘊涵的模型和語義導(dǎo)出程度的計算方法；在語構(gòu)方面，將模糊決策蘊涵中的3條推理規(guī)則拓展到含參模糊決策蘊涵，并證明了這些推理規(guī)則的合理性和完備性.

從理論上看，將閾值引入模糊決策蘊涵的意義并不局限于構(gòu)建一種以模糊決策蘊涵為特例的理論框架.一方面，這種引入方式具有普遍意義，事實上，定義4和性質(zhì)1的1)正是模糊集包含度和含參的模糊集包含度的定義.因此，這個引入方式對整個粒計算領(lǐng)域均有參考意義.另一方面，由定義5可以看出，將閾值引入模糊決策蘊涵本質(zhì)上相當于在完備剩余格上建立一種協(xié)調(diào)結(jié)構(gòu)，而定理1正是說明這種協(xié)調(diào)結(jié)構(gòu)所具有的特性，因此，本文的結(jié)論對完備剩余的公理化或代數(shù)研究也具有一定的啟發(fā)意義.進一步來說，含參模糊決策蘊涵同時包含閾值和語氣真值算子2種知識簡化策略，但本文并沒有考慮這種簡化策略之間的聯(lián)系和相互作用.事實上，如果說參數(shù)的引入是在完備剩余格上建立一種協(xié)調(diào)結(jié)構(gòu)，那么語氣真值算子就是完備剩余格上的另一種協(xié)調(diào)結(jié)構(gòu)，因此，從代數(shù)角度和應(yīng)用角度研究這2種結(jié)構(gòu)之間的關(guān)系將是下一步的研究工作.

值得指出的是，在應(yīng)用中，用戶可能需要根據(jù)不同的實際需求選擇合適的閾值.由定理1可知，給定模糊決策背景，參數(shù)δ1越小或參數(shù)δ2越大，滿足含參模糊決策蘊涵的模型也越少，因此模糊決策背景中成立的含參模糊決策蘊涵也越少.當δ1和δ2分別為0和1時，用戶可以得到最嚴格意義上的模糊決策蘊涵；用戶可以進一步增加δ1或減小δ2來獲取更多的模糊決策蘊涵.在具體應(yīng)用中，用戶可以參考專家的意見來選定閾值，或選取一些指標(如分類性能等)來有監(jiān)督地選擇合適的閾值.

作者貢獻聲明：王琪負責設(shè)計研究方案、方法實現(xiàn)與論證、論文初稿撰寫；李德玉提出研究思路，優(yōu)化研究方案；翟巖慧參與研究方案優(yōu)化以及方法檢驗與論證；張少霞參與方法檢驗與論證以及論文審閱與修訂.