Teoría

Agrupamiento o Clustering es una técnica de aprendizaje automático no supervidaso que agrupa datos en función de su similitud.

Algunos usos típicos de esta técnica son:

  • Segmentación de clientes
  • Detección de anormalidades
  • Categorización de documentos

Instalar paquetes y llamar librerías

#install.packages("cluster") # Análisis de agrupamiento
library(cluster)
#install.packages("ggplot2") # Graficar
library(ggplot2)
#install.packages("data.table") # Manejo de muchos datos
library(data.table)
#install.packages("factoextra") # Gráfica de optimización de número de clústers
library(factoextra)
#install.packages("datasets")
library(datasets)
#install.packages("tidyverse")
library(tidyverse)

Ejercicio 1. Puntos

Contexto

Agrupa los siguientes ocho puntos.

Obtener datos

df1 <- data.frame(x=c(2,2,8,5,7,6,1,4), y=c(10,5,4,8,5,4,2,9))

Entender datos

summary(df1)
##        x               y         
##  Min.   :1.000   Min.   : 2.000  
##  1st Qu.:2.000   1st Qu.: 4.000  
##  Median :4.500   Median : 5.000  
##  Mean   :4.375   Mean   : 5.875  
##  3rd Qu.:6.250   3rd Qu.: 8.250  
##  Max.   :8.000   Max.   :10.000
str(df1)
## 'data.frame':    8 obs. of  2 variables:
##  $ x: num  2 2 8 5 7 6 1 4
##  $ y: num  10 5 4 8 5 4 2 9
plot(df1$x, df1$y)

Escalar datos

# datos_escalados <- scale(datos_originales)

Asignar numero de grupos

grupos1 <- 3

Agrupar los puntos

set.seed(123)
clusters1 <- kmeans(df1, grupos1)
clusters1
## K-means clustering with 3 clusters of sizes 2, 3, 3
## 
## Cluster means:
##          x        y
## 1 1.500000 3.500000
## 2 3.666667 9.000000
## 3 7.000000 4.333333
## 
## Clustering vector:
## [1] 2 1 3 2 3 3 1 2
## 
## Within cluster sum of squares by cluster:
## [1] 5.000000 6.666667 2.666667
##  (between_SS / total_SS =  85.8 %)
## 
## Available components:
## 
## [1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
## [6] "betweenss"    "size"         "iter"         "ifault"

Optimizar el número de grupos

set.seed(123)
optimizacion1 <- clusGap(df1, FUN=kmeans, nstart=2, K.max = 7)
plot(optimizacion1, xlab="Número de clusters K", main="Optimización de clusters")

#El óptimo es el primer punto más alto

Graficar los grupos

fviz_cluster(clusters1, data=df1)

Agregar grupos a la base de datos

df1_clusters <- cbind(df1, cluster = clusters1$cluster)
head(df1_clusters)
##   x  y cluster
## 1 2 10       2
## 2 2  5       1
## 3 8  4       3
## 4 5  8       2
## 5 7  5       3
## 6 6  4       3

Conclusiones

La técica de clustering permite identificar patrones o grupos naturales en los datos sin necesidad de etiquetas previas

Ejercicio 2. USArrests

Contexto

La base de datos USArrests contiene estadísticas en arrestos por cada 100,000 residentes por agresión, asesinato y violación en cada uno de los 50 estados de EE.UU. en 1973.

Obtener datos

df2 <- USArrests
df2 <- df2 %>% select(-UrbanPop)

Entender datos

summary(df2)
##      Murder          Assault           Rape      
##  Min.   : 0.800   Min.   : 45.0   Min.   : 7.30  
##  1st Qu.: 4.075   1st Qu.:109.0   1st Qu.:15.07  
##  Median : 7.250   Median :159.0   Median :20.10  
##  Mean   : 7.788   Mean   :170.8   Mean   :21.23  
##  3rd Qu.:11.250   3rd Qu.:249.0   3rd Qu.:26.18  
##  Max.   :17.400   Max.   :337.0   Max.   :46.00
str(df2)
## 'data.frame':    50 obs. of  3 variables:
##  $ Murder : num  13.2 10 8.1 8.8 9 7.9 3.3 5.9 15.4 17.4 ...
##  $ Assault: int  236 263 294 190 276 204 110 238 335 211 ...
##  $ Rape   : num  21.2 44.5 31 19.5 40.6 38.7 11.1 15.8 31.9 25.8 ...

Escalar datos

df2_escalado <- scale(df2)
summary(df2_escalado)
##      Murder           Assault             Rape        
##  Min.   :-1.6044   Min.   :-1.5090   Min.   :-1.4874  
##  1st Qu.:-0.8525   1st Qu.:-0.7411   1st Qu.:-0.6574  
##  Median :-0.1235   Median :-0.1411   Median :-0.1209  
##  Mean   : 0.0000   Mean   : 0.0000   Mean   : 0.0000  
##  3rd Qu.: 0.7949   3rd Qu.: 0.9388   3rd Qu.: 0.5277  
##  Max.   : 2.2069   Max.   : 1.9948   Max.   : 2.6444

Asignar numero de grupos

grupos2 <- 5

Agrupar los puntos

set.seed(123)
clusters2 <- kmeans(df2_escalado, grupos2)
clusters2
## K-means clustering with 5 clusters of sizes 7, 14, 17, 4, 8
## 
## Cluster means:
##       Murder    Assault        Rape
## 1  0.8292944  1.3313823  0.90560938
## 2 -1.0812577 -1.0779212 -1.00700542
## 3 -0.2754591 -0.2999280 -0.12336985
## 4  0.4562038  0.9358314  2.26533514
## 5  1.5238170  0.8908337  0.09934463
## 
## Clustering vector:
##        Alabama         Alaska        Arizona       Arkansas     California 
##              5              4              1              3              4 
##       Colorado    Connecticut       Delaware        Florida        Georgia 
##              4              2              3              1              5 
##         Hawaii          Idaho       Illinois        Indiana           Iowa 
##              2              2              1              3              2 
##         Kansas       Kentucky      Louisiana          Maine       Maryland 
##              3              3              5              2              1 
##  Massachusetts       Michigan      Minnesota    Mississippi       Missouri 
##              3              1              2              5              3 
##        Montana       Nebraska         Nevada  New Hampshire     New Jersey 
##              3              2              4              2              3 
##     New Mexico       New York North Carolina   North Dakota           Ohio 
##              1              1              5              2              3 
##       Oklahoma         Oregon   Pennsylvania   Rhode Island South Carolina 
##              3              3              3              2              5 
##   South Dakota      Tennessee          Texas           Utah        Vermont 
##              2              5              5              3              2 
##       Virginia     Washington  West Virginia      Wisconsin        Wyoming 
##              3              3              2              2              3 
## 
## Within cluster sum of squares by cluster:
## [1] 3.380664 5.645542 9.205038 1.346517 4.683603
##  (between_SS / total_SS =  83.5 %)
## 
## Available components:
## 
## [1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
## [6] "betweenss"    "size"         "iter"         "ifault"

Optimizar el número de grupos

set.seed(123)
optimizacion2 <- clusGap(df2_escalado, FUN=kmeans, nstart=1, K.max = 10)
plot(optimizacion2, xlab="Número de clusters K", main="Optimización de clusters")

#El óptimo es el primer punto más alto

Graficar los grupos

fviz_cluster(clusters2, data=df2_escalado)

Agregar grupos a la base de datos

df2_clusters <- cbind(df2, cluster = clusters2$cluster)
head(df2_clusters)
##            Murder Assault Rape cluster
## Alabama      13.2     236 21.2       5
## Alaska       10.0     263 44.5       4
## Arizona       8.1     294 31.0       1
## Arkansas      8.8     190 19.5       3
## California    9.0     276 40.6       4
## Colorado      7.9     204 38.7       4
df2_clusters %>% group_by(cluster) %>% summarise_all(mean) %>% mutate(indicador_inseguridad = Murder + Assault + Rape)
## # A tibble: 5 × 5
##   cluster Murder Assault  Rape indicador_inseguridad
##     <int>  <dbl>   <dbl> <dbl>                 <dbl>
## 1       1  11.4    282.   29.7                 323. 
## 2       2   3.08    80.9  11.8                  95.8
## 3       3   6.59   146.   20.1                 172. 
## 4       4   9.78   249.   42.4                 301. 
## 5       5  14.4    245    22.2                 282.
df2_clusters <- df2_clusters %>% 
  mutate(cluster = case_when(
    cluster == 1 ~ "Inseguridad muy alta",
    cluster == 4 ~ "Inseguridad  alta",
    cluster == 5 ~ "Inseguridad media",
    cluster == 3 ~ "Inseguridad baja",
    cluster == 2 ~ "Inseguridad muy baja",
  ))
head(df2_clusters)
##            Murder Assault Rape              cluster
## Alabama      13.2     236 21.2    Inseguridad media
## Alaska       10.0     263 44.5    Inseguridad  alta
## Arizona       8.1     294 31.0 Inseguridad muy alta
## Arkansas      8.8     190 19.5     Inseguridad baja
## California    9.0     276 40.6    Inseguridad  alta
## Colorado      7.9     204 38.7    Inseguridad  alta

Conclusiones

La técica de clustering permite identificar patrones o grupos naturales en los datos sin necesidad de etiquetas previas.

Ejercicio 3. Segmentación de clientes

Contexto

La base de datos ventas tiene los registros entre el 1 de diciembre del 2010 y el 9 de diciembre del 2011 de las ventas de una empresa minorista en línea sin tienda física, basada en Reino Unido.
La empresa vende principalmente regalos únicos para toda ocasión y muchos de sis clientes son mayoristas.
Objetivo: Segmentar clientes, asignarles nombres y características de comportamiento y proponer sugerencias a las empresas para aumentar las ventas.

Obtener datos

df3 <- read.csv("C:\\Users\\natal\\OneDrive\\Carrera\\7moSemestre\\Modulo2\\ventas.csv")

Entender datos

summary(df3)
##        Ticket            Producto         Cantidad              Fecha       
##  Length   :522064   Length   :522064   Min.   :-9600.00   Length   :522064  
##  N.unique : 21663   N.unique :  4183   1st Qu.:    1.00   N.unique :   305  
##  N.blank  :     0   N.blank  :  1455   Median :    3.00   N.blank  :     0  
##  Min.nchar:     6   Min.nchar:     0   Mean   :   10.09   Min.nchar:    10  
##  Max.nchar:     7   Max.nchar:    36   3rd Qu.:   10.00   Max.nchar:    10  
##                                        Max.   :80995.00                     
##                                                                             
##         Hora            Precio              Cliente              País       
##  Length   :522064   Min.   :-11062.060   Min.   :12346    Length   :522064  
##  N.unique :   739   1st Qu.:     1.250   1st Qu.:13950    N.unique :    30  
##  N.blank  :     0   Median :     2.080   Median :15265    N.blank  :     0  
##  Min.nchar:     8   Mean   :     3.827   Mean   :15317    Min.nchar:     3  
##  Max.nchar:     8   3rd Qu.:     4.130   3rd Qu.:16837    Max.nchar:    20  
##                     Max.   : 13541.330   Max.   :18287                      
##                                          NAs    :134041
str(df3)
## 'data.frame':    522064 obs. of  8 variables:
##  $ Ticket  : chr  "536365" "536365" "536365" "536365" ...
##  $ Producto: chr  "WHITE HANGING HEART T-LIGHT HOLDER" "WHITE METAL LANTERN" "CREAM CUPID HEARTS COAT HANGER" "KNITTED UNION FLAG HOT WATER BOTTLE" ...
##  $ Cantidad: int  6 6 8 6 6 2 6 6 6 32 ...
##  $ Fecha   : chr  "01/12/2010" "01/12/2010" "01/12/2010" "01/12/2010" ...
##  $ Hora    : chr  "08:26:00" "08:26:00" "08:26:00" "08:26:00" ...
##  $ Precio  : num  2.55 3.39 2.75 3.39 3.39 7.65 4.25 1.85 1.85 1.69 ...
##  $ Cliente : int  17850 17850 17850 17850 17850 17850 17850 17850 17850 13047 ...
##  $ País    : chr  "United Kingdom" "United Kingdom" "United Kingdom" "United Kingdom" ...

Crear variables a analizar

df3$Venta <- df3$Cantidad * df3$Precio

library(dplyr)

tickets_cliente <- df3 %>%
  group_by(Cliente, Ticket) %>%
  summarise(
    Total_Ticket = sum(Venta, na.rm = TRUE),
    .groups = "drop"
  )

ticket_promedio <- tickets_cliente %>%
  group_by(Cliente) %>%
  summarise(
    Ticket_Promedio = mean(Total_Ticket, na.rm = TRUE),
    .groups = "drop"
  )

frecuencia <- df3 %>%
  group_by(Cliente) %>%
  summarise(
    Frecuencia_Compra = n_distinct(Ticket),
    .groups = "drop"
  )
clientes_cluster <- ticket_promedio %>%
  left_join(frecuencia, by = "Cliente")

Asignar numero de grupos

grupos2 <- 4

Agrupar los puntos

set.seed(123)
clusters2 <- kmeans(df2_escalado, grupos2)
clusters2
## K-means clustering with 4 clusters of sizes 12, 14, 17, 7
## 
## Cluster means:
##       Murder   Assault       Rape
## 1  1.3420549  1.048826  0.2875176
## 2 -1.0812577 -1.077921 -1.0070054
## 3 -0.2754591 -0.299928 -0.1233698
## 4  0.5308219  1.086252  1.8207361
## 
## Clustering vector:
##        Alabama         Alaska        Arizona       Arkansas     California 
##              1              4              4              3              4 
##       Colorado    Connecticut       Delaware        Florida        Georgia 
##              4              2              3              1              1 
##         Hawaii          Idaho       Illinois        Indiana           Iowa 
##              2              2              1              3              2 
##         Kansas       Kentucky      Louisiana          Maine       Maryland 
##              3              3              1              2              1 
##  Massachusetts       Michigan      Minnesota    Mississippi       Missouri 
##              3              4              2              1              3 
##        Montana       Nebraska         Nevada  New Hampshire     New Jersey 
##              3              2              4              2              3 
##     New Mexico       New York North Carolina   North Dakota           Ohio 
##              4              1              1              2              3 
##       Oklahoma         Oregon   Pennsylvania   Rhode Island South Carolina 
##              3              3              3              2              1 
##   South Dakota      Tennessee          Texas           Utah        Vermont 
##              2              1              1              3              2 
##       Virginia     Washington  West Virginia      Wisconsin        Wyoming 
##              3              3              2              2              3 
## 
## Within cluster sum of squares by cluster:
## [1] 8.838465 5.645542 9.205038 4.158414
##  (between_SS / total_SS =  81.1 %)
## 
## Available components:
## 
## [1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
## [6] "betweenss"    "size"         "iter"         "ifault"

Optimizar el número de grupos

set.seed(123)
optimizacion2 <- clusGap(df2_escalado, FUN=kmeans, nstart=1, K.max = 10)
plot(optimizacion2, xlab="Número de clusters K", main="Optimización de clusters")

#El óptimo es el primer punto más alto

Graficar los grupos

fviz_cluster(clusters2, data=df2_escalado)

Agregar grupos a la base de datos

df2_clusters <- cbind(df2, cluster = clusters2$cluster)
head(df2_clusters)
##            Murder Assault Rape cluster
## Alabama      13.2     236 21.2       1
## Alaska       10.0     263 44.5       4
## Arizona       8.1     294 31.0       4
## Arkansas      8.8     190 19.5       3
## California    9.0     276 40.6       4
## Colorado      7.9     204 38.7       4
df2_clusters %>% group_by(cluster) %>% summarise_all(mean) %>% mutate(indicador_inseguridad = Murder + Assault + Rape)
## # A tibble: 4 × 5
##   cluster Murder Assault  Rape indicador_inseguridad
##     <int>  <dbl>   <dbl> <dbl>                 <dbl>
## 1       1  13.6    258.   23.9                 296. 
## 2       2   3.08    80.9  11.8                  95.8
## 3       3   6.59   146.   20.1                 172. 
## 4       4  10.1    261.   38.3                 310.
df2_clusters <- df2_clusters %>% 
  mutate(cluster = case_when(
    cluster == 1 ~ "Inseguridad muy alta",
    cluster == 4 ~ "Inseguridad  alta",
    cluster == 5 ~ "Inseguridad media",
    cluster == 3 ~ "Inseguridad baja",
    cluster == 2 ~ "Inseguridad muy baja",
  ))
head(df2_clusters)
##            Murder Assault Rape              cluster
## Alabama      13.2     236 21.2 Inseguridad muy alta
## Alaska       10.0     263 44.5    Inseguridad  alta
## Arizona       8.1     294 31.0    Inseguridad  alta
## Arkansas      8.8     190 19.5     Inseguridad baja
## California    9.0     276 40.6    Inseguridad  alta
## Colorado      7.9     204 38.7    Inseguridad  alta

Conclusiones

La técica de clustering permite identificar patrones o grupos naturales en los datos sin necesidad de etiquetas previas

LS0tDQp0aXRsZTogIkNsw7pzdGVycyAtIFB1bnRvcyBVU0FycmVzdHMgeSBDbGllbnRlcyINCmF1dGhvcjogIk5hdGFsaWEgQm9yamFzIE1lbmRleiAtIEEwMTAyOTQ0OCINCmRhdGU6ICIyMDI2LTA4LTI1Ig0Kb3V0cHV0OiANCiAgaHRtbF9kb2N1bWVudDoNCiAgICB0b2M6IFRSVUUNCiAgICB0b2NfZmxvYXQ6IFRSVUUNCiAgICBjb2RlX2Rvd25sb2FkOiBUUlVFDQogICAgdGhlbWU6IGZsYXRseQ0KLS0tDQoNCiFbXShodHRwczovL21lZGlhMy5naXBoeS5jb20vbWVkaWEvdjEuWTJsa1BUYzVNR0kzTmpFeGFEZG1kSGRuZG5SelluWjROMmhyYkRWeWJUWnZNMjExY1d0blpXSTNiWEoyYzNCbk1HNTZOeVpsY0QxMk1WOXBiblJsY201aGJGOW5hV1pmWW5sZmFXUW1ZM1E5WncvMTJ2VkFHa2FxSFVxQ1EvZ2lwaHkuZ2lmKQ0KDQoNCiMgPHNwYW4gc3R5bGU9ImNvbG9yOiNEODFCNjAiPlRlb3LDrWE8L3NwYW4+DQoqKkFncnVwYW1pZW50byoqIG8gKkNsdXN0ZXJpbmcqIGVzIHVuYSB0w6ljbmljYSBkZSBhcHJlbmRpemFqZSBhdXRvbcOhdGljbyBubyBzdXBlcnZpZGFzbyBxdWUgYWdydXBhIGRhdG9zIGVuIGZ1bmNpw7NuIGRlIHN1IHNpbWlsaXR1ZC4gIA0KDQpBbGd1bm9zIHVzb3MgdMOtcGljb3MgZGUgZXN0YSB0w6ljbmljYSBzb246IA0KDQoqIFNlZ21lbnRhY2nDs24gZGUgY2xpZW50ZXMgIA0KKiBEZXRlY2Npw7NuIGRlIGFub3JtYWxpZGFkZXMgIA0KKiBDYXRlZ29yaXphY2nDs24gZGUgZG9jdW1lbnRvcw0KDQojIDxzcGFuIHN0eWxlPSJjb2xvcjojRDgxQjYwIj5JbnN0YWxhciBwYXF1ZXRlcyB5IGxsYW1hciBsaWJyZXLDrWFzPC9zcGFuPg0KYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0NCiNpbnN0YWxsLnBhY2thZ2VzKCJjbHVzdGVyIikgIyBBbsOhbGlzaXMgZGUgYWdydXBhbWllbnRvDQpsaWJyYXJ5KGNsdXN0ZXIpDQojaW5zdGFsbC5wYWNrYWdlcygiZ2dwbG90MiIpICMgR3JhZmljYXINCmxpYnJhcnkoZ2dwbG90MikNCiNpbnN0YWxsLnBhY2thZ2VzKCJkYXRhLnRhYmxlIikgIyBNYW5lam8gZGUgbXVjaG9zIGRhdG9zDQpsaWJyYXJ5KGRhdGEudGFibGUpDQojaW5zdGFsbC5wYWNrYWdlcygiZmFjdG9leHRyYSIpICMgR3LDoWZpY2EgZGUgb3B0aW1pemFjacOzbiBkZSBuw7ptZXJvIGRlIGNsw7pzdGVycw0KbGlicmFyeShmYWN0b2V4dHJhKQ0KI2luc3RhbGwucGFja2FnZXMoImRhdGFzZXRzIikNCmxpYnJhcnkoZGF0YXNldHMpDQojaW5zdGFsbC5wYWNrYWdlcygidGlkeXZlcnNlIikNCmxpYnJhcnkodGlkeXZlcnNlKQ0KYGBgDQoNCiMgPHNwYW4gc3R5bGU9ImNvbG9yOiNEODFCNjAiPkVqZXJjaWNpbyAxLiBQdW50b3M8L3NwYW4+DQojIyA8c3BhbiBzdHlsZT0iY29sb3I6I0Y0OEZCMSI+Q29udGV4dG88L3NwYW4+DQpBZ3J1cGEgbG9zIHNpZ3VpZW50ZXMgb2NobyBwdW50b3MuIA0KDQojIyA8c3BhbiBzdHlsZT0iY29sb3I6I0Y0OEZCMSI+T2J0ZW5lciBkYXRvczwvc3Bhbj4NCmBgYHtyfQ0KZGYxIDwtIGRhdGEuZnJhbWUoeD1jKDIsMiw4LDUsNyw2LDEsNCksIHk9YygxMCw1LDQsOCw1LDQsMiw5KSkNCmBgYA0KDQojIyA8c3BhbiBzdHlsZT0iY29sb3I6I0Y0OEZCMSI+RW50ZW5kZXIgZGF0b3M8L3NwYW4+DQpgYGB7cn0NCnN1bW1hcnkoZGYxKQ0Kc3RyKGRmMSkNCnBsb3QoZGYxJHgsIGRmMSR5KQ0KYGBgDQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5Fc2NhbGFyIGRhdG9zPC9zcGFuPg0KYGBge3J9DQojIGRhdG9zX2VzY2FsYWRvcyA8LSBzY2FsZShkYXRvc19vcmlnaW5hbGVzKQ0KYGBgDQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5Bc2lnbmFyIG51bWVybyBkZSBncnVwb3M8L3NwYW4+DQpgYGB7cn0NCmdydXBvczEgPC0gMw0KYGBgDQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5BZ3J1cGFyIGxvcyBwdW50b3M8L3NwYW4+DQpgYGB7cn0NCnNldC5zZWVkKDEyMykNCmNsdXN0ZXJzMSA8LSBrbWVhbnMoZGYxLCBncnVwb3MxKQ0KY2x1c3RlcnMxDQpgYGANCg0KIyMgPHNwYW4gc3R5bGU9ImNvbG9yOiNGNDhGQjEiPk9wdGltaXphciBlbCBuw7ptZXJvIGRlIGdydXBvczwvc3Bhbj4NCmBgYHtyfQ0Kc2V0LnNlZWQoMTIzKQ0Kb3B0aW1pemFjaW9uMSA8LSBjbHVzR2FwKGRmMSwgRlVOPWttZWFucywgbnN0YXJ0PTIsIEsubWF4ID0gNykNCnBsb3Qob3B0aW1pemFjaW9uMSwgeGxhYj0iTsO6bWVybyBkZSBjbHVzdGVycyBLIiwgbWFpbj0iT3B0aW1pemFjacOzbiBkZSBjbHVzdGVycyIpDQojRWwgw7NwdGltbyBlcyBlbCBwcmltZXIgcHVudG8gbcOhcyBhbHRvDQpgYGANCg0KIyMgPHNwYW4gc3R5bGU9ImNvbG9yOiNGNDhGQjEiPkdyYWZpY2FyIGxvcyBncnVwb3M8L3NwYW4+DQpgYGB7cn0NCmZ2aXpfY2x1c3RlcihjbHVzdGVyczEsIGRhdGE9ZGYxKQ0KYGBgDQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5BZ3JlZ2FyIGdydXBvcyBhIGxhIGJhc2UgZGUgZGF0b3M8L3NwYW4+DQpgYGB7cn0NCmRmMV9jbHVzdGVycyA8LSBjYmluZChkZjEsIGNsdXN0ZXIgPSBjbHVzdGVyczEkY2x1c3RlcikNCmhlYWQoZGYxX2NsdXN0ZXJzKQ0KYGBgDQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5Db25jbHVzaW9uZXM8L3NwYW4+DQpMYSB0w6ljaWNhIGRlICpjbHVzdGVyaW5nKiBwZXJtaXRlIGlkZW50aWZpY2FyIHBhdHJvbmVzIG8gZ3J1cG9zIG5hdHVyYWxlcyBlbiBsb3MgZGF0b3Mgc2luIG5lY2VzaWRhZCBkZSBldGlxdWV0YXMgcHJldmlhcw0KDQoNCiMgPHNwYW4gc3R5bGU9ImNvbG9yOiNEODFCNjAiPkVqZXJjaWNpbyAyLiBVU0FycmVzdHM8L3NwYW4+DQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5Db250ZXh0bzwvc3Bhbj4NCkxhIGJhc2UgZGUgZGF0b3MgKipVU0FycmVzdHMqKiBjb250aWVuZSBlc3RhZMOtc3RpY2FzIGVuIGFycmVzdG9zIHBvciBjYWRhIDEwMCwwMDAgcmVzaWRlbnRlcyBwb3IgYWdyZXNpw7NuLCBhc2VzaW5hdG8geSB2aW9sYWNpw7NuIGVuIGNhZGEgdW5vIGRlIGxvcyA1MCBlc3RhZG9zIGRlIEVFLlVVLiBlbiAxOTczLiAgDQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5PYnRlbmVyIGRhdG9zPC9zcGFuPg0KYGBge3J9DQpkZjIgPC0gVVNBcnJlc3RzDQpkZjIgPC0gZGYyICU+JSBzZWxlY3QoLVVyYmFuUG9wKQ0KYGBgDQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5FbnRlbmRlciBkYXRvczwvc3Bhbj4NCmBgYHtyfQ0Kc3VtbWFyeShkZjIpDQpzdHIoZGYyKQ0KYGBgDQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5Fc2NhbGFyIGRhdG9zPC9zcGFuPg0KYGBge3J9DQpkZjJfZXNjYWxhZG8gPC0gc2NhbGUoZGYyKQ0Kc3VtbWFyeShkZjJfZXNjYWxhZG8pDQpgYGANCg0KIyMgPHNwYW4gc3R5bGU9ImNvbG9yOiNGNDhGQjEiPkFzaWduYXIgbnVtZXJvIGRlIGdydXBvczwvc3Bhbj4NCmBgYHtyfQ0KZ3J1cG9zMiA8LSA1DQpgYGANCg0KIyMgPHNwYW4gc3R5bGU9ImNvbG9yOiNGNDhGQjEiPkFncnVwYXIgbG9zIHB1bnRvczwvc3Bhbj4NCmBgYHtyfQ0Kc2V0LnNlZWQoMTIzKQ0KY2x1c3RlcnMyIDwtIGttZWFucyhkZjJfZXNjYWxhZG8sIGdydXBvczIpDQpjbHVzdGVyczINCmBgYA0KDQojIyA8c3BhbiBzdHlsZT0iY29sb3I6I0Y0OEZCMSI+T3B0aW1pemFyIGVsIG7Dum1lcm8gZGUgZ3J1cG9zPC9zcGFuPg0KYGBge3J9DQpzZXQuc2VlZCgxMjMpDQpvcHRpbWl6YWNpb24yIDwtIGNsdXNHYXAoZGYyX2VzY2FsYWRvLCBGVU49a21lYW5zLCBuc3RhcnQ9MSwgSy5tYXggPSAxMCkNCnBsb3Qob3B0aW1pemFjaW9uMiwgeGxhYj0iTsO6bWVybyBkZSBjbHVzdGVycyBLIiwgbWFpbj0iT3B0aW1pemFjacOzbiBkZSBjbHVzdGVycyIpDQojRWwgw7NwdGltbyBlcyBlbCBwcmltZXIgcHVudG8gbcOhcyBhbHRvDQpgYGANCg0KIyMgPHNwYW4gc3R5bGU9ImNvbG9yOiNGNDhGQjEiPkdyYWZpY2FyIGxvcyBncnVwb3M8L3NwYW4+DQpgYGB7cn0NCmZ2aXpfY2x1c3RlcihjbHVzdGVyczIsIGRhdGE9ZGYyX2VzY2FsYWRvKQ0KYGBgDQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5BZ3JlZ2FyIGdydXBvcyBhIGxhIGJhc2UgZGUgZGF0b3M8L3NwYW4+DQpgYGB7cn0NCmRmMl9jbHVzdGVycyA8LSBjYmluZChkZjIsIGNsdXN0ZXIgPSBjbHVzdGVyczIkY2x1c3RlcikNCmhlYWQoZGYyX2NsdXN0ZXJzKQ0KDQpkZjJfY2x1c3RlcnMgJT4lIGdyb3VwX2J5KGNsdXN0ZXIpICU+JSBzdW1tYXJpc2VfYWxsKG1lYW4pICU+JSBtdXRhdGUoaW5kaWNhZG9yX2luc2VndXJpZGFkID0gTXVyZGVyICsgQXNzYXVsdCArIFJhcGUpDQoNCmRmMl9jbHVzdGVycyA8LSBkZjJfY2x1c3RlcnMgJT4lIA0KICBtdXRhdGUoY2x1c3RlciA9IGNhc2Vfd2hlbigNCiAgICBjbHVzdGVyID09IDEgfiAiSW5zZWd1cmlkYWQgbXV5IGFsdGEiLA0KICAgIGNsdXN0ZXIgPT0gNCB+ICJJbnNlZ3VyaWRhZCAgYWx0YSIsDQogICAgY2x1c3RlciA9PSA1IH4gIkluc2VndXJpZGFkIG1lZGlhIiwNCiAgICBjbHVzdGVyID09IDMgfiAiSW5zZWd1cmlkYWQgYmFqYSIsDQogICAgY2x1c3RlciA9PSAyIH4gIkluc2VndXJpZGFkIG11eSBiYWphIiwNCiAgKSkNCmhlYWQoZGYyX2NsdXN0ZXJzKQ0KYGBgDQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5Db25jbHVzaW9uZXM8L3NwYW4+DQpMYSB0w6ljaWNhIGRlICpjbHVzdGVyaW5nKiBwZXJtaXRlIGlkZW50aWZpY2FyIHBhdHJvbmVzIG8gZ3J1cG9zIG5hdHVyYWxlcyBlbiBsb3MgZGF0b3Mgc2luIG5lY2VzaWRhZCBkZSBldGlxdWV0YXMgcHJldmlhcy4NCg0KDQojIDxzcGFuIHN0eWxlPSJjb2xvcjojRDgxQjYwIj5FamVyY2ljaW8gMy4gU2VnbWVudGFjacOzbiBkZSBjbGllbnRlczwvc3Bhbj4NCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5Db250ZXh0bzwvc3Bhbj4NCkxhIGJhc2UgZGUgZGF0b3MgKip2ZW50YXMqKiB0aWVuZSBsb3MgcmVnaXN0cm9zIGVudHJlIGVsIDEgZGUgZGljaWVtYnJlIGRlbCAyMDEwIHkgZWwgOSBkZSBkaWNpZW1icmUgZGVsIDIwMTEgZGUgbGFzIHZlbnRhcyBkZSB1bmEgZW1wcmVzYSBtaW5vcmlzdGEgZW4gbMOtbmVhIHNpbiB0aWVuZGEgZsOtc2ljYSwgYmFzYWRhIGVuIFJlaW5vIFVuaWRvLiAgDQpMYSBlbXByZXNhIHZlbmRlIHByaW5jaXBhbG1lbnRlIHJlZ2Fsb3Mgw7puaWNvcyBwYXJhIHRvZGEgb2Nhc2nDs24geSBtdWNob3MgZGUgc2lzIGNsaWVudGVzIHNvbiBtYXlvcmlzdGFzLiAgDQpPYmpldGl2bzogU2VnbWVudGFyIGNsaWVudGVzLCBhc2lnbmFybGVzIG5vbWJyZXMgeSBjYXJhY3RlcsOtc3RpY2FzIGRlIGNvbXBvcnRhbWllbnRvIHkgcHJvcG9uZXIgc3VnZXJlbmNpYXMgYSBsYXMgZW1wcmVzYXMgcGFyYSBhdW1lbnRhciBsYXMgdmVudGFzLiANCg0KIyMgPHNwYW4gc3R5bGU9ImNvbG9yOiNGNDhGQjEiPk9idGVuZXIgZGF0b3M8L3NwYW4+DQpgYGB7cn0NCmRmMyA8LSByZWFkLmNzdigiQzpcXFVzZXJzXFxuYXRhbFxcT25lRHJpdmVcXENhcnJlcmFcXDdtb1NlbWVzdHJlXFxNb2R1bG8yXFx2ZW50YXMuY3N2IikNCmBgYA0KDQojIyA8c3BhbiBzdHlsZT0iY29sb3I6I0Y0OEZCMSI+RW50ZW5kZXIgZGF0b3M8L3NwYW4+DQpgYGB7cn0NCnN1bW1hcnkoZGYzKQ0Kc3RyKGRmMykNCmBgYA0KDQojIyA8c3BhbiBzdHlsZT0iY29sb3I6I0Y0OEZCMSI+Q3JlYXIgdmFyaWFibGVzIGEgYW5hbGl6YXI8L3NwYW4+DQpgYGB7cn0NCmRmMyRWZW50YSA8LSBkZjMkQ2FudGlkYWQgKiBkZjMkUHJlY2lvDQoNCmxpYnJhcnkoZHBseXIpDQoNCnRpY2tldHNfY2xpZW50ZSA8LSBkZjMgJT4lDQogIGdyb3VwX2J5KENsaWVudGUsIFRpY2tldCkgJT4lDQogIHN1bW1hcmlzZSgNCiAgICBUb3RhbF9UaWNrZXQgPSBzdW0oVmVudGEsIG5hLnJtID0gVFJVRSksDQogICAgLmdyb3VwcyA9ICJkcm9wIg0KICApDQoNCnRpY2tldF9wcm9tZWRpbyA8LSB0aWNrZXRzX2NsaWVudGUgJT4lDQogIGdyb3VwX2J5KENsaWVudGUpICU+JQ0KICBzdW1tYXJpc2UoDQogICAgVGlja2V0X1Byb21lZGlvID0gbWVhbihUb3RhbF9UaWNrZXQsIG5hLnJtID0gVFJVRSksDQogICAgLmdyb3VwcyA9ICJkcm9wIg0KICApDQoNCmZyZWN1ZW5jaWEgPC0gZGYzICU+JQ0KICBncm91cF9ieShDbGllbnRlKSAlPiUNCiAgc3VtbWFyaXNlKA0KICAgIEZyZWN1ZW5jaWFfQ29tcHJhID0gbl9kaXN0aW5jdChUaWNrZXQpLA0KICAgIC5ncm91cHMgPSAiZHJvcCINCiAgKQ0KDQpgYGANCg0KYGBge3J9DQpjbGllbnRlc19jbHVzdGVyIDwtIHRpY2tldF9wcm9tZWRpbyAlPiUNCiAgbGVmdF9qb2luKGZyZWN1ZW5jaWEsIGJ5ID0gIkNsaWVudGUiKQ0KYGBgDQoNCg0KIyMgPHNwYW4gc3R5bGU9ImNvbG9yOiNGNDhGQjEiPkFzaWduYXIgbnVtZXJvIGRlIGdydXBvczwvc3Bhbj4NCmBgYHtyfQ0KZ3J1cG9zMiA8LSA0DQpgYGANCg0KIyMgPHNwYW4gc3R5bGU9ImNvbG9yOiNGNDhGQjEiPkFncnVwYXIgbG9zIHB1bnRvczwvc3Bhbj4NCmBgYHtyfQ0Kc2V0LnNlZWQoMTIzKQ0KY2x1c3RlcnMyIDwtIGttZWFucyhkZjJfZXNjYWxhZG8sIGdydXBvczIpDQpjbHVzdGVyczINCmBgYA0KDQojIyA8c3BhbiBzdHlsZT0iY29sb3I6I0Y0OEZCMSI+T3B0aW1pemFyIGVsIG7Dum1lcm8gZGUgZ3J1cG9zPC9zcGFuPg0KYGBge3J9DQpzZXQuc2VlZCgxMjMpDQpvcHRpbWl6YWNpb24yIDwtIGNsdXNHYXAoZGYyX2VzY2FsYWRvLCBGVU49a21lYW5zLCBuc3RhcnQ9MSwgSy5tYXggPSAxMCkNCnBsb3Qob3B0aW1pemFjaW9uMiwgeGxhYj0iTsO6bWVybyBkZSBjbHVzdGVycyBLIiwgbWFpbj0iT3B0aW1pemFjacOzbiBkZSBjbHVzdGVycyIpDQojRWwgw7NwdGltbyBlcyBlbCBwcmltZXIgcHVudG8gbcOhcyBhbHRvDQpgYGANCg0KIyMgPHNwYW4gc3R5bGU9ImNvbG9yOiNGNDhGQjEiPkdyYWZpY2FyIGxvcyBncnVwb3M8L3NwYW4+DQpgYGB7cn0NCmZ2aXpfY2x1c3RlcihjbHVzdGVyczIsIGRhdGE9ZGYyX2VzY2FsYWRvKQ0KYGBgDQoNCiMjIDxzcGFuIHN0eWxlPSJjb2xvcjojRjQ4RkIxIj5BZ3JlZ2FyIGdydXBvcyBhIGxhIGJhc2UgZGUgZGF0b3M8L3NwYW4+DQpgYGB7cn0NCmRmMl9jbHVzdGVycyA8LSBjYmluZChkZjIsIGNsdXN0ZXIgPSBjbHVzdGVyczIkY2x1c3RlcikNCmhlYWQoZGYyX2NsdXN0ZXJzKQ0KDQpkZjJfY2x1c3RlcnMgJT4lIGdyb3VwX2J5KGNsdXN0ZXIpICU+JSBzdW1tYXJpc2VfYWxsKG1lYW4pICU+JSBtdXRhdGUoaW5kaWNhZG9yX2luc2VndXJpZGFkID0gTXVyZGVyICsgQXNzYXVsdCArIFJhcGUpDQoNCmRmMl9jbHVzdGVycyA8LSBkZjJfY2x1c3RlcnMgJT4lIA0KICBtdXRhdGUoY2x1c3RlciA9IGNhc2Vfd2hlbigNCiAgICBjbHVzdGVyID09IDEgfiAiSW5zZWd1cmlkYWQgbXV5IGFsdGEiLA0KICAgIGNsdXN0ZXIgPT0gNCB+ICJJbnNlZ3VyaWRhZCAgYWx0YSIsDQogICAgY2x1c3RlciA9PSA1IH4gIkluc2VndXJpZGFkIG1lZGlhIiwNCiAgICBjbHVzdGVyID09IDMgfiAiSW5zZWd1cmlkYWQgYmFqYSIsDQogICAgY2x1c3RlciA9PSAyIH4gIkluc2VndXJpZGFkIG11eSBiYWphIiwNCiAgKSkNCmhlYWQoZGYyX2NsdXN0ZXJzKQ0KYGBgDQoNCiMgPHNwYW4gc3R5bGU9ImNvbG9yOiNEODFCNjAiPkNvbmNsdXNpb25lczwvc3Bhbj4NCkxhIHTDqWNpY2EgZGUgKmNsdXN0ZXJpbmcqIHBlcm1pdGUgaWRlbnRpZmljYXIgcGF0cm9uZXMgbyBncnVwb3MgbmF0dXJhbGVzIGVuIGxvcyBkYXRvcyBzaW4gbmVjZXNpZGFkIGRlIGV0aXF1ZXRhcyBwcmV2aWFzDQo=