### 10.2 Hierarchical Clustering

Hierarchical clusteringadalah teknik untuk membentuk pembagian bersarang
(nested partition). Berbeda dengan K- _mean_ s yang hasil _clustering_ -nya berbentukflatatau
rata, _hierarchical clustering_ memiliki satu _cluster_ paling atas
yang mencakup konsep seluruh _cluster_ dibawahnya. Ada dua cara untuk membentuk _hierarchical_
_clustering_ [41]:

```
1.Agglomerative. Dimulai dari beberapaflat clusters; pada setiap langkah
iterasi, kita menggabungkan dua _clusters_ termirip. Artinya, kita harus
mendefinisikan arti “kedekatan” dua _clusters_.
```
```
2.Divisive. Dimulai dari satu _cluster_ (seluruh data), kemudian kita memecah
belah _cluster_. Artinya, kita harus mendefinisikan _cluster_ mana yang harus
dipecah dan bagaimana cara memecahnya.
```
```
Gambar 10.1: Ilustrasi _hierarchical clustering_.
```
(^1) https://en.wikipedia.org/wiki/Cosine_similarity


138 10 Clustering

Sebagai contoh, algoritma _hierarchical clustering_ menghasilkan struktur
hirarkis seperti pada gambar 10.1 yang disebutdendogram. Dendogram
melambangkan taksonomi, sebagai contoh taksonomi dokumen berita _sport_,
dipecah menjadi _baseball_ dan _soccer_.
Sejauh ini, teknik _agglomerative clustering_ lebih populer, karena pendekatan
ini bersifat _bottom-up_. Secara umum, pendekatan _bottom-up_ memang
relatif lebih populer dibanding pendekatan _top-down_. Langkah-langkahagglomerative
_clustering_ sebagai berikut:

1. Sediakan sebanyakK _cluster_. Kamu dapat menganggap satu _instance_ data
    sebagai satu _cluster_.
2. Gabung dua _clusters_ paling mirip.
3. Ulangi langkah ke-2 sampai hanya satu _cluster_ tersisa.
    Perhatikan, untuk menggabungkan dua _clusters_ termirip, kita membutuhkan
definisi “mirip”. Definisi tersebut dikuantifikasi dengan formula matematis
(seperti definisi kemiripan data pada subbab 10.1). Perhitungan kemiripan _clusters_ dapat
dihitung dengan tiga metode [43] (untuk data numerik):

```
1. _Single Link_. Nilai kemiripan dua _clusters_ UdanVdihitung berdasarkan
nilai kemiripanmaksimumdiantara anggota kedua _clusters_ tersebut^2.
```
```
SimsingleLink(U,V) = max
ui∈U,vj∈V
cosSim(ui,vj) (10.3)
```
```
2. _Complete Link_. Nilai kemiripan dua _clusters_ dihitung berdasarkan nilai
kemiripanminimumdiantara anggota kedua _clusters_ tersebut.
```
```
SimcompleteLink(U,V) = min
ui∈U,vj∈V
cosSim(ui,vj) (10.4)
```
```
3.UPGMA ( _Average Link_ ). Nilai kemiripan dua _clusters_ dihitung berdasarkan
nilai kemiripanrata-ratadiantara anggota kedua _clusters_ tersebut.
```
```
SimUPGMA(U,V) =
```
#### 1

#### |U||V|

#### ∑

```
ui∈U,vj∈V
```
```
cosSim(ui,vj) =
cUcV
|U||V|
```
#### (10.5)

```
dimana|U|adalah banyaknya data pada _cluster_ UdancUadalah centroid
untuk _cluster_ U.
```
(^2) Clusterdapat dianggap sebagai matriks karena merupakan kumpulanfeature vec-
tor.


```
10.3 Evaluasi 139
```
