Agglomerative 2-3 hierarchical classification (theoretical and applicative study)
Sergiu Chelcea, LEMAIRE, Jacques, TROUSSE, Brigitte · OpenGrey (Institut de l'Information Scientifique et Technique) · 2007
Cette thèse porte sur une extension récente de la classification ascendante hiérarchique, appelée classification ascendante 2-3 hiérarchique (2-3 CAH), proposée par P. Bertrand en 2002, avec en vue son application en fouille de données. Les trois contributions majeures de cette thèse sont : i) quatre nouvelles propriétés des 2-3 hiérarchies (appelées aussi paired hiérarchies ) issues d une étude théorique qui nous ont permis de mettre en évidence un cas spécial de fusion des classes. ii) Un nouvel algorithme général de la 2-3 CAH avec une complexite réduite de O(n3) à O(n2 log n). Les tests sur des différents ensembles de données ont confirmé notre analyse théorique de la complexité. Des résultats très satisfaisants ont été obtenus en analysant la qualité des 2-3 hiérarchies comparées aux hiérarchies classiques. Nous avons également proposé un modèle orienté-objet de notre algorithme ainsi qu une boîte à outils appelée Hierarchical Clustering Toolbox (HCT). iii) Une toute première étude de l utilisation de la 2-3 CAH sur des données réelles relevant des domaines du Web Mining et de la classification de documents XML : celle-ci a donné lieu à des résultats intéressants et portait sur la comparaison de la classification 2-3 hiérarchique des équipes de recherche de l INRIA en utilisant soit le comportement des utilisateurs Web, soit leur rapport annuel d activité écrit en HTML par rapport à la structure organisationnelle existante en thèmes de recherche. Enfin, pour conclure, nous proposons plusieurs pistes de recherche future relatives à la 2-3 CAH et à notre boîte à outils HCT, développée pendant cette thèse.