属性集变化下序决策信息系统的增量属性约简算法

doi:10.13232/j.cnki.jnju.2023.05.009

属性集变化下序决策信息系统的增量属性约简算法

张义宗¹^,², 王磊^,¹^,², 徐阳¹^,²

1.南昌工程学院信息工程学院，南昌，330099

2.江西省水信息协同感知与智能处理重点实验室，南昌，330099

Incremental attribute reduction algorithm for ordered decision information systems with the change of attribute set

Zhang Yizong¹^,², Wang Lei^,¹^,², Xu Yang¹^,²

1.School of Information Engineering，Nanchang Institute of Technology，Nanchang，330099，China

2.Jiangxi Province Key Laboratory of Water Information Cooperative Sensing and Intelligent Processing，Nanchang，330099，China

通讯作者: E⁃mail：ezhoulei@163.com

收稿日期: 2023-07-03

基金资助:

国家自然科学基金. 61562061
江西省教育厅科技项目. GJJ2202005. GJJ211920

Received: 2023-07-03

摘要

当序决策信息系统中的属性集不断变化时，基于优势关系的现有静态算法无法高效地更新其属性约简，为此，从属性增加和属性删除两个角度出发，以知识粒度表征的属性重要度为启发信息，提出两种新的增量属性约简算法.首先介绍优势粗糙集方法的相关基础知识，并将经典粗糙集中基于知识粒度的属性约简算法扩展到优势粗糙集方法，得到可处理序决策信息系统的属性约简算法；然后，给出劣势属性矩阵的定义，并基于知识粒度的矩阵计算方法分析属性增删时属性约简的增量式更新机制，进一步设计了两种增量属性约简算法.最后，分析比较三种算法的时间复杂度，选取了六个不同的UCI数据集进行算法性能的测试，结果表明，提出的算法比静态的属性约简算法更高效.

关键词： 序决策信息系统 ; 知识粒度 ; 优势粗糙集方法 ; 劣势属性矩阵 ; 增量属性约简

Abstract

When attribute set in the ordered decision information system is constantly changing，existing static algorithms that have been studied based on dominance relationship cannot efficiently update its attribute reduction. To this end，this paper proposes two new incremental attribute reduction algorithms from the perspective of both attribute addition and attribute deletion，respectively，using the attribute importance of knowledge granularity representations as the heuristic information. Firstly，the relevant basic knowledge of the dominance rough set method are introduced，and the attribute reduction algorithm based on knowledge granularity in the classical rough set is extended to the dominance rough set method to obtain an attribute reduction algorithm that can handle ordered decision information systems; Then，the definition of the inferior attribute matrix is given，and the incremental update mechanism of attribute reduction during attribute addition and deletion is analyzed by the matrix calculation method of knowledge granularity. From there，two incremental attribute reduction algorithms are further designed; Finally，time complexity of the three algorithms is analyzed and compared，and six different UCI datasets are selected to test the algorithm performance. The test results show that the algorithm proposed in this paper is more efficient than the static attribute reduction algorithm.

Keywords： ordered decision information system ; knowledge granularity ; the dominance rough set approach ; inferior attribute matrix ; incremental attribute reduction

PDF (1210KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

张义宗, 王磊, 徐阳. 属性集变化下序决策信息系统的增量属性约简算法. 南京大学学报（自然科学）[J], 2023, 59(5): 813-822 doi:10.13232/j.cnki.jnju.2023.05.009

Zhang Yizong, Wang Lei, Xu Yang. Incremental attribute reduction algorithm for ordered decision information systems with the change of attribute set. Journal of nanjing University[J], 2023, 59(5): 813-822 doi:10.13232/j.cnki.jnju.2023.05.009

粗糙集理论是1982年波兰数学家Pawlak^［1］提出的一种能够有效处理带有不确定性、模糊性、不精确性数据的数学工具，由于其解决实际问题的有效性，被大量应用于机器学习^［2-3］、模式识别^［4］、数据挖掘^［5］和知识发现^［6］等领域.属性约简是粗糙集理论中的核心与热点研究问题之一，旨在找出与决策信息系统分类能力一致的属性子集，达到决策信息系统属性降维的目的.

经典粗糙集理论以等价关系对论域进行划分形成的等价类为研究基础，但其不适合处理属性值具有偏序关系的数据.为此，Greco et al^［7-8］基于优势关系对经典粗糙集方法进行推广，提出优势粗糙集方法（Dominance Rough Set Approach，DRSA），而DRSA近似集的运算对象是决策类的上（下）向联合集，由此给出了上（下）向联合集的上、下近似集的定义.此后，众多学者对优势粗糙集方法进行了一系列的研究和推广.李艳等^［9］深入研究了不协调目标信息系统的属性约简，在优势关系上给出了浓缩布尔矩阵的概念来计算属性约简.Li et al^［10］针对区间值序信息系统提出一种基于优势关系的特征选择（属性约简）方法.Du and Hu^［11］针对一致不完备序信息系统的属性约简问题，基于可分辨矩阵和可分辨函数，提出一种计算所有属性约简的方法.Yang et al^［12］将优势关系拓展到区间值决策系统上，提出基于α⁃优势的粗糙集模型，并给出了上、下近似的计算方法.Zhang and Yang^［13］将α⁃优势推广至集值信息系统，结合合取和析取给出了两种新的优势关系，并基于此提出集值决策表的特征选择（属性约简）方法.以上研究均是对优势粗糙集模型的扩展和推广，可解决不同类型数据集的属性约简问题.

然而，实际生活中数据的属性集会发生动态变化，相应的属性约简结果也随之变化，使用非增量属性约简算法对属性集动态变化的数据进行属性约简是不可行的，因为这会重复计算未变动前的部分属性，增加计算成本，在大数据集上甚至无法满足其属性约简的效率要求.因而，众多学者针对属性集动态变化的序决策信息系统展开了一系列研究，如Luo et al^［14］将知识粒度引入序集值决策信息系统，对系统中属性增加和删除的情况，基于矩阵提出一种增量更新近似集的方法.Wang et al^［15］针对有序信息系统多维变化的动态更新近似集的问题，基于矩阵提出一种可以在对象和属性同时增加的情况下有效更新的增量方法.Huang et al^［16］将近似集的布尔矩阵表示方法引入动态模糊信息系统，考虑属性和对象增加的情况，通过更新布尔矩阵达到动态更新近似集的目的.Sang et al^［17］将条件熵引入序决策信息系统，在系统中添加或删除多个对象时，基于矩阵提出两种增量属性约简算法，还针对动态变化的有序模糊信息系统的特征选择（属性约简）问题，提出一种新的模糊优势邻域粗糙集模型，并基于条件熵提出一种启发式增量特征选择（属性约简）算法^［18］.上述研究推动了序决策信息系统近似集的动态更新在众多领域的发展，但是，针对属性集动态变化的序决策信息系统，基于矩阵计算其属性约简的增量算法并不常见.

本文以序决策信息系统为研究对象，首先将王磊和李天瑞^［19］的知识粒度的矩阵表示与计算方法推广到序决策信息系统中，同时，将经典粗糙集中以知识粒度表征的属性重要度为启发信息的属性约简方法引入优势粗糙集方法，作为本文的非增量对照实验算法.然后，以矩阵分析序决策信息系统中知识粒度、劣势元素矩阵和优势关系矩阵在属性数目变化条件下的变化过程，并给出属性增删条件下属性约简的增量更新机制，基于此提出两种新的增量属性约简算法.最后，在UCI数据集上测试了属性约简算法的性能，实验结果证实了本文提出的增量属性约简算法的可行性和高效性.

本文提出的劣势元素矩阵和优势关系矩阵的增量更新机制能降低属性约简子集选取属性的计算成本，进一步增加算法的增量属性约简效率，同时，其不仅适用于序决策信息系统，还可扩展到其他模型的属性约简算法.究其本质，劣势元素矩阵和优势关系矩阵的增量更新机制的提出，给出了基于满足模型关系和不满足模型关系相结合的属性约简方法.

1 基本知识

首先介绍优势粗糙集方法的相关基础知识，然后，将知识粒度的矩阵表示与计算方法扩展到优势粗糙集方法中，介绍了以知识粒度为启发信息的启发式属性约简算法.

1.1　优势粗糙集方法的相关基础知识

定义1

决策信息系统 $S = (U, A = C ⋃ D,$

$V, f)$ ，其中，U为非空有限对象集合， $U = \{x_{1},$

$x_{2}, \dots, x_{m}\}$ ；A是一个有限非空属性集，C是条件属性集，D是决策属性集，并且 $C ⋂ D = \emptyset$ ；对于 $\forall a \in A$ ，均存在a的一个属性值集 $V_{a}$ ， $V = ⋃ V_{a}$ 为属性集A的属性值集；f为信息系统的信息函数，能给出属性集A在U上的属性值集.若属性值集V具有偏序关系，则称该系统为序决策信息系统.

定义2

给定一个序决策信息系统 $S = (U,$

$A = C ⋃ D, V, f)$ ，对于 $\forall P \subseteq C$ 均会确定一个优势关系 $R_{P}^{\leq}$ ，表示为：

R_{P}^{\leq} = \{(x_{i}, x_{j}) \in U \times U| \forall a \in P, f (x_{i}, a) \leq f (x_{j}, a)\}

(1)

此外，对于 $\forall P \subseteq C$ 也会确定一个劣势关系 $R_{P}^{>}$ ，可表示为：

R_{P}^{>} = \{(x_{i}, x_{j}) \in U \times U| \forall a \in P, f (x_{i}, a) > f (x_{j}, a)\}

(2)

其中， $f (x_{i}, a)$ 为对象 $x_{i}$ 在属性a上的属性值， $f (x_{j}, a)$ 为对象 $x_{j}$ 在属性a上的属性值.

定义3

给定一个序决策信息系统 $S = (U,$

$A = C ⋃ D, V, f), P \subseteq C$ ，那么属性子集P在U上的优势关系矩阵为 $M_{U}^{R_{P}^{\leq}}$ . $R (i, j)$ 表示 $M_{U}^{R_{P}^{\leq}}$ 第i行第j列的元素，其值为：

R (i, j) = \{\begin{matrix} 1, f (x_{i}, a) \leq f (x_{j}, a), \forall a \in P \\ 0, f (x_{i}, a) > f (x_{j}, a), \exists a \in P \end{matrix}

(3)

定义4

$S = (U, A = C ⋃ D, V, f), P \subseteq C,$ 则属性集 $P ⋃ D$ 在U上的优势关系矩阵为 $M_{U}^{R_{P ⋃ D}^{\leq}}$ . $R (i, j)$ 表示 $M_{U}^{R_{P ⋃ D}^{\leq}}$ 第i行第j列的元素，其值为：

\begin{array}{l} R (i, j) = \\ \{\begin{matrix} \begin{array}{l} 1, f (x_{i}, a) \leq f (x_{j}, a) \land f (x_{i}, d) = f (x_{j}, d), \\ \forall a \in P \end{array} \\ 0, 其他 \end{matrix} \end{array}

(4)

定义5

给定一个序决策信息系统 $S = (U,$

$A = C ⋃ D, V, f), P \subseteq A,$ 那么P的知识粒度记为 $G K (P)$ ，定义为：

G K (P) = \frac{\sum_{i = 1}^{|U|} \sum_{j = 1}^{|U|} R (i, j)}{{|U|}^{2}} = m e a n (M_{U}^{R_{P}^{\leq}})

(5)

其中， $m e a n (M_{U}^{R_{P}^{\leq}})$ 为优势关系矩阵 $M_{U}^{R_{P}^{\leq}}$ 的算术平均值.

定义6

$S = (U, A = C ⋃ D, V, f), P, Q \subseteq A,$

知识Q关于知识P在U上的相对知识粒度为 $G K (Q| P)$ ，可表示为：

\begin{array}{l} G K (Q| P) = G K (P) - G K (P ⋃ Q) = \\ m e a n (M_{U}^{R_{P}^{\leq}}) - m e a n (M_{U}^{R_{P ⋃ Q}^{\leq}}) \end{array}

(6)

定义7

$S = (U, A = C ⋃ D, V, f), P \subseteq C,$

$\forall a \in C - P$ ，那么属性a相对于属性集P的外部属性重要度可定义为：

\begin{array}{l} S i g_{U}^{o u t e r} (a, P, D) = m e a n (M_{U}^{R_{P}^{\leq}}) - m e a n (M_{U}^{R_{P ⋃ D}^{\leq}}) - \\ m e a n (M_{U}^{R_{P ⋃ \{a\}}^{\leq}}) + m e a n (M_{U}^{R_{P ⋃ \{a\} ⋃ D}^{\leq}}) \end{array}

(7)

同理，若 $\forall a \in P$ ，属性a相对于属性集P的内部属性重要度可定义为：

\begin{array}{l} S i g_{U}^{i n n e r} (a, P, D) = m e a n (M_{U}^{R_{P - \{a\}}^{\leq}}) - m e a n (M_{U}^{R_{P - \{a\} ⋃ D}^{\leq}}) - \\ m e a n (M_{U}^{R_{P}^{\leq}}) + m e a n (M_{U}^{R_{P ⋃ D}^{\leq}}) \end{array}

(8)

定义8

$S = (U, A = C ⋃ D, V, f), R \subseteq C, R$ 是条件属性集C相对于决策属性集D的一个属性约简，则R必须满足以下两个条件：

（1） $G K (D| R) = G K (D| C)$ ；

（2） $\forall a \in R, 使得 G K (D |R - \{a\}) \neq G K (D| C)$ .

1.2　优势粗糙集方法中的启发式非增量属性约简算法

根据Jing et al^［20］的经典粗糙集中基于知识粒度的属性约简算法，将其引入优势粗糙集方法，构造以知识粒度表征的属性重要度为启发信息的属性约简算法，如算法1所示.

算法1

优势关系下基于知识粒度的属性约简算法（Attribute Reduction Algorithm Based on Knowledge Granularity under Dominance Relationship，ARKG⁃DR）

输入：序决策信息系统 $S = (U, A = C ⋃ D, V, f) .$

输出：一个属性约简RED.

步骤1.计算 $G K (D| C)$ .

步骤2.初始化 $R E D \leftarrow \emptyset, R E D_P o o l \leftarrow C$ .

步骤3.对于 $\forall a \in C$ ，计算 $S i g_{U}^{i n n e r} (a, C, D)$ ，如果 $S i g_{U}^{i n n e r} (a, C, D) > 0$ ，则 $R E D \leftarrow R E D ⋃ \{a\}, R E D_P o o l \leftarrow$

R E D_P o o l - \{a\}

步骤4.计算 $G K (D| R E D)$ ，如果 $G K (D| C) = G K (D| R E D)$ ，则转至步骤8，否则转至步骤5.

步骤5.对于 $\forall a \in R E D_P o o l$ ，计算 $S i g_{U}^{o u t e r} (a, R E D, D)$ ，

得出 $S i g_{U}^{o u t e r} (a_{m}, R E D, D) = m a x (S i g_{U}^{o u t e r} (a, R E D, D))$ ，则 $R E D \leftarrow R E D ⋃ \{a_{m}\}, R E D_P o o l \leftarrow R E D_P o o l - \{a_{m}\}$ .

步骤6.计算更新后的 $G K (D| R E D)$ ，若 $G K (D| C) =$

$G K (D| R E D)$ ，则转至步骤5，否则转至步骤7.

步骤7.对于 $\forall a \in R E D$ ，如果 $G K (D| C) = G K (D |R E D - \{a\})$ ，则 $R E D \leftarrow R E D - \{a\}$ .

步骤8.输出属性约简结果RED.

然而，对属性集动态变化的数据集进行属性约简时，算法1会重新计算变化后的数据集，这会重复计算上次的属性约简结果，极大地提升属性集动态变化数据集的属性约简时间复杂度.此外，在步骤5和步骤7中增加或者删除某个属性后，需要重新计算更新对应的优势关系矩阵，重新判断对象在未变化属性上的优势关系，很大程度上降低了算法属性约简的效率.针对这些问题，本文研究了属性集变化下属性约简的增量更新机制，包括知识粒度的矩阵增量更新方法、优势关系矩阵的增量更新方法和劣势元素矩阵的增量更新方法，基于此设计了启发式增量属性约简算法.

2 属性集变化下序决策信息系统的增量属性约简算法

为了提高属性集动态变化的数据集的属性约简效率，通过矩阵分析序决策信息系统中知识粒度在属性数目变化条件下的增量更新机制，进一步分析优势关系矩阵和劣势元素矩阵的增量更新机制，最后在属性集增加和属性集删除的条件下，分别设计了两种启发式增量属性约简算法.

2.1　属性集增加条件下的增量更新机制

定义9

给定一个序决策信息系统 $S = (U,$

$A = C ⋃ D, V, f), P \subseteq A, M_{U}^{R_{P}^{\leq}} = {(M_{i j}^{R_{P}^{\leq}})}_{|U| \times |U|}$ 是属性集P在论域U上的优势关系矩阵.假设Q是新增的属性集， $M_{U}^{R_{Q}^{\leq}} = {(M_{i j}^{R_{Q}^{\leq}})}_{|U| \times |U|}$ 是属性集Q在论域U上的优势关系矩阵，那么P上的增量关系矩阵为 $Δ M_{U}^{R_{P}^{\leq}}$ ，表示为：

Δ M_{U}^{R_{P}^{\leq}} = {(r_{i j})}_{|U| \times |U|} = \{\begin{matrix} 1, M_{i j}^{R_{P}^{\leq}} = 1 且 M_{i j}^{R_{Q}^{\leq}} = 0 \\ 0, 其他 \end{matrix}

(9)

根据文献［19］可知，数据集 $P ⋃ Q$ 的优势关系矩阵 $M_{U}^{R_{P ⋃ Q}^{\leq}}$ 是在数据集P的优势关系矩阵 $M_{U}^{R_{P}^{\leq}}$ 上变化而来，增加属性集Q只会令 $M_{U}^{R_{P}^{\leq}}$ 中的1变为0，对应变化的位置会标记为1，从而构成了P的增量关系矩阵.

定理1

给定一个序决策信息系统 $S = (U,$

$A = C ⋃ D, V, f), P \subseteq C, Q$ 是新增的属性集， $G K (P)$ 为属性集P的知识粒度，那么新增属性集后更新的知识粒度为：

\begin{array}{l} G K (P ⋃ Q) = m e a n (M_{U}^{R_{P ⋃ Q}^{\leq}}) = \\ G K (P) - m e a n (Δ M_{U}^{R_{P}^{\leq}}) \end{array}

(10)

定理2

给定一个序决策信息系统 $S = (U,$

$A = C ⋃ D, V, f), P \subseteq C, Q$ 是新增的属性集， $G K (D| P)$ 为属性集P相对于属性集D的相对知识粒度，则新增属性集后更新的相对知识粒度为：

\begin{array}{l} G K (D |P ⋃ Q) = \\ G K (D |P) - m e a n (Δ M_{U}^{R_{P}^{\leq}}) + m e a n (Δ M_{U}^{R_{P ⋃ D}^{\leq}}) \end{array}

(11)

证明如下：

\begin{array}{l} G K (D |P ⋃ Q) = G K (P ⋃ Q) - G K (P ⋃ Q ⋃ D) = \\ m e a n (M_{U}^{R_{P ⋃ Q}^{\leq}}) - m e a n (M_{U}^{R_{P ⋃ Q ⋃ D}^{\leq}}) = \\ G K (P) - m e a n (Δ M_{U}^{R_{P}^{\leq}}) - \\ G K (P ⋃ D) + m e a n (Δ M_{U}^{R_{P ⋃ D}^{\leq}}) = \\ G K (D |P) - m e a n (Δ M_{U}^{R_{P}^{\leq}}) + m e a n (Δ M_{U}^{R_{P ⋃ D}^{\leq}}) \end{array}

定理3

给定一个序决策信息系统 $S = (U,$

$A = C ⋃ D, V, f), P \subseteq C, Q$ 是新增的属性集， $\forall a \in$

$(C - P) ⋃ Q, S i g_{U}^{o u t e r} (a, P, D)$ 为属性a相对于属性集P关于属性集D的外部重要度，可表示为：

\begin{array}{l} S i g_{U}^{o u t e r} (a, P, D) = G K (D |P) - G K (D |P ⋃ \{a\}) = \\ m e a n (Δ M_{U}^{R_{P}^{\leq}}) - m e a n (Δ M_{U}^{R_{P ⋃ D}^{\leq}}) \end{array}

(12)

证明如下：

\begin{array}{l} S i g_{U}^{o u t e r} (a, P, D) = G K (D |P) - G K (D |P ⋃ \{a\}) = \\ G K (D |P) - G K (D |P) + \\ m e a n (Δ M_{U}^{R_{P}^{\leq}}) - m e a n (Δ M_{U}^{R_{P ⋃ D}^{\leq}}) = \\ m e a n (Δ M_{U}^{R_{P}^{\leq}}) - m e a n (Δ M_{U}^{R_{P ⋃ D}^{\leq}}) \end{array}

定义10

$S = (U, A = C ⋃ D, V, f), P \subseteq A,$

Q是新增的属性集， $M_{U}^{R_{P}^{\leq}} = {(M_{i j}^{R_{P}^{\leq}})}_{|U| \times |U|}$ 是属性集P在论域U上的优势关系矩阵， $Δ M_{U}^{R_{P}^{\leq}} = {(r_{i j})}_{|U| \times |U|}$ 是增加属性集Q后增量关系矩阵，那么属性集 $P ⋃ Q$ 的优势关系矩阵 $M_{U}^{R_{P ⋃ Q}^{\leq}}$ 中的元素 $M_{i j}^{R_{P ⋃ Q}^{\leq}}$ 可表示为：

M_{i j}^{R_{P ⋃ Q}^{\leq}} = \{\begin{matrix} 1, M_{i j}^{R_{P}^{\leq}} = 1 且 r_{i j} = 0 \\ 0, 其他 \end{matrix}

(13)

2.2　属性集删除条件下的增量更新机制

定义11

给定一个序决策信息系统 $S = (U,$

A = C ⋃ D, V, f), P \subseteq C, P = \{c_{1}, c_{2}, \dots, c_{n}\} (n \leq

$|C|), \forall x_{i}, x_{j} \in U,$ 那么，U在P上的劣势属性矩阵为 $M_{U}^{R_{P}^{>}}$ ， $M_{i j}^{R_{P}^{>}}$ 是 $M_{U}^{R_{P}^{>}}$ 第i行第j列的元素，其本质是一个条件属性子集，表示为：

M_{i j}^{R_{P}^{>}} = \{c_{i} \in P |x_{i}, x_{j} \in U, f (x_{i}, c_{i}) > f (x_{j}, c_{i})\}

(14)

同理，U在P∪D上的劣势属性矩阵为 $M_{U}^{R_{P ⋃ D}^{>}}$ ， $M_{i j}^{R_{P ⋃ D}^{>}}$ 是 $M_{U}^{R_{P ⋃ D}^{>}}$ 第i行第j列的元素，其本质也是一个条件属性子集，表示为：

M_{i j}^{R_{P ⋃ D}^{>}} = \{\begin{matrix} \begin{array}{l} \{c_{i} \in P |x_{i}, x_{j} \in U, f (x_{i}, c_{i}) > f (x_{j}, c_{i})\}, \\ f (x_{i}, d) = f (x_{j}, d) \end{array} \\ P, f (x_{i}, d) \neq f (x_{j}, d) \end{matrix}

(15)

此外，当删除或者增加属性集Q时，U在属性集 $P - Q, P ⋃ D - Q, P ⋃ Q 和 P ⋃ Q ⋃ D$ 上的劣势属性矩阵元素都会发生相应的增量变化，具体表示为：

M_{i j}^{R_{A t t}^{>}} = \{\begin{matrix} M_{i j}^{R_{P}^{>}} - Q, P - Q \\ M_{i j}^{R_{P ⋃ D}^{>}} - Q, P ⋃ D - Q \\ M_{i j}^{R_{P}^{>}} ⋃ M_{i j}^{R_{Q}^{>}}, P ⋃ Q \\ M_{i j}^{R_{P ⋃ D}^{>}} ⋃ M_{i j}^{R_{Q ⋃ D}^{>}}, P ⋃ D ⋃ Q \end{matrix}

(16)

定义12

给定一个序决策信息系统 $S = (U,$

A = C ⋃ D, V, f), Q \subseteq P \subseteq A, M_{U}^{R_{P}^{\leq}} = {(M_{i j}^{R_{P}^{\leq}})}_{|U| \times |U|}

是属性集P在论域U上的优势关系矩阵， $M_{U}^{R_{P}^{>}} = {(M_{i j}^{R_{p}^{>}})}_{|U| \times |U|}$ 是属性集P在论域U上的劣势属性矩阵，假设Q是S删除的属性集 $(若 P 中包含 D, 那$

$么 |Q| < |P - D|)$ ，那么P上的增量关系矩阵为 $Δ M_{U}^{R_{P}^{\leq}}$ ，表示为：

Δ M_{U}^{R_{P}^{\leq}} = {(r_{i j})}_{|U| \times |U|} = \{\begin{matrix} 1, M_{i j}^{R_{P}^{\leq}} = 0 且 M_{i j}^{R_{P}^{>}} \subseteq Q \\ 0, 其他 \end{matrix}

(17)

根据文献［19］可知，数据集P-Q的优势关系矩阵 $M_{U}^{R_{P - Q}^{\leq}}$ 是在数据集P的优势关系矩阵 $M_{U}^{R_{P}^{\leq}}$ 上变化而来，删除属性集Q只可能令 $M_{U}^{R_{P}^{\leq}}$ 中的0变为1，对应变化的位置会标记为1，构成P的增量关系矩阵.

定理4

给定一个序决策信息系统 $S = (U,$

$A = C ⋃ D, V, f), Q \subseteq P \subseteq C, Q$ 是S删除的属性集， $G K (P)$ 为属性集P的知识粒度，那么新增属性集后更新的知识粒度为：

\begin{array}{l} G K (P - Q) = m e a n (M_{U}^{R_{P - Q}^{\leq}}) = \\ G K (P) + m e a n (Δ M_{U}^{R_{P}^{\leq}}) \end{array}

(18)

定理5

给定一个序决策信息系统 $S = (U,$

$A = C ⋃ D, V, f), Q \subseteq P \subseteq C, Q$ 是S删除的属性集， $G K (D| P)$ 为属性集P相对于属性集D的相对知识粒度，那么新增属性集后的相对知识粒度为：

\begin{array}{l} G K (D| P - Q) = G K (D| P) + \\ m e a n (Δ M_{U}^{R_{P}^{\leq}}) - m e a n (Δ M_{U}^{R_{P ⋃ D}^{\leq}}) \end{array}

(19)

证明过程与定理2的证明过程类似，略.

定理6

给定一个序决策信息系统 $S = (U,$

$A = C ⋃ D, V, f), Q \subseteq P \subseteq C, Q$ 是S删除的属性集， $\forall a \in (P - Q), S i g_{U}^{i n n e r} (a, P, D)$ 为属性a相对于属性集P关于属性集D的内部重要度，可表示为：

\begin{array}{l} S i g_{U}^{i n n e r} (a, P, D) = \\ G K (D |P - \{a\}) - G K (D| P) = \\ m e a n (Δ M_{U}^{R_{P}^{\leq}}) - m e a n (Δ M_{U}^{R_{P ⋃ D}^{\leq}}) \end{array}

(20)

证明过程与定理3的证明过程类似，略.

定义13

给定一个序决策信息系统 $S = (U,$

A = C ⋃ D, V, f), Q \subseteq P \subseteq A, M_{U}^{R_{P}^{\leq}} = {(M_{i j}^{R_{P}^{\leq}})}_{|U| \times |U|}

是属性集P在论域U上的优势关系矩阵， $Δ M_{U}^{R_{P}^{\leq}}$ 是删除属性集Q后的增量关系矩阵，则属性集 $P - Q$

的优势关系矩阵 $M_{U}^{R_{P - Q}^{\leq}}$ 中的元素 $M_{i j}^{R_{P - Q}^{\leq}}$ 可表示为：

M_{i j}^{R_{P - Q}^{\leq}} = \{\begin{matrix} 0, M_{i j}^{R_{P}^{\leq}} = 0 且 r_{i j} = 0 \\ 1, 其他 \end{matrix}

（21）

2.3　属性集变化条件下的增量属性约简算法

基于2.1和2.2的知识粒度和优势关系矩阵的增量更新机制，属性集变化下增量属性约简算法的过程主要分三个步骤：

（1）对属性集变化的数据集增量更新其相对知识粒度；

（2）向约简集中添加待约简集中外部属性重要度最大的属性；

（3）逐步向前删除约简集中的冗余属性，提高约简结果的准确性.

属性集变化下的增量属性约简算法如算法2和算法3所示.

算法2

优势关系下基于属性集增加的增量属性约简算法（Incremental Attribute Reduction Algorithm Based on Attribute Set Increase under Dominance Relations，IARAI⁃DR）

输入：序决策信息系统 $S = (U, A = C ⋃ D, V, f),$

$S$ 的属性约简 $R E D_{C}$ ，增加的属性集P，U在C， $C ⋃ D$ 上的劣势属性矩阵 $M_{U}^{R_{C}^{>}}, M_{U}^{R_{C ⋃ D}^{>}}$ 和优势关系矩阵 $M_{U}^{R_{C}^{\leq}}, M_{U}^{R_{C ⋃ D}^{\leq}}$ .

输出：序决策信息系统更新后的属性约简 $R E D_{C ⋃ P}$ .

步骤1.在计算优势关系矩阵 $M_{U}^{R_{P}^{\leq}}$ 的同时计算 $M_{U}^{R_{P}^{>}}$ ，根据定义9求出更新后的增量关系矩阵 $Δ M_{U}^{R_{C}^{\leq}}$ 和 $Δ M_{U}^{R_{C ⋃ D}^{\leq}}$ .

步骤2.根据定理2计算更新后的 $G K (D| C ⋃ P) .$

步骤3. $B \leftarrow R E D_{C}, R E D_P o o l \leftarrow C ⋃ P - R E D_{C} .$

步骤4.根据定理5计算 $G K (D |B)$ ，并根据定义13计算 $M_{U}^{R_{B}^{\leq}}, M_{U}^{R_{B ⋃ D}^{\leq}}$ ，若 $G K (D |B) = G K (D |C ⋃ P)$ ，则执行步骤7，否则执行步骤5.

步骤5.对于 $\forall a \in R E D_P o o l$ ，根据定理3计算 $S i g_{U}^{o u t e r} (a, B, D)$ ，取 $S i g_{U}^{o u t e r} (a_{m}, B, D) = m a x$

$(S i g_{U}^{o u t e r} (a, B, D)), R E D_P o o l \leftarrow R E D_P o o l - \{a_{m}\}, B \leftarrow$ $B ⋃ \{a_{m}\}$ ，同时根据定义10更新 $M_{U}^{R_{B}^{\leq}}$ 和 $M_{U}^{R_{B ⋃ D}^{\leq}}$ .

步骤6.若 $G K (D |C ⋃ P) = G K (D |B)$ ，则执行步骤7，否则执行步骤5.

步骤7.对于 $\forall a \in B$ ，根据定理6计算 $S i g_{U}^{i n n e r} (a, B, D)$ ，若 $S i g_{U}^{i n n e r} (a, B, D)$ =0，则 $B \leftarrow B - \{a\} .$

步骤8. $R E D_{C ⋃ P} \leftarrow B$ ，输出 $R E D_{C ⋃ P}$ .

算法3

优势关系下基于属性删除的增量属性约简算法（Incremental Attribute Reduction Algorithm Based on Attribute Deletion under the Dominance Relationship，IARAD⁃DR）

输入：序决策信息系统 $S = (U, A = C ⋃ D, V, f), S$ 的属性约简RED_C，删除的属性集P，U在 $C, C ⋃ D$ 上的劣势属性矩阵 $M_{U}^{R_{C}^{>}}, M_{U}^{R_{C ⋃ D}^{>}}$ 和优势关系矩阵 $M_{U}^{R_{C}^{\leq}}, M_{U}^{R_{C ⋃ D}^{\leq}}$ .

输出：序决策信息系统更新后的属性约简 $R E D_{C - P}$ .

步骤1.根据定义12求出更新后的增量关系矩阵 $Δ M_{U}^{R_{C}^{\leq}}$ 和 $Δ M_{U}^{R_{C ⋃ D}^{\leq}}$ .

步骤2.根据定理5计算更新后的 $G K (D| C - P)$ .

步骤3. $B \leftarrow R E D_{C} - P, R E D_P o o l \leftarrow C - (P ⋃ R E D_{C}) .$

步骤4.根据定理5计算 $G K (D| B)$ ，并根据定义13计算 $M_{U}^{R_{B}^{\leq}}, M_{U}^{R_{B ⋃ D}^{\leq}}$ ，若 $G K (D| B) = G K (D| C - P)$ ，则执行步骤7，否则执行步骤5.

步骤5.对于 $\forall a \in R E D_P o o l$ ，根据定理3计算 $S i g_{U}^{o u t e r} (a, B, D)$ ，取 $S i g_{U}^{o u t e r} (a_{m}, B, D) = m a x$

(S i g_{U}^{o u t e r} (a, B, D)), R E D_P o o l \leftarrow R E D_P o o l - \{a_{m}\}, B \leftarrow

$B ⋃ \{a_{m}\}$ ，同时根据定义10更新 $M_{U}^{R_{B}^{\leq}}$ 和 $M_{U}^{R_{B ⋃ D}^{\leq}}$ .

步骤6.若 $G K (D| C - P) = G K (D| B)$ ，则执行步骤7，否则执行步骤5.

步骤7.对于 $\forall a \in B$ ，根据定理6计算 $S i g_{U}^{i n n e r} (a, B, D)$ ，若 $S i g_{U}^{i n n e r} (a, B, D) = 0$ ，则 $B \leftarrow B - \{a\}$ .

步骤8. $R E D_{C ⋃ P} \leftarrow B$ ，输出 $R E D_{C ⋃ P}$ .

2.4　三种算法的时间复杂度分析

表1给出了数据集属性增加时ARKG⁃DR和IARAI⁃DR两种算法的时间复杂度.

表1 属性增加时两种算法的时间复杂度比较

Table 1 Time complexity of the two algorithms with the increase of attributes

算法	时间复杂度
ARKG⁃DR	$O ({\|U\|}^{2} (\|C\| + \|P\| + {(\|C\| + \|P\|)}^{2}))$
IARAI⁃DR	$O ({\|U\|}^{2} (2 \|C\| + 3 \|P\| + 7))$

新窗口打开| 下载CSV

IARAI⁃DR算法中，步骤1~3求新增属性集P后新数据集的知识粒度，时间复杂度为 $O ({|U|}^{2}$

$(|P| + 2))$ ；步骤4~6将每轮迭代中属性重要度最大的属性加入约简集，由于可以根据优势关系矩阵和劣势属性矩阵的增量更新机制计算，无须重新计算更新后的约简集的优势关系矩阵，时间复杂度最差为 $O ({|U|}^{2} (2 (|C| + |P|) + 4))$ ；步骤7~8向前删除约简集中的冗余属性，时间复杂度为 $O ({|U|}^{2}) .$ 那么，IARAI⁃DR算法总的时间复杂度为 $O ({|U|}^{2} (2 |C| + 3 |P| + 7))$ .

ARKG⁃DR算法中，步骤1~4求核属性，其时间复杂度为 $O ({|U|}^{2} (|C| + |P| + {(|C| + |P|)}^{2}))$ ；步骤5~8加入必要属性，删除冗余属性，时间复杂度最差为 $O ({|U|}^{2} ({(|C| + |P|)}^{2} + |C| + |P|)) .$ 那么，ARKG⁃DR算法总的时间复杂度为 $O ({|U|}^{2} (|C| + |P| + {(|C| + |P|)}^{2}))$ .

由以上分析可知，被约简集C的属性越多，IARAI⁃DR和ARKG⁃DR算法相比，效率更高.

表2给出了数据集属性删除时IARAD⁃DR和ARKG⁃DR两种算法的时间复杂度.

表2 属性删除时两种算法的时间复杂度比较

Table 2 Time complexity of the two algorithms with the deletion of attributes

算法	时间复杂度
ARKG⁃DR	$O ({\|U\|}^{2} (\|C\| - \|P\| + {(\|C\| - \|P\|)}^{2}))$
IARAD⁃DR	$O ({\|U\|}^{2} (2 \|C\| - 2 \|P\|) + 7)$

新窗口打开| 下载CSV

IARAD⁃DR算法中，步骤1~3的时间复杂度为 $O (2 {|U|}^{2})$ ，步骤4~8的时间复杂度最差为

$O ({|U|}^{2} (2 (|C| - |P|) + 5))$ .IARAD⁃DR总的时间复杂度为 $O ({|U|}^{2} (2 (|C| - |P|) + 7)) .$

ARKG⁃DR算法中，步骤1~4的时间复杂度为 $O ({|U|}^{2} (|C| - |P| + {(|C| - |P|)}^{2})),$ 步骤5~8的时间复杂度最坏为 $O ({|U|}^{2} (|C| - |P| +$

${(|C| - |P|)}^{2})) .$ ARKG⁃DR算法总的时间复杂度为 $O ({|U|}^{2} (|C| - |P| + {(|C| - |P|)}^{2})) .$

由以上的分析可知，被约简集C的属性越多，IARAD⁃DR和ARKG⁃DR算法相比，效率更高.

3 实验与结果分析

为了验证算法2和算法3的有效性及属性约简结果的准确性，从UCI机器学习数据库（https：∥archive.ics.uci.edu/ml/datasets.php）中选取六个数据集进行算法的性能测试.实验前对原始数据进行以下预处理：对属性值为字符串的数据集，根据数据集属性信息将字符串属性值按从劣到优的趋势赋予从小到大的具体数值，且相同的字符串属性值赋予相同数值，对属性值为数值的数据集不作任何更改，此外，数据集的分类（决策）属性值若相同则赋予相同的具体数值.各UCI数据集信息的具体描述如表3所示.

表3 实验使用的UCI数据集

Table 3 UCI datasets used in experiments

序号	数据集	对象数	属性数	类别数
1	Post⁃operative Patient	90	8	3
2	Blood Transfusion Service	748	5	2
3	Absenteeism	740	20	3
4	Ionosphere	351	34	2
5	Cardiotocography	2126	36	3
6	Diabetic Retinopathy	1151	20	2

新窗口打开| 下载CSV

测试环境：Intel（R） Core（TM） i5⁃6300HQ CPU @ 2.30 GHz处理器，12 GB内存，操作系统为Window10（64位），Pycharm软件平台.

实验分三部分.首先，将各数据集的数据按属性分为五等份，将第一份数据作为基础数据集，每次添加一份数据直至将整个数据集添加进来进行属性约简，最后比较分析IARAI⁃DR和ARKG⁃DR算法按此过程对数据集进行属性约简的运行时间和属性约简结果.第二部分，将第一部分实验得出的数据作为已知条件，将整个数据集作为基础数据集，每次从后往前删除一份数据直至还剩最后一份数据进行属性约简，然后比较分析IARAD⁃DR算法按此过程对数据集进行属性约简和第一部分ARKG⁃DR算法属性约简的运行时间.前两部分实验中的属性约简运行时间是十次运行时间的均值.第三部分，在Weka机器学习软件上测试IARAI⁃DR和ARKG⁃DR算法在六个数据集上属性约简的分类准确度.

从表3可知，实验选取了六个不同规模的数据集.规模最大的是Cardiotocography数据集，有2126个对象、36维属性，规模最小的是Post⁃operative Patient数据集，仅有90个对象、8维属性；属性维数最多的是Cardiotocography数据集，有36维属性，属性维数最少的是Blood Transfusion Service数据集，具有5维属性.

图1给出了逐渐增加数据时，ARKG⁃DR和IARAI⁃DR算法的运行时间.由图可见，数据量属性占比为20%时，ARKG⁃DR和IARAI⁃DR算法处理各数据集的运行时间的差距不大，这是因为属性较少时，两者的时间复杂度差距不大；随着数据量的增加，增量算法IARAI⁃DR处理各数据集的运行时间明显少于静态算法ARKG⁃DR.总体上，增量算法IARAI⁃DR计算数据集属性约简的运行效率优于ARKG⁃DR算法.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 数据量逐渐增加时，ARKG⁃DR和IARAI⁃DR算法运行时间的比较

Fig.1 Running time of ARKG⁃DR and IARAI⁃DR algorithms with the increase of data amount

表4给出了ARKG⁃DR和IARAI⁃DR算法在各数据集上计算属性约简的结果.由表可见，IARAI⁃DR处理Absenteeism数据集的属性约简结果长度优于ARKG⁃DR算法，处理其余数据集的属性约简结果的长度与ARKG⁃DR算法一致.

表4 两种算法在六个数据集上属性约简结果的比较

Table 4 Attribute reduction results of two algorithms on six datasets

属性集	属性数	ARKG⁃DR		IARAI⁃DR
属性集	属性数	属性约简	长度	属性约简	长度
Post⁃operative Patient	8	1,2,3,4,5,6,7,8	8	1,2,3,4,5,6,7,8	8
Blood Transfusion Service	5	1,4,5	3	1,2,4	3
Absenteeism	20	1,2,3,4,7,8,10,11,12,13,14,15,16,17,19	15	1,2,3,4,5,6,7,8,11,12,13,15,17,19	14
Ionosphere	34	4,6,8,9,10,11,14,16,17,18,20,22,23, 24,25,26,27,29,30,31,32,33,34	23	4,6,8,9,10,11,14,16,17,18,19,20,22, 23,24,26,27,29,30,31,32,33,34	23
Cardiotocography	36	1,5,7,8,9,10,11,12,14,16,17,20,22, 26,27,28,36	17	1,5,7,8,9,10,11,12,14,16,17,20,22, 26,27,28,36	17
Diabetic Retinopathy	20	2,3,4,5,6,7,9,10,11,12,13,14,15,16, 17,18,19,20	18	2,3,4,5,6,7,8,9,10,11,12,13,14,15, 16,17,18,19	18

新窗口打开| 下载CSV

图2给出了从后往前逐渐删除数据时，ARKG⁃DR和IARAD⁃DR算法处理数据集的运行时间.由图可见，当数据的删除量从0增加到80%时，增量算法IARAD⁃DR处理各数据集的运行时间都少于ARKG⁃DR算法；当数据的删除量接近或高于80%时，增量算法IARAD⁃DR处理各数据集的运行时间与ARKG⁃DR算法差不多.总体上，增量算法IARAD⁃DR计算数据集属性约简的运行效率优于ARKG⁃DR算法.

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 从后向前删除数据时，ARKG⁃DR和IARAD⁃DR算法运行时间的比较

Fig 2 Running time of ARKG⁃DR and IARAD⁃DR algorithms with the deletion of data from back to front

为了验证ARKG⁃DR和IARAI⁃DR算法处理各数据集得到的属性约简结果的准确性，使用Weka机器学习软件上自带的贝叶斯分类器进行测试并使用十折交叉验证的方式计算ARKG⁃DR和IARAI⁃DR算法得到的属性约简结果的分类准确度，结果如表5所示.由表可见，IARAI⁃DR在大多数数据集上的分类准确度和ARKG⁃DR算法一致，在Absenteeism和Ionosphere数据集上稍优于ARKG⁃DR算法，可见IARAI⁃DR算法计算属性约简是有效且准确的.

表5 ARKG⁃DR和IARAI⁃DR算法在六个数据集上的分类准确度的比较

Table 5 Classification accuracy of ARKG⁃DR and IARAI⁃DR algorithms on six datasets

数据集	ARKG⁃DR	IARAI⁃DR
Post⁃operative Patient	96.76%	96.76%
Blood Transfusion Service	98.21%	98.21%
Absenteeism	89.65%	91.83%
Ionosphere	90.35%	90.87%
Cardiotocography	86.54%	86.54%
Diabetic Retinopathy	93.35%	93.35%

新窗口打开| 下载CSV

4 结论

本文以知识粒度来度量序决策信息系统中的属性重要度，并以矩阵分析序决策信息系统中属性增删条件下知识粒度和优势关系矩阵的增量更新机制，由此提出了两种以属性重要度为启发信息的增量属性约简算法.为了验证算法的有效性和高效性，选择了六个UCI数据集进行实验.实验结果表明：从属性约简效率的角度看，各数据集参与属性约简的属性数目越多，本文提出的两种增量属性约简算法明显优于非增量约简算法；从属性约简结果的准确性看，本文提出的两种增量属性约简算法与非增量约简算法相差不大.另外，现实生活中的数据样本随时会发生动态变化，本文提出的算法无法对其进行属性约简.未来研究的重点是在序决策信息系统中有多个对象增加或者删除的情况下，设计以知识粒度表征属性重要度的快速增量式属性约简算法.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Pawlak

Rough sets

International Journal of Computer and Information Sciences，1982，11(5)：341-356.