Ist es möglich, Cluster-Zentroide in Kernel-K-Mitteln zu finden?

Question

Annehmen ${x_1, \ldots, x_N}$ sind die Datenpunkte und wir müssen finden $K$ Cluster mit Kernel K Means.

Lass den Kernel sein $Ker$ (nicht zu verwechseln mit $K$ Anzahl der Cluster)

Lassen $\phi$ sei die implizite Zuordnung, die durch diesen Kernel induziert wird.

Nun wenn $\phi$waren endlich dimensioniert, gab es kein Problem. Nehmen Sie jedoch an$phi$ unendlich dimensional zu sein, hat dies durch den RBF-Kernel induziert

Überall, wo ich über Kernel-K-Mittel gelesen habe, heißt es nur, dass wir Kernel-K-Mittel verwenden können

$||\phi(x_i) - \phi(x_j)||^2 = Ker(x_i, x_i) + Ker(x_j, x_j) - 2Ker(x_i, x_j) \;\; \ldots(1)$

Ich verstehe das, aber es ist nicht so einfach für mein Gehirn und niemand gibt einen expliziten Algorithmus für Kernel-K-Mittel an, der mich mit folgenden Zweifeln zurücklässt:

1. In welchem ​​Raum initialisieren wir die K-Zentroide? Im ursprünglichen Raum oder im Raum, der durch induziert wird$\phi$? Ich vermute, wir initialisieren nur im ursprünglichen Raum, weil wir nicht einmal die Datenpunkte im Raum erfassen können, die durch induziert werden$\phi$ Angenommen, wir initialisieren diese zufällig $K$ Zentroide $\mu_1, \ldots \mu_K$nur im ursprünglichen Raum. (Bitte korrigieren Sie mich, wenn ich falsch annehme)

2. Nach der Initialisierung müssen wir jeden Datenpunkt einem der Cluster zuordnen. Angenommen, wir möchten zuweisen$x_n$ Für einen Cluster kann dies einfach mit (1) zum Berechnen durchgeführt werden $\mu_k$ = $\text{arg min}_j\; ||\phi(x_n) - \phi(\mu_j)||^2$

3. Wie berechne ich nach dem Zuweisen von Clustern die neuen Zentroide? Offensichtlich kann ich in dem Raum, der durch induziert wird, nicht gemein sein$\phi$ Was mache ich jetzt, da es unendlich dimensional ist?

Was ist die Lösung für dieses Problem? Ich gehe davon aus, dass wir die Zentroide irgendwie überhaupt nicht lagern müssen. Aber ich kann mir nicht vorstellen, wie ich das erreichen kann.

Ich habe gelesen, die Cluster-Zentren im Kernel zu finden. K-bedeutet Clustering

Die Antwort im Community-Wiki erklärt jedoch nicht, wo $(1)$ kommt von.

Answer 1

Das Kernel-k-Mittel entspricht dem regulären k-Mittel, das in dem vom Kernel induzierten Merkmalsraum arbeitet. Daher leben die Zentroide in einem Merkmalsraum, der, wie Sie erwähnt haben, unendlich dimensional sein kann. Bei der Formulierung eines Lernalgorithmus mit dem Kernel-Trick müssen wir den Funktionsbereich niemals direkt berühren. Alle Operationen im Feature-Space werden implizit mit der Kernelfunktion ausgeführt. Wir beschäftigen uns also nie direkt mit den Zentroiden im Kernel k-means. Stattdessen arbeiten wir mit den Clusterzuweisungen, wie ich weiter unten erläutern werde.

K-Mittel im Merkmalsraum

Der Lloyd's-Algorithmus ist die Standardmethode zur (ungefähren) Lösung des k-means-Problems. Hier ist eine Verallgemeinerung, die direkt im Feature-Space funktioniert. Lassen$X = \{x_1, \dots, x_n\}$ seien die Datenpunkte und $\phi(\cdot)$ eine Funktion sein, die einen Punkt aus dem Eingaberaum in den Merkmalsraum abbildet.

1. Initialisieren $K$ Cluster $C_1, \dots, C_K$, wo jeder Cluster $C_j$ ist ein Set mit $n_j$ Punkte, und jeder Punkt ist Mitglied von genau einem Cluster.

Wiederholen Sie diesen Vorgang bis zur Konvergenz (keine Änderung der Cluster-Mitgliedschaft):

1. Für jeden Cluster $C_j$Der Schwerpunkt (im Feature-Bereich) ist:

   $$\mu_j = \frac{1}{n_j} \sum_{x \in C_j} \phi(x) \tag{1}$$

2. Für jeden Punkt $x_i$, finde den Index $a_i$ des Clusters, dessen Schwerpunkt am nächsten liegt (im Merkmalsraum).

$$a_i = \arg \min_j \ \|\phi(x_i) - \mu_j\|^2 \tag{2}$$

$$= \arg \min_j \ \langle \phi(x_i), \phi(x_i) \rangle + \langle \mu_j, \mu_j \rangle - 2 \langle \phi(x_i), \mu_j \rangle \tag{3}$$

$$= \arg \min_j \ \langle \mu_j, \mu_j \rangle - 2 \langle \phi(x_i), \mu_j \rangle \tag{4}$$

1. Cluster aktualisieren. Jeder Punkt wird Mitglied des Clusters mit dem nächsten Schwerpunkt:

$$C_j = \{x_i \mid a_i = j\}$$

Hinweis: $\langle \cdot, \cdot \rangle$bezeichnet das innere Produkt. Gleichung$(3)$folgt aus der Beziehung zwischen Norm und innerem Produkt. Die erste Amtszeit$\langle \phi(x_i), \phi(x_i) \rangle$ hängt nicht vom Cluster ab, also können wir ihn fallen lassen und eine Gleichung geben $(4)$.

Verwenden des Kernel-Tricks

Angenommen, wir haben eine Kernelfunktion $k(\cdot, \cdot)$das berechnet innere Produkte im Merkmalsraum. So$k(x, x') = \langle \phi(x), \phi(x') \rangle$. Wir können innere Produkte im obigen Algorithmus durch Kernelfunktionsbewertungen ersetzen und dadurch implizit im Merkmalsraum arbeiten. Dies wird als Kernel-Trick bezeichnet.

Kombinieren Sie zunächst die Schritte 2 und 3, indem Sie die Definition der Schwerpunkte in der Gleichung einsetzen $(1)$ in die nächste Schwerpunktsuche in Gleichung $(4)$::

$$\arg \min_j \ \left \langle \frac{1}{n_j} \sum_{x \in C_j} \phi(x), \frac{1}{n_j} \sum_{x' \in C_j} \phi(x') \right \rangle - 2 \left \langle \phi(x_i), \frac{1}{n_j} \sum_{x \in C_j} \phi(x) \right \rangle \tag{5}$$

Da das innere Produkt bilinear ist, können wir dies wie folgt umschreiben:

$$\arg \min_j \ \frac{1}{n_j^2} \sum_{x \in C_j} \sum_{x' \in C_j} \langle \phi(x), \phi(x') \rangle - \frac{2}{n_j} \sum_{x \in C_j} \langle \phi(x_i), \phi(x) \rangle \tag{6}$$

Ersetzen Sie innere Produkte durch Kernelfunktionsbewertungen:

$$\arg \min_j \ \frac{1}{n_j^2} \sum_{x \in C_j} \sum_{x' \in C_j} k(x, x') - \frac{2}{n_j} \sum_{x \in C_j} k(x_i, x) \tag{7}$$

Für jeden Punkt $x_i$Hier erfahren Sie, wie Sie den Cluster mit dem nächstgelegenen Schwerpunkt finden, ohne die Schwerpunkte im Feature-Space explizit zu berechnen. Die Schritte 2 und 3 können im obigen Algorithmus ersetzt werden.