烟台大学计算机与控制工程学院，山东 烟台

收稿日期：2023年4月20日；录用日期：2023年5月19日；发布日期：2023年5月30日

摘要

近年来，信息技术不断完善并飞速发展，数据呈现出指数型增长趋势，这使得数据挖掘技术效率降低且性能变差。属性约简能去除信息系统中的冗余属性保留重要属性，是一种有效的数据降维方法，而最短约简能最大限度地删除不相关的属性，从而提高系统数据处理和分析的效率。现有在集值系统下的属性约简方法需要所有决策类的参与，算法的效率较低，而一些实际应用中，针对所有决策类的约简可能是非必要的。针对上述问题，本文以集值决策系统为数据背景，给出了特定类广义决策约简的定义，构造了特定类广义决策约简的差别矩阵及差别函数，引入最短约简算法，提出了特定类广义决策最短约简算法，最后使用8组UCI数据集从约简结果、差别矩阵非空项占比以及约简效率三个方法验证了算法的有效性。

关键词

粗糙集，粒计算，差别矩阵，属性约简

The Minimal Attribute Reduction Algorithm of General Decision Based on Class-Specific in Set-Value Decision Systems

Dejie Hu

School of Computer and Control Engineering, Yantai University, Yantai Shandong

Received: Apr. 20^th, 2023; accepted: May 19^th, 2023; published: May 30^th, 2023

ABSTRACT

In recent years, information technology has been improved and developed rapidly, and data has shown an exponential growth trend, which makes data mining techniques less efficient and less performant. Attribute reduction, which can remove redundant attributes and retain important attributes in information systems, is an effective method for data dimensionality reductionand the shortest reduction can delete irrelevant attributes, thereby improving the efficiency of data processing and analysis of the systems. The existing attribute reduction methods under set-valued systems require the participation of all decision classes, and the efficiency of the algorithm is low, while the reduction for all decision classes may be non-essential in some practical applications. To address the above problems, this paper takes the set-valued decision system as the data background, proposes the definition of class-specific generalized decision simplification, constructs the discernibility matrix and discernibility function for class-specific generalized decision simplification, introduces the shortest simplification algorithm, proposes the shortest reduction algorithm for class-specific generalized decision, and finally verifies the algorithm using eight sets of UCI data sets from the length of reduction results, the percentage of non-empty terms in the discernibility matrix and the reduction efficiency.

Keywords:Rough Settheory, Granular Computing, Discernibility Matrix, Attribute Reduction

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

粗糙集理论 [1] [2] [3] [4] 是知识获取的重要工具，可以处理不确定、不完整的知识。作为粗糙集领域的课题研究热点，属性约简能够消除决策系统中的冗余属性保留重要的属性，从而减少系统的数据维度，是一种有效的数据降维方法。经典粗糙集理论通过等价关系实现对单值数据的处理。

集值信息系统是单值信息系统的扩展，对象在条件属性下的值不是唯一的，例如一个人可以有活泼、温柔、乐观、大方等多种不同的性格。Guan [5] 等提出了集值决策系统中最大相容类相对约简的概念，利用最大相容类定义了上下近似和正域。Qian等 [6] 基于优势关系给出了集值系统的合取和析取两种类型的集值序信息系统，并研究了相应的属性约简和规则提取方法。陈曼如等 [7] 引入属性无关性和保序性的相关定义，在集值决策系统中提出了快速正域约简的启发式方法。

广义决策的概念由Skowron [8] 提出。Zhang等 [9] 提出了一种新的广义决策保持的相似度的概念，并在此基础上提出了前向启发式约简算法和后向启发式约简算法。唐玉凯等 [10] 在不完备决策系统中提出了基于多特定类的广义决策属性约简的理论框架，并设计了相关算法。最短约简是保证与原系统具有相同分类能力和表达能力的最小属性子集，能最大限度的删除不相关的属性，是包含属性数目最少的属性约简。Zhou等 [11] 分析了差别函数中属性出现的次数与最短约简之间的关系，在差别函数的基础上提出了精确计算决策系统最短约简的算法。Yanir等 [12] 提出了一种通过剪枝策略高效获取最短约简的算法，该算法能得到决策系统的所有最短约简。由于决策者偏好不同或需求变化，在某些场景下，针对特定决策类的属性约简更有意义。Yao等 [13] 提出了基于特定类正域约简的概念。

现有的广义决策约简大都针对决策系统的所有决策类，在集值决策系统中未见有对基于特定类广义决策最短约简的研究。本章在基于相容关系的集值决策系统中给出了特定类广义决策约简的概念，并且结合Zhou [11] 所提出的最短约简算法，设计了基于特定类的广义决策最短约简算法。

2. 基本概念

本节介绍基于相容粗糙集模型的集值决策系统的相关知识。

定义1. [5] 给定一个集值决策系统 $SVDS=\left(OB,AT=C\cup D,V,F\right)$ ， $OB=\left\{x_1,x_2,\cdot \cdot \cdot ,x_n\right\}$ 表示对象的集合，称为论域； $AT=\left\{b_1,b_2,\cdot \cdot \cdot ,b_m\right\}$ 表示条件属性的集合； $D=\left\{d\right\}$ 表示决策属性集合；V表示属性的值域，满足 $V={\displaystyle {\cup }_{b\in AT}{V}_b}$ ，其中 $V_b$ 表示为条件属性 $b\in AT$ 的值域； $F:OB\times AT\to V$ 表示OB在AT上的映射函数。

集值决策系统如表1所示。

表1. 集值决策系统

定义2. [5] 在集值决策系统 $SVDS=\left(OB,C\cup D,V,F\right)$ 中， $\forall B\subseteq C$ ，对于 $\forall x,y\in OB$ ，B的相容关系定义为：

$T_B=\left\{\left(x,y\right)\in OB\times OB|\forall b\in B,b\left(x\right)\cap b\left(y\right)\ne \varnothing \right\}$ 。 (1)

相容关系满足自反、对称和非传递性，且 $T_B={\displaystyle {\cap }_{b\in B}{T}_b}$ 。相容关系在论域OB上导出的划分形成论域的覆盖。

定义3. [5] 在集值决策系统 $SVDS=\left(OB,C\cup D,V,F\right)$ 中， $B\subseteq C$ ， $\forall x\in OB$ ，对象x在属性集B上的相容类定义为：

$T_B\left(x\right)=\left\{y\in OB|\left(x,y\right)\in T_B\right\}$ (2)

定义4. [14] 在集值决策系统 $SVDS=\left(OB,C\cup D,V,F\right)$ 中， $B\subseteq C$ ，对于 $\forall x\in OB$ ， $d\left(x\right)$ 表示对象x的决策值，对象x关于B的广义决策定义为：

$\vartheta \left(x|B\right)=\left\{d\left(y\right)|y\in T_B\left(x\right)\right\}$ 。 (3)

$\vartheta \left(x|B\right)$ 表示x的等价类中对象决策值集合；则在论域OB中，所有对象的广义决策构成的集合为 $\vartheta \left(B\right)=\left\{\vartheta \left(x_1|B\right),\vartheta \left(x_2|B\right),\cdot \cdot \cdot ,\vartheta \left(x_n|B\right)\right\}$ ，其中 $n=\left|OB\right|$ 。

3. 基于差别矩阵的广义决策最短约简

本节以集值决策系统为数据背景，介绍基于差别矩阵的广义决策最短约简计算方法。

定义5. [14] 在集值决策系统 $SVDS=\left(OB,C\cup D,V,F\right)$ 中，若 $B\subseteq C$ 同时满足以下两个条件，则B是 $SVDS$ 的一个广义决策约简：

1) $\forall x\in OB$ ， $\vartheta \left(x|B\right)=\vartheta \left(x|C\right)$ ；

2) 对 $\forall B^{\prime }\in B$ ， $\exists x^{\prime }\subseteq OB$ ，使 $\vartheta \left(x^{\prime }|B^{\prime }\right)\ne \vartheta \left(x^{\prime }|C\right)$ 。

在定义5中，第一个条件保证了约简前后决策系统的广义决策 $\vartheta \left(x|C\right)$ 不发生改变，即约简的联合充分性；第二个条件保证了约简中每一个属性都是不可缺少的，即约简的个体必要性。

定义6. [14] 在集值决策系统 $SVDS=\left(OB,C\cup D,V,F\right)$ 中，决策类集合 ${\pi }_D=\left\{D_1,D_2,\cdots ,D_m\right\}$ $\left(1\le m\le \left|{\pi }_D\right|\right)$，对于 $\forall x,y\in U$ ， $SVDS$ 广义决策约简对应的差别矩阵定义为 $M={\left(M\left(x,y\right)\right)}_{\left|OB\times OB\right|}$ ， $M\left(x,y\right)$ 表示为：

$M\left(x,y\right)=\{\begin{array}{ll}\left\{b\in C|b\left(x\right)\cap b\left(y\right)=\varnothing \right\},\hfill & y\in \Pi \hfill \\ \varnothing ,\hfill & \text{otherwise}\hfill \end{array}$ (4)

其中 $\Pi =\left\{z\in OB|d\left(z\right)\notin \vartheta \left(x|C\right)\right\}$ 。

定义7. [14] 在集值决策系统 $SVDS=\left(OB,C\cup D,V,F\right)$ 中， $M={\left(M\left(x,y\right)\right)}_{\left|OB\times OB\right|}$ 表示 $SVDS$ 广义决策约简所对应差别矩阵，则由差别矩阵导出的差别函数定义为：

$D{F}_{gd}=\wedge \left\{\vee M_{gd}\left(x,y\right)|M_{gd}\left(x,y\right)\ne \varnothing \right\}$ 。 (5)

Zhou在文献 [11] 中提出了一种最短约简的算法CAMARDF算法，该算法根据差别函数的拓展律，提出了多种搜索方法，能高效地计算出决策系统的最短约简。本节根据文献 [11] [14] ，以集值决策系统为数据背景，引入CAMARDF算法计算决策系统的最短约简，给出集值决策系统中基于差别矩阵的广义决策最短约简算法，算法步骤如表2所示。

表2. 基于差别矩阵的广义决策最短约简算法(GRM)

文献 [11] 中总结了13中不同的约简目标，Miao在文献 [15] 给出了差别矩阵的广义定义，当给定一个约简目标由矩阵的广义定义可以得到差别矩阵具体的定义，因此可以将表2算法中的广义决策替换为正域得到基于差别矩阵的正域最短约简算法(PRM)。

4. 基于特定的广义决策最短约简

现有的广义决策约简需要所有决策类的参与，而某些场景下，只关注某一个特定的决策类更具有针对性，既满足偏好，又能压缩差别矩阵的空间，减少计算属性约简所需要的时间。针对以上问题，本文以广义决策为约简目标，研究特定类的属性约简方法，并将CAMARDF算法引入到特定类的属性约简方法中，以高效地获取决策系统的最短约简。

定义8. 在集值决策系统 $SVDS=\left(OB,C\cup D,V,F\right)$ 中， ${\pi }_D=\left\{D_1,D_2,\cdots ,D_m\right\}$ $\left(1\le m\le \left|{\pi }_D\right|\right)$，对于 $\forall D_{msc}\subseteq {\pi }_D$ ， $\forall B\subseteq C$ ，若B同时满足以下两个条件，则B是 $D_{msc}$ 的广义决策约简：

1) $\forall x\in \left\{z\in OB|V_{msc}\cap \vartheta \left(z|C\right)\ne \varnothing \right\}$ ，有 $\vartheta \left(x|B\right)=\vartheta \left(x|C\right)$ ；

2) 对 $\forall B^{\prime }\subset B$ ， $\exists x^{\prime }\in \left\{z\in OB|V_{msc}\cap \vartheta \left(z|C\right)\ne \varnothing \right\}$ ，使 $\vartheta \left(x^{\prime }|B^{\prime }\right)\ne \vartheta \left(x^{\prime }|C\right)$ 。

其中 $V_{msc}$ 表示特定类 $D_{msc}$ 决策值的集合，即 $V_{msc}=\left\{d\left(x\right)|x\in D_{msc}\right\}$ 。

第一个条件保证了约简的联合充分性，即约简前后，多特定类的广义决策 $\vartheta \left(x|C\right)$ 保持不变；第二个条件保证了约简的个体必要性，即得到的约简中每一个属性都是不可缺少的。

定义9. 在集值决策系统 $SVDS=\left(OB,C\cup D,V,F\right)$ 中， ${\pi }_D=\left\{D_1,D_2,\cdots ,D_m\right\}$ ，对于 $\forall D_{msc}\subseteq {\pi }_D$ ， $V_{msc}$ 表示 $D_{msc}$ 决策值的集合 $\forall x,y\in OB$ ，SVDS多特定类 $D_{msc}$ 的广义决策约简所对应的差别矩阵定义为 $M_{msc}={\left(M_{msc}\left(x,y\right)\right)}_{\left|OB\times OB\right|}$ ， $M_{msc}\left(x,y\right)$ 表示为：

$M_{msc}\left(x,y\right)=\{\begin{array}{ll}\left\{b\in C|b\left(x\right)\cap b\left(y\right)=\varnothing \right\},\hfill & \left(x,y\right)\in {\Pi }_{msc}\hfill \\ \varnothing ,\hfill & \text{otherwise}\hfill \end{array}$ ， (6)

其中 ${\Pi }_{msc}=\left\{\left(x,y\right)|x,y\in OB,V_{msc}\cap \vartheta \left(x|C\right)\ne \varnothing \wedge d\left(y\right)\notin \vartheta \left(x|C\right)\right\}$ 。

定义10. 在集值决策系统 $SVDS=\left(OB,C\cup D,V,F\right)$ 中， ${\pi }_D=\left\{D_1,D_2,\cdots ,D_m\right\}$ ，对于 $\forall D_{msc}\subseteq {\pi }_D$ ， $M_{msc}={\left(M_{msc}\left(x,y\right)\right)}_{\left|OB\times OB\right|}$ 是 $D_{msc}$ 广义决策约简对应的差别矩阵，则由差别矩阵导出的差别函数定义为：

$D{F}_{msc}=\wedge \left\{\vee M_{msc}\left(x,y\right)|M_{msc}\left(x,y\right)\ne \varnothing \right\}$ 。 (7)

根据特定类广义决策约简的定义、差别矩阵及差别函数的定义，给出在集值决策系统中基于特定类广义决策最短约简算法，算法具体步骤如表3所示。

表3. 基于特定类的广义决策最短约简算法(MGRM)

多特定类约简方法实际是单特定类约简方法的推广，而单特定类约简方法可看作是多特定类约简方法的特例，将表3多特定类替换为单特定类即可得单特定类算法(SGRM)。

5. 实验分析

本节将从约简结果对比、差别矩阵空间占用对比及约简效率对比三个部分进行实验验证，并对实验结果进行分析。实验选择单个特定类是使用SGRM算法，选择多个特定类是选择MGRM算法。实验环境为：Windows 10 64bit操作系统，Inter Core i5-6300 (3.2 GHz) CPU，内存8 GB；算法使用Python在Pycharm中完成。

实验选用8组UCI标准数据集(http://archive.ics.uci.edu/ml/)对所提出的算法进行验证，数据集描述如表4所示。部分数据集含有缺失值，对于数值类型的数据，缺失值用平均值代替，对于离散型数据，缺失值使用出现次数最多的值代替。为了得到实验所使用的集值数据集，需要对8组数据进行预处理，预处理过程分为以下几个步骤：首先将条件属性离散化；其次将名词性数据替换为整数表示；最后根据文献 [7] 的方法，在条件属性上随机选取10%的数据在对应的属性列上进行并集操作。

表4. UCI数据

5.1. 约简结果的对比

所选取8组UCI数据集的约简结果及约简长度如表5所示。表中左侧“序号”表示数据集的序号，与表4中数据集名称和序号对应。表中“GRM”表示GRM算法在所有决策类下的约简结果；表中“SGRM”表示的是SGRM算法选择单个决策类时的约简结果；“MGRM”表示的是MGRM算法选择多个决策类时的约简结果；“RR”表示约简结果，“RL”表示约简的长度，将所选择决策类的约简长度以及约简结果在表中一一列出。

表5. 约简个数与平均约简长度对比

5.2. 差别矩阵中非空项的占比

本节在8组数据集上，通过统计PRM算法、GRM算法、SGRM算法和MGRM算法在构造差别矩阵时非空差别项的个数，进而对比四种算法所构造差别矩阵的非空差别项所占比例，实验结果如图1所示。图中横坐标表示8组数据集的序号，其序号于表4中数据集名称和序号对应；纵坐标表示非空差别项占比。图中“GRM”表示GRM算法在所有决策类下的约简结果；“PRM”表示正域最短约简算法在所有决策类下的结果；“SGRM”表示的是SGRM算法选择单个决策类时的结果，“MGRM”表示的是MGRM算法选择多个决策类时的约简结果。

图1. 非空差别项占比

5.3. 约简效率的对比

为了验证本章所提出算法的有效性，8组UCI数据集以论域增加的方式做对比实验，实验结果如图2。论域递增时，数据集被平均分成十份，实验时逐次增加一份作为时间测试数据集，即第1份作为第一次测试数据集，第1份和第2份作为第二次测试数据集，以此类推，第十次测试使用完整的数据集。

图2. 约简效率的对比

图2所示曲线中横坐标均表示论域大小，纵坐标表示约简耗时，图中蓝色三角折线表示的是GRM算法计算最短约简所消耗的时间，棕色星型折线表示的是PRM算法计算最短约简所消耗的时间，红色圆形折线表示的是SGRM算法计算最短约简所消耗的时间，绿色圆形折线表示的是MGRM算法计算最短约简所消耗的时间。

6. 总结

本章对集值决策系统进行研究，讨论特定类广义决策最短约简方法，在集值决策系统中提出了基于特定类广义决策最短约简的理论框架，提出了特定类广义决策最短约简算法。实验部分选用了8组UCI数据集，将SGRM算法在约简结果、非空差别项占比以及约简效率三个方面进行实验，经过对比分析可得所提出的特定类算法得到的最短约简长度更短、差别矩阵中非空差别项占比更少并且时间效率更高。

本文使用了差别矩阵的方法求取决策系统的属性约简，提出了特定类广义决策最短约简算法，因此在集值决策系统下探索其他约简目标的属性约简方法是未来的研究方向之一。

基金项目

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

文章引用

胡德杰. 集值系统基于特定类的广义决策最短约简
The Minimal Attribute Reduction Algorithm of General Decision Based on Class-Specific in Set-Value Decision Systems[J]. 计算机科学与应用, 2023, 13(05): 1065-1073. https://doi.org/10.12677/CSA.2023.135104

参考文献