Merke: Der k-nächste-Nachbarn-Algorithmus (KNN) ordnet einen neuen Datenpunkt einer Klasse zu. Er berechnet die Abstände des neuen Punkts zu allen Trainingsdaten und wählt die k Trainingsdaten mit den kleinsten Abständen aus – die k nächsten Nachbarn. Der neue Punkt bekommt die Klasse, die unter diesen Nachbarn am häufigsten vorkommt. Die Anzahl k der Nachbarn wird vorher festgelegt.
Künstliche Intelligenz · Klassifikation
Der k-nächste-Nachbarn-Algorithmus: Idee und Abstand
Aufgabe 7
Finde heraus, wie man einen neuen Datenpunkt mithilfe ähnlicher Trainingsdaten einer Klasse zuordnet und wie man misst, wie nah sich zwei Punkte sind.
Dein Bearbeitungsstand wird in diesem Browser gespeichert.
Welche Größe passt?
Welche Größe passt?
Am KI-Gymnasium gibt es Schulshirts in den Größen S, M und L. Für 15 Personen sind Körpergröße, Brustumfang und gekaufte Shirtgröße bekannt – das sind die Trainingsdaten.
Eine neue Person mit 183 cm Körpergröße und 106 cm Brustumfang möchte ein Schulshirt. Wähle die passende Größe und kreuze alle passenden Begründungen an.
Welche Shirtgröße passt?
Hilfe 1: Wo liegt die Person?
Suche die neue Person im Diagramm: 183 cm nach rechts, 106 cm nach oben.
Hilfe 2: Umgebung ansehen
Schau dir die Punkte an, die direkt um die neue Person herum liegen. Welche Form und Farbe haben sie?
Hilfe 3: Teillösung
Die drei Punkte, die der neuen Person am nächsten liegen, sind Dreiecke – sie gehören zu M.
Die k nächsten Nachbarn
Die k nächsten Nachbarn
Stelle k = 1 und k = 5 ein und bestimme jeweils die Shirtgröße der neuen Person N(186|110). Begründe danach, warum sich das Ergebnis ändert.
Anzahl k der nächsten Nachbarn
bei k = 1:
bei k = 5:
Hilfe 1: Linien zählen
Zähle nur die Punkte, zu denen vom neuen Punkt eine Linie führt. Die Auszählung neben der Grafik hilft dir.
Hilfe 2: Mehrheit
Die neue Person bekommt die Größe, die unter den verbundenen Punkten am häufigsten vorkommt.
Hilfe 3: Teillösung
Bei k = 1 führt die einzige Linie zum Punkt 185|109 mit Größe M. Bei k = 5 kommen vier weitere Punkte hinzu.
Die Schritte des Verfahrens
Ordne die Schritte des Verfahrens in die richtige Reihenfolge. Ziehe die Karten in die nummerierten Felder oder tippe erst eine Karte und dann ein Feld an – eine Karte gehört nicht dazu.
Hilfe 1: Wo anfangen?
Bevor man die nächsten Punkte auswählen kann, muss man wissen, wie weit jeder Punkt entfernt ist.
Hilfe 2: Vom Ende her denken
Die Zuordnung zu einer Klasse ist das Ergebnis – sie steht am Ende. Davor muss gezählt werden.
Hilfe 3: Teillösung
Schritt 1 ist „Abstände des neuen Punkts zu allen Trainingsdaten berechnen“, Schritt 4 ist „Den neuen Punkt dieser Klasse zuordnen“.
Regel für Gleichstände: Wir wählen k immer ungerade (1, 3, 5, 7). Bei zwei Klassen kann es dann keinen Gleichstand geben. Bei drei Klassen wie S, M und L ist trotzdem ein Gleichstand möglich, zum Beispiel bei k = 3 mit je einem Nachbarn pro Klasse. Dann entscheidet der nächstgelegene Nachbar.
Euklidischer Abstand
Wie misst man „nah“? – Euklidischer Abstand
Im Diagramm siehst du, welche Punkte nah beieinanderliegen. Ein Computer muss das ausrechnen. N ist die neue Person aus Reiter 1, A und B sind zwei Trainingspersonen.
Berechne den Abstand von N zu A und von N zu B, also die Länge der direkten Verbindung. Runde auf zwei Nachkommastellen.
- N (neue Person)
- A und B (Trainingspersonen)
- gewählte Verbindung
Gewähltes Paar
cm
cm
Hilfe 1: Dreieck erkennen
Blende das Dreieck ein. Die direkte Verbindung von N zum anderen Punkt ist die längste Seite eines rechtwinkligen Dreiecks.
Hilfe 2: Seiten bestimmen
Die beiden kurzen Seiten verlaufen parallel zu den Achsen. Ihre Längen sind die Unterschiede der x-Werte und der y-Werte der beiden Punkte.
Hilfe 3: Teillösung
Für N und A sind die kurzen Seiten 3 und 4 lang. Nach dem Satz des Pythagoras gilt d² = 3² + 4².
Merke: Euklidischer Abstand. Der euklidische Abstand d zweier Punkte A(x₁|y₁) und B(x₂|y₂) ist die Länge ihrer direkten Verbindung. Die Differenzen der Koordinaten bilden die Katheten eines rechtwinkligen Dreiecks, die Verbindung ist die Hypotenuse. Nach dem Satz des Pythagoras gilt:
d = √((x₂ − x₁)² + (y₂ − y₁)²)
Beispiel: N(183|106) und A(180|102) unterscheiden sich um 3 und um 4, also d = √(3² + 4²) = √25 = 5.
Manhattan-Metrik
Manhattan-Metrik
In Manhattan verlaufen die Straßen wie ein Gitter. Ein Taxi kann nicht quer durch die Häuserblöcke fahren, sondern nur entlang der Straßen.
Bestimme, wie viele Blocklängen das Taxi von der Haltestelle H zum Kino K mindestens fahren muss.
- rote Route (durchgezogen)
- blaue Route (gestrichelt)
- direkte Verbindung (gepunktet)
Blocklängen
Hilfe 1: Route abzählen
Fahre eine der beiden eingezeichneten Routen mit dem Finger ab und zähle jede Blocklänge.
Hilfe 2: Richtungen trennen
Jede Route besteht aus Stücken nach rechts und Stücken nach oben. Zähle beide Richtungen getrennt und addiere.
Hilfe 3: Teillösung
Nach rechts sind es 5 Blocklängen. Zähle noch die Blocklängen nach oben dazu.
Merke: Manhattan-Metrik. Beim Manhattan-Abstand bewegt man sich nur parallel zu den Achsen, wie ein Taxi in den rechtwinkligen Straßen von Manhattan. Man addiert die Beträge der Koordinatendifferenzen:
d = |x₂ − x₁| + |y₂ − y₁|
Für H(1|1) und K(6|4): d = |6 − 1| + |4 − 1| = 5 + 3 = 8.
Wer ist der nächste Nachbar?
Berechne für P(0|0) die Abstände zu A(3|3) und zu B(5|0) – euklidisch und nach Manhattan. Runde auf zwei Nachkommastellen.
- P, A und B (Punkte)
| euklidisch | Manhattan | |
|---|---|---|
| P zu A | ||
| P zu B |
Hilfe 1: Ablesen
Lies in der kleinen Grafik ab, wie weit A und B in x- und in y-Richtung von P entfernt sind.
Hilfe 2: Zwei Rechenwege
Euklidisch: direkte Verbindung über ein rechtwinkliges Dreieck wie in Reiter 3. Manhattan: Wege entlang der Achsen addieren.
Hilfe 3: Teillösung
Von P nach A sind es 3 nach rechts und 3 nach oben, von P nach B 5 nach rechts und 0 nach oben.
Merke: Abstandsmaße. Der euklidische Abstand und der Manhattan-Abstand sind zwei verschiedene Abstandsmaße. Der KNN-Algorithmus kann mit jedem Abstandsmaß arbeiten. Welche Trainingsdaten die nächsten Nachbarn sind, kann vom gewählten Abstandsmaß abhängen. Der Manhattan-Abstand ist nie kleiner als der euklidische Abstand.
Schulshirts klassifizieren
Schulshirts klassifizieren
Berechne die beiden fehlenden euklidischen Abstände zur neuen Person N(178|98) und runde auf zwei Nachkommastellen. Markiere dann durch Antippen der Zeilen die k = 5 nächsten Nachbarn und bestimme die Shirtgröße.
| Nachbar | Nr. | Körpergröße x (cm) | Brustumfang y (cm) | Größe | Abstand d zu N |
|---|
Shirtgröße der neuen Person
Hilfe 1: Differenzen
Bestimme für jede fehlende Zeile, um wie viel sich Körpergröße und Brustumfang von N(178|98) unterscheiden.
Hilfe 2: Wie in Reiter 3
Berechne mit den beiden Differenzen wie in Reiter 3 den euklidischen Abstand. Markiere danach die fünf kleinsten Werte der Abstandsspalte.
Hilfe 3: Teillösung
Für Nr. 3 (180|102) sind die Differenzen 2 und 4, also d = √(2² + 4²) = √20. Der kleinste Abstand der Tabelle gehört zu Nr. 11.
Erläutern
Erläutere an diesem Beispiel, wie der KNN-Algorithmus die Shirtgröße bestimmt.
0 von 600 Zeichen
Hinweis: Gib keine personenbezogenen Informationen ein. Deine Antwort wird zur automatischen Auswertung an den Skriptserver und dort an ein KI-System übertragen.
Abschlussquiz
Das Wichtigste sichern
- Der k-nächste-Nachbarn-Algorithmus (KNN) ordnet einen neuen Datenpunkt der Klasse zu, die unter seinen k nächsten Nachbarn in den Trainingsdaten am häufigsten vorkommt.
- Wir wählen k ungerade. Bleibt bei drei oder mehr Klassen trotzdem ein Gleichstand, entscheidet der nächstgelegene Nachbar.
- Euklidischer Abstand: d = √((x₂ − x₁)² + (y₂ − y₁)²) – die Länge der direkten Verbindung.
- Manhattan-Abstand: d = |x₂ − x₁| + |y₂ − y₁| – der Weg entlang der Achsen. Er ist nie kleiner als der euklidische Abstand.
- Welche Punkte die nächsten Nachbarn sind, kann vom Abstandsmaß abhängen.
Abschlussquiz
Kreuze alle richtigen Aussagen an. Bei manchen Fragen sind mehrere Antworten richtig.
0 von 6 Fragen vollständig richtig