SciPy (pronunciado sai pie) es un paquete de aplicación matemática basado en la extensión Numpy Python. Amplía enormemente las capacidades de Python al proporcionar al usuario comandos y clases de alto nivel para administrar y visualizar datos. Con SciPy, una sesión interactiva de Python se convierte en el mismo entorno completo de procesamiento de datos y creación de prototipos para sistemas complejos como MATLAB, IDL, Octave, R-Lab y SciLab.
Introduccion
Se recomienda instalar el paquete SciPy como parte de Anaconda. También es recomendable familiarizarse con los conceptos básicos de Python y tener a mano la documentación de Numpy. Por brevedad y mayor comodidad, acordamos que los paquetes principales (numpy, scipy y matplotlib) se importarán de la siguiente manera:
import numpy as np import matplotlib as mpl import matplotlib.pyplot as plt
Este es el acuerdo de importación oficial utilizado en el código fuente de NumPy, SciPy y en la documentación. El cumplimiento de estas convenciones en su código es opcional, pero muy recomendable. Es recomendable importar cada uno de los paquetes por separado de la siguiente manera:
from scipy import linalg, optimize
SciPy y NumPy tienen versiones completas de la documentación que cubren casi todas sus funciones. Están disponibles en https://docs.scipy.org/ en formato HTML y PDF. Algunas partes pueden estar incompletas o desactualizadas, como La documentación está en constante desarrollo. Dado que SciPy es una organización de voluntarios y depende de la comunidad, su participación al proporcionar comentarios para mejorar la documentación y el código es bienvenida y se fomenta activamente.
Algoritmos de gráficos dispersos (scipy.csgraph)
Lewis Carroll, Feliz Navidad 1877
Considere el uso del paquete scipy.csgraph como un ejemplo del juego infantil " Escaleras de palabras " inventado por Lewis Carroll el día de Navidad de 1877. En este juego, necesitas encontrar el camino entre las palabras, reemplazando una letra a la vez. Por ejemplo, puede rastrear el camino de un mono a una persona conectando las palabras "mono" y "hombre" de la siguiente manera:
Tenga en cuenta que cada paso implica cambiar solo una letra de la palabra. Este es solo un camino posible de un mono a un hombre, pero ¿es este el camino más corto? Por lo tanto, es necesario encontrar el camino más corto (escalera) entre dos palabras dadas. Este problema se puede resolver utilizando el paquete scipy.sparse.csgraph.
Primero necesitamos una lista de palabras válidas. Muchos sistemas operativos tienen dicha lista incorporada. Por ejemplo, en Linux, se puede encontrar una lista de palabras en uno de los siguientes lugares:
/usr/share/dict /var/lib/dict
Otra fuente de palabras son los diccionarios disponibles en varios sitios en Internet (busque en su motor de búsqueda favorito). La lista de palabras del sistema es un archivo con una palabra por línea. Para usar la lista de palabras del sistema, debe leerla de la siguiente manera:
word_list = open('/usr/share/dict/words').readlines() word_list = map(str.strip, word_list)
Porque buscamos palabras de tres letras, luego seleccionaremos solo las palabras necesarias de la lista general. También excluya palabras que comienzan con mayúsculas (sustantivos propios) o que contienen caracteres no alfabéticos como los apóstrofes y guiones. Al final, verifique el tamaño de la lista de palabras resultante.
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
Ahora tenemos una lista de 591 palabras de tres letras (el número exacto puede variar según el diccionario particular utilizado). Cada una de estas palabras es la parte superior del gráfico. Cree aristas que conecten los vértices (pares de palabras) que difieran solo en una letra.
Utilizamos una forma bastante eficiente, que requerirá alguna manipulación de la matriz numpy:
word_list = np.asarray(word_list) word_list.sort()
dtype('<U3')
Ahora tenemos una matriz en la que cada entrada contiene tres caracteres Unicode. Nos gustaría encontrar todos los pares que tengan exactamente un carácter. Comencemos convirtiendo cada palabra en un vector tridimensional:
word_bytes = np.ndarray((word_list.size, word_list.itemsize), dtype='uint8', buffer=word_list.data)
(591, 3)
Recordamos que la distancia de Hamming es el número de caracteres diferentes en dos vectores de la misma longitud. Usando la distancia de Hamming, determinamos la longitud de los bordes que conectan los pares de palabras. Cada dos palabras están conectadas a la escala de palabras con una distancia igual a donde - número de letras en una palabra:
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))
Al comparar distancias, se utiliza la igualdad no estricta, porque de lo contrario el resultado puede ser inestable para los valores de coma flotante. La desigualdad da el resultado deseado si los dos caracteres de la palabra no coinciden. Ahora que se proporciona el gráfico, realizaremos la búsqueda de la ruta más corta entre dos palabras en el gráfico:
i1 = word_list.searchsorted ('ape') i2 = word_list.searchsorted ('man')
Ahora necesita encontrar el camino más corto entre estos dos vértices en el gráfico. Para hacer esto, utilizamos el algoritmo Dijkstra, que le permite encontrar todas las distancias posibles para el vértice especificado:
from scipy.sparse.csgraph import dijkstra distances, predecessors = dijkstra(graph, indices=i1, return_predecessors=True) print(distances[i2])
5.0
Entonces, vemos que el camino más corto entre un mono y un hombre contiene solo cinco pasos. Podemos usar los predecesores devueltos por el algoritmo para restaurar esta ruta:
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 longitud de las escaleras es tres pasos menos que en el ejemplo inicial. Usando otras herramientas del módulo, puede encontrar la respuesta a otras preguntas. Por ejemplo, ¿hay palabras con tres letras que no están conectadas en la escalera de palabras? Esta es la tarea de determinar la conectividad de un gráfico:
from scipy.sparse.csgraph import connected_components N_components, component_list = connected_components(graph) print(N_components)
15
En nuestro ejemplo, para palabras de tres letras, hay 15 componentes relacionados: es decir, 15 conjuntos diferentes de palabras sin caminos entre ellas. ¿Cuántas palabras hay en cada uno de estos conjuntos? Podemos averiguarlo en la lista de componentes:
[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]
Tenemos un gráfico grande, que incluye 577 vértices, así como 14 gráficos aislados. Veamos estas palabras:
[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']]
Puede averiguar entre qué palabras hay una escalera de longitud máxima. Esto se puede determinar calculando la matriz de adyacencia. Tenga en cuenta que la distancia entre dos puntos no conectados se considera infinita, por lo tanto, deben excluirse:
distances, predecessors = dijkstra(graph, return_predecessors=True) max_distance = np.max(distances[~np.isinf(distances)]) print(max_distance)
13.0
Entonces, en nuestro ejemplo, hay tales pares de palabras, ¡entre las cuales la escalera más corta contiene 13 escalones! Vamos a determinar cuáles son estos pares:
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')]
Vimos todas las combinaciones posibles de pares de palabras, la distancia entre las cuales es 13 (máximamente separadas entre sí). Si observa detenidamente, a un lado de las escaleras están las palabras "imp" y "ump", que difieren entre sí con solo una letra. En el otro lado de las escaleras están las palabras "ohm" y "ohs", que también se distinguen por una sola letra. La lista de pasos entre estas palabras será casi la misma. Se puede encontrar de la misma manera que se indicó anteriormente:
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']
Las escaleras de palabras son solo uno de los posibles usos de algoritmos rápidos en gráficos dispersos en scipy. La teoría de gráficos se usa en muchas áreas de las matemáticas, el análisis de datos y el aprendizaje automático. Las herramientas de gráficos dispersos de Scipy son lo suficientemente flexibles como para manejar una amplia gama de tareas.
Me alegrará si escribe en los comentarios qué sección de scipy será interesante de leer en el próximo artículo.