Vektoren aus einer Distanzmatrix berechnen
Lars Dieterle
folgendes Problem: Es soll ein Clustering-Problem mit dem K-Means
Algorithmus gelöst werden. Da der K-Means Algorithmus aus der
Bildverarbeitung motiviert zu sein scheint funktioniert dieser Algorithmus
nur, wenn man Vektoren zu Verfügung hat. Gegeben ist bei der Problemstellung
allerdings nur eine Distanzmatrix, d.h. eine Tabelle in der die Abstände der
einzelnen Objekte zueinander eingetragen sind.
Beispiel mit drei Objekten:
Obj# | Obj# | Dist
-----|------|------
1 | 2 | 1
1 | 3 | sqrt(8)
2 | 3 | sqrt(5)
Wie und vor allem unter welchen Umständen ist es möglich daraus einen
"künstlichen" Vektorraum zu erzeugen. Die Distanzen dürfen (müssen sogar wg.
K-Means) als Euklidische Distanzen definiert werden. Die Definition für eine
Euklidische Metrik (Dreiecksungeleichung erfüllt, usw.) erspare ich mit an
dieser Stelle...
Das Ergebnis des Beispiels oben würde folgendermaßen aussehen:
- Es reicht wenn man einen zweidimensionalen Raum aufspannt, da sich drei
Elemente deren Abstände jeweils gegeben sind widerspruchsfrei in einem
zweidimensionalen Raum darstellen lassen. Frage: Kann man diese Ausage auf n
Elemente erweitern? Also bei n Elementen würde ein (n-1) dimensionaler Raum
benötigt werden, oder sehe ich das falsch? Ich brauche dazu keinen
mathematischen Beweis ich gebe mich mit einer anschaulichen Erklärung
zufrieden...
- Ergebnisse:
Obj1=[0 0]
Obj2=[1 0]
Obj3=[2 2]
Hinweis: das Beispiel wurde absichtlich so gewählt...
Beim Lösungsweg ist mir aufgefallen, daß ich bei Vorgabe des ersten Objekts
Obj1=[0 0] ein Gleichungssystem mit drei Gleichungen und vier unbekannten
erhalte.. Welche Information habe ich dabei übersehen?
Gibt es eine Funktion in Matlab, die aus einer Distanzmatrix
(Dissimilarity-Matrix) eine Matrix mit den "passenden" Vektoren liefert? Ich
suche Quasi eine inverse Funktion zu der Funktion "pdist" aus der
Statistical Toolbox.
Danke für Hilfe!
Gruß
Lars
--
Lars Dieterle EMail: lars.d...@gmx.de
Darmstadt, Germany ICQ: 62403219
Mit Humor kann man Frauen am leichtesten verführen, denn die meisten Frauen
lachen gerne, bevor sie anfangen zu küssen.
(Jerry Lewis, am. Komiker, 1926-)
Olaf Gerstung
> Gegeben ist bei der Problemstellung allerdings nur eine
> Distanzmatrix, d.h. eine Tabelle in der die Abstände der
> einzelnen Objekte zueinander eingetragen sind.
>
>
> Wie und vor allem unter welchen Umständen ist es möglich
> daraus einen "künstlichen" Vektorraum zu erzeugen.
Da ich vor kurzem vor einem ganz ähnlich gelagerten Problem
stand, kann ich dir vielleicht einen Tipp geben. Gegeben ist
also eine Distanzmatrix D mit euklidischen Abständen. Die
Idee ist, die PCA umzukehren. Die Abstände bleiben dabei
erhalten.
D wird nach D' transformiert, die die Eigenschaften einer
Kovarianzmatrix hat, und mit D' wird eine Eigenzerlegung
durchgeführt:
D' = E*L^2*E^T
L ist eine Diagonalmatrix mit den Wurzeln der Eigenwerte zu
D' (sortiert nach Betrag), E enthält die zugehörigen
Eigenvektoren als Spalten. E*L=:X ist eine Matrix mit den
gesuchten Vektoren als Zeilen. Bei der PCA würde man den
umgekehrten Weg gehen: Von X über D'=X*X^T und
Eigenzerlegung zu (im Vergleich zu den Spalten von X)
dimensionsreduzierten Vektoren. Von D' braucht man dann ja
nicht alle Eigenwerte-/vektoren zu berechnen, sondern nur
die ersten paar.
Wenn du nach Details suchst, traktiere doch mal Google mit
dem Stichwort "Principal Coordinate Analysis" (PCO) oder
"Multidimensional Scaling".
Wie man die Sache mit Matlab angeht, weiß ich nicht. Ich
habe 'newmat'[1] dafür verwendet.
Olaf