### 10.1 K- _mean_ s, Pemilihan Centroid, Kemiripan Data

Algoritma K- _mean_ s mengelompokkan data menjadi sebanyakK kelompok
sesuai yang kita definisikan. Algoritma ini disebut juga sebagai _flat clustering_,
artinya kelompok satu memiliki kedudukan sejajar dengan kelompok lainnya.
Kita tinjau kembali tahapan-tahapan algoritma K- _mean_ s sebagai berikut:

1. Tentukan sebanyakKkelompok yang kita inginkan.
2. Inisiasi _centroid_ untuk setiap kelompok. Centroid ibarat seperti “ketua
    kelompok”, yang merepresentasikan kelompok.
3. Hitung kedekatan suatu data terhadap _centroid_, kemudian masukkan data
    tersebut ke kelompok yang _centroid_ -nya memiliki sifat terdekat dengan
    dirinya.
4. Pilih kembali centroid untuk masing-masing kelompok, yaitu dari anggota
    kelompok tersebut.
5. Ulangi langkah-langkah sebelumnya sampai tidak ada perubahan anggota
    untuk semua kelompok.

Perhatikan, ada dua hal penting pada algoritma K- _mean_ s yaitu: (1)
memilih centroid dan (2) Perhitungan kemiripan data. Pada bab 4, dijelaskan
salah satu metode pemilihan centroid paling sederhana yaitu secara acak.
Pada kenyataannya, inisiasi centroid untuk setiap kelompok/ _cluster_ dapat dilakukan
secara acak; tetapi pada tahap berikutnya, secara umum centroid
dipilih menggunakan nilai rata-rata/ _mean_. Dengan demikian, centroid bisa
saja merupakan suatu vektor yang tidak ada _entry_ -nya di dataset.
Diberikan sekumpulan dataD={d 1 ,d 2 ,···,dN}; maka centroidcuntuk
_cluster_ itu dihitung dengan persamaan 10.1,

```
c=
```
#### 1

#### N

#### ∑N

```
i=1
```
#### ∑F

```
e=1
```
```
di[e] (10.1)
```
yaitu nilai rata-rata setiap elemen _feature vector_ untuk seluruh anggota _cluster_
tersebut, dimanaN adalah banyaknya anggota _cluster_,F adalah dimensi
_vektor_,diadalah anggota ke-i dalam representasi _feature vector_ dandi[e]
melambangkan elemen ke-epada vektordi. Dengan ini, centroid secara umum
bisa jadi tidak merupakan elemen anggota _cluster_ ( _centroid_ bukan sebuah
_instance_ data).
Pada bab 4 dijelaskan salah satu metode perhitungan kemiripan data
sederhana yaitu dengan menghitung banyaknya nilai atribut yang sama diantara
dua _feature vector_. Selain metode tersebut, terdapat banyak perhitungan
kemiripan data lainnya tergantung pada tipe, contohnya:

```
1.Numerik. Euclidean Distance, Manhattan Distance, Cosine Distance,
dsb.
2.Boolean. Jaccard Dissimilarity, Rogers Tanimoto Dissimilarity, dsb.
3.String. Levenshtein Distance, Hamming Distance, dsb.
```

```
10.2 Hierarchical Clustering 137
```
Perhitungan yang paling populer digunakan adalah _cosine similarity_ ^1 (kebetulan
pada kebanyakan kasus kita bekerja dengan data numerik), didefinisikan
pada persamaan 10.2, yaitu _dot product_ antara dua vektor dibagi dengan
perkalian _norm_ kedua vektor.

```
cosSim(di,dj) =
di·dj
‖di‖‖dj‖
```
#### (10.2)

_Cluster_ s yang terbentuk, nantinya dapat digunakan sebagai pengelompokkan
untuk label klasifikasi. Seumpama _cluster_ 1 dapat dianggap sebagai data untuk
kelas ke-1, dst.

