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)
χ^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
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
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.
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]:
[feature selection method and algorithm- L.Ladha]
[George Forman-feature selection for TC]
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
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]:
- Mengurangi dimensionalitas feature space, sehingga mengurangi kebutuhan storage dan meningkatkan kecepatan algoritma.
- Menghapus data redundan, fitur yang tidak relevan, atau noise
- Mempercepat waktu running algoritma learning
- Mengembangkan dan menambah kualitas data
- Meningkatkan akurasi model
- Meningkatkan performansi
[feature selection method and algorithm- L.Ladha]
[George Forman-feature selection for TC]
27
Feb
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
No comments:
Post a Comment