對稱形式背景及其概念約簡

魏 玲,趙思雨,2,祁建軍

(1.西北大學 數(shù)學學院,陜西 西安 710127; 2.咸陽師范學院 數(shù)學與統(tǒng)計學院,陜西 咸陽 712000;3.新疆政法學院 信息網(wǎng)絡(luò)安全學院,新疆 圖木舒克 844000;4.西安電子科技大學 計算機科學與技術(shù)學院,陜西 西安 710071)

形式概念分析(formal concept analysis, FCA)是以形式背景為數(shù)據(jù)基礎(chǔ)的知識發(fā)現(xiàn)理論,于1982年由德國數(shù)學家Wille提出[1]。

FCA的研究主題包括概念格構(gòu)造[2-3],概念格簡化[4]、約簡[5-17]、規(guī)則獲取[18-19]、應(yīng)用[19]等。其中,約簡理論主要包括屬性約簡[5-10]及概念約簡[11-17]。屬性約簡的目標是以極小的屬性子集保持某一特性不變,如張文修[5]、魏玲[6]等研究保持概念格結(jié)構(gòu)不變的屬性約簡,此外還有保持粒[7],交、并不可約元[8-9],決策規(guī)則不變[10]的屬性約簡。概念約簡作為一個新的約簡理論,其研究目標主要集中于以極小的概念子集保持形式背景的關(guān)系不變。魏玲[11]、曹麗[12]等提出了保持二元關(guān)系不變的概念約簡(簡稱概念約簡),給出了概念約簡的計算方法,并將概念分類,研究了每類概念的概念特征。隨后,謝小賢等通過布爾矩陣運算研究了概念特征和概念約簡[13];王霞等定義了概念可辨識矩陣,并基于此矩陣給出概念約簡求解方法[14];馬文勝等提出了同效關(guān)系,并給出由同效關(guān)系子集補集的概念格來得到概念約簡的新算法[15];Zhao等定義了代表概念矩陣,并給出了一種直觀的尋找概念約簡的方法[16];李俊余等提出了三元背景中保留所有三元關(guān)系的三元概念約簡[17]。

形式背景是FCA的研究起點,關(guān)于形式背景變化的研究是FCA的研究熱點。決策形式背景在形式背景的基礎(chǔ)上加入了決策屬性,魏玲等針對決策形式背景定義了背景的協(xié)調(diào)性并討論了屬性約簡[6],隨后研究了決策形式背景的規(guī)則提取[18]。由于不確定數(shù)據(jù)的廣泛存在性和不可避免性,許多學者也探索了不完備背景[20],模糊背景[21],區(qū)間值背景[22]等不確定性背景的理論研究及實際應(yīng)用。此外,FCA與沖突分析、社交網(wǎng)絡(luò)等領(lǐng)域結(jié)合,可用于解決各自領(lǐng)域的基本問題,而連接不同領(lǐng)域的基石與橋梁恰為形式背景。王藝超等在沖突分析中利用代理人之間的復(fù)合沖突程度定義了聯(lián)盟形式背景,并利用聯(lián)盟形式背景獲取了極大聯(lián)盟[23];Hao等將社交網(wǎng)絡(luò)轉(zhuǎn)化為基于修正鄰接矩陣的形式背景,并利用該形式背景上的k-等勢概念探測了社交網(wǎng)絡(luò)中的k-團[24]。

通過觀察發(fā)現(xiàn),聯(lián)盟形式背景及基于修正鄰接矩陣的形式背景可一般化為一類特殊的形式背景,本文稱其為對稱形式背景。事實上,在任何團體中,若團體內(nèi)部關(guān)系具有自反性和對稱性的特點,則該關(guān)系可以表示于對稱形式背景中。因此,對稱形式背景在FCA中占據(jù)著重要的地位,有必要對對稱形式背景及其性質(zhì)展開研究。另外,作為特殊的形式背景,對稱形式背景的概念約簡也具有特殊性,因此,本文亦探討了對稱形式背景的概念約簡。

本文首先定義了對稱形式背景并討論了其性質(zhì);其次,研究了對稱形式背景上由對稱概念構(gòu)成的概念約簡;最后,給出了對稱形式背景及其概念格在沖突分析、社交網(wǎng)絡(luò)等領(lǐng)域的實際應(yīng)用。

1 FCA基礎(chǔ)知識

定義1[1]稱三元組(G,M,I)為形式背景。其中:G={x1,x2,…,xn}為對象集,xi(i≤n)稱為對象;M={a1,a2,…,am}為屬性集,aj(j≤m)稱為屬性;I?G×M為G與M之間的二元關(guān)系。對于任意的x∈G及a∈M,若(x,a)∈I,稱對象x具有屬性a或?qū)傩詀被對象x具有,記為xIa;若(x,a)?I,稱對象x不具有屬性a或?qū)傩詀不被對象x具有,記為xIca。

對于任意的對象子集X?G,屬性子集A?M,引入記號

XIA??x∈X,a∈A,s.t.xIa;

XIcA??x∈X,a∈A,s.t.xIca。

設(shè)(G,M,I)為形式背景,在對象子集X?G和屬性子集A?M上定義一對對偶算子

X*={a∈M|?x∈X,xIa},

A*={x∈G|?a∈A,xIa}。

對偶算子的相關(guān)性質(zhì)見文獻[1]。特別地,對于任意的對象x∈G,屬性a∈M,記{x}*為x*,{a}*為a*。

定義2[1]設(shè)(G,M,I)為形式背景,X?G,A?M。如果一個二元對(X,A)滿足X*=A且A*=X,則稱(X,A)是一個形式概念,簡稱概念。其中:X為概念的外延;A為概念的內(nèi)涵。

在形式背景中,對任意的對象x∈G,屬性a∈M,(x**,x*)和(a*,a**)也是概念,分別被稱為對象概念及屬性概念。

用L(G,M,I)表示形式背景(G,M,I)的全體概念,對于任意的(X1,A1),(X2,A2)∈L(G,M,I),定義偏序關(guān)系

(X1,A1)≤(X2,A2)?X1?X2(?A2?A1)則L(G,M,I)形成一個完備格,稱為概念格。其中上、下確界為

(X1,A1)∨(X2,A2)=((X1∪X2)**,A1∩A2),

(X1,A1)∧(X2,A2)=(X1∩X2,(A1∪A2)**)。

設(shè)L為格,x∈L,若x≠∨{l∈L|l

本文記概念格L(G,M,I)中對象概念的全體為O(L),屬性概念的全體為A(L),并不可約概念的全體為J(L),交不可約概念的全體為M(L)。

例1表1是一個形式背景(G,M,I)。其中:對象集G={1,2,3,4};屬性集M={a,b,c,d,e}。如果對象具有屬性,則在對象行與屬性列的交叉處用1標記,否則用0標記。

表1 形式背景(G,M,I)Tab.1 A formal context (G,M,I)

形式背景(G,M,I)對應(yīng)的概念格L(G,M,I)如圖1所示,4種概念集合分別為

圖1 概念格L(G,M,I)Fig.1 A concept lattice L(G,M,I)

O(L)={(1,abde),(24,abc),(13,d)},

A(L)={(124,ab),(24,abc),(13,d),

(1,abde)},

J(L)={(1,abde),(24,abc),(13,d)},

M(L)={(124,ab),(24,abc),(13,d)}。

2 對稱形式背景及其性質(zhì)

王藝超等[23]和Hao等[24]分別將FCA與沖突分析、社交網(wǎng)絡(luò)相結(jié)合,研究了相關(guān)領(lǐng)域的基本問題。由于連接這些不同理論的橋梁是一類特殊的形式背景,稱其為對稱形式背景,并研究其性質(zhì)。

定義3設(shè)(G,M,I)為形式背景。其中:G={x1,x2,…,xn};M={a1,a2,…,am}。若n=m且對于任意的xi,xj∈G,ai,aj∈M,1≤i,j≤n,滿足i=j時,xiIaj;i≠j時,xiIaj?xjIai,則稱(G,M,I)為對稱形式背景。

事實上,對稱形式背景可以看作是一個對稱矩陣。不失一般性,本文在后續(xù)研究中把對稱形式背景的對象集和屬性集看作相同的集合,并記對稱形式背景為(G,G,I),其中G={x1,x2,…,xn}。

例2表2是一個對稱形式背景(G,G,I)。其中,G={1,2,3,4,5,6}。圖2為相應(yīng)的概念格L(G,G,I)。其中:

圖2 對稱形式背景(G,G,I)的概念格L(G,G,I)Fig.2 The concept lattice L(G,G,I) of a symmetric formal context (G,G,I)

表2 對稱形式背景(G,G,I)Tab.2 A symmetric formal context (G,G,I)

O(L)=J(L)={(16,1246),(2,1256),(346,346),(46,1346),(25,25),(6,12346)};

A(L)=M(L)={(1246,16),(1256,2),(346,346),(1346,46),(25,25),(12346,6)}。

下面探討對稱形式背景的概念格的特征。

定理1設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格,對于任意的(X,Y)∈L(G,G,I),都有(Y,X)∈L(G,G,I)。

證明對于任意的(X,Y)∈L(G,G,I),有Y=X*,X=Y*,Y?G,X?G,故(Y,X)∈L(G,G,I)。

定理1表明對稱形式背景的概念格中任意一個概念都存在與其自身外延和內(nèi)涵互換的概念。

本文將對稱形式背景(G,G,I)的概念格L(G,G,I)稱為對稱概念格。圖2就是對稱概念格的一個例子。

下面探究對稱形式背景的對象概念、屬性概念、并不可約概念、交不可約概念等概念的特征。

定理2設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格,則(X,Y)∈O(L)?(Y,X)∈A(L)。

定理2表明對稱形式背景中對象概念和屬性概念一一對應(yīng),并且有對應(yīng)關(guān)系的對象概念和屬性概念的外延和內(nèi)涵互換。

定理3設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格,則(X,Y)∈J(L)?(Y,X)∈M(L)。

證明必要性。設(shè)(X,Y)∈J(L),即(X,Y)≠(H,M),其中(H,M)=∨{(P,Q)∈L(G,G,I)|(P,Q)<(X,Y)}。因為(H,M)≤(X,Y),所以(X,Y)≤/(H,M),即XH且MY。對于任意的(P,Q)∈{(P,Q)∈L(G,G,I)|(P,Q)<(X,Y)},P?X,Y?Q且由定理1知(Y,X),(Q,P)∈L(G,G,I),故(Y,X)<(Q,P),則∧{(Q,P)∈L(G,G,I)|(Y,X)<(Q,P)}=(M,H)。由于(M,H)≤/(Y,X),所以(Y,X)≠(M,H),故(Y,X)∈M(L)。充分性類似可證。

定理3表明對稱形式背景中并不可約概念和交不可約概念一一對應(yīng),并且有對應(yīng)關(guān)系的并不可約概念和交不可約概念的外延和內(nèi)涵互換。

定理4設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格。下列結(jié)論成立:

1) 若(X,Y)∈O(L),則X?Y;

2) 若(X,Y)∈A(L),則Y?X。

定理4表明對稱形式背景中對象概念的外延包含于內(nèi)涵,屬性概念的內(nèi)涵包含于外延。又由J(L)?O(L),M(L)?A(L)[1],易得如下推論。

推論1設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格。下列結(jié)論成立:

1) 若(X,Y)∈J(L),則X?Y;

2) 若(X,Y)∈M(L),則Y?X。

推論1表明對稱形式背景中并不可約概念的外延包含于內(nèi)涵,交不可約概念的內(nèi)涵包含于外延。

顯然,若一個概念同時是對象概念和屬性概念,或同時是并不可約概念和交不可約概念,則其外延一定等于內(nèi)涵,相關(guān)結(jié)論見推論2。

推論2設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格。下列結(jié)論成立:

1) 若(X,Y)∈O(L)∩A(L),則X=Y;

2) 若(X,Y)∈J(L)∩M(L),則X=Y。

注:定理4、推論1及推論2的逆命題不成立,可由例2中(126,126)∈L(G,G,I)驗證。

外延和內(nèi)涵相等的概念在對稱形式背景的相關(guān)知識發(fā)現(xiàn)中有重要作用。本文將此類概念定義為對稱概念,并在后文中研究由對稱概念構(gòu)造的概念約簡及其相關(guān)性質(zhì)。

定義4設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格,(X,Y)∈L(G,G,I)。若X=Y,稱(X,Y)為對稱概念。

記對稱概念集為SC,即SC={(X,Y)∈L(G,G,I)|X=Y}。

例3(續(xù)例2)對稱概念格L(G,G,I)的對稱概念集SC={(25,25),(126,126),(146,146),(346,346)}。

3 對稱概念構(gòu)造的概念約簡

魏玲[11]、曹麗[12]等提出的概念約簡指保持形式背景二元關(guān)系不變的極小概念集。對稱概念作為對稱形式背景中的特殊概念,與概念約簡有密切的聯(lián)系。本節(jié)研究對稱形式背景上由對稱概念構(gòu)造的概念約簡及其相關(guān)性質(zhì)。

對稱形式背景是特殊的形式背景,利用代表概念矩陣[16]可以求解對稱形式背景的所有概念約簡。而其中存在一類特殊的概念約簡,即對稱概念集SC。下面對以上事實展開證明,即對稱概念集是對稱形式背景的一個概念約簡。

首先,任意對稱形式背景中一定存在對稱概念。

定理5設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格。SC={(X,Y)∈L(G,G,I)|X=Y},則SC≠?。

證明對于任意的xi∈G,由背景對稱知xiIxi。考慮{xi},若對于任意的xj∈G(i≠j)滿足xiIcxj,由背景對稱知xjIcxi,故({xi},{xi})∈L(G,G,I);若存在xj∈G(i≠j)滿足xiIxj,由背景對稱知xjIxi,xiIxi,xjIxj,即{xi,xj}I{xi,xj},則考慮{xi,xj}。重復(fù)以上過程,由G是有限集知一定存在(X,X)∈L(G,G,I),即SC≠?。

其次,定理6證明了對稱概念集是一個概念約簡。

定理6設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格。SC={(X,Y)∈L(G,G,I)|X=Y},則SC是一個概念約簡。

例4(續(xù)例2)對稱形式背景(G,G,I)有10個概念約簡,其中對稱概念集SC={(25,25),(126,126),(146,146),(346,346)}就是一個概念約簡。

作為對稱形式背景中的概念約簡,對稱概念集SC具有獨特的性質(zhì)。在討論其性質(zhì)之前,先給出對稱概念格的對稱軸的定義。

定義6設(shè)L(G,G,I)為對稱概念格,(X,Y)∈L(G,G,I)。若X?Y且Y?X,則稱(X,Y)為軸概念。進一步,稱AXIS(L)={(X,Y)∈L(G,G,I)|X?Y且Y?X}為對稱概念格L(G,G,I)的對稱軸。

由于對稱概念的外延等于內(nèi)涵,故對稱概念一定是軸概念。

性質(zhì)1設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格,則SC?AXIS(L)。

性質(zhì)1給出了一種直觀獲取對稱形式背景的一個概念約簡的方法。即首先畫出對稱概念格;其次,確定對稱概念格的對稱軸;最后,在對稱軸中找到所有的對稱概念,對稱概念的全體即為一個概念約簡。需要注意的是,軸概念不一定為對稱概念,如例5所示。

例5表3為對稱形式背景(G,G,I)。其中,G={1,2,3,4}。圖3為相應(yīng)的對稱概念格。顯然,(12,34)是一個軸概念,但(12,34)不是對稱概念。

圖3 例5的對稱概念格L(G,G,I)Fig.3 The symmetric concept lattice L(G,G,I) of example 5

表3 例5的對稱形式背景(G,G,I)

對稱概念是特殊的軸概念,滿足以下性質(zhì)。

性質(zhì)2設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格,(Z,Z)∈SC。若(X,Y)∈L(G,G,I)滿足(X,Y)≤(Z,Z),則存在(Y,X)∈L(G,G,I)使得(Z,Z)≤(Y,X);若(Z,Z)≤(X,Y),則(Y,X)≤(Z,Z)。

證明設(shè)(Z,Z)∈SC,對于任意的(X,Y)≤(Z,Z),(X,Y)∈L(G,G,I),有X?Z?Y,又由定理1知(Y,X)∈L(G,G,I),且由概念的偏序關(guān)系知(Z,Z)≤(Y,X);同理,對于任意的(Z,Z)≤(X,Y),有(Y,X)≤(Z,Z)。

下面給出核心概念集C和對稱概念集SC之間的關(guān)系。

性質(zhì)3設(shè)(G,G,I)為對稱形式背景,L(G,G,I)為其概念格,則C?SC。

性質(zhì)3顯然成立。該性質(zhì)表明對稱形式背景中若存在核心概念,則一定是對稱概念。即對稱形式背景中若存在核心知識,則一定包含于SC。在此意義下,SC是一類重要的概念約簡。

4 對稱形式背景及對稱概念格的應(yīng)用

本節(jié)從沖突分析及社交網(wǎng)絡(luò)的角度給出對稱形式背景及對稱概念格的實際應(yīng)用。

4.1 對稱形式背景在沖突分析中的應(yīng)用

沖突普遍存在于訴訟糾紛、政策制定、軍事行動等方面。在沖突中,至少有兩方(稱為代理人)在某些議題上存在爭議。而沖突分析[23, 25-28]是對沖突進行分析從而幫助決策者制定合理策略的理論。

Pawlak結(jié)合粗糙集理論首次提出了沖突分析的具體模型[25]。基于此,多位學者從不同角度或結(jié)合不同理論對沖突分析模型進行了改進或拓展[26-28]。其中,Yao結(jié)合三支決策理論給出了三支沖突分析模型[26]。三支沖突分析模型利用多值沖突表表示代理人關(guān)于議題的態(tài)度。

定義7[26]稱三元組S=(A,I,r)為多值沖突表。其中:A={x1,x2,…,xn}為代理人集,A中每個元素xj(1≤j≤n)為一個代理人;I={i1,i2,…,im}為議題集,I中的每個元素ik(1≤k≤m)為一個議題;r:A×I→[-1,+1]為映射,r(xj,ik)表示代理人xj關(guān)于議題ik的態(tài)度的取值。

例6表4為多值沖突表S=(A,I,r)。其中:A={x1,x2,x3,x4,x5,x6};I={i1,i2,i3,i4,i5};r(xj,ik)為代理人xj關(guān)于議題ik的態(tài)度的取值,如r(x1,i3)=+0.9表示代理人x1支持議題i3的程度為0.9,r(x2,i4)=-0.5表示代理人x2反對議題i4的程度為0.5。

表4 多值沖突表(A,I,r)Tab.4 A many-valued conflict situation (A,I,r)

在沖突分析中,對代理人之間沖突程度的刻畫是研究的焦點。Yao等利用距離函數(shù)定義了代理人之間的沖突程度[26],在此基礎(chǔ)上,Lang等[28]和王藝超等[23]對其進行了改進。特別地,王藝超等[23]定義的復(fù)合沖突程度同時關(guān)注兩個代理人關(guān)于議題態(tài)度取值的差別和每個代理人自身關(guān)于議題態(tài)度的取值,可以較為全面地刻畫兩個代理人之間的沖突程度。基于復(fù)合沖突程度,王藝超等研究了沖突場景中的極大聯(lián)盟,即刻畫了復(fù)合沖突程度小于等于給定閾值的極大的代理人集合,并借助形式概念分析定義了聯(lián)盟形式背景,利用聯(lián)盟形式背景中外延和內(nèi)涵相等的等聯(lián)盟概念獲取了所有的極大聯(lián)盟。

表2中對稱形式背景為(G,G,I),其中G={1,2,3,4,5,6}。令6個對象(屬性)表示6位代理人,給定議題子集,對于任意的xi,xj∈G,若代理人xi與代理人xj的復(fù)合沖突程度小于等于給定閾值,則用xiIxj表示代理人xi與代理人xj具有聯(lián)盟關(guān)系,如取議題子集J={i2,i3},閾值(α,β)=(0.4,0.3),表4對應(yīng)的聯(lián)盟形式背景同表2。由此可得本文定義的對稱形式背景直接對應(yīng)沖突分析中的聯(lián)盟形式背景[23]。進一步,對稱概念對應(yīng)等聯(lián)盟概念,對稱概念集SC對應(yīng)等聯(lián)盟概念集,對稱概念的外延(或內(nèi)涵)對應(yīng)極大聯(lián)盟。

因此,在沖突分析中對稱形式背景及對稱概念格可被用于獲取代理人的極大聯(lián)盟。

4.2 對稱形式背景在社交網(wǎng)絡(luò)中的應(yīng)用

社交網(wǎng)絡(luò)[24, 29-30]是由許多節(jié)點構(gòu)成的一種社會結(jié)構(gòu),節(jié)點通常指用戶,而用戶之間有著各種社會關(guān)系。社交網(wǎng)絡(luò)可表示為包含節(jié)點和邊的圖,其中節(jié)點表示用戶,節(jié)點之間有邊相連表示用戶之間有關(guān),如圖4所示。

圖4 社交網(wǎng)絡(luò)Fig.4 Social network

在社交網(wǎng)絡(luò)中,用戶通常因為共同的興趣和目的聚集在幾個社區(qū)中,并進行大量的社交互動。因此,社區(qū)檢測是社交網(wǎng)絡(luò)中的一項重要研究內(nèi)容。Tang等將社交網(wǎng)絡(luò)與FCA相結(jié)合,提出了一種化學結(jié)構(gòu)檢索方法[29]。Hao等給出了利用FCA進行k-團(k-clique)檢測的算法[24]。具體地,Hao等首先定義了修正鄰接矩陣以建立形式背景[24]。圖4所對應(yīng)的形式背景同表2,其中,6個對象(或?qū)傩?表示6個節(jié)點,對于任意的xi,xj∈G,xiIxj表示節(jié)點xi與xj之間有邊。因此,對稱形式背景的二元關(guān)系I直接對應(yīng)社交網(wǎng)絡(luò)中的修正鄰接矩陣。

此外,Hao等稱修正鄰接矩陣形成的形式背景中外延等于內(nèi)涵的概念為等勢概念(equiconcept),進一步,若等勢概念的外延(或內(nèi)涵)的模為k,則稱為k-等勢概念, (k-equiconcept)。 并證明了k-等勢概念的外延(或內(nèi)涵)為k-團, 如圖5所示, 同一個橢圓虛線內(nèi)的節(jié)點構(gòu)成一個k-團, 圖5中有3個3-團, 1個2-團。 由此, 對稱概念對應(yīng)等勢概念, 對稱概念集SC對應(yīng)等勢概念集, 外延(或內(nèi)涵)的模為k的對稱概念的外延(或內(nèi)涵)對應(yīng)k-團。

因此,在社交網(wǎng)絡(luò)中對稱形式背景及對稱概念格可應(yīng)用于k-團社區(qū)檢測。

5 結(jié)語

本文首先定義對稱形式背景,討論對稱形式背景概念及概念格的特征,并給出對稱概念的定義;其次,證明對稱概念集SC是概念約簡并探討SC的性質(zhì);最后,從沖突分析及社交網(wǎng)絡(luò)的角度解釋對稱形式背景、對稱概念及SC的實際語義及應(yīng)用。

關(guān)于對稱形式背景還有很多新問題亟待提出和解決。如對稱形式背景的二元關(guān)系滿足自反性和對稱性,若在此基礎(chǔ)上附加傳遞性,那么同時滿足自反性、對稱性和傳遞性的形式背景對應(yīng)著何種應(yīng)用場景、有何更特殊的性質(zhì)等都是值得探討的問題。