Brevet FR2835940A1 — publié le 20030815

L'invention concerne un procédé de recherche des plus proches voisins dans de grandes bases de données multidimensionnelles. Elle s'applique en particulier, mais non exclusivement, à la recherche par similarité dans de grandes bases de données de contenu multimedia tel que de la vidéo, des images fixes ou des documents audio. Les applications de la recherche par le contenu se décomposent généralement en deux volets : - la description du contenu des objets gérés par l'application - la recherche au sein de l'ensemble des objets stockés. La description des objets gérés, images, vidéos, textes, séquences audio, etc., est réalisée de manière automatique et se traduit en général par l'extraction d'un certain nombre de primitives représentées par des vecteurs de grande dimension, appelés descripteurs, auxquels est associée une mesure de similarité. Cette mesure, généralement une distance, permet de quantifier la similarité entre descripteurs, et donc indirectement, la ressemblance entre les objets qu'ils décrivent. Le deuxième volet concerne la structuration des descripteurs de manière à pouvoir effectuer des recherches rapides au sein de la base de données constituée de l'ensemble des descripteurs stockés. Les recherches les plus pratiques sont les recherches par l'exemple : on présente au système un nouveau document qui sert de requête pour rechercher les documents les plus semblables. On extrait alors les descripteurs de ce document, descripteurs qui vont servir à interroger la base. La recherche au sein de la base est elle-même une recherche de similarité qui consiste à retrouver les vecteurs de la base qui ressemblent le plus au vecteur descripteur de la requête. Cette recherche peut s'exprimer de différentes manières, la plus utilisée est la recherche des plus proches voisins. Ce deuxième volet relève plutôt du domaine des bases de données. Le problème qui se pose peut se formuler comme suit : soient un ensemble E de N vecteurs de dimension d et une fonction de distance f qui permet de mesurer la similarité entre les vecteurs de E. Il s'agit de structurer les vecteurs de E et fournir des algorithmes qui permettent d'effectuer des recherches efficaces de plus proches voisins : retrouver les k vecteurs de E les plus proches, au sens de la métrique f, d'un vecteur requête q. L'objectif de ces algorithmes est de répondre à ce type de requêtes en évitant de parcourir la totalité des vecteurs de E. En d'autres termes, il s'agit de minimiser le nombre d'accès au fichier contenant les descripteurs (entrées/sorties sur disque) et le temps de calcul CPU nécessaire au traitement d'une recherche, afin de répondre le plus rapidement possible aux requêtes formulées par l'utilisateur. Les particularités du problème font que les techniques traditionnelles en bases de données ne peuvent être utilisées. En effet, d'une part, les descripteurs manipulés sont de grande dimension et de volume important, et d'autre part, le mode de recherche requis est la recherche de similarité. Plusieurs techniques d'indexation multidimensionnelle ont ainsi été développées. Elles reposent sur le même principe : regrouper a priori les données de la base de telle sorte que les données proches dans l'espace soient dans le même groupe, puis développer des algorithmes qui exploitent a posteriori la structure mise en place pour effectuer des recherches efficaces dans la base. Ces techniques peuvent être classées en trois grandes familles : les techniques basées sur le partitionnement des données, connues sous les appellations anglaises R*-tree, SR-tree, X-tree, etc., les techniques basées sur le partitionnement de l'espace, k-d-b-tree, LSD h-tree, PyramidTree, etc., et les techniques basées sur la compression, le VA-File et ses variantes. Plusieurs travaux ont montré que ces techniques sont inefficaces dans les espaces de grande dimension pour diverses raisons. D'une part, les groupes de données sont généralement mal formés, car les procédures de structuration des données sont très sensibles à l'ordre d'insertion des vecteurs et à la distribution des données, et d'autre part, les procédures de recherche sont incapables de confiner la recherche à un petit sous-ensemble des données auquel il suffit d'accéder pour construire l'ensemble résultat. Ce dernier problème est dû principalement à la complexité de l'organisation, généralement arborescente, des groupes de données. L'article intitulé''When is "nearest neighbor" meaningful ? " dans la revue Proceedings of the 7th International Conference on Database Theory, 217-235, Jerusalem, Israel, January 1999, de K. Beyer, J. Goldstein, R. Ramakrishnan and U. Shaft ou l'article"A quantitative analysis and performance study for similarity search methods in high-dimensional spaces" dans la revue Proceedings of the 24th International Conference on Very Large Data Bases, 194-205, New York City, New York, USA, August 1998, de R. Weber, H.-J. Schek and S. Blott, ont même montré que, dans certains cas, les performances des techniques connues en indexation multidimensionnelle sont inférieures à celles d'une simple recherche séquentielle. Récemment, d'autres techniques qui exploitent des algorithmes de clustering, aussi appelés algorithmes de regroupement ou de classification, pour regrouper les données, qui n'utilisent aucune organisation particulière des groupes de données et qui proposent des algorithmes de recherche approximative, ont été développées. Dans l'article intitulé"Densitybased indexing for approximate nearest-neighbor queries"de K. P. Bennett, U. Fayyad et D. Geiger, dans la revue Proceedings of the 5th ACM International Conference on knowledge discovery and data mining, San Diego, California, pages 577-588, February 2000, la technique proposée repose sur une modélisation statistique de l'ensemble de données. Chaque concentration de données ou cluster est modélisée par une gaussienne. L'algorithme de recherche décide de lire un cluster en fonction de la probabilité qu'a celui-ci de contenir le plus proche voisin du vecteur requête. Cette technique possède deux inconvénients majeurs. D'une part, le nombre de clusters pouvant être utilisés pour modéliser l'ensemble de données est contraint par la technique de modélisation utilisée. En pratique, ce nombre est de l'ordre de quelques dizaines. D'autre part, les calculs de probabilités reposent sur des suppositions qui sont rarement vérifiées pour des ensembles de données réels, telles que distributions particulières, indépendance des paramètres, etc. Dans l'article intitulé"Clustering for approximate similarity search in high-dimensional spaces de C. Li, E. Chang, H. Garcia-Molina et G. Wiederhold, dans la revue IEEE Transactions on knowledge and data engineering, 2001, une autre technique basée sur le clustering a été proposée. Elle utilise des principes beaucoup plus simples et permet d'effectuer des recherches de plus proches voisins approximatives. Cependant, le taux de précision ne peut être ni quantifié ni contrôlé. Cette méthode ordonne les clusters selon leur proximité par rapport au vecteur requête et considère arbitrairement un nombre fixe parmi eux. Le nombre de clusters à considérer est un paramètre fixé par l'utilisateur. Cependant, aucun contrôle direct sur la précision de la recherche ne peut être effectué. L'invention a pour but de pallier les inconvénients précités. Elle a pour objet un procédé de recherche des k plus proches voisins d'un vecteur requête q dans une base de données multidimensionnelle de N vecteurs comprenant une phase de structuration de la base en clusters pour le regroupement des vecteurs et une phase de recherche, caractérisé en ce qu'il comprend les étapes suivantes : - calcul de la distance Dppc (C, p) du centre de gravité d'un cluster C de la base au pième plus proche vecteur voisin parmi les vecteurs du cluster, p étant un entier naturel supérieur ou égal à k, - calcul de la distance distc (C, q) du vecteur requête q au centre de gravité du cluster C -calcul de la somme distPc (C, q, p) des distances distc (C, q) et Dppc (C, p), -calcul, sur l'ensemble des clusters C de la base, de la plus petite valeur distPc (C, q, p), - élimination des clusters C de la base dont la distance mindist (C, q), qui est la plus petite distance entre le vecteur requête q et la sphère englobante du cluster C, est supérieure à la plus petite valeur distPc. Selon un mode de mise en oeuvre, la phase de structuration est effectuée hors ligne et le calcul des distances Dppc (C, p) est effectué pour chaque cluster pendant cette phase, les calculs faisant intervenir q étant effectués pendant la phase de recherche. Selon un mode de mise en oeuvre particulier, la valeur de k est définie pendant la phase de requête, le calcul Dppc (C, p) est effectué pour plusieurs valeurs de p et la valeur retenue pour le calcul de la somme est la valeur de p immédiatement supérieure à celle de k. Si les recherches sont à effectuer pour un nombre prédéterminé k de plus proches voisins, p=k. Selon un mode de mise en oeuvre particulier, le procédé comporte : - une étape de lecture d'un cluster courant parmi les clusters non éliminés consistant en un calcul des distances entre le vecteur requête q et tous les vecteurs du cluster lu, en une mémorisation des k vecteurs les plus proches au vecteur requête q si des vecteurs plus proches à q que ceux mémorisés ont été retrouvés, et de la distance entre q et son k1ème plus proche voisin si cette distance est inférieure à celle mémorisée, - une étape d'élimination ou de sélection pour la lecture, d'un cluster suivant, selon que sa distance mindist est supérieure ou non à la distance entre q et son k'ème plus proche voisin courant. Les clusters peuvent être préalablement ordonnés selon les valeurs croissantes de distc, mindist ou bien distPc pour le choix du cluster suivant. Selon un mode de mise en oeuvre, la sphère englobante d'un cluster, de rayon raye, est remplacée par une sphère approchée, de même centre que la sphère englobante, mais de rayon raya inférieur à raye, raya étant déterminé en fonction d'un taux de précision de la recherche a prédéfini, correspondant à la probabilité qu'un vecteur du cluster soit ignoré lors de la phase d'élimination des clusters. Selon un mode de mise en oeuvre, le calcul du rayon approché est effectué par recherche dichotomique en faisant l'hypothèse que tous les vecteurs situés dans le volume compris entre la sphère englobante d'un cluster, de rayon raye, et la sphère approchée, de rayon raya, sont ignorés. Selon un autre mode de mise en oeuvre, le calcul du rayon approché est effectué par recherche dichotomique en faisant l'hypothèse que les vecteurs situés dans le volume compris entre la sphère englobante d'un cluster, de rayon raye, et la sphère approchée, de rayon raya, sont distribués de manière isotrope. Selon un autre mode de mise en oeuvre, le calcul du rayon approché est effectué par recherche dichotomique en fonction de la probabilité P (H) que l'hypothèse d'isotropie est vérifiée pour les vecteurs situés dans le volume compris entre la sphère englobante et la sphère approchée. Selon un mode de mise en oeuvre, l'estimation de la probabilité P (H) est effectuée pour un cluster C selon les étapes suivantes : - calcul du rayon approché raya en supposant la distribution des vecteurs situés dans le volume compris entre la sphère englobante et la sphère approchée d'un cluster isotrope, - calcul de la proportion p théorique du nombre de vecteurs ignorés, soit p = N. a, - tirage aléatoire d'un ensemble de vecteurs requêtes Qi, - détermination expérimentale, pour chaque Qi, du nombre de vecteurs du cluster C qui sont ignorés si le rayon approché de C est pris en compte au lieu de son rayon exact, - estimation de P (H) par la proportion des Qi pour lesquels le nombre de vecteurs ignorés réellement est inférieur ou égal au nombre estimé sous l'hypothèse de distribution isotrope. Selon un mode de mise en oeuvre, l'estimation de la probabilité P (H) est effectuée en moyennant les estimations effectuées séparément sur plusieurs clusters. L'invention concerne également un procédé d'indexation mettant en oeuvre le procédé de recherche du plus proche voisin défini précédemment. Une application du procédé concerne la recherche d'images par le contenu, procédé dans lequel la base de données est une base relative à des descripteurs d'image, les dimensions correspondant à ces descripteurs et le vecteur requête représente les valeurs de descripteurs d'une image requête. L'invention se base sur des algorithmes et des principes très simples. Les principaux avantages en sont des temps de traitements des requêtes réduits et de bons résultats en termes de précision. De plus, le taux de précision de la recherche peut être contrôlé par l'utilisateur, ce qui permet au procédé de s'adapter aux contraintes de l'application et aux exigences de l'utilisateur. Les algorithmes utilisés permettent une grande souplesse dans le choix des paramètres. D'autres particularités et avantages de l'invention apparaîtront clairement dans la description suivante donnée à titre d'exemple non limitatif, et faite en regard des figures annexées qui représentent : -) a f'gure 1, les distances entre un vecteur requête et un cluster, - la figure 2, la distance distPc (C, q), - la figure 3, quelques positions possibles de deux clusters par rapport à un vecteur requête, illustrant l'intérêt de la règle de filtrage des clusters proposée dans l'invention, - la figure 4, les règles de sélection des clusters, - la figure 5, un cluster avec rayon exact et rayon approximatif. La technique d'indexation multidimensionnelle proposée ici exploite un algorithme de clustering pour la phase de structuration des données de la base et propose un algorithme de recherche de plus proches voisins pour la phase de recherche, ce dernier pouvant être soit exact, soit approximatif. Cette technique est destinée à gérer des ensembles de données de grande dimension et de volume important. Structuration des données Il s'agit, dans un premier temps, de structurer les données de la base et de leur associer des informations additionnelles appelées données d'indexation. Le principe général de cette phase repose sur une mise en paquets des données de la base, de manière à retrouver dans le même paquet les données colocalisées dans l'espace. L'exploitation ultérieure des données considère les paquets plutôt que les vecteurs de données élémentaires, comme unités de lecture. Les données d'indexation concernent principalement la forme des clusters. Cette phase peut être exécutée hors ligne car elle ne dépend pas des paramètres de requête. Elle fait appel à un algorithme de clustering pour la mise en paquets des vecteurs de la base. Aucune contrainte n'est imposée pour le choix de l'algorithme. Toutefois, la performance des algorithmes de recherche dépend de la qualité du regroupement des données obtenues par clustering. Le nombre de clusters à former n'a pas besoin d'être spécifié précisément. Cependant, comme on considère les clusters comme unités de lecture, ils doivent avoir des tailles et des populations à peu près équilibrées. De plus, selon les applications, les clusters très peu peuplés, qui correspondent à des vecteurs isolés, peuvent être mis à part et traités différemment. À l'issue de l'opération de clustering, l'ensemble de données de taille N et de dimension d est partitionné en m clusters, chacun contenant au moins Pmin vecteurs. Les vecteurs appartenant aux clusters peu peuplés, c'est à dire les clusters qui contiennent moins de pm ; n vecteurs, sont mis dans un fichier spécial, appelé fichier des données isolées. Bien entendu, le nombre de vecteurs isolés dépend de la distribution des données mais aussi de la valeur de pmfn choisie. Dans le cas où l'utilisateur décide de traiter tous les vecteurs de la même manière, il suffit de choisir pmm égal à zéro. À chaque cluster C" l'algorithme de structuration des données rajoute les informations suivantes : id, : identifiant du cluster (entier), n, : nombre de vecteurs appartenant au cluster, cg, : centre de gravité des vecteurs appartenant au cluster (vecteur de dimension d), ray, : rayon de l'hypersphère englobante du cluster (distance entre cg, et son plus lointain voisin parmi les vecteurs du cluster), Dppc, : distance entre cg, et son plus proche voisin parmi les vecteurs du cluster. Enfin, les données (vecteurs de la base et données d'indexation qui leur sont associés) sont organisées physiquement de la manière suivante : - les informations associées aux clusters sont mises dans un fichier appelé fichier de description des clusters, - l'ensemble des vecteurs est réorganisé physiquement de façon à pouvoir accéder directement aux vecteurs d'un cluster sur la base de son identifiant (un index monodimensionnel peut être utilisé), - les vecteurs isolés, s'ils existent, sont stockés dans un fichier spécial appelé fichier des données isolées. Algorithmes de recherche Les algorithmes de recherche de similarité de type "plus proches voisins" exploitent généralement des distances entre le point requête et les différents paquets de données. La décision de lire ou non le contenu d'un paquet se base sur un certain nombre de critères géométriques. Cela permet de confiner la recherche à un sous-ensemble de paquets, les plus pertinents par rapport à la recherche en cours. Deux algorithmes de recherche de plus proches voisins sont proposés ici : -un algorithme de recherche exact qui permet de retrouver exactement les plus proches voisins d'un vecteur requête mais dont le coût risque d'être élevé, - un algorithme de recherche approximative qui permet d'effectuer des recherches approximatives des plus proches voisins, mais dont le coût est relativement très faible. Le taux de précision de la recherche, ou taux de confiance, est contrôlé par l'utilisateur. Ces algorithmes de recherche exploitent la structure de données réalisée hors ligne. Le but est de minimiser le nombre d'accès au fichier contenant les vecteurs de la base (le nombre d'opérations d'entrées/sorties sur disque) et le temps de calcul CPU nécessaire pour répondre au traitement d'une requête de l'utilisateur. Pour des raisons de clarté, les algorithmes présentés se limitent, dans un premier temps, à la recherche du plus proche voisin. L'extension de ces algorithmes à la recherche des k plus proches voisins est détaillée par la suite. Les données isolées ne sont pas considérées à ce niveau. Dans le cas de la recherche exacte, cet ensemble de données est traité séquentiellement (recherche séquentielle) car sa taille n'est généralement pas très importante. Pour la recherche approximative, la prise en compte de cette portion de données est optionnelle et dépend du choix de l'utilisateur. L'algorithme de recherche considère les clusters comme unités de lecture. Cela signifie que la phase de filtrage des algorithmes de recherche ne considère que les positions relatives des clusters par rapport au vecteur requête pour décider lesquels sont pertinents pour la recherche et lesquels n'ont aucune chance de contenir des résultats. Ainsi, entre un vecteur requête q et un cluster C, on définit les distances suivantes : - distc (C, q) : la distance entre q et le centre de gravité Cg du cluster C, -maxdist (C, q) : la plus grande distance entre q et la sphère englobante du cluster C, - mindist (C, q) : la plus petite distance entre q et la sphère englobante du cluster C, - distPc (C, q) : la somme des distances distc (C, q) et Dppc (C), Dppc (C) étant la distance entre le centre de gravité du cluster C et son plus proche voisin. Cette définition permet de garantir qu'il existe un vecteur appartenant au cluster C dont la distance par rapport à q est inférieure ou égale à distpc. La figure 1 représente un cluster C référencé 1, de centre de gravité Cg, et les distances distc (C, q), mindist (C, q), maxdist (C, q) référencées respectivement 2,3 et 4. La figure 2 représente un cluster C avec son centre de gravité Cg, le plus proche vecteur (PPV (C)) du centre de gravité, vecteur du cluster C référencé 5, la distance Dppc (C) et distPc (C, q) référencées 6 et 7. L'algorithme de recherche exacte des plus proches voisins s'exécute en deux étapes. La première étape permet d'éliminer les clusters qui n'ont aucune chance de contenir des résultats, en utilisant juste les différentes distances qui peuvent être calculées entre un vecteur requête et un cluster. La règle habituellement utilisée permet d'éliminer un cluster C2 si sa distance minimale par rapport au vecteur requête q est supérieure à la distance maximale d'un autre cluster C1 par rapport à q. En pratique cette règle n'est pas très efficace du fait que, dès qu'il y a le moindre chevauchement entre les clusters, aucun d'entre eux ne peut être éliminé. Les figures 3 représentent un vecteur requête q positionné par rapport à un premier cluster C1 référencé 1 et un deuxième cluster C2 référencé 8. Sur la figure 3a, il n'y a aucun chevauchement entre les clusters C1 et C2. Les vecteurs de Ci sont plus proches de q que tous les vecteurs de C2. Ainsi, la règle traditionnelle permet d'éliminer le cluster C2 car mindist (C2, q) est supérieure à maxdist (Ci, q). Sur la figure 3b, les clusters C1 et C2 se chevauchent. Même s'il est visuellement évident que le cluster C2 ne peut contenir le plus proche voisin de q, la règle de sélection basée sur mindist et maxdist ne permet pas d'éliminer le cluster C2. Selon l'invention, une nouvelle règle de sélection est exploitée, pour cette première étape, qui permet d'apporter de meilleurs résultats, même en présence de chevauchement. Cette règle utilise distPc au lieu de maxdist et se formule comme suit : "Si un cluster C, possède une distance mindist (C,, q) supérieure à une distPc (C,, q) d'un autre cluster Cil alors C, n'a aucune chance de contenir le plus proche voisin de q." La figure 3c illustre un exemple d'application de cette nouvelle règle. Même si le cluster C1 référencé 1 et le cluster C2 référencé 2 chevauchent, étant donné que mindist (C2, q), référence 9, est supérieure à distPc (Ci, q), référence 7, le règle proposée permet d'éliminer le cluster C2. Dans la deuxième étape, phase d'accès aux données proprement dites, les clusters sélectionnés lors de la première étape sont ordonnés selon les valeurs croissantes de distc, mindist ou bien distPc. Cet ordre est utilisé pour la lecture des clusters. Par conséquent, le cluster qui a le plus de chances de contenir le plus proche voisin est lu en premier. Le choix du critère d'ordonnancement (distc, mindist ou distPc) dépend de la distribution des données et de la densité des clusters. Ce critère est un paramètre fixé par l'utilisateur. En général, si les clusters sont très denses, mindist est le critère le plus approprié. Cependant, si les vecteurs sont distribués de manière éparse à l'intérieur du cluster, distc ou distPc donnent de meilleurs résultats que mindist. La lecture d'un cluster se traduit par des calculs de distances entre le vecteur requête et tous les vecteurs du cluster. Ainsi, le plus proche voisin (PPV) et sa distance par rapport au vecteur requête sont mis à jour au fur et à mesure des lectures. La décision de lire le prochain cluster dans la liste est prise en fonction de sa distance mindist et de la distance au plus proche voisin courant : SI sa distance mindist est supérieure à la distance au plus proche voisin courant, ce cluster n'a aucune chance de contenir des vecteurs plus proches que le plus proche voisin courant, et donc, il n'est pas nécessaire de lire son contenu. La figure 4 montre un exemple d'un cluster C2 référencé 8 qui ne doit pas être lu, car ! t ne peut contenir un vecteur plus proche du vecteur requête q que le plus proche voisin courant (PPV (q)), vecteur référencé 10 sur la figure. L'extension de cet algorithme à la recherche des k plus proches voisins peut s'effectuer de différentes manières : - soit on utilise, lors de la première étape de la deuxième phase, la keme plus petite distance distPc parmi l'ensemble des distances distPc (C,, q) calculées pour chacun des dusters Cl, correspondant par exemple au cluster Cs, distPc (Cs, q). Ainsi, lors de l'application de la règle de filtrage permettant d'éliminer les clusters, les distances mindist (C,, q) des clusters i sont comparées à la valeur distPc (Cs, q) au lieu d'être comparées à la plus petite valeur parmi les valeurs distPc (C,, q) de l'ensemble des clusters, - soit on calcule et mémorise, pour chaque cluster Calors de la phase de structuration, la distance Dppc (C,, k) entre le centre de gravité du cluster C, et son k' p) us proche voisin parmi les vecteurs du cluster. La somme distPc (C,, q, k), qui correspond à la somme des distances distc (C,, q) et Dppc (C,, k) peut alors être calculée pour chaque cluster et c'est la valeur minimale de distPc (C,, q, k) sur l'ensemble des clusters i qui est extraite pour être comparée aux valeurs mindist (C,, q), pour le filtrage des clusters. Dans le cas ou le nombre de plus proches voisins que l'on recherche n'est pas connu a priori et dépend des applications, on calcule et mémorise pour chaque cluster Ci, lors de la phase de structuration, la distance Dppc (Ci, p) entre le centre de gravité du cluster Ci et son pième plus proche voisin parmi les vecteurs du cluster, pour plusieurs valeurs de p prédéfinies. La valeur prise en compte pour le calcul de la somme distPc (Ci, q, p), lors de la phase de recherche des k plus proches voisins, sera alors la valeur de p immédiatement supérieure à la valeur de k. Dans un exemple, 1 et n étant des entiers naturels supérieurs à 1, p est un multiple de n et les calculs, lors de la phase de structuration, sont effectués pour les nième, 2nième, 3nième,..., l. nième plus proches voisins ainsi que pour le premier plus proche voisin pour les requêtes concernant une recherche du plus proche voisin. Lors de la première étape de recherche des k plus proches voisins, pour k supérieur à 1, l'algorithme de filtrage considère alors la distance entre le centre de gravité et le pième plus proche voisin pour réaliser la sélection, avec : INT (x) représentant la la partie entière de x En effectuant un filtrage pour un nombre de plus proches voisins supérieur à k, ici la plus proche valeur de k multiple de n et supérieure à k, on est ainsi assuré de conserver les clusters renfermant au moins les k plus proches voisins. Si par exemple on choisit un multiple de 5 et si l'on cherche les 8 images qui ressemblent le plus à une image requête, c'est à dire si on choisit n=5 et k=8, l'algorithme va considérer, pour chaque cluster, la distance entre le centre de gravité et le 10"'plus proche vecteur, choisir la valeur minimale parmi ces distances et éliminer les clusters dont la distance minimale mindist est supérieure à cette valeur minimale. Enfin, lors de la deuxième étape de la phase de recherche, pour la décision de lire ou pas le prochain cluster, il suffit de considérer la distance du vecteur requête au kième plus proche voisin courant au lieu de la distance au plus proche voisin courant. Il est à noter à ce niveau que les k vecteurs les plus proches au vecteur requête ainsi que la distance entre le vecteur requête et son kième plus proche sont mémorisés. Ces informations sont mises à jour après la lecture de chaque cluster et le calcul des distances entre le vecteur requête et les vecteurs du cluster lu. La recherche exacte présentée ci-dessus permet de retrouver exactement les plus proches voisins d'un vecteur requête. Cependant, dans certains cas, les règles de sélection des clusters deviennent inefficaces et la recherche se traduit par la lecture d'une grande partie des données. Cela est dû, d'une part, au taux de chevauchement entre les sphères englobantes qui permet par exemple à un vecteur requête d'appartenir géométriquement à plusieurs clusters en même temps, et d'autre part, à la gestion de sphères englobantes de taille très importante. Ces phénomènes affectent principalement le pouvoir discriminant de la distance mindist, et par conséquent, rendent les règles de sélection moins sélectives. Ces problèmes de chevauchement et de volume, problèmes particulièrement présents dans les espaces de grande dimension, peuvent être la conséquence d'une mauvaise distribution des données, mais peuvent également provenir d'erreurs introduites par l'algorithme de clustering. En effet, l'algorithme de clustering peut insérer par erreur dans un cluster un vecteur éloigné de celui-ci et engendrer ainsi un agrandissement du rayon de sa sphère englobante, et par conséquent, un accroissement démesuré du volume de cette sphère. Pour remédier à ces problèmes, une technique de recherche approximative est exploitée qui permet de répondre aux requêtes de l'utilisateur plus rapidement avec des résultats approchés mais dont la précision est contrôlée. Cette technique permet donc aux utilisateurs de gérer un compromis entre le coût et la précision de la recherche. Elle permet notamment à un utilisateur d'effectuer des recherches progressives : commencer d'abord par une recherche approximative avec un faible taux de précision mais dont le temps de réponse est relativement faible, puis, en fonction des résultats approximatifs retournés et des objectifs de la recherche, arrêter la recherche si les résultats sont satisfaisants, ou dans le cas contraire, relancer la recherche avec un taux de précision plus élevé. Dans cette technique, au lieu de considérer les sphères englobantes des clusters, on considère des sphères de rayon plus faible mais qui englobent la majorité des vecteurs du cluster. Ces nouvelles sphères sont appelées sphères approchées. La pnse en compte de sphère approchées de rayons plus faibles que ceux des sphères englobantes permet de réduire le chevauchement entre les sphères représentant les clusters, de limiter la sphère approchée à la partie dense du cluster, et d'ignorer les points isolés du cluster, et donc, d'atténuer les effets dus aux erreurs introduites par l'algorithme de clustering. La proportion des vecteurs ignorés en considérant le nouveau rayon est fixée par l'utilisateur. Ce pourcentage reflète le taux de précision de la recherche. Les vecteurs qui se trouvent hors de la sphère approchée sont ignorés uniquement lors de l'utilisation du rayon approché dans les règles de sélection des clusters candidats. Dans le cas où un cluster est tout de même sélectionné, tous les vecteurs qu'il contient sont considérés. Ainsi, lors de la phase de construction, plusieurs rayons approximés sont calculés pour chaque cluster. Chaque rayon correspond à un taux de précision donné. L'ensemble des taux de précision à considérer est choisi par l'utilisateur lors de cette phase de construction. Néanmoins, d'autres taux de précision peuvent être rajoutés à la demande. Il suffit de calculer pour chaque cluster et pour chaque nouveau taux de précision le rayon de la sphère approchée correspondante. L'algorithme de recherche à utiliser est le même que pour la recherche exacte, à une variante près : le rayon approximé correspondant au taux de précision choisi est utilisé à la place du rayon exact. La figure 5 représente la sphère englobante et la sphère approchée d'un cluster. Pour le calcul du nouveau rayon, on considère un cluster C contenant N vecteurs, de centre de gravité Cg et de sphère englobante Se 11 de rayon raye 12. Le but de l'algorithme est de calculer, pour le cluster C, une sphère approchée Sa 13 de rayon raya 14 plus petit que raye, tout en contrôlant le nombre de vecteurs de C qui risquent d'être ignorés lors de la phase de recherche, soit une proportion a des vecteurs de C. Comme le montre la figure 5, quelle que soit la distance du vecteur requête q par rapport au cluster C, les points ignorés appartiennent à la calotte sphérique CS 15. En effet, pour un vecteur requête particulier, les points intéressants qui risquent d'être ignorés sont les points qui appartiennent à l'intersection des deux sphères : Se et la sphère de centre q et de rayon distmina référencée 17 (mindist relative à la sphère approchée 13). Cette ensemble de points dépend de la distance entre le vecteur requête q et le cluster C : plus q est éloigné de C, plus l'ensemble des points ignorés est important. Cependant, étant donné que le calcul du rayon approché doit être réalisé hors ligne et indépendemment d'un quelconque vecteur requête, on considère le cas le plus défavorable, c'est à dire lorsque q est à une distance infinie du cluster. Ainsi, quelle que soit la distance entre le vecteur requête q et le cluster C, l'ensemble des points ignorés est un sous ensemble des points qui appartiennent à la calotte sphérique CS. Cette calotte CS est le résultat de l'intersection de la sphère englobante et de l'hyperplan tangent à la sphère approchée au point d'intersection entre Sa et le droite reliant q et Cg. En d'autres termes, il s'agit de calculer le plus petit rayon raya tel que : où Ncs est le nombre de vecteurs contenus dans la calotte CS. Comme Ncs ne peut être exprimé analytiquement, on utilise une méthode numérique pour la résolution de l'inégalité (1). Sachant de plus que Ncs décroît lorsque raya croît, la recherche dichotomique dans l'intervalle [O. raye] est la plus appropriée. Étant donné que Ncs dépend à la fois de raya et de la distribution des vecteurs dans la couronne CC, son calcul peut être envisagé de deux manières différentes : - considérer que tous les vecteurs appartenant à CC peuvent appartenir à CS, auquel cas l'inégalité (1) devient : - considérer que les vecteurs appartenant à CC sont distribués de manière isotrope, donc : où Ncc est le nombre de vecteurs contenus dans la couronne CC, Nes le nombre de vecteurs contenus dans la calotte CS, volume (CS) le volume de la calotte CS, volume (Se) et volume (Sa), respectivement les volumes des sphères englobantes et approchées. Dans ce cas, l'inégalité (1) devient : En réalité, l'utilisation de l'inégalité (2) pour contrôler le taux de précision en fonction du rayon de la sphère approchée est une solution trop pessimiste car elle considère toujours le cas le plus défavorable. La solution proposée par l'inégalité (3), quant à elle, dépend de l'hypothèse de distribution isotrope des vecteurs dans la couronne CC. Si on considère que le rayon raya doit être fixé tel que la probabilité d'ignorer un vecteur du cluster soit inférieure à un seuil fixé par l'utilisateur (a), une solution plus générale peut être envisagée comme suit : Soit P (E) la probabilité d'ignorer un vecteur du cluster C quand le rayon raya est considéré au lieu du rayon raye. Si H est l'hypothèse d'isotropie de la distribution des vecteurs de C, P (E) peut s'écrire : P (E) = P (E 1 H). P (H) + P (E 1 H). P (H), (4) où P (H) et P (H) sont respectivement les probabilités que l'hypothèse d'isotropie ou de non isotropie est vérifiée. P (EIH) est la probabilité d'ignorer un vecteur sachant que les vecteurs de C sont distribués de manière isotrope. Cette probabilité peut être calculée en utilisant l'inégalité (3). D'où : P (E 1 H) est la probabilité d'ignorer un vecteur sachant que les vecteurs de C ne sont pas distribués de manière isotrope. En prenant en considération le cas extrême (inégalité 2) : Ainsi, à partir de (4), (5) et (6) on a : Sachant que l'objectif est d'avoir : P (E) a, (8) il suffit de retrouver le plus petit rayon raya tel que l'inégalité suivante soit toujours vérifiée : Dans l'inégalité (9), P (H) est le seul paramètre inconnu. De façon générale, P (H) indique si le fait de considérer que la distribution réelle des vecteurs dans le cluster est isotrope, est une hypothèse raisonnable, auquel cas P (H) est proche de 1, ou si au contraire l'hypothèse est erronée, auquel cas P (H) est proche de 0. Si la valeur de P (H) reflète très mal la distribution effective des points dans le cluster, la précision des résultats approximatifs obtenus lors de la phase de recherche pourrait être inférieure à celle fixée initialement par l'utilisateur lors du calcul du rayon approximatif. Fixer P (H) pour n'importe quel cluster aux points arbitrairement distribués relève plutôt de la statistique. En pratique, ce paramètre peut être estimé expérimentalement pour chaque cluster, ou bien être estimé pour un échantillon de clusters en considérant la valeur moyenne comme un P (H) qui s'applique à tous les clusters. Pour un cluster C et pour un taux de précision a, P (H) peut être estimé comme suit : - calculer le rayon approché du cluster en fonction de a sous l'hypothèse de distribution isotrope des vecteurs de C, - tirer aléatoirement un ensemble de vecteurs requêtes, - calculer l'estimation du nombre de vecteurs du cluster qui risquent d'être ignorés (N. a) - calculer pour chaque vecteur requête le nombre de vecteurs du cluster qui sont ignorés si le rayon approché est pris en compte au lieu de rayon exact, - estimer P (H) en calculant la proportion des vecteurs requêtes pour lesquels le nombre de vecteurs effectivement ignorés est inférieur ou égal au nombre estimé sous l'hypothèse de distribution isotrope. P (H) ainsi estimé, la recherche du plus petit raya qui vérifie l'inégalité (9) peut être effectuée en utilisant une recherche dichotomique dans l'intervalle [O, raye] pour les mêmes raisons évoquées précédemment, à savoir la partie gauche de (9) est décroissante lorsque raya croît. On rappelle que les deux façons pour contrôler les rayons, exprimées par (2) et (3), sont des cas particuliers de (9) ; (2) correspond au cas où P (H) est supposé nul alors que (3) correspond au cas où P (H) est égale à un. Ainsi, l'algorithme de calcul du rayon approché en fonction du taux de précision choisi (1-a) peut être exprimé comme suit : Algorithme calcutray~a ; Entrées : C : un cluster de centre de gravité Cg et de rayon raye, N : le nombre de vecteur C, d : dimension de l'espace des descripteurs, distrib : la densité des distances entre les vecteurs de C et Cg, P (H) : la probabilité pour que les vecteurs de C soient distribués de manière isotrope, a : probabilité pour qu'un vecteur de C soit ignoré lors de la recherche. Sortie : raya : rayon de la sphère approchée qui correspond au taux de précision 1-a. début precis *--10-4. raye ; facteur de précision du calcul de raya sup - raYe ; inf 0 ; sup+inf raYa+~ 2 Ncc PE -evalProbaE (N, Ncc, raya, raye, P (H)) ; tant que ((PE#&alpha; et sup-inf > precis) faire si (PE > a) alors inf-ray. ; si (PE (PEa) alors raya avec : - precis : un facteur de précision utilisé pour le calcul de raya. Ce paramètre peut être fixé en absolu ou bien être calculé comme une proportion de la largeur de l'intervalle total de recherche (par exemple 10-4. raye ou 0.001). - eva ! Ncc : une procédure qui permet de calculer le nombre de vecteurs qui se trouvent à une distance supérieure à raya de Cg en utilisant la distribution des vecteurs de C. Cette distribution est calculée empiriquement en utilisant les distances entre Cg et les vecteurs du cluster C. - evalProbaE : une fonction qui utilise la partie gauche de l'inégalité 9 pour calculer la probabilité d'ignorer un vecteur de C si la sphère approchée est utilisée au lieu de la sphère englobante exacte lors de la recherche. Selon cet algorithme, les bornes supérieures et inférieures de la plage dans laquelle raya est recherché sont progressivement rapprochées l'une de l'autre, la borne supérieure si la probabilité P (E) est inférieure à a, la borne inférieure dans l'autre cas, le rayon raya étant choisi au milieu de la plage. La plage initiale est (0, raye). Les itérations sont arrêtées lorsque la probabilité est égale à a ou bien lorsque la plage est devenue inférieure à une valeur prédéterminée. Un exemple de mise en oeuvre des algorithmes de recherche de plus proches voisins pour une application de recherche d'images par le contenu est donné ci-après ainsi que les résultats obtenus. Les descripteurs utilisés sont des descripteurs locaux de 24 dimensions et la métrique utilisée est la métrique euclidienne. Pour chaque image, entre 50 et 600 descripteurs sont calculés. Les requêtes exécutées sont des requêtes par l'exemple : l'utilisateur fournit une image requête, les descripteurs de celle-ci sont calculés et utilisés comme vecteurs requêtes. Pour chaque vecteur requête, les plus proches voisins sont recherchés et le résultat final est construit après fusion des résultats intermédiaires. Ainsi, chaque descripteur requête vote pour plusieurs images et une image peut être élue par plusieurs vecteurs requêtes. Enfin, les images sont classées selon le nombre de votes qui leurs ont été attribuées et seul un sousensemble d'entre elles est retenu. Il faut noter que cette technique est particulièrement adaptée pour la recherche approximative du fait que le résultat final est la consolidation de plusieurs résultats intermédiaires. La base d'images utilisée comprend 1816 images décrites à l'aide de 413412 descripteurs. Après la phase de clustering, 727 clusters ont été créés et un ensemble de vecteurs isolés a été identifié. Cet ensemble n'a pas été considéré dans le reste des expérimentations puisque notre objectif concerne l'évaluation de la sélectivité des algorithmes de recherche et leur capacité à fournir de bons résultats en lisant le moins de données possible. Pour le calcul des rayons des sphères approchées, l'hypothèse est faite que les clusters sont isotropes (P (H) =1). Le tableau ci-dessous donne quelques résultats quantitatifs et qualitatifs des recherches effectuées. L'image requête utilisée contient 139 descripteurs. Pour chaque descripteur, 15 plus proches voisins ont été recherchés. L'ensemble final des résultats se limite aux 10 images dont les scores sont les plus élevés. À titre comparatif, une recherche séquentielle et exhaustive spécialement optimisée pour les descripteurs utilisées dans cette expérience, permet de répondre à la même requête en 38.61 sec. Taux de Pourcentage Pourcentage Temps Qualité des précision moyen des moyen des d'exécution résultats ( (l-a} lOO) clusters lus pour vecteurs lus pour (sec) chaque vecteur chaque vecteur requête (%) requête (%) 100 26.77 35. 02 37. 95 Recherche exacte 1 99 3.12 7.67 10. 94 Identique à la recherche exacte 1 95 1. 43 4. 26 7. 51 Très bonne 90 0. 87 2.93 6.40 Très bonne 80 0. 46 1.60 5. 41 Bonne REVENDICATIONS 1 Procédé de recherche des k plus proches voisins d'un vecteur requête q dans une base de données multidimensionnelle de N vecteurs appliquée à des objets multimedia tels que de la vidéo, des images fixes ou des documents audio comprenant une phase de structuration de la base en clusters pour le regroupement des vecteurs et une phase de recherche, caractérisé en ce qu'il comprend les étapes suivantes : - calcul de la distance Dppc (C, p) (6) du centre de gravité d'un cluster C (1) de la base au pième plus proche vecteur voisin (5) parmi les vecteurs du cluster, p étant un entier naturel supérieur ou égal à k, - calcul de la distance distc (C, q) (2) du vecteur requête q au centre de gravité du cluster C (1) - calcul de la somme distPc (C, q, p) (7) des distances distc (C, q) et Dppc (C, p), - calcul, sur l'ensemble des clusters C de la base, de la plus petite valeur distPc (C, q, p), - élimination des clusters C de la base dont la distance mindist (C, q), qui est la plus petite distance entre le vecteur requête q et la sphère englobante du cluster C (1), est supérieure à la plus petite valeur distPc. 2 Procédé selon la revendication 1, caractérisé en ce que la phase de structuration est effectuée hors ligne et en ce que le calcul des distances Dppc (C, p) est effectué pour chaque cluster pendant cette phase, les calculs faisant intervenir q étant effectués pendant la phase de recherche. 3 Procédé selon la revendication 2, caractérisé en ce que la valeur de k est définie pendant la phase de requête, en ce que le calcul Dppc (C, p) (6) est effectué pour plusieurs valeurs de p et en ce que la valeur retenue pour le calcul de la somme est la valeur de p immédiatement supérieure à celle de k. 4 Procédé selon la revendication 3, caractérisé en ce que les valeurs de p sont des multiples d'un entier naturel n. 5 Procédé selon la revendication 1, caractérisé en ce que, lorsque les recherches sont à effectuer pour un nombre prédéterminé k de plus proches voisins, p=k. 6 Procédé selon la revendication 1, caractérisé en ce qu'il comporte : - une étape de lecture d'un cluster courant parmi les clusters non éliminés consistant en un calcul des distances entre le vecteur requête q et tous les vecteurs du cluster lu, en une mémorisation des k vecteurs les plus proches au vecteur requête q si des vecteurs plus proches à q que ceux mémorisés ont été retrouvés, et de la distance entre q et son k' plus proche voisin si cette distance est inférieure à celle mémorisée, - une étape d'élimination ou de sélection pour la lecture, d'un cluster suivant, selon que sa distance mindist est supérieure ou non à la distance entre q et son k'ème plus proche voisin courant. 7 Procédé selon la revendication 6, caractérisé en ce que les clusters sont préalablement ordonnés selon les valeurs croissantes de distc, mindist ou bien distPc pour le choix du cluster suivant. 8 Procédé selon la revendication 1, caractérisé en ce que la sphère englobante d'un cluster (11), de rayon raye (12), est remplacée par une sphère approchée (13), de même centre que la sphère englobante, mais de rayon raya (14) inférieur à raye, raya étant déterminé en fonction d'un taux de précision de la recherche a prédéfini, correspondant à la probabilité qu'un vecteur du cluster soit ignoré lors de la phase d'élimination des clusters, 9 Procédé selon la revendication 8, caractérisé en ce que le calcul du rayon approché est effectué par recherche dichotomique en faisant l'hypothèse que tous les vecteurs situés dans le volume compris entre la sphère englobante d'un cluster (11), de rayon raye (12), et la sphère approchée (13), de rayon raya (14), sont ignorés, 10 Procédé selon la revendication 8, caractérisé en ce que le calcul du rayon approché est effectué par recherche dichotomique en faisant l'hypothèse que les vecteurs situés dans le volume compris entre la sphère englobante d'un cluster (11), de rayon raye (12), et la sphère approchée (13), de rayon raya (14), sont distribués de manière isotrope, 11 Procédé selon la revendications 8, caractérisé en ce que le calcul du rayon approché est effectué par recherche dichotomique en fonction de la probabilité P (H) que l'hypothèse d'isotropie est vérifiée pour les vecteurs situés dans le volume compris entre la sphère englobante (11) et la sphère approchée (13), 12 Procédé selon la revendication 11, caractérisé en ce que l'estimation de la probabilité P (H) est effectuée pour un cluster C selon les étapes suivantes : - calcul du rayon approché raya (14) en supposant la distribution des vecteurs situés dans le volume (16) compris entre la sphère englobante et la sphère approchée d'un cluster, isotrope, - calcul de la proportion p théorique du nombre de vecteurs ignorés, soit p = N. a, - tirage aléatoire d'un ensemble de vecteurs requêtes Qi, - détermination expérimentale, pour chaque Qi, du nombre de vecteurs du cluster C qui sont ignorés si le rayon approché de C est pris en compte au lieu de son rayon exact, - estimation de P (H) par la proportion des Qi pour lesquels le nombre de vecteurs ignorés réellement est inférieur ou égal au nombre estimé sous l'hypothèse de distribution isotrope. 13 Procédé selon la revendication 11 ou 12, caractérisé en ce que l'estimation de la probabilité P (H) est effectuée en moyennant les estimations effectuées séparément sur plusieurs clusters. 14 Procédé d'indexation, caractérisé en ce qu'il met en oeuvre le procédé de recherche du plus proche voisin selon la revendication 1. 15 Procédé selon la revendication 1 pour la recherche d'image par le contenu, caractérisé en ce que la base de données est une base relative à des descripteurs d'image, les dimensions correspondant à ces descripteurs et en ce que le vecteur requête représente les valeurs de descripteurs d'une image requête.