Data 612 - Project 2
Emmanuel Hayble-Gomes
06/16/2020
0.1 Introduction
The goal of this assignment is for you to try out different ways of implementing and configuring a recommender, and to evaluate your different approaches.
For assignment 2, start with an existing dataset of user-item ratings, such as our toy books dataset, MovieLens, Jester [http://eigentaste.berkeley.edu/dataset/] or another dataset of your choosing. Implement at least two of these recommendation algorithms:
• Content-Based Filtering • User-User Collaborative Filtering • Item-Item Collaborative Filtering
0.1.1 Assignment Highlights
As an example of implementing a Content-Based recommender, you could build item profiles for a subset of MovieLens movies from scraping http://www.imdb.com/ or using the API at https://www.omdbapi.com/ (which has very recently instituted a small monthly fee). A more challenging method would be to pull movie summaries or reviews and apply tf-idf and/or topic modeling.
You should evaluate and compare different approaches, using different algorithms, normalization techniques, similarity methods, neighborhood sizes, etc. You don’t need to be exhaustive—these are just some suggested possibilities.
You may use the course text’s recommenderlab or any other library that you want. Please provide at least one graph, and a textual summary of your findings and recommendations.
0.1.2 About the Data
The MovieLens Latest Small Datasets contain 100,000 ratings and 3,600 tag applications applied to 9,000 movies by 600 users.
0.1.3 Loading the MovieLense Data
## [1] "data" "normalize"## [1] "realRatingMatrix"
## attr(,"package")
## [1] "recommenderlab"## [1] 943 16640.1.4 Data structure
## Formal class 'realRatingMatrix' [package "recommenderlab"] with 2 slots
## ..@ data :Formal class 'dgCMatrix' [package "Matrix"] with 6 slots
## .. .. ..@ i : int [1:99392] 0 1 4 5 9 12 14 15 16 17 ...
## .. .. ..@ p : int [1:1665] 0 452 583 673 882 968 994 1386 1605 1904 ...
## .. .. ..@ Dim : int [1:2] 943 1664
## .. .. ..@ Dimnames:List of 2
## .. .. .. ..$ : chr [1:943] "1" "2" "3" "4" ...
## .. .. .. ..$ : chr [1:1664] "Toy Story (1995)" "GoldenEye (1995)" "Four Rooms (1995)" "Get Shorty (1995)" ...
## .. .. ..@ x : num [1:99392] 5 4 4 4 4 3 1 5 4 5 ...
## .. .. ..@ factors : list()
## ..@ normalize: NULL0.1.5 Exploring the ratings values
ratingvalues <- as.vector(MovieLense@data)
unique(ratingvalues) # The rating is numeric with the least value as 0.5 and the highest values as 5.## [1] 5 4 0 3 1 2## ratingvalues
## 0 1 2 3 4 5
## 1469760 6059 11307 27002 33947 210770.1.6 Excluding the missing values
0.1.7 Distribution of the Ratings
hist(ratingvalues,
breaks = 6,
main="Distribution of Ratings",
xlab="Ratings",
col="pink",
freq=TRUE
)
0.1.8 Pre-processing
Convert data to numeric
0.1.9 Create the sparse Matrix
ratingsMat <- sparseMatrix(i = movies$user, j = movies$item, x = movies$rating,
dims = c(length(unique(movies$user)), length(unique(movies$item))),
dimnames = list(paste("u", 1:length(unique(movies$user)), sep = ""),
paste("m", 1:length(unique(movies$item)), sep = "")))
ratingsReal <- new("realRatingMatrix", data = ratingsMat)
ratingsReal## 943 x 1664 rating matrix of class 'realRatingMatrix' with 99392 ratings.I’m selecting the Users who have rated at least 100 movies and those movies that have been watched at least 150 times
0.2 Create Training and Testing sets
Use 80% for training and 20% for testing the model
Prepare training dataset
Prepare testing set
0.3 User-User Collaborative Filtering
The User based collaborative filtering algorithms are based on measuring the similarity between users. A “Recommender” object is then given the “UBCF” (User-based collaborative filter), with a center normalization, cosine method, with 25 nearest neighbors.But first, I will compute the similarity matrix.
0.3.1 Similarity Matrix
A similarity matrix is a recommenderlab function that takes the “realRatingMatrix”" and calculates a cosine similarity which aids in the investigation of model development.
similarityUsers <- similarity(MovieLense[1:4, ], method = "cosine", which = "users")
image(as.matrix(similarityUsers), main = "Users similarity")
0.3.2 The User Based Model
Building the User Based Model using 25 nearest neighbor. Building the user collaborative filtering system to recommend movies to users based on how similar they are with other users.
0.3.3 Making Predictions with newdata = test
usermodelprediction <- predict(object = usermodel, newdata = test, type="ratings")
as(usermodelprediction, "matrix")[, 1:4] %>% kable() %>% kable_styling(full_width = T)| Toy Story (1995) | Get Shorty (1995) | Twelve Monkeys (1995) | Babe (1995) | |
|---|---|---|---|---|
| 22 | 3.781925 | NA | 4.138567 | 4.021311 |
| 44 | NA | 3.782291 | NA | 4.023630 |
| 57 | NA | 3.627189 | NA | NA |
| 58 | NA | 4.108803 | NA | NA |
| 60 | 4.221428 | 3.945063 | NA | NA |
| 70 | NA | 3.793470 | 3.952004 | NA |
| 82 | NA | 3.422929 | NA | NA |
| 85 | 3.619038 | 3.626235 | 3.499749 | NA |
| 99 | NA | NA | NA | 3.871983 |
| 125 | NA | 3.731686 | 3.886966 | NA |
| 128 | NA | 3.650993 | 3.679047 | 3.793576 |
| 141 | NA | 3.810379 | NA | 4.045046 |
| 151 | NA | NA | NA | 4.137262 |
| 158 | NA | NA | NA | NA |
| 181 | NA | 2.218023 | NA | 2.823249 |
| 201 | NA | NA | NA | NA |
| 207 | 3.455511 | NA | 3.405310 | NA |
| 221 | 3.818030 | NA | NA | 3.654129 |
| 224 | 3.736582 | 3.438769 | 3.720914 | 3.593943 |
| 239 | 4.341020 | 3.808810 | 4.136243 | NA |
| 250 | NA | 3.651374 | NA | 3.902230 |
| 264 | 4.467544 | NA | NA | 4.751885 |
| 279 | NA | NA | NA | 3.717380 |
| 280 | NA | NA | NA | NA |
| 293 | NA | NA | NA | NA |
| 296 | NA | 4.130021 | NA | 4.468650 |
| 298 | NA | 4.056455 | 4.208806 | NA |
| 299 | NA | NA | NA | 3.654436 |
| 301 | NA | NA | NA | NA |
| 305 | NA | 3.305570 | NA | 3.419887 |
| 313 | NA | 3.680840 | 3.791153 | NA |
| 314 | NA | 3.994760 | NA | NA |
| 328 | 3.818877 | NA | NA | NA |
| 334 | 3.263622 | NA | NA | NA |
| 339 | NA | NA | NA | 4.164154 |
| 345 | NA | NA | 4.048610 | 4.209362 |
| 346 | 3.777548 | NA | NA | 3.867273 |
| 379 | NA | NA | NA | NA |
| 387 | NA | NA | NA | NA |
| 393 | NA | NA | NA | NA |
| 398 | NA | NA | 3.760041 | NA |
| 399 | NA | 2.777281 | 3.128807 | NA |
| 401 | NA | 2.865687 | 3.052007 | 3.014357 |
| 407 | NA | NA | NA | NA |
| 417 | NA | NA | NA | 3.789563 |
| 442 | 3.607058 | 3.372064 | NA | 3.424742 |
| 455 | NA | NA | NA | NA |
| 493 | NA | 4.044486 | NA | 4.197289 |
| 496 | 3.019448 | 3.101432 | NA | 3.207622 |
| 505 | NA | 3.155593 | NA | 3.402737 |
| 535 | NA | NA | NA | NA |
| 536 | NA | 4.033887 | 4.053168 | NA |
| 567 | NA | 3.627711 | NA | 3.922535 |
| 592 | NA | NA | NA | NA |
| 617 | 3.172960 | 2.634722 | NA | 2.645739 |
| 630 | NA | 3.412451 | NA | 3.716795 |
| 639 | 3.015679 | 2.709074 | 2.865973 | 2.869516 |
| 650 | NA | NA | NA | 3.628631 |
| 659 | 3.990956 | NA | NA | 3.882698 |
| 694 | 4.531028 | 4.175881 | 4.349192 | 4.409131 |
| 711 | 3.882092 | 3.654377 | 3.873608 | NA |
| 715 | NA | NA | NA | 3.872303 |
| 733 | NA | 2.980552 | NA | 3.257285 |
| 748 | NA | NA | NA | NA |
| 825 | 3.953589 | 3.890185 | NA | 4.216666 |
| 870 | NA | NA | NA | 3.984096 |
| 881 | NA | NA | NA | NA |
| 883 | NA | NA | NA | NA |
| 889 | NA | NA | NA | NA |
| 890 | NA | 4.071963 | NA | 4.163947 |
| 894 | NA | 3.590505 | NA | 3.727390 |
| 899 | NA | 3.656421 | 3.693090 | NA |
| 932 | NA | 4.026150 | NA | 4.079013 |
| 938 | NA | 3.262872 | NA | 3.671855 |
0.4 Model Evaluation - User Based
scheme <- evaluationScheme(ratings, method="cross-validation",
k = 4,
given = 10,
goodRating = 4)
results <- evaluate(x = scheme, method = "UBCF", n=c(10,25,50,75,100))## UBCF run fold/sample [model time/prediction time]
## 1 [0.01sec/0.25sec]
## 2 [0sec/0.4sec]
## 3 [0sec/0.14sec]
## 4 [0sec/0.17sec]## TP FP FN TN precision recall TPR
## 10 4.439560 5.56044 48.96703 131.03297 0.4439560 0.08509718 0.08509718
## 25 9.769231 15.23077 43.63736 121.36264 0.3907692 0.18431378 0.18431378
## 50 17.824176 32.17582 35.58242 104.41758 0.3564835 0.33441705 0.33441705
## 75 26.186813 48.81319 27.21978 87.78022 0.3491575 0.49445469 0.49445469
## 100 33.780220 66.21978 19.62637 70.37363 0.3378022 0.63791011 0.63791011
## FPR
## 10 0.03969298
## 25 0.10943232
## 50 0.23236638
## 75 0.35363671
## 100 0.48105204The TPR is the percentage of the movies that have been purchased and was recommended while the FPR is the percentage of the movies that was not purchased but was recommended with n as the number of recommendations (10,25,50,75,100).
ROC Curve Plot
The precision and recall shows the percentage of movies that have been purchased and the percentage of movies that was recommended.
0.5 item-item Collaborative Filtering
The Item based collaborative filtering algorithms are based on measuring the similarity between items A “Recommender” object is then given the “IBCF” (Item-based collaborative filter), with a center normalization, cosine method, with K = 250.But first, I will compute the similarity matrix.
0.5.1 Similarity Matrix
A similarity matrix is a recommenderlab function that takes the “realRatingMatrix”" and calculates a cosine similarity which aids in the investigation of model development.
similarityitems <- similarity(MovieLense[, 1:4], method = "cosine", which = "items")
image(as.matrix(similarityitems), main = "Items similarity")
The diagonal is yellow because it’s comparing each items with itself.
0.5.2 The Item Based Model
Building the item-item collaborative filtering system to recommend movies to users where their item’s ratings are similar.
0.5.3 Making Predictions with newdata = test
itemmodelprediction <- predict(object = itemmodel, newdata = test, type="ratings")
as(itemmodelprediction, "matrix")[, 1:4] %>% kable() %>% kable_styling(full_width = T)| Toy Story (1995) | Get Shorty (1995) | Twelve Monkeys (1995) | Babe (1995) | |
|---|---|---|---|---|
| 22 | 4.283615 | NA | 4.147702 | 4.102685 |
| 44 | NA | 3.901811 | NA | 3.850054 |
| 57 | NA | 3.878747 | NA | NA |
| 58 | NA | 4.181955 | NA | NA |
| 60 | 3.966626 | 4.110938 | NA | NA |
| 70 | NA | 3.750311 | 3.547979 | NA |
| 82 | NA | 3.106853 | NA | NA |
| 85 | 3.644796 | 3.620886 | 3.614051 | NA |
| 99 | NA | NA | NA | 3.614084 |
| 125 | NA | 3.624266 | 3.424463 | NA |
| 128 | NA | 3.740166 | 3.722324 | 3.692069 |
| 141 | NA | 3.731692 | NA | 4.409189 |
| 151 | NA | NA | NA | 4.061031 |
| 158 | NA | NA | NA | NA |
| 181 | NA | 1.993500 | NA | 2.399475 |
| 201 | NA | NA | NA | NA |
| 207 | 3.419416 | NA | 3.197713 | NA |
| 221 | 3.827299 | NA | NA | 4.011960 |
| 224 | 3.597986 | 3.671785 | 3.440014 | 3.382952 |
| 239 | 3.518356 | 4.245348 | 4.183181 | NA |
| 250 | NA | 3.699032 | NA | 3.692559 |
| 264 | 4.284696 | NA | NA | 4.286974 |
| 279 | NA | NA | NA | 3.467185 |
| 280 | NA | NA | NA | NA |
| 293 | NA | NA | NA | NA |
| 296 | NA | 3.986218 | NA | 4.514032 |
| 298 | NA | 4.174220 | 3.995286 | NA |
| 299 | NA | NA | NA | 3.886759 |
| 301 | NA | NA | NA | NA |
| 305 | NA | 3.303163 | NA | 3.673859 |
| 313 | NA | 3.985239 | 3.751861 | NA |
| 314 | NA | 4.034791 | NA | NA |
| 328 | 3.802414 | NA | NA | NA |
| 334 | 3.410970 | NA | NA | NA |
| 339 | NA | NA | NA | 4.126004 |
| 345 | NA | NA | 3.671957 | 3.942133 |
| 346 | 3.787034 | NA | NA | 3.900648 |
| 379 | NA | NA | NA | NA |
| 387 | NA | NA | NA | NA |
| 393 | NA | NA | NA | NA |
| 398 | NA | NA | 4.077610 | NA |
| 399 | NA | 3.307224 | 3.072430 | NA |
| 401 | NA | 3.315413 | 3.040033 | 3.186588 |
| 407 | NA | NA | NA | NA |
| 417 | NA | NA | NA | 3.536884 |
| 442 | 3.297734 | 3.341717 | NA | 3.457097 |
| 455 | NA | NA | NA | NA |
| 493 | NA | 3.866104 | NA | 3.987802 |
| 496 | 3.067049 | 2.859318 | NA | 3.103866 |
| 505 | NA | 3.476801 | NA | 3.799254 |
| 535 | NA | NA | NA | NA |
| 536 | NA | 4.222383 | 3.752575 | NA |
| 567 | NA | 4.048823 | NA | 3.917836 |
| 592 | NA | NA | NA | NA |
| 617 | 2.509773 | 2.866630 | NA | 3.201489 |
| 630 | NA | 3.711334 | NA | 3.562731 |
| 639 | 3.033611 | 2.554343 | 2.593819 | 3.139381 |
| 650 | NA | NA | NA | 3.695807 |
| 659 | 3.739144 | NA | NA | 3.997772 |
| 694 | 4.320639 | 4.305813 | 4.174105 | 4.320125 |
| 711 | 4.056210 | 3.968443 | 3.703726 | NA |
| 715 | NA | NA | NA | 3.547479 |
| 733 | NA | 2.907816 | NA | 3.196125 |
| 748 | NA | NA | NA | NA |
| 825 | 4.006931 | 4.026326 | NA | 4.109223 |
| 870 | NA | NA | NA | 3.706447 |
| 881 | NA | NA | NA | NA |
| 883 | NA | NA | NA | NA |
| 889 | NA | NA | NA | NA |
| 890 | NA | 4.019789 | NA | 4.144436 |
| 894 | NA | 3.859504 | NA | 3.634725 |
| 899 | NA | 3.799083 | 3.530526 | NA |
| 932 | NA | 3.959724 | NA | 4.251144 |
| 938 | NA | 2.888139 | NA | 3.363482 |
0.6 Model Evaluation - Item Based
scheme <- evaluationScheme(ratings, method="cross-validation",
k = 4,
given = 10,
goodRating = 4)
results2 <- evaluate(x = scheme, method = "IBCF", n=c(10,25,50,75,100))## IBCF run fold/sample [model time/prediction time]
## 1 [0.19sec/0.06sec]
## 2 [0.19sec/0.04sec]
## 3 [0.38sec/0.05sec]
## 4 [0.17sec/0.05sec]## TP FP FN TN precision recall TPR
## 10 3.153846 6.846154 46.65934 133.34066 0.3153846 0.06206133 0.06206133
## 25 7.043956 17.890110 42.76923 122.29670 0.2824523 0.14217212 0.14217212
## 50 13.351648 36.307692 36.46154 103.87912 0.2688259 0.26777350 0.26777350
## 75 19.516484 54.714286 30.29670 85.47253 0.2634008 0.39374833 0.39374833
## 100 25.703297 72.252747 24.10989 67.93407 0.2634209 0.51552199 0.51552199
## FPR
## 10 0.04846687
## 25 0.12718102
## 50 0.25850890
## 75 0.38986228
## 100 0.51441433The TPR is the percentage of the movies that have been purchased and was recommended while the FPR is the percentage of the movies that was not purchased but was recommended with n as the number of recommendations (2,4,6,8,10,50).
ROC Curve Plot
0.6.1 Conclusion
The precision and recall for the User Based Recommender system shows the percentage of Movies that have been purchased and the percentage of Movies that was recommended. We can see that 10 movies were purchased 42% of the time while 100 movies were recommended 61% of the time.
On the other hand, the precision and recall for the Item Based Recommender system also shows the percentage of Movies that have been purchased and the percentage of Movies that was recommended. We can also see that 10 movies were purchased 36% of the time while 100 movies were recommended 50% of the time.
References
Kohavi, Ron (1995). “A study of cross-validation and bootstrap for accuracy estimation and model selection”. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pp. 1137-1143.
Breese JS, Heckerman D, Kadie C (1998). “Empirical Analysis of Predictive Algorithms for Collaborative Filtering.” In Uncertainty in Artificial Intelligence. Proceedings of the Fourteenth Conference, pp. 43-52.
LS0tDQp0aXRsZTogIkRhdGEgNjEyIC0gUHJvamVjdCAyIg0KYXV0aG9yOiBFbW1hbnVlbCBIYXlibGUtR29tZXMNCmRhdGU6ICIwNi8xNi8yMDIwIg0Kb3V0cHV0Og0KICBodG1sX2RvY3VtZW50Og0KICAgIGNvZGVfZG93bmxvYWQ6IHllcw0KICAgIGNvZGVfZm9sZGluZzogaGlkZQ0KICAgIGhpZ2hsaWdodDogcHlnbWVudHMNCiAgICBudW1iZXJfc2VjdGlvbnM6IHllcw0KICAgIHRoZW1lOiBmbGF0bHkNCiAgICB0b2M6IHllcw0KICAgIHRvY19mbG9hdDogeWVzDQogIHBkZl9kb2N1bWVudDoNCiAgICB0b2M6IHllcw0KLS0tDQoNCiMjIEludHJvZHVjdGlvbg0KDQpUaGUgZ29hbCBvZiB0aGlzIGFzc2lnbm1lbnQgaXMgZm9yIHlvdSB0byB0cnkgb3V0IGRpZmZlcmVudCB3YXlzIG9mIGltcGxlbWVudGluZyBhbmQgY29uZmlndXJpbmcgYSByZWNvbW1lbmRlciwgYW5kIHRvIGV2YWx1YXRlIHlvdXIgZGlmZmVyZW50IGFwcHJvYWNoZXMuDQoNCkZvciBhc3NpZ25tZW50IDIsIHN0YXJ0IHdpdGggYW4gZXhpc3RpbmcgZGF0YXNldCBvZiB1c2VyLWl0ZW0gcmF0aW5ncywgc3VjaCBhcyBvdXIgdG95IGJvb2tzIGRhdGFzZXQsIE1vdmllTGVucywgSmVzdGVyIFtodHRwOi8vZWlnZW50YXN0ZS5iZXJrZWxleS5lZHUvZGF0YXNldC9dIG9yIGFub3RoZXIgZGF0YXNldCBvZiB5b3VyIGNob29zaW5nLiBJbXBsZW1lbnQgYXQgbGVhc3QgdHdvIG9mIHRoZXNlIHJlY29tbWVuZGF0aW9uIGFsZ29yaXRobXM6DQoNCuKAoiBDb250ZW50LUJhc2VkIEZpbHRlcmluZw0K4oCiIFVzZXItVXNlciBDb2xsYWJvcmF0aXZlIEZpbHRlcmluZw0K4oCiIEl0ZW0tSXRlbSBDb2xsYWJvcmF0aXZlIEZpbHRlcmluZw0KDQojIyMgQXNzaWdubWVudCBIaWdobGlnaHRzDQoNCkFzIGFuIGV4YW1wbGUgb2YgaW1wbGVtZW50aW5nIGEgQ29udGVudC1CYXNlZCByZWNvbW1lbmRlciwgeW91IGNvdWxkIGJ1aWxkIGl0ZW0gcHJvZmlsZXMgZm9yIGEgc3Vic2V0IG9mIE1vdmllTGVucyBtb3ZpZXMgZnJvbSBzY3JhcGluZyBodHRwOi8vd3d3LmltZGIuY29tLyBvciB1c2luZyB0aGUgQVBJIGF0IGh0dHBzOi8vd3d3Lm9tZGJhcGkuY29tLyAod2hpY2ggaGFzIHZlcnkgcmVjZW50bHkgaW5zdGl0dXRlZCBhIHNtYWxsIG1vbnRobHkgZmVlKS4gQSBtb3JlIGNoYWxsZW5naW5nIG1ldGhvZCB3b3VsZCBiZSB0byBwdWxsIG1vdmllIHN1bW1hcmllcyBvciByZXZpZXdzIGFuZCBhcHBseSB0Zi1pZGYgYW5kL29yIHRvcGljIG1vZGVsaW5nLg0KDQpZb3Ugc2hvdWxkIGV2YWx1YXRlIGFuZCBjb21wYXJlIGRpZmZlcmVudCBhcHByb2FjaGVzLCB1c2luZyBkaWZmZXJlbnQgYWxnb3JpdGhtcywgbm9ybWFsaXphdGlvbiB0ZWNobmlxdWVzLCBzaW1pbGFyaXR5IG1ldGhvZHMsIG5laWdoYm9yaG9vZCBzaXplcywgZXRjLiBZb3UgZG9u4oCZdCBuZWVkIHRvIGJlIGV4aGF1c3RpdmXigJR0aGVzZSBhcmUganVzdCBzb21lIHN1Z2dlc3RlZCBwb3NzaWJpbGl0aWVzLg0KDQpZb3UgbWF5IHVzZSB0aGUgY291cnNlIHRleHTigJlzIHJlY29tbWVuZGVybGFiIG9yIGFueSBvdGhlciBsaWJyYXJ5IHRoYXQgeW91IHdhbnQuDQpQbGVhc2UgcHJvdmlkZSBhdCBsZWFzdCBvbmUgZ3JhcGgsIGFuZCBhIHRleHR1YWwgc3VtbWFyeSBvZiB5b3VyIGZpbmRpbmdzIGFuZCByZWNvbW1lbmRhdGlvbnMuDQoNCg0KIyMjIEFib3V0IHRoZSBEYXRhDQoNClRoZSBNb3ZpZUxlbnMgTGF0ZXN0IFNtYWxsIERhdGFzZXRzIGNvbnRhaW4gMTAwLDAwMCByYXRpbmdzIGFuZCAzLDYwMCB0YWcgYXBwbGljYXRpb25zIGFwcGxpZWQgdG8gOSwwMDAgbW92aWVzIGJ5IDYwMCB1c2Vycy4NCg0KYGBge3IsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9DQpsaWJyYXJ5KGRwbHlyKQ0KbGlicmFyeShnZ3Bsb3QyKQ0KbGlicmFyeShrYWJsZUV4dHJhKQ0KbGlicmFyeShyZWNvbW1lbmRlcmxhYikNCmBgYA0KDQojIyMgTG9hZGluZyB0aGUgTW92aWVMZW5zZSBEYXRhDQoNCmBgYHtyfQ0KZGF0YSAoTW92aWVMZW5zZSkNCmBgYA0KDQoNCmBgYHtyfQ0Kc2xvdE5hbWVzKE1vdmllTGVuc2UpDQpjbGFzcyhNb3ZpZUxlbnNlKQ0KZGltKE1vdmllTGVuc2UpDQpgYGANCg0KIyMjIERhdGEgc3RydWN0dXJlDQoNCmBgYHtyfQ0Kc3RyKE1vdmllTGVuc2UpDQpgYGANCg0KIyMjIEV4cGxvcmluZyB0aGUgcmF0aW5ncyB2YWx1ZXMNCg0KYGBge3J9DQpyYXRpbmd2YWx1ZXMgPC0gYXMudmVjdG9yKE1vdmllTGVuc2VAZGF0YSkNCnVuaXF1ZShyYXRpbmd2YWx1ZXMpICMgVGhlIHJhdGluZyBpcyBudW1lcmljIHdpdGggdGhlIGxlYXN0IHZhbHVlIGFzIDAuNSBhbmQgdGhlIGhpZ2hlc3QgdmFsdWVzIGFzIDUuDQoNCnRhYmxlcmF0aW5nIDwtIHRhYmxlKHJhdGluZ3ZhbHVlcykNCnRhYmxlcmF0aW5nDQpgYGANCg0KIyMjIEV4Y2x1ZGluZyB0aGUgbWlzc2luZyB2YWx1ZXMNCg0KYGBge3J9DQpyYXRpbmd2YWx1ZXMgPC0gcmF0aW5ndmFsdWVzW3JhdGluZ3ZhbHVlcyAhPTBdDQpgYGANCg0KDQojIyMgRGlzdHJpYnV0aW9uIG9mIHRoZSBSYXRpbmdzDQoNCmBgYHtyfQ0KaGlzdChyYXRpbmd2YWx1ZXMsIA0KICAgICBicmVha3MgPSA2LCANCiAgICAgbWFpbj0iRGlzdHJpYnV0aW9uIG9mIFJhdGluZ3MiLA0KICAgICB4bGFiPSJSYXRpbmdzIiwNCiAgICAgY29sPSJwaW5rIiwNCiAgICAgZnJlcT1UUlVFDQogICAgICkNCmBgYA0KDQojIyMgUHJlLXByb2Nlc3NpbmcNCg0KKipDb252ZXJ0IGRhdGEgdG8gbnVtZXJpYyoqDQoNCmBgYHtyfQ0KbW92aWVzIDwtIGFzKE1vdmllTGVuc2UsICdkYXRhLmZyYW1lJykNCm1vdmllcyR1c2VyIDwtIGFzLm51bWVyaWMobW92aWVzJHVzZXIpDQptb3ZpZXMkaXRlbSA8LSBhcy5udW1lcmljKG1vdmllcyRpdGVtKQ0KYGBgDQoNCiMjIyBDcmVhdGUgdGhlIHNwYXJzZSBNYXRyaXgNCg0KYGBge3J9DQpyYXRpbmdzTWF0IDwtIHNwYXJzZU1hdHJpeChpID0gbW92aWVzJHVzZXIsIGogPSBtb3ZpZXMkaXRlbSwgeCA9IG1vdmllcyRyYXRpbmcsIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRpbXMgPSBjKGxlbmd0aCh1bmlxdWUobW92aWVzJHVzZXIpKSwgbGVuZ3RoKHVuaXF1ZShtb3ZpZXMkaXRlbSkpKSwgIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRpbW5hbWVzID0gbGlzdChwYXN0ZSgidSIsIDE6bGVuZ3RoKHVuaXF1ZShtb3ZpZXMkdXNlcikpLCBzZXAgPSAiIiksIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBwYXN0ZSgibSIsIDE6bGVuZ3RoKHVuaXF1ZShtb3ZpZXMkaXRlbSkpLCBzZXAgPSAiIikpKQ0KDQpyYXRpbmdzUmVhbCA8LSBuZXcoInJlYWxSYXRpbmdNYXRyaXgiLCBkYXRhID0gcmF0aW5nc01hdCkNCnJhdGluZ3NSZWFsDQpgYGANCg0KKipJJ20gc2VsZWN0aW5nIHRoZSBVc2VycyB3aG8gaGF2ZSByYXRlZCBhdCBsZWFzdCAxMDAgbW92aWVzIGFuZCB0aG9zZSBtb3ZpZXMgdGhhdCBoYXZlIGJlZW4gd2F0Y2hlZCBhdCBsZWFzdCAxNTAgdGltZXMqKg0KDQpgYGB7cn0NCnJhdGluZ3MgPC0gTW92aWVMZW5zZVtyb3dDb3VudHMoTW92aWVMZW5zZSkgPiAxMDAsIGNvbENvdW50cyhNb3ZpZUxlbnNlKSA+IDE1MF0NCmBgYA0KDQojIyBDcmVhdGUgVHJhaW5pbmcgYW5kIFRlc3Rpbmcgc2V0cw0KDQpVc2UgODAlIGZvciB0cmFpbmluZyBhbmQgMjAlIGZvciB0ZXN0aW5nIHRoZSBtb2RlbA0KDQpgYGB7cn0NCk1vdmllc3RyYWluIDwtIHNhbXBsZSh4ID0gYyhUUlVFLCBGQUxTRSksIHNpemUgPSBucm93KHJhdGluZ3MpLCByZXBsYWNlID0gVFJVRSwgcHJvYiA9IGMoMC44LCAwLjIpKQ0KYGBgDQoNCioqUHJlcGFyZSB0cmFpbmluZyBkYXRhc2V0KioNCg0KYGBge3J9DQp0cmFpbiA8LSByYXRpbmdzW01vdmllc3RyYWluLCBdDQpgYGANCg0KKipQcmVwYXJlIHRlc3Rpbmcgc2V0KioNCg0KYGBge3J9DQp0ZXN0IDwtIHJhdGluZ3NbIU1vdmllc3RyYWluLCBdDQpgYGANCg0KIyMgVXNlci1Vc2VyIENvbGxhYm9yYXRpdmUgRmlsdGVyaW5nDQoNClRoZSBVc2VyIGJhc2VkIGNvbGxhYm9yYXRpdmUgZmlsdGVyaW5nIGFsZ29yaXRobXMgYXJlIGJhc2VkIG9uIG1lYXN1cmluZyB0aGUgc2ltaWxhcml0eSBiZXR3ZWVuIHVzZXJzLiBBIOKAnFJlY29tbWVuZGVy4oCdIG9iamVjdCBpcyB0aGVuIGdpdmVuIHRoZSDigJxVQkNG4oCdIChVc2VyLWJhc2VkIGNvbGxhYm9yYXRpdmUgZmlsdGVyKSwgd2l0aCBhIGNlbnRlciBub3JtYWxpemF0aW9uLCBjb3NpbmUgbWV0aG9kLCB3aXRoIDI1IG5lYXJlc3QgbmVpZ2hib3JzLkJ1dCBmaXJzdCwgSSB3aWxsIGNvbXB1dGUgdGhlIHNpbWlsYXJpdHkgbWF0cml4Lg0KDQojIyMgU2ltaWxhcml0eSBNYXRyaXgNCg0KQSBzaW1pbGFyaXR5IG1hdHJpeCBpcyBhIHJlY29tbWVuZGVybGFiIGZ1bmN0aW9uIHRoYXQgdGFrZXMgdGhlIOKAnHJlYWxSYXRpbmdNYXRyaXjigJ0iIGFuZCBjYWxjdWxhdGVzIGEgY29zaW5lIHNpbWlsYXJpdHkgd2hpY2ggYWlkcyBpbiB0aGUgaW52ZXN0aWdhdGlvbiBvZiBtb2RlbCBkZXZlbG9wbWVudC4gDQoNCmBgYHtyfQ0Kc2ltaWxhcml0eVVzZXJzIDwtIHNpbWlsYXJpdHkoTW92aWVMZW5zZVsxOjQsIF0sIG1ldGhvZCA9ICJjb3NpbmUiLCB3aGljaCA9ICJ1c2VycyIpDQoNCmltYWdlKGFzLm1hdHJpeChzaW1pbGFyaXR5VXNlcnMpLCBtYWluID0gIlVzZXJzIHNpbWlsYXJpdHkiKQ0KYGBgDQoNCiMjIyBUaGUgVXNlciBCYXNlZCBNb2RlbA0KDQpCdWlsZGluZyB0aGUgVXNlciBCYXNlZCBNb2RlbCB1c2luZyAyNSBuZWFyZXN0IG5laWdoYm9yLiBCdWlsZGluZyB0aGUgdXNlciBjb2xsYWJvcmF0aXZlIGZpbHRlcmluZyBzeXN0ZW0gdG8gcmVjb21tZW5kIG1vdmllcyB0byB1c2VycyBiYXNlZCBvbiBob3cgc2ltaWxhciB0aGV5IGFyZSB3aXRoIG90aGVyIHVzZXJzLg0KDQpgYGB7cn0NCnVzZXJtb2RlbCA8LSBSZWNvbW1lbmRlcih0cmFpbiwgbWV0aG9kID0gIlVCQ0YiLCANCiAgICAgICAgICAgICAgICAgICAgIHBhcmFtPWxpc3Qobm9ybWFsaXplID0gImNlbnRlciIsIG1ldGhvZD0iQ29zaW5lIiwgbm49MjUpKQ0KDQp1c2VybW9kZWxkZXRhaWxzIDwtIGdldE1vZGVsKHVzZXJtb2RlbCkNCmBgYA0KDQojIyMgTWFraW5nIFByZWRpY3Rpb25zIHdpdGggbmV3ZGF0YSA9IHRlc3QNCg0KYGBge3J9DQp1c2VybW9kZWxwcmVkaWN0aW9uIDwtIHByZWRpY3Qob2JqZWN0ID0gdXNlcm1vZGVsLCBuZXdkYXRhID0gdGVzdCwgdHlwZT0icmF0aW5ncyIpDQphcyh1c2VybW9kZWxwcmVkaWN0aW9uLCAibWF0cml4IilbLCAxOjRdICU+JSBrYWJsZSgpICU+JSBrYWJsZV9zdHlsaW5nKGZ1bGxfd2lkdGggPSBUKQ0KYGBgDQoNCiMjIE1vZGVsIEV2YWx1YXRpb24gLSBVc2VyIEJhc2VkDQoNCmBgYHtyfQ0KDQpzY2hlbWUgPC0gZXZhbHVhdGlvblNjaGVtZShyYXRpbmdzLCBtZXRob2Q9ImNyb3NzLXZhbGlkYXRpb24iLCANCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgayA9IDQsIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICBnaXZlbiA9IDEwLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICBnb29kUmF0aW5nID0gNCkNCg0KcmVzdWx0cyA8LSBldmFsdWF0ZSh4ID0gc2NoZW1lLCBtZXRob2QgPSAiVUJDRiIsIG49YygxMCwyNSw1MCw3NSwxMDApKQ0KDQpoZWFkKGdldENvbmZ1c2lvbk1hdHJpeChyZXN1bHRzKVtbMV1dKQ0KYGBgDQoNClRoZSBUUFIgaXMgdGhlIHBlcmNlbnRhZ2Ugb2YgdGhlIG1vdmllcyB0aGF0IGhhdmUgYmVlbiBwdXJjaGFzZWQgYW5kIHdhcyByZWNvbW1lbmRlZCB3aGlsZSB0aGUgRlBSIGlzIHRoZSBwZXJjZW50YWdlIG9mIHRoZSBtb3ZpZXMgdGhhdCB3YXMgbm90IHB1cmNoYXNlZCBidXQgd2FzIHJlY29tbWVuZGVkIHdpdGggbiBhcyB0aGUgbnVtYmVyIG9mIHJlY29tbWVuZGF0aW9ucyAoMTAsMjUsNTAsNzUsMTAwKS4NCg0KKipST0MgQ3VydmUgUGxvdCoqDQoNCmBgYHtyfQ0KcGxvdChyZXN1bHRzLCBhbm5vdGF0ZT0gVFJVRSwgbWFpbiA9ICJST0MgQ3VydmUiKQ0KYGBgDQoNClRoZSBwcmVjaXNpb24gYW5kIHJlY2FsbCBzaG93cyB0aGUgcGVyY2VudGFnZSBvZiBtb3ZpZXMgdGhhdCBoYXZlIGJlZW4gcHVyY2hhc2VkIGFuZCB0aGUgcGVyY2VudGFnZSBvZiBtb3ZpZXMgdGhhdCB3YXMgcmVjb21tZW5kZWQuIA0KDQojIyBpdGVtLWl0ZW0gQ29sbGFib3JhdGl2ZSBGaWx0ZXJpbmcNCg0KVGhlIEl0ZW0gYmFzZWQgY29sbGFib3JhdGl2ZSBmaWx0ZXJpbmcgYWxnb3JpdGhtcyBhcmUgYmFzZWQgb24gbWVhc3VyaW5nIHRoZSBzaW1pbGFyaXR5IGJldHdlZW4gaXRlbXMgQSDigJxSZWNvbW1lbmRlcuKAnSBvYmplY3QgaXMgdGhlbiBnaXZlbiB0aGUg4oCcSUJDRuKAnSAoSXRlbS1iYXNlZCBjb2xsYWJvcmF0aXZlIGZpbHRlciksIHdpdGggYSBjZW50ZXIgbm9ybWFsaXphdGlvbiwgY29zaW5lIG1ldGhvZCwgd2l0aCBLID0gMjUwLkJ1dCBmaXJzdCwgSSB3aWxsIGNvbXB1dGUgdGhlIHNpbWlsYXJpdHkgbWF0cml4Lg0KDQojIyMgU2ltaWxhcml0eSBNYXRyaXgNCg0KQSBzaW1pbGFyaXR5IG1hdHJpeCBpcyBhIHJlY29tbWVuZGVybGFiIGZ1bmN0aW9uIHRoYXQgdGFrZXMgdGhlIOKAnHJlYWxSYXRpbmdNYXRyaXjigJ0iIGFuZCBjYWxjdWxhdGVzIGEgY29zaW5lIHNpbWlsYXJpdHkgd2hpY2ggYWlkcyBpbiB0aGUgaW52ZXN0aWdhdGlvbiBvZiBtb2RlbCBkZXZlbG9wbWVudC4gDQoNCmBgYHtyfQ0Kc2ltaWxhcml0eWl0ZW1zIDwtIHNpbWlsYXJpdHkoTW92aWVMZW5zZVssIDE6NF0sIG1ldGhvZCA9ICJjb3NpbmUiLCB3aGljaCA9ICJpdGVtcyIpDQoNCmltYWdlKGFzLm1hdHJpeChzaW1pbGFyaXR5aXRlbXMpLCBtYWluID0gIkl0ZW1zIHNpbWlsYXJpdHkiKQ0KYGBgDQoNClRoZSBkaWFnb25hbCBpcyB5ZWxsb3cgYmVjYXVzZSBpdOKAmXMgY29tcGFyaW5nIGVhY2ggaXRlbXMgd2l0aCBpdHNlbGYuIA0KDQojIyMgVGhlIEl0ZW0gQmFzZWQgTW9kZWwNCg0KQnVpbGRpbmcgdGhlIGl0ZW0taXRlbSBjb2xsYWJvcmF0aXZlIGZpbHRlcmluZyBzeXN0ZW0gdG8gcmVjb21tZW5kIG1vdmllcyB0byB1c2VycyB3aGVyZSB0aGVpciBpdGVt4oCZcyByYXRpbmdzIGFyZSBzaW1pbGFyLg0KDQpgYGB7cn0NCml0ZW1tb2RlbCA8LSBSZWNvbW1lbmRlcih0cmFpbiwgbWV0aG9kID0gIklCQ0YiLCANCiAgICAgICAgICAgICAgICAgICAgIHBhcmFtPWxpc3Qobm9ybWFsaXplID0gImNlbnRlciIsIG1ldGhvZD0iQ29zaW5lIiwgaz0yNTApKQ0KDQppdGVtbW9kZWxkZXRhaWxzIDwtIGdldE1vZGVsKGl0ZW1tb2RlbCkNCmBgYA0KDQojIyMgTWFraW5nIFByZWRpY3Rpb25zIHdpdGggbmV3ZGF0YSA9IHRlc3QNCg0KYGBge3J9DQppdGVtbW9kZWxwcmVkaWN0aW9uIDwtIHByZWRpY3Qob2JqZWN0ID0gaXRlbW1vZGVsLCBuZXdkYXRhID0gdGVzdCwgdHlwZT0icmF0aW5ncyIpDQphcyhpdGVtbW9kZWxwcmVkaWN0aW9uLCAibWF0cml4IilbLCAxOjRdICU+JSBrYWJsZSgpICU+JSBrYWJsZV9zdHlsaW5nKGZ1bGxfd2lkdGggPSBUKQ0KYGBgDQoNCiMjIE1vZGVsIEV2YWx1YXRpb24gLSBJdGVtIEJhc2VkDQoNCmBgYHtyfQ0KDQpzY2hlbWUgPC0gZXZhbHVhdGlvblNjaGVtZShyYXRpbmdzLCBtZXRob2Q9ImNyb3NzLXZhbGlkYXRpb24iLCANCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgayA9IDQsIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICBnaXZlbiA9IDEwLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICBnb29kUmF0aW5nID0gNCkNCg0KcmVzdWx0czIgPC0gZXZhbHVhdGUoeCA9IHNjaGVtZSwgbWV0aG9kID0gIklCQ0YiLCBuPWMoMTAsMjUsNTAsNzUsMTAwKSkNCg0KaGVhZChnZXRDb25mdXNpb25NYXRyaXgocmVzdWx0czIpW1sxXV0pDQpgYGANCg0KVGhlIFRQUiBpcyB0aGUgcGVyY2VudGFnZSBvZiB0aGUgbW92aWVzIHRoYXQgaGF2ZSBiZWVuIHB1cmNoYXNlZCBhbmQgd2FzIHJlY29tbWVuZGVkIHdoaWxlIHRoZSBGUFIgaXMgdGhlIHBlcmNlbnRhZ2Ugb2YgdGhlIG1vdmllcyB0aGF0IHdhcyBub3QgcHVyY2hhc2VkIGJ1dCB3YXMgcmVjb21tZW5kZWQgd2l0aCBuIGFzIHRoZSBudW1iZXIgb2YgcmVjb21tZW5kYXRpb25zICgyLDQsNiw4LDEwLDUwKS4NCg0KKipST0MgQ3VydmUgUGxvdCoqDQoNCmBgYHtyfQ0KcGxvdChyZXN1bHRzMiwgYW5ub3RhdGU9IFRSVUUsIG1haW4gPSAiUk9DIEN1cnZlIikNCmBgYA0KDQoNCiMjIyBDb25jbHVzaW9uDQoNClRoZSBwcmVjaXNpb24gYW5kIHJlY2FsbCBmb3IgdGhlIFVzZXIgQmFzZWQgUmVjb21tZW5kZXIgc3lzdGVtIHNob3dzIHRoZSBwZXJjZW50YWdlIG9mIE1vdmllcyB0aGF0IGhhdmUgYmVlbiBwdXJjaGFzZWQgYW5kIHRoZSBwZXJjZW50YWdlIG9mIE1vdmllcyB0aGF0IHdhcyByZWNvbW1lbmRlZC4gV2UgY2FuIHNlZSB0aGF0IDEwIG1vdmllcyB3ZXJlIHB1cmNoYXNlZCA0MiUgb2YgdGhlIHRpbWUgd2hpbGUgMTAwIG1vdmllcyB3ZXJlIHJlY29tbWVuZGVkIDYxJSBvZiB0aGUgdGltZS4NCg0KT24gdGhlIG90aGVyIGhhbmQsIHRoZSBwcmVjaXNpb24gYW5kIHJlY2FsbCBmb3IgdGhlIEl0ZW0gQmFzZWQgUmVjb21tZW5kZXIgc3lzdGVtIGFsc28gc2hvd3MgdGhlIHBlcmNlbnRhZ2Ugb2YgTW92aWVzIHRoYXQgaGF2ZSBiZWVuIHB1cmNoYXNlZCBhbmQgdGhlIHBlcmNlbnRhZ2Ugb2YgTW92aWVzIHRoYXQgd2FzIHJlY29tbWVuZGVkLiBXZSBjYW4gYWxzbyBzZWUgdGhhdCAxMCBtb3ZpZXMgd2VyZSBwdXJjaGFzZWQgMzYlIG9mIHRoZSB0aW1lIHdoaWxlIDEwMCBtb3ZpZXMgd2VyZSByZWNvbW1lbmRlZCA1MCUgb2YgdGhlIHRpbWUuDQoNCg0KUmVmZXJlbmNlcw0KDQpLb2hhdmksIFJvbiAoMTk5NSkuICJBIHN0dWR5IG9mIGNyb3NzLXZhbGlkYXRpb24gYW5kIGJvb3RzdHJhcCBmb3IgYWNjdXJhY3kgZXN0aW1hdGlvbiBhbmQgbW9kZWwgc2VsZWN0aW9uIi4gUHJvY2VlZGluZ3Mgb2YgdGhlIEZvdXJ0ZWVudGggSW50ZXJuYXRpb25hbCBKb2ludCBDb25mZXJlbmNlIG9uIEFydGlmaWNpYWwgSW50ZWxsaWdlbmNlLCBwcC4gMTEzNy0xMTQzLg0KDQpCcmVlc2UgSlMsIEhlY2tlcm1hbiBELCBLYWRpZSBDICgxOTk4KS4gIkVtcGlyaWNhbCBBbmFseXNpcyBvZiBQcmVkaWN0aXZlIEFsZ29yaXRobXMgZm9yIENvbGxhYm9yYXRpdmUgRmlsdGVyaW5nLiIgSW4gVW5jZXJ0YWludHkgaW4gQXJ0aWZpY2lhbCBJbnRlbGxpZ2VuY2UuIFByb2NlZWRpbmdzIG9mIHRoZSBGb3VydGVlbnRoIENvbmZlcmVuY2UsIHBwLiA0My01Mi4NCg==