优势关系下属性值粗化细化时近似集分析

2023年12月29日发(作者：2023安徽数学试卷)

第３６卷　第１２期　Ｖｏ１．３６　・计算机工程　２０１０年６月　Ｊｕｎｅ　２０１０　Ｎｏ．１２　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　软件技术与数据库・　文章编号；１ｏｏ　４２８（２ｏ１ｏ）１２＿＿伽３３＿－０３　文献标识码；Ａ　中图分类号：ＴＰ３１１　优势关系下属性值粗化细化时近似集分析　季晓岚　，李天王Ｉ｝　，邹维丽　，陈红梅　（１．西南交通大学信息科学与技术学院，成都６１００３１；２．西南交通大学数学学院，成都６１００３Ｉ）　摘要：基于优势关系粗糙集模型反映属性间的偏好情况，实际上多数数据库中的数据是动态变化的。如何利用已有的信息更新近似集对　于提高知识发现效率有重要意义。提出不完备信息系统在优势关系下属性值粗化细化的定义，讨论优势关系下不完备信息系统中属性值粗　化细化时近似集的变化情况，对比分析优势关系下属性值粗化细化前后的粗糙近似精度和粗糙近似质量。通过实例分析验证了该方法的有　效性。　关健诃：不完备信息系统；粗糙集；优势关系；近似集　Ａｎａｌｙｓｉｓ　“Ａｐｐｒｏｘｉｍａｔｉｏｎｓ　ｙｓｉｓ　ｏｌ　Ａ　ｒｏｘｉｍａｔｉｏｎｓ　Ｕ　Ｕｎｄｅｒ　ｎ　Ｄｏｍｉｎａｎｃｌｏｍｉｎａｎｃｅ　　ＲｅｌａｔｉｏｎＤｕｒｉｎｇ　Ａｔｔｒｉｂｕｔｅ　Ｖａｌｕｅｓ　Ｃｏａｒｓｅｎｉｎｇ　ａｎｄ　Ｒｅｆｉｎｉｎｇ　ＪＩ　Ｘｉａｏ．１ａｎ　，ＬＩ　Ｔｉａｎ．ｒｕｉ　，ＺＯＵ　Ｗｅｉ．１ｉ　，ＣＨＥＮ　Ｈｏｎｇ．ｍｅｉ　（１．Ｓｃｈｏｏｌ　ｏｆＩｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｓｏｕｔｈｗｅｓｔ　ＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ　６１００３ｌ：　２．Ｓｃｈｏｏｌ　ｏｆＭａｔｈｅｍａｔｉｃｓ，Ｓｏｕｔｈｗｅｓｔ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ　６１００３１）　［Ａｂｓｔｒａｃｔ］Ｉｎ　ｔｈｅ　ｄｏｍｉｎａｎｃｅ—ｂａｓｅｄ　ｒｏｕｇｈ　ｓｅｔｓ　ａｐｐｒｏａｃｈ，ａｔｔｒｉｂｕｔｅｓ　ｖａｌｕｅｓ　ｉｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍｓ　ｈａｖｅ　ｐｒｅｆｅｒｅｎｃｅ　ｒｅｌａｔｉｏｎ．Ｍａｎｙ　ｄａｔａ　ｓｏｕｒｃｅｓ　ｈａｖｅ　ｄｙｎａｍｉｃ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ．Ｈｏｗ　ｔＯ　ｕｐｄａｔｅ　ａｐｐｒｏｘｉｍａｔｉｏｎｓ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｏｒｉｇｉｎａｌ　ａｐｐｒｏｘｉｍａｔｉｏｎｓ　ｉｎｆｏｒｍａｔｉｏｎ　ｉｓ　ａｎ　ｉｍｐｏｒｔａｎｔ　ｐｒｏｂｌｅｍ　ｓｉｎｃｅ　ｉｔ　ｍａ３，　ｉｍｐｒｏｖｅ　ｔｈｅ　ｅｆｉｃｉｆｅｎｃｙ　ｏｆ　ｋｎｏｗｌｅｄｇｅ　ｄｉｓｃｏｖｅｒｙ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｖｉｄｅｓ　ｔｈｅ　ｄｅｆｉｎｉｔｉｏｎｓ　ｏｆ　ａｔｔｒｉｂｕｔｅ　ｖａｌｕｅｓ　ｃｏａｒｓｅｎｉｎｇ　ａｎｄ　ｒｅｆｉｎｉｎｇ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｄｏｍｉｎａｎｃｅ　ｒｅｌａｔｉｏｎ　ｉｎ　ｉｎｃｏｍｐｌｅｔｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍｓ，ｆｏｃｕｓｅｓ　ｏｎ　ｄｉｓｃｕｓｓｉｎｇ　ａｎｄ　ａｎａｌｙｚｉｎｇ　ｔｈｅ　ｃｈａｎｇｅ　ｏｆ　ｕｐｐｅｒ　ａｎｄ　ｌｏｗｅｒ　ａｐｐｒｏｘｉｍａｔｉｏｎｓ，ｒｏｕｇｈ　ａｐｐｒｏｘｉｍａｔｉｏｎ　ａｃｃｕｒａｃｙ　ａｎｄ　ｔｈｅ　ｑｕａｌｉｔｙ　ｏｆ　ｒｏｕｇｈ　ａｐｐｒｏｘｉｍａｔｉｏｎｓ　ｉｎ　ｉｎｃｏｍｐｌｅｔｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍｓ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｄｏｍｉｎａｎｃｅ　ｒｅｌａｔｉｏｎ　ｗｈｉｌｅ　ａｔｔｉｂｕｔｒｅ　ｖａｌｕｅｓ　ａｒｅ　ｃｏａｒｓｅｎｅｄ　ｏｒ　ｒｅｆｉｎｅｄ　ｒｅｓｐｅｃｔｉｖｅｌｙ．Ａｎ　ｅｘａｍｐｌｅ　ｉｓ　ｕｓｅｄ　ｔｏ　ｉｌｌｕｓｔｒａｔｅ　ｔｈｅ　ｖａｌｉｄｉｔｙ　ｏｆ　ｈｅ　ｔｍｅｔｈｏｄ．　［Ｋｅｙ　ｗｏｒｄｓ］ｉｎｃｏｍｐｌｅｔｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍ；ｒｏｕｇｈ　ｓｅｔ；ｄｏｍｉｎａｎｃｅ　ｒｅｌａｔｉｏｎ；ａｐｐｒｏｘｉｍａｔｉｏｎｓ　１概述　粗糙集理论是一种用于处理不完备和不精确知识的数学　多个属性同时增删时近似集的增量式更新方法和规则提取方　法。然而，在属性值改变时，对属性值粗化细化时基于优势　工具…。它以等价关系为基础，发现信息系统中隐含的知识，　进行规则提取，在机器学习、模式识别和数据挖掘等领域得　到了成功的应用　Ｊ。　在现实世界中，很多属性是具有偏好信息的，属性不但　以一种有序的状态存在，而且还存在一种优势关系，如用于　评价火车是否舒适的噪声指数、振动指数、空气流动等属性。　关系粗糙集模型的动态知识发现问题却未见报道。本文讨论　在优势关系下不完备信息系统中属性值粗化细化时近似集的　变化情况，为基于优势关系粗糙集模型的动态知识发现问题　的研究提供了基础。　２基本概念　定义１Ｌ２　设四元组Ｓ＝ｆＵ，Ａ，Ｖ，ｆ１是一个信息系统。其　中，　是非空的有限对象集合；Ａ是非空的有限属性集合；　由于传统的粗糙集只考虑属性值是否可区分，而不考虑其偏　好关系，因此在系统分析过程中不能很好地表达其原有的偏　好信息。针对基于等价关系的经典粗糙集方法不能解决带有　偏好关系属性问题，文献【３—４】提出的基于优势关系的粗糙集　方法考虑了属性取值之间存在的偏好关系，弥补了传统粗糙　集的缺陷。近年来，基于优势关系的粗糙集方法得到了人们　的普遍关注。例如，文献［５】给出了优势关系下不完备有序信　息系统中的知识约简方法；文献【６】讨论了基于有限扩展优势　关系的粗糙决策分析方法；文献［７】设计了优势关系下信息系　Ｖ＝｛　：ｑ∈Ａ｝，属性值　具有偏好次序，即属性值域是全　序集；ｆ：ＵｘＡ＿÷　是一个信息函数，使ｆ（　，ｑ）∈　，　（　，ｑ）∈ＵｘＡ。　表示某条记录在对应属性上的值不可知。如果　ｅ　，　ｑ∈Ａ，则称此信息系统为不完备信息系统，否则，称为完备　信息系统。　基金项目：国家自然科学基金资助项目“基于粒计算的动态知识发　现中若干关键问题研究”（６０８７３１０８）　统分配约筒的矩阵算法。　现实中数据的动态变化是多数数据库的一个主要特点。　针对这一特点，不少学者从属性集粗化细化、对象集粗化细　化２个方面对基于粗糙集的动态知识发现问题进行了研究。　如文献【８】在经典粗糙集框架下提出了单个属性增加与删除　作者简介：季晓岚（１９８４－），女，硕士研究生，主研方向：智能信息　处理；李天瑞，教授、博士、博士生导师；邹维丽，硕士研究生；　陈红梅，讲师、博士研究生　时近似集的增量式更新方法和规则提取方法。文献【９】实现了　收稿日期．２００９—１１—２４　Ｅ－ｍａｉｌ：ｘｉａｏｌａｎ一６７７＠１２６．ｃｏｒｎ　一３３—　

假定　是一个全Ｇｒｅｃｏ序集，即对于Ｖｘ，ｙｅ　Ｕ，　定义８设信息系统ｓ，Ｂ　Ａ，ｑｌ∈Ｂ，ｆ（ｘｉ，ｑｔ）为对象　在属性ｑｌ下的属性值。ｆ（ｘｋ，ｑ１）为对象　（　≠　）在属性　ｑ（ｘ）＞ｑ（Ｙ）、ｑ（ｘ）＜ｑ（Ｙ）和ｑ（ｘ）＝ｑ（Ｙ）中必有一个成立，其　中，ｑ（　）表示属性ｑ在　处的值。　下文讨论的信息系统Ｓ：（Ｕ，Ａ，Ｖ，ｆ）都是基于优势关系　下的不完备信息系统，简记为Ｓ。　定义２设信息系统Ｓ，Ｂ　Ａ且Ｂ＝Ｂ．ＵＢ２，ＢＩ是上向　属性集（偏好递增有序），Ｂｚ是下向属性集（偏好递减有序）。记：　＝｛（ｙ，　）∈Ｕ￣Ｕ　ｌ（Ｖｑ　∈　，ｆ（Ｙ，ｑ　）≥ｆ（ｘ，ｑ。）　ｏｒ　ｆ（　，｝）ｏｒｆ（ｙ，＊））ａｎｄ（Ｖｑ２∈Ｂ２，ｆ（　，ｑ２）≥　ｆ（ｘ，ｑ２）ｏｒｆ（ｘ，　）ｏｒ，（ｙ，　））｝　则称　为信息系统　的属性子集Ｂ确定的优势关系。　定义≥　为相对于ｑ具有优势。　≥　Ｙ表示相对于属性　ｑ，ｘ至少与Ｙ一样好，即：　ｘ≥　Ｙ甘ｆ（　，ｑ）≥ｆ（Ｙ，ｑ）（依偏好递增有序）　≥。Ｙ甘Ｉ（ｘ，ｑ）≤ｆ（Ｙ，ｑ）（依偏好递减有序）　对于属性子集Ｂ　Ａ，本文定义：ｘ≥　Ｙ铮Ｖｑ∈Ｂ，　ｘ≥　Ｙ，即对于属性子集Ｂ中的所有属性，ｘ至少与Ｙ一样　好。如果（），，ｘ）ｅ　，那么Ｙ在Ｂ上优于　。　定义３＿ｊ　设信息系统Ｓ，ＶｘｅＵ，Ｂ￡Ａ，　在属性集Ｂ　上的优势集可定义为　＝｛），　ｕ　ｌ（）’，　）　）　称【　］　是关于属性集Ｂ比　优的对象集合。　定义４　设信息系统Ｓ，ＶｘｅＵ，Ｂ　Ａ，　对于优势关　系　的上、下近似集及边界域可定义为　磁　（ｘ）＝｛　∈Ｕ　ｌ　Ｘ｝　（Ｘ）＝　∈Ｕｌ　ＮＸ≠　｝　ＢＮＲ；　（ｘ）＝　（ｘ）一　（ｘ）　设信息系统Ｓ，Ｖｘｅ　Ｕ，Ｂ　Ａ，Ｖｑ∈Ｂ，则有以下性　质成立：　（１）优势关系具有自反性和传递性；　（２）　（Ｘ）　Ｘ　（Ｘ）；　（３）　Ｘ］Ａ　；　（４）　（　）　（ｘ），　（Ｘ）　ｎＡ　（ｘ）。　与文献【６】中的定义类似，可以定义在优势关系下集合的　上下边界、粗糙近似精度和粗糙近似质量。　定义５设Ｂ　Ａ，集合Ｘ　Ｕ在优势关系月　下关于属　性集Ｂ的上边界、下边界可定义为：△　（ｘ）＝　（Ｘ）一Ｘ，　垒砧　（Ｘ）＝Ｘ—　（Ｘ）。　定义６设Ｂ　Ａ，集合Ｘ　Ｕ在优势关系　下关于属　性集　的粗糙近似精度可定义为　ｉ　（　）ｆ　其中，ｘ≠　；ｌｘ　Ｊ表示集合ｘ的基数。　定义７设Ｂ∈Ａ，集合Ｘ　Ｕ在优势关系Ｒ　下关于属　性集　的粗糙近似质量可定义为　（ｘ）：—Ｕ－ＢＮｅ广＿￣（＿一Ｘ）［。　面一３４一　下的属性值，且，（ｔ，　）≠，（　，ｑｉ）。ｕ　＝ｘｊ∈ｕｌｓ（ｘ￣，ｇ２）＝　ｆ（ｘｉ，　）｝，令ｆ（ｘｊ，ｑ　）＝ｆ（ｘｔ，ｑ　），　∈Ｕ　，则称属性值　ｆ（ｘｉ，ｑ１）被粗化为ｆ（ｘｋ，　）。　记　为经粗化后的属性ｑ，，　为经粗化后的属性集Ｂ，　为属性　的值域。　定义９设信息系统Ｓ，Ｂ　Ａ，ｇｆ∈Ｂ，ｆ（ｘｉ，　）为对象　在属性ｑｔ下的一个值，Ｕ　＝｛＿　ｕＩＳ（ｘ，，ｑ，）－ｓ（－，，　）｝，若　ｖ芒　，　Ｕ　，令ｆ（ｘｊ，　）＝Ｖ，则称对象　下的属性值　，（ｘｊ，ｑ　）被细化为ｖ。　记　为经细化后的属性ｑ　，　为经细化后的属性集Ｂ，　为属性　的值域。　３属性值粗化细化时近似集的变化情况　３．１单个属性的属性值粗化细化时近似集的变化情况　定理１设信息系统Ｓ，Ｘ　Ｕ，Ｂ　Ａ，ｇ』∈Ｂ，属性ｑｆ的　属性值粗化后，近似集的变化情况为：　，　。　证明：依属性值粗化定义知Ｖ（ｘ，）＇）ｅ磁　，有（　，），）∈　，　所以【　Ｃ【　。　（１）因为Ｖｘｅ　（ｘ），［　］　Ｘ，所以【　】　Ｘ，　ｘＥ　（Ｘ），　。　（２）Ｖｘｅ　（ｘ），［　Ｅ　Ｎｘ≠　，因为【　Ｅ　【　，　所以［　Ｎｘ≠　，　∈　（ｘ），　。　推论１设信息系统ｓ，ｘ　ｕ，Ｂ　Ａ，　∈Ｂ，属性ｑｌ的　属性值粗化后，边界集变化情况为：△舻（Ｘ）　Ａｚ．　（Ｘ），　垒　（Ｘ）ｃ７＿ＡＲ．　；（Ｘ）。　推论２设信息系统Ｓ，Ｘ　Ｕ，Ｂ　Ｃ７．Ａ，ｑｔ∈Ｂ，属性ｑ，的　属性值粗化后，粗糙近似精度和粗糙近似质量的变化情况为：　一≥　；，　；。（Ｘ）≥　・　（Ｘ）。　Ｂ定理２设信息系统Ｓ，Ｘ　Ｕ，Ｂ　Ａ，　∈Ｂ，属性　的　属性值细化后，近似集的变化情况为：　Ｒ：　，　。　证明：依属性值细化定义知Ｖ（Ｘ，ｙ）Ｅ　Ｒ　，有　（　）　，所以　。　（１）因为Ｖｘｅ　（ｘ），【　Ｅ　Ｘ，所以［　】：　Ｘ，　ｘＥ　（Ｘ），　。　（２）Ｖｘｅ　（ｘ），［　Ｎｘ≠　，因为【　【　】　，　所以【　］：　Ｎｘ≠　，　∈　（ｘ），　。　推论３设信息系统Ｓ，Ｘ　Ｕ，Ｂ　Ａ，ｑｔ∈Ｂ，属性　的　属性值细化后，边界集的变化情况为　△　（Ｘ）　ＡＲ　＂　（Ｘ），垒　；（Ｘ）　垒　：　（Ｘ）　推论４设信息系统Ｓ，Ｘ　Ｕ，Ｂ　Ａ，　∈Ｂ，属性ｑｌ的　

属性值细化后，粗糙近似精度和粗糙近似质量的变化情况为　．　Ｒ　（Ｘ）＝｛ｘ５），Ｒ　（Ｘ）＝｛　，　，ｘ４，ｘ５，ｘ６，ｘ７）　ＢＮ∥（ｘ）＝｛ｘ２，ｘ３，ｘ４，　，ｘＴ｝，ＡＲ　（Ｘ）＝｛ｘ３，ｘ６）　≥　，　。　（Ｘ）　（Ｘ）　３．２　多个属性的属性值粗化细化时近似集的变化情况　在现实中，经常会出现多个属性值同时变化的情形。因　此，需要讨论多个属性值粗化细化时近似集的变化。　垒　（ｘ）＝｛　ｚ，ｘ４，　），　一　云，　（ｘ）　号　将对象‘和ｘ　在空气流动指数下的值粗化（不妨设其值　分别为１．７和２．９），则：　定理３设信息系统Ｓ，Ｘ　Ｕ，Ｂ　Ａ，属性集Ｂ的属　性值粗化后，近似集的变化情况为　Ｒ　，　Ｒ　。　声数一噪指一　ｎ　＝２［　＝［　＝［　２＇Ｘ３＇Ｘ４，Ｘ５，　ＸＴ｝，　证明：证明过程与定理１类似，略。　推论５设信息系统Ｓ，ｘ　Ｕ，Ｂ　Ａ，属性集Ｂ的属　【　＝｛　，．　，　），Ｉｘ　】　＝Ｉｘ６］；　＝｛　，ｘ０｝，　性值粗化后，边界集的变化情况为　△　（Ｘ）　ＡＲ；　（Ｘ），垒　（Ｘ）　垒Ｒ：　（ｘ）　推论６设信息系统Ｓ，Ｘ　Ｕ，Ｂ　Ａ，属性集Ｂ的属　性值粗化后，粗糙近似精度和粗糙近似质量的变化情况为　ａＲ；；≥　．　，　：　（Ｘ）≥　。　（Ｘ）　定理４设信息系统Ｓ，Ｘ　Ｕ，Ｂ　Ａ，属性集Ｂ的属　性值细化后，近似集的变化情况为　，％　Ｒ：　。　证明：证明过程与定理２类似，略。　推论７设信息系统ｓ，ｘ　Ｇ　Ｕ，Ｂ　Ａ，属性集Ｂ的属　性值细化后，边界集的变化情况为　ＡＲ；　（Ｘ）　△　（Ｘ），垒　（Ｘ）　垒　：　（Ｘ）　推论８设信息系统Ｓ，ｘ　Ｕ，Ｂ∈ｋ，属性集Ｂ的属　性值细化后，粗糙近似精度和粗糙近似质量的变化情况为　＿¨；≥　，　．；（ｘ）≥　（Ｘ）　定理１～定理４表明，属性值粗化后，下近似集变小，上　近似集变大，从而边界变大；属性值细化后，下近似集变大，　上近似集变小，从而边界变小。推论２、４、６和８表明，属　性值粗化后，基于Ｒ：　的粗糙近似精度和粗糙近似质量低于　基于　的粗糙近似；属性值细化后，基于　的粗糙近似　精度和粗糙近似的质量不低于基于　的粗糙近似。　４实例分析　下面从评价火车是否舒适的几个指标对优势关系下不完　备信息系统进行分析，结果见表１。　表１不完备信息系统　振动　空流　湿度　指数　指数　指数　ｏ　９６　ｌ　５　Ｏ．８９　２　７　３　９　ｏ　９ｌ　ｌ　７　２　８　ｌ　７　３　１　ｏ　８９　３　１　５　２　ｏ　７４　２　９　４　４　ｏ　７９　２　１　４　２　在表１中，对象集Ｕ＝　，ｘ２，ｘ３，ｘ４，　，ｘ６，ｘ７），根据先验　经验，噪声指数和振动指数是下向属性，即噪声指数和振动　指数越大，火车舒适度越低；而空流指数（空气流动指数）和　湿度指数是上向属性，即空气流动指数和湿度指数较大，火　车舒适度较高。　例：令Ｂ＝｛空气流动指数ｌ，Ｘ＝｛ｘ２，ｘ４，ｘ５，ｘ７｝，则：　【　＝｛　，　，ｘ３，ｘ４，ｘ５，ｘ６，ｘＴ｝，【　＝｛ｘ２，ｘ５，ｘ６）　［　］　＝｛ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，　｝，［　］　＝｛ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７｝　【砖】　＝｛鼍），【％］　：｛　，　），ｉｘ，ｉ；　＝｛ｘ２，　，　，ｘＴ｝　【　】　＝｛　，　，ｘ６，　｝，尺：　（Ｘ）＝　，　（　）＝｛　。，ｘ２，ｘ３，ｘ４，　，ｘ６，西），ａＲ；　（Ｘ）：｛＿，　，　），　垒　（Ｘ）＝｛ｘ２，　，　，ｘ７），　ＢＮ　（　）＝｛　・，　，ｘ３，ｘ４，ｘ５，ｘ６，　），　＝０，　；（ｘ）　０　显然有：　（ｘ）　（ｘｊ，　（Ｘ）　（ｘ），△　Ｂ；（Ｘ）　△　（ｘ），垒　（ｘ）　ＡＲ＊　　（ｘ），　≤　，　（ｘ）≤　（ｘ）。　这样的结果也验证了定理１、推论１和推论２。　将对象　在空气流动指数下的值细化（不妨设其值为　１．９），　则：　＝｛ＸｐＸ２，　，Ｘ４，　，Ｘ６，ＸＴ｝，　＝　Ｘ５，Ｘ０｝，　】　＝｛　，　．　，　，．　，　ｒｒ｝，［－】　＝｛　，　，　，　，　），　】　＝｛　｝，［　】　＝｛　，ｘ６｝，［　］　＝｛　，ｘ５，ｘ６，ｘ７｝　（Ｘ）＝｛　ｊ，　＝≥（ｘ）：｛ｘ２，ｘ４，ｘ５，ｘ６，ｘ７｝，　ＢＮ　（ｘ）＝｛ｘＩ　ｘ２，　，ｘ４，ｘ５，ｘ６，　），ＡＲ；　（Ｘ）＝｛　｝，　。（ｘ）＝　，ｘＴ｝一　１，　Ｂ　（　）　号　显然有：尺≥　（ｘ）　（Ｘ），　（ｘ）　（ｘ），　（ｘ）　ＡＲ；　（ｘ），垒　（ｘ）　垒　（Ｘ），ａ＂ｇ：　≥　一，　．Ｂ　　（）≥　；（Ｘ　ｘ）。这样的结果也验证了定理２、推论３和推论４。　类似地，可以验证多个属性值粗化细化的情况也成立。　５结束语　本文给出了优势关系下属性值粗化细化的概念，讨论了　在不完备有序信息系统中属性值粗化细化时近似集的变化情　况。当属性值粗化后，上近似集变大，下近似集变小，从而　边界变大，粗糙近似精度和粗糙近似的质量变低。当属性值　细化后，上近似集变小，下近似集变大，从而边界变小，粗　糙近似精度和粗糙近似的质量变高。本文只讨论了不含决策　属性的不完备有序信息系统，优势关系下的不完备决策信息　系统中近似集的研究将另文介绍。　参考文献　【ｌ】王国胤．Ｒｏｕｇｈ集理论与知识获取［Ｍ］．西安：西安交通大学出版　社，２００１．　［２】张文修，吴伟志．粗糙集理论与方法【Ｍ］．北京：科学出版社，　２００１．　【３］Ｓａｌｖａｔｏｒｅ　Ｇ，Ｂｅｎｅｄｅｔｔｏ　Ｍ．Ｒｏｕｇｈ　Ａｐｐｏｘｉｍａｔｉｏｎ　ｏｆ　ａ　Ｐｒｅｆｅｒｅｎｃｅ　Ｒｅｌａｔｉｏｎ　ｂｙ　Ｄｏｍｉｎａｎｃｅ　Ｒｅｌａｔｉｏｎｓ［Ｊ］．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，１９９９，５３（１）：６３—８３．　［４１　Ｓａｌｖａｔｏｒｅ　Ｇ，Ｂｅｎｅｄｅｔｔｏ　Ｍ，Ｒｏｍａｎ　Ｓ．Ｒｏｕｇｈ　Ａｐｐｒｏｘｉｍａｔｉｏｎ　ｂｙ　Ｄｏｍｉｎａｎｃｅ　Ｒｅｌａｔｉｏｎｓ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｓｙｓｔｅ　，２００２，１７（２）：１５３—１７１　（下转第４２页）　一３５一　

平均附加空间的大小与压缩效果关系不大，这是由于引入的　附加空间相对自动机所占内存空间可以忽略。结果表明，对　参考文献　［１］１　Ｋｕｍａｒ　Ｓ，Ｄｈａｒｍａｐｕｒｉｋａｒ　Ｓ，Ｙｕ　Ｆａｎｇ，ｅｔ　ａ１．Ａｌｇｏｒｉｔｈｍｓ　ｔｏ　Ａｃｃｅｌｅｒａｔｅ　网络应用中实际存在的规则，Ｂｓ．ＦＡ只需引入较小空间的位　Ｍｕｌｔｉｐｌｅ　Ｒｅｇｕｌａｒ　Ｅｘｐｒｅｓｓｉｏｎｓ　Ｍａｔｃｈｉｎｇ　ｆｏｒ　Ｄｅｅｐ　Ｐａｃｋｅｔ　图结构，就能够充分减少正则表达式的空间存储需求。　Ｉｎｓｐｅｃｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　Ａｎｎｕａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｆ　ｔｈｅ　ＡＣＭ　Ｓｐｅｃｉａｌ　表３　Ｂｓ－ＦＡ在ｓｎｏｒｔ规尉集的评估结果　Ｉｎｔｅｒｅｓｔ　Ｇｒｏｕｐ　ｏｎ　Ｄａｔａ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ．Ｐｉｓａ，Ｉｔａｌｙ：【ｓ．ｎ．】，２００６：　３３９—３５０．　［２］Ｋｕｍａｒ　Ｓ，Ｔｕｒｎｅｒ　Ｊ，Ｗｉｌｌｉａｍｓ　Ｊ．Ａｄｖａｎｃｅｄ　Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　Ｆａｓｔ　ａｎｄ　Ｓｃａｌａｂｌｅ　Ｄｅｅｐ　Ｐａｃｋｅｔ　Ｉｎｓｐｅｃｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　ＡＣＭｆｌＥＥＥ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ａｒｃｈｉｔｅｃｔｕｒｅ　ｆｏｒ　Ｎｅｔｗｏｒｋｉｎｇ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｓｙｓｔｅｍｓ．Ｎｅｗ　Ｙｏｒｋ，Ｎ　ＵＳＡ：ＡＣＭ　Ｐｒｅｓｓ，２００６：８１・９２．　［３】Ｂｅｃｃｈｉ　Ｍ，Ｃｒｏｗｌｅｙ　Ｐ．Ａｎ　Ｉｍｐｒｏｖｅｄ　Ａｌｇｏｒｉｔｈｍ　ｔｏ　Ａｃｃｅｌｅｒａｔｅ　Ｒｅｇｕｌａｒ　Ｅｘｐｒｅｓｓｉｏｎ　Ｅｖａｌｕａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　３ｒｄ　ＡＣＭ／ＩＥＥＥ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ａｒｃｈｉｔｅｃｔｕｒｅ　ｆｏｒ　Ｎｅｔｗｏｒｋｉｎｇ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｓｙｓｔｅｍｓ．Ｎｅｗ　Ｙｏｒｋ，Ｎ　ＵＳＡ：ＡＣＭ　Ｐｒｅｓｓ，２００７：１４５—１５４．　【４］Ｙｕ　Ｆａｎｇ，Ｃｈｅｎ　Ｚｈｉｆｅｎｇ，Ｄｉａｏ　Ｙａｎｌｅｉ，ｅｔ　ａ１．Ｆａｓｔ　ａｎｄ　Ｍｅｍｏｒｙ—　ｅｆｉｆｃｉｅｎｔ　Ｒｅｇｕｌｒａ　Ｅｘｐｒｅｓｓｉｏｎ　Ｍａｔｃｈｉｎｇ　ｆｏｒ　Ｄｅｅｐ　Ｐａｃｋｅｔ　ｌｎｓｐｅｃｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　ＡＣＭ／ＩＥＥＥ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ａｒｃｈｉｔｅｃｔｕｒｅ　６结束语　ｆｏｒ　Ｎｅｔｗｏｒｋｉｎｇ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｓｙｓｔｅｍｓ．Ｎｅｗ　Ｙｏｒｋ，Ｎ　ＵＳＡ　本文通过对ＰＣＲＥ规则语法引起的状态爆炸情况进行研　ＡＣＭ　Ｐｒｅｓｓ，２００６：９３—１０２．　究，给出了一类尚无法有效处理的模式。针对该模式将条件　［５】Ｂｅｃｃｈｉ　Ｍ，Ｃｒｏｗｌｅｙ　Ｐ　Ａ　Ｈｙｂｒｉｄ　Ｆｉｎｉｔｅ　Ａｕｔｏｍａｔｏｎ　ｆｏｒ　Ｐｒａｃｔｉｃａｌ　Ｄｅｅｐ　函数和位图结构引入传统自动机，提出了一种位图移位有限　Ｐａｃｋｅｔ　Ｉｎｓｐｅｃｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　自动机Ｂｓ—ＦＡ。该自动机同时可以处理满足重写规则１和重　Ｅｍｅｒｇｉｎｇ　Ｎｅｔｗｏｒｋｉｎｇ　Ｅｘｐｅｒｉｍｅｎｔｓ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｉｅｓ．Ｎｅｗ　Ｙｏｒｋ，　写规则２中的模式。通过对实际的规则集进行评估，与其他　Ｎ　ＵＳＡ：ＡＣＭ　Ｐｒｅｓｓ．２００７：７７０—７７３．　方法相比，该自动机可以大量节省内存空间。　编辑顾逸斐　（上接第３５页）　【８］Ｃｈａｎ　Ｃｈｉｅｎｃｈｕｎｇ．Ａ　Ｒｏｕｇｈ　Ｓｅｔ　Ａｐｐｒｏａｃｈ　ｔｏ　Ａｔｔｉｒｂｕｔｅ　Ｇｅｎｅｒａｌｉ—　［５】Ｙａｎｇ　Ｘｉｂｅｉ，Ｙａｎｇ　Ｊｉｎｇｙｕ，Ｗｕ　Ｃｈｅｎ，ｅｔ　ａ１．Ｄｏｍｉｎａｎｃｅ—ｂａｓｅｄ　Ｒｏｕｇｈ　ｚａｔｉｏｎ　ｉｎ　Ｄａｔａ　Ｍｉｎｉｎｇ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ，１９９８，１０７（１－４）：　Ｓｅｔ　Ａｐｐｒｏａｃｈ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ　Ｒｅｄｕｃｔｉｏｎｓ　ｉｎ　Ｉｎｃｏｍｐｌｅｔｅ　Ｏｒｄｅｒｅｄ　１　７７—１９４．　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ，２００８，１７４（４）：１２１９—　［９］Ｌｉ　Ｔｉａｎｒｕｉ，Ｙａｎｇ　Ｎｉｎｇ，Ｘｕ　Ｙａｎｇ，ｅｔ　ａ１．Ａｎ　Ｉｎｃｒｅｍｅｎｔａｌ　Ａｌｇｏｒｉｔｈｍ　１２３４．　ｏｆｒ　Ｍｉｎｉｎｇ　Ｃｌａｓｓｉｉｆｃａｔｉｏｎ　Ｒｕｌｅｓ　ｉｎ　Ｉｎｃｏｍｐｌｅｔｅ　Ｉｎｆｏｒｍａｔｉｏｎ　【６］胡明礼，刘思峰．基于有限扩展优势关系的粗糙决策分析方　Ｓｙｓｔｅｍ［Ｃ］／／Ｐｒｏｃ．ｏｆ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｆ　ｔｈｅ　Ｎｏｒｔｈ　法［Ｊ］．系统工程，２００６，２４（４）：１０６一ｌ１０．　Ａｍｅｒｉｃａｎ　Ｆｕｚｚｙ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　Ｓｏｃｉｅｔｙ．Ｃｈｉｃａｇｏ，ＵＳＡ：　【７】徐伟华，张文修．基于优势关系下信息系统分配约简的矩阵算　［ｓ．ｎ．】，２００４：４４６—４４９．　法【Ｊ］＿计算机工程，２００７，３３（１４）：４－７．　编辑张正兴　（上接第３８页）　５结束语　［３］Ｌｉｕ　Ｂｉｎｇ，Ｚｈａｏ　Ｋａｉｄｉ，Ｂｅｎｋｌｅｒ　Ｊ，ｅｔ　ａ１．Ｒｕｌｅ　Ｉｎｔｅｒｅｓｔｉｎｇｎｅｓｓ　Ａｎａｌｙｓｉｓ　仿真结果分析如下：在相同的数据集、最小支持度门限　Ｕｓｉｎｇ　ＯＬＡＰ　Ｏｐｅｒａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　１２出Ｉｎｔｅｒｎａｔｉｏｎａｌ　和最小置信度门限条件下，无冗余关联规则数量和产生时间　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｎｅｗ　Ｙｏｒｋ，　均分别远远小于冗余关联规则数量和产生时间，尤其是低支　Ｎ　ＵＳＡ：ＡＣＭ　Ｐｒｅｓｓ．２００６：２９７—３０６．　持度门限时，差距更加明显。导致这种差异的本质原因是　［４】Ｊｉａｎ　Ｐｅｉ，Ｈａｎ　Ｊｉａｗｅｉ，Ｍａｏ　Ｒｕｎｙｉｎｇ．ＣＬＯＳＥＴ：Ａｎ　Ｅｆｉｆｃｉｅｎｔ　Ａｐｒｉｏｒｉ算法采用穷举方法发现全部规则，而本文算法通过相　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｍｉｎｉｎｇ　Ｆｒｅｑｕｅｎｔ　Ｃｌｏｓｅｄ　Ｉｔｅｍｓｅｔ［ｃｌ／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　集分解产生最小生成项集的方法能够大大减少搜索空间，并　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ．　且根据关联规则之间的相关性对规则进行了精简。　Ｎｅｗ　Ｙｏｒｋ，Ｎ　ＵＳＡ：ＡＣＭ　Ｐｒｅｓｓ，２０００：１　１－２０．　参考文献　［５】Ｚａｋｉ　Ｊ．Ｍｉｎｉｎｇ　Ｎｏｎ－ｒｅｄｕｎｄａｎｔ　Ａｓｓｏｃｉａｔｉｏｎ　ＲｕｌｅｓｃＪ】．Ｄａｔａ　Ｍｉｎｍｇ　【１】Ｇｅｎｇ　Ｌｉｑｉａｎｇ，Ｈａｍｉｔｏｎ　Ｊ．Ｉｎｔｅｒｅｓｔｉｎｇｎｅｓｓ　Ｍｅａｓｕｒｅｓ　ｏｆｒ　Ｄａｔａ　Ｍｉｎｉｎｇ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ，２００４，９（１）：２２３－２４８．　ＡＳｕｒｖｅｙ［Ｊ］．ＡＣＭＣｏｍｐｕｔｉｎｇ　Ｓｕｒｖｅｙｓ，２００６，３８（３）：１１４５—１１７７．　［６］Ｂａｓｔｉｄｅ　Ｐａｓｑｕｉｅｒ　Ｎ，Ｔａｏｕｉｌ　Ｒ，ｅｔ　ａ１．Ｍｉｎｉｎｇ　Ｍｉｎｉｍａｌ　［２】Ｂａｙａｒｄｏ　Ｒ，Ａｇｒａｗａｌ　Ｒ，Ｇｕｎｏｐｕｌｏｓ　Ｄ．Ｃｏｎｓｔｒａｉｎｔ—ｂａｓｅｄ　Ｒｕｌｅ　Ｍｉｎｉｎｇ　Ｎｏｎ—ｒｅｄｕｎｄａｎｔ　Ａｓｓｏｃｉａｔｉｏｎ　Ｒｕｌｅｓ　Ｕｓｉｎｇ　Ｆｒｅｑｕｅｎｔ　Ｃｌｏｓｅｄ　ｉｎ　Ｌａｒｇｅ，Ｄｅｎｓｅ　Ｄａｔａｂａｓｅｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　１　５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｉｔｅｍｓｅｔｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　１ｓｔ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ　Ｄ．Ｃ．，ＵＳＡ：ＩＥＥＥ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｌｏｇｉｃ．Ｌｏｎｄｏｎ，ＵＫ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２０００：９７２—９８６．　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ，１９９９：１６７－１７７．　编辑顾逸斐　—＿４２一