La clasificación multi-etiqueta como una tarea de minería de datos ha atraído recientemente un interés creciente por parte de los investigadores. Muchas aplicaciones actuales de minería de datos abordan problemas con instancias que pertenecen a más de una categoría. Estos problemas requieren el desarrollo de nuevos métodos eficientes. La regla de vecinos más cercanos multi-etiqueta, ML-kNN, se encuentra entre los métodos con mejor rendimiento para problemas multi-etiqueta. Los métodos actuales utilizan un valor único para todas las etiquetas, como en el método de etiqueta única. Sin embargo, las distribuciones de las etiquetas suelen ser muy diferentes. En tales escenarios, un valor único para las etiquetas podría ser subóptimo. En este documento, proponemos un enfoque novedoso en el que cada etiqueta se predice con un valor diferente de . Obtener el mejor para cada etiqueta se plantea como un problema de optimización. Se proponen tres algoritmos diferentes para esta tarea, dependiendo de cuál métrica multi-etiqueta sea el objetivo de nuestro proceso de optimización. En un amplio conjunto de 40 problemas multi-etiqueta del mundo real, nuestro enfoque mejora los resultados de dos implementaciones diferentes de ML-kNN probadas.