一种基于相容块划分的动态增量式属性约简方法

doi:10.13232/j.cnki.jnju.2023.04.014

一种基于相容块划分的动态增量式属性约简方法

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

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

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

A dynamic incremental attribute reduction method based on consisitent block partitioning

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

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

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

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

收稿日期: 2023-01-09

基金资助:

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

Received: 2023-01-09

摘要

属性约简是数据挖掘、机器学习等研究领域中的一个颇为重要的预处理步骤，其效率的高低会直接影响相关任务的性能.针对已有的非增量式属性约简方法在相容块粗糙集模型中对象集发生变化时无法高效更新属性约简的问题，提出一种以区分度为启发信息的增量式属性约简方法.首先，引入相容块的概念并运用相容块对论域进行划分，在此基础上给出不完备信息系统的区分度定义；然后，详细分析对象集发生变化条件下区分度的更新机理；进一步，以区分度为启发式信息构造增量式属性约简算法；最后，选取六个UCI数据集进行增量式约简的更新实验.实验结果表明，在不影响属性约简精度的前提下，该增量式方法的时间消耗比非增量式更新方法平均缩短50%，更加可行和高效.

关键词： 属性约简 ; 相容块 ; 划分 ; 区分度 ; 增量学习

Abstract

Attribute reduction is essential for preprocessing in research fields such as data mining and machine learning since its efficiency has an immediate impact on the performances of the above⁃mentioned fields. In this paper，an incremental attribute reduction approach with discrimination as heuristic information is proposed against the problem of the non⁃incremental attribute reduction method failing to efficiently update the attribute reduction when the object set is changed in the consistent block rough set model. To begin with，the concept of compatible block is introduced to divide the domain of discourse using compatible blocks. Then，the differentiation degree of incomplete information system is defined before the analysis on the update mechanism of discrimination when the object set is changed. Moreover，an incremental attribute reduction algorithm is built with the discrimination as heuristic information. At last，an incremental reduction updating experiment is conducted on six UCI data sets selected. The time consumed by the incremental method is 50 % shorter than that by the non⁃incremental updating method on the premise of not affecting the accuracy of attribute reduction，according to the experimental results. To sum up，the proposed incremental reduction algorithm is more feasible and efficient than the non⁃incremental reduction algorithm.

Keywords： attribute reduction ; consistent block ; partition ; discrimination ; incremental learning

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

本文引用格式

徐阳, 王磊, 张义宗, 王诚彪. 一种基于相容块划分的动态增量式属性约简方法. 南京大学学报（自然科学）[J], 2023, 59(4): 680-689 doi:10.13232/j.cnki.jnju.2023.04.014

Xu Yang, Wang Lei, Zhang Yizong, Wang Chengbiao. A dynamic incremental attribute reduction method based on consisitent block partitioning. Journal of nanjing University[J], 2023, 59(4): 680-689 doi:10.13232/j.cnki.jnju.2023.04.014

粗糙集理论（Rough Set）是1982年波兰数学家Pawlak^［1］提出的一种处理不确定、不精确问题的有效数学工具，可描述属性间的依存关系，评估属性的重要性，并从决策表中导出规则.目前，粗糙集模型在医学^［2］、金融^［3］、机器学习^［4］、图像处理^［5］、模式识别^［6］等领域都有重要的应用.

经典粗糙集是在数据完整且没有缺失值的前提下，通过不可分辨关系对论域进行划分，对数据的要求严格.而在现实世界中，数据的收集、存储、传输等过程存在各种原因会导致数据的丢失，因此不完备信息系统中的粗糙集模型得到了广泛应用.各种基于不完备信息系统的研究任务也在持续开展.Kryszkiewicz^［7］提出基于容差关系的粗糙集模型并将其运用于属性约简.Leung and Li^［8］提出基于极大相容块的属性约简方法.杨习贝等^［9］将极大相容块引入特征类，提出特征相容块的概念并且讨论了特征相容块的基本性质.孙妍等^［10］将变精度粗糙集模型与极大相容块相结合，提出一种保持决策类上下近似不变的属性约简方法.周石泉和蒙祖强^［11］分析极大相容块在不完备信息系统中的特点，提出一种通过数据填补的方法来获取极大相容块.王敬前和张小红^［12］提出一种基于矩阵求取极大相容块与属性约简的方法.胡宝清和温彪^［13］在不完备模糊目标信息系统中引入极大相容块的概念，定义上、下近似集并且提出近似一致集和近似约简的概念以及近似约简的方法.以上都是通过容差关系构成论域的覆盖范围形成极大相容块.2021年Wang et al^［14］提出基于相容块的粗糙集模型，在不完备信息系统中运用对象的相容块构造论域的划分并由此给出概念上、下近似集的定义，该定义使上近似集中的元素个数减少，下近似集中的元素个数增加，与经典粗糙集模型相比，提高了其概念近似精度.

在实际应用中数据规模在不断变化，数据也会随着时间的变化而发生动态变化，因此属性约简的结果也会随之变化.非增量式方法在计算过程中需要从头开始计算，会消耗大量的时间.与非增量式方法相比，增量式方法被认为是处理动态数据的有效技术，因为它们可以在先前计算结果的基础上进行计算.鉴于不完备信息系统中数据的动态变化情况，许多学者也进行了系统深入的研究.如刘斌等^［15］在对象集发生变化的条件下，设计了一种相容块模型划分条件下近似集增量更新的方法.Wang^［16］在不完备信息表中针对属性集动态递增的情况提出基于条件熵的矩阵和非矩阵形式的两种增量机制，并由此给出属性集动态变化时的属性约简方法.Xie and Qin^［17］分析不完备信息系统下容差类的更新机制并由此提出属性值变化条件下的增量式属性约简方法.上述研究推动了不完备决策信息系统领域的蓬勃发展，但在对象集发生变化时，相容块模型划分情况下的增量式属性约简方面的研究相对较少.

本文在相容块划分的基础上，在论域发生变化时，对相容块属性约简以增量式更新方法进行系统研究.首先，介绍相容块的划分方法，随后将区分度应用于启发式属性约简的计算；然后，分析相容块粗糙集模型在对象集变化的条件下属性约简的增量机制，设计增量式属性约简方法；最后，通过实验证明了该方法的有效性.

1 相关概念

1.1　不完备信息系统基本概念

当信息系统存在缺失属性值时，信息系统由完备信息系统变成不完备信息系统，相应地，区分信息系统论域中对象间的关系由等价关系转变为相容关系，即将等价关系中的传递性去除，得到一种新的关系.

定义1

四元组 $S = (U, C ⋃ D, V, f)$ 称为信息系统，其中， $U$ 为对象的非空集合，称为论域； $C$ 为条件属性集合； $D$ 为决策属性集合； $V = ⋃ V a (\forall a \in C ⋃ D)$ 表示属性值域的集合，其中， $V a$ 表示属性 $a$ 的值域. $f$ 是论域与属性的映射函数， $f = (x, a)$ 表示对象 $x$ 关于属性 $a$ 的取值.若存在 $x \in U, a \in C$ 的取值不确定，记作 $f (x, a) = *$ ，称为不完备决策系统.

定义2

对于给定的不完备信息系统，其相容关系可记为 $S (T)$ ：

\begin{array}{l} S (T) = \{(u, v) \in U \times U| \forall a \in T, \\ f (u, a) = f (v, a) ⋁ f (u, a) = * ⋁ f (v, a) = *\} \end{array}

不完备信息系统中的相容关系是将缺失值看作与任何同属性下已有的值相等的可能性的一种描述.对象 $u$ 在知识 $S$ 下，与对象 $v$ 可能的不可区分的相容类为 $S I M (u) = \{v \in U |(u, v) \in S (T)\},$

$u, v \in U$ ，称 $S I M (u)$ 为相容关系下的信息粒度.

1.2　相容块及其对论域的划分

当等价关系转变为相容关系后，各对象的相容类不再构成对论域的划分，而是形成对论域的覆盖.尽管信息系统的知识和集合的粗糙性可以通过相容类来描述，但由于一个给定相容类中的对象也可能与其他相容类中的对象相似，甚至在同一个相容类中的两个对象也可以相似而不是不可区分的，因此，在不完备信息系统中用相容类来定义知识粒度并用它来度量知识的粗糙性就不合适.鉴于此，本文在不完备信息系统中引入相容块的概念.

定义3^［7］

设 $S = (U, C ⋃ D, V, f)$ 为不完备信息系统， $T \subseteq C 为属性子集, X \subseteq U$ 为论域子集.如果对任意两个对象 $x, y \in X$ ，均满足 $(x, y) \in S (T)$ ，则称 $X$ 是关于 $T$ 的相容块.如果不存在关于 $T$ 也是相容的论域子集 $Y$ ，使 $X \subset Y$ ，则称 $X$ 为 $T$ 的一个极大相容块.

对于 $\forall x_{i} \in U$ ，在 $B \subseteq A$ 下确定的所有包含 $x_{i}$ 的极大相容块的集合为 $C_{T}$ ， $C_{T} = \{\cup_{i = 1}^{m} C_{B} (x_{i}),$

$x_{i} \in U, m = |U|\}$ ，相容块的集合为 $K_{T} (x_{i})$ ， $K_{T} = \{\cup_{i = 1}^{m} K_{B} (x_{i}), x_{i} \in U, m = |U|\}$ .

定义4

相容关系下的相容块在论域上的划分：

\begin{array}{l} π_{T} = \{X_{k} \in K_{T} \land (\forall X_{i}, X_{j} \in K_{T} \land i \neq j \land \\ X_{i} ⋂ X_{j} = \emptyset, \cup_{i} X_{i} = U)\} \end{array}

例1

表1是一个不完备决策系统，其中 $U = \{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}\}$ 为论域，条件属性集为 $C = \{a_{1}, a_{2}, a_{3}, a_{4}\}, “ * ” 表示缺失值$ .

表1 一个不完备信息系统

Table 1 An incomplete information system

$U$	$a_{1}$	$a_{2}$	$a_{4}$
$x_{1}$	1	1	2
$x_{2}$	2	*	2
$x_{3}$	*	*	1
$x_{4}$	1	*	1
$x_{5}$	*	*	1
$x_{6}$	2	1	*

新窗口打开| 下载CSV

由定义3可知：

\begin{array}{l} C_{T} = \{\{x_{1}\}, \{x_{2}, x_{6}\}, \{x_{3}, x_{4}, x_{5}\}, \{x_{5}, x_{6}\}\} \\ C_{T} (x_{1}) = \{\{x_{1}\}\} \\ C_{T} (x_{2}) = \{\{x_{2}, x_{6}\}\} \\ C_{T} (x_{3}) = \{\{x_{3}, x_{4}, x_{5}\}\} \\ C_{T} (x_{4}) = \{\{x_{3}, x_{4}, x_{5}\}\} \\ C_{T} (x_{5}) = \{\{x_{3}, x_{4}, x_{5}\}, \{x_{5}, x_{6}\}\} \\ C_{T} (x_{6}) = \{\{x_{5}, x_{6}\}\} \end{array}

图1为极大相容块在论域上的覆盖.根据Wang et al^［14］将其划分为 $π_{T} = \{\{x_{1}\}, \{x_{3}, x_{4}, x_{5}\},$

图1

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

图1 极大相容块在论域上的覆盖

Fig.1 Coverage of maximal consistent blocks on universe

$\{x_{2}, x_{6}\}\}$ .图2为相容块在论域上的划分.

图2

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

图2 相容块在论域上的划分

Fig.2 Division of compatible blocks on universe

1.3　区分度度量与属性重要度

如图1和图2所示，利用无向图来表示相容块，顶点表示对象.在求解相容块划分的执行过程中寻找极大完全子图并删除与极大完全子图的顶点相关边，这个操作弱化了这部分顶点表示的对象之间的相容关系.被删除的边涉及的对象之间的相容关系在整体的相容块模型中可以看作块与块之间是可区分的，而同一相容块内部任意两个对象均是不可区分的.在基于相容块划分的粗糙集模型中，区分关系表示为：

D i s (P) = \{(x_{i}, x_{j}) \in U \times U| \exists a \in P, f (x_{i}, a) \neq f (x_{j}, a) \land (f (x_{i}, a) \neq * \lor f (x_{j}, a) \neq *)\}

由于弱化了一部分对象的相容关系，所以 $D i s (P) ⋃ S_{S I M} (P) = U \times U$ ，即 $|D i s (P)| + |S_{S I M} (P)| = {|U|}^{2}$ ，其中， $|S_{S I M} (P)|$ 为划分后相容块对象个数的平方和.据此给出区分度的定义.

定义5

已知不完备信息系统 $I S = (U, C ⋃ D, V, f)$ ， $U$ 为论域， $P \subseteq C$ ， $U / P = \{P_{1}, P_{2},$

$\dots, P_{m}\} 为$ 相容块对论域 $U$ 的划分，则区分度 $|D i s_{U} (P)|$ 为：

|D i s_{U} (P)| = {|U|}^{2} - \sum_{i = 1}^{m} {|P_{i}|}^{2}

定义6

已知不完备信息系统 $I S = (U, C ⋃ D, V, f)$ ， $U$ 为论域，假设论域 $U$ 上基于两个相容块划分为 $P, Q$ ，则 $Q$ 关于 $P$ 的相对区分度定义为：

|D i s_{U} (Q| P)| = |D i s_{U} (P)| - |D i s_{U} (P ⋃ Q)|

由定义5和定义6可知，区分度是以属性所能区分的对象对的数目的多少来表示属性的区分能力.随着条件属性集的增加，基于相容块的划分也会随之细化，其区分度也会随之变化.区分度越大的属性，区分能力越强.据此给出属性重要度的定义如下.

定义7

属性重要度1 已知非完备信息系统 $I S = (U, C ⋃ D, V, f)$ ， $\forall a \in C$ ，属性 $a$ 关于条件属性集 $C$ 相对于决策属性集 $D$ 的重要度定义为：

\begin{array}{l} S i g_{U}^{i n t e r} (a, C, D) = \\ |D i s_{U} (D| C - \{a\})| - |D i s_{U} (D| C)| \end{array}

定义8

属性重要度2 已知不完备信息系统 $I S = (U, C ⋃ D, V, f)$ ， $B \subseteq C, \forall a \in C$ ，属性 $a$ 关于条件属性集 $B$ 相对于决策属性集 $D$ 的重要度为：

\begin{array}{l} S i g_{U}^{o u t e r} (a, B, D) = \\ |D i s_{U} (D| B)| - |D i s_{U} (D |B ⋃ \{a\})| \end{array}

性质1

$I S = (U, C ⋃ D, V, f)$ 是非完备信息系统，如果 $S i g_{U}^{i n t e r} (a, C, D) > 0$ ，则属性 $a$ 是不完备信息系统条件属性集 $C$ 相对于决策属性集 $D$ 的必要属性.

定义9

已知 $I S = (U, C ⋃ D, V, f)$ ，则 $I S$ 的核被定义为：

C o r e_{C} (D) = \{a \in C |S i g_{U}^{i n t e r} (a, B, D) > 0\}

2 以区分度为启发式信息的属性约简方法

基于区分度的启发式属性约简算法（Heuristic Attribute Reduction Algorithm Based on Discrimination，HARM⁃D）的具体描述如算法1所示.

算法1 HARM⁃D

输入：一个非完备信息系统

输出：属性约简集合

Step 1.初始化属性集合 $r e d = \emptyset$ .

Step 2.对于 $\forall a_{i} \in C$ ，计算内部属性重要度，将属性重要度大于0的 $a_{i}$ 存入 $r e d$ 中，即 $r e d \leftarrow r e d ⋃ \{a_{i}\}$ .

Step 3. $B \leftarrow r e d$ .

Step 4.分别计算 $D i s (D| B)$ 和 $D i s (D| C)$ ，如果相等，转Step 8，否则转Step 5.

Step 5.对于 $\forall a_{0} \in (C - B)$ ，计算其外部属性重要度，依次选取 $a_{0} = m a x \{S i g_{U}^{o u t e r} (a_{0}, B, D)\}$ 添加到属性集中，即 $B \leftarrow B ⋃ \{a_{0}\}$ .

Step 6.计算更新后的 $D i s (D| B)$ ，若和 $D i s (D| C)$ 相等则停止计算，转Step 7，否则继续循环直到满足相等条件为止.

Step 7.对于 $\forall a_{j} \in B$ ，计算 $D i s (D| B - {a_{j}})$ ，若与 $D i s (D| C)$ 相等，则 $a_{j}$ 为冗余属性，予以删除；否则 $B$ 保持不变.

Step 8. $r e d \leftarrow B$ ，返回属性约简结果.

3 对象集变化条件下的增量式属性约简

本节介绍基于相容块的动态增量式属性约简方法.当对象集发生变化时其相容块必然会发生相应的变化，导致区分度随之变化.运用增量式更新策略更新区分度，避免从头开始计算，减少了属性约简更新的时间.

3.1　有对象添加至对象集时区分度的更新方法

非完备决策表 $S = \{U, C ⋃ D, V, f\}, U / B = \{P_{1}, P_{2}, \dots, P_{m}\}$ ，假设 $U^{+}$ 为新增加的对象集.由于容差关系不具备传递性，所以先对新增对象进行划分再与原有相容块联合不再可行，即 $U^{+} / C = \{Y_{1}, Y_{2}, \dots, Y_{k}\}, \exists y_{1}, y_{2} \in Y_{i} (1 \leq i \leq k),$ $(y_{1}, y_{2}) \in S (T)$ ，其中， $(x_{1}, y_{1}) \in S (T), x_{1} \in P_{i}$ ，但 $(x_{1}, y_{2}) \notin S (T),$ 所以 $X_{i}$ 与 $Y_{i}$ 不相容.新增一组对象时，需要判断每一个对象是直接加入到某一个既有的相容块中，还是由该单个对象构造一个新的相容块.

定理1

假设 $S = (U, A = C ⋃ D, V, f)$ 是一个不完备信息表， $B \subseteq C, U / B = \{P_{1}, P_{2}, \dots, P_{m}\}$ ，增加对象集 $U^{+}$ 后的相容块划分为 $U ⋃ U^{+} / B = \{P_{1}^{'}, P_{2}^{'}, \dots, P_{k}^{'}, P_{k + 1}, P_{k + 2}, \dots, P_{m}, Y_{k + 1}, \dots, Y_{m'}\}$ ，则增加对象集 $U^{+}$ 后的区分度为：

\begin{array}{l} D i s_{U ⋃ U^{+}} (C) = {|U ⋃ U^{+}|}^{2} - \\ (\sum_{i = 1}^{k} {|P_{i}^{'}|}^{2} + \sum_{i = k + 1}^{m} {|P_{i}|}^{2} + \sum_{i = k + 1}^{m'} {|Y_{i}|}^{2}) \end{array}

其中， $P_{i}^{'} = P_{i} ⋃ y_{j} (i = 1,2, \dots, k)$ ， $y_{j} \in U^{+}$ ， $\forall p \in P_{i}$ 均有 $(p, y_{j}) \in S_{S I M} (T)$ 成立.

证明

令 $U^{'} = U ⋃ U^{+}, U^{'} / B = \{X_{1}, X_{2}, \dots,$

$X_{m}\}$ ，所以更新后的区分度为 $D i s_{U^{'}} = U'^{2} - \sum_{i = 1}^{m} {|X_{i}|}^{2}$ ，可以发现新增对象后的相容块划分：

\begin{array}{l} U^{'} / B = \{X_{1}, X_{2}, \dots, X_{m}\} = \\ ⋃_{i = 1}^{k} P_{i}' ⋃_{i = k + 1}^{m} P_{i} ⋃_{i = k + 1}^{m'} Y_{i} \end{array}

所以，

\begin{array}{l} D i s_{U^{'}} = U'^{2} - \sum_{i = 1}^{m} {|X_{i}|}^{2} = {|U ⋃ U^{+}|}^{2} - \\ (\sum_{i = 1}^{k} {|P_{i}^{'}|}^{2} + \sum_{i = k + 1}^{m} {|P_{i}|}^{2} + \sum_{i = k + 1}^{m'} {|Y_{i}|}^{2}) \end{array}

得证.

定理2

假设 $S = {U, A = C ⋃ D, V, f}$ 为不完备信息表， $U / C ⋃ D = {M_{1}, M_{2}, \dots, M_{n}}$ ，增加对象集 $U^{+}$ ，增加对象集后相容块的划分更新为：

\begin{array}{l} U ⋃ U^{+} = \{M_{1}^{'}, M_{2}^{'}, \dots, M_{k}^{'}, M_{k + 1}, M_{k + 2}, \dots, M_{m}, \\ N_{k + 1}, \dots, N_{m'}\} \end{array}

则有：

\begin{array}{l} D i s_{U ⋃ U^{+}} (D| C) = \\ (\sum_{i = 1}^{k} {|P_{i}^{'}|}^{2} + \sum_{i = k + 1}^{m} {|P_{i}|}^{2} + \sum_{i = k + 1}^{m^{'}} {|Y_{i}|}^{2}) - \\ (\sum_{i = 1}^{k} {|M_{i}'|}^{2} + \sum_{i = k + 1}^{m} {|M_{i}|}^{2} + \sum_{i = k + 1}^{m'} {|N_{i}|}^{2}) \end{array}

证明

D i s_{U ⋃ U^{+}} (D| C) = D i s_{U ⋃ U^{+}} (C) - D i s_{U ⋃ U^{+}} (C ⋃ D)

其中， $D i s_{U ⋃ U^{+}} (C)$ 见定理1， $D i s_{U ⋃ U^{+}} (C ⋃ D)$ 定理与定理1类似.所以，

\begin{array}{l} D i s_{U ⋃ U^{+}} (D| C) = {|U ⋃ U^{+}|}^{2} - \\ (\sum_{i = 1}^{k} {|M_{i}'|}^{2} + \sum_{i = k + 1}^{m} {|M_{i}|}^{2} + \sum_{i = k + 1}^{m^{'}} {|N_{i}|}^{2}) - \\ {|U ⋃ U^{+}|}^{2} + \\ (\sum_{i = 1}^{k} {|P_{i}^{'}|}^{2} + \sum_{i = k + 1}^{m} {|P_{i}|}^{2} + \sum_{i = k + 1}^{m^{'}} {|Y_{i}|}^{2}) = \\ (\sum_{i = 1}^{k} {|P_{i}^{'}|}^{2} + \sum_{i = k + 1}^{m} {|P_{i}|}^{2} + \sum_{i = k + 1}^{m^{'}} {|Y_{i}|}^{2}) - \\ (\sum_{i = 1}^{k} {|M_{i}'|}^{2} + \sum_{i = k + 1}^{m} {|M_{i}|}^{2} + \sum_{i = k + 1}^{m'} {|N_{i}|}^{2}) \end{array}

得证.

3.2　有对象从对象集中删除时区分度的更新方法不完备信息表 $S = (U, C ⋃ D, V, f),$ 其划分相容块为 $U / B = \{P_{1}, P_{2}, \dots, P_{m}\}$ ，假设 $U^{-} = \{x_{1}, x_{2},$

$\dots, x_{n}\}$ 为删除的对象集.由于既有相容块的块内任意对象均是相容的，而任意两个不同相容块之间的任意对象都是不相容的，即 $\forall p_{s} \in P_{t}, \forall p_{n} \in P_{a}$

$(t \neq a), (p_{s}, p_{n}) \notin S (T)$ ，所以，对于删除对象集，直接删除每一个相容块里的待删除的对象，不会影响既有的基于相容块的论域划分.

定理3

假设 $S = (U, A = C ⋃ D, V, f)$ 是一个非完备信息表，基于相容块的论域划分为 $U / B = \{P_{1}, P_{2} \dots P_{m}\}$ ，删除的对象集为 $U^{-} = \{x_{1},$

$x_{2}, \dots, x_{n}\}$ ，删除对象集后基于相容块的论域划分为 $U - U^{-} / C = \{P_{1}^{'}, P_{2}^{'}, \dots, P_{k}^{'}, P_{k + 1}, \dots, P_{m}\}$ ，则删除对象集后的区分度为：

D i s_{U - U^{-}} (C) = {|U - U^{-}|}^{2} - (\sum_{i = 1}^{k} {|P_{i}^{'}|}^{2} + \sum_{i = k + 1}^{m} {|P_{i}|}^{2})

其中，

P_{i}^{'} = P_{i} - x_{t} (i = 1,2, \dots, k), x_{t} \in U^{-} \land x_{t} \in P_{i})

证明

令 $U^{'} = U - U^{-}$ ， $U^{'}$ 下的相容块划分为 $U^{'} / C = \{X_{1}, X_{2}, \dots, X_{n}\}$ ，所以区分度为：

D i s_{U^{'}} (C) = {|U'|}^{2} - (\sum_{i = 1}^{n} {|X_{i}|}^{2})

可以发现更新后的相容块

U^{'} / C = \{X_{1}, X_{2}, \dots, X_{n}\} = ⋃_{i = 1}^{k} P_{i}' ⋃_{i = k + 1}^{m} P_{i}

所以更新后的区分度为：

\begin{array}{l} D i s_{U^{'}} (C) = {|U'|}^{2} - (\sum_{i = 1}^{n} {|X_{i}|}^{2}) = \\ {|U - U^{-}|}^{2} - (\sum_{i = 1}^{k} {|P_{i}^{'}|}^{2} + \sum_{i = k + 1}^{m} {|P_{i}|}^{2}) \end{array}

得证.

定理4

假设 $S = {U, A = C ⋃ D, V, f}$ 为非完备信息表， $U / C ⋃ D = {M_{1}, M_{2}, \dots, M_{n}}$ ，删除对象 $U^{-} = \{x_{1}, x_{2}, \dots, x_{n}\}$ ，删除对象后的相容块划分为 $U - U^{-} / C ⋃ D = \{M_{1}^{'}, M_{2}^{'}, \dots, M_{k}^{'}, M_{k + 1},$

$M_{k + 2}, \dots, M_{m}\}$ ，则其相对区分度为：

\begin{array}{l} D i s_{U - U^{-}} (D| C) = (\sum_{i = 1}^{k} {|P_{i}^{'}|}^{2} + \sum_{i = k + 1}^{m} {|P_{i}|}^{2}) - \\ (\sum_{i = 1}^{k} {|M_{i}^{'}|}^{2} + \sum_{i = k + 1}^{m} {|M_{i}|}^{2}) \end{array}

证明

定理4的证明与定理2类似.

3.3　算法描述

针对基于相容块划分的粗糙集中对象集动态变化的情形，构造一种增量式属性约简方法，具体步骤见算法2和算法3.

算法2 对象集增加时基于区分度的增量属性约简算法（Incremental Property Reduction Algorithm Based on Discrimination When Adding Objects，IPRM⁃D）

输入：非完备决策系统 $I D S = \{U, C ⋃ D, V, f\}$ ，原有属性约简集 $r e d_{U}$ ，新增对象集 $U^{+}$

输出：属性约简的更新 $r e d_{U ⋃ U^{+}}$

Step 1. $B \leftarrow r e d_{U}$ .

Step 2.计算基于相容块的论域划分 $U ⋃ U^{+} / B,$

U ⋃ U^{+} / C

Step 3.判断 $D i s_{U ⋃ U^{+}} (D| B)$ 与 $D i s_{U ⋃ U^{+}} (D| C)$ 是否相等，若相等，转Step 7.

Step 4.对 $\forall a \in C - B$ ，计算其外部属性重要度，依次选取 $a^{'} = m a x \{s i g_{D i s}^{o u t e r} (a, B, D)\}$ 添加到属性约简集中.

Step 5. $B \leftarrow B ⋃ \{a'\}$ ，计算更新后的区分度 $D i s_{U ⋃ U^{+}} (D| B)$ ，若与 $D i s_{U ⋃ U^{+}} (D| C)$ 相等，则转Step 6，否则继续循环直到满足条件为止.

Step 6.对于 $\forall a_{0} \in B$ ，计算 $D i s_{U ⋃ U^{+}} (D| B - {a_{0}})$ ，若 $D i s_{U ⋃ U^{+}} (D| B - \{a_{0}\}) = D i s_{U ⋃ U^{+}} (D| B)$ ，则 $a_{0}$ 为冗余属性，否则 $a_{0}$ 为约简， $B$ 保持不变.

Step 7. $r e d_{U ⋃ U^{+}} \leftarrow B$ .

算法3 对象删除时相容块基于区分度的增量约简算法（Updating Attribute Reduction Algorithm When Deleting Some Objects，UARD）

输入：一个非完备决策表 $I D S = \{U, A = C ⋃ D, V, f\}$ ，约简属性集 $r e d_{U}$ ，删除对象集合 $U^{-}$

输出：约简集合 $r e d_{U - U^{-}}$

Step 1. $B \leftarrow r e d_{U}$ .

Step 2.计算 $D i s_{U - U^{-}} (D| C)$ .

Step 3.对 $\forall a \in B$ ，计算 $D i s_{U - U^{-}} (D| B - \{a\})$ ，判断是否与 $D i s_{U - U^{-}} (D| C)$ 相等，如果相等，转Step 4，如果不相等，则继续执行Step 3.

Step 4. $B \leftarrow (B - \{a\})$ .

Step 5. $r e d_{U - U^{-}} \leftarrow B$ .

3.4　算法时间复杂度分析与比较

当新增对象集 $U^{+}$ 添加至非完备决策信息系统时，非增量式属性约简算法，即算法1在不完备决策信息表中基于相容块划分的粗糙集模型下的时间复杂度为计算论域中相对区分度，即起点的时间复杂度为 $O (|C| {|U ⋃ U^{+}|}^{3})$ ，所以非增量式方法的总的时间复杂度为 $O (|C| {|U ⋃ U^{+}|}^{3} + {|C|}^{2} {|U ⋃ U^{+}|}^{3} +$

k ∙ {|U ⋃ U^{+}|}^{3})

增量式属性约简方法的时间复杂度如下.计算新的区分度的时间复杂度为 $O ({|n ∙ U ⋃ U^{+}|}^{3})$ .有新的对象添加时，仅需依据原有的属性约简结果来处理属性约简结果之外的属性，因此，提出的增量式属性约简算法的时间复杂度为 $O (n ∙ {|U ⋃ U^{+}|}^{3} + |U| |U^{+}|)$ ，其中， $n$ 为约简属性数量的变化量， $k$ 为去除冗余之前属性的数量.从对象集中删除对象时，非增量式属性约简算法总的时间复杂度为 $O (|C| {|U - U^{-}|}^{3} + {|C|}^{2} {|U - U^{-}|}^{3} + k ∙ {|U - U^{-}|}^{3})$ ，而增量式属性约简算法总的时间复杂度则为 $O (k ∙ {|U - U^{-}|}^{3})$ .

可以看出，增量式属性约简的时间复杂度比非增量的时间复杂度低.即在基于相容块划分的属性约简的计算中，增量式属性约简算法节省了大量的时间.

4 实验与结果分析

4.1　实验数据集

为了证实提出的增量式属性约简算法的准确性和有效性，从UCI机器学习数据库中精选了六个数据集.先对这六个数据集进行预处理：首先，对完整数据集随机选择20%的属性值进行剔除；然后，对含有缺失值的数据集，将缺失的值全部用“*”代替.六个数据集的具体信息如表2所示.

表2 实验使用的数据集

Table 2 Datasets used in experiments

序号	数据集	对象数	属性数	类别数
1	Lymphography	148	18	3
2	Diabetes_data_upload	520	16	2
3	Anneal	798	38	5
4	Credit Approval	690	15	2
5	Maternal Health Risk	1014	6	3
6	Obesity Dataset	2111	16	7

新窗口打开| 下载CSV

4.2　实验方案

硬件环境：Intel（R） Core（TM） i5⁃7300 HQ CPU @ 2.50 GHz 2.50 GHz，内存为8 GB.各约简算法在Pycharm软件平台上编程实现.为了比较非增量式属性约简算法与增量式属性约简算法的时间消耗，具体的实验步骤如下：

（1）将每个数据集分成均匀的两部分，第一部分是作为基础数据集的50%，然后取剩余数据的20%添加到基础数据集中，后面按剩余数据集的20%递增直至剩余数据全部取完，记录每次的运行时间.

（2）将每个数据集选取10%作为删除数据集，并按10%的数据依次递增，直至全部数据的50%，记录每次的运行时间.

4.3　两种算法运行时间比较

为了验证增量式属性约简算法的高效性，通过添加对象集来使原始对象集发生变化.图3给出了在六个数据集上增加一组对象时，增量与非增量属性约简消耗的时间对比.图4给出了每个数据集删除一组对象时，增量与非增量属性约简消耗的时间对比.

图3

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

图3 两种算法在六个数据集上增加一组对象时消耗的时间对比

Fig.3 Time consumption of two algorithms on six datasets when adding a group of objects

图4

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

图4 两种算法在六个数据集上删除一组对象时消耗的时间对比

Fig.4 Time consumption of two algorithms on six datasets when deleting a group of objects

由图3和图4的各子图可以得到以下结论：

（1）图3a和图4a中，由于基础数据集与增量数据集较小，非增量属性约简算法的运行时间会出现波动的情况.但是在增量式属性约简的算法中仍然呈现递增或递减的趋势，并且运行速度仍然比非增量式算法快.

（2）当增加对象集时，无论原有基础对象集的约简属性集是否改变，增量式属性约简算法消耗的时间都比非增量式属性约简算法要少.

（3）非增量式方法在时间消耗上的增长幅度较大，而增量式的方法的增长幅度较小.

（4）随着数据集大小的增加，两种方法在时间消耗上的差异也越来越明显.在部分数据集中，由于增加对象后区分度在原有属性集下区分度不变，会出现约简结果不会随着对象集的变化而变化的情况，这极大地缩短了属性约简的时间.

4.4　两种方法的约简结果比较

两种方法的属性约简结果如表3所示.由表可见，非增量式属性约简方法与增量式属性约简方法的约简结果非常接近，并且增量式方法可以在更短的时间内获得一个可行的约简.

表3 两种属性约简方法的实验结果

Table 3 Experimental results of attribute reduction by two methods

数据集	增量算法	非增量算法
Lymphography	7,15,14,2,16,4,3,11,12	3,4,7,8,11,13,14,15,17,2
Diabetes_data_upload	1,5,6,4,2,10,9	1,2,5,3,15,16,14,8
Anneal	1,3,4,8,9,12,33,34,35,7	1,3,4,5,7,8,33,34,37
Credit Approval	2,3,8,6	2,3,8,6
Maternal Health Risk	2,3,4,9,11,13,14,15,1,7,8	2,3,4,12,13,14,15,16,9
Obesity Dataset	1,3,4,6,5,2	1,3,4,6,5,2

新窗口打开| 下载CSV

4.5　分类精度比较

为了验证相容块划分增量式算法约简结果的准确性，在Weka机器学习软件上，用软件自带的贝叶斯分类器进行测试，并通过十折交叉验证的方法来计算增量式算法与非增量式算法获得的属性约简结果的分类精度，结果如表4所示.

表4 两种算法在六个数据集上的分类精度比较

Table 4 Classification accuracy of two methods on six datasets

数据集	增量算法	非增量算法
Lymphography	81.376%	81.352%
Diabetes_data_upload	92.233%	92.383%
Anneal	74.375%	74.575%
Credit Approval	84.453%	84.453%
Maternal Health Risk	67.843%	67.843%
Obesity Dataset	78.778%	78.778%

新窗口打开| 下载CSV

由表可见，划分相容块粗糙集模型运用非增量式方法与增量式方法的分类精度十分接近，说明本文提出的增量式方法属性约简是可行和有效的.

4.6　与其他增量算法比较

选用文献［19-21］中的方法与本文算法进行比较实验，实验搭载的硬件环境和数据集与前文相同.选取每个数据集的20%作为增加或者删除数据集，记录其运行时间，实验结果如表5所示.

表5 四种算法增加或者删除20%的数据集时的运行时间比较

Table 5 Running time of four algorithms when adding or deleting 20% of datasets

数据集	文献[19]		文献[20]		文献[21]		本文提出的方法
数据集	增加	删除	增加	删除	增加	删除	增加	删除
Lymphography	0.23 s	0.54 s	0.17 s	0.67 s	0.47 s	1.03 s	0.14 s	0.61 s
Diabetes_data_upload	45.43 s	95.43 s	79.52 s	80.44 s	52.19 s	65.10 s	35.64 s	67.4 s
Anneal	42.10 s	275.43 s	39.17 s	160.43 s	79.52 s	105.90 s	6.08 s	153.64 s
Credit Approval	0.35 s	0.79 s	1.43 s	1.59 s	2.11 s	1.77 s	0.37 s	0.57 s
Maternal Health Risk	103.42 s	257.79 s	39.57 s	423.12 s	57.23 s	251.43 s	23.16 s	237.12 s
Obesity Dataset	509.42 s	1503.2 s	645.2 s	2709.4 s	1002.5 s	2347.6 s	1116.32 s	2001.55 s

新窗口打开| 下载CSV

由表可见，与其他算法相比，本文算法在大多数数据集中同样具有一定的优势.

5 结论

本文以区分度的视角来度量基于相容块划分的粗糙集模型中的属性重要度，并在此基础上提出基于区分度视角的增量更新机制，以此提出增量式属性约简算法.为了验证算法的可靠性，选取六个UCI数据集进行实验.实验结果表明，针对在不完备信息系统中基于相容块划分的粗糙集模型的对象的增加或者减少两种情形，本文提出的方法均能高效地进行动态属性约简.但本研究只考虑了对象集的变化情况，所以未来工作的重点是在属性集发生变化时，设计基于区分度的增量式属性约简方法.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Pawlak

Rough sets

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