李立峰， 俞 伟

(1.西安邮电大学 理学院， 陕西 西安 710121;2.中国人民解放军69213部队， 新疆 喀什 844900)

概念格约简与覆盖约简之间的关系

李立峰1， 俞 伟2

(1.西安邮电大学 理学院， 陕西 西安 710121;2.中国人民解放军69213部队， 新疆 喀什 844900)

以一类与覆盖粗糙集相对应的形式背景为工具，对概念格属性约简和覆盖粗糙集约简进行研究，结果表明覆盖粗糙集与形式背景之间存在一一对应关系，并且证明了覆盖粗糙集的交约简可化为概念格的属性约简。

概念格； 属性约简； 覆盖

0 引 言

概念格是根据对象与属性之间的二元关系建立的一种层次结构[1]。作为数据处理的有力工具，概念格被越来越多地应用于知识发现、软件工程、信息检索等领域。近年来，概念格的约简理论是概念格研究领域的一个热点问题。文献[2]通过删掉形式概念中的可约属性和对象来进行概念约简；文献[3]提出在保持格同构的条件下建立概念格属性约简理论和方法；吴伟志[4]基于软计算在决策形式背景中提出了新的约简方法；Elloumi等[5]基于模糊形式背景建立了一个多层次的约简理论；针对文献[5]中建立的概念之集不能构成格结构，文献[6]改进了建格方法，在保持格同构条件下建立了多层次属性约简理论；随后产生了基于区间值形式背景的概念格的属性约简[7-8]。

在粗集理论的众多理论中，覆盖广义粗集理论是近年来发展迅速的一个方向，其中不同的覆盖可以产生相同的上下近似运算，因此，寻找两个覆盖会生成相同的上下近似运算的条件是一个重要的论题。另外，一个剖分去掉其中一个等价类或初等集后就不再是一个剖分了，因此不存在冗余问题；而一个覆盖去掉其中一个子集成员后仍然可以是一个覆盖，而且还可能生成与原覆盖相同的上下近似运算，这就表明一个覆盖可能会有冗余成分存在，这样，将一个覆盖的冗余成分去掉也是一个重要论题。覆盖约简概念由此产生[9-12]，通过它可以将一个覆盖的所有冗余部分去掉。因此，覆盖约简是粗糙集约简理论的一个热点研究方向。关于概念格和粗糙集的结合研究一直是热点问题，如文献[13-18]。

本文在概念格属性约简和覆盖粗糙集约简之间建立联系，证明了覆盖粗糙集的交约简可以化为概念格的属性约简。

1 预备知识

定义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]设(V1,V2,E)为形式背景，X⊆V1,Y⊆V2，如果一个二元组(X,Y)满足X′=Y且Y′=X，则称(X,Y)是一个形式概念，简称概念。

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

形式背景(V1,V2,E)中的概念具有如下性质(∀X1,X2,X⊆V1，∀Y1,Y2,Y⊆V2)：

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

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

不同的形式背景所对应的概念格可能是同构的，很多情况下减少对象集和属性集的某些元素并不改变概念格的格结构，基于此，概念格约简是一个热点问题。

在形式背景(V1,V2,E)下，∀N⊆V2，记EN=E∩(V1×N)，∀M⊆V1，记EM=E∩(M×V2)，那么(V1,N,EN)和(M,V2,EM)都为形式背景。

定义3[3]设(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)不同构，则称N为(V1,V2,E)的属性约简，此时称(V1,N,EN)为属性约简的形式背景。

定理2[2]V2-{y}是(V1,V2,E)的相容属性集，当且仅当存在Y⊆V2,y∉Y但有{y}′=Y′。

定义4[19]设U是一个论域，C是U的子集族，如果C中的所有子集都非空，而且∪C=U，则我们称C是U的覆盖。

2 形式概念分析与覆盖的关系

定义5 设F={Aj|j∈J}是U的覆盖，令V1=U,V2=F，对于任意x∈V1,Ai∈V2，规定(x,Ai)∈E当且仅当x∈Ai，则(V1,V2,E)构成形式背景，称(V1,V2,E)为F导出的形式背景。

例1 设U={x1,x2,x3,x4}，F={Ai|i=1,2,3,4}，其中Ai={x1},A2={x2,x3,x4},A3={x4},A4={x1,x2}，由F导出的形式背景(V1,V2,E)如表1。

图1 由例1的覆盖导出的概念格L(V1,V2,E)

A1A2A3A4x11001x20100x30100x40111

定义6 设(V1,V2,E)为覆盖F导出的形式背景，则称L(V1,V2,E)为F导出的概念格。

例2 接例1，图1为F={Ai|i=1,2,3,4}所导出的概念格。

这里，形式概念分别为C1=(∅,V2)，C2=({x4},{A2,A3,A4})，C3=({x1},{A1,A4})，C4=({x2,x3,x4},{A2})，C5=({x1,x4},{A4})，C6=(V1,∅)。

图2 由F1导出的概念格

A1A2A4x1101x2010x3010x4011

定义7[19]设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 设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 设F={Aj|j∈J}是U的覆盖，则A∈F为F的交可约元，当且仅当F-{A}是F导出形式背景(V1,V2,E)的相容属性集。

例5 由例3和例4可知，A3是覆盖F的交可约元，因此F-{A3}是F导出形式背景(V1,V2,E)的相容属性集。

3 结 语

我们将概念格约简理论与覆盖粗糙集交约简相联系，结果表明覆盖粗糙集的交约简可以纳入到概念格属性约简理论当中，这是二者之间的初步探讨。关于并约简与概念格属性约简的关系我们将在后续工作中讨论。

[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].中国科学E辑:信息科学,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] 祝峰,王飞跃.关于覆盖广义粗集的一些基本结果[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] 朱鹏飞,胡清华,于达仁.基于随机化属性选择和邻域覆盖约简的集成学习[J].电子学报,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] 徐伟华,王巧荣,张先韬.不协调格值目标信息系统的近似约简[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.

[责任编辑：魏 强]

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

陕西省科学技术研究发展计划项目(2013JQ1020)；陕西省教育厅自然科学专项基金资助项目(2013JK1130；2013JK1182)

李立峰(1980—)，男，陕西省西安市人，西安邮电大学讲师，博士研究生，主要研究方向为不确定性推理；俞伟(1985—)，男，青海省乐都县人，中国人民解放军69213部队上尉，主要研究方向为粗糙集理论。

TP18

A