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 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]';
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.
Saya tertarik untuk diskusi lebih lanjut untuk pengolahan data (statistik dan pendekatan machine learning) untuk data riset. Detail mohon bisa komunikasi lebih lanjut pada alamat email yang saya infokan lebih lanjut.
Diskusi lebih lanjut dapat dilakukan dengan menghubungi nomor kontak yang tersedia pada halaman hubungi kami https://piptools.net/hubungi-kami/ . Terima kasih