2.3.2 k-Nearest-Neighbor-Klassifikation

Die k-Nearest-Neighbor-Klassifikation basiert auf der Ähnlichkeit von Dokumenten bzw. der Ähnlichkeit ihrer Dokumentenvektoren. Für ein zu klassifizierendes Dokument d werden die k nächsten Nachbarn bezüglich eines Ähnlichkeitsmaßes gesucht, die die Basis für die Klassifikation bilden. Über die Verteilung der Zugehörigkeit dieser k nächsten Nachbarn zu den verschiedenen Klassen $c_j$ wird d in die Klasse eingeordnet, für die die Funktion

$$f(\vec{d},c_j)=\sum_{\vec{x_i} \in kNN(\vec{d})} Sim(\vec{d},\vec{x_i}) \; cont(\vec{x_i},c_j)$$

maximal wird, wobei

$$cont(\vec{x_i},c_j)= \left\{ \begin{array}{ll} 1 & falls x_i \in c_j\\ 0 & sonst\\ \end{array}\right.$$

$Sim(\vec{d},\vec{x_i})$ ist das Maß der Ähnlichkeit zwischen den Dokumenten d und $x_i$, jeweils repräsentiert durch ihren Feature-Vektor. (Es wird an dieser Stelle davon ausgegangen, daß der Feature-Raum n Dimensionen hat und jeder Feature-Vektor gleich lang ist.) Für die Ähnlichkeit bieten sich nun zum Beispiel folgende Maße an:

1. Die euklidische Distanz zwischen zwei Vektoren $\vec{x_1}$ und $\vec{x_2}$:
   $$Sim(\vec{x_1},\vec{x_2})=\vert\vec{x_1}-\vec{x_2}\vert=\sqrt{(\vec{x_1}-\vec{x_2})^2}$$

2. Das Cosinus-Ähnlichkeitsmaß für zwei Vektoren $\vec{x_1}$ und $\vec{x_2}$:
   $$Sim(\vec{x_1},\vec{x_2})=\cos \alpha=\dfrac{\vec{x_1} \: \vec{x_2}}{\vert\vec{x_1}\vert \: \vert\vec{x_2}\vert},$$

   wobei $\alpha$ der Winkel zwischen den beiden Vektoren ist.

   Für normalisierte Vektoren $\vec{x_i}=(x_{i1}, \ldots,x_{in})$ mit

   $$\vert\vec{x_i}\vert=\sum_{j=1}^{n}x_{ij}=1$$

   läßt sich die Cosinus-Ähnlichkeit als Produkt der Vektoren schreiben:

   $$Sim(\vec{x_1},\vec{x_2})=\vec{x_1} \: \vec{x_2}=\sum_{j=1}^n x_{1j}x_{2j}$$