Pertinence de résultats de recherches multi-critères

L’auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour tout le monde !

Je cherche à implémenter un moteur de recherches multi-critères avec une base de données MySQL, et si possible avoir les résultats classés par pertinence. Pour faire simple, j’ai des personnages avec différentes capacités, et pour des missions il me faut composer des équipes avec des capacités définies par la mission. Les personnages peuvent avoir plusieurs capacités qui sont demandées pour la mission, et c’est là que cette histoire de pertinence intervient.

Je ne vois pas vraiment comment faire de manière simple. J’ai déjà imaginé d’avoir une série de tests selon les critères afin de déterminer la pertinence, mais ma "solution" ne me paraît pas vraiment flexible ni performante — si pour deux critères on a deux tests, pour trois critères on en a 5, pour quatre on en a 12, etc. —, sachant que je vais avoir jusqu’à sept critères.

Y a-t’il une autre manière de faire que de générer les multiples combinaisons1 à tester pour générer une notion de pertinence ?

Merci d’avance  ^^


  1. Je ne suis pas certain de mon calcul, là, mais il s’agirait bien d’une somme de combinaisons, quelque chose comme $\sum\limits_{i=1}^n C^n_i$  

Evitez qu’on vous dise de les lire : FAQ PHP et SymfonyTutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0

Salut, j’ai pas bien compris ce que tu veux faire. De ce que je comprends, il n’y a pas de rapport avec ta base de donnée ?

Tu as des "objets" qui ont des "caractéristiques", tu dois trouver ceux qui correspondent le mieux à une contrainte. C’est ça ?

Genre chaque perso a une vitesse de course et une endurance, et tu dois composer une équipe de 3 personnes pour grimper l’everest, et une équipe de 4 personnes pour courir un 4x100m ?

Ton problème c’est un problème d’"optimisation" (enfin, recherche opérationnelle, blabla) ? Ou t’as déjà ce que tu veux et tu sais pas comment écrire une requête performante / minimiser les requêtes nécessaires ?

Édité par cepus

+0 -0
Auteur du sujet

Tu as des "objets" qui ont des "caractéristiques", tu dois trouver ceux qui correspondent le mieux à une contrainte. C’est ça ?s objets peuvent avoir jusqu’à trois des caractéristiques nécessaires.

Genre chaque perso a une vitesse de course et une endurance, et tu dois composer une équipe de 3 personnes pour grimper l’everest, et une équipe de 4 personnes pour courir un 4x100m ?

victor

Oui, c’est le même genre d’idée.
Après, ce qui n’aide peut-être pas à comprendre mais qui me semble important, c’est que la contrainte porte sur plusieurs critères (un ensemble de X caractéristiques nécessaires à la réalisation de la mission), et que les objets peuvent avoir jusqu’à trois caractéristiques correspondant à celles nécessaires à l’accomplissement de la mission.

Ton problème c’est un problème d’"optimisation" (enfin, recherche opérationnelle, blabla) ? Ou t’as déjà ce que tu veux et tu sais pas comment écrire une requête performante / minimiser les requêtes nécessaires ?

victor

C’est une forme d’optimisation tant concrète (moins j’utilise de personnes sur une mission, plus je peux effectuer de missions en parallèle) que sur le plan algorithmique.

Imaginons qu’une mission demande d’avoir les compétences (c’est plus logique dans ce contexte que "caractéristique") de patinage et de pâtisserie. Les personnes ayant une des deux compétences devraient idéalement sortir avec une pertinence moins élevée que les personnes qui ont les deux compétences.
Techniquement, c’est relativement simple de faire comme suit :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
IF(
        competence1 IN (person.competences)
    AND competence2 IN (person.competences),
    2,
    IF(
            competence1 IN (person.competences)
        OR  competence2 IN (person.competences),
        1,
        0
    )
)

Mais quand on augmente le nombre de compétences requises, ça devient bien plus complexe, parce que justement c’est là qu’interviennent les combinaisons : ceux qui ont toutes les compétences, c’est facile de savoir et de leur attribuer la pertinence maximale. Mais avec trois compétences, j’ai déjà $C^3_2 = 3$ possibilités de paires de combinaisons pour avoir une pertinence un peu moindre, plus $C^3_1 = 3$ d’avoir une pertinence non nulle, mais encore plus faible (et là, techniquement, c’est une suite de OR plutôt que trois tests séparés, donc mon estimation n’est pas totalement correcte).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
IF (
        competence1 IN (person.competences)
    AND competence2 IN (person.competences)
    AND competence3 IN (person.competences),
    3,
    IF (
       (
                competence1 IN (person.competences)
            AND competence2 IN (person.competences)
        ) OR (
                competence1 IN (person.competences)
            AND competence3 IN (person.competences)
        ) OR (
                competence2 IN (person.competences)
            AND competence3 IN (person.competences)
        ),
        2,
        IF (
                competence1 IN (person.competences)
            OR  competence2 IN (person.competences)
            OR  competence3 IN (person.competences),
            1,
            0
        )
    )
)
Un exemple avec 3 compétences demandées

Je me demandais s’il y avait un moyen différent que de construire les $n$ membres de $1 + C^n_{n-1} + C^n_{n-2} + C^n_{n-3} + … + C^n_2 + 1$, sachant que $n$ représente notamment le nombre de compétences nécessaires, mais aussi les $n$ niveaux de pertinence et donc les $n$ niveaux de IF imbriqués, pour reprendre la structure des codes proposés.

De ce que je comprends, il n’y a pas de rapport avec ta base de donnée ?

victor

Si, dans la mesure ou je pense qu’il est logique de faire calculer la pertinence par le SGBDR, donc d’avoir ce qu’il faut soit dans le moteur de bases de données (auquel cas je ne sais pas comment le faire avec MySQL), soit dans la requête (et c’est là que je vois comment faire, mais ça me paraît lourd).

Édité par Ymox

Evitez qu’on vous dise de les lire : FAQ PHP et SymfonyTutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0

Cette réponse a aidé l’auteur du sujet

Que penses-tu de récupérer toutes les personnes qui ont au moins une compétence requise pour la mission X, puis de travailler sur le résultat de la requête ? Tu peux en sortir une bête matrice.

Si tu veux pas faire ça, à mon avis faudra revoir ton schéma de base de donnée. Pas une bonne idée d’avoir plusieurs compétences dans un seul champ person.competences.

Avec un meilleur schéma, t’as plusieurs solutions. Tu peux par exemple bêtement sélectionner la compétence présente comme 1 et passer par SUM pour ordonner les résultats par nombre de critères remplis ?

+2 -0
Auteur du sujet

Ne t’en fais pas, je me rends compte avec ton commentaire que j’ai fait un mélange de SQL et de DQL dans mes exemples  ^^
Je n’ai pas un champ contenant toutes mes compétences de la personne dans celle-ci.

J’avais vaguement pensé à une somme (ce qui me semblerait effectivement bien plus simple et léger), mais c’était tard hier soir et avoir dormi dessus n’as pas aidé, j’ai même oublié la chose  :honte:

En fait, quelque chose comme ce qui suit pourrait peut-être faire l’affaire aussi… :-°

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
SELECT
        p.*,
        count(DISTINCT s.id) AS relevance
    FROM
            person p
        INNER JOIN
                skill_person sp
            ON  p.id = sp.person_id
        INNER JOIN
                skill s
            ON      s.id = sp.skill_id
    WHERE
            s.id IN (:s_id1, :s_id2, etc.)
    GROUP BY
        p.id
    ORDER BY
        relevance DESC
Le tout, c’est de ne plus chercher une compétence requise dans celles de la personne, mais de chercher les personnes qui ont au moins une des compétences, effectivement. "Inverser" la manière dont je (sinon on) utilise le IN

Tout cet étalement de logique pour en arriver à ça…  :'(

Edit

Allez, des missions, des compétences, et ce sujet, quelques indices supplémentaires bien placés, d’aucuns devraient switcher sur ce que je manigance  ^^

Édité par Ymox

Evitez qu’on vous dise de les lire : FAQ PHP et SymfonyTutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0
Auteur du sujet

Je m’en doute, mais j’ai la flemme d’installer un autre serveur, d’apprendre à l’utiliser, d’adapter mon application pour ça juste parce qu’Elasticsearch calcule le score automatiquement.  :lol:

Et il me semble que les solutions NoSQL sont justement moins récentes que le SQL, donc j’étais aussi curieux de savoir comment on faisait avant

Sans parler du fait que la solution est d’une simplicité déconcertante par rapport à ce sur quoi j’étais parti.

Édité par Ymox

Evitez qu’on vous dise de les lire : FAQ PHP et SymfonyTutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0

Tu dois forcément faire ça avec MySQL ? Elasticsearch me semble bien plus optimisé pour faire ce que tu souhaites.

John

Oui et non, franchement. Elasticsearch, pour moi, c’est plutôt pour stocker des documents et leurs métadonnées, analyser le tout, indexer le tout, puis faire des recherches textuelles et multi-critères. Là oui.

Dans le cas présent ça me semble largement overkill vu qu’il n’y a pas du tout d’aspect document ou textuel.

Il a une liste de critères tout à fait définie et il veut juste faire une recherche dedans. Le faire dans une base de donnée relationnelle ou récupérer les données et leur attribuer une pertinence dans le backend, ces 2 solutions me semblent meilleures dans son cas que de sortir ES pour ça.

+0 -0

Oui et non. On est d’accord qu’ES est prévu pour des choses plus "complexes" que ça. D’un autre côté, il est aussi fait pour faire du requêtage rapide, avec de multiples critères, et de ressortir les données triées par pertinence. Ce de manière "plus ou moins" automatique ("plus ou moins" parce que derrière il y a un peu de conf quand même).

Après je ne connais pas l’appli d’Ymox. Mais c’est toujours bien de se poser la question de l’évolutivité. Et si dans 6 mois un critère est rajouté, il faut potentiellement modifier l’algo PHP, ce qui serait (normalement) moins le cas avec une base ES.

Après si le besoin est simple et n’est pas amené à évoluer, du SQL fera en effet très bien l’affaire. :)

+0 -0
Auteur du sujet

Cette réponse a aidé l’auteur du sujet

Je repasse par ici pour quelques ajustements.

Après des tests plus poussés, je me suis retrouvé avec des résultats dont la pertinence était systématiquement le nombre de compétences de la personne…

  1. Il faut donc utiliser le filtre dans la jointure ;
  2. Si on a plusieurs tables impliquées pour les critères :
    • on doit passer par des LEFT JOIN, vu que des critères peuvent correspondre dans une des tables seulement ;
    • on doit mettre les filtres dans les jointures ET dans la clause de sélection WHERE, mais avec des OR dans cette dernière.
      Les filtres dans les jointures font qu’on ne sélectionne que les valeurs jointes qui nous intéressent, et les filtres dans la clause de sélection WHERE limitent aux seules personnes qui remplissent au moins un critère, nécessaire du fait des LEFT JOIN qui, sans ça, nous feraient récupérer toutes les personnes.
  3. La pertinence est la somme des critères remplis :
    • il faut des if pour savoir si un critère sur une table est rempli (même partiellement) ;
    • pour des critères sur des jointures, on compte le nombre de correspondances distinctes avec if(s.id IN (:s.ids), count(DISTINCT s.id), 0) (sans DISTINCT on se retrouve à compter autant de fois les éléments d’une table jointe qu’il y en a dans une autre table jointe) ;
    • pour des critères sur la table "principale" (le sexe de la personne, typiquement), on ajoute simplement 1 à la pertinence si le critère est rempli, donc if(p.gender = 'f', 1, 0).

Du coup, la requête change un poil :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
SELECT
        p.*,
        if(p.gender = 'f', 1, 0) + if(s.id IN (:s_id1, :s_id2, etc.), count(DISTINCT s.id), 0) AS relevance
    FROM
            person p
        LEFT JOIN
                skill_person sp
            ON  p.id = sp.person_id
        LEFT JOIN
                skill s
            ON      s.id = sp.skill_id
                AND 
                    s.id IN (:s_id1, :s_id2, etc.)
    WHERE
            s.id IN (:s_id1, :s_id2, etc.)
        OR  p.gender = 'f'
    GROUP BY
        p.id
    ORDER BY
        relevance DESC

Ce qui fait que moi, je peux construire ma suite de if qui rejoint mon idée initiale et qui semble donc nécessaire dans ce que je souhaite.

Édité par Ymox

Evitez qu’on vous dise de les lire : FAQ PHP et SymfonyTutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte