[PYTHON] k-bedeutet und Kernel k-bedeutet

Ich habe angefangen, meine Studieninhalte in einem anderen Blog zu schreiben, indem ich die Wartezeit zu Hause genutzt habe, aber da die Tex-Funktion dort Scheiße war, werde ich einige Artikel nach Qiita verschieben. .. ..

Ich lernte k-means, den grundlegendsten [Quell] -Algorithmus für unbeaufsichtigtes Lernen, und versuchte es einfach.

k-means Eine der Methoden, um bestimmte Daten in mehrere Cluster aufzuteilen.

Vorteile etc.

Vorteil

Da es nach dem Abstand vom Zentrum des Clusters klassifiziert wird, ist das Ergebnis beim Zeichnen fast immer intuitiv.

Nachteil

Algorithmus

gegeben

Berechnungsmethode

  1. Weisen Sie allen Daten $ x_i $ $ (x_i, k_i) $ zufällig den Cluster $ k_i $ zu 1.Zentral für jeden Cluster(m_k)Ich suchem_k |N_k| = \sum_{i \in N_k} x_i
  2. Berechnen Sie die Entfernung zu allen Clusterzentren für alle Daten und aktualisieren Sie sie auf den kürzesten Cluster
  3. Wiederholen Sie 2-3, bis keine Cluster-Updates mehr vorhanden sind

Dabei ist $ N_k $ der Datensatz, der zu diesem Zeitpunkt im Cluster $ k $ enthalten ist.

Anwendungsbeispiel

Experimentieren Sie mit den folgenden Parametern in sklearns datasets.make_circles.

Mit den obigen Einstellungen werden zwei Cluster, ein Kreis mit einem Radius von 0,1 und ein Kreis mit einem Radius von 1, unter 0,01 Rauschen erhalten.

Code

# k:Anzahl der Cluster
def kmeans(data, k):
  df = pd.DataFrame()
  df['x'] = data.T[0]
  df['y'] = data.T[1]
  clusters = np.random.randint(0, k, len(df))
  df['c'] = clusters

  while True:
    before_clusters = list(df.c.copy())
    centers = df.groupby('c').mean().reset_index().drop(columns=['c']).T

    tmp = df.drop(columns=['c']).T
    new_clusters = [min(centers.columns, key=lambda k:((tmp[col] - centers[k]) ** 2).sum()) for col in tmp.columns]
    if before_clusters == new_clusters:
      break
    else:
      df['c'] = new_clusters

  return df.c

Versuchsergebnis

Das Ergebnis des Drehens von k-Mitteln ist wie folgt. Da die Daten nicht klar linear getrennt werden können, ist ersichtlich, dass die Klassifizierungsergebnisse nicht korrekt wie erwartet klassifiziert sind. k-means.png

kernel k-means

Vorteile etc.

Vorteil

Nachteil

Algorithmus

gegeben

Fast das gleiche wie normales k-Mittel. Wenn Sie die Mitte jedes Clusters finden, kann die Mitte des Merkmalsraums gefunden werden. Das heißt, unter Berücksichtigung des Clusters $ k $ definieren wir den Vektor $ m_k $, der den folgenden Betrag minimiert, als Zentrum des Clusters $ k $.

\displaystyle{
\begin{aligned}
\sum_{i \in N_k} (\phi(x_i) - m_k)^ 2.
\end{aligned}
}

$ M_k], um dies zu minimieren, kann wie folgt erhalten werden.

\displaystyle{
\begin{aligned}
m_k = \frac{1}{|N_k|} \sum_{i \in N_k} \phi(x_i).
\end{aligned}
}

Damit ist der Abstand zwischen den Daten $ x_i $ und dem Cluster $ k $ wie folgt.

\displaystyle{
\begin{aligned}
(\phi(x_i) - m_k)^ 2 &= K(x_i, x_i) -\frac{2}{|N_k|} \sum_{j \in N_k} K(x_i, x_j) + \frac{1}{|N_k|^ 2} \sum_{m, n \in N_k} K(x_m, x_n)
\end{aligned}
}

Wobei $ K (x, y) $ eine Kernelfunktion ist.

Anwendungsbeispiel

Experimentieren Sie mit den folgenden Parametern in sklearns datasets.make_circles.

Die Kernelfunktion verwendet den folgenden RBF-Kernel.

\displaystyle{
\begin{aligned}
K(x, y) = \exp \left(\frac{(x-y)^ 2}{\sigma^2} \right)
\end{aligned}
}

Code

# kernel:Kernelfunktion, die 2 Variablen empfängt
def kernel_kmeans(data, k, kernel):
  df = pd.DataFrame()
  df['x'] = data.T[0]
  df['y'] = data.T[1]
  clusters = np.random.randint(0, k, len(df))
  df['c'] = clusters

  self_corr = {}
  #Die Korrelation innerhalb der Klasse ist bei mehrmaliger Berechnung stark. Zwischenspeichern Sie sie daher
  def compute_self_corr():
    for j in range(0, k):
      sub_df = df[df.c == j].drop(columns=['c']).T
      ret = sub_df.apply(lambda col1: sub_df.apply(lambda col2:  kernel(col1, col2), axis=0).mean(), axis=0).mean()
      self_corr[j] = ret

  #Berechnen Sie den Abstand zum Cluster-Center im Feature-Space
  def compute_distance_from_center_j(x, j):
    sub_df = df[df.c == j].drop(columns=['c']).T
    ret = kernel(x, x)
    ret += sub_df.apply(lambda col: -2 * kernel(x, col), axis=0).mean()
    ret += self_corr[j]
    return ret

  while True:
    compute_self_corr()
    before_clusters = list(df.c.copy())
    tmp = df.drop(columns=['c']).T
    new_clusters = [min(range(0, k), key=lambda compute_distance_from_center_j(tmp[col], j)) for col in tmp.columns]
    if before_clusters == new_clusters:
      break
    else:
      df['c'] = new_clusters
  return df.c

Versuchsergebnis

Das Ergebnis des Drehens des Kernels k-means ist wie folgt. Der Kernel-Parameter $ \ sigma $ ist $ 0.5 $. kernel-k-means-sig0.5.png

Wenn der Kernel k-means funktioniert (funktioniert nicht)

Betrachten Sie die folgende Situation.

Unter der obigen Situation werden neue Daten $ D = (x, y) = (R, 0) $ hinzugefügt und klassifiziert. In diesem Fall ist der Abstand zu den Klassen $ c_r $ und $ c_R $ wie folgt, wenn der Abstand zum Eingeben der Klasse $ c $ als $ C (c) $ geschrieben wird.

\displaystyle{
\begin{aligned}
C(c_r) &= 1 -2 \exp \left(-\frac{r^ 2 + R^ 2}{\sigma^ 2}\right) I_0 \left(\frac{2rR}{\sigma^ 2}\right) + \exp \left(-\frac{2r^ 2}{\sigma^ 2}\right) I_0 \left(\frac{2r^ 2}{\sigma^ 2}\right), \\
C(c_R) &= 1 - \exp \left(-\frac{2R^ 2}{\sigma^ 2}\right) I_0 \left(\frac{2R^ 2}{\sigma^ 2}\right).
\end{aligned}
}

Wobei $ I_ \ alpha (x) $ eine modifizierte Schiffsfunktion ist. Darüber, wenn es $ r \ ll \ sigma \ ll R $ ist

\displaystyle{
\begin{aligned}
C(c_r) &= 2, \\
C(c_R) &= 1 - \sqrt \frac{\sigma^ 2}{2\pi R^ 2}.
\end{aligned}
}

Offensichtlich ist $ C (c_R) \ lt C (c_r) $, daher wird es als der richtige Cluster klassifiziert. Auch wenn $ \ sigma \ ll r, R $

\displaystyle{
\begin{aligned}
C(c_r) &= 1 - 2 \sqrt \frac{\sigma^ 2}{2\pi r R} \exp \left(-\frac{(r - R)^ 2}{\sigma^ 2}\right) + \sqrt \frac{\sigma^ 2}{2\pi r^ 2}, \\
C(c_R) &= 1 - \sqrt \frac{\sigma^ 2}{2\pi R^ 2}.
\end{aligned}
}

Wenn Sie sich den Bereich ansehen, in dem beide gleich sind,r=REs gibt keine andere Wahl als andersC(c_r) \lt C(c_R)Es wird eine falsche Klassifizierung. Das Wichtigste hier ist\sigmaWann\delta r := |R - r|Es spielt keine Rolle, wie groß oder klein die Skala ist. Ebenfallsr, R \ll \sigmaWann

\displaystyle{
\begin{aligned}
C(c_r) &= 0, \\
C(c_R) &= 0.
\end{aligned}
}

Offensichtlich kann es nicht richtig klassifiziert werden. In Anbetracht der Lesereihenfolge von $ r / \ sigma und R / \ sigma $ ist auch ersichtlich, dass sie nicht korrekt klassifiziert sind, da sie den gleichen Ausdruck wie normale k-Mittelwerte haben.

Betrachten Sie in ähnlicher Weise den Fall, in dem die Daten $ d = (x, y) = (r, 0) $ hinzugefügt werden. Der Abstand vom Zentrum der Klasse

\displaystyle{
\begin{aligned}
C(c_r) &= 1 - \exp \left(-\frac{2r^ 2}{\sigma^ 2}\right) I_0 \left(\frac{2r^ 2}{\sigma^ 2}\right), \\
C(c_R) &= 1 -2 \exp \left(-\frac{r^ 2 + R^ 2}{\sigma^ 2}\right) I_0 \left(\frac{2rR}{\sigma^ 2}\right) + \exp \left(-\frac{2R^ 2}{\sigma^ 2}\right) I_0 \left(\frac{2R^ 2}{\sigma^ 2}\right).
\end{aligned}
}

Darüber, wenn es $ r \ ll \ sigma \ ll R $ ist

\displaystyle{
\begin{aligned}
C(c_r) &= 0, \\
C(c_R) &= 1 + \sqrt \frac{\sigma^ 2}{2\pi R^ 2}.
\end{aligned}
}

Offensichtlich ist $ C (c_r) \ lt C (c_R) $, daher wird es als der richtige Cluster klassifiziert. Auch wenn $ \ sigma \ ll r, R $

\displaystyle{
\begin{aligned}
C(c_r) &= 1 - \sqrt \frac{\sigma^ 2}{2\pi r^ 2}, \\
C(c_R) &= 1 - 2 \sqrt \frac{\sigma^ 2}{2\pi r R} \exp \left(-\frac{(r - R)^ 2}{\sigma^ 2}\right) + \sqrt \frac{\sigma^ 2}{2\pi R^ 2}.
\end{aligned}
}

Auch in diesem Fall gibt es, wenn Sie sich den Bereich ansehen, in dem beide gleich sind, nur $ r = R $, und ansonsten ist es $ C (c_r) \ lt C (c_R) $, was eine falsche Klassifizierung ist. Wenn es $ r ist, ist R \ ll \ sigma $

\displaystyle{
\begin{aligned}
C(c_r) &= 0, \\
C(c_R) &= 0.
\end{aligned}
}

Offensichtlich kann es nicht richtig klassifiziert werden. In ähnlicher Weise ist der Ausdruck unter Berücksichtigung der Lesereihenfolge von $ r / \ sigma und R / \ sigma $ der gleiche wie der des normalen k-Mittels.

Wie Sie diesen Ergebnissen entnehmen können, funktioniert die Klassifizierung gut, wenn $ \ sigma $, die Auflösung der Kernelfunktion, zwischen den Skalen der beiden Cluster liegt. Vielleicht kann der RBF-Kernel nicht in die Richtung schauen, sondern nur in die Größe, insbesondere größer oder kleiner als die angegebene Skala $ \ sigma $. Wenn die Skalierung des Kernels nicht zwischen den Skalierungen jeder Klasse liegt, wird davon ausgegangen, dass sie nicht wie erwartet funktioniert.

Lassen Sie uns ein konkretes numerisches Experiment durchführen. Lassen Sie uns $ \ sigma $ unter den gleichen Parametern $ r = 0.1, R = 1 $ wie zuvor ändern. Mal sehen, wie es sich besonders in den Bereichen $ \ sigma \ ll r, R $, $ r \ ll \ sigma R $, $ r, R \ ll \ sigma $ verhält.

\sigma = 0.01, r=0.1, R=1 kernel-k-means-sig0.01.png

\sigma = 0.5, r=0.1, R=1 kernel-k-means-sig0.5.png

\sigma = 2, r=0.1, R=1 kernel-k-means-sig2.0.png

Impressionen

Kernel k-means ist nicht einfach zu bedienen, da es stark vom Kernel und seinen Parametern abhängt. Gewöhnliche k-Mittel funktionieren jedoch nur für linear trennbare und sind nicht einfach zu verwenden. .. ..

Referenz

Recommended Posts

k-bedeutet und Kernel k-bedeutet
[Hinweis] Aufbau und Verwendung des WSL2-Kernels
Erklärbare KI ~ Erklärbares k-Mittel- und k-Median-Clustering ~
Unüberwachte Textklassifizierung mit Doc2Vec und k-means
Kernel-Selbstschutz (1/2)
Anfänger Kmeans
Kernel-Selbstschutz (2/2)
Verstehe k-means ++
Über _ und __
Vergleichen Sie die Implementierungsbeispiele für scikit-learn und pyclustering k-means