Metode pengelompokan observasi pada data yang digunakan untuk mempelajari data tanpa label tertentu. Blog kali ini akan membahas metode cluster secara garis besar untuk memberikan gambaran umum metode cluster dan contoh penerapannya. (Ditulis oleh HN Rizka, Februari 2022)
"The aim of science is to seek the simplest explanation of complex facts. Seek simplicity and distrust it" -AN Whitehead
Pernahkah anda membayangkan bagaimana iklan-iklan online yang anda dapati bisa anda dapatkan? Selain itu mungkin anda juga pernah mendapatkan iklan suatu produk/jasa yang saat itu "kebetulan" anda perlukan atau inginkan? Hal inilah yang merupakan salah satu manfaat dari metode clustering. Google secara berkelanjutan memeriksa data traffic anda dan semua pengguna internet lainnya yang kemudian ini digunakan untuk mengkategorikan para pengguna internet ke kelompok-kelompok. Tentunya kriteria pengelompokan tersebut disesuaikan oleh google. Contohnya dalam kasus iklan, produk-produk kecantikan akan lebih disarankan kepada kalangan wanita daripada pria.
Contoh lain untuk manfaat dari clustering dapat anda temui pada marketing produk pada toko online. Konsepnya mirip seperti iklan sebelumnya, namun lebih spesifik ke data belanjaan anda. Untuk melihat ini anda dapat memeriksa homepage anda pada aplikasi toko online yang pernah anda gunakan. Tentu produk-produk yang ditawarkan di halaman tersebut akan mirip dengan apa yang pernah anda beli.
Gambaran Umum
Kedua contoh diatas hanya sebagian kecil manfaat dari clustering yang tentunya telah banyak mempengaruhi kehidupan kita. Definisi dari clustering sendiri adalah metode pemisahan pada data sedemikian terbentuk kelompok-kelompok yang anggota didalam masing-masing kelompok tersebut memiliki kemiripan yang tinggi dan anggota antar kelompok memiliki perbedaan yang berarti. Sederhananya, metode ini bertujuan untuk mengelompokkan observasi-observasi yang "mirip" dalam kelompok. Tentunya bagaimana mendifinisikan kemiripan ini ada berbagai cara. Detail tersebut dibahas dibagian selanjutnya.
Jenis dari cluster/kelompok dibagi menjadi 2 yaitu hard cluster dan soft cluster. Hard clustering merujuk pada pengelompokan sedemikian setiap individu/observasi dalam data hanya termasuk dalam satu cluster/kelompok tertentu. Soft clustering merupakan metode yang menetapkan peluang suatu observasi termasuk ke dalam salah satu dari kelompok. Untuk lebih memahami kedua jenis pengelompokan ini, perhatikan ilustrasi berikut :
Misalkan anda bekerja di divisi pemasaran, kemudian anda diberikan tugas untuk mempelajari customer perusahaan anda sehingga pemasaran perusahaan anda menjadi lebih efektif. Dalam siatuasi ini anda dapat menarik data penjualan dan riwayat pembelian customer. Keadaan diatas dapat anda tangani dengan cara melakukan pengelompokan customer berdasarkan data riwayat pembelian mereka. Seperti contoh customer yang cenderung lebih sering membeli produk makanan ringan dikelompokkan dengan customer lainnya yang juga membeli makanan. Metode pengelompokan ini termasuk kedalam jenis hard clustering. Cara lainnya adalah dengan melihat kecenderungan dalam membeli beberapa produk bersamaan. Misalkan anda menemukan customer yang sering membeli makanan ringan namun di beberapa waktu lainnya dia juga membeli produk perawatan kesehatan. Maka customer tersebut dapat anda berikan peluang termasuk kedalam kelompok "produk makanan" dan kelompok "produk kesehatan". Jenis clustering yang menjadi fokus pembahasan blog ini adalah hard cluster. Selanjutnya dibahas mengenai prosedur kerja clustering.
Algoritma Clustering
Similarity/Dissimilarity antar Observasi
Seperti yang sebelumnya disinggung, tujuan dari clustering adalah mengelompokan observasi yang mirip kedalam kelompok. Kriteria yang diinginkan dari hasil pengelompokan ini adalah indvidu/observasi didalam kelompok memiliki kemiripan yang besar sedangkan individu antar kelompok memiliki perbedaan yang besar. Kriteria ini jika dilihat dari sudut pandang matematika merupakan permasalahan optimasi. Permasalahan optimasi seperti ini memiliki contoh paling mudah seperti pada soal terapan sistem persamaan linear berikut : Penerapan Sistem Persamaan Linear 3 Variabel dalam Kehidupan Sehari-Hari. Pada clustering batasan informasi yang diketahui adalah berupa "jarak" antar observasi. Definisi jarak memiliki beberapa jenis, untuk kali ini kita gunakan jarak euclidean yang merupakan definisi jarak yang paling umum digunakan.
Menggunakan definisi jarak ini, kita dapat membangun konsep kemiripan yang menjadi inti masalah optimasi pada clustering. Definisi jarak sebelumnya dapat diterapkan pada data anda, sehingga ukuran kemiripan antar observasi menjadi terdefinisi. Sebagai contoh, perhatikan data berikut :
Misalkan kita memiliki data dengan 2 variabel dimana keduanya merupakan "fitur" yang digunakan untuk mengkarakterisasi klien suatu bank. Terlihat bahwa antar klien dalam plot memiliki jarak, sehingga kita dapat gunakan jarak tersebut untuk menilai seberapa mirip klien bank tersebut.
Dari ilustrasi diatas, tentu muncul pertanyaan bagaimana jika fitur yang mengkarakterisasi klien bank berjumlah lebih dari 2? Tentunya representasi grafik seperti yang dilakukan diatas tidak dapat digunakan. Namun, jarak euclidean tidak terbatas pada 2 dimensi dan jarak yang kita gunakan untuk mengukur kemiripan observasi masih dapat dihitung walaupun data memiliki fitur/variabel yang sangat banyak. Sebagai tambahan informasi, jarak euclid sebenarnya tidak terlalu baik dalam merepresentasikan jarak di dimensi tinggi, bagi pembaca yang tertarik mendalami ini dapat melihat sesi diskusi "Why is Euclidean distance not a good metric in high dimensions?". Terdapat beberapa alternatif solusi definisi jarak yang tentunya lebih baik, untuk blog ini penulis hanya akan berfokus pada jarak euclid.
Tipe Algoritma Clustering
Setelah memahami ide besar dari konsep kemiripan/similarity, kita dapat melangkah ke pemabahasan prosedur membangun cluster atau prosedur pengelempokan. Ingat kembali tujuan dari cluster adalah selain mengelompokan observasi yang mirip, perbedaan antar cluster juga harus jelas. Pendefinisian perbedaan atau dissimilarity antar cluster inilah yang membedakan satu metode cluster dengan lainnya. Dua tipe paling populer dan sering digunakan adalah hierarchical dan K-means.
Hierarchical Clustering
Sesuai dengan namanya, algoritma ini melakukan pengelompokan secara bertingkat atau hierarkis. Algoritma ini memulai dengan cara menganggap semua individu adalah cluster masing-masing, sehingga ketika kita memiliki N observasi maka pada langkah pertama algoritma ini juga memiliki N cluster. Setiap langkah selanjutnya dalam algoritma ini adalah menggabungkan 2 cluster paling dekat menjadi 1 cluster. Proses ini berlanjut hingga di akhir algoritma semua observasi adalah anggota 1 cluster yang sama atau dengan kata lain hanya tersisa 1 cluster. Dalam alternatif lain, langkah dalam algoritma ini dapat dibalik. Dengan kata lain anda juga dapat memulai dengan menganggap hanya ada 1 cluster dalam data yang kemudian anda memisahkan satu persatu observasi dengan jarak terjauh dari observasi lainnya. Metode yang menggabungkan cluster-cluster kecil sebelumnya dikenal dengan agglomerative (bawah keatas) dan divisive (atas kebawah).
Tentu dari penjelasan tersebut anda tidak menginginkan hasil akhir dari algoritma clustering ini. Entah itu semua observasi merupakan anggota cluster tunggal ataupun setiap oservasi adalah cluster masing-masing. Namun, yang menjadi perhatian adalah pada langkah ke berapa kita berhenti menggabungkan atau memisahkan cluster, sehingga didapatkan pengelompokan yang kita inginkan. Sebagai contoh mari kita fokus pada algoritma agglomerative. Perhatikan matriks berikut
matriks diatas dikenal sebagai matriks dissimilarity yang isinya adalah jarak antar observasi. Seperti contoh jarak antara observasi 1 dengan 2 adalah 2.0622 sedangkan jarak antara observasi 5 dan 9 adalah 0.7089.
Dengan menggunakan data dari matriks tersebut, algoritma hierarchical akan menggabungkan 2 cluster terdekat setiap langkahnya. Pada langkah 1, observasi 9 dan 10 akan digabungkan, sehingga setalah langkah satu selesai kita memiliki 9 cluster. Langkah selanjutnya memerlukan definisi jarak cluster ketika terdapat lebih dari 1 anggota. Dalam algoritma hierarchical kita dapat menggunakan beberapa pilihan diantaranya seperti complete linkage (jarak 2 titik terjauh antara 2 cluster) dan single linkage (jarak 2 titik terdekat antara 2 cluster). Setelah semua langkah selesai dan tersisa satu cluster, dapat digambarkan dendogram yang menggambarkan proses penggabungan cluster yang telah dilakukan.
Menggunakan dendogram tersebut, kita dapat menentukan berapa kelompok/cluster yang kita inginkan pada data tersebut. Pemilihan ini dapat dilakukan secara subjektif dengan melihat dendogram atau dapat berdasarkan informasi prior mengenai keadaan data. Pilihan banyaknya cluster yang terbaik adalah garis horizontal yang dapat memotong jarak maksimum secara vertikal tanpa memotong cluster. Pada contoh dendogram diatas, banyaknya cluster yang terbaik adalah 3 dengan menarik garis merah berikut
Hasil clustering pada matriks dissimilarity sebelumnya adalah : cluster 1 berisi observasi 8, cluster 2 berisi obsrvasi 1, 2, 4, 5, 9, dan 10 serta cluster 3 berisi observasi 3, 6, dan 7. Plot untuk hasil pengelompokan ini dapat dilihat dibawah :
Terlihat bahwa hasil yang didapatkan cukup mencapai tujuan yaitu anggota dalam cluster memiliki kemiripan yang tinggi sedangkan anggota antar cluster memiliki perbedaan yang besar. Tujuan ini dapat dipastikan selalu tercapai ketika anda menggunakan algoritma hierachical. Secara matematis, algoritma ini akan selalu mencapai solusi unik yang relatif pada definisi jarak anda. Hal ini karena tidak ada "keacakan" selama langkah pengelompokan.
Keunggulan dari algoritma hierarchical adalah kemudahan dalam memahami prosedur kerja dan penerapan pada data. Selain itu, penentuan cluster cukup jelas yaitu dengan melihat dendogram dan tidak memerlukan informasi tambahan. Namun, kekurangan yang jelas terlihat adalah ketika menghadapi data dengan jumlah observasi yang banyak. Kekurangan ini sangatlah berpengaruh pada lama proses pengerjaan/komputasi. Kemudian adalah mengenai ukuran similarity yang mana selain dari kekurangan dari definisi jarak, skala variabel yang berbeda akan menyebabkan permasalahan saat langkah penggabungan cluster. Contoh dari masalah skala dapat anda lihat pada makalah berikut : The problem of scale . Algoritma selanjutnya akan menjadi solusi terhadap masalah komputasi pada hierarchical. Selain itu, varian dari algoritma tersebut juga lebih baik dalam menangani perbadaan skala variabel.
K - Means Clustering
Setelah membahas mengenai algoritma hierarchical sebelumnya, anda setidaknya dapat membayangkan prosedur yang dilakukan untuk mencapai pengelompokan data yang diharapkan. Algoritma kedua merupakan metode iteratif, artinya dalam setiap langkahnya terdapat "perbaikan" dari hasil yang didapatkan sebelumnya (Selengkapnya : iterative method). Jika algoritma hierarchical melakukan penggabungan/pemisahan cluster hingga mencapai banyaknya cluster yang sesuai. K - means langsung menempatkan tiap observasi pada cluster yang sesuai. Hal ini mengimplkasikan bahwa pada k - means anda menentukan banyaknya cluster yang ingin anda buat pada data diawal prosedur.
Untuk memulai algoritma k - means, tentukan banyaknya cluster. Misalkan data contoh sebelumnya akan kita cluster menjadi 3 cluster. Setelah itu, kita menentukan "mean" dari setiap cluster. Mean ini jika dapat diibaratkan sebagai titik pusat dari cluster. Pada langkah pertama kita akan melakukan "inisiasi" atau memberikan nilai input untuk titik pusat setiap cluster.
Setelah menentukan titik pusat pertama ini, setiap observasi dihitung jaraknya terhadap tiap pusat. Masing-masing observasi kemudian dimasukkan kedalam cluster terdekat. Seperti pada gambar diatas, terlihat ada 3 titik observasi yang dekat dengan pusat merah. Maka ketiga titik tersebut menjadi bagian dari cluster merah tersebut. Selanjutnya dilakukan "perbaikan" pada titik pusat cluster setelah terdapat anggota baru di tiap cluster. Didapatkan hasil sebagai berikut :
Setelah langkah pertama diatas, terlihat bahwa cluster yang terbentuk sama dengan hasil hierarchical clustering sebelumnya. Tentunya langkah selanjutnya dilanjutkan dengan menghitung jarak tiap titik observasi dengan pusat-pusat baru dan tempatkan observasi ke cluster terdekat. Algoritma ini berhenti ketika tidak ada perubahan pada cluster dari langkah sebelumnya. Pada contoh data diatas, tidak perubahan cluster pada langkah kedua sehingga algoritma dikatakan sudah konvergen ke solusi.
Jika dibandingkan dengan algoritma hierarchical, terlihat bahwa k means lebih cepat dalam mendapatkan solusinya pada data contoh diatas. Tentunya ini karena pemilihan pusat awal yang "baik". Dalam penentuan titik pusat di langkah pertama ini, anda harus berhati-hati dengan keadaan data. Hal ini karena jika anda memilih titik awal yang "buruk" hasil yang anda dapatkan juga akan buruk dalam artian tidak mencapai solusi optimal dalam masalah clustering. Bahkan, lebih buruk lagi adalah ada kemungkinan ada cluster kosong saat langkah pertama dengan kata lain solusi pun tidak bisa anda dapatkan.
Salah satu saran terbaik dalam memilih titik awal ini adalah dengan memastikan lokasinya cukup tersebar dan dekat dengan setidaknya satu observasi. Alternatif lain adalah dengan mencoba beberapa himpunan lokasi titik awal secara acak. Dalam R anda dapat mengacak lokasi awal pusat cluster ini dan mencoba beberapa inisiasi berbeda yang hasilnya dapat anda bandingkan. Hal ini memudahkan anda untuk mendapatkan solusi optimal relatif terhadap himpunan titik pusat awal yang anda coba tersebut.
Terkait pemilihan banyaknya cluster pada algoritma k means terdapat beberapa metode. Salah satunya adalah metode elbow. Pada metode ini, anda melakukan pembandingan seberapa baik hasil clustering untuk banyaknya cluster k secara terurut. Kemudian, proporsional terhadap k, tingkat kualitas untuk hasil clustering dibandingkan dan anda dapat memutuskan pada perubahan terkecil pertama yang terjadi. Contohnya adalah pada plot berikut :
Plot diatas menunjukkan kualitas hasil clustering data contoh sebelumnya menggunakan jumlahan kuadrat "within" atau dikenal dengan within sum of square (WSS). WSS dalam clustering merepresentasikan persebaran total didalam cluster. Tentunya kita ingin WSS yang rendah. Namun ingat bahwa WSS akan bernilai 0 atau tidak ada persebaran sama sekali ketika banyaknya cluster sama dengan banyaknya observasi. Sehingga dari metode ini kita ingin perubahan WSS yang cukup sedikit dari 2 nilai k terdekat. Pada plot diatas, perubahan WSS dari k sama dengan 3 ke 4 mulai bernilai cukup kecil. Artinya, hasil reduksi WSS dari penambahan 1 cluster untuk k sama dengan 3 tidaklah terlalu berarti dan dapat diputuskan bahwa k = 3 adalah banyaknya cluster optimal pada data tersebut.
Kekurangan terbesar pada k means selain dari spesifikasi banyaknya cluster adalah skala variabel. Nilai ekstrim juga menjadi momok karena ingat kembali bahwa mean sangat sensitif terhadap nilai ekstrim. Pembahasan lebih detail akan mengarahkan anda pada bentuk dari cluster yang sederhananya merujuk pada pola bentuk cluster. K means sangat buruk dalam menangani bentuk cluster non convex.
Setelah membahas kedua jenis algoritma clustering paling populer diatas, penulis akan merangkum perbedaan keduanya :
Hierarchical tidak cukup baik dalam menangani data besar dibandingkan k means karena kompleksitas tiap langkahnya membebani penghitungan/komputasi.
Solusi yang didapatkan pada hierarchical adalah unik dan reproducible relatif pada metode jarak yang digunakan. Sedangkan pada k means solusinya sangat bergantung pada titik awal yang digunakan.
Jika anda memiliki prior information tentang banyaknya cluster pada data, maka k means menjadi metode yang disarankan. Di sisi lain, anda masih dapat menggunakan k means walau tidak ada prior information tentang banyaknya cluster pada data. Caranya adalah dengan mengambil "contoh" dari data anda dan melakukan hierarchical clustering pada contoh tersebut. Hasilnya dapat anda gunakan sebagai dasar pemilihan k pada k means.
Pada model clustering yang lebih kompleks, beberapa kendala yang dialami k means dan hierarchical dapat diantisipasi. Tentunya ini menjadi topik yang penulis ingin bagi suatu saat. Untuk menutup blog kali ini, mari kita terapkan analisis cluster untuk data klien.
Penerapan pada Data Klien
Sesuai dengan permasalahan sebelumnya, kita ingin mencoba mengkarakterisasi klien bank berdasarkan variabel yang disediakan. Untuk penerapa clustering, kita lupakan keberadan label "default.payment.." dan melakukan clustering berdasarkan pada hasil PCA pada blog PCA.
Prosedur setelah mendapatkan komponen adalah melakukan pengambilan contoh untuk menentukan banyaknya cluster optimal. Tentu saja idealnya kita menginginkan agar data bisa dibagi menjadi 2 cluster sedemikian prediksi apakah klien akan mangkir dari pemabayaran dapat dilakukan. Berdasarkan eksplorasi awal menggunakan beberapa contoh data didapatkan bahwa banyaknya cluster optimal adalah 2.
Selanjutnya dilakukan penerapan prosedur clustering dengan algoritma k means. Hasilnya adalah sebagai berikut :
Dengan melakukan analisis perbandingan hasil clustering cengan label asli didapatkan bahwa pendekatan terbaik adalah dengan menganggap cluster 1 sebagai label "0" pada variabel default.payment... Dengan kata lain, cluster 1 merupakan kelompok dengan individu yang cenderung patuh dalam membayar tagihan kreditnya. Sedangkan cluster kedua merupakan kelompok dengan individu yang resiko mangkir pembayaran kreditnya tinggi. Akurasi dari prediksi menggunakan clustering pada data klien sendiri adalah : specificity = 0.35 dan sensitivity = 0.74. Ini dapat dilihat dari confusion matrix berikut :
Secara keseluruhan, prediksi menggunakan clustering pada data klien ini cenderung lebih buruk dibandingkan model regresi logistik pada data klien. Namun, metode clustering ini cenderung lebih memiliki sensitivitas tinggi. Dengan kata lain, prediksi clustering untuk klien yang akan mangkir dari pembayaran kredit lebih akurat dari regresi logistik.
Seluruh kode yang digunakan di blog ini dapat anda replikasi dengan software R dan dapat anda lihat di github penulis : clustering .
Comments