Finding clusters in 1D array that contains certain number of entries with specific value

Hello,

I am wondering what would be the efficient way to find clusters of data in 1D array that contains certain number of specific value. For instance, I have a binary array that looks like this

data = [0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1]'

I would like to find a cluster that satisfy the following conditions

1) length of the cluster is fixed as 'L' (let's say L=7)

2) cluster should contain at least 'p' number of ones (let's say p=3)

3) if some clusters overlap or are located right next to each other, they can merge to create one bigger cluster

After clustering, I should get the following answer (answers are marked with {})

data = [0 0 0 {0 1 0 1 0 0 1 0} 0 0 0 {0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 1 0} 0 0 1 0 1]'

Here, you can see some clusters merged to form a bigger cluster.

In the end, I need to know the index of the start and end point of the each cluster as well as the total number of clusters. This will give me the following answers.

1) number of clusters = 2

2) index of initial value in each cluster = [4 15]

2) index of last value in each cluster = [11 34]

The actual array I need to work with is quite large so I want to see if there's an efficient way to compute this.

Thank you in advance!

[Mehmed Saad]

I think this is not the right output

data = [0 0 0 {0 1 0 1 0 0 1 0} 0 0 0 {0 1 0 0 0 1 1 0} 1 0 0 0 {0 1 1 1 1 0 1 0} 0 0 1 0 1]'

can you eloborate?

[Tae Lim]

Yes, the correct output would be three arrays marked with parenthesis {}. These include the following arrays.

[0 1 0 1 0 0 1 0], [0 1 0 0 0 1 1 0], [0 1 1 1 1 0 1 0]

In my original post, I meant to indicate where these arrays are located in the original data.

[Mehmed Saad]

i mean dont you think the 2nd output should be

[0 1 0 0 0 1 1 0 1 0 0 0]

[Image Analyst]

Why are the leading and trailing zeros included in the clusters? Why don't you just use imdilate() followed by bwlabel()?

[Tae Lim]

Muhammad Saad; you are correct. I missed that portion when I was making up this example. Actually, the correct answers would be [0 1 0 1 0 0 1 0], [0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 1 0]. In this case, I can also merge two adjacent clusters into one. I've corrected this in the original post. Thank you for spoting this!

[Tae Lim]

Image Analyst; I have a minimum length of the cluster (denoted by 'L' in my original post) in this problem. In the end, I will need to change all the values contained inside the clusters, including both 0 and 1 values. This is why I want to know the starting index and final index of each of the cluster so I can post process them.

[Sindar]

Why aren't the trailing numbers clustered?

[0 0 0 {0 1 0 1 0 0 1 0} 0 0 0 {0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 <1 0} 0 0 1 0 1>]'

[Sindar]

I don't have a full answer, but my suggestion is to start playing around with movsum. If the moving sum of 7 elements is >=3, then it is a cluster. Once you identify all the raw clusters, you can combine them

[Mohammad Sami]

yes, moving sum with window L is likely the best option.

[Image Analyst]

I'm afraid I still don't understand. Perhaps you can use cumsum() to count the 1's as you go along:

data = [0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1]
c = cumsum(data)

So why aren't the final 101 in a cluster? Is it because somehow cluster 2 and 3 got merged to form one giant cluster of more than 7 elements and there just weren't 7 elements remaining after that to form another cluster?

And why does cluster 1 have 8 elements instead of 7? And why is cluster #1 {0 1 0 1 0 0 1 0} instead of {0 0 1 0 1 0 0 1} or {1 0 1 0 0 1 0 0}

And why do you need to do this quirky thing anyway? What is the real world use case?

[Tae Lim]

Thank you all for your response. Again, it is simply my mistake that I didn't see the trailing numbers will form yet another cluster. So the correct answer will be

[0 0 0 {0 1 0 1 0 0 1 0} 0 0 0 {0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1}]'

Image Analyst; This actually came from real world application of rail tie replacement. You can either spot replace failed tie individually or remove the whole section with a dedicated machine. The use of dedicated machine is cheaper and thus preferred, but it may require replacing adjacent ties that are still good. The window 'L' denotes minimum length required to use the dedicated machine. The '0' in data indicates good ties and '1' are bad ties.

Sindar and Mohammad Sami; 'movsum' seems to be a great function to start with! I will start working with the function.

Thank you!