LMIRA: Large Margin Instance Reduction Algorithm

Abstract

In instance-based learning, a training set is given to a classifier for classifying new instances. In practice, not all information in the training set is useful for classifiers. Therefore, it is convenient to discard irrelevant instances from the training set. This process is known as instance reduction, which is an important task for classifiers since through this process the time for classification or training could be reduced. In this paper, we propose a Large Margin Instance Reduction Algorithm, namely LMIRA. LMIRA removes non-border instances and keeps border ones. In the proposed method, the instance reduction process is formulated as a constrained binary optimization problem and then it is solved by employing a filled function algorithm. Instance-based learning algorithms are often confronted with the difficulty of choosing those instances which must be stored to be used during an actual test. Storing too many instances can result in large memory requirements and slow execution. In LMIRA, core of instance reduction process is based on keeping the hyperplane that separates a two-class data and provides large margin separation. LMIRA selects the most representative instances, satisfying both following objectives: high accuracy and reduction rates. The performance has been evaluated on real world data sets from UCI repository by the ten-fold cross-validation method. The results of experiments are compared with state-of-the-art methods, which show the superiority of proposed method in terms of classification accuracy and reduction percentage.