Clustering Kmeans
Review : Definisi Clustering • Metode untuk menemukan kelompok pada data berdasarkan kriteria tertentu.
K‐Means • K‐Means clustering adalah metode untuk mengelompokkan item ke dalam k kelomopk (dimana k adalah jumlah kelompok yang diinginkan). • Kelompok/cluster dibentuk dengan meminimalkan jumlah dari Euclidean distances) diantara data dengan titik pusat (centroid) yang berkorespondensi. • Centroid adalah titik pusat data, dalam hal ini kita mengasumsikan rata‐rata vector sebagai centroid.
Ilustrasi K‐Means
• Titik hitam menyatakan data. Garis merah menyatakan partisi/pemisah. Titik biru merepresentasikan titik pusat (centroid) yang mendefinisikan suatu partisi
Inisialisasi titik pusat (centroid) • Inisialisasi centroid dapat dilakukan dengan beberapa cara, contohnya 3 cara berikut: – Dipilih secara dinamik: Metode ini tepat digunakan jika data baru ditambahkan secara cepat dan banyak. Untuk menyederhanakan persoalan, inisial cluster dipilih dari beberapa data baru, misal jika data dikelompokkan menjadi 3 clusters, maka inisial cluster berarti 3 item pertama dari data. – Dipilih secara random: Paling banyak digunakan, dimana inisial cluster dipilih secara random dengan range data antara nilai terendah sampai nilai tertinggi.. – Memilih dari batasan nilai tinggi dan rendah: tergantung pada tipe datanya, nilai data tertinggi dan terendah dipilih sebagai inisial cluster. Contoh berikut menggunakan metode ini.
Kelemahan K‐Means • Jumlah cluster (k) harus ditentukan terlebih dahulu. • Jika sampel data terlalu sedikit, hasilnya menjadi tidak akurat. • Kita tidak pernah tahu independent variable yang berkontribusi lebih terhadap proses clustering karena setiap variable diasumsikan memiliki bobot yang sama. • Jika terdapat outlier, maka hasilnya akan berpengaruh secara signifikan sehingga tidak lagi akurat. • Solusi yang bisa dilakukan: • Melibatkan data sebanyak mungkin (semakin banyak data, maka hasilnya akan semakin akurat) • Untuk menghindari distorsi yang disebabkan oleh outlier, maka digunakan nilai median, bukan nilai rata‐rata
Contoh K‐Means, step by step • Berikut ini akan diilustrasikan metode K‐ means untuk mengelompokkan data berikut:
Inisialisasi centroid • Data ini dikelompokkan ke dalam dua cluster. Misal A & B adalah data yang memiliki jarak yang paling jauh (euclidean distance), maka kita dapatkan data 1 dan data 4 sebagai inisialisasi centroid:
Menghitung jarak dari data yang lain ke centroid • Data yang lain dihitung jaraknya ke dua centroid tadi. 1 2 3 4 5 6 7
A 1.0 1.5 3.0 5.0 3.5 4.5 3.5
B 1.0 2.0 4.0 7.0 5.0 5.0 4.5
centroid1 centroid2
1.0 5.0
1.0 7.0
Subject
iterasi1 Cluster1 0 1.118034 3.605551 7.211103 4.716991 5.315073 4.301163
Cluster2 7.211103 6.103278 3.605551 0 2.5 2.061553 2.915476
• Contoh perhitungan: • 1.118034=sqrt((1.5‐1.0)2+(2.0‐1.0)2)
Membandingkan jarak ke centroid dari tiap cluster • Dibandingkan jarak ke centroid dari tiap cluster, dicari yang terpendek untuk menjadi anggota dari cluster tersebut. 1 2 3 4 5 6 7
A 1.0 1.5 3.0 5.0 3.5 4.5 3.5
B 1.0 2.0 4.0 7.0 5.0 5.0 4.5
centroid1 centroid2
1.0 5.0
1.0 7.0
Subject
iterasi1 Cluster1 0 1.118034 3.605551 7.211103 4.716991 5.315073 4.301163
Cluster2 7.211103 6.103278 3.605551 0 2.5 2.061553 2.915476
• Contoh: perhatikan data‐2 (1.5,2.0), karena 1.118034 (jarak dengan cluster1) < 6.103278 (jarak dengan cluster 2) maka data‐2 termasuk dalam cluster1.
Mencari titik centroid yang baru • Untuk mencari titik centroid yang baru, kita perhatikan, keanggotaan dari tiap cluster. • Cluster1 terdiri dari data: ((1,1),(1.5,2),(3,4)) maka titik centroid dari cluster1 ini ada di : – X = (1+1.5+3)/3 =1.83333 – Y = (1+2+4)/3= 2.33333
• Sehingga kita dapatkan titik centroid yang baru sebagai berikut: centroid1 1.833333 2.333333 centroid2 4.125 5.375
Program MATLAB untuk clustering KMeans • Proses awal / Inisialisasi KMeans • • • • • • • • • • •
[ndata, text, alldata]=xlsread('datakmeans.xlsx'); % dapatkan ukuran data (data size) [xx yy]=size(ndata) % mengambil data mulai kolom ke 2 ndata=ndata(:,2:yy) %# tentukan inisialisasi centroid: cluster1 = data1 (1,1) % cluster2 =data4 (5,7) centroid(1,:)=ndata(1,:) centroid(2,:)=ndata(4,:)
Program MATLAB untuk clustering KMeans • Kita lakukan proses iterasi sampai kondisi penghentian terpenuhi • Kondisi penghentian berarti: antara centroid lama dengan centroid baru nilainya mendekati atau sama dengan nol. • Iterasi yang dipakai misal: • While (1) • if kondisi • break; • End;
Program MATLAB untuk clustering KMeans •
Proses yang dilakukan pada body of loop (setiap iterasi), meliputi: 1. Menghitung jarak semua data ke centroid yang ada 2. Kita bandingkan jarak antara centroid1 dengan centroid2 dan tempatkan data pada cluster yang memiliki jarak terdekat ke centroid ybs. 3. hitung centroid yang baru berdasarkan anggota yang ada di setiap cluster 4. periksa apakah sudah memenuhi kondisi penghentian. Jika terpenuhi, maka keluar dari looping, jika tidak maka kembali ke proses nomer 1.
Program MATLAB untuk clustering KMeans Menghitung jarak semua data ke centroid yang ada • for i=1:xx, • for j=1:2, • % jarak antara data ke ‐ i dengan centroid ke j • jumlah=0; • for z=1:yy‐1, • jumlah=jumlah+(ndata(i,z)‐centroid(j,z))^2; • end; • jarak(i,j)=sqrt(jumlah); • end; • end; • jarak
Program MATLAB untuk clustering KMeans Kita bandingkan jarak antara centroid1 dengan centroid2 dan tempatkan data pada cluster yang memiliki jarak terdekat ke centroid ybs. –for i=1:xx, – if (jarak(i,1)<=jarak(i,2)) – cluster(i,1)=1; – else – cluster(i,1)=2; – end; – end; – cluster –
Program MATLAB untuk clustering KMeans • hitung centroid yang baru berdasarkan anggota yang ada di setiap cluster – – – – – – – – – – – – – – – – – – – – – – – –
% hitung centroid yang baru berdasarkan anggota yang ada di setiap cluster centroid_baru=zeros(2,2); n1=0; n2=0; for i=1:xx, if (cluster(i,1)==1) for j=1:yy‐1, centroid_baru(1,j)=centroid_baru(1,j)+ndata(i,j); end; n1=n1+1; else for j=1:yy‐1, centroid_baru(2,j)=centroid_baru(2,j)+ndata(i,j); end; n2=n2+1; end; end; for i=1:yy‐1, centroid_baru(1,i)=centroid_baru(1,i)/n1; centroid_baru(2,i)=centroid_baru(2,i)/n2; end; % menampilkan centroid yang baru
Program MATLAB untuk clustering KMeans • • • • • • • • • • • • • • • • • • •
periksa apakah sudah memenuhi kondisi penghentian. Jika terpenuhi, maka keluar dari looping, jika tidak maka kembali ke proses nomer 1. % periksa apakah sudah memenuhi kondisi penghentian selisih1=0; selisih2=0; for i=1:yy‐1, selisih1=selisih1+(centroid(1,i)‐centroid_baru(1,i))*(centroid(1,i)‐centroid_baru(1,i)); selisih2=selisih2+(centroid(2,i)‐centroid_baru(2,i))*(centroid(2,i)‐centroid_baru(2,i)); end; selisih1=sqrt(selisih1); selisih2=sqrt(selisih2); if (selisih1<0.000000001 && selisih2<0.000000001) break; else % jika tidak, update nilai centroid for i=1:yy‐1, centroid(1,i)=centroid_baru(1,i); centroid(2,i)=centroid_baru(2,i); end; end;
