k-Nearest Neighbor (k-NN) Menggunakan Matlab


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:

15890-thumb

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

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

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 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
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:

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 objek pada citra yang diberikan.

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

Save

Save

Save

Save

Posted on April 21, 2016, in Data mining, Pengenalan Pola, Pengolahan Citra and tagged , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , . Bookmark the permalink. 7 Comments.

  1. Mas kasih tau link download matlab yang versi 2014 seperti mas pake ini. Kalo bisa emailkan kesini mas alimamawar6@gmail.com

  2. siang mas mau tanya, metode apa yang cocok untuk menentukan ukuran dan bentuk, misalnya untuk menentukan mutiara berdasarkan bentuk dan ukuran dan sebagainya,

  3. terima kasih banyak mas, infonya sangat membantu

  4. malam mas, klo berbentuk citra gmna cara menentukan nilai k nya? apakah citranya harus diberikan nilai dulu?

  5. dalam algoritma k-nn, nilai k adalah jumlah tetangga terdekat dari nilai masukan yang diujikan

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: