Chatou, Mohammed Reda
(2024).
« Approche d'identification du nombre optimal de clusters dans les algorithmes de regroupement en combinant k-means et des métaheuristiques » Mémoire.
Montréal (Québec), Université du Québec à Montréal, Maîtrise en informatique.
Fichier(s) associé(s) à ce document :
Résumé
Le Projet traite la complexité NP-difficile associée à la détermination du nombre optimal de clusters pour l’algorithme K-means, une méthode courante en apprentissage automatique non supervisé. L’algorithme K-means nécessite la spécification préalable du nombre de clusters (k), et le défi réside dans le choix de k qui capture le mieux la structure sous-jacente des données. Ce choix est crucial, car il influence la qualité du regroupement des données, généralement évaluée en fonction de la proximité des points de données par rapport aux centres des clusters. Le problème se complique et devient NP-difficile en raison de l’aspect combinatoire de la sélection des clusters, où le nombre de combinaisons possibles croît de manière exponentielle avec la taille des données. Ceci rend la quête d’une solution optimale non seulement exigeante en termes de temps de calcul, mais aussi complexe en raison de l’absence d’une méthode déterministe fiable. De plus, l’obtention du résultat optimal dépend étroitement des données spécifiques utilisées et de la métrique de distance employée. Mon projet cherche à intégrer K-means avec des métaheuristiques telles que la Differential Evolution, le Dual Annealing, le Direct, et le Basin Hopping pour développer une méthode capable de rivaliser avec la méthode du coude tout en réduisant le temps d’exécution. Cette approche hybride est évaluée à l’aide de trois indices de validité (Davies-Bouldin, Calinski-Harabasz, Silhouette), permettant une comparaison de ces indices en termes de précision et de temps d’exécution. Les expériences menées montrent que les algorithmes hybrides peuvent être compétitifs par rapport à la méthode du coude, avec des performances variables selon l’indice de validité utilisé. Les résultats indiquent également que le choix de l’indice de validation peut influencer significativement les performances des algorithmes, et que la stabilité des résultats peut varier en fonction de la taille de l’échantillon et du type de données utilisé. En conclusion, le projet illustre l’efficacité de l’approche hybride pour résoudre le problème du nombre optimal de clusters, offrant une alternative viable qui combine la précision et l’efficacité temporelle. La recherche suggère des directions futures pour l’application de ces algorithmes à divers ensembles de données réels et pour l’exploration d’autres métaheuristiques et indices de validation, ouvrant ainsi la voie à des améliorations supplémentaires dans le domaine de l’analyse de données.
| Type: |
Mémoire accepté
|
| Informations complémentaires: |
Fichier numérique reçu et enrichi en format PDF/A. |
|
Directeur de thèse: |
Diallo, Abdoulaye Baniré |
| Mots-clés ou Sujets: |
Apprentissage non supervisé (Intelligence artificielle) / Regroupement de données / Algorithmes des k-moyennes / Algorithmes métaheuristiques |
| Unité d'appartenance: |
Faculté des sciences > Département d'informatique |
| Déposé par: |
Service des bibliothèques
|
| Date de dépôt: |
29 août 2025 09:55 |
| Dernière modification: |
29 août 2025 09:55 |
| Adresse URL : |
http://archipel.uqam.ca/id/eprint/19018 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
