Note publique d'information : 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 complexité 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.
Note publique d'information : This thesis deals with a recent extension of the agglomerative hierarchical classification,
the agglomerative 2-3 hierarchical classification (2-3 AHC), proposed by p. Bertrand
in 2002, with a focus on its application to the data mining. The three major contributions
of this thesis are : i) four new properties of the 2-3 hierarchies (also called paired
hierarchies) as a result of a theoretical study that allowed us to highlight a special
case of clusters merging. ii) A new general 2-3 AHC algorithm with a reduced complexity
from (On3) to O(n2 log n). The tests on different datasets confirmed our theoretical
complexity study. Very satisfying results were obtained by analyzing the “quality”
of the 2-3 hierarchies compared with the traditional hierarchies. We also proposed
an object-oriented model of our algorithm and a new toolbox called Hierarchical Clustering
Toolbox (HCT). iii) A first study of the applicability of the 2-3 AHC on real data
from the Web Mining and XML Document Clustering fields. This study lead to interesting
results and was based on the comparison of the 2-3 hierarchical clustering of INRIA’s
research teams using either the Web users behaviour, or the research teams annual
reports, with the existent structure of the research themes organization. Finally,
to conclude, we propose several research perspectives related to the 2-3 AHC and to
our HCT toolbox.