Slide_DM_08_Clustering

Report
Minggu lalu
• Decision tree
• Bayesian Classification
• Ujian
Clustering : k-means
Overview: Tabel Delapan nasabah Bank
ABC yg pernah memperoleh kredit
Nasabah
A
B
C
D
E
F
G
H
Rumah
1
3
4
5
1
4
1
2
Mobil
3
3
3
3
2
2
1
1
Overview
• Mari kita simak, renungi, pelajari Tabel delapan
nasabah yg pernah memperoleh kredit dari Bank ABC.
• Diharapkan kita dpt mengelompokkan (clustering) ke-8
nasabah tsb ke dlm bbrp kelompok nasabah.
• Pengelompokkan yg diharapkan yg mampu
menghasilkan kelompok nasabah yg memenuhi sifat
sbb:
– Nasabah yg jumlah rmh dan mobilnya hampir sama akan
berada pd kelompok nasabah yg sama
– Nasabah yg jumlah rumah dan mobilnya cukup berbeda
akan berada pada kelompok nasabah yg berbeda.
Overview
• Hal-hal yg akan dikelompokan disebut “objek”
atau “catatan”.
• Bdsk Tabel, objek dpt mengambil bentuk ke-8
nasabah yg akan dikelompokkan.
• Setiap objek dibedakan dari objek lain
berdasarkan atribut yg dimilikinya masing2.
• Pada Tabel, objek dicirikan oleh “atribut” yg
berupa jumlah “mobil” dan “rumah” yg
dimiliki.
Overview
• Kumpulan dari seluruh atribut disebut “data input”
• Pada tabel, data input  himpunan dari keseluruhan
atribut jumlah rumah dan mobil yg dimiliki objek
(berupa nasabah) yg akan dikelompokkan
• Hasilnya  pengetahuan yg diperoleh merupakan
pengetahuan berupa penentuan beberapa kelompok
catatan yg memiliki kemiripan atribut.
• Secara ringkas, catatan2 yg memiliki kemiripan atribut
akan dikelompokkan ke dalam salah satu dari sekian
kelompok
• Adapun catatan2 yg kurang memiliki kesamaan atribut
akan ditempatkan pada kelompok yg berbeda
Overview
• Pengelompokkan berawal dari data input yg
tersedia  tabel
• Data input diolah dengan menggunakan
algoritma clustering
• Masalah pengelompokkan berakhir dgn
dihasilkannya 2 atau lebih kelompok objek
sehingga objek2 yg memiliki atribut akan
dimasukkan ke dalam kelompok yg sama, dan
objek2 yg jrg memiliki kemiripan atribut akan
dimasukkan dalam kelompok yg berbeda
Contoh
• Bsdk tabel 1, hendak dikelompokkan ke dalam
3 kelompok
• Hasil pengelompokkan pada Tabel 2
merupakan pengetahuan yg dihasilkan dari
fungsi pengelompokan
Tabel 1
Nasabah
A
B
C
D
E
F
G
H
Rumah
1
3
4
5
1
4
1
2
Mobil
3
3
3
3
2
2
1
1
Tabel 2
Cluster
Anggota Cluster
1
{B}
2
{A, E, G, H}
3
{C, D, F}
Contoh:
• Pengetahuan yg didapatkan dlm interpretasi sbb:
– Kelompok Nasabah pertama  kelompok yg unik krn
hanya memiliki seoranga anggota saja (hanya B), yg
kelak jelas bagi kita bhw kelompok ini mrpk kelompok
nasabah yg memiliki jumlah rmh sedang (3 buah) dan
jumlah mobil banyak (3 buah)
– Kelompok Nasabah kedua  memiliki 4 org anggota
(A, E, G, H), yg kelak akan menjadi jelas bagi kita bhw
kelompok ini mrpkan kelompok nasabah yg memiliki
rata2 jumlah rmh sedikit (1,25 buah) dan rata2 jumlah
mobil sedikit pula (1,75 buah)
– Kelompok Nasabah ketiga  memiliki 3 org anggota
(C, D, F), yg kelak akan jelas bagi kita bhw kelompok ini
merupakan kelompok nasabah yg memiliki rata2
jumlah rmh banyak (4,33 buah) dan rata2 jumlah
mobil yg cukup banyak (2,67 buah)
Algoritma pengelompokan k-means
• Pembahasan dpt kita ringkas sbb:
– Kita memiliki data input berupa atribut dari 8 buah
catatan nasabah (Tabel A) dan kita ingin peroleh
pengetahuan mengenai bgm catatan2 itu hrs
dikelompokan agar diperoleh kelompok catatan yg
memiliki kemiripan atribut
– Data input tsb kelak akan dijadikan masukan bagi
suatu algoritma, yg saat ini blm kita ketahui jenis
algoritmanya
– Sbg keluaran algoritma yg belum kita ketahui jenisnya,
kita akan peroleh pengetahuan berupa kelompok
catatan yg memiliki kemiripan atribut
• Algoritma k- means akan menghasilkan
kelompok catatan sebanyak k buah
• Algoritma ini digagas pertama kali oleh J.
MacQueen
Langkah-langkah Algoritma k-means
• Pertama, tanyakan kpd user algoritma k-means,
catatan2 yg ada akan dibuat menjadi berapa kelompok
(misalnya sebanyak k kelompok)
• Kedua, secara random, pilihlah k buah catatan (dari
sekian catatan yg ada) sebagai pusat kelompok awal
• Ketiga, untuk setiap catatan, tentukan pusat kelompok
terdekatnya dan tetapkan catatan tsb sbg anggota dari
kelompok yg terdekat pusat kelompoknya. Hitung rasio
antara besaran “Between Cluster Variation” dgn
“Within Cluster Variation”, lalu bandingkan rasio tsb
dgn rasio sebelumnya (bila sdh ada). Jika rasio tsb
membesar, lanjutkan ke langkah keempat. Jika tidak,
hentikan prosesnya
• Keempat, perbaharui pusat-pusat kelompok
(berdasarkan kelompok yg didapat dari langkah ketiga)
dan kembalilah ke langkah ketiga.
Contoh penerapan:
1. Langkah 1
• Data input didpt dari Tabel 1
• Tanyakan kpd user, catatan2 yg ada akan
dijadikan brp kelompok  Misalkan 3
kelompok, maka k-nya adalah 3 atau k=3
2. Langkah 2
• Kita akan memilih secara random 3 buah (3
buah krn k=3) catatan dari 8 catatan yg ada
pada Tabel 1 sbg pusat2 kelompok awal
• Misalnya,
– Catatan B sbg pusat kelompok 1 shg m1=(3,3)
– Catatan E sbg pusat kelompok 2 shg m2=(1,2)
– Catatan F sbg pusat kelompok 3 shg m3=(4,2)
3. Langkah 3: Iterasi 1
• Setiap catatan akan ditentukan pusat
kelompok terdekatnya. Catatan tsb akan
ditetapkan sbg anggota kelompok yg terdekat
pusat kelompoknya (lihat Tabel 3)
Langkah 3: Iterasi 1
• Contoh cara hitung jarak:
– Catatan A ke pusat kelompok 1 (B)
A(1,3) dan B(3,3) maka Jarak = [ (1-3)2 + (3-3)2 ]0,5 = 2
– Catatan A ke pusat kelompok 2 (E)
A(1,3) dan E(1,2) maka Jarak = [ (1-1)2 + (3-2)2 ]0,5 =1
– Catatan A ke pusat kelompok 3 (F)
A(1,3) dan F(4,2) maka Jarak = [ (1-4)2 + (3-2)2 ]0,5 = 3,162
Catatan
Jarak ke
Pusat
kelompok 1
Jarak ke
Pusat
kelompok 2
Jarak ke
Pusat
kelompok 3
Jarak
terdekat ke
kelompok
A
2
1
3,162
C2
...
...
...
...
...
H
2,236
1,414
2,236
C2
Tabel 3: Iterasi ke-1
Catatan
Jarak ke
Pusat
kelompok 1
 B(3,3)
Jarak ke
Pusat
kelompok 2
 E(1,2)
Jarak ke
Pusat
kelompok 3
 F(4,2)
Jarak
terdekat ke
kelompok
A (1,3)
2
1
3,162
C2
B (3,3)
0
2,236
1,414
C1
C (4,3)
1
3,162
1
C3
D (5,3)
2
4,123
1,414
C3
E (1,2)
2,236
0
3
C2
F (4,2)
1,414
3
0
C3
G (1,1)
2,828
1
3,162
C2
H (2,1)
2,236
1,414
2,236
C2
• Bdsk Tabel 3, didpt keanggotaan sbg berikut:
– Kelompok 1 atau C1 = {B}
– Kelompok 2 atau C2 = {A, E, G, H}
– Kelompok 3 atau C3 = {C, D, F}
• Selanjutnya, hitung rasio antara BCV dgn WCV,
sbb:
BCV = d(m1, m2) + d(m1, m3) + d(m2, m3)
= 2,236 +1,414 + 3 = 6,650
WCV = 12 +02 +12 +1,4142+02+02+12+1,4142 = 7
Maka BCV/WCV = 6,650/7 = 0,950
Hitung Rasio BCV dgn WCV
Catatan
Jarak ke Pusat
pok 1 (B)
Jarak ke Pusat
pok 2 (E)
Jarak ke Pusat
pok 3 (F)
Jarak terdekat
ke
A
2
1
3,162
C2
B
0
2,236
1,414
C1
C
1
3,162
1
C3
D
2
4,123
1,414
C3
E
2,236
0
3
C2
F
1,414
3
0
C3
G
2,828
1
3,162
C2
H
2,236
1,414
2,236
C2
BCV = d(m1, m2) + d(m1, m3) + d(m2, m3)
= 2,236 +1,414 + 3 = 6,650
WCV = 12 +02 +12 +1,4142+02+02+12+1,4142 = 7
Maka BCV/WCV = 6,650/7 = 0,950
• Dengan memperhatikan bhw langkah
sebelumnya blm ada rasio ini, maka
perbandingan rasio belum dpt dilakukan maka
algoritma dilanjutkan langkah ke-empat
4. Langkah 4: Iterasi 1
• Pada langkah ini, perbaharui pusat2 kelompok dgn
hasil sbb:
– m1 = rata2 (mB) = (3,3)
– m2 = rata2 (mA, mE, mG, mH) = (1,25; 1,75)
Cara hitungnya
A
1
3
E
1
2
G
1
1
H
2
1
Jml
5
7
hasil
5/4 =
1,25
7/4 =
2,75
– m3 = rata2 (mC, mD, mF) = (4,333; 3,667)
5. Langkah 3: Iterasi 2
• Sama dengan langkah 3 iterasi 1, hitung jarak
setiap catatan ke pusat masing kelompoknya
• Hasil terlihat pata Tabel 4: Iterasi ke-2
Tabel 4: Iterasi ke-2
Jarak ke
Jarak ke
Pusat
Pusat
kelompok 3
kelompok 2
 (1.25, 1.75)  (4.33, 3.66)
Catatan
Jarak ke
Pusat
kelompok 1
 (3,3)
A (1,3)
2
1,275
3,350
C2
B (3,3)
0
1,768
1,374
C1
C (4,3)
1
3,021
0,471
C3
D (5,3)
2
3,953
0,745
C3
E (1,2)
2,236
0,354
3,399
C2
F (4,2)
1,414
2,813
0,745
C3
G (1,1)
2,828
0,791
3,727
C2
H (2,1)
2,236
1,061
2,867
C2
Jarak
terdekat ke
kelompok
• Bdsk Tabel 4, didpt keanggotaan sbg berikut:
– Kelompok 1 atau C1 = {B}
– Kelompok 2 atau C2 = {A, E, G, H}
– Kelompok 3 atau C3 = {C, D, F}
• Selanjutnya, hitung rasio antara BCV dgn WCV, sbb:
BCV = d(m1, m2) + d(m1, m3) + d(m2, m3)
= 6,741
WCV = 4,833
Maka BCV/WCV = 6,741/4,833 = 1,394
Tampak bhw rasio ini (1,394) membesar dibandingkan rasio
sejenis yg didptkan pd langkah sebelumnya (0,950)
Oleh krn itu, algoritma dilanjutkan kelangkah ke 4.
6. Langkah 4: Iterasi ke-3
• Pada langkah ini, perbaharui pusat2 kelompok
dgn hasil sbb:
– m1 = rata2 (mB) = (3,3)
– m2 = rata2 (mA, mE, mG, mH) = (1,25; 1,75)
– m3 = rata2 (mC, mD, mF) = (4,333; 3,667)
7. Langkah 3: Iterasi ke-3
• Pada langkah ini, pusat kelompok terdekat utk
setiap catatan akan ditentukan
• Tetapkan catatan tsb sbg anggota kelompok yg
terdekat pusat kelompoknya
• Hasil lengkap terlihat pada Tabel 5
Tabel 5: Iterasi ke-3
Catatan
Jarak ke
Pusat
kelompok 1
(B)
Jarak ke
Pusat
kelompok 2
(E)
Jarak ke
Pusat
kelompok 3
(F)
Jarak
terdekat ke
kelompok
A
2
1,275
3,350
C2
B
0
1,768
1,374
C1
C
1
3,021
0,471
C3
D
2
3,953
0,745
C3
E
2,236
0,354
3,399
C2
F
1,414
2,813
0,745
C3
G
2,828
0,791
3,727
C2
H
2,236
1,061
2,867
C2
• Bdsk Tabel 5, didpt keanggotaan sbg berikut:
– Kelompok 1 atau C1 = {B}
– Kelompok 2 atau C2 = {A, E, G, H}
– Kelompok 3 atau C3 = {C, D, F}
• Selanjutnya, hitung rasio antara BCV dgn WCV, sbb:
BCV = d(m1, m2) + d(m1, m3) + d(m2, m3)
= 6,741
WCV = 4,833
Maka BCV/WCV = 6,741/4,833 = 1,394
Tampak bhw rasio ini (1,394) sudah tdk lagi membesar
dibandingkan rasio sejenis yg didptkan pd langkah
sebelumnya (1,394)
Oleh krn itu, algoritma akan dihentikan
Pengetahuan apa yg didapat?
– Kelompok Nasabah pertama  kelompok yg unik krn
hanya memiliki seoranga anggota saja (hanya B), yg
kelak jelas bagi kita bhw kelompok ini mrpk kelompok
nasabah yg memiliki jumlah rmh sedang (3 buah) dan
jumlah mobil banyak (3 buah)
– Kelompok Nasabah kedua  memiliki 4 org anggota
(A, E, G, H), yg kelak akan menjadi jelas bagi kita bhw
kelompok ini mrpkan kelompok nasabah yg memiliki
rata2 jumlah rmh sedikit (1,25 buah) dan rata2 jumlah
mobil sedikit pula (1,75 buah)
– Kelompok Nasabah ketiga  memiliki 3 org anggota
(C, D, F), yg kelak akan jelas bagi kita bhw kelompok ini
merupakan kelompok nasabah yg memiliki rata2
jumlah rmh banyak (4,33 buah) dan rata2 jumlah
mobil yg cukup banyak (2,67 buah)
Algoritma Pengelompokan lainnya
•
•
•
•
•
•
Algoritma hierarchical clustering
Algoritma partition clustering
Algoritma single linkage
Algoritma complete linkage
Algoritma average linkage
dll
Selesai
Lupakan

similar documents