date dernière version : juillet 2012
A partir de la carte, identifions les coordonnées des points représentant les villes :
1) représentation par un 2-d tree :
2) réprésentation par un Quad-tree
3) représentation par un MX-Quad-tree
4) représentation par un R-tree . On choisira un arbre d'ordre 3
Cette représentation n'est pas unique. On notera que chaque noeud intermédiaire satisfait la propriété n ≥ k
Calculons les moyennes (facile avec un tableur) . On obtient les segments suivants (mis en couleur pour mieux les distinguer) :
O nobtient donc 23 segments.
Prennons la convention NO = 0, NE = 1, SE = 2, SO = 3
Le codage est : 002X, 013X, 020X, 022X, 023X, 031X, 032X, 102X, 113X, 120X, 123X, 131X, 132X, 133X, 200X, 201X, 202X, 210X, 213X, 220X, 231X, 301X, 302X, 310X, 311X, 313X, 320X, 331X.
En appliquant la distance euclidienne, on obtient d(0, 1) = 2, d(0,2) = 2,83, d(0,3) = 1, d(0,4) = 2. L'image 3 est donc la plus proche de l'image 0.
1) On normalise les colonnes du tableau ce qui conduit à la matrice F :
2) Pour obtenir les similarités entre documents on effectue le produit matriciel FTF :
On constate que la meilleure similarité est obtenue pour les documents D1 et D3.
3) LSI et décomposition. On utilise le logiciel Scilab qui permet de trouver les matrices de la décomposition :
On peut négliger la dernière valeur diagonale de la matrice S, soit
F* constitue une bonne approximation de F. Pour vérifier le résultat de la question précédente, on calcule la matrice D = (V*S*)T et on effectue le produit DTD :
On retrouve bien le rsultat précédent.
4) La requête est traduite en un vecteur normalisé. Puis on recherche la similarité avec les documents Di :
Le document le mieux positionné par rapport à a requête est le document D5.