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]	陈虹, 齐兵, 金海波, 武聪, 张立昂. 融合1D-CNN与BiGRU的类不平衡流量异常检测[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2493-2499.
[2]	高麟, 周宇, 邝得互. 进化双层自适应局部特征选择[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1408-1414.
[3]	雷明珠, 王浩, 贾蓉, 白琳, 潘晓英. 基于特征间关系合成少数类样本的过采样算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1428-1436.
[4]	徐大鹏, 侯新民. 基于网络结构设计的图神经网络特征选择方法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 663-670.
[5]	孟圣洁, 于万钧, 陈颖. 最大相关和最大差异的高维数据特征选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 767-771.
[6]	孙林, 刘梦含. 基于自适应布谷鸟优化特征选择的K-means聚类[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 831-841.
[7]	刘晶鑫, 黄雯静, 徐亮胜, 黄冲, 吴建生. 字典学习与样本关联保持结合的无监督特征选择模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3766-3775.
[8]	唐宇皓, 彭德中, 袁钟. 面向不完备混合数据的模糊多粒度异常检测[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3097-3104.
[9]	何添, 沈宗鑫, 黄倩倩, 黄雁勇. 基于自适应学习的多视图无监督特征选择方法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2657-2664.
[10]	孙林, 黄金旭, 徐久成. 基于邻域容差互信息和鲸鱼优化算法的非平衡数据特征选择[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1842-1854.
[11]	李元江, 权金升, 谭阳奕, 杨田. 基于相似和差异双视角的高维数据属性约简[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1467-1472.
[12]	于振华, 刘争气, 刘颖, 郭城. 基于自适应混合粒子群优化的软件缺陷预测特征选择方法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1206-1213.
[13]	孙林, 马天娇, 薛占熬. 基于Fisher score与模糊邻域熵的多标记特征选择算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3779-3789.
[14]	徐精诚, 陈学斌, 董燕灵, 杨佳. 融合特征选择的随机森林DDoS攻击检测[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3497-3503.
[15]	马磊, 罗川, 李天瑞, 陈红梅. 基于模糊粗糙集的无监督动态特征选择算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3121-3128.

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

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