Luận văn:Nghiên cứu, thử nghiệm và đánh giá các phương pháp xếp hạng kết quả tìm kiếm

Chia sẻ: Nhung Thi | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

86
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Những nhân tố tác động vào kết quả tìm kiếmNgoài nội dung được tối ưu hóa, Việc xếp hạng của những trang web của bạn cũng bị ảnh hưởng bởi những nhân tố từ bên ngoài. Những nhân tố bên ngoài là số lượng mối liên kết link đến một website, tuổi của một website và số lượng người đã click (nhấn) vào một kết quả tìm kiếm. Chỉ một ít cỗ máy tìm kiếm xem xét tuổi của một website (Mặc dù Google là một trong số chúng) Và thậm chí còn ít hơn những cỗ máy tìm kiếm đếm...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn:Nghiên cứu, thử nghiệm và đánh giá các phương pháp xếp hạng kết quả tìm kiếm

-1- -2- B GIÁO D C VÀ ĐÀO T O Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Đ I H C ĐÀ N NG NGÔ TH HI N TRANG Ngư i hư ng d n khoa h c: TS. Huỳnh Công Pháp NGHIÊN C U, TH NGHI M VÀ ĐÁNH GIÁ Ph n bi n 1: CÁC PHƯƠNG PHÁP X P H NG TS. Trương Ng c Châu K T QU TÌM KI M Ph n bi n 2: TS. Trương Công Tu n Chuyên ngành: Khoa h c máy tính Mã s : 60.48.01 Lu n văn s ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p Th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 04 tháng 03 năm 2012. TÓM T T LU N VĂN TH C SĨ K THU T * Có th tìm hi u lu n văn t i: - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng Đà N ng - Năm 2012 - Trung tâm H c li u, Đ i h c Đà N ng.
-3- -4- M Đ U • V m t th c nghi m: ñánh giá các phương pháp x p h ng và ch n l a th c nghi m phương pháp t t nh t. 1. Lý do ch n ñ tài 3. Đ i tư ng và ph m vi nghiên c u Hi n nay, Công ngh Thông tin ñư c ng d ng r ng rãi trong • Đ i tư ng nghiên c u là các phương pháp x p h ng tài li u. nhi u lĩnh v c c a ñ i s ng xã h i. D li u ñư c thu th p và lưu tr • Ph m vi nghiên c u là th c nghi m x p h ng k t qu tìm trong quá trình ng d ng công ngh thông tin ngày càng ñư c tích ki m ñơn ng . lu nhi u lên. Theo th ng kê ñ n tháng 4/2010 s lư ng máy ch hơn 4. Phương pháp nghiên c u 46 tri u máy, trên ñó cài ñ t hơn 240 tri u website [12]. Theo m t • Phương pháp phân tích: Thu th p và ñánh giá ñ liên quan tính toán khác, ñ n cu i năm 2009, ñã có 20 t trang Web ñã ñư c gi a câu truy v n và b d li u. Google ñánh ch m c [13]. • Phương pháp th c nghi m: Th c hi n vi c cài ñ t, th Tìm ki m thông tin là nhu c u thi t th c c a t t c m i ngư i. nghi m phương pháp x p h ng tài li u; Đánh giá k t qu ñ t ñư c Tuy nhiên, ngư i s d ng g p nhi u khó khăn khi ti p nh n k t qu theo b ng ñánh giá ñ liên quan ñã xây d ng. tr v . Đ h tr ngư i dùng, các máy tìm ki m th c hi n vi c x p 5. Ý nghĩa khoa h c và th c ti n c a ñ tài h ng (ranking) các tài li u ñ s p x p theo th t ưu tiên. Có nhi u Sau khi th c hi n nghiên c u và ñánh giá hi u qu các phương phương pháp ñưa ra ñ th c hi n vi c x p h ng tài li u nhưng chưa pháp x p h ng k t qu tr v làm cơ s cho vi c l a ch n mô hình có ñánh giá nào ñư c th c hi n nh m phân tích tính hi u qu c a các x p h ng phù h p trong vi c xây d ng m t h truy tìm thông tin. phương pháp này. V i lý do như v y, tôi ch n ñ tài “Nghiên c u, 6. C u trúc lu n văn th nghi m và ñánh giá các phương pháp x p h ng k t qu tìm ki m” N i dung chính c a lu n văn này ñư c chia thành ba chương: làm cơ s cho vi c ch n l a phương pháp x p h ng phù h p. Chương 1 – Cơ s lý thuy t 2. M c ñích nghiên c u Các khái ni m cơ b n trong tìm ki m thông tin. M c ñích c a ñ tài là tìm hi u, ñánh giá các phương pháp x p Các khái ni m v Ma tr n, giá tr riêng. h ng tài li u ñ ch n l a phương pháp x p h ng phù h p và sau ñó là Chương 2 – Các phương pháp x p h ng k t qu tìm ki m ti n hành th c nghi m phương pháp x p h ng ñã l a ch n. Đ hoàn N i dung chính là tìm hi u các phương pháp, mô thành m c ñích ñ ra c n nghiên c u các n i dung như sau: hình x p h ng k t qu tìm ki m. So sánh, ñánh giá các phương pháp • V m t lý thuy t: Tìm hi u ki n th c v tìm ki m thông tin x p h ng. (Information Retrieval), vai trò c a x p h ng (ranking) trong h Chương 3 – Cài ñ t th nghi m th ng tìm ki m thông tin, các phương pháp x p h ng tài li u; tiêu chí Mô t ki n trúc và cài ñ t th nghi m h tìm ki m ñánh giá k t qu x p h ng. thông tin theo mô hình ch m c ng nghĩa ng m LSI.
-5- -6- CHƯƠNG 1 trong ñó di là tài li u th i trong b sưu t p tài li u (document CƠ S LÝ THUY T collection), tj là thu t ng th j ch a trong tài li u. 1 th hi n thu t ng tj có ch a trong tài li u di. và 0 là ngư c l i. Các s 1 trong b ng 1.1.CÁC KHÁI NI M CƠ B N trên có th thay b ng s l n xu t hi n c a thu t ng trong tài li u. 1.1.1. Tài li u - Document Trong khi ñó, ch m c ngư c (inverted index), m i thu t ng Tài li u gi vai trò trung tâm và là s n ph m c a quá trình tìm s tương ng v i danh sách các tài li u ch a nó. ki m, ch a thông tin c n thi t. Vi c tìm ki m ñư c th c hi n trên b t1 d1 d3 d51 d151 d2011 sưu t p tài li u (document collection). 1.1.2. Thu t ng - Term t2 d2 d10 d61 M i tài li u ñư c bi u di n m t cách lô-gic như m t t p h p … các thu t ng (term). Các h th ng tìm ki m có các cách ti p c n tm d100 d1001 d3000 d3001 d5001 khác nhau. M t tài li u tương ng v i t p h p các t , hay c m t ch a trong nó. 1.1.4. Ma tr n t ch m c – Term - Document 1.1.3. L p ch m c cho tài li u – Index M t t p văn b n có n văn b n ñư c bi u di n b i m t ch m c L p ch m c cho tài li u phương pháp th c hi n quét m t l n ñư c vector hóa thành ma tr n A – ma tr n này ñư c g i là ma tr n trên các file văn b n và lưu l i danh sách các thu t ng (t , c m t ) t ch m c (term document). Trong ñó n văn b n trong t p văn b n có trong file ñó cũng như các thông tin ñi kèm v i m i thu t ng ñư c bi u di n thành n vector c t, m t ch m c ñư c bi u di n thành (term) (v trí, t n su t, ñ quan tr ng, …). Các thông tin này s ñư c m dòng. Ph n t dij c a ma tr n A chính là tr ng s c a t ch m c i t ch c theo m t c u trúc d li u riêng và ñư c g i là ch m c. Lúc xu t hi n trong văn b n j. Thông thư ng, trong m t t p văn b n s t này các thao tác tìm ki m s ñư c ti n hành d a trên ch m c thay vì ch m c l n hơn r t nhi u so v i văn b n m >> n. ñư c th c hi n tr c ti p trên file văn b n. 1.1.5. Tr ng s c a thu t ng - Term – weight Ch m c c a tài li u (index) tương ng v i t p h p các thu t D a vào s l n xu t hi n c a thu t ng c a tài li u (term ng ch a trong nó. Các tài li u ñư c bi u di n dư i d ng: count), tính ra t n su t xu t hi n c a thu t ng (term frequency), v i ký hi u là tft. t1 t2 t3 t4 tm Giá tr dft (document frequency) tương ng v i s lư ng tài d1 1 1 0 0 1 li u ch a thu t ng t. … 0 0 0 1 0 dn 1 0 0 0 0
-7- -8- T n s ngh ch ñ o tài li u (inverse document frequency), ñư c ngư i dùng ñưa vào câu truy v n, h th ng tìm ki m thông tin x lý tính b ng công th c: idft = log( ) . Trong ñó, N là t ng s tài li u, N df t các câu truy v n thành ngôn ng ch m c mô t các y u t thông tin dft là s tài li u ch a thu t ng t. c n tìm ki m và th c hi n ñ i chi u v i ch m c tài li u ñ tìm ra các D a trên các giá tr tf và idf, giá tr tr ng s (term-weight) c a tài li u liên quan. Cu i cùng, các tài li u liên quan s ñư c tr v cho m t thu t ng trong m t tài li u ñư c xác ñ nh b ng công th c: wt,d = ngư i dùng theo m t danh sách ñư c s p x p theo ñ ưu tiên chính tft,d*idft. xác gi m d n (ranked list). Giá tr tr ng s này ñư c s d ng trong ma tr n t ch m c, 1.2.2. Cách th c ho t ñ ng c a h tìm ki m thông tin các giá tr khác 0 trong ma tr n th hi n tr ng s c a thu t ng trong 1.2.3. Các b ph n c u thành c a h tìm ki m thông tin tài li u. M t h th ng tìm ki m thông tin ho t ñ ng trên môi trư ng 1.1.6. Truy v n - Query m ng (internet) hay trên môi trư ng máy tính cá nhân (PC) ñ u g m Truy v n (query) là cách bi u di n yêu c u thông tin t ngư i có các thành ph n chính sau: s d ng. Thông thư ng nó ch a các thu t ng và các toán t k t h p 1.2.3.1. B thu th p thông tin - Crawler các thu t ng như AND, OR, LIKE, NEAR. 1.2.3.2. B l p ch m c – Index 1.1.7. S phù h p - Relevant 1.2.3.3. B tìm ki m thông tin – Search Engine M t tài li u ñư c coi là phù h p n u ngư i s d ng ñánh giá 1.2.4. M c tiêu c a h tìm ki m thông tin r ng nó ch a thông tin có giá tr phù h p v i nhu c u tìm ki m thông 1.2.5. Tách t tin. Bên c nh s ph thu c vào tính ch quan c a ngư i s d ng, có 1.3. ĐÁNH GIÁ CÁC H TH NG TÌM KI M THÔNG TIN nhi u ki u phù h p d a trên ngu n tư li u, cách bi u di n yêu c u 1.3.1. N n t ng ñánh giá các h tìm ki m thông tin cũng như ng c nh tìm ki m (context of the search). 1.3.2. Khái ni m v ñ liên quan gi a câu truy v n và tài li u 1.2. H TÌM KI M THÔNG TIN – Information Retrieval Đ liên quan là m t khái ni m ña khía c nh (multifaceted), ña 1.2.1. T ng quan v tìm ki m thông tin và h th ng tìm ki m chi u (multidimension). Theo nghiên c u có nhi u lo i ñ liên quan. thông tin Đ liên quan mang tính ch quan, và ph thu c vào tính cá nhân Tìm ki m thông tin (Information Retrieval - IR) là tìm ki m tài ho c nhân t th i gian. nguyên trên m t t p l n các d li u phi c u trúc ñư c lưu tr trên Có hai lo i ñ liên quan: máy tính nh m th a mãn nhu c u v thông tin.[2] • Đ liên quan nh phân (binary relevance): là ñ liên quan Đ tìm ki m thông tin, trư c h t, h th ng tìm ki m x lý tài ch có 2 giá tr : ho c là có liên quan (relevant _ 1), ho c không có li u thô thành nh ng tài li u ñư c tách t , phân ño n (tokennized liên quan (not relevant _ 0). documents) và sau ñó l p ch m c (index) d a trên v trí c a t . Khi
-9- - 10 - • Đ liên quan nhi u m c ñ (ñ liên quan ña c p ñ ): ñ CHƯƠNG 2 liên quan ñư c xét nhi u m c ñ , có nhi u giá tr . X P H NG TRONG CÁC MÔ HÌNH TÌM KI M THÔNG TIN Trong h u h t các th nghi m ñánh giá h th ng tìm ki m thông tin ngư i ta thư ng quan tâm ñ liên quan nh phân (tài li u có Các mô hình bao g m: mô hình so kh p (Boolean model), mô liên quan (1) ho c không có liên quan (0)). hình tính ñi m tr ng s (term-weight), mô hình không gian vec-tơ 1.3.2. Các tiêu chí ñánh giá hi u qu h truy tìm thông tin (Vector Space Model), mô hình ch m c ng nghĩa ng m (Latent Đ ñánh giá hi u qu c a h truy tìm thông tin có th d a Sematic Indexing), mô hình xác su t (Probabilistic model). Tr mô theo các tiêu chu n sau [5]: hình Boolean, trong các mô hình khác s d ng các công th c x p • D a trên hai ñ ño : h ng, cho phép ngư i s d ng nh p câu truy v n và nh n ñư c danh Đ chính xác (Precision): ñư c ño b i t l c a tài li u tr v sách các tài li u ñư c x p h ng theo m c ñ phù h p [8]. chính xác trên t ng các tài li u nh n ñư c. 2.1. MÔ HÌNH SO KH P CHÍNH XÁC – Boolean Model Đ bao ph (Recall): ñư c ño b i t l c a tài li u tr v 2.1.1. Gi i thi u chính xác trên t ng các tài li u có liên quan. Đây là mô hình s d ng nguyên t c so sánh chính xác khi tìm • Hi u qu th c thi c a h th ng(Execution efficiency) ñư c ki m tài li u. H th ng yêu c u ngư i s d ng cung c p câu truy v n ño b i th i gian th c hi n th t c tìm ki m các văn b n liên quan ñ n dư i hình th c là các t khoá kèm theo các toán t AND, OR, NOT. câu truy v n ñư c cho. 2.1.2. Cách t ch c d li u • Hi u qu lưu tr ñư c ño b i dung lư ng b nh c n thi t M t t p văn b n có n văn b n ñư c bi u di n b i m t ch m c ñ lưu tr d li u. ñư c vector hóa thành ma tr n A – ma tr n này ñư c g i là ma tr n 1.4. Đ I S TUY N TÍNH t ch m c (term document). Trong ñó n văn b n trong t p văn b n 1.4.1. Đ nh nghĩa các lo i ma tr n ñư c bi u di n thành n c t, m t ch m c ñư c bi u di n thành m 1.4.2. Các phép toán cơ b n trên ma tr n dòng. Ph n t dij c a ma tr n A là hai giá tr 1 ho c 0. M t ma tr n 1.4.3. Tính ñ nh th c c a Ma tr n nh phân m c t v i giá tr 1 bi u di n m c t ki có trong tài li u di và 1.4.4. Tính h ng c a Ma tr n 0 là ngư c l i. 1.4.5. Gi i HPTTT b ng phương pháp GAUSS Antony Julius The Hamlet Othello Macbeth … 1.4.6. Tính tr riêng và vector riêng c a Ma tr n and Caesar Tempest 1.4.6.1. Đ nh nghĩa Cleopatra 1.4.6.2. Cách tính tr riêng và vector riêng Antony 1 1 0 0 0 1 …
- 11 - - 12 - Brutus 1 1 0 1 0 0 … Như c ñi m: • Chuy n câu truy v n sang d ng boolean là không ñơn gi n; Caesar 1 1 0 1 1 1 … • Văn b n tr v không quan tâm ñ n th t quan h v i câu Mercy 1 0 1 1 1 1 … truy v n. 2.2. MÔ HÌNH TÍNH ĐI M VÀ TR NG S CHO M C T - Worser 1 0 1 1 1 0 … TERM WEIGHT … … … … … … … … 2.2.1. Gi i thi u Hình 2.1 Ví d ma tr n m c t cho các tác ph m c a Shakespeare Mô hình so kh p chính xác ch tr v giá tr logic là có ho c 2.1.3. Truy v n trong mô hình Boolean không có trong tài li u tìm ki m, k t qu tr v không có th h ng. Trong mô hình Boolean, câu truy v n ñư c thi t l p b ng Đ c i ti n mô hình này, ngư i ta áp d ng cách tính ñi m cho k t qu cách các m c t k t h p v i các toán t AND, OR, NOT. Ví d : tr v , d a trên tr ng s c a m c t trên tài li u. Brutus AND Caesar AND NOT Calpurnia. Đ truy v n trong mô M i m c t trong ma tr n t ch m c ñư c gán m t tr ng s , hình Boolean: d a trên ma tr n nh phân m c t và câu truy v n th c giá tr này ph thu c vào s l n xu t hi n c a m c t trên tài li u hi n l y các vector m c t và so kh p theo toán t bit. ch a m c t và t p tài li u. Tính k t qu ñ liên quan c a câu truy Gi s có ma tr n nh phân m c t như hình 2.1. Đ tr l i cho v n trên t ng văn b n và sau ñó s p x p k t qu tr v . câu truy v n Brutus AND Caesar AND NOT Calpurnia, chúng ta 2.2.2. Cách t ch c d li u th c hi n l y các vector và so kh p theo toán t bit như sau: M t ma tr n m c t ñư c xây d ng v i n c t tương ng v i n Vector m c t Brutus trên ma tr n tương ñương: 110100. văn b n trong t p tài li u, m dòng tương ng v i m m c t . Ph n t Tương t Caesar tương ñương: 110111, Calpurnia: 010000 dij c a ma tr n A thay vì ch có 2 giá tr là 1 ho c 0 như trong mô Th c hi n so kh p các toán t bít như sau: Brutus AND hình Boolean ñư c thay b ng tr ng s c a m c t (term weight). Caesar AND NOT Calpurnia. Tương ñương v i: 110100 AND Tr ng s c a m c t ñư c tính b ng công th c (2.1) 110111 AND NOT 010000 = 100100 2.2.3. Công th c tính tr ng s c a t ch m c Sau khi th c hi n so kh p các giá tr 1 tương ñương v i c t Đ nh nghĩa m t hàm tính tr ng s c a t ch m c như sau: wij = lij * gi * nj (2.1) th i (văn b n th i) trong ma tr n m c t tho mãn ñi u ki n. Như Trong ñó: v y k t qu tr l i s là Antony and Cleopatra (d1) và Hamlet (d4). 2.1.4. Đánh giá mô hình Boolean lij : hàm ñ m s l n xu t hi n c a t ch m c trong m t VB. Ưu ñi m: gi là tr ng s toàn c c c a t ch m c i - là hàm ñ m s l n • Đơn gi n và d s d ng. xu t hi n c a m i t ch m c trong toàn b t p văn b n
- 13 - - 14 - nj là h s ñư c chu n hoá c a văn b n j - là h s cân b ng 2.3. MÔ HÌNH KHÔNG GIAN VECTOR – Vector Space Model chi u dài c a các văn b n trong t p văn b n. 2.3.1. Gi i thi u 2.2.3.1. Các công th c tính tr ng s c c b lij Mô hình không gian vector ñư c phát tri n b i Gerard Salton, 2.2.3.2. Các công th c tính tr ng s toàn c c gi trong ñó tài li u và câu truy v n ñư c bi u di n dư i d ng các vector. 2.2.3.3. Công th c tính h s chu n hoá nj M t văn b n d ñư c bi u di n như m t vector c a các t ch m c 2.2.4. Cách truy v n trong mô hình tính ñi m, tr ng s m c t d = (t1 , t 2 ,K, t n ) . Tương t , câu truy v n cũng ñư c bi u di n như Đi m s c a tài li u d là t ng ñi m c a các m c t trên câu   m t vector q =  t1 , t 2 , K , t n  . Sau khi bi u di n t p văn b n và câu truy v n q có m t trong tài li u d. Truy v n trong mô hình tính ñi m   truy v n thành các vector trong không gian vector, s d ng ñ ño và tr ng s ñư c tính theo công th c: Score(q,di )= ∑ wq ij cosin ñ tính ñ ño tương t gi a các vector văn b n và vector truy Ví d 2.2: v i 1000 tài li u có 100 tài li u ch a m c t “tin” và v n. K t qu sau khi tính toán ñư c dùng ñ x p h ng ñ liên quan 150 tài li u ch a m c t “h c”, gi s tài li u th nh t d có 3 l n xu t gi a văn b n và câu truy v n. hi n m c t “tin” và 4 l n xu t hi n m c t “h c”, khi ñó ñi m s 2.3.2. S hoá t p văn b n c a câu truy v n q=tin h c trên tài li u d s là: Score(q,d) = tftin,d – idftin + tfh – idfh 2.3.2.1. Cách t ch c d li u – Ma tr n t ch m c c,d c Trong mô hình không gian vector, m t t p văn b n có n văn N N = tftin,d * log + tfh c,d * log b n ñư c bi u di n b i m t ch m c ñư c vector hóa thành ma tr n df tin df h A – ma tr n này ñư c g i là ma tr n t ch m c (term document). = 3 * log(1000/100) + 4 * log(1000/150) =6.23 Trong ñó n văn b n trong t p văn b n ñư c bi u di n thành n vector 2.2.5. Đánh giá mô hình tính ñi m, tr ng s m c t c t, m t ch m c ñư c bi u di n thành m dòng. Do ñó ph n t dij c a Ưu ñi m: ma tr n A chính là tr ng s c a t ch m c i xu t hi n trong văn b n • Tr ng s t ch m c không gi i h n b i hai tr 0 ho c 1, j. các tr ng s này ñư c s d ng ñ tính toán ñ ño tương t c a m i 2.3.2.2. Công th c tính tr ng s c a t ch m c văn b n v i câu truy v n. K t qu tr v có quan tâm ñ n th t xu t Trong ma tr n t ch m c, các ph n t c a ma tr n tr ng s c a hi n. t ch m c i ñ i v i t p văn b n ñư c tính b ng công th c: Như c ñi m: wij =lij * gi * nj • K t qu tính tr ng s chưa xét vai trò c a các m c t trong 2.3.3. Truy v n trong mô hình không gian vector câu truy v n. Có th s lư ng các m c t như nhau nhưng vai trò Trong mô hình không gian vector, m t câu truy v n ñư c xem khác nhau hoàn toàn. như t p các t ch m c và ñư c bi u di n như các văn b n trong t p văn b n. S lư ng t ch m c câu truy v n ng n là r t ít so v i s
- 15 - - 16 - lư ng t ch m c nên có r t nhi u t ch m c c a t p văn b n không Cho câu truy v n c a ngư i dùng q và văn b n d trong t p văn xu t hi n trong câu truy v n, có nghĩa là h u h t các thành ph n c a b n. Mô hình xác su t tính xác su t mà văn b n d liên quan ñ n c u vector truy v n là 0. Th t c truy v n chính là tìm các văn b n trong truy v n c a ngư i dùng. Mô hình gi thi t xác su t liên quan c a t p văn b n liên quan v i câu truy v n hay còn g i là các văn b n có m t văn b n v i câu truy v n ph thu c cách bi u di n chúng. T p ñ ño tương t “cao” v i câu truy v n. Theo cách bi u di n hình h c, văn b n k t qu ñư c xem là liên quan và có t ng xác su t liên quan các văn b n ñư c ch n là các văn b n g n v i câu truy v n nh t theo v i câu truy v n l n nh t [11]. m t ñ ño (measure) nào ñó. Đ ño thư ng ñư c s d ng nh t là ñ 2.4.2. Mô hình tìm ki m nh phân ñ c l p - Binary independence ño cosin c a góc gi a vector truy v n và vector văn b n ñư c tính retrieval -BIR theo công th c: 2.4.3. Mô hình m c ñ ñáng k (eliteness) ∑ T m dj q d ij qi 2.4.4. Công th c BM25 cos θ j = = i =1 2.4.5. Đánh giá mô hình xác su t ∑ ∑ m m dj q d 2 q 2 2 2 i =1 ij i =1 i 2.5. MÔ HÌNH CH M C NG NGHĨA NG M - LSI Trong ñó dij là giá tr tr ng s c a ph n t trong ma tr n t 2.5.1. Gi i thi u ch m c; qi là giá tr tr ng s c a ph n t th i trong vector câu truy Latent Semantic Indexing (LSI) là phương pháp t o ch m c ng nghĩa ng m d a trên khái ni m ñ kh c ph c hai h n ch t n t i v n. trong mô hình không gian vector chu n v v n ñ ñ ng nghĩa 2.3.4. Đánh giá mô hình không gian vector (synoymy) và ña nghĩa (polysemy) [14]. V i synoymy, nhi u t có Ưu ñi m: th ñư c s d ng ñ bi u di n m t khái ni m, vì v y h th ng không • Đưa ra khái ni m phù h p m t ph n; công th c x p h ng th tr v nh ng văn b n liên quan ñ n câu truy v n c a ngư i dùng cô-sin cho phép ñ ng th i xác ñ nh s phù h p và ph c v s p x p khi h s d ng nh ng t trong câu truy v n ñ ng nghĩa v i nh ng t danh sách k t qu .. trong văn b n. V i polysemy, m t t có th có nhi u nghĩa, vì v y h Như c ñi m: th ng có th tr v nh ng văn b n không liên quan. Đi u này th c t • S chi u bi u di n cho t p văn b n có th r t l n nên t n r t thư ng x y ra b i vì các văn b n trong t p văn b n ñư c vi t b i nhi u không gian lưu tr ; r t nhi u tác gi , v i cách dùng t r t khác nhau. M t cách ti p c n • Không xét quan h v ng nghĩa v i câu truy v n. t t hơn cho phép ngư i dùng truy v n văn b n d a trên khái ni m 2.4. MÔ HÌNH XÁC SU T - Probabilistic model (concept) hay nghĩa (meaning) c a văn b n. 2.4.1. Gi i thi u Mô hình LSI kh c ph c hai h n ch trên trong mô hình không gian vector b ng cách ch m c khái ni m ñư c t o ra b i phương
- 17 - - 18 - pháp phân tích giá tr ñơn (Single Value Decomposition - SVD) t m c và s d ng ki m ñ nh th ng kê ñ ch n h s k t t nh t trên dãy ma tr n t ch m c (term – document A). các h s k ñư c ch n th nghi m. 2.5.2. Phân tích giá tr ñơn (Single Value Decomposition - SVD) 2.5.4. Truy v n trong mô hình LSI c a ma tr n t ch m c Đ truy v n trong mô hình LSI: Tính ñ ño cosines c a các V n ñ cơ b n c a mô hình LSI là dùng k thu t phân hu giá góc gi a vector truy v n q và các vector văn b n trong ma tr n x p x tr ñơn SVD trên ma tr n t ch m c ñ t o ra m t ma tr n ng nghĩa. Ak (Đ ño cô-sin ñư c tính theo công th c trong mô hình không gian M c ñích c a vi c phân tích SVD là phát hi n ra m i quan h ng vector). Ho c các văn b n có th ñư c so sánh v i nhau b ng cách nghĩa trong cách dùng t trong toàn b văn b n A = UΣV T và gi m tính ñ ño cosines các vector văn b n trong “không gian văn b n” s chi u ma tr n sau khi phân tích. (document space) – chính là so sánh các vector c t trong ma tr n Đ u tiên, t t p d li u xây d ng ma tr n t ch m c ñư c bi u VkT . M t câu truy v n q ñư c xem như là m t văn b n và gi ng như di n trong ñó m i dòng tương ng v i m t t ch m c (term) xác m t vector c t ñư c thêm vào ma tr n VkT . Đ thêm q như m t c t ñ nh quan h (s l n xu t hi n, hay tr ng s ) c a thu t ng ñ i v i m i vào VkT ta ph i chi u q vào không gian văn b n k chi u. các tài li u. Tương t , m i c t bi u di n cho 01 tài li u. T công th c: A=U Σ VT Ti p theo, LSI áp d ng k thu t phân h y giá tr ñơn (SVD) ⇒ AT= (U Σ VT)T = V Σ UT trên ma tr n t ch m c. Ma tr n t ch m c A b phân h y thành s n ⇔ ATU Σ −1 = V Σ UTU Σ −1 ph m c a ba ma tr n khác: A = UΣV . T ⇒ V=ATU Σ −1 Khi rút g n ma tr n ∑, gi l i m t s k ph n t ñ u tiên và rút Ma tr n V g m n dòng (n>1), m i dòng c a ma tr n V th hi n T g n tương ng các ma tr n U và V , s t o ra m t x p x g n ñúng 01 vector tài li u d: d=dTU Σ −1 cho ma tr n t ch m c A. Vi c gi m chi u trong không gian k chi u, vector d có th −1 2.5.3. Ch n h s k trong mô hình LSI ñư c vi t l i như sau: d=dTUk Σ k Trong mô hình LSI, vi c ch n h s k ñ xây d ng ma tr n x p M t câu truy v n q ñư c xem như là m t văn b n và gi ng như x là m t vi c h t s c quan tr ng ñ n hi u qu c a thu t toán. Theo m t vector c t ñư c thêm vào ma tr n VkT . Đ thêm q như m t c t các tài li u nghiên c u v LSI [6] qua th c nghi m trên các t p d m i vào VkT ta ph i chi u q vào không gian văn b n k chi u: −1 li u văn b n c th , các tác gi ch n k t 50 ñ n 100 cho các t p d q=qTUk Σ k li u nh và t 100 ñ n 300 cho các t p d li u l n. Tính ñ liên quan gi a vector truy v n q và vector tài li u di M t phương pháp ñ ngh ch n h s k g n ñây nh t (2003) trong ma tr n VkT b ng công th c sau: ñư c ñưa ra b i Miles Efron trong tài li u [26], tác gi s d ng −1 −1 q.d sim(q,d)=sim(qTUk Σ k ,dTUk Σ k )= phương pháp phân tích giá tr riêng (Eigenvalue) c a ma tr n t ch | q |.| d |
- 19 - - 20 - S p k t qu tr v theo gi m d n ñ liên quan. ñ ng nghĩa và ña nghĩa. Hi u qu c a mô hình LSI ñư c ñánh giá là 2.5.5. C p nh t giá tr trong mô hình LSI cao hơn so v i mô hình VSM [6], [7]. Thông tin thì luôn luôn ñư c thêm vào hay b xóa ñi, ñi u ñó 2.6.2. Đánh giá theo th nghi m trên hai mô hình VSM và LSI có nghĩa r ng ma tr n ch m c cũng luôn b bi n ñ ng. Trong mô Như ñã trình bày trong chương 1, hi u qu c a m t h IR cơ hình LSI, khi có m t văn b n m i ñư c thêm vào hay b xóa ñi ñ u b n ñư c ñánh giá d a trên 3 tiêu chu n: hi u qu truy tìm, hi u qu nh hư ng ñ n vi c tính toán l i giá tr trong ma tr n t ch m c và lưu tr d li u ch m c; Th i gian th c hi n th t c truy v n. ma tr n x p x thông qua k thu t phân tích SVD. Đ i v i các ma 2.6.2.1. Đánh giá hi u qu truy tìm tr n l n, vi c tính toán l i t n r t nhi u chi phí và th i gian. Trên th c t vi c s d ng hai ñ ño precision và recall ñ ñánh 2.5.5.1. C p nh t văn b n (SVD- Updating document) giá hi u qu c a h th ng b t kỳ là r t khó, vì th c t không th xác 2.5.5.2. C p nh t t ch m c (SVD- Updating terms): ñ nh ñư c s văn b n liên quan ñ n câu truy v n c th trong t p văn 2.5.5.3. Xoá t ch m c(Downdating) l n là bao nhiêu, ch có th th c hi n ñi u này trên t p văn b n nh , 2.5.6. Đánh giá mô hình LSI ñư c ch n l a và phân lo i chi ti t. M t khó khăn n a g p ph i là Ưu ñi m: trong vi c ñánh giá k t qu tr v c a t p văn b n liên quan ñ n câu • LSI là phương pháp t o ch m c t ñ ng d a trên khái truy v n ph thu c r t nhi u vào tính ch quan c a ngư i ñánh giá và ni m ñ kh c ph c h n ch t n t i trong mô hình không gian vector nhu c u. Vì v y ch ñánh giá và so sánh hi u qu c a h IR b ng cách v hai v n ñ ñ ng nghĩa (synoymy) và ña nghĩa (polysemy) [9]; so sánh t ng s văn b n liên quan ñư c tr v c a hai h VSM_IR và • Vi c gi m s chi u c i thi n ñáng k chi phí lưu tr và th i LSI_IR khi th nghi m trên cùng m t t p câu truy v n. 2.6.2.2. Đánh giá dung lư ng lưu tr d li u ch m c gian th c thi. Dung lư ng b nh RAM cho m i h IR lưu tr d li u ch Như c ñi m: m c khi th c thi ñư c ño b i ma tr n ch m c. Công th c tính sau: • Vi c tìm ki m cũng ph i quét qua t t c các c t trong ma RAM = ( x ) x (sizeof( )) tr n LSI nên cũng t n nhi u chi phí và th i gian. 2.6.2.3. Đánh giá th i gian th c thi th t c truy v n 2.6. ĐÁNH GIÁ CÁC MÔ HÌNH X P H NG 2.6.3. Xác ñ nh mô hình cài ñ t th nghi m 2.6.1. Đánh giá theo lý thuy t Qua các phân tích ñánh giá, ñ tài xác ñ nh mô hình cho vi c Do tính hi u qu th p c a mô hình Boolean, mô hình xác su t, cài ñ t th nghi m là mô hình x p h ng tài li u pheo phương pháp nên hi n nay mô hình VSM và mô hình LSI ñang ñư c nghiên c u ch m c ng nghĩa ti m n LSI. ph c v cho vi c xây d ng các h th ng IR hi n ñ i [6]. Mô hình LSI ñư c ñưa ra ñ kh c ph c nh ng h n ch c a mô hình VSM là v n ñ
- 21 - - 22 - CHƯƠNG 3 T p văn b n Câu truy v n CÀI Đ T TH NGHI M H IR THEO MÔ HÌNH LSI 3.1. MÔ T KI N TRÚC H IR THEO MÔ HÌNH LSI T o Term_Index file Hình 3.1 sau mô t ki n trúc h tìm k m theo mô hình LSI, T o Doc_Index file g m các bư c: • X lý văn b n và t o các t p tin ch m c t (Term_ T o Term – Document Matrix A Index.out) và t p tin ch m c văn b n (Doc_ Index.out) Vector hoá • T o ma tr n ch m c t (Term – Document A) Tính SVD(A) • Tính SVD ma tr n ch m c t (Term – Document) A = UΣV T Ch n h s k • Ch n h s k Ak = U k Σ k VkT • T o ma tr n x p x Tính ma tr n x p x • X lý truy v n Ak • X p h ng k t qu tr v theo th t gi m d n ñ ño cosines 3.2. Đ T T CÁC BƯ C XÂY D NG H LSI-IR 3.2.1. Xây d ng file t ch m c 3.2.2. Xây d ng ma tr n t ch m c 3.2.3. Phân tích SVD ma tr n t ch m c A Term_Index file 3.2.4. Xác ñ nh h s k Doc_Index file X lý truy v n Uk_Matrix file 3.2.5. Xây d ng ma tr n x p x Ak Sk_Matrix file 3.2.6. Th c hi n truy v n và x p h ng k t qu tr v Vk_Matrix file X p h ng k t qu tr T p k t qu v tr v Hình 3.1 Ki n trúc h LSI-IR
- 23 - - 24 - 3 003 79% 4 004 74% 3.3. B D LI U TH NGHI M VÀ MÔI TRƯ NG PHÁT 5 005 78% TRI N 6 006 93% 3.3.1. B d li u th nghi m 7 007 88% B d li u ph c v th nghi m h th ng: t p Cranfield 8 008 94% 9 009 100% collection ñư c l y t Internet [24] v i kích thư c 10 010 94% • T p văn b n (docummetn collection):1.400 văn b n, kích Precision trung bình 81% thư c 1.57MB Qua k t qu th nghi m trên t p d li u 1400 văn b n và 3763 • T p truy v n (query): 365 câu truy v n, kích thư c 28KB. t ch m c v i 20 câu truy v n và căn c vào b ng ñánh giá ñ liên • B ng ñánh giá ñ liên quan gi a câu truy v n và văn b n quan, k t qu ñ t ñư c c a ñ ño precision trung bình là 81% . • 3763 t ch m c trên t p văn b n, kích thư c 1.98MB V i vi c th nghi m trên cùng m t t p câu truy v n cho c hai • H s k cho mô hình LSI: k=185. H s này ñã ñư c ki m h IR, th i gian cho th t c tìm ki m trên LSI_IR nhanh hơn trên th có hi u qu nh t trên t p CRAN [24]. dư i 30 l n so v i VSM_IR. H VSM th i gian tìm ki m là 13.344 3.3.2. Môi trư ng cài ñ t h th ng giây, h LSI là 0.407 giây. 3.4. K T QU TH NGHI M Dung lư ng b nh RAM cho m i h IR lưu tr d li u ch 3.4.1. B d li u m c khi th c thi ñư c ño b i ma tr n ch m c. 3.4.2. Ma tr n t ch m c • V i h VSM_IR, ma tr n ch m c A (1400 x 3763) m i ph n 3.4.3. B câu h i th c hi n truy v n t ma tr n có ki u float trong java chi m 4 byte. 3.4.4. B ng ñánh giá ñ liên quan gi a b câu h i trên t p d li u RAM = (1400 x 3763) x 4(byte) = 20MB th nghi m • V i LSI_IR lưu ba ma tr n U3763x185, Σ185*185 , và V185*1400 . T 3.4.5. Đánh giá k t qu th nghi m K t qu th nghi m ñ ño Precision trên t p d li u 1400 văn RAM =(3763 x 185 + 185 x 185 + 185 x 1400) x 4(byte) = 3.8 MB b n và 3763 t ch m c v i 20 câu truy v n. Ch n h s k = 185 cho V i k t qu như trên: có th th y r ng dung lư ng lưu tr d mô hình LSI. li u ch m c c a mô hình LSI gi m hơn 90% so v i VSM. Đi u này B ng 3.2 Đ ño Precision trung bình c a mô hình LSI v i k=185 cho th y thông qua k thu t phân hu VSD chi phí lưu tr gi m ñi r t STT Câu truy v n Precision LSI nhi u. 1 001 75% 2 002 56%
- 25 - - 26 - K T LU N VÀ HƯ NG PHÁT TRI N m t phương pháp, là trư c khi th c hi n tính Cosines gi a vector truy v n v i các vector văn b n trong ma tr n Ak ta ti n hành gom 1. K t lu n c m văn b n trư c trong ma tr n Ak. K t h p LSI vào trong bài toán Đ tài “Nghiên c u, th nghi m và ñánh giá các phương pháp gom c m văn b n. x p h ng k t qu tìm ki m” ñã t p trung nghiên c u các phương pháp Đ i v i mô hình LSI hi u qu truy tìm c a h th ng cũng như x p h ng tài li u theo các mô hình khác nhau như: mô hình không hi u qu v dung lư ng lưu tr và th i gian tìm ki m ph thu c vào gian vector VSM, ch m c ng nghĩa LSI, các công th c và cách k t vi c ch n h s k. Bài toán này hi n nay v n ñang là bài toán m h p gi a các công th c ph c v cho vi c tính tr ng s c a t ch chưa có l i gi i t ng quát, ch gi i quy t b ng th c nghi m trên t p m c. T nh ng nghiên c u v lý thuy t này ñã ñưa ra ñư c ki n trúc d li u c th . Hư ng phát tri n tương lai là s d ng các công c cơ b n c a m t h IR d a trên mô hình LSI. toán h c v t i ưu hoá ñ gi i quy t bài toán ch n h s k sao cho h Đánh giá hi u qu th c thi c a hai mô hình v các tiêu chí hi u th ng ho t ñ ng t i ưu trong mô hình LSI này. qu truy tìm, th i gian và dung lư ng b nh c n thi t lưu tr d li u s hoá cho m i mô hình. T ñó, th y ñư c hi u qu c a mô hình ng nghĩa LSI cao hơn so v i mô hình không gian vector r t nhi u. T k t qu này, h tr cho vi c xây d ng các h IR th c t có hi u qu truy tìm cao. Nh ng k t qu ñ t ñư c làm cơ s lý thuy t và th c nghi m cho vi c xây d ng các h IR th c t ho t ñ ng hi u qu v sau. 2. Hư ng phát tri n Trong mô hình LSI, vi c phân tích SVD cho ma tr n t ch m c trong mô hình không gian vector làm gi m ñi s chi u c a ma tr n A r t nhi u và vi c gi i quy t ñư c quan h ng nghĩa các văn b n liên quan ñ n câu truy v n mà ñư c xem là ñi m y u trong mô hình không gian vector, nên mô hình LSI ñư c ñánh giá r t cao. Tuy v y, ñ tr v các văn b n liên quan thì cũng ph i ñi so sánh v i t t c các văn b n trong ma tr n x p x Ak. Đi u này d n ñ n vi c h n ch t c ñ tìm ki m c a gi i thu t. Đ kh c ph c ñi u này, ñ ngh