EM (Expectation–Maximization)

algorithm
Dr. Sutikno
 EM (Expectation–Maximization)
algorithm
• Expectation–Maximization (EM) adalah algoritma iteratif yang
digunakan untuk mengestimasi parameter model statistik
ketika data yang tersedia tidak lengkap, mengandung variabel
tersembunyi (laten).
• EM bekerja dengan dua langkah utama yang dilakukan
berulang-ulang sampai konvergen:
– E-step (Expectation step)
• Menghitung nilai harapan (ekspektasi) dari variabel tersembunyi berdasarkan
parameter saat ini.
• Artinya, pada tahap ini algoritma “menebak” data yang hilang atau variabel laten.
– M-step (Maximization step)
• Menghitung ulang atau memperbarui parameter model untuk memaksimalkan
likelihood (peluang) berdasarkan hasil dari E-step.
 EM (Expectation–Maximization)
algorithm
• Siklus Iteratif
– Langkah E dan M dilakukan berulang:
–E→M→E→M
• hingga nilai parameter stabil (konvergen), yaitu ketika
perubahan likelihood sangat kecil.
• Tujuan Akhir
– Menemukan estimasi parameter terbaik
(maximum likelihood estimate) meskipun sebagian
informasi dalam data tidak diketahui secara
langsung.
EM (Expectation–Maximization)
algorithm
 EM Algorithm
1. Mulai dengan tebakan awal
– Tentukan nilai awal untuk parameter model (misalnya
rata-rata, varians, atau peluang tiap kelompok).
2. Langkah E (Expectation)
– Gunakan parameter saat ini untuk memperkirakan data
yang hilang atau tersembunyi.
– Artinya, menghitung kemungkinan setiap data termasuk
ke kelompok tertentu.
3. Langkah M (Maximization)
– Setelah data yang hilang “diperkirakan”, perbarui
parameter model agar lebih sesuai dengan data yang
sudah dilengkapi.
 EM Algorithm
4. Ulangi langkah E dan M
– Lakukan langkah E dan M berulang-ulang sampai nilai
parameter tidak banyak berubah lagi (artinya sudah
konvergen).
5. Hasil akhir
– Diperoleh nilai parameter terbaik yang menggambarkan
data, meskipun sebagian informasinya tidak lengkap.
 Contoh: Mengisi Data Hilang
(Estimasi Rata-rata dan Varians)
Terdapat data tinggi badan (dalam cm):
𝑋=[160,165,?,170,?,175]
Tanda “?” artinya nilai hilang (missing).
Akan memperkirakan μ dan σ² menggunakan
EM.
 Langkah-langkah EM
Langkah 1. Inisialisasi
Tebak awal:

(berarti simpangan baku awal 5 cm)

Langkah 2. E-step (Estimasi Nilai Hilang)
• Isi nilai hilang dengan nilai harapan berdasarkan parameter
saat ini, yaitu rata-rata (μ).
• Data lengkap sementara:
– 𝑋=[160,165,?,170,?,175]
– 𝑋 = 160 165 165 170 165 175
 Langkah-langkah EM
Langkah 3. M-step (Update Parameter Baru)
Hitung mean dan varians baru dari data hasil E-step.
 Langkah-langkah EM
Iterasi 2
E-step: isi nilai hilang dengan mean baru

M-step: hitung ulang mean:

 Langkah-langkah EM
Iterasi 3
Isi nilai hilang dengan 167.22 → perbarui μ dan
σ² sedikit lagi → hasil akhirnya mendekati:
 Proses Iterasi
E-step: isi nilai hilang dengan tebakan terbaik (berdasarkan rata-
rata saat ini).
M-step: hitung kembali parameter (rata-rata dan varians) dari
data lengkap hasil E-step.
Ulangi sampai parameter tidak berubah banyak → konvergen.
Iterasi μ (mean) σ² (varians)
0 165.00 25.00
1 166.67 22.56
2 167.22 20.31
3 167.47 19.80
Akhir 167.5 ≈19.8
DBSCAN Clustering
 Apa itu DBSCAN?
• DBSCAN: Density-based Spasial Clustering of
Applications with Noise.
• DBSCAN adalah algoritma clustering berbasis
kepadatan (density).
• Mengelompokkan titik-titik yang berdekatan secara
padat, dan mengabaikan titik yang tersebar jauh
(noise).
• Cocok untuk data dengan bentuk klaster tidak
teratur.
 K-Means vs DBSCAN
• Terdapat point yang • Tidak memesahkan
seharusnya tidak point-point yang terpilih
berada pada kelompok kedalam kateori outlier.
manapun.
 Konsep Kepadatan dalam DBSCAN
• DBSCAN menggunakan dua parameter penting:
– ε (Epsilon): radius maksimum untuk mencari tetangga suatu
titik.
– MinPts: jumlah minimal titik dalam radius ε agar disebut
padat (dense region).
• Jika suatu titik memiliki ≥ MinPts tetangga dalam radius
ε → disebut core point.
 Tiga Jenis Titik dalam DBSCAN

• Core Point: memiliki ≥ MinPts titik

dalam radius ε, merupakan titik inti
area padat.
• Border Point: memiliki < MinPts tapi
berada dekat dengan core point
(pinggir klaster).
• Noise (Outlier): tidak memenuhi dua
kondisi di atas, bukan bagian dari
klaster manapun.
 Cara Kerja DBSCAN
1. Pemilihan Parameter
• Pilih ε (epsilon): Jarak maksimum antara dua titik agar keduanya dianggap sebagai
tetangga.
• Pilih MinPts: Jumlah minimum titik yang dibutuhkan untuk membentuk suatu
wilayah padat (dense region).
2. Pilih Titik Awal
• Algoritma memulai dari satu titik acak yang belum dikunjungi di dalam dataset.
3. Periksa Lingkungan Sekitar (Neighborhood)
• Algoritma mencari semua titik yang berada dalam jarak ε dari titik awal tersebut.
• Jika jumlah titik tetangga kurang dari MinPts, maka titik tersebut untuk sementara
diberi label noise (bukan bagian dari klaster).
• Jika terdapat setidaknya MinPts titik dalam jarak ε, maka titik tersebut diberi label
sebagai core point, dan klaster baru mulai dibentuk.
 Cara Kerja DBSCAN
4. Perluas Klaster (Cluster Expansion)
• Semua titik tetangga dari core point ditambahkan ke dalam
klaster.
• Untuk setiap titik tetangga:
– Jika titik tersebut juga merupakan core point, maka semua
tetangganya juga ditambahkan ke klaster secara rekursif.
– Jika titik tersebut bukan core point, maka diberi label sebagai border
point, dan perluasan berhenti di situ.
5. Ulangi Proses
• Algoritma berpindah ke titik lain yang belum dikunjungi dalam
dataset. Langkah (3) dan (4) diulangi hingga semua titik telah
diperiksa.
 Cara Kerja DBSCAN
6. Finalisasi Klaster
• Setelah semua titik diproses, algoritma
mengidentifikasi seluruh klaster yang terbentuk.
• Titik-titik yang sebelumnya dilabeli noise mungkin
berubah menjadi border point jika ternyata berada
dalam jarak ε dari suatu core point.
7. Penentuan Noise
• Titik-titik yang tidak termasuk dalam klaster mana
pun tetap diklasifikasikan sebagai noise.
Kelebihan dan Kelemahan DBSCAN
• Kelebihan:
– Tidak perlu menentukan jumlah klaster di awal.
– Mendeteksi bentuk klaster yang kompleks.
– Mampu mengenali noise (outlier).
• Kelemahan:
– Sulit menentukan nilai ε dan MinPts yang tepat.
– Tidak cocok untuk data dengan kepadatan klaster yang
sangat bervariasi.
 2. Contoh Data Sederhan
Misalkan kita punya 6 titik di garis 1 dimensi. Set parameter ε = 2 dan MinPts
=2

Titik Posisi (x)

A 1
B 2
C 3
D 8
E 9
F 25
 Langkah-langkah Perhitungan
1) Titik & posisi
A: 1
B: 2
C: 3
D: 8
E: 9
F: 25
Parameter: ε = 2, MinPts = 2
 Langkah-langkah Perhitungan
Manual
2) Cari tetangga tiap titik (jarak ≤ ε)
Karena ini 1-D, jarak = selisih nilai posisi.
• A (1): tetangga dalam ε = {A(1), B(2), C(3)} → |Nε(A)| = 3
• B (2): tetangga = {B(2), A(1), C(3)} → |Nε(B)| = 3
• C (3): tetangga = {C(3), B(2), A(1)} → |Nε(C)| = 3
• D (8): tetangga = {D(8), E(9)} → |Nε(D)| = 2
• E (9): tetangga = {E(9), D(8)} → |Nε(E)| = 2
• F (25): tetangga = {F(25)} → |Nε(F)| = 1
 Langkah-langkah Perhitungan
Manual
3) Klasifikasi core / border / noise
Kriteria core: |Nε| ≥ MinPts (≥2)
• A: 3 ≥ 2 → Core
• B: 3 ≥ 2 → Core
• C: 3 ≥ 2 → Core
• D: 2 ≥ 2 → Core
• E: 2 ≥ 2 → Core
• F: 1 < 2 → Noise
 Langkah-langkah Perhitungan
Manual
5) Hasil akhir
• Cluster 1: {A, B, C} (posisi 1,2,3)
• Cluster 2: {D, E} (posisi 8,9)
• Noise: {F} (posisi 25)
 Contoh 2
Parameter:
• ε (jarak maksimum) = 2
• MinPts = 2
Titik x y
A 1 1
B 2 1
C 2 2
D 8 8
E 8 9
F 25 25
 Penyelesaian
Langkah 1. Hitung jarak antar titik (Euclidean
distance)
Dari/Ke A B C D E F
A 0 1 1.41 9.90 10.63 33.94
B 1 0 1 9.22 9.90 33.23
C 1.41 1 0 8.48 9.22 32.53
D 9.90 9.22 8.48 0 1 24.04
E 10.63 9.90 9.22 1 0 23.34
F 33.94 33.23 32.53 24.04 23.34 0
 Penyelesaian
Langkah 2. Tentukan tetangga dalam radius ε = 2
• 2) Tetangga dalam radius ε = 2 (sertakan titik itu sendiri)
• Nε(A) = {A, B, C} → |Nε(A)| = 3 Dari/K
A B C D E F
e
• Nε(B) = {B, A, C} → |Nε(B)| = 3
A 0 1 1.41 9.90 10.63 33.94
• Nε(C) = {C, A, B} → |Nε(C)| = 3
B 1 0 1 9.22 9.90 33.23
• Nε(D) = {D, E} → |Nε(D)| = 2
C 1.41 1 0 8.48 9.22 32.53
• Nε(E) = {E, D} → |Nε(E)| = 2
D 9.90 9.22 8.48 0 1 24.04
• Nε(F) = {F} → |Nε(F)| = 1
E 10.63 9.90 9.22 1 0 23.34
F 33.94 33.23 32.53 24.04 23.34 0
 Penyelesaian
Langkah 3. Tentukan jenis titik
• Titik core: jumlah tetangga (termasuk dirinya) ≥ MinPts = 2
• Titik border: bukan core tapi tetangga dari core
• Titik noise: bukan core dan bukan tetangga core
Kriteria core: |Nε| ≥ MinPts (≥2)
• A: 3 ≥ 2 → Core
• B: 3 ≥ 2 → Core
• C: 3 ≥ 2 → Core
• D: 2 ≥ 2 → Core
• E: 2 ≥ 2 → Core
• F: 1 < 2 → Noise
 Penyelesaian
Langkah 4. Bentuk cluster
• Mulai dari A (core) → tambahkan B, C → karena B & C juga
core dan hanya berhubungan satu sama lain, Cluster 1 = {A, B,
C}.
• Lanjut D (core) → tambahkan E → Cluster 2 = {D, E}.
• F tidak terhubung ke siapa pun → Noise = {F}.
Hasil Akhir:
• Cluster 1: {A, B, C} (sekitar (1,1)-(2,2))
• Cluster 2: {D, E} (sekitar (8,8)-(8,9))
• Noise: {F} (25,25)
 Soal 1
Terdapat data berat badan (dalam kg) sebagai berikut:
𝑋=[55,60,z,65,70,z,75,80]
Variabel z menunjukkan data yang hilang (missing value).
Asumsikan bahwa data mengikuti distribusi normal..
Tunjukkan langkah iterasi pertama (E-step dan M-step) dengan
asumsi awal:
 Soal 2
Misalkan terdapat 7 titik pada bidang 2 dimensi [Link] parameter ε
= 3 dan MinPts = 3 untuk melakukan klasterisasi dengan algoritma DBSCAN.
1. Tentukan titik mana saja yang termasuk core point, border point, dan
noise point.
2. Sebutkan hasil akhir cluster yang terbentuk.
Titik x y
A 1 1
B 2 2
C 3 2
D 10 10
E 11 10
F 11 11
G 25 25
TERIMAKASIH