Évaluation et recommandation des mesures de similarité pour le clustering de données mixtes

Numéro national de thèse

2025TLSEJ143

Titre en français

Titre en anglais

Evaluation and recommendation of similarity measures for mixed data clustering

Auteur

Diop, Abdoulaye (1998-....)

Directeur de recherche

Chevalier, Max (1975-.... ; enseignant-chercheur en informatique)

Co-directeur de recherche

Teste, Olivier (1972-....)

Date de soutenance

21 janvier 2025

Établissement

Université de Toulouse

Université Toulouse-Jean Jaurès

École doctorale

ALLPH@ : Arts, Lettres, Langues, Philosophie, Communication

Diplôme

Doctorat en Informatique

Unité de recherche

Institut de Recherche en Informatique de Toulouse - IRIT

Sujet

Informatique

Mots-clés en français

Clustering de données mixtes

Mesures de similarité

Système de recommandation

Méta-apprentissage

Mots-clés en anglais

Mixed data clustering

Similarity measures

Recommendation system

Meta-Learning

Résumé en français

Le clustering est une tâche importante pour l'exploration de données. Il permet de découvrir de manière non-supervisée des tendances ou des structures cachées au sein de grands ensembles de données. Les algorithmes de clustering visent à regrouper un ensemble d'observations en plusieurs groupes ou clusters de telle sorte que les observations au sein d'un même groupe soient similaires entre elles et différentes des observations dans les autres groupes. Un composant clé de ces algorithmes est la mesure de similarité qui a un impact direct sur la construction des clusters et, par conséquent, sur les performances des algorithmes. Le choix d'une mesure de similarité adaptée en fonction des données et de l'algorithme de clustering considéré est donc primordial et constitue l'objet principal de cette thèse.
Notre recherche se concentre sur le clustering de données mixtes qui sont des données hétérogènes présentant à la fois des attributs numériques et catégoriels. Elles sont très courantes dans des domaines tels que la santé, la finance, le marketing et les sciences sociales. Les algorithmes de clustering traditionnels, conçus pour des données homogènes, ne peuvent pas être appliqués directement aux données mixtes, d'où la nécessité de méthodes spécialisées. Nous classons ces méthodes en deux catégories : les approches basées sur la conversion (appelées méthodes d'homogénéisation) et celles qui considèrent les données mixtes directement sans conversion (méthodes mixtes). Nous montrons dans ce manuscrit, que les méthodes mixtes sont généralement préférables aux méthodes d'homogénéisation, car elles conservent la structure originale des données et utilisent un traitement adapté pour chaque type d'attribut. Nos travaux se focalisent donc principalement sur les méthodes mixtes.
Dans un premier temps, nous avons mené une étude expérimentale afin d’évaluer l'impact des mesures de similarité sur les performances des méthodes mixtes. Ces méthodes combinent généralement deux mesures de similarité : l'une pour les attributs numériques et l'autre pour les attributs catégoriels. Nos expérimentations montrent que le choix de ces mesures de similarité influence de manière significative les performances des différents algorithmes considérés, soulignant ainsi l'importance de choisir des mesures appropriées.
Trouver les meilleures ou de bonnes mesures de similarité est difficile, en particulier pour les utilisateurs non experts, en raison du grand nombre de mesures qui existent dans la littérature et de leurs performances variables en fonction du jeu de données, de l'algorithme de clustering et de la mesure de performance. Afin de répondre à cette problématique, nous avons proposé SIMREC, un système de recommandation de mesures de similarité pour les algorithmes de clustering de données mixtes. SIMREC utilise le meta-learning (ou méta-apprentissage) pour identifier les relations entre les caractéristiques des jeux de données et les performances des différentes mesures de similarité, et ce pour différents algorithmes de clustering et mesures de performance. SIMREC prend en entrée un triplet composé d'un jeu de données mixtes, d'un algorithme de clustering et d'une mesure de performance à optimiser. Il recommande ensuite les paires optimales de mesures de similarité numérique et catégorielle en fonction des caractéristiques du jeu de données d'entrée. Ce système permet à la fois à des utilisateurs experts et non experts de choisir de façon efficace des mesures de similarité adaptées à leur cas d'usage, évitant ainsi les stratégies d'essais-erreurs qui sont souvent chronophages et coûteuses.

Résumé en anglais

Clustering algorithms are essential in data mining, offering powerful tools to uncover hidden patterns and structures within datasets. aim to divide data points into coherent groups based on similarities or dissimilarities, making it easier to explore and understand complex data. A critical component of clustering algorithms is the similarity measure, which significantly affects their ability to identify meaningful patterns. Thus, selecting suitable similarity measures for clustering algorithms is a crucial challenge addressed in this thesis.
Our research focuses on clustering mixed data—datasets containing both numerical and categorical attributes—which are increasingly common in fields such as healthcare, finance, marketing, and social sciences. Traditional clustering algorithms, designed for homogeneous data, cannot be directly applied to mixed data due to the differing nature of numerical and categorical attribute types. This necessitates specialized approaches for mixed data clustering.
We categorize mixed data clustering methods into two groups: conversion-based approaches (referred to as homogenization methods) and non-conversion-based approaches (mixed methods). Through extensive experiments, we demonstrate that mixed methods are generally more effective, as they handle different data types directly without altering the dataset’s inherent structure. In contrast, homogenization methods, which convert one data type into another, often lead to sub-optimal clustering results.
Focusing on mixed methods, we further investigate the impact of similarity measures on clustering performance. Unlike clustering algorithms for homogeneous data, mixed methods typically combine two similarity measures—one for numerical attributes and one for categorical attributes. Our experiments confirm that the choice of these similarity measures significantly influences clustering outcomes, underscoring the importance of selecting the appropriate measures for each dataset.
However, selecting the right similarity measures can be challenging, especially for non-experts, due to the wide range of available measures for each data type and their performance dependency on the dataset, clustering algorithm, and cluster validity index. To address this, we propose SIMREC, a similarity measure recommendation system for mixed data clustering. SIMREC leverages meta-learning to identify relationships between dataset characteristics and the performance of similarity measures for different mixed data clustering algorithms and cluster validity indices. Given a mixed dataset, clustering algorithm, and validity index, the system recommends optimal pairs of numerical and categorical similarity measures based on the dataset characteristics. This system aims to assist both expert and non-expert users in efficiently selecting similarity measures, avoiding time-consuming trial-and-error and search-based strategies.

Accès au document

Accès libre

Citation bibliographique

Ce document est en accès restreint