Clustering
Dr. techn. Annisa Maulida Ningtyas, [Link].
Clustering
Data
Mining/Machine
learning
Reinforcement
Supervised Unsupervised
Learning
Clustering
Classification vs Clustering
Classification vs Clustering
Classification vs Clustering
Clustering
Teknik clustering melakukan pembelajaran mesin tanpa ada supervisi untuk
menyelesaikan suatu masalah
Clustering juga dapat dianalogikan sebagai tugas mengidentifikasi subkelompok dalam
data sedemikian rupa sehingga titik data dalam subkelompok yang sama (cluster)
sangat mirip sedangkan titik data dalam cluster yang berbeda sangat berbeda
Keputusan tentang ukuran kemiripan dapat ditentukan melalui
jumlah centroid masing-masing kelompok dan jaraknya.
Clustering
Clustering
Partition based Hierarchical Density based
clustering clustering clustering
K-Means Agglomerative DBSCAN
Fuzzy C-Means Divisive
Dsb…
K-Means
Algoritma Kmeans adalah salah satu algoritma clustering yang bersifat iteratif yang mencoba untuk
mempartisi dataset menjadi subkelompok non-overlapping berbeda yang ditentukan oleh K
(cluster) di mana setiap titik data hanya dimiliki oleh satu kelompok.
K-Means mencoba membuat titik data intra-cluster semirip mungkin sambil dengan titik data
yang lain pada satu cluster.
K-Means menetapkan poin data ke cluster sedemikian rupa sehingga jumlah jarak kuadrat antara
titik data dan pusat massa cluster (rata-rata aritmatika dari semua titik data yang termasuk dalam
cluster itu) minimal.
Semakin sedikit variasi yang kita miliki dalam cluster, semakin homogen (serupa) titik data dalam
cluster yang sama.
Langkah-langkah metode K-
Means
1. Memilih jumlah cluster awal (K) yang ingin dibuat
• Sebagai contoh terdapat data 2 dimensi seperti yang ditampilkan dalam grafik,
langkah pertama adalah memilih jumlah kluster. Misal kita pilih untuk membaginya ke
dalam 2 kluster.
0
0 2 4 6 8
Langkah-langkah metode K-
Means
• 2. Memilih titik secara random sebanyak K buah, di mana titik ini akan menjadi
pusat (centroid) dari masing-masing kelompok (clusters)
• Pada Gambar 2, titik merah mewakili pusat dari kluster 1, dan hijau untuk kluster 2. Dengan
demikian, maka masing-masing data point akan memilih titik pusat (centroid) yang paling
dekat. Jika sudah dipilih maka data point tersebut akan menjadi bagian dari klusternya.
0
0 2 4 6 8
Langkah-langkah metode K-
Means
• 3. Dari dataset yang kita miliki, buat dataset yang terdekat dengan
titik centroid sebagai bagian dari cluster tersebut. Sehingga secara total akan
terbentuk clusters sebanyak K buah.
7
A
6
4 B
3
0
0 2 4 6 8
Langkah-langkah metode K-
Means
4. Lakukan kalkulasi, dan tempatkan pusat centroid yang baru untuk setiap cluster-nya.
Langkah ini dilakukan untuk menemukan centroid yang paling tepat untuk masing-
masing klaster.
7
A
6
4 B
3
0
0 2 4 6 8
Langkah-langkah metode K-
Means
• 5. Dari dataset yang kita miliki ambil titik centroid terdekat, sehingga dataset tadi
menjadi bagian dari cluster tersebut. Jika masih ada data yang berubah kelompok
(pindah cluster), kembali ke langkah 4. Jika tidak, maka cluster yang terbentuk sudah
baik.
Visualisasi K-means
[Link]
Optimasi K-means
Dari pembahasan di atas, dapat dianalisa bahwa salah satu faktor krusial baik tidaknya
metode ini adalah saat menentukan jumlah klusternya (nilai K). Karena hasil
pengelompokan akan menghasilkan analisa yang berbeda untuk jumlah klaster yang
berbeda juga.
Jika terlalu sedikit K (misal 2), maka pembagian kluster menjadi cepat, namun mungkin
ada informasi tersembunyi yang tidak terungkap.
Jika K=8, maka terlalu banyak kluster. Mungkin akan terlalu sulit untuk membuat analisa
atau memilih dukungan keputusan dari hasil cluster.
Optimasi K-means
• Untuk mengatasi ini, maka dapat ditambahkan fungsi optimasi yang akan
memilih jumlah awal kluster secara tepat. kita gunakan di sesi latihan dan
sebuah metode elbow yang akan membantu kita untuk memilih nilai K yang
tepat dengan menggunakan metricWCSS (Within Cluster Sum of Squares),
contoh penghitungan untuk tiga klaster:
Grafik perhitungan WCSS untuk sebuah contoh dataset. Semakin kecil skor WCSS, semakin baik.
Sumbu x adalah jumlah kluster, sumbu y adalah skor WCSS. Bisa dilihat bahwa saat K=1, nilai WCSS
sangat tinggi. Kemudian menurun terus sampai K=5 terlihat membentuk seperti sebuah siku. Mulai K=6
sampai K=10 penurunan skor WCSS sudah tidak signifikan. Dengan demikian, dapat diketahui bahwa
jumlah kluster yang tepat untuk grafik di atas adalah 5. Contoh hasil perhitungan WCSS dapat
dilihat pada grafik berikut:
Studi Kasus K-Means
Hasil pengelompokan data menggunakan metode K-Means yang dioptimasi
dengan metrics WCSS:
Pada dua gambar di atas dapat diamati hasil pengelompokan data set yang
terbagi dalam 3 dan 5 klaster. Hasil dari pengelompokan tersebut dapat
digunakan sebagai dukungan keputusan untuk menentukan strategi yang
dituju oleh pemilik toko terhadap pelanggannya
Hierarchical Clustering
Pengelompokan hierarki adalah Teknik clustering dengan memisahkan data ke dalam kelompok
berdasarkan beberapa ukuran kesamaan, menemukan cara untuk mengukur bagaimana mereka
sama dan berbeda, dan selanjutnya mempersempit data.
This Photo by Unknown Author is licensed under CC BY-SA
Types of Hierachical Clustering
Metode hierarchical clustering dibagi menjadi dua yaitu:
1. Divisive
Pengelompokan divisif dikenal sebagai pendekatan top-down, yaitu mengambil cluster besar dan
mulai membaginya menjadi dua, tiga, empat, atau lebih cluster.
2. Aglomerative
Pengelompokan aglomeratif dikenal sebagai pendekatan bottom-up, yaitu
pengelompokan dimulai dari cluster kecil menuju satu cluster besar.
Aglomerative Divisive
Hierachical Clustering
• Langkah-langkah metode hierarchical clustering dengan agglomerative:
1. Buat setiap data poin dalam dataset menjadi sebuah cluster, sehingga untuk
N data kita memiliki N cluster. Misalnya jika jumlah row data adalah 500
maka akan terdapat 500 cluster.
2. Cari dua poin/2 cluster yang saling berdekatan untuk digabung menjadi
satu cluster sehingga jumlah cluster menjadi lebih kecil.
3. Cari 2 cluster lagi yang berdekatan dengan yang lain (termasuk dengan
kluster yang baru saja dibuat di langkah 2 jika memang cluster tersebut
memiliki jarak terdekat dengan kluster lain), dan jadikan dua cluster
terdekat ini menjadi 1 kluster. Dengan demikian, sekarang kita memiliki N-2
kluster.
4. Langkah ketiga akan diulang terus hingga mendapatkan satu buah cluster
besar.
• #Jadijagoandigi
tal
Hierachical Clustering
4.5
X3
4 X2
Ilustrasi dari langkah-langkah
3.5 X1
aglomerative: X4
3 X5
Misalnya terdapat enam data poin.
Pada langkah pertama sudah jelas 2.5 X6
bawah N data= N cluster. Kita akan 2
1.5 2.5 3.5 4.5
mendefinisikan jarak antara 2
kluster sebagai jarak Euclidean 4.5
X3
terdekatnya. Ilustrasinya sebagai 4 X2
berikut: 3.5 X1
X4
3 X5
2.5 X6
2
1.5 2.5 3.5 4.5
Hierachical Clustering
4.5
X3
4 X2
3.5 X1
Proses menggabungkan dua cluster menjadi X4
3 X5
dapat masih dilanjutkan jika masih terdapat
titik yang terdekat lagi yang memungkinkan 2.5 X6
untuk digabungkan 2
1.5 2.5 3.5 4.5
4.5
X3
4 X2
3.5 X1
X4
3 X5
2.5 X6
2
1.5 2.5 3.5 4.5
• #Jadijagoandigi
tal
Hierachical Clustering
4.5
X3
4 X2
3.5 X1
Selanjutnya, seperti langkah sebelumnya, X4
3 X5
kita cari dua cluster terdekat lagi untuk
digabungkan. Cluster yang digabungkan 2.5 X6
boleh cluster yang berupa satu titik pada 2
langkah pertama atau cluster yang 1.5 2.5 3.5 4.5
merupakan gabungan dari dua titik/cluster.
4.5
X3
4 X2
3.5 X1
X4
3 X5
2.5 X6
2
1.5 2.5 3.5 4.5
• #Jadijagoandigi
tal
Hierachical Clustering
4.5
X3
4 X2
3.5 X1
X4
3 X5
2.5 X6
Menggabungkan lagi dua cluster
2
yang terdekat menjadi satu cluster. 1.5 2.5 3.5 4.5
Jumlah titik dalam cluster tidak
harus ditentukan sama, dapat saja 4.5
X3
cluster yang satu jumlah titiknya 4 X2
lebih banyak dibandingkan cluster
3.5 X1
yang lain. X4
3 X5
2.5 X6
2
1.5 2.5 3.5 4.5
• #Jadijagoandigi
tal
Hierachical Clustering
4.5
X3
4 X2
3.5 X1
X4
3 X5
2.5 X6
Proses akan berakhir Ketika semua 2
1.5 2.5 3.5 4.5
cluster telah tergabung menjadi
satu cluster besar.
4.5
X3
4 X2
3.5 X1
X4
3 X5
2.5 X6
2
1.5 2.5 3.5 4.5
• #Jadijagoandigi
tal
Optimasi Hierachical Clustering
Pada clustering K-Means yang kita pelajari sebelumnya, untuk mengetahui jumlah cluster
yang tepat kita dapat menggunakan metode Elbow, pada hierarchical clustering kita dapat
menggunakan Dendogram.
Dendrogram adalah sebuah grafik (diagram) yang menunjukkan proses penggabungan
kluster. Di sumbu x dari sebuah dendrogram kita memiliki data kluster, sementara di
sumbu y adalah jarak euclideannya.
Optimasi Hierachical Clustering
4.5
X3
4 X2
3.5 X1
X4
3 X5
2.5 X6
Ilustrasi dari penentuan dendogram adalah
2
sebagai berikut: 1.5 2.5 3.5 4.5
1. Sama seperti pada contoh hierarchical
clustering sebelumnya, terdapat enam titik 3
dalam satu diagram. Grafik yang atas adalah 2.5
grafik awal dan yang bawah adalah grafik
2
dendogram.
1.5
0.5
0
0 1 2 3 4 5 6
• #Jadijagoandigi
tal
Optimasi Hierachical Clustering
4.5
X3
4 X2
3.5 X1
X4
3 X5
2. Sama seperti ilustrasi pada hierarchical 2.5 X6
clustering, langkah pertama adalah
menentukan dua titik terdekat kemudian 2
1.5 2.5 3.5 4.5
menerjemahkannya ke dalam diagram
dendogram 3
2.5
1.5
0.5
0
0 1 2 3 4 5 6
• #Jadijagoandigi
tal
Optimasi Hierachical Clustering
4.5
X3
4 X2
3.5 X1
X4
3 X5
3. Mencari lagi dua cluster yang berdekatan
untuk digabungkan menjadi satu cluster lagi. 2.5 X6
Tinggi diagram Dendogram berbeda-beda 2
sesuai dengan hasil penghitungan Euclidean 1.5 2.5 3.5 4.5
Distancenya.
3
2.5
2
1.5
1
0.5
0
0 1 2 3 4 5 6
• #Jadijagoandigi
tal
Optimasi Hierachical Clustering
4.5
X3
4 X2
3.5 X1
X4
3 X5
4. Proses yang ketiga diulang lagi dengan
2.5 X6
mencari dua cluster yang terdekat. Jika dua
cluster yang digabungkan sebelumnya adalah 2
cluster antara dua titik maka cara 1.5 2.5 3.5 4.5
menerjemahkan dalam dendogram dapat
diamati pada gambar disamping,
3
2.5
2
1.5
1
0.5
0
0 1 2 3 4 5 6
• #Jadijagoandigi
tal
Optimasi Hierachical Clustering
4.5
X3
4 X2
3.5 X1
X4
3 X5
5. Mengulang proses dengan menggabungkan
cluster yang sudah ada, Pada gambar 2.5 X6
disamping tampak bahwa dua cluster terakhir 2
merupakan gabungan dari cluster (dua titik 1.5 2.5 3.5 4.5
yang menjadi satu cluster) pada proses awal.
3
2.5
2
1.5
1
0.5
0
0 1 2 3 4 5 6
• #Jadijagoandigi
tal
Optimasi Hierachical Clustering
4.5
X3
4 X2
3.5 X1
X4
3 X5
6. Proses akan berhenti setelah semua cluster
telah tergabung menjadi satu cluster besar 2.5 X6
seperti pada gambar di samping:
2
1.5 2.5 3.5 4.5
3
2.5
2
1.5
1
0.5
0
0 1 2 3 4 5 6
• #Jadijagoandigi
tal
Optimasi Hierachical Clustering
7. Untuk menentukan berapa jumlah cluster 3
yang paling sesuai pada dats set yang diujikan 2.5
dapat dianalisa melalui dendogram. Yaitu 2
dengan menentukan garis grafik dendogram 1.5 threshold
yang paling panjang yang tidak terkena 1
potongan atau bisa juga dengan menentukan 0.5
0
nilai threshold, seperti pada gambar di 0 1 2 3 4 5 6
samping:
• #Jadijagoandigi
tal