序决策系统下基于图顶点最小覆盖的属性约简

现如今的互联网时代，数据维度灾难性增长，如何从高维数据中提取有用信息成为一大难题。属性约简是数据预处理的重要步骤之一，能够减少属性维度和计算复杂度，提高分类性能和可解释性。传统的属性约简方法主要基于信息论、统计学或启发式算法，存在不足之处。本文提出了一种基于图顶点最小覆盖的序决策系统属性约简方法，利用图来建模属性之间的依赖关系，使属性约简算法和图论知识相结合。实验结果表明，本文方法在多个数据集上具有较好的约简效果和分类性能，具有良好的可解释性和可视化效果。

基于集合论，波兰学者Pawlak 于1982 年提出了粗糙集理论[1]，粗糙集理论是用于处理不精确、不一致、不完备信息和知识的有效工具，其主要思想是通过上下近似来表示数据中的确定性与不确定性， 从而推导出相应的决策规则。属性约简[2] [3] [4] [5]作为粗糙集理论数据预处理中的一个重要步骤，目的是减少属性维度和计算复杂度，做到数据降维。目前，许多学者对属性约简作了深入的研究并取得了很多成果[6] [7] [8] [9] [10]，但目前的研究大多以在传统粗糙集理论不断改进启发式属性约简或差别矩阵算法为主[11] [12] [13]。

超图是图论中的一种扩展，能够表示节点之间的多重关系，被广泛应用于数据分析、图像分割、社交网络等领域。超图应用于数据分析主要包括超图聚类、超图分析、超图可视化等方面。超图理论将数据点作为节点，利用超图表达样本之间的关系。超图分析方法将数据点和特征作为节点，利用超图表达数据之间的依赖关系，实现数据分析，能够将复杂数据映射到超图上，展示数据之间的关系和特征，提高数据的可视化效果和理解性。

本文从超图理论的角度出发，将超图理论的最小顶点覆盖算法与序决策系统相结合，提高约简效率。

经实验证明本文所提算法具备一定的有效性。

2. 基本概念 2.1. 序决策系统 设一个四元组(), , , CISU AT V f=为一个信息系统，如果在信息系统CIS 中的某一属性的值域上存在偏序关系，则称该属性为一个准则。当CIS 中每个属性都为一个准则时，该系统为一个序决策系统(), , , OISU AT V f=。其中： • U：表示所有对象的集合，称为论域。

• AT：包含条件属性集合C 和决策属性集合D。

• V：表示条件属性集合C 和决策属性集合D 的值域。

• f：代表一个映射函数:f UATV×→， 论域中的每一个对象在条件属性和决策属性上对应一个属性值， 即()( ), ikkif x ccx=。

定义1 [14] 在序决策系统(), , , OISU AT V f=中，对于C∀⊆，有优势关系定义如下：