Hierarchy Clustering

Hierarchy clustering berfungsi membagi-bagi data menjadi beberapa klaster menurut urutan kejadiannya (hirarki). Ada dua pendekatan dalam membuat hirarki yaitu 

• bottom-up: dari klaster kecil menjadi satu klaster besar (Agglomerative)
• top-down: dari satu klaster besar menjadi klaster-klaster kecil (Divisive)

Step-by-Step Hierarchy Clustering Agglomerative

1. Buat setiap data menjadi satu klaster
2. Cari dan gabungkan 2 klaster dengan jarak terpendek.
3. Ulangi langkah kedua sampai semua data menjadi 1 klaster

Ukuran jarak antar klaster terbagi menjadi beberapa:

• Single linkage cluster: mengukur a anggota X dan c anggota Y dimana jarak a dan c adalah yang paling pendek.
• Complete linkage cluster: mengukur b anggota X dan d anggota Y dimana jarak b dan d adalah yang paling panjang. 
• Centroid linkage cluster: mengukur p centroid X dan q centroid Y dimana jarak p dan q adalah yang paling pendek. 
• Average linkage cluster: mengukur rata-rata jarak setiap x anggota X ke setiap y anggota Y dimana nilai rata-ratanya adalah yang paling pendek. 

CONTOH SOAL

• Kita memiliki 10 data yang akan kita bagi-bagi menjadi beberapa klaster.

• STEP 1: Setiap data adalah sebuah klaster, jadi kita memiliki 10 klaster yaitu {A}, {B},{C}, ... {J}

• STEP 2: Cari 2 klaster yang paling berdekatan dan gabungkan. Kita temukan {A }dan {B }menjadi {A,B}. Di contoh ini kita menggunakan centroid linkage untuk mengukur jarak terpendek antar klaster.

• STEP 3: Gabungkan 2 klaster yang paling berdekatan. Kita temukan lagi {I }dan {J} menjadi {I,J}

• STEP 4: Gabungkan lagi 2 klaster yang paling berdekatan. Kita temukan {C }dan {D }menjadi {C,D}

• STEP 5: Gabungkan 2 klaster yang paling berdekatan. Kita temukan {A,B} dan {C,D} menjadi {A,B,C,D}

• STEP 6: Gabungkan 2 klaster yang paling berdekatan. Kita temukan {F} dan {G} menjadi {F,G}

• STEP 7: Gabungkan 2 klaster yang paling berdekatan. Kita temukan {E } dan {F,G} menjadi {E,F,G}

STEP 8: Gabungkan 2 klaster yang paling berdekatan. Kita temukan {E,F,G} dan {H} menjadi {E,F,G,H}

• STEP 9: Gabungkan 2 klaster yang paling berdekatan. Kita temukan {A,B,C,D} dan {E,F,G,H} menjadi {A,B,C,D,E,F,G,H}

• STEP 10: Gabugkan 2 klaster yang paling berdekatan. Kita temukan {A,B,C,D,E,F,G,H} dan {I,J} menjadi {A,B,C,D,E,F,G,H,I,J}

• Karena semua data sudah menjadi satu klaster, maka proses berhenti sampai disini.
• Hasilnya adalah sebuah visualisasi yang dinamakan dendrogram yang bentuknya seperti decision tree (pohon keputusan).

• Dari dendrodram di bawah ini dapat disimpulkan sbb:
• kalau dibuat 2 klaster maka klaster pertama {I,J}, klaster kedua {A,B,C,D,E,F,G,H}.
• kalau dibuat 3 klaster maka klaster pertama {I,J}, klaster kedua {E,F,G,H} dan klaster ketiga {A,B,C,D}.
• dst