Algoritma k-nearest neighbor (k-NN atau KNN) merupakan sebuah algoritma untuk melakukan klasifikasi terhadap objek berdasarkan data pembelajaran yang jaraknya paling dekat dengan objek tersebut.

Ilustrasi dari metode yang digunakan oleh algoritma k-nn ditunjukkan pada gambar di bawah ini:

Berikut ini merupakan contoh aplikasi pemrograman matlab untuk mengklasifikasi citra digital berdasarkan pola bentuk menggunakan algoritma k-nearest neighbor.

Pada contoh ini k-nn digunakan untuk mengklasifikasi bentuk dari citra apel, tulang, gajah, dan garpu.

Ciri yang digunakan untuk membedakan keempat bentuk dari citra tersebut adalah eccentricity dan metric

Pemrograman matlab menggunakan algoritma k-nearest neighbor pada contoh ini dapat dijalankan minimal menggunakan matlab versi r2014a karena menggunakan fungsi baru yaitu fitcknn (fit k-nearest neighbor classifier)

Langkah-langkah pemrograman matlab untuk mengklasifikasikan bentuk suatu objek dalam citra digital yaitu:
1. Mempersiapkan citra untuk proses pelatihan. Pada proses tersebut digunakan 60 citra yang terdiri dari 15 citra apel, 15 citra tulang, 15 citra gajah, dan 15 citra garpu

2. Mempersiapkan citra untuk proses pengujian. Pada proses tersebut digunakan 20 citra yang terdiri dari 5 citra apel, 5 citra tulang, 5 citra gajah, dan 5 citra garpu

3. Setelah citra untuk proses pelatihan dan pengujian disiapkan, dilakukan pemrograman untuk kedua proses tersebut. Source code untuk mengklasifikasi bentuk suatu objek dalam citra digital menggunakan algoritma k-nearest neighbor adalah sebagai berikut:

clc;clear;close all;

image_folder = 'data latih';
filenames = dir(fullfile(image_folder, '*.gif'));
total_images = numel(filenames);

for n = 1:total_images
    full_name= fullfile(image_folder, filenames(n).name);
    our_images = logical(imread(full_name));
    our_images = bwconvhull(our_images,'objects');
    stats = regionprops(our_images,'Area','Perimeter','Eccentricity');
    area(n) = stats.Area;
    perimeter(n) = stats.Perimeter;
    metric(n) = 4*pi*area(n)/(perimeter(n).^2);
    eccentricity(n) = stats.Eccentricity;
    training = [metric;eccentricity]';
    
    group = cell(60,1);
    group(1:15,:) = {'tulang'};
    group(16:30,:) = {'apel'};
    group(31:45,:) = {'gajah'};
    group(46:60,:) = {'garpu'};
end

figure,
gscatter(metric',eccentricity',group,'rgbk','.',15)
legend('Tulang pelatihan','Apel pelatihan','Gajah pelatihan','Garpu pelatihan',...
    'Location','SouthWest')
grid on

image_folder_uji = 'data uji';
filenames_uji = dir(fullfile(image_folder_uji, '*.gif'));
total_images_uji = numel(filenames_uji);
for n = 1:total_images_uji
    full_name_uji = fullfile(image_folder_uji, filenames_uji(n).name);
    our_images_uji = logical(imread(full_name_uji));
    our_images_uji = bwconvhull(our_images_uji,'objects');
    stats_uji = regionprops(our_images_uji,'Area','Perimeter','Eccentricity');
    area_uji(n) = stats_uji.Area;
    perimeter_uji(n) = stats_uji.Perimeter;
    metric_uji(n) = (4*pi*area_uji(n))./(perimeter_uji(n).^2);
    eccentricity_uji(n) = stats_uji.Eccentricity;
    sample = [metric_uji;eccentricity_uji]';
end

c = fitcknn(training, group,'NumNeighbors',1,'Standardize',1);
Class = predict(c,sample);
figure,
gscatter(metric',eccentricity',group,'rgbk','.',15)
grid on
hold on
gscatter(metric_uji',eccentricity_uji',Class,[1 1 0; 1 0 1; 0 1 1; .5 .5 .5],'x',15);
legend('Tulang pelatihan','Apel pelatihan','Gajah pelatihan','Garpu pelatihan',...
    'Tulang pengujian','Garpu pengujian','Apel pengujian','Gajah pengujian',...
    'Location','SouthWest')
hold off

4. Sehingga pada proses pelatihan diperoleh hasil berupa grafik seperti pada gambar berikut

Pada grafik tersebut terlihat distribusi data (nilai metric dan ecentricity) pada masing-masing kelas grup (apel, tulang, gajah, garpu). Pada proses pengujian, suatu data uji dikatakan masuk ke dalam kelas grup apel apabila tetangga terdekat dari data uji tersebut dominan dengan kelas grup A

5. Pada proses pengujian dihasilkan grafik seperti pada gambar di bawah ini

8. Kelas keluaran yang dihasilkan dalam proses pengujian adalah sbb:

sehingga hasil perbandingan antara kelas keluaran dengan kelas target pada proses pengujian adalah:

Berdasarkan tabel di atas, tampak bahwa terdapat empat buah data uji yang diklasifikasikan ke dalam kelas yang salah (tidak sesuai dengan kelas target). Sehingga akurasi sistem dalam mengklasifikasikan bentuk objek adalah (16/20) x 100% = 80%. Nilai akurasi tersebut menunjukkan bahwa algoritma k-nearest neighbor cukup baik dalam mengklasifikasikan bentuk objek pada citra yang diberikan.

File source code lengkap beserta citra pada pemrograman matlab di atas dapat diperoleh melalui halaman berikut ini: Source Code

Save

Save

Save

Save