nbhkdz.com冰点文库

形式背景下概念格的一种建格算法

时间:2017-10-16


第 12 卷第 4 期 2013 年 8 月

江 南 大 学 学 报( 自 然 科 学 版) Journal of Jiangnan University( Natural Science Edition)

Vol. 12 Aug.

No. 4 2013

形式背景下概念格的一种建格算法

/>1 2 周 建 , 莫智文

( 1. 攀枝花学院 数学与计算机学院, 四川 攀枝花 617000 ; 2. 四川师范大学 数学与软件科学学院, 四川 成都 610068 ) 要: 在形式背景下的概念分析理论中, 概念格是 其 核 心 的 数 据结 构 之 一, 在 数 据 检索 和 数 据 挖 掘中得到广泛应用。 概念格的建立是这些 应 用 的基 本 前 提, 建 立 概 念格 的过程 也 是 概 念聚 类 的过 摘 文中通过对形式背景中的对象和 属 性 之 间的 二元 关系 简 化为 布 尔 矩阵, 并 对 布 尔 矩阵 进 行 算 程。 法处理, 着重分析了求外延的算法及计算机语言的实现, 得 到 所有 概 念 的 外 延, 而外延所形成的格 是与对应的概念格同构的。 关键词: 概念格; 建格; 算法 中图分类号: TP 181 文献标志码: A 文章编号: 1671 - 7147 ( 2013 ) 04 - 0429 - 03

Study of Establising Lattice Algorithms Based on the Concept Lattice under the Formal Contexs
ZHOU Jian1 , MO Zhiwen2
( 1. School of Mathematics and Computer Science, Panzhihua University, Panzhihua 617000 , China; 2. College of Mathematics and Software Science,Sichuan Normal University,Chengdu 610068 ,China) Abstract: The concept lattice is the core data structure under the formal context and concept analysis. It has been widely applied to the data retrieval and data mining. The concept lattice is a basic premise of the applications, establishing the concept lattice is a conceptual clustering process. This article simplifies the relation between the object and attribute of the formal context as a Boolean matrix,and then processes the Boolean matrix obtaining the extension of a concept,and the lattice formed by extension is isomorphic with the corresponding concept lattice. Key words: concept lattice, to establish concept lattice, algorithm

概念格是研究知识发现、 概念分析、 规则提取 的重要方法, 从形式背景下建立对应的概念格是这 12] 给出了形式背 些应用的基本前提。 参考文献[ 通过文中定理 2 得出求所 景下建立概念格的算法, 有概念外延的方法, 而所有概念的外延构成的集合 这种算 在包含关系下形成的格是与概念格同构的。 法比较适合小的形式背景, 文中着重给出了基于此 算法的 C 语言实现方法。 这种算法输出了所有概念
收稿日期: 2013 - 02 - 20 ; 修订日期: 2013 - 03 - 21 。

的外延。

1

预备知识

[3 ] A, I) 。 定义 1 形式背景为三元组: S = ( U, 其中 U = ( x1 , x2 , …, x n ) 为 S 的对象集, A = { a1 , a2 , …, a m } 为属性集, I ? U ? A, ( x, a) ∈ I 称 x 具有属性 A, ( x, a) ? I 称 x 不具有属性 A, 用 1 表示, 用 0 表示。 U 与 A 之间的二元关系就可以看作一个 这样, 布尔矩阵。

基金项目: 国家自然科学基金项目( 11071178 ) 。 作者简介: 周 建( 1964 —) , 男, 江苏徐州人, 副教授。 主要从事模糊数学、 商空间等研究。 Email: 861215361@ qq. com

430

江 南 大 学 学 报 ( 自 然 科 学 版) X = ( ( ∪ x* )
x∈X *

第 12 卷 ) = ( ∩ x* )
x∈X ** * * = ( ∩[ x] RA ) x∈X *

* B ? A, 设 X ? U, 记 X = { a | a ∈ A, ?x ∈ A, ( x, a) ∈ I} 表示 X 中所有对象具有的属性 ?x ∈ X , * ( x, a) ∈ I} 表示具 集; B = { x | x ∈ U, ?a ∈ B ,

=

( ∪[ x] RA )
x∈X

x] ?∪ [ RA
x∈X

有 B 中所有属性的对象集。 * x* ≠ 假定 S 是正则的: 对 ?x ∈ U 有 x ≠ Φ, * A, a * ≠ U。 对 ?a ∈ A 有 a ≠ Φ ,
[4 ] A, I) , X ? U, B? 定义 2 设形式背景为 S = ( U, * * A, B = X, B) 是 S 上 若满足: X = B , 称二元组( X ,

由定理 1 知 X 是概念的外延, 所以 G ? L U 所以 G = L U 。 推论
[6 ]

{ G , ?, U} 是 与 L( U, A, I) 同 构 的 φ,

完备格。 a2 , …, am } , 构造 G 的方法: 设 A = { a1 , 由于有 公式( a i ∪ a j ) 的布尔矩阵
[7 ] * * = a* 所以先根据形式背景 i ∩ aj , * * a2 , …, a* 的每一列, 输出 a1 , 再依 m , 次对任意两列元素进行布尔积运算, 得到一个新的

X 为概念的外延, B 为概念的内涵。 的概念, B1 ) ,( X2 , B2 ) 的 偏 序 定义 两 个 概 念 的 ( X1 , 关系: ( X1 B1 ) ≤ ( X2 , B2 ) ?X1 ? X2 ( ?B1 ? B2 ) S 则正则形 式 背 景 上 的 所 有 概 念 形 成 一 个 完 备 格
[2 ]

列, 若此列与之前的某列相同则删除, 否则输出此 列值为 1 的元素对应的对象, 直至所有的布 尔 积 为 0。

, A, I) 。 记为 L( U, 其上、 下确界运算:
**

( X1 , B1 ) ∧ ( X2 , B2 ) = ( X1 ∩ X2 , ( B1 ∪ B2 )



3

算法的实现

( X1 , B1 ) ∨ ( X2 , B2 ) = ( ( X1 ∪ X2 ) ** , B1 ∩ B2 ) ( U, A) 是它的最小元。 φ) 是它的最大元,( φ, 概念格简洁地通过偏序关系体现了概念之间 的泛化和特化关系, 每个概念都是外延和内涵的统 一体。 希望通过形式背景 S 或其布尔矩阵, 用更简洁 方便的算法得到全体概念, 或者得到与概念格同构 的一个格。

子函数接受形式背景的布尔矩阵、 属性集和对 n[8], 象集的元素个数 m, 输出概念格的所有概念的 外延。 Void concept ( int m, int n, int a[ 0] ) { int I, j, k, l, p, q, t, b[ n] [ m] ; for( i = 0 ; i < m; i + + ) { for( j = 0 ; j < n; j + + ) If( a[ j* n + i] = = 1 ) 1 ) ; printf ( “\ n” ); er2 t = 0 ; for( i = 0 ; i < m - 1 ; i + + ) { for( j = i + 1 ; j < m; j + + ) { for( k = 0 ; k < n; k + + ) b[ k] [ t] = a[ k* n + i] * b[ k* n + j] ; for( p = 0 ; p < m; p + + ) / * 判断是否为新的 概念 * / for( q = 0 ; q < n; q + + ) { if( a[ q* n + p] ! = b[ q* n + t] ) break; else if( q = = n - 1 ) { goto er1 } } for( l = 0 ; l < n; l + + ) If( b[ l* n + t] = = 1 ) printf ( “% d, ” , l + 1 ) ; printf ( “\ n” ); t + +; er1 if( j = = m - 1 ) break; } } If( t! = 0 ) ( a[ 0] = b[ 0] ; m = t; goto er2 ; } } printf ( “% d, ” , j +

2

原 理

由形式背景下 概 念 的 定 义, 显 然 对 ?a ∈ I , * * * (a , (a ) ), 是一个概念, 这就说明: 在形式背景 对应的布尔矩阵中, 每一列对应一个概念, 这个概 1 念的外延就是这一列中值为 的元素对应的对象的 集合。 那么其他概念如何得到呢? A, I) , 设形式背景 S = ( U, ?D ? A, 定义等价 关系: RD = { ( xi , xj ) | ( xi , x j ) ∈ U ? U, a) = ( x j , a) } ?a ∈ D 有( x i , 则得到 U 上的划分: U / RD = { [ x i] }, [ x i] D | xi ? U D 代表与 x i 在属性集 D 中属性值相同的集合。
[5 ] A, I) 上的任意概念( X , B) , 定理 1 对于 L( U, 有 X = ∪[ x] A。 x∈X

定理 2 设 G = { X | X = D , ?D ? A} , 记 LU = { X | ( X, B ) ∈ L( U, A, I) } ( 所有概念的外延构成的 集合) , 则 G = LU 。 证 L X ? G 显然; ?X ∈ G , 则

*

第4 期

周 建等: 形式背景下概念格的一种建格算法

431

文中研究了构建概念格外延的一种方法、 算法 从与概念格同构的角度得出了快速建 及实现过程, 格的一种方法, 方法简单明了, 方便易行, 算法较易

实现, 可根据数据检索和数据挖掘的需要选择使 对于多值下的形式背景的概念构造, 需要今后 用, 进一步研究。

参考文献( References) :
[1 ]毛华, J] . 大学数学, 2010 , 26 ( 1 ) : 115117. 杨蕾, 窦林立. 矩阵行秩生成概念格的一种算法[ MAO Hua, YANG Lei, DOU Linli. An algorithm of generating concept lattice utilizing row rank of matrix [J] . College 2010 , 26 ( 1 ) : 115117. ( in Chinese) Mathematics, [2 ]田宏, J] . 大连交通大学学报, 2011 , 32 ( 3 ) : 7275. 王绍雯. 概念格的批处理构造算法[ TIAN Hong, WANG Shaowen. Batch constructing algorithm of concept lattice[ J] . Journal of Dalian Jiaotong University, 2011 , 32 ( 3 ) : 7275. ( in Chinese) [3 ] Wille R. Restructuring lattice theory: an approach based on hierarchies of concepts[C]/ / Proceedings of the NATO Advanced Study Institute Series C. Dordrecht, Holland: [ s. n. ] , 1982 , 83 : 445470. [4 ] Ganter B, Wille R. Formal Concept Analysis Mathematical Foundations[ M] . Berlin: Springer, 1999 : 185202. [5 ]苗夺谦, M] . 北京: 科学出版社, 2007 : 256259. 王国胤. 粒计算: 过去、 现在与展望[ [6 ]张贤勇, J] . 数学的实践与认识, 2006 ( 11 ) : 193197. 熊方, 莫智文. 覆盖空间及粗糙集与拓扑的统一[ XIONG Fang, MO Zhiwen. Covering space and the unification of rough sets and topology[ J] . Mathematics in ZHANG Xianyong, Practice and Theory, 2006 ( 11 ) : 193197. ( in Chinese) J] . 哈尔滨师范大学学报, 2010 , 26 ( 2 ) : 2731. [7 ]李海霞. 概念格的一种纵向合并算法[ LI Haixia. A vertical union algorithm of concept lattice[J] . Journal of Harbin Normal University, 2010 , 26 ( 2 ) : 2731. ( in Chinese) [8 ]郑金英, J] . 硅谷, 2011 ( 22 ) : 1820. 滕春霞. 概念格构造算法的现状与发展前景[ ZHEN Jinying, TENG Chunxia. Current situation and development prospect of constructing algorithm of concept lattice[J] . 2011 ( 22 ) : 1820. ( in Chinese) Silicon Valley,

( 责任编辑: 杨 勇)