Teoría

El árbol de decisión es un método de aprendizaje automático que permite tomar decisiones a partir de diferentes condiciones hasta llegar a un resultado final.

Las partes principales de un árbol son:

  • Nodo raíz: es donde inicia el árbol.
  • Ramas: representan los diferentes caminos que se pueden seguir.
  • Nodos internos: contienen las condiciones o decisiones.
  • Hojas: muestran el resultado final de cada camino.

Contexto

Se cuenta con información de 569 pacientes a los que se les realizaron diferentes mediciones relacionadas con tumores de mama.

El objetivo es crear un árbol de decisión que permita clasificar los tumores como benignos o malignos utilizando algunas características como el tamaño, la textura y la forma del tumor.

Importar la base de datos

# Importar la base de datos

cancer <- read.csv("/Users/kamilahchaidez/Downloads/cancer_de_mama.csv")

Entender la base de datos

# Resumen de las variables
summary(cancer)
##      diagnosis    radius_mean      texture_mean   perimeter_mean  
##  Length   :569   Min.   : 6.981   Min.   : 9.71   Min.   : 43.79  
##  N.unique :  2   1st Qu.:11.700   1st Qu.:16.17   1st Qu.: 75.17  
##  N.blank  :  0   Median :13.370   Median :18.84   Median : 86.24  
##  Min.nchar:  1   Mean   :14.127   Mean   :19.29   Mean   : 91.97  
##  Max.nchar:  1   3rd Qu.:15.780   3rd Qu.:21.80   3rd Qu.:104.10  
##                  Max.   :28.110   Max.   :39.28   Max.   :188.50  
##    area_mean      smoothness_mean   compactness_mean  concavity_mean   
##  Min.   : 143.5   Min.   :0.05263   Min.   :0.01938   Min.   :0.00000  
##  1st Qu.: 420.3   1st Qu.:0.08637   1st Qu.:0.06492   1st Qu.:0.02956  
##  Median : 551.1   Median :0.09587   Median :0.09263   Median :0.06154  
##  Mean   : 654.9   Mean   :0.09636   Mean   :0.10434   Mean   :0.08880  
##  3rd Qu.: 782.7   3rd Qu.:0.10530   3rd Qu.:0.13040   3rd Qu.:0.13070  
##  Max.   :2501.0   Max.   :0.16340   Max.   :0.34540   Max.   :0.42680  
##  concave.points_mean symmetry_mean    fractal_dimension_mean   radius_se     
##  Min.   :0.00000     Min.   :0.1060   Min.   :0.04996        Min.   :0.1115  
##  1st Qu.:0.02031     1st Qu.:0.1619   1st Qu.:0.05770        1st Qu.:0.2324  
##  Median :0.03350     Median :0.1792   Median :0.06154        Median :0.3242  
##  Mean   :0.04892     Mean   :0.1812   Mean   :0.06280        Mean   :0.4052  
##  3rd Qu.:0.07400     3rd Qu.:0.1957   3rd Qu.:0.06612        3rd Qu.:0.4789  
##  Max.   :0.20120     Max.   :0.3040   Max.   :0.09744        Max.   :2.8730  
##    texture_se      perimeter_se       area_se        smoothness_se     
##  Min.   :0.3602   Min.   : 0.757   Min.   :  6.802   Min.   :0.001713  
##  1st Qu.:0.8339   1st Qu.: 1.606   1st Qu.: 17.850   1st Qu.:0.005169  
##  Median :1.1080   Median : 2.287   Median : 24.530   Median :0.006380  
##  Mean   :1.2169   Mean   : 2.866   Mean   : 40.337   Mean   :0.007041  
##  3rd Qu.:1.4740   3rd Qu.: 3.357   3rd Qu.: 45.190   3rd Qu.:0.008146  
##  Max.   :4.8850   Max.   :21.980   Max.   :542.200   Max.   :0.031130  
##  compactness_se      concavity_se     concave.points_se   symmetry_se      
##  Min.   :0.002252   Min.   :0.00000   Min.   :0.000000   Min.   :0.007882  
##  1st Qu.:0.013080   1st Qu.:0.01509   1st Qu.:0.007638   1st Qu.:0.015160  
##  Median :0.020450   Median :0.02589   Median :0.010930   Median :0.018730  
##  Mean   :0.025478   Mean   :0.03189   Mean   :0.011796   Mean   :0.020542  
##  3rd Qu.:0.032450   3rd Qu.:0.04205   3rd Qu.:0.014710   3rd Qu.:0.023480  
##  Max.   :0.135400   Max.   :0.39600   Max.   :0.052790   Max.   :0.078950  
##  fractal_dimension_se  radius_worst   texture_worst   perimeter_worst 
##  Min.   :0.0008948    Min.   : 7.93   Min.   :12.02   Min.   : 50.41  
##  1st Qu.:0.0022480    1st Qu.:13.01   1st Qu.:21.08   1st Qu.: 84.11  
##  Median :0.0031870    Median :14.97   Median :25.41   Median : 97.66  
##  Mean   :0.0037949    Mean   :16.27   Mean   :25.68   Mean   :107.26  
##  3rd Qu.:0.0045580    3rd Qu.:18.79   3rd Qu.:29.72   3rd Qu.:125.40  
##  Max.   :0.0298400    Max.   :36.04   Max.   :49.54   Max.   :251.20  
##    area_worst     smoothness_worst  compactness_worst concavity_worst 
##  Min.   : 185.2   Min.   :0.07117   Min.   :0.02729   Min.   :0.0000  
##  1st Qu.: 515.3   1st Qu.:0.11660   1st Qu.:0.14720   1st Qu.:0.1145  
##  Median : 686.5   Median :0.13130   Median :0.21190   Median :0.2267  
##  Mean   : 880.6   Mean   :0.13237   Mean   :0.25427   Mean   :0.2722  
##  3rd Qu.:1084.0   3rd Qu.:0.14600   3rd Qu.:0.33910   3rd Qu.:0.3829  
##  Max.   :4254.0   Max.   :0.22260   Max.   :1.05800   Max.   :1.2520  
##  concave.points_worst symmetry_worst   fractal_dimension_worst
##  Min.   :0.00000      Min.   :0.1565   Min.   :0.05504        
##  1st Qu.:0.06493      1st Qu.:0.2504   1st Qu.:0.07146        
##  Median :0.09993      Median :0.2822   Median :0.08004        
##  Mean   :0.11461      Mean   :0.2901   Mean   :0.08395        
##  3rd Qu.:0.16140      3rd Qu.:0.3179   3rd Qu.:0.09208        
##  Max.   :0.29100      Max.   :0.6638   Max.   :0.20750
# Estructura de la base
str(cancer)
## 'data.frame':    569 obs. of  31 variables:
##  $ diagnosis              : chr  "M" "M" "M" "M" ...
##  $ radius_mean            : num  18 20.6 19.7 11.4 20.3 ...
##  $ texture_mean           : num  10.4 17.8 21.2 20.4 14.3 ...
##  $ perimeter_mean         : num  122.8 132.9 130 77.6 135.1 ...
##  $ area_mean              : num  1001 1326 1203 386 1297 ...
##  $ smoothness_mean        : num  0.1184 0.0847 0.1096 0.1425 0.1003 ...
##  $ compactness_mean       : num  0.2776 0.0786 0.1599 0.2839 0.1328 ...
##  $ concavity_mean         : num  0.3001 0.0869 0.1974 0.2414 0.198 ...
##  $ concave.points_mean    : num  0.1471 0.0702 0.1279 0.1052 0.1043 ...
##  $ symmetry_mean          : num  0.242 0.181 0.207 0.26 0.181 ...
##  $ fractal_dimension_mean : num  0.0787 0.0567 0.06 0.0974 0.0588 ...
##  $ radius_se              : num  1.095 0.543 0.746 0.496 0.757 ...
##  $ texture_se             : num  0.905 0.734 0.787 1.156 0.781 ...
##  $ perimeter_se           : num  8.59 3.4 4.58 3.44 5.44 ...
##  $ area_se                : num  153.4 74.1 94 27.2 94.4 ...
##  $ smoothness_se          : num  0.0064 0.00522 0.00615 0.00911 0.01149 ...
##  $ compactness_se         : num  0.049 0.0131 0.0401 0.0746 0.0246 ...
##  $ concavity_se           : num  0.0537 0.0186 0.0383 0.0566 0.0569 ...
##  $ concave.points_se      : num  0.0159 0.0134 0.0206 0.0187 0.0188 ...
##  $ symmetry_se            : num  0.03 0.0139 0.0225 0.0596 0.0176 ...
##  $ fractal_dimension_se   : num  0.00619 0.00353 0.00457 0.00921 0.00511 ...
##  $ radius_worst           : num  25.4 25 23.6 14.9 22.5 ...
##  $ texture_worst          : num  17.3 23.4 25.5 26.5 16.7 ...
##  $ perimeter_worst        : num  184.6 158.8 152.5 98.9 152.2 ...
##  $ area_worst             : num  2019 1956 1709 568 1575 ...
##  $ smoothness_worst       : num  0.162 0.124 0.144 0.21 0.137 ...
##  $ compactness_worst      : num  0.666 0.187 0.424 0.866 0.205 ...
##  $ concavity_worst        : num  0.712 0.242 0.45 0.687 0.4 ...
##  $ concave.points_worst   : num  0.265 0.186 0.243 0.258 0.163 ...
##  $ symmetry_worst         : num  0.46 0.275 0.361 0.664 0.236 ...
##  $ fractal_dimension_worst: num  0.1189 0.089 0.0876 0.173 0.0768 ...
# Primeras filas
head(cancer)
##   diagnosis radius_mean texture_mean perimeter_mean area_mean smoothness_mean
## 1         M       17.99        10.38         122.80    1001.0         0.11840
## 2         M       20.57        17.77         132.90    1326.0         0.08474
## 3         M       19.69        21.25         130.00    1203.0         0.10960
## 4         M       11.42        20.38          77.58     386.1         0.14250
## 5         M       20.29        14.34         135.10    1297.0         0.10030
## 6         M       12.45        15.70          82.57     477.1         0.12780
##   compactness_mean concavity_mean concave.points_mean symmetry_mean
## 1          0.27760         0.3001             0.14710        0.2419
## 2          0.07864         0.0869             0.07017        0.1812
## 3          0.15990         0.1974             0.12790        0.2069
## 4          0.28390         0.2414             0.10520        0.2597
## 5          0.13280         0.1980             0.10430        0.1809
## 6          0.17000         0.1578             0.08089        0.2087
##   fractal_dimension_mean radius_se texture_se perimeter_se area_se
## 1                0.07871    1.0950     0.9053        8.589  153.40
## 2                0.05667    0.5435     0.7339        3.398   74.08
## 3                0.05999    0.7456     0.7869        4.585   94.03
## 4                0.09744    0.4956     1.1560        3.445   27.23
## 5                0.05883    0.7572     0.7813        5.438   94.44
## 6                0.07613    0.3345     0.8902        2.217   27.19
##   smoothness_se compactness_se concavity_se concave.points_se symmetry_se
## 1      0.006399        0.04904      0.05373           0.01587     0.03003
## 2      0.005225        0.01308      0.01860           0.01340     0.01389
## 3      0.006150        0.04006      0.03832           0.02058     0.02250
## 4      0.009110        0.07458      0.05661           0.01867     0.05963
## 5      0.011490        0.02461      0.05688           0.01885     0.01756
## 6      0.007510        0.03345      0.03672           0.01137     0.02165
##   fractal_dimension_se radius_worst texture_worst perimeter_worst area_worst
## 1             0.006193        25.38         17.33          184.60     2019.0
## 2             0.003532        24.99         23.41          158.80     1956.0
## 3             0.004571        23.57         25.53          152.50     1709.0
## 4             0.009208        14.91         26.50           98.87      567.7
## 5             0.005115        22.54         16.67          152.20     1575.0
## 6             0.005082        15.47         23.75          103.40      741.6
##   smoothness_worst compactness_worst concavity_worst concave.points_worst
## 1           0.1622            0.6656          0.7119               0.2654
## 2           0.1238            0.1866          0.2416               0.1860
## 3           0.1444            0.4245          0.4504               0.2430
## 4           0.2098            0.8663          0.6869               0.2575
## 5           0.1374            0.2050          0.4000               0.1625
## 6           0.1791            0.5249          0.5355               0.1741
##   symmetry_worst fractal_dimension_worst
## 1         0.4601                 0.11890
## 2         0.2750                 0.08902
## 3         0.3613                 0.08758
## 4         0.6638                 0.17300
## 5         0.2364                 0.07678
## 6         0.3985                 0.12440

La base contiene 569 pacientes y diferentes características relacionadas con los tumores.

La variable que queremos predecir es diagnosis, donde:

  • B significa Benigno.
  • M significa Maligno.

Las demás columnas contienen diferentes mediciones realizadas sobre los tumores.

Filtrar la base de datos

# Seleccionar solamente las variables que se utilizarán en el árbol

Cancer <- cancer[, c(
  "radius_worst",
  "texture_worst",
  "concave.points_worst",
  "diagnosis"
)]

# Cambiar B y M por palabras más fáciles de interpretar

Cancer$diagnosis <- as.factor(
  ifelse(
    Cancer$diagnosis == "B",
    "Benigno",
    "Maligno"
  )
)

# Revisar estructura
str(Cancer)
## 'data.frame':    569 obs. of  4 variables:
##  $ radius_worst        : num  25.4 25 23.6 14.9 22.5 ...
##  $ texture_worst       : num  17.3 23.4 25.5 26.5 16.7 ...
##  $ concave.points_worst: num  0.265 0.186 0.243 0.258 0.163 ...
##  $ diagnosis           : Factor w/ 2 levels "Benigno","Maligno": 2 2 2 2 2 2 2 2 2 2 ...
# Revisar valores faltantes
sum(is.na(Cancer))
## [1] 0
sapply(
  Cancer,
  function(x) sum(is.na(x))
)
##         radius_worst        texture_worst concave.points_worst 
##                    0                    0                    0 
##            diagnosis 
##                    0
# Eliminar datos faltantes si existen
Cancer <- na.omit(Cancer)

Las tres características que se utilizarán son:

  • radius_worst: representa el tamaño del tumor.
  • texture_worst: representa la textura del tumor.
  • concave.points_worst: representa qué tan irregular es el borde del tumor.

La base no presenta valores faltantes en estas variables, pero se utiliza na.omit() para asegurar que el modelo trabaje únicamente con información completa.

Crear árbol de decisión

library(rpart)

# Crear el árbol
arbol <- rpart(
  formula = diagnosis ~ .,
  data = Cancer
)

arbol
## n= 569 
## 
## node), split, n, loss, yval, (yprob)
##       * denotes terminal node
## 
##  1) root 569 212 Benigno (0.62741652 0.37258348)  
##    2) radius_worst< 16.795 379  33 Benigno (0.91292876 0.08707124)  
##      4) concave.points_worst< 0.1358 333   5 Benigno (0.98498498 0.01501502) *
##      5) concave.points_worst>=0.1358 46  18 Maligno (0.39130435 0.60869565)  
##       10) texture_worst< 25.67 19   4 Benigno (0.78947368 0.21052632) *
##       11) texture_worst>=25.67 27   3 Maligno (0.11111111 0.88888889) *
##    3) radius_worst>=16.795 190  11 Maligno (0.05789474 0.94210526) *

Graficar árbol de decisión

library(rpart.plot)

# Gráfica del árbol
rpart.plot(arbol)

# Árbol mostrando información adicional
prp(
  arbol,
  extra = 7,
  prefix = "fraccion "
)

Para interpretar el árbol se comienza desde la parte superior. Cada nodo contiene una condición y dependiendo de si se cumple o no, se sigue una rama diferente hasta llegar a una hoja que muestra la clasificación final.

Probar el modelo

# Realizar predicciones con el árbol

prediccion <- predict(
  arbol,
  Cancer,
  type = "class"
)

# Comparar resultados reales contra las predicciones

matriz <- table(
  Real = Cancer$diagnosis,
  Prediccion = prediccion
)

matriz
##          Prediccion
## Real      Benigno Maligno
##   Benigno     343      14
##   Maligno       9     203

Exactitud del modelo

# Calcular la exactitud

exactitud <- sum(
  diag(matriz)
) / sum(matriz)

exactitud
## [1] 0.9595782

El árbol logra clasificar correctamente aproximadamente el 96% de los casos utilizando solamente tres características del tumor.

Sin embargo, aunque el porcentaje de aciertos es alto, el modelo también puede cometer errores.

En este caso es especialmente importante evitar clasificar un tumor maligno como benigno, ya que podría representar un riesgo para el paciente.

Por esta razón, el árbol puede utilizarse como una herramienta de apoyo, pero no debe sustituir la evaluación de un profesional médico.

Conclusiones

  1. El árbol de decisión permite clasificar los tumores como benignos o malignos utilizando solamente tres características.

  2. Una de las variables más importantes para realizar la clasificación es radius_worst, relacionada con el tamaño del tumor.

  3. Los tumores de mayor tamaño y con bordes más irregulares presentan una mayor tendencia a ser clasificados como malignos.

  4. Los tumores de menor tamaño y con bordes menos irregulares presentan una mayor tendencia a ser clasificados como benignos.

  5. El modelo obtiene aproximadamente un 96% de exactitud, lo que indica que estas tres variables contienen una cantidad importante de información para distinguir entre ambos tipos de tumor.

  6. Aunque el modelo presenta buenos resultados, debe considerarse únicamente como una herramienta de apoyo y no como un método definitivo de diagnóstico.

LS0tCnRpdGxlOiAiw4FyYm9sIGRlIGRlY2lzacOzbiAtIEPDoW5jZXIgZGUgbWFtYSIKYXV0aG9yOiAiS2FtaWxhaCBDaGFpZGV6IC0gQTAxNzQxOTQzIgpkYXRlOiAiMjAyNi0wOC0yMCIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICB0b2M6IHRydWUKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgY29kZV9kb3dubG9hZDogdHJ1ZQogICAgdGhlbWU6IGNvc21vCi0tLQoKIVtdKGh0dHBzOi8vbWVkaWExLmdpcGh5LmNvbS9tZWRpYS92MS5ZMmxrUFRaak1EbGlPVFV5ZVRBMmRqQXljM2xrYVdnNWJIY3lZbkJ5WkRSaFpuQnZiek5sTjI0d01YRmpPSFpzZW1oak5pWmxjRDEyTVY5bmFXWnpYM05sWVhKamFDWmpkRDFuL2IzTGZtWHNwZUd3Q1NmSmgyRC8yMDB3LmdpZikKCiMgPHNwYW4gc3R5bGU9ImNvbG9yOmRhcmsiPlRlb3LDrWE8L3NwYW4+CgpFbCAqKsOhcmJvbCBkZSBkZWNpc2nDs24qKiBlcyB1biBtw6l0b2RvIGRlIGFwcmVuZGl6YWplIGF1dG9tw6F0aWNvIHF1ZSBwZXJtaXRlIHRvbWFyIGRlY2lzaW9uZXMgYSBwYXJ0aXIgZGUgZGlmZXJlbnRlcyBjb25kaWNpb25lcyBoYXN0YSBsbGVnYXIgYSB1biByZXN1bHRhZG8gZmluYWwuCgpMYXMgcGFydGVzIHByaW5jaXBhbGVzIGRlIHVuIMOhcmJvbCBzb246CgoqICoqTm9kbyByYcOtejoqKiBlcyBkb25kZSBpbmljaWEgZWwgw6FyYm9sLgoqICoqUmFtYXM6KiogcmVwcmVzZW50YW4gbG9zIGRpZmVyZW50ZXMgY2FtaW5vcyBxdWUgc2UgcHVlZGVuIHNlZ3Vpci4KKiAqKk5vZG9zIGludGVybm9zOioqIGNvbnRpZW5lbiBsYXMgY29uZGljaW9uZXMgbyBkZWNpc2lvbmVzLgoqICoqSG9qYXM6KiogbXVlc3RyYW4gZWwgcmVzdWx0YWRvIGZpbmFsIGRlIGNhZGEgY2FtaW5vLgoKIyA8c3BhbiBzdHlsZT0iY29sb3I6ZGFyayI+Q29udGV4dG88L3NwYW4+CgpTZSBjdWVudGEgY29uIGluZm9ybWFjacOzbiBkZSAqKjU2OSBwYWNpZW50ZXMqKiBhIGxvcyBxdWUgc2UgbGVzIHJlYWxpemFyb24gZGlmZXJlbnRlcyBtZWRpY2lvbmVzIHJlbGFjaW9uYWRhcyBjb24gdHVtb3JlcyBkZSBtYW1hLgoKRWwgb2JqZXRpdm8gZXMgY3JlYXIgdW4gKirDoXJib2wgZGUgZGVjaXNpw7NuKiogcXVlIHBlcm1pdGEgY2xhc2lmaWNhciBsb3MgdHVtb3JlcyBjb21vICoqYmVuaWdub3MqKiBvICoqbWFsaWdub3MqKiB1dGlsaXphbmRvIGFsZ3VuYXMgY2FyYWN0ZXLDrXN0aWNhcyBjb21vIGVsIHRhbWHDsW8sIGxhIHRleHR1cmEgeSBsYSBmb3JtYSBkZWwgdHVtb3IuCgojIDxzcGFuIHN0eWxlPSJjb2xvcjpkYXJrIj5JbXBvcnRhciBsYSBiYXNlIGRlIGRhdG9zPC9zcGFuPgoKYGBge3J9CiMgSW1wb3J0YXIgbGEgYmFzZSBkZSBkYXRvcwoKY2FuY2VyIDwtIHJlYWQuY3N2KCIvVXNlcnMva2FtaWxhaGNoYWlkZXovRG93bmxvYWRzL2NhbmNlcl9kZV9tYW1hLmNzdiIpCmBgYAoKIyA8c3BhbiBzdHlsZT0iY29sb3I6ZGFyayI+RW50ZW5kZXIgbGEgYmFzZSBkZSBkYXRvczwvc3Bhbj4KCmBgYHtyfQojIFJlc3VtZW4gZGUgbGFzIHZhcmlhYmxlcwpzdW1tYXJ5KGNhbmNlcikKCiMgRXN0cnVjdHVyYSBkZSBsYSBiYXNlCnN0cihjYW5jZXIpCgojIFByaW1lcmFzIGZpbGFzCmhlYWQoY2FuY2VyKQpgYGAKCkxhIGJhc2UgY29udGllbmUgKio1NjkgcGFjaWVudGVzKiogeSBkaWZlcmVudGVzIGNhcmFjdGVyw61zdGljYXMgcmVsYWNpb25hZGFzIGNvbiBsb3MgdHVtb3Jlcy4KCkxhIHZhcmlhYmxlIHF1ZSBxdWVyZW1vcyBwcmVkZWNpciBlcyBgZGlhZ25vc2lzYCwgZG9uZGU6CgoqICoqQioqIHNpZ25pZmljYSBCZW5pZ25vLgoqICoqTSoqIHNpZ25pZmljYSBNYWxpZ25vLgoKTGFzIGRlbcOhcyBjb2x1bW5hcyBjb250aWVuZW4gZGlmZXJlbnRlcyBtZWRpY2lvbmVzIHJlYWxpemFkYXMgc29icmUgbG9zIHR1bW9yZXMuCgojIDxzcGFuIHN0eWxlPSJjb2xvcjpkYXJrIj5GaWx0cmFyIGxhIGJhc2UgZGUgZGF0b3M8L3NwYW4+CgpgYGB7cn0KIyBTZWxlY2Npb25hciBzb2xhbWVudGUgbGFzIHZhcmlhYmxlcyBxdWUgc2UgdXRpbGl6YXLDoW4gZW4gZWwgw6FyYm9sCgpDYW5jZXIgPC0gY2FuY2VyWywgYygKICAicmFkaXVzX3dvcnN0IiwKICAidGV4dHVyZV93b3JzdCIsCiAgImNvbmNhdmUucG9pbnRzX3dvcnN0IiwKICAiZGlhZ25vc2lzIgopXQoKIyBDYW1iaWFyIEIgeSBNIHBvciBwYWxhYnJhcyBtw6FzIGbDoWNpbGVzIGRlIGludGVycHJldGFyCgpDYW5jZXIkZGlhZ25vc2lzIDwtIGFzLmZhY3RvcigKICBpZmVsc2UoCiAgICBDYW5jZXIkZGlhZ25vc2lzID09ICJCIiwKICAgICJCZW5pZ25vIiwKICAgICJNYWxpZ25vIgogICkKKQoKIyBSZXZpc2FyIGVzdHJ1Y3R1cmEKc3RyKENhbmNlcikKCiMgUmV2aXNhciB2YWxvcmVzIGZhbHRhbnRlcwpzdW0oaXMubmEoQ2FuY2VyKSkKCnNhcHBseSgKICBDYW5jZXIsCiAgZnVuY3Rpb24oeCkgc3VtKGlzLm5hKHgpKQopCgojIEVsaW1pbmFyIGRhdG9zIGZhbHRhbnRlcyBzaSBleGlzdGVuCkNhbmNlciA8LSBuYS5vbWl0KENhbmNlcikKYGBgCgpMYXMgdHJlcyBjYXJhY3RlcsOtc3RpY2FzIHF1ZSBzZSB1dGlsaXphcsOhbiBzb246CgoqIGByYWRpdXNfd29yc3RgOiByZXByZXNlbnRhIGVsIHRhbWHDsW8gZGVsIHR1bW9yLgoqIGB0ZXh0dXJlX3dvcnN0YDogcmVwcmVzZW50YSBsYSB0ZXh0dXJhIGRlbCB0dW1vci4KKiBgY29uY2F2ZS5wb2ludHNfd29yc3RgOiByZXByZXNlbnRhIHF1w6kgdGFuIGlycmVndWxhciBlcyBlbCBib3JkZSBkZWwgdHVtb3IuCgpMYSBiYXNlIG5vIHByZXNlbnRhIHZhbG9yZXMgZmFsdGFudGVzIGVuIGVzdGFzIHZhcmlhYmxlcywgcGVybyBzZSB1dGlsaXphIGBuYS5vbWl0KClgIHBhcmEgYXNlZ3VyYXIgcXVlIGVsIG1vZGVsbyB0cmFiYWplIMO6bmljYW1lbnRlIGNvbiBpbmZvcm1hY2nDs24gY29tcGxldGEuCgojIDxzcGFuIHN0eWxlPSJjb2xvcjpkYXJrIj5DcmVhciDDoXJib2wgZGUgZGVjaXNpw7NuPC9zcGFuPgoKYGBge3IsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CgpsaWJyYXJ5KHJwYXJ0KQoKIyBDcmVhciBlbCDDoXJib2wKYXJib2wgPC0gcnBhcnQoCiAgZm9ybXVsYSA9IGRpYWdub3NpcyB+IC4sCiAgZGF0YSA9IENhbmNlcgopCgphcmJvbApgYGAKCiMgPHNwYW4gc3R5bGU9ImNvbG9yOmRhcmsiPkdyYWZpY2FyIMOhcmJvbCBkZSBkZWNpc2nDs248L3NwYW4+CgpgYGB7ciwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KCmxpYnJhcnkocnBhcnQucGxvdCkKCiMgR3LDoWZpY2EgZGVsIMOhcmJvbApycGFydC5wbG90KGFyYm9sKQoKIyDDgXJib2wgbW9zdHJhbmRvIGluZm9ybWFjacOzbiBhZGljaW9uYWwKcHJwKAogIGFyYm9sLAogIGV4dHJhID0gNywKICBwcmVmaXggPSAiZnJhY2Npb24gIgopCmBgYAoKUGFyYSBpbnRlcnByZXRhciBlbCDDoXJib2wgc2UgY29taWVuemEgZGVzZGUgbGEgcGFydGUgc3VwZXJpb3IuIENhZGEgbm9kbyBjb250aWVuZSB1bmEgY29uZGljacOzbiB5IGRlcGVuZGllbmRvIGRlIHNpIHNlIGN1bXBsZSBvIG5vLCBzZSBzaWd1ZSB1bmEgcmFtYSBkaWZlcmVudGUgaGFzdGEgbGxlZ2FyIGEgdW5hIGhvamEgcXVlIG11ZXN0cmEgbGEgY2xhc2lmaWNhY2nDs24gZmluYWwuCgojIDxzcGFuIHN0eWxlPSJjb2xvcjpkYXJrIj5Qcm9iYXIgZWwgbW9kZWxvPC9zcGFuPgoKYGBge3J9CiMgUmVhbGl6YXIgcHJlZGljY2lvbmVzIGNvbiBlbCDDoXJib2wKCnByZWRpY2Npb24gPC0gcHJlZGljdCgKICBhcmJvbCwKICBDYW5jZXIsCiAgdHlwZSA9ICJjbGFzcyIKKQoKIyBDb21wYXJhciByZXN1bHRhZG9zIHJlYWxlcyBjb250cmEgbGFzIHByZWRpY2Npb25lcwoKbWF0cml6IDwtIHRhYmxlKAogIFJlYWwgPSBDYW5jZXIkZGlhZ25vc2lzLAogIFByZWRpY2Npb24gPSBwcmVkaWNjaW9uCikKCm1hdHJpegpgYGAKCiMgPHNwYW4gc3R5bGU9ImNvbG9yOmRhcmsiPkV4YWN0aXR1ZCBkZWwgbW9kZWxvPC9zcGFuPgoKYGBge3J9CiMgQ2FsY3VsYXIgbGEgZXhhY3RpdHVkCgpleGFjdGl0dWQgPC0gc3VtKAogIGRpYWcobWF0cml6KQopIC8gc3VtKG1hdHJpeikKCmV4YWN0aXR1ZApgYGAKCkVsIMOhcmJvbCBsb2dyYSBjbGFzaWZpY2FyIGNvcnJlY3RhbWVudGUgYXByb3hpbWFkYW1lbnRlIGVsICoqOTYlIGRlIGxvcyBjYXNvcyoqIHV0aWxpemFuZG8gc29sYW1lbnRlIHRyZXMgY2FyYWN0ZXLDrXN0aWNhcyBkZWwgdHVtb3IuCgpTaW4gZW1iYXJnbywgYXVucXVlIGVsIHBvcmNlbnRhamUgZGUgYWNpZXJ0b3MgZXMgYWx0bywgZWwgbW9kZWxvIHRhbWJpw6luIHB1ZWRlIGNvbWV0ZXIgZXJyb3Jlcy4KCkVuIGVzdGUgY2FzbyBlcyBlc3BlY2lhbG1lbnRlIGltcG9ydGFudGUgZXZpdGFyIGNsYXNpZmljYXIgdW4gdHVtb3IgbWFsaWdubyBjb21vIGJlbmlnbm8sIHlhIHF1ZSBwb2Ryw61hIHJlcHJlc2VudGFyIHVuIHJpZXNnbyBwYXJhIGVsIHBhY2llbnRlLgoKUG9yIGVzdGEgcmF6w7NuLCBlbCDDoXJib2wgcHVlZGUgdXRpbGl6YXJzZSBjb21vIHVuYSAqKmhlcnJhbWllbnRhIGRlIGFwb3lvKiosIHBlcm8gbm8gZGViZSBzdXN0aXR1aXIgbGEgZXZhbHVhY2nDs24gZGUgdW4gcHJvZmVzaW9uYWwgbcOpZGljby4KCiMgPHNwYW4gc3R5bGU9ImNvbG9yOmRhcmsiPkNvbmNsdXNpb25lczwvc3Bhbj4KCjEuIEVsIMOhcmJvbCBkZSBkZWNpc2nDs24gcGVybWl0ZSBjbGFzaWZpY2FyIGxvcyB0dW1vcmVzIGNvbW8gKipiZW5pZ25vcyBvIG1hbGlnbm9zKiogdXRpbGl6YW5kbyBzb2xhbWVudGUgdHJlcyBjYXJhY3RlcsOtc3RpY2FzLgoKMi4gVW5hIGRlIGxhcyB2YXJpYWJsZXMgbcOhcyBpbXBvcnRhbnRlcyBwYXJhIHJlYWxpemFyIGxhIGNsYXNpZmljYWNpw7NuIGVzIGByYWRpdXNfd29yc3RgLCByZWxhY2lvbmFkYSBjb24gZWwgdGFtYcOxbyBkZWwgdHVtb3IuCgozLiBMb3MgdHVtb3JlcyBkZSBtYXlvciB0YW1hw7FvIHkgY29uIGJvcmRlcyBtw6FzIGlycmVndWxhcmVzIHByZXNlbnRhbiB1bmEgbWF5b3IgdGVuZGVuY2lhIGEgc2VyIGNsYXNpZmljYWRvcyBjb21vICoqbWFsaWdub3MqKi4KCjQuIExvcyB0dW1vcmVzIGRlIG1lbm9yIHRhbWHDsW8geSBjb24gYm9yZGVzIG1lbm9zIGlycmVndWxhcmVzIHByZXNlbnRhbiB1bmEgbWF5b3IgdGVuZGVuY2lhIGEgc2VyIGNsYXNpZmljYWRvcyBjb21vICoqYmVuaWdub3MqKi4KCjUuIEVsIG1vZGVsbyBvYnRpZW5lIGFwcm94aW1hZGFtZW50ZSB1biAqKjk2JSBkZSBleGFjdGl0dWQqKiwgbG8gcXVlIGluZGljYSBxdWUgZXN0YXMgdHJlcyB2YXJpYWJsZXMgY29udGllbmVuIHVuYSBjYW50aWRhZCBpbXBvcnRhbnRlIGRlIGluZm9ybWFjacOzbiBwYXJhIGRpc3Rpbmd1aXIgZW50cmUgYW1ib3MgdGlwb3MgZGUgdHVtb3IuCgo2LiBBdW5xdWUgZWwgbW9kZWxvIHByZXNlbnRhIGJ1ZW5vcyByZXN1bHRhZG9zLCBkZWJlIGNvbnNpZGVyYXJzZSDDum5pY2FtZW50ZSBjb21vIHVuYSBoZXJyYW1pZW50YSBkZSBhcG95byB5IG5vIGNvbW8gdW4gbcOpdG9kbyBkZWZpbml0aXZvIGRlIGRpYWduw7NzdGljby4=