Algoritma Mean Shift

Algoritma Mean Shift 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.
Kegunaan pengelompokan data ada beberapa macam. Pada kasus yang dibahas kali ini, data akan dikelompokkan ke dalam kelompok / cluster sehingga data-data yang memiliki kemiripan akan saling terkelompok, dan kemudian dapat dihitung kelompok tersebut merupakan kelompok apa. Contoh kasus pengembangan selanjutnya dari klasifikasi ini adalah menentukan data yang paling tidak cocok berada pada masing-masing cluster. Nantinya dapat ditarik kesimpulan apakah data tersebut dibuang atau dipindah ke cluster lain.

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

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 bandwidth, yaitu konstanta yang digunakan untuk menghitung sebuah data akan berada pada cluster tersendiri atau bergabung dengan cluster yang ada
Diasumsikan dalam kasus ini, nilai bandwidth adalah selisih nilai maksimal dan minimal data dibagi dengan jumlah atribut (jurusan)

bandwidth = (max(data(:)) - min(data(:))) / size(data,1);

* Tentukan epsilon, yaitu batas selisih minimal antara mean sekarang dengan mean pada perhitungan sebelumnya
Jika selisih antara kedua mean tersebut kurang dari nilai ini, maka perhitungan akan dihentikan
Diasumsikan dalam kasus ini, nilai epsilon adalah 0.1 persen dari nilai bandwidth

epsilon = 1e-3 * bandwidth;

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses pengelompokan dengan metode Mean Shift
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 3)

[daftarCentroid,daftarCluster,daftarDataPerCluster] = MeanShift(data,bandwidth,epsilon);

Memasuki perhitungan utama pada fungsi MeanShift

1. Lakukan perulangan selama masih ada titik yang belum dikunjungi (poin 1a – 1e)

while jumlahDataYangBelumDikunjungi > 0
. . .

1a. Tentukan posisi acak dari data yang belum masuk ke dalam cluster

    tmpPosisiAcak	= ceil( (jumlahDataYangBelumDikunjungi-1e-6)*rand);
    idxDataAcak     = daftarDataYangBelumDikunjungi(tmpPosisiAcak);

1b. Tentukan mean awal, yaitu diisi dengan data pada posisi acak yang sudah ditentukan sebelumnya

meanAwal        = data(:,idxDataAcak);

1c. Mean sebelumnya diisi dengan nilai yang sangat rendah, agar dapat masuk ke dalam perhitungan selanjutnya

meanSebelumnya  = repmat(-inf,1,jumlahDimensi)';

1d. Lakukan perulangan selama masih terdapat perbedaan mean antara mean sekarang dan mean sebelumnya (poin 1d1 – 1d8)

while norm(meanAwal-meanSebelumnya) >= epsilon
. . .

1d1. Hitung kuadrat jarak dari mean pada masing-masing data

daftarKuadratJarakDariMean = sum((repmat(meanAwal,1,jumlahData) - data).^2);

1d2. Ambil semua data yang masih termasuk dalam radius kuadrat bandwidth

calonDataDalamRadius = find(daftarKuadratJarakDariMean < bandWidth^2);

1d3. Tambahkan angka 1 pada setiap data dalam radius tersebut

jumlahCalonData(calonDataDalamRadius) = jumlahCalonData(calonDataDalamRadius)+1;

1d4. Ambil nilai mean sebelumnya, yaitu mean pada awal perhitungan

meanSebelumnya = meanAwal;

1d5. Hitung nilai mean yang baru, yaitu rata-rata dari semua data dalam radius bandwidth

meanAwal = mean(data(:,calonDataDalamRadius),2);

1d6. Tambahkan semua data dalam radius bandwidth sebagai calon data yang dimasukkan ke dalam cluster

calonData   = [calonData calonDataDalamRadius];

1d7. Untuk masing-masing data, beri status bahwa data ini sudah dikunjungi

isDataSudahDikunjungi(calonData) = 1;

1d8. Lakukan perhitungan ini sebagai perhitungan terakhir apabila masih terdapat perbedaan mean antara mean sekarang dan mean sebelumnya (poin 1d8a – 1d8c)

if norm(meanAwal-meanSebelumnya) < epsilon
. . .

* Lakukan pengecekan apakah calon data akan dimasukkan kedalam cluster yang sudah ada, atau membentuk cluster baru

1d8a. Lakukan perulangan sebanyak jumlah cluster yang sudah terbentuk (poin 1d8a1 – 1d8a2)

for i = 1:jumlahClusterTerbentuk
. . .

1d8a1. Hitung jarak antara nilai mean calon data dengan nilai mean pada cluster lain

jarakKeClusterLain = norm(meanAwal-daftarCentroid(:,i));

1d8a2. Jika selisihnya kurang dari setengah nilai bandwidth,
Maka ambil cluster ini sebagai cluster tujuan

if jarakKeClusterLain < bandWidth / 2
	ClusterTujuan = i;
	break;
end

1d8b. Jika terdapat nilai cluster tujuan, maka lakukan penggabungan ke dalam cluster tersebut (poin 1d8b1 – 1d8b3)

if ClusterTujuan > 0
. . .

1d8b1. Hitung nilai mean yang baru, yaitu (nilai mean sekarang + nilai mean cluster) dibagi 2

daftarCentroid(:,ClusterTujuan)       = 0.5*(meanAwal+daftarCentroid(:,ClusterTujuan));

1d8b2. Tambahkan jumlah data kedalam jumlah data per cluster ini

jumlahDataPerCluster(ClusterTujuan,:)    = jumlahDataPerCluster(ClusterTujuan,:) + jumlahCalonData;

1d8c. Jika tidak terdapat nilai cluster tujuan, maka lakukan pembuatan cluster baru (poin 1d8c1 – 1d8c3)

1d8c1. Tambahkan jumlah cluster yang terbentuk

jumlahClusterTerbentuk                    = jumlahClusterTerbentuk+1;

1d8c2. Masukkan nilai mean sekarang sebagai nilai mean cluster yang baru

daftarCentroid(:,jumlahClusterTerbentuk)       = meanAwal;

1d8c3. Tambahkan jumlah data kedalam jumlah data per cluster yang baru

jumlahDataPerCluster(jumlahClusterTerbentuk,:)    = jumlahCalonData;

1e. Setelah sejumlah data masuk ke dalam cluster atau membentuk cluster baru,
Ambil data yang belum dikunjungi, dan hitung jumlah datanya untuk digunakan di perulangan selanjutnya

daftarDataYangBelumDikunjungi = find(isDataSudahDikunjungi == 0);
jumlahDataYangBelumDikunjungi = length(daftarDataYangBelumDikunjungi);

2. Tentukan nilai cluster akhir pada masing-masing data, yaitu cluster dengan nilai yang paling tinggi pada masing-masing data

[val,daftarCluster] = max(jumlahDataPerCluster,[],1);

3. Setelah menemukan cluster sebenarnya,
maka kumpulkan masing-masing data ke dalam cluster secara terurut

daftarDataPerCluster = cell(jumlahClusterTerbentuk,1);
for i = 1:jumlahClusterTerbentuk
	calonData = find(daftarCluster == i);
	daftarDataPerCluster{i} = calonData;
end

4. 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;

5. Lakukan pencatatan data pada setiap data yang termasuk sebagai NOISE
NOISE adalah semua data yang tidak berhubungan dengan cluster apapun dan tidak bisa membentuk cluster sendiri
Dalam hal ini, NOISE adalah cluster yang hanya berisi dirinya sendiri

if jumlahCluster > size(data,2),
    disp('Sedangkan data siswa ini tidak diketahui hasilnya karena termasuk NOISE');
    disp('------------------------------');
    
    for k = 1:jumlahCluster
        if cellfun('length',daftarDataPerCluster(k)) <= 1,
            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;
        end;    
    end;
else
    disp('Tidak ada data yang termasuk NOISE');
end;

Hasil akhir adalah:

Algoritma Mean Shift
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


Bandwidth = 18.6667
Epsilon   = 0.018667


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


Sedangkan data siswa ini tidak diketahui hasilnya karena termasuk NOISE
------------------------------
Siswa A 50 60 70
Siswa K 92 91 55
Siswa E 40 82 73

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.

Langkah-langkah penggunaan algoritma ini adalah

Hasil akhir adalah:

Contoh modul / source code menggunakan Matlab dapat didownload disini:

Bagikan ini: