9.6. Eigenschaften und Varianten des k-Nächste-Nachbarn-Algorithmus#
9.6.1. Aufgabe: Immobilien klassifizieren#
Daten und Visualisierung#
In den Trainingsdaten einer Immobiliengesellschaft sind pro Immobilie die folgenden Merkmale gespeichert:
die Größe der nutzbaren Fläche der Immobilie in Quadratmeter (Merkmal Fläche)
die Wandhöhe, d.h der Abstand vom Fußboden zur Decke innerhalb der Immobilie in Metern (Merkmal Wandhöhe)
das Verhältnis zwischen der Innen- und Außenfläche wie z. B. Balkon, Garten (Merkmal Innen-Außen-Verhältnis) und
die Immobilienart (Merkmal Art), entweder Haus oder Wohnung. Dies ist das Zielmerkmal, das vorhergesagt werden soll.
Trainingsdaten
In der folgenden Tabelle sind die Trainingsdaten der Immobiliengesellschaft dargestellt. Sie wurden in Ausschnitten der Webseite entnommen.
Fläche |
Wandhöhe |
Innen-Außen-Verhältnis |
Art |
|---|---|---|---|
745 |
3,00 |
13,00 |
Haus |
470 |
4,20 |
24,00 |
Haus |
217 |
2,75 |
29,00 |
Wohnung |
198 |
2,70 |
9,00 |
Wohnung |
272 |
3,00 |
8,00 |
Haus |
64 |
2,70 |
12,00 |
Wohnung |
100 |
3,00 |
3,00 |
Wohnung |
215 |
4,20 |
21,00 |
Haus |
171 |
2,80 |
51,00 |
Wohnung |
46 |
2,70 |
6,00 |
Wohnung |
Visualisierung der Trainingsdaten als 3D-Plot
Die folgende Abbildung zeigt die Trainingsdaten in einem 3D-Plot.
Aufgabenstellung#
Analysiere die Trainingsdaten der Immobiliengesellschaft. Wie würdest du vorgehen, wenn du für einen unbekannten Datensatz die Immobilienart vorhersagen müsstest? Formuliere geeignete Kriterien.
Eine Immobilie hat die folgenden Merkmale:
Fläche: 250 Quadratmeter,
Wandhöhe: 2,7 Meter,
Innen-Außen-Verhältnis: 9.
Schätze anhand der 3D-Visualisierung ab, ob es sich um eine Wohnung oder ein Haus handelt. Betrachte dazu die drei nächsten Nachbarn der neuen Immobilie.
Bestimme die drei nächsten Nachbarn der Immobilie jetzt anhand der Tabelle oben. (Nutze die Manhattan-Distanz als Ähnlichkeitsmaß.) Welche Klassifikation ergibt sich für die Immobilie? Entspricht sie deiner Einschätzung aus der Visualisierung? Kamen bei der Berechnung der nächsten Nachbarn dieselben Immobilien heraus, die du in der vorigen Teilaufgabe als die drei nächsten Nachbarn eingeschätzt hast?
Welchee Probleme können bei Anwendung des k-nächsten-Nachbarn Verfahrens in diesem Beispiel und prinzipiell auftreten?
Mögliche Lösung
Man könnte z.B. so kategorisieren: Haus Es handelt sich um ein Haus, wenn die Fläche größer als 180, die Wandhöhe mindestens 2,70 und das Innen-Außenverhältnis größer als 14 ist.
Wohnung sonstDie nächsten drei Nachbarn sind (laut Code, s. unten):
Fläche: 198, Wandhöhe: 2,70, Innen-Außen-Verhältnis: 9, Art: Wohnung
Fläche: 215, Wandhöhe: 4,2, Innen-Außen-Verhältnis: 21, Art: Haus
Fläche: 171, Wandhöhe: 2,8, Innen-Außen-Verhältnis: 51, Art: Wohnung
Da zwei der drei nächsten Nachbarn Wohnungen sind, wird die Immobilie als Wohnung klassifiziert.
Das sind wahrscheinlich nicht die gleichen Immobilien, die du anhand der 3D-Visualisierung als die drei nächsten Nachbarn eingeschätzt hast. Ein Grund dafür ist (s. nächste Teilaufgabe), dass die Visualisierung die Achsen unterschiedlich skaliert.
Mögliche Antworten:
Die Dimensionen sind unterschiedlich skaliert. Die Fläche ist wesentlich größer als die anderen beiden Merkmale. Das führt dazu, dass bei der Berechnung der Distanz zwischen zwei Datenpunkten die Fläche einen größeren Einfluss hat als die anderen beiden Merkmale.
Das Innen-Außen-Verhältnis weicht bei einem der Punkte (mit I.-A.V. 51) stark von den anderen ab. Das führt dazu, dass dieser Punkt bei der Berechnung der Distanz einen großen Einfluss hat.
9.6.2. Umsetzung in Python#
In der folgenden Zelle wird eine neue Version des k-nächsten-Nachbarn-Algorithmus implementiert. Sie folgt unserer bisherigen Implementierung, ist aber etwas allgemeiner gehalten, insb. kann sie jetzt mit beliebig vielen Merkmalen umgehen.
Damit es nicht zu unübersichtlich wird, sind die Funktionen eingeklappt. Natürlich darfst du sie aber aufklappen und genau studieren. 😉
Show code cell content
# Achtung: Hier werden einige fortgeschrittene Python-Konzepte verwendet,
# insb. Abkürzungen für Typangaben und List Comprehensions
# Abkürzungen für komplizierte Typangaben
Datenpunkt = list
DistanzInfo = tuple[float, Datenpunkt]
def manhattan_distanz(punkt1: Datenpunkt, punkt2: Datenpunkt) -> float:
"""allgemeine Manhattan-Distanz für beliebig viele Dimensionen"""
distanz = 0
# Durchlaufe alle Dimensionen der Punkte und addiere die Differenzen
for i in range(len(punkt1)):
x_i_p1 = punkt1[i]
x_i_p2 = punkt2[i]
if not isinstance(x_i_p1, (int, float)):
continue # Wir ignorieren nicht-numerische Werte
distanz += abs(x_i_p1 - x_i_p2)
return distanz
def berechne_distanzen(punkt: Datenpunkt, daten: list[Datenpunkt]) -> list[DistanzInfo]:
"""Berechnet die Distanzen zu allen Punkten in den Daten"""
distanzen = []
for datenpunkt in daten:
distanz = manhattan_distanz(punkt, datenpunkt)
distanz_und_punkt = (distanz, datenpunkt)
# z.B. (3.5, [745, 3, 13, 1]), d.h. die Distanz des übergebenen Punktes zur Immobilie mit den
# Merkmalen 745, 3, 13, 1 beträgt 3.5
distanzen.append(distanz_und_punkt)
return distanzen
def k_naechste_nachbarn(k: int, distanzen: list[DistanzInfo]) -> list[Datenpunkt]:
"""Bestimmt die k nächsten Nachbarn"""
distanzen.sort() # sortiert die Liste nach den Distanzen
k_nachbarn = [punkt for distanz, punkt in distanzen[:k]] # nimmt die ersten k Punkte (Distanzen sind nicht mehr nötig)
return k_nachbarn
def haeufigkeiten_ermitteln(nachbarn: list[Datenpunkt]) -> dict[str, int]:
"""Ermittelt die Häufigkeiten der verschiedenen Klassen"""
haeufigkeiten = {}
for nachbar in nachbarn:
klasse = nachbar[-1] # Die Klasse ist das letzte Element des Punktes
if klasse in haeufigkeiten:
haeufigkeiten[klasse] += 1
else:
haeufigkeiten[klasse] = 1
return haeufigkeiten
def haeufigsten_wert_ermitteln(haeufigkeiten: dict[str, int]) -> str:
"""Ermittelt den häufigsten Wert"""
haeufigste_klasse = ""
max_haeufigkeit = 0
for klasse, haeufigkeit in haeufigkeiten.items():
if haeufigkeit > max_haeufigkeit:
haeufigste_klasse = klasse
max_haeufigkeit = haeufigkeit
return haeufigste_klasse
def k_naechste_nachbarn_bestimmen(unbekannter_punkt: Datenpunkt, gelabelte_daten: list[Datenpunkt], k: int) -> tuple[str, list[Datenpunkt]]:
"""Bestimmt die Klasse des unbekannten Punktes"""
distanzen = berechne_distanzen(unbekannter_punkt, gelabelte_daten) # [(3.5, [745, 3, 13, 1]), ... ]
k_nachbarn = k_naechste_nachbarn(k, distanzen) # Diesmal haben wir die Sortierung hier drin "versteckt"
haeufigkeiten = haeufigkeiten_ermitteln(k_nachbarn)
klasse = haeufigsten_wert_ermitteln(haeufigkeiten)
return klasse, k_nachbarn
daten = [
[745, 3.0, 13, "Haus"],
[470, 4.2, 24, "Haus"],
[217, 2.75, 29, "Wohnung"],
[198, 2.7, 9, "Wohnung"],
[272, 3.0, 8, "Haus"],
[64, 2.7, 12, "Wohnung"],
[100, 3.0, 3, "Wohnung"],
[215, 4.2, 21, "Haus"],
[171, 2.8, 51, "Wohnung"],
[46, 2.7, 6, "Wohnung"],
]
# Testen des Algorithmus mit dem Punkt aus der Aufgabenstellung
unbekannter_punkt = [180, 2.7, 14]
print(f"Unbekannter Punkt: {unbekannter_punkt}")
k = 3
klasse, k_nachbarn = k_naechste_nachbarn_bestimmen(unbekannter_punkt, daten, k)
print(f"Die {k} nächsten Nachbarn des unbekannten Punktes sind:")
for nachbar in k_nachbarn:
print(nachbar)
print(f"Der unbekannte Punkt wird klassifiziert als '{klasse}'")
Unbekannter Punkt: [180, 2.7, 14]
Die 3 nächsten Nachbarn des unbekannten Punktes sind:
[198, 2.7, 9, 'Wohnung']
[215, 4.2, 21, 'Haus']
[171, 2.8, 51, 'Wohnung']
Der unbekannte Punkt wird klassifiziert als 'Wohnung'
9.7. Normalisierung von Daten#
Bei der Anwendung des k-nächsten-Nachbarn-Algorithmus kann es vorkommen, dass einige Merkmale (Features) einen größeren Einfluss auf die Berechnung der Distanzen haben als andere. Dies liegt daran, dass die Wertebereiche der Merkmale unterschiedlich sein können. Um dies zu verhindern, sollten die Daten normalisiert werden.
Die Normalisierung ist ein Verfahren, bei dem die Werte der Merkmale in einen gemeinsamen Bereich transformiert werden. Eine gängige Methode ist die Min-Max-Normalisierung, bei der die Werte eines Merkmals so skaliert werden, dass sie in einem Bereich von 0 bis 1 liegen.
Die Formel für die Min-Max-Normalisierung lautet:
Dabei ist:
\(x\) der ursprüngliche Wert des Merkmals,
\(x_{min}\) der minimale Wert des Merkmals in den Daten,
\(x_{max}\) der maximale Wert des Merkmals in den Daten,
\(x_{norm}\) der normalisierte Wert des Merkmals.
Im nächsten Schritt werden wir die Normalisierung der Daten implementieren und den k-nächsten-Nachbarn-Algorithmus auf die normalisierten Daten anwenden.