基于包含度理論的概念格構(gòu)造方法研究

何 苗，石 慧，魏 玲

(西北大學(xué)數(shù)學(xué)系，陜西西安 710127)

Wille R.于1982年首先提出了形式概念分析理論[1－2]，用于概念的發(fā)現(xiàn)、排序和顯示。形式背景與形式概念是形式概念分析的基本概念，形式概念是由形式背景中的對象集和屬性集組成的統(tǒng)一體，形式概念之間可形成一種有序的層次結(jié)構(gòu)——概念格，概念格的構(gòu)造[3－5]是形式概念分析理論的主要研究內(nèi)容之一。

Duntsch和Gediga把粗糙集中的上、下近似算子引入概念格理論中，得到了面向?qū)傩愿拍罡馵6]。類似地，Yao獲得了面向?qū)ο蟾拍罡?，并對兩者之間的關(guān)系做了進一步的研究[7－9]。包含度理論[10]是張文修教授提出的一種定量化不確定性的理論，是對“包含關(guān)系”的擴充，從而包含了“關(guān)系”的不確定性。作者利用包含度基于形式背景定義了4種新的算子，并證明了當(dāng)包含度取不同的值時，可以構(gòu)造4種概念格，即經(jīng)典概念格、補背景概念格、面向?qū)傩愿拍罡窈兔嫦驅(qū)ο蟾拍罡?。因而，本文提出的基于包含度理論?gòu)造概念格的方法可以實現(xiàn)對多種概念格構(gòu)造方法的統(tǒng)一。

1 預(yù)備知識

定義1[2]稱(G，M，I)為一個形式背景，其中G={g1，…，gt}為對象集，每個gi(i≤t)稱為一個對象;M={m1，…，ms}為屬性集，每個mj(j≤s)稱為一個屬性;I為G和M之間的二元關(guān)系I?G×M。若(g，m)∈I，則稱g具有屬性m，用gIm表示。

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

X*={m|m∈M，?g∈X，gIm}，

B'={g|g∈G，?m∈B，gIm}。

?g∈G，記{g}*為g*;?m∈M，記{m}'為m'。若?g∈G，g*≠?，g*≠G，且?m∈M，m'≠?，m'≠M，則稱形式背景(G，M，I)是正則的。本文提到的形式背景都是正則的。

對于二元關(guān)系I，定義其補關(guān)系Ic={(g，m)|? (gIm)}，則形式背景(G，M，Ic)是(G，M，I)的補形式背景。

設(shè)(G，M，I)是形式背景，?A?G，B?M，若滿足A*=B且A=B'，則稱(A，B)是一個形式概念，簡稱概念;其中A稱為概念的外延，B稱為概念的內(nèi)涵。形式背景(G，M，I)的全體概念記為 L(G，M，I)。?(A1，B1)，(A2，B2)∈ L(G，M，I)，定義

(A1，B1)∧ (A2，B2)=(A1∩ A2，(B1∪B2)'*)，

(A1，B1)∨ (A2，B2)=((A1∪ A2)*'，B1∩B2)，

則L(G，M，I)是完備格，稱為概念格。

定義2[6]設(shè)(G，M，I)是形式背景，?X?G，B?M，定義一對近似算子◇，□，:

X◇={m|m∈M，m'∩X≠?}，

B□={g|g∈G，g*?B}。

定義3[6]設(shè)(G，M，I)是形式背景，?X?G，B?M，若一個二元組(X，B)滿足X◇=B，B□=X，稱(X，B)為面向?qū)傩愿拍睢?/p>

記 LP(G，M，I)={(X，B)|X◇=B，B□=X}，則LP(G，M，I)是完備格，稱為面向?qū)傩愿拍罡瘛Ｆ渖?、下確界定義為:?(X1，B1)，(X2，B2)∈ LP(G，M，I)，

(X1，B1)∧ (X2，B2)=(X1∩ X2，(B1∩B2)□◇)，

(X1，B1)∨ (X2，B2)=((X1∪X2)◇□，B1∪B2)。

定義4[9]設(shè)(G，M，I)是形式背景，?X?G，B?M，若一個二元組(X，B)滿足X□=B，B◇=X，稱(X，B)為面向?qū)ο蟾拍睢?/p>

記 LO(G，M，I)={(X，B)|X□=B，B◇=X}，則LO(G，M，I)是完備格，稱為面向?qū)ο蟾拍罡?。其上、下確界定義為:?(X1，B1)，(X2，B2)∈ LO(G，M，I)，

(X1，B1)∧ (X2，B2)=((X1∩X2)□◇，B1∩B2)，

(X1，B1)∨ (X2，B2)=(X1∪ X2，(B1∪B2)◇□)。

定義5[11]設(shè)(G，M，I)是形式背景，?X?G，B?M，在X和B上定義運算

X+={m∈M|?g∈X，(g，m)?I}，

B+={g∈ G|?m ∈B，(g，m)?I}。

設(shè)(G，M，I)是形式背景，?X?G，B?M，若滿足X+=B且X=B+，則(X，B)是補背景(G，M，Ic)的概念。補背景(G，M，Ic)的全體概念記為L(G，M，Ic)。?(A1，B1)，(A2，B2)∈L(G，M，Ic)，定義

(A1，B1)∧ (A2，B2)=(A1∩ A2，(B1∪B2)'*)，

(A1，B1)∨ (A2，B2)=((A1∪A2)*'，B1∩B2)，

則L(G，M，Ic)是完備格，稱為補背景的概念格。

2 基于包含度的4種概念格構(gòu)造方法

本節(jié)主要基于包含度定義了新算子，當(dāng)包含度取不同的值時，新算子就是*，'，+，◇，□，算子，由此可以構(gòu)造經(jīng)典概念格、補背景概念格、面向?qū)ο蟾拍罡窈兔嫦驅(qū)傩愿拍罡瘛?/p>

定義6[10]設(shè)(X，≤)是偏序集，若對于任意x，y∈X，都有數(shù)D(y/x)與之對應(yīng)，且滿足:

1)0≤D(y/x)≤1，

2)x≤ y? D(y/x)=1，

3)x≤ y≤z? D(x/z)≤ D(x/y)，則稱D為X上的包含度。

設(shè)G是有限集，Π(G)表示G上的全體子集，“?”表示集合的包含關(guān)系，則(Π(G)，?)為偏序集。?E∈Π(G)，F(xiàn)∈Π(G)，記則根據(jù)包含度的定義可知，D為Π(G)上的包含度。

定義7 設(shè)(G，M，I)是形式背景，?X≠?，X?G，B≠?，B?M，在X和B上定義運算(0≤α≤β≤1):

定義8 設(shè)(G，M，I)是形式背景，?X?G，B?M，在X和B上定義運算(0≤α≤β≤1):

例1 表1給出的形式背景(G，M，I)來源于匈牙利的科教電影“生物與水”［2］。這里的對象是電影中提及的生物，屬性是電影所強調(diào)的特性。對象和屬性代碼意義如下:①螞蝗，②魚，③蛙，④狗，⑤水草，⑥蘆葦，⑦豆，⑧玉米;a:在水中生活，b:在陸地生活，c:有葉綠素，d:雙子葉，e:單子葉，f:能運動，g:有四肢，h:哺乳。

表1 科教電影“生物與水”的形式背景(G，M，I)Tab.1 Formal context(G，M，I)of science and eduration filum"Biology and Water"

考察表1的形式背景 (G，M，I)。若設(shè) α =0.5，β=1，則根據(jù)定義7和定義8可得:

根據(jù)定義7和定義8，可得如下結(jié)論。

性質(zhì)1 當(dāng)［α1，β1］?［α2，β2］時，以下性質(zhì)成立

例2 考察形式背景表1。若?。郐?，β1］ =［0.5，1］，［α2，β2］ = ［0.25，1］，則計算可得

因此

因此

因此

因此

定理1 設(shè)(G，M，I)是形式背景，?X?G，B?M，0≤α≤β≤1，有

證 明1)E11(X)={m∈M|D(m'/X)=1}=

{m∈M|X?m'}=X*，

{g∈ G|B ? g*}=B'。

{m∈M|X∩m'≠?}=X◇。

{g∈G|B∩g*≠?}=B◇。

{m∈M|m'∩X=?}=X+，

{g∈G|g*∩B=?}=B+。

定理2 設(shè)(G，M，I)是形式背景，?X?G，B?M，0≤α≤β≤1，有

證 明1)L11(X)={m∈M|D(X/m')=1}=

{m∈M|m'?X}=X□，

N11(B)={g∈G|D(B/g*)=1}=

{g∈G|g*?B}=B□。

2)L1α(X)={m∈M|α≤D(X/m')≤1}=

{m∈M|X∩m'≠?}=X◇，

N1α(B)={g∈ G|α ≤ D(B/g*)≤1}=

{g∈G|g*∩B≠?}=B◇。

3)L00(X)

{m∈M|X∩m'=?}=X+，

N00(B)={g∈G|D(B/g*)=0}=

{g∈G|B∩g*=?}=B+。

可由以上定理以及已有的*，'，+，◇算子的性質(zhì)［2，6，11］，得出以下結(jié)論。

推論1 設(shè)(G，M，I)是形式背景，?X1，X2，X?G，B1，B2，B?M，以下性質(zhì)成立

(Ⅰ)當(dāng)α=β=1時

由定理1與定理2知，當(dāng)α，β取特定的值時，Eβα，F(xiàn)βα算子對應(yīng)著形式背景的概念格與補背景概念格中的算子，因而可以構(gòu)造相應(yīng)概念格。類似地，Lβα，Nβα算子對應(yīng)補背景概念格、面向?qū)ο蟾拍罡衽c面向?qū)傩愿拍罡裰械乃阕?，因而可以?gòu)造這3種格。具體方法如下定理所示。

定理3 設(shè)(G，M，I)是形式背景，?X?G，B?M(0≤α≤β≤1)，則

3 結(jié)語

本文基于包含度理論定義了新的算子，并證明了當(dāng)包含度取不同的值時，利用新算子可以構(gòu)造4種概念格，即經(jīng)典概念格、補背景概念格、面向?qū)傩愿拍罡窈兔嫦驅(qū)ο蟾拍罡?。這種基于包含度方法是對這4種概念格構(gòu)造方法的統(tǒng)一。

[1]WILLE R.Restructuring lattices theory:an approach based on hierarchies of concepts[C]∥RIARAL I，Ordered Sets.Dordrecht:Reidel，1982:445-470.

[2]GANTER B，WILLE R.Formal Concept Analysis[M].Mathematical Foundations，New York:Springer-Verlag，1999.

[3]CARPINETO C，ROMANO G.Concept Data Analysis:Theory and Application [M].Chichester:John Wiley＆Sons，Ltd，2004.

[4]HO T B.Discovering and using knowledge from unsupervised data[J].Decision Support System，1997，21(1):29-42.

[5]BELOHLAVEK R.Fuzzy closure operators[J].Journal of Mathematical Analysis and Applications，262(2001)473-489.

[6]DUNTSCH I，GEDIGA G.Approximation operators in qualitative data analysis[C]∥In:Theory and Application of Relation of Structures as Knowledge Instruments，2003:216-233.

[7]YAO Y Y.A comparative study of formal concept analysis and rough set theory in data analysis[J].Lecture Notes in Artificial Intelligence，2004，3066:59-68.

[8]YAO Y Y.A partition model of granular computing[J].Lecture Notes in Computer Science，2004，3100:232-253.

[9]YAO Y Y.Concept Lattices in Rough Set Theory[C]∥DICK S，KURGAN L，PEDRYCZ W，et al.Proceedings of 2004 Annual Meeting of the North American Fuzzy Information Proceeding Society Washington:IEEE Computer Society，2004:796-801.

[10]張文修，梁怡.不確定性推理原理[M].西安:西安交通大學(xué)出版社，1996.

[11]何苗，魏玲.基于原背景的補背景概念獲取[J].計算機科學(xué)，2012，39(11):197-200.