top of page
Gambar penulisCornellius Yudha Wijaya

Memahami Proses Agglomerative Clustering

Memahami Proses Agglomerative Clustering

Jika Anda tidak memahami gambar di atas, bisa dimaklumi karena gambar ini kebanyakan hanya ditemukan dalam jurnal atau buku teks biologi.


Gambar di atas adalah pohon filogeni spesies (species phylogeny tree), yaitu pohon biologi historis yang digunakan untuk melihat seberapa dekat spesies satu sama lain. Dalam istilah yang lebih umum, jika Anda familiar dengan Hierarchical Clustering, pada dasarnya itulah yang dimaksud. Lebih tepatnya adalah metode bottom-up atau Agglomerative clustering untuk membuat pohon filogeni yang disebut Neighbour-Joining.


Agglomerative Clustering


Pendahuluan

Pada machine learning, unsupervised learning adalah model yang mempelajari pola data tanpa panduan atau label. Ada banyak model termasuk dalam family unsupervised learning, tetapi salah satu model favorit saya adalah Agglomerative Clustering.


Agglomerative Clustering atau bottom-up clustering pada dasarnya dimulai dari individual cluster (setiap titik data dianggap sebagai klaster individu, disebut leaf/daun), kemudian dihitung jarak/distance setiap klaster dengan klaster lainnya. Dua klaster dengan jarak terpendek akan bergabung membentuk apa yang kita sebut node/simpul.


Klaster yang baru terbentuk sekali lagi dihitung jaraknya dengan klaster lain di luar klaster mereka. Proses ini diulang hingga semua titik data dimasukkan ke satu klaster yang disebut root/akar. Hasilnya adalah representasi objek berbasis pohon yang disebut dendrogram.


Sebagai pengingat, walaupun kita diberikan hasil bagaimana data harus dikelompokkan, Agglomerative Clustering tidak memberikan angka pasti tentang berapa banyak kelompok yang seharusnya ada pada data kita. Kita perlu menentukan sendiri titik cut-off untuk pengelompokkan data tersebut.


Memahami Proses Agglomerative Clustering

Mari kita uraikan langkah-langkahnya secara lebih rinci. Untuk mempermudah, saya hanya akan menjelaskan cara kerja Agglomerative Clustering menggunakan parameter yang paling umum.


Pengukuran Jarak


Proses Agglomerative Clustering dimulai dengan mengukur jarak antara titik data. Cara perhitungannya bagaimana? Saya akan beri contoh dengan data dummy berikut.


#creating dummy data
import pandas as pd
dummy = pd.DataFrame([[30,100,5],
              [18, 200, 2],
              [35, 150, 7],
             [48, 300, 4],
             [50, 200, 6]], index = ['Anne', 'Ben', 'Chad', 'Dave', 'Eric'], columns =['Age', 'Expense($)', 'Distance(KM)'])
Memahami Proses Agglomerative Clustering

Misalkan kita memiliki 5 orang berbeda dengan 3 fitur kontinu yang berbeda dan kita ingin melihat bagaimana kita bisa mengelompokkan orang-orang ini.


Pertama-tama, kita perlu menentukan pengukuran jarak klaster kita. Salah satu pengukuran jarak yang paling umum digunakan adalah Euclidean Distance.

Memahami Proses Agglomerative Clustering
Perhitungan Euclidean Distance

Euclidean Distance, istilah sederhananya adalah garis lurus dari titik x ke titik y. Saya akan memberikan contoh dengan menggunakan jarak antara Anne dan Ben dari data dummy kita.


Dalam data dummy, kita memiliki 3 fitur (atau dimensi) yang mewakili 3 fitur kontinu yang berbeda. Dalam hal ini, kita bisa menghitung Euclidean Distance antara Anne dan Ben menggunakan rumus di bawah ini.


Memahami Proses Agglomerative Clustering

Jika kita memasukkan semua angkanya, maka akan seperti ini.

Memahami Proses Agglomerative Clustering

Menggunakan pengukuran Euclidean Distance, kita memperoleh 100,76 untuk Euclidean Distance antara Anne dan Ben. Jika kita menerapkan pengukuran ini ke semua titik data harus menghasilkan matriks jarak sebagai berikut.


import numpy as np
from scipy.spatial import distance_matrix

pd.DataFrame(np.round(distance_matrix(dummy.values, dummy.values), 2), index = dummy.index, columns = dummy.index)
Memahami Proses Agglomerative Clustering

Setelah itu, kita menggabungkan jarak non-zero terkecil dalam matriks untuk membuat node pertama kita. Dalam hal ini adalah Ben dan Eric.


Memahami Proses Agglomerative Clustering

Dengan node atau klaster baru, kita perlu memperbarui matriks jarak kita.


Memahami Proses Agglomerative Clustering

Sekarang kita memiliki klaster baru Ben dan Eric, tetapi kita masih tidak tahu jarak antara klaster (Ben, Eric) dengan titik data lainnya. Bagaimana kita menghitung jarak klaster baru? Untuk melakukan ini, kita perlu menentukan linkage criterion terlebih dahulu.


Linkage Criterion

Linkage criterion adalah dimana jarak antar data diukur secara tepat. Ini adalah aturan yang kita buat untuk menentukan jarak antar klaster.


Ada banyak jenis linkage criterion, kali ini saya hanya akan menggunakan linkage paling sederhana yang disebut Single Linkage. Bagaimana cara kerjanya? Saya akan menunjukkan dengan gambar di bawah ini.

Memahami Proses Agglomerative Clustering

Dalam single linkage criterion kita mendefinisikan jarak sebagai jarak minimum antara titik data klaster. Jika kita menuliskan dalam rumus matematika maka akan terlihat seperti ini.


Memahami Proses Agglomerative Clustering

Di mana jarak antara klaster X ke klaster Y didefinisikan oleh jarak minimum antara x dan y yang merupakan anggota klaster X dan klaster Y.


Mari kita lihat contoh berikut. Jika kita menerapkan single linkage criterion ke data dummy kita, misalnya antara Anne dan klaster (Ben, Eric) akan dijelaskan dengan gambar di bawah ini.

Memahami Proses Agglomerative Clustering

Dengan single linkage criterion, kita memperoleh Euclidean Distance antara Anne ke klaster (Ben, Eric) adalah 100,76. Menerapkan single linkage criterion ke data dummy akan menghasilkan matriks jarak berikut.

Memahami Proses Agglomerative Clustering

Sekarang, kita memiliki jarak antara klaster baru dengan titik data lainnya. Meskipun jika Anda perhatikan, sekarang jarak antara Anne dan Chad menjadi yang yang terkecil. Maka, penggabungan berikutnya adalah antara Anne dan Chad.

Memahami Proses Agglomerative Clustering

Kita terus melakukan penggabungan hingga semua data dikelompokkan ke dalam satu klaster. Pada akhirnya, kita akan mendapatkan dendrogram dengan semua data yang telah digabungkan ke dalam satu klaster.

from scipy.cluster.hierarchy import linkage, dendrogram
import matplotlib.pyplot as plt

den = dendrogram(linkage(dummy, method='single'), 
labels = dummy.index)
plt.ylabel('Euclidean Distance', fontsize = 14)
plt.title('Dendrogram of the Dummy Data')
plt.show()
Memahami Proses Agglomerative Clustering

Menentukan Jumlah Klaster


Kita sudah mendapatkan dendrogram, jadi apa yang kita lakukan dengannya? Kita akan menggunakannya untuk memilih jumlah klaster untuk data kita. Ingat, dendrogram hanya menunjukkan hierarki data kita; tidak memberikan kita jumlah klaster yang paling optimal.


Cara terbaik untuk menentukan jumlah klaster adalah dengan melihat dendrogram dan memilih nilai tertentu sebagai titik cut-off (cara manual). Biasanya, kita memilih titik cut-off yang memotong garis vertikal tertinggi. Saya akan menunjukkan contoh dengan gambar di bawah ini.

Memahami Proses Agglomerative Clustering

Jumlah perpotongan dengan garis vertikal yang dibuat oleh garis horizontal akan menghasilkan jumlah klaster.


Memilih titik cut-off pada nilai 60 akan memberi kita 2 klaster berbeda (Dave dan (Ben, Eric, Anne, Chad)). Memilih titik cut-off yang berbeda akan memberi kita jumlah klaster yang berbeda juga. Misalnya, jika kita menggeser titik cut-off ke 52.

Memahami Proses Agglomerative Clustering

Kali ini, dengan titik cut-off di 52 kita akan mendapatkan 3 klaster berbeda (Dave, (Ben, Eric), dan (Anne, Chad)).


Pada akhirnya, kitalah yang memutuskan jumlah klaster yang masuk akal untuk data kita. Dalam hal ini, memiliki domain knowledge tentang data akan sangat membantu.


Dan tentu saja, kita bisa secara otomatis menemukan jumlah klaster terbaik melalui metode tertentu; tetapi saya percaya cara terbaik untuk menentukan jumlah klaster adalah dengan mengamati hasil yang dihasilkan oleh metode clustering.


Model Agglomerative Clustering

Misalkan saya memilih nilai 52 sebagai titik cut-off. Berarti saya akan mendapatkan 3 klaster. Dengan pengetahuan ini, kita bisa mengimplementasikannya ke dalam model machine learning.

from sklearn.cluster import AgglomerativeClustering
aglo = AgglomerativeClustering(n_clusters=3, affinity='euclidean', linkage='single')
aglo.fit_predict(dummy)

Model Agglomerative Clustering akan menghasilkan [0, 2, 0, 1, 2] sebagai hasil clustering. Kita kemudian bisa mengembalikan hasil clustering ke data dummy. Dalam kasus saya, saya beri nama ‘Aglo-label’.


dummy['Aglo-label'] = aglo.fit_predict(dummy)
Memahami Proses Agglomerative Clustering

Sekarang data saya telah dikelompokkan, dan siap untuk analisis lebih lanjut. Penting untuk menganalisis hasilnya karena unsupervised learning hanya mempelajari pola data, tetapi jenis pattern yang dihasilkan memerlukan analisis yang lebih mendalam.


Kesimpulan

Agglomerative Clustering adalah anggota dari Hierarchical Clustering yang bekerja dengan menggabungkan setiap klaster tunggal dengan proses yang diulang-ulang hingga semua data menjadi satu klaster.

Langkah-langkah yang dilakukan oleh Agglomerative Clustering adalah:

  1. Setiap titik data ditetapkan sebagai klaster tunggal

  2. Tentukan pengukuran jarak dan hitung matriks jarak

  3. Tentukan linkage criteria untuk menggabungkan klaster

  4. Perbarui matriks jarak

  5. Ulangi proses hingga setiap titik data menjadi satu klaster


Dengan dendrogram, kita bisa memilih nilai cut-off untuk memperoleh jumlah klaster.

Pada akhirnya, Agglomerative Clustering adalah metode unsupervised learning dengan tujuan untuk mempelajari data.


Hasil akhirnya masih tergantung pada kita bagaimana menginterpretasikan hasil klasterisasi tersebut.

148 tampilan0 komentar

Postingan Terkait

Lihat Semua

Komentar


bottom of page