Machine Learning: Hierarchical Clustering

Catatan penting : Jika Anda benar-benar awam tentang apa itu Python, silakan klik artikel saya ini. Jika Anda awam tentang R, silakan klik artikel ini.

Kali ini saya akan berbagi tentang salah satu teknik dari metode clustering. Seperti sudah diketahui di pembahasan sebelumnya bahwa metode clustering adalah bagian dari unsupervised learning. Artinya bahwa metode ini bisa mengelompokkan data ke dalam beberapa bagian tanpa kita beri contoh, sehingga ia bisa belajar sendiri dari pola-pola yang ada di datanya.

Di metode clustering, saya sebelumnya juga sudah membahas tentang teknik K-Means. Di teknik tersebut, kita sudah menentukan berapa jumlah kluster yang ingin dibuat terlebih dahulu, baru setelah itu algoritma K-Means akan mengelompokkan data sesuai jumlah kluster yang sudah kita tentukan.

Berbeda dengan K-Means, hierarchical clustering (HC) akan mengelompokkan datanya ke dalam beberapa kluster, sampai terbentuklah 1 kluster utuh. Baru dari situ kita pecah-pecah ke dalam beberapa kluster sesuai dengan jumlah yang kita inginkan.

Bisa dikatakan bahwa kita mulai dari belakang (mengelompokkan kluster satu per satu) ke depan (hingga menjadi 1 kluster utuh) lalu sedikit mundur ke belakang (memecah-mecah kluster).

Untuk memudahkan pemahaman, mari kita lihat ilustrasi sebagai berikut:

Ilustrasi dataset sebelum dan setelah aplikasi teknik hierarchical clustering (HC)

Melalui ilustrasi di atas, anggap saja kita belum mengetahui kelompok (kluster) apa saja yang bisa dibuat dari dataset yang kita miliki. Walaupun secara visual (untuk memudahkan) kita bisa tahu bahwa ada 3 kluster yang bisa dibentuk, teknik HC akan membentuk 3 kluster berdasarkan jarak terdekat antara masing-masing data poin yang ada.

Perlu diketahui bahwa teknik HC terdiri dari 2 jenis:

  1. Agglomerative: memulai dari bawah ke atas (bottom up)
  2. Divisive: memulai dari atas ke bawah (top down)

Untuk pembahasan teknik HC kali ini masuk ke dalam jenis agglomerative.


Langkah-langkah HC agglomerative adalah sebagai berikut:

  1. Buat setiap data poin di dataset kita menjadi sebuah kluster, sehingga total kita memiliki N kluster. Artinya jika kita memiliki 800 data, maka kita memiliki 800 kluster juga (1 data = 1 kluster).
  2. Cari 2 kluster yang saling berdekatan satu dengan yang lain, dan jadikan 2 kluster terdekat ini menjadi 1 kluster. Dengan demikian, sekarang kita memiliki N-1 kluster.
  3. Cari 2 kluster yang sakling berdekatan dengan yang lain (termasuk dengan kluster yang baru saja dibuat di langkah 2 jika memang ia memiliki jarak terdekat dengan kluster lain), dan jadikan 2 kluster terdekat ini menjadi 1 kluster. Dengan demikian, sekarang kita memiliki N-2 kluster.
  4. Ulangi terus langkah ketiga, sampai kita hanya memiliki 1 kluster saja.

Mudah bukan? Jadi secara logika, kita hanya mencari 2 kluster dengan jarak terdekat, itu saja. Pertanyaannya sekarang, apa yang dimaksud dengan jarak terdekat?

Jarak yang dimaksud di sini adalah jarak euclidean, yang dijelaskan dengan formula sebagai berikut;

Jarak euclidean antara 2 titik

Jika dua kluster adalah berupa 2 titik (2 data poin) maka sangatlah mudah menghitung jarak euclidean-nya. Namun jika 2 kluster, di mana masing-masing kluster adalah kumpulan dari beberapa titik, maka ada 4 cara mendefinisikan jarak antara keduanya. Pembaca bisa memilih mana saja yang diinginkan, yaitu:

  1. Titik terdekat antara 2 kluster ini
  2. Titik terjauh antara 2 kluster ini
  3. Titik pusat antara 2 kluster ini
  4. Nilai rataan dari jarak antara masing-masing titik di 2 kluster ini

Berikut ilustrasi dari keempat pilihan di atas:

Ilustrasi dari definisi jarak antara 2 kluster. untuk penjelasan no 1, 2, dan 3

Untuk penjelasan dari jarak no 4 (nilai rataan antara masing-masing titik), maka kita menghitung jarak antara satu data poin (anggap a1), dengan satu data poin di kluster yang lain (anggap b1). Setelah itu kita hitung jarak antara a1 dengan b2, a1 dengan b3 dan seterusnya. Kemudian dilanjutkan dengan a2 dengan b1, a2 dengan b2 dan seterusnya. Jika sudah semua, maka langkah akhir adalah tinggal menghitung nilai rataannya.


Sekarang kita akan mulai proses pembentukan klusternya. Kita memiliki 6 buah data poin (untuk memudahkan pemahaman kita hanya memakai 6 data saja). Dengan memiliki 6 data poin, maka kita memiliki 6 kluster. Kita akan mendefinisikan jarak antara 2 kluster sebagai jarak uclidean terdekatnya. Ilustrasinya sebagai berikut:

Proses pertama, mengambil jarak terdekat 2 kluster dan menggabungkan 2 kluster menjadi satu kluster (warna biru muda)

Langkah selanjutnya adalah mencari lagi jarak terdekat dari dua kluster. Perlu diperhatikan bahwa 2 titik berwarna biru muda tadi (di langkah 1) sudah menjadi 1 kluster:

Proses kedua, mencari jarak terdekat 2 kluster dan menjadikannya sebagai 1 kluster (warna hijau)

Dilanjutkan dengan langkah ketiga:


Proses ketiga, mencari jarak terdekat 2 kluster dan menjadikannya sebagai 1 kluster (warna hijau lagi)

Dilanjutkan langkah keempat:


Proses ketiga, mencari jarak terdekat 2 kluster dan menjadikannya sebagai 1 kluster (warna biru muda)

Langkah terakhir adalah menyatukan semuanya menjadi 1 kluster:


Proses ketiga, mencari jarak terdekat 2 kluster dan menjadikannya sebagai 1 kluster (warna biru muda)

Sekarang kita sudah memiliki 1 kluster besar. Namun pertanyaannya, bukankah seharusnya kita membagi-bagi dataset ke dalam beberapa kluster? Mengapa kita hanya memiliki 1 kluster saja? Untuk menjawabnya kita perlu menggunakan teknik elbow method atau dengan dendrogram. Apa itu dendrogram?

Untuk melanjutkan membaca silakan klik halaman berikutnya di bawah ini.

Bagikan artikel ini:

Pages: 1 2 3 4

Leave a Reply

avatar
  Subscribe  
Notify of