Actuariat Data science

CENTROÏDES PARFAITS : MINIMISER LE SSE DANS LE CLUSTERING

 

L’algorithme k-means est une méthode puissante pour regrouper des éléments en fonction de leurs caractéristiques. Mais comment s’assurer que ces regroupements sont optimaux ? Découvrez comment minimiser les erreurs de clustering pour obtenir des résultats fiables et précis. Cet article vous guidera à travers les concepts clés et leurs applications pratiques.

INTRODUCTION

L’algorithme k-means se distingue par sa capacité fascinante à regrouper divers éléments en fonction de leurs caractéristiques intrinsèques. Son application est remarquablement simple : il suffit de l’exécuter jusqu’à ce que les clusters se stabilisent. Toutefois, une question cruciale se pose : comment évaluer la qualité de notre regroupement ?

En d’autres termes : ce clustering est-il optimal ? Pourrions-nous obtenir une classification encore plus précise ? Cette question est essentielle, car elle conditionne la fiabilité des résultats obtenus. Des résultats solides et précis permettent aux entreprises de prendre des décisions éclairées et stratégiques en toute confiance.

Dans le but de répondre à ces interrogations, nous allons nous concentrer sur l’analyse des erreurs des clusters.

I) LES ERREURS

Lorsqu’on réalise un clustering, l’objectif est de former des groupes distincts. Ces groupes doivent être constitués de manière à ce que les éléments d’un groupe soient le plus proches possible de leur centroïde. Pour vérifier cela, nous calculons le carré de la distance de chaque élément du cluster à son centroïde. Nous utilisons le carré des distances afin de pénaliser les grandes distances, c’est-à-dire les éléments très éloignés du centroïde. Ensuite, nous en faisons la somme. Cette somme est appelée : ” Erreur du cluster ”

En additionnant les erreurs de chaque cluster, on obtient l’erreur totale du clustering. L’objectif devient alors de minimiser cette erreur afin d’obtenir le meilleur regroupement possible.

En anglais, cette erreur est appelée ” Sum of Squared Errors (SSE) “. On écrit SSE(C) pour désigner l’erreur du clustering C et SSEk(C) pour désigner l’erreur du cluster k du clustering C.

Ainsi, pour un clustering de K clusters, on a :

SSE(C) = \sum_{k=1}^{K} SSE_k(C)

II) MINIMISONS SSE

Soient un ensemble de données de n points D = \lbrace x_{1}, x_{2}, ..., x_{n} \rbrace et le clustering obtenu par l’algorithme k-means C = \lbrace C_{1}, C_{2}, ..., C_{K} \rbrace.

En considérant c_{k} comme le centroïde du cluster C_{k}, on écrit que :

Erreur du cluster k : SSE_{k}(C) = \sum_{x \in C_{k} } d(x ; c_{k})^{2}

Avec d la distance euclidienne de x à c_{k}, c’est a dire : d(x ; c_{k}) = \sqrt{ (x - c_{k})^{2} }

Or                                         SSE_{k}(C) = \sum_{x \in C_{k} } (x - c_{k})^{2}

Ainsi :                                   SSE(C) = \sum_{k = 1}^{K} SSE_{k}(C)}

On a donc:                            SSE(C) = \sum_{k = 1}^{K} \sum_{x \in C_{k} }(x - c_{k})^{2}

Vu que SSE(C) représente la somme des erreurs de chaque cluster, minimiser SSE(C) revient a minimiser chacune des erreurs de chaque cluster, c’est-à-dire minimiser SSE_{k}(C).

Il parait évident de poser la dérivée par rapport à c_{k} de SSE_{k}(C) égale 0 et de trouver le c_{k} qui minimise SSE_{k}(C).

On a donc :

\frac{\partial{}}{\partial{c_{k}}} (SSE_{k}(C)) = 0 \Leftrightarrow \frac{\partial{}}{\partial{c_{k}}} (\sum_{x \in C_{k}} (x - c_{k})^{2}}) = 0

                               \Leftrightarrow 2 \sum_{x \in C_{k}} (-1) (x - c_{k}) = 0}

                               \Leftrightarrow \sum_{x \in C_{k}} c_{k} = \sum_{x \in C_{k}} x

                               \Leftrightarrow c_{k} (\sum_{x \in C_{k}} 1) = \sum_{x \in C_{k}} x

Or \sum_{x \in C_{k}} 1 représente le nombre d’éléments du cluster k

Notons le Card(C_{k})

On obtient donc : c_{k} = \frac{1}{Card(C_{k})} \sum_{x \in C_{k}} x

De plus, on a : \frac{\partial{}^{2}}{\partial{c_{k}^{2}}} (SSE_{k}(C)) = (-2)(-1) \sum_{x \in C_{k}} (1) = 2Card(C_{k}) \ge 0

Ainsi minimiser SSE(C) revient à choisir comme centroïde du cluster k, \frac{1}{Card(C_{k})} \sum_{x \in C_{k}} x.

Avec ces centroïdes, l’on est sur de faire un bon clustering.

III) INTERPRETATION

Cette solution signifie que pour minimiser l’erreur de chaque cluster, il faut positionner le centroïde au centre de gravité des points du cluster. En d’autres termes, le centroïde idéal est celui qui minimise les distances quadratiques entre lui-même et les éléments du cluster, garantissant ainsi que chaque cluster est le plus compact possible.

Cette minimisation de SSE nous fournit une méthode rigoureuse pour évaluer et améliorer la qualité de nos regroupements. En plaçant les centroïdes à ces positions optimales, nous assurons que le regroupement des éléments est le plus précis possible, ce qui est essentiel pour diverses applications pratiques, notamment dans l’analyse de données et la prise de décision.

CONCLUSION

En conclusion, la minimisation de la somme des erreurs quadratiques (SSE) est une étape cruciale pour assurer la qualité des clusters formés par l’algorithme k-means. En déterminant que le centroïde optimal est la moyenne des points d’un cluster, nous avons établi une méthode claire et efficace pour améliorer la précision des regroupements.

Cette approche permet de créer des clusters bien définis, augmentant ainsi la fiabilité des résultats obtenus. Les entreprises peuvent utiliser ces regroupements optimisés pour prendre des décisions stratégiques éclairées, basées sur une analyse de données rigoureuse et fiable.

Dans notre prochain article, nous verrons une application de la méthode k-means avec un exercice simple et amusant.

 

-
ParAnge-Kenuel Claude-Ivan Koutou