BAB II TINJAUAN PUSTAKA

BAB II

TINJAUAN PUSTAKA

2.1. Pengenalan Pola Sebuah pola adalah setiap antar hubungan data (analog atau digital), kejadian atau konsep yang dapat dibedakan. Pengenalan pola merupakan bidang dalam pembelajaran mesin dan dapat diartikan sebagai tindakan mengambil data mentah dan bertindak berdasarkan klasifikasi data. Dengan demikian, pengenalan pola merupakan himpunan kaidah bagi pembelajaran diselia (supervised learning). Ada beberapa definisi lain tentang pengenalan pola, di antaranya: 1. Penentuan suatu objek fisik atau kejadian ke dalam salah satu atau beberapa kategori. 2. Ilmu pengetahuan yang menitikberatkan pada deskripsi dan klasifikasi (pengenalan) dari suatu pengukuran. 3. Suatu pengenalan secara otomatis suatu bentuk, sifat, keadaan, kondisi, susunan tanpa keikutsertaan manusia secara aktif dalam proses pemutusan. Berdasarkan beberapa definisi di atas, pengenalan pola dapat didefinisikan sebagai cabang kecerdasan yang menitik-beratkan pada metode pengklasifikasian objek ke dalam klas-klas tertentu untuk menyelesaikan masalah tertentu. Salah satu aplikasinya adalah pengenalan suara, klasifikasi teks dokumen dalam kategori (contoh. surat-E spam/bukan-spam), pengenalan tulisan tangan, pengenalan kode pos secara otomatis pada sampul surat, atau sistem pengenalan wajah manusia. Aplikasi ini kebanyakan menggunakan analisis citra bagi pengenalan pola yang berkenaan dengan citra digital sebagai input ke dalam sistem pengenalan pola.

2.2. Teknik Pengenalan Pola Pengenalan pola merupakan langkah perantaraan bagi proses menghilangkan dan menormalkan gambar dalam satu cara (pemrosesan gambar (image processing),

Universitas Sumatera Utara

teks dll.), pengiraan ciri-ciri, pengkelasan dan akhirnya post-pemrosesan berdasarkan kelas pengenalan dan aras keyakinan. Pengenalan pola itu sendiri khususnya berkaitan dengan langkah pengkelasan. Dalam kasus tertentu, sebagaimana dalam jaringan syaraf (neural networks), pemilihan ciri-ciri dan pengambilan juga boleh dilaksanakan secara semi otomatis atau otomatis sepenuhnya. Untuk penyelesaian masalah dengan pengkelasan dapat dilakukan dengan tiga cara . Pertama adalah mencari peta ruang ciri (feature space) (biasanya berbagai dimensi ruang vektor (vector space)) bagi set label. Secara bersamaan dapat membagi ruang ciri menjadi kawasan-kawasan, kemudian meletakkan label kepada setiap kawasan. Algoritma yang demikian ini (contohnya the nearest neighbour algorithm) biasanya belumlah menghasilkan kepercayaan atau kelas probabilitas, sebelum diterapkannya post-processing. Masalah kedua adalah dengan menganggap masalah sebagai suatu kemungkinan, dimana konsepnya adalah kondisi probabilitas bagi bentuk ................................................................ (2.1) dimana input vektor ciri adalah sebagian parameter

, dan fungsi f biasanya diparameter oleh

. Dalam pendekatan statistik Bayesian bagi masalah ini,

berlainan dengan memilih satu vektor parameter

, hasil dibentuk bagi kesemua

kelas yang mungkin, sesuai urutan berdasarkan data latihan D: .................................. (2.2) Masalah ketiga terkait dengan masalah kedua, tetapi masalahnya adalah untuk kondisi probabilitas bersyarat (conditional probability)

dan

kemudian menggunakan aturan Bayes untuk menghasilkan kemungkinan kelas sebagaimana dalam masalah kedua.

2.2.1. Evaluasi Ciri Melalui Ukuran-Ukuran Fuzzy Kriteria sebuah ciri yang baik adalah ciri harus invarian terhadap variasi kelas dengan penekanan antara jenis-jenis pola yang berlainan. Salah satu teknik yang


berguna untuk mencapainya yaitu transformasi kluster yang memaksimum dan meminimumkan jarak dengan menggunakan transformasi diagonal sehingga bobot-bobot yang lebih kecil memiliki variansi yang lebih besar. Data-data atau pola yang terpilih akan di kelompokkan menjadi beberapa kluster dengan parameter yang digunakan untuk proses pengklusteran yaitu: 1. Jumlah kluster yang akan dibentuk. 2. Pembobot. 3. Maksimum iterasi. 4. Kriteria penghentian.

2.2.2. Pendekatan Teoritik Keputusan Pengenalan pola komputer dapat dipandang sebagai tugas yang berisikan ajar (learning) perilaku-perilaku invarian dan lazim dari sekumpulan sampel yang mencirikan sebuah kelas, dan memutuskan sebuah sampel baru. Langkah pengoperasian yang perlu dalam mengembangkan serta melaksanakan aturan keputusan dalam sistem pengenalan pola praktis, ditunjuk dalam blok-blok sebagai berikut: SISTEM FISIS

RUANG PENGUKURAN

RUANG CIRI (FEATURE)

RUANG KEPUTUSAN

Gambar 2.1. Tahap Pengoperasian Suatu sistem pengenalan pola

Sebuah sistem fisis untuk tujuan pengenalan pola ditandai oleh beberapa perwujudan fisisnya yang dinyatakan secara numerik yang membentuk ruang pengukuran. Pemilihan dan ekstraksi feature dalam pengenalan pola merupakan proses pemilihan sebuah pemetaan bentuk X = f(Y) yang berasal dari sampel Y(y 1 , y 2 ,...., y Q ) dalam ruang dimensi yang ditransformasi ke suatu titik X (x 1 , x 2 ,...., x N ). Fungsi f(Y) akan meminimumkan jarak dan memaksimumkan jarak dalam ruang feature. Proses penurunan sebuah aturan keputusan berdasarkan sekumpulan sampel untuk mengklasifikasi suatu titik dalam ruang feature terhadap sampel.


2.3. Algoritma Genetika 2.3.1. Pengertian Algoritma Genetika Menurut Desiani dan Arhami (2005), Algoritma genetika (AG) merupakan suatu algoritma pencarian yang berbasis pada mekanisme yang memanfaatkan proses seleksi alamiah yang dikenal dengan proses evolusi. Dalam proses evolusi, individu secara terus-menerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya dan hanya individu yang kuat yang mampu bertahan. Proses seleksi alamiah ini melibatkan perubahan gen yang terjadi pada individu melalui proses perkembangbiakan. Dalam algoritma genetika ini, proses perkembang-biakan ini menjadi proses dasar yang menjadi tujuan untuk mendapatkan keturunan yang lebih baik. Algoritma genetika (AG) adalah algoritma pencarian heuristik yang didasarkan atas mekanisme evolusi biologis. Keberagaman pada evolusi biologis adalah variasi dari kromosom antar individu organisme. Variasi kromosom ini akan mempengaruhi laju reproduksi dan tingkat kemampuan organisme untuk tetap bertahan hidup. Yang membedakan algoritma genetika dengan berbagai algoritma konvensional lainnya adalah bahwa algoritma memulai dengan suatu himpunan penyelesaian acak awal yang disebut populasi (Kusumadewi 2005). Algoritma genetika digunakan untuk penyelesaian masalah optimasi yang kompleks

dan

sukar

diselesaikan

dengan

menggunakan

metode

yang

konvensional. Sebagaimana halnya proses evolusi di alam, suatu algoritma genetika yang sederhana umumnya terdiri dari tiga operator yaitu: operator reproduksi, operator crossover (persilangan) dan operator mutasi. Struktur umum dari suatu algoritma genetika dapat didefinisikan dengan langkah-langkah sebagai berikut: 1. Membangkitkan populasi awal, Populasi awal ini dibangkitkan secara random sehingga didapatkan solusi awal. Populasi itu sendiri terdiri dari sejumlah kromosom yang merepresentasikan solusi yang diinginkan.


2. Membentuk generasi baru, Dalam membentuk digunakan tiga operator yang telah disebut di atas yaitu operator reproduksi/seleksi, crossover dan mutasi. Proses ini dilakukan berulang-ulang sehingga didapatkan jumlah kromosom yang cukup untuk membentuk generasi baru dimana generasi baru ini merupakan representasi dari solusi baru. 3. Evaluasi solusi, Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah 2. Sejak dikembangkan sampai saat ini GA ini terus menjadi objek riset dalam berbagai aplikasi. Alasan mengapa GA banyak menjanjikan, antara lain banyak problem dibidang sains dan teknik tidak dapat dipecahkan dengan algoritma deterministik biasa meskipun dengan waktu yang meningkat secara polynomial. Secara umum algoritma ini memiliki prosedur yang dapat dirumuskan sebagai berikut Procedure Genetic Algorithms Begin t←0 initialize P(t) evaluate P(t) while (not termination condition ) do begin recombine P(t) to yield C(t) evaluate C(t) select P(t+1) from P(t) and C(t) t ← t+1 end end

Dengan t = generasi, P(t)= Populasi pada generasi t, dan C(t)=Populasi tambahan atau individu baru (offspring) dari hasil proses operasi genetik Crossover dan Mutasi. 2.3.2. Encoding Dalam algoritma genetika pengkodean (encoding) solusi problem kedalam suatu kromosom merupakan isu penting. Populasi awal yang berisi N kromosom


dibangkitkan secara random yang menjangkau keseluruhan ruang solusi. Proses evolusi dilakukan dengan melakukan operasi genetik (cross-over dan mutasi) dan melakukan seleksi kromosom untuk generasi berikutnya sampai

sejumlah

generasi yang dikehendaki dengan panduan fungsi fitness. Algoritma genetika pada dua ruang, yaitu ruang solusi (disebut phenotip) dan ruang coding (disebut genotip). Operasi genetika (cross over dan mutasi) dilakukan pada ruang genotip sementara operasi seleksi dilakukan pada ruang phenotip. Dalam binary encoding variabel keputusan diwakili oleh deretan bit 0,1 yang panjangnya disesuaikan dengan ruang pencarian. Tiap bit 0,1 dapat dianggap sebagai sebuah gen. Untuk optimasi 2 variabel misalnya, maka solusi adalah x 1 dan x 2. Integer dan literal permutation encoding adalah kode terbaik untuk problem combinatorial optimization karena inti dari problem ini adalah mencari kombinasi atau permutasi terbaik dari item solusi terhadap kendala yang ada. Untuk problem yang lebih komplek encoding menggunakan data struktur yang lebih sesuai.

2.3.3. Fungsi Fitness Fungsi fitness adalah fungsi yang digunakan untuk menentukan apakah suatu kromosom layak bertahan. Pada setiap generasi dipilih kromosom yang mendekati solusi dengan mengevaluasi fungsi kecocokan dari kromosom tersebut. Fungsi ini didefinisikan sedemikian sehingga semakin besar nilai fitness semakin besar probabilitas untuk terseleksi pada generasi berikutnya. Untuk maksimasi maka fungsi tujuan dapat dijadikan sebagai fungsi fitness, sehingga kromosom yang mewakili nilai fungsi besar akan memiliki probabilitas terseleksi yang besar juga. Untuk minimasi dapat dirumuskan sedemikian sehingga fungsi tujuan yang semakin kecil maka memiliki fungsi fitness yang besar (Fadlisyah 2009). Pada penyelesaian yang berada diluar daerah visible dapat digunakan suatu modifikasi fungsi fitness dengan menambahkan suatu fungsi yang sering disebut sebagai fungsi penalti, sehingga fungsi fitness menjadi:


fitness(x) = f(x)+p(x)

2.3.4. Seleksi Setiap anggota populasi diwakili deretan string (disebut kromosom) dengan panjang tertentu. Elemen string tersebut dapat berupa digit 0,1 (untuk binary encoding), bilangan real (untuk real encoding), atau elemen lain. Untuk ukuran populasi N yang biasanya dipertahankan tetap prosedur seleksi diperlukan untuk memilih anggota populasi yang mana yang akan tetap eksis pada generasi berikutnya. Fungsi fitness digunakan untuk menentukan apakah kromosom layak dipertahankan atau tidak dalam generasi berikutnya. Sebelum dilakukan seleksi jumlah anggota populasi ditambah dengan hasil offspring dari proses operasi genetik yang dapat berupa cross over dan mutasi. Hasil operasi genetik dan populasi semula selanjutnya diseleksi dengan metode tertentu untuk diambil n anggota populasi yang terbaik. Untuk kasus minimasi maka yang terpilih adalah n anggota populasi dengan nilai fitness yang terkecil.

2.3.5. Crossover Proses operasi crossover dirancang untuk mencari kemungkinan yang lebih baik dari anggota populasi yang telah ada. Dari pasangan induk yang terpilih berdasarkan seleksi fungsi fitness diambil sejumlah pasangan dengan probabilitas P c untuk dikenakan operasi crossover.

2.3.6. Mutasi Mutasi dalam konteks binary encoding adalah perubahan pada bit tunggal (bit 0 jadi 1 dan sebaliknya) anggota populasi yang terpilih. Banyaknya bit yang mengalami mutasi pada setiap generasi diatur oleh probabilitas mutasi (P m ) yang nilainya merupakan cacah bit mutasi dibagi cacah bit total dalam populasi (Widyastuti dan Hamzah 2007).


2.3.7. Konsep Penggunaan Algoritma Genetika (GA) GA bekerja dengan modalitas coding dari set parameter, tetapi tidak menghitung parameter sendiri. Setiap langkah di GA adalah mencari solusi dari suatu kelompok ke kelompok lain dalam ruang solusi bukan dari solusi untuk solusi lain. GA memanfaatkan probabilitas transisi dari aturan kepastian. GA hanya memanfaatkan informasi fungsi objek tetapi tidak proses derivasi dan informasi tambahan lainnya. GA disediakan dengan paralelisme operasi, dan dapat menilai beberapa data atau titik pada waktu yang sama dalam ruang pencarian yang rumit, yang hasilnya adalah tepat untuk mencari solusi optimal global dalam ruang solusi multi-nilai. Hal ini merawat kualitas individu kelompok berkembang setiap kali dalam proses GA, yaitu kualitas solusi masalah, yang berbeda dari algoritma optimasi banyak yang membutuhkan informasi rekursif atau semua informasi dari masalah seperti struktur dan parameter. Sehingga, GA sangat cocok untuk solusi masalah waktu yang tidak terbatas atau masalah nonlinier yang rumit (Wang 2008).

2.4.

Logika Fuzzy

2.4.1 Pengertian Logika Fuzzy Fuzzy secara bahasa diartikan sebagai kabur atau samar-samar. Suatu nilai dapat bernilai besar atau salah secara bersamaan. Dalam fuzzy dikenal derajat keanggotaan yang memiliki rentang nilai 0 (nol) hingga 1(satu). Berbeda dengan himpunan tegas yang memiliki nilai 1 atau 0 (ya atau tidak). Logika Fuzzy merupakan suatu logika yang memiliki nilai kekaburan atau kesamaran (fuzzyness) antara benar atau salah. Dalam teori logika fuzzy suatu nilai bias bernilai benar atau salah secara bersama. Namun berapa besar keberadaan dan kesalahan suatu tergantung pada bobot keanggotaan yang dimilikinya. Logika fuzzy memiliki derajat keanggotaan dalam rentang 0 hingga 1. Berbeda dengan logika digital yang hanya memiliki dua nilai 1 atau 0.


Logika fuzzy digunakan untuk menterjemahkan suatu besaran yang diekspresikan menggunakan bahasa (linguistic), misalkan besaran kecepatan laju kendaraan yang diekspresikan dengan pelan, agak cepat, cepat, dan sangat cepat. Dan logika fuzzy menunjukan sejauh mana suatu nilai itu benar dan sejauh mana suatu nilai itu salah. Tidak seperti logika klasik (scrisp)/tegas, suatu nilai hanya mempunyai 2 kemungkinan yaitu merupakan suatu anggota himpunan atau tidak. Derajat keanggotaan 0 (nol) artinya nilai bukan merupakan anggota himpunan dan 1 (satu) berarti nilai tersebut adalah anggota himpunan. Logika fuzzy adalah suatu cara yang tepat untuk memetakan suatu ruang input kedalam suatu ruang output, mempunyai nilai kontiniu. Fuzzy dinyatakan dalam derajat dari suatu keanggotaan dan derajat dari kebenaran. Oleh sebab itu sesuatu dapat dikatakan sebagian benar dan sebagian salah pada waktu yang sama (Kusumadewi 2006). Kelebihan dari teori logika fuzzy adalah kemampuan dalam proses penalaran secara bahasa (linguistic reasoning). Sehingga dalam perancangannya tidak memerlukan persamaan matematik dari objek yang akan dikendalikan.

2.4.2. Fungsi Keanggotaan Dalam penelitian ini untuk mendapatkan derajat keanggotaan adalah dengan pendekatan fungsi keanggotaan yang direpresentasikan dalam bentuk kurva bahu. Membership function ditentukan dari awal yang direpresentasikan menggunakan kurva bahu. Dalam kluster, untuk menggabungkan dua atau lebih obyek menjadi satu kluster dengan menggunakan ukuran kemiripan atau ketidakmiripan. Semakin mirip dua obyek semakin tinggi peluang untuk dikelompokkan dalam satu kluster. Sebaliknya semakin tidak mirip semakin rendah peluang untuk dikelompokkan dalam satu kluster. Untuk mengukur kemiripan (similiarity) dan ketidakmiripan (dissimiliarity) diantara data atau obyek dapat dipakai beberapa ukuran, diantaranya:


1. Cosinus antara dua titik x dan y didefinisikan sebagai:

xT y cos θ = ................................................................ (2.3) x y n

dimana x didefinisikan sebagai

∑x i =1

2 i

2. Kovarian Kovarian antara dua data didefinisikan sebagai berikut: cov( x, y ) =

1 n ∑ ( X i − X )(Yi − Υ ) .......................................... (2.4) n i =1

dimana x adalah data pertama dan y data kedua. 3. Koefisien korelasi

r ( x, y ) =

cov( x, y ) ............................................................... (2.5) σ xσ y

2.4.3. Proses Sistem Fuzzy Sebuah sistem fuzzy akan memiliki struktur proses sebagai berikut: 1. Fuzzification (fuzzifikasi), yaitu proses memetakan crisp input ke dalam himpunan fuzzy. Hasil dari proses ini berupa fuzzy input dalam bentuk rule fuzzy. 2. Rule evaluation (rule evaluasi), yaitu proses melakukan penalaran terhadap fuzzy input yang dihasilkan oleh proses fuzzification berdasarkan aturan fuzzy yang telah dibuat. Proses ini menghasilkan fuzzy output. 3. Defuzzification (defuzzifikasi), yaitu proses mengubah fuzzy output menjadi crisp value. Metode defuzzifikasi yang paling sering


digunakan adalah metode centroid dan metode largest of maximum (LOM).

2.5.

Fuzzy Clustering

Fuzzy clustering adalah salah satu teknik untuk menentukan kluster optimal dalam suatu ruang vektor yang didasarkan pada bentuk normal euclidian untuk jarak antar vektor. Fuzzy clustering sangat berguna bagi pemodelan fuzzy terutama dalam mengindentifikasi aturan-aturan fuzzy. Metode clustering merupakan pengelompokkan data beserta parameternya dalam kelompok-kelompok sesuai kecenderungan sifat dari masing-masing data tersebut (kesamaan sifat) (Kusumadewi 2004). Ada dua pendekatan dalam clustering yaitu partisioning dan hirarki. Dalam postioning, dengan mengelompokkan obyek x 1 , x 2 ,...,x n kedalam c kluster. Hal ini dilakukan untuk menentukan pusat kluster awal, lalu dilakukan realokasi obyek berdasarkan kriteria tertentu sampai dicapai pengelompokkan yang optimum. Sedangkan dalam kluster hirarki yaitu dengan membuat m kluster dimana setiap kluster beranggotakan satu obyek dan berakhir dengan satu kluster dimana anggotanya adalah m obyek. Pada setiap tahap prosedurnya, satu kluster digabung dengan satu kluster yang lain. Lalu dengan memilih berapa jumlah kluster yang diinginkan dengan menentukan cut-off pada tingkat tertentu.

2.5.1. Algoritma Fuzzy Clustering dengan Pendekatan Algoritma Genetika (Genetic Guided Algorithm for Fuzzy C-Means = GGA-FCM) Pada pendekatan algoritma genetika untuk penyelesaian fuzzy clustering ditempuh pilihan untuk menggunakan pendekatan Prototype-based algorithms, yaitu mengevolusikan matrik pusat kluster V. Beberapa hal yang ditentukan adalah: Fungsi Fitness: Fungsi fitness yang digunakan adalah objective function Jm, yaitu:


c

n

Jm( U, V) = ∑ ∑ µ ik Dik (v i − x k ) ........................................... (2.6) 2

i =1 k =1

Encoding dan Struktur kromosom: Encoding yang digunakan adalah real encoding. Struktur kromosom untuk V dalam populasi yang dievolusikan adalahvektor real beranggotakan cxp elemen (c=cacah kluster dan p cacah elemen dalam objek).

Gambar 2.2. Struktur Kromosom untuk Encoding V Berdasarkan Algoritma Genetika digunakan fuzzy clustering untuk mengatasi 6 hal yaitu (Wang 2008): 1. Menghasilkan kelompok awal. Populasi awal terdiri dari individu awal yang dihasilkan secara acak yang jumlahnya popsize. Delegasi kromosom A data titik, yaitu berisi lokasi setiap data dalam pengelompokan ruang. Jika jumlah popsize terlalu kecil, situasi akan keluar keragaman, jika jumlah popsize terlalu besar, clustering akan menghabiskan banyak waktu. 2. Menentukan pengkodean. Metode pengkodean tidak hanya menentukan bentuk permutasi kromosom individu, tetapi juga metode decoding individu dari genotipe transformasi ruang pencarian untuk fenotipe ruang solusi. Metode coding juga mempengaruhi pengoperasian GA, seperti operator crossover, operator mutasi dan sebagainya. Mencari clustering pusat dalam kelompok data titik memerlukan analisis clustering, setiap titik data dapat menjadi pusat kluster atau tidak. Ini akan menghadapi masalah jika setiap pemilihan harus dinyatakan dengan pengkodean bahwa: jika struktur pengkodean rumit, penghitungan ini akan menjadi lebih kompleks ketika jumlah titik data yang besar. Oleh karena itu, pada desain metode coding, sangat nyaman untuk


memilih coding, pengkodean dan operasi crossover dan kemudian proses pengkodean biner. 3. Menentukan fungsi fitness. Hal ini mencerminkan bahwa seberapa kuat kemampuan pas individu untuk keadaan adalah dengan fungsi fitness. 4. Untuk menentukan metode operasi GA. Dalam operasi GA, metode yang harus ditentukan adalah terutama pemilihan, metode metode crossover dan mutasi. 5. Seleksi operator. Dalam rangka warisan biologis dan evolusi alam, spesies yang memiliki daya adaptasi lebih tinggi untuk lingkungan hidup, akan memperoleh lebih banyak kesempatan untuk menyebarkan ke generasi berikutnya, sedangkan yang lebih rendah akan mendapatkan lebih sedikit.

Meniru kursus ini, GA membuat

individu dari grup diproses "kelangsungan bagi yang terkuat" dengan memanfaatkan operator seleksi. 6. Crossover operator. Dalam tesis ini, operator crossover menerapkan metode persimpangan duatitik. Probabilitas crossover tidak boleh terlalu kecil karena operasi crossover adalah pencarian global, mungkin dari 90 % menjadi 100 %.

2.5.2. Parameter dalam Algoritma Genetika Parameter dalam dalam algoritma genetika adalah hal yang harus ditentukan dalam mengimplementasikan algoritma genetika ke dalam penyelesaian masalah. Parameter ini menentukan ukuran populasi, probabilitas penyilangan (Pc), dan probabilitas mutasi. Probabilitas mutasi (Pm) dalam algoritma genetika seharusnya diberi nilai yang kecil karena tujuan mutasi adalah untuk menjaga perbedaan kromosom dalam populasi sehingga dapat menghindari konvergensi prematur. Parameter lain yang ikut berperan untuk menjaga efisiensi kinerja algoritma genetika adalah ukuran populasi (popsize). Parameter ini menunjukkan banyaknya kromosom dalam satu populasi. Jika jumlah kromosom dalam populasi


terlalu sedikit maka algoritma genetika hanya mempunyai probabilitas yang kecil untuk melakukan penyilangan. Sebaliknya, jika jumlah kromosom dalam populasi terlalu banyak, maka algoritma genetika akan cenderung lambat dalam menemukan solusi.

Algoritma Genetika Untuk Fuzzy Clustering Algoritma genetika (GA) sebagai teknik optimasi dapat diterapkan pada clustering yang berbasis optimasi fungsi tujuan. Pada pendekatan GA untuk fuzzy clustering fungsi fitness diambil dari fungsi objektif yang diminimumkan, yaitu Jm (U,V) (Widyastuti dan Hamzah 2007).

2.5.3. Validitas Clustering dan Classification Rate Hasil akhir FCM atau GGA-FCM adalah V,U dan Rm tertentu untuk suatu c yang diinputkan. Pada beberapa kasus c yang tepat mungkin tidak diketahui. Untuk itu beberapa pendekatan telah diusulkan untuk menentukan berapa sebaiknya c sehingga hasil clustering dapat dianggap terbaik. Ukuran ini dikenal sebagai validitas clustering. 2.5.4. Algoritma Fuzzy Clustering konvensional Berikut diuraikan algoritma fuzzy clustering konvensional, yaitu penyelesaian fuzzy clustering dengan cara iteratif dengan melakukan update pada matrik keanggotan U dan matrik prototipe kluster V. Dalam algoritma diperlukan sampel objek sebanyak n 1 , tiap objek p parameter, dituliskan : X ={x 1 , x 2 ,.... ,x n } x i ∈ RP I = 1,2,…,n. Ditentukan dalam proses penyelesaian melalui iterasi : U = [µ ικ ] matrik ukuran cxn ; i=1,2,…,c ; k =1,2,…,n; V={v1,v2,…,vc} i=1,2,…,c.


Berikut adalah algoritma yang diajukan : 1. Initialization step: Tentukan: n = cacah objek yang akan dikluster; p = cacah parameter dalam tiap objek; c = cacah kluster; t = 0 (iterasi ke); m = derajat fuzziness = dipilih 2;

ε =nilai yang cukup kecil mendekati 0 Tentukan secara acak : U(0) dan V(0)

2. Iteration step : a) Dengan menggunakan U(t), hitung pusat kluster V(t) menurut rumus :

Vi =

n

1

µ ik

m

∑µ k =1

m

xik

ik

...........................................................................

(2.7)

Untuk i=1,2,...,c. b) Dengan menggunakan V(t) , hitung derajat keanggotaan dengan rumus: 1 /( m −1)

µ ik

  1   2  x k − vi  = c  1  ∑ j =1  x − v j  k

c) Jika max ( µ ik

(t )

− µ ik

  2  

m

( t −1)

........................................................ (2.8)

) < ε berhenti, Jika tidak ulangi langkah

2.a.

2.5.5. Fuzzy C-Means Ada beberapa algoritma clustering data, salah satu diantaranya adalah Fuzzy CMeans. Fuzzy C-Means adalah suatu teknik pengklusteran yang mana keberadaannya tiap-tiap titik data dalam suatu kluster ditentukan oleh derajat keanggotaan. Teknik ini pertama kali diperkenalkan oleh Jim Bezdek pada tahun 1981. Fuzzy C-means Clustering (FCM), atau dikenal juga sebagai Fuzzy ISODATA, merupakan salah satu metode clustering yang merupakan bagian dari metode Hard K-Means. FCM menggunakan model pengelompokan fuzzy


sehingga data dapat menjadi anggota dari semua kelas atau kluster terbentuk dengan derajat atau tingkat keanggotaan yang berbeda antara 0 hingga 1. Konsep dari Fuzzy C-Means pertama kali adalah menentukan pusat kluster, yang akan menandai lokasi rata-rata untuk tiap-tiap kluster. Pada kondisi awal, pusat kluster ini masih belum akurat. Tiap-tiap titik data memiliki derajat keanggotaan untuk tiap-tiap kluster. Dengan cara memperbaiki pusat kluster dan derajat keanggotaan tiap-tiap titik data secara berulang, maka akan dapat dilihat bahwa pusat kluster akan bergerak menuju lokasi yang tepat. Perulangan ini didasarkan pada minimasi fungsi obyektif yang menggambarkan jarak dari titik data yang diberikan kepusat kluster yang terbobot oleh derajat keanggotaan titik data tersebut. Output dari Fuzzy C-Means merupakan deretan pusat kluster dan beberapa derajat keanggotaan untuk tiap-tiap titik data. Informasi ini dapat digunakan untuk membangun suatu fuzzy inference system.

Algoritma Fuzzy C-Means Algoritma Fuzzy C-Means adalah sebagai berikut (Ross, 2005): 1. Input data yang akan dikluster X, berupa matriks berukuran n x m (n=jumlah sample data, m=atribut setiap data). X = data sample kei (i=1,2,…,n), atribut ke-j (j=1,2,…,m). 2. Tentukan: a. Jumlah kluster = c; b. Pangkat = w; c. Maksimum iterasi = MaxIter; d. Error terkecil yang diharapkan = ζ; e. Fungsi obyektif awal = P=0; f. Iterasi awal = t=1; 3. Bangkitkan nilai acak μ ik , i=1,2,…,n; k=1,2,…,c; sebagai elemenelemen matriks partisi awal u.


μ ik adalah derajat keanggotaan yang merujuk pada seberapa besar kemungkinan suatu data bisa menjadi anggota ke dalam suatu kluster. Posisi dan nilai matriks dibangun secara random. Dimana nilai keangotaan terletak pada interval 0 sampai dengan 1. Pada posisi awal matriks partisi U masih belum akurat begitu juga pusat klusternya. Sehingga kecendrungan data untuk masuk suatu kluster juga belum akurat. Hitung jumlah setiap kolom (atribut).


BAB II TINJAUAN PUSTAKA

Recommend Documents