SciPy-Räumliche Daten

Räumliche Daten, auch als geometrische Daten bekannt, werden verwendet, um Informationen über verschiedene Aspekte von Objekten wie Position, Form, Größenverteilung usw. darzustellen, zum Beispiel Punkte auf Koordinaten.

SciPy verarbeitet räumliche Daten über das Modul scipy.spatial, wie z. B. die Bestimmung, ob ein Punkt innerhalb einer Grenze liegt, die Berechnung des nächstgelegenen Punktes um einen gegebenen Punkt und aller Punkte innerhalb einer gegebenen Entfernung.

Triangulation

Die Triangulation ist in der Trigonometrie und Geometrie eine Methode zur Messung der Entfernung zu einem Ziel, indem die Winkel zwischen dem Zielpunkt und den bekannten Endpunkten einer festen Basislinie gemessen werden.

Die Triangulation eines Polygons ist die Unterteilung des Polygons in mehrere Dreiecke, und wir können diese Dreiecke verwenden, um die Fläche des Polygons zu berechnen.

Eine bekannte Tatsache in der Topologie besagt, dass jede Oberfläche eine Triangulation besitzt.

Angenommen, es gibt eine Triangulierung auf einer Fläche. Die Gesamtzahl der Eckpunkte aller Dreiecke sei mit p bezeichnet (gemeinsame Eckpunkte werden nur einmal gezählt), die Anzahl der Kanten mit a und die Anzahl der Dreiecke mit n. Dann ist e = p - a + n eine topologische Invariante der Fläche. Das heißt, unabhängig davon, welche Triangulierung verwendet wird, ergibt e immer denselben Wert. e wird als Euler-Charakteristik bezeichnet.

Die Methode zur Triangulierung einer Punktmenge ist die Delaunay()-Triangulation.

Beispiel

Dreiecke aus gegebenen Punkten erstellen:

import numpy as np
from scipy.spatial import Delaunay
import matplotlib.pyplot as plt

points = np.array([
  [2, 4],
  [3, 4],
  [3, 0],
  [2, 2],
  [4, 1]
])

simplices = Delaunay(points).simplices    # Indizes der Eckpunkte im Dreieck

plt.triplot(points[:, 0], points[:, 1], simplices)
plt.scatter(points[:, 0], points[:, 1], color='r')

plt.show()

Das Ausgabeergebnis ist in der folgenden Abbildung dargestellt:

Hinweis:Die IDs der Eckpunkte des Dreiecks werden im simplices-Attribut des Triangulierungsobjekts gespeichert.

Konvexe Hülle

Die konvexe Hülle ist ein Konzept in der algorithmischen Geometrie (Grafik).

In einem reellen Vektorraum V wird für eine gegebene Menge X der Durchschnitt S aller X enthaltenden konvexen Mengen als konvexe Hülle von X bezeichnet. Die konvexe Hülle von X kann mithilfe von Konvexkombinationen aller Punkte (X1, ...Xn) in X konstruiert werden.

Wir können die Methode ConvexHull() verwenden, um eine konvexe Hülle zu erstellen.

Beispiel

Erstellen Sie eine konvexe Hülle aus gegebenen Punkten:

import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt

points = np.array([
  [2, 4],
  [3, 4],
  [3, 0],
  [2, 2],
  [4, 1],
  [1, 2],
  [5, 0],
  [3, 1],
  [1, 2],
  [0, 2]
])

hull = ConvexHull(points)
hull_points = hull.simplices

plt.scatter(points[:,0], points[:,1])
for simplex in hull_points:
  plt.plot(points[simplex,0], points[simplex,1], 'k-')

plt.show()

Das Ausgabeergebnis ist in der folgenden Abbildung dargestellt:

K-D-Baum

Ein kd-Baum (Abkürzung für k-dimensionaler Baum) ist eine Baumdatenstruktur, die Instanzpunkte im k-dimensionalen Raum für schnellen Abruf speichert. Er wird hauptsächlich zum Suchen von Schlüsseldaten im mehrdimensionalen Raum verwendet (z. B. Bereichssuche und Nächste-Nachbarn-Suche).

K-D-Bäume können in verschiedenen Anwendungen eingesetzt werden, wie z. B. bei der mehrdimensionalen Schlüsselsuche (Bereichssuche und Nächste-Nachbarn-Suche).

Die Nächste-Nachbar-Suche wird verwendet, um den Punkt im Baum zu finden, der dem Eingabepunkt am nächsten liegt.

KDTree()Die Methode gibt ein KDTree-Objekt zurück.

query()Die Methode gibt die Distanz zum nächsten Nachbarn und die Position des nächsten Nachbarn zurück.

Beispiel

Ermittle die Distanz zum nächsten Nachbarn zu (1,1):

from scipy.spatial import KDTree

points = [(1, -1), (2, 3), (-2, 3), (2, -3)]

kdtree = KDTree(points)

res = kdtree.query((1, 1))

print(res)

Das Ausgabeergebnis ist in der folgenden Abbildung dargestellt:

(2.0, 0)

Distanzmatrix

In der Mathematik ist eine Distanzmatrix eine Matrix (zweidimensionales Array), deren Elemente die Abstände zwischen Punkten sind. Daher ist ihre Distanzmatrix für N Punkte im euklidischen Raum eine Matrix mit nicht negativen reellen Zahlen als Elementen.N×NDie symmetrische Matrix. Distanzmatrix und Adjazenzmatrix sind im Konzept ähnlich, der Unterschied besteht darin, dass letztere nur enthält, ob es eine Kante zwischen Elementen (Punkten) gibt, und keine Informationen über die Entfernung der Verbindung zwischen Elementen (Punkten) enthält. Daher kann eine Distanzmatrix als gewichtete Form einer Adjazenzmatrix angesehen werden.

Zum Beispiel analysieren wir die folgenden zweidimensionalen Punkte a bis f. Hier nehmen wir die euklidische Metrik zwischen den Pixeln, an denen sich die Punkte befinden, als Distanzmetrik.

Ihre Distanzmatrix ist:

Diese Daten der Distanzmatrix können in grafischer Darstellung weiter als Heatmap betrachtet werden (wie in der Abbildung unten dargestellt), wobei Schwarz den Abstand null und Weiß den maximalen Abstand darstellt.

In der Bioinformatik werden Distanzmatrizen verwendet, um Proteinstrukturen unabhängig von Koordinatensystemen darzustellen, sowie die Abstände zwischen zwei Sequenzen im Sequenzraum. Diese Darstellungen werden beim Struktur-Alignment, Sequenz-Alignment und bei der Bestimmung von Proteinstrukturen in NMR, Röntgen- und Kristallographie verwendet.

Euklidische Distanz

In der Mathematik ist die euklidische Distanz oder euklidische Metrik die "gewöhnliche" (d. h. geradlinige) Entfernung zwischen zwei Punkten im euklidischen Raum. Mit dieser Distanz wird der euklidische Raum zu einem metrischen Raum. Die zugehörige Norm wird euklidische Norm genannt. Frühere Literatur bezeichnet sie als pythagoreische Metrik.

Die euklidische Metrik (auch euklidische Distanz genannt) ist eine häufig verwendete Definition des Abstands und bezeichnet die tatsächliche Entfernung zwischen zwei Punkten im m-dimensionalen Raum oder die natürliche Länge eines Vektors (d. h. den Abstand vom Punkt zum Ursprung). Im zwei- und dreidimensionalen Raum ist die euklidische Distanz die tatsächliche Entfernung zwischen zwei Punkten.

Das folgende Beispiel betrachtet die euklidische Distanz zwischen gegebenen Punkten:

Beispiel

from scipy.spatial.distance import euclidean

p1 = (1, 0)
p2 = (10, 2)

res = euclidean(p1, p2)

print(res)

Das Ausgabeergebnis ist in der folgenden Abbildung dargestellt:

9.21954445729

Manhattan-Distanz

Die Taxicab-Geometrie oder Manhattan-Distanz ist ein Begriff, der im 19. Jahrhundert von Hermann Minkowski geprägt wurde. Es ist ein geometrischer Begriff, der in metrischen Räumen verwendet wird, um die Summe der absoluten axialen Abstände zwischen zwei Punkten in einem Standardkoordinatensystem anzugeben.

Die Manhattan-Distanz erlaubt nur Bewegungen in die vier Richtungen nach oben, unten, links und rechts, und die Manhattan-Distanz zwischen zwei Punkten ist die kürzeste Entfernung zwischen ihnen.

Manhattan- vs. euklidische Distanz: Die roten, blauen und gelben Linien zeigen jeweils an, dass alle Manhattan-Distanzen dieselbe Länge (12) haben, während die grüne Linie anzeigt, dass die euklidische Distanz eine Länge von 6×√2 ≈ 8.48 hat.

Das folgende Beispiel berechnet die Manhattan-Distanz zwischen den gegebenen Punkten:

Beispiel

from scipy.spatial.distance import cityblock

p1 = (1, 0)
p2 = (10, 2)

res = cityblock(p1, p2)

print(res)

Das Ausgabeergebnis ist:

11

Kosinus-Distanz

Die Kosinus-Distanz, auch bekannt als Kosinus-Ähnlichkeit, misst die Ähnlichkeit zwischen zwei Vektoren, indem sie den Kosinus des Winkels zwischen ihnen misst.

Der Kosinus eines 0-Grad-Winkels ist 1, während der Kosinus jedes anderen Winkels nicht größer als 1 ist und sein Minimalwert -1 ist.

Das folgende Beispiel berechnet die Kosinus-Distanz zwischen den Punkten A und B:

Beispiel

from scipy.spatial.distance import cosine

p1 = (1, 0)
p2 = (10, 2)

res = cosine(p1, p2)

print(res)

Das Ausgabeergebnis ist:

0.019419324309079777

Hamming-Distanz

In der Informationstheorie ist die Hamming-Distanz zwischen zwei gleich langen Zeichenketten die Anzahl der Positionen, an denen sich die entsprechenden Zeichen unterscheiden. Mit anderen Worten: Sie ist die Anzahl der Zeichen, die ersetzt werden müssen, um eine Zeichenkette in die andere umzuwandeln.

Das Hamming-Gewicht ist die Hamming-Distanz zwischen einer Zeichenkette und einer Null-Zeichenkette derselben Länge. Mit anderen Worten: Es ist die Anzahl der Nicht-Null-Elemente in der Zeichenkette; für eine Binärzeichenkette ist es die Anzahl der Einsen, also ist das Hamming-Gewicht von 11101 gleich 4.

  • 1011101und1001001Die Hamming-Distanz zwischen ihnen beträgt 2.
  • 2143896und2233796Die Hamming-Distanz zwischen ihnen beträgt 3.
  • "toned"und"roses"Die Hamming-Distanz zwischen ihnen beträgt 3."

Das folgende Beispiel berechnet die Hamming-Distanz zwischen zwei Punkten:

Beispiel

from scipy.spatial.distance import hamming

p1 = (True, False, True)
p2 = (False, True, True)

res = hamming(p1, p2)

print(res)

Das Ausgabeergebnis ist:

0.666666666667
Andere Erweiterungen