City trip search, principes de fonctionnement et avantages
But du programme et du présent document
Le but du moteur de recherche "city trip search" est de montrer à toute personne intéressée comment fonctionne en pratique un moteur de recherche triant des objets par k-Pareto optimalité. Ainsi l'interface web permet d'interagir de manière très directe avec le serveur. Pour une application destinée à un internaute lambda, l'interface peut être simplifiée. L'interface est cependant simple à utiliser et le but principal de ce document est d'expliquer de manière intuitive la méthodologie sur laquelle le moteur de recherche se base.
Pour des raisons de disponibilité de données les localités d'Europe de l'Ouest, disponibles sur les sites geonames.org et dans wikipedia.org ont été chargées dans le moteur de recherche. D'autres cas d'utilisation devraient être plus importants ou plus intéressants économiquement, comme par exemple:
- des sites de petites annonces immobilières ou d'offres d'emploi,
- des outils d'aide à la décision pour investisseurs désirant diversifier leur portefeuille tout en respectant différentes préférences (secteur, rentabilité de l'entreprise, âge de l'entreprise, valeur des marques, ... ).
Scénario d'utilisation
Un utilisateur est supposé chercher une localité à découvrir en vacances.
Les boîtes de sélection supérieures "Select a subset of cities" permettent de sélectionner un sous-ensemble de localités. Cette partie fonctionne de manière classique. Le nombre localités retenues est affiché au-dessus des résultats.
Les boîtes de sélection inférieures "Sort the subset by preferences" permettent à l'utilisateur de trier, selon ses préférences, le sous-ensemble de localités retenues. Les 50 premières localités de ce tri par préférences sont finalement affichées. En grandes lignes ce tri par préférences fonctionne comme suit.
Le tri selon les préférences
La partie "Sort the subset by preferences" de l'interface permet à l'utilisateur d'entrer ses préférences sous forme d'une relation de préordre composite. Il peut préférer une localité à une autre si elle est plus proche de Paris, a une population plus petite et contient un château.
La sous-relation "a une population plus petite" pourrait aussi être remplacée par "a une population entre 500 et 1000 habitants". La signification de ce type de sous-relation "appartient à un intervalle" est la suivante:
- si les deux villes sont dans l'intervalle elles sont considérées comme étant équipréférables,
- sinon celle qui est la plus proche de l'intervalle est considérée comme étant préférable.
Il y a beaucoup de manières à trier des résultats tout en respectant les préférences de l'utilisateur. Par exemple tous les tris lexicographiques ou les tris selon diverses moyennes pondérées des écarts par rapport aux valeurs souhaitées conviennent de ce point de vue.
Ce moteur de recherche respecte les préférences de l'utilisateur en triant tous les résultats selon un critère original appelé k-Pareto-optimalité. La k-Pareto-optimalité d'une ville est le pourcentage de villes qui lui sont préférables. Il s'agit du produit des pourcentages de villes préférables pour chaque sous-critère. Au lieu de calculer des produits on prend des logarithmes qui s'additionnent. Ces scores additifs appelés entropie sont visualisés sous forme de barres horizontales bleues.
Il est intéressant de sélectionner deux ou trois intervalles, de faire varier leur longueur et d'observer les résultats et les scores.
Avantages du tri par k-Pareto optimalité
Par ses propriétés intéressantes le tri par k-Pareto optimalité présente beaucoup d'avantages pour l'utilisateur.
- Plus une caractéristique est rare, plus elle a de la valeur, ce qui traduit le bon sens économique.
- Il est transparent. L'utilisateur peut voir des sous-scores et savoir pourquoi tel résultat a été placé devant tel autre résultat.
- Aucun paramètre arbitraire n'intervient dans les calculs et aucun calibrage n'est donc nécessaire.
- Il offre un choix maximal. C'est la méthode de tri qui laisse à l'utilisateur le plus de choix tout en respectant ses préférences. Étant donné que l'utilisateur ne cherche qu'une seule localité les couples de localités où une est strictement préférable à l'autre sont les moins souhaités parmi les résultats. Le tri par k-Pareto optimalité évite ce type de redondance au mieux et la grande diversité de résultats ainsi obtenue rend plus probable que l'utilisateur trouve une localité qui corresponde au mieux à ses désirs personnels.
- Elle peut être implémentée de manière efficace.
Nous avons défini mathématiquement ces propriétés et elles ont été démontrées sous des conditions générales dans le texte de méthodologie PDF.
La méthode ci-dessus est surtout adaptée aux cas où il faut prendre en compte au moins trois critères. Par exemple trois critères indépendants qui chacun éliminent neuf résultats sur dix éliminent ensemble approximativement 999 résultats sur 1000. A défaut de trouver des données qui satisfont bien trois critères cette méthode se rabat tout aussi bien sur des résultats qui satisfont mal un critère et très bien les deux autres que sur des résultats qui sont très moyens selon les trois critères. La k-Pareto optimalité laisse à l'utilisateur le choix de faire le compromis qui lui semble le plus approprié.
En effet n critères numériques constituent un espace à n dimensions. D'un point de vue géométrique on sélectionne dans cet espace des régions délimitées par des espèces d'hyperboloïdes de k-Pareto optimalité constante. Des moyennes pondérées ou des distances euclidiennes délimitent via des sphères ou des plans et ont ainsi tendance à ne garder que des résultats qui sont très moyens selon tous les critères
La méthodologie ci-dessus s'applique bien à beaucoup de processus de décision en deux étapes. La première étape est une pré-sélection d'un nombre limité d'éléments parmi un grand jeu de données, selon la méthode décrite ci-dessus. Cette étape peut être réalisée par un ordinateur. La deuxième étape consiste en la sélection finale d'un seul élément parmi ceux qui ont été pré-sélectionnés. Cette étape peut être réalisée par un expert au moyen d'analyses et de raisonnements complexes et coûteux ou par une personne quelconque selon ses goûts particuliers.