11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Could you please explain what "intelligently" means? What are you trying to accomplish with the binning? Why are you binning in the first place? $\endgroup$ – whuber Aug 13 '12 at 17:39
  • $\begingroup$ 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. $\endgroup$ – gung - Reinstate Monica Aug 13 '12 at 17:42
  • $\begingroup$ 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. $\endgroup$ – Matthew Kemnetz Aug 13 '12 at 17:42
  • $\begingroup$ 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. $\endgroup$ – Matthew Kemnetz Aug 13 '12 at 17:44
  • $\begingroup$ Here's something I did in a slightly different setting. $\endgroup$ – Macro Aug 14 '12 at 15:22
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Matthew Kemnetz Aug 14 '12 at 13:40
8
$\begingroup$

k-means is an option, but it is not very sensible for 1 dimensional data. In one-dimensional data, you have one enormous benefit: the data can be fully sorted.

Have a look at natural breaks optimization instead:
http://en.wikipedia.org/wiki/Jenks_natural_breaks_optimization

$\endgroup$
  • $\begingroup$ This is extremely interesting. Could you possibly go into more detail on why this might be better than k means? $\endgroup$ – Matthew Kemnetz Aug 15 '12 at 15:02
  • $\begingroup$ The main reason why I ask is because I am using MATLAB for my algorithm and I couldn't find any Jenks natural breaks optimizations in any toolboxes etc. so i will need to implement my own. I just wanted to know how much better/faster this might be before I switch gears and implement this. $\endgroup$ – Matthew Kemnetz Aug 15 '12 at 15:17
  • 1
    $\begingroup$ k-means is pretty stupid. It has means, and it will always split in the middle of the two means. So given e.g. 0 1 2 3 4 5 7 7 7, k-means will prefer to split between 4 and 5. Sometimes it will even split between 3 and 4. $\endgroup$ – Has QUIT--Anony-Mousse Aug 15 '12 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.