Déterminer différents clusters de données 1d à partir de la base de données

24

J'ai une table de base de données de transferts de données entre différents nœuds. Il s'agit d'une énorme base de données (avec près de 40 millions de transferts). L'un des attributs est le nombre de transferts d'octets (nbytes) qui vont de 0 octet à 2 tera octets. Je voudrais regrouper les nbytes de telle sorte que, étant donné k clusters, certains transferts x1 appartiennent à k1 cluster, x2 transfters à k2 etc.

D'après la terminologie que j'ai utilisée, vous auriez pu deviner ce que j'allais faire: K-means. Il s'agit de données 1d car nbytes est la seule fonctionnalité qui m'importe. Lorsque je cherchais des méthodes différentes pour cela, j'ai vu que l'EM a été mentionné à quelques reprises avec une approche sans clustering. Je voudrais connaître votre point de vue sur la façon d'aborder ce problème (en particulier s'il faut regrouper ou non en cluster).

Merci!

clustering k-means Shaun
la source
Que sont les «transferts x1», les «transferts x2», etc.? Le "type de transfert" est-il une deuxième variable?
Peter Flom - Réintègre Monica
Les transferts x1 ne sont qu'un moyen pour moi de dire que ces 500 transferts avaient une taille de transfert autour d'une certaine valeur (ce serait la moyenne pour ce cluster en k-means).
Shaun
5
Je ne suis pas un expert en clustering, mais avec autant de données et seulement 1 dimension, je me demande si vous pouvez simplement faire des graphiques de densité de noyau en utilisant différentes bandes passantes et voir combien de modes / pics vous trouvez, et si le résultat semble cela vous serait utile.
gung - Rétablir Monica
1
Vous avez demandé si vous souhaitez regrouper ou non. Quel serait votre objectif de clustering? Souhaitez-vous utiliser les clusters à d'autres fins, ou est-ce d'intérêt théorique?
Peter Flom - Réintègre Monica
Certains des autres attributs de la table sont le nom d'utilisateur, les dates de début et de fin. J'espère qu'en regroupant les transferts en fonction de la taille du transfert, je peux ensuite me référer à d'autres attributs d'un transfert particulier pour voir qui transfère combien à quel mois de l'année. Je ne sais pas encore ce que nous ferons de cette observation. Mais c'est un peu là où je vais.
Shaun

Réponses:

43

Dans les données unidimensionnelles, n'utilisez pas l'analyse de cluster.

L'analyse en grappes est généralement une technique multivariée. Ou permettez-moi de le dire autrement: pour les données unidimensionnelles - qui sont complètement ordonnées - il existe de bien meilleures techniques. L'utilisation de k-means et de techniques similaires ici est un gaspillage total, à moins que vous ne fassiez suffisamment d'efforts pour les optimiser réellement pour le cas 1-d.

Juste pour vous donner un exemple: pour k-signifie qu'il est courant d'utiliser k objets aléatoires comme graines initiales. Pour les données unidimensionnelles, il est assez facile de faire mieux en utilisant simplement les quantiles appropriés (1 / 2k, 3 / 2k, 5 / 2k, etc.), après avoir trié les données une fois , puis optimisé à partir de ce point de départ. Cependant, les données 2D ne peuvent pas être triées complètement. Et dans une grille, il y aura probablement des cellules vides.

Je ne l'appellerais pas non plus cluster. Je l'appellerais intervalle . Ce que vous voulez vraiment faire, c'est optimiser les bordures d'intervalle. Si vous faites k-means, il testera pour chaque objet s'il doit être déplacé vers un autre cluster. Cela n'a pas de sens dans 1D: seuls les objets aux limites d'intervalle doivent être vérifiés. C'est évidemment beaucoup plus rapide, car il n'y a que ~ 2k objets là-bas. S'ils ne préfèrent pas déjà d'autres intervalles, les objets plus centraux ne le seront pas non plus.

Vous voudrez peut-être examiner des techniques telles que l' optimisation Jenks Natural Breaks , par exemple.

Ou vous pouvez faire une estimation de la densité du noyau et rechercher des minima locaux de la densité à y répartir. La bonne chose est que vous n'avez pas besoin de spécifier k pour cela!

PS, veuillez utiliser la fonction de recherche. Voici quelques questions sur le clustering de données 1-D que vous avez manquées:

Anony-Mousse
la source
Les quantiles ne sont pas nécessairement d'accord avec les clusters. Une distribution 1d peut avoir 3 grappes naturelles où deux détiennent chacune 10% des données et la dernière contient 80% des données. Je pense donc qu'il est possible de se regrouper ici, bien que je convienne qu'il est logique d'optimiser la course en sélectionnant intelligemment les graines, etc. ou en utilisant d'autres idées.
Bitwise
Les quantiles sont probablement de bons points de départ pour l' optimisation , c'est à cela que je faisais référence. Et juste pour donner un exemple de ce que vous pouvez faire en 1D qui ne fonctionne pas si bien en 2+ dimensions.
Anony-Mousse
Je suis d'accord que ça vaudrait la peine d'utiliser des quantiles comme graines, mais j'essaierais quand même quelques initialisations aléatoires (pour des exemples comme celui que j'ai donné). Dans tous les cas, la meilleure méthode serait de simplement regarder le graphique histogramme / densité et de choisir manuellement les graines puis de les optimiser avec le clustering. Cela convergera très rapidement vers une bonne solution.
Bitwise
3
Jenks est k-means en 1D.
whuber
1
@whuber même si c'est mathématiquement, j'espère qu'il a été assez intelligent pour exploiter que les données puissent être commandées . Si vous utilisez l'approche Lloyd pour faire k-means sur des données 1-d, vous êtes stupide, car vous faites beaucoup de calculs que vous pourriez ignorer. Et pour la plupart des gens, k-means est Lloyd. Et certaines personnes se soucient d'éviter les recalculs inutiles.
Anony-Mousse
1

Votre question est-elle de savoir si vous devez regrouper ou quelle méthode utiliser pour regrouper?

Pour savoir si vous devez mettre en cluster, cela dépend si vous voulez partitionner automatiquement vos données (par exemple si vous voulez répéter ce partitionnement plusieurs fois). Si vous ne faites cela qu'une seule fois, vous pouvez simplement regarder l'histogramme de la distribution de vos valeurs, et le partitionner à l'œil, comme proposé dans les commentaires. Je recommanderais quand même de regarder les données à l'œil nu, car cela pourrait vous aider à déterminer le nombre de clusters que vous souhaitez et également si le clustering "a fonctionné".

En ce qui concerne le type de clustering, k-means devrait convenir s'il y a de "vrais" clusters dans les données. Si vous ne voyez aucun cluster dans l'histogramme, cela n'a pas beaucoup de sens de le regrouper de toute façon, car tout partitionnement de votre plage de données donnera des clusters valides (ou dans le cas de l'initiation aléatoire de kmeans, vous obtiendrez différents clusters chaque course).

Au niveau du bit
la source