Clustering

de données extrait du datawarehouse et ciblé sur un sujet unique présentées à l 'utilisateur averti pour examen par Optimisation type K-Means, ISODATA.

Part of the document

Clustering
Benjamin Monmege
benjamin.monmege@lsv.ens-cachan.fr
24 avril 2013
On considere une familleX= (xi)1iNd'observations avecxi2RD. L'objectif est de
regrouper ces donnees en un nombreKxe de classes. On cherche donc lesvariables de classes
Y= (yi)1iNavecyi2 f1;2;:::;Kgassociant a chaque exemple sa classe. Pour ce faire, on
xe unefonction de dissemblanced:RDRD![0;+1[ qui donne la distance separant deux
donneesxetx0. On cherche les variablesYde classes minimisant le critere
W(Y) =12
K
X
k=1X
i6=jjyi=k;yj=kd(xi;xj)
c'est-a-dire qu'on souhaite trouver
bY= argminYW(Y).
Exercice 1.Estimer le nombre total de partitions de l'ensemble d'observations, puis le nombre
de partitions aKclasses. En deduire qu'une enumeration complete de l'espace des solutions
n'est pas envisageable.
On xe dans la suite de ce TD la fonction de dissemblance egale a la distance euclidienne au
carre : pourx;x02RD,
d(x;x0) =kxx0k2=NX
i=1(xix0i)2
Exercice 2(K-means).Verier qu'on cherche donc les variablesYminimisant
W(Y) =12
K
X
k=1X
ijyi=kX
jjyj=kkxixjk2
1.
Mon trerque
W(Y) =KX
k=1N
kX
ijYi=kkxikk2
avecNkle nombre de donnees classees dans la classek, etkla moyenne de cesNkdonnees.
2.