基于三支概念格合并的決策背景規(guī)則提取

王一賓，楊思春

(1. 安慶師范大學(xué)計(jì)算機(jī)與信息學(xué)院 安徽 安慶 246011；2. 安徽省智能感知與計(jì)算重點(diǎn)實(shí)驗(yàn)室 安徽 安慶 246011；3. 安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 馬鞍山 243032)

作為形式概念分析(FCA)的核心數(shù)據(jù)結(jié)構(gòu)，概念格刻畫(huà)了概念之間的泛化和例化關(guān)系，在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和信息檢索等領(lǐng)域取得了廣泛的應(yīng)用[1]。近年來(lái)，概念格研究取得了很多重要的成果，特別是文獻(xiàn)[2]提出粗糙集框架下的概念格理論以來(lái)，一些學(xué)者借鑒粗糙集理論深入研究概念格的屬性約簡(jiǎn)和規(guī)則提取等問(wèn)題。文獻(xiàn)[3-6]研究了粗糙集與信息系統(tǒng)的屬性約簡(jiǎn)和規(guī)則提取問(wèn)題，文獻(xiàn)[7-10]探討了粗糙集與概念格的屬性約簡(jiǎn)理論以及基于概念格的決策形式背景規(guī)則獲取問(wèn)題。文獻(xiàn)[11-12]針對(duì)不完備決策形式背景，研究了相應(yīng)的近似概念構(gòu)造、規(guī)則提取以及知識(shí)約簡(jiǎn)。

作為二支決策的推廣，三支決策(3-way decisions)是文獻(xiàn)[13]提出的一種新的決策理論框架，它將決策問(wèn)題分為三類(lèi)：接收、拒絕和不承諾。傳統(tǒng)的形式概念分析僅支持二支決策，實(shí)際構(gòu)造形式概念時(shí)，僅僅考慮“某些對(duì)象共同具有哪些屬性”或“某些屬性為哪些對(duì)象所共同具有”，而沒(méi)有同時(shí)考慮“某些對(duì)象共同不具有哪些屬性”或“某些屬性為哪些對(duì)象所共同不具有”。為了更好地支持實(shí)際應(yīng)用中的復(fù)雜決策問(wèn)題，文獻(xiàn)[14-15]引入三支決策思想，將具有二支決策的形式概念分析推廣為支持三支決策的三支概念分析(3-way concept analysis)，提出了兩種具體的三支概念格(對(duì)象導(dǎo)出三支概念格和屬性導(dǎo)出三支概念格)，并研究了它們與經(jīng)典概念格之間的關(guān)系。

自文獻(xiàn)[14]提出三支概念格以來(lái)，就引起了有關(guān)學(xué)者的關(guān)注，并取得了一些初步的研究成果。文獻(xiàn)[16]對(duì)概念格與三支決策相結(jié)合的研究歷程、研究?jī)?nèi)容以及研究展望進(jìn)行了系統(tǒng)的綜述。目前，這些工作主要集中在基于三支概念格的屬性約簡(jiǎn)方面[17]，在基于三支概念格的規(guī)則提取方面則偏少。文獻(xiàn)[18]在利用三支概念格進(jìn)行規(guī)則提取方面做了有益的嘗試，給出了基于屬性導(dǎo)出三支概念格的決策背景規(guī)則提取方法，并通過(guò)與經(jīng)典概念格下的生成規(guī)則進(jìn)行比較，表明了基于屬性導(dǎo)出三支概念格的決策背景規(guī)則提取方法的有效性和優(yōu)越性。

本文在文獻(xiàn)[18]的基礎(chǔ)上進(jìn)一步研究基于對(duì)象導(dǎo)出三支概念格的規(guī)則提取，并與經(jīng)典概念格及屬性導(dǎo)出三支概念格下的生成規(guī)則進(jìn)行比較。同時(shí)通過(guò)對(duì)象導(dǎo)出三支概念格和屬性導(dǎo)出三支概念格的合并，進(jìn)一步改善三支概念格下的生成規(guī)則質(zhì)量。

1 基本概念和性質(zhì)

先給出形式背景及其算子的定義。

定義 1[1](G,M,I)為形式背景，其中G={x1, x2, …,xn}，每個(gè)xi(i≤n)稱(chēng)為對(duì)象；M={a1, a2, …, am}，每個(gè)aj(j≤m)稱(chēng)為屬性；對(duì)于x∈G與a∈M，如果(x,a)∈I，則稱(chēng)對(duì)象x擁有屬性a。

定義 2[1](G,M,I)為形式背景，X?G，A?M。一對(duì)算子定義如下：

*: P(G)→P(M)，X*={a∈M |?x∈X，(x,a)∈I}；

*: P(M)→P(G)，A*={x∈G |?a∈M，(x,a)∈I}?；谛问奖尘暗乃阕樱啥x形式概念及其概念格。

定義 3[1](G,M,I)為形式背景，若X*=A且A*=X，則稱(chēng)(X,A)是一個(gè)概念。X稱(chēng)為該概念的外延，A稱(chēng)為該概念的內(nèi)涵。

對(duì)于任意概念(X1,A1)，(X2,A2)，定義偏序關(guān)系為(X1,A1)≤(X2,A2)?X1?X2?A2?A1，則形式背景(G,M,I)的所有概念在該偏序關(guān)系下是完備格，稱(chēng)為概念格，記為L(zhǎng)(G,M,I)。

以下給出概念格之間的細(xì)于關(guān)系以及決策形式背景及其協(xié)調(diào)性的定義。

定義 4[8]L(G,M,I)與L(G,N,J)是兩個(gè)概念格，若對(duì)?(Y,B)∈L(G,N,J)，存在(X,A)∈L(G,M,I)，使得X=Y，則稱(chēng)L(G,M,I)細(xì)于L(G,N,J)，記作L(G,M,I)≤L(G,N,J) 。

定義 5[8](G,M,I)與(G,N,J)是兩個(gè)形式背景，則稱(chēng)(G,M,I,N,J)是決策形式背景。若L(G,M,I)≤L(G,N,J)，則稱(chēng)該決策形式背景是協(xié)調(diào)的。

為了在形式概念分析中引入三支決策的思想，給出形式背景負(fù)算子的定義：

定義 6[14](G,M,I)是形式背景，對(duì)于X?G，A?M，一對(duì)負(fù)算子定義如下：

*－: P(G)→P(M)：X*－= {a∈M|?x∈X，(xIa)}={a∈M|?x∈X，xIca}，其中Ic=(G×M)-I。

*－: P(M)→P(G)：A*－={x∈G|?a∈A，(xIa)}={x∈G|?a∈A，xIca}。

在形式背景算子及負(fù)算子的基礎(chǔ)上，可定義形式背景的三支算子：

定義 7[14](G,M,I)是形式背景，X?G，A?M，一對(duì)三支算子定義如下：

≤: P(G)→DP(M)：X≤=(X*，X*－)

≤: P(M)→DP(G)：A≤=(A*，A*－)

進(jìn)一步地，可定義上述三支算子的逆運(yùn)算：

≥: DP(M)→P(G)：(A,B)≥={x∈G|x∈A*且x∈B*－}=A*∩B*－

≥: DP(G)→P(M)：(X,Y)≥={a∈M|a∈X*且 a∈Y*－}=X*∩Y*－

基于形式背景的三支算子，可定義對(duì)象導(dǎo)出三支概念和對(duì)象導(dǎo)出三支概念格。

定義 8[14]設(shè)(G,M,I)是形式背景，(X,(A,B))稱(chēng)為對(duì)象導(dǎo)出三支概念，簡(jiǎn)稱(chēng)OE-概念，這里 X≤=(A,B)且(A,B)≥=X，其中X?G，A、B?M。X和(A,B)分別稱(chēng)為OE-概念的外延和內(nèi)涵。

對(duì)于(X,(A,B))，(Y,(C,D))，定義偏序關(guān)系(X,(A,B))≤(Y,(C,D))?X?Y?(C,D)?(A,B)，形式背景(G,M,I)的所有OE-概念在該偏序關(guān)系下是完備格，稱(chēng)為對(duì)象導(dǎo)出三支概念格，記為OEL(G,M,I)。

類(lèi)似地，可定義屬性導(dǎo)出三支概念及屬性導(dǎo)出三支概念格。

定義 9[14]設(shè)(G,M,I)是形式背景，則稱(chēng)((X,Y),A)為屬性導(dǎo)出三支概念，簡(jiǎn)稱(chēng)AE-概念，這里(X,Y)≥=A且A≤=(X,Y)，其中X、Y?G，A?M。(X,Y)和A分別稱(chēng)為AE-概念的外延和內(nèi)涵。

對(duì)于((X,Y),A),((Z,W),B)，定義偏序關(guān)系((X,Y),A)≤((Z,W),B)?(X,Y)?(Z,W) ?B?A，形式背景(G,M,I)的所有AE-概念在該偏序關(guān)系下是完備格，稱(chēng)為屬性導(dǎo)出三支概念格，記AEL(G,M,I)。

文獻(xiàn)[18]定義了屬性導(dǎo)出三支概念格之間的細(xì)于關(guān)系，以及決策背景基于屬性導(dǎo)出三支概念格的協(xié)調(diào)性。

定義 10[18]設(shè)AEL(G,M,I)與AEL(G,N,J) 是屬性導(dǎo)出三支概念格。若對(duì)于任意((Z,W),B)∈AEL(G,N,J)，存在((X,Y),A)∈AEL(G,M,I)，使得X=Z且Y=W，則稱(chēng)AEL(G,M,I) 細(xì)于AEL(G,N,J)，記作AEL(G,M,I)≤AEL(G,N,J)，并稱(chēng)決策背景(G,M,I,N,J)是基于屬性導(dǎo)出三支概念格協(xié)調(diào)的。

文獻(xiàn)[18]比較了屬性導(dǎo)出三支概念格和經(jīng)典概念格下的規(guī)則提取。

定理 1[18]設(shè)(G,M,I,N,J)是決策形式背景，且AEL(G,M,I)≤AEL(G,N,J)。R表示經(jīng)典概念格下的生成規(guī)則集合，TRa表示屬性導(dǎo)出三支概念格下的生成規(guī)則集合，則R?TRa。

定理 2[18]設(shè)(G,M,I,N,J)是決策形式背景，且AEL(G,M,I)≤AEL(G,N,J)，R表示經(jīng)典概念格下的生成規(guī)則集合，TRa表示屬性導(dǎo)出三支概念格下的生成規(guī)則集合，則對(duì)于A→B∈R，總存在C→B∈TRa，且C?A。

2 基于對(duì)象導(dǎo)出三支概念格的決策背景規(guī)則提取

文獻(xiàn)[18]給出基于屬性導(dǎo)出三支概念格的決策背景規(guī)則提取方法，本文在其基礎(chǔ)上進(jìn)一步研究基于對(duì)象導(dǎo)出三支概念格的規(guī)則提取，并與經(jīng)典概念格及屬性導(dǎo)出三支概念格下的規(guī)則提取進(jìn)行比較。

2.1 對(duì)象導(dǎo)出三支概念格下的生成規(guī)則

先定義對(duì)象導(dǎo)出三支概念格之間的細(xì)于關(guān)系，以及決策背景基于對(duì)象導(dǎo)出三支概念格的協(xié)調(diào)性。

定義 11 設(shè)OEL(G,M,I)與OEL(G,N,J)是對(duì)象導(dǎo)出三支概念格，若對(duì)于任意(Y,(C,D))∈OEL(G,N,J)，存在(X,(A,B))∈OEL(G,M,I)，使得X=Y，則稱(chēng)OEL(G,M,I)細(xì)于OEL(G,N,J)，記作OEL(G,M,I)≤OEL(G,N,J)，并稱(chēng)決策背景(G,M,I,N,J)是基于對(duì)象導(dǎo)出三支概念格協(xié)調(diào)的。

例1：表1是一個(gè)決策形式背景[18]，G={1,2,3,4}，M={a,b,c,d,e,f}，N={g,h,k}，其對(duì)象導(dǎo)出三支概念格OEL(G,M,I)和OEL(G,N,J)分別如圖1、圖2所示。

表1 決策形式背景(G,M,I,N,J)

圖1 對(duì)象導(dǎo)出三支概念格OEL(G,M,I)

圖2 對(duì)象導(dǎo)出三支概念格OEL(G,N,J)

由圖1、圖2可以看出，OEL(G,M,I)≤OEL(G,N,J)，所以表1所示決策背景是基于對(duì)象導(dǎo)出三支概念格協(xié)調(diào)的。

接著定義對(duì)象導(dǎo)出三支概念格下的生成規(guī)則。

定義 12 設(shè)決策背景(G,M,I,N,J)是基于對(duì)象導(dǎo)出三支概念格協(xié)調(diào)的，若對(duì)于X、Y≠?，G，有(X,(A,B))∈OEL(G,M,I), (Y,(C,D))∈OEL(G,N,J), 且X=Y，則稱(chēng)A→C和B→D分別是一個(gè)規(guī)則。

例2：根據(jù)定義12，表1所示決策背景在對(duì)象導(dǎo)出三支概念格下的生成規(guī)則集合TRo為：

d→g；de→g；ab→h；abc→h；f→k；def→gk；abde→gh；abcf→hk；abcef→hk

2.2 與經(jīng)典概念格下的生成規(guī)則比較

2.2.1 經(jīng)典概念格下的生成規(guī)則

定義 13 設(shè)決策背景(G,M,I,N,J)是協(xié)調(diào)的，若對(duì)于X,Y≠?,G，有(X,A)∈L(G,M,I)，(Y,B)∈L(G,N,J)，且X=Y，則稱(chēng)A→B是一個(gè)規(guī)則。

例3：表1所示決策背景的概念格L(G,M,I)和L(G,N,J)分別如圖3、圖4所示。

根據(jù)定義13，表1所示決策背景在經(jīng)典概念格下的生成規(guī)則集合R為：de→g；f→k；def→gk；abcef→hk

圖3 概念格L(G,M,I)

圖4 概念格L(G,N,J)

2.2.2 與經(jīng)典概念格下的生成規(guī)則比較

定理 3 設(shè)(G,M,I,N,J)是決策形式背景，且OEL(G,M,I)≤OEL(G,N,J)。R表示經(jīng)典概念格下的生成規(guī)則集合，TRo表示對(duì)象導(dǎo)出三支概念格下的生成規(guī)則集合，則R?TRo

證明：對(duì)任意A→B∈R，由定義13，存在(X,A)∈L(G,M,I)，(Y,B)∈L(G,N,J)，且X=Y。又因?yàn)镺EL(G,M,I)≤OEL(G,N,J)，由定義11，對(duì)于(Y,(B,Y*-J))∈OEL(G,N,J)，存在(X,(C,X*-I))∈OEL(G,M,I)。由于C=X*I=A，所以(X,(C,X*-I))即(X,(A,X*-I))。由定義12，A→B∈TRo，因此R?TRo

例4：比較表1所示決策背景分別在對(duì)象導(dǎo)出三支概念格及經(jīng)典概念格下的生成規(guī)則集合TRo和R，可以看出，TRo不僅包含了R中每條規(guī)則，還包含了ab→h；abde→gh等其他更多規(guī)則。

定理 4 設(shè)(G,M,I,N,J)是決策形式背景，且OEL(G,M,I)≤OEL(G,N,J)，R表示經(jīng)典概念格下的生成規(guī)則集合，TRo表示對(duì)象導(dǎo)出三支概念格下的生成規(guī)則集合，則對(duì)于A→B∈R，總存在C→B∈TRo，且C?A。

證明：對(duì)任意A→B∈R，由定義13，存在(X,A)∈L(G,M,I)，(Y,B)∈L(G,N,J)，且X=Y。由于存在保序 嵌 入[15]?:L(G,M,I)→OEL(G,M,I)，?:L(G,N,J)→OEL(G,N,J)，使?((X,A))=(X,(A,X*-I))，?((Y,B))= (Y,(B,Y*-J))，且OEL(G,M,I)≤OEL(G,N,J)，因此對(duì)于(Y,(B,Y*-J))∈OEL(G,N,J)，存在(Y,(C,Y*-I))∈OEL(G,M,I)，使得C→B∈TRa。又因?yàn)閅=C*I∩ Y*-I*-I，所以Y?C*I，進(jìn)而C?Y*I=X*I=A，即C?A。

例5：比較表1所示決策背景分別在對(duì)象導(dǎo)出三支概念格及經(jīng)典概念格下的生成規(guī)則集合TRo和R，可以看出，對(duì)于R中的每條規(guī)則A→B，在TRo中總存在相應(yīng)的規(guī)則C→B，且C?A。

與經(jīng)典概念格下的生成規(guī)則比較，對(duì)象導(dǎo)出三支概念格下的生成規(guī)則更為豐富也更為精煉。但是，由于對(duì)象導(dǎo)出三支概念格比經(jīng)典概念格的概念數(shù)量更多，結(jié)構(gòu)也更為復(fù)雜，因此構(gòu)建對(duì)象導(dǎo)出三支概念格比構(gòu)建經(jīng)典概念格要付出更多的時(shí)間開(kāi)銷(xiāo)。

2.3 與屬性導(dǎo)出三支概念格下的生成規(guī)則比較

2.3.1 屬性導(dǎo)出三支概念格下的生成規(guī)則

定義 14 設(shè)決策背景(G,M,I,N,J)是基于屬性導(dǎo)出三支概念格協(xié)調(diào)的，若(X,Y)、(Z,W) ≠(?,?)、(G,G)，有((X,Y),A)∈AEL(G,M,I)，((Z,W),B)∈AEL(G,N,J)，且X=Z、Y?W，則稱(chēng)A→B是一個(gè)規(guī)則。

例6：表1所示決策背景的屬性導(dǎo)出三支概念格AEL(G,M,I)和AEL(G,N,J)如圖5、圖6所示。

圖5 屬性導(dǎo)出三支概念格AEL(G,M,I)

圖6 屬性導(dǎo)出三支概念格AEL(G,N,J)

根據(jù)定義14，表1所示決策背景在屬性導(dǎo)出三支概念格下的生成規(guī)則集合TRa為：

d→g；de→g；ab→h；abe→h；abc→h；abcf→h；abcef→h；f→k；def→gk；abde→gh；abcf→hk；abcef→hk

2.3.2 與屬性導(dǎo)出三支概念格下的生成規(guī)則比較

先定義對(duì)象導(dǎo)出三支概念格與屬性導(dǎo)出三支概念格之間的細(xì)于關(guān)系，以及決策背景基于對(duì)象導(dǎo)出三支概念格和屬性導(dǎo)出三支概念格的協(xié)調(diào)性。

定義 15 設(shè)(G,M,I)是形式背景，若對(duì)于任意(X,(A,B))∈OEL(G,M,I)，存在((Y,Z),C)∈AEL (G,M,I)，使得X=Y或Z，則稱(chēng)AEL(G,M,I)細(xì)于OEL(G,M,I)，記作AEL(G,M,I)≤OEL(G,M,I)，并稱(chēng)形式背景(G,M,I)是基于AEL(G,M,I)和OEL(G,M,I)協(xié)調(diào)的。

例7：由定義15，對(duì)于圖1所示對(duì)象導(dǎo)出三支概念格OEL(G,M,I)，圖5所示屬性導(dǎo)出三支概念格AEL(G,M,I)，有AEL(G,M,I)≤OEL(G,M,I)，所以形式背景(G,M,I)是基于AEL(G,M,I)和OEL(G,M,I)協(xié)調(diào)的；類(lèi)似地，對(duì)于圖2所示對(duì)象導(dǎo)出三支概念格OEL(G,N,J)，圖4所示屬性導(dǎo)出三支概念格AEL(G,N,J)，有AEL(G,N,J)≤OEL(G,N,J)，所以形式背景(G,N,J)是基于AEL(G,N,J)和OEL(G,N,J)協(xié)調(diào)的。

接下來(lái)，給出相應(yīng)的規(guī)則定義。

定義 16 設(shè)形式背景(G,M,I)是基于AEL(G,M,I)和OEL(G,M,I)協(xié)調(diào)的，若對(duì)于X≠?、G，(Y,Z)≠(?, ?)、(G,G)，有(X,(A,B))∈OEL(G,M,I)，((Y,Z),C)∈AEL(G,M,I)，且X=Y或Z，則稱(chēng)A→B是一個(gè)規(guī)則。

在上述定義的基礎(chǔ)上，以下比較對(duì)象導(dǎo)出三支概念格與屬性導(dǎo)出三支概念格下的生成規(guī)則。

定理 5 設(shè)(G,M,I,N,J)是決策背景，且AEL(G,M,I)≤AEL(G,N,J)，OEL(G,M,I)≤OEL(G,N,J),AEL(G,M,I)≤OEL(G,N,J)，則TRo?TRa

證明：對(duì)于任意A→B∈TRo，由定義12，存在(X,(A,C)∈OEL(G,M,I)，(X,(B,D)∈OEL(G,N,J)。因?yàn)锳EL(G,M,I)≤OEL(G,N,J)，因此對(duì)于(X,(B,D)∈OEL(G,N,J)，存在((X,Z),A)或((Y,X),A)∈AEL(G,M,I)。又因?yàn)锳EL(G,N,J)≤OEL(G,N,J)，所以(X,(B,D)∈OEL(G,N,J)等價(jià)于((X,Z),A)或((Y,X),A)∈AEL(G,N,J)，因此對(duì)于((X,Z),A)或((Y,X),A)∈AEL(G,N,J)，存在((X,Z),A)或((Y,X),A)∈AEL(G,M,I)。因此A→B∈TRa，即TRo?TRa

例8：比較表1所示決策背景分別在對(duì)象導(dǎo)出三支概念格及屬性導(dǎo)出三支概念格下的生成規(guī)則集合TRo和TRa，可以看出，TRa不僅包含了TRo中每條規(guī)則，還包含了abe→h；abcf→h；abcef→h等規(guī)則。

通過(guò)與屬性導(dǎo)出三支概念格下的生成規(guī)則進(jìn)行比較，可以看出，屬性導(dǎo)出三支概念格下的生成規(guī)則更為豐富。但是，屬性導(dǎo)出三支概念格比對(duì)象導(dǎo)出三支概念格生成了更多的冗余規(guī)則，如圖5、圖6所示屬性導(dǎo)出三支概念格生成了de→g、abc→h、abe→h、abcf→h、abcef→h、abcef→hk等6條冗余規(guī)則，而圖1、圖2所示對(duì)象導(dǎo)出三支概念格只生成了de→g、abc→h、abcef→hk等3條冗余規(guī)則。因此，在支持決策分析方面，屬性導(dǎo)出三支概念格的能力要稍弱于對(duì)象導(dǎo)出三支概念格。

3 基于三支概念格合并的決策背景規(guī)則提取

與屬性導(dǎo)出三支概念格類(lèi)似，對(duì)象導(dǎo)出三支概念格下的生成規(guī)則中也引入了一些冗余規(guī)則。冗余規(guī)則是指[18]，對(duì)規(guī)則B→C和B′→C′，若B?B′且C′?C，則稱(chēng)規(guī)則B′→C′是冗余的。例如，由圖5、圖6，屬性導(dǎo)出三支概念格下的生成規(guī)則中de→g、abc→h、abe→h、abcf→h、abcef→h、abcef→hk均為冗余規(guī)則；由圖1、圖2，對(duì)象導(dǎo)出三支概念格下的生成規(guī)則中de→g、abc→h、abcef→hk均為冗余規(guī)則。

進(jìn)一步分析原因，主要是因?yàn)榛趯?duì)象導(dǎo)出三支概念格的規(guī)則提取時(shí)考慮的是對(duì)象特性，而基于屬性導(dǎo)出三支概念格的規(guī)則提取時(shí)考慮的是屬性特性。因此單純基于對(duì)象導(dǎo)出或?qū)傩詫?dǎo)出三支概念格進(jìn)行規(guī)則提取時(shí)，就會(huì)生成一些冗余規(guī)則。

為進(jìn)一步消除對(duì)象導(dǎo)出三支概念格或?qū)傩詫?dǎo)出三支概念格下生成的冗余規(guī)則，以下通過(guò)對(duì)象導(dǎo)出三支概念格與屬性導(dǎo)出三支概念格的合并，使得在進(jìn)行規(guī)則提取時(shí)受雙重特性(對(duì)象特性和屬性特性)約束，從而進(jìn)一步減少冗余規(guī)則的生成。為此，先給出對(duì)象/屬性導(dǎo)出合并三支概念格的定義。

定義 17 (G,M,I,N,J)是形式背景，若((X,Y),A)∈AEL(G,M,I)，(X,(A,B))或(Y,(B,A)) ∈OEL(G,M,I)，則((X,Y),(A,B))稱(chēng)為對(duì)象/屬性導(dǎo)出合并三支概念，簡(jiǎn)稱(chēng)OAE-概念，這里(X,Y)≥=A且A≤=(X,Y)，X≤=(A,B)且(A,B)≥=X ； 或 (X,Y)≥=A 且 A≤=(X,Y)， Y≤=(B,A)且(B,A)≥=Y。其中X、Y? G，A、B?M。(X,Y)和(A,B)稱(chēng)為OAE-概念的外延和內(nèi)涵。

對(duì)于((X,Y),(A,B))，((Z,W),(C,D))，定義其偏序關(guān)系 ((X,Y),(A,B)) ≤ ((Z,W),(C,D))?(X,Y)?(Z,W)?(C,D)?(A,B)，形式背景(G,M,I)的所有OAE-概念在上面定義的偏序關(guān)系下是完備格，稱(chēng)為對(duì)象/屬性導(dǎo)出合并三支概念格，記為OAEL(G,M,I)。

例9：合并圖1的OEL(G,M,I)和圖5的AEL(G,M,I)，以及圖2的OEL(G,N,J)和圖6的AEL(G,N,J)，所得對(duì)象/屬性導(dǎo)出合并三支概念格OAEL(G,M,I)和OAEL(G,N,J)如圖7、圖8所示。

圖7 對(duì)象/屬性導(dǎo)出合并三支概念格OAEL(G,M,I)

圖8 對(duì)象/屬性導(dǎo)出合并三支概念格OAEL(G,N,J)

接下來(lái)，定義對(duì)象/屬性導(dǎo)出合并三支概念格之間的細(xì)于關(guān)系，以及決策背景基于對(duì)象/屬性導(dǎo)出合并三支概念格的協(xié)調(diào)性。

定義 18 設(shè)OAEL(G,M,I)與OAEL(G,N,J)是對(duì)象/屬性導(dǎo)出合并三支概念格,若對(duì)于任意((Z,W),(C,D))∈OAEL(G,N,J)，存在((X,Y),(A,B))∈OAEL(G,M,I)，使得X=Z且Y=W，則稱(chēng)OAEL(G,M,I)細(xì)于OAEL(G,N,J)，記作OAEL(G,M,I)≤OAEL(G,N,J)，并稱(chēng)決策背景(G,M,I,N,J)是基于對(duì)象/屬性導(dǎo)出合并三支概念格協(xié)調(diào)的。

例10：表1所示決策背景的對(duì)象/屬性導(dǎo)出合并三支概念格OAEL(G,M,I)≤OAEL(G,N,J)，所以該決策背景是基于對(duì)象/屬性導(dǎo)出合并三支概念格協(xié)調(diào)的。

在上述定義的基礎(chǔ)上，進(jìn)一步定義對(duì)象/屬性導(dǎo)出合并三支概念格下的生成規(guī)則。

定義 19 設(shè)決策背景(G,M,I,N,J)是基于對(duì)象/屬性導(dǎo)出合并三支概念格協(xié)調(diào)的，若對(duì)于(X,Y)、(Z,W)≠(?,?)、(G,G)，有((X,Y),(A,B))∈OAEL(G,M,I),((Z,W),(C,D))∈OAEL(G,N,J)且X=Z、Y=W，則稱(chēng)A→C，B→D分別是一個(gè)規(guī)則。

例11：由圖7、圖8可以看出，因?yàn)?(?,1),(gh,?))∈OAEL(G,N,J)，((?,1),(abde,?))∈OAEL(G,M,I)，根據(jù)定義19，可得規(guī)則abde→gh, ?→?(舍去)。

以下給出基于對(duì)象/屬性導(dǎo)出合并三支概念格的規(guī)則提取算法。

算法1 基于合并三支概念格的規(guī)則提取算法

輸入：決策形式背景(G,M,I,N,J)；

輸出：決策規(guī)則集合C；

1) C=?；

2) 構(gòu)建對(duì)象導(dǎo)出三支概念格OEL(G,M,I)和OEL(G,N,J)；

3) 構(gòu)建屬性導(dǎo)出三支概念格AEL(G,M,I)和AEL(G,N,J)；

4) 合并OEL(G,M,I)和AEL(G,M,I)，構(gòu)建對(duì)象/屬性導(dǎo)出合并三支概念格OAEL(G,M,I)；

① 對(duì)于AEL(G,M,I) 中每個(gè)概念((X,Y),A))，若OEL(G,M,I)中存在對(duì)應(yīng)概念(X,(A,B))或(Y,(B,A))，則生成新概念((X,Y), (A,B))；

② 由所有概念((X,Y), (A,B))生成對(duì)象/屬性導(dǎo)出合并三支概念格OAEL(G,M,I)；

5) 合并OEL(G,N,J)和AEL(G,N,J)，構(gòu)建對(duì)象/屬性導(dǎo)出合并三支概念格OAEL(G,N,J)：

① 對(duì)于AEL(G,N,J)中每個(gè)概念((X,Y),A))，若OEL(G,N,J)中存在對(duì)應(yīng)概念(X,(A,B))或(Y,(B,A))，則生成新概念((X,Y), (A,B))；

② 由所有概念((X,Y), (A,B))生成對(duì)象/屬性導(dǎo)出合并三支概念格OAEL(G,N,J)；

6) 對(duì)于OAEL(G,N,J)中每個(gè)概念((X,Y), (C,D))，重復(fù)下列操作：

若OAEL(G,M,I)中存在對(duì)應(yīng)概念((X,Y),(A,B))，則C = C∪{A→C，B→D}；

7) 舍去C中所有前提或結(jié)論為φ的規(guī)則，輸出C。

該算法綜合利用了對(duì)象導(dǎo)出三支概念格所包含的對(duì)象信息和屬性導(dǎo)出三支概念格所包含的屬性信息，這是因?yàn)镺E概念(X,(A,B))刻畫(huà)了對(duì)象子集X共同具有的屬性子集A和共同不具有的屬性子集B，而AE概念((X,Y),A)刻畫(huà)了共同具有屬性子集A的對(duì)象子集X 和共同不具有屬性子集A的對(duì)象子集Y，因此相對(duì)于單純的對(duì)象導(dǎo)出三支概念格或?qū)傩詫?dǎo)出三支概念格，所得的對(duì)象/屬性導(dǎo)出合并三支概念格同時(shí)包含了對(duì)象和屬性信息，進(jìn)而也使得所生成的規(guī)則在冗余性方面得到一定程度的降低。

另外，該算法的實(shí)現(xiàn)效率主要取決于對(duì)象導(dǎo)出三支概念格和屬性導(dǎo)出三支概念格中的三支概念構(gòu)建算法。關(guān)于三支概念的構(gòu)建，文獻(xiàn)[19]通過(guò)對(duì)形式背景及其補(bǔ)背景的變換和并置，提出一種基于二支算子的三支概念構(gòu)建算法。文獻(xiàn)[20]針對(duì)三支概念分析理論中三支概念數(shù)量龐大、構(gòu)建耗時(shí)的問(wèn)題，提出一種三支概念的并行構(gòu)建算法?？紤]到本文示例中的形式背景比較簡(jiǎn)單，因此借鑒的是一般形式概念的構(gòu)建方法，在后續(xù)研究中將結(jié)合具體的應(yīng)用，嘗試采用上述兩類(lèi)新的三支概念構(gòu)建算法。

例12：應(yīng)用上述算法，由圖7、圖8的對(duì)象/屬性導(dǎo)出合并三支概念格OAEL(G,M,I)和OAEL(G,N,J)所得的生成規(guī)則集合如下：

d→g；ab→h；f→k；def→gk；abde→gh；abcf→hk

比較前面的屬性導(dǎo)出三支概念格下的生成規(guī)則集合：

d→g；de→g；ab→h；abe→h；abc→h；abcf→h；abcef→h；f→k；def→gk；abde→gh；

abcf→hk；abcef→hk

以及對(duì)象導(dǎo)出三支概念格下的生成規(guī)則集合：

d→g；de→g；ab→h；abc→h；f→k；def→gk；abde→gh；abcf→hk；abcef→hk

可以看出，對(duì)屬性導(dǎo)出三支概念格和對(duì)象導(dǎo)出三支概念格進(jìn)行合并以后，進(jìn)一步消除了原來(lái)的冗余規(guī)則。

4 結(jié) 束 語(yǔ)

在決策背景的規(guī)則提取方面，現(xiàn)有文獻(xiàn)基于屬性導(dǎo)出三支概念格進(jìn)行規(guī)則提取，并取得了較好的效果。本文在其基礎(chǔ)上進(jìn)一步研究了基于對(duì)象導(dǎo)出三支概念格的規(guī)則提取，并與經(jīng)典概念格及屬性導(dǎo)出三支概念格下的規(guī)則提取進(jìn)行了比較；同時(shí)通過(guò)對(duì)象導(dǎo)出三支概念格和屬性導(dǎo)出三支概念格的合并，定義了對(duì)象/屬性導(dǎo)出合并三支概念格，并提出了基于對(duì)象/屬性導(dǎo)出合并三支概念格的規(guī)則提取算法。理論分析和實(shí)例結(jié)果也表明了本文工作的有效性。下一步將本文提出的決策規(guī)則提取算法應(yīng)用到地理課程自動(dòng)解題研究，以自動(dòng)獲取用于地理試題解答的隱式解題規(guī)則。