Minimum Spanning Tree Based Classification Model for Massive Data with MapReduce Implementation
Authors:
- Jin ChangJCJin Chang
- Jun LuoJLJun Luo
- Joshua Zhexue HuangJHJoshua Zhexue Huang
- Shengzhong FengSFShengzhong Feng
- Jianping FanJFJianping Fan
- 1 December 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 129-137
Abstract
Rapid growth of data has provided us with more information, yet challenges the tradition techniques to extract the useful knowledge. In this paper, we propose MCMM, a Minimum spanning tree (MST) based Classification model for Massive data with MapReduce implementation. It can be viewed as an intermediate model between the traditional K nearest neighbor method and cluster based classification method, aiming to overcome their disadvantages and cope with large amount of data. Our model is implemented on Hadoop platform, using its MapReduce programming framework, which is particular suitable for cloud computing. We have done experiments on several data sets including real world data from UCI repository and synthetic data, using Downing 4000 clusters, installed with Hadoop. The results show that our model outperforms KNN and some other classification methods on a general basis with respect to accuracy and scalability.Keywords
This publication has 10 references indexed in Scilit:
- A clustering-Based KNN improved algorithm CLKNN for text classification2010
- A Model of Computation for MapReduce2010
- Minimum spanning tree based one-class classifierNeurocomputing, 2009
- A CUDA-based parallel implementation of K-nearest neighbor algorithm2009
- Fast k-nearest neighbor classification using cluster-based treesIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Spanning Trees and Optimization Problems2004
- Practical parallel algorithms for minimum spanning trees2002
- Clustering algorithms based on minimum and maximum spanning trees1988
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphsCombinatorica, 1986
- Minimum Spanning Trees and Single Linkage Cluster AnalysisJournal of the Royal Statistical Society Series C: Applied Statistics, 1969