Résumé - Clustering des vecteurs hiérarchiques : Théorie et applications

Clustering des vecteurs hiérarchiques : Théorie et applications

2025-07-16 19:00:09

{"Ali Fattahi","Ali Eshragh","Babak Aslani","Meysam Rabiee"}

{cs.LG,cs.CC,stat.AP,stat.ME}

Ce document s'immerge dans le problème de regroupement de vecteurs de classement, où chaque vecteur représente des préférences sous forme d'une liste ordonnée d'entiers distincts. L'accent est mis sur le problème de regroupement de vecteurs de k-centroids (KRC), qui vise à partitionner un ensemble de vecteurs de classement en k clusters et à identifier le centroid de chaque cluster. Contrairement au regroupement k-means classique (KMC), le KRC impose que les observations et les centroids soient des vecteurs de classement. **Points clés** : * **KRC vs. KMC** : Le KRC est similaire au KMC mais avec une contrainte plus stricte qui impose que les points de données et les centroids soient des vecteurs de classement. Cela introduit de nouveaux défis en raison de la discrétisation structurée des variables de décision. * **NP-dur** : Le document établit la NP-durabilité du KRC, ce qui signifie que trouver la solution optimale est intractable en termes de temps de calcul pour de grandes bases de données. * **Solution pour un seul cluster** : Pour le cas d'un seul cluster, une solution analytique close-forme pour le centroid optimal est dérivée, qui peut être calculée en temps linéaire. * **Algorithme KRCA** : Pour répondre aux défis de calcul du KRC, un algorithme d'approximation efficace appelé KRCA est développé. Il affine itérativement les solutions initiales du KMC et utilise la structure unique des vecteurs de classement pour améliorer l'efficacité de calcul. * **Algorithme BnB** : Un algorithme de branch-and-bound (BnB) est introduit pour la reconstruction efficace de clusters dans KRCA. Il utilise un cadre d'arbre de décision pour réduire le temps de calcul tout en intégrant un paramètre de contrôle pour équilibrer la qualité et l'efficacité des solutions. * **Expériences numériques** : Des expériences numériques extensives sur des ensembles de données synthétiques et réelles montrent que KRCA outperforme constamment les solutions de base, offrant des améliorations significatives en termes de qualité des solutions avec des temps de calcul rapides. **Applications** : * **Plateformes de critiques en ligne** : Personnaliser les évaluations en fonction des préférences de genre, améliorer l'utilité et la rentabilité des spectateurs. * **Prise de décision de groupe à grande échelle** : Aggréger des perspectives diverses et dériver des solutions de consensus qui reflètent les préférences de tous les groupes. **Signification** : Ce travail met en lumière l'importance pratique du KRC pour la personnalisation et la prise de décision à grande échelle. Il fournit des avancées méthodologiques et des insights qui peuvent être construits dans des études futures, le rendant un outil précieux pour résoudre les problèmes de regroupement de vecteurs de classement dans diverses applications.