面向对象概念格的压缩

陈永平，杨思春

1.马鞍山职业技术学院计算机系，安徽马鞍山 243000

2.安徽工业大学计算机学院，安徽马鞍山 243002

面向对象概念格的压缩

陈永平1，杨思春2

1.马鞍山职业技术学院计算机系，安徽马鞍山 243000

2.安徽工业大学计算机学院，安徽马鞍山 243002

1 引言

概念格理论，又称形式概念分析，是由德国数学家Wille于1982年提出的[1]，是进行数据分析的一种有效工具，该理论是根据数据集中对象和属性间的二元关系建立的一种概念层次结构，体现了概念间的泛化和特化的关系。目前，该理论已应用到数据决策分析、信息检索、数据挖掘、软件工程和知识发现等领域。粗糙集理论由Pawlak提出的，它是一种处理模糊和不确定知识的计算工具，已被成功地应用于决策分析、数据挖掘等领域。

虽然，粗糙集理论和形式概念分析为我们提供了两种不同的数据分析方法，它们以不同的角度研究数据集合中所隐含的知识；但是概念格理论和粗糙集理论又是相互关联、相互补充，在研究方法上相互借鉴、相互融合，为数据分析提供了新的研究方法[2-3]。Gediga、Dntsch[4]和Yao[5]等把粗糙集理论引入到概念格理论中，从而定义了面向对象概念格和面向属性概念格，并且进一步研究了这两种概念格之间的关系。

概念格的压缩由于概念格中的节点数量是指数级的，导致数据与概念格也变得十分复杂，所以有必要对概念格进行压缩，简化知识库，从而可以快速地从复杂数据中进行知识发现，做出高效的决策。文献[6-7]分别利用SVD方法和模糊聚类方法对经典概念格进行压缩，不能适用于面向对象概念格；文献[8]根据对象的相似度或者属性的相似度来控制面向属性概念格中节点的个数，以实现对面向属性概念格的压缩。然而概念是由对象和属性共同确定，仅考虑对象相似度或属性相似度都不能全面地反映概念的特性，因此本文引入了概念间相似度的一种新的计算方法，由对象和属性共同确定概念之间的相似程度，进而产生概念邻域，并根据概念间相似程度来控制概念邻域的大小，从而控制面向对象概念格中节点的个数，实现面向对象概念格的压缩。与现有文献的其他压缩方法相比，本文提出的方法当选取的参数值较小时，压缩效果明显。

2 预备知识

3 面向对象概念格的压缩

该定理表明，使用本文方法对面向对象概念格进行压缩后，不会产生新的概念节点，并且压缩后的概念集包含于压缩前的概念集中，即压缩后的概念集为压缩前的概念集的子集。

4 例子

设(G，M，R)为形式背景，对象集G={1，2，3，4，5，6}，属性集M={a，b，c，d，e，f，h}，其中(n，m)∈R时用1表示，(n，m)∉R用0表示，如表1所示。

表1 形式背景(G，M，R)

由表1可以得到形式背景(G，M，R)中的关系R的集合共有19项，并分别令为：t1=(1，a)，t2=(1，c)，t3=(1，d)，t4=(1，e)，t5=(1，f)，t6=(2，a)，t7=(2，c)，t8=(2，f)，t9=(3，b)，t10=(3，e)，t11=(4，b)，t12=(4，e)，t13=(4，f)，t14=(4，h)，t15=(5，a)，t16=(6，a)，t17=(6，b)，t18=(6，e)，t19=(6，f)。这样关系R={t1，t2，…，t19}。并通过计算得到表1的形式背景(G，M，R)的面向对象概念格LS(G，M，R)，如图1所示。

对于形式背景(G，M，R)，如表1所示，利用方法对面向对象概念格进行压缩，其中的α和β的取值为0.5。

图1 LS(G，M，R)

步骤3利用本文方法（式（2））对面向对象概念格进行压缩，压缩后的面向对象概念格如图2所示。

图2 γ=0.5时的LS0(G，M，R)

另外，本文还对参数γ=0.31和γ=0.80分别进行计算，得到压缩后的面向对象概念格分别如图3和图4所示。

图4 γ=0.80时的LS0(G，M，R)

通过上述计算可以看出，γ取不同值，面向对象概念格的压缩效果不同，如果γ取值较小时，概念格的压缩比较明显，γ取值较大时，概念格的压缩不是很明显。因此，对于γ值的选取，要根据实际应用和实际压缩的需要，选取满足要求的γ值，使压缩后的面向对象概念格效果最优。

5 结束语

概念格理论是知识处理与分析的一种有力工具，在知识发现和数据挖掘等众多领域有着重要的应用。本文引入了概念间相似度的新的计算方法，由对象和属性共同确定概念之间的相似程度，进而产生概念邻域，并根据概念间相似程度来控制概念邻域的大小，删除不必要的节点，以得到控制面向对象概念格中节点的个数，实现了面向对象概念格的压缩和知识库简化。与现有的其他压缩方法相比，本文提出的方法中当参数γ值较小时，压缩效果明显。后续研究，将对面向对象概念格压缩的应用以及参数α、β、γ取值进行探讨。

[1]Wille R.Restructuring lattice theory：an approach based on hierarchies of concepts[M]//Rival I.Ordered Sets.Dordrecht-Boston：Reidel，1982：445-470.

[2]宋笑雪，张文修，李红.变精度对象概念格的构造及其性质[J].计算机科学，2010，37（12）：197-200.

[3]韩中华，马斌，许可，等.基于谱系聚类的粗糙集数据挖掘预处理方法[J].计算机工程与应用，2008，44（2）：194-196.

[4]Gediga G，Dntsch I.Modal style operators in qualitative data analysis[C]//Proceedings of the IEEE International Conference on Data Mining，2002：155-162.

[5]Yao Y Y.A comparative study of formal concept analysis and rough set theory in data analysis[C]//Proceedings of 3rd International Conference（RSCTC’04），2004：59-68.

[6]Cheung K S K，Vogel D.Complexity reduction in lattice based information retrieval[J].Information Retrieval，2005，8：285-299.

[7]Kumar A C，Srinivs S.Concept lattice reduction using fuzzy K-meansclustering[J].ExpertSystemswithApplications，2010，37（3）：2696-2704.

[8]魏玲，李强.面向属性概念格基于覆盖的压缩[J].电子科技大学学报，2012，41（2）：299-304.

[9]姚广，魏玲，王磊.合成背景的面向属性概念生成[J].西北大学学报：自然科学版，2010，40（1）：1-4.

[10]王虹，张文修.基于概念格的形式背景的知识约简[J].模式识别与人工智能，2005，18（6）：641-645.

[11]王虹，万金凤.协调决策形式背景的属性约简[J].工程数学学报，2006，23（3）：455-460.

[12]Zhu W.Relationship between generalized rough sets based on binary relation and covering[J].Information Seienees，2009，179：210-225.

CHEN Yongping1,YANG Sichun2

1.Department of Computer Science,Ma’anshan Technical College,Ma’anshan,Anhui 243000,China
2.School of Computer Science,Anhui University of Technology,Ma’anshan,Anhui 243002,China

Concept lattice theory is a powerful tool for processing and analysis of knowledge,knowledge discovery and data mining,and other important applications.A new method of similarity calculation of concepts is introduced.Objects and properties are both used to determine the similarity of concepts,generate the concept neighborhood and control its size according to the similarity degree of concepts.And then,it removes unnecessary nodes,to control the number of nodes in the object-oriented concepts,realization of object-oriented concepts simplify the compression and the knowledge base.The examples show that the compressing of object-oriented concept lattice is more effect when parameter values are smaller.

formal context;concept lattice;object-oriented concept lattice;similarity degree;neighborhood

概念格理论是知识处理与分析的一种有力工具，在知识发现和数据挖掘等众多领域有着重要的应用。引入了概念相似度新的计算方法，由对象和属性共同确定概念之间的相似程度，进而产生概念邻域，并根据概念间相似程度来控制概念邻域的大小，删除不必要的节点，从而控制面向对象概念格中节点的个数，实现面向对象概念格的压缩和知识库简化。示例表明，当参数的值较小时，压缩效果明显。

形式背景；概念格；面向对象概念格；相似度；邻居

A

TP18

10.3778/j.issn.1002-8331.1303-0451

CHEN Yongping,YANG Sichun.Reduction of object-oriented concept lattices.Computer Engineering and Applications, 2013,49（19）：119-122.

安徽省高校省级自然科学基金（No.KJ2010B223）；安徽省高校省级自然科学研究重点项目（No.KJ2011A048）。

陈永平（1969—），男，副教授，主要研究方向为人工智能等；杨思春，男，博士研究生，副教授，硕导，主要研究方向为人工智能，自然语言处理等。E-mail：cyp7222@sina.com

2013-03-28

2013-06-13

1002-8331（2013）19-0119-04

◎图形图像处理◎