CLUSTERING

KEMAMPUAN AKHIR YANG DIHARAPKAN

Dapat menjelaskan konsep dasar cluster dan penerapannya pada data.

 CLUSTERING
 Cluster
Suatu cluster merupakan sekelompok entitas yang memiliki kesamaan dan
memiliki perbedaan dengan entitas dari kelompok lain(Everitt,1980).
Cluster berguna untuk mengelompokkan objek-objek data yang
memiliki kemiripan ke dalam satu grup dan yang berbeda
dikelompokkan ke dalam grup lainnya
 Semakin besar tingkat kemiripan/similarity (atau homogenitas) di dalam
satu grup dan semakin besar tingkat perbedaan diantara grup, maka
semakin baik (atau lebih berbeda) clustering tersebut.
 Tujuan Pengelompokan
• Tujuan clustering (pengelompokan) data dapat dibedakan menjadi dua,
yaitu pengelompokan untuk pemahaman dan clustering untuk
penggunaan (Prasetyo,2012).

• Biasanya proses pengelompokan untuk tujuan pemahaman hanya sebagai

proses awal untuk kemudian dilanjutkan dengan pekerjaan seperti
summarization (rata-rata, standar deviasi), pelabelan kelas untuk setiap
kelompok sehingga dapat digunakan sebagai data training dalam klasifikasi
supervised.
• Sementara jika untuk penggunaan, tujuan utama clustering biasanya
adalah mencari prototipe kelompok yang paling representatif terhadap
data, memberikan abstraksi dari setiap obyek data dalam kelompok
dimana sebuah data terletak didalamnya
clustering untuk pemahaman
• Contoh tujuan clustering untuk pemahaman
diantaranya: dibidang Biologi (pengelompokan
berdasarkan karakter tertentu secara hirarkis) ,
pengelompokan gen yang memiliki fungsi sama.
• Dibidang information retrieval (web search),bidang
klimatologi (pengelompokam pola tekanan udara
yang berpengaruh pada cuaca), bidang bisnis
(pengelompokan konsumen yang berpotensi untuk
analisa dan strategi pemasaran).
clustering untuk penggunaan
• Contoh tujuan clustering untuk penggunaan dibidang
summarization, dengan semakin besarnya jumlah data maka
ongkos melakukan peringkasan semakin mahal
(berat&kompleks), maka perlu diterapkan pengelompokan
data untuk membuat prototipe yang dapat mewakili
keseluruhan data yang akan digunakan.
• Kompresi , data yang terletak dalam satu cluster dapat
dikompresi dengan diwakili oleh indeks prototipe yang
dikaitkan dengan kelompok , teknik kompresi ini dikenal
sebagai quantization vector.
 Aplikasi Teknik Clustering
Clustering telah diterapkan diberbagai bidang seperti di jelaskan
sebagai berikut:
• 1. Teknik
• Digunakan dalam bidang biometric recognition & speech
recognition, analisa sinyal radar, Information
Compression,dan noise removal.

• 2. Ilmu Komputer
• Web mining,analisa database spatial,information
retrieval,textual document collection,dan image
segmentation.
 Aplikasi Teknik Clustering
• 3. Medis
• Digunakan dalam mendefinisikan taxonomi dalam bidang
biologi, identifikasi fungsi protein dan gen, diagnosa penyakit
dan penanganannya.

• 4. Astronomy
• Digunakan untuk mengelompokkan bintang dan planet,
menginvestigasi formasi tanah, mengelompokkan wilayah
/kota, digunakan dalam studi tentang sistem pada sungai dan
gunung.
 Aplikasi Teknik Clustering
• 5. Sosial
• Digunakan pada analisa pola perilaku,identifikasi hubungan
diantara budaya yang berbeda, pembentukan sejarah evolusi
bahasa, dan studi psikologi criminal.

• 6. Ekonomi
• Penerapan pada pengenalan pola pembelian& karakteristik
konsumen, pengelompokan perusahaan, analisa trend stok.
 TIPE-TIPE CLUSTERING
 Partitional clustering adalah himpunan obyek data ke
dalam sub-himpunan (cluster) yang tidak overlap,
sehingga setiap obyek data berada dalam tepat satu
cluster.

 Hierarchical clustering adalah cluster yang memiliki

subcluster. Himpunan cluster besarang yang diatur
dalam tree.
PARTITIONAL CLUSTERING
HIERARCHICAL CLUSTERING
 ALGORITMA CLUSTERING

• K-Means
• K-Medoids
• Hierarchical Clustering
K-MEANS CLUSTERING
• K‐Means clustering adalah metode untuk
mengelompokkan item ke dalam kelompok (dimana k
adalah jumlah kelompok yang diinginkan).

• Kelompok/cluster dibentuk dengan meminimalkan jumlah

dari Euclidean distances) diantara data dengan titik pusat
(centroid) yang berkorespondensi.

• Centroid adalah titik pusat data, dalam hal ini kita

mengasumsikan rata‐rata vector sebagai centroid.
K-MEANS CLUSTERING

 Pendekatan partitional clustering

 Setiap cluster diasosiasikan dengan sentroid
 Setiap titik di tandai ke cluster dengan sentroid terdekat
 K menandakan jumlah cluster yang akan terbentuk
 Algoritma Clustering:
1. Menentukan jumlah cluster
2. Menentukan nilai centroid biasanya dilakukan secara random atau
biasanya menggunakan rumus rata-rata
3. Menghitung jarak antara titik centroid dengan titik tiap objek.
Biasanya menggunakna jarak Euclidean distance.
4. Mengelompokkan objek berdasarkan jarak terdekat
5. Kembali ke tahap ke 2 dan lakukan perulangan hingga nilai
centroid yang dihasilkan tetap dan anggota cluster tidak berpindah
ke cluster lain.
 Ilustrasi K‐Means

• Titik hitam menyatakan data. Garis merah menyatakan partisi/pemisah.

Titik biru merepresentasikan titik pusat (centroid) yang mendefinisikan
suatu partisi
 Inisialisasi titik pusat (centroid)
• Inisialisasi centroid dapat dilakukan dengan beberapa cara, contohnya 3
cara berikut:
– Dipilih secara dinamik: Metode ini tepat digunakan jika data baru
ditambahkan secara cepat dan banyak. Untuk menyederhanakan
persoalan, inisial cluster dipilih dari beberapa data baru, misal jika data
dikelompokkan menjadi 3 clusters, maka inisial cluster berarti 3 item
pertama dari data.
– Dipilih secara random: Paling banyak digunakan, dimana inisial cluster
dipilih secara random dengan range data antara nilai terendah sampai nilai
tertinggi.
– Memilih dari batasan nilai tinggi dan rendah: tergantung pada tipe
datanya, nilai data tertinggi dan terendah dipilih sebagai inisial cluster.
Contoh berikut menggunakan metode ini.
 CONTOH SOAL
DATA X Y
M1 2 5.0
M2 2 5.5
M3 5 3.5
M4 6.5 2.2
M5 7 3.3
M6 3.5 4.8
M7 4 4.5

C1=(3,4) dan C2=(6,4)

 CONTOH SOAL
Iterasi 1

a. Menghitung Euclidean distance dari semua data ke tiap titik pusat pertama

Dengan cara yang sama hitung jarak tiap titik ke titik pusat ke dan kita akan
mendapatkan D21= 4.12, D22=4.27, D23= 1.18, D24= 1.86, D25=1.22, D26=2.62,
D27=2.06
 CONTOH SOAL
Iterasi 1

b. Dari perhitungan Euclidean distance, kita dapat membandingkan

DATA C1 C2
M1 1.41 4.12
M2 1.80 4.27
M3 2.06 1.18
M4 3.94 1.86
M5 4.06 1.22
M6 0.94 2.62
M7 1.12 2.06

{M1, M2, M6, M7} anggota C1 and {M3, M4, M5} anggota C2
 CONTOH SOAL
Iterasi 1

c. Hitung titik pusat baru

Lakukan iterasi ke 2 seperti iterasi ke 1, sampai anggota kelompok C1

dan C2 tidak berubah lagi seperti sebelumnya,

Kesimpulan {M1, M2, M6, M7} anggota C1 dan {M3, M4, M5} anggota C2
 HIERARCHICAL CLUSTERING
Strategi pengelompokkannya umumnya ada dua jenis, yaitu:
• Agglomerative (Bottom-Up)
• Devisive (Top-Down)

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 metode
pengelompokan ( Single Linkage, Complete Linkage, Average
Linkage)
4. Perbarui Matrik Jarak antar data untuk merepresentasikan
kedekatan diantara kelompok baru dan kelompok yang masih
tersisa.
5. Selesai
Metode Pengelompokan Hierarki
Aglomeratif
Beberapa metode pengelompokan secara hierarki Aglomeratif:
 Single Linkage (Jarak Terdekat)

 Complete Linkage (Jarak Terjauh)

 Average Linkage (Jarak rata-rata)

 CONTOH STUDI KASUS

Kelompokkan dataset tersebut dengan menggunakan metode AHC

(Single Linkage) menggunakan jarak Manhattan!
CONTOH STUDI KASUS
CONTOH STUDI KASUS
• Menghitung jarak antar kelompok (1 dan 3) dengan kelompok lain yang
tersisa, yaitu 2, 4 dan 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)

Selanjuttnya dipilih jarak dua kelompok yang terkecil.

• Menghapus baris dan kolom matrik yang bersesuaian dengan kelompok
(13) dan 2, serta menambahkan baris dan kolom untuk kelompok (132).

• 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 :
 Tugas
• Latihan: Gunakan metode k-means untuk mengelompokkan mahasiswa
berdasarkan tinggi & berat badan:
• Clustering yang diharapkan mampu menghasilkan kelompok
mahasiswa yang memenuhi sifat berikut :
• Mahasiswa yang memiliki berat dan tinggi badan yang hampir
sama dikelompokkan tersendiri

• 1. Mahasiswa yang memiliki berat dan tinggi badan yang

hampir sama dikelompokkan akan berada pada kelompok
yang sama.

• 2. Mahasiswa yang yang memiliki berat dan tinggi badan yang

berbeda akan berada pada kelompok yang berbeda.
TERIMA KASIH