2022-10-02

Hierarchical Clustering

Machine Learning

Clustering

Python

sklearn

Apa itu Hierarchical Clustering

Hierarchical clustering adalah jenis algoritma machine learning yang tidak terpantau yang mengelompokkan objek-objek yang serupa menjadi klaster atau subkelompok berdasarkan kesamaan dan perbedaan mereka. Tujuan dari hierarchical clustering adalah untuk menciptakan hierarki atau struktur pohon dari klaster, di mana klaster di tingkat yang lebih rendah dari pohon lebih mirip satu sama lain daripada yang di tingkat yang lebih tinggi.

Dendrogram

Dendrogram adalah diagram seperti pohon yang memvisualisasikan struktur hierarkis dari klaster. Dalam dendrogram, setiap node mewakili klaster, sedangkan tepi mewakili jarak atau perbedaan antara klaster. Tinggi dari setiap tepi menunjukkan derajat kesamaan antara klaster yang digabungkan atau dibagi. Dengan memeriksa dendrogram, seseorang dapat mengamati struktur pengelompokan pada berbagai tingkat granularitas dan menentukan jumlah klaster optimal berdasarkan pengetahuan domain atau kriteria lainnya.

Dendrogram
Hierarchical clustering explained

Dendrogram slicing
Hierarchical clustering explained

Pendekatan Aglomeratif vs. Divisif

Ada dua pendekatan utama untuk hierarchical clustering: aglomeratif dan divisif.

Hierarchical clustering aglomeratif, juga dikenal sebagai pengelompokan bottom-up, dimulai dengan mempertimbangkan setiap titik data sebagai klaster tunggal. Pada setiap langkah, dua klaster terdekat digabungkan, dan proses ini diulang sampai semua titik data menjadi satu klaster. Hirarki direpresentasikan sebagai dendrogram, diagram seperti pohon yang menggambarkan penggabungan pada level yang berbeda.

Hierarchical clustering divisif, atau pengelompokan top-down, dimulai dengan semua titik data dalam satu klaster. Pada setiap langkah, klaster terbesar atau paling heterogen dibagi menjadi dua klaster kecil, dan proses ini berlanjut sampai setiap titik data membentuk klaster sendiri. Pengelompokan divisif juga menggunakan dendrogram untuk merepresentasikan hierarki klaster.

Agglomerative vs. Divisive Approaches
Hierarchical Clustering Analysis

Hierarchical Clustering Aglomeratif

Pendekatan Bottom-Up

Hierarchical clustering aglomeratif adalah pendekatan bottom-up yang dimulai dengan titik data individual sebagai klaster terpisah dan bergabung secara bertahap menjadi klaster yang lebih besar. Algoritma secara iteratif menggabungkan pasangan klaster yang paling mirip atau terdekat sampai semua titik data menjadi satu klaster. Hasilnya adalah hierarki klaster yang direpresentasikan dengan dendrogram.

Metode Linkage

Proses penggabungan klaster dalam hierarchical clustering aglomeratif tergantung pada pilihan metode linkage. Metode linkage mendefinisikan jarak atau ukuran kesamaan antara klaster, yang menentukan klaster mana yang harus digabungkan pada setiap langkah. Beberapa metode linkage umum meliputi:

Single Linkage

Dalam single linkage, jarak antara dua klaster didefinisikan sebagai jarak minimum antara setiap pasangan titik data dari kedua klaster. Metode ini cenderung menghasilkan klaster yang memanjang seperti rantai dan sensitif terhadap noise dan outliers.

Complete Linkage

Complete linkage mendefinisikan jarak antara dua klaster sebagai jarak maksimum antara setiap pasangan titik data dari kedua klaster. Metode ini menghasilkan klaster yang kompak dan terpisah dengan baik, tetapi sensitif terhadap pilihan klaster awal dan dapat menyebabkan over-segmentation.

Average Linkage

Average linkage menghitung jarak antara dua klaster sebagai rata-rata jarak antara semua pasangan titik data dari kedua klaster. Metode ini menghasilkan klaster dengan bentuk dan ukuran yang seimbang, dan kurang sensitif terhadap noise dan outliers dibandingkan dengan single dan complete linkage.

Centroid Linkage

Centroid linkage menghitung jarak antara dua klaster sebagai jarak antara centroid mereka, yang merupakan vektor rata-rata dari titik data di setiap klaster. Metode ini menghasilkan klaster yang relatif kompak dan seimbang dalam ukuran. Namun, dapat dipengaruhi oleh "fenomena pergeseran centroid", di mana centroid klaster yang digabungkan dapat bergeser secara signifikan, menghasilkan hasil pengelompokan yang suboptimal.

Metode Ward

Metode Ward meminimalkan varians dalam klaster dengan menggabungkan klaster yang menghasilkan peningkatan terkecil dalam jumlah kesalahan kuadrat. Metode ini cenderung menghasilkan klaster yang bulat dan kompak dan cocok untuk data dengan ukuran klaster yang relatif seimbang.

Hierarchical Clustering Divisif

Pendekatan Top-Down

Hierarchical clustering divisif adalah pendekatan top-down yang dimulai dengan semua titik data dalam satu klaster dan secara rekursif membagi klaster menjadi lebih kecil. Algoritma mengidentifikasi klaster terbesar atau paling heterogen pada setiap langkah dan membaginya menjadi dua subklaster berdasarkan strategi pembagian yang dipilih. Proses ini berlanjut sampai setiap titik data membentuk klaster sendiri. Hasilnya adalah hierarki klaster yang direpresentasikan dengan dendrogram, mirip dengan pendekatan aglomeratif.

Strategi Pembagian

Pilihan strategi pembagian dalam hierarchical clustering divisif menentukan bagaimana klaster dibagi pada setiap langkah. Berbagai strategi pembagian telah diusulkan dalam literatur, dengan beberapa yang paling umum adalah:

Berbasis K-means atau K-medoids
Klaster dibagi menjadi dua subklaster menggunakan algoritma K-means atau K-medoids, dengan K diatur menjadi 2.
Berbasis Spectral Clustering
Klaster dibagi berdasarkan vektor eigen dari Laplacian grafik, yang menangkap struktur keterhubungan data.
Berbasis PCA
Klaster dibagi sepanjang arah komponen utama pertama, yang menangkap varians terbesar dalam data.
Berbasis Diameter Maksimum
Klaster dibagi menjadi dua subklaster dengan menemukan pasangan titik data dengan jarak maksimum dan memisahkan titik-titik yang tersisa berdasarkan kedekatan mereka dengan kedua titik tersebut.

Menerapkan Hierarchical Clustering dalam Python

Dalam bab ini, saya akan mendemonstrasikan bagaimana menerapkan hierarchical clustering dalam Python. Kita akan menggunakan dataset publik, menerapkan berbagai metode linkage, dan memvisualisasikan hasil dengan dendrogram dan plot lainnya.

Memuat Dataset dan Pra-pemrosesan

Untuk demonstrasi ini, kita akan menggunakan dataset Iris yang terkenal. Dataset terdiri dari 150 sampel bunga iris, dengan empat fitur (panjang kelopak, lebar kelopak, panjang mahkota, dan lebar mahkota) dan tiga spesies (setosa, versicolor, dan virginica).

Pertama, mari muat dataset dan lakukan pra-pemrosesan data:

import numpy as np
import pandas as pd
from sklearn import datasets

# Load the Iris dataset
iris = datasets.load_iris()
X = iris.data
y = iris.target
target_names = iris.target_names

# Create a DataFrame for easier manipulation
df = pd.DataFrame(X, columns=iris.feature_names)
df['species'] = [target_names[i] for i in y]

Mengeksekusi Hierarchical Clustering

Selanjutnya, kita akan melakukan hierarchical clustering menggunakan kelas AgglomerativeClustering Scikit-learn dan library SciPy untuk visualisasi dendrogram:

python

from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage

# Define the linkage methods to compare
linkage_methods = ['single', 'complete', 'average', 'ward']

# Perform hierarchical clustering with each linkage method
clustering_results = {}
for method in linkage_methods:
    clustering = AgglomerativeClustering(n_clusters=None, distance_threshold=0, linkage=method)
    clustering.fit(X)
    Z = linkage(X, method)
    clustering_results[method] = Z

Memvisualisasikan Dendrogram dengan Metode Linkage yang Berbeda

Kita akan memvisualisasikan dendrogram sekarang:

python

import matplotlib.pyplot as plt
import seaborn as sns

sns.set(style='white', rc={'figure.figsize': (8, 5)})

# Plot dendrograms for each linkage method
for method, Z in clustering_results.items():
    plt.figure()
    plt.title(f'Dendrogram for {method.capitalize()} Linkage', fontsize=12)
    dendrogram(Z, truncate_mode='level', p=5, color_threshold=None, above_threshold_color='k', no_labels=True)
    plt.xlabel('Sample Index', fontsize=14)
    plt.ylabel(f'{method.capitalize()} Distance', fontsize=14)
    plt.grid(False)
    sns.despine()
    plt.show()