A geometric approach to consistent classification

摘要

A classifier is called consistent with respect to a given set of class-labeled points if it correctly classifies the set. We consider classifiers defined by unions of local separators (e.g., polytopes) and propose algorithms for consistent classifier reduction. The proposed approach yields a consistent reduction of the nearest-neighbor classifier, relating the expected classifier size to a local clustering property of the data and resolving unanswered questions raised by Hart (IEEE Trans. Inform. Theory IT-14(3) (1968)) with respect to the complexity of the condensed nearest neighbor method. (C) 1999 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved. [References: 20]