基于柔性逻辑的区分矩阵属性约简算法①

侯慧欣, 刘城霞

(北京信息科技大学 计算机学院,北京 100101)

粗糙集理论最早由波兰数学家华沙理工大学教授Z.Pawlak于1982年提出,是一种处理不精确、不一致、不完整等数据的数学工具,同时对处理非常复杂的系统非常有效. 属性约简是粗糙集理论研究的核心内容之一,其中基于区分矩阵的方法是现有的一种具有代表性的属性约简算法,很多属性约简及其拓展的工作都以此为基础[1-4]. 目前,对现有算法的改进大多是提高算法的效率,如文献[5-8],或扩大其应用范围如文献[9-11],而此次实现的改进则是针对数据而言. 由于现有的算法都只用于处理离散数据,对于连续数据需要先进行离散化处理. 而本次实现的改进则取缔了离散化这一步骤,可以对离散数据和连续数据统一进行处理.

泛逻辑是本世纪初由何华灿教授提出. 它基于二值逻辑,多值逻辑和模糊逻辑,并可以有效地处理人工智能中不精确、不完整和连续的数据,不完备和模糊数据. 它可以被认为是一种柔性逻辑. 粗糙集理论和泛逻辑都可以用来处理不精确和不确定问题,因此结合两个理论来取得更好的效果是可行和方便的[12].

1 基本概念

1.1 粗糙集

定义1[13]. 一个信息表可以描述为,其中U是论域,：C是条件属性集,d是决策属性.是属性的值域,其中,Va是属性a的值域.是信息决策函数. 当时,该信息表是一个决策信息表.

1.2 属性约简

在粗糙集信息系统中,设R是一个等价关系簇,,如果,则称I在等价关系簇R中是不必要的. 否则称I在等价关系簇R中是必要的. 若R中的每一个等价关系I都是必要的,则称R是独立的. 属性约简就是在知识库分类能力保持不变的情况下,删除冗余属性.

(1)D是独立的,

则称D是B的一个约简. 记为：. 其中所有的必要关系组成的集合,称为B的核,记为：.即. 核是信息系统中的核心属性集,是所有约简的公共部分.

1.3 区分矩阵

定义5[5]. 设为一个决策表,其中C为条件属性集,D为决策属性集,决策表S的区分矩阵被定义为,其中

2 算法原理

(1) 首先根据信息表S构造区分矩阵M,按照公式(1)规则构造矩阵.

构造区分矩阵时,需要将信息表中所有数据一一进行对比,在此以第条数据举例说明具体构造过程：首先判断第条数据决策属性值是否相同,若相同,即则将值记为空; 若决策属性值不同,即,此时从第一个条件属性开始比较这两条数据的所有条件属性,若两条数据的条件属性ak相等,则不作处理; 若两条数据的条件属性ak不相等,则将ak属性添加到值中. 由于每两条数据只需要单向比较一次即可,所以结合矩阵的特点,我们可以知道最后得到的区分矩阵是一个主对角线上元素为空的上三角矩阵或下三角矩阵.

(2) 根据区分矩阵构造区分函数,规则如下：

(3) 删除包含关系： 将所有析取表达式合取得到的合取范式通常都很复杂,甚至含有大量重复内容. 在这种情况下若是直接将合取范式转化为析取范式需要花费大量的时间和空间,且十分不必要. 根据离散定律中幂等律和吸收律特点,我们可以简化合取范式的内容,有效地减少后续工作的工作量. 幂等律：,吸收律：拓展为包含关系可以将相等或较大的一项析取范式删掉,且对最后结果没有影响. 证明过程参见定理1的证明. 所以,我们可以在求出区分矩阵之后先将包含关系删除,再对简化后的区分矩阵进行后续操作. 这一方法可以有效降低系统开销,缩短程序运行时间,提高算法运行效率.

将合取范式转化为析取范式,即将L转化为析取范式L',. 通过离散定律分配律可以将合取范式转化为析取范式,最终得到结果一个或多个约简集以及所有约简集的交集——核.

3 算法改进

3.1 改进原理

由于原始的算法只能用于处理离散的数据,然而现实生活中我们收集的数据大部分都是既包含连续数据又包含离散数据. 因此对于这些数据,我们需要先进行离散化处理再进行属性约简. 然而在使用等区间离散化方法时经常会出现以下问题： 两个边界值的数值非常接近,但它们离散化后属于不同区域,因此它们会被置于不同的等价集中. 这显然是不合理的,这是人为的离散化带来的错误. 但是如果使用柔性逻辑等价关系就可以避免这种错误. 因为等区间离散化方法是将该属性划分为一定的区间数,每个区间距离相同,将位于同一区间的数据离散化为同一结果. 因此这种离散化方法对于边界值的处理会产生错误,比如说位于不同区间但数值十分相近的两个数值,很明显这两个数值应当离散化为相同的结果,但是对于等区间离散化方法而言,对于这一类数据的处理就会发生错误. 而使用柔性逻辑等价关系时,使用的是中心等价公式：此时判断x和y离散化结果是否相同时,判断条件不是这两个数值是否位于同一区间,而是这两个数值的差距是否超过固定的区间距离. 这样就可以避免边界值由于等区间离散化方法而产生的错误. 本文只讨论了最简单的离散化方法(等区间离散),如果连续属性具有不同的特征,并且使用不同的离散化方法来使数据离散,我们也可以调整参数,使用不同的等价公式来处理这些连续数据. 如果零级泛逻辑不足以覆盖使用,我们也可以引入自相关参数k以获得更大的柔性.

改进算法利用了柔性逻辑中的中心等价公式. 在柔性逻辑理论中,定义了一组连续而灵活的运算符集,以表示广义相关性和广义自相关性[14]. 在本文中,我们只考虑广义相关性[15],而广义相关性可以被量化为广义相关系数,一般用h表示,h在[0,1]中连续取值.

使用T范数来表示AND关系,S范数来表示OR关系,这是泛逻辑的数学基础. 广义相关性被定义为h和两个仅由h控制的两个函数,T生成元完整簇和S生成元完整簇.把它们应用到AND运算模型和OR运算模型,我们可以得到和：

将T生成元完整簇放入蕴含运算模型中,我们可以得到：

将T生成元完整簇放入等价运算模型

(1) Zadeh等价：

(2) 概率等价：

(3) 中心等价：

(4) 最大等价：

使用柔性逻辑中的中心等价公式：

由于x,y的取值区间只能为[0,1],所以将公式转化为：

与改进前的算法相比较,改进后算法只是将构造区分矩阵的条件由公式(1)改为公式(10).公式(10)主要描述了构造区分矩阵的规则,规则如下： 首先判断Xi和Xi的决策属性值是否相同,若相同则将该矩阵的i行j列置空,若其决策属性值不同,则依次计算的结果,将该结果与参数进行比较,若该结果小于等于,则将该属性加入到该项中,若大于,则不将该属性加入该项. 公式(1)与公式(10)的区别在于： 在判断条件属性是否加入该项时,公式(1)是对离散化后的结果直接进行判断,等于或不等关系. 而公式(10)则直接将离散数据或连续数据根据中心等价公式进行计算,再将计算结果与值进行比较. 其实这两种判断条件直接体现出了不可分辨关系和柔性逻辑等价关系的区别.

3.2 实例说明

在实现区分矩阵属性约简算法时,通常需要先将原始数据离散化,再对离散数值进行属性约简. 现在提出一种利用柔性逻辑等价关系替代原本的不可分辨关系,省略离散化这一过程. 这一改进使用公式(8),只针对等区间离散化这一方法进行改进.

为了完整的研究算法,现引入一个覆盖算法涉及到的全部步骤的气象表,如表1. 表中数据后的小括号内容表示对应的离散化后的结果.

表1 气象表

表中存在2个连续属性,分别为a2和a3. 将a2划分为 3个区间,分别为： [6,19),[19,28),[28,39],对应离散值为3,2,1. 将a3划分为2个区间,分别为：[28,55),[55,82),对应离散值为2,1.

传统的区分矩阵属性约简算法大致分为3步：

1) 首先根据信息系统S构造区分矩阵M(S);

2) 根据区分矩阵构造区分函数;

3) 计算区分函数,将合取范式转化为析取范式.

改进的算法对代码改动较小,只需在构造区分矩阵时将原来的不可分辨关系判断条件改为柔性逻辑等价关系的判断条件即可.

表2 改进前区分矩阵

表3 改进后区分矩阵

改进前后构造的区分矩阵结果略有不同. 分析这些不同,主要有以下两种情况：

1) 改进后的矩阵某一项增加了某一属性： 如X6,9改进前的内容为a1a4,改进后为a1a3a4. 针对a3属性进行分析,湿度52%和28.5%离散化后均为2.所以改进前区分矩阵该项的内容中并不包括a3属性. 但是52%和28.5%均属于边界值,虽然同属一个区间,但实际差距还是很大的. 因此改进后的算法更合理.

2) 改进后的矩阵某一项删除了某一属性. 如X1,4改进前的内容为a1a2,改进后为a1. 针对a2属性进行分析,温度32和25离散化后分别为1和2.所以改进前区分矩阵该项的内容中包括a3属性. 但是32和25均属于边界值,虽然属于不同区间,但实际差距不大的.因此改进后的算法更合理.

对改进前后的算法效率进行比较,发现： 改进后的算法效率与改进前的算法效率几乎持平,甚至在数据量逐渐增多的情况下,改进后的算法效率要低于改进前的算法效率. 而且,改进后的算法效率在构建区分矩阵部分所消耗的时间远大于改进前的算法. 由于机器限制,只比较了具有5个属性的数据表在100～900,1000～7000条数据等不同情况下的运行时间. 实验结果如表4和表5.

表4 千条以内数据算法效率对比

表5 千条以上数据算法效率对比

测试硬件环境： 联想PC,1.90 GHZ,内存2.0 GB,测试软件环境： Microsoft Windows7 旗舰版,编程语言：Java,开发环境： MyEclipse Professional 2014.

4 结论与展望

本文实现了基于区分矩阵的属性约简基础算法,并实现了利用柔性逻辑对该算法的改进,将改进前后的算法进行了内容和效率两方面的对比并得出结论.但是本文使用的柔性逻辑等价关系只针对等区间离散化方法,对于其他的离散化方法并不适用,因此今后的研究方向是利用柔性了逻辑对其他的离散化方法进行改进,将柔性逻辑和粗糙集理论做一个更好的统一.

1张文修,吴伟志,梁吉业,等. 粗糙集理论与方法. 北京： 科学出版社,2001.

2王丹,吴孟达,刘银山. 属性约简的一种简单算法. 模糊系统与数学,2004,18(S)： 254-257.

3陶志,许宝栋,汪定伟. 一种基于分明矩阵的启发式知识约简方法. 系统工程与电子技术,2005,27(4)： 734-736.

4孙士保,秦克云. 基于包含度的决策表属性约简算法的研究. 计算机工程与应用,2006,(3)： 19-21.

5高锦标. 一种改进的区分矩阵属性约简算法及应用. 电脑知识与技术,2009,5(8)： 1876-1877.

6史君华,胡学钢. 一种基于粗集的决策表属性值约简改进算法. 合肥工业大学学报(自然科学版),2008,31(1)： 36-39.

7叶东毅. Jelonek属性约简算法的一个改进. 电子学报,2000,28(12)： 81-82. [doi： 10.3321/j.issn：0372-2112.2000.12.023]

8刘文军,谷云东,冯艳宾,等. 基于可辨识矩阵和逻辑运算的属性约简算法的改进. 模式识别与人工智能,2004,17(1)： 119-123.

9陶志,刘庆拯,李卫民. 一种基于改进区分矩阵的属性约简算法. 2007中国控制与决策学术年会论文集. 无锡,中国.2007. 83-85.

10葛浩,李龙澍,杨传健. 新的可分辨矩阵及其约简方法. 控制与决策,2010,25(12)： 1891-1895,1900.

11Liu CX,He HC,Zhu ML. The study of new indiscernible relation based on flexible logic in complete information system. 2015 8th International Symposium on Computational Intelligence and Design. Hangzhou,China. 2015. 222-227.

12Pawlak Z. Rough sets. International Journal of Computer &Information Sciences,1982,11(5)： 341-356.

13薛占熬. 柔性区间逻辑及推理研究[博士学位论文]. 西安：西北工业大学,2006. 1-19.

14刘城霞,何华灿. 广义相关性基础上的量化容差关系的改进. 北京邮电大学学报,2015,38(5)： 28-32,41.

15胡彧,李智玲,李春伟. 一种基于区分矩阵的属性约简算法. 计算机应用,2006,26(S)： 80-82.

16蔡卫东,李凡,徐章艳,等. 基于修正差别矩阵的高效属性约简算法. 华中科技大学学报(自然科学版),2007,35(9)：110-113.