SciPy (prononcé sai pie) est un ensemble de procédures mathématiques appliquées basées sur l'extension Numpy Python. Il étend considérablement les capacités de Python en fournissant à l'utilisateur des commandes et des classes de haut niveau pour la gestion et la visualisation des données. Avec SciPy, une session Python interactive se transforme en le même environnement complet de traitement de données et de prototypage pour des systèmes complexes comme MATLAB, IDL, Octave, R-Lab et SciLab.
Présentation
Il est recommandé d'installer le package SciPy dans le cadre d'Anaconda. Une connaissance des bases de Python et une documentation Numpy à portée de main sont également recommandées. Pour des raisons de concision et de commodité, nous convenons que les principaux packages (numpy, scipy et matplotlib) seront importés comme suit:
import numpy as np import matplotlib as mpl import matplotlib.pyplot as plt
Il s'agit de l'accord d'importation officiel utilisé dans le code source NumPy, SciPy et dans la documentation. La conformité à ces conventions dans votre code est facultative, mais fortement recommandée. Il est conseillé d'importer chacun des packages séparément comme suit:
from scipy import linalg, optimize
SciPy et NumPy ont des versions complètes de la documentation qui couvrent presque toutes leurs fonctions. Ils sont disponibles sur https://docs.scipy.org/ au format HTML et PDF. Certaines parties peuvent être incomplètes ou obsolètes, la documentation est en constante évolution. Puisque SciPy est une organisation bénévole et dépend de la communauté, votre participation, de la rétroaction à l'amélioration de la documentation et du code, est la bienvenue et activement encouragée.
Algorithmes de graphe clairsemé (scipy.csgraph)
Lewis Carroll, Joyeux Noël 1877
Considérez l'utilisation du paquet scipy.csgraph comme exemple du jeu pour enfants " Ladders of Words " inventé par Lewis Carroll le jour de Noël 1877. Dans ce jeu, vous devez trouver le chemin entre les mots, en remplaçant une lettre à la fois. Par exemple, vous pouvez tracer le chemin d'un singe à une personne en connectant les mots «singe» et «homme» comme suit:
Veuillez noter que chaque étape implique de changer une seule lettre du mot. Ce n'est qu'un chemin possible d'un singe à un homme, mais est-ce le chemin le plus court? Ainsi, il est nécessaire de trouver le chemin le plus court (échelle) entre deux mots donnés. Ce problème peut être résolu à l'aide du package scipy.sparse.csgraph.
Nous avons d'abord besoin d'une liste de mots valides. De nombreux systèmes d'exploitation ont une telle liste intégrée. Par exemple, sous Linux, une liste de mots peut être trouvée dans l'un des endroits suivants:
/usr/share/dict /var/lib/dict
Une autre source de mots est les dictionnaires disponibles sur différents sites sur Internet (regardez dans votre moteur de recherche préféré). La liste de mots système est un fichier avec un mot par ligne. Pour utiliser la liste de mots système, vous devez la lire comme suit:
word_list = open('/usr/share/dict/words').readlines() word_list = map(str.strip, word_list)
Parce que nous recherchons des mots de trois lettres, puis nous ne sélectionnerons que les mots nécessaires dans la liste générale. Nous excluons également les mots commençant par des majuscules (noms propres) ou contenant des caractères non alphabétiques, tels que des apostrophes et des tirets. À la fin, vérifiez la taille de la liste de mots résultante.
word_list = [word for word in word_list if len(word) == 3] word_list = [word for word in word_list if word[0].islower()] word_list = [word for word in word_list if word.isalpha()] word_list = list (map (str.lower, word_list)) len (word_list)
591
Nous avons maintenant une liste de 591 mots de trois lettres (le nombre exact peut varier selon le dictionnaire particulier utilisé). Chacun de ces mots est en haut du graphique. Créez des arêtes reliant les sommets (paires de mots) qui diffèrent par une seule lettre.
Nous utilisons un moyen assez efficace, qui nécessitera une certaine manipulation du tableau numpy:
word_list = np.asarray(word_list) word_list.sort()
dtype('<U3')
Nous avons maintenant un tableau dans lequel chaque entrée contient trois caractères Unicode. Nous aimerions trouver toutes les paires qui ont exactement un caractère. Commençons par convertir chaque mot en un vecteur tridimensionnel:
word_bytes = np.ndarray((word_list.size, word_list.itemsize), dtype='uint8', buffer=word_list.data)
(591, 3)
Nous rappelons que la distance de Hamming est le nombre de caractères différents dans deux vecteurs de même longueur. En utilisant la distance de Hamming, nous déterminons la longueur des bords reliant les paires de mots. Tous les deux mots sont connectés à l'échelle des mots avec une distance égale à où - nombre de lettres dans un mot:
from scipy.spatial.distance import pdist, squareform from scipy.sparse import csr_matrix hamming_dist = pdist (word_bytes, metric = 'hamming') graph = csr_matrix (squareform (hamming_dist < 1.5 / 3))
Lors de la comparaison des distances, une égalité non stricte est utilisée, car sinon le résultat peut être instable pour les valeurs à virgule flottante. L'inégalité donne le résultat souhaité si les deux caractères du mot ne correspondent pas. Maintenant que le graphique est donné, nous allons effectuer la recherche de chemin le plus court entre deux mots quelconques du graphique:
i1 = word_list.searchsorted ('ape') i2 = word_list.searchsorted ('man')
Vous devez maintenant trouver le chemin le plus court entre ces deux sommets sur le graphique. Pour ce faire, nous utilisons l'algorithme de Dijkstra, qui vous permet de trouver toutes les distances possibles pour le sommet spécifié:
from scipy.sparse.csgraph import dijkstra distances, predecessors = dijkstra(graph, indices=i1, return_predecessors=True) print(distances[i2])
5.0
Ainsi, nous voyons que le chemin le plus court entre un singe et un homme ne contient que cinq étapes. Nous pouvons utiliser les prédécesseurs renvoyés par l'algorithme pour restaurer ce chemin:
path = [] i = i2 while i != i1: path.append(word_list[i]) i = predecessors[i] path.append(word_list[i1]) print(path[::-1])
['ape', 'apt', 'opt', 'oat', 'mat', 'man']
La longueur de l'escalier est de trois marches de moins que dans l'exemple initial. En utilisant d'autres outils du module, vous pouvez trouver la réponse à d'autres questions. Par exemple, y a-t-il des mots avec trois lettres qui ne sont pas connectés dans l'escalier des mots? C'est la tâche de déterminer la connectivité d'un graphe:
from scipy.sparse.csgraph import connected_components N_components, component_list = connected_components(graph) print(N_components)
15
Dans notre exemple, pour les mots de trois lettres, il y a 15 composants liés: c'est-à-dire 15 ensembles différents de mots sans aucun chemin entre eux. Combien de mots y a-t-il dans chacun de ces ensembles? Nous pouvons découvrir à partir de la liste des composants:
[np.sum(component_list == i) for i in range(N_components)]
[577, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Nous avons obtenu un grand graphique, qui comprend 577 sommets, ainsi que 14 graphiques isolés. Regardons ces mots:
[list(word_list[np.where(component_list == i)]) for i in range(1, N_components)]
[['aha'], ['chi'], ['ebb'], ['gnu'], ['ism'], ['khz'], ['nth'], ['née'], ['ova'], ['qua'], ['ugh'], ['ups'], ['urn'], ['use']]
Vous pouvez savoir entre quels mots il y a une échelle de longueur maximale. Cela peut être déterminé en calculant la matrice d'adjacence. Notez que la distance entre deux points non connectés est considérée comme infinie, ils doivent donc être exclus:
distances, predecessors = dijkstra(graph, return_predecessors=True) max_distance = np.max(distances[~np.isinf(distances)]) print(max_distance)
13.0
Donc, dans notre exemple, il y a de telles paires de mots, entre lesquelles l'escalier le plus court contient 13 marches! Déterminons quelles sont ces paires:
i1, i2 = np.where(distances == max_distance) list(zip(word_list[i1], word_list[i2]))
[('imp', 'ohm'), ('imp', 'ohs'), ('ohm', 'imp'), ('ohm', 'ump'), ('ohs', 'imp'), ('ohs', 'ump'), ('ump', 'ohm'), ('ump', 'ohs')]
Nous avons vu toutes les combinaisons possibles de paires de mots, dont la distance est de 13 (au maximum séparées les unes des autres). Si vous regardez attentivement, d'un côté de l'escalier se trouvent les mots "imp" et "ump", qui diffèrent l'un de l'autre par une seule lettre. De l'autre côté de l'escalier se trouvent les mots «ohm» et «ohs», qui se distinguent également par une seule lettre. La liste des étapes entre ces mots sera presque la même. Il peut être trouvé de la même manière qu'indiqué ci-dessus:
path = [] i = i2[0] while i != i1[0]: path.append(word_list[i]) i = predecessors[i1[0], i] path.append(word_list[i1[0]]) print(path[::-1])
['imp', 'amp', 'asp', 'ass', 'ads', 'ids', 'ins', 'inn', 'ion', 'won', 'woo', 'who', 'oho', 'ohm']
Les escaliers de mots ne sont qu'une des utilisations possibles des algorithmes rapides sur les graphiques clairsemés dans scipy. La théorie des graphes est utilisée dans de nombreux domaines des mathématiques, de l'analyse de données et de l'apprentissage automatique. Les outils graphiques clairsemés sont suffisamment flexibles pour gérer un large éventail de tâches.
Je serai heureux si vous écrivez dans les commentaires quelle section de scipy sera intéressante à lire dans le prochain article.