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.