Algoritma K-Medoids Clustering

Algoritma K-Medoids Clustering adalah salah satu algoritma yang digunakan untuk klasifikasi atau pengelompokan data. Contoh yang dibahas kali ini adalah mengenai penentuan jurusan siswa berdasarkan nilai skor siswa.
Algoritma ini memiliki kemiripan dengan Algoritma K-Means Clustering, tetapi terdapat beberapa perbedaan utama, dimana apabila pada Algoritma K-Means Clustering, nilai tengah dihitung dengan rata-rata (mean) dan perhitungan jarak dihitung dari data pada masing-masing mean, sedangkan pada algoritma ini, data akan digunakan sebagai nilai tengah / disebut dengan medoid, dan perhitungan jarak dihitung dari jarak antar masing-masing data.

Diasumsikan ada 20 orang siswa, yaitu siswa A sampai dengan T
Masing-masing siswa memiliki rata-rata nilai IPA, IPS, dan Bahasa yang berbeda-beda
Maka tentukan semua siswa tersebut akan masuk ke dalam jurusan apa berdasarkan nilai skor yang dimiliki
Diasumsikan data awal nilai siswa adalah sebagai berikut

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data awal adalah sebagai berikut:

data=[50, 60, 70; ...
    65, 80, 73; ...
    72, 70, 65; ...
    83, 65, 80; ...
    40, 82, 73; ...
    95, 71, 85; ...
    60, 74, 96; ...
    75, 75, 92; ...
    83, 55, 70; ...
    91, 60, 65; ...
    92, 91, 55; ...
    76, 80, 59; ...
    75, 65, 74; ...
    74, 76, 89; ...
    63, 79, 69; ...
    58, 93, 76; ...
    82, 50, 80; ...
    81, 65, 88; ...
    76, 74, 70; ...
    77, 71, 55]';

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan Jumlah Cluster
Jumlah Cluster adalah jumlah dari pengelompokan data yang ingin dilakukan
Jumlah Cluster nilainya harus diantara 2 dan jumlah data
Diasumsikan dalam kasus ini, jumlah pengelompokan data ada 3 kelompok, yaitu jurusan IPA, jurusan IPS, jurusan Bahasa

jumlahCluster = 3;

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses pengelompokan dengan metode K-Medoids Clustering
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 6)

daftarCluster = kMedoids(data,jumlahCluster);

Memasuki perhitungan utama pada fungsi kMedoids

1. Hitung jumlah data pada matriks data

jumlahData = size(data,2);

2. Hitung matriks v
Lakukan perkalian matriks data dengan dirinya sendiri
dan jumlahkah nilai yang terdapat dalam masing-masing dimensi untuk setiap data

v = dot(data,data,1);

3. Hitung matriks jarak, yang disimbolkan dengan D
Lakukan penjumlahan nilai baris matriks v dengan nilai kolom dari transpos matriks v
Kemudian kurangkan dengan 2 kali dari matriks data dikali dengan transpos matriks data

D = bsxfun(@plus,v,v')-2*(data'*data);

for i=1:jumlahData,
    D(i,i) = 0;
end

4. Tentukan medoid awal mula, yang diisi dengan nilai acak dari angka 1 sampai jumlah data, sebanyak jumlah cluster
Ambil semua nilai dari masing-masing baris data pada nilai acak tersebut
Kemudian bandingkan nilai minimal dari masing-masing data untuk membentuk daftar cluster mula-mula

[~, daftarCluster] = min(D(randsample(jumlahData,jumlahCluster),:),[],1);

5. lakukan perhitungan selama masih ada data yang berpindah cluster (poin 5a -5c)

daftarClusterTerakhir = 0;
while any(daftarCluster ~= daftarClusterTerakhir)
	. . .

5a. Ambil daftar cluster lama sebagai daftar cluster terakhir

daftarClusterTerakhir = daftarCluster;    

5b. Tentukan data acak selain medoid lama untuk menggantikan nilai medoid lama
Lakukan pencatatan indeks cluster yang lama
Lakukan perkalian indeks tersebut dengan matriks D
Kemudian cari indeks data yang nilai minimal pada masing-masing cluster

[~, idxD] = min(D*sparse(1:jumlahData,daftarCluster,1,jumlahData,jumlahCluster,jumlahData),[],1);

5c. Ambil semua nilai dari masing-masing baris data pada indeks yang telah ditentukan sebelumnya
Kemudian hitung nilai minimal dari matriks indeks D untuk mendapatkan nilai minimal dan daftar cluster yang baru

[nilaiMinimal, daftarCluster] = min(D(idxD,:),[],1);

6. Jika diperlukan, hitung penjumlahan nilai minimal yang didapatkan pada matriks D akhir

nilaiEnergi = sum(nilaiMinimal);

* Tampilkan semua data yang sudah dimasukan ke dalam cluster
Hitung nilai skornya untuk masing-masing kriteria dalam cluster tersebut
Ambil nilai skor tertinggi sebagai jawaban jurusan yang seharusnya diambil

data = data';
jumlahCluster = size(daftarCentroid,2);
st = zeros(1,size(data,2),'uint8');

for k = 1:jumlahCluster
    if cellfun('length',daftarDataPerCluster(k)) > 1,
        skor = zeros(1,size(data,2),'double');
        for i = 1:size(data,1)
            s = '';
            if daftarCluster(i) == k,
                s = strcat([s, 'Siswa ', char(i + 64), '   ']);
                for j = 1:size(data,2)
                    s = strcat([s, ' ', num2str(data(i,j)), ' ']);

                    if st(j) == 0, skor(j) = skor(j) + data(i,j); end;
                end
                disp(s);
            end;
        end;

        maks = -inf;
        idxmaks = -1;
        for i = 1:size(data,2)
            if maks < skor(i),
                maks = skor(i);
                idxmaks = i;
            end
        end

        disp(['Kelompok ini memiliki skor terbanyak pada kolom ke ' , num2str(idxmaks + 1) , ...
            ' , -> kelompok data ' , char(atribut(idxmaks))]);
        disp('------------------------------');

        st(idxmaks) = 1;
    end;    
end;

Hasil akhir adalah:

Algoritma K-Medoids Clustering
Contoh: Penentuan jurusan siswa berdasarkan nilai skor siswa
Diasumsikan ada 20 orang siswa, yaitu siswa A sampai dengan T
Masing-masing siswa memiliki rata-rata nilai IPA, IPS, dan Bahasa yang berbeda-beda
Maka tentukan semua siswa tersebut akan masuk ke dalam jurusan apa berdasarkan nilai skor yang dimiliki
Diasumsikan data awal nilai siswa adalah sebagai berikut
Nama Siswa, Nilai IPA, Nilai IPS, Nilai Bahasa
Siswa A   ,        50,        60,           70
Siswa B   ,        65,        80,           73
Siswa C   ,        72,        70,           65
Siswa D   ,        83,        65,           80
Siswa E   ,        40,        82,           73
Siswa F   ,        95,        71,           85
Siswa G   ,        60,        74,           96
Siswa H   ,        75,        75,           92
Siswa I   ,        83,        55,           70
Siswa J   ,        91,        60,           65
Siswa K   ,        92,        91,           55
Siswa L   ,        76,        80,           59
Siswa M   ,        75,        65,           74
Siswa N   ,        74,        76,           89
Siswa O   ,        63,        79,           69
Siswa P   ,        58,        93,           76
Siswa Q   ,        82,        50,           80
Siswa R   ,        81,        65,           88
Siswa S   ,        76,        74,           70
Siswa T   ,        77,        71,           55


Jumlah Cluster = 3


Data yang sudah dikelompokkan:
------------------------------
Siswa C 72 70 65
Siswa J 91 60 65
Siswa K 92 91 55
Siswa L 76 80 59
Siswa T 77 71 55
Kelompok ini memiliki skor terbanyak pada kolom ke 1 , -> kelompok data IPA
------------------------------
Siswa D 83 65 80
Siswa F 95 71 85
Siswa G 60 74 96
Siswa H 75 75 92
Siswa I 83 55 70
Siswa M 75 65 74
Siswa N 74 76 89
Siswa Q 82 50 80
Siswa R 81 65 88
Kelompok ini memiliki skor terbanyak pada kolom ke 3 , -> kelompok data Bahasa
------------------------------
Siswa A 50 60 70
Siswa B 65 80 73
Siswa E 40 82 73
Siswa O 63 79 69
Siswa P 58 93 76
Siswa S 76 74 70
Kelompok ini memiliki skor terbanyak pada kolom ke 2 , -> kelompok data IPS
------------------------------

Contoh modul / source code menggunakan Matlab dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.