9
$\begingroup$

I have a binary sequence such as 11111011011110101100000000000100101011011111101111100000000000011010100000010000000011101111

Where clusters of mostly 1's are followed by a larger number of zeros, like in the picture below (black stands for 1):

enter image description here

I would like to apply a technique (preferably in R or in Python) where I can automatically detect these clusters of 1's, and produce spans (denoted as red lines in the image). I know one could do this with a threshold, i.e. saying that two clusters must be seperated by at least n 0's to be clusters, but I wonder if there are other established methods which do not use predefined thresholds.

Any idea?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

I would avoid calling them "clusters". With this terminology you end up getting distracted into multidimensional techniques from data mining all the time.

Your problem is a much simpler one dimensional setting. And even simpler: you don't even have coordinates but an array of zeros and ones.

There will not be a one-size-fits all solution for your problem ever. Because one user might want to read very high resolution "barcodes", while the other user has a lot of noise.

So in the end, you will need to have one parameter. You have a number of choices: absolute gap sizes, relative gap sizes, kernel bandwidth etc.

A very simple "kernel based" approach would be to map each pixel to the number of pixels set in -10...+10. So that is 21 cells, the value will be 0 to 21. Now look for a local minimum. Increase the window size, if it starts splitting runs that you did not yet want to split.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. The suggestion with the kernel and the local minimum is actually similar to what @EngrStudent proposed, right? Still I do not fully understand what is meant by it. How can I even look for a local minimum in a machine-based way? I.e. how can I calculate the first derivative of the "function" without knowing the function itself but just the values? $\endgroup$
    – grssnbchr
    Commented Apr 6, 2013 at 8:14
  • $\begingroup$ Yes, that probably is the same as EngrStudent suggested. Kernel density estimation is a very standard technique for smoothing. It's also used all over the place in image processing! It's a local minimum if there is no smaller neighbor value... it's as simple as that if you have a discrete data set. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Apr 6, 2013 at 16:11
2
$\begingroup$

Reference 1 on pages 49-55 has nice section on kernel based methods that might be useful here. If I were doing it then I would look at some weighted sum of the actual values and their first derivative because it might be a better indicator of "information".

Reference: http://amzn.com/0198538642 "Neural Networks for Pattern Recognition" by Christopher Bishop.(1995)

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ the numeric first derivative with respect to index is "diff". So if you have many "ones" in a row the derivative will be zeros. If you have sparse ones then the each time it switches the diff will be bigger. You could use EWMA as a poor mans kernel smooth. en.wikipedia.org/wiki/Exponential_smoothing . How does it work? It makes a weighted average of a window of values. A kernel function does something related but a little more complex. It takes a window sometimes a much wider window, and then computes a function based on the values in it. Sometimes the function looks like a pdf. $\endgroup$
    – EngrStudent
    Commented Apr 6, 2013 at 14:59
  • 1
    $\begingroup$ Summing the diff and the raw values gives you information when the ones are sparse and when they are dense. $\endgroup$
    – EngrStudent
    Commented Apr 6, 2013 at 15:02
  • $\begingroup$ Could you elaborate on your response and comment with a little example sequence? I have a very similar problem. $\endgroup$
    – Arun Jose
    Commented Jan 21, 2019 at 19:18
  • $\begingroup$ The absolute value of a diff is an edge detector. If you have a sequence such as 000111000, and you take the diff you get 00100(-1)00. The location of the 1 in the diff showns you the rising edge and the -1 shows the falling edge. If you took the absolute value of the diff, and then summed you would get 2 edges toal. If you had the sequence 010101010 then its absolute diff is 11111111, which sums to 8 edges. There is a substantially higher edge count. If you NOT the abs diff and use it in a running sum, it will tell you how many 1's or how many 0's you have in a row. $\endgroup$
    – EngrStudent
    Commented Jan 22, 2019 at 11:42
  • $\begingroup$ Under what criteria would you say a run of 1's comes to an end and starts? How do you determine the size of the window? $\endgroup$
    – Arun Jose
    Commented Jan 23, 2019 at 4:45
0
$\begingroup$

The problem has some similarity with image processing. You have a binary image with a height of one pixel and want to achieve some sort of segmentation.

The nature of the input image suggests a morphological filter to smooth the regions, e.g. closing. You'd need to choose the structuring element that thereby determines the "linkage" of the clusters. In the end this is pretty similar to your approach. You could also smooth the image using convolution filters, e.g. using blur, or gaussian kernel and apply a chosen threshold to re-binarize it.

If you can treat every 1 as a point, its position in the sequence as a coordinate, and can make up some distance metric, you could use pretty much every standard clustering algorithm there is. For example, you could use hierarchical clustering (choose a linkage criterion and a threshold), you could use k-means or an EM with a gaussian mixture model (choose the number of clusters you are looking for).

But I don't think, you may eventually getting away without having to predefine the sensitivity of the algorithm at least.

Improve this answer
$\endgroup$

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.