Minería de Grafos

Minería de Grafos

Como caso general de la minería de datos está la Minería de grafos, esta consiste en encontrar elementos o patrones representativos dentro de un grafo, pero no es solo el encontrar sub estructuras que se repitan una y otra vez, sino que también es el proceso de identificar conceptos que describen a las estructuras más importantes para una mejor interpretación de los datos (Deepayan Chakrabarti, Zhan & C. Faloutsos, 2010). Los gráfos representan una clase de estructuras más general que los conjuntos, secuencias, celosías y árboles.

Ejemplo de Celosía:

Celosía de cuboides, formando un cubo de datos 4-D para tiempo, artículo, ubicación y proveedor. Cada cuboide representa un grado diferente de resumen.

Un grafo es una estructura compuesta por un conjunto de vértices V y un conjunto de aristas E.

Grafo

En minería de grafos cada vértice representa una v.a. La minería de grafos solo se enfoca en grafos no dirigidos llamados campos aleatorios de Markov. La ausencia de una arista entre dos vértices indica que las variables aleatorias son condicionalmente independiente, por ejemplo los nodos 2 y 5 son condicionalmente independientes.

1.- Grafos de Markov y sus Propiedades

Definición de Nodos Adyacentes: Entonces dado un grafo de Markov G. Sean X y Y, dos nodos de G, entonces se dice que X es adyacente a Y ssi existe una arista que los une. Se nota como: \[X \sim Y\]

Definición de Grafo Completo: Dado el grafo de Markov G, se dice que G es completo si todos sus nodos estan conectados.

Notación del nodo X condicionalmente independiente al nodo Y: \[X \perp Y \mid resto\] Donde "resto" se refiere a todos los demás vértices del gráfico.

Definición: Entonces dado un grafo de Markov G. Sean X,Y y Z, subgrafos de G. Se dice que Z separa a X y a Y si cada ruta entre X y Y incluye al noto Z.

Entonces dado un Grafo de Markov G. Sean A,B y C subgrafos de G. C es la separación de A y B ssi \[A \perp B \mid C\] Definición: Un "clique" es un subgrafo completo.

Un subgrafo completo se llama máximo si es una clique y no se le pueden agregar otros vértices y aun así producir una clique.

Esta última definición es importante porque dado un grafo lo que se tratará de hacer es descomponer al grafo en cliques.

Ejemplo:

Ejemplo

Entonces para este ejemplo los máximos cliques son:

• {X, Y }, {Y,Z}, {Z,W}, {X,W}

Definición: La función de densidad f sobre el grafo de Markov G, se define como:

Densidad del Grafo de Markov

Donde \[ \begin{equation} \mathcal{C} \end{equation}\] es el conjunto de los cliques máximos. Las funciones phi en general no son funciones de densidad, son llamadas potenciales de cliques.

2.- Modelos de gráfos no dirigidos para Variables continuas.

Supongamos que tenemos un grafo G con variables aleatorias continuas. Se supone que la observación tiene una distribución Gaussiana Multivariante, con media: \[\mu\] y matriz de covarianzas: \[\sum\] Entonces dado el conjunto de variables aleatorias continuas \[X_{1},...,X_{p}\] Y consideremos la partición:

\[Z=X_{1},...,X_{p-1}\] También: \[Y=X_{p}\] Entonces tenemos que:

3.- Estimación de los parámetros cuando el grafo de la estructura es conocida

Dadas N realizaciones de X, con cada v.a continua sigue una distribución normal multivariante, con media: \[\mu\] y matriz de covarianzas: \[\sum\] Entonces para estimar la matriz de covarianzas:

Ignorando las constantes, la probabilidad logarítmica de los datos se puede escribir como: \[ \mathcal{l} (\Theta)= log \ det(\Theta)-traza(S\Theta) \] Donde: \[ \Theta \] es la inversa de matriz de covarianzas. Ahora considerando las aristas para nodos condicionalmente independientes: \[ \mathcal{l} (\Theta)= log det(\Theta)-traza(S\Theta)-\sum_{(i,j)\notin E}\gamma_{jk} \theta _{jk} \] Ahora hallando el gradiente para maximizar se tiene que: \[ \Theta^{-1}-S-\Gamma= 0 \] Recuérdese que la derivada de: \[ log \ det \Theta \] Es: \[ \Theta^{-1} \] Considerando la última componente de la última fila y columna, de la última ecuación se tiene: \[ w_{12}-s_{12}-\gamma_{12}= 0 \]

Tomando: \[ W=\Theta^{-1} \] Usando la definición de la matriz W, y tomando una partición en la última fila y columna:

\[\begin{equation} \begin{pmatrix} W_{11} & w_{12}\\ w_{12}^T & w_{22} \end{pmatrix} \begin{pmatrix} \theta_{11} & \theta_{12}\\ \theta_{12}^T & \theta_{22} \end{pmatrix} = \begin{pmatrix} I_{11} & 0\\ 0^T & 1 \end{pmatrix} \end{equation}\]

Es decir, reemplazando en la ecuación: \[ w_{12}-s_{12}-\gamma_{12}= 0 \] se tiene que: \[ W_{11}(\theta_{12}/\theta_{22})+s_{12}+\gamma_{12}= 0 \] Y notando: \[ \hat{\beta}= \theta_{12}/\theta_{22} \] Luego sustituimos W11 en S11. Suponiendo que hay p-q elementos diferentes de cero en Gamma. Además, podemos reducir β a β* eliminando sus p - q elementos cero, al no aportar información lo que se hace es eliminarlos con lo cual se ha obtenido el sistema de ecuaciones reducido q × q: \[ W_{11}^{*}\beta_{12}^{*}-s_{12}^{*}= 0 \] Y la solución de la ecuación es de: \[ \beta_{12}^{*}=\frac{s_{12}^{*}}{W_{11}^{*}} \] Luego se tiene que: \[ \frac{1}{\theta_{22}}=w_{22}-w_{12}^{T}\beta \\ w_{22}=s_{22} \] Esto conduce al procedimiento iterativo simple dado en el algoritmo para estimar la matriz de covarianzas y su inversa. Luego el algoritmo iterativo para estimar la matriz de covarianzas y su inversa es el siguiente:

Ejemplo:

4.- Estimación de la Estructura del Grafo

En la mayoría de los casos, no sabemos qué vértices omitir de nuestro grafo, por lo que nos gustaría intentar descubrirlo a partir de los datos mismos. Meinshausen y B¨uhlmann (2006) adoptan un enfoque simple del problema: en lugar de tratar de estimar completamente la matriz de covarianzas estiman las componentes de la inversa de la matriz de covarianzas que no es de cero. Para esto se usa la regularización L1 (lazo) para este propósito. Entonces realizando un procedimiento parecido al anterior se tiene que:

Ahora veremos que este sistema es exactamente equivalente a las ecuaciones de estimación para una regresión de lazo. Donde Z es la matriz predictora, y: \[ \lambda \] el parámetro de penalidad. Con lo cual la expresión del gradiente es:

El procedimiento resultante se denomina grafo lazo. De manera que tiene que el algoritmo para determinar la estructura del grafo es la siguiente:

Ejemplo:

5.- Máquina de Boltzmann restringida:

Una máquina de Boltzmann es un tipo de red neuronal recurrente estocástica. El cual actualmente no es muy utilizado debido a que no son muy útiles para resolver ciertos problemas de aprendizaje de máquina. Pero ese problema no se da en una arquitectura llamada Máquina de Boltzmann restringida o MBR (RBM en inglés: Restricted Boltzmann Machine) el cual se basa en un método que hace posible entrenar muchas capas de unidades ocultas de manera eficiente y que cada nueva capa sea añadida para mejorar el modelo.

En la máquina de Boltzmann restringida (RBM) no hay conexiones entre nodos en la misma capa. Las unidades visibles se subdividen para permitir que la GBR modelen la densidad conjunta de la característica V1 y sus etiquetas V2.

6.- Aplicaciones de la Minería de Grafos

Existe una amplia gama de aplicaciones:

• Gráficas en la Web.
• Redes sociales.
• Redes de información.
• Redes biológicas.
• Bioinformática.
• Informática química.
• Recuperación multimedia.
• Recuperación de texto.

Ejemplos

7.- Minería de patrones de grafos

La minería de patrones de grafos es la minería de subgrafos frecuentes (también llamados patrones de (sub) grafos) en uno o en un conjunto de grafos. Los métodos para la minería de patrones de grafos se pueden categorizar en enfoques basados en Apriori.

En la parte práctica se podría responder incógnitas como:

• ¿Qué productos se compraban juntos a menudo?
• ¿Cuáles son las compras posteriores después de comprar una PC?
• ¿Qué tipos de ADN son sensibles a este nuevo fármaco?
• ¿Podemos clasificar documentos web utilizando patrones frecuentes?

Un (sub) grafo es frecuente si su soporte (frecuencia de ocurrencia) en un conjunto de datos dado no es menor que un umbral mínimo de soporte.

Principio Apriori: Si un grafo es frecuente todos sus subgrafos son frecuentes.

Gráfica donde se ejemplifica el concepto de soporte:

Ejemplo Soporte

8.- Agrupación y clasificación de grafos y redes homogéneas

Los grandes grafos y redes tienen estructuras cohesivas, que a menudo se ocultan entre sus nodos y enlaces masivos e interconectados. Se han desarrollado métodos de análisis de conglomerados en grandes redes para descubrir estructuras de red, descubrir comunidades ocultas, concentradores y valores atípicos basados en estructuras topológicas de red y sus propiedades asociadas (Jiawei Han, Micheline Kambar & Jiam Pei, 2012).

Autores académicos y su relación en grafo

9.- Aplicación: Minería de Texto

Este ejemplo es la reproducción del trabajo de Hugo Porras. Se trata del Procesamiento del Lenguaje Natural en Twitter.

Para tener acceso a los datos hay que crear una cuenta en Twitter:

Cuenta en Twitter

Luego hay que entrar al link https://developer.twitter.com/ y dar click en "Aplicar" o "Apply":

Página para desarrolladores de Twitter

Después hay que seleccionar el modo desarrollador:

Página para ser Desarrollador en Twitter

Se llena los datos y también Twitter pide una descripción del propósito con el cual se va a usar los datos. También Twitter pide comprobar usando el correo personal:

Correo de Confirmación

Así pues se va a la parte de Projects y Apps:

Luego se da clic en "New Project" y se llena los datos. En seguida se dirige a generar la llave:

Al cabo de dar clic se nos proporcionará tres códigos:

• API key
• API secret Key
• Bearer Token

Los tres códigos se los debe de guardar, ya que el programa no los guarda. Para este caso de estudio utilizaremos las siguientes librerías:

• rtweet: Conexión a la API de Twitter para la extracción de datos.
• tidyverse: Manipulación, limpieza y visualización de datos estructurados.
• tidytext: Manipulación de datos de texto.
• waffle: Gráficos de “waffle” (como al alternativa los gráficos de pastel).
• tm: Funciones para limpieza y procesamiento de corpus texto.
• stringi: Funciones de manipulación de texto.
• stopwords: Palabras vacías en varios idiomas.
• wordcloud2: Visualización de nubes de palabras.
• udpipe: Librería para realizar varias tareas de NLP en varios idiomas.
• syuzhet: Librería dedicada al análisis de sentimientos en varios idiomas.
• parallel: Librería que habilita la paralelización de procesos, muy útil con syuzhet.

Carga de Librerías:

# Carga de librerías
library(dplyr)
library(rtweet)
library(tidyverse)
library(tidytext)
library(waffle)
library(tm)
library(stopwords)
library(wordcloud2)
library(syuzhet)
library(stringi)
library(parallel)
library(udpipe)

Creación del Token:

# Nombre de la aplicación
appname = "MiningGraphData"
key = "4IgvkdAlyG6nJjO13C2oNXSN1";
secret = "9ydF0XGrq08ue1CCHt43tOYltTYEKyxQaxbmkl5ORWSeA2hrYi";


# Token de conexión
twitter_token = rtweet::create_token( app = appname,
                                      consumer_key = key,
                                      consumer_secret = secret)

NOTA: La función "create_token" no funcionaba, fue necesario actualizar RStudio, R y la librería "rtweet". También hubo que eliminar versiones anteriores de R. Y reinstalar R y R Studio.

El mensaje donde se confirma la autentificación que aparece en el navegador es:

Cargado de Credenciales:

# Cargado del token
home_directory = path.expand("C:/Users/Andres1/Downloads/TRAB FINAL/Graph Mining")
file_name = file.path(home_directory,"twitter_token.rds")
twitter_token = readRDS(file = file_name)
head(twitter_token)

Si queremos observar las tendencias en Twitter, simplemente debemos utilizar la función trends_available. En nuestro caso, filtraremos aquellas disponibles para Ecuador.

trends_available() %>% filter(countryCode=="EC")

Tendencias en Ecuador usando la función "woeid":

get_trends(woeid = 23424801)

Para extraer datos se utiliza la función search_tweets, especificando la ubicación del Ecuador, que se incluyan retweets y que los tweets estén en español:

# Extraer data de un hashtag o de un tema
tweets_ec = search_tweets(q = "#justiciaparaRobertoMalta", 
                          n = 10000, geocode = "-0.220102,-78.5119250,100mi", 
                          include_rts = T, lang="es")
tweets_ec %>% head()

Así también, podemos extraer los tweets desde cuentas de usuario con la función get_timeline. Esta extraerá máximo los últimos 3200 tweets de la cuenta. En nuestro caso de estudio, utilizaremos los datos de Fiscalía General del Estado:

# Extraer data de un usuario
user_tweets_ec = get_timeline(user = "@FiscaliaEcuador", n = 3200, lang="es")
saveRDS(user_tweets_ec, "twitter_token.rds")
user_tweets_ec %>% head()

10. Limpieza de datos

Cuando tratamos con datos de Twitter, la primera tarea que debemos llevar a cabo es la identificación de tweets orgánicos (originales), retweets y respuestas. Para esto, los datos recogidos por la API de twitter tienen las columnas is_retweet y reply_to_status_id.

# Tweets orgánicos
user_tweets_ec_organic = user_tweets_ec %>% filter(is_retweet==F, is.na(reply_to_status_id))


# Retweets
user_tweets_ec_retweets = user_tweets_ec %>% filter(is_retweet==T)


# Respuestas
user_tweets_ec_replies = user_tweets_ec %>% filter(!is.na(reply_to_status_id))

En los tweets orgánicos vamos a remover hipervínculos, menciones (@) y puntuación a través de las funciones str_replace_all, removeNumbers y removePunctuation y stri_trans_general con la finalidad de analizar únicamente los textos.

# Limpieza de textos
user_tweets_ec_organic = user_tweets_ec_organic %>% 
  mutate(text=str_replace_all(text, "https\\S*", "")) %>% # hipervínculos
  mutate(text=str_replace_all(text, "@\\S*", "")) %>% # menciones
  mutate(text=str_replace_all(text, "[\r\n\t]", "")) %>% # separadores
  mutate(text=removeNumbers(text)) %>% # números
  mutate(text=removePunctuation(text)) %>%  # puntuación
  mutate(text=str_squish(text))

Acto seguido removeremos palabras vacías y tokenizaremos por palabras usando las funciones stopwords y unnest_tokens. Las palabras vacías son aquellas que no son útiles para el análisis y usualmente incluyen artículos, pronombres, preposiciones, etc. y la función stopwords nos ayuda a cargar distintos diccionarios de palabras vacías. La tokenización en cambio se refiere a la estructuración de los datos de texto en filas, donde cada fila será un token (tal token puede ser una palabra, un n-grama, una oración, etc.).

# Palabras vacías
stopwords_snow = stopwords("es", source = "snowball")
stopwords_iso = stopwords("es", source = "stopwords-iso")
stopwords_ntlk = stopwords("es", source = "nltk")
# Conteo de palabras
tweets = user_tweets_ec_organic %>%
  select(text) %>%
  unnest_tokens(token, text, to_lower = F)
tweets = tweets %>%
  filter(!token %in% c(stopwords_ntlk))

Una tarea adicional que se lleva a cabo en este tipo de análisis es el stemming o la lematización. Estos son métodos para reducir una palabra a su raíz o morfema con el objetivo de analizar variaciones de una palabra como una sola:

Descarga de modelo pre entrenado udpipe:

Cuadro de Descarga

#udpipe::udpipe_download_model('spanish')

Comentado para que no se descargue a cada momento. Ahora hay que revisar el código udpipe el cual es el nombre del archivo udpipe que se descargó:

Codigo Udpipe

Después de obtenido el código udpipe se lo ubica en los argumentos del código "udpipe_load_model":

model = udpipe_load_model("spanish-gsd-ud-2.5-191206.udpipe")
tweets_ann = as_tibble(udpipe_annotate(model, tweets$token))
# Stemming
tweets = tweets_ann %>% 
  select(token, lemma) %>% 
  filter(!is.na(lemma))
tweets

Debido a que al traer a la raíz se podrían generar otras palabras vacías que estaban conjugadas, realizaremos este procedimiento nuevamente y pasaremos a minúsculas las palabras:

# Conteo de palabras
tweets = tweets %>%
  mutate(lemma=tolower(lemma)) %>% 
  filter(!lemma %in% c(stopwords_ntlk))

Veamos el resultado de esta limpieza y procesamiento de los datos:

tweets %>% head(7)

11.- Análisis descriptivo

Una vez que tenemos los datos extraídos limpios, realizaremos algunos análisis descriptivos para extraer conclusiones acerca del manejo de la cuenta de Twitter de Lenin Moreno (Hugo Porras, 2016):

Top tweets por conteo de likes

# Top de tweets por conteo de likes
user_tweets_ec = user_tweets_ec %>% arrange(desc(favorite_count))
user_tweets_ec %>% head(5) %>% select(text)

Evolución temporal de los tweets por día

# Gráfico de la evolución de tweets
ts_plot(user_tweets_ec, by="day", color="darkred") +
  labs(x = "Fecha", y = NULL, title = "Frecuencia de los tweets de Lenin Moreno", 
       subtitle = "Conteo de tweets agregado por día", caption = "Fuente: Twitter") +
  theme_bw()

Es interesante notar que los tweets se incrementan a la misma fecha que se registra la mayor cantidad de covid:

Fuente de publicación de los tweets

# Fuente de los tweets
user_tweets_ec_sources = user_tweets_ec %>% 
  group_by(source) %>%
  summarize(conteo=n()) %>% 
  mutate(porcentaje=round(conteo/sum(conteo)*100,0)) %>% 
  arrange(desc(conteo))
user_tweets_ec_sources

# Gráfico de la fuente de los tweets
w_vec2 = user_tweets_ec_sources$porcentaje
names(w_vec2) = user_tweets_ec_sources$source
waffle(w_vec2, rows = 10, title = 'FGE: Tweets por fuente')

Hashtags más comunes

# Hashtags más comunes
data.frame(text=unlist(user_tweets_ec_organic$hashtags)) %>% 
  count(text, sort = TRUE) %>%
  top_n(15) %>%
  mutate(text = reorder(text, n)) %>%
  ggplot(aes(x = text, y = n)) +
  geom_col() +
  xlab(NULL) +
  coord_flip() +
  labs(y = "Frecuencia",
       x = "Hashtags",
       title = "Hashtags más frecuentes en la cuenta de Twitter de Lenin Moreno",
       subtitle = "Tweets orgánicos de Lenin Moreno")

# Hashtags más comunes
data.frame(text=unlist(user_tweets_ec_organic$hashtags)) %>% 
  count(text, sort = TRUE) %>%
  mutate(text = reorder(text, n)) %>%
  select(word=text, freq=n) %>% 
  wordcloud2()

Palabras más usadas en los tweets

# Palabras más usadas
tweets %>% 
  count(lemma, sort = TRUE) %>%
  top_n(15) %>%
  mutate(lemma = reorder(lemma, n)) %>%
  ggplot(aes(x = lemma, y = n)) +
  geom_col() +
  xlab(NULL) +
  coord_flip() +
  labs(y = "Frecuencia",
       x = "Palabras",
       title = "Palabras más frecuentes en la cuenta de Lenin Moreno")

# Palabras más usadas
tweets %>% 
  count(lemma, sort = TRUE) %>%
  mutate(lemma = reorder(lemma, n)) %>%
  select(word=lemma, freq=n) %>% 
  wordcloud2()

12.- Análisis de sentimientos

Cuando tenemos datos de texto podemos realizar además análisis de sentimientos. Acorde a Robinson y Silge (2019), cuando el ser humano lee un texto, entiende la intención emocional de una palabra para inferir si una porción de texto es positiva o negativa, o incluso podría reconocer miedo o disgusto. Este mismo acercamiento lo podemos realizar a través de técnicas de mineo de texto, de las cuales existen muchas alternativas.

En este caso de estudio usaremos una técnica de diccionarios y uni gramas basada en el trabajo de Saif Mohammad y Peter Turney. A tal diccionario se lo llama “nrc” y lo que busca es etiquetar cada palabra en una de 10 emociones a través de un algoritmo de búsqueda intensiva. Este análisis se lo realiza a través de la función get_nrc_sentiment, optimizándola al paralelizarlo con el número de núcleos que tenga nuestra CPU.

# Creación del ambiente de paralelización
cl = makeCluster(detectCores()-1)
clusterExport(cl = cl, c("get_sentiment", "get_sent_values", "get_nrc_sentiment", "get_nrc_values", "parLapply"))


# Análisis de sentimientos
tweet_sentiment_nrc = get_nrc_sentiment(tweets$lemma,language = "spanish", cl=cl)
stopCluster(cl)


# Etiquetado de sentimientos
tweet_sentiment_nrc = cbind(tweets, tweet_sentiment_nrc)
tweet_sentiment_nrc %>% filter(rowSums(tweet_sentiment_nrc[,-c(1,2)]) > 0) %>% head()




tweet_sentiment_nrc =tweet_sentiment_nrc[,-c(1,2)]

Gráficamente, los sentimientos más recurrentes en los tweets de la FGE son:

# Frecuencia de sentimientos
sentimentscores = data.frame(colSums(tweet_sentiment_nrc %>% filter(lemma!="general") %>% 
                                       select(-token,-lemma)))
names(sentimentscores) = "Score"
sentimentscores = cbind("sentiment"=rownames(sentimentscores),sentimentscores)
rownames(sentimentscores) = NULL
sentimentscores = sentimentscores %>% 
  mutate(sentiment = recode(sentiment, 
                            "anger"="enfado",
                            "anticipation"="anticipación",
                            "disgust"="disgusto",
                            "fear"="miedo",
                            "joy"="alegría",
                            "negative"="negativo",
                            "positive"="positivo",
                            "sadness"="tristeza",
                            "surprise"="sorpresa",
                            "trust"="confianza"))

ggplot(data=sentimentscores,aes(x=sentiment,y=Score))+
  geom_bar(aes(fill=sentiment),stat = "identity")+
  xlab("Sentimientos")+ylab("Scores")+
  ggtitle("Sentimientos totales basados en scores")+
  theme(axis.text.x = element_text(angle=90),
        legend.position = "none")

Se puede notar en este gráfico que el sentimiento más frecuente en los tweets de la FGE es negativo (específicamente, el miedo), sus palabras asociadas se pueden ver gráficamente como:

tweet_sentiment_nrc %>% 
  filter(fear > 0) %>% 
  select(lemma) %>% 
  count(lemma) %>% 
  select(word=lemma, freq=n) %>% 
  wordcloud2()

13. Bibliografía

D. Chakrabarti, Y. Zhan,y C. Faloutsos (2010) R-MAT: un modelo recursivo para la minería de gráfos, en SIAM Data Mining 2004,1-2. https://faculty.mccombs.utexas.edu/deepayan.chakrabarti/

Trevor Hastie, Robert Tibshirani, Jerome Friedman, (2017), The Elements of Statistical Learing: Data Mining, Inference, and Prediction (2° ed), Springer, 625-639.

Jiawei Han, Micheline Kambar, Jiam Pei, (2012), Data Mining: Concepts and Techniques (3° ed), Elsevier, 591-593.

Hugo Porras (2016), Introducción al análisis de redes sociales usando Procesamiento del Lenguaje Natural. Rpubs. https://rpubs.com/hugoporras/ce_fge_trends