Brevet FR2885713A1 — publié le 20061117

Procédé de recherche rapide dans une base de donnée: contenant des enregistrements tels que notamment des images, produit programme d'ordinateur et dispositif correspondants. 1. Domaine de l'invention Le domaine de l'invention est celui des bases de donnes contenant N enregistrements définis chacun par M variables. Plus précisément, l'invention concerne un procédé de recherc le rapide au sein d'une telle base de données, mettant en oeuvre une méthode permettant d'obtenir le ou les enregistrements les plus proches d'un enregistrement requête ou d'obtenir une classification des enregistrements. L'invention s'applique notamment, mais non exclusivement, cans le cas où les enregistrements contenus dans la base de données sont des images défi nies chacune par M variables. La méthode permettant d'obtenir le ou les enregistrements les plus proches d'un enregistrement requête est par exemple la méthode des plus proches voisins ou la méthode des K plus proches voisins, K z 2. La méthode permettant d'obtenir une classification des enregi; trements est par exemple la méthode des K-moyennes, la méthode de classification hiérarchique ascendante ou la méthode des cartes de Kohonen. D'une façon générale, l'invention peut s'appliquer dans tocs les cas où la méthode mise en oeuvre par le procédé de recherche au sein de la base de données comprend au moins une étape d'évaluation d'une distance entre deux enregistrements. 2. Art antérieur On présente maintenant les inconvénients de l'art antérieur dans le cas particulier où la méthode mise en oeuvre par le procédé de recherche est la méthode des plus proches voisins. Ces inconvénients, du fait qu'ils sont liés au calcul de distance, peuvent aisément être transposés à toutes les méthodes comprenant au moins une étape d'évaluation d'une distance entre deux enregistrements. La méthode des plus proches voisins est connue depuis longtemps dans le domaine de l'analyse des données. Il s'agit de rechercher dans une base de données de N enregistrements et M variables le ou les enregistrements les plus proches d'un enregistrement "requête". Il peut s'agir par exemple de rechercher dans une base d'images les images les plus proches d'une image donnée. Le problème de cette méthode intitulée méthode des plus proches voisins est un problème de performance. Il faut en effet calculer la distance de l'enregistrement requête à chaque enregistrement de la base, ce qui nécessite N*M opérations (N calculs de distances portant chacun sur M variables, aussi appelées attributs). Ce coût de calcul devient prohibitif pour les grandes bases (N > 100 000) et pour des enregistrements comportant de grands nombres d'attributs (plusieurs centaines ou milliers d'attributs, comme pour les images). Les améliorations décrites dans l'état de l'art visent à optimiser le temps de calcul de la recherche des plus proches voisins en se focalisant principalement sur le nombre d'enregistrements à explorer. Il s'agit de techniques d'indexation multi-dimensionnelles qui permettent de rapidement identifier un sous-ensemble de la base susceptible de contenir les enregistrements les plus proches de l'enregistrement requête. Le recours à des techniques d'issues du stream-mining (exploration de flux) permet une indexation approchée efficace même face à un très grand nombre d'enregistrements. Ces techniques permettent de maîtriser le compromis entre la précision souhaitée sur le résultat et les ressources (temps, mémoire) allouées à l'algorithme. Un exemple de ce type de technique est l'algorithme LSH, qui fournit une approximation de l'algorithme des k plus proches voisins par une indexation efficace des enregistrements. L'algorithme LSH est décrit dans l'article suivant: Similarity Search in High Dimensions via Hashing , A. Gionis, P. Indyk, R. Motwani, proceedings of the 25 VLDB Conference, Edinburgh, Scotland, 1999. Ces techniques de réduction du nombre d'enregistrements permettent d'envisager une réduction du nombres d'opérations de N*M à environ.Fsi * M. Les techniques d'indexation sont très efficaces pour les faibles nombres de variables. Elles deviennent plus complexes à mettre en oeuvre et moins efficaces quand le nombre M de variables augmente. A la connaissance de l'inventeur, il n'existe pas de travaux permettant d'envisager des améliorations de performances vis-à-vis du nombre M de variables. 3. Objectifs de l'invention L'invention a notamment pour objectif de pallier ces différents inconvénients de l'état de la technique. Plus précisément, l'un des objectifs de la présente invention est de fournir une technique de recherche rapide au sein d'une base de données, mettant en oeuvre une méthode permettant d'obtenir le ou les enregistrements les plus proches d'un enregistrement requête ou d'obtenir une classification des enregistrements, cette technique de recherche permettant d'améliorer les performances en réduisant le nombre d'opérations à effectuer. L'invention a également pour objectif, dans au moins un mode de réalisation, de fournir une telle technique qui soit complémentaire des techniques existantes d'indexation, de sorte que les gains en performances soient cumulatifs. Un autre objectif de l'invention, dans au moins un mode de réalisation, est de fournir une telle technique qui soit simple à mettre en oeuvre et peu coûteuse. 4. Exposé de l'invention Ces différents objectifs, ainsi que d'autres qui apparaîtront par la suite, sont atteints selon l'invention à l'aide d'un procédé de recherche dans une base de données contenant N enregistrements définis chacun par M variables, du type mettant en oeuvre une méthode permettant d'obtenir le ou les enregistrements les plus proches d'un enregistrement requête ou d'obtenir une classification des enregistrements, ladite méthode comprenant au moins une étape d'évaluation d'une distance entre deux enregistrements. Selon l'invention, ladite étape d'évaluation d'une distance comprend les étapes successives suivantes: - calcul d'une distance partielle de rang m, m M; vérification d'une condition d'arrêt déterminée pour la distance partielle calculée; - en cas de vérification positive, ladite distance est évaluée par la distance partielle calculée, sinon on incrémente la valeur du rang m d'un pas & .terminé puis on revient à l'étape de calcul d'une distance partielle. Le principe général de l'invention consiste donc à considérer que les distances partielles (distances calculées sur m Ainsi, l'invention repose sur une approche tout à fait nouvelle et inventive de l'évaluation d'une distance entre deux enregistrements, permettant d'améliorer les performances vis-à-vis du nombre M de variables. Il est à noter que la technique de l'invention (basée sur une réduction du nombre de variables) est complémentaire avec les techniques existantes d'indexation. Ainsi, les gains en performances attendus sont cumulatifs. De façon avantageuse, la méthode mise en oeuvre appartient au groupe comprenant: - la méthode des plus proches voisins; - la méthode des K plus proches voisins, K z 2; - la méthode des K-moyennes; la méthode de classification hiérarchique ascendante; la méthode des cartes de Kohonen. Cette liste n'est pas exhaustive. Dans un premier mode de réalisation particulier de l'invention, la méthode mise en oeuvre est la méthode des plus proches voisins, qui comprend les étapes suivantes: i) initialisation de variables: Dmm - 00 et xmin = 0; ii) pour chaque enregistrement x de la base de données: * évaluation de la distance D(x,y) entre l'enregistrement x et un enregistrement requête y; * si D(x,y) d. Retourner kmin comme étant l'indice du centroïde auquel doit être associé l'enregistrement x Avantageusement, les enregistrements contenus dans la base de données sont des images définies chacune par M variables. De façon avantageuse, chacune des M variables définissant une image est un pixel. L'invention concerne également un produit programma; d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur uni support lisible par ordinateur et/ou exécutable par un processeur, comprenant des instructions de code de programme pour l'exécution des étapes du procédé précité, lorsque ledit programme est exécuté sur un ordinateur. L'invention concerne aussi un dispositif de recherche dans une base de données contenant N enregistrements définis chacun par M variables, du type comprenant des moyens de mise en oeuvre d'une méthode permettant d'obtenir le ou les enregistrements les plus proches d'un enregistrement requête ou d'obtenir une classification des enregistrements, les moyens de mise en oeuvre de ladite méthode comprenant des moyens d'évaluation d'une distance entre deux enregistrements. Selon l'invention, les moyens d'évaluation d'une distance comprennent: - des moyens de calcul d'une distance partielle de rang m, m s M; - des moyens de vérification d'une condition d'arrêt déterminée pour la distance partielle calculée; - des moyens d'incrémentation de la valeur du rang m; de sorte qu'en cas de vérification positive par les moyens de vérification, ladite distance est évaluée par la distance partielle calculée, sinon les moyens de calcul d'une distance partielle sont à nouveau activés, après que les moyens d'incrémentation ont incrémenté la valeur du rang m d'un pas déterminé. 5. Liste des figures D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description suivante d'un mode de réalisation préférentiel de l'invention, donné à titre d'exemple indicatif et non limitatif, et des dessins annexés, dans lesquels: les figures 1 et 2 présentent un organigramme d'un premier made de réalisation particulier du procédé de recherche selon l'invention, dans lequel la méthode mise en oeuvre est la méthode des plus proches voisins, la figure 1 présentant l'algorithme standard de la méthode des plus proches voisins, la figure 2 détaillant une étape de calcul de distances apparaissant sur l'algorithme de la figure 1 et modifiée selon l'invention; les figures 3 et 4 présentent un organigramme d'un second mcde de réalisation particulier du procédé de recherche selon l'invention, dans lequel la méthode mise en oeuvre est la méthode des K-moyennes, la figure 3 présentant l'algorithme standard de la méthode des K-moyennes, la figure 4 détaillant une étape de calcul de distances apparaissant sur l'algorithme de la figure 3 et modifiée selon l'invention; et la figure 5 présente la structure d'un dispositif de recherche selon l'invention. 6. Description détaillée 6.1 Recherche des plus proches voisins (figures 1 et 2) 6.1.1 Présentation Il s'agit de rechercher dans une base de données de N enregistrements et M variables le ou les enregistrements les plus proches d'un enregistrerr.ent "requête". Il peut s'agir par exemple de rechercher dans une base d'images les image;; les plus proches d'une image donnée en entrée comme "requête". La base contient N images définies par M variables (une variable par pixel par exemple). Chaque enregistrement x de données de la base est un vecteur x = (x1,x2,.. .,xM) de RM On recherche pour un enregistrement requête y son plus proche voisin x au sens m d'une distance D additive sur l'ensemble des variables: D(x, y) _ d (xl, y,) . - m D peut être par exemple la norme L1: D(x, y) - E (x; - y; I. On peut également utiliser le carré de la norme L2: D(x,y) _ 2 (x1 - y, )2. g_, L'algorithme standard de recherche du plus proche voisin est le; uivant: 1. Initialiser D. _ , x _ 0 2. Pour tout enregistrement x de la base: a. Evaluer D(x,y) b. Si D(x,y) L'algorithme standard précité est illustré sur la figure 1. Les étapes 1, 2a, 2b et 3 ci-dessus y sont référencées 11, 12, 13 et 15 respectivement. L'étape:-éférencée 14 est un test permettant de revenir à l'étape référencée 12 tant que les N enregistrements n'ont pas été traités. Prenons l'exemple d'un service de recherche dans une base d'images de l'image la plus proche d'une image donnée. Un utilisateur client du service possède par exemple une image de montagne en fond d'écran sur son ordinateur personnel e': il désire trouver une image de paysage similaire en s'adressant à un service de type banque d'images. Le service reçoit l'image "requête" en entrée et doit chercher dans sa base l'image la plus proche de la requête. On commente ci-dessous les étapes de l'algorithme standard des plus proches voisins pour l'exemple du service d'image: 1. On commence en initialisant la distance de référence à très grande valeur, signifiant que l'on a pas encore de réponse 2. Pour tout image de la base d'image: a. On calcule la distance entre l'image et l'image "requête" b. Si cette distance améliore la plus petite distance en cours (distance de référence), on mémorise cette nouvelle distance de référence, et on mémorise l'image correspondante 3. On retourne à l'utilisateur l'image la plus proche, correspondant à la plus petite distance calculée 6.1.2 Notations On suppose chaque variable xi bornée LB, s x; s UB, . Soit R l'étendue maximale des distances élémentaires sur l'ensemble des attributs. R= Max Ir Sup d(x,y)- Inf d(x,y)1. 1smsM1 X,YEELB,,L8,] xyd LB,UB,] Par exemple, R - Max (UBm - LBm) pour la norme L1. 1smsM On suppose également que les coordonnées des vecteurs ont été ordonnées de façon aléatoire. On introduit les distances partielles Dm.de la façon suivante pour 1 s m s M: m Dm(X,y)=d(X;,y,), D=DM. i-1 6.1.3 Mise en oeuvre de l'invention L'algorithme de recherche du plus proche voisin, modifié selon la présente invention, est le suivant: Soit p 1- b la probabilité avec laquelle on souhaite trouver le plus proche voisin. 1. Initialiser Dmin - , X,,,ü, =0 2. Pour tout enregistrement x de la base: a. Evaluer D(x,y) au moyen des distances partielles Dm (x, y) i. Tester l'arrêt de l'évaluation en un nombre limité de Haleurs de m (par exemple les carrés: m E{4, 9, 16, 25...1) 1 Iog(Nb) ii. Arrêter si Dm/m 2 Dmm/M+ R m 2 b. Si D(x,y) On trouvera en annexe une démonstration que ce test d'arrêt permet d'apporter la garantie annoncée. Il y est également montré que le gain escompté en performances permet d'accélérer d'un facteur environ égal à J le temps de calcul de l'algorithme standard. Sur la figure 2, l'étape 2a modifiée selon la présente invention est référencée 12' (elle remplace l'étape référencée 12 sur la figure 1). Elle comprend une étape référencée 21, de calcul d'une distance partielle D. (x, y) de rang m, m s M, ainsi qu'une étape de test référencée 22 (étape 2.a.i ci-dessus) et une étape référencée 23, d'incrémentation du rang m (afin de permettre le calcul d'une nouvelle distance partielle). Prenons à nouveau l'exemple d'un service de recherche dans une base d'images. On suppose ici par exemple que les distances entre images sont évaluées sous la forme de la somme des distances entre leurs pixels. On commenter ci-dessous les étapes de l'algorithme modifié des plus proches voisins pour l'exemple du service d'image: 1. On commence en initialisant la distance de référence à très grande valeur, signifiant que l'on a pas encore de réponse 2. Pour toute image de la base d'images: a. On calcule la distance partielle entre l'image et l'image "requê.:e", en arrêtant le calcul au bout d'une partie de l'image (une partie des pixels) i. On teste de temps en temps (par exemple tous les 100 pixels) s'il est nécessaire d'évaluer la distance entièrement (avec tous les pixels). ii. Test d'arrêt L'idée est que si par exemple au bout dc 10% des pixels pris en compte, on atteint déjà 50% de la valeur de la distance de référence, il y a très peu de chance qu'avec 100% des pixels, on puisse espérer améliorer la distance de référence. On peu alors s'arrêter avant la fin de l'évaluation, et gagner ainsi en temps de calcul. Le test d'arrêt permettant d'instancier rigoureusement cette idée avec une garantie de 1 log(Na) performance est le suivant: arrêter si Dm/m Dmin/M+ = R m 2 30 b. Si cette distance améliore la plus petite distance en cours (distance de référence), on mémorise cette nouvelle distance de référence. et on mémorise l'image correspondante 3. On retourne à l'utilisateur l'image la plus proche, correspondant à la plus petite distance calculée 6.2 Méthode des K-moyennes (figures 3 et 4) 6.2.1 Présentation Il s'agit de rechercher dans une base de données de N enregistrements et M variables une partition des enregistrements en K classes résumant le mieux possible le 10 contenu de la base. Chaque classe est représentée par un centroïde, moyenne des er registrements de la classe. Chaque classe est constituée des enregistrements de la base plus proche du centroïde de cette classe que de tous les autres centroïdes. On présente ci-dessous l'algorithme standard de recherche de la partition. L'algorithme standard de recherche des K-moyennes est le suivant: 1. Choisir K enregistrements de la base au hasard XI,X2,...,XK (ils sont ensuite utilisés comme centroïdes de départ) 2. Construire K classes Ck, 1 s k s K, en associant chaque enregistrement de la base à son "centroïde" le plus proche Ck = {x:dix k, D(x,xk) D(x,x, )} 3. Recalculer les centroïdes en faisant la moyenne des enregistrements de leur classe x xk xk = ICk1 4. Arrêter si les centroïdes n'ont pas changés, sinon recommencer à l'étape 2. L'étape 2 (construction des K classes) peut être détaillée sous la forme d'un l'algorithme standard de classification d'une base sur K centroïdes, pouvant s'écrire comme suit: 2. Pour tout enregistrement x de la base: a. Initialiser D. = , kmia = 0 b. Pour tout centroïde xk,1 s k s K i. Evaluer D(x,xk) 30 ii. Si D(x,xk) L'algorithme standard précité est illustré sur la figure 3. Les étapes 1, 2 et 3 ci-dessus y sont référencées 31, 32 et 33 respectivement. L'étape référencée 34 est un test permettant de revenir à l'étape référencée 32 si les centroïdes ont changés. L'étape référencée 35 est une étape finale, permettant de retourner les K centroïdes représentant les K classes. 6.2.2 Mise en oeuvre de l'invention L'algorithme de classification d'une base sur K centroïdes (étape 2 de l'algorithme de recherche des Kmoyennes), modifié selon la présente invention, est le suivant: Soit p -1 -b la probabilité avec laquelle on souhaite classer tous les en egistrements sur le centroïde le plus proche. 2. Pour tout enregistrement x de la base, évaluer les distances D(x,xk) aux K centroïdes au moyen des distances partielles Dm (x,xk) et tester l'arrêt de l'évaluation en un nombre limité de valeurs de m (par exemple les carrés: m E{4, 9, 16, 25...1) : a. Initialiser Dmin = , kmin = 0, m s M, b. pour tout centroïde xk,l s k s K i. Evaluer la distance partielle Dm (x,xk) de rang m de l'enregistrement x au centroïde xk ii. Si Dm (x,xk) d. Retourner kmin comme étant l'indice du centroïde auquel Joit être associé l'enregistrement x La modification de l'algorithme intervient dans l'étape b) de calcul des distances. Ce calcul peut être arrêté dès que la probabilité d'améliorer la meilleure distance D,, devient suffisamment faible, ce qui correspond au test d'arrêt présenté en 2.b.iii. Par rapport à l'algorithme de recherche des plus proches voisins, les différences portent sur le type de test (comparer une distance partielle avec une distance réelle dans un cas, comparer deux distances partielles entre elles dans le second cas) et > tir le nombre de tests envisagés (N dans le premier cas, N*K dans le second cas). Sur la figure 4, l'étape 2 modifiée selon la présente invention e st référencée 32' (elle remplace l'étape référencée 32 sur la figure 3). Les étapes 2.a, 2.b et 2.d ci-dessus sont référencées 41, 42 et 45 respectivement sur la figure 4. L'étape 2.c ci-dessus est représentée sur la figure 3 par une étape de test référencée 43 ( res:e-t-il plus de un centroïde candidat ? ) et une étape d'incrémentation du rang m, référencée 44. Ainsi, en cas de vérification positive au test de l'étape référencée 43, on effectue l'étape référencée 44 avant de revenir à l'étape référencée 41. En cas de vérification négative au test de l'étape référencée 43, on passe à l'étape référencée 45. Enfin, l'étape référencée 46 est un test permettant de revenir à l'étape référencée 41 tant que les N enregistrements n'ont pas été traités. On trouvera en annexe une démonstration que le test d'arrêt ci-dessus permet d'apporter la garantie annoncée. 6.3 Dispositif de recherche (figure 5) La figure S présente enfin la structure d'un dispositif de recherche selon l'invention, qui comprend une mémoire 51, et une unité de traitement 50 équipée d'un microprocesseur, qui est piloté par un programme d'ordinateur (ou application) 52 permettant la mise en oeuvre du procédé de recherche selon l'invention. L'unité de traitement 50 reçoit en entrée des requêtes clients 53, que le micropro cesseur 50 traite, selon les instructions du programme 52 et en fonction du contenu d'une base de données 55, pour générer des réponses 54. ANNEXE Une technique d'optimisation pour les algorithmes de traitement de données en grandes dimensions s 1. Algorithme de recherche du plus proche voisin On s'intéresse ici au problème de l'indexation performante d'une instance sur une base de parangons, c'est-à-dire à la recherche du plus proche voisin de l'instance parmi les parangons. Soit une base de parangons comportant N instances, représentés par des vecteurs de M attributs X2... XM dans RM. Chaque instance x de données est un vecteur x = (x1,x2 xM) . On recherche pour un instance y à classifier sont plus proche voisin x au sens d'une distance D additive sur l'ensemble des attributs: M D(x,y)-d(x;,y,)É _, D peut être par exemple la norme L1 (on peut également utiliser le carré de la norme L2). L'algorithme de recherche de plus proche voisin est en O(N.M), ce qui est prohibitif quand N et M sont grands et que l'opération d'indexation doit ce faire un très grand nombre de fois. Ici PAC signifie Probably Approximately Correct. Pour une instance à indexer, on cherche une solution approximative, c'est-à-dire un parangon dont la distance soit proche de la distance optimale (à e près) avec une probabilité p- 1-â donnée. L'objectif est ici d'optimiser le temps de recherche de ce parangon, au détriment potentiel de la qualité (mais de façon contrôlée). 1.1 Indexation sur un sous-échantillon aléatoire Une solution basique consiste à recherche le plus proche voisin sur une sou i-base de taille n de la base de parangons. Voyons quelle garantie on peut apporter sur la qualilé de la solution. Soit K s N et e =1/K un pourcentage. Par exemple, e =1% pour K=100 pour fixer les idées. Chaque distance à un parangon a une probabilité 1/K d'être dans le pourcentage e% des distances les plus proches à l'instanceà indexer, et (1-1/K) d'être dans les distances plus grandes. En cherchant la meilleure de toutes les distances parmi n parangons, la probabilité de ne pas avoir trouvé au moins une instance dans le top e% des distances est égale à (1-1/K)" . 16 Or (1-1/K)K -1/e. On a alors la garantie statistique suivante liant les paramètres E, p- 1â et n: â- (1/e) w, soit n=-ln(1-p)/E. L'algorithme de recherche approximative du meilleurs parangon est alors en ()(M.1n(1/6)/e) Par exemple, si l'on cherche à approcher de la distance optimale à 0.1 % près avec une probabilité supérieure à 99%, il faut prendre n=4605 parangons à tester. Cette méthode basique permet d'évaluer les performances d'algorithmes d'indexation qui doivent faire au moins aussi bien. 1.2 Elagage déterministe L'algorithme précédent peut être légèrement optimisé en notant que qua:id on calcule la distance entre l'instance à évaluer et un nouveau parangon, on additionne itérativement les M contributions par attribut pour obtenir la distance. On passe alors par M distances partielles faisant intervenir une partie des attributs. Dès qu'une somme partielle dépasse la meilleure distance actuellement obtenue, on peut abandonner le parangon en cour, sans risque de manquer une amélioration. Cet élagage est de plus en plus efficace au fur et ii mesure que l'on a exploré d'avantage d'instances, la borne inf courante (de plus en plus petite) étant plus facilement atteinte par les distances partielles. On peut tenter d'améliorer l'efficacité de cet élagage par une heuristique "kinler" consistant à ordonner les attributs par variabilité (entropie) décroissante. Les attributs lies plus variables vont entraîner des accroissements des sommes partielles plus importants, donc favoriser le dépassement de la borne inf plus rapidement. 1.3 Elagage probabiliste Ces deux heuristiques sont déterministes: on ne perd rien en qualité de la solution, et on gagne potentiellement en temps d'exécution. Il est tentant d'aller plus loin en acceptant une perte potentielle, mais contrôlée en probabilité. L'idée de base est la suivante. Quand on a calculé une distance partielle, on peut être encore très loin de la borne et ne pas pouvoir élaguer à coup sûr. Par contre, les statistiques sur les distribution des valeurs pour cette distance partielle peuvent montrer que 1 on à très peu de chance qu'au final, on soit parmi les distances les plus petites. Dans un premier temps, on cherche à évaluer la qualité des distances partielles en tant qu'estimateur de la distance réelle. Les distances partielles Dm.sont définie par: Dm(x,Y)=d(xi,Yi), D=DM. i-1 On suppose chaque attribut X1 borné LBi s x, s UB. Soit R l'étendue maximale des distances élémentaire sur l'ensemble des attributs. R- Max I( Sup d(x,y)- le d(x,y)l. 1smsM1 x,yE{LB,UB,J x,yE[LB;,UB,] Par exemple, R - Max (UBm - LBm) pour la norme L1. 1smsM On suppose également que les coordonnées des vecteurs ont été ordonnées de façon aléatoire. Théorème 1: Pour 0 s Dmin et Dm /m Z Dmin / M, on a ( 2m(Dm/m Dmin/M)2i J P1 D s Dmin} s expll- R2 Preuve: L'ensemble {d(x,,y,)} 1sisM correspond aux valeurs d'une variable aléatoire de moyenne D/M, et d'étendue R. Les distances partielles pondérées Dm/m correspondent à la moyennc de m tirages indépendants de cette variable aléatoire. La borne de Hoeffding permet de majorer la probabilité que l'écart entre la moyenne estimée s'écarte de la moyenne de plus de E: P Dm -D M 2 E ex (2mE2\ [m pl R2 / On obtient le résultat annoncé avec E = Dm/m-Dmin/M É Proposons maintenant un algorithme d'élagage probabiliste exploitant le théorème 1. Algorithme 1: Soit O s Dmin une distance et p = 1- b la probabilité avec laquelle on souhait; trouver un plus proche voisin de distance D s Dm;n s'il existe. Soit p'(N)= pi/N =1-b'(N). É Pour tout point x à évaluer o Evaluer D au moyen des distances partielles D. o Tester l'arrêt de l'évaluation en un nombre limité de valeurs de m (par exemple les carrés) 1 log(1/b'(N))R2 ^ Arrêter si Dm /m i D n / M + Théorème 2: L'algorithme 1 répond correctement à ses spécifications. Preuve: Soit N' s N le nombre de points non évalués entièrement. En tout point non évalué entièrement, on a: 2m(D /m-%n/M)2 m 2 z log(1/ô') . R2 En appliquant le théorème 1, on obtient P{ D Dmin} s b' , soit P {D 2 Dmm} p. On a ainsi une garantie sur chaque point, mais comme le test d'arrêt est potentiellement répété (de façon indépendante) sur tous les points, il faut en évaluer la fiabilité sl.r l'ensemble des tests, c'est-à-dire: P{Vn,lsnsN,D(xn,y)zDmn,}zp'. La probabilité que tous les points non évalués entièrement soit à une distance supérieure à Dmin est supérieure à p'' . p = p'N s p'N' . CQFD. _ On en déduit l'algorithme d'élagage suivant qui permet de trouver le plus proche voisin avec une probabilité contrôlée. Il s'agit d'une variante de l'algorithme 1, dans laquelle la distance du plus proche voisin est améliorée itérativement au cours de l'exploratio i de la base de parangons. Algorithme 2: Soit p =1- b la probabilité avec laquelle on souhaite trouver le plus proche voisin. Soit p'(N)= É Initialiser Dm. =cc É Pour tout point x à évaluer o Evaluer D au moyen des distances partielles Dm o Tester l'arrêt de l'évaluation en un nombre limité de valeurs de m (par exemple les carrés) 1og(l/b'(N)) R2 É Arrêter si Dm/m a Dmin/M+ m 2 o Si D Preuve: Introduisons la valeur de Dmin n correspondant à la meilleure évaluation de Dmn au moment de l'exploration de l'instance n. Comme Dmin s D,mn n, on obtient P {D Dmin} Z P {D Z Dm, n} Z p' selon le théo ème 2. La preuve est alors la même que celle du théorème 2. _ Théorème 4: Soit p = 1-b avec k - 1/b. Le critère d'arrêt des algorithmes 1 et 2 peut être approximé de la façon suivante: 1 /log(kN) Dm/miDm/M+T R m 2 Preuve: Soit p,... pl/N = _â,. p(1-b')N =1 11-b')kN (1- ') _ é-1/kN b'-1/kN _ 1.4 Performance de l'élagage probabiliste En terme de préparation, l'élagage probabiliste demande uniquement un ordonnancement aléatoire des instances et des attributs, et une évaluation de l'étendue R des données. Il s'agit donc d'une "lazzy" préparation, permettant d'ajouter/retrancher facilement des instances, et également des attributs. En terme de classification, le surcoût de l'élagage probabiliste est négligeab: e. On calcule les distances partielles, qui doivent de toute façon être évaluées. En rajoute une série de tests, ce qui coûte 0(, /M) par instance si l'on effectue les tests pour les valeurs de rr. correspondant à des carrés entiers. Dans le pire des cas où l'élagage serait complètement inefficace, le surcoût algorithmique est négligeable. En interprétant le critère d'arrêt de l'algorithme 1, l'élagage est d'autant plie efficace que les distances sont distribuées de façon contrastée (pour avoir des distances partielles éloignée de la distance minimale) et que le nombre d'attributs est important (pour avoi - des évaluations fiables des distances partielles). Dans le cas d'une base aléatoire, le rapport entre la distance max et la distance min tend vers 1, ce qui rend l'élagage inopérant. Prenons un exemple théorique d'une distance de Hamming, avec des distances moyennes D/m uniformément distribuées entre 0 et 1. Pour les distances moyennes proches de 0, l'évaluation des distances partielles devra être menée plus loin que pour les distances loin de 0, selon la formule suivante (cf. critère algorithme 1) l log(kN) D/ M + . m 2 log(1cN)( M\2 Le nombre moyen d'attributs à évaluer sera donc proportionnel à c(m)=f m(.r) dx. 0 a log(kN) 1 ( \2 C(M) fMdx+ 2 1 dx o a log(kN) (l 'log( ) C (M) = aM + 1 avec a = 2 l a 2M c(M) s n-.J21og(kN) On adonc MZma 2 l D) Si l'on passe d'une distance de Hamming à une distance quelconque, il faut prendre en compte l'étendue:-- C(M)yMR 21og(kN). Dans le meilleurs des cas, il est donc raisonnable d'escompter un gain de performance de l'ordre de ' . On peut noter que la performance de l'élagage dépend de l'étendue R. Si l'étendue est homogène sur l'ensemble des dimensions (comme dans le cas d'une distance de Hamming), la borne d'élagage est satisfaisante. Dans le cas contraire où l'étendue domine sur quelques dimensions au détriment des autres, il peut être intéressant d'isoler les dimensions de grande étendue pour les calculer systématiquement pour le "début" des distances, 1;t de faire porter l'élagage sur les dimensions restantes. Si l'on a ordonné les dimensions par étendue décroissante, soit R(n) l'étendues des n dernières dimensions. R(n) est une fonction décroissante de n avec R(N) = R. En se basant sur le nombre moyen d'attributs à évaluer présenté ci-dessus, la formule suivante (à minimiser) permet de trouver un compromis acceptable sur le nombre de dimensions à évaluer inconditionnellement: C(M) N-n+yw1R(n).J21og(kN) 2. Algorithme probabiliste des K-moyennes On cherche cette fois à comparer deux distances Dy = D(x,y) et DZ - D(x,z) en décidant du point y ou z le plus proche de x. Il s'agit toujours de minimiser le nombre de calcul à effectuer pour obtenir une décision fiable. Dans un premier temps, on cherche à évaluer la qualité des distances Partielles en tant qu'estimateur des distance réelle. Les distances partielles Dxm.sont définie par: m D m (X,Y) = d (xi, Y,) , Dx = Dx,M É i-I m' Dym,(X,Y)_1d(xi,Y;), Dy =Dy,M i.l Soit R l'étendue maximale des distances élémentaires sur l'ensemble des attributs. On suppose également que les coordonnées des vecteurs ont été ordonnées de façon aléatoire. Théorème 5: Pour o s D et Dy m, D/ M s Dx m /m, on a {Dx ( 2m (D x m/m- D/M)2 2m'(Dy,m,/m'- D/M)2 PsDsDy}sexe - 2 R2 R Preuve: P{Dx sDsDy}=P{Dx sD,DsDy}. P{D sDsDy}=P{DXsD}P{DeD}. Le résultat annoncé découle alors du théorème 1._ 10 Théorème 6: Pour Dy m, /m' s Dx m /m, on a mm' 2 P 2m+m(Dx,m/m-Dym./m) {D s D y} s exe - R2 Preuve: La borne du théorème 5 est une fonction de D. On peut chercher la position du minimum Do en dérivant la borne par rapport à D. On trouve M(Dm +Dym,) Da - m + m' Le résultat du théorème 5 est vrai pour toute valeur de D, et donc en particulier pour Do. Après simplification, cela correspond au résultat annoncé._ Dans l'algorithme des K moyennes, on dispose d'une base de N points. et de K points "moyens". On cherche à affecter chacun des points de la base au point moyen le plus proche. L'affectation de tous les points repose sur le calcul de N*K distances, nécessitant N*K*M opérations. On peut utiliser le résultat du théorème 6 pour proposer une version probabiliste optimisée de l'algorithme des K moyennes. On peut escompter accélérer significativement les calculs pour tous les points proches d'une des K moyennes, et ne condui re les calculs de distance au bout que pour les points proches des frontières entre deux ou plusieurs zones d'influence. Algorithme 3: Soit p 1- b la probabilité avec laquelle on souhaite trouver le point moyen yk,1 k K le plus proche pour tout point x. Soit p'(NK) = p'INK = 1- 8'(NK) . Pour tout point x à évaluer o Evaluer les distances Dk = D(x,yk) au moyen des distances partielles Dk.m = Dm (x' yk) o Tester l'arrêt de l'évaluation en un nombre limité de valeurs de m (par exemple les carrés supérieurs à K2, car chaque test demande O(K) opérations) ^ Rechercher la distance DL, la plus faible ^ Pour chaque k, arrêter l'évaluation de Dk si D k m/m i Dk m/m+ mR J1og(1/fi'(NK)) ^ Affecter le point x au point moyen yk ci celui-ci es: le dernier point en lice REVENDICATIONS 1. Procédé de recherche dans une base de données contenant N enregistrements définis chacun par M variables, du type mettant en oeuvre une méthode permettant d'obtenir le ou les enregistrements les plus proches d'un enregistrement requête ou d'obtenir une classification des enregistrements, ladite méthode comprenant au moins une étape d'évaluation d'une distance entre deux enregistrements, caractérisé en ce que ladite étape d'évaluation d'une distance comprend les étapes successives suivantes: - calcul (21; 42) d'une distance partielle de rang m, m M; vérification (22; 42) d'une condition d'arrêt déterminée pour la distance partielle calculée; - en cas de vérification positive, ladite distance est évaluée par la distance partielle calculée, sinon on incrémente (23; 44) la valeur du rang m d'un pas déterminé puis on revient à l'étape de calcul d'une distance partielle. 2. Procédé selon la revendication 1, caractérisé en ce que la méthode mise en oeuvre appartient au groupe comprenant: est la méthode des plus proches voisins, qui comprend les étapes suivantes: i) initialisation de variables: Dm;n - 00 et xmin = 0; ii) pour chaque enregistrement x de la base de données: * évaluation de la distance D(x,y) entre l'enregistrement x et un enregistrement requête y; * si D(x,y) _ 2; - la méthode des K-moyennes; - la méthode de classification hiérarchique ascendante; - la méthode des cartes de Kohonen. 3. Procédé selon la revendication 1, caractérisé en ce que la méthode mise en oeuvre - vérification (22) de la condition d'arrêt suivante pour la distance partielle calculée: 1 I1og(N/b) Dm/m i Dmin/M+ T R,avec p -1- â la probabilité avec laquelle on m 2 souhaite trouver l'enregistrement le plus proche de l'enregistrement requête y; si la condition d'arrêt est vérifiée, ladite distance D(x,y)est évaluée par la distance partielle calculée D,,, (x, y) , sinon on incrémente (23) la valeur du rang m d'un pas déterminé puis on revient à l'étape de calcul (21 d'une distance partielle. 4. Procédé selon la revendication 1, caractérisé en ce que la méthode mise en oeuvre est la méthode des K-moyennes, qui comprend les étapes suivantes: i') choisir K enregistrements de la base de données au hasard x1.x2,...,xK, utilisés comme K centroïdes de départ; ii') construire K classes Ck, 1 k s K, en associant chaque enregistrement x de la base de données à son centroïde le plus proche parmi Ics K centroïdes xt,x2,..., xK: Ck ={x:di k,D(x,xk)s D(x,x,)} iii') recalculer les centroïdes en faisant la moyenne des enregistrements de leur classe: xk ICk) iv') arrêter si les centroïdes n'ont pas changés, sinon recommencer à l'étape ii') ; et en ce que l'étape ii') comprend elle-même les étapes suivantes (41 à 45), pour tout enregistrement x de la base: a. Initialiser des variables Dmin = 00, kmin - 0, m s M, b. Pour tout centroïde xk,1 k K i. Evaluer la distance partielle Dm (x,xk) de rang m de l'enregistrement x au centroïde xk ü. Si D. (x,xk) d. Retourner km.n comme étant l'indice du centroïde auquel doit être associé l'enregistrement x 5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que les enregistrements contenus dans la base de données sont des images définies chacune par M variables. 6. Procédé selon la revendication 5, caractérisé en ce que chacune des M variables définissant une image est un pixel. 7. Produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur, caractérisé en ce qu'il comprend des instructions de code de programme pour l'exécution des étapes du procédé selon l'une quelconque des revendications 1 à 6, lorsque ledit programme est exécuté sur un ordinateur. 8. Dispositif de recherche dans une base de données contenant N enregistrements définis chacun par M variables, du type comprenant des moyens de en oeuvre d'une méthode permettant d'obtenir le ou les enregistrements les plus proches d'un enregistrement requête ou d'obtenir une classification des enregistrements, les moyens de mise en oeuvre de ladite méthode comprenant des moyens d'évaluation d'une distance entre deux enregistrements, caractérisé en ce que les moyens d'évaluation d'une distance comprennent: - des moyens de calcul d'une distance partielle de rang m, m s M; - des moyens de vérification d'une condition d'arrêt déterminée pour la distance partielle calculée; - des moyens d'incrémentation de la valeur du rang m; de sorte qu'en cas de vérification positive par les moyens de vérification, ladite distance est évaluée par la distance partielle calculée, sinon les moyens de cale Il d'une distance partielle sont à nouveau activés, après que les moyens d'incrémentation ont incrémenté la valeur du rang m d'un pas déterminé.