概念知識系統與閉包系統的聯系

洪小飛，袁曉華

（鄭州工業應用技術學院 基礎部，河南 鄭州 451100）

概念知識系統與閉包系統的聯系

洪小飛，袁曉華

（鄭州工業應用技術學院 基礎部，河南 鄭州 451100）

形式背景中的概念來源于哲學，是由外延以及內涵共同形成的.為實現概念的發現、排序和顯示的目的，德國數學家Will.R首次提出以形式背景為基礎構建格理論的思想，該理論成為數據分析、知識處理的重要方法.本文首先給出概念知識系統的概念，通過論證得到：形式背景與概念知識系統能互相確定，而且且建立概念知識系統與閉包系統之間的聯系.

形式背景；概念知識系統；閉包系統

1.1 預備知識

定義1.1.1[1]（上界與下界） 設(X,≤)為一偏序集，A?X，若?a∈A，都有x≤a，x∈X，則稱x是A的一個下界；若?a∈A，都有a≤y，y∈X，則稱y是A的一個上界.A的所有下界的集合中最大的下界稱為A的下確界；A的所有上界的集合中最小的上界稱為A的上確界.A的下確界可記為infA或∧A；A的上確界可記為supA或∨A.若A中只有兩個元素x,y時，可記為x∨y及x∧y.

定義1.1.2[1]（格與完備格） 設(X,≤)是一個偏序集，若?x,y∈X，x∨y和x∧y都存在，則稱 (X,≤)是一個格.若?A?X，supA或∨A及infA或∧A都存在，則稱(X,≤)是一個完備格.

定義1.1.3[2]（形式背景） 稱(U,A,I)為一形式背景，其中U={u1,u2,…,un}稱為對象集，且每個ui(i=1,2,…,n)為一個對象，A={m1,m2,…,mm}稱為屬性集，且每一個mj(j=1,2,…,m)為一個屬性，I為U與A的二元關系，即I?U×A.

在形式背景(U,A,I)中，若u具有屬性m，用(u,m)∈I來表示，簡記做uIm，一般用1表示(u,m)∈I，0表示(u,m)?I.如此，一個形式背景(U,A,I)可用只含0,1的二維表來表示.

例1.1.1 如下一個二維表可表示一個形式式背景.

?

在該形式背景中，U={u1,u2,…,un}，A={a,b,c,d}，由表顯然可知(u2,a)∈I，(u1,a)?I等.

定義1.1.4[3]設(U,A,I)為一形式背景，X?U,B?A.下面給出一對對偶算子，分別記作f,g,

f(X)表示集合X中所有對象共的屬性集，g(B)表示集合中所有屬性的對象集.

定義1.1.5[4]（正則形式背景） 設(U,A,I)為一形式背景，稱(U,A,I)為正則形式背景，若滿足下列條件：

事實上，如果一形式背景(U,A,I)可稱為為正則形式背景，那么該形式背景所對應的二維表中每一行和列中至少有一個0或1，并且不允許行與列均為0與1.

一般情況下，本文所使用的形式背景(U,A,I)均是正則形式背景.

命題1.1.1[4]設(U,A,I)是一形式背景，?X1,X2X?U,B1, B2,B?A，有以下結論成立：

定義1.1.6[2]（概念）設(U,A,I)是一形式背景，X?U，B?T，稱（X，B）為形式背景（U，A，I）的一個概念，若滿足以下條件：

一般情況下，本文用L(U,A,I)來表示形式背景(U,A,I)的所有概念的集合.即L(U,A,I)={(X,B)|f(X)=B,g(B)=X}.

例1.1.2 如例1.1.1所示形式背景，則所有的概念有：

命題1.1.2 設(U,A,I)是一形式背景，則(L(U,A,I),≤)為一偏序集,且是一個完備格，稱為概念格.

其次，再證(L(U,A,I),≤)是一個格.?(X1,B1),(X2,B2)∈L(U, A,I)，往證

如果(X,B)是(X1,B1)和(X2,B2)的任一個共同下界，則X?X1且X?X1，從而X?X1∩X2，所以(X,B)≤(X1∩X2，f(g(B1∪B2)))，即

同理可得(X1,B1)∨(X2,B2)=(g(f(X1∪X2)),B1∩B2)∈L(U,A,I).

因此，(L(U,A,I),≤)是一個格.

用上述方法，可證?(Xt,Bt)∈L(U,A,I),t∈T，有

綜上所訴，(∈L(U,A,I),≤)是完備格.

定義1.1.7[5]設U是一個有限對象集，A為有限屬性集，X1,X2?U，B1,B2?A.稱L:P(U)→P(A)為外延內涵算子，若L滿足：

稱H:P(A)→P(U)為內涵外延算子，若H滿足：

稱(U,A,L,H)為概念知識系統.

定理1.1.1[5]設(U,A,L,H)為概念知識系統，X1,X2?U，B1,B2?A,則有以下新性質成立：

定義1.1.8[6]設(U,A,L,H)為概念知識系統，對于X?U, B?A，若L(X)=B,H(B)=X，稱(X,B)為概念.

定理1.1.2[5]設(U,A,L,H)為一個概念知識系統,則(L(U, A,L,H)≤)是一個完備格，稱為概念知識格.

其中L(U,A,L,H)={X,B)|L(X)=B,H(B)=X,X?U,B?A}.

定義1.1.9[1]（閉包系統） 設S是一個集合，?是S的子集的集合，??2S，若?滿足：

（1）S∈?；

（2）P??，則∩P∈?；

則稱?是一個閉包系統.

定義1.1.10[1]（閉包算子） 設S是一個集合，φ：2S|→2S，滿足：

則稱φ是S上的一個閉包算子.

1.2 概念知識系統與形式背景

命題1.2.1 設(U,A,I)為形式背景，集合U和A均為有限的，則存在概念知識系統(U,A,f,g)，使得(U,A,f,g)產生的形式背景與(U,A,I)一致.

證明 對形式背景(U,A,I)，設X?U,B?A，取

f(X)={a∈A:?x∈X,(x,a)∈I}，g(B)={x∈U:?a∈B,(x,a)∈I}；由定義1.1.7，則顯然可證：f滿足外延外延內涵算子的條件，g滿足內涵外延算子的條件，且由命題1.1.1有g(f(X))?X,f(g(B))?B.

因此，(U,A,f,g)是概念知識系統.

設I0={(x,a)∈U×A:x∈g({a})}是(U,A,f,g)產生的形式背景(U,A,I0)的二元關系，則I0?U×A.且由形式背景(U,A,I)中關系I可知：

與I0的定義一致，所以，(U,A,f,g)產生的的形式背景(U,A,I0)與(U,A,I)一樣.

命題1.2.2 設(U,A,L,H)為概念知識系統，那么存在形式背景(U,A,I)，使得(U,A,I)產生的概念知識系統與(U,A,L,H)一致.

根據定義1.1.7（1.7）式，?u∈U,{u}≠??L(u)≠A，即f(u)≠A；由定義1.1.7（1.1.9）式?m∈A,{m}≠??H(m)≠U，g(m)≠U即.當U≠{u}時，L(u)≠L(U)=?，即f(u)≠?；同理可證，當A≠{m}時，H(m)≠H(A)=?，即g(m)≠?.所以，(U,A,I)為一正則形式背景.

由上述兩定理可知，形式背景(U,A,I)和概念知識系統(U, A,L,H)可以相互確定，并且L(U,A,I)中的概念與L(U,A,L,H)中的概念一致，即L(U,A,I)=L(U,A,L,H)，那么本節中的概念知識格可簡稱為概念格，且L(U,A,L,H)可記為L(U,A,f,g)，本文之后用(U,A,f,g)來表示概念知識系統.

1.3 概念知識系統與閉包系統

命題1.3.1 算子(fg)為U上的閉包算子，算子(gf)為A上的閉包算子.

證明 （1）如果X?Y，且X,Y?U，則由f,g閉包算子的屬性可得：f(X)?f(Y)，g(f(X))?g(f(Y))，即(fg)(X)?(fg)(Y),單調性成立；

（2）由定義1.1.7知：X?g(f(X))，即X?(fg)(Y)，擴展性成立；

（3）由定理1.1.1（3）知對任意的X?U，有f(g(f(X)))=f(X)，從而有g(f(g(f(X))))=g(f(X))，即(fg)(fg)(X)=(fg)(X)，冪等性成立.

綜上所述，算子(fg)為U的閉包算子.

同理可證，算子(gf)為A的閉包算子.

命題1.3.2 設(U,A,f,g)是概念知識系統，?是U上的閉包系統，?是A上的閉包系統，定義

（1）φ:P(U)→P(U)，φ(X)=∩{T∈?|X?T}；

（2）?:P(A)→P(A)，?(B)=∩{T∈?|B?T}.

則φ是U上的閉包算子，?是A上的閉包算子，這兩個算子均稱為由閉包系統誘導出的閉包算子.

證明 （1）首先，如果X?U，則{T∈?|X?T}?{T∈?|Y?T}，從而有：∩{T∈?|X?T}?∩{T∈?|Y?T}，即φ(X)?φ(Y),單調性成立.

其次，由于{T∈?|X?T}中的每個元素都包含X，故可得：X?∩{T∈?|X?T}=φ(X)，從而X?φ(X)，擴展性得證.

再次，因為{T∈?|X?T}中的每一個元素都是閉包系統?中的元素，且?是閉包系統，故∩{T∈?|X?T}也為?的元素，記∩{T∈?|X?T}=Y，則Y∈?，從而Y∈{T∈?|Y?T }，所以，∩{T∈?|Y?T}=Y，又由算子的擴展性可得Y?φ(Y) =∩{T∈?|Y?T}，即φ(Y)=Y，故φ(φ(X))=φ(Y)=Y，從而可以得到φ(φ(X))=φ(X)，即冪等性得證.

綜上所述，φ是U上的閉包算子.

同理可證（2）.

命題1.3.3 設(U,A,f,g)為概念知識系統，則

（1）{(fg)(X)|X?U}是U上的閉包系統；

（2）{(gf)(B)|B?A}是A上的閉包系統.

證明 （1）首先，因為(U,A,f,g)為概念知識系統，從而對?X?U，都有g(f(X))?X成立，所以有(fg)(X)?X,即X?(fg) (X)；由于U?U，則U?(fg)(U)，從而U∈{(fg)(X)|X?U}.

其次，假設P?{(fg)(X)|X?U}，則由命題1.3.1閉包算子(fg)的擴展性可知：∩P?(fg)(∩P)，另外，對?T∈P，均有∩P?T；再由閉包算子(fg)單調性有：

從而T∈P?{(fg)(X)|X?U)}；所以存在X0，使得T=(fg) (X0)，于是有：

將（1.13）代入（1.12）得(fg)(∩P)?(fg)(T)=T，即(fg)(∩P)?T.由于T是P的任一元素，所以(fg)(∩P)?P,又由于有∩P?(fg)(∩P)，從而可得(fg)(∩P)=∩P.

綜上可得，∩P?(fg)(∩P)∈{(fg)(X)|X?U}.

所以，∩P∈{(fg)(X)|X?U}.

所以，{(fg)(X)|X?U}是U上的閉包系統.

同理可證（2），即{(fg)(B)|B?A}是A上的閉包系統.

命題1.3.4 設(U,A,f,g)是概念知識系統，

（1）記?={(fg)(X)|X?U}，?是對象U上的一個閉包系統，則(?,?)是一個完全格；

（2）記?={(fg)(B)|B?A}是屬性A上的閉包系統，則(?,?)是一個完

全格.

證明 （1）首先，?P??，P中的每一個元素N，均有∩P?N成立，所以∩P是集合P的下界；假設集合M是P的任一下界，則M是P的每一個元素的子集，則?m∈M，均有m∈∩P，即M?∩P，從而∩P是集合P的下確界.

其次，對于集合{X∈?|∪P?X}，則{X∈?|∪P?X}是?中P的上界的集合，那么有∩{X∈?|∪P?X}是?中P的上界集合中最小的元素；又由?是閉包系統知∩{X∈?|∪P?X}∈?；所以，∩{X∈?|∪P?X}是P的上確界.

綜上所述，?的任一子集都存在上確界、下確界，故(?,?)是完全格.

同理可證（2）.

〔1〕馬垣，曾子維，遲呈英，吳建勝.形式概念及其新進展[M].北京:科學出版社,2011.1-13.

〔2〕Nourine L,Raynaud O.A fast algorithm for building lattices[J].Information processing letters,1999,71(5): 199-204.

〔3〕Fa?d M,Missaoi R,Godin R.Mining complex structures using context concatenation in formal concept analysis[C]//International KRUSE Symposium,Vancouver,BC.1997:11-13.

〔4〕張文修,魏玲,祁建軍.概念格的屬性約簡理論與方法[J].中國科學(E輯),2005,35(6):628-639.

〔5〕仇國芳,陳勁.概念知識系統與概念信息粒格[J].工程數學學報,2005,22(6):963-969.

〔6〕Valtchev P,Missaoui R,Codin R.et al..Generating frequent itemsets incrementally：Two novel approaches based on galois lattice theory.Journal of Experimental &Theoreyical Artificial Intelligence,2002,14(2-3)：115-142.

O189.1

A

1673-260X（2017）03-0012-03

2016-11-10

2016年湖南財政經濟學院課題：我院大學生職業生涯指導-困境與出路（YJ201603）