区间值决策系统下的最小属性约简

在给定的属性约简目标函数下，决策表中往往存在多个约简。最后的决策规则集直接依赖于所获得的约简。决策规则集的简洁性、可理解性、通用性和精确性因约简的不同而不同，因此期望得到一些最优结果，即长度最短的最小约简。这样可以尽可能多地去除冗余属性，有效地管理决策表的存储空间，并且决策规则集的性能将变得优异。不幸的是，寻找最小约简已被证明是一个NP-难问题(Wong和Ziarko 1985)。当给定决策表时，启发式算法并不总是能得到最小约简。因此本文在区间值决策系统下提出了基于差别矩阵的0-1规划最短约简算法。

波兰数学家Pawlak 于1982 年提出的粗糙集理论[1]，它是一种新型的处理模糊和不确定知识的数学工具，其主要思想就是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。属性约简[2] [3] [4] [5]是粗糙集理论中的核心内容之一，数据库中的属性并不是同等重要的，甚至其中某些知识是冗余的，通过属性约简，可以去除数据库中的冗余、无用的成分，揭示数据中隐含的规律。从粗糙集理论的角度来理解，在一个信息系统中，有些属性对于分类来说是多余的，去掉这些属性后，信息系统的分类能力不会改变，所以属性约简后仍然反映了一个信息系统的本质信息[6] [7] [8] [9] [10]。一般来讲，一个信息系统的属性约简不是唯一的，通常人们希望能够找到一个属性个数最小的属性约简，该属性约简称为最小属性约简。

对任一给定区间值决策系统，若属性约简算法能确保找到其最小属性约简，则该算法称为最小属性约简的完备算法。现有的最短约简工作大多是基于二进制差别矩阵[11] [12] [13]的方法， 这种方法大多又只适用于经典的粗糙集系统模型。

本文在经典的区间值决策系统数据背景下， 提出了基于差别矩阵的0-1规划最短约简算法并与经典的基于差别矩阵的属性约简算法作比较。

2. 基本概念 2.1. 区间值决策系统 定义1 给定区间值系统IVDS 是一个四元组：(), , , IVDSU ATCD V f==，其中U 是一个非空有限集合称为论域，AT 表C 表示条件属性的集合，D 表示决策属性的集合， aV 表示的是属性a 的值域，f是一个映射函数，其中:f UATV×→， (), f x a 表示对象xU∈在属性aC∈上的取值，简记为( )a x ， (), f x d 表示对象x 在属性dD∈上的取值，简记为( )d x 。

定义2 [14] 设, mmiiiluξ= 和, mmjjjluξ= 为任意两个区间值， 分别表示的是对象ix 和jx 在属性ma 下的属性值，则区间值的相关运算如下： () ()()(), max, ,min, , otherwisemmmmijjiijmmmmijijulullluuξξ∅<∨<=  (1) ()()min, ,max, ξξ= mmmmijijijlluu (2)