Qu’est-ce que le clustering ?

Processus qui partitionne un ensemble de

Clustering z
données en sous-classes (clusters) ayant du sens

z Classification non-supervisée : classes non pré-

définies
¾ Les regroupements d'objets (clusters) forment les
classes

z Optimiser le regroupement
¾ Maximisation de la similarité intra-classe
¾ Minimisation de la similarité inter-classes
Maria Rifqi
z Principales applications
¾ Observer la distribution des données en identifiant
les groupes et leurs caractéristiques (découvrir des
corrélations)
¾ Préparation des données pour un autre algorithme
ou application

Applications du Clustering
z Reconnaissance de formes

Cj
z Analyse des données spatiales:

Ci z Traitement d’images
ωl

ωm z Market Research

ωk
z Recherche d’information
¾ Catégorisation de documents ou de termes
Les individus d’d’ une même Les individus de deux classes ¾ Visualisation de l’information et interfaces de recherche d’information
classe sont le « plus ressemblants » difféé rentes sont « le plus disse mblables »
diff
possible possible
z Web Mining
¾ Clustering des usages du web pour découvrir des groupes d’accès similaires
¾ Personalisation du Web

Méthodologies de Clustering Structures des données

z Deux méthodologies générales z Représentation de vecteurs dans un espace à N

¾ Algorithmes de partitionnment dimensions et une distance
D1: 57,M,195,0,125,95,39,25,0,1,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0
¾ Algorithmes hiérarchiques
D2: 78,M,160,1,130,100,37,40,1,0,0,0,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0
...
z Partitionnment Dn: 18,M,165,0,110,80,41,30,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

¾ Diviser un ensemble de N items en K clusters Distance (D1,D2) = ???

z Distances 2 à 2 entre les points
-- 1 2 3 4 5 6 7 8 9 10
z Hiérarchique z Matrice de similarités/dissimilarités 1 - ddddddddd
¾ Par agglomérations : les paires d’items ou de clusters sont z Distance : 0 = proche, ∞ = loin, 2
3
- dddddddd
- ddddddd
successivement liés pour produire des clusters plus grands (bottom-up) z Similarité : 0 = loin, ∞ = proche 4 - dddddd
5 - ddddd
6 - dddd
¾ Par divisions : commencer par l’ensemble entier comme cluster et 7 - ddd
successivement diviser en de plus petites partitions (top-down) 8 - dd
9 - d

1
Qualité d’une méthode de clustering Le clustering est un problème mal posé

z Une des questions difficiles du clustering : à quel point les clusters

trouvés sont bons ?
z Bonnes propriétés de croissance (scalability)
z Capacité à traiter différents types d’attributs
z Découverte de clusters de formes arbitraires
z Connaissances minimales du domaines requises pour définir les
paramètres
z Capacité à traiter les données bruitées et les exceptions
z Insensibilité à l’ordre des objets du jeu de données
z Capacité à traiter de très nombreux attributs
z Extraction de clusters en intégrant des contraintes spécifiées par Combien de clusters ?
l’utilisateur
z Résultat interprétable et utilisable

Combien de clusters ? Combien de clusters ?

Combien de clusters ? Types de données pour l’analyse de clusters

z Cinq types différents de variables nécessitent des traitements

différents
z Numériques linéaires
¾ Ex : poids, taille, longitude, latitude, etc.
z Binaires : une valeur parmi deux possibles
¾ 0 : la variable est absente, 1 : la variable est présente
z Nominale : valeur prise dans une liste finie
¾ Ex : couleur : « vert, bleu, rouge, jaune, noir »
z Ordinales : l’ordre des valeurs est plus important
¾ Ex : résultat d’un concours
z Ratios : variables numériques sur une échelle exponentielle

2
Mesure de similarité entre objets Variables numériques continues

z Similarité entre objets calculée selon leur caractéristiques (attributs z Souvent, les distances sont utilisées
possédés, valeurs des attributs, taille des objets, etc.) z Propriétés des distances :
¾ Souvent exprimée en termes de fonctions de distance : d(o1,o2) ¾ Symétrie : Pour tout A et tout B, D(A, B) ≥ 0, and D(A, B) = D(B, A)
¾ Pour tout A, D(A, A) = 0
¾ Fonction de distance différente pour les variables numériques continues,
booléennes, catégoriques, ordinales et de ratios ¾ Inégalité triangulaire : D(A, C) ≤ D(A, B) + D(B, C)

¾ Des poids peuvent être associés à chaque variable selon la sémantique

de l’application et des données z Distances classiques :
¾ Distance Euclidienne :

z Objets « suffisamment similaires » sont regroupés en clusters D(X,Y) = [(x1 –y1)2 + (x2 –y2)2 + ... + (xN –yN)2]1/2
¾ Définition de « suffisamment similaire » difficile, subjective
¾ Distance de Minkowski (généralisation de la distance euclidienne) :

z Mesure de qualité de chaque cluster D(X,Y) = [(x1 –y1)q + (x2 –y2)q + ... + (xN –yN)q]1/q , q entier positif non nul
¾ Selon la distance entre les objets appartenant au cluster et la distance
entre les clusters ¾ Distance de Manhattan (q=1) :

D(X,Y) = | x1 –y1| + | x2 –y2|+ ... + xN –y N|

Variables numériques : Normalisation Variables numériques : Normalisation

z Valeurs entre 0 et 1
x 'i =
xi − min xi z Standardiser les données
max xi − min xi
z Exemple ¾ Égaliser le poids des variables pour assurer
¾ max distance de l’âge: 100000-19000 = 79000
l’indépendance par rapport aux unités de mesures
¾ max distance de l’âge : 52-27 = 25 ¾ Calculer la déviation absolue moyenne :
ID Sexe Age Salaire ID Sexe Age Salaire sf = 1/n(|x1f - mf| + (|x2f - mf| +...+ (|xNf - mf| )
1 F 27 19 000 1 1 0,00 0,00
2 M 51 64 000 2 0 0,96 0,56 avec :
3 M 52 100 000 3 0 1,00 1,00
4 F 33 55 000 4 1 0,24 0,44
mf = 1/n(x1f+ x2f +...+ xNf)
5 M 45 45 000 5 0 0,72 0,32
¾ Puis calculer le z-score :
zif = (xif - mf)/sf
¾ dist(ID2, ID3) = SQRT( 0 + (0.04)2 + (0.44)2 ) = 0.44
¾ dist(ID2, ID4) = SQRT( 1 + (0.72)2 + (0.12)2 ) = 1.24

Variables binaires Variables binaires

Objet i
z Une table de contingence pour données binaires
1 (Présence) 0 (Absence)
Objet j
1 0 sum a= nombre de positions Objet j 1 (Présence) a b

1 a b a +b où Oi a 1 et Oj a 1 0 (Absence) c d

Objet i 0 c d c+d z Coefficient de Russel et Rao :

sum a + c b + d p ¾ S(i,j) = a/(a+b+c+d)
z Coefficient de Jaccard :
z Exemple Oi=(1,1,0,1,0) et Oj=(1,0,0,0,1) ¾ S(i,j) = a/(a+b+c)
z Coefficient de Dice :
z a=1, b=2, c=1, d=2 ¾ S(i,j) = 2a/(2a+b+c)

3
Variables binaires Variables nominales

z Exemple : z Généralisation des variables binaires : plus de

Toux Fièvre Test
deux états possibles
Apollon N Oui P
Zeus N Oui N
¾ Ex : couleur = {vert, jaune, rouge, bleu}
¾ Intersection, différence,... ensembliste
z Les valeurs Oui et P sont transformées en 1 et les
valeurs N en 0
¾ sJaccard (Apollon, Zeus)=2/3

Similarités de documents Méthodes hiérarchiques

T1 T2 T3 T4 T5 T6 T7 T8 z Créent une décomposition hiérarchique des objets

Doc1 0 4 0 0 0 2 1 3 z Méthodes par agglomérations (bottom-up)
Doc2 3 1 4 3 1 2 0 1 ¾ Départ : chaque objet constitue un cluster
Doc3 3 0 0 0 3 0 3 0 ¾ Regroupe les objets ou clusters les plus proches
Doc4 0 1 0 3 0 0 2 0
¾ Condition d’arrêt : on arrive au concept sommet ou bien une condition est
Doc5 2 2 2 3 1 4 0 2 vérifiée (ex : obtenu k clusters)
z Méthodes par divisions (top-down)
N T1 T2 T3 T4 T5 T6 T7
sim(Ti , Tj ) = ∑ ( wik ⋅ w jk ) T2 7 ¾ Départ : un unique cluster contenant tous les objets
k =1 T3 16 8 ¾ Séparer les objets ou clusters les plus dissimilaires
T4 15 12 18 ¾ Condition d’arrêt : tous les objets sont des concepts feuilles ou bien une
T5 14 3 6 6 condition est vérifiée
T6 14 18 16 18 6 z Différentes méthodes : différentes définitions de la mesure de
T7 9 6 0 6 9 2 dissimilarité entre clusters
T8 7 17 8 9 3 16 3

Méthodes hiérarchiques Méthode hiérarchique : exemple

z Procédure adoptée :
¾ regrouper ensemble tous les éléments dont la distance est
inférieure ou égale à 3 et uniquement ceux-ci.
z Distance ultramétrique : au lieu de l’inégalité triangulaire,
on a :
¾ D(X,Y) <= max(D(X,Z), D(Y,Z))

D Xav Yves Ziad Tania Ute

Xav 0
Yves 4,5 0
Ziad 2 3,5 0
Tania 5 6 4,5 0
Ute 4 5,5 2,5 1,5 0

4
Méthode hiérarchique : exemple Méthode hiérarchique : exemple

z 1ère étape : La paire constituée des éléments les plus proches

z 2ème étape : on cherche la paire qui constituera le
constituera le premier « agrégat ».
deuxième agrégat
¾ On regroupe Tania et Ute -> nouvel ensemble {Xav, Yves, Ziad,
(Tania, Ute)} ¾ Xav et Ziad -> nouvel ensemble {(Xav,Ziad),Yves, (Tania, Ute)}
¾ On recalcule la matrice des distances en considérant que la ¾ On recalcule la matrice des distances
distance entre un élément et un ens. d’éléments est le min des
distances à chaque élément.

D Xav Yves Ziad Tania,Ute D Xav,Ziad Yves Tania,Ute

Xav 0 Xav, Ziad 0
Yves 4,5 0 Yves 3,5 0
Ziad 2 3,5 0 Tania,Ute 2,5 5,5 0
Tania,Ute 4 5,5 2,5 0

Méthode hiérarchique : exemple Méthode hiérarchique : exemple

z 2ème étape : on cherche la paire qui constituera z Conclusion :

le deuxième agrégat ¾ La dernière étape, symbolique, consiste à constater
¾ les objets les plus proches sont (Xav,Ziad) et (Tania, que la distance de Yves à (Xav,Ziad,Tania, Ute), est
Ute) -> nouvel ensemble {(Xav,Ziad,Tania, Ute),Yves} 3,5.

¾ On recalcule la matrice des distances ¾ Nous pouvons distinguer trois groupes ou agrégats, le
premier formé des jurés Tania et Ute distant de celui
D Xav, Ziad, Yves de Xav et Ziad de 2,5 unités et enfin au loin le juré
Tania, Ute Yves distant de 3,5 de ses voisins les plus proches. Il
Xav, Ziad, 0 semble que ce dernier devra être exclu du jury.
Tania,Ute
Yves 3,5 0

Résultat : Dendogramme Méthodes hiérarchiques : Autres stratégies

z La stratégie
d’agrégation de
l’exemple est une
3,5 stratégie du
2,5 “minimum”. Peut-on
2
en imaginer d’autres ?
1,5
¾ On peut en envisager au
moins 6 autres !

Tania Ute Xav Ziad Yves

5
Méthodes par partitionnement Méthodes par partitionnement

z Partitionnement : les objets du jeu de données sont z But : partitionner un ensemble X de N objets {x1, x2, ... xN} en k
groupés en k clusters classes (k fixé par l'utilisateur)
z Chaque classe Ck ayant Nk membres est définie par un prototype ou
z Étant donnée une valeur k, trouver une partition de k centre
clusters qui optimise le critère de partionnement (fonction 1
de similarité) mk =
Nk
∑x
x∈Ck
z Approches heuristiques : z Critère de performance : à défaut de valeurs cibles, l'erreur est
¾ K-means : chaque cluster est représenté par son centre de définie comme la distance euclidienne entre individus et centres des
gravité groupes
¾ K-medoïds : chaque cluster est représenté par un objet du cluster K 2 K T

E 2 = ∑ ∑ x x − mk = ∑ ∑ ( x − mk ) ( x − mk )
k =1 x∈Ck k =1 x∈Ck

Algorithme des K-Means K-Means : exemple

z Algorithme de base : En utilisant la mesure de similarité classique, calculer la nouvelle matrice
de similarités aux clusters
1. selectionner K points comme les représentants initiaux
2. for i = 1 to N, affecter l’item xi au centre le plus similaire (ceci donne K clusters) T1 T2 T3 T4 T5 T6 T7 T8
Classe1 29/2 29/2 24/2 27/2 17/2 32/2 15/2 24/2
3. for j = 1 to K, recalculer le centre du cluster Cj Classe2 31/2 20/2 38/2 45/2 12/2 34/2 6/2 17/2
4. repéter les étapes 2 et 3 jusqu’à ce qu’il n’y ait plus (ou peu) de changement Classe3 28/2 21/2 22/2 24/2 17/2 30/2 11/2 19/2
dans les clusters Affecté à Classe2 Classe1 Classe2 Classe2 Classe3 Classe2 Classe1 Classe1
z Exemple: Clustering de mots Calculer les centres des nouveaux clusters en utilisant la matrice initiale
Affectation initiale arbitraire : Centres des Clusters
C1 = {T1,T2}, C2 = {T3,T4}, C3 = {T5,T6}
T1 T2 T3 T4 T5 T6 T7 T8 C1 C2 C3
Doc1 0 4 0 0 0 2 1 3 8/3 2/4 0/1
T1 T2 T3 T4 T5 T6 T7 T8 C1 C2 C3 Doc2 3 1 4 3 1 2 0 1 2/3 12/4 1/1
Doc1 0 4 0 0 0 2 1 3 4/2 0/2 2/2 Doc3 3 0 0 0 3 0 3 0 3/3 3/4 3/1
Doc2 3 1 4 3 1 2 0 1 4/2 7/2 3/2 Doc4 0 1 0 3 0 0 2 0 3/3 3/4 0/1
Doc3 3 0 0 0 3 0 3 0 3/2 0/2 3/2 Doc5 2 2 2 3 1 4 0 2 4/3 11/4 1/1
Doc4 0 1 0 3 0 0 2 0 1/2 3/2 0/2
Doc5 2 2 2 3 1 4 0 2 4/2 5/2 5/2 Le processus est répété jusqu’à ce que les clusters ne soient plus modifiés

K-means : Illustration K-Means : Quelle valeur de K ?

z Nombre de classes K à fixer par l'utilisateur
Calcul des
Choix aléatoire de centres des ¾ soit en utilisant des connaissances du domaine : K=10 pour la
k objets, centres clusters et reconnaissance de chiffres
initiaux et calcul recalcul des ¾ soit de manière empirique : essayer différentes valeurs de K et choisir le
des clusters clusters K qui optimise un critère de qualité/validité du clustering obtenu
z L'erreur n'est pas un bon indice de qualité/validité :
¾ décroît monotoniquement avec K. On peut chercher le "coude" de la
courbe :
On stoppe Calcul des
lorsque les centres des
clusters sont clusters et
stables recalcul des
clusters

z Le calcul de l'erreur n'est basé que sur la dispersion intra-groupes

6
Indice de validité VRC K-means : bilan
z Force des k-means:
z Une trentaine d'indices de validité étudiés par Mulligan & Cooper 85
¾ Relativement efficaces : O(tkn), où n est le nb d’objets, k est le nb de clusters, et
z Meilleures performances obtenues par l'indice VRC (variance ratio t est le nb d’itérations. Normalement, k, t << n
criterion) ¾ Terminent souvent dans un optimum local
dispersion inter − groupes B z Faiblesse des k-means:
VRC = =
dispersion intra − groupes W ¾ Besoin de préciser k à l’avance
1 K ¾ Sensibles aux données bruitées et aux exceptions, aux cas aberrants
∑ N t mt − m
2
B=
K − 1 t =1 ¾ Sensibles à l’initialisation
2
z lancer plusieurs éxecutions avec différents états initiaux
K
1
∑ x−m
z retenir la configuration jugée la meilleure
W= ¾ marche mal lorsque les groupes se chevauchent => variante : K-means flou
N −K
t
t =1
z Les variantes des K-Means diffèrent dans :
m = grand centre (vecteur des moyennes prises sur toutes les N ¾ La sélection des k initiaux
données ) ¾ Calcul de la dissimilarité
m i = centre du groupe i ¾ Stratégies pour calculer la moyenne d’un cluster

z Choisir le K qui maximise VRC.

Soft K-Means Clustering Modèles probabilistes

z Cas particulier du k-means : chaque individu z Les individus à classifier sont des réalisations
appartient à un cluster avec un certain degré de indépendantes d’un vecteur aléatoire de loi f.
probabilité z Plusieurs approches :
¾ Classification bayésienne
¾ Estimation de densité de probabilité (méthodes non
paramétriques)
¾ Modèles fonctionnels à effet fixe
¾ Mélange fini de densités de probabilité

Le modèle de mélange Modèle de mélange : exemple

z Mélange gaussien
¾ La densité de chaque classe k (population) est une loi normale A 51 B 62 B 64 A 48 A 39
A 43 A 47 A 51 B 64 B 62
¾ Paramètres B 62 A 52 A 52 A 51 B 64
z sigma : distance maximale de voisinage B 64 B 64 B 62 B 63 A 52
z m : nombre minimal d’objets dans le voisinage d’un objet pour qu’il soit l’objet cœur d’un cluster A 45 A 51 A 49 A 43 B 63
A 42 B 65 A 48 B 65 B 64
z Deux approches pour effectuer une classification: A 46 A 48 B 62 B 66 A 48
¾ Approche statistique classique estimant les paramètres des composants du mélange A 45 A 49 A 43 B 65 B 64
(approche mélange) A 45 A 46 A 40 A 46 A 48
z Maximisation de la vraisemblance : algorithme EM
¾ Maximisation de la vraisemblance (ou log-vraisemblance)
¾ Il n’existe pas de solution analytique
¾ Algo EM utilisé :
z Etape Estimation
z Etape Maximisation
z Approche estimant simultanément les paramètres des composants et le composant
dont est issu chaque point de l’échantillon (approche classification)
¾ On ajoute comme paramètres supplémentaires à estimer la classe à laquelle appartient
chaque individu
z Vraisemblance classifiante
z CEM = EM + étape Classification entre le E et le M.
µA=50, σ A =5, p A =0.6 µB=65, σB =2, p B=0.4

7
Modèle de mélange : exemple Fuzzy k-means

z Trouver les 5 paramètres : mA, sigmaA, mB, z Initialiser les moyennes m1, m2,..., mk
sigmaB, pA z Tant qu’il n’y a pas de changement dans les moyennes :
¾ m = x1 + ... + xn/n ¾ Utiliser les moyennes estimées pour trouver les degrés
d’appartenance u(j,i) de xj dans le Cluster i;
¾ sigma2= [(x1-m) 2 + ... + (xn-m) 2] /(n-1) par exemple, si a(j,i) = exp(- || xj - mi ||2 ), on peut utiliser u(j,i) =
a(j,i) / sum_j a(j,i)
¾ pA = nb d’exemples dans A / n
¾ For i = 1 to k
z Problème : on ne connait ni la classe des z Remplacer mi avec la moyenne floue de tous les exemples du

∑ u ( j , i) x
Cluster i 2
exemples ni les 5 paramètres j

mi =
j
¾ m = w1x1 + ... + wnxn/(w1+...+wn)
∑ u ( j, i) 2

¾ sigma2= [w1(x1-m)2 + ... + wn(xn-m)2] /(w1+...+wn) ¾ end_for

j

z end_until

Les cartes auto-organisatrices (Kohonen 82) SOM : principes

z self-organizing maps ou SOM, souvent appelés "réseaux z Les relations de voisinage entre les neurones définissent
de Kohonen" une topologie et donc un nouvel espace. 2 espaces :
z très proches des algorithmes de centres mobiles ¾ Un espace des entrées dans lequel peuvent être représentés les
¾ représentent les données par un nombre réduit de prototypes données et les vecteurs poids des neurones
(appelés neurones dans les SOM) ¾ Un espace de sortie (ou carte à une ou deux dimensions) qui
¾ méthode d'apprentissage compétitive : le "gagnant" = le prototype contient l’ensembles des neurones et sur lequel une topologie a
le plus proche de l'objet donné été définie.
z ce qui distingue les SOM de K-means : préservation de la z But de la cartographie associative :
topologie ¾ Associer chaque vecteur d’entrée à un neurone de la carte
¾ les objets les plus semblables seront plus proches sur la carte =>
¾ On espère que 2 vecteurs proches dans l’espace des entrées
visualisation claire des groupements
exciteront 2 neurones proches sur la carte.

La topologie du SOM Le fonctionnement du SOM

z réseau à une couche

z neurones ou prototypes
¾ vecteurs représentant les mêmes attributs que les données
¾ simples neurones linéaires, chacun connecté à toutes les entrées
¾ disposés sur une grille régulière (typiquement en 1-D ou 2-D)
z l'utilisateur choisit a priori la géométrie du réseau

Sur présentation d'un exemple :

z chaque neurone calcule sa distance par rapport à x. Le "gagnant" =
le neurone le plus proche de x
z la carte finale = une projection non linéaire de la densité de données z le gagnant et ses neurones voisins sont "tirés" vers x => garantit la
de haute dimensionnalité sur un espace 2-D préservation de la topologie
z la carte se comporte comme une bande ou surface élastique qu'on
étire pour la rapprocher des données

8
Algorithme du SOM Paramètre 1 : le pas d'apprentissage

z Initialiser un ensemble de neurones ou prototypes suivant la topologie z Contrôle la vitesse d'apprentissage et le compromis
choisie
¾ Architecture de la carte spécifiée => revient à choisir le nb de neurones et définir
stabilité/plasticité
les relations de voisinage ¾ h trop petit : le modèle ne s'adapte pas assez aux données =>
z Boucle de base : apprentissage très lent
¾ 1. Lire un vecteur d'entrée x ¾ h trop grand : apprentissage rapide, mais risque d'instabilité =>
¾ 2. Repérer le neurone k le plus proche de x (dist. euclidienne) peut ne jamais converger
||x - wk|| < || x - wi|| pour tout i = k
¾ 3. Mise à jour : tirer vers x les neurones i = {le gagnant k et les autres neurones
du voisinage centré sur k} z L'idée : focaliser rapidement sur une région prometteuse
w'i = wi + h*L(wi , wk)(x - wi) de l'espace d'hypothèses, puis affiner la recherche dans
z L'importance du déplacement : régie par 2 paramètres: cette région
¾ le pas d'apprentissage h ¾ choisir h grand au départ et le réduire graduellement
¾ la fonction de voisinage L(.) (souvent gaussienne)
¾ l'apprentissage s'arrête dès que h = 0

Paramètre 2 : la fonction de voisinage Exemple : Carte mondiale de la pauvreté

z La fonction de voisinage entre le neurone gagnant m k et un neurone z Illustre la robustesse des SOM aux données manquantes
m i doit décroître monotoniquement avec la distance entre les deux. z Données : statistiques de la Banque Mondiale
z Caractérisée par une forme et une largeur sigma z 126 pays, 39 indicateurs économiques (relatifs à la population)
¾ 78 pays utilisés pour entraîner le SOM
¾ autres pays ( > 11 valeurs manquantes) : intégrés dans la carte après
apprentissage
z Visualisation des groupements dans les SOM

¾ sigma grand (grand voisinage) => beaucoup de neurones se rapprochent ¾ utiliser des niveaux de gris pour représenter les distances relatives entre
en même temps de la donnée actuelle vecteurs

¾ sigma petit => adaptativité très localisée

z Commencer par un grand voisinage et le réduire progressivement

Exemple : Carte mondiale de la pauvreté Exemple : Carte mondiale de la pauvreté

9
SOM : bilan Clustering conceptuel

z Robuste aux données incomplètes z Le clustering est réalisé en fonction d’un modèle mathématique
z On construit le treillis de concepts fréquents
z Ajustable aux très grandes bases de données : ¾ Hiérarchie conceptuelle inhérente au données
¾ établissement d'une carte des 78 000 protéïnes de Swiss-Prot en ¾ Chaque concept est un couple : (Extension,Intension)
2000 z L’extension est un ensemble d’objets
z L’intention est l’ensemble maximal d’attributs communs aux objets
¾ regroupement d'environ 7 millions de documents (demandes de ¾ Les concepts sont déterminés par la fermeture de Galois
brevets) z Intension : ensemble fermé d’attributs (ensemble maximal d’attributs commun
aux objets)
z Essentiellement un outil d'analyse exploratoire et de z Extension : ensemble fermé d’objets (si on ajoute un objet, on diminue la taille
de l’extension)
visualisation. z Un concept est fréquent si son extension contient un nombre d’objets
supérieur à un seuil minsup
z Tentatives pour utiliser les SOM à des fin prédictives non
¾ Les concepts fréquents constituent les clusters
concluantes. cf. Michie et al. 1994 (Projet StatLog)

Clustering conceptuel COBWEB

z Le clustering est réalisé à partir d’une relation binaire R

inclus O X A
¾ O : ensemble fini d’objets
¾ A : ensemble fini d’attributs binaires
z Au début, l’arbre consiste en une racine vide
z Les exemples sont ajoutés un par un, et l’arbre est mis à
jour à chaque étape :
¾ Consiste à trouver la bonne feuille pour chaque exemple
(éventuellement en restructurant l’arbre)
¾ Les décisions de mises à jour sont basées sur l’utilité de la
catégorie

10