Artículo
On the Selection of the Globally Optimal Prototype Subset for Nearest-Neighbor Classification
Autor/es | Carrizosa Priego, Emilio José
Martín Barragán, Belén Plastria, Frank Romero Morales, María Dolores |
Departamento | Universidad de Sevilla. Departamento de Estadística e Investigación Operativa |
Fecha de publicación | 2007-07-20 |
Fecha de depósito | 2021-04-26 |
Publicado en |
|
Resumen | The nearest-neighbor classifier has been shown to be a powerful tool for multiclass classification. We explore both theoretical properties and empirical behavior of a variant method, in which the nearest-neighbor rule is ... The nearest-neighbor classifier has been shown to be a powerful tool for multiclass classification. We explore both theoretical properties and empirical behavior of a variant method, in which the nearest-neighbor rule is applied to a reduced set of prototypes. This set is selected a priori by fixing its cardinality and minimizing the empirical misclassification cost. In this way we alleviate the two serious drawbacks of the nearest-neighbor method: high storage requirements and time-consuming queries. Finding this reduced set is shown to be NP-hard. We provide mixed integer programming (MIP) formulations, which are theoretically compared and solved by a standard MIP solver for small problem instances. We show that the classifiers derived from these formulations are comparable to benchmark procedures. We solve large problem instances by a metaheuristic that yields good classification rules in reasonable time. Additional experiments indicate that prototype-based nearest-neighbor classifiers remain quite stable in the presence of missing values. |
Cita | Carrizosa Priego, E.J., Martín Barragán, B., Plastria, F. y Romero Morales, M.D. (2007). On the Selection of the Globally Optimal Prototype Subset for Nearest-Neighbor Classification. INFORMS JOURNAL ON COMPUTING, 19 (3), 470-479. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
On the selection of the globally ... | 160.6Kb | [PDF] | Ver/ | |