Fichier PDF

Partagez, hébergez et archivez facilement vos documents au format PDF

Partager un fichier Mes fichiers Boite à outils PDF Recherche Aide Contact



segmentation .pdf



Nom original: segmentation.pdf
Titre: Mer de glace
Auteur: ri ali

Ce document au format PDF 1.4 a été généré par Impress / OpenOffice.org 3.2, et a été envoyé sur fichier-pdf.fr le 16/05/2011 à 20:13, depuis l'adresse IP 41.200.x.x. La présente page de téléchargement du fichier a été vue 1283 fois.
Taille du document: 379 Ko (33 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Méthodes de clusterisation

PLAN


Notion de distance



Clusterisation


Méthodes par regroupement



Méthodes par partition

PLAN


Notion de distance



Clusterisation


Méthodes par regroupement



Méthodes par partition

BUT
Regrouper des objets similaires sans supervision, est
utilisé pour réduire le nombre de données pour le K-nn

Exemples


Chercher des galaxies (groupement d'étoiles)



Chercher des segments de clients



Chercher des groupes de produits similaires

Notion de distance
Exemple la distance Euclidienne
2
( x2,, y2 )
1
( x1, y1 )

D= √ (x1 - x2)2 + (y1 - y2)2

Distance généralisée
Pour n dimensions :

D = √ ∑i=1,n ( x1i – x2i ) 2

Les distances sont généralement normalisées (ie: ramenées
entre 0 et 1) pour pouvoir combiner plusieurs dimensions
différentes.

D = √ ∑i=1,n ( x1i – x2i / maxi) 2

Distance généralisée (2)

Avec un facteur d'échelle : D = √ ∑i=1,n ei2 ( x1i – x2i ) 2

Le facteur d'échelle ei qui est différent pour chaque
attribut, est utilisé pour pouvoir donner une
importance relative aux dimensions.

La notion de distance avec des
attributs nominaux


Attribut booléen:
si égal alors distance égal 0 ou 1 sinon



Attribut nominal:


si égal alors distance égal 0 ou 1 sinon



Matrice de distances

Exemple de matrice de distances
Pour les couleurs ROUGE, ORANGE et BLEU
par exemple

ROUGE

ROUGE

ORANGE

ORANGE

BLEU

0

0.1

0.3

0.1

0

0.2

Exemple de distance
La distance entre un client âgé de 20 ans et celle d’un client âgé
de 25 ans = 5. Cette distance normalisée (par rapport à l’age
max 100)= 0.05
Distance entre deux personnes fumeuses= 0 et entre un fumeur
et un non fumeur = 1
Distance entre deux personnes l’un âgé de 20 ans et fumeur et
une personne âgée de 70 ans et non fumeur:
= √ 0.52 +12 =

√ 1.25

PLAN


Notion de distance



Clusterisation


Méthodes par regroupement



Méthodes par partition

Definition
Soit un ensemble E d'instances non étiquetées.
La clusterisation consiste à partitionner E en un
ensemble de R clusters Ei (i = 1, R) mutuellement
exclusifs et exhaustifs.
ie:
Ei ∩ Ej = Ø

pour tout i,j

UE =E

pour i=1,R

i

i =1,R

Centre de gravité
Le centre de gravity est defini comme :
NbI

NbI

G = ( ∑ xi1 / NbI ,…….. ,∑ xinvars / NbI  )
i=1

i=1

where: NbI is the number of individuals and nvars is the
number of variables characterising an individual .

Example de Methode Clustering

age

age
10

10

9

9

8

8

7

7

6

6

5

5

4

4

3

3

2

2

1

1

0
0

1

2

3

4

5

6

7

8

9

10

0
0

taille

1

2

3

4

5

6

7

8

9

10

taille

PLAN


Notion de distance



Classification à base de distance



Clusterisation


Méthodes par regroupement



Méthodes par partition

Principe de méthode hiérarchique
Mettre dans une liste toutes les instances
TANT QUE liste non vide
Calculer les distances entre tous les éléments de la liste
Selectionner les deux éléments avec la + petite distance
Si les deux éléments sont 2 instances ALORS


créer un cluster



Supprimer les 2 instances de la liste

Si les deux élements sont 1 intance et 1 cluster ALORS


Inserer l'instance dans le cluster



Supprimer l'instance de la liste

Si les deux éléments sont 2 clusters ALORS



Fusionner les deux clusters en un nouveau cluster

Supprimer le cluster restant

FAIT

Exemple villes d'italie (1)

Exemple villes d'italie (2)

Exemple villes d'italie (3)

Exemple villes d'italie (4)

Exemple villes d'italie (5)

Résultat: hiérarchie

Objectif de clusterisation
Centre de gravité
D
D
Centre de gravité classes
d

Objectif MAX 1/N ∑ Dkl
D distance inter centres de gravité

Instance

PLAN


Notion de distance



Clusterisation


Méthodes par regroupement



Méthodes par partition

Objectif de clusterisation

D
Centre de gravité
d

Objectif MAX ∑ Dkl Min ∑ dij
D distance inter centres de gravité
d distance intra instances – centres de gravités

Instance

Exemple ( 1 )

Exemple ( 2 )

Exemple (3)

Principe
Entrée : un échantillon de m objets x1, …, xm

1. Choisir k centres initiaux aléatoirement c1, …, ck
2. Répartir chacun des m objets dans le groupe i dont le centre ciest le plus
proche.
3. Si aucun élément ne change de groupe alors arrêt et sortir les groupes.
4. Calculer les nouveaux centres : pour tout i, ciest la moyenne des
éléments du groupe i.
Aller en 2.

Exemple villes d'italie (1)

Exemple villes d'italie (2)

Comparaison des methodes

Méthodes de
regroupement

Méthodes de
partition

Temps de calcul

Lente O( N2 )

Rapide O( kN )

Nombre de clusters

Déterminé
automatiquement

Déterminé par
l'utilisateur

Algorithme mixte


On choisit k tres grand



On effectue une k mean



Puis on effectue un regroupement


Documents similaires


Fichier PDF segmentation
Fichier PDF fastlain cluster
Fichier PDF centre 20de 20gravit c3 a9
Fichier PDF exercices cercle et lieux de points maths premiere 1148
Fichier PDF cours mco
Fichier PDF physique


Sur le même sujet..