Header
   TUM Logo Clusteranalyse Polytop
Header_Inhalt

Header Bild

Abstands- und Ähnlichkeitsmaße

In einem Cluster liegen Punkte, die sich besonders ähnlich sind. Aber was heißt das genau und wie kann man diese Ähnlichkeit messen?

Hat man zwei Datenpunkte gegeben, möchte man intuitiv den direkten ”natürlichen” Abstand zwischen den beiden Punkten messen:


Jeder Datenpunkt wird durch einen Vektor x = (x1,x2,...,xn) gegeben, wobei n die Dimension ist, die wir gerade betrachten. Im oberen Beispiel ist n = 2, und Vektor x = (2,2) und y = (1,3). Um den Abstand zu berechnen berechnet man zuerst die Differenz der beiden Vektoren:

Man erhält x - y = (2 - 1,2 - 3) = (1,-1). Von diesem Vektor berechnet man nun die Länge (mit Hilfe der sogenannten euklidischen Norm):

 ∘ 2-------2 √ -
||x- y||2 = 1 + (- 1) = 2.

Der ”natürliche” Abstand zwischen x und y beträgt also √2- .

Dieser Abstand wird euklidischer Abstand genannt und die allgemeine Formel lautet:

 ┌│ -n---------
dE(x,y) = ∥x- y∥2 = ∘ (x1---y1)2 +-...+-(xn --yn)2 = │∘ ∑ (xi - yi)2
i=1

Aber leider ist dieser Abstand nicht immer sinnvoll.

Möchte man zum Beispiel den Abstand zwischen dem Empire State Building und dem Chrysler Building berechnen, ist der euklidische Abstand weniger sinnvoll, es sei denn man plant den Weg durch die Luft zurückzulegen.

Man wählt den Abstand so, dass man ”um die Häuser herumläuft". Verallgemeinert läuft man wie auf einem Schachbrett:

Manhattan

Für obiges Beispiel gilt nun: 

 
dM (x,y) = |2- 1|+ |2 - 3| = 1+ 1 = 2

Da die Stadt Manhattan einem Schachbrett sehr nahe kommt, heißt dieser Abstand Manhattan-Abstand bzw. Manhattan-Metrik.

Beim Cluster betrachtet man nicht nur Daten die in Form von Vektoren mit Zahleneinträgen vorliegen, sondern zum Beispiel auch Wörter oder ganze Texte.

Eine einfache Möglichkeit um die Ähnlichkeit zwischen zwei Wörtern zu berechnen ist es, die gemeinsamen Buchstaben zu betrachten:

dJ(Otto,Lotto) = 1- -|{o,t,t,o}∩-{l,o,t,t,o}|-= 1 - |{o,t,t,o}|-= 1 - 4= 1
|{l,o,t,t,o}|∪ {l,o,t,t,o}| |{l,o,t,t,o} 5 5

 |{}|
dJ(Otto,Eisdiele) = 1 - |{o,t,t,o,e,i,s,d,i,e,l,e}| = 1

dJ(Lotto,Eisdiele) =?

Die allgemeine Formel lautet

dJ(A,B ) = 1- |A-∩B-|
|A ∪B |

Haben zwei Wörter keine gemeinsamen Buchstaben so ist der Abstand gleich eins und maximal. Sind alle Buchstaben identisch ist der Abstand minimal und beträgt null.

Copyright 2009 - Team Clusteranalyse
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _