Klasifikasi Kategori dan Identifikasi Topik pada Artikel Berita Berbahasa Indonesia Tugas Akhir KI91391 Dosen Pembimbing: Dr. Agus Zainal Arifin, S. Kom, M. Kom
1
Penyusun: Aini Rachmania 5107100077
Pendahuluan
2
Latar Belakang Berita Laporan mengenai fakta atau ide terbaru yang benar,dan atau
penting bagi sebagian besar khalayak, melalui media berkala seperti surat kabar, radio, televisi, atau media online internet. (Siti, 2009)
Aliran informasi yang dinamis (Bracewell, 2009)
Karakter berita: Jumlah data besar Satu berita dengan berita lainnya berbeda Topik baru terus muncul Dibutuhkan: Klasifikasi berita untuk memudahkan navigasi berita 3
4
Algoritma yang Umumnya Digunakan Support Vector Machine Dapat diimplementasikan secara mudah (Nugroho, 2003) Sulit dipakai dalam problem berskala besar (Nugroho, 2003) Proses pembelajaran lambat (Bracewell, 2009) Harus dilatih ulang pada saat terjadi penambahan data (Princea, 2010)
Naive Bayesian Hasilnya cukup baik untuk sebagian kasus Ukuran vektor fitur yang dibutuhkan cukup besar (Johanes, 2006) Fitur – fitur data training harus disimpan (Bracewell, 2009)
5
Algoritma yang Digunakan Topic Analysis Diusulkan oleh David B. Bracewell, Jiajun Yan, Fuji Ren dan
Shingo Kuroiwa pada tahun 2009 pada paper yang berjudul “Category Classification and Topic Discovery of Japanese and English News Articles” Tidak memerlukan online training Membagi proses menjadi dua tahap: klasifikasi kategori dan identifikasi topik
6
Hirarki Berita Edukasi Beasiswa
Investasi
Ujian Nasional
Saham
SNMPTN
Praktik Dumping
Sertifikasi Guru
Pajak
Pendidikan Agama 7
Bisnis & Ekonomi
Permasalahan Bagaimana membangun aplikasi yang mampu menglasifikasikan
kategori berita tanpa harus melakukan online training Bagaimana membangun sebuah aplikasi yang dapat mengidentifikasi topik dari sebuah berita yang ada
Tujuan Membuat sebuah aplikasi yang dapat menglasifikasikan berita ke
kategori yang sesuai dan menemukan topik dari berita tersebut
8
Gambaran umum aplikasi
9
Klasifikasi Kategori
Corpus Dokumen Berita
Kategori
Perhitungan Likelihood Training
Perhitungan Threshold Seleksi Kategori
DataBase Dokumen Berita
DataBase Kamus dan Stoplist
Preprocess Perhitungan CosSim Seleksi t dengan CosSim terbesar Topik
Perhitungan threshold Seleksi topik menggunakant hreshold
10
Identifikasi Topik
Ekstraksi Kata Kunci Database Kata Kunci
Training
Case Folding
Filtering Eliminasi Stopword Stemming
Weighting
11
Keywords Extraction
Klasifikasi Kategori Pengambilan Kata Kunci pada Database Perhitungan Likelihood
Perhitungan Rata – rata dan standard Deviasi
Seleksi kategori 12
Identifikasi Topik Perhitungan CosSim
Seleksi CosSim Terbesar
Perhitungan Threshold
Seleksi Topik 13
Contoh Corpus Selasa, 19 April 2011 KOMPETISI UI Juara Kompetisi Bisnis di Paris DEPOK, KOMPAS.com - Tim Universitas Indonesia (UI) berhasil menjadi juara dunia setelah mengalahkan tujuh negara lainnya, yaitu Algeria, China, Czech Republic, Portugal, Romania, Rusia, dan Amerika Serikat di ajang kompetisi bisnis internasional tingkat mahasiswa Trust by Danone di Paris, Perancis, 4-6 April 2011. Para finalis diwajibkan berperan sebagai jajaran direksi untuk membuat perencanaan strategis di suatu negara dan mempresentasikan solusi mereka dalam bahasa Inggris di hadapan dewan juri. -- Vishnu Juwono Tim UI terdiri dari Ekky Gompa, Ivan Cahyadi, Shanty Debora, Stevenlie Satryaputra dari FEUI dan Chandra Satria Muda dari FTUI. Kelimanya tergabung dalam tim Jayawijaya yang mempresentasikan Way in Doing Business melalui media video kreatif dan sebuah objek pada babak International Final. Mereka juga diuji secara ketat dalam memahami filosofi bisnis yang tidak hanya mengejar profit tetapi juga kontribusi terhadap lingkungan dan sosial.Adapun kompetisi simulasi bisnis ini terdiri dari empat babak, yaitu seleksi CV, Trust Day, Country Final, dan International Final.
14
Klasifikasi Kategori (Offline)
15
Identifikasi Topik (Offline)
16
Thresholding topik
17
Uji Coba
Identifikasi kata (Filtering) “ “\t\n\r\f\’\”\\1234567890!@#$%^&*()_+{}|[]:;<,>.?/`~
Eliminasi Stopwords
Penghilangan kata – kata yang dianggap tidak berkontribusi
banyak pada isi dokumen (Yates dan Neto, 1999) Jenis kata yang termasuk stoplist adalah: 18
Kata depan Kata ganti Kata hubung Kata sandang
Stemming Terms Frekuensi Fira 1 gemar 1 memasak 1 masakannya 1 lezat 1
Terms Fira gemar masak lezat
Frekuensi 1 1 2 1
sesudah stemming sebelum stemming
19
Confix Stripping Stemmer Formula Kata berimbuhan : [ DP + [ DP + [ DP ] ] ] Kata-Dasar [ [+DS] [+PP] [+P] ] Alur stemming-1 :
/
/
/ /
/ /
/
/ /
/ /
[ DP + [ DP + [ DP ] ] ] Kata-Dasar [ [+DS] [+PP] [+P] ] Alur stemming-2 :
/
[ DP + [ DP + [ DP ] ] ] Kata-Dasar [ [+DS] [+PP] [+P] ] Keterangan: DP = Derivation Prefix (awalan “me-”, “be-”, “pe-”, “te-”, “di-”, “ke-”, “se-”) DS = Derivation Suffix (akhiran “-i”, “-kan”, “-an”) PP = Possesive Pronoun (kata ganti kepunyaan “-ku”, “-mu”, “-nya”) P = Partikel (“-kah”, “-lah”, “-tah”, “-pun”)
20
Weighting
Pada setiap term, diberikan pembobotan TF-IDF : Terms
Frekuensi
Fira
1
gemar
1
masak
2
lezat
1
N wij = tf ij . log 2 df j
Keterangan: wij = bobot term j pada dokumen i tfij = frekuensi kemunculan term j pada dokumen i N = jumlah keseluruhan dokumen yang diproses dfj = jumlah dokumen yang memiliki term j 21
Ekstraksi kata kunci Setiap dokumen yang telah selesai distemming diambil
keseluruhan termsnya Terms dokumen diberi bobot menggunakan TFIDF 10-15 terms terbaik diambil dan dikumpulkan menjadi kata kunci untuk kategori dan topik
22
Perhitungan Likelihood cj = kategori A = artikel k = keywords Kata Kunci Dokumen Uji
c1
c2
c3
c4
c5
c6
c7
c8
c9
k1
saham
0
0
0
0
3
0
0
0
0
k2
TBK
0
0
0
0
1
0
0
0
0
k3
mega
0
0
0
0
0
1
0
0
0
k4
top
0
0
0
0
0
0
0
0
0
k5
IHSG
0
0
0
0
2
0
0
0
0
k6
sektor
0
1
1
0
3
1
0
0
0
k7
indeks
0
0
0
0
2
0
0
0
0
k8
naik
0
0
1
0
4
0
1
0
0
k9
persen
0
1
0
0
6
3
0
3
1
0
0
0
0
0
0
0
2
0
100
100
104
100
96
91
97
90
90
k10
23
peringkat Total dokumen pada kategori
Perhitungan Likelihood (lanjutan) Kata Kunci saham tbk mega top ihsg sektor indeks naik persen peringkat saham
24
P(kata kunci | kategori) log2(P) 0,03125 -1,50515 0,01041 -1,98227 0 0 0 0 0,02083 -1,68124 -1,50515 0,03125 0,02083 -1,68124 0,04167 -1,38021 0,0625 -1,20411 0 0 0,03125 -1,50515 Nilai Likelihood
P* log2(P) -0,0470359 -0,0206487 0 0 -0,0350259 -0,0470359 -0,0350259 -0,0575088 -0,0752575 0 -0,0470359 0,317538551
Perhitungan Threshold L = likelihood seluruh kategori yang ada li = likelihood untuk kategori i
Likelihood-Mean Likelihood1 - Mean Likelihood2 – Mean Likelihood3 – Mean Likelihood4 – Mean Likelihood5 – Mean Likelihood6 – Mean Likelihood7 – Mean Likelihood8 – Mean Likelihood9 - Mean
25
(Likelihood – Mean)2
-0,068489938 -0,028489938 -0,029700835 -0,068489938 0,249048614 -0,046776132 0,023420427 -0,048007755 0,017485493
0,004690872 0,000811677 0,00088214 0,004690872 0,062025212 0,002188007 0,000548516 0,002304745 0,000305742
Mean Sum |L| Sum / |L| Standard Deviasi Threshold
0,068489938 0,078447781 9 0,00871642 0,09336177 0,161851708
Algoritma Identifikasi Topik 1.
Transformasikan kata kunci dokumen dan topik ke dalam vectorspace model yang sama Topik Artikel
2.
Kurs 5 Valuta 2
rumus: ti = topik ke-i A = artikel
26
Dollar 10 Kurs 3
Saham 3 Dollar 7
Kurs 5 Kurs 3
Dollar 10 Dollar 7
Saham 3 Saham 0
Valuta 0 Valuta 2
3.
Hitung nilai NewTSim menggunakan rumus:
4.
Bandingkan CosSim topik awal dengan kedua threshold: (i) CosSim(tc,A) > 0.1 AND CosSim(tc,A) > NewTSim(tc,A) (ii) NumTopics > 10 CosSim(tc,A) AND > (2 × StdDev(AllTopicSims) +Mean(AllTopicSims))
5.
27
Bila topik awal memenuhi kedua threshold, maka topik awal ditetapkan. Bila topik awal memenuhi <= 1 threshold, masukkan topik baru.
Uji Coba Perangkat Lunak
28
Uji Coba Aplikasi Tujuan:
Pencarian parameter optimal: Jumlah Kata Kunci Nilai threshold topik Performa Parser (tambahan) Dokumen Testing:
29
Kategori Nasional Regional Internasional Metropolitan Bisnis dan Ekonomi Olahraga Sains dan Teknologi Edukasi Pariwisata Total
Jumlah Dokumen 10 11 11 10 11 11 11 10 10 95
Uji Coba Kata Kunci Jumlah kata kunci yang diambil : 5, 10, 15, 20 Diujikan pada dua kondisi: offline dan online
30
Uji Coba Kata Kunci (lanjutan) Hasil uji coba offline : Keyword = 5
Keyword = 10
Keyword = 15
Keyword = 20
Precision
Precision
Precision
Precision
Kategori
31
Bisnis & Ekonomi
0,667
0,571
0,933
0,929
Edukasi
0,588
0,467
0,600
0,733
Internasional
0,286
0,563
0,563
0,563
Metropolitan
0,214
0,154
0,231
0,231
Nasional
0,952
0,947
0,947
1,000
Olahraga
0,846
0,923
1,000
1,000
Pariwisata
1,000
0,933
0,933
1,000
Regional
1,000
1,000
1,000
1,000
Sains & Teknologi
0,818
1,000
0,909
1,000
Uji Coba Kata Kunci (lanjutan) Hasil uji coba offline : Keyword = 5
Keyword = 10
Keyword = 15
Keyword = 20
Recall
Recall
Recall
Recall
Bisnis & Ekonomi
0,667
0,727
0,737
0,765
Edukasi
0,909
0,875
0,900
0,917
Internasional
1,000
1,000
0,900
1,000
Metropolitan
0,429
0,400
0,500
0,600
Nasional
0,952
0,947
0,947
0,950
Olahraga
1,000
1,000
1,000
1,000
Pariwisata
0,400
0,389
0,452
0,467
Regional
0,348
0,390
0,390
0,390
Sains & Teknologi
0,643
0,733
0,769
0,786
Kategori
32
Uji Coba Kata Kunci (lanjutan) Hasil uji coba offline : Rata - Rata Akurasi A K U R A S I
94.50% 94.00% 93.50% 93.00% 92.50% 92.00% 91.50%
Rata - Rata Akurasi
91.00% 90.50% 90.00% 5
10
15
K ATA KUNCI YANG DIEKSTRAKSI
33
20
Uji Coba Kata Kunci (lanjutan) Hasil Uji Coba Online Rata - Rata Akurasi
A K U R A S I
94.00% 93.80% 93.60% 93.40% 93.20% 93.00% 92.80% 92.60% 92.40% 92.20% 92.00% 91.80%
Rata - Rata Akurasi
5
10
15
K ATA KUNCI YANG DIEKSTRAKSI
34
20
Uji Coba parameter threshold Pada identifikasi topik, parameter nilai ambang CosSim
ditentukan 0,1 Jumlah kta kunci yang diambil 20 Nilai threshold diuji coba pada nilai 0.1, 0.2, 0.3, dan 0.4
35
Hasil Uji Coba Identifikasi Topik Akurasi
A K U R A S I
98.00% 97.00% 96.00% 95.00%
Akurasi
94.00% 93.00% 92.00% 0.1
0.2
0.3
THRESHOLD
36
0.4
Uji Coba Parser Menemukan kesalahan – kesalahan pada parser Hasil uji coba:
Contoh Kasus Kesalahan Seharusnya > > — — Pembacaan karakter HTML 2.0 " ̎ ldquo; “ Dokumen tidak Dokumen hanya Dokumen terunduh terunduh sempurna terunduh hingga secara lengkap pertengahan berita hingga akhir berita Tipe Kesalahan
37
Evaluasi Performa aplikasi meningkat seiring bertambahnya kata kunci
38
yang diekstraksi Jumlah kata kunci yang dapat menghasilkan nilai akurasi optimal adalah 20 Akurasi tertinggi klasifikasi offline: 93,82% Akurasi tertinggi klasifikasi online: 93,84% Akurasi tertinggi identifikasi topik : 97,26% Parameter nilai threshold klasifikasi optimal adalah 0,3
Simpulan dan Saran
39
Kesimpulan Algoritma terbukti mampu melakukan klasifikasi
kategori dan identifikasi topik dokumen berita berbahasa Indonesia dengan akurasi 93,84% Performa algoritma berkaitan erat dengan jumlah kata kunci yang diambil pada saat ekstraksi kata kunci
40
Saran Riset lebih dalam untuk algoritma ekstraksi kata kunci Riset untuk mengurangi waktu running time Ground truth kategori sebaiknya saling lepas Riset lebih dalam untuk parser
41
Terima Kasih
42
