algoritma clustering - universitas algoritma klastering.pdf · pdf file p4 p1 p3 p2 p4 p1...

Click here to load reader

Post on 03-Nov-2020

14 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

  • Algoritma Clustering Amil Ahmad Ilham

    1

  • Pengertian Cluster

    Cluster: Kumpulan dari object data, dimana data dalam cluster yang sama memiliki kemiripan dan memiliki perbedaan dengan data yang berada dalam cluster lain (Jia Wei-Han)

    Centroid: Titik pusat cluster

    Proses pembelajaran di dalam cluster : • Jarak antar data dalam cluster sama di minimalkan

    (memaksimalkan kemiripan) • Jarak antar data dari cluster berbeda di maksimalkan

    (memaksimalkan perbedaan)

    2

  • Tujuan: Cluster Analysis • Menentukan kelompok objects data sedemikian hingga object data yang berada

    dalam satu kelompok memiliki kemiripan satu dengan lainnya, dan memiliki berbedaan dengan object data yang berada dalam kelompok lain

    Memaksimasi Inter- cluster distances

    Meminimasi Intra- cluster distances

    Tujuan

    3

  • Gambaran Cluster

    Data set pada gambar secara alami memiliki tiga kelompok data. Dengan demikian data set ini terdiri dari 3 cluster.

    4

  • Bagaimana melakukan clustering

    5

  • Macam clustering

    • Partitional Clustering

    Proses untuk membagi sekumpulan objek ke dalam beberapa cluster dimana setiap anggota cluster tidak terjadi overlap. Artinya sebuah object data hanya akan menjadi bagian dari sebuah cluster

    • Hierarchical Clustering

    Proses untuk membagi sekumpulan objek ke dalam beberapa cluster yang memungkinkan terjadi overlap. Sebuah object data bisa menjadi anggota lebih dari satu cluster.

    Sehingga penggambaran cluster dalam bentuk hierarchical tree atau dendogram

    6

  • Partitional Clustering

    A Partitional Clustering

    7

  • Hierarchical Clustering

    p4

    p1 p3

    p2

    p4

    p1 p3

    p2

    p4p1 p2 p3

    p4p1 p2 p3

    dicluster menjadi

    8

  • Euclidean Distance

    Contoh

    A(3,2)

    B(10,6)

    𝑑𝐸 𝐵, 𝐴 = (10 − 3) 2+(6 − 2)2

    𝑑𝐸 𝐵, 𝐴 = 8.06

    𝑑𝐸 𝐵, 𝐴 = 49 + 16

    𝑑𝐸 𝐵, 𝐴 = 65

    9

  • Algoritma K-Means Algoritma K-Means

    10

  • Algoritma K-Means

    • K-Means adalah salah satu partitional clustering yang terkenal

    • Parameter K menunjukkan banyaknya cluster yang akan dibentuk

    • Perbandingan dengan metode lain

    • Kelebihan: komputasi yang sederhana

    • Kekurangan: kualitas kluster tergantung pada pemilihan centroid awal dan nilai k.

    • Nilai k ditentukan di awal.

    • Koordinat awal setiap centroid ditentukan secara acak.

    11

  • Algoritma K-Means Contoh k-Means clustering dengan k=3 (berarti ada 3 centroid yaitu m1, m2, m3)

    Setiap cluster diasosiasikan dengan sebuah centroid

    Setiap point data dimasukkan ke cluster dengan centroid terdekat berdasarkan jarak terkecil.

    12

  • Algoritma K-Means

    1.Tentukan jumlah klaster (k) 2.Tentukan koodinat awal setiap centroid secara acak. 3. Hitung jarak setiap data ke setiap centroid (misalnya

    menggunakan Euclidean Distance) 4.Tentukan keanggotaan setiap centroid berdasarkan jarak terdekat

    dari data ke centroid 5.Update koordinat dari masing-masing centroid 6. Kembali ke no 3, iterasi berhenti jika sudah tidak ada perubahan

    keanggotaan centroid

    13

  • Cara kerja k-means

    14

    Misalnya akan dilakukan pengelompokan pelanggan berdasarkan “Age” dan “Income”

  • Cara kerja k-means (langkah ke-1)

    Misalnya data akan dikelompokkan menjadi 3 klaster, maka ditetapkan nilai k = 3

    15

  • Cara kerja k-means (langkah ke-2)

    Karena k = 3, maka ada 3 titik koordinat awal centroid yang harus ditentukan secara acak, misalnya:

    16

  • Cara kerja k-means (langkah ke-3)

    Hitung jarak (distance) dari setiap data ke setiap centroid. Misalnya: • jarak dari data ke c1 adalah d(p1,c1), d(p2,c1), d(p3,c1) …

    • Jarak dari data ke c2 adalah d(p1,c2), d(p2,c2), d(p3,c2) …

    • Jarak dari data ke c3 adalah d(p1,c3), d(p2,c3), d(p3,c3) …

    17

  • Cara kerja k-means (langkah ke-4) Tetapkan keanggotaan setiap centroid • Data yang memiliki jarak terdekat ke suatu centroid, ditetapkan menjadi anggota

    centroid tersebut.

    18

  • Cara kerja k-means (langkah ke-5)

    Hitung ulang koordinat setiap centroid sehingga centroid akan berpindah ke titik pusat klaster (berada ditengah-tengah anggotanya)

    19

    Koordinat baru centroid = (rata-rata nilai sumbu x, rata-rata nilai sumbu y)

  • Cara kerja k-means (perulangan)

    • Karena koordinat centroid berpindah, maka ulangi kembali langkat ke-3 sampai ke-5.

    • Iterasi berhenti jika tidak ada lagi anggota centroid yang pindah ke centroid lain (artinya koordinat centroid tidak berubah lagi)

    • Pengelompokan selesai.

    20

  • Contoh penggunaan k-means

    Misalkan ada 4 macam obat yang memiliki dua atribute (weight dan pH). Tujuan: mengelompokkan obat ini menjadi 2 klaster obat

    Medicine Weight pH-Index

    A 1 1

    B 2 1

    C 4 3

    D 5 4 A B

    C

    D

    21

  • Contoh penggunaan k-means (langkah ke-1)

    Karena 4 macam obat ini akan dikelompokkan menjadi 2 klaster, maka ditetapkan nilai k = 2

    Medicine Weight pH-Index

    A 1 1

    B 2 1

    C 4 3

    D 5 4 A B

    C

    D

    22

  • Contoh penggunaan k-means (langkah ke-2)

    Karena k = 2, maka ada 2 titik koordinat awal centroid yang harus ditentukan secara acak, misalnya: c1=(1,1) dan c2 = (2,1) (Kebetulan sama dengan koordinat A dan B)

    Medicine Weight pH-Index

    A 1 1

    B 2 1

    C 4 3

    D 5 4

    23

    A B

    C

    D

    C

    D

    A B

  • Contoh penggunaan k-means (langkah ke-3)

    Hitung jarak (distance) dari setiap data ke setiap centroid menggunakan Euclidean Distance. Koordinat centroid: c1=(1,1) dan c2 = (2,1)

    Medicine Weight pH-Index

    A 1 1

    B 2 1

    C 4 3

    D 5 4

    24

    Hitung distance (d): d(A,c1) = d(A,c2) =

    d(B,c1) = d(B,c2) =

    d(C,c1) = d(C,c2) =

    d(D,c1) = d(D,c2) =

    Tugas No. 1

    Tugas No. 1

  • Contoh penggunaan k-means (langkah ke-4)

    Tetapkan keanggotaan setiap centroid berdasarkan jarak terdekat dari data ke centroid

    Medicine Weight pH-Index

    A 1 1

    B 2 1

    C 4 3

    D 5 4

    25

    Hitung distance (d): d(A,c1) = d(A,c2) =

    d(B,c1) = d(B,c2) =

    d(C,c1) = d(C,c2) =

    d(D,c1) = d(D,c2) =

    Berdasarkan jarak terdekat: A -> c1 B, C, D -> c2

  • Contoh penggunaan k-means (langkah ke-5)

    Hitung ulang koordinat setiap centroid sehingga centroid akan berpindah ke titik pusat klaster (berada ditengah- tengah anggotanya)

    Medicine Weight pH-Index

    A 1 1

    B 2 1

    C 4 3

    D 5 4

    26

    c1: (1,1) => (1,1)

    c2: (2,1) => (3.67,2.67)

    c2 = (rata-rata nilai sumbu x, rata-rata nilai sumbu y)

  • Contoh penggunaan k-means (ulangi langkah ke-3)

    Hitung jarak (distance) dari setiap data ke setiap centroid menggunakan Euclidean Distance. Koordinat centroid: c1=(1,1) dan c2 = (3.67,2.67)

    Medicine Weight pH-Index

    A 1 1

    B 2 1

    C 4 3

    D 5 4

    27

    Hitung distance (d): d(A,c1) = d(A,c2) =

    d(B,c1) = d(B,c2) =

    d(C,c1) = d(C,c2) =

    d(D,c1) = d(D,c2) =

    Tugas No. 2

    Tugas No. 2

  • Contoh penggunaan k-means (ulangi langkah ke-4)

    Tetapkan keanggotaan setiap centroid berdasarkan jarak terdekat dari data ke centroid

    Medicine Weight pH-Index

    A 1 1

    B 2 1

    C 4 3

    D 5 4

    28

    Hitung distance (d): d(A,c1) = d(A,c2) =

    d(B,c1) = d(B,c2) =

    d(C,c1) = d(C,c2) =

    d(D,c1) = d(D,c2) =

    Berdasarkan jarak terdekat: A, B -> c1 (B pindah ke c1) C, D -> c2

  • Contoh penggunaan k-means (ulangi langkah ke-5)

    Hitung ulang koordinat setiap centroid sehingga centroid akan berpindah ke titik pusat klaster (berada ditengah- tengah anggotanya)

    Medicine Weight pH-Index

    A 1 1

    B 2 1

    C 4 3

    D 5 4

    29

    c = (rata-rata nilai sumbu x, rata-rata nilai sumbu y)

    ) 2

    1 3 ,

    2

    1 4(

    2

    43 ,

    2

    54

    )1 , 2

    1 1(

    2

    11 ,

    2

    21

    2

    1

     

      

      

     

      

      

    c

    c

  • Contoh penggunaan k-means (ulangi langkah ke-3)

    Hitung jarak (distance) dari setiap data ke setiap centroid menggunakan Euclidean Distance. Koordinat centroid: c1=(1.5,1) dan c2 = (4.5,3.5)

    Medicine Weight pH-Index

    A 1 1

    B 2 1

    C 4 3

    D 5 4

    30

    Hitung distance (d): d(A,c1) = d(A,c2) =

    d(B,c1) = d(B,c2) =

    d(C,c1) = d(C,c2) =

    d(D,c1) = d(D,c2) =

    Tugas No. 3

    Tugas No. 3