UNSUPERVISED LEARNING : HIERARCHYCAL CLUSTERING - AGGLOMERTIVE

Hai ini blog ku nikmatilah karyaku

setelah kita bertemu dengan anggota pertama dari unsupervised learning, berikutnya kita akan bertemu dengan clustering yang kedua yaitu hierarchycal dengan metode agglomerative

Analisis Klaster

Analisis Klaster merupakan salah satu metode statistik yang bertujuan untuk memisahkan objek ke dalam beberapa klaster (kelompok data) yang mempunyai sifat :

• Objek memiliki karakteristik yang serupa dalam satu klaster
• Objek memiliki karakteristik berbeda antar klaster

Secara umum, analisis klaster dibagi menjadi dua yaitu 1] Hierarchical Clustering dan 2] Non Hierarchical Clustering. Perbedaan diantara kedua metode tersebut adalah pada 1] Hierarchical Clustering, jumlah klaster ditentukan kemudian dan pengelompokkan objek ke dalam klaster dilakukan secara bertahap; sedangkan pada 2] Non Hierarchical Clustering, jumlah klaster ditentukan di awal dan pengelompokkan objek ke dalam klaster dilakukan sekaligus.

Hierarchical Clustering

Metode analisis klaster secara hierarki dapat dibedakan menjadi dua yaitu : 1] Divisive dan 2] Agglomerative. Pada metode 1] Divisive, dimulai dengan membuat satu klaster yang memuat seluruh objek/pengamatan, kemudian objek yang paling berbeda ‘kemiripannya’ dipisahkan dari klaster demikian seterusnya hingga setiap objek terpisah dan menjadi satu klaster. Sebaliknya, pada metode 2] Agglomerative, setiap objek dianggap sebagai satu klaster kemudian dua objek yang memiliki ‘kemiripan’ digabungkan menjadi satu klaster demikian seterusnya hingga terbentuk satu klaster yang terdiri atas keseluruhan objek.

Algoritma atau langkah-langkah dari metode Agglomerative adalah sebagai berikut:

1. Anggap sebuah data memiliki N objek atau pengamatan. Dimulai dengan N klaster, yang masing-masing berisikan entitas yang merupakan matriks simetris dengan jarak D :
   D=di,k$$D=d_{i,k}$$
2. Cari jarak matriks terdekat pada pasangan klaster. Kemudian beri nama jarak antar klaster U dan V dengan nama
   du,v$$d_{u,v}$$
3. Gabungkan klaster U dan V menjadi klaster UV.
4. Ulangi langkah (2) dan (3) sebanyak N-1 kali hingga tersisa satu klaster yang memuat seluruh objek atau pengamatan.

Metode Pengukuran Jarak pada Agglomerative.

Pendekatan dalam mengukur kesamaan suatu objek dengan objek lainnya adalah dengan menggunakan jarak antar pasangan objek. Pasangan objek yang memiliki jarak yang lebih dekat akan lebih ‘mirip’ karakteristiknya dibandingkan dengan pasangan objek yang memiliki jarak yang lebih jauh. Salah satu metode untuk mengukur jarak antar objek adalah dengan menggunakan Euclidian Distance. Misal terdapat dua objek ( u dan v ) dan sebanyak p variabel, maka Euclidian Distance-nya adalah :

du,v=(u21−v21)+(u22−v22)+...+(u2p−v2p)−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√$$d_{u,v}=\sqrt{(u_1^2-v_1^2)+(u_2^2-v_2^2)+...+(u_p^2-v_p^2)}$$

Kemudian setelah diketahui Euclidian Distance dari masing-masing pasangan objek dalam data, pengelompokkannya dapat dilakukan berdasarkan metode berikut:

• Single Linkage

Klaster dibentuk berdasarkan pasangan objek dengan jarak terdekat.

du,vw=min(du,w,dv,w)$$d_{u,v}w=min(d_{u,w},d_{v,w})$$

• Complete Linkage

Klaster dibentuk berdasarkan pasangan klaster dengan jarak terjauh.

du,vw=max(du,w,dv,w)$$d_{u,v}w=max(d_{u,w},d_{v,w})$$

Selain dua diatas, terdapat metode pengukuran jarak lainnya, yaitu Average Linkage dan Metode Ward. Namun yang akan dibahas disini hanya metode Single Linkage dan Average Linkage dengan metode Agglomerative.

Contoh Kasus : Pengelompokkan Negara di ASEAN

Data yang digunakan adalah data indikator kependudukan negara-negara Asia Tenggara pada tahun 2015. Data Indikator yang tercakup hanya yang terkait dengan kelahiran dan kematian. Indikator tersebut adalah :

1. Total Fertility Rate (TFR), yaitu rata-rata jumlah anak yang dilahirkan hidup oleh wanita pada akhir masa reproduksinya.
2. Angka Kematian Bayi (AKB), yaitu banyaknya kematian bayi per 1000 kelahiran hidup.
3. Angka Kematian Ibu (AKI), yaitu banyaknya kematian ibu per 100000 penduduk. Kematian ibu yang dicatat adalah kematian ibu yang terjadi pada saat kehamilan, atau selama 42 hari sejak terminasi kehamilan yang disebabkan atau diperparah oleh proses kehamilan tersebut.
   
4. Angka Harapan Hidup (AHH), yaitu rata-rata tahun hidup yang masih akan dijalani oleh seseorang yang telah berhasil mencapai umur x, pada suatu tahun tertentu, dalam situasi mortalitas yang berlaku di lingkungan masyarakatnya.

Tujuan dilakukannya analisis kluster adalah untuk mengklasterkan negara-negara ASEAN berdasarkan indikator kependudukanya yang meliputi indikator kematian dan kelahiran. Indikator kematian dan kelahiran penduduk dapat digunakan untuk mengetahui kualitas kesehatan penduduk di negara-negara ASEAN. Namun, untuk memudahkan dalam penghitungan secara manual, hanya dipilih 5 negara saja yaitu : Indonesia, Malaysia, Filipina, Singapura, dan Thailand.

Data beserta syntax yang ada di artikel ini dapat diunduh disini

Load Library

library(readr)  #Membaca data
library(dplyr)  #Data processing
library(DT)     #Menampilkan tabel agar mudah dilihat di browser

Input Data

asean_data <- read_csv("asean_demografi.csv")
asean_data <- asean_data[c(3,5,7,8,9), ] #Memilih 5 negara : Indonesia, Malaysia, Filipina, Singapura, dan Thailand.
datatable(asean_data, caption = "Indikator Demografi Negara ASEAN 2015")

Show 102550100 entries

Search:

Indikator Demografi Negara ASEAN 2015

	Negara	TFR	AKB	AKI	AHH
1	Indonesia	2.4	22.2	126	70.8
2	Malaysia	2	6.9	23.8	74.8
3	Filipina	2.9	23	114	70.4
4	Singapura	1.2	1.7	7.1	82.9
5	Thailand	1.5	6.2	24.6	74.6

Showing 1 to 5 of 5 entries

Previous1Next

Tahapan Sebelum Analisis Klaster

Normalisasi Data

Karena data yang digunakan memiliki satuan dan rentang yang berbeda, maka perlu dilakukan standardisasi data terlebih dahulu sebelum masuk ke analisis klaster. Untuk melakukan standardisasi data ke dalam normal baku di R dapat menggunakan fungsi scale()

data_standardized <- scale(asean_data[,2:5]) #Hanya memilih kolom/variabel yang berisikan indikator kelahiran dan kematian

Menghitung Matriks Distance

Matriks distance merupakan matriks yang berisikan pasangan jarak antar objek yang dihitung dengan Euclidian Distance. Dalam R, matriks distance dapat dihitung dengan menggunakan fungsi dist()

d <- dist(x = data_standardized, method = "euclidean")
d

##           1         2         3         4
## 2 2.5849735                              
## 3 0.7720948 2.7819009                    
## 4 4.2043427 2.0834816 4.5462924          
## 5 2.8619600 0.7378601 3.2146810 1.7964452

Memulai Analisis Klaster

Metode 1. Single Linkage

DENGAN R

Untuk melakukan metode Single Linkage, dalam R dapat menggunakan fungsi hclust() kemudian memasukkan argument ‘single’ pada parameter ‘method’.

hc_single <- hclust(d = d, method = "single")

MENGHITUNG MANUAL

Gambaran metode Single Linkage adalah klaster baru dibuat dengan cara mencari jarak pasangan objek yang nilainya terkecil di dalam matriks distance. Kemudian menghitung matriks distance baru berdasarkan jarak terdekat dengan klaster yang terbentuk sebelumnya.

1. Menampilkan matriks distance

	1	2	3	4	5
1	0	2.58	0.77	4.20	2.86
2	2.58	0	2.78	2.08	0.74
3	0.77	2.78	0	4.55	3.21
4	4.20	2.08	4.55	0	1.80
5	2.86	0.74	3.21	1.80	0

min(du,v)=d5,2=0.74$$min(d_{u,v})=d_{5,2}=0.74$$

sehingga negara ke-2 dan ke-5 digabungkan menjadi 1 klaster.

2. Menghitung jarak baru tiap objek dengan klaster yang baru terbentuk (negara ke-2 dan ke-5)

d(5,2)1=min(2.86,2.58)=2.58$$d_{(5,2)1}=min(2.86,2.58)=2.58$$

d(5,2)3=min(3.21,2.78)=2.78$$d_{(5,2)3}=min(3.21,2.78)=2.78$$

d(5,2)4=min(2.08,1.80)=1.80$$d_{(5,2)4}=min(2.08,1.80)=1.80$$

3. Menampilkan matriks distance baru

	(52)	1	3	4
(52)	0	2.58	2.78	1.80
1	2.58	0	0.77	4.20
3	2.78	0.77	0	4.55
4	1.80	4.20	4.55	0

min(du,v)=d3,1=0.77$$min(d_{u,v})=d_{3,1}=0.77$$

sehingga negara ke-1 dan ke-3 digabungkan menjadi 1 klaster.

4. Menghitung jarak baru tiap objek dengan klaster yang baru terbentuk (negara ke-1 dan ke-3)

d(3,1)52=min(2.58,2.78)=2.58$$d_{(3,1)52}=min(2.58,2.78)=2.58$$

d(3,1)4=min(4.20,4.55)=4.20$$d_{(3,1)4}=min(4.20,4.55)=4.20$$

5. Menampilkan matriks distance baru

	(52)	(31)	4
(52)	0	2.58	1.80
(31)	2.58	0	4.20
4	1.80	4.20	0

min(du,v)=d4,(52)=1.80$$min(d_{u,v})=d_{4,(52)}=1.80$$

sehingga negara ke-2, ke-5, dan ke-3 digabungkan menjadi 1 klaster.

6. Menghitung jarak baru tiap objek dengan klaster yang baru terbentuk (negara ke-2, ke-5, dan ke-3)

d52,4(31)=min(2.58,4.20)=2.58$$d_{52,4(31)}=min(2.58,4.20)=2.58$$

7. Menampilkan matriks distance baru

	(524)	(31)
(524)	0	2.58
(31)	2.58	0

MEMBUAT DENDOGRAM

Ketika menggunakan R, untuk membuat dendogram cukup dengan menggunakan fungsi plot(); sedangkan ketika menghitung manual dengan cara membuat plot antara objek/pengamatan dan mengubungkannya ketika antar objek/pengamatan tergabung menjadi satu klaster berdasarkan jarak minimum yang telah dihitung.

plot(hc_single, hang = -1) #Menampilkan Dendogram

Metode 2. Complete Linkage

DENGAN R

Untuk melakukan metode Single Linkage, dalam R dapat menggunakan fungsi hclust() kemudian memasukkan argument ‘complete’ pada parameter ‘method’.

hc_complete <- hclust(d = d, method = "complete")

MENGHITUNG MANUAL

Langkah menghitung manual metode Complete Linkage tidak jauh berbeda dengan metode Single Linkage. Perbedaannya terletak ketika membuat matriks distance baru maka jarak yang digunakan adalah jarak terjauh antara objek dengan klaster yang dibuat sebelumnya.

1. Menampilkan matriks distance

	1	2	3	4	5
1	0	2.58	0.77	4.20	2.86
2	2.58	0	2.78	2.08	0.74
3	0.77	2.78	0	4.55	3.21
4	4.20	2.08	4.55	0	1.80
5	2.86	0.74	3.21	1.80	0

min(du,v)=d5,2=0.74$$min(d_{u,v})=d_{5,2}=0.74$$

sehingga negara ke-2 dan ke-5 digabungkan menjadi 1 klaster.

2. Menghitung jarak baru tiap objek dengan klaster yang baru terbentuk (negara ke-2 dan ke-5)

d(5,2)1=max(2.86,2.58)=2.86$$d_{(5,2)1}=max(2.86,2.58)=2.86$$

d(5,2)3=max(3.21,2.78)=3.21$$d_{(5,2)3}=max(3.21,2.78)=3.21$$

d(5,2)4=max(2.08,1.80)=2.08$$d_{(5,2)4}=max(2.08,1.80)=2.08$$

3. Menampilkan matriks distance baru

	(52)	1	3	4
(52)	0	2.86	3.21	2.08
1	2.86	0	0.77	4.20
3	3.21	0.77	0	4.55
4	2.08	4.20	4.55	0

min(du,v)=d3,1=0.77$$min(d_{u,v})=d_{3,1}=0.77$$

sehingga negara ke-1 dan ke-3 digabungkan menjadi 1 klaster.

4. Menghitung jarak baru tiap objek dengan klaster yang baru terbentuk (negara ke-1 dan ke-3)

d(3,1)52=max(2.86,3.21)=3.21$$d_{(3,1)52}=max(2.86,3.21)=3.21$$

d(3,1)4=max(4.20,4.55)=4.55$$d_{(3,1)4}=max(4.20,4.55)=4.55$$

5. Menampilkan matriks distance baru

	(52)	(31)	4
(52)	0	3.21	2.08
(31)	3.21	0	4.55
4	2.08	4.55	0

min(du,v)=d4,(52)=2.08$$min(d_{u,v})=d_{4,(52)}=2.08$$

sehingga negara ke-2, ke-5, dan ke-3 digabungkan menjadi 1 klaster.

6. Menghitung jarak baru tiap objek dengan klaster yang baru terbentuk (negara ke-2, ke-5, dan ke-3)

d524(31)=max(3.21,4.55)=4.55$$d_{524(31)}=max(3.21,4.55)=4.55$$

7. Menampilkan matriks distance baru

	(524)	(31)
(524)	0	4.55
(31)	4.55	0

Catatan : Baris 1 = (524), Kolom 1 = (524) Baris 2 = (31), Kolom 2 = (31)

MEMBUAT DENDOGRAM

Ketika menggunakan R, untuk membuat dendogram cukup dengan menggunakan fungsi plot(); sedangkan ketika menghitung manual dengan cara membuat plot antara objek/pengamatan dan mengubungkannya ketika antar objek/pengamatan tergabung menjadi satu klaster berdasarkan jarak minimum yang telah dihitung.

plot(hc_complete, cex = 0.6, hang = -1) #Menampilkan Dendogram
abline(h = 3, col = 'red')

Pemilihan Klaster

Pemilihan klaster pada metode hierarki dapat dilakukan dengan cara 1] menentukan terlebih dahulu jumlah klaster yang ingin dibentuk kemudian 2] menggambar garis lurus horizontal pada dendogram yang memotong garis vertikal sebanyak jumlah klaster yang dipilih.

Sebagai contoh pada dendogram Complete Linkage, ingin dibuat 2 klaster, maka dibuat garis horizontal yang memotong dua garis vertikal pada klaster yang terbentuk. Sehingga klaster yang terbentuk adalah :

• Klaster 1 berisikan negara ke-1 dan ke-3 (Indonesia dan Filipina)
• Klaster 2 berisikan negara ke-2, ke-4, dan ke-5 (Malaysia, Singapura, dan Thailand).

Untuk menginterpretasikan klaster yang terbentuk, maka dapat dilihat dari nilai rata-rata karakteristik tiap klaster. Di dalam R dapat menggunakan fungsi cutree() untuk mengetahui lokasi klaster pada tiap objek.

cut_point = cutree(hc_complete, k = 2) #Memilih sebanyak 2 klaster
asean_data %>%
  mutate(Klaster = cut_point) %>%
  group_by(Klaster) %>% 
  summarise(Mean_TFR = round(mean(TFR),2), Mean_AKB = round(mean(AKB),2), Mean_AKI = round(mean(AKI),2), Mean_AHH = round(mean(AHH),2))

## # A tibble: 2 x 5
##   Klaster Mean_TFR Mean_AKB Mean_AKI Mean_AHH
##     <int>    <dbl>    <dbl>    <dbl>    <dbl>
## 1       1     2.65    22.6     120       70.6
## 2       2     1.57     4.93     18.5     77.4

Dilihat dari rata-rata angka TFR, AKB, AKI, dan AHH pada masing-masing klaster, maka dapat diinterpretasikan bahwa:

• Klaster 1 berisikan negara-negara dengan kualitas kesehatan yang cukup rendah.
• Klaster 2 berisikan negara dengan kualitas kesehatan yang cukup tinggi.

Sumber : 

pertemuan 12 machine learning Institut Teknologi PLN

http://jurnal.unmuhjember.ac.id/index.php/JUSTINDO/article/view/2418/0#:~:text=Hierarchical%20clustering%20adalah%20salah%20satu,agglomerative%20(down%20to%20top).

https://rpubs.com/nadhifanhf/hierarchical-clustering