SciPy (pronuncia-se sai pie) é um pacote de aplicativos matemáticos baseado na extensão Numpy Python. Ele expande enormemente os recursos do Python, fornecendo ao usuário comandos e classes de alto nível para gerenciar e visualizar dados. Com o SciPy, uma sessão interativa em Python se transforma no mesmo ambiente completo de processamento e prototipagem de dados para sistemas complexos como MATLAB, IDL, Octave, R-Lab e SciLab.
1. Introdução
Recomenda-se que o pacote SciPy seja instalado como parte do Anaconda. Também é recomendável familiarizar-se com o básico do Python e ter a documentação do Numpy em mãos. Para maior brevidade e conveniência, concordamos que os principais pacotes (numpy, scipy e matplotlib) serão importados da seguinte maneira:
import numpy as np import matplotlib as mpl import matplotlib.pyplot as plt
Este é o contrato oficial de importação usado no código-fonte NumPy, SciPy e na documentação. A conformidade com essas convenções no seu código é opcional, mas altamente recomendada. É recomendável importar cada um dos pacotes separadamente, da seguinte maneira:
from scipy import linalg, optimize
SciPy e NumPy têm versões completas da documentação que cobrem quase todas as suas funções. Eles estão disponíveis em https://docs.scipy.org/ nos formatos HTML e PDF. Algumas partes podem estar incompletas ou desatualizadas, como a documentação está constantemente em desenvolvimento. Como o SciPy é uma organização voluntária e depende da comunidade, sua participação, desde o feedback até a melhoria da documentação e do código, é bem-vinda e ativamente encorajada.
Algoritmos de gráficos esparsos (scipy.csgraph)
Lewis Carroll, Feliz Natal 1877
Considere o uso do pacote scipy.csgraph como um exemplo do jogo infantil " Ladders of Words " inventado por Lewis Carroll no dia de Natal de 1877. Neste jogo, você precisa encontrar o caminho entre as palavras, substituindo uma letra de cada vez. Por exemplo, você pode rastrear o caminho de um macaco para uma pessoa conectando as palavras "macaco" e "homem" da seguinte maneira:
Observe que cada etapa envolve alterar apenas uma letra da palavra. Este é apenas um caminho possível de um macaco para um homem, mas este é o caminho mais curto? Assim, é necessário encontrar o caminho mais curto (escada) entre duas palavras dadas. Esse problema pode ser resolvido usando o pacote scipy.sparse.csgraph.
Primeiro, precisamos de uma lista de palavras válidas. Muitos sistemas operacionais possuem uma lista embutida. Por exemplo, no linux, uma lista de palavras pode ser encontrada em um dos seguintes locais:
/usr/share/dict /var/lib/dict
Outra fonte de palavras são os dicionários disponíveis em vários sites da Internet (procure no seu mecanismo de pesquisa favorito). A lista de palavras do sistema é um arquivo com uma palavra por linha. Para usar a lista de palavras do sistema, você precisa lê-lo da seguinte maneira:
word_list = open('/usr/share/dict/words').readlines() word_list = map(str.strip, word_list)
Porque estamos procurando palavras com três letras e, em seguida, selecionaremos apenas as palavras necessárias na lista geral. Exclua também as palavras que começam com maiúsculas (nomes próprios) ou contêm caracteres não alfabéticos, como apóstrofos e hífens. No final, verifique o tamanho da lista de palavras 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
Agora, temos uma lista de 591 palavras de três letras (o número exato pode variar dependendo do dicionário específico usado). Cada uma dessas palavras está no topo do gráfico. Crie arestas conectando os vértices (pares de palavras) que diferem em apenas uma letra.
Usamos uma maneira bastante eficiente, que exigirá alguma manipulação da matriz numpy:
word_list = np.asarray(word_list) word_list.sort()
dtype('<U3')
Agora, temos uma matriz na qual cada entrada contém três caracteres Unicode. Gostaríamos de encontrar todos os pares que tenham exatamente um caractere. Vamos começar convertendo cada palavra em um vetor tridimensional:
word_bytes = np.ndarray((word_list.size, word_list.itemsize), dtype='uint8', buffer=word_list.data)
(591, 3)
Lembramos que a distância de Hamming é o número de caracteres diferentes em dois vetores do mesmo comprimento. Usando a distância de Hamming, determinamos o comprimento das arestas que conectam os pares de palavras. A cada duas palavras estão conectadas à escada de palavras com uma distância igual a onde - número de letras em uma palavra:
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))
Ao comparar distâncias, a igualdade não estrita é usada, pois, caso contrário, o resultado pode ser instável para valores de ponto flutuante. A desigualdade fornece o resultado desejado se os dois caracteres da palavra não corresponderem. Agora que o gráfico é fornecido, realizaremos a pesquisa de caminho mais curto entre duas palavras no gráfico:
i1 = word_list.searchsorted ('ape') i2 = word_list.searchsorted ('man')
Agora você precisa encontrar o caminho mais curto entre esses dois vértices no gráfico. Para fazer isso, usamos o algoritmo Dijkstra, que permite encontrar todas as distâncias possíveis para o vértice especificado:
from scipy.sparse.csgraph import dijkstra distances, predecessors = dijkstra(graph, indices=i1, return_predecessors=True) print(distances[i2])
5.0
Portanto, vemos que o caminho mais curto entre um macaco e um homem contém apenas cinco etapas. Podemos usar os predecessores retornados pelo algoritmo para restaurar este caminho:
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']
O comprimento da escada é três passos a menos do que no exemplo inicial. Usando outras ferramentas do módulo, você pode encontrar a resposta para outras perguntas. Por exemplo, existem palavras com três letras que não estão conectadas na escada de palavras? Esta é a tarefa de determinar a conectividade de um gráfico:
from scipy.sparse.csgraph import connected_components N_components, component_list = connected_components(graph) print(N_components)
15
No nosso exemplo, para palavras de três letras, existem 15 componentes relacionados: ou seja, 15 conjuntos diferentes de palavras sem caminhos entre eles. Quantas palavras existem em cada um desses conjuntos? Podemos descobrir na 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]
Temos um gráfico grande, que inclui 577 vértices, além de 14 gráficos isolados. Vamos olhar para estas palavras:
[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']]
Você pode descobrir entre quais palavras há uma escada de comprimento máximo. Isso pode ser determinado calculando a matriz de adjacência. Observe que a distância entre dois pontos desconectados é considerada infinita, portanto, eles devem ser excluídos:
distances, predecessors = dijkstra(graph, return_predecessors=True) max_distance = np.max(distances[~np.isinf(distances)]) print(max_distance)
13.0
Portanto, em nosso exemplo, existem pares de palavras entre os quais a escada mais curta contém 13 degraus! Vamos determinar o que são esses 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 as combinações possíveis de pares de palavras, cuja distância é 13 (maximamente separados um do outro). Se você olhar atentamente, de um lado da escada estão as palavras "imp" e "ump", que diferem entre si com apenas uma letra. Do outro lado da escada estão as palavras "ohm" e "ohs", que também são distinguidas por apenas uma letra. A lista de etapas entre essas palavras será quase a mesma. Pode ser encontrado da mesma maneira como indicado acima:
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']
As escadas de palavras são apenas um dos possíveis usos de algoritmos rápidos em gráficos esparsos no scipy. A teoria dos grafos é usada em muitas áreas da matemática, análise de dados e aprendizado de máquina. As ferramentas de gráficos esparsos Scipy são flexíveis o suficiente para lidar com uma ampla gama de tarefas.
Ficarei feliz se você escrever nos comentários que seção do scipy será interessante ler no próximo artigo.