Rejillas adaptativas para la clustering de conjuntos de datos masivos

El clustering es un problema clave en la minería de datos. La técnica basada en densidad y rejillas es una forma popular de encontrar clústeres en un amplio espacio multidimensional donde los clústeres se consideran regiones densas en comparación con su entorno. Los valores de los atributos y los rangos de estos atributos caracterizan los clústeres. Tamaños de rejilla finos conducen a una enorme cantidad de cálculo, mientras que tamaños de rejilla gruesos resultan en una pérdida de calidad de los clústeres encontrados. Además, tamaños de rejilla variados resultan en descubrir clústeres con diferentes descripciones de clústeres. La técnica de rejillas adaptativas permite usar rejillas basadas en la distribución de datos y no requiere que el usuario especifique ningún parámetro, como el tamaño de la rejilla o los umbrales de densidad. Además, los clústeres podrían estar incrustados en un subespacio de un espacio de alta dimensión. Proponemos un algoritmo modificado de clustering en subespacios de abajo hacia arriba para descubrir clústeres en todos los posibles subespacios. Nuestro método se escala linealmente con la dimensionalidad de los datos y el tamaño del conjunto de datos. Resultados experimentales en una amplia variedad de conjuntos de datos sintéticos y reales demuestran la efectividad de las rejillas adaptativas y el efecto del algoritmo de clustering en subespacios modificado. Nuestro algoritmo explora al menos un orden de magnitud más de subespacios que el algoritmo original y el uso de rejillas adaptativas ofrece, en promedio, una aceleración de dos órdenes de magnitud en comparación con el método que especifica el tamaño de rejilla y el umbral por parte del usuario.