Model Capaian Maklumat Model Boolean Model Ruang Vektor Model Capaian Maklumat.

Model Capaian Maklumat

Model Boolean

Model Ruang Vektor



Model capaian maklumat merupakan kerangka formal yang menyokong semua fasa utama dalam proses capaian maklumat termasuk Perwakilan item (dokumen) Perwakilan kepada kehendak pengguna Padanan kehendak dan item Pangkatan capaian item

Kerangka formal yang telah dicadangkan termasuk Teori set, boolean algebra, linear algebra, probability, fuzzy set

theory, neural networks, Bayesian networks dan banyak lagi

Perbincangan akan meliputi Model Boolean, model ruang vektor dan latent semantic indexing

Model Umum

D : set perwakilan dokumen

Q : set perwakilan kehendak pengguna (kueri)

R : D x Q real numbers

fungsi yang akan menentukan bagi setiap dokumen dan kueri suatu

nombor tertentu (real number) bagi diwakili oleh suatu pangkatan

(berkaitan) dokumen berdasarkan kueri yang dimasukkan.

Model Boolean

Dokumen diwakilkan dalam bentuk satu set katakunci. kata kunci hanya dinyatakan sama ada ujud atau tiada di dalam sesuatu dokumen

Kueri : dinyatakan dalam ungkapan katakunci yang dihubungkan dengan and, or dan not , termasuk penggunaan kurungan untuk penilaian berdasarkan kepentingan.

Pangkatan : bagi setiap term indeks ki set dokumen Dki dimana ki ujud : Dki = {dj | Wi,j = 1}

Hasil capaian adalah set yang berkaitan dan yang selebihnya tidak berkaitan

Operator Boolean

Q1 AND Q2 Documents that are in BOTH sets: Q1 and Q2

Q1 OR Q2 Documents that are in at least in one set: Q1 or Q2

NOT Q1 All documents except the one in set Q1

Q1 \ Q2 Logical “minus” all documents from Q1 except those that belong to Q2 Used also as “binary NOT” (Q1 NOT Q2)

Q1 XOR Q2 Exclusive OR - documents that belong to exactly one set: Q1 or Q2, but

not both In other words (Q1 OR Q2) \ (Q1 AND Q2)

Contoh :

Dapatkan semua dokumen mengandungi “information” dan “retrieval”

Dapatkan semua dokumen mengandungi “information” atau “retrieval” (atau kedua-duanya)

Dapatkan semua dokumen mengandungi “information” atau “retrieval”,

tetapi bukan kedua-duanya. Dapatkan semua dokumen mengandungi “information” dan “retrieval”

atau tidak mengandungi kedua-dua “retrieval” dan “science”

Boolean Logic

A B

BABA

BABA

BAC

BAC

AC

AC

:Law sDeMorgan'

Boolean Logic

t33

t11 t22

D11D22

D33

D44D55

D66

D88D77

D99

D1010

D1111

m1

m2

m3m5

m4

m7m8

m6

m2 = t1 t2 t3

m1 = t1 t2 t3

m4 = t1 t2 t3

m3 = t1 t2 t3

m6 = t1 t2 t3

m5 = t1 t2 t3

m8 = t1 t2 t3

m7 = t1 t2 t3

Model Boolean : Kekuatan

Sehingga sekarang merupakan model capaian yang popular kerana

Mudah untuk difahamai untuk kueri yang mudah

Kawalan yang baik bagi set jawapan dengan menggunakan ungkapan boolean yang kompleks.

Penjanaan yang efisyen

Selagimana pengenalpastian dokumen berasaskan kepada term dititikberatkan.

Pengguna dengan hanya sedikit latihan dengan senang dapat menformulasikan kueri boolean yang mudah

Model boolean boleh ditingkatkan bagi membolehkan penjanaan pangkatan

Model Boolean : Masalah

Terlalu rigid : AND bermaksud SEMUA ; OR bermaksud SALAH SATU

Susah jika permintaan pengguna yang kompleks.

Susah untuk mengawal bilangan dokuman yang dicapai

Semua dokumen yang padan akan dipulangkan tanpa ada senarai keutamaan

Susah untuk pangkatkan output

Semua dokumen yang padan, memenuhi kueri pada aras yang sama

Susah untuk menjanakan “relevent feedback” secara automatik

Jika dokumen yang dikenalpasti oleh pengguna adalah releven, bagaimana untuk menjana term baru bagi sesuatu kueri? AND? OR?

Capaian “Extended Boolean”

2),(

)()( 2

2

1

2

1,21

wwQ dSC

tt

• membenarkan proses pangkatan dilakukan

Bagi dokumen yang mengandungi term t1 dan t2 dengan pemberat w1 dan w2 maka similarity coefficient dikira

21),(

)1()1( 2

2

1

2

1,21

wwQ dSC

tt

Model Ruang Vektor

Setiap term dianggap sebagai term indeks dimana ianya tidak berkaitan diantara satu sama lain.

Setiap term indeks adalah mewakili term penting bagi sesuatu aplikasi.

Koleksi sains komputer

architecture

bus

computer

database

….

network

Term indeks dalam satu koleksi

Model Vektor

Dokumen : dokumen dengan set term indeks dengan pemberat. Pemberat dijanakan bagi menentukan kepentingan (keberkaitan) sesuatu term kepada dokumen

dj = (W1,j , W2,j, …… , Wi,j)

Kueri : kueri adalah term indeks dengan pemberat. Pemberat dijanakan bagi menentukan kepentingan (keberkaitan) sesuatu term kepada kehendak pengguna

q = (W1,j , W2,j, …… , Wi,j)

Setiap term, I, di dalam suatu dokumen atau kueri, j, diberi nilai (real) pemberat wij.

Koleksi bagi n dokumen boleh diwakilkan dalam bentuk model ruang vektor dengan matrik term-dokumen

Kemasukkan matrik bergantung kepada pemberat term dalam suatu dokumen; kosong bermaksud term tidak significance dalam dokumen atau tidak ujud di dalam dokumen tersebut.

Model Ruang Vektor

T1 T2 …. Tt

D1 w11 w21 … wt1

D2 w12 w22 … wt2

: : : : : : : :Dn w1n w2n … wtn

Perwakilan Grafik

Example:

D1 = 2T1 + 3T2 + 5T3

D2 = 3T1 + 7T2 + T3

Q = 0T1 + 0T2 + 2T3

T3

T1

T2

D1 = 2T1+ 3T2 + 5T3

D2 = 3T1 + 7T2 + T3

Q = 0T1 + 0T2 + 2T3

7

32

5

• Adakah D1 atau D2 lebih sama dgn Q?

• Bagaimana untuk mengukur darjah kesamaan? Jarak ? Sudut?

Model Ruang Vektor

Perkara yang penting di dalam permodelan ruang vektor ialah

menentukan pemberat bagi dokumen dan pemberat bagi kueri Pengiraan persamaan antara dokumen dan kueri

Model Ruang Vektor : Penentuan Pemberat

• Penyelesaian mudah : kepentingan sesuatu term berkait dengan kekerapan keujudan term tersebut.

• Jika term A dinyatakan lebih banyak/kerap dari term B, maka dokumen itu lebih menceritakan tentang A berbanding B.

• katakan freqi,j adalah kekerapan keujudan term ki dalam suatu dokumen dj, maka

Wi,j = freqi,j

• Masalah : penyelesaian mudah ini tidak normal jika perbandingan berdasarkan panjang suatu dokumen

• Satu laman dokumen yang menyebut 10 kali mengenai A berbanding 100 laman dokumen yang menyebut 20 kali mengenai A

• Penyelesaian :

• Bahagi setiap bilangan kekerapan (freq) dengan panjang dokumen

• Bahagi setiap bilangan kekerapan dengan bil. Kekerapan yang maksima bagi setiap item dalam dokumen


Masalah : term yang ujud di dalam banyak dokumen tidak semestinya menggambarkan ianya berkaitan dengan dokumen tersebut

Term komputer di dalam perpustakaan kejuruteraan

Penyelesaian : pemberat menggabungkan dua nilai pengukuran1. Pemberat bagi kekerapan term dalam sesbuah dokumen

2. Pemberat disongsangkan bagi memberi penumpuan kepada keujudan term di dalam keseluruhan koleksi dokumen yang ada. Ia menunjukkan term yang jarang muncul dalam keseluruhan dokumen adalah lebih bermakna

3. Digabungkan :

jijiji freqfreqf ,,, max/

ii nnidf /log 2

ijiji idffw ,,

tf x idf

)/log(* kikik nNtfw

log

Tcontain that in documents ofnumber the

collection in the documents ofnumber total

in T termoffrequency document inverse

document in T termoffrequency

document in term

nNidf

Cn

CN

Cidf

Dtf

DkT

kk

kk

kk

ikik

ik

Inverse Document Frequency

IDF provides high values for rare words and low values for common words

41

10000log

698.220

10000log

301.05000

10000log

010000

10000log


Jika koleksi mengandungi 10000 dokumen dan term A ujud sebanyak 20

kali pada dokumen tertentu dan maksima suatu term yang ujud pada

dokumen ialah 50. Term A ujud 2000 kali pada keseluruhan koleksi

dokumen maka

fi,j = freqi,j / max{ freqk,j} = 20/50 = 0.4

idfi = log2(n/ni) = log2 (10000/2000) = log2(5) = 2.32

wi,j = fi,j . idfi = 0.4 * 2.32 = 0.93


Pemberat kueri dicadangkan seperti berikut

iqkk

qiqi

n

n

freq

freqw 2

,

,, log

max

5.05.0

iqi idff ,5.05.0

• freqi,j merupakan kekerapan term ki dalam teks kueri q yang diminta

• Kueri dianggap seperti dokumen lain di dalam koleksi.

Model Ruang Vektor : pengukuran kesamaan (similarity)

• Pengukuran kesamaan merupa fungsi dijanakan bagi mendapatkan darjah kesamaan diantara sepasang vektor.

• Memandangkan kueri dan dokuemn dalam bentuk vektor maka pengukuran kesamaan boleh mendapatkan kesamaan di antara dua dokumen, dua kueri atau satu dokumen dan satu kueri.

• Terdapat beberapa kaedah digunakan didalam mendapatkan pengukuran kesamaan. Diantaranya :

• Inner product

• Cosine

• Jaccard Coefficient.

Inner product : pengukuran kesamaan yang paling mudah

• Dokumen :

• Kueri :

• Pengukuran yang digunakan :

Contoh

• Dokumen dan kueri

• d1 = (3, 2, 5, 4)

• d2 = (6, 4, 10, 8)

• q = (2, 0, 4, 3)

Pengukuran kesamaan :

Sim(q, d1) = 6+0+20+12 = 38

Sim(q, d2) = 12+0+40+24=76

),.........,( ,,2,1 jtjj wwwdj ),....,( ,,2,1 qtqq wwwq

t

i

qijij wwqdsim1

,,),(


Inner Product

Binary: D = 1, 1, 1, 0, 1, 1, 0

Q = 1, 0 , 1, 0, 0, 1, 1

sim(D, Q) = 3

retri

eval

database

archite

cture

computer

text

managemen

t

informatio

n

Size of vector = size of vocabulary = 7 0 means corresponding term not

found in document or query

Weighted

D1 = 2T1 + 3T2 + 5T3 D2 = 3T1 + 7T2 + T3

Q = 0T1 + 0T2 + 2T3

sim(D1 , Q) = 2*0 + 3*0 + 5*2 = 10

sim(D2 , Q) = 3*0 + 7*0 + 1*2 = 2


Inner Product

Cosine : pernormalan pengukuran kesamaan inner product

• Dokumen :

• Kueri :

• Pengukuran cosine yang digunakan :

),.........,( ,,2,1 jtjj wwwdj ),....,( ,,2,1 qtqq wwwq

t

i

t

i

t

ii

qiji

qiji

ww

wwqdsim

1

22

1

1

)()(

),(

,,

,,


Cosine


Cosine

Pengukuran cosine Contoh :• Dokumen dan kueri

d1=(3, 2, 5, 4)

d2=(6, 4, 10, 8)q = (2, 0, 4, 3)

• Vektor

|d1| =7.35

|d2| =14.70|q | = 5.38

• Kesamaan

• sim(q,d1) = (6+0+20+12) / (7.35 5.38) = 0.96

• sim(q,d2) = (12+0+40+24) / (14.70 5.38) = 0.96

• Cosine mengukur berdasarkan sudut antara dua vektor

• Semua nilai di antara 0 – 1

• Pendekatan cosine ialah, 1, menunjukkan dua vektor tersebut mewakilkan konsep yang sama. 0, menunjukan keduanya tidak mewakili konsep yang sama


Cosine

Pengukuran cosine Contoh :• Dokumen dan kueri

d1=(6, 4, 0, 8)

d2=(0, 0, 5, 0)q = (3, 2, 0, 4)

• Vektor

|d1| =10.77

|d2| = 5.00|q | = 5.385

• Kesamaan

• sim(q,d1) = (18+8+0+32) / (10.77 5.385) = 1.00

• sim(q,d2) = (0+0+0+0) / (5.00 5.385) = 0

Vector Space with Term Weights and Cosine Matching

1.0

0.8

0.6

0.4

0.2

0.80.60.40.20 1.0

D2

D1

Q

1

2

Term B

Term A

Di=(di1,wdi1;di2, wdi2;…;dit, wdit)Q =(qi1,wqi1;qi2, wqi2;…;qit, wqit)

t

j

t

j dq

t

j dq

i

ijj

ijj

ww

wwDQsim

1 1

22

1

)()(),(

Q = (0.4,0.8)D1=(0.8,0.3)D2=(0.2,0.7)

98.042.0

64.0

])7.0()2.0[(])8.0()4.0[(

)7.08.0()2.04.0()2,(

2222

DQsim

74.058.0

56.),( 1 DQsim

D1 = 2T1 + 3T2 + 5T3 Sim(D1 , Q) = 10 / (38+4-10) = 10/32 = 0.31D2 = 3T1 + 7T2 + T3 Sim(D2 , Q) = 2 / (59+4-2) = 2/61 = 0.04

Q = 0T1 + 0T2 + 2T3

t

i

t

iqiji

t

iqiji

t

iqiji

i

WWWW

WWqdsim

1 1,,

1,

2

,

2

1,,

)(

)(),(

Jaccard Coefficient:


Jaccard Coefficient

Dokumen Ruang Vektor dan Kueri Boolean

docs t1 t2 t3 RSV=Q.DiD1 1 0 1 4D2 1 0 0 1D3 0 1 1 5D4 1 0 0 1D5 1 1 1 6D6 1 1 0 3D7 0 1 0 2D8 0 1 0 2D9 0 0 1 3

D10 0 1 1 5D11 1 0 1 3Q 1 2 3

q1 q2 q3

D1

D2

D3

D4

D5

D6

D7

D8

D9

D10

D11

t2

t3

t1

Model Capaian Maklumat Model Boolean Model Ruang Vektor Model Capaian Maklumat.

Documents

Transcript of Model Capaian Maklumat Model Boolean Model Ruang Vektor Model Capaian Maklumat.