II
TINJAUAN PUSTAKA
Pada bab ini akan dibahas mengenai konsep knowledge management, klasifikasi dokumen, mencakup algoritma klasifikasi dan cluster dokumen secara umum, dan struktur dokumen. II.1 Knowledge Management Knowledge management (KM) menyediakan kerangka kerja untuk mengelola pengetahuan.
KM terdiri atas empat komponen utama [6],
yaitu: people;
knowledge, business process, dan technology. People adalah komponen utama yang menerapkan KM, knowledge adalah komponen dasar yang dikelola dalam KM; dapat berupa informasi dan konten seperti dokumen teks, gambar, file audio dan video, konten web, dan sebagainya; business process merupakan landasan kebijakan, arah pelaksanaan KM, dan sebagainya, dan technology merupakan pendukung dalam penerapan KM. Secara garis besar proses pada aplikasi KM terdiri dari: 1. Acquiring, adalah proses akuisisi knowledge ke dalam aplikasi KM. 2. Storing, adalah proses menyimpan hasil akuisisi knowledge, knowledge direpresentasikan sesuai dengan representasi penyimpanan dalam storage. 3. Appraising, adalah proses penaksiran terhadap knowledge yang sudah di simpan untuk menjawab pertanyaan atau query. 4. Extracting, adalah proses pengambilan (retrieval) knowledge, yang kemudian akan di ekstrak untuk digunakan oleh pengguna.
Proses extracting
membutuhkan hasil proses appraising untuk menentukan knowledge yang sesuai dengan request pengguna. 5. Sharing, adalah proses dimana knowledge yang tersimpan dalam aplikasi KM di-share secara luas. Jumlah knowledge yang disimpan dalam aplikasi KM akan terus bertambah seiring waktu. Pertambahan jumlah knowledge tersebut mendorong munculnya kebutuhan terhadap suatu mekanisme pengorganisasian knowledge yang baik, dan
II-1
yang dapat memfasilitasi pencarian dan pengambilan knowledge yang tepat dalam waktu yang cepat. Klasifikasi dokumen berkaitan erat dengan aktifitas pencarian dan pemanggilan kembali dokumen atau informasi. Gambar dibawah ini menjelaskan hubungan tersebut [7]:
Gambar II.1. Document Retrieval
Dalam proses retrieval dokumen, pengguna menentukan informasi yang dibutuhkan dan merepresentasikannya dalam bentuk query kepada sistem. Sistem kemudian menganalisis query dan mencari dokumen yang relevan dengan query pengguna pada tempat penyimpanan dokumen.
Pengklasifikasian dokumen
memungkinkan sistem menemukan dokumen dengan tingkat relevansi yang tinggi dalam waktu yang lebih cepat.
II.2 Pengelompokkan Dokumen Pengelompokkan dokumen adalah proses mengelompokkan dokumen ke dalam satu atau beberapa kategori menurut isi dokumen. Tujuan utama pengelompokkan dokumen adalah untuk menyederhanakan proses dan akses terhadap informasi dan pengetahuan, mengatasi masalah yang disebabkan oleh ledakan informasi (information overload), dan untuk mendukung fungsi manajemen pengetahuan seperti pemanggilan kembali (retrieval), organisasi, visualisasi, pengembangan, dan pertukaran pengetahuan [3].
Pengelompokkan dokumen digunakan pada
beberapa aplikasi seperti knowledge management, sistem temu-balik informasi (information retrieval), e-mail filtering, spam filtering, mail routing, pengontrolan
II-2
berita, otomatisasi indeks artikel, otomatisasi katalog web, identifikasi tipe dokumen, dan sebagainya. Secara umum proses pengelompokkan dokumen digambarkan sebagai berikut:
Gambar II.2. Gambaran Umum Proses Pengelompokkan Dokumen
Untuk menggunakan algoritma klasifikasi, dokumen teks yang menyimpan informasi dalam bahasa alami manusia harus dipetakan ke dalam bentuk yang dapat dimengerti oleh algoritma klasifikasi, yaitu bentuk numerik; dijelaskan pada bagian II.2.1. II.2.1 Pra-pengolahan Dokumen Proses konversi kata dalam dokumen menjadi bentuk numerik disebut document preprocessing (pra-pengolahan dokumen). Selanjutnya, dokumen dikelompokkan ke dalam kelas-kelas yang sesuai dengan isi dokumen. Pra-pengolahan dokumen terdiri dari proses feature extraction, feature selection, dan document representation; seperti digambarkan pada gambar II.3.
Gambar II.3. Pra-pengolahan Dokumen
II-3
1. Feature Extraction Feature extraction bertujuan untuk menghasilkan kamus yang berisi daftar term atau kata yang terdapat pada dokumen.
Fase ini dimulai dengan
menguraikan isi dokumen menjadi daftar kata atau kamus, disebut juga parsing. Parsing didefinisikan sebagai proses mengidentifikasi token dalam teks atau dokumen.
Selanjutnya dilakukan pengurangan dimensi kamus
menggunakan metode stop word removal dan word stemming. Stop word removal adalah proses menghilangkan ‗noise‘ atau term yang tidak mempunyai makna semantik seperti kata sandang, angka, dan preposisi dari kamus.
Setelah token teridentifikasi, sistem melakukan pengecekan term
dengan daftar stop words yang sudah ditentukan. Jika term terdapat dalam daftar stop words, maka term tersebut akan dihapus. Pengecekan stop words dapat dilakukan menggunakan metode binary search atau algoritma hashing. Stemming adalah proses menghilangkan imbuhan (awalan dan akhiran) pada term, untuk mencari kata dasar (stem). Dokumen teks yang dikaji pada tesis ini adalah dokumen berbahasa Inggris. Terdapat tiga kelompok algoritma stemming untuk teks berbahasa Inggris, yaitu rule-based stemmer, dictinarybased stemmer, dan co-occurence based stemmer. Rule-based stemmer adalah algoritma yang melakukan stemming berdasarkan aturan-aturan tertentu. Dictionary-based stemmer adalah algoritma yang melakukan stemming dengan menghilangkan imbuhan kata, kemudian mencocokkan kata dasar yang ditemukan dengan kata yang terdapat pada dictionary (daftar kata dasar). Kata dasar yang diterima hanyalah kata yang termasuk dalam daftar dictionary, sehingga akurasi hasil proses stemming sangat ditentukan oleh akurasi dan kualitas dictionary. Co-occurence based stemmer melakukan stemming pada kata yang sering muncul pada dokumen yang sama dalam koleksi dokumen. 2. Feature Selection Feature Selection bertujuan untuk mengeliminasi term-term yang kurang berarti atau memberikan sedikit informasi. Indikator yang digunakan sebagai pengukur adalah term frequency (TF), inverse document frequency (IDF), dan kombinasi TF dan IDF (TF x IDF). Pada TF term yang paling sering muncul
II-4
dalam dokumen adalah term yang mempunyai arti penting. IDF adalah jumlah dokumen dimana term ke-i muncul; menggunakan formula berikut:
N idf log df
(1)
dimana N adalah total dokumen dalam koleksi, dan df adalah jumlah atau frekuensi dokumen yang mengandung term ke-i. TFxIDF menggabungkan pengukuran TF dan IDF menjadi satu variabel. Kata-kata yang mempunyai nilai tertinggi adalah kata yang paling berarti.
N fd tf log df
(2)
dimana fd adalah bobot term ke-i pada dokumen d, tf adalah frekuensi kemunculan term ke-i pada dokumen d, N adalah total dokumen, dan df adalah jumlah atau frekuensi dokumen yang mengandung term ke-i Feature selection berguna untuk meningkatkan ke-efektifan klasifikasi dan kompleksitas komputasi. 3. Document Representation Document representation adalah langkah terakhir pada proses pra-pengolahan dokumen, yang direpresentasikan dalam bentuk fitur-fitur term yang dihasilkan dari langkah-langkah sebelumnya. Document representation untuk satu dokumen berbentuk vektor yang terdiri dari n elemen, dimana n adalah jumlah term. Untuk sekumpulan koleksi dokumen, document representation adalah matriks m x n, dimana m adalah adalah jumlah dokumen dan n adalah term.
Elemen matriks aij menyatakan frekuensi kemunculan term j pada
dokumen i, dan direpresentasikan dengan bilangan biner.
Nilai 1 dan 0
menyatakan term tertentu muncul atau tidak muncul pada dokumen. Hasil dari pra-pengolahan dokumen adalah daftar pasangan term dan frekuensi kemunculan term dalam dokumen, yang selanjutnya akan digunakan untuk mengklasifikasi dokumen.
II-5
Pengelompokkan dokumen dapat dilakukan dengan dua pendekatan yaitu supervised learning atau klasifikasi dan unsupervised learning atau clustering. II.2.2 Klasifikasi Dokumen Klasifikasi dokumen mengelompokkan dokumen ke dalam kategori-kategori yang bersifat tetap (fixed) dan sudah ditentukan (predefined).
Metode klasifikasi
dokumen bersifat supervised learning, pengelompokkan dokumen diawali dengan proses pembelajaran dokumen yang dilakukan oleh supervisor untuk menentukan kategori dokumen.
Dua pendekatan utama yang digunakan dalam klasifikasi
dokumen, yaitu pendekatan berbasis aturan (rule-based approach) dan pembelajaran mesin (machine learning).
Pada pendekatan berbasis aturan
klasifikasi dilakukan secara manual, dimulai dengan pengelompokkan dokumen ke dalam kategori, dan menentukan aturan-aturan yang mendefinisikan kategori. Kelebihan pendekatan berbasis aturan adalah nilai relevansi dokumen tinggi terhadap query. Sedangkan kelemahannya adalah dibutuhkan tenaga kerja yang banyak, biaya yang mahal, dan waktu yang lama untuk mengelompokkan dokumen dalam jumlah banyak.
Pada metode pembelajaran mesin aturan
klasifikasi dokumen dibuat secara otomatis menggunakan informasi dari label teks yang sudah dikelompokkan terlebih dulu.
Metode ini dapat mengatasi
masalah jumlah dokumen yang banyak. Kekurangan metode ini adalah aturanaturan yang dihasilkan tidak seakurat aturan yang dibuat supervisor. Klasifikasi data, dalam tesis ini data adalah dokumen, terbagi menjadi dua langkah atau subproses, yaitu learning dan classification. Proses klasifikasi dapat dilihat pada gambar II.4. Pada subproses learning dikembangkan sebuah model yang menjelaskan konsep kelas. Setiap dokumen diasumsikan menjadi anggota pada satu kelas (predefined class), ditentukan oleh atribut label kelas (class label attribute) yang telah didefinisikan sebelumnya. Dokumen pelatihan dianalisis menggunakan algoritma klasifikasi untuk membangun model atau classifier, dalam bentuk aturan-aturan klasifikasi.
II-6
Gambar II.4. Proses Klasifikasi Dokumen
Pada subproses classification, model atau classifier yang dihasilkan pada subproses learning diuji menggunakan dokumen penguji, untuk mengestimasi akurasi aturan-aturan klasifikasi.
Akurasi sebuah model adalah persentasi
dokumen penguji yang diklasifikasikan dengan benar oleh model tersebut. Jika hasil estimasi akurasi dapat diterima atau memenuhi threshold tertentu, maka model dapat digunakan sebagai model siap pakai untuk mengklasifikasi dokumen baru yang belum memiliki label kelas. Kriteria yang digunakan untuk mengevaluasi algoritma klasifikasi adalah sebagai berikut [11]: 1. Predicitive accuracy. Algoritma klasifikasi harus mampu memprediksi label class dari data baru. 2. Speed.
Berkaitan dengan kompleksitas komputasi atau waktu untuk
membentuk dan menggunakan model atau classifier. 3. Robustness. Algoritma klasifikasi harus mampu memberikan prediksi yang tepat dan mengelompokkan data ke dalam kategori yang tepat.
II-7
4. Scalability.
Algoritma klasifikasi mampu menangani data dalam jumlah
banyak. 5. Interpretability. Berkaitan dengan tingkat pemahaman yang disediakan oleh model atau classifier. Algoritma-algoritma dasar metode kategorisasi dokumen adalah decision tree, decision rules, k-Nearest Neighbor, Naive Bayes, neural network, regressionbased, centroid-based, dan Support Vector Machine. 1. Decision Rules Decision rules mengelompokkan dokumen ke dalam kategori-kategori menurut aturan yang sudah ditetapkan. Setiap kategori mempunyai sekumpulan aturan yang menjelaskan profil kategori. Setiap aturan tunggal terdiri dari nama kategori dan daftar kata atau kamus.
Kumpulan aturan
merupakan gabungan aturan-aturan tunggal menggunakan operator logika ―OR‖.
Tidak semua aturan dalam kumpulan aturan digunakan untuk
mengelompokkan dokumen.
Untuk menyederhanakan kumpulan aturan
digunakan heuristic, tanpa mempengaruhi proses pengelompokkan. Kelebihan algoritma decision rule adalah setiap kategori mempunyai kamus lokal, sehingga memungkinkan untuk membedakan arti dari kata-kata yang homonim.
Kekurangan algoritma decision rule adalah aturan-aturan dari
semua kategori dapat dipakai dalam proses pengelompokkan dokumen sehingga menyulitkan untuk mengelompokkan dokumen secara eksplisit pada satu kategori. 2. Decision Tree Algoritma decision tree mengelompokkan dokumen ke dalam struktur berbentuk pohon dimana simpul menyatakan pertanyaan dan leaf menyatakan kategori dokumen.
Pada setiap simpul terdapat atribut-atribut yang akan
dibandingkan dengan dokumen, dan setiap cabang yang diturunkan dari simpul tersebut mewakili salah satu nilai atribut.
Sebuah dokumen
dikelompokkan mulai dari simpul akar, menguji dokumen terhadap atribut dari
II-8
simpul tersebut, kemudian turun pada cabang yang cocok dengan nilai atribut. Proses ini diulang hingga mencapai kategori yang tepat. Kelebihan algoritma decision tree adalah struktur pohon mudah dimengerti dan diinterpretasikan, dan dokumen dikelompokkan berdasarkan struktur logika.
Kekurangan algoritma ini adalah waktu yang lama untuk
mengelompokkan secara manual, kesalahan klasifikasi pada level yang lebih tinggi mempengaruhi level dibawahnya, dan kemungkinan terjadi overfit tinggi.
Overfit adalah kondisi dimana terdapat lebih dari satu pohon
klasifikasi yang mungkin terbentuk. Overfit terjadi jika terdapat alternatif pohon lain yang dapat mengelompokkan dokumen dengan lebih baik. Dalam menggunakan algoritma decision tree juga perlu ditentukan maksimum kedalaman pohon, atau minimum jumlah simpul yang akan diobservasi untuk menghindari pembentukan pohon yang besar 3. k-Nearest Neighbor (k-NN) Algoritma k-nearest neighbor mengelompokkan dokumen-dokumen yang ―berdekatan‖ dikelompokkan ke dalam satu kelas. dokumen ditentukan dengan jarak Euclidean [11].
―Kedekatan‖ antara Algoritma ini dimulai
dengan mencari atau menentukan k nearest neighbors dari dokumen yang akan diklasifikasi, menghitung atau membandingkan kesamaan antara dokumen dengan neighbors (kelas atau dokumen-dokumen dalam satu kelas), kemudian mengelompokkan dokumen ke dalam kelas yang paling sama menggunakan aturan k-NN sebagai berikut [9]:
y x, c j
sim x , di y di , c j b j
d i kNN
(3)
dimana y d i , c j 0,1 adalah klasifikasi untuk dokumen d i pada kategori c j , sim x , di adalah kesamaan antara dokumen x dengan dokumen d i , dan
b j adalah threshold untuk pengambilan keputusan.
Algoritma k-NN sederhana dan mudah diimplementasikan, serta dapat memberikan hasil yang baik dengan pemilihan fitur dan perhitungan bobot yang tepat.
Dokumen yang memiliki lebih dari satu topik dapat
II-9
dikelompokkan pada dua kategori yang berbeda. Kekurangan algoritma k-NN adalah k-NN menggunakan semua fitur atau term untuk mengukur kesamaan dokumen dengan k-NN yang menghasilkan ukuran kesamaan yang buruk dan dapat menyebabkan kesalahan klasifikasi. 4. Naive Bayes (NB) Naïve Bayes menggunakan gabungan probabilitas term dan kategori untuk memperkirakan probabilitas kategori sebuah dokumen.
Metode NB
mengasumsikan bahwa probabilitas term dalam dokumen tidak bergantung pada probabilitas term yang lain (word independence), sehingga kemunculan term tidak mempengaruhi term lain. Ada beberapa varian NB, yang umum digunakan adalah Multivariative Bernoulli dan Multinomial model. Beberapa studi membuktikan performansi multinomial model lebih tinggi dibanding varian NB lain [8, 9].
Untuk mengelompokkan dokumen d, Multinomial
classifier memilih kelas c yang paling cocok dengan dokumen yang akan dikelompokkan. Estimasi probabilitas kelas p(c | d) dihitung dengan aturan Bayes [8]: pc | d
pc pd | c pd
(4)
Prior probability p(c) adalah frekuensi relatif dokumen pada kelas c. Conditional probability p(d | c) adalah probabilitas dokumen d untuk kelas c yang dihitung dari probabilitas kemunculan term terhadap semua term dalam dokumen d dengan rumus sebagai berikut: pd | c
pw | c f w, d f w, d !
d!
wd
wd
F(w,d) menyatakan frekuensi kemunculan term w dalam dokumen d,
(5) |d|
adalah total frekuensi semua term dalam dokumen, atau panjang dokumen, dan koefisien multinomial
d!
wd f w, d !
menyatakan jumlah semua urutan term
yang mungkin. Probabilitas term pada kelas p (w | c) menyatakan jumlah kemunculan term atau frekuensi term,
II-10
pw | c
1 f w, c v w'v f w' , c
(6)
dimana f(w,c) adalah frekuensi kemunculan term pada kelas c.
Untuk
menghindari nilai probabilitas 0 ditambahkan 1 sebagai kemunculan term ‗semu‘ pada daftar kata v. Naïve Bayes digunakan pada pengelompokkan teks atau dokumen karena performansi yang baik, ukuran klasifikasi kecil, dan kompleksitas kecepatan linier. Kelemahan naïve Bayes adalah metode ini hanya memproses vektor fitur biner dan mengabaikan informasi yang relevan. 5. Neural Networks (NNet) Pengelompokkan dokumen menggunakan algoritma neural network terdiri dari dua pendekatan, yaitu perceptron dan backpropagation.
Perceptron
terdiri atas lapisan input dan output. Perceptron menggunakan vektor bernilai ril sebagai input, menghitung kombinasi linier input, kemudian memberikan output 1 jika nilai hasil lebih besar dari threshold yang ditentukan dan -1 jika sebaliknya [10]. Algoritma backpropagation, disebut juga feed-forward-nets, digunakan untuk multi-lapisan, terdiri dari lapisan input, lapisan output, dan lapisan tersembunyi (hidden layer). Kelebihan algoritma neural networks adalah fleksibilitas tinggi, dapat menangani noisy atau data yang bersifat kontradiksi dengan baik, dapat memahami logika yang tidak jelas. Kelemahan algoritma neural network adalah biaya komputasi yang sangat tinggi, sulit dimengerti oleh orang awam. 6. Regression-based Klasifikasi menggunakan dua matriks, yaitu matriks fitur sebagai matriks input, disebut sebagai matriks A, dan matriks output B yang mengindikasikan kategori dari dokumen pada matriks A. Matriks B terdiri dari m baris dan c kolom, dimana m adalah dokumen pada matriks A; sehingga jumlah baris matriks A dan B adalah sama, dan c adalah jumlah kategori. Tujuan metode ini adalah mencari matriks F yang mentransformasikan matriks A ke matriks B', sedemikian hingga B'=B. Kelebihan algoritma regression-based adalah pra-pengolahan pembentukan term, stop word removal dan word stemming,
II-11
dapat dihindari tanpa mempengaruhi kualitas klasifikasi, dan dapat digunakan dengan mudah untuk satu kategori dan multi-kategori. 7. Centroid-based (CB) Algoritma centroid-based merepresentasikan dokumen dengan model ruang vektor (vector-space model).
Setiap dokumen adalah vektor d dalam
kumpulan term, disebut juga term-space, yang direpresentasikan oleh vektor term frequency (TF) sebagai [13]:
d tf tf1 , tf 2 ,..., tf n
(7)
dimana tfi adalah frekuensi istilah ke-i dalam dokumen. Skema pembobotan yang paling sering digunakan adalah inverse document frequency (IDF). Bobot vektor dokumen direpresentasikan dengan vektor tf-idf; persamaan 2. Panjang halaman dokumen yang berbeda akan mempengaruhi hasil perhitungan kesamaan antar dokumen maupun kesamaan dokumen dengan kelas, dimana semakin panjang sebuah dokumen maka nilai pembobotan akan semakin tinggi.
Untuk meminimalisasi pengaruh panjang dokumen yang
berbeda, panjang setiap vektor dinormalisasi menjadi 1. Algoritma CB diawali dengan menghitung vektor centroid untuk setiap kelas pada training documents.
Vektor centroid didefinisikan sebagai rata-rata
bobot terms pada himpunan dokumen S, sebagai berikut:
1 C S
d d S
(8)
Untuk mengelompokkan dokumen baru, dilakukan penghitungan kesamaan antara vektor dokumen , d tfidf , dengan setiap vektor centroid, menggunakan fungsi cosine sebagai berikut: d C d C cos(d , C ) C d C
(9)
Dokumen baru akan dikelompokkan pada vektor centroid yang paling sama, menggunakan aturan:
II-12
arg max (cos( x , Cj ))
(10)
j 1,...,k
Kelebihan algoritma CB adalah algoritma ini berjalan dengan baik (efektif), sederhana dan mudah diimplementasikan, kompleksitas komputasi pada fase learning linier terhadap jumlah dokumen, kompleksitas komputasi klasifikasi dokumen baru linier terhadap jumlah kelas [4, 11]. 8. Support Vector Machine (SVM) Algoritma SVM merepresentasikan dokumen sebagai vektor dan mencari batasan, disebut decision hyperplane, yang memisahkan dua kelompok vektor atau kelas. Kualitas decision hyperplane ditentukan oleh jarak antara dua hyperplane, disebut ‗margin‘, yang paralel dengan decision hyperplane dan menyentuh objek terdekat dari setiap kelas, disebut support vector. Decision hyperplane yang terbaik mempunyai margin terlebar atau maksimum, dan bersinggungan dengan semua objek terdekat dari setiap kelas.
SVM
digambarkan pada gambar II.5. Hyperplane untuk ruang vektor dua dimensi linier dinyatakan dengan [8]:
w.x b 0
(11)
dimana x adalah vektor dokumen yang akan diklasifikasi, vektor bobot w dan konstanta bias b adalah parameter training data. Untuk himpunan training data D, dinyatakan dengan D yi , xi dan y i 1 menyatakan klasifikasi untuk x (+1 diklasifikan pada kelas positif dan -1 diklasifikasikan pada kelas negatif), SVM mencari w dan b yang memenuhi syarat sebagai berikut:
w.xi b 1 untuk y i 1 w.xi b 1 untuk y i 1
(12)
Pada fase learning model dibangun menggunakan contoh positif dan negatif dari setiap kategori, kemudian menghitung batas antara kategori. Dokumen dikelompokkan dengan menghitung vektor dan menentukan partisi ruang dimana vektor berada.
II-13
Gambar II.5. Support Vector Machine [8]
Kelebihan SVM adalah hanya satu dot product pada dokumen baru yang harus dihitung sehingga pengelompokkan dokumen baru lebih cepat. Kelemahan SVM adalah sebuah dokumen dapat dikelompokkan pada beberapa kategori karena kesamaan dihitung per kategori.
Kelebihan metode klasifikasi dokumen adalah akurasi klasifikasi yang baik dan menghasilkan dokumen dengan tingkat relevansi yang tinggi dengan query pengguna. Sedangkan kekurangan klasifikasi dokumen adalah biaya dan waktu yang dibutuhkan untuk mengelompokkan dokumen secara manual, struktur kategori yang bersifat predefined dan statis tidak menyediakan mekanisme untuk melakukan perubahan struktur [4]. Perubahan struktur kategori dapat terjadi jika ada beberapa kategori yang perlu digabung, atau muncul kategori baru. II.2.2.1 Hierarchical Text Classification Algoritma-algoritma klasifikasi yang dibahas pada bagian II.2.2 melakukan pengklasifikasian dengan pendekatan flat classification. Pada pendekatan flat classification, kelas-kelas klasifikasi yang dihasilkan adalah kelas-kelas yang terpisah dan bersifat independen, yang tidak memiliki struktur yang menjelaskan hubungan antara kelas.
Pulijala & Gauch [14] menjelaskan pendekatan
hierarchical classification untuk mengklasifikasi dokumen.
Hierarchical
classification mengklasifikasi dokumen ke dalam kelas-kelas yang saling
II-14
terhubung dalam bentuk struktur hirarki.
Dengan pendekatan ini akurasi
klasifikasi semakin baik dan pencarian dokumen menjadi lebih efisien. Ada dua metode hierarchical classification, yaitu pendekatan big-bang dan topdown level-based. Pada pendekatan big-bang, classifier mengklasifikasi dokumen dengan satu langkah.
Pada top-down level-based, klasifikasi dilakukan pada
setiap level pohon. Dari root pohon dokumen dibandingkan dengan setiap kelas pada level pertama, kemudian dokumen dikelompokkan pada kelas level pertama yang paling cocok. Selanjutnya, dokumen dibandingkan dengan setiap sub-kelas dari kelas tersebut. Proses ini terus berlanjut hingga dokumen mencapai leaf atau kelas pada level terbawah.
Untuk membangun model classifier dapat
menggunakan algoritma-algoritma klasifikasi yang telah ada. II.2.2.2 Teknik Estimasi Akurasi Teknik-teknik dasar yang digunakan untuk mengestimasi akurasi model yang dihasilkan subproses learning adalah [11]: 1. Holdout Data atau dokumen dipartisi menjadi dua bagian, yaitu 70% dokumen dialokasikan sebagai training documents atau dokumen pelatihan dan 30% dokumen dialokasikan sebagai testing documents atau dokumen penguji. Dokumen pelatihan digunakan pada subproses learning, sedangkan dokumen penguji digunakan pada subproses klasifikasi. 2. k-fold Cross Validation Pada teknik ini, data atau dokumen dipartisi menjadi k subset atau fold, S1,S2,...,Sk, dengan ukuran yang sama.
Pelatihan dan pengujian model
merupakan proses yang iteratif, sebanyak k iterasi. Pada iterasi ke-i, subset Si berperan sebagai data penguji, dan subset yang lain menjadi data pelatihan. Untuk iterasi pertama, S1 menjadi data penguji dan S2, S3, ..., Sk menjadi data pelatihan. Akurasi diukur dari total jumlah klasifikasi yang tepat dari k iterasi, dibagi dengan total jumlah seluruh data.
II-15
II.2.3 Clustering Dokumen Clustering adalah proses mengelompokkan objek ke dalam kelas-kelas, disebut cluster, sehingga objek-objek pada satu cluster yang sama mempunyai tingkat kesamaan yang tinggi, tetapi berbeda dengan objek-objek pada cluster yang berbeda [11]. Clustering dokumen bersifat unsupervised learning, dokumen tidak dikategorikan oleh seorang supervisor. kesamaan antara dokumen.
Pengelompokkan dilakukan menurut
Kesamaan dihitung menggunakan hubungan dan
kesatuan antar fitur dalam dokumen, dimana fitur dapat berupa kata dan frase [4]. Proses clustering dokumen dapat dilihat pada gambar II.6.
Gambar II.6. Proses Clustering Dokumen
Algoritma cluster dokumen harus memenuhi syarat atau kriteria sebagai berikut [12]: 1. High dimensionality.
Algoritma clustering harus mampu menangani data
yang memiliki dimensi atau atribut yang banyak. 2. Scalability. Algoritma cluster dokumen harus mampu menangani dokumen dalam jumlah banyak dengan efisien. 3. Accuracy. Algoritma cluster dokumen yang baik mempunyai kesamaan intracluster yang tinggi dan kesamaan inter-cluser yang rendah. 4. Easy to browse with meaningful cluster description. Struktur cluster yang dihasilkan harus tepat, mempunyai deskripsi yang berarti, dan mendukung browsing interaktif. 5. Prior domain knowledge. Algoritma cluster yang baik tidak bergantung pada parameter input, misalnya jumlah cluster, karena akan mengurangi akurasi cluster. Secara garis besar teknik clustering dibagi menjadi dua kelompok, yaitu exclusive dan non-exclusive cluster. Non-exclusive cluster memungkinkan sebuah dokumen menjadi anggota lebih dari satu cluster. Algoritma non-exclusive cluster yang II-16
dikenal adalah fuzzy clustering. Pada exclusive cluster sebuah dokumen hanya menjadi anggota satu cluster. Exclusive cluster terdiri atas hierarchical clustering dan partitional clustering. 1. Hierarchical Clustering Hierarchical clustering membentuk rangkaian partisi bersarang (nested partition) berbentuk dendogram, yaitu diagram yang menyerupai struktur pohon.
Struktur hirarki dapat dibangun dengan metode agglomerative
(bottom-up) dan divisive (top-down). Pada metode agglomerative dokumendokumen dikelompokkan ke dalam cluster yang terpisah, kemudian dua cluster yang mempunyai tingkat kesamaan yang tinggi digabungkan menjadi satu cluster. Metode divisive diawali dengan menyatukan semua dokumen ke dalam satu cluster, kemudian cluster dibagi menjadi cluster-cluster yang lebih kecil secara berulang-ulang hingga memenuhi kondisi tertentu. Ada empat metode yang digunakan untuk mengukur kesamaan atau jarak antara dua cluster, yaitu: a) Single-Link atau minimum distance. Jarak antara dua cluster ditentukan oleh kesamaan dua dokumen terdekat pada cluster yang berbeda. b) Complete-Link atau maximum distance.
Jarak antara dua cluster
ditentukan oleh kesamaan dua dokumen terjauh pada cluster yang berbeda. c) Average-Link atau average distance. Jarak antara dua cluster ditentukan oleh jarak rata-rata semua pasangan dokumen pada dua cluster berbeda, disebut unweighted pair-group average (UPGMA), atau menghitung jarak antara dua cluster menggunakan rata-rata bobot cluster, disebut weighted pair-group average (WPGMA). d) Ward’s Method atau mean distance. Jarak antara dua cluster dievaluasi menggunakan pendekatan analisis varian; mean.
Keanggotaan cluster
dinilai dengan menghitung total rata-rata (mean) pangkat dua, atau sum of square.
II-17
2. Partitional Clustering Algoritma partitional clustering membentuk cluster-cluster secara iteratif, dimulai dengan memilih cluster-cluster awal secara acak, kemudian memperbaiki cluster-cluster awal ini dengan melakukan relokasi objek secara iteratif.
Partitional clustering membagi sekumpulan dokumen menjadi
beberapa cluster non-hirarki yang terpisah, menggunakan matriks vektor term untuk menentukan hubungan antar dokumen. Fitur atau term pada setiap dokumen dibandingkan dan dokumen-dokumen yang mempunyai pola yang serupa dikelompokkan pada satu cluster. Partitional clustering sesuai untuk dokumen dalam jumlah besar, karena tidak memerlukan komputasi yang kompleks untuk membentuk dendogram.
Kekurangan metode ini adalah
sulitnya menentukan jumlah cluster pada awal pembentukan cluster. 1) K-Means Algoritma k-Means merupakan metode clustering yang banyak digunakan, termasuk beberapa varian dari k-Means. K-Means mengelompokkan dokumen ke dalam k partisi, sehingga dalam satu cluster menyimpan dokumendokumen dengan kesamaan yang tinggi. Prosedur pengelompokkan dokumen dengan k-Means adalah sebagai berikut: 1.Memilih sejumlah k dokumen sebagai centroid atau cluster awal secara acak, menurut jumlah cluster yang ditentukan.
2.Mengelompokkan dokumen pada cluster yang paling sama
(dekat) berdasarkan jarak antara dokumen dengan centroid.
Untuk
menentukan cluster terdekat, dokumen dibandingkan dengan semua centroid. Jarak dokumen dengan centroid dihitung menggunakan Euclidean distance. 3.Menghitung nilai rata-rata baru pada setiap cluster, sebagai centroid baru, yaitu nilai rata-rata dokumen pada setiap cluster. 4.Ulangi langkah 2 dan 3 hingga centroid tidak berubah, stabil dan konstan. Keluaran algoritma k-means adalah sekumpulan k clusters yang memenuhi kriteria squared-error, yaitu cluster dengan minimal squared-error. Squarederror didefinisikan sebagai [11]: E i 1 p mi k
pCi
II-18
2
(13)
dimana E adalah total squared-error untuk semua dokumen dalam basis data, p adalah titik yang merepresentasikan dokumen tertentu, dan mi adalah nilai rata-rata cluster Ci. Kriteria squared-error menghasilkan sejumlah cluster yang padat dan terpisah satu dengan yang lain. Kelebihan algoritma k-means adalah k-means bersifat scalable dan efisien untuk memproses data dalam jumlah besar dengan kompleksitas komputasi linier. Kompleksitas komputasi k-means adalah O(nkt), dimana n adalah total jumlah dokumen, k adalah jumlah cluster, dan t adalah jumlah iterasi. 2) Single-Pass Algoritma single-pass dimulai dengan menentukan cluster-cluster kosong, kemudian mengambil sebuah dokumen secara acak atau menurut urutan yang sudah ditentukan. Dokumen yang diambil dianggap sebagai sebuah cluster baru dengan satu anggota. Cluster baru dibandingkan dengan cluster-cluster awal.
Jika relasi antara cluster baru dan cluster lainnya lebih besar dari
threshold yang ditentukan, maka cluster baru digabung dengan cluster terdekat, sebaliknya relasi lebih kecil dari threshold yang ditentukan, maka cluster baru ditambahkan pada kumpulan cluster. 3) Nearest Neighbor Algoritma nearest-neighbor serupa dengan metode hierarchical single-link, menggunakan jarak terdekat sebagai threshold untuk menentukan apakah dokumen-dokumen akan ditambahkan pada cluster yang sudah ada atau menciptakan cluster baru. 4) Expectation Maximization (EM) Algorithma
EM
mengelompokkan
dikembangkan dokumen
pada
dari
algoritma
cluster
dengan
K-Means,
yang
menghitung
bobot
probabilitas keanggotaan dokumen pada cluster [11]. 3. Fuzzy Clustering Fuzzy clustering adalah metode non-exclusive clustering yang menghasilkan sejumlah partisi dengan batasan yang tidak jelas, dimana setiap objek dapat menjadi anggota pada lebih dari satu cluster secara bersamaan, tapi memiliki II-19
level yang berbeda pada setiap cluster. Cluster dinyatakan sebagai sebuah prototipe cluster yang terdiri dari cluster pusat, yang menjelaskan domain cluster, dan informasi tentang ukuran dan bentuk cluster. Keanggotaan objek pada cluster dinyatakan oleh fungsi keanggotaan (membership function) yang menghitung vektor keanggotaan untuk setiap objek. Elemen ke-i dari vektor keanggotaan, disebut faktor keanggotaan fi, adalah sebuah objek menyatakan level keanggotaan objek pada cluster ke-i. Level keanggotaan sebuah objek pada cluster dihitung menurut jarak antara objek dan cluster pusat. Semakin dekat objek dengan cluster pusat, semakin tinggi level keanggotaannya pada cluster tersebut, yang berarti faktor keanggotaan tinggi.
Semakin tinggi faktor keanggotaan menyatakan
pengelompokkan objek pada cluster semakin tepat. Algoritma yang dikenal pada fuzzy clustering adalah Fuzzy C-Means. Fuzzy C-Means menentukan cluster pusat secara acak atau random. Jarak antara objek dan cluster pusat dihitung menggunakan metrik Euclidean. Algoritma Fuzzy C-Means cenderung mempartisi objek ke dalam cluster-cluster yang berbentuk hyper-spherical dengan jumlah objek yang sama.
Untuk
mendapatkan partisi yang paling tepat proses pengelompokkan dilakukan berulang-ulang agar dapat meningkatkan objektifitas fungsi.
Pengulangan
proses pengelompokkan dilakukan dengan menginisialisasi cluster pusat yang berbeda, kemudian membandingkan hasil fungsi untuk memilih partisi terbaik. Kelebihan metode cluster dokumen adalah otomatisasi pengelompokkan dokumen; clustering tidak memerlukan predefined class label untuk dokumen; clustering dapat digunakan pada semua jenis koleksi teks, dapat menciptakan cluster dokumen baru, memperjelas query yang ambigu, dan mengeliminasi dokumen-dokumen yang tidak relevan. Sedangkan kelemahan cluster dokumen adalah dalam hal prediktabilitas, penamaan cluster, dan pengelompokkan yang tidak tepat; nama cluster tidak sesuai dengan isi dokumen dalam cluster [4].
II-20
II.2.3.1 Distance Measure Dissimilarity atau similarity antara dokumen dihitung berdasarkan jarak antara setiap pasangan dokumen, disebut distance measure. Distance measure yang umum digunakan adalah [11]: 1. Euclidean distance, didefinisikan sebagai:
d (i, j )
xi1 xj1 xi 2 xj 2 ... xin xjn 2
2
2
(14)
Dimana i = (xi1, xi2,...,xin) dan j = (xj1, xj2,..., xjn) adalah dua dokumen berdimensi n.
2. Manhattan distance, didefinisikan sebagai: d (i, j ) xi1 xj1 xi 2 xj 2 ... xin xjn 2
2
2
(15)
3. Minkowski distance, didefinisikan sebagai:
x d (i, j )
i1
xj1 xi 2 xj 2 ... xin xjn q
q
q
q
(16)
II.3 Struktur Dokumen Penelitian berkaitan dengan mengubah dokumen elektronik dari bentuk tidak terstruktur ke dalam bentuk terstuktur dimotivasi oleh beberapa hal seperti kebutuhan untuk menggunakan kembali (reuse) dokumen, keseragaman bentuk dokumen pada basis data informasi, dan memfasilitasi proses pencarian atau pemanggilan kembali dokumen. Struktur sebuah dokumen sangat membantu manusia dalam menentukan sumber, topik, atau karakteristik lain dari dokumen. Dibandingkan dengan dokumen tidak terstruktur (flat document), dokumen terstruktur memungkinkan sistem atau pengguna untuk mengakses elemen atau bagian dari dokumen, sehingga dapat memperoleh informasi yang lebih tepat dan lebih berharga dari dokumen tersebut. Sebuah dokumen mempunyai dua struktur, yaitu struktur fisik geometris atau layout, dan struktur logik. Perbedaan struktur layout dan logik dijelaskan oleh [15]. Struktur layout tidak memberikan informasi yang dapat membantu pembaca
II-21
dokumen untuk memahami arti dokumen. Struktur layout bervariasi antara satu dokumen dengan dokumen lain. Dari sudut pandang stuktur layout dokumen dibentuk oleh halaman-halaman, sebuah halaman terdiri dari beberapa blok teks, sebuah blok teks terdiri dari beberapa baris, dan sebuah baris terdiri dari beberapa kata. Struktur logik berkaitan dengan isi dokumen yang memberikan informasi kepada pembaca dokumen tentang arti dokumen. Struktur logik bersifat tetap. Dari sudut pandang struktur logik dokumen terdiri atas unit-unit logik seperti babbab dari buku, paragraf dari bab, heading, judul, tabel, dan sebagainya. Representasi struktur layout dokumen dapat dilihat pada gambar II.7, sedangkan struktur logik dokumen pada gambar II.8; kedua gambar tersebut disadur dari [16]. Document
Block
Page
...
...
Block
Line
...
Page
Line
Word ... Word Gambar II.7. Struktur Layout Dokumen
II-22
Document
Logical Unit
Logical Unit
Title, Author, Abstract
Table
...
Logical Unit List
Table Cell
List Entity
Line
...
...
...
Table Cell
List Entity
Line
Block
Line
Block
Word
Line
...
...
...
Line
Word
Line
Word
Word
...
...
Word
Word Gambar II.8. Struktur Logik Dokumen
Struktur logik dokumen direpresentasikan dalam bentuk struktur pohon atau berbentuk hirarki [17]. Bentuk struktur seperti ini merupakan representasi umum struktur dokumen XML. Setiap node pada struktur pohon dokumen menyatakan bagian dari dokumen, yang menyimpan dua informasi yaitu label, disebut juga structural node, dan konten. Label adalah informasi yang merepresentasikan bentuk struktural dokumen, sedangkan konten adalah isi node. Pada dokumen XML label didefinisikan pada DTD dokumen. Contoh stuktur pohon sebuah dokumen pada gambar II.9 [17].
II-23
Title
This is the 'Title' of this document
Author
Author of the document This document is an example of semistructured document
Abstract
This is the first section
Document Section
Paragraph
This is the first paragraph
Paragraph
This is the second paragraph
This is the second section Section Paragraph
This is the third paragraph
Gambar II.9. Struktur Logik Dokumen dalam Bentuk Struktur Pohon
Pada gambar II.9, sebuah dokumen memiliki label sebagai berikut: tile, author, abstract, section, dan paragraph.
Konten node ‘title’ adalah teks yang
menyatakan title dokumen tersebut; konten node ‗paragraph‘ adalah teks paragraf, dan seterusnya. II.3.1 Klasifikasi Dokumen Semi-structured Dokumen terstruktur (struktur logik) memiliki representasi yang lebih kaya dibanding dokumen flat atau tidak terstruktur. Sebagian besar data atau informasi yang disimpan dalam basis data teks atau basis data dokumen adalah dokumen semi-structured. Dokumen semi-structured terdiri atas komponen dokumen yang terstruktur dan tidak terstruktur.
Komponen dokumen terstruktur adalah
komponen yang memiliki pasangan attribute-value; contoh, pada gambar II.9 title dan author termasuk komponen terstuktur. Komponen dokumen tidak terstruktur dapat berbentuk teks atau gambar; contoh, pada gambar II.9 isi abstract dan isi paragraf merupakan komponen tidak terstruktur. II-24
Klasifikasi dokumen terstruktur atau dokumen semi-structured dapat dilakukan dengan teknik modeling, yang terdiri atas dua pendekatan [17].
Pendekatan
pertama, menggunakan classifier teks tidak terstruktur yang berbeda, sebagai base classifier, untuk mengklasifikasi bagian-bagian dokumen yang berbeda. Selanjutnya hasil klasifikasi base classifier digabungkan untuk mengklasifikasi seluruh dokumen. Pendekatan kedua, membangun classifier baru yang disesuaikan untuk dokumen terstruktur, disebut generative model.
II-25
