Hierarchical clustering is another popular method for clustering. The goal of this chapter is to go over how it works, how to use it, and how it compares to k-means clustering.

library(readr)
library(dplyr)
library(ggplot2)
library(stringr)

2.1: Hierarchical clustering with results

In this exercise, you will create your first hierarchical clustering model using the hclust() function.

We have created some data that has two dimensions and placed it in a variable called x. Your task is to create a hierarchical clustering model of x. Remember from the video that the first step to hierarchical clustering is determining the similarity between observations, which you will do with the dist() function.

You will look at the structure of the resulting model using the summary() function.

Instructions

100 XP

x<-read.csv("Datacamp_R_Unsupervised_Learning_Chapter2_x.csv")
# Create hierarchical clustering model: hclust.out
head(x)
hclust.out <- hclust(dist(x))
# Inspect the result
summary(hclust.out)
            Length Class  Mode     
merge       98     -none- numeric  
height      49     -none- numeric  
order       50     -none- numeric  
labels       0     -none- NULL     
method       1     -none- character
call         2     -none- call     
dist.method  1     -none- character

2.2: Cutting the tree

Remember from the video that cutree() is the R function that cuts a hierarchical model. The h and k arguments to cutree() allow you to cut the tree based on a certain height h or a certain number of clusters k.

In this exercise, you will use cutree() to cut the hierarchical model you created earlier based on each of these two criteria.

Instructions

100 XP

# Cut by height
cutree(hclust.out, h = 7) 
 [1] 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[50] 2
plot(hclust.out)
abline(h = 7, col = "red")

# Cut by number of clusters
cutree(hclust.out, k = 3)
 [1] 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[50] 2

Remark: If you’re wondering what the output means, remember, there are 50 observations in the original dataset x. The output of each cutree() call represents the cluster assignments for each observation in the original dataset.

2.3: Linkage methods

In this exercise, you will produce hierarchical clustering models using different linkages and plot the dendrogram for each, observing the overall structure of the trees.

You’ll be asked to interpret the results in the next exercise.

Instructions

100 XP

# Cluster using complete linkage: hclust.complete
hclust.complete <- hclust(dist(x), method = "complete")
# Cluster using average linkage: hclust.average
hclust.average <- hclust(dist(x), method = "average")
# Cluster using single linkage: hclust.single
hclust.single <- hclust(dist(x), method = "single")
# Plot dendrogram of hclust.complete
plot(hclust.complete, main = "Complete")
abline(h = 7, col = "red")

# Plot dendrogram of hclust.average
plot(hclust.average, main = "Average")
abline(h = 4.5, col = "red")

# Plot dendrogram of hclust.single
plot(hclust.single, main = "Single")
abline(h = 1.5, col = "red")

# Cut by height
#cutree(hclust.complete, h = 7)
# Cut by number of clusters
#cutree(hclust.complete, k = 3)

Remarks: Whether you want balanced or unbalanced trees for your hierarchical clustering model depends on the context of the problem you’re trying to solve. Balanced trees are essential if you want an even number of observations assigned to each cluster. On the other hand, if you want to detect outliers, for example, an unbalanced tree is more desirable because pruning an unbalanced tree can result in most observations assigned to one cluster and only a few observations assigned to other clusters.

2.4: Practical matters: scaling

Recall from the video that clustering real data may require scaling the features if they have different distributions. So far in this chapter, you have been working with synthetic data that did not need scaling.

In this exercise, you will go back to working with “real” data, the pokemon dataset introduced in the first chapter. You will observe the distribution (mean and standard deviation) of each feature, scale the data accordingly, then produce a hierarchical clustering model using the complete linkage method.

Instructions

100 XP

pokemon_raw <- read_csv('Pokemon.csv')
Parsed with column specification:
cols(
  `#` = col_integer(),
  Name = col_character(),
  `Type 1` = col_character(),
  `Type 2` = col_character(),
  Total = col_integer(),
  HP = col_integer(),
  Attack = col_integer(),
  Defense = col_integer(),
  `Sp. Atk` = col_integer(),
  `Sp. Def` = col_integer(),
  Speed = col_integer(),
  Generation = col_integer(),
  Legendary = col_logical()
)
#head(pokemon_raw)
pokemon <- pokemon_raw %>% select(6:11)
head(pokemon)
#str(pokemon)
# View column means
colMeans(pokemon)
      HP   Attack  Defense  Sp. Atk  Sp. Def    Speed 
69.25875 79.00125 73.84250 72.82000 71.90250 68.27750 
# View column standard deviations
apply(pokemon,2,sd)
      HP   Attack  Defense  Sp. Atk  Sp. Def    Speed 
25.53467 32.45737 31.18350 32.72229 27.82892 29.06047 
# Scale the data
pokemon.scaled<-scale(pokemon)
# Create hierarchical clustering model: hclust.pokemon
hclust.pokemon<-hclust(dist(pokemon.scaled), method="complete")
# Apply cutree() to hclust.pokemon: cut.pokemon
cut.pokemon<-cutree(hclust.pokemon,k=3)
##############################################################
# Initialize total within sum of squares error: wss
wss <- 0
# Look over 1 to 15 possible clusters
for (i in 1:15) {
  # Fit the model: km.pokemon
  km.pokemon <- kmeans(pokemon, centers = i, nstart = 20, iter.max = 50)
  # Save the within cluster sum of squares
  wss[i] <- km.pokemon$tot.withinss
}
# Produce a scree plot
plot(1:15, wss, type = "b", 
     xlab = "Number of Clusters", 
     ylab = "Within groups sum of squares")

# Select number of clusters
k <- 3
# Build model with k clusters: km.out
km.pokemon <- kmeans(pokemon, centers = k, nstart = 20, iter.max = 50)
#####################################################################
# Compare methods
table(km.pokemon$cluster, cut.pokemon)
   cut.pokemon
      1   2   3
  1 267   3   0
  2 171   3   1
  3 350   5   0

Remarks: Looking at the table, it looks like the hierarchical clustering model assigns most of the observations to cluster 1, while the k-means algorithm distributes the observations relatively evenly among all clusters. It’s important to note that there’s no consensus on which method produces better clusters. The job of the analyst in unsupervised clustering is to observe the cluster assignments and make a judgment call as to which method provides more insights into the data.

LS0tDQp0aXRsZTogIkRhdGFjYW1wIFIgLSBVbnN1cGVydmlzZWQgTGVhcm5pbmcgaW4gUiA6IENoYXB0ZXIgMiAoSGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcpIg0KYXV0aG9yOiAiQ2hlbiBXZWlxaWFuZyINCmRhdGU6ICJOb3ZlbWJlciAyOCwgMjAxOCINCm91dHB1dDogaHRtbF9ub3RlYm9vaw0KLS0tDQoNCg0KSGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgaXMgYW5vdGhlciBwb3B1bGFyIG1ldGhvZCBmb3IgY2x1c3RlcmluZy4gVGhlIGdvYWwgb2YgdGhpcyBjaGFwdGVyIGlzIHRvIGdvIG92ZXIgaG93IGl0IHdvcmtzLCBob3cgdG8gdXNlIGl0LCBhbmQgaG93IGl0IGNvbXBhcmVzIHRvIGstbWVhbnMgY2x1c3RlcmluZy4NCg0KYGBge3J9DQpsaWJyYXJ5KHJlYWRyKQ0KbGlicmFyeShkcGx5cikNCmxpYnJhcnkoZ2dwbG90MikNCmxpYnJhcnkoc3RyaW5ncikNCmBgYA0KDQojIDIuMTogSGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgd2l0aCByZXN1bHRzDQoNCkluIHRoaXMgZXhlcmNpc2UsIHlvdSB3aWxsIGNyZWF0ZSB5b3VyIGZpcnN0IGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIG1vZGVsIHVzaW5nIHRoZSBoY2x1c3QoKSBmdW5jdGlvbi4NCg0KV2UgaGF2ZSBjcmVhdGVkIHNvbWUgZGF0YSB0aGF0IGhhcyB0d28gZGltZW5zaW9ucyBhbmQgcGxhY2VkIGl0IGluIGEgdmFyaWFibGUgY2FsbGVkIHguIFlvdXIgdGFzayBpcyB0byBjcmVhdGUgYSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyBtb2RlbCBvZiB4LiBSZW1lbWJlciBmcm9tIHRoZSB2aWRlbyB0aGF0IHRoZSBmaXJzdCBzdGVwIHRvIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIGlzIGRldGVybWluaW5nIHRoZSBzaW1pbGFyaXR5IGJldHdlZW4gb2JzZXJ2YXRpb25zLCB3aGljaCB5b3Ugd2lsbCBkbyB3aXRoIHRoZSBkaXN0KCkgZnVuY3Rpb24uDQoNCllvdSB3aWxsIGxvb2sgYXQgdGhlIHN0cnVjdHVyZSBvZiB0aGUgcmVzdWx0aW5nIG1vZGVsIHVzaW5nIHRoZSBzdW1tYXJ5KCkgZnVuY3Rpb24uDQoNCkluc3RydWN0aW9ucw0KDQoxMDAgWFANCg0KLSBGaXQgYSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyBtb2RlbCB0byB4IHVzaW5nIHRoZSBoY2x1c3QoKSBmdW5jdGlvbi4gU3RvcmUgdGhlIHJlc3VsdCBpbiBoY2x1c3Qub3V0Lg0KDQotIEluc3BlY3QgdGhlIHJlc3VsdCB3aXRoIHRoZSBzdW1tYXJ5KCkgZnVuY3Rpb24uDQoNCmBgYHtyfQ0KeDwtcmVhZC5jc3YoIkRhdGFjYW1wX1JfVW5zdXBlcnZpc2VkX0xlYXJuaW5nX0NoYXB0ZXIyX3guY3N2IikNCiMgQ3JlYXRlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIG1vZGVsOiBoY2x1c3Qub3V0DQpoZWFkKHgpDQpoY2x1c3Qub3V0IDwtIGhjbHVzdChkaXN0KHgpKQ0KDQojIEluc3BlY3QgdGhlIHJlc3VsdA0Kc3VtbWFyeShoY2x1c3Qub3V0KQ0KYGBgDQoNCiMgMi4yOiBDdXR0aW5nIHRoZSB0cmVlDQoNClJlbWVtYmVyIGZyb20gdGhlIHZpZGVvIHRoYXQgY3V0cmVlKCkgaXMgdGhlIFIgZnVuY3Rpb24gdGhhdCBjdXRzIGEgaGllcmFyY2hpY2FsIG1vZGVsLiBUaGUgaCBhbmQgayBhcmd1bWVudHMgdG8gY3V0cmVlKCkgYWxsb3cgeW91IHRvIGN1dCB0aGUgdHJlZSBiYXNlZCBvbiBhIGNlcnRhaW4gaGVpZ2h0IGggb3IgYSBjZXJ0YWluIG51bWJlciBvZiBjbHVzdGVycyBrLg0KDQpJbiB0aGlzIGV4ZXJjaXNlLCB5b3Ugd2lsbCB1c2UgY3V0cmVlKCkgdG8gY3V0IHRoZSBoaWVyYXJjaGljYWwgbW9kZWwgeW91IGNyZWF0ZWQgZWFybGllciBiYXNlZCBvbiBlYWNoIG9mIHRoZXNlIHR3byBjcml0ZXJpYS4NCg0KSW5zdHJ1Y3Rpb25zDQoNCjEwMCBYUA0KDQotIFRoZSBoY2x1c3Qub3V0IG1vZGVsIHlvdSBjcmVhdGVkIGVhcmxpZXIgaXMgYXZhaWxhYmxlIGluIHlvdXIgd29ya3NwYWNlLg0KDQotIEN1dCB0aGUgaGNsdXN0Lm91dCBtb2RlbCBhdCBoZWlnaHQgNy4NCg0KLSBDdXQgdGhlIGhjbHVzdC5vdXQgbW9kZWwgdG8gY3JlYXRlIDMgY2x1c3RlcnMuDQoNCmBgYHtyfQ0KIyBDdXQgYnkgaGVpZ2h0DQpjdXRyZWUoaGNsdXN0Lm91dCwgaCA9IDcpIA0KDQpwbG90KGhjbHVzdC5vdXQpDQphYmxpbmUoaCA9IDcsIGNvbCA9ICJyZWQiKQ0KDQojIEN1dCBieSBudW1iZXIgb2YgY2x1c3RlcnMNCmN1dHJlZShoY2x1c3Qub3V0LCBrID0gMykNCmBgYA0KDQpSZW1hcms6IElmIHlvdSdyZSB3b25kZXJpbmcgd2hhdCB0aGUgb3V0cHV0IG1lYW5zLCByZW1lbWJlciwgdGhlcmUgYXJlIDUwIG9ic2VydmF0aW9ucyBpbiB0aGUgb3JpZ2luYWwgZGF0YXNldCB4LiBUaGUgb3V0cHV0IG9mIGVhY2ggY3V0cmVlKCkgY2FsbCByZXByZXNlbnRzIHRoZSBjbHVzdGVyIGFzc2lnbm1lbnRzIGZvciBlYWNoIG9ic2VydmF0aW9uIGluIHRoZSBvcmlnaW5hbCBkYXRhc2V0LiANCg0KIyAyLjM6IExpbmthZ2UgbWV0aG9kcw0KDQpJbiB0aGlzIGV4ZXJjaXNlLCB5b3Ugd2lsbCBwcm9kdWNlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIG1vZGVscyB1c2luZyBkaWZmZXJlbnQgbGlua2FnZXMgYW5kIHBsb3QgdGhlIGRlbmRyb2dyYW0gZm9yIGVhY2gsIG9ic2VydmluZyB0aGUgb3ZlcmFsbCBzdHJ1Y3R1cmUgb2YgdGhlIHRyZWVzLg0KDQpZb3UnbGwgYmUgYXNrZWQgdG8gaW50ZXJwcmV0IHRoZSByZXN1bHRzIGluIHRoZSBuZXh0IGV4ZXJjaXNlLg0KDQpJbnN0cnVjdGlvbnMNCg0KMTAwIFhQDQoNCi0gUHJvZHVjZSB0aHJlZSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyBtb2RlbHMgb24geCB1c2luZyB0aGUgImNvbXBsZXRlIiwgImF2ZXJhZ2UiLCBhbmQgInNpbmdsZSIgbGlua2FnZSBtZXRob2RzLCByZXNwZWN0aXZlbHkuDQoNCi0gUGxvdCBhIGRlbmRyb2dyYW0gZm9yIGVhY2ggbW9kZWwsIHVzaW5nIHRpdGxlcyBvZiAiQ29tcGxldGUiLCAiQXZlcmFnZSIsIGFuZCAiU2luZ2xlIiwgcmVzcGVjdGl2ZWx5Lg0KDQpgYGB7cn0NCiMgQ2x1c3RlciB1c2luZyBjb21wbGV0ZSBsaW5rYWdlOiBoY2x1c3QuY29tcGxldGUNCmhjbHVzdC5jb21wbGV0ZSA8LSBoY2x1c3QoZGlzdCh4KSwgbWV0aG9kID0gImNvbXBsZXRlIikNCg0KIyBDbHVzdGVyIHVzaW5nIGF2ZXJhZ2UgbGlua2FnZTogaGNsdXN0LmF2ZXJhZ2UNCmhjbHVzdC5hdmVyYWdlIDwtIGhjbHVzdChkaXN0KHgpLCBtZXRob2QgPSAiYXZlcmFnZSIpDQoNCiMgQ2x1c3RlciB1c2luZyBzaW5nbGUgbGlua2FnZTogaGNsdXN0LnNpbmdsZQ0KaGNsdXN0LnNpbmdsZSA8LSBoY2x1c3QoZGlzdCh4KSwgbWV0aG9kID0gInNpbmdsZSIpDQoNCiMgUGxvdCBkZW5kcm9ncmFtIG9mIGhjbHVzdC5jb21wbGV0ZQ0KcGxvdChoY2x1c3QuY29tcGxldGUsIG1haW4gPSAiQ29tcGxldGUiKQ0KYWJsaW5lKGggPSA3LCBjb2wgPSAicmVkIikNCg0KIyBQbG90IGRlbmRyb2dyYW0gb2YgaGNsdXN0LmF2ZXJhZ2UNCnBsb3QoaGNsdXN0LmF2ZXJhZ2UsIG1haW4gPSAiQXZlcmFnZSIpDQphYmxpbmUoaCA9IDQuNSwgY29sID0gInJlZCIpDQoNCiMgUGxvdCBkZW5kcm9ncmFtIG9mIGhjbHVzdC5zaW5nbGUNCnBsb3QoaGNsdXN0LnNpbmdsZSwgbWFpbiA9ICJTaW5nbGUiKQ0KYWJsaW5lKGggPSAxLjUsIGNvbCA9ICJyZWQiKQ0KDQojIEN1dCBieSBoZWlnaHQNCiNjdXRyZWUoaGNsdXN0LmNvbXBsZXRlLCBoID0gNykNCiMgQ3V0IGJ5IG51bWJlciBvZiBjbHVzdGVycw0KI2N1dHJlZShoY2x1c3QuY29tcGxldGUsIGsgPSAzKQ0KDQoNCmBgYA0KDQpSZW1hcmtzOiBXaGV0aGVyIHlvdSB3YW50IGJhbGFuY2VkIG9yIHVuYmFsYW5jZWQgdHJlZXMgZm9yIHlvdXIgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgbW9kZWwgZGVwZW5kcyBvbiB0aGUgY29udGV4dCBvZiB0aGUgcHJvYmxlbSB5b3UncmUgdHJ5aW5nIHRvIHNvbHZlLiBCYWxhbmNlZCB0cmVlcyBhcmUgZXNzZW50aWFsIGlmIHlvdSB3YW50IGFuIGV2ZW4gbnVtYmVyIG9mIG9ic2VydmF0aW9ucyBhc3NpZ25lZCB0byBlYWNoIGNsdXN0ZXIuIE9uIHRoZSBvdGhlciBoYW5kLCBpZiB5b3Ugd2FudCB0byBkZXRlY3Qgb3V0bGllcnMsIGZvciBleGFtcGxlLCBhbiB1bmJhbGFuY2VkIHRyZWUgaXMgbW9yZSBkZXNpcmFibGUgYmVjYXVzZSBwcnVuaW5nIGFuIHVuYmFsYW5jZWQgdHJlZSBjYW4gcmVzdWx0IGluIG1vc3Qgb2JzZXJ2YXRpb25zIGFzc2lnbmVkIHRvIG9uZSBjbHVzdGVyIGFuZCBvbmx5IGEgZmV3IG9ic2VydmF0aW9ucyBhc3NpZ25lZCB0byBvdGhlciBjbHVzdGVycy4NCg0KIyAyLjQ6IFByYWN0aWNhbCBtYXR0ZXJzOiBzY2FsaW5nDQoNClJlY2FsbCBmcm9tIHRoZSB2aWRlbyB0aGF0IGNsdXN0ZXJpbmcgcmVhbCBkYXRhIG1heSByZXF1aXJlIHNjYWxpbmcgdGhlIGZlYXR1cmVzIGlmIHRoZXkgaGF2ZSBkaWZmZXJlbnQgZGlzdHJpYnV0aW9ucy4gU28gZmFyIGluIHRoaXMgY2hhcHRlciwgeW91IGhhdmUgYmVlbiB3b3JraW5nIHdpdGggc3ludGhldGljIGRhdGEgdGhhdCBkaWQgbm90IG5lZWQgc2NhbGluZy4NCg0KSW4gdGhpcyBleGVyY2lzZSwgeW91IHdpbGwgZ28gYmFjayB0byB3b3JraW5nIHdpdGggInJlYWwiIGRhdGEsIHRoZSBwb2tlbW9uIGRhdGFzZXQgaW50cm9kdWNlZCBpbiB0aGUgZmlyc3QgY2hhcHRlci4gWW91IHdpbGwgb2JzZXJ2ZSB0aGUgZGlzdHJpYnV0aW9uIChtZWFuIGFuZCBzdGFuZGFyZCBkZXZpYXRpb24pIG9mIGVhY2ggZmVhdHVyZSwgc2NhbGUgdGhlIGRhdGEgYWNjb3JkaW5nbHksIHRoZW4gcHJvZHVjZSBhIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIG1vZGVsIHVzaW5nIHRoZSBjb21wbGV0ZSBsaW5rYWdlIG1ldGhvZC4NCg0KSW5zdHJ1Y3Rpb25zDQoNCjEwMCBYUA0KDQotIFRoZSBkYXRhIGlzIHN0b3JlZCBpbiB0aGUgcG9rZW1vbiBvYmplY3QgaW4geW91ciB3b3Jrc3BhY2UuDQoNCi0gT2JzZXJ2ZSB0aGUgbWVhbiBvZiBlYWNoIHZhcmlhYmxlIGluIHBva2Vtb24gdXNpbmcgdGhlIGNvbE1lYW5zKCkgZnVuY3Rpb24uDQoNCi0gT2JzZXJ2ZSB0aGUgc3RhbmRhcmQgZGV2aWF0aW9uIG9mIGVhY2ggdmFyaWFibGUgdXNpbmcgdGhlIGFwcGx5KCkgYW5kIHNkKCkgZnVuY3Rpb25zLiBTaW5jZSB0aGUgdmFyaWFibGVzIGFyZSB0aGUgY29sdW1ucyBvZiB5b3VyIG1hdHJpeCwgbWFrZSBzdXJlIHRvIHNwZWNpZnkgMiBhcyB0aGUgTUFSR0lOIGFyZ3VtZW50IHRvIGFwcGx5KCkuDQoNCi0gU2NhbGUgdGhlIHBva2Vtb24gZGF0YSB1c2luZyB0aGUgc2NhbGUoKSBmdW5jdGlvbiBhbmQgc3RvcmUgdGhlIHJlc3VsdCBpbiBwb2tlbW9uLnNjYWxlZC4NCg0KLSBDcmVhdGUgYSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyBtb2RlbCBvZiB0aGUgcG9rZW1vbi5zY2FsZWQgZGF0YSB1c2luZyB0aGUgY29tcGxldGUgbGlua2FnZSBtZXRob2QuIA0KDQotIE1hbnVhbGx5IHNwZWNpZnkgdGhlIG1ldGhvZCBhcmd1bWVudCBhbmQgc3RvcmUgdGhlIHJlc3VsdCBpbiBoY2x1c3QucG9rZW1vbi4NCg0KYGBge3J9DQpwb2tlbW9uX3JhdyA8LSByZWFkX2NzdignUG9rZW1vbi5jc3YnKQ0KI2hlYWQocG9rZW1vbl9yYXcpDQoNCnBva2Vtb24gPC0gcG9rZW1vbl9yYXcgJT4lIHNlbGVjdCg2OjExKQ0KaGVhZChwb2tlbW9uKQ0KI3N0cihwb2tlbW9uKQ0KDQoNCiMgVmlldyBjb2x1bW4gbWVhbnMNCmNvbE1lYW5zKHBva2Vtb24pDQoNCiMgVmlldyBjb2x1bW4gc3RhbmRhcmQgZGV2aWF0aW9ucw0KYXBwbHkocG9rZW1vbiwyLHNkKQ0KDQojIFNjYWxlIHRoZSBkYXRhDQpwb2tlbW9uLnNjYWxlZDwtc2NhbGUocG9rZW1vbikNCg0KIyBDcmVhdGUgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgbW9kZWw6IGhjbHVzdC5wb2tlbW9uDQpoY2x1c3QucG9rZW1vbjwtaGNsdXN0KGRpc3QocG9rZW1vbi5zY2FsZWQpLCBtZXRob2Q9ImNvbXBsZXRlIikNCmBgYA0KDQoNCg0KYGBge3J9DQojIEFwcGx5IGN1dHJlZSgpIHRvIGhjbHVzdC5wb2tlbW9uOiBjdXQucG9rZW1vbg0KY3V0LnBva2Vtb248LWN1dHJlZShoY2x1c3QucG9rZW1vbixrPTMpDQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KIyBJbml0aWFsaXplIHRvdGFsIHdpdGhpbiBzdW0gb2Ygc3F1YXJlcyBlcnJvcjogd3NzDQp3c3MgPC0gMA0KDQojIExvb2sgb3ZlciAxIHRvIDE1IHBvc3NpYmxlIGNsdXN0ZXJzDQpmb3IgKGkgaW4gMToxNSkgew0KICAjIEZpdCB0aGUgbW9kZWw6IGttLnBva2Vtb24NCiAga20ucG9rZW1vbiA8LSBrbWVhbnMocG9rZW1vbiwgY2VudGVycyA9IGksIG5zdGFydCA9IDIwLCBpdGVyLm1heCA9IDUwKQ0KICAjIFNhdmUgdGhlIHdpdGhpbiBjbHVzdGVyIHN1bSBvZiBzcXVhcmVzDQogIHdzc1tpXSA8LSBrbS5wb2tlbW9uJHRvdC53aXRoaW5zcw0KfQ0KDQojIFByb2R1Y2UgYSBzY3JlZSBwbG90DQpwbG90KDE6MTUsIHdzcywgdHlwZSA9ICJiIiwgDQogICAgIHhsYWIgPSAiTnVtYmVyIG9mIENsdXN0ZXJzIiwgDQogICAgIHlsYWIgPSAiV2l0aGluIGdyb3VwcyBzdW0gb2Ygc3F1YXJlcyIpDQoNCiMgU2VsZWN0IG51bWJlciBvZiBjbHVzdGVycw0KayA8LSAzDQoNCiMgQnVpbGQgbW9kZWwgd2l0aCBrIGNsdXN0ZXJzOiBrbS5vdXQNCmttLnBva2Vtb24gPC0ga21lYW5zKHBva2Vtb24sIGNlbnRlcnMgPSBrLCBuc3RhcnQgPSAyMCwgaXRlci5tYXggPSA1MCkNCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KIyBDb21wYXJlIG1ldGhvZHMNCnRhYmxlKGttLnBva2Vtb24kY2x1c3RlciwgY3V0LnBva2Vtb24pDQpgYGANCg0KUmVtYXJrczogTG9va2luZyBhdCB0aGUgdGFibGUsIGl0IGxvb2tzIGxpa2UgdGhlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIG1vZGVsIGFzc2lnbnMgbW9zdCBvZiB0aGUgb2JzZXJ2YXRpb25zIHRvIGNsdXN0ZXIgMSwgd2hpbGUgdGhlIGstbWVhbnMgYWxnb3JpdGhtIGRpc3RyaWJ1dGVzIHRoZSBvYnNlcnZhdGlvbnMgcmVsYXRpdmVseSBldmVubHkgYW1vbmcgYWxsIGNsdXN0ZXJzLiBJdCdzIGltcG9ydGFudCB0byBub3RlIHRoYXQgdGhlcmUncyBubyBjb25zZW5zdXMgb24gd2hpY2ggbWV0aG9kIHByb2R1Y2VzIGJldHRlciBjbHVzdGVycy4gVGhlIGpvYiBvZiB0aGUgYW5hbHlzdCBpbiB1bnN1cGVydmlzZWQgY2x1c3RlcmluZyBpcyB0byBvYnNlcnZlIHRoZSBjbHVzdGVyIGFzc2lnbm1lbnRzIGFuZCBtYWtlIGEganVkZ21lbnQgY2FsbCBhcyB0byB3aGljaCBtZXRob2QgcHJvdmlkZXMgbW9yZSBpbnNpZ2h0cyBpbnRvIHRoZSBkYXRhLiA=