Hier finden Sie einen Ratschlag. Kennt jemand einen guten Platz, um in einem n-dimensionalen Raum nach einem passenden Algorithmus zu suchen? Zum Beispiel muss jede Dating-Website da draußen eine Art Algorithmus verwenden, um 2 Personen zu entsprechen. Was ich gelesen habe, ist, dass wir Eigenschaften einer Person in einem n-dimensionalen Array mit einem Punktsystem für jedes Merkmal abbilden können. Sobald wir alle (verfügbaren) Eigenschaften einer Person haben, können wir diese Person in einem Punkt innerhalb eines n-dimensionalen Arrays darstellen. Dann wäre die Suche nach der kürzesten Entfernung zwischen zwei Punkten in diesem n-dim-Array so einfach, dass zwei Personen zusammenpassen. Hat irgendjemand einen Bezug bei der Implementierung dieser Art von Algorithmus? Was ist die beste Sprache, um solche Sachen zu schreiben?N-dimensionaler Matching-Algorithmus
Antwort
Wählen Sie zuerst die Sprache aus, mit der Sie vertraut sind. Die Algorithmen zur Handhabung sind ziemlich einfach und sollten in jeder modernen Sprache funktionieren. (Solange es ein Array-Konzept und möglicherweise eine Matrix-Bibliothek gibt, sollten Sie in Ordnung sein.) Ich habe viele davon bereits in C, C++ und C# implementiert, aber Implementierungen in Python, vb.net, etc .
Je nachdem, was Sie zu tun versuchen, gibt es eine Reihe von Optionen.
Das gesagt, was Sie tun möchten, hängt von Ihren Zielen ab. Wenn Sie nur die beste Übereinstimmung finden möchten, können Sie einfache Abstandsberechnungen verwenden (dh: Quadrat der Summe der Quadrate für jede Bemaßung/Eigenschaft im n-dimensionalen Array), optional jede Objektentfernung gewichten und den nächsten Punkt verwenden.
Wenn Sie Personen zusammen gruppieren möchten, sollten Sie sich clustering algorithms ansehen. Für Daten wie diese würde ich vermuten, dass eine Form von K-Means-Clustering oder Fuzzy-C-Means-Clustering am besten funktionieren würde.
Wenn Sie das nächste Spiel für eine Person finden möchten, Bentley & Shamos veröffentlicht eine mehrdimensionale Divide-and-Conquer-Verfahren: Teile-und-Herrsche in O (N log N) Zeit: Divide-and-conquer in multidimensional space in Proceedings of the Achte jährliche ACM-Symposium über die Theorie des Computing 1976. Wenn Sie keine Kopie erhalten können this kann auch hilfreich sein.
Für Ihre Beispielanwendung scheint es jedoch nicht das größte Problem zu sein, den nächsten Nachbarn zu finden - viel schwieriger ist es, Eingaben in Dimensionen zu mappen. Zum Beispiel, wenn eine Dimension "mag Tiere" ist, welchen Wert geben Sie jemandem, der Hunde mag, aber keine Pferde ertragen kann? Was ist mit jemandem, der Pferde liebt, denkt, dass Hunde in Ordnung sind, sich über Katzen ärgern und am Goldfisch ambivalent sind?
Der von Ihnen erwähnte Prozess ist als k-nächster Nachbar bekannt, wobei k = 1 ist. Es ist der intuitivste Ansatz, um ähnliche Vektoren zu finden.
Wie wäre Lösung nach.
Angenommen, die Benutzer sind U1, U2, U3, U4, U5 .... Un. Attribute sind A1, A2, A3, A4, A5 ..... Am
Shop diese als
A1 - U1, U2, U3 ... A2 - U4, U6, U7 ... A3 -
Profilattribut ist der Index und speichert alle Benutzer. Wenn nun ein neuer Benutzer kommt, finden Sie unter den zugehörigen Attributen und für diese Attribute normale Benutzer. wie oft eine Person in diesen Listen existiert - höherrangig.
Was Sie mit Ihrem Beispiel beschreiben, ist kein n-dimensionales Matching, sondern bipartite matching von Knoten mit mehreren Features. (Sie müssen eine Funktion bereitstellen, die berechnet, wenn zwei Personen diese Entfernung berechnen). Dafür sollte es sehr effiziente Algorithmen geben. Beim n-dimensionalen Matching würden Sie versuchen, Knoten aus mehr als zwei Sätzen zu finden (in Ihrem Beispiel könnten Sie Leute zu Körper-, Soul- und Musikpräferenzen abschneiden und sie dann zu neuen Personen zusammenfassen. Dann würde das n-dimensionale Matching) schneiden Sie die Leute auseinander, und rekombinieren Sie sie, so dass die neuen Personen, die ausgeführt werden, wirklich nette Paare machen würden: D) Hier ist die wikipedia article for 3-dimentional matching, die np-vollständig ist.
Wenn Ihr Ziel nicht darin besteht, Personen in Paaren zu finden, sondern kompatible Gruppen, sollten Sie, wie von einem anderen Benutzer angegeben, Cluster zu Gruppen zusammenfassen. Dies kann z.B. Unsupervised Learning
Guter Punkt auf passende Personen in Dimensionen. Vielleicht etwas wie eine Skala pro Dimension, dh jemand, der Katzen und Hunde mag, aber Pferde hasst, würde + 1/+ 1/-1 bekommen, dh: +1 als Punktzahl in dieser Dimension oder etwas in dieser Richtung. –
@danio: Sie können immer eine einzelne Dimension "mag Tiere" in separate "mag Hunde", "mag Katzen", etc. Dimensionen. –