DATA MINING
Topic 2. Clusterring
Randy Permana, [Link]
DEFINISI CLUSTERING
Merupakan pengelompokkan objek data yang berbeda, yang dimasukkan ke
dalam objek yang serupa.
Kumpulan data akan dibagi menjadi beberapa kelompok yang berbeda yang
didasarkan pada kesamaan data.
Analisis Cluster dalam Data Mining berarti untuk mengetahui kelompok
objek yang mirip satu sama lain dalam satu kelompok tetapi berbeda
dengan objek di kelompok lain.
Data Mining_Randy Permana, [Link]
KEGUNAAN CLUSTERING
Interpretasi
Hasil clustering harus dapat digunakan, dimengerti dan ditafsirkan.
Membantu dalam menangani data yang kacau
Clustering dapat memberikan beberapa struktur pada data dengan
mengaturnya ke dalam kelompok-kelompok objek data yang serupa.
Dimensi Tinggi
Clustering juga mampu menangani data yang berdimensi tinggi maupun
yang berukuran kecil.
Data Mining_Randy Permana, [Link]
KEGUNAAN CLUSTERING
Kegunaan dengan banyak jenis data
Banyak jenis data yang berbeda dapat digunakan dengan algoritma
pengelompokan. Data tersebut dapat berupa data biner, data kategorikal
dan data berbasis interval.
Skalabilitas Pengelompokan
Basis data biasanya sangat besar untuk ditangani. Algoritma harus dapat
diskalakan untuk menangani basis data yang luas, sehingga harus dapat
diskalakan.
Data Mining_Randy Permana, [Link]
ALGORITMA K-MEANS
K-means merupakan metode clustering secara partitioning yang memisahkan data
ke dalam kelompok yang berbeda
Dengan partitioning secara iteratif, K-Means mampu meminimalkan rata-rata
jarak setiap data ke cluster-nya
K-means merupakan salah satu metode cluster analysis non hirarki yang berusaha
untuk mempartisi objek yang ada ke dalam satu atau lebih cluster/kelompok objek
berdasarkan karakteristiknya
Sehingga objek yang mempunyai karakteristik yang sama dikelompokan dalam satu
cluster yang sama dan objek yang mempunyai karakteristik yang berbeda
dikelompokan kedalam cluster yang lain
.Data Mining_Randy Permana, [Link]
ALGORITMA K-MEANS
Kelebihan Algoritma K-Means, yaitu:
Mudah untuk diimplementasikan dan dijalankan.
Waktu yang dibutuhkan untuk menjalankan pembelajaran ini relatif
cepat.
Mudah untuk diadaptasi.
Umum digunakan.
Data Mining_Randy Permana, [Link]
ALGORITMA K-MEANS
Kekurangan Algoritma K-Means, yaitu:
• Nilai k (jumlah cluster) diinisialisasi secara random sehingga
pengelompokkan data yang dihasilkan dapat berbeda-beda. Jika nilai
random untuk inisialisasi kurang baik, maka pengelompokkan yang
dihasilkan pun menjadi kurang optimal.
• Dapat terjebak dalam masalah yang disebut curse of dimensionality.
Terjadi jika data pelatihan memiliki dimensi yang sangat tinggi (Jika data
pelatihan terdiri dari 2 atribut maka dimensinya adalah 2 dimensi. Namun
jika ada 20 atribut, maka akan ada 20 dimensi)
Data Mining_Randy Permana, [Link]
ALGORITMA K-MEANS
Kekurangan Algoritma K-Means, yaitu:
Jika hanya terdapat beberapa titik sampel data, maka cukup mudah untuk
menghitung dan mencari titik terdekat dengan k titik yang diinisialisasi
secara random. Namun jika terdapat banyak sekali titik data, maka
perhitungan dan pencarian titik terdekat akan membutuhkan waktu yang
lama.
Data Mining_Randy Permana, [Link]
ALGORITMA K-MEANS
Dasar algoritma K-means adalah sebagai berikut :
1. Tentukan nilai k sebagai jumlah klaster yang ingin dibentuk.
2. Bangkitkan k centroid (titik pusat klaster) awal secara random.
3. Hitung jarak setiap data ke masing-masing centroid menggunakan
rumus korelasi antar dua objek yaitu Euclidean Distance
4. Kelompokkan setiap data berdasarkan jarak terdekat antara data
dengan centroidnya.
Data Mining_Randy Permana, [Link]
ALGORITMA K-MEANS
4. Tentukan posisi centroid baru (Ck ) dengan cara menghitung nilai
rata-rata dari data-data yang ada pada centroid yang sama.
Dimana : nk = jumlah dokumen dalam cluster k
di = dokumen dalam cluster k.
5. Kembali ke langkah 3 jika posisi centroid baru dengan centroid
lama tidak sama.
Data Mining_Randy Permana, [Link]
CONTOH KASUS K MEANS
Diketahui Data (M) yang dipengaruhi oleh Atribut X dan Y berikut :
Data X Y
M1 2 5
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
Data Mining_Randy Permana, [Link]
CONTOH KASUS K MEANS
Penyelesaian Kasus :
1. Tentukan nilai k sebagai jumlah klaster yang ingin dibentuk
Data akan dikelompokkan menjadi dua cluster (nilai k = 2)
2. Bangkitkan Centroid secara random sesuai dengan nilai k
Karena nilai k = 2, maka centroid yang dibangkitkan ada 2, yaitu :
C1=(3 ; 4), C2=(6 ; 4)
Data Mining_Randy Permana, [Link]
CONTOH KASUS K MEANS
3. Hitung jarak setiap data ke masing-masing centroid menggunakan
rumus korelasi antar dua objek yaitu Euclidean Distance
Hitung Jarak setiap M ke C1 :
Data Mining_Randy Permana, [Link]
CONTOH KASUS K MEANS
3. Hitung jarak setiap data ke masing-masing centroid menggunakan
rumus korelasi antar dua objek yaitu Euclidean Distance
Jarak dari M ke C1 Jarak dari M ke C2
D11 = 1.41 D21 = 4.12
D12 = 1.80 D22 = 4.27
D13 = 2.06 D23 = 1.12
D14 = 3.94 D24 = 1.87
D15 = 4.06 D25 = 1.22
D16 = 0.94 D26 = 2.62
D17 = 1.12 D27 = 2.06
Data Mining_Randy Permana, [Link]
CONTOH KASUS K MEANS
4. Kelompokkan setiap data berdasarkan jarak terdekat antara
data dengan centroidnya
M1 M2 M3 M4 M5
M6 M7
jarak ke C1 1.41 1.80 2.06 3.94 4.06 0.94 1.12
C2 4.12 4.27 1.12 1.87 1.22 2.62
2.06
{M1 , M2 , M6 , M7 } anggota C1 dan
{M3 , M4 , M5 } anggota C2
Data Mining_Randy Permana, [Link]
CONTOH KASUS K MEANS Anggota C1
Data X Y
5. Tentukan posisi centroid baru M1 2 5
M2 2 5.5
M6 3.5 4.8
M7 4 4.5
Anggota C2
Data X Y
C1baru = (2.88 ; 4.9) M3 5 3.5
C2baru = (6.17 ; 3)
M4 6.5 2.2
M5 7 3.3
Data Mining_Randy Permana, [Link]
CONTOH KASUS K MEANS
6. Karena Centroid Baru TIDAK SAMA dengan Centroid Lama
Maka, kembali ke Langkah 3, hitung jarak setiap M ke C1baru
dan C2 baru dengan Euclidean Distance
Jarak dari M ke C1baru Jarak dari M ke C2baru
D11 = 0.88 D21 = 4.62
D12 = 1.04 D22 = 4.86
D13 = 2.57 D23 = 1.27
D14 = 4.55 D24 = 0.87
D15 = 4.55 D25 = 0.88
D16 = 0.64 D26 = 3.22
D17 = 1.21 D27 = 2.64
Data Mining_Randy Permana, [Link]
CONTOH KASUS K MEANS
7. Kelompokkan setiap data berdasarkan jarak terdekat antara
data dengan centroidnya
M1 M2 M3
M4 M5 M6 M7
jarak ke C1 0.88 1.04 2.57 4.55 4.55 0.64 1.21
C2 4.62 4.86 1.27 0.87 0.88 3.22
2.64
{M1 , M2 , M6 , M7 } anggota C1 dan
{M3 , M4 , M5 } anggota C2
Data Mining_Randy Permana, [Link]
CONTOH KASUS K MEANS
Dari Langkah 3 dan Langkah 7, tidak terjadi Perubahan atau
Perpindahan Anggota Cluster, maka proses dihentikan.
Kesimpulan
{M1 , M2 , M6 , M7 } anggota C1 dan
{M3 , M4 , M5 } anggota C2
Latihan : dengan data yang sama lakukan clustering jika nilai K=
3
C1 (2; 5) C2 (3,5;5) C3 (6;2)
Data Mining_Randy Permana, [Link]