Clustering diferencialmente privado mediante la generación de sinopsis privadas de datos

Abstract

Actualmente estamos en una era donde la generación de datos masivos es constante y crucial para diferentes sectores como empresas, gobiernos y centros de investigación. Esta realidad ha impulsado el desarrollo del campo de la minería de datos, enfocado en extraer información valiosa de grandes volúmenes de datos. En particular, se destaca la importancia del agrupamiento (clustering) de datos y el algoritmo k-means, un método para la creación de grupos de datos, aunque enfrenta desafíos como la dificultad en encontrar el agrupamiento óptimo, un problema muy difícil (NP-Hard).

Existe una creciente preocupación por el manejo de datos sensibles, especialmente en lo que respecta a la privacidad en el uso de algoritmos de clustering como k-means. Para abordar esto, se han incorporado técnicas de privacidad diferencial. En pocas palabras, estas técnicas modifican el algoritmo para enmascarar la contribución de cada individuo.

Nuestro enfoque se basa en crear una aproximación de los datos que tenga garantías de privacidad. La denominaremos sinopsis privada. Esta sinopsis privada se emplea como entrada para el algoritmo k-means, el cual preservara las garantías de privacidad. La elaboración de la sinopsis privada se llevará a cabo mediante técnicas de particionamiento espacial y conteo privado. En otras palabras, contamos de manera privada cuantos puntos hay en regiones del espacio (definidas por una partición) y este resultado lo representamos como un conjunto de puntos ponderados, lo que seria la sinopsis privada.

Para evaluar la eficacia de nuestros algoritmos de generación de sinopsis privadas, realizamos una comparativa entre los resultados obtenidos mediante k-means aplicados a sinopsis privadas y aquellos obtenidos mediante algoritmos de clustering, tanto privados como no privados. Investigamos la eficiencia de distintos tipos de particionadores en combinación con un análisis exhaustivo de hiperparámetros, incluyendo aspectos como el presupuesto de privacidad, las estrategias para su distribución, los umbrales de la condición de parada y la profundidad máxima en los pasos recursivos.

Este estudio propuso y evaluó distintas estrategias de particionamiento del espacio para crear sinopsis privadas. Se descubrió que, aunque no siempre superaron los benchmarks, los métodos de particionamiento multi-cuantil y uniforme resultaron ser prometedores, sobre todo al ajustar adecuadamente los hiperparámetros. Los resultados obtenidos con estos particionadores son alentadores, mostrándose competentes en términos de privacidad y precisión