文章快速检索 高级检索

Concept acquisition based on the down-set lattice of irreducible elements
SHI Hui, HE Miao, WEI Ling
Department of Mathematics, Northwest University, Xi'an 710127, China
Abstract: As an efficient tool for knowledge acquisition,formal concept analysis has been applied to many fields. Based on a formal context,the arrow operator proposed by Wille is used to find the join-irreducible elements(meet-irreducible elements)of a concept lattice firstly,and then the down-set lattice of the extents(intents)of the join-irreducible elements(meet-irreducible elements)can be obtained; then an operation is defined on the down-set lattice,and the intents(extents)of the concept lattice can be obtained,which can be expanded to the concepts; finally,this method is used to complete an incomplete formal context. The completion method combines the lattice theory and the formal concept analysis,reflects the importance of irreducible elements which simplifies the structure of the concept lattice,and the method is visual and clear.
Key words: formal context     down-set lattice     concept lattice     irreducible element     formal concept analysis     concept acquisition

1 理论基础

gG,记{g}*g*; ∀mM,记{m}′为m′。若∀gG,,g*≠M,且∀mM,,,则称形式背景(G,M,I)是正则的。本文提到的形式背景都是正则的。

L(G,M,I)是完备格,称为概念格。

1)x≠0(如果L有零元);

2) x=b(a,bL)。

1)对象概念是并不可约元⇌存在一个mM，使gm;

2)属性概念是交不可约元⇌存在一个gG，使;

3)对象概念是并不可约元⇌存在一个mM，使

4)属性概念是交不可约元⇌存在一个gG，使

2 基于不可约元下集格的概念获取

2)当χ1χ2时有。由于,且*算子有逆序性,即对X1X2,有,从而有:

2)当A1A2时有∪Ai⊆∪Aj,AiA1,AjA2。由于f2(A)=(∪A)′且′算子有逆序性,即对A1A2,有A2′⊆A1′,从而有: f2(A2)⊆f2(A1)。

 序号 a b c d e 1 × × × 2 × × × × 3 × × × 4 × × × 5 × × ×

 序号 a b c d e

 图 1 JG(L)的Hasse图 Fig. 1 Hasse of JG(L)

,计算f1(χ),得到:

 图 2 L(G,M,I) Fig. 2 L(G,M,I)

 图 3 MM(L)的Hasse图 Fig. 3 MM(L)

,{{a,e}},{{b}},{{c}},{{a,e},{b}},{{a,e},{c}},{{b},{c}},{{b,d},{b}},{{a,e},{b,d},{b}},{{a,e},{b},{c}},{{b,d},{b},{c}},{{a,e},{b,d},{b},{c}}}。

Aο(MM(L)),计算f2(A)得到

 图 4 L(G,M,I) Fig. 4 L(G,M,I)
3 不完备形式背景的完备化

 序号 a b c d e 1 1 0 # 1 0 2 0 1 0 # 0 3 1 0 1 0 1 4 1 1 0 0 1

1)将不完备形式背景(G,M,I,#)中的#全部替换为0,得到形式背景(G,M,I1),如表 4所示。将不完备形式背景(G,M,I,#)中的#全部替换为1,得到形式背景(G,M,I2),如表 5所示。

 序号 a b c d e 1 1 0 0 1 0 2 0 1 0 0 0 3 1 0 1 0 1 4 1 1 0 0 1

 序号 a b c d e 1 1 0 1 1 0 2 0 1 0 1 0 3 1 0 1 0 1 4 1 1 0 0 1

2)概念格L1图 5所示,概念格L2图 6所示:

 图 5 概念格L1 Fig. 5 L(G,M,I)
 图 6 概念格L2 Fig. 6 L(G,M,I)

3)概念格L2的并不可约元如下:

4)将所有并不可约元的外延构成集合:JG(L2)={{1},{2},{3},{4}}。其Hasse图如图 7所示。

 图 7 JG(L2)的Hasse图 Fig. 7 Hasse of JG(L2)

5) JG(L2)的下集格如下:

,{{1}},{{2}},{{3}},{{4}},{{1},{2}},{{1},{3}},{{1},{4}},{{2},{3}},{{2},{4}},{{3},{4}},{{1},{2},{3}},{{1},{2},{4}},{{1},{3},{4}},{{2},{3},{4}},{{1},{2},{3},{4}}}。

6) ,在形式背景(G,M,I1)上计算f1(χ),可得

7)根据集合P2的定义,可得:P2={{d},{a,c},{b,d},{a,c,d}}

8)根据映射h21得到I(1,c)=0,I(2,d)=0。从而得到补全后的完备的形式背景(G,M,I3)如表 6所示:

 序号 a b c d e 1 1 0 0 1 0 2 0 1 0 0 0 3 1 0 1 0 1 4 1 1 0 0 1

1)概念格L2的交不可约元如下:

2)将所有交不可约元的内涵构成集合:MM(L2)={{a},{d},{b},{a,e},{a,c}}。其Hasse图如图 8所示:

 图 8 MM(L2)的Hasse图 Fig. 8 Hasse of MM(L2)

3)MM(L2)的下集格如下:

4)∀Aο(MM(L2)),在形式背景(G,M,I1)上计算f2(A)可得:

5)根据集合Q2的定义,可得: Q2={{1,2},{1,3},{2}}

 序号 a b c d e 1 1 0 0 1 0 2 0 1 0 0 0 3 1 0 1 0 1 4 1 1 0 0 1

4 结束语

 [1] WILLE R. Restructuring lattices theory: an approach on hierarchies of concepts[M]. Dordrecht,Holland: Springer, 1982 : 445 -470. [2] CARPINETO C,ROMANO G. Concept data analysis: theory and application[M].[S.l.]:John Wiley & Sons,2004: 21-35. [3] GODIN R. Incremental concept formation algorithm based on Galois lattices[J]. Computational Intelligence , 1995, 11 (2) : 246-267 DOI:10.1111/coin.1995.11.issue-2 [4] HO T B. Discovering and using knowledge from unsupervised data[J]. Decision Support System , 1997, 21 (1) : 29-42 DOI:10.1016/S0167-9236(97)00011-0 [5] BELOHLAVEK R. fuzzy closure operators[J]. Journal of Mathematical Analysis and Applications , 2001 (262) : 473-489 [6] NOURINE L, RAYNAUD O. A fast algorithm for building lattices[J]. Information Processing Letters , 1999, 47 : 111-112 [7] BODAT J P. Calcul pratique du treillis de galois d'ume correspondence[J]. Math Sci Hum , 1986, 96 : 31-47 [8] HO T B. Incremental conceptual clustering in the framework of galois lattice[C]//Proceedings of First Pacific-Asia Conference. Knowledge Discovery and Data Mining: Techniques and Applications. [S.l.],1997: 49-64. [9] 李云, 刘宗田, 陈崚, 等. 多概念格的横向合并算法[J]. 电子学报 , 2004, 32 (11) : 1847-1854 LI Yun, LIU Zongtian, CHEN Ling. Horizontal union algorithm of multiple concept lattices[J]. Acta Electronica Sinica , 2004, 32 (11) : 1847-1854 [10] 万青, 魏玲, 李涛. 一种基于并不可约元的建格新方法[J]. 西北大学学报 , 2013, 43 (1) : 10-14 WAN Qing, WEI Ling, LI Tao. A new method of building lattice based on join-irreducible[J]. Journal of Northwest University: Natural Science Edition , 2013, 43 (1) : 10-14 [11] GANTER B, WILLE R. Formal Concept Analysis[M]. Formal Concept Analysis New York: Mathematical Foundations.SpringerVerlag, 1999 : 21 -24. [12] DAVEY B A, PRIESTLEY H A. Introduction to lattices and order[M]. Cambridge: Cambridge University Press, 2002 . [13] 李金海.面向规则提取的概念格约简方法及其算法实现[D].西安:西安交通大学,2012: 45-63. LI Jinhai. Acquisition oriented reduction methods for concept lattices and their implementation algorithms[D].Xi'an: Xi'an Jiao Tong University,2012: 45-63. [14] 康向平, 李德玉, 李瑞萍. 基于多划分的不完备信息系统的完备化模型[J]. 计算机工程与设计 , 2011 (9) : 3131-3134 KANG Xiangping, LI Deyu, LI Ruiping. Completion model of incomplete information system based on multiple-partitions[J]. Computer Engineering and Design , 2011 (9) : 3131-3134
DOI: 10.3969/j.issn.1673-4785.201307019

0

#### 文章信息

SHI Hui, HE Miao, WEI Ling

Concept acquisition based on the down-set lattice of irreducible elements

CAAI Transactions on Intelligent Systems, 2014, 9(2): 244-250
http://dx.doi.org/10.3969/j.issn.1673-4785.201307019