BAB 2 LANDASAN TEORI
Bab ini membahas tentang teori penunjang dan penelitian sebelumnya yang berhubungan dengan rekomendasi tag serta metode TF-IDF dan Collaborative tagging. 2.1 Rekomendasi Tag Rekomendasi tag mengacu pada proses pemberian rekomendasi tag secara otomatis yang berguna dan informatif untuk sebuah objek yang muncul berdasarkan informasi historisnya. Objek yang akan ditandai dapat berupa foto, video atau dokumen. Secara umum, dokumen yang di-tag biasanya berhubungan dengan satu sama lain atau memiliki banyak koneksi tag. Pengguna juga dapat memberikan tag pada dokumennya dengan berbagai persepsi (Song et al, 2008).
Gambar 2.1 Representasi Grafik Triplet (u, d, t) (Song et al, 2008) Pemberian tag pada dokumen d dilakukan oleh pengguna u dengan tag t dapat direpresentasikan dengan menggunakan triplet (u, d, t). Bila dilihat dari representasi grafiknya, setiap node adalah salah satu elemen dalam triplet dan tiap-tiap ujung dari node menjadi derajat atau bobot dari koneksinya. Baik pengguna dan dokumen sangat terhubung ke tag, sedangkan hubungan antara tag sendiri tidak bisa diamati secara langsung. Merekomendasikan tag yang relevan dengan pengguna baru atau dokumen
7
baru hanya bisa dilakukan secara tidak langsung dari perspektif pengguna atau sudut pandang dokumen (Song et al, 2008). Rekomendasi tag dapat dilakukan secara manual atau menggunakan autotag, yaitu pemberian tag secara otomatis dengan menggunakan suatu metode atau konsep pembelajaran tertentu seperti metode statistik dan text mining. Sistem rekomendasi tag secara otomatis memberikan kemudahan dalam memberikan rekomendasi tag terhadap informasi yang akan dipublikasikan terutama jika informasi tersebut memiliki ukuran yang besar atau cakupan yang luas. Selain itu, sistem rekomendasi tag secara otomatis juga akan menghemat penggunaan waktu dalam pemberian tag. Diharapkan rekomendasi yang diberikan dapat membantu pengguna dalam mengambil keputusan pemberian tag pada objek yang akan dipublikasikan sehingga nantinya dapat memudahkan dalam peroses filterasi objek tersebut ataupun objek lain yang memiliki kesamaan dengan objek tersebut. Dari segi perilaku pengguna, sistem tag dapat diklasifikasikan menjadi 3, yaitu self-tagging, permission-based dan free-for-all. Pada self-tagging, pengguna hanya menandai konten yang mereka ciptakan untuk pengambilan pribadi di masa depan, contohnya seperti situs facebook (http://www.facebook.com/) dan YouTube (http://www.youtube.com/). Permission-based
menetapkan berbagai tingkat izin
untuk pemberian tag, contohnya seperti situs Flickr (http://www.flickr.com/). Kedua bentuk penandaan tersebut digolongkan sebagai ‘narrow
folksonomies’ atau
folksonomi sempit dan tidak mendukung atau tidak termasuk ke dalam collaborative tagging. Free-for-all memungkinkan pengguna untuk menandai setiap item dan merupakan sistem collaborative tagging, contohnya seperti situs Yahoo! MyWeb (http://myweb.yahoo.com/). Free-to-all tagging juga dikenal sebagai ‘broad folksonomy’ atau folksonomi luas (Ji et al, 2007). 2.2 Text Mining Text mining (penambangan teks) bisa secara luas didefinisikan sebagai proses pengetahuan intensif dimana pengguna berinteraksi dengan koleksi dokumen dari waktu ke waktu dengan menggunakan seperangkat alat analisis. Dalam kaitannya dengan data mining, text mining berusaha untuk mengekstrak informasi yang berguna dari sumber data melalui identifikasi dan eksplorasi dari pola-pola yang menarik. Namun dalam text mining, sumber-sumber data adalah koleksi dokumen. Dan pola-
8
pola menarik tersebut tidak ditemukan diantara catatan database yang sudah diformalisasi melainkan dalam data tekstual yang tidak terstruktur di dalam koleksi dokumen-dokumen tersebut (Feldman et al, 2007). Sama sepertihalnya data mining, text mining adalah salah satu bagian lain dari Knowledge Discovery. Text Mining sering juga disebut dengan Text Data Mining (TDM) atau Knowledge Discovery in Textual Database (KDT). Metode ini digunakan untuk menggali informasi dari data-data dalam bentuk teks seperti buku, makalah, paper, dan lain sebagainya. Secara umum text mining memiliki definisi ‘menambang’ data yang berupa teks dimana sumber data biasanya didapatkan dari dokumen, dan tujuannya adalah mencari kata-kata yang dapat mewakili isi dari dokumen sehingga dapat dilakukan analisa keterhubungan antar dokumen (Anggaradana, 2013). Hal yang membedakan data mining dengan text mining adalah proses analisis terhadap suatu datanya. Data Mining atau Knowledge Discovery in Database (KDD) adalah proses untuk menemukan pengetahuan dari sejumlah besar data yang disimpan baik di dalam databases, data warehouses atau tempat penyimpanan informasi lainnya. Sedangkan untuk text mining sering disebut dengan Keyword-Based Association Analysis. Keyword-Based Association Analysis merupakan sebuah analisa yang mengumpulkan keywords atau terms (istilah) yang sering muncul secara bersamaan dan kemudian menemukan hubungan asosiasi dan korelasi diantara keywords atau terms itu (Kurniawan et al, 2009). Secara garis besar dalam melakukan implementasi text mining terdiri dari dua tahap besar yaitu pre-processing dan processing (Anggaradana, 2013). 2.2.1 Pre-Processing Tahap pre-processing adalah tahap dimana aplikasi melakukan seleksi data yang akan diproses pada setiap dokumen. Setiap kata akan dipecah-pecah menjadi struktur bagian kecil yang nantinya akan mempunyai makna sempit. Ada beberapa hal yang perlu dilakukan pada tahap pre-processing ini, yaitu Tokenizing, Filtering,dan Stemming. a. Tokenizing Tokenizing atau parsing adalah sebuah proses yang dilakukan sesorang untuk menjadikan sebuah kalimat menjadi lebih bermakna atau berarti dengan cara
9
memecah kalimat tersebut menjadi kata-kata atau frase-frase. Untuk beberapa kasus, pada tahap ini tindakan yang dilakukan adalah to Lower Case, dengan mengubah semua karakter huruf menjadi huruf kecil. Kemudian, dilakukan tahap tokenizing yaitu merupakan proses penguraian abstrak yang semula berupa kalimatkalimat berisi kata-kata dan tanda pemisah antar kata seperti titik (.), koma (,), spasi dan tanda pemisah lain menjadi kumpulan kata-kata saja baik itu berupa kata penting maupun kata tidak penting (Anggaradana, 2013). b. Filtering atau Seleksi Fitur Tahap filtering adalah tahap mengambil kata-kata penting dari hasil token. Dimana dalam tahap ini bisa digunakakan algoritma stoplist (membuang kata yang kurang penting) atau wordlist (menyimpan kata penting). Dalam tahap ini penulis menggunakan algoritma stoplist. Stoplist / stopword adalah kata-kata yang tidak deskriptif yang dapat dibuang. Contoh stopwords adalah “yang”, “dan”, “di”, “dari” dan seterusnya. Proses ini akan menghasilkan daftar istilah beserta informasi tambahan seperti frekuensi dan posisi yang akan digunakan dalam proses selanjutnya (Anggaradana, 2013). c. Stemming Tahap stemming adalah tahap mencari root kata dari tiap kata hasil filtering. Pada tahap ini dilakukan proses pengembalian berbagai bentukan kata ke dalam suatu representasi yang sama. Atau dengan kata lain pada tahap ini dilakukan proses penghilangan prefiks dan sufiks dari query dan istilah-istilah yang dihasilkan dari proses filtering. Stemming dilakukan atas dasar asumsi bahwa kata-kata yang memiliki stem yang sama dianggap memiliki makna yang serupa sehingga pengguna tidak keberatan untuk memperoleh dokumen-dokumen yang di dalamnya terdapat kata-kata dengan stem yang sama dengan query-nya (Anggaradana, 2013). Pada intinya proses ini mempunyai dua tujuan, yaitu (1) dalam hal efisiensi, stemming mengurangi jumlah kata-kata unik dalam indeks sehingga mengurangi kebutuhan ruang penyimpanan dan mempercepat proses pencarian. (2) dalam hal keefektifan, stemming mengurangi recall dengan mengurangi bentuk-bentuk kata ke bentuk dasarnya atau stem-nya. Sehingga dokumen-dokumen yang menyertakan suatu kata dalam berbagai bentuknya memiliki kecenderungan yang sama untuk
10
ditemukembalikan. Hal tersebut tidak akan diperoleh jika tiap bentuk suatu kata disimpan secara terpisah dalam indeks. Beberapa algoritma yang telah dikembangkan untuk proses stemming diantaranya Algoritma Porter (Bahasa Indonesia dan Inggris) dan Algoritma Nazief & Adriani untuk teks berbahasa Indonesia (Nazief et al, 1996). Dalam hal ini, Penelitian yang dilakukan Agusta (2009) menunjukkan algoritma Nazief & Adriani memiliki tingkat akurasi yang lebih tinggi dalam proses stemming untuk bahasa Indonesia dibandingkan algoritma Porter. 2.2.2 Processing Tahap yang kedua adalah melakukan processing. Tahap ini merupakan tahap inti dimana setiap kata akan diolah dengan algoritma tertentu, yang dalam penelitian ini akan digunakan metode TF-IDF. Tahap ini sering disebut juga dengan Analizing. Dalam tahap processing, dokumen akan dianalisa oleh aplikasi. Secara umum terdapat dua jenis metode yaitu metode yang tidak melakukan perhitungan bobot kalimat dan yang melakukan perhitungan bobot kalimat. Metode yang tidak menghitung bobot kalimat hanya mengambil beberapa kalimat awal dan akhir. Metode-metode yang menghitung bobot kalimat menggunakan bobot term (kata maupun pasangan kata) dari setiap term yang terdapat dalam kalimat tersebut (Anggaradana, 2013). Dalam penelitian ini digunakan metode yang menghitung bobot (term), dimana bobot term diperoleh dengan melakukan perhitungan terhadap Term Frequency dan Inverse Document Frequency dari term tersebut yaitu TF-IDF. Hasil perhitungan dari TF-IDF akan menghasilkan beberapa rekomendasi tag yang berasal dari dalam artikel tersebut. Selanjutnya digunakan teknik Collaborative tagging untuk mencari rekomendasi tag dari objek yang sudah dipublikasi sebelumnya. 2.3 Algoritma Nazief & Adriani Algoritma Nazief & Adriani adalah algoritma yang dikembangkan oleh Bobby Nazief dan Mirna Adriani. Algoritma ini dapat dimanfatkan untuk stemming bahasa Indonesia. Adapun flow chart algoritma Nazief & Adriani dapat dilihat pada gambar 2.2.
11
Gambar 2.2 Flow Chart Algoritma Nazief & Adriani (Nazief et al, 1996) Proses stemming pada teks berbahasa Indonesia berbeda dengan stemming pada teks berbahasa Inggris. Pada teks berbahasa Inggris, proses yang diperlukan hanya proses menghilangkan sufiks. Sedangkan pada teks berbahasa Indonesia, selain sufiks, prefiks, dan konfiks juga dihilangkan (Nazief et al, 1996). Untuk mengoptimalkan pemotongan sufiks, prefiks, dan konfiks pada kata digunakan tabel kombinasi kata awalan dan akhiran yang tidak diijinkan dan dapat dilihat pada tabel 2.1.
12
Tabel 2.1 Tabel kombinasi awalan akhiran yang tidak diijinkan (Adriani, et al. 2007) Awalan
Akhiran yang tidak diijinkan
be-
-i
di-
-an
ke-
-i, -kan
me-
-an
se-
-i, -kan
Adapun pemotongan kata dasar dibuat berdasarkan aturan peluruhan kata dasar seperti terlihat pada tabel 2.2. Tabel 2.2 Tabel aturan peluruhan kata dasar (Adriani, et al. 2007) Aturan
Awalan
Peluruhan
1
berV…
Ber-V.. | be-rV…
2
belajar
bel-ajar
3
berC1erC2
be-C1erC2.. dimana C1 !={‘r’ | ‘l’}
4
terV…
ter-V.. | te-rV…
5
terCer…
ter-Cer.. dimana C!==’r’
6
teC1erC2
te-C1erC2… dimana C1!=’r’
7
me{l|r|w|y}V…
me-{l|r|w|y}V…
8
mem{b|f|v}…
mem-{b|f|v}…
9
mempe…
mem-pe…
10
mem{rV|V}…
me-m{rV|V}…|me-p{rV|V}…
11
men{c|d|j|z}…
men-{c|d|j|z}…
12
menV…
me-nV…|me-tV…
13
meng{g|h|q|k }…
meng-{g|h|q|k}…
14
mengV…
meng-V…|meng-kV…
15
mengeC
menge-C
16
menyV…
me-ny.. | meny-sV…
17
mempV…
mem-pV…
18
pe{w|y}V…
pe-{w|y}V…
19
perV…
per-V…|pe-rV…
20
pem{b|f|v}…
pem-{b|f|v}…
21
pem{rV|V}…
pe-m{rV|V}…|pe-p{rV|V}
22
pen{c|d|j|z}…
pen-{c|d|j|z}…
23
penV…
pe-nV … | pe-tV …
13
Tabel 2.2 Tabel aturan peluruhan kata dasar (Adriani, et al. 2007)(Lanjutan) Aturan
Awalan
Peluruhan
24
peng{g|h|q}
peng-{g|h|q}
25
pengV
peng-V | peng-kV
26
penyV
pe-nya|peny-sV
27
pelV
pe-lV…; kecuali untuk kata "pelajar"
28
PeCP
pe-CP…dimana C!={r|w|y|l|m|n} dan P!='er'
29
perCerV
per-CerV… dimana C!={r|w|y|l|m|n}
Untuk mengatasi keterbatasan pada algoritma di atas, maka ditambahkan aturanaturan berikut: 1. Aturan untuk reduplikasi a. Jika kedua kata yang dihubungan penghubung adalah kata yang sama maka root word adalah bentuk tunggalnya, contoh “anak-anak” root word-nya adalah “anak”. b. Kata lain misalnya “bolak-balik”, “berbalas-balasan” dan “seolah-olah”. Untuk mendapatkan root word-nya, kedua kata diartikan secara terpisah. Jika keduanya memiliki root word yang sama maka diubah menjadi bentuk tunggal, contoh: kata “berbalas-balasan”, “berbalas” dan “balasan” memiliki root word yang sama yaitu “balas”, maka root word “berbalas-balasan” adalah “balas”. Sebaliknnya, pada kata “bolak-balik”, “bolak” dan “balik” memiliki root word yang berbeda, maka root word-nya adalah “bolak-balik”. 2. Tambahan untuk awalan dan akhiran serta aturannya. a. Tipe awalan “mem-”, kata yang diawali dengan awalan “memp-” memiliki tipe awalan “mem-”. b. Tipe awalan “meng-”, kata yang diawali dengan awalan “mengk-” memiliki tipe awalan “meng-”. 2.4 Term Frequency-Invers Document Frequency (TF-IDF) TF-IDF (Term Frequency-Inverse Document Frequency) merupakan metode statistik numeric yang mencerminkan seberapa pentingnya sebuah kata dalam sebuah dokumen atau korpus (Rajaraman et al, 2011). Hal ini sering digunakan sebagai faktor bobot dalam pencarian informasi dan penambangan teks (text mining). Nilai TF-IDF meningkat secara proporsional berdasarkan jumlah atau banyaknya kata yang muncul
14
pada dokumen, tetapi diimbangi dengan frekuensi kata dalam korpus. Variasi dari skema pembobotan TF-IDF sering digunakan oleh mesin pencari sebagai alat utama dalam mencetak nilai (scoring) dan peringkat (ranking) sebuah relevansi dokumen yang diberikan user. TF-IDF pada dasarnya merupakan hasil dari perhitungan antara TF (Term Frequency) dan IDF (Inverse Document Frequency). Banyak cara untuk menentukan nilai yang tepat dari kedua statistik yang ada. Dalam kasus term frequency tf (t, d), cara yang paling sederhana adalah dengan menggunakan raw frequency di dalam dokumen, yaitu berapa kali term t muncul di dokumen d. Jika menyatakan raw frequency t sebagai f (t,d), maka skema tf yang sederhana adalah tf (t, d) = f (t,d). Kemungkinan lain meliputi (Manning, et al. 2008): - frekuensi Boolean : tf (t,d) = 1 jika t muncul di d dan 0 kebalikannya; - skala frekuensi logaritmik : tf (t,d) = log (f (t ,d) + 1); - penambahan frekuensi, untuk mencegah bias terhadap dokumen lagi, misalnya raw frequency dibagi dengan raw frequency maksimum dari setiap term di dalam dokumen. 𝑡𝑓 (𝑡, 𝑑) = 0,5 +
0,5 × 𝑓 (𝑡, 𝑑) 𝑚𝑎𝑥 {𝑓 (𝑤, 𝑑) ∶ 𝑤 ∈ 𝑑
(2.1)
IDF (Inverse Document Frequency) merupakan ukuran apakah term itu umum atau langka di semua dokumen. Hal ini diperoleh dengan membagi jumlah dokumen di dalam korpus dengan jumlah dokumen yang berisi term, dan kemudian mengambil logaritma dari hasil bagi tersebut. 𝑖𝑑𝑓 (𝑡, 𝐷) = log
|𝑁| |{𝑑 ∈𝐷 ∶𝑡 ∈𝑑|
(2.2)
dimana: -
|𝑁| : kardinalitas dari N, atau jumlah total dokumen di dalam korpus.
-
| { 𝑑 ∈ 𝐷 ∶ 𝑡 ∈ 𝑑 | : jumlah dokumen dimana term t muncul (misalnya 𝑡𝑓 (𝑡, 𝑑) ≠ 0). Jika term tidak ada di dalam korpus, hal ini akan mengacu kepada division-by-zero. Oleh karena itu, biasanya untuk menyesuaikannya rumus menjadi: 1 + |{𝑑 ∈ 𝐷: 𝑡 ∈ 𝑑}|
(2.3)
15
Secara matematis fungsi dasar log tidak lah penting dan merupakan faktor pengali terhadap hasil keseluruhan. Maka TF-IDF dapat dirumuskan menjadi: 𝑡𝑓𝑖𝑑𝑓 (𝑡, 𝑑, 𝐷) = 𝑡𝑓 (𝑡, 𝑑) × 𝑖𝑑𝑓 (𝑡, 𝐷)
(2.4)
2.5 Collaborative Tagging Collaborative tagging menawarkan alternatif rekomendasi tag dan filterasi tag yang telah banyak digunakan. Collaborative tagging digambarkan seperti berbagai pengetahuan antara objek satu dengan berbagai objek lainnya. Collaborative tagging memungkinkan pengguna untuk berbagi tag pada objek mereka dengan objek pengguna lain. Teknik ini juga memungkinkan pengguna untuk menandai objek mereka secara bebas dan berbagi konten, sehingga para pengguna dapat mengkategorikan informasi dengan bebas, dan mereka dapat menelusuri kategori informasi yang dimiliki oleh pengguna lain. Tag klasifikasi, dan konsep menghubungkan set tag antara server web/blog, telah menyebabkan munculnya klasifikasi folksonomi pada objek-objek di internet. Mereka cenderung menggunakan tag yang ada untuk dengan mudah membentuk koneksi antar objek dengan tag yang berkaitan (Lee, et al, 2008). Collaborative tangging memungkinkan rekomendasi tag untuk objek baru yang akan publikasikan dapat berasal dari objek itu sendiri dan atau dari objek yang mirip. Pada metode collaborative tagging, tag yang berasal dari objek tersebut (Obaru) akan dicocokkan dengan tag pada objek lainnya yang telah diterbitkan (Olama). Tingkat kemiripan tag pada Obaru dengan Olama harus ditetapkan terlebih dahulu. Jika tingkat kemiripan yang ditentukan telah melewati ambang batasnya, maka tag-tag pada Olama (selain tag yang sama antar Obaru dan Olama) akan diikutsertakan menjadi rekomendasi tag pada Obaru (tag recommendation = Obaru Olama). Semakin tinggi derajat tingkat kemiripan yang ditentukan, maka semakin akurat rekomendasi tag yang akan didapatkan dan berlaku sebaliknya. Pada penelitian ini, collaborative tag yang digunakan ialah menggunakan tag similarity yaitu pengukuran kesamaan dengan menghitung persentase kemiripan tag hasil ekstraksi dari arikel yang baru dengan tag-tag berita lainnya di database. Persentase kemiripan berita berdasarkan tag pada penelitian ini adalah 50%.
16
2.6 Penerapan TF-IDF dan Collaborative Tagging pada Rekomendasi Tag Secara umum, tahap-tahap dalam membentuk sistem rekomendasi tag pada penelitian ini mengggunakan metode text-mining dimana tahap stemming-nya menggunakan algoritma Algoritma Nazief & Adriani, tahap processing-nya menggunakan metode TF-IDF. Untuk meningkatkan kemampuan sistem dalam memberikan rekomendasi, digunakan Collaborative tagging agar rekomendasi tag dapat berasal dari berita lain yang pernah diterbitkan sebelumnya. Adapun
langkah-langkah
pada
sistem
rekomendasi
tag
yang
akan
dikembangkan adalah sebagai berikut: 1. Masukkan text berita yang akan dibuat rekomendasinya. 2. Lakukan tokenizing pada text yang telah dimasukkan sehingga setiap kalimat pada text menjadi satuan kata-kata atau frase-frase. Kemudian sistem akan merubah semua karakter huruf menjadi huruf kecil melalui proses toLowerCase. 3. Lakukan filtering pada kata-kata atau frase-frase yang telah ada dengan menggunakan metode stoplist (membuang kata-kata yang kurang penting seperti kata sambung, kata depan, dan lain sebagainya). 4. Lakukan stemming pada setiap kata (k) menggunakan Algoritma Nazief & Adriani untuk teks berbahasa Indonesia yang berfungsi menemukan kata dasar dari setiap kata masukan. Untuk k =1 hingga k=n dilakukan langkah berikut: 4.1 Samakan kata atau frase dengan kata-kata di dalam kamus dimana jika ditemukan maka diasumsikan kata tersebut adalah kata dasar atau root word, jika tidak maka tahap selanjutnya dilakukan. 4.2 Lakukan Infection suffixes (“-lah”, “-kah”, “-ku”, “-mu”, atau “-nya”) dibuang. Jika berupa particles (“-lah”, “-kah”, “-tah”, atau “-pun”) maka langkah ini diulangi untuk menghapus Passive Pronouns (“-ku”, “-mu”, atau “-nya”), jika ada. 4.3 Hapus Derivation Suffixes (“-i”, “-an” atau “-kan”). Jika kata ditemukan dikamus, maka diasumsikan kata tersebut adalah root word. Jika tidak maka dilanjutkan ke langkah 4.3.1. 4.3.1
Jika “-an” telah dihapus dan huruf terakhir dari kata tersebut adalah“k”, maka “-k” juga akan ikut dihapus. Jika kata tersebut ditemukan dalam kamus, maka diasumsikan kata tersebut adalah root word. Jika tidak, akan dilanjutkan ke langkah 3b.
17
4.3.2
Akhiran yang dihapus (“i”, “-an” atau “-kan”) dikambalikan, lanjut ke tahap 4.4.
4.4 Hapus derivation prefix (“di-”, “ke-”, “se-”, “te-”, “be-” dan “me-”). Jika pada langkah 3 ada suffix yang dihapus maka dilanjutkan ke langkah 4.4.1, jika tidak pergi ke langkah 4.4.2. 4.4.1
Periksa tabel kombinasi awalan-akhiran yang tidak diijinkan seperti pada tabel 2.1. Jika ditemukan, maka diasumsikan kata tersebut adalah root word, jika tidak lanjut ke langkah 4.4.2.
4.4.2
For i=1 to 3, tentukan tipe awalan kemudian hapus awalan dan lakukan perubahan kata dasar sesuai tabel 2.2. Jika root word belum ditemukan lakukan langkah 5, jika sudah maka diasumsikan kata tersebut adalah root word. Catatan: jika awalan kedua dan awalan pertama adalah sama maka kata tersebut adalah root word.
4.5 Lakukan recoding. 4.6 Jika semua langkah selesai tetapi masih tidak berhasil, maka kata awal diasumsikan sebagai root word. Jika root word merupakan kata reduplikasi seperti “anak-anak”, “bolak-balik”, atau “berbalas-balasan”, maka kata tersebut harus mengikti aturan reduplikasi. 4.7 k+1, ulangi proses stemming untuk kata berikutnya. 5. Setelah hasil stemming kata telah didapatkan, tentukan bobot tiap-tiap kata dengan menggunakan metode TF-IDF sebagai berikut: 5.1 Hitung TF yaitu frekuensi kemunculan kata term (t) pada text berita (d). 5.2 Hitung invers document frequency (idf) yaitu dengan persamaan berikut: idf = Log10(N/(1+df) )
(2.5)
dimana: N = merupakan jumlah seluruh berita yang ada pada tabel berita. df = jumlah kemunculan kata (term) terhadap daftar isi berita di database. 5.3 Hitung bobot (W) masing-masing dokumen dengan persamaan 2.6. Wt= tf * idf dengan : t = kata(term) ke –t tf = term freqency W = bobot kata(term) ke- t idf = inverse document f reqency
(2.6)
18
5.4 Lakukan proses pengurutan (sorting) nilai kumulatif dari W untuk setiap kata dan mengambil 6 kata dengan bobot terbesar akan dijadikan sebagai hasil rekomendasi tag. 6. Hasil rekomendasi tag dari proses TF-IDF akan dicari kemiripannya dengan berita lainnya yang telah diterbitkan dan disimpan pada Tabel Berita di database dengan langkah berikut: 6.1 Persentasi kemiripan berita dihitung dengan persamaan 2.7. Kpn = (%kemiripan * hslTfidf)/100
(2.7)
Dimana: Kpn
= Jumlah kemiripan tag,
%kemiripan
= Persentase kemiripan tag,
hslTfidf
= Jumlah rekomendasi tag hasil TF-IDF (hasil Langkah 5.4).
6.2 Untuk setiap berita yang telah di-upload pada kategori yang sama dan memiliki jumlah kemiripan tag Kpn maka tag pada berita lainnya akan ditambahkan ke dalam rekomendasi tag otomatis. 2.7 Teknik Rekomendasi Tag Terdahulu Penelitian mengenai rekomendasi tag telah banyak dilakukan dengan berbagai algoritma guna mendapatkan hasil rekomendasi yang lebih relevan dan efektif. Muflikah, Fadilah, dan Rido (2013) menggunakan Algoritma Latent Semantic Indexing untuk sistem rekomendasi tag pada dokumen blog. Adapun langkah-langkah rekomendasi tag dengan menggunakan Algoritma Latent Semantic Indexing yang mereka lakukan adalah sebagai berikut: 1. Parsing Dokumen Blog berformat .html ke .txt. 2. Proses Training Data meliputi pengelompokan tag dan pembentukan Graf term frequency (TF) dan first occurrence (FO). 3. Preprocessing dalam sistem ini meliputi tokenizing, filtering, perhitungan term frequency (TF) dan perhitungan first occurrence (FO). Stemming tidak diperlukan karena sifat dari tag yang bebas dari kaidah tata bahasa. Perhitungan TF dan FO digunakan untuk pembobotan kata. FO adalah menyatakan jarak posisi kemunculan kata pertama pada dokumen. Hal ini didasarkan pada asumsi bahwa kata-kata penting yang menjadi topik isi dokumen berada pada beberapa paragraf pertama.
19
4. Tahap ekstraksi TI merupakan proses untuk mendapatkan sekumpulan kata kunci TI sebanyak jumlah input TI dari user. TI yang diambil adalah sebanyak m kata dengan bobot score terbesar. Semakin tinggi nilai TF dan semakin rendah nilai FO maka semakin besar kemungkinan kata tersebut merupakan kata kunci. 5. Teknik dekomposisi matriks dengan Singular Value Decomposition (SVD). SVD berkaitan erat dengan singular value atau nilai singular dari sebuah matriks yang merupakan salah satu karakteristik matriks. 6. Ekstraksi tag (Tag-Out) menggunakan algoritma Latent Semantic Indexing (LSI) dengan langkah kerja sebagai berikut:
Matriks berukuran 𝑚𝑥𝑠 dibentuk pada saat proses dokumen uji, setelah tahap ekstraksi TI. Sebanyak m jumlah TI dicari pasangan co-occurrence-nya di dalam graf. Maka didapatkan sebanyak s jumlah TO yang paling sedikit memiliki nilai co-occurrence 1 dengan paling sedikit 1 buah TI.
Selanjutnya dibentuk matriks 𝐴𝑚𝑥𝑠 yang berisikan bobot untuk m TI dan s TO yang memiliki co-occurrence pada bipartite graph (bigraf). Bigraf dibentuk saat training data.
Kemudian dilakukan reduksi matriks menjadi Uk, Vk, dan Sk. Baris-baris pada matriks Vk adalah kumpulan dari vektor eigen, maka tiap baris matriks Vk merupakan koordinat vektor masing-masing dokumen.
Tahap terakhir adalah mengukur tingkat kesamaan (similarity) antara vektor query dan masing-masing vektor dokumen menggunakan rumus perhitungan cosine similarity.
Setelah didapatkan hasil kedekatan masing-masing vektor kemudian dilakukan pengurutan secara descending hasil similarity antara query dan semua dokumen. Semakin besar nilai similarity artinya semakin dekat hubungan antara TO dengan m TI yang telah dipilih pada proses ekstraksi keyword.
7. Metode Evaluasi dengan ukuran evaluasi terhadap sistem rekomendasi tag adalah sebagai berikut:
Top-k accuracy. Prosentase dari dokumen yang rekomendasi tag-nya benar paling sedikit 1 dari sejumlah k tag teratas yang direkomedasikan (top-kth tag).
Exact-k Accuracy. Prosentase banyaknya dokumen yang hasil rekomendasi tag-nya benar sebanyak k dari sejumlah k tag teratas yang direkomendasikan (exact-kth tag)
20
Tag-recall. Prosentase hasil tag rekomendasi yang benar dari seluruh tag yang telah diberikan oleh user. Tag rekomendasi yang benar adalah tag yang sama antara tag yang dihasilkan oleh program dan tag yang dibuat oleh user.
Tag-precision. Prosentase hasil tag rekomendasi yang benar dari seluruh tag yang dihasilkan oleh algoritma program.
F-Measure merupakan gabungan antara precision dan recall. Pada tahun 2013, Purbasari, Cai, Lao, dan Al-Rawali melakukan penelitian
mengenai rekomendasi tag pada situs berbagi gambar di Flikr®. Langkah-langkah yang dilakukan oleh dalam penelitian mereka adalah sebagai berikut: 1.
Pengambilan tag dari Flickr®. Proses ini menggunakan API dari Flickr® dengan menggunakan implementasi Java sebagai bahasa pemrogramannya.
2.
Lakukan crawling pada semua gambar di Flickr yang memiliki tag tersebut. Untuk setiap gambar yang ditemukan, diambil seluruh tag-nya dan dilakukan crawling kembali untuk mengambil tag dari gambar lain yang mengandung tag tersebut. Sejumlah gambar yang tidak memiliki tag tidak disimpan dalam database.
3.
Lakukan iterasi selama stopping condition masih belum terpenuhi. Untuk menentukan stopping condition. Jika iterasi sudah melebihi maksimal iterasi maka pelatihan dihentikan. Bila nilai MAPE kurang dari atau sama dengan error tolerance maka pelatihan dihentikan.
4.
Kegiatan pra-proses pada tag, yang meliputi pengecekan dengan kamus untuk menyaring kata yang berbahasa Inggris saja, Pembuangan tag yang memiliki frekuensi dengan frekuensi tertinggi maupun terendah,
5.
Pembuatan matriks untuk memetakan tag dengan gambar.
6.
Proses clustering untuk memudahkan proses mining tag.
7.
Pencarian association rule pada setiap cluster untuk menghasilkan kombinasi tag yang sering muncul bersamaan. Algoritma Apriori mencari pasangan tag yang paling sering muncul bersamaan dengan menetapkan batasan confidence dan minimum support.
8.
Perekomendasian tag. Tag yang direkomendasikan didasarkan pada hasil association rule yang ditemukan pada langkah sebelumnya. Hanya rule yang kuat yang akan dipilih untuk menghasilkan rekomendasi tag dari query tag yang dimasukkan oleh pengguna.
21
9.
Pengambilan kembali gambar yang memiliki tag yang sama atau yang irekomendasikan. Selain menghasilkan output berupa tag hasil rekomendasi, sistem juga akan menampilkan sejumlah gambar dari Flickr yang memiliki tag yang direkomendasikan tersebut. Ini juga dilakukan melalui Flickr API dengan menggunakan metode SEARCH pada interface PhotoInterface. Adapun ringkasan beberapa penelitian terdahulu yang telah dilakukan untuk
memberikan rekomendasi tag pada beberapa masalah yang berbeda dapat dilihat pada tabel 2.3. Tabel 2.3 Penelitian Sebelumnya No
1.
Judul
TagAssist: Automatic tag Suggestion for Blog Posts
Pengarang
Tahun
Kelebihan
Kekurangan
Sanjay C. 2007 Sood dan Kristian J. Hammond
Nilai Precision Tag tidak memiliki mencapai 42.10% komponen user feedback
2.
Automatic tag Recommendation for the Web 2.0 Blogosphere Using Collaborative tagging and Hybrid ANN Semantic Structures
Sigma On, Kee Lee dan Andy Hon Wai Chun
2007
Tag-tag yang berhubungan dengan semantic content akan diberikan walaupun sudah pernah dipakai pada blog sebelumnya
Parameter dan algoritma yang digunakan masih dalam proses pengembangan
3.
A Content-Based Method to Enhance tag Recommendation
Yu-Ta Lu, Shoou-I Yu, Tsung-Chieh Chang, Jane Yung-jen Hsu
2009
Nilai Precision rekomendasi tag mencapai 59% tervalidasi oleh 5 fold cross validation
Tag yang direkomendasikan merupakan tag-tag yang tergolong populer dan kurang informatif dan spesifik
22
Tabel 2.3 Penelitian Sebelumnya (Lanjutan) No
Judul
Pengarang
Tahun
4.
Sistem Rekomendasi tag Pada Dokumen Blog Menggunakan Latent Semantic Indexing
Lailil Muflikhah, Nurul Fadilah, Achmad Ridok
2013
5.
Aplikasi Rekomendasi tag Pada Situs Berbagi Gambar Flickr®
Intan Yuniar 2013 Purbasari, Hongyun Cai, Angeli Diane Lao, Iman Mohamed Al-Rawahi
Kelebihan
Kekurangan
Rekomendasi tag yang n/a diberikan sebanyak 5 buah tag. Metode LSI digunakan untuk mencari hubungan latent antara Tag-In (TI) dan Tag-Out (TO) dalam setiap dokumen. Hasil terbaik FMeasure dicapai pada saat TI=2, yaitu 0.5. Teknik yang digunakan adalah Asossiation Rule Mining dan menggunakan API dari Flickr® untuk crawling semua gambar di Flickr® yang memiliki tag yang sesuai dengan tag yang diinput. Dapat memperoses data dengan jumlah data yang besar (sekitar 8000 data) dan jumlah kluster data yang besar.
Aplikasi rekomendasi tag masih terbatas pada topik “animal” saja. Efisiensi proses Mining cukup rendah. Proses pemberian rekomendasi tag berjalan lambat. Tidak ada perhitungan tingkat keakuratan rekomendasi tag yang dihasilkan.
