Paralelizando Iteraciones de K-Means

Si se hace una segmentacion con k-means en un set de datos muy grande, pueden obtenerse resultados significativamente diferentes en cada ejecucion. Una forma de obtener el mejor resultado es usando el parametro nstart para indicar cuantos set de datos se van a considerar al inicio del algoritmo para luego quedarse con el mejor.

Si al usar nstart se hace mas lenta la ejecución de k-means, puede paralelizarse este proceso y distribuir la tarea entre varios procesadores.

El siguiente scrip es una ejecución de k-means con nstart = 100. Tiene un tiempo de ejecucion de 1 minuto en un procesador i7

#-----------------------------------------------------------------------------

suppressWarnings(library(C50)); library(rpart); data(churn);

Datos<-churnTrain[,c(2,6:19)]

for (i in 1:4) Datos<-rbind(Datos,Datos)  # aumenta dataset duplicandolo

system.time(Madelo<-kmeans(Datos, centers = 5, iter.max = 100, nstart = 100))

#-----------------------------------------------------------------------------

Para mejorar el tiempo de ejecución del script anterior, pueden ejecutarse en paralelo 4 iteraciones con nstart=25 y luego elegir la de mejor resultado. Este proceso paralelizado tiene un tiempo de ejecución de 15 segundos en un procesador i7.

El script sería el siguiente:

#-----------------------------------------------------------------------------
# PASO 1: Inicio y fin de Paralelizacion de procesos
tiempo_inicio<-Sys.time()          # guarda tiempo de inicio de ejecucion
suppressMessages(library(snow) )   # carga libreria snow que permite paralelizar
 
# inicia clusterizacion indicando 4 procesadores a usar
Cluster<-makeCluster(4,type="SOCK")   
NoImprir<-clusterEvalQ(Cluster,
{
  # Carga 4 veces mismo dataset. 1 para cada procesador
  suppressMessages(library(C50)); data(churn);   
  Datos<-churnTrain[,c(2,6:19)]
  for (i in 1:4) Datos<-rbind(Datos,Datos) # aumenta dataset duplicandolo
})
# Ejecuta 4 veces kmeans con nstart=25 en cada iteracion
# Crea 4 modelos diferentes para luego elegir el mejor
# Mejor = el de menor distancia intracluster
#  Distancia Intracluster=Distancia entre cada observacion y su centroide
ConjuntoDeModelos<-clusterApply(Cluster,c(25,25,25,25),
                                function(i) kmeans(Datos,
                                                   centers   = 5,
                                                   iter.max  = 100,
                                                   nstart    = i )
)
# fin del proceso en paralelo
stopCluster(Cluster)
 
 
#-----------------------------------------------------------------------------
# PASO 2: Eleccion de la mejor iteracion
# Crea vector que contiene las distancias intracluster de cada iteracion
DistanciaEntreCentroides<- sapply( ConjuntoDeModelos,
                             function(iteraciones) {iteraciones$tot.withinss})
 
# Elije mejor modelo (el de menor distancia intracluster)
ModeloFinal <- ConjuntoDeModelos[[which.min(DistanciaEntreCentroides)]]
Sys.time()-tiempo_inicio   # calcula tiempo total de ejecucion