k-means et kernel k-means

J'ai commencé à écrire le contenu de mon étude sur un autre blog en utilisant la période d'attente à la maison, mais comme la fonction tex était de la merde, je vais déplacer certains articles vers qiita. .. ..

J'ai appris k-means, l'algorithme [source] le plus basique pour l'apprentissage non supervisé, et je l'ai essayé facilement.

k-means Une des méthodes pour séparer des données données en plusieurs clusters.

Avantages etc.

avantage

• L'algorithme est simple et facile à comprendre
• Le résultat n'est pas difficile à interpréter

Puisqu'il est classé en fonction de la distance du centre du cluster, il est presque toujours vrai que le résultat est intuitif lorsqu'il est tracé.

Désavantage

• Le nombre de clusters doit être spécifié à l'avance (ce n'est pas quelque chose qui reconnaît le nombre de clusters à l'avance)
• Ne convient pas aux choses qui ne peuvent pas être séparées linéairement

algorithme

donné

• Ensemble de données $ x_i $
• Nombre de clusters $ K $

Méthode de calcul

1. Attribuez au hasard le cluster $ k_i $ à toutes les données $ x_i $ $ (x_i, k_i) $ 1.Central pour chaque cluster(m_k)Cherchantm_k |N_k| = \sum_{i \in N_k} x_i
2. Calculez la distance à tous les centres de cluster pour toutes les données et mettez à jour vers le cluster le plus court
3. Répétez 2-3 jusqu'à ce qu'il n'y ait plus de mises à jour de cluster

Où $ N_k $ est l'ensemble des données contenues dans le cluster $ k $ à ce moment.

Exemple d'utilisation

Expérimentez les paramètres suivants dans les ensembles de données de sklearn.

• n_samples = 100
• factor = 0.1
• noise = 0.01

Avec les paramètres ci-dessus, deux clusters, un cercle de rayon de 0,1 et un cercle de rayon de 1, sont obtenus sous un bruit de 0,01.

code

# k:Nombre de clusters
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

Résultat expérimental

Le résultat de la rotation des k-moyens est le suivant. Puisque les données ne peuvent pas être clairement séparées de manière linéaire, on peut voir que les résultats de la classification ne sont pas correctement classés comme prévu.

kernel k-means

Avantages etc.

avantage

• Une séparation non linéaire est également possible

Désavantage

• Le résultat de la classification dépend grandement de la manière de sélectionner la fonction du noyau et les paramètres du noyau.

algorithme

donné

• Ensemble de données $ x_i $
• Nombre de clusters $ K $
• Fonction du noyau (et paramètres requis pour cette fonction du noyau)

Presque le même que les k-moyens normaux. Lors de la recherche du centre de chaque cluster, le centre de l'espace des fonctionnalités peut être trouvé. Autrement dit, en considérant le cluster $ k $, nous définissons le vecteur $ m_k $, qui minimise le montant suivant, comme le centre du cluster $ k $.

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

$ M_k] pour minimiser cela peut être obtenu comme suit.

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

En utilisant cela, la distance entre les données $ x_i $ et le cluster $ k $ est la suivante.

\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}
}

Où $ K (x, y) $ est une fonction du noyau.

Exemple d'utilisation

Expérimentez les paramètres suivants dans les ensembles de données de sklearn.

• n_samples = 100
• factor = 0.1
• noise = 0.01

La fonction noyau utilise le noyau RBF suivant.

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

code

# kernel:Fonction noyau qui reçoit 2 variables
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 = {}
  #La corrélation en classe est lourde lorsqu'elle est calculée plusieurs fois, alors mettez-la en cache
  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

  #Calculer la distance au centre du cluster dans l'espace des fonctionnalités
  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

Résultat expérimental

Le résultat de la rotation du noyau k-means est le suivant. Le paramètre du noyau $ \ sigma $ est de 0,5 $.

Si kernel k-means fonctionne (ne fonctionne pas)

Considérez la situation suivante.

• Nombre de clusters 2
• Cluster $ c_r $ uniformément distribué sur la circonférence de rayon $ r $ et cluster $ c_R $ uniformément distribué sur la circonférence de rayon $ R $
• r \lt R
• Le nombre de données est suffisamment grand et la somme peut être remplacée avec une précision suffisante par intégration.
• Les données sont correctement classées. Autrement dit, les données sur le rayon $ r $ ont été classées dans le cluster $ c_r $ et les autres dans le cluster $ c_R $.
• Les fonctions du noyau utilisent le noyau RBF

Dans la situation ci-dessus, de nouvelles données $ D = (x, y) = (R, 0) $ sont ajoutées et classées. Dans ce cas, si la distance pour entrer dans la classe $ c $ s'écrit $ C (c) $, la distance aux classes $ c_r $ et $ c_R $ sera la suivante.

\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}
}

Où $ I_ \ alpha (x) $ est une fonction Vessel modifiée. À propos de cela, quand il s'agit de $ r \ ll \ sigma \ ll R $

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

Évidemment $ C (c_R) \ lt C (c_r) $, il est donc classé comme le cluster correct. Aussi, quand $ \ 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}
}

Si vous regardez la zone où les deux sont égaux,r=RIl n'y a pas d'autre choix que sinonC(c_r) \lt C(c_R)Cela devient une classification incorrecte. L'important ici est\sigmaQuand\delta r := |R - r|Peu importe la taille de l'échelle. Aussir, R \ll \sigmaQuand

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

De toute évidence, il ne peut pas être classé correctement. De plus, en considérant l'ordre de lecture de $ r / \ sigma et R / \ sigma $, on peut voir qu'ils ne sont pas classés correctement car ils ont la même expression que les k-means normaux.

De même, considérons le cas où les données $ d = (x, y) = (r, 0) $ sont ajoutées. La distance du centre de la classe

\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}
}

À propos de cela, quand il s'agit de $ r \ ll \ sigma \ ll R $

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

Évidemment $ C (c_r) \ lt C (c_R) $, il est donc classé comme le cluster correct. Aussi, quand $ \ 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}
}

Dans ce cas également, si vous regardez la zone où les deux sont égaux, il n'y a que $ r = R $, et sinon c'est $ C (c_r) \ lt C (c_R) $, ce qui est une classification incorrecte. Aussi, quand c'est $ r, R \ ll \ sigma $

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

De toute évidence, il ne peut pas être classé correctement. De même, en considérant l'ordre de lecture de $ r / \ sigma et R / \ sigma $, l'expression est la même que celle des k-means normaux dans ce cas également.

Comme vous pouvez le voir à partir de ces résultats, la classification fonctionne bien lorsque $ \ sigma $, qui est la résolution de la fonction du noyau, est entre les échelles des deux clusters. Peut-être que le noyau RBF ne peut pas regarder dans la direction, seulement la taille, en particulier plus grande ou plus petite que l'échelle donnée $ \ sigma $. Par conséquent, si l'échelle du noyau n'est pas entre les échelles de chaque classe, on considère qu'elle ne fonctionne pas comme prévu.

Faisons une expérience numérique concrète. Changeons $ \ sigma $ sous les mêmes paramètres $ r = 0,1, R = 1 $ que précédemment. Voyons comment il se comporte en particulier dans les domaines de $ \ sigma \ ll r, R $, $ r \ ll \ sigma R $, $ r, R \ ll \ sigma $.

• Pour $ \ sigma \ ll r, R $

\sigma = 0.01, r=0.1, R=1

• Pour $ r \ ll \ sigma R $

\sigma = 0.5, r=0.1, R=1

• Pour $ r, R \ ll \ sigma $

\sigma = 2, r=0.1, R=1

Impressions

kernel k-means n'est pas facile à utiliser car il dépend fortement du noyau et de ses paramètres. Cependant, les k-moyens ordinaires ne fonctionnent que pour les moyens séparables linéairement et ne sont pas faciles à utiliser. .. ..

référence

--Hajipata --Castella livre

• https://research.miidas.jp/2019/07/kernel-kmeans%E3%81%AEnumpy%E5%AE%9F%E8%A3%85/