Spectral Clustering: Tipe Matriks Normalisasi Laplacian (NL)

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 Normalisasi Laplacian. Perhitungan Eigen Vector didapatkan dari Matriks Normalisasi Laplacian (NL), dan pengelompokan data dilakukan berdasarkan proses k-means pada matriks normalisasi Eigen Vector

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;

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_NL(data,jumlahCluster);

Memasuki perhitungan utama pada fungsi Spectral_NL

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 Normalisasi Laplacian, yang disimbolkan dengan NL
Matriks Normalisasi Laplacian dihitung dengan rumus:
NL = D^(-1/2) .* L .* D^(-1/2);

Ada 2 cara untuk menghitung Matriks Normalisasi Laplacian
Cara pertama adalah sebagai berikut:

for i=1:size(A,1)
    for j=1:size(A,2)
        NL1(i,j) = A(i,j) / (sqrt(D(i,i)) * sqrt(D(j,j)));  
    end
end

Cara kedua adalah menggunakan matriks Identitas, dengan hasil perhitungan adalah sebagai berikut:

NL2 = eye(size(A,1),size(A,2)) - (D^(-1/2) .* A .* D^(-1/2));

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

[eigenVector,eigenValue] = eig(NL1);

5. Tentukan beberapa Eigen Vector yang memiliki Eigen Value tertinggi

k = jumlahCluster;
daftarEigenVectorTerbesar = eigenVector(:,(size(eigenVector,1)-(k-1)): size(eigenVector,1));

6. Hitung matriks Normalisasi Eigen Vector Terbesar, yang disimbolkan dengan U
Untuk masing-masing baris data, hitung jumlah nilai baris tersebut
Nilai normalisasi dihitung dengan cara membagi setiap nilai dengan jumlah nilai baris tersebut

for i=1:size(daftarEigenVectorTerbesar,1)
    jumlahNilaiBaris = sqrt(sum(daftarEigenVectorTerbesar(i,:).^2));    
    U(i,:) = daftarEigenVectorTerbesar(i,:) ./ jumlahNilaiBaris; 
end

7. Lakukan proses pengelompokan data pada matriks normalisasi Eigen Vector menggunakan metode K-Means

[daftarCluster,daftarCentroid] = kmeans(U,jumlahCluster);

* 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:jumlahCluster
    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) , ...
        ' , -> kelompok data ' , char(atribut(idxmaks))]);
    disp('------------------------------');

    st(idxmaks) = 1;
end;
disp(char(10));

Hasil akhir adalah:

Algoritma Spectral Clustering: Tipe Matriks Normalisasi Laplacian (NL)
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 A 50 60 70
Siswa B 65 80 73
Siswa C 72 70 65
Siswa E 40 82 73
Siswa K 92 91 55
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 2 , -> 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
Kelompok ini memiliki skor terbanyak pada kolom ke 1 , -> kelompok data IPA
------------------------------
Siswa G 60 74 96
Siswa H 75 75 92
Siswa N 74 76 89
Siswa R 81 65 88
Kelompok ini memiliki skor terbanyak pada kolom ke 3 , -> kelompok data Bahasa
------------------------------

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