Comment regrouper «intelligemment» une collection de données triées?

J'essaie de classer intelligemment une collection triée. J'ai une collection de éléments de données. Mais je sais que ces données s'inscrivent dans bacs de taille inégale. Je ne sais pas comment choisir intelligemment les points de terminaison pour ajuster correctement les données. par exemple: $n$ $m$

Supposons que j'ai 12 articles dans ma collection et que je sais que les données tiendront dans 3 bacs:

Index:  1 2 3 4 5 6 7 8 9 10 11 12
Value:  1 1 1 3 3 3 3 3 3 5  5  6

Comment choisir intelligemment mes points d'arrêt pour les casiers ? $i = \{1-3\}, \{4-9\}, \{10-12\}$

L'implémentation actuelle que j'ai divise les données en bacs de taille égale, puis prend la moyenne des points d'extrémité pour trouver les index pour la fin des bacs. Donc ça marche comme ça:

Index:  1 2 3 4 5 6 7 8 9 10 11 12
Value:  1 1 1 3 3 3 3 3 3 5  5  6

first break evenly: i = 1-4, 5-8, 9-12
mean endpoints:  between 4 and 5: (3+3)/2 = 3
                 between 8 and 9: (3+3)/2 = 3

Alors maintenant, tout ce qui est inférieur à 3 rentre dans le bac 1, tout ce qui est supérieur à 3 mais inférieur à 3 rentre dans le bac 2, et tout ce qui dépasse 3 rentre dans le bac 3. Vous pouvez voir quel est mon problème. Si les données ont des cases inégales, ma méthode échoue.

Un ami a mentionné l'algorithme du plus proche voisin, mais je ne suis pas sûr.

clustering histogram binning Matthew Kemnetz
la source

Pourriez-vous expliquer ce que signifie "intelligemment"? Qu'essayez-vous d'accomplir avec le binning? Pourquoi êtes-vous binning en premier lieu?

whuber

Pour l'avant-dernier paragraphe, voulez-vous dire , et ? Sinon, cela n'a aucun sens pour moi.

< 3 \to b i n 1

$<3\rightarrow bin1$

\geq 3 & < 4 \to b i n 2

$\ge3\&<4\rightarrow bin2$

\geq 4 \to b i n 3

$\ge4\rightarrow bin3$

gung - Rétablir Monica

Je veux dire intelligemment comme pas naïvement comme je l'ai fait en supposant que les bacs étaient régulièrement espacés. si un morceau de données tombe dans un bac spécifique qui me dit quelque chose de très important au sujet de ce morceau de données. Je trie les données pour déterminer les indices de rupture de bac, puis je décide dans quel bac chaque donnée tombe individuellement.

Matthew Kemnetz

sauf si j'ai fait quelque chose de mal dans ma moyenne, je pense que j'ai raison. en choisissant pair; les cases espacées y tous mes points de terminaison sont des 3. Je ne peux donc pas classer correctement mes données. C'est pourquoi mon implémentation tombe en panne sans paires espacées.

Matthew Kemnetz

Voici quelque chose que j'ai fait dans un cadre légèrement différent.

Macro du

Réponses:

Je pense que ce que vous voulez faire est appelé clustering. Vous souhaitez regrouper vos "valeurs" de telle sorte que des valeurs similaires soient collectées dans le même bac et que le nombre total de bacs soit prédéfini.

Vous pouvez résoudre ce problème en utilisant l' algorithme de clustering k-means . Dans MATLAB, vous pouvez le faire en:

bin_ids = kmeans(Values,3);

L'appel ci-dessus regroupera les valeurs en Valuestrois groupes de sorte que la variance intra-groupe soit minimale.

emrea
la source

Je l'ai aussi découvert. C'est exactement ce que j'ai mis en œuvre et cela a parfaitement fonctionné. Je suis venu ici pour répondre à ma propre question mais tu m'as battu! Le regroupement était ce que j'essayais de faire.

Matthew Kemnetz

k-means est une option, mais elle n'est pas très sensible pour les données à 1 dimension. Dans les données unidimensionnelles, vous avez un énorme avantage: les données peuvent être entièrement triées.

Jetez plutôt un œil à l'optimisation des ruptures naturelles :
http://en.wikipedia.org/wiki/Jenks_natural_breaks_optimization

A QUIT - Anony-Mousse
la source

C'est extrêmement intéressant. Pourriez-vous éventuellement expliquer plus en détail pourquoi cela pourrait être mieux que k signifie?

Matthew Kemnetz

La principale raison pour laquelle je pose la question est parce que j'utilise MATLAB pour mon algorithme et que je n'ai trouvé aucune optimisation des ruptures naturelles Jenks dans aucune boîte à outils, etc. donc je devrai implémenter la mienne. Je voulais juste savoir à quel point cela pourrait être meilleur / plus rapide avant de changer de vitesse et de l'implémenter.

Matthew Kemnetz

k-means est assez stupide. Il a des moyens, et il se divisera toujours au milieu des deux moyens. Donc, donné par exemple 0 1 2 3 4 5 7 7 7, k-means préférera se diviser entre 4 et 5. Parfois, il se divisera même entre 3 et 4.

A QUIT - Anony-Mousse