University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Messai ,Dhaia eddine |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Évaluation des performances des algorithmes clustering (Validation des algorithms) / Messai ,Dhaia eddine
Titre : Évaluation des performances des algorithmes clustering (Validation des algorithms) Type de document : texte imprimé Auteurs : Messai ,Dhaia eddine, Auteur ; Mediani ,chahrazed, Directeur de thèse Editeur : Setif:UFA Année de publication : 2019 Importance : 1 vol (67 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : clustering
Indices de validation
K-means
Birch
HCA
ARI
V-measure
CompletenessIndex. décimale : 004 - Informatique Résumé : La validation de clustering est un sujet de recherche très important qui intéresse beaucoup
de chercheurs en classification non supervisée des données, et c’est un axe de
recherche pas moins important que le clustering lui-même. Plusieurs indices de validation
de clustering ont été proposés dans la littérature.
Les travaux sur des méthodes de classification non supervisées, nous ont amené Ã
s’interroger sur la qualité des résultats. Le problème consiste à estimer si une méthode de
regroupement est «meilleure» qu’une autre pour un jeu particulier de données. Initialement,
après un état de l’art desméthodes existantes, nous avons appliqué certains de ces
méthodes comme k-means, HCA, ect., en choisissant des paramètres et des solutions
optimaux et les valider par des indices de qualité de clustering comme ARI, V-measure,
Completeness ... à l’aide de la bibliothéque scikit-learn de l’environnement python. Ces
indices de qualité nous ont permis de sélectionner le meilleure regroupement , qui est le
regroupement hiérarchique (HCA et Birch) pour notre jeu de données choisi.Note de contenu : Sommaire
Liste des tableaux xi
Table des figures xiii
1 Apprentissage automatique-Géneralité 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Pourquoi l’apprentissage automatique? . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Définition de l’apprentissage automatique . . . . . . . . . . . . . . . . . . . . 4
1.4 Déférents étapes pour création modèle apprentissage . . . . . . . . . . . . . . 4
1.4.1 Collection des données . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.2 Préparation des données . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.3 Entraîner un modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.4 Évaluation de modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Domaines de l’Apprentissage Automatique . . . . . . . . . . . . . . . . . . . . 5
1.5.1 Fouille des données (data mining) . . . . . . . . . . . . . . . . . . . . . 6
1.5.2 Intelligence artificielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Les techniques d’apprentissage automatique . . . . . . . . . . . . . . . . . . . 8
1.6.1 Apprentissage supervisé . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6.2 Apprentissage non supervisé . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Les algorithmes d’apprentissage automatique . . . . . . . . . . . . . . . . . . 11
1.7.1 Arbre de décision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.2 Support vecteur machine(SVM) . . . . . . . . . . . . . . . . . . . . . . 12
1.7.3 k-plus proche voisine . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.4 Naïve de bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Etat de l’art : Clustering et Validation de ses algorithmes 17
vii
TABLE OF CONTENTS
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Définition de clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1 Définition 1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Définition 2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Les objectives du clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Qu’est ce qu’un bon Clustering? . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 Les principales étapes du clustering . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.1 La préparation des données : . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.2 Le choix de l’algorithme de clustering : . . . . . . . . . . . . . . . . . . 21
2.5.3 Validation et l’exploitation des résultats de l’algorithme . . . . . . . . 22
2.6 Applications du Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6.1 La segmentation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6.2 Extraction des connaissances . . . . . . . . . . . . . . . . . . . . . . . . 23
2.7 Les différentes méthodes de clustering . . . . . . . . . . . . . . . . . . . . . . . 24
2.7.1 Clustering en partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.7.2 Clustering hiérarchique (Hierarchical Cluster Analysis) . . . . . . . . 28
2.7.3 clustering basée sur la densité . . . . . . . . . . . . . . . . . . . . . . . 32
2.7.4 clustering par grilles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.8 Clustering et Fonctions de similarité . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8.1 la distance Euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8.2 la distance deManhattan . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8.3 la distance deMinkowski . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.9 Les techniques d’évaluation de la qualité du clustering(validation) . . . . . . 37
2.9.1 Variance intra-classe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.9.2 Connectivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.9.3 L’indice de Davies-Bouldin . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.9.4 Précision-Rappel et F-mesure . . . . . . . . . . . . . . . . . . . . . . . 39
2.9.5 Coefficient de Jaccard . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.9.6 L’indice Rand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.9.7 Silhouette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.9.8 V-measure [Homogeneity et completeness] . . . . . . . . . . . . . . . 41
2.9.9 D’autres critères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.10 Traveaux connexes sur l’evaluation des algorithmes de clustering . . . . . . . 42
2.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
viii
TABLE OF CONTENTS
3 Implementation et Etude comparative 45
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Jeux des données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Prétraitement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.1 Analyse en composantes principales (ACP) . . . . . . . . . . . . . . . . 47
3.3.2 L’objectif de l’ACP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4.1 Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4.2 Jupyter Notebook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4.3 bibliothéques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5 Expérimentation et Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5.1 Regroupement par Partition . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5.2 Regroupement hiérarchique . . . . . . . . . . . . . . . . . . . . . . . . 55
3.5.3 Regroupement basé sur les graphes et partition . . . . . . . . . . . . . 59
3.5.4 Validation des Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Bibliographie 67Côte titre : MAI/0320 En ligne : https://drive.google.com/file/d/1aAlVs0xzXEk-jHEk4-Wz9JjU9-Fa1qw5/view?usp=shari [...] Format de la ressource électronique : Évaluation des performances des algorithmes clustering (Validation des algorithms) [texte imprimé] / Messai ,Dhaia eddine, Auteur ; Mediani ,chahrazed, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (67 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : clustering
Indices de validation
K-means
Birch
HCA
ARI
V-measure
CompletenessIndex. décimale : 004 - Informatique Résumé : La validation de clustering est un sujet de recherche très important qui intéresse beaucoup
de chercheurs en classification non supervisée des données, et c’est un axe de
recherche pas moins important que le clustering lui-même. Plusieurs indices de validation
de clustering ont été proposés dans la littérature.
Les travaux sur des méthodes de classification non supervisées, nous ont amené Ã
s’interroger sur la qualité des résultats. Le problème consiste à estimer si une méthode de
regroupement est «meilleure» qu’une autre pour un jeu particulier de données. Initialement,
après un état de l’art desméthodes existantes, nous avons appliqué certains de ces
méthodes comme k-means, HCA, ect., en choisissant des paramètres et des solutions
optimaux et les valider par des indices de qualité de clustering comme ARI, V-measure,
Completeness ... à l’aide de la bibliothéque scikit-learn de l’environnement python. Ces
indices de qualité nous ont permis de sélectionner le meilleure regroupement , qui est le
regroupement hiérarchique (HCA et Birch) pour notre jeu de données choisi.Note de contenu : Sommaire
Liste des tableaux xi
Table des figures xiii
1 Apprentissage automatique-Géneralité 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Pourquoi l’apprentissage automatique? . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Définition de l’apprentissage automatique . . . . . . . . . . . . . . . . . . . . 4
1.4 Déférents étapes pour création modèle apprentissage . . . . . . . . . . . . . . 4
1.4.1 Collection des données . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.2 Préparation des données . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.3 Entraîner un modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.4 Évaluation de modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Domaines de l’Apprentissage Automatique . . . . . . . . . . . . . . . . . . . . 5
1.5.1 Fouille des données (data mining) . . . . . . . . . . . . . . . . . . . . . 6
1.5.2 Intelligence artificielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Les techniques d’apprentissage automatique . . . . . . . . . . . . . . . . . . . 8
1.6.1 Apprentissage supervisé . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6.2 Apprentissage non supervisé . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Les algorithmes d’apprentissage automatique . . . . . . . . . . . . . . . . . . 11
1.7.1 Arbre de décision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.2 Support vecteur machine(SVM) . . . . . . . . . . . . . . . . . . . . . . 12
1.7.3 k-plus proche voisine . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.4 Naïve de bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Etat de l’art : Clustering et Validation de ses algorithmes 17
vii
TABLE OF CONTENTS
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Définition de clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1 Définition 1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Définition 2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Les objectives du clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Qu’est ce qu’un bon Clustering? . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 Les principales étapes du clustering . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.1 La préparation des données : . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.2 Le choix de l’algorithme de clustering : . . . . . . . . . . . . . . . . . . 21
2.5.3 Validation et l’exploitation des résultats de l’algorithme . . . . . . . . 22
2.6 Applications du Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6.1 La segmentation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6.2 Extraction des connaissances . . . . . . . . . . . . . . . . . . . . . . . . 23
2.7 Les différentes méthodes de clustering . . . . . . . . . . . . . . . . . . . . . . . 24
2.7.1 Clustering en partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.7.2 Clustering hiérarchique (Hierarchical Cluster Analysis) . . . . . . . . 28
2.7.3 clustering basée sur la densité . . . . . . . . . . . . . . . . . . . . . . . 32
2.7.4 clustering par grilles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.8 Clustering et Fonctions de similarité . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8.1 la distance Euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8.2 la distance deManhattan . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8.3 la distance deMinkowski . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.9 Les techniques d’évaluation de la qualité du clustering(validation) . . . . . . 37
2.9.1 Variance intra-classe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.9.2 Connectivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.9.3 L’indice de Davies-Bouldin . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.9.4 Précision-Rappel et F-mesure . . . . . . . . . . . . . . . . . . . . . . . 39
2.9.5 Coefficient de Jaccard . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.9.6 L’indice Rand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.9.7 Silhouette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.9.8 V-measure [Homogeneity et completeness] . . . . . . . . . . . . . . . 41
2.9.9 D’autres critères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.10 Traveaux connexes sur l’evaluation des algorithmes de clustering . . . . . . . 42
2.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
viii
TABLE OF CONTENTS
3 Implementation et Etude comparative 45
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Jeux des données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Prétraitement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.1 Analyse en composantes principales (ACP) . . . . . . . . . . . . . . . . 47
3.3.2 L’objectif de l’ACP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4.1 Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4.2 Jupyter Notebook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4.3 bibliothéques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5 Expérimentation et Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5.1 Regroupement par Partition . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5.2 Regroupement hiérarchique . . . . . . . . . . . . . . . . . . . . . . . . 55
3.5.3 Regroupement basé sur les graphes et partition . . . . . . . . . . . . . 59
3.5.4 Validation des Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Bibliographie 67Côte titre : MAI/0320 En ligne : https://drive.google.com/file/d/1aAlVs0xzXEk-jHEk4-Wz9JjU9-Fa1qw5/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0320 MAI/0320 Mémoire Bibliothéque des sciences Français Disponible
Disponible