Detectar grupos en una secuencia binaria

8

Tengo una secuencia binaria como 11111011011110101100000000000100101011011111101111100000000000011010100000010000000011101111

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

ingrese la descripción de la imagen aquí

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

¿Alguna idea?

classification clustering data-mining pattern-recognition binary-data wnstnsmth
fuente

Respuestas:

5

Evitaría llamarlos "grupos". Con esta terminología terminas distrayéndote con técnicas multidimensionales desde la minería de datos todo el tiempo.

Su problema es una configuración unidimensional mucho más simple. E incluso más simple: ni siquiera tiene coordenadas, sino una matriz de ceros y unos.

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

Entonces, al final, necesitarás tener un parámetro. Tiene varias opciones: tamaños de espacio absolutos, tamaños de espacio 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. Entonces son 21 celdas, el valor será de 0 a 21. Ahora busque un mínimo local. Aumente el tamaño de la ventana, si comienza a dividir ejecuciones que aún no desea dividir.

HA SALIDO - Anony-Mousse
fuente
Gracias. La sugerencia con el kernel y el mínimo local es en realidad similar a lo que propuso @EngrStudent, ¿verdad? Aún no entiendo completamente lo que significa. ¿Cómo puedo incluso buscar un mínimo local en una máquina? Es decir, ¿cómo puedo calcular la primera derivada de la "función" sin conocer la función en sí, sino solo los valores?
wnstnsmth
Sí, eso probablemente es lo mismo que sugirió EngrStudent. La estimación de la densidad del grano es una técnica muy estándar para suavizar. ¡También se usa por todas partes en el procesamiento de imágenes! Es un mínimo local si no hay un valor vecino más pequeño ... es tan simple como eso si tiene un conjunto de datos discreto.
HA SALIDO - Anony-Mousse
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ían ser útiles aquí. Si lo estuviera haciendo, vería una 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 "Redes neuronales para el reconocimiento de patrones" por Christopher Bishop. (1995)

Estudiante
fuente
1
la primera derivada numérica con respecto al índice es "diff". Entonces, si tiene muchos "unos" seguidos, la derivada será ceros. Si tiene unos escasos, cada vez que cambie, la diferencia será mayor. Podría usar EWMA como un núcleo de mans pobre. en.wikipedia.org/wiki/Exponential_smoothing . ¿Como funciona? Hace un promedio ponderado de una ventana de valores. Una función del núcleo hace algo relacionado pero un poco más complejo. Toma una ventana, a veces una ventana mucho más ancha, y luego calcula una función basada en los valores que contiene. A veces la función se ve como un pdf.
EngrStudent
1
Sumar los valores diff y raw le da información cuando son escasos y cuando son densos.
EngrStudent
¿Podría explicar su respuesta y comentar con una pequeña secuencia de ejemplo? Tengo un problema muy similar.
Arun Jose
El valor absoluto de un diff es un detector de borde. Si tiene una secuencia como 000111000, y toma la diferencia, obtiene 00100 (-1) 00. La ubicación del 1 en el diferencial le muestra el borde ascendente y el -1 muestra el borde descendente. Si tomaras el valor absoluto de la diferencia y luego sumaras, obtendrías 2 aristas. Si tenía la secuencia 010101010, entonces su diferencia absoluta es 11111111, que suma 8 aristas. Hay un recuento de bordes sustancialmente mayor. Si NO usa el abs diff y lo usa en una suma acumulada, le dirá cuántos 1 o cuántos 0 tiene en una fila.
EngrStudent
¿Bajo qué criterio diría que una serie de 1 termina y comienza? ¿Cómo se determina el tamaño de la ventana?
Arun Jose
0

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

La naturaleza de la imagen de entrada sugiere un filtro morfológico para suavizar las regiones, por ejemplo, cierre . Debería elegir el elemento de estructuración que determina la "vinculación" de los clústeres. Al final, esto es bastante similar a su enfoque. También puede suavizar la imagen con filtros de convolución, por ejemplo, con desenfoque o núcleo gaussiano y aplicar un umbral elegido para volver a binarizarlo.

Si puede tratar cada 1punto como un punto, su posición en la secuencia como una coordenada, y puede completar alguna métrica de distancia, podría usar casi todos los algoritmos de agrupamiento estándar que existen. Por ejemplo, podría usar la agrupación jerárquica (elija un criterio de vinculación y un umbral), podría usar k-means o un EM con un modelo de mezcla gaussiana (elija la cantidad de grupos que está buscando).

Pero no creo que eventualmente pueda escapar sin tener que predefinir la sensibilidad del algoritmo al menos.

moooeeeep
fuente