| Titre : | Utilisation des méthodes support vector machine (SVM) dans l'analyse des basse de données |
| Auteurs : | Abdelhamid Djeffal, Auteur ; Mohamed Chaouki Babahenini, Directeur de thèse |
| Type de document : | Thése doctorat |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2012 |
| ISBN/ISSN/EAN : | TINF/53 |
| Format : | 1 vol. (118 p.) / ill. / 29 cm |
| Langues: | Français |
| Résumé : |
Le data mining est une discipline en pleine expansion qui vise l’extraction des connaissances pertinentes des grandes quantités de données. Elle utilise des outils provenant des statistiques,de l’intelligence artificielle, et des techniques d’optimisation, ...etc. Le data mining vient même d’être intégré dans des grands systèmes de gestion de bases de données tel que Oracle.La technique des machines à vecteurs supports (SVM) est une méthode d’apprentissage statistique qui a connu, cette dernière décennie, un grand développement en théorie et en application.Elle repose sur un fondement théorique solide basé sur le principe de maximisation de la marge, ce qui lui confie une grande capacité de généralisation. Les SVMs ont été utilisées avec succès dans plusieurs domaines tels que la reconnaissance des visages, des textes manuscrits, de la parole,...etc.Dans ce travail, nous avons traité la question de l’utilisation de la méthode SVM pour l’analyse des bases de données. En effet, Le processus d’analyse passe par plusieurs étapes, dans chacune,les données subissent des traitements qui peuvent être optimisés par l’utilisation de la méthode SVM. L’objectif de cette thèse est d’étudier les possibilités d’utilisation de cette méthode dans les différents niveaux du processus d’analyse.Nos principales contributions, dans cette thèse, peuvent se résumer en trois points :1. Nous avons analysé les utilisations possibles des SVMs dans les différentes tâches des deux niveaux les plus importants du processus d’analyse des bases de données, à savoir la préparation et l’analyse. Nous avons discuté, sans implémentation, les différentes variantes de la méthode SVMs qui peuvent être utilisées ainsi que les adaptations nécessaires face aux attributs symboliques et aux grandes quantités de données. 2. Nous avons proposé une nouvelle méthode de prétraitement pour améliorer les performances de la méthode SVM en face des grandes bases de données. Cette méthode, que nous avons appelée CB-SR (Covering Based Samples Reduction), se base sur la détection précoce des vecteurs supports en utilisant la visibilité des exemples les uns vis à vis des autres dans l’espace de caractéristiques. La méthode a permis d’accélérer l’opération d’entrainement tout en préservant la précision de la méthode SVM.3. Nous avons proposé une nouvelle méthode pour l’accélération des SVMs multiclasse par l’utilisation de la SVM monoclasse. La méthode, appelée OCBM-SVM (One Class based Multiclass SVM), se base sur l’apprentissage d’un hyperplan, pour chaque classe, que nousgénéralisons par un décalage. La méthode proposée a donné des résultats intéressants par rapport aux méthodes, une-contre-une et une-contre-reste, actuellement utilisées.Les contributions proposées ont été validées sur des données artificielles et réelles largement utilisées par la communauté, et appuyées par des analyses montrant leurs avantages et leurs limites. Les résultats sont encourageants et ouvrent de nouvelles perspectives de recherche. |
| Sommaire : |
1 Introduction générale 1 1.1 Problématique . . . . . . . . . . . . . . 2 1.2 Contributions . . . .. . . . . . . . . . . . . . . . 3 1.3 Organisation de la thèse . . . . . . . . . . . . . . . . . 4 I État de l’art 6 2 Machines à vecteur support 7 2.1 Introduction . . . . . . . . . . 7 2.2 Apprentissage statistique . . . . . . . . . . . 8 2.3 SVMs binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 SVM à marge dure . . . . . 9 2.3.2 SVM à marge souple . . . . . . . . . .. . 12 2.3.3 Utilisation des noyaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.4 Architecture générale d’une machine à vecteur support . . . . . . . . . . . 16 2.4 SVMs multiclasse . . . . . . . .. . . . . . . . . . 17 2.4.1 Une-contre-reste (1vsR) . . . . . . . . . . . . . . . . . 18 2.4.2 Une-contre-une (1vs1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.3 Graphe de décision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.4 SVMs basées arbres de décision . . . . . . . . . . . . . . . . . . . . . . . . 21 2.5 SVM monoclasse (Novelty detection) . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.6 SVM pour la régression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.7 Implémentation des SVMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.8 Tuning et évaluation du modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.8.1 Métriques de performances . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.8.1.1 Taux de reconnaissance . . . . . . . . . . . . . . . . . . . . . . . 29 2.8.1.2 Matrice de confusion . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.8.2 Évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.8.2.1 Méthode HoldOut . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.8.2.2 Validation croisée . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.8.2.3 Le Bootstrap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.9 Conclusion et bilan . . . . . . . . . . . . . 33 3 SVMs et analyse des bases de données 34 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . 34 3.2 Analyse des bases de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3 Processus de data mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3.1 Définition et compréhension du problème . . . . . . . . . . . . . . . . . . 36 3.3.2 Collecte des données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3.3 Prétraitement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.4 Estimation du modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.5 Interprétation du modèle et établissement des conclusions . . . . . . . . . 37 3.4 Structure des bases de données à analyser . . . . . . . . . . . . . . . . . . . . . . 37 3.5 Types d’analyse effectuées sur les bases de données . . . . . . . . . . . . . . . . . 39 3.5.1 Niveau acquisition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.5.2 Niveau Extraction des connaissances . . . . . . . . . . . . . . . . . . . . . 41 3.5.2.1 L’apprentissage statistique . . . . . . . . . . . . . . . . . . . . . 41 3.5.2.2 Les réseaux de neurones . . . . . . . . . . . . . . . . . . . . . . . 41 3.5.2.3 Les arbres de décision . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5.2.4 Les machines à vecteur support . . . . . . . . . . . . . . . . . . . 42 3.5.2.5 Régression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5.2.6 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.5.2.7 Analyse des motifs fréquents . . . . . . . . . . . . . . . . . . . . 43 3.5.3 Synthèse et bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.6 Utilisation des SVMs pour la préparation . . . . . . . . . . . . . . . . . . . . . . 43 3.6.1 Lissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.6.2 Nettoyage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.6.3 Réduction verticale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.6.4 Réduction horizontale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.7 Utilisation des SVMs pour l’extraction des connaissances . . . . . . . . . . . . . . 45 3.7.1 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.7.1.1 Les attributs symboliques . . . . . . . . . . . . . . . . . . . . . . 45 3.7.1.2 Le nombre élevé d’enregistrements . . . . . . . . . . . . . . . . . 48 3.7.2 Régression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.7.3 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.7.4 Renforcement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.8 Intégration des SVMs dans les SGBD . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.8.1 Préparation des données pour les SVMs . . . . . . . . . . . . . . . . . . . 55 3.8.2 Réglage des paramètres des SVMs . . . . . . . . . . . . . . . . . . . . . . 56 3.8.3 Utilisation des SVMs dans Oracle . . . . . . . . . . . . . . . . . . . . . . . 56 3.9 Conclusion et bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 II Contributions 59 4 Accélération des SVMs par réduction d’exemples 60 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3 Travaux antérieurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.4 Méthode CB-SR proposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.4.1 Organigramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.4.2 Filtrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4.2.1 Notion de couverture . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4.2.2 Zone de couverture . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.4.2.3 Couverture mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.4.2.4 Couverture totale . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.4.2.5 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.4.2.6 Contrôle du taux de filtrage . . . . . . . . . . . . . . . . . . . . . 69 4.4.2.7 Algorithme proposé . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.4.3 Révision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.5 Résultats et discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.5.1 Données utilisées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.5.2 Matériel et critères d’évaluation . . . . . . . . . . . . . . . . . . . . . . . . 73 4.5.3 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.5.3.1 Sur des toys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.5.3.2 Sur des bases UCI . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.5.4 Utilisation du paramètre . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.5.5 Détermination automatique de . . . . . . . . . . . . . . . . . . . . . . . 76 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5 SVM multiclasse basée sur le OC-SVM 79 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.2 Travaux antérieurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.3 Méthode SVM multiclasse basée OC-SVM proposée . . . . . . . . . . . . . . . . . 82 5.4 Analyse de complexité et comparaison . . . . . . . . . . . . . . . . . . . . . . . . 85 5.4.1 Entrainement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.4.2 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.4.3 Taille du modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.5 Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.5.1 Données utilisées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.5.2 Matériel et critères d’évaluation . . . . . . . . . . . . . . . . . . . . . . . . 89 5.5.3 Résultats et bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.5.3.1 Sur des Toys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.5.3.2 Sur des bases UCI . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6 Applications 96 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.2 Calculatrice vocale par SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.2.1 Description du système proposé . . . . . . . . . . . . . . . . . . . . . . . . 97 6.2.1.1 Traitement du signal . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.2.1.2 Extraction des caractéristiques . . . . . . . . . . . . . . . . . . . 98 6.2.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.3 Tri automatique des dattes par SVM . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.3.1 Description du système proposé . . . . . . . . . . . . . . . . . . . . . . . . 100 6.3.2 Extraction des caractéristiques . . . . . . . . . . . . . . . . . . . . . . . . 101 6.3.3 Tests et Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.4 Reconnaissance des caractères manuscrits arabes . . . . . . . . . . . . . . . . . . 104 6.4.1 Description du système proposé . . . . . . . . . . . . . . . . . . . . . . . . 104 6.4.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 7 Conclusion générale 107 7.1 Bilan et contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.2 Perspectives de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Bibliographie 110 |
| En ligne : | http://thesis.univ-biskra.dz/id/eprint/2097 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/53 | Théses de doctorat | bibliothèque sciences exactes | Consultable |
