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” 1). Des approches peuvent être empruntées:
Dans la première famille, on procède au calcul des regroupements par
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),
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?
Exemple de distance :
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”:
i_2 = vrai | i_2 = faux | \Sigma | |
---|---|---|---|
i_1 = vrai | n_1 | n_2 | n_1 + n_2 |
i_1 = faux | n_3 | n_4 | n_3 + n_4 |
\Sigma | n_1+ n_3 | n_2 + n_4 | p |
Alongée | Texturée | Grande | Isolée | Fréquente | |
---|---|---|---|---|---|
Ville | Non | Oui | Oui | Oui | Non |
Quartier | Non | Oui | Non | Non | Oui |
Lac | Non | Non | Oui | Oui | Non |
Champs | Oui | Non | Non | Non | Oui |
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.
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.
Ca converge (et très vite, généralement), car
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.
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