Algorithmus similarness von Sätzen von Zahlen zu punkten

StackOverflow https://stackoverflow.com/questions/139811

  •  02-07-2019
  •  | 
  •  

Frage

Was ist ein Algorithmus, mehrere Sätze von Zahlen gegen ein Ziel vergleichen gesetzt zu bestimmen, welche die „ähnlich“ sind?

Eine Verwendung dieses Algorithmus wäre heutige stündliche Wettervorhersage gegen historische Wetteraufzeichnungen zu vergleichen, um einen Tag zu finden, die ähnliche Wetter hatte.

Die Ähnlichkeit von zwei Sätzen ist ein wenig subjektiv, so dass der Algorithmus wirklich braucht nur zwischen guten Spielen und schlechten Spielen diferentiate. Wir haben eine Menge von historischen Daten, so würde Ich mag versuchen, die Anzahl der Tage zu verengen die Benutzer benötigen, indem es automatisch Sätze werfen zu durchschauen, die nicht in der Nähe sind und versuchen, die „besten“ zu setzen Spiele an der Spitze die folgende Liste.

Bearbeiten : Im Idealfall würde das Ergebnis des Algorithmus zu den Ergebnissen mit verschiedenen Datensatz vergleichbar sein. Zum Beispiel mit dem mittleren quadratischen Fehler, wie vorgeschlagen von Niles produziert recht gute Ergebnisse, aber die erzeugten Zahlen, wenn die Temperatur des Vergleich nicht zu Zahlen mit anderen Daten wie Windgeschwindigkeit oder Niederschlag erzeugt verglichen werden, da der Umfang der Daten unterscheidet. Einige der nicht-Wetterdaten Wesen ist sehr groß, so dass der mittlere quadratische Fehler Algorithmus erzeugt Zahlen in die Hunderttausende im Vergleich zu den Dutzenden oder Hunderten, die mit Temperatur erzeugt wird.

War es hilfreich?

Lösung

ich glaube, die mittlere quadratische Fehler-Metrik für Anwendungen funktionieren könnte wie Wetter vergleicht. Es ist leicht zu berechnen und gibt Zahlen, die Sinn machen machen.

Da Ihr Mangel Messungen im Laufe der Zeit zu vergleichen, können Sie einfach auslassen Werte aus der Berechnung fehlen.

Für Werte, die nicht zeitgebunden oder auch unsortiert, mehrdimensionale Streudaten sind, ist es ein bisschen schwieriger. eine gute Distanzmetrik wird die Wahl solcher Daten Teil der Kunst der Analyse.

Andere Tipps

Mit der pearson Korrelationskoeffizient. Ich fand heraus, wie es in einer SQL-Abfrage zu berechnen, die hier gefunden werden kann: http://vanheusden.com /misc/pearson.php

In der Finanz verwenden sie Beta die Korrelation von 2 Reihe von Zahlen zu messen. EG, Beta könnte die Frage „Im letzten Jahr, wie viel würde der Preis von IBM an einem Tag steigen, dass der Preis des S & P-500-Index um 5% ging?“ Es befasst sich mit dem Prozentsatz der Bewegung, so dass die 2-Serie verschiedene Skalen haben.

In meinem Beispiel ist die Beta-Kovarianz (IBM, S & P 500) / Abweichung (S & P 500).

Wikipedia hat Seiten erklären Kovarianzstrukturen Variance und Beta: http://en.wikipedia.org/wiki/Beta_ (Finanzwesen)

Blick auf statistischen Websites. Ich glaube, Sie für die Korrelation suchen.

Als Beispiel werde ich nehme an, Sie messen Temperatur, Wind und Niederschlag. Wir werden diese Elemente „Features“ nennen. So gültige Werte können sein:

  • Temp: -50 bis 100F (Ich bin in Minnesota, USA)
  • Wind: 0 bis 120 Meilen / h (nicht sicher, ob dies realistisch ist, aber mit mir tragen)
  • Niederschlag: 0 bis 100

Starten Sie durch Ihre Daten zu normalisieren. Temp hat eine Reichweite von 150 Einheiten, Wind 120 Einheiten und 100 Einheiten Niederschl. Multiplizieren Sie Ihre Windanlagen von 1,25 und Niederschlag von 1,5 bis sie in etwa gleich „Maßstab“ als Temp zu machen. Sie können Phantasie hier und machen Regeln erhalten, die als andere eine Funktion als wertvollen wiegen. In diesem Beispiel könnte Wind eine große Auswahl haben, aber in der Regel bleibt in einem kleineren Bereich, so dass Sie es weniger wiegen wollen, es zu verhindern, dass Ihre Ergebnisse verfälscht haben.

Nun stellt jede Messung als einen Punkt in mehrdimensionalen Raum. Dieses Beispiel misst 3D-Raum (Temperatur, Wind, Niederschlag). Das Schöne daran ist, wenn wir mehr Funktionen hinzuzufügen, wir einfach die Dimensionalität unseres Raumes erhöhen, aber die Mathematik bleibt gleich. Auf jeden Fall wollen wir die historischen Punkte finden, die am nächsten zu unserem aktuellen Punkt befinden. Der einfachste Weg, dies zu tun, ist euklidischen Abstand . So misst die Entfernung von unserem aktuellen Punkt zu jedem historischen Punkt und halten Sie die nächsten Begegnungen: 

for each historicalpoint

    distance = sqrt(
        pow(currentpoint.temp - historicalpoint.temp, 2) + 
        pow(currentpoint.wind - historicalpoint.wind, 2) +
        pow(currentpoint.precip - historicalpoint.precip, 2))

    if distance is smaller than the largest distance in our match collection
        add historicalpoint to our match collection
        remove the match with the largest distance from our match collection

next

Dies ist ein Brute-Force-Ansatz. Wenn Sie die Zeit haben, könnten Sie viel schicker bekommen. Mehrdimensionale Daten können als Bäume wie kd-Bäume dargestellt werden oder r-Bäume . Wenn Sie eine Menge von Daten haben, würde Ihre aktuelle Beobachtung mit jeder historischen Beobachtung Vergleich zu langsam. Bäume beschleunigen Ihre Suche. Vielleicht haben Sie einen Blick auf Datenclusterung und Nearest Neighbor Suche .

Prost.

Sprechen Sie

auf einen Statistiker.

Im Ernst.

Sie tun, um diese Art der Sache, für ein Leben.

Sie schreiben, dass die „Ähnlichkeit von zwei Sätzen etwas subjektiv ist“ , aber es ist nicht subjektiv bei all-- es darum, die entsprechenden Kriterien für die Ähnlichkeit für Ihren Problembereich zu bestimmen.

Dies ist einer jener Situation, wo Sie sind viel besser weg zu einem professionellen sprechen, als eine Reihe von Programmierern zu fragen.

Zunächst einmal, fragen Sie sich, wenn diese Sätze oder geordnete Sammlungen.

Ich gehe davon aus, dass diese geordnete Sammlungen mit Dubletten. Der offensichtlichste Algorithmus ist es, eine Toleranz zu wählen, in dem Zahlen gleich betrachtet werden, und die Anzahl der Slots zählen, wo die Zahlen sind gleich unter dieser Maßnahme.

Ich habe eine Lösung für diesen in meiner Anwendung implementiert, aber ich bin auf der Suche, um zu sehen, ob es etwas gibt, das besser oder „richtig“ ist. Für jeden historischen Tag mache ich die folgende: 

function calculate_score(historical_set, forecast_set)
{
    double c = correlation(historical_set, forecast_set);
    double avg_history = average(historical_set);
    double avg_forecast = average(forecast_set);
    double penalty = abs(avg_history - avg_forecast) / avg_forecast
    return c - penalty;
}

ich dann sortiert alle Ergebnisse von hoch zu niedrig.

Da die Korrelation ein Wert von -1 bis 1 ist, die besagt, ob die Zahlen fallen oder steigen zusammen, ich dann „bestrafen“, dass mit der prozentualen Differenz der Mittelwert der beiden Sätze von Zahlen.

Ein paar Mal, haben Sie erwähnt, dass Sie die Verteilung der Daten nicht wissen, was wahr ist natürlich. Ich meine, morgen könnte es einen Tag sein, die 150 Grad F ist, mit 2000 km / h Wind, aber es scheint ziemlich unwahrscheinlich.

Ich würde behaupten, dass Sie eine sehr gute Vorstellung von der Verteilung haben, da Sie eine lange historische Aufzeichnung haben. In Anbetracht, dass Sie alles, was in Bezug auf die Quantile der historischen Aufteilung setzen können, und etwas zu tun mit absoluten oder quadratischen Differenz der Quantile auf alle Maßnahmen. Dies ist eine weitere Normierungsverfahren, aber eine, die für die Nichtlinearitäten in den Daten berücksichtigt.

Normalisierungs in jedem Stil sollten alle Variablen vergleichbar machen.

Als Beispiel wollen wir sagen, dass ein Tag es ist ein windiger, heißen Tag: das eine temporäre Quantil von .75 und einen Wind Quantil .75 haben könnte. Die .76 Quantil für Wärme abstrahlen 1 Grad entfernt sein, und der Computer für den Wind könnte 3kmh entfernt sein.

Dieser Fokus auf der empirischen Verteilung ist einfach wie gut zu verstehen und könnte robuster sein als normale Schätzung (wie Mean-Square-Fehler).

Sind die beiden Datensätze bestellt haben, oder nicht?

Wenn bestellt, sind die Indizes gleich? gleich beabstandeten?

Wenn die Indizes üblich sind (Temperaturen an den gleichen Tagen gemessen (aber unterschiedlichen Standorten), zum Beispiel, können Sie die ersten Datensatz gegen die zweite regredieren, und dann testen, dass die Steigung gleich 1 ist, und dass der Achsenabschnitt ist 0.
http://stattrek.com/AP-Statistics-4/ Test-Slope.aspx? Tutorial = AP

Sie können aber zwei Regressionen tun, der y = Werte gegen ihren Indizes. http://en.wikipedia.org/wiki/Correlation . Sie würden immer noch wollen, Steigungen und Schnittpunkte vergleichen.

====

Wenn ungeordnete, ich glaube, Sie an den kumulativen Verteilungsfunktionen aussehen wollen http://en.wikipedia.org/wiki/Cumulative_distribution_function

Eine entsprechende Prüfung ist Kolmogorov-Smirnov: http://en.wikipedia.org/wiki/Kolmogorov-Smirnov_test

Sie können auch auf

aussehen

T-Test, http://en.wikipedia.org/wiki/Student%27s_t-test

oder ein Wilcoxon-Test http://en.wikipedia.org/wiki/ Wilcoxon_signed-rank_test

Gleichheit der Mittel zwischen den beiden Proben zu testen.

Und man konnte für die Gleichstellung von Abweichungen mit einem Levene-Test testen http://www.itl.nist.gov/div898/handbook/eda/section3/eda35a.htm

Hinweis: es ist möglich, ungleiche Sätze von Daten, die die gleichen Mittelwert und die Varianz zu haben - je nachdem, wie streng Sie sein wollen (und wie viele Daten Sie haben), können Sie könnte betrachten Prüfung für die Gleichstellung von höheren Momenten, wie gut.

Vielleicht ist Ihr Satz von Zahlen als Vektor (jede Nummer des Satzes einen componant des Vektors ist).

Sie können sehen,

Dann können Sie einfach Skalarprodukt verwenden, um die Ähnlichkeit von zwei gegebenen Vektoren (d Satz von Zahlen) zu berechnen.

Möglicherweise müssen Sie Ihre Vektoren normalisieren.

Mehr Kosinusähnlichkeit

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top