A new parameter-free classification algorithm based on nearest neighbor rule and K-means for mobile devices

This paper proposes a parameter-free classifier which combines K-means with Nearest Neighbor Rule (NNR) - called Incremental Cluster-based Classification (ICC). The classifier is used in low power and capacity devices such as Personal Digital Assistant (PDA) and Smartphone. In the training phase, ICC employs K-means to group instances into several clusters, and then incrementally separates the cluster into two clusters until the cluster members belong to the same type within each cluster. Thus instances have uniform class label within each cluster. In the predicting phase, ICC adopts NNR to find a centroid which is the nearest neighbor of the unlabeled instance. Since the training data are substituted by the cluster centroids; memory and computation requirements are decreased. K-means and NNR are both simple and efficient methods. ICC is easy to redo and have efficient performance and is, hence, suitable for low capacity hardware. In this paper, the prediction accuracy of ICC is evaluated and compared with those of NNR and Support Vector Machine (SVM). Our experimental results show that the prediction accuracy of ICC is comparable to NNR. Although NNR is the easiest to use and redo, it is sensitive to noises and consumes time and memory for a large dataset. Despite the higher accuracy of LIBSVM, it is time-consuming to select an appropriate kernel function and related parameters. ICC is parameter-free, simple to operate and easy to implement. Mobile users can complete their work more conveniently and accurately.