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:



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


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)

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

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

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:

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

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

5. Tentukan beberapa Eigen Vector yang memiliki Eigen Value tertinggi

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

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

* 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


Hasil akhir adalah:


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 *