Source Code Algoritma k-Nearest Neighbor (k-NN) Menggunakan Pemrograman Java

Table of Contents

Sebagaimana artikel saya sebelumnya, bahwa algoritma k-Nearest Neighbor menjadi salah satu dari top 10 algoritma data mining yang populer digunakan (Prasetya, 2014). Metode ini melakukan klasifikasi terhadap objek berdasarkan data pembelajaran yang jaraknya paling dekat dengan objek tersebut. Penentuan jarak yang paling dekat didasarkan atas kemiripan menggunakan metode perhitungan jarak (distance similarity). Merujuk ke artikel hitung manual k-NN, perhitungan jarak yang saya gunakan adalah Euclidean Distance. Saya sarankan sebelum oprek koding, pahami dulu perhitungan manual k-NN di Artikel hitung manual algoritma k-NN.

Gambar 1. Ilustrasi k-NN (sumber gambar: https://www.researchgate.net)

Pada postingan ini, saya tidak ada berpanjang lebar membahas teori dan hitung manual k-NN lagi.  Saya fokus ke bagaimana mengimplementasikan algoritma k-NN menggunakan bahasa pemrograman yang saya kuasai, yaitu Pemrograman Java. Saya sering mengatakan ke mahasiswa, sebelum masuk ke source code, biasakan dulu menghitung manual suatu algoritma, sebelum hitung manual baca dulu teorinya. Logika sederhananya adalah bagaimana mungkin mampu membuat source code suatu algoritma dalam bahasa pemrograman jika hitung manual saja tidak mampu, dan bagaimana bisa hitung manual kalau teorinya saja tidak paham. Jika sudah paham teori dan hitung manualnya. Ayo masuk ke source code.

Eh bentar, sebelum masuk source code, disiapkan dulu data training yang dijadikan dataset sederhana dalam pembuatan k-NN. Saya bilang sederhana karena hanya terdiri dari 10 baris data beserta klasifikasi yang dihasilkan. Ditampilkan di Gambar 2 berikut:

Gambar 2. Data Training

Data training ini adalah data tentang seleksi mahasiswa baru di suatu kampus, yang kriteria seleksi hanya mengandalkan 2 atribut, yaitu nilai rapor (NR) dan nilai ujian nasional (UN), serta memiliki 3 Kelas, yaitu Reguler, Beasiswa dan Tidak Lulus. Data training ini yang bakal menjadi acuan pengalaman k-NN untuk memutuskan klasifikasi kelas jika ada data baru yang masuk. Nantinya data baru yang masuk disebut sebagai data testing. Berarti data testing hanya terdiri dari NR dan UN, kemudian k-NN yang memutuskan klasifikasi kelasnya.

Langkah pertama dalam membuat source code k-NN adalah membuat dataset sederhana sebagaimana Gambar 2 sebagai data training pada aplikasi. Berhubung saya belum menggunakan basis data, maka data training cukup disimpan dalam array. Atribut dan kelas masing-masing memiliki nama variabel array yang berbeda.  

 // Data Training 
        int[] NR = {5, 4, 9, 6, 10, 9, 3, 5, 9, 2};
        int[] UN = {6, 6, 8, 5, 8, 6, 4, 3, 4, 3};
        String[] kelas = {"REGULER", "REGULER", "BEASISWA", "REGULER", "BEASISWA", "BEASISWA",
            "TIDAK LULUS", "TIDAK LULUS", "REGULER", "TIDAK LULUS"};

        //Data Testing
        int NR1 = 3;
        int UN1 = 4;

Berikutnya, membuat function untuk menghitung jarak euclidean. Sudah pada tahu rumusnya kan? jarak euclidean ini sangat populer digunakan dalam k-NN. Saya tidak lagi membahas bagaimana cara hitung manual dan cara bikin source code jarak euclidean. Cek saja di Mengukur Jarak Euclidean: Teori dan Implementasi.

    // membuat function untuk Jarak Euclidean
    static double jarakEuclidean(int NR, int NR1, int UN, int UN1) {
        return Math.sqrt(Math.pow(NR - NR1, 2) + Math.pow(UN - UN1, 2));
    }

Data training sudah, data testing sudah ada, function jarak euclidean juga sudah, kurang apa? belum selesai. Perjalanan kita masih berlanjut. Saya perlu membuat source code untuk menampilkan atribut, kelas serta hasil jarak euclidean yang diperoleh setiap data training ketika dibandingkan dengan data testing. Saya juga menambahkan HashMap untuk menyimpan hasil perhitungan jarak euclidean dan klasifikasi kelasnya.  

 
Map knn = new HashMap<>();
        System.out.println("DATA TESTING");
        System.out.println("Nilai Raport    : " + NR1);
        System.out.println("Ujian Nasional  : " + UN1);
        System.out.println("");
        System.out.println("Hasil Jarak Euclidean");
        System.out.println("NR   " + "UN   " + "Kelas      " + "    ED");
        for (int a = 1; a < 10; a++) {
            hasilED = jarakEuclidean(NR[a], NR1, UN[a], UN1);
            System.out.println(NR[a] + "    " + UN[a] + "   " + kelas[a] + "  " + hasilED);

            knn.put(hasilED, kelas[a]);
        }

Langkah terakhir, menentukan rangking tertinggi sebagai acuan menentukan klasifikasi kelas. Rangking tertinggi dapat diperoleh berdasarkan jarak euclidean yang paling kecil. Makin kecil jarak euclidean makin mirip dan akurat.

System.out.println("Hasil k-NN");

        Map knn_hasil = new TreeMap(knn);
        printMap(knn_hasil);

        System.out.println("");
        System.out.println("Hasil Keputusan : "+ knn_hasil.values().toArray()[0]);

Ada tambahan method untuk mencetak hasil hashMap. Untuk menentukan rangking tertinggi pada k-NN, saya menggunakan method TreeMap.

 public static void printMap(Map map) {
        Set s = map.entrySet();
        Iterator it = s.iterator();
        while (it.hasNext()) {
            Map.Entry entry = (Map.Entry) it.next();
            Double key = (Double) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println(key + " => " + value);
        }//while
        System.out.println("========================");
    }//printMap

Seluruh source code sudah selesai ditulis. Biar mudah dalam mempelajari source code k-NN, saya berbaik hati untuk berbagi code lengkapnya. Secara keseluruhan, code saya bagi menjadi 3 class. 

1. class KNN_Algoritma

2. class DataTraining

3. class KNN_Run

 
import java.io.IOException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 *
 * @author CHARIS
 */
public class KNN_Algoritma {

    /**
     * @param args the command line arguments
     */
   // public static void main(String[] args) throws IOException {

    public static String ranking="";
    public String knn(int nR, int uN) throws IOException{

        // TODO code application logic here
        // Data Training 
        
        DataTraining training = new DataTraining();
        
        
      
//        String[] kelas = {"REGULER", "REGULER", "BEASISWA", "REGULER", "BEASISWA", "BEASISWA",
//            "TIDAK LULUS", "TIDAK LULUS", "REGULER", "TIDAK LULUS"};

        //Data Testing
  

        int NR = nR;
        int UN = uN;


        double hasilED, hasilED_before;

        Map knn = new HashMap<>();
        System.out.println("DATA TESTING");
        System.out.println("NR    : " + NR);
        System.out.println("UN  : " + UN);
        System.out.println("");
        System.out.println("Hasil Jarak Euclidean");
        System.out.println("R   " + "G   " + "B     "   + "Kelas      " + "    ED");
        for (int a = 1; a < 10; a++) {
            hasilED = jarakEuclidean(training.NR[a], NR, training.UN[a], UN);
           // System.out.println(NR[a] + "    " + UN[a] + "   " + kelas[a] + "  " + hasilED);

            knn.put(hasilED, training.kelas[a]);
        }

        System.out.println("Ranking Euclidean Distance");

        Map knn_hasil = new TreeMap(knn);
        printMap(knn_hasil);

        System.out.println("");
        System.out.println("Hasil Keputusan : " + knn_hasil.values().toArray()[0]);
        return (String) knn_hasil.values().toArray()[0];
    }

    public static void printMap(Map map) {
        Set s = map.entrySet();
        Iterator it = s.iterator();
        int i = 0;
        while (it.hasNext()) {
            Map.Entry entry = (Map.Entry) it.next();
            Double key = (Double) entry.getKey();
            String value = (String) entry.getValue();
            ranking = ranking + "\n " + "Apel: " + i + " nilai: " + key + " => " + value;
            System.out.println(key + " => " + value);
            i++;
        }//while
        System.out.println("========================");
    }//printMap

    // membuat function untuk Jarak Euclidean
    static double jarakEuclidean(int R1, int R2, int G1, int G2) {
        return Math.sqrt(Math.pow(R1 - R2, 2) + Math.pow(G1 - G2, 2));
    }

}

Berikut class yang kedua

 
  import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;

/**
 *
 * @author CHARIS
 */
public class DataTraining {

    int[] NR = {5,4,9,6,10,9,3,5,9,2};
    int[] UN = {6,6,8,5,8,6,4,3,4,3};
    String[] kelas = {"REGULER", "REGULER", "BEASISWA","REGULER","BEASISWA","BEASISWA","TIDAK LULUS", "TIDAK LULUS","REGULER","TIDAK LULUS"};

}
  

Terakhir, class yang ketiga. Fokus kelas ini hanya untuk method main saja. Tujuannya untuk menjalankan dua class sebelumnya. 

 
  
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author ASUS
 */
public class KNN_Run {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        
        //Data Testing
        int nr= 6;
        int un= 9;

        KNN_Algoritma deteksi = new KNN_Algoritma();
        String hasil = null;
        
        hasil = deteksi.knn(nr,un);
    }
}
  

Sekarang tinggal run hasilnya:

Gambar 3. Running k-NN

Berdasarkan Gambar 3, diketahui bahwa data testing yang dientri adalah NR=3 dan UN=4. Lalu k-NN digunakan sebagai metode untuk memutuskan, apakah NR dan UN dengan nilai itu dapat diterima beasiswa, reguler atau malah tidak lulus. Ternyata k-NN memutuskan klafisikasi akhir TIDAK LULUS, mengacu ke data training. Kelemahan aplikasi tersebut adalah, hanya mampu memutuskan berdasarkan k=1 saja. Jadi, klasifikasi ditentukan oleh ranking euclidean tertinggi saja. 

Teman-teman bisa mengembangkannya dengan menerapkan Graphical User Interface (GUI). Contoh versi GUI, K-Nearest Neighbor Untuk Seleksi Penerimaan Mahasiswa Baru, seperti gambar berikut

Jika ada teman-teman yang belum paham, bisa kontak atau japri. Atau jika mau meminta source code lengkap beserta GUI-nya juga boleh. Silakan.