Algoritma EM (Expectation–Maximization)

Algoritma EM (Expectation–Maximization) 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.
Sesuai namanya, ada 2 proses utama dalam algoritma ini, yaitu proses expectation (E), yaitu fungsi untuk memperkirakan evaluasi likelihood berdasarkan beberapa parameter yang ada, dan proses maximization (M), yaitu untuk memaksimalkan nilai likelihood yang ditemukan pada proses E. Kedua proses ini digunakan untuk menentukan distribusi data untuk proses E pada perulangan selanjutnya.

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

* Tentukan jumlah maksimal iterasi yang digunakan
Diasumsikan dalam kasus ini, jumlah maksimal iterasi adalah 100 kali

jumlahIterasi = 100;

* 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.0000000001

epsilon = 1e-10;

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses pengelompokan dengan metode EM (Expectation-Maximization)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 2)

daftarCluster = EM(data,jumlahCluster, jumlahIterasi, eps);

Memasuki perhitungan utama pada fungsi EM

1. Lakukan proses inisialisasi,
yaitu memasukkan masing-masing data ke dalam cluster acak (poin 1a – 1d)

1a. Tentukan jumlah data

[~,jumlahData] = size(data);

1b. Tentukan indeks data acak sebanyak jumlah cluster
Kemudian gunakan masing-masing data ini sebagai mean dari masing-masing cluster

idx = randsample(jumlahData,jumlahCluster);
mean = data(:,idx);

1c. Lakukan perhitungan selisih data dengan masing-masing mean
Kemudian catat cluster tujuan sementara dimana mengembalikan selisih paling maksimal

[~,daftarCluster] = max(bsxfun(@minus,mean'*data,dot(mean,mean,1)'/2),[],1);
[~,~,daftarCluster] = unique(daftarCluster);

1d. Lakukan pencatatan data cluster tujuan sementara untuk masing-masing data

R = full(sparse(1:jumlahData,daftarCluster,1,jumlahData,jumlahCluster,jumlahData));

2. Lakukan perhitungan sebanyak jumlah iterasi dan selama statusnya belum selesai (poin 2a – 2d)

while ~isSelesai && iterasi < jumlahIterasi
    iterasi = iterasi+1;
	. . .

2a. Lakukan proses maximization pada data
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2a1 – 2a7)

model = maximization(data,R);

Memasuki perhitungan utama pada fungsi maximization

2a1. Tentukan jumlah dimensi dan jumlah data

[jumlahDimensi,jumlahData] = size(data);

2a2. Tentukan jumlah cluster

jumlahCluster = size(R,2);

2a3. Hitung jumlah data pada masing-masing cluster

jumlahDataPerCluster = sum(R,1);

2a4. Hitung bobot pada masing-masing cluster
yaitu jumlah data per cluster dibagi jumlah semua data

bobotPerCluster = jumlahDataPerCluster/jumlahData;

2a5. Hitung nilai mu, yaitu perkalian antara data dengan probabilitas data tersebut dibagi dengan jumlah data per cluster

mu = bsxfun(@times, data*R, 1./jumlahDataPerCluster);

2a6. Lakukan perhitungan pada masing-masing cluster (point 2a6a – 2a6b)

for i = 1:jumlahCluster
. . .

2a6a. Hitung nilai Xo:
Lakukan pengurangan data dengan nilai mu pada perhitungan diatas
Kemudian lakukan perkalian nilai tersebut dengan akar kuadrat dari R

Xo = bsxfun(@minus,data,mu(:,i));
Xo = bsxfun(@times,Xo,akarKuadratR(:,i)');

2a6b. Hitung nilai Sigma
Lakukan perkalian antara Xo dan transpos Xo dibagi dengan jumlah data per cluster
Kemudian tambahkan nilai diagonal sigma dengan nilai yang sangat kecil

Sigma(:,:,i) = Xo*Xo'/jumlahDataPerCluster(i);
Sigma(:,:,i) = Sigma(:,:,i)+eye(jumlahDimensi)*(1e-6);

2a7. Ambil nilai mu, Sigma, dan bobot per cluster sebagai jawaban nilai model

model.mu = mu;
model.Sigma = Sigma;
model.bobot = bobotPerCluster;

2b. Lakukan proses expectation pada data untuk digunakan pada perulangan selanjutnya
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2b1 – 2b7)

[R, likelihood(iterasi)] = expectation(data,model);

Memasuki perhitungan utama pada fungsi expectation

2b1. Tentukan nilai mu, Sigma, dan bobot dari parameter model yang sudah dijelaskan sebelumnya

mu = model.mu;
Sigma = model.Sigma;
bobot = model.bobot;

2b2. Tentukan jumlah data dan jumlah cluster

jumlahData = size(data,2);
jumlahCluster = size(mu,2);

2b3. Lakukan perhitungan pada masing-masing cluster
Hitung nilai logaritma rho menggunakan fungsi logaritma gauss
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

for i = 1:jumlahCluster
    logRho(:,i) = LogGaussPDF(data,mu(:,i),Sigma(:,:,i));
end

* Gunakan fungsi ini untuk menghitung nilai logaritma gauss

function y = LogGaussPDF(data, mu, Sigma)
jumlahDimensi = size(data,1);
data = bsxfun(@minus,data,mu);
[U,p]= chol(Sigma);
if p ~= 0
    error('Pada fungsi LogGaussPDF, Sigma tidak dalam PD.');
end
Q = U'\data;
q = dot(Q,Q,1);
c = jumlahDimensi*log(2*pi)+2*sum(log(diag(U)));
y = -(c+q)/2;

2b4. Tambahkan nilai logaritma rho dengan nilai logaritma dari bobot

logRho = bsxfun(@plus,logRho,log(bobot));

2b5. Hitung nilai T, yang dihitung dengan rumus log(sum(exp(data),jumlahDimensi))
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

T = LogJumlahExp(logRho,2);

* Gunakan fungsi ini untuk menghitung rumus log(sum(exp(data),jumlahDimensi))

function s = LogJumlahExp(data, jumlahDimensi)
y = max(data,[],jumlahDimensi);
data = bsxfun(@minus,data,y);
s = y + log(sum(exp(data),jumlahDimensi));
i = find(~isfinite(y));
if ~isempty(i)
    s(i) = y(i);
end

2b6. Hitung nilai likelihood, yaitu jumlah dari nilai T dibagi dengan jumlah semua data

likelihood = sum(T)/jumlahData;

2b7. Lakukan pengurangan nilai logaritma rho dengan nilai T
Kemudian hitung nilai eksponen dari nilai tersebut sebagai jawaban nilai R yang baru

logR = bsxfun(@minus,logRho,T);
R = exp(logR);

* 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 EM (Expectation-Maximization)
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
Jumlah Iterasi = 100
Epsilon        = 1e-10


Selesai dalam 24 iterasi.
Data yang sudah dikelompokkan:
------------------------------
Siswa A 50 60 70
Siswa F 95 71 85
Siswa G 60 74 96
Siswa H 75 75 92
Siswa J 91 60 65
Siswa M 75 65 74
Siswa N 74 76 89
Kelompok ini memiliki skor terbanyak pada kolom ke 3 , -> kelompok data Bahasa
------------------------------
Siswa D 83 65 80
Siswa I 83 55 70
Siswa K 92 91 55
Siswa L 76 80 59
Siswa Q 82 50 80
Siswa R 81 65 88
Siswa T 77 71 55
Kelompok ini memiliki skor terbanyak pada kolom ke 1 , -> kelompok data IPA
------------------------------
Siswa B 65 80 73
Siswa C 72 70 65
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.

Langkah-langkah penggunaan algoritma ini adalah

Hasil akhir adalah:

Contoh modul / source code menggunakan Matlab dapat didownload disini:

Bagikan ini:

Tinggalkan sebuah komentar Batalkan balasan