Clustering

Solutions du code

Module .../moteurs_clustering/clustering_kmeans.py

from .cluster_mean import ClusterMean
from .clustering import Clustering

class ClusteringKMeans(Clustering):
    """ K-means clustering. """

    def __init__(self, k, dist_f):
        """
            :param k: le nombre de clusters à construire.
            :param dist_f: la fonction de distance entre deux données.
        """

        super().__init__()
        self.k = k
        self.dist_f = dist_f

    def noyaux(self, clusters):
        """ Extrait les noyaux d'une liste de clusters.

           :param list clusters: une liste de clusters dont les noyaux doivent\
           être retournés.
           :return: la liste des noyaux des clusters.
        """

        return [cluster.noyau for cluster in clusters]

    def initialise_clusters(self, donnees):
        """ Initialise les clusters.

            :param list donnees: les données à regrouper dans des clusters.
        """
        if len(donnees) < self.k:
            raise Exception('Il faut au moins {} données'.format(self.k))

        # Crée les clusters autour des noyaux, qui sont les premières k données.
        noyaux = [(donnees[i], str(i + 1)) for i in range(self.k)]
        self.clusters = [ClusterMean([noyau[0]], noyau[1]) for noyau in noyaux]

        # Ajoute toutes les autres données au premier cluster.
        self.clusters[0].ajoute_donnees(donnees[self.k:])

    def fini(self, anciens_clusters):
        """ Teste si les clusters ont changé par rapport aux anciens clusters.

            C'est le cas si les noyaux ont changé depuis l'itération précédente.

            :param list anciens_clusters: la liste des anciens clusters.
        """
        return self.noyaux(self.clusters) == self.noyaux(anciens_clusters)

    def revise_clusters(self):
        """ Révise les clusters. """
        # Extrait toutes les données des anciens clusters, sauf les noyaux.
        donnees = []
        for cluster in self.clusters:
            donnees.extend([d for d in cluster.donnees if d != cluster.noyau])

        # Réinitialise les nouveaux clusters aux noyaux des anciens clusters.
        for cluster in self.clusters:
            cluster.vide(garde_noyau=True)

        # Assigne chaque donnée au cluster du noyau duquel il est le
        # plus proche.
        for donnee in donnees:
            distances = [(self.dist_f(donnee, cluster.noyau), cluster)
                         for cluster in self.clusters]
            cluster = min(distances, key=lambda x: x[0])[1]
            cluster.ajoute_donnee(donnee)

        # Recentre le noyau de chaque nouveau cluster.
        for cluster in self.clusters:
            cluster.centre(self.dist_f)

    def affiche_clusters(self):
        """ Affiche les clusters construits par l'algorithme."""

        print('\n'.join([str(cluster) for cluster in self.clusters]))

Module .../moteurs_clustering/clustering_hierarchique.py

from .cluster_hierarchique import ClusterHierarchique
from .clustering import Clustering

class ClusteringHierarchique(Clustering):
    """ Clustering hiérarchique. """

    liens = {
        'single': min,
        'complete': max,
    }

    def __init__(self, type_lien, dist_f):
        """
            :param str lien: le type de distance entre deux clusters,\
            'single' ou 'complete'.
            :param dist_f: la fonction de distance entre deux données.
        """

        super().__init__()
        self.dist_f = dist_f
        # Permet d'utiliser min ou max de manière générique en fonction du
        # paramètre type_lien.
        self.lien = self.liens[type_lien]

    def fusionne_clusters(self, cluster1, cluster2):
        """ Fusionne deux clusters.

            Le nouveau cluster contiendra ``cluster1`` à gauche et ``cluster2``\
            à droite.

            :param cluster1: un noeud qui ira à droite du nouveau cluster.
            :param cluster2: un noeud qui ira à gauche du nouveau cluster.
            :return: le nouveau cluster.
        """

        donnees = cluster1.donnees + cluster2.donnees
        return ClusterHierarchique(donnees, cluster1, cluster2)

    def calcule_distance(self, cluster1, cluster2):
        """ Calcule la distance entre deux clusters. """
        distances = []
        for donnee1 in cluster1.donnees:
            for donnee2 in cluster1.donnees:
                distances.append(self.dist_f(donnee1, donnee2))

        return self.lien(distances)

    def initialise_clusters(self, donnees):
        """ Initialise les clusters.

            :param list donnees: les données à regrouper dans des clusters.
        """
        # Construit les clusters terminaux : un par donnée.
        # Les clusters seront ensuite fusionnés pour créer la hiérarchie.
        self.clusters = [ClusterHierarchique([donnee]) for donnee in donnees]

    def fini(self, anciens_clusters):
        """ Teste si les clusters ont changé par rapport aux anciens clusters.

            C'est le cas si leur nombre a diminué.

            :param list anciens_clusters: la liste des anciens clusters.
        """
        return len(self.clusters) == len(anciens_clusters)

    def revise_clusters(self):
        """ Révise les clusters. """
        if len(self.clusters) == 1:
            return

        # Calcule la distance entre chaque paire de clusters.
        distances = []
        for cluster1 in self.clusters:
            for cluster2 in self.clusters:
                if cluster1 != cluster2:
                    distance = self.calcule_distance(cluster1, cluster2)
                    distances.append((distance, cluster1, cluster2))

        # Trouve les deux clusters les plus proches.
        paire = min(distances, key=lambda x: x[0])
        cluster1 = paire[1]
        cluster2 = paire[2]

        # Fusionne ces deux clusters.
        nouveau_cluster = self.fusionne_clusters(cluster1, cluster2)
        self.clusters.remove(cluster1)
        self.clusters.remove(cluster2)
        self.clusters.append(nouveau_cluster)

    def affiche_clusters(self):
        """ Affiche les clusters découverts par l'algorithme."""

        print('\n'.join([str(cluster) for cluster in self.clusters]))

Documentation du code

class moteurs_clustering.cluster.Cluster(donnees, nom='')

Représentation d’un cluster générique.

__init__(donnees, nom='')

Initialise un cluster avec un nom et une liste de données.

Paramètres:
  • donnees (list) – les données du cluster.
  • nom (str) – le nom du cluster.
ajoute_donnee(donnee)

Ajoute une donnée au cluster.

Paramètres:donnee – la donnée à ajouter.
ajoute_donnees(donnees)

Ajoute une liste de données au cluster.

Paramètres:donnees (list) – les données à ajouter.
class moteurs_clustering.cluster_mean.ClusterMean(donnees, nom)

Bases: moteurs_clustering.cluster.Cluster

Représentation d’un cluster utilisé dans l’algorithme du k-means.

ClusterMean.__init__(donnees, nom)

Initialise le cluster avec un nom et une liste de données.

Paramètres:
  • donnees (list) – les données du cluster.
  • nom (str) – le nom du cluster.
ClusterMean.ajoute_donnee(donnee)

Ajoute une donnée au cluster.

Paramètres:donnee – la donnée à ajouter.
ClusterMean.ajoute_donnees(donnees)

Ajoute une liste de données au cluster.

Paramètres:donnees (list) – les données à ajouter.
ClusterMean.centre(dist_f)

Recentre le noyau du cluster en fonction des données qu’il contient.

Paramètres:dist_f – la fonction de distance entre deux données.
ClusterMean.vide(garde_noyau=False)

Vide la liste des données du cluster avec l’option de garder le noyau.

class moteurs_clustering.cluster_hierarchique.ClusterHierarchique(donnees, gauche=None, droite=None)

Bases: moteurs_clustering.cluster.Cluster

Représentation d’un cluster utilisé dans l’algorithme de clustering hiérarchique.

ClusterHierarchique.__init__(donnees, gauche=None, droite=None)
Paramètres:
ClusterHierarchique.ajoute_donnee(donnee)

Ajoute une donnée au cluster.

Paramètres:donnee – la donnée à ajouter.
ClusterHierarchique.ajoute_donnees(donnees)

Ajoute une liste de données au cluster.

Paramètres:donnees (list) – les données à ajouter.
ClusterHierarchique.est_terminal()

Teste si le cluster courant est terminal (c’est-à-dire s’il n’a pas de sous-clusters ni à gauche ni à droite).

Retourne:True quand le cluster courant est terminal.
ClusterHierarchique.repr_hierarchie(level=0)

Représentation sous forme de string de la hiérarchie de laquelle le cluster courant est la racine.

class moteurs_clustering.clustering.Clustering

Classe générique pour le clustering.

Devra être sous-classée selon le type de clustering.

__init__()
fini(anciens_clusters)

Teste si les clusters ont changé par rapport aux anciens clusters (à implémenter différemment pour le clustering k-means et le clustering hiérarchique).

Paramètres:anciens_clusters (list) – la liste des anciens clusters.
initialise_clusters(donnees)

Initialise les clusters (à implémenter différemment pour le clustering k-means et le clustering hiérarchique).

Paramètres:donnees (list) – les données à regrouper dans des clusters.
itere(donnees)

Regroupe les données dans des clusters de façon itérative.

Paramètres:donnees (list) – les données à regrouper dans des clusters.
revise_clusters()

Révise les clusters (à implémenter différemment pour le clustering k-means et le clustering hiérarchique).

class moteurs_clustering.clustering_kmeans.ClusteringKMeans(k, dist_f)

Bases: moteurs_clustering.clustering.Clustering

K-means clustering.

ClusteringKMeans.__init__(k, dist_f)
Paramètres:
  • k – le nombre de clusters à construire.
  • dist_f – la fonction de distance entre deux données.
ClusteringKMeans.affiche_clusters()

Affiche les clusters construits par l’algorithme.

ClusteringKMeans.fini(anciens_clusters)

Teste si les clusters ont changé par rapport aux anciens clusters.

C’est le cas si les noyaux ont changé depuis l’itération précédente.

Paramètres:anciens_clusters (list) – la liste des anciens clusters.
ClusteringKMeans.initialise_clusters(donnees)

Initialise les clusters.

Paramètres:donnees (list) – les données à regrouper dans des clusters.
ClusteringKMeans.itere(donnees)

Regroupe les données dans des clusters de façon itérative.

Paramètres:donnees (list) – les données à regrouper dans des clusters.
ClusteringKMeans.noyaux(clusters)

Extrait les noyaux d’une liste de clusters.

Paramètres:clusters (list) – une liste de clusters dont les noyaux doivent être retournés.
Retourne:la liste des noyaux des clusters.
ClusteringKMeans.revise_clusters()

Révise les clusters.

class moteurs_clustering.clustering_hierarchique.ClusteringHierarchique(type_lien, dist_f)

Bases: moteurs_clustering.clustering.Clustering

Clustering hiérarchique.

ClusteringHierarchique.__init__(type_lien, dist_f)
Paramètres:
  • lien (str) – le type de distance entre deux clusters, ‘single’ ou ‘complete’.
  • dist_f – la fonction de distance entre deux données.
ClusteringHierarchique.affiche_clusters()

Affiche les clusters découverts par l’algorithme.

ClusteringHierarchique.calcule_distance(cluster1, cluster2)

Calcule la distance entre deux clusters.

ClusteringHierarchique.fini(anciens_clusters)

Teste si les clusters ont changé par rapport aux anciens clusters.

C’est le cas si leur nombre a diminué.

Paramètres:anciens_clusters (list) – la liste des anciens clusters.
ClusteringHierarchique.fusionne_clusters(cluster1, cluster2)

Fusionne deux clusters.

Le nouveau cluster contiendra cluster1 à gauche et cluster2 à droite.

Paramètres:
  • cluster1 – un noeud qui ira à droite du nouveau cluster.
  • cluster2 – un noeud qui ira à gauche du nouveau cluster.
Retourne:

le nouveau cluster.
ClusteringHierarchique.initialise_clusters(donnees)

Initialise les clusters.

Paramètres:donnees (list) – les données à regrouper dans des clusters.
ClusteringHierarchique.itere(donnees)

Regroupe les données dans des clusters de façon itérative.

Paramètres:donnees (list) – les données à regrouper dans des clusters.
ClusteringHierarchique.revise_clusters()

Révise les clusters.