K-Nearest Leader Follower Classifier

Abstract

In pattern recognition, the k-nearest neighbor classifier (k-NN) is a non-parametric approach for classifying test cases based on closest training set elements in the given dataset. k-NN belongs to the category of instance-based learning, or lazy learning where the function is estimated locally and all computation is delayed until classi- fication. The k-nearest neighbor algorithm is supposed to be easiest of all machine learning algorithms, in which an object is classified by a bulk vote of its neighbors, with the object being allotted to the class most common amongst its k nearest neigh- bors. If k = 1, then the object is merely assigned to the class of its nearest neighbor. Nearest Neighbor classifier and its variants like k-Nearest Neighbor (KNN) classifier are popular because of their simplicity and good performance. But one of the major limitations of KNN is that it has to search the entire training set in order to classify a given pattern which proves to be very expensive when a big sized training set is given or dimension of training set is high. In this paper, a generalized k-nearest leader follower classification algorithm is presented, which is an improvement over k-nearest neighbor rule. It can find the class of a test dataset in less time with respect to tra- ditional Nearest-neighbor and KNN. The method is to find a set of leaders with the concept of clustering using a pre- defined minimum distance between two leaders as tou. After finding leaders set, rest of the remaining training set is classified into follower set, with a group of followers assigned to each leader. Now the k-nearest leaders will be found out of the obtained leader set by finding the distance of a given test set from the leader set. And finally using these k-nearest leaders and their corresponding followers, class of the dataset is found. The algorithm is empirically tested with some standard data sets and a comparison is made with some of the earlier classifiers.