Abstract CLIFF: Finding Prototypes for Nearest Neighbor Algorithms with Application to Forensic Trace Evidence

Prototype Learning Schemes (PLS) started appearing over 30 years ago (Hart 1968, [22]) in order to alleviate the drawbacks of nearest neighbor classifiers (NNC). These drawbacks include: 1. computation time, 2. storage requirements, 3. the effects of outliers on the classification results, 4. the negative effect of data sets with non-separable and/or overlapping classes, 5. and a low tolerance for noise. To that end, all PLS have endeavored to create or select a good representation of training data which is a mere fraction of the size of the original training data. In most of the literature this fraction is approximately 10%. The aim of this work is to present solutions for these drawbacks of NNC. To accomplish this, the design, implementation and evaluation of CLIFF is described. The basic structure of the CLIFF algorithm involves a ranking measure which ranks the values of each attribute in a training set. The values with the highest ranks are the used as a rule or criteria to select instances/prototypes which obeys the rule/criteria. Intuitively these prototypes best represent the region or neighborhood it comes from and so are expected to eliminate the drawbacks of NN