Decidiendo entre NP-hard y NP-complete según mis propias reglas.
Tengo el conjunto de datos de Iris que se ve así:
1,3,1,1,0
1,1,1,1,0
1,3,1,1,0
1,2,1,1,0
1,3,1,1,0
1,2,1,1,0
2,2,2,2,1
2,2,2,2,1
2,2,2,2,1
2,1,2,2,1
1,1,2,2,1
2,1,2,2,1
2,2,3,4,2
2,1,3,4,2
3,1,3,4,2
2,1,3,4,2
2,1,3,4,2
3,1,3,4,2
Solo estoy mostrando 18 filas, pero en total hay 150 filas. Las primeras 4 columnas dan los 4 valores de atributo y la quinta columna da la clase.
Así que 3,1,3,4,2 significa que si att_1=3, att_2=1, att_3=3, att_4=4, entonces class=2.
Ahora he escrito 2 algoritmos clasificadores, en los que intenté extraer reglas de este conjunto de datos.
El primer algoritmo (implementado en C y python) da como resultado:
*,*,1,*,0
*,*,2,2,1
*,*,*,3,1
*,*,*,4,2
*,*,3,*,2
Con estas 5 filas intenté mantener todas las características del conjunto de datos principal que contiene 150 filas. Aquí, * significa “no importa” y *,*,2,2,1 significa que si el valor del atributo 3 y 4 es 2, entonces no importa el valor de los atributos 1 y 2, la clase será 1.
El segundo algoritmo (implementado en C y python) da como resultado:
*,*,1,*,0
*,*,2,2,1
2,*,*,3,1
*,2,2,*,1
*,*,3,4,2
*,1,*,4,2
*,*,3,2,2
3,*,*,*,2
1,*,*,3,2
Ahora he tomado la unión de estos 2 conjuntos de reglas y obtuve el resultado:
*,*,2,2,1
*,*,1,*,0
*,2,2,*,1
*,*,3,2,2
*,*,3,4,2
3,*,*,*,2
*,*,*,3,1
1,*,*,3,2
*,*,*,4,2
*,*,3,*,2
*,1,*,4,2
2,*,*,3,1
Ahora me surge la pregunta de si hay 12 reglas en ese archivo de unión, ¿pero puede haber 3 o 4 reglas más efectivas con las cuales podamos obtener una visión clara del conjunto de datos iris inicial con 150 filas? Entonces mi pregunta es: ¿Este problema es un problema NP-hard o un problema NP-complete? ¿Y por qué?
davy.ai
Este problema es “np-hard”.
La tarea de encontrar las 5 reglas más efectivas de un conjunto dado de reglas se puede ver como un problema de optimización combinatoria, donde el objetivo es seleccionar un subconjunto de las reglas dadas que maximice alguna función objetivo. En este caso, la función objetivo podría ser la precisión de las reglas generadas para predecir las etiquetas de clase de los ejemplos en el conjunto de datos original.
El espacio de búsqueda para este problema de optimización es exponencial en el número de reglas, ya que hay “2^12” posibles subconjuntos del conjunto dado de 12 reglas. Por lo tanto, la complejidad temporal para encontrar el subconjunto óptimo de reglas puede ser exponencial o peor, lo que lo convierte en un problema “np-hard”.
Además, dado que el problema implica seleccionar un subconjunto de reglas que maximice una función objetivo, se clasifica como uno de los problemas de optimización “np-hard”, los cuales suelen ser más difíciles que los problemas de decisión que requieren una respuesta de sí o no.
En conclusión, el problema de encontrar las 5 reglas más efectivas de un conjunto dado de reglas es “np-hard” porque implica resolver un problema de optimización con un espacio de búsqueda exponencial.