He estado buscando el algoritmo más eficiente (transmisión ??) que me dice los elementos 'k' que ocurren con mayor frecuencia en un flujo de datos en cualquier momento. Esta publicación: Los algoritmos de flujo de datos "Divide y vencerás" me interesaron.
Por ejemplo, supongamos que hay números: (4,3,5,1,6,2,4,3,3,8,9,1) y consulto los 3 números más frecuentes (por ejemplo), entonces debería obtener (3,4,1) como respuesta.
Intenté buscar en línea, pero no pude encontrar ningún lugar que ofrezca un enfoque y diga que es lo mejor. Una solución trivial sería usar un montón o un árbol binario equilibrado, pero creo que hay una mejor manera y quería saber si está documentado en alguna parte.
Editar: estoy buscando un algoritmo que siempre dé la respuesta correcta en lugar de un algoritmo de aplicación (muchos de los cuales aparecen en los resultados de búsqueda) que dependen de la distribución de datos de una manera u otra
fuente
Respuestas:
fuente
También recomiendo leer la sección 8.1.3 "Minería de patrones frecuentes en flujos de datos" del siguiente libro:
Jiawei Han, Micheline Kamber. Minería de datos --- Conceptos y técnicas, segunda edición, Morgan Kaufmann Publishers , 2006.
Introduce un algoritmo, conocido como Conteo con pérdida , que se aproxima a elementos frecuentes (elementos cuyo soporte está por encima de un mínimo de soporte ) con precisión arbitraria.
No es exactamente lo que quieres, pero pensé que podría ayudar.
fuente