3.4. Méthodes de partitionnement
Les méthodes de partitionnement ont pour but de fournir
une partition des éléments à classer. Le nombre de classes
dans la partition à générer doit être fixé au
départ. Le principe des méthodes de partitionnement est le
suivant : à partir d'un ensemble E de n individus, on cherche à
construire une partition P = (C1, ,CK) contenant K classes homogènes et
distinctes, tout en respectant un critère basé sur une distance
entre les individus. Doivent se trouver dans une même classe les
individus qui se ressemblent et en classes différentes les individus
divergents en termes du critère adopté.
Une partition optimale peut être obtenue à partir
de l'énumération exhaustive de toutes les partitions, ce qui
devient cependant prohibitif en termes de temps de calcul. Comme solution
alternative à ce problème, des méthodes de partitionnement
basées sur l'optimisation itérative du critère à
respecter permettent d'obtenir des groupes bien distincts en un temps de
calcul raisonnable. Ces méthodes d'optimisation utilisent
une réaffectation afin de redistribuer itérativement les
individus dans les K classes.
3.4.1. Clustering K-means
Proposé en 1967 par MacQueen, l'algorithme des centres
mobiles (K-means) est l'algorithme de clustering le plus connu et le plus
utilisé, tout en étant très efficace et simple. Ce
succès est dû au fait que cet algorithme présent un rapport
coût/efficacité avantageux.
On considère l'espace de (n) points de dimension (p)
suivant :
X=
On suppose que les (n) points peuvent être regroupés
en (c) classes (c < n).
x Ck = [???? 1, ???? 2,???? 3, ., ???? ??]
. x ?
f 1
Les classes sont décrites par leurs centres :
... .. .. ... ...
? ?
+ S on note par d (i, k) la distance entre le point xi et le
centre Ck, alors le point xi est x .. x . x
i1 if p
affecté au classe dont le centre est le plus proche.
... .. ... .. ... ?
?
L'algorithme fonctionne selon les étapes suivantes :
? n nf p ?
1' On choisit d'abord K points représentant les K classes
recherchés et appelés centroides des classes (le nombre K est
fixé par l'utilisateur).
1' On assigne chaque point non classé au classe dont le
centroide est le plus proche. 1' On réévalue les nouveaux
centroides des classes.
1' On recommence (réassignation des points au classe
dont le centroide est le plus proche, et recalculé des centroides)
jusqu'à ce que les centroides ne changent plus significativement.
[24]
Entrée : k le nombre de clusters désiré.
Sortie : Une partition C = {C1, ...,Ck} Initialiser ì1, ...ìk {k
donné}
Répéter
Affecter chaque point à son cluster le plus proche C (xi)
= ming d (xi, ìg)
Recalculer le centre ìi de chaque cluster
|
ìg =
|
1
????
|
????????
|
????
|
Jusqu?`a ce que (|?ì|<??)
FIG 3.1. L'algorithme k-means.
Le principal inconvénient de l'algorithme est que la
partition finale dépend du choix de la partition initiale. L'algorithme
est sensible à la sélection initiale des centroides, et
nécessite que l'utilisateur lui fournisse le nombre K de classes
(information souvent peu disponible).
| 
