k-Nearest Neighbor (k-NN)


Algoritma k-nearest neighbor (k-NN atau KNN) adalah sebuah metode untuk melakukan klasifikasi terhadap objek berdasarkan data pembelajaran yang jaraknya paling dekat dengan objek tersebut.  Ilustrasi dari metode yang digunakan oleh algoritma k-nn dalam mengklasifikasikan objek ditunjukkan pada gambar di bawah ini:

15890-thumb
Berikut ini merupakan contoh pemrograman matlab untuk mengklasifikasikan citra digital berdasarkan pola bentuknya. Pada contoh ini k-nn digunakan untuk mengklasifikasikan bentuk dari citra apel, tulang, gajah, dan garpu. Ciri yang digunakan untuk membedakan keempat bentuk dari citra tersebut adalah eccentricity dan metric (materi mengenai ekstraksi ciri dapat dilihat pada laman berikut: link). 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
data latih

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
data uji

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

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
pelatihan

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
pengujian

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

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

kelas keluaran

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 suatu objek dalam citra digital

Source code algoritma k-nearest neighbor untuk mengklasifikasikan bentuk suatu objek dalam citra digital dapat diunduh pada laman berikut: link

  1. selamat malam mas.
    sya mau nnyak, disini kan mas untuk proses pengklasifikasiannya menggunakan function matlab bawaannya yaitu fitcknn(training, group,’NumNeighbors’,1,’Standardize’,1);. nah mas kira2 bsa gak kita melakukan klasifikasix dibuat tanpa menggunakan function dari matlabx ???
    terima kasih sebelumnya mas.

  2. Selamat malam mas mau nanya lagi nih .,.

    Boleh kah di kombinasikan antara algoritma knn dengan Neural Network Backprop ??

    Mohon penjelasannya kanda ….

  3. bisa minta no Tlpnya

  4. mas minta nomor Tlpnya??

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: