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.

Improve this question
$\endgroup$
5
  • 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 ♦
    Commented Aug 13, 2012 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
    Commented Aug 13, 2012 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
    Commented Aug 13, 2012 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
    Commented Aug 13, 2012 at 17:44
  • $\begingroup$ Here's something I did in a slightly different setting. $\endgroup$
    – Macro
    Commented Aug 14, 2012 at 15:22

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Aug 14, 2012 at 13:40
10
$\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

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is extremely interesting. Could you possibly go into more detail on why this might be better than k means? $\endgroup$
    – Matthew Kemnetz
    Commented Aug 15, 2012 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
    Commented Aug 15, 2012 at 15:17
  • 2
    $\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
    Commented Aug 15, 2012 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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