Pengenalan Pola Hierarchical Clustering
PTIIK - 2014
Course Contents 1
Agglomerative Hierarchical Clustering (AHC)
2
Studi Kasus
3
Latihan dan Diskusi
4
Progress Final Project
Hierarchical Clustering Hierarchical Clustering adalah metode analisis kelompok yang berusaha untuk membangun sebuah hirarki kelompok data. Strategi pengelompokannya umumnya ada 2 jenis yaitu Agglomerative (Bottom-Up) dan Devisive (Top-Down). (Pada bagian ini akan dibatasi hanya menggunakan konsep Agglomerative). Algoritma Agglomerative Hierarchical Clustering : 1. Hitung Matrik Jarak antar data. 2. Ulangi langkah 3 dan 4 higga hanya satu kelompok yang tersisa. 3. Gabungkan dua kelompok terdekat berdasarkan parameter kedekatan yang ditentukan. 4. Perbarui Matrik Jarak antar data untuk merepresentasikan kedekatan diantara kelompok baru dan kelompok yang masih tersisa. 5. Selesai.
Rumus Umum
Membentuk Matrik Jarak, misal dengan Manhattan Distance : d
Dman x, y x j y j j 1
atau menggunakan Euclidian Distance : d
D x2 , x1 x2 j x1 j
2
j 1
Beberapa metode Pengelompokan Secara Hierarki Aglomeratif : Single Linkage (Jarak Terdekat) duv min{duv}, duv D Complete Linkage (Jarak Terjauh) duv max{duv}, duv D Average Linkage (Jarak Rata-Rata)
duv average{duv}, duv D
Contoh Studi Kasus
Perhatikan dataset berikut : Data 1 2 3 4 5
Fitur x 1 4 1 3 5
Fitur y 1 1 2 4 4
Kelompokkan dataset tersebut dengan menggunakan metode AHC (Single Linkage, Complete Linkage dan Average Linkage) menggunakan jarak Manhattan !
Menghitung Jarak Pada Semua Pasangan dua data : Data 1 2 3 4 5
Fitur x 1 4 1 3 5
Fitur y 1 1 2 4 4
2
Dman Data1 , Data1 x j y j 1 1 1 1 0 j 1
Dman Data1 , Data2 1 4 1 1 3 Dman Data1 , Data3 1 1 1 2 1
Dman Data1 , Data4 1 3 1 4 2 3 5
Dman Data3 , Data4 1 3 2 4 2 2 4
Dman Data1 , Data5 1 5 1 4 4 3 7
Dman Data3 , Data5 1 5 2 4 4 2 6
Dman Data 2 , Data3 4 1 1 2 3 1 4
Dm anData4 , Data5 3 5 4 4 2 0 2
Dman Data 2 , Data 4 4 3 1 4 1 3 4 Dman Data 2 , Data5 4 5 1 4 1 3 4
Hasil Matrik Jarak : Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Single Linkage
Menggunakan Metode Single Linkage : Dengan memperlakukan data sebagai kelompok, selanjutnya kita pilih jarak dua kelompok yang terkecil. Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
min( Dm an) min( d13 ) 1
terpilih kelompok 1 dan 3, sehingga kedua kelompok ini digabungkan. (Melanjutkan pengelompokan).
Menghitung jarak antar kelompok (1 dan 3) dengan kelompok lain yang tersisa, yaitu 2, 4 dan 5. d (13 ) 2 min{ d12 , d 32 } min{3,4} 3 d (13 ) 4 min{ d14 , d 34 } min{5,4} 4 d (13 ) 5 min{ d15 , d 35 } min{7,6} 6
Menghitung jarak antar kelompok (1 dan 3) dengan kelompok lain yang tersisa, yaitu 2, 4 dan 5. d (13 ) 2 min{ d12 , d 32 } min{3,4} 3 d (13 ) 4 min{ d14 , d 34 } min{5,4} 4 d (13 ) 5 min{ d15 , d 35 } min{7,6} 6
Dengan menghapus baris-baris dan kolom-kolom matrik jarak yang bersesuaian dengan kelompok 1 dan 3, serta menambahkan baris dan kolom untuk kelompok (13). Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman
(13)
2
4
5
(13)
0
3
4
6
2
3
0
4
4
4
4
4
0
2
5
6
4
2
0
Selanjutnya dipilih jarak dua kelompok yang terkecil. min( Dm an) min( d 45 ) 2
Dengan menghapus baris-baris dan kolom-kolom matrik jarak yang bersesuaian dengan kelompok 1 dan 3, serta menambahkan baris dan kolom untuk kelompok (13). Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman
(13)
2
4
5
(13)
0
3
4
6
2
3
0
4
4
4
4
4
0
2
5
6
4
2
0
Selanjutnya dipilih jarak dua kelompok yang terkecil. min( Dm an) min( d 45 ) 2
Menghitung jarak antar kelompok (4 dan 5) dengan kelompok lain yang tersisa, yaitu (13) dan 2. d ( 45 )(13 ) min{ d 41 , d 43 , d 51 , d 53 } min{5,4,7,6} 4 d ( 45 ) 2 min{ d 42 , d 52 } min{ 4,4} 4
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok 4 dan 5, serta menambahkan baris dan kolom untuk kelompok (45)
Menghitung jarak antar kelompok (4 dan 5) dengan kelompok lain yang tersisa, yaitu (13) dan 2. d ( 45 )(13 ) min{ d 41 , d 43 , d 51 , d 53 } min{5,4,7,6} 4 d ( 45 ) 2 min{ d 42 , d 52 } min{ 4,4} 4
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok 4 dan 5, serta menambahkan baris dan kolom untuk kelompok (45) Dman
(13)
2
4
5
(13)
0
3
4
6
Dman
(45)
(13)
2
2
3
0
4
4
(45)
0
4
4
4
4
4
0
2
(13)
4
0
3
5
6
4
2
0
2
4
3
0
Selanjutnya dipilih jarak dua kelompok yang terkecil. min( Dman ) min( d (13) 2 ) 3
terpilih kelompok (13) dan 2, sehingga kedua kelompok ini digabungkan. (Melanjutkan pengelompokan). Menghitung jarak antar kelompok ((13) dan 2) dengan kelompok lain yang tersisa, yaitu (45).
Menghitung jarak antar kelompok ((13) dan 2) dengan kelompok lain yang tersisa, yaitu (45). d (132 )( 45 ) min{d14 , d15 , d 34 , d 35 , d 24 , d 25 } min{5,7,4,6,4,4} 4
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok (13) dan 2, serta menambahkan baris dan kolom untuk kelompok (123) Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman
(13)
2
4
5
(13)
0
3
4
6
Dman
(45)
(13)
2
2
3
0
4
4
(45)
0
4
4
4
4
4
0
2
(13)
4
0
3
5
6
4
2
0
2
4
3
0
Dman
(132)
(45)
(132)
0
4
(45)
4
0
Jadi kelompok (132) dan (45) digabung untuk menjadi kelompok tunggal dari lima data, yaitu kelompok (13245) dengan jarak terdekat 4.
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok (13) dan 2, serta menambahkan baris dan kolom untuk kelompok (132) Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman (13) (13)
2 4 5
0 3 4 6
2
4
5
3
4
6
0 4 4
4 0 2
Dman (45) (13) 2
Dman (132) (45)
4
(45)
0
4
4
(132)
4
0
3
0
4
2
(13)
(45)
4
3
0
4
0
0
2
Jadi kelompok (132) dan (45) digabung untuk menjadi kelompok tunggal dari lima data, yaitu kelompok (13245) dengan jarak terdekat 4. Berikut Dendogram Hasil Metode Single Linkage : J 4 a 3 r 2 a k 1 1
3
2
4
5
Data
Complete Linkage
Menggunakan Metode Complete Linkage : Dengan memperlakukan data sebagai kelompok, selanjutnya kita pilih jarak dua kelompok yang terkecil. Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
min( Dm an) min( d13 ) 1
terpilih kelompok 1 dan 3, sehingga kedua kelompok ini digabungkan. (Melanjutkan pengelompokan).
Menghitung jarak antar kelompok (1 dan 3) dengan kelompok lain yang tersisa, yaitu 2, 4 dan 5. d (13 ) 2 max{d12 , d 32 } max{3,4} 4 d (13 ) 4 max{d14 , d 34 } max{5,4} 5 d (13 ) 5 max{d15 , d 35 } max{7,6} 7
Menghitung jarak antar kelompok (1 dan 3) dengan kelompok lain yang tersisa, yaitu 2, 4 dan 5. d (13 ) 2 max{d12 , d 32 } max{3,4} 4 d (13 ) 4 max{d14 , d 34 } max{5,4} 5 d (13 ) 5 max{d15 , d 35 } max{7,6} 7
Dengan menghapus baris-baris dan kolom-kolom matrik jarak yang bersesuaian dengan kelompok 1 dan 3, serta menambahkan baris dan kolom untuk kelompok (13). Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman
(13)
2
4
5
(13)
0
4
5
7
2
4
0
4
4
4
5
4
0
2
5
7
4
2
0
Selanjutnya dipilih jarak dua kelompok yang terkecil. min( Dm an) min( d 45 ) 2
Dengan menghapus baris-baris dan kolom-kolom matrik jarak yang bersesuaian dengan kelompok 1 dan 3, serta menambahkan baris dan kolom untuk kelompok (13). Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman
(13)
2
4
5
(13)
0
4
5
7
2
4
0
4
4
4
5
4
0
2
5
7
4
2
0
Selanjutnya dipilih jarak dua kelompok yang terkecil. min( Dm an) min( d 45 ) 2
Menghitung jarak antar kelompok (4 dan 5) dengan kelompok lain yang tersisa, yaitu (13) dan 2. d ( 45 )(13 ) max{d 41 , d 43 , d 51 , d 53 } max{5,4,7,6} 7 d ( 45 ) 2 max{d 42 , d 52 } max{4,4} 4
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok 4 dan 5, serta menambahkan baris dan kolom untuk kelompok (45)
Menghitung jarak antar kelompok (4 dan 5) dengan kelompok lain yang tersisa, yaitu (13) dan 2. d ( 45 )(13 ) max{d 41 , d 43 , d 51 , d 53 } max{5,4,7,6} 7 d ( 45 ) 2 max{d 42 , d 52 } max{4,4} 4
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok 4 dan 5, serta menambahkan baris dan kolom untuk kelompok (45) Dman
(13)
2
4
5
(13)
0
4
5
7
Dman
(45)
(13)
2
2
4
0
4
4
(45)
0
7
4
4
5
4
0
2
(13)
7
0
4
5
7
4
2
0
2
4
4
0
Selanjutnya dipilih jarak dua kelompok yang terkecil. min( Dman ) min( d ( 45 ) 2 ) 4
terpilih kelompok (45) dan 2, sehingga kedua kelompok ini digabungkan. (Melanjutkan pengelompokan). Menghitung jarak antar kelompok ((45) dan 2) dengan kelompok lain yang tersisa, yaitu (13).
Menghitung jarak antar kelompok ((45) dan 2) dengan kelompok lain yang tersisa, yaitu (13). d ( 452 )(13) max{d 41 , d 43 , d 51 , d 53 , d 21 , d 23 } max{5,4,7,6,3,4} 7
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok (45) dan 2, serta menambahkan baris dan kolom untuk kelompok (452) Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman
(13)
2
4
5
(13)
0
4
5
7
Dman
(45)
(13)
2
2
4
0
4
4
(45)
0
7
4
4
5
4
0
2
(13)
7
0
4
5
7
4
2
0
2
4
4
0
Dman
(452)
(13)
(452)
0
7
(13)
7
0
Jadi kelompok (452) dan (13) digabung untuk menjadi kelompok tunggal dari lima data, yaitu kelompok (13452) dengan jarak terdekat 7.
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok (45) dan 2, serta menambahkan baris dan kolom untuk kelompok (452) Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman (13) (13)
2 4 5
0 4 5 7
2
4
5
4
5
7
0 4 4
4 0 2
Dman (45) (13) 2
Dman (452) (13)
4
(45)
0
7
4
(452)
7
0
4
0
7
2
(13)
(13)
4
4
0
7
0
0
2
Jadi kelompok (452) dan (13) digabung untuk menjadi kelompok tunggal dari lima data, yaitu kelompok (13452) dengan jarak terdekat 7. Berikut Dendogram Hasil Metode Complete Linkage : 7 J 4 a r 2 a k 1 1
3
4
5
2
Data
Average Linkage
Menggunakan Metode Average Linkage : Dengan memperlakukan data sebagai kelompok, selanjutnya kita pilih jarak dua kelompok yang terkecil. Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
min( Dm an) min( d13 ) 1
terpilih kelompok 1 dan 3, sehingga kedua kelompok ini digabungkan. (Melanjutkan pengelompokan).
Menghitung jarak antar kelompok (1 dan 3) dengan kelompok lain yang tersisa, yaitu 2, 4 dan 5. d (13 ) 2 average{d12 , d 32 } average{3,4} (3 4) / 2 3.5 d (13 ) 4 average{d14 , d 34 } average{5,4} (5 4) / 2 4.5 d (13 ) 5 average{d15 , d 35 } average{7,6} (7 6) / 2 6.5
Menghitung jarak antar kelompok (1 dan 3) dengan kelompok lain yang tersisa, yaitu 2, 4 dan 5. d (13 ) 2 average{d12 , d 32 } average{3,4} (3 4) / 2 3.5 d (13 ) 4 average{d14 , d 34 } average{5,4} (5 4) / 2 4.5 d (13 ) 5 average{d15 , d 35 } average{7,6} (7 6) / 2 6.5
Dengan menghapus baris-baris dan kolom-kolom matrik jarak yang bersesuaian dengan kelompok 1 dan 3, serta menambahkan baris dan kolom untuk kelompok (13). Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman
(13)
2
4
5
(13)
0
3.5
4.5
6.5
2
3.5
0
4
4
4
4.5
4
0
2
5
6.5
4
2
0
Selanjutnya dipilih jarak dua kelompok yang terkecil. min( Dm an) min( d 45 ) 2
Dengan menghapus baris-baris dan kolom-kolom matrik jarak yang bersesuaian dengan kelompok 1 dan 3, serta menambahkan baris dan kolom untuk kelompok (13). Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman
(13)
2
4
5
(13)
0
3.5
4.5
6.5
2
3.5
0
4
4
4
4.5
4
0
2
5
6.5
4
2
0
Selanjutnya dipilih jarak dua kelompok yang terkecil. min( Dm an) min( d 45 ) 2
Menghitung jarak antar kelompok (4 dan 5) dengan kelompok lain yang tersisa, yaitu (13) dan 2. d ( 45 )(13 ) average{d 41 , d 43 , d 51 , d 53 } average{5,4,7,6} (5 4 7 6) / 4 5.25 d ( 45 ) 2 average{d 42 , d 52 } average{4,4} ( 4 4) / 2 4
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok 4 dan 5, serta menambahkan baris dan kolom untuk kelompok (45)
Menghitung jarak antar kelompok (4 dan 5) dengan kelompok lain yang tersisa, yaitu (13) dan 2. d ( 45 )(13 ) average{d 41 , d 43 , d 51 , d 53 } average{5,4,7,6} (5 4 7 6) / 4 5.25 d ( 45 ) 2 average{d 42 , d 52 } average{4,4} ( 4 4) / 2 4
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok 4 dan 5, serta menambahkan baris dan kolom untuk kelompok (45) Dman
(13)
2
4
5
(13)
0
3.5
4.5
6.5
Dman
(45)
(13)
2
2
3.5
0
4
4
(45)
0
5.25
4
4
4.5
4
0
2
(13)
5.25
0
3.5
5
6.5
4
2
0
2
4
3.5
0
Selanjutnya dipilih jarak dua kelompok yang terkecil. min( Dman ) min( d (13) 2 ) 3.5
terpilih kelompok (13) dan 2, sehingga kedua kelompok ini digabungkan. (Melanjutkan pengelompokan). Menghitung jarak antar kelompok ((13) dan 2) dengan kelompok lain yang tersisa, yaitu (45).
Menghitung jarak antar kelompok ((13) dan 2) dengan kelompok lain yang tersisa, yaitu (45). d (132 )( 45 ) average{d14 , d15 , d 34 , d 35 , d 24 , d 25 } average{5,7,4,6,4,4} (5 7 4 6 4 4) / 6 5
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok (45) dan 2, serta menambahkan baris dan kolom untuk kelompok (452) Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman
(13)
2
4
5
(13)
0
3.5
4.5
6.5
Dman
(45)
(13)
2
2
3.5
0
4
4
(45)
0
5.25
4
4
4.5
4
0
2
(13)
5.25
0
3.5
5
6.5
4
2
0
2
4
3.5
0
Dman
(132)
(45)
(132)
0
5
(45)
5
0
Jadi kelompok (132) dan (45) digabung untuk menjadi kelompok tunggal dari lima data, yaitu kelompok (13245) dengan jarak terdekat 5.
Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok (45) dan 2, serta menambahkan baris dan kolom untuk kelompok (452) Dman 1 2 3 4 5
1 0 3 1 5 7
2 3 0 4 4 4
3 1 4 0 4 6
4 5 4 4 0 2
5 7 4 6 2 0
Dman (13) (13)
2 4 5
0 3.5 4.5 6.5
2
4
5
3.5 4.5 6.5 4 4 0 4 4
0 2
Dman (45) (13) 2 (45)
0
2
(13)
5.25
0
3.5
0
2
4
3.5
0
5.25 4
Dman (132) (45) (132)
0
5
(45)
5
0
Jadi kelompok (132) dan (45) digabung untuk menjadi kelompok tunggal dari lima data, yaitu kelompok (13245) dengan jarak terdekat 5. Berikut Dendogram Hasil Metode Average Linkage : 5 J 4 a 3 r 2 a k 1 1
3
2
4
5
Data
Single-Linkage
Complete-Linkage 7
J 4 a 3 r 2 a k 1 1
3
2
4
Data
5
1
Average-Linkage 5 J 4 a 3 r 2 a k 1 1
3
2
4
J 4 a r 2 a k 1
5
Data
3
4
5
2
Data
Latihan 1. Perhatikan dataset 1 berikut : Data 1 2 3 4 5
Fitur x 1 4 1 3 5
Fitur y 1 1 2 4 4
Kelompokkan dataset tersebut dengan menggunakan metode AHC (Single Linkage, Complete Linkage dan Average Linkage) menggunakan jarak Euclidian dan Visualisasikan Dendogramnya !
2. Perhatikan dataset 2 berikut : Data 1 2 3 4 5 6 7 8 9 10
Fitur x 1 4 6 1 2 5 2 3 2 3
Fitur y 1 1 1 2 3 3 5 5 6 8
Kelompokkan dataset tersebut dengan menggunakan metode AHC Average Linkage menggunakan jarak Euclidian dan Visualisasikan Dendogramnya !
[email protected] 081 331 834 734 / 088 160 127 40
