李立峰， 俞 偉

(1.西安郵電大學(xué) 理學(xué)院， 陜西 西安 710121;2.中國人民解放軍69213部隊， 新疆 喀什 844900)

概念格約簡與覆蓋約簡之間的關(guān)系

李立峰1， 俞 偉2

(1.西安郵電大學(xué) 理學(xué)院， 陜西 西安 710121;2.中國人民解放軍69213部隊， 新疆 喀什 844900)

以一類與覆蓋粗糙集相對應(yīng)的形式背景為工具，對概念格屬性約簡和覆蓋粗糙集約簡進行研究，結(jié)果表明覆蓋粗糙集與形式背景之間存在一一對應(yīng)關(guān)系，并且證明了覆蓋粗糙集的交約簡可化為概念格的屬性約簡。

概念格； 屬性約簡； 覆蓋

0 引 言

概念格是根據(jù)對象與屬性之間的二元關(guān)系建立的一種層次結(jié)構(gòu)[1]。作為數(shù)據(jù)處理的有力工具，概念格被越來越多地應(yīng)用于知識發(fā)現(xiàn)、軟件工程、信息檢索等領(lǐng)域。近年來，概念格的約簡理論是概念格研究領(lǐng)域的一個熱點問題。文獻[2]通過刪掉形式概念中的可約屬性和對象來進行概念約簡；文獻[3]提出在保持格同構(gòu)的條件下建立概念格屬性約簡理論和方法；吳偉志[4]基于軟計算在決策形式背景中提出了新的約簡方法；Elloumi等[5]基于模糊形式背景建立了一個多層次的約簡理論；針對文獻[5]中建立的概念之集不能構(gòu)成格結(jié)構(gòu)，文獻[6]改進了建格方法，在保持格同構(gòu)條件下建立了多層次屬性約簡理論；隨后產(chǎn)生了基于區(qū)間值形式背景的概念格的屬性約簡[7-8]。

在粗集理論的眾多理論中，覆蓋廣義粗集理論是近年來發(fā)展迅速的一個方向，其中不同的覆蓋可以產(chǎn)生相同的上下近似運算，因此，尋找兩個覆蓋會生成相同的上下近似運算的條件是一個重要的論題。另外，一個剖分去掉其中一個等價類或初等集后就不再是一個剖分了，因此不存在冗余問題；而一個覆蓋去掉其中一個子集成員后仍然可以是一個覆蓋，而且還可能生成與原覆蓋相同的上下近似運算，這就表明一個覆蓋可能會有冗余成分存在，這樣，將一個覆蓋的冗余成分去掉也是一個重要論題。覆蓋約簡概念由此產(chǎn)生[9-12]，通過它可以將一個覆蓋的所有冗余部分去掉。因此，覆蓋約簡是粗糙集約簡理論的一個熱點研究方向。關(guān)于概念格和粗糙集的結(jié)合研究一直是熱點問題，如文獻[13-18]。

本文在概念格屬性約簡和覆蓋粗糙集約簡之間建立聯(lián)系，證明了覆蓋粗糙集的交約簡可以化為概念格的屬性約簡。

1 預(yù)備知識

定義1 稱(V1,V2,E)為一個形式背景，其中V1={x1,x2,…,xs}為對象集，V2={y1,y2,…,yt}為屬性集，E?V1×V2。

本文中用1表示(x,y)∈E，用0表示(x,y)?E，這樣形式背景可以表示成只含0和1的矩陣。

對于形式背景，在對象集X?V1和屬性集Y?V2上分別定義

X′={y∈V2|(x,y)∈E,?x∈X}，

Y′={x∈V1|(x,y)∈E,?y∈Y}。

定義2[2]設(shè)(V1,V2,E)為形式背景，X?V1,Y?V2，如果一個二元組(X,Y)滿足X′=Y且Y′=X，則稱(X,Y)是一個形式概念，簡稱概念。

定理1[2]L(V1,V2，E)是完備格，且有

形式背景(V1,V2,E)中的概念具有如下性質(zhì)(?X1,X2,X?V1，?Y1,Y2,Y?V2)：

(2)X?X″,Y?Y″；

(3) (X,X″)和(Y″,Y)都是概念。

不同的形式背景所對應(yīng)的概念格可能是同構(gòu)的，很多情況下減少對象集和屬性集的某些元素并不改變概念格的格結(jié)構(gòu)，基于此，概念格約簡是一個熱點問題。

在形式背景(V1,V2,E)下，?N?V2，記EN=E∩(V1×N)，?M?V1，記EM=E∩(M×V2)，那么(V1,N,EN)和(M,V2,EM)都為形式背景。

定義3[3]設(shè)(V1,V2,E)為形式背景，如果存在N?V2使得L(V1,V2,E)?L(V1,N,EN)，則稱N為相容屬性集，進一步，如果?y∈N，L(V1,N-{y},EN-{y})與L(V1,N,EN)不同構(gòu)，則稱N為(V1,V2,E)的屬性約簡，此時稱(V1,N,EN)為屬性約簡的形式背景。

定理2[2]V2-{y}是(V1,V2,E)的相容屬性集，當(dāng)且僅當(dāng)存在Y?V2,y?Y但有{y}′=Y′。

定義4[19]設(shè)U是一個論域，C是U的子集族，如果C中的所有子集都非空，而且∪C=U，則我們稱C是U的覆蓋。

2 形式概念分析與覆蓋的關(guān)系

定義5 設(shè)F={Aj|j∈J}是U的覆蓋，令V1=U,V2=F，對于任意x∈V1,Ai∈V2，規(guī)定(x,Ai)∈E當(dāng)且僅當(dāng)x∈Ai，則(V1,V2,E)構(gòu)成形式背景，稱(V1,V2,E)為F導(dǎo)出的形式背景。

例1 設(shè)U={x1,x2,x3,x4}，F(xiàn)={Ai|i=1,2,3,4}，其中Ai={x1},A2={x2,x3,x4},A3={x4},A4={x1,x2}，由F導(dǎo)出的形式背景(V1,V2,E)如表1。

圖1 由例1的覆蓋導(dǎo)出的概念格L(V1,V2,E)

A1A2A3A4x11001x20100x30100x40111

定義6 設(shè)(V1,V2,E)為覆蓋F導(dǎo)出的形式背景，則稱L(V1,V2,E)為F導(dǎo)出的概念格。

例2 接例1，圖1為F={Ai|i=1,2,3,4}所導(dǎo)出的概念格。

這里，形式概念分別為C1=(?,V2)，C2=({x4},{A2,A3,A4})，C3=({x1},{A1,A4})，C4=({x2,x3,x4},{A2})，C5=({x1,x4},{A4})，C6=(V1,?)。

圖2 由F1導(dǎo)出的概念格

A1A2A4x1101x2010x3010x4011

定義7[19]設(shè)F={Aj|j∈J}是U的覆蓋且A∈F，如果A可以表示成F-{A}的若干元之交，則稱A為F的交可約元，否則稱A為F的交不可約元；如果A可以表示成F-{A}的若干元之并，則稱A為F的并可約元，否則稱A為F的并不可約元；如果F中每個集合A都為F的交不可約元，則稱F交不可約的，否則稱為交可約的；如果F中每個集合A都為F的并不可約元，則稱F并不可約的，否則稱為并可約的。

由定義7可知，如果A為F的交可約元，則∩(F-{A})=∩F且∪(F-{A})=∪F；如果A為F的并不可約元，則∩(F-{A})=∩F且∪(F-{A})=∪F。

定義8 設(shè)F={Aj|j∈J}是U的非空子集族，如果Fi?F為交可約元之集，則稱集族(F-Fi)為F的交約簡，其中F的交約簡是唯一的且記為∩-reduct(F)。

例4 接例1，因為A3=A2∩A4，所以A3是覆蓋F的交可約元，由于A3是覆蓋F的唯一交可約元，因此∩-reduct(F)={A1,A2,A4}。

定理3 設(shè)F={Aj|j∈J}是U的覆蓋，則A∈F為F的交可約元，當(dāng)且僅當(dāng)F-{A}是F導(dǎo)出形式背景(V1,V2,E)的相容屬性集。

例5 由例3和例4可知，A3是覆蓋F的交可約元，因此F-{A3}是F導(dǎo)出形式背景(V1,V2,E)的相容屬性集。

3 結(jié) 語

我們將概念格約簡理論與覆蓋粗糙集交約簡相聯(lián)系，結(jié)果表明覆蓋粗糙集的交約簡可以納入到概念格屬性約簡理論當(dāng)中，這是二者之間的初步探討。關(guān)于并約簡與概念格屬性約簡的關(guān)系我們將在后續(xù)工作中討論。

[1] WILLE R.Restructuring lattice theory:an approach based on hierarchies of concept[C]//R.Ivan Rival(ED.),Ordered Sets.Boston:Reidel,Dordecht,1982:445-470.

[2] GANTER B,WILLE R.Formal Concept Analysis[M]//Mathematical Foundations.Berlin:Springer,1999.

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

[4] WU Wei-zhi,YEE Leung,MI Ju-sheng.Granular computing and knowledge reduction in formal contexts[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(10):1461-1474.

[5] ELLOUMI Samir,JAAM Jihad,HASNAH Ahmed,et al.A multi-level conceptual data reduction approach based on the Lukasiewicz implication[J].Information Sciences,2004(163):253-262.

[6] LI Li-feng,ZHANG Jian-ke.Attribute reduction in fuzzy concept lattices based on the T implication[J].Knowledge-Based Systems,2010(23):497-503.

[7] YANG Hong-zhi,YEE Leung,SHAO Ming-wen.Rule acquisition and attribute reduction in real decision formal contexts[J].Soft Computing,2011(15):1115-1128.

[8] LI Jin-hai,MEI Chang-lin,LV Yue-jin.Knowledge reduction in real decision formal contexts[J].Information Sciences,2012(189):191-207.

[9] 祝峰,王飛躍.關(guān)于覆蓋廣義粗集的一些基本結(jié)果[J].模式識別與人工智能,2002,15(1):6-13.

[10] ZHU William,WANG Fei-yue.Reduction and axiomization of covering generalized rough sets[J].Information Sciences,2003(3):217-230.

[11] LI Fei,YIN Yun-qiang.Approaches to knowledge reduction of covering decision systems based on information theory[J].Information Sciences,2009(179):1704-1794.

[12] 朱鵬飛,胡清華,于達仁.基于隨機化屬性選擇和鄰域覆蓋約簡的集成學(xué)習(xí)[J].電子學(xué)報,2012(2):273-279.

[13] YAO Yi-yu.A Comparative Study of Formal Concept Analysis and Rough Set Theory in Data Analysis[J].Lecture Notes in Computer Science,2004(3066):59-68.

[14] LAI Hong-liang,ZHANG De-xue.Concept lattices of fuzzy contexts: Formal concept analysis vs. rough set theory[J].International Journal of Approximate Reasoning,2009(50):695-707.

[15] WOLLF Karl Erich.A Conceptual View of Knowledge Bases in Rough Set Theory[J].Lecture Notes in Computer Science,2005(2001):220-228.

[16] WEI Ling,QI Jian-jun.Relation between concept lattice reduction and rough set reduction[J].Knowledge-Based Systems,2010(23):934-938.

[17] LIU Min,SHAO Ming-wen,ZHANG Wen-xiu,et al.Reduction method for concept lattices based on rough set theory and its application [J].Computers & Mathematics with Applications,2007(53):1390-1410.

[18] 徐偉華,王巧榮,張先韜.不協(xié)調(diào)格值目標(biāo)信息系統(tǒng)的近似約簡[J].計算機工程,2011,37(23):69-71.

[19] YAO Yi-yu,YAO Bing-xue.Covering based rough set approximations[J].Information Sciences,2012(200):91-107.

[責(zé)任編輯：魏 強]

Abstract: The relationships between attribute reduction theory in concept lattice and reduction in covering rough set are studied based on the formal context corresponding with covering rough set. The results show that formal context and covering rough set are equivalent in some sense, and the occurrence that join reduction of covering rough set is a kind of reduction theory of concept lattice is proved.

Keywords: concept lattice; attribute reduction; covering

Relationships of reduction between concept lattice and covering

LI Li-feng, YU Wei

(1.School of Science, Xi’an University of Posts and Telecommunications, Xi’an 710121, China;2.The Chinese People’s Liberation Army 69213 Troops, Kashgar 844900, China)

1673-2944(2014)03-0037-04

2013-11-04

陜西省科學(xué)技術(shù)研究發(fā)展計劃項目(2013JQ1020)；陜西省教育廳自然科學(xué)專項基金資助項目(2013JK1130；2013JK1182)

李立峰(1980—)，男，陜西省西安市人，西安郵電大學(xué)講師，博士研究生，主要研究方向為不確定性推理；俞偉(1985—)，男，青海省樂都縣人，中國人民解放軍69213部隊上尉，主要研究方向為粗糙集理論。

TP18

A