Friday, November 30, 2012

Clustering vs Classification

Diambil dari http://pengolahancitra.com, bahasanya enak dibaca, saya edit sedikit biar komplit.

Pengantar

Pada artikel singkat ini, kita akan membahas mengenai perbedaan antara clustering dan classification. Adalah penting untuk mengetahui perbedaan antara keduanya. Karena keduanya membawa pada pendekatan dan solusi yang berbeda.

Clustering
Secara formal clustering di definisikan sebagai suatu proses unsupervised untuk mengelompokan data yang memiliki karakteristik tertentu yang sama. 

Di Wikipedia, Cluster analysis atau clustering adalah pengelompokan object-object kedalam kelompok-kelompok (yang disebut cluster) sehingga object-object yang ada di dalam cluster yang sama lebih mirip satu dengan yang lain dibandingkan dengan cluster yang berbeda. 

Sederhananya seperti ini. Misalkan kita diberikan kelompok data, katakanlah data tinggi anak-anak pada sekolah SD. Katakanlah kita ingin mengelompokkan data-data ini kedalam 3 kelompok yang mana setiap kelompok memiliki tinggi yang kurang lebih sama. Problem tersebut dapat dikategorikan dalam clustering problem.

Pendekatan yang ada dalam Clustering
Ada banyak pendekatan yang ada dalam clustering. Salah satu yang paling terkenal adalah pendekatan k-means clustering. huruf K yang ada pada K-means berarti kita mengasumsikan bahwa kita mengetahui jumlah kelompok yang akan dihasilkan. 

Sederhananya algoritma ini adalah sebagai berikut. Kita asumsikan ada K kelompok. Katakanlah ada 3 kelompok. Lalu, kita tentukan secara acak 3 cluster centre. Lalu kelompokkan data-data kedalam kelompok yang memiliki jarak terpendek antara data tersebut dengan cluster centre. Selanjutnya, kalkulasikan centre baru pada setiap kelompok. Lakukan langkah tersebut hingga pusat kelompok tidak berubah. Mudah bukan?

Bagaimana kalau saya tidak mempunyai informasi mengenai jumlah kelompok yang mungkin terjadi? Ada caranya! yaitu dengan memakai leader-follower algorithm. Sederhananya, pendekatan ini memakai graph theory. Pertama2x kita pilih satu data menjadi cluster representation, selanjutnya, diberikan data yang lain, kita hitung jarak antara data tersebut dengan cluster representation yang ada. Jika jaraknya terlalu besar, maka data tersebut akan dikelompokkan dalam cluster yang baru. 

Dalam clustering, biasanya kita menghadapi jumlah data yang amat banyak. Nah! ada beberapa pendekatan, ada yang disebut offline clustering , ada yang disebut online clustering.  

Offline clustering artinya pendekatan tersebut tidak dapat digunakan dalam aplikasi real-time, mungkin saja prosesnya membutuhkan waktu 1 hari. Sebaliknya online clustering mungkin bisa memproses data dalam hitungan detik. Tentunya tidak ada makan siang yang gratis. Kita harus mengorbankan beberapa hal untuk mendapatkan keuntungan di hal yang lainnya.

Kalau diperhatikan, k-means clustering termasuk dalam offline clustering. Ini disebabkan pada setiap iterasi pendekatan ini memproses semua datanya. Jadi jika ada 1 juta data, setiap kali iterasi, ada 1 juta data yang di proses. Jika dibutuhkan sekitar 500 000 iterasi, artinya komputer akan memiliki beban sekitar 500 milyar komputasi.

Sebaliknya leader-follower algorithm dapat dikategorikan dalam online clustering. Dalam pendekatan ini, data yang sudah dikelompokkan tidak perlu diproses lagi. Dan dalam setiap iterasinya hanya akan memproses 1 data saja. Jadi kalau ada 1 juta data, komputer hanya akan memiliki beban 1 juta komputasi.

Classification
Berbeda dengan clustering, classification memiliki tujuan untuk mengklasifikasikan suatu data ke dalam kelompok kelas yang sudah ada. 

Sebagai contoh, misalkan diberikan sekelompok sampel darah orang. Kita sudah tau jumlah kelompok golongan darah. Maka tugas kita hanyalah menentukan suatu sampel darah masuk ke kelompok mana. Jadi intinya, tidak akan ada pembentukan kelompok baru. Dan biasanya prosesnya supervised. Dalam arti ada training yang dilakukan, dan dalam training tersebut, kita diberikan sekelompok sampel darah yang sudah diketahui masuk ke kelompok manakah sampel tersebut.

Pendekatan yang ada dalam classification
Ada banyak! contohnya adalah neural network. Dalam pendekatan ini, neural network dilatih dengan menggunakan data yang sudah diketahui masuk ke kelompok mana data tersebut. Setelah pelatihan, prosesnya cukup sederhana, yaitu dengan memasukkan data baru (yang tidak termasuk dalam data training) ke dalam neural network, lalu neural network akan memberikan informasi termasuk ke dalam kelompok manakah data baru tersebut.

Contoh lain adalah pendekatan K-nn (k nearest neighbour). Dalam hal ini setiap data baru akan dibandingkan dengan data training. Lalu 3 data training terdekat (misalkan kita ambil k = 3) dengan data baru akan diambil. Misalkan ketiga data tersebut masuk ke dalam kelompok 1, 2 dan 1, maka data baru tersebut dimasukan ke dalam kelompok 1 (seperti voting, karena suara yang terbanyak adalah 1, maka keputusannya adalah 1).

Ringkasan sedikit
Maka jelas, kalau clustering dipakai ketika kita tidak mengetahui bagaimana data harus dikelompokkan. Kita bisa mengasumsikan jumlah kelompok yang ada. Keluaran pendekatan ini adalah data yang sudah dikelompokkan. Di lain pihak, dalam classification, kita sudah mempunyai informasi mengenai bagaimana data tersebut dikelompokkan. Tugas kita hanyalah melakukan training pada sistem dengan data yang sudah diberikan label (ke dalam kelompok manakah data tersebut dikelompokkan), selanjutnya sistem akan mengklasifikasikan data-data yang baru ke dalam kelompok yang ada. Tidak akan ada pertambahan kelompok.

Baca Selengkapnya...

Tuesday, November 20, 2012

Image Enhancement vs Image Restoration


Acapkali dalam menghadapi permasalahan di pengolahan citra, kita berhadapan dengan citra yang mempunyai pengotor (noise). Dalam proses, kita ingin menghilangkan pengotor-pengotor tersebut. Ada dua macam teknik yang kita dapat lakukan, yaitu image enhancement dan image restoration. Apakah berbedaannya? Marilah kita lihat satu persatu.

Apa itu pengotor?
Noise atau pengotor citra biasanya didapat dari proses dijitasi citra. Apa itu proses dijitasi citra? ini adalah proses meng-capture objek di dunia nyata kedalam citra dijital. Bingung? Singkatnya, kalau kita memotret sesuatu dengan kamera dijital, sebenarnya kita sedang melakukan proses dijitasi citra. Nah... kadang-kadang lensa kamera kita kotor kan? jadi ada bintik-bintik di foto yang didapat. Bintik-bintik itu salah satu jenis pengotor. Sebenarnya ada banyak jenis pengotor. Jenis-jenis pengotor ini akan dibahas pada artikel terpisah. Untuk sementara, asumsikan bahwa pada proses "Pemotretan" (proses dijitasi citra), ada banyak hal yang menyebabkan citra tidak sempurna (memiliki pengotor). Oh ya, jenis pengotor yang lainnya adalah pengotor yang berasal dari hardware (cth: kamera yang setengah rusak).

Image Restoration
Teknik ini dipakai pada saat kita dapat memodelkan pengotor.
Pengotor dapat dimodelkan? Kenapa tidak?! Ada beberapa jenis pengotor yang dapat kita modelkan, misalkan pengotor yang berasal dari sensor yang kurang sempurna, pengotor yang berasal dari sinyal transmisi yang kurang baik sehingga pada saat transimisi data citra tidak diterima dengan baik. Salah satu contoh pengotor yang terkenal adalah salt-and-pepper noise (garam dan merica). Jenis pengotor ini didapatkan karena sensor yang kurang sempurna. Inilah salah satu contoh salt-and-pepper noise.


Perhatikan pada citra diatas, citra sebelah kiri adalah citra dengan pengotor salt-and-pepper, citra disebelah kanan adalah citra tanpa pengotor. Secara matematis, pengotor jenis ini dapat dimodelkan dengan memakai random variable yang ada pada ilmu probabilitas. Rumusnya adalah sebagai berikut.


Biasanya pengotor-pengotor dimodelkan secara matematis dengan menggunakan Probabilistic Density Function (PDF). Kenapa? Karena, noise itu random bukan? maksudnya, tidak dapat diterka, dimana dan kapan dia muncul. Namun demikian, kita dapat mengira-ngira kemungkinan suatu pengotor itu muncul. Nah ilmu mengira-ngira kemungkinan itu ada di ilmu probabilitas.

Lalu setelah kita mengetahui jenis pengotornya. Apa yang kita lakukan berikutnya? Wah gampang itu... biasanya kalau kita sudah tau jenis pengotornya, dan kita tau kalau jenis pengotor tersebut dapat dimodelkan. Hal berikutnya adalah mencari filter yang dapat menghilangkan noise tersebut. Contohnya, pada kasus salt-and-pepper noise , untuk menghilangkan noise tersebut secara sempurna adalah dengan menggunakan median filter. Dijamin mutu, pasti pengotornya akan hilang seketika.

Jadi esensi image restoration adalah ketika kita dapat memodelkan pengotor, dan pengotor tersebut sudah dikenal, kita tinggal menggunakan metode yang sudah ada untuk menghilangkan pengotor. Dan biasanya hasil image restoration cukup memuaskan. Kebanyakan hasilnya adalah, kita mendapatkan citra tanpa pengotor tersebut.

Image Enhancement

Teknik ini dipakai pada saat kita tidak dapat memodelkan pengotor. Biasanya proses ini dilakukan secara heuristic, alias coba-coba sampai puas. Kalau pada proses image restoration kita tau kapan saatnya berhenti, pada image enhancement penilaian subjektif sangat berpengaruh. Proses ini baru berhenti ketika kita merasa puas akan hasil yang didapatkan.

Ada banyak metode yang dapat dipakai pada image enhancement. Metode tersebut sebagian besar adalah berupa filter. Filter-filter  ini nantinya akan dikonvolusi dengan citra untuk mendapatkan hasil yang baik. Untuk proses filtering akan dibahas secara terpisah. Selain dengan menggunakan filter, ada metode-metode lain seperti transformasi, histogram, contrast-stretching, dan sebagainya. Contoh metode yang paling mudah adalah power-law transformation pada grey-level. Pada prinsipnya setiap nilai grey level pada pixel diganti dengan nilai hasil perhitungan formula tertentu. Bingung? Baik, marilah kita lihat formula power-law transformation ini.


n adalah nilai grey level yang baru, r adalah nilai grey level yang lama, s dan a ditentukan sesuai dengan selera. Misalkan pada koordinat (1,1), nilai grey-level untuk komponen red adalah 120. Maka, dengan s = 1 dan a = 0.5 nilai ini akan diganti menjadi 10.9. Kalau dilihat, proses ini akan membuat setiap nilai menuju nilai 0, alias membuat citra lebih gelap!. Ingin membuat lebih terang? Mudah, ubah a menjadi 1.2 alhasil, citra akan semakin terang.
Berikut ini adalah contoh dari power-law transformation.





Citra sebelah kiri adalah citra hasil power-law transformation dengan nilai peubah a 1.2, sebelah kanan adalah dengan nilai peubah 0.5. Yang mana yang lebih baik? Itu tergantung kebutuhan. Mungkin ada yang lebih memerlukan citra yang terang, atau mungkin ada yang lebih membutuhkan citra yang lebih gelap. 

Sebagai kesimpulan, kita dapat melihat perbedaan yang mendasar antara image restoration dan image enhancement. Image restoration adalah proses yang pasti, dan menghasilkan citra yang baik. Biasanya dapat dilakukan bila jenis pengotor dapat dimodelkan. Di lain pihak, image enhancement adalah proses heuristik yang sangat bergantung dari kebutuhan dari setiap kasus. Biasanya dipakai ketika pengotor tidak dapat dimodelkan.
Baca Selengkapnya...