变精度多粒度粗糙集近似集更新的矩阵算法

郑文彬 李进金 于佩秋 林艺东

摘 要：随着信息大爆炸时代的到来，数据集的巨大化和数据集结构的复杂化已经成为近似计算中不能忽视的问题，而动态计算是解决这些问题的一种行之有效的途径。对现有的应用于经典多粒度粗糙集动态近似集更新方法进行了改进，提出了应用于变精度多粒度粗糙集（VPMGRS）的向量矩阵近似集计算与更新方法。首先，提出了一种基于向量矩阵的VPMGRS近似集静态计算算法;其次，重新考虑了VPMGRS近似集更新时的搜索区域，并根据VPMGRS的性质缩小了该区域，有效地提升了近似集更新算法的时间效率;再次，根据新的搜索区域，在VPMGRS近似集静态计算算法的基础上提出了一种新的VPMGRS近似集更新的向量矩阵算法;最后，通过实验验证了所提算法的有效性。

关键词：动态计算;近似集更新;变精度多粒度粗糙集;矩阵算法

中图分类号：TP18

文献标志码：A

Matrixbased algorithm for updating approximations in

variable precision multigranulation rough sets

ZHENG Wenbin1，2*， LI Jinjin3， YU Peiqiu3， LIN Yidong4

1.School of Computer Science， Minnan Normal University， Zhangzhou Fujian 363000， China;

2.Fujian Key Laboratory of Granular Computing and Its Important Applications（Minnan Normal University）， Zhangzhou Fujian 363000， China;

3.School of Mathematics and Statistics， Minnan Normal University， Zhangzhou Fujian 363000， China;

4.School of Mathematical Sciences， Xiamen University， Xiamen Fujian 361005， China

Abstract：

In an information explosion era， the large scale and structure complexity of datasets become problems in approximation calculation. Dynamic computing is an efficient approach to solve these problems. With the development of existing updating method applied to the dynamic approximation in multigranular rough sets， a vector matrix based method for computing and updating approximations in Variable Precision MultiGranulation Rough Sets （VPMGRS） was proposed. Firstly， a static algorithm for computing approximations based on vector matrix for VPMGRS was presented. Secondly， the searching area for updating approximations in VPMGRS was reconsidered， and the area was shrunk according to the properties of VPMGRS， effectively improving the time efficiency of the approximation updating algorithm. Thirdly， according to the new searching area， a vector matrix based algorithm for updating approximations in VPMGRS was proposed based on the static algorithm for computing approximations. Finally， the effectiveness of the designed algorithm was verified by experiments.

Key words：

dynamic computing; approximation updating; variable precision multigranulation rough set; matrix algorithm

0 引言

自粗糙集[1]模型于1982年被波蘭学者Pawlak 提出以来，粗糙集模型被广泛应用于各种领域，例如模式识别[2]、机器学习[3]、图像处理[4]、数据挖掘[5]等。为了拓展粗糙集模型的应用范围，学者提出了许多粗糙集模型的拓展模型，例如覆盖粗糙集[6]、变精度粗糙集[7]、概率粗糙集[8]、多粒度粗糙集[9]、变精度多粒度粗糙集（Variable Precision MultiGranulation Rough Sets， VPMGRS）[10]等。

VPMGRS模型是窦慧莉等[10]于2012年提出的，该模型进一步拓展了多粒度粗糙集模型的应用前景。

VPMGRS是一种强大的数学工具，在许多多粒度视角下的现实生活场景中具有非常广泛的应用和非常强大的表示能力; 然而自VPMGRS被提出以来，较少有学者进行VPMGRS近似集计算与近似集更新方面的研究。不论应用何种粗糙集模型，包括且不限于VPMGRS模型，近似集计算都是应用中必要且重要的一环，例如：在有些属性约简的过程中必须计算正域，在规则提取时必须计算下近似集和上近似集。 在数据大爆炸时代，近似集计算开始变得越来越困难，数据集的巨大化使得有时不可能在整个数据集上进行计算，数据集的复杂化使得数据的结构也经常变化，属性增减、属性值改变、样本增多与减少在近似集计算时变得非常普遍。针对这些问题，在各种改变的场景下动态计算近似集是行之有效的解决方案。计算和更新多粒度粗糙集及其拓展模型的上下近似集引起众多研究者的广泛关注，这些研究通常分为4类，即：如何在增减属性时更新近似集[11]，如何在改变属性值时更新上下近似集[12]，如何在决策属性改变时更新上下近似集[13]，如何在论域中对象变化时更新上下近似集[14]。

本文提出一种在属性增加和减少时计算和更新VPMGRS上下近似集的新方法。首先提出了一种应用于VPMGRS的向量矩阵近似集静态计算方法;其次，根据VPMGRS的性质，缩小了更新上下近似集的搜索区域，更小的搜索区域意味着更少的计算时间;再次，根據新的搜索区域，提出了在属性增减时基于矩阵向量的VPMGRS近似集更新算法;最后，采用了几个UCI（http：//archive.ics.uci.edu/ml/index.php）数据集进行实验验证了所提算法的有效性。

1 预备知识

本章列举所有与本文工作相关的定义与定理。

定义1[15]设集合A与B是论域U的非空子集，定义集合A相对于集合B的相对正确分类率为：

P（A，B）=|A∩B|/|A|

其中|A|代表集合A的基数。

定义2[9]令S=（U，AT，V， f）为一个信息系统，其中：U={x1，x2，…，xn}为非空有限论域;AT={A1，A2，…，Am}为非空有限属性集族;Ak∈AT是一个属性集。V=∪A∈ATVA为属性值的值域，VA为属性集A的值域;f：U×AT→V为一个决策函数使得f（x，A）∈VA对任意的A∈AT，x∈U都成立。

定义3[10]变精度多粒度乐观粗糙集（Optimistic Variable Precision MultiGranulation Rough Sets， OVPMGRS）。令S=（U，AT，V， f）为一个信息系统。对于任意的XU， X的可变精度多粒度乐观下近似集与乐观上近似集分别表示为：

mk=1AβkO（X）={x∈U|P（[x]A1，X）≥β∨

P（[x]A2，X）≥β∨…∨P（[x]Am，X）≥β}

mk=1AβkO（X）=～mk=1AβkO（～X）

其中～X表示X的补集，β∈（0.5，1]。

由对偶性容易得到以下定理：

定理1[10]令S=（U，AT，V， f）为一个信息系统。 对于任意的XU，X的可变精度多粒度乐观上近似集表示为mk=1AβkO（X），则有：

mk=1AβkO（X）={x∈U|P（[x]A1，X）>（1-β）∧

P（[x]A2，X）>（1-β）∧…∧

P（[x]Am，X）>（1-β）}

定义4[10]变精度多粒度悲观粗糙集（Pessimistic Variable Precision MultiGranulation Rough Sets， PVPMGRS）。令S=（U，AT，V， f）为一个信息系统。 对于任意的XU，X的可变精度悲观下近似集与上近似集分别表示为：

mk=1AβkP（X）={x∈U|P（[x]A1，X）≥β∧

P（[x]A2，X）≥β∧…∧P（[x]Am，X）≥β}

mk=1AβkP（X）=～mk=1AβkP（～X）

由对偶性容易得到以下定理：

定理2[10]令S=（U，AT，V， f）为一个信息系统。 对于任意的XU，X的可变精度多粒度悲观上近似集表示为mk=1AβkP（X），则有：

mk=1AβkP（X）={x∈U|P（[x]A1，X）>（1-β）∨

P（[x]A2，X）>（1-β）∨…∨

P（[x]Am，X）>（1-β）}

定义5[16]令S=（U，AT，V， f）为一个信息系统。对于任意的XU，X的向量矩阵表示为G（X）=[g1（X），g2（X），…，g|U|（X）]T，其中gi（X）=1，xi∈X0，xiX，T表示矩阵的转置。

定理3 对于任意的集合X，YU，X相对于Y的相对正确分类率为：

P（X，Y）=[G（X）]T·G（Y）∑|U|i=1gi（X）

其中·为矩阵乘法。

证明 xi∈X∩Y  gi（X）=1∧gi（Y）=1  |X∩Y|=[G（X）]T·G（Y）

综上所述，P（X，Y）=[G（X）]T·G（Y）∑|U|i=1gi（X）。

2 基于矩阵的近似集静态计算算法

为了对变精度多粒度粗糙集（VPMGRS）近似集更新方法进行研究，本文首先对其近似集计算方法进行研究，给出静态的VPMGRS上、下近似集计算算法。

定义6 令S=（U，AT，V， f）为一个信息系统。对于任意的XU，X在属性集Ak上的变精度多粒度近似集特征向量定义为HAk（X）=[hAk1（X），hAk2（X），…，hAk|U|（X）]T，其中：

hAki（X）=P（[xi]Ak，X）; k∈{1，2，…，m}

显然，当[xi]Ak∩X=时，有hAki（X）=0，即如果能够确保[xi]Ak∩X=，则可以直接令hAki（X）=0。

定义7 令S=（U，AT，V， f）为一个信息系统。对于任意的XU，定义向量HAk（X）两个截向量HAk≥α（X）=[Ak1（X），Ak2（X），…，Ak|U|（X）]T与HAk>α（X）=[Ak1（X），Ak2（X），…，Ak|U|（X）]T，式中：

Aki（X）0，hAki<α1，hAki≥α

Aki（X）0，hAki≤α1，hAki>α

其中：k∈{1，2，…，m}， i∈{1，2，…，|U|}，α∈R为任一实数。

定理4 令S=（U，AT，V， f）为一个信息系统。对于任意的XU，X的变精度多粒度乐观下近似集与乐观上近似集分别表示为mk=1AβkO（X）和mk=1AβkO（X），则有：

1）G（mk=1AβkO（X））=∨mk=1HAk≥β（X）

2）G（mk=1AβkO（X））=∧mk=1HAk>1-β（X）

证明

1）xi∈mk=1AβkO（X）  gi（mk=1AβkO（X））=1  k∈{1，2，…，m}，s.t.P（[xi]Ak，X）≥β  ∨mk=1hAki（X）≥β  ∨mk=1Aki（X）=1。

综上所述，G（mk=1AβkO（X））=∨mk=1HAk≥β（X）。

2）证明过程类似于1）。

算法1 基于矩阵的变精度多粒度粗糙集上、下近似集算法。

输入 1）S=（U，AT，V， f）;2）G（[xi]Ak），k∈{1，2，…，m}，i∈{1，2，…，|U|}; 3）G（X）;4）β;

输出 mk=1AβkO（X）和mk=1AβkO（X）， mk=1AβkP（X）和mk=1AβkP（X）。

程序前

1）

n←|U|

2）

For i=1→n

3）

For j=1→n

4）

For k=1→m #m=|AT|

5）

If gi（X）=1∧gi（[xj]Ak）=1

#保证[xj]Ak∩X≠

6）

hAkj（X）←[G（[xj]Ak）]T·G（X）∑|U|i=1gi（[xj]Ak）

7）

End If

8）

End For

9）

End For

10）

End For

11）

G（mk=1AβkO（X））←∨mk=1HAk≥β（X）

12）

G（mk=1AβkO（X））←∧mk=1HAk>1-β（X）

13）

G（mk=1AβkP（X））←∧mk=1HAk≥β（X）

14）

G（mk=1AβkP（X））←∨mk=1HAk>1-β（X）

15）

Return mk=1AβkO（X）和mk=1AβkO（X）， mk=1AβkP（X）和mk=1AβkP（X）

程序后

定理5

令S=（U，AT，V， f）為一个信息系统。对于任意的XU，X的变精度多粒度悲观下近似集与上近似集分别表示为mk=1AβkP（X）和mk=1AβkP（X），则有：

1）G（mk=1AβkP（X））=∧mk=1HAk≥β（X）;

2）G（mk=1AβkP（X））=∨mk=1HAk>1-β（X）。

证明 证明过程类似于定理4。

由定理4与定理5可以得到算法1，即为基于矩阵的变精度多粒度粗糙集上下近似集算法，若RAk（X）={x|[x]Ak∩X≠}，则该算法的时间复杂度为Θ（max|RAk（X）||U|）。步骤2）～10）是用来计算HAk（X）的，时间复杂度为Θ（max|RAk（X）||U|）; 步骤11）～14）是用来计算mk=1AβkO（X）、mk=1AβkO（X）、mk=1AβkP（X）、mk=1AβkP（X）的，时间复杂度为Θ（m|U|）。

3 基于矩阵的近似集更新方法

基于本文给出的变精度多粒度粗糙集近似集静态计算方法，提出了基于矩阵的变精度多粒度粗糙集近似集更新算法。

3.1 添加属性时的近似集更新算法

在本节中，用St=（U，AT，V， f）表示一个t时刻的信息系统，其中AT={A1，A2，…，Am}为非空有限属性集族，用St+1=（U，AT，V，F）表示一个t+1时刻的信息系统，其中AT={A1，A2，…，Am}为非空有限属性集族。用mk=1AβkO（X）和mk=1AβkO（X）表示t时刻OVPMGRS的上、下近似集，用mk=1AβkP（X）和mk=1AβkP（X）表示t时刻PVPMGRS的上、下近似集，Ak是一个属性集，β∈（0.5，1]。 用mk=1AβkO（X）和mk=1AβkO（X）表示t+1时刻OVPMGRS的上、下近似集，用mk=1AβkP（X）和mk=1AβkP（X）表示t+1时刻PVPMGRS的上、下近似集，Ak∈AT，Ak∈AT使得AkAk，即从t时刻到t+1时刻属性增加了。

定理6 令St=（U，AT，V， f）为一个t时刻的信息系统，St+1=（U，AT，V，F）为一个t+1时刻的信息系统。HAk（X）为X在属性集Ak上的变精度多粒度近似特征向量，HAk（X）为X在属性集Ak上的变精度多粒度近似集特征向量，则对于任意的k∈{1，2，…，m}，X有以下性质成立：

1）hAki（X）=1hAki（X）=1

2）hAki（X）=0hAki（X）=0

证明

1） hAki（X）=1  P（[xi]Ak，X）=1  [xi]AkX

[xi]AkX  hAki（X）=1。

2） 证明类似于1）。

定理6说明，在向属性集中添加属性时，计算HAk（X）可以不计算HAk（X）中0和为1的那些位，因为由[x]Ak[x]Ak，x∈U都成立，有HAk（X）中为0和1的位在HAk（X）中也不变。

算法2 基于矩阵的变精度多粒度粗糙集上下近似集更新算法。

输入 1） S=（U，AT，V， f）; 2） G（[xi]Ak），k∈{1，2，…，m}，i∈{1，2，…，|U|}; 3）G（X）; 4）β; 5）HAk（X）。

输出 mk=1AβkO（X）和mk=1AβkO（X）， mk=1AβkP（X）和mk=1AβkP（X）。

程序前

1）

HAk（X）←HAk（X）

2）

n←|U|

3）

For i=1→n

4）

For k=1→m #m=|AT|

5）

If hAki（X）∈（0，1）

6）

hAki（X）←[G（[xi]Ak）]T·G（X）∑|U|i=1gi（[xi]Ak）

7）

End If

8）

End For

9）

End For

10）

G（mk=1AβkO（X））←∨mk=1HAk≥β（X）

11）

G（mk=1AβkO（X））←∧mk=1HAk>1-β（X）

12）

G（mk=1AβkP（X））←∧mk=1HAk≥β（X）

13）

G（mk=1AβkP（X））←∨mk=1HAk>1-β（X）

14）

Return mk=1AβkO（X）和mk=1AβkO（X），mk=1AβkP（X）和mk=1AβkP（X）

程序后

由定理6可以得到变精度多粒度粗糙集上下近似集更新算法，因为只对HAk（X）中处于（0，1）区间内的元素进行更新，若RAk′（X）={x|[x]Ak∩X≠∧[x]AkX}，则算法2的时间复杂度为O（∑mk=1|R′Ak（X）||U|）。步骤3）～9）是用来更新HAk（X）的，时间复杂度为O（∑mk=1|RAk′（X）||U|）; 步骤10）～13）是用来更新mk=1AβkO（X）、mk=1AβkO（X）、mk=1AβkP（X）、mk=1AβkP（X）的，时间复杂度为O（m|U|）。显然有RAk′（X）RAk（X）即最壞的情况下动态更新算法的时间复杂度才会等于静态计算算法。

3.2 减少属性时的近似集更新

下面将举出反例说明属性减少时，定理6将不再成立。

例1 一个多粒度信息系统如表1所示。令X={x2，x5，x6}，A1={a1，a2，a3}，A2={a4，a5，a6}，A3={a7，a8，a9}，A1={a2}，A2={a4}，A3={a9}，由定义6知hA12（X）=1，hA12（X）=1/2≠1;hA31（X）=0，hA31（X）=1/2≠0，所以当属性减少时定理6不再成立。

例1说明了当属性减少时不能使用本文所提出的近似集更新方法进行上下近似集更新，当本文的动态算法不能用于属性减少时，可以用本文提出的静态算法来计算变精度多粒度粗糙集上下近似集。

4 UCI数据实验分析

为了验证算法的有效性，本文选取了8个UCI数据来验证近似集静态计算算法与近似集更新算法的有效性。实验所使用的UCI数据集如表2所示。可以看到样本数从194到1-000，属性数目从5到59。所有实验均在系统为64bit Windows 10，CPU为Inter Core i7 6700HQ CPU 2.60GHz，16GB内存的个人计算机上进行，所使用的编程语言是Matlab r2015b。

4.1 不同大小数据集的计算时间对比

在本节中，令β=0.9，将数据集等分成10份U1，U2，…，U10，然后以每一份数据集为增加的步长，逐步地使数据集增大，即dataset1=U1，dataset2=U1∪U2，dataset3=U1∪U2∪U3…并使X大致为每个临时数据集的0.85倍大小，X中元素从每个临时数据集中随机选择。模拟属性增加时，对每个数据集，首先随机选出一个属性，然后将剩余的属性分为大致相等的三组At1、At2、At3。首先用算法1计算VPMGRS上下近似集，然后令At1、At2、At3、At+11=At1∪、At+12=At2∪、At+13=At3∪，分别使用算法1（静态算法）与算法2（动态算法）及对比算法基于关系矩阵的多粒度粗糙集近似更新算法[17]与基于关系矩阵的多粒度粗糙集近似计算算法[17]计算VPMGRS上下近似集并对比计算时间，得出如图1的实验结果，本文实验中计算时间的单位为秒。

[11]YANG X， QI Y， YU H， et al. Updating multigranulation rough approximations with increasing of granular structures[J]. Knowledge Based Systems， 2014， 64（1）： 59-69.

[12]CHEN H， LI T， LUO C， et al. A rough setbased method for updating decision rules on attribute values coarsening and refining [J]. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（12）： 2886-2899.

[13]CHENG Y. Dynamic maintenance of approximations under fuzzy rough sets [J]. International Journal of Machine Learning and Cybernetics， 2018， 9（12）： 2011-2026.

[14]HU J， LI T， LUO C， et al. Incremental fuzzy probabilistic rough sets over two universes[J]. International Journal of Approximate Reasoning， 2017， 81： 28-48.

[15]ZIARKO W. Variable precision rough set model[J]. Journal of Computer and System Sciences， 1993， 46（1）： 39-59.

[16]程燕.基于矩陣的覆盖粗糙集算法研究[D]. 合肥： 安徽大学， 2017. （CHENG Y. Study on covering rough set algorithm based on matrix [D]. Hefei： Anhui University， 2017.）

[17]HU C， LIU S， LIU G. Matrixbased approaches for dynamic updating approximations in multigranulation rough sets [J]. KnowledgeBased Systems， 2017， 122： 51-63.

This work is partially supported by the National Natural Science Foundation of China （11871259， 61379021）， the Youth Fund of Natural Science Foundation of China （11701258）.

ZHENG Wenbin， born in 1971， M. S.， senior lecturer. His research interests include rough set， granular computing， data mining， artificial intelligence.

LI Jinjin， born in 1960， Ph. D.， professor. His research interests include artificial intelligence， granular computing， topology.

YU Peiqiu， born in 1991， M. S. candidate. His research interests include rough set， granular computing， data mining， artificial intelligence.

LIN Yidong， born in 1989， Ph. D. candidate. His research interests include uncertainty theory.