Wie passt man am leichtesten über?

7

Das ist eine seltsame Frage, ich weiß.

Ich bin nur ein Neuling und versuche, etwas über verschiedene Klassifikatoroptionen und deren Funktionsweise zu lernen. Also stelle ich die Frage:

Bei einem Datensatz mit n1-Dimensionen und n2-Beobachtungen, bei dem jede Beobachtung in n3-Buckets klassifiziert werden kann, erzeugt dieser Algorithmus am effizientesten (idealerweise mit nur einer Trainingsiteration) ein Modell (Klassifizierungsgrenze), das jede Beobachtung im Datensatz perfekt klassifiziert (komplett überpasst)?

Mit anderen Worten, wie passt man am leichtesten über?

(Bitte belehren Sie mich nicht über "Nicht überanpassen". Dies dient nur theoretischen Bildungszwecken.)

Ich habe den Verdacht, dass die Antwort ungefähr so ​​lautet: "Nun, wenn Ihre Anzahl von Dimensionen größer ist als Ihre Anzahl von Beobachtungen, verwenden Sie den X-Algorithmus, um die Grenze (n) zu zeichnen, andernfalls verwenden Sie den Y-Algorithmus."

Ich habe auch den Verdacht, dass die Antwort lautet: "Sie können eine glatte Grenze zeichnen, aber das ist rechenintensiver als das Zeichnen von geraden Linien zwischen allen unterschiedlichen klassifizierten Beobachtungen."

Aber so weit wird mich meine Intuition führen. Kannst du helfen?

Ich habe ein handgezeichnetes Beispiel dafür, wovon ich in 2D mit binärer Klassifizierung spreche.

Teilen Sie einfach den Unterschied auf, oder? Welcher Algorithmus macht das effizient für n-Dimensionen?

Teilen Sie einfach den Unterschied auf, oder?  Welcher Algorithmus macht das effizient?

Legit Stack
quelle
5
knn mit ? k=1
Shimao
@shimao Ich nehme an, das würde funktionieren, nicht wahr? Ja, ich kann nicht verstehen warum nicht. Vielen Dank!
Legit Stack
@shimao Ist das der effizienteste Weg, um die Grenze zu kodieren? Wahrscheinlich richtig? Da wir nicht wissen, ob die Daten völlig zufällig sind oder nicht, ist die Verwendung der Daten selbst als codiertes Modell mit KNN-Algorithmus wahrscheinlich das Beste, was Sie im Allgemeinen tun können. Recht?
Legit Stack
2
@shimao: möchtest du deinen Kommentar als Antwort posten (vielleicht mit etwas mehr Details)?
Stephan Kolassa
Der Titel ist nicht sehr informativ über den Inhalt. Die überwiegende Mehrheit der Benutzer, die auf dieser Seite nach Antworten suchen, wird feststellen, dass die tatsächlich gestellte Frage ganz anders ist als erwartet. Bitte überarbeiten.
OrangeSherbet

Antworten:

7

Solange alle Beobachtungen eindeutig sind, geben K-nächste Nachbarn mit K auf 1 und einer beliebigen gültigen Abstandsmetrik einen Klassifikator, der perfekt zum Trainingssatz passt (da der nächste Nachbar jedes Punkts im Trainingssatz trivial ist selbst). Und es ist wahrscheinlich das effizienteste, da überhaupt kein Training erforderlich ist.

Ist das der effizienteste Weg, um die Grenze zu kodieren? Wahrscheinlich richtig? Da wir nicht wissen, ob die Daten völlig zufällig sind oder nicht, ist die Verwendung der Daten selbst als codiertes Modell mit KNN-Algorithmus wahrscheinlich das Beste, was Sie im Allgemeinen tun können. Recht?

Es ist das zeiteffizienteste, aber nicht unbedingt das platzsparendste.

Shimao
quelle
Wenn Sie Platz sparen möchten, speichern Sie die Hashcodes. Beachten Sie auch, dass Sie nur N-1-Buckets analysieren müssen.
Mooing Duck
1
Wenn Sie die Grenze erhalten möchten, können Sie die Voronoi-Tessellation berechnen.
Davidmh
5

Das kannst du nicht.

Zumindest im Allgemeinen nicht in dem Maße, wie Sie es möchten, wenn Sie eine perfekte Übereinstimmung mit beliebigen Daten und beliebiger Dimensionalität wünschen .

Nehmen wir als Beispiel an, wir haben n1=0 Prädiktor-Dimensionen (dh überhaupt keine) und n2=2 Beobachtungen klassifiziert in n3=2Eimer. Die beiden Beobachtungen werden in zwei verschiedene Eimer eingeteilt, nämlich "Schokolade" und "Vanille".

Da Sie keine Prädiktoren haben, können Sie diese nicht perfekt klassifizieren.


Wenn Sie mindestens einen Prädiktor haben , der für jede Beobachtung unterschiedliche Werte annimmt , können Sie tatsächlich willkürlich schlecht überpassen, indem Sie einfach beliebig hohe Polynomordnungen für einen numerischen Prädiktor verwenden (wenn der Prädiktor mit unterschiedlichen Werten für jede Beobachtung kategorisch ist, tun Sie das nicht). muss nicht einmal transformieren). Das Werkzeug oder Modell ist ziemlich zweitrangig. Ja, es ist leicht zu überpassen.

Hier ist ein Beispiel. Die 10 Beobachtungen sind völlig unabhängig vom einzelnen numerischen Prädiktor. Wir passen immer komplexere logistische Regressionen oder Potenzen des Prädiktors an und klassifizieren anhand eines Schwellenwerts von 0,5 ( was keine gute Praxis ist ). Richtig angepasste Punkte sind grün markiert, falsch angepasste rot.

Überanpassung

R-Code:

nn <- 10
set.seed(2)

predictor <- runif(nn)
outcome <- runif(nn)>0.5

plot(predictor,outcome,pch=19,yaxt="n",ylim=c(-0.1,1.6))
axis(2,c(0,1),c("FALSE","TRUE"))

orders <- c(1,2,3,5,7,9)
xx <- seq(min(predictor),max(predictor),0.01)

par(mfrow=c(3,2))
for ( kk in seq_along(orders) ) {
    plot(predictor,outcome,pch=19,yaxt="n",ylim=c(-0.2,1.2),main=paste("Order:",orders[kk]))
    axis(2,c(0,1),c("FALSE","TRUE"))

    model <- glm(outcome~poly(predictor,orders[kk]),family="binomial")
    fits_obs <- predict(model,type="response")
    fits <- predict(model,newdata=data.frame(predictor=xx),type="response")

    lines(xx,fits)
    correct <- (fits_obs>0.5 & outcome) | ( fits_obs<0.5 & !outcome)
    points(predictor[correct],outcome[correct],cex=1.4,col="green",pch="o")
    points(predictor[!correct],outcome[!correct],cex=1.4,col="red",pch="o")
}
Stephan Kolassa
quelle