第11卷第3期 智能系统学报 Vol.11 No.3 2016年6月 CAAI Transactions on Intelligent Systems Jun.2016 D0I:10.11992/is.201603043 网s络出版地址：http:/www.cnki.net/kcms/detail/23.1538.TP.20160513.0925.026.html 基于相容模糊概念的规则提取方法 胡小康，王俊红 (山西大学计算机与信息技术学院，山西太原030006) 摘要：概念格是具有严格数学模型的数据分析与规则提取的一种有效工具，大部分情况下是在完备的精确形式背 景即二值背景下进行研究，然而在现实生活中遇到的大多数情况是不完备的模糊形式背景，不完备模糊形式背景中 包含许多不确定的信息，其上的知识表示与完备形式背景下的知识表示既有区别又有联系。为了研究两者的内在 联系，本文定义了相似模糊概念和相容模糊概念，构建了相似模糊概念格和建立了在不完备模糊形式背景下相容模 糊概念之间的偏序关系，进而设计出面向不完备模糊形式背景下的关联规则挖掘算法最后通过实验验证了该方法 的有效性和可行性。 关键词：形式背景：概念格：相似模糊概念；相容模糊概念；知识获取；关联规则；偏序关系；相容关系 中图分类号：TP18文献标志码：A文章编号：1673-4785(2016)03-0352-07 中文引用格式：胡小康，王俊红.基于相容模糊概念的规则提取方法[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 uncer- tain 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 lat- tice,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 repre- sentation;association rules;partial ordering relation;compatible relation 概念格也称为Glos格，又叫做形式概念分析，间的关系。概念格是研究知识表示和推理的理论， 由德国的Wile山在20世纪80年代提出。概念格 它具有严格的数学模型，已经在机器学习、数据挖 的每个节点是一个形式概念，概念格结构模型是形 掘、软件工程等领域[26)得到广泛的应用。 式概念分析中的核心结构，它描述了对象和属性之 通常我们研究的形式背景是完备的，也就是对 象和属性之间的关系是已知的，但是在实际应用中， 收稿日期：2016-03-19.网络出版日期：2016-05-13. 基金项目：国家自然科学基金项目(61202018,61303008,61305057) 大多数信息是模糊[)的、复杂的。更槽糕的是在现 通信作者：王俊红.E-mail:wjhwjhe@sxu.cdu.cm
第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０３０４３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０５１３．０９２５．０２６．ｈｔｍｌ 基于相容模糊概念的规则提取方法 胡小康，王俊红 （山西大学 计算机与信息技术学院，山西 太原 ０３０００６） 摘 要：概念格是具有严格数学模型的数据分析与规则提取的一种有效工具，大部分情况下是在完备的精确形式背 景即二值背景下进行研究，然而在现实生活中遇到的大多数情况是不完备的模糊形式背景，不完备模糊形式背景中 包含许多不确定的信息，其上的知识表示与完备形式背景下的知识表示既有区别又有联系。 为了研究两者的内在 联系，本文定义了相似模糊概念和相容模糊概念，构建了相似模糊概念格和建立了在不完备模糊形式背景下相容模 糊概念之间的偏序关系，进而设计出面向不完备模糊形式背景下的关联规则挖掘算法．最后通过实验验证了该方法 的有效性和可行性。 关键词：形式背景；概念格；相似模糊概念；相容模糊概念；知识获取；关联规则；偏序关系；相容关系 中图分类号：ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０３⁃０３５２⁃０７ 中文引用格式：胡小康，王俊红．基于相容模糊概念的规则提取方法［Ｊ］． 智能系统学报， ２０１６， １１（３）： ３５２⁃３５８． 英文引用格式：ＨＵ Ｘｉａｏｋａｎｇ， ＷＡＮＧ Ｊｕｎｈｏｎｇ． Ｒｅｓｅａｒｃｈ ｏｎ ｒｕｌｅ ｅｘｔｒａｃｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｃｏｍｐａｔｉｂｉｌｉｔｙ ｆｕｚｚｙ ｃｏｎｃｅｐｔ ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（３）： ３５２⁃３５８． Ｒｅｓｅａｒｃｈ ｏｎ ｒｕｌｅ ｅｘｔｒａｃｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｃｏｍｐａｔｉｂｉｌｉｔｙ ｆｕｚｚｙ ｃｏｎｃｅｐｔ ＨＵ Ｘｉａｏｋａｎｇ， ＷＡＮＧ Ｊｕｎｈｏｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， Ｓｈａｎｘｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｔａｉｙｕａｎ ０３０００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｉｓ ａｎ ｅｆｆｅｃｔｉｖｅ ｄａｔａ ａｎａｌｙｓｉｓ ａｎｄ ｒｕｌｅ ｅｘｔｒａｃｔｉｏｎ ｔｏｏｌ ｗｉｔｈ ａ ｓｔｒｉｃｔ ｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌ． Ｉｎ ｍｏｓｔ ｉｎｓｔａｎｃｅｓ， ｓｔｕｄｉｅｓ ａｒｅ ｃａｒｒｉｅｄ ｏｕｔ ｉｎ ａ ｃｏｍｐｌｅｔｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ， ｉ．ｅ．， ａ ｔｗｏ－ｖａｌｕｅ ｃｏｎｔｅｘｔ． Ｈｏｗｅｖｅｒ， ｉｎ ｒｅａｌ ｌｉｆｅ， ａｎ ｉｎｃｏｍｐｌｅｔｅ ｆｕｚｚｙ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ｉｓ ｆｒｅｑｕｅｎｔｌｙ ｅｘｐｅｒｉｅｎｃｅｄ． Ｉｎｃｏｍｐｌｅｔｅ ｆｕｚｚｙ ｃｏｎｔｅｘｔｓ ｃｏｎｔａｉｎ ａ ｌｏｔ ｏｆ ｕｎｃｅｒ⁃ ｔａｉｎ ｉｎｆｏｒｍａｔｉｏｎ． Ｔｈｅｒｅ ａｒｅ ｂｏｔｈ ｄｉｓｔｉｎｃｔｉｏｎｓ ａｎｄ ｒｅｌａｔｉｏｎｓｈｉｐｓ ｔｈａｔ ｃａｎ ｂｅ ｉｄｅｎｔｉｆｉｅｄ ｂｅｔｗｅｅｎ ｔｈｅ ｆｏｒｍｓ ｏｆ ｋｎｏｗｌｅｄｇｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｉｎ ｔｈｅ ｉｎｃｏｍｐｌｅｔｅ ｆｕｚｚｙ ｆｏｒｍａｌ ａｎｄ ｃｏｍｐｌｅｔｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔｓ． Ｔｏ ｓｔｕｄｙ ｔｈｅｉｒ ｉｎｔｅｒｎａｌ ｒｅｌａｔｉｏｎｓｈｉｐ， ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｄｅｆｉｎｅ ａｐｐｒｏｘｉｍａｔｅ ｆｕｚｚｙ ａｎｄ ｃｏｍｐａｔｉｂｌｅ ｆｕｚｚｙ ｃｏｎｃｅｐｔｓ， ｅｓｔａｂｌｉｓｈ ａｎ ａｐｐｒｏｘｉｍａｔｅ ｆｕｚｚｙ ｃｏｎｃｅｐｔ ｌａｔ⁃ ｔｉｃｅ， ａｎｄ ｉｄｅｎｔｉｆｙ ａ ｐａｒｔｉａｌ ｏｒｄｅｒｉｎｇ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｃｏｍｐａｔｉｂｌｅ ｆｕｚｚｙ ｃｏｎｃｅｐｔｓ ｉｎ ａｎ ｉｎｃｏｍｐｌｅｔｅ ｆｕｚｚｙ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ． Ｗｅ ｅｘｔｅｎｄ ｔｈｅ ｄｅｓｉｇｎ ｏｆ ａｎ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｏ ａｄｄｒｅｓｓ ｔｈｅ ｂａｃｋｇｒｏｕｎｄ ｏｆ ｔｈｅ ｉｎｃｏｍｐｌｅｔｅ ｆｕｚｚｙ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ， ａｎｄ ｃｏｎｄｕｃｔ ａｎ ｅｘｐｅｒｉｍｅｎｔ ｔｏ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｆｅａｓｉｂｉｌｉｔｙ ａｎｄ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ． Ｋｅｙｗｏｒｄｓ：ｆｏｒｍａｌ ｃｏｎｔｅｘｔ； ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ； ａｐｐｒｏｘｉｍａｔｅ ｆｕｚｚｙ ｃｏｎｃｅｐｔ； ｃｏｍｐａｔｉｂｌｅ ｆｕｚｚｙ ｃｏｎｃｅｐｔ； ｋｎｏｗｌｅｄｇｅ ｒｅｐｒｅ⁃ ｓｅｎｔａｔｉｏｎ； ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ； ｐａｒｔｉａｌ ｏｒｄｅｒｉｎｇ ｒｅｌａｔｉｏｎ； ｃｏｍｐａｔｉｂｌｅ ｒｅｌａｔｉｏｎ 收稿日期：２０１６⁃０３⁃１９． 网络出版日期：２０１６⁃０５⁃１３． 基金项目：国家自然科学基金项目（６１２０２０１８，６１３０３００８，６１３０５０５７）． 通信作者：王俊红．Ｅ⁃ｍａｉｌ：ｗｊｈｗｊｈ＠ ｓｘｕ．ｅｄｕ．ｃｎ． 概念格也称为 Ｇａｌｏｉｓ 格，又叫做形式概念分析， 由德国的 Ｗｉｌｌｅ ［１］ 在 ２０ 世纪 ８０ 年代提出。 概念格 的每个节点是一个形式概念，概念格结构模型是形 式概念分析中的核心结构，它描述了对象和属性之 间的关系。 概念格是研究知识表示和推理的理论， 它具有严格的数学模型，已经在机器学习、数据挖 掘、软件工程等领域［２⁃６］得到广泛的应用。 通常我们研究的形式背景是完备的，也就是对 象和属性之间的关系是已知的，但是在实际应用中， 大多数信息是模糊［７］ 的、复杂的。 更糟糕的是在现
第3期 胡小康，等：基于相容模糊概念的规则提取方法 ·353· 实生活中由于人的认知能力以及机器的局限性，人 G(B)={g∈GI glm,Hm∈B},BCM(2) 们经常不能准确地判断对象和属性之间的关系，使 形式背景能用一个二维表表示，如表1，其中对 得获取的形式背景经常存在数据缺失，从而得到形 象集G={x1,x2,x3,x4},属性集M={a,b,c,d。表 式背景是不完备的模糊形式背景，这对于知识获取 中1表示某对象拥有某属性，0表示某对象不拥有 产生了很大障碍。因此不完备模糊形式背景的研究 某属性，例如x,有a属性，没有b属性。 获得了广泛的关注。 表1形式背景 粗糙集理论中的信息系统就是形式概念分析中 Table 1 A formal context 的形式背景，对于不完备信息系统[】，粗糙集已通 G a b C 过相容关系、非对称相似关系等进行了一些研究。 X 1 0 在形式概念分析中LuJ等在文献[9]中将多值形 X2 0 式背景转变为单值形式背景后，通过把不完备属性 1 0 在不同对象上的不同取值进行扩展，从而得到了完 X3 1 0 0 备的形式背景来进行概念的提取。Dubois D等在文 Xa 0 0 1 0 献[10]提出了利用概率论来解决不完备形式背景 定义2山形式背景K=(G,M,)中一对二元 的方法。Krupka M等在文献[I1]中定义了不完备 组(A,B)称为形式概念，当且仅当F(A)=B与G 的模糊形式背景，然后提出了在不完备模糊形式背 (B)=A同时成立(ACG,BCM),其中A叫做形式 景下构建概念格的方法。Djouadi Y等在文献[12] 概念的外延，B叫做形式概念的内涵。 中将不完备模糊形式背景中的隶属度值均采用区间 假定(41，B)与(A2,B2)是形式背景(G,M,I) 值来表示，将不完备模糊形式背景转化为区间值模 下的两个概念，这两个概念间可以建立起偏序关系 糊形式背景(interval-valued fuzzy formal concept, (A1,B)≤(A2,B2)台A1CA2(曰B2CB1)。领先次 VFF),在此基础上提出了基于区间值形式背景的 概念格构建方法。iJH等在文献[13]中提出了在 序意味着(41，B,)是(42，B,)的子概念。根据概念 间的偏序关系生成格的Hasse图见图1。下面是在 不完备形式背景下构建相似概念格的方法，此外基 形式背景K下生成的概念： 于相似概念格还研究了在不完备的决策形式背景下 1){☑，(a,b,c,d)}; 获取规则的方法。上述研究中，无论是将不完备形 2){(x),(a,d)}: 式背景转化为区间值形式背景，还是对不完备属性 3){(x3),(a,c)}; 进行扩展来构造概念格的方法，仅仅适用于形式背 4){(x2),(b,c)}; 景中数据量缺失较少的情况。当形式背景中数据缺 失量较大时，所构造的概念格中包含有大量不确定 5){(x1,x3),(a)}: 6){(x2,x3,x4),(c)}: 的信息，这对知识获取造成了很大影响。 7)1(x1,x2,x3,x),☑1。 本文为了减少形式背景中数据缺失量对知识获 取的影响，提出并定义了相似模糊概念和相容模糊 7 概念并给出了相容模糊概念的构建方法，建立了相 容模糊概念之间的偏序关系，进而设计面向模糊不 完备信息的关联规则挖掘算法。 1基本概念 1.1形式概念分析 定义1山一个形式背景K=(G,M,I)是一个 三元组，其中G是对象集合，M是属性集合，I是G 与M之间的一个二元关系gm或(g,m)∈I,表示 图1表1对应概念格的Hasse图 对象g具有属性m。在形式背景中定义式(1)和式 Fig.1 Hasse diagram of table 1 (2): F(A)={m∈MI glm,Hg∈A},ACG(1)
实生活中由于人的认知能力以及机器的局限性，人 们经常不能准确地判断对象和属性之间的关系，使 得获取的形式背景经常存在数据缺失，从而得到形 式背景是不完备的模糊形式背景，这对于知识获取 产生了很大障碍。 因此不完备模糊形式背景的研究 获得了广泛的关注。 粗糙集理论中的信息系统就是形式概念分析中 的形式背景，对于不完备信息系统［８］ ，粗糙集已通 过相容关系、非对称相似关系等进行了一些研究。 在形式概念分析中 Ｌｉｕ Ｊ 等在文献［９］中将多值形 式背景转变为单值形式背景后，通过把不完备属性 在不同对象上的不同取值进行扩展，从而得到了完 备的形式背景来进行概念的提取。 Ｄｕｂｏｉｓ Ｄ 等在文 献［１０］提出了利用概率论来解决不完备形式背景 的方法。 Ｋｒｕｐｋａ Ｍ 等在文献［１１］中定义了不完备 的模糊形式背景，然后提出了在不完备模糊形式背 景下构建概念格的方法。 Ｄｊｏｕａｄｉ Ｙ 等在文献［１２］ 中将不完备模糊形式背景中的隶属度值均采用区间 值来表示，将不完备模糊形式背景转化为区间值模 糊形 式 背 景 （ ｉｎｔｅｒｖａｌ⁃ｖａｌｕｅｄ ｆｕｚｚｙ ｆｏｒｍａｌ ｃｏｎｃｅｐｔ， ＩＶＦＦ），在此基础上提出了基于区间值形式背景的 概念格构建方法。 Ｌｉ Ｊ Ｈ 等在文献［１３］中提出了在 不完备形式背景下构建相似概念格的方法，此外基 于相似概念格还研究了在不完备的决策形式背景下 获取规则的方法。 上述研究中，无论是将不完备形 式背景转化为区间值形式背景，还是对不完备属性 进行扩展来构造概念格的方法，仅仅适用于形式背 景中数据量缺失较少的情况。 当形式背景中数据缺 失量较大时，所构造的概念格中包含有大量不确定 的信息，这对知识获取造成了很大影响。 本文为了减少形式背景中数据缺失量对知识获 取的影响，提出并定义了相似模糊概念和相容模糊 概念并给出了相容模糊概念的构建方法，建立了相 容模糊概念之间的偏序关系，进而设计面向模糊不 完备信息的关联规则挖掘算法。 １ 基本概念 １．１ 形式概念分析 定义 １ ［１］ 一个形式背景 Ｋ ＝ （Ｇ，Ｍ，Ｉ）是一个 三元组 ，其中 Ｇ 是对象集合，Ｍ 是属性集合， Ｉ 是 Ｇ 与 Ｍ 之间的一个二元关系 ｇＩｍ 或（ ｇ，ｍ） ∈Ｉ，表示 对象 ｇ 具有属性 ｍ。 在形式背景中定义式（１）和式 （２）： Ｆ(Ａ) ＝ ｛ｍ ∈ Ｍ ｜ ｇＩｍ，∀ｇ ∈ Ａ｝，Ａ ⊆ Ｇ （１） Ｇ(Ｂ) ＝ ｛ｇ ∈ Ｇ ｜ ｇＩｍ，∀ｍ ∈ Ｂ｝，Ｂ ⊆ Ｍ （２） 形式背景能用一个二维表表示，如表 １，其中对 象集 Ｇ ＝ ｘ１ ，ｘ２ ，ｘ３ ，ｘ４ { } ，属性集 Ｍ ＝ {ａ，ｂ，ｃ，ｄ} 。 表 中 １ 表示某对象拥有某属性，０ 表示某对象不拥有 某属性，例如 ｘ１ 有 ａ 属性，没有 ｂ 属性。 表 １ 形式背景 Ｔａｂｌｅ １ Ａ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ Ｇ ａ ｂ ｃ ｄ Ｘ１ １ ０ ０ １ Ｘ２ ０ １ １ ０ Ｘ３ １ ０ １ ０ Ｘ４ ０ ０ １ ０ 定义 ２ ［１］ 形式背景 Ｋ ＝ (Ｇ，Ｍ，Ｉ) 中一对二元 组（ Ａ，Ｂ） 称为形式概念，当且仅当 Ｆ (Ａ) ＝ Ｂ 与 Ｇ (Ｂ) ＝ Ａ 同时成立（Ａ⊆Ｇ，Ｂ⊆Ｍ），其中 Ａ 叫做形式 概念的外延，Ｂ 叫做形式概念的内涵。 假定 Ａ１ ，Ｂ１ ( ) 与 Ａ２ ，Ｂ２ ( ) 是形式背景（Ｇ，Ｍ，Ｉ） 下的两个概念，这两个概念间可以建立起偏序关系 Ａ１ ，Ｂ１ ( ) ≤ Ａ２ ，Ｂ２ ( ) ⇔Ａ１⊆Ａ２（⇔Ｂ２⊆Ｂ１ ） 。 领先次 序意味着 Ａ１ ，Ｂ１ ( ) 是 Ａ２ ，Ｂ２ ( ) 的子概念。 根据概念 间的偏序关系生成格的 Ｈａｓｓｅ 图见图 １。 下面是在 形式背景 Ｋ 下生成的概念： １）｛∅，（ａ，ｂ，ｃ，ｄ）｝； ２）｛（ｘ１ ），（ａ，ｄ）｝； ３）｛（ｘ３ ），（ａ，ｃ）｝； ４）｛（ｘ２ ），（ｂ，ｃ）｝； ５）｛（ｘ１ ，ｘ３ ），（ａ）｝； ６）｛（ｘ２ ，ｘ３ ，ｘ４ ），（ｃ）｝； ７）｛（ｘ１ ，ｘ２ ，ｘ３ ，ｘ４ ），∅｝。 图 １ 表 １ 对应概念格的 Ｈａｓｓｅ 图 Ｆｉｇ．１ Ｈａｓｓｅ ｄｉａｇｒａｍ ｏｆ ｔａｂｌｅ １ 第 ３ 期 胡小康，等：基于相容模糊概念的规则提取方法 ·３５３·
·354 智能系统学报 第11卷 1.2模糊形式概念 过设置置信度阈值可以消除一些不在这个值之内的 定义34 一个模糊形式背景是一个三元组 关系，对于t与【2的值用户可以根据需要来设定。 (G,M,'),其中G是对象的有限集，M是属性有 例如在表2中设定模糊形式背景的置信度阈值为 限集，I'是G'×M'的模糊集合。(g,m)∈'有一个隶 T=[0.5,1],对于表中(o1,b)的隶属度值为0.1，认 属度值u(g,m)∈[0,1]。 为病人0，的血压没有问题，可以不考虑。 定义414)给定一个模糊形式背景K'={G, 表3置信度阔值为T的模糊形式背景 M,'=p(G'×M)}和一个置信度阈值T=[t1,t2], Table 3 Confidence thresholds for T fuzzy formal context 在形式背景中定义式(3)与式(4)： d e FA(A)={m∈M'1Hg∈A:t1≤u(g,m)≤t2} 0 0.8 0 0.61 0.6 0.8 (3) 02 0.9 0.85 0 0.7 0.9 式中ACG。 03 0 0.87 0.6 0.6 FO(B)={g∈G'IVm∈B:41≤u(g,m)≤t2l 04 0.6 0 0.5 0 (4) 式中BCM'。 2相似模糊概念与相容模糊概念 模糊形式背景(G',M',)同置信度阈值T下的 一个二元组(A,B)(ACG',B二M')是模糊形式概 在形式概念分析中，对不完备形式背景进行完 念，当且仅当FA(A)=B与FO(B)=A同时成立。 备化处理，一般可采用以下3种方法。 A、B分别叫做模糊形式背景的模糊外延和模糊 1)删除法。删除法即删除形式背景中缺失数 内涵。 据的一列或者一行，也就是删除一个对象或者删除 定义5(A1,B,)和(A2,B2)是形式背景 一个属性。这类方法操作起来比较简单，但是在删 (G',M',')的两个模糊概念。(A1,B,)是(A2,B2) 除过程中会导致原先存在的数据缺失，可能会造成 的子概念，记作(A1,B,)≤(A2,B2),当且仅当 获取的知识不准确。 ACA2(台B2SB,)。 2)填补法。填补法就是对不完备形式背景中 目前所研究的形式背景是完备的，换句话讲，此 缺失的数据填充为1或者0，使之补全为一个完备 时对象或者具有某属性，或者不具有某属性，他们之 的形式背景。这类方法比较简单，但是容易造成获 间的关系是确定的。数据缺失现象在生活中普遍存 取的知识错误，因为好多缺失信息都是人为地填充 在。例如，对一些突发事件，并没有该事件的完整记 0或者1。 录：再如病人突发疾病，而不能对病人进行全面检 3)扩展属性法[1)。扩展属性法即把原有不完 查，然后来制定相应的治疗方案。下面给出一个例 备形式背景下的属性集合中的属性分为完备和不完 子来说明，表2是医生诊断表，即为不完备模糊形式 备属性两部分，然后将不完备属性在不同对象的不 背景，其中01、02、03、04表示病人编号，组成对象集 同取值进行扩展，从而把不完备形式背景补充完整。 G'。a、b、c、d、ef表示病人的症状，其代表为头痛、 此方法的好处是既不会增加知识也不会缺失知识， 血压、恶心、食欲不振、咳嗽、乏力，组成属性集M”。 但是增加了知识获取的时间和空间复杂度。 用*来表示缺失数据，但是这些数据是客观存在的。 定义6在不完备模糊形式背景K=(G',M', 表2初始模糊形式背景 I)中，对于集合A∈G,记作： Table 2 The initial fuzzy formal context FA(A)={m∈M'IVg∈A:t1≤ u(g,m)≤t2或u(g,m)=*} (5) e 式中A∈G。 0.8 0.1 0.61 0.6 0.8 FO(B)={g∈GlHm∈B:t1≤ u(g,m)≤t2或u(g,m)=*} (6) 03 0.9 0.85 0.2 0.7 0.9 式中BM'。 03 0.21 0.87 0.6 0.6 如果FA(4)=B且FO(B)=A称(A,B)为模糊 04 0.6 0.30 0.5 形式背景K。下的一个相似模糊概念，g∈A时u,为 个置信度阈值T设置在区间[，2]中。通 (4,B)中对象g的隶属度值，其表示如式(7)：
１．２ 模糊形式概念 定义 ３ ［１４］ 一个模糊形式背景是一个三元组 （Ｇ′，Ｍ′，Ｉ′），其中 Ｇ′是对象的有限集，Ｍ′是属性有 限集，Ｉ′是 Ｇ′×Ｍ′的模糊集合。 （ｇ，ｍ）∈Ｉ′有一个隶 属度值 ｕ（ｇ，ｍ）∈［０，１］ 。 定义 ４ ［１４］ 给定一个模糊形式背景 Ｋ′ ＝ ｛Ｇ′， Ｍ′，Ｉ′＝φ（Ｇ′×Ｍ′）｝和一个置信度阈值 Ｔ ＝ ［ ｔ １ ，ｔ ２ ］， 在形式背景中定义式（３）与式（４）： ＦＡ（Ａ） ＝ ｛ｍ ∈ Ｍ′ ｜ ∀ｇ ∈ Ａ：ｔ １ ≤ ｕ（ｇ，ｍ） ≤ ｔ ２ ｝ （３） 式中 Ａ⊆Ｇ′。 ＦＯ（Ｂ） ＝ ｛ｇ ∈ Ｇ′ ｜ ∀ｍ ∈ Ｂ：ｔ １ ≤ ｕ（ｇ，ｍ） ≤ ｔ ２ ｝ （４） 式中 Ｂ⊆Ｍ′。 模糊形式背景（Ｇ′，Ｍ′，Ｉ′）同置信度阈值 Ｔ 下的 一个二元组（ Ａ，Ｂ） （ Ａ⊆Ｇ′，Ｂ⊆Ｍ′） 是模糊形式概 念，当且仅当 ＦＡ（ Ａ） ＝ Ｂ 与 ＦＯ（Ｂ） ＝ Ａ 同时成立。 Ａ、Ｂ 分别叫做模糊形式背景的模糊外延和模糊 内涵。 定义 ５ ［１４］ （ Ａ１ ，Ｂ１ ） 和（ Ａ２ ，Ｂ２ ） 是形式背景 （Ｇ′，Ｍ′，Ｉ′）的两个模糊概念。 （Ａ１ ，Ｂ１ ） 是（ Ａ２ ，Ｂ２ ） 的子 概 念， 记 作 （ Ａ１ ， Ｂ１ ） ≤ （ Ａ２ ， Ｂ２ ）， 当 且 仅 当 Ａ１⊆Ａ２ （⇔Ｂ２⊆Ｂ１ ）。 目前所研究的形式背景是完备的，换句话讲，此 时对象或者具有某属性，或者不具有某属性，他们之 间的关系是确定的。 数据缺失现象在生活中普遍存 在。 例如，对一些突发事件，并没有该事件的完整记 录；再如病人突发疾病，而不能对病人进行全面检 查，然后来制定相应的治疗方案。 下面给出一个例 子来说明，表 ２ 是医生诊断表，即为不完备模糊形式 背景，其中 ｏ１ 、ｏ２ 、ｏ３ 、ｏ４ 表示病人编号，组成对象集 Ｇ′。 ａ、ｂ、ｃ、ｄ、ｅ、ｆ 表示病人的症状，其代表为头痛、 血压、恶心、食欲不振、咳嗽、乏力，组成属性集 Ｍ′。 用∗来表示缺失数据，但是这些数据是客观存在的。 表 ２ 初始模糊形式背景 Ｔａｂｌｅ ２ Ｔｈｅ ｉｎｉｔｉａｌ ｆｕｚｚｙ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ａ ｂ ｃ ｄ ｅ ｆ ｏ１ ０．８ ０．１ ０．６１ ０．６ ０．８ ∗ ｏ２ ０．９ ０．８５ ∗ ０．２ ０．７ ０．９ ｏ３ ０．２１ ∗ ０．８７ ∗ ０．６ ０．６ ｏ４ ０．６ ∗ ０．３０ ∗ ０．５ ０ 一个置信度阈值 Ｔ 设置在区间［ ｔ １ ，ｔ ２ ］ 中。 通 过设置置信度阈值可以消除一些不在这个值之内的 关系，对于 ｔ １ 与 ｔ ２ 的值用户可以根据需要来设定。 例如在表 ２ 中设定模糊形式背景的置信度阈值为 Ｔ ＝ [０．５，１] ，对于表中（ｏ１ ，ｂ）的隶属度值为 ０．１，认 为病人 ｏ１ 的血压没有问题，可以不考虑。 表３ 置信度阈值为 Ｔ 的模糊形式背景 Ｔａｂｌｅ ３ Ｃｏｎｆｉｄｅｎｃｅ ｔｈｒｅｓｈｏｌｄｓ ｆｏｒ Ｔ ｆｕｚｚｙ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ａ ｂ ｃ ｄ ｅ ｆ ｏ１ ０．８ ０ ０．６１ ０．６ ０．８ ∗ ｏ２ ０．９ ０．８５ ∗ ０ ０．７ ０．９ ｏ３ ０ ∗ ０．８７ ∗ ０．６ ０．６ ｏ４ ０．６ ∗ ０ ∗ ０．５ ０ ２ 相似模糊概念与相容模糊概念 在形式概念分析中，对不完备形式背景进行完 备化处理，一般可采用以下 ３ 种方法。 １）删除法。 删除法即删除形式背景中缺失数 据的一列或者一行，也就是删除一个对象或者删除 一个属性。 这类方法操作起来比较简单，但是在删 除过程中会导致原先存在的数据缺失，可能会造成 获取的知识不准确。 ２）填补法。 填补法就是对不完备形式背景中 缺失的数据填充为 １ 或者 ０，使之补全为一个完备 的形式背景。 这类方法比较简单，但是容易造成获 取的知识错误，因为好多缺失信息都是人为地填充 ０ 或者 １。 ３）扩展属性法［１５］ 。 扩展属性法即把原有不完 备形式背景下的属性集合中的属性分为完备和不完 备属性两部分，然后将不完备属性在不同对象的不 同取值进行扩展，从而把不完备形式背景补充完整。 此方法的好处是既不会增加知识也不会缺失知识， 但是增加了知识获取的时间和空间复杂度。 定义 ６ 在不完备模糊形式背景 Ｋｃ ＝ （Ｇ′，Ｍ′， ＩＭ ） 中，对于集合 Ａ∈Ｇ′，记作： ＦＡ(Ａ) ＝ ｛ｍ ∈ Ｍ′ ｜ ∀ｇ ∈ Ａ：ｔ １ ≤ ｕ(ｇ，ｍ) ≤ ｔ ２ 或 ｕ(ｇ，ｍ) ＝ ∗｝ （５） 式中 Ａ∈Ｇ′。 ＦＯ(Ｂ) ＝ ｛ｇ ∈ Ｇ ｜ ∀ｍ ∈ Ｂ：ｔ １ ≤ ｕ(ｇ，ｍ) ≤ ｔ ２ 或 ｕ(ｇ，ｍ) ＝ ∗｝ （６） 式中 Ｂ⊆Ｍ′。 如果 ＦＡ(Ａ) ＝ Ｂ 且 ＦＯ(Ｂ) ＝ Ａ 称 (Ａ，Ｂ) 为模糊 形式背景 Ｋｃ 下的一个相似模糊概念，ｇ∈Ａ 时 ｕｇ 为 (Ａ，Ｂ) 中对象 ｇ 的隶属度值，其表示如式（７）： ·３５４· 智 能 系 统 学 报 第 １１ 卷
第3期 胡小康，等：基于相容模糊概念的规则提取方法 ·355· ug=min(u(g,m))m∈B (7) 证明假设(A,B)是(A,B)的一个子概念， 特别地当u(g,m)=*时可用补全法补全g与 (A,B)是粗糙相容模糊概念，即存在u(g,m)=*, m的隶属度值。在不完备形式背景下所有相似模糊 根据概念之间的继承关系可知g∈A1,m∈B1。 概念构成的集合可表示为w(K)。 相似模糊概念与相容模糊概念既有区别也有联 在相似概念(A,B)中，如果含有大量缺失数据， 系，在经典的不完备形式背景中“补全法”将缺失数 则涉及(4，B)的任何应用都是不可靠的，即它不仅 据补充为1，而在不完备的模糊形式背景中，相似模 降低了知识获取的有效性，反而会使不确定性进一 糊概念是将不完备模糊形式背景中的缺失数据补充 步扩散。下面在相似模糊概念的基础上提出了相容 为0.5得到的。而相容模糊概念是对相似模糊概念 模糊概念，通过设置参数（α，B)可满足不同用户的 的扩展，它是在相似模糊概念基础上通过设置参数 需求，（α，B)就叫做相容参数。 (α：，B),去除一些数据量缺失较大的相似模糊概念 定义7在不完备模糊形式背景K。= 而得到的。根据定义6和定义7以及传统的概念获 (G,M',Iw)中，设ACG,BCM',(M,B)∈o(K), 取算法[6，可以得出相似模糊概念和相容模糊概念 0≤a,B≤1，记作： 的构造算法，具体算法步骤参考算法1与算法2。 X(A,B)={a∈B1|(A,B).|≥a×Al}(8) 算法1在不完备形式背景K。中，相似模糊概 P(A,B)={x∈AI|(A,B)|≥×|B|}(9) 念的构造算法。 y(A,B)=AI+B(IX(A,B)+l(A,B)1) 输入不完备模糊形式背景K=(G,M,Iy), w(K)为空集。 (10) 输出相似模糊概念w(K)。 式中：(A,B)={x∈AIt1≤u(x,a)≤t2},(A,B)'= 1)先对不完备模糊形式背景进行处理，如果 {a∈BIt1≤u(x,a)≤t2},在相似模糊概念 (g,m)小于置信度阈值T,则u(g,m)为0，然后将 (A,B)中，X(A,B)表示属性a(Ha∈B)在K。中满 K。中的空缺数据*全部填充为0.5，即用补全法把 足集合(A,B)中元素数量大于α×|A的属性集 不完备形式背景转化为完备形式背景。 合。P(A,B)表示为对象x(Hx∈A)在K。满足集合 2)获得第一个概念(FO(M),M)设置概念的隶 (A,B)中元素数量大于a×|B|的对象集合。 属度值并加入(K)中。 如果Y(A,B)≥B则称(A,B)是相容模糊概念， 3)遍历对象g,其中g∈G,如果遍历完成转到 定义u为(A,B)的隶属度值，u可以表示为 6),反之转到4)。 ∑“ 4)遍历近似模糊概念(A,B),其中(A,B)∈ (11) w(K),如果遍历完成转到3)，否则转到5)。 在不完备模糊形式背景K中，基于参数（α，B) 5)求出B与FA(g)交集I,如果获得的交集I不 的所有相容概念构成的集合为w(K)。不完备模 是已获得w(K)的内涵，则计算出(FO(I),I)隶属 糊形式背景K.用补全法转化为完备的模糊形式背 度值并加入w(K)中然后回到4)。 景，其上获得的相似模糊概念(K)中有许多填充 6)输出w(K),算法结束。 的信息，通过参数：与外延中对象数量与内涵中属 算法2在不完备形式背景K中，相容模糊概 性数量的乘积，即aα×A与α×|B可以去掉填充值 念的获取算法。 较大概念。 输入不完备模糊形式背景K。=(G',M',I), 定义8如果在一个相容模糊概念中有“ 相似模糊概念o(K),w(K)为空集。 (g,m)=*则这个相容模糊概念称为粗糙概念，反 输出相容模糊概念wg(K。)。 之称为精确概念。 1)任取o(K)里的相似模糊概念并计算出 定理1在不完备模糊形式背景K。= X(4,B)、P(A,B)与Y(A,B)。如果Y(A,B)>B,计 (G',M',IM)中，如果(A,B)是粗糙概念，那么这个相 算出(A,B)的隶属度值并加入到相容模糊概念 容模糊概念的子概念至少存在一个概念，其粗糙 wg(K)中。 度为 2)如果相似模糊概念都被进行计算过，则输出 I u(g,m)(VeA=I 相容模糊概念转到3)，反之再进行1)。 I AI XI BI (12) 3)输出u(K),算法结束
ｕｇ ＝ ｍｉｎ(ｕ(ｇ，ｍ) ) ｍ ∈ Ｂ （７） 特别地当 ｕ (ｇ，ｍ) ＝ ∗时可用补全法补全 ｇ 与 ｍ 的隶属度值。 在不完备形式背景下所有相似模糊 概念构成的集合可表示为 ｗ Ｋｃ ( ) 。 在相似概念(Ａ，Ｂ) 中，如果含有大量缺失数据， 则涉及(Ａ，Ｂ) 的任何应用都是不可靠的，即它不仅 降低了知识获取的有效性，反而会使不确定性进一 步扩散。 下面在相似模糊概念的基础上提出了相容 模糊概念，通过设置参数（α，β）可满足不同用户的 需求，（α，β）就叫做相容参数。 定义 ７ 在 不 完 备 模 糊 形 式 背 景 Ｋｃ ＝ Ｇ′，Ｍ′，ＩＭ ( ) 中，设 Ａ⊆Ｇ′，Ｂ⊆Ｍ′， (Ａ，Ｂ) ∈ｗ Ｋｃ ( ) ， ０≤α，β≤１，记作： χ (Ａ，Ｂ) ＝ ｛ａ ∈ Ｂ ｜ (Ａ，Ｂ) ａ ≥ α × Ａ ｝ （８） φ(Ａ，Ｂ) ＝ ｛ｘ ∈ Ａ ｜ (Ａ，Ｂ) ｘ ≥ α × Ｂ ｝ （９） γ(Ａ，Ｂ) ＝ １ ｜ Ａ ｜ ＋｜ Ｂ ｜ （｜ χ (Ａ，Ｂ) ＋ φ(Ａ，Ｂ) ｜ ） （１０） 式中：(Ａ，Ｂ) ａ ＝ ｛ｘ∈Ａ ｜ ｔ １≤ｕ (ｘ，ａ) ≤ｔ ２ ｝， (Ａ，Ｂ) ｘ ＝ ｛ａ ∈ Ｂ ｜ ｔ １ ≤ ｕ (ｘ，ａ) ≤ ｔ ２ ｝， 在 相 似 模 糊 概 念 (Ａ，Ｂ) 中， χ (Ａ，Ｂ) 表示属性 ａ（∀ａ∈Ｂ）在 Ｋｃ 中满 足集合(Ａ，Ｂ) ａ 中元素数量大于 α × Ａ 的属性集 合。 φ(Ａ，Ｂ) 表示为对象 ｘ（∀ｘ∈Ａ）在 Ｋｃ 满足集合 (Ａ，Ｂ) ｘ 中元素数量大于 α× Ｂ 的对象集合。 如果 γ(Ａ，Ｂ) ≥β 则称(Ａ，Ｂ) 是相容模糊概念， 定义 ｕ － 为(Ａ，Ｂ) 的隶属度值，ｕ － 可以表示为 ｕ － ＝ ∑ｇ∈Ａ ｕｇ Ａ （１１） 在不完备模糊形式背景 Ｋｃ 中，基于参数（α，β） 的所有相容概念构成的集合为 ｗ α β （Ｋｃ ）。 不完备模 糊形式背景 Ｋｃ 用补全法转化为完备的模糊形式背 景，其上获得的相似模糊概念 ｗ Ｋｃ ( ) 中有许多填充 的信息，通过参数 α 与外延中对象数量与内涵中属 性数量的乘积，即 α× Ａ 与 α× Ｂ 可以去掉填充值 较大概念。 定义 ８ 如 果 在 一 个 相 容 模 糊 概 念 中 有 ｕ (ｇ，ｍ) ＝ ∗则这个相容模糊概念称为粗糙概念，反 之称为精确概念。 定理 １ 在 不 完 备 模 糊 形 式 背 景 Ｋｃ ＝ Ｇ′，Ｍ′，ＩＭ ( ) 中，如果（Ａ，Ｂ）是粗糙概念，那么这个相 容模糊概念的子概念至少存在一个概念，其粗糙 度为 ｜ ｕ (ｇ，ｍ) （∀ｇ∈Ａ） ＝ ∗ ｜ ｜ Ａ ｜ ×｜ Ｂ ｜ （１２） 证明 假设（Ａ１ ，Ｂ１ ） 是（Ａ，Ｂ） 的一个子概念， （Ａ，Ｂ）是粗糙相容模糊概念，即存在 ｕ (ｇ，ｍ) ＝ ∗， 根据概念之间的继承关系可知 ｇ∈Ａ１ ，ｍ∈Ｂ１ 。 相似模糊概念与相容模糊概念既有区别也有联 系，在经典的不完备形式背景中“补全法”将缺失数 据补充为 １，而在不完备的模糊形式背景中，相似模 糊概念是将不完备模糊形式背景中的缺失数据补充 为 ０．５ 得到的。 而相容模糊概念是对相似模糊概念 的扩展，它是在相似模糊概念基础上通过设置参数 （α，β），去除一些数据量缺失较大的相似模糊概念 而得到的。 根据定义 ６ 和定义 ７ 以及传统的概念获 取算法［１６］ ，可以得出相似模糊概念和相容模糊概念 的构造算法，具体算法步骤参考算法 １ 与算法 ２。 算法 １ 在不完备形式背景 Ｋｃ 中，相似模糊概 念的构造算法。 输入 不完备模糊形式背景 Ｋｃ ＝ Ｇ′，Ｍ′，ＩＭ ( ) ， ｗ Ｋｃ ( ) 为空集。 输出 相似模糊概念 ｗ Ｋｃ ( ) 。 １）先对不完备模糊形式背景进行处理，如果 ｕ (ｇ，ｍ) 小于置信度阈值 Ｔ，则 ｕ (ｇ，ｍ) 为 ０，然后将 Ｋｃ 中的空缺数据∗全部填充为 ０．５，即用补全法把 不完备形式背景转化为完备形式背景。 ２）获得第一个概念（ＦＯ（Ｍ），Ｍ）设置概念的隶 属度值并加入 ｗ（Ｋｃ）中。 ３）遍历对象 ｇ，其中 ｇ∈Ｇ，如果遍历完成转到 ６），反之转到 ４）。 ４）遍历近似模糊概念（ Ａ，Ｂ），其中（ Ａ，Ｂ） ∈ ｗ Ｋｃ ( ) ，如果遍历完成转到 ３），否则转到 ５）。 ５）求出 Ｂ 与 ＦＡ(ｇ) 交集 Ｉ，如果获得的交集 Ｉ 不 是已获得 ｗ Ｋｃ ( ) 的内涵，则计算出（ＦＯ（ Ｉ），Ｉ）隶属 度值并加入 ｗ Ｋｃ ( ) 中然后回到 ４）。 ６）输出 ｗ Ｋｃ ( ) ，算法结束。 算法 ２ 在不完备形式背景 Ｋｃ 中，相容模糊概 念的获取算法。 输入 不完备模糊形式背景 Ｋｃ ＝ Ｇ′，Ｍ′，ＩＭ ( ) ， 相似模糊概念 ｗ Ｋｃ ( ) ，ｗ α β（Ｋｃ）为空集。 输出 相容模糊概念 ｗ α β（Ｋｃ）。 １）任取 ｗ Ｋｃ ( ) 里的相似模糊概念并计算出 χ (Ａ，Ｂ) 、φ(Ａ，Ｂ) 与 γ（ Ａ，Ｂ）。 如果 γ（ Ａ，Ｂ） ＞β，计 算出（Ａ，Ｂ） 的隶属度值 ｕ － 并加入到相容模糊概念 ｗ α β（Ｋｃ）中。 ２）如果相似模糊概念都被进行计算过，则输出 相容模糊概念转到 ３），反之再进行 １）。 ３）输出 ｗ α β（Ｋｃ），算法结束。 第 ３ 期 胡小康，等：基于相容模糊概念的规则提取方法 ·３５５·
·356· 智能系统学报 第11卷 3基于相容模糊概念的规则提取 可以将得到的规则B,=B,-B2加入Σ中，其可信度 是IA,I/八A2I。 关联规则数据挖掘中最活跃的研究方法之 3)如果对于节点C=(4,B)有多个双亲节点， 一【2。规则就是形如“如果…那么…(f…Then 则任取两个双亲节点C,=(A1,B,)与C2=(42,B2), …)”前者为条件，后者为结果。典型的关联规则发 现问题是对超市中的购物篮数据进行分析，例如最 如果满足条件min(i(A,B,),a(4,B, >7,则可 max(u(A:,B),u(A2,B2)) 著名的案例就是啤酒与尿布。 以提取到的规则B,→B2与B2→B1,并将其加入∑ 对于关联规则A→B的支持度是supP(A→B)= 中，支持度分别为1A1/八AI与1AI/八A2I。 IFO(AUB)I/IUI,置信度为conf(A→B)>B关联规 4)输出∑。 则A→B被称为关于(w,r)关联规则，当supp(A曰 在得到提取规则∑后，可以给其支持度阈值ω B)>w时把AUB称为频繁的。 与置信度阈值？。然后根据需要从提取的规则中筛 在不完备的模糊背景下，规则提取是一件比较 选出符合要求的规则。 困难的工作，在之前的工作中已经获得了相似模糊 概念和相容模糊概念，然后根据算法3构造好相似 4示例展示 模糊概念格，但是由于相似模糊概念中有许多不确 现在举例来展示规则提取的过程，在表3中讨 定性信息，所以构造的相似模糊概念格也是不准确 论的置信度阈值是T=[0.5,1],通过算法1，可以得出 的。通过对相似模糊概念的筛选，最后得到了较为 在表3的不完备模糊背景下形成的相似模糊概念为 准确的相容模糊概念，可以在构造好的相似模糊概 1){☑，(a,b,c,d,ef)}; 念格基础上得到相容模糊概念的之间的偏序关系， 2){(0.6/o1),(a,c,d,ef); 从而可以提取出可信度较高的关联规则，具体算法 3){(0.5/o2),(a,b,c,ef)}; 参考算法4。 4){(0.61/o1,0.5/o2),(a,c,ef}; 算法3相似模糊概念格的构造算法。 5){(0.5/o3),(b,c,d,ef)}; 输入不完备模糊形式背景K。=(G',M',Iw), 6){(0.6/o1,0.5/o3),(c,d,ef}: 相似模糊概念w(K)。 7){(0.5/o2,0.5/o3),(b,c,e)}: 输出相似模糊概念格。 8){(0.61/o1,0.5/o2,0.6/o3),(c,e,f)}. 1)遍历相似模糊概念(A,B),其中(A,B)∈0 9){(0.5/oa),(a,b,d,e)}: (K),并且设置(A,B)的count为0。如果遍历完成 10){(0.6/o1,0.5/o4),(a,d,e)}; 则转4)，否则转2)。 11){(0.7/o2,0.5/o4),(a,b,e)}; 2)遍历属性m,其中m∈M,并求得A与FO(m) 12){(0.8/o1,0.7/o2,0.5/o4),(a,e)}: 交集I。如果遍历结束转到1)，否则转到3)。 13){(0.5/o3,0.5/o4),(b,d,e)}: 3)在w(K)找出相似模糊概念(A1,B,)使得 14){(0.6/o1,0.5/o3,0.5/o4),(d,e)}; A,=I,并把概念(A1,B,)的count值加1。假如 15){(0.7/o2,0.5/o3,0.5/o4),(b,e)}: IB,I-IB1等于(A1,B)的count值，则增加边在 16){(o1,o2,03,04),(0a,0yb,0yc,0yd,05/e,0yfio (A1,B)与(A,B),反之转2)。 4)输出相似模糊概念格，算法结束。 16 算法4不完备形式背景下规则提取的算法。 输入不完备模糊形式背景K。=(G,M',Iw), 4口5 相容模糊概念1g(K)。 力3 输出关联规则Σ。 1)对相似模糊概念格进行处理，除去相容模糊 概念之外的概念，更新父节点和子节点。 2)如果概念C1=(A1,B1)与C2=(42,B2)满足 C2是C,的父节点，且满足C,与C2的隶属度大于 给定的阑值，即min(i(A,B,),i(A,B,)） 图2相似模糊概念的相似模糊概念格 >n,则 Fig.2 Approximat fuzzy concept lattice max(u(A,B),u(A2,B2)) 图2是相似模糊概念格对应的Hasse图。上述
３ 基于相容模糊概念的规则提取 关联规则数据挖掘中最活跃的研究方法之 一［１７⁃２１］ 。 规则就是形如“如果…那么…（ Ｉｆ…Ｔｈｅｎ …）”前者为条件，后者为结果。 典型的关联规则发 现问题是对超市中的购物篮数据进行分析，例如最 著名的案例就是啤酒与尿布。 对于关联规则 Ａ⇒Ｂ 的支持度是 ｓｕｐｐ（Ａ⇒Ｂ）＝ ｜ ＦＯ（Ａ∪Ｂ） ｜ ／ ｜Ｕ｜ ，置信度为 ｃｏｎｆ（Ａ⇒Ｂ）＞β 关联规 则 Ａ⇒Ｂ 被称为关于（ω，τ）关联规则，当 ｓｕｐｐ（Ａ⇒ Ｂ）＞ω 时把 Ａ∪Ｂ 称为频繁的。 在不完备的模糊背景下，规则提取是一件比较 困难的工作，在之前的工作中已经获得了相似模糊 概念和相容模糊概念，然后根据算法 ３ 构造好相似 模糊概念格，但是由于相似模糊概念中有许多不确 定性信息，所以构造的相似模糊概念格也是不准确 的。 通过对相似模糊概念的筛选，最后得到了较为 准确的相容模糊概念，可以在构造好的相似模糊概 念格基础上得到相容模糊概念的之间的偏序关系， 从而可以提取出可信度较高的关联规则，具体算法 参考算法 ４。 算法 ３ 相似模糊概念格的构造算法。 输入 不完备模糊形式背景 Ｋｃ ＝ Ｇ′，Ｍ′，ＩＭ ( ) ， 相似模糊概念 ｗ Ｋｃ ( ) 。 输出 相似模糊概念格。 １）遍历相似模糊概念（ Ａ，Ｂ），其中（ Ａ，Ｂ） ∈ｗ Ｋｃ ( ) ，并且设置（Ａ，Ｂ）的 ｃｏｕｎｔ 为 ０。 如果遍历完成 则转 ４），否则转 ２）。 ２）遍历属性 ｍ，其中 ｍ∈Ｍ，并求得 Ａ 与ＦＯ（ｍ） 交集 Ｉ。 如果遍历结束转到 １），否则转到 ３）。 ３）在 ｗ Ｋｃ ( ) 找出相似模糊概念 Ａ１ ，Ｂ１ ( ) 使得 Ａ１ ＝ Ｉ， 并 把 概 念 Ａ１ ，Ｂ１ ( ) 的 ｃｏｕｎｔ 值 加 １。 假 如 ｜ Ｂ１ ｜ － ｜ Ｂ ｜ 等 于 Ａ１ ，Ｂ１ ( ) 的 ｃｏｕｎｔ 值， 则 增 加 边 在 Ａ１ ，Ｂ１ ( ) 与（Ａ，Ｂ），反之转 ２）。 ４）输出相似模糊概念格，算法结束。 算法 ４ 不完备形式背景下规则提取的算法。 输入 不完备模糊形式背景 Ｋｃ ＝ Ｇ′，Ｍ′，ＩＭ ( ) ， 相容模糊概念 ｗ α β（Ｋｃ）。 输出 关联规则∑。 １）对相似模糊概念格进行处理，除去相容模糊 概念之外的概念，更新父节点和子节点。 ２）如果概念 Ｃ１ ＝ Ａ１ ，Ｂ１ ( ) 与 Ｃ２ ＝ Ａ２ ，Ｂ２ ( ) 满足 Ｃ２ 是 Ｃ１ 的父节点，且满足 Ｃ１ 与 Ｃ２ 的隶属度大于 给定的阈值 η，即 ｍｉｎ（ｕ － （Ａ１ ，Ｂ１ ），ｕ － （Ａ２ ，Ｂ２ ）） ｍａｘ（ｕ － （Ａ１ ，Ｂ１ ），ｕ － （Ａ２ ，Ｂ２ ）） ＞η，则 可以将得到的规则 Ｂ２ ＝ Ｂ１ －Ｂ２ 加入∑中，其可信度 是｜ Ａ１ ｜ ／ ｜ Ａ２ ｜ 。 ３）如果对于节点 Ｃ ＝ (Ａ，Ｂ) 有多个双亲节点， 则任取两个双亲节点 Ｃ１ ＝ Ａ１ ，Ｂ１ ( ) 与 Ｃ２ ＝ Ａ２ ，Ｂ２ ( ) ， 如果满足条件 ｍｉｎ（ｕ － （Ａ１ ，Ｂ１ ），ｕ － （Ａ２ ，Ｂ２ ）） ｍａｘ（ｕ － （Ａ１ ，Ｂ１ ），ｕ － （Ａ２ ，Ｂ２ ）） ＞η，则可 以提取到的规则 Ｂ１⇒Ｂ２ 与 Ｂ２⇒Ｂ１ ，并将其加入∑ 中，支持度分别为｜ Ａ ｜ ／ ｜ Ａ１ ｜与｜ Ａ ｜ ／ ｜ Ａ２ ｜ 。 ４）输出∑。 在得到提取规则∑后，可以给其支持度阈值 ω 与置信度阈值 τ。 然后根据需要从提取的规则中筛 选出符合要求的规则。 ４ 示例展示 现在举例来展示规则提取的过程，在表 ３ 中讨 论的置信度阈值是 Ｔ＝［０．５，１］，通过算法 １，可以得出 在表 ３ 的不完备模糊背景下形成的相似模糊概念为 １）｛∅，（ａ，ｂ，ｃ，ｄ，ｅ，ｆ）｝； ２）｛（０．６ ／ ｏ１ ），（ａ，ｃ，ｄ，ｅ，ｆ）｝； ３）｛（０．５ ／ ｏ２ ），（ａ，ｂ，ｃ，ｅ，ｆ）｝； ４）｛（０．６１ ／ ｏ１ ，０．５ ／ ｏ２ ），（ａ，ｃ，ｅ，ｆ）｝； ５）｛（０．５ ／ ｏ３ ），（ｂ，ｃ，ｄ，ｅ，ｆ）｝； ６）｛（０．６ ／ ｏ１ ，０．５ ／ ｏ３ ），（ｃ，ｄ，ｅ，ｆ）｝； ７）｛（０．５ ／ ｏ２ ，０．５ ／ ｏ３ ），（ｂ，ｃ，ｅ，ｆ）｝； ８）｛（０．６１ ／ ｏ１ ，０．５ ／ ｏ２ ，０．６ ／ ｏ３ ），（ｃ，ｅ，ｆ）｝．； ９）｛（０．５ ／ ｏ４ ），（ａ，ｂ，ｄ，ｅ）｝； １０）｛（０．６ ／ ｏ１ ，０．５ ／ ｏ４ ），（ａ，ｄ，ｅ）｝； １１）｛（０．７ ／ ｏ２ ，０．５ ／ ｏ４ ），（ａ，ｂ，ｅ）｝； １２）｛（０．８ ／ ｏ１ ，０．７ ／ ｏ２ ，０．５ ／ ｏ４ ），（ａ，ｅ）｝； １３）｛（０．５ ／ ｏ３ ，０．５ ／ ｏ４ ），（ｂ，ｄ，ｅ）｝； １４）｛（０．６ ／ ｏ１ ，０．５ ／ ｏ３ ，０．５ ／ ｏ４ ），（ｄ，ｅ）｝； １５）｛（０．７ ／ ｏ２ ，０．５ ／ ｏ３ ，０．５ ／ ｏ４ ），（ｂ，ｅ）｝； １６）｛（ｏ１，ｏ２，ｏ３，ｏ４），（０／ ａ，０／ ｂ，０／ ｃ，０／ ｄ，０．５／ ｅ，０／ ｆ）｝。 图 ２ 相似模糊概念的相似模糊概念格 Ｆｉｇ．２ Ａｐｐｒｏｘｉｍａｔ ｆｕｚｚｙ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ 图 ２ 是相似模糊概念格对应的Ｈａｓｓｅ 图。上述 ·３５６· 智 能 系 统 学 报 第 １１ 卷