schnelle Ähnlichkeit Erkennung

Question

Ich habe eine große Sammlung von Objekten, und ich brauche die Ähnlichkeiten zwischen ihnen zu verstehen.

Um genau zu sein: Da zwei Objekte, die ich ihre Unähnlichkeit als Zahl berechnen kann, ein metrisch - höhere Werte bedeuten weniger Ähnlichkeit und 0 bedeutet, dass die Objekte identische Inhalte. Die Kosten für diese Zahl Computing ist proportional zur Größe des kleineren Objekts (jedes Objekt eine vorgegebene Größe).

ich brauche die Fähigkeit, schnell zu finden, ein Objekt, um den Satz von Objekten ähnlich wie es gegeben.

Um genau zu sein: Ich brauche eine Datenstruktur zu erzeugen, die jedes Objekt abbildet o auf die Menge der Objekte nicht mehr unähnlich o als d, für einige Unähnlichkeit Wert d, so dass die Objekte in der Menge Auflistung nicht mehr Zeit in Anspruch nimmt als wenn sie in einem Array oder einer verknüpften Liste waren (und möglicherweise sind sie tatsächlich). Typischerweise wird die Menge sehr viel kleiner als die Gesamtzahl der Objekte, so ist es wirklich lohnt sich, diese Berechnung durchzuführen. Es ist gut genug, wenn die Datenstruktur eine feste d annimmt, aber wenn es funktioniert für eine beliebige d, noch besser.

Haben Sie dieses Problem, das Sie schon einmal gesehen, oder etwas ähnliches wie das? Was ist eine gute Lösung?

Um genau zu sein: eine einfache Lösung besteht darin, zwischen allen Paaren von Objekten, die die Unterschiedlichkeit der Berechnung, aber das ist langsam - O (n ² ), wobei n die Anzahl der Objekte ist. Gibt es eine allgemeine Lösung mit geringerer Komplexität?

Answer 1

Ohne weitere Details der Metrik zu wissen, es ist schwer zu sagen. Ich habe keine Ideen zur Eliminierung des O (n ^ 2) Aspekt, aber es kann ein Weg sein, zu reduzieren einige der beteiligten Konstanten. wenn Sie ein euklidischen Metrik d (p, q) = sqrt haben zum Beispiel ((p_1-Q_1) ^ 2 + .. + (p_n-q_n) ^ 2), könnten Sie Ihren Abstand d Quadrat und an den Teil vergleichen Summen von (p_i-Q_i) ^ 2 und nicht mehr, wenn man d ^ 2 überschreiten.

Ob dies tatsächlich Sie sparen Zeit hängt davon ab, wie teuer der Vergleich nur die Summanden zu berechnen und wie viele Summanden Berechnungen, die Sie dies tun zu vermeiden, erwarten konnte (natürlich, je kleiner d ist, desto besser).

Answer 2

  

Ich brauche eine Datenstruktur zu erzeugen   dass Karten jedes Objekt o zu dem Satz von   Objekte nicht mehr unähnlich o als   d, für einige Unähnlichkeit Wert d.

Es könnte am schnellsten sein, nur die Ähnlichkeitsberechnung zu verlassen, wenn der Wert Ihres größer als d wird. Zum Beispiel, wenn Ihre Ähnlichkeiten auf Kosinus oder Hausdorff-Abständen basiert dies leicht getan werden kann.

PS: , wenn dies nicht getan werden kann, könnte Ihr Problem das k-nächsten Nachbarn Problem (oder genauer gesagt ein nächsten Nachbarn Problem mit einer Schwelle Nachbarschaft) bezogen werden. Sie sollten für Algorithmen suchen, die Nähe von Mitgliedern ohne alle Entfernungen Berechnung (vielleicht etwas Dreiecksungleichung verwenden). Wikipedia soll Ihnen helfen, geeignete Algorithmen zu erforschen.

Answer 3

Wenn Ihr Ähnlichkeitsmaß transitiv ist, Sie müssen nicht für alle Paare von Objekten, die Ähnlichkeit berechnen, da für Objekte a, b, c:

similarity(a,c) = similarity(a,b) op similarity(b,c)

wo op ist ein binärer Operator z.B. Multiplikation oder Addition.

Answer 4

Ich denke, die Lösung auf viel mehr Details über die Art des Problems ab.

1. Haben Sie oft ähnliche Objekte für das gleiche Objekt finden müssen, oder nur einmal? Wenn dann ist es oft, dann eine Datenstruktur schaffen, in dem Sie den Unterschied einmal für jedes Paar zu berechnen und dann Objekte zu ähnlichen Objekten verbinden, so dass Sie die Liste schnell und ohne Neuberechnung abrufen könnte eine sehr nützliche Leistungssteigerung sein.

2. Was ist die Natur der Berechnung? Auf dem einen Seite, wenn die Art des Unterschiedes ist, dass es zum Beispiel die Höhendifferenz zwischen zwei Menschen, dann die Liste nach Höhe sortiert beibehalten würden Sie die ähnlichen Objekte sehr schnell finden. Ich gehe davon aus dem eigentlichen Problem, als dass komplizierter ist, aber im Anschluss an dieser Logik, wenn die Differenz die Summe von mehreren linearen Mengen ist, könnten Sie einen Multi-dimenstional Array erstellen, und dann konzeptionell den Satz von ähnlichen Objekten wie jene vorstellen in einem n-dimensionalen Kugel (dh Kreis, Kugel, Hypershäre, etc) um das Referenzobjekt zentriert, und sie direkt wieder finden. Eigentlich ist es mir ein, dass, wenn der Radius Berechnungen zu kompliziert oder zu viel Lauf Zeit in Anspruch nehmen, eine gute Näherung wäre ein n-dimensionalen Würfel zu erstellen (dh Quadrat, Würfel, tesseract, etc.) um das Referenzobjekt, Abrufen aller Objekte, die innerhalb dieses Würfels als „Kandidaten“ liegen, und dann tun nur die tatsächliche Berechnung über die Kandidaten.

Beispiel: Angenommen, die „Differenz“ ist die Summe der absoluten Werte der Differenzen von drei Attributen, sagen a1, a2 und a3. Sie könnte ein 3-dimensionales Array erstellen und den Wert jedes Knotens des Arrays auf das Objekt mit diesen Werten, falls vorhanden. Dann, wenn Sie alle Objekte mit Differenz kleiner als d von Objekt o finden wollen, könnten Sie schreiben:

for (x1=o.a1-d;x1<o.a1+d;++x1)
{
  for (x2=o.a2-d;x1<o.a2+d;++x2)
  {
    for (x3=o.a3-d;x1<o.a3+d;++x3)
    {
      if (array[x1][x2][x3]!=null
        && (abs(x1-o.a1)+abs(x2-o.a2)+abs(x3-o.a3)<=d)
        {
          ... found a match ...
        }
    }
  }
}

Ich vermute, dass die Differenzregeln komplizierter sind als das, aber fein, fügen Sie einfach Raffinesse der alrorithm die Komplexität der Regeln anzupassen. Der Punkt ist, um das Array zu verwenden, um die Menge von Objekten zu begrenzen, die Sie zu untersuchen haben.

3. Wieder auf die Art der Berechnung: Wenn eines der Elemente, die die Differenz, oder eine kleine Untergruppe bilden, als andere an Bedeutung zu sein scheint, dann eine Datenstruktur erstellen, die Sie für diese innerhalb der Reichweite schnell zu vergleichen. Wenn es sich in Reichweite ist, tun vergleichen, die voll ist. Wenn nicht, dann suchen Sie nicht einmal daran.

Answer 5

Ist es nicht möglich, eine verwenden k d-Baum?

Es kann notwendig sein (wenn möglich), die Abmessungen zu normalisieren. Danach müssen Sie nur den Baum zu bevölkern, und verwenden Sie einen „nearest N Nachbarn“ suchen und versuchen, innerhalb eines gewissen Bereichs jedes Objekt zu finden.

Answer 6

Beispiel von Objekten: Bilder, Dokumente. Natürlich mit der rohen Darstellung dieser Objekte arbeiten, ist meist nicht sinnvoll. in der Regel würde man die Rohform und schalten Sie ihn in eine normalisierte Form (für Dokumente vorverarbeiten, sagen einen Vektor, für die jeder Eintrag die Anzahl / Prozent wie oft ein bestimmtes Wort für Bilder erschienen, stellt es eine Darstellung von visuellen Merkmalen könnte gefunden im Bild).

, wenn d festgelegt ist und eine n ^ 2 Pre-Berechnung ist möglich, könnten Sie nur eine Diagrammdarstellung verwenden, um eine verknüpfte Liste mit für jedes Objekt zum Beispiel. Sie können sich auf Kosten der Genauigkeit anhand annähernden nächsten Nachbarn Algorithmen effiziente Lösungen haben.

Answer 7

Können wir davon ausgehen, dass Ähnlichkeit transitiv ist, dh. diff(a,c) == diff(a,b) + diff(b,c)? Wenn ja, können Sie versuchen, die folgenden:

1. Sortieren Sie die Sammlung von Objekten. Wenn das Objekt Ahnlichkeitsmetrik keinen anständigen absoluten Wert haben, können Sie beliebig wählen Sie ein Objekt als „Null“ und sortieren alle anderen Objekte durch ihre Ähnlichkeit zu diesem Objekt.
2. Um die Objekte mit Ähnlichkeit s zu finden o, o in der sortierten Liste zu finden, und nach links und nach rechts suchen, bis der Unterschied wächst größer als s.

Der Vorteil hierbei ist, dass die Sortierung einmal getan werden kann, und nachfolgende Satz Gebäude ist auf die Anzahl der Mitglieder proportional, die in dem Satz sein wird.

Answer 8

Klingt wie BK-Baum. Hier ist eine kleine Beispiel . Sie erstellen im Grunde Baum und prüfen, welcher Zweig sollten für ähnliches Objekt suchen und welche nicht verwendet werden, so dass Sie verhindern O(n2)