Cómo colocar un elefante en una hoja de cálculo

Tabla de enlaces

Resumen y 1 Introducción

2 Trabajos preliminares y relacionados

2.1 Sobre las estrategias de muestreo

2.2 Otras estrategias de conjunto básico

2.3 Conjuntos de núcleos para aplicaciones de bases de datos

2.4 Incrustaciones de árboles cuádruples

3 conjuntos de núcleos rápidos

4 Reducir el impacto de la propagación

4.1 Cálculo de un límite superior rudimentario

4.2 De la solución aproximada a la dispersión reducida

5 Compresión rápida en la práctica

5.1 Objetivo y alcance del análisis empírico

5.2 Configuración experimental

5.3 Evaluación de estrategias de muestreo

5.4 Configuración de transmisión y conclusiones del apartado 5.5

6 Conclusión

7 Agradecimientos

8 Pruebas, pseudocódigo y extensiones y 8.1 Prueba del corolario 3.2

8.2 Reducción de k-medias a k-medianas

8.3 Estimación del costo óptimo en un árbol

8.4 Extensiones del algoritmo 1

Referencias

Abstracto

Estudiamos los límites teóricos y prácticos del tiempo de ejecución de la agrupación en clústeres mediante k-medias y k-medianas en grandes conjuntos de datos. Dado que, efectivamente, todos los métodos de agrupación en clústeres son más lentos que el tiempo que lleva leer el conjunto de datos, el enfoque más rápido es comprimir rápidamente los datos y realizar la agrupación en clústeres en la representación comprimida. Desafortunadamente, no existe una mejor opción universal para comprimir el número de puntos: mientras que el muestreo aleatorio se ejecuta en tiempo sublineal y los conjuntos centrales brindan garantías teóricas, el primero no garantiza la precisión, mientras que el segundo es demasiado lento a medida que aumenta el número de puntos y clústeres. De hecho, se ha conjeturado que cualquier construcción de conjuntos centrales basada en la sensibilidad requiere un tiempo superlineal en el tamaño del conjunto de datos.

Analizamos esta relación mostrando primero que existe un algoritmo que obtiene conjuntos de núcleos mediante un muestreo de sensibilidad en un tiempo efectivamente lineal, dentro de los factores logarítmicos del tiempo que lleva leer los datos. Cualquier enfoque que mejore esto significativamente debe recurrir a heurísticas prácticas, lo que nos lleva a considerar el espectro de estrategias de muestreo en conjuntos de datos reales y artificiales en los entornos estáticos y de transmisión. A través de esto, mostramos las condiciones en las que los conjuntos de núcleos son necesarios para preservar la validez del grupo, así como los entornos en los que las estrategias de muestreo más rápidas y rudimentarias son suficientes. Como resultado, proporcionamos un modelo teórico y práctico integral para un agrupamiento efectivo independientemente del tamaño de los datos. Nuestro código está disponible públicamente en la fuente y tiene scripts para recrear los experimentos.

1 Introducción

El analista de datos moderno no tiene escasez de algoritmos de agrupamiento para elegir, pero, dado el tamaño cada vez mayor de los conjuntos de datos relevantes, muchos son a menudo demasiado lentos para ser útiles en la práctica. Esto es particularmente relevante para las canalizaciones de big data, donde los algoritmos de agrupamiento se utilizan comúnmente para la compresión. El objetivo es reemplazar un conjunto de datos muy grande por uno más pequeño y manejable para tareas posteriores, con la esperanza de que represente bien la entrada original. El algoritmo de Lloyd [49] se introdujo precisamente por esta razón y minimiza el error de cuantificación: la suma de la distancia al cuadrado de cada punto de entrada a su representante en el conjunto de datos comprimido. Posiblemente el algoritmo de agrupamiento más popular, Lloyd se ejecuta en múltiples iteraciones hasta la convergencia y cada iteración requiere un tiempo O(ndk), donde n es el número de puntos, d es el número de características y k es el número de clústeres, o el tamaño de la compresión deseada. Para tales aplicaciones, la cantidad de puntos puede ser fácilmente de cientos de millones y, dado que la calidad de la compresión aumenta con k, los objetivos estándar pueden tener k en miles [41, 4]. En tales entornos, cualquier algoritmo O(ndk) es prohibitivamente lento.

Ejemplos como estos han impulsado el surgimiento de algoritmos de big data que proporcionan mejoras teóricas y prácticas en el tiempo de ejecución. Sin embargo, las perspectivas de solidez teórica y eficacia práctica a menudo están en desacuerdo entre sí. Por un lado, las garantías teóricas brindan seguridad de que el algoritmo funcionará independientemente de las entradas desafortunadas que reciba. Por otro lado, puede resultar difícil convencerse a uno mismo de implementar el algoritmo teóricamente óptimo cuando existen métodos más rudimentarios que se ejecutan más rápido y funcionan bien en la práctica.

Dado que los conjuntos de datos pueden ser grandes en cuanto a la cantidad de puntos n y/o la cantidad de características d, los métodos de big data deben mitigar los efectos de ambos. Con respecto al espacio de características, la cuestión está efectivamente cerrada ya que las proyecciones aleatorias son rápidas (se ejecutan en un tiempo efectivamente lineal), prácticas de implementar [50] y brindan garantías estrictas sobre el tamaño y la calidad de la incrustación. La perspectiva es menos clara cuando se reduce la cantidad de puntos n, y hay dos paradigmas separados que brindan cada uno ventajas distintas. Por un lado, tenemos el muestreo uniforme, que se ejecuta en un tiempo sublineal pero puede omitir subconjuntos importantes de los datos y, por lo tanto, solo puede garantizar la precisión bajo ciertas suposiciones sólidas sobre los datos [45]. Por otro lado, las estrategias de muestreo más precisas brindan la garantía sólida del conjunto central, en la que el costo de cualquier solución en los datos comprimidos está dentro de un factor ε del costo de esa solución en el conjunto de datos original [25].

Nuestras contribuciones Estudiamos ambos paradigmas (muestreo uniforme y coresets fuertes) con respecto a un problema clásico: la compresión para los objetivos k-medias y k-medianas. Mientras que el muestreo uniforme proporciona una velocidad óptima pero no garantiza la precisión en el peor de los casos, todas las construcciones de coresets disponibles tienen un tiempo de ejecución de al menos Ω˜(nd + nk) cuando se obtienen límites estrictos en el número mínimo de muestras requeridas para una compresión precisa.

Es fácil demostrar que cualquier algoritmo que logre una garantía de compresión debe leer el conjunto de datos completo[1]. Por lo tanto, una pregunta abierta clara es qué garantías se pueden lograr en un tiempo lineal o casi lineal. De hecho, los algoritmos de muestreo rápido disponibles actualmente para la agrupación [6, 5] no pueden lograr garantías sólidas de coreset. Recientemente, [31] propuso un método para coresets sólidos que se ejecuta en un tiempo O˜(nd + nk) y conjeturó que esto es óptimo para k-mediana y k-medias.

Si bien este límite es efectivamente óptimo para valores pequeños de k, existen muchas aplicaciones, como la visión por computadora [34] o la equidad algorítmica [18], donde la cantidad de clústeres puede ser mayor que la cantidad de características en varios órdenes de magnitud. En tales entornos, la cuestión de los conjuntos de núcleos óptimos en el tiempo permanece abierta. Dado que la cuestión de determinar un conjunto de núcleos de tamaño óptimo se ha cerrado recientemente [25, 28, 44], este es posiblemente el principal problema abierto en la investigación de conjuntos de núcleos para la agrupación basada en el centro. Resolvemos esto mostrando que existe un algoritmo fácil de implementar que construye conjuntos de núcleos en tiempo O˜(nd), solo factores logarítmicos de distancia del tiempo que lleva leer el conjunto de datos.

Sin embargo, esto no arroja luz sobre el panorama de los algoritmos de muestreo para la agrupación en la práctica. Aunque nuestro algoritmo logra un tiempo de ejecución y una compresión óptimos, es posible que otros métodos más rudimentarios sean igualmente viables para todos los fines prácticos. Lo planteamos formalmente en la siguiente pregunta: ¿Cuándo son necesarios conjuntos de núcleos con k-medias y k-medianas óptimos y cuál es el equilibrio práctico entre la velocidad y la precisión de los conjuntos de núcleos?

Para responder a esta pregunta, realizamos una comparación exhaustiva en todo el espectro de algoritmos de muestreo que son más rápidos que nuestro método propuesto. A través de esto, verificamos que, si bien estos métodos más rápidos son lo suficientemente precisos en muchos conjuntos de datos del mundo real, existen distribuciones de datos que causan fallas catastróficas para cada uno de ellos. De hecho, estos casos solo se pueden evitar con un método de conjunto de núcleos fuerte. Por lo tanto, si bien muchos entornos prácticos no requieren la garantía completa del conjunto de núcleos, no se pueden tomar atajos si se quiere confiar en su compresión. Verificamos que esto se extiende al paradigma de transmisión y se aplica a los enfoques de agrupamiento descendente.

En resumen, nuestras aportaciones son las siguientes:

• Demostramos que se pueden obtener conjuntos de núcleos sólidos para k-medias y k-medianas en tiempo O˜(nd). Esto resuelve una conjetura sobre el tiempo de ejecución necesario para conjuntos de núcleos de k-medias [31] y es teóricamente óptimo hasta factores logarítmicos.

• Mediante un análisis exhaustivo de conjuntos de datos, tareas y paradigmas de transmisión y no transmisión, verificamos que existe un equilibrio necesario entre velocidad y precisión entre los métodos de muestreo de tiempo lineal y sublineal. Esto proporciona al profesional de la agrupación en clústeres un modelo sobre cuándo utilizar cada algoritmo de compresión para obtener resultados de agrupación en clústeres efectivos en el menor tiempo posible.