% Studienarbeit von Ulrike Steffens
%
% Universitaet Hamburg
% Fachbereich Informatik
% Arbeitsbereich DBIS
%
% Anhang: Distanzma"se f"ur Vektorraummodelle des Information Retrieval
% 2.4.96

\chapter{Distanzma"se f"ur Vektorraummodelle des Information Retrieval}
\label{cos}
In Information Retrieval Systemen, die auf Vektorraum-Modellen basieren,
werden Anfragen und Dokumente als Vektoren repr"asentiert. Bei der Auswertung
von Anfragen an diese Systeme, wird die Distanz zwischen dem Anfragevektor
und den verschiedenen Dokumentenvektoren ermittelt. Hierzu werden in
verschiedenen Systemen verschiedene Distanzma"se verwendet.

Ein in Information Retrieval Systemen oft benutztes Ma"s f"ur $k$-dimensionale Vektorr"aume ist der Cosinus
des Winkels $\alpha$
zwischen dem Anfragevektor $\stackrel{\rightarrow}{a}$ und den Dokumentenvektoren $\stackrel{\rightarrow}{d}$ \cite{tcr92}.
Je gr"o"ser dabei der Cosinus, desto besser erf"ullt ein Dokument die Anfrage. Der Cosinus berechnet sich wie folgt \cite{bro95}:
\begin{eqnarray*}
\cos \alpha = \frac{\stackrel{\rightarrow}{a} \cdot \stackrel{\rightarrow}{d}}
{\| \stackrel{\rightarrow}{a} \| \cdot \| \stackrel{\rightarrow}{d} \|}
\end{eqnarray*}
Dabei ist $\stackrel{\rightarrow}{a} \cdot \stackrel{\rightarrow}{d}$ das
Skalarprodukt von $\stackrel{\rightarrow}{a}$ und $\stackrel{\rightarrow}{d}$
mit
\begin{eqnarray*}
\stackrel{\rightarrow}{a} \cdot \stackrel{\rightarrow}{d} = 
{a_1}{d_1} + {a_2}{d_2} + \cdots + {a_k}{d_k} =
\sum\limits_{j=1}^{k} {a_j}{d_j}
\end{eqnarray*}
$\| \stackrel{\rightarrow}{a} \|$ bzw. $\| \stackrel{\rightarrow}{d} \|$
sind die euklidischen Normen von $\stackrel{\rightarrow}{a}$ und 
$\stackrel{\rightarrow}{d}$
mit
\begin{eqnarray*}
\| \stackrel{\rightarrow}{a} \| =
\sqrt{{a_1}^2 + {a_2}^2 + \cdots {a_k}^2} =
\sqrt{\sum\limits_{j=1}^{k} {a_j}^2}
\end{eqnarray*}
und
\begin{eqnarray*}
\| \stackrel{\rightarrow}{a} \| =
\sqrt{{d_1}^2 + {d_2}^2 + \cdots {d_k}^2} =
\sqrt{\sum\limits_{j=1}^{k} {d_j}^2}
\end{eqnarray*}
Somit l"a"st sich der Cosinus des Winkels zwischen $\stackrel{\rightarrow}{a}$
und $\stackrel{\rightarrow}{d}$ mit Hilfe der Komponenten dieser beiden Vektoren
wie folgt berechnen:
\begin{eqnarray*}
\cos \alpha = \frac{\sum\limits_{j=1}^{k} {a_j}{d_j}}
{\sqrt{\sum\limits_{j=1}^{k} {a_j}^2 \sum\limits_{j=1}^{k} {d_j}^2}}
\end{eqnarray*}
Dieses Ma"s ist f"ur das Information Retrieval jedoch nur begrenzt geeignet,
da es die L"ange der jeweiligen Vektoren au"ser acht l"a"st. Dadurch werden
 unter Umst"anden Dokumente, die nur minimal von den Erfordernissen der
Anfrage abweichen, schlechter bewertet als solche, die der Anfrage nur
in sehr geringem Ma"se gen"ugen.

Zur Verdeutlichung betrachte man folgendes Beispiel: Sei
 $\stackrel{\rightarrow}{a}$ ein Anfragevektor mit folgenden Eigenschaften:
\begin{eqnarray*}
\stackrel{\rightarrow}{a} = ( 0,8 \hspace{0.2cm},\hspace{0.2cm} 0,8 \hspace{0.2cm}, \hspace{0.2cm} 0,8)
\end{eqnarray*}
In der Dokumentensammlung gibt es drei Dokumente, die folgenderma"sen
repr"asentiert seien:
\begin{eqnarray*}
\stackrel{\rightarrow}{d_1} = ( 0,8 \hspace{0.2cm},\hspace{0.2cm} 0,8 \hspace{0.2cm}, \hspace{0.2cm} 0,8)
\end{eqnarray*}
\begin{eqnarray*}
\stackrel{\rightarrow}{d_2} = ( 0,8 \hspace{0.2cm},\hspace{0.2cm} 0,7 \hspace{0.2cm}, \hspace{0.2cm} 0,7)
\end{eqnarray*}
\begin{eqnarray*}
\stackrel{\rightarrow}{d_3} = ( 0,1 \hspace{0.2cm},\hspace{0.2cm} 0,1 \hspace{0.2cm}, \hspace{0.2cm} 0,1)
\end{eqnarray*}


Sei $\cos \alpha_i$ der Cosinus des Winkels zwischen dem Anfragevektor
$\stackrel{\rightarrow}{a}$ und dem jeweiligen Dokumentenvektor
$\stackrel{\rightarrow}{d_i}$. So ergibt sich f"ur $\stackrel{\rightarrow}{d_1}$:
\begin{eqnarray*}
\cos \alpha_1 = 1
\end{eqnarray*}
Dieses Ergebnis entspricht der intuitiven Auffassung von Information Retrieval.
Der Anfragevektor und der Dokumentenvektor beschreiben exakt die gleichen
Eigenschaften, so da"s die h"ochste Bewertung mit $1$ erwartet werden konnte.

Betrachtet man das zweite Dokument, so erh"alt man:
\begin{eqnarray*}
\cos \alpha_2 \approx 0,9979
\end{eqnarray*}
Im Vergleich zu dem Ergebnis des ersten Dokuments entspricht aus dieses
Ergebnis den Erwartungen. Schlie"slich weicht es bei der zweiten und
dritten Eigenschaft leicht von der Anfrage ab, so da"s ein etwas schlechteres
Ergebnis nicht ungew"ohnlich erscheint.

Bei der Betrachtung des dritten Dokuments ergibt sich jedoch folgender Wert:
\begin{eqnarray*}
\cos \alpha_3 = 1
\end{eqnarray*}
Dieses Ergebnis ist konnte nicht erwartet werden, denn das dritte Dokument
erf"ullt alle drei geforderten Eigenschaften nur in sehr geringem Ma"se.
Dennoch wird es ebenso gut wie das erste und sogar besser als das zweite
Dokument bewertet.

Der Grund hierf"ur liegt darin, da"s die Vektoren des ersten und des dritten
Dokuments sowie der Anfragevektor sich im Vektorraum "uberdecken. Der Winkel
zwischen ihnen ist jeweils $0$ und der Cosinus dieses Winkels damit $1$.

Aus diesem Fallbeispiel mu"s man schlie"sen, da"s ein Distanzma"s f"ur
Vektorraum-Modelle im Information Retrieval nur dann sinnvoll eingesetzt
werden kann, wenn sowohl der Winkel zwischen den Vektoren als auch deren
L"ange betrachtet werden. Dieses Voraussetzungen erf"ullt das oben bereits
definierte Skalarprodukt, das sich ebenfalls aus den Vektorkomponenten
bilden l"a"st  \cite{bro95}:
\begin{eqnarray*}
\stackrel{\rightarrow}{a} \cdot \stackrel{\rightarrow}{d} = 
{a_1}{d_1} + {a_2}{d_2} + \cdots + {a_k}{d_k} =
\sum\limits_{j=1}^{k} {a_j}{d_j}
\end{eqnarray*}
Die folgende Tabelle zeigt, da"s dieses Distanzma"s f"ur das Information 
Retrieval besser geeignet ist.
\newline
\newline
\begin{tabular}{|p{2.7cm}|p{2.7cm}|p{1.5cm}|p{2.7cm}|p{1.5cm}|} \hline
Dokumenten\-vektor im Vergleich zum Anfrage\-vektor (0,8 , 0,8 , 0,8) &
Cosinus d. Winkels zwi\-schen Anfrage- u. Dokumenten\-vektor &
ent\-spre\-chen\-der Rang &
Skalar\-produkt von Anfrage- u. Dokumenten\-vektor &
ent\-spre\-chen\-der Rang\\ \hline

(0,8 , 0,8 , 0,8) 

&

1

&

1

&

1,92

&

1

\\

(0,8 , 0,7 , 0,7)

&

0,9979

&

3

&

1,76

&

2

\\

(0,1 , 0,1 , 0,1)
&

1
&

1
&

0,24
&

3
\\
\hline
\end{tabular}

 
