Data clustering merupakan salah satu metode data mining yang bersifat tanpa arahan (unsupervised).

Ada dua jenis data clustering yang sering digunakan dalam proses pengelompokan data yaitu hierarchical (hirarki) data clustering dan non-hierarchical (non hirarki) data clustering.

K-means merupakan salah satu metode data clustering non hirarki yang berusaha mempartisi data yang ada ke dalam satu atau lebih cluster/kelompok.

Metode ini mempartisi data ke dalam cluster/kelompok sehingga data yang memiliki karakteristik yang sama dikelompokkan ke dalam satu cluster yang sama dan data yang mempunyai karakteristik yang berbeda dikelompokkan ke dalam kelompok yang lain.

Ilustrasi algoritma k-means ditunjukkan pada gambar di bawah ini:

Algoritma untuk melakukan k-means clustering adalah sebagai berikut:
1. Tentukan jumlah kluster yang diinginkan (k)
2. Tentukan nilai centroids awal secara acak
3. Hitung jarak tiap data terhadap masing-masing centroid
4. Kelompokkan data-data tersebut ke kluster berdasarkan jarak paling dekat (minimum) terhadap sebuah kluster
5. Hitung ulang nilai centroids dengan menghitung nilai rerata (mean) data dari masing-masing kluster
6. Lakukan langkah 3-5 hingga nilai centroids tidak lagi mengalami perubahan

Perhitungan jarak antara centroid dengan data dapat dilakukan menggunakan persamaan euclidean distance, cityblock, cosine, correlation, maupun hamming.

Berikut ini merupakan contoh pemrograman matlab untuk melakukan teknik clustering pada pengenalan pola citra.

Pada contoh ini algoritma k-means digunakan untuk mengkluster 60 citra yang terdiri dari 20 citra kelelawar, 20 citra ikan, dan 20 citra katak seperti ditunjukkan pada gambar berikut:

Secara visual, berdasarkan bentuk objeknya, citra tersebut terbagi menjadi tiga kelompok yaitu kelelawar, ikan, dan katak.

Oleh sebab itu, pada contoh ini jumlah kluster yang digunakan dalam algoritma k-means adalah sebanyak tiga buah.

Sedangkan ciri yang digunakan untuk membedakan ketiga jenis citra tersebut adalah luas dan keliling.

Source code untuk melakukan klustering menggunakan algoritma k-means adalah sebagai berikut:

clc; clear; close all;

image_folder = 'Images Dataset';
filenames = dir(fullfile(image_folder, '*.gif'));
total_images = numel(filenames);

area = zeros(1,total_images);
perimeter = zeros(1,total_images);

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');
    our_images = bwareaopen(our_images,100);
    stats = regionprops(our_images,'All');
    area(n) = stats.Area;
    perimeter(n) = stats.Perimeter;
    X = [area;perimeter]';
end

opts = statset('Display','final');
[idx,C] = kmeans(X,3,'Distance','sqeuclidean',...
    'Replicates',5,'Options',opts);

figure;
plot(X(idx==1,1),X(idx==1,2),'r.','MarkerSize',24)
hold on
grid on
plot(X(idx==2,1),X(idx==2,2),'g.','MarkerSize',24)
plot(X(idx==3,1),X(idx==3,2),'b.','MarkerSize',24)
plot(C(:,1),C(:,2),'kx',...
    'MarkerSize',15,'LineWidth',3)
legend('Cluster 1','Cluster 2','Cluster 3','Centroids',...
    'Location','best')
title('Cluster Assignments and Centroids')
xlabel('Area')
ylabel('Perimeter')
hold off

Setelah koding tersebut dijalankan, maka akan menghasilkan grafik seperti pada gambar di bawah ini

Pada grafik tersebut tampak bahwa algoritma k-means telah berhasil mengelompokkan data luas (area) dan keliling (perimeter) menjadi tiga kluster.

Hasil dari pengelompokkan data tersebut ditunjukkan pada tabel berikut:

Tabel tersebut menunjukkan bahwa setiap data telah berhasil dikelompokkan ke dalam tiga kelas meskipun memang terdapat beberapa data yang tidak sesuai dengan kelas klusternya.

Akurasi yang dihasilkan pada proses klustering tersebut yaitu 45/60*100 = 75%.

Hal ini menunjukkan bahwa algoritma k-means cukup baik dalam mengelompokkan tiga jenis citra masukan yang diberikan.

Citra dan source code algoritma k-means untuk pengenalan pola citra dapat diperoleh pada halaman berikut ini: Source Code

Sedangkan materi mengenai algoritma k-means clustering dan naive bayes classifier untuk pengenalan pola tesktur dapat dilihat pada: Algoritma k-means clustering dan naive bayes classifier untuk pengenalan pola tesktur

Save

Save

Save

Save