Ici, le but est de trouver une description compacte permettant de résumer et décrire des objets à partir des données initiales (copieuses). Ceci s'inscrit dans la fouille exploratoire et descriptive et “summarization” ¹⁾. Des approches peuvent être empruntées:

• statistique : “découverte” de regroupements, classes, ou “clusters” à l'aide de l'évaluation des distances ²⁾
• logique : formation de concepts

Dans la première famille, on procède au calcul des regroupements par

• partitionnement
• modélisation
• classification hiérarchique
• et bien d'autres façons

• “hard clustering” : chaque objet appartient à une classe, et seulement une
• “soft clustering” : chaque objet appartient à au moins une classe, mais peut appartenir à plus d'une classe, et les classes peuvent être
  • hiérarchique
  • ou simplement se chevaucher.
• “fuzzy clustering” : les objets appartiennent à des degrés différents à toutes les classes.

Posons D = l'ensemble des individus, avec |D|=N, K = nombre de regroupements. Si l'on représente la classification par une matrice C_{i,k}, i\in \left\{1,\ldots,N\right\}, avec une ligne par (objet ou) individu et une colonne par catégorie (ou classe),

• “hard clustering” : tous les coéfficients sont 0 ou 1, et il y a un et un seul 1 par ligne: \forall i\in\left\{ 1,\ldots ,N\right\}, \forall k\in\left\{1,\ldots,K\right\}, C_{i,k}\in \left\{0,1\right\}\; \& \;\sum_{k=1}^{K} C_{i,k} = 1
• “soft clustering” : tous les coefficients sont 0 ou 1, et il y au moins un 1 par ligne : \forall i\in\left\{ 1,\ldots ,N\right\}, \forall k\in\left\{1,\ldots,K\right\}, C_{i,k}\in \left\{0,1\right\}\; \& \; \sum_{k=1}^{K} C_{i,k} \geq 1
• “fuzzy clustering” : tous les coéfficients sont entre 0 et 1, et la somme des coefficients sur chaque ligne est égale à 1 : \forall i\in\left\{ 1,\ldots ,N\right\}, \forall k\in\left\{1,\ldots,K\right\}, C_{i,k}\in \left[0,1\right]\; \& \; \sum_{k=1}^{K} C_{i,k} = 1

Le but étant de trouver des regroupements intéressants, basés sur des faits clivants, on souhaite que les individus dans chaque catégorie se “ressemblent” et que les individus d'une catégorie ne ressemblent pas (beaucoup) aux individus appartenant à d'autres catégories. Le problème est comment mesurer cette ressemblance?

• on appelle dissimilarité toute application d : M^2 \mapsto R^+\quad | \quad \forall\left(x,y\right)\in M^2\quad d\left(x,y\right)=0\;\Leftrightarrow \; x=y
• on appelle distance toute fonction de dissimilarité symétrique qui vérifiant en plus l'inégalité triangulaire : \forall\left(x,y,z\right)\in M^3, d\left(x,z\right)\leq d\left(x,y\right)+d\left(y,z\right)

Exemple de distance :

• x,y\in\mathbb{R}^p \;:\; d_q\left(x,y\right) = \sqrt[q]{\sum_{i=1}^{p}|x_i - y_i|^q}

Considérons une distance entre deux vecteurs binaires (“vrai” ou “faux”) de dimension p; on va simplement compter le nombre de fois ils sont en désaccord, ou le nombre de fois qu'ils sont en désaccord et l'un dit “vrai”:

• variables symétriques : \displaystyle d\left(i_1, i_2\right) = \frac{n_2 + n_3}{p}
• variables asymétriques : \displaystyle d\left(i_1, i_2\right) = \frac{n_2 + n_3}{p - n_4}

Si l'on applique la mesure a ville et quartier, on constate qu'ils diffèrent trois cas sur cinq, donc dissimilarité symétrique = 0,6 et similarité (symétrique) = 0,4. Si l'on exclue le cas où ils ont tous deux “non”, la dissimilarité devient 3/4= 0,75. On procède de la même façon pour les autres comparaisons, paire par paire.

Considérons maintenant des comparaisons point par point plus complexes, où les valeurs ne sont plus toujours vrai-faux.

• données nominales (catégorielles) telles couleur, voir ordinales (petit, moyen, grand)
• données complexes (histogrammes, et quoi encore?)

Qu'en dit-on?

Rappel :

Le but étant de trouver des regroupements intéressants, basés sur des faits clivants, on souhaite que les individus dans chaque catégorie se “ressemblent” et que les individus d'une catégorie ne ressemblent pas (beaucoup) aux individus appartenant à d'autres catégories.

Ainsi, si I1 et I2 appartiennent à une catégorie et I3 à une autre, nous voudrions que d(I1,I2) soit plus faible que d(I1,I3) et d(I2,I3). Ceci ne sera pas toujours possible, puisque un regroupement peut être très vaste par rapport à la distance séparant ce regroupement de son plus proche voisin. Un individu très excentré, pour peu qu'on ne le laisse pas constitué un “regroupement” à lui seul, peut avoir une grande influence sur la densité du regroupement auquel on l'affecte, alors que le laisser constituer un regroupement pourrait augmenter la séparation des regroupements.

Une possibilité est de chercher à minimiser l'inertie interne des classes (maximiser la densité des classes?). Une autre est de chercher à maximiser l'inertie inter-classes.

• \displaystyle I_{intra} \left(C_k\right) = \sum_{x_i\in C_k} d\left(x_i, g_k \right) ³⁾, où g_k est le centroïde de C_k.
• \displaystyle I_{intra}\left(D\right) = \sum_{k=1}^{K} I_{intra}\left(C_k\right)
• \displaystyle I_{inter}\left(D\right) = \sum_{k=1}^{K} P_k \times d\left(g, g_k \right), où g_k est le centroïde de C_k et g est le centroïde de D.
• I_{totale} = I_{intra} + I_{inter}; donc maximiser l'un minimise l'autre, on n'a même pas à choisir entre les deux critères!

• on se donne–on verra comment par la suite– un ensemble de noyaux g_k initiaux.
• on effectue un premier partitionnement en affectant chaque individu au noyau le plus proche.
• on calcule les centres (qui minimise les I_{intra}) pour chaque partie
• on ajuste les affections de individus qui se trouvent plus proche du nouveau centre d'une autre partie que la leur
• on recalcule les centres, et refait des affectations correctives tant qu'il y a des changements d'affectation.

Ca converge (et très vite, généralement), car

• tous les changements d'affectation et de points centraux réduisent I{intra}
• il y a un nombre fini (mais grand) de partitionnements possibles

Cependant, il fournit un optimum local qui n'est pas forcément un optimum global; tout dépend du choix des noyaux initiaux. Il convient donc d'étudier comment faire ça pour le mieux. Malheureusement, il n'y a pas de solution parfaite, seulement des suggestions.

• “sélection” sur la base d'informations d'un oracle, ou d'une pré-étude (d'histogrammes, e.g.)
• “répétition” de l'algorithme avec des initialisations différents (aléatoires)
• répétition avec “découverte de formes fortes” par intersection de deux (ou plus) résultats successives, c'est à dire des régions qui sont systématiquement unies dans une partie quelque soit le partitionnement. On prend les centres de ces “formes fortes” comme noyaux initiaux.

La qualité du résultat dépend également du choix de K, le nombre de regroupements. S'il y a, par exemple, trois amas et on n'en cherche que deux ou on en cherche quatre ou plus, le résultat ne sera pas très bon. Ici aussi, on peut faire une “sélection” sur la base d'informations d'un oracle, ou d'une pré-étude (d'histogrammes, e.g.). Sinon, d'autres possibilités sont

• estimation en fonction d'une indice statistique, basée sur la variance, c'est à dire la distance moyenne des individus de leur centre : \displaystyle T = \sum_{k=1}^{K} \sum_{x_i \in C_k} |x_i - gk |^2. Une bonne valeur serait K tel que \displaystyle \frac{1}{T}\times \frac{M-K}{K-1} est maximisé. Mais qu'est-ce, M?

• Répéter jusqu'à “stabilisation”:
  • effectuer un regroupement par k-means
  • éliminer les clusters trop petits
  • scinder les clusters trop vastes
  • fusionner les groupes trop proches