Upload
edmond-fouquet
View
116
Download
4
Embed Size (px)
Citation preview
Plan
Définition et Objectifs Méthodes de Partitionnement Méthodes Hiérarchiques Méthodes par Densité Autres méthodes Applications Exemple
Définition et Objectifs
Regrouper des objetsen groupes homogènes ou proches
En marketing, la segmentation du public consiste à« le découper en un certain nombre de sous-ensembles, aussi homogènes que possibles, afin de permettre à une entreprise de mieux adapter sa politique de marketing à chacun de ces sous-ensembles » [Mercator]
En statistiques, on parle plutôt de « classification » En anglais (marketing ou statistiques) on parle de
« clustering »
Approche intuitive
Objectif Identifier des
« attroupements » de points.
Intérêt Représentation plus
compacte Inteprétation des
groupes
Caractéristique 1
Caractéristique 2
Caractéristique 1
Caractéristique 2
Conditions
Les objets sont supposés décrits par un tableau En ligne, un individu, ou objet En colonne, une caractéristique, ou variable
Les données individuelles peuvent être Continues (le cas général) Binaires ou discrètes Textuelles
Les données doivent être connues pour chaque individu
Pour pouvoir poser le problème
Disposer de n caractéristiques décrivant chaque objet : Nombre de caractéristiques fixes
Pas de séries temporelles Pas de listes
Toutes les données doivent être connues
Les outils mathématiques de base
Groupes Homogènes Groupes = Partitions
Une partition est la décomposition d’un ensemble en sous-ensembles deux à deux disjoints, et de réunion égale à l’ensemble de départ
Homogènes = Distances et dissimilarités Entre individus Entre ensembles
Approche combinatoire
Critère de qualité d’une partition Ex : inertie intraclasse
Recherche de la meilleure partition Recherche exhaustive ?
Nombre de partitions d’un ensemble …
Partitions d’un ensemble
Nombre de partitions d’un ensemblePn,k = Pn-1,k-1+k.Pn-1,k
Méthodes de partitionnement
Méthodes des nuées dynamiques
Soient n points partitionnés en k groupes On définit pour chaque groupe :
g1, g2, …, gK le centre de gravité I1, I2, …, Ik l’inertie
L’inertie totale des n points est égale à :I=IB+IW
(théorème de König_Huyghens)
Inertie intraclasse et interclasses
IB=(n1/n).d(G1,G)2+(n2/n).d(G2,G)2
IW=(n1/n).I1+(n2/n).I2
Méthode des nuées dynamiques
Rechercher la partition qui minimise l’inertie intraclasse (IB)
(groupes bien homogènes) … donc maximise l’inertie interclasses (IW)
(groupes bien éloignés) Ce critère ne s’applique qu’à un nombre
de classes fixé.Sinon :k=n réalise IB=0
Méthode des nuées dynamiques
Caractéristique 1
Caractéristique 2 1. On part de k centres2. Ces centres
déterminent une partition
3. On remplace les centres par les centres de gravité de chaque sous ensemble
4. On recommence en 2
L’algorithme converge
Méthode des nuées dynamiques
12
Convergence
Notons ECi la classe
constituée par les points de E plus proches de Ci que d’un autre centre
Notons Egi la classe
obtenue en remplaçant Ci par gi le centre de gravité de ECi
Variance intraclasse avant =
>=
>= Variance intraclasse après
k
i Emi
ic
gmdn 1
2,
1
k
i Epi
ig
gpdn 1
2,
1
Faiblesses
Sensibilité aux points initiaux La convergence n’est garantie que vers un
minimum local Variables qualitatives ? Difficultés
S’il y a des points extrêmes Si les groupes ont des tailles ou des densités
différentes Si les groupes ne sont pas de forme convexe
Amélioration des k-means
“k-medoids” (PAM) K fixé Choisir k points aléatoirement appelés “medoids”,
notés H Associer chaque point J au medoid le plus proche Calculer l’inertie intraclasse Pour chaque couple (H,J) évaluer le gain en inertie
si on échange H et J Echanger si l’inertie diminue
Plus robuste, mais moins efficace pour des grandes bases de données.
Méthodes hiérarchiques
La classification hiérarchique
Principe Utiliser un regroupement successif de
parties Regroupement ascendant
Problème Disposer d’une distance entre parties
CAH : Principe
a
b
c d
e
f
En appliquant un algorithme de classification ascendante hiérarchique aux points ci-contre, on aboutit à l’arbre ci-dessous. (la distance entre parties utilisée ici est la plus petite distance entre deux éléments des parties)
a b c d e f
En coupant l’arbre au niveau horizontal figuré par la ligne en pointillés, on choisit la partition ci-contre.
a
b
c d
e
f
Définitions
Hiérarchies de parties d’un ensemble E Une famille H est une hiérarchie ssi
E et tous les singletons {a} appartiennent à H Si A et B appartiennent à H, alors elles sont soient
disjointes, soit incluses l’une dans l’autre Toute classe est la réunion des classes qui sont
incluses en elle A toute hiérarchie correspond un arbre de
classification
Exemple
a b c d e f
H={, a,b, c, d, e, f, ab, de, abc, abcde, abcdef}
Distances entre parties
Dissimilarités Saut minimum : plus petite distance entre
éléments des deux parties
Distance moyenne
AB
Indice de la hiérarchie
a b c d e f
0.3
0.5
0.7
1
Les niveaux d’agrégation sont égaux à la distance des parties réuniesI({a,b,c}) = 0.5 = d({a,b},{c})
Coupure de la hiérarchie
Une partition de E compatible avec la hiérarchie H est une partition dont les classes sont des éléments de H
C’est une partition obtenue en « coupant l’arbre et en regroupant les morceaux »
a b c d e f
P={{a,b,c},{d,e},{f}}
Méthodes par densité
Principe
La segmentation est basée sur la densité
Fonctionne bien si la densité de points est beaucoup plus élevée à l’intérieur d’un segment qu’à l’extérieur.
Définitions (1)
Deux paramètres Eps: Rayon maximum d’un voisinage
MinPts: Nombre minimum de points dans le “Eps-voisinage” d’un point
Point dense : point entouré d’au moins MinPts points dans un rayon de Eps
pq
MinPts = 5
Eps = 1 cm
Définitions (2)
NEps(p): {q | dist(p,q) <= Eps}
Point directement accessible par densité: Un point p est directement accessible par densité à partir d’un point q si :
1) q est un point dense
2) p NEps(q)
Définitions (3)
Point accessible par densité: Un point p est accessible par densité à partir d’un
point q s’il existe une chaîne de points p1, …, pn, p1 = q, pn = p telle que pi+1 est directement accessible par densité à partir de pi
Point connecté par densité Un point p est connecté par densité à un point q
s’il existe un point o tel que p et q soit accessible par densité à partir de o.
Illustration des définitions
p
qp1
p q
o
p est accessible par densitéà partir de q
p et q sontconnectés par densité
DBSCAN
Repose sur une notion de segment basée sur la densité : un segment est défini comme un ensemble maximal de points connectés par densité
Cet algorithme permet de découvrir des segments de forme quelconque
Point noyau
Point bordure
Point isolé
Algorithme DBSCAN
EntréesD={t1,t2, …, tn} // Ensemble de pointsMinPts // Nombre minimal de points d’un segmentEps // Distance maximale pour connexion
RésultatK={K1, K2, …Kp} // Ensemble de segments
Algorithmep=0Pour i=1 à n, faire
Si ti n’est pas dans un segment alorsX={tj|tj est accessible par densité à partir de ti};Si X est un segment valide, alors
P=p+1;Kp=X;
FinSiFinSi
FinPour
Comparaison k-means et DBSCAN
Résultat de K-means Résultat de DBSCAN
Apport de l’ACP
Visualisation des groupes homogènes
Les segments trouvés sont difficiles à analyser Option 1
Projection des individus sur le plan des deux axes principaux d’inertie
Segmentation du nuage en 2 dimensions Option 2
Segmentation du nuage en n dimensions Projection des segments sur le plan des deux axes principaux d’inertie
Exemple
Autres méthodes
Self-organising MAPs (SOM)
Ou “Cartes topologiques autoadaptatives”
Idée de Teuvo Kohonen Basée sur une modélisation de certains systèmes
neuronaux Visualisation en 2D de données en dimension
élevée Conservation de la topologie (proximité) Extension à la classification
SOM - Principe de fonctionnement (1)
SOM - Principe de fonctionnement (2)
0.3
Carte topologique
Neuroneindividuel
0.6
0.8
0.9
SOM - Algorithme
Initialiser le réseau
Trouver le neurone gagnant
Le rapprocher de l’exemple
Rapprocher les voisins proches
Eloigner les voisins éloignés
Présenter un exemple
Principe du renforcement
Carte topologique
Neuroneindividuel
0.3
0.6
0.8
0.9
Exemple
Points en 3 dimensions Chaque point est une
couleur codée en R,G,B
Dans la carte initiale , chaque neurone répond aléatoirement
On colorie chaque neurone en fonction de la couleur à laquelle il répond.
Etude de cas
Un cas pratique Analyse des sessions de navigation sur un
site professionnel Des outils de l’analyse des données
Préparation des données Analyse en composantes principales Segmentation
Description du cas
Etude réalisée pour le groupe Lafarge
Identification des usages d’un site internet professionnel : le configurateur de toit.
Le configurateur de toiture
Les données
Les données brutes sont des données de « log » : Données de « trace » de la navigation Chaque ligne matérialise une action
individuelle de l’internaute
23,@@@@0026564285.1031774594@@@@,16489,creargos-1.6,geo,ssid=default&null&nomProjet=&codePost=&ville=&adresse=&nomRoofer=Larroque&fonction=&[email protected]&tel=&roofSurface=0,Sep 11 2002 22:04:07…
Prétraitement des données
Ces données brutes ne peuvent pas être analysées
Pourquoi ? L’objectif est de comprendre les usages Usage = ensemble des lignes d’un même
utilisateur (session) Représentation de l’usage sous forme d’un
ensemble de chiffres Les usages doivent être comparables entre eux
Créer un « Vecteur d’usage » par session
Représentation des données
Exemple de caractéristiques des usages Durée d’une session Heure de la session Code Postal Profession Sauvegarde du résultat Nombre d’erreurs Etc.
Représentation des données
Pour être analysées les données sont représentées sous forme d’un tableau Une ligne par session (utilisateur) Une colonne par caractéristique
Représentation des données
Travaux dirigés
Fichier de données “semi-brutes” Analyse statistique des données Segmentation des données Analyse et interprétation des segments Outils
Excel, XLMiner, Spad