基于MapReduce和Spark的大规模压缩模糊K-近邻算法

doi:10.19678/j.issn.1000-3428.0055670

计算机工程 ›› 2020, Vol. 46 ›› Issue (11): 139-147. doi: 10.19678/j.issn.1000-3428.0055670

基于MapReduce和Spark的大规模压缩模糊K-近邻算法

王谟瀚^a, 翟俊海^a,b, 齐家兴^a

河北大学 a. 数学与信息科学学院;b. 河北省机器学习与计算智能重点实验室, 河北保定 071002

收稿日期:2019-08-05 修回日期:2019-11-10 发布日期:2019-11-20
作者简介:王谟瀚(1992-),男,硕士研究生,主研方向为分布式计算、机器学习;翟俊海(通信作者),教授;齐家兴,硕士。
基金资助:
国家自然科学基金（71371063）；河北省自然科学基金（F2017201026）；河北省科技计划重点研发基金（19210310D）；河北大学研究生创新项目基金（hbu2019ss077）。

Large-Scale Condensed Fuzzy K-Nearest Neighbor Algorithm Based on MapReduce and Spark

WANG Mohan^a, ZHAI Junhai^a,b, QI Jiaxing^a

a. College of Mathematics and Information Science;b. Hebei Key Laboratory of Machine Learning and Computational Intelligence, Hebei University, Baoding, Hebei 071002, China

Received:2019-08-05 Revised:2019-11-10 Published:2019-11-20

摘要/Abstract

摘要： 压缩模糊K-近邻（CFKNN）算法仅适用于中小数据环境，且其样例选择采用静态机制，导致算法不能对阈值进行动态调整从而选出最优样例。为此，对CFKNN算法进行改进，将其扩展到大规模数据环境，提出分别基于MapReduce和Spark的2种大规模压缩模糊K-近邻算法。在样例选择阈值设置方面，引入动态机制，使得所选样例更具代表性。在具有7个数据节点的大数据平台上进行实验，结果表明，与CFKNN算法相比，所提2种算法具有更高的分类精度和加速比。2个平台相比，MapReduce产生的中间文件数目多于Spark，而Spark在运行时间和同步次数上优于MapReduce。

关键词: MapReduce平台, Spark平台, 模糊K-近邻, 样例选择, 动态机制

Abstract: The Condensed Fuzzy K-Nearest Neighbor(CFKNN) algorithm is applicable only to small-sized and medium-sized data sets,and its mechanism of instance selection is static,so the algorithm can not adjust the threshold dynamically to select the optimal sample.To address the problems,this paper improves the CFKNN algorithm to make it applicable it to large-scale data environment,and on this basis proposes two kinds of large-scale condensed fuzzy K-nearest neighbor algorithms based on MapReduce and Spark.A dynamic mechanism is introduced into the setting of the instance selection threshold to make the selected instances more representative.Experiments are carried out on a big data platform with 7 data nodes.The experimental results show that compared with the CFKNN algorithm,the two proposed algorithms have better classification accuracy and acceleration ratio.Results of comparison between the two proposed algorithms show that MapReduce produces more intermediate files than Spark,yet Spark outperforms MapReduce in terms of running time and synchronization times.

Key words: MapReduce platform, Spark platform, fuzzy K-Nearest Neighbor(K-NN), instance selection, dynamic mechanism

中图分类号:

TP311

王谟瀚, 翟俊海, 齐家兴. 基于MapReduce和Spark的大规模压缩模糊K-近邻算法[J]. 计算机工程, 2020, 46(11): 139-147.

WANG Mohan, ZHAI Junhai, QI Jiaxing. Large-Scale Condensed Fuzzy K-Nearest Neighbor Algorithm Based on MapReduce and Spark[J]. Computer Engineering, 2020, 46(11): 139-147.

http://www.ecice06.com/CN/Y2020/V46/I11/139

图/表 15

20201124085502

20201124085505

20201124085508

20201124085511

20201124085515

20201124085518

20201124085521

20201124085524

20201124085527

20201124085530

20201124085534

20201124085536

20201124085539

20201124085542

20201124085546

参考文献

[1] COVER T,HART P.Nearest neighbor pattern classification[J].IEEE Transactions on Information Theory,1967,13(1):21-27.
[2] HART P E.The condensed nearest neighbor rule[J].IEEE Transactions on Information Theory,1968,14(3):515-516.
[3] GATES G.The reduced nearest neighbor rule[J].IEEE Transactions on Information Theory,1972,18(3):431-433.
[4] WILSON D,MARTINEZ T.Reduction techniques for instance-based learning algorithms[J].Machine Learning,2000,38(3):257-286.
[5] BRIGHTON H,MELLISH C.Identifying competence-critical instances for instance-based learners[M].Berlin,Germany:Springer,2001.
[6] HOU Guangdong,CUI Runpeng,PAN Zheng,et al.Tree-based compact hashing for approximate nearest neighbor search[J].Neurocomputing,2015,166:271-281.
[7] LIANG Cong,XIA Shuyin,CHEN Zizhong.Improvement k-nearest neighbor classification algorithm based on reference points[J].Computer Engineering,2019,45(2):173-178.(in Chinese)梁聪,夏书银,陈子忠.基于参考点的改进k近邻分类算法[J].计算机工程,2019,45(2):173-178.
[8] WAN Ji,TANG Sheng,ZHANG Yongdong,et al.HDIdx:high-dimensional indexing for efficient approximate nearest neighbor search[J].Neurocomputing,2017,237:401-404.
[9] WEN Qingfu,WANG Jianmin,ZHU Han,et al.Distributed hash learning method for approximate neighbor query[J].Chinese Journal of Computers,2017,40(1):192-206.(in Chinese)文庆福,王建民,朱晗,等.面向近似近邻查询的分布式哈希学习方法[J].计算机学报,2017,40(1):192-206.
[10] ARNAIZ-GONZÁLEZ Á,DÍEZ-PASTOR J,RODRÍGUEZ J J,et al.Instance selection of linear complexity for big data[J].Knowledge-Based Systems,2016,107:83-95.
[11] YANG Dingzhong,CHEN Xinhao.Approximate nearest neighbor search based on projection residual quantization hash[J].Computer Engineering,2015,41(12):161-165,170.(in Chinese)杨定中,陈心浩.基于投影残差量化哈希的近似最近邻搜索[J].计算机工程,2015,41(12):161-165,170.
[12] LUO Xin,OUYANG Yuanxin,XIONG Zhang,et al.Optimization of K-nearest neighbor based collaborative filtering algorithm by similarity support degree[J].Chinese Journal of Computers,2010,33(8):1437-1445.(in Chinese)罗辛,欧阳元新,熊璋,等.通过相似度支持度优化基于K近邻的协同过滤算法[J].计算机学报,2010,33(8):1437-1445.
[13] QIAO Yulong,PAN Zhengxiang,SUN Shenghe.An improved fast k-nearest neighbor classification algorithm[J].Acta Electronica Sinica,2005,33(6):1146-1149.(in Chinese)乔玉龙,潘正祥,孙圣和.一种改进的快速k-近邻分类算法[J].电子学报,2005,33(6):1146-1149.
[14] ZHAI Junhai,LI Ta,WANG Xizhao.A cross-selection instance algorithm[J].Journal of Intelligent and Fuzzy Systems,2016,30(2):717-728.
[15] SONG Yunsheng,LIANG Jiye,LU Jing,et al.An efficient instance selection algorithm for k nearest neighbor regression[J].Neurocomputing,2017,251:26-34.
[16] MUJA M,LOWE D G.Scalable nearest neighbor algorithms for high dimensional data[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(11):2227-2240.
[17] ZHAI Junhai,WANG Xizhao,PANG Xiaohe.Voting-based instance selection from large data sets with MapReduce and random weight networks[J].Information Sciences,2016(367/368):1066-1077.
[18] MAILLO J,RAMÍREZ S,TRIGUERO I,et al.kNN-IS:an iterative Spark-based design of the k-nearest neighbors classifier for big data[J].Knowledge-Based Systems,2017,117:3-15.
[19] SONG G,ROCHAS J,BEZE L E,et al.K nearest neighbour joins for big data on MapReduce:a theoretical and experimental analysis[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(9):2376-2392.
[20] KELLER J M,GRAY M R,GIVENS J A.A fuzzy K-nearest neighbor algorithm[J].IEEE Transactions on Systems,Man,and Cybernetics,1985,15(4):580-585.
[21] ZHAI Junhai,LI Na,ZHAI Mengyao.The condensed fuzzy k-nearest neighbor rule based on sample fuzzy entropy[C]//Proceedings of 2011 International Conference on Machine Learning and Cybernetics.Washington D.C.,USA:IEEE Press,2011:16-27.
[22] APACHE.Hadoop[EB/OL].[2019-07-20].http://hadoop.apache.org/.
[23] APACHE.Spark[EB/OL].[2019-07-20].http://spark.apache.org/.
[24] WU Xindong,JI Shengqiao.Comparison of MapReduce and Spark in big data analysis[J].Journal of Software,2018,29(6):1770-1791.(in Chinese)吴信东,嵇圣硙.MapReduce与Spark用于大数据分析之比较[J].软件学报,2018,29(6):1770-1791.

选择文件类型/文献管理软件名称

选择包含的内容

基于MapReduce和Spark的大规模压缩模糊K-近邻算法

Large-Scale Condensed Fuzzy K-Nearest Neighbor Algorithm Based on MapReduce and Spark

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	贾晓芳, 桑国明, 祁文凯. 基于Spark平台的ALS加速算法研究[J]. 计算机工程, 2020, 46(2): 103-109.
[2]	高权,万晓冬. 基于负载均衡的并行FP-Growth算法[J]. 计算机工程, 2019, 45(3): 32-35,40.
[3]	张浩盛伦,李翀,柯勇,张士波. 一种分布式用户浏览点击模型算法[J]. 计算机工程, 2019, 45(3): 1-6.
[4]	陈广胜,程逸群,景维鹏. 基于KD树划分的云计算DBSCAN优化算法[J]. 计算机工程, 2017, 43(4): 21-27.
[5]	黄廷辉,王玉良,汪振,崔更申. 基于内存与文件共享机制的Spark I/O性能优化[J]. 计算机工程, 2017, 43(3): 1-6.
[6]	杨志伟,郑烇,王嵩,杨坚,周乐乐. 异构Spark集群下自适应任务调度策略[J]. 计算机工程, 2016, 42(1): 31-35,40.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于MapReduce和Spark的大规模压缩模糊K-近邻算法

Large-Scale Condensed Fuzzy K-Nearest Neighbor Algorithm Based on MapReduce and Spark

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献

相关文章 6

编辑推荐

Metrics

本文评价