Clustering
Unsupervised Learning
Wir haben jetzt nur noch ungelabelte Daten
$\mathcal{D} = \{x^{(1)}, x^{(2)}, \ldots, x^{(m)}\}$
Kein Testset - hier haben wir kein formelles Qualitätskriterium, dass wir darauf messen könnten
Beispiel: Marktsegmentierung
- Gekaufte Artikel
- Angeschaute Artikel
- Gesamtumsatz
- Reklamationen
- ...
Input Daten $x$:
Hier suchen wir nach Gruppen von möglichst ähnlichen Kunden. Für jedes dieser Segmente machen wir dann individuelles Marketing.
k-means
Wir suchen genau k unterschiedliche Cluster
Idee: Jeder Cluster ist definiert durch sein Zentrum. Jeder Punkt gehört zu dem nächsten Cluster.
k-means mit K=3
https://commons.wikimedia.org/wiki/File:K-means_convergence.gif
Algorithmus: k-means
- Wähle $k$ zufällige Punkte $x^{(r_1)}, \ldots, x^{(r_k)}$ aus
- Setze Cluster Zentren $\mu_1 = x^{(r_1)}, \ldots, \mu_k = x^{(r_k)}$
- Wiederhole bis Konvergenz:
- Weise Punkte zu Zentren zu:
$c^{(i)} = \operatornamewithlimits{arg\,min}_j ||x^{(i)} - \mu_j||$ - Finde neues Cluster Zentrum:$$\mu_j = \frac{\sum_i 1[c^{(i)} = j] x^{(i)}}{\sum_i 1[c^{(i)} = j]}$$
- Weise Punkte zu Zentren zu:
k-means konvergiert zu einem lokalen Minimum von $$ J(c, \mu) = \sum_{i=1}^m || x^{(i)} - \mu_{c^{(i)}} ||^2$$
Globales Optimum finden ist NP-schwer.
In der Praxis meistens kein Problem.
Option: Mehrfach mit unterschiedlichen Starts laufen lassen.
Wie wählt man k?
Hängt sehr vom Problem ab.
- Wie viele Marktsegmente können wir einzeln behandeln?
- Wie viele Cluster erwarten wir?
- Wie feingranular wollen wir unterteilen?
- Durch Ausprobieren ermitteln wann die Cluster sinnvoll aussehen.
Welches k Sinn macht, ist nicht immer eindeutig.
In sklearn: sklearn.cluster.KMeans
Je nach Struktur der Daten macht k-means nicht immer Sinn
 |
 |
Hier suchen wir eher nach Zusammenhangskomponenten
Was für Cluster wollen wir haben, wenn unsere Daten einen Graph bilden?
Mit einem minimalen Schnitt durch die Kanten erhalten wir 2 Cluster
Der Minimale Schnitt ist nicht immer der sinnvollste
Mini Komponenten nicht sinnvoll
- wenige Kanten schneiden
- keine Komponente zu klein werden lassen
Ein sinnvoller Schnitt sollte
Mithilfe spektraler Graphentheorie kommen wir zu besseren Schnitten
Für einen Graphen mit $n$ Knoten sei $D$ die $n \times n$ Matrix mit der Anzahl an Kanten je Knoten auf der Diagonalen.
| $D$ | |
|
$\begin{bmatrix} 3 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 2 \\ \end{bmatrix}$ |
$A \in \mathbb{R}^{n\times n}$ ist die adjacency matrix, welche angibt, zwischen welchen Knoten eine Kante ist.
| $A$ | |
|
|
$\begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ \end{bmatrix}$ |
Die Laplace Matrix ist $L = D - A$
| $L$ | |
|
|
$\begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 1 & 0 & 0 \\ -1 & 0 & 2 & -1 \\ -1 & 0 & -1 & 2 \\ \end{bmatrix}$ |
Die Eigenwerte und Eigenvektoren der Laplace Matrix haben interessante Eigenschaften.
Für Matrix $M$ sind Eigenwert $\lambda$ und zugehöriger Eigenvektor $v$ so dass $$M v = \lambda v$$
Für jede Zusammenhangskomponente gibt es ein Eigenwert / -vektor Paar $(\lambda, v)$ mit $\lambda = 0$ und $v_i = 1$ für alle Knoten der Komponente.
| $L$ | |
|
$\begin{bmatrix} 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \\ -1 & 0 & 1 & 0 \\ 0 & -1 & 0 & 1 \\ \end{bmatrix}$ |
| $\lambda^{(1)} = 0, v^{(1)} = \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix}$ | $\lambda^{(2)} = 0, v^{(2)} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \end{bmatrix}$ |
Der kleinste Eigenwert $\lambda > 0$ gibt uns den sinnvollen Schnitt, den wir gesucht haben.
Für die Knoten auf der einen Seite des Schnittes gilt $v_i > 0$, für die anderen $v_i < 0$.
|
$\lambda^{(1)} = 0\qquad
v^{(1)} = \begin{bmatrix}
1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1
\end{bmatrix}
$
$\lambda^{(2)} = 0.4156\qquad
v^{(2)} = \begin{bmatrix}
-0.05652\\ -0.2089\\ -0.1138\\ -0.3696\\ -0.6323\\ 0.1767\\ 0.2269\\ 0.2862\\ 0.336\\ 0.3553
\end{bmatrix}
$
|
Aus den nächst größeren Eigenwerten bekommen wir weitere sinnvolle Schnitte.
|
|
$\lambda^{(2)} = 0.4156\qquad
v^{(2)} = \begin{bmatrix}
-0.05652\\ -0.2089\\ -0.1138\\ -0.3696\\ -0.6323\\ 0.1767\\ 0.2269\\ 0.2862\\ 0.336\\ 0.3553
\end{bmatrix}
$
$\lambda^{(3)} = 1.0824\qquad
v^{(3)} = \begin{bmatrix}
-0.4379\\ -0.4019\\ -0.2839\\ -0.0488\\ 0.5922\\ -0.154\\ 0.06027\\ 0.08238\\ 0.2517\\ 0.34
\end{bmatrix}
$
|
Wie kommen wir nun an insgesamt $k$ Cluster?
- Berechne die kleinsten $k$ Eigenwerte und -vektoren
- Jeder Knoten $j$ erhält einen Vektor $u^{[j]} \in \mathbb{R}^k$, zusammengesetzt aus den Eigenvektoren: \[ u^{[j]} = \begin{bmatrix} v^{(1)}_j \\ v^{(2)}_j \\ \vdots \\ v^{(k)}_j \end{bmatrix} \]
- Suche $k$ Cluster in diesen neuen Features $u$ mit k-means.
|
|
$v^{(1)} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} $ | $v^{(2)} = \begin{bmatrix} -0.05652\\ -0.2089\\ -0.1138\\ -0.3696\\ -0.6323\\ 0.1767\\ 0.2269\\ 0.2862\\ 0.336\\ 0.3553 \end{bmatrix} $ | $ v^{(3)} = \begin{bmatrix} -0.4379\\ -0.4019\\ -0.2839\\ -0.0488\\ 0.5922\\ -0.154\\ 0.06027\\ 0.08238\\ 0.2517\\ 0.34 \end{bmatrix} $ |
| $ u^{[1]} = \begin{bmatrix} 1 \\ -0.05652 \\ -0.4379 \end{bmatrix} \quad u^{[2]} = \begin{bmatrix} 1 \\ -0.2089 \\ -0.4019 \end{bmatrix} \quad u^{[3]} = \begin{bmatrix} 1 \\ -0.1138 \\ -0.2839 \end{bmatrix} \quad \cdots $ | |||
Spektrales Embedding
Wie stellen wir unsere Daten als Graph dar?
Idee: Eine Kante für die $n$ nächsten Nachbarn.
Alternativ:Eine gewichtete Kante zu allen anderen Knoten (mehr Gewicht = näher)
Brauchen Ähnlichkeitsfunktion, z.B.: \[ s(d_1, d_2) = e^{-\frac{1}{\sigma^2} ||d_1 - d_2||} \]
Laplace Matrix mit Gewicht statt $1$ für jede Kante
Je nach Problem können wir einen Ähnlichkeitsgraph beliebig definieren.
Mit passendem Graph, kann Spectral Clustering gut zusammenhängende Komponenten finden
$n$ nächste Nachbarn (mit $n$ zwischen 10 und 50)
In sklearn: sklearn.cluster.SpectralClustering