Metodologi Penelitian dan Optimasi

~ Ujian Tengah Semester ~

PERBANDINGAN ANTARA KMEANS DAN ALGORITMA EM DENGAN MENGGUNAKAN EMCLUSTER

Diajukan sebagai salah satu syarat untuk memperoleh nilai Ujian Tengah Semester pada mata kuliah Optimasi dan Metodologi Penelitian


BAB 1


PENDAHULUAN

Latar Belakang

Clustering atau klasterisasi adalah metode pengelompokan data yang merupakan proses partisi satu set objek ke dalam himpunan bagian yang disebut cluster. Objek yang di dalam cluster memiliki kemiripan karakteristik antar satu sama lainnya dan berbeda dengan cluster yang lain. Partisi tidak dilakukan secara manual melainkan dengan suatu algoritma clustering. Oleh karena itu, clustering sangat berguna dan bisa menemukan group atau kelompok yang tidak dikenal dalam data.

Iris merupakan salah satu jenis bunga dari famili Iridaceae yang terdiri dari 300 spesies. Penelitian ini menggunakan data Iris sebanyak 150 sampel dengan 3 spesies berbeda. Maing-masing spesies memiliki Sepal Length, Sepal Width, Petal Length, dan Petal Width.

Clustering memiliki banyak algoritma dengan beberapa kategori, yaitu hierarchical. Algoritma dengan kategori hierarchical menentukan sendiri jumlah cluster yang dihasilkannya, seperti algoritma SNN, COBWEB, Chandeon dan Rock. Selanjutnya ada algoritma dengan kategori Partitional. Algoritma dengan kategori Partitional mengelompokkan data kedalam k cluster, dengan k adalah banyak cluster dari input user misalnya algoritma CLARA, K-Means, EM, dan Bond Energy.Dengan hal demikian, peneliti ingin mencari tahu perbandingan antara K-Means dengan Algoritma EM yang dikelompokkan ke dalam cluster-cluster.

Rumusan Masalah

Berdasarkan latar belakang, maka rumusan pada penelitian ini adalah: 1.2.1 Bagaimana hasil perbandingan antara K-Means dengan Algoritma EM?

Tujuan Penelitian

Sesuai dengan rumusan masalah yang telah disusun, maka tujuan dari penelitian ini adalah: 1.3.1 Untuk mengetahui hasil perbandingan antara K-Means dengan Algoritma EM.

Manfaat Penelitian

Berdasarkan tujuan penelitian, manfaat penelitian ini adalah: 1.4.1 Mengetahui car akerja Algoritma K-Meas dan EM. 1.4.2 Mengetahui perbandingan K-Meand dan Algoritma EM pada data Iris yang digunakan.

BAB 2


KAJIAN PUSTAKA

K-Means

K-means merupakan algoritma clustering. K-means Clustering adalah salah satu “unsupervised machine learning algorithms” yang paling sederhana dan populer. K-Means Clustering adalah suatu metode penganalisaan data atau metode Data Mining yang melakukan proses pemodelan tanpa supervisi (unsupervised) dan merupakan salah satu metode yang melakukan pengelompokan data dengan sistem partisi.

K-means clustering merupakan salah satu metode cluster analysis non hirarki yang berusaha untuk mempartisi objek yang ada kedalam satu atau lebih cluster atau kelompok objek berdasarkan karakteristiknya, sehingga objek yang mempunyai karakteristik yang sama dikelompokan dalam satu cluster yang sama dan objek yang mempunyai karakteristik yang berbeda dikelompokan kedalam cluster yang lain. Metode K-Means Clustering berusaha mengelompokkan data yang ada ke dalam beberapa kelompok, dimana data dalam satu kelompok mempunyai karakteristik yang sama satu sama lainnya dan mempunyai karakteristik yang berbeda dengan data yang ada di dalam kelompok yang lain.

Dengan kata lain, metode K-Means Clustering bertujuan untuk meminimalisasikan objective function yang diset dalam proses clustering dengan cara meminimalkan variasi antar data yang ada di dalam suatu cluster dan memaksimalkan variasi dengan data yang ada di cluster lainnya juga bertujuan untuk menemukan grup dalam data, dengan jumlah grup yang diwakili oleh variabel K. Variabel K sendiri adalah jumlah cluster yang diinginkan.

EM

Algoritma Expectation Maximizaton (EM) adalah suatu metode estimasi untuk menemukan kemungkinan maksimum dari perkiraan parameter dalam metode statistik. Algortima EM adalah salah satu algoritma yang digunakan untuk klasifikasi atau pengelompokan data. Expectation Maximation (EM) termasuk algoritma partitional yang berbasiskan model, dengan menggunakan perhitungan probabilitas, bukan jarak seperti umumnya algoritma clustering yang lainnya.

BAB 3


METODOLOGI PENELITIAN ## Metode Metode adalah suatu proses atau cara sistematis yang digunakan untuk mencapai tujuan tertentu dengan efisiensi, biasanya dalam urutan langkah-langkah tetap yang teratur. Kata metode (method) berasal dari bahasa Latin dan juga Yunani, methodus yang berasal dari kata meta yang berarti sesudah atau di atas, dan kata hodos, yang berarti suatu jalan atau suatu cara. Metode penelitian adalah langkah-langkah yang diambil oleh peneliti untuk mengumpulkan data atau informasi untuk diolah dan dianalisis secara ilmiah.

Packages

Dalam penelitian ini, peneliti memakai beberapa package dalam R. Berikut adalah package yang dimuat dalam penelitian ini:

library(ggplot2)
library(DT)
library(EMCluster)
## Loading required package: MASS
## Loading required package: Matrix
library(FactoMineR)
library(reshape2)
library(summarytools)
library(dplyr)
## 
## Attaching package: 'dplyr'
## The following object is masked from 'package:EMCluster':
## 
##     recode
## The following object is masked from 'package:MASS':
## 
##     select
## The following objects are masked from 'package:stats':
## 
##     filter, lag
## The following objects are masked from 'package:base':
## 
##     intersect, setdiff, setequal, union

Package ggplot2 merupakan paket di R yang bebas diunduh dan digunakan untuk membuat berbagai bentuk grafik. Grafik yang ditampilkan bisa berupa data numerik maupun data kategorik, univariat maupun multivariat. Selanjutnya, package DT adalah package datatabel, yang dapat digunakan untuk menampilkan data dalam bentuk tabel. Lalu, package EMCluster digunakan pada R untuk klasterisasi algoritma EM. Package FactoMineR digunakan pada R untuk Analisis Data Eksplorasi Multivariat dan Penambangan Data, Metode analisis data eksplorasi untuk meringkas, memvisualisasikan, dan menggambarkan dataset. Kemudian, package reshape2 digunakan untuk memudahkan dalam mengubah data antara format yang luas dan panjang. Lalu, kegunaan package summarytools pada R adalah menyediakan alat untuk meringkas data dengan rapi dan cepat. Yang terakhir, untuk package dplyr dapat digunakan untuk memanipulasi data. Package ini sangat berguna ketika digunakan untuk melakukan analisis dan eksplorasi data.

Metode Pengambilan Data

Pada penelitian perbandingan algoritma K-Means dan EM, data yang dipakai adalah data sekunder, dengan kata lain data ini sudah ada di R. Berikut akan diimport data yang dipakai pada perbandingan dalam penelitian ini.

datatable(iris)

BAB 4


HASIL DAN PEMBAHASAN

Dalam penelitian ini akan membandingkan dua cara untuk melakukan Analisis cluster, yaitu dengan K-Means dan EM Algoritma atas data mentah dan komponen utama (PC). PCA dilakukan melalui fungsi PCA() dari paket FactomineR. Demikian pula, untuk kmeans kami menggunakan fungsi stat built-in.

set.seed(123)
pca_iris=PCA(iris[,-5],scale.unit = T,ncp = 2,graph = F)
iris_sc=scale(iris[,-5],center = T,scale = T)

km_raw=kmeans(iris_sc, centers=3)

emobj <- exhaust.EM(iris_sc,nclass = 3) 
emobj <- shortemcluster(iris_sc, emobj,maxiter = 1000)
em_raw <- emcluster(iris_sc, emobj, assign.class = TRUE)

dat_clust_raw=data.frame(iris_sc,"Species"=as.factor(iris$Species), 
          kmeans=as.factor(km_raw$cluster), EM=as.factor(em_raw$class))
km_pca=kmeans(pca_iris$ind$coord, centers=3)

emobj_pca <- exhaust.EM(pca_iris$ind$coord, nclass = 3) 
emobj_pca <- shortemcluster(pca_iris$ind$coord, emobj_pca,maxiter = 1000)
em_pca <- emcluster(pca_iris$ind$coord, emobj_pca, assign.class = TRUE)

dat_clust_pca=data.frame(pca_iris$ind$coord,"Species"=iris$Species,
              kmeans=as.factor(km_pca$cluster), EM=as.factor(em_pca$class))

EM-Algoritma seharusnya memiliki kinerja lebih baik dari K-means normal, ketika bentuk sebenarnya dari cluster adalah tidak bulat atau berukuran kecil.

dat_raw=dat_clust_raw %>% melt(id.var=colnames(iris[,-5]))
## Warning: attributes are not identical across measure variables; they will be
## dropped
dat_raw %>% ggplot(aes(x=Sepal.Length,y=Petal.Width, color=value))+geom_point()+
  facet_wrap(~variable)+theme_grey()+
  theme(strip.background =element_rect(fill="darkred"))+
  theme(strip.text = element_text(colour = 'white'))+guides(color=FALSE)
## Warning: `guides(<scale> = FALSE)` is deprecated. Please use `guides(<scale> =
## "none")` instead.

dat_pca=dat_clust_pca %>% melt(id.var=c("Dim.1","Dim.2"))
## Warning: attributes are not identical across measure variables; they will be
## dropped
dat_pca %>% ggplot(aes(x=Dim.1,y=Dim.2, color=value))+geom_point()+facet_wrap(~variable)+theme_grey()+
  theme(strip.background =element_rect(fill="darkred"))+
  theme(strip.text = element_text(colour = 'white'))+guides(color=FALSE)
## Warning: `guides(<scale> = FALSE)` is deprecated. Please use `guides(<scale> =
## "none")` instead.

Dapat dilihat bahwa dalam kedua, data mentah dan koordinat PCA, EM tampaknya berperilaku dan melakukan penghormatan yang lebih baik terhadap Kmeans. Bandingkan sendiri. Lihatlah aspek “Spesies” dan temukan mana dari kedua metode yang lebih dekat dengan representasi grafis yang sebenarnya.

BAB 5


KESIMPULAN DAN SARAN

Kesimpulan

Berdasarkan perhitungan yang sudah dilakukan di atas, maka dapat disimpulkan bahwa walaupun terdapat beberapa hasil yang berbeda, namun analisis data dengan algoritma K-Means atau EM dapat digunakan untuk mengelompokkan data berdasarkan jenisnya. Dengan adanya clustering dapat membantu mempercepat pengolahan data dalam mengelompokkan jumlah data berdasarkan jenisnya. Algoritma yang terbaik digunakan untuk mengelompokkan data iris adalah algoritma EM, karena memiliki tingkat perbedaan yang lebih rendah dan memiliki tingkat keakuratan yang lebih tinggi.

Saran

Penelitian ini masih merupakan penelitian yang sederhana. Untuk penelitian selanjutnya kiranya dapat menggunakan data yang lebih luas dan dapat membandingkan kembali dengan metode lainnya.

LS0tDQp0aXRsZTogIk1ldG9kb2xvZ2kgUGVuZWxpdGlhbiBkYW4gT3B0aW1hc2kiDQpzdWJ0aXRsZTogIn4gVWppYW4gVGVuZ2FoIFNlbWVzdGVyIH4iDQphdXRob3I6ICJKb2NlbHluIElyZW5lIEdhbmkiDQpkYXRlOiAgImByIGZvcm1hdChTeXMuRGF0ZSgpLCAnJUIgJWQsICVZJylgIg0Kb3V0cHV0Og0KICBybWRmb3JtYXRzOjpyZWFkdGhlZG93bjogICAjIGh0dHBzOi8vZ2l0aHViLmNvbS9qdWJhL3JtZGZvcm1hdHMNCiAgICBzZWxmX2NvbnRhaW5lZDogdHJ1ZQ0KICAgIHRodW1ibmFpbHM6IHRydWUNCiAgICBsaWdodGJveDogdHJ1ZQ0KICAgIGdhbGxlcnk6IHRydWUNCiAgICBsaWJfZGlyOiBsaWJzDQogICAgZGZfcHJpbnQ6ICJwYWdlZCINCiAgICBjb2RlX2ZvbGRpbmc6ICJzaG93Ig0KICAgIGNvZGVfZG93bmxvYWQ6IHllcw0KICAgIGNzczogInN0eWxlICgzKS5jc3MiDQoNCi0tLQ0KDQojIFBFUkJBTkRJTkdBTiBBTlRBUkEgS01FQU5TIERBTiBBTEdPUklUTUEgRU0gREVOR0FOIE1FTkdHVU5BS0FOIEVNQ0xVU1RFUg0KIyBEaWFqdWthbiBzZWJhZ2FpIHNhbGFoIHNhdHUgc3lhcmF0IHVudHVrIG1lbXBlcm9sZWggbmlsYWkgVWppYW4gVGVuZ2FoIFNlbWVzdGVyIHBhZGEgbWF0YSBrdWxpYWggT3B0aW1hc2kgZGFuIE1ldG9kb2xvZ2kgUGVuZWxpdGlhbiANCg0KPGJyPg0KDQpgYGB7ciBtZSwgZWNobz1GQUxTRSxmaWcuYWxpZ249J2NlbnRlcicsIG91dC53aWR0aCA9ICczMCUnfQ0Ka25pdHI6OmluY2x1ZGVfZ3JhcGhpY3MoImxvZ28ucG5nIikNCmBgYA0KDQoqKioNCg0KIyBCQUIgMSANCjxicj4gUEVOREFIVUxVQU4NCg0KIyMgTGF0YXIgQmVsYWthbmcNCiAgX0NsdXN0ZXJpbmdfIGF0YXUga2xhc3RlcmlzYXNpIGFkYWxhaCBtZXRvZGUgcGVuZ2Vsb21wb2thbiBkYXRhIHlhbmcgbWVydXBha2FuIHByb3NlcyBwYXJ0aXNpIHNhdHUgc2V0IG9iamVrIGtlIGRhbGFtIGhpbXB1bmFuIGJhZ2lhbiB5YW5nIGRpc2VidXQgX2NsdXN0ZXJfLiBPYmplayB5YW5nIGRpIGRhbGFtIF9jbHVzdGVyXyBtZW1pbGlraSBrZW1pcmlwYW4ga2FyYWt0ZXJpc3RpayBhbnRhciBzYXR1IHNhbWEgbGFpbm55YSBkYW4gYmVyYmVkYSBkZW5nYW4gX2NsdXN0ZXJfIHlhbmcgbGFpbi4gUGFydGlzaSB0aWRhayBkaWxha3VrYW4gc2VjYXJhIG1hbnVhbCBtZWxhaW5rYW4gZGVuZ2FuIHN1YXR1IGFsZ29yaXRtYSBfY2x1c3RlcmluZ18uIE9sZWgga2FyZW5hIGl0dSwgX2NsdXN0ZXJpbmdfIHNhbmdhdCBiZXJndW5hIGRhbiBiaXNhIG1lbmVtdWthbiBncm91cCBhdGF1IGtlbG9tcG9rIHlhbmcgdGlkYWsgZGlrZW5hbCBkYWxhbSBkYXRhLg0KDQogIElyaXMgbWVydXBha2FuIHNhbGFoIHNhdHUgamVuaXMgYnVuZ2EgZGFyaSBmYW1pbGkgX0lyaWRhY2VhZV8geWFuZyB0ZXJkaXJpIGRhcmkgMzAwIHNwZXNpZXMuIFBlbmVsaXRpYW4gaW5pIG1lbmdndW5ha2FuIGRhdGEgSXJpcyBzZWJhbnlhayAxNTAgc2FtcGVsIGRlbmdhbiAzIHNwZXNpZXMgYmVyYmVkYS4gTWFpbmctbWFzaW5nIHNwZXNpZXMgbWVtaWxpa2kgX1NlcGFsIExlbmd0aF8sIF9TZXBhbCBXaWR0aF8sIF9QZXRhbCBMZW5ndGhfLCBkYW4gX1BldGFsIFdpZHRoXy4NCg0KICBfQ2x1c3RlcmluZ18gbWVtaWxpa2kgYmFueWFrIGFsZ29yaXRtYSBkZW5nYW4gYmViZXJhcGEga2F0ZWdvcmksIHlhaXR1IF9oaWVyYXJjaGljYWxfLiBBbGdvcml0bWEgZGVuZ2FuIGthdGVnb3JpIGhpZXJhcmNoaWNhbCBtZW5lbnR1a2FuIHNlbmRpcmkganVtbGFoIF9jbHVzdGVyXyB5YW5nIGRpaGFzaWxrYW5ueWEsIHNlcGVydGkgYWxnb3JpdG1hIFNOTiwgQ09CV0VCLCBDaGFuZGVvbiBkYW4gUm9jay4gU2VsYW5qdXRueWEgYWRhIGFsZ29yaXRtYSBkZW5nYW4ga2F0ZWdvcmkgUGFydGl0aW9uYWwuIEFsZ29yaXRtYSBkZW5nYW4ga2F0ZWdvcmkgUGFydGl0aW9uYWwgbWVuZ2Vsb21wb2trYW4gZGF0YSBrZWRhbGFtIGsgY2x1c3RlciwgZGVuZ2FuIGsgYWRhbGFoIGJhbnlhayBfY2x1c3Rlcl8gZGFyaSBpbnB1dCB1c2VyIG1pc2FsbnlhIGFsZ29yaXRtYSBDTEFSQSwgSy1NZWFucywgRU0sIGRhbiBCb25kIEVuZXJneS5EZW5nYW4gaGFsIGRlbWlraWFuLCBwZW5lbGl0aSBpbmdpbiBtZW5jYXJpIHRhaHUgcGVyYmFuZGluZ2FuIGFudGFyYSBLLU1lYW5zIGRlbmdhbiBBbGdvcml0bWEgRU0geWFuZyBkaWtlbG9tcG9ra2FuIGtlIGRhbGFtIF9jbHVzdGVyLWNsdXN0ZXJfLg0KDQojIyBSdW11c2FuIE1hc2FsYWgNCkJlcmRhc2Fya2FuIGxhdGFyIGJlbGFrYW5nLCBtYWthIHJ1bXVzYW4gcGFkYSBwZW5lbGl0aWFuIGluaSBhZGFsYWg6DQoxLjIuMSBCYWdhaW1hbmEgaGFzaWwgcGVyYmFuZGluZ2FuIGFudGFyYSBLLU1lYW5zIGRlbmdhbiBBbGdvcml0bWEgRU0/DQoNCiMjIFR1anVhbiBQZW5lbGl0aWFuDQpTZXN1YWkgZGVuZ2FuIHJ1bXVzYW4gbWFzYWxhaCB5YW5nIHRlbGFoIGRpc3VzdW4sIG1ha2EgdHVqdWFuIGRhcmkgcGVuZWxpdGlhbiBpbmkgYWRhbGFoOg0KMS4zLjEgVW50dWsgbWVuZ2V0YWh1aSBoYXNpbCBwZXJiYW5kaW5nYW4gYW50YXJhIEstTWVhbnMgZGVuZ2FuIEFsZ29yaXRtYSBFTS4NCg0KIyMgTWFuZmFhdCBQZW5lbGl0aWFuDQpCZXJkYXNhcmthbiB0dWp1YW4gcGVuZWxpdGlhbiwgbWFuZmFhdCBwZW5lbGl0aWFuIGluaSBhZGFsYWg6DQoxLjQuMSBNZW5nZXRhaHVpIGNhciBha2VyamEgQWxnb3JpdG1hIEstTWVhcyBkYW4gRU0uDQoxLjQuMiBNZW5nZXRhaHVpIHBlcmJhbmRpbmdhbiBLLU1lYW5kIGRhbiBBbGdvcml0bWEgRU0gcGFkYSBkYXRhIElyaXMgeWFuZyBkaWd1bmFrYW4uDQoNCiMgQkFCIDINCjxicj4gS0FKSUFOIFBVU1RBS0ENCg0KIyMgSy1NZWFucw0KICBLLW1lYW5zIG1lcnVwYWthbiBhbGdvcml0bWEgX2NsdXN0ZXJpbmdfLiBLLW1lYW5zIF9DbHVzdGVyaW5nXyBhZGFsYWggc2FsYWggc2F0dSBf4oCcdW5zdXBlcnZpc2VkIG1hY2hpbmUgbGVhcm5pbmcgYWxnb3JpdGhtc+KAnV8geWFuZyBwYWxpbmcgc2VkZXJoYW5hIGRhbiBwb3B1bGVyLiBLLU1lYW5zIENsdXN0ZXJpbmcgYWRhbGFoIHN1YXR1IG1ldG9kZSBwZW5nYW5hbGlzYWFuIGRhdGEgYXRhdSBtZXRvZGUgRGF0YSBNaW5pbmcgeWFuZyBtZWxha3VrYW4gcHJvc2VzIHBlbW9kZWxhbiB0YW5wYSBzdXBlcnZpc2kgKHVuc3VwZXJ2aXNlZCkgZGFuIG1lcnVwYWthbiBzYWxhaCBzYXR1IG1ldG9kZSB5YW5nIG1lbGFrdWthbiBwZW5nZWxvbXBva2FuIGRhdGEgZGVuZ2FuIHNpc3RlbSBwYXJ0aXNpLg0KDQogIEstbWVhbnMgY2x1c3RlcmluZyBtZXJ1cGFrYW4gc2FsYWggc2F0dSBtZXRvZGUgY2x1c3RlciBhbmFseXNpcyBub24gaGlyYXJraSB5YW5nIGJlcnVzYWhhIHVudHVrIG1lbXBhcnRpc2kgb2JqZWsgeWFuZyBhZGEga2VkYWxhbSBzYXR1IGF0YXUgbGViaWggY2x1c3RlciBhdGF1IGtlbG9tcG9rIG9iamVrIGJlcmRhc2Fya2FuIGthcmFrdGVyaXN0aWtueWEsIHNlaGluZ2dhIG9iamVrIHlhbmcgbWVtcHVueWFpIGthcmFrdGVyaXN0aWsgeWFuZyBzYW1hIGRpa2Vsb21wb2thbiBkYWxhbSBzYXR1IGNsdXN0ZXIgeWFuZyBzYW1hIGRhbiBvYmplayB5YW5nIG1lbXB1bnlhaSBrYXJha3RlcmlzdGlrIHlhbmcgYmVyYmVkYSBkaWtlbG9tcG9rYW4ga2VkYWxhbSBjbHVzdGVyIHlhbmcgbGFpbi4gTWV0b2RlIEstTWVhbnMgQ2x1c3RlcmluZyBiZXJ1c2FoYSBtZW5nZWxvbXBva2thbiBkYXRhIHlhbmcgYWRhIGtlIGRhbGFtIGJlYmVyYXBhIGtlbG9tcG9rLCBkaW1hbmEgZGF0YSBkYWxhbSBzYXR1IGtlbG9tcG9rIG1lbXB1bnlhaSBrYXJha3RlcmlzdGlrIHlhbmcgc2FtYSBzYXR1IHNhbWEgbGFpbm55YSBkYW4gbWVtcHVueWFpIGthcmFrdGVyaXN0aWsgeWFuZyBiZXJiZWRhIGRlbmdhbiBkYXRhIHlhbmcgYWRhIGRpIGRhbGFtIGtlbG9tcG9rIHlhbmcgbGFpbi4NCg0KICBEZW5nYW4ga2F0YSBsYWluLCBtZXRvZGUgSy1NZWFucyBDbHVzdGVyaW5nIGJlcnR1anVhbiB1bnR1ayBtZW1pbmltYWxpc2FzaWthbiBvYmplY3RpdmUgZnVuY3Rpb24geWFuZyBkaXNldCBkYWxhbSBwcm9zZXMgY2x1c3RlcmluZyBkZW5nYW4gY2FyYSBtZW1pbmltYWxrYW4gdmFyaWFzaSBhbnRhciBkYXRhIHlhbmcgYWRhIGRpIGRhbGFtIHN1YXR1IGNsdXN0ZXIgZGFuIG1lbWFrc2ltYWxrYW4gdmFyaWFzaSBkZW5nYW4gZGF0YSB5YW5nIGFkYSBkaSBjbHVzdGVyIGxhaW5ueWEganVnYSBiZXJ0dWp1YW4gdW50dWsgbWVuZW11a2FuIGdydXAgZGFsYW0gZGF0YSwgZGVuZ2FuIGp1bWxhaCBncnVwIHlhbmcgZGl3YWtpbGkgb2xlaCB2YXJpYWJlbCBLLiBWYXJpYWJlbCBLIHNlbmRpcmkgYWRhbGFoIGp1bWxhaCBjbHVzdGVyIHlhbmcgZGlpbmdpbmthbi4NCg0KIyMgRU0NCiAgQWxnb3JpdG1hIF9FeHBlY3RhdGlvbiBNYXhpbWl6YXRvbl8gKEVNKSBhZGFsYWggc3VhdHUgbWV0b2RlIGVzdGltYXNpIHVudHVrIG1lbmVtdWthbiBrZW11bmdraW5hbiBtYWtzaW11bSBkYXJpIHBlcmtpcmFhbiBwYXJhbWV0ZXIgZGFsYW0gbWV0b2RlIHN0YXRpc3Rpay4gQWxnb3J0aW1hIEVNIGFkYWxhaCBzYWxhaCBzYXR1IGFsZ29yaXRtYSB5YW5nIGRpZ3VuYWthbiB1bnR1ayBrbGFzaWZpa2FzaSBhdGF1IHBlbmdlbG9tcG9rYW4gZGF0YS4gRXhwZWN0YXRpb24gTWF4aW1hdGlvbiAoRU0pIHRlcm1hc3VrIGFsZ29yaXRtYSBwYXJ0aXRpb25hbCB5YW5nIGJlcmJhc2lza2FuIG1vZGVsLCBkZW5nYW4gbWVuZ2d1bmFrYW4gcGVyaGl0dW5nYW4gcHJvYmFiaWxpdGFzLCBidWthbiBqYXJhayBzZXBlcnRpIHVtdW1ueWEgYWxnb3JpdG1hIGNsdXN0ZXJpbmcgeWFuZyBsYWlubnlhLg0KDQojIEJBQiAzDQo8YnI+IE1FVE9ET0xPR0kgUEVORUxJVElBTg0KIyMgTWV0b2RlDQogIE1ldG9kZSBhZGFsYWggc3VhdHUgcHJvc2VzIGF0YXUgY2FyYSBzaXN0ZW1hdGlzIHlhbmcgZGlndW5ha2FuIHVudHVrIG1lbmNhcGFpIHR1anVhbiB0ZXJ0ZW50dSBkZW5nYW4gZWZpc2llbnNpLCBiaWFzYW55YSBkYWxhbSB1cnV0YW4gbGFuZ2thaC1sYW5na2FoIHRldGFwIHlhbmcgdGVyYXR1ci4gS2F0YSBtZXRvZGUgKG1ldGhvZCkgYmVyYXNhbCBkYXJpIGJhaGFzYSBMYXRpbiBkYW4ganVnYSBZdW5hbmksIF9tZXRob2R1c18geWFuZyBiZXJhc2FsIGRhcmkga2F0YSBfbWV0YV8geWFuZyBiZXJhcnRpIHNlc3VkYWggYXRhdSBkaSBhdGFzLCBkYW4ga2F0YSBfaG9kb3NfLCB5YW5nIGJlcmFydGkgc3VhdHUgamFsYW4gYXRhdSBzdWF0dSBjYXJhLiBNZXRvZGUgcGVuZWxpdGlhbiBhZGFsYWggbGFuZ2thaC1sYW5na2FoIHlhbmcgZGlhbWJpbCBvbGVoIHBlbmVsaXRpIHVudHVrIG1lbmd1bXB1bGthbiBkYXRhIGF0YXUgaW5mb3JtYXNpIHVudHVrIGRpb2xhaCBkYW4gZGlhbmFsaXNpcyBzZWNhcmEgaWxtaWFoLg0KDQojIyBQYWNrYWdlcw0KICBEYWxhbSBwZW5lbGl0aWFuIGluaSwgcGVuZWxpdGkgbWVtYWthaSBiZWJlcmFwYSBwYWNrYWdlIGRhbGFtIFIuIEJlcmlrdXQgYWRhbGFoIHBhY2thZ2UgeWFuZyBkaW11YXQgZGFsYW0gcGVuZWxpdGlhbiBpbmk6DQpgYGB7cn0NCmxpYnJhcnkoZ2dwbG90MikNCmxpYnJhcnkoRFQpDQpsaWJyYXJ5KEVNQ2x1c3RlcikNCmxpYnJhcnkoRmFjdG9NaW5lUikNCmxpYnJhcnkocmVzaGFwZTIpDQpsaWJyYXJ5KHN1bW1hcnl0b29scykNCmxpYnJhcnkoZHBseXIpDQpgYGANCg0KICBQYWNrYWdlIGBnZ3Bsb3QyYCBtZXJ1cGFrYW4gcGFrZXQgZGkgUiB5YW5nIGJlYmFzIGRpdW5kdWggZGFuIGRpZ3VuYWthbiB1bnR1ayBtZW1idWF0IGJlcmJhZ2FpIGJlbnR1ayBncmFmaWsuIEdyYWZpayB5YW5nIGRpdGFtcGlsa2FuIGJpc2EgYmVydXBhIGRhdGEgbnVtZXJpayBtYXVwdW4gZGF0YSBrYXRlZ29yaWssIHVuaXZhcmlhdCBtYXVwdW4gbXVsdGl2YXJpYXQuIFNlbGFuanV0bnlhLCBwYWNrYWdlIGBEVGAgYWRhbGFoIHBhY2thZ2UgZGF0YXRhYmVsLCB5YW5nIGRhcGF0IGRpZ3VuYWthbiB1bnR1ayBtZW5hbXBpbGthbiBkYXRhIGRhbGFtIGJlbnR1ayB0YWJlbC4gTGFsdSwgcGFja2FnZSBgRU1DbHVzdGVyYCBkaWd1bmFrYW4gcGFkYSBSIHVudHVrIGtsYXN0ZXJpc2FzaSBhbGdvcml0bWEgRU0uIFBhY2thZ2UgYEZhY3RvTWluZVJgIGRpZ3VuYWthbiBwYWRhIFIgdW50dWsgQW5hbGlzaXMgRGF0YSBFa3NwbG9yYXNpIE11bHRpdmFyaWF0IGRhbiBQZW5hbWJhbmdhbiBEYXRhLCBNZXRvZGUgYW5hbGlzaXMgZGF0YSBla3NwbG9yYXNpIHVudHVrIG1lcmluZ2thcywgbWVtdmlzdWFsaXNhc2lrYW4sIGRhbiBtZW5nZ2FtYmFya2FuIGRhdGFzZXQuIEtlbXVkaWFuLCBwYWNrYWdlIGByZXNoYXBlMmAgZGlndW5ha2FuIHVudHVrIG1lbXVkYWhrYW4gZGFsYW0gbWVuZ3ViYWggZGF0YSBhbnRhcmEgZm9ybWF0IHlhbmcgbHVhcyBkYW4gcGFuamFuZy4gTGFsdSwga2VndW5hYW4gcGFja2FnZSBgc3VtbWFyeXRvb2xzYCBwYWRhIFIgYWRhbGFoIG1lbnllZGlha2FuIGFsYXQgdW50dWsgbWVyaW5na2FzIGRhdGEgZGVuZ2FuIHJhcGkgZGFuIGNlcGF0LiBZYW5nIHRlcmFraGlyLCB1bnR1ayBwYWNrYWdlIGBkcGx5cmAgZGFwYXQgZGlndW5ha2FuIHVudHVrIG1lbWFuaXB1bGFzaSBkYXRhLiBQYWNrYWdlIGluaSBzYW5nYXQgYmVyZ3VuYSBrZXRpa2EgZGlndW5ha2FuIHVudHVrIG1lbGFrdWthbiBhbmFsaXNpcyBkYW4gZWtzcGxvcmFzaSBkYXRhLg0KICANCiMjIE1ldG9kZSBQZW5nYW1iaWxhbiBEYXRhDQogIFBhZGEgcGVuZWxpdGlhbiBwZXJiYW5kaW5nYW4gYWxnb3JpdG1hIEstTWVhbnMgZGFuIEVNLCBkYXRhIHlhbmcgZGlwYWthaSBhZGFsYWggZGF0YSBzZWt1bmRlciwgZGVuZ2FuIGthdGEgbGFpbiBkYXRhIGluaSBzdWRhaCBhZGEgZGkgUi4gQmVyaWt1dCBha2FuIGRpaW1wb3J0IGRhdGEgeWFuZyBkaXBha2FpIHBhZGEgcGVyYmFuZGluZ2FuIGRhbGFtIHBlbmVsaXRpYW4gaW5pLg0KDQpgYGB7cn0NCmRhdGF0YWJsZShpcmlzKQ0KYGBgDQojIEJBQiA0DQo8YnI+IEhBU0lMIERBTiBQRU1CQUhBU0FODQoNCiAgRGFsYW0gcGVuZWxpdGlhbiBpbmkgYWthbiBtZW1iYW5kaW5na2FuIGR1YSBjYXJhIHVudHVrIG1lbGFrdWthbiBBbmFsaXNpcyBjbHVzdGVyLCB5YWl0dSBkZW5nYW4gSy1NZWFucyBkYW4gRU0gQWxnb3JpdG1hIGF0YXMgZGF0YSBtZW50YWggZGFuIGtvbXBvbmVuIHV0YW1hIChQQykuIFBDQSBkaWxha3VrYW4gbWVsYWx1aSBmdW5nc2kgUENBKCkgZGFyaSBwYWtldCBgRmFjdG9taW5lUmAuIERlbWlraWFuIHB1bGEsIHVudHVrIGttZWFucyBrYW1pIG1lbmdndW5ha2FuIGZ1bmdzaSBgc3RhdGAgYnVpbHQtaW4uDQoNCmBgYHtyfQ0Kc2V0LnNlZWQoMTIzKQ0KcGNhX2lyaXM9UENBKGlyaXNbLC01XSxzY2FsZS51bml0ID0gVCxuY3AgPSAyLGdyYXBoID0gRikNCmBgYA0KDQpgYGB7cn0NCmlyaXNfc2M9c2NhbGUoaXJpc1ssLTVdLGNlbnRlciA9IFQsc2NhbGUgPSBUKQ0KDQprbV9yYXc9a21lYW5zKGlyaXNfc2MsIGNlbnRlcnM9MykNCg0KZW1vYmogPC0gZXhoYXVzdC5FTShpcmlzX3NjLG5jbGFzcyA9IDMpIA0KZW1vYmogPC0gc2hvcnRlbWNsdXN0ZXIoaXJpc19zYywgZW1vYmosbWF4aXRlciA9IDEwMDApDQplbV9yYXcgPC0gZW1jbHVzdGVyKGlyaXNfc2MsIGVtb2JqLCBhc3NpZ24uY2xhc3MgPSBUUlVFKQ0KDQpkYXRfY2x1c3RfcmF3PWRhdGEuZnJhbWUoaXJpc19zYywiU3BlY2llcyI9YXMuZmFjdG9yKGlyaXMkU3BlY2llcyksIA0KICAgICAgICAgIGttZWFucz1hcy5mYWN0b3Ioa21fcmF3JGNsdXN0ZXIpLCBFTT1hcy5mYWN0b3IoZW1fcmF3JGNsYXNzKSkNCmBgYA0KDQpgYGB7cn0NCmttX3BjYT1rbWVhbnMocGNhX2lyaXMkaW5kJGNvb3JkLCBjZW50ZXJzPTMpDQoNCmVtb2JqX3BjYSA8LSBleGhhdXN0LkVNKHBjYV9pcmlzJGluZCRjb29yZCwgbmNsYXNzID0gMykgDQplbW9ial9wY2EgPC0gc2hvcnRlbWNsdXN0ZXIocGNhX2lyaXMkaW5kJGNvb3JkLCBlbW9ial9wY2EsbWF4aXRlciA9IDEwMDApDQplbV9wY2EgPC0gZW1jbHVzdGVyKHBjYV9pcmlzJGluZCRjb29yZCwgZW1vYmpfcGNhLCBhc3NpZ24uY2xhc3MgPSBUUlVFKQ0KDQpkYXRfY2x1c3RfcGNhPWRhdGEuZnJhbWUocGNhX2lyaXMkaW5kJGNvb3JkLCJTcGVjaWVzIj1pcmlzJFNwZWNpZXMsDQogICAgICAgICAgICAgIGttZWFucz1hcy5mYWN0b3Ioa21fcGNhJGNsdXN0ZXIpLCBFTT1hcy5mYWN0b3IoZW1fcGNhJGNsYXNzKSkNCmBgYA0KDQpFTS1BbGdvcml0bWEgc2VoYXJ1c255YSBtZW1pbGlraSBraW5lcmphIGxlYmloIGJhaWsgZGFyaSBLLW1lYW5zIG5vcm1hbCwga2V0aWthIGJlbnR1ayBzZWJlbmFybnlhIGRhcmkgY2x1c3RlciBhZGFsYWggdGlkYWsgYnVsYXQgYXRhdSBiZXJ1a3VyYW4ga2VjaWwuDQoNCmBgYHtyfQ0KZGF0X3Jhdz1kYXRfY2x1c3RfcmF3ICU+JSBtZWx0KGlkLnZhcj1jb2xuYW1lcyhpcmlzWywtNV0pKQ0KDQpkYXRfcmF3ICU+JSBnZ3Bsb3QoYWVzKHg9U2VwYWwuTGVuZ3RoLHk9UGV0YWwuV2lkdGgsIGNvbG9yPXZhbHVlKSkrZ2VvbV9wb2ludCgpKw0KICBmYWNldF93cmFwKH52YXJpYWJsZSkrdGhlbWVfZ3JleSgpKw0KICB0aGVtZShzdHJpcC5iYWNrZ3JvdW5kID1lbGVtZW50X3JlY3QoZmlsbD0iZGFya3JlZCIpKSsNCiAgdGhlbWUoc3RyaXAudGV4dCA9IGVsZW1lbnRfdGV4dChjb2xvdXIgPSAnd2hpdGUnKSkrZ3VpZGVzKGNvbG9yPUZBTFNFKQ0KYGBgDQoNCmBgYHtyfQ0KZGF0X3BjYT1kYXRfY2x1c3RfcGNhICU+JSBtZWx0KGlkLnZhcj1jKCJEaW0uMSIsIkRpbS4yIikpDQoNCmRhdF9wY2EgJT4lIGdncGxvdChhZXMoeD1EaW0uMSx5PURpbS4yLCBjb2xvcj12YWx1ZSkpK2dlb21fcG9pbnQoKStmYWNldF93cmFwKH52YXJpYWJsZSkrdGhlbWVfZ3JleSgpKw0KICB0aGVtZShzdHJpcC5iYWNrZ3JvdW5kID1lbGVtZW50X3JlY3QoZmlsbD0iZGFya3JlZCIpKSsNCiAgdGhlbWUoc3RyaXAudGV4dCA9IGVsZW1lbnRfdGV4dChjb2xvdXIgPSAnd2hpdGUnKSkrZ3VpZGVzKGNvbG9yPUZBTFNFKQ0KYGBgDQoNCkRhcGF0IGRpbGloYXQgYmFod2EgZGFsYW0ga2VkdWEsIGRhdGEgbWVudGFoIGRhbiBrb29yZGluYXQgUENBLCBFTSB0YW1wYWtueWEgYmVycGVyaWxha3UgZGFuIG1lbGFrdWthbiBwZW5naG9ybWF0YW4geWFuZyBsZWJpaCBiYWlrIHRlcmhhZGFwIEttZWFucy4gQmFuZGluZ2thbiBzZW5kaXJpLiBMaWhhdGxhaCBhc3BlayDigJxTcGVzaWVz4oCdIGRhbiB0ZW11a2FuIG1hbmEgZGFyaSBrZWR1YSBtZXRvZGUgeWFuZyBsZWJpaCBkZWthdCBkZW5nYW4gcmVwcmVzZW50YXNpIGdyYWZpcyB5YW5nIHNlYmVuYXJueWEuDQoNCg0KIyBCQUIgNSANCjxicj4gS0VTSU1QVUxBTiBEQU4gU0FSQU4NCg0KIyMgS2VzaW1wdWxhbg0KICBCZXJkYXNhcmthbiBwZXJoaXR1bmdhbiB5YW5nIHN1ZGFoIGRpbGFrdWthbiBkaSBhdGFzLCBtYWthIGRhcGF0IGRpc2ltcHVsa2FuIGJhaHdhIHdhbGF1cHVuIHRlcmRhcGF0IGJlYmVyYXBhIGhhc2lsIHlhbmcgYmVyYmVkYSwgbmFtdW4gYW5hbGlzaXMgZGF0YSBkZW5nYW4gYWxnb3JpdG1hIEstTWVhbnMgYXRhdSBFTSBkYXBhdCBkaWd1bmFrYW4gdW50dWsgbWVuZ2Vsb21wb2trYW4gZGF0YSBiZXJkYXNhcmthbiBqZW5pc255YS4gRGVuZ2FuIGFkYW55YSBfY2x1c3RlcmluZ18gZGFwYXQgbWVtYmFudHUgbWVtcGVyY2VwYXQgcGVuZ29sYWhhbiBkYXRhIGRhbGFtIG1lbmdlbG9tcG9ra2FuIGp1bWxhaCBkYXRhIGJlcmRhc2Fya2FuIGplbmlzbnlhLiBBbGdvcml0bWEgeWFuZyB0ZXJiYWlrIGRpZ3VuYWthbiB1bnR1ayBtZW5nZWxvbXBva2thbiBkYXRhIGlyaXMgYWRhbGFoIGFsZ29yaXRtYSBFTSwga2FyZW5hIG1lbWlsaWtpIHRpbmdrYXQgcGVyYmVkYWFuIHlhbmcgbGViaWggcmVuZGFoIGRhbiBtZW1pbGlraSB0aW5na2F0IGtlYWt1cmF0YW4geWFuZyBsZWJpaCB0aW5nZ2kuDQogIA0KIyMgU2FyYW4NCiAgUGVuZWxpdGlhbiBpbmkgbWFzaWggbWVydXBha2FuIHBlbmVsaXRpYW4geWFuZyBzZWRlcmhhbmEuIFVudHVrIHBlbmVsaXRpYW4gc2VsYW5qdXRueWEga2lyYW55YSBkYXBhdCBtZW5nZ3VuYWthbiBkYXRhIHlhbmcgbGViaWggbHVhcyBkYW4gZGFwYXQgbWVtYmFuZGluZ2thbiBrZW1iYWxpIGRlbmdhbiBtZXRvZGUgbGFpbm55YS4=