Aus großer Menge von vieldimensionalen Vektoren die ähnlichsten finden

Hallo Community,

wie kann man aus einer großen Menge von vieldimensionalen Vektoren effizient die zu einem vorgegebenen Vektor ähnlichsten finden?

Jeder Vektor steht für ein Dokument. Nehmen wir an, jeder Vektor hat 100 Elemente, die Werte zwischen jeweils 0 und 100 annehmen können und die das Dokument bzw. seine Eigenschaften beschreiben. Der Abstand der Vektoren v = (v1, v2, ..., v100) und w = (w1, w2, ..., w100) ergibt sich aus der Summe der Quadrate der Differenzen der Werte, also

Summe i = 1 bis 100 von (v_i-w_i)²

Je kleiner der Abstand, desto ähnlicher sind sich die Vektoren.

Ich habe leider auch keine passenden Stellen im Web gefunden, obwohl ich eigentlich davon ausgehe, dass dies eins der Standardprobleme des Information Retrievals sein müsste. Ich weiß leider auch nicht, ob es für das Problem einen festen Namen gibt.

Für Anregungen, Stichworte oder Verweise wäre ich daher dankbar.

herbivore

Hi herbivore,

im 2D-Bereich gibt es für solche Zwecke den QuadTree, im 3D-Bereich den Octree. Mit höheren Dimensionen kenne ich mich nicht aus, aber ich könnte mir vorstellen, daß BSP (Binary Space Partition) auch für beliebig hohe Dimensionen funktioniert.

Christian

Hallo MrSparkle,

leider habe ich recht viele Dimensionen, weshalb Quadtrees und Octrees ausscheiden. Auch die Generalisierung BSP nützt mir m.E. nichts oder ich übersehe was. Denn irgendwo muss man die Hyperebene ja ziehen und egal wo man sie zieht, kann es sein, dass der vorgegebene Vektor in ihrer Nähe liegt. Dann nützt aber die Segmentierung nichts, weil man dann eben doch beide Teilbäume durchlaufen muss. Und selbst wenn er relativ weit weg von den ersten Hyperebenen liegt, kann es wegen der vielen Dimensionen auf beiden Seiten der Hyperebenen trotzdem relativ ähnliche Vektoren geben.

Der Vektor 0, 0, 0, 50, ... 50 ist bei vielen Dimensionen einem Vektor 100, 100, 100, 50, ... 50 trotzdem sehr ähnlich.

Nehmen wir an, ich würde die erste Hyperebene so ziehen, dass sie den Hyperraum so teilt, dass Vektoren mit einem Wert der ersten Komponente kleiner gleich 50 auf der einen Seite und welche mit einem Wert größer 50 auf der anderen Seite landen, und die zweite Hyperebene analog eben für die zweite Komponente usw. Dann hätte ich das gleiche Problem wie es oben schon für die Teilung in 101 Segmente beschrieben habe: Ein ähnlicher Vektor kann sich in den ersten Komponenten trotzdem beliebig stark unterscheiden, so dass ich immer beide Seiten untersuchen muss. Oder übersehe ich da was?

Gibt es noch andere Ansätze, Datenstrukturen oder Algorithmen?

herbivore

Hallo,

Für Anregungen, Stichworte oder Verweise wäre ich daher dankbar.

"support vector machines similarity search" wäre vielleicht ein Ansatzpunkt. Erfahrung oder tiefer gehendes Wissen habe ich allerdings nicht.

Hi herbivore,

verstehe, so einfach wie ich mir das vorgestellt hatte, ist das nicht.

Letztendlich würdest du ja bei einer naiven Herangehensweise den gegeben Vektor mit jedem Vektor deiner Auflistung vergleichen, das wäre ein O(n)-Vorgang. Oder O(n*m) für m Komponenten.

Bei einem (Quad-, Oc- oder in deinem Fall N-) Tree könnte man Bereichsabfragen mit wesentlich weniger Aufwand durchführen. Aber Abfragen wie "finde die umliegenden Vektoren" oder "finde den nächstliegenden Vektor", sind doch etwas aufwändiger, als ich zuerst eingeschätzt hab.

Eine einfache Optimierung, die auch im 2D- oder 3D-Bereich Anwendung findet, wäre die Erstellung eines Indizes für jede Vektor-Komponente. D.h. man sortiert alle Vektoren nach ihre X-, Y-, Z- .... N-Komponente und kann dann für einen gegeben Wert einer Komponente die umliegenden Punkte mittels Binary-Search in O(n log n) finden. Das Erstellen der Indizes hat auch einen Aufwand von O(n log n) bzw. O(m(n log n)) für Vektoren mit m Komponenten.

Christian

Vielleicht kannman was mit einer ZuordnungsProblemlösung reißen.

Irgendwie kommen mir die vielen Vektoren vor wie die 4 Kinder, die sich um die 4 Spielzeuge streiten, und es gilt nun, diejenige Zuordnungs-Kombination zu finden, bei insgesamt die höchste Präferenz-Zahl auftritt.

Aber durchdacht und ob das für den Fall der Vektoren geht habichdas noch nicht.

Also ich bin mehr Praktiker als Theoretiker deswegen würde ich versuchen eine Art Meta-Struktur anzulegen, natürlich als Baum, inwiefern (binär) balanciert lasse ich dabei gerne mal aussen vor. Was du uns nicht sagst ist ob es auf den Namen oder den Inhalt der Dokuments ankommt. Soweit ich es verstehe, geht es um Ähnlichkeiten. Die Regel für diese Ähnlichkeit zu definieren ist der Schlüssel zum Glück. Wenn ich davon ausgehe das der Name des Dokuments die Ähnlichkeit bildet kann ich indizierende Wege in Form eines Baumes vorbereiten, eben eine Meta Struktur, nennen wir sie Kategorien. Diese könnten bestehen aus einer selbstlernden Struktur von Wörtern(eignet sich erst ab eine grossen Datenmenge die ich als gegeben betrachte) der andere Weg bildet sich individuell aus Wortlisten, Anzahl vorkommender Substantive und allem was die Textsuche für einen findigen Programmierer hergibt. Einige Prinzipien der Fuzzy Logik würden hier greifen.

@Herbivore
Die Struktur deiner Daten selbst muss so vorbereitet sein das die Suche nach Ähnlichkeiten simpel ist. Soweit ich es verstanden suchst du nach einer "nachträglichen" Lösung in der Suche und da wirst du immer für bezahlen.

Hallo zusammen,

schon mal vielen Dank für die bisherigen Antworten, auch wenn mir damit ein Durchbruch leider noch nicht gelungen ist.

Hallo ujr,

ich habe bisher leider nur die Zeit gefunden, mir die "support vector machines" anzuschauen und ich denke, die habe ich soweit auch verstanden. Diese helfen mir dabei, die trennenden Hyperebenen möglichst so zu wählen, dass deren minimaler Abstand zu den Punkten möglichst groß wird. Allerdings greift hier, was ich schon auf MrSparkle erwidert habe. Selbst bei maximalem Abstand von einer Hyperebene können die Vektoren sich wegen der großen Anzahl von Dimensionen immer noch sehr ähnlich sein. Deshalb ist meine Vermutung, dass selbst ein optimale Wahl von Hyperebenen nicht hilft.

Allerdings hatte noch keine Zeit mich durch die Dokumente nach "support vector machines similarity search" zu wühlen. Vielleicht stoße ich da noch auf was brauchbares.

Hallo MrSparkle,

der lineare Vergleich scheidet aus, weil es um sehr viele Dokumente geht (momentan Millionen, theoretisch aber auch Milliarden oder mehr) in Kombination mit vielen Anfragen (mindestens zehntausende) geht. Deshalb hatte ich schon darauf gehofft, dass es sowas ähnliches wie binäre Suche gibt, also irgendwas mit Aufwand O(log(n)) oder so. Allerdings sehe ich noch nicht, wie mir das Sortieren der Werte innerhalb der Vektoren dabei helfen soll. Wenn ich mein Beispiel von oben nehme, würde aus 0, 0, 0, 50, ... 50 und 100, 100, 100, 50, ... 50 durch Sortieren 0, 0, 0, 50, ... 50 und 50, ... 50, 100, 100, 100. Das würde die Differenz auf den ersten Komponenten lediglich von 100 auf 50 reduzieren. Die an sich ähnlichen Vektoren würden also immer noch an sehr unterschiedlichen Stellen eingeordnet werden, obwohl sie sich sehr ähnlich sind. Habe ich dich falsch verstanden? Oder kannst du nochmal genauer ausführen, inwiefern das Sortieren der Werte innerhalb der Vektoren etwas bringen würde?

Hallo ErfinderDesRades,

das Zuordnungsproblem geht von zwei gleich großen Mengen aus, deren Elemente paarweise zugeordnet so werden sollen, dass - bezogen auf meinen Fall - die Summe der Abstände minimal werden würden. Da kann ich zumindest auf den ersten Blick noch nicht erkennen, wie mir das bei der Zuordnung von einem einzelnen Vektor zu einer (potenziell) kleinen Menge von ähnlichen Vektoren aus einer sehr großen Menge von Vektoren helfen würde. Wenn du da eine konkrete Idee hast, lass es mich bitte wissen.

Hallo Sebastian.Lange,

doch, ich habe genaue beschrieben, worauf es ankommt. 😃 Zu jedem Dokument gibt es einen Vektor. Das ist das einzige was zählt. Der Name und der Inhalt des Dokuments ist ansonsten egal. Ich habe auch genau die Ähnlichkeitsrelation zwischen den Vektoren definiert. Da weder der Name des Dokuments noch die enthaltenen Worte eine Rolle spielen, helfen leider auch keine derartigen Kategorien oder Wortlisten. Es geht ohnehin nicht um Text-Dokumente, sondern um enthaltene graphische Features, die unterschiedliche stark ausgeprägt sein können, was zu den genannten Vektoren führt.

Und nein, ich suche nicht nach einer nachträglichen Lösung, sondern tatsächlich gerade nach einer Datenstruktur, in der die Suche nach Ähnlichkeiten simpel ist.

herbivore

nächste idee:

die vektoren kriegen ihre nähe-bewertung und den grad ihrer Abarbeitung beigeordnet, und kommen auf einen Heap. und da bearbeitet man immer den obersten, und reheapt den dann.

bei sehr vielen sehr langen und sehr unterschiedlichen vektoren würdedas die bearbeitung sehr vieler, die sich bereits früh als sehr entfernt erweisen, deutlich zurückstellen.

leider ist die ermittlung der distanz so sehr performant, dass die pflege des Heaps auch deutlich ins gewicht fällt.

(mein gott, wieviele "sehr" enthält dieser post 😉)

Hallo zusammen,

ich denke, ich habe nun die richtigen Stichworte gefunden:

Nearest neighbor search in Kombination mit Curse of dimensionality.

Dort habe ich zunächst bestätigt gefunden, was ich oben (z.B. im Zusammenhang mit den Hyperebenen bzw. mit jeder Art von Segmentierung) als Problem der ganzen Geschichte benannt habe:

The [curse of dimensionality] effect complicates nearest neighbor search in high dimensional space. It is not possible to quickly reject candidates by using the difference in one coordinate as a lower bound for a distance based on all the dimensions.

Und auch möglicherweise einen Hinweis darauf, dass ich nach etwas aussichtslosem gesucht habe:

Surprisingly, naive [linear] search outperforms space partitioning approaches on higher dimensional spaces.

Anderseits werden auch verschiedene Ansätze genannt, um das Problem zu lösen. Ich bin darüber jetzt auf jede Menge PDF-Dokumente gestoßen, die ich erstmal in Ruhe durcharbeiten muss.

Ich melde mich wieder, sollte ich eine brauchbare Lösung finden oder nochmal eure Hilfe benötigen. Vielen Dank bis hier hin.

herbivore

Hi herbivore,

ein sehr interessantes Thema, finde ich.

Oder kannst du nochmal genauer ausführen, inwiefern das Sortieren der Werte innerhalb der Vektoren etwas bringen würde?

Es sollte die Laufzeit von konstant auf logarithmisch verringern. Dadurch, daß du die Vektoren anhand ihrer einzelnen Komponenten sortierst, kannst du sie mit einem Aufwand von O(n log n) durchsuchen. Das ist das gleiche Prinzip, das sich auch die BSP, k-d Trees oder R-Trees zunutze machen. Allerdings bringt das auch nur etwas, wenn die Daten halbwegs zufällig verteilt sind, was bei deinen nicht der Fall zu sein scheint.

Den Hinweis, daß eine naive (lineare) Suche in den meisten Fällen wesentlich schneller ist, als irgendwelche Datenstrukturen aufzubauen, kann ich übrigens aus der Praxis bestätigen. Ich hab es zwar bisher nur 2D-Vektoren und Quad-Trees ausprobieren können, aber da war eine naive Suche auch bei Millionen von Punkten schneller.

Eine sehr wirkungsvolle Optimierung, die allerdings oft einfach übersehen wird, ist da das Weglassen der Quadratwurzel bei der Berechnung der Vektoren-Abstände. Man kann die Vergleiche genausogut mit den Quadraten durchführen und spart sich ein Wurzelziehen pro Vektor.

Christian

Hast du denn Einfluss darauf wie die Daten strukturiert sind? Nur nochmal als Anmerkung. Typische Baumstrukturen scheitern hier natürlich aufgrund mangelnder Perfektion.(Klar, hast du daran gedacht aber nur für die Diskussion...) Ich versuche, wie viele andere auch, von hintenzu denken. Wie werde ich am schnellsten gefunden, also wie kann ich mich einsortieren um am schnellsten entdeckt zu werden? Das Ergebniss führt für mich nicht über die Suche selbst sondern wie schon gesagt über die Meta-Suche. Anders esagt, nur der letzte Baum ist die echte Suche, alle Ebenen davor führen über eine Meta Suche also Enititäten die ein Dokument üer sich selbst ablegt, Länge, Stichwörter usw. Möglicherweise ist damit Hyperebene gemeint(Ich weiss leider nicht was das heisst)

Hallo MrSparkle,

Eine sehr wirkungsvolle Optimierung, die allerdings oft einfach übersehen wird, ist da das Weglassen der Quadratwurzel bei der Berechnung der Vektoren-Abstände.

wie man oben sieht, hatte ich das bei meiner Abstandsdefinition im Startbeitrag auch so gemacht. 😃 Und solange man nur wissen will, ob ein Abstand größer/kleiner/gleich ist als ein anderer oder ob ein Abstand größer/kleiner/gleich ist als ein bestimmter Schwellwert, klappt das auch. Allerdings habe ich bei meiner Recherche erfahren dass die Dreiecksungleichung (Triangle inequality) erfüllt sein muss, wenn man einen Metrischen Raum definieren will. Die Dreiecksungleichung ist jedoch nur erfüllt, wenn man die Quadratwurzel zieht. Und dass der Raum metrisch ist, ist wiederum für einige der Algorithmen und Datenstrukturen erforderlich. (Das "metrisch" in "metrischer Raum" hat übrigens nichts damit zu tun, dass Entfernungsangaben etwa in Meter angegeben würden, sondern alleine etwas mit bestimmten festgelegten mathematischen Eigenschaften des Raums.)

Hallo zusammen,

ansonsten laufen alle Datenstrukturen und Algorithmen, die ich bisher ausgehend vom Kernproblem Nearest neighbor search gefunden habe, auf ein Branch-and-Bound hinaus. Die Vektoren werden also in einen (meist binären) Baum eingetragen, wobei in unterschiedlicher Weise festgelegt wird, in welchen Teilbaum welcher Vektor eingetragen wird. Die verschiedenen Bäumen unterscheiden sich hauptsächlich in dem Kriterium, das verwendet wird, um zu entscheiden, in welchen Teilbaum welcher Vektor gehört.

Da sind zum einen die schon genannten Hyperebenen, die den (Hyper-)Raum in (jeweils) zwei Teile teilen. Diese werden manchmal dadurch gezogen, dass man sich eine einzelne Dimension schnappt, einen Schwellwert festlegt und alle Vektoren, die in dieser Dimension über dem Schwellwert liegen, in den einen und alle anderen in den anderen Teilbaum einsortiert. Auf der nächst tieferen Ebene beginnt man das Spiel üblicherweise mit der nächsten Dimension von neuem. Das ist das Prinzip von Kd-trees.

Man kann eine Hyperebene aber auch dadurch definieren, dass man sich zwei (oder mehr) Vektoren ausguckt (quasi als Prototypen) und die Vektoren immer in den Teilbaum einsortiert, zu dessen ausgegucktem Vektor sie die geringere Entfernung haben. Das Prinzip das dahinter steckt, ist also so ähnlich, wie das beim Voronoi diagram.

Bei Vp-tree guckt man sich dagegen nur einen Vektor und einen Schwellwert aus und packt alle Vektoren, deren Abstand zu dem ausgegucken Vektor geringer sind als der Schwellwert, in den einen und die anderen in den anderen Teilbaum.

Wie man sieht, wird der Raum manchmal in (Hyper-)Quader und manchmal in (Hyper-)Kugeln unterteilt. Dabei gibt bei steigender Dimensionalität einen interessanten Effekt: Das Verhältnis des Volumes einer in einen Hyperwürfel eingeschriebenen Hyperkugel im Vergleich zum Volumen den Hyperwürfels geht gegen 0. Das sagt allerdings nicht direkt etwas darüber aus, ob Hyperkugeln oder Hyperwürfel besser geeignet sind, um dem Raum zu unterteilen. Ich fand es nur interessant. Und wenn man sich mal in Ruhe überlegt, warum das so ist, bekommt man einen ganz interessanten Einblick in hochdimensionale Räume (Tipp: Bei wenigen Dimensionen anfangen und überlegen, was passiert, wenn man immer eine weitere Dimension hinzufügt. Außerdem bei mehr als drei Dimensionen Projektionen auf drei oder weniger Dimensionen verwenden - so wie man einen dreidimensionalen Würfel auch als zweidimensionale Projektion auf ein Blatt Papier zeichnen kann).

Kommen wir jetzt zur Suche in diesen Bäumen. Das Problem dabei ist - wie schon oben gesagt - dass man in vielen Fällen nicht unmittelbar entscheiden kann, in welchem Teilbaum sich der nächste Nachbar eines vorgegebenen Vektors befindet (das gilt insbesondere, wenn man keine Vorgabe machen kann, wie weit der nächste Nachbar vom vorgegebenen Vektor entfernt sein darf), sondern, dass man oft beide Teilbäume durchsuchen muss, wodurch der Aufwand sich von O(log(n)) wieder in Richtung O(n) verschiebt und - wie weiter schon angesprochen - dabei von der realen Laufzeit gesehen sogar größer werden kann als bei einer einfachen linearen Suche.

Wenn man sich nicht für den absoluten nächsten Nachbarn interessiert, sondern es reicht, wenn man einen Nachbarn findet, der - im Vergleich absoluten nächsten Nachbarn - nicht viel weiter weg ist, kann man die Best bin first Strategie verwenden, also immer zuerst bzw. nur die Teilbäume durchsuchen, in denen man am wahrscheinlichsten den nächsten Nachbarn findet.

Bevor man jedoch anfängt, sich über die beste Suchstrategie Gedanken zu machen, sollte man versuchen, das eigentliche Übel, nämlich den Fluch der Dimensionalität (Curse of dimensionality) an der Wurzel zu packen. Dabei kann die Principal component analysis helfen, mit der man die Anzahl der Dimensionen verringern kann, wenn mehrere Dimensionen mehr oder weniger redundant zueinander sind.

Es gibt auch noch andere Möglichkeiten. Wenn man z.B. vergleichen will, ob zwei Bilder pixelweise ähnlich zueinander sind (und die Folge von (Sub-)Pixeln des Bildes kann man ja als hochdimensionalen Vektor betrachten), kann man zuerst die Differenz der durchschnittliche Helligkeit der beiden Bilder berechnen und wenn diese schon zu groß ist, kann man sich den Vergleich auf der Pixelebene sparen.

Das lässt sich natürlich auch allgemein auf Vektoren übertragen. Wenn man den Durchschnittswert aller Werte des Vektors berechnet, bekommt man eine einzige Dimension, für die man schnell feststellen kann, welche anderen Vektoren hinsichtlich dieser Dimension überhaupt nah genug sind, damit noch eine Ähnlichkeit besteht. So kann man in einem Schritt schnell sehr viele Vektoren vorab von einem genaueren Vergleich ausklammern (denn nach der einzelnen Dimension lassen sich alle Vektoren leicht sortieren und mit binärer Suche lässt sich schnell der Bereich ermitteln, der überhaupt durchsucht werden muss).

Das ist so ungefähr mein Stand. Um den Rahmen nicht zu sprengen, habe ich mich auf die wesentlichen Erkenntnisse beschränkt. Wenn man sich auf das Thema wirklich einlässt, kann man in beliebige Tiefen abtauchen.

Fazit: Ich bin nach meiner bisherigen Recherche darin bestätigt worden, dass es keine Datenstruktur gibt, die das im Startbeitrag beschriebene Problem vollständig löst. Bei hoher Dimensionalität kann sogar das einfach lineare Durchsuchen aller Vektoren die schnellste Lösung sein. Trotzdem gibt es eine ganze Anzahl von Ansätzen, mit denen man die Suche in bestimmten Fällen oder bei Inkaufnahme von kleinen Ungenauigkeiten beschleunigen kann. Welche sich davon am besten für mein konkretes Problem eignen, muss ich noch ausprobieren. Trotzdem bin ich gewillt, das Problem vorerst als gelöst anzusehen. Vielen Dank für eure Beiträge dazu.

herbivore