13. Budi Susanto (v1.01)

4/2/13

Text dan Web Mining - Budi Susanto TI UKDW

1


2

INDEXING Budi Susanto (v1.01)

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

1

4/2/13


3

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

Introduction to Information Retrieval. Cammbridge University Press, New York, Chapter 1, 2, dan 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.

2

4/2/13


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.

3

4/2/13


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.

4

4/2/13


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?

Query

mouse trap

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.

5

4/2/13


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

16 57 132

54 101 Postings

6

4/2/13


13

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


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

7

4/2/13


15

Struktur Data untuk Dictionary Root

si-z

ot!

n-sh

kle

s! gen

sic

aar

n-z

!

hy-m

huy

dva

rk!

a-hu

a-m

zyg

Binary Search Tree

15


16

Struktur Data untuk Dictionary •  B+ Tree a-hu

n-z hy-m

8

4/2/13


17

Pembentukan Inverted Index Kompulan dokumen

Tokenisasi

Normalisasi

Inverted index harus disimpan dalam struktur list yang dinamis.

Indexer

Inverted index


18

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

9

4/2/13


19


20

Contoh Indexer Sorting

•  Diurutkan berdasar term •  Kemudian diurutkan

berdasar docID

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.

10

4/2/13


21

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.


22

Algoritma Interseksi

11

4/2/13


23


24

Contoh Interseksi

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

12

4/2/13


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: schizophrenia AND drug b.  for AND NOT(drug OR approach) a. 


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

13

4/2/13


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

14

4/2/13


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

15

4/2/13


31

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

tersebut muncul:


32

Contoh Positional Index

16

4/2/13


33

Positional Intersect Algorithm


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?

17

4/2/13


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

18

4/2/13


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.

3. 

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.

19

4/2/13


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

20

4/2/13

41


Contoh u n i v e r s i t a s

u 0 1 1 0 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10

n 2 1 0 1 2 3 4 5 6 7 8 9

v 3 2 1 1 1 2 3 4 5 6 7 8

e 4 3 2 2 2 1 2 3 4 5 6 7

r 5 4 3 3 3 2 1 2 3 4 5 6

s 6 5 4 4 4 3 2 1 2 3 4 5

i 7 6 5 4 5 4 3 2 1 2 3 4

t 8 7 6 5 6 5 4 3 2 1 2 3

a 9 8 7 6 7 6 5 4 3 2 1 2

42


Latihan j

o

g

j

a

k

a

t

a

y o g y a k a r t a

21

4/2/13


43

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.


44

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?

22

4/2/13


45

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)


46

TERIMA KASIH Budi Susanto

23

13. Budi Susanto (v1.01)

Recommend Documents