BAB II TINJAUAN PUSTAKA
2.1
Multimedia Information Retrieval Internet merupakan sebuah loncatan besar dalam dunia tehnologi manusia
yang perkembangannya semakin cepat dari waktu ke waktu. Pemanfaatan tehnologi internet semain beragam, mulai dari surat elektronik (email) sampai pada pengiriman video (video streaming), bahkan digunakan sebagai media komunikasi jarak jauh (teleconference) tanpa mengenal batas-batas teritorial negara.Pengguna internet tinggal memilih sejauh mana mereka akan melakukan sesuatu dengan bantuan tehnologi internet ini, karena internet merupakan sebuah dunia baru, dimana tidak mengenal adanya batas waktu dan batas wilayah. Kondisi tersebut memunculkan kebutuhan untuk pencarian data yang komprehensif dimana dapat mencari data teks, gambar, video ataupun suara. Hal ini yang disebut sebagai Multimedia Information Retrieval System (MIRS). Sehingga MIRS dapat didefinisikan sebagai sebuah sistem manajemen (penyimpanan, retrival dan manipulasi) dari berbagai tipe data(Nordbotten, 2008). Dalam prakteknya arsitektur dari MIRS dapat digambarkan sebagai berikut:
5
6
ontology
query
IR System Query enrichment Feature vector (fv) miner
Ontology repository Onto‐driven retrieval engine
Document repository
Search result
Feature vector repository
Query and indexing system wrappers e.g. Lucene, Nutch, Yahoo, Google, etc
Gambar 2.1 Arsitektur MIRS (Nordbotten, 2008)
Pada gambar arsitektur diatas, ada dua proses besar dalam MIRS, yaitu proses offline dan online. Kegiatan pada proses offline antara lain proses indexing dokumen, penentuan faktor-faktor fitur, proses pembentukan ontology dan lainnya. Sedangkan proses online adalah proses dimana query dilakukan oleh user. Algoritma yang dilakukan pada saat query berdasarkan proses pembelajaran yang dilakukan pada proses offline.
2.2
Multimedia Data Mining Perkembangan internet ini mendorong munculnya sebuah sumber
informasi yang tidak terbatas, baik informasi teks, gambar, suara dan video, yang lebih dikenal dengan sebutan data multimedia (multimedia database). Data
7
multimedia ini memerlukan sebuah proses eksplorasi data (data mining) dan manajemen data untuk melakukan ekstraksi informasi (Thuraisingham, 2001). Data mining adalah sebuah proses penarikan kesimpulan dari sebuah premis yang biasanya sebelumnya tidak diketahui dari jumlah data yang besar, mencakup dua pekerjaan besar yaitu pengambilan data(data mining) dan ekstraksi informasi (Thuraisingham, 2001).
Gambar 2.2 Proses Pengambilan & Ekstraksi Data(Thuraisingham, 2001)
Proses ektraksi terhadap informasi-informasi penting terhadap data yang sangat besar adalah merupakan bagian yang penting dari eksplorasi data (Tan, Steinbach, & Kumar, 2006). Berbagai macam teknik digunakan dalam proses eksplorasi data untuk mendapatkan sebuah pola baru dan bermanfaat. Secara umum kegiatan dalam eksplorasi data menggunakan metode prediksi dan deskripsi. Prediksi bertujuan untuk mendapatkan sebuah nilai yang tidak diketahui atau nilai mendatang dari data sebelumnya. Yang termasuk dalam hal ini adalah klasifikasi, regresi dan deteksi penyimpangan. Sedangkan deskripsi bertujuan untuk mencari pola yang dapat menggambarkan data secara keseluruhan. Dalam
8
hal ini adalah klastering, association rule discovery dan sequential pattern discovery(Tan, Steinbach, & Kumar, 2006).
Data Mining Methodologies (Approaches) Top Down Bottom‐Up (Supervised or Unsupervised) Hybrid
Data Mining Techniques (Algorithms) Neural Networks Inductive Logic Programming Decision Trees Nearest Neighbor
Data Mining Task (Outcomes) Classification Clastering Assosiation Derivation Detection Gambar 2.3 Multimedia Data Mining Task, Techniques and Methodologies
Dalam Gambar 2.4 menunjukkan bahwa dalam proses eksplorasi data multimedia adalah informasi teks, gambar, video, suara, ataupun kombinasi dari hal-hal tersebut. Dalam thesis ini, proses eksplorasi data akan lebih difokuskan pada eksplorasi data teks sebagai sumber informasi.
9
Video Mining Image Mining
Text Mining
Audio Mining
Multimedia Data Mining
Mining Combinations of Data Types
Gambar 2.4 Multimedia Data Mining (Thuraisingham, 2001)
Ketersediaan informasi tekstual yang tidak terbatas menimbulkan kebutuhan manusia akan proses penyajian informasi yang ringkas dan cepat. Informasi tekstual yang sedemikian banyak tersebut tidak mungkin dibaca satu persatu untuk mendapatkan informasi yang dibutuhkan. Oleh karena itu diperlukan proses ekstraksi informasi untuk mengolah dan menyajiakan informasi tekstual menjadi informasi yang ringkas tanpa mengurangi nilai informasi secara keseluruhan. Secara garis besar informasi tekstual dapat dikategorikan menjadi dua macan: fakta dan opini(Liu, Sentiment Analysis: A Multi-Faceted Problem, 2010). Fakta merupakan ekspresi yang obyektif mengenai suatu entitas, kejadian atau sifat, sedangkan opini biasanya bersifat berupa ekspresi subyektif yang menggambarkan sentimen orang, pendapat atau perasaan tentang sebuah entitas, kejadian atau sifat.Salah satu bentuk penyajian terhadap informasi tektual tersebut adalah opinion mining.
10
Dengan adanya opinion miningkita dapat melihat bagaimana pendapat orang lain terhadap suatu hal sehingga membantu kita dalam mengambil sebuah keputusan dengan lebih cepat dan tepat, atau membantu dalam mengidentifikasi suatu tren yang ada. (Pang, Lee, & Vaithyanathan, Thumbs up? Sentiment Classification using Machine Learning, 2002).Hasil penelitian dalam opinion miningberusaha melakukan klasifikasi pada dokumen apakah merupakan opini atau fakta, atau melakukan klasifikasi pada dokumen tersebut apakah memiliki sentimen positif atau negatif(Abbasi, Chen, & Salem, 2008).
2.3
Klasifikasi Dokumen Klasifikasi merupakan proses identifikasi objek ke dalam sebuah kelas,
grup ataupun kategori tertentu berdasarkan prosedur, karakteristik serta definisinya.(Tan, Steinbach, & Kumar, 2006).
Input Attribute set (x)
Classification model
Output Class label (y)
Gambar 2.5 Proses klasifikasi dengan masukan nilai atribut x ke dalam kelas label y (Tan, Steinbach, & Kumar, 2006)
Gambar 2.5menunjukkan garis besar proses klasifikasi dilakukan, dimana dokumen inputan yang akan diklasifikasi memiliki nilai atribut x, kemudian dengan menggunakan model klasifikasi yang telah ditentukan akan menghasilkan nilai y sebagai kelas keluaran proses klasifikasi.
11
Dalam
machine
learning,
proses
klasifikasi
memerlukan
data
pembelajaran. Masing-masing data memiliki atribut dimana salah satu atribut tersebut merupakan sebuah kelas. Proses machine learning dilakukan untuk mendapatkan model untuk mendapatkan kelas dari atribut yang lain dengan tujuan mendapatkan kelas dari data yang lain seakurat mungkin. Untuk menilai keakuratan dari model yang diperoleh dilakukan proses percobaan. Proses percobaan dilakukan dengan membagi data yang telah diketahui menjadi dua, yaitu data pembelajaran dan data percobaan.Data pembelajaran digunakan untuk membuat model dan data test digunakan untuk validasi. Berdasarkan keluaran hasil klasifikasi, proses klasifikasi dokumen dapat dibagi menjadi tiga(Melli, 2010), yaitu : •
Proses klasifikasi binary Pada proses ini keluaran dari klasifikasi hanya ada dua macam, biasanya dinyatakan dalam 0 dan 1, sehingga disebut klasifikasi binary.Contoh aplikasi klasifikasi ini antara lain untuk pendekteksian email spam {spam, bukan spam} dan klasifikasi dalam analisis sentimen {opini, fakta} atau {positif, negatif}
•
Proses klasifikasi multikelas Keluaran dari proses klasifikasi ini lebih dari dua kelas. Contohnya proses pengklasifikasi topik pada sebuah berita {olahraga, keuangan, infotainment, berita, ... }
•
Proses klasifikasi multikelas dalam skala besar
12
Pada proses klasifikasi multikelas skala besar, pada dasarnya sama dengan klasifikasi multikelas biasa, hanya keluaran yang diperoleh adalah sangat besar, lebih dari ribuan kelas. Sehingga klasifikasi ini diperlukan sebuah teknik khusus agar proses klasifikasi dapat dilakukan. Contohnya pada klasifikasi 18.000 Medical Subject Heading (MeSH) Berdasarkan tujuan dari model klasifikasi dokumen yang digunakan, tujuan dari klasifikasi dapat dibagi menjadi dua (Tan, Steinbach, & Kumar, 2006), yaitu : •
Pemodelan Deskriptif (Deskriptif modelling) Pemodelan deskriptif dilakukan dengan tujuan untuk mencari pola yang dapat menggambarkan data secara keseluruhan. Tabel 2.1 Data Set Hewan Bertulang Belakang Name
Body Temperat ure
Skin Cover
Gives Birth
human
warmblooded coldblooded coldblooded warmblooded coldblooded coldblooded warmblooded warmblooded warmblooded coldblooded coldblooded warm-
hair
phyton salmon whale frog komodo bat pigeon cat leopard turtle penguin
Aerial Creat ure
Has Legs
Hiber nates
Class Label
yes
Aquat ic Creat ure no
no
yes
no
mammal
scales
no
no
no
no
yes
reptile
scales
no
yes
no
no
no
fish
hair
yes
yes
no
no
no
mammal
none
no
semi
no
yes
yes
amphibian
slaces
no
no
no
yes
no
reptile
hair
yes
no
yes
yes
yes
mammal
feathers
no
no
yes
yes
no
bird
fur
yes
no
no
yes
no
mammal
scales
yes
yes
no
no
no
fish
scales
no
semi
no
yes
no
reptile
feathers
no
semi
no
yes
no
bird
13
porcupine eel salamander
blooded warmblooded coldblooded coldblooded
quills
yes
no
no
yes
yes
mammal
scales
no
yes
no
no
no
fish
none
no
semi
no
yes
yes
amphibian
Sumber : (Tan, Steinbach, & Kumar, 2006, hal. 147)
Tabel 2.1merupakan contoh pemodelan klasifikasi dengan tujuan deskriptif. Dari model klasifikasi diatas dapat dideskripsikan bagaimanaciri-ciri hewan bertulang belakang apakah termasuk sebagai mamalia, reptil, burung, ikan atau amphibi. •
Pemodelan Prediktif (Predictive modelling) Pemodelan prediksif bertujuan untuk mendapatkan sebuah nilai yang tidak diketahui atau nilai mendatang dari data sebelumnya. Pada Tabel 2.2 menunjukkan bahwa model klasifikasi dapat juga digunakan untuk melakukan prediksi nilai yang tidak diketahui dengan menggunakan model klasifikasi yang diperoleh dari Tabel 2.1. Tabel 2.2 Prediksi Hewan Bertulang Belakang Name
Gila
Body
Skin
Gives
Aquatic
Aerial
Has
Hibern
Class
Temperature
Cover
Birth
Creatur
Creatu
Legs
ates
Label
e
re
No
No
Yes
Yes
?
Cold-blooded
Scales
No
monster
Sumber : (Tan, Steinbach, & Kumar, 2006, hal. 147)
Berdasarkan dari parameter keluaran proses klasifikasi, dapat menjadi dua macam, yaitu supervised classification dan unsupervised classification.
14
2.3.1 Supervised Classification Pada proses klasifikasi ini, parameter keluaran dari klasifikasi sudah ditentukan terlebih dahulu dengan melibatkan mekanisme external, seperti human feedback, guna menyediakan informasi klasifikasi yang benar(Susanto, 2006). Berikut akan dijelaskan beberapa algoritma yang biasa digunakan dalam supervised classification.
2.3.1.1
Naive Bayes Classifier
Metode klasifikasi ini menggunakan konsep peluang dalam menentukan kelas dokumen. Metode ini menggunakan asumsi bahwa dalam sebuah dokumen kemunculan kata tidak mempengaruhi kemunculan kata yang lain dan ketidak munculan kata tidak mempengaruhi ketidakmunculan kata yang lain. Walaupun asumsi ini bertentangan dengan aturan bahasa, namun tidak mengurangi keakuratan dari metode ini (Susanto, 2006; Farisi, 2007). Aturan Bayes mengatakan bahwa agar klasfikasi memiliki tingkat akurasi yang tinggi, maka dokumen masukan |
memiliki nilai kategori dan
.
|
harus dipetakan ke dalam kelas yang
adalah peluang
untuk masuk ke dalam kelas
merupakan kelas kategori. Hal ini dapat dilihat pada persamaan: |
Persamaan berikut merupakan persamaan akhir yang akan digunakan untuk klasifikasi Bayes.
15
∏|
Pr ∑
|
∏|
Pr
| |
|
Keterangan : o
= nilai Bayes pada dokumen masukan
o
=
o | |
= jumlah dokumen pembelajaran pada kategori
o | |
= jumlah seluruh dokumen pembelajaran di semua
|
|
| |
kategori | o ∏
|
|
= perkalian probabilitas kemunculan kata ke-i dokumen masukan ke dalam seluruh dokumen kategori
o ∑ | o ∏
Pr |
= kumulatif probabilitas seluruh kategori |
= kumulatif perkalian probabilitas kemunculan kata ke –i dokumen masukan dalam seluruh kategori
o | |
= jumlah kata pada dokumen input
Pembagi pada persamaan diatas dapat dihilangkan karena tidak mempengaruhi nilai dari arg |
Nilai
. ditentukan dari persamaan: |
1 | |
∑
,
Keterangan: = probabilitas kemunculan kata ke-i dokumen
o
pembelajaran dari seluruh dokumen kelas j = jumlah kemunculan kata ke-i dokumen masukan
o
dalam seluruh dokumen pembelajaran kelas j o | |
= jumlah seluruh kata unik dokumen pembelajaran di kategori j
o ∑
,
= jumlah seluruh kata unik dokumen pembelajaran di seluruh kategori
16
2.3.1.2
Decision Tree based Methods
Decision tree merupakan metode klasifikasi dengan membuat model dari sebuah persoalan dalam bentuk pohon keputusan. Tiap simpul dari pohon menyatakan sebuah keputusan dan tiap daun menyatakan sebuah solusi. Jumlah dari simpul pohon yang dibuat tergantung jumlah fitur yang digunakan. Berikut gambar contoh sederhana dari decision tree.
Gambar 2.6 Contoh Decision Tree
Beberapa algoritma yang biasa digunakan dalam decision tree antara lain Hunt’s Algorithm, CART, ID3 - C4.5, SLIQ dan SPRINT Ketuntungan penggunaan dari metode ini antara lain: •
Mudah dimengerti, karena aturan dari proses klasifikasi dapat digambarkan dengan jelas.
•
Tidak membutuhkan asumsi dari data-data sebelumnya, dari data yang sudah ada bisa digunakan langsung untuk membuat decision tree.
•
Bisa digunakan untuk memproses data numerik ataupun data kelas
17
Sedangkan kelemahan dari metode ini antara lain: •
Atribut keluaran yang dihasilkan harus berupa kelas
•
Kelas keluaran terbatas, hanya memiliki satu atribut
•
Algoritma dalam decision tree tidak stabil
•
Tree yang terbuat dari data numerik dapat sangat rumit
2.3.1.3
Decision Rule Classifier
Klasifikasi ini mirip dengan decision tree, dengan membuat aturan-aturan yang membedakan dari data pembejaran yang ada menggunakan prinsip inductive rule learning. Proses pembelajaran aturan memilih aturan terbaik dari semua kemungkinan yang adasecara bottom up. Dapat dituliskan sebagai: … Dimana
adalah merupakan fitur dari dokumen dan
merupakan kelas
dokumen.
2.3.1.4
Artificial Neural Network
Artificial Neural Network merupakan tehnik yang digunakan dalam machine learning yang mensimulasikan cara kerja jaringan syaraf pada otak manusia. Seperti pada otak manusia, fungsi jaringan ditentukan oleh hubungan antar neuron. Hubungan antar neuron ini memiliki bobot, dan untuk mendapatkan sebuah model, dilakukan proses pembelajaran dengan menyesuaikan bobot dari masing-masing neuron.
18
Prinsip dasar dari metode ini adalah membandingkan antara masukan dengan keluaran untuk menyesuaikan bobot pada setiap proses pembelajaran. Proses ini dilakukan iterasi sampai dengan nilai bobot mencapai kondisi dimana masukan sudah sesuai dengan target keluaran. Algoritma yang biasa digunakan adalah back propagation, menggunakan keluaran kesalahan (error output) untuk mengubah nilai bobot dalam arah mundur. Untuk mendapatkan nilai kesalahan tahap forward propagation harus dilakukan terlebih dahulu. Pada forward propagation neuron akan diaktifkan menggunakan fungsi aktifasi yang dapat didiferensiakan, seperti: •
Log Sigmoid 1 1 dengan 1
•
Tansig 1 dengan 1
•
Purelin dengan 1
1
19
Gambar 2.7 Arsitektur Jaringan Backpropagation
Pada gambar 2.7 dapat dilihat arsitektur jaringan backpropagation dengan lapisan masukan x1, x2, x3; satu lapisan tersembunyi z1, z2; dan satu unit keluaran yaitu y. Masing-masing unit masukan dihubungkan dengan lapisan tersembunyi dengan bobot tertentu. Demikian juga antara unit pada lapisan tersembunyi dengan unit keluaran.
2.3.1.5
Support Vector Machine (SVM)
Konsep support Vector Machine (SVM) dikembangkan oleh Boser, Guyon, Vapnik, dan pertama kali dipresentasikan pada tahun 1992 di Annual Workshop on Computational Learning Theory. Konsep dasar SVM sebenarnya merupakan kombinasi harmonis dari teori-teori komputasi yang telah ada puluhan tahun sebelumnya, seperti margin hyperplane, kernel, dan konsep-konsep
20
pendukung yang lain. Akan tetapi hingga tahun 1992, belum pernah ada upaya merangkaikan komponen-komponen tersebut (Satriyo, Budi, & Handoko, 2003). Berbeda dengan strategi neural network yang berusaha mencari hyperplane pemisah antar kelas, SVM bekerja atas prinsip Structural Risk Minimization (SRM) dengan tujuan menemukan hyperplane terbaik yang memisahkan dua buah kelas pada input space. Prinsip dasar SVM adalah klasifikasi linear, dan selanjutnya dikembangkan agar dapat bekerja pada problem non-linear, dengan memasukkan konsep kernel trick pada ruang kerja berdimensi tinggi.
Gambar 2.8 SVM berusaha menemukan hyperplane terbaik untuk memisahkan kelas (Nugroho, Witarto, & Handoko, 2003)
Pada Gambar 2.8 memperlihatkan bagaimana konsep dasar dari SVM., penyebaran data ditunjukkan oleh warna merah (kotak) dan warna kuning (lingkaran). Data berwarna merah merupakan anggota dari kelas -1 dan data berwarna kuning adalah anggota dari kelas +1. Masalah utama dari klasifikasi adalah mencari hyperplane pemisah antara kedua kelas. Dari gambar Gambar 2.8a
21
terlihat bahwa ada banyak alternatif garis pemisah (discrimination boundaries) antara kedua kelas. Hyperplane pemisah terbaik antara kedua kelas diperoleh dengan cara mengukur margin dari hyperplane dan mencari margin terbesar. Margin adalah jarak antara hyperplane tersebut dengan data terdekat dari masing-masing kelas. Data yang paling dekat dengan hyperplane disebut sebagai support vector. Garis solid pada gambar Gambar 2.8b menunjukkan hyperplane yang terbaik, yaitu yang terletak tepat pada tengah-tengah kedua class, sedangkan titik merah dan kuning yang berada dalam lingkaran hitam adalah support vector. Usaha untuk mencari lokasi hyperplane ini merupakan inti dari proses pembelajaran pada SVM.
wx+b=1 wx+b=0 wx’+b=-1 Gambar 2.9 Representasi Hyperplane
Misalkan dokumen yang tersedia direpresentasikan dalam bentuk vektor: , dimana
dan
,
, 1, 1 .
,…,
,
},
22
Diasumsikan dokumen tersebut dipisahkan secara sempurna ke dalam kelas -1 dan +1 oleh hyperplane berdimensi d, yang didefinisikan: · dimana
0,
merupakan vektor normal pada pad hyperplane tersebut, dan adalah
jarak dari hyperplane ke titik pusat. Sehingga data yang termasuk dalam kelas -1 dan 1 dapat adalah data yang memenuhi persamaan:
Misal
dan
1, jika
·
0
1, jika
·
0
adalah vektor terluar dari masing-masing kelas yang terdekat
dengan hyperplane pemisah, dengan jarak
dan
. Maka fungsi keputusan
yang digunakan dalam klasifikasi: ,
2.3.1.5.1
·
Klasifikasi Data Linear Separable
Data dapat dinyatakan terpisah sempurna secara linear oleh hyperplane, jika didapat pasangan nilai
,
sedemikian hingga data dapat dipisahkan ke dalam
kelas -1 dan +1, yang memenuhi kondisi berikut: ·
1 , jika
·
1 , jika
= -1 =1
Kedua kondisi diatas dapat disederhanakan : · Terdapat banyak pasangan
1 , = 1,2,3,…, N ,
yang dapat membentuk hyperplane, dalam hal
ini hyperplane yang dicari adalah yang paling optimal, yang memiliki margin
23
maksimum antar kelas. Margin didefinisikan sebagai
, sehingga
margin akan memiliki nilai maksimal jika ·
·
Berdasarkan persamaan diatas, maka mencari margin maksimal sama dengan 2
meminimumkan nilai Min
, secara matematis dinyatakan sebagai:
2
dengan memperhatikan ·
1 , = 1,2,3,…, N
Dengan menggunakan metode Lagrange, masalah klasifikasi tersebut dapat dinyatakan sebagai masalah meminimumkan fungsi Lagrange.
, ,
1 2
2
, , Dimana
2
∑
.
1
.
∑
adalah pengali Lagrange
Karena, 0
∑
0
∑
=0
Maka masalah Lagrange untuk klasifikasi dapat dinyatakan : Min
, ,
dengan memperhatikan,
2
∑
.
∑
24
∑ ∑
=0
Model persamaan diatas merupakan model primal Lagrange. Sedangkan model dual dari masalah diatas: ∑,
∑
Maks
dengan memperhatikan, ∑
=0
Solusi dari masalah dual diatas adalah : ∑
Dengan didapatnya pasangan nilai
,
maka telah didapatkan hyperplane yang
optimal.
2.3.1.5.2
Klasifikasi Data Linear Non Separable
Penjelasan di sebelumnya berdasarkan asumsi bahwa kedua belah kelas dapat dipisahkan secara sempurna oleh hyperplane. Akan tetapi, pada umumnya dua buah kelas pada input space tidak dapat terpisahkan secara sempurna. Untuk mengatasi kondisi ini, SVM dirumuskan ulang dengan menggunakan teknik softmargin, dengan mengikutsertakan slack variable
0. Misalkan ξ adalah
jarak antara garis pemisah (decision boundary) dengan data, maka persamaan dirumuskan kembali menjadi: · ·
1 1
, jika , jika
= -1 =1
25
Untuk optimasi margin dilakukan dengan meminimumkan nilai
2
dan
meminimumkan kesalahan klasifikasi ∑
)k
dimana k=1 atau k=2 dan C adalah parameter regulasi yang digunakan untuk mengontrol hubungan antara slack variable dengan
.
Jika digunakan nilai k=1, maka pada dual Lagrange, semua nilai ξ dan suku yang memuat pengali Lagrange akan hilang, sehingga bentuk dual Lagrange menjadi: ∑
Maks
∑,
dengan memperhatikan ∑
=0
0 Solusi dari masalah dual diatas adalah : ∑
2.3.1.5.3
Klasifikasi Data Non Linear
Dalam kenyataannya tidak semua data dapat dipisahkan secara linear, untuk mengatasi masalah tersebut dilakukan pemetaan terhadap data dari input space ke dalam feature space yang memiliki dimensi yang lebih tinggi seperti terlihat pada Gambar 2.10. Dengan dilakukan pemetaan tersebut maka hyperplane pemisah antara dua kelas dapat diperoleh, hal ini sesuai dengan teorema Cover yang menyatakan “Jika suatu transformasi bersifat non linear dan dimensi dari feature space cukup tinggi, maka data pada input space dapat dipetakan ke
26
feature space yang baru, dimana pattern-pattern tersebut pada probabilitas tinggi dapat dipisahkan secara linear” (Nugroho, Witarto, & Handoko, 2003).
Gambar 2.10 Pemetaan data ke dimensi yang lebih tinggi
Misalkan Φ adalah sebuah pemetaan non linear dari input space Rn ke ruang feature spaceF, dinyatakan sebagai: Φ
RnÆ F , dimana dimensi dari F lebih besar dari dimensi Rn
Jika semua data yang akan diklasifikasi ditransformasikan ke dalam feature space, masalah klasifikasi dapat diselesaikan dengan cara-cara yang telah dibahas sebelumnya. Berikut jenis-jenis kernel yang biasa digunakan dalam SVM. •
Kernel Polinomial ,
•
1
Kernel Gaussian ,
•
.
exp
| .
Kernel Sigmoid ,
.
|
27
2.3.2 Unspervised Classification Pada klasifikasi ini, proses klasifikasi dilakukan secara mandiri tanpa adanya informasi lain dari luar yang digunakan sebagai dasar analisa struktur dan hubungan antar data (Susanto, 2006). Proses yang biasa dilakukan pada klasifikasi ini adalah klastering, data dibagi menjadi beberapa klaster, dimana tiap klaster yang memiliki karakteristik yang sama. Contoh algoritma klastering yang paling dasar adalah k-means.
2.3.2.1
K-means Clustering
Algoritma k-means merupakan algoritma dasar dalam proses klastering. Algoritma ini melakukan klastering menggunakan jarak dokumen dengan centroid dari sebuah klaster yang paling dekat (Susanto, 2006). Berikut adalah algoritma dasar dari k-means clustering: 1
Inisiasi klaster (dengan k-centroid)
2
Masukan setiap dokumen ke dalam klaster yang paling cocok berdasarkan ukuran kedekatan dengan centroid. Pengukuran kedekatan antara dua term vektor dapat menggunakan cosine similarity
3
Setelah semua dokumen masuk ke dalam klaster, maka pusat dari centroid klaster dihitung ulang berdasarkan dokumen yang ada di dalam klater tersebut.
4
Jika centroid tidak berubah, maka proses klastering telah selesai. Sebaliknya apabila centroid berubah, maka dihitung kembali ke proses nomor 2.
28
Contoh dari k-means clustering dapat dilihat pada gambar berikut. Pada gambar terlihat proses iterasi berlangsung (gambar a-b-c), dimana centroid dan cluster akan terus berubah sampai kondisi centroid tidak berubah (gambar c)
Gambar 2.11 Ilustrasi k-means
Algoritma k-means sangat sederhana dan memiliki kompleksitas linear. Dengan kompleksitas linear, membuat algoritma ini dapat berjalan dengan baik pada data set yang besar. Hal tersebut merupakan kelebihan dari algoritma ini. Sedangkan kelemahan dari algoritma ini adalah jumlah klaster harus ditentukan terlebih dahulu dan klaster yang dihasilkan sangat tergantung pada inisiasi awal dari centroid(Susanto, 2006).
2.3.2.2
Single Pass Clustering
Single Pass Clustering tergolong dalam hierarchical clustering.Algoritma dari single pass clustering adalah sebagai berikut: 1.
Masukkan dokumen pertama d1 sebagai representasi dari klaster pertama c1
2.
Untuk dokumen selanjutnya di, dihitung derajat kemiripan dengan wakil dari masing-masing klaster menggunakan cosine similarity. Kemudian catat nilai maksimum similarity Smax
29
3.
Jika nilai Smax lebih besar dari batas nilai (thresold value) ST, tambahkan dokumen pada klaster yang bersesuaian dan representasi dari klaster dihitung kembali. Jika sebaliknya maka digunakan di untuk inisiasi klaster baru.
4.
Jika masih ada dokumen di yang belum memiliki kelas maka kembali ke langkah 2.
Gambar 2.12 Ilustrasi Single Pass Clustering
Contoh dari single pass clustering dapat dilihat pada gambar diatas. Gambar a menunjukkan dokumen yang berwarna merah adalah dokumen yang akan dimasukkan ke dalam klaster hijau atau kuning. Gambar b menunjukkan dokumen merah masuk ke dalam klaster hijau karena perhitungan derajat kemiripan yang diperoleh pada klaster hijau lebih besar daripada pada klaster kuning dan tidak lebih kecil dari thresold value. Pada gambar c sebaliknya dari gambar b. Sedangkan pada gambar d menunjukkan bahwa derajat kemiripan lebih kecil dari thresold value sehingga membentuk sebuah klaster sendiri. Kelebihan dari algoritma ini adalah sederhana dan dapat dilakukan hanya satu kali (tidak memerlukan iterasi), sedangkan kelemahannya jumlah klaster yang terbentuk tergantung dari urutan memasukkan dokumen(Susanto, 2006).
30
2.4
Analisis Sentimen Analisis sentimen adalah proses memahami, mengekstrak dan mengolah
data tekstual secara otomatis untuk mendapatkan informasi (Pang & Lee, Opinion Mining and Sentiment Analysis, 2008).Analisis sentimen merupakan salah satu bagian dari opinion mining(Liu, Sentiment Analysis and Subjectivity, 2010). Pada dasarnya analisis sentimen merupakan proses klasifikasi data tekstual. Akan tetapi pada kenyataannya, analisis sentimen tidak semudah proses klasifikasi tekstual biasa, karena pada analisis sentimen terkait dengan penggunaan bahasa. Dimana terdapat ambigu dalam penggunaan kata, tidak adanya intonasi dalam sebuah data tekstual, serta perkembangan dari bahasa itu sendiri(Liu, Sentiment Analysis: A Multi-Faceted Problem, 2010). Berdasarkan hasil klasifikasinya, analisis sentimen terbagi menjadi dua: •
Klasifikasi dokumen ke dalam kelas opini atau fakta, atau lebih dikenal dengan subjectivity classification.
•
Klasifikasi dokumen ke dalam kelas sentimen positif atau negatif, yang lebih dikenal dengan analisis sentimen itu sendiri. Dalam klasifikasi ini, ada dua proses penting yaitu memastikan bahwa dokumen yang dilakukan klasifikasi adalah merupakan opini dan mengandung sentimen didalamnya, serta mengetahui topik dari dokumen tersebut sehingga dapat ditentukan obyek dan fitur apakah positif atau negatif.
2.4.1 Opinion Lexicon Seperti dijelaskan sebelumnya, bahwa dalam proses analisis sentimen, dokumen yang diklasifikasi haruslah merupakan sebuah opini, dimana terdapat
31
sentimen di dalam dokumen tersebut. Untuk mendapatkan dokumen bersentimen, kata yang ada di dalam dokumen harus dianalisis sehingga dapat disimpulkan mengandung sentimen atau tidak.Kumpulan dari kata-kata yang mengandung sentimen biasa disebut sebagai opinion lexicon, sedangkan kata itu sendiri biasa disebut sebagai polar words, opinion-bearing words dan sentiment words. Contoh kata yang mengandung opini dengan sentimen positif adalah “cantik”, “indah”, “bagus” dan “luar biasa”. Sedangkan contoh kata yang mengandung sentimen negatif adalah “jelek”, “lemah” dan “payah”(Liu, Sentiment Analysis and Subjectivity, 2010). Penggunaan kata yang memiliki opini pada prakteknya ada dua macam, yaitu opini langsung dan opini perbandingan (Pang & Lee, Opinion Mining and Sentiment Analysis, 2008). Opini langsung adalah pengekpresian sentimen terhadap sebuah target obyek seperti produk, topik atau orang dalam sebuah dokumen. Contohnya adalah: “Kualitas gambar dari kamera ini luar biasa”. Sedangkan opini perbandingan adalah membandingkan kemiripan atau perbedaan untuk obyek lebih dari satu. Contoh penggunaannya adalah: “Kamera merek X lebih murah daripada merek Y”. Teknik
pengumpulan
kata-kata
yang
memiliki
sentimen
dapat
menggunakan pendekatan berdasarkan kamus(Liu, Sentiment Analysis and Subjectivity, 2010). Strategi yang digunakan adalah mendaftar kata yang terlebih dulu diketahui sentimennya, kemudian melakukan query ke dalam kamus untuk mendapatkan persamaan kata (sinonim) dan lawan kata (antonim). Hasil query selanjutnya digunakan sebagai paremeter masukan untuk query berikutnya, sampai dengan tidak ditemukan kata yang baru lagi. Untuk bahasa Inggris kamus
32
yang biasa digunakan adalah WordNet, dimana dalam kamus ini sudah terdapat lexical yang lengkap untuk bahasa Inggris. Kelemahan dari teknik ini adalah tidak bisa mendapatkan kata sesuai dengan domain tertentu. Misalnya kata diam/tenangpada speaker biasanya bermakna negatif, tetapi pada mobil dapat bermakna positif. Untuk mengeliminasi hal tersebut, maka digunakan teknik berdasarkan korpus. Dimana identifikasi kata dilakukan pada korpus dengan domain tertentu yang sudah ada. Masalah yang muncul adalah tidak ada sebuah korpus dengan kosakata yang lengkap untuk semua bahasa.
2.4.2 Analisis SentimenBerdasarkan Fitur dari Obyek Analisis sentimen dalam hal ini ditentukan terlebih dahulu domain dari dokumen yang akan diproses, mengingat bahwa sentimen kata bisa berbeda-beda tiap domain. Proses analisis sentimen yang dilakukan dalam hal ini adalah: •
Identifikasi fitur dari obyek yang akan diklasifikasikan. Contohnya pada kalimat “Kualitas gambar yang dihasilkan dari kamera ini luar biasa”, fitur obyek dalam hal ini adalah kualitas gambar.
•
Penentuan sentimen dari dokumen berdasarkan fitur yang diperoleh. Dari contoh diatas, fitur yang digunakan sebagai identifikasi adalah kualitas gambar, selanjutnya dicari opini dalam dokumen yang menyatakan sentimen, dalam hal ini adalah “luar biasa”. Sehingga dokumen tersebut memiliki sentimen positif
33
2.4.3 Fitur dan Pembobotan Sebuah dokumen dapat dinyatakan dalam model vector-space, dimana dokumen diwakili dengan sebuah vektor dari keywords yang diextract. Dari vektor dokumen yang didapat, dilakukan pembobotan yang mewakili seberapa penting keyword tersebut dalam dokumen dan dalam keseluruhan koleksi dokumen. Berikut akan dijelaskan fitur-fitur yang digunakan dalam pembobotan. 2.4.3.1
Fitur Unigram
Dalam fitur unigram, kata dan simbol dalam dokumen direpresentasi ke dalam bentuk vektor, dan tiap kata atau simbol dihitung sebagai satu fitur(O’Keefe & Koprinska, 2009). Semua kata yang terkandung dalam dokumen didaftarkan, dinyatakan dengan
,
,…,
yang merupakan daftar kata. Jumlah yang merupakan
kemunculan kata dalam dokumen dinyatakan dengan jumlah kemunculan kata dokumen
muncul dalam dokumen
direpresentasikan dalam vektor
. Sehingga didapat ,
, …,
.
Perhitungan bobot yang biasa digunakan antara lain : 1. Feature Frequency (FF) Pembobotan ini merupakan cara yang paling sederhana dilakukan. Dilakukan dengan menghitung jumlah kemunculan kata dalam dokumen. Misalnya kata “bagus” muncul sebanyak sepuluh kali dalam satu dokumen, maka bobot dari kata tersebut adalah sepuluh. Dalam bentuk vektor dituliskan: ,
, …,
2. Feature Presence (FP) Bentuk vektor dari pembobotan ini adalah sebuah vektor biner. Dimana hanya menggunakan kemunculan kata dalam dokumen, bukan frekuensi. Kata yang
34
ada dalam dokumen diberi bobot 1, dan yang tidak ada diberi bobot 0. Contohnya kata “bagus” muncul sebanyak sepuluh kali dalam dokumen, maka bobot dari kata tersebut adalah 1. Dalam persamaan matematika: ni(d) = 1 , jika fitur fi ada di dokumen d ni(d) = 0 , jika fitur fi tidak ada di dokumen d 3. Term Frequency – Inverse Document Frequency (TFIDF) Perhitungan bobot dengan cara ini menggunakan kombinasi dari dua nilai, yaitu frekuensi kata dan inverse frekuensi dokumen yang didapat dari membagi jumlah dokumen secara keseluruan dengan jumlah dokumen dimana kata tesebut muncul. Dalam persamaan matematika ni(d) = dfi . Log D/dfi dimana : df adalah jumlah fitur fi dalam seluruh dokumen D adalah jumlah dokumen 4. SentiWordNet Word Groups SentiWordNet merupakan pengembangan dari WordNet, adalah kamus sentimen dalam bahasa Inggris. Dalam kamus ini setiap kata memiliki nilai dalam sentimen positif atau negatis. Dari nilai tersebut dapat dijumlahkan untuk selanjutnya digunakan sebagai bobot fitur. 5. CHI (Statistic Measure) Pembobotan ini dilakukan dengan menghitung secara statistik hubungan antara kata dengan kategori. Dinyatakan dengan: , Dan
,
35
Dimana A adalah jumlah kemunculan t dan ci; B adalah jumlah kemunculan t tanpa ci; E adalah jumlah kemunculan ci tanpa t; D adalah jumlah kemunculan tanpa ci dan t; dan N adalah jumlah total dokumen 6. MI (Mutual Information) MI adalah kriteria yang biasa digunakan dalam permodelan bahasa secara statistik, didapat dengan menghubungkan antara asosiasi kata dan aplikasi yang terkait. (Songbo & Jin, 2008). Dinyantakan dalam persamaan matematika: ,
log ,
Dan
dimana A, B, E, D dan N memiliki definisi yang sama dengan CHI 7. IG (Information Gain) IG biasa digunakan sebagai kriteria good-ness dalam machine learning. Dilakukan dengan mengukur jumlah bit informasi yang diperoleh untuk mengetahui ada tidaknya istilah dalam dokumen. | |
| |
log
|
log
|
| |
|
log
|
dimana P(ci) adalah kemungginan munculnya kelas ci; P(t) adalah kemungkinan munculnya kata t; P( ) adalah kemungkinan kata t tidak muncul
36
2.4.3.2
Fitur n-gram
Pada analisis dengan menggunakan fitur n-gram antara lain menggunakan syntactic, semantic, link based, dan part-of-speech. Dalam hal ini fitur diambil bukan dari kata per kata melainkan dari keseluruhan dokumen, dimana hubungan tiap kata dalam sebuah dokumen dianalisa terlebih dahulu untuk mendapatkan relasi antar kata. Dari kata-kata yang membentuk relasi tersebut diambil menjadi sebuah fitur klasifikasi. 2.4.4 Teknik dalam Analisis Sentimen Penelitian mengenai analisis sentimen masih terus berkembang, dimana masing-masing penelitian menggunakan metode, fitur, dan teknik yang berbedabeda. Baik berupa pengembangan, penggabungan ataupun membuat sebuah metode baru. Secara garis besar teknik dalam melakukan analisis sentimen terbagi menjadi dua(Boiy, Hens, Moens, & Deschacht, 2007), yaitu: 1. Menggunakan teknik simbol Pada teknikini, dilakukan analisis terhadap setiap kata yang ada pada dokumen dan melakukan ekstraksi hubungan untuk mendapatkan sentimen.Untuk menggunakan teknik ini, makna dari setiap kata harus diketahui dan aturan kata dalam kalimat berbeda-beda tergantung dari bahasa yang digunakan. Contoh penggunaan teknik simbol antara lain dengan menggunakan kamus sebagai dasar, dimana sebuah dokumen dinyatakan sebagai representasi dari kata (Boiy, Hens, Moens, & Deschacht, 2007; Maurel, Curtoni, & Dini, 2008; Liao, Cao, Tan, Liu, Guodong, & Cheng, 2006; Turney, 2002; Ahn, Geyer,Werner, Dugan, & Millen, 2010; Songbo & Jin, 2008; Nasukawa & Yi, 2003; Dini & Mazzini, 2002; Hatzivassiloglou & R. McKeown, 1997, hal.
37
174-181). Dari tiap kata tersebut ditentukan sentimennya kemudian dengan menggunakan fungsi tertentu (penjumlahan, rata-rata, bobot, dan lain-lain) digunakan untuk mendapatkan sentimen dari sebuah dokumen. Contoh lainnya adalah dengan memperhatikan tata-bahasa dari sebuah dokumen (Dini & Mazzini, 2002), yang memperhatikan hubungan antara kata-kata yang menyusun dokumen tersebut. Penggunaan teknik ini sangat tergantung pada bahasa yang digunakan, karena aturan kata dalam bahasa berbeda-beda. Bahkan meskipun telah dirumuskan aturan baku dalam bahasa, pada kenyataannya tidak dapat diterapkan secara sempurna, hal ini terkait dengan bahasa itu sendiri yang terus berkembang. 2. Menggunakan teknikmachine learning. Teknikmachine learningmenggunakan statistik untuk memproses text (Maurel, Curtoni, & Dini, 2008). Contoh penggunaan teknikmachine learning(Maurel, Curtoni, & Dini, 2008; Boiy, Hens, Moens, & Deschacht, 2007; O’Keefe & Koprinska, 2009; Franky & Manurung, 2008; Hatzivassiloglou & R. McKeown, 1997; Ahn, Geyer,Werner, Dugan, & Millen, 2010; Songbo & Jin, 2008; Mullen & Collier, 2004)antara lain menggunakan Super Vector Machine(SVM), Naive Bayes, Maximum Entropy, Centroid Classifier, dan K-nearest Neighbor.
2.4.5 Penelitian Analisis Sentimen Sebelumnya Pada Tabel 2.3dapat kita lihat sebagian penelitian mengenai analisis sentimen yang menggunakan teknik machine learning.
Tabel 2.3Penelitian Analisis Sentimen menggunakan Machine Learning Peneliti
Teknik/Algoritma
Fitur
Domain
Bahasa
Ketelitian
(Maurel, Curtoni,
•
SVM
•
•
DEFT'07
Perancis
F1 :
& Dini, 2008)
•
NB
•
Forum diskusi
•
Newsgroup
n-gram
(Songbo & Jin,
•
centroid classifier
•
Mutual Information (MI)
•
Pendidikan
2008)
•
K-nearest neighbor
•
Information Gain (IG)
•
Film
•
winnow classifier
•
CHI statistics (CHI)
•
properti
•
Naıve Bayes
•
Document Frequency (DF)
•
SVM
(Boiy, Hens,
•
SVM
•
Unigram (FF)
•
Film (Pang & Lee)
Moens, &
•
Naive Bayes
•
n-gram
•
Blog
Deschacht, 2007)
•
Maximum entropy
•
Forum diskusi
•
Website lainnya
•
Film (Pang & Lee)
(Franky &
•
NB
Manurung, 2008)
•
Maximum Entropy
•
SVM
•
SVM
(O’Keefe & Koprinska, 2009)
•
NB
•
Unigram (FF, FF(N), FP, TF-IDF, TF-IDF(N))
• •
•
Unigram (FF, FP, TF-IDF)
Film (Pang & Lee)
0,51 - 0,70
Chineese
F1 : 0.4653 - 0.8992
Inggris
Akurasi : 75.85% - 86.35%
Indonesia
Akurasi :
(terjemahan)
69.50% - 81.45%
Inggris
Akurasi : 59.9% - 87.15%
SentiWordNet (SWN-SG, SWNPG, SWN-PS)
(Yessenov &
•
Naive Bayes
Misailovic, 2009)
•
Maximum Entropy
•
Decision Trees
•
K-Means clustering
•
•
Unigram (FF)
Film
Inggris
Akurasi: 52.74% - 64.71%
38
39
Korpus yang digunakan pada penelitian analisis sentimen, baik dengan teknik simbol maupun teknikmachine learningantara lain menggunakan data wall street journal(Hatzivassiloglou & R. McKeown, 1997), data forum diskusi(Ahn, Geyer,Werner, Dugan, & Millen, 2010; Boiy, Hens, Moens, & Deschacht, 2007), data filem(Songbo & Jin, 2008; O’Keefe & Koprinska, 2009; Franky & Manurung, 2008; Mullen & Collier, 2004), data permainan komputer (Maurel, Curtoni, & Dini, 2008), data pariwisata (Maurel, Curtoni, & Dini, 2008), data pendidikan (Songbo & Jin, 2008), datarumah (Songbo & Jin, 2008), serta data dari blog dan media sosial (Boiy, Hens, Moens, & Deschacht, 2007; Nasukawa & Yi, 2003; Liao, Cao, Tan, Liu, Guodong, & Cheng, 2006; Dini & Mazzini, 2002). Penelitian pada umumnya penelitian dilakukan pada informasi tekstual dengan bahasa Inggris. Dari hasil pencarian di internet hanya ditemukan satu penelitian pada dokumen berbahasa Indonesia (Franky, 2008). Dimana penelitian tersebut merupakan pengaplikasian dari penelitian sebelumnya (Pang, Lee, & Vaithyanathan, 2002) dengan menterjemahkan korpus filem menggunakan perangkat lunak ke dalam bahasa Indonesia.Minimnya jumlah penelitian analisis sentimen ini tentu saja sangat kurang, mengingat bahasa Indonesia digunakan lebih dari 200 juta penduduk Indonesia untuk menyatukan 750 bahasa daerah(Rni/Ant/Berita8.com, 2009). Analisis sentimen merupakan bagian dari pemrosesan bahasa alami yang akan terus berubah seiring dengan perkembangan bahasa yang digunakan, dimana banyak faktor yang mempengaruhi dalam menterjemahkan bahasa yang digunakan. Penggunaan machine learning diharapkan dapat menghilangkan pengaruh dari faktor bahasa tersebut.
40
Dalam klasifikasi menggunakan teknik machine learning metode yang biasa digunakan adalah metode klasifikasi Naive Bayes (NB) dan SVM. Untuk proses klasifikasi sentimen pada penelitian ini menggunakan metode machine learning SVM yang memiliki kemampuan dalam berbagai aplikasinya menempatkannya sebagai state of the art dalam pattern recognition. (Satriyo, Budi, & Handoko, 2003; Pang & Lee, Opinion Mining and Sentiment Analysis, 2008). Pemilihan SVM karena konsep metode ini adalah menemukan hyperplane terbaik yang berfungsi untuk memisahkan ke dalam dua kelas yang berbeda, tidak seperti NB yang dirancang untuk membedakan dengan berdasarkan probabilitas. Halini bisa dibuktikan dari penelitian sebelumnya (Pang, Lee, & Vaithyanathan, Thumbs up? Sentiment Classification using Machine Learning, 2002), menggunakan metodelearning SVM, Naive Bayes dan Maximum Entropy untuk dengan menggunakan delapan fitur yang berbeda. Hasil penelitian tersebut didapat nilai akurasi tiap-tiap fitur yang digunakan, metode SVM memiliki akurasi lebih baik pada lima fitur, sedangkan ME dua fitur dan NB satu fitur. Dikarenakan terbatasnya korpus dalam bahasa Indonesia, maka korpus dalam penelitian ini akan menggunakan data dari microblogging Twitter. Adapun metode dalam pengumpulan korpus merujuk pada penelitian “Twitter as a Corpus for Sentiment Analysis and Opinion Mining” (Alexander & Paroubek, 2010) dengan lebih dikhususkan pada Twitter post yang menggunakan bahasa Indonesia.
