|
| Titre : |
Fouille de données basée algorithmes bio-inspirés |
| Type de document : |
texte imprimé |
| Auteurs : |
ZOUACHE, Djaafar, Auteur ; Abdelouahab Moussaoui, Directeur de thèse |
| Editeur : |
Setif:UFA |
| Année de publication : |
2016 |
| Importance : |
1 vol (98 f .) |
| Format : |
29 cm |
| Catégories : |
Informatique
|
| Mots-clés : |
Fouille de données Informatique quantique algorithme de luciole Optimisation par essaime de particules Sélection d’attributs Problème
d’optimisation discrète Problème du sac à dos |
| Résumé : |
Résumé
L’extraction de connaissances dans les bases de données, également appelé
“data mining”, désigne le processus de découverte des informations et des
connaissances utiles, nouvelles et compréhensibles à partir d’une base de
données de grande taille, d’un entrepôt de données ou d’autres bases. La
majorité des problèmes d’extraction de connaissances peuvent s’exprimer comme
des problèmes d’optimisation combinatoire. Par conséquent, nous avons besoin
d’une approche fondamentale différente des approches d’extraction exactes
classiques. Cette approche est basée sur l’inspiration des idées et des intuitions à
partir de la nature et de la vie (biologique, physique, etc.) pour résoudre les
problèmes d’extraction de connaissances.
Notre contribution est faite en deux phases : La première phase consiste à
concevoir des méta-heuristiques bio-inspirés pour résoudre des problèmes
d’optimisation combinatoire d’une manière générale et la deuxième phase
consiste à réaliser et d’appliquer ces méta-heuristiques proposées aux problèmes
d’extraction de connaissances.
Dans la première phase, nous avons proposé deux algorithmes bio-inspirés,
le premier algorithme appelé QDEPSO hybride entre le DE et le PSO. Le
deuxième algorithme appelé QIFAPSO fait coopérer le firefly algorithm et le
PSO. Les deux algorithmes utilisent les concepts de l’informatique quantique.
Dans la deuxième phase, nous avons appliqué l’algorithme QIFAPSO pour
résoudre le problème de la sélection d’attributs.
Une évaluation expérimentale approfondie sur les différents jeux de
données disponibles dans la littérature montre que les algorithmes développés
sont performants et concurrents en terme de qualité de solutions comparant avec
d’autres algorithmes qu’ont été développés pour résoudre des problèmes
d’optimisation combinatoire ou bien dans la résolution de problème de la
sélection d’attributs.
|
| Note de contenu : |
Contents
1 Introduction 1
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Data mining and optimization . . . . . . . . . . . . . . . . . . 1
1.1.2 Metaheuristics methods for discrete optimization . . . . . . . 2
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Majors contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Thesis organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Academic publications and communication produced . . . . . . . . 8
2 Bio-inspired algorithms for feature selection in classification 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Bio-inspired algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Quantum inspired computation . . . . . . . . . . . . . . . . . 10
2.2.2 Particle swarm optimization method . . . . . . . . . . . . . . . 11
2.2.3 Differential Evolution . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.4 Firefly algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Feature selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Feature selection process . . . . . . . . . . . . . . . . . . . . . . 16
2.3.3 Classification of feature selection approaches . . . . . . . . . 17
2.4 Entropy, mutual information . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Basic notions on Rough set theory . . . . . . . . . . . . . . . . . . . . 19
2.6 Background of approaches for feature selection . . . . . . . . . . . . . 21
2.6.1 Mutual information based approach . . . . . . . . . . . . . . . 21
2.6.2 Rough set based approaches . . . . . . . . . . . . . . . . . . . 21
2.6.3 Metaheuristics approaches based on rough set for feature selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.7 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 QDEPSO for Knapsack Problem 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 The proposed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.1 Binary representation of items selection . . . . . . . . . . . . . 29
3.3.2 Quantum representation . . . . . . . . . . . . . . . . . . . . . . 29
3.3.3 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.4 Quantum observation . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.5 Mutation operation . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.6 Crossover operation . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.7 Selection operation . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.8 Quantum rotation gate . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.9 Adaptation of the PSO formula . . . . . . . . . . . . . . . . . . 32
3.3.10 Outlines of QDEPSO algorithm . . . . . . . . . . . . . . . . . 33
3.4 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.5 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4 QIFAPSO for discrete optimization problems 43
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 0–1 multidimensional knapsack problem: overview and related work 44
4.3 The proposed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3.1 Binary representation of fireflies . . . . . . . . . . . . . . . . . 46
4.3.2 Quantum representation of fireflies . . . . . . . . . . . . . . . 48
4.3.3 Initialization of quantum fireflies’ population . . . . . . . . . 48
4.3.4 Quantum measure . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.5 Distance between two binary fireflies . . . . . . . . . . . . . . 49
4.3.6 Quantum movement according to the firefly algorithm strategy 51
4.3.7 Quantum movement according to the PSO strategy . . . . . . 53
4.3.8 QIFAPSO algorithm . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4.1 0-1 Simple Knapsack Problem . . . . . . . . . . . . . . . . . . . 54
4.4.2 Multidimensional Knapsack Problem . . . . . . . . . . . . . . 56
4.5 Conclusion and perspectives . . . . . . . . . . . . . . . . . . . . . . . 65
5 Quantum inspired firefly algorithm for feature selection 67
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2 QIFAPSO for feature selection . . . . . . . . . . . . . . . . . . . . . . . 68
5.2.1 Quantum representation for feature selection . . . . . . . . . . 68
5.2.2 Construction of feasible solution by Quantum observation . . 69
5.2.3 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.2.4 The distance and attractiveness between two fireflies’ solutions 70
5.2.5 Quantum movements for updating the fireflies’ solutions . . 72
5.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.4 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6 Conclusions and Future works 83
6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Bibliography 87 |
| Côte titre : |
DI/0020 |
| En ligne : |
https://drive.google.com/file/d/1asHbMhrknzzhu9MJtNiU_6GXXLNbKEdc/view?usp=shari [...] |
| Format de la ressource électronique : |
pdf |
Fouille de données basée algorithmes bio-inspirés [texte imprimé] / ZOUACHE, Djaafar, Auteur ; Abdelouahab Moussaoui, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (98 f .) ; 29 cm.
| Catégories : |
Informatique
|
| Mots-clés : |
Fouille de données Informatique quantique algorithme de luciole Optimisation par essaime de particules Sélection d’attributs Problème
d’optimisation discrète Problème du sac à dos |
| Résumé : |
Résumé
L’extraction de connaissances dans les bases de données, également appelé
“data mining”, désigne le processus de découverte des informations et des
connaissances utiles, nouvelles et compréhensibles à partir d’une base de
données de grande taille, d’un entrepôt de données ou d’autres bases. La
majorité des problèmes d’extraction de connaissances peuvent s’exprimer comme
des problèmes d’optimisation combinatoire. Par conséquent, nous avons besoin
d’une approche fondamentale différente des approches d’extraction exactes
classiques. Cette approche est basée sur l’inspiration des idées et des intuitions à
partir de la nature et de la vie (biologique, physique, etc.) pour résoudre les
problèmes d’extraction de connaissances.
Notre contribution est faite en deux phases : La première phase consiste à
concevoir des méta-heuristiques bio-inspirés pour résoudre des problèmes
d’optimisation combinatoire d’une manière générale et la deuxième phase
consiste à réaliser et d’appliquer ces méta-heuristiques proposées aux problèmes
d’extraction de connaissances.
Dans la première phase, nous avons proposé deux algorithmes bio-inspirés,
le premier algorithme appelé QDEPSO hybride entre le DE et le PSO. Le
deuxième algorithme appelé QIFAPSO fait coopérer le firefly algorithm et le
PSO. Les deux algorithmes utilisent les concepts de l’informatique quantique.
Dans la deuxième phase, nous avons appliqué l’algorithme QIFAPSO pour
résoudre le problème de la sélection d’attributs.
Une évaluation expérimentale approfondie sur les différents jeux de
données disponibles dans la littérature montre que les algorithmes développés
sont performants et concurrents en terme de qualité de solutions comparant avec
d’autres algorithmes qu’ont été développés pour résoudre des problèmes
d’optimisation combinatoire ou bien dans la résolution de problème de la
sélection d’attributs.
|
| Note de contenu : |
Contents
1 Introduction 1
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Data mining and optimization . . . . . . . . . . . . . . . . . . 1
1.1.2 Metaheuristics methods for discrete optimization . . . . . . . 2
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Majors contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Thesis organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Academic publications and communication produced . . . . . . . . 8
2 Bio-inspired algorithms for feature selection in classification 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Bio-inspired algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Quantum inspired computation . . . . . . . . . . . . . . . . . 10
2.2.2 Particle swarm optimization method . . . . . . . . . . . . . . . 11
2.2.3 Differential Evolution . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.4 Firefly algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Feature selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Feature selection process . . . . . . . . . . . . . . . . . . . . . . 16
2.3.3 Classification of feature selection approaches . . . . . . . . . 17
2.4 Entropy, mutual information . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Basic notions on Rough set theory . . . . . . . . . . . . . . . . . . . . 19
2.6 Background of approaches for feature selection . . . . . . . . . . . . . 21
2.6.1 Mutual information based approach . . . . . . . . . . . . . . . 21
2.6.2 Rough set based approaches . . . . . . . . . . . . . . . . . . . 21
2.6.3 Metaheuristics approaches based on rough set for feature selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.7 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 QDEPSO for Knapsack Problem 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 The proposed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.1 Binary representation of items selection . . . . . . . . . . . . . 29
3.3.2 Quantum representation . . . . . . . . . . . . . . . . . . . . . . 29
3.3.3 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.4 Quantum observation . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.5 Mutation operation . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.6 Crossover operation . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.7 Selection operation . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.8 Quantum rotation gate . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.9 Adaptation of the PSO formula . . . . . . . . . . . . . . . . . . 32
3.3.10 Outlines of QDEPSO algorithm . . . . . . . . . . . . . . . . . 33
3.4 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.5 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4 QIFAPSO for discrete optimization problems 43
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 0–1 multidimensional knapsack problem: overview and related work 44
4.3 The proposed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3.1 Binary representation of fireflies . . . . . . . . . . . . . . . . . 46
4.3.2 Quantum representation of fireflies . . . . . . . . . . . . . . . 48
4.3.3 Initialization of quantum fireflies’ population . . . . . . . . . 48
4.3.4 Quantum measure . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.5 Distance between two binary fireflies . . . . . . . . . . . . . . 49
4.3.6 Quantum movement according to the firefly algorithm strategy 51
4.3.7 Quantum movement according to the PSO strategy . . . . . . 53
4.3.8 QIFAPSO algorithm . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4.1 0-1 Simple Knapsack Problem . . . . . . . . . . . . . . . . . . . 54
4.4.2 Multidimensional Knapsack Problem . . . . . . . . . . . . . . 56
4.5 Conclusion and perspectives . . . . . . . . . . . . . . . . . . . . . . . 65
5 Quantum inspired firefly algorithm for feature selection 67
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2 QIFAPSO for feature selection . . . . . . . . . . . . . . . . . . . . . . . 68
5.2.1 Quantum representation for feature selection . . . . . . . . . . 68
5.2.2 Construction of feasible solution by Quantum observation . . 69
5.2.3 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.2.4 The distance and attractiveness between two fireflies’ solutions 70
5.2.5 Quantum movements for updating the fireflies’ solutions . . 72
5.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.4 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6 Conclusions and Future works 83
6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Bibliography 87 |
| Côte titre : |
DI/0020 |
| En ligne : |
https://drive.google.com/file/d/1asHbMhrknzzhu9MJtNiU_6GXXLNbKEdc/view?usp=shari [...] |
| Format de la ressource électronique : |
pdf |
|
Ajouter le résultat dans votre panier Affiner la recherche
