Pengantar Hierarchical Clustering di Python

Motivasi

Bayangkan Anda seorang Data Scientist di perusahaan ritel. Atasan Anda meminta agar Anda membagi pelanggan ke dalam kelompok berikut: pelanggan rendah, rata-rata, menengah, atau platinum berdasarkan perilaku belanja untuk keperluan pemasaran terarah dan rekomendasi produk.

Mengetahui bahwa tidak ada label historis yang terkait dengan pelanggan tersebut, bagaimana mungkin mengkategorikan mereka? 

Di sinilah clustering dapat membantu. Ini adalah teknik machine learning tanpa pengawasan yang digunakan untuk mengelompokkan data tanpa label ke dalam kategori yang serupa. 

Tutorial ini akan lebih berfokus pada pendekatan hierarchical clustering, salah satu dari banyak teknik dalam machine learning tanpa pengawasan. Kita akan mulai dengan gambaran umum tentang apa itu hierarchical clustering, sebelum membandingkannya dengan beberapa teknik yang sudah ada.

Kemudian, Anda akan dipandu langkah demi langkah implementasinya di Python menggunakan pustaka populer Scipy.

Definisi Hierarchical Clustering

Pendekatan hierarchical clustering didasarkan pada penentuan klaster berturut-turut berdasarkan klaster yang telah didefinisikan sebelumnya. Ini adalah teknik yang lebih diarahkan untuk mengelompokkan data ke dalam pohon klaster yang disebut dendrogram, yang secara grafis merepresentasikan hubungan hierarkis antar klaster yang mendasarinya.

Perbandingan Hierarchical Clustering dengan Teknik Clustering Lain

Hierarchical clustering adalah algoritme yang kuat, tetapi bukan satu-satunya, dan setiap jenis clustering memiliki kelebihan dan kekurangannya masing-masing. 

Mari pahami bagaimana perbandingannya dengan jenis clustering lain, seperti K-means dan model-based clustering. Masih banyak teknik lainnya, namun kedua teknik tersebut, selain hierarchical clustering, digunakan secara luas dan memberikan kerangka untuk membantu memahami yang lain dengan lebih baik. 

Anda dapat mempelajari lebih lanjut tentang clustering dalam machine learning di artikel terpisah kami, yang membahas lima algoritme clustering esensial. 

Hierarchical clustering vs K Means clustering

Tidak seperti Hierarchical clustering, K-means clustering berupaya membagi titik data asli menjadi sejumlah “K” kelompok atau klaster di mana pengguna menentukan “K” terlebih dahulu. 

Gagasan umumnya adalah mencari klaster yang meminimalkan jarak Euclidean kuadrat dari semua titik ke pusatnya pada seluruh atribut (variabel atau fitur) dan menggabungkan individu-individu tersebut secara iteratif. 

Tutorial K-means Clustering di Python dengan Scikit-learn kami akan membantu Anda memahami cara kerja internal K-means clustering dengan studi kasus yang menarik.

Keuntungan 

• Lebih efisien secara komputasi dibanding hierarchical clustering dan dapat digunakan untuk menganalisis kumpulan data besar. 
• K-means lebih mudah dipahami dan diimplementasikan. 

Kekurangan

• Kurang fleksibel dibanding hierarchical clustering karena membatasi pengguna untuk menentukan jumlah klaster terlebih dahulu, yang mungkin tidak jelas dalam beberapa situasi.  
• Hasilnya tidak stabil dan berubah dari satu iterasi ke iterasi lain untuk kumpulan data yang sama.
• Lebih sensitif terhadap outlier karena keberadaan outlier memengaruhi nilai rata-rata klaster. 
• Baik k-means maupun hierarchical clustering tidak mampu menangani data kategorikal secara langsung dan mungkin tidak bekerja baik pada data yang tidak kontinu atau memiliki varians yang sangat besar.

Terlepas dari keterbatasannya, k-means clustering tetap menjadi metode populer karena kemudahan penggunaan dan efisiensi komputasinya. Metode ini sering digunakan sebagai tolok ukur untuk membandingkan kinerja teknik clustering lainnya. 

Model-based clustering

Baik K-means maupun hierarchical clustering menggunakan matriks jarak untuk merepresentasikan jarak antar semua titik dalam dataset. Di sisi lain, model-based clustering menerapkan teknik statistik untuk mengidentifikasi klaster dalam data. Berikut proses umumnya: 

• Tentukan model statistik yang akan digunakan dan pilih jumlah klaster. 
• Fitting model pada data. 
• Identifikasi klaster berdasarkan parameter model.

Keuntungan 

• Model-based clustering lebih fleksibel dibanding hierarchical clustering karena memungkinkan penggunaan berbagai model untuk mengidentifikasi berbagai jenis klaster. 
• Bekerja lebih baik pada data dengan bentuk atau struktur yang kompleks.

Kekurangan

• Lebih mahal secara komputasi dibanding hierarchical clustering, terutama untuk data besar. 
• Memerlukan pemahaman yang lebih baik tentang teknik pemodelan statistik karena pemilihan model dapat memengaruhi hasil akhir. 
• Sama seperti K-means clustering, memerlukan penentuan jumlah klaster terlebih dahulu. 

Aplikasi Hierarchical Clustering

Hierarchical clustering memiliki beragam aplikasi dalam kehidupan sehari-hari, termasuk (namun tidak terbatas pada) biologi, pemrosesan citra, pemasaran, ekonomi, dan analisis jejaring sosial.

Biologi

Pengelompokan urutan DNA adalah salah satu tantangan terbesar dalam bioinformatika. 

Ahli biologi dapat memanfaatkan hierarchical clustering untuk mempelajari hubungan genetik antar organisme guna mengklasifikasikan organisme tersebut ke dalam kelompok taksonomi. Ini bermanfaat untuk analisis cepat dan visualisasi hubungan yang mendasarinya.  

Pemrosesan citra

Hierarchical clustering dapat diterapkan dalam pemrosesan citra untuk mengelompokkan wilayah atau piksel serupa pada sebuah gambar dalam hal warna, intensitas, atau fitur lainnya. Ini dapat berguna untuk tugas lanjutan seperti segmentasi gambar, klasifikasi gambar, dan pengenalan objek.

Pemasaran

Spesialis pemasaran dapat menggunakan hierarchical clustering untuk menyusun hierarki antara berbagai tipe pelanggan berdasarkan kebiasaan belanja mereka demi strategi pemasaran yang lebih baik dan rekomendasi produk. Misalnya, produk yang berbeda di ritel dapat direkomendasikan kepada pelanggan apakah mereka termasuk pembelanja rendah, menengah, atau tinggi.

Analisis jejaring sosial

Jejaring sosial merupakan sumber informasi berharga ketika dimanfaatkan secara efisien. Hierarchical clustering dapat digunakan untuk mengidentifikasi kelompok atau komunitas serta memahami hubungan antar kelompok dan struktur jaringan secara keseluruhan.

Algoritme Hierarchical Clustering

Pada bagian ini, kita akan melihat tiga konsep utama. Langkah-langkah algoritme hierarkis, sorotan dua jenis hierarchical clustering (agglomerative dan divisive), dan akhirnya, beberapa teknik untuk memilih ukuran jarak yang tepat.

Langkah-langkah dalam algoritme hierarchical clustering

Algoritme hierarchical clustering menggunakan ukuran jarak untuk menghasilkan klaster. Proses pembentukan ini melibatkan langkah-langkah utama berikut: 

Praproses data dengan menghapus data hilang dan menerapkan tugas tambahan apa pun agar data menjadi sebersih mungkin. Langkah ini bersifat umum untuk sebagian besar tugas machine learning. 

1. Hitung matriks jarak yang berisi jarak antara setiap pasangan titik data menggunakan metrik jarak tertentu seperti jarak Euclidean, jarak Manhattan, atau kemiripan kosinus. Namun metrik jarak default adalah Euclidean.

2.Gabungkan dua klaster yang jaraknya paling dekat. 

3. Perbarui matriks jarak terkait dengan klaster baru.  

4. Ulangi langkah 1, 2, dan 3 hingga semua klaster digabungkan menjadi satu klaster. 

Contoh hierarchical clustering 

Kita dapat menganggap agglomerative dan divisive clustering sebagai cermin satu sama lain. Mari lihat lebih detail bagaimana masing-masing bekerja, beserta contoh hierarchical clustering dan visualisasi grafisnya. 

Agglomerative hierarchical clustering

Skenario pertama ini sesuai dengan pendekatan yang dijelaskan di atas. Dimulai dengan menganggap setiap observasi sebagai klaster tunggal (klaster dengan hanya satu titik data). Kemudian secara iteratif menggabungkan klaster hingga hanya tersisa satu klaster. Proses ini juga dikenal sebagai pendekatan bottom-up. 

Seperti terlihat pada ilustrasi di bawah ini: 

• Kita mulai dengan menganggap setiap hewan sebagai klaster yang unik.  
• Lalu kita membentuk tiga klaster berbeda dari hewan-hewan unik tersebut berdasarkan kemiripannya: 
• Burung: Elang dan Merak
• Mamalia:  Singa dan Beruang
• Hewan berkaki lebih dari tiga: Laba-laba dan Kalajengking.
• Kita ulangi proses penggabungan untuk membuat klaster vertebrata dengan menggabungkan dua klaster yang paling mirip: Burung dan Mamalia.
• Setelah langkah ini, dua klaster yang tersisa, Vertebrata dan Lebih dari tiga kaki, digabungkan untuk membentuk satu klaster Hewan. 

Dendrogram Pendekatan Agglomerative Clustering

Divisive clustering

Di sisi lain, divisive clustering bersifat top-down karena dimulai dengan menganggap semua titik data sebagai satu klaster unik. Kemudian memisahkannya hingga semua titik data menjadi unik.

Dari grafik pendekatan divisive ini: 

• Kita perhatikan bahwa seluruh dataset hewan dianggap sebagai satu blok. 
• Kemudian, kita membagi blok tersebut menjadi dua klaster: Vertebrata dan Lebih dari 3 kaki. 
• Proses pembagian diterapkan secara iteratif pada klaster yang sebelumnya dibuat hingga kita mendapatkan hewan-hewan yang unik. 

Dendrogram Pendekatan Divisive Clustering

Memilih ukuran jarak yang tepat

Pilihan ukuran jarak adalah langkah krusial dalam clustering, dan bergantung pada masalah yang ingin Anda selesaikan. Dalam skenario berikut, kita dapat mengelompokkan siswa berdasarkan berbagai pendekatan seperti: 

• Negara asal
• Jenis kelamin, laki-laki atau perempuan
• Latar belakang akademik sebelumnya.

Semua ini adalah klaster yang valid namun berbeda maknanya. 

Meskipun jarak Euclidean adalah jarak yang paling umum digunakan di sebagian besar perangkat lunak clustering, ukuran jarak lain seperti jarak Manhattan, jarak Canberra, korelasi Pearson atau Spearman, dan jarak Minkowski juga ada.

Cara mengukur klaster sebelum menggabungkannya

Jarak-jarak yang disebutkan sebelumnya terkait dengan item. Pada bagian ini, kita akan membahas tiga cara standar (tidak eksklusif) untuk mengukur pasangan klaster terdekat sebelum menggabungkannya: (1) Single linkage, (2) Complete linkage, dan (3) Average linkage. 

Single linkage

Dari semua jarak berpasangan antar item di dua klaster C1 dan C2, single linkage mengambil jarak antarklaster sebagai jarak minimum. 

Jarak (C1, C2) = Min { d(i, j), di mana item i berada dalam C1, dan item j berada dalam C2}

Dari semua pasangan item dari dua klaster, yang disorot hijau memiliki jarak minimum. 

Ilustrasi single linkage

Complete linkage

Dari semua jarak berpasangan antar item di dua klaster C1 dan C2, single linkage mengambil jarak antarklaster sebagai jarak maksimum. 

Jarak (C1, C2) = Max { d(i, j), di mana item i berada dalam C1, dan item j berada dalam C2}

Dari semua pasangan item dari dua klaster, yang disorot hijau memiliki jarak maksimum.

Ilustrasi complete linkage

Average linkage

Pada average linkage clustering, jarak antara dua klaster C1 dan C2 adalah rata-rata jarak antar semua pasangan item di kedua klaster.

Jarak (C1, C2) = Jumlah{ d(i, j) } / Jumlah total jarak

Ilustrasi average linkage

​Kemudian average linkage clustering dilakukan sebagai berikut 

d(a,j) + d(a,h) + d(a,n) + d(d,j) + d(d,h) + d(d,n)  

—-----------------------------------------------------------, di mana Jumlah total jarak = 6

  Jumlah total jarak

Mengimplementasikan Hierarchical Clustering di Python

Sekarang Anda memahami cara kerja hierarchical clustering. Pada bagian ini, kita akan fokus pada implementasi teknis menggunakan Python.

Jika Anda lebih tertarik melakukan implementasi dengan bahasa pemrograman R, tutorial Hierarchical clustering di R kami adalah tempat yang tepat untuk mulai.

Menyiapkan lingkungan 

Untuk memulai, Anda perlu memasang Python di komputer Anda, bersama pustaka berikut:

• Pandas untuk memuat data frame. 
• Scikit-learn untuk melakukan normalisasi data.
• Seaborn dan matplotlib untuk visualisasi.
• Scipy untuk menerapkan clustering.

Anda dapat memasang pustaka-pustaka ini menggunakan pip, manajer paket Python, sebagai berikut:

pip install scikit-learn
pip install pandas

pip install matplotlib seaborn

pip install scipy

Selanjutnya, mari impor modul yang diperlukan dan muat dataset. Kita akan menggunakan dataset iris bawaan dari scikit-learn, yang berisi informasi tentang berbagai jenis bunga iris.

Untuk mengilustrasikan use case dengan lebih baik, kita akan menggunakan Loan Data yang tersedia di DataLab. Seluruh kode dalam tutorial ini tersedia di buku kerja DataLab ini; Anda dapat dengan mudah membuat salinannya sendiri untuk menjalankan kode di browser, tanpa perlu memasang perangkat lunak apa pun di komputer Anda.

Memahami data

Dataset memiliki 9.500 pinjaman dengan informasi tentang struktur pinjaman, peminjam, dan apakah pinjaman dilunasi penuh. Kita akan menghapus kolom target not.fully.paid untuk memenuhi aspek tanpa pengawasan.

import pandas as pd
loan_data = pd.read_csv("loan_data.csv")
loan_data.head()

Lima baris pertama data pinjaman

Instruksi berikut menunjukkan bahwa data memiliki 9.578 baris, dan 14 kolom bertipe numerik kecuali purpose, yang bertipe object dan memberikan deskripsi tekstual tujuan pinjaman. 

loan_data.info()

Informasi tentang data

Prapemrosesan data 

Sebelum penerapan clustering, data perlu dipraproses untuk menangani informasi yang hilang, menormalkan nilai kolom, dan menghapus kolom yang tidak relevan.

Menangani nilai hilang

Dari keluaran di bawah, kita perhatikan tidak ada nilai hilang dalam data.

percent_missing =round(100*(loan_data.isnull().sum())/len(loan_data),2)
percent_missing

Persentase nilai hilang dalam data

Hapus kolom yang tidak diinginkan

Kita akan menganalisis data pinjaman menggunakan semua kolom kecuali yang berikut: 

• Purpose
• Not.fully.paid, karena ini adalah label yang menyatakan apakah peminjam melakukan pelunasan penuh atau tidak.

cleaned_data adalah data tanpa kolom-kolom di atas. 

cleaned_data = loan_data.drop(['purpose', 'not.fully.paid'], axis=1)
cleaned_data.info()

Gambar di bawah menunjukkan informasi dari data baru.

Data baru tanpa kolom yang tidak diinginkan

Analisis outlier

Salah satu kelemahan hierarchical clustering adalah sensitif terhadap outlier.  Distribusi setiap variabel ditunjukkan oleh boxplot. 

def show_boxplot(df):
plt.rcParams['figure.figsize'] = [14,6]
sns.boxplot(data = df, orient="v")
plt.title("Outliers Distribution", fontsize = 16)
plt.ylabel("Range", fontweight = 'bold')
plt.xlabel("Attributes", fontweight = 'bold')
   
show_boxplot(cleaned_data)

Boxplot semua variabel dalam data

Saldo berputar peminjam (revol_bal) adalah satu-satunya atribut dengan titik data yang jauh dari yang lain. 

Dengan menggunakan pendekatan interquartile range, kita dapat menghapus semua titik yang berada di luar rentang yang ditentukan oleh kuartil +/-1,5 * IQR, di mana IQR adalah InterQuartile Range. 

Ini dicapai dengan fungsi pembantu berikut. 

def remove_outliers(data):
   
df = data.copy()
   
for col in list(df.columns):
 
      Q1 = df[str(col)].quantile(0.05)
      Q3 = df[str(col)].quantile(0.95)
      IQR = Q3 - Q1
      lower_bound = Q1 - 1.5*IQR
      upper_bound = Q3 + 1.5*IQR
 
      df = df[(df[str(col)] >= lower_bound) & 

        (df[str(col)] <= upper_bound)]
   
return df

Kemudian, kita dapat menerapkan fungsi tersebut ke dataset. 

without_outliers = remove_outliers(cleaned_data)

Sekarang kita dapat memeriksa boxplot baru dan membandingkannya dengan yang sebelum penghapusan outlier. 

show_boxplot(without_outliers)

Tidak ada lagi titik data yang berada di luar interquartile range.

without_outliers.shape

Bentuk data sekarang 9.319 baris dan 12 kolom. Ini berarti 259 observasi merupakan outlier, yang telah dihapus. 

Skalakan ulang data

Karena hierarchical clustering menggunakan jarak Euclidean, yang sangat sensitif saat menangani variabel dengan skala berbeda, sebaiknya semua variabel diskalakan ulang sebelum menghitung jarak. 

Ini dilakukan menggunakan kelas StandardScaler dari sklearn. 

from sklearn.preprocessing import StandardScaler

data_scaler = StandardScaler()

scaled_data = data_scaler.fit_transform(without_outliers)
scaled_data.shape

Bentuk data tetap sama (9.319 baris, 12 kolom) karena normalisasi tidak memengaruhi bentuk data. 

Menerapkan algoritme hierarchical clustering 

Semua prasyarat terpenuhi untuk masuk lebih dalam ke implementasi algoritme clustering. 

Pada titik ini, kita dapat memutuskan pendekatan linkage mana yang akan diadopsi untuk clustering di atribut method dari metode linkage(). Pada bagian ini, kita akan membahas ketiga teknik linkage menggunakan jarak euclidean. 

Ini dilakukan dengan kode di bawah setelah mengimpor pustaka yang relevan.

from scipy.cluster.hierarchy import linkage, dendrogram

complete_clustering = linkage(scaled_data, method="complete", metric="euclidean")
average_clustering = linkage(scaled_data, method="average", metric="euclidean")
single_clustering = linkage(scaled_data, method="single", metric="euclidean")

Setelah kita menghitung ketiga clustering tersebut, dendrogram yang sesuai ditunjukkan sebagai berikut, dimulai dengan complete clustering  

dendrogram(complete_clustering)
plt.show()

Dendrogram pendekatan complete clustering

dendrogram(average_clustering)
plt.show()

Dendrogram pendekatan average clustering

dendrogram(single_clustering)
plt.show()

Dendrogram pendekatan single clustering

Menginterpretasikan hasil (memvisualisasikan dendrogram, menentukan jumlah klaster)

Untuk setiap pendekatan linkage, bagaimana dendrogram dibangun dan setiap titik data pada akhirnya bergabung ke dalam satu klaster. 

• Sumbu x dari dendrogram merepresentasikan sampel dalam data.
• Sumbu y merepresentasikan jarak antar sampel tersebut. Semakin tinggi garisnya, semakin tidak mirip sampel/klaster tersebut.
• Kita mendapatkan jumlah klaster yang sesuai dengan menggambar garis horizontal melalui garis vertikal tertinggi itu, dan jumlah perpotongan sesuai dengan jumlah klaster. 

Jumlah klaster optimal dapat diperoleh dengan mengidentifikasi garis vertikal tertinggi yang tidak berpotongan dengan klaster lain (garis horizontal). Garis seperti itu ditemukan di bawah ini dengan lingkaran merah dan tanda centang hijau.   

• Untuk complete linkage, itu adalah garis biru di sebelah kanan, dan menghasilkan tiga klaster. 

Jumlah klaster optimal dari jarak tertinggi tanpa perpotongan (complete linkage)

• Untuk average linkage, itu adalah garis vertikal biru pertama, dan menghasilkan dua klaster.

Jumlah klaster optimal dari jarak tertinggi tanpa perpotongan (average linkage)

• Untuk single linkage, itu adalah garis vertikal pertama, dan hanya menghasilkan satu klaster. 

Jumlah klaster optimal dari jarak tertinggi tanpa perpotongan (single linkage)

Dari pengamatan di atas, average linkage tampaknya memberikan clustering terbaik, berbeda dengan single dan complete linkage, yang masing-masing menyarankan mempertimbangkan satu klaster dan tiga klaster. Selain itu, jumlah klaster optimal sebesar dua sesuai dengan pengetahuan awal kita tentang dataset, yaitu dua jenis peminjam. 

Sekarang setelah kita menemukan jumlah klaster optimal, mari lihat apa arti klaster tersebut berdasarkan skor kredit peminjam.

cluster_labels = cut_tree(average_clustering, n_clusters=2).reshape(-1, )
without_outliers["Cluster"] = cluster_labels

sns.boxplot(x='Cluster', y='fico', data=without_outliers)

Dari boxplot di atas, kita dapat mengamati bahwa: 

• Peminjam dari klaster 0 memiliki skor kredit lebih tinggi.  
• Sedangkan peminjam dari klaster 1 memiliki skor kredit lebih rendah.

Cluster Analysis in Python bisa menjadi langkah berikut yang baik untuk mendalami K-means dan hierarchical clustering menggunakan pustaka Scipy. 

Kesimpulan

Artikel ini telah membahas apa itu hierarchical clustering, kelebihan dan kelemahannya, serta bagaimana perbandingannya dengan k-means dan model-based clustering. 

Kami berharap artikel ini memberi Anda keterampilan yang relevan untuk secara efisien mengelompokkan data tanpa label Anda untuk pengambilan keputusan yang dapat ditindaklanjuti.