Home | Wissen Stichwortverzeichnis Tags

Nächste-Nachbarn-Klassifikation

Einfache Sprache

Def. Nächste-Nachbarn-Klassifikation

Gegeben ist eine Menge an Trainingsdaten, eine Distanzfunktion $d$ und die Anzahl an Nachbarn die berücksichtigt werden sollen $k\in\mathbb N$. Die KNN Methode funktioniert dann folgendermaßen: Sei $x$ ein unbekanntes Objekt. Finde alle $k$ nächsten Nachbarn von $x$. Nutze die Klassifikation der Nachbarn um über die Klassifikation von $x$ zu entscheiden, z.B. durch einfache Mehrheit oder gewichtet nach Distanz.

Algorithmus für KNN ist wiefolgt Dabei gibt $\textrm{getObject}(\mathcal D,i)$ bzw. $\mathcal D.\textrm{getObject}(i)$ das $i$-te Objekt der Datenbank $\mathcal D$ zurück.

	\begin{algorithm}
	\caption{NN with squential scan}
	\begin{algorithmic}
	\Input $\textrm{Datenbank }\mathcal D, \textrm{Abfragenobjekt }q,\textrm{Nachbaranzahl } k$
    \Procedure{NN-SeqScanCore}{$\mathcal D,q,k$}
	\Comment{$r$ is a priority list where $d$ is distance.}
    \State $r \gets$ List of $(d\in\mathbb R,q\in\mathcal D)$ Orderd by $d$ descending
	\State $r\gets []$
	\State $n\gets |\mathcal D|$
	\For{$i= 1$ to $k$}
		\State $r.\mathrm{insert}(\textrm{dist}(q,\textrm{getObject}(\mathcal D,i)), \textrm{getObject}(\mathcal D,i))$
    \EndFor
	\For{$i= k+1$ to $n$}
		\If{$\textrm{dist}(q,\textrm{getObject}(\mathcal D,i) \leq r.\textrm{getFirst}()$}
			\State $r.\textrm{deleteFirst}()$
			\State $r.\mathrm{insert}(\textrm{dist}(q,\textrm{getObject}(\mathcal D,i)), \textrm{getObject}(\mathcal D,i))$
        \EndIf
	\EndFor
    \return r
    \EndProcedure
	\end{algorithmic}
	\end{algorithm}

Wahl von $k$

Normalerweise ist $1\ll k < 10$ empfohlen. Sonst kann folgendes passieren:

Probleme

Attribute mit verschiedenem Größen/Zahlenbereichen => Lösung ist Normalisierung.

KNN ist ein Lazy learner, das heißt es wird kein Modell gebraucht. => Lösungen ist die optimierte Suche mit Indexstrukturen oder nur die partielle Distanz berechnen aus eine Teilmenge der Attribute.

Fluch der Dimensionalität

Zusammenfassung

Home: