Nächstes Kapitel: Nächste Nachbarn-Klassifikation mit sklearn
k-Nächste-Nachbarn-Klassifikator¶
„Zeig mir, wer deine Freunde sind, und ich sage dir, wer du bist.“
Die Idee hinter dieser Redewendung findet sich in vielen Sprachen und Kulturen:
🇪🇸 Spanisch:
"Dime con quién andas y te diré quién eres."
Sag mir, mit wem du gehst, und ich sage dir, wer du bist.🇫🇷 Französisch:
"Dis-moi qui tu fréquentes, je te dirai qui tu es."
Sag mir, mit wem du Umgang hast, und ich sage dir, wer du bist.🇩🇪 Deutsch:
„Sag mir, mit wem du gehst, und ich sage dir, wer du bist.“
Eine weitere geläufige Variante lautet: „Zeig mir deine Freunde, und ich sag dir, wer du bist.“🇷🇺 Russisch:
"Скажи мне, кто твой друг, и я скажу, кто ты."
Sag mir, wer dein Freund ist, und ich sage dir, wer du bist.🇨🇳 Chinesisch:
"物以类聚，人以群分。"
Dinge gleicher Art finden zusammen; Menschen gruppieren sich nach Ähnlichkeit.🇯🇵 Japanisch:
「類は友を呼ぶ」 (Rui wa tomo o yobu)
Gleiches zieht Gleiches an.
Oft sinngemäß übersetzt als: „Gleich und Gleich gesellt sich gern.“🇮🇹 Italienisch:
"Dimmi con chi vai e ti dirò chi sei."
Sag mir, mit wem du gehst, und ich sage dir, wer du bist.🇬🇷 Griechisch:
"Πες μου τον φίλο σου να σου πω ποιος είσαι."
Sag mir, wer dein Freund ist, und ich sage dir, wer du bist.🇹🇷 Türkisch:
"Bana arkadaşını söyle, sana kim olduğunu söyleyeyim."
Sag mir, wer dein Freund ist, und ich sage dir, wer du bist.🇮🇳 Hindi:
"जैसे संग वैसे रंग।" (Jaise sang, waise rang)
Wie die Gesellschaft, so die Färbung.
Sinngemäß: Du wirst den Menschen ähnlich, mit denen du Zeit verbringst.🏛️ Latein:
"Socius pro socio habetur."
Ein Mensch wird nach seinen Gefährten beurteilt.
Eine ähnliche Idee findet sich sogar in der Bibel:
„Wer mit Weisen umgeht, wird weise; wer sich mit Toren einlässt, dem wird es schlecht ergehen.“
— Sprüche 13,20
Von Redewendungen zur Nächste-Nachbarn-Klassifikation¶
- Du kannst etwas über eine Person lernen, wenn du dir anschaust, mit wem sie sich umgibt.
- Die zugrunde liegende Idee der Nächste-Nachbarn-Klassifikation ist ganz ähnlich: Ein unbekanntes Objekt wird anhand der bekannten Objekte klassifiziert, die ihm am ähnlichsten sind.
- Bei der 1-Nächster-Nachbar-Klassifikation erhält das neue Objekt die Klasse seines nächsten Nachbarn.
- Bei der k-Nächste-Nachbarn-Klassifikation (k-NN) betrachten wir die k nächsten Objekte und lassen deren Klassen abstimmen.
„Zeig mir deine Nachbarn, und ich sage dir, zu welcher Klasse du gehörst.“
Damit steht die Grundidee des k-Nächste-Nachbarn-Klassifikators in engem Zusammenhang mit einer Art von Schlussfolgerung, die wir auch im Alltag verwenden.
Stell dir vor, du triffst eine Gruppe von Menschen. Sie sind alle jung, modisch und sportlich. Sie sprechen über ihren Freund Ben, der gerade nicht dabei ist. Was für einen Menschen stellst du dir unter Ben vor?
Ohne etwas Weiteres über ihn zu wissen, wirst du ihn dir wahrscheinlich ebenfalls jung, modisch und sportlich vorstellen. Du ziehst also aus den Eigenschaften der Menschen in seiner Nähe Rückschlüsse auf eine unbekannte Person.
Nehmen wir nun an, du erfährst, dass Ben in einer Wohngegend lebt, in der die meisten Menschen konservativ wählen und das durchschnittliche Jahreseinkommen über 200.000 Dollar liegt. Seine beiden nächsten Nachbarn verdienen jeweils mehr als 300.000 Dollar im Jahr. Dann hältst du es vielleicht für weniger wahrscheinlich, dass Ben ein sehr niedriges Einkommen hat, und vermutest möglicherweise, dass seine politischen Präferenzen denen seiner Umgebung ähneln.
Solche Schlussfolgerungen können bei einer einzelnen Person natürlich falsch sein. Entscheidend ist lediglich die zugrunde liegende Intuition:
Objekte, die nahe beieinander liegen, besitzen häufig ähnliche Eigenschaften.
Das k-Nächste-Nachbarn-Prinzip¶
Das Prinzip der Nächste-Nachbarn-Klassifikation besteht darin, diejenigen Trainingsbeispiele zu finden, die einem neuen, bisher unbekannten Beispiel am nächsten liegen. Diese benachbarten Beispiele werden anschließend verwendet, um die Klasse des neuen Beispiels zu bestimmen.
Im einfachsten Fall, beim 1-Nächster-Nachbar-Klassifikator, suchen wir nur das einzelne nächstgelegene Trainingsbeispiel. Das neue Beispiel erhält dieselbe Klassenbezeichnung wie dieser nächste Nachbar.
Beim k-Nächste-Nachbarn-Klassifikator suchen wir stattdessen die k nächstgelegenen Trainingsbeispiele. Die Klasse des neuen Beispiels wird normalerweise durch eine Mehrheitsentscheidung dieser Nachbarn bestimmt.
Wählen wir beispielsweise k = 5 und gehören die fünf nächsten Nachbarn zu den Klassen A, A, B, A, B, dann wird das neue Beispiel als A klassifiziert, weil drei der fünf nächsten Nachbarn zur Klasse A gehören.
Der Wert von k ist ein vom Benutzer festgelegter Parameter. Kleine Werte von k sorgen dafür, dass der Klassifikator stark von einzelnen nahe gelegenen Beispielen abhängt; größere Werte berücksichtigen eine breitere Nachbarschaft.
Um festzustellen, welche Beispiele die „nächsten“ sind, benötigen wir ein Distanzmaß. Für numerische Daten ist die euklidische Distanz eine der gebräuchlichsten Möglichkeiten.
Nächste-Nachbarn-Verfahren werden häufig als instanzbasierte Verfahren oder als Verfahren des Lazy Learning bezeichnet. Anstatt beim Training ein explizites Modell zu konstruieren, speichern sie die Trainingsbeispiele und führen den größten Teil der Berechnung erst dann durch, wenn ein neues Beispiel klassifiziert werden soll.
So wird aus der alten Redewendung
„Zeig mir, wer deine Freunde sind, und ich sage dir, wer du bist.“
in der Sprache des maschinellen Lernens:
„Zeig mir deine nächsten Nachbarn, und ich sage dir deine Klasse.“
Ein einfaches visuelles Beispiel¶
Das folgende Bild veranschaulicht die Grundidee der Nächste-Nachbarn-Klassifikation.
Das Puzzleteil steht für ein unbekanntes Objekt. Wir möchten herausfinden, welches Tier es darstellt, indem wir die ihm am nächsten liegenden Objekte betrachten.
Für $k=1$ ist der nächste Nachbar eine Katze. Der Klassifikator sagt daher voraus, dass auch das Puzzleteil eine Katze ist.
Für $k=4$ bestehen die vier nächsten Nachbarn aus drei Katzen und einem Huhn. Die Mehrheit der nächsten Nachbarn sind Katzen, also lautet die Vorhersage des Klassifikators erneut Katze.
Finde die nächsten bekannten Objekte und lasse deren Klassen über die Klasse des unbekannten Objekts entscheiden.
Bevor wir mit der Implementierung eines Nächste-Nachbarn-Klassifikators beginnen, benötigen wir Trainingsdaten und Testdaten. Wir verwenden den von sklearn.datasets bereitgestellten Iris-Datensatz.
Der Datensatz enthält jeweils 50 Beispiele von drei Iris-Arten:
- Iris setosa,
- Iris versicolor,
- Iris virginica.
Für jedes Beispiel wurden vier Merkmale gemessen: Länge und Breite des Kelchblatts sowie Länge und Breite des Blütenblatts, jeweils in Zentimetern.
import numpy as np
from sklearn import datasets
iris = datasets.load_iris()
data = iris.data
labels = iris.target
for i in [0, 79, 99, 121]:
print(f"Index: {i:3}, Merkmale: {data[i]}, Klasse: {labels[i]}")
Wir teilen die Daten zufällig in einen Trainingsdatensatz und einen Testdatensatz auf. Der Zufalls-Seed sorgt dafür, dass die Beispiele auf der Webseite reproduzierbar sind.
np.random.seed(42)
indices = np.random.permutation(len(data))
n_test_samples = 12
train_data = data[indices[:-n_test_samples]]
train_labels = labels[indices[:-n_test_samples]]
test_data = data[indices[-n_test_samples:]]
test_labels = labels[indices[-n_test_samples:]]
print("Die ersten Beispiele unseres Trainingsdatensatzes:")
print(f"{'Index':7s}{'Daten':22s}{'Klasse':5s}")
for i in range(5):
print(f"{i:4d} {train_data[i]} {train_labels[i]:3}")
print()
print("Die ersten Beispiele unseres Testdatensatzes:")
print(f"{'Index':7s}{'Daten':22s}{'Klasse':5s}")
for i in range(5):
print(f"{i:4d} {test_data[i]} {test_labels[i]:3}")
Der folgende Code dient ausschließlich der Visualisierung der Trainingsdaten. Die Iris-Beispiele besitzen vier Merkmale, ein dreidimensionales Diagramm kann jedoch nur drei Koordinaten darstellen. Für diese Visualisierung verwenden wir deshalb Kelchblattlänge, Blütenblattlänge und Blütenblattbreite. Der Klassifikator selbst verwendet weiterhin alle vier Merkmale.
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111, projection="3d")
for class_id, class_name in enumerate(iris.target_names):
mask = train_labels == class_id
ax.scatter(
train_data[mask, 0],
train_data[mask, 2],
train_data[mask, 3],
label=class_name,
)
ax.set_xlabel("Kelchblattlänge")
ax.set_ylabel("Blütenblattlänge")
ax.set_zlabel("Blütenblattbreite")
ax.legend()
plt.show()
Distanzmaße¶
Wir haben bereits gesehen, dass die Nächste-Nachbarn-Klassifikation darauf beruht, ein neues Objekt mit den Beispielen im Trainingsdatensatz zu vergleichen. Um zu entscheiden, welche Beispiele am nächsten liegen, benötigen wir eine Distanzfunktion.
In einem $n$-dimensionalen Merkmalsraum werden häufig die folgenden drei Distanzmaße verwendet:
Euklidische Distanz
Die euklidische Distanz zwischen zwei Punkten $x$ und $y$ misst die Länge der geraden Verbindungsstrecke zwischen ihnen. Im zwei- oder dreidimensionalen Raum lässt sie sich aus den kartesischen Koordinaten mithilfe des Satzes des Pythagoras berechnen. Deshalb wird sie gelegentlich auch als pythagoreische Distanz bezeichnet.
Die allgemeine Formel in $n$ Dimensionen lautet
$$ d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i-y_i)^2}. $$
Manhattan-Distanz
Die Manhattan-Distanz ist als Summe der absoluten Differenzen zwischen den Koordinaten von $x$ und $y$ definiert:
$$ d(x, y) = \sum_{i=1}^{n} |x_i-y_i|. $$
Der Name beruht auf der Vorstellung, sich durch ein rechtwinkliges Straßengitter zu bewegen: Anstatt die direkte Verbindung zwischen zwei Punkten zu nehmen, bewegt man sich ausschließlich parallel zu den Koordinatenachsen.
Minkowski-Distanz
Die Minkowski-Distanz verallgemeinert die euklidische und die Manhattan-Distanz in einem einzigen Distanzmaß. Sie ist definiert durch
$$ d(x, y) = \left(\sum_{i=1}^{n} |x_i-y_i|^p\right)^{\frac{1}{p}}. $$
Für $p=1$ erhalten wir die Manhattan-Distanz, für $p=2$ die euklidische Distanz.
Das folgende Diagramm veranschaulicht die euklidische und die Manhattan-Distanz:
Die blaue Linie zeigt die euklidische Distanz zwischen dem grünen und dem roten Punkt: Sie ist die direkte geradlinige Verbindung.
Die orangefarbenen, grünen und gelben Wege zeigen unterschiedliche Möglichkeiten, vom grünen zum roten Punkt zu gelangen, wobei nur horizontale und vertikale Strecken verwendet werden. Sie entsprechen alle der Manhattan-Distanz. Obwohl die Wege unterschiedlich aussehen, ist ihre Gesamtlänge gleich.
Bestimmung der Nachbarn¶
Um in unserer ersten Implementierung die Ähnlichkeit zwischen zwei Instanzen zu bestimmen, verwenden wir die euklidische Distanz.
NumPy stellt mit der Funktion norm aus dem Modul np.linalg eine bequeme Möglichkeit zur Berechnung bereit. Für zwei Vektoren $x$ und $y$ berechnet
np.linalg.norm(x - y)
genau die oben definierte euklidische Distanz.
def distance(instance1, instance2):
"""Gibt die euklidische Distanz zwischen zwei numerischen Instanzen zurück."""
return np.linalg.norm(np.subtract(instance1, instance2))
print(distance([3, 5], [1, 1]))
print(distance(train_data[3], train_data[44]))
Die Funktion get_neighbors berechnet die Distanz einer neuen Instanz zu jeder Trainingsinstanz, sortiert die Ergebnisse nach ihrer Distanz und gibt die ersten k Elemente zurück.
def get_neighbors(training_set, labels, test_instance, k, distance):
"""Gibt die k nächsten Nachbarn von test_instance zurück.
Jedes zurückgegebene 3-Tupel enthält
(training_instance, distance, label)
sortiert nach aufsteigender Distanz.
"""
distances = []
for index in range(len(training_set)):
dist = distance(test_instance, training_set[index])
distances.append((training_set[index], dist, labels[index]))
distances.sort(key=lambda item: item[1])
return distances[:k]
Nun können wir die drei nächsten Nachbarn der ersten fünf Testbeispiele betrachten:
for i in range(5):
neighbors = get_neighbors(
train_data,
train_labels,
test_data[i],
3,
distance=distance,
)
print("Index:", i)
print("Testdaten:", test_data[i])
print("Tatsächliche Klasse:", test_labels[i])
print("Nachbarn:", neighbors)
print()
Abstimmung zur Bestimmung eines einzelnen Ergebnisses¶
Die nächsten Nachbarn zu finden, ist nur der erste Schritt. Für die Klassifikation müssen die Nachbarn über die Klasse des neuen Objekts abstimmen.
Mit der Klasse Counter aus collections lässt sich eine einfache Mehrheitsentscheidung leicht implementieren:
from collections import Counter
def vote(neighbors):
"""Gibt die häufigste Klassenbezeichnung unter den Nachbarn zurück."""
class_counter = Counter(neighbor[2] for neighbor in neighbors)
return class_counter.most_common(1)[0][0]
Wir testen die Abstimmung für alle Testbeispiele mit k = 3:
for i in range(n_test_samples):
neighbors = get_neighbors(
train_data,
train_labels,
test_data[i],
3,
distance=distance,
)
prediction = vote(neighbors)
print(
"Index:", i,
", Vorhersage:", prediction,
", Klasse:", test_labels[i],
", Daten:", test_data[i],
)
Bei dieser konkreten Aufteilung stimmen alle Vorhersagen bis auf ein Testbeispiel mit den bekannten Klassenbezeichnungen überein. Das ist durchaus hilfreich: Auch ein einfacher und intuitiver Klassifikator kann Fehler machen.
Manchmal möchten wir außerdem wissen, wie stark sich die Nachbarn einig sind. Die folgende Funktion gibt die siegreiche Klasse zusammen mit ihrem Stimmenanteil zurück. Ein Stimmenanteil von beispielsweise 0.8 bedeutet, dass 80 % der ausgewählten Nachbarn für die Gewinnerklasse gestimmt haben.
Der Stimmenanteil ist ein nützlicher Indikator für die Sicherheit der Entscheidung, sollte aber nicht automatisch als kalibrierte statistische Wahrscheinlichkeit interpretiert werden.
def vote_with_confidence(neighbors):
"""Gibt die Gewinnerklasse und ihren Anteil an den Nachbarstimmen zurück."""
class_counter = Counter(neighbor[2] for neighbor in neighbors)
winner, winner_votes = class_counter.most_common(1)[0]
return winner, winner_votes / len(neighbors)
for i in range(n_test_samples):
neighbors = get_neighbors(
train_data,
train_labels,
test_data[i],
5,
distance=distance,
)
print(
"Index:", i,
", Abstimmung:", vote_with_confidence(neighbors),
", Klasse:", test_labels[i],
)
Der gewichtete Nächste-Nachbarn-Klassifikator¶
Bisher haben wir die $k$ nächsten Nachbarn eines unbekannten Objekts betrachtet und eine einfache Mehrheitsentscheidung verwendet. Das hat im vorherigen Beispiel recht gut funktioniert, berücksichtigt aber einen wichtigen Gedanken nicht: Die nächstgelegenen Nachbarn können uns mehr über das unbekannte Objekt verraten als weiter entfernte Nachbarn.
Mit anderen Worten: Es kann sinnvoll sein, nahen Nachbarn stärker zu vertrauen als weit entfernten.
Nehmen wir beispielsweise an, wir hätten 11 Nachbarn eines unbekannten Objekts $UO$. Die fünf nächsten Nachbarn gehören alle zur Klasse A, während die übrigen sechs Nachbarn, die weiter entfernt liegen, zur Klasse B gehören.
Welche Klasse sollte $UO$ erhalten?
Bei einer gewöhnlichen Mehrheitsentscheidung lautet die Antwort B, weil die Abstimmung mit 6 zu 5 zugunsten von B ausgeht. Allerdings gehören alle fünf nächstgelegenen Nachbarn zur Klasse A. Es erscheint daher sinnvoll, diesen nahen Nachbarn einen größeren Einfluss zu geben als den weiter entfernten.
Um diese Idee umzusetzen, können wir den Nachbarn unterschiedliche Gewichte zuweisen. Eine einfache Strategie richtet sich ausschließlich nach ihrer Position in der sortierten Nachbarschaftsliste:
- der nächste Nachbar erhält das Gewicht $1/1$,
- der zweitnächste Nachbar erhält das Gewicht $1/2$,
- der drittnächste Nachbar erhält das Gewicht $1/3$,
- und so weiter bis zum Gewicht $1/k$ für den $k$-ten Nachbarn.
Damit verwenden wir die harmonische Reihe als Gewichtung:
$$ \sum_{i=1}^{k}\frac{1}{i} =1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{k}. $$
Beachte, dass dieser Ansatz nicht die tatsächlichen numerischen Distanzen verwendet. Er berücksichtigt lediglich die Rangfolge der Nachbarn: erster, zweiter, dritter usw.
Wir implementieren diese Strategie in der folgenden Funktion:
def vote_harmonic_weights(neighbors, all_results=True):
"""Stimmt mit den Gewichten 1, 1/2, ..., 1/k entsprechend dem Rang der Nachbarn ab."""
class_counter = Counter()
for index, neighbor in enumerate(neighbors):
label = neighbor[2]
class_counter[label] += 1 / (index + 1)
total = sum(class_counter.values())
winner = class_counter.most_common(1)[0][0]
if all_results:
normalized = [(label, value / total) for label, value in class_counter.most_common()]
return winner, normalized
return winner, class_counter[winner] / total
for i in range(n_test_samples):
neighbors = get_neighbors(
train_data,
train_labels,
test_data[i],
6,
distance=distance,
)
print(
"Index:", i,
", Klasse:", test_labels[i],
", gewichtete Abstimmung:", vote_harmonic_weights(neighbors),
)
Das vorherige Gewichtungsschema verbessert die gewöhnliche Mehrheitsentscheidung, berücksichtigt aber weiterhin nur die Rangfolge der Nachbarn. Es spielt keine Rolle, ob die beiden nächsten Nachbarn nahezu gleich weit entfernt sind oder ob einer von ihnen sehr viel weiter entfernt liegt als der andere.
Wir können deshalb noch einen Schritt weitergehen und die tatsächlichen Distanzen selbst als Gewichte verwenden. Die Grundidee bleibt gleich: Nahe Nachbarn sollen einen stärkeren Einfluss auf das Ergebnis haben als weiter entfernte.
Für eine distanzabhängige Gewichtung gibt es nicht eine einzige zwingend vorgeschriebene Formel. In der folgenden Implementierung verwenden wir
$$ w(d)=\frac{1}{1+d^2}. $$
Ein Nachbar mit der Distanz $d=0$ erhält das Gewicht $1$. Mit zunehmender Distanz nimmt sein Gewicht stetig ab. Das +1 im Nenner verhindert außerdem eine Division durch null bei einer identischen Trainingsinstanz.
Damit haben wir nun zwei unterschiedliche Formen der gewichteten Abstimmung:
- rangbasierte Gewichtung: Das Gewicht hängt nur davon ab, ob ein Nachbar der erste, zweite, dritte usw. ist;
- distanzbasierte Gewichtung: Das Gewicht hängt von der tatsächlichen numerischen Distanz zum zu klassifizierenden Objekt ab.
Wir implementieren die distanzbasierte Variante in der folgenden Funktion:
def vote_distance_weights(neighbors, all_results=True):
"""Stimmt mit dem distanzabhängigen Gewicht 1 / (1 + distance**2) ab."""
class_counter = Counter()
for _, dist, label in neighbors:
class_counter[label] += 1 / (1 + dist**2)
total = sum(class_counter.values())
winner = class_counter.most_common(1)[0][0]
if all_results:
normalized = [(label, value / total) for label, value in class_counter.most_common()]
return winner, normalized
return winner, class_counter[winner] / total
for i in range(n_test_samples):
neighbors = get_neighbors(
train_data,
train_labels,
test_data[i],
6,
distance=distance,
)
print(
"Index:", i,
", Ergebnis:", vote_distance_weights(neighbors),
)
Übung und Beispiel: Klassifikation von Früchten mit k-Nächste-Nachbarn¶
Das nächste Beispiel veranschaulicht eine wichtige Eigenschaft jedes distanzbasierten Klassifikators: Die Skalierung der Merkmale spielt eine Rolle.
Wir erzeugen künstliche Daten für drei Obstsorten:
- Apfel,
- Mango,
- Zitrone.
Jede Frucht wird durch drei Merkmale beschrieben:
- Süße,
- pH-Wert,
- Gewicht in Gramm.
Für dieses Experiment sind Süße und pH-Wert bewusst aussagekräftig, während alle drei Obstklassen dieselbe breite Gewichtsverteilung erhalten. Das Gewicht enthält daher fast keine Information über die Klasse.
Das ist beabsichtigt. Auf diese Weise können wir beobachten, was passiert, wenn ein numerisch großes, aber wenig aussagekräftiges Merkmal die Distanzberechnung dominiert.
rng = np.random.default_rng(42)
def create_features(number_samples, *feature_specs):
"""Erzeugt synthetische Merkmale aus (min, max, Nachkommastellen)-Spezifikationen."""
features = []
for min_val, max_val, decimals in feature_specs:
values = rng.uniform(min_val, max_val, number_samples).round(decimals)
features.append(values)
return np.column_stack(features)
num_apples = num_mangos = num_lemons = 150
# Süße und pH-Wert tragen den größten Teil der Klasseninformation.
# Das Gewicht besitzt für alle drei Klassen dieselbe breite Verteilung.
weight = (50, 700, 0)
apples = create_features(
num_apples,
(9, 15, 1), # Süße
(3.0, 4.2, 2), # pH
weight,
)
mangos = create_features(
num_mangos,
(14, 20, 1), # Süße
(3.8, 5.2, 2), # pH
weight,
)
lemons = create_features(
num_lemons,
(5, 11, 1), # Süße
(2.0, 3.2, 2), # pH
weight,
)
apples[:5]
from sklearn.model_selection import train_test_split
X = np.vstack((apples, mangos, lemons))
y = np.array(
["Apfel"] * num_apples
+ ["Mango"] * num_mangos
+ ["Zitrone"] * num_lemons
)
X_train, X_test, y_train, y_test = train_test_split(
X,
y,
test_size=0.2,
random_state=42,
stratify=y,
)
Bevor wir irgendetwas skalieren, wenden wir exakt den oben implementierten k-NN-Klassifikator an.
def predict_knn(X_train, y_train, X_test, k=5):
predictions = []
for sample in X_test:
neighbors = get_neighbors(
X_train,
y_train,
sample,
k,
distance=distance,
)
predictions.append(vote(neighbors))
return np.array(predictions)
def accuracy(y_true, y_pred):
return np.mean(y_true == y_pred)
predictions_unscaled = predict_knn(X_train, y_train, X_test, k=5)
accuracy_unscaled = accuracy(y_test, predictions_unscaled)
print(f"Genauigkeit ohne Skalierung: {accuracy_unscaled:.3f}")
Das Ergebnis ist überraschend schlecht, obwohl Süße und pH-Wert die Obstklassen eigentlich recht gut voneinander trennen.
Der Grund wird deutlich, wenn wir uns die numerischen Wertebereiche der drei Merkmale ansehen.
feature_names = ["Süße", "pH", "Gewicht"]
for column, name in enumerate(feature_names):
minimum = X_train[:, column].min()
maximum = X_train[:, column].max()
print(f"{name:10s}: {minimum:7.2f} ... {maximum:7.2f}")
Eine Differenz von 200 Gramm trägt erheblich stärker zur euklidischen Distanz bei als eine Differenz von 3 Einheiten bei der Süße oder von 1 beim pH-Wert. Deshalb schenkt der unskalierte Klassifikator dem Gewicht viel zu viel Aufmerksamkeit, obwohl das Gewicht absichtlich so erzeugt wurde, dass es nahezu keine Information über die Klasse enthält.
Nun standardisieren wir jedes Merkmal. Für jedes einzelne Merkmal, beispielsweise Süße, pH-Wert oder Gewicht, berechnen wir aus den Trainingsdaten seinen Mittelwert $\mu$ und seine Standardabweichung $\sigma$.
Der Mittelwert $\mu$ ist der Durchschnittswert eines Merkmals. Enthält der Trainingsdatensatz die Werte
$$ x_1, x_2, \ldots, x_n, $$
dann ist der Mittelwert
$$ \mu = \frac{1}{n}\sum_{i=1}^{n} x_i. $$
Er beschreibt das Zentrum der beobachteten Werte.
Die Standardabweichung $\sigma$ beschreibt, wie stark die Werte eines Merkmals um ihren Mittelwert streuen. Sie wird berechnet als
$$ \sigma = \sqrt{ \frac{1}{n} \sum_{i=1}^{n}(x_i-\mu)^2 }. $$
Eine kleine Standardabweichung bedeutet, dass die meisten Werte nahe beim Mittelwert liegen. Eine große Standardabweichung zeigt dagegen an, dass die Werte stärker verteilt sind.
Jeder Wert $x$ wird anschließend in einen standardisierten Wert $z$ transformiert:
$$ z=\frac{x-\mu}{\sigma}. $$
Diese Transformation hat zwei Auswirkungen:
- Durch das Subtrahieren von $\mu$ wird das Merkmal so verschoben, dass sein Mittelwert ungefähr $0$ wird.
- Durch die Division durch $\sigma$ wird es so skaliert, dass seine Standardabweichung ungefähr $1$ wird.
Wichtig ist, dass $\mu$ und $\sigma$ für jedes Merkmal getrennt berechnet werden. Die Süße besitzt also ihren eigenen Mittelwert und ihre eigene Standardabweichung, ebenso der pH-Wert und das Gewicht.
Nehmen wir beispielsweise an, die Gewichte im Trainingsdatensatz hätten
$$ \mu_{\text{weight}} = 220 $$
und
$$ \sigma_{\text{weight}} = 80. $$
Eine Frucht mit einem Gewicht von $300$ Gramm wird dann transformiert zu
$$ z_{\text{weight}} = \frac{300-220}{80} = 1. $$
Das bedeutet: Ihr Gewicht liegt eine Standardabweichung über dem mittleren Gewicht.
Entsprechend bedeutet ein standardisierter Wert von
$$ z=-2, $$
dass der ursprüngliche Wert zwei Standardabweichungen unterhalb des Mittelwerts liegt.
Nach der Standardisierung werden Süße, pH-Wert und Gewicht somit auf vergleichbaren Skalen ausgedrückt. Eine Differenz von einer Standardabweichung beim Gewicht wird ähnlich behandelt wie eine Differenz von einer Standardabweichung bei der Süße oder beim pH-Wert.
Die Werte für $\mu$ und $\sigma$ müssen ausschließlich aus den Trainingsdaten berechnet werden. Dieselben Werte werden anschließend unverändert auf Trainings- und Testdaten angewendet.
Dieser letzte Punkt ist wichtig: Würden wir den Scaler an den gesamten Datensatz anpassen, könnten Informationen aus dem Testdatensatz die Vorverarbeitung beeinflussen. Das ist eine Form von Data Leakage.
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)
predictions_scaled = predict_knn(
X_train_scaled,
y_train,
X_test_scaled,
k=5,
)
accuracy_scaled = accuracy(y_test, predictions_scaled)
print(f"Genauigkeit ohne Skalierung: {accuracy_unscaled:.3f}")
print(f"Genauigkeit mit Skalierung: {accuracy_scaled:.3f}")
Der Algorithmus selbst hat sich nicht verändert. Wir verwenden dieselben Trainingsbeispiele, dieselben Testbeispiele, denselben Wert von k, dieselbe euklidische Distanz und dieselbe Mehrheitsentscheidung. Verändert wurde lediglich die Darstellung der Merkmale.
Distanzbasierte Algorithmen wie k-NN reagieren besonders empfindlich auf die Skalierung der Merkmale.
Das Beispiel zeigt außerdem, warum die Maßeinheit, in der ein Merkmal angegeben wird, nicht unbeabsichtigt darüber entscheiden sollte, wie wichtig dieses Merkmal wird.
Für die spätere Verwendung können wir die erzeugten unskalierten Fruchtdaten als CSV-Datei speichern:
from pathlib import Path
import pandas as pd
Path("data").mkdir(exist_ok=True)
fruit_df = pd.DataFrame(X, columns=["Süße", "pH", "Gewicht"])
fruit_df["Frucht"] = y
fruit_df.to_csv("data/fruits_data.csv", index=False)
fruit_df.head()
Nächste Nachbarn jenseits der Klassifikation: Zeichenketten und Rechtschreibung¶
Nächste-Nachbarn-Verfahren sind nicht auf numerische Vektoren beschränkt. Entscheidend ist lediglich, dass wir eine sinnvolle Distanz zwischen zwei Objekten definieren können.
Für Zeichenketten eignet sich beispielsweise die Levenshtein-Distanz: die minimale Anzahl von Einfügungen, Löschungen und Ersetzungen, die erforderlich ist, um eine Zeichenkette in eine andere zu überführen.
Die folgenden Beispiele lassen sich daher genauer als Nächste-Nachbarn-Suche und nicht als Klassifikation beschreiben. Wir verwenden dieselbe Funktion get_neighbors, nur sind die Objekte jetzt selbst Zeichenketten.
Eine ausführliche Behandlung findet sich in unserem Tutorial zurEine ausführliche Behandlung findet sich in unserem Tutorial zur Levenshtein-Distanz
def levenshtein_distance(s, t):
"""Gibt die Levenshtein-Distanz zwischen den Zeichenketten s und t zurück."""
if len(s) < len(t):
s, t = t, s
previous = list(range(len(t) + 1))
for i, char_s in enumerate(s, start=1):
current = [i]
for j, char_t in enumerate(t, start=1):
insertion = current[j - 1] + 1
deletion = previous[j] + 1
substitution = previous[j - 1] + (char_s != char_t)
current.append(min(insertion, deletion, substitution))
previous = current
return previous[-1]
city_file = Path("data/city_names.txt")
if city_file.exists():
cities = [line.strip() for line in city_file.read_text().splitlines() if line.strip()]
else:
# Kleine Ersatzliste, damit das Notebook auch eigenständig ausführbar bleibt.
cities = [
"Freiburg",
"Freiberg",
"Hamburg",
"Bamberg",
"Saarlouis",
"Bayreuth",
"Lüneburg",
"Nuremberg",
]
for query in ["Frieburg", "Freiborg", "Hamborg", "Sahrluis"]:
neighbors = get_neighbors(
cities,
cities,
query,
3,
distance=levenshtein_distance,
)
suggestions = [(word, dist) for word, dist, _ in neighbors]
print(f"{query:10s} -> {suggestions}")
Die nächstgelegenen Zeichenketten sind naheliegende Kandidaten für eine Rechtschreibkorrektur. Beachte, dass wir hier keine Klassenabstimmung mehr durchführen: Jedes Kandidatenwort ist im Grunde seine eigene Klassenbezeichnung. Wir betrachten einfach die nächstgelegenen bekannten Zeichenketten.
Marvin und James führen uns in das nächste Beispiel ein:
Kannst du Marvin und James helfen?
Für ein größeres Rechtschreibbeispiel benötigen wir eine englische Wortliste. Auf vielen Linux-Systemen befindet sich ein Wörterbuch unter /usr/share/dict/british-english. Eine Kopie kann außerdem mit den Tutorial-Daten bereitgestellt werden.
dictionary_candidates = [
Path("british-english.txt"),
Path("/usr/share/dict/british-english"),
]
dictionary_path = next((path for path in dictionary_candidates if path.exists()), None)
if dictionary_path is not None:
words = [line.strip() for line in dictionary_path.read_text(errors="ignore").splitlines() if line.strip()]
else:
# Ersatzwortschatz für die folgenden Beispiele.
words = [
"helpful", "hopeful", "helpless", "hippos", "shoes", "those",
"kindness", "fondness", "understand", "understands", "interstate",
"barefoot", "Blackfoot", "liberal", "liberty", "kudos", "doleful",
]
for query in ["holpful", "kundnoss", "holpposs", "thoes", "innerstand", "blagrufoo", "liberdi"]:
neighbors = get_neighbors(
words,
words,
query,
3,
distance=levenshtein_distance,
)
suggestions = [(word, dist) for word, dist, _ in neighbors]
print(f"{query:10s} -> {suggestions}")
Eine formalere Betrachtung der k-Nächste-Nachbarn-Klassifikation¶
Bisher haben wir uns k-NN intuitiv genähert und den Algorithmus direkt implementiert. Nun können wir dasselbe Verfahren mathematisch präziser beschreiben.
Wie im Kapitel Datenvorbereitung erläutert, benötigt eine überwachte Klassifikation beschriftete Trainingsdaten und üblicherweise einen getrennten Testdatensatz, um den Klassifikator zu bewerten.
Im Gegensatz zu vielen anderen Klassifikationsverfahren konstruiert der grundlegende Nächste-Nachbarn-Klassifikator während einer Trainingsphase kein explizites parametrisches Modell. Stattdessen ist der Trainingsdatensatz selbst ein wesentlicher Bestandteil des Klassifikators.
Der k-Nächste-Nachbarn-Klassifikator (k-NN) arbeitet direkt mit den gespeicherten Trainingsbeispielen. Deshalb wird k-NN häufig als instanzbasiertes Lernen oder Lazy Learning bezeichnet.
Mathematische Formulierung¶
Sei
$$ C=\{c_1,c_2,\ldots,c_m\} $$
eine Menge von $m$ möglichen Kategorien oder Klassen, zum Beispiel
$$ C=\{\text{Katze},\text{Hund},\text{Huhn}\}. $$
Weiterhin besitzen wir einen beschrifteten Trainingsdatensatz $LS$ mit $n$ Instanzen:
$$ LS=\left\{ (o_1,c_{o_1}), (o_2,c_{o_2}), \ldots, (o_n,c_{o_n}) \right\}. $$
Dabei gilt:
- $o_i$ bezeichnet eine Trainingsinstanz,
- $c_{o_i}\in C$ bezeichnet ihre bekannte Klassenbezeichnung,
- $n$ ist die Anzahl der Trainingsinstanzen,
- $m$ ist die Anzahl der möglichen Klassen.
Ist jede Klasse im Trainingsdatensatz vertreten, gilt notwendigerweise
$$ n\geq m. $$
In praktischen Anwendungen besitzen wir normalerweise viele Trainingsinstanzen pro Klasse, sodass typischerweise
$$ n\gg m. $$
gilt.
Die Klassifikationsaufgabe¶
Die Aufgabe besteht darin, einer neuen Instanz $o$, deren Klasse unbekannt ist, eine Klasse $c\in C$ zuzuweisen.
Um $o$ mit den Trainingsinstanzen zu vergleichen, verwenden wir ein Distanzmaß
$$ d(o_i,o). $$
Eine kleine Distanz bedeutet, dass zwei Instanzen bezüglich der gewählten Merkmalsdarstellung und des verwendeten Distanzmaßes nahe beieinander liegen.
Bestimmung der nächsten Nachbarn¶
Wir berechnen
$$ d(o_1,o),\;d(o_2,o),\;\ldots,\;d(o_n,o) $$
und ordnen den Trainingsdatensatz so um, dass
$$ d(o_{i_j},o)\leq d(o_{i_{j+1}},o) $$
für alle
$$ 1\leq j<n $$
gilt.
Die Menge der $k$ nächsten Nachbarn ist dann
$$ N_k(o)=\left\{ (o_{i_1},c_{o_{i_1}}), (o_{i_2},c_{o_{i_2}}), \ldots, (o_{i_k},c_{o_{i_k}}) \right\}, $$
wobei
$$ 1\leq k\leq n. $$
gilt.
Mehrheitsentscheidung¶
Für jede Klasse $c\in C$ zählen wir, wie viele der $k$ Nachbarn zu dieser Klasse gehören:
$$ V_c(o)= \sum_{(o_i,c_{o_i})\in N_k(o)} \mathbf{1}(c_{o_i}=c), $$
wobei $\mathbf{1}$ die Indikatorfunktion ist:
$$ \mathbf{1}(P)= \begin{cases} 1, & \text{falls }P\text{ wahr ist},\\ 0, & \text{sonst}. \end{cases} $$
Die vorhergesagte Klasse ist damit
$$ \hat{c}(o)= \underset{c\in C}{\operatorname{argmax}}\;V_c(o). $$
In Worten:
Wähle die Klasse, die unter den $k$ nächsten Nachbarn am häufigsten vorkommt.
Sind beispielsweise für $k=5$ die Klassenbezeichnungen
$$ A,\;A,\;B,\;A,\;B, $$
dann gilt $V_A(o)=3$ und $V_B(o)=2$, also
$$ \hat{c}(o)=A. $$
Der Spezialfall $k=1$¶
Für $k=1$ bestimmen wir die Trainingsinstanz mit der kleinsten Distanz:
$$ i^*=\underset{i}{\operatorname{argmin}}\;d(o_i,o). $$
Die vorhergesagte Klasse ist dann einfach
$$ \hat{c}(o)=c_{o_{i^*}}. $$
„Zeig mir deinen nächsten Nachbarn, und ich sage dir deine Klasse.“
Gewichtete Abstimmung¶
Anstatt jeden Nachbarn gleich zu zählen, können wir ihm ein von seiner Distanz abhängiges Gewicht zuweisen:
$$ V_c^{(w)}(o)= \sum_{(o_i,c_{o_i})\in N_k(o)} w(d(o_i,o))\,\mathbf{1}(c_{o_i}=c). $$
Die oben verwendete distanzgewichtete Implementierung benutzte
$$ w(d)=\frac{1}{1+d^2}. $$
Die vorhergesagte Klasse ist wiederum die Klasse mit der größten gewichteten Stimmenzahl.
Skalierung der Merkmale¶
Das Fruchtbeispiel hat gezeigt, dass das Distanzmaß auf der numerischen Darstellung der Merkmale arbeitet. Besitzt ein Merkmal einen wesentlich größeren numerischen Wertebereich, kann es die Distanz dominieren.
Durch Standardisierung wird ein Merkmal $x$ transformiert zu
$$ z=\frac{x-\mu}{\sigma}. $$
Die Parameter $\mu$ und $\sigma$ müssen aus den Trainingsdaten geschätzt und anschließend unverändert auf die Testdaten angewendet werden.
Was geschieht, wenn sich das Objekt bereits im Trainingsdatensatz befindet?¶
Falls
$$ (o,c)\in LS, $$
gilt für ein gewöhnliches Distanzmaß
$$ d(o,o)=0. $$
Damit ist $o$ sein eigener nächster Nachbar, wenn der Trainingsdatensatz selbst durchsucht wird. Für $k=1$ wird seine gespeicherte Klasse sofort zurückgegeben. Dies ist einer der Gründe dafür, warum wir den Klassifikator normalerweise mit einem getrennten Testdatensatz bewerten.
Wahl von $k$¶
Es gibt keinen universell optimalen Wert für $k$.
- Kleines $k$: flexibel und empfindlich gegenüber lokalen Strukturen, aber auch empfindlich gegenüber Rauschen.
- Großes $k$: stabiler, aber möglicherweise zu stark geglättet und weniger empfindlich gegenüber lokalen Strukturen.
Eine Regel wie
$$ k\approx\sqrt{n} $$
wird manchmal als grobe Ausgangsheuristik verwendet, ist aber keine allgemein gültige mathematische Regel. In der Praxis wird $k$ normalerweise als Hyperparameter behandelt und mithilfe von Validierungsdaten oder Kreuzvalidierung ausgewählt.
Bei binärer Klassifikation kann ein ungerader Wert für $k$ die Häufigkeit von Gleichständen verringern.
Gleichstände¶
Für $k=4$ könnten die Klassenbezeichnungen beispielsweise
$$ A,\;A,\;B,\;B $$
lauten.
Dann gibt es keine eindeutige Mehrheit. Ein Klassifikator benötigt deshalb eine Regel zur Auflösung eines Gleichstands. Mögliche Strategien sind die Wahl der Klasse des nächsten Nachbarn, eine distanzgewichtete Abstimmung oder eine festgelegte deterministische Regel.
Lazy Learning¶
Der k-Nächste-Nachbarn-Algorithmus ist ein Verfahren des instanzbasierten Lernens beziehungsweise des Lazy Learning. Es wird im Voraus kein explizites allgemeines Modell konstruiert; stattdessen werden die Trainingsinstanzen gespeichert, und der größte Teil der Berechnung erfolgt erst dann, wenn eine neue Anfrage klassifiziert werden soll.
Im Gegensatz dazu steht das Eager Learning, bei dem aus den Trainingsdaten zunächst ein Modell konstruiert wird.
Eager Learning:
$$ \text{Trainingsdaten} \longrightarrow \text{Modell} \longrightarrow \text{Vorhersage} $$
Lazy Learning:
$$ \text{Trainingsdaten}+\text{neues Objekt} \longrightarrow \text{nächste Nachbarn} \longrightarrow \text{Vorhersage} $$
Die obige Mathematik formalisiert genau das Verfahren, das wir zuvor in Python implementiert haben.