# How to 'intelligently' bin a collection of sorted data?

I am trying to intelligently bin a sorted collection. I have a collection of $n$ pieces of data. But I know that this data fits into $m$ unequally sized bins. I don't know how to intelligently choose the endpoints to properly fit the data. for example:

Say I have 12 items in my collection, and I know the data will fit into 3 bins:

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


How do I intelligently choose my breakpoints for the bins of $i = \{1-3\}, \{4-9\}, \{10-12\}$?

The current implementation I have breaks the data into evenly sized bins and then takes the average of the endpoints to find the indexes for the end of the bins. So it works like this:

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


So now anything below 3 fits in bin 1, anything above 3 but below 3 fits in bin 2, and anything above 3 fits in bin 3. You can see what my problem is. If the data has unequal bins my method fails.

A friend mentioned the k-nearest neighbor algorithm but I'm not sure.

-
Could you please explain what "intelligently" means? What are you trying to accomplish with the binning? Why are you binning in the first place? –  whuber Aug 13 '12 at 17:39
For your second to last paragraph, do you mean $<3\rightarrow bin1$, $\ge3\&<4\rightarrow bin2$, and $\ge4\rightarrow bin3$? Otherwise, it doesn't make sense to me. –  gung Aug 13 '12 at 17:42
I mean intelligently as in not naively like I did by assuming the bins were evenly spaced. if a piece of data falls in a specific bin that tells me something very important about that piece of data. I sort the data to determine the bin break indices and then decide which bin each piece of data falls individually. –  Matthew Kemnetz Aug 13 '12 at 17:42
unless i did something wrong in my averaging I think I have it right. by choosing even;y spaced bins all my endpoints are 3's. So I properly can't bin my data. This is why my implementation breaks down without even;y spaced bins. –  Matthew Kemnetz Aug 13 '12 at 17:44
Here's something I did in a slightly different setting. –  Macro Aug 14 '12 at 15:22

I think what you want to do is called clustering. You want to group together your "Value"s such that similar values are collected in the same bin and the number of total bins is preset.

You can solve this problem using the k-means clustering algorithm. In MATLAB, you can do this by:

bin_ids = kmeans(Values,3);


Above call will group the values in Values in three groups such that the within-group variance is minimal.

-
I found that out too. This is exactly what I implemented and it worked excellently. I came here to answer my own question but you beat me to it! Clustering was what I was trying to do. –  Matthew Kemnetz Aug 14 '12 at 13:40