SciPy (ausgesprochen sai pie) ist ein mathematisches Anwendungspaket, das auf der Erweiterung Numpy Python basiert. Es erweitert die Funktionen von Python erheblich, indem es dem Benutzer allgemeine Befehle und Klassen zum Verwalten und Visualisieren von Daten zur Verfügung stellt. Mit SciPy wird aus einer interaktiven Python-Sitzung dieselbe komplexe Datenverarbeitungs- und Prototyping-Umgebung für komplexe Systeme wie MATLAB, IDL, Octave, R-Lab und SciLab.
Einführung
Es wird empfohlen, das SciPy-Paket als Teil von Anaconda zu installieren. Es ist auch ratsam, sich mit den Grundlagen von Python vertraut zu machen und über eine Numpy-Dokumentation zu verfügen. Der Kürze halber und zur Vereinfachung vereinbaren wir, dass die Hauptpakete (numpy, scipy und matplotlib) wie folgt importiert werden:
import numpy as np import matplotlib as mpl import matplotlib.pyplot as plt
Dies ist die offizielle Importvereinbarung, die im NumPy-, SciPy-Quellcode und in der Dokumentation verwendet wird. Die Einhaltung dieser Konventionen in Ihrem Code ist optional, wird jedoch dringend empfohlen. Es ist ratsam, jedes der Pakete wie folgt separat zu importieren:
from scipy import linalg, optimize
SciPy und NumPy verfügen über Vollversionen der Dokumentation, die fast alle ihre Funktionen abdecken. Sie sind unter https://docs.scipy.org/ im HTML- und PDF-Format verfügbar. Einige Teile sind möglicherweise unvollständig oder veraltet Die Dokumentation wird ständig weiterentwickelt. Da SciPy eine Freiwilligenorganisation ist und von der Community abhängt, ist Ihre Teilnahme von der Bereitstellung von Feedback bis zur Verbesserung der Dokumentation und des Codes willkommen und wird aktiv gefördert.
Sparse Graph Algorithmen (scipy.csgraph)
Lewis Carroll, Frohe Weihnachten 1877
Betrachten Sie die Verwendung des Pakets scipy.csgraph als Beispiel für das von Lewis Carroll am Weihnachtstag 1877 erfundene Kinderspiel " Ladders of Words ". In diesem Spiel müssen Sie den Pfad zwischen den Wörtern finden und jeweils einen Buchstaben ersetzen. Sie können beispielsweise den Pfad von einem Affen zu einer Person verfolgen, indem Sie die Wörter „Affe“ und „Mensch“ wie folgt verbinden:
Bitte beachten Sie, dass bei jedem Schritt nur ein Buchstabe des Wortes geändert wird. Dies ist nur ein möglicher Weg von einem Affen zu einem Mann, aber ist dies der kürzeste Weg? Daher ist es notwendig, den kürzesten Weg (Leiter) zwischen zwei gegebenen Wörtern zu finden. Dieses Problem kann mit dem Paket scipy.sparse.csgraph gelöst werden.
Zuerst brauchen wir eine Liste gültiger Wörter. Viele Betriebssysteme haben eine solche integrierte Liste. Unter Linux befindet sich beispielsweise eine Liste von Wörtern an einer der folgenden Stellen:
/usr/share/dict /var/lib/dict
Eine weitere Wortquelle sind Wörterbücher, die auf verschiedenen Websites im Internet verfügbar sind (siehe Ihre bevorzugte Suchmaschine). Die Systemwortliste ist eine Datei mit einem Wort pro Zeile. Um die Systemwortliste zu verwenden, müssen Sie sie wie folgt lesen:
word_list = open('/usr/share/dict/words').readlines() word_list = map(str.strip, word_list)
Weil Wenn wir nach Wörtern mit drei Buchstaben suchen, wählen wir nur die erforderlichen Wörter aus der allgemeinen Liste aus. Schließen Sie auch Wörter aus, die mit Großbuchstaben (Eigennamen) beginnen oder nicht alphabetische Zeichen wie Apostrophe und Bindestriche enthalten. Überprüfen Sie am Ende die Größe der resultierenden Wortliste.
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
Jetzt haben wir eine Liste von 591 Wörtern mit drei Buchstaben (die genaue Anzahl kann je nach verwendetem Wörterbuch variieren). Jedes dieser Wörter steht oben in der Grafik. Erstellen Sie Kanten, die die Eckpunkte (Wortpaare) verbinden und sich nur um einen Buchstaben unterscheiden.
Wir verwenden einen ziemlich effizienten Weg, der eine Manipulation des Numpy-Arrays erfordert:
word_list = np.asarray(word_list) word_list.sort()
dtype('<U3')
Jetzt haben wir ein Array, in dem jeder Eintrag drei Unicode-Zeichen enthält. Wir möchten alle Paare finden, die genau ein Zeichen haben. Beginnen wir damit, jedes Wort in einen dreidimensionalen Vektor umzuwandeln:
word_bytes = np.ndarray((word_list.size, word_list.itemsize), dtype='uint8', buffer=word_list.data)
(591, 3)
Wir erinnern uns, dass der Hamming-Abstand die Anzahl verschiedener Zeichen in zwei Vektoren gleicher Länge ist. Anhand des Hamming-Abstands bestimmen wir die Länge der Kanten, die die Wortpaare verbinden. Alle zwei Wörter werden mit einem Abstand von gleich der Wortleiter verbunden wo - Anzahl der Buchstaben in einem Wort:
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))
Beim Vergleichen von Entfernungen wird eine nicht strikte Gleichheit verwendet, da das Ergebnis sonst für Gleitkommawerte instabil sein kann. Ungleichung ergibt das gewünschte Ergebnis, wenn die beiden Zeichen im Wort nicht übereinstimmen. Nachdem das Diagramm angegeben wurde, führen wir die Suche nach dem kürzesten Pfad zwischen zwei beliebigen Wörtern im Diagramm durch:
i1 = word_list.searchsorted ('ape') i2 = word_list.searchsorted ('man')
Jetzt müssen Sie den kürzesten Weg zwischen diesen beiden Eckpunkten im Diagramm finden. Dazu verwenden wir den Dijkstra-Algorithmus, mit dem Sie alle möglichen Abstände für den angegebenen Scheitelpunkt finden können:
from scipy.sparse.csgraph import dijkstra distances, predecessors = dijkstra(graph, indices=i1, return_predecessors=True) print(distances[i2])
5.0
Wir sehen also, dass der kürzeste Weg zwischen einem Affen und einem Mann nur fünf Schritte enthält. Wir können die vom Algorithmus zurückgegebenen Vorgänger verwenden, um diesen Pfad wiederherzustellen:
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']
Die Länge der Treppe beträgt drei Stufen weniger als im ersten Beispiel. Mit anderen Tools des Moduls können Sie die Antwort auf andere Fragen finden. Gibt es zum Beispiel Wörter mit drei Buchstaben, die nicht in der Treppe der Wörter verbunden sind? Dies ist die Aufgabe, die Konnektivität eines Diagramms zu bestimmen:
from scipy.sparse.csgraph import connected_components N_components, component_list = connected_components(graph) print(N_components)
15
In unserem Beispiel gibt es für Wörter mit drei Buchstaben 15 verwandte Komponenten, dh 15 verschiedene Wortgruppen ohne Pfade zwischen ihnen. Wie viele Wörter enthält jedes dieser Sets? Wir können aus der Liste der Komponenten herausfinden:
[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]
Wir haben ein großes Diagramm mit 577 Eckpunkten sowie 14 isolierte Diagramme. Schauen wir uns diese Worte an:
[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']]
Sie können herausfinden, zwischen welchen Wörtern sich eine Leiter mit maximaler Länge befindet. Dies kann durch Berechnung der Adjazenzmatrix bestimmt werden. Beachten Sie, dass der Abstand zwischen zwei nicht verbundenen Punkten als unendlich betrachtet wird. Daher sollten sie ausgeschlossen werden:
distances, predecessors = dijkstra(graph, return_predecessors=True) max_distance = np.max(distances[~np.isinf(distances)]) print(max_distance)
13.0
In unserem Beispiel gibt es also solche Wortpaare, zwischen denen die kürzeste Treppe 13 Stufen enthält! Lassen Sie uns bestimmen, was diese Paare sind:
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')]
Wir haben alle möglichen Kombinationen von Wortpaaren gesehen, deren Abstand 13 beträgt (maximal voneinander getrennt). Wenn Sie genau hinschauen, befinden sich auf einer Seite der Treppe die Wörter "imp" und "ump", die sich mit nur einem Buchstaben voneinander unterscheiden. Auf der anderen Seite der Treppe befinden sich die Wörter "Ohm" und "Ohs", die sich auch durch nur einen Buchstaben unterscheiden. Die Liste der Schritte zwischen diesen Wörtern ist fast gleich. Es kann auf die gleiche Weise wie oben angegeben gefunden werden:
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']
Worttreppen sind nur eine der möglichen Anwendungen schneller Algorithmen für spärliche Diagramme in Scipy. Die Graphentheorie wird in vielen Bereichen der Mathematik, Datenanalyse und des maschinellen Lernens verwendet. Scipy Sparse Graph Tools sind flexibel genug, um eine Vielzahl von Aufgaben zu erledigen.
Ich würde mich freuen, wenn Sie in den Kommentaren schreiben, welcher Abschnitt von scipy im nächsten Artikel interessant zu lesen sein wird.