1
TEI4N3– Pembelajaran Mesin dan Aplikasi
Topic 9
Unsupervised Learning
FYS,HBU,ITQ
S1 Teknik Elektro- Fakultas Teknik Elektro
Deskripsi 2
Dalam supervise learning, untuk data dalam jumlah banyak diperlukan waktu yang cukup untuk proses labelling
Sehingga umumnya data tersebut diringkas (dipilih beberapa) dan menghasilkan classisfier yang jauh dari harpan.
Sehingga dipelukan suatu classifier tanpa perlu melalui proses labelling yang dilakukansecara manual. Dalam hal ini
unsuppervise learning sangat berperan.
• Ada tiga bagian penting dalam unsuppervise learning:
1. Clustering: melakukan grouping dari instances yang serupa ke dalam satu cluster.
2. Anomaly Detection: untuk mempelajari bagaimanakah data “normal” itu, dan menggunakannya untuk mendeteksi
keadaan abnormal dari instances, seperti item-item yang rusak pada lini produksi atau untuk menemukan trend
pada sebuah time series.
3. Density Estimation: untuk melakukan estimasi probability density function (PDF) dari proses acak yang
menghasilkan dataset tersebut.
2
Clustering 3
Walaupun Joko tidak mengetahui jenis
mangga disamping, tapi Joko tahu
bahwa mangga tersebut berbeda jenis.
Bahkan Joko mungkin perlu pakar
mangga untuk mengenali mangga ini.
Gambar diatas adalah contoh clustering mangga yang didapat dari kebun paman Joko. Walaupun Joko
tidak mengetahui jenis mangganya tapi Joko mengelompokkan berdasarkan kerseragaman.
Dapat dilihat data disamping bahwa secara visual data disamping membentuk
Suatu cluster tanpa label.
Tidak mudah menyimpulkan bahwa data tersebut adalah cluster yang berbeda.
3
Clustering 4
Beberapa aplikasi yang menggunakan clustering:
• Segmentasi pelanggan: segmentasi kustomer sangat berguna pada recommender systems untuk memberikan usulan konten dimana user-user lain
pada cluster yang sama sudah beli atau nikmati.
• Analisis Data: Mengeksekusi algoritma clustering dan menganalisa setiap cluster secara terpisah
• Teknik Reduksi Dimensi: Ketika dataset sudah dibuat cluster, biasanya dimungkinkan untuk mengukur affinity setiap instance (affinity adalah
ukuran seberapa cocok sebuah instance dikategorikan kedalam sebuah cluster).
• Deteksi Anomali: jika kita sudah melakukan clustering terhadap user-user dari website kita berdasarkan behaviour mereka, kita dapat mendetksi
behaviour yang tidak lazim atau di luar kebiasaan, misalkan jumlah request per detik yang tidak lazim.
• Semi-Supervised Learning: Jika kita hanya mempunyai beberapa
Dapat dilihat datalabel, kita bisa melakukan
disamping clusteringvisual
bahwa secara dan mengasosiasikan
data disampinglabel-label pada
membentuk
Suatu cluster tanpa label.
keseluruhan instances di cluster yang sama.
• Tidak
Mesin Pencari: Untuk membangun sistem image mudahkitamenyimpulkan
referensi, dapat menerapkanbahwa data
algoritma tersebut
clustering adalah
pada semua cluster
image yang
di dalam berbeda
database,
sehingga image-image yang serupa akan dikategorikan ke dalam cluster yang sama.
• Segmentasi Citra: Dengan melakukan clustering piksel-piksel berdasarkan wana, kemudian mengganti setiap warna piksel-piksel dengan warna
rata-rata sebuah cluster, maka hal ini memungkinkan kita untuk mengurangi jumlah warna-warna yang berbeda dalam sebuah image.
4
K-Means Clustering 5
K-Means diajukan oleh Stuard Lloyd dari Bell Labs tahun 1957 sebagai teknik pulse code modulation. Pada tahun
1965 Edward W. Forgy mempublikasikan algortma yang sama, sehingg aalgoritma ini disebut Lloyd-Forgy
Terdapat 5 gumpalan dalam sekumpulan instances
5
K-Means Clustering 6
Menempatkan Centroid secara acak yaitu dengan memilih sejumlah k instances dan menggunakan semua lokasinya
sebagai centroid awal. Dilanjutkan dengan melabeli setiap instances, update centroid lagi, hingga lokasi centroid
tidak berubah lagi
Inisialisasi sebanyak k Update setiap centroid
Ulangi prosedur tersebut
centroid secara random, Assign setiap instance yang merupakan rata-rata
hingga konvergen (lokasi
kemudian ditempatkan pada centroid terdekat instanc yang diassign pada
centroid tidak bergerak)
pada masing-masing lokasi centroid sebelumnya
• Pengukuran jarak antra centroid dan instance menggunakan
Euclidean distance
• Tingkat kompleksitas umumnya linier terhadap jumlah
instance (m), jumlah cluster (k) dan jumlah dimensi /feature(n)
6
K-Means 7
Kendatipun algoritma ini dijamin akan konvergen, tetapi bisa jadi tidak
konvergen pada solusi yang tepat (optimal), atau hanya konvergen ke optimum
lokal (suboptimal). Konvergensi ke solusi yang optimal atau suboptimal akan
tergantung pada inisialisasi letak centroid secara acak.
Gambar 6.4 menunjukan kondisi dimana algoritma konvergen hanya pada
solusi suboptimal, jika kita tidak beruntung saat memilih lokasi centroid
pertama kali secara acak
7
K-Means 8
Metode Inisialisasi Centroid
Model inersia=223,3 Model inersia=237,5
Jika lokasi centroid dilakukan dengan perkiraan, maka setting
hyperparameter dapat dilakukan.
Solusi lain adalah dengan mengeksekusi algoritma beberapa kali
dengan inisialisasi acak yang berbeda-beda dan pilihlah solusi terbaik.
Jumlah inisialiasi random dikontrol dengan hyperparameter n_init
(dengan nilai default =10). Model inersia=211,6
Matriks yang digunakan oleh Scikit Learn untuk memilih solusi terbaik
adalah model’s inertia, yang dapat didefinisikan sebagai jarak kuadrat
rata-rata (mean squared distance) antara setiap instance terhadap
centroid terdekat.
Metode score() akan menghasilkan inertia yang negatif karena metode
score() dari prediktor harus mengikuti aturan Scikit Learn yaitu ‘greater
is better’.
8
K-Means 9
Metode Inisialisasi Centroid
Modifikasi yang paling penting untuk memperbaiki kinerja dari algoritma K-Means salah satunya adalah algoritma K-
Means++, yang diajukan pada tahun 2006 oleh David Arthur dan Sergei Vassilvitskii.
1. Ambil satu centroid c(1) yang dipilih secara acak dari dataset.
2. Ambil centroid baru c(i) yang dipilih berdasarkan instance x(i) yang memiliki probabilitas tertinggi, dimana
probablitas didefinisikan sebagai dan adalah jarak instance x(i) terhadap centroid terdekat yang telah dipilih
sebelumnya.
3. Proses sebelumnya berulang sampai semua centroid yang berjumlah k sudah terpilih semuanya.
9
K-Means 10
Menemukan jumlah cluster yang optimum
Tentunya tidak mudah untuk menentukan jumlah
cluster k dan hasilnya akan sangat buruk ketika kurang
tepat menentukan jumlah cluster k.
Dalam menentukan jumlah cluster, parameter inertia
bukan merupakan indikator yang baik karena inertia
kan mengecil ketika menambah k.
K ditentukan berdasarkan posisi elbow dari grafik.
Teknik ini bersifat kasar (tidak presisi),. Pendekatan yang
lebih presisi dapat menggunakan perhitungan
silhouette score.
10
K-Means 11
Menemukan jumlah cluster yang optimum
Harga koefisien Sc bervariasi dari -1 sampai +1.
Koefisien mendekati +1 artinya nstance sudah berada
pada cluster yang benar, harga o berarti instance dekat
dengan perbatasan cluster dan -1 berarti penempatan
cluster yang salah.
Dari gambar disamping terlihat bahwa k=4
adalah yang paling bagus , tetapi k=5 juga tidak
buruk, dan lebih baik dibanding 6 dan 7
Visualisasi yang lebih informatif dapat diperoleh
dengan membuat gambar setiap koefisien
silhouette, diurutkan berdasarkan cluster yang
diassign dan berdasarkan sc.
11
K-Means 12
Menemukan jumlah cluster yang optimum
Setiap diagram berisi grafik berbentuk pisau untuk tiap
cluster. Tinggi grafik menujukkan jumlah instance setiap
cluster , lebarnya menunjukkan sc, garis putus-putus
menunjukkan skor silhouette untuk setiap jumlah cluster
k.
Dapat dilihat skor menujukkan nilai tertinggi pada cluster
k=4 dan k=5. Ketika cluster k=5 semua cluster terlihat
mempunyai ukuran yang sama. Sehingga k=5 merupakan
solusi lain selain k=4.
Untuk contoh listing code dapat dilihat di hands on 6
hal.16.
Untuk analisis silhouette dapat dilihat di link berikut:
Analisis silhouette
Diagram Silhouette
12
K-Means 13
Kekurangan
Selain kelebihan yang dimiliki K-means (Kecepatan dan kemudahan untuk penskalaan) , K-Means memiliki
keterbatasan yaitu:
1. Harus mengeksekusi algoritma beberapa kali
2. Harus menspesifikkan jumlah cluster sebelumnya
3. K-Means tidak berprilaku bai ketika ukuran cluster bervariasi, kerapatan berbeda atau bentuk yang
tidak bundar.
Note:
Untuk menghindari hasil yang buruk, sangat
penting untuk melakukan penskalaan ciri
sebelum mengeksekusikan K-Means.
Penskalaan cluster tidak menjamin semua
cluster terlihat baik dan bundar tapi
setidaknya akan memperbaiki beberapa hal.
13
Contoh Penggunaan Clustering 14
Untuk Segmentasi Citra
14
Contoh Penggunaan Clustering 15
Untuk Segmentasi Citra
Berikut contoh penerapan kalsterisasi warna pada citra dari 2 s/d 10 klaster, dapat dilihat
efek pada sebuah citra bunga
15
Contoh Penggunaan Clustering 16
Untuk Pre-processing
Contoh preprocessing darai data MNIST yang terdiri dari 1797 citra grayscale dengan ukuran 8x8 yang
merepresentasikan digit 0-9:
Hasil tanpa preprocessing Hasil dengan preprocessing
Error rate dapat dikurangi sebesar 1-(1-0.98)/(1-0.96) =0.36
16
Contoh Penggunaan Clustering 17
Untuk Pre-processing
Harga k terbaik merupakan harga yang menghasilkan kinerja klasifikasi pada saat melakukan cross-validation (lihat di chapter sebelumnya). Kita dapat gunakan
GirdSearchCV untuk menemukan jumlah cluster yang optimal pada kasus ini
Jika kita buat harga k semakin besar misalkan s/d 99 (dengan cara
merubah bagian range dari 20 menjadi 100), maka kita akan temukan
bahwa dengan k = 99 akan diperoleh perbaikan keakuratan cukup
signifikan, menjadi 98, 22% pada test set. Atau bahkan kita bisa eksplorasi
k menjadi lebih besar lagi, untuk mendapatkan keakuratan yang lebih
17 besar
Contoh Penggunaan Clustering 18
Untuk Semi-Supervised Learning
Berikut merupakan penilaian pada model hasil training menggunakan regresi logistik dari 50
instances yang mempunyai label dari dataset digit
50 instance yang dilabeli, masing-masing adalah
representatif image dari setiap klaster
Berikut merupakan penilaian pada model hasil training menggunakan regresi logistik dari 50
instances yang mempunyai label dari dataset digit dan menggunakan clusterisasi sebelumnya
(IMAGE REPRESENTATIF)
Dapat dilihat peningkatan kinerja dari sebelumnya
Bagaimana kalau dilakukan propagasi label-label pada instance-instance dari cluster yang
sama?
18
Contoh Penggunaan Clustering 19
Untuk Semi-Supervised Learning
IMPLEMENTASI LABEL PROPAGATION
Didapati kinerja yang lebih baik dari sebelumnya.
Contoh di atas menunjukan perbaikan yang diperoleh ketika proses clustering digunakan
untuk membantu pada saat training set hanya mempunyai sedikit instance yang dilabeli.
19
20
Terima Kasih
20