Existe-t-il des algorithmes de clustering non basés sur la distance?

Il semble que pour les moyennes K et d'autres algorithmes associés, le regroupement est basé sur le calcul de la distance entre les points. Y en a-t-il un qui fonctionne sans lui?

Un exemple d'une telle méthode est les modèles de mélanges finis (par exemple ici ou ici ) utilisés pour le clustering. En FMM on considère la distribution ( ) de votre variable X comme un mélange de K distributions ( f 1 , . . . , F k ):$f$$X$$K$$f_1,...,f_k$

où est un vecteur de paramètres θ = ( π ' , θ ' 1 , . . . , θ ' k ) ' et π k est un nombre de k ième répartition dans le mélange et θ k est un paramètre (ou les paramètres) de la distribution de f k .$\vartheta$$\vartheta = (\pi', \vartheta_1', ..., \vartheta_k')'$$\pi_k$$k$$\vartheta_k$$f_k$

Un cas spécifique pour les données discrètes est l'analyse de classe latente (par exemple ici ) définie comme:

où est la probabilité d'observer la classe latente k (c'est-à-dire π k ), P ( x ) est la probabilité d'observer une valeur x et P ( x | k ) est la probabilité que x soit dans la classe k .$P(k)$$k$$\pi_k$$P(x)$$x$$P(x|k)$$x$$k$

Habituellement, pour l' algorithme FMM et LCA EM est utilisé pour l'estimation, mais l'approche bayésienne est également possible, mais un peu plus exigeante en raison de problèmes tels que l'identification du modèle et le changement d'étiquette (par exemple, le blog de Xi'an ).

Il n'y a donc pas de mesure de distance mais plutôt un modèle statistique définissant la structure (distribution) de vos données. En raison de cet autre nom de cette méthode est "clustering basé sur un modèle".

Consultez les deux livres sur FMM:

• McLachlan, G. et Peel, D. (2000). Modèles de mélanges finis. John Wiley & Sons.
• Frühwirth-Schnatter, S. (2006). Mélange fini et modèles de commutation Markov. Springer.

L' un des plus populaires paquets de regroupement qui utilise FMM mclust(vérifier ici ou ici ) qui est mis en œuvre en R . Cependant, des FMM plus compliqués sont également possibles, vérifiez par exemple le flexmixpackage et sa documentation . Pour LCA, il existe un package R poLCA .

K-means n'est pas "vraiment" basé sur la distance. Il minimise la variance . (Mais la variance$\sim$distances euclidiennes au carré; donc chaque point est également affecté au centroïde le plus proche par la distance euclidienne).

Il y a beaucoup de approches de clustering basées grille . Ils ne calculent pas les distances car cela donnerait souvent un temps d'exécution quadratique. Au lieu de cela, ils partitionnent les données et les agrègent en cellules de grille. Mais l'intuition derrière de telles approches est généralement très étroitement liée aux distances.

Il existe un certain nombre d'algorithmes de clustering pour les données catégorielles telles que COOLCAT et STUCCO. Les distances ne sont pas faciles à utiliser avec de telles données (l'encodage à chaud est un hack et ne donne pas de distances particulièrement significatives). Mais je n'ai entendu parler de personne utilisant ces algorithmes ...

Il existe des approches de regroupement pour les graphiques. Mais soit ils se réduisent à des problèmes de graphe classiques tels que la recherche de clique ou de quasi-clique et la coloration de graphe, soit ils sont étroitement liés au clustering basé sur la distance (si vous avez un graphe pondéré).

Le clustering basé sur la densité comme DBSCAN a un nom différent et ne se concentre pas sur la réduction des distances; mais la "densité" est généralement spécifiée par rapport à une distance, donc techniquement ces algorithmes sont basés sur la distance ou sur la grille.

La partie essentielle de votre question que vous avez laissée de côté est: quelles sont vos données ?

En plus des bonnes réponses précédentes, je suggérerais de considérer les modèles de mélange de Dirichlet et les modèles de processus hiérarchiques basés sur Bayesian . Pour une vue d'ensemble assez complète et générale des approches et méthodes pour déterminer un nombre optimal de clusters , veuillez consulter cette excellente réponse sur StackOverflow : /programming//a/15376462/2872891 .

Une approche purement discriminatoire est «maximisation de l'information régularisée» par Gomes et al . Il n'y a aucune notion de similitude / distance impliquée.

L'idée est d'avoir une régression logistique comme un modèle qui met des points dans des bacs. Mais au lieu de l'entraîner à maximiser une certaine forme de log-vraisemblance des étiquettes de classe, la fonction objectif est celle qui place les points dans différents groupes.

Pour contrôler la quantité de clusters utilisés par le modèle, un terme de régularisation supplémentaire pondéré par le paramètre hyper $\lambda$est utilisé. Cela se résume à la variance inverse d'un a priori gaussien sur les poids.

L'extension aux méthodes du noyau ou aux réseaux de neurones pour le clustering non linéaire est simple.