Bài giảng Tìm kiếm và trình diễn thông tin: Bài 4 - TS.Nguyễn Bá Ngọc

Chia sẻ: Codon_02 Codon_02 | Ngày: | Loại File: PDF | Số trang:31

Thêm vào BST

Báo xấu

92
lượt xem 11
download

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

Bài giảng Tìm kiếm và trình diễn thông tin: Bài 4 hướng đến trình bày trọng số từ, mô hình không gian vec-tơ như: Xếp hạng kết quả tìm kiếm; mức tương đồng; hệ số Jaccard; trọng số từ;...

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Tìm kiếm và trình diễn thông tin: Bài 4 - TS.Nguyễn Bá Ngọc

(IT4853) Tìm kiếm và trình diễn thông tin Trọng số từ, mô hình không gian vec-tơ 1
Giảng viên  TS. Nguyễn Bá Ngọc  Địa chỉ: Viện CNTT & TT/BM HTTT/B1-603  Email: ngocnb@soict.hust.edu.vn  Website: http://is.hust.edu.vn/~ngocnb 2
Nội dung chính  1. Trọng số từ  2. Mô hình không gian vec-tơ 3
Xếp hạng kết quả tìm kiếm  Theo tiêu chí tương đồng:  Đánh giá mức tương đồng giữa văn bản và truy vấn  Trả về những văn bản có mức tương đồng cao và theo thứ tự giảm dần giá trị đó. 4
Mức tương đồng  Trong xếp hạng, quan hệ thứ tự quan trọng hơn tính chính xác của các giá trị.  Thông thường mức tương đồng được đưa về miền giá trị [0, 1].  Văn bản thường được đánh giá dựa trên cách sử dụng từ truy vấn. 5
Ch. 6 Hệ số Jaccard  Hai đối tượng bất kỳ được đánh giá là tương đồng nếu chia sẻ những đặc trưng chung.  Hệ số Jaccard được sử dụng khá rộng rãi để đánh giá mức tương đồng.  Đối với hai tập hợp A và B:  Jaccard(A, B) = |A ∩ B| / |A ∪ B|  0
Trọng số từ  Thể hiện tầm quan trọng của từ đối với văn bản:  Đồng biến với số lần từ được sử dụng trong văn bản.  Nghịch biến với số văn bản sử dụng nó. 7
Trọng số tf.idf  Trọng số tf.idf được tính như sau: wtf.idf(t, d) = wtf(t,d) x idf(t) 8
Thành phần tf  Term Frequency (tf)  Trọng số 1 + 𝑙𝑜𝑔10 𝑡𝑓𝑡,𝑑 , 𝑁ế𝑢 𝑡𝑓𝑡,𝑑 > 0 𝑤𝑡𝑓 𝑡, 𝑑 = 0, 𝑁ế𝑢 𝑛𝑔ượ𝑐 𝑙ạ𝑖  Trong đó: tft,d là tần suất từ t trong văn bản d là số lần từ t được sử dụng trong văn bản d 9
Thành phần idf  Inverse document frequency (idf)  Xác định idf(t) như sau: idf(t) = log10(N/dft)  Trong đó N là số văn bản trong bộ dữ liệu; dft là số văn bản chứa từ t 10
Nội dung chính  1. Trọng số từ  2. Mô hình không gian vec-tơ 11
Biểu diễn văn bản và truy vấn  Trong không gian vec-tơ M chiều, với M = |V| là kích thước bộ từ vựng, mỗi thuật ngữ trong bộ từ vựng là một trục của không gian:  Mỗi văn bản, mỗi truy vấn là một điểm trong không gian này  M có thể rất lớn, vec-tơ biểu diễn văn bản và truy vấn là những vec-tơ thưa.  Ký hiệu 𝑑, 𝑞 là biểu diễn vec-tơ của văn bản d và truy vấn q. 12
Xác định mức tương đồng  Tương đồng là đặc tính nghịch của sự khác biệt.  Có thể xác định mức khác biệt bằng khoảng cách.  Thử nghiệm 1: Xếp hạng văn bản theo thứ tự tăng dần của khoảng các Euclide giữa các điểm biểu diễn văn bản và truy vấn. 13
Ví dụ khoảng cách Euclide  Khoảng cách Euclide giữa biểu diễn vec-tơ của q và d2 tương đối lớn mặc dù phân bố từ khá giống nhau 14
Sử dụng khoảng cách góc  Thử nghiệm 2: Từ văn bản d thiết lập d’ bằng cách lặp lại nội dung của d.  Về mặt nội dung thì d và d’ là tương đương. Văn bản d’ tuy dài hơn nhưng không cung cấp thông tin mới.  Khoảng cách Euclide giữa d và d’ có thể rất lớn  Góc giữa biểu diễn vec-tơ của d và d’ bằng 0 thể hiện mức tương đồng cực đại  Xếp hạng văn bản theo thứ tự tăng dần của góc giữa các biểu diễn vec-tơ của văn bản và truy vấn. 15
Thay thế góc bằng cosine  Hai phương pháp sau là tương đương  Xếp hạng văn bản theo thứ tự tăng dần góc giữa các biểu diễn vec-tơ của văn bản và truy vấn  Xếp hạng văn bản theo thứ tự giảm dần cosine góc giữa các biểu diễn vec-tơ của văn bản và truy vấn.  Cosine là hàm đơn điệu giảm trong khoảng [0o,180o] 16
Sử dụng cosine thay góc Tính cosine như thế nào? Ưu điểm sử dụng cosine so với góc? 17
Mức tương đồng Cosine t3  Mức tương đồng cosine thể hiện bằng cosine 1 góc giữa hai vec-tơ  Là tích vô hướng chia cho tích độ dài các vec-tơ D1 Q |V | 2   d q  (wi,d  wi,q ) t1 Simcos (d , q)     i 1 d q |V | |V | t2 w w D2 2 i ,d  2 i ,q i 1 i 1 D1 = 2T1 + 3T2 + 5T3 Simcos(D1 , Q) = 10 / (4+9+25)(0+0+4) = 0.81 D2 = 3T1 + 7T2 + 1T3 Simcos(D2 , Q) = 2 / (9+49+1)(0+0+4) = 0.13 Q = 0T1 + 0T2 + 2T3 D1 phù hợp với truy vấn hơn D2 6 lần theo độ tương đồng Cosine nhưng chỉ hơn 5 lần theo tích vô hướng. 18
Chuẩn hóa cosine  Chia mỗi thành phần vec-tơ cho độ dài của nó, độ dài vec-tơ được xác định như sau:  x 2  i xi2  Độ dài vec-tơ đã chuẩn hóa bằng 1, vì vậy mỗi văn bản là một điểm trên bề mặt siêu cầu có bán kính 1 đơn vị.  Chuẩn hóa làm mờ sự khác biệt trọng số giữa các văn bản dài và ngắn 19
Cosine cho vec-tơ đã chuẩn hóa  Cosine góc giữa các vec-tơ đã chuẩn hóa bằng tích vô hướng của các vec-tơ này:     cos(q, d )  q  d  i 1 qi di V Với 𝑑 và 𝑞 là những vec-tơ đã chuẩn hóa 20