Sushant Gote 17PHD1054
``
install.packages("cluster")
install?packages("dendextend")
install.packages('factoextra')
#Load the packages :
### Installling addtional Packages if required
library('cluster')
library('dendextend')
library('factoextra')
print('Done')
Hierachical Clustering
?ierarchical clustering can be divided into two main types: agglomerative and divisive.
Agglomerative clustering: It’s also known as AGNES (Agglomerative Nesting). It works in a bottom-up manner. That is, each object is initially considered as a single-ele?ent cluster (leaf). At each step of the algorithm, the two clusters that are the most similar are combined into a new bigger cluster (nodes). This procedure is iterated until all points are member of just one single big cluster (root) (see figure below). T?e result is a tree which can be plotted as a dendrogram.
Divisive hierarchical clustering: It’s also known as DIANA (Divise Analysis) and it works in a top-down manner. The algorithm is an inverse order of AGNES. It begins with the root, in which all obje?ts are included in a single cluster. At each step of iteration, the most heterogeneous cluster is divided into two. The process is iterated until all objects are in their own cluster .
Note that agglomerative clustering is good at identifying small clust?rs. Divisive hierarchical clustering is good at identifying large clusters.
The merging or the division of clusters is performed according some (dis)similarity measure. In R softwrare, the Euclidean distance is used by default to measure the dissimilarity?between each pair of observations.
Tt’s easy to compute dissimilarity measure between two pairs of observations. It’s mentioned above that two clusters that are most similar are fused into a new big cluster.
A natural question is : How to measure the dis?imilarity between two clusters of observations?
A number of different cluster agglomeration methods (i.e, linkage methods) has been developed to answer to this question. The most common types methods are:
Maximum or complete linkage clustering: It compu?es all pairwise dissimilarities between the elements in cluster 1 and the elements in cluster 2, and considers the largest value (i.e., maximum value) of these dissimilarities as the distance between the two clusters. It tends to produce more compact clust?rs.
Minimum or single linkage clustering: It computes all pairwise dissimilarities between the elements in cluster 1 and the elements in cluster 2, and considers the smallest of these dissimilarities as a linkage criterion. It tends to produce long, “loo?e” clusters.
Mean or average linkage clustering: It computes all pairwise dissimilarities between the elements in cluster 1 and the elements in cluster 2, and considers the average of these dissimilarities as the distance between the two clusters.
Comple?e linkage and Ward’s method are generally preferred.
Centroid linkage clustering: It computes the dissimilarity between the centroid for cluster 1 (a mean vector of length p variables) and the centroid for cluster 2.
Ward’s minimum variance method: It mi?imizes the total within-cluster variance. At each step the pair of clusters with minimum between-cluster distance are merged.
Data preparation and descriptive statistics
R dataset USArrest which contains statistics, in arrests per 100,000 residents for ?ssault, murder, and rape in each of the 50 US states in 1973. It includes also the percent of the population living in urban areas.
It contains 50 observations on 4 variables:
[,1] Murder numeric Murder arrests (per 100,000) [,2] Assault numeric Assault ?rrests (per 100,000) [,3] UrbanPop numeric Percent urban population [,4] Rape numeric Rape arrests (per 100,000)
# Load the data set
data("USArrests")
# Remove any missing value (i.e, NA values for not available)
# That might be present in the data
df <- na.omit(USArrests)
# View the firt 6 rows of the data
head(df, n = 6)
Before hierarchical clustering, we can compute some descriptive statistics:
desc_stats <- data.frame(
Min = apply(df, 2, min), # minimum
Med = apply(df, 2, median), # median
Mean = apply(df, 2, mean), # mean
SD = apply(df, 2, sd), # Standard deviation
Max = apply(df, 2, max) # Maximum
)
desc_stats <- round(desc_stats, 1)
head(desc_stats)
Note that the variables have a large different means and va?iances. This is explained by the fact that the variables are measured in different units; Murder, Rape, and Assault are measured as the number of occurrences per 100 000 people, and UrbanPop is the percentage of the state’s population that lives in an urba? area.
They must be standardized (i.e., scaled) to make them comparable. Recall that, standardization consists of transforming the variables such that they have mean zero and standard deviation one.
df <- scale(df)
head(df)
Murder Assault UrbanPop Rape
Alabama 1.24256408 0.7828393 -0.5209066 -0.003416473
Alaska 0.50786248 1.1068225 -1.2117642 2.484202941
Arizona 0.07163341 1.4788032 0.9989801 1.042878388
Arkansas 0.23234938 0.2308680 -1.0735927 -0.184916602
California 0.27826823 1.2628144 1.7589234 2.067820292
Colorado 0.02571456 0.3988593 0.8608085 1.864967207
print('Look @ this head')
[1] "Look @ this head"
R functions for hierarchical clustering
There are different functions available in R for computing hierarchical clustering. The commonly used functions are:
hclust() [in stats package] and agnes() [in cluster package] for agglomerative hierarch?cal clustering (HC) diana() [in cluster package] for divisive HC #### hclust() function hclust() is the built-in R function [in stats package] for computing hierarchical clustering.
The simplified format is:
hclust(d, method = “complete”)
d a dissimilar?ty structure as produced by the dist() function. method: The agglomeration method to be used. Allowed values is one of “ward.D”, “ward.D2”, “single”, “complete”, “average”, “mcquitty”, “median” or “centroid”.
The dist() function is used to compute the Eu?lidean distance between observations. Finally, observations are clustered using Ward’s method.
# Dissimilarity matrix
d <- dist(df, method = "euclidean")
# Hierarchical clustering using Ward's method
res.hc <- hclust(d, method = "ward.D2" )
# Plot the obtained dendrogram
plot(res.hc, cex = 0.6, hang = -1)
agnes() and diana() functions
The R function agnes() [in cluster package] can be also used to compute agglomerative hierarchical clustering. The R function diana() [ in cluster package ] is?an example of divisive hierarchical clustering.
Agglomerative Nesting (Hierarchical Clustering)
agnes(x, metric = “euclidean”, stand = FALSE, method = “average”)
DIvisive ANAlysis Clustering
diana(x, metric = “euclidean”, stand = FALSE)
x: data ?atrix or data frame or dissimilarity matrix. In case of matrix and data frame, rows are observations and columns are variables. In case of a dissimilarity matrix, x is typically the output of daisy() or dist(). metric: the metric to be used for calculating?dissimilarities between observations. Possible values are “euclidean” and “manhattan”. stand: if TRUE, then the measurements in x are standardized before calculating the dissimilarities. Measurements are standardized for each variable (column), by subtract?ng the variable’s mean value and dividing by the variable’s mean absolute deviation method: The clustering method. Possible values includes “average”, “single”, “complete”, “ward”.
The function agnes() returns an object of class “agnes” (see ?agnes.objec?) which has methods for the functions: print(), summary(), plot(), pltree(), as.dendrogram(), as.hclust() and cutree(). The function diana() returns an object of class “diana” (see ?diana.object) which has also methods for the functions: print(), summary()? plot(), pltree(), as.dendrogram(), as.hclust() and cutree(). Compared to other agglomerative clustering methods such as hclust(), agnes() has the following features:
It yields the agglomerative coefficient (see agnes.object) which measures the amount of ?lustering structure found Apart from the usual tree it also provides the banner, a novel graphical display (see plot.agnes).
library("cluster")
# Compute agnes()
res.agnes <- agnes(df, method = "ward")
# Agglomerative coefficient
res.agnes$ac
[1] 0.934621
``?{r} # Plot the tree using pltree() pltree(res.agnes, cex = 0.6, hang = -1, main = “Dendrogram of Agnes”) print(‘Done’) ```
# Plot the tree using pltree()
pltree(res.agnes, cex = 0.6, hang = -1, main = "Dendrogram of Agnes")
print('Done')
[1] "Done"
It’s also possible to draw AGNES dendrogram ?sing the function plot.hclust() and the function plot.dendrogram() as follow:
pltree(res.agnes, cex = 0.6, hang = -1, main = "Dendrogram of Agnes")
plot.dendrogram()
# plot.hclust()
plot(as.hclust(res.agnes), cex = 0.6, hang = -1)
DIANA
# plot.dendrogram()
plot(as.dendrogram(res.agnes), cex = 0.6,
horiz = TRUE)
LS0tDQp0aXRsZTogJ01hY2hpbmUgTGVhbnJpbmcgQXNzaWdubWVudCAyOiBBbmFseXNpcyBvZiBDbHVzdGVyaW5nIEstTWVhbnMsIERJQU5BLCBBR05FUywNCiAgU09NJw0Kb3V0cHV0Og0KICBodG1sX25vdGVib29rOiBkZWZhdWx0DQogIHBkZl9kb2N1bWVudDogZGVmYXVsdA0KICB3b3JkX2RvY3VtZW50OiBkZWZhdWx0DQotLS0NCiMjIyBTdXNoYW50IEdvdGUgMTdQSEQxMDU0DQoNCmBgDQoNCmBgYHtyfQ0KaW5zdGFsbC5wYWNrYWdlcygiY2x1c3RlciIpDQppbnN0YWxsP3BhY2thZ2VzKCJkZW5kZXh0ZW5kIikNCmluc3RhbGwucGFja2FnZXMoJ2ZhY3RvZXh0cmEnKQ0KI0xvYWQgdGhlIHBhY2thZ2VzIDoNCmBgYA0KDQpgYGB7cn0NCiMjIyBJbnN0YWxsbGluZyBhZGR0aW9uYWwgUGFja2FnZXMgaWYgcmVxdWlyZWQNCmBgYA0KDQogDQpgYGB7cn0NCmxpYnJhcnkoJ2NsdXN0ZXInKQ0KbGlicmFyeSgnZGVuZGV4dGVuZCcpDQpsaWJyYXJ5KCdmYWN0b2V4dHJhJykNCnByaW50KCdEb25lJykNCiANCmBgYA0KIyBIaWVyYWNoaWNhbCBDbHVzdGVyaW5nDQo/aWVyYXJjaGljYWwgY2x1c3RlcmluZyBjYW4gYmUgZGl2aWRlZCBpbnRvIHR3byBtYWluIHR5cGVzOiBhZ2dsb21lcmF0aXZlIGFuZCBkaXZpc2l2ZS4NCg0KQWdnbG9tZXJhdGl2ZSBjbHVzdGVyaW5nOiBJdCdzIGFsc28ga25vd24gYXMgQUdORVMgKEFnZ2xvbWVyYXRpdmUgTmVzdGluZykuIEl0IHdvcmtzIGluIGEgYm90dG9tLXVwIG1hbm5lci4gVGhhdCBpcywgZWFjaCBvYmplY3QgaXMgaW5pdGlhbGx5IGNvbnNpZGVyZWQgYXMgYSBzaW5nbGUtZWxlP2VudCBjbHVzdGVyIChsZWFmKS4gQXQgZWFjaCBzdGVwIG9mIHRoZSBhbGdvcml0aG0sIHRoZSB0d28gY2x1c3RlcnMgdGhhdCBhcmUgdGhlIG1vc3Qgc2ltaWxhciBhcmUgY29tYmluZWQgaW50byBhIG5ldyBiaWdnZXIgY2x1c3RlciAobm9kZXMpLiBUaGlzIHByb2NlZHVyZSBpcyBpdGVyYXRlZCB1bnRpbCBhbGwgcG9pbnRzIGFyZSBtZW1iZXIgb2YganVzdCBvbmUgc2luZ2xlIGJpZyBjbHVzdGVyIChyb290KSAoc2VlIGZpZ3VyZSBiZWxvdykuIFQ/ZSByZXN1bHQgaXMgYSB0cmVlIHdoaWNoIGNhbiBiZSBwbG90dGVkIGFzIGEgZGVuZHJvZ3JhbS4NCg0KRGl2aXNpdmUgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmc6IEl0J3MgYWxzbyBrbm93biBhcyBESUFOQSAoRGl2aXNlIEFuYWx5c2lzKSBhbmQgaXQgd29ya3MgaW4gYSB0b3AtZG93biBtYW5uZXIuIFRoZSBhbGdvcml0aG0gaXMgYW4gaW52ZXJzZSBvcmRlciBvZiBBR05FUy4gSXQgYmVnaW5zIHdpdGggdGhlIHJvb3QsIGluIHdoaWNoIGFsbCBvYmplP3RzIGFyZSBpbmNsdWRlZCBpbiBhIHNpbmdsZSBjbHVzdGVyLiBBdCBlYWNoIHN0ZXAgb2YgaXRlcmF0aW9uLCB0aGUgbW9zdCBoZXRlcm9nZW5lb3VzIGNsdXN0ZXIgaXMgZGl2aWRlZCBpbnRvIHR3by4gVGhlIHByb2Nlc3MgaXMgaXRlcmF0ZWQgdW50aWwgYWxsIG9iamVjdHMgYXJlIGluIHRoZWlyIG93biBjbHVzdGVyICAuDQoNCk5vdGUgdGhhdCBhZ2dsb21lcmF0aXZlIGNsdXN0ZXJpbmcgaXMgZ29vZCBhdCBpZGVudGlmeWluZyBzbWFsbCBjbHVzdD9ycy4gRGl2aXNpdmUgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgaXMgZ29vZCBhdCBpZGVudGlmeWluZyBsYXJnZSBjbHVzdGVycy4NCg0KVGhlIG1lcmdpbmcgb3IgdGhlIGRpdmlzaW9uIG9mIGNsdXN0ZXJzIGlzIHBlcmZvcm1lZCBhY2NvcmRpbmcgc29tZSAoZGlzKXNpbWlsYXJpdHkgbWVhc3VyZS4gSW4gUiBzb2Z0d3JhcmUsIHRoZSBFdWNsaWRlYW4gZGlzdGFuY2UgaXMgdXNlZCBieSBkZWZhdWx0IHRvIG1lYXN1cmUgdGhlIGRpc3NpbWlsYXJpdHk/YmV0d2VlbiBlYWNoIHBhaXIgb2Ygb2JzZXJ2YXRpb25zLg0KDQpUdCdzIGVhc3kgdG8gY29tcHV0ZSBkaXNzaW1pbGFyaXR5IG1lYXN1cmUgYmV0d2VlbiB0d28gcGFpcnMgb2Ygb2JzZXJ2YXRpb25zLiBJdCdzIG1lbnRpb25lZCBhYm92ZSB0aGF0IHR3byBjbHVzdGVycyB0aGF0IGFyZSBtb3N0IHNpbWlsYXIgYXJlIGZ1c2VkIGludG8gYSBuZXcgYmlnIGNsdXN0ZXIuDQoNCkEgbmF0dXJhbCBxdWVzdGlvbiBpcyA6IEhvdyB0byBtZWFzdXJlIHRoZSBkaXM/aW1pbGFyaXR5IGJldHdlZW4gdHdvIGNsdXN0ZXJzIG9mIG9ic2VydmF0aW9ucz8NCg0KQSBudW1iZXIgb2YgZGlmZmVyZW50IGNsdXN0ZXIgYWdnbG9tZXJhdGlvbiBtZXRob2RzIChpLmUsIGxpbmthZ2UgbWV0aG9kcykgaGFzIGJlZW4gZGV2ZWxvcGVkIHRvIGFuc3dlciB0byB0aGlzIHF1ZXN0aW9uLiBUaGUgbW9zdCBjb21tb24gdHlwZXMgbWV0aG9kcyBhcmU6DQoNCg0KTWF4aW11bSBvciBjb21wbGV0ZSBsaW5rYWdlIGNsdXN0ZXJpbmc6IEl0IGNvbXB1P2VzIGFsbCBwYWlyd2lzZSBkaXNzaW1pbGFyaXRpZXMgYmV0d2VlbiB0aGUgZWxlbWVudHMgaW4gY2x1c3RlciAxIGFuZCB0aGUgZWxlbWVudHMgaW4gY2x1c3RlciAyLCBhbmQgY29uc2lkZXJzIHRoZSBsYXJnZXN0IHZhbHVlIChpLmUuLCBtYXhpbXVtIHZhbHVlKSBvZiB0aGVzZSBkaXNzaW1pbGFyaXRpZXMgYXMgdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlIHR3byBjbHVzdGVycy4gSXQgdGVuZHMgdG8gcHJvZHVjZSBtb3JlIGNvbXBhY3QgY2x1c3Q/cnMuIA0KDQpNaW5pbXVtIG9yIHNpbmdsZSBsaW5rYWdlIGNsdXN0ZXJpbmc6IEl0IGNvbXB1dGVzIGFsbCBwYWlyd2lzZSBkaXNzaW1pbGFyaXRpZXMgYmV0d2VlbiB0aGUgZWxlbWVudHMgaW4gY2x1c3RlciAxIGFuZCB0aGUgZWxlbWVudHMgaW4gY2x1c3RlciAyLCBhbmQgY29uc2lkZXJzIHRoZSBzbWFsbGVzdCBvZiB0aGVzZSBkaXNzaW1pbGFyaXRpZXMgYXMgYSBsaW5rYWdlIGNyaXRlcmlvbi4gSXQgdGVuZHMgdG8gcHJvZHVjZSBsb25nLCAibG9vP2UiIGNsdXN0ZXJzLg0KDQpNZWFuIG9yIGF2ZXJhZ2UgbGlua2FnZSBjbHVzdGVyaW5nOiBJdCBjb21wdXRlcyBhbGwgcGFpcndpc2UgZGlzc2ltaWxhcml0aWVzIGJldHdlZW4gdGhlIGVsZW1lbnRzIGluIGNsdXN0ZXIgMSBhbmQgdGhlIGVsZW1lbnRzIGluIGNsdXN0ZXIgMiwgYW5kIGNvbnNpZGVycyB0aGUgYXZlcmFnZSBvZiB0aGVzZSBkaXNzaW1pbGFyaXRpZXMgYXMgdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlIHR3byBjbHVzdGVycy4NCg0KQ29tcGxlP2UgbGlua2FnZSBhbmQgV2FyZCdzIG1ldGhvZCBhcmUgZ2VuZXJhbGx5IHByZWZlcnJlZC4NCg0KQ2VudHJvaWQgbGlua2FnZSBjbHVzdGVyaW5nOiBJdCBjb21wdXRlcyB0aGUgZGlzc2ltaWxhcml0eSBiZXR3ZWVuIHRoZSBjZW50cm9pZCBmb3IgY2x1c3RlciAxIChhIG1lYW4gdmVjdG9yIG9mIGxlbmd0aCBwIHZhcmlhYmxlcykgYW5kIHRoZSBjZW50cm9pZCBmb3IgY2x1c3RlciAyLg0KDQpXYXJkJ3MgbWluaW11bSB2YXJpYW5jZSBtZXRob2Q6IEl0IG1pP2ltaXplcyB0aGUgdG90YWwgd2l0aGluLWNsdXN0ZXIgdmFyaWFuY2UuIEF0IGVhY2ggc3RlcCB0aGUgcGFpciBvZiBjbHVzdGVycyB3aXRoIG1pbmltdW0gYmV0d2Vlbi1jbHVzdGVyIGRpc3RhbmNlIGFyZSBtZXJnZWQuDQoNCiMgRGF0YSBwcmVwYXJhdGlvbiBhbmQgZGVzY3JpcHRpdmUgc3RhdGlzdGljcw0KUiBkYXRhc2V0IFVTQXJyZXN0IHdoaWNoIGNvbnRhaW5zIHN0YXRpc3RpY3MsIGluIGFycmVzdHMgcGVyIDEwMCwwMDAgcmVzaWRlbnRzIGZvciA/c3NhdWx0LCBtdXJkZXIsIGFuZCByYXBlIGluIGVhY2ggb2YgdGhlIDUwIFVTIHN0YXRlcyBpbiAxOTczLiBJdCBpbmNsdWRlcyBhbHNvIHRoZSBwZXJjZW50IG9mIHRoZSBwb3B1bGF0aW9uIGxpdmluZyBpbiB1cmJhbiBhcmVhcy4NCg0KSXQgY29udGFpbnMgNTAgb2JzZXJ2YXRpb25zIG9uIDQgdmFyaWFibGVzOg0KDQpbLDFdIE11cmRlciBudW1lcmljIE11cmRlciBhcnJlc3RzIChwZXIgMTAwLDAwMCkNClssMl0gQXNzYXVsdCBudW1lcmljIEFzc2F1bHQgP3JyZXN0cyAocGVyIDEwMCwwMDApDQpbLDNdIFVyYmFuUG9wIG51bWVyaWMgUGVyY2VudCB1cmJhbiBwb3B1bGF0aW9uDQpbLDRdIFJhcGUgbnVtZXJpYyBSYXBlIGFycmVzdHMgKHBlciAxMDAsMDAwKQ0KDQoNCmBgYHtyfQ0KIyBMb2FkIHRoZSBkYXRhIHNldA0KZGF0YSgiVVNBcnJlc3RzIikNCg0KIyBSZW1vdmUgYW55IG1pc3NpbmcgdmFsdWUgKGkuZSwgTkEgdmFsdWVzIGZvciBub3QgYXZhaWxhYmxlKQ0KIyBUaGF0IG1pZ2h0IGJlIHByZXNlbnQgaW4gdGhlIGRhP2ENCmRmIDwtIG5hLm9taXQoVVNBcnJlc3RzKQ0KDQojIFZpZXcgdGhlIGZpcnQgNiByb3dzIG9mIHRoZSBkYXRhDQpoZWFkKGRmLCBuID0gNikNCmBgYA0KIyMjIEJlZm9yZSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZywgd2UgY2FuIGNvbXB1dGUgc29tZSBkZXNjcmlwdGl2ZSBzdGF0aXN0aWNzOg0KDQoNCmBgYHtyfQ0KDQpkZXNjX3N0YXRzIDwtIGRhdGEuZnJhbWUoDQogIE1pbiA9IGFwcGx5KGRmLCAyLCBtaW4pLCAjIG1pbmltdW0NCiAgTWVkID0gYXBwbHkoZGYsIDIsP21lZGlhbiksICMgbWVkaWFuDQogIE1lYW4gPSBhcHBseShkZiwgMiwgbWVhbiksICMgbWVhbg0KICBTRCA9IGFwcGx5KGRmLCAyLCBzZCksICMgU3RhbmRhcmQgZGV2aWF0aW9uDQogIE1heCA9IGFwcGx5KGRmLCAyLCBtYXgpICMgTWF4aW11bQ0KICApDQpkZXNjX3N0YXRzIDwtIHJvdW5kKGRlc2Nfc3RhdHMsIDEpDQpoZWFkKGRlc2Nfc3RhdHMpDQoNCmBgYA0KTm90ZSB0aGF0IHRoZSB2YXJpYWJsZXMgaGF2ZSBhIGxhcmdlIGRpZmZlcmVudCBtZWFucyBhbmQgdmE/aWFuY2VzLiBUaGlzIGlzIGV4cGxhaW5lZCBieSB0aGUgZmFjdCB0aGF0IHRoZSB2YXJpYWJsZXMgYXJlIG1lYXN1cmVkIGluIGRpZmZlcmVudCB1bml0czsgTXVyZGVyLCBSYXBlLCBhbmQgQXNzYXVsdCBhcmUgbWVhc3VyZWQgYXMgdGhlIG51bWJlciBvZiBvY2N1cnJlbmNlcyBwZXIgMTAwIDAwMCBwZW9wbGUsIGFuZCBVcmJhblBvcCBpcyB0aGUgcGVyY2VudGFnZSBvZiB0aGUgc3RhdGUncyBwb3B1bGF0aW9uIHRoYXQgbGl2ZXMgaW4gYW4gdXJiYT8gYXJlYS4NCg0KVGhleSBtdXN0IGJlIHN0YW5kYXJkaXplZCAoaS5lLiwgc2NhbGVkKSB0byBtYWtlIHRoZW0gY29tcGFyYWJsZS4gUmVjYWxsIHRoYXQsIHN0YW5kYXJkaXphdGlvbiBjb25zaXN0cyBvZiB0cmFuc2Zvcm1pbmcgdGhlIHZhcmlhYmxlcyBzdWNoIHRoYXQgdGhleSBoYXZlIG1lYW4gemVybyBhbmQgc3RhbmRhcmQgZGV2aWF0aW9uIG9uZS4NCiANCmBgYHtyfQ0KZGYgPC0gc2NhbGUoZGYpDQpoZWFkKGRmKQ0KcHJpbnQoJ0xvb2sgQCB0aGlzIGhlYT8nKQ0KYGBgDQoNCiMjIFIgZnVuY3Rpb25zIGZvciBoaWVyYXJjaGljYWwgY2x1c3RlcmluZw0KVGhlcmUgYXJlIGRpZmZlcmVudCBmdW5jdGlvbnMgYXZhaWxhYmxlIGluIFIgZm9yIGNvbXB1dGluZyBoaWVyYXJjaGljYWwgY2x1c3RlcmluZy4gVGhlIGNvbW1vbmx5IHVzZWQgZnVuY3Rpb25zIGFyZToNCg0KaGNsdXN0KCkgW2luIHN0YXRzIHBhY2thZ2VdIGFuZCBhZ25lcygpIFtpbiBjbHVzdGVyIHBhY2thZ2VdIGZvciBhZ2dsb21lcmF0aXZlIGhpZXJhcmNoP2NhbCBjbHVzdGVyaW5nIChIQykNCmRpYW5hKCkgW2luIGNsdXN0ZXIgcGFja2FnZV0gZm9yIGRpdmlzaXZlIEhDDQojIyMjIGhjbHVzdCgpIGZ1bmN0aW9uDQpoY2x1c3QoKSBpcyB0aGUgYnVpbHQtaW4gUiBmdW5jdGlvbiBbaW4gc3RhdHMgcGFja2FnZV0gZm9yIGNvbXB1dGluZyBoaWVyYXJjaGljYWwgY2x1c3RlcmluZy4NCg0KVGhlIHNpbXBsaWZpZWQgZm9ybWF0IGlzOg0KDQpoY2x1c3QoZCwgbWV0aG9kID0gImNvbXBsZXRlIikNCg0KZCBhIGRpc3NpbWlsYXI/dHkgc3RydWN0dXJlIGFzIHByb2R1Y2VkIGJ5IHRoZSBkaXN0KCkgZnVuY3Rpb24uDQptZXRob2Q6IFRoZSBhZ2dsb21lcmF0aW9uIG1ldGhvZCB0byBiZSB1c2VkLiBBbGxvd2VkIHZhbHVlcyBpcyBvbmUgb2YgIndhcmQuRCIsICJ3YXJkLkQyIiwgInNpbmdsZSIsICJjb21wbGV0ZSIsICJhdmVyYWdlIiwgIm1jcXVpdHR5IiwgIm1lZGlhbiIgb3IgImNlbnRyb2lkIi4NCg0KDQpUaGUgZGlzdCgpIGZ1bmN0aW9uIGlzIHVzZWQgdG8gY29tcHV0ZSB0aGUgRXU/bGlkZWFuIGRpc3RhbmNlIGJldHdlZW4gb2JzZXJ2YXRpb25zLiBGaW5hbGx5LCBvYnNlcnZhdGlvbnMgYXJlIGNsdXN0ZXJlZCB1c2luZyBXYXJkJ3MgbWV0aG9kLg0KDQpgYGB7cn0NCiMgRGlzc2ltaWxhcml0eSBtYXRyaXgNCmQgPC0gZGlzdChkZiwgbWV0aG9kID0gImV1Y2xpZGVhbiIpDQoNCg0KIyBIaWVyYXJjaGljYWwgY2x1c3RlcmluZyB1c2luZyBXYXJkJ3MgbWV0aG9kDQpyZXMuaGMgPC0gaGNsdXN0KGQsIG1ldGhvZCA9ICJ3YXJkLkQyIiApDQojIFBsbz8gdGhlIG9idGFpbmVkIGRlbmRyb2dyYW0NCnBsb3QocmVzLmhjLCBjZXggPSAwLjYsIGhhbmcgPSAtMSkNCg0KYGBgDQojIGFnbmVzKCkgYW5kIGRpYW5hKCkgZnVuY3Rpb25zDQpUaGUgUiBmdW5jdGlvbiBhZ25lcygpIFtpbiBjbHVzdGVyIHBhY2thZ2VdIGNhbiBiZSBhbHNvIHVzZWQgdG8gY29tcHV0ZSBhZ2dsb21lcmF0aXZlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nLiBUaGUgUiBmdW5jdGlvbiBkaWFuYSgpIFsgaW4gY2x1c3RlciBwYWNrYWdlIF0gaXM/YW4gZXhhbXBsZSBvZiBkaXZpc2l2ZSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZy4NCg0KIyMjIEFnZ2xvbWVyYXRpdmUgTmVzdGluZyAoSGllcmFyY2hpY2FsIENsdXN0ZXJpbmcpDQphZ25lcyh4LCBtZXRyaWMgPSAiZXVjbGlkZWFuIiwgc3RhbmQgPSBGQUxTRSwgbWV0aG9kID0gImF2ZXJhZ2UiKQ0KDQojIyMgREl2aXNpdmUgQU5BbHlzaXMgQ2x1c3RlcmluZw0KZGlhbmEoeCwgbWV0cmljID0gImV1Y2xpZGVhbiIsIHN0YW5kID0gRkFMU0UpDQoNCng6IGRhdGEgP2F0cml4IG9yIGRhdGEgZnJhbWUgb3IgZGlzc2ltaWxhcml0eSBtYXRyaXguIEluIGNhc2Ugb2YgbWF0cml4IGFuZCBkYXRhIGZyYW1lLCByb3dzIGFyZSBvYnNlcnZhdGlvbnMgYW5kIGNvbHVtbnMgYXJlIHZhcmlhYmxlcy4gSW4gY2FzZSBvZiBhIGRpc3NpbWlsYXJpdHkgbWF0cml4LCB4IGlzIHR5cGljYWxseSB0aGUgb3V0cHV0IG9mIGRhaXN5KCkgb3IgZGlzdCgpLg0KbWV0cmljOiB0aGUgbWV0cmljIHRvIGJlIHVzZWQgZm9yIGNhbGN1bGF0aW5nP2Rpc3NpbWlsYXJpdGllcyBiZXR3ZWVuIG9ic2VydmF0aW9ucy4gUG9zc2libGUgdmFsdWVzIGFyZSAiZXVjbGlkZWFuIiBhbmQgIm1hbmhhdHRhbiIuDQpzdGFuZDogaWYgVFJVRSwgdGhlbiB0aGUgbWVhc3VyZW1lbnRzIGluIHggYXJlIHN0YW5kYXJkaXplZCBiZWZvcmUgY2FsY3VsYXRpbmcgdGhlIGRpc3NpbWlsYXJpdGllcy4gTWVhc3VyZW1lbnRzIGFyZSBzdGFuZGFyZGl6ZWQgZm9yIGVhY2ggdmFyaWFibGUgKGNvbHVtbiksIGJ5IHN1YnRyYWN0P25nIHRoZSB2YXJpYWJsZSdzIG1lYW4gdmFsdWUgYW5kIGRpdmlkaW5nIGJ5IHRoZSB2YXJpYWJsZSdzIG1lYW4gYWJzb2x1dGUgZGV2aWF0aW9uDQptZXRob2Q6IFRoZSBjbHVzdGVyaW5nIG1ldGhvZC4gUG9zc2libGUgdmFsdWVzIGluY2x1ZGVzICJhdmVyYWdlIiwgInNpbmdsZSIsICJjb21wbGV0ZSIsICJ3YXJkIi4NCg0KDQpUaGUgZnVuY3Rpb24gYWduZXMoKSByZXR1cm5zIGFuIG9iamVjdCBvZiBjbGFzcyAiYWduZXMiIChzZWUgP2FnbmVzLm9iamVjPykgd2hpY2ggaGFzIG1ldGhvZHMgZm9yIHRoZSBmdW5jdGlvbnM6IHByaW50KCksIHN1bW1hcnkoKSwgcGxvdCgpLCBwbHRyZWUoKSwgYXMuZGVuZHJvZ3JhbSgpLCBhcy5oY2x1c3QoKSBhbmQgY3V0cmVlKCkuDQpUaGUgZnVuY3Rpb24gZGlhbmEoKSByZXR1cm5zIGFuIG9iamVjdCBvZiBjbGFzcyAiZGlhbmEiIChzZWUgP2RpYW5hLm9iamVjdCkgd2hpY2ggaGFzIGFsc28gbWV0aG9kcyBmb3IgdGhlIGZ1bmN0aW9uczogcHJpbnQoKSwgc3VtbWFyeSgpPyBwbG90KCksIHBsdHJlZSgpLCBhcy5kZW5kcm9ncmFtKCksIGFzLmhjbHVzdCgpIGFuZCBjdXRyZWUoKS4NCkNvbXBhcmVkIHRvIG90aGVyIGFnZ2xvbWVyYXRpdmUgY2x1c3RlcmluZyBtZXRob2RzIHN1Y2ggYXMgaGNsdXN0KCksIGFnbmVzKCkgaGFzIHRoZSBmb2xsb3dpbmcgZmVhdHVyZXM6DQoNCkl0IHlpZWxkcyB0aGUgYWdnbG9tZXJhdGl2ZSBjb2VmZmljaWVudCAoc2VlIGFnbmVzLm9iamVjdCkgd2hpY2ggbWVhc3VyZXMgdGhlIGFtb3VudCBvZiA/bHVzdGVyaW5nIHN0cnVjdHVyZSBmb3VuZA0KQXBhcnQgZnJvbSB0aGUgdXN1YWwgdHJlZSBpdCBhbHNvIHByb3ZpZGVzIHRoZSBiYW5uZXIsIGEgbm92ZWwgZ3JhcGhpY2FsIGRpc3BsYXkgKHNlZSBwbG90LmFnbmVzKS4NCmBgYHtyfQ0KbGlicmFyeSgiY2x1c3RlciIpDQojIENvbXB1dGUgYWduZXMoKQ0KcmVzLmFnbmVzIDwtIGFnbmVzKGRmLCBtZXRob2QgPSAid2FyZCIpDQojIEFnZ2xvbWVyYXRpdmUgY29lZmZpY2llbnQNCnJlcy5hZ25lcyRhYw0KYGBgDQpgYD97cn0NCiMgUGxvdCB0aGUgdHJlZSB1c2luZyBwbHRyZWUoKQ0KcGx0cmVlKHJlcy5hZ25lcywgY2V4ID0gMC42LCBoYW5nID0gLTEsIG1haW4gPSAiRGVuZHJvZ3JhbSBvZiBBZ25lcyIpIA0KcHJpbnQoJ0RvbmUnKQ0KYGBgDQpgYGB7cn0NCnBsdHJlZShyZXMuYWduZXMsIGNleCA9IDAuNiwgaGFuZyA9IC0xLCBtYWluID0gIkRlbmRyb2dyYW0gb2YgQWduZXMiKSANCmBgYA0KDQojIyMjIEl0J3MgYWxzbyBwb3NzaWJsZSB0byBkcmF3IEFHTkVTIGRlbmRyb2dyYW0gP3NpbmcgdGhlIGZ1bmN0aW9uIHBsb3QuaGNsdXN0KCkgYW5kIHRoZSBmdW5jdGlvbiBwbG90LmRlbmRyb2dyYW0oKSBhcyBmb2xsb3c6DQoNCmBgYHtyfQ0KIyBwbG90LmhjbHVzdCgpDQpwbG90KGFzLmhjbHVzdChyZXMuYWduZXMpLCBjZXggPSAwLjYsIGhhbmcgPSAtMSkNCg0KYGBgDQpwbG90LmRlbmRyb2dyYW0oKQ0KYGBge3J9DQojIHBsb3QuZGVuZHJvZ3JhbSgpDQpwbG90KGFzLmRlbmRyb2dyYW0ocmVzLmFnbmVzKSwgY2V4ID0gMC42LCANCiAgICAgaG9yaXogPT9UUlVFKQ0KYGBgDQojIyBESUFOQQ0KYGBge3J9DQojIENvbXB1dGUgZGlhbmEoKQ0KcmVzLmRpYW5hIDwtIGRpYW5hKGRmKQ0KIyBQbG90IHRoZSB0cmVlDQpwbHRyZWUocmVzLmRpYW5hLCBjZXggPSAwLjYsIGhhbmcgPSAtMSwNCiAgICAgICBtYWluID0gIkRlbmRyb2dyYW0gb2YgRGlhbmEiKQ0KYGBgDQoNCg0K