University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Heraguemi kamel addine |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Approche bio-inspirée pour l’extraction des règles d’association Type de document : texte imprimé Auteurs : Heraguemi kamel addine, Auteur ; Habiba DRIAS, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (145 f .) Format : 29 cm Catégories : Informatique Mots-clés : bio-inspirée l’extraction des règles
d’associationRésumé : Résumé
L’extraction des règles d’association (ARM) peut être considérée comme un
problème combinatoire Dans le but d'extraire les corrélations entre les éléments dans des
ensembles de données considérables. Les nombreux algorithmes exacts polynômes déjÃ
proposés pour ARM deviennent inadapté aux grandes bases de données et surtout à ceux qui
existent sur le Web en raison au grand nombre de règles générées et aux exigences de temps.
Attendu que les utilisateurs ne peut pas exploiter toutes les règles obtenues par le processus
de recherche dans des algorithmes exhaustifs et ne peut pas perdre beaucoup de temps
lorsque la base de données augmente. Ainsi, la création de de nouveaux cadres et outils pour
la problématique ARM deviennent indispensables. Par conséquent, cette thèse de doctorat
propose plusieurs algorithmes pour la règle d'association minière à partir de données stockées
basées sur l'intelligence de l'essaim qui est un mécanisme moderne et efficace pour résoudre
des problèmes d'informatique, d'ingénierie, d'économie et d'optimisation, c'est un
comportement collectif de décentralisation et de système d'auto-organisation. Le point focal
de ce travail est consacré à l'algorithme Bat qui est développé récemment. BA a déjà prouvé
son efficacité et sa supériorité dans plusieurs champs d'application. Ici, nous proposons trois
propositions avancées basées sur l’algorithme bat pour découvrir le meilleur ensemble de
règles d'association à partir des données, L’algorithme Bat pour l'exploitation minière des
règles d'association minière, Algorithme coopératif multi-essaim pour ARM et algorithme
Bat multi-objectifs pour l'ARM.
Tous les algorithmes proposés dans cette thèse sont évalués à l'aide d'une série appropriée
d'expériences, en utilisant plusieurs ensembles de données bien connus dans le domaine
d’ARM et la performance de chaque approche proposée est évalué et comparé à ceux d'autres
méthodes récemment publiées. Les résultats montrent une nette supériorité de nos
propositions contre d'autres approches en termes du temps et de la qualité des règles.Note de contenu : Table of Contents
Declaration of Authorship iii
Abstract v
Acknowledgements vii
Table of Contents ix
List of Figures xiii
List of Tables xv
List of Algorithms xvii
Abbreviations xviii
1 Introduction 1
1.1 Goals and Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Thesis organization . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Background on Association Rule Mining 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Knowledge discovery in databases and Data mining . . . . . . . . . 8
2.2.1 Data Preprocessing . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Data mining . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.3 Post-mining phase in KDD . . . . . . . . . . . . . . . . . . . 13
2.3 Association rule mining . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Basics of association rule mining . . . . . . . . . . . . . . . . 14
2.3.2 Association rules measures . . . . . . . . . . . . . . . . . . . 19
2.3.3 Applications of AR . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Exhaustive Search algorithms for ARM . . . . . . . . . . . . . . . . 24
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Computational intelligence 37
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Artificial or Computational intelligence and soft computing . . . . . 38
3.3 Principal paradigms of computational intelligence . . . . . . . . . . 40
3.3.1 Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Fuzzy Systems . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.3 Evolutionary computing . . . . . . . . . . . . . . . . . . . . 43
3.3.4 Swarm intelligence . . . . . . . . . . . . . . . . . . . . . . . 45
3.4 Swarm intelligence algorithms instances . . . . . . . . . . . . . . . . 47
3.4.1 Ant Colony System Algorithm . . . . . . . . . . . . . . . . . 47
3.4.2 Particle Swarm Optimization Algorithm . . . . . . . . . . . 49
3.4.3 Bees Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4.4 Firefly Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.5 Cuckoo search . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.5 Computational intelligence algorithms for ARM . . . . . . . . . . . 56
3.5.1 Evolutionary algorithms for ARM . . . . . . . . . . . . . . . 58
3.5.2 Swarm intelligence algorithms for ARM . . . . . . . . . . . . 60
3.5.3 Multi-objective Proposals for ARM . . . . . . . . . . . . . . 62
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4 Bat Algorithm: An Overview 67
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Natural Bat behavior . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3 Original Bat algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.4 Variants of Bat algorithm . . . . . . . . . . . . . . . . . . . . . . . 71
4.4.1 Multi-swarm bat algorithm . . . . . . . . . . . . . . . . . . . 71
4.4.2 Bat Algorithm for Multi-objective Optimization . . . . . . . 72
4.4.3 Other variants of bat algorithm . . . . . . . . . . . . . . . . 74
4.5 Bat algorithm applications . . . . . . . . . . . . . . . . . . . . . . . 76
4.5.1 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.5.2 Data mining . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.5.3 Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5 Bat algorithm for ARM 81
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2 The BAT-ARM algorithm . . . . . . . . . . . . . . . . . . . . . . . 82
5.2.1 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.2.2 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2.3 Virtual Bat Motion . . . . . . . . . . . . . . . . . . . . . . . 83
5.2.4 Complexity of BAT-ARM . . . . . . . . . . . . . . . . . . . 84
5.3 Analysis and comparative study . . . . . . . . . . . . . . . . . . . . 85
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.5 Publications Associated with this Chapter . . . . . . . . . . . . . . 89
6 Multi-swarm Cooperative Bat Algorithm for ARM 91
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2 The MSB-BAT algorithm . . . . . . . . . . . . . . . . . . . . . . . 92
6.2.1 Dataset representation and Rule encoding . . . . . . . . . . 92
6.2.2 Cooperative strategies in multi-swarm bat algorithm for ARM 92
6.2.2.1 Ring strategy . . . . . . . . . . . . . . . . . . . . . 93
6.2.2.2 Master-Slave strategy . . . . . . . . . . . . . . . . 93
6.2.2.3 Hybrid strategy . . . . . . . . . . . . . . . . . . . . 95
6.3 Experimental Study . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.3.1 Datasets description . . . . . . . . . . . . . . . . . . . . . . 96
6.3.2 Experimental Set-up . . . . . . . . . . . . . . . . . . . . . . 98
6.3.3 Analysis and comparison . . . . . . . . . . . . . . . . . . . . 98
6.3.3.1 Stability analysis . . . . . . . . . . . . . . . . . . . 98
6.3.3.2 Comparative study to similar approaches . . . . . . 99
6.3.3.3 Comparative study to multi-objective optimization approaches . . . . . . . . . . . . . . . . .. . 104
6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.5 Publications Associated with this Chapter . . . . . . . . . . . . . . 107
7 Multi-objective bat algorithm for ARM 109
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.2 The MOB-ARM algorithm . . . . . . . . . . . . . . . . . . . . . . . 110
7.2.1 Databases layout and rule representation . . . . . . . . . . . 110
7.2.2 Rule encoding . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.2.3 Objective Functions . . . . . . . . . . . . . . . . . . . . . . 112
7.2.4 The algorithm flow . . . . . . . . . . . . . . . . . . . . . . . 113
7.3 Experimentation and results . . . . . . . . . . . . . . . . . . . . . . 114
7.3.1 Benchmark and setup description . . . . . . . . . . . . . . . 115
7.3.2 Stability analysis . . . . . . . . . . . . . . . . . . . . . . . . 116
7.3.3 Comparative study to single objective approaches . . . . . . 117
7.3.4 Comparative study to multi-objective approaches . . . . . . 118
7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.5 Publications Associated with this Chapter . . . . . . . . . . . . . . 123
8 Conclusion and future work 125
8.0.1 Future Work and Perspectives . . . . . . . . . . . . . . . . . 126
Bibliography 129Côte titre : DI/0026 En ligne : https://drive.google.com/file/d/1abzHe_6gU2YrehAIhlQOqEu8P2V5K7j2/view?usp=shari [...] Format de la ressource électronique : Approche bio-inspirée pour l’extraction des règles d’association [texte imprimé] / Heraguemi kamel addine, Auteur ; Habiba DRIAS, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (145 f .) ; 29 cm.
Catégories : Informatique Mots-clés : bio-inspirée l’extraction des règles
d’associationRésumé : Résumé
L’extraction des règles d’association (ARM) peut être considérée comme un
problème combinatoire Dans le but d'extraire les corrélations entre les éléments dans des
ensembles de données considérables. Les nombreux algorithmes exacts polynômes déjÃ
proposés pour ARM deviennent inadapté aux grandes bases de données et surtout à ceux qui
existent sur le Web en raison au grand nombre de règles générées et aux exigences de temps.
Attendu que les utilisateurs ne peut pas exploiter toutes les règles obtenues par le processus
de recherche dans des algorithmes exhaustifs et ne peut pas perdre beaucoup de temps
lorsque la base de données augmente. Ainsi, la création de de nouveaux cadres et outils pour
la problématique ARM deviennent indispensables. Par conséquent, cette thèse de doctorat
propose plusieurs algorithmes pour la règle d'association minière à partir de données stockées
basées sur l'intelligence de l'essaim qui est un mécanisme moderne et efficace pour résoudre
des problèmes d'informatique, d'ingénierie, d'économie et d'optimisation, c'est un
comportement collectif de décentralisation et de système d'auto-organisation. Le point focal
de ce travail est consacré à l'algorithme Bat qui est développé récemment. BA a déjà prouvé
son efficacité et sa supériorité dans plusieurs champs d'application. Ici, nous proposons trois
propositions avancées basées sur l’algorithme bat pour découvrir le meilleur ensemble de
règles d'association à partir des données, L’algorithme Bat pour l'exploitation minière des
règles d'association minière, Algorithme coopératif multi-essaim pour ARM et algorithme
Bat multi-objectifs pour l'ARM.
Tous les algorithmes proposés dans cette thèse sont évalués à l'aide d'une série appropriée
d'expériences, en utilisant plusieurs ensembles de données bien connus dans le domaine
d’ARM et la performance de chaque approche proposée est évalué et comparé à ceux d'autres
méthodes récemment publiées. Les résultats montrent une nette supériorité de nos
propositions contre d'autres approches en termes du temps et de la qualité des règles.Note de contenu : Table of Contents
Declaration of Authorship iii
Abstract v
Acknowledgements vii
Table of Contents ix
List of Figures xiii
List of Tables xv
List of Algorithms xvii
Abbreviations xviii
1 Introduction 1
1.1 Goals and Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Thesis organization . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Background on Association Rule Mining 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Knowledge discovery in databases and Data mining . . . . . . . . . 8
2.2.1 Data Preprocessing . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Data mining . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.3 Post-mining phase in KDD . . . . . . . . . . . . . . . . . . . 13
2.3 Association rule mining . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Basics of association rule mining . . . . . . . . . . . . . . . . 14
2.3.2 Association rules measures . . . . . . . . . . . . . . . . . . . 19
2.3.3 Applications of AR . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Exhaustive Search algorithms for ARM . . . . . . . . . . . . . . . . 24
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Computational intelligence 37
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Artificial or Computational intelligence and soft computing . . . . . 38
3.3 Principal paradigms of computational intelligence . . . . . . . . . . 40
3.3.1 Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Fuzzy Systems . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.3 Evolutionary computing . . . . . . . . . . . . . . . . . . . . 43
3.3.4 Swarm intelligence . . . . . . . . . . . . . . . . . . . . . . . 45
3.4 Swarm intelligence algorithms instances . . . . . . . . . . . . . . . . 47
3.4.1 Ant Colony System Algorithm . . . . . . . . . . . . . . . . . 47
3.4.2 Particle Swarm Optimization Algorithm . . . . . . . . . . . 49
3.4.3 Bees Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4.4 Firefly Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.5 Cuckoo search . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.5 Computational intelligence algorithms for ARM . . . . . . . . . . . 56
3.5.1 Evolutionary algorithms for ARM . . . . . . . . . . . . . . . 58
3.5.2 Swarm intelligence algorithms for ARM . . . . . . . . . . . . 60
3.5.3 Multi-objective Proposals for ARM . . . . . . . . . . . . . . 62
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4 Bat Algorithm: An Overview 67
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Natural Bat behavior . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3 Original Bat algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.4 Variants of Bat algorithm . . . . . . . . . . . . . . . . . . . . . . . 71
4.4.1 Multi-swarm bat algorithm . . . . . . . . . . . . . . . . . . . 71
4.4.2 Bat Algorithm for Multi-objective Optimization . . . . . . . 72
4.4.3 Other variants of bat algorithm . . . . . . . . . . . . . . . . 74
4.5 Bat algorithm applications . . . . . . . . . . . . . . . . . . . . . . . 76
4.5.1 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.5.2 Data mining . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.5.3 Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5 Bat algorithm for ARM 81
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2 The BAT-ARM algorithm . . . . . . . . . . . . . . . . . . . . . . . 82
5.2.1 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.2.2 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2.3 Virtual Bat Motion . . . . . . . . . . . . . . . . . . . . . . . 83
5.2.4 Complexity of BAT-ARM . . . . . . . . . . . . . . . . . . . 84
5.3 Analysis and comparative study . . . . . . . . . . . . . . . . . . . . 85
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.5 Publications Associated with this Chapter . . . . . . . . . . . . . . 89
6 Multi-swarm Cooperative Bat Algorithm for ARM 91
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2 The MSB-BAT algorithm . . . . . . . . . . . . . . . . . . . . . . . 92
6.2.1 Dataset representation and Rule encoding . . . . . . . . . . 92
6.2.2 Cooperative strategies in multi-swarm bat algorithm for ARM 92
6.2.2.1 Ring strategy . . . . . . . . . . . . . . . . . . . . . 93
6.2.2.2 Master-Slave strategy . . . . . . . . . . . . . . . . 93
6.2.2.3 Hybrid strategy . . . . . . . . . . . . . . . . . . . . 95
6.3 Experimental Study . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.3.1 Datasets description . . . . . . . . . . . . . . . . . . . . . . 96
6.3.2 Experimental Set-up . . . . . . . . . . . . . . . . . . . . . . 98
6.3.3 Analysis and comparison . . . . . . . . . . . . . . . . . . . . 98
6.3.3.1 Stability analysis . . . . . . . . . . . . . . . . . . . 98
6.3.3.2 Comparative study to similar approaches . . . . . . 99
6.3.3.3 Comparative study to multi-objective optimization approaches . . . . . . . . . . . . . . . . .. . 104
6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.5 Publications Associated with this Chapter . . . . . . . . . . . . . . 107
7 Multi-objective bat algorithm for ARM 109
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.2 The MOB-ARM algorithm . . . . . . . . . . . . . . . . . . . . . . . 110
7.2.1 Databases layout and rule representation . . . . . . . . . . . 110
7.2.2 Rule encoding . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.2.3 Objective Functions . . . . . . . . . . . . . . . . . . . . . . 112
7.2.4 The algorithm flow . . . . . . . . . . . . . . . . . . . . . . . 113
7.3 Experimentation and results . . . . . . . . . . . . . . . . . . . . . . 114
7.3.1 Benchmark and setup description . . . . . . . . . . . . . . . 115
7.3.2 Stability analysis . . . . . . . . . . . . . . . . . . . . . . . . 116
7.3.3 Comparative study to single objective approaches . . . . . . 117
7.3.4 Comparative study to multi-objective approaches . . . . . . 118
7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.5 Publications Associated with this Chapter . . . . . . . . . . . . . . 123
8 Conclusion and future work 125
8.0.1 Future Work and Perspectives . . . . . . . . . . . . . . . . . 126
Bibliography 129Côte titre : DI/0026 En ligne : https://drive.google.com/file/d/1abzHe_6gU2YrehAIhlQOqEu8P2V5K7j2/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DI/0026 DI/0026 Thèse Bibliothéque des sciences Français Disponible
Disponible
