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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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 ini: Source Code

Comments

  1. AnonymousDecember 3, 2017 at 12:34 AM

    nice share
    akan lebih baik jika mencantumkan sumber artikel dan mencantumkan ijin dari website aslinya

    ReplyDelete

Post a Comment

Popular posts from this blog

Algoritma K-Nearest Neighbor (KNN)

Image
Algoritma  K-Nearest Neighbor  (KNN) adalah sebuah metode untuk melakukan klasifikasi terhadap objek berdasarkan data pembelajaran yang jaraknya paling dekat dengan objek tersebut. Data pembelajaran diproyeksikan  k  ruang berdimensi banyak, dimana masing – masing dimensi merepresentasikan fitur dari data. Ruang ini dibagi menjadi bagian – bagian berdasarkan klasifikasi data pembelajaran. Sebuah titik pada ruangan ini ditandai dengan kelas c , jika kelas  c  merupakan klasifikasi yang paling banyak ditemui pada  k  buah tetangga terdekat titik tersebut. K-Nearest Neighbor  merupakan metode yang bersifat  supervised , dimana hasil dari  query instance  yang baru diklasifikasikan berdasarkan mayoritas kategori pada KNN.     Pada fase  training , algoritma ini hanya melakukan penyimpanan vektor – vektor fitur dan klasifikasi data  training sample . Pada fase klasifikasi, fitur – fitur yang sama dih...
Read more

Perhitungan K-Nearest Neighbor (KNN)

Image
K-Nearest Neighbor  (KNN) adalah suatu metode yang menggunakan algoritma  supervised  dimana hasil dari  query instance  yang baru diklasifikan berdasarkan mayoritas dari kategori pada KNN. Tujuan dari algoritma ini adalah mengklasifikasikan obyek baru bedasarkan atribut dan  training sample .  Classifier  tidak menggunakan model apapun untuk dicocokkan dan hanya berdasarkan pada memori. Diberikan titik  query,  akan ditemukan sejumlah  k  obyek atau (titik  training ) yang paling dekat dengan titik  query . Klasifikasi menggunakan  voting  terbanyak diantara klasifikasi dari k obyek.. algoritma KNN menggunakan klasifikasi ketetanggaan sebagai nilai prediksi dari  query instance  yang baru. Algoritma metode KNN sangatlah sederhana, bekerja berdasarkan jarak terpendek dari  query instance  ke  training sample  untuk menentukan KNN-nya.  Training sample  diproyeksika...
Read more