基于极大相容块的邻域粗糙集模型

doi:10.13232/j.cnki.jnju.2019.04.002

基于极大相容块的邻域粗糙集模型

程永林¹, 李德玉^,¹^,², 王素格¹^,²

1. 山西大学计算机与信息技术学院，太原，030006

2. 计算智能与中文信息处理教育部重点实验室，山西大学，太原，030006

Neighborhood rough set model based on maximal consistent blocks

Cheng Yonglin¹, Li Deyu^,¹^,², Wang Suge¹^,²

1. School of Computer & Information Technology, Shanxi University, Taiyuan, 030006, China

2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan, 030006, China

通讯作者: E⁃mail：lidy@sxu.edu.cn

收稿日期: 2019-05-28 网络出版日期: 2019-07-17

基金资助:

国家自然科学基金.  61672331,61573231,61432011,61806116
山西省重点研发计划.  201803D421024
山西省自然科学基金.  201801D221175
山西省高等学校科技创新项目.  201802014

Received: 2019-05-28 Online: 2019-07-17

摘要

对于数值型数据而言，邻域粗糙集模型是处理不确定信息的有效工具.现有的邻域粗糙集模型仅关注那些邻域中所有样本都属于同一个决策类的一致性情形，无法利用邻域中与多个决策类相交的边界样本所蕴含的信息.针对邻域粗糙集的这一局限性，将相容关系的极大相容块与邻域粗糙集相结合，选取样本邻域内的最大等价块作为最小的信息粒，通过重新定义邻域粗糙集的上下近似和属性重要度等概念，建立了一种基于极大相容块的邻域粗糙集模型.该模型可在更小的信息粒度下将原来边界样本转化成一致性样本来增大正域.运用前向贪婪策略构建了相应的属性约简算法.在七个公开的UCI数据集上的对比实验验证了提出模型的有效性.

关键词： 属性约简 ; 边界样本 ; 邻域粗糙集 ; 极大相容块

Abstract

For numerical data,neighborhood rough set model is an effective tool for dealing with uncertain information. The existing neighborhood rough set models only focus on the consistent situation that all samples in the neighborhood are in a single decision class. So they cannot make use of the information contained in the boundary samples with multiple decision class labels in the neighborhood. Aiming at this limitation of neighborhood rough set mode,we combine the concept of maximal consistent block of a tolerance relation with neighborhood rough set model and select the largest equivalent block in a sample neighborhood as the minimum information granule. We establish a new model,called neighborhood rough set model based on maximal consistent block,by redefining some concepts,such as upper and lower approximations, attribute importance and so on. The new model can enlarge the positive region by transforming the boundary samples into consistent samples in smaller information granules. In addition,we construct the corresponding attribute reduction algorithm by using the forward greedy strategy. The effectiveness of the proposed model is validated by the experiments on seven public UCI data sets.

Keywords： attribute reduction ; boundary sample ; neighborhood rough set ; maximal consistent block

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

本文引用格式

程永林, 李德玉, 王素格. 基于极大相容块的邻域粗糙集模型. 南京大学学报(自然科学版)[J], 2019, 55(4): 529-536 doi:10.13232/j.cnki.jnju.2019.04.002

Cheng Yonglin, Li Deyu, Wang Suge. Neighborhood rough set model based on maximal consistent blocks. Journal of nanjing University(Natural Science)[J], 2019, 55(4): 529-536 doi:10.13232/j.cnki.jnju.2019.04.002

粗糙集理论是属性约简的有力工具.基于二元关系类型，经典粗糙集理论已从等价关系拓展到相似关系、相容关系、模糊关系、优势关系等，并产生了对应的粗糙集拓展模型^{[1,2,3,4,5,6,7,8]}.

为了提高模型的抗噪性能，确定型粗糙集模型被发展出变精度粗糙集模型和概率粗糙集模型^{[8,9,10,11,12,13]}.近年来，张清华等^[14,15]将正域内样本个数与样本总数的比值作为参数，用来判断边界样本是否属于正域，提出了粗糙集的最优近似集.本质上，该模型利用全局参数代替了变精度模型中的人为参数.Fan et al^[16]提出将边界样本的相似类与决策类做交运算，选择最大的交集作为边界样本新的相似类，提出了最优决策粗糙集模型.

邻域粗糙集模型被广泛应用于数值型数据的属性约简任务，并取得了良好的效果^[1,3,4,5].Hu et al^[1,4,5]提出基于邻域粒化和粗糙逼近的数值型属性约简加速算法.针对符号型数据的非完备系统，Yee and Li^[17]和其他研究者^{[18,19,20,21]}提出了基于极大相容块粗糙集模型.

针对数值型数据，本文将极大相容块概念与邻域粗糙集相结合，在样本的邻域内寻找条件属性空间中的最大不可区分信息粒去刻画决策不确定性信息.相比于采用邻域粒度进行分析，它是在更小的粒度下，将原来某些边界样本转化成邻域粗糙集能处理的一致性样本来增大决策正域，从而提高属性约简的质量.依据上述思想，本文重新定义了邻域粗糙集的上下近似和属性重要度等概念，构建了基于极大相容块的邻域粗糙集模型，讨论了该模型的性质，并运用前向贪婪策略提出了相应的属性约简算法.对比实验表明，基于提出的模型所获属性约简用于分类，可获得更高的分类精度.

1 相关理论

1.1　邻域粗糙集

给定决策表 $S = 〈U, A, D〉$ ，

$U = {x_{1}, x_{2}, \dots, x_{m}}$ 为非空有限样本集合， $A = {a_{1}, a_{2}, \dots, a_{n}}$ 为非空有限的条件属性集， $D$ 为决策属性.

定义1^[1] 给定决策表 $S = 〈U, A, D〉$ ， $B \subseteq A$ 和实值参数 $δ \geq 0$ . $\forall x, y \in U$ ，称 $L_{B}^{δ}$ 为相容关系； $\forall x \in U$ ， $L_{B}^{δ} (x)$ 作为 $x$ 的 $δ$ 邻域.式(1)和式(2)中的 $d_{B} (x, y)$ 是 $x$ 和 $y$ 在属性集 $B$ 下的欧氏距离：

L_{B}^{δ} = {(x, y) \in U \times U | d_{B} (x, y) \leq δ, δ \geq 0}

(1)

L_{B}^{δ} (x) = {y | d_{B} (x, y) \leq δ, y \in U, δ \geq 0}

(2)

定义2^[1] 给定决策表 $S = 〈U, A, D〉$ ， $D$ 将 $U$ 划分为 $q$ 个等价类，称为决策类 $D_{1}, D_{2}, \dots,$

$D_{q}$ .对于 $B \subseteq A$ 且实值参数 $δ \geq 0$ 生成 $U$ 上的邻域关系 $N_{B}$ ，则称决策 $D$ 关于条件属性集 $B$ 的下近似是 $\underset{⇀}{N_{B}} D$ ，上近似是 $\bar{N_{B}} D$ ：

\underset{⇀}{N_{B}} D = \underset{⇀}{N_{B}} D_{1} ⋃ \underset{⇀}{N_{B}} D_{2} ⋃ \dots ⋃ \underset{⇀}{N_{B}} D_{q} = \cup_{i = 1}^{q} \underset{⇀}{N_{B}} D_{i}

(3)

\bar{N_{B}} D = \bar{N_{B}} D_{1} ⋃ \bar{N_{B}} D_{2} ⋃ \dots ⋃ \bar{N_{B}} D_{q} = \cup_{i = 1}^{q} \bar{N_{B}} D_{i}

(4)

这里：

\underset{̲}{N_{B}} D_{i} = {x | L_{B}^{δ} (x) \subseteq D_{i}, x \in U}

\bar{N_{B}} D_{i} = {x | L_{B}^{δ} (x) ⋂ D_{i} \neq \emptyset, x \in U}

由上下近似的定义可得正域 $P O S_{B} (D)$ 、边界域 $B N_{B} (D)$ ：

P O S_{B} (D) = \underset{̲}{N_{B}} D

(5)

B N_{B} (D) = \bar{N_{B}} D - \underset{̲}{N_{B}} D

(6)

定义3^[1] 给定决策表 $S = 〈U, A, D〉$ ， $B \subseteq$

$A$ 决策类 $D$ 对属性集 $B$ 的依赖程度是属性依赖度 $r_{B} (D)$ .若属性 $a \in B$ 则属性 $a$ 对于属性子集 $B$ 的内部重要度是 $S i g_{1} (a, B, D)$ .若属性 $a \in A - B$ 则属性 $a$ 对于属性子集 $B$ 的外部属性重要度是 $S i g_{2} (a, B, D)$ .如式(7)至式(9)所示：

r_{B} (D) = \frac{| P O S_{B} (D) |}{| U |}

(7)

S i g_{1} (a, B, D) = r_{B} (D) - r_{B - a} (D)

(8)

S i g_{2} (a, B, D) = r_{B ⋃ a} (D) - r_{B} (D)

(9)

1.2　极大相容块

定义4^[17,19] 给定决策表 $S = 〈U, A, D〉$ ， $B \subseteq A$ ， $X \subseteq U$ 且实值参数 $δ \geq 0$ .如果对于 $\forall x, y \in X$ ，均满足相容关系 $L_{B}^{δ}$ ，则称 $X$ 关于 $B$ 是相容的.如果对于U不存在子集 $Y$ ，使得 $X \subset Y$ ，且 $Y$ 也是关于 $B$ 相容的，则称 $X$ 为 $B$ 的一个极大相容块 $C_{B}$ . $C_{B}$ 是一种极大的样本集合，即在给定可利用信息下，该样本集合下的所有样本都是不可区分的.对于 $\forall x_{i} \in U$ ，在 $B \subseteq A$ 下确定的所有包含 $x_{i}$ 的集合为 $C_{B} (x_{i})$ ：

C_{B} = {\cup_{i = 1}^{m} C_{B} (x_{i}), x_{i} \in U, m = | U |}

(10)

根据定义4，采取蛮力搜索的方式计算每个样本与其他样本之间是否满足相容关系可得到一系列满足相容关系 $L_{B}^{δ}$ 的二元对，然后计算其他样本与二元对中的每个样本是否满足相容关系得到三元对.以此类推，将得到的一致块全部并起来求得 $C_{B}$ .

例1 样本集合 $X = {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}}$ ， $X$ 在属性集 $B$ 下满足实值参数 $δ$ 的相容关系的矩阵表示如表1所示，表中“1”表示两个对象间的距离小于参数 $δ$ ，“0”表示两个对象间的距离大于参数 $δ$ .由定义4和表1可得：

表1 $X$ 的相容关系矩阵

Table 1 The compatible relation matrix of X

	x₁	x₂	x₃	x₄	x₅
x₁	1	1	1	0	1
x₂	1	1	0	0	0
x₃	1	0	1	0	1
x₄	0	0	0	1	0
x₅	1	0	1	0	1

新窗口打开| 下载CSV

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

如图1所示， $C_{B} = {{x_{1}, x_{3}, x_{5}}, {x_{1}, x_{2}}$ ， ${x_{4}}}$ ，则 $X$ 的极大相容块可以看作是几个等价块的集合，即 ${x_{1}, x_{3}, x_{5}}$ ， ${x_{1}, x_{2}}$ 和 ${x_{4}}$ 的集合.而对于 $x_{1}$ 而言，

C_{B} (x_{1}) = {{x_{1}, x_{3}, x_{5}}, {x_{1}, x_{2}}}

L_{B}^{δ} (x_{1}) = {x_{1}, x_{2}, x_{3}, x_{5}}

图1

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

图1 例1中样本分布图

Fig.1 The distribution of samples in example 1

$L_{B}^{δ} (x_{1})$ 被分成 ${x_{1}, x_{3}, x_{5}}$ 和 ${x_{1}, x_{2}}$ 两个等价块且 $x_{1}$ 同时属于两个等价块.

2 基于极大相容块的邻域粗糙集模型

2.1　NMCBRS( Neighborhood Rough Set Model Based on Maximal Consistent Blocks)

定义5 给定决策表 $S = 〈U, A, D〉$ 和实值参数 $δ \geq 0$ ， $B \subseteq A$ ， $\forall x \in U$ ，由定义4可得极大相容块 $C_{B}$ 和 $C_{B} (x)$ . $C_{B} (x)$ 中包含一系列的一致性块，也是等价块，用 $T$ 表示，即：

C_{B} (x) = {T_{1}, T_{2}, \dots, T_{s} | s = |C_{B} (x)|}

使用 $C_{B} (x)$ 中的最大等价块 $M L_{B} (x)$ 作为描述 $x$ 的最小信息粒， $M L_{B} (x)$ 如式(11)所示：

\begin{array}{l} M L_{B} (x) = \\ {T_{p} | p = a r g m a x {T_{1}, T_{2}, \dots, T_{s} | s = |C_{B} (x)|}} \end{array}

(11)

定义6 给定决策表 $S = 〈U, A, D〉$ ， $D$ 将 $U$ 划分为 $q$ 个等价类，称为决策类： $D_{1}, D_{2}, \dots,$

$D_{q}$ .给定实值参数 $δ \geq 0$ , $B \subseteq A$ ，则决策 $D$ 关于 $B$ 下的上近似是 $\bar{R N_{B}} D$ ，下近似是 $\underset{̲}{R N_{B}} D$ ：

\underset{̲}{R N_{B}} D_{i} = {x | M L_{B} (x) \subseteq D_{i}, x \in U}

(12)

\bar{R N_{B}} D_{i} = {x | M L_{B} (x) ⋂ D_{i} \neq \emptyset, x \in U}

(13)

\underset{̲}{R N_{B}} D =

\underset{̲}{R N_{B}} D_{1} ⋃ \underset{̲}{R N_{B}} D_{2} ⋃ \dots ⋃ \underset{̲}{R N_{B}} D_{q} = \cup_{i = 1}^{q} \underset{̲}{R N_{B}} D_{i}

(14)

\bar{R N_{B}} D =

\bar{R N_{B}} D_{1} ⋃ \bar{R N_{B}} D_{2} ⋃ \dots ⋃ \bar{R N_{B}} D_{q} = \cup_{i = 1}^{q} \bar{R N_{B}} D_{i}

(15)

由上近似和下近似的定义可得正域 $R P O S_{B} (D)$ 、边界域 $R B N_{B} (D)$ :

R P O S_{B} (D) = \underset{̲}{R N_{B}} D

(16)

R B N_{B} (D) = \bar{R N_{B}} D - \underset{̲}{R N_{B}} D

(17)

定义7 给定决策表 $S = 〈U, A, D〉$ ， $B \subseteq A$ ，决策类 $D$ 对属性集 $B$ 的依赖程度是属性依赖度 $R r_{B} (D)$ ：

R r_{B} (D) = \frac{| R P O S_{B} (D) |}{| U |}

(18)

如果 $C \subseteq B \subseteq A$ ，满足 $R r_{C} (D) \geq$ $R r_{B} (D)$ ，则称在属性集 $C$ 下对于全体样本 $U$ 的辨别能力与在属性集 $B$ 下的辨别能力相等，即属性集 $B - C$ 为冗余属性，可以将属性集 $B - C$ 约简掉.当属性 $a \in B$ ，则属性 $a$ 对于属性集 $B$ 的内部重要度是 $R S i g_{1} (a, B, D)$ .当属性 $a \in A - B$ ，属性 $a$ 对于属性子集 $B$ 的外部属性重要度是 $R S i g_{2} (a, B, D)$ ：

R S i g_{1} (a, B, D) = R r_{B} (D) - R r_{B - a} (D)

(19)

R S i g_{2} (a, B, D) = R r_{B ⋃ a} (D) - R r_{B} (D)

(20)

2.2　性质

性质1 给定决策表 $S = 〈U, A, D〉$ ， $B_{1} \subseteq B_{2} \subseteq A$ 在相同的实值参数 $δ$ 下， $\forall x \in U$ ， $M L_{B_{1}} (x) \supseteq M L_{B_{2}} (x)$ .

证明由 $B_{1} \subseteq B_{2} \subseteq A$ ，可得 $\forall x, y \in U$ ，

$d_{B_{1}} (x, y) \leq d_{B_{2}} (x, y)$ .如果 $d_{B_{2}} (x, y) \leq δ$ ，则 $d_{B_{1}} (x, y) \leq δ$ 一定成立.反之，如果 $d_{B_{1}} (x, y) \leq$ $δ$ ，则 $d_{B_{2}} (x, y) \leq δ$ 不一定成立.由此可以推出 $M L_{B_{1}} (x) \supseteq M L_{B_{2}} (x)$ .

性质2 给定决策表 $S = 〈U, A, D〉$ ， $B_{1} \subseteq B_{2} \subseteq A$ 在相同的参数 $δ$ 下，可得：

(1) $\underset{̲}{R N_{B_{1}}} D \subseteq \underset{̲}{R N_{B_{2}}} D$ ；

(2) $R P O S_{B_{1}} (D) \subseteq R P O S_{B_{2}} (D)$ ；

(3) $R r_{B_{1}} (D) \leq R r_{B_{2}} (D)$ .

证明由性质1可知 $B_{1} \subseteq B_{2} \subseteq A$ ，在相同的实值参数 $δ$ 下， $M L_{B_{1}} (x) \supseteq M L_{B_{2}} (x)$ ，由式(12)和式(14)即可得到：

\underset{̲}{R N_{B_{1}}} D \subseteq \underset{̲}{R N_{B_{2}}} D

再由式(16)可以推出：

R P O S_{B_{1}} (D) \subseteq R P O S_{B_{2}} (D)

在 $U$ 一定的条件下，根据式(18)可推出：

R r_{B_{1}} (D) \leq R r_{B_{2}} (D)

3 算法

输入：决策表 $S 〈U, A, D〉$ ，参数 $δ$

输出：约简后的属性子集redl

1.划分等价类 $U / D = \{D_{1}, D_{2}, \dots, D_{q}\}$ ；

2. $r e d l = \emptyset$ ；

3. for $a_{i} \in A$

4. 用式(19)计算内部属性重要度 $R S i g_{1} (a_{i}, A, D)$ ；

5. if $R S i g_{1} (a_{k}, A, D) > 0$

6. $a_{k} \to r e d l, B = A - r e d l$ ；

7. end if

8.end for

9.用式(18)计算 $R r_{A} (D)$ ；

10.while $B \neq \emptyset$

11. 用式(18)计算 $R r_{r e d l} (D)$ ；

12. if $R r_{r e d l} (D) < R r_{A} (D)$

13. for each $a_{m} \in B$

14. 用式(20)计算外部属性重要度 $R S i g_{2} (a_{m}, r e d l, D)$ ；

15. end for

16. $R S i g_{2} (a_{n}, r e d l, D) = m a x (R S i g_{2} (a_{m},$

r e d l, D))

r e d l \to r e d l ⋃ a_{n}

，

B = A - r e d l

；

17. else

18. break；

19. end if

20.end while

21.return redl；

假设给定的决策表中有 $U$ 个样本， $D$ 个类别， $C$ 个属性，属性子集中包含 $d$ 个属性，判别所有样本是否属于某个决策类的时间复杂度为 $O (U D)$ ，计算加入候选属性后的样本的最大等价块的时间复杂度为 $O (U^{3})$ ，那该算法的时间复杂度为 $O (U^{3} C d)$ .

4 实验及结果分析

4.1　实验设置

实验使用七个UCI数据集上的数值型数据集进行测试，数据集的信息如表2所示.

表2 数据集描述

Table 2 Description of datasets

数据集	样本数	属性数	类别数
Wine	178	13	3
Wdbc	569	30	2
Glass	214	10	6
Wpbc	198	32	2
Ionos	351	33	2
Snoar	208	60	2
Cancer	683	9	2

新窗口打开| 下载CSV

实验采用近期提出类似的方法如经典邻域粗糙集(Neighborhood Rough Set,NRS)^[1]、变精度邻域粗糙集(Variable Precision Neighborhood Rough Set,VP⁃NRS)^[9]、最优决策邻域粗糙集方法(Max⁃Decision Neighborhood Rough Set,MAX⁃NRS)^[16]与本文中提出的新的粗糙集模型NMCBRS以及原始数据集(Raw Data Set,RAW)进行对比.主要的对比数据是使用前向贪婪算法进行属性约简后得到的属性子集的属性个数以及使用这些属性子集在KNN(K⁃Nearest Neighbors)和SVM(Support Vector Machine)分类器上的分类精度进行比较，以此来验证基于极大相容块的邻域粗糙集属性约简算法的有效性.

4.2　参数设置

邻域参数 $δ$ 以0.1为步长，从0到1之间寻找最佳邻域半径.针对变精度邻域粗糙集方法中精度参数 $α$ 的设置，将从0到1以0.01为步长，寻找最佳的参数.采用十折交叉验证对最优属性子集进行分类测试，对于KNN分类器而言，选取参数 $k = 3$ 的KNN分类器进行分类.

4.3　实验结果

实验结果如表3至表6所示.

表3 最优属性子集

Table 3 Best feature subsets from different models

Data	NRS	VP⁃NRS	MAX⁃NRS	NMCBRS
Wine	1,13,12,11,5,2,3, 7,4	1,12,13,2,5,9,3	1,7,3,13,4,10,5,9	1,12,13,5,2,11,3
Wdbc	1,28,22,12,25,10, 19,2	25,23,27,2,10,30,14,19, 24,28,15,5,22,21,11,9,1, 8,3,12,18,4,6,7,26,13	1,25,22,7,29,9,15, 3,4,12,2	1,28,22,26
Glass	1,9,2,10,5,6,4, 3,7,8	1,3,5,6,10	1,7,4	1,10
Wpbc	1,29,3,2,32,12,3, 10,6,26	1,11,9,13,3,10,2	1,13,12,6,10,32,5, 23,26,2	1,20,12,26,6
Ionos	1,26,8,2,31,6,5, 22,3,32,4,15,7	1,2,3,6,12,11,8,15, 5,4,7,9,10,28,13	1,2,3,12,6,28,4,8,5, 15,24	2,28,29,20, 21,1,19,4
Snoar	1,54,45,11,27,24, 37,17,29,13,12,39, 8,25,26,22,18,2	1,12,25,17,37,29,8, 27,40,22,2	1,12,24,16,26,5,56, 9,29,48,14,10,27,46, 23,2	1,23,22,36,19,12,13,45, 2
Cancer	6,1,2,8,4,5,3	1	3,6,8,5,4	6,1,2,4

新窗口打开| 下载CSV

表6 最优属性子集在KNN(k=3)下的分类精度

Table 6 The classification accuracy with KNN(k=3)

Data	RAW	NRS	VP⁃NRS	MAX⁃NRS	NMCBRS
Wine	94.21±6.77	97.60±4.47	94.73±6.08	97.89±2.72	97.44±3.65
Wdbc	97.23±1.81	96.02±2.00	96.71±2.76	96.01±2.18	95.26±2.40
Glass	89.61±5.17	90.67±2.68	87.87±7.87	93.11±6.49	93.71±6.45
Wpbc	70.14±8.79	76.44±11.80	76.89±8.58	75.42±11.91	81.82±7.93
Ionos	83.52±9.53	86.01±6.26	85.01±4.49	85.18±5.19	89.18±3.97
Snoar	80.23±9.65	81.40±9.18	80.14±8.43	81.32±6.71	81.51±9.06
Cancer	96.62±3.94	96.38±6.38	89.00±4.75	95.78±1.51	96.68±2.02
Average	87.36±6.52	89.21±6.11	87.19±6.13	89.24±5.24	90.85±5.21

新窗口打开| 下载CSV

七个UCI数据集在NRS，VP⁃NRS，MAX⁃NRS与NMCBRS模型上进行属性约简后的最优属性子集如表3所示，其中最优属性子集的排列是按属性重要度的值由大到小排列，从中可以发现同一数据集在不同的模型度量下的属性重要度不同.

表4至表6中的RAW表示的是没有采用属性约简方法的原始数据集.表4所示的是七个数据集在不同的模型下最优属性子集的属性个数.从中可以发现相对于其他三种方法，我们提出的NMCBRS模型约简后的最优属性子集的属性个数最少.原始数据平均有26个属性，经过NMCBRS模型约简后平均只剩5.57个属性，减少78%的冗余属性.

表4 最优属性子集个数

Table 4 The number of best feature subsets from different models

Data	RAW	NRS	VP⁃NRS	MAX⁃NRS	NMCBRS
Wine	13	9	7	8	7
Wdbc	30	8	26	11	4
Glass	10	10	5	3	2
Wpbc	32	10	7	10	5
Ionos	33	13	15	11	8
Snoar	60	20	11	16	9
Cancer	9	7	1	5	4
Average	26.71	11	10.29	9.14	5.57

新窗口打开| 下载CSV

表5和表6是约简后的最优属性子集在KNN和SVM分类器的实验结果，表中加粗的数据是性能最佳的分类结果.表5中七个数据集中有六个数据集是NMCBRS模型的精度最高，只有Ionos数据集中NMCBRS模型与其他模型的精度相差不大，但是最优属性子集属性个数比其他模型的都少.同理，表6的Wdbc数据集中NMCBRS模型在KNN分类器上的精度表现一样.从表5和表6可以看出，NMCBRS模型在平均分类精度上高于NRS，VP⁃NRS，MAX⁃NRS.

表5 最优属性子集在SVM下的分类精度

Table 5 The classification accuracy with SVM

Data	RAW	NRS	VP⁃NRS	MAX⁃NRS	NMCBRS
Wine	93.68±4.84	97.36±3.72	95.26±3.88	95.20±6.31	97.89±2.42
Wdbc	94.62±4.53	95.15±1.77	95.15±2.26	94.63±2.09	95.43±2.08
Glass	77.55±8.57	78.41±6.01	80.33±5.08	77.82±6.49	80.92±6.57
Wpbc	76.00±12.28	75.94±9.80	75.94±9.84	75.94±9.84	76.42±7.59
Ionos	84.98±12.34	87.45±5.00	87.45±5.46	87.72±5.48	87.57±4.67
Snoar	71.32+10.98	72.82±10.08	73.68±9.78	70.62±12.77	75.96±10.20
Cancer	96.34±3.77	96.50±2.42	85.69±4.63	95.93±1.83	96.71±2.40
Average	84.92±8.18	86.23±5.54	84.78±5.84	85.40±6.40	86.61+5.45

新窗口打开| 下载CSV

综上所述，我们提出的NMCBRS模型能够在保持更高的分类精度下约简更多的冗余属性，极大地降低数据的维度.

5 结束语

本文对经典邻域粗糙集模型进行属性约简过程中忽视了边界样本所蕴含的信息，导致属性约简不充分的问题，提出了基于极大相容块的邻域粗糙集模型.该模型在更小的粒度下度量和利用边界样本的信息，保证在保持更高的分类精度的条件下约简掉更多的冗余属性，进一步完善了利用邻域粗糙集进行属性约简的方法.下一步，将在新的模型下对前向贪婪算法进行改进，减小时间复杂度.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Q H

,Yu

D R

, Liu

J F

,et al.

Neighborhood rough set based heterogeneous feature subset selection

Information Sciences,2008,178(18)：3577-3594.

[本文引用: 7]

[2]

Qian

Y H

,Liang

J Y

,Pedrycz

,et al.

Positive approximation： an accelerator for attribute reduction in rough set theory

Artificial Intelligence,2010,174(9-10)：597-618.

[本文引用: 1]

[3]

Wang

,Qian

Y H

,Liang

X Y

,et al.

Local neighborhood rough set

Knowledge⁃Based Systems,2018,153：53-64.

[本文引用: 2]

[4]

胡清华,赵辉,于达仁.

基于邻域粗糙集的符号与数值属性快速约简算法

模式识别与人工智能,2008,21(6)：730-738.

[本文引用: 3]

Hu Q H, Zhao H,Yu D R.

Efficient symbolic and numerical attribute reduction with neighborhood rough sets.

Pattern Recognition &Artificial Intelligence,2008,21(6)：732-738.

[本文引用: 3]

[5]

陈铁桥，柳嫁航，朱锋等.

适用于遥感分类的多邻域粗糙集加权特征提取方法

武汉大学学报(信息科学版)，2018,43(2)：311-317.

[本文引用: 3]

Chen T Q,Liu J H,Zhu F,et al.

A novel multi⁃radius neighbor⁃hood rough set weighted feature extraction method for remote sensing image classification.

Geomatics and Information Science of Wuhan University,2018,43(2)：311-317.

[本文引用: 3]

[6]

Suo

M L

,An

R M

,Zhou

,et al.

Grid⁃clustered rough set model for self⁃learning and fast reduction

Pattern Recognition Letters,2018,106：61-68.

[本文引用: 1]

[7]

Luo

,Li

T R

,Chen

H M

,et al.

Incremental rough set approach for hierarchical multicriteria classification

Information Sciences,2018,429：72-87.

[本文引用: 1]

[8]

Y Y

,Luo

X Y

,Li

X L

,et al.

Selection of rich model steganalysis features based on decision rough set α⁃positive region reduction

IEEE Transactions on Circuits and Systems for Video Technology,2018,29(2)：336-350.

[本文引用: 2]

[9]

J S

,Wu

W Z

,Zhang

W X

Approaches to knowledge reduction based on variable precision rough set model

Information Sciences,2004,159(3-4)：255-272.

[本文引用: 2]

[10]

Yao

Y Y

Probabilistic rough set approximations

International Journal of Approximate Reasoning,2008,49(2)：255-271.

[本文引用: 1]

[11]

Kang

,Wu

S X

,Li

Y W

,et al.

A variable precision grey⁃based multi⁃granulation rough set model and attribute reduction

Knowledge⁃Based Systems,2018,148：131-145.

[本文引用: 1]

[12]

Liu

J B

,Zhao

P Y

,Liu

,et al.

Multi⁃granularity fuzzy soft probability rough sets∥2018 Chinese Control And Decision Conference

Shenyang,China：IEEE,2018：6204-6209.

[本文引用: 1]

[13]

Suo

Z Y

,Cheng

S Y

,Ren

J S

Probability rough set model based on the semantic in set⁃valued information system∥2^nd IEEE International Conference on Computer and Communications

Chengdu,China：IEEE,2017：1244-1249.

[本文引用: 1]

[14]

张清华,薛玉斌,王国胤.

粗糙集的最优近似集

软件学报,2016,27(2)：295-308.

[本文引用: 1]

Zhang Q H,Xue Y B,Wang G Y.

Optimal approximation sets of rough sets.

Journal of Software,

2016,27(2)：295-308.

[本文引用: 1]

[15]

杨帅华,张清华.

粗糙集近似集的KNN文本分类算法研究

小型微型计算机系统,2017,38(10)：2192-2196.

[本文引用: 1]

Yang S H,Zhang Q H.

Research on k⁃nearest neighbor text classification algorithm of approximation set of rough set.

Journal of Chinese Computer Systems,2017,38(10)：2192-2196.

[本文引用: 1]

[16]

Fan

X D

,Zhao

W D

,Wang

C Z

,et al.

Attribute reduction based on max⁃decision neighborhood rough set model

Knowledge⁃Based Systems,2018,151：16-23.

[本文引用: 2]

[17]

Yee

,Li

D Y

Maximal consistent block technique for rule acquisition in incomplete information systems

Information Sciences,2003,153：85-106.

[本文引用: 2]

[18]

Clark

P G

,Gao

,Grzymala⁃Busse

J W

,et al.

Characteristic sets and generalized maximal consistent blocks in mining incomplete data

Information Sciences,2018,453：66-79.

[本文引用: 1]

[19]

江效尧,程玉胜,胡林生.

基于极大相容块的粗糙性度量及其属性约简

合肥工业大学学报(自然科学版),2012,35(4)：476-480.

[本文引用: 2]

Jiang X Y,Cheng Y S,Hu L S.

Roughness measure and attribute reduction based on maximal consistent block.

Journal of Hefei University of Technology(Natural Science),2012,35(4)：476-480.

[本文引用: 2]

[20]

黄治国,张天伍.

基于极大团的不完备系统规则获取方法

重庆邮电大学学报(自然科学版),2017,29(2)：279-284.

[本文引用: 1]

Huang Z G,Zhang T W.

Maximal clique⁃based method for acquiring association rules in incomplete system.

Journal of Chongqing University of Posts and Telecommu⁃nications(Natural Science Edition),2017,29(2)：279-284.

[本文引用: 1]

[21]

钱宇华,梁吉业,王锋.

面向非完备决策表的正向近似特征选择加速算法

计算机学报,2011,34(3)：435-442.

[本文引用: 1]

Qian Y H,Liang J Y,Wang F.

A positive⁃approximation based accelerated algori⁃thm to feature selection from incomplete decision tables.

Chinese Journal of Computers,2011,34(3)：435-442.

[本文引用: 1]

Neighborhood rough set based heterogeneous feature subset selection

2008

... 粗糙集理论是属性约简的有力工具.基于二元关系类型，经典粗糙集理论已从等价关系拓展到相似关系、相容关系、模糊关系、优势关系等，并产生了对应的粗糙集拓展模型^{[1,2,3,4,5,6,7,8]}. ...

... 邻域粗糙集模型被广泛应用于数值型数据的属性约简任务，并取得了良好的效果^[1,3,4,5].Hu et al^[1,4,5]提出基于邻域粒化和粗糙逼近的数值型属性约简加速算法.针对符号型数据的非完备系统，Yee and Li^[17]和其他研究者^{[18,19,20,21]}提出了基于极大相容块粗糙集模型. ...

... [1,4,5]提出基于邻域粒化和粗糙逼近的数值型属性约简加速算法.针对符号型数据的非完备系统，Yee and Li^[17]和其他研究者^{[18,19,20,21]}提出了基于极大相容块粗糙集模型. ...

... 定义1^[1] 给定决策表

S = 〈U, A, D〉

，

B \subseteq A

和实值参数

δ \geq 0

\forall x, y \in U

，称

L_{B}^{δ}

为相容关系；

\forall x \in U

，

L_{B}^{δ} (x)

作为

x

的

δ

邻域.式(1)和式(2)中的

d_{B} (x, y)

是

x

和

y

在属性集

B

下的欧氏距离： ...

... 定义2^[1] 给定决策表

S = 〈U, A, D〉

，

D

将

U

划分为

q

个等价类，称为决策类

D_{1}, D_{2}, \dots,

...

... 定义3^[1] 给定决策表

S = 〈U, A, D〉

，

B \subseteq

...

... 实验采用近期提出类似的方法如经典邻域粗糙集(Neighborhood Rough Set,NRS)^[1]、变精度邻域粗糙集(Variable Precision Neighborhood Rough Set,VP⁃NRS)^[9]、最优决策邻域粗糙集方法(Max⁃Decision Neighborhood Rough Set,MAX⁃NRS)^[16]与本文中提出的新的粗糙集模型NMCBRS以及原始数据集(Raw Data Set,RAW)进行对比.主要的对比数据是使用前向贪婪算法进行属性约简后得到的属性子集的属性个数以及使用这些属性子集在KNN(K⁃Nearest Neighbors)和SVM(Support Vector Machine)分类器上的分类精度进行比较，以此来验证基于极大相容块的邻域粗糙集属性约简算法的有效性. ...

Positive approximation： an accelerator for attribute reduction in rough set theory

2010

Local neighborhood rough set

2018

基于邻域粗糙集的符号与数值属性快速约简算法

2008

... ,4,5]提出基于邻域粒化和粗糙逼近的数值型属性约简加速算法.针对符号型数据的非完备系统，Yee and Li^[17]和其他研究者^{[18,19,20,21]}提出了基于极大相容块粗糙集模型. ...

基于邻域粗糙集的符号与数值属性快速约简算法

2008

适用于遥感分类的多邻域粗糙集加权特征提取方法

2018

... ,5]提出基于邻域粒化和粗糙逼近的数值型属性约简加速算法.针对符号型数据的非完备系统，Yee and Li^[17]和其他研究者^{[18,19,20,21]}提出了基于极大相容块粗糙集模型. ...

适用于遥感分类的多邻域粗糙集加权特征提取方法

2018

Grid?clustered rough set model for self?learning and fast reduction

2018

Incremental rough set approach for hierarchical multicriteria classification

2018

Selection of rich model steganalysis features based on decision rough set α?positive region reduction

2018

... 为了提高模型的抗噪性能，确定型粗糙集模型被发展出变精度粗糙集模型和概率粗糙集模型^{[8,9,10,11,12,13]}.近年来，张清华等^[14,15]将正域内样本个数与样本总数的比值作为参数，用来判断边界样本是否属于正域，提出了粗糙集的最优近似集.本质上，该模型利用全局参数代替了变精度模型中的人为参数.Fan et al^[16]提出将边界样本的相似类与决策类做交运算，选择最大的交集作为边界样本新的相似类，提出了最优决策粗糙集模型. ...

Approaches to knowledge reduction based on variable precision rough set model

2004

Probabilistic rough set approximations

2008

A variable precision grey?based multi?granulation rough set model and attribute reduction

2018

Multi?granularity fuzzy soft probability rough sets∥2018 Chinese Control And Decision Conference

2018

Probability rough set model based on the semantic in set?valued information system∥2^nd IEEE International Conference on Computer and Communications

2017

粗糙集的最优近似集

2016

粗糙集的最优近似集

2016

粗糙集近似集的KNN文本分类算法研究

2017

粗糙集近似集的KNN文本分类算法研究

2017

Attribute reduction based on max?decision neighborhood rough set model

2018

Maximal consistent block technique for rule acquisition in incomplete information systems

2003

... 定义4^[17,19] 给定决策表

S = 〈U, A, D〉

，

B \subseteq A

，

X \subseteq U

且实值参数

δ \geq 0

.如果对于

\forall x, y \in X

，均满足相容关系

L_{B}^{δ}

，则称

X

关于

B

是相容的.如果对于U不存在子集

Y

，使得

X \subset Y

，且

Y

也是关于

B

相容的，则称

X

为

B

的一个极大相容块

C_{B}

C_{B}

是一种极大的样本集合，即在给定可利用信息下，该样本集合下的所有样本都是不可区分的.对于

\forall x_{i} \in U

，在

B \subseteq A

下确定的所有包含

x_{i}

的集合为

C_{B} (x_{i})

： ...

Characteristic sets and generalized maximal consistent blocks in mining incomplete data

2018

基于极大相容块的粗糙性度量及其属性约简

2012

... 定义4^[17,19] 给定决策表

S = 〈U, A, D〉

，

B \subseteq A

，

X \subseteq U

且实值参数

δ \geq 0

.如果对于

\forall x, y \in X

，均满足相容关系

L_{B}^{δ}

，则称

X

关于

B

是相容的.如果对于U不存在子集

Y

，使得

X \subset Y

，且

Y

也是关于

B

相容的，则称

X

为

B

的一个极大相容块

C_{B}

C_{B}

是一种极大的样本集合，即在给定可利用信息下，该样本集合下的所有样本都是不可区分的.对于

\forall x_{i} \in U

，在

B \subseteq A

下确定的所有包含

x_{i}

的集合为

C_{B} (x_{i})

： ...

基于极大相容块的粗糙性度量及其属性约简

2012

... 定义4^[17,19] 给定决策表

S = 〈U, A, D〉

，

B \subseteq A

，

X \subseteq U

且实值参数

δ \geq 0

.如果对于

\forall x, y \in X

，均满足相容关系

L_{B}^{δ}

，则称

X

关于

B

是相容的.如果对于U不存在子集

Y

，使得

X \subset Y

，且

Y

也是关于

B

相容的，则称

X

为

B

的一个极大相容块

C_{B}

C_{B}

是一种极大的样本集合，即在给定可利用信息下，该样本集合下的所有样本都是不可区分的.对于

\forall x_{i} \in U

，在

B \subseteq A

下确定的所有包含

x_{i}

的集合为

C_{B} (x_{i})

： ...

基于极大团的不完备系统规则获取方法

2017

基于极大团的不完备系统规则获取方法

2017

面向非完备决策表的正向近似特征选择加速算法

2011

面向非完备决策表的正向近似特征选择加速算法

2011

〈

〉