Umwandlung der Ähnlichkeitsmatrix in eine (euklidische) Distanzmatrix

27

In Random Forest-Algorithmus erstellt Breiman (Autor) eine Ähnlichkeitsmatrix wie folgt:

  1. Senden Sie alle Lernbeispiele an jeden Baum im Wald

  2. Wenn zwei Beispiele im selben Blatt landen, erhöhen Sie das entsprechende Element in der Ähnlichkeitsmatrix um 1

  3. Normalisieren Sie die Matrix mit der Anzahl der Bäume

Er sagt:

Die Ähnlichkeiten zwischen den Fällen n und k bilden eine Matrix {prox (n, k)}. Aus ihrer Definition ist leicht zu ersehen, dass diese Matrix symmetrisch, positiv bestimmt und oben durch 1 begrenzt ist, wobei die diagonalen Elemente gleich 1 sind. Daraus folgt, dass die Werte 1-prox (n, k) quadratische Abstände in einem Euklidischen sind Raum der Dimension nicht größer als die Anzahl der Fälle. Quelle

In seiner Implementierung verwendet er sqrt (1-prox) , wobei prox eine Ähnlichkeitsmatrix ist, um sie in eine Distanzmatrix umzuwandeln. Ich denke, es hat etwas mit den oben zitierten "quadratischen Abständen in einem euklidischen Raum" zu tun.

Kann jemand ein bisschen Licht ins Dunkel bringen, warum 1-prox quadratische Abstände in einem euklidischen Raum sind und warum er Quadratwurzel verwendet, um eine Abstandsmatrix zu erhalten?

Uros K
quelle

Antworten:

30

Bildbeschreibung hier eingeben

d122=h12+h222h1h2cosϕh12h22h1h2cosϕ (= Skalarprodukt, = Innenprodukt) der Vektoren 1 und 2.

Das Skalarprodukt wird auch als winkelartige Ähnlichkeit zwischen 1 und 2 bezeichnet und ist im euklidischen Raum das geometrisch gültigste Ähnlichkeitsmaß , da es leicht in den euklidischen Abstand umgerechnet werden kann und umgekehrt (siehe auch hier ).

h2cosϕrσ1σ2r12space ". Art und Weise der Darstellung Cosinussatz gilt unabhängig davon bleiben , was als genommen‚Vektoren‘auf dieser Instanz -. Datenpunkte oder Datenfunktionen]

hsd2=2(1s)d2d2=1srr

sshd

ttnphns
quelle