6 BAB 2 LANDASAN TEORI
Pada bab ini diuraikan beberapa landasan teori yang mendukung penulisan ini, seperti teori-teori Computer Vision, teori-teori Gray Level Co-occurremce Matrix dan lain-lain:
2.1.
Intelegensia Semu Istilah kecerdasan buatan sebenarnya berasal dari bahasa Inggris: “Artificial
Intelligence”. Jika diartikan tiap kata, artificial artinya buatan, sedangkan intelligence adalah kata sifat yang berarti cerdas. Jadi artificial intelligence maksudnya adalah sesuatu buatan atau suatu tiruan yang cerdas. Cerdas di sini kemungkinan maksudnya adalah kepandaian atau ketajaman dalam berpikir, seperti halnya otak manusia dalam menyelesaikan suatu masalah (http://kampustembalang.web.id/2007/06/03/kecerdasanbuatan/). Kecerdasan
buatan
(Artificial
Intelligence)
didefinisikan
sebagai
(
http://id.wikipedia.org/wiki/Artificial_intelligence) kecerdasan yang ditunjukkan oleh suatu entitas buatan. Sistem seperti ini umumnya dianggap sebagai komputer. Kecerdasan diciptakan dan dimasukkan kedalam suatu mesin (komputer) agar dapat melakukan pekerjaan seperti yang dapat dilakukan manusia. Kecerdasan buatan ini bukan hanya ingin mengerti apa itu sistem kecerdasan, tapi juga mengkonstruksinya. Tidak ada definisi yang memuaskan untuk kecerdasan. Definisi untuk kecerdasan yang berlaku saat ini :
Kecerdasan : Kemampuan untuk memperoleh pengetahuan dan menggunakannya.
7
Atau kecerdasan: Apa yang diukur oleh sebuah ‘Test Kecerdasan’.
2.1.1 Latar Belakang Pada awal diciptakannya, computer hanya difungsikan sebagai alat komputasi belaka. Seiring dengan perkembangan waktu, penggunaan komputer semakin mendominasi kehidupan manusia sehingga computer tidak hanya digunakan sebagai alat hitung saja, tetapi lebih dari itu yaitu menggantikan beberapa pekerjaan yang biasanya dilakukan oleh manusia (http://firman-its.com/?pilih=news&aksi=lihat&id=54). Manusia menjadi pintar dalam menyelesaikan segala permasalahan yang dihadapi karena manusia mempunyai pengetahuan dan pengalaman. Pengetahuan didapatkan dari proses belajar, pengalaman didapatkan karena perjalanan waktu dan kehidupan yang dialami oleh manusia. Semakin banyak bekal pengetahuan dan pengalaman yang dimiliki oleh seseorang, diharapkan orang tersebut lebih mampu menyelesaikan masalah yang dihadapinya. Namun bekal pengetahuan saja tidak cukup, manusia juga diberikan akal untuk melakukan penalaran, mengambil kesimpulan berdasarkan pengetahuan dan pengalaman yang dimilikinya. Tanpa memiliki kemampuan penalaran yang baik, tidak ada artinya manusia itu memiliki pengetahuan dan pengalaman sebanyak apapun. Demikian juga sebaliknya, walaupun seorang manusia memiliki kemampuan penalaran yang baik, namun tanpa bekal pengetahuan dan pengalaman yang memadai, manusia juga tidak dapat menyelesaikan masalahnya dengan baik. Agar komputer bisa bertindak seperti dan sebaik manusia, maka komputer juga harus diberi bekal pengetahuan dan diberikan kemampuan untuk menalar. Untuk itu, artificial intelligence akan mencoba untuk memberikan beberapa metode untuk
8 membekali computer dengan kedua komponen tersebut agar computer bisa menjadi mesin yang cerdas. 2.1.2 Definisi Menyatakan komputer itu cerdas tentu tergantung sudut pandang dari orang yang memanfaatkan computer tersebut. Karena itulah sangat sulit untuk mendefinisikan dengan pasti apa yang dimaksud dengan kecerdasan buatan itu (http://firmanits.com/?pilih=news&aksi=lihat&id=54). Menurut John McCarthy, 1965, Artificial Intelligence adalah untuk mengetahui dan memodelkan proses – proses berpikir manusia dan mendesain mesin agar dapat menirukan perilaku manusia. Menurut Russell dan Norvig (2003, p5) definisi tentang kecerdasan buatan dikembangkan berdasarkan empat kelompok kategori, yaitu :
Sistem yang berpikir selayaknya manusia berfikir (thinking humanly).
Sistem yang bertindak selayaknya manusia bertindak (acting humanly).
Sistem yang berpikir secara rasional (thinking rationally).
Sistem yang bertindak secara rasional (actingt rationally). Dari keempat perspektif diatas, pengertian kecerdasan buatan dapat dipandang
dari
berbagai
sudut
pandang,
antara
lain
(http://firman-
its.com/?pilih=news&aksi=lihat&id=54) :
Sudut pandang kecerdasan Kecerdasan buatan akan membuat mesin menjadi cerdas, yaitu mampu berbuat seperti apa yang dilakukan oleh manusia.
9
Sudut pandang penelitian Kecerdasan buatan adalah suatu studi bagaimana membuat mesin atau computer dapat melakukan sesuatu sebaik yang dikerjakan oleh manusia. Ada beberapa bidang (domain) yang sering dibahas oleh para peneliti meliputi: a. Mundane Task
Persepsi (vision & speech)
Bahasa alami (understanding, generation & translation)
Pemikiran yang bersifat commonsense
Robot kontrol
b. Formal Task
Games / permainan
Matematika (geometri, logika, kalkulus integral, pembuktian)
c. Expert Task
Analisis finansial
Analisis medikal
Analisis ilmu pengetahuan
Rekayasa (desain, pencarian kegagalan, perencanaan manufaktur)
Sudut pandang bisnis Kecerdasan buatan adalah sekumpulan peralatan (tools) yang sangat powerfull dan metodelogis dalam menyelesaikan masalah bisnis.
Sudut pandang pemrograman Kecerdasan buatan meliputi studi tentang pemrograman simbolik, penyelesaian masalah (problem solving) dan pencarian (searching).
10 Untuk melakukan aplikasi kecerdasan buatan ada dua bagian utama yang sangat dibutuhkan, yaitu (Sri Kusumadewi, 2003, p4):
Basis Pengetahuan (Knowledge Base) Berisi fakta – fakta, teori, pemikiran dan hubungan antara satu dengan yang lainnya.
Motor Inferensi (Inference Engine) Yaitu kemampuan menarik kesimpulan berdasarkan pengalaman.
Gambar 2.1, Penerapan Konsep Kecerdasaan Buatan di Komputer 2.1.3 Sejarah Intelegensia semu merupakan inovasi baru di bidang ilmu pengetahuan. Mulai ada
sejak
muncul
computer
modern,
yakni
pada
1940
dan
1950
(
http://www.komputasi.lipi.go.id/utama.cgi?cetakartikel&1130607775). Dalam literatur, orang pertama yang dianggap sebagai pionir dalam mengembangkan mesin cerdas (intelligence machine) adalah Alan Turing, seorang matematikawan asal Inggris yang memulai karir saintifiknya di awal tahun 1930-an. Di tahun 1937 ia menulis paper tentang konsep mesin universal (universal machine). Kemudian, selama perang dunia ke-2 ia dikenal sebagai pemain kunci dalam penciptaan Enigma, sebuah mesin encoding milik militer Jerman. Setelah perang, Turing membuat automatic computing engine. Ia dikenal juga sebagai pencipta pertama program komputer untuk bermain catur, yang kemudian program ini dikembangkan dan dimainkan di komputer milik Manchester
11 University. Karya-karyanya ini, yang kemudian dikenal sebagai Turing Machine, dewasa
ini
masih
dapat
ditemukan
aplikasi-aplikasinya
(http://lecturer.eepis-
its.edu/~epit/modules.php?name=News&file=article&sid=20). Beliau melakukan percobaan Turing (Turing Test) yaitu sebuah komputer melalui terminalnya ditempatkan pada jarak jauh. Di ujung yang satu ada terminal dengan software AI dan diujung lain ada sebuah terminal dengan seorang operator. Operator itu tidak mengetahui kalau di ujung terminal lain dipasang software AI. Mereka berkomunikasi dimana terminal di ujung memberikan respon terhadap serangkaian pertanyaan yang diajukan oleh operator. Dan sang operator itu mengira bahwa ia sedang berkomunikasi dengan operator lainnya yang berada pada terminal lain. Turing beranggapan bahwa jika mesin dapat membuat seseorang percaya bahwa dirinya mampu berkomunikasi dengan orang lain, maka dapat dikatakan bahwa mesin tersebut cerdas (seperti layaknya manusia) (http://idhaclassroom.com/download/KecerdasanBuatan/Kecerdasan%20buatan.pdf). Beberapa tulisannya yang berkaitan dengan prediksi perkembangan komputer di masa
datang
akhirnya
juga
ada
yang
terbukti
its.edu/~epit/modules.php?name=News&file=article&sid=20).
(http://lecturer.eepisMisalnya
tentang
ramalannya bahwa di tahun 2000-an komputer akan mampu melakukan percakapan dengan manusia. Meski tidak ditemukan dalam paper-papernya tentang istilah resmi artificial intelligence, namun para peneliti di bidang ini sepakat untuk menobatkan Turing sebagai orang pertama yang mengembangkan kecerdasan buatan . Secara ilmu pengetahuan, istilah kecerdasan buatan untuk selanjutnya disebut sebagai AI (artificial intelligence), pertama kali diperkenalkan oleh Warren McCulloch, seorang filsuf dan ahli perobatan dari Columbia University, dan Walter Pitts, seorang
12 matematikawan muda pada tahun 1943, (Negnevitsky, 2004). Mereka mengajukan suatu teori tentang jaringan saraf tiruan (artificial neural network) untuk selanjutnya disebut sebagai ANN, bahwa setiap neuron dapat dipostulasikan dalam dua keadaan biner, yaitu ON dan OFF. Mereka mencoba menstimulasi model neuron ini secara teori dan eksperimen di laboratorium. Dari percobaan, telah didemonstrasikan bahwa model jaringan saraf yang mereka ajukan mempunyai kemiripan dengan mesin Turing, dan setiap fungsi perhitungan dapat diselesaikan melalui jaringan neuron yang mereka modelkan. Pentingnya kecerdasan buatan menjadi nyata bagi negara-negara yang berperan sejak tahun 1970. Para pemimpin negara yang mengakui potensialnya kecerdasan buatan mengharap
mendapat
persetujuan
jangka
panjang
(
http://www.komputasi.lipi.go.id/utama.cgi?cetakartikel&1130607775) untuk sumbersumber yang memerlukan dana intensif. Awalnya, kecerdasan buatan hanya ada di universitas-universitas dan laboratorium penelitian, dan hanya sedikit produk yang dihasilkan dan dikembangkan. Menjelang akhir 1970-an dan 1980-an, mulai dikembangkan secara penuh dan hasilnya berangsur-angsur dipublikasikan di khalayak umum. 2.1.4 Tujuan Adapun
tujuan
Intelegensia
Semu
adalah
sebagai
berikut
(
http://library.gunadarma.ac.id/files/disk1/9/jbptgunadarma-gdl-course-2005-timpengaja416-penganta-a.doc):
Untuk mengembangkan metode dan sistem untuk menyelesaikan masalah,masalah yang biasa diselesaikan melalui aktifivitas intelektual manusia, misalnya pengolahan
13 citra, perencanaan, peramalan dan lain-lain, meningkatkan kinerja sistem informasi yang berbasis komputer.
Untuk meningkatkan pengertian/pemahaman kita pada bagaimana otak manusia bekerja
2.1.5 Beda Intelegensia Semu dan Kecerdasan Alami Berikut
perbedaannya.
(http://idhaclassroom.com/download/Kecerdasan-
Buatan/Kecerdasan%20buatan.pdf) Kelebihan kecerdasan buatan :
Lebih bersifat permanent Kecerdasan alami bisa berubah karena sifat manusia pelupa. Kecerdasan buatan tidak berubah selama system computer dan program tidak mengubahnya.
Lebih mudah diduplikasi dan disebarkan Mentransfer pengetahuan manusia dari 1 orang ke orang lain membutuhkan proses yang sangat lama dan keahlian tidak akan pernah dapat diduplikasi dengan lengkap. Jadi jika pengetahuan terletak pada suatu system computer, pengetahuan tersebut dapat disalin dari computer dan dapat dengan mudah dipindahkan ke computer yang lain
Lebih murah Menyediakan layanan computer akan lebih mudah dan murah dibandingkan mendatangkan seseorang untuk mengerjakan sejumlah pekerjaan dalam jangka waktu yang sangat lama.
Bersifat konsisten karena kecerdasan buatan adalah bagian dari teknologi computer sedangkan kecerdasan alami senantiasa berubah – ubah.
14
Dapat didokumentasi Keputusan yang dibuat computer dapat didokumentasi dengan mudah dengan cara melacak setiap aktivitas dari system tersebut. Kecerdasan alami sangat sulit direproduksi.
Lebih cepat
Lebih baik Kelebihan kecerdasan alami :
Kreatif : manusia memiliki kemampuan untuk menambah pengetahuan, sedangkan pada kecerdasan buatan untuk menambah pengetahuan harus dilakukan melalui system yang dibangun
Memungkinkan orang untuk menggunakan pengalaman secara langsung. Sedangkan pada kecerdasan buatan harus bekerja dengan input – input simbolik.
Pemikiran manusia dapat digunakan secara luas, sedangkan kecerdasan buatan sangat terbatas.
2.1.6 Komputasi Kecerdasan Buatan dan Komputasi Konvensional Seperti telah dikatakan sebelumnya, bahwa pada awal diciptakannya, komputer hanya di peruntukan sebagai alat hitung (komputasi konvensional). Untuk itu, ada beberapa perbedaan antara komputasi yang dilakukan pada kecerdasan buatan dengan komputasi konvensional tersebut. Perbedaan komputasi kecerdasan buatan dengan komputasi konvensional terlihat seperti tabel dibawah ini (Sri Kusumadewi, 2003, p4),
15 Pemrograman Dimensi
Kecerdasan Buatan Konvensional Mengandung konsep-
Pemrosesan
konsep simbolik
Algoritmik
Sifat Input
Bisa tidak lengkap
Harus lengkap
Kebanyakan bersifat
Biasanya didasarkan
heuristik
pada algoritma
Pencarian
Biasanaya tidak Keterangan
Disediakan
disediakan
Fokus
Pengetahuan
Data dan Informasi Kontrol terintegrasi
Kontrol dipisahkan dari
dengan informasi
Struktur
pengetahuan
(data)
Sifat Output
Kuantitatif
Kualitatif
Relatif mudah
Sulit
Ya
Tidak
Pemeliharaan dan Update Kemampuan menalar
Tabel 2.1, Kecerdasarn Buatan Vs. Pemrograman Konvensional. 2.1.7 Lingkup Kecerdasan Buatan pada Aplikasi Komersial Makin pesatnya perkembangan teknologi menyebabkan adanya perkembangan dan perluasan lingkup yang membutuhkan kehadiran kecerdasan buatan. Karakteristik ’cerdas’ sudah mulai dibutuhkan diberbagai disiplin ilmu dan teknologi. Kecerdasan
16 buatan tidak hanya dominan di bidang ilmu komputer (informatika), namun juga sudah merambah di berbagai disiplin ilmu yang lain. Irisan antara psikologi dan kecerdasan buatan melahirkan sebuah area yang dikenal dengan nama cognition dan psycolinguistics. Irisan antara teknik elektro dengan kecerdasan buatan melahirkan berbagai ilmu seperti: pengolahan citra, teori kendali, pengenalan pola dan robotika. Dewasa ini, kecerdasan buatan juga memberikan kontribusi yang cukup besar di bidang manajemen. Adanya sistem pendukung keputusan, dan Sistem Informasi Manajemen juga tidak terlepas dari andil kecerdasan buatan. Adanya irisan penggunaan kecerdasan buatan di berbagai disiplin ilmu tersebut menyebabkan cukup rumitnya untuk mengklasifikasikan kecerdasan buatan menurut disiplin ilmu yang menggunakannya. Untuk memudahkan hal tersebut, maka pengklasifikasian lingkup kecerdasan buatan didasarkan pada output yang diberikan yaitu pada aplikasi komersial (meskipun sebenarnya kecerdasan buatan itu sendiri bukan meruapakan medan komersial). Lingkup utama dalam kecerdasan buatan adalah (Sri Kusumadewi, 2003, p6): 1. Sistem Pakar (Expert System). Disini komputer digunakan sebagai sarana untuk menyimpan pengetahuan para pakar. Dengan demikian komputer akan memiliki keahlian untuk menyelesaikan permasalahan dengan meniru keahlian yang dimiliki oleh pakar. 2. Pengolahan Bahasa Alami (Natural Language Processing). Dengan pengolahan bahasa alami ini diharapkan user dapat berkomunikasi dengan komputer dengan menggunakan bahasa sehari-hari.
17 3. Pengenalan Ucapan (Speech Recognition). Melalui pengenalan ucapan diharapkan
manusia
dapat
berkomunikasi
dengan
komputer
dengan
menggunakan suara. 4. Robotika dan Sistem Sensor (Robotics dan Sensory Systems). 5. Computer Vision, mencoba untuk dapat menginterpretasikan gambar atau objekobjek tampak melalui komputer. 6. Intelligent Computer-aided Instruction. Komputer dapat digunakan sebagai tutor yang dapat melatih dan mengajar. 7. Game Playing. Berbagai karakteristik yang ada pada sistem yang menggunakan artificial intelligence adalah pemrogramannya yang cenderung bersifat simbolik ketimbang algoritmik, bisa mengakomodasi input yang tidak lengkap, bisa melakukan inferensi, dan adanya pemisahan antara kontrol dengan pengetahuan. Namun, seiring dengan perkembagan teknologi, muncul beberapa teknologi yang juga bertujuan untuk membuat agar komputer menjadi cerdas sehingga dapat menirukan kerja manusia sehari-hari. Teknologi ini juga mampu mengakomodasi adanya ketidakpastian dan ketidaktepatan data input. Dengan didasari pada teori himpunan, maka pada tahun 1965 muncul Logika Fuzzy. Kemudian pada tahun 1975 John Holland mengatakan bahwa setiap problem berbentuk adaptasi (alami maupun buatan) secara umum dapat diformulasikan dalam terminologi genetika. Algoritma genetika ini merupakan simulasi proses evolusi Darwin dan operasi genetika atas kromosom.
18 2.2
Computer Vision Computer vision adalah sebuah ilmu dan teknologi dimana sebuah mesin dapat
melihat. (Anomymous, 2007, Wikipedia). Computer vision sering juga disebut dengan machine vision. Dimana computer vision merupakan cabang dari sebuah AI. Sistem computer vision ialah mengambil informasi – informasi yang penting dari sebuah citra proyeksi 2D. (Jain, Kasturi, G. Schunk, 1995, p1). Computer vision digunakan untuk mendapatkan keputusan-keputusan yang tepat tentang objek-objek didunia nyata dan citra yang kita lihat. Segmentasi dokumen merupakan salah satu contoh dari penerapan computer vision.
2.3
Soft Computing Dalam beberapa dekade terakhir, perkembangan sistem proses informasi di
dalam model kotak hitam, telah membuat prospek evolusi ilmiah menuju kepada perkembangan sistem kecerdasan, dengan memungkinkan dibuat model-model dari fenomena alam secara otomatis oleh mereka sendiri, dan pada akhirnya perumusan mereka merupakan hukum-hukum fisik di dalam batas hubungan-hubungan yang abstrak. Sistem kecerdasan pada dasarnya merupakan suatu sistem yang berusaha meniru cara berfikir manusia. Peniruan cara berfikir tersebut terdiri atas dua bagian yaitu peniruan
proses
berfikir
dan
peniruan
proses
komputasi
http://jurnalft.brawijaya.ac.id/?hlm=jfull&edisi=1101834000&idj=1118626681)
( .
Pengembangan suatu sistem yang memiliki kecerdasan komputasional dikenal dengan istilah soft computing. Soft computing berusaha untuk mengintegrasikan beberapa paradigma model perhitungan meliputi artificial neural network, fuzzy logic dan genetic algorithms.
19 2.3.1 Pengertian Soft Computing adalah kumpulan teknik – teknik perhitungan dalam ilmu komputer, inteligensia semu, machine learning dan beberapa disiplin ilmu teknik lainnya, yang berusaha untuk mempelajari, memodelkan, dan menganalisa fenomena yang sangat rumit : untuk metoda yang lebih konvensional yang tidak memberikan biaya rendah, analitis dan solusi lengkap (http://en.wikipedia.org/wiki/Soft_computing). Soft Computing adalah segolongan metoda yang mampu mengolah data dengan baik walaupun didalamnya terdapat ketidakpastian, ketidakakuratan maupun kebenaran parsial (Prof. Lotfi A Zadeh, 1992). 2.3.2 Sejarah Istilah
soft
computing
dicetus
pertama
kali
pada
tahun
1990
(
http://www.komputasi.lipi.go.id/utama.cgi?bacaforum&berita&1106541628&4) sehubungan dengan ide untuk mendirikan BISC (Berkeley Initiative in Soft Computer) oleh Prof. L.A.Zadeh dari Berkeley University. Soft computing, berbeda dengan conventional (hard) computing, memungkinkan toleransi terhadap input, proses dan output yang bersifat tidak akurat(imprecision), tidak pasti (uncertainty) dan setengah benar (partial truth). 2.3.3 Soft Computing sebagai Solusi Metoda
soft
bielefeld.de/~made/artikel/softcomp/)
computing menempati
(http://nakula.rvs.uniposisi
yang
menarik
dalam
perkembangan metoda komputasi dan pemecahan masalah pada saat ini. Hal ini karena ditawarkan solusi yang menarik dan kemudahan implementasi dari metoda ini untuk memecahkan masalah-masalah yang tadinya sangat sulit dipecahkan dengan komputer dengan menggunakan metoda komputasi konvensional.
20 Dengan adanya toleransi terhadap imprecision, uncertainty dan partial truth, diharapkan
akan
dapat
menciptakan
suatu
system
yang
(
http://www.komputasi.lipi.go.id/utama.cgi?bacaforum&berita&1106541628&4) cerdas (intelligent systems), handal (robustness), mudah diproses atau dijalankan (tractability) dan membutuhkan biaya yang lebih murah (low solution cost). Karakteristik ini ( http://asnugroho.net/papers/sriti2007.pdf) menempatkan soft computing sebagai salah satu solusi yang dapat digunakan untuk memecahkan berbagai masalah yang terdapat pada domain dunia nyata (real-world domain). Disekeliling kita terdapat banyak contoh dari berbagai masalah
yang
berkarakteristik demikian, antara lain : -
bagaimana kita mampu membaca berbagai macam corak tulisan tangan, atau bahkan pada tulisan itu ada sebagian yang terhapus
-
bagaimana membuat AC agar mengatur sendiri suhunya secara otomatis, sehingga udara didalam ruangan terasa nyaman
-
bagaimana mengenali sesorang, padahal tidak seluruh wajahnya dapat terlihat Solusi berbagai masalah yang terdapat pada domain ini tidak mudah dihitung
dengan berbagai model analitik yang ada. Diperlukan solusi yang seolah memiliki kecerdasan sehingga mampu menyelesaikan masalah – masalah yang sedemikian kompleks itu. Disinilah soft computing menjadi suatu solusi atas permasalahan tersebut. Metoda soft computing diinspirasikan oleh cara manusia memecahkan suatu masalah (http://nakula.rvs.uni-bielefeld.de/~made/artikel/softcomp/). Namun pendekatan soft computing ini berbeda dengan metoda Artificial Intelligence yang menggunakan pendekatan simbolik. Pada pendekatan simbolik yang bertumpu pada Physical Symbol System (PSS), jawaban suatu masalah harus berdasarkan dari keadaan yang konsisten
21 dari data yang ada (Newel and Simon, 1976) karena Physical Symbol System tak dapat memberikan solusi bila keadaan chaos. Dengan kata lain knowledge base yang menjadi basis dari pencarian solusi harus bersifat koheren, konsisten, dan reasonable (Delgrande and Mylopulos, 1986). Pada sistem konvensional, jawaban akan diberikan apabila seluruh syarat dari permasalahan terpenuhi. Ini menyebabkan sebagian besar dari pendekatan simbolik akan berakhir pada sistem yang bersifat semi-decidable. Sistem tidak akan memberikan jawaban bila seluruh kondisi yang diketahui tidak dipenuhi. Bila keadaan tidak terpenuhi, atau jawaban tidak tertemukan sistem ini akan memberikan jawaban yang bersifat negatif, sifat inilah yang dikenal dengan sifat semi-decidable dari sistem ini. 2.3.4 Pencarian Solusi dengan Metoda Soft Computing Metoda soft computing, tidak menggunakan satu algoritma yang pasti untuk memecahkan suatu masalah. Suatu teknik hanyalah mendeskripsikan interaksi antar sub sistem, bukanlah langkah pemecahan permasalahan secara detail. Sehingga dapat dilukiskan pemecahan menggunakan diagram sebagai berikut (http://nakula.rvs.unibielefeld.de/~made/artikel/softcomp/) :
Gambar 2.2, Pemecahan masalah dengan Soft Computing
22 Pada problem space, untuk problem yang ingin dipecahkan, telah diketahui contoh penyelesaian, yang biasanya dilakukan oleh human. Informasi yang bersifat pemetaan dari masalah ke solusi inilah yang akan diberikan kepada perangkat soft computing. Dengan memberikan sistem secara terus menerus melalui proses pelatihan maupun optimasi, solusi untuk seluruh problem space dapat ditemukan. Jadi dalam perancangan sistem, tidak pernah didefinisikan bagaimana solusi tersebut dicapai, yang ada hanyalah contoh-contoh, ataupun aturan-aturan kecil dari sistem tersebut. 2.3.5 Metoda Soft Computing Mengacu pada definisi yang diberikan oleh Zadeh, metoda – metoda dalam soft computing
dapat
dikategorikan
ke
dalam
tiga
kategori
besar
(
http://asnugroho.net/papers/sriti2007.pdf) : o Fuzzy Logic o Artificial Neural Network o Probabilistic Reasoning Kemudian ditambah dengan : o Genetic Algorithm o Evolutionary Computation o Belief Network o Chaos Theory Metoda – metoda ini sebenarnya bukanlah sesuatu yang baru yang diadakan setelah
konsep
soft
computing
yang
dirumuskan
(
http://asnugroho.net/papers/sriti2007.pdf). Yang terjadi justru sebaliknya. Metoda – metoda Fuzzy Logic, Artificial Neural Network, Probabilistic Reasoning maupun Genetic Algorithm telah ada lebih dahulu. Fuzzy Logic telah berkembang sejak tahun
23 1965. Konsep – konsep dasar Neural Network telah digali sejak tahun 1940an. Demikian halnya dengan Probabilistic Reasoning dan Genetic Algorithm yang bukan merupakan hal baru. Oleh karena itu, Zadeh menyebut soft computing sebagai reinkarnasi dari metoda – metoda diatas. Walaupun semua konsep dan teori diatas adalah untuk memproses system dan menyelesaikan masalah yang bersifat uncertainty, keberadaan semua konsep dan teori tersebut seharusnya tidak dilihat sebagai suatu persaingan (competitive) tetapi lebih dilihat sebagai saling melengkapi (complementary). Tidak ada satu konsep atau teoripun yang bersifat perfect, powerful, dan general untuk menyelesaikan semua masalah dalam real-world application, sehingga penggunaan suatu konsep atau teori bergantung dan disesuaikan dengan jenis dan karakteristik dari permasalahan dan aplikasinya. Bahkan, untuk dapat membentuk suatu complicated system yang cerdas (intelligent system), harus diperlukan suatu hybrid system melalui penggabungan beberapa konsep dan teori ( http://www.petra.ac.id/~puslit/statics/index.php?lang=ENG&pageid=PG-2005100033&staticid=3) dari soft computing . Lebih lanjut lagi, dalam konsep soft computing, metoda – metoda ini ibarat pilar , slaing mendukung dan bekerjasama dalam memecahkan suatu permasalahan. Keunggulan yang diperoleh dari kerjasama metoda – metoda itu lebih ditekankan daripada keunggulan individual salah satu daripadanya. Kekurangan satu metoda akan ditutup dengan kelebihan metoda lainnya. Keunggulan satu metoda disumbangkan, sehingga segi – segi positif dari metode yang ada tersebut dapat dimanfaatkan secara optimal.
24 2.3.6 Tujuan Soft Computing Tujuan soft computing adalah terbentuknya High Machine Intelligence Quotient (HMIQ), suatu system yang mampu mengolah informasi seperti cara berpikir manusia, mempunyai kemampuan untuk menyelesaikan permasalahan non-linier dan tidak ada model matematisnya (tractability), serta dapat diimplementasikan dengan biaya rendah ( http://soft-computing.org/). Adapun tujuan metode soft computing adalah : a.
Non-linearitas
dan
kompleksitas
problema.
Kemampuan
menyelesaikan
problematika yang sulit dan tidak bisa diselesaikan dengan metoda biasa b.
Kemampuan memanipulir parameter yang tidak pasti ( sesuatu yang tidak bisa diukur secara pasti, misalnya mengukur kadar cinta )
c.
Kemampuan men-generalisir solusi
d.
pengerjaan kasus regresi linier dengan teknologi ini daripada dengan fuzzy logic.
e.
Kemampuan mengatasi keterbatasan data, misalnya pada dunia statistic.
2.3.7 Aplikasi Soft Computing Dalam bidang sains dan engineering, metoda soft computing ini telah banyak diaplikasikan, misal pada sistem kendali, komunikasi, pengenalan pola dan lain lain. Pada bidang bisnis, metoda ini telah mulai diterapkan dengan luas. Beberapa aplikasi yang dominan antara lain (http://nakula.rvs.uni-bielefeld.de/~made/artikel/softcomp/) : a. Modelling Pendekatan fuzzy, yang dikenal sebagai Fuzzy Cognitive Map (FCM), pendekatan ini menyediakan suatu sarana untuk menganalisa sistem sosial dan ekonomi,
25 dengan lebih baik (Kosko, 1993; Taber, 1994). Karena perangkat analisa ini tidak membutuhkan masukan yang bersifat kuantitatif, dan perangkat analisis ini bersifat dinamis. Penggunaan Fuzzy Logic lainnya adalah Qualitative Modelling (Sugeno dan Yasukawa, 1993) yang telah diaplikasikan untuk memprediksi stock. b. Prediksi stock market Dengan menggunakan metoda ANN dengan arsitektur back propagation (Blum, 1992; Srirengan & Looi, 1991) disusun suatu sistem untuk memprediksikan nilai stock di masa yang akan datang. Sistem ini menghasilkan prediksi persentase perubahan pada harga saham di masa yang akan datang. Sebagai masukan dari sistem ini adalah :
Previous price fluctuation Dinyatakan dalam persentasi perubahan harga pada minggu sebelumnya. Hal ini disebabkan perubahan harga stock pada minggu sebelumnya akan mempengaruhi perubahan harga di minggu yang akan dating.
Volume and volatility for DJ30 stocks
Interest rate dan exchanges rates Factor makroekonomik ini akan berguna untuk memprediksi harga stock dimasa yang akan datang.
Stock average Digunakan data dari the Dow Jones Industrial Average (DJIA), the Standard and Poor's 500 (S & P 500) dan Value Line Composite Index.
Beberapa factor lainnya yang berhubungan, seperti total trading volume, overall advance dan decline volume, jumlah advance, decline, unchanged stock, dan lain – lain.
26 Total faktor masukan adalah sejumlah 106 input faktor yang harus dipertimbangkan. Total faktor masukan yang banyak inilah yang menjadikan sulit untuk menerapkan metoda konvensional. Karena setiap masukan membutuhkan penanganan matematis yang berbeda, serta permodelan yang berbeda. c. Standard & Poor's Corporate Bond Rating System (Garavaglia, 1991) Sistem ini dikembangkan oleh Chanse Manhattan Bank. Berdasarkan kemampuan Artificial Neural Network (ANN) untuk pengklasifikasian, ANN dapat dimanfaatkan dalam aplikasi keuangan. Beberapa area telah memanfaatkannya termasuk analisis kredit, analisa pasar, deteksi penyelewengan, dan ramalan harga. Kesamaan masalah dalam aplikasi di aplikasi keuangan adalah besarnya volume data, proses yang kritis terhadap waktu, kompleksitas dari pola, serta kriteria keputusan yang bersifat kualitatif. Sistem konvensional, ekonometrik yang menggunakan analisis diskriman, termasuk teknik regressi, estimasi maximum likelihood, membutuhkan model matetmatis dari data kualitatif tersebut. Sehingga dibutuhkan pengetahuan yang dalam tentang data masukan serta aturan-aturan yang diterapkan pada data tersebut. Ini akan mempersulit apabila tersedianya jenis data baru. Standard and Poor (S&P) melakukan rating sejak 1923. Mereka tidak mengumumkan metodologi yang digunakan untuk melakukan proses tersebut, hanya mempublikasikan faktor-faktor yang menjadi pertimbangan dalam melakukan proses rating dan arti rating tersebut. Bond Rating adalah masalah klasifikasi, untuk klasifikasi yang non-linear dan tidak adanya model matematis, ANN merupakan salah satu kandidat dari sistem yang digunakan. Perusahaan yang memiliki rate tinggi, misal Fortune 1000, dipertimbangkan sebagai pasar yang telah matang, dimana kesempatan untuk bersaing memperoleh
27 keuntungan dari perusahaan ini hanya akan menghasilkan keuntungan yang kecil Kemampuan untuk menghasilkan bond rating untuk perusahaan yang belum memperoleh rating dari S & P akan menghasilkan analisis kredit dan resiko yang lebih baik. Lebih lanjut rating ini tidak dilakukan oleh suatu badan, keuntungan dari sistem :
Suatu perusahaan dapat mempertimbangkan rating yang diberikan untuknya.
Dapat digunakan untuk pengechekan ulang hasil rating.
Dapat digunakan sebagai pembanding dari rating yang dipublikasikan. Dengan menggunakan data dari S & P Corporate Credit Analysis (CCA) dan
mempertimbangkan data dalam Database CompuStat, dipilih 87 faktor masukan dari setiap perusahaan yang telah memiliki rating. Dipilih 797 perusahaan dari 7200 perusahaan. Digunakan data selama 3 tahun, sebab biasanya S & P menggunakan perioda 3 tahun untuk analisa perbandingan. Bond Rating memiliki range dari AAA (paling berharga), hingga D (paling rendah). Secara umum rating AAA, AA, A, dan BBB dianggap rating yang baik untuk investasi, ini digunakan oleh Controller of the Currency membolehkan suatu Bank untuk menginvesasi dalam sekuritas tersebut. Rating BB, B, CCC, CC dipertimbangkan beresiko dan spekulatif. Sedang Rating D, adalah paling rendah. Contoh data tidak ideal untuk klasifikasi dapat dilihat pada tabel berikut ini : Rating Jumlah Perusahaan Persentase AAA
36
4,5%
AA+
20
2,5%
AA
88
11,0%
28 AA-
51
6,4%
A+
94
11,9%
A
80
10,0%
A-
70
8,8%
BBB+
59
7,4%
BBB
51
6,4%
BBB-
32
4,0%
BB+
25
3,1%
BB
17
2,1%
BB-
20
2,5%
B+
27
3,4%
B
34
4,3%
B-
49
6,1%
CCC+
10
1,3%
CCC
9
1,1%
CCC-
9
1,1%
CC
3
0,4%
C
4
0,5%
D
9
1,1%
Tabel 2.2, Tabel Rating Investasi dari Suatu Bank
29 Data tersebut adalah tidak ekuiprobable, dan lagi klasifikasi adalah tidaklah separable dan faktor subyektif digunakan untuk menentukannya. Sistem ini melakukan rating dan menklasifikasi perusahaan ke dalam tiga jenis:baik untuk investasi, spekulatif, dan buruk. Akurasi dari sistem ini sekitar 84,90% dalam memprediksi rating dari perusahaan dibandingkan dengan rating yang dikeluarkan oleh S&P. Masalah ketidak tepatan ini disebabkan faktor kualitatif yang tidak dimasukkan dalam sistem. Terlebih lagi S&P tidak mempublikasikan persamaan untuk memetakan dari informasi kualitatif ini ke nilai kuantitatif. Sistem ini menunjukkan bahwa ANN dapat melakukan bond rating suatu perusahaan tanpa pengetahuan yang detail mengenai persamaan matematis dan proses penentuan oleh S & P, dengan menghasilkan hasil yang tidak terlalu jauh berbeda. Ketidakakuratan adalah ketidak konsistenan dari sistem rating tersebut sendiri. d. Prediksi penjualan bulanan (Srirengan dan Looit, 1992) Telah diterapkan di sebuah department store di Phoenix, Arizona. Menggunakan ANN dengan backpropagation untuk memprediksikan penjualan bulan mendatang dengan menggunakan data time series penjualan bulan-bulan terdahulu. e. Yamaichi Fuzzy Fund (Munakanta & Jani, 1994) Aplikasi ini merupakan aplikasi awal di dunia perdagangan yang menggunakan pendekatan fuzzy. Sistem ini menangani 65 stok industri dan merupakan stok utama di Nikei Dow. Sistem ini menggunakan 800 rule. Rule ditentukan oleh para ahli dan diperbaiki oleh senior business analys bilamana perlu. Sistem ini telah diuji coba selama 2 tahun dan unjuk kerja dengan menggunakan Nikei Average menunjukkan lebih dari 20%. Ketika diuji coba sistem iini menyarakankan "sell" 18 hari sebelum terjadinya
30 "Black Monday" di tahun 1987. Sistem ini dioperasikan secara komersial pada tahun 1988. Sebagian besar analis keuangan, sepakat mengatakan bahwa "rule" untuk perdagangan itu bersifat "fuzzy". Berbeda dengan pendekatan probabilistik yang menggunakan pertimbangan stochastic event, dan non deterministic, fuzzy model yang menggunakan pendekatan possibilistik adalah menggunakan pendekatan deterministik. (Dubois & Prade, 1988). Sehingga untuk seluruh keadaan masukan yang sama akan selalu diberikan jawaban yang sama. f. Deteksi Penyalahgunaan Kartu Kredit (Hall, 1992) Beberapa perusahaan yang bergerak dalam kartu kredit termasuk American Express menggunakan neural network untuk mempelajari pola penggunaan kartu kredit dari para pelanggannya. Ini digunakan untuk mendeteksi penyalahgunaan kartu kredit tersebut. Penyalah gunaan kartu kredit merupakan masalah yang makin lama makin besar
dan
mengancam
industri
keuangan
ini.
Beberapa
perusahaan
telah
mengaplikasikan metoda ini baik dengan menggunakan program buatan sendiri, ataupun dengan produk komersial misal dari Hecht-Nielsen Computer, Nestor dan lain-lain. Sistem ini dapat memberikan peringatan dini kepada perusahaan apabila ketika dilakukan analisis kepada seorang pelanggan terhadap kemungkinan penyalahgunaan kartu kredit tersebut. g. Financial forecasting dan portofolio manajemen ANN telah digunakan untuk financial forecasting di banyak firma investasi termasuk Meril Lynch & Co, Salomon Brothers, Shearson Lehman Brothers Inc., CitiBank, WorldBank (Schwartz, 1992; Schartz & Treece, 1992). Gerber Baby Food telah menggunakan teknik ini untuk membantu memanajemen perdagangan mereka
31 dalam cartle future. Dengan menggabungkan teknik ANN dan GA CitiBank's Adrew Collins telah mendapatkan 25% pengembalian dari investasi mereka di pasar mata uang. h. Loan Approval Chase Manhattan Bank telah menggunakan sistem yang merupakan gabungan antara ANN dan pattern analysis untuk memperhitungkan resiko pinjaman yang diberikan. Suatu sistem CreditView (Moore, 1990) membantu petugas kredit untuk menentukan apakah suatu pinjaman layak diberikan kepada satu perusahaan. i.
Real Estate Analysis Perusahaan Foster Ouster Conley telah menggunakan sistem ANN yang
dirancang oleh Heccht-Nielsen Computing (HNC), sistem tersebut adalah HNC Areas Automated Property Valuation System (Hall, 1992). Sistem ini digunakan untuk mengevaluasi nilai dari property rumah tinggal di California. j.
Marketing Analysis Pada saat ini Veratex Corp. telah menggunakan sistem yang disebut The Target
Marketing System yang dikembangkan oleh Churchill Systems. Sistem ini digunakan dalam proses optimasi strategi pemasaran dan memotong biaya pemasaran dengan menghilangkan kustomer yang dianggap tidak potensial di masa yang akan datang dari daftar pelanggan yang mendapat kiriman katalog (Hall, 1992). Spiegel Inc., suatu perusahaan mail order, menggunakan software yang diproduksi oleh Neural-Ware Inc. menentukan kustomer manakah yang layak menerima katalog mereka. Dengan menggunakan sistem ini mereka dapat menghemat paling tidak 1 juta dolar setahun yang disebabkan kenaikan penjualan dan mengurangi biaya pengiriman katalog (Schawrtz & Tree, 1992). k. Airline Seating Allocation
32 Suatu software The Airline MArketing Assistant/Tactician yang dikembangkan oleh BehavHeuristics Inc. Suatu sistem ANN digunakan untuk memprediksi permintaan penumpang dan pengalokasian tempat dukuk. Sistem ini telah diterapkan oleh perusahaan penerbangan USAir dan CanadaAir.(Hall, 1992). l.
Rating convertible Bond Nikko Securites telah menggunakan ANN untuk menaikkan rating convertible
bond sejak November 1992 (Okidata et al., 1992). Sistem ini belajar dari reaksi instruktsi seorang ahli rating, yang berubah sesuai dengan keadaan ekonomi. Sistem akan menganalisa hasil, dan menggunakan hasil ini untuk memberikan saran. Sistem terdiri dari gabungan antara Fuzzy Logic dan ANN untuk mendeskripsikan masukan. Ratio dari jawaban yang benar adalah 96%. m. Sharpe Ratio Telah diterapkan oleh The Prediction Company di Santa Fe, GA telah digunakan untuk prediksi time series, serta perangkat bantu untuk perdagangan mata uang. (Packard, 1990). Dengan mengkodekan time series tersebut ke dalam kode generasi, diprediksikan untuk masa yang akan datang akan naik atau turun. Aplikasi lainnya addlah Sharpe Ratio, suatu ratio untuk return to risk untuk perdagangan mata uang. Sharpe ratio ini memiliki nilai dari 0.3 - 1.0, sebagian besar pedagang mata uang memiliki ratio dalam jangakuan 0.3-0.7. Percobaan perhitungan ratio dengan menggunakan teknik GA memberikan hasil yang sama dengan hasil perhitungan ratio dari sistem terbaik dalam lingkungan perdagangan valuta asing. Sistem ini telah digunakan oleh O'Conner Associate, sebuah perusahaan di Chicago yang berafiliasi dengan Swiss Bank Corporation.
33 2.4
Optical Character Recognition Pengenalan kartu nama tergolong dalam pengenalan karakter. Kartu nama yang
telah di capture atau di scan langsung dilakukan pengenalan pada masing-masing karakter seperti pada pengenalan tulisan pada umumnya. Pengenalan tulisan ini telah lama diteliti hingga sekarang oleh para ahli. Dikarenakan, sistem yang ada sekarang ini masih terbatas dan masih butuh pengembangan dalam topik penelitian yang lain, yang berhubungan dengan bidang ini. Pengenalan digolongkan menjadi dua bagian, yaitu pengenalan secara On-line dan pengenalan secara Off-line. (Beren, O, Lecolinet, E. 1994)
2.4.1 Pengenalan secara On-line Sistem pengenalan secara online ini akan melakukan pengenalan karakter pada saat karakter tersebut sedang ditulis, biasanya dilakukan pada suatu alat input digital. Sistem ini sekurang-kurangnya akan mencatat informasi goresan alat input digital secara real-time dan kemudian menganalisa informasi tersebut. Contoh dari sistem pengenalan ini adalah pada program pengenalan tulisan tangan pada PalmPilot. Beberapa hal yang harus diperhatikan pada pengenalan tulisan secara on-line adalah: -
urutan penulisan dapat digunakan dalam proses pengenalan.
-
Informasi sementara, seperti kecepatan menulis juga dapat dijadikan sebagai informasi untuk pengenalan.
-
Garis yang dibuat tidak memiliki ketebalan.
-
Tekanan alat input juga dapat dijadikan sebagai informasi tambahan.
34 2.4.2 Pengenalan secara Off-line Sistem pengenalan tulisan yang mengenali tulisan tidak pada waktu tulisan itu ditulis, tetapi sewaktu tulisan itu selesai ditulis. Sistem pengenalan secara off-line harus menerapkan beberapa aturan agar dapat melakukan pengenalan dengan lebih baik. Banyak sistem yang mengharuskan karakter yang akan dikenali memiliki ukuran yang konsisten dan posisi yang konsisten dengan menggunakan kolom yang telah dicetak sebelumnya sebagai panduan untuk menulis. Contoh dari sistem pengenalan secara offline ini seperti pada aplikasi pengenalan sebuah kode pos yang mana pasti memiliki 5 karakter numerik dan juga digunakan pada bank untuk membaca nominal dan informasi rekening pada cek. Pengenalan tulisan secara offline dibagi menjadi dua bagian besar yaitu pengenalan tulisan tangan dan pengenalan tulisan cetak dari suatu mesin. 2.4.2.1 Pengenalan Tulisan yang Dicetak Oleh Mesin Pengenalan karakter hasil dari cetakan suatu mesin memiliki banyak kemudahan. Hal ini dikarenakan karakter yang dihasilkan memiliki karakter dan lebar yang sama serta ukuran dan jarak antar hurufnya juga sama. Posisi karakter yang ingin dikenali biasa tersusun rapi dan mudah diprediksi. Untuk pengenalan ini dapat dilakukan lebih mudah dibandingkan pengenalan tulisan tangan dan banyak solusi berbiaya rendah yang ditawarkan. Beberapa penelitian yang mengunakan pengenalan tulisan yang dicetak oleh mesin dapat dicontohkan seperti penelitin pengenalan docoment, pengenalan kartu nama, dan lain-lain. 2.4.2.2 Pengenalan Tulisan Tangan Pengenalan tulisan tangan ini memiliki tingkat kesulitan yang cukup komplek. Karakter-karater yang ditulis tangan akan memiliki ukuran dan gaya penulisan yang
35 berbeda antar penulis yang satu dengan penulis yang lain dan juga karakter hasil penulisan seorang yang sama dapat memiliki variasi yang cukup beragam. Secara umum, lokasi maupun jarak antar huruf dari karakter pada halaman yang akan dikenali tidak dapat diprediksi. Kadang-kadang juga memiliki karakter ambigu
yang susah
kenali, seperti ’e’, dan ’l’, ’a’ dan ’o’, dan sebagainya. Biasanya pengenalan terhadap tulisan tangan membutuhkan berberapa aturan tambahan, seperti penulisan harus ditulis pada kertas bergaris dengan lebar yang sama. Pengenalan tulisan tangan ini sendiri dapat digolongkan menjadi dua bagian, yaitu tulisan sambung dan tulisan tidak sambung.
2.5
Citra Digital Citra digital adalah sebuah representasi dari citra dua dimensi sebagai set terbatas
dari nilai-nilai digital yang disebut elemen citra atau pixel. (Anonymous, 2007, Wikipedia). Citra digital terdiri dari jumlah kolom dan baris dari yang tetap. Menurut Gonzalez dan Woods (1993, p6), citra digambarkan dengan fungsi dua demensi f(x,y), dimana x dan y adalah koordinat atau posisi yang mengambarkan lokasi, sedangkan nilai f pada setiap titip (x,y) adalah intensitas atau keabu-abuan. Citra digital ini merupakan data masukan dalam proses selanjutnya yang merepresentasikan sebuah objek atau orang. Biasanya citra digital didapat dari capture kamera atau hasil scan.
2.6
Pixel Pixel adalah sebuah titik single didalam citra digital yang merupakan elemen
individual terkecil yang mempunyai nilai-nilai terkuantisasi yang merepresentasikan brightness dari sebuah warna pada sebuah titik yang spesifik (Anonymous, 2007,
36 Wikipedia). Banyaknya pixel menentukan kualitas dan besarnya ukuran file dari suatu citra gambar. Semakin banyak jumlah pixel yang dipakai, semakin baik kualitas gambar dan semakin besar ukuran file dari gambar tersebut. Keanekaragaman warna dari tergantung dari bit depth yang dipakai. Setiap pixel memiliki tiga atau empat variabilitas secara khas, seperti red, green dan blue atau cyan, magenta, yellow dan black. Hubungan diantara tiap-tiap pixel (Gonzalez dan Woods, 1993, p40):
Neighbors of a pixel Pixel p terletak dalam koordinat p(x,y), memiliki - neightbors yaitu: (x+1,y),(x-1,y)(x,y+1),(x,y-1),(x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1). Ada dua aturan utama dalam relasi antar pixel , yaitu: a. Dua pixel dikatakan 4-adjacent jika bersebelahan secara horizontal dan vertical saja. Contoh untuk pixel 4 pada gambar 2.3, maka 4-adjacentnya adalah pixel 1, pixel 3, pixel 5 dan pixel 7.
Gambar 2.3, Relasi antar pixel 4 Adjacent. b. Dua pixel dikatakan 8-adjacent jika bersebelahan secara diagonal atau bersebelahan secara 4-adjacent. Contoh untuk pixel 4 pada gambar 2.4, maka 8-
37 adjacentnya adalah pixel 0, pixel 1, pixel 2, pixel 3, pixel 5, pixel 6, pixel 7, pixel 8 dan pixel 9.
Gambar 2.4, Relasi antar pixel 8 Adjacent.
Connectivity Konektifitas diantara pixel adalah sebuah konsep penting yang digunakan didalam membangun batas-batas dari objek-objek dan komponen-komponen dari area didalam citra. Konektifitas pixel yang satu dengan lainnya di tentukan oleh letak itu sendiri dan toleransi skala warna yang ada pada citra.
2.7
Image Processing Pengolahan citra adalah manipulasi digital dari suatu citra untuk membantu jarak
penglihatan dari suatu fitur, membuat pengukuran dan mengubah konten dari suatu citra. (Anonymous, 2006, Image Labs International). Pengolahan citra dalam penulisan ini digunakan untuk memperbaiki kualitas dari suatu citra, yang mana citra tersebut merupakan hasil dari capture kamera ataupun scan. Proses menghasilan gambar tersebut biasanya terdapat noise, size yang tidak sesuai dengan standard yang kita inginkan dan sebagainya, sehingga dengan melakukan proses
38 ini dapat membantu mempermudah untuk melakukan proses selanjutnya. Proses ini merupakan proses dasar, mengambil citra sebagai input dan menghasilkan citra baru sebagai output (image to image). 2.7.1 Grayscale Grayscale merupakan batas keabu–abuan pada intensitas yang berbeda dari hitam yang komplek ke putih yang komplek. (Anonymous, 2007, Cnet Reviews). Pada umumnya, warna hitam diberi nilai 0 dan putih diberi nilai 255. Citra dari hasil capture kamera atau scan merupakan warna RGB (Red, Green dan Blue), sehingga harus dirubah terlebih dahulu kedalam warna grayscale. Cara untuk mengubah citra berwarna RGB menjadi citra berwarna grayscale adalah sebagai berikut: RGBrata – rata = R + G + B / 3 diuraikan, R = R + G + B / 3; G = R + G + B / 3; B = R + G + B / 3.
Gambar 2.5, contoh gambar berwarna dan greyscale 2.7.2 Histogram Salah satu cara untuk memperbaiki suatu citra digital adalah dengan mengatur level dari brightness dan contrast-nya. Pertama-tama, kami akan menggambarkan
39 variasi-sebuah brightness pada suatu citra dengan menggunakan histogram citra tersebut dan bagaimana suatu citra dapat dimanipulasi dengan merubah histogram citra tersebut. Histogram akan menempatkan beberapa pixel dengan brightness level mereka yang sesuai. Untuk pixel dengan ukuran level brightness sebesar 8-bit maka brightness akan memiliki grey level yang berkisar antara nol(hitam) sampai 255(putih). Sehingga histogram yang memiliki nilai brightness yang lebih kecil akan terlihat lebih gelap dibandingkan dengan yang memiliki nilai lebih besar. Gambar 2.6 menunjukkan gambar sebuah ban mobil dengan histogramnya. Histogram pada gambar 2.6 menunjukkan bahwa tidak semua grey level yang ada dalam histogram terpakai. Dapat kita lihat bahwa histogram yang memiliki grey level dibawah 120 memiliki tingkat kegelapan yang lebih gelap, dimana warna gelap tersebut dimiliki oleh ban mobil dan bagian bawah mobil, serta bayangan mobil yang memiliki warna cenderung hitam. Disini juga terlihat bahwa apabila suatu gambar memiliki warna yang cenderung gelap maka secara keseluruhan histogram akan berkonsentrasi kearah kiri(hitam).Bandingkanlah gambar 2.7 tersebut dengan gambar 2.7 yang mana gambar tersebut adalah gambar yang sama, tetapi telah dinaikkan nilai brightness-nya. Sekarang histogram cenderung merata dan agak sedikit terkonsentrasi ke arah kanan(putih).
Gambar 2.6, sebuah ban mobil dan histogramnya
40
Gambar 2.7, ban mobil dan histogramnya Disini kita dapat melihat bahwa kita belum memakai seluruh dari grey level yang tersedia. Kita dapat menarik histogram citra tersebut sehingga semua grey level yang tersedia sepenuhnya terpakai, dan teknik itu akan menghasilkan citra yang lebih jelas. Histogram ini juga dapat memperlihatkan kejanggalan bila didalam citra tersebut terdapat noise apabila histogram yang ideal telah kita ketahui. Sehingga kami dapat menghilangkan noise tersebut. Proses ini tidak hanya semata-mata kami lakukan untuk mendapatkan citra yang lebih baik, tetapi juga untuk lebih memudahkan tugas-tugas kami dalam teknik-teknik pemprosesan citra selanjutnya. 2.7.3 Histogram normalisasi Seperti yang sudah dibahas diatas bahwa pada histogram terdapat jarak yang berkisar antara nol(hitam) sampai 255(putih) dimana dari seluruh grey level yang tersedia tidak semuanya terpakai dalam suatu histogram. Cara yang paling populer untuk menarik kisaran jarak intensitas suatu histogram adalah dengan cara histogram normalisasi. Dengan cara inilah histogram yang asli ditarik dan digeser untuk memenuhi seluruh dari 256 level yang tersedia(0-255).
41 Histogram dari citra awal adalah O diawali dari Omin sampai Omax level brightness, kita dapat menaikkan skala citra sehingga pada gambar yang baru N terdapat pada level output minimum Nmin sampai level maksimum Nmax, sehingga Nx,y = (Nmax - Nmin / Omax - Omin )
*
(Ox,y - Omin ) + Nmin V
(Mark Nixon & Alberto Aguado)
2.7.4 Histogram equalisation Histogram equalisation adalah suatu proses non-linear yang bertujuan untuk memberikan nilai pencahayaan citra yang sesuai dengan analisis visual manusia. Histogram equalisation bertujuan untuk merubah citra, sehingga gambar yang dihasilkan memiliki histogram yang lebih merata, dimana bisa membuat semua level brightness suatu histogram dapat terpakai. Untuk jarak dari suatu brightness level M, histogram menempatkan point untuk setiap levelnya dengan level. Dan untuk setiap input(citra awal) dan setiap output(citra baru), angka dari poin-poin per level dinotasikan sebagai O(l) dan N(l) (untuk 0 < l < M). Untuk image dengan betuk persegi(seperti ), terdapat N2 poin pada input dan output, maka jumlah poin per-levelnya sama dengan
Untuk mendapatkan image dengan histogram yang merata maka kita harus mengkumulatifkan level awal p untuk di transformasikan agar dapat memenuhi level akhir q pada histogram yang baru.Sehingga rumusnya menjadi:
42 Karena output dari histogram diharapkan merata, maka kumulatif histogram dengan level p haruslah merupakan rata-rata dari seluruh jumlah fraksi yang ada. Maka jumlah dari poin per level pada gambar baru merupakan rasio dari jumlah poin dengan jarak dari level gambar baru:
Sehingga histogram kumulatif dari gambar baru adalah :
Dengan menggabungkan rumus ini dengan rumus persamaan diatas, maka didapatkan :
Rumus ini dapat memetakan output pixel pada level q, dari input pixel pada level p dengan cara:
Dengan rumus ini kita dapat membuat suatu fungsi yang dapat menyediakan histogram dari gambar baru yang memiliki level merata.Fungsi ini dapat kita tentukan dengan cara menggunakan rumus diatas dan menggunakannya sebagai fungsi persamaan (E) dari level (q) dan memiliki gambar (O), sehingga didapat:
Maka gambar yang baru memiliki rumus :
43
Dengan cara ini kita dapat mendapatkan gambar dengan kualitas yang jauh lebih baik dibandingkan dengan gambar asalnya. Performa dari cara ini sungguh sangat meyakinkan sejak cara ini dapat memetakan gambar dengan baik sehingga sesuai dengan visualisasi mata manusia. 2.7.5
Thresholding Thresholding adalah suatu proses yang digunakan untuk
menghasilkan citra biner yaitu citra dengan hanya dua warna, yaitu: hitam dan putih. Operator ini memilih yang memiliki nilai tertentu, atau lingkup tertentu. Proses ini dapat dilakukan apabila kita telah mengetahui brightness level(atau contrast) dari gambar tersebut. Bentuk teknik Thresholding ada 2 macam, yaitu: Uniform Thresholding dan Adaptive Thresholding. Didalam uniform thresholding metode yang digunakan adalah dengan menentukan suatu batas level, yang nantinya akan dipergunakan untuk menentukan warna . yang levelnya lebih dari threshold level akan dirubah menjadi putih, dan sebaliknya pixel yang levelnya ada di bawah dari level threshold akan dirubah menjadi hitam. Seperti yang kami tampilkan pada gambar 2.8(a) merupakan gambar original yang kami dapat dari meja kerja matlab dan gambar 2.8(b) adalah hasil thresholding dari gambar 2.8(a).
(a)
(b)
44 Gambar2.8, (a) Citra original dan (b) Citra hasil thresholding Pada gambar diatas ditunjukkan citra hasil thresholding dengan nilai threshold sebesar 128 dimana pixel-pixel yang memiliki nilai 128 keatas dirubah menjadi putih dan pixel yang bernilai 128 kebawah dirubah menjadi hitam. Pada teknik thresholding, sebenarnya masih ada lagi teknik yang lebih lanjut, teknik ini dikenal dengan nama optimal thresholding. Teknik ini biasa digunakan untuk memisahkan suatu objek gambar dengan latar belakangnya. Teknik ini dapat melihat perbedaan intensitas yang terdapat pada latar belakang dan objek sehingga dapat menentukan nilai sebuah threshold yang sesuai.
Gambar 2.9, optimal thresholding Gambar 2.9. merupakan sebuah contoh dari pengambilan nilai threshold pada optimal thresholding dengan menggunakan metode Otsu (Otsu, 1979). Metode ini adalah metode yang paling populer diantara semua metode thresholding yang ada. Teknik Otsu ini memaksimalkan kecocokan dari sebuah threshold sehingga dapat memisahkan objek dengan latar belakangnya.Semua ini didapatkan dengan memilih nilai threshold yang memberikan pembagian kelas yang terbaik untuk semua yang ada didalam image. Dasarnya adalah dengan menggunakan histogram yang telah dinormalisasi dimana jumlah tiap poin pada setiap level dibagi dengan jumlah total poin pada image.
45
(a)
(b)
Gambar 2.10, (a)Citra original dan (b)Citra hasil thresholding dengan metode Otsu 2.7.6 Scaling Scaling adalah sebuah operasi yang digunakan untuk menambah atau mengurangi ukuran citra dengan ratio yang ditetapkan. Teknik ini mengubah ukuran citra menjadi citra yang berukuran sesuai dengan yang akan dijadikan sebagai data masukan untuk proses selanjutnya. 2.7.7 Segmentasi Segmentasi adalah partisi dari sebuah citra menjadi satu set wilayah yang mencakup citra tersebut. (Shapiro dan Stockman, 2001, p279). Segmentasi memiliki dua tujuan:
Untuk memisahkan citra menjadi bagian-bagian untuk analisa lebih lanjut.
Untuk menampilkan suatu perubahan dari representasi.
Pengindentifikasian suatu wilayah:
Wilayah dari sebuah citra segmentasi harus homogen dan seragam dengan mengikuti beberapa karakteristik, contoh: tingkat keabu-abuan, warna, atau terkstur.
Wilayah interior sebaiknya sederhana dan tanpa banyak titik-titik kecil(noise).
Batas wilayah segmentasi sebaiknya memiliki perbedaan nilai yang signifikan dengan meyerupai karakteristik yang seragam.
46
Batas-batas dari masing-masing segmen sebaiknya halus, tidak kasar dan terspatial secara akurat.
2.7.8 Ekstraksi Fitur Ekstrak fitur merupakan suatu teknik untuk mendapatkan suatu karakteristik dari suatu citra yang mana setiap citra memiliki karakteristik yang berbeda dengan citra yang lain. Ekstrak fitur menjadi data masukan di dalam segmentasi dokumen, sehingga memperkecil perhitungan dalam proses selanjutnya. Tujuan dari ekstrak fitur adalah untuk mengelompokan parameter yang mendefinisikan suatu citra dengan keakuratan dan keunikan. Ekstrak fitur adalah langkah penting untuk memperoleh hasil pengklasifikasian wilayah didalam sistem. Pemilihan metode ekstrak fitur akan membatasi atau menentukan sifat dan hasil dari langkah pre processing.
2.9
Grey Level Co-occurrence Matrix Texture-based Gray Level Co-occurrence Matrix (GLCM) dikenal juga dengan Grey Tone
Spatial Dependency Matrix merupakan suatu tabulasi dari seberapa sering suatu kombinasi nilai brightness pixel yang berbeda yang terdapat didalam suatu citra. (Hall, Mryka.,Beyer, 2007). Gambar dibawah menjelaskan suatu contoh nilai citra, nilai citra merupakan Grey Level.
Gambar 2.11, Citra Contoh
47 0 0 0 2
0 0 2 2
1 1 2 3
1 1 2 3
Gambar 2.12, Grey Level dari Citra Contoh 2.8.1 Definisi “Order” Gray Level Co-occurrence Matrix diuraikan di sini digunakan untuk satu rangkaian ”second order” kalkulasi texture. First Order texture merupakan kalkulasi statistik dari nilai citra asli, seperti perbedaan dan tidak mempertimbangkan hubungan pixel neighbour. Second Order mempertimbangkan hubungan antara group dari pixel-pixel di dalam citra asli. Third and higher Order texture (mempertimbangkan hubungan antara tiga atau lebih pixel) secara teori mungkin diterapkan namun tidak untuk diterapkan secara umum yang berkaitan dengan kalkulasi waktu dan sulit di taksir. 2.8.2 Framework Gray Level Co-occurrence Matrix
Hubungan spatial antara dua pixel: GLCM texture mempertimbangkan hubungan dua pixel pada suatu waktu,
disebut dengan reference dan pixel neighbour. Pada ilustrasi dibawah, pixel neighbour dipilih dari satu sebelah kanan dari setiap pixel acuan. Ini dapat dinyatakan dengan relation (1,0): 1 pixel pada direction x, 0 pixel pada direction y.
48 0 0 0 2
0 0 2 2
1 1 2 3
1 1 2 3
2
2
1
0
0
2
0
0
0
0
3
1
0
0
0
1
Gambar 2.13, Greylevel dari Citra Contoh (atas) dan GLCM dengan relation(1,0) (bawah) Satiap pixel yang ada pada window menjadi pixel acuan pada gilirannya (semua pixel akan menjadi pixel acuan), dimulai dari kiri atas dan diteruskan sampai kanan bawah. Pixel sepanjang edge (tepi) kanan pada greylevel diatas tidak memiliki relation pixel pada sebelah kanannya, sehingga pixel-pixel ini tidak digunakan dalam perhitungan (tidak dijadikan acuan pada relation(1,0) ).
Pemisahan antara dua pixel: Semua contoh pada teori ini menggunakan 1 pixel offset (sebuah acuan pixel dan
neighbour sekitarnya). Jika ukuran dari gambar kita cukup besar, menggunakan offset yang lebih besar adalah sangat mungkin untuk diterapkan. Penjumlahan dari semua masukan GLCM (yaitu, banyaknya pixel kombinasi) akan lebih kecil untuk ukuran window yang telah ditentukan. Kombinasi greylevel yang mungkin untuk citra seperti diatas dan posisi matrix masing-masing kombinasi,
49 0 0 0 2
0 0 2 2
1 1 2 3
neighbour pixel value -> 0
1 1 2 3
1
2
3
ref pixel value: 0
0,0
0,1
0,2
0,3
1
1,0
1,1
1,2
1,3
2
2,0
2,1
2,2
2,3
3 3,0 3,1 3,2 3,3 Gambar 2.14, Greylevel dari Citra Contoh (atas) dan kombinasi greylevel dari Citra Contoh (bawah) Hanya pada waktu ini lebal baris atas dan kolom kiri yang akan ditampilkan Semua representasi lebih lanjut dari GLCM hanya memasukkan 16 data cell (seperti gambar diatas). Membaca matrix framework: Kiri atas diisi dengan banyaknya kombinasi 0,0 yang muncul, dengan kata lain, seberapa sering sebuah pixel dengan greylevel 0 (neightbour pixel) jatuh pada kanan dari pixel yang lain dengan grey level 0 (reference pixel) pada area citra. Contoh mengisi matrix framework untuk dengan offset atau spatial relationship (1,0) dengan menggunakan citra contoh sebelumnya: 2
2
1
0
0
2
0
0
0
0
3
1
0
0
0
1
50 Dua kali pada citra contoh, reference pixel 0 dan eastern neighbournya juga 0. Dua kali reference pixel 0 dan eastern neighbournya 1. Tiga kali reference pixel 2 dan neightbournya juga 2.
2.9
Cluster Analysis Analisis Pengelompokan (cluster analysis), disebut juga analisis segmentasi
(segmentation analysis) atau analisis taksonomi (taxonomy analysis), merupakan seperangkat tehnik untuk mencapai pekerjaan mempilah – pilah objek – objek (observasi) menjadi subset – subset yang relatif homogen, berdasarkan kesamaan – kesamaan antar objek (http://mail.pl.itb.ac.id/~zpontoh/PL212/StatCH16/sld002.htm). Clustering adalah klasifikasi obyek kedalam kelompok yang berbeda, atau lebih tepatnya, pembagian sebuah set data kedalam subset – subset (cluster), sehingga data dalam tiap subset (idealnya) berbagi beberapa sifat umum – seringkali dekatnya bergantung pada beberapa perhitungan jarak yang dijelaskan. Pengelompokan data (data clustering) adalah tehnik umum untuk analisis data statistic, yang digunakan pada banyak bidang, termasuk machine learning, data mining, pengenalan pola, analisis citra dan bioinformatik (http://en.wikipedia.org/wiki/Cluster_analysis). 2.9.1 Aplikasi-aplikasi yang Memungkinkan Algoritma Clustering dapat dipakai dalam banyak bidang, seperti:
Marketing: menemukan grup-grup pelanggan dengan sifat yang sama yang memberikan sebuah database pelanggan yang besar yang mengandung barangbarang mereka dan dokumen pembelian lalu.
51
Biologi: pengklasifikasian dari tanaman dan hewan yang memberikan fitur-fitur mereka.
Perpustakaan: pemesanan buku.
Asuransi: mengindentifikasian grup-grup dari pemegang kebijakkan asuransi motor dengan biaya klaim yang cukup tinggi; mengindentifikasi penipuan.
Perencanaan kota: mengindentifikasian kelompok rumah menurut jenis rumah, nilai, dan lokasi geografi.
Pembelajaran
gempa:
clustering
mengamati
pusat
gempa
untuk
mengindentifikasi zona-zona bahaya.
WWW: pengklasifikasin dokumen; Clustering data weblog untuk menemukan kleompok dari akses pola yang sama.
Astronomi : Bintang-bintang dikelompokkan dalam suatu gugus (misalnya yang sifat pancarannya sama)
Meteorologi : Curah hujan, kelembaban, tekanan udara bisa mengelompokkan wilayah-wilayah tertentu yang sifatnya sama
Geologi : Untuk mengetahui sebaran bebatuan atau tanah yang sifatnya sama
2.9.2 Persyaratan Syarat utama algoritma Clustering:
Scalability
Berhubungan dengan jenis-jenis sifat yang berbeda.
Menemukan cluster dengan bentuk yang berubah-ubah.
Persyaratan minimal untuk ilmu daerah untuk menetukan pemasukan parameter.
Kemampuan untuk menghadapi suara dan outlier.
52
Ketidakpekaan untuk mengorder masukan dokumen.
Dimensi yang tinggi.
Kemampuan penafsiran dan penggunaan.
2.9.3 Masalah-masalah Ada banyak masalah-masalah dengan Clustering. Seperti:
Teknik Clustering terkini tidak menunjukkan semua persyaratan yang cukup.
Menghadapi dengan banyak dimensi dan banyak item-item data yang problematis karena waktu kompleks.
Keefektifan dari metode-metode bergantung pada penjelasan ”jarak” (untuk distance-based Clustering).
Jika ukuran jarak yang ”jelas” tidak muncul, kita harus menjelaskan jarak ini, yang tidak akan selalu mudah, terutama dalam ruang multi-dimensi.
Hasil dari algoritma Clustering (yang dalam kebanyakan masalah dapat berubahubah) dapat ditafsir dalam cara-cara berbeda.
2.9.4 Tipe-tipe Clustering Terdapat dua jenis algoritma pengelompokan data antara lain pengelompokkan hierarkis dan pengelompokan partisional (http://en.wikipedia.org/wiki/Cluster_analysis). Clustering dua arah, co-clustering atau biclustering adalah metode pengelompokkan dimana bukan hanya obyek yang dikelompokkan tetapi juga sifat-sifat dari obyek, contohnya, jika data direpresentasikan dalam sebuah matriks data, maka baris dan kolom akan dikelompokkan secara bersamaan. 2.9.4.1 Hierarchical Clustering
53 Algoritma hierarkis menemukan cluster berturut-turut menggunakan cluster yang dibangun sebelumnya, atau dengan kata lain pembagian data kedalam kelompokkelompok tertentu tidak dilakukan dalam satu langkah. Bahkan, serangkaian pembagian terjadi, yang mungkin berjalan dari sebuah cluster tunggal yang berisikan semua obyek ke
n
cluster
yang
masing-masing
berisi
sebuah
obyek
tunggal
(
http://www.resample.com/xlminer/help/HClst/HClst_intro.htm). Hierarchical Clustering dibagi kedalam dua metode antara lain :
Agglomerative Method Didapat dengan serangkaian penyatuan n obyek kedalam kelompok-kelompok. Metode ini lebih umum digunakan.
Divisive Method Memisahkan n obyek secara berturut-turut kedalam finer grouping. Hierarchical Clustering dapat ditunjukkan dengan sebuah diagram dua dimensi
yang dikenal sebagai dendogram yang mengilustrasikan penyatuan atau pemisahan yang dibuat pada tiap urutan tahap dari analisis. Contoh dendogram diberikan seperti dibawah ini :
Gambar 2.15, Dendogram
54 Prosedur pengelompokan hierarkis agglomerative menghasilkan serangkaian pembagian data, Pn, Pn-1, ....... , P1 . Pn yang pertama berisi n kelompok obyek tunggal, P1 berisi kelompok tunggal yang berisi semua permasalahan n. Pada tiap tahap tertentu metode ini bekerja sama dengan dua cluster yang paling mirip. Perbedaan antara metode timbul karena cara yang berbeda-beda dalam menetapkan jarak (atau kemiripan) antar cluster. Beberapa tehnik agglomerative akan dijelaskan dibawah ini.
Single Linkage Clustering Salah satu metode pengelompokan hierarkis agglomerative yang paling sederhana adalah pertalian tunggal, dikenal juga dengan tehnik tetangga terdekat (nearest neighbor). Pendefinisian sifat dari metode ini adalah bahwa jarak antar kelompok ditetapkan sebagai jarak antara pasangan obyek terdekat, dimana hanya pasangan yang berisikan satu obyek dari tiap kelompok yang dipertimbangkan. Dalam metode pertalian tunggal, D(r,s) dirumuskan sebagai : D(r,s) = Min { d(i,j) :dimana obyek i didalam cluster r dan obyek j didalam cluster s} Disini jarak antara pasangan obyek (i,j) yang mungin dihitung, dimana obyek i didalam cluster r dan obyek j didalam cluster s. Nilai minimum dari jarak ini adalah jarak antara cluster r dan s. Dengan kata lain, jarak antara dua cluster adalah nilai dari link terpendek antar cluster. Pada tiap tahap dari hierarchical clustering, cluster r dan s, untuk D(r,s) minimum, digabungkan.
55
Gambar 2.16, Single Linkage Clustering
Complete Linkage Clustering Metode pengelompokan Complete Linkage , disebut juga furthest neighbor, adalah kebalikan dari single linkage. Jarak antar kelompok ditetapkan sebagai jarak antar pasangan obyek terjauh, satu dari tiap-tiap kelompok. Dalam metode ini, D(r,s) dirumuskan sebagai : D(r,s) = Max{ d(i,j) :dimana obyek i didalam cluster r dan obyek j didalam cluster s} Disini jarak antara pasangan obyek (i,j) yang mungin dihitung, dimana obyek i didalam cluster r dan obyek j didalam cluster s dan nilai minimum dari jarak ini adalah jarak antara cluster r dan s. Dengan kata lain, jarak antara dua cluster adalah nilai dari link terpanjang antar cluster. Pada tiap tahap dari hierarchical clustering, cluster r dan s, untuk D(r,s) minimum, digabungkan.
56
Gambar 2.17, Complete Linkage Clustering
Average Linkage Clustering Jarak antar dua cluster ditetapkan sebagai jarak rata-rata antar semua pasangan obyek, dimana tiap-tiap pasangan dibentuk dari satu obyek dari masing-masing kelompok. Dalam metode ini, D(r,s) dirumuskan sebagai : D(r,s) = Trs / ( Nr * Ns)
Dimana Trs adalah jumlah dari semua jarak pasangan antara cluster r dan cluster s. Nr dan Ns
adalah ukuran dari cluster r dan s berturut-turut. Pada tiap tahap dari
hierarchical clustering, cluster r dan s, untuk D(r,s) minimum, digabungkan.
57
Gambar 2.18, Average Linkage Clustering
Average Group Linkage Dengan metode ini, kelompok akan direpresentasikan oleh nilai mean untuk tiap-tiap variable, oleh karena itu, vektor mean, dan jarak inter-group ditetapkan sebagai jarak antar dua vektor mean tersebut. Dalam metode average group linkage, dua cluster r dan s digabungkan sehingga, setelah penggabungan, jarak rata-rata pasangan dalam cluster yang diperbaharui adalah minimum. Anggap saja kita menandakan cluster baru yang dibentuk dengan penggabungan cluster r dan s, sebagai t. Maka D(r,s), jarak antara cluster r dan s dirumuskan sebagai : D(r,s) = rata-rata { d(i,j) : dimana observasi i dan j ada didalam cluster t, cluster dibentuk dengan penggabungan cluster r dan s } Pada tiap tahap dari hierachical clustering, cluster r dan s, untuk D(r,s) minimum, digabungkan. Dalam kasus ini, kedua cluster tersebut digabungkan sehingga cluster
58 yang baru dibentuk akan memiliki jarak pasangan minimum antara titik-titik didalamnya.
Ward’s Hierarchical Clustering Method Ward (1963) mengajukan sebuah prosedur clustering mencoba untuk membentuk pembagian dalam cara yang meminimalisasikan asosiasi yang hilang dengan tiaptiap pengelompokan, dan untuk mengukur kehilangan tersebut dalam sebuah bentuk yang dapat ditafsirkan. Pada tiap langkah dalam analisis, kesatuan dari semua pasangan cluster yang mungkin dipertimbangkan dan dua cluster yang hasil penyatuannya dalam peningkatan minimum dalam hal hilangnya informasi dikombinasikan.
2.9.4.2 Partitional Clustering Berbeda dengan hierarchical clustering, pada metode pengelompokkan parsional ini, pembagian data kedalam kelompok-kelompok tertentu justru dilakukan dalam satu langkah. Partitional Clustering (http://www.cis.hut.fi/~sami/thesis/node9.html), pada sisi lain, berusaha secara langsung untuk mendekomposisikan set data kedalam sebuah set cluster yang terputus-putus. Fungsi standar yang algoritma pengelompokan berusaha untuk meminimalisasinya, mungkin menekankan pada struktur local dari data, dengan menugaskan cluster untuk mencapai puncaknya dalam fungsi kepadatan kemungkinan, atau struktur global. Secara khusus, criteria global menyangkut meminimalkan beberapa ukuran ketidakcocokan dalam sample pada tiap cluster, ketidakcocokan pada cluster yang berbeda.
saat memaksimalkan
59 2.9.4.2.1 K-Means Clustering K-means (MacQueen,1967) adalah salah satu algoritma unsupervised learning paling sederhana yang menyelesaikan masalah pengelompokan yang umum dikenal. Prosedurnya mengikuti cara yang sederhana dan mudah untuk mengklasifikasikan set data yang diberikan melalui sejumlah tertentu cluster (diasumsikan k cluster) menentukan prioritas. Gagasan utamanya adalah untuk menetapkan k centroid, satu untuk masingmasing cluster. Centroid ini seharusnya ditempatkan dalam cara yang cerdik karena lokasi yang berbeda menyebabkan hasil yang berbeda pula. Jadi, pilihan terbaik untuk menempatkannya sejauh mungkin satu sama lain. Langkah selanjutnya adalah menjadikan tiap point masuk dalam set data yang diberikan dan mengasosiasikannya ke centroid terdekat. Ketika tidak ada point yang pending, langkah pertama sempurna dan groupage awal selesai. Pada titik ini kita perlu mengkalkulasi ulang k centroid baru sebagai barycenter dari cluster yang didapat dari tahap sebelumnya. Setelah kita mendapatkan k centroid baru ini, ikatan baru harus dilakukan antara data set point yang sama dan centroid baru terdekat. Perulangan dilakukan. Dari hasil perulangan ini kita mungkin memperhatikan bahwa k centroid mengubah lokasinya langkah demi langkah hingga akhirnya tidak ada lagi perubahan yang bisa dilakukan. Dengan kata lain centroid tidak bergerak lagi. Algoritma ini bertujuan pada peminimalan sebuah fungsi obyektif, dalam hal ini fungsi error kuadrat. Fungsi obyektifnya :
60
adalah ukuran jarak yang dipilih antara data point
dimana cluster
dan pusat
, adalah sebuah indikator jarak pada n data point dari pusat cluster.
Adapun algoritmanya terdiri dari langkah-langkah sebagai berikut :
Tempatkan k point kedalam ruang yang direpresentasikan oleh obyek-obyek yang dikelompokkan. Point ini menerangkan centroid grup awal.
Arahkan tiap obyek ke grup yang memiliki centroid terdekat.
Ketika semua obyek telah diarahkan, hitung ulang posisi dari k centroid.
Ulangi langkah 2 dan 3 sampai centroid tidak lagi bergerak. Hal ini menciptakan pemisahan obyek ke dalam grup yang mana matriks yang diminimalkan dapat dihitung.
2.9.4.2.2 QT Clustering Algorithm QT (Quality Threshold) Clustering(Heyer et al,1999) adalah suatu metode alternatif dalam pemisahan data, diciptakan untuk pengelompokan gen. Hal ini memerlukan penetapan yang banyaknya cluster awal, dan selalu menghasilkan hasil yang sama ketika dijalankan berkali – kali. 2.9.5 Perhitungan Jarak Sebuah langkah penting dalam pengelompokan adalah dengan memilih sebuah ukuran jarak, yang akan menentukan bagaimana kesamaan dua elemen diperhitungkan ( http://en.wikipedia.org/wiki/Cluster_analysis). Hal ini akan memperngaruhi bentuk cluster, dimana beberapa elemen mungkin saling berdekatan satu sama lain mengacu pada satu jarak atau saling menjauh. Terdapat sejumlah perhitungan jarak inter-observasi dan jarak inter-cluster yang berbeda-beda untuk digunakan sebagai criteria saat menggabungkan cluster terdekat
61 kedalam kelompok yang lebih besar atau pada saat menentukan hubungan antara sebuah point ke satu cluster. Perlu diketahui bahwa pada saat dua atau lebih variable digunakan untuk mendefinisikan jarak, variable yang satu dengan magnitudo yang besar akan mendominasi, jadi untuk mencegah hal ini umum dilakukan untuk menstandarisasikan semua variable dahulu (http://www2.chass.ncsu.edu/garson/pA765/cluster.htm). 2.9.5.1 The Euclidean Distance Euclidean Distance merupakan pengukur jarak yang paling umum digunakan. Perlu diperhatikan bahwa Euclidean Distance biasanya dihitung dari data yang mentah, dan bukan dari data yang sudah distandarkan. Metode ini memiliki kelebihan tertentu misalnya jarak antara dua obyek tidak dipengaruhi oleh penambahan obyek baru ke dalam analisis. Bagaimanapun, jarak dapat dipengaruhi oleh perbedaan dalam skala antar dimensi dimana jarak diperhitungkan. Euclidean Distance dirumuskan sebagai ( http://www.statsoft.com/textbook/stcluan.html):
distance(x,y) = {
i
(xi - yi)2 }…
2.9.5.2 City Block Distance City Block Distance, dikenal juga dengan nama Block Distance atau Manhattan Distance, merupakan perbedaan rata-rata antar dua atau lebih dimensi yang digunakan untuk
menetapkan
jarak
(http://www2.chass.ncsu.edu/garson/pA765/cluster.htm).
Dirumuskan sebagai (http://www.statsoft.com/textbook/stcluan.html):
distance(x,y) =
i
|xi - yi|
62 2.9.5.3 Chebychev Distance Pengukur jarak ini cocok digunakan dalam kasus dimana seseorang ingin mendefinisikan dua obyek sebagai suatu perbedaan jika mereka berbeda pada satu dimensi.
Chebychev
Distance
dirumuskan
sebagai
(
http://www.statsoft.com/textbook/stcluan.html) :
distance(x,y) = Maximum|xi - yi| 2.9.5.4 Mahanalobis Distance Pengukur jarak ini diperkenalkan oleh P.C. Mahanalobis pada 1936. Mahanalobis Distance berdasarkan pada korelasi antar variable dimana pola yang berbeda dapat diidentifikasi dan dianalisa. Hal ini merupakan cara yang berguna dalam menentukan kemiripan sample set yang belum diketahui ke yang sudah diketahui. Dirumuskan sebagai (http://en.wikipedia.org/wiki/Mahalanobis_distance) :
2.9.5.5 Hamming Distance Hamming Distance menghitung jumlah minimum dari substitusi yang dibutuhkan untuk mengubah anggota yang satu ke anggota lainnya. Hamming Distance antara dua string dari panjang yang sama adalah jumlah posisi yang mana symbol korespondensinya berbeda (http://en.wikipedia.org/wiki/Hamming_distance). Richard Hamming, yang memperkenalkan Hamming distance dalam makalah fundamentalnya mengenai pendeteksian error dan kode pendeteksian error (1950), memperkenalkan Hamming codes. Kode Hamming ini digunakan dalam bidang telekomunikasi untuk menghitung jumlah bit yang dibalik dalam bentuk biner yang
63 panjangnya tetap sebagai estimasi error, sehingga terkadang disebut juga signal distance.
