A geometric approach to consistent classification

✍ Scribed by Yoram Baram

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 167 KB
• Volume: 33
• Category: Article
• ISSN: 0031-3203
• DOI: 10.1016/s0031-3203(99)00050-3

✦ Synopsis

A classi"er is called consistent with respect to a given set of class}labeled points if it correctly classi"es the set. We consider classi"ers de"ned by unions of local separators (e.g., polytopes) and propose algorithms for consistent classi"er reduction. The proposed approach yields a consistent reduction of the nearest-neighbor classi"er, relating the expected classi"er 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.