algorithm - libro - Encontrar el conjunto más pequeño de criterios para la singularidad

singularidad filosofia

Question

Tengo una colección de objetos con propiedades. Quiero encontrar el conjunto de criterios más simple que especifique exactamente uno de estos objetos (no me importa cuál).

Por ejemplo, dado {a = 1, b = 1, c = 1}, {a = 1, b = 2, c = 1}, {a = 1, b = 1, c = 2}, especificando b == 2 (o c == 2) me dará un objeto único.

Del mismo modo, dado {a = 1, b = 1, c = 1}, {a = 1, b = 2, c = 2}, {a = 1, b = 2, c = 1}, especificando b == 2 yc == 2 (o b == 1 && c == 1 o b == 2 && c == 1) me dará un objeto único.

Esto suena como un problema conocido, con una solución conocida, pero no he podido encontrar la formulación correcta del problema que me permita buscarlo en Google.

Answer 1

De hecho, es un problema conocido en AI: selección de características. Hay muchos algoritmos para hacer esto, solo Google "selección de funciones", "inteligencia artificial".

El problema principal es que cuando el conjunto de muestras es grande, debe usar algún tipo de heurística para llegar a una solución dentro de un tiempo razonable.

Selección de características en minería de datos

La idea principal de la selección de características es elegir un subconjunto de variables de entrada mediante la eliminación de características con poca o ninguna información predictiva.

Answer 2

La libertad de elegir el objetivo es algo inusual. Si se especifica el objetivo, este es esencialmente el problema de cobertura establecido . Aquí hay dos instancias correspondientes una al lado de la otra.

A={1,2,3} B={2,4} C={3,4} D={4,5}

0: {a=0, b=0, c=0, d=0}  # separate 0 from the others
1: {a=1, b=0, c=0, d=0}
2: {a=1, b=1, c=0, d=0}
3: {a=1, b=0, c=1, d=0}
4: {a=0, b=1, c=1, d=1}
5: {a=0, b=0, c=0, d=1}

Mientras que set cover es NP-hard, sin embargo, su problema tiene un algoritmo O (m ^{log n + O (1)} poli (n)) donde m es el número de atributos yn es el número de elementos (el conjunto óptimo de criterios tiene un tamaño como máximo log n), lo que hace bastante improbable que se presente una prueba de dureza NP. Me acuerdo de la situación con el problema de la Junta (básicamente la formulación teórica de la selección de características).

Answer 3

No sé cuán fácilmente esto podría traducirse en un algoritmo, pero usando SQL, que ya está configurado en base, podría funcionar así

• construir una tabla con todas las combinaciones posibles de columnas de la tabla de entrada
• seleccione todas las combinaciones que aparezcan iguales a la cantidad de registros presentes en la tabla de entrada como combinaciones distintas.

Script de SQL

;WITH q (a, b, c) AS (
  SELECT ''1'', ''1'', ''1''
  UNION ALL SELECT ''1'', ''2'', ''2''
  UNION ALL SELECT ''1'', ''2'', ''1''
  UNION ALL SELECT ''1'', ''1'', ''2''
)
SELECT  col
FROM    (
          SELECT val = a, col = ''a''  FROM q
          UNION ALL SELECT b, ''b'' FROM q
          UNION ALL SELECT c, ''c'' FROM q
          UNION ALL SELECT a+b, ''a+b'' FROM q
          UNION ALL SELECT a+c, ''a+c'' FROM q
          UNION ALL SELECT b+c, ''b+c'' FROM q
          UNION ALL SELECT a+b+c, ''a+b+c'' FROM q
        ) f
GROUP BY
        col        
HAVING
        COUNT(DISTINCT (val)) = (SELECT COUNT(*) FROM q)

Answer 4

Su problema se puede definir de la siguiente manera:

1 1 1 -> A
1 2 1 -> B
1 1 2 -> C
.
.

donde 1 1 1 se llama vector de característica y A es la clase de objeto. Luego puede usar árboles de decisión (con poda) para encontrar un conjunto de reglas para clasificar objetos. Entonces, si su objetivo es decidir automáticamente el conjunto de criterios para identificar el objeto A , entonces puede observar la ruta en el árbol de decisión que conduce a A

Si tiene acceso a MATLAB , es realmente fácil obtener un árbol de decisión para sus datos.