Grundlagen

Gegeben: Datenpunkte (x1,y1),...,(xm,ym)(x_1, y_1), ..., (x_m, y_m)(x1​,y1​),...,(xm​,ym​)

Ziel: Finde eine Funktion f(x)f(x)f(x), die den korrekten Output yyy für neue xxx vorhersagt.

1.Suche die kkk nächsten Nachbarn

2.Nimm die Mehrheitsklasse der Nachbarn

Ein Baum, bei dem jeder innere Knoten ein Feature testet und jedes Blatt einen Klassifikationswert angibt.

Greedy Decision Tree Lernalgorithmus

Wähle das Feature mit größtem Informationsgewinn. Teile die Daten nach den Featurewerten und rekursiv weitermachen.

h(x)=sgn(⟨w,x⟩−b)

Wenn Vorhersage falsch:

w←w+yxw \leftarrow w + yxw←w+yx

min∥w∥2 s.t. yi⟨w,xi⟩≥1y_i \langle w, x_i \rangle \geq 1yi​⟨w,xi​⟩≥1

fw​(x)=σ(⟨w,x⟩),

wobei σ(z)=11+e−z\sigma(z) = \frac{1}{1 + e^{-z}}σ(z)=1+e−z1​

Eine Menge von Punkten in genau k Clustern zu gruppieren, wobei Punkte innerhalb eines Clusters nah beieinander liegen sollen.

Initialisiere k Zentren (z.B. zufällig)

Ordne jeden Punkt dem nächsten Zentrum zu

Aktualisiere die Zentren als Mittelwerte ihrer Cluster

Wiederhole, bis keine Änderung mehr auftritt

Die Fehlerfunktion (Summe der quadrierten Abstände) sinkt monoton und es gibt endlich viele mögliche Clusterzuordnungen.

Nein, es kann in lokale Minima konvergieren und hängt stark von der Initialisierung ab.

Maß für die durchschnittliche Information eines Zufallsexperiments:

H(X)=−∑p(x)log⁡(p(x))H(X) = -\sum p(x) \log(p(x))H(X)=−∑p(x)log(p(x))

Bei Gleichverteilung, also wenn alle Ereignisse gleich wahrscheinlich sind:

H(X)=log⁡(n)H(X) = \log(n)H(X)=log(n)

Man wählt das Attribut mit dem höchsten Information Gain.

Differenz zwischen Entropie vor und nach Aufteilung:

G(S,A)=H(Y)−∑x∣Sx∣∣S∣⋅H(Y∣x)G(S, A) = H(Y) - \sum_x \frac{|S_x|}{|S|} \cdot H(Y|x)G(S,A)=H(Y)−∑x​∣S∣∣Sx​∣​⋅H(Y∣x)