MapReduce并行化压缩近邻算法

摘要：

压缩近邻(CNN:Condensed Nearest Neighbors)是Hart针对K-近邻(K-NN:K-Nearest Neighbors)提出的样例选择算法,目的是为了降低K-NN算法的内存需求和计算负担.但在最坏情况下,CNN算法的计算时间复杂度为O(n3),n为训练集中包含的样例数.当CNN算法应用于大数据环境时,高计算时间复杂度会成为其应用的瓶颈.针对这一问题,本文提出了基于Ma-pReduce并行化压缩近邻算法.在Hadoop环境下,编程实现了并行化的CNN,并与原始的CNN算法在6个数据集上进行了实验比较.实验结果显示,本文提出的算法是行之有效的,能解决上述问题.

关键词：压缩近邻、K-近邻、样例选择、MapReduce

所属期刊栏目：38

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金项目71371063;河北省自然科学基金项目 F2017201026;浙江省计算机科学与技术重中之重学科浙江师范大学课题项目资助

在线出版日期：2018-01-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：2678-2682