Spectral Clustering: Tipe Matriks Q


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



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.

Tinggalkan sebuah komentar

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