Journal of Frontiers of Computer Science and Technology ›› 2013, Vol. 7 ›› Issue (1): 35-45.DOI: 10.3778/j.issn.1673-9418.1206048

Previous Articles     Next Articles

Parallel Algorithm Model for Knowledge Reduction Using MapReduce

QIAN Jin1,2,3, MIAO Duoqian1,3+, ZHANG Zehua1,3, ZHANG Zhifei1,3   

  1. 1. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China
    2. School of Computer Engineering, Jiangsu University of Technology, Changzhou, Jiangsu 213001, China
    3. Key Laboratory of Embedded System & Service Computing, Ministry of Education of China, Tongji University, Shanghai 201804, China
  • Online:2013-01-01 Published:2012-12-29

MapReduce框架下并行知识约简算法模型研究

钱  进1,2,3,苗夺谦1,3+,张泽华1,3,张志飞1,3   

  1. 1. 同济大学 计算机科学与技术系,上海 201804
    2. 江苏理工学院 计算机工程学院,江苏 常州 213001
    3. 同济大学 嵌入式系统与服务计算教育部重点实验室,上海 201804

Abstract:

Knowledge reduction for massive datasets has attracted many research interests in rough set theory. Classical knowledge reduction algorithms assume that all datasets can be loaded into the main memory of a single machine, which are infeasible for large-scale data. Firstly, this paper analyzes the parallel computations among classical knowledge reduction algorithms. Then, in order to compute the equivalence classes and attribute significance on different candidate attribute sets, it designs and implements the Map and Reduce functions using data and task parallelism. Finally, it constructs the parallel algorithm framework model for knowledge reduction using MapReduce, which can be used to compute a reduct for the algorithms based on positive region, discernibility matrix or information entropy. The experimental results demonstrate that the proposed parallel knowledge reduction algorithms can efficiently process massive datasets on Hadoop platform.

Key words: MapReduce, rough set, knowledge reduction, data parallel, task parallel

摘要:

面向大规模数据进行知识约简是近年来粗糙集理论研究热点。经典的知识约简算法是一次性将小数据集装入单机主存中进行约简,无法处理海量数据。深入剖析了知识约简算法中的可并行性;设计并实现了数据和任务同时并行的Map和Reduce函数,用于计算不同候选属性集导出的等价类和属性重要性;构建了一种MapReduce框架下并行知识约简算法模型,用于计算基于正区域、基于差别矩阵或基于信息熵的知识约简算法的一个约简。在Hadoop平台上进行了相关实验,实验结果表明,该并行知识约简算法模型可以高效地处理海量数据集。

关键词: MapReduce, 粗糙集, 知识约简, 数据并行, 任务并行