基于相容模糊概念的规则提取方法

胡小康，王俊红

(山西大学 计算机与信息技术学院，山西 太原 030006)



基于相容模糊概念的规则提取方法

胡小康，王俊红

(山西大学 计算机与信息技术学院，山西 太原 030006)

摘要：概念格是具有严格数学模型的数据分析与规则提取的一种有效工具，大部分情况下是在完备的精确形式背景即二值背景下进行研究,然而在现实生活中遇到的大多数情况是不完备的模糊形式背景，不完备模糊形式背景中包含许多不确定的信息，其上的知识表示与完备形式背景下的知识表示既有区别又有联系。为了研究两者的内在联系，本文定义了相似模糊概念和相容模糊概念,构建了相似模糊概念格和建立了在不完备模糊形式背景下相容模糊概念之间的偏序关系，进而设计出面向不完备模糊形式背景下的关联规则挖掘算法.最后通过实验验证了该方法的有效性和可行性。

关键词：形式背景；概念格；相似模糊概念；相容模糊概念；知识获取；关联规则；偏序关系；相容关系

概念格也称为Galois格，又叫做形式概念分析，由德国的Wille[1]在20世纪80年代提出。概念格的每个节点是一个形式概念，概念格结构模型是形式概念分析中的核心结构，它描述了对象和属性之间的关系。概念格是研究知识表示和推理的理论，它具有严格的数学模型，已经在机器学习、数据挖掘、软件工程等领域[2-6]得到广泛的应用。

通常我们研究的形式背景是完备的，也就是对象和属性之间的关系是已知的，但是在实际应用中，大多数信息是模糊[7]的、复杂的。更糟糕的是在现实生活中由于人的认知能力以及机器的局限性，人们经常不能准确地判断对象和属性之间的关系，使得获取的形式背景经常存在数据缺失，从而得到形式背景是不完备的模糊形式背景，这对于知识获取产生了很大障碍。因此不完备模糊形式背景的研究获得了广泛的关注。

粗糙集理论中的信息系统就是形式概念分析中的形式背景，对于不完备信息系统[8]，粗糙集已通过相容关系、非对称相似关系等进行了一些研究。在形式概念分析中Liu J等在文献[9]中将多值形式背景转变为单值形式背景后，通过把不完备属性在不同对象上的不同取值进行扩展，从而得到了完备的形式背景来进行概念的提取。Dubois D等在文献[10]提出了利用概率论来解决不完备形式背景的方法。Krupka M等在文献[11]中定义了不完备的模糊形式背景，然后提出了在不完备模糊形式背景下构建概念格的方法。Djouadi Y等在文献[12] 中将不完备模糊形式背景中的隶属度值均采用区间值来表示，将不完备模糊形式背景转化为区间值模糊形式背景(interval-valued fuzzy formal concept,IVFF)，在此基础上提出了基于区间值形式背景的概念格构建方法。Li J H等在文献[13]中提出了在不完备形式背景下构建相似概念格的方法，此外基于相似概念格还研究了在不完备的决策形式背景下获取规则的方法。上述研究中，无论是将不完备形式背景转化为区间值形式背景，还是对不完备属性进行扩展来构造概念格的方法，仅仅适用于形式背景中数据量缺失较少的情况。当形式背景中数据缺失量较大时，所构造的概念格中包含有大量不确定的信息，这对知识获取造成了很大影响。

本文为了减少形式背景中数据缺失量对知识获取的影响，提出并定义了相似模糊概念和相容模糊概念并给出了相容模糊概念的构建方法，建立了相容模糊概念之间的偏序关系，进而设计面向模糊不完备信息的关联规则挖掘算法。

1基本概念

1.1形式概念分析

定义1[1]一个形式背景K=(G,M,I)是一个三元组 ，其中G是对象集合，M是属性集合，I是G与M之间的一个二元关系gIm或(g,m)∈I，表示对象g具有属性m。在形式背景中定义式(1)和式(2)：

(1)

(2)

表1　形式背景

1){∅,(a,b,c,d)}；

2){(x1),(a,d)}；

3){(x3),(a,c)}；

4){(x2),(b,c)}；

5){(x1,x3),(a)}；

6){(x2,x3,x4),(c)}；

7){(x1,x2,x3,x4),∅}。

图1　表1对应概念格的Hasse图Fig.1　Hasse diagram of table 1

1.2模糊形式概念

定义3[14]一个模糊形式背景是一个三元组(G′,M′,I′)，其中G′是对象的有限集，M′是属性有限集，I′是G′×M′的模糊集合。(g,m)∈I′有一个隶属度值u(g,m)∈[0,1] 。

定义4[14]给定一个模糊形式背景K′={G′,M′,I′=φ(G′×M′)}和一个置信度阈值T=[t1,t2],在形式背景中定义式(3)与式(4)：

(3)

式中A⊆G′。

(4)

式中B⊆M′。

模糊形式背景(G′,M′,I′)同置信度阈值T下的一个二元组(A,B)(A⊆G′,B⊆M′)是模糊形式概念，当且仅当FA(A)=B与FO(B)=A同时成立。A、B分别叫做模糊形式背景的模糊外延和模糊内涵。

定义5[14](A1,B1)和(A2,B2)是形式背景(G′,M′,I′)的两个模糊概念。(A1,B1)是(A2,B2)的子概念，记作(A1,B1)≤(A2,B2)，当且仅当A1⊆A2(⟺B2⊆B1)。

目前所研究的形式背景是完备的，换句话讲，此时对象或者具有某属性，或者不具有某属性，他们之间的关系是确定的。数据缺失现象在生活中普遍存在。例如，对一些突发事件，并没有该事件的完整记录；再如病人突发疾病，而不能对病人进行全面检查，然后来制定相应的治疗方案。下面给出一个例子来说明，表2是医生诊断表，即为不完备模糊形式背景，其中o1、o2、o3、o4表示病人编号，组成对象集G′。a、b、c、d、e、f表示病人的症状，其代表为头痛、血压、恶心、食欲不振、咳嗽、乏力，组成属性集M′。用*来表示缺失数据，但是这些数据是客观存在的。

表2　初始模糊形式背景

表3　置信度阈值为T的模糊形式背景

2相似模糊概念与相容模糊概念

在形式概念分析中，对不完备形式背景进行完备化处理，一般可采用以下3种方法。

1)删除法。删除法即删除形式背景中缺失数据的一列或者一行，也就是删除一个对象或者删除一个属性。这类方法操作起来比较简单，但是在删除过程中会导致原先存在的数据缺失，可能会造成获取的知识不准确。

2)填补法。填补法就是对不完备形式背景中缺失的数据填充为1或者0，使之补全为一个完备的形式背景。这类方法比较简单，但是容易造成获取的知识错误，因为好多缺失信息都是人为地填充0或者1。

3)扩展属性法[15]。扩展属性法即把原有不完备形式背景下的属性集合中的属性分为完备和不完备属性两部分，然后将不完备属性在不同对象的不同取值进行扩展，从而把不完备形式背景补充完整。此方法的好处是既不会增加知识也不会缺失知识，但是增加了知识获取的时间和空间复杂度。

定义6在不完备模糊形式背景Kc=(G′,M′,IM) 中，对于集合A∈G′，记作：

(5)

式中A∈G′。

(6)

式中B⊆M′。

(7)

(8)

(9)

(10)

(11)

(12)

相似模糊概念与相容模糊概念既有区别也有联系，在经典的不完备形式背景中“补全法”将缺失数据补充为1，而在不完备的模糊形式背景中，相似模糊概念是将不完备模糊形式背景中的缺失数据补充为0.5得到的。而相容模糊概念是对相似模糊概念的扩展，它是在相似模糊概念基础上通过设置参数(α,β)，去除一些数据量缺失较大的相似模糊概念而得到的。根据定义6和定义7以及传统的概念获取算法[16],可以得出相似模糊概念和相容模糊概念的构造算法，具体算法步骤参考算法1与算法2。

算法1在不完备形式背景Kc中，相似模糊概念的构造算法。

2)获得第一个概念(FO(M),M)设置概念的隶属度值并加入w(Kc)中。

3)遍历对象g，其中g∈G，如果遍历完成转到6)，反之转到4)。

算法2在不完备形式背景Kc中，相容模糊概念的获取算法。

2)如果相似模糊概念都被进行计算过，则输出相容模糊概念转到3)，反之再进行1)。

3基于相容模糊概念的规则提取

关联规则数据挖掘中最活跃的研究方法之一[17-21]。规则就是形如“如果…那么…(If…Then…)”前者为条件，后者为结果。典型的关联规则发现问题是对超市中的购物篮数据进行分析，例如最著名的案例就是啤酒与尿布。

对于关联规则A⟹B的支持度是supp(A⟹B)=|FO(A∪B)|/|U|，置信度为conf(A⟹B)>β关联规则A⟹B被称为关于(ω,τ)关联规则，当supp(A⟹B)>ω时把A∪B称为频繁的。

在不完备的模糊背景下，规则提取是一件比较困难的工作，在之前的工作中已经获得了相似模糊概念和相容模糊概念，然后根据算法3构造好相似模糊概念格，但是由于相似模糊概念中有许多不确定性信息，所以构造的相似模糊概念格也是不准确的。通过对相似模糊概念的筛选，最后得到了较为准确的相容模糊概念，可以在构造好的相似模糊概念格基础上得到相容模糊概念的之间的偏序关系，从而可以提取出可信度较高的关联规则，具体算法参考算法4。

算法3相似模糊概念格的构造算法。

输出相似模糊概念格。

2)遍历属性m，其中m∈M，并求得A与FO(m)交集I。如果遍历结束转到1)，否则转到3)。

4)输出相似模糊概念格，算法结束。

算法4不完备形式背景下规则提取的算法。

输出关联规则∑。

1)对相似模糊概念格进行处理，除去相容模糊概念之外的概念，更新父节点和子节点。

4)输出∑。

在得到提取规则∑后，可以给其支持度阈值ω与置信度阈值τ。然后根据需要从提取的规则中筛选出符合要求的规则。

4示例展示

现在举例来展示规则提取的过程，在表3中讨论的置信度阈值是T=[0.5,1]，通过算法1，可以得出在表3的不完备模糊背景下形成的相似模糊概念为

1){∅,(a,b,c,d,e,f)}；

2){(0.6/o1),(a,c,d,e,f)}；

3){(0.5/o2),(a,b,c,e,f)}；

4){(0.61/o1,0.5/o2),(a,c,e,f)}；

5){(0.5/o3),(b,c,d,e,f)}；

6){(0.6/o1,0.5/o3),(c,d,e,f)}；

7){(0.5/o2,0.5/o3),(b,c,e,f)}；

8){(0.61/o1,0.5/o2,0.6/o3),(c,e,f)}.；

9){(0.5/o4),(a,b,d,e)}；

10){(0.6/o1,0.5/o4),(a,d,e)}；

11){(0.7/o2,0.5/o4),(a,b,e)}；

12){(0.8/o1,0.7/o2,0.5/o4),(a,e)}；

13){(0.5/o3,0.5/o4),(b,d,e)}；

14){(0.6/o1,0.5/o3,0.5/o4),(d,e)}；

15){(0.7/o2,0.5/o3,0.5/o4),(b,e)}；

16){(o1,o2,o3,o4),(0/a,0/b,0/c,0/d,0.5/e,0/f)}。

图2　相似模糊概念的相似模糊概念格Fig.2　Approximat fuzzy concept lattice

1){0.6/(o1),(a,c,d,e,f)}；

2){0.5/(o2),(a,b,c,e,f)}；

3){0.57/(o1,o2,o3),(c,e,f)}；

4){0.55/(o1,o4),(a,d,e)}；

5){0.6/(o2,o4),(a,d,e)}；

6){0.667/(o1,o2,o4),(a,e)}；

7){0.083/(o1,o2,o3,o4),(c)}。

根据算法4可以得出阈值τ为0.9，置信度阈值为0.5的关联规则：

1){a,d,e}⟹{c,f}置信度为0.5。

解释：如果头疼、食欲不振、咳嗽则恶心、乏力。

2){a,e}⟹{b}置信度为0.67。

解释：如果头疼、咳嗽则血压会高。

5实验结果与分析

本文基于相容模糊概念的关联规则提取可分为在不完备模糊形式背景中相容模糊概念的构造过程和根据相容模糊概念的偏序关系进行提取规则的过程。本文算法在Win7环境下用MATLAB来实现，并在UCI数据库的water数据集(526个对象，38个属性)进行实验。实验主要对2个指标进行测量：第1个是在不完备模糊形式背景下相似模糊概念数目与对象数目以及相容模糊概念与对象数目之间的关系；第2个是提取的关联规则数目与对象数目之间的关系。在本实验中针对不完备模糊形式背景，设定相容模糊参数为(α=0.8,β=0.9)，关联规则的置信度阈值为0.8。在不完备形式背景下相似模糊概念与相容模糊概念的数量关系可由图3体现，图4则体现了对象数目与关联规则数量之间的关系。图3与图4都在相容模糊参数与属性数量都不变的情况下，取water数据集中的前200个对象进行测量。图3与图4中横坐标都表示对象的数量，初始为0，分别一次递增50与10进行测试。图3纵坐标表示由不完备形式背景形成概念的数量，图4纵坐标表示由相容模糊概念获得的关联规则的数量。通过图3、4的实验结果可以观察到，在不完备模糊形式背景中随着对象数目的增多，通过本算法获得知识准确性与传统的方法相比具有一定的优势。

图3　对象与概念个数关系Fig.3　Relationship between object and concept

图4　对象与关联规则个数关系Fig.4　Relationship between object and association rule

6结束语

目前在不完备模糊形式背景下的研究越来越多。本文结合在传统的不完备形式背景下获取概念的方法，提出了在不完备模糊形式背景中提取出相容模糊概念，并根据相似模糊概念格提取出相容规则的方法。实验表明，该方法可以有效的降低形式背景中因数据缺失和数据的模糊性对获取知识准确性带来的的影响。未来的工作还需要改进和细化文中的一些算法，例如如何在知识库分类能力保持不变的情况下删除不相关的冗余属性；如何把模糊概念格与粗糙集理论有效结合以解决不确定规则提取中的规则冗余性等问题。

参考文献:

[1]WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M]//RIVAL I. Ordered sets. Netherlands: Springer, 1982: 445-470.

[2]POELMANS J, IGNATOV D I, KUZNETSOV S O, et al. Formal concept analysis in knowledge processing: a survey on applications[J]. Expert systems with applications, 2013, 40(16): 6538-6560.

[3]MINEAU G W, GODIN R. Automatic structuring of knowledge bases by conceptual clustering[J]. IEEE transactions on knowledge and data engineering, 1995, 7(5): 824-829.

[4]COLE R, EKLUND P W. Scalability in formal concept analysis[J]. Computational intelligence, 1999, 15(1): 11-27.

[5]CARPINETO C, ROMANO G. A lattice conceptual clustering system and its application to browsing retrieval[J]. Machine learning, 1996, 24(2): 95-122.

[6]MA Jianmin, ZHANG Wenxiu. Axiomatic characterizations of dual concept lattices[J]. International journal of approximate reasoning, 2013, 54(5): 690-697.

[7]胡明涵, 张莉, 任飞亮. 模糊形式概念分析与模糊概念格[J]. 东北大学学报:自然科学版, 2007, 28(9): 1274-1277.

HU Minghan, ZHANG Li, REN Feiliang. Fuzzy formal concept analysis and fuzzy concept lattices[J]. Journal of northeastern university : natural science, 2007, 28(9): 1274-1277.

[8]GRZYMALA-BUSSE J W. Rough set approach to incomplete data[C]//Proceedings of the 7th international conference on artificial intelligence and soft computing-ICAISC 2004. Berlin Heidelberg, Germany, 2004: 50-55.

[9]LIU Jun, YAO Xiaoqiu. Formal concept analysis of incomplete information system[C]//Proceedings of the 7th international conference on fuzzy systems and knowledge discovery. Yantai, China, 2010, 5: 2016-2020.

[10]DJOUADI Y, DUBOIS D, PRADE H. Possibility theory and formal concept analysis: Context decomposition and uncertainty handling[C]//Proceedings of the 13th international conference on information processing and management of uncertainty. Berlin Heidelberg, Germany, 2010: 260-269.

[11]KRUPKA M. Fuzzy concept lattices with incomplete knowledge[C]//Proceedings of the 14th international conference on information processing and management of uncertainty in knowledge-based systems. Berlin Heidelberg, Germany, 2012: 171-180.

[12]DJOUADI Y, PRADE H. Interval-valued fuzzy formal concept analysis[C]//Proceedings of the 18th international symposium. Berlin Heidelberg, Germany, 2009: 592-601.

[13]LI Jinhai, MEI Changlin, LV Yuejin. Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction[J]. International journal of approximate reasoning, 2013, 54(1): 149-165.

[14]LAI Hongliang, ZHANG Dexue. Concept lattices of fuzzy contexts: formal concept analysis vs. rough set theory[J]. International journal of approximate reasoning, 2009, 50(5): 695-707.

[15]何淑贤, 王育红, 翟岩慧, 等. 不完备形式背景及其完备化方法[J]. 山西大学学报:自然科学版, 2006, 29(4): 364-367.

HE Shuxian, WANG Yuhong, ZHAI Yanhui, et al. Incomplete formal context and the completion approach[J]. Journal of Shanxi university : natural science edition, 2006, 29(4): 364-367.

[16]谢志鹏, 刘宗田. 概念格的快速渐进式构造算法[J]. 计算机学报, 2002, 25(5): 490-496.

XIE Zhipeng, LIU Zongtian. A fast incremental algorithm for building concept lattice[J]. Chinese journal of computers, 2002, 25(5): 490-496.

[17]梁吉业, 王俊红. 基于概念格的规则产生集挖掘算法[J]. 计算机研究与发展, 2004, 41(8): 1339-1344.

LIANG Jiye, WANG Junhong. An algorithm for extracting rule-generating sets based on concept lattice[J]. Journal of computer research and development, 2004, 41(8): 1339-1344.

[18]LEKHA A, SRIKRISHNA C V, VINOD V. Fuzzy association rule mining[J]. Journal of computer science, 2015, 11(1): 71-74.

[19]LAKHAL L, STUMME G. Efficient mining of association rules based on formal concept analysis[M]//GANTER B, STUMME G, WILLE R. Formal concept analysis. Berlin Heidelberg: Springer-Verlag, 2005: 180-195.

[20]KUMAR CH A, DIAS S M, VIEIRA N J. Knowledge reduction in formal contexts using non-negative matrix factorization[J]. Mathematics and computers in simulation, 2015, 109: 46-63.

[21]王志海, 胡可云, 胡学纲, 等. 概念格上规则提取的一般算法与渐进式算法[J]. 计算机学报, 1991, 22(1): 66-70.

WANG Zhihai, HU Keyun, HU Xuegang, et al. General and incremental algorithms of rule extraction based on concept lattice[J]. Chinese journal of computers, 1991, 22(1): 66-70.

胡小康，男，1991年生，硕士研究生，主要研究方向为形式概念分析、数据挖掘。

王俊红，女，1979年生，副教授，主要研究方向形式概念分析、粗糙集和数据挖掘。主持或参与多项国家863计划、国家自然科学基金和省部级等科研项目。发表学术论文10余篇。

中文引用格式：胡小康，王俊红.基于相容模糊概念的规则提取方法[J]. 智能系统学报， 2016, 11(3): 352-358.

英文引用格式：HU Xiaokang， WANG Junhong. Research on rule extraction method based on compatibility fuzzy concept[J]. CAAI transactions on intelligent systems, 2016,11(3): 352-358.

Research on rule extraction method based on compatibility fuzzy concept

HU Xiaokang， WANG Junhong

(School of Computer and Information Technology, Shanxi University, Taiyuan 030006, China)

Abstract：The concept lattice is an effective data analysis and rule extraction tool with a strict mathematical model. In most instances, studies are carried out in a complete formal context, i.e., a two-value context. However, in real life, an incomplete fuzzy formal context is frequently experienced. Incomplete fuzzy contexts contain a lot of uncertain information. There are both distinctions and relationships that can be identified between the forms of knowledge representation in the incomplete fuzzy formal and complete formal contexts. To study their internal relationship, in this paper, we define approximate fuzzy and compatible fuzzy concepts, establish an approximate fuzzy concept lattice, and identify a partial ordering relationship between compatible fuzzy concepts in an incomplete fuzzy formal context. We extend the design of an association rules mining algorithm to address the background of the incomplete fuzzy formal context, and conduct an experiment to demonstrate the feasibility and effectiveness of the proposed method.

Keywords：formal context; concept lattice; approximate fuzzy concept; compatible fuzzy concept; knowledge representation; association rules; partial ordering relation; compatible relation

作者简介：

中图分类号：TP18

文献标志码：A

文章编号：1673-4785(2016)03-0352-07

通信作者：王俊红.E-mail:wjhwjh@sxu.edu.cn.

基金项目：国家自然科学基金项目(61202018，61303008，61305057).

收稿日期：2016-03-19.网络出版日期：2016-05-13.

DOI:10.11992/tis.201603043

网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0925.026.html