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

李立峰， 俞 偉

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

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

李立峰1， 俞 偉2

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

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

概念格； 屬性約簡(jiǎn)； 覆蓋

0 引 言

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

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

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

1 預(yù)備知識(shí)

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

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

對(duì)于形式背景，在對(duì)象集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，如果一個(gè)二元組(X,Y)滿足X′=Y且Y′=X，則稱(X,Y)是一個(gè)形式概念，簡(jiǎn)稱概念。

定理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)都是概念。

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

在形式背景(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為相容屬性集，進(jìn)一步，如果?y∈N，L(V1,N-{y},EN-{y})與L(V1,N,EN)不同構(gòu)，則稱N為(V1,V2,E)的屬性約簡(jiǎn)，此時(shí)稱(V1,N,EN)為屬性約簡(jiǎn)的形式背景。

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

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

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

定義5 設(shè)F={Aj|j∈J}是U的覆蓋，令V1=U,V2=F，對(duì)于任意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中每個(gè)集合A都為F的交不可約元，則稱F交不可約的，否則稱為交可約的；如果F中每個(gè)集合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的交約簡(jiǎn)，其中F的交約簡(jiǎn)是唯一的且記為∩-reduct(F)。

例4 接例1，因?yàn)锳3=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é) 語(yǔ)

我們將概念格約簡(jiǎn)理論與覆蓋粗糙集交約簡(jiǎn)相聯(lián)系，結(jié)果表明覆蓋粗糙集的交約簡(jiǎn)可以納入到概念格屬性約簡(jiǎn)理論當(dāng)中，這是二者之間的初步探討。關(guān)于并約簡(jiǎn)與概念格屬性約簡(jiǎ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] 張文修,魏玲,祈建軍.概念格的屬性約簡(jiǎn)理論與方法[J].中國(guó)科學(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].模式識(shí)別與人工智能,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] 朱鵬飛,胡清華,于達(dá)仁.基于隨機(jī)化屬性選擇和鄰域覆蓋約簡(jiǎn)的集成學(xué)習(xí)[J].電子學(xué)報(bào),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)的近似約簡(jiǎn)[J].計(jì)算機(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é)任編輯：魏 強(qiáng)]

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ā)展計(jì)劃項(xiàng)目(2013JQ1020)；陜西省教育廳自然科學(xué)專項(xiàng)基金資助項(xiàng)目(2013JK1130；2013JK1182)

李立峰(1980—)，男，陜西省西安市人，西安郵電大學(xué)講師，博士研究生，主要研究方向?yàn)椴淮_定性推理；俞偉(1985—)，男，青海省樂(lè)都縣人，中國(guó)人民解放軍69213部隊(duì)上尉，主要研究方向?yàn)榇植诩碚摗?/p>

TP18

A