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 Q. Perhitungan Eigen Vector didapatkan dari Matriks Kemiripan (A), dan pengelompokan data dilakukan menggunakan matriks Q yang diperoleh dari 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;
* Tentukan Threshold Q
Nantinya setiap nilai pada matriks Q yang lebih dari nilai ini akan bergabung dalam cluster yang sama
Diasumsikan dalam kasus ini, nilai Threshold Q adalah 0.9
ThresholdQ = 0.9;
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 – 8)
daftarCluster = Spectral_Q(data, jumlahCluster, ThresholdQ);
Memasuki perhitungan utama pada fungsi Spectral_Q
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. Lakukan proses dekomposisi pada matriks kemiripan untuk mendapatkan Eigen Vector
[eigenVector,eigenValue] = eig(A);
3. Tentukan beberapa Eigen Vector yang memiliki Eigen Value tertinggi
k = jumlahCluster; daftarEigenVectorTerbesar = eigenVector(:,(size(eigenVector,1)-(k-1)): size(eigenVector,1));
4. 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
5.Hitung Matriks Q, yaitu perkalian matriks antara matriks Normalisasi Eigen Vector Terbesar dengan transpos matriks tersebut
Jika nilai data pada baris i kolom j mendekati 1, maka data i dan j akan membentuk satu cluster,
Jika nilai data pada baris i kolom j mendekati 0, maka data i dan j akan berada pada cluster berbeda
Q = U * U';
6. Pada masing-masing data, tentukan data-data lain yang diperkirakan akan membentuk sebuah cluster dengan dirinya
idxClusterPerData = 1; for i=1:size(Q,1) for j=1:size(Q,2) if Q(i,j) >= ThresholdQ && Q(j,i) >= ThresholdQ clusterPerData(idxClusterPerData,1) = i; clusterPerData(idxClusterPerData,2) = j; idxClusterPerData = idxClusterPerData + 1; end end end
7. Tentukan cluster yang berisi masing-masing data
for i=1:size(data,1) [baris,kolom] = find(clusterPerData(:,1) == i); for j=1:size(baris,1) SetClusterPerData(i,j) = clusterPerData(baris(j),2); end end
8. Hilangkan cluster yang berisi data sangat mirip untuk mendapatkan jawaban daftar cluster akhir
idxUnique = 1; uniqueSetCluster = SetClusterPerData(1,:); for i=1:size(SetClusterPerData,1) isDitemukan = 0; for j=1:idxUnique idxBarisUniqueSetCluster = find(SetClusterPerData(i,1) == uniqueSetCluster(j,:)); if idxBarisUniqueSetCluster > 0 isDitemukan = 1; break; end end if ~isDitemukan idxUnique = idxUnique + 1; uniqueSetCluster(idxUnique,:) = SetClusterPerData(i,:); end end
* 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(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; disp(char(10));
* Lakukan pencatatan data pada setiap data yang termasuk sebagai NOISE
NOISE adalah semua data yang tidak berhubungan dengan cluster apapun
Nantinya dapat dilakukan perhitungan lebih lanjut untuk memasukkan masing-masing NOISE ke dalam cluster yang ada
if size(daftarCluster,1) > jumlahCluster, disp('Sedangkan data siswa ini tidak diketahui hasilnya karena termasuk NOISE'); disp('------------------------------'); for k = jumlahCluster+1:size(daftarCluster,1) 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; end; else disp('Tidak ada data yang termasuk NOISE'); end; disp(char(10));
Hasil akhir adalah:
Algoritma Spectral Clustering: Tipe Matriks Q 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 Threshold Q = 0.9 Data yang sudah dikelompokkan: ------------------------------ Siswa A 50 60 70 Siswa B 65 80 73 Siswa E 40 82 73 Siswa O 63 79 69 Siswa P 58 93 76 Kelompok ini memiliki skor terbanyak pada kolom ke 2 , -> kelompok data IPS ------------------------------ Siswa C 72 70 65 Siswa K 92 91 55 Siswa L 76 80 59 Siswa S 76 74 70 Siswa T 77 71 55 Kelompok ini memiliki skor terbanyak pada kolom ke 1 , -> kelompok data IPA ------------------------------ Siswa D 83 65 80 Siswa F 95 71 85 Siswa Q 82 50 80 Siswa R 81 65 88 Kelompok ini memiliki skor terbanyak pada kolom ke 3 , -> kelompok data Bahasa ------------------------------ Sedangkan data siswa ini tidak diketahui hasilnya karena termasuk NOISE ------------------------------ Siswa G 60 74 96 Siswa H 75 75 92 Siswa N 74 76 89 Siswa I 83 55 70 Siswa J 91 60 65 Siswa M 75 65 74
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.