Implémenter l’algorithme K-Means Clustering (regroupement K-Means), Excel VBA

Implémenter l’algorithme K-Means Clustering (regroupement K-Means), Excel VBA

Voici une explication détaillée pour implémenter l’algorithme K-Means Clustering (regroupement K-Means) en utilisant Excel VBA. L’algorithme K-Means est l’un des algorithmes de regroupement (clustering) les plus utilisés. L’idée est de partitionner un ensemble de points de données en K clusters où chaque point appartient au cluster dont le centre est le plus proche.
K-Means Clustering dans Excel VBA
Aperçu des étapes de l’algorithme K-Means :
1. Initialisation : Choisir aléatoirement K centres de clusters.
2. Affectation : Assigner chaque point de données au centre de cluster le plus proche.
3. Recalcul des centres : Calculer les nouveaux centres des clusters comme la moyenne des points dans chaque cluster.
4. Répétition : Répéter les étapes 2 et 3 jusqu’à ce que les centres ne changent plus ou qu’un critère d’arrêt soit atteint.
Implémentation détaillée dans Excel VBA :
1. Préparation des données
Nous supposons que vous avez un jeu de données avec 2 caractéristiques (colonnes) dans une feuille de calcul Excel :

• La colonne A contient la première caractéristique (X1).
• La colonne B contient la deuxième caractéristique (X2).

Nous allons utiliser K = 3 clusters dans cet exemple.
2. Code VBA pour implémenter l’algorithme K-Means
Voici le code VBA pour implémenter l’algorithme de K-Means Clustering :

Sub KMeansClustering()
    ' Définir les variables
    Dim ws As Worksheet
    Dim dataRange As Range
    Dim dataPoints As Range
    Dim k As Integer
    Dim numPoints As Integer
    Dim centroids() As Variant
    Dim assignments() As Integer
    Dim newCentroids() As Variant
    Dim i As Integer, j As Integer
    Dim iterations As Integer
    Dim maxIterations As Integer
    Dim clusterIndex As Integer
    Dim minDist As Double
    Dim dist As Double
    Dim sumX As Double, sumY As Double
    Dim count As Integer
    ' Définir la feuille de calcul et la plage de données
    Set ws = ThisWorkbook.Sheets("Sheet1")
    Set dataRange = ws.Range("A2:B100") ' Modifier cette plage selon vos données
    numPoints = dataRange.Rows.Count
    ' Initialiser le nombre de clusters (K) et le nombre maximal d'itérations
    k = 3 ' Vous pouvez modifier K selon vos besoins
    maxIterations = 100 ' Nombre maximal d'itérations avant d'arrêter
    ' Initialiser les tableaux assignments et centroids
    ReDim assignments(1 To numPoints)
    ReDim centroids(1 To k, 1 To 2) ' Centroids pour chaque cluster
    ReDim newCentroids(1 To k, 1 To 2) ' Nouveaux centroids après recalcul
    ' Étape 1 : Initialiser les centroids de manière aléatoire à partir des points de données
    Randomize
    For i = 1 To k
        centroids(i, 1) = dataRange.Cells(Int(Rnd() * numPoints) + 1, 1).Value
        centroids(i, 2) = dataRange.Cells(Int(Rnd() * numPoints) + 1, 2).Value
    Next i
    ' Étape 2 : Lancer la boucle K-means
    iterations = 0
    Do While iterations < maxIterations
        ' Étape 3 : Assigner chaque point de données au centroid le plus proche
        For i = 1 To numPoints
            minDist = -1
            For clusterIndex = 1 To k
                dist = (dataRange.Cells(i, 1).Value - centroids(clusterIndex, 1)) ^ 2 + _
                       (dataRange.Cells(i, 2).Value - centroids(clusterIndex, 2)) ^ 2
                If minDist = -1 Or dist < minDist Then minDist = dist assignments(i) = clusterIndex End If Next clusterIndex Next i ' Étape 4 : Recalculer les centroids For i = 1 To k sumX = 0 sumY = 0 count = 0 For j = 1 To numPoints If assignments(j) = i Then sumX = sumX + dataRange.Cells(j, 1).Value sumY = sumY + dataRange.Cells(j, 2).Value count = count + 1 End If Next j If count > 0 Then
                newCentroids(i, 1) = sumX / count
                newCentroids(i, 2) = sumY / count
            End If
        Next i
        ' Vérification de la convergence (si les centroids n'ont pas changé)
        Dim converged As Boolean
        converged = True
        For i = 1 To k
            If centroids(i, 1) <> newCentroids(i, 1) Or centroids(i, 2) <> newCentroids(i, 2) Then
                converged = False
                Exit For
            End If
        Next i
        If converged Then Exit Do
        ' Mettre à jour les centroids pour la prochaine itération
        For i = 1 To k
            centroids(i, 1) = newCentroids(i, 1)
            centroids(i, 2) = newCentroids(i, 2)
        Next i
        iterations = iterations + 1
    Loop
    ' Afficher les résultats
    For i = 1 To numPoints
        ws.Cells(i + 1, 3).Value = assignments(i) ' Assigner les labels de cluster dans la colonne C
    Next i
    MsgBox "Clustering terminé !"
End Sub

Explication du code :
1. Variables et préparation :

• ws : L’objet feuille de calcul contenant les données.
• dataRange : La plage de cellules contenant les données (par exemple, les colonnes A et B).
• k : Le nombre de clusters (K).
• centroids() : Tableau pour stocker les centroids de chaque cluster.
• assignments() : Tableau pour stocker l’affectation des points de données aux clusters.
• iterations : Nombre d’itérations de l’algorithme.
• maxIterations : Nombre maximal d’itérations avant d’arrêter l’algorithme.

2. Initialisation des centroids aléatoires :

• Les centroids sont initialisés en sélectionnant aléatoirement des points de données à partir de la plage de données.

3. Affectation des points aux clusters :

• Pour chaque point de données, nous calculons la distance Euclidienne avec chaque centroid et assignons le point au cluster dont le centroid est le plus proche.

4. Recalcul des centroids :

• Après avoir affecté les points aux clusters, nous recalculons les nouveaux centroids comme la moyenne des points de chaque cluster.

5. Vérification de la convergence :

• Si les centroids ne changent plus d’une itération à l’autre, l’algorithme s’arrête, sinon il continue.

6. Affichage des résultats :

• Les affectations des clusters pour chaque point de données sont affichées dans la colonne C de la feuille de calcul.

Comment exécuter ce code :
1. Ouvrez Excel et appuyez sur Alt + F11 pour ouvrir l’éditeur VBA.
2. Insérez un nouveau module (Insertion > Module) et collez le code dans ce module.
3. Fermez l’éditeur et exécutez la macro en appuyant sur Alt + F8, en sélectionnant KMeansClustering, puis en cliquant sur Exécuter.
Les résultats seront affichés dans la colonne C de la feuille de calcul, où chaque point sera affecté à un cluster.
Conclusion :
Le code ci-dessus vous montre comment implémenter l’algorithme K-Means Clustering en utilisant Excel VBA. Vous pouvez modifier le nombre de clusters (K) ou la plage de données selon vos besoins. L’algorithme fonctionne en initialisant des centroids aléatoires, en assignant les points aux clusters, en recalculant les centroids et en répétant ce processus jusqu’à ce que les centroids ne changent plus.