基于對象和基于屬性的三支概念格合并方法比較

蘇 新 陳永平 楊思春

1(馬鞍山職業(yè)技術學院電子信息系 安徽 馬鞍山 243000) 2(安徽工業(yè)大學計算機學院 安徽 馬鞍山 243000)

0 引 言

形式概念分析，又稱概念格理論(一般稱為經(jīng)典概念格)，1982年由德國數(shù)學家Ganter等[1]提出，該理論是根據(jù)數(shù)據(jù)集中二元關系建立的一種概念層次結構，是數(shù)據(jù)分析與規(guī)則提取的一種有效工具。目前形式概念分析已在決策分析、信息檢索、數(shù)據(jù)挖掘、軟件工程和知識發(fā)現(xiàn)等領域得到了廣泛的應用。

三支概念格[2]是由三支決策理論[3]與經(jīng)典概念格理論相結合而產(chǎn)生的一種用于知識發(fā)現(xiàn)的理論。三支決策理論將決策問題分為三種：接收、拒絕和延遲決策；經(jīng)典概念格理論只考慮某些對象共同具有內涵中的屬性或者某些屬性被外延中的所有對象共同擁有，而沒有考慮某些對象共同不具有的屬性或某些屬性不被哪些對象所擁有。Qi等將這兩種理論有機地結合起來，提出了負算子(共同不具有)的概念，而把經(jīng)典概念格中的運算稱為正算子(共同擁有)，由此可以將對象域或屬性域分成三個不相交的部分，分別是正域、負域和邊界域(部分擁有)。在此基礎上可以得到三支概念和三支概念格，分別是由對象導出的三支概念和三支概念格、由屬性導出的三支概念和三支概念格。

三支概念格提出以來，受到了學者的廣泛關注，并取得了不錯的研究成果。文獻[4]簡述了形式概念分析的優(yōu)劣與三支決策理論的意義,并闡述了三支概念格產(chǎn)生的思想，從理論和應用兩個方面梳理了三支概念格的研究成果，并對三支概念格的今后研究方向進行了展望；文獻[5]給出了三支概念格的四種約簡方法，并對它們之間的關系進行了討論；文獻[6]分別從元素、集合和序的角度對由對象和屬性導出的三支概念格與經(jīng)典概念格之間的關系進行了研究。目前對三支概念格的研究主要集中于屬性約簡[5,7-8]、三支概念格的構造[9]和規(guī)則的提取[10-11]等方面，而對三支概念格的合并研究較少。雖然文獻[12]利用規(guī)則提取方法，通過對對象導出的三支概念格和屬性導出的三支概念格的合并，給出了合并后的三支概念格的規(guī)則提取算法，但也僅僅是為了規(guī)則提取而給出一種合并方法，沒有給出合并后的三支概念格的相關性質。因此，本文在文獻[12]的研究基礎上，提出一種基于屬性為主的三支概念格的合并和基于對象為主的三支概念格的合并方法，并給出合并后三支概念格的性質，也就是對合并后的三支概念格與合并前的三支概念格和經(jīng)典概念格之間的關系進行了研究。同時也對兩種方法(基于屬性為主的三支概念格的合并和基于對象為主的三支概念格的合并)所得到的三支概念格之間的關系進行了研究，并給出基于屬性為主的三支概念格的合并和基于對象為主的三支概念格合并的算法，最后通過實例對本文提出的理論進行驗證。

1 基本知識

定義1[1]設(U，M，R)為形式背景，其中U={a1，a2，…，am}，每個ai(i=1,2,…,m)稱為對象,M={b1，b2，…，bn}，每個bj(j=1,2,…,n)稱為屬性,對于a∈U、b∈M,如果(a,b)∈R,則稱對象a擁有屬性b。

定義2[1]設(U，M，R)為形式背景，對于A?U,B?M，一對算子定義如下：

*:P(U)→P(M)，A*={b∈M|?a∈U,(a,b)∈R}

(1)

*：P(M)→P(U)，B*={a∈U|?b∈M,(a,b)∈R}

(2)

定義3[1]設(U，M，R)為形式背景，若A*=B且B*=A，則稱(A，B)是一概念，A稱為該概念的外延，B稱為該概念的內涵。

對于任意概念(A1，B1)、(A2，B2)，定義偏序關系為(A1，B1)≤(A2，B2)?A1?A2?B2?B1，則形式背景(U，M，R)的所有概念在該偏序關系下是完備格，稱為概念格，記為L(U，M，R)。

以上定義的算子是形式背景中的正算子，下面給出負算子的定義。

定義4[2]設(U，M，R)為形式背景，對于A?U,B?M，一對負算子定義如下：

(3)

(4)

在形式背景的正算子和負算子定義的基礎上，定義三支算子如下：

定義5[2]設(U，M，R)為形式背景，對于A?U,B?M，三支算子定義如下：

(5)

(6)

進一步定義該三支算子的逆算子如下：

≥：DP(M)→P(U)：(A,B)≥={a∈U|a∈A*

(7)

≥：DP(U)→P(M)：(X,Y)≥={b∈M|b∈X*

(8)

式中：DP(U)=P(U)×P(U)；DP(M)=P(M)×P(M)。

在此基礎上，下面可以定義三支概念和三支概念格。

定義6[2]設(U，M，R)為形式背景，X?U，A,B?M，若X≤=(A,B)且(A,B)≥=X，則稱(X，(A，B))為對象導出的三支概念，簡稱為OE-概念，其中X和(A，B)分別稱為OE-概念(X，(A，B))外延和內涵。

若(X，(A，B))、(Y，(C，D))為形式背景(U，M，R)的OE-概念，定義偏序關系(X，(A，B))≤(Y，(C，D))?X?Y?(C,D)?(X,Y)，形式背景(U，M，R)所有OE-概念在該偏序關系下是完備格，稱為對象導出的三支概念格，記為OEL(U，M，R)。

類似地，可以定義由屬性導出的三支概念和三支概念格。

定義7[2]設(U，M，R)為形式背景，X,Y?U，A?M，如果(X,Y)≥=A且A≤=(X,Y)，則稱((X，Y)，A)為屬性導出的三支概念，簡稱為AE-概念，其中(X，Y)和A分別稱為AE-概念((X，Y)，A)的外延和內涵。

若((X，Y)，A)、((Z，W)，B)為形式背景(U，M，R)的AE-概念，定義偏序關系((X，Y)，A)≤((Z，W)，B)?(X,Y)?(C,D)?B?A，形式背景(U，M，R)的所有AE-概念在該偏序關系下是完備格，稱為由屬性導出的三支概念格，記為AEL(U，M，R)。

例1在形式背景(U，M，R)中，U={1，2，3，4,5}，M={a，b，c，d},任意(u，m)∈R時，用1表示，任意(u，m)?R時，用0表示，其對應的概念格用L(U，M，R)表示，如表1所示，其對應的概念格L(U，M，R)={(1245，a)，(123，bd)，(12，abd)，(4，ac)，(U,?),(M,?)}，L(U，M，R)對應的哈斯圖如圖1所示，而(U，M，R)的補概念格L(U，M，Rc)={(1 235，c)，(45，bd)，(5，bcd)，(3，ac)，(U,?),(M,?)}，其對應的哈斯圖如圖2所示。表1對應的AEL(U，M，R)和OEL(U，M，R)分別如圖3和圖4所示。

表1 形式背景(U，M，R)

圖1 L(U，M，R)

圖2 L(U，M，Rc)

圖3 AEL(U，M，R)

圖4 OEL(U，M，R)

文獻[6]給出了經(jīng)典概念格與三支概念格的關系，下面給出經(jīng)典概念格和由對象導出的三支概念格的關系，在此記：

定理1[6]設(U，M，R)為形式背景，(U,M,Rc)為其補背景，其中Rc=U×MR，則下列式子成立：

①LU(U,M,R)?OELU(U,M,R)

②LU(U,M,Rc)?OELU(U,M,R)

下面再給出經(jīng)典概念格和由對象導出的三支概念格的關系，在此記：

定理2[6]設(U，M，R)為形式背景，(U,M,Rc)為其補背景，其中Rc=U×MR，則下列式子成立：

①LM(U,M,R)?AELM(U,M,R)

②LM(U,M,Rc)?AELM(U,M,R)

2 三支概念格的合并

2.1 基于屬性為主的三支概念格合并

定義8設(U，M，R)為形式背景，若((X，Y)，A)∈AEL(U，M，R)，(X，(A，B))∈OEL(U，M，R)或(Y，(B，A))∈OEL(U，M，R)，則((X，Y)，(A，B))為基于屬性為主的三支概念格合并，簡稱為AOE-概念。這里(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?U,Y?U,A?M,B?M。(X，Y)和(A，B)分別稱為AOE-概念的外延和內涵。

對于((X，Y)，(A，B))、((Z，W)，(C，D))，定義其上的偏序關系為((X,Y),(A,B))≤((Z,W),(C,D))?(X,Y)?(Z,W)?(C,D)?(A,B)，則形式背景(U，M，R)的所有AOE-概念在該定義的偏序關系下是完備格，記為AOEL(U，M，R)。

2.2 基于對象為主的三支概念格合并

定義9設(U，M，R)為形式背景，若(X，(A，B))∈OEL(U，M，R)，((X，Y)，A)∈AEL(U，M，R)，或((Y，X)，B)∈AEL(U，M，R)，則((X，Y)，(A，B))為基于對象為主的三支概念合并，簡稱為OAE-概念。這里X≤=(A,B)且(A,B)≥=X，(X,Y)≥=A且A≤=(X,Y)或X≤=(A,B)且(A,B)≥=X，B≤=(Y,X)且(Y,X)≥=B，X?U,Y?U,A?M,B?M。(X，Y)和(A，B)分別稱為OAE-概念的外延和內涵。

對于((X，Y)，(A，B))、((Z，W)，(C，D))，定義其上的偏序關系為((X,Y),(A,B))≤((Z,W),(C,D))?(X,Y)?(Z,W)?(C,D)?(A,B)，則形式背景(U，M，R)的所有OAE-概念在該定義的偏序關系下是完備格，記為OAEL(U，M，R)。

根據(jù)定義8和定義9分別得到AOEL(U，M，R)和OAEL(U，M，R)如圖5和圖6所示。

圖5 AOEL(U，M，R)

根據(jù)基于屬性為主和基于對象為主的三支概念格合并定義條件，在AEL(U，M，R)和OEL(U，M，R)中可能會存在一些概念，因不符合合并定義條件，在合并后的概念格中，不存在這樣的概念，如例1的OEL(U，M，R)中的概念(125，(a，c))。

3 合并前后三支概念格及經(jīng)典概念格之間的關系

在此先說明AOEL(U，M，R)與AEL(U，M，R)的關系，記：

定理3設(U，M，R)為形式背景，(U,M,Rc)為其補背景，其中Rc=U×MR，則下列式子成立：

同理可證得②和③成立。

而由定理2、①、②可證得④和⑤成立。

同樣對于合并后的三支概念格OAEL(U，M，R)與合并前的三支概念格的關系有以下結論成立，在此記：

定理4設(U，M，R)為形式背景，(U,M,Rc)為其補背景，其中Rc=U×MR，則下列式子成立：

同理可證得②和③成立。

而由定理1、①、②可證得④和⑤成立。

上面兩個定理說明了合并后的概念格和合并前的三支概念格及經(jīng)典概念格之間的關系，下面研究合并后的三支概念格之間的關系。

定理5設(U，M，R)為形式背景，AOEL(U，M，R)為基于屬性為主的三支概念格合并所得的三支概念格，OAEL(U，M，R)為基于對象為主的三支概念格合并所得的三支概念格，則對于任意((X，Y)，(A，B))∈AOEL(U，M，R)，有((X，Y)，(A，B))∈OAEL(U，M，R)或者((Y，X)，(B，A))∈OAEL(U，M，R)。

證明：?((X,Y),(A,B))∈AOEL(U,M,R)，則由定義8知，((X，Y)，(A，B))滿足下列兩個條件之一:

條件1：(X,Y)≥=A且A≤=(X,Y)，X≤=(A,B)且(A,B)≥=X，

條件2：(X,Y)≥=A且A≤=(X,Y)，Y≤=(B,A)且(B,A)≥=Y。

若滿足條件1，則由定義9易知，((X，Y)，(A，B))∈OAEL(U，M，R)。

若滿足條件2，由將X與Y互換，A與B互換，那么((X，Y)，(A，B))就變成((Y，X)，(B，A))，同樣條件將(X,Y)≥=A且A≤=(X,Y)，Y≤=(B,A)且(B,A)≥=Y也做出相應的變化得到X≤=(A,B)且(A,B)≥=X，B≤=(Y,X)且(Y,X)≥=B，則根據(jù)定義9知((Y，X)，(B，A))∈OAEL(U，M，R)。證畢。

由定理5可知，AOEL(U，M，R)和OAEL(U，M，R)中的概念數(shù)應該相等，而本文中AOEL(U，M，R)比OAEL(U，M，R)中的概念要少一個，這是因為((4，3)，ac)∈AEL(U，M，R)，(4，(ac，bd))∈OEL(U，M，R)，根據(jù)定義8生成的屬性/對象概念是((4，3)，(ac，bd))；而((4，3)，ac)∈AEL(U，M，R)，(3，(bd，ac))∈OEL(U，M，R)，按照定義8生成的三支概念也是((4，3)，(ac，bd))，所以AOEL(U，M，R)和OAEL(U，M，R)中的概念數(shù)可能是不相等的。

4 三支概念格的合并算法

合并算法流程如下：

輸入：由屬性導出的三支概念格AEL(U，M，R)和由對象導出的三支概念格OEL(U，M，R)。

輸出：由基于屬性為主的三支概念格合并的三支概念格AOEL(U，M，R)和由基于對象為主的三支概念格合并的三支概念格OAEL(U，M，R)。

1.AOEL(U，M，R)={}，OAEL(U，M，R)={}

2.for(i=1；i≤m,i++)

/*m表示AEL(U，M，R)中的概念個數(shù)*/

3.{for(j=1；j≤k;j++)

/*k表示OEL(U，M，R)中的概念個數(shù)*/

4.{ if

((Xi,Yi)≥=Ai&&Ai≤=(Xi,Yi)&&Xi≤=(Ai,Bj)&&(Ai,Bj)≥=Xi≤)

{AOEL(U，M，R)=AOEL(U，M，R)∪((Xi,Yi),(Ai,Bj))

OAEL(U，M，R)=OAEL(U，M，R)∪((Xi,Yi),(Ai,Bj))}

5.elseif

((Xi,Yi)≥=Ai&&Ai≤=(Xi,Yi)&&Yi≤=(Bj,Ai)&&(Bj,Ai)≥=Yi)

{AOEL(U，M，R)=AOEL(U，M，R)∪{((Xi,Yi),(Ai,Bj))

OAEL(U，M，R)=OAEL(U，M，R)∪((Yi,Xi),(Bj,Ai))}

/*根據(jù)定理5生成OAEL(U，M，R)*/}

6.for(i=1；i≤s-1；i++)

/*s表示AOEL(U，M，R)中的概念個數(shù)*/

7.for(j=i+1；j≤s；j++)

8.if((Xi,Yi),(Ai,Bi))=((Xj,Yj),(Aj,Bj))則刪除概念((Xj,Yj),(Aj,Bj))

9. 同樣的方法刪除OAEL(U，M，R)中的相同概念。

該算法中的第1行-第5行是根據(jù)定義8和定理5生成AOEL(U，M，R)和OAEL(U，M，R)，而第6行-第9行是分別刪除AOEL(U，M，R)和OAEL(U，M，R)中相同概念。算法的時間復雜度主要體現(xiàn)在AOEL(U，M，R)和OAEL(U，M，R)生成和刪除AOEL(U，M，R)和OAEL(U，M，R)中相同概念時，根據(jù)算法描述，AOEL(U，M，R)和OAEL(U，M，R)生成時的時間復雜度為O(mk)，而刪除AOEL(U，M，R)和OAEL(U，M，R)相同概念的時間復雜度為O(s2)，如果設n=max(m，k，s)，n為m、k、s中的最大值，則本文算法的時間復雜度為O(n2)。

5 結 語

三支概念格是將經(jīng)典概念格理論和三支決策理論相結合而發(fā)展起來，它使得形式概念分析更具體、更完善，而隨著大數(shù)據(jù)和計算機網(wǎng)絡的快速發(fā)展，需要對多個形式背景進行合并處理。因此，本文提出基于屬性為主的三支概念格的合并和基于對象為主的三支概念格的合并的定義，并給出合并后三支概念格的性質，也就是合并后的三支概念格與合并前的三支概念格及經(jīng)典概念格之間的關系，以及對兩種方法合并后的三支概念格之間的關系進行了研究，在此基礎上給出三支概念格合并算法，并通過實例驗證本文提出的理論。后續(xù)將對合并后的三支概念格的屬性約簡做更深入的研究。