面向?qū)傩裕▽ο螅┒嗔６雀拍罡裰g的關系*

楊 涵，秦克云

西南交通大學 數(shù)學學院，成都610000

1 引言

1982年，德國數(shù)學家Wille 提出了形式概念分析理論[1]（formal concept analysis，F(xiàn)CA），也稱概念格理論。該理論是根據(jù)數(shù)據(jù)集中對象與屬性之間的二元關系建立的一種概念層次結構，它反映了形式概念之間的泛化和專業(yè)化的關系。作為知識描述和總結的有用工具，概念格理論已廣泛應用于知識工程、機器學習、模式識別、專家系統(tǒng)、決策分析、數(shù)據(jù)挖掘等領域。

面向?qū)傩缘母拍詈兔嫦驅(qū)ο蟮母拍钍切问礁拍畹膬蓚€重要擴展。在Wille 概念格的基礎上，Duntsch和Gediga[2]引入了一對近似模態(tài)算子構造了面向?qū)傩缘母拍罡?。它提供了關于經(jīng)典形式概念分析的推導算子的補充數(shù)據(jù)視圖。Yao[3-4]介紹了面向?qū)ο蟾拍罡竦母拍?，并比較了不同概念格在數(shù)據(jù)分析中的作用。Wan 等[5]提出了一些基于屬性集和對象集的近似概念獲取方法。還討論了近似概念、屬性導向概念和面向?qū)ο蟾拍钪g的關系。此外，近年來已經(jīng)提出了一些測量模糊形式概念之間相似程度的相似性[6-8]。這些相似性度量可用于分解相關的概念格，并構建因子格[9-10]。此外，已經(jīng)做了許多努力來比較和組合形式概念分析和粗糙集理論。指出形式概念分析的推導算子是極性或模態(tài)邏輯中使用的充分運算符，粗糙集近似算子[11]實際上是模態(tài)邏輯中運算符的必要性和可能性[2-3]。因此，形式概念分析側重于可以通過屬性的連接來定義的概念，而粗糙集理論則側重于可以通過屬性的分離來定義的概念[3,12]。它們?yōu)閿?shù)據(jù)分析提供相關和互補的方法。模態(tài)式算子的表述使能夠更深入地了解粗糙集和形式概念分析的理論。

最近，受粗糙集中多粒度標記信息系統(tǒng)研究的啟發(fā)[13-15]，多粒度計算越來越受到研究人員的關注。Qian 等[16]考慮了多個二元關系并提出了多粒度粗糙集模型MGRS（multi-granulation rough sets），其中目標概念被描述為一個整體上的多個二元關系。另外有人提出了MGRS 的一些擴展[17-18]。Li等[19]通過規(guī)則獲取研究了多粒度粗糙集與概念格之間的關系，指出悲觀多粒度粗糙集中的“AND”決策規(guī)則是概念格中的粒度規(guī)則。概念格中的非冗余析取規(guī)則是樂觀多粒度粗糙集中“OR”決策規(guī)則的真實部分的多重組合。郝晨等[20]考慮了包含一個屬性的多粒度標記形式背景。Xie 等[21]把多粒度標記信息系統(tǒng)直接理解成多粒度標記多值形式背景，在此基礎上討論了關聯(lián)規(guī)則挖掘問題。李金海等[22]提出了形式概念分析的多粒度標記理論，通過正向尺度化和反向尺度化方法，研究信息系統(tǒng)與形式背景之間的相互轉(zhuǎn)化關系，利用經(jīng)典形式背景給出多粒度標記形式背景的定義，證明多粒度標記形式背景與多粒度標記信息系統(tǒng)在語義上等價。對于多粒度標記形式背景，不同粒度標記下的蘊涵規(guī)則之間可以相互推理。

本文基于多粒度形式背景，討論了不同粒度下的極值算子之間的關系，以此研究了不同粒度的面向?qū)傩缘母拍罡裰g的關系，并提出了相關概念格的生成方法。再利用面向?qū)傩缘母拍罡窈兔嫦驅(qū)ο蟮母拍罡裰g的互補關系，得到了不同粒度的面向?qū)ο蟮母拍罡裰g的關系。

2 預備知識

本章回顧形式概念分析中的一些基本概念和性質(zhì)。

定義1[1]一個形式背景是一個三元組(G,M,I)，其中G={g1,g2,…,gn}為對象集，M={m1,m2,…,ml}為屬性集，I為G和M之間的二元關系，I?G×M。若(g,m)∈I，則表示對象g具有屬性m，或者屬性m由對象g擁有，記具有m的所有對象組成的集合為Im。

對于形式背景(G,M,I)，在對象集X?G和屬性集A?M上分別定義運算：

也就是說，X↑是X中所有對象擁有的最大屬性集，A↓是A中具有所有屬性的最大對象集。若X↑=A且A↓=X，則稱二元組(X,A)為一個形式概念（簡稱概念），其中X稱為形式概念的外延，A稱為形式概念的內(nèi)涵。(G,M,I)中的所有形式概念組成的集合構成一個格，稱為概念格，記作L(G,M,I)，它的上下確界和序關系為：

為了方便起見，對?g∈G，m∈M，{g}↑記為g↑，{m}↓記為m↓。(g↑↓,g↑)和(m↓,m↓↑)可以表示所有的形式概念。

定理1[1]?X,X1,X2?G,A,A1,A2?M，有：

定義2[2](G,M,I)是形式背景，對?X?G，A?M，Duntsch 和Gediga 曾定義一對模態(tài)算子?和□：

顯然，X?={m∈M;m↓?X≠?}，A□={g∈G;g↑?A}。對X?G和A?M，若X?=A且A□=X，則稱二元組(X,A)為一個面向?qū)傩缘母拍睢?G,M,I)中的所有面向?qū)傩缘母拍罱M成的集合構成一個完備格，稱為面向?qū)傩缘母拍罡?，記作LP(G,M,I)，它的上下確界和序關系為：

對?X?G和A?M，(X?□,X?)和(A□,A□?)都是面向?qū)傩陨傻母拍睢?/p>

定理2[2]?X,X1,X2?G,A,A1,A2?M，有：

Yao 通過粗糙集理論和形式概念分析的一些比較，研究了粗糙集模型中的概念格結構和形式背景中的粗糙近似，提出了面向?qū)ο蟾拍罡竦母拍睢?/p>

定義3[3-4](G,M,I)是形式背景，對?X?G，A?M，考慮以下算子：

顯然，X□={m∈M;m↓?X}，A?={g∈G;g↑?A≠?}。對X?G和A?M，若X□=A且A?=X，則稱二元組(X,A)為一個面向?qū)ο蟮母拍睢?G,M,I)中的所有面向?qū)ο蟮母拍罱M成的集合構成一個完備格，稱為面向?qū)ο蟮母拍罡瘢涀鱈O(G,M,I)，它的上下確界和序關系為：

對?X?G和A?M，(X□?,X□)和(A?,A?□)都是面向?qū)ο笊傻母拍睢?/p>

定理3[3-4]?X,X1,X2?G,A,A1,A2?M，有：

李金海受粗糙集中多粒度標記信息系統(tǒng)研究的啟發(fā)，基于經(jīng)典形式背景給出了多粒度標記形式背景的形式化定義。

定義4[19]對于形式背景(G,M,I)，假設a∈M所具有的對象集為Ia。若A?M的任意兩個屬性a、b所具有的對象集滿足Ia?Ib=?且則稱A為(G,M,I)的對象劃分集。

定義5[19]設(G,A1,I1) 和(G,A2,I2) 為兩個形式背景。假設a∈A1所具有的對象集為Ia，稱Bin(Ia)為集合Ia的布爾向量表示。對于?b∈A2，如果存在at∈A1（t∈Tb，Tb是指標集）使得則稱b是{at|t∈Tb}的融合屬性。

例1[19]表1 是一個形式背景(G,A1,I1)，其中G={x1,x2,x3,x4,x5,x6},A1={a1,a2,a3,a4,a5,a6}。表2 是一個形式背景(G,A2,I2)，其中G={x1,x2,x3,x4,x5,x6},A2={b1,b2,b3,b4}。

Table 1 Formal context (G,A1,I1)表1 形式背景(G,A1,I1)

可計算得Ia1={x4,x5,x6}，那么集合Ia1的布爾向量為Bin(I1a1)=(0,0,0,1,1,1)。且由表1和表2易計算得：

Table 2 Formal context (G,A2,I2)表2 形式背景(G,A2,I2)

定義6[19]設(G,A1,I1) 和(G,A2,I2) 為兩個形式背景。對于?b∈A2，如果存在at∈A1（t∈Tb，Tb是指標集）使得b是{at|t∈Tb}的融合屬性，且A1中的每個屬性均被用來融合A2中的某一屬性，則稱(G,A2,I2)是(G,A1,I1)的融合形式背景，記為(G,A1,I1)?(G,A2,I2)。

直觀地，(G,A1,I1)?(G,A2,I2)表示(G,A2,I2)的每一列均通過合并(G,A1,I1)的若干列得到，這種合并關系在實際中必須借助特定的屬性語義完成。

3 不同粒度形成的面向?qū)傩愿拍罡裰g的關系

設(G,A1,I1) 和(G,A2,I2) 為兩個形式背景，且(G,A1,I1)?(G,A2,I2)，本章將討論概念格LP(G,A1,I1) 和LP(G,A2,I2)之間的聯(lián)系。(G,A1,I1)、(G,A2,I2)中的算子分 別為?1,□1與?2,□2，且假設b∈A2，b由Γb={at;t∈Tb}?A1融合得到，其中Tb為指標集。

定理4設(G,A1,I1)?(G,A2,I2)，對于任意的X∈G，Z?A2，則：

證明（1）假設b∈X?2，則存在x∈X使得(x,b)∈I2。由可知，存在唯一的t∈Tb使得(x,at)∈I1，從而at∈X?1?Γb，即?Γb≠?。

假設b∈A2使得X?1?Γb≠?。不妨設at∈X?1?Γb,由at∈X?1可知存在x∈X，使得(x,at)∈I1,再由可知(x,b)∈I2,從而由x∈X可知

（2）對于任意m∈X?1，因A1中任一屬性均被用來融 合A2中某一屬性，存在c∈A2使得m∈Γc。由X?1?Γc≠?及（1）可得c∈X?2，從而

（3）設x∈G使得x∈。若a∈A1滿足(x,a)∈I1，不妨設a∈Γc，則(x,c)∈I2，從而由知c∈Z,從而

定理5設(G,A1,I1)?(G,A2,I2)，對于任意的X∈G，Z?A2，則：

（1）如果(X,Z)∈LP(G,A2,I2)，則

（2）Ext(LP(G,A2,I2))?Ext(LP(G,A1,I1)),其中：

（3）定義φP:LP(G,A2,I2)→LP(G,A1,I1)為φP((X,Z))=，則φP是一個保交單射。

證明（1）由(X,Z)∈LP(G,A2,I2)，則X,則由定理4（3），可得因此(X,

（2）由（1）顯然可得。

（3）對任意(X1,Z1),(X2,Z2)∈LP(G,A2,I2)有：

由X1,X2?Ext(LP(G,A1,I1))可得：

即φP((X1,A1)∧(X2,A2))=φP((X1,A1))∧φP((X2,A2)),故φP是一個保交映射，顯然φP是單射。 □

定理6設(G,A1,I1)?(G,A2,I2)，對于任意的X∈G，Z?A2，則：

證明若?(X,Y)∈LP(G,A1,I1) 使得Z={b;Γb?Y≠?}，則由定理4（3）可得由定理4（1）可得，Z={b;Γb?Y≠?}={b;Γb?X?1≠?}=X?2，從 而

反之，對任意的(V,W)∈LP(G,A2,I2)，有V?2=W,W□2=V,于是有(V,V?1)∈LP(G,A1,I1)。令Z={b;Γb?V?1≠?}，則由定理4（1）可得Z=V?2=W，由定理4（3）可得從而結論成立。 □

推論1LP(G,A2,I2)={(X?2□2,X?2);X∈ExtLP(G,A1,I1)}。

例2參照例1 中的形式背景。

(G,A2,I2)中生成的所有面向?qū)傩陨傻母拍頛P(G,A2,I2)如下：

4 不同粒度形成的面向?qū)ο蟾拍罡裰g的關系

設(G,A1,I1)和(G,A2,I2)為兩個形式背景，且(G,A1,I1)?(G,A2,I2)，本章將討論概念格LO(G,A1,I1)和LO(G,A2,I2)之間的聯(lián)系。

定理7設(G,A1,I1)?(G,A2,I2)，對于任意的X∈G，Z?A2，則：

證明（1）設b∈A2滿足Γb?X□1。若x∈G使得(x,b)∈I2，則存在唯一t∈Tb使得(x,at)∈I1，由at∈Γb?X□1可知x∈X，從而b∈X□2。

反之，設c∈X□2。對于任意at∈Γc，t∈Tc，若x∈G使得(x,at)∈I1，則(x,c)∈I2。再由c∈X□2可得x∈X，從而at∈X□1。由at的任意性可得Γc?X□1。

（2）設x∈G滿足x∈Z?2，則存在b∈Z使得(x,b)∈I2,從而存在at∈Γb使得(x,at)∈I1

反之，設x∈G滿足于是存在b∈Z及at∈Γb，使得(x,at)∈I1，于是(x,b)∈I2。再由b∈Z可得x∈Z?2。 □

定理8若(X,Z)∈LO(G,A2,I2)，則(X,X□1)∈LO(G,A1,I1)。

證明若(X,Z)∈LO(G,A2,I2)，則由X∈Ext(LO(G,A2,I2))可得(G-X)∈Ext(LP(G,A2,I2))。再由定理5（2）可得(G-X)∈Ext(LP(G,A1,I1))，從而X∈Ext(LO(G,A1,I1))，即(X,X□1)∈LO(G,A1,I1)。 □

推論2Ext(LO(G,A2,I2))?Ext(LO(G,A1,I1)),其中：

定理9設(G,A1,I1)?(G,A2,I2)，對于任意的X∈G，Z?A2，則：

證明若

反之，對任意的(V,W)∈LO(G,A2,I2)，有V□2=W,W?2=V,于是有(V,V□1)∈LO(G,A1,I1)。令Z=X□2，則從而結論成立。 □

由定理9 可知，LO(G,A2,I2) 中的任一概念可由LO(G,A1,I1)中的某些概念的外延生成，即有：

推論3LO(G,A2,I2)={(X□2?2,X□2);X∈ExtLO(G,A1,I1)}。

例3參照例1 中的形式背景。

(G,A2,I2) 中生成的所有面向?qū)ο笊傻母拍頛O(G,A2,I2)如下：

5 結束語

本文的主要目的是提出一種研究多粒度概念格的新方法，研究了面向?qū)傩裕▽ο螅┑母拍罡裨诓煌６认轮g的關系。主要得出結論：LP(G,A2,I2)中的任一概念可由LP(G,A1,I1)中的某些概念的外延生成（LO(G,A2,I2)中的任一概念可由LO(G,A1,I1)中的某些概念的外延生成）?；谶@個結果，提供了從LP(G,A1,I1)和LO(G,A1,I1)生成面向?qū)傩缘母拍罡馤P(G,A2,I2)和面向?qū)ο蟮母拍罡馤O(G,A2,I2)的方法。基于本文的研究結果，可以進一步討論Wille 概念格在不同粒度下之間的關系。