Un Jeu De Potentiel Pour Le Clustering De Données

Résumé: Actuellement, les données ont un intérêt considérable et croissant dans les secteurs économiques et industriels. De nouvelles techniques sont apparues pour gérer ce flux important de données qui peuvent être de différentes sources et de différents types. L'une des techniques les plus répandues est le clustering. Le clustering est une classification non supervisée de données sur la base de leur similarité. Bien qu'il existe plusieurs méthodes pour la résolution de ce problème, aucune approche reconnue fiable ne peut garantir la qualité des solutions fournies. Chaque méthode présente des avantages et des inconvénients selon le(s) critère(s) d'évaluation utilisé(s). Depuis peu, le clustering constitue un nouveau champ d'application de la théorie des jeux. Le tout premier travail initiant cette application est un article de M. Pellilo et al, intitulé : Grouping with asymmetric affinities: A game-theoretic perspective. L'intérêt d'une telle approche est que les outils de la théorie des jeux permettent de surpasser quelques limitations des approches par partitionnement, tels que la connaissance au préalable du nombre de groupes à former, le chevauchement des clusters, la détection des bruits, la symétrie des matrices de similarité, etc. Notre principale objectif dans ce travail est alors de proposer une nouvelle approche de clustering basée sur les outils de la théorie des jeux, qui permettrait de ramener la résolution du problème de clustering de données à la résolution d'un jeu de potentiel, dont l'existence d'au moins un équilibre de Nash pure est garantie. Pour résoudre ce jeu, nous proposons un algorithme efficace, basé sur la notion de stratégies de meilleure réponse pour la recherche d'un équilibre de Nash pure, qui dans ce cas, correspondant à une solution stable au problème de clustering.

Publié dans la revue: Séminaire Mathématique de Béjaia