Solutions pour l'identification continue des clusters en ligne?

Permettez-moi de vous montrer un exemple d'une application de clustering en ligne hypothétique:

Au temps n, les points 1, 2, 3, 4 sont attribués au groupe bleu A et les points b, 5, 6, 7 sont attribués au groupe rouge B.

Au temps n + 1, un nouveau point a est introduit qui est affecté au cluster bleu A mais provoque également l'attribution du point b au cluster bleu A.

Au final, les points 1, 2, 3, 4, a, b appartiennent à A et les points 5, 6, 7 à B. Cela me semble raisonnable.

Ce qui semble simple à première vue est en fait un peu délicat - pour conserver les identifiants à travers les pas de temps. Permettez-moi d'essayer de clarifier ce point avec un exemple plus limite:

Le point vert provoquera la fusion de deux points bleus et de deux points rouges en un seul cluster que j'ai décidé arbitrairement de colorier en bleu - sachez que c'est déjà ma pensée heuristique humaine au travail!

Un ordinateur pour prendre cette décision devra utiliser des règles. Par exemple, lorsque des points sont fusionnés dans un cluster, l'identité du cluster est déterminée par la majorité. Dans ce cas, nous ferions face à un tirage au sort - le bleu et le rouge pourraient être des choix valides pour le nouveau cluster (ici de couleur bleue).

Imaginez un cinquième point rouge proche du vert. Ensuite, la majorité serait rouge (3 rouges contre 2 bleus), donc le rouge serait un bon choix pour le nouveau cluster - mais cela contredirait le choix encore plus clair de rouge pour le cluster le plus à droite car ceux-ci ont été rouges et devraient probablement le rester. .

Je trouve louche de penser à ça. À la fin de la journée, je suppose qu'il n'y a pas de règles parfaites pour cela - plutôt une heuristique optimisant certains critères de stabilité.

Cela m'amène finalement à mes questions:

1. Ce «problème» a-t-il un nom auquel il peut être fait référence?
2. Existe-t-il des solutions "standard" à cela et ...
3. ... existe-t-il peut-être même un package R pour cela?

Héritage raisonnable des identités de cluster dans le clustering répétitif

Dilemme de stabilité-plasticité, taux d'apprentissage et algorithmes d'oubli:

Tout d'abord, permettez-moi de dire que c'est une très bonne question et que c'est le genre de choses qui suscitent la réflexion qui améliorent vraiment la compréhension des algorithmes ML.

1. Ce «problème» a-t-il un nom auquel il peut être fait référence?

Ceci est généralement appelé "stabilité". Ce qui est drôle, c'est que la stabilité est en fait un concept utile dans le clustering régulier, c'est-à-dire pas en ligne. La «stabilité» de l'algorithme est souvent choisie comme critère de sélection pour déterminer si le bon nombre de grappes a été sélectionné. Plus précisément, le problème de stabilité du clustering en ligne que vous avez décrit est appelé le stability-plasticity dilemma.

2. Existe-t-il des solutions "standard" à cela et ...

Premièrement, la réponse globale est que de nombreux algorithmes de clustering en ligne sont étonnamment stables lorsqu'ils ont été bien formés avec une grande cohorte de données initiales. Cependant, c'est toujours un problème si vous voulez vraiment clouer les identités de cluster des points tout en permettant à l'algorithme de réagir aux nouvelles données. L'astuce de votre point est brièvement abordée dans Introduction à l'apprentissage automatique par Ethem Alpaydin. À la page 319, il dérive l'algorithme en ligne des k-moyennes par l'application de la descente de gradient stochastique, mais mentionne que le stability-plasticity dilemmasurvient lors du choix d'une valeur pour le taux d'apprentissage. Un petit taux d'apprentissage se traduit par la stabilité, mais le système perd l'adaptabilité alors qu'un taux d'apprentissage plus élevé gagne en adaptabilité, mais perd la stabilité du cluster.

Je crois que la meilleure voie à suivre est de choisir une implémentation de clustering en ligne qui vous permet de contrôler l'algorithme de descente de gradient stochastique, puis de choisir le taux d'apprentissage afin de maximiser la stabilité et l'adaptabilité du mieux que vous pouvez en utilisant une procédure de validation croisée solide.

Une autre méthode que j'ai vue employée est une sorte d'algorithme d'oubli, par exemple oublier des points plus anciens à mesure que le flux de données mûrit. Cela permet un système assez stable sur des échelles de temps rapides et permet une évolution sur des échelles de temps plus lentes. Adaptive Resonance Theorya été créé pour essayer de résoudre le problème stability-plasticity dilemma. Vous pourriez trouver cet article intéressant.

Je ne connais pas assez bien R pour suggérer un algorithme, mais je vous suggère de rechercher un mini-batch k-meansalgorithme qui vous permet de contrôler le taux d'apprentissage dans son algorithme de descente de gradient stochastique.

J'espère que ça aide!