Spark下的分布式粗糙集属性约简算法

doi:10.11772/j.issn.1001-9081.2019091642

《计算机应用》唯一官方网站 ›› 2020, Vol. 40 ›› Issue (2): 518-523.DOI: 10.11772/j.issn.1001-9081.2019091642

• 第七届CCF大数据学术会议 • 上一篇下一篇

Spark下的分布式粗糙集属性约简算法

章夏杰¹, 朱敬华¹^,²(), 陈杨¹

^1.黑龙江大学计算机科学技术学院，哈尔滨 150080
^2.黑龙江省数据库与并行计算重点实验室，哈尔滨 150080

收稿日期:2019-08-30 修回日期:2019-09-26 接受日期:2019-10-18 发布日期:2019-10-31 出版日期:2020-02-10
通讯作者: 朱敬华
作者简介:章夏杰（1995—），男，浙江温州人，硕士研究生，主要研究方向：数据挖掘、粗糙集理论
陈杨（1996—），男，重庆人，硕士研究生，主要研究方向：数据挖掘、离散化。
基金资助:
黑龙江省自然科学基金面上项目(F2018028)

Distributed rough set attribute reduction algorithm under Spark

Xiajie ZHANG¹, Jinghua ZHU¹^,²(), Yang CHEN¹

^1.School of Computer Science and Technology，Heilongjiang University，Harbin Heilongjiang 150080，China
^2.Key Laboratory of Database and Parallel Computing of Heilongjiang Province，Harbin Heilongjiang 150080，China

Received:2019-08-30 Revised:2019-09-26 Accepted:2019-10-18 Online:2019-10-31 Published:2020-02-10
Contact: Jinghua ZHU
About author:ZHANG Xiajie， born in 1995， M. S. candidate. His research interests include data mining， rough set theory.
CHEN yang， born in 1996， M. S. candidate. His research interests include data mining， discretization.
Supported by:
the Surface Program of Natural Science Foundation of Heilongjiang Province(F2018028)

摘要/Abstract

摘要：

属性约简（特征选择）作为数据预处理的重要环节，大多以属性依赖作为筛选属性子集的标准。设计了一种快速依赖计算方法FDC，通过直接寻找基于相对正域的对象来计算依赖度，而不需要预先求出相对正域，相比传统方法在速度上有明显的性能提升。另外，改进鲸鱼优化算法（WOA）使其能够有效应用于粗糙集属性约简。结合上述两个方法，提出一种基于Spark的分布式粗糙集属性约简算法SP-WOFRST，并在两组人工合成的大数据集上与另一种基于Spark的粗糙集属性约简算法SP-RST进行对比实验。实验结果表明所提出的SP-WOFRST算法在精度和速度上均优于SP-RST。

关键词: 粗糙集, Apache Spark, 鲸鱼优化算法, 特征选择, 属性约简

Abstract:

Attribute reduction （feature selection） is an important part of data preprocessing. Most of attribute reduction methods use attribute dependence as the criterion for filtering attribute subsets. A Fast Dependence Calculation （FDC） method was designed to calculate the dependence by directly searching for the objects based on relative positive domains. It is not necessary to find the relative positive domain in advance， so that the method has a significant performance improvement in speed compared with the traditional methods. In addition， the Whale Optimization Algorithm （WOA） was improved to make the calculation method effective for rough set attribute reduction. Combining the above two methods， a distributed rough set attribute reduction algorithm based on Spark named SP-WOFRST was proposed， which was compared with a Spark-based rough set attribute reduction algorithm named SP-RST on two synthetical large data sets. Experimental results show that the proposed SP-WOFRST algorithm is superior to SP-RST in accuracy and speed.

Key words: rough set, Apache Spark, Whale Optimization Algorithm (WOA), feature selection, attribute reduction

中图分类号:

TP391

章夏杰, 朱敬华, 陈杨. Spark下的分布式粗糙集属性约简算法[J]. 计算机应用, 2020, 40(2): 518-523.

Xiajie ZHANG, Jinghua ZHU, Yang CHEN. Distributed rough set attribute reduction algorithm under Spark[J]. Journal of Computer Applications, 2020, 40(2): 518-523.

图/表 10

参考文献 16

1	CHEN M， MAO S， LIU Y. Big data： a survey［J］. Mobile Networks and Applications， 2014， 19（2）： 171-209. 10.1007/s11036-013-0489-0
2	FAN W， BIFET A. Mining big data： current status， and forecast to the future［J］. ACM SIGKDD Explorations Newsletter， 2013， 14（2）： 1-5. 10.1145/2481244.2481246
3	PAWLAK Z. Rough sets［J］. International Journal of Computer and Information Sciences， 1982， 11（5）： 341-356. 10.1007/bf01001956
4	HU X， CERCONE N. Learning in relational databases： a rough set approach［J］. Computational Intelligence， 1995， 11（2）： 323-338. 10.1111/j.1467-8640.1995.tb00035.x
5	HU K， LU Y， SHI C， et al. Feature ranking in rough sets［J］. AI Communications， 2003， 16（1）： 41-50. 10.1007/978-3-540-79721-0_17
6	WÓBLEWSKI J. Finding minimal reducts using genetic algorithms［C］// Proceedings of the 2nd Annual Join Conference on Information Sciences. Wrightsville Beach： Mendeley， 1995： 186-189.
7	JENSEN R， SHEN Q. Finding rough set reducts with ant colony optimization［C］// Proceedings of the 2003 UK Workshop on Computational Intelligence. Birmingham：［s.n.］， 2003：15-22.
8	WANG X， YANG J， TENG X， et al. Feature selection based on rough sets and particle swarm optimization［J］. Pattern Recognition Letters， 2007， 28（4）： 459-471. 10.1016/j.patrec.2006.09.003
9	DAGDIA Z C， ZARGES C， BECK G， et al. A distributed rough set theory based algorithm for an efficient big data pre-processing under the Spark framework［C］// Proceedings of the 2017 IEEE International Conference on Big Data. Piscataway： IEEE， 2017：911-916. 10.1109/bigdata.2017.8258008
10	王国胤. Rough集理论与知识获取［M］. 西安：西安交通大学出版社， 2001：12-70. 10.1002/stab.v70.12
	WANG G Y. Rough Set Theory and Knowledge Acquisition［M］. Xi’an： Xi’an Jiaotong University Press， 2001： 12-70. 10.1002/stab.v70.12
11	MIRJALILI S， LEWIS A. The whale optimization algorithm［J］. Advances in Engineering Software， 2016， 95： 51-67. 10.1016/j.advengsoft.2016.01.008
12	KENNEDY J， EBERHART R. Particle swarm optimization［C］// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway： IEEE， 1995： 1942-1948. 10.1109/icnn.1995.488968
13	MAFARJA M， MIRJALILI S. Whale optimization approaches for wrapper feature selection［J］. Applied Soft Computing， 2018， 62：441-453. 10.1016/j.asoc.2017.11.006
14	BELANCHE L A， GONZÁLEZ F F. Review and evaluation of feature selection algorithms in synthetic problems［EB/OL］. ［2019-01-21］. .
15	ZIARKO W. Variable precision rough set model［J］. Journal of Computer and System Sciences， 1993， 46（1）： 39-59. 10.1016/0022-0000(93)90048-2
16	王国胤，于洪，杨大春.基于条件信息熵的决策表约简［J］.计算机学报，2002，25（7）：759-766. 10.3321/j.issn:0254-4164.2002.07.013
	WANG G Y， YU H， YANG D C. Decision table reduction based on conditional information entropy［J］. Chinese Journal of Computers， 2002， 25（7）：759-766. 10.3321/j.issn:0254-4164.2002.07.013

个体编号	肤色	瞳色	出生地
X1	White	Blue	Europe
X2	White	Blue	Europe
X3	Yellow	Brown	Asia
X4	Black	Dark brown	Africa
X5	Yellow	Brown	Asia
X6	Black	Dark brown	Africa
X7	Black	Dark brown	America
X8	Black	Dark brown	America

个体编号	肤色	瞳色	出生地
X1	White	Blue	Europe
X2	White	Blue	Europe
X3	Yellow	Brown	Asia
X4	Black	Dark brown	Africa
X5	Yellow	Brown	Asia
X6	Black	Dark brown	Africa
X7	Black	Dark brown	America
X8	Black	Dark brown	America

编号	条件属性		决策类
1	White	Blue	1
2	White	Blue	1
3	Yellow	Brown	2
4	Black	Dark brown	3
5	Yellow	Brown	2
6	Black	Dark brown	3
7	Black	Dark brown	4
8	Black	Dark brown	4

编号	条件属性		决策类
1	White	Blue	1
2	White	Blue	1
3	Yellow	Brown	2
4	Black	Dark brown	3
5	Yellow	Brown	2
6	Black	Dark brown	3
7	Black	Dark brown	4
8	Black	Dark brown	4

编号	条件属性		决策类	标记
1	White	Blue	1	0
2	White	Blue	1	0
3	Yellow	Brown	2	0
4	Black	Dark brown	3	1
5	Yellow	Brown	2	0
6	Black	Dark brown	3	1
7	Black	Dark brown	4	1
8	Black	Dark brown	4	1

Spark下的分布式粗糙集属性约简算法

Distributed rough set attribute reduction algorithm under Spark

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 16

相关文章 15

编辑推荐

Metrics

特征数/分区	迭代总次数	约简大小	TP	FN	FP	TN	查准率	查全率	F1	时间/s
2	180	89	46	43	4	407	0.92	0.517	0.662	198
2	200	71	43	28	7	422	0.86	0.606	0.711	222
4	80	65	39	26	11	424	0.78	0.600	0.678	133
4	90	49	33	16	17	434	0.66	0.673	0.667	150
6	40	75	40	35	10	415	0.80	0.533	0.640	106
6	50	46	31	15	19	435	0.62	0.674	0.646	133
8	25	63	39	24	11	426	0.78	0.619	0.690	341
8	30	59	35	24	15	426	0.70	0.593	0.642	412
10	20	99	46	53	4	397	0.92	0.465	0.617	1 133
10	30	41	31	10	19	440	0.62	0.756	0.681	1 700

特征数/分区	迭代总次数	约简大小	TP	FN	FP	TN	查准率	查全率	F1	时间/s
4	100	379	233	146	17	104	0.932	0.615	0.741	117
	200	286	195	91	55	159	0.78	0.682	0.728	240
	300	211	164	47	86	203	0.656	0.777	0.711	354
6	60	289	236	53	14	197	0.944	0.817	0.876	266
	80	241	202	39	48	211	0.808	0.838	0.823	354
	100	199	156	43	94	207	0.624	0.784	0.695	445
8	30	322	250	72	0	178	1.000	0.776	0.874	430
	40	280	234	46	16	204	0.936	0.836	0.883	577
	50	240	174	66	76	184	0.696	0.725	0.710	716

种群个体总数	迭代总次数	约简大小	TP	FN	TN	查准率	查全率	F1	时间/s
12	200	72	50	22	428	1	0.694	0.820	206
	300	55	50	5	445	1	0.909	0.952	295
	400	52	50	2	448	1	0.962	0.980	375
24	100	62	50	12	438	1	0.806	0.893	189
	200	54	50	4	446	1	0.926	0.962	350
	300	51	50	1	449	1	0.980	0.990	512
36	100	57	50	7	443	1	0.877	0.935	313
	150	54	50	4	446	1	0.926	0.962	466
	200	52	50	2	448	1	0.962	0.980	589

种群个体总数	迭代总次数	约简大小	TP	FN	TN	查准率	查全率	F1	时间/s
12	300	342	250	14	236	1	0.947	0.973	342
	400	294	250	6	244	1	0.977	0.988	513
	600	257	250	0	250	1	1.000	1.000	640
24	200	295	250	12	238	1	0.954	0.977	278
	300	271	250	5	245	1	0.980	0.990	530
	400	255	250	0	250	1	1.000	1.000	800
36	100	314	250	33	217	1	0.883	0.938	462
	200	271	250	6	244	1	0.977	0.988	663
	300	255	250	0	250	1	1.000	1.000	897

[1]	湛航, 何朗, 黄樟灿, 李华峰, 张蔷, 谈庆. 改进的基于层次距离的基因表达式编程特征选择分类算法[J]. 计算机应用, 2021, 41(9): 2658-2667.
[2]	祝承, 赵晓琦, 赵丽萍, 焦玉宏, 朱亚飞, 陈建英, 周伟, 谭颖. 基于谱聚类半监督特征选择的功能磁共振成像数据分类[J]. 计算机应用, 2021, 41(8): 2288-2293.
[3]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[4]	林筠超, 万源. 基于图结构优化的自适应多度量非监督特征选择方法[J]. 计算机应用, 2021, 41(5): 1282-1289.
[5]	王小荣, 张玉召, 张振江. 基于双论域粗糙集的快捷货物运输方案选择[J]. 计算机应用, 2021, 41(5): 1500-1505.
[6]	贾鹤鸣, 姜子超, 李瑶, 孙康健. 基于改进斑点鬣狗优化算法的同步优化特征选择[J]. 计算机应用, 2021, 41(5): 1290-1298.
[7]	彭莉, 张海清, 李代伟, 唐聃, 于曦, 何磊. 基于粗糙集理论的不完备数据分析方法的混合信息系统填补算法[J]. 计算机应用, 2021, 41(3): 677-685.
[8]	张志浩, 林耀进, 卢舜, 郭晨, 王晨曦. 缺失标记下基于类属属性的多标记特征选择[J]. 计算机应用, 2021, 41(10): 2849-2857.
[9]	董海, 吴瑶, 齐新娜. 基于改进鲸鱼优化算法的血液供应链网络多目标鲁棒优化设计[J]. 计算机应用, 2021, 41(10): 3063-3069.
[10]	童林, 官铮. 改进鲸鱼优化支持向量机的交通流量模糊粒化预测[J]. 计算机应用, 2021, 41(10): 2919-2927.
[11]	陆荣秀, 陈明明, 杨辉, 朱建勇. 基于溶液图像时序特征的元素组分含量动态监测系统[J]. 计算机应用, 2021, 41(10): 3075-3081.
[12]	黄学雨, 徐浩特, 陶剑文. 具有特征选择的多源自适应分类框架[J]. 计算机应用, 2020, 40(9): 2499-2506.
[13]	顾桐, 许国良, 李万林, 李家浩, 王志愿, 雒江涛. 基于集成LightGBM和贝叶斯优化策略的房价智能评估模型[J]. 计算机应用, 2020, 40(9): 2762-2767.
[14]	肖跃雷, 张云娇. 基于特征选择和超参数优化的恐怖袭击组织预测方法[J]. 计算机应用, 2020, 40(8): 2262-2267.
[15]	刘丹, 姚立霜, 王云锋, 裴作飞. 面向类不平衡流量数据的分类模型[J]. 计算机应用, 2020, 40(8): 2327-2333.

数据集	实例数	属性数	类型	分类数
arsds1	3 000	500	Integer	25
arsds2	3 000	500	Integer	50

数据集	实例数	属性数	类型	分类数
arsds1	3 000	500	Integer	25
arsds2	3 000	500	Integer	50