Trouver l'ensemble minimum de propriétés qui décrivent un référent dans un ensemble d'entités

Question

Je me demandais si quelqu'un pouvait m'aider à obtenir des pointeurs pour résoudre ce problème. Un lien vers les algorithmes serait génial, mais les pointeurs vers les documents/infos sont également bons.

Le problème est le suivant. Supposons que j'ai un ensemble E d'entités E={car1, car2, bicycle} et un ensemble de propriétés P ={red, blue, small}. J'ai aussi une base de connaissances telle que red(bicycle), blue(car1), blue(car2), small(car2). Supposons que j'ai aussi un référent r qui appartient à E.

Le problème consiste à trouver l'ensemble minimum de propriétés P' \subseteq P de sorte qu'il sélectionne sans équivoque r de E. Ainsi, si r est car2, alors P'={small}.

Des idées? J'imagine que quelque chose comme le problème de couverture ou les dépendances fonctionnelles (comme dans la théorie de la DB) pourrait fournir un aperçu, mais je pensais que je demanderais avant d'entrer dans cette littérature. Une autre possibilité est de construire des graphes et de trouver des algorithmes pour les isomorphismes de sous-graphes ... peut-être.

Merci.

Answer 1

Commencez par trouver l'ensemble des propriétés de r. Appelez-le S. Pour chaque propriété p dans S, trouvez e (p), toutes les entités qui ont la propriété p. Il est clair pour chaque p dans S que e (p) contient r. Maintenant, prenez les intersections de e (p) pour chaque p dans S. Si l'intersection contient plus d'une entité, il n'y a pas de solution, et nous terminons l'algorithme. Nous avons donc un ensemble S de propriétés qui déterminent de manière unique l'entité r.

Nous devons maintenant trouver un sous-ensemble minimal de S qui détermine uniquement r. Nous pouvons supprimer toute propriété p de S pour laquelle il existe une propriété q dans S de sorte que e (p) soit un sur-ensemble de e (q). Si vous faites cela de manière exhaustive, vous finirez par obtenir un ensemble réduit de propriétés T, de sorte que l'intersection de e (p) pour tout p dans T sera toujours {r}, mais aucune autre propriété dans T ne peut être supprimée. Cet ensemble T est alors minimal.

Je n'ai pensé à rien pour trouver une propriété que vous pouvez enlever plus efficace que de simplement essayer toutes les combinaisons, mais il me semble qu'il devrait y avoir un moyen.

Answer 2

Vous recherchez un minimum set cover de l'ensemble E \ {r} avec les négations (les compléments) des propriétés auxquelles appartient r (les propriétés peuvent être traitées comme des sous-ensembles de E).

Étant donné que ces ensembles peuvent être quelconques, c'est NP-difficile.

Plus précisément:

Avoir une instance de couverture de jeu (U, S) où U est l'ensemble que vous devez couvrir et S = {s1, s2, ..., sn} est la famille de couvrir jeux que vous pouvez construire une instance de votre problème afin que sa solution donne une couverture de jeu dans le problème d'origine:

E = U \ union {r}, où r est le référent et r n'appartient pas à U. L'ensemble des propriétés P =, pn} est construit à partir S de telle sorte que pour chaque e dans U et chaque i tel que 1 = < i < = n nous avons pi (e) ssi e est pas en si. De plus, chaque propriété est vraie pour r. En d'autres termes, les propriétés sont des compléments des ensembles d'origine lorsqu'elles sont limitées à U, et r a toutes les propriétés.

Maintenant, il est clair que chaque ensemble de propriétés qui sélectionne r est une couverture de jeu dans le problème d'origine - si r est sélectionné par un ensemble S* de propriétés, tous les autres éléments (cela signifie que tous ceux U) échouent à Au moins une propriété dans S*, de sorte que chaque élément de U appartient à au moins un ensemble d'origine (à partir de la construction de propriétés en tant que compléments des ensembles). Cela signifie que U est l'union de ces ensembles à partir desquels les propriétés de S* ont été construites.

L'inverse est également vrai - une couverture d'ensemble dans U se traduit par un ensemble de sélection r dans E.

La réduction ci-dessus est évidemment polynomiale, donc le problème est NP-difficile.