descubrir patrones periódicos en un gran conjunto de datos

Question

tengo una gran secuencia de tuplas en el disco en forma (t1, k1) (t2, k2) ... (tn, kn)

ti es una marca de tiempo creciente monótonamente y ki es una clave (suponga una cadena de longitud fija si es necesario). Ni ti ni ki tienen la garantía de ser únicos. Sin embargo, la cantidad de tis y kis únicos es enorme (millones). n en sí es muy grande (100 millones +) y el tamaño de k (aproximadamente 500 bytes) hace que sea imposible almacenar todo en la memoria.

Me gustaría encontrar apariciones periódicas de claves en esta secuencia.

Por ejemplo, si tengo la secuencia (1, a) (2, b) (3, c) (4, b) (5, a) (6, b) (7, d) (8, b) (9, a) (10, b)

El algoritmo debe emitir (a, 4) y (b, 2). Esto ocurre con un período de 4 yb ocurre con un período de 2.

Si construyo un hash de todas las claves y almaceno el promedio de la diferencia entre marcas de tiempo consecutivas de cada tecla y una desviación estándar del mismo , Podría hacer un pase e informar solo aquellos que tienen una desviación estándar aceptable (idealmente, 0). Sin embargo, requiere un cubo por clave única, mientras que en la práctica, podría tener muy pocos patrones realmente periódicos. ¿Alguna mejor manera?

Answer 1

Este es más o menos el motivo por el cual se inventaron Fourier transforms (Fast Fourier Transforms, etc.).

Está esencialmente transformando una secuencia del dominio de tiempo (o alguna dimensión similar) a frequency domain. Este es un problema muy antiguo, anterior a la aplicación de las computadoras, y existe un inmenso cuerpo de teoría sobre el tema. También vea discrete fourier transform.

EDITAR: Debería transformar sus valores k1, k2, ... de alguna manera, pero suponiendo que eso sea factible, este enfoque debería serlo también.

Answer 2

Puede usar el discreto autocorrelation para buscar los puntos y luego buscar las teclas. Las ventajas de la autocorrelación son que es un poco más fácil entender lo que sucede en el dominio discreto, y no tiene que preocuparse por mapear las claves para nada — simplemente use una función característica de dos teclas que es 1 cuando son iguales y 0 cuando son desiguales.

Answer 3

Si construyo un hash de todas las claves y tienda de la media de la diferencia entre las marcas de tiempo consecutivos de cada clave y una desviación std de la misma, que podría ser capaz de hacer un pase, y informe solo los que tienen una desviación estándar aceptable (idealmente, 0). Sin embargo, requiere un intervalo por cada clave única , mientras que en la práctica, I podría tener muy pocos patrones realmente periódicos . ¿Alguna mejor manera?

Personalmente, creo que esto es probablemente lo mejor que obtendrá a menos que pueda identificar más estructura al problema.

etiqueta

Answer 4

Vamos a un (fecha y hora, cadena) como tupla ( clave, valor). Algunas restricciones: 1. Existe un conjunto discreto de valores , es decir, la coincidencia entre apariciones periódicas de estos valores es exacta: aaabb ... aaabb, not aaabb ... aaabc. 2. El conjunto de todas las instancias de un valor se puede ajustar a la memoria.

Algoritmo: 1. Obtenga una lista completa de todos los valores únicos 2. Para cada valor único, obtenga todas las tuplas y genere una lista ordenada de marcas de tiempo. 3. Aplica un algoritmo para buscar patrones en estos datos. Idealmente una transformada discreta de Fourier no uniforme, o autocorrelación.

Answer 5

Usted realmente tiene dos problemas distintos:

1. tiene m señales diferentes en sus datos, definidos por las claves únicas m. Debe separar cada señal y almacenar por separado.

2. dada una de estas señales únicas, debe determinar si es periódica, esta es una aplicación de autocorrelación o la Transformada de Fourier Discreta, cualquiera que prefiera. Por ejemplo, el DFT le proporciona los coeficientes de las funciones periódicas de interpolación de sus datos. Si solo un coeficiente en el DFT no es cero, hay un período claro.

Si se aplica la DFT o autocorrelación de los datos sin separar las señales obtendrá una problema que se agrava cuando no se sabe si una de las señales "periódicas" encontradas se compone de una señal única o varias .