Encontrar el conjunto mínimo de propiedades que describen un referente en un conjunto de entidades

Question

Me preguntaba si alguien podría ayudarme a obtener sugerencias para resolver este problema. Un enlace a los algoritmos sería genial, pero los punteros a los documentos/información también son buenos.

El problema es el siguiente. Supongamos que tengo un conjunto E de entidades E={car1, car2, bicycle} y un conjunto de propiedades P ={red, blue, small}. También tengo una base de conocimiento tal que red(bicycle), blue(car1), blue(car2), small(car2). Supongamos que también tengo un referente r que pertenece a E.

El problema consiste en encontrar el conjunto mínimo de propiedades P' \subseteq P de manera que distingue inequívocamente r de E. Por lo tanto, si r es car2, entonces P'={small}.

¿Alguna idea? Supongo que algo así como el conjunto de problemas que cubren o las dependencias funcionales (como en la teoría de DB) pueden proporcionar alguna idea, pero pensé que lo haría antes de entrar en esa literatura. Otra posibilidad es construir gráficos y encontrar algoritmos para subomizar isomorfismos ... tal vez.

Gracias.

Answer 1

Primero encuentre el conjunto de todas las propiedades que r tiene. Llámalo S. Para cada propiedad p en S, encuentra e (p), todas las entidades que tienen la propiedad p. Está claro para cada p en S que e (p) contiene r. Ahora tome las intersecciones de e (p) para cada p en S. Si la intersección contiene más de una entidad, no hay solución, y terminamos el algoritmo.

Así que tenemos un conjunto S de propiedades que determinan de manera única la entidad r. Ahora necesitamos encontrar un subconjunto mínimo de S que determine de forma exclusiva r. Podemos eliminar cualquier propiedad p de S para la cual exista una propiedad q en S, de modo que e (p) sea un superconjunto de e (q). Si lo hace exhaustivamente, eventualmente terminará con un conjunto reducido de propiedades T, de modo que la intersección de e (p) para toda la p en T seguirá siendo {r}, pero no se podrá eliminar ninguna otra propiedad en T. Este conjunto T es entonces mínimo.

No he pensado en nada para hacer que encontrar una propiedad que pueda eliminar sea más eficiente que intentar todas las combinaciones, pero me parece que debería haber alguna manera.

Answer 2

Está buscando minimum set cover del conjunto E \ {r} con negaciones (complementos) de las propiedades a las que r pertenece (las propiedades se pueden tratar como subconjuntos de E).

Dado que estos conjuntos pueden ser cualquier conjunto, este es NP-hard.

Más precisamente:

Tener una instancia de la cubierta conjunto (U, S), donde U es el conjunto que necesita para cubrir y S = {s1, s2, ..., sn} es la familia de cubrir Establece puede construir una instancia de su problema para que su solución proporciona una cubierta de set en el problema original:

E = U \ union {r}, donde r es el referente y r no pertenece a U. El conjunto de propiedades P = {p1, p2, ..., pn} está construida a partir S modo que para cada e en U y cada i tal que 1 < = i < = n tenemos pi (e) si y sólo si e no es en si. Además, cada propiedad es verdadera para r. En otras palabras, las propiedades son complementos de los conjuntos originales cuando se restringen a U, y r tiene todas las propiedades.

Ahora está claro que cada conjunto de propiedades que selecciona r es una cubierta de conjunto en el problema original - si r se selecciona por un conjunto S* de propiedades, entonces todos los otros elementos (es decir, todas aquellas en U) fallan en al menos una propiedad en S*, por lo que cada elemento de U pertenece a al menos un conjunto original (a partir de la construcción de propiedades como complementos de los conjuntos). Eso significa que U es la unión de aquellos conjuntos a partir de los cuales se construyeron las propiedades en S*.

Lo contrario también es cierto: una cubierta de conjunto en U se traduce en un conjunto de r -selecting en E.

La reducción anterior es obviamente polinómica, por lo que el problema es NP-hard.