Reduction techniques for instance-based learning algorithms

Instance-based learning algorithms are often faced with the problem of deci ding which instances to store for use during generalization. Storing too ma ny instances can result in large memory requirements and slow execution spe ed, and can cause an oversensitivity to noise. This paper has two main purp oses. First, it provides a survey of existing algorithms used to reduce sto rage requirements in instance-based learning algorithms and other exemplar- based algorithms. Second, it proposes six additional reduction algorithms c alled DROP1-DROP5 and DEL (three of which were first described in Wilson & Martinez, 1997c, as RT1-RT3) that can be used to remove instances from the concept description. These algorithms and 10 algorithms from the survey are compared on 31 classification tasks. Of those algorithms that provide subs tantial storage reduction, the DROP algorithms have the highest average gen eralization accuracy in these experiments, especially in the presence of un iform class noise.