Jin Chul Han , Sang Kwi Kim , Chung Hwa Yoon

The KIPS Transactions:PartB , Vol. 13, No. 2, pp. 127-132, Apr. 2006
10.3745/KIPSTB.2006.13.2.127,   PDF Download:

Abstract

K-NN (k-Nearest Neighbors), which is a well-known instance-based learning algorithm, simply stores entire training patterns in memory, and uses a distance function to classify a test pattern. K-NN is proven to show satisfactory performance, but it is notorious formemory usage and lengthy computation. Various studies have been found in the literature in order to minimize memory usage and computation time, and NGE (Nested Generalized Exemplar) theory is one of them. In this paper, we propose RPA (Recursive Partition Averaging) and IRPA (Incremental RPA) which is an incremental version of RPA. RPA partitions the entire pattern space recursively, and generates representatives from each partition. Also, due to the fact that RPA is prone to produce excessive number of partitions as the number of features in a pattern increases, we present IRPA which reduces the number of representative patterns by processing the training set in an incremental manner. Our proposed methods have been successfully shown to exhibit comprable performance to k-NN with a lot less number of patterns and better result than EACH system which implements the NGE theory.

Statistics
Cite this article