BAB II LANDASAN TEORI 1
Klasifikasi Klasifikasi merupakan suatu pekerjaan menilai objek data untuk memasukkannya ke dalam kelas tertentu dari sejumlah kelas yang tersedia. Dalam klasifikasi ada dua pekerjaan utama yang dilakukan, yaitu : pertama, Pembangunan model sebagai prototype untuk disimpan sebagai memori dan kedua, Penggunaan model tersebut untuk melakukan pengenalan/ klasifikasi/ prediksi pada suatu objek data lain agar diketahui di kelas mana objek data tersebut dalam model yang mudah disimpan (Prasetyo, Eko. 2012). Contoh aplikasi yang sering ditemui adalah pengklasifikasian jenis hewan, yang mempunyai sejumlah atribut. Dengan atribut tersebut, jika ada hewan baru, kelas hewannya bisa langsung diketahui. Contoh lain adalah bagaimana melakukan diagnosis penyakit kulit kanker melanoma (Prasetyo, Eko. 2012), yaitu dengan melakukan pembangunan model berdasarkan data latih yang ada, kemudian menggunakan model tersebut untuk mengidentifikasi penyakit pasien baru sehingga diketahui apakah pasien tersebut menderita kanker atau tidak. 2
Sentimen Analisis Sentiment Analysis atau opinion mining merupakan proses memahami,
mengekstrak dan mengolah data tekstual secara otomatis untuk mendapatkan informasi sentiment yang terkandung dalam suatu kalimat opini. Sentiment Analysis dilakukan untuk melihat pendapat atau kecenderungan opini terhadap sebuah masalah atau objek oleh seseorang, apakah cenderung berpandangan atau beropini negatif atau positif (Bo Pang, 2002). Sentiment Analysis dapat dibedakan berdasarkan sumber datanya, beberapa level yang sering digunakan dalam penelitian Sentiment Analysis adalah Sentiment Analysis pada level dokumen dan Sentiment Analysis pada level kalimat (Fink Clayton, 2011). Berdasarkan level sumber datanya Sentiment Analysis terbagi menjadi 2 kelompok besar yaitu :
1
Coarse-grained Sentiment Analysis Pada Sentiment Analysis jenis ini, Sentiment Analysis yang dilakukan adalah pada level dokumen. Secara garis besar fokus utama dari Sentiment Analysis jenis ini adalah menganggap seluruh isi dokumen sebagai sebuah sentiment positif atau sentiment negatif (Fink Clayton, 2011). Salah satu contoh yang menggambarkan coarse-grained Sentiment Analysis adalah sebagai berikut : “ Time and time again, the wily filmmakers sprinkle the overarching storyline of the fall and decline of Larry Gopnik’s life (a masterful, wideranging and sensitive performance from Michael Stuhlbarg) with a fine combination of overt, discreet and subliminal set-ups whose payoffs give their film extra punch and an unstoppable pace.” (Fink Clayton, 2011) Pada review diatas, dapat disimpulkan dengan jelas bahwa sentiment yang terkandung dalam review tersebut adalah positif, dapat di jelaskan dengan kata-kata subjektif positif seperti “masterful” , “extra punch”, dan “unstopabble pace”. Fined-grained Sentiment Analysis Fined-grained Sentiment Analysis adalah Sentiment Analysis pada level kalimat. Fokus utama fined-greined Sentiment Analysis adalah menentukan sentimen pada setiap kaliamat pada suatu dokumen, dimana kemungkinan yang terjadi adalah terdapat sentimen pada level kalimat yang berbeda pada suatu dokumen (Fink Clayton, 2011). 2.3
Text Mining Text mining yang juga disebut sebagai text data mining (TDM) atau knowledge-
discovery in text (KDT), secara umum mengacu pada proses ekstrasi informasi atau knowledge yang menarik dan non-trival dari dokumen-dokumen text tak terstruktur . Text mining dapat didefiniskan sebagai penemuan informasi baru dan tidak diketahui sebelumnya oleh komputer dengan secara otomatis mengekstrak informasi dari sumbersumber text tak terstruktur yang berbeda. Kunci dari proses ini adalah menggabungkan informasi yang berhasil diekstrasi dari bebagai sumber. Pada prinsipnya text mining adalah bidang ilmu multidipliner, melibatkan information retrieval (IR), text analisis, informasi extraction (IE), clustering, categorization, visualization, database technology, natural language processing (NLP), 2
machine learning, dan data mining. Dapata pula dikatakan bahwa text mining merupakan salah satu bentuk aplikasi kecerdasan buatan. Text mining mencoba memecahkan masalah information overload dengan mengunakan teknik-teknik dari bidang ilmu yang terkait. Text mining dapat dipandang sebagai suatu perluasan dari data mining atau knowledge-discovery in database (KDD), yang mencoba untuk menemukan pola pola menarik sari basis data berskala besar. Namun text mining memiliki potensi komersil yang lebih tinggi dibandingkan dengan data mining, karena kebnyakan format alami dari penyimpanan informasi adalah berupa text. Text mining mengunakan informasi text tak berstruktur dan mengujinya dalam upaya mengungkap struktur dan arti yang “tersembunyi” di dalam text. 2.1
Text Preprocessing Text Preprocessing merupakan tahapan awal dalam mengolah data input sebelum
memasuki proses tahapan utama dari metode Latent Semantic Analysis (LSA). Preprocessing text dilakukan untuk tujuan penyeragaman dan kemudahan pembacaan serta proses LSA selanjutnya (Aji P., Baizal SSi. and Firdaus S.T., 2011). Preprocessing terdiri dari beberapa tahapan. Adapun tahapan preprocessing berdasarkan (Triawati, 2009) , yaitu: case folding, tokenizing / parsing, filtering, stemming. Berikut penjelasan empat tahapan dalam proses preprocessing adalah sebagai berikut. 1.
Case Folding Case folding merupakan tahapan yang mengubah semua huruf dalam dokumen
menjadi huruf kecil. Hanya huruf ‘a’ sampai dengan ‘z’ yang diterima. Karakter selain huruf dihilangkan dan dianggap delimiter (pembatas) (Triawati, 2009). Contoh penggunaan case folding adalah sebagai berikut.
Gambar 2.1 Proses Case Folding
3
2.
Tokenizing Tahap tokenizing / parsing adalah tahap pemotongan string input berdasarkan tiap
kata yang menyusunnya (Triawati, 2009). Selain itu, spasi digunakan untuk memisahkan antar kata tersebut.
Gambar 2.2 Proses Tokenizing 3.
Filtering Tahap filtering adalah tahap mengambil kata - kata penting dari hasil tokenizing.
Proses filtering dapat menggunakan algoritma stoplist (membuang kata yang kurang penting) atau wordlist (menyimpan kata penting). Stoplist / stopword adalah kata-kata yang tidak deskriptif yang dapat dibuang dalam pendekatan bag-of-words. Contoh stopword adalah “yang”, “dan”, “di”, “dari” dan lain – lain. (Triawati, 2009).
Gambar 2.3 Proses Filtering
4.
4
Stemming
Stemming merupakan suatu proses yang terdapat dalam sistem IR yang mentransformasi kata-kata yang terdapat dalam suatu dokumen ke kata-kata akarnya (root word) dengan menggunakan aturan-aturan tertentu (Agusta, 2009). Stemming kebanyakan digunakan pada teks berbahasa inggris dikarenakan teks berbahasa inggris memiliki struktur imbuhan yang tetap dan mudah untuk diolah sementara stemming untuk proses bahasa Indonesia memiliki struktur imbuhan yang rumit / kompleks sehingga agak lebih susah untuk diolah. Contoh penggunaan stemming :
Gambar 2.4 Proses Stemming
5
2.2
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. 2.3
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. 2.4
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 k-NN, 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
6
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. 3
Naïve Bayes Classifier Algoritma Naïve Bayes Classifier merupakan algoritma yang digunakan untuk
mencari nilai probabilitas tertinggi untuk mengklasifikasi data uji pada kategori yang paling tepat. Dalam penelitian ini yang menjadi data uji adalah dokumen berita. Ada dua tahap pada klasifikasi dokumen. Tahap pertama adalah pelatihan terhadap dokumen yang sudah diketahui kategorinya. Sedangkan tahap kedua adalah proses klasifikasi dokumen yang belum diketahui kategorinya. Dalam algoritma Naïve Bayes Classifier setiap dokumen direpresentasikan dengan pasangan atribut “x1, x2, x3,...xn” dimana x1 adalah kata pertama, x2 adalah kata kedua dan seterusnya. Sedangkan V adalah himpunan kategori hasil jawaban. Pada saat klasifikasi algoritma akan mencari probabilitas tertinggi dari semua kategori dokumen yang diujikan (VMAP), dimana persamaannya adalah sebagai berikut :
V
7
Untuk P(x1, x2, x3,...xn) nilainya konstan untuk semua kategori (Vj) sehingga persamaan dapat ditulis sebagai berikut :
V Persamaan diatas dapat disederhanakan menjadi sebagai berikut :
Keterangan: Vj = Kategori jawaban j =1, 2, 3,…n. Dimana dalam penelitian ini j1 =
kategori
negatif dan j2 = kategori berita positif P(xi|Vj) = Probabilitas xi pada kategori Vj P(Vj) = Probabilitas dari Vj Untuk P(Vj) dan P(xi|Vj) dihitung pada saat pelatihan dimana persamaannya adalah sebagai berikut :
P(Vj) = P(Vj) = Keterangan : |docs j| = jumlah dokumen setiap kategori j |contoh| = jumlah dokumen dari semua kategori nk = jumlah frekuensi kemunculan setiap kata n = jumlah frekuensi kemunculan kata dari setiap kategori |kosakata| = jumlah semua kata dari semua kategori 4
K-Nearst Neighbor Algoritma K-nearest neighbor (KNN) adalah sebuah metode untuk melakukan klasifikasi terhadap objek berdasarkan data pembelajaran yang jaraknya paling dekat dengan objek tersebut. KNN termasuk algoritma supervised learning dimana hasil dari query instance yang baru diklasifikan berdasarkan mayoritas dari kategori pada KNN. Nanti kelas yang paling banyak muncul yang akan menjadi kelas hasil klasifikasi.
8
Tujuan dari algoritma ini adalah mengklasifikasikan obyek baru bedasarkan atribut dan training sample. Classifier tidak menggunakan model apapun untuk dicocokkan dan hanya berdasarkan pada memori. Diberikan titik query, akan ditemukan sejumlah k obyek atau (titik training) yang paling dekat dengan titik query. Klasifikasi menggunakan voting terbanyak diantara klasifikasi dari k obyek.. algoritma K-Nearest Neighbor (KNN)
menggunakan klasifikasi ketetanggaan sebagai nilai prediksi dari
query instanceyang baru. Algoritma metode K-Nearest Neighbor (KNN) sangatlah sederhana, bekerja berdasarkan
jarak
terpendek
dari
query
instance ke
training
sample untuk
menentukan KNN-nya. Training sample diproyeksikan ke ruang berdimensi banyak, dimana masing-masing dimensi merepresentasikan fitur dari data. Ruang ini dibagi menjadi bagian-bagian berdasarkan klasifikasi training sample. Sebuah titik pada ruang ini ditandai kelas jika kelas merupakan klasifikasi yang paling banyak ditemui pada k buah tetangga terdekat dari titik tersebut. Dekat atau jauhnya tetangga biasanya dihitung berdasarkan Euclidean Distance. Jarak Euclidean paling sering digunakan menghitung jarak. Jarak euclidean berfungsi menguji ukuran yang bisa digunakan sebagai interpretasi kedekatan jarak antara dua obyek. yang direpresentasikan sebagai berikut : dimana D(a,b) = 2 matriks D (a,b) adalah jarak skala dari matriks dengan ukuran dimensi.
kedua vektor adan b dari
Semakin besar nilai D akan semakin jauh tingkat keserupaan antara kedua individu dan sebaliknya jika nilai D semakin kecil maka akan semakin dekat tingkat keserupaan antar individu tersebut. Nilai k yang terbaik untuk algoritma ini tergantung pada data. Secara umum, nilai k yang tinggi akan mengurangi efek noise pada klasifikasi, tetapi membuat batasan antara setiap klasifikasi menjadi semakin kabur. Nilai k yang bagus dapat dipilih dengan optimasi parameter, misalnya dengan menggunakan cross-validation. Kasus khusus dimana klasifikasi diprediksikan berdasarkan training data yang paling dekat (dengan kata lain, k = 1) disebut algoritma k-nearest neighbor. Ketepatan algoritma KNN sangat dipengaruhi oleh ada atau tidaknya fiturfitur yang tidak relevan atau jika bobot fitur tersebut tidak setara dengan relevansinya
9
terhadap
klasifikasi.
Riset
terhadap
algoritma
ini
sebagian
besar membahas
bagaimana memilih dan memberi bobot terhadap fitur agar performa klasifikasi menjadi lebih baik. Langkah-langkah untuk menghitung metode K-Nearest Neighbor : 1.
Menentukan parameter K (jumlah tetangga paling dekat).
2.
Menghitung kuadrat jarak eucledian (query instance) masing-masing obyek terhadap data sampel yang diberikan.
3.
Kemudian mengurutkan objek-objek tersebut kedalam kelompok yang mempunyai jarak eucledian terkecil.
4.
Mengumpulkan kategori Y (Klasifikasi K-Nearest Neighbor)
5.
Dengan menggunakan kategori K-Nearest Neighbor yang paling mayoritas maka dapat dipredisikan nilai query instance yang telah dihitung.
10
11
