Clustering data into bins of variable sizes

I'd like to build a model (in R or excel) that takes in large amount of linear data and segments it into "bins". The linear data is an attribute that reflects what condition that section/record is at.

I'd like to simplify the data and generalize it over sections as seen in the example below. This could perhaps be done based on a normal distribution with a confidence interval or any other method you may recommend. The idea is that to aggregate the data into more generalized bins. Each bin must have at least 4 sections/records in it but not more than 10.

So in short, I'd like to do the following:

1. I want a clustering method to group my data
2. I want each group to have 4-10 members always
3. I want the items in each group to be successive for example A001_002 wouldn't be grouped with A001_999

Here's an example of what I want to do followed by a data dump. Note that I have about 100,000 of these points.

Section_ID  Condition_Rating
A001_001    3
A001_002    2
A001_003    1
A001_004    3
A001_005    4
A001_006    5
A001_007    0
A001_008    0
A001_009    0
A001_010    1
A001_011    2
A001_012    3
A001_013    2
A001_014    8
A001_015    9
A001_016    10
A001_017    9
A001_018    8
A001_019    2
A001_020    3
A001_021    4
A001_022    9
A001_023    5
A001_024    3

• What do you mean "linear data"? – wolfsatthedoor Dec 12 '14 at 16:11
• Clustering is easy but most algorithms offer little control over the cluster sizes. Looking for structural breaks in the data generating process is harder, especially with such small groups, but possibly the slightly more appropriate approach for what you are doing. In my personal opinion the problem you are trying to solve is nontrivial. Hopefully someone has something to offer in the way of a solution. – wolfsatthedoor Dec 12 '14 at 16:41
• @Tim the only way I can describe it is that the sections should be homogeneous. There is no rule per say; however, if I had to force some, I'd say 8-10, 5-7, 2-4, 0-1 – dassouki Dec 12 '14 at 19:35

A dynamic program to minimize the sum of group variances subject to these constraints is simple and reasonably fast, especially for such a narrow range of group sizes. It reproduces the posted solution.

The data are plotted as point symbols. The groups are color-coded and separated by vertical lines. Group means are plotted as horizontal lines.

Commented R code follows. It computes the solution recursively, achieving efficiency by caching the results as it goes along. The program cluster(x,i) finds (and records) the best solution starting at index i in the data array x by searching among all feasible windows of lengths n.min through n.max beginning at index i. It returns the best value found so far (and, within the global variable cache$Breaks, leaves behind an indicator of the indexes that start each group). It can process arrays of thousands of elements in seconds, depending on how large the range n.max-n.min is. For larger problems it would have to be improved to include some branch-and-bound heuristics to limit the amount of searching. # # Univariate minimum-variance clustering with constraints. # Requires a global data structure cache. # cluster <- function(x, i) { # # Cluster x[i:length(x)] recursively. # Begin with the terminal cases. # if (i > cache$Length) return(0)                    # Nothing to process   $cache$Breaks[i] <<- FALSE                          # Unmark this break    $if (i + cache$n.min - 1 > cache$Length) return(Inf)# Interval is too short if (!is.na(v <- cache$Cache[i])) return(v)         # Use the cached value $n.min <- cache$n.min + i-1                         # Start of search      $n.max <- min(cache$n.max + i-1, cache$Length) # End of search if (n.max < n.min) return(0) # Prevents R errors # # The recursion: accumulate the best total within-group variances. # To implement other objective functions, replace var by any measure of # within-group homogeneity. # values <- sapply(n.min:n.max, function(k) var(x[i:k]) + cluster(x, k+1)) # # Find and store the best result. # j <- which.min(values) cache$Breaks[n.min + j] <<- TRUE  # Mark this as a good break $cache$Cache[i] <<- values[j]      # Cache the result          $return(values[j]) # Pass it to the caller } # # The data. # x <- c(3,2,1,3,4,5,0,0,0,1,2,3,2,8,9,10,9,8,2,3,4,9,5,3) # # Initialize cache to specify the constraints; and run the clustering. # system.time({ n <- length(x) cache <- list(n.min=4, n.max=10, # The length constraints Cache=rep(NA, n), # Values already found Breaks=rep(FALSE, n+1), # Group start indexes Length=n) # Cache size cluster(x, 1) # I.e., process x[1:n] cache$Breaks[1] <- TRUE # Indicate the start of the first group $}) # # Display the results. # breaks <- (1:(n+1))[cache$Breaks]                # Group start indexes $groups <- cumsum(cache$Breaks[-(n+1)])           # Group identifiers
averages <- tapply(x, groups, mean)              # Group summaries
colors <- terrain.colors(max(groups))            # Group plotting colors

plot(x, pch=21, bg=colors[groups], ylab="Rating")
abline(v = breaks-1/2, col="Gray")
invisible(mapply(function(left, right, height, color) {
lines(c(left, right)-1/2, c(height, height), col=color, lwd=2)
}, breaks[-length(breaks)], breaks[-1], averages, colors))

• All I can say is Wow! Thank you very much. You've always been such a great help whether on this site or GIS.SE. I really appreciate the thorough and perfect answer – dassouki Dec 12 '14 at 19:58
• +1, great answer! I just naively ran your code but changed the data to x <- (3,2,1,3,4,5,0,0,0,1,2,3,2,8,9,100,9,8,2,3,4,9,5,3) (everything else is the same). But now, several groups of size 1 are displayed. Do you know why this is the case? – COOLSerdash Dec 12 '14 at 20:46
• @COOL That doesn't happen for me. I stuck the missing c in front of the opening parenthesis (so it reads something like x <- c(3,2,1,3,4,5,0,0,0,1,2,3,2,8,9,100,9,8,2,3,4,9,5,3)), pasted the whole line in immediately before the system.time statement, and re-ran the entire file. I get four groups starting at positions 1, 5, 15, and 21. Note that I adopted a very quick and dirty architecture which requires you to re-initialize the cache data structure before re-running the code. (I should have encapsulated that better.) – whuber Dec 12 '14 at 21:56
• You're right! I played around with some numbers and must have forgotten to re-initialize the cache data structure. Sorry. – COOLSerdash Dec 12 '14 at 21:58
• @whuber if I want to write a paper and reference your answer to my question in my methodology question and the fact that I'm converting the code into python. What's the correct way to do so? – dassouki Jul 4 '16 at 12:27