Friday, July 18, 2014

New York Tee

New York Tee: T-Shirt With New York Animal Print Applique by 24:01.






Find this cool stuff here: http://zocko.it/LC6gu

Camo Unit SS Watch

Camo Unit SS Watch: The Unit SS. A powerful watch in a small design. Its sporty, stainless steel construction protects it while the powerful insides provides more than just time measurement.



Find this cool stuff here: http://zocko.it/LC6gl

Portrait Blouse

Portrait Blouse: Portrait Blouse by Shopatvelvet.



Find this cool stuff here: http://zocko.it/LC6g1

Monday, July 14, 2014

Algoritma Bayesian Filter



Bayesian filter merupakan metode terbaru yang digunakan untuk mendeteksi spam mail. Algoritma ini memanfaatkan metode probabilitas dan statistik yang dikemukakan oleh ilmuwan Inggris Thomas Bayes, yaitu memprediksi probabilitas di masa depan berdasarkan pengalaman di masa sebelumnya. Dua kelompok peneliti, satu oleh Pantel dan Lin, dan yang lain oleh Microsoft Research memperkenalkan metode statistik Bayesian ini pada teknologi anti spam filter. Tetapi yang membuat algoritma Bayesian filtering ini popular adalah pendekatan yang dilakukan oleh Paul Graham. 
 Bayesian filter mendeteksi spam dengan cara menghitung probabilitas dari suatu pesan (mail) berdasarkan isinya. Probabilitas ini dapat dihitung dengan terlebih dahulu membuat suatu database spam-mail dan database non spam-mail. Kemudian dengan suatu metode training, software anti spam yang menggunakan algoritma Bayesian dapat dilatih untuk melihat kata-kata yang sering digunakan pada spam-mail, sehingga pada akhirnya dihasilkan filter anti spam yang akurat dengan sesedikit mungkin false positives. False positives adalah e-mail legal yang ditujukan kepada penerima, tetapi karena kesalahan dari filter anti spam, dikategorikan menjadi spam-mail.
Pada dasarnya, algoritma Bayesian filter merupakan merupakan pengembangan dari algoritma penilaian pesan (scoring content-based filter, hampir sama dengan keywords filtering) yaitu filter mencari karakteristik kata-kata yang banyak digunakan pada spam-mail, kata-kata ini diberi nilai individual, dan nilai spam secara keseluruhan dihitung dari nilai individual tersebut. Tetapi algoritma ini memiliki kelemahan yaitu karakteristik kata-kata pada spam-mail dan non-spam mail akan berbeda-beda untuk setiap individu. Kata “business” misalnya yang untuk sebagian orang akan termasuk pada karakteristik kata-kata pada spam-mail, tetapi untuk perusahaan tertentu yang bergerak di bidang itu, kata “business” tersebut akan termasuk pada non spam-mail. Dapat dikatakan bahwa algoritma scoring content-based filter ini tidak kompatibel.
Lain halnya dengan scoring content-based filter, Bayesian filter akan membuat daftar karakteristik kata-kata spam dan non-spam mail secara otomatis. Tentunya terlebih dahulu , kita harus mengklasifikasikan e-mail – e-mail mana saja yang termasuk spam-mail dan mana yang termasuk non-spam mail. Bayesian filter akan menghitung probabilitas dari kata-kata yang umum digunakan pada spam mail berdasarkan klasifikasi ini. Karakteristik dari spam-mail yang dapat diidentifikasi antara lain berdasarkan kata-kata pada body message, header message, dan juga kode HTML (seperti pemberian background warna).

3.1. Perhitungan Probabilitas Berdasarkan Algoritma Bayesian

Pada awalnya, Bayesian filter ini harus di-training terlebih dahulu menggunakan sejumlah spam mail dan sejumlah ham mail. Bayesian filter akan menghitung probabilitas lokal dari suatu kata, misalnya kata “adult”, untuk muncul di kelompok spam mail. Probabilitas lokal ini dapat dirumuskan sebagai berikut :


 
                        Plocal – spam = N spam / (N spam + N non-spam)         …………..(1.1)

dimana : Plocal – spam    = probabilitas suatu kata “x” terdapat pada spam-mail
               N spam           = jumlah spam mail dengan kata “x” di dalamnya
               N non-spam        = jumlah non-spam mail dengan kata “x” di dalamnya
Atau rumus lain yang digunakan untuk menghitung probabilitas lokal dari suatu kata, terutama jika nilai  N spam dan N non-spam kecil adalah bahwa probabilitas akan terletak di sekitar probabilitas ketidakpastian (P = 0.5) :



 
                                                Plocal – spam = 0.5 +       …………….(1.2)

            dimana : C1 dan C2 adalah konstanta yang dipilih melalui eksperimen

Misalkan jika C1 = 2 dan C2 = 1, dan jika suatu kata “x” hanya ditemukan pada satu spam-mail dan tidak ditemukan sama sekali pada ham mail, maka probabilitas lokal suatu message baru yang mengandung kata tersebut dikategorikan sebagai spam adalah 0.75. Probabilitas ini tidak terlalu tinggi untuk dikategorikan sebagai spam. Sementara jika kata tersebut ditemukan pada sepuluh spam-mail dan tidak ditemukan sama sekali pada ham mail, maka probabilitas lokal-nya akan sama dengan 95.4%, yang cukup tinggi untuk dikategorikan sebagai spam. Perhitungan probabilitas ini jika dilakukan dengan rumus (1.1), akan memberikan hasil yang terlalu “kasar”, yaitu probabilitas mutlak = 1.
Probabilitas lokal dari masing-masing kata tersebut kemudian menggunakan aturan rantai (chain rule) Bayesian untuk menentukan probabilitas total dari suatu message adalah spam. Bayesian chain rule dirumuskan sebagai berikut :


 
        …………………………(1.3)

dimana : a = probabilitas suatu message dikategorikan sebagai spam dengan adanya kata “a” 
               b = probabilitas suatu message dikategorikan sebagai spam dengan adanya kata “b” 
Untuk menentukan probabilitas total, perhitungan di atas dilakukan terus menerus secara iterative dari  probabilitas lokal masing-masing kata pada message tersebut.
            Sebagai salah satu cara untuk menghindari false positives, filter dapat di-training untuk mengkategorikan message sebagai spam hanya jika :

   ……………… (1.4)

dimana :           = probabilitas total suatu message dengan kata-kata tertentu dikategorikan sebagai spam
                   =  probabilitas total suatu message dengan kata-kata tertentu dikategorikan sebagai legitimate mail
Seperti telah dibahas di atas, bahwa setiap kata memiliki probabilitas lokal untuk muncul pada spam-mail dan probabilitas lokal untuk muncul pada legitimate-mail. Berdasarkan probabilitas lokal tersebut, suatu message mempunyai probabilitas total untuk dikategorikan sebagai spam mail atau sebagai legitimate mail. Karena false positives dianggap lebih beresiko karena dapat menghilangkan mail yang penting bagi seseorang atau suatu perusahaan, maka dipilih nilai l tertentu pada persamaan(1.4) di atas untuk memperkecil kemungkinan terjadinya false positives.
Kelemahan dari Bayesian chain rule ini adalah tiap kata diasumsikan terpisah dan tidak tergantung satu sama lain. Padahal dalam menganalisis suatu teks, setiap kata saling berhubungan satu dengan yang lain. Kelemahan ini diatasi oleh algoritma probabilitas chi-squared yang dikembangkan pada proyek SpamBayes (akan dibahas berikut ini).

            3.2. Pengembangan Algoritma Bayesian
Salah satu pengembangan algoritma Bayesian filter adalah proyek SpamBayes yang ditujukan untuk melakukan pembaharuan dari algoritma Bayesian filter yang pertama kali dikembangkan oleh Paul Graham. Proyek SpamBayes ini dimotori oleh Gary Robinson dan Tim Peters. Secara prinsip proyek SpamBayes ini sama dengan algoritma Bayesian dari Paul Graham. Kelebihannya adalah SpamBayes dapat mengkategorikan mail menjadi spam-mail, non-spam mail (ham), dan unsure-mail. Unsure-mail dapat dikatakan sebagai pesan yang tidak dapat dikategorikan secara rating menjadi spam mail ataukah ham mail. Pengkategorian seperti ini juga dilakukan dengan cara yang sama yaitu dengan memberikan algoritma belajar pada SpamBayes berdasarkan beberapa e-mail yang dikategorikan sebagai spam mail atau ham mail.

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].

Feature Selection

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]

Text Pre-Processing

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