改进的差别矩阵属性约简方法

董春游, 黄春楠

(1.黑龙江科技学院 研究生学院;2.黑龙江科技学院 信息网络中心,哈尔滨 150027)

改进的差别矩阵属性约简方法

董春游1, 黄春楠2

(1.黑龙江科技学院 研究生学院;2.黑龙江科技学院 信息网络中心,哈尔滨 150027)

针对目前属性约简方法计算量过大、复杂度高的问题,在已有差别矩阵定义和求核方法的基础上,根据二元决策表所特有的性质,提出一种新的差别矩阵的定义,将一个大的差别矩阵分化成两个小矩阵。与建立一个差别矩阵的方法相比,改进的差别矩阵方法减少了矩阵中元素的比较次数。数据分析表明,该方法在改进差别矩阵定义的同时简化了计算过程,提高了运算效率。

决策表;核;属性约简;差别矩阵;差别函数

0 引 言

随着信息化时代的发展,人们在各个领域获取的信息急剧膨胀,这些数据的不确定性也更加显著。如何从这些模糊的、不精确的、不完整的大量信息中获取有价值的知识已经对智能信息处理提出了严峻的挑战。粗糙集理论应运而生,它不仅能够处理复杂系统中的数据和信息,也可以处理模糊的和不精确的信息[1]。在粗糙集理论中,属性约简是知识获取的关键步骤,也是粗糙集理论和应用研究的焦点问题之一[2]。

目前,已经有很多属性约简的方法[3-4]。其中, Hu提出的基于差别矩阵的求核方法是经典的属性约简方法之一。该方法减少了计算量,提高了求解核的效率。但在某些情况下不能正确得到核。于是有学者在此基础上提出了新的差别矩阵[5-7],但计算量过大。文献[1]提出的基于分体策略和差别矩阵的决策表属性约简方法在纠正了 Hu方法错误的同时,有效的降低了计算复杂度。对于实际需求中比较大的决策表,这个方法还可以进一步的改进,因此,笔者针对该问题进行了研究。

1 粗糙集的基本理论

2 改进的差别矩阵

波兰科学家 A.Skowron于 1991年首次提出利用差别矩阵来表示知识。实践证明这种方法在知识表达系统中求核和约简以及在其它概念的表示和计算等方面有很多优点,但是该方法在某些时候会产生错误的结果。在文献[1]中分析了 Skowron差别矩阵对不相容决策表求相对核及约简时可能会产生错误结果的原因。Skowron差别矩阵没有考虑到当决策表的不相容度大于某一确定阈值后,可能会造成无法正确分类,因此需要忽略不相容对象组之间的差异。而不相容的样本集本身对决策表的分类能力会产生一定的影响,若忽略其影响,则会使约简后的决策表无法完整地表达原始决策表的分类能力,因此在进行属性约简时有必要充分考虑不相容样本集对决策表的分类能力。笔者正是基于以上原则提出了一种改进的差别矩阵的方法。该方法的总体思想是首先应用分体策略将不相容决策表中的对象分为两部分:相容对象和不相容对象。然后根据不同的对象采取不同的比较方式分情况进行讨论,最后求得决策表的属性约简。

2.1 差别矩阵定义

如上所述,基于分体策略的属性约简方法可以在尽可能的保持原始决策表分类能力不变的前提下对决策表进行属性约简,因此很多学者在约简决策表时均是基于这一思想,只是不同的学者有各自不同的方法[5-7]。例如:文献 [1]中建立的基于分体策略的差别矩阵充分考虑了不相容样本集对决策表分类能力的影响,而且在一定程度上也提高了运算效率,但若遇到不相容对象较少而绝大多数是相容对象的情况、或是决策表比较大,对象非常多等情况,这种方法在运算效率上就会受到影响。而文献[8]中提出的方法在给出差别矩阵的定义时仅考虑了相容对象之间的比较和相容对象与不相容对象之间的比较,忽略了相容与不相容对象之间当决策属性相等时两个对象的比较,虽然约简后的结果是一样的,却增加了矩阵规模。因此笔者在文献[1]的基于分体策略的差别矩阵定义基础上,结合二元矩阵所特有的性质,提出了一种新的改进的基于分体策略的差别矩阵定义。

定义 5 改进的基于分体策略的差别矩阵

由基于分体策略的差别矩阵定义[1]可以发现:当两个样本都属于不相容决策表时,或两个样本都在相容决策表中,而且其决策属性相同时,这两个样本比较的结果都是∅。因此,定义 5建立的差别矩阵忽略了以上比较,简化了矩阵的规模。

2.2 差别矩阵的属性约简

根据定义 5建立差别矩阵时,首先将决策表中的对象按其相容性分为两部分:完全相容子表U1和完全不相容子表U2,然后针对两个子表分别建立差别矩阵。

第一个差别矩阵的构造方法为:将U1中的对象作为差别矩阵的行,再将U2中的对象作为差别矩阵的列,根据式(1)依次计算出差别矩阵中的元素。需要注意的是:建立矩阵时比较的是两个对象的条件属性,因此每一组不相容对象组中只保留一个对象即可,忽略其余对象不会影响差别矩阵的完整性。

第二个差别矩阵比较U1中的对象。根据定义5按决策属性的不同将U1中的对象分为两类U11和U12,U11为差别矩阵的行,U12为差别矩阵的列,构造矩阵。再根据式(2)计算出第二个矩阵的元素。

根据定理 1和差别函数的性质 2可知,两个差别矩阵中所有单个属性元素组成的集合就是决策表的相对核。根据定理 2和差别矩阵的性质 1及 3可知,差别矩阵所对应的合取范式经过逻辑运算转化后得到的极小析取范式中的每个Lk都是该决策表的一个属性约简。但在求核后会发现如果合取表达式比较复杂,计算过程会非常繁琐,因此可以利用合取析取逻辑运算特点对方法做进一步改进,进而求出决策表的属性约简。具体步骤为:

(1)根据定理 1和差别函数的性质 2得到决策表的相对核。

(2)将差别矩阵中包含相对核属性的元素的值修改为0。

(3)根据定理 2将矩阵中剩余元素的合取表达式转化为析取范式,最终得到决策表的属性约简。

3 实例分析

以某矿区突出点瓦斯参数统计表中的一组检验瓦斯突出的数据(表 1)为例。对表 1中具有连续型的属性值离散化,再对其应用文中提出的改进的差别矩阵属性约简方法进行属性约简。为了凸显属性约简的过程和效果,只取原表中的部分数据进行处理。其中,共有 10个对象和 5个属性,C={a,b,c, d}为条件属性,e为决策属性。a为标高,m;b为突出强度,t;c为瓦斯量,m3/t;d为瓦斯压力,MPa。e值为 1时表示突出,0表示压出。对表 1进行离散化处理后得到表2。

表1 某煤矿瓦斯突出参数决策表Table 1 Decision table of coa lm ine outburst parameters

表2 离散化后的决策表Table 2 D iscretized decision table

根据文献[1]建立的差别矩阵为

根据定理 1和性质 2可得决策表的相对核为K(C)={b,c}。计算相对约简前,先将两个差别矩阵中所有包含相对核属性元素的值都改为“0”。最后这两个矩阵只包含两个取值为非“0”的元素,而且都是{a,d},将非“0”元素转化为逻辑公式并最终化简得:L′∨(Λ)=a∨d,将核属性加入到各合取项中得到的结果为:(a∧b∧c)∨(b∧c∧d)。

从实例中可以发现:文献[1]和[8]的方法所得到的核和约简与文中得到的结论相同,这也验证了三种方法都可以得到正确的结果。但对比三个差别矩阵,可以发现文献[1]共做了 21次比较,文献[8]做了 36次比较,而根据文中建立的差别矩阵仅做了16次比较。这是因为根据文献[1]建立的矩阵将所有可比较的样本都一一进行了比较,根据文献[8]提出的矩阵进行比较时将相容样本集中的每个样本都和不相容样本集中的每个样本进行了一次比较。而文中提出的矩阵则忽略了决策属性相同的相容样本之间的比较,这样就减少了矩阵中∅的数量。文中给出的实例仅有 10个样本,就减少了 5次比较次数,而现实数据的样本可能多达几千个,若依照文中提出的方法会大量减少比较次数。因此,文中的方法更能提高运算效率。

4 结束语

在粗糙集理论中,求核及相对约简的计算都是非常关键的步骤[9-10]。基于前人的研究,文中对核属性本质及约简过程进行分析,提出了新的差别矩阵的定义和属性约简的方法,建立了一种更简洁的差别矩阵,有效的降低了计算代价。

[1] 苗夺谦,李道国.粗糙集理论、方法与应用[M].北京:清华大学出版社,2008.

[2] 杨 明,孙志辉.改进的差别矩阵及其求核方法[J].复旦学报:自然版,2004,43(5):865-868.

[3] 夏克文,沈钧毅,李昌彪.样本信息处理中一种属性约简方法的研究[J].西安交通大学学报,2005,39(6):558-561.

[4] 王宗军,李红侠,邓晓岚.粗糙集理论研究的最新进展及发展趋势[J].武汉理工大学学报:信息与管理工程版,2006, 28(1):43-48,52.

[5] 梁吉业,李德玉.信息系统中的不确定性与知识获取[M].北京:科学出版社,2005.

[6] 周江卫,冯博琴,刘 洋.粗糙集高效遗传约简算法[J].西安交通大学学报,2007,41(4):444-447.

[7] 王 刚.基于粗糙集的数据约简算法研究与应用[D].合肥:合肥工业大学,2007.

[8] 张振琳,黄 明.改进的差别矩阵及其求核方法[J].大连交通大学学报,2008,29(4):79-82.

[9] 张文修,梁 怡,吴伟志.信息系统与知识发现[M].北京:科学出版社,2003.

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

[11] 刘志民.基于最大外权重的一种启发式属性约简算法[J].河北工程大学学报:自然科学版,2008,25(3):110-112.

Improved method of discernibility matrix and attributes reduction

DONG Chunyou1,HUANG Chunnan2
(1.Graduate School,Heilongjiang Institute of Science and Technology; 2.Information Network Center,Heilongjiang Institute of Science and Technology,Harbin 150027,China)

W ith a view to eliminating too much calculation and greater complexity due to current method of attribute reduction,this paper proposes a new definition of discernibilitymatrix,based on discernibilitymatrix and the method of computing core,and according to the special quality of binary decision table.The improved method of forming discernibilitymatrix involves changing a complexmatrix into two simple ones and gives fewer times of elements comparison than only one matrix.The analysis of the given data shows that the method improves the definition of discernibility matrix with accompanying simplification of the algorithm and enhancement of calculation efficiency.

decision table;core;attributes reduction;discernibilitymatrix;discernibility function

TP301.6

A

1671-0118(2010)02-0155-04

2010-02-14

董春游(1962-),男,吉林省长春人,教授,博士,研究方向:人工智能与决策支持系统,E-mail:chunyou_dong@163.com。

(编辑王 冬)