第11卷第4期 智能系统学报 Vol.11 No.4 2016年8月 CAAI Transactions on Intelligent Systems Aug.2016 D0I:10.11992/6is.201606008 网络出版地址：http:/www.cnki.net/kcms/detail/23.1538.TP.20160808.0830.016.html 横向拆分形势背景下的快速规则提取方法 温云霞1，王俊红12 (1.山西大学计算机与信息技术学院，山西太原030006：2.计算智能与中文信息处理教育部重点实验室，山西太原030006) 摘要：概念格是进行数据挖掘和规则提取的一种有效工具。目前已经提出的概念格上的规则提取方法大多是针 对整个形式背景，得到的规则数目较多，规则集规模较大，且这种规则结构不便于两个规则集的合并。针对这个问 题，本文提出一种伪规则的概念，并给出渐近式获取伪规则的方法：同时证明了通过伪规则集，用户可以根据自己的 兴趣有选择地从伪规则集合中产生出所需的蕴含规则：提出了将两个伪规则集进行合并的方法，从而用户可以通过 拆分合并的思想来获取规则集：最后通过实验分析验证了算法的有效性。 关键词：概念格：形式背景：子背景：规则提取：伪规则：规则合并 中图分类号：TP18文献标志码：A文章编号：1673-4785(2016)04-0526-08 中文引用格式：温云覆，王俊红.横向拆分形势背景下的快速规则提取方法[J].智能系统学报，2016,11(4)：526-533. 英文引用格式：WEN Yunxia,WANG Junhong.Research on a fast method for extracting rules based on horizontal splitting[J]. CAAI Transactions on Intelligent Systems,2016,11(4):526-533. Research on a fast method for extracting rules based on horizontal splitting WEN Yunxia',WANG Junhong'2 (1.School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China;2.Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education,Taiyuan 030006,China) Abstract:The concept lattice is a valid tool for data mining and rule extraction.The methods of extracting rules from the concept lattice are based mainly on the whole formal context,but this results in a large number of rules and rule sets,and it is difficult to combine the rule sets subsets with the original structure.In this paper,the con- cept of a pseudo rule set and its incremental determination method is given;users can get the needed implication rules from the pseudo rule set,according to their interests.A method of combining two pseudo rule sets is then giv- en.Users may therefore get their rule sets by dividing or combining these sets.The effectiveness of this method is proven through experiment analysis. Keywords:concept lattice;formal context;subcontext;extracting rules;pseudo rule;combination of the rule set 概念格[-)是数据分析和知识处理的一种有力的形式背景下概念格构造的复杂度很高，一个可行 工具，由Wl)在1982年提出。近年来获得了飞的方法是把形式背景拆分成多个子形式背景) 速的发展，概念格理论)已经被广泛地应用于软件 分别存储和处理。这种方法的思想是在每个子形式 工程、知识工程、数据挖掘和信息检索等领域。 背景上构造概念格并通过子概念格的合并得到所需 在多源信息系统和数据分布式存储与并行处理 的概念格。概念格的分布式处理大大减少了概念格 中，数据都是分别存储和处理的。另一方面，在较大 的构造复杂度，但对子概念格上获得的规则集之间 的联系，以及不通过子概念格合并直接利用规则集 收稿日期：2016-06-02.网络出版日期：2016-08-08. 基金项目：国家自然科学基金项目(612022018,61303008). 融合产生新规则的研究还较少。 通信作者：王俊红.E-mail:wjhwjh@sxu.cd.em 概念格表明了概念之间的泛化和例化关系，这第 １１ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．４ ２０１６ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０６００８ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０８０８．０８３０．０１６．ｈｔｍｌ 横向拆分形势背景下的快速规则提取方法 温云霞１ ， 王俊红１，２ （１． 山西大学 计算机与信息技术学院，山西 太原 ０３０００６； ２． 计算智能与中文信息处理教育部重点实验室，山西 太原 ０３０００６） 摘 要：概念格是进行数据挖掘和规则提取的一种有效工具。 目前已经提出的概念格上的规则提取方法大多是针 对整个形式背景，得到的规则数目较多，规则集规模较大，且这种规则结构不便于两个规则集的合并。 针对这个问 题，本文提出一种伪规则的概念，并给出渐近式获取伪规则的方法；同时证明了通过伪规则集，用户可以根据自己的 兴趣有选择地从伪规则集合中产生出所需的蕴含规则；提出了将两个伪规则集进行合并的方法，从而用户可以通过 拆分合并的思想来获取规则集；最后通过实验分析验证了算法的有效性。 关键词：概念格； 形式背景； 子背景； 规则提取； 伪规则； 规则合并 中图分类号： ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１６）０４－０５２６－０８ 中文引用格式：温云霞， 王俊红． 横向拆分形势背景下的快速规则提取方法［Ｊ］． 智能系统学报， ２０１６， １１（４）： ５２６－５３３． 英文引用格式：ＷＥＮ Ｙｕｎｘｉａ， ＷＡＮＧ Ｊｕｎｈｏｎｇ． Ｒｅｓｅａｒｃｈ ｏｎ ａ ｆａｓｔ ｍｅｔｈｏｄ ｆｏｒ ｅｘｔｒａｃｔｉｎｇ ｒｕｌｅｓ ｂａｓｅｄ ｏｎ ｈｏｒｉｚｏｎｔａｌ ｓｐｌｉｔｔｉｎｇ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（４）： ５２６－５３３． Ｒｅｓｅａｒｃｈ ｏｎ ａ ｆａｓｔ ｍｅｔｈｏｄ ｆｏｒ ｅｘｔｒａｃｔｉｎｇ ｒｕｌｅｓ ｂａｓｅｄ ｏｎ ｈｏｒｉｚｏｎｔａｌ ｓｐｌｉｔｔｉｎｇ ＷＥＮ Ｙｕｎｘｉａ １ ， ＷＡＮＧ Ｊｕｎｈｏｎｇ １，２ （１． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， Ｓｈａｎｘｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｔａｉｙｕａｎ ０３０００６， Ｃｈｉｎａ； ２． Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ａｎｄ Ｃｈｉｎｅｓｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ ｏｆ Ｍｉｎｉｓｔｒｙ ｏｆ Ｅｄｕｃａｔｉｏｎ， Ｔａｉｙｕａｎ ０３０００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｉｓ ａ ｖａｌｉｄ ｔｏｏｌ ｆｏｒ ｄａｔａ ｍｉｎｉｎｇ ａｎｄ ｒｕｌｅ ｅｘｔｒａｃｔｉｏｎ． Ｔｈｅ ｍｅｔｈｏｄｓ ｏｆ ｅｘｔｒａｃｔｉｎｇ ｒｕｌｅｓ ｆｒｏｍ ｔｈｅ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ａｒｅ ｂａｓｅｄ ｍａｉｎｌｙ ｏｎ ｔｈｅ ｗｈｏｌｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ， ｂｕｔ ｔｈｉｓ ｒｅｓｕｌｔｓ ｉｎ ａ ｌａｒｇｅ ｎｕｍｂｅｒ ｏｆ ｒｕｌｅｓ ａｎｄ ｒｕｌｅ ｓｅｔｓ， ａｎｄ ｉｔ ｉｓ ｄｉｆｆｉｃｕｌｔ ｔｏ ｃｏｍｂｉｎｅ ｔｈｅ ｒｕｌｅ ｓｅｔｓ ｓｕｂｓｅｔｓ ｗｉｔｈ ｔｈｅ ｏｒｉｇｉｎａｌ ｓｔｒｕｃｔｕｒｅ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｔｈｅ ｃｏｎ⁃ ｃｅｐｔ ｏｆ ａ ｐｓｅｕｄｏ ｒｕｌｅ ｓｅｔ ａｎｄ ｉｔｓ ｉｎｃｒｅｍｅｎｔａｌ ｄｅｔｅｒｍｉｎａｔｉｏｎ ｍｅｔｈｏｄ ｉｓ ｇｉｖｅｎ； ｕｓｅｒｓ ｃａｎ ｇｅｔ ｔｈｅ ｎｅｅｄｅｄ ｉｍｐｌｉｃａｔｉｏｎ ｒｕｌｅｓ ｆｒｏｍ ｔｈｅ ｐｓｅｕｄｏ ｒｕｌｅ ｓｅｔ， ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅｉｒ ｉｎｔｅｒｅｓｔｓ． Ａ ｍｅｔｈｏｄ ｏｆ ｃｏｍｂｉｎｉｎｇ ｔｗｏ ｐｓｅｕｄｏ ｒｕｌｅ ｓｅｔｓ ｉｓ ｔｈｅｎ ｇｉｖ⁃ ｅｎ． Ｕｓｅｒｓ ｍａｙ ｔｈｅｒｅｆｏｒｅ ｇｅｔ ｔｈｅｉｒ ｒｕｌｅ ｓｅｔｓ ｂｙ ｄｉｖｉｄｉｎｇ ｏｒ ｃｏｍｂｉｎｉｎｇ ｔｈｅｓｅ ｓｅｔｓ． Ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｉｓ ｍｅｔｈｏｄ ｉｓ ｐｒｏｖｅｎ ｔｈｒｏｕｇｈ ｅｘｐｅｒｉｍｅｎｔ ａｎａｌｙｓｉｓ． Ｋｅｙｗｏｒｄｓ： ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ； ｆｏｒｍａｌ ｃｏｎｔｅｘｔ； ｓｕｂｃｏｎｔｅｘｔ； ｅｘｔｒａｃｔｉｎｇ ｒｕｌｅｓ； ｐｓｅｕｄｏ ｒｕｌｅ； ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｔｈｅ ｒｕｌｅ ｓｅｔ 收稿日期：２０１６－０６－０２． 网络出版日期：２０１６－０８－０８． 基金项目：国家自然科学基金项目（６１２０２２０１８，６１３０３００８）． 通信作者：王俊红． Ｅ⁃ｍａｉｌ：ｗｊｈｗｊｈ＠ ｓｘｕ．ｅｄｕ．ｃｎ． 概念格［１－３］是数据分析和知识处理的一种有力 工具，由 Ｗｉｌｌｅ ［１］ 在 １９８２ 年提出。 近年来获得了飞 速的发展，概念格理论［２］ 已经被广泛地应用于软件 工程、知识工程、数据挖掘和信息检索等领域。 在多源信息系统和数据分布式存储与并行处理 中，数据都是分别存储和处理的。 另一方面，在较大 的形式背景下概念格构造的复杂度很高，一个可行 的方法是把形式背景拆分成多个子形式背景［４－５］ ， 分别存储和处理。 这种方法的思想是在每个子形式 背景上构造概念格并通过子概念格的合并得到所需 的概念格。 概念格的分布式处理大大减少了概念格 的构造复杂度，但对子概念格上获得的规则集之间 的联系，以及不通过子概念格合并直接利用规则集 融合产生新规则的研究还较少。 概念格表明了概念之间的泛化和例化关系，这