Metode Anti Spam

Beberapa Metode Anti Spam

            Telah terdapat beberapa metode yang dapat digunakan untuk mencegah spam diantaranya :

a.    Keyword filtering

Metode ini merupakan Application Layer Filtering (ALF). Dengan metode ini, spam di-blok berdasarkan kata-kata tertentu yang sering dituliskan pada spam-mail misalnya :  “sex”, atau “hot sexy babes”.

b.    Address blocking

Metode ini memblok spam-mail berdasarkan IP atau domain atau alamat e-mail tertentu yang telah dikategorikan sebagai alamat spammer. 

c.    Black listing

Metode ini hampir sama dengan address blocking, yaitu mem-blok spam berdasarkan list alamat spammers yang telah diketahui. Biasanya black listing ini dikerjakan oleh beberapa sukarelawan dan dibuat dalam bentuk database spam-mail, sehingga dapat digunakan oleh semua orang. Salah satu black listing yang dapat diakses adalah Open Relay Data Base, ORDB.org.

d.    White Listing

Kebalikan dengan Black listing, white listing berisi daftar alamat yang dikategorikan sebagai pengirim e-mail yang sah (legitimate mail). Alamat pengirim mail yang tidak termasuk dalam daftar ini akan diasumsikan sebagai spam-mail.

  

e.    Signature –Based Filtering

Metode ini akan membandingkan e-mail yang datang dengan spam-mail yang telah diketahui. Hal ini dilakukan dengan membuat beberapa alamat e-mail palsu. Spam-mail yang biasanya dikirim ke beratus-ratus alamat e-mail juga akan dikirim ke alamat-alamat palsu ini. Sehingga dengan membuat list alamat-alamat mana saja yang mengirim mail ke alamat palsu ini, spam mail dapat diblok. Salah satu cara untuk menunjukkan bahwa dua buah e-mail sama dilakukan dengan memberikan “signature” pada setiap e-mail. Metode untuk memberikan signature antara lain dengan memberikan angka untuk setiap huruf, lalu semua angka tersebut dijumlahkan. Sehingga setiap e-mail akan memiliki “signature” yang berbeda. Dalam hal ini, dua e-mail yang memiliki signature yang sama, dan dikirim ke beberapa alamat dapat dikategorikan sebagai spam-mail. Cara inilah yang diterapkan pada signature-based filtering. Tetapi metode filter ini sangat mudah dikalahkan oleh spammers. Cukup dengan menambahkan sembarang karakter yang berbeda pada setiap copy spam-mail, akan membuat copy spam-mail itu memiliki signature yang berbeda. Sehingga metode ini tidak terlalu efektif untuk mem-filter spam.   

f.      Bayesian (Statistical) Filtering

Metode Bayesian Filtering merupakan metode anti spam filter yang terbaru. Metode ini mengenali spam berdasarkan kata-kata (token) yang terkandung pada sebuah e-mail. Metode filter ini pertama kali perlu di-“training” menggunakan dua koleksi e-mail, satu koleksi merupakan spam-mail, dan koleksi yang lain merupakan legitimate mail. Dengan cara seperti ini, pada setiap e-mail baru yang diterima, Bayesian filter dapat memperkirakan probabilitas spam berdasarkan kata-kata yang sering muncul di koleksi spam-mail atau di koleksi legitimate mail. Bayesian filter efektif untuk mem-blok spam karena filter ini dapat secara otomatis mengkategorikan spam-mail atau legitimate mail.

g.    Rule-based (heuristic) filtering

Filter ini mem-blok spam-mail dengan mencari pola karakteristik tertentu yang mengindikasikan spam contohnya : kata-kata “kotor”, kata dengan banyak huruf besar atau banyak tanda seru, atau tanggal pengiriman yang tidak tepat. Kekurangan dari metode ini adalah rule (aturan ) yang digunakan bersifat statis, sehingga jika spammers menggunakan pola baru untuk mengirim spam-mail, aturan yang baru harus diberikan pada filter. Sedangkan pada Bayesian filter, kita cukup memberitahu filter bahwa pengklasifikasian e-mail yang dilakukannya salah, maka Bayesian filter akan secara otomatis mempelajari pola yang terdapat pada e-mail tersebut.

h.    Challenge-response filtering

Jika kita memperoleh e-mail pertama kalinya dari seseorang, maka challenge-response filter akan mengirim e-mail kembali ke alamat pengirim tersebut  dan memerintahkannya untuk meng-akses alamat web tertentu dan mengisi suatu form sebelum e-mail yang ia kirim dapat kita terima. Dengan cara seperti ini, kita dapat mem-filter spam dengan akurat. Karena hanya pengirim yang benar-benar berkepentingan dengan kita yang akan melaksanakan prosedur tersebut. Tetapi metode ini dapat dikatakan “kasar”, karena membuat orang lain melakukan pekerjaan ekstra untuk mengirim e-mail kepada kita. Selain itu kekurangan metode ini adalah legitimate e-mail dapat hilang atau terlambat sampai, karena pengirimnya tidak mengetahui bahwa ia harus melakukan suatu prosedur dari challenge-response filter agar e-mailnya dapat diterima. Kekurangan yang lain adalah karena filter ini hanya menyeleksi e-mail berdasarkan alamat pengirimnya, maka spammers yang melakukan spoofing akan mampu menaklukkan filter ini. Sehingga filter ini tidak terlalu efektif untuk mem-blok spam-mail. Cara yang dapat dilakukan adalah dengan mengkombinasikan filter ini dengan Bayesian filter, yaitu e-mail yang dikategorikan sebagai spam oleh Bayesian filter, di-challenge kembali oleh challenge-response filter ini. Dengan cara seperti ini, keakuratan Bayesian filter akan bertambah, dan challenge-response filter juga dapat digunakan dengan efektif. 

i.      E-mail minefield

Metode ini dilakukan dengan menambahkan sejumlah alamat e-mail palsu pada bagian alamat suatu situs, sehingga e-mail yang dikirimkan ke alamat tersebut dapat disimpulkan sebagai spam. Spammers biasanya mencoba untuk memalsukan header message atau IP address yang mereka gunakan. Tetapi pada transaksi SMTP dari spammers ke alamat minefield, terdapat suatu mekanisme tertentu yang mengharuskan spammers menyatakan IP address yang sebenarnya. Dengan mekanisme seperti ini, situs yang menjadi target spamming dan situs-situs lain yang terkait dengan situs target dapat mem-“black-list” IP address tersebut secara bersamaan (realtime shared minefield). Sehingga pemblokiran suatu IP address spammer dapat dilakukan dengan cepat.

Karena metode yang paling akurat untuk memfilter spam adalah dengan menggunakan algoritma Bayesian filter, maka algoritma ini akan dibahas lebih mendalam pada paper ini. Software-software anti-spam yang tersedia, tidak hanya menggunakan satu metode tertentu saja untuk memfilter spam, tetapi biasanya menggunakan kombinasi dari beberapa metode. Dengan cara seperti ini kelebihan dan kekurangan dari suatu metode akan melengkapi kelebihan dan kekurangan metode lain. 

Feature Transformation

Scale-invariant feature transform (atau SIFT) adalah sebuah algoritma dalam Computer vision untuk mendeteksi dan mendeskripsikan fitur-fitur lokal dari citra. Algoritma ini dipublikasikan oleh David Lowe pada tahun 1999.

Pendeteksian dan pendeskripsian fitur-fitur lokal dapat dipergunakan dalam aplikasi pengenalan obyek dan tracking. SIFT memiliki ketahanan yang kuat terhadap penskalaan, rotasi dan perubahan sudut pandang citra. SIFT juga tahan terhadap perubahan intensitas pencahayaan dan noise.

SIFT mendeteksi fitur-fitur lokal yang relatif banyak dalam sebuah citra. Jika SIFT diaplikasikan untuk tracking, hal ini bisa berpengaruh terhadap waktu komputasinya. Untuk itu, ada sebuah algoritma yang merupakan pengembangan dari SIFT yakni SURF (Speeded-Up Robust Features) yang memiliki waktu komputasi lebih cepat dari SIFT. SURF menggunakan integral citra dan box filter dalam komputasi fitur-fitur lokalnya. Fast Approximated SIFT juga adalah hasil pengembangan SIFT dalam hal kecepatan waktu komputasi. Perbedaannya, Fast Approximated SIFT juga menggunakan integral citra dan box filter untuk mempercepat waktu komputasi dan juga menggunakan Difference-of-Mean (DoM) pada pembentukan skala ruang (scale space). DI bawah ini adalah beberapa contoh gambar yang merupakan aplikasi dari SIFT. Citra yang kecil (Istana Kepresidenan RI) merupakan citra terget yang akan dicari pada citra uji(citra ukuran besar-Peta Jakarta di atas Monas). Garis-garis putih menunjukkan fitur-fitur yang cocok antara citra target dan citra uji. Algoritma-algoritma computer vision di atas dapat diaplikasikan dalam aplikasi pengenalan obyek, pendeteksian obyek, tracking. Biasanya diaplikasikan untuk peluru kendali(DSMAC), robot(sensor kamera robot), autonomous vehicle, dll.

Scale Invariant Feature Transform (SIFT) adalah sebuah metode untuk mendeteksi dan mendeskripsikan fitur lokal invarian khas dari gambar yang dapat digunakan untuk melakukan pencocokan handal antara tampilan gambar yang berbeda pada objek dan scene-nya.

         Aplikasi yang dapat diterapkan dari algoritma ini misalnya object recognition, robotic mapping dan navigation, image stitching, 3D modeling, video tracking, individual identification, dll. Algoritma ini dipublikasikan oleh David Lowe pada tahun 1999.

         SIFT mengubah data dari gambar ke dalam koordinat relatif skala-invarian terhadap fitur lokal. Untuk Image matching, fitur SIFT pertama kali diambil dari satu set gambar referensi dan disimpan dalam database. Gambar baru dapat dicocokkan secara otomatis dengan membandingkan setiap fitur dari gambar baru ke database sebelumnya dan menemukan calon match fitur berdasarkan second-closet nearest neighbor sebagai tetangga terdekat yang dideteksi sebagai match feature dari fitur vektor gambar refrensi.

Algoritma ini memiliki ketahanan yang cukup kuat terhadap penskalaan, rotasi dan perubahan sudut pandang citra. Algoritma ini  juga tahan terhadap perubahan intensitas pencahayaan dan noise. Terdapat empat tahapan yang harus dilakukan dalam algoritma SIFT ini yaitu :

a.       Scale-space extrema detection

b.      Keypoint localization

c.       Orientation assignment

d.      Keypoint descriptors

FEATURE SELECTION

Feature Selection atau Feature Reduction adalah suatu kegiatan yang umumnya bisa dilakukan secara preprocessing dan bertujuan untuk memilih feature yang berpengaruh dan mengesampingkan feature yang tidak berpengaruh dalam suatu kegiatan pemodelan atau penganalisaan data. Ada banyak alternatif yang bisa digunakan dan harus dicoba-coba untuk mencari yang cocok. Secara garis besar ada dua kelompok besar dalam pelaksanaan feature selection: Ranking Selection dan Subset Selection.
Ranking Selection
Ranking selection secara khusus memberikan ranking pada setiap feature yang ada dan mengesampingkan feature yang tidak memenuhi standar tertentu. Ranking selection menentukan tingkat ranking secara independent antara satu feature dengan feature yang lainnya. Feature yang mempunyai ranking tinggi akan digunakan dan yang rendah akan dikesampingkan. Ranking selection ini biasanya menggunakan beberapa cara dalam memberikan nilai ranking pada setiap feature misalnya regression, correlation, mutual information dan lain-lain.
Subset Selection
Subset selection adalah metode selection yang mencari suatu set dari features yang dianggap sebagai optimal feature. Ada tiga jenis metode yang bisa digunakan yaitu selection dengan tipe wrapper, selection dengan tipe filter dan selection dengan tipe embedded.
Feature Selection Tipe Wrapper: feature selection tipe wrapper ini melakukan feature selection dengan melakukan pemilihan bersamaan dengan pelaksanaan pemodelan. Selection tipe ini menggunakan suatu criterion yang memanfaatkan classification rate dari metode pengklasifikasian/pemodelan yang digunakan. Untuk mengurangi computational cost, proses pemilihan umumnya dilakukan dengan memanfaatkan classification rate dari metode pengklasifikasian/pemodelan untuk pemodelan dengan nilai terendah (misalnya dalam kNN, menggunakan nilai k terendah). Untuk tipe wrapper, perlu untuk terlebih dahulu melakukan feature subset selection sebelum menentukan subset mana yang merupakan subset dengan ranking terbaik. Feature subset selection bisa dilakukan dengan memanfaatkan metode sequential forward selection (dari satu menjadi banyak feature), sequential backward selection (dari banyak menjadi satu), sequential floating selection (bisa dari mana saja), GA, Greedy Search, Hill Climbing, Simulated Annealing, among others.
Feature Selection Tipe Filter: feature selection dengan tipe filter hampir sama dengan selection tipe wrapper dengan menggunakan intrinsic statistical properties dari data. Tipe filter berbeda dari tipe wrapper dalam hal pengkajian feature yang tidak dilakukan bersamaan dengan pemodelan yang dilakukan. Selection ini dilakukan dengan memanfaatkan salah satu dari beberapa jenis filter yang ada. Contohnya: Individual Merit-Base Feature Selection dengan selection criterion: Fisher Criterion, Bhattacharyya, Mahalanobis Distance atau Divergence, Kullback-Leibler Distance, Entropy dan lain-lain. Metode filter ini memilih umumnya dilakukan pada tahapan preprocessing dan mempunyai computational cost yang rendah.
Feature Selection Tipe Embedded: feature selection jenis ini memanfaatkan suatu learning machine dalam proses feature selection. Dalam sistem selection ini, feature secara natural dihilangkan, apabila learning machine menganggap feature tersebut tidak begitu berpengaruh. Beberapa learning machine yang bisa digunakan antara lain: Decision Trees, Random Forests dan lain-lain.

• Chi-χ^2 (Chi-Square)

Chi-χ^2 mengukur keterhubungan atau ketergantungan suatu kata, w_k, dengan sebuah kategori, c_i. χ^2 dapat didefinisikan secara matematis menurut rumus berikut. [dimensionality reduction technique for enhancing automatic TC-Dina Adel Said]
χ^2 (w_k,c_i )= (N(tr)×〖[A*D- C*B]〗^2)/([A+C]*[B+D]*[A+B]*[C+D] ) …(1)
Dimana :
N(Tr) : jumlah dokumen dalam training set
A : jumlah dokumen dalam c_i yang mengandung w_k
B : jumlah dokumen yang bukan kategori c_i, tapi mengandung w_k
C : jumlah dokumen dalam c_i yang tidak mengandung w_k
D : jumlah dokumen yang tidak dalam c_i dan tidak mengandung w_k
Seperti yang telah dijelaskan sebelumnya, Chi-Square adalah metode testing terhadap sebuah hipotesis yang diambil dari statistika, yang mengevaluasi korelasi diantara dua variabel (dalam hal ini kata (term) dengan kategori) dan menentukan apakah keduanya independen atau berhubungan[Naïve Bayesian on chi square to categorize arabic data—fadi thabtah, dkk]. Jika nilai χ^2= 0, maka tidak ada hubungan atau korelasi diantara dua variabel tersebut.
Proses pemilihan fitur untuk tugas akhir ini juga berdasarkan pada prinsip tersebut. Dokumen yang telah di pre-processing (case folding, tokenizing, stopwords removal, stemming) kemudian dilakukan pengurangan dimensi. Perhitungan chi-square (χ^2) dilakukan terhadap semua token pada setiap kategorinya. Kemudian token dengan nilai χ^2=0 tidak digunakan sebagai fitur dalam proses learning. Selain itu, digunakan sebuah threshold yang digunakan untuk menentukan tingkat korelasi dari kata tersebut dengan kategorinya. Nilai threshold itu sendiri ditentukan dengan beberapa kali percobaan sehingga didapatkan threshold yang sesuai.

• Information Gain

Information Gain (IG) dari suatu term diukur dengan menghitung jumlah bit informasi yang diambil dari prediksi kategori dengan ada atau tidaknya term dalam suatu dokumen. Secara matematis dapat dituliskan sebagai berikut. [Evolutionary Feature Selection for Text Documents using the SVM-Daniel I. Morariu, Lucian N. Vintan, and Volker Tresp]
InfoGain (S,A)=Entropy(S)- ∑_(v ∈ Value(A))〖(|S_v |)/S 〗 Entropy (S_v) … (2)
Entropy (S)= -∑(〖|S〗_i |)/S log2〖S_i/S〗 … (3)
Dimana :
S : Jumlah seluruh fitur
A : kategori
S_v : jumlah sampel untuk nilai v
v : nilai yang mungkin untuk kategori A
S_i : fitur ke i
value(A) : himpunan nilai-nilai yang mungkin untuk kategori A
Ide dibalik Information gain untuk memilih fitur adalah menyatakan fitur dengan informasi yang paling signifikan terhadap kelas. [IGFS for ordinal TC using Probability Re-distribution—Rahman Mukras, dkk.]. Fitur yang dipilih adalah fitur dengan nilai Information Gain yang tidak sama dengan nol dan lebih besar dari suatu nilai threshold tertentu[a hybrid FS method for microarray classification—cheng-san yang, dkk].

28 Feb

Feature Selection

Posted by IkaSofiana in cin-TA kuuu. Tagged: dimensionalitas, feature selection, filter, wrapper. Leave a comment

Assalamu’alaikum wr wb Minna..
Seperti yang telah dijelaskan sebelumnya, dimensionalitas dari suatu dokumen bisa menjadi sangat tinggi, sehingga diperlukan suatu mekanisme untuk mengurangi feature tersebut sehingga meningkatkan efisiensi klasifikasi dan mengurangi kompleksitas komputasi. Salah satu caranya adalah dengan feature selection.

• Konsep Feature Selection

Ada dua pendekatan dalam feature selection, yaitu pendekatan filter dan pendekatan wrapper. Dalam pendekatan filter, setiap fitur dievaluasi secara independen sehubungan dengan label kelas dalam training set dan menentukan peringkat dari semua fitur, dimana fitur dengan peringkat teratas yang dipilih. Pendekatan wrapper menggunakan metode pencarian kecerdasan buatan klasik seperti greedy hill-climbing atau simulated-annealing untuk mencari subset terbaik dari fitur, dan secara berulang-ulang mengevaluasi subset fitur yang berbeda dengan cross validation dan algoritma induksi tertentu.
Selain itu, metode dalam feature selection juga dibagi menjadi dua, yaitu forward selection dan backward selection, dimana dalam forward selection dimulai dengan tidak ada fitur dan menambahnya satu persatu sampai tidak ada lagi fitur yang dapat menurunkan error secara signifikan, dan backward selection dimulai dengan seluruh fitur yang ada kemudian dikurangi satu persatu sampai jika fitur dikurangi lagi, maka error akan meningkat secara signifikan.
Manfaat dari pemilihan fitur ini sendiri adalah [L.Ladha]:

1. Mengurangi dimensionalitas feature space, sehingga mengurangi kebutuhan storage dan meningkatkan kecepatan algoritma.
2. Menghapus data redundan, fitur yang tidak relevan, atau noise
3. Mempercepat waktu running algoritma learning
4. Mengembangkan dan menambah kualitas data
5. Meningkatkan akurasi model
6. Meningkatkan performansi

Source :
[feature selection method and algorithm- L.Ladha]
[George Forman-feature selection for TC]

27 Feb

Text Pre-Processing

Posted by IkaSofiana in cin-TA kuuu. Tagged: feature selection, kategorisasi, preprosesing, stemming, stopword, token. Leave a comment

Assalamu’alaykum wr wb minna san…..

Ada beberapa hal yang harus dilakukan agar dokumen dalam kategorisasi teks dapat digunakan dalam proses learning sesuai dengan algoritma yang akan digunakan nantinya. Dalam hal ini, dilakukan pre-processing terhadap dokumen. Pre-processing yang dilakukan biasa dilakukan terhadap dokumen adalah sebagai berikut.

•   Case Folding

Dalam proses ini, dokumen mentah dioleh sedemikian sehingga hanya ada huruf ‘a’ sampai ‘z’ dalam dokumen tersebut. Jadi dalam proses ini dilakukan penghapusan terhadap tanda baca dan angka, serta pengubahan huruf besar menjadi huruf kecil.

•   Tokenisasi

Tokenisasi merupakan sebuah proses untuk memecah (mem-parsing) kalimat menjadi kata-kata pembentuknya, baik yang penting maupun tidak penting. Karena tanda baca sudah dihilangkan sebelumnya pada proses Case Folding, maka pemisahan kata-kata dalam kalimat ini dilakukan berdasarkan adanya spasi.

•  Penghapusan stopword

Stopword merupakan kata-kata yang sangat sering muncul dalam dokumen. Stopword ini tidak bisa dikatakan sebagai kata-kata yang tidak berpengaruh terhadap proses kategorisasi. Misalnya adalah kata penghubung seperti ‘dan’, ‘atau’, ‘kemudian’, dan seterusnya. Selain itu, kata depan juga merupakan stopword yang tidak memiliki arti penting bagi dokumen itu sendiri. Oleh karena itu, stopword harus dihilangkan. Penghilangan stopword ini dilakukan berdasarkan kamus kata tertentu yang disebut dengan database stopword. Database stopword yang digunakan dalam tugas akhir ini adalah data stopword yang telah ada dan dapat didownload dari  sini.

•  Stemming

Stemming dilakukan untuk mengubah kata berimbuhan menjadi kata dasarnya. Misalnya ‘berlari’ menjadi ‘lari’, ‘pemrosesan’ menjadi ‘proses’ dan seterusnya. Dengan demikian, kualitas informasi meningkat. Kualitas informasi yang dimaksud adalah hubungan antar kata itu sendiri, misalnya ‘memberi’, ‘diberi’, ‘memberikan’, yang semula adalah kata yang berbeda, dengan adanya stemming, kata tersebut menjadi ‘beri’, sehingga ada hubungan antara satu sama lain. Selain itu, space yang digunakan untuk penyimpanan juga menjadi lebih kecil.

•  Pengurangan Dimensionalitas

Pengurangan dimensionalitas disini dilakukan dengan feature selection, atau proses pemilihan fitur-fitur yang relevan terhadap kategori. Penjelasan lebih lanjut mengenai feature selection akan dijelaskan dalam postingan selanjutnya.

• Representasi Dokumen

Representasi dokumen yang digunakan dalam tugas akhir ini adalah the word-based representation  dimana metode ini merupakan metode yang paling sederhana untuk merepresentasikan sebuah dokumen dengan meng-konversi dokumen tersebut menjadi vector, yang dikenal sebagai bag-of-word (BOW). Namun demikian, metode ini memiliki beberapa kekurangan dimana metode ini tidak mengikutsertakan informasi mengenai paragraf, kalimat, dan susunan katanya. Ditambah lagi metode ini mengabaikan hubungan semantik diantara katanya. Namun, BOW tetap menjadi pendekatan yang paling banyak digunakan karena kesederhanaan dan efisiensinya.

source :

dimensionality reduction technique for enhancing automatic Text Categorization - Dina Adel Said

TUGAS4/5, AI, Rabu 4 Juni 2014

1.)    SPK pada suatu UKM dengan pendekatan Fuzzy Tsukamoto. Hasil survey yang dilakukan sebelumnya (Pre Research) menyatakan bahwa mesin produksi bekerja secara efisien jika mampu menghasilkan paling tidak 55000 per hari, adapun kemampuan mesin bisa mencapai 75000 per hari. Survey juga membuktikan bahwa persediaan barang di gudang harus berkisar antara 7000 hingga 13000. Pada perayaan 17 Agustus mendapat permintaan (Order) sebesar 60000 bendera tetapi persediaan di gudang hanya 8000 buah bendera saja. Hitung dengan Fuzzy Tsukamoto jumlah bendera yang harus di produksi pada hari itu.

2.)    Merancang (Design) Mesin Cuci Cerdas dengan Fuzzy Mamdani. Mesin cuci harus mampu mendeteksi derajat kekotoran pakaian (kotor, sedang, bersih) dan jumlah pakaian yang ditimbang dalam kg (ringan, normal, berat). Jika jumlah diterjen sebanding dengan jumlah air yang dibutuhkan untuk mencuci (sedikit, cukup, banyak) maka lama waktu cuci (cepat, tengah dan lambat) harus juga masuk dalam perhitungan. Rancang bangun secara lengkap dengan aturan (Rule) yang masuk akal.

3.)    Basis Data menggunakan Fuzzy: Diketahui 13 mahasiswa mengajukan beasiswa. Kriteria penerimaan berdasarkan kecerdasan yang di ukur dengan IPK (Harus >  2.5), TOEFL harus tinggi diatas 275 dan penghasilan Orang tua lebih kecil dari 1500 ribu rupiah. Adapun data yang diperoleh adalah tabel yang terdiri dari 5 kolom (Nomor urut, Nama mahasiswa, TOEFL, IPK dan Penghasilan Ortu) berturut-turut sbb.: [1 s/d 13], [A s/d M], [450,480,360,395,280,470,390, 360,370,275,265,325,280], [3.5,3,3,3,2.5,3.5,4,2,3,3,3, 2.5,2.5], [750,1400,1250,1600,1000,650, 1450,1050,1200,700,550,650,500]. Siapakah mahasiswa yang berhak mendapatkan beasiswa?

decision tree

Decision tree adalah salah satu metode klasifikasi yang paling populer karena mudah untuk diinterpretasi oleh manusia. Decision tree adalah model prediksi menggunakan struktur pohon atau struktur berhirarki. Konsep dari decision tree adalah mengubah data menjadi pohon keputusan dan aturan-aturan keputusan. Manfaat utama dari penggunaan decision tree adalah kemampuannya untuk mem-break down proses pengambilan keputusan yang kompleks menjadi lebih simpel sehingga pengambil keputusan akan lebih menginterpretasikan solusi dari permasalahan.

     

Kelebihan dari metode decision tree adalah:

·         Daerah pengambilan keputusan yang sbelumnya kompleks dan sangat global, dapat diubah menjadi lebih simpel dan spesifik.

·         Eliminasi perhitungan-perhitungan yang tidak diperlukan, karena ketika menggunakan metode decision tree maka sample diuji hanya berdasarkan criteria atau kelas tertentu.

·         Fleksibel untuk memilih features dari internal nodes yang berbeda, feature yang terpilih akan membedakan suatu criteria dibandingkan criteria yang lain dalam node yang sama. Kefleksibelan metode decision tree ini meningkatkan kualitas keputusan yang dihasilkan jika dibandingkan ketika menggunakan metode penghitungan satu tahap yang lebih konvensional.

·         Dalam analisis multivariat, dengan kriteria dan kelas yang jumlahnya sangat banyak, seorang penguji biasanya perlu untuk mengestimasikan baik itu distribusi dimensi tinggi ataupun parameter tertentu dari distribusi kelas tersebut. Metode decision tree dapat menghindari munculnya permasalahan ini dengan menggunakan criteria yang jumlahnya lebih sedikit pada setiap node internal tanpa banyak mengurangi kualitas keputusan yang dihasilkan.

Kekurangan metode decision tree, yaitu:

·      Terjadi overlap terutama ketika kelas-kelas dan criteria yang digunakan jumlahnya sangat banyak. Hal tersebut juga dapat menyebabkan meningkatnya waktu pengambilan keputusan dan jumlah memory yang diperlukan.

·      Pengakumulasian jumlah error dari setiap level dalam sebuah pohon keputusan yang besar.

·      Kesulitan dalam mendesain decision tree yang optimal. Hasil kualitas keputusan yang didapatkan dari metode decision tree sangat tergantung pada bagaimana pohon tersebut didesain.

Data: A set of data records (also called
examples, instances or cases) described by
 k attributes: A1, A2, … Ak.
 a class: Each example is labelled with a predefined
class.
 Goal: To learn a classification model from the
data that can be used to predict the classes
of new (future, or test) cases/instances.

 

Pemodelan Dasar Sistem Fuzzy

Soft Computing merupakan inovasi baru dalam membangun sistem cerdas. Sistem cerdas ini merupakan sistem yang memiliki keahlian seperti manusia pada domain tertentu, mampu beradaptasi dan belajar agar dapat bekerja lebih baik jika terjadi perubahan lingkungan. Unsur-unsur pokok dalam Soft Computing adalah : Sistem fuzzy, Jaringan Saraf Tiruan, Probabilistic Reasoning, Evolutionary Computing.
Sistem fuzzy secara umum terdapat 5 langkah dalam melakukan penalaran, yaitu:

1. Memasukkan input fuzzy.
2. Mengaplikasikan operator fuzy.
3. Mengaplikasikan metode implikasi.
4. Komposisi semua output.
5. Defuzifikasi.

Logika Fuzzy adalah suatu cara yang tepat untuk memetakan suatu ruang input ke dalam ruang output. Untuk sistem yang sangat rumit, penggunaan logika fuzzy (fuzzy logic) adalah salah satu pemecahannya. Sistem tradisional dirancang untuk mengontrol keluaran tunggal yang berasal dari beberapa masukan yang tidak saling berhubungan.  Karena ketidaktergantungan ini, penambahan masukan yang baru akan memperumit proses kontrol dan membutuhkan proses perhitungan kembali dari semua fungsi . Kebalikannya, penambahan masukan baru pada sistem fuzzy, yaitu sistem yang bekerja berdasarkan prinsip-prinsip logika fuzzy, hanya membutuhkan penambahan fungsi keanggotaan yang baru dan aturan-aturan yang berhubungan dengannya.

Secara umum, sistem fuzzy sangat cocok untuk penalaran pendekatan terutama untuk sistem yang menangani masalah-masalah yang sulit didefinisikan dengan menggunakan model matematis Misalkan, nilai masukan dan parameter sebuah sistem bersifat kurang akurat atau kurang jelas, sehingga sulit mendefinisikan model matematikanya.

Sistem fuzzy mempunyai beberapa keuntungan bila dibandingkan dengan sistem tradisional, misalkan pada jumlah aturan yang dipergunakan. Pemrosesan awal sejumlah besar nilai menjadi sebuah nilai derajat keanggotaan pada sistem fuzzy mengurangi jumlah nilai menjadi sebuah nilai derajat keanggotaan pada sistem fuzzy mengurangi jumlah nilai yang harus dipergunakan pengontrol untuk membuat suatu keputusan. Keuntungan lainnya adalah sistem fuzzy mempunyai kemampuan penalaran yang mirip dengan kemampuan penalaran manusia. Hal ini disebabkan karena sistem fuzzy mempunyai kemampuan untuk memberikan respon berdasarkan informasi yang bersifat kualitatif, tidak akurat, dan ambigu.

Ada beberapa alasan penggunaan Logika Fuzzy :

1. Logika Fuzzy sangat fleksibel.
2. Logika Fuzzy memiliki toleransi.
3. Konsep logika fuzzy mudah dimengerti. Konsep matematis yang mendasari penalaran fuzzy sangat sederhana dan mudah dimengerti.
4. Logika fuzzy mampu memodelkan fungsi-fungsi nonlinear yang sangat kompleks.
5. Logika fuzzy dapat membangun dan mengaplikasikan pengalaman-pengalaman para pakar secara langsung tanpa harus melalui proses pelatihan.
6. Logika fuzzy dapat bekerjasama dengan teknik-teknik kendali secara konvensional.
7. Logika fuzzy didasarkan pada bahasa alami.(Sri Kusumadwi,2002:3)

Sistem fuzzy pertama kali diperkenalkan oleh Prof. L. A. Zadeh dari Barkelay pada tahun 1965. Sistem fuzzy merupakan penduga numerik yang terstruktur dan dinamis. Sistem ini mempunyai kemampuan untuk mengembangkan sistem intelijen dalam lingkungan yang tak pasti. Sistem ini menduga suatu fungsi dengan logika fuzzy. Dalam logika fuzzy terdapat beberapa proses yaitu penentuan himpunan fuzzy, penerapan aturan IF-THEN dan proses inferensi fuzzy (Marimin, 2005:10).

Ada beberapa metode untuk merepresentasikan hasil logika fuzzy yaitu metode Tsukamoto, Sugeno dan Mamdani. Pada metode Tsukamoto, setiap konsekuen direpresentasikan dengan himpunan fuzzy dengan fungsi keanggotaan monoton. Output hasil inferensi masing-masing aturan adalah z,  berupa himpunan biasa (crisp) yang ditetapkan berdasarkan -predikatnya. Hasil akhir diperoleh dengan menggunakan rata-rata terbobotnya.(Sri Kusumadewi,2002:108)

Metode Sugeno mirip dengan metode Mamdani, hanya output (konsekuen) tidak berupa himpunan fuzzy, melainkan berupa konstanta atau persamaan liniar. Ada dua model metode Sugeno yaitu model fuzzy sugeno orde nol dan model fuzzy sugeno orde satu. Bentuk umum model fuzzy sugeno orde nol adalah :

IF (x1 is A1) o (x2 is A2) o ….. o (xn is An) THEN  z = k
Bentuk umum model fuzzy Sugeno orde satu adalah :
IF (x1 is A1) o (x2 is A2) o ….. o (xn is An) THEN  z = p1.x1 + … pn.xn + q
Defuzzifikasi pada metode Sugeno dilakukan dengan mencari nilai rata-ratanya.

Gambar 1  Model fuzzy sugeno orde 1

Pada metode Mamdani, aplikasi fungsi implikasi menggunakan MIN, sedang komposisi aturan menggunakan metode MAX. Metode Mamdani dikenal juga dengan metode MAX-MIN.  Inferensi output yang dihasilkan berupa bilangan fuzzy maka harus ditentukan suatu nilai crisp tertentu sebagai output. Proses ini dikenal dengan defuzzifikasi. Ada beberapa tahapan untuk mendapatkan output yaitu:

A. Pembentukan himpunan fuzzy
Pada metode Mamdani baik variabel input maupun variabel output dibagai menjadi satu atau lebih himpunan fuzzy.

2. Aplikasi fungsi implikasi

Pada metode Mamdani, fungsi implikasi yang digunakan adalah Min.

3. Komposisi Aturan

Tidak seperti penalaran monoton, apabila sistem terdiri dari beberapa aturan, maka inferensi diperoleh dari kumpulan dan korelasi antar aturan. Ada 3 metode yang digunakan dalam melakukan inferensi sistem fuzzy yaitu : Max, Additive dan Probabilistik OR
a.Metode Max (Maximum)
Pada metode ini solusi himpunan fuzzy diperoleh dengan cara mengambil nilai maksimum aturan, kemudian menggunakannya untuk memodifikasi daerah fuzzy dan mengaplikasikan ke output dengan menggunakan operator OR(union). Jika semua proposisi telah dievaluasi, maka output akan beisi suatu himpunan fuzzy yang merefleksikan konstribusi dari tiap-tiap proposisi. Secara umum dapat dituliskan :
µsf[xi] ← max ( µsf[xi] , µkf[xi])
dengan :
µsf[xi]=nilai keanggotaan solusi fuzzy sampai aturan ke-i
µkf[xi]=nilai keanggotaan konsekuen fuzzy aturan ke-i
b. Metode Additive (Sum)
Pada metode ini, solusi himpunan fuzzy diperoleh dengan cara melakukan bounded-sum terhadap semua output dareah fuzzy. Secara umum dituliskan:
µsf[xi] ← max ( 1, µsf[xi]  + µkf[xi] )
µsf[xi]=nilai keanggotaan solusi fuzzy sampai aturan ke-i
µkf[xi]=nilai keanggotaan konsekuen fuzzy aturan ke-i
c. Metode Probabilistik OR
Pada metode ini, solusi himpunan fuzzy diperoleh dengan cara melakukan product terhadap semua output daerah fuzzy. Secara umun dituliskan :
µsf[xi] ← max ( µsf[xi]  + µkf[xi] ) – (µsf[xi]  * µkf[xi] )
µsf[xi]=nilai keanggotaan solusi fuzzy sampai aturan ke-i
µkf[xi]=nilai keanggotaan konsekuen fuzzy aturan ke-i

4. Penegasan /Defuzzifikasi

Input dari proses Defuzzifikasi adalah suatu himpunan fuzzy yang diperoleh dari komposisi aturan-aturan fuzzy, sedangkan output yang dihasilkan merupakan suatu bilangan pada domain himpunan fuzzy tersebut. Sehingga jika diberikan suatu himpunan fuzzy dalam range tertentu, maka harus dapat diambil suatu nilai crisp tertentu sebagai output.

Ada beberapa metoda yang dipakai dalam defuzzifikasi:
a. Metode Centroid.
Pada metode ini penetapan nilai crisp dengan cara mengambil titik pusat daerah fuzzy.
b. Metode Bisektor.
Pada metode ini , solusi crisp diperoleh dengan cara mengambil nilai pada domain fuzzy yang memiliki nilai keanggotaan seperti dari jumlah total nilai keanggotaan pada daerah fuzzy.
c. Metode Means of Maximum (MOM).
Pada metode ini, solusi crisp diperoleh dengan cara mengambil nilai rata-rata domain yang memiliki niali keanggotaan maksimum.
d. Metode Largest of Maximum (LOM)
Pada metode ini, solusi crisp diperoleh dengan cara mengambil nilai terbesar dari domain yang memiliki niali keanggotaan maksimum.
e. Metode Smallest of Maksimum (SOM).
Solusi crisp diperoleh dengan cara mengambil nilai terkecil dari domain yang memiliki nilai keanggotaan maksimum.

Langkah Umum Pengembangan Model Fuzzy

 

Gambar 2. Langkah – Langkah Pengembangan Sistem Fuzzy

PUSTAKA

 JS.R.Jang, C.T.Sun dan E.Mizutani, (1997). Neuro Fuzzy and Soft Computing London Prentice Hall.
Kusumadewi. S dan H. Purnomo. (2004). Aplikasi Logika Fuzzy Untuk Mendukung Keputusan. Graha Ilmu, Yogyakarta.
Marimin. (2005). Teori dan aplikasi sistem pakar dalam tehnologi manajerial. IPB – Press, Bogor.
Sri Kusumadewi, (2002). Analisis  dan Desain Sistem Fuzzy menggunakan Tool Box Matlab, edisi pertama. Penerbit Graha Ilmu, Jakarta.
Sri Kusumadewi, (2003). Artificial Intelligence (Teknik dan Aplikasinya), edisi pertama. Penerbit Graha Ilmu, Jakarta.
Turban, E. (1988). Decision Support and Expert System. MacMillan Publishing Company, New York.
Widodo,T.S (2005). Sistem Neuro Fuzzy. Graha Ilmu, Yogyakarta.

Riwayat Penulis

Afan Galih Salman ST. M.Si, lahir di Bandung, 9 September  1969, Penulis menamatkan pendidikan S1 di Universitas Indonesia (UI) dalam bidang Teknik Gas & Petrokimia pada tahun 1994, menamatkan pendidikan S2 di Institut Pertanian Bogor (IPB) dalam bidang Ilmu Komputer peminatan Soft Computing pada tahun 2006. Saat ini penulis bekerja sebagai Head of Program Mobile Aps. & Tech di School of Computer Science Universitas Bina Nusantara dan aktif sebagai pengajar di mata kuliah Inteligensia Semu (AI).

Fuzzy Set

Fuzzy Logic adalah suatu cabang ilmu Artificial Intellegence, yaitu suatu pengetahuan yang membuat komputer dapat meniru kecerdasan manusia sehingga diharapkan komputer dapat melakukan hal-hal yang apabila dikerjakan manusia memerlukan kecerdasan.

Dengan kata lain fuzzy logic mempunyai fungsi untuk “meniru” kecerdasan yang dimiliki manusia untuk melakukan sesuatu dan mengimplementasikannya ke suatu perangkat, misalnya robot, kendaraan, peralatan rumah tangga, dan lain-lain.

Sejarah Fuzzzy Logic

Konsep Fuzzy Logic diperkenalkan oleh Prof. Lotfi Zadeh dari Universitas California di Berkeley pada 1965 dan dipresentasikan bukan sebagai suatu metodologi kontrol, tetapi sebagai suatu cara pemrosesan data dengan memperkenankan penggunaan partial set membership dibanding crisp set membership atau non-membership.Pendekatan pada set teori ini tidak diaplikasikan pada sistem kontrol sampai tahun 70-an karena kemampuan komputer yang tidak cukup pada saat itu. Profesor Zadeh berpikir bahwa orang tidak membutuhkan kepastian, masukan informasi numerik, dan belum mampu terhadap kontrol adaptif yang tinggi.

Konsep fuzzy logic kemudian berhasil diaplikasikan dalam bidang kontrol oleh E.H. Mamdani. Sejak saat itu aplikasi fuzzy berkembang kian pesat. Di tahun 1980-an negara Jepang dan negara-negara di Eropa secara agresif membangun produk nyata sehubungan dengan konsep fuzzy logic yang diintegrasikan dalam produk-produk kebutuhan rumah tangga seperti vacuum cleaner, microwave oven dan kamera video.  Sementara pengusaha di Amerika Serikat tidak secepat itu mencakup teknologi ini. Fuzzy logic  berkembang pesat selama beberapa tahun terakhir. Terdapat lebih dari dua ribu produk dipasaran yang menggunakan konsep fuzzy logic, mulai dari mesin cuci hingga kereta berkecepatan tinggi. Setiap aplikasi tentunya menyadari beberapa keuntungan dari fuzzy logic seperti performa, kesederhaan, biaya rendah dan produktifitasnya.

Konsep Fuzzy Logic

• Fuzzy logic umumnya diterapkan pada masalahmasalah yang mengandung unsur ketidakpastian (uncertainty), ketidaktepatan (imprecise), noisy, dan sebagainya.
• Fuzzy logic menjembatani bahasa mesin yang presisi dengan bahasa manusia yang menekankan pada makna atau arti (significance).
• Fuzzy logic dikembangkan berdasarkan cara berfikir manusia

Contoh-contoh masalah yang mengandung ketidakpastian

Contoh 1 : Seseorang dikatakan “tinggi” jika tinggi badannya lebih dari 1,7 meter. Bagaimana dengan orang yang mempunyai tinggi badan 1,6999 meter atau 1,65 meter, apakah termasuk kategori orang yang tinggi? Menurut persepsi manusia, orang yang mempunyai tinggi badan sekitar 1,7 meter dikatakan “kurang lebih tinggi” atau “agak tinggi”.

Contoh 2 : Kecepatan “pelan” didefinisikan di bawah 20 km/jam. Bagaimana dengan kecepatan 20,001 km/jam, apakah masih dapat dikatakan pelan? Manusia mungkin mengatakan bahwa kecepatan 20,001 km/jam itu “agak pelan”.
Arsitektur Fuzzy Logic

Ada tiga proses utama jika ingin mengimplementasikan fuzzy logic pada suatu perangkat, yaitu fuzzifikasi, evaluasi rule, dan defuzzifikasi.

1. Fuzzification, merupakan suatu proses untuk mengubah suatu masukan dari bentuk tegas (crisp) menjadi fuzzy yang biasanya disajikan dalam bentuk himpunan-himpunan fuzzy dengan suatu fungsi kenggotaannya masing-masing.
2. Interference System (Evaluasi Rule), merupakan sebagai acuan untuk menjelaskan hubungan antara variable-variabel masukan dan keluaran yang mana variabel yang diproses dan yang dihasilkan berbentuk fuzzy. Untuk menjelaskan hubungan antara masukan dan keluaran biasanya menggunakan “IF-THEN”.
   
3. Defuzzification, merupakan proses pengubahan variabel berbentuk fuzzy tersebut menjadi data-data pasti (crisp) yang dapat dikirimkan ke peralatan pengendalian.
   

Berikut diagram alir prosesnya.