Chapter 3: Classification using Nearest Neighbors

Example: Classifying Cancer Samples

Step 2: Exploring and preparing the data

# import the CSV file
wbcd <- read.csv("wisc_bc_data.csv", stringsAsFactors = FALSE)

# examine the structure of the wbcd data frame
str(wbcd)
'data.frame':   569 obs. of  32 variables:
 $ id               : int  87139402 8910251 905520 868871 9012568 906539 925291 87880 862989 89827 ...
 $ diagnosis        : chr  "B" "B" "B" "B" ...
 $ radius_mean      : num  12.3 10.6 11 11.3 15.2 ...
 $ texture_mean     : num  12.4 18.9 16.8 13.4 13.2 ...
 $ perimeter_mean   : num  78.8 69.3 70.9 73 97.7 ...
 $ area_mean        : num  464 346 373 385 712 ...
 $ smoothness_mean  : num  0.1028 0.0969 0.1077 0.1164 0.0796 ...
 $ compactness_mean : num  0.0698 0.1147 0.078 0.1136 0.0693 ...
 $ concavity_mean   : num  0.0399 0.0639 0.0305 0.0464 0.0339 ...
 $ points_mean      : num  0.037 0.0264 0.0248 0.048 0.0266 ...
 $ symmetry_mean    : num  0.196 0.192 0.171 0.177 0.172 ...
 $ dimension_mean   : num  0.0595 0.0649 0.0634 0.0607 0.0554 ...
 $ radius_se        : num  0.236 0.451 0.197 0.338 0.178 ...
 $ texture_se       : num  0.666 1.197 1.387 1.343 0.412 ...
 $ perimeter_se     : num  1.67 3.43 1.34 1.85 1.34 ...
 $ area_se          : num  17.4 27.1 13.5 26.3 17.7 ...
 $ smoothness_se    : num  0.00805 0.00747 0.00516 0.01127 0.00501 ...
 $ compactness_se   : num  0.0118 0.03581 0.00936 0.03498 0.01485 ...
 $ concavity_se     : num  0.0168 0.0335 0.0106 0.0219 0.0155 ...
 $ points_se        : num  0.01241 0.01365 0.00748 0.01965 0.00915 ...
 $ symmetry_se      : num  0.0192 0.035 0.0172 0.0158 0.0165 ...
 $ dimension_se     : num  0.00225 0.00332 0.0022 0.00344 0.00177 ...
 $ radius_worst     : num  13.5 11.9 12.4 11.9 16.2 ...
 $ texture_worst    : num  15.6 22.9 26.4 15.8 15.7 ...
 $ perimeter_worst  : num  87 78.3 79.9 76.5 104.5 ...
 $ area_worst       : num  549 425 471 434 819 ...
 $ smoothness_worst : num  0.139 0.121 0.137 0.137 0.113 ...
 $ compactness_worst: num  0.127 0.252 0.148 0.182 0.174 ...
 $ concavity_worst  : num  0.1242 0.1916 0.1067 0.0867 0.1362 ...
 $ points_worst     : num  0.0939 0.0793 0.0743 0.0861 0.0818 ...
 $ symmetry_worst   : num  0.283 0.294 0.3 0.21 0.249 ...
 $ dimension_worst  : num  0.0677 0.0759 0.0788 0.0678 0.0677 ...

#The str function is then used to inspect the structure of the wbcd data frame, which provides information about the data types and structure of each variable in the data frame. This helps in understanding the overall composition of the dataset.

# drop the id feature
wbcd <- wbcd[-1]

#the wbcd data frame will no longer contain the column with the “id” feature, effectively removing it from the dataset.


# table of diagnosis
table(wbcd$diagnosis)
< table of extent 0 >
# recode diagnosis as a factor
wbcd$diagnosis <- factor(wbcd$diagnosis, levels = c("B", "M"),
                         labels = c("Benign", "Malignant"))

#This code uses the factor function to convert the “diagnosis” variable into a factor variable with specified levels and corresponding labels. The levels parameter specifies the unique values to be used, and the labels parameter provides the corresponding labels for those levels.

# table or proportions with more informative labels
round(prop.table(table(wbcd$diagnosis)) * 100, digits = 1)

   Benign Malignant 
     62.7      37.3 

#This code calculates the proportions of each unique value in the “diagnosis” variable, and then multiplies the result by 100 to express the proportions as percentages.

# summarize three numeric features
summary(wbcd[c("radius_mean", "area_mean", "smoothness_mean")])
  radius_mean       area_mean      smoothness_mean  
 Min.   : 6.981   Min.   : 143.5   Min.   :0.05263  
 1st Qu.:11.700   1st Qu.: 420.3   1st Qu.:0.08637  
 Median :13.370   Median : 551.1   Median :0.09587  
 Mean   :14.127   Mean   : 654.9   Mean   :0.09636  
 3rd Qu.:15.780   3rd Qu.: 782.7   3rd Qu.:0.10530  
 Max.   :28.110   Max.   :2501.0   Max.   :0.16340  

#This code selects the specified numeric columns from the wbcd data frame and then uses the summary function to generate summary statistics for each of these features.

# create normalization function
normalize <- function(x) {
  return ((x - min(x)) / (max(x) - min(x)))
}
# test normalization function - result should be identical
normalize(c(1, 2, 3, 4, 5))
[1] 0.00 0.25 0.50 0.75 1.00
normalize(c(10, 20, 30, 40, 50))
[1] 0.00 0.25 0.50 0.75 1.00
# normalize the wbcd data
wbcd_n <- as.data.frame(lapply(wbcd[2:31], normalize))
# confirm that normalization worked
summary(wbcd_n$area_mean)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
 0.0000  0.1174  0.1729  0.2169  0.2711  1.0000 

#The lapply function is used to apply the normalize function to each numeric column in the specified range (columns 2 through 31) of the original wbcd data frame. The result is stored in a new data frame called wbcd_n. Finally, the summary function is used to check the summary statistics for the “area_mean” feature in the normalized data (wbcd_n). This step is a way to confirm that the normalization process was successful for one of the features.

# create training and test data
wbcd_train <- wbcd_n[1:469, ]
wbcd_test <- wbcd_n[470:569, ]
# create labels for training and test data

wbcd_train_labels <- wbcd[1:469, 1]
wbcd_test_labels <- wbcd[470:569, 1]

Step 3: Training a model on the data

# load the "class" library
library(class)
wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test,
                      cl = wbcd_train_labels, k = 21)

#In this code, the knn function from the “class” library is utilized for kNN classification. The train argument specifies the training data, the test argument specifies the test data, the cl argument specifies the class labels for the training data, and k is set to 21, indicating that the algorithm considers the 21 nearest neighbors when making predictions

Step 4: Evaluating model performance

# load the "gmodels" library
library(gmodels)
Warning: package ‘gmodels’ was built under R version 4.3.2
# Create the cross tabulation of predicted vs. actual
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred,
           prop.chisq = FALSE)

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.968 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         2 |        37 |        39 | 
                 |     0.051 |     0.949 |     0.390 | 
                 |     0.032 |     1.000 |           | 
                 |     0.020 |     0.370 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        63 |        37 |       100 | 
                 |     0.630 |     0.370 |           | 
-----------------|-----------|-----------|-----------|

 
## Step 5: Improving model performance

# use the scale() function to z-score standardize a data frame
wbcd_z <- as.data.frame(scale(wbcd[-1]))

# confirm that the transformation was applied correctly
summary(wbcd_z$area_mean)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
-1.4532 -0.6666 -0.2949  0.0000  0.3632  5.2459 

#The scale function is applied to the numeric columns in the wbcd data frame, excluding the first column (id). The result is stored in a new data frame called wbcd_z. The summary function is then used to check the summary statistics for the “area_mean” feature in the standardized data (wbcd_z). This step is a way to confirm that the z-score standardization process was successful for one of the features.

# create training and test datasets
wbcd_train <- wbcd_z[1:469, ]
wbcd_test <- wbcd_z[470:569, ]

# re-classify test cases
wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test,
                      cl = wbcd_train_labels, k = 21)

#This code splits the z-score standardized data into training and test sets. The first 469 rows are used for training, and the remaining rows (470:569) are used for testing. The kNN algorithm is then applied to reclassify the test cases using the training set and associated labels.

# Create the cross tabulation of predicted vs. actual
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred,
           prop.chisq = FALSE)

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.924 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         5 |        34 |        39 | 
                 |     0.128 |     0.872 |     0.390 | 
                 |     0.076 |     1.000 |           | 
                 |     0.050 |     0.340 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        66 |        34 |       100 | 
                 |     0.660 |     0.340 |           | 
-----------------|-----------|-----------|-----------|

 
# try several different values of k
wbcd_train <- wbcd_n[1:469, ]
wbcd_test <- wbcd_n[470:569, ]
#K=1
wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=1)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        58 |         3 |        61 | 
                 |     0.951 |     0.049 |     0.610 | 
                 |     0.983 |     0.073 |           | 
                 |     0.580 |     0.030 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         1 |        38 |        39 | 
                 |     0.026 |     0.974 |     0.390 | 
                 |     0.017 |     0.927 |           | 
                 |     0.010 |     0.380 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        59 |        41 |       100 | 
                 |     0.590 |     0.410 |           | 
-----------------|-----------|-----------|-----------|

 
#k=5
wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=5)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.968 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         2 |        37 |        39 | 
                 |     0.051 |     0.949 |     0.390 | 
                 |     0.032 |     1.000 |           | 
                 |     0.020 |     0.370 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        63 |        37 |       100 | 
                 |     0.630 |     0.370 |           | 
-----------------|-----------|-----------|-----------|

 
wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=11)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.953 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         3 |        36 |        39 | 
                 |     0.077 |     0.923 |     0.390 | 
                 |     0.047 |     1.000 |           | 
                 |     0.030 |     0.360 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        64 |        36 |       100 | 
                 |     0.640 |     0.360 |           | 
-----------------|-----------|-----------|-----------|

 

#This code uses the kNN algorithm with k=1 to classify the test set (wbcd_test). The CrossTable function then creates a contingency table to evaluate the classification results by comparing the true labels (wbcd_test_labels) with the predicted labels (wbcd_test_pred). The prop.chisq = FALSE argument indicates that the table should not include column percentages. This contingency table helps assess the performance of the kNN classification for k=1 on the test set.

wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=15)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.953 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         3 |        36 |        39 | 
                 |     0.077 |     0.923 |     0.390 | 
                 |     0.047 |     1.000 |           | 
                 |     0.030 |     0.360 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        64 |        36 |       100 | 
                 |     0.640 |     0.360 |           | 
-----------------|-----------|-----------|-----------|

 
wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=21)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.968 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         2 |        37 |        39 | 
                 |     0.051 |     0.949 |     0.390 | 
                 |     0.032 |     1.000 |           | 
                 |     0.020 |     0.370 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        63 |        37 |       100 | 
                 |     0.630 |     0.370 |           | 
-----------------|-----------|-----------|-----------|

 
wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=27)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.938 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         4 |        35 |        39 | 
                 |     0.103 |     0.897 |     0.390 | 
                 |     0.062 |     1.000 |           | 
                 |     0.040 |     0.350 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        65 |        35 |       100 | 
                 |     0.650 |     0.350 |           | 
-----------------|-----------|-----------|-----------|

 

#These code snippets are similar to the previous one but with different values of k (k=15 and k=27). They apply the kNN algorithm to classify the test set for each k value and then generate contingency tables to assess the classification results.

LS0tDQp0aXRsZTogIlIgTm90ZWJvb2siDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQojIyMjIyBDaGFwdGVyIDM6IENsYXNzaWZpY2F0aW9uIHVzaW5nIE5lYXJlc3QgTmVpZ2hib3JzDQoNCiMjIEV4YW1wbGU6IENsYXNzaWZ5aW5nIENhbmNlciBTYW1wbGVzDQojIyBTdGVwIDI6IEV4cGxvcmluZyBhbmQgcHJlcGFyaW5nIHRoZSBkYXRhDQoNCg0KYGBge3J9DQojIGltcG9ydCB0aGUgQ1NWIGZpbGUNCndiY2QgPC0gcmVhZC5jc3YoIndpc2NfYmNfZGF0YS5jc3YiLCBzdHJpbmdzQXNGYWN0b3JzID0gRkFMU0UpDQoNCiMgZXhhbWluZSB0aGUgc3RydWN0dXJlIG9mIHRoZSB3YmNkIGRhdGEgZnJhbWUNCnN0cih3YmNkKQ0KYGBgDQojVGhlIHN0ciBmdW5jdGlvbiBpcyB0aGVuIHVzZWQgdG8gaW5zcGVjdCB0aGUgc3RydWN0dXJlIG9mIHRoZSB3YmNkIGRhdGEgZnJhbWUsIHdoaWNoIHByb3ZpZGVzIGluZm9ybWF0aW9uIGFib3V0IHRoZSBkYXRhIHR5cGVzIGFuZCBzdHJ1Y3R1cmUgb2YgZWFjaCB2YXJpYWJsZSBpbiB0aGUgZGF0YSBmcmFtZS4gVGhpcyBoZWxwcyBpbiB1bmRlcnN0YW5kaW5nIHRoZSBvdmVyYWxsIGNvbXBvc2l0aW9uIG9mIHRoZSBkYXRhc2V0Lg0KDQpgYGB7cn0NCiMgZHJvcCB0aGUgaWQgZmVhdHVyZQ0Kd2JjZCA8LSB3YmNkWy0xXQ0KYGBgDQojdGhlIHdiY2QgZGF0YSBmcmFtZSB3aWxsIG5vIGxvbmdlciBjb250YWluIHRoZSBjb2x1bW4gd2l0aCB0aGUgImlkIiBmZWF0dXJlLCBlZmZlY3RpdmVseSByZW1vdmluZyBpdCBmcm9tIHRoZSBkYXRhc2V0Lg0KDQpgYGB7cn0NCg0KIyB0YWJsZSBvZiBkaWFnbm9zaXMNCnRhYmxlKHdiY2QkZGlhZ25vc2lzKQ0KYGBgDQoNCg0KYGBge3J9DQojIHJlY29kZSBkaWFnbm9zaXMgYXMgYSBmYWN0b3INCndiY2QkZGlhZ25vc2lzIDwtIGZhY3Rvcih3YmNkJGRpYWdub3NpcywgbGV2ZWxzID0gYygiQiIsICJNIiksDQogICAgICAgICAgICAgICAgICAgICAgICAgbGFiZWxzID0gYygiQmVuaWduIiwgIk1hbGlnbmFudCIpKQ0KYGBgDQojVGhpcyBjb2RlIHVzZXMgdGhlIGZhY3RvciBmdW5jdGlvbiB0byBjb252ZXJ0IHRoZSAiZGlhZ25vc2lzIiB2YXJpYWJsZSBpbnRvIGEgZmFjdG9yIHZhcmlhYmxlIHdpdGggc3BlY2lmaWVkIGxldmVscyBhbmQgY29ycmVzcG9uZGluZyBsYWJlbHMuIFRoZSBsZXZlbHMgcGFyYW1ldGVyIHNwZWNpZmllcyB0aGUgdW5pcXVlIHZhbHVlcyB0byBiZSB1c2VkLCBhbmQgdGhlIGxhYmVscyBwYXJhbWV0ZXIgcHJvdmlkZXMgdGhlIGNvcnJlc3BvbmRpbmcgbGFiZWxzIGZvciB0aG9zZSBsZXZlbHMuDQoNCg0KYGBge3J9DQojIHRhYmxlIG9yIHByb3BvcnRpb25zIHdpdGggbW9yZSBpbmZvcm1hdGl2ZSBsYWJlbHMNCnJvdW5kKHByb3AudGFibGUodGFibGUod2JjZCRkaWFnbm9zaXMpKSAqIDEwMCwgZGlnaXRzID0gMSkNCmBgYA0KI1RoaXMgY29kZSBjYWxjdWxhdGVzIHRoZSBwcm9wb3J0aW9ucyBvZiBlYWNoIHVuaXF1ZSB2YWx1ZSBpbiB0aGUgImRpYWdub3NpcyIgdmFyaWFibGUsIGFuZCB0aGVuIG11bHRpcGxpZXMgdGhlIHJlc3VsdCBieSAxMDAgdG8gZXhwcmVzcyB0aGUgcHJvcG9ydGlvbnMgYXMgcGVyY2VudGFnZXMuDQoNCmBgYHtyfQ0KIyBzdW1tYXJpemUgdGhyZWUgbnVtZXJpYyBmZWF0dXJlcw0Kc3VtbWFyeSh3YmNkW2MoInJhZGl1c19tZWFuIiwgImFyZWFfbWVhbiIsICJzbW9vdGhuZXNzX21lYW4iKV0pDQpgYGANCiNUaGlzIGNvZGUgc2VsZWN0cyB0aGUgc3BlY2lmaWVkIG51bWVyaWMgY29sdW1ucyBmcm9tIHRoZSB3YmNkIGRhdGEgZnJhbWUgYW5kIHRoZW4gdXNlcyB0aGUgc3VtbWFyeSBmdW5jdGlvbiB0byBnZW5lcmF0ZSBzdW1tYXJ5IHN0YXRpc3RpY3MgZm9yIGVhY2ggb2YgdGhlc2UgZmVhdHVyZXMuIA0KDQpgYGB7cn0NCiMgY3JlYXRlIG5vcm1hbGl6YXRpb24gZnVuY3Rpb24NCm5vcm1hbGl6ZSA8LSBmdW5jdGlvbih4KSB7DQogIHJldHVybiAoKHggLSBtaW4oeCkpIC8gKG1heCh4KSAtIG1pbih4KSkpDQp9DQpgYGANCg0KDQoNCg0KYGBge3J9DQojIHRlc3Qgbm9ybWFsaXphdGlvbiBmdW5jdGlvbiAtIHJlc3VsdCBzaG91bGQgYmUgaWRlbnRpY2FsDQpub3JtYWxpemUoYygxLCAyLCAzLCA0LCA1KSkNCm5vcm1hbGl6ZShjKDEwLCAyMCwgMzAsIDQwLCA1MCkpDQpgYGANCg0KDQpgYGB7cn0NCiMgbm9ybWFsaXplIHRoZSB3YmNkIGRhdGENCndiY2RfbiA8LSBhcy5kYXRhLmZyYW1lKGxhcHBseSh3YmNkWzI6MzFdLCBub3JtYWxpemUpKQ0KYGBgDQoNCg0KYGBge3J9DQojIGNvbmZpcm0gdGhhdCBub3JtYWxpemF0aW9uIHdvcmtlZA0Kc3VtbWFyeSh3YmNkX24kYXJlYV9tZWFuKQ0KYGBgDQojVGhlIGxhcHBseSBmdW5jdGlvbiBpcyB1c2VkIHRvIGFwcGx5IHRoZSBub3JtYWxpemUgZnVuY3Rpb24gdG8gZWFjaCBudW1lcmljIGNvbHVtbiBpbiB0aGUgc3BlY2lmaWVkIHJhbmdlIChjb2x1bW5zIDIgdGhyb3VnaCAzMSkgb2YgdGhlIG9yaWdpbmFsIHdiY2QgZGF0YSBmcmFtZS4gVGhlIHJlc3VsdCBpcyBzdG9yZWQgaW4gYSBuZXcgZGF0YSBmcmFtZSBjYWxsZWQgd2JjZF9uLiBGaW5hbGx5LCB0aGUgc3VtbWFyeSBmdW5jdGlvbiBpcyB1c2VkIHRvIGNoZWNrIHRoZSBzdW1tYXJ5IHN0YXRpc3RpY3MgZm9yIHRoZSAiYXJlYV9tZWFuIiBmZWF0dXJlIGluIHRoZSBub3JtYWxpemVkIGRhdGEgKHdiY2RfbikuIFRoaXMgc3RlcCBpcyBhIHdheSB0byBjb25maXJtIHRoYXQgdGhlIG5vcm1hbGl6YXRpb24gcHJvY2VzcyB3YXMgc3VjY2Vzc2Z1bCBmb3Igb25lIG9mIHRoZSBmZWF0dXJlcy4NCg0KYGBge3J9DQojIGNyZWF0ZSB0cmFpbmluZyBhbmQgdGVzdCBkYXRhDQp3YmNkX3RyYWluIDwtIHdiY2RfblsxOjQ2OSwgXQ0Kd2JjZF90ZXN0IDwtIHdiY2Rfbls0NzA6NTY5LCBdDQpgYGANCg0KDQpgYGB7cn0NCiMgY3JlYXRlIGxhYmVscyBmb3IgdHJhaW5pbmcgYW5kIHRlc3QgZGF0YQ0KDQp3YmNkX3RyYWluX2xhYmVscyA8LSB3YmNkWzE6NDY5LCAxXQ0Kd2JjZF90ZXN0X2xhYmVscyA8LSB3YmNkWzQ3MDo1NjksIDFdDQpgYGANCg0KDQojIyBTdGVwIDM6IFRyYWluaW5nIGEgbW9kZWwgb24gdGhlIGRhdGENCg0KYGBge3J9DQojIGxvYWQgdGhlICJjbGFzcyIgbGlicmFyeQ0KbGlicmFyeShjbGFzcykNCmBgYA0KDQoNCmBgYHtyfQ0Kd2JjZF90ZXN0X3ByZWQgPC0ga25uKHRyYWluID0gd2JjZF90cmFpbiwgdGVzdCA9IHdiY2RfdGVzdCwNCiAgICAgICAgICAgICAgICAgICAgICBjbCA9IHdiY2RfdHJhaW5fbGFiZWxzLCBrID0gMjEpDQpgYGANCg0KI0luIHRoaXMgY29kZSwgdGhlIGtubiBmdW5jdGlvbiBmcm9tIHRoZSAiY2xhc3MiIGxpYnJhcnkgaXMgdXRpbGl6ZWQgZm9yIGtOTiBjbGFzc2lmaWNhdGlvbi4gVGhlIHRyYWluIGFyZ3VtZW50IHNwZWNpZmllcyB0aGUgdHJhaW5pbmcgZGF0YSwgdGhlIHRlc3QgYXJndW1lbnQgc3BlY2lmaWVzIHRoZSB0ZXN0IGRhdGEsIHRoZSBjbCBhcmd1bWVudCBzcGVjaWZpZXMgdGhlIGNsYXNzIGxhYmVscyBmb3IgdGhlIHRyYWluaW5nIGRhdGEsIGFuZCBrIGlzIHNldCB0byAyMSwgaW5kaWNhdGluZyB0aGF0IHRoZSBhbGdvcml0aG0gY29uc2lkZXJzIHRoZSAyMSBuZWFyZXN0IG5laWdoYm9ycyB3aGVuIG1ha2luZyBwcmVkaWN0aW9ucw0KDQojIyBTdGVwIDQ6IEV2YWx1YXRpbmcgbW9kZWwgcGVyZm9ybWFuY2UNCg0KYGBge3J9DQojIGxvYWQgdGhlICJnbW9kZWxzIiBsaWJyYXJ5DQpsaWJyYXJ5KGdtb2RlbHMpDQoNCiMgQ3JlYXRlIHRoZSBjcm9zcyB0YWJ1bGF0aW9uIG9mIHByZWRpY3RlZCB2cy4gYWN0dWFsDQpDcm9zc1RhYmxlKHggPSB3YmNkX3Rlc3RfbGFiZWxzLCB5ID0gd2JjZF90ZXN0X3ByZWQsDQogICAgICAgICAgIHByb3AuY2hpc3EgPSBGQUxTRSkNCmBgYA0KDQoNCmBgYHtyfQ0KIyMgU3RlcCA1OiBJbXByb3ZpbmcgbW9kZWwgcGVyZm9ybWFuY2UNCg0KIyB1c2UgdGhlIHNjYWxlKCkgZnVuY3Rpb24gdG8gei1zY29yZSBzdGFuZGFyZGl6ZSBhIGRhdGEgZnJhbWUNCndiY2RfeiA8LSBhcy5kYXRhLmZyYW1lKHNjYWxlKHdiY2RbLTFdKSkNCg0KIyBjb25maXJtIHRoYXQgdGhlIHRyYW5zZm9ybWF0aW9uIHdhcyBhcHBsaWVkIGNvcnJlY3RseQ0Kc3VtbWFyeSh3YmNkX3okYXJlYV9tZWFuKQ0KYGBgDQojVGhlIHNjYWxlIGZ1bmN0aW9uIGlzIGFwcGxpZWQgdG8gdGhlIG51bWVyaWMgY29sdW1ucyBpbiB0aGUgd2JjZCBkYXRhIGZyYW1lLCBleGNsdWRpbmcgdGhlIGZpcnN0IGNvbHVtbiAoaWQpLiBUaGUgcmVzdWx0IGlzIHN0b3JlZCBpbiBhIG5ldyBkYXRhIGZyYW1lIGNhbGxlZCB3YmNkX3ouIFRoZSBzdW1tYXJ5IGZ1bmN0aW9uIGlzIHRoZW4gdXNlZCB0byBjaGVjayB0aGUgc3VtbWFyeSBzdGF0aXN0aWNzIGZvciB0aGUgImFyZWFfbWVhbiIgZmVhdHVyZSBpbiB0aGUgc3RhbmRhcmRpemVkIGRhdGEgKHdiY2RfeikuIFRoaXMgc3RlcCBpcyBhIHdheSB0byBjb25maXJtIHRoYXQgdGhlIHotc2NvcmUgc3RhbmRhcmRpemF0aW9uIHByb2Nlc3Mgd2FzIHN1Y2Nlc3NmdWwgZm9yIG9uZSBvZiB0aGUgZmVhdHVyZXMuDQoNCmBgYHtyfQ0KIyBjcmVhdGUgdHJhaW5pbmcgYW5kIHRlc3QgZGF0YXNldHMNCndiY2RfdHJhaW4gPC0gd2JjZF96WzE6NDY5LCBdDQp3YmNkX3Rlc3QgPC0gd2JjZF96WzQ3MDo1NjksIF0NCg0KIyByZS1jbGFzc2lmeSB0ZXN0IGNhc2VzDQp3YmNkX3Rlc3RfcHJlZCA8LSBrbm4odHJhaW4gPSB3YmNkX3RyYWluLCB0ZXN0ID0gd2JjZF90ZXN0LA0KICAgICAgICAgICAgICAgICAgICAgIGNsID0gd2JjZF90cmFpbl9sYWJlbHMsIGsgPSAyMSkNCmBgYA0KDQojVGhpcyBjb2RlIHNwbGl0cyB0aGUgei1zY29yZSBzdGFuZGFyZGl6ZWQgZGF0YSBpbnRvIHRyYWluaW5nIGFuZCB0ZXN0IHNldHMuIFRoZSBmaXJzdCA0Njkgcm93cyBhcmUgdXNlZCBmb3IgdHJhaW5pbmcsIGFuZCB0aGUgcmVtYWluaW5nIHJvd3MgKDQ3MDo1NjkpIGFyZSB1c2VkIGZvciB0ZXN0aW5nLiBUaGUga05OIGFsZ29yaXRobSBpcyB0aGVuIGFwcGxpZWQgdG8gcmVjbGFzc2lmeSB0aGUgdGVzdCBjYXNlcyB1c2luZyB0aGUgdHJhaW5pbmcgc2V0IGFuZCBhc3NvY2lhdGVkIGxhYmVscy4NCmBgYHtyfQ0KIyBDcmVhdGUgdGhlIGNyb3NzIHRhYnVsYXRpb24gb2YgcHJlZGljdGVkIHZzLiBhY3R1YWwNCkNyb3NzVGFibGUoeCA9IHdiY2RfdGVzdF9sYWJlbHMsIHkgPSB3YmNkX3Rlc3RfcHJlZCwNCiAgICAgICAgICAgcHJvcC5jaGlzcSA9IEZBTFNFKQ0KYGBgDQoNCg0KYGBge3J9DQojIHRyeSBzZXZlcmFsIGRpZmZlcmVudCB2YWx1ZXMgb2Ygaw0Kd2JjZF90cmFpbiA8LSB3YmNkX25bMTo0NjksIF0NCndiY2RfdGVzdCA8LSB3YmNkX25bNDcwOjU2OSwgXQ0KYGBgDQoNCg0KYGBge3J9DQojSz0xDQp3YmNkX3Rlc3RfcHJlZCA8LSBrbm4odHJhaW4gPSB3YmNkX3RyYWluLCB0ZXN0ID0gd2JjZF90ZXN0LCBjbCA9IHdiY2RfdHJhaW5fbGFiZWxzLCBrPTEpDQpDcm9zc1RhYmxlKHggPSB3YmNkX3Rlc3RfbGFiZWxzLCB5ID0gd2JjZF90ZXN0X3ByZWQsIHByb3AuY2hpc3E9RkFMU0UpDQpgYGANCg0KDQpgYGB7cn0NCiNrPTUNCndiY2RfdGVzdF9wcmVkIDwtIGtubih0cmFpbiA9IHdiY2RfdHJhaW4sIHRlc3QgPSB3YmNkX3Rlc3QsIGNsID0gd2JjZF90cmFpbl9sYWJlbHMsIGs9NSkNCkNyb3NzVGFibGUoeCA9IHdiY2RfdGVzdF9sYWJlbHMsIHkgPSB3YmNkX3Rlc3RfcHJlZCwgcHJvcC5jaGlzcT1GQUxTRSkNCmBgYA0KYGBge3J9DQp3YmNkX3Rlc3RfcHJlZCA8LSBrbm4odHJhaW4gPSB3YmNkX3RyYWluLCB0ZXN0ID0gd2JjZF90ZXN0LCBjbCA9IHdiY2RfdHJhaW5fbGFiZWxzLCBrPTExKQ0KQ3Jvc3NUYWJsZSh4ID0gd2JjZF90ZXN0X2xhYmVscywgeSA9IHdiY2RfdGVzdF9wcmVkLCBwcm9wLmNoaXNxPUZBTFNFKQ0KYGBgDQoNCiNUaGlzIGNvZGUgdXNlcyB0aGUga05OIGFsZ29yaXRobSB3aXRoIGs9MSB0byBjbGFzc2lmeSB0aGUgdGVzdCBzZXQgKHdiY2RfdGVzdCkuIFRoZSBDcm9zc1RhYmxlIGZ1bmN0aW9uIHRoZW4gY3JlYXRlcyBhIGNvbnRpbmdlbmN5IHRhYmxlIHRvIGV2YWx1YXRlIHRoZSBjbGFzc2lmaWNhdGlvbiByZXN1bHRzIGJ5IGNvbXBhcmluZyB0aGUgdHJ1ZSBsYWJlbHMgKHdiY2RfdGVzdF9sYWJlbHMpIHdpdGggdGhlIHByZWRpY3RlZCBsYWJlbHMgKHdiY2RfdGVzdF9wcmVkKS4gVGhlIHByb3AuY2hpc3EgPSBGQUxTRSBhcmd1bWVudCBpbmRpY2F0ZXMgdGhhdCB0aGUgdGFibGUgc2hvdWxkIG5vdCBpbmNsdWRlIGNvbHVtbiBwZXJjZW50YWdlcy4gVGhpcyBjb250aW5nZW5jeSB0YWJsZSBoZWxwcyBhc3Nlc3MgdGhlIHBlcmZvcm1hbmNlIG9mIHRoZSBrTk4gY2xhc3NpZmljYXRpb24gZm9yIGs9MSBvbiB0aGUgdGVzdCBzZXQuDQoNCg0KYGBge3J9DQp3YmNkX3Rlc3RfcHJlZCA8LSBrbm4odHJhaW4gPSB3YmNkX3RyYWluLCB0ZXN0ID0gd2JjZF90ZXN0LCBjbCA9IHdiY2RfdHJhaW5fbGFiZWxzLCBrPTE1KQ0KQ3Jvc3NUYWJsZSh4ID0gd2JjZF90ZXN0X2xhYmVscywgeSA9IHdiY2RfdGVzdF9wcmVkLCBwcm9wLmNoaXNxPUZBTFNFKQ0KYGBgDQoNCg0KYGBge3J9DQp3YmNkX3Rlc3RfcHJlZCA8LSBrbm4odHJhaW4gPSB3YmNkX3RyYWluLCB0ZXN0ID0gd2JjZF90ZXN0LCBjbCA9IHdiY2RfdHJhaW5fbGFiZWxzLCBrPTIxKQ0KQ3Jvc3NUYWJsZSh4ID0gd2JjZF90ZXN0X2xhYmVscywgeSA9IHdiY2RfdGVzdF9wcmVkLCBwcm9wLmNoaXNxPUZBTFNFKQ0KYGBgDQoNCg0KYGBge3J9DQp3YmNkX3Rlc3RfcHJlZCA8LSBrbm4odHJhaW4gPSB3YmNkX3RyYWluLCB0ZXN0ID0gd2JjZF90ZXN0LCBjbCA9IHdiY2RfdHJhaW5fbGFiZWxzLCBrPTI3KQ0KQ3Jvc3NUYWJsZSh4ID0gd2JjZF90ZXN0X2xhYmVscywgeSA9IHdiY2RfdGVzdF9wcmVkLCBwcm9wLmNoaXNxPUZBTFNFKQ0KYGBgDQoNCiNUaGVzZSBjb2RlIHNuaXBwZXRzIGFyZSBzaW1pbGFyIHRvIHRoZSBwcmV2aW91cyBvbmUgYnV0IHdpdGggZGlmZmVyZW50IHZhbHVlcyBvZiBrIChrPTE1IGFuZCBrPTI3KS4gVGhleSBhcHBseSB0aGUga05OIGFsZ29yaXRobSB0byBjbGFzc2lmeSB0aGUgdGVzdCBzZXQgZm9yIGVhY2ggayB2YWx1ZSBhbmQgdGhlbiBnZW5lcmF0ZSBjb250aW5nZW5jeSB0YWJsZXMgdG8gYXNzZXNzIHRoZSBjbGFzc2lmaWNhdGlvbiByZXN1bHRzLg0K