Los medios sociales anotados geográficamente son extremadamente valiosos para la recuperación moderna de la información. Sin embargo,  los usuarios de redes sociales rara vez publican información de localización. conforman su red social.

geo

El paper: Geotagging One Hundred Million Twitter Accounts with Total Variation Minimization, de  Ryan Compton, David Jurgens y David Allen, ofrece un nuevo enfoque para solucionar este problema, proponiendo un algoritmo que  infiere la ubicación de un usuario desconocido, a partir de ubicaciones de los amigos con los que se conecta a través  de menciones en tweets,  y que conforman su red social.

gep1

Donde f = (f1; fn) es la locación estimada para cada usuario y  L es el set de usuarios, d es la distancia geodésica y wij, los pesos equivalentes al mínimo número de menciones.

El enfoque busca una red tal que la suma sobre todas las distancias geográficas entre usuarios conectados sea lo más pequeña posible. Esta suma se conoce como la variación total.

Metodología.

Se construyó una red social, G = (V; E), con usuarios como vértices y @menciones entre usuarios como aristas, usando  10% de la muestra de  tweets públicos  de Abril 2012 hasta Abril del  2014., con un peso de  76,9TB de datos, con 25.312.399.718 de @menciones. Se filtraron las menciones reciprocas, para conformar una red de  1.034.362.407 enlaces y 110.893.747 usuarios.  Del  número total de usuarios, el subtotal con localizaciones confirmadas vía GPS o auto-informes es 24.545.425.  Los usuarios con ubicaciones conocidas por GPS constituyen sólo una pequeña porción de las redes de menciones.

En cada iteración, el algoritmo actualiza simultáneamente la ubicación de cada usuario con la mediana l1 multivariante de las ubicaciones de sus amigos. Sólo después de que todas las actualizaciones estén completas comunicamos nuestros resultados a través de la red.

El framework Apache Spark se utilizó para implementar el algoritmo en una arquitectura Big Data. Permite distribuir los datos en la memoria del clúster haciendo uso de conjuntos de datos distribuidos resilientes (denominados RDD) y operando en estos conjuntos de datos, con código Scala.

geo2

La  red y las locaciones de usuarios se almacenan en los RDDs edgeList y userLocations., los cálculos de estos RDD hacen uso de todos los recursos de la CPU del clúster disponibles. El algoritmo se implementa con un simple map y un filtro. La comunicación de las ubicaciones actualizadas a través de la red se logra con una combinación en la lista de vértices, seguida de un groupByKey, que establece una lista de adyacencias para el siguiente mapa.

Análisis de resultados

El algoritmo fue ejecutado en la red bidireccional y los resultados se informan después de 5 iteraciones. El número de usuarios geo codificados después de cada iteración es el siguiente:

geo3

La probabilidad de que un usuario sea geo codificado por el método planteado aumenta cuando existe un incremento un nivel de actividad de la función. Una gran fracción de usuarios  pierde el interés en Twitter después de generar un pequeño número de Tweets, lo que dificulta su localización calculada.

geo5

Para evaluar la cobertura, se examinaron 4.835.561.225 tweets recogidos entre el 2013-01-01 y el 2013-04-07. Estos tweets fueron generados por 117.215.282 usuarios. El método fue capaz de geo codificar el 89% de los tweets. Podría aumentar el porcentaje si todas las ubicaciones reportadas no-vacías no fueran ambiguas.

geo6

Para la precisión se realizo una validación cruzada, tomando un 10% del set de  12.297.785 usuarios que revelaron su posición GPS.  Después de 5 iteraciones del algoritmo, se pudo inferir la locación de 966.515 usuarios, con una Desviación absoluta mediana (median error) de 6,33 kms .

Conclusiones

  • El uso de Apache Spark está justificado por el gran volumen de datos a ser procesados para la conformación de las redes y el cálculo de las distancias geográficas.
  • El hecho que se pueda inferir las locaciones de usuarios, a partir de datos públicos, permite que se  analicen nuevos algoritmos para el cálculo de las distancias geográficas, con mayor precisión y con mejor cobertura.
  • Implementar métodos para eliminar datos de localizaciones (auto-informes) que sean ambiguos, ya que generan errores en el procesamiento de las distancias de usuarios.
  • Se conseguiría mejor cobertura si el método considera que la relación por menciones sea unidireccional.

Los distintos algoritmos de clustering, permiten encontrar agrupamientos de tal forma que los objetos de un grupo sean similares entre sí y diferentes de los objetos de otros grupos.  Pueden detectar regiones densas de puntos separadas de otras regiones densas por regiones poco densas de otros grupos.  Al ser métodos de aprendizaje no supervisado, se caracterizan por que en los datos no existen clases predefinidas

Los resultados obtenidos dependerán del algoritmo de agrupamiento seleccionado, el conjunto de datos disponible y la medida de similitud utilizada para comparar objetos (usualmente, definida como medida de distancia).

El presente trabajo, trata sobre la comparación de los resultados obtenidos de tres algoritmos de clustering, aplicados a un mismo dataset:  K-Means y Clustering Jerárquico

Dataset

El dataset utilizado  para el siguiente estudio, se refiere a información correspondiente a animales en cautiverio, que son distintos entre sí. Cada registro de un animal contiene 17 atributos biológicos, la mayoría son  booleanos  y hacen referencia sobre diversas características propias de su  especie. Así tenemos, si el animal es mamífero, pone huevos, es doméstico, acuático, dentado, etc. El atributo nombre de animal, es un identificador único y el atributo «tipo» corresponde el atributo de clase con valores del 1 al 7. Esta columna no se considera para la ejecución de los algoritmos de clustering.

El dataset esta publicado en http://sci2s.ugr.es/keel/dataset.php?cod=69

fig1

Metodología

Para el dataset, fue aplicado los métodos de clustering: x. Para los algoritmos: K-Means y Clustering Jerárquico, se realizó la técnica de acodamiento  para encontrar el valor más adecuado para el número de agrupamientos (clúster) en una primera instancia.

Para los algoritmos K-Means y Clustering Jerárquico  se aplicó  la técnica del promedio Silhouette para medir la calidad de los agrupamientos (clusters) encontrados. Este método va a permitir determinar qué tan bien cada objeto se encuentra dentro de su agrupación. El número óptimo de clusters k es el que maximiza la silueta promedio en un rango de posibles valores de k.

Para el algoritmo DBSCAN, se utilizó la técnica KNN (k-nearest neighbors), para hallar el valor más adecuado de la distancia épsilon.  El objetivo de su aplicación es  calcular el promedio de las distancias de todos los puntos a sus k vecinos más cercanos. El valor de k será incremental en un ciclo y se corresponde con MinPts.

A continuación con la distancia óptima calculada con la técnica KNN, se realizaron varias iteraciones para calcular los agrupamientos obtenidos con el algoritmo DBSCAN, con un valor de minPts de 2 a 20. El  valor de minPts óptimo se lo asociara con número máximo de clusters determinado, luego de la ejecución de todas las iteraciones

Resultados

Algoritmo K-MEANS

Al ejecutar la técnica de acodamiento, se puede observar que el numero sugerido de clusters K,  como parámetro para el algoritmo K-Means está entre 4 y 5.

fig2

Fig. 1 Técnica del codo en K-Means

Al ejecutar la técnica del promedio Silhouette, en un rango de entre 2 a 10 particiones, el resultado sugiere que el número óptimo de agrupamientos (clusters), para el dataset es 6

fig3

Fig. 2.  Técnica Promedio Silhouette para algoritmo K-Means

k.max <- 10
data <- data.scaled
sil <- rep(0, k.max)
#for(i in 2:k.max)

{ km.res <- kmeans(data, centers = i, nstart = 25)
ss <- silhouette(km.res$cluster, dist(data))
sil[i] <- mean(ss[, 3])}

# Plot the  average silhouette width

plot(1:k.max, sil, type = «b», pch = 8,
frame = FALSE, xlab = «Number of clusters k»)
abline(v = which.max(sil), lty = 2)

A continuación se procesa, el algoritmo K-Means, con parámetro K =6, y aplicamos un plot gráfico. Se obtiene el siguiente resultado

fig4

Fig. 3. Clusters obtenidos con algoritmo K-Means

 

Agrupamiento jerárquico

Al ejecutar la técnica de acodamiento, se puede observar que el numero sugerido de clusters K,  como parámetro para el algoritmo K-Means está entre 5 y 6.

fig5

Fig. 4.  Técnica del codo en Clustering Jerárquico

Al ejecutar la técnica del promedio Silhouette, en un rango de entre 2 a 12 particiones, el resultado sugiere que el número óptimo de agrupamientos (clusters), para el dataset es 5.

fig6

Fig. 5.  Técnica Promedio Silhouette para algoritmo K-Means

k.max <- 12
data <- zoo.data.scaled
sil <- rep(0, k.max)

# Compute the average silhouette width for
for(i in 2:k.max){ km.res <-eclust(zoo.data.scaled, «hclust», k = i, graph = FALSE)
ss <- silhouette(km.res$cluster, dist(data))
sil[i] <- mean(ss[, 3])}

plot(1:k.max, sil, type = «b», pch = 15,
frame = FALSE, xlab = «Number of clusters k»)
abline(v = which.max(sil), lty = 2)

Se ejecuta el algoritmo de clustering jerárquico, con corte de k=6 y aplicamos un plot gráfico y obtenemos el siguiente resultado

fig7

Fig. 6. Dendograma obtenido con algoritmo Clustering Jerárquico

 

Algoritmo DBSCAN

Se aplicó la técnica KNN para evaluar distancias de 0 a 2,5, para el dataset en cuestión y se determinó que con un numero de MinPts = 4, la distancia épsilon optima es de 1.8. Luego de las iteraciones con un valor del parámetro MinPts de 3 a 8, se puede observar el número máximo de clusters calculado es de 6, para valores de MinPts = 4  y a partir de un valor de MinPts = 6, el número de clusters comienza a decrecer.

fig-9

Fig. 7. Comparación de Clusters en relación al número de puntos mínimos en DBSCAN

 

Conclusiones

Entre los algoritmos KMeans y Clustering Jerárquico, el valor del promedio Silhouette, se maximiza  para el algoritmo KMeans, con 0.4095, con 6 clusters. A continuación se presenta la siguiente tabla, en los que se detalla en número de clusters proyectado y la medida promedio Silhouette calculada.

Algoritmo/Cluster 2 3 4 5 6 7
hierarchical  Silhouette 0.2613 0.3008 0.3842  0.4033  0.3866 0.4009
Kmeans  Silhouette 0.2635 0.2937 0.4017 0.4071 0.4085 0.4052

 

Con respecto al algoritmo DBSCAN, el número de clusters calculado con una distancia épsilon = 1.8 y MinPts = 4, es de 6.

El número de clases (grupos) para el dataset evaluado es de 7, por lo que se puede concluir que los algoritmos K-Means y DBSCAN, han presentado alto grado de bondad y una calidad aceptable en lo que a medidas de similitud se refiere, con respecto al conjunto de datos en lo que fueron aplicados,