| Data Reduction technique is an important pre-processing step in KDD(knowledge discovery in databases)aiming to reduce the data size to improve the performance of data mining methods.Instance selection method is a kind of data reduction techniques is used to improve the quality of data set by removing redundant,erroneous and noisy instances.However,with the exponential growth of data in many application domains,processing very large scale data sets for instance selection is becoming a major limitation.The traditional methods lack enough scalability to cope with data sets of millions of instances even though they have already been performed over the previous smaller dataset.Recent improvements in this field cover the stratification of data and redesign the algorithms and their inclusion in parallel environments.Based on the divide and conquer principle,they divide the training set into some disjoint subsets and apply instance selection algorithms independently to each subset.Finally,they merge all partial reduced sets into a final reduced result.These distributed previous methods lack the information of the whole problem and may lead to the introduction of noisy and redundant instances.In this paper,we propose a novel distributed instance selection framework.In this framework,every computing node can leverage the whole information of the data set.Furthermore,for different application requirements,we design two parallel instance selection algorithm and implement them in the MapReduce way.The main research results and innovation on this dissertation are listed as follows:(1)We design a framework for parallel instance selection methods.We analyze the limitation of the previous methods and propose a novel parallel framework.To solve the poor accuracy and scalability problems,this framework can select a small part of representative data and distribute them to each computing node to ensure the access of the whole information.We analyze the features of suitable algorithms and the limitation of this platform.(2)Based on the MapReduce framework,we implemented a prototype,FCNN-MR,to remove redundant data in the data set.This parallel method can produce the same output as the sequential version and is order independent.We evaluate the performance of FCNN-MR on one small data set(Page-blocks)and two large data sets(Poker-hand and Mnist).The experimental results show that it is effective and practical.(3)To solve the presence of noisy and redundant values in data sets.We redesign the genetic algorithm and propose a novel method,RMHC-MR based on MapReduce framework.It can improve the quality of data sets during each iteration by mutation and selection.We test the method on three data sets.The results show that it can effectively remove the noisy and redundant values and has good performances of generalization accuracy and reduction rate. |
