A multi prototype classification algorithm and its application to multi class diagnostics

This paper introduces a novel, universal distance-based classification procedure. It is based on a simple geometric model. Considering all objects as points in a metric space, a class is imagined as covered by potentially differentsized hyperspheres, the centres of which are referred to as prototypes. The radii of the hyperspheres are individually optimised by a generalised ROC-analysis. For the approximate solution of the entire discrete optimisation problem, a greedy algorithm was developed and implemented in R. It runs in O(k 2 ∙n 2 ∙log(n)) time where k is the number of prototypes to be selected and n the number of training objects. For application to multi class problems, one against all approach is performed. The diagnostic decision is finalised for that class of maximum positive predictive value when in doubt. Objects not recognised as a member of any of the classes are assigned to an additional residual class. The performance of the classification system presented is demonstrated on various data examples, and in comparison with other methods.