Klassifizieren mit Trenngeraden, k-nächsten Nachbarn und Entscheidungsbäumen

Klassifizieren mit Trenngeraden, k-nächsten Nachbarn und Entscheidungsbäumen

https://bildung.social/@oerinformatik/

https://oer-informatik.de/klassifikation-knn

Klassifikation, Trenngerade, lineare Klassifikation, k-nächste Nachbarn, kNN, euklidische Distanz, Normalisierung, Entscheidungsbaum, ID3, Entropie, Informationsgewinn, maschinelles Lernen

tl/dr; (ca. 22 min Lesezeit): Wie ordnet ein Programm einen neuen Datensatz einer Klasse zu? Der Artikel stellt drei einfache Verfahren des überwachten Lernens vor: Trenngeraden (mit Geradengleichung, Klassifizieren durch Hinschauen und durch Rechnen, Auswahl einer guten Geraden und Test mit Testdaten), die k-nächsten Nachbarn (euklidische Distanz, Wahl von k, Aufbereitung der Daten) und Entscheidungsbäume nach ID3 (Entropie und Informationsgewinn). Zum Schluss vergleicht er die Verfahren und zeigt, wie Du eine Auswahl begründest [AI-Assisted]. (Zuletzt geändert am 29.10.2026)

Schon fit in diesem Thema? Nutze die Kann-Liste und die Leitfragen unter dem Artikel als Checkliste, ob Du die relevanten Kompetenzen bereits hast. Hier klicken, um Kann-Liste ein- oder auszublenden

Ist dieser Akku bald defekt? Fällt die Maschine in den nächsten Tagen aus? Ist diese E-Mail Spam? Alle drei Fragen verlangen eine Klassifikation: Ein neuer Datensatz soll einer von mehreren bekannten Klassen zugeordnet werden. Grundlage sind Daten aus der Vergangenheit, bei denen die Klasse bekannt ist. Dieser Artikel baut auf der Kann-Liste des Artikels Grundlagen des maschinellen Lernens auf: Begriffe wie Merkmal (Feature), Zielwert (Label), Trainings- und Testdaten sowie Overfitting werden hier vorausgesetzt.

Klassifikation im Merkmalsraum

Hat jeder Datensatz zwei Merkmale, lässt er sich als Punkt in einem Koordinatensystem darstellen: das erste Merkmal auf der x-Achse, das zweite auf der y-Achse. So entsteht ein Streudiagramm (engl. Scatter Plot). Die Klasse zeigst Du durch Form und Farbe des Symbols, in diesem Artikel z. B. ein blaues Dreieck ▲ für Klasse A und ein oranges Quadrat ■ für Klasse B. Unterschiedliche Formen bleiben auch beim Schwarz-Weiß-Druck und bei Farbsehschwäche lesbar. Bei drei Merkmalen bräuchte man einen Raum, bei noch mehr Merkmalen kann man nicht mehr zeichnen, aber genauso rechnen. Man spricht allgemein vom Merkmalsraum.

Beim Übertragen von Werten aus einer Tabelle hilft dieses Vorgehen:

1. Achsen beschriften (Merkmal und Einheit) und Maßstab so wählen, dass alle Werte hineinpassen.

2. Je Datensatz den x-Wert auf der x-Achse suchen, senkrecht darüber bis zum y-Wert gehen und das Symbol der Klasse setzen.

3. Trainings- und Testdaten unterscheidbar markieren, z. B. Testdaten nur als Umriss (nicht ausgefüllt) zeichnen und das in der Legende angeben.

Alle drei Verfahren dieses Artikels gehören zum überwachten Lernen: Sie lernen aus Trainingsdaten mit bekannter Klasse und werden mit zurückgehaltenen Testdaten überprüft.

Trenngeraden: linear klassifizieren

Liegen die Punkte der beiden Klassen in getrennten Bereichen des Streudiagramms, kann man eine Gerade so hindurchlegen, dass auf der einen Seite (fast) nur Punkte der einen Klasse liegen und auf der anderen Seite die der anderen Klasse. Eine solche Trenngerade ist das einfachste Modell eines linearen Klassifikators. Das Lernen besteht darin, eine möglichst gute Lage der Geraden zu finden.

Die Geradengleichung

Eine Gerade wird durch eine Funktionsvorschrift der Form

y = m \cdot x + b

beschrieben. Die beiden Parameter haben eine feste Bedeutung:

• m ist die Steigung: Um so viel ändert sich y, wenn x um 1 größer wird. Ist m positiv, steigt die Gerade nach rechts an, ist m negativ, fällt sie, bei m = 0 verläuft sie waagerecht (z. B. y = 12).

• b ist der y-Achsenabschnitt: An dieser Stelle schneidet die Gerade die y-Achse, denn für x = 0 gilt y = b.

Zum Einzeichnen genügen zwei Punkte: Der erste ist (0 | b), den zweiten erhältst Du, indem Du einen x-Wert am anderen Ende der Achse einsetzt. Für y = 0,5x + 3 sind das (0 | 3) und (12 | 9).

Umgekehrt lässt sich die Gleichung aus zwei Punkten (x₁ | y₁) und (x₂ | y₂) aufstellen. Zuerst die Steigung, dann den Achsenabschnitt:

m = \frac{y_2 - y_1}{x_2 - x_1} \qquad b = y_1 - m \cdot x_1

Beispiel mit (2 | 4) und (10 | 8): m = \frac{8 - 4}{10 - 2} = 0{,}5 und b = 4 - 0{,}5 \cdot 2 = 3, also y = 0,5x + 3.

Klassifizieren durch Hinschauen

Ein neuer Datenpunkt wird der Klasse zugeordnet, auf deren Seite der Geraden er liegt. Welche Seite zu welcher Klasse gehört, ergibt sich aus den Trainingsdaten: Im Bild oben liegen die Dreiecke (Klasse A) oberhalb, die Quadrate (Klasse B) unterhalb der Geraden. Ein neuer Punkt oberhalb der Geraden wird also als A, ein Punkt unterhalb als B vorhergesagt. Bei einer anderen Lage der Daten kann es genau umgekehrt sein; schau deshalb immer nach, wo die Trainingspunkte liegen.

Klassifizieren durch Rechnen

Ein Programm kann nicht „hinschauen“, aber es kann vergleichen. Die Gerade y = m · x + b teilt die Ebene in zwei Halbebenen: Für alle Punkte oberhalb gilt die Ungleichung

y > m \cdot x + b

für alle Punkte unterhalb gilt y < m · x + b. Die Klassifikation ist also nichts anderes als das Prüfen einer Ungleichung. Bringst Du alles auf eine Seite, entsteht der Entscheidungswert

g(x, y) = y - (m \cdot x + b)

Sein Vorzeichen zeigt die Seite: g > 0 heißt oberhalb, g < 0 heißt unterhalb, g = 0 heißt genau auf der Geraden (dafür braucht es eine feste Regel, welche Klasse gilt). Anschaulich ist g der senkrechte Abstand in y-Richtung zwischen dem Punkt und der Geraden: Der Klammerausdruck m · x + b ist die Höhe der Geraden an der Stelle x (der Funktionswert f(x)); er wird von der gemessenen Höhe y abgezogen.

Beispiele mit y = 0,5x + 3 (siehe Bild oben):

• Punkt N (9 | 9): Die Gerade hat bei x = 9 die Höhe 0,5 · 9 + 3 = 7,5. g = 9 − 7,5 = +1,5, also oberhalb und damit Klasse A.
• Punkt M (4 | 3): Höhe der Geraden 0,5 · 4 + 3 = 5. g = 3 − 5 = −2, also unterhalb und damit Klasse B.

Im Programm ist das eine einzige Verzweigung. Welche Klasse zu welchem Vorzeichen gehört, steht nicht in der Formel, sondern wurde vorher an den Trainingsdaten abgelesen:

def klasse(x: float, y: float, m: float = 0.5, b: float = 3.0) -> str:
    g = y - (m * x + b)          # Entscheidungswert
    return "A" if g > 0 else "B" # Regel: Punkte auf der Geraden zählen zu B

Der Betrag von g sagt zusätzlich etwas über die Sicherheit aus: Ein Punkt weit weg von der Geraden ist eindeutig, ein Punkt mit g nahe 0 liegt im Grenzbereich.

Eine gute Trenngerade finden

Meist gibt es viele Geraden, die die Trainingsdaten trennen. Zwei Kriterien helfen bei der Wahl:

1. Möglichst wenige Fehler: Zähle für jede Gerade, wie viele Trainingspunkte auf der falschen Seite liegen. Die Gerade mit weniger Fehlern trennt besser.

2. Möglichst breiter Korridor: Verschiebt man eine fehlerfreie Gerade parallel nach oben und unten, bis sie den ersten Punkt berührt, entsteht ein punktfreier Korridor (engl. Margin). Die Punkte am Rand des Korridors heißen Stützpunkte (engl. support vectors). Je breiter der Korridor und je mittiger die Gerade darin liegt, desto mehr Spielraum haben neue Punkte, die etwas anders liegen als die Trainingspunkte, bevor sie auf der falschen Seite landen.

Im Bild trennen beide Geraden fehlerfrei. Gerade P läuft aber dicht an einem Quadrat vorbei: Ein neuer Punkt der Klasse B, der nur wenig weiter links oben liegt, würde schon falsch eingeordnet. Gerade Q lässt nach beiden Seiten etwa anderthalbmal so viel Platz und ist deshalb die robustere Wahl.

Verfahren des maschinellen Lernens erledigen das automatisch. Das Perzeptron verschiebt und dreht die Gerade schrittweise bei jedem falsch eingeordneten Trainingspunkt ein wenig. Eine Support Vector Machine (SVM) sucht gezielt die Gerade mit dem größten Abstand (engl. Margin) zu den Punkten beider Klassen.

Mit Testdaten prüfen

Ob eine Gerade auch bei neuen Fällen taugt, zeigen erst die Testdaten: Sie wurden beim Festlegen der Geraden nicht verwendet, ihre Klasse ist aber bekannt. Für jeden Testpunkt vergleichst Du die Vorhersage (Seite der Geraden) mit der tatsächlichen Klasse und zählst richtige und falsche Vorhersagen. Daraus ergibt sich die Trefferquote (Genauigkeit, engl. Accuracy):

\text{Trefferquote} = \frac{\text{Anzahl richtiger Vorhersagen}}{\text{Anzahl aller Vorhersagen}}

Bei 9 richtigen von 10 Testpunkten beträgt sie 9/10 = 90 %. Bei wenigen Testdaten ist dieser Wert allerdings unsicher, ein einzelner Punkt ändert ihn schon um 10 Prozentpunkte. Kommt es auf eine Klasse besonders an (z. B. „Ausfall“), lohnt ein Blick darauf, welche Art von Fehler gemacht wurde: Ein übersehener Ausfall ist meist teurer als eine unnötige Wartung.

Grenzen von Trenngeraden

Eine Gerade kann nur linear trennbare Daten sauber trennen. Liegen die Punkte einer Klasse z. B. ringförmig um die andere, gibt es keine passende Gerade. Dann helfen gekrümmte Grenzen, mehrere Geraden (wie in neuronalen Netzen) oder ganz andere Verfahren wie kNN und Entscheidungsbäume. Bei drei Merkmalen wird aus der Trenngeraden eine Trennebene, bei noch mehr Merkmalen spricht man von einer Hyperebene; das Rechenprinzip (Seite bestimmen über ein Vorzeichen) bleibt gleich.

k-nächste Nachbarn (kNN)

Das Verfahren der k-nächsten Nachbarn (engl. k-nearest neighbors, kNN) beruht auf einer einfachen Idee: Ähnliche Fälle gehören meist zur selben Klasse. Um einen neuen Datenpunkt einzuordnen, „befragt“ man die k Trainingspunkte, die ihm am ähnlichsten sind, und übernimmt die Klasse, die unter diesen Nachbarn am häufigsten vorkommt (Mehrheitsentscheidung).

Ablauf

1. Abstand berechnen: Für den neuen Punkt den Abstand zu jedem Trainingspunkt berechnen (meist euklidische Distanz, siehe unten).

2. Nachbarn bestimmen: Die Trainingspunkte nach Abstand sortieren und die k nächsten auswählen.

3. Abstimmen: Die Klasse wählen, die unter den k Nachbarn am häufigsten vertreten ist.

kNN baut vorab kein Modell auf, sondern merkt sich nur die Trainingsdaten und rechnet erst, wenn eine Anfrage kommt. Man nennt es deshalb einen faulen Lerner (engl. lazy learner). Neue Trainingsdaten lassen sich sofort berücksichtigen, indem man sie einfach hinzufügt; dafür ist jede einzelne Vorhersage aufwendig, weil die Abstände zu allen Trainingspunkten berechnet werden müssen.

Abstand messen: euklidische Distanz

Der übliche Abstand ist die euklidische Distanz, also die Länge der geraden Verbindungslinie. Für zwei Punkte p und q mit n Merkmalen gilt (Satz des Pythagoras, erweitert auf n Dimensionen):

d(p, q) = \sqrt{(p_1 - q_1)^2 + (p_2 - q_2)^2 + \dots + (p_n - q_n)^2}

Du bildest also je Merkmal die Differenz, quadrierst sie, addierst alle Quadrate und ziehst die Wurzel. Die Reihenfolge der Punkte spielt keine Rolle, weil das Quadrat das Vorzeichen beseitigt.

Beispiel: Ein Fahrradgeschäft schlägt die Rahmengröße S, M oder L vor. Eine neue Kundin ist 178 cm groß und hat eine Schrittlänge von 82 cm. Bekannt sind sechs Kundinnen und Kunden, die mit ihrer Größe zufrieden waren:

Die drei nächsten Nachbarn sind R6 (L), R3 (M) und R4 (L). Bei k = 3 steht es 2 : 1 für L, die Kundin bekommt Rahmengröße L vorgeschlagen.

Neben der euklidischen Distanz gibt es weitere Abstandsmaße, z. B. die Manhattan-Distanz (Summe der Beträge der Differenzen, wie Wege in einem Straßenraster).

Einfluss von k

Wie viele Nachbarn befragt werden, bestimmt der Parameter k. Er wird nicht gelernt, sondern vorher festgelegt (ein sogenannter Hyperparameter). Das Ergebnis kann stark von k abhängen. Im folgenden Beispiel sind die sieben nächsten Nachbarn des neuen Punkts nach ihrem Abstand nummeriert:

Bei k = 1 entscheidet ein einzelnes Quadrat, das zufällig am nächsten liegt. Bei k = 3 und 5 überwiegen die Dreiecke der näheren Umgebung. Bei k = 7 zählen auch die weiter entfernten Quadrate mit, und die Vorhersage kippt zurück.

Für die Wahl von k gelten diese Kriterien:

• k nicht zu klein: Bei k = 1 genügt ein einzelner Ausreißer oder Messfehler in der Nähe, um die Entscheidung zu kippen. Das Modell passt sich zu stark an einzelne Trainingspunkte an (Overfitting).

• k nicht zu groß: Je größer k, desto weiter entfernte und damit unähnlichere Punkte stimmen mit. Die Entscheidung wird unspezifisch; im Extremfall (k = Anzahl aller Trainingspunkte) wird immer die häufigste Klasse vorhergesagt (Underfitting).

• k ungerade bei zwei Klassen: Dann kann es kein Unentschieden geben. Bei mehr Klassen hilft das nicht vollständig; dann entscheidet z. B. der nächste Nachbar oder eine Gewichtung.

• k mit Daten bestimmen: Mehrere Werte ausprobieren und den wählen, der auf Validierungsdaten die beste Trefferquote liefert. Als Startwert wird oft die Wurzel aus der Anzahl der Trainingsdaten genannt.

Eine Erweiterung ist das gewichtete kNN: Nähere Nachbarn zählen mehr als entfernte, z. B. mit dem Gewicht 1/d.

Daten für kNN aufbereiten

Weil kNN mit Abständen rechnet, müssen alle Merkmale Zahlen sein und vergleichbare Größenordnungen haben. Die Grundlagen dazu stehen im Abschnitt Daten aufbereiten des Grundlagenartikels; für kNN sind drei Punkte entscheidend:

1. Kategoriale Werte kodieren: Geordnete Kategorien (z. B. Qualität niedrig, mittel, hoch) erhalten Zahlen in ihrer Reihenfolge, etwa 1, 2, 3. Ungeordnete Kategorien (z. B. Farbe) bekommen je eine eigene 0/1-Spalte (One-Hot-Kodierung), damit keine falsche Reihenfolge entsteht.

2. Skalieren: Ein Merkmal mit großen Zahlen beherrscht sonst die Distanz. Ergänzt man im Rahmenbeispiel die Jahresfahrleistung in Kilometern, unterscheiden sich die Kundinnen und Kunden dort um Tausende, bei der Körpergröße nur um wenige Zentimeter. Die Distanz würde fast nur noch die Fahrleistung messen. Üblich ist die Min-Max-Normalisierung auf den Bereich 0 bis 1:

   x_{norm} = \frac{x - x_{min}}{x_{max} - x_{min}}

   Für die Differenz zweier Werte genügt es, durch die Spannweite zu teilen: \frac{p_i - q_i}{x_{max} - x_{min}}. Alternativ wird standardisiert (Mittelwert abziehen, durch die Standardabweichung teilen).

3. Kodierte Kategorien passend skalieren: Die Zahlen 1, 2, 3 müssen zur Größenordnung der übrigen Merkmale passen. Liegen alle anderen Merkmale zwischen 0 und 1, werden sie z. B. zu 0, 0,5 und 1. Soll ein Merkmal bewusst stärker oder schwächer zählen, multipliziert man seine normierten Werte mit einem Gewichtsfaktor; mit dem Faktor 2 wird aus 0, 0,5, 1 also 0, 1, 2, und ein Stufenunterschied zählt doppelt so viel wie vorher. Die Wahl ist eine fachliche Entscheidung über das Gewicht des Merkmals.

Außerdem gilt wie immer: nur Merkmale verwenden, die mit der Klasse zusammenhängen. Jedes unnötige Merkmal verändert die Abstände und verschlechtert kNN, besonders bei vielen Merkmalen (Fluch der Dimensionalität, engl. curse of dimensionality: in hochdimensionalen Räumen sind alle Punkte ähnlich weit voneinander entfernt).

Entscheidungsbäume und ID3

Ein Entscheidungsbaum (engl. decision tree) stellt eine Folge von Fragen dar. Jeder innere Knoten prüft ein Merkmal, jede Kante steht für eine mögliche Antwort, und jedes Blatt nennt die vorhergesagte Klasse. Um einen neuen Datensatz einzuordnen, beginnt man an der Wurzel und folgt den Kanten, die zu seinen Werten passen, bis man ein Blatt erreicht.

Der Baum lässt sich direkt als Regeln lesen: „Wenn das Wetter sonnig und der Wind schwach ist, findet die Tour statt.“ Diese Nachvollziehbarkeit ist die große Stärke von Entscheidungsbäumen.

Wie ID3 den Baum aufbaut

Der Algorithmus ID3 (Iterative Dichotomiser 3, J. Ross Quinlan, 1986) baut den Baum aus den Trainingsdaten von oben nach unten auf:

1. Für jedes noch nicht verwendete Merkmal berechnen, wie gut es die Datensätze nach Klassen trennt (Informationsgewinn, engl. information gain).

2. Das Merkmal mit dem größten Informationsgewinn wird zum Knoten; für jeden seiner Werte entsteht eine Kante mit den passenden Datensätzen.

3. Für jede Teilmenge wiederholen. Gehören alle Datensätze einer Teilmenge zur selben Klasse, wird sie ein Blatt. Sind keine Merkmale mehr übrig, entscheidet im Blatt die Mehrheit der Datensätze.

Wie „gemischt“ eine Menge S ist, misst die Entropie (p_i ist der Anteil der Klasse i):

H(S) = -\sum_i p_i \cdot \log_2 p_i

Sie ist 0, wenn alle Datensätze zur selben Klasse gehören, und bei zwei Klassen im Verhältnis 1 : 1 genau 1. Der Informationsgewinn eines Merkmals A ist die Entropie vorher minus die gewichtete Entropie der Teilmengen nach der Aufteilung:

IG(S, A) = H(S) - \sum_{v} \frac{|S_v|}{|S|} \cdot H(S_v)

Beispiel: Eine Freizeitgruppe hat zehn geplante Radtouren erfasst.

Insgesamt 5-mal ja und 5-mal nein, also H(S) = 1.

• Wetter: sonnig 4 Touren (2 : 2, H = 1), bewölkt 3 (3 : 0, H = 0), regnerisch 3 (0 : 3, H = 0). IG = 1 − (4/10 · 1 + 3/10 · 0 + 3/10 · 0) = 0,6.

• Wind: schwach 5 (4 : 1, H ≈ 0,722), stark 5 (1 : 4, H ≈ 0,722). IG = 1 − 0,722 = 0,278.

• Temperatur: warm 3 (2 : 1), mild 4 (2 : 2), kalt 3 (1 : 2). IG ≈ 0,049.

Wetter hat den größten Informationsgewinn und wird zur Wurzel. Bewölkt und regnerisch sind sofort eindeutig (Blätter). Für die vier sonnigen Touren wird erneut gerechnet: Wind trennt sie vollständig (IG = 1), Temperatur nur teilweise (IG = 0,5). Es entsteht der Baum aus dem Bild oben; die Temperatur wird gar nicht gebraucht.

Numerische Merkmale, Overfitting und Pruning

ID3 arbeitet mit kategorialen Merkmalen. Zahlenwerte wie Temperatur in °C oder Betriebsstunden müssen vorher in Klassen eingeteilt werden (z. B. „≤ 500 h“ und „> 500 h“); die Grenzen beeinflussen das Ergebnis. Der Nachfolger C4.5 und das verwandte Verfahren CART suchen solche Schwellenwerte selbst.

Ein Baum, der so lange weiterteilt, bis jedes Blatt rein ist, lernt auch Zufälle und Messfehler der Trainingsdaten auswendig: Overfitting. Gegenmittel sind eine begrenzte Tiefe, eine Mindestanzahl Datensätze je Blatt oder das nachträgliche Zurückschneiden (Pruning). Robuster sind Random Forests, die viele Bäume aus zufälligen Teilen der Daten bilden und abstimmen lassen.

Ein fertiger Baum ist starr: Kommen neue Trainingsdaten hinzu, muss er neu aufgebaut werden. Dafür sind Vorhersagen sehr schnell, weil nur wenige Fragen beantwortet werden.

Welches Verfahren passt?

Eine Entscheidung begründest Du immer mit den Eigenschaften der vorliegenden Daten und Anforderungen, nicht allgemein. Beispiele:

• Viele numerische Messwerte und laufend neue Daten (z. B. Sensordaten) sprechen für kNN: Die Werte müssen nicht in Klassen eingeteilt werden, und neue Messungen fließen sofort ein.

• Wird eine nachvollziehbare Begründung verlangt (z. B. gegenüber Kundschaft oder Aufsichtsbehörden) und liegen kategoriale Merkmale vor, spricht das für einen Entscheidungsbaum.

• Liegen nur zwei Merkmale vor und sind die Klassen im Streudiagramm klar durch eine Gerade getrennt, genügt eine Trenngerade; sie ist am einfachsten zu berechnen und zu erklären.

Typische Fehler in Aufgaben

• Seiten der Trenngeraden vertauscht: Welche Seite welcher Klasse entspricht, folgt aus der Lage der Trainingsdaten, nicht aus der Formel.

• Entscheidungswert falsch herum gebildet: Hier gilt g = y − (m · x + b). Wer (m · x + b) − y rechnet, muss die Vorzeichenregel umdrehen und das auch so begründen.

• Steigung und Achsenabschnitt nur genannt: Bei „Bedeutung benennen“ gehört dazu, was sie aussagen (Änderung von y je Einheit x, Schnittpunkt mit der y-Achse).

• Testdaten beim Festlegen der Geraden benutzt: Dann sagt die Trefferquote nichts mehr über neue Fälle aus.

• kNN mit Clustering verwechselt: kNN ist überwacht und braucht Trainingsdaten mit bekannter Klasse; k bezeichnet die Zahl der Nachbarn, nicht die Zahl der Gruppen (wie bei k-Means).

• Distanz ohne Skalierung beurteilt: Ohne Normalisierung dominiert das Merkmal mit dem größten Wertebereich.

• Kriterien für k ohne Begründung: „k ungerade“ allein reicht nicht; begründe, dass so kein Unentschieden entsteht.

• ID3 nur als „Baum“ beschrieben: Dazu gehört, dass das Merkmal mit dem größten Informationsgewinn an die jeweils nächste Stelle kommt und im Blatt die Mehrheit entscheidet.

Leitfragen

1. Welche Bedeutung haben m und b in der Geradengleichung y = m · x + b? Antwort

m ist die Steigung (Änderung von y, wenn x um 1 wächst), b ist der y-Achsenabschnitt (Schnittpunkt mit der y-Achse bei x = 0), siehe Abschnitt „Die Geradengleichung“.

2. Wie ordnet ein Programm einen Punkt mithilfe einer Trenngeraden einer Klasse zu? Antwort

Es prüft die Ungleichung y > m · x + b, also das Vorzeichen des Entscheidungswerts g = y − (m · x + b): positiv = oberhalb, negativ = unterhalb. Welche Seite welche Klasse ist, folgt aus den Trainingsdaten, siehe Abschnitt „Klassifizieren durch Rechnen“.

3. Woran erkennst Du eine robuste Trenngerade? Antwort

Die bessere Gerade ordnet weniger Trainingspunkte falsch ein; bei gleicher Fehlerzahl hat sie den breiteren punktfreien Korridor (Margin) zu den Stützpunkten beider Klassen. Endgültig zeigt es die Trefferquote auf den Testdaten, siehe Abschnitt „Eine gute Trenngerade finden“.

4. Wie funktioniert kNN? Antwort

Für einen neuen Punkt werden die Abstände zu allen Trainingspunkten berechnet, die k nächsten ausgewählt, und die Klasse, die unter ihnen am häufigsten vorkommt, wird vorhergesagt, siehe Abschnitt „Ablauf“.

5. Wie berechnest Du die euklidische Distanz zweier Datenpunkte? Antwort

Je Merkmal die Differenz bilden, quadrieren, alle Quadrate addieren und die Wurzel ziehen, siehe Abschnitt „Abstand messen“.

6. Nach welchen Kriterien wählst Du k? Antwort

Nicht zu klein (sonst entscheiden Ausreißer), nicht zu groß (sonst unspezifisch, im Extrem immer die häufigste Klasse), bei zwei Klassen ungerade (kein Unentschieden), am besten durch Ausprobieren mit Validierungsdaten, siehe Abschnitt „Einfluss von k“.

7. Warum müssen Daten für kNN kodiert und skaliert werden? Antwort

kNN rechnet mit Abständen. Kategorien müssen dafür Zahlen werden, und Merkmale mit großem Wertebereich würden ohne Skalierung (z. B. Min-Max-Normalisierung) die Distanz beherrschen, siehe Abschnitt „Daten für kNN aufbereiten“.

8. Wie wählt ID3 das Merkmal für einen Knoten aus? Antwort

Es berechnet für jedes verbleibende Merkmal den Informationsgewinn (Entropie vorher minus gewichtete Entropie der Teilmengen) und nimmt das Merkmal mit dem größten Wert. In den Blättern entscheidet die Mehrheit der Trainingsdatensätze, siehe Abschnitt „Wie ID3 den Baum aufbaut“.

9. Wann spricht etwas für kNN, wann für einen Entscheidungsbaum? Antwort

kNN: viele numerische Merkmale, laufend neue Daten, keine Klasseneinteilung nötig. Entscheidungsbaum: kategoriale Merkmale, nachvollziehbare Regeln verlangt, schnelle Vorhersage; aber Gefahr von Overfitting und Neuaufbau bei neuen Daten, siehe Abschnitt „Welches Verfahren passt?“.

Links und weitere Informationen

• Übungsaufgaben zum Klassifizieren mit Trenngeraden, kNN und Entscheidungsbäumen

• Grundlagen des maschinellen Lernens: Lernarten, Trainings- und Testdaten, CRISP-DM

• Datenqualität und Datenimport

• scikit-learn: Nearest Neighbors (englisch)

• scikit-learn: Decision Trees (englisch)

• Quinlan, J. R.: Induction of Decision Trees. Machine Learning 1, 81–106 (1986)

Hinweis zur Nachnutzung als Open Educational Resource (OER)

Dieser Artikel und seine Texte, Bilder, Grafiken, Code und sonstiger Inhalt sind - sofern nicht anders angegeben - lizenziert unter CC BY 4.0. Nennung gemäß TULLU-Regel bitte wie folgt: “Klassifizieren mit Trenngeraden, k-nächsten Nachbarn und Entscheidungsbäumen” von oer-informatik.de (H. Stein), Lizenz: CC BY 4.0. Der Artikel wurde unter https://oer-informatik.de/klassifikation-knn veröffentlicht, die Quelltexte sind in weiterverarbeitbarer Form verfügbar im Repository unter https://gitlab.com/oer-informatik/daten-ki/datenanalyse-ki. Erstellt mit KI-Assistenz; von mir umfassend redaktionell überarbeitet, geprüft und freigegeben. Stand: 29.10.2026.

[Kommentare zum Artikel lesen, schreiben] / [Artikel teilen] / [gitlab-Issue zum Artikel schreiben]