Hispanopedia Wiki
Articulo de referencia

Agrupamiento de flujos de datos

En informática , la agrupación de flujos de datos se define como la agrupación de datos que llegan de forma continua, como registros telefónicos, datos multimedia, transacciones...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , la agrupación de flujos de datos se define como la agrupación de datos que llegan de forma continua, como registros telefónicos, datos multimedia, transacciones financieras, etc. La agrupación de flujos de datos se estudia habitualmente como un algoritmo de transmisión y el objetivo es, dada una secuencia de puntos, construir una buena agrupación del flujo, utilizando una pequeña cantidad de memoria y tiempo.

Historia

La agrupación de flujos de datos ha atraído recientemente la atención para aplicaciones emergentes que involucran grandes cantidades de datos en tiempo real. Para la agrupación, k-means es una heurística ampliamente utilizada, pero también se han desarrollado algoritmos alternativos, como k-medoids , CURE y el popular [ cita requerida ] BIRCH . Para los flujos de datos, uno de los primeros resultados apareció en 1980 [1], pero el modelo se formalizó en 1998. [2]

Definición

El problema de la agrupación de flujos de datos se define como:

Entrada: una secuencia de n puntos en el espacio métrico y un entero k .
Salida: k centros en el conjunto de los n puntos de modo de minimizar la suma de las distancias desde los puntos de datos hasta sus centros de conglomerados más cercanos.

Esta es la versión de streaming del problema de la k-mediana.

Algoritmos

ARROYO

STREAM es un algoritmo para agrupar flujos de datos descrito por Guha, Mishra, Motwani y O'Callaghan [3] que logra una aproximación de factor constante para el problema k-Median en una sola pasada y utilizando un espacio pequeño.

Teorema  —  STREAM puede resolver el problema k -Mediana en un flujo de datos en una sola pasada, con tiempo O ( n 1+ e ) y espacio θ ( n ε ) hasta un factor 2 O(1/ e ) , donde n es el número de puntos y ⁠ ⁠ mi < 1 / 2 {\estilo de visualización e<1/2} .

Para entender STREAM, el primer paso es demostrar que la agrupación puede tener lugar en espacios pequeños (sin importar el número de pasadas). Small-Space es un algoritmo de divide y vencerás que divide los datos, S , en fragmentos, agrupa cada uno de ellos (usando k -medias) y luego agrupa los centros obtenidos. ℓ {\displaystyle \ell}

Representación del algoritmo de espacio pequeño

Algoritmo de espacio pequeño (S)

  1. Dividir S en partes disjuntas . ℓ {\displaystyle \ell} incógnita 1 , … , incógnita ℓ {\displaystyle X_{1},\ldots ,X_{\ell }}
  2. Para cada i , encuentre los centros Oh ( a ) {\displaystyle O(k)} en X i . Asigna cada punto en X i a su centro más cercano.
  3. Sean X' los centros obtenidos en (2), donde cada centro c está ponderado por el número de puntos asignados a él. Oh ( ℓ a ) {\displaystyle O(\ell k)}
  4. Agrupa X' para encontrar k centros.

Donde, si en el Paso 2 ejecutamos un algoritmo de aproximación bicriterio que genera ( a , b ) {\estilo de visualización (a,b)} como máximo ak medianas con un costo como máximo b veces la solución k-Mediana óptima y en el Paso 4 ejecutamos un algoritmo de aproximación c entonces el factor de aproximación del algoritmo Small-Space() es ⁠ ⁠ . También podemos generalizar Small-Space para que se llame recursivamente a sí mismo i veces en un conjunto sucesivamente más pequeño de centros ponderados y logre una aproximación de factor constante al problema de k -mediana. 2 do ( 1 + 2 b ) + 2 b {\estilo de visualización 2c(1+2b)+2b}

El problema con el Small-Space es que el número de subconjuntos en los que particionado S es limitado, ya que tiene que almacenar en memoria las medianas intermedias en X . Por lo tanto, si M es el tamaño de la memoria, necesitamos particionar S en subconjuntos de modo que cada subconjunto quepa en la memoria, ( ) y de modo que los centros ponderados también quepan en la memoria, . Pero tal cosa no siempre existe. ℓ {\displaystyle \ell} ℓ {\displaystyle \ell} norte / ℓ {\displaystyle n/\ell} ℓ a {\displaystyle \ell k} ℓ a < METRO {\displaystyle \ell k<M} ℓ {\displaystyle \ell}

El algoritmo STREAM resuelve el problema de almacenar medianas intermedias y logra mejores requisitos de tiempo y espacio de ejecución. El algoritmo funciona de la siguiente manera: [3]

  1. Ingrese los primeros m puntos; utilizando el algoritmo aleatorio presentado en [3], redúzcalos a ( Oh ( a ) {\displaystyle O(k)} digamos 2 k ) puntos .
  2. Repita lo anterior hasta que hayamos visto m 2 /(2 k ) de los puntos de datos originales. Ahora tenemos m medianas intermedias.
  3. Utilizando un algoritmo de búsqueda local , agrupe estas m medianas de primer nivel en 2 k medianas de segundo nivel y continúe.
  4. En general, mantener como máximo m medianas de nivel i y, al ver m , generar 2 k medianas de nivel i + 1, con el peso de una nueva mediana como la suma de los pesos de las medianas intermedias asignadas a ella.
  5. Cuando hemos visto todos los puntos de datos originales, agrupamos todas las medianas intermedias en k medianas finales, utilizando el algoritmo dual primal. [4]

Otros algoritmos

Otros algoritmos conocidos utilizados para la agrupación de flujos de datos son:

  • BIRCH : [5] construye una estructura de datos jerárquica para agrupar de forma incremental los puntos entrantes utilizando la memoria disponible y minimizando la cantidad de E/S requerida. La complejidad del algoritmo es ⁠ ⁠ Oh ( norte ) {\displaystyle O(N)} ya que una pasada es suficiente para obtener una buena agrupación (aunque los resultados se pueden mejorar permitiendo varias pasadas).
  • COBWEB : [6] [7] es una técnica de agrupamiento incremental que mantiene un modelo de agrupamiento jerárquico en forma de árbol de clasificación . Para cada nuevo punto, COBWEB desciende por el árbol, actualiza los nodos a lo largo del camino y busca el mejor nodo para colocar el punto (utilizando una función de utilidad de categoría ).
  • C2ICM: [8] construye una estructura de agrupamiento de partición plana seleccionando algunos objetos como semillas/iniciadores de clúster y se asigna una no semilla a la semilla que proporciona la mayor cobertura; la adición de nuevos objetos puede introducir nuevas semillas y falsificar algunas semillas antiguas existentes; durante el agrupamiento incremental, los nuevos objetos y los miembros de los clústeres falsificados se asignan a una de las semillas nuevas/antiguas existentes.
  • CluStream: [9] utiliza micro-cúmulos que son extensiones temporales del vector de características del clúster BIRCH [5] , de modo que puede decidir si un micro-cúmulo se puede crear, fusionar u olvidar basándose en el análisis de la suma cuadrada y lineal de los puntos de datos y marcas de tiempo de los micro-cúmulos actuales, y luego en cualquier punto en el tiempo uno puede generar macro-cúmulos agrupando estos micro-cúmulos usando un algoritmo de agrupamiento fuera de línea como K-Means , produciendo así un resultado de agrupamiento final.

Referencias

  1. ^ Munro, J.; Paterson, M. (1980). "Selección y ordenación con almacenamiento limitado". Ciencias de la computación teórica . 12 (3): 315– 323. doi : 10.1016/0304-3975(80)90061-4 .
  2. ^ Henzinger, M.; Raghavan, P.; Rajagopalan, S. (agosto de 1998). "Computación en flujos de datos". Digital Equipment Corporation . TR-1998-011. CiteSeerX 10.1.1.19.9554 . 
  3. ^ abc Guha, S.; Mishra, N.; Motwani, R.; O'Callaghan, L. (2000). "Agrupamiento de flujos de datos". Actas del 41.º Simposio anual sobre fundamentos de la informática . pp.  359– 366. CiteSeerX 10.1.1.32.1927 . doi :10.1109/SFCS.2000.892124. ISBN  0-7695-0850-2. Número de identificación del sujeto  2767180.
  4. ^ Jain, K.; Vazirani, V. (1999). Algoritmos de aproximación primal-dual para problemas de ubicación de instalaciones métricas y k-medianas. Focs '99. pp. 2–. ISBN 9780769504094. {{cite book}}: |journal=ignorado ( ayuda )
  5. ^ ab Zhang, T.; Ramakrishnan, R.; Linvy, M. (1996). "BIRCH: Un método de agrupamiento de datos eficiente para bases de datos muy grandes". ACM SIGMOD Record . 25 (2): 103– 114. doi : 10.1145/235968.233324 .
  6. ^ Fisher, DH (1987). "Adquisición de conocimiento mediante agrupamiento conceptual incremental". Aprendizaje automático . 2 (2): 139– 172. doi : 10.1023/A:1022852608280 .
  7. ^ Fisher, DH (1996). "Optimización iterativa y simplificación de agrupaciones jerárquicas". Journal of AI Research . 4 . arXiv : cs/9604103 . Bibcode :1996cs........4103F. CiteSeerX 10.1.1.6.9914 . 
  8. ^ Can, F. (1993). "Agrupamiento incremental para procesamiento dinámico de información". ACM Transactions on Information Systems . 11 (2): 143– 164. doi : 10.1145/130226.134466 . S2CID  1691726.
  9. ^ Aggarwal, Charu C.; Yu, Philip S.; Han, Jiawei; Wang, Jianyong (2003). "Un marco para la agrupación de flujos de datos en evolución" (PDF) . Actas de la conferencia VLDB de 2003 : 81– 92. doi :10.1016/B978-012722442-8/50016-1. ISBN 9780127224428.S2CID2354576  .​
Obtenido de "https://es.wikipedia.org/w/index.php?title=Agrupamiento_de_flujos_de_datos&oldid=1181464782"