University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur LEGRIB, Med El-Amine |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Clustering algorithm using K-means and Cuckoo Search Type de document : texte imprimé Auteurs : LEGRIB, Med El-Amine ; KAMEL, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2015 Importance : 1 vol (49f.) Format : 29 cm Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Cluster,clustering data,k-means,cuckoo search,metaheuristics,datamining,
Knowledge Discovery.Index. décimale : 004 Informatique Résumé : Abstract
Cluster analysis comprises a range of methods for classifying multivariate data into
subgroups. By organizing multivariate data into such subgroups, clustering can help
reveal the characteristics of any structure or patterns present. These techniques have
proven useful in a wide range of areas such as medicine, psychology, market research
and bioinformatics. in this thesis we will take a look on many clustering algorithms
and implement our solution for clustering data using k-means and cuckoo search algorithms evaluate the result of our work using the benchmark of various dataset proposed
in UC Irvine Machine Learning Repository ,result showed a good k-means algorithm
initialization
Note de contenu : Contents
Dedication 1
abstract 2
Introduction 6
1 DATA Mining 8
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Etymology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Definition DATA MINIG . . . . . . . . . . . . . . . . . . . 8
1.3.2 Definition KNOWLEDGE Discovery in Databases . . . . . . 9
1.3.3 Definition machine learning . . . . . . . . . . . . . . . . . . 9
1.3.3.1 Leaning style . . . . . . . . . . . . . . . . . . . . 10
1.3.3.1.1 Supervised Learning: . . . . . . . . . . . 10
1.3.3.1.2 Unsupervised Learning . . . . . . . . . . 10
1.3.3.1.3 Semi-Supervised Learning . . . . . . . . 10
1.3.3.1.4 Reinforcement Learning: . . . . . . . . . 10
1.4 data mining tasks [Kan11] . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Predictive Method . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.2 Description Method . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Types of Data Mining System . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 Classification of data mining systems according to the type of
data source mined . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.2 Classification of data mining systems according to the data model 11
1.5.3 Classification of data mining systems according to the kind of
knowledge discovered . . . . . . . . . . . . . . . . . . . . . 12
1.5.4 Classification of data mining systems according to mining techniques used . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Data Mining in the real world [UGP96] . . . . . . . . . . . . . . . . 12
1.6.1 Finance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.2 Telecommunication . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.3 Biological Data Analysis . . . . . . . . . . . . . . . . . . . . 12
1.6.4 Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . 13
1.7 Clustering and classification . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1.1 The decision tree . . . . . . . . . . . . . . . . . . . 13
1.7.2 cluster and Clustering . . . . . . . . . . . . . . . . . . . . . 13
1.7.3 Reasons of clustering . . . . . . . . . . . . . . . . . . . . . . 13
1.7.4 application of cluster analysis . . . . . . . . . . . . . . . . . 14
1.7.4.1 market Research . . . . . . . . . . . . . . . . . . 14
1.7.4.2 Astronomy . . . . . . . . . . . . . . . . . . . . . . 14
1.7.4.3 psychology . . . . . . . . . . . . . . . . . . . . . . 14
1.7.4.4 Weather classification . . . . . . . . . . . . . . . . 14
1.7.4.5 Archeology . . . . . . . . . . . . . . . . . . . . . 14
1.7.5 Data type in cluster analysis . . . . . . . . . . . . . . . . . . 14
1.7.5.1 Clustering categorical Data . . . . . . . . . . . . . 14
1.7.5.2 Clustering Text Data . . . . . . . . . . . . . . . . 15
1.7.5.3 Clustring multimedia data . . . . . . . . . . . . . 15
1.7.5.4 Clustering time-series data . . . . . . . . . . . . . 15
1.7.6 Distances and similarities . . . . . . . . . . . . . . . . . . . 16
1.7.7 Clustering algorithms . . . . . . . . . . . . . . . . . . . . . 16
1.7.7.1 The hierarchical clustering . . . . . . . . . . . . . 16
1.7.7.1.1 Agglomerative and divisive methods . . . 17
1.7.7.1.2 BIRCH ALGORITHEM [TzRr96] . . . . 18
1.7.7.2 The partitional clustering . . . . . . . . . . . . . . 19
1.7.7.2.1 The Heuristics methods . . . . . . . . . . 20
1.7.7.2.1.1 K-means . . . . . . . . . . . . . . 20
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 MetaHeuristics 22
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Etymology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Deintion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Metaheuristics for Clustering . . . . . . . . . . . . . . . . . . . . . . 23
2.5.1 Clustering by evolutionary algorithms . . . . . . . . . . . . . 23
2.5.2 Clustering by artificial ants . . . . . . . . . . . . . . . . . . . 26
2.5.3 Clustering particle swarm . . . . . . . . . . . . . . . . . . . 27
2.5.4 Clustering by artificial immune system . . . . . . . . . . . . 28
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Meta-heuristics+K-means 30
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 K-Means and firefly . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 K-Means and PSO . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 Integrating Nature-inspired Optimization Algorithms to K-means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.5 Firefly and k-means in image processing . . . . . . . . . . . . . . . . 36
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4 implementation 38
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 Our approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3.1 Iris Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.1.1 Data Set Information . . . . . . . . . . . . . . . . 39
4.3.2 Wine Data Set . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.2.1 Data Set Information . . . . . . . . . . . . . . . . 39
4.3.3 Poker Hand Data Set . . . . . . . . . . . . . . . . . . . . . . 39
4.3.4 datasets uses . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Algorithm k-means/cuckoo-search . . . . . . . . . . . . . . . . . . . 40
4.5 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.1 Hardware used . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.2 Software used . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.3 Software manual guide . . . . . . . . . . . . . . . . . . . . . 41
4.5.3.1 Cluster validity . . . . . . . . . . . . . . . . . . . 42
4.5.3.2 Clusters . . . . . . . . . . . . . . . . . . . . . . . 42
4.5.4 Screen shot . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6 Results and evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6.1 Compactness intra-cluster . . . . . . . . . . . . . . . . . . . 44
4.6.2 Separation inter-cluster . . . . . . . . . . . . . . . . . . . . . 44
4.6.3 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.7 Decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.8 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
General conclusion 46
References 49Côte titre : MAI/0080 En ligne : https://drive.google.com/file/d/1y8oDElqZXLYljFg0uiN0Fl4Et9sDZYJ4/view?usp=shari [...] Format de la ressource électronique : Clustering algorithm using K-means and Cuckoo Search [texte imprimé] / LEGRIB, Med El-Amine ; KAMEL, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2015 . - 1 vol (49f.) ; 29 cm.
Langues : Anglais (eng)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Cluster,clustering data,k-means,cuckoo search,metaheuristics,datamining,
Knowledge Discovery.Index. décimale : 004 Informatique Résumé : Abstract
Cluster analysis comprises a range of methods for classifying multivariate data into
subgroups. By organizing multivariate data into such subgroups, clustering can help
reveal the characteristics of any structure or patterns present. These techniques have
proven useful in a wide range of areas such as medicine, psychology, market research
and bioinformatics. in this thesis we will take a look on many clustering algorithms
and implement our solution for clustering data using k-means and cuckoo search algorithms evaluate the result of our work using the benchmark of various dataset proposed
in UC Irvine Machine Learning Repository ,result showed a good k-means algorithm
initialization
Note de contenu : Contents
Dedication 1
abstract 2
Introduction 6
1 DATA Mining 8
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Etymology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Definition DATA MINIG . . . . . . . . . . . . . . . . . . . 8
1.3.2 Definition KNOWLEDGE Discovery in Databases . . . . . . 9
1.3.3 Definition machine learning . . . . . . . . . . . . . . . . . . 9
1.3.3.1 Leaning style . . . . . . . . . . . . . . . . . . . . 10
1.3.3.1.1 Supervised Learning: . . . . . . . . . . . 10
1.3.3.1.2 Unsupervised Learning . . . . . . . . . . 10
1.3.3.1.3 Semi-Supervised Learning . . . . . . . . 10
1.3.3.1.4 Reinforcement Learning: . . . . . . . . . 10
1.4 data mining tasks [Kan11] . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Predictive Method . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.2 Description Method . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Types of Data Mining System . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 Classification of data mining systems according to the type of
data source mined . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.2 Classification of data mining systems according to the data model 11
1.5.3 Classification of data mining systems according to the kind of
knowledge discovered . . . . . . . . . . . . . . . . . . . . . 12
1.5.4 Classification of data mining systems according to mining techniques used . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Data Mining in the real world [UGP96] . . . . . . . . . . . . . . . . 12
1.6.1 Finance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.2 Telecommunication . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.3 Biological Data Analysis . . . . . . . . . . . . . . . . . . . . 12
1.6.4 Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . 13
1.7 Clustering and classification . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1.1 The decision tree . . . . . . . . . . . . . . . . . . . 13
1.7.2 cluster and Clustering . . . . . . . . . . . . . . . . . . . . . 13
1.7.3 Reasons of clustering . . . . . . . . . . . . . . . . . . . . . . 13
1.7.4 application of cluster analysis . . . . . . . . . . . . . . . . . 14
1.7.4.1 market Research . . . . . . . . . . . . . . . . . . 14
1.7.4.2 Astronomy . . . . . . . . . . . . . . . . . . . . . . 14
1.7.4.3 psychology . . . . . . . . . . . . . . . . . . . . . . 14
1.7.4.4 Weather classification . . . . . . . . . . . . . . . . 14
1.7.4.5 Archeology . . . . . . . . . . . . . . . . . . . . . 14
1.7.5 Data type in cluster analysis . . . . . . . . . . . . . . . . . . 14
1.7.5.1 Clustering categorical Data . . . . . . . . . . . . . 14
1.7.5.2 Clustering Text Data . . . . . . . . . . . . . . . . 15
1.7.5.3 Clustring multimedia data . . . . . . . . . . . . . 15
1.7.5.4 Clustering time-series data . . . . . . . . . . . . . 15
1.7.6 Distances and similarities . . . . . . . . . . . . . . . . . . . 16
1.7.7 Clustering algorithms . . . . . . . . . . . . . . . . . . . . . 16
1.7.7.1 The hierarchical clustering . . . . . . . . . . . . . 16
1.7.7.1.1 Agglomerative and divisive methods . . . 17
1.7.7.1.2 BIRCH ALGORITHEM [TzRr96] . . . . 18
1.7.7.2 The partitional clustering . . . . . . . . . . . . . . 19
1.7.7.2.1 The Heuristics methods . . . . . . . . . . 20
1.7.7.2.1.1 K-means . . . . . . . . . . . . . . 20
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 MetaHeuristics 22
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Etymology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Deintion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Metaheuristics for Clustering . . . . . . . . . . . . . . . . . . . . . . 23
2.5.1 Clustering by evolutionary algorithms . . . . . . . . . . . . . 23
2.5.2 Clustering by artificial ants . . . . . . . . . . . . . . . . . . . 26
2.5.3 Clustering particle swarm . . . . . . . . . . . . . . . . . . . 27
2.5.4 Clustering by artificial immune system . . . . . . . . . . . . 28
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Meta-heuristics+K-means 30
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 K-Means and firefly . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 K-Means and PSO . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 Integrating Nature-inspired Optimization Algorithms to K-means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.5 Firefly and k-means in image processing . . . . . . . . . . . . . . . . 36
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4 implementation 38
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 Our approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3.1 Iris Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.1.1 Data Set Information . . . . . . . . . . . . . . . . 39
4.3.2 Wine Data Set . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.2.1 Data Set Information . . . . . . . . . . . . . . . . 39
4.3.3 Poker Hand Data Set . . . . . . . . . . . . . . . . . . . . . . 39
4.3.4 datasets uses . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Algorithm k-means/cuckoo-search . . . . . . . . . . . . . . . . . . . 40
4.5 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.1 Hardware used . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.2 Software used . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5.3 Software manual guide . . . . . . . . . . . . . . . . . . . . . 41
4.5.3.1 Cluster validity . . . . . . . . . . . . . . . . . . . 42
4.5.3.2 Clusters . . . . . . . . . . . . . . . . . . . . . . . 42
4.5.4 Screen shot . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6 Results and evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6.1 Compactness intra-cluster . . . . . . . . . . . . . . . . . . . 44
4.6.2 Separation inter-cluster . . . . . . . . . . . . . . . . . . . . . 44
4.6.3 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.7 Decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.8 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
General conclusion 46
References 49Côte titre : MAI/0080 En ligne : https://drive.google.com/file/d/1y8oDElqZXLYljFg0uiN0Fl4Et9sDZYJ4/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0080 MAI/0080 Mémoire Bibliothéque des sciences Anglais Disponible
Disponible
