Solution N°3 Systéme de recommandation hybride à base de Clustering k-means
Solution N°3 Systéme de recommandation hybride à base de Clustering k-means
Embedded Files
Définition Clustering K-means algorithme
Définition Clustering K-means algorithme
K-moyennes
Le partitionnement en k-moyennes (ou k-means en anglais) est une méthode de partitionnement de données et un problème d'optimisation combinatoire. Étant donnés des points et un entier k, le problème est de diviser les points en k groupes, souvent appelés clusters, de façon à minimiser une certaine fonction. On considère la distance d'un point à la moyenne des points de son cluster ; la fonction à minimiser est la somme des carrés de ces distances.
Il existe une heuristique classique pour ce problème, souvent appelée méthodes des k-moyennes, utilisée pour la plupart des applications. Le problème est aussi étudié comme un problème d'optimisation classique, avec par exemple des algorithmes d'approximation.
Les k-moyennes sont notamment utilisées en apprentissage non supervisé où l'on divise des observations en k partitions. Les nuées dynamiques sont une généralisation de ce principe, pour laquelle chaque partition est représentée par un noyau pouvant être plus complexe qu'une moyenne. Un algorithme classique de k-means est le même que l'algorithme de quantification de Lloyd-Max.
Principe
Principe
Le clustering consiste à classer n éléments en k ensembles en fonction de leurs proximités.
Par exemple, supposons un ensemble de 10000 utilisateurs ayant différentes 5 compétences java, Php python, dotNet, SQL. L’idée est d’identifier des groupes d’utilisateurs ayant sensiblement les mêmes résultats afin de procurer des aides adaptées aux groupes.
Pour cela, algorithme des K-Moyennes (K-Means) est particulièrement efficace ; et simple dans son fonctionnement :
Les données sont d’abord normalisées (chaque compétence est ramenée à une valeur entre 0 et 100.
Des centroïdes (barycentres) sont choisis parmi les données et représentent les centres des clusters.
Chaque donnée est placée dans le cluster dont le centroïde est le plus proche
Une boucle est ensuite effectuée tant que des changements ont lieu :
Dans chaque cluster, les coordonnées du centroïde sont recalculées pour représenter les coordonnées moyennes des données contenues
Chaque donnée est déplacée si nécessaire dans un meilleur cluster
On obtient ainsi une classification de données basée sur le calcul des distances entre données.
En Java, on définira : une classe Data pour représenter les données, une classe Cluster qui contient des données et un centroïde, et une classe AppliKMeans qui contient l’algorithme.
Page updated
Google Sites
Report abuse