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

doi:10.13232/j.cnki.jnju.2019.04.002

南京大学学报(自然科学版) ›› 2019, Vol. 55 ›› Issue (4): 529–536.doi: 10.13232/j.cnki.jnju.2019.04.002

所属专题：测试专题

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

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

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

收稿日期:2019-05-28 出版日期:2019-07-30 发布日期:2019-07-23
通讯作者: 李德玉 E-mail:lidy@sxu.edu.cn
基金资助:
国家自然科学基金(61672331,61573231,61432011,61806116);山西省重点研发计划(201803D421024);山西省自然科学基金(201801D221175);山西省高等学校科技创新项目(201802014)

Neighborhood rough set model based on maximal consistent blocks

Yonglin Cheng¹,Deyu Li^1,²(),Suge Wang^1,²

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

Received:2019-05-28 Online:2019-07-30 Published:2019-07-23
Contact: Deyu Li E-mail:lidy@sxu.edu.cn

摘要/Abstract

摘要：

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

Key words: attribute reduction, boundary sample, neighborhood rough set, maximal consistent block

中图分类号:

TP391

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

Yonglin Cheng, Deyu Li, Suge Wang. Neighborhood rough set model based on maximal consistent blocks[J]. Journal of Nanjing University(Natural Sciences), 2019, 55(4): 529–536.

图/表 7

表1

图1

表2

表3

表6

表4

表5

参考文献 21

1	HuQ H,YuD R, LiuJ F,et al. Neighborhood rough set based heterogeneous feature subset selection. Information Sciences,2008,178(18)：3577-3594.
2	QianY H,LiangJ Y,PedryczW,et al. Positive approximation： an accelerator for attribute reduction in rough set theory. Artificial Intelligence,2010,174(9-10)：597-618.
3	WangQ,QianY H,LiangX Y,et al. Local neighborhood rough set. Knowledge?Based Systems,2018,153：53-64.
4	胡清华,赵辉,于达仁. 基于邻域粗糙集的符号与数值属性快速约简算法. 模式识别与人工智能,2008,21(6)：730-738.
	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.
5	陈铁桥，柳嫁航，朱锋等. 适用于遥感分类的多邻域粗糙集加权特征提取方法. 武汉大学学报(信息科学版)，2018,43(2)：311-317.
	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.
6	SuoM L,AnR M,ZhouD,et al. Grid?clustered rough set model for self?learning and fast reduction. Pattern Recognition Letters,2018,106：61-68.
7	LuoC,LiT R,ChenH M,et al. Incremental rough set approach for hierarchical multicriteria classification. Information Sciences,2018,429：72-87.
8	MaY Y,LuoX Y,LiX 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.
9	MiJ S,WuW Z,ZhangW X. Approaches to knowledge reduction based on variable precision rough set model. Information Sciences,2004,159(3-4)：255-272.
10	YaoY Y. Probabilistic rough set approximations. International Journal of Approximate Reasoning,2008,49(2)：255-271.
11	KangY,WuS X,LiY W,et al. A variable precision grey?based multi?granulation rough set model and attribute reduction. Knowledge?Based Systems,2018,148：131-145.
12	LiuJ B,ZhaoP Y,LiuJ,et al. Multi?granularity fuzzy soft probability rough sets∥2018 Chinese Control And Decision Conference. Shenyang,China：IEEE,2018：6204-6209.
13	SuoZ Y,ChengS Y,RenJ 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.
14	张清华,薛玉斌,王国胤. 粗糙集的最优近似集. 软件学报,2016,27(2)：295-308.
	Zhang Q H,Xue Y B,Wang G Y.Optimal approximation sets of rough sets. Journal of Software,2016,27(2)：295-308.
15	杨帅华,张清华. 粗糙集近似集的KNN文本分类算法研究. 小型微型计算机系统,2017,38(10)：2192-2196.
	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.
16	FanX D,ZhaoW D,WangC Z,et al. Attribute reduction based on max?decision neighborhood rough set model. Knowledge?Based Systems,2018,151：16-23.
17	YeeL,LiD Y. Maximal consistent block technique for rule acquisition in incomplete information systems. Information Sciences,2003,153：85-106.
18	ClarkP G,GaoC,Grzymala?BusseJ W,et al. Characteristic sets and generalized maximal consistent blocks in mining incomplete data. Information Sciences,2018,453：66-79.
19	江效尧,程玉胜,胡林生. 基于极大相容块的粗糙性度量及其属性约简. 合肥工业大学学报(自然科学版),2012,35(4)：476-480.
	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.
20	黄治国,张天伍. 基于极大团的不完备系统规则获取方法. 重庆邮电大学学报(自然科学版),2017,29(2)：279-284.
	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.
21	钱宇华,梁吉业,王锋. 面向非完备决策表的正向近似特征选择加速算法. 计算机学报,2011,34(3)：435-442.
	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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

	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

数据集	样本数	属性数	类别数
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

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

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

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

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

Neighborhood rough set model based on maximal consistent blocks

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 21

相关文章 12

Metrics

本文评价

推荐阅读 7

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

[1]	刘鑫,胡军,张清华. 属性组序下基于代价敏感的约简方法[J]. 南京大学学报(自然科学版), 2020, 56(4): 469-479.
[2]	张龙波, 李智远, 杨习贝, 王怡博. 决策代价约简求解中的交叉验证策略[J]. 南京大学学报(自然科学版), 2019, 55(4): 601-608.
[3]	陶玉枝1，2，赵仕梅1，2，谭安辉1，2*. 一种基于决策表约简的集覆盖问题的近似解法[J]. 南京大学学报(自然科学版), 2018, 54(4): 821-.
[4]	李俊余1，2，王　霞1，2*，刘庆凤3. 属性定向概念格的协调近似表示空间[J]. 南京大学学报(自然科学版), 2017, 53(2): 333-.
[5]	施玉杰1*，杨宏志2，徐久成3. α－先验概率优势关系下的粗糙集模型研究[J]. 南京大学学报(自然科学版), 2016, 52(5): 899-.
[6]	梁新彦^1，2，钱宇华^1，2*，郭　倩²，成红红^1，2. 面向多标记学习的局部粗糙集[J]. 南京大学学报(自然科学版), 2016, 52(2): 270-.
[7]	刘莹莹1，吕跃进2*. 基于相似度的集值信息系统属性约简算法基于相似度的集值信息系统属性约简算法[J]. 南京大学学报(自然科学版), 2015, 51(2): 384-389.
[8]	贾洪杰1,2丁世飞1,2. 基于邻域粗糙集约减的谱聚类算法[J]. 南京大学学报(自然科学版), 2013, 49(5): 619-627.
[9]	于洪*，姚园，赵军 . 一种有效的基于风险最小化的属性约简算法[J]. 南京大学学报(自然科学版), 2013, 49(2): 133-141.
[10]	陈玉明*，吴克寿，孙金华. 基于幂树的决策表最小属性约简 [J]. 南京大学学报(自然科学版), 2012, 48(2): 164-171.
[11]	谢娟英*，李楠^1,2，乔子茵¹. 基于邻域粗糙集的不完整决策系统特征选择算法[J]. 南京大学学报(自然科学版), 2011, 47(4): 383-390.
[12]	赵荣泳 1 , 李翠玲 2 ** , 高晓康 3 , 王昭云 4 . 电子镇流器故障诊断的变精度粗糙集模型* [J]. 南京大学学报(自然科学版), 2010, 46(5): 494-500.