Cara Analisis Klaster: Agglomerative Hierarchical Clustering (AHC)

Analisis klaster adalah teknik statistik yang digunakan untuk mengelompokkan objek-objek serupa ke dalam satu atau lebih kelompok atau klaster berdasarkan fitur-fitur yang dimiliki oleh objek tersebut. Metode ini sering digunakan dalam berbagai bidang, seperti ilmu komputer, pemasaran, biologi, dan lain-lain.

Agglomerative Hierarchical Clustering (AHC) adalah salah satu jenis metode klasterisasi hierarki yang biasa digunakan dalam analisis klaster. Istilah "agglomerative" merujuk pada cara metode ini bekerja, yaitu dimulai dengan setiap data point sebagai klaster tersendiri, dan kemudian menggabungkan (agglomerate) klaster-klaster ini berdasarkan tingkat kesamaan antara klaster sampai hanya tersisa satu klaster besar.

Berikut adalah langkah-langkah dasar dalam Agglomerative Hierarchical Clustering:

• Mulai dengan setiap titik data sebagai klaster sendiri.
• Temukan dua klaster yang paling serupa dan gabungkan menjadi satu. Kesamaan antara klaster dapat diukur dengan berbagai cara, tapi yang paling umum adalah jarak Euclidean, jarak Manhattan, atau jarak Cosine.
• Ulangi langkah kedua sampai semua data digabungkan menjadi satu klaster.

Keuntungan dari Agglomerative Hierarchical Clustering adalah struktur hierarki yang dihasilkan dapat dengan mudah ditampilkan dalam bentuk dendrogram, yang menunjukkan cara klaster digabungkan dan jarak antar klaster pada setiap tahap penggabungan. Dendrogram ini dapat membantu analis memahami struktur data dan menentukan jumlah klaster yang optimal. Namun, Agglomerative Hierarchical Clustering juga memiliki beberapa kelemahan. Pertama, metode ini cenderung mahal secara komputasi, terutama untuk dataset besar. Kedua, metode ini tidak memiliki cara untuk "membatalkan" langkah penggabungan sebelumnya jika terbukti suboptimal pada tahap selanjutnya, yang dapat berpotensi menghasilkan klaster yang kurang akurat.

Contoh Kasus

Berikut adalah salah satu contoh kasus yang sering digunakan dalam Analisis Klaster, kasus set data Iris. Set data ini merupakan set data multivariat yang diperkenalkan oleh ahli statistik dan biologi Ronald Fisher dalam artikelnya pada tahun 1936. Set data ini sangat populer dalam berbagai bidang, termasuk Machine Learning dan Statistika.

Set data Iris berisi 150 sampel dari tiga spesies iris (Iris setosa, Iris virginica, dan Iris versicolor). Empat fitur diukur dari setiap sampel: panjang dan lebar sepal, serta panjang dan lebar petal. Pada contoh kasus ini, hanya diambil sampel acak sebanyak 35 sampel dari 150 sampel dengan tujuan untuk mempermudah dan mempercepat proses belajar.

Iris Dataset: Originally published at UCI Machine Learning Repository

Iris Dataset, this small dataset from 1936 is often used for testing out machine learning algorithms and visualizations. The Iris data set is a classification dataset that contains three classes of 50 instances each, where each class refers to a type of iris plant. The three classes in the Iris dataset are: Setosa, Versicolor, Virginica. Each row of the table represents an iris flower, including its species and dimensions of its botanical parts, sepal length, sepal width, petal length and petal width (in centimeters).

Author: R.A. Fisher (1936)

Source: UCI Machine Learning Repository

Langkah-langkah Analisis AHC:

1. Aktifkan lembar kerja (Sheet) yang akan dianalisis.
2. Tempatkan kursor pada Dataset (untuk membuat Dataset, lihat cara Persiapan Data).
3. Apabila sel aktif (Active Cell) tidak berada pada Dataset, SmartstatXL otomatis akan mencoba menentukan Dataset secara otomatis.
4. Aktifkan Tab SmartstatXL
5. Klik Menu Multivariate > Agglomerative Hierarchical Clustering.
   
6. SmartstatXL akan menampilkan kotak dialog untuk memastikan apakah Dataset sudah benar atau belum (biasanya alamat sel Dataset sudah otomatis dipilih dengan benar).
   
7. Apabila sudah benar, Klik Tombol Selanjutnya
8. Selanjutnya akan tampil Kotak Dialog Analisis AHC:
   
9. Pilih Variabel, Metode, dan Output. Pada contoh kasus ini kita tentukan:
   • Variabel: Sepal length, Sepal width, Petal length, dan Petal width
   • Aturan Linkage: Complete
   • Ukuran Jarak: Jarak Euclidean
   • Kluster Berdasarkan: Pilih Observasi (baris)
   • Label Observasi: Species

   Selengkapnya bisa dilihat pada tampilan kotak dialog berikut:
   

   Aturan Linkage

   Metode linkage menentukan bagaimana jarak antara klaster dihitung, dan ada beberapa jenis yang umum digunakan:

   • Single Linkage (Nearest Neighbor): Menghitung jarak antara dua cluster berdasarkan titik terdekat di antara kedua cluster tersebut. Cenderung menghasilkan cluster yang panjang dan tipis dan mungkin rentan terhadap noise dan outlier.
   • Complete Linkage (Farthest Neighbor): Menghitung jarak antara dua cluster berdasarkan titik terjauh di antara kedua cluster tersebut. Cenderung menghasilkan cluster yang lebih kompak dan bulat.
   • Average Linkage: Menghitung jarak antara dua cluster sebagai rata-rata jarak antara setiap titik di satu cluster ke setiap titik di cluster lainnya. Lebih resisten terhadap noise dan outlier daripada single atau complete linkage.
   • Centroid Linkage: Menghitung jarak antara dua cluster berdasarkan jarak antara pusat gravitasi atau centroid dari dua cluster. Rentan terhadap "efek perpindahan" atau "inversi".
   • Ward’s Linkage: Menggabungkan dua cluster yang menghasilkan peningkatan minimum dalam total within-cluster variance setelah digabungkan. Menghasilkan cluster yang umumnya kompak dan seragam.
   • Median Linkage: Mirip dengan Centroid Linkage, namun untuk setiap penggabungan cluster, titik tengah diperbarui dengan mengambil median dari titik tengah cluster yang baru digabungkan.
   • Weighted Linkage (WPGMA): Menghitung jarak antara dua cluster sebagai rata-rata jarak antara setiap titik di satu cluster ke setiap titik di cluster lainnya, sama seperti Average Linkage. Perbedaannya adalah, setiap cluster dalam pasangan memiliki bobot yang sama, tidak peduli berapa banyak titik yang ada di dalamnya.

   Pilihan metode linkage dapat berdampak signifikan pada hasil Agglomerative Hierarchical Clustering, jadi penting untuk memilih metode yang paling sesuai dengan data dan tujuan analisis Anda.

   Ukuran Jarak

   Berikut adalah ringkasan untuk semua ukuran jarak yang digunakan dalam Agglomerative Hierarchical Clustering:

   • Jarak Euclidean: Jarak "garis lurus" antara dua titik dalam ruang n-dimensi. Metode pengukuran jarak yang paling langsung dan intuitif.
   • Jarak Euclidean Kuadrat: Variasi dari jarak Euclidean di mana jarak antara dua titik dikuadratkan. Cocok digunakan ketika Anda ingin memberikan bobot lebih besar pada outlier.
   • Jarak Euclidean Normalized: Jarak Euclidean antara dua titik setelah data telah dinormalisasi sehingga semua variabel memiliki mean 0 dan standar deviasi 1. Pilihan yang baik ketika data Anda memiliki unit yang berbeda atau ketika Anda ingin setiap variabel memiliki bobot yang sama dalam perhitungan jarak.
   • Jarak Manhattan: Jarak total absolut antara dua titik di semua dimensi, dihitung seperti jarak yang ditempuh saat bergerak sepanjang grid kota.
   • Jarak Minkowski: Generalisasi dari jarak Euclidean dan Manhattan. Dengan memilih parameter yang berbeda untuk p dalam rumus Minkowski, kita dapat menghasilkan kedua metrik tersebut.
   • Jarak Cosinus: Bukan mengukur jarak antara dua titik, tetapi mengukur sudut antara dua vektor. Cocok digunakan ketika orientasi dari vektor lebih penting daripada panjang absolut vektor.
   • Jarak Korelasi: Mengukur jarak berdasarkan korelasi antara dua vektor. Cocok untuk dataset di mana Anda ingin mengetahui korelasi antara variabel, bukan jarak aktual.
   • Jarak Chebyshev: Mengukur jarak antara dua vektor sebagai jarak maksimum di sepanjang setiap dimensi. Berfungsi baik untuk data dengan banyak fitur, di mana jarak Euclidean mungkin menjadi terlalu sensitif terhadap outlier.
   • Jarak Kustom: Anda bisa membuat metrik jarak Anda sendiri berdasarkan pengetahuan domain khusus Anda.
   • Jarak Jaccard: Jarak ini dihitung dengan membandingkan perbedaan dan kesamaan antara dua set, sering digunakan untuk data kategorikal atau biner.
   • Jarak Mahalanobis: Jarak ini dihitung dengan mempertimbangkan korelasi antara variabel dan skala variabel. Metrik yang baik untuk digunakan jika data memiliki unit yang berbeda dan ada korelasi yang signifikan antara variabel.

   Pilihan metrik jarak dalam Agglomerative Hierarchical Clustering tergantung pada sifat data dan tujuan analisis.

10. Pilih output Analisis AHC seperti pada tampilan di atas.
11. Tekan tombol OK untuk membuat outputnya dalam Lembar Output

Hasil Analisis

Informasi AHC.

Agglomerative Hierarchical Clustering (AHC) adalah metode analisis klaster yang berusaha untuk mengelompokkan data dalam bentuk hirarki atau struktur pohon. AHC memulai dengan menganggap setiap titik data sebagai klaster tersendiri. Kemudian, ia menggabungkan klaster yang paling mirip satu sama lain dalam langkah-langkah suksessif, sampai semua data berada dalam satu klaster besar. Ada beberapa metode untuk menentukan 'kecenderungan' antara klaster, yang dikenal sebagai metode "linkage".

Dalam kasus ini, kita menggunakan metode 'Complete Linkage'. Complete linkage meminimalkan jarak maksimum antara observasi dari pasangan klaster. Ini berarti bahwa, pada setiap tahap penggabungan, kita melihat pada jarak antara dua klaster yang paling jauh satu sama lain, dan menggabungkan dua klaster yang memiliki jarak maksimum terkecil. Ini berbeda dari metode lain seperti 'Single Linkage', yang melihat pada jarak minimum antara observasi dari pasangan klaster, dan 'Average Linkage', yang melihat pada rata-rata jarak antara observasi dari pasangan klaster.

Untuk menghitung jarak antara titik data, kita menggunakan 'Jarak Euclidean'. Ini adalah metode yang sangat umum dan intuitif untuk menghitung jarak: jarak antara dua titik adalah jarak garis lurus antara mereka, seperti yang akan Anda ukur dengan penggaris jika Anda dapat menarik garis langsung antara titik-titik tersebut.

Variabel yang digunakan dalam analisis ini adalah 'Sepal length', 'Sepal width', 'Petal length', dan 'Petal width'. Dengan kata lain, kita mencoba mengelompokkan spesies iris berdasarkan empat ukuran ini. Diharapkan bahwa spesies yang berbeda akan memiliki ukuran yang berbeda untuk setidaknya beberapa variabel ini, dan oleh karena itu kita dapat mengidentifikasi spesies berdasarkan ukuran mereka.

Tabel Matriks Jarak

Matriks yang di atas adalah matriks jarak yang menggambarkan jarak Euclidean antara setiap pasangan bunga Iris dalam dataset.

• Jarak dalam kelompok: Nilai di sepanjang diagonal adalah nol, yang sesuai dengan fakta bahwa jarak antara titik data dan dirinya sendiri adalah nol. Untuk spesies yang sama, nilai-nilai lainnya menunjukkan jarak antara pasangan bunga. Misalnya, jarak antara bunga Setosa pertama dan kedua adalah 1.367, sementara jarak antara bunga Setosa pertama dan ketiga adalah 0.332. Nilai-nilai ini dapat memberikan wawasan tentang seberapa beragam bunga dalam spesies yang sama.
• Jarak antar kelompok: Anda juga dapat melihat jarak antara dua spesies yang berbeda. Misalnya, jarak antara bunga Setosa pertama dan bunga Versicolor pertama adalah 3.071. Dalam matriks ini, tampaknya jarak antara spesies yang berbeda selalu lebih besar daripada jarak dalam spesies yang sama. Ini menunjukkan bahwa kedua spesies ini dapat dipisahkan dengan baik berdasarkan fitur yang Anda miliki (yaitu Sepal length, Sepal width, Petal length, dan Petal width).
• Insights tentang struktur data: Secara umum, Anda dapat menggunakan matriks ini untuk memahami seberapa dekat setiap pasangan bunga dalam ruang fitur 4-dimensi. Namun, perlu diingat bahwa matriks ini hanya menunjukkan jarak dan tidak memberikan gambaran langsung tentang bagaimana titik-titik data diatur dalam ruang.

Tergantung pada hasil analisis klustering, matriks ini dapat membantu Kita memahami seberapa baik kluster tersebut merangkum struktur data. Misalnya, jika Kita memiliki kluster yang sepenuhnya terdiri dari bunga Setosa dan kluster yang sepenuhnya terdiri dari bunga Versicolor, maka ini bisa menjadi indikasi bahwa klustering bekerja dengan baik karena tampaknya ada jarak yang jelas antara kedua spesies ini.

Dalam analisis hierarchical clustering (AHC), matriks jarak memainkan peran penting. Dalam matriks ini, setiap elemen (i, j) adalah jarak antara sampel i dan j sampel dalam dataset. Matriks ini biasanya bersifat simetris dan semua elemennya adalah non-negatif.

Untuk dataset Iris, dengan asumsi bahwa analisisnya dilakukan pada 4 fitur numerik (panjang sepal, lebar sepal, panjang petal, lebar petal), matriks jarak akan berdimensi 35x35 (karena hanya 35 sampel yang digunakan, dari 150 sampel dataset Iris). Nilai dalam matriks mewakili jarak antara pasangan titik data tersebut. Algoritma AHC kemudian akan menggunakan informasi ini untuk secara bertahap mengelompokkan sampel yang paling dekat satu sama lain, dimulai dari yang memiliki jarak terkecil.

Nilai dalam matriks ini digunakan untuk menentukan bagaimana sampel dikelompokkan bersama dalam hierarki. Misalnya, jika jarak antara sampel 1 dan 2 sangat kecil, mereka kemungkinan besar akan dikelompokkan dalam cluster yang sama pada tahap awal proses pengelompokan. Namun, perlu diingat bahwa interpretasi ini sangat bergantung pada metrik jarak dan metode pengelompokan yang digunakan. Sebagai contoh, Euclidean distance adalah metrik jarak yang umum digunakan, tetapi ada juga metrik lain seperti Manhattan distance atau Minkowski distance. Demikian pula, terdapat berbagai metode pengelompokan dalam AHC, seperti single linkage, complete linkage, average linkage, dan Ward's method, yang semua ini dapat mempengaruhi hasil akhir pengelompokan.

Amalgamation Schedule (Penggabungan)

Tabel di atas adalah output dari proses amalgamation (penggabungan) dalam analisis Hierarchical Clustering. Setiap baris merepresentasikan langkah penggabungan dalam proses clustering, dan ada beberapa informasi yang bisa kita petik dari tabel tersebut.

• Jarak Linkage: Ini adalah jarak antara dua cluster yang digabungkan dalam langkah tersebut. Jarak ini dihitung berdasarkan metode linkage yang dipilih (misalnya single, complete, average, atau Ward's). Nilai jarak ini menunjukkan sejauh mana kedua cluster tersebut dianggap mirip atau berdekatan.
• Setosa, Versicolor, Virginica: Ini adalah label spesies Iris yang mewakili tiap-tiap titik data (atau cluster) yang digabungkan dalam langkah tersebut. Dalam hal ini, label spesies menunjukkan asal titik data tersebut sebelum digabungkan.
  Misalnya, baris pertama menunjukkan bahwa dua titik data dari spesies Setosa digabungkan pada jarak 0.141. Selanjutnya, dalam baris dengan jarak linkage 0.245, kita melihat bahwa ada tiga titik data dengan label Versicolor yang digabungkan menjadi satu cluster.
• Pada baris terakhir, kita melihat bahwa semua titik data telah digabungkan menjadi satu cluster tunggal pada jarak linkage 6.155. Pada tahap ini, kita dapat mengasumsikan bahwa tidak ada lagi penggabungan yang bisa dilakukan (karena semua titik data sudah menjadi bagian dari satu cluster tunggal), dan proses clustering berakhir.

Dengan memahami tabel ini, kita dapat melacak proses clustering dan melihat bagaimana cluster dibentuk dan berkembang seiring dengan peningkatan jarak linkage. Menginterpretasikan hasil seperti ini dapat membantu kita memahami struktur dan hubungan dalam data kita, dan juga membantu memilih titik potong yang tepat dalam dendrogram untuk menentukan jumlah cluster akhir.

Dendrogram

Dari dendrogram tersebut mencerminkan pola yang umum ditemui dalam analisis kluster menggunakan dataset Iris, dan ini sangat berguna dalam menunjukkan kekuatan dan keterbatasan metode pengelompokan hierarkis. Berdasarkan dendrogram tersebut kita bisa menyimpulkan:

• Setosa telah dipisahkan dengan baik ke dalam kluster pertama. Ini mencerminkan fakta bahwa, dalam ruang fitur, Setosa cenderung sangat berbeda dari dua spesies lainnya. Oleh karena itu, dalam sebagian besar metode pengelompokan, Setosa sering kali terpisah dengan baik.
• Versicolor kebanyakan dikumpulkan menjadi kluster kedua. Namun, ada satu instance yang salah diklasifikasikan sebagai Virginica. Ini bisa mencerminkan beberapa hal. Misalnya, titik data Versicolor tersebut mungkin berada dekat dengan batas keputusan antara kluster Versicolor dan Virginica, dan oleh karena itu lebih mirip dengan Virginica dalam hal fitur-fiturnya dibandingkan dengan Versicolor lainnya. Atau, mungkin ada kesalahan pengukuran atau variasi alami dalam data yang membuat titik data tersebut tampak lebih seperti Virginica.
• Virginica kebanyakan berada dalam kluster ketiga, namun ada satu instance Versicolor yang termasuk di dalamnya. Seperti yang dijelaskan sebelumnya, ini mungkin karena titik data tersebut berada di dekat batas antara kluster atau karena variasi dalam data.

Secara umum, interpretasi ini menunjukkan bahwa metode pengelompokan yang digunakan cukup baik dalam mengidentifikasi struktur alami dalam data, meskipun ada beberapa kesalahan. Faktanya bahwa sebagian besar instance dikelompokkan dengan benar menunjukkan bahwa ada beberapa perbedaan fitur yang signifikan antara spesies yang memungkinkan pengelompokan yang efektif. Kesalahan pengelompokan yang ada menunjukkan bahwa ada sejumlah overlap dalam fitur antara Versicolor dan Virginica, sehingga lebih sulit untuk dipisahkan secara sempurna. Ini merupakan hal yang umum dalam analisis kluster di dunia nyata.

Kesimpulan

Dari hasil analisis Agglomerative Hierarchical Clustering (AHC) yang telah dilakukan terhadap dataset iris, didapatkan beberapa temuan yang penting. Dengan menggunakan empat variabel ukuran, yaitu Sepal Length, Sepal Width, Petal Length, dan Petal Width, serta menggunakan metode Complete Linkage dan Jarak Euclidean, terdapat beberapa interpretasi yang dapat ditarik.

• Pertama, metode AHC secara efektif mengidentifikasi tiga klaster utama yang berhubungan erat dengan tiga spesies iris yang ada di dataset. Ini menunjukkan bahwa empat ukuran yang dipilih memiliki kekuatan yang cukup untuk membedakan antara spesies tersebut.
• Kedua, walaupun metode ini cukup efektif, masih ada beberapa kesalahan dalam pengelompokan. Dalam klaster Versicolor, terdapat satu spesies Virginica yang salah dikelompokkan dan dalam klaster Virginica, terdapat satu spesies Versicolor yang salah dikelompokkan. Ini mungkin menunjukkan bahwa ada beberapa penumpang antara spesies tersebut, atau bisa juga karena adanya variabilitas dalam ukuran individu dalam satu spesies.
• Secara keseluruhan, metode AHC menunjukkan efektivitasnya dalam mengklasifikasikan spesies iris berdasarkan empat variabel ukuran. Meski terdapat beberapa kesalahan, metode ini secara umum telah berhasil menunjukkan struktur klaster yang ada dalam data. Dengan mempertimbangkan hasil ini, kita dapat melanjutkan analisis lebih lanjut atau mencoba pendekatan lain untuk melihat apakah kita dapat meningkatkan kinerja pengklasteran.