fr en

L'algorithme des k-moyennes n'est pas la panacée

Posté le Sun 09 December 2018 dans machine learning • 6 min de lecture

Cet article est le numéro 2 de la série "clustering" :

Les k-moyennes (ou k-means) est l'algorithme de classification non supervisée le plus connu et le plus utilisé. Il présente cependant plusieurs inconvénients et ne se comporte pas bien sur certains jeux de données.

En fait, chaque algorithme de clustering a ses propres forces et faiblesses. Chacun repose sur des hypothèses sur le jeu de données et exploite ces propriétés pour segmenter les données. Le théorème "No Free Lunch" stipule que "deux algorithmes quelconques sont équivalents lorsque leurs performances sont moyennées sur tous les problèmes possibles". Cela signifie que nous ne pouvons pas utiliser un seul algorithme pour tous les jeux de données. Le rôle de l'utilisateur est donc de choisir le bon algorithme pour traiter le jeu de données. Pour cela, il est important de connaître le comportement des algorithmes sur plusieurs jeux de données et de comprendre comment ils se comporteront sur de nouveaux jeux de données. Les propriétés des jeux de données et les hypothèses sur lesquelles repose l'algorithme, ainsi que son critère, peuvent nous donner des indications.

Cet article présente l'algorithme de classification non supervisée des k-moyennes en :

l'utilisant avec le langage R sur les jeux de données générés dans un précédent article;
étudiant les hypothèses qu'il fait sur les données;
présentant son critère et la famille d'algorithmes à laquelle il appartient;

Il ne s'agit pas d'une présentation exhaustive de k-means : par exemple, cet article ne présente ni l'algorithme ni son temps d'exécution. Nous ne nous pencherons pas non plus sur certains problèmes importants auxquels nous sommes confrontés lors de l’utilisation, tels que tomber dans les optima locaux et trouver le nombre approprié de clusters.

Comportement de k-means sur des jeux de données générés

Voyons d'abord comment il se comporte sur certains jeux de données générés. Nous pouvons générer des jeux de données intéressants avec le code R suivant :

library(mvtnorm)
library(dplyr)
library(movMF)

generateGaussianData <- function(n, center, sigma, label) {
    data = rmvnorm(n, mean = center, sigma = sigma)
    data = data.frame(data)
    names(data) = c("x", "y")
    data = data %>% mutate(class=factor(label))
    data
}

dataset1 <- {
    # cluster 1
    n = 500
    center = c(5, 5)
    sigma = matrix(c(1, 0, 0, 1), nrow = 2)
    data1 = generateGaussianData(n, center, sigma, 1)

    # cluster 2
    n = 500
    center = c(1, 1)
    sigma = matrix(c(1, 0, 0, 1), nrow = 2)
    data2 = generateGaussianData(n, center, sigma, 2)

    # all data
    data = bind_rows(data1, data2)

    data$dataset = "1 - Mixture of Gaussians"

    data
}

dataset2 <- {
    # cluster 1
    n = 2000
    center = c(5, 5)
    sigma = matrix(c(1, 0, 0, 1), nrow = 2)
    data1 = generateGaussianData(n, center, sigma, 1)

    # cluster 2
    n = 50
    center = c(1, 1)
    sigma = matrix(c(1, 0, 0, 1), nrow = 2)
    data2 = generateGaussianData(n, center, sigma, 2)

    # all data
    data = bind_rows(data1, data2)

    data$dataset = "2 - Different sizes"

    data
}

dataset3 <- {
    # cluster 1
    n = 100
    center = c(5, 5)
    sigma = matrix(c(3, 0, 0, 3), nrow = 2)
    data1 = generateGaussianData(n, center, sigma, 1)

    # cluster 2
    n = 100
    center = c(1, 1)
    sigma = matrix(c(0.1, 0, 0, 0.1), nrow = 2)
    data2 = generateGaussianData(n, center, sigma, 2)

    # all data
    data = bind_rows(data1, data2)

    data$dataset = "3 - Different variances"

    data
}

dataset4 <- {
    # cluster 1
    n = 500
    center = c(4, 4)
    sigma = matrix(c(1, -0.99, -0.99, 1), nrow = 2)
    data1 = generateGaussianData(n, center, sigma, 1)

    # cluster 2
    n = 500
    center = c(5, 5)
    sigma = matrix(c(1, -0.99, -0.99, 1), nrow = 2)
    data2 = generateGaussianData(n, center, sigma, 2)

    # all data
    data = bind_rows(data1, data2)

    data$dataset = "4 - Non zero covariance"

    data
}

generateMFData <- function(n, theta, cluster, scale=1) {
    data = rmovMF(n, theta)
    data = data.frame(data[,1], data[,2])
    data = scale * data
    names(data) = c("x", "y")
    data = data %>% mutate(class=factor(cluster))
    data
}

dataset6 <- {
    # cluster 1
    n = 100
    data1 = generateMFData(n, 1 * c(-1, 1), 1, 5)

    # cluster 2
    n = 100
    data2 = generateMFData(n, 1 * c(1, -1), 2, 1)

    # all data
    data = bind_rows(data1, data2)

    data$dataset = "6 - Spherical classes"

    data
}

generateSpiralData <- function(n) {
    maxRadius = 7
    xShift = 2.5
    yShift = 2.5
    angleStart = 2.5 * pi
    noiseVariance = 0.1

    # first spiral
    firstSpiral <- function() {
        d1 = data.frame(0:(n-1))
        colnames(d1) <- c("i")
        d1 %>% mutate(angle = angleStart + 2.5 * pi * (i / n),
                      radius = maxRadius * (n + n/5 - i)/ (n + n/5),
                      x = radius * sin(angle),
                      y = radius * cos(angle),
                      class=1)
    }
    d1 = firstSpiral()

    # second spiral
    d2 = d1 %>% mutate(x = -x, y = -y, class=2)

    # combine, add noise, and shift
    generateNoise <- function(n) {
        sigma = matrix(c(noiseVariance, 0, 0, noiseVariance), nrow = 2)
        noise = rmvnorm(n, mean = c(0, 0), sigma = sigma)
        df = data.frame(noise)
        colnames(df) <- c("xNoise", "yNoise")
        df
    }
    d1 %>%
        bind_rows(d2) %>%
        bind_cols(generateNoise(2*n)) %>%
        transmute(x = x + xShift + xNoise,
                  y = y + yShift + yNoise,
                  dataset = "7 - Spirals",
                  class = factor(class))
}

dataset7 = generateSpiralData(500)

dataset8 <- {
    generateUniformData <- function(cluster, minX, maxX) {
        x = runif(500, min = minX, max = maxX)
        y = runif(500, min = -4, max = 9)
        data.frame(x, y) %>% mutate(class=cluster)
    }

    generateUniformData(1, -4, 1) %>% bind_rows(generateUniformData(2, 3, 9)) %>%
        mutate(dataset = "8 - Uniform data",
               class = factor(class))
}

dataset9 <- {
    generateuniformdata <- function(cluster) {
        x = runif(500, min = -4, max = 9)
        y = runif(500, min = -4, max = 9)
        data.frame(x, y) %>% mutate(class=cluster)
    }

    generateuniformdata(1) %>% bind_rows(generateuniformdata(2)) %>%
        mutate(dataset = "9 - unclustered data",
               class = factor(class))
}

data = bind_rows(dataset1, dataset2, dataset3, dataset4, dataset5, dataset6, dataset7, dataset8, dataset9)

On peut alors appliquer l'algorithme des k-moyennes sur ces jeux de données avec le code suivant :

dataKmeans = data %>%
             group_by(dataset) %>%
             do(data.frame(.,
                           cluster = factor(kmeans(cbind(.$x,.$y),
                           centers=2)$cluster)))

Notons que nous avons utilisé la fonction do de dplyr pour appliquer l'algorithme à chaque jeu de données. L' algorithme kmeans est intégré à R (d'autres implémentations sont disponibles en utilisant des bibliothèques).

Visualiser les neuf jeux de données et colorier les points en fonction des clusters trouvés par l'algorithme peut être effectué avec le code suivant :

library(ggplot2)

scatterPlotWithLabels <- function(data) {
    scatterPlot = ggplot(data, aes(x=x, y=y, shape=class, color=cluster)) +
        geom_point() +
        coord_fixed() +
        scale_shape_manual(values=c(2, 3)) +
        facet_wrap(~dataset, nrow=3)
    scatterPlot
}

scatterPlotWithLabels(dataKmeans)

Cela produit le graphique suivant :

Cela fonctionne plutôt bien pour le premier jeu de données, mais malheureusement pas pour les autres. Ce comportement est prévisible lorsque nous connaissons le critère optimisé par l'algorithme et comment les données sont générées.

Hypothèses et critères de l'algorithme des k-moyennes

Pour un nombre donné de cluster K et un ensemble de N vecteurs \(x_i , i \in [1, N]\), K-means a pour objectif de minimiser le critère suivant :

\begin{equation*} W(z, \mu) = \sum_{k=1}^{K} \sum_{i=1}^{N} z_{ik} ||x_i - \mu_k||^2 \end{equation*}

avec :

\(z_{ik} \in {0, 1}\) indique si le vecteur \(x_i\) appartient au cluster \(k\);
\(\mu_k \in \mathbb{R}^p\), le centre du cluster \(k\).

Il minimise la variance intra-cluster, c'est-à-dire la somme des distances au carré entre le centre du cluster et les objets qui lui sont associés.

Pour comprendre pourquoi l'algorithme fonctionne bien sur le premier jeu de données et non sur les autres, il est utile de voir que le critère est un cas particulier d'un modèle plus large : les modèles de mélange gaussien tentent d'optimiser le critère suivant :

\begin{equation*} L_C(\theta) = \sum_{i, k} z_{ik} \log (\pi_k \phi_k(x_i, \alpha_k)) \end{equation*}

où :

\(\theta = (\pi, \alpha)\) avec \(\pi\) est un vecteur des proportions et \(\alpha\) est un vecteur de paramètres d'une composante;
\(\phi_k(x_i, \alpha_k)\) est la probabilité d'une observation \(x_i\) de provenir de la \(k^{eme}\) composante.

Si on considère un mélange de Gaussiennes, la fonction de densité est définie par :

\begin{equation*} \phi_k(x; \mu, \Sigma) = \frac{1}{(2 \pi)^{n/2} |\Sigma|^{1/2}} \exp (- \frac{1}{2} (x - \mu)^T \Sigma^{-1} (x-\mu)) \end{equation*}

avec :

\(n\) le nombre de dimensions du vecteur \(x\);
\(\mu\) le vecteur moyen;
\(\Sigma\) la matrice de covariance.

Si on considère un mélange de Gaussiennes avec une matrice de covariance égale à l'identité (même variance et covariances nulles) et des proportions égales (tous les \(\pi_k\) sont égaux), on obtient, à une constante près, le critère des k-moyennes.

Ainsi, il est prévisible que l'algorithme des k-moyennes fonctionne bien sur le premier jeu de données car il correspond parfaitement aux hypothèses sur la distribution de probabilité générant les objets à regrouper.

Ce qu'il faut retenir

Voici quelques points à retenir de cet article :

Il n’existe pas d’algorithme de clustering pour les gouverner tous : l’utilisateur doit choisir avec soin l’algorithme en fonction des données et du critère à optimiser.
K-means suppose que les données sont générées par un mélange de Gaussiennes ayant la même variance, la même proportion (même nombre d'objets par classe) et aucune covariance intra-classe.

Le deuxième point peut être vu de deux manières :

Si on a un a priori sur les données, on peut choisir l'algorithme pour regrouper les données en fonction du critère optimisé et de l'a priori qu'on a sur les données.
Si on n'a aucun a priori sur les données, on peut toujours appliquer k-means, mais on doit veiller à ne pas surinterpréter les résultats. Par exemple, la taille des clusters est imposée par l'algorithme. On ne peut donc pas en déduire que les classes sous-jacentes ont des proportions égales.

Previous Post Next Post

Comportement de k-means sur des jeux de données générés

Hypothèses et critères de l'algorithme des k-moyennes

Ce qu'il faut retenir

Vous pourriez aimer