Introduction à la data-science
et à ses outils


Master, Paris Est MLV

@comeetie

Apprentissage Non Supervisé


Clustering et Reduction de dimension

Master, Paris Est-MLV

@comeetie

Clustering,


Trouver des groupes homogènes

Reduction de dimension,


Trouver un espace de projection des données pertinent

Apprentissage Non-supervisé

Clustering

Réduction de dimension

Clustering ?

Touver des groupes "homogènes"

$$\{\mathbf{x}_1,...,\mathbf{x}_N\}, \mathbf{x_i} \in \mathcal{R}^p$$

Clustering ?

Touver des groupes "homogènes"

Illustration de quelques exemples de clustering

K-means

Comment mesurer l'homogénité (1)

Distance moyenne au centre, variance : $$\sum_{i=1}^{N}||\mathbf{x}_i-\mu||^2$$ Groupe homogènes, faible variance autour des centres de chaque groupe $$\sum_{i=1}^N\sum_{k=1}^{K}z_{ik}||\mathbf{x}_i-\mu_k||^2$$ avec : $\forall i\in \{1,...N\},\, z_{ik}\in\{0,1\}^K,\,\sum_{k=1}^{K}z_{ik}=1$

K-means

Minimisation de la variance intra-groupe : $$z_1,...,z_N\,et\,\mathbf{\mu_1},...,\mathbf{\mu_K}=\arg\min\sum_{i=1}^N\sum_{k=1}^{K}z_{ik}||\mathbf{x}_i-\mu_k||^2$$ avec : $\forall i\in \{1,...N\},\, z_{ik}\in\{0,1\}^K,\,\sum_{k=1}^{K}z_{ik}=1$

Problème :

Optimisation non convexe, pas d'algorithme polynomial

K-means

Minimisation de la variance intra-groupe : $$\arg_{z_1,...,z_N}\min_{\mathbf{\mu_1},...,\mathbf{\mu_K}}\sum_{i=1}^N\sum_{k=1}^{K}z_{ik}||\mathbf{x}_i-\mu_k||^2$$

Solution :

Optimisation alternée :

K-means example

K-means

Minimisation de la variance intra-groupe : $$\arg_{z_1,...,z_N}\min_{\mathbf{\mu_1},...,\mathbf{\mu_K}}\sum_{i=1}^N\sum_{k=1}^{K}z_{ik}||\mathbf{x}_i-\mu_k||^2$$

Remarques :

K-means

avec scikit-lean

kmeans = KMeans(init='k-means++', n_clusters=n_digits, n_init=10)
kmeans.fit(digits.data)
kmeans.cluster_centers_
kmeans.labels_

Clustering

Clustering

Ascendant

Clustering

Ascendant

Hiérarchique

C

A

H

Comment mesurer l'homogénité (2)

La distance maximale entre deux menbres des groupes est faible : $$ max_{i \in C_1,j\in C_2}||x_i-x_j||^2$$

Lien maximal

Comment mesurer l'homogénité (2)

La distance minimale entre deux menbres des groupes est faible : $$ min_{i \in C_1,j\in C_2}||x_i-x_j||^2$$

Lien minimal

Comment mesurer l'homogénité (2)

La distance moyenne entre deux menbres des groupes est faible : $$ \frac{1}{N_{C_1}N_{C_2}}\sum_{i \in C_1}\sum_{j\in C_2}||x_i-x_j||^2$$

Lien moyen

Comment mesurer l'homogénité (2)

La distance(pondérés par les effectifs) entre leurs moyennes est faible : $$ \frac{N_{C_1}N_{C_2}}{N_{C_1}+N_{C_2}}||\mu_{C_1}-\mu_{C_2}||^2$$

Distance de ward

CAH

CAH example

"./agglo.html"

CAH

Minimisation gloutone du critère de fusion

Remarques :

CAH

avec scikit-lean

cah = AgglomerativeClustering(linkage="ward",n_clusters=10)
cah.fit_predict(digits.data)
cah.labels_

DB-Scan

Comment mesurer l'homogénité (3)

Densité ~ nombre de point par unité de surface

Comment mesurer l'homogénité (3)

Densité ~ nombre de point par unité de surface

Mesure de densité locale $\xi(\mathbf{x},\epsilon) = \sum_{i=1}^{N}1_{\{||\mathbf{x}-\mathbf{x}_i\||^2<\epsilon\}}$

Comment mesurer l'homogénité (3)

$i,j$ dans la même zone de forte densité = dans le même cluster si :

il existe un chemin de $i$ à $j$ le long duquel la densité est toujours élevée

DBSCAN

paramètres :$\epsilon, minpts$
nbcluster = 0

DBSCAN

étendre($\mathbf{x}_i$,nbcluster)

DBSCAN

Remarques

DB-scan

avec scikit-lean

db = DBSCAN(eps=25,min_samples=40)
db.fit_predict(digits.data)
db.labels_

Clustering, remarques générales :

!! lorsque les variables ont des unités ≠ !!

!! aux effets taille !!

Réduction de dimension

ACP

Réduction de dimension

Analyse en

Composantes

Principales

A

C

P

P

C

A

ACP

Pearson, K., On Lines and Planes of Closest Fit to Systems of Points in Space, Philosophical Magazine, vol. 2, no 6,‎ 1901, p. 559–572. (pdf)

ACP

Projection maximisant la variance

ACP

Projection minimisant l'erreur de reconstruction

ACP

Projection minimisant l'erreur de reconstruction

+ composantes orthogonales.

ACP

Projection maximisant la variance



$$\hat{\mathbf{w}}=\arg\min_{\mathbf{w}}\frac{1}{N}\frac{\mathbf{w}^{t}\mathbf{X}^{t}\mathbf{X}\mathbf{w}}{\mathbf{w}^{t}\mathbf{w}},\,avec\,||\mathbf{w}||=1$$

ACP

Projection maximisant la variance

Vecteur propre $(\mathbf{A}.\mathbf{v}=\lambda.\mathbf{v})$ dominant (de plus grande valeure propre) de la matrice de variance-covariance empirique (données centrées): $$\Sigma=\frac{1}{N}\mathbf{X}^{t}\mathbf{X}$$

ACP

Projection maximisant la variance

Vecteur propre $(\mathbf{A}.\mathbf{v}=\lambda.\mathbf{v})$ dominant (de plus grande valeure propre) de la matrice de variance-covariance empirique (données centrées): $$\Sigma\mathbf{w}=\lambda_k\mathbf{w}$$

ACP

Projection maximisant la variance sur K composantes

ACP

Projection maximisant la variance sur K composantes

$K$ vecteurs propres $(\mathbf{A}.\mathbf{v}=\lambda.\mathbf{v})$ dominants (de plus grande valeure propre) de la matrice de covariance empirique (données centrées): $$\Sigma\mathbf{w_k}=\lambda_k\mathbf{w}_k$$ La valeur propre associée à la composante principale $\lambda_k$ fournies le pourcentage de variance expliquée par la $k^{ième}$ composante principale.

ACP

Projection maximisant la variance sur K composantes

Pour projeter les données sur les composantes principales simple multiplication matricielle : $$\tilde{\mathbf{X}}_k=\mathbf{X}\mathbf{w_k}$$

Remarques :

ACP

avec scikit-lean

pca = decomposition.PCA(n_components=6)
pca.fit(X)
Xp = pca.transform(X)

Self

Organizing

Maps

S

O

M

SOM

Projection discrète non liénaire

SOM

SOM example

som.html

SOM

Visualisation, exploration

Scikit Learn

Clustering et ACP en python




Scikit Learn

(documentation clustering)

Exemple de notebook, analyse d'images de chiffre manuscrits (MNIST) :

TP Clustering

Tester différents algorithmes de clustering sur les profils de remplissage des stations Vélib et interpréter les résultats.

! à la mise en forme des données

Un notebook pour vous lancer :

Problème de librarie sur les postes :
ipython kernelspec install-self --user
https://ipython.org/ipython-doc/3/notebook/notebook.html#installing-new-kernels