Télécharger le fichier pdf d’un mémoire de fin d’études
Espace multidimensionnel
Un espace multidimensionnel est défini lorsque les éléments de l’ensemble considéré sont des vecteurs, homogènes ou hétérogènes, dont les composantes sont totalement ordonnées.
Le cas le plus fréquent est celui des sous-espaces orthonormés, c’est-à-dire dé- finis sur Rn et munis d’une norme, c’est-à-dire des espaces vectoriels.
Nous ne nous attardons pas sur ces derniers. Nous soulignons seulement que les espaces vectoriels sont des sous-ensembles des espaces métriques. En effet, toute norme sur un espace vectoriel est également une métrique, mais l’inverse n’est pas nécessairement vrai. (Pour les espaces multidimensionnels quelconques, il faut fournir une distance et il deviennent alors naturellement des espaces mé- triques (cf. section suivante).) Cela peut devenir un avantage, une distance donnée révélant la dimension intrinsèque (cf. page 26)des objets plutôt que la dimension « réelle » des vecteurs (cf. section 2.6.1).
En sens inverse, il est possible de plonger arbitrairement un espace métrique dans un espace vectoriel. Pour cela, il suffit de choisir un nombre n > 0 d’éléments de l’espace vectoriel, distincts les uns des autres, et de les ordonner arbitrairement. Les distances de chacun des éléments de l’espace métrique à ces éléments-pivots, ordonnées de la même façon, fournissent des vecteurs dans Rn. Une telle approche est utilisée par FastMap [35] pour réduire la dimension des données.
Il existe donc des nombreux points communs ou rapprochements possibles entre ces deux familles d’espaces de données.
Fonctions de distance
Les fonctions de distance peuvent être adaptées à une application spécifique ou à un domaine d’application donné. Elles sont alors spécifiées par un expert. Cependant, la définition d’une fonction de distance donnée n’est généralement pas limitée à un unique type de requêtes. Il existe de nombreuses d’un usage assez vaste.
Les fonctions de distance peuvent être divisées en deux groupes suivant les valeurs retournées :
• Les fonctions de distance discrètes ne renvoient qu’un petit ensemble de valeurs. Un exemple du cas discret est la distance d’édition entre deux chaînes de caractères (nombre de caractères à insérer, supprimer ou déplacer) ou encore la distance de HAMMING entre chaînes de bits (nombre de couples de bits différents deux à deux). Des techniques d’indexation spécifiques ont été proposées pour ces cas-là.
• Pour les fonctions de distance continues, le cardinal de l’ensemble des valeurs renvoyées par une fonction de distance est sinon véritablement infini du moins très grand. Un exemple du cas continu est la distance euclidienne (cf. ci-dessous, formule (2.8)).
Les fonctions de distance peuvent également être classées en fonction de leur coût de calcul, en retenant tout simplement leur complexité asymptotique. Les plus simples sont linéaires en la taille de l’objet, ce qui est optimal. Beaucoup sont déjà quadratiques, comme les distances entre ensembles ou la distance d’édition mentionnée ci-dessus. Mais d’autres peuvent présenter des complexités encore supérieures. Dans nos travaux nous ne nous intéressons pas directement aux distances utilisées mais tenons compte de cette contrainte et tentons de minimiser le nombre de calculs de distances.
À titre d’illustration, fournissons un exemple emblématique de métrique, la famille des distances de MINKOWSKI.
Distances de MINKOWSKI. Les distances de MINKOWSKI forment une famille de fonctions métriques, appelées « métriques Lp », qui peuvent être appliquées sur différents types de données à partir du moment où l’on peut les considérer, voire transformer, en vecteurs de nombres.
Définition 2 (Métriques Lp) Soit (x1, . . . , xn) ∈ Rn et (y1, . . . , yn) ∈ Rn deux vecteurs. Soit p ∈ R avec p ≥ 1.
Alors, on définit : L p((x1, . . . , xn), (y1, . . . , yn)) = sp X∀i |xi – yi|p. (2.6)
Hyper-plan
Un deuxième concept important dans un espace métrique est celui d’hyper-plan. Un hyper-plan est indirectement déterminé par deux éléments distincts.
Définition 6 (Hyper-plan généralisé) Soit (O, d) un espace métrique. Soit (p1, p2) ∈ O2 deux pivots, avec d(p1, p2) > 0.
Alors H(O, d, p1, p2) – ou seulement H(p1, p2) – définit un hyper-plan : H(O, d, p1, p2) = {o ∈ O : d(p1, o) = d(p2, o)} ; (2.13)
qui permet de partitionner l’espace en deux sous-espaces : G(O, d, p1, p2) = {o ∈ O : d(p1, o) ≤ d(p2, o)} ; D(O, d, p1, p2) = {o ∈ O : d(p1, o) > d(p2, o)} ; (2.14)
soit respectivement le demi-plan « gauche » au sens large – G(p1, p2) – et le demi-plan « droit » au sens strict – D(p1, p2).
En d’autres termes, les objets de G(p1, p2) sont plus proches de p1 que de p2 (ou à égale distance des deux), et les objets de D(p1, p2) sont strictement plus proches de p2 que de p1.
Il faut noter que, dans un espace métrique, un hyper-plan quelconque ne peut pas être défini. Il lui faut absolument s’appuyer sur la présence de deux élé- ents de l’ensemble. Par ailleurs, dans un espace métrique général, des propriétés comme le parallélisme, l’orthogonalité, etc., ne sont pas toujours définissables.
Requête par similarité
Le concept de boule vu ci-dessus permet de définir le « voisinage » d’un élément. En terme de recherche, nous parlerons de « requête par similarité ».
Une requête par similarité est définie à partir d’un élément de référence. Cet élément n’appartient pas nécessairement à l’ensemble de référence considéré. À partir de là, il est possible de définir différents types de requêtes. Nous en présentons deux :
1. les requêtes par intervalles (traduction approximative de range query) ;
2. les requêtes de k plus proches voisins (k-ppv ou encore kNN pour k-nearestneighbours).
Plus proches voisins
Dans une requête de plus proches voisins, nous recherchons les k objets les plus similaires à un élément donné. La requête n’est rien d’autre qu’un élément de référence q et le nombre d’éléments recherchés k (cf. figure 2.6).
L’ensemble des réponses n’est jamais vide, sauf dans des cas particuliers triviaux. En outre, sa taille est définie au préalable par l’utilisateur. Ce type de requêtes peut être formalisé par la définition suivante.
Définition 8 (Requête kNN) Soit (O, d) un espace métrique. Soit q ∈ E un élément requête. Soit k ∈ N le nombre recherché de réponses.
Alors NN(O, d, q, k) définit une requête kNN, dont la valeur est S ⊆ E de telle sorte que |S| = k (sauf si |E| < k) et ∀(s, e) ∈ S × E, d(q, s) ≤ d(q, e).
Dans le cas où plusieurs objets se trouvent à la même distance de la requête, le choix de fait d’une manière arbitraire [8, 14].
Ici aussi, il s’agit de déterminer un sous-ensemble en extension à partir d’une boule. La différence par rapport à une requête par intervalle vue précédemment et que le rayon r est initialement inconnu. Il sera déterminé a posteriori comme étant égal à la distance au ke élément de la réponse. (Notons qu’il peut y avoir une toute petite différence entre les deux définitions lorsqu’il existe des éléments ex æquo. Autrement dit, lorsque la réponse à une requête kNN est connue, se servir de la ke distance pour définir la requête par intervalle correspondante peut renvoyer un sur-ensemble.)
Dimension d’un espace métrique et problèmes liés
Nous avons déjà évoqué la difficulté de définir certaines notions classiques des espaces vectoriels dans les espaces métriques. La dimension est l’une d’entre elles.
Dimension intrinsèque
Les données multidimensionnelles présentent naturellement un nombre donné de dimensions. Dans les espaces métriques, cette notion disparaît, non seulement parce que l’on ne prend en compte l’objet que comme un tout et non pas comme un ensemble de composantes, mais aussi parce que certains objets sont naturellement sans dimension perceptible. C’est le cas d’une chaîne de caractères, d’un ensemble d’éléments quelconques, d’un graphe, etc.
Dans un espace métrique, la notion de « dimension » est alors traduite par des définitions autres. Une de ces définitions est celle de la dimension intrinsèque. Cette notion correspond à la notion de dimension « réelle » d’un ensemble de données, au sens où il serait possible de transformer toutes les données dans un espace vectoriel de cette dimension-là tout en conservant leurs distances respectives [25]. Une façon de définir une dimension intrinsèque est fournie ci-dessous.
Définition 9 (Dimension intrinsèque) Soit M = (O, d) un espace métrique. Soit E ⊆ O un sous-ensemble d’éléments.
• µ est la moyenne des distances observées entre tout couple d’éléments :µ =|E| X∀(x,y)∈E2d(x, y) ; (2.16)
• σ2 est sa variance :µ =1|E| X∀(x,y)∈E2d(x, y)2 – µ2. (2.17)
Elle donne une mesure de la complexité de l’indexation d’un ensemble de données [75, 18, 85]. Elle a été établie de manière à retrouver approximativement, pour les distances L1 et L2, les dimensions d’un espace vectoriel uniformément peuplé. Soulignons que le paramètre principal de la formule est la variance. Plus cette valeur est proche de zéro, plus il est difficile de distinguer les éléments les uns des autres, donc de les classer ou de les indexer. Cette constatation a également été faite préalablement pour les espaces vectoriels, le comportement statistique des données en grandes dimensions étant assez particulier.
En résumé, cette mesure de dimension intrinsèque permet de déterminer à quel point les éléments sont équidistants les uns des autres. Or, cela apparaît naturellement dans les espaces de grandes dimensions.
Partitionnement des données
L’idée principale du partitionnement de données est la création de paquets regroupant des données, également appelés « formes englobantes ».
Nous allons voir comme principaux représentants de cette approche : l’arbre-R, une technique très ancienne, et d’autres techniques un peu plus récentes : l’arbreSR et l’arbre-X.
Arbre-R
L’arbre-R a été proposé par Antonin Guttman [39, 58]. Il est parmi les premières propositions qui indexent des données dans les espaces multidimensionnels sous la forme d’un découpage hiérarchique équilibré en ensembles de rectangles. C’est originellement une méthode d’accès spatiale utilisée pour indexer des coordonnées géographiques.
Définition d’un arbre-R
La structure d’un arbre-R est basée sur la décomposition de l’espace autour de rectangles englobants minimaux (REM). Dans un espace multidimensionnel, disons Rn par souci de simplification, un rectangle englobant minimal est défini par un
couple de vecteurs tel que les composantes du premier vecteur sont deux à deux inférieures ou égales à celles du second vecteur. Ce couple de coordonnées définit le plus petit volume qui englobe un ensemble de points et/ou de formes géomé- triques donné.
Définition 10 (REM dans Rn) Soit S ⊆ Rn un ensemble de points. Alors le couple (x, y) ∈ (Rn)2 avec :
• x = (x1, x2, . . . , xn) ;
• y = (y1, y2, . . . , yn) ; définit le rectangle englobant minimal (REM) de S si, et seulement si : ∀1 ≤ i ≤ n, xi = min{zi, ∀z ∈ S},yi = max{zi, ∀z ∈ S}
On notera cette opération sous la forme fonctionnelle : (x, y) = REM(S). (3.2)
Notons qu’il faudrait parler d’hyper-rectangles (ou de rectangles de degré n) plutôt que de simples rectangles.
Cette définition s’étend à des ensembles d’hyper-rectangles.
Définition 11 (REM sur Rn) Soit R ⊆ (Rn)2 un ensemble d’hyper-rectangles.
Alors, le couple (x, y) ∈ (Rn)2 définit le rectangle englobant minimal (REM) de R si, et seulement si :∀1 ≤ i ≤ n, xi = min{zi, ∀(z, t) ∈ R},yi = max{ti, ∀(z, t) ∈ R}.
Partitionnement de l’espace
Suite au principal problème associé aux techniques d’indexation basée sur le partitionnement des données, c’est-à-dire les recouvrements entre formes englobantes, il existe une autre approche où les intersections de régions sont nulles. Cette approche est basée sur le partitionnement de l’espace.
Plusieurs techniques s’appuient sur ce principe : arbre-LSD, fichier-grille, etc. Nous introduisons l’arbre-kD.
Arbre-kD
L’arbre-kD [7] est un type d’index basé sur le partitionnement d’un espace de dimension k suivant chacun de ses axes. Contrairement à une « simple » grille, tous les axes ne sont pas pris en compte simultanément. Les données sont structurées sous la forme d’un arbre binaire. À chaque niveau de l’index, on partitionne le sous-espace en cours en deux sous-sous-espaces selon une dimension différente (cf. figure 3.7). Les choix (i) de l’axe et (ii) de la valeur selon laquelle on bipartitionne les données sur cet axe sont des paramètres importants.
Techniques basées sur le partitionnement de l’espace
Pour les techniques à base de partitionnement de l’espace, deux types de partitionnement ont été développés : le premier s’appuie sur les hyper-plans (arbres GH, GNAT, EGNAT, etc.) tandis que le second utilise les boules (arbres VP, mVP, MM, oignon, etc.).
Arbre-VP
L’arbre-VP [91] (pour vantage point ou « point de vue avantageux ») est un arbre binaire où le partitionnement se fait en utilisant une boule.
Définition de l’arbre-VP
Dans l’arbre-VP (cf. figure 4.4), on choisit un objet p aléatoirement et on le considère comme le pivot. Puis on calcule la médiane des distances dm de l’ensemble des objets au pivot et on le considère comme le rayon de la boule. Le pivot p et la médiane dm sont utilisés pour définir une boule B(p, dm) qui va partager l’espace en deux sous-espaces disjoints.
Définition 17 (Arbre-VP) Soit (O, d) un espace métrique. Soit E ⊆ O un sousensemble d’éléments à indexer.
|
Table des matières
1 Introduction
1.1 Contexte
1.2 Problématique
1.3 Contraintes préalables
1.4 Idées préliminaires
1.5 Contributions
1.6 Plan de l’étude
I État de l’art
2 Brève introduction aux espaces métriques
2.1 Espace métrique
2.2 Espace multidimensionnel
2.3 Fonctions de distance
2.4 Notions de boule et d’hyper-plan
2.4.1 Boule
2.4.2 Hyper-plan
2.5 Requête par similarité
2.5.1 Requête par intervalle
2.5.2 Plus proches voisins
2.6 Dimension d’un espace métrique et problèmes liés
2.6.1 Dimension intrinsèque
2.6.2 Quelques propriétés des espaces multidimensionnels
2.6.3 Malédiction de la dimension
3 Techniques d’indexation multidimensionnelles
3.1 Partitionnement des données
3.1.1 Arbre-R
3.1.2 Arbre-SR
3.1.3 Arbre-X
3.2 Partitionnement de l’espace
34 TABLE DES MATIÈRES
3.2.1 Arbre-kD
4 Techniques d’indexation métriques
4.1 Non-partitionnement de l’espace
4.1.1 Arbre-M
4.1.2 Arbre-slim
4.2 Partitionnement de l’espace
4.2.1 Arbre-VP
4.2.2 Arbre-GH
4.2.3 Arbre-MM
4.2.4 Arbre-oignon
5 Synthèse sur l’état de l’art 89
5.1 Introduction
5.2 Comparatif des méthodes multidimensionnelles
5.3 Comparatif des méthodes métriques
5.4 Analyses
II Proposition
6 Arbre-IM
6.1 Idées préliminaires
6.2 Formalisation
6.2.1 Définition
6.2.2 Choix de α
6.2.3 Choix des pivots
6.3 Construction de l’index
6.3.1 Construction en lot
6.3.2 Construction incrémentale
6.4 Requêtes de similarité
6.5 Conclusion
7 Expérimentations et résultats : approche séquentielle
7.1 Collections indexées et requêtes
7.2 Mesures relatives à la structure d’index
7.2.1 Expérimentations
7.2.2 Comparaison avec des techniques récentes
7.3 Performances des recherches kNN
7.3.1 Protocole des expérimentations
7.3.2 Résultats et analyse des expérimentations
7.4 Comparaison avec des techniques récentes
7.4.1 Protocole des expérimentations
7.5 Conclusion
8 Parallélisation de l’arbre-IM
8.1 Introduction
8.1.1 Objectif de la version parallèle
8.2 Algorithme parallèle pour une recherche kNN
8.2.1 Recherche kNN parallèle dans un arbre-IM
8.2.2 Complexité parallèle
8.2.3 Estimation du rayon de requête initial
8.3 Conclusion
9 Expérimentations et résultats : approche parallèle
9.1 Protocole des expérimentations
9.2 Résultats et analyse des expérimentations
9.2.1 Effet de l’algorithme d’estimation du rayon de requête
9.3 Comparaison avec des techniques récentes
9.3.1 Protocole des expérimentations
10 Conclusion et perspectives
Bibliographie
Télécharger le rapport complet
