Détection de clusters dans une séquence binaire

J'ai une séquence binaire telle que 11111011011110101100000000000100101011011111101111100000000000011010100000010000000011101111

Où les grappes de la plupart des 1 sont suivies d'un plus grand nombre de zéros, comme dans l'image ci-dessous (noir signifie 1):

Je voudrais appliquer une technique (de préférence en R ou en Python) où je peux détecter automatiquement ces grappes de 1 et produire des étendues (désignées comme des lignes rouges dans l'image). Je sais que l'on pourrait le faire avec un seuil, c'est-à-dire en disant que deux clusters doivent être séparés d'au moins n 0 pour être des clusters, mais je me demande s'il existe d'autres méthodes établies qui n'utilisent pas de seuils prédéfinis .

Une idée?

J'éviterais de les appeler "clusters". Avec cette terminologie, vous vous retrouvez constamment distrait par les techniques multidimensionnelles de l'exploration de données.

Votre problème est un cadre unidimensionnel beaucoup plus simple. Et encore plus simple: vous n'avez même pas de coordonnées mais un tableau de zéros et de uns.

Il n'y aura pas une seule taille unique solution pour votre problème jamais . Parce qu'un utilisateur peut vouloir lire des "codes-barres" à très haute résolution, tandis que l'autre utilisateur a beaucoup de bruit.

Donc, à la fin, vous aurez besoin d'un paramètre. Vous avez plusieurs choix: tailles d'écart absolues, tailles d'écart relatives, bande passante du noyau, etc.

Une approche très simple "basée sur le noyau" consisterait à mapper chaque pixel sur le nombre de pixels défini dans -10 ... + 10. Donc, c'est 21 cellules, la valeur sera de 0 à 21. Recherchez maintenant un minimum local. Augmentez la taille de la fenêtre, si elle commence à fractionner des cycles que vous ne vouliez pas encore fractionner.

La référence 1 aux pages 49-55 contient une belle section sur les méthodes basées sur le noyau qui pourrait être utile ici. Si je le faisais, je regarderais une somme pondérée des valeurs réelles et de leur dérivée première, car cela pourrait être un meilleur indicateur de "l'information".

Référence: http://amzn.com/0198538642 "Neural Networks for Pattern Recognition" par Christopher Bishop. (1995)

Le problème présente une certaine similitude avec le traitement d'image. Vous avez une image binaire d'une hauteur d'un pixel et souhaitez réaliser une sorte de segmentation .

La nature de l'image d'entrée suggère un filtre morphologique pour lisser les régions, par exemple la fermeture . Vous devez choisir l'élément structurant qui détermine ainsi le "lien" des clusters. En fin de compte, cela est assez similaire à votre approche. Vous pouvez également lisser l'image en utilisant des filtres de convolution, par exemple en utilisant le flou ou le noyau gaussien et en appliquant un seuil choisi pour la re-binariser.

Si vous pouvez traiter chaque 1point comme un point, sa position dans la séquence comme une coordonnée, et peut constituer une métrique de distance, vous pouvez utiliser à peu près tous les algorithmes de clustering existants. Par exemple, vous pouvez utiliser le clustering hiérarchique (choisissez un critère de liaison et un seuil), vous pouvez utiliser k-means ou un EM avec un modèle de mélange gaussien (choisissez le nombre de clusters que vous recherchez).

Mais je ne pense pas, vous pourriez éventuellement vous en sortir sans avoir à prédéfinir la sensibilité de l'algorithme au moins.