Les structures d’un schéma de clustering

INTRODUCTION

Depuis plusieurs années, l’information est devenue un élément très présent autour de nous et depuis la venue de l’informatique, non seulement le volume des données stockées sous forme numérique est en croissance, mais aussi le type de ces données est devenu très varié. Le domaine de la fouille de données se focalise sur le traitement de ces données afin d’extraire et de mettre en évidence des informations utiles. L’organisation et la structuration des données est l’une des tâches les plus importantes dans le domaine de la fouille de données. Grâce à son importance cruciale dans le développement de notre société, la création de groupe ou la classification est une opération omniprésente dans la vie quotidienne. L’organisation et la structuration d’un ensemble d’éléments sont des tâches qui font appel naturellement aux groupes.

Les groupes sanguins, les espèces d’animaux, les genres de musique et de films représentent des exemples rencontrés dans la vie de tous les jours . De façon informelle, la création de groupe peut être définie comme étant la tâche visant à rassembler un ensemble d’éléments en raison d’une relation particulière. Les premières recherches théoriques en classification ont été réalisées par les biologistes afin de spécifier des classes d’animaux. Le but était d’affecter un animal à une telle ou telle espèce étant donnée une description simple de cet animal.La problématique consistant à former automatiquement des groupes est appelée classification automatique. Cette problématique s’est posée dans de nombreux domaines. En médecine, pour classer les patients ou en marketing pour regrouper les personnes ayant des comportements de consommation similaires et plus récemment, dans le domaine des technologies de l’information et de la communication où les données peuvent être classées selon leur nature, leur taille et leur diversité.Dans la classification, deux approches sont considérées. Ces approches diffèrent selon si les groupes existent à priori ou non. On distingue alors la classification non supervisée et la classification supervisée [Hartigan, 1975] [Kaufman & Rousseeuw, 1990]. Dans l’approche supervisée, les groupes existent à priori. Le problème consiste alors à créer une procédure permettant d’affecter les éléments aux différents groupes (classes).

Ce type d’approche nécessite l’existence d’un ensemble d’éléments dont la classe est connue. Cet ensemble est appelé ensemble d’apprentissage. Il est utilisé pour concevoir le modèle permettant de classer de nouveaux éléments [Celeux & al., 1989].

Les structures d’un schéma de clustering

Dans ce qui suit, nous utilisons les notations suivantes :
• X={x1, x2, x3,…, xn} : l’ensemble des objets à classer.
• C={C1, C2, C3, …., Ck} : un schéma de clustering composé de K clusters.
• |Ci| : Le nombre d’objets dans le cluster Ci .

Le résultat d’un algorithme de clustering peut être représenté sous différents formats :
• Le clustering dur (hard clustering): c’est le résultat le plus simple et le plus souvent rencontré. Dans ce type de clustering, chaque objet appartient à un et un seul cluster c’est-à-dire : ∪ = avec ∀ , ∈ , ∩ = ∅
• Le clustering doux (soft clustering) : appelé aussi le clustering par chevauchement. Ce type de clustering est rencontré quand les frontières entre les clusters sont difficiles à définir. Dans ce cas, il arrive que certains objets soient à la frontière entre plusieurs clusters. Pour refléter cette situation, le clustering doux permet à ces objets d’appartenir à plus d’un cluster. 
• Le clustering flou (fuzzy clustering): un schéma de clustering doux est difficile à interpréter et manque souvent de précision. Le clustering flou permet d’apporter une solution à ce problème en permettant à un objet d’appartenir à un cluster selon un degré d’appartenance

Similarité, dissimilarité et distance

L’élément de base de tout algorithme de clustering est une mesure de proximité, de dissimilarité ou de distance. De nombreuses formules ont été développées pour évaluer la similarité entre les objets. Il a été aussi démontré que la formule utilisée a une grande influence sur le résultat [Roux, 1985]. Donc la définition de la mesure de similarité ou de distance constitue en soit une problématique dans le domaine de la classification. Le choix d’une formule doit être donc consciencieusement réfléchi car la formule ne dépend pas seulement du problème considéré mais aussi de variables descriptives du problème.Selon [Celeux & al., 1989], une similarité ou une dissimilarité est une application à valeurs numériques permettant de mesurer le lien entre les objets d’un même ensemble. Dans le cadre de la similarité, ce lien est d’autant plus fort si sa valeur est grande.

Dans le cadre de la dissimilarité et par opposition, ce lien est plus fort si sa valeur est petite.Nous donnons, dans la suite de cette section, un cadre formel des notions de similarité, de dissimilarité et de distance et nous présentons les principales formules développées dans la littérature [Roux, 1985][De Carvalho, 1994][Nieddu & Rizzi, 2003].

Le clustering hiérarchique

Le but de ce type de clustering est de créer une hiérarchie de clusters. La racine de la hiérarchie contient l’ensemble des objets et les différents niveaux contiennent des clusters composés des objets considérés comme similaires. Le résultat du clustering est représenté par un dendrogramme (figure 1.1) où les niveaux représentent les clusters et les feuilles représentent les objets. Cette représentation permet une meilleure visualisation des données et du processus de clustering. Il existe deux approches principales de clustering hiérarchique : l’approche descendante et l’approche ascendante.

L’approche descendante
Appelée aussi approche divisive, elle démarre d’un unique cluster contenant l’ensemble des objets. Ce cluster est divisé successivement de manière à ce que les clusters résultant soient les plus dissimilaires possibles. Le processus de clustering se termine lorsque chaque cluster sera réduit à un singleton représentant une feuille de l’arborescence. La difficulté de définir le critère de séparation d’un cluster constitue l’inconvénient majeur de ce type d’approche et c’est la raison pour laquelle il n’existe que peu d’algorithmes divisifs. En effet, pour un cluster composé de n objets, il existe 2n-1 possibilités de division. DIANA (DIvisive ANAlysis) [Kaufman & Rousseeuw, 1990] est l’un des algorithmes les plus utilisés dans ce type d’approche. Cet algorithme (figure 1.2) permet d’éviter l’exploration de toutes les possibilités de séparation en commençant par déterminer l’objet le plus dissimilaire (atypique) d’un cluster et de lui associer les objets les plus proches de façon à définir deux clusters.

L’approche ascendante
Connue sous le nom de l’approche agglomérative ou par fusion (figure 1.3). Au démarrage d’un algorithme agglomératif, chaque objet constitue un cluster. Les clusters similaires sont ensuite fusionnés successivement jusqu’à ce que tous les objets soient regroupés dans un même cluster représentant la racine de la hiérarchie. Dans un algorithme hiérarchique ascendant il n’existe que `@ possibilités pour fusionner deux clusters parmi n. Ce qui réduit la complexité de ce type d’approche par rapport à l’approche descendante. Dans l’approche hiérarchique, la mesure de distance joue un rôle primordial dans la détermination des clusters à fusionner (les plus proches) ou des clusters à diviser (les plus éloignés).

Trois alternatives existent pour déterminer la distance entre deux clusters [Karipys & al., 1999]:
• La méthode « single-link » qui consiste à considérer le minimum des distances entre tous les couples d’objets appartenant à des clusters différents.
• La méthode « complete-link » qui utilise le maximum des distances entre tous les couples d’objets appartenant à des clusters différents.
• La méthode « average-link » qui utilise la moyenne des distances entre tous les couples d’objets appartenant à des clusters différents.

Le clustering par densité

Cette technique considère les clusters comme des régions homogènes de haute densité. DBSCAN [Ester & al., 1996] est l’un des algorithmes de référence dans ce type de clustering. Cet algorithme est basé sur deux paramètres :
1- ε : le radius du voisinage de l’objet xi. où le voisinage représente l’ensemble des objets de X qui sont distant d’au plus ε de l’objet xi.
2- M : le nombre minimum d’objets contenu dans ce voisinage pour considérer la zone comme dense.

L’algorithme est basé sur un processus itératif qui consiste à :
• Sélectionner un objet non encore affecté à un cluster.
• Si son voisinage respecte le critère de densité (défini par les deux paramètres (ε, M) fournis en entrée) alors les objets correspondant sont intégrés au cluster courant.
• Répéter la dernière étape pour chaque objet du voisinage. L’approche présente des faiblesses liées à sa complexité quadratique et à sa sensibilité aux paramètres permettant de définir le critère de densité. Cependant, elle est caractérisée par sa capacité à considérer des clusters de forme variée et aussi par sa capacité à faire face au bruit qui peut exister dans les données.

Evaluation de la qualité d’un schéma de clustering

L’existence d’un nombre important de schémas de clustering possibles pour un même ensemble de données nécessite la définition d’un critère d’évaluation de la qualité d’un schéma de clusteringafin de déterminer si un résultat est meilleur qu’un autre. L’évaluation de la qualité d’un schéma de clusteringa été sujette de plusieurs travaux de recherche [Halkidi & Vazirgiannis, 2001] [Halkidi & al., 2002] [Jain & Dubes, 1988] [Tan & al., 2005]. Les méthodes proposées peuvent être regroupées en trois grandes catégories:
1. L’évaluation externe.
2. L’évaluation interne.
3. L’évaluation relative.

Evaluation externe
Connue aussi sous le nom de l’approche d’évaluation supervisée. Elle consiste à mesurer l’adéquation entre résultat d’un schéma de clusteringC et un partitionnement connu P de l’ensemble des données. Plusieurs mesures ont été développées pour comparer cette adéquation, telles que les mesures de comptage utilisées pour la définition des mesures de similarité dans le cas des objets symboliques à savoir l’indice de Rand, l’indice de Jaccard, l’indice de Fowlkes et Mallows.

Ces indices permettent de mesurer les taux de liaison ou non-liaison correcte à travers la définition des paramètres suivants :
1. a: le nombre de paires d’objets (xi, xj) tels que xi et xj se trouvent dans le même cluster dans le clustering C ainsi que dans P (liaison correcte).
2. b: le nombre de paires d’objets (xi, xj) tels que xi et xj se trouvent dans le même cluster dans le clustering C mais dans des clusters différents dans P (liaison incorrecte).
3. c: le nombre de paires d’objets (xi, xj) tels que xi et xj se trouvent dans le même cluster dans le clustering P mais dans des clusters différents dans C (non liaison incorrecte).
4. d: le nombre de paires d’objets (xi, xj) tels que xi et xj ne se trouvent pas dans le même cluster dans le clustering C et dans P (non liaison correcte). 

Evaluation interne
Appelée aussi évaluation non supervisée. Dans ce type d’évaluation, l’information interne au clustering, telle que la matrice de similarité, est utilisée comme référence. Elle mesure le degré de correspondance entre le résultat du clustering et l’information contenue dans l’ensemble de données. Le meilleur clustering est celui qui conserve le maximum d’information relativement à l’information contenue dans la matrice de similarité. Ce type d’approche permet aussi d’évaluer la compacité et la séparabilité des clusters. De nombreuses mesures existent, nous présentons dans ce qui suit les plus connues.

L’évaluation relative
Basée sur un critère d´évaluation bi-objectif. Le meilleur clustering est celui qui réalise le meilleur compromis entre la distance inter-clusters qu’il faut maximiser et la distance intra-cluster qu’il faut minimiser.

La prise en compte de contexte dans le processus de clustering

La prise en considération du contexte lors de la définition des clusters est l’un des problèmes les plus difficiles dans le domaine du clustering. En effet, il faut admettre que dans le cadre d’un processus de clustering certains attributs peuvent être déterminants pour la création d’un cluster et sans aucune importance pour un autre. Par exemple, dans les problèmes de clustering en analyse de données, les attributs d’un objet sont exprimés par des valeurs qui ne sont pas à optimiser, donc une simple différence de valeurs par rapport à chaque attribut est prise en considération pour évaluer la dissimilarité entre les objets.Contrairement aux problèmes du clustering en analyse de données, les problèmes de clustering en aide multicritère à la décision sont caractérisés par l’existence de différentes types d’informations. En effet, les objets ne sont pas décrits pas des attributs mais plutôt par des critères qui reflètent les préférences du décideur.

Ces critères sont souvent contradictoires et sont considérés comme des fonctions à optimiser. A chaque critère est associé un poids qui représente son degré d’importance selon la perception subjective du décideur. De plus, des fonctions de préférence sont utilisées pour comparer les objets entre eux.La prise en compte de toutes ces caractéristiques, dans un processus de clustering, nécessite une étude supplémentaire car il est clair qu’une simple mesure de distance, définie globalement, est inadaptée pour ce type de problème. Selon [De Smet & Guzman, 2004] cette observation constitue une barrière fondamentale devant l’utilisation des méthodes de clustering dans le contexte d’aide multicritère à la décision d’où la nécessité de développer de nouvelles approches de clustering adaptées à ce contexte. Parmi les approches qui se sont intéressées au domaine de clustering en aide multicritère à la décision, nous mentionnons le travail de De Smet et Guzman [De Smet & Guzman, 2004] qui a développé une mesure de distance basée sur les relations de préférence.

Cette distance a été utilisée pour étendre l’algorithme k-means au contexte multicritère. Ce travail a été étendu par De Smet et Eppe dans [De Smet & Eppe, 2009] pour définir des relations entre les clusters. Figueira et al. [Figuiera & al., 2004] se sont intéressés à l’extension de la méthode multicritère PROMETHEE [Brans & al., 1982] pour construire des clusters. Nemery a proposé une approche de clustering qui génère un ensemble de clusters ordonnés dans [Nemery, 2006]. L’approche utilise le degré de préférence de chaque objet pour regrouper les objets. La méthode génère des clusters de façon à ce que le degré de préférence soit minimisé entre les objets appartenant au même cluster et maximisé entre les objets appartenant à des clusters différents. Nous mentionnons également les travaux de Meyer et Olteanu [Meyer & Olteanu, 2013], Rocha & Dias [Rocha & Dias, 2013] et [Rocha & al., 2013]. L’ensemble de ces travaux seront étudiés plus loin dans ce mémoire. Nous nous intéressons, dans cette thèse, à un problème de clustering dans un contexte d’aide multicritère à la décision.

Ce contexte est caractérisé par :
– Chaque objet est décrit par un ensemble de critères.
– Chaque critère est considéré comme une fonction à optimiser.
– Les critères sont souvent conflictuels.
– Les critères n’ont pas le même degré d’importance (à chaque critère est associé un poids représentant son importance).
– Les valeurs des critères peuvent être de natures différentes (numérique, intervalle, ordinale, nominale….).
– Les objets sont comparés les uns aux autres par des relations de préférence.

Table des matières

Introduction générale
PARTIE I : Clustering et Aide multicritère à la décision
Chapitre 1 : Le clustering
1. Introduction
2. Le clustering
2.1.Définition
2.2.Les structures d’un schéma de clustering
2.3.Les étapes d’un processus de clustering
3. Similarité, dissimilarité et distance
3.1.Propriétés formelles
3.1.1. Indice de dissimilarité
3.1.2. Indice de similarité
3.1.3. Distance
3.2.Différentes mesures de similarité
3.2.1. Cas des variables numériques
3.2.2. Cas des variables ordinales
3.2.3. Cas des variables nominales
3.2.4. Cas des variables binaires
3.2.5. Cas des variables symboliques
3.2.6. Cas des variables hétérogènes
4. Les méthodes de clustering
5. Les problèmes du clustering
6. Evaluation de la qualité d’un schéma de clustering
6.1.Evaluation externe
6.2.Evaluation interne
6.2.1. Somme des erreurs au carré : SSE
6.2.2. Le coefficient silhouette : CS
6.2.3. L’indice de Wemmert et Gançarski : WG
6.3.Evaluation relative
6.3.1. L’indice de Dunn
6.3.2. L’indice de Davis et Bouldin
6.3.3. La fonction de Mimaroglu et Yagci
7. Le problème de désagréments en clustering
8. La prise en compte du contexte dans le processus de clustering
9. Conclusion
Chapitre 2 : Aide multicritère à la décision (AMCD)
1. Introduction
2. L’aide multicritère à la décision
3. Concepts de base
3.1.Le concept de critère
3.2.Les actions potentielles
3.3.Le tableau de performances
3.4.Le système relationnel de préférence
4. Problématiques multicritère en aide à la décision
4.1.Problématique de choix P.α
4.2.Problématique de rangement P.γ
4.3.Problématique du tri P.β
5. Les méthodes d’aide multicritère à ladécision
5.1.Les méthodes d’agrégation complète
5.2.Les méthodes d’agrégation partielle
5.2.1. La méthode PROMETHEE
5.2.2. La méthode ELECTRE III
5.3.Les méthodes d’agrégation locale
6. La classification multicritère
6.1.La méthode ELECTRE Tri
7. Conclusion
PARTIE II : Contributions et évaluation de l’approche proposée
Chapitre 3 : Le clustering en aide multicritère à la décision : Proposition d’un nouvelle mesure de dissimilarité
1. Introduction
2. Le clustering multicritère
2.1.Définitions du clustering multicritère
2.1.1. Définition de Ferligoj et Batagelj
2.1.2. Définition d’Eppe, Roland et De Smet
2.1.3. Définition de Meyer & Olteanu
3. Les principales approches du clustering en AMCD
3.1.L’approche de De Smet & Guzman
3.1.1. La mesure de distance
3.1.2. Une extension de l’algorithme k-means au contextemulticritère
3.2.L’approche de De Smet & Eppe
3.3.L’approche d’Eppe, Roland & De Smet
3.4.L’approche de De Smet, Nemery & Selvaraj
3.5.Les travaux de Rocha et Dias
4.Problématique
5. Contribution : Proposition d’un indice de dissimilarité multicritère
5.1.Le principe de désagrément en AMCD5.1.1. Définition de l’accord en AMCD
5.1.2. Définition du désagrément (désaccord) en AMCD
5.1.3. Définition de l’indice de dissimilarité
5.2.Illustration
5.2.1. Génération des profiles des objets
5.2.2. Génération des matrices de dissimilarité
6. Discussion
Chapitre 4 : Agrégation des schémas de clustering : Une nouvelle formulation du problème du clustering en aide multicritère à la décision
1. Motivations
2. L’agrégation des schémas de clustering
3. Contribution : une nouvelle formulation du problème du clustering en AMCD
3.1.Hypothèses
3.2.Problématique
3.3.Domaine d’extension
3.4.Résolution
4. Les approches de l’agrégation des schémas de clustering
4.1.Approche par minimisation des désagréments
4.1.1. Définition du désagrément en agrégation des schémas de clustering
4.2.Approches par ensemble
4.2.1. Les méthodes basées sur les matrices de co-association
4.2.2. Les méthodes basées sur les hypergraphes
4.2.3. Les méthodes basées sur le vote
4.2.4. La méthode COMUSA
4.2.5. La méthode CL_CONSENSUS
5. Description détaillée de l’approche proposée
6. Conclusion
Chapitre 5 : Evaluations et analyse de sensibilité
1. Introduction
2. Caractéristiques de l’approche proposée
3. Spécifications des études de cas
3.1.Problème1 : Business risk Failure
3.2.Problème2: Aménagement du territoire
4. Evaluation de notre approche
4.1.Evaluation de l’impact de l’indice de similarité sur la qualité des schémas de clustering individuels
4.2.Evaluation de l’impact de la méthode multicritère sur la qualité des schémas de clustering individuels
4.3.Comparaison de la mesure de dissimilarité proposée avec la distance développée par De Smet et Guzman
4.4.Evaluation de l’impact de la méthode d’agrégation sur la qualité du schéma de clustering final
5. Discussion sur la complexité de notre approche
6. Conclusion 
Chapitre 6 : Etude des propriétés relationnelles des clusters agrégés : Extension au clustering relationnel
1. Introduction
2. Définitions
2.1.Le clustering non-relationnel
2.2.Le clustering relationnel
2.3.Le clustering ordonné
3. Contribution : Extension de l’approche proposée au clustering relationnel
3.1.Définition d’une relation dominante
3.2.Exemple
3.3.Généralisation
4. Application au problème du Country Risk
5. Conclusion
Conclusion générale
Bibliographie
Annexe A
Annexe B

Télécharger le rapport complet