Punkte möglichst weit entfernt auf einer Ebene platzieren

[hoshbad]

Hallo,

ich habe eine Ebene und x Punkte (2-5).

Im ersten Schritt muss ich diese x Punkte möglichst weit voneinander entfernt platzieren.

Hier ein Beispiel, wie es aussehen müsste. http://sebastian.russ24.net/misc/uni/Punkte%20auf%20Ebene.jpg

Das könnte ich ja zur Not noch hart kodieren, aber schön wäre es dafür einen Algorithmus zu haben.

Hat da jemand eine Idee oder ein Stichwort für mich?

Dann gibt es noch eine Erweiterung. Es kommt ein neuer Punkt y hinzu und ich kenne alle Entfernungsrelation, also Abstand von y nach x1 ist 2 mal so groß wie nach x2, etc.

Da habe ich auch nicht wirklich eine Idee für

Wäre toll, wenn mir jemand helfen könnte. Danke im Voraus!

[Klotzkopp]

Was genau soll da maximiert werden? Wirklich nur die Summe der Abstände aller Punktepaare? Gibt es sonst keine Anforderungen?

Denn dein Beispiel für drei Punkte ist nach deiner Beschreibung nicht die Lösung.

Wenn man für die Fläche ein Quadrat der Seitenlänge 1 annimmt, hast du da als Gesamtabstand 1 + Wurzel(1,25) + Wurzel(1,25), was ungefähr 3,23 ist.

Wenn man die Punkte aber einfach in drei beliebige Ecken der Fläche setzt, kommt man schon auf 1 + 1 + Wurzel(2), ungefähr 3,41.

[flashpixx]

Hallo,

als mathematischer Ansatz würde ich dir die LaGrange Optimierung empfehlen. Du hast eine Funktion (Punkte auf Ebene), bei der Du die Extrema unter einer Nebenbedingung (maximale Distanz) suchst. Falls es rein um Projektion der Punkte geht, ließe sich auch eine Sammonsmap (wenn es nicht um exakte Darstellung) verwenden (Sammon ist generell für hochdimensionale Daten gedacht).

HTH Phil

Bearbeitet 29. Juli 2008 von flashpixx

[hoshbad]

Ja stimmt, die Abbildung für drei Punkte ist nicht ganz richtig.

Ich versuche es nochmal genauer zu beschreiben.

Problem 1 (nicht so wichtig, da hart-kodierbar)

Es gibt eine Menge x mit Punkten. Diese Punkte müssen äquidistant sein, wobei die Entfernung möglichst groß sein soll.

Problem 2

Zustand: Alle Punkte aus x sind verteilt.

Es gibt einen neuen Punkt y für den ich alle Entfernungsrelationen zu den Punkten aus x kenne.

Abstand von y nach x1 ist zwei mal so groß wie nach x2, usw.

[Klotzkopp]

Problem 1 (nicht so wichtig, da hart-kodierbar)

Es gibt eine Menge x mit Punkten. Diese Punkte müssen äquidistant sein, wobei die Entfernung möglichst groß sein soll.

Das ist für mehr als 3 Punkte nicht möglich. Du kannst beispielsweise 4 Punkte in der Ebene nicht so anordnen, dass alle den gleichen Abstand haben. Bei deiner vorgeschlagenen Anordnung (Quadrat) sind die jeweils gegenüberliegenden Punkte weiter voneinander entfernt als die direkten Nachbarn.

[hoshbad]

Hmm, stimmt.

Vielleicht ist das vernachlässigbar.

Ich umschreibe das Problem mal ein wenig.

Die Punkte der Menge x sind Prototypen mit gewissen Eigenschaften, wobei jede Eigenschaft nur durch einen Prototyp ausgeprägt wird.

Diese Prototypen sollen halt möglichst weit von einander entfernt werden, weil deren Eigenschaften halt disjunkt sind.

Steckt man nun ein neues Objekt in die Ebene, welches irgendeine Kombination von Eigenschaften haben kann, soll es entsprechend der Ausprägungen gescheit platziert werden.

[flashpixx]

@hoshbad: dem stimme ich eben auch so zu ;-)

@Klotzkopp: Die Aussage ist so nicht korrekt, denn es werden nur euklidische Distanzen betrachten. Lege ich eine andere Metrik zu Grunde, dann ist dies ohne weiteres auch möglich (Bsp geodäsische Distanzen). Generell ist dieses Problem aber wie @hoshbad auch formuliert hat ein Optimierungsproblem hier speziell im R^2, das man mit Hilfe des LaGrangeansatzes lösen kann. Ich persönlich würde aber zu einem prototypenbasierten Verfahren greifen, das man mit Hilfe einer Funktion optimiert, da aufgrund der gegebenen Punktmenge auch neue Punkte eingeordnet werden sollen, müssen sowohl die neuen, wie auch die alten entsprechend verschoben werden.

Das ganze Problem kann somit nicht zu Beginn vollständig gelöst werden. Man kann zu einer Anfangsmenge die maximalen Abstände berechnen, bei einem neuen Punkt muss die Berechnung iterativ wiederholt werden,um die Punkte innerhalb der Ebene zu verschieben.

Ein weiterer Ansatz: Jeden Punkt auf einen Hypercube des R^n (n = Punkteanzahl) der Kantenlänge 1 zu platzieren, wobei jeder Punkt nur in einer Dimension 1 und sonst 0 stehen hat. Diese Vektoren mit Hilfe von Sammon nach 2D bzw 3D zu plotten.

Phil

Bearbeitet 29. Juli 2008 von flashpixx

[Klotzkopp]

@Klotzkopp: Die Aussage ist so nicht korrekt, denn es werden nur euklidische Distanzen betrachten. Lege ich eine andere Metrik zu Grunde, dann ist dies ohne weiteres auch möglich (Bsp geodäsische Distanzen).

Ich hatte aus der Beschreibung und den Beispielen geschlossen, dass es hier in der Tat um den ganz gewöhnlichen euklidischen R^2 geht. Ansonsten könnte man die Punkte ja beliebig verteilen und dann einfach eine passende Metrik angeben.

Ich persönlich würde aber zu einem prototypenbasierten Verfahren greifen, das man mit Hilfe einer Funktion optimiert, da aufgrund der gegebenen Punktmenge auch neue Punkte eingeordnet werden sollen, müssen sowohl die neuen, wie auch die alten entsprechend verschoben werden.

Wenn ich das richtig verstanden habe, unterliegt der "Problem-2-Punkt" nicht der Äquidistanzbedingung, sondern muss nur entsprechend der Ausprägung seiner Eigenschaften positioniert werden.

[flashpixx]

Ich hatte aus der Beschreibung und den Beispielen geschlossen, dass es hier in der Tat um den ganz gewöhnlichen euklidischen R^2 geht. Ansonsten könnte man die Punkte ja beliebig verteilen und dann einfach eine passende Metrik angeben.

Ich bin auch von einer euklidischen Metrik ausgegangen, da im Orginalpost, dieses auch auf dem Bild zu sehen war.

Wenn ich das richtig verstanden habe, unterliegt der "Problem-2-Punkt" nicht der Äquidistanzbedingung, sondern muss nur entsprechend der Ausprägung seiner Eigenschaften positioniert werden.

ja, und hier wären die Eigenschaften eben die Positionen. Diverse VQ Verfahren kämen in Frage (z.B. RLVQ): Prototype Based Recognition of Splice Sites - Hammer, Strickert, Villmann (ResearchIndex)

Phil

[hoshbad]

Hallo ihr zwei,

zunächst mal vielen Dank für euren Einsatz.

Ich habe das wohl am Anfang unterschätzt und daher nicht genug Infos gegeben. Ich hole kurz einmal aus und erkläre dann meine momente Lösung, die ich heute mit einem Bekannten ertüfftelt habe.

Es gibt 2-5 Prototypen, welche disjunkte Eigenschaften haben. Aufgrund der Disjunktheit sollen diese "einfach möglichst weit" voneinander entfernt werden. Ich schreibe das bewusst in Anführungszeichen, weil es nicht um eine exakte Darstellung, sondern um eine Visualisierung als Orientierungshilfe gibt. Das genaue Ergebnis wird durch Zahlenwerte ausgegeben. (Die genaue Art und den Zweck meines Programms klammere ich mal aus).

Nachdem diese Prototypen platziert wurden, ist es möglich einen neuen Punkt zu definieren, welcher einige der Eigenschaften aufweist (auswählbar), wobei natürlich die Eigenschaften der Prototypen gemischt werden können, es kann also ein Punkt herauskommen, der einige Eigenschaften des einen und einige Eigenschaften des anderen Prototypen hat. Entsprechend dieser Ausprägungen muss der neue Punkt nun in Bezug auf die vorhandenen Prototypen platziert werden.

Beispiel:

Zwei Prototypen X1, X2, mit jeweils zwei Eigenschaften E1..E4.

X1 hat E1 und E2; X2 hat E3 und E4.

Nun erstelle ich einen neun Punkt mit E1, E2 und E4. Offensichtlich hat der neue Punkte zwei Eigenschaften von X1 und eine von X2, also sollte der neue Punkt auch deutlich näher (genauer Wert kann berechnet werden) bei X1 liegen.

Gelöst ist es nun folgendermaßen. Es wird ein maximales gleichseitiges n-Eck innerhalb der Ebene konstruiert, wobei n = Anzahl der Protoypen. Die direkten Nachbarpunkte des n-Ecks haben die gleiche Distanz voneinander. Das war es eigentlich. Natürlich gibt es da einen Informationsverlust, aber das ist ja nicht zu ändern.

Ein neuer Punkt wird dann als Linearkombination der vorhanden Vektoren (Prototypen) dargestellt und kann so eingezeichnet werden.

Ich weiß, dass mag nun nicht sehr einleuchtend klingen, weil ihr nicht konkrete Berechnung habt und auch nicht genau wisst, was da für Werte sind und so. Jedenfalls ist es vorerst gelöst, weil heute glücklicherweise mein Bekannter sich des Problems angenommen hat. Ich danke euch jedenfalls vielfach für eure Hinweise, auch wenn ich das nun nicht so umgesetzt habe.

Sobald ich das implementiert habe, kann ich gerne ein paar Screenshots posten und es noch genauer erklären. Falls ihr Bedarf habt.

Gute Nacht!

[flashpixx]

Hallo,

vielleicht zu Deiner generellen Problembeschreibung. Es ist immer hilfreich, wenn man alle Informationen zur Verfügung hat. Desweiteren ist meiner Ansicht nach, eine Interpolation des neuen Punktes zwischen bestehenden Prototypen nicht die Lösung, denn in dem Originalpost sagst Du, dass alle Punkte möglichst weit von einander entfernt sein sollen (Bild). Mit der Interpolation gilt dies nicht. In Deinem Fall besitzt Du n Prototypen, zu denen Du einen neuen Punkt klassifizierst, in dem linear interpolierst. Der neue Punkt liegt oder liegt nicht innerhalb eines rezeptiven Feldes und er wird nicht anhand seiner Eigenschaften zugeordnet.

Was willst Du überhaupt erreichen? Willst Du überwacht/unüberwacht klassifizieren oder eine Regression haben? Dann verwende z.B. eine Vektorquantisierung oder LazyLearning mit entsprechenden Weightening.

Oder willst Du visualisieren? Dann kombiniere ein Lernverfahren mit einer entsprechenden Visualisierung

Du sprichst von 2-5 Prototypen mit disjunkten Eigenschaften, aber jeder Prototyp hat 2 Dimensionen nach Deiner Ausführung. Dies widerspricht sich, denn im R^n können n+1 Vektoren nicht linear unabhängig sein, somit nicht disjunkt.

Eine Vektorquantisierung basiert auf Datenpunkten und ermittelt aus diesen die Prototypen, d.h. Du hast zu Beginn keine Prototypen und sie werden Dir geliefert, anhand einer Funktion liegen diese Prototypen max. auseinander. Neue Datenpunkte werden dann anhand der sich aufspannenden rezeptiven Felder klassifiziert (analog zum LazyLearning).

Wenns Dir um eine Visualisierung geht und Deine Prototypen bekannt sind, warum verwendest Du dann nicht ebenfalls ein Lernverfahren und eine Visualisierung? Bei Deinen bekannten Prototypen kannst Du, wie schon erwähnt, die Einheitsvektoren Deines R^n nehmen (Skalierung Deiner Datenmenge auf [0,1] im Hypercube). Da jeder Basisvektor linear unabhängig ist, sind die Ecken Deines Cubes symbolisch Deine Prototypen, die disjunkt sind. Mit LazyLearning oder auch Interpolation kannst Du Deine neuen Punkte in den Cube einfügen ("klassifizieren") und projizierst diesen nun mit Hilfe eine PCA, ICA, LDA (alle 3 linear) oder LLE (nicht linear) in 2D oder 3D?

So wie ich im Moment das sehe, trennst Du die Darstellung Deiner Daten nicht von der Problemlösung. Du willst eine Visualisierung in 2D und beschränkst die Problemlösung auf dieses. Auf der einen Seite sprichst Du von Ausprägungen Deiner Prototypen, die im Grunde mit der Darstellung nichts zu tun haben (die Ausprägungen können sowohl symbolisch wie auch reel sein), verwendest aber die Visualisierung (n-Eck), um Deine Daten (Prototypen) innerhalb des Raumes maximal entfernt anzuordnen.

Zu der Konstruktion über ein n-Eck: Konstruierbare Polygone ? Wikipedia

Phil

[hoshbad]

Hallo Phil,

danke für deinen umfassenden Beitrag, ich werde mal versuchen punktuell darauf einzugehen.

vielleicht zu Deiner generellen Problembeschreibung. Es ist immer hilfreich, wenn man alle Informationen zur Verfügung hat.

Full ack. Ich habe wohl einfach das Problem unterschätzt und dachte, es sei (für die Problemlösung) hinlänglich beschrieben. Aber ohne mein Ziel zu kennen, ist es wohl doch nicht so einfach, weil es vielleicht sogar einen besseren grundlegenden Ansatz gibt, um mein Ziel zu erreichen.

Desweiteren ist meiner Ansicht nach, eine Interpolation des neuen Punktes zwischen bestehenden Prototypen nicht die Lösung, denn in dem Originalpost sagst Du, dass alle Punkte möglichst weit von einander entfernt sein sollen (Bild). Mit der Interpolation gilt dies nicht.

Die Prototypen sollen zu Anfang möglichst weit voneinander entfernt sein. Die Punkte halt gemäß ihrer Ausprägungen. Ist mein neuer Ansatz eine Interpolation? Wüsste nicht warum. Hier mal ein vollständiges Beispiel:

Es gibt 2 Prototypen und 6 Eigenschaften.

Prototyp Mann Xm: Eigenschaften: (1, 1, 1, 0, 0, 0), Koordinate in der Ebene: 100, 0

Prototyp Frau Xf: Eigenschaften: (0, 0, 0, 1, 1, 1), Koordinate in der Ebene: 0, 100

Neuer Punkt C: (0.1, 0.2, 0.3, 0.4, 0.5, 0.6)

C * Xm = 0.6

C * Xf = 1.5

Offensichtlich ist der neue Vektor der Frau deutlich näher als dem Mann.

Nomierung der Summe auf 1 (Rundensfehler egal). Der neue Vektor würde ohne Normierung bereits in die richtige Richtung zeigen, aber viel zu lang sein, daher die Normierung:

0.6 / 2.1 = 0.288

1.5 / 2.1 = 0.714

Nun summiere ich die Produkte der Prototyp-Punkte mit dem Ergebnis aus (C * Xx).

Vmann = (100, 0) * 0.288 = (28.8, 0)

Vfrau = (0, 100) * 0.714 = (0, 71.4)

Koordinaten C = Vmann + Vfrau = (28.8, 71.4)

Fertig. Der neue Punkt liegt also deutlich näher bei der Frau, was gemäß der Ausprägungen richtig ist.

In Deinem Fall besitzt Du n Prototypen, zu denen Du einen neuen Punkt klassifizierst, in dem linear interpolierst. Der neue Punkt liegt oder liegt nicht innerhalb eines rezeptiven Feldes und er wird nicht anhand seiner Eigenschaften zugeordnet.

Hmm, da muss ich passen, ich studiere weder Mathe, noch reine Informatik und komme da gerade nicht hinterher Rezeptives Feld? Warum wird er nicht anhand der Eigenschaften zugeordnet? VIelleicht nur ein Missverständis, weil ich gestern Nacht nicht alles genau beschrieben habe?

Was willst Du überhaupt erreichen? Willst Du überwacht/unüberwacht klassifizieren oder eine Regression haben? Dann verwende z.B. eine Vektorquantisierung oder LazyLearning mit entsprechenden Weightening.

Oder willst Du visualisieren? Dann kombiniere ein Lernverfahren mit einer entsprechenden Visualisierung

Es geht um Klassifizierung. Die Prototypen sind vorgegeben und ein neuer Eingabevektor wird gemäß seiner Eigenschaften bewertet. Es wird also für jeden vorhanden Prototypen ein Ähnlichkeitswert errechnet (das ist auch schon alles implementiert). Nach dem ein gewisses Verfahren also ausgeführt wurde, weiß ich, wie groß die Ähnlichkeit meines Eingabevektors zu jedem einzelnen Prototypen ist. Die Werte sind exakt und können folglich interpretiert werden. Ziel ist es nun eine *ungefähre* Visualisierung dessen zu erreichen. Man soll also auf Anhieb *grafisch* sehen können, wie ähnlich ein Eingabevektor den vorhandenen Prototypen ist,

Du sprichst von 2-5 Prototypen mit disjunkten Eigenschaften, aber jeder Prototyp hat 2 Dimensionen nach Deiner Ausführung. Dies widerspricht sich, denn im R^n können n+1 Vektoren nicht linear unabhängig sein, somit nicht disjunkt.

Entschuldige, da kommt mein mathematischer Wissensmangel erneut zum Tragen. Warum hat jeder Prototyp nur 2 Dimensionen? Dass es im R^n nur n linear unabhängig Vektoren gibt, ist mir noch aus einer Mathevorlesung bekannt.

P1 = (1, 0, 0)

P2 = (0, 1, 0)

P3 = (0, 0, 1)

Die sind doch disjunkt, oder nicht?

Eine Vektorquantisierung basiert auf Datenpunkten und ermittelt aus diesen die Prototypen, d.h. Du hast zu Beginn keine Prototypen und sie werden Dir geliefert, anhand einer Funktion liegen diese Prototypen max. auseinander. Neue Datenpunkte werden dann anhand der sich aufspannenden rezeptiven Felder klassifiziert (analog zum LazyLearning).

Erm...

Wenns Dir um eine Visualisierung geht und Deine Prototypen bekannt sind, warum verwendest Du dann nicht ebenfalls ein Lernverfahren und eine Visualisierung? Bei Deinen bekannten Prototypen kannst Du, wie schon erwähnt, die Einheitsvektoren Deines R^n nehmen (Skalierung Deiner Datenmenge auf [0,1] im Hypercube). Da jeder Basisvektor linear unabhängig ist, sind die Ecken Deines Cubes symbolisch Deine Prototypen, die disjunkt sind. Mit LazyLearning oder auch Interpolation kannst Du Deine neuen Punkte in den Cube einfügen ("klassifizieren") und projizierst diesen nun mit Hilfe eine PCA, ICA, LDA (alle 3 linear) oder LLE (nicht linear) in 2D oder 3D?

Das hört sich alles unheimlich spannend an, das mit dem Cube kann ich auch noch nachvollziehen, aber den Rest leider nicht. PCA, ICA, LDA? Ich habe gerade mal gegoogelt und geschaut. Sieht alles ganz schön mächtig aus, für einen nicht-Mathematiker Gibt es denn mit meinem aktuellen Verfahren ein Problem? Es ist ja schon recht simpel.

So wie ich im Moment das sehe, trennst Du die Darstellung Deiner Daten nicht von der Problemlösung. Du willst eine Visualisierung in 2D und beschränkst die Problemlösung auf dieses. Auf der einen Seite sprichst Du von Ausprägungen Deiner Prototypen, die im Grunde mit der Darstellung nichts zu tun haben (die Ausprägungen können sowohl symbolisch wie auch reel sein), verwendest aber die Visualisierung (n-Eck), um Deine Daten (Prototypen) innerhalb des Raumes maximal entfernt anzuordnen.

Puh, moment. Ich sehe das Problem nicht. Ich errechne also diese Ähnlichkeitswerte für einen Eingabevektor zu den Prototypen. Punkt, mehr erst mal nicht. Und das möchte ich dann einfach nur in 2D visualisieren, wie oben geschrieben.

Zu der Konstruktion über ein n-Eck: Konstruierbare Polygone ? Wikipedia

Das funktioniert gerade folgendermaßen:

function y = n_eck(n, dim_y)

	mittelpunkt = [ 1 1 ] * dim_y / 2

	radius = dim_y / 2;

	y = [ ];

	for i = 0:(n - 1)

		v = mittelpunkt - radius * [ cos(2 * pi * i / n)  ,  sin(2 * pi * i / n) ];

		y = [y; v];

	endfor

endfunction

Wobei n die Anzahl der Ecken ist und dim_y die Größe meiner Fläche.

Noch mal ein Schlußwort. Ich freue mich über deine Antworten, finde das auch sehr spannend und versuche daraufhin immer was nachzulesen, aber prinzipiell kann ich nicht auf dem hohen mathematischen Niveau mitdiskutieren, wie gesagt, bin weder Mathematiker noch Informatiker (oder Physiker). Dass ich oben nicht auf alles von dir eingegangen bin liegt also nicht in mangelnder Lust ;-)