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

A Fast Algorithm for Computing Positive Regions in an Incomplete Decision System

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

Abstract: Nowadays, in the era of the Internet, data dimensions are growing catastrophically. Extracting use-ful information from high-dimensional data has become a major challenge. Due to the incompleteness of data, incomplete decision systems are gradually gaining attention. Finding deterministic rules in data is one of the important research directions in today’s society, and computing the posi-tive domain in incomplete decision systems represents the extraction of deterministic rules. How-ever, efficiency has always been a key issue in the computation of positive domains. This computa-tion involves finding tolerance classes, and the complexity of computing the tolerance classes di-rectly affects the complexity of computing the positive domains. In this paper, we utilize the mono-tonicity of the tolerance classes of the samples under the set of attributes to propose an algorithm that computes the positive domain with low time complexity. Experimental results show that the method in this paper is efficient in both dimension and scale on multiple datasets, exhibits better stability, and is more suitable for large-scale as well as high-dimensional data.