Text dan Web Mining - Budi Susanto TI UKDW 1 INDEXING. Budi Susanto

Text dan Web Mining - Budi Susanto TI UKDW

INDEXING Budi Susanto

1


2

Tujuan • Memaham pengertian dari information retrieval • Memahami pembentukan struktur inverted index • Memahami tentang kebutuhan index terhadap adanya

query frase • Memahami kebutuhan index terhadap query wildcard


Buku Acuan • Manning, C. D., Raghavan, P., Chutze, H. (2008).

Introduction to Information Retrieval. Cammbridge University Press, New York, Chapter 1, 2, dan 3.

3


4

Definisi IR • Information Retrieval (IR) is finding material (usually

documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers). - Manning (2008) • IR dapat mencakup bentuk masalah data dan informasi selain

disebutkan pada definisi di atas. • Misalnya beberapa format dokumen memiliki suatu struktur header,

body, dan footer. • Sering disebut dengan semistructure data.


5

Contoh Masalah IR • Terdapat sekumpulan dokumen berita dari berbagai

macam kelompok berita. • Kemudian ingin ditemukan dokumen berita apa saja yang berisi kata • badai AND topan AND NOT tsunami.

• Solusi: • Cara paling sederhana adalah melakukan pemindaian secara linier terhadap seluruh dokumen. • Proses ini sering disebut sebagai grepping. • Apa masalahnya?


6

Contoh Masalah IR • Dengan kemampuan komputer saat ini, ada kebutuhan

yang lebih terhadap pencarian: • mampu memproses kumpulan dokumen sangat besar secara

cepat; • memungkinkan operasi-operasi pencocokan yang fleksibel; • Memungkinkan melakukan pemeringkatan terhadap hasil pencarian.

• Salah satu cara untuk menghindari pemindaian linier

adalah membuat sebuah index terhadap seluruh dokumen.


7

Contoh incidence matrix

Antony and Cleopatra

Julius Caesar

The Tempest

Hamlet

Othello

Macbeth

Antony

1

1

0

0

0

1

Brutus

1

1

0

1

0

0

Caesar

1

1

0

1

1

1

Calpurnia

0

1

0

0

0

0

Cleopatra

1

0

0

0

0

0

mercy

1

0

1

1

1

1

worser

1

0

1

1

1

0

1 if play contains word, 0 otherwise


8

Contoh pencarian • Sehingga untuk menemukan dokumen terhadap query: • Brutus AND Caesar AND NOT Calpurnia • Dilakukan operasi boolean:

• 110100 AND 110111 AND 101111 = 100100.


9

Model Pencarian Klasik Get rid of mice in a politically correct way

TASK

Misconception?

Info about removing mice without killing them

Info Need

Mistranslation? Verbal form

How do I trap mice alive? Misformulation? mouse trap

Query

SEARCH ENGINE

Query Refinement

Results

Corpus


10

Terminologi • Kebutuhan informasi • Topik dimana ingin diketahui lebih oleh pemakai

• Query • Sesuatu yang pemakai sampaikan kepada komputer dalam rangka

mencoba untuk mengkomunikasikan kebutuhan informasi.

• Dokumen Relevan • Dikatakan relevan ketika pemakai mempersepsikan bahwa

dokumen tersebut mengandung informasi yang berkaitan dengan kebutuhan informasi mereka.


11

Dasar Evaluasi IR • Untuk menilai efektifitas sebuah sistem IR (kualitas hasil

pencarian), pada umumnya digunakan: • Precision • Berapa bagian dari hasil kembalian adalah relevan dengan kebutuhan

informasi? • Recall • Berapa bagian dari dokumen relevan dalam koleksi yang dikembalikan

oleh sistem?


12

Dasar Inverted Index • Daripada menyimpan secara biner (slide 6) untuk semua

term (vocabulary – kumpulan term), sebaiknya cukup disimpan dokumen apa saja yang mengandung masingmasing term.

Brutus

1

Caesar

1

Calpurnia Dictionary

2

2 2 31

4

11 31 45 173 174

4

5

6

54 101 Postings

16 57 132


Struktur Data untuk Dictionary • Array. Contoh: • char[40] int Postings*; • dimana Postings berupa struct atau class

13


14

Struktur Data untuk Dictionary • Hashtables • Setiap term di-hash menjadi sebuah integer. • Contoh fungsi hash: /* Peter Weinberger's */ int hashpjw(char *s) { char *p; unsigned int h, g; h = 0; for(p=s; *p!='\0'; p++){ h = (h<<4) + *p; if (g = h&0xF0000000) { h ^= g>>24; h ^= g; } } return h % 211; } http://en.wikipedia.org/w/index.php?title=File:Hash_table_5_0_1_1_1_1_1_LL.svg&page=1


Struktur Data untuk Dictionary Binary Search Tree

a-hu

hy-m

a-m

Root

n-z

n-sh

si-z

15

15


Struktur Data untuk Dictionary • B+ Tree n-z

a-hu hy-m

16


Pembentukan Inverted Index Kompulan dokumen

Tokenisasi

Normalisasi

Indexer

Inverted index harus disimpan dalam struktur list yang dinamis.

Inverted index

17


Contoh Indexer Tokenisasi dan Normalisasi

Doc 1 I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me.

Doc 2 So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious

18


Contoh Indexer Sorting

• Diurutkan berdasar term • Kemudian diurutkan

berdasar docID

19


Contoh Indexer Dictionary dan Postings

• Beberapa term sama

dalam dokumen tunggal di gabungkan. • Dipisahkan ke dalam Dictionary dan Postings. • Informasi tambahan, seperti frekuensi kemunculan term, disimpan.

20


Contoh Query • Dicari: Brutus AND Calpurnia • Proses: 1. Temukan Brutus dalam dictionary. 2. Ambil postings yang terkait. 3. Temukan Calpurnia dalam dictionary. 4. Ambil postings yang terkait. 5. Lakukan operasi interseksi antara dua daftar postings. • Interseksi adalah memilih item dari dua list yang sama.

21


Algoritma Interseksi

22


Contoh Interseksi

23


Latihan #1 1. Gambarkan inverted index untuk

Doc 1

new home sales top forecasts

Doc 2

home sales rise in july

Doc 3

increase in home sales in july

Doc 4

july new home sales rise

24


25

Latihan #2 • Terdapat kumpulan dokumen berikut:

Doc 1 breakthrough drug for schizophrenia Doc 2 new schizophrenia drug Doc 3 new approach for treatment of schizophrenia Doc 4 new hopes for schizophrenia patients 1. Gambarkan incidence matrix untuk kumpulan dokumen tersebut 2. Gambarkan inverted index untuk kumpulan dokumen tersebut. 3. Apa hasil kembalian untuk query berikut: a. b.

schizophrenia AND drug for AND NOT(drug OR approach)


26

Ingest • Menurut Kowalski, G. (2010), proses awal dalam suatu

sistem information retrieval disebut sebagai ingest. • Ingest merupakan proses yang menerima item-item yang

akan disimpan dan diindex dalam sistem dan melakukan preprocessing. • Pull atau crawling. • Tokenisasi • Deteksi kemiripan dan atau duplikasi • Stemming dan atau normalisasi lain

• Ekstraksi entitas (information extraction) • Pemrosesan metadata


27

Query Frase • Saat ini sistem IR harus juga mampu menerima query

dalam bentuk frase. • Contoh: “Universitas Kristen Duta Wacana” atau “UKDW

Yogyakarta” • Sehingga jika ada dokumen berisi “Duta Wacana adalah satu-satunya

universtas kristen terbaik di Yogyakarta” tidak akan ditemukan. • Frase dalam query biasanya ditulis dalam tanda petik ganda (“).

• Dengan query frase, diperlukan struktur index yang

sedikit berbeda.


28

Biword Index • Sebuah pengindex yang akan membangun dictionary

berdasar setiap pasangan dua kata yang muncul dalam tiap dokumen. • Contoh: universitas kristen duta wacana, • Akan diindex membentuk dictionary: • universitas kristen • kristen duta • duta wacana


29

Biword Index • Sehingga penanganan query yang panjang, seperti: • universitas duta wacana yogyakarta

• Akan dibagi menjadi: • “universitas duta” AND “duta wacana” AND “wacana yogyakarta”

• Kelemahan: • Bisa memberikan false positif. • Tanpa melakukan pengujian terhadap seluruh dokumen, kita tidak

dapat memverifikasi apakah query tersebut memang mewakili frase yang sebenarnya.


30

Extended Biword • Memparsing teks dan melakukan POST. • Term-term akan dikenali sebagai Nouns (N) dan

artikel/preposisi (X). • Dengan demikian, maka setiap string berpola NX*N

merupakan bentukan dari dictionary. • Contoh: universitas di yogyakarta • Akan diparsing menjadi N X N, sehingga index yang dicari

adalah: • universitas yogyakarta


31

Positional Index • Dalam postings, simpan posisi setiap term dimana term

tersebut muncul:


Contoh Positional Index

32


Positional Intersect Algorithm

33


34

Wildcard Queries • Contoh wildcard query: • yogya* : menemukan semua dokumen yang berisi sembarang kata

berawalan yogya. • Dengan B+Tree dapat cukup dilakukan dengan mencari semua

node yang berada di bawah node yogya. • yogya ≤ w < yogyb

• Bagaimana dengan query: *arta ? • Perlu dipelihara B+ tree tambahan yang menyimpan backward dari

semua kata. • Bagaimana dengan query: yo*arta?


35

Permuterm Index • Menggunakan karakter khusus, misal $, untuk menandai

akhir sebuah term. • Contoh: ukdw akan tersimpan sebagai ukdw$.

• Dibangun sebuah permuterm index yang berisi berbagai

bentuk rotasi tiap term. • kdw$u, dw$uk, w$ukw

• Query wildcard • X lookup on X$ • X* lookup on $X* • *X lookup on X$* • *X* lookup on X* • X*Y lookup on Y$X*


36

K-gram index • Menghasilkan enumerasi semua k-grams (deretan k-

karakter) dari tiap kata yang muncul. • Contoh enumerasi dari kalimat “ukdw yogyakarta” dengan 3-gram adalah: • $uk, ukd, kdw, dw$, $yo, yog, ogy, gya, yak, aka, art, rta, ta$

• Setiap postings akan berisi semua term yang berisi k-

gram dari dictionary. $m

mace

madden

mo

among

amortize

on

along

among


37

k-gram index • Semua query yang dikenakan terhadap k-gram index

akan dilakukan proses enumerasi serupa dengan pembentukan index. • Contoh: yo*arta akan diubah menjadi • $yo AND art AND rta AND ta$


38

Spelling Correction • Terdapat dua prinsip dasar : 1. Pilih salah satu yang paling mendekati dari query yang salah ejaan. • Didasarkan pada dictionary index.

2.

Ketika terdapat dua atau lebih kemunculan term yang benar, maka dipilih yang paling umum digunakan.

• Bentuk pembetulan ejaan • Isolated-term • Pembetulan terhadap masing-masing kata

• Context-sensitive • Pembetulan berdasar kata-kata yang ada di sekitarnya.


39

Isolated-Term • Menggunakan dasar lexicon dimana pembetulan ejaan

berasal. • Standar lexicon • Misalnya Kamus bahasa

• Index lexicon

• Terdapat dua metode: • Edit distance • K-gram


40

Edit Distance (Levenshtein distance) • Diberikan dua buah string, S1 dan S2, pilih kata yang

memiliki jumlah operasi konversi paling kecil. • Jenis operasi yang dilakukan: • Insert, delete, replace


Contoh

41


42

K-gram • Enumerasikan semua n-gram dalam string query

sebagaimana terhadap lexicon. • Gunakan index n-gram untuk mengambil semua lexicon yang cocok dengan n-gram query. • Threshold dengan jumlah n-gram yang cocok.


Contoh tri-gram • Sebagai contoh term november • nov, ove, vem, emb, mbe, ber. • Query adalah december. • dec, ece, cem, emb, mbe, ber. • Terdapat 3 trigram yang overlap. • Bagaimana caranya agar overlap tersebut

dinormalisasikan menjadi sebuah nilai overlap?

43


Jaccard coefficient • X dan Y adalah himpunan n-gram. Maka JC adalah

X Y / X Y • Contoh:

• JC untuk q=bord dan term=boardroom • 2/(8+3-2)

44


TERIMA KASIH Budi Susanto

45

Text dan Web Mining - Budi Susanto TI UKDW 1 INDEXING. Budi Susanto

Recommend Documents