Spectral Clustering: Tipe Matriks Laplacian (L) 2


Algoritma Spectral 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.
Ada beberapa teknik Spectral Clustering yang dapat digunakan, dan teknik yang digunakan pada kali ini adalah teknik Matriks Laplacian. Perhitungan Eigen Vector didapatkan dari Matriks Laplacian (L), dan pengelompokan data dilakukan berdasarkan proses threshold pada Eigen Vector dengan Eigen Value terbesar kedua.



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 SiswaNilai IPANilai IPSNilai Bahasa
Siswa A506070
Siswa B658073
Siswa C727065
Siswa D836580
Siswa E408273
Siswa F957185
Siswa G607496
Siswa H757592
Siswa I835570
Siswa J916065
Siswa K929155
Siswa L768059
Siswa M756574
Siswa N747689
Siswa O637969
Siswa P589376
Siswa Q825080
Siswa R816588
Siswa S767470
Siswa T777155

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

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses pengelompokan dengan metode Spectral Clustering
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 7)

daftarCluster = Spectral_L(data);

Memasuki perhitungan utama pada fungsi Spectral_L

1. Lakukan perhitungan untuk mengetahui tingkat kemiripan antar data, yang disimbolkan dengan A
nilai jarak dihitung dengan menggunakan rumus Euclidean,
yaitu akar kuadrat dari jumlah kuadrat masing-masing selisih antar data

%Tentukan sigma
sigma = 10;

for i=1:size(data,1)    
    for j=1:size(data,1)
        jarak = sqrt((data(i,1) - data(j,1))^2 + (data(i,2) - data(j,2))^2 + (data(i,3) - data(j,3))^2); 
        A(i,j) = exp(-jarak/(2*sigma^2));
    end
end

2. Hitung matriks Diagonal, yang disimbolkan dengan D
nilai diagonal pada matriks tersebut akan berisi semua jumlah nilai pada masing-masing baris

for i=1:size(A,1)
    D(i,i) = sum(A(i,:));
end

3. Hitung matriks Laplacian, yang disimbolkan dengan L
matriks Laplacian adalah matriks diagonal dikurangi dengan matriks ketertarikan

L = D - A; 

4. Lakukan proses dekomposisi pada matriks Laplacian untuk mendapatkan Eigen Vector

[eigenVector,eigenValue] = eig(L);

5. Eigen Value terbesar kedua adalah Eigen Vector pada kolom kedua

EigenValueTerbesarKedua = eigenVector(:,2);

6. Tentukan Threshold yang digunakan untuk melakukan pengelompokan data
Karena ada 3 kelompok yang sedang dicari, maka dibutuhkan 2 nilai Threshold untuk membedakan ketiga kelompok tersebut
Proses pencarian nilai Threshold bebas tergantung kebutuhan

maksThreshold = max(EigenValueTerbesarKedua);
minThreshold = min(EigenValueTerbesarKedua);
nilaiTengah = median(EigenValueTerbesarKedua);

selisihMinimal = inf;
if abs(nilaiTengah-minThreshold) < abs(nilaiTengah-maksThreshold)
    selisihMinimal = abs(nilaiTengah-minThreshold);
else
    selisihMinimal = abs(nilaiTengah-maksThreshold);
end

ThresholdPertama = nilaiTengah - selisihMinimal * 0.1;
ThresholdKedua = nilaiTengah + selisihMinimal * 0.1;

7. Lakukan pengelompokan data berdasarkan nilai Threshold tersebut

[Cluster1,~,~] = find(EigenPertama <= ThresholdPertama);
[Cluster2,~,~] = find(EigenPertama > ThresholdPertama & EigenPertama <= ThresholdKedua);
[Cluster3,~,~] = find(EigenPertama > ThresholdKedua);

ukuranMaks = -inf;
if size(Cluster1, 1) > size(Cluster2, 1) && size(Cluster1, 1) > size(Cluster3, 1)
    ukuranMaks = size(Cluster1, 1);
elseif size(Cluster2, 1) > size(Cluster1, 1) && size(Cluster2, 1) > size(Cluster3, 1)
    ukuranMaks = size(Cluster2, 1);
else
    ukuranMaks = size(Cluster3, 1);
end

daftarCluster(1,:) = [Cluster1' zeros(1, ukuranMaks - size(Cluster1, 1))];
daftarCluster(2,:) = [Cluster2' zeros(1, ukuranMaks - size(Cluster2, 1))];
daftarCluster(3,:) = [Cluster3' zeros(1, ukuranMaks - size(Cluster3, 1))];

* 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

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

for k = 1:size(daftarCluster,1)
    skor = zeros(1,size(data,2),'double');
    for i = 1:size(daftarCluster,2)
        idxData = daftarCluster(k,i);
        s = '';
        if daftarCluster(k,i) ~= 0,
            s = strcat([s, 'Siswa ', char(idxData + 64), '   ']);
            for j = 1:size(data,2)
                s = strcat([s, ' ', num2str(data(idxData,j)), ' ']);

                if st(j) == 0, skor(j) = skor(j) + data(idxData,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) , ...
        ' , -> kelompok data ' , char(atribut(idxmaks))]);
    disp('------------------------------');

    st(idxmaks) = 1;
end;

Hasil akhir adalah:

Algoritma Spectral Clustering: Tipe Matriks Laplacian (L)
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


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


Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

2 pemikiran di “Spectral Clustering: Tipe Matriks Laplacian (L)