blob: 9016706ecceac13167148fc1e30d5079ee07d956 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
-> trouver une structure de groupe dans un jeu de données
# Hypothèses
- Homogénéité inter clusters : similarité entre les données intra clusters
- Séparation inter-clusters (frontières claires)
- Forme des clusters (convexes, sphériques, ellipses...)
- Nombre de clusters
- Distribution de données
- Equidistance entre les points
- Linéarité des clusters
- Stabilité des clusters
- Représentation des données
Varient selon l'algo de clustering
# Algorithmes des kmeans
- n points
- Trouver K centroïdes de cluster $m_{k}, k=1,\dots,K$ qui minimise la distance par rapport aux centroïdes les plus proches
- Résultats fortement dépendants de l'initialisation
## kmeans++
- Initialisation paramêtrée
## Limites
- Incapable de capturer autre chose que des formes sphériques
- Nécessite que la moyenne ait un sens
## Nombre optimal de clusters
- Recherche des coudes
- Coefficient de silhouette
# Algorithme DBSCAN
## Points
- Points centraux
- Points frontière
- Points aberrants
## Concepts
- $\varepsilon$-voisinage : $V_{\varepsilon}(x) = \{ x' \in X | d(x,x') < \varepsilon\}$
- m densité : nb minimum de voisins pour qu'un voisinage soit considéré comme dense
## Algo
-> calculs des $\varepsilon$-voisinages pour les points
# Algorithme Affinity Propagation
- Pts de données -> noeuds de graphe
- A chaque itération, chaque noeud recoit des messages de tous les autres noeuds
- Les messages estiment l'aptitude des noeuds à servir d'examples pour les autres
- Les messages des tours précédents sont utilisés pour calculer un nouveau jeu de messages
## Algo
- Entrée : matrice de similarité S
- Matrice de responsabilité R et de disponibilité A construites de manière itérative
-
|
