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

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.

1. 引言

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

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

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

2. 基本概念

不完备决策系统

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

定义1 [10] 在给定信息系统 $IS=\left(U,AT,V,f\right)$ 中，其中 $U=\left\{x_1,x_2,\cdots ,x_{\left|U\right|}\right\}$ 表示非空有限对象的集合，称之为论域；AT表示属性的非空有限集合； $V=\cup \left\{V_a|a\in AT\right\}$ ，其中 $V_a$ 表示属性 $a\in AT$ 的值域； $f:U\times AT\to V$ 是信息函数， $f\left(x,a\right)$ 表示对象 $x\in U$ 在属性 $a\in AT$ 上的值，简称 $a\left(x\right)$ 。

在信息系统IS中，若 $AT=C\cup D$ ，则该信息系统被称为决策系统，记作 $DS=\left(U,AT=C\cup D,V,f\right)$ ，其中C表示非空有限的条件属性的集合，D表示非空有限的决策属性的集合。

定义2 [10] 在决策系统 $DS=\left(U,AT=C\cup D,V,f\right)$ 中，若存在 $a\in C$ 使得 $V_a$ 含有缺失值，且缺失值使用 $\ast$ 表示，则该决策系统被称为不完备决策系统，记作 $IDS=\left(U,AT=C\cup D,V,f\right)$ ，其中决策属性 $d\in D$ 的值域 $V_d$ 中均不含有缺失值。

定义3 [10] 在不完备决策系统 $IDS=\left(U,AT=C\cup D,V,f\right)$ 下，对于 $\forall ℂ\in C$ ，存在相容关系：

$TOL\left(ℂ\right)=\left\{\left(x,y\right)\in U\ast U|\forall a\in ℂ,a\left(x\right)=a\left(y\right)\vee a\left(x\right)=\ast \vee a\left(y\right)=\ast \right\}$ (1)

设 ${\partial }_{ℂ}\left(x\right)=\left\{y\in U|\left(x,y\right)\in TOL\left(ℂ\right)\right\}$ ，其中 ${\partial }_{ℂ}\left(x\right)$ 表示通过条件属性集合 $ℂ$ 与样本x不可区分的对象的集合， ${\partial }_{ℂ}\left(x\right)$ 也被称为相容类。因此，可以导出论域U在属性子集 $ℂ$ 上的覆盖 $U/TOL\left(ℂ\right)=\left\{{\partial }_{ℂ}\left(x\right)|x\in U\right\}$ 。

性质 1不完备决策系统 $IDS=\left(U,AT=C\cup D,V,f\right)$ 中，对于 $\forall ℂ\in C$ ，有：

$TOL\left(ℂ\right)=\underset{a\in ℂ}{\cap }TOL\left(a\right)$ (2)

同时相容关系 $TOL\left(ℂ\right)$ 满足：

1) 自反性：对 $\forall x\in U$ ，有 $\left(x,x\right)\in TOL\left(ℂ\right)$ 。

2) 对称性：对 $\forall x,y\in U$ ，若 $\left(x,y\right)\in TOL\left(ℂ\right)$ ，则 $\left(y,x\right)\in TOL\left(ℂ\right)$ 。

定义4 [11] 在不完备决策系统 $IDS=\left(U,AT=C\cup D,V,f\right)$ 中，对于 $\forall ℂ\subseteq C$ ， $\forall X\in U$ ，对于X关于 $ℂ$

的下、上近似定义如下：

$\underset{\_}{App{r}_{ℂ}}\left(X\right)=\left\{x_i\in U|{\partial }_{ℂ}\left(x_i\right)\subseteq X\right\}$ (3)

$\overline{App{r}_{ℂ}}\left(X\right)=\left\{x_i\in U|{\partial }_{ℂ}\left(x_i\right)\cap X\ne \varnothing \right\}$ (4)

且正域表示为 $PO{S}_{ℂ}\left(X\right)=\underset{\_}{App{r}_{ℂ}}\left(X\right)$ ，边界域表示为 $BN{D}_{ℂ}\left(X\right)=\overline{App{r}_{ℂ}}\left(X\right)-\underset{\_}{App{r}_{ℂ}}\left(X\right)$ ，负域为 $NE{G}_{ℂ}\left(X\right)=U-\overline{App{r}_{ℂ}}\left(X\right)-\underset{\_}{App{r}_{ℂ}}\left(X\right)$ 。

定义5 [11] 在不完备决策系统 $IDS=\left(U,AT=C\cup D,V,f\right)$ 中，假设论域U对决策属性D上的划分为 $U/D=\left\{D_1,D_2,\cdots ,D_m\right\}$ $\left(1\le m\le \left|U\right|\right)$，对于 $\forall ℂ\subseteq C$ ，决策类集合U/D关于条件属性集合 $ℂ$ 的下、上近似

定义如下：

$\underset{\_}{App{r}_{ℂ}}\left(U/D\right)=\left\{\underset{\_}{App{r}_{ℂ}}\left(D_1\right),\underset{\_}{App{r}_{ℂ}}\left(D_2\right),\cdots ,\underset{\_}{App{r}_{ℂ}}\left(D_m\right)\right\}$ (5)

$\overline{App{r}_{ℂ}}\left(D\right)=\left(\overline{App{r}_{ℂ}}\left(D_1\right),\overline{App{r}_{ℂ}}\left(D_2\right),\cdots ,\overline{App{r}_{ℂ}}\left(D_m\right)\right)$ (6)

决策类集合U/D关于条件属性 $ℂ\subseteq C$ 的正域以及边界域定义为：

$PO{S}_{ℂ}\left(U/D\right)=\underset{D_i\in U/D}{\cup }\underset{\_}{App{r}_{ℂ}}\left(D_i\right)$ (7)

$BN{D}_{ℂ}\left(U/D\right)=\underset{D_i\in U/D}{\cup }\overline{App{r}_{ℂ}}\left(D_i\right)-\underset{D_i\in U/D}{\cup }\underset{\_}{App{r}_{ℂ}}\left(D_i\right)$ (8)

基于上述定理，表1给出不完备决策系统下的正域计算算法(Positive domain computational algorithms in incomplete decision systems, PDCA-IDS)。

Table 1. Positive domain computational algorithms in incomplete decision systems (PDCA-IDS)

表1. 不完备决策系统下的正域计算算法(PDCA-IDS)

上述传统的计算正域的时间复杂度为 $O\left(m{n}^2\right)$ ，其中m为条件属性的个数(即 $\left|C\right|$ )，n为样本对象的个数。时间复杂度较高，效率低下。

3. 基于不完备决策系统的正域快速算法

由于数据量的增大，数据的维度和规模都是对不完备信息数据进行相容类的划分时的一个考验。常规的容差类的划分时间复杂度高、效率低下，本小节主要介绍相容类的单调性、对正域的分析以及正域快速算法的构建。

3.1. 相容类的快速计算

定理1 [12] 给定一个不完备决策系统 $IDS=\left(U,AT=C\cup D,V,f\right)$ ，X₁和X₂是C的两个属性子集，其中 $X_1\subseteq X_2\subseteq C$ ，对于 $\forall x_i\in U$ ， ${\delta }_{X_2}\left(x_i\right)\subseteq {\delta }_{X_1}\left(x_i\right)$ 。

定理1说明在当属性子集越大时，对任意样本对象 $x_i$ 来说所含有的与其保持一致的样本对象越少，即对于任意的样本对象 $x_i$ 在较大的属性子集下的相容类可以通过较小的属性子集的相容类得出。

Table 2. Fast positive domain computing algorithms for incomplete decision systems (FPDCA-IDS)

表2. 不完备决策系统下快速正域计算算法(FPDCA-IDS)

3.2. 正域的快速计算

定理2 [13] 给定一个不完备决策系统 $IDS=\left(U,AT=C\cup D,V,f\right)$ ，X₁和X₂是C的两个属性子集，其中 $X_1\subseteq X_2\subseteq C$ ，可以得到 $PO{S}_{X_1}\left(D\right)\subseteq PO{S}_{X_2}\left(D\right)$ 。

定理3 [13] 给定一个不完备决策系统 $IDS=\left(U,AT=C\cup D,V,f\right)$ ，X₁和X₂是C的两个属性子集，其中 $X_1\subseteq X_2\subseteq C$ ，对于 $\forall x_i\in U$ ， $x_i\in PO{S}_{X_1}\left(D\right)$ ，那么 $x_i\in PO{S}_{X_2}\left(D\right)$ 。

定理2和定理3表明在当任意一个对象属于较小属性子集的正域时，则必属于包含整个较小属性子集的较大属性子集的正域。

基于上述定理，表2给出不完备决策系统下快速正域计算算法(Fast Positive Domain Computing Algorithms inIncomplete Decision Systems, FPDCA-IDS)。

4. 实验分析

本实验选取八组UCI数据集进行求取正域效率对比，详细信息如表3所示。在验证算法有效性之前，使用WEKA3.8对数据集进行离散化预处理。本节进行的所有的实验都是在一台带有MacOS13.4 Ventura、8核、M1芯片和16GB内存的笔记本电脑上进行。算法在Pycharm2023开发工具是使用Python编写，实验图使用Python绘制。

Table 3. Dataset information

表3. 实验使用的数据集

4.1. 纬度效率验证

如图1所示为本文所提算法FPDCA-IDS与经典求取正域的算法PDCA-IDS在不完备决策系统下改变数据集的维度时(即改变属性个数的多少时)算法的执行时间曲线。红色球形折线为本文提出的算法FPDCA-IDS，蓝色三角折线为传统的计算正域的方法PDCA-IDS。横坐标为属性的个数，纵坐标为运行所需要的时间单位为秒。

从图1中可以看出，当数据集的属性个数都较少时算法的效率差别不大。当随着属性的个数逐渐增加时，两种算法的执行时间均有上升，但是FPDCA-IDS算法的折线始终保持在PDCA-IDS算法折线的下方，也就是FPDCA-IDS算法一直保持较好的效率。尤其是当属性的个数不断增加时，两种算法直接的差距更为明显，本文提出的算法优势更大。并且本文提出的算法随着属性个数的增加变化比较均匀，稳定性更好。因此，相对来说可以证明本文提出的算法更加适用于维度较高的数据集。

Figure 1. Comparison of efficiency in longitude

图1. 维度下的效率对比

4.2. 规模效率验证

如图2所示为本文所提算法FPDCA-IDS与经典求取正域的算法PDCA-IDS在不完备决策系统下改变数据集的规模时(即改变样本对象个数的时)算法的执行时间曲线。红色球形折线为本文提出的算法FPDCA-IDS，蓝色三角折线为传统的计算正域的方法PDCA-IDS。横坐标为样本对象的比例，纵坐标为运行所需要的时间单位为秒。

从图2中可以看出，当数据集的样本对象个数较少时算法的效率差别不大。当随着属性的个数逐渐增加时，两种算法的执行时间均有上升，但是本文提出的算法随着样本对象比例的增加变化比较均匀，稳定性更好。本文提出的FPDCA-IDS算法的折线始终保持在PDCA-IDS算法折线的下方，也就是FPDCA-IDS算法一直保持较好的效率。当样本对象比例较高时，两种算法直接的差距更为的明显，本文提出的算法优势更大。因此，相对来说可以证明本文提出的算法更加适用于大规模的数据集。

Figure 2. Comparison of efficiency in magnitude

图2. 规模下的效率对比

5. 结论

在本文中，首先通过分析相容类的单调性以及正域在属性集合下的规律，进一步提出了一种时间复杂度较低的计算相容类和正域的算法。本文所提算法FPDCA-IDS与传统的计算正域的算法PDCA-IDS思想相比，减少了多次迭代次数和属性值的比较次数，能够有效的避免了时间复杂度过高的问题，可以大幅度提高算法的计算效率。本文最后通过选取的八组UCI数据集上进行算法有效性验证。从实验结果可以看出，本文所提算法相比于传统的计算正域的算法效率较高并且更加的稳定，尤其是更适用于大规模数据集以及维度较高的数据集。

基金项目

本文受烟台市科技计划项目(编号：2022XDRH016)的资助。

参考文献