Detección de clusters en una secuencia binaria

Question

Tengo una secuencia binaria como 11111011011110101100000000000100101011011111101111100000000000011010100000010000000011101111

Donde los grupos de mayoría de 1's son seguidos por un mayor número de ceros, como en la imagen de abajo (el negro representa el 1):

Me gustaría aplicar una técnica (preferiblemente en R o en Python) en la que pueda detectar automáticamente estos clusters de 1's, y producir los tramos (denotados como líneas rojas en la imagen). Sé que se podría hacer esto con un umbral, es decir, diciendo que dos clusters deben estar separados por al menos n 0 a ser racimos, pero me pregunto si hay otros métodos establecidos que no utilizan predefinido umbrales.

¿Alguna idea?

Answer 1

Yo evitaría llamarlos "racimos". Con esta terminología acabas distrayéndote en técnicas multidimensionales de minería de datos todo el tiempo.

Su problema es un escenario unidimensional mucho más simple. Y aún más simple: ni siquiera tienes coordenadas sino una matriz de ceros y unos.

No habrá una solución única para su problema siempre . Porque un usuario puede querer leer "códigos de barras" de muy alta resolución, mientras que el otro usuario tiene mucho ruido.

Así que al final, necesitarás tener un parámetro. Tienes varias opciones: tamaños de huecos absolutos, tamaños de huecos relativos, ancho de banda del núcleo, etc.

Un enfoque muy simple "basado en el núcleo" sería asignar cada píxel al número de píxeles establecido en -10...+10. Así que son 21 celdas, el valor será de 0 a 21. Ahora busque un mínimo local. Aumentar el tamaño de la ventana, si comienza a dividir las carreras que aún no quería dividir.

Answer 2

La referencia 1, en las páginas 49-55, tiene una buena sección sobre métodos basados en el núcleo que podría ser útil en este caso. Si yo lo hiciera, me fijaría en alguna suma ponderada de los valores reales y su primera derivada porque podría ser un mejor indicador de "información".

Referencia: http://amzn.com/0198538642 "Neural Networks for Pattern Recognition" (Redes neuronales para el reconocimiento de patrones), de Christopher Bishop.(1995)

Answer 3

El problema tiene cierta similitud con el procesamiento de imágenes. Se tiene una imagen binaria con una altura de un píxel y se quiere conseguir algún tipo de segmentación .

La naturaleza de la imagen de entrada sugiere un filtro morfológico para suavizar las regiones, por ejemplo cerrar . Habría que elegir el elemento estructurador que determina así la "vinculación" de los grupos. Al final, esto es bastante similar a tu enfoque. También podrías suavizar la imagen mediante filtros de convolución, por ejemplo, utilizando el desenfoque, o el núcleo gaussiano y aplicar un umbral elegido para volver a binarizarla.

Si puedes tratar cada 1 como un punto, su posición en la secuencia como una coordenada, y puede hacer alguna métrica de distancia, podría utilizar casi todos los algoritmos de agrupación estándar que hay. Por ejemplo, podría utilizar agrupación jerárquica (elija un criterio de vinculación y un umbral), podría utilizar k-means o un EM con un modelo de mezcla gaussiana (elija el número de racimos que busca).

Pero no creo que, al final, puedas librarte sin tener que predefinir la sensibilidad del algoritmo al menos.