Es una técnica de clasificación en donde la variable respuesta es cuantitativa.

El objetivo es:

  • Separar los grupos, identificando las variables que permiten esa separación

  • Clasificar a nuevos individuos

La idea es contruir funciones discriminantes (FD) que maximicen la variabilidad entre grupos con el objetivo de discriminarlos mejor. Esto se logra al maximizar la varianza entre grupos en relación con la varianza total

Base de datos

Vamos a trabajar con la base de datos de Iris

data(iris)
glimpse(iris)
## Rows: 150
## Columns: 5
## $ Sepal.Length <dbl> 5.1, 4.9, 4.7, 4.6, 5.0, 5.4, 4.6, 5.0, 4.4, 4.9, 5.4, 4.~
## $ Sepal.Width  <dbl> 3.5, 3.0, 3.2, 3.1, 3.6, 3.9, 3.4, 3.4, 2.9, 3.1, 3.7, 3.~
## $ Petal.Length <dbl> 1.4, 1.4, 1.3, 1.5, 1.4, 1.7, 1.4, 1.5, 1.4, 1.5, 1.5, 1.~
## $ Petal.Width  <dbl> 0.2, 0.2, 0.2, 0.2, 0.2, 0.4, 0.3, 0.2, 0.2, 0.1, 0.2, 0.~
## $ Species      <fct> setosa, setosa, setosa, setosa, setosa, setosa, setosa, s~

Realicemos algunos scatterplots

library(GGally)

ggpairs(iris, legend = 1, columns = 1:4, aes(color = Species, alpha = 0.5),
        upper = list(continuous = "points"))+
  theme(legend.position = "bottom")

Al conocerse la especie de pertenencia de cada individuo, se puede comprobar la efectividad del método de clasificación observando el porcentaje de casos bien clasificados. Para ello, vamos a separar el dataset en train y test

set.seed(123)#setear la semilla
# Create data split for train and test
df_split <- initial_split(iris,
                          prop = 0.9,
                          strata = Species)#para conservar la proporción de las clases

df_train <- df_split %>%
              training()

df_test <- df_split %>%
              testing()

# Número de datos en test y train
paste0("Total del dataset de entrenamiento: ", nrow(df_train))
## [1] "Total del dataset de entrenamiento: 135"
paste0("Total del dataset de testeo: ", nrow(df_test))
## [1] "Total del dataset de testeo: 15"

Creamos tres subsets de datos para cada especie

setosa<- subset(df_train[,1:4], df_train$Species == "setosa")
versicolor<- subset(df_train[,1:4], df_train$Species == "versicolor")
virginica <- subset(df_train[,1:4], df_train$Species=="virginica")

Análisis Discriminante Lineal (LDA)

Este tipo de análisis es válido solo si se satisfacen los siguientes supuestos:

1- Normalidad multivariada

2- Independencia de las observaciones

3- Homocedasticidad.

Verefiquemos supuestos

1- Normalidad multivariada

¿Cuál es la hipótesis estadística?

mvShapiro.Test(as.matrix(setosa))
## 
##  Generalized Shapiro-Wilk test for Multivariate Normality by
##  Villasenor-Alva and Gonzalez-Estrada
## 
## data:  as.matrix(setosa)
## MVW = 0.96115, p-value = 0.0371
mvShapiro.Test(as.matrix(versicolor))  
## 
##  Generalized Shapiro-Wilk test for Multivariate Normality by
##  Villasenor-Alva and Gonzalez-Estrada
## 
## data:  as.matrix(versicolor)
## MVW = 0.97362, p-value = 0.4165
mvShapiro.Test(as.matrix(virginica))
## 
##  Generalized Shapiro-Wilk test for Multivariate Normality by
##  Villasenor-Alva and Gonzalez-Estrada
## 
## data:  as.matrix(virginica)
## MVW = 0.98463, p-value = 0.9764

2- Independencia de las observaciones

Viene dada por el diseño

3- Homocedasticidad

Ho las matrices de varianzas-covarianzas de los grupos son iguales.

Analizamos igualdad de matrices de varianzas y covarianzas:

boxM(df_train[,-5],df_train[,5])
## 
##  Box's M-test for Homogeneity of Covariance Matrices
## 
## data:  df_train[, -5]
## Chi-Sq (approx.) = 136.76, df = 20, p-value < 2.2e-16

Entonces ¿qué concluimos?

Vamos a proseguir como si se hubiese cumplido todos los supuestos. Tener en cuenta que los resultados del LDA no van a ser confiables en este caso.

LDA

model_lda <- lda(Species~., data =df_train)
model_lda
## Call:
## lda(Species ~ ., data = df_train)
## 
## Prior probabilities of groups:
##     setosa versicolor  virginica 
##  0.3333333  0.3333333  0.3333333 
## 
## Group means:
##            Sepal.Length Sepal.Width Petal.Length Petal.Width
## setosa         4.991111    3.393333     1.471111   0.2377778
## versicolor     5.940000    2.757778     4.262222   1.3266667
## virginica      6.566667    2.977778     5.506667   2.0133333
## 
## Coefficients of linear discriminants:
##                     LD1        LD2
## Sepal.Length  0.7633602 -0.2360469
## Sepal.Width   1.8553244  2.4183855
## Petal.Length -2.2547164 -0.7663631
## Petal.Width  -2.9175526  2.6999226
## 
## Proportion of trace:
##    LD1    LD2 
## 0.9913 0.0087

El objeto lda (en este ejemplo, model_lda) contiene los siguientes componentes:

prior: las probabilidades previas utilizadas.

means: la media de cada clase.

svd: son los valores singulares, informan el cociente entre desvíos estándar entre y dentro de grupos para cada FD; si se elevan al cuadrado se obtiene el autovalor de cada FD

counts: El número de observaciones por clase.

Coefficients of linear discriminants: Muestra la combinación lineal de variables predictoras que se utilizan para formar la regla de decisión LDA.

Por ejemplo:

\(\ LD1= 0.76*Sepal.Length+ 1.85*Sepal.Width - 2.25*Petal.Length -2.91*Petal.Width\)

LD1 explica el 99% de la proporción de varianza entre clases.

La 2da función discriminante es independiente de la primera (ortogonal) y es la que mejor separa los grupos usando la variación remanente o residual, después que la 1ra función discriminante ha sido determinada

prop = model_lda$svd^2/sum(model_lda$svd^2)
prop #varianza entre grupos explicada por cada FD
## [1] 0.991319021 0.008680979
lda.data <- cbind(df_train, predict(model_lda)$x)
ggplot(lda.data, aes(LD1, LD2)) +
  geom_point(aes(color = Species))

Veamos que predice el modelo en df_test

predictions <- model_lda %>% predict(df_test)
predictions
## $class
##  [1] setosa     setosa     setosa     setosa     setosa     versicolor
##  [7] versicolor versicolor versicolor versicolor virginica  virginica 
## [13] virginica  virginica  virginica 
## Levels: setosa versicolor virginica
## 
## $posterior
##           setosa   versicolor    virginica
## 2   1.000000e+00 1.249522e-19 2.400232e-39
## 16  1.000000e+00 1.695972e-31 2.933345e-53
## 23  1.000000e+00 4.323480e-28 7.878366e-50
## 34  1.000000e+00 2.371974e-32 4.218843e-55
## 44  1.000000e+00 7.284354e-18 2.344684e-35
## 51  3.482024e-20 9.999108e-01 8.921915e-05
## 60  2.108587e-22 9.994953e-01 5.047370e-04
## 70  1.717244e-19 9.999965e-01 3.547080e-06
## 89  2.753852e-19 9.999581e-01 4.187694e-05
## 92  7.431814e-24 9.981819e-01 1.818098e-03
## 101 1.698805e-55 4.638431e-09 1.000000e+00
## 119 4.077561e-65 4.227345e-10 1.000000e+00
## 125 1.930807e-42 7.142563e-05 9.999286e-01
## 131 2.082064e-46 7.590232e-05 9.999241e-01
## 143 1.949097e-41 6.623572e-04 9.993376e-01
## 
## $x
##           LD1         LD2
## 2    7.395395 -0.76528994
## 16   9.794555  2.89496048
## 23   9.181468  1.06310065
## 34  10.079800  1.99514454
## 44   6.781428  1.34699455
## 51  -1.572111 -0.06640228
## 60  -2.070049 -0.23762022
## 70  -1.260504 -1.62569284
## 89  -1.367295 -0.02978819
## 92  -2.404729 -0.26100090
## 101 -8.061370  2.31431193
## 119 -9.737127 -0.93873481
## 125 -5.912590  1.36983307
## 131 -6.624276 -0.85112223
## 143 -5.776469  0.05107727

Veamos la matriz de confusión en df_train

table(predict(model_lda,type="class")$class,df_train$Species)
##             
##              setosa versicolor virginica
##   setosa         45          0         0
##   versicolor      0         43         1
##   virginica       0          2        44

partimat muestra una matriz de gráficos para cada combinación de dos variables. Cada gráfico muestra una vista diferente de los mismos datos. Las regiones coloreadas delimitan cada área de clasificación. Se predice que cualquier observación que se encuentre dentro de una región pertenece a una clase específica. Cada gráfico también incluye la tasa de error aparente para esa vista de los datos.

library(klaR) 
partimat (Species~. , data=df_train , method="lda")

Veamos la performance en df_test

lda.test <- predict(model_lda,df_test)
df_test$lda <- lda.test$class
table(df_test$lda,df_test$Species)
##             
##              setosa versicolor virginica
##   setosa          5          0         0
##   versicolor      0          5         0
##   virginica       0          0         5

Biplot

#install.packages("devtools")
#library(devtools)
#install_github("fawda123/ggord")
library(ggord)
ggord(model_lda, df_train$Species, xlim = c(-10, 11))

Análisis discriminante cuadrático (QDA)

El discriminante se dice cuadrático porque el término de segundo orden no se cancela como en el caso del discriminante lineal. QDA no asume la igualdad en la matriz de varianzas/covarianzas. En otras palabras, para QDA la matriz de covarianza puede ser diferente para cada clase.

Vamos a aplicar QDA, a pesar de que no se satisface el supuesto de normalidad multivariada.

model_qda <- qda(Species ~ ., df_train)
model_qda
## Call:
## qda(Species ~ ., data = df_train)
## 
## Prior probabilities of groups:
##     setosa versicolor  virginica 
##  0.3333333  0.3333333  0.3333333 
## 
## Group means:
##            Sepal.Length Sepal.Width Petal.Length Petal.Width
## setosa         4.991111    3.393333     1.471111   0.2377778
## versicolor     5.940000    2.757778     4.262222   1.3266667
## virginica      6.566667    2.977778     5.506667   2.0133333
partimat(Species ~ ., data=df_train, method="qda")

table(predict(model_qda,type="class")$class,df_train$Species)
##             
##              setosa versicolor virginica
##   setosa         45          0         0
##   versicolor      0         43         1
##   virginica       0          2        44
lda.test_qda <- predict(model_qda,df_test)
df_test$qda <- lda.test_qda$class
table(df_test$qda,df_test$Species)
##             
##              setosa versicolor virginica
##   setosa          5          0         0
##   versicolor      0          5         0
##   virginica       0          0         5

Algunos comentarios

  • El ánalisis discriminante es una técnica sensible a la presencia de outliers

  • Si el supuesto de normalidad multivariada se sostiene pero hay outliers es recomendable recurrir a la versión robusta de QDA.

  • Si se rechaza la normalidad multivariada, el modelo robusto no es adecuado.

¿Qué hacer si no se cumple el supuesto de normalidad multivariada?

Hay diversas opiniones al respecto. Algunos mencionan que LDA es robusto a la falta de normalidad multivariada si los datos son lo suficientemente grandes.1 Sin embargo, Lachenbruch et al. (1973)2 han demostrado que los resultados de aplicar LDA si se ven muy afectados por la falta de normalidad multivariada luego de usar tres tipos de distribuciones no normales. Por otra parte, también se ha encontrado que QDA si es robusto a la falta de normalidad si las distribuciones de los datos se alejan ligeramente de distribución teórica3

Actualmente, se han propuesto alternativas no paramétricas para los casos en que el supuesto de normalidad no se cumple.4 haciendo uso de matrices de dispersión, por ejemplo. Además, Sharipah Soaad Syed Yahaya et al. (2016)5 proponen el uso de dos estimadores robusto llamados one-step M-estimator (MOM) y winsorized modified one-step M-estimator (WMOM), que permiten trabajar con aquellos datos que no solo no siguen una distribución normal sino que tambien son heterocedásticos.

Finalmente, se propone también el uso de algoritmos mas complejos que permiten proseguir cuando no se cumplen los supuestos y no hay necesidad de transformar los datos para ello. Uno de los modelos propuestos es el uso de Árboles de decisión para clasificación6

LS0tDQp0aXRsZTogIkFuw6FsaXNpcyBEaXNjcmltaW5hbnRlIg0KYXV0aG9yOiAiUGFtZWxhIEUuIFBhaXJvIg0Kb3V0cHV0Og0KICBodG1sX2RvY3VtZW50Og0KICAgIHRvYzogeWVzDQogICAgY29kZV9mb2xkaW5nOiBzaG93DQogICAgdG9jX2Zsb2F0OiB5ZXMNCiAgICBkZl9wcmludDogcGFnZWQNCiAgICB0aGVtZTogdW5pdGVkDQogICAgY29kZV9kb3dubG9hZDogdHJ1ZQ0KLS0tDQoNCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQ0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFKQ0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KG1lc3NhZ2UgPSBGQUxTRSkNCmtuaXRyOjpvcHRzX2NodW5rJHNldCh3YXJuaW5nID0gRkFMU0UpDQpsaWJyYXJ5KHRpZHl2ZXJzZSkNCmxpYnJhcnkodGlkeW1vZGVscykNCmxpYnJhcnkoZmFjdG9leHRyYSkNCmxpYnJhcnkobXZTaGFwaXJvVGVzdCkNCmxpYnJhcnkoYmlvdG9vbHMpDQpsaWJyYXJ5KGRvd25sb2FkdGhpcykNCmxpYnJhcnkoTUFTUykNCmxpYnJhcnkoa2xhUikNCmBgYA0KDQpgYGB7ciwgZWNobyA9IEZBTFNFfQ0KDQpkb3dubG9hZF9saW5rKA0KICBsaW5rID0gImh0dHBzOi8vZ2l0aHViLmNvbS9QYW1lbGFQYWlyby9tYWVzdHJpYV9ETS9yYXcvbWFpbi9BSUQvQUQvYW5hbGlzaXNfZGlzY3JpbWluYW50ZS5SbWQiLA0KICBidXR0b25fbGFiZWwgPSAiRG93bmxvYWQgLlJtZCIsDQogIGJ1dHRvbl90eXBlID0gImRhbmdlciIsDQogIGhhc19pY29uID0gVFJVRSwNCiAgaWNvbiA9ICJmYSBmYS1zYXZlIiwNCiAgc2VsZl9jb250YWluZWQgPSBGQUxTRQ0KKQ0KYGBgDQoNCg0KRXMgdW5hIHTDqWNuaWNhIGRlICoqY2xhc2lmaWNhY2nDs24qKiBlbiBkb25kZSBsYSB2YXJpYWJsZSByZXNwdWVzdGEgZXMgY3VhbnRpdGF0aXZhLg0KDQpFbCBvYmpldGl2byBlczoNCg0KLSBTZXBhcmFyIGxvcyBncnVwb3MsIGlkZW50aWZpY2FuZG8gbGFzIHZhcmlhYmxlcyBxdWUgcGVybWl0ZW4gZXNhIHNlcGFyYWNpw7NuDQoNCi0gQ2xhc2lmaWNhciBhIG51ZXZvcyBpbmRpdmlkdW9zDQoNCkxhIGlkZWEgZXMgY29udHJ1aXIgZnVuY2lvbmVzIGRpc2NyaW1pbmFudGVzIChGRCkgcXVlIG1heGltaWNlbiBsYSB2YXJpYWJpbGlkYWQgZW50cmUgZ3J1cG9zIGNvbiBlbCBvYmpldGl2byBkZSBkaXNjcmltaW5hcmxvcyBtZWpvci4gRXN0byBzZSBsb2dyYSBhbCBtYXhpbWl6YXIgbGEgdmFyaWFuemEgZW50cmUgZ3J1cG9zIGVuIHJlbGFjacOzbiBjb24gbGEgdmFyaWFuemEgdG90YWwNCg0KDQojIEJhc2UgZGUgZGF0b3MNCg0KVmFtb3MgYSB0cmFiYWphciBjb24gbGEgYmFzZSBkZSBkYXRvcyBkZSBgSXJpc2ANCg0KDQpgYGB7cn0NCmRhdGEoaXJpcykNCmdsaW1wc2UoaXJpcykNCmBgYA0KUmVhbGljZW1vcyBhbGd1bm9zIF9zY2F0dGVycGxvdHNfDQoNCmBgYHtyfQ0KbGlicmFyeShHR2FsbHkpDQoNCmdncGFpcnMoaXJpcywgbGVnZW5kID0gMSwgY29sdW1ucyA9IDE6NCwgYWVzKGNvbG9yID0gU3BlY2llcywgYWxwaGEgPSAwLjUpLA0KICAgICAgICB1cHBlciA9IGxpc3QoY29udGludW91cyA9ICJwb2ludHMiKSkrDQogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJib3R0b20iKQ0KYGBgDQoNCkFsIGNvbm9jZXJzZSBsYSBlc3BlY2llIGRlIHBlcnRlbmVuY2lhIGRlIGNhZGEgaW5kaXZpZHVvLCBzZSBwdWVkZSBjb21wcm9iYXIgbGEgZWZlY3RpdmlkYWQgZGVsIG3DqXRvZG8gZGUgY2xhc2lmaWNhY2nDs24gb2JzZXJ2YW5kbyBlbCBwb3JjZW50YWplIGRlIGNhc29zIGJpZW4gY2xhc2lmaWNhZG9zLiBQYXJhIGVsbG8sIHZhbW9zIGEgc2VwYXJhciBlbCBkYXRhc2V0IGVuIHRyYWluIHkgdGVzdA0KDQpgYGB7cn0NCnNldC5zZWVkKDEyMykjc2V0ZWFyIGxhIHNlbWlsbGENCiMgQ3JlYXRlIGRhdGEgc3BsaXQgZm9yIHRyYWluIGFuZCB0ZXN0DQpkZl9zcGxpdCA8LSBpbml0aWFsX3NwbGl0KGlyaXMsDQogICAgICAgICAgICAgICAgICAgICAgICAgIHByb3AgPSAwLjksDQogICAgICAgICAgICAgICAgICAgICAgICAgIHN0cmF0YSA9IFNwZWNpZXMpI3BhcmEgY29uc2VydmFyIGxhIHByb3BvcmNpw7NuIGRlIGxhcyBjbGFzZXMNCg0KZGZfdHJhaW4gPC0gZGZfc3BsaXQgJT4lDQogICAgICAgICAgICAgIHRyYWluaW5nKCkNCg0KZGZfdGVzdCA8LSBkZl9zcGxpdCAlPiUNCiAgICAgICAgICAgICAgdGVzdGluZygpDQoNCiMgTsO6bWVybyBkZSBkYXRvcyBlbiB0ZXN0IHkgdHJhaW4NCnBhc3RlMCgiVG90YWwgZGVsIGRhdGFzZXQgZGUgZW50cmVuYW1pZW50bzogIiwgbnJvdyhkZl90cmFpbikpDQpwYXN0ZTAoIlRvdGFsIGRlbCBkYXRhc2V0IGRlIHRlc3RlbzogIiwgbnJvdyhkZl90ZXN0KSkNCmBgYA0KQ3JlYW1vcyB0cmVzIHN1YnNldHMgZGUgZGF0b3MgcGFyYSBjYWRhIGVzcGVjaWUNCg0KYGBge3J9DQpzZXRvc2E8LSBzdWJzZXQoZGZfdHJhaW5bLDE6NF0sIGRmX3RyYWluJFNwZWNpZXMgPT0gInNldG9zYSIpDQp2ZXJzaWNvbG9yPC0gc3Vic2V0KGRmX3RyYWluWywxOjRdLCBkZl90cmFpbiRTcGVjaWVzID09ICJ2ZXJzaWNvbG9yIikNCnZpcmdpbmljYSA8LSBzdWJzZXQoZGZfdHJhaW5bLDE6NF0sIGRmX3RyYWluJFNwZWNpZXM9PSJ2aXJnaW5pY2EiKQ0KYGBgDQoNCiMgQW7DoWxpc2lzIERpc2NyaW1pbmFudGUgTGluZWFsIChMREEpDQoNCkVzdGUgdGlwbyBkZSBhbsOhbGlzaXMgZXMgdsOhbGlkbyBzb2xvIHNpIHNlIHNhdGlzZmFjZW4gbG9zIHNpZ3VpZW50ZXMgc3VwdWVzdG9zOg0KDQoxLSBOb3JtYWxpZGFkIG11bHRpdmFyaWFkYQ0KDQoyLSBJbmRlcGVuZGVuY2lhIGRlIGxhcyBvYnNlcnZhY2lvbmVzDQoNCjMtIEhvbW9jZWRhc3RpY2lkYWQuDQoNCiMjIFZlcmVmaXF1ZW1vcyBzdXB1ZXN0b3MNCg0KMS0gTm9ybWFsaWRhZCBtdWx0aXZhcmlhZGENCg0Kwr9DdcOhbCBlcyBsYSBoaXDDs3Rlc2lzIGVzdGFkw61zdGljYT8NCg0KYGBge3J9DQptdlNoYXBpcm8uVGVzdChhcy5tYXRyaXgoc2V0b3NhKSkNCm12U2hhcGlyby5UZXN0KGFzLm1hdHJpeCh2ZXJzaWNvbG9yKSkgIA0KbXZTaGFwaXJvLlRlc3QoYXMubWF0cml4KHZpcmdpbmljYSkpDQpgYGANCg0KMi0gSW5kZXBlbmRlbmNpYSBkZSBsYXMgb2JzZXJ2YWNpb25lcw0KDQpWaWVuZSBkYWRhIHBvciBlbCBkaXNlw7FvDQoNCjMtIEhvbW9jZWRhc3RpY2lkYWQNCg0KSG8gbGFzIG1hdHJpY2VzIGRlIHZhcmlhbnphcy1jb3ZhcmlhbnphcyBkZSBsb3MgZ3J1cG9zIHNvbiBpZ3VhbGVzLg0KDQpBbmFsaXphbW9zIGlndWFsZGFkIGRlIG1hdHJpY2VzIGRlIHZhcmlhbnphcyB5IGNvdmFyaWFuemFzOg0KDQpgYGB7cn0NCmJveE0oZGZfdHJhaW5bLC01XSxkZl90cmFpblssNV0pDQpgYGANCkVudG9uY2VzIMK/cXXDqSBjb25jbHVpbW9zPw0KDQpWYW1vcyBhIHByb3NlZ3VpciBjb21vIHNpIHNlIGh1Ymllc2UgY3VtcGxpZG8gdG9kb3MgbG9zIHN1cHVlc3Rvcy4gVGVuZXIgZW4gY3VlbnRhIHF1ZSBsb3MgcmVzdWx0YWRvcyBkZWwgTERBICoqbm8gdmFuIGEgc2VyIGNvbmZpYWJsZXMgZW4gZXN0ZSBjYXNvKiouDQoNCiMjIExEQQ0KDQpgYGB7cn0NCm1vZGVsX2xkYSA8LSBsZGEoU3BlY2llc34uLCBkYXRhID1kZl90cmFpbikNCm1vZGVsX2xkYQ0KYGBgDQpFbCBvYmpldG8gbGRhIChlbiBlc3RlIGVqZW1wbG8sIG1vZGVsX2xkYSkgY29udGllbmUgbG9zIHNpZ3VpZW50ZXMgY29tcG9uZW50ZXM6DQoNCipwcmlvcio6IGxhcyBwcm9iYWJpbGlkYWRlcyBwcmV2aWFzIHV0aWxpemFkYXMuDQoNCiptZWFucyo6IGxhIG1lZGlhIGRlIGNhZGEgY2xhc2UuDQoNCipzdmQqOiBzb24gbG9zIHZhbG9yZXMgc2luZ3VsYXJlcywgaW5mb3JtYW4gZWwgY29jaWVudGUgZW50cmUgZGVzdsOtb3MgZXN0w6FuZGFyIGVudHJlIHkgZGVudHJvIGRlIGdydXBvcyBwYXJhIGNhZGEgRkQ7IHNpIHNlIGVsZXZhbiBhbCBjdWFkcmFkbyBzZSBvYnRpZW5lIGVsIGF1dG92YWxvciBkZSBjYWRhIEZEDQoNCipjb3VudHMqOiBFbCBuw7ptZXJvIGRlIG9ic2VydmFjaW9uZXMgcG9yIGNsYXNlLg0KDQoqKkNvZWZmaWNpZW50cyBvZiBsaW5lYXIgZGlzY3JpbWluYW50cyoqOiBNdWVzdHJhIGxhIGNvbWJpbmFjacOzbiBsaW5lYWwgZGUgdmFyaWFibGVzIHByZWRpY3RvcmFzIHF1ZSBzZSB1dGlsaXphbiBwYXJhIGZvcm1hciBsYSByZWdsYSBkZSBkZWNpc2nDs24gTERBLg0KDQpQb3IgZWplbXBsbzoNCg0KJFwgTEQxPSAwLjc2KlNlcGFsLkxlbmd0aCsgMS44NSpTZXBhbC5XaWR0aCAtIDIuMjUqUGV0YWwuTGVuZ3RoIC0yLjkxKlBldGFsLldpZHRoJA0KDQpMRDEgZXhwbGljYSBlbCA5OSUgZGUgbGEgcHJvcG9yY2nDs24gZGUgdmFyaWFuemEgZW50cmUgY2xhc2VzLg0KDQpMYSAyZGEgZnVuY2nDs24gZGlzY3JpbWluYW50ZSBlcyBpbmRlcGVuZGllbnRlIGRlIGxhIHByaW1lcmEgKG9ydG9nb25hbCkgeSBlcyBsYSBxdWUgbWVqb3Igc2VwYXJhIGxvcyBncnVwb3MgdXNhbmRvIGxhIHZhcmlhY2nDs24gcmVtYW5lbnRlIG8gcmVzaWR1YWwsIGRlc3B1w6lzIHF1ZSBsYSAxcmEgZnVuY2nDs24gZGlzY3JpbWluYW50ZSBoYSBzaWRvIGRldGVybWluYWRhDQoNCmBgYHtyfQ0KcHJvcCA9IG1vZGVsX2xkYSRzdmReMi9zdW0obW9kZWxfbGRhJHN2ZF4yKQ0KcHJvcCAjdmFyaWFuemEgZW50cmUgZ3J1cG9zIGV4cGxpY2FkYSBwb3IgY2FkYSBGRA0KYGBgDQoNCmBgYHtyfQ0KbGRhLmRhdGEgPC0gY2JpbmQoZGZfdHJhaW4sIHByZWRpY3QobW9kZWxfbGRhKSR4KQ0KZ2dwbG90KGxkYS5kYXRhLCBhZXMoTEQxLCBMRDIpKSArDQogIGdlb21fcG9pbnQoYWVzKGNvbG9yID0gU3BlY2llcykpDQpgYGANCg0KVmVhbW9zIHF1ZSBwcmVkaWNlIGVsIG1vZGVsbyBlbiBkZl90ZXN0DQoNCmBgYHtyfQ0KcHJlZGljdGlvbnMgPC0gbW9kZWxfbGRhICU+JSBwcmVkaWN0KGRmX3Rlc3QpDQpwcmVkaWN0aW9ucw0KYGBgDQoNClZlYW1vcyBsYSBtYXRyaXogZGUgY29uZnVzacOzbiBlbiBkZl90cmFpbg0KDQpgYGB7cn0NCnRhYmxlKHByZWRpY3QobW9kZWxfbGRhLHR5cGU9ImNsYXNzIikkY2xhc3MsZGZfdHJhaW4kU3BlY2llcykNCmBgYA0KYHBhcnRpbWF0YCBtdWVzdHJhIHVuYSBtYXRyaXogZGUgZ3LDoWZpY29zIHBhcmEgY2FkYSBjb21iaW5hY2nDs24gZGUgZG9zIHZhcmlhYmxlcy4gQ2FkYSBncsOhZmljbyBtdWVzdHJhIHVuYSB2aXN0YSBkaWZlcmVudGUgZGUgbG9zIG1pc21vcyBkYXRvcy4gTGFzIHJlZ2lvbmVzIGNvbG9yZWFkYXMgZGVsaW1pdGFuIGNhZGEgw6FyZWEgZGUgY2xhc2lmaWNhY2nDs24uIFNlIHByZWRpY2UgcXVlIGN1YWxxdWllciBvYnNlcnZhY2nDs24gcXVlIHNlIGVuY3VlbnRyZSBkZW50cm8gZGUgdW5hIHJlZ2nDs24gcGVydGVuZWNlIGEgdW5hIGNsYXNlIGVzcGVjw61maWNhLiBDYWRhIGdyw6FmaWNvIHRhbWJpw6luIGluY2x1eWUgbGEgdGFzYSBkZSBlcnJvciBhcGFyZW50ZSBwYXJhIGVzYSB2aXN0YSBkZSBsb3MgZGF0b3MuDQoNCmBgYHtyfQ0KbGlicmFyeShrbGFSKSANCnBhcnRpbWF0IChTcGVjaWVzfi4gLCBkYXRhPWRmX3RyYWluICwgbWV0aG9kPSJsZGEiKQ0KYGBgDQoNClZlYW1vcyBsYSBfcGVyZm9ybWFuY2VfIGVuIGRmX3Rlc3QNCg0KYGBge3J9DQpsZGEudGVzdCA8LSBwcmVkaWN0KG1vZGVsX2xkYSxkZl90ZXN0KQ0KZGZfdGVzdCRsZGEgPC0gbGRhLnRlc3QkY2xhc3MNCnRhYmxlKGRmX3Rlc3QkbGRhLGRmX3Rlc3QkU3BlY2llcykNCmBgYA0KIyMjIEJpcGxvdA0KDQpgYGB7cn0NCiNpbnN0YWxsLnBhY2thZ2VzKCJkZXZ0b29scyIpDQojbGlicmFyeShkZXZ0b29scykNCiNpbnN0YWxsX2dpdGh1YigiZmF3ZGExMjMvZ2dvcmQiKQ0KbGlicmFyeShnZ29yZCkNCmdnb3JkKG1vZGVsX2xkYSwgZGZfdHJhaW4kU3BlY2llcywgeGxpbSA9IGMoLTEwLCAxMSkpDQpgYGANCg0KIyBBbsOhbGlzaXMgZGlzY3JpbWluYW50ZSBjdWFkcsOhdGljbyAoUURBKQ0KDQpFbCBkaXNjcmltaW5hbnRlIHNlIGRpY2UgY3VhZHLDoXRpY28gcG9ycXVlIGVsIHTDqXJtaW5vIGRlIHNlZ3VuZG8gb3JkZW4gbm8gc2UgY2FuY2VsYSBjb21vIGVuIGVsIGNhc28gZGVsIGRpc2NyaW1pbmFudGUgbGluZWFsLiBRREEgbm8gYXN1bWUgbGEgaWd1YWxkYWQgZW4gbGEgbWF0cml6IGRlIHZhcmlhbnphcy9jb3Zhcmlhbnphcy4gRW4gb3RyYXMgcGFsYWJyYXMsIHBhcmEgUURBIGxhIG1hdHJpeiBkZSBjb3ZhcmlhbnphIHB1ZWRlIHNlciBkaWZlcmVudGUgcGFyYSBjYWRhIGNsYXNlLg0KDQpWYW1vcyBhIGFwbGljYXIgUURBLCBhIHBlc2FyIGRlIHF1ZSBubyBzZSBzYXRpc2ZhY2UgZWwgc3VwdWVzdG8gZGUgbm9ybWFsaWRhZCBtdWx0aXZhcmlhZGEuDQoNCmBgYHtyfQ0KbW9kZWxfcWRhIDwtIHFkYShTcGVjaWVzIH4gLiwgZGZfdHJhaW4pDQptb2RlbF9xZGENCmBgYA0KDQpgYGB7cn0NCnBhcnRpbWF0KFNwZWNpZXMgfiAuLCBkYXRhPWRmX3RyYWluLCBtZXRob2Q9InFkYSIpDQpgYGANCg0KYGBge3J9DQp0YWJsZShwcmVkaWN0KG1vZGVsX3FkYSx0eXBlPSJjbGFzcyIpJGNsYXNzLGRmX3RyYWluJFNwZWNpZXMpDQpgYGANCg0KYGBge3J9DQpsZGEudGVzdF9xZGEgPC0gcHJlZGljdChtb2RlbF9xZGEsZGZfdGVzdCkNCmRmX3Rlc3QkcWRhIDwtIGxkYS50ZXN0X3FkYSRjbGFzcw0KdGFibGUoZGZfdGVzdCRxZGEsZGZfdGVzdCRTcGVjaWVzKQ0KYGBgDQojIEFsZ3Vub3MgY29tZW50YXJpb3MgDQoNCi0gRWwgw6FuYWxpc2lzIGRpc2NyaW1pbmFudGUgZXMgdW5hIHTDqWNuaWNhIHNlbnNpYmxlIGEgbGEgcHJlc2VuY2lhIGRlIF9vdXRsaWVyc18NCg0KLSBTaSBlbCBzdXB1ZXN0byBkZSBub3JtYWxpZGFkIG11bHRpdmFyaWFkYSBzZSBzb3N0aWVuZSBwZXJvIGhheSBfb3V0bGllcnNfIGVzIHJlY29tZW5kYWJsZSByZWN1cnJpciBhIGxhIHZlcnNpw7NuIHJvYnVzdGEgZGUgUURBLg0KDQotIFNpIHNlIHJlY2hhemEgbGEgbm9ybWFsaWRhZCBtdWx0aXZhcmlhZGEsIGVsIG1vZGVsbyByb2J1c3RvIG5vIGVzIGFkZWN1YWRvLg0KDQojIyDCv1F1w6kgaGFjZXIgc2kgbm8gc2UgY3VtcGxlIGVsIHN1cHVlc3RvIGRlIG5vcm1hbGlkYWQgbXVsdGl2YXJpYWRhPw0KDQpIYXkgZGl2ZXJzYXMgb3BpbmlvbmVzIGFsIHJlc3BlY3RvLiBBbGd1bm9zIG1lbmNpb25hbiBxdWUgTERBIGVzIHJvYnVzdG8gYSBsYSBmYWx0YSBkZSBub3JtYWxpZGFkIG11bHRpdmFyaWFkYSBzaSBsb3MgZGF0b3Mgc29uIGxvIHN1ZmljaWVudGVtZW50ZSBncmFuZGVzLl5bW19EaXNjcmltaW5hbnQgRnVuY3Rpb24gQW5hbHlzaXMgSW50cm9kdWN0b3J5IE92ZXJ2aWV3IC0gQXNzdW1wdGlvbnNfXShodHRwczovL2RvY3MudGliY28uY29tL2RhdGEtc2NpZW5jZS9HVUlELUIzNEUwQ0VDLUVDRUYtNENBMC1BRjU2LTdEOTFFNzY5NTM5Ny5odG1sKV0gU2luIGVtYmFyZ28sIF9MYWNoZW5icnVjaCBldCBhbC4gKDE5NzMpX15bW19Sb2J1c3RuZXNzIG9mIHRoZSBsaW5lYXIgYW5kIHF1YWRyYXRpYyBkaXNjcmltaW5hbnQgZnVuY3Rpb24gdG8gY2VydGFpbiB0eXBlcyBvZiBub24tbm9ybWFsaXR5X10oaHR0cHM6Ly9zY2ktaHViLnNlLzEwLjEwODAvMDM2MTA5MjczMDg4MjcwMDYpXSBoYW4gZGVtb3N0cmFkbyBxdWUgbG9zIHJlc3VsdGFkb3MgZGUgYXBsaWNhciBMREEgc2kgc2UgdmVuIG11eSBhZmVjdGFkb3MgcG9yIGxhIGZhbHRhIGRlIG5vcm1hbGlkYWQgbXVsdGl2YXJpYWRhIGx1ZWdvIGRlIHVzYXIgdHJlcyB0aXBvcyBkZSBkaXN0cmlidWNpb25lcyBubyBub3JtYWxlcy4gUG9yIG90cmEgcGFydGUsIHRhbWJpw6luIHNlIGhhIGVuY29udHJhZG8gcXVlIFFEQSBzaSBlcyByb2J1c3RvIGEgbGEgZmFsdGEgZGUgbm9ybWFsaWRhZCBzaSBsYXMgZGlzdHJpYnVjaW9uZXMgZGUgbG9zIGRhdG9zIHNlIGFsZWphbiBsaWdlcmFtZW50ZSBkZSBkaXN0cmlidWNpw7NuIHRlw7NyaWNhXltbX0hvdyBub24tbm9ybWFsaXR5IGFmZmVjdHMgdGhlIHF1YWRyYXRpYyBkaXNjcmltaW5hbnQgZnVuY3Rpb25fXShodHRwczovL3NjaS1odWIuc2UvMTAuMTA4MC8wMzYxMDkyNzkwODgyNzgzMCldDQoNCkFjdHVhbG1lbnRlLCBzZSBoYW4gcHJvcHVlc3RvIGFsdGVybmF0aXZhcyBubyBwYXJhbcOpdHJpY2FzIHBhcmEgbG9zIGNhc29zIGVuIHF1ZSBlbCBzdXB1ZXN0byBkZSBub3JtYWxpZGFkIG5vIHNlIGN1bXBsZS5eW1tfTm9ucGFyYW1ldHJpYyBEaXNjcmltaW5hbnQgQW5hbHlzaXNfXShodHRwczovL3NjaS1odWIuc2UvMTAuMTEwOS9UUEFNSS4xOTgzLjQ3Njc0NjEpXSBoYWNpZW5kbyB1c28gZGUgbWF0cmljZXMgZGUgZGlzcGVyc2nDs24sIHBvciBlamVtcGxvLiBBZGVtw6FzLCBfU2hhcmlwYWggU29hYWQgU3llZCBZYWhheWEgZXQgYWwuICgyMDE2KV9eW1tfUm9idXN0IExpbmVhciBEaXNjcmltaW5hbnQgQW5hbHlzaXMgX10oaHR0cHM6Ly90aGVzY2lwdWIuY29tL3BkZi9qbXNzcC4yMDE2LjMxMi4zMTYucGRmKV0gcHJvcG9uZW4gZWwgdXNvIGRlIGRvcyBlc3RpbWFkb3JlcyByb2J1c3RvIGxsYW1hZG9zIG9uZS1zdGVwIE0tZXN0aW1hdG9yIChNT00pIHkgd2luc29yaXplZCBtb2RpZmllZCBvbmUtc3RlcCBNLWVzdGltYXRvciAoV01PTSksIHF1ZSBwZXJtaXRlbiB0cmFiYWphciBjb24gYXF1ZWxsb3MgZGF0b3MgcXVlIG5vIHNvbG8gKipubyoqIHNpZ3VlbiB1bmEgZGlzdHJpYnVjacOzbiBub3JtYWwgc2lubyBxdWUgdGFtYmllbiBzb24gaGV0ZXJvY2Vkw6FzdGljb3MuDQoNCkZpbmFsbWVudGUsIHNlIHByb3BvbmUgdGFtYmnDqW4gZWwgdXNvIGRlIGFsZ29yaXRtb3MgbWFzIGNvbXBsZWpvcyBxdWUgcGVybWl0ZW4gcHJvc2VndWlyIGN1YW5kbyBubyBzZSBjdW1wbGVuIGxvcyBzdXB1ZXN0b3MgeSBubyBoYXkgbmVjZXNpZGFkIGRlIHRyYW5zZm9ybWFyIGxvcyBkYXRvcyBwYXJhIGVsbG8uIFVubyBkZSBsb3MgbW9kZWxvcyBwcm9wdWVzdG9zIGVzIGVsIHVzbyBkZSDDgXJib2xlcyBkZSBkZWNpc2nDs24gcGFyYSBjbGFzaWZpY2FjacOzbl5bW19DbGFzc2lmaWNhdGlvbiBUcmVlcyBhcyBhbiBBbHRlcm5hdGl2ZSB0byBMaW5lYXIgRGlzY3JpbWluYW50IEFuYWx5c2lzX10oaHR0cHM6Ly93d3cucmVzZWFyY2hnYXRlLm5ldC9wdWJsaWNhdGlvbi8xMTA5Mzc4NV9DbGFzc2lmaWNhdGlvbl9UcmVlc19hc19hbl9BbHRlcm5hdGl2ZV90b19MaW5lYXJfRGlzY3JpbWluYW50X0FuYWx5c2lzKV0=