Data Mining
Metode Klasterisasi K-Means
Pokok Pembahasan 1. Konsep Dasar Clustering 2. Tahapan Clustering 3. K-Means Clustering Algoritma K-Means Rumus Umum K-Means 4. Case Study
Konsep Dasar • Klusterisasi Data, atau Data Clustering (atau Clustering), juga disebut sebagai analisis klaster, analisis segmentasi, analisis taxonomi, atau unsupervised classification. • Metode yang digunakan untuk membangun grup dari objek-objek, atau klaster-klaster, dimana objek-objek dalam satu kluster tertentu memiliki kesamaan ciri yang tinggi dan objekobjek pada kluster yang berbeda memiliki kesamaan ciri yang rendah.
Konsep Dasar • Tujuan dari klasterisasi data adalah mengelompokkan data yang memiliki kesamaan ciri dan memisahkan data ke dalam klaster yang berbeda untuk objek-objek yang memiliki ciri yang berbeda. • Berbeda dengan klasifikasi, yang memiliki kelas yang telah didefinisikan sebelumnya. Dalam klasterisasi, klaster akan terbentuk sendiri berdasarkan ciri objek yang dimiliki dan kriteria pengelompokan yang telah ditentukan.
Konsep Dasar • Untuk menunjukkan klasterisasi dari sekumpulan data, suatu kriteria pengelompokan haruslah ditentukan sebelumnya secara random. • Perbedaan kriteria pengelompokan akan memberikan dampak perbedaan hasil akhir dari klaster yang terbentuk.
Contoh • Dua klaster dengan kriteria berdasarkan “Bagaimana cara hewan mamalia berkembang biak”. Blue shark, sheep, cat, dog
Lizard, sparrow, viper, seagull, gold fish, frog, red mullet
• Dua klaster dengan kriteria berdasarkan “Keberadaan paru-paru”. Gold fish, red mullet, blue shark
Sheep, sparrow, dog, cat, seagull, lizard, frog, viper
Tahapan Klasterisasi 1. Feature Selection –
Penentuan informasi fitur yang digunakan.
2. Proximity Measure –
Tahap kuantifikasi item kemiripan data.
3. Clustering Criterion –
Penentuan fungsi pembobotan / tipe aturan.
4. Clustering Algorithm –
Metode klaster berdasarkan ukuran kemiripan data dan kriteria klasterisasi.
5. Validation of the Result 6. Interpretation of the Result
Proximity Measure • Kemiripan data memiliki peranan yang sangat penting dalam proses analisis klaster. • Pada berbagai literatur tentang clustering, ukuran kemiripan (similarity measures), koefisien kemiripan (similarity coefficients), ukuran ketidakmiripan (dissimilarity measures), atau jarak (distances) digunakan untuk mendeskripsikan nilai kuantitatif dari kemiripan atau ketidakmiripan dari dua titik atau dua klaster data.
Proximity Measure • Koefisien kemiripan menunjukkan kekuatan hubungan antara dua data. • Semakin banyak kemiripan titik data satu sama lain, maka semakin besar koefisien kesamaan. • Misalkan x = (x1, x2, ..., xd) dan y = (y1, y2, ..., yd) adalah dua titik data pada d dimensi. Maka nilai koefisien kemiripan antara x dan y adalah beberapa nilai atribut fungsi s(x,y) = s(x1, x2, ..., xd, y1, y2, ..., yd).
Proximity Measure • •
Pemilihan jarak pada clustering adalah sangat penting, dan pilihan yang terbaik sering diperoleh melalui pengalaman, kemampuan, pengetahuan. Pengukuran Jarak Data : – Numerik dengan banyak fitur atau dimensi (d) : - Euclidean Distance :
2 d euclid ( x, y ) x j y j j 1 d
- Manhattan Distance :
1 2
- Minkowski Distance :
r d minkow ( x, y ) x j y j j 1 d
j 1
- Maximum Distance :
d max ( x, y) max x j y j j 1..d
– Kategorikal : - Simple Matching Distance 0 if x y ( x, y ) 1 if x y
, r 1
- Mahalanobis Distance :
d
d man ( x, y ) x j y j
1 r
d mah ( x, y)
x y 1 x y T
- Average Distance :
1 d ave ( x, y ) d
x d
j 1
j
2 y j
d sim ( x, y ) x j , y j d
j 1
1 2
Proximity Measure •
Jika x1=(1,2) dan x2=(2,3). Hitunglah Jarak x1 dan x2 dengan Euclidean! d d euclid ( x1 , x2 ) x1 j x2 j j 1
•
Jika
1 x1 3 2
2 5 4 x2 7 3
1
2 2 2 2 1 2 2 3
5 1
1 2
1 2 2
1 1 2
22 1
2 1.4
Hitunglah Jarak x1 dan x2 dengan Mahalanobis!
(Note : Mahalanobis biasanya digunakan untuk menghitung jarak antar cluster) –
Hitung Mean Corected Matrix 1 2 x 3 2 2 2 0 1
–
2 3 1 1 4 3 3 3 0
Hitung Matrik Covarian (Ci) 1 0T 0 1 1 1 C1 x1 x1 n1 3 1 1 C2
1 0T 0 1 1 x2 x2 n2 2 2
x 0 i
1 1 0
5 7 5 1 1 3 2 2 4 3 x2 x 2 3 6 3 2 2 3 3 1
5 6 x20 7 6
5 3 1 1 3 1
2 2
1 1 0 1 2 2 0.7 0.7 1 1 3 2 2 0.7 0.7 0 0 0 1 1 2 1 2 4 1 2 2 1 2 8 2 4 2 4
Proximity Measure •
Jika –
1 x1 3 2
2 4 3
5 x2 7
5 1
Hitunglah Jarak x1 dan x2 dengan mahalanobis!
Hitung Matrik Covarian (Ci)
1 1 0 1 2 2 0.7 0.7 1 1 3 2 2 0.7 0.7 1 0 0 0 1 1 2 1 2 4 1 2 1 0T 0 1 1 C2 x2 x2 2 1 2 8 2 4 n2 2 2 2 4 1 0T 0 1 1 C1 x1 x1 n1 3 1
1 n
n g ro u p
1
1 2 3 0.7 n C n C i i 5 0.7 i i 5 i 1 i 1 0.4 0.4 0.8 0.8 0.4 0.4 0.8 1.6 0.4 2
1 n C i i n1 n2 i 1
0.4 0.4
1
2
0.7 2 1 0.7 5 2
2 4
2 0.4 1 1 1 2 0.4 1.4 0.3 Adj 0.8 * 2 0.4 * 0.4 0.4 0.8 1.44 0.4 0.8 0.3 0.6
Proximity Measure •
Jika
1 x1 3 2
–
1
2 4 3
5 x2 7
5 1
Hitunglah Jarak x1 dan x2 dengan mahalanobis!
2 0.4 1 1 1 2 0.4 1.4 0.3 Adj 0.8 * 2 0.4 * 0.4 0.4 0.8 1.44 0.4 0.8 0.3 0.6
Hitung Mean Different (X1,X2) :
5 7 5 1 1 3 2 2 4 3 x2 6 3 x 2 3 2 2 3 3 x1 , x2 2 6 3 3 4 0 1
d mah ( x1 , x2 )
x1 x2 1 x1 x2 T
d mah ( x1 , x2 )
x1 , x2 1 x1 , x2
T
5.6
4 1.1 0
4
22.2 4.7
1.4 0 0.3
0.3 4 0.6 0
K-Means • K-Means termasuk partitioning clustering yang memisahkan data ke k daerah bagian yang terpisah. • K-Means sangat terkenal karena kemudahan dan kemampuannya untuk mengklaster data besar dan data outlier dengan sangat cepat. • Setiap data harus masuk cluster tertentu.
K-Means • Kelemahan metode ini memungkinkan bagi setiap data yang termasuk cluster tertentu pada suatu tahapan proses, pada tahapan berikutnya berpindah ke cluster yang lain. • Prinsip utama dari teknik ini adalah menyusun k buah prototipe/pusat massa (centroid)/rata-rata (mean) dari sekumpulan data berdimensi n. • Teknik ini mensyaratkan nilai k sudah diketahui sebelumnya (a priori)
K-Means Algoritma K-Means adalah seperti berikut : 1. Tentukan k (jumlah cluster) yang ingin dibentuk 2. Bangkitkan k centroid (titik pusat cluster) awal secara random 3. Hitung jarak setiap data ke masing-masing centroid. 4. Kelompokkan obyek berdasar jarak minimum 5. Tentukan posisi centroid baru (Ck) untuk semua cluster dengan cara menghitung nilai rata-rata dari data-data yang berada pada cluster yang sama. 6. Kembali ke langkah 3 jika posisi centroid baru dan centroid lama tidak sama
Mulai
Jumlah kluster k
Pilih centroid
Hitung jarak obyek ke centroid
Kelompokkan berdasar jarak minimum
tidak Konvergen? ya
Selesai
Rumus Umum K-Means •
Menentukan Centroid (Titik Pusat) setiap kelompok diambil dari nilai ratarata (Means) semua nilai data pada setiap fiturnya. Jika M menyatakan jumlah data pada suatu kelompok, i menyatakan fitur ke-i dalam sebuah kelompok, berikut rumus untuk menghitung centroid :
1 Ci M •
M
x j 1
Hitung jarak titik terdekat (Euclidean Distance):
Dx2 , x1 •
j
p
x j 1
2j
x1 j
2
Pengalokasian keanggotaan titik :
1 , d min( D( x j , Ci )) a ji 0 , lainnya
•
Fungsi Objektif : N
K
F a ji D( x j , Ci ) j 1 i 1
Contoh Studi Kasus •
Perhatikan dataset berikut : Data 1 2 3 4 5 6 7 8 9 10
•
Fitur x 1 4 6 1 2 5 2 3 2 3
Fitur y 1 1 1 2 3 3 5 5 6 8
Kelompok 1 *
Bentuk Visualisasi data :
Kelompok 2
Kelompok 3
* * * * * *
* * *
Inisialisasi : K = 3, Fungsi Objektif (F) = 0, Threshold (T) = 0.8, dan Data dicluster sebanyak K secara random. Tentukan Hasil Akhir Clusteringnya !
Contoh Studi Kasus (Cont.) •
Menghitung Centroid Setiap Cluster : Data 1 2 3 4 5 6 7 8 9 10
•
Fx 1 4 6 1 2 5 2 3 2 3 Total
Fy 1 1 1 2 3 3 5 5 6 8
K1 *
K2
K3
K1Fx 1
K1Fy 1
* * 1
*
K2Fx
K2Fy
4 6
1 1
5
*
3
*
2
3
2
5
2
6
6
14
5
*
3
2 3
*
2
K3Fy
2
*
* 5
K3Fx
3
3 21
8 18
Hasil Centroid Setiap Cluster : Kelompok
Centroid Fitur x
Centroid Fitur y
1
Total K1Fx / Total K1 = 2 / 2 = 1
Total K1Fy / Total K1 = 3 / 2 = 1.5
2
Total K2Fx / Total K2 = 21 / 5 = 4.2
Total K2Fy / Total K2 = 18 / 5 = 3.6
3
Total K3Fx / Total K3 = 6 / 3 = 2
Total K3Fy / Total K3 = 14 / 3 = 4.6667
Contoh Studi Kasus (Cont.) •
Menghitung Jarak Data Ke Centroid (Euclidian Distance) : Dx 1,1, C1 1,1.5
1 12 1 1.52
Dx 1,1, C2 4.2,3.6 Dx 1,1, C3 2,4.6667
Data 1 2 3 4 5 6 7 8 9 10
Fx 1 4 6 1 2 5 2 3 2 3 Total
02 0.52
1 4.22 1 3.62
1 22 1 4.66672
0.25 0.5
3.22 2.62
10.24 6.76 17 4.1231
12 3.66672
Fy
Jarak Ke C 1
Jarak Ke C 2
Jarak Ke C 3
1 1 1 2 3 3 5 5 6 8
0.5000 3.0414 5.0249 0.5000 1.8028 4.2720 3.6401 4.0311 4.6098 6.8007 1.0000
4.1231 2.6077 3.1623 3.5777 2.2804 1.0000 2.6077 1.8439 3.2558 4.5607 13.1746
3.8006 4.1767 5.4263 2.8480 1.6667 3.4319 0.3333 1.0541 1.3333 3.4801 3.3333
3.8006
Kelompok Kelompok Baru Sebelumnya 0.5000 1 1 2.6077 2 2 3.1623 2 2 0.5000 1 1 1.6667 3 3 1.0000 2 2 0.3333 3 3 1.0541 3 2 1.3333 3 3 3.4801 3 2 (Total berdasarkan kelompok sebelumnya) Min
Sehingga, F baru = 1.0000 + 13.1746 + 3.3333 = 17.5079 Delta = | F baru – F lama | = | 17.5079 – 0 | = 17.5079 ( > T) , Lanjutkan !
Contoh Studi Kasus (Cont.) •
Iterasi 1 : (Mengalokasikan Setiap Data Pada Centroid Terdekat) Data 1 2 3 4 5 6 7 8 9 10
Fx 1 4 6 1 2 5 2 3 2 3 Total
Fy 1 1 1 2 3 3 5 5 6 8
K1 *
K2
K3
* * * * *
2
3
* * * * 5
Jarak Ke C 1 0.5000 3.0414 5.0249 0.5000 1.8028 4.2720 3.6401 4.0311 4.6098 6.8007 1.0000
Jarak Ke C 2 4.1231 2.6077 3.1623 3.5777 2.2804 1.0000 2.6077 1.8439 3.2558 4.5607 13.1746
Jarak Ke C 3 3.8006 4.1767 5.4263 2.8480 1.6667 3.4319 0.3333 1.0541 1.3333 3.4801 3.3333
Min 0.5000 2.6077 3.1623 0.5000 1.6667 1.0000 0.3333 1.0541 1.3333 3.4801
Kelompok Baru 1 2 2 1 3 2 3 3 3 3
Contoh Studi Kasus (Cont.) •
Menghitung Centroid Setiap Cluster : Data 1 2 3 4 5 6 7 8 9 10
•
Fx 1 4 6 1 2 5 2 3 2 3 Total
Fy 1 1 1 2 3 3 5 5 6 8
K1 *
K2
K3
K1Fx 1
K1Fy 1
* * 1
*
K2Fx
K2Fy
4 6
1 1
5
*
2
3
2
K3Fy
2
3
2 3 2 3 12
5 5 6 8
2
* * * * * 5
K3Fx
3
15
3
5
Hasil Centroid Setiap Cluster : Kelompok
Centroid Fitur x
Centroid Fitur y
1
Total K1Fx / Total K1 = 2 / 2 = 1
Total K1Fy / Total K1 = 3 / 2 = 1.5
2
Total K2Fx / Total K2 = 15 / 3 = 5
Total K2Fy / Total K2 = 5 / 3 = 1.6667
3
Total K3Fx / Total K3 = 12 / 5 = 2.4
Total K3Fy / Total K3 = 27 / 5 = 5.4
27
Contoh Studi Kasus (Cont.) •
•
Hasil Centroid Setiap Cluster : Kelompok
Centroid Fitur x
Centroid Fitur y
1
Total K1Fx / Total K1 = 2 / 2 = 1
Total K1Fy / Total K1 = 3 / 2 = 1.5
2
Total K2Fx / Total K2 = 15 / 3 = 5
Total K2Fy / Total K2 = 5 / 3 = 1.6667
3
Total K3Fx / Total K3 = 12 / 5 = 2.4
Total K3Fy / Total K3 = 27 / 5 = 5.4
Menghitung Jarak Data Ke Centroid : Data 1 2 3 4 5 6 7 8 9 10
Fx 1 4 6 1 2 5 2 3 2 3 Total
Fy
Jarak Ke C 1
Jarak Ke C 2
Jarak Ke C 3
1 1 1 2 3 3 5 5 6 8
0.5000 3.0414 5.0249 0.5000 1.8028 4.2720 3.6401 4.0311 4.6098 6.8007 1.0000
4.0552 1.2019 1.2019 4.0139 3.2830 1.3333 4.4845 3.8873 5.2705 6.6416 3.7370
4.6174 4.6819 5.6851 3.6770 2.4331 3.5384 0.5657 0.7211 0.7211 2.6683 7.1093
Kelompok Kelompok Baru Sebelumnya 0.5000 1 1 1.2019 2 2 1.2019 2 2 0.5000 1 1 1.8028 1 3 1.3333 2 2 0.5657 3 3 0.7211 3 3 0.7211 3 3 2.6683 3 3 (Total berdasarkan kelompok sebelumnya) Min
Sehingga, F baru = 1.0000 + 3.7370 + 7.1093 = 11.8464 Delta = | F baru – F lama | = | 11.8464 – 17.5079 | = 5.6615 ( > T) , Lanjutkan !
Contoh Studi Kasus (Cont.) •
Iterasi 2 : (Mengalokasikan Setiap Data Pada Centroid Terdekat) Data 1 2 3 4 5 6 7 8 9 10
Fx 1 4 6 1 2 5 2 3 2 3 Total
Fy 1 1 1 2 3 3 5 5 6 8
K1 *
K2
K3
* * * * *
2
3
* * * * 5
Jarak Ke C 1 0.5000 3.0414 5.0249 0.5000 1.8028 4.2720 3.6401 4.0311 4.6098 6.8007 1.0000
Jarak Ke C 2 4.0552 1.2019 1.2019 4.0139 3.2830 1.3333 4.4845 3.8873 5.2705 6.6416 3.7370
Jarak Ke C 3 4.6174 4.6819 5.6851 3.6770 2.4331 3.5384 0.5657 0.7211 0.7211 2.6683 7.1093
Min 0.5000 1.2019 1.2019 0.5000 1.8028 1.3333 0.5657 0.7211 0.7211 2.6683
Kelompok Baru 1 2 2 1 1 2 3 3 3 3
Contoh Studi Kasus (Cont.) •
Menghitung Centroid Setiap Cluster : Data 1 2 3 4 5 6 7 8 9 10
•
Fx 1 4 6 1 2 5 2 3 2 3 Total
Fy 1 1 1 2 3 3 5 5 6 8
K1 *
K2
K3
K1Fx 1
K1Fy 1
* * * *
1 2
3
3
4
K2Fy
4 6
1 1
5
3
K3Fx
K3Fy
2 3 2 3 10
5 5 6 8
2 3
* * * * * 4
K2Fx
6
15
5
Hasil Centroid Setiap Cluster : Kelompok
Centroid Fitur x
Centroid Fitur y
1
Total K1Fx / Total K1 = 4 / 3 = 1.3333
Total K1Fy / Total K1 = 6 / 3 = 2
2
Total K2Fx / Total K2 = 15 / 3 = 5
Total K2Fy / Total K2 = 5 / 3 = 1.6667
3
Total K3Fx / Total K3 = 10 / 4 = 2.5
Total K3Fy / Total K3 = 24 / 4 = 6
24
Contoh Studi Kasus (Cont.) •
•
Hasil Centroid Setiap Cluster : Kelompok
Centroid Fitur x
Centroid Fitur y
1
Total K1Fx / Total K1 = 4 / 3 = 1.3333
Total K1Fy / Total K1 = 6 / 3 = 2
2
Total K2Fx / Total K2 = 15 / 3 = 5
Total K2Fy / Total K2 = 5 / 3 = 1.6667
3
Total K3Fx / Total K3 = 10 / 4 = 2.5
Total K3Fy / Total K3 = 24 / 4 = 6
Menghitung Jarak Data Ke Centroid : Data 1 2 3 4 5 6 7 8 9 10
Fx 1 4 6 1 2 5 2 3 2 3 Total
Fy
Jarak Ke C 1
Jarak Ke C 2
Jarak Ke C 3
1 1 1 2 3 3 5 5 6 8
1.0541 2.8480 4.7726 0.3333 1.2019 3.8006 3.0732 3.4319 4.0552 6.2272 2.5893
4.0552 1.2019 1.2019 4.0139 3.2830 1.3333 4.4845 3.8873 5.2705 6.6416 3.7370
5.2202 5.2202 6.1033 4.2720 3.0414 3.9051 1.1180 1.1180 0.5000 2.0616 4.7976
Kelompok Kelompok Baru Sebelumnya 1.0541 1 1 1.2019 2 2 1.2019 2 2 0.3333 1 1 1.2019 1 1 1.3333 2 2 1.1180 3 3 1.1180 3 3 0.5000 3 3 2.0616 3 3 (Total berdasarkan kelompok sebelumnya) Min
Sehingga, F baru = 2.5893 + 3.7370 + 4.7976 = 11.1239 Delta = | F baru – F lama | = | 11.1239 – 11.8464 | = 0.7224 ( < T) , Stop Iterasi !
Contoh Studi Kasus (Cont.) •
Hasil Akhir Clustering Data : Data 1 2 3 4 5 6 7 8 9 10
•
Fx 1 4 6 1 2 5 2 3 2 3
Fy 1 1 1 2 3 3 5 5 6 8
Kelompok Baru 1 2 2 1 1 2 3 3 3 3
Visualisasi Hasil Akhir Clustering :
Selesai
