Ist KNN ein diskriminierender Lernalgorithmus?

16

Es scheint, dass KNN ein diskriminierender Lernalgorithmus ist, aber ich kann keine Online-Quellen finden, die dies bestätigen.

machine-learning classification k-nearest-neighbour jpmuc
quelle

18

KNN ist ein Unterscheidungsalgorithmus, da es die bedingte Wahrscheinlichkeit einer Stichprobe modelliert, die zu einer bestimmten Klasse gehört. Um dies zu sehen, muss man nur überlegen, wie man zur Entscheidungsregel der kNNs gelangt.

Eine Klassenbezeichnung entspricht einer Menge von Punkten, die zu einer Region im Merkmalsraum . Wenn Sie unabhängig Stichprobenpunkte aus der tatsächlichen Wahrscheinlichkeitsverteilung , ist die Wahrscheinlichkeit, eine Stichprobe aus dieser Klasse zu ziehen, $R$ $p(x)$

P = \int_{R} p (x) d x

$P = \int_{R} p(x) dx$

Was ist, wenn Sie Punkte haben? Die Wahrscheinlichkeit, dass Punkte dieser Punkte in den Bereich folgt der Binomialverteilung: $N$ $K$ $N$ $R$

P r Ö b (K) = (\binom{N}{K}) P^{K} (1 - P)^{N - K}

$Prob(K) = {{N} \choose {K}}P^{K}(1-P)^{N-K}$

Als diese Verteilung scharf gespitzt, so dass die Wahrscheinlichkeit durch ihren Mittelwert angenähert werden kann . Eine zusätzliche Annäherung ist, dass die Wahrscheinlichkeitsverteilung über annähernd konstant bleibt, so dass man das Integral durch annähern kann, wobei das Gesamtvolumen von ist Region. Unter diesen Annäherungen ist . $N \to \infty$ $\frac{K}{N}$ $R$

P = \int_{R} p (x) d x \approx p (x) V

$P = \int_{R} p(x) dx \approx p(x)V$

V

$V$

p (x) \approx \frac{K}{N V}

$p(x) \approx \frac{K}{NV}$

Wenn wir nun mehrere Klassen hätten, könnten wir die gleiche Analyse für jede wiederholen, was uns wobei ist die Anzahl der Punkte aus der Klasse die in diese Region fallen, und ist die Gesamtanzahl der Punkte, die zur Klasse . Hinweis .

p (x | C_{k}) = \frac{K_{k}}{N_{k} V}

$p(x|C_{k}) = \frac{K_{k}}{N_{k}V}$

K_{k}

$K_{k}$

k

$k$

N_{k}

$N_{k}$

C_{k}

$C_k$

\sum_{k} N_{k} = N

$\sum_{k}N_{k}=N$

Wenn wir die Analyse mit der Binomialverteilung wiederholen, können wir leicht das vorherige schätzen . $P(C_{k}) = \frac{N_{k}}{N}$

Unter Verwendung der Bayes-Regel ist

P (C_{k} | x) = \frac{p (x | C_{k}) p (C_{k})}{p (x)} = \frac{K_{k}}{K}

$P(C_{k}|x) = \frac{p(x|C_{k})p(C_{k})}{p(x)} = \frac{K_{k}}{K}$ das ist die Regel für kNNs.

jpmuc
quelle

2

Die Referenz enthält keine Informationen zu KNN. Ist es das richtige

Bayerj

1

Ich meinte es, um zu betonen, was für einen Unterscheidungsalgorithmus gegenüber einem Generativ verstanden wird.

Jpmuc

5

Answer by @jpmuc scheint nicht genau zu sein. Generative Modelle modellieren die zugrunde liegende Verteilung P (x / Ci) und verwenden später das Bayes-Theorem, um die posterioren Wahrscheinlichkeiten zu finden. Das ist genau das, was in dieser Antwort gezeigt wurde und schließt dann das genaue Gegenteil. :Ö

Damit KNN ein generatives Modell ist, sollten wir in der Lage sein, synthetische Daten zu generieren. Es scheint, dass dies möglich ist, sobald wir einige erste Trainingsdaten haben. Es ist jedoch nicht möglich, ohne Trainingsdaten zu beginnen und synthetische Daten zu generieren. Daher passt KNN nicht gut zu generativen Modellen.

Man kann argumentieren, dass KNN ein Unterscheidungsmodell ist, weil wir eine Unterscheidungsgrenze für die Klassifizierung zeichnen können, oder wir können das hintere P (Ci / x) berechnen. All dies gilt jedoch auch für generative Modelle. Ein echtes Unterscheidungsmodell sagt nichts über die zugrunde liegende Verteilung aus. Aber im Fall von KNN wissen wir viel über die zugrunde liegende Verteilung, tatsächlich speichern wir den gesamten Trainingssatz.

So scheint es, dass KNN auf halbem Weg zwischen generativen und diskriminativen Modellen liegt. Wahrscheinlich wird KNN deshalb in renommierten Artikeln nicht nach generativen oder diskriminativen Modellen kategorisiert. Nennen wir sie einfach nicht parametrische Modelle.

Binu Jasim
quelle

Ich stimme nicht zu. Generative Klassifikatoren lernen ein Modell der gemeinsamen Wahrscheinlichkeit p (x, y) der Eingaben x und der Bezeichnung y und treffen ihre Vorhersagen, indem sie Bayes-Regeln verwenden, um p (ylx) zu berechnen, und dann die wahrscheinlichste Bezeichnung y auswählen Diskriminative Klassifikatoren modellieren das hintere p (ylx) direkt oder lernen eine direkte Zuordnung von Eingaben x zu den Klassenbezeichnungen ". Siehe "Über diskriminierende vs. generative Klassifikatoren: Ein Vergleich von logistischer Regression und naivem Bayes.

jpmuc

3

Ich bin auf ein Buch gestoßen, das das Gegenteil sagt ( dh ein generatives nichtparametrisches Klassifikationsmodell)

Dies ist der Online-Link: Maschinelles Lernen Eine probabilistische Perspektive von Murphy, Kevin P. (2012)

Hier der Auszug aus dem Buch:

Gürol Canbek
quelle

Muss ein Fehler sein ..

1

Ich stimme zu, dass kNN diskriminierend ist. Der Grund ist, dass es nicht explizit ein (probabilistisches) Modell speichert oder zu lernen versucht, das die Daten erklärt (im Gegensatz zu zB Naive Bayes).

Die Antwort von juampa verwirrt mich, da nach meinem Verständnis ein generativer Klassifikator versucht zu erklären, wie die Daten generiert werden (z. B. unter Verwendung eines Modells), und diese Antwort besagt, dass es aus diesem Grund diskriminierend ist ...

Amir
quelle

1

Ein generatives Modell lernt P (Ck, X), sodass Sie mit dieser gemeinsamen Verteilung mehr Daten generieren können. Im Gegensatz dazu würde ein Unterscheidungsmodell P (Ck | X) lernen. Darauf weist @juampa mit KNN hin.

Zhubarb

1

Zum Zeitpunkt der Klassifizierung verwenden sowohl generative als auch diskriminative Faktoren bedingte Wahrscheinlichkeiten, um Vorhersagen zu treffen. Generative Klassifikatoren lernen jedoch die gemeinsame Wahrscheinlichkeit und berechnen nach der Bayes-Regel die Bedingung, während diskriminativ ein Klassifikator entweder direkt die Bedingung berechnet oder eine Näherung dafür liefert, so gut es geht.

Rapaio

Ist KNN ein diskriminierender Lernalgorithmus?

Antworten: