基于直觀圖的三支概念獲取及屬性特征分析

萬 青，馬盈倉，李金海

1.西安工程大學 理學院，西安 710048

2.西北大學 概念、認知與智能研究中心，西安 710127

3.昆明理工大學 理學院，昆明 650500

4.昆明理工大學 數(shù)據(jù)科學研究中心，昆明 650500

形式概念分析理論[1]是Wille 于1982 年提出的，用于概念的發(fā)現(xiàn)、排序和顯示，是知識發(fā)現(xiàn)的有效數(shù)學理論。該理論的基礎數(shù)據(jù)是形式背景，Wille 通過概念誘導算子提取了形式背景中“共同具有”的共性信息，進而形成概念格。隨后，借鑒粗糙集理論[2]中的上、下近似思想，Gediga和Duntsch以及Yao[3-4]提出了面向?qū)ο蟾拍罡窈兔嫦驅(qū)傩愿拍罡?，將形式背景中部分具有的信息提煉出來。此外?014年，Qi等將三支決策理論[5]的思想引入形式概念分析，提出了對象誘導的三支概念格和屬性誘導的三支概念格這兩種模型，它們既可以表達形式背景中“共同（被）具有”的共性信息，也可以表達“共同不（被）具有”的共性信息，使得獲取的知識更為豐富，為知識發(fā)現(xiàn)提供了新的理論——三支概念分析[6]。

目前，關于該理論的研究包括三支概念格的構建、模型推廣、屬性約簡、規(guī)則獲取、與其他理論的結合以及應用等方面。比如，在三支概念格構造與模型推廣方面，Qi等[7]較為深入地分析了概念格與三支概念格之間的關系，基于此Qian 等通過形式背景的并置與疊置研究了三支概念格的構造方法[8]，并提出了對象誘導的三支面向?qū)ο蟾拍罡窈蛯傩哉T導的三支面向?qū)傩愿拍罡竦亩x，詳細分析了這四種三支概念格之間的關系[9-10]。Yu等[11]討論了三支概念格的一些特殊性質(zhì)，并建立了某些特殊完備格和三支概念格之間的同構映射。Yao[12]討論了不完備背景上的三支概念。Li 等[13]基于粗糙集上、下近似的思想，在不完備背景上提出了三支近似概念。

在屬性約簡方面，Ren等[14]研究了三支概念格的四種約簡，并分析了不同類型的約簡之間的關系。李美爭等[15]構造了一種對象-概念辨識矩陣，基于此研究了三支近似概念格的約簡。在規(guī)則獲取方面，Wei等[16]基于三支概念格，在三支協(xié)調(diào)的意義下研究了決策背景的規(guī)則獲取問題，并與強協(xié)調(diào)決策背景所獲得的一般決策規(guī)則進行了詳細的比較研究。此外，任睿思等[17]討論了弱協(xié)調(diào)意義下的三支規(guī)則獲取問題。

在三支概念分析理論與其他理論結合方面，Li等[18-19]提出了基于多粒度的三支認知概念學習。徐偉華等[20]討論了模糊三支概念的概念認知學習方法。龍柄翰等[21]提出了模糊三支概念分析，考慮模糊背景中“共同具有的程度”與“共同不具有的程度”兩方面不確定的共性信息?；诖耍逖诺萚22]提出了畢達哥拉斯模糊三支概念格，而Singh[23]利用中智集提出了一種新的三支模糊概念格的模型。此外，三支概念格現(xiàn)已被應用于醫(yī)療診斷[24]、認知記憶[25]以及文本分類[26]等領域。

由于在形式概念分析中，可以通過形式背景的直觀圖獲取形式概念、面向?qū)ο蟾拍詈兔嫦驅(qū)傩愿拍?，也可以用于判別屬性特征[27-28]，而四種三支概念又可以通過特殊的形式背景（形式背景與其補背景的疊置和并置）的形式概念進行一定的轉(zhuǎn)化而得到[8-10]。因此，很自然的一個想法就是，通過這類特殊形式背景的直觀圖研究四種三支概念的獲取方法及相應的三支概念格的約簡。

于是，本文的主要目的就是結合三支思想提出形式背景的另外兩種新的直觀圖，并基于此研究三支概念的獲取方法以及三支概念格的屬性特征分析。首先，從屬性集出發(fā)，給出形式背景的屬性混合直觀圖和屬性對誘導的三支直觀圖的定義，以此為基礎研究對象誘導的三支概念和對象誘導的三支面向?qū)ο蟾拍畹墨@取方法；其次，對偶地，從對象集出發(fā)，提出對象混合直觀圖和對象對誘導的三支直觀圖的定義，給出屬性誘導的三支概念和屬性誘導的三支面向?qū)傩愿拍畹墨@取方法；最后，對于格約簡和屬性特征分類給出一般化的定義，并針對對象誘導的三支概念格，基于差別矩陣對其屬性特征進行分析，給出相應的判別定理，進而通過屬性對誘導的三支直觀圖得到屬性特征的判別方法。

1 預備知識

本章主要介紹直觀圖和三支概念分析的相關概念。

1.1 形式背景及直觀圖的基礎知識

定義1[1]稱(G,M,I)為一個形式背景，其中G={x1,x2,…,xp}為對象集，每個xi(i≤p)稱為一個對象；M={a1,a2,…,aq}為屬性集，每個aj(j≤q)稱為一個屬性；I為G和M之間的二元關系，I?G×M。若(x,a)∈I，則表示對象x具有屬性a，記為xIa。

注1本文所研究的形式背景是有限的且是正則的。

對于形式背景K=(G,M,I)，Wille 在對象子集X?G和屬性子集A?M上定義兩個導出算子，具體定義如下：

特別地，對任意的x∈G,a∈M，記{x}*為x*，{a}*為a*。

若滿足X*=A且A*=X，則稱(X,A)是一個形式概念，簡稱概念；其中，稱X為概念的外延，A為其內(nèi)涵。用L(K)表示所有概念的集合，記

則“≤”是L(K)上的偏序關系。對于任意兩個概念，定義下確界和上確界，如下：

從而(L(K),≤)形成了完備格，稱為概念格，并簡記為L(K)。記所有概念的外延的集合和內(nèi)涵的集合分別為LG(K)和LM(K)。

對于L(K)中的任意兩個概念(X1,A1),(X2,A2)，若(X1,A1)≤(X2,A2)，且不存在(X,A)∈L(K)，有(X,A)≠(X1,A1),(X,A)≠(X2,A2)，使得(X1,A1)≤(X,A)≤(X2,A2)，則稱(X2,A2)是(X1,A1)的父概念，(X1,A1)是(X2,A2)的子概念，并記為(X1,A1)?(X2,A2)。

另外，對任意的X?G和A?M，一對近似算子□和 ?定義如下：

類似于概念和概念格的形成過程，Gediga 和Duntsch以及Yao分別提出了面向?qū)傩愿拍罡馤P(K)和面向?qū)ο蟾拍罡馤O(K)，更多的關于這兩類概念格的詳細內(nèi)容及相關性質(zhì)可參考文獻[3-4]，此處不再贅述。

下面給出形式背景K=(G,M,I)對象/屬性直觀圖的定義。

注2在形式背景中，用[x]表示對象x的等價類，[a]表示屬性a的等價類。在文獻[27]中，因為所研究形式背景是凈化背景，故對象/屬性等價類均為單點集，因此將[x]簡記為x，[a]簡記為a。

例1[14]表1 為形式背景K=(G,M,I)，它的對象直觀圖和屬性直觀圖分別如圖1和圖2所示。

表1 形式背景K=(G,M,I)Table 1 Formal context K=(G,M,I)

圖1 對象直觀圖Fig.1 Object pictorial diagram

圖2 屬性直觀圖Fig.2 Property pictorial diagram

表2為形式背景K=(G,M,I)的補背景。

表2 表1的補背景Table 2 Complementary context of table 1

表3 I型混合背景Table 3 Type I-combinatorial context

表4 II型混合背景Table 4 Type II-combinatorial context

1.2 三支概念格的基礎知識

本節(jié)首先對任意非空有限集合冪集的笛卡爾積上的運算進行回顧。

令S是一個非空有限集，P(S)是其冪集，DP(S)=P(S)×P(S)。則DP(S)是布爾代數(shù)，其上的交、并、補等運算可以通過標準的集合運算來定義。也就是說，任意的(A,B),(C,D)∈DP(S)，那么：

事實上，形式背景中的負算子ˉ*是其補背景上的概念導出算子*。

2016 年Qi 等通過結合正算子和負算子，在形式背景中提出了兩種三支算子：OE 算子和AE 算子。下面給出這兩個算子的相關知識的介紹。

當X?=(A,B)且(A,B)?=X時，稱(X,(A,B))為對象誘導的三支概念，簡稱為OE 概念。其中，稱X為OE 概念的外延，(A,B) 為其內(nèi)涵。用OEL(K) 表示K=(G,M,I)中所有OE概念的集合，并記所有OE概念的外延的集合和內(nèi)涵的集合分別為OELG(K) 和OELM(K)。

當 (X,Y)?=A且A?=(X,Y)時，稱((X,Y),A)為屬性誘導的三支概念，簡稱為AE概念。其中，稱(X,Y)為AE 概念的外延，A為其內(nèi)涵。用AEL(K)表示所有AE 概念的集合，記所有AE 概念的外延的集合和內(nèi)涵的集合分別為AELG(K)和AELM(K)。

對于OEL(K)和AEL(K)，類似于概念格的形成過程，通過定義偏序關系“≤”以及上確界“∨”、下確界“∧”運算，可得（OEL(K)，≤）和（AEL(K)，≤）也形成了完備格，分別稱為對象誘導的三支概念格和屬性誘導的三支概念格，并依次簡記為OEL(K)和AEL(K)。

類似于形式背景中負算子ˉ*的定義，對任意X?G和A?M，定義□和?的負算子分別為：

基于此，Qian等提出了另外兩種三支算子：OEO算子和AEP算子。

類似于面向?qū)ο蟾拍罡窈兔嫦驅(qū)傩愿拍罡瘢琎ian等進而提出了對象誘導的三支面向?qū)ο蟾拍罡馩EOL(K)和屬性誘導的三支面向?qū)傩愿拍罡馎EPL(K)。記所有對象誘導的三支面向?qū)ο螅▽傩裕└拍畹耐庋拥募虾蛢?nèi)涵的集合分別為OEOLG(K)和OEOLM(K)(AEPLG(K)和AEPLM(K))。關于這兩種三支概念格的更多詳細的內(nèi)容可參考文獻[9]。

對于對象誘導的三支概念格OEL(K)、屬性誘導的三支概念格AEL(K)、對象誘導的三支面向?qū)ο蟾拍罡馩EOL(K)和屬性誘導的三支面向?qū)傩愿拍罡馎EPL(K)，這四種三支概念格中父子概念的定義與經(jīng)典概念格中的完全一致。另外，這四種三支概念格與I 型和II 型混合背景的三種概念格之間具有如下的關系。

引理1[10]設K=(G,M,I)是形式背景，分別是該形式背景的I 型混合背景和II 型混合背景。則有：

引理1 揭示了形式背景的這四種三支概念格與經(jīng)典概念格、面向?qū)ο螅▽傩裕└拍罡裰g的內(nèi)在關聯(lián)性，進一步由引理1可以得到如下結論。

推論1設K=(G,M,I)是形式背景。對任意x∈G和a∈M，則有下列結論成立。

類似地，也可證得（2）、（3）和（4）是成立的。

例2（續(xù)例1）對于表1的形式背景，它的四種三支概念格分別如圖3～圖6所示。

圖3 表1的OEL(K)Fig.3 OEL(K)of table 1

圖4 表1的AEL(K)Fig.4 AEL(K)of table1

圖5 表1的OEOL(K)Fig.5 OEOL(K)of table 1

圖6 表1的AEPL(K)Fig.6 AEPL(K)of table 1

2 OE概念和OEO概念的獲取方法

在形式背景中，經(jīng)典概念和面向?qū)ο蟾拍罹赏ㄟ^形式背景的屬性直觀圖來獲取，具體的方法如下。

引理2[27]設K=(G,M,I)是形式背景，(HM,≤)是該形式背景的屬性直觀圖。則有：

在引理2的基礎上，再通過概念的交、并運算，便可以獲得L(K)和LO(K)。

受引理2 的啟發(fā)，本文借助引理1 的結論，通過給定形式背景的I 型混合背景的屬性直觀圖研究對象誘導的三支概念和對象誘導的三支面向?qū)ο蟾拍畹墨@取方法。首先，給出如下的定義。

定義5設K=(G,M,I)是形式背景，是K的I型混合背景。記：

通過引理2可從(HM∪Mˉ,≤)獲取中的經(jīng)典概念和面向?qū)ο蟾拍?。于是，結合引理1，可從屬性混合直觀圖(HM∪Mˉ,≤)直接獲取K=(G,M,I)中的OE 概念和OEO概念的方法。

且可驗證這些OE概念都是(G,(?,?))的子概念。

例3（續(xù)例1）表1 所示形式背景的屬性混合直觀圖如圖7所示。

圖7 屬性混合直觀圖Fig.7 Combinatorial-property pictorial diagram

對圖7的屬性混合直觀圖(HM∪Mˉ,≤)進行屬性分離映射[·]m，所得屬性對誘導的三支直觀圖如圖8所示。

圖8 屬性對誘導的三支直觀圖Fig.8 Property pair induced three-way pictorial diagram

而(24,(c,d))∈OEOL(K)，此結果可由圖5驗證。

3 AE概念和AEP概念的獲取方法

利用形式背景中對象集與屬性集的對偶性，從對象集的角度提出了對象直觀圖，由它可以獲取形式背景的經(jīng)典概念和面向?qū)傩愿拍?。進一步，再通過概念的交、并運算，便可以獲得L(K)和LP(K)。

引理3[27]設K=(G,M,I)是形式背景，(HG,≤)是該形式背景的對象直觀圖。則有：

且可驗證這些AE概念都是((?,?),M)的父概念。

例4（續(xù)例1）表1所示形式背景的對象混合直觀圖和對象對誘導的三支直觀圖如圖9和圖10所示。

圖9 對象混合直觀圖Fig.9 Combinatorial-object pictorial diagram

圖10 對象對誘導的三支直觀圖Fig.10 Object pair induced three-way pictorial diagram

該結果可由圖6驗證((3,24),de)∈AELP(K)。

4 三支概念格的屬性特征分析

本章只討論形式背景的不同類型的概念格保持其格結構不變的約簡，簡稱為約簡。

對于形式背景K=(G,M,I)，它的任意的一類概念格記為α(G,M,I)，相應的外延集合記為αG(G,M,I)。下面給出約簡的一般化定義。

定義9設K=(G,M,I)是形式背景，α(G,M,I)是其某一類概念格。若存在屬性子集D?M，使得αG(G,D,ID)=αG(G,M,I)成立，則稱D是α(G,M,I)的協(xié)調(diào)集；如果對于任意的d∈D，都有αG(G,D-j5i0abt0b,ID-j5i0abt0b)≠αG(G,M,I)，則稱D是α(G,M,I)的約簡。

本文僅限定α的取值為{K,OE,AE,OEO,AEP}，依次代表經(jīng)典概念格L(K)、對象誘導的三支概念格OEL(K)、屬性誘導的三支概念格AEL(K)、對象誘導的三支面向?qū)ο蟾拍罡馩EOL(K)以及屬性誘導的三支面向?qū)傩愿拍罡馎EPL(K)。

屬性特征分類的一般化定義如下。

這三類屬性在構造約簡的過程中起著不同的作用。其中，每一個核心必包含于每一個約簡之中，是必不可少的；每一個絕對不必要屬性是必不包含在任意一約簡之中，是完全可以刪除的；每一個相對必要屬性是包含于部分約簡之中，類型比較特殊。

對于形式背景K=(G,M,I)的四種三支概念格，由引理1可知，AEPL(K)與AEL(K)的約簡相同，OEOL(K)與OEL(K)的約簡相同。而且，AEL(K)沒有絕對不必要屬性，若存在a*=b*(a,b∈M)，則表明屬性a和b是一類相對必要屬性[14]。因此下面只需討論OEL(K)的約簡。

差別矩陣是尋找約簡最常見的計算方法，OEL(K)的差別矩陣定義如下。

定義11[14]設K=(G,M,I)是形式背景，(X,(A,B)),(Y,(C,D))∈OEL(K)，則稱：

是對象導出三支概念(X,(A,B))與(Y,(C,D))的差別屬性集。其中，(X,(A,B))?(Y,(C,D))表示(X,(A,B))是(Y,(C,D))的子概念。

在此基礎上，稱集合：

為OEL(K)的差別矩陣。

注3因為只有差別矩陣中的非空元素對約簡有意義，所以把非空元素的集合也記為ΛOEL，兩者不加區(qū)別。此外，在具體計算時，差別集用集合的并表示，即用(A-C)∪(B-D)代替(A-C,B-D)。

因LG(K|)=OELG(K)，所以這兩種格的差別矩陣ΛOEL和ΛL(K|Kˉ)之間必存在如下的一一對應關系。

推論2設K=(G,M,I)是形式背景，[·]m為屬性分離映射。對任意的H∈ΛL(K|Kˉ),[H]m=(H1,H2),則有H1∪H2∈ΛOEL且|ΛL(K|Kˉ)|=|ΛOEL|。

在經(jīng)典概念格的約簡中，差別矩陣元素若為單點集，則其唯一的元素必為核心。這個性質(zhì)對于OEL(K)來說仍然成立，且可通過推論2得到。

定理5設K=(G,M,I) 是形式背景。對任意的a∈M，a∈COE??(X,(A,B)),(Y,(C,D))∈OEL(K),使 得DISOEL((X,(A,B)),(Y,(C,D)))={a}。

由此，可以通過OEL(K)的差別矩陣得到核心屬性的判別方法。

引理4設K=(G,M,I) 是形式背景，(X,(A,B))∈OEL(K)，且(X,(A,B))是(G,(?,?))的子概念。則?a∈A,b∈B,總有a*∩b*ˉ=X。

證明若|A|=1,|B|=0 或|B|=1,|A|=0，則根據(jù)OE概念的定義可知該結論顯然成立。即當|A∪B|=1時，結論成立。

當|A∪B|≥2 時，分為以下三種情況進行證明。

綜合上述分析，可證原命題成立。

通過引理4可以得到下述判斷OEL(K)的核心和相對必要屬性的方法。

定理6設K=(G,M,I) 是形式背景，(X,(A,B))∈OEL(K)，且(X,(A,B))是(G,(?,?))的子概念。則以下命題成立：

（1）若|A∪B|=1，則A∪B中元素是核心。

（2）若|A∪B|≥2，則A∪B中元素是相對必要屬性。

證明（1）由于|A∪B|=1，DISOEL((X,(A,B)),(G,(?,?)))=A∪B是單點集。根據(jù)定理5 可知，A∪B中元素是核心。

（2）若|A∪B|≥2，則由定理5 可知A∪B中元素一定不是核心。以下分三種情況進行說明。

①對于|A|≥2,|B|=0 的情況，根據(jù)引理4 可知，?a∈A,都有a*=X。因此，A中屬性屬于同一等價類；且A中屬性要么同時屬于、要么同時不屬于某個概念內(nèi)涵的第一部分。又因M-A不是協(xié)調(diào)集，于是A中屬性屬于某個約簡。因此A中屬性是相對必要屬性且屬于同一類相對必要屬性。

②對于|A|=0,|B|≥2 的情況，與|A|≥2,|B|=0 的證明類似，可得B中屬性是相對必要屬性且屬于同一類相對必要屬性。

③對于|A|≥1,|B|≥1的情況，設A={a,c}，B={b,d}，則由引理4 的證明過程（3）的方法可以證得a*∩c*=b*ˉ∩d*ˉ=X。又進一步由引理4 的證明過程（1）的方法可證a*=c*=b*ˉ=d*ˉ=X。又因M-A∪B肯定不是協(xié)調(diào)集，所以A∪B中屬性是相對必要屬性且屬于同一類相對必要屬性。

由定理6可得相對必要屬性具有下述特點。

推論3設K=(G,M,I) 是形式背景。對任意的a∈M,若a∈KOE，則一定存在b∈M,b≠a，滿足a*=b*或者a*=b*ˉ。

下面通過屬性對誘導的三支直觀圖將定理6 的結論敘述如下。

從而，根據(jù)定理7 可以得到OEL(K)和OEOL(K)的核心屬性是e，相對必要屬性為a、b、c、d，其中a*=b*,d*=c*ˉ,故a、b屬于同一類相對必要屬性，c、d屬于另一類相對必要屬性。故由此可驗證定理7的結論。

5 結束語

本文利用形式背景的直觀圖與概念、面向?qū)ο蟾拍詈兔嫦驅(qū)傩愿拍钪g的關系，以及四種三支概念與兩類混合背景的概念之間的關聯(lián)性，基于形式背景的混合直觀圖和三支直觀圖，提出了獲取四種三支概念的方法；通過差別矩陣給出了OEL(K)屬性特征的判別方法，并基于此得到了由屬性對誘導的三支直觀圖判別屬性特征的方法。后續(xù)將進一步借助屬性混合直觀圖研究三支意義下的決策形式背景的協(xié)調(diào)性的判別方法以及三支規(guī)則的獲取問題。