Scalable laplacian k-modes
Modes K laplaciens évolutifs
Ziko, Imtiaz Masud et Granger, Eric et Ayed, Ismail Ben
arXiv 2018
Résumé: Nous préconisons les modes K laplaciens pour la classification conjointe et la recherche de modes de densité, et proposons une relaxation concave-convexe du problème, qui donne un algorithme parallèle qui évolue jusqu'à de grands ensembles de données et de grandes dimensions. Nous optimisons une borne étroite (fonction auxiliaire) de notre relaxation, ce qui, à chaque itération, revient à calculer une mise à jour indépendante pour chaque variable d'affectation de cluster, avec convergence garantie. Par conséquent, notre optimiseur lié peut être distribué de manière simple pour les ensembles de données à grande échelle. De plus, nous montrons que les modes de densité peuvent être obtenus comme sous-produits des variables d'affectation via de simples opérations de valeur maximale dont le coût de calcul supplémentaire est linéaire en nombre de points de données. Notre formulation n'a pas besoin de stocker une matrice d'affinité complète et de calculer sa décomposition en valeurs propres, elle n'effectue pas non plus d'étapes de projection coûteuses et des itérations internes duel lagrangien pour les contraintes simplex de chaque point. De plus, contrairement au décalage moyen, notre estimation en mode densité ne nécessite pas d'itérations de montée en gradient en boucle interne. Il a une complexité indépendante de la dimension de l'espace de caractéristiques, produit des modes qui sont des points de données valides dans l'ensemble d'entrée et s'applique aux domaines discrets ainsi qu'aux noyaux arbitraires. Nous rapportons des expériences complètes sur divers ensembles de données, qui montrent que notre algorithme donne des performances très compétitives en termes de qualité d'optimisation (c'est-à-dire la valeur de l'objectif à variable discrète à la convergence) et de précision de clustering.
