序决策系统下近似约简的启发式算法

随着网络的进步，社会中产生了大量的高维数据，但很多统计方法难以直接应用到高维数据上。如何获得去噪简化且保存关键信息的低维度数据是一项急需解决的问题。粗糙集理论提供了一种数据降维的方法，被称为属性约简。属性约简的目标是保证原数据集的一种分类特征不变，获得其最小的属性子集。目前，基于不同的分类特征，已提出了许多不同的属性约简算法，如下近似保持、分布保持等。在序决策系统中，传统的下近似约简算法是基于差别矩阵的，计算复杂度高。为了解决这一问题，本文使用依赖度，设计了一个后向贪婪的启发式算法来计算下近似约简。实验使用6组UCI数据集。实验结果表明本文设计的算法可以得到正确的下近似约简，并在时间效率上优于传统的差别矩阵算法。

粗糙集理论[1]是Pawlak 提出的处理模糊数据分类的有效方法，已被使用在数据挖掘[2] [3]、数据分析[4]和机器学习[5]等领域。属性约简[6] [7] [8]是粗糙集理论中的一种数据降维方法。属性约简可以保证原数据集的一种分类特征不变，然后获得最小的特征子集。Pawlak 粗糙集使用等价关系来划分样本，但在现实生活中，样本往往需要使用序关系来进行描述，例如学生的成绩、产品的市场占有率等。序决策系统是经典决策系统的一种拓展。在序决策系统中，属性的值域是有序的，在样本间能建立偏序(优势)关系。为了从序决策系统中提取有效信息，Greco 等[9]提出了优势粗糙集方法(Dominance-based rough set approach, DRSA)。

如今，对于DRSA 的研究已经较为深入。对于序决策系统中不同的分类特征，专家学者们设计了许多不同的属性约简算法。Yuan 等[10]提出了上近似保持约简和广义决策保持约简的算法，并证明了两种算法结果的等价性。Xu 等[11]提出了下近似保持约简算法。Qian 等[12] [13]将DRSA 应用于集值数据和区间值数据，提出了优势关系保持的约简算法。

以上提及的算法是基于差别矩阵[14]、利用布尔运算法则来进行计算的。

尽管这种方法能够得到所有的约简结果，但计算的时间复杂度高。为了提升属性约简的效率，专家学者们在序决策系统中研究设计了启发式算法[15] [16] [17]。启发式算法能够根据不同的分类特征得到一个约简结果，计算效率高。本文基于后向贪婪策略，在序决策系统中提出了下近似约简的启发式算法。实验表明，本文所提的算法能计算出一个正确的下近似约简，且在时间效率上优于Xu 等[11]提出的差别矩阵算法。

2. 基本概念 给定一个序决策系统(), SO AMN= = ∪，O 是样本集合，也被称为论域。A 是属性集合，其中M 是条件属性集合，N 是决策属性集合。对于aA∀∈，xO∀∈，( )a x 表示样本x 在某个属性a 下的取值。表1 为一个序信息系统，论域{}1234, , , Ox xxx=，条件属性集{}, , Ma b c=，决策属性集{ }Nd=。