基于区间值决策系统的正域快速求解算法

Fast Algorithms for Computing Positive Regions Based on Interval-Valued Decision Systems

摘要: 区间值决策系统在不确定性数据处理领域具有重要应用价值，而正域的高效计算是提升系统整体性能的关键。由于相容类的计算是正域求解的必要步骤，但是传统相容类计算方法在处理大规模数据时面临较高的计算复杂度，导致属性约简的效率显著下降。针对这一问题，本文提出了一种利用哈希思想的快速计算方法。该方法通过哈希函数对每个对象进行快速分区，缩小相容类的查找范围，减少冗余计算，从而显著提升了相容类的计算效率，以至于能够优化属性约简的整体性能。通过在8个UCI数据集上的实验验证，本文所提方法在计算速度上较传统方法具有明显优势，为区间值决策系统的高效属性约简算法提供了新思路。

Abstract: Interval-valued decision systems play a crucial role in uncertain data processing, where the efficient computation of the positive domain is essential for enhancing overall system performance. Since the computation of compatible classes is a necessary step in solving the positive domain, traditional methods for computing compatible classes face high computational complexity when handling large-scale data, leading to a significant decline in attribute reduction efficiency. To address this issue, this paper proposes a fast computation method based on hashing techniques. By utilizing hash functions to rapidly partition each object, the proposed method narrows the search scope for compatible classes, reduces redundant computations, and significantly improves the efficiency of compatible class computation, thereby optimizing the overall performance of attribute reduction. Experimental validation on eight UCI datasets demonstrates that the proposed method achieves a significant speed advantage over traditional approaches, providing new insights for developing efficient attribute reduction algorithms in interval-valued decision systems.

1. 引言

随着信息技术的飞速发展，数据规模和复杂性呈指数级增长，如何从海量、高维、不确定的数据中高效提取有价值的信息已成为数据挖掘与知识发现领域的关键研究问题。Pawlak于1982年提出粗糙集理论[1]，该理论是一种处理不确定性和不完备信息的数学工具，随着技术的发展，这一工具在数据分析、模式识别和机器学习等领域展现了其重要价值，得到了广泛应用。区间值决策系统[2]-[4]作为粗糙集理论的重要扩展，能够有效处理区间特征的数据，在不确定数据分析和决策支持中发挥着重要作用。

在区间值决策系统中，属性约简[5]-[8]是核心任务之一，而正域中的相容类的求解是属性约简的关键步骤。然而随着数据规模的增大和维度的提升，传统的相容类计算方法逐渐暴露出计算效率较慢的问题，成为系统性能的主要瓶颈。因此提升相容类的计算效率对于优化区间值决策系统的整体性能具有重要意义。近年来，研究者们提出了多种属性约简的优化方法，如差别矩阵[9]-[12]、启发式算法等，但这些方法在处理大规模数据时仍存在性能不足的问题，因此提高属性约简的效率成为了研究热题。

针对现有方法的局限性，本文提出了一种基于区间值决策系统的正域快速求解算法。该算法通过哈希函数对对象进行快速分区，并利用对象在属性集合下相容类的单调性优化计算过程，从而显著减少冗余计算，提升相容类的计算效率，进而优化属性约简的整体性能。通过在8个UCI数据集上的实验验证，本文所提方法在计算速度上较传统方法具有明显优势，能够更好地满足大规模、高维度数据的处理需求，为区间值决策系统的高效计算提供了新的解决方案。

2. 基本概念

定义1：给定一个四元组$IVDS=\left(U,A=C\cup D,V,f\right)$ 为区间值决策系统，$U=\left\{x_1,x_2\cdots x_n\right\}$ 为论域，$C=\left\{a_1,a_2\cdots a_m\right\}$ 为条件属性集合，$D=\left\{d\right\}$ 为决策属性的集合，$V_a$ 是条件属性a的值域，$f:U\times A\to V$ 是一个对象与属性值间的映射函数，$f\left(x,a\right)=a\left(x\right)$ 表示对象$x\in U$ 在条件属性$a\in C$ 上的取值，而$a\left(x\right)$ 的值为一个区间，$a\left(x\right)=\left[a^{-},a^{+}\right]$ ，其中$a^{-}$ 代表区间的左边界，$a^{+}$ 代表区间的右边界。

定义2：假设区间值决策系统$IVDS=\left(U,A=C\cup D,V,f\right)$ 中的任意两个区间$I_1=\left[l^{-},l^{+}\right]$ 和$I_2=\left[e^{-},e^{+}\right]$ ，则区间$I_1$ 和区间$I_2$ 之间的交运算和并运算定义如下：

$I_1\cap I_2=\{\begin{array}{l}\left[\max (l^{-},e^{-}),\min (l^{+},e^{+})\right],\max \left(l^{-},e^{-}\right)\le \min \left(l^{+},e^{+}\right)\\ \varnothing ,otherwise\end{array}$ (1)

$I_1\cup I_2=\{\begin{array}{l}\left[\min \left(l^{-},e^{-}\right),\max \left(l^{+},e^{+}\right)\right],\max \left(l^{-},e^{-}\right)\le \min \left(l^{+},e^{+}\right)\\ \left[l^{-},l^{+}\right]\cup \left[e^{-},e^{+}\right],otherwise\end{array}$ (2)

定义3 [13]：假设区间值决策系统$IVDS=\left(U,A=C\cup D,V,f\right)$ 中的两个对象$\forall x,y\in U$ ，条件属性$a_m\in C$ ，则对象x和y在条件属性$a_m$ 下的取值分别为$x_m=\left[l^{-},l^{+}\right]$ ，$y_m=\left[e^{-},e^{+}\right]$ ，则对象x相较于对象y在条件属性$a_m$ 下的优势度定义为：

$G_{x_m\ge y_m}=\min \left(1,\max \left(\frac{l^{+}-e^{-}}{\left(l^{+}-l^{-}\right)-\left(e^{+}-e^{-}\right)}，0\right)\right)$ (3)

优势度具有以下性质：

1) $G_{x_m\ge y_m}\ne G_{y_m\ge x_m}$ ；

2) $0\le G_{x_m\ge y_m}\le 1$ ；

3) $G_{x_m\ge y_m}+G_{y_m\ge x_m}=1$ ；

4) $G_{x_m\ge x_m}=G_{y_m\ge y_m}=0.5$ 。

定义4 [13]：假设区间值决策系统$IVDS=\left(U,A=C\cup D,V,f\right)$ 中的两个对象$\forall x,y\in U$ ，条件属性$a_m\in C$ ，则对象x和y在条件属性$a_m$ 下的优势度分别为$G_{x_m\ge y_m}$ 和$G_{y_m\ge x_m}$ ，$\forall P\subseteq C\left(\left|P\right|=s\right)$ ，则对象x和对象y在条件属性子集P下的相似距离定义为：

$\vartheta \left(x,y\right)=\sqrt{{{\displaystyle \sum {}_{m=1}^s\left(G_{x_m\ge y_m}-G_{y_m\ge x_m}\right)}}^2}$ (4)

则相似距离$\vartheta$ 具有以下性质：

1) $\vartheta \left(x,x\right)=0$ ；

2) $\vartheta \left(x,y\right)=\vartheta \left(y,x\right)$ ；

3) $\vartheta \left(x,z\right)\le \vartheta \left(x,y\right)+\vartheta \left(y,z\right)$ ；

4) $\vartheta \left(x,z\right)\ge \vartheta \left(x,y\right)-\vartheta \left(y,z\right)$ 。

定义5：给定一个区间值决策系统$IVDS=\left(U,A=C\cup D,V,f\right)$ ，相似距离阈值$0\le \epsilon \le 1$ ，对于非空条件属性子集$\forall P\subseteq C$ ，则定义在条件属性子集P下ε-相容关系${\zeta }_P^{\epsilon }$ 为：

${\zeta }_P^{\epsilon }=\left\{\left(x_i,x_j\right)|\left(x_i,x_j\right)\in U^2,\forall a_k\in P\wedge \vartheta \left(x_i,x_j\right)\le \epsilon \right\}$ (5)

定义6：给定一个区间值决策系统$IVDS=\left(U,A=C\cup D,V,f\right)$ ，对于非空条件属性子集$\forall P\subseteq C$ ，对于$\forall x_i\in U$ ，则对象$x_i$ 在条件属性子集P下ε-相容类${{\rm T}}_P^{\epsilon }\left(x_i\right)$ 定义为：

${{\rm T}}_P^{\epsilon }\left(x_i\right)=\left\{x_j|\forall x_j\in U,\left(x_i,x_j\right)\in {\zeta }_P^{\epsilon }\right\}$ (6)

而在条件属性子集P下的相容类集合为：

${{\rm T}}_P^{\epsilon }\left(U\right)=\left\{{{\rm T}}_P^{\epsilon }\left(x_1\right),{{\rm T}}_P^{\epsilon }\left(x_2\right),\cdots ,{{\rm T}}_P^{\epsilon }\left(x_{\left|U\right|}\right)\right\}$ (7)

定义7：给定一个区间值决策系统$IVDS=\left(U,A=C\cup D,V,f\right)$ ，$\forall P\subseteq C$ ，对于$\forall X\subseteq U$ ，则目标集合X关于条件属性子集P的下、上近似定义为：

$\underset{\_}{R{S}_P}\left(X\right)=\left\{x_i|x_i\in U,{{\rm T}}_P^{\epsilon }\left(x_i\right)\subseteq X\right\}$ (8)

$\overline{R{S}_P}\left(X\right)=\left\{x_i|x_i\in U,{{\rm T}}_P^{\epsilon }\left(x_i\right)\cap X\ne \varnothing \right\}$ (9)

由此可推出正域为$PO{S}_P\left(X\right)=\underset{\_}{R{S}_P}\left(X\right)$ ，边界域为$BN{D}_P\left(X\right)=\overline{R{S}_P}\left(X\right)-\underset{\_}{R{S}_P}\left(X\right)$ ，负域为$NE{G}_P\left(X\right)=U-\overline{R{S}_P}\left(X\right)$ 。

根据上述定义，给出了基于区间值决策系统的下近似经典计算算法，算法详情如表1所示。

Table 1. Classical algorithm for computing positive region in interval-valued decision systems (CCMLA)

表1. 区间值决策系统的正域经典求解算法

输入：一个区间值决策系统$IVDS=\left(U,AT=C\cup D,V,f\right)$ ，相似距离阈值$\epsilon$

输出：IVDS的正域集合$PO{S}_C\left(D\right)$

1) 初始化：$PO{S}_C\left(D\right)=\varnothing$

2) 对于$\forall x_i\in U$ ，根据定义5计算对象$x_i$ 的相容类${{\rm T}}_P^{\epsilon }\left(x_i\right)$

3) 若${{\rm T}}_P^{\epsilon }\left(x_i\right)$ 完全包含在决策类中，$PO{S}_C\left(D\right)=PO{S}_C\left(D\right)\cup x_i$

4) 输出正域集合$PO{S}_C\left(D\right)$

假设区间值决策系统IVDS中包含n个对象，m个条件属性，在计算相容类时，需要遍历数据集中的每个对象，并依据定义计算相容关系，在全部属性下计算正域的时间复杂度为$O\left(m\cdot n^2\right)$ 。

3. 区间值决策系统的正域快速求解算法

定义8 [14]：给定一个区间值决策系统$IVDS=\left(U,A=C\cup D,V,f\right)$ ，相似距离阈值$0\le \epsilon \le 1$ ，对于$\forall b\subseteq C$ ，通过哈希函数可以将论域U中的所有对象在条件属性b下映射到有限个区域$Q_1,Q_2,\cdots Q_t$ 中，其中区域$Q_t$ 中的对象集合定义为：

$Q_t=\left\{x_i|\forall x_i\in U,\lceil {\vartheta }_b\left(x_0,x_i\right)/\epsilon \rceil =t\right\}$ (10)

其中$x_0$ 表示在每个条件属性下的最小区间值，选取方法为：先确定下边界最小的区间，若下边界相同，则选择上边界最小的区间。${\vartheta }_b\left(x_0,x_i\right)$ 表示为在条件属性b下两者之间的相似距离，$Q_t$ 集合中的所有对象表示都和当前条件属性下最小区间值的相似距离在$\left(\left(t-1\right)\epsilon ,t\epsilon \right)$ 之间。

定理1：给定一个区间值决策系统$IVDS=\left(U,A=C\cup D,V,f\right)$ ，相似距离阈值$0\le \epsilon \le 1$ ，对于$\forall b\subseteq C$ ，根据上述定义所示，通过哈希函数可以将论域U中的所有对象在条件属性b下映射到有限个区域$Q_1,Q_2,\cdots Q_t$ 中，则对于$\forall x_i\in Q_g\left(g=2,3\cdots t-1\right)$ ，则对象$x_i$ 的相容类对象仅包含在区域$Q_{g-1},Q_g,\cdots Q_{g+1}$ 中；如果$\forall x_i\in Q_1$ ，则对象$x_i$ 的相容类对象仅包含在区域$Q_1,Q_2$ 中；如果$\forall x_i\in Q_t$ ，则对象$x_i$ 的相容类对象仅包含在区域$Q_t,Q_{t-1}$ 中。

证明：图1为有6个区域的哈希映射图$Q_1,Q_2,\cdots Q_6$ ，假设存在两个对象$x_1,x_2\in U$ ，根据上述定义在条件属性b下，对象$x_1$ 映射到了区域$Q_2$ ，对象$x_2$ 映射到了区域$Q_4$ ，即$x_1\in Q_2$ ，$x_2\in Q_4$ ，则有$\epsilon <{\vartheta }_b\left(x_0,x_1\right)\le 2\epsilon$ ，$3\epsilon <{\vartheta }_b\left(x_0,x_2\right)\le 4\epsilon$ ，此时${\vartheta }_b\left(x_0,x_2\right)-{\vartheta }_b\left(x_0,x_1\right)>\epsilon$ ，并且由相似距离函数的性质可知${\vartheta }_b\left(x_1,x_2\right)<{\vartheta }_b\left(x_0,x_1\right)+{\vartheta }_b\left(x_0,x_2\right)$ ，并且${\vartheta }_b\left(x_1,x_2\right)>{\vartheta }_b\left(x_0,x_2\right)-{\vartheta }_b\left(x_0,x_1\right)$ ，所以有${\vartheta }_b\left(x_1,x_2\right)>\epsilon$ ，所以对象$x_1$ 和对象$x_2$ 在条件属性b下不构成相容关系，即不在同一个相容类中。对于$\forall x_i,x_j\in U$ ，$\forall Q_t\in Q$ ，上述均可被同理证明，证明完毕。

Figure 1. Hash mapping graph

图1. 哈希映射图

根据上述定义可以得出基于区间值决策系统的下近似快速计算算法，算法详情如表2所示。

Table 2. Fast algorithm for computing positive region in interval-valued decision systems (FCMLA)

表2. 区间值决策系统的正域快速求解算法(FCMLA)

输入：一个区间值决策系统$IVDS=\left(U,AT=C\cup D,V,f\right)$ ，相似距离阈值$\epsilon$

输出：$IVDS$ 的正域集合$PO{S}_C\left(D\right)$

1) 初始化：$PO{S}_C\left(D\right)=\varnothing$

2) 对于$\forall a_m\in C$ ，求出在条件属性$a_m$ 下的最小值

3) 对于$\forall x_i\in U$ ，根据定义9计算对象$x_i$ 的映射区域$Q_t$

4) 对于$\forall x_j\in U$ ，遍历对象$x_j$ 所在区域以及相邻区域求得${{\rm T}}_P^{\epsilon }\left(x_j\right)$

5) 若${{\rm T}}_P^{\epsilon }\left(x_j\right)$ 完全包含在决策类中，$PO{S}_C\left(D\right)=PO{S}_C\left(D\right)\cup x_j$

6) 输出正域集合$PO{S}_C\left(D\right)$

假设区间值决策系统IVDS中包含n个对象，m个条件属性，传统的相容类计算方法需要遍历两次论域U，因此在寻找所有对象相容类的时间复杂度为$O\left(m\cdot n^2\right)$ ，而用哈希函数映射的方法，只需要遍历当前对象的区域以及邻近区域中的对象即可，不用再去遍历所有的对象，具体的时间复杂度由对象所在区域和邻近区域内的数量决定，时间复杂度明显小于$O\left(m\cdot n^2\right)$ 。当所有的对象经过哈希函数的映射都在一个区域内，此时的时间复杂度最大，时间复杂度应为$O\left(m\cdot n^2\right)$ ；而当每个对象都被映射到单独一个区域内，那么也就是经过哈希函数的映射，每个区域内只有一个对象时，此时的时间复杂度最小，时间复杂度达到了$O\left(m\cdot n\right)$ 。

4. 实验分析

实验选取了8组UCI数据集，数据集的详细信息如表3所示，对于数据集中的符号型数据、缺失数据、名词型数据、连续型数据等不同的数据类型，分别采用数值化处理、插值法替换、{0、1}替换、等频分割等方法进行处理。等数据处理完之后，使用编写的区间值数据生成算法对上述数据集进行处理，使之生成新的区间值数据集。实验主要验证区间值决策系统的正域经典求解算法(CCMLA)与本文章提出的区间值决策系统的正域快速求解算法(FCMLA)的计算效率对比，本实验的实验环境为：Windows10 64位操作系统；8GB的内存；Intel(R) Core(TM) i7-8550U CPU；软件环境为：PyCharm；编程环境为：Python，相似距离阈值$\epsilon =0.2$ 。

实验对比了区间值决策系统的正域经典求解算法(CCMLA)同区间值决策系统的正域快速求解算法(FCMLA)计算下近似的时间消耗情况。将数据集的对象平均分成10份，每份占原数据集大小的10%，数据集对象的初始数量从10%开始，每次添加10%的对象数量，直至添加至原数据集大小。图2表示随着对象数量的变化，两个算法下近似计算时间的变化情况，蓝色五角星折线是本文提出的算法FCMLA，红色球形折线是经典算法CCMLA，横坐标为添加对象比例，纵坐标是算法运行时间，单位为秒。

Table 3. UCI datasets

表3. UCI数据集

序号	数据集	样本数	属性数	类别数
1	Divorce	170	54	2
2	Sonar	208	60	2
3	Libras	360	90	15
4	Turkish	400	50	4
5	Musk	476	168	2
6	Breast Cancer	568	30	2
7	Sports	1000	59	2
8	Statlog	4435	36	6

从图2中可以看出，本文所提的算法FCMLA在8个数据集下都优于经典算法CCMLA，而且随着对象数量的增加，两种算法所消耗的时间都有所上升，但FCMLA算法时间消耗起伏较小，而CCMLA算法的时间消耗起伏较大。在大数据集上更明显，比如Statlog数据集，随着对象数量的增加，CCMLA算法时间消耗明显上升，而FCMLA算法时间消耗起伏很小，几乎为一条直线。

Figure 2. Time efficiency graph

图2. 时间效率图

Figure 3. Time speedup ratio

图3. 时间加速比

图3为CCMLA算法与FCMLA算法所用时间的比值，来进一步证实了FCMLA算法的优越性，可以观察到FCMLA算法在Sonar数据集上的加速比是CCMLA算法的3.12倍到5.78倍；在Statlog数据集上的加速比是CCMLA算法的4.03倍到15.89倍。

5. 结论

在本文中，针对传统正域计算算法在处理大规模区间值决策系统时计算复杂度较高的问题，提出了一种采用哈希思想的快速求解算法。该算法利用哈希函数对每个对象进行快速分区，并结合相容类的单调性优化计算过程，有效减少冗余计算，提高计算效率。实验结果表明，在8个UCI数据集上，本文所提算法在计算速度上优于传统算法，且在大规模数据集上的性能更稳定，具有较高的应用价值。

基金项目

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