Maschinelles Lernen und Sicherheit

Anhang A. Ergänzendes Material für Kapitel 2

Mehr über Metriken

In unserer Diskussion über das Clustering haben wir in erster Linie den euklidischen Standardabstand zwischen Vektoren in einem Vektorraum verwendet:

$$d(x,y)=\sqrt{\sum _i(x_i-y_i{)}^2}$$

Der euklidische Abstand ist auch als L2-Norm bekannt. Es gibt noch einige andere Metriken, die häufig in Anwendungen verwendet werden:

• Eine Variante des euklidischen Abstands ist die L1-Norm, auch bekannt als Manhattan-Abstand (weil sie die Anzahl der "Blöcke" zwischen zwei Punkten auf einem Gitter zählt):

  $$d(x,y)=\sum _i|(x_i-y_i)|$$

• Eine andere ist die _L∞-Norm, die wie folgt definiert ist:

  $$d(x,y)=\underset{i}{\max }|(x_i-y_i)|$$

• Für Vektoren mit binären Werten oder Bits kannst du die Hamming-Distanz verwenden, also die Anzahl der Bits, die x und y gemeinsam haben. Dies kann wie folgt berechnet werden:

  $$d(x,y)=H(\neg (x\oplus y\left)\right)$$

  Dabei ist H(v) das Hamming-Gewicht, also die Anzahl der "1"-Bits in v. Wenn die Punkte, die du vergleichst, eine unterschiedliche Bitlänge haben, muss dem kürzeren Punkt eine Null vorangestellt werden.

• Für Listen kannst du die Jaccard-Ähnlichkeit verwenden:

  $$d(x,y)=\frac{|x\cap y|}{|x\cup y|}$$

  Die Jaccard-Ähnlichkeit berechnet die Anzahl der gemeinsamen Elemente von x und y, normiert auf die Gesamtzahl der Elemente in der Schnittmenge. Eine nützliche Eigenschaft der Jaccard-Ähnlichkeit ist, dass du damit Listen mit unterschiedlicher Länge vergleichen kannst.

Die_L1- und_L2-Metriken in Vektorräumen leiden unter dem so genannten "Fluch der Dimensionalität". Dieser ...