一种不完备决策系统下快速求取正域的算法

现如今的互联网时代，数据维度灾难性增长，如何从高维数据中提取有用信息成为一大难题。由于数据的不完整性，不完备决策系统逐渐得到人们的关注。在数据中寻找确定性的规则是当今社会重要的研究方向之一，在不完备决策系统中正域的计算则代表着确定性的规则的提取。但效率一直是正域计算中的关键问题，正域的计算必须要通过求取相容类，计算相容类的复杂度直接影响到计算正域的复杂度。本文利用样本在属性集合下相容类的单调性给出了一个时间复杂度低的计算正域的算法。实验结果表明，本文方法在多个数据集上无论是维度还是规模上效率都是较高的，具有更好的稳定性，更适用于大规模以及大维度的数据。

在当代信息时代，数据的快速增长和复杂性给决策过程带来了巨大挑战。面对庞大、多样化的数据集，基于粗糙集理论[1]的传统的经典决策系统可能无法满足需求。因此，不完备决策系统[2] [3]成为了处理复杂决策问题的有效工具。不完备决策系统基于一种基本假设，即我们所拥有的信息并不完整，因此需要从有限的信息中进行决策。通过考虑不完整性和不确定性，不完备决策系统能够在实践中更好地适应真实世界的复杂性。

不完备决策系统的发展已经取得了显著的进展。研究者们提出了许多创新的方法和算法，用于有效地处理缺失数据[4] [5]、模糊信息[6] [7]、优势关系[8] [9]等问题。这些方法和算法使得不完备决策系统能够更好地应对现实中的不确定性，并提供可靠的决策支持。此外，随着机器学习、人工智能等领域的快速发展，不完备决策系统正逐渐融合这些技术，为决策制定者提供更准确、可靠的决策建议。

通过深入研究和分析，利用不完备决策系统解决现实世界中的复杂决策问题，寻找对应确定性的规则是一个重要的目标。在不完备决策系统中寻找确定性的规则，必须通过相容类的计算，而相容类的效率问题一直阻碍者确定性规则的提取速度。本文通过不完备决策系统的中容差类的单调性以及对正域的分析， 提出了一种在不完备系统下快速寻找正域(确定性规则)的算法， 经过实验证明本文所提算法的有效性以及稳定性。

2. 基本概念 不完备决策系统 由于数据采集或数据损坏等原因导致决策系统部分信息缺失， 则称此类决策系统为不完备决策系统， 本节将主要介绍不完备决策系统下的粗糙集理论相关概念，包括不完备决策系统、相容关系、上近似集、下近似集、正域、边界域和负域等相关概念。

定义1 [10]在给定信息系统(), , , ISU AT V f=中，其中{}12, , , UUx xx=表示非空有限对象的集合， 称之为论域；AT 表示属性的非空有限集合；{}aVV aAT=∈，其中aV 表示属性aAT∈的值域；