Welcher Algorithmus zur Auswahl des richtigen Punktes angewendet werden soll

Das Bild unten zeigt 7 Punkte um den Ursprung. Einer von ihnen wurde von einem Menschen aufgrund von Regeln und Erfahrungen ausgewählt und ist rot gefärbt (der im unteren linken Quadranten).

Jetzt haben wir über 1000 dieser Punktmengen und für jede Menge hat ein Mensch einen einzelnen Punkt ausgewählt. Diese Bedingungen gelten für alle Sets:

• Jeder Satz hat ungefähr 3 - 10 Punkte
• Es gibt keine Ausreißer
• Punkte können positive und negative Werte haben
• Bei der Auswahl eines Punktes wurden keine Fehler gemacht

Meine Frage ist: Gibt es einen Algorithmus für maschinelles Lernen, um aus diesen Sätzen und von Menschen getroffenen Auswahlen zu lernen, damit er automatisch entscheiden kann, welcher Punkt ausgewählt werden soll, wenn ein neuer Satz von Punkten vergeben wird? Dieses neue Set erfüllt natürlich die ersten 3 Bedingungen von oben.

2 abschließende Bemerkungen:

• Das Beispiel, das ich gegeben habe, ist nur ein zufällig erstelltes Beispiel von mir, um die Idee von Punkten in einer Ebene um den Ursprung zusammen mit einem ausgewählten zu unterstützen. Im wirklichen Leben mag es mehr Struktur geben, aber im Moment bin ich neugierig und würde gerne wissen, was für diesen Fall möglich ist.
• Wären Variationen möglich? Angenommen, es handelt sich um 2 ausgewählte Punkte, oder Sie haben Kreise mit einem bestimmten Radius anstelle von Punkten.

Das ist ein faszinierendes Problem! Zwei Dinge machen es besonders herausfordernd:

• Wie sollen wir zwei Punktmengen vergleichen? Klassische Probleme beim maschinellen Lernen haben eine feste Anzahl von Attributen, und diese Attribute sind nicht austauschbar: Zum Beispiel könnte ich Daten über verschiedene Personen mit Attributen ageund height(in Zentimetern) haben. Jede Probe hat einen Eintrag für jede und ist natürlich (age, height) = (22, 180)nicht dasselbe wie (age, height) = (180, 22). Beides trifft auf Ihr Problem nicht zu. Eine Punktmenge hat zwischen 3 und 10 Punkte, und die Reihenfolge, in der wir die Punkte eingeben, sollte beim Vergleich zweier Punktmengen keinen Unterschied machen.
• Wie machen wir eine Vorhersage? Angenommen, wir haben einen Weg gefunden, Punktesätze aus unserem Trainingssatz auszuwählen, die Ihrem oben genannten Punktesatz ähnlich sind. Wir stehen vor dem Problem, dass unsere Vorhersage einer der 7 Punkte in Ihrem Bild sein muss. Keiner dieser Punkte kann jedoch in ähnlichen Punktmengen enthalten sein.

Lassen Sie mich einen Algorithmus skizzieren, der sich mit beiden Herausforderungen befasst. Die Vorhersagegenauigkeit ist nicht sehr gut; aber vielleicht sehen Sie einen Weg, wie es verbessert werden kann. Und zumindest sagt es etwas voraus , oder?

1. Proben simulieren

Um den Algorithmus testen zu können, habe ich Funktionen geschrieben, die Samples und Labels generieren.

Proben erzeugen: Jede Probe enthält zwischen 3 und 10 Punkte. Die Anzahl der Punkte ist zufällig und ergibt sich aus einer gleichmäßigen Verteilung. Jeder Punkt hat die Form (x_coordinate, y_coordinate). Die Koordinaten sind wiederum zufällig und stammen aus einer Normalverteilung.

import numpy as np
from random import randint

def create_samples(number_samples, min_points, max_points):

    def create_single_sample(min_points, max_points):
        n = randint(min_points, max_points)
        return np.array([np.random.normal(size=2) for _ in range(n)]) 

    return np.array([create_single_sample(min_points, max_points) for _ in range(number_samples)])

Generieren von Beschriftungen: Nehmen wir als Spielzeugbeispiel an, dass die Regel für die Auswahl eines Punkts lautet: Wählen Sie immer den Punkt aus, der am nächsten liegt (0, 0), wobei "am nächsten" im Sinne der euklidischen Norm zu verstehen ist.

def decision_function_minnorm(sample):
    norms = np.apply_along_axis(np.linalg.norm, axis=1, arr=sample)
    return sample[norms.argmin()]

def create_labels(samples, decision_function):
    return np.array([decision_function(sample) for sample in samples])

Wir können jetzt unsere Zug- und Testsätze erstellen:

n_train, n_test = 1000, 100
dec_fun = decision_function_minnorm

X_train = create_samples(number_samples=n_train, min_points=3, max_points=10)
X_test = create_samples(number_samples=n_test, min_points=3, max_points=10)
y_train = create_labels(X_train, dec_fun)
y_test = create_labels(X_test, dec_fun)

2. Vergleich der Punktmengen über die Hausdorff-Distanz

Lassen Sie uns das erste Problem angehen: Wie sollen wir verschiedene Punktmengen vergleichen? Die Anzahl der Punkte in den Punktmengen ist unterschiedlich. Denken Sie auch daran, dass die Reihenfolge, in der wir die Punkte aufschreiben, keine Rolle spielen sollte: Der Vergleich mit der Punktmenge [(0,0), (1,1), (2,2)]sollte das gleiche Ergebnis liefern wie der Vergleich mit der Punktmenge [(2,2), (0,0), (1,1)]. Mein Ansatz ist es, Punktmengen über ihre Hausdorff-Entfernung zu vergleichen :

def hausdorff(A, B):

    def dist_point_to_set(x, A):
        return min(np.linalg.norm(x - a) for a in A)

    def dist_set_to_set(A, B):
        return max(dist_point_set(a, B) for a in A)

    return max(dist_set_to_set(A, B), dist_set_to_set(B, A))

3. Vorhersage über k-nächste Nachbarn und Mittelwertbildung

Wir haben jetzt eine Vorstellung von der Entfernung zwischen Punktmengen. Dies ermöglicht die Verwendung der Klassifikation der k-nächsten Nachbarn: Bei gegebenem Testpunktsatz finden wir kin unserem Trainingsmuster die Punktsätze, die den kleinsten Hausdorff-Abstand zum Testpunktsatz aufweisen, und erhalten ihre Bezeichnungen. Nun kommt das zweite Problem: Wie verwandeln wir diese kBeschriftungen in eine Vorhersage für den Testpunktsatz? Ich habe den einfachsten Ansatz gewählt: Durchschnitt der Beschriftungen und Vorhersage des Punkts im Testpunktsatz, der dem Durchschnitt am nächsten kommt.

def predict(x, num_neighbors):
    # Find num_neighbors closest points in X_train.
    distances_to_train = np.array([hausdorff(x, x_train) for x_train in X_train])
    neighbors_idx = np.argpartition(distances_to_train, -num_neighbors)[-num_neighbors:]

    # Get labels of the neighbors and calculate the average.
    targets_neighbors = y_train[neighbors_idx]
    targets_mean = sum(targets_neighbors) / num_neighbors

    # Find point in x that is closest to targets_mean and use it as prediction.
    distances_to_mean = np.array([np.linalg.norm(p - targets_mean) for p in x])
    closest_point = x[distances_to_mean.argmin()]

    return closest_point

4. Testen

Alles ist vorhanden, um die Leistung unseres Algorithmus zu testen.

num_neighbors = 70
successes = 0
for i, x in enumerate(X_test):
    print('%d/%d' % (i+1, n_test))
    prediction = predict(x, num_neighbors)
    successes += np.array_equal(prediction, y_test[i])

Für die gegebene Entscheidungsfunktion und erhalten num_neighbors = 70wir eine Vorhersagegenauigkeit von 84%. Dies ist nicht besonders gut und natürlich spezifisch für unsere Entscheidungsfunktion, die ziemlich einfach vorherzusagen scheint.

Um dies zu sehen, definieren Sie eine andere Entscheidungsfunktion:

decision_function_maxaverage(sample):
    avgs = (sample[:, 0] + sample[:, 1]) / 2
    return sample[norms.argmin()]

Durch Verwendung dieser Funktion über wird dec_fun = decision_function_maxaveragedie Vorhersagegenauigkeit auf 45% gesenkt. Dies zeigt, wie wichtig es ist, über die Entscheidungsregeln nachzudenken, die Ihre Labels generieren. Wenn Sie eine Idee haben, warum Personen bestimmte Punkte auswählen, können Sie auf diese Weise den besten Algorithmus finden.

Einige Möglichkeiten zur Verbesserung dieses Algorithmus: (1) Verwenden Sie eine andere Distanzfunktion anstelle der Hausdorff-Distanz, (2) verwenden Sie etwas Anspruchsvolleres als k-nächste Nachbarn, (3) verbessern Sie, wie die ausgewählten Trainingsbezeichnungen in eine Vorhersage umgewandelt werden.

Hier sind einige Möglichkeiten, wie Sie neuronale Netze verwenden können, um dieses Problem zu lösen:

Mit einem einfachen neuronalen Feedforward-Netzwerk:

• Skalieren Sie Ihre Daten so, dass sie in das Quadrat um den Ursprung von (-1, -1) bis (1,1) passen.
• $k$
• Fügen Sie für jeden Punkt einen dritten Indikatoreingang hinzu, der angibt, ob dieser Punkt vorhanden ist
• Wählen Sie die Anzahl und Größe der ausgeblendeten Ebenen
• Verwenden Sie am Ausgang eine Softmax-Schicht der Größe 10

$k$$k$ Punkte in der Menge vorhanden sind, und die Ausgabe ein Vektor der Länge 10 ist, der zu 1 summiert, unabhängig davon, ob die Der größte Wert entspricht dem vorhergesagten Punkt (dessen Position dieser Position in der Eingabe entspricht).

Mit einem Faltungs-Neuronalen Netz:

• $n$$n$$n$$n$$k$$k$$i,j$$0$$1$$0$
• $n*n$

Das CNN bietet möglicherweise eine bessere Leistung, da Ihre Daten von Natur aus räumlich sind. Sie müssen jedoch entscheiden, was zu tun ist, wenn sich zwei oder mehr Punkte überlappen. Die einfachste Lösung besteht darin, eine zufällig auszuwählen, was je nach Ihrer spezifischen Aufgabe in Ordnung sein kann.

Mit einem wiederkehrenden neuronalen Netzwerk:

• Geben Sie Sequenzen variabler Länge von skalierten (x, y) Punkten ein und geben Sie eine Softmax-Schätzung der Größe 10 aus

Ja, so einfach ist das mit RNNs! Sie verarbeiten Eingaben mit variabler Länge gut, aber es fehlen ihnen immer noch die Vorteile von CNNs für die Verarbeitung von Geodaten.

Vorsichtsmaßnahmen:

Wenn Sie eine FNN oder eine RNN verwenden, kommt es auch darauf an, wie Sie Ihre Eingabedaten bestellen. Wenn Ihre realen Daten keine inhärente Reihenfolge aufweisen, möchten wir nicht, dass unser Netzwerk unterschiedliche Vorhersagen für dieselben Daten trifft, die in unterschiedlichen Reihenfolgen codiert sind. Eine Möglichkeit, dies zu handhaben, ist die Datenerweiterung : Duplizieren Sie jedes Trainingsbeispiel einige Male mit unterschiedlichen Eingabereihenfolgen, damit Ihr Netzwerk hoffentlich die entsprechenden Symmetrien lernen kann.

Wenn Sie nur Zeit haben, einen Ansatz auszuprobieren, würde ich den CNN wählen. CNNs sind so konzipiert, dass sie gut mit räumlichen Daten umgehen können, und es gibt kein Problem mit der Eingabereihenfolge.