Enfoques de minería de datos distribuida

En la tesis de grado de Mamani, publicada el año 2015 con el título “Aplicación de la minería de datos distribuida usando algoritmos de agrupamiento de k-medias para mejorar la calidad de servicios de las organizaciones modernas” se describen los siguientes algoritmos asociados al enfoque de minería de datos distribuida: (1) Algoritmo k-medias; (2) Modelo base; (3) Densidad en malla; (4) Jerárquicos; (5) Agrupamiento P2P; (6) Algoritmo k-medias P2P. Estos algoritmos se describen a continuación.

Para el algoritmo “k-medias” se consideran los siguientes pasos: (1) Se eligen de manera aleatoria k centroides. (2) Los centroides son enviados a todos los nodos participantes; luego se realiza el agrupamiento k-medias en cada nodo. (3) Cada nodo extrae información estadística de los elementos de sus grupos. (4) Las estadísticas son transferidas hacia un controlador central quien se encargara de consolidar los modelos provenientes de los nodos locales. El hecho de transferir solo información estadística hacia un nodo central y no el conjunto de datos completo permite mantener la confidencialidad y seguridad de la información. Una de las desventajas de este modelo se basa en el hecho de tener que enviar en forma continua la información estadística de los nodos locales hasta lograr convergencia en los resultados lo cual puede generar bastante tráfico en la red y ralentizar el proceso. El algoritmo de “modelo base” utiliza agrupamiento de maximización de expectativas a nivel local, que es similar al algoritmo “k-medias”, excepto que la decisión sobre el agrupamiento final se basa en el uso de funciones adicionales como la función gaussiana. Inicialmente, el sistema local procesa sus elementos individuales, mediante el algoritmo de agrupamiento de maximización de expectativas local, a continuación cada grupo es modelado como una suma de funciones gaussianas. Las funciones resultantes son transferidas a un coordinador central, quien se encarga de reunir las funciones para generar la función global sobre la densidad de la probabilidad de la imagen global. Esta información se envía a cada nodo local con la finalidad que cada uno de ellos pueda utilizarla y reevaluar sus resultados de ser necesario. El algoritmo emplea buenas medidas de confidencialidad y precisión. Sin embargo tiene un problema básico que consiste en que dos grandes grupos conectados mediante un componente con densidad mínima puede resultar constituyéndose en un mismo grupo sin que lo sea.

El algoritmo “densidad en malla” hace uso del algoritmo “clique” con ciertas mejoras enfocadas en el agrupamiento distribuido. El enfoque basado en densidad para el agrupamiento distribuido consiste en que de manera inicial cada atributo definido en la consulta del usuario es explorado y en lugar de definir ciertos valores globales para el tamaño de una malla estos son determinados dinámicamente basándose en información estadística. Los grupos son representados como mallas rellenadas y debido al proceso dinámico de cuadricular el área se tiene que en zonas de intensa densidad la granularidad es bastante fina y en zonas de baja población la densidad es gruesa. El algoritmo genera grupos sólidos, sin embargo estos asumen que los datos están centralizados en un repositorio desde el cual se distribuye a todos los nodos. El algoritmo “jerárquico” es bastante similar al enfoque basado en “densidad en malla”. La idea principal que persigue este algoritmo es empezar con un conjunto de puntos distintos, cada uno formando su propio grupo. A continuación se empieza recursivamente a unir dos grupos cercanos hasta asegurar que todos los puntos lleguen a pertenecer a un mismo grupo. De este modo en los algoritmos jerárquicos paralelos se utilizan dendogramas para crear grupos y sus distancias mínimas y máximas entre ellos. La unión de grupos se basa en distancias mínimas las cuales son transmitidas junto a un objeto identificador. La propiedad reducción es utilizada para crear el modelo global.

Sunny y Thampi, en el artículo publicado el año 2010 con el título “Estudio sobre minería de datos distribuida en redes P2P”, hacen referencia a investigaciones de “algoritmos de agrupamiento P2P”, considerando las siguientes propuestas: (1) Algoritmo exacto para monitoreo de agrupamiento de k-means. Este algoritmo consiste en monitorear la distribución de los centroides de los nodos locales dispersos y realizar el proceso de k-medias cuando se actualizan los grupos. El algoritmo considera dos fases, la primera fase consiste en monitorear la distribución de los datos mediante un algoritmo exacto; la segunda fase consiste en calcular los centroides mediante un enfoque centralizado. (2) Algoritmo k-medias basado en probar y hacer. Esta propuesta consiste en transmitir los centroides a todos los nodos en la red utilizando el mecanismo probar y hacer. Se requiere una sincronización de todos los nodos en cada iteración lo cual genera congestión en la red. De manera adicional se describen otros 3 algoritmos basados en k-medias P2P. En el artículo de Datta y sus colegas, publicado el año 2006 con el título “Minería de datos distribuida en redes punto a punto”, se propone un algoritmo iterativo basado en el intercambio de mensajes entre nodos conectados directamente para resolver el problema de agrupamiento de k-medias en redes P2P. Se eligen aleatoriamente un conjunto de centroides y se distribuyen sobre todos los nodos. Para cada iteración, cada nodo ejecuta un proceso basado en dos pasos: (1) Idéntico a la primera iteración del algoritmo k-medias estándar; en el cual cada nodo asigna cada uno de sus puntos a su centroide más cercano. (2) Un nodo envía un mensaje a los nodos vecinos conteniendo su identificador y el número de la iteración actual en la cual se encuentra. Se repite el paso (1) y paso (2) hasta que los centroides de las iteración actual y la siguiente no presenten cambios significativos con lo cual el algoritmo habrá concluido.