K-Means adalah suatu metode penganalisaan data atau metode Data Mining yang melakukan proses pemodelan tanpa supervisi (unsupervised) dan merupakan salah satu metode yang melakukan pengelompokan data dengan sistem partisi. Metode k-means berusaha mengelompokkan data yang ada ke dalam beberapa kelompok, dimana data dalam satu kelompok mempunyai karakteristik yang sama satu sama lainnya dan mempunyai karakteristik yang berbeda dengan data yang ada di dalam kelompok yang lain. Dengan kata lain, metode ini berusaha untuk meminimalkan variasi antar data yang ada di dalam suatu cluster dan memaksimalkan variasi dengan data yang ada di cluster lainnya.
Objective function yang berusaha diminimalkan oleh k-means adalah:
J (U, V) = SUM (k=1 to N) SUM (i=1 to c) (a_ik * (x_k, v_i)^2)
dimana:
U : Matriks keanggotaan data ke masing-masing cluster yang berisikan nilai 0 dan 1
V : Matriks centroid/rata-rata masing-masing cluster
N : Jumlah data
c : Jumlah cluster
a_ik : Keanggotaan data ke-k ke cluster ke-i
x_k : data ke-k
v_i : Nilai centroid cluster ke-i
Prosedur yang digunakan dalam melakukan optimasi menggunakan k-means adalah sebagai berikut:
Step 1. Tentukan jumlah cluster
Step 2. Alokasikan data ke dalam cluster secara random
Step 3. Hitung centroid/rata-rata dari data yang ada di masing-masing cluster.
Step 4. Alokasikan masing-masing data ke centroid/rata-rata terdekat
Step 5. Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau apabila perubahan nilai centroid, ada yang di atas nilai threshold yang ditentukan atau apabila perubahan nilai pada objective function yang digunakan, di atas nilai threshold yang ditentukan
Centroid/rata-rata dari data yang ada di masing-masing cluster yang dihitung pada Step 3. didapatkan menggunakan rumus sebagai berikut:
v_ij = SUM (k=0 to N_i) (x_kj) / N_i
dimana:
i,k : indeks dari cluster
j : indeks dari variabel
v_ij : centroid/rata-rata cluster ke-i untuk variabel ke-j
x_kj : nilai data ke-k yang ada di dalam cluster tersebut untuk variabel ke-j
N_i : Jumlah data yang menjadi anggota cluster ke-i
Sedangkan pengalokasian data ke masing-masing cluster yang dilakukan pada Step 4. dilakukan secara penuh, dimana nilai yang memungkinkan untuk a_ik adalah 0 atau 1. Nilai 1 untuk data yang dialokasikan ke cluster dan nilai 0 untuk data yang dialokasikan ke cluster yang lain. Dalam menentukan apakah suatu data teralokasikan ke suatu cluster atau tidak, dapat dilakukan dengan menghitung jarak data tersebut ke masing-masing centroid/rata-rata masing-masing cluster. Dalam hal ini, a_ik akan bernilai 1 untuk cluster yang centroidnya terdekat dengan data tersebut, dan bernilai 0 untuk yang lainnya.
Referensi:
J. B. MacQueen (1967): “Some Methods for classification and Analysis of Multivariate Observations, Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability”, Berkeley, University of California Press, 1:281-297
J. A. Hartigan (1975) “Clustering Algorithms”. Wiley.
J. A. Hartigan and M. A. Wong (1979). “A K-Means Clustering Algorithm”. Applied Statistics 28 (1): 100–108.
Cluster Validity Criterion
Untuk menentukan jumlah cluster yang paling tepat, saat menggunakan metode k-means dapat dilakukan dengan beberapa cara. Salah satunya adalah dengan cara manual yang saya jelaskan dalam posting saya tentang Akurasi Hasil Pemodelan K-Means yang sering juga direfer sebagai Bootstrapped Method. Selain itu ada beberapa cara yang lain yang juga bisa digunakan seperti di bawah ini.
Elbow Criterion (RMSSDT dan RS)
Elbow criterion adalah salah satu cara untuk menentukan jumlah cluster yang paling tepat untuk pemodelan k-means. Elbow criterion untuk k-means ini mengkombinasikan antara nilai RMSSTD dan RS statistics, dimana cluster yang paling tepat untuk suatu dataset ditentukan apabila perbedaan nilai antara RMSSTD dan RS menjadi berbanding terbalik dengan keadaan sebelumnya.
RMSSTD (Root Means Square Standard Deviation) merupakan alat ukur tingkat kemiripan (homogeneity) data yang terdapat di dalam cluster yang ditemukan (within clusters). Makin rendah nilai RMSSTD makin mirip data di dalam cluster yang ditemukan. RMSSDT dihitung menggunakan rumus sebagai berikut:
RMSSTD = SQRT (SUM(i=1 to k) SUM(j=1 to d) (SUM(k=1 to N_i) ((x_kj – mu_j)^2)) /
SUM(i=1 to k) SUM(j=1 to d) (N_i – 1))
RS (R Squared) digunakan untuk mengukur tingkat kesamaan atau ketidaksamaan antara cluster (between clusters). RS mempunyai nilai antara 0 dan 1. Nilai 0 untuk cluster yang sama dan 1 untuk cluster yang benar-benar berbeda. RS dihitung dengan rumus:
RS = (SS_t – SS_w) / SS_t
SS_t = SUM(j=1 to d) (SUM(k=1 to N) ((x_kj – mu_j)^2) dan
SS_w = SUM(i=1 to k) SUM(j=1 to d) (SUM(k=1 to N_i) ((x_kj – mu_j)^2))
Notasi:
x_kj : data ke-k yang ada di dalam cluster untuk dimensi ke-j
mu_j : means/rata-rata nilai dari variabel dimensi ke-j
N_i : jumlah data di dalam cluster ke-i
N : jumlah data keseluruhan
d : jumlah dimensi dari data
k : jumlah cluster
Elbow criterion adalah suatu modelling criterion yang bisa digunakan untuk menentukan jumlah cluster dengan melihat perubahan perbandingan antara nilai RMSSTD dan RS. Hal ini dilihat dengan membandingkan persentase tingkat perubahan kedua nilai (RMSSTD dan RS). Apabila muncul suatu keadaan yang berbanding terbalik dengan keadaan sebelumnya, maka titik sebelum terjadinya perubahan tersebut dianggap sebagai jumlah cluster yang paling tepat.
Referensi:
Subhash Sharma: Applied Multivariate Techniques, John Wiley & Sons, Inc., 1996.
G-Means (Gaussian Means)
G-Means berusaha menentukan jumlah cluster secara gradual dengan melihat apakah suatu cluster sudah dalam keadaan terdistribusi secara normal atau tidak. Kalau masih dianggap belum normal, maka akan dilihat apakah cluster tersebut masih bisa displit untuk dijadikan dua cluster. Hipotesis yang digunakan adalah:
H0: Data di sekitar centroid disample dari suatu distribusi Gaussian.
H1: Data di sekitar centroid tidak disample dari suatu distribusi Gaussian.
Adapun algoritma yang digunakan untuk menentukan split atau tidak adalah sebagai berikut:
1. Tentukan confidence level Alpha untuk testing.
2. Tentukan dua centroid baru c1 dan c2.
3. Jalankan k-means terhadap dua centroid baru tersebut.
4. Tentukan vektor v yang menghubungkan antara centroid c1 dan c2 dimana v = c1 – c2. Kemudian proyeksikan data X ke v dengan rumus x’ = (x,v)/||v||^2. X’ merupakan representasi satu dimensi dari data yang diproyeksikan ke v. Hitung z = F(x’), dimana z adalah bentuk normalisasi x’.
5. Hitung nilai A_2*(Z) dengan rumus di bawah. Apabila A_2*(Z) berada di wilayah nilai non-critical pada confidence level Alpha, maka H0 diterima, dan centroid awal tetap digunakan dan centroid baru c1 dan c2 dihapus. Untuk keadaan sebaliknya, H0 harus ditolak dan centroid baru c1 dan c2 digunakan sebagai pengganti centroid awal.
A_2*(Z) = A_2(Z)(1+4/n-25/(n^2)) dan
A_2(Z) = -1/n * SUM (i=1 to n) ((2*i – 1)(log(z_i)+log(1-z_(n+1-i))) – n
dimana:
n : Jumlah data
Referensi:
G. Hamerly and C. Elkan (2003). Learning the k in k-means. In Proceedings of 17th Neural Information Processing Systems.
X-Means
Merupakan suatu pengembangan k-means untuk menentukan jumlah cluster yang paling tepat untuk suatu dataset yang dianalisa. Adapun algoritma yang diterapkan di dalam metote ini adalah dengan menggabungkan algoritma k-means murni dan salah satu modelling criterion seperti Bayesian Information Criterion (BIC) atau Akaike Information Criterion (AIC) – penjelasan tentang kedua criteria ini ada di My Mixture Modelling Page. Algoritma yang diterapkan adalah sebagai berikut:
Step 1: Tentukan jumlah cluster
Step 2: Lakukan optimasi dengan k-means murni
Step 3: Untuk setiap cluster yang dihasilkan split cluster menjadi dua dan bandingkan modelling score antara model dengan satu cluster dan model dengan dua cluster. Model dengan score yang lebih baik dipilih menjadi perwakilan model yang displit.
Referensi
Pelleg D. and Moore A. (2000). X-means: Extending K-means with Efficient Estimation of the Number of Clusters. In Proceedings of the Seventeenth International Conference on Machine Learning (ICML). 727-734.
K-Means Variances
Fuzzy c-Means
Variasi dalam hal penentuan nilai keanggotaan data ke masing-masing cluster.
Fuzzy c-Means merupakan perkembangan dari metode k-means dengan memperhitungkan bahwa data dapat tergabung ke dalam ke dalam beberapa cluster dengan tingkat keanggotaan yang berbeda-beda. Tetapi sum total dari nilai keanggotaan data tersebut harus sama dengan 1. Misalnya data x1 bisa tergabung dengan cluster I dengan tingkat keanggotaan 0,7, dengan cluster II dengan tingkat keanggotaan 0,2 dan dengan cluster III dengan tingkat keanggotaan 0,1. Hal ini berbeda dengan k-means karena metode tersebut mengharuskan suatu data untuk menjadi anggota atau tidak sekalian.
Algoritma yang digunakan dalam fuzzy c-means sama dengan algoritma yang digunakan dalam k-means. Tetapi objective function dan rumus yang digunakan untuk menghitung centroid/rata-rata berbeda. Di samping itu, dalam fuzzy c-means, tingkat keanggotaan, yang sering disebut dengan membership function, juga perlu di hitung. Objective function dan rumus-rumus yang digunakan adalah sebagai berikut:
Objective function:
J (U, V) = SUM (k=1 to N) SUM (i=1 to c) (u_ik^m * (x_k, v_i)^2)
dimana:
u_ik = membership function data ke i ke cluster ke k
m = weighting exponent
U, V, N, c, x_k dan v_i : sudah dijelaskan di objective function untuk k-means
Rumus menghitung rata-rata/centroid:
v_ij = SUM (k=1 to N_i) (u_ik^m * x_kj) / SUM (k=1 to N_i) (u_ik^m)
Rumus menghitung membership function:
u_ik = SUM (j=1 to c) ((x_k – v_i)/(x_k – v_j))^(2/(m-1))
Referensi:
Bezdek, J.C. (1981). Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press, New York.
K Harmonic Means
Variasi dalam hal objective function yang digunakan.
K Harmonic Means menggunakan suatu objective function untuk menghindarkan pengaruh yang besar dari data-data yang ada di sekitar cluster center. Untuk keperluan tersebut, di samping nilai keanggotaan dari data terhadap cluster, setiap data juga mempunyai nilai weight yang digunakan untuk meng-harmoni-kan pengaruh masing-masing data dalam pemodelan. Adapun objective function yang digunakan dalam metode ini adalah sebagai berikut:
J (V) = SUM (k=1 to N) (c / (SUM (i=1 to c) (1/ (x_k- v_i)^p)))
dimana:
V : Matriks centroid/rata-rata masing-masing cluster
N : Jumlah data
c : Jumlah cluster
v_i : Nilai centroid cluster ke-i
p : suatu input parameter yang besarnya lebih dari atau sama dengan 2
Nilai membership function u_ik dan weight w_k dihitung dengan rumus sebagai berikut:
u_ik = SUM (j=1 to c) ((x_k – v_i)/(x_k – v_j))^(-p-2)
w_k = SUM (j=1 to c) (x_k – v_j)^(-p-2) / (SUM (j=1 to c) (x_k – v_j)^(-p))^2
Referensi:
G. Hamerly and C. Elkan (2002). Altenatives to the k-means algorithm that find better clusterings. In Proceedings of the 11th International Conference on Information and Knowledge Management. pp. 600-607.
Kernel K-means
Variasi untuk sekumpulan data yang ‘dianggap’ terkelompok secara non-linear.
K-means yang standar umumnya digunakan untuk mengelompokkan data yang secara umum datanya dipisahkan secara linear. Kalau data ‘dianggap’ terkelompok secara non-linear, k-means perlu dimodifikasi untuk dapat mengakomodasi ke-non-linear-an tersebut. Adapun metode yang diimplementasikan di dalam menyelesaikan permasalahan ini adalah dengan mengadopsi Kernel Trick dalam proses pengelompokan yang dilakukan.
Perlu diketahui di sini, untuk bisa menerapkan Kernel Trick, data perlu untuk dipetakan terlebih dahulu ke bentuk data dengan dimensi yang lain, yang umumnya jumlah dimensinya lebih tinggi dengan fungsi THETA(x), yang artinya data x dipetakan dari dimensi awal ke dimensi yang lain (umumnya dimensi yang lebih tinggi).
Adapun objective function yang digunakan untuk Kernel K-Means adalah:
J (U, V) = SUM (k=1 to N) SUM (i=1 to c) (a_ik * (THETA(x_k), v_i)^2)
dimana:
U : Matriks keanggotaan data ke masing-masing cluster yang berisikan nilai 0 dan 1
V : Matriks centroid/rata-rata masing-masing cluster
N : Jumlah data
c : Jumlah cluster
a_ik : Keanggotaan data ke-k ke cluster ke-i
v_i : Nilai centroid cluster ke-i
Rumus menghitung rata-rata/centroid:
v_ij = SUM (k=0 to N_i) THETA (x_kj) / N_i
yang tentunya tidak bisa dihitung, karena kita tidak bisa mengetahui nilai THETA (x_kj) secara langsung. Hal ini bisa diakali, dengan langsung menentukan nilai a_ik (yang nilainya adalah 1 atau 0), dimana a_ik bernilai 1 untuk data yang mempunyai jarak terdekat dengan centroid dan 0 untuk yang lainnya. Adapun jarak antara data dengan centroid dihitung dengan rumus berikut ini:
(THETA(x_l),v_i)^2 = SUM (l=0 to N_i) THETA(x_lj)*THETA(x_lj) -
2*SUM (k,l=0 to N_i) THETA (x_lj)*THETA (x_kj)/ N_i +
SUM (k=0 to N_i) THETA (x_kj)*THETA (x_kj)/ N_i
Disini fungsi kernel disubstitusikan, sehingga jarak antara data dengan centroid dapat dihitung dengan rumus berikut ini:
(THETA(x_l),v_i)^2 = SUM (l=0 to N_i) K(x_lj,x_lj) -
2*SUM (k,l=0 to N_i) K (x_lj,x_kj)/ N_i + SUM (k=0 to N_i) K (x_kj,x_kj)/ N_i
Data di-assign ke dalam kelompok yang jarak antara centroid dan data tersebut diminimalkan. Prosedur yang digunakan tetap sama dengan prosedur yang diterapkan pada standar k-means.
Referensi
M Girolami (2002). Mercer kernel-based clustering in feature space. Neural Networks, IEEE Transactions on, Vol. 13, No. 3., pp. 780-784.
Inderjit S Dhillon, Yuqiang Guan, Brian Kulis (2004).Kernel k-means: spectral clustering and normalized cuts. pp. 551-556
K-Modes
Variasi dalam hal data yang dianalisa bukan continuous, tapi categorical.
Untuk data categorical, k-means tidak bisa digunakan karena data categorical tidak bisa dicari nilai means (rata-rata)-nya. Untuk keperluan tersebut K-Modes dapat digunakan sebagai gantinya. Adapun algoritma yang digunakan sama dengan k-means dengan beberapa modifikasi sebagai berikut:
Step 1. Tentukan jumlah cluster
Step 2. Alokasikan data ke dalam cluster secara random
Step 3. Hitung modes dari data yang ada di masing-masing cluster.
Step 4. Alokasikan masing-masing data ke cluster terdekat menggunakan Hemming Distance
Step 5. Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau apabila perubahan nilai modes atau apabila perubahan nilai pada objective function yang digunakan, di atas nilai threshold yang ditentukan
Objective function yang digunakan k-modes adalah:
J (A, M) = SUM (k=1 to N) SUM (i=1 to c) (a_ik * D(x_k, m_i))
dimana:
A : Matriks keanggotaan data ke masing-masing cluster yang berisikan nilai 0 dan 1
M : Matriks modes masing-masing cluster
N : Jumlah data
c : Jumlah cluster
a_ik : Keanggotaan data ke-k ke cluster ke-i
x_k : data ke-k
m_i : Nilai modes cluster ke-i
D(x_k, m_i) : Hemming Distance antara data x dan modes m
Referensi:
Chaturvedi, A.D., Green, P.E. and Carroll, J.D. (2001). K-Modes Clustering. Journal of Classification, 18, 35-56.
Sdr/i Yulie, untuk 26 Kabupaten dan 11 variabel yang dimiliki, bisa menggunakan baik K-Means dan FCM. Kedua metode hanya berbeda di proses pengklasifikasiannya. Yang satu HARD CLUSTERING dan yang kedua SOFT CLUSTERING, dalam artian, yang satu selalu menentukan suatu data masuk ke suatu cluster atau tidak (ya dan tidak) sedang yang SOFT, suatu data bisa masuk satu cluster dengan derajat tertentu (misalnya kabupaten A, bisa masuk kelompok 1 dengan derajat membership 0,74, ke kelompok 2 dengan derajat 0,18, ke kelompok 3 dengan derajat 0,08; kalau diasumsikan ada 3 kelompok di dalam data kita).
Demikian dan semoga menjawab.
sore..pak..
nie mahasiswa bapak yang mata kuliah metode penulisan ilmiah, kelas D061 hari selasa jam 15.30-17.00. saya mau nanya alamat bapak di group.yahoo.com, saya coba belum bisa pak. dan satu lagi soal materi yang suruh bapak download, saya lihat yang ada cuma Metode Penulisan Ilmiah untuk D3 saja, apa materi itu juga sama untuk saya yang S1 pak? mohon petunjuknya ya pak, Trima kasih sebelumnya^_^..
Terima kasih atas tulisan Bapak yang sangat membantu saya yang baru belajar Pengenalan Pola, saya ingin tanya pak?
Algo K-Mean itu paling tepat di implementasikan pada permasalahan apa? kemudian bahasa pemrog. apa yang paling mudah untuk diimplementasikannya? terima kasih sebelumnya..
mau tanya pak…sy melakukan clusterisasi menggunakan Fuzzy C-Means…
utk mengukur seberpa besar tingkat presisi yang dihasilkaan oleh metode tersebut…menggunakan rumus apa y?
Dan Mengenai K-Harmonic Means, apakah K-Harmonic Means itu hampir sama dengan Fuzzy c means, karena dilihat bahwa K-HArmonic Means juga mempunyai weight ddi setiap datanya..?
Lalu apakah dengan menggunakan K-HArmonic Means, apakh semua data akan tercluster, seperti halnya Fuzzy C-Means.
Dan Apakah K-Harmonic Means dapt menghasilkan solusi yang global
Terima Kasih Sebelumnya
Terima Kasih Pak Atas Jawabannya
Tapi ada yang mau saya tanyakann lagi pak
Cluster Validation itu artinya sama dengan untuk menentukan keakuratan clustering ya?
Apakah Elbow Criterrion itu hanya bisa digunakan untuk K-Means saja, kalau saya gunakan di K-Harmonic Means apakah bisa?
trimakasih atas artikel yang menarik diatas pak,,,
tetapi saya ada beberapa pertanyaan…
ada contoh implementasinya gag pak, soalnya saya bingung ketika mengimplementasikannya pada persoalan yang ada.
contohnya: penentuan studi tugas akhir berdasarkan nilai matakuliah tetapi menggunakan metode K-Means…
mohon pencerahan
terimakasih ^.^
Saya Baiknya Pake Metode yang mana ya dengan menggunakan 26 observasi??
K-means atau Fuzzy C-means??
Saya mau tanya..
Saya ingin melakukan pengelompokkan 26 Kabupaten/kota di Jabar berdasarkan derajat kesehatan. Jadi ada 26 observasi dan 11 variabel indikator.Datanya numerik.
Truz saya ingin melakukan analisis dengan analisis klaster.Baiknya pakai k-means atau Fuzzy C-means Ya??
Apa ada ketentuan banyaknya observasi untuk k-means dan FCM??
Klo Iya berapa??
K-Harmonic Means berbeda dengan K-Means dalam hal bentuk objective functionnya. Dengan perbedaan objective function ini, maka rumus yang digunakan untuk menghitung cluster center juga berbeda. Secara algorithm keduanya sama, tetapi rumus-rumus penghitungan yang digunakan berbeda.
Mungkin demikian yang bisa dijawab, kalau ada waktu nanti saya tambahkan di tulisan ini mengenai k-harmonic means juga.
Pak Jika berkenan
Mohon minta penjelasan lebih detail tentang k-harmonic means
Karena saya sangat perlu untuk keperluan tugas akhir saya
Saya sudah membaca paper tentang k-harmonic means, tapi saya masih bingung..
Terus pak..apakah sebenarnya yang dimaksud dengan objective function, weight function, function tersebut digunakan pada saat kapan?
Terima Kasih Sebelumnya.
K-Medoids sama seperti k-means pada intinya, tetapi cara untuk menentukan cluster centernya yang berbeda. Kalau k-means dengan mencari nilai rata-rata data yang ada di dalam satu cluster, kalau k-medoids dengan mencari data yang mana yang paling representative di dalam suatu cluster. Dalam k-medoids ini, data yang paling representative tersebut yang menjadi ‘cluster center’-nya.
Demikian dan semoga menjawab.
pak mau nanya,,kalo k-means sama k-medoids bedanya d mana ya?
kalo k-means jadinya pake euclidean distance ya?
makasih pak
Sebenarnya secara natural tidak batas minimal jumlah cluster. Kalau data yang kita miliki, homogen semuanya, satu cluster adalah representasi yang paling bagus. Tetapi karena nature-nya, FCM berfungsi untuk mengelompokkan data, maka jumlah cluster minimal adalah 2 cluster.
Membership function bisa mempunyai nilai 1, bila nilai centroidnya sama dengan nilai datanya. Kalau model hanya dengan satu cluster, membership function untuk semua data nilainya 1.
Semoga menjawab.
Yth bpk Yudi saya mau menanyakan beberapa hal Mengenai FCM :
Berapakah Cluster minimum pada FCM ?
Bisakah random Degree of Membership Function bernilai 1 dan Membership function jumlahnya hanya 1?
Mohon penjelasannya, terima kasih….
Saya tidak mengerti maksudnya dengan titik-titik tersebut. Pada dasarnya, kalau data yang anda miliki bisa diubah menjadi representasi berupa numeric atau kategorical, akan bisa dilakukan pengklasifikasian dengan clustering baik K-Means maupun Fuzzy C-Means.
Maaf bapak data yang di dapatkan bukan berupa image tetapi berupa titik-titik?
Kalau dia berupa image, berarti bisa melakukan image clustering yaitu mengelompokkan image-image yang ada menjadi beberapa kelompok sesuai dengan karakteristik yang dimiliki. Selain itu, setiap image yang didapatkan juga bisa dicari karakteristiknya dengan melakukan clustering terhadap setiap image yang ada. Yang pasti kedua metode bisa digunakan untuk itu. Referensi lebih lanjut tentang image clustering banyak tersedia di internet.
Data sinyal otak ini berupa gambar sinyal otak yang sudah diubah ke noteped dalam bentuk titik-titik yang buanyak sekali.Kira-kira cocok tidak kedua metode tersebut digunakan???jika iya kira-kira apa alasannya??terimakasih atas penjelasannya.
Mbak Teti, saya perlu tahu dulu data sinyal otaknya itu seperti apa? Apa berupa sinyal berkelanjutan, image atau yang lainnya.
Bapak yudi saya tanya lagi. Untuk pengolahan sinyal otak apakah cocok jika datanya dikluster menggunakan FCM dan K-means??Jika iya kenapa dipilih metode tersebut???Terimakasih atas penjelasannya.
K-Means itu termasuk hard clustering, yang diartikan, dalam setiap proses pengelompokan, setiap data masuk menjadi bagian ke dalam suatu cluster secara penuh atau tidak sama sekali (a_ik=1 atau 0). Sedangkan Fuzzy C-Means itu termasuk soft clustering, dimana setiap dapat menjadi anggota suatu cluster dengan kemungkinan _dari_ 0 _sampai_ 1. Jadi bisa saja kita mengatakan data nomor 1 masuk ke cluster nomor 1 dengan kemungkinan 0,42, ke cluster nomor 2 dengan kemungkinan 0,24, dst dst. Jadi nilai a_ik-nya tidak harus 1 atau 2. Kalau menanyakan mana yang lebih bagus, saya memilih FCM, karena setiap proses pengelompokan dilakukan dengan cara yang lebih soft dibanding dengan K-Means.
Mbak Sheila, yang dimaksud di sini, nilai J(U,V) yang terdapat pada rumus yang paling atas dalam tulisan ini.
Bpk Yudi saya ingin bertanya lagi.Apakah jika kita melakukan pengelompokan dengan FCM secara otomatis K-means akan masuk di dalamnya??Jika tidak apakah perbedaanya??Satu lagi bpk diantara kedua metode tsb mana yang lebih baik untuk melakukan pengelompokan data??Terimakasih untuk penjelasannya.
nilai akhir fungsi k-means??maksudnya gimana pak?saya bgung,,
Mbak Sheila, memang kalau kita menggunakan elbow criterion, hal seperti ini bisa terjadi. Untuk menentukannya, pakai saja nilai akhir fungsi k-means yang digunakan. Yang lebih kecil yang lebih bagus.
Semoga menjawab.
Mbak Teti, sebenarnya ada berbagai macam cara inisiasi centroid awal. Tetapi saya sendiri, lebih cenderung membiarkan agar data berbicara untuk dirinya sendiri. Dalam artian, centroid awal ditentukan secara acak, kemudian dia akan mencari centroid akhir sesuai dengan karakteristik data masing-masing. Kalau memakai proses inisiasi nilai centroid, kalau karakteristik metode yang digunakan untuk menentukan centroid awal sama dengan karakteristik k-means tidak jadi masalah, tetapi kalau berbeda, bisa dikatakan ada suatu pemaksaan angka centroid awal, yang mungkin tidak sesuai dengan karakteristik data dan metode clustering yang digunakan.
Semoga menjawab.
Bpk yudi disini saya ingin menanyakan masalah K-means. Mengapa untuk centroid awal ditentukan secara acak???mohon penjelasannya dan terima kasih atas penjelasannya.
pak saya kan udah menemukan titik ke 10 sebagai jumlah cluster yang tepat dengan melihat perubahan nilainya,apa perlu saya mengadakan uji lagi pada cluster setelahnya,,apa udah selese berhenti d cluster 10 saja?menurut bapak?
kemudian saya mau menanyakan lagi,,kok tiap kali runtime hasilnya beda2 ya pa?pada 5kali runtime jumlah cluster yang tepat 9 akan tetapi pada 10 kali runtime jumlah cluster yang tepat menjadi 10,ini bagaimana bapak?saya bingung ,,ambil yg mana..baeknya bagaimana?
Bpk Yudi disini saya ingin menanyakan mengenai FCM dan K-means. Kenapa untuk centroid awal ditentukan secara random??Terima kasih untuk penjelasannya.
RS memperlihatkan tingkat perbedaan antara satu cluster dengan cluster yang lain. Nilai mendekati 0 atau 0 menunjukkan keadaan/komposisi cluster yang satu dengan yang lain hampir sama, dan sebaliknya nilai mendekati 1 atau 1 menunjukkan bahwa keadaan/komposisi satu cluster berbeda dengan cluster yang lain.
maap pak saya tanya lagi,,pada RMSSTD Makin rendah nilai RMSSTD makin mirip data di dalam cluster yang ditemukan.,,tetapi klo pada RS gimana pak?semakin kecil menunjukkan apa? kan nilai RS antara 0 hingga 1,,RS yang baek mendekati 1 atau 0 pak?
maap pak saya tanya lagi,,pada RMSSTD Makin rendah nilai RMSSTD makin mirip data di dalam cluster yang ditemukan.,,tetapi klo pada RS gimana pak?semakin kecil menunjukkan apa? kan nilai RS antara 0 hingga 1,,RS yang baek mendekati 1 atau 0 pak,,
Berbanding terbalik artinya komposisi antara persentase nilai RMSSTD dan RS berubah. Tadinya yang satu lebih besar, setelah suatu titik nilai yang lainnya yang lebih besar. Titik perubahan itulah menjadi jumlah cluster yang paling tepat untuk data yang dimodel.
Semoga menjawab
terima kasih pak,,saya udah melakukan uji terhadap 400 data dengan menggunakan elbow criterion,,seperti pada blog bapak,,yang ingin saya tanyakan lagi,,di blog tersebut ada kata “Apabila muncul suatu keadaan yang berbanding terbalik dengan keadaan sebelumnya, ” neh saya masih kurang mengerti pak,,berbanding terbalik itu gimana?
Menentukan jumlah cluster dalam k-means memang agak susah dan tidak ada panduan yang jelas. Anda bisa menggunakan Partition Entropy, Bootstrapped method, atau likelihood ratio.
Semoga menjawab.
pak,saya sedang mengerjakan skripsi saya tentang K-Means,,tapi saya bngung analisa K-means nya menggunakan apa,,data yang saya gunakan 400 dan saya cluster menggunakan K-Means,,untuk mengetahui jumlah cluster yang paling optimal dan bagus,baiknya memakai apa?
pak, saya mohon penerangan dong. kalo ingin menerapkan hiraki clustering sebaiknya diimplemetasikan pada masalah apa yah??soalnya saya bingung untuk implementasiannya padahal programmnya menggunakan data buatan sudah jadi. mohon dibalas. ato di-email.
Bisa saja. K-Means bisa digunakan untuk mengelompokkan image berdasarkan karakteristiknya. Yang menjadi masalah, seringnya adalah bagaimana kita bisa memberikan tag atau anotasi pada sebuah gambar secara otomatis sehingga bisa diklasifikasikan lebih lanjut menggunakan K-Means. Automatic annotation atau tagging seperti ini banyak dipelajari pada keilmuan computer visioin.
pak, saya mau bertanya k-means itu klo diterapkan pd image retrieval kyk gma
pak, k-means klo diterapkan pada image retrieval bisa ga??gmana??makasih y
Fenny, saya di Jakarta sampai tanggal 10 Juli. Kalau mau konsultasi, datang ke ruangan saja
wah… ini materi ujian saya besok lusa… jika Bapak berkenan, saya mau minta dijelaskan cara groupingnya setelah menentukan centroidnya. Maklum, Pak… Saya baru belajar… Rabu sore (2/7) Bapak di kampus?
Tidak ada kerugian apa-apa. Hanya nilai membership functionnya saja yang sedikit mengalami perubahan komposisi, lebih menyebar atau lebih menyempit. Semoga menjawab.
Maaf pak, saya tanya lagi….
Bapak menyebutkan bahwa makin besar nilai m, makin luas sebaran membership function yang ada terhadap keseluruhan pemodelan.
Apa kerugian jika semakin luas sebaran membership function yang ada terhadap keseluruhan pemodelan?
Terima kasih atas jawaban Bapak.
C-Means sama dengan K-Means. Penjelasannya bisa dilihat di atas.
Wah menarik sekali, pak bagaimana dengan c means? Saya mengalami masalah dalam menganalisa gambar dengan c means ini….
Saya jawab di sini saja ya.
Weighting exponent (m) mempengaruhi seberapa besar tingkat ketidak pastian (membership function) suatu data dalam suatu pemodelan. Makin besar nilai m, makin luas sebaran membership function yang ada terhadap keseluruhan pemodelan. Nilai yang memungkinkan digunakan adalah m>1.0. Interval yang banyak digunakan adalah [1.5,3.5] dan nilai yang umum digunakan adalah 2.0, dengan alasan: disamping melihat tingkat pengaruh sebaran nilai membership function dalam suatu pemodelan, juga melihat mathematical convenience dalam menghitung membership function (u_ik) yang diperlukan.
Saya sendiri tidak terlalu banyak memikirkan nilai m ini selain 2.0. FYI, ada juga beberapa referensi yang berusaha mencari nilai m yang tepat untuk suatu pemodelan. Untuk yang ini, mungkin anda bisa minta bantuan google.
Untuk pertanyaan yang lain:
1. Semua data bisa bisa dicluster asalkan data tersebut bukan categorical data. Karena sifat Fuzzy c-Means yang mencari tingkat kesamaan antar data menggunakan konsep jarak geometri.
2. Untuk jenis data yang bagus dimodel dengan fuzzy c-means, sudah tentu adalah data yang bentuk clusternya globular (lingkaran, elips atau yang sejenisnya). Hal ini karena fuzzy c-means menggunakan konsep jarak geometri untuk mencari kesamaan antar data. Tetapi sudah tentu kita umumnya tidak tahu bentuk data yang dimodel terlebih dahulu (kecuali data yang kita miliki 1, 2 atau 3 dimensi), masih bisa kita visualisasikan. Begitulah ciri khas dari metode yang tergolong unsupervised classification. Kalau memang kita tahu bentuk data kita di awal pemodelan, kita bisa mencari metode clustering yang paling cocok untuk data tersebut.
Mudahan bisa menjawab.
Kalau bapak tidak keberatan mohon jawabannya bisa dikirim ke email saya: husmul_beze79@yahoo.co.id.
Pertanyaan yang lain:
1. Apakah pada penggunaan Fuzzy K Mean bisa dipastikan semua data bisa ter-cluster?
2. Data apa saja yang bisa di cluster menggunakan Fuzzy K Mean. Semua data? Atau pada data-data dengan karakter tertentu saja hasil cluster akan menjadi baik, sementara pada data karakter lain kurang bagus dilakukan cluster dengan Fuzzy K Mean? Terus….kalau iya…data yang berkarakter seperti apakah yang bagus digunakan cluster menggunakan Fuzzy K Mean?
Terima kasih.
Saya sungguh mendapat pencerahan dengan tulisan Bapak soal Fuzzy clustering. Kalau diperbolehkan bertanya. Apakah fungsi dari m (weight exponent) pada FCM? Makna dari m dari FCM adalah apa pak? Trus kaitannya jika dilakukan cluster terhadap data apa?
Terima kasih atas penjelasannya.