WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

Application du processus de fouille de données d'usage du web sur les fichiers logs du site cubba

( Télécharger le fichier original )
par Nabila Merzoug et Hanane Bessa
Centre universitaire de Bordj Bou Arréridj Algérie - Ingénieur en informatique 2009
Dans la categorie: Informatique et Télécommunications
  

précédent sommaire suivant

Soutenons La Quadrature du Net !

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).

précédent sommaire suivant