Tuto Python-SciPy : le sous-module Spatial
Table des matières
Introduction :
Bonjour ! Bienvenue dans un nouveau tutoriel Python. Aujourd’hui, nous allons voir le sous-module spatial du module Scipy. Il contient des fonctionnalités très intéressantes et utiles pour les algorithmes spatiaux et les structures de données. Nous allons voir l’intérêt de ces fonctionnalités et comment les utiliser dans des exemples.
À la fin de ce tutoriel, vous aurez tous les outils du module spatial entre les mains et il suffira de les déployer dans vos propres exemples.
Aucun prérequis n’est nécessaire pour suivre ce cours. Il suffit de bien suivre les instructions et le tour est joué ! Commençons alors .
Le Module Scipy en général :
Scipy est l’un des modules numériques de base de Python. C’est une librairie open-source utilisée dans les mathématiques, l’informatique scientifique, l’ingénierie et l’informatique technique.
Il offre plusieurs fonctionnalités représentées par des sous-modules. Voici quelques-uns parmi les plus pertinentes :
- Cluster: Algorithmes de clustering .
- Constants: Constantes physiques et mathématiques .
- Integrate: Solveurs d’intégration et d’équation différentielle ordinaire.
- Signal: Traitement de signal.
- Sparse: Matrices et routines associés .
- Spatial : Structures et algorithmes de données spatiales .
- Ndimage: Traitement d’image N dimension .
- Optimize: optimisation des algorithmes.
- Special: fonctions spéciales .
Cependant, aujourd’hui, nous allons seulement nous intéresser au module spatial de Scipy.
Spatial, le sous-module :
Scipy.spatial est un sous-module du module Scipy, Il est utilisé pour les problèmes tel que les triangulations, les diagrammes voronoi et les représentations convexes d’un ensemble de points.
De plus, il contient des implémentations KDTree pour les requêtes de point voisin le plus proche, et des utilitaires pour les calculs de distance dans diverses métriques.
Parmi Les fonctions de base du module spatial on trouve tsearch() et distance_matrix() .
Nous allons voir chacune de ces fonctionnalités en détail dans les sections suivantes .
Triangulations Delaunay :
En mathématiques, Une triangulation d’un polygone est de diviser le polygone en plusieurs triangles avec lesquels nous pouvons calculer une zone du polygone.
Une triangulation Delaunay d’un ensemble de Points P est une triangulation DT(P) de telle manière qu’aucun point de l’ensemble P n’est à l’intérieur d’un des sous-cercles des triangles DT.
En Python, c’est la classe suivante qui nous permet de réaliser cet algorithme :
class scipy.spatial.Delaunay(points , further_site=False,incremental=False,qhull_options=None)
Avec:
- points: Cordonnées des points à trianguler
- further_site: Calcul de la triangulation Delaunay la plus éloignée du site. Valeur par défaut : Faux .
- Incremental: permet d’ajouter de nouveaux points par incrément.
- qhull_options: option additionnelle qu’on ne verra pas dans ce tutoriel.
Voici un exemple pour vous montrer de quoi il s’agit !
Remarque : Notez que nous allons utiliser d’autre libraire tel que numpy pour créer un ensemble de points ou matplotlib.pyplot pour afficher les résultats :
Exemple :
Voici un ensemble d’une triangulation Delaunay d’un ensemble de points.
Syntaxe :
from scipy.spatial import Delaunay
ensemble_points = np.array ([[1, 1], [1, 2.1], [2, 1], [2, 2]])
res = Delaunay (ensemble_points)
#Visualisation
import matplotlib.pyplot as plt
plt.triplot(ensemble_points[:,0], ensemble_points[:,1], res.simplices)
plt.plot (ensemble_points[:,0], ensemble_points[:,1], 'o')
Résultat de l’exécution :
La propriété Simplices crée une généralisation de la notation triangulation. Pour récupérer les indices de points qui forment les triangles de la triangulation, on procède comme suivant :
Syntaxe :
tri.simplices
Résultat de l’exécution :
L’exécution retourne les indices des points qui forment les deux triangles :
- Le premier triangle est formé par les points 2, 3 et 0.
- Le deuxième triangle est formé par les points 3, 1 et 0 .
Maintenant si on veut les coordonnées de ces triangles, on écrit la commande suivante :
Syntaxe :
ensemble_points[res.simplices]
Résultat :
Le résultat retourne les coordonnés des deux triangles de la triangulation Delaunay, effectivement si vous regardez le dessin voici les deux triangles avec les coordonnés du résultat de l’exécution :
Exemple :
Voici un deuxième exemple de la triangulation Delaunay
Syntaxe :
import numpy as np
import sys
from scipy.spatial import Delaunay
import matplotlib.pyplot as plt
ensemble_points = np.array([
[3, 5],
[4, 6],
[4, 1],
[3, 3],
[5, 2]
])
simpl = Delaunay (ensemble_points).simplices
plt.triplot (ensemble_points [:, 0], ensemble_points[:, 1], simpl)
plt.scatter (ensemble_points [:, 0], ensemble_points[:, 1], color='r')
plt.show()
Résultat de l’exécution :
Comme ce qu’on a fait dans l’exemple précèdent, on peut afficher les indices des points qui constituent les triangles ainsi que leurs coordonnées :
Syntaxe :
simpl
points [simpl]
Résultat de l’exécution :
Le premier triangle est composé des points 4, 1 et 0. Donc, les cordonnées de ce triangle sont :
Point4(5,2) , Point1(4,6) et le Point0(3,5) .
Le deuxième triangle quant à lui est composé des points 3, 4 et 0 du simplexe . Les coordonnées de ce triangle sont : Point3(3,3) , Point4(5,2) et Point0(3,5) .
Finalement, le dernier triangle composé des points 3 ,2 et 4 dont les coordonnées sont : Point3(3,3), Point2(4,1) et Point4(5,2) .
Nous allons à présent passer à une nouvelle fonctionnalité du sous-module spatial.
Fonction distance_matrix() :
Cette fonction permet de calculer la distance matricielle :
Exemple :
Syntaxe :
from scipy.spatial import distance_matrix
distance_matrix([[2,0],[1,0]], [[0,0],[0,1]])
Résultat de l’éxécution :
Fonction tsearch() :
Cette fonction permet de trouver les simplexes contenant certains points donnés.
Exemple : Triangulation Delaunay
On veut retrouver les simplexes contenant certains points aléatoires d’une triangulation Delaunay d’un ensemble de points .
Syntaxe :
from scipy.spatial import Delaunay, delaunay_plot_2d, tsearch
import numpy as np
import matplotlib.pyplot as plt
#Triangulation delaunay d'un ensemble de points aléatoires
points = np.random.rand(15, 2)
delaunay_points = Delaunay(points)
_ = delaunay_plot_2d(delaunay_points)
#Trouver les simplexes des points donnés :
loc = np.random.uniform(0.2, 0.8, (5, 2))
s = tsearch(delaunay_points, loc)
plt.triplot(points[:, 0], points[:, 1], delaunay_points.simplices[s], 'b-', mask=s==-1)
plt.scatter(loc[:, 0], loc[:, 1], c='r', marker='x')
plt.show ()
Résultat de l’éxécution :
Nous obtenons comme résultat les simplexes qui contiennent les 5 points aléatoires .
Exemple :
Similaire que le premier mais avec un nombre de points aléatoires plus grand.
Syntaxe :
from scipy.spatial import Delaunay, delaunay_plot_2d, tsearch
import numpy as np
import matplotlib.pyplot as plt
#Triangulation delaunay d'un ensemble de points aléatoires
points = np.random.rand(15, 2)
delaunay_points = Delaunay(points)
_ = delaunay_plot_2d(delaunay_points)
#Find the simplices containing a given set of points:
loc = np.random.uniform(0.2, 0.8, (10, 2))
s = tsearch(delaunay_points, loc)
plt.triplot(points[:, 0], points[:, 1], delaunay_points.simplices[s], 'b-', mask=s==-1)
plt.scatter(loc[:, 0], loc[:, 1], c='r', marker='x')
plt.show()
Résultat de l’exécution :
Convexe hulls:
Une Enveloppe convexe est le plus petit polygone qui couvre tous les points donnés. Il peut être calculé via les enveloppes Qhull dans scipy.spatial comme suit :
class scipy.spatial.ConvexHull(points, incremental=False, qhull_options=None)
- points : Coordonnées des points pour construire une coque convexe.
- Incremental : Permet d’ajouter de nouveaux points par incréments.
- Qhull_options : Options supplémentaires pour passer à Qhull.
Exemple :
Voici un exemple qui crée une enveloppe convexe pour un ensemble donné de points.
Syntaxe :
import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt
ensemble_points = np.array([
[4, 2],
[3, 4],
[3, 1],
[3, 2],
[4, 1],
[1, 2],
[5, 2],
[3, 1],
[0, 2],
[0, 1]
])
hull = ConvexHull(ensemble_points)
hull_points = hull.simplices
plt.scatter(ensemble_points[:,0], ensemble_points[:,1])
for simplex in hull_points:
plt.plot(ensemble_points[simplex,0], ensemble_points[simplex,1], 'k-')
plt.show()
Résultat de l’exécution :
Exemple :
Dans cet exemple, on veut créer une enveloppe convexe de 25 points aléatoires.
Syntaxe :
from scipy.spatial import ConvexHull
ensemble_points = np.random.rand(30, 2) # 25 points aléatoires en 2-D
points_hulls = ConvexHull (ensemble_points)
import matplotlib.pyplot as plt
plt.plot (ensemble_points [:,0], ensemble_points [:,1], 'o')
for simplex in points_hull.simplices:
plt.plot (ensemble_points [simplex,0], ensemble_points [simplex,1], 'k-')
plt.show()
Résultat de l’exécution :
Requêtes Nearest-neighbor:
KDTree :
Cette classe fournit un index dans un ensemble de points k-D qui peut être utilisé pour rechercher rapidement les voisins les plus proches de n’importe quel point.
class scipy.spatial.KDTree(data, leafsize=10)
Exemple :
Dans cet exemple, nous voulons voir le voisin le plus proche du point (0,1) .
Syntaxe :
from scipy.spatial import KDTree
ensemble_points = [(0, -1), (2, 1), (-1, 2), (2, -3)]
kdtree = KDTree(points)
resultat = kdtree.query((0, 1))
print(resultat)
Résultat de l’exécution :
Diagrammes Voronoi :
Un diagramme Voronoi est une subdivision de l’espace en cellules dans les quartiers les plus proches d’un ensemble donné de points discrets.
Exemple :
Syntaxe :
ensemble_points = np.array([[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3],
[3, 1], [3, 1], [3, 2]])
from scipy.spatial import Voronoi, voronoi_plot_2d
voronoi = Voronoi (ensemble_points)
import matplotlib.pyplot as plt
fig = voronoi_plot_2d(voronoi)
plt.show()
Résultat de l’exécution :
Les sommets du diagramme Voronoi peuvent être calculés grâce à la requête suivante :
Vornoi.vertices
Résultat de l’exécution :
Matrice Distance :
Il existe de nombreux indicateurs de distance utilisés pour trouver différents types de distances entre deux points dans la science des données, distance euclidienne, distance cosinus, etc .
La distance entre deux vecteurs peut être non seulement la longueur de la ligne droite entre eux, mais aussi l’angle entre eux à partir de l’origine, ou le nombre d’étapes unitaires nécessaires, etc.
Il faut dire que la performance de l’algorithme de Machine Learning dépend beaucoup des mesures de distance. P.ex. "K voisins les plus proches", ou "K moyens" etc .
Examinons quelques-unes des mesures de distance :
Euclidian distance :
Permet de trouver la distance euclidienne entre des points.
Exemple :
Voici un exemple de calcul de la distance euclidienne entre deux points .
Syntaxe :
from scipy.spatial.distance import euclidean
point_1 = (10, 0)
point_2 = (1, 2)
dis = euclidean (point_1, point_2)
print(dis)
Résultat de l’exécution :
Exemple :
Un autre exemple de calcul de la distance euclidienne.
Syntaxe :
from scipy.spatial.distance import euclidean
point_1 = (10, 0,9)
point_2 = (1, 2,6)
point_3=(2,4,5)
dis = euclidean (point_1, point_2,point_3)
print (dis)
Résultat de l’exécution :
Manhattan distance :
C’est la distance calculée en utilisant les 4 degrés de liberté : en haut, en bas, à droite et à gauche mais pas diagonalement.
Exemple :
La distance de Manhattan ou ce qu’on appelle aussi distance Cityblock est calculée par la fonction cityblock() .
Syntaxe :
from scipy.spatial.distance import cityblock
point_1 = (10, 0)
point_2 = (1, 2)
resultat = cityblock(point_1, point_2)
print(resultat)
Résultat de l’exécution :
Exemple :
Voici un deuxième exemple de calcul de la distance Manhattan entre trois points.
Syntaxe :
from scipy.spatial.distance import cityblock
point_1 = (10, 0)
point_2 = (1, 2)
point_3=(1,0)
resultat = cityblock (point_1, point_2,point_3)
print (resultat)
Résultat de l’éxécution :
Distance Cosine :
Retourne la valeur de l’angle cosine entre deux points A et B.
Exemple :
Syntaxe :
from scipy.spatial.distance import cosine
point_1 = (1, 0)
point_2 = (10, 2)
resultat = cosine(point_1, point_2)
print(resultat)
Résultat de l’éxécution :
Distance Hamming :
C’est la proportion de bits où deux bits sont la différence. C’est une façon de mesurer la distance pour les séquences binaires.
Exemple :
from scipy.spatial.distance import hamming
hamming([0, 1, 0], [0, 0, 1])
Résultat de l’éxécution :
Exemple :
Voici un exemple avec les booléens True et False .
Syntaxe :
from scipy.spatial.distance import hamming
point_1 = (True, False, True)
point_2 = (True, True, True)
res = hamming(p1, p2)
print(res)
Résultat de l’éxécution :
Conclusion :
Nous sommes arrivés à la fin de ce tutoriel, maintenant vous connaissez plusieurs fonctionnalités du sous-module Spatial. C’est un modèle très riche en méthodes de transformations spatiales et qui vous sera d’une très grande utilité dans la géométrie spatiale.
Voila ! Vous avez presque tous les outils du module spatial, il suffit de vous entrainer sur les exemples et coder vos propres programmes .
Ce module n’est qu’un seule sous-module de Scipy et regardez sa richesse ! Nous vous invitions donc à découvrir les autres modules qui restent . La route est encore longue mais vous y arriverez certainement ! Bon courage et à un prochain tutoriel chers lecteurs !
Article publié le 27 Octobre 2020par Mouna HAMIM