Je n’ai pas retrouvé la citation exacte d’un certain philosophe du 20e siècle dont le nom m’échappe, mais son message était clair : le peuple qui ne comprend pas comment fonctionnent les technologies est en danger, car ceux qui les comprennent ont sur lui un pouvoir immense. C’est pourquoi je lance une série d’articles sur l’Intelligence Artificielle (IA), cette grande inconnue. Je vais essayer de démystifier les processus d’apprentissage d’une IA en décrivant et commentant des bouts de codes accessibles. Il ne faut en effet pas imaginer une IA comme un robot à la conscience unifiée. Une IA est un ensemble de processus conceptualisés par des algorithmes. Ces processus (et donc les algorithmes qui les sous-tendent) sont plus ou moins complexes en fonction des résultats attendus.

Nous allons commencer aujourd’hui par explorer un algorithme relativement simple. Nommé K-Means, il s’agit d’un algorithme de partition de données, une des branches de l’IA. La partition de données peut être utilisée pour faire de la segmentation, de l’extraction de données ou encore de la classification. Dans la grande famille des algorithmes d’IA, on retrouve le nôtre dans la hiérarchie suivante :

  • IA : software final
  • Apprentissage automatique (machine learning) : concevoir, analyser, développer et implémenter des méthodes permettant à une machine d’évoluer par un processus systématique, et ainsi de remplir des tâches difficiles ou impossibles à remplir par des moyens algorithmiques plus classiques.
  • Apprentissage non supervisé (clustering) : diviser un groupe hétérogène de données, en sous-groupes de manière à ce que les données considérées comme les plus similaires soient associées au sein d’un groupe homogène et qu’au contraire les données considérées comme différentes se retrouvent dans d’autres groupes distincts.
  • K-Moyennes (K-Means) : Algorithme résolvant la problématique suivante « Étant donnés des points et un entier k, le problème est de diviser les points en k partitions de façon à minimiser une certaine fonction. »

La particularité d’un algorithme d’apprentissage non supervisé est que les données ne sont pas étiquetées. En apprentissage supervisé, des exemples de ce que l’on cherche sont déjà codifiés et le programme doit alors retrouver dans les données qui lui sont fournies des exemples similaires. Ici, l’algorithme doit trouver tout seul du « sens » dans les données qui lui sont fournies. Les algorithmes de cette famille favorisent ainsi la sérendipité.

K-Means

L’algorithme de K-Means Clustering présenté dans cet article a été conçu dans une optique de classification d’une population en sous-groupes. Nous étudierons d’abord sa formule mathématique et l’explication de celle-ci avant de passer à une représentation graphique du processus pour finir dans le code même de l’algorithme.

Description

K-Means Clustering : formule

La formule mathématique de la fonction de clustering peut se lire de la manière suivante : Étant donné un ensemble de points (x1, x2, x3, xi…), on cherche à partitionner les n points en k clusters en minimisant la distance entre les points à l’intérieur de chaque cluster.

Pour réaliser ceci de manière pratique, on peut suivre les étapes suivantes :

  1. Choisir un nombre de clusters k
  2. Désigner aléatoirement k points comme barycentres (centroid) de clusters
  3. Répéter jusqu’à ce que chaque point de n soit assigné au même barycentre deux itérations de suite :
    1. Assigner chaque point au cluster le plus proche
    2. Mettre à jour le barycentre de chaque cluster

 

Numérisation des données

L’algorithme ayant besoin d’établir des distances entre les données, celles-ci ne peuvent être caractérisées que par des éléments numériques. Mais alors, comment faire pour distinguer des couleurs ou les hommes des femmes ? En pratique on codifie ces données. Par exemple, on pourra utiliser les représentations RGB des couleurs et assigner des valeurs différentes aux hommes et aux femmes. Un point x d’un ensemble n peut ainsi posséder de nombreuses caractéristiques que l’on qualifiera de dimensions.

$people = array(
'p1' => array(
    'age' => 28,
    'sex' => 1),
'p2' => array(
    'age' => 56,
    'sex' => 0),
'p3' => array(
    'age' => 35,
    'sex' => 0)
);
Données à 2 dimensions
$colors = array(
'c1' => array(
    'r' => 189,
    'g' => 128,
    'b' => 64),
'c2' => array(
    'r' => 240,
    'g' => 29,
    'b' => 146)
);
Données à 3 dimensions

Représentation graphique

Les données possédant de une à trois dimensions peuvent être représentées graphiquement. Les autres ne peuvent qu’être mathématiquement appréhendées. Voici une représentation simplifiée du processus itératif que l’algorithme va effectuer sur des données à deux dimensions. Dans cet exemple, l’algorithme retournera les résultats à l’itération 3 car les clusters définis seront identiques à ceux de l’itération 2.

K-Means Clustering : processus

 

Code

La version présentée est une version abrégée ; vous pourrez trouver l’algorithme complet ici.

public function kMeans($dataset, $k = 2)
{
    //Initialization of the centroids points
    $centroids = $this->initializeCentroidsRandom($dataset, $k);

    $mapping = array();

    while (true) {
        //Assign centroids
        $new_mapping = $this->assignCentroids($dataset, $centroids);

        //If no data has moved to another centroid that means the clusters are found
        if ($mapping != $new_mapping) {
            $mapping = $new_mapping;
        } else {
            return $new_mapping;
        }

        //Move centroids
        $centroids = $this->moveCentroids($mapping);
    }
}

private function initializeCentroidsRandom($dataset, $k)
{
    $centroids = array();
    $dataset_size = count($dataset);

    for ($i=0; $i < $k; ++$i) {
        $data_rand = array_rand($dataset);
        $centroids[$i] = $dataset[$data_rand];
        //Unset the data point for it not to be used again as an initialization point
        unset($dataset[$data_rand]);
    }

    return $centroids;
}

private function assignCentroids($dataset, $centroids)
{
    $map = array();

    foreach ($dataset as $dataID => $datavalue) {
        $min_distance = null;
        $min_centroid = null;

        foreach ($centroids as $centroidID => $centroidvalue) {
            //Distance between the data and the centroid
            $dist = $this->Common->euclideanDistance($datavalue, $centroidvalue);
            //If it's closer we save the centroid ID
            if ($min_distance == null or $dist < $min_distance) {
                $min_distance = $dist;
                $min_centroid = $centroidID;
            }
        }

        $map[$min_centroid][$dataID] = $datavalue;
    }

    return $map;
}

private function moveCentroids($mapping)
{
    $centroids = array();

    foreach ($mapping as $centroidID => $data) {
        //Set centroid new coordinates
        $centroids[$centroidID] = $this->Common->centroid($data);
    }

    return $centroids;
}
K-Means Clustering

On retrouve dans le code les étapes présentées précédemment :

  1. Ligne 10, on choisit le nombre de clusters
  2. Ligne 13, on initialise aléatoirement les barycentres en sélectionnant au hasard (ligne 48) un point dans l’ensemble des données
  3. Lignes 17 à 30, tant qu’on n’a pas une cartographie (itération précédente) strictement égale à la nouvelle cartographie (itération actuelle, ligne 22), on effectue deux actions :
    1. Ligne 19, on calcule la distance de chaque point avec l’ensemble des barycentres préétablis (ligne 76) et on crée une cartographie des points attribués à chaque barycentre (ligne 84).
    2. Ligne 29, on recalcule le barycentre de chaque cluster de la nouvelle cartographie (ligne 104).
  4. Une fois que deux cartographies sont similaires, on renvoie les résultats (ligne 25).

 

Limites

Cet algorithme est limité par deux éléments :

  • Le nombre de clusters est défini par l’utilisateur. Il se pourrait très bien que notre population possède des caractéristiques qui font que 3 clusters la partitionneraient mieux que 2 clusters. On peut pour cela précéder notre K-Means Clustering d’une Classification Ascendante Hiérarchique qui définira automatiquement le meilleur nombre de clusters à choisir.
  • Les clusters finaux peuvent dépendre de l’initialisation aléatoire des barycentres et donc proposer des résultats différents pour les mêmes données. Dans l’algorithme complet que je n’ai pas présenté ici, j’ai proposé une solution pour initialiser des barycentres fictifs sur une droite traversant l’ensemble des dimensions des données.

 

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.