萬家良，魏 玲

(西北大學數學系，陜西西安 710127)

Wille R.于1982年提出的形式概念分析理論[1－2]是一種非常有力的數據分析和知識發(fā)現的數學工具，廣泛應用于人工智能和信息檢索等領域[3－4]。

粗糙集理論和概念格理論是兩種不同的知識處理的數學工具。近年來，廣大學者對概念格和粗糙集理論展開了深入的研究，并且將二者結合起來，以便更好地掌握和理解數據[5－6]。Duntsch和Gediga通過定義modal-style算子，并且由粗糙近似算子構造了面向屬性概念格[7]，Yao Y.Y.借用該思想，建立了面向對象概念格，且證明了面向屬性概念格與面向對象概念格是同構的[8]，為數據分析提供了新的理論依據。

隨著網絡的發(fā)展，大數據時代離我們越來越近，從龐大的數據庫中找到我們需要的知識越來越困難，構建概念格也變得十分復雜。因此，概念格的壓縮引起了人們的關注。文獻[9]用SVD對概念格進行剪枝的方法，使原概念格的結構變小。文獻[10]應用FKM-模糊聚類方法對概念格進行壓縮，減少了概念格的節(jié)點。但是，這兩種方法都是對經典概念格進行壓縮。文獻[11]根據對象的相似程度調整對象鄰域的大小，控制面向屬性概念格的節(jié)點，對面向屬性概念格進行壓縮。而本文則是從面向對象概念出發(fā)，借鑒文獻[12－13]的n階粗糙集的思想，引入n階算子，產生n階面向對象概念，進而通過調整n值的大小，對面向對象概念格進行動態(tài)壓縮，并給出壓縮后的概念與原面向對象概念格概念的關系，達到簡化知識庫的目的。

1 預備知識

定義1[1]稱三元組(G，M，I)是一個形式背景，其中 G={x1，x2，…，xn}為對象集，每個 xi稱為一個對象，M={a1，a2，…，as}為屬性集，每個ai稱為一個屬性，I是對象集G和屬性集M之間的二元關系集，且I?G×M。若(x，a)∈I，則稱x具有屬性a。

對于形式背景(G，M，I)，在對象集X?G和屬性集B?M上分別定義運算* 與'[1－2]:

X*={a|a∈M，?x∈X，(x，a)∈I}，

B'={x|x∈G，?a∈B，(x，a)∈I}。

X*表示X中所有的對象共同具有的屬性集合，B'表示具有B中所有屬性的對象集合。若?x∈G，x*≠?，x*≠M，且?a∈M，a'≠?，a'≠G，則稱形式背景(G，M，I)是正則的，以下假定形式背景都是正則的。

文獻[8]用“□”表示下近似對應的集合，用“◇”表示上近似對應的集合，對于X?G及B?M，定義

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

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

定理 1[8]設(G，M，I)為一個形式背景，?X，X1，X2?G及?B，B1，B2?M，算子“□”與“◇”有以下性質:

1)X1? X2?X1□?X2□

2)B1? B2?B1◇?B2◇;

3)X□◇?X，B?B◇□;

4)X□◇□=X□，B◇□◇=B◇;

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

定義 2[8]設(G，M，I)是形式背景，如果?X?G，?B?M，滿足X=B◇且B=X□，則稱二元組(X，B)為面向對象概念。其中X為概念的外延，B為概念的內涵。

定理 2[8]設(G，M，I)是形式背景，記LO(G，M，I)={(X，B)|X=B◇，B=X□}，令(X1，B1)≤(X2，B2)，則LO(G，M，I)為偏序集。在LO(G，M，I)上定義

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

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

那么(LO(G，M，I)，∨，∧)是一個完備格，稱為面向對象概念格。

把所有面向對象概念的外延的集合表示為LOG(G，M，I)，所有面向對象概念的內涵的集合表示為 LOM(G，M，I)。

定義3[1]設(G，M，I)為形式背景，對于它的兩個概念(Xi，Bi)和(Xj，Bj)，若 Xi? Xj或 Bi? Bj，則稱(Xi，Bi)是(Xj，Bj)的亞概念，(Xj，Bj)是(Xi，Bi)的超概念。

定義 4[14－15]設(G，M，I)為形式背景，對于它的兩個概念(X1，B1)，(X2，B2)，若(X1，B1)≤(X2，B2)，而且不存在(X，Y)，(X，Y)≠ (X1，B1)，(X，Y)≠ (X2，B2)，使 得(X1，B1)≤ (X，Y)≤ (X2，B2)，則稱(X1，B1)是(X2，B2)的子概念，稱(X2，B2)是(X1，B1)的父概念。

2 面向對象概念格的壓縮

本文提出的面向對象概念格的壓縮方法是通過引入n階上下近似算子，產生n階面向對象概念，進而由n值的大小來控制壓縮后的節(jié)點個數，最終實現對面向對象概念格的動態(tài)壓縮。

2.1 壓縮方法

定義5 設(G，M，I)為形式背景，對于X?G及B?M，定義算子“□n”與“◇n”如下:

X□n={a∈ M||a'－ X|≤ n}=

{a∈ M||a'|－|a'∩ X|≤ n}，

B◇n={x∈G||x*∩B|＞ n}。

n=0，1，…，max{|G|－1，|M|－1}，|·|表示集合的基數。

定義5表明，如果具有屬性a的對象個數最多有n個不在對象集X中，則屬性a屬于X□n;如果對象x所擁有的屬性在屬性集B中的元素個數多于 n個，則對象x屬于B◇n。

定理3 設(G，M，I)為一個形式景，?X，X1，X2? G及 ?B，B1，B2? M，算子“□n”與“◇n”有以下性質:

1)X□0=X□;B◇0=B◇;

2)?◇n= ?，G□n=M;當n≠0時，a◇n=?;

3)X1?X2?

4)(X1∩ X2)□n?

5)若 n≥ m，則:X□n? X□m，B◇n? B◇m;

證 明 1)，2)可直接由定義得出。

3)?a∈X1□n，有|a'－ X1|≤ n。如果X1?X2，則 |a'－X2|≤ |a'－X1|≤n，所以a。因此有。第二式可類似證明。

4)因為X1∩X2? X1，X1∩X2? X2，所以由3)可知:(X1∩X2)□n?X1□n，(X1∩ X2)n?，于是，(X1∩ X2)□n? X1□n∩。類似地，(B1∪B2)◇n

5)?a∈ X□m，有|a'－ X|≤ m。如果 n≥m，則 |a'－ X|≤m≤n，即a∈X□n。因此，X□n?X□m。?x∈B◇n，有|x*∩B|＞ n。如果n≥m，則|x*∩B|＞ n≥m，即x∈B◇m。

對比定理1發(fā)現，算子“□n”與“◇n”不具備類似于定理1中的性質3)和性質4)，這可通過下面的例題得出。

例1 設形式背景(G，M，I)如表1所示，對象集G={1，2，3，4，5，6}，屬性集M={a，b，c，d，e，f}。其中 × 表示(x，a)∈ I。其面向對象概念格如圖1所示。為簡便起見，本文中內涵與外延皆用相應集合的元素序列表示。

表1 形式背景T=(G，M，I)Tab.1 T=(G，M，I)

圖1 LO(G，M，I)Fig.1 LO(G，M，I)

不失一般性，這里取n=1。

令 X=3456，則

X□1={a∈M||a'－ 3456|≤1}=acdef。而 X□1◇1=acdef◇1={x∈G| |x*∩acdef| ＞1}=23456。同時 X□1◇1□1=23456□1=M。所以X□1◇1? X，X□1◇11≠ X1。

令 B=ad，則B◇1={x∈G| |x*∩ad|＞ 1}=34。

而 B◇1□1=34□1={a∈ M||a'－ 34|≤1}=af。同時 B◇1□1◇1=af◇1=3。所以 B ? B◇1□1，B◇1□1◇1≠ B◇1。

為便于下文敘述，記

O(G，M，I)={∩Xi∈XXi|X ? LOG(G，M，I)}，

A(G，M，I)={∪Bi∈BBi|B ? LOM(G，M，I)}。

定義6 設LO(G，M，I)是面向對象概念格。若X=B◇n，B=X□n，n ＞ 0，則稱(X，B)為壓縮后的n階面向對象概念。

定義6即是將原面向對象概念的內涵壓縮為一些概念內涵的并，將原面向對象概念的外延壓縮為一些概念外延的交。

例2 本例針對例1中的形式背景，研究n=1及n=2時，面向對象概念格的壓縮，以達到簡化概念格的目的。

當n=1時，其面向對象概念格的壓縮步驟如下:

1)?X ∈ O(G，M，I)，計算 X□1:

?□1，= ?，3□1=34□1=af，

5□1=ef，2□1=e，

35□1=23□1=aef，25□1=125□1=bef，

235□1=1235□1=abef，345□1=acef，

346□1=acdf，

23□1=adef，2346□1=3456□1=acdef，

2345□1=23456□1=12345□1=M。

2)?B ∈ A(G，M，I)，計算 B◇1:

?◇1=a◇1=e◇1=f◇1= ?，af◇1=3，

be◇1=bef◇1=25，aef◇1=35，ef◇1=5，

ad◇1=34，acf◇1=acef◇1=345，

abef◇1=235，

ade◇1=234，adcf◇1=3456，

abcef◇1=abdef◇1=2345，

acdef◇1=M◇1=23456。

3)由定義6可得到壓縮后的所有概念:

(23456，M)，(235，abef)，(345，acef)，(35，aef)，(25，bef)，(3，af)，(5，ef)，(?，?)。

壓縮后的1階面向對象概念的Hasse圖如圖2所示。

圖2 LO1(G，M，I)Fig.2 LO1(G，M，I)

當n=2時，由類似的計算過程可得到2階面向對象概念，其Hasse圖如圖3所示。

對比壓縮后的n階面向對象概念的Hasse圖與原形式背景的面向對象概念格可知，本文的壓縮實質是:如果形式背景中的對象x滿足|x*|≤n，則作n階壓縮時，將該對象去掉;如果形式背景中的屬性m滿足|m'|≤n，則作n階壓縮時，n階面向對象概念的內涵都有該屬性。

圖3 LO2(G，M，I)Fig.3 LO2(G，M，I)

2.2 相關性質

以下兩個定理將給出LO(G，M，I)的概念外延和內涵分別作n階算子后的特征。

定理4 設(G，M，I)為形式背景，?(X，B)∈ LO(G，M，I)，X ≠ G，(Xi，Bi)是(X，B)的超概念。如果 |Xi|－|X|≤ n(i∈ τ)，則:X□n= ∪τBi。

證 明 因X ?Xi，且|Xi|－|X|≤n，所以 ?a ∈ Bi，有 a'? Xi，因此 |a'－ X|≤ n，即 a∈ X□n，所以Bi? X□n。由i的任意性得，∪τBi?X□n。

下面證明 X□n?∪τBi。如果 X□n? ∪τBi，那么?d0∈ X□n，且 d0? ∪τBi，即 d0∈ M －∪τBi。由于 |d0'－X|≤n，記C1=d0'－X，D1={d∈M|d'－X?C1}，則有d0∈D1。下面證明序對(X∪C1，B∪D1)是一個面向對象概念。由于?x?X∪C1，x*∩(B∪D1)=?，所以只需對X∪C1中的對象作*算子。?x∈X∪C1，有x*∩(B∪D1)≠?;同樣地，?b?B∪D1，因此也只要對B∪D1中的屬性作'算子。?b∈B∪D1，如果b∈ B，則 b'? X∪C1顯然，若b∈D1，由D1的定義可知b'?X∪C1;從而(X∪C1，B∪D1)是面向對象概念，而且是(X，B)的超概念，滿足|X∪C1|－|X|≤ n，且 d0∈ B∪ D1。這與假設 d0?∪τBi矛盾。所以 Xn? ∪τBi。綜上得 Xn= ∪τBi。

推論1 設(G，M，I)為形式背景，?(X，B)∈ LO(G，M，I)，X≠G，(Xi，Bi)是(X，B)的父概念，如果 |Xi|－|X|＞ n(i∈ τ)，則 X□n=B。

證 明 如果X□n? B，則?d0∈M －B，有d0∈X□n，|d0'－ X|≤n。同樣地，令C2=d0－ X，D2={d∈M|d'－X? C2}，類似的，由定理4可知，概念(X∪C2，B∪D2)是概念(X，B)的超概念，且|X∪C2|－|X|≤n，與題設矛盾，所以不存在屬性d0?B，且d0∈ X□n。因此X□n? B。又因為 B=X□? X□n。得 X□n=B。

例3 在例1中，概念(235，ef)有5個超概念，它們的外延與該概念的外延關系為:

|1235|=|235|+1，|2345|=|235|+1，

|12345|=|23456|=|235|+2，|G|=|235|+3。

則根據定理4得:

235□1={bef}∪ {aef}={abef}，

235□2={aef}∪{bef}∪{abef}∪{acdef}=M，

235□3=M。

概念(?，?)有3個父概念，它們的外延與該概念的外延關系為:

|25|=|34|=|35|=2 ＞0。

因此滿足推論1的條件，則根據推論1得

?□2=?。

定理5 設(G，M，I)為形式背景，?(X，B)∈ LO(G，M，I)，X ≠?，(Xj，Bj)是(X，B)的亞概念，j∈ τ。如果|B|－|Bj|≤n，n ＞ 0，則B◇n= ∩τXj。

證 明 因為B ?Bj，且|B|－|Bj|≤n。所以?x ∈B◇n，有x*∩Bj≠?，又(Xj，Bj)是面向對象概念，從而x∈Xj。由j的任意性，得B◇n?∩τXj。下面證明 ∩τXj? B◇n。如果 ∩τXj? B◇n，那么存在 g0∈ ∩τXj，但 g0? B◇n，即 |g0*∩B|≤ n。記D1=g0*∩B，C1={g∈G|g*∩B?D1}，則g0∈C1。下面證明序對(X －C1，B －D1)是面向對象概念，因為X－C1?X，所以只要對X－C1中的對象作* 算子。?x∈X－C1，若 x*∩D1≠?，則x∈ C1，顯然矛盾，因此x*∩(BD1)≠?;同樣的，由于B－D1?B，所以只要對B－ D1中的屬性作'算子。?b∈B －D1，若b'?C1，那么b∈ D1，因此 b'?X －C1。所以(X －C1，B －D1)是面向對象概念，也是(X，B)的亞概念，且滿足|B|－|B － D1|≤n，同時g0?X － C1，但是由假設 g0∈∩τXj，可知矛盾，故得 ∩τXj? B◇n。得 ∩τXj=B◇n。

推論2 設(G，M，I)為形式背景，?(X，B)∈ LO(G，M，I)，X≠?，(Xj，Bj)是(X，B)的子概念。如果 |B|－|Bj| ＞ n(j∈ τ)，則 B◇n=X。

證 明 因為X=B◇，所以B◇n?X顯然。如果 X ? B◇n，則 ?g0∈ X，但|g0*∩B|≤n，類似的，記D2=g0*∩B，C2={g∈G|g*∩B? D2}，則g0∈C2。由定理5的證明可知(X－C2，B－D2)是概念(X，B)的亞概念，且滿足|B|－|B－D2|≤n，與題設矛盾，所以不存在g0∈X，但g0? B◇n，因此 X ? B◇n，綜上得 B◇n=X。

例4 在例1中，概念(2345，aef)有6個亞概念，它們的內涵與該概念的內涵關系為

|aef|=|ef|+1=|af|+1，

|aef|=|a|+2=|e|+2=|f|+2，

|aef|=|? |+3。

則根據定理5得

aef◇1={235}∩{345}={35}，

aef◇2={235}∩{345}∩{34}∩{35}∩{25}=?，

aef◇3= ?。

概念(23456，acdef)有3個子概念，它們的內涵與該概念的內涵關系為

|acdef|－|aef|＞ 1，|acdef|－|ad|＞ 1，

|acdef|－|acf|＞ 1。

因此滿足推論2的條件，則根據推論2得

acdef◇1={23456}。

由這兩個定理可知，LO(G，M，I)中的概念不管從外延出發(fā)還是從內涵出發(fā)進行壓縮，都能得到壓縮后的n階面向對象概念。也就是說任給一個LO(G，M，I)中的概念，都能找到壓縮后的唯一的n階面向對象概念。

3 結 語

概念格作為一種概念數據分析和知識處理的數學工具，已被廣泛應用于眾多領域。本文主要研究了基于n階算子的面向對象概念格壓縮方法，根據引入的n階算子進行壓縮，并且壓縮后的概念的外延為原概念外延的交集，壓縮后的概念的內涵為原概念的內涵的并集。通過這種方法，可動態(tài)的壓縮面向對象概念格，刪減不重要的概念，為知識庫的壓縮提供了一種新的方法。

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

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

[3]CARPINETO C，ROMANO G.A lattice conceptual clustering system and its application to browsing retrieval[J].Machine Learning，1996，10:95-122.

[4]CHEN Y，YAO Y.A multiview approach for intelligent data analysis based on data operators[J].Information Sciences，2008，178(1):1-20.

[5]HU K，SUI Y，LU Y，et al.Concept approximation in concept lattice [J].Lecture Notes in Computer Science，2001，2035:167-173.

[6]KENT R E.Rough concept analysis:a synthesis of rough sets and formal concept analysis[J].Fundamenta Informaticae，1996，27:169-181.

[7]DUNTSCH I，GEDIGA G.Approximation operators in qualitative data analysis[C]//Theory and Application of Relational Structures as Knowledge Instruments.Heidelberg:Springer，2003.

[8]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.

[9]CHEUNG K S K，VOGEL D.Complexity reduction in lattice based information retrieval[J].Information Retrieval，2005，8:285-299.

[10]ASWANI KUMAR CH，SRINIVAS S.Concept lattice reduction using fuzzy K-Means clustering[J].Expert Systems with Applications，2010，37(3):2696-2704.

[11]魏玲，李強.面向屬性概念格基于覆蓋的壓縮[J].電子科技大學學報，2012，41(2):299-304.

[12]YAO Y Y，LIN T Y.Generalization of rough sets using modal logic[J].Intelligent Automation and Soft Computing，1996，2(2):103-120.

[13]LIU CAIHUI，MIAO DUOQIAN.Graded rough set model based on two universes and its properties[J].Knowledge-Based Systems，2012，33:65-72.

[14]魏玲.粗糙集與概念格約簡理論與方法[M].西安:西安交通大學出版社，2005.

[15]張文修，仇國芳.基于粗糙集的不確定性決策[M].北京:清華大學出版社，2005.