Algoritmo de agrupación secuencial

Question

Quiero agrupar elementos en un array. La diferencia crucial con respecto a un algoritmo de clustering normal es que el orden de los elementos es significativo. Por ejemplo, si miramos una simple secuencia de números como esta:

1.1, 1.2, 1.0, 3.3, 3.3, 2.9, 1.0, 1.1, 3.0, 2.8, 3.2

Es obvio que hay dos clusters ahí (1,1, 1,2, 1,0, 1,0, 1,1) y (3,3, 3,3, 2,9, 3,0, 2,8, 3,2). Lo que quiero es encontrar grupos secuenciales de elementos similares

(1.1, 1.2, 1.0), (3.3, 3.3, 2.9), (1.0, 1.1), (3.0, 2.8, 3.2)

4 en este caso. Por supuesto, puedo ejecutar alguna variante de un algoritmo de agrupación normal y luego dividir los clusters según los índices de los elementos, pero probablemente haya una forma más sencilla de hacerlo.

¿Hay algún algoritmo que pueda utilizar para esto?

Answer 1

La agrupación restringida mantiene el orden de los datos. Hay un paquete en R llamado 'rioja' que implementa esto en la función 'chclust'.

Sin embargo, el procedimiento no es demasiado complejo:

1. Calcular la distancia entre puntos
2. Encuentra la menor distancia entre puntos adyacentes
3. Promediar el valor de los dos puntos para generar un único valor
4. Vuelve a escupir la lista y empieza desde uno hasta que tengas un solo punto.

Necesitas mantener algún tipo de estructura de árbol, pero con algo de experiencia en programación elemental deberías ser capaz de hacerlo.