bab ii tinjauan pustaka - library.binus.ac.idlibrary.binus.ac.id/ecolls/ethesisdoc/bab2/muhamad...
Post on 07-Apr-2019
216 Views
Preview:
TRANSCRIPT
5
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:
6
Feature vector (fv) miner
Query enrichment
Onto‐driven retrieval engine
Document repositorySearch result
ontology query
Ontology repository
Feature vector repository
Query and indexing system wrappers
e.g. Lucene, Nutch, Yahoo, Google, etc
IR System
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).
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.
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
9
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.
Multimedia Data MiningText Mining
Image Mining
Video Mining
Audio Mining
Mining Combinations of Data Types
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).
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.
InputAttribute set (x)
Classification model
OutputClass label (y)
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
Temperature
Skin Cover
Gives Birth
Aquatic Creature
Aerial Creature
Has Legs
Hibernates
Class Label
human warm-blooded
hair yes no no yes no mammal
phyton cold-blooded
scales no no no no yes reptile
salmon cold-blooded
scales no yes no no no fish
whale warm-blooded
hair yes yes no no no mammal
frog cold-blooded
none no semi no yes yes amphibian
komodo cold-blooded
slaces no no no yes no reptile
bat warm-blooded
hair yes no yes yes yes mammal
pigeon warm-blooded
feathers no no yes yes no bird
cat warm-blooded
fur yes no no yes no mammal
leopard cold-blooded
scales yes yes no no no fish
turtle cold-blooded
scales no semi no yes no reptile
penguin warm- feathers no semi no yes no bird
13
blooded porcupine warm-
blooded quills yes no no yes yes mammal
eel cold-blooded
scales no yes no no no fish
salamander cold-blooded
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 Body
Temperature
Skin
Cover
Gives
Birth
Aquatic
Creatur
e
Aerial
Creatu
re
Has
Legs
Hibern
ates
Class
Label
Gila
monster
Cold-blooded Scales No No No Yes Yes ?
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 harus dipetakan ke dalam kelas yang
memiliki nilai | . | adalah peluang untuk masuk ke dalam kelas
kategori dan 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 ∑ Pr = kumulatif probabilitas seluruh kategori
o ∏ || | = 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:
o = probabilitas kemunculan kata ke-i dokumen
pembelajaran dari seluruh dokumen kelas j
o = jumlah kemunculan kata ke-i dokumen masukan
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 1
• Purelin
dengan
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.
Gambar 2.9 Representasi Hyperplane
Misalkan dokumen yang tersedia direpresentasikan dalam bentuk vektor:
, , , , … , , },
dimana dan 1, 1 .
wx+b=1 wx+b=0 wx’+b=-1
22
Diasumsikan dokumen tersebut dipisahkan secara sempurna ke dalam kelas -1 dan
+1 oleh hyperplane berdimensi d, yang didefinisikan:
· 0,
dimana 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:
1, jika · 0
1, jika · 0
Misal dan 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
· 1 , jika = 1
Kedua kondisi diatas dapat disederhanakan :
· 1 , = 1,2,3,…, N
Terdapat banyak pasangan , 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
meminimumkan nilai 2 , secara matematis dinyatakan sebagai:
Min 2
dengan memperhatikan
· 1 , = 1,2,3,…, N
Dengan menggunakan metode Lagrange, masalah klasifikasi tersebut dapat
dinyatakan sebagai masalah meminimumkan fungsi Lagrange.
, ,12 2 . 1
, , 2 ∑ . ∑
Dimana adalah pengali Lagrange
Karena,
0 ∑
0 ∑ = 0
Maka masalah Lagrange untuk klasifikasi dapat dinyatakan :
Min , , 2 ∑ . ∑
dengan memperhatikan,
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 , jika = -1
· 1 , jika = 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
kemunculan kata dalam dokumen dinyatakan dengan yang merupakan
jumlah kemunculan kata muncul dalam dokumen . Sehingga didapat
dokumen direpresentasikan dalam vektor , , … , .
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 berbeda-
beda. 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.
38
Tabel 2.3Penelitian Analisis Sentimen menggunakan Machine Learning Peneliti Teknik/Algoritma Fitur Domain Bahasa Ketelitian
(Maurel, Curtoni,
& Dini, 2008)
• SVM
• NB
• n-gram • DEFT'07
• Forum diskusi
• Newsgroup
Perancis F1 :
0,51 - 0,70
(Songbo & Jin,
2008)
• centroid classifier
• K-nearest neighbor
• winnow classifier
• Naıve Bayes
• SVM
• Mutual Information (MI)
• Information Gain (IG)
• CHI statistics (CHI)
• Document Frequency (DF)
• Pendidikan
• Film
• properti
Chineese F1 :
0.4653 - 0.8992
(Boiy, Hens,
Moens, &
Deschacht, 2007)
• SVM
• Naive Bayes
• Maximum entropy
• Unigram (FF)
• n-gram
• Film (Pang & Lee)
• Blog
• Forum diskusi
• Website lainnya
Inggris Akurasi :
75.85% - 86.35%
(Franky &
Manurung, 2008)
• NB
• Maximum Entropy
• SVM
• Unigram (FF, FF(N), FP, TF-IDF,
TF-IDF(N))
• Film (Pang & Lee) Indonesia
(terjemahan)
Akurasi :
69.50% - 81.45%
(O’Keefe &
Koprinska, 2009)
• SVM
• NB
• Unigram (FF, FP, TF-IDF)
• SentiWordNet (SWN-SG, SWN-
PG, SWN-PS)
• Film (Pang & Lee) Inggris Akurasi :
59.9% - 87.15%
(Yessenov &
Misailovic, 2009)
• Naive Bayes
• Maximum Entropy
• Decision Trees
• K-Means clustering
• Unigram (FF) • Film Inggris Akurasi:
52.74% - 64.71%
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.
top related