Chapitre 1 : Classification non supervisée

Quelles sont les deux grandes catégories de méthodes en analyse de données ?

description et réduction de dimension

classification (non supervisée)

À quoi correspond n dans les données statistiques ?

n correspond au nombre d’individus (éléments, objets, etc.), on parle de population

Quelles sont les natures possibles des p variables observées ?

les variables peuvent être quantitatives (numériques) ou qualitatives : nominales (qualifiées par une couleur, une catégorie) et ordinales (avec un ordre)

Que signifie la classification non supervisée ?

dans la classification non supervisée, on ne connaît pas les classes

Qu’est-ce que la classification en analyse de données ?

la classification est l’action de regrouper des individus en classes, le résultat de cette action

À quoi est liée la notion de classe en classification ?

la notion de classe est liée à la relation de classe d’équivalence, définie à partir d’une relation binaire

Que signifie l’écriture x R y ?

x R y signifie que x et y sont en relation pour R

Quand une relation R est-elle une relation d’équivalence ?

une relation R est une relation d’équivalence si elle est réflexive, symétrique et transitive

Dans la classification supervisée, que ne connaît-on pas ?

Les classes

Qu’est-ce que la classification ?

Action de regrouper des individus en classes

Qu’est-ce qu’une classe ?

Le résultat de l’action de classification, lié à la notion de classe d’équivalence

Quand dit-on qu’une relation R est réflexive ?

Pour tout x, x R x

Quand dit-on qu’une relation R est symétrique ?

Pour tous x, y, si x R y alors y R x

Quand dit-on qu’une relation R est transitive ?

Pour tous x, y, z, si x R y et y R z alors x R z

Qu’est-ce qu’une relation d’équivalence ?

Une relation réflexive, symétrique et transitive

Que considère-t-on dans le problème général de la classification non supervisée ?

On considère n éléments dotés de p caractéristiques et des données qualitatives

Quel est le but de la classification non supervisée ?

Trouver une partition des éléments ou des individus qui soit la meilleure possible pour un critère donné

Que représente x_{ik} dans la matrice de données X ?

x_{ik} représente la propriété de l’individu i par rapport à la caractéristique k

Comment une caractéristique peut-elle être représentée dans la classification non supervisée ?

Chaque caractéristique peut être représentée par une relation binaire, et même une relation d’équivalence, définie par i R_k j ⇔ x_ik = x_jk

Quelle est l’interprétation de la classification en classification non supervisée ? ( Qu’est-ce qu’on cherche avec R ?)

On cherche une relation d’équivalence R que l’on ne connaît pas

Comment mesurer si une relation R est plus ou moins bonne ?

On peut compter le nombre de différences entre R et les relations dérivées R_k pour tout k

Comment s’écrit la mesure de différence entre une relation R et une relation R_k ?

|R Δ Rk| = card{(i,j) | (i R j et non i Rk j) ou (i R_k j et non i R j)}

Quel est le problème de la classification non supervisée à partir de relations binaires ?

Étant données p relations binaires R₁,…,Rp définies sur N = {1,…,m}, trouver une relation binaire d’équivalence R* qui minimise la quantité ∑{k=1}^p |R* Δ R_k|

Quelle est la remarque importante concernant les relations R_k dans le problème de classification non supervisée ?

Normalement, on s’attend à ce que les relations R_k soient des relations d’équivalence

Pourquoi la définition du problème reste-t-elle valable même si les relations R_k ne sont pas des relations d’équivalence ?

Parce que la définition fonctionne dans tous les cas, même si les relations R_k ne sont pas des relations d’équivalence

Comment s’appelle le modèle associé à la somme ∑{k=1}^p |R* Δ Rk| et quelle est la nature du problème ?

C’est le modèle d’agrégation statistique, et c’est un problème d’optimisation combinatoire

Que représente la formulation par programmation linéaire binaire dans le problème de classification ?

Elle consiste à reformuler le problème comme un problème de programmation linéaire binaire à partir des relations données

Comment sont définies les variables r^k{ij} et r{ij} dans la formulation par programmation linéaire binaire ?

r^k{ij} = 1 si i Rk j, 0 sinon (données), et r_{ij} = 1 si i R j, 0 sinon (variables)

Qu’est-ce que la fonction économique dans la formulation du problème de classification ?

C’est la fonction que l’on cherche à minimiser, en utilisant le fait que si x ∈ {0,1} alors x² = x, on obtient :

∑_k=1^p |R Δ R_k| = ∑_k=1^p ∑_(i,j)∈N² (r_ij^k − r_ij)² + C,

ce qui revient à minimiser

g = ∑_(i,j)∈N² c_ij r_ij, avec c_ij = ∑_k=1^p (1 − 2 r_ij^k).

Quelle est la fonction objectif à minimiser dans la formulation du problème ?

On cherche à minimiser g = ∑{(i,j)∈N²} c{ij} r{ij}, où c{ij} = ∑{k=1}^p (1 − 2 r{ij}^k)

Quelles sont les propriétés que doit vérifier la relation R ?

R doit être réflexive, symétrique et transitive

Que signifie la réflexivité de la relation R ?

rᵢᵢ = 1 pour tout i ∈ ℕ

Que signifie la symétrie de la relation R ?

rᵢⱼ = rⱼᵢ pour tout i, j ∈ ℕ avec i ≠ j

Quelle est la condition de transitivité pour la relation R ?

rᵢⱼ + rⱼₖ − rᵢₖ ≤ 1 pour tous i, j, k distincts dans ℕ

Que devient la contrainte de transitivité si on pose r̄ᵢⱼ = 1 − rᵢⱼ ?

r̄ᵢₖ ≤ r̄ᵢⱼ + r̄ⱼₖ (inégalité triangulaire)

Comment se formule le problème général de la classification non supervisée ? (formule et contrainte)

Min ∑_{{1 ≤ i < j ≤ m}} w_ij x_ij sous les contraintes

x_ij + x_jk − x_ik ≤ 1 pour tout (i,j,k) ∈ T et x_ij ∈ {0,1}

Quelles remarques peut-on faire sur les variables x_{ij} dans la formulation du problème ?

On a x{ij} = x{ji} et les termes constants ont été retirés de la fonction objectif car r_{ii} = 1

Comment représente-t-on le problème de classification d’un point de vue graphique ?

On représente le problème sous la forme d’un graphe complet G = (X, U) où chaque sommet représente un élément (individu)

Que signifie la minimisation de la somme des poids w_{ij} dans l’interprétation graphique ?

Cela revient à minimiser la somme des poids w_{ij} à l’intérieur des classes, c’est-à-dire l’intra-classe

À quoi revient la minimisation de la somme des poids intra-classe dans le problème de classification ?

Cela revient à maximiser l’inertie inter-classes, car la somme totale des poids est invariante

Qu’est-ce que l’inertie intra-classe et comment s’exprime-t-elle mathématiquement ?

Et si les données sont réparties en K classes, que cherche-t’on à maximiser ?

Comment cela s’exprime mathématiquement ?

Pourquoi la somme des poids est invariante ?

Somme des poids des paires d’éléments appartenant à une même classe, donnée par Σ_{1 ≤ i < j ≤ n} w_ij x_ij = Σ_{1 ≤ i < j ≤ n} Σ _{i € Ck} Σ_{j € Ck (i=/j)} w_ij

x_ij vaut 1 si les éléments i et j sont dans la même classe (sinon 0),

w_ij est le poids ou la similarité entre i et j ;

si les données sont partitionnées en K classes {C1, C2, …, CK}, on cherche à maximiser l’inertie inter-classes :

Max Σ_{1 ≤ i < j ≤ n} w_ij (1 − x_ij) ;

(1 − x_ij) signifie que i et j sont dans des classes différentes ;

la somme des poids est invariante car Σ w_ij x_ij + Σ w_ij (1 − x_ij) = Σ w_ij ;

Quelle est la reformulation du problème utilisant l’inertie inter-classes ?

Comme la somme totale des poids est constante, minimiser l’inertie intra-classe revient à maximiser l’inertie inter-classes, ce qui s’écrit : max Σ_{1 ≤ i < j ≤ n} w_ij (1 − x_ij)

En quoi consiste la méthode de partitionnement en sous-graphes denses ?

Elle consiste à partitionner un graphe en cliques ou en quasi-cliques en autorisant quelques arêtes en moins, le graphe pouvant être complet ou non

Quel est l’algorithme de la méthode des centroïdes (k-means) ?

On initialise k centroïdes M₁,…,M_k puis, à chaque itération, on affecte chaque point au centroïde le plus proche et on recalcule chaque centroïde comme la moyenne des points qui lui sont rattachés, jusqu’à stabilisation

À quoi sert la méthode des centroïdes (k-means) ?

Elle sert à partitionner un ensemble de points en k classes en regroupant les points autour de centroïdes afin de minimiser l’inertie intra-classe

Quel est le principe de la méthode de classification hiérarchique ascendante ?

Elle consiste à construire un arbre binaire où chaque niveau correspond à une partition des éléments, en partant de n classes (chaque élément seul) puis en diminuant progressivement le nombre de classes jusqu’à n’avoir qu’une seule classe, les classes d’un niveau étant incluses dans celles du niveau suivant, à l’aide d’une fonction de dissimilarité qui étend aux classes la dissimilarité entre éléments

Qu’est-ce qu’un dendrogramme ?

Un dendrogramme sur N = {1,…,n} est une application θ : [0,1] → S(N) telle que :

i) θ(0) est l’ensemble des singletons de N ;

ii) ∃ t₀ tel que ∀ t ≥ t₀, θ(t) = {N} ;

iii) ∀ t < t’, ∀ A ∈ θ(t), ∃ A’ ∈ θ(t’) tel que A ⊂ A’

Quelle est la stratégie d’agrégation par saut (ou saut minimum) ?

Saut (ou saut minimum) = single link (single linkage). On regroupe 2 éléments (leurs classes) présentant la plus petite dissimilarité (cf. algo de Kruskal) : d(C1, C2) = min d(i, j) avec i ∈ C1 et j ∈ C2

Quelle est la stratégie d’agrégation par saut maximum ?

Saut maximum = saut complet (full linkage). La plus grande dissimilarité entre deux éléments des deux classes : d(Ci, Cj) = max d(p, q) avec p ∈ Ci et q ∈ Cj. On regroupe les deux classes Ci et Cj qui minimisent d(Ci, Cj)

Quelle est la stratégie du lien moyen ?

Lien moyen = moyenne des dissimilarités entre les éléments des 2 classes. d(C1, C2) = 1 / (|C1||C2|) * ∑_i∈C1 ∑__j∈C2 d(i,j)

Qu’est-ce que la distance de Ward ?

Distance de Ward : minimiser l’inertie intra classe. d(C1, C2) = (|C1||C2| / (|C1| + |C2|)) · d(G1, G2) avec G1, G2 les centres de gravité des deux classes, visant à minimiser l’inertie intra-classe

Qu’est-ce qu’un indice de ressemblance (similarité) entre deux individus ?

Une application s : N×N → ℝ⁺ est une similarité si :

(i) s(i,j)=s(j,i) pour tout (i,j)∈N×N (symétrie),

(ii) s(i,i)=S>0 pour tout i∈N (ressemblance d’un individu avec lui-même),

(iii) s(i,j)≤S pour tout (i,j)∈N×N (la ressemblance est majorée par S)

Quelle est la valeur maximale possible d’un indice de similarité et comment note-t-on sa borne ?

S est une constante et la similarité vérifie s(i,j)∈[0,S]

Comment peut-on normaliser un indice de similarité pour qu’il soit compris entre 0 et 1 ?

On définit s*(i,j)= (1/S) s(i,j) et alors s*(i,j) ∈ [0,1]

Qu’est-ce qu’un indice de dissemblance (dissimilarité) ?

Une application d : N×N → ℝ⁺ est une dissimilarité si :

(i) d(i,j)=d(j,i) pour tout (i,j)∈N×N (symétrie)

(ii) d(i,i)=0 pour tout i∈N (semi-définie positive)

Quelle propriété relie un indice de similarité s et un indice de dissimilarité d ?

Soient s : N×N → ℝ⁺, d : N×N → ℝ⁺ et S ∈ ℝ⁺* avec d(i,j)=S−s(i,j). Les deux propriétés suivantes sont équivalentes :

(i) s est une similarité et S=s(i,i) pour tout i∈N

(ii) d est une dissimilarité et S ≥ sup d(i,j) pour (i,j)∈N×N

Qu’est-ce qu’une distance au sens mathématique ?

Une application d : N×N → ℝ⁺ est une distance si :

(i) d(i,j)=d(j,i) pour tout (i,j)∈N×N (symétrie)

(ii) d(i,j)=0 ⇔ i=j (définie)

(iii) d(i,j) ≤ d(i,k)+d(k,j) pour tout i,j,k∈N (inégalité triangulaire)

Qu’est-ce que la distance euclidienne ?

Dans un espace vectoriel muni d’un produit scalaire, la distance euclidienne entre i et j est définie par d(i,j)=⟨i−j,i−j⟩^{1/2} = ||i−j||

Qu’est-ce qu’une partition U de E ?

Soit E un ensemble, une partition U de E est divisée en K parties (les classes) et on a U={U1,…,Uk} avec Up ∈ P(E) ∀p telle que :

(i) Uk ≠ ∅ ∀k∈{1,…,K},

(ii) ⋃_{k=1}^{K} Uk = E,

(iii) Uk ∩ Ul = ∅ ∀k,l∈{1,…,K} avec k ≠ l

Que signifie la remarque 2 concernant K dans la partition ?

Rmq 2 : K sera parfois un paramètre dans certaines méthodes

Que signifie la remarque 3 sur les conditions de la partition ?

Rmq 3 : On peut parfois relâcher i) ou ii) ou iii)

Quelle est l’interprétation si on relâche la condition i) ?

Q1) interprétation si on relâche i) : on a au plus K classes (on écartera les parties vides)

Que se passe-t-il si on relâche la condition ii) ?

Q2) Si on relâche ii) certains individus peuvent alors être non classés (anomalie)

Que considère-t-on dans la suite pour comparer des partitions ? (au niveau d’une ou de plsuieurs partitions)

Dans la suite, on considère deux partitions U = {U1,…,Up} et Z = {Z1,…,Zq}

Quelles sont les notations utilisées pour les paires d’éléments lors de la comparaison de deux partitions ?

Notation :

paire = 2 éléments,

a = nombre de paires qui sont ensemble dans U et dans Z,

b = nombre de paires qui sont ensemble dans U mais pas dans Z,

c = nombre de paires qui sont dans Z mais pas dans U,

d = nombre de paires qui ne sont ensemble ni dans Z, ni dans U

Comment définit-on le nombre d’accords entre deux partitions ?

nombre d’accords entre les partitions est a + d

Quels sont les deux cas possibles lorsqu’on compare U et Z ?

Remarque U et Z : 2 cas

1) U et Z sont deux partitions quelconques qu'on souhaite comparer.

2) Une partition de référence est une partition obtenue par une heuristique.

Quel est le premier cas de comparaison entre deux partitions ?

1) U et Z sont 2 partitions quelconques qu’on souhaite comparer

Quel est le deuxième cas de comparaison entre deux partitions ?

2) une partition de référence et une partition obtenue par une heuristique

Comment définit-on les indices de Wallace ?

Def : W = a/(a+b) (proportion de paires de la 1ère partition qui sont aussi dans la seconde), V = a/(a+c) (proportion de paires de la 2nde partition qui sont aussi des paires de la 1ère)

Comment définit-on l’indice de Jaccard ?

Définition : Ij = a/(a+b+c), proportion de paires communes aux deux partitions et des paires qui sont au moins dans une partition

Comment s’exprime l’indice de Dice ?

I_D = 2a/(2a + b + c)

Comment définit-on l’indice de Rand ?

I_R = (a + d)/(a + b + c + d) = nombre d’accords entre les partitions sur le nombre total de paires

Quelle remarque peut-on faire sur la valeur de l’indice de Rand si U = Z ?

Si U = Z, I_R = 1

Dans quel intervalle varie l’indice de Rand ?

I_R ∈ [0,1]

Quelle remarque peut-on faire sur la cohérence de l’indice de Rand ?

Cet indice est en cohérence avec le modèle d’agrégation statistique