Học xếp hạng trong tính hạng đối tượng và tạo nhãn cụm tài liệu

∑ d∈D PR(d)×max γ ( ∏ ei∈γ ei.conf × αB(γ)× p(s|γ)) pτ = p(q(t)|D ′) = m∏ j=1 ( ∑ ej∈d,d∈D p(d))× l∏ i=1 ( ∑ ki∈d,d∈D p(d))× × m∏ j=1 ej.conf × ∑ s p(q(t)|s) |s| 3.2.2 Nhận xét, đánh giá mô hình Impression Ưu điểm Với những đặc điểm của tìm kiếm thực thể được phân tích, mô hình Impression đã bám sát và xác định hàm tính hạng Score(q(t)) để đảm bảo các tính chất đó: 1. Tính chất R-Contextual được thể hiện ở các trọng số αB và p(s|γ) 2. Xác định giá trị cực đại theo γ để chọn ra quan sát "phù hợp" nhất (R-Holistic) CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 28 3. Tính chất R-Uncertainty của việc rút trích các thực thể và đánh giá các thực thể được thể hiện ở trọng số ei.conf 4. Bằng kiểm định giả thiết thống kê trong tầng đánh giá (Validate), tính chất R-Associative được đảm bảo 5. Sử dụng trọng số PR - độ quan trọng/phổ biến của trang web (đảm bảo tính chất R-Discriminative) Đánh giá chất lượng của xếp hạng các bộ thực thể t tìm được, [18] giới thiệu các phương pháp xếp hạng làm đối sánh: • N (Naive): xếp hạng theo phần trăm các tài liệu có chứa t. • L (Local Model Only): xếp hạng dựa theo trọng số cục bộ cao nhất của t trong từng tài liệu. • G (Global Aggregation Only): xếp hạng theo tổng trọng số của các tài liệu có chứa t. Và PR được chọn là trọng số cho mỗi tài liệu. • C (Combination of Local Model and Global Aggregation): xếp hạng theo tổng trọng số cục bộ của t trong tất cả các tài liệu chứa t. • W (EntityRank Without G-test): xếp hạng theo trọng số tổng hợp của Entity Rank nhưng không sử dụng đánh giá G-test (p0). Và theo đánh giá trong [18] (hình 3.6) độ chính xác kết quả xếp hạng của thuật toán EntityRank (xếp hạng với mô hình Impression) có MRR u 0.65 cao hơn gấp nhiều lần những phương pháp xếp hạng đối sánh được đưa ra. Nhược điểm Trong tài liệu d, một thực thể có thể xuất hiện nhiều lần và phù hợp với ngữ cảnh truy vấn (các quan sát γ) theo tính chất R-Holistic. Việc ước lượng với công thức 3.5 chỉ mang ý nghĩa lựa chọn quan sát phù hợp nhất trong tài liệu. Tuy nhiên, ta CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 29 Measure EntityRank L N G C W M R R 0.648 0.047 0.037 0.050 0.266 0.379 M R R 0.648 0.125 0.106 0.138 0.316 0.387 Query Type I MRR Comparison Measure EntityRank L N G C W M R R 0.659 0.112 0.451 0.053 0.573 0.509 M R R 0.660 0.168 0.454 0.119 0.578 0.520 Query Type II MRR Comparison Hình 3.6: So sánh độ chính xác MRR [18] có thể dễ dàng nhận thấy số lần xuất hiện trong tài liệu của thực thể mà phù hợp ngữ cảnh cũng có một vai trò quan trọng, ảnh hưởng hạng của thực thể. Ví dụ: trong tài liệu trích chọn các thực thể thuốc hình 3.5, với truy vấn q = {"viêm"#drug}. Nếu chỉ xét trên tài liệu này thì một cách trực giác ta thấy các thực thể thuốc nên được xếp hạng {"Diclofenac", "NSAID", "Voltaren", "Catafram","Voltaren-XR","steroid"}. Nếu chỉ dựa vào công thức 3.5, thì rõ ràng ở đây thuốc "steroid" được xếp hạng đầu tiên- như vậy không hợp lý. Thêm nữa, từ bảng so sánh độ chính xác của một số phương pháp xếp hạng hình 3.6, ta dễ dàng nhận thấy độ đo C có ý nghĩa cao hơn hẳn L, tức độ đo dựa vào tổng trọng số cục bộ trong từng tài liệu có ý nghĩa cao hơn lấy trọng số cục bộ cao nhất. 3.2.3 Mô hình đề xuất Mô hình xếp hạng Impression, công thức xác định giá trị để xếp hạng thực thể được đưa ra hoàn toàn dựa vào việc phân tích các đặc điểm và tìm công thức để thỏa mãn các nhận định đó. Tuy nhiên sau khi phân tích nhược điểm ở trên đã cho thấy như vậy là chưa đầy đủ. Học xếp hạng cho ta giải pháp để giải quyết vấn đề, tìm hàm tính hạng "tốt nhất" với các đặc trưng xác định. Qua phân tích các đặc điểm của CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 30 tìm kiếm để đưa ra các trọng số tương ứng với các đặc trưng của thực thể. Mô hình học xếp hạng thực thể trong máy tìm kiếm thực thể đề xuất hình 3.7. Trong mô Learning Ranking Mô hình ),( tqf ),(, ),(, 22 11 tqft tqft ii ii )1( 2 )1( 1 )1( t t q )( 2 )( 1 )( m m m t t q Truy vấn Dữ liệu học ?),(......, ?),(?),,( 21 nt tt q Hàm th ự c th ể ... .. . ... .. . ... .. . Hình 3.7: Mô hình học xếp hạng trong máy tìm kiếm thực thể hình, thành phần được bao đen là một thành phần xếp hạng trong máy tìm kiếm. Mô-dul học xếp hạng độc lập với phần tìm kiếm, có nhiệm vụ học hàm xếp hạng (có thể chỉ cần một lần) để đưa ra mô hình/hàm xếp hạng phù hợp cho mô-dul xếp hạng của máy tìm kiếm. Dữ liệu học Tập dữ liệu học gồm DT tài liệu- đã xác định các thực thể trong mỗi tài liệu, và tập truy vấn QT . Với mỗi truy vấn q ∈ QT , q = α(e1, ..., em, k1, ..., kl) có danh sách các thực thể (t(1..m)i ) tương ứng phù hợp truy vấn q và được sắp xếp giảm dần độ phù hợp. Mỗi bộ thực thể t có các đặc trưng tương ứng với mỗi truy vấn q, từ những phân tích về máy tìm kiếm thực thể và xếp hạng thực thể, tôi xác định các đặc trưng của thực thể: CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 31 1. Tỷ lệ trang tài liệu chứa t phù hợp với q: N = |D′| |DT | với ∀d ∈ D′có q(t) ∈ d 2. Tổng trọng số PR của các trang tài liệu chứa t phù hợp với q: G = ∑ d∈DT , q(t)∈d PR[d] 3. Trọng số cục bộ lớn nhất (công thức 3.3) của t với truy vấn q trên tất cả các tài liệu: L = max d∈DT , q(t)∈d max γ∈d p(α(γ)) Với γ là một quan sát của t trên tài liệu d 4. Tổng trọng số cục bộ của t trong tất cả các tài liệu chứa t phù hợp q: SL = ∑ d∈DT , q(t)∈d, γ∈d p(α(γ)) 5. Tổng các tích trọng số cục bộ của t trong từng tài liệu chứa t phù hợp q nhân với PR của tài liệu đó: GL = ∑ d∈DT , q(t)∈d, γ∈d ( p(α(γ))×PR[d] ) 6. Giá trị cực đại của tích trọng số cục bộ của t nhân PR của tài liệu chứa t tương ứng: M = max d∈DT , q(t)∈d, γ∈d ( p(α(γ))×PR[d] ) Trong các công thức trên, p(α(γ)) là trọng số cục bộ của thực thể t ứng với quan sát γ trong tài liệu d đang xét. Với các phạm vi (domain ) tìm kiếm thực thể khác nhau, giá trị trọng số cục bộ có thể được thay đổi phù hợp. Thực nghiệm với domain cụ thể dưới đây, tôi sẽ đưa ra cách tính cho đại lượng này. CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 32 3.3 Thực nghiệm Hiện nay, đang có một dự án nghiên cứu xây dựng "hệ theo dõi sức khỏe toàn cầu" mang tên BioCaster∗ giúp tìm kiếm những thông tin về y-sinh học một cách chính xác hơn các máy tìm kiếm thông thường. Điều đó cho thấy việc xây dựng hệ tìm kiếm y tế đang rất được quan tâm. Tiếp cận vấn đề thời sự về xếp hạng thực thể và tìm kiếm y tế, tôi tiến hành thử nghiệm mô hình xếp hạng thực thể của mình vào máy tìm kiếm trong lĩnh vực y tế tiếng Việt, mà cụ thể là tìm kiếm thực thể thuốc. Vấn đề rút trích thực thể không nằm trong phạm vi của luận văn này, với thử nghiệm của mình, khi khảo sát dữ liệu, tôi đưa ra cách xác định thực thể thuốc đơn giản như sau: • Thực thể thuốc trên trang web tiếng Việt: tên thuốc thường là tiếng Anh, ngoại trừ tên các nước, tên viết tắt của doanh nghiệp (tuân theo một số mẫu xác định, ví dụ: "Rottapharm., Ltd", "dược phẩm Hà Nội HAPHARCO"). • Một thực thể đã được xác định là thuốc thì chắc chắn đó là thuốc. Như mô hình đã đưa ra, trọng số cục bộ của một quan sát γ trên d cần được xác định. Với quan nhận định: mối liên kết giữa thực thể và từ khóa ngữ cảnh càng khăng khít khi chúng càng gần nhau, nên trọng số cục bộ được xách định: p(α(γ)) = 1 Sγ Với Sγ là kích thước của đoạn tài liệu bao quan sát γ, ví dụ hình 3.8. 3.3.1 Công cụ sử dụng Các chương trình phần mềm mã mở đã được sử dụng trong thực nghiệm này: SVMmap† là công cụ (tool) học giám sát với tối ưu MAP để học xếp hạng tài liệu. Trong thực nghiệm tôi sử dụng công cụ này áp dụng vào học mô hình xếp hạng thực thể. ∗ † CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 33 Tài liệu: d = “Desipramin1 là2 thuốc3 được4 dùng5 điều6 trị7 trầm8 cảm9” Truy vấn: q=("trầm cảm" #drug) Với quan sát: γ=(o1,o2) thì o1 o2 Hình 3.8: Ví dụ xác định trọng số cục bộ p(α(γ)) Lucene‡ là một máy tìm kiếm văn bản (text) mã mở được lựa chọn để tiến hành cài đặt các modul: • Rút trích thực thể thuốc • Đánh chỉ mục (index) thực thể • Xếp hạng thực thể thuốc 3.3.2 Dữ liệu Dữ liệu tìm kiếm Tiến hành thu thập (crawl) các trang web về y tế tiếng Việt, từ nguồn của 10 web site (phụ lục A.1) • Tổng số trang web tiếng Việt được crawl và index: 6217 trang (không index những trang web có nội dung quá ngắn- dưới 20 từ, và các trang web chỉ chứa liên kết) • Kích thước dữ liệu: sấp xỉ 180MB • Số thể hiện của thực thể thuốc được index: 14794 ‡ CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 34 Các mẫu truy vấn được sử dụng 1. q=(context #drug): Tìm thực thể thuốc với ngữ cảnh context mà truy vấn xác định. 2. q=(context #drug=[Thuoc] #drug): Tìm thực thể thuốc có quan hệ với thực thể thuốc Thuoc trong ngữ cảnh context được xác định trong truy vấn. Xây dựng tập dữ liệu học đưa vào mô-dul học hàm tính hạng Tạo 5 truy vấn cho mỗi mẫu truy vấn trên, với mỗi truy vấn xác định 10 thực thể trả về đầu tiên tương ứng và sắp xếp theo độ phù hợp giảm dần. Khi tìm kiếm người dùng quan tâm tới các kết quả trả về đầu tiên, việc xếp hạng đúng các thực thể vào 10 kết quả đầu tiên quan trọng hơn việc các xếp hạng sau đó. Do giới hạn thời gian làm thực nghiệm, nên tôi chỉ xây dựng tập dữ liệu học với 10 thực thể xếp hạng đầu tiên cho mỗi truy vấn. Cách xác định 10 thực thể đầu tiên: • Tìm kiếm thực thể với mô hình xếp hạng Impression (Cài đặt Impression với hàm p(s|γ) = 1 s ) để tìm các thực thể với các trang chứa thực thể tương ứng • Tìm kiếm thuốc với máy tìm kiếm thông thường (cài đặt Lucene với hàm xếp hạng BM25[63]) có được các trang tốt nhất theo đánh giá BM25. • Từ 2 kết quả trên, lựa chọn 10 thực thể tốt nhất và sắp xếp để được kết quả trả về "đúng" cần có. 3.3.3 Kết quả và đánh giá Kết quả có hàm tính hạng: rf(t) = 0.0010×N + 0.0011×G + 0.0120× L+ + 0.3305× SL+ 0.2953×GL + 0.3601×M CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 35 Bảng 3.2: So sánh MRR, MAP của BM25, Impression, LTR Phương pháp BM25 Impression LTR MRR 0.283 0.767 0.800 MAP 0.275 0.651 0.705 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 2 3 4 5 A v e ra g e P re ce si o n Query BM25 ER LTR Hình 3.9: So sánh độ chính xác trung bình AP trên 5 query Từ hàm tính hạng trên, cho ta thấy vai trò quan trọng của trọng số: M, SL và GL. Trọng số N, G ít quan trọng nhất, có thể bỏ qua - do giá trị N, G thường rất nhỏ, mà hệ số lại nhỏ nên thành phần đó không có ảnh hưởng lớn tới kết quả xếp hạng. Và trọng số L (cực đại trọng số cục bộ) có ít giá trị hơn trọng số SL (tổng trọng số cục bộ) Áp dụng hàm tính hạng vào mô-dul xếp hạng thực thể trong máy tìm kiếm, thực hiện tìm kiếm trên 5 query khác nhau để đánh giá. Bảng 3.2 so sánh MRR và MAP của ba phương pháp sử dụng Okapi BM25 để xếp hạng, với mô hình Impression của EntityRank trong phần trước và với mô hình học xếp hạng (gọi tắt LTR: Learn To Rank). Các nhận xét: • LTR và Impression có MRR, MAP hơn hẳn BM25, cho thấy việc tìm kiếm CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 36 thực thể trả lại kết quả tốt hơn cho người dùng. • MRR của LTR là 0.8 cao hơn của mô hình Impression bằng 0.767 (+0.023) chứng tỏ kết quả đúng đầu tiên của LTR trả về xuất hiện ở thứ hạng tốt hơn (thấp hơn) của Impression. • So sánh MAP cho thấy độ chính xác trung bình của LTR cũng cao hơn của Impression (+0.054). • Biểu đồ so sánh chi tiết độ chính xác trung bình AP trên từng truy vấn (hình 3.9) càng cho ta khẳng định phương pháp LTR đã học hàm tính hạng thực thể hiệu quả. 3.4 Tổng kết chương Qua phân tích một mô hình xếp hạng thực thể trong máy tìm kiếm thực thể [17, 18, 19], và học xếp hạng để học hàm tính hạng thực thể hiệu quả trên lĩnh vực tìm kiếm thực thể thuốc. Các kết quả thu được đã chứng minh vai trò và hiệu quả của học xếp hạng áp dụng vào máy tìm kiếm. C h ư ơ n g 4 Tạo nhãn cụm tài liệu Chương này giới thiệu các phương pháp tạo nhãn cụm tài liệu, và tự động tạo nhãn cho cây phân cấp tài liệu. 4.1 Giới thiệu Máy tìm kiếm ngày nay được sử dụng rộng rãi và trở thành một công cụ không thể thiếu của người dùng khi tìm kiếm thông tin trên môi trường web. Kết quả trả về của máy tìm kiếm cho mỗi truy vấn thường rất lớn (từ vài nghìn tới hàng triệu kết quả). Với cùng truy vấn nhưng mỗi người dùng khác nhau có thể có mong muốn khác nhau, ví dụ khi tìm kiếm "phân cụm" (cluster) có người quan tâm tới các phương pháp và thuật toán phân cụm nhưng có người lại quan tâm tới tính toán cụm. Để nâng cao chất lượng của máy tìm kiếm và giúp định hướng chủ đề cho người dùng, một nhu cầu đặt ra đó là phân cụm kết quả trả về của máy tìm kiếm 37 CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 38 giống như Vivisimo∗ hay Carrot†. Phân cụm không phải là lĩnh vực mới nhưng vấn đề phân cụm các kết quả trả về từ máy tìm kiếm được nhiều nhà khoa học quan tâm trong những năm gần đây, với các nghiên cứu về phân cụm để cải tiến chất lượng tìm kiếm web [65, 41, 31, 28, 27, 67]. Kết quả trả về của máy tìm kiếm được phân thành các tập nhỏ hơn, mỗi cụm này bao gồm các tài liệu tương tự nhau, khi đó các tài liệu trong một cụm sẽ cùng hướng tới một chủ đề chung nào đó. Mỗi cụm cần được tạo nhãn chủ đề giúp định hướng nội dung cho người dùng về các tài liệu thuộc cụm đó. Do đó việc tạo nhãn cho cụm tài liệu là một bài toán quan trọng, và nó cũng thể hiện chất lượng phân cụm tài liệu. Vấn đề tạo nhãn cho cụm tài liệu cũng được nhiều nhà khoa học [28, 42, 39, 38, 65, 5] quan tâm. Không chỉ tạo nhãn cho các kết quả trả về từ máy tìm kiếm, vấn đề tạo nhãn có thể được áp dụng để tạo nên các danh bạ web (Web directory) như Dmoz của ODP∗ hay Yahoo!Directory† mà hiện nay trong tiếng Việt có Zing‡ đang phát triển một danh bạ web. Và các trang web cũng thường được phân loại (category) và tổ chức thành cấu trúc cây phân loại như các trang tin tức (vietnamnet, vnexpress). Tất cả đều được tổ chức dạng cấu trúc cây phân cấp gọi là cây phân cấp chủ đề. Cách tổ chức dạng cây phân cấp khá phổ biến bởi nó biểu diễn thông tin ở các mức chi tiết khác nhau: từ đỉnh của cây càng đi xuống sâu hơn càng nhận được thông tin chi tiết hơn về chủ đề riêng giúp người dùng tiếp cận thông tin có định hướng và dễ dàng hơn. Mỗi đỉnh của cây phân cấp có một tập các tài liệu và có nhãn tương ứng về chủ để các tài liệu đó (cụm tài liệu). Ví dụ của báo vnexpress có: mục "Văn hóa" chứa các mục con "âm nhạc", "thời trang", "điện ảnh",... Mục tiêu của phân cấp tài liệu là để cải thiện khả năng cho người dùng hiển thị thông tin, vì vậy một cây tốt cần có mô tả tốt - tức có nhãn cụm tài liệu ở các đỉnh tốt. Dmoz[25] là cây phân cấp chủ đề Web lớn nhất đã được xây dựng và được tổ chức theo từng ngôn ngữ khác nhau Anh, Pháp, Nhật, Trung Quốc, Hàn Quốc,...chưa ∗http:/vivisimo.com † ∗ † ‡ CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 39 có tiếng Việt. Dmoz cung cấp cấu trúc phân cấp chủ đề cho các trang Web từ tổng quát tới chi tiết và được sử dụng trong tìm kiếm nâng cao của Google. Nhu cầu xây dựng cây phân cấp chủ đề Web tiếng Việt được đặt ra, nhằm mục đích hỗ trợ người dùng việc tìm kiếm theo từng chủ đề. Và Zing!Directory là một cây phân cấp chủ đề Web tiếng Việt đang được xây dựng. Với sự phát triển của các danh bạ web (tiếng Anh), C.Yang và J.Lin [60] năm 2007, T.C. Wu và W.L. Hsu [57] năm 2006 đã đưa ra hướng tích hợp các danh bạ web có sẵn để tạo một cây phân cấp chủ đề duy nhất, hỗ trợ người dùng tìm kiếm thông tin từ nhiều nguồn khác nhau. Kỹ thuật tích hợp cho phép mở rộng, sửa đổi cây phân loại bằng cách học cách tổ chức các tài liệu từ các cây nguồn để tạo cây mới [60], và dựa vào mô hình trường ngẫu nhiên (CRFs: Conditional Random Fields)[57]. Trong tiếng Việt, danh bạ web của trang tin tức việt nam§ là danh bạ trang web của các tổ chức đã đăng ký, hoạt động trong các lĩnh vực khác nhau và được cấu trúc dạng cây phân cấp chủ đề nhưng mới chỉ có chủ đề tới mức 3. Hay một số danh bạ web tiếng Việt khác như vnn777.com hướng các chủ đề về tin tức và giải trí, và các danh bạ đó chỉ có phân cấp cao nhất tới mức 3. Nên không đặt vấn đề tích hợp các danh bạ web cho tiếng Việt. Một câu hỏi đưa ra: làm thế nào tạo cây phân cấp chủ đề cho các trang web tiếng Việt giống như Dmoz? Qua các phân tích về phân cụm và tạo nhãn cụm tài liệu, một phương pháp khả thi đó là phân cụm phân cấp các trang web [1], sau đó xác định chủ đề cho từng cụm ở mỗi cấp. Vấn đề tạo nhãn cụm tài liệu có vai quan trọng trong cả bài toán phân cụm kết quả trả về của máy tìm kiếm và xây dựng cây phân cấp chủ đề. Nghiên cứu và đưa ra mô hình học tạo nhãn cho cụm tài liệu được đề cập trong các phần tiếp theo. 4.2 Phương pháp lựa chọn nhãn Trong tạo nhãn cụm phân cấp, giả thiết đã có sẵn một cây phân cấp tốt các cụm tài liệu và cần tạo mô tả tốt cho mỗi cụm tài liệu trên cây gọi là nhãn cụm. Nhãn cụm §httt://tintuc.vnn.vn/danhbaweb CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 40 có thể là cụm từ hoặc danh sách các từ, cụm từ nói lên chủ đề chung của cụm, ví dụ: cụm các tài liệu về xử lý ngôn ngữ tự nhiên có nhãn "xử lý ngôn ngữ tự nhiên" hoặc danh sách cụm từ "thẻ, ngôn ngữ, từ vựng, tạo nhãn, từ, cấu trúc, ngữ pháp". Danh sách các cụm từ thường ít hữu dụng hơn là một nhãn chủ đề bởi nó yêu cầu người dùng phải tự xác định khái niệm tương ứng. Tuy nhiên danh sách các cụm từ là lựa chọn phổ biến cho tạo nhãn tự động các cụm theo [53, 65, 42, 28]. Khái niệm nhãn cụm tốt: ko chỉ mô tả chủ đề chính được đề cập trong cụm các tài liệu mà còn phân biệt cụm đó với các cụm cùng cấp và cụm cha. Xác định nhãn duy nhất tốt cho một cụm tức chọn một từ/cụm từ xuất hiện trong các tài liệu thuộc cụm có ý nghĩa bao quát nội dung cho cụm đó là việc khó khả thi. Một ví dụ đơn giản như đã đưa ra ở trên: một cụm các tài liệu về xử lý ngôn ngữ tự nhiên, nhãn tốt cho cụm là "xử lý ngôn ngữ tự nhiên". Nhưng có thể trong các tài liệu thuộc cụm không tài liệu có chính xác cụm từ này, trong khi dễ dàng thấy sự xuất hiện nhiều của các từ "ngôn ngữ, từ vựng, corpus, tạo nhãn, cấu trúc, ngữ pháp". Do vậy nhãn được tạo thường là danh sách các từ có khả năng làm nhãn cao được lựa chọn. Tuy nhiên, số lượng nhãn khả năng được lựa chọn cần vừa đủ, vì nếu quá nhiều sẽ gây nhiễu, khó hiểu cho người dùng nhưng nếu quá ít (ví dụ một từ "cấu trúc"), nhãn trở thành trừu tượng và cũng khó hiểu với người dùng. P.Treeratpituk và J.Callan [53] đưa ra phương pháp xác định nhãn cho mỗi cụm: là danh sách các nhãn khả năng được xếp hạng theo độ phù hợp với cụm và đưa ra cách xác định số lượng nhãn phù hợp vì danh sách nhãn này nên ngắn nhất có thể để mô tả chủ đề của cụm. Vì vậy tạo nhãn cụm tài liệu là xác định các nhãn khả năng và xếp hạng chúng theo độ phù hợp làm nhãn cho cụm giảm dần. Sau đó chọn một số lượng nhất định nhãn khả năng đầu tiên làm nhãn cho cụm tài liệu đó. Theo [53], Popescul sử dụng phương pháp thống kê để lựa chọn nhãn dựa trên ngữ cảnh của các cụm liên quan (cụm cha và các cụm con cùng cấp): loại bỏ các cụm từ có xác suất xuất hiện như nhau ở các cụm khác nhau. Do đó các từ đồng thời xuất hiện ở nhiều cụm không được lựa chọn làm nhãn, tránh trường hợp nhãn quá tổng quát. Và Glover [29] phân tích tần số xuất hiện của các từ đơn có thể dự đoán nhãn cho các cụm, với nhận định một từ phổ biết trong cụm và ít quan hệ với CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 41 các cụm khác thì là đặc trưng tốt cho cụm. Các từ/cụm từ (gọi chung là cụm từ) được ứng cử làm nhãn cụm được chọn dựa vào tiêu chuẩn: Candidates = { p ∣∣DFC |C| < maxColPos & DFS |S| > minSelfPos } Trong đó: • DFC : số tài liệu trong cả tất cả các cụm tài liệu mà chứa cụm từ p • DFS: số tài liệu trong cụm đang xét có chứa cụm từ p • |C|, |S|: lần lượt số tài liệu của tất cả các cụm và của cụm đang xét. • maxColPos, minSelfPos : ngưỡng tần suất xuất hiện lớn nhất, nhỏ nhất của các nhãn được chọn. Những từ được chọn để có thể làm nhãn có tính chất xuất hiện hơn minSelPos lần, và nhỏ hơn maxColPos lần ở mỗi tài liệu trong cụm. Sau đó các nhãn khả năng p này được xếp hạng theo DFS. Phương pháp của Glover đơn giản nhưng còn hạn chế: cần xác định giá trị ngưỡng và tối ưu ngưỡng đó cho mọi cụm, khi xếp hạng dựa theo DFS dễ dàng thấy các từ đơn thường có hạng tốt hơn trong khi các cụm từ thường mang ý nghĩa cao hơn khi làm nhãn. Filippo Geraci và các cộng sự [28] sử dụng độ đo Information Gain để chọn các từ "giàu thông tin nhất" trong cụm làm nhãn. Dawn.J.Lawrie và W.Bruce Croft [39] xây dựng mô hình thống kê để xác định các từ chủ đề cho mỗi cụm (dùng độ đo Kullback–Leibler). Các phương pháp này dựa vào phân phối của các từ, cụm từ trên các cụm để lựa chọn các nhãn ứng viên cho mỗi cụm. P.Treeratpituk và J.Callan [52] đã đưa ra thuật toán tự động tạo nhãn cụm tài liệu dựa vào học xếp hạng, và trong phương pháp phân cụm của H.Zeng và Q.He [65] cũng sử dụng học xếp hạng các cụm từ làm nhãn. CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 42 4.3 Học xếp hạng nhãn cụm Nhãn của cụm tài liệu là các từ, cụm từ được xác định từ các tài liệu thuộc cụm. Tất cả các từ, cụm từ đều có khả năng làm nhãn, cần tìm nhãn tốt nhất có thể, đó là bài toán xếp hạng nhãn cụm. Với S là cụm đang xét, có cụm cha là P: bao gồm tất cả tài liệu của cụm S và các cụm cùng cấp với S, thuật toán chọn nhãn cho cụm S được P.Treeratpituk và J.Callan trong [52] đưa ra gồm 4 bước như sau: 1. Thống kê tất cả các cụm từ: 1-3 gram (gram trong tiếng Việt có thể hiểu là tiếng) trong cụm S, tính tần số xuất hiện của cụm từ trong mỗi tài liệu, trong cụm đang xét, cụm cha và trên tập dữ liệu chung (corpus E). 2. Chọn các nhãn khả năng: Chọn tập ứng cử từ các cụm trên dựa vào tần số xuất hiện của tài liệu trong cụm và trong ngôn ngữ. 3. Tính trọng số DScore cho mỗi ứng cử làm nhãn trên và sắp xếp theo trọng số đó. 4. Tính điểm cắt: Quyết định bao nhiêu ứng cử được chọn dựa trên DScore. Với mỗi cụm từ p, và cụm tài liệu C, ký hiệu DFC là số tài liệu trong cụm C có chứa cụm từ p, và TFC là số lần xuất hiện của p trong tất cả các tài liệu của cụm C. Ngoài ra, các tác giả còn dựa vào một tập dữ liệu chung (corpus E) để xác định độ phổ biến của các cụm từ trong ngôn ngữ đang xét (tiếng Anh), những từ xuất hiện với tần suất hơn 20% trong E gọi là từ dừng và sẽ không được xét làm nhãn. Không phải tất cả các cụm từ đều được chọn, chỉ những từ 1-gram xuất hiện ở ít nhất 20% tài liệu trong cụm và những từ 2,3-gram xuất hiện ở ít nhất 5% tài liệu trong cụm mới được coi là mô tả tốt và được chọn là nhãn ứng viên. 4.3.1 Các đặc trưng Hàm xếp hạng có ý nghĩa xác định khả năng là một nhãn của cụm từ với một cụm tài liệu xác định, và là một hàm của các đặc trưng của cụm từ. Với mỗi cụm từ p, CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 43 P.Treeratpituk và J.Callan [52] xác định các đặc trưng: nDFC tỷ lệ của số tài liệu trong cụm C chứa cụm từ trên tổng số tài liệu trong cụm C đó. Một cụm từ có khả năng mô tả tốt nếu xảy ra tương đối thường xuyên ở cụm cha P nhưng rất thường xuyên ở cụm đang xét S. nDFC = DFC |C| TFIDF là độ đo tương tự của tích tần số và nghịch đảo tần số xuất hiện được xác định bởi công thức: TFIDFC = TFC ∗ log |C| DFC r(TFIDF), r(nDF) thứ hạng của TFIDF, nDF trong sắp xếp giảm dần. Sử dụng r(TFIDF), r(nDF) có thể đem lại ý nghĩa cao hơn khi so sánh các giá trị thực TFIDF, nDF. Boost Rank nDF : độ đo về tính gia tăng của nDF . Một mô tả tốt cần có nDFP khá cao, nDFS cao hơn. Để xác định tính chất này sử dụng độ đo về tính gia tăng log[r(DFp/|p|]− log[r(DFs/|S|)] Công thức trên xác định độ thay đổi hạng nDF của cụm từ ở cụm cha với cụm đang xét, và hạng nDF được tính log bởi những thay đổi thứ hạng càng ở phần đầu (top rank) thì càng có ý nghĩa. Ví dụ: một nhãn mà thay đổi từ thứ hạng thứ 200 trong cụm cha tới thứ 100 trong cụm con thì khả năng mô tả ít hơn nhãn có thứ hạng 100 ở cụm cha và thứ hạng ở cụm con là 5. Boost Rank TFIDF độ đo về tính gia tăng của TFIDF . Một cụm từ là mô tả tốt thì cần có thứ hạng TFIDF cao hơn trong cụm con so với ở cụm cha. Độ đo được xác định: log[r(TFIDFp)]− log[r(TFIDFs)] LEN độ dài của cụm từ p. LEN càng lớn càng tốt, do ưu tiên các cụm từ dài hơn làm nhãn. CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 44 H.Zeng và Q.He [65] cũng chọn độ đo TFIDF và LEN như P.Treeratpituk và J.Callan đã đưa ra làm các đặc trưng của cụm từ, và ngoài ra còn có một số đặc trưng về xác định cụm như độ co cụm của các tài liệu chứa cụm từ (Intra-cluster similarity ICS). Do H.Zeng và Q.He sử dụng phương pháp xếp hạng cụm từ để tiến hành phân cụm tài liệu nên đã sử dụng các độ đo đó để xác định các tài liệu thuộc cùng cụm. Và trong ngữ cảnh của chúng ta, không cần thiết xét tới các độ đo cụm đó. Kết hợp giá trị các đặc trưng bằng hàm tuyến tính gọi là hàm DScore- mô tả một cụm từ có khả năng tạo nhãn cho cụm S như thế nào với cụm cha P theo công thức: DScorep = m∑ i=1 (αi × fi(p)) + α0 Với fi(p) là đặc trưng thứ i của cụm từ p, m là số đặc trưng. Sau đó các nhãn được sắp xếp theo DScore nên được gọi là hàm tính hạng. 4.3.2 Học hàm tính hạng Hàm DScore với các trọng số αi của các đặc trưng được P.Treeratpituk và J.Callan ước lượng dựa vào phương pháp quy hồi tuyến tính. Ước lượng DScore∗ của nhãn L được xác định dựa vào việc so sánh độ tương đồng của nhãn đó với nhãn đúng CL đã được cho trong dữ liệu học, DScore∗ được tính bỏi ước lượng nhãn L với nhãn đúng là CL: DScore∗L = max SL∈Synonym(L) overlap(SL,CL) max (len(SL), len(CL)) Trong đó, overlap(SL,CL) là số các từ mà xuất hiện trong cả SL và CL, và len(x) là độ dài của x, Synonym(L) là hàm xác định các cụm từ đồng nghĩa với L. Nếu nhãn được chọn đồng nghĩa của nhãn đúng thì DScore=1 và ngược lại DScore =0. Mỗi cụm được xác định một nhãn đúng duy nhất CL, trong khi thực tế có thể có một số nhãn cùng tốt như nhau. Để xử lý trường hợp này, hàm ước lượng đã sử dụng hàm xác định từ đồng nghĩa, để xác định các nhãn tốt là các nhãn đồng nghĩa với nhãn đúng. Tuy nhiên vẫn còn nhiều trường hợp lỗi- nhãn tốt có DScore = 0, ví CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 45 dụ: cụm tài liệu có nhãn đúng "cardiovascular disorder" (rối loạn tim), thuật toán đưa ra các nhãn cho cụm là "heart" và "heart disease" (bệnh tim). Với chúng ta, trong trường hợp này nhãn "heart" và "heart disease" là hoàn toàn phù hợp nhưng với đánh giá tự động trên thì nhãn này bị bỏ qua bởi "cardiovascular" và "heart" không thực sự đồng nghĩa. Phương pháp học hàm xếp hạng RankingSVM[34] được tôi lựa chọn học hàm xếp hạng nhãn tài liệu. Đây là phương pháp học ghép cặp, dữ liệu học các đối tượng là nhãn cần được sắp xếp theo độ phù hợp giảm dần. Số lượng cụm từ được chọn làm nhãn cho cụm chỉ nên có từ 3 tới 5 cụm từ được xác định trong [52, 28] nên dữ liệu học: mỗi cụm tài liệu với các nhãn ứng viên được sắp xếp theo độ phù hợp giảm dần. Đặc biệt cần đảm bảo 5 nhãn đầu tiên là 5 nhãn tốt nhất và thứ tự sắp xếp 5 nhãn này có thể chỉ là tương đối - khi các nhãn đều phù hợp làm nhãn tốt nhất ví dụ: "giáo dục" với "dạy học" hay "công nghệ", "thông tin" và "tin học". 4.4 Thực nghiệm 4.4.1 Nguồn dữ liệu Trên wikipedia tiếng Việt¶ các trang web được xác định chủ đề, và mỗi chủ đề có trang web tương ứng tên chủ đề chứa thông tin các chủ đề con của chủ đề đó nếu có. Ví dụ: chủ đề "dược khoa" gồm có các chủ đề con ("dược phẩm", "dược điển", "công ty dược"). Do đó ta dễ dàng xây dựng cấu trúc phân cấp chủ đề của các trang web trên wikipedia. Mỗi chủ đề được coi là một cụm các tài liệu thuộc chủ đề đó. Tiến hành thu thập (crawl) các trang web của wikipedia tiếng Việt: • 5280 trang web • 15 chủ đề mức 1 (mức 0 là gốc) • 870 chủ đề các mức ¶ CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 46 • Độ sâu phân cấp cây chủ đề: 5 mức (ví dụ: 1. Địa chất học | 2. Niên đại địa chất| 3. Liên đại Hiển Sinh | 4. Đại Cổ Sinh | 5. Kỷ Cambri) Các trang web được lọc bỏ thẻ html, lấy nội dung chính và cho đi qua modul thống kê ngram [32] (thực hiện thống kê 1-gram, 2-gram, 3-gram). 4.4.2 Dữ liệu học Lấy một phần dữ liệu cây phân cấp chủ đề của wikipedia trên để tạo nhãn cho các cụm (dựa trên chủ đề của cụm được wiki xác định): 1. Các cụm có chủ đề rõ ràng dễ phân tách- các chủ đề mức 1 của cây phân cấp chủ đề của wikipedia: 232 trang web, 8 cụm mức 1 và 5 cụm mức 2 (bảng A.1). 2. Các cụm chủ đề gần nhau ở mức 2 của cây phân cấp wikipedia: chủ đề giáo dục gồm 6 cụm con và 75 trang web (bảng A.2). 3. Các cụm thuộc chủ đề "động vật học" được chọn làm dữ liệu đánh giá: động vật học gồm 8 cụm con và 76 trang web (bảng A.3). Mỗi cụm trong dữ liệu học được xác định danh sách các nhãn ứng viên (có khả năng làm nhãn) dựa vào giới hạn nDFC lớn hơn 20%. Tuy nhiên do một số cụm trong wiki có số lượng tài liệu ít (nhỏ hơn 10), khi đó nDFC được xác định phải lớn hơn 40% Sau khi có danh sách nhãn ứng viên, tiến hành sắp xếp các nhãn ứng viên theo độ phù hợp giảm dần (đặc biệt quan trọng cần xác định 5 nhãn đầu tiên tốt nhất), rồi thực hiện tính các giá trị đặc trưng để tạo dữ liệu học đưa vào mô-dul học hàm xếp hạng của SVM light ‖. ‖ CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 47 Các đặc trưng được xác định đưa vào hàm học lần lượt: f1 = LEN f2 = r(nDFS) f3 = r(nDFP ) f4 = r(TFIDFS) f5 = r(TFIDFP ) f6 = log(r(nDFP )− log(r(nDFS)) f7 = log(r(TFIDFP )− log(r(TFIDFS)) Trong thực nghiệm, P.Treeratpituk và J.Callan chỉ sử dụng 6 đặc trưng f2 tới f7, và bỏ qua một đặc trưng rất quan trọng là độ dài LEN của cụm từ được chọn. 4.4.3 Kết quả và đánh giá Hàm xếp hạng thu được: RF (p) = 0.0150× LEN(p)+ + 0.0210× r(nDFS)+ − 0.0011× r(nDFP )+ + 0.2470× r(TFIDFS)+ − 0.0524× r(TFIDFP )+ + 0.1932× [log(r(nDFP )− log(r(nDFS))]+ + 0.5713× [log(r(TFIDFP )− log(r(TFIDFS))] Sau khi có được hàm xếp hạng, tiến hành tạo nhãn cho cụm dữ liệu kiểm tra (chủ đề "động vật"). Kết quả tạo nhãn cụm tài liệu được tiến hành đánh giá so sánh với phương pháp của Glover (chỉ dựa vào xác định ngưỡng tần suất xuất hiện) đã được trình bày ở trên. Các độ đo đánh giá chất lượng tạo nhãn: • Match@N: số nhãn đúng ở N nhãn đầu tiên CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 48 • MRR: Là trung bình của nghịch đảo thứ hạng nhãn đúng đầu tiên. • MTRR: Nếu có hơn một nhãn đúng, MTRR là trung bình của tổng nghịch đảo thứ hạng của tất cả nhãn đúng. Bảng 4.1 so sánh độ đo MRR và MTRR giữa phương pháp của Glover và phương pháp sử dụng hàm RF(p), cho thấy với hàm RF kết quả xếp hạng cụm từ để tạo nhãn có chất lượng tốt hơn. Với MRR, MTRR cao hơn chứng tỏ các nhãn đúng xuất hiện ở thứ hạng nhỏ hơn (ở hạng đầu). Bảng 4.2 so sánh về số nhãn trung bình Bảng 4.1: So sánh MRR, MTRR MRR MTRR Glover 0.51 0.57 RF 0.69 0.90 phù hợp ở N hạng đầu tiên, cho thấy các nhãn đúng thường được xác định ở hạng 1, 2. Với kết quả này cho thấy hiệu quả của việc học hàm xếp hạng, cho chúng ta Bảng 4.2: So sánh Match@N Match@N N=1 N=2 N=3 N=4 Glover 0.29 0.43 0.57 1.00 RF 0.43 1.00 1.00 1.00 hàm xết hạng tốt hơn. 4.5 Tổng kết chương Xếp hạng các nhãn ứng viên để tạo nhãn cụm tài liệu là một trong các ứng dụng của học xếp hạng đối tượng, cụ thể đối tượng ở đây là "nhãn" của cụm tài liệu. Với kết quả đạt được của chất lượng tạo nhãn, cho ta cơ sở để xây dựng cây phân cấp chủ đề web cho các trang web tiếng Việt một cách tự động. KẾT LUẬN Học xếp hạng là một lĩnh vực đang rất được quan tâm. Vấn đề xác định hạng của các đối tượng mà cụ thể trong máy tìm kiếm là các trang web và các thực thể có một vai trò quan trọng bởi nó giúp định hướng, chỉ dẫn người dùng đến với những thông tin phù hợp theo nhu cầu. Bên cạnh đó cùng sự phát triển của các phương pháp phân cụm, đặt ra vấn đề gán nhãn cụm tài liệu nhằm hỗ trợ người dùng tiếp cận kết quả phân cụm và định hướng tạo cây phân cấp chủ đề web tiếng Việt. Luận văn này đã tiếp cận vấn đề học xếp hạng và nghiên cứu, đưa ra mô hình, áp dụng vào máy tìm kiếm để nâng cao chất lượng của máy tìm kiếm. Luận văn đã đạt được những kết quả: • Phân tích các vấn đề thời sự nhất về bài toán xếp hạng, trình bày các phương pháp học xếp hạng trong vài năm gần đây. • Đưa ra mô hình học xếp hạng thực thể và thực nghiệm tìm kiếm thực thể trong lĩnh vực y tế - cụ thể là thuốc trong tiếng Việt. • Mô-dul tạo nhãn cụm tài liệu có ứng dụng không chỉ trong máy tìm kiếm mà còn trong việc tạo tạo danh bạ web (web directory). 49 Các công trình công bố của tác giả [TTT08 ]Nguyen, C.-T., Nguyen, T.-T., Ha, Q.-T., Phan, X.-H., and Horiguchi,S. Web Search Clustering and Labeling with Hidden Topics. Journal of ACM Transaction on Asian Language Information Processing (ACM- TALIP), 2008. (TALIP-08-0036, Resubmit after reviewed). [CTT08 ] Nguyễn Thi Thu Chung, Nguyễn Thu Trang, Nguyễn Cẩm Tú, Hà Quang Thụy. Đánh giá chất lượng phân cụm trên máy tìm kiếm tiếng Việt VNSEN Kỷ yếu Hội thảo Quốc gia Một số vấn đề chọn lọc về Công nghệ thông tin và Truyền thông lần thứ XI. (Huế, 12-13/6/2008 2008), [TNT06 ] Q.Ha, T., H.Nguyen, N., and T.Nguyen, T. Improve Performance of PageRank Computation with Connected-Component PageRank. Interna- tional Journal of Natural Sciences and Technology, 1(1):53-60, 2006. [NNT05 ]Đỗ Thị Diệu Ngọc, Nguyễn Hoài Nam, Nguyễn Thu Trang, Nguyễn Yến Ngọc Giải pháp tính hạng trang modified adaptive pagerank trong máy tìm kiếm. Chuyên sang "Các công trình nghiên cứu về CNTT và truyền thông". Tạp chí Bưu chính Viễn thông, 14: 65-71, 4-2005 50 Tài liệu tham khảo [1] Adami, G., Avesani, P., and Sona, D. Clustering documents in a web directory. In WIDM ’03: Proceedings of the 5th ACM international workshop on Web information and data management (New York, NY, USA, 2003), ACM, pp. 66–73. [2] Agarwal, A., Chakrabarti, S., and Aggarwal, S. Learning to rank networked entities. In KDD ’06: Proceedings of the 12th ACM SIGKDD inter- national conference on Knowledge discovery and data mining (New York, NY, USA, 2006), ACM, pp. 14–23. [3] Aguillo, I., Ortega, J. L. L., and Fernandez, M. Webometric ranking of world universities: Introduction, methodology, and future developments. Higher Education in Europe 33, 2-3 (July 2008), 233–244. [4] Aguillo, I. F. Webometrics ranking of world universities. In 3rd Meeting of the International Rankings Expert Group (IREG-3), (2007), Shanghai Jiao Tong University. [5] Amini, M. R., Usunier, N., and Gallinari, P. Automatic text summa- rization based on word clusters and ranking algorithms. In In Proceedings of the 27 th European Conference on Information Retrieval (2005), pp. 142–156. [6] Arasu, A., Cho, J., Garcia-Molina, H., Paepcke, A., and Raghavan, S. Searching the web. ACM Trans. Interet Technol. 1, 1 (2001), 2–43. 51 TÀI LIỆU THAM KHẢO 52 [7] Balmin, A., Hristidis, V., and Papakonstantinou, Y. Objectrank: authority-based keyword search in databases. In VLDB ’04: Proceedings of the Thirtieth international conference on Very large data bases (2004), VLDB Endowment, pp. 564–575. [8] Burges, C. Learning to rank for web search: Some new directions. Keynote talk at SIGIR Ranking Workshop, 7 2007. [9] Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamil- ton, N., and Hullender, G. Learning to rank using gradient descent. In ICML ’05: Proceedings of the 22nd international conference on Machine learn- ing (New York, NY, USA, 2005), ACM, pp. 89–96. [10] Burges, C. J. C., Ragno, R., and Le, Q. V. Learning to rank with non- smooth cost functions. In NIPS (2006), B. Scho¨lkopf, J. C. Platt, T. Hoffman, B. Scho¨lkopf, J. C. Platt, and T. Hoffman, Eds., MIT Press, pp. 193–200. [11] Cao, Y., Xu, J., Liu, T.-Y., Li, H., Huang, Y., and Hon, H.-W. Adapt- ing ranking svm to document retrieval. In SIGIR ’06: Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval (New York, NY, USA, 2006), ACM, pp. 186–193. [12] Cao, Z., Qin, T., Liu, T.-Y., Tsai, M.-F., and Li, H. Learning to rank: from pairwise approach to listwise approach. In ICML ’07: Proceedings of the 24th international conference on Machine learning (New York, NY, USA, 2007), ACM, pp. 129–136. [13] Chakrabarti, S. Dynamic personalized pagerank in entity-relation graphs. In WWW ’07: Proceedings of the 16th international conference on World Wide Web (New York, NY, USA, 2007), ACM, pp. 571–580. [14] Chakrabarti, S. Learning to rank in vector spaces and social networks. In WWW ’07: Tutorial - 16th international conference on World Wide Web (2007). [15] Chakrabarti, S., and Agarwal, A. Learning parameters in entity rela- tionship graphs from ranking preferences. In PKDD (2006), pp. 91–102. TÀI LIỆU THAM KHẢO 53 [16] Chakrabarti, S., Khanna, R., Sawant, U., and Bhattacharyya, C. Structured learning for non-smooth ranking losses. In KDD ’08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining (New York, NY, USA, 2008), ACM, pp. 88–96. [17] Cheng, T., and Chang, K. C.-C. Entity search engine: Towards agile best- effort information integration over the web. In CIDR (2007), pp. 108–113. [18] Cheng, T., Yan, X., and Chang, K. C.-C. Entityrank: searching entities directly and holistically. In VLDB ’07: Proceedings of the 33rd international conference on Very large data bases (2007), VLDB Endowment, pp. 387–398. [19] Cheng, T., Yan, X., and Chang, K. C.-C. Supporting entity search: a large-scale prototype search engine. In SIGMOD ’07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data (New York, NY, USA, 2007), ACM, pp. 1144–1146. [20] Chu, W., and Keerthi, S. S. New approaches to support vector ordinal regression. In In ICML ’05: Proceedings of the 22nd international conference on Machine Learning (2005), pp. 145–152. [21] Cohen, W. W., Schapire, R. E., and Singer, Y. Learning to order things. In NIPS ’97: Proceedings of the 1997 conference on Advances in neural information processing systems 10 (Cambridge, MA, USA, 1998), MIT Press, pp. 451–457. [22] Collins, M., Schapire, R. E., and Singer, Y. Logistic regression, ad- aboost and bregman distances. In Machine Learning (2000), pp. 158–169. [23] Demartini, G., Firan, C. S., Iofciu, T., Krestel, R., and Nejdl, W. A model for ranking entities and its application to wikipedia. Web Congress, Latin American 0 (2008), 29–38. [24] Demartini, G., Firan, C. S., Iofciu, T., and Nejdl, W. Semantically enhanced entity ranking. In WISE ’08: Proceedings of the 9th international con- ference on Web Information Systems Engineering (Berlin, Heidelberg, 2008), Springer-Verlag, pp. 176–188. TÀI LIỆU THAM KHẢO 54 [25] Dmoz. [26] Duh, K., and Kirchhoff, K. Learning to rank with partially-labeled data. In SIGIR ’08: Proceedings of the 31st annual international ACM SIGIR con- ference on Research and development in information retrieval (New York, NY, USA, 2008), ACM, pp. 251–258. [27] Gelgi, F., Davulcu, H., and Vadrevu, S. Term ranking for clustering web search results. In WebDB (2007). [28] Geraci, F., Pellegrini, M., Maggini, M., and Sebastiani, F. Cluster generation and cluster labelling for web snippets: A fast and accurate hierar- chical solution. In SPIRE (2006), pp. 25–36. [29] Glover, E., Pennock, D. M., Lawrence, S., and Krovetz, R. Infer- ring hierarchical descriptions. In CIKM ’02: Proceedings of the eleventh in- ternational conference on Information and knowledge management (New York, NY, USA, 2002), ACM, pp. 507–514. [30] Herbrich, R., Graepel, T., and Obermayer, K. Support vector learn- ing for ordinal regression. In In International Conference on Artificial Neural Networks (1999), pp. 97–102. [31] Jiang, Z., Joshi, A., Krishnapuram, R., and Yi, L. Retriever: Improv- ing Web Search Engine Results Using Clustering. Tech. rep., University of Maryland Baltimore County, October 2000. [32] JNSP. [33] Joachims, T. Making large-scale support vector machine learning practical. Advances in kernel methods: support vector learning (1999), 169–184. [34] Joachims, T. Optimizing search engines using clickthrough data. In KDD ’02: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining (New York, NY, USA, 2002), ACM, pp. 133–142. TÀI LIỆU THAM KHẢO 55 [35] Joachims, T. A support vector method for multivariate performance mea- sures. In Proceedings of the 22nd International Conference on Machine Learn- ing (2005), ACM Press, pp. 377–384. [36] Joachims, T., Li, H., Liu, T.-Y., and Zhai, C. Learning to rank for information retrieval (lr4ir 2007). SIGIR Forum 41, 2 (2007), 58–62. [37] Klementiev, A., Roth, D., and Small, K. An unsupervised learning algorithm for rank aggregation. Machine Learning: ECML 2007 (2007), 616– 623. [38] Lawrie, D., Croft, W. B., and Rosenberg, A. Finding topic words for hierarchical summarization. In SIGIR ’01: Proceedings of the 24th annual inter- national ACM SIGIR conference on Research and development in information retrieval (New York, NY, USA, 2001), ACM, pp. 349–357. [39] Lawrie, D. J., and Croft, W. B. Generating hierarchical summaries for web searches. In SIGIR ’03: Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval (New York, NY, USA, 2003), ACM, pp. 457–458. [40] Liu, T.-Y. Learning to rank in information retrieval. In WWW ’08: Tutorial - 17th international conference on World Wide Web (2008). [41] Mecca, G., Raunich, S., and Pappalardo, A. A new algorithm for clus- tering search results. Data Knowl. Eng. 62, 3 (2007), 504–522. [42] Mei, Q., Shen, X., and Zhai, C. Automatic labeling of multinomial topic models. In KDD ’07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (New York, NY, USA, 2007), ACM, pp. 490–499. [43] Page, L., Brin, S., Motwani, R., and Winograd, T. The pagerank citation ranking: Bringing order to the web. Tech. rep., Stanford University, 1998. TÀI LIỆU THAM KHẢO 56 [44] Qin, T., Liu, T.-Y., Zhang, X.-D., Wang, D.-S., Xiong, W.-Y., and Li, H. Learning to rank relational objects and its application to web search. In WWW ’08: Proceeding of the 17th international conference on World Wide Web (New York, NY, USA, 2008), ACM, pp. 407–416. [45] Radlinski, F., and Joachims, T. Active exploration for learning rankings from clickthrough data. In KDD ’07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (New York, NY, USA, 2007), ACM, pp. 570–579. [46] Raykar, V. C., Duraiswami, R., and Krishnapuram, B. A fast algo- rithm for learning a ranking function from large-scale data sets. IEEE Trans. Pattern Anal. Mach. Intell. 30, 7 (2008), 1158–1170. [47] Rode, H., Serdyukov, P., Hiemstra, D., and Zaragoza, H. Entity ranking on graphs: Studies on expert finding. Tech. Rep. TR-CTIT-07-81, University of Twente, 2007. [48] Sciencegateway. [49] SIGIR. on LR4IR. [50] Taylor, M., Guiver, J., Robertson, S., and Minka, T. Softrank: op- timizing non-smooth rank metrics. In WSDM ’08: Proceedings of the interna- tional conference on Web search and web data mining (New York, NY, USA, 2008), ACM, pp. 77–86. [51] Thom, J. A., Pehcevski, J., and Vercoustre, A.-M. Use of wikipedia categories in entity ranking. CoRR abs/0711.2917 (2007). [52] Treeratpituk, P., and Callan, J. Automatically labeling hierarchical clusters. In dg.o ’06: Proceedings of the 2006 international conference on Digital government research (New York, NY, USA, 2006), ACM, pp. 167–176. [53] Treeratpituk, P., and Callan, J. An experimental study on automat- ically labeling hierarchical clusters using statistical features. In SIGIR ’06: TÀI LIỆU THAM KHẢO 57 Proceedings of the 29th annual international ACM SIGIR conference on Re- search and development in information retrieval (New York, NY, USA, 2006), ACM, pp. 707–708. [54] Vercoustre, A.-M., Thom, J. A., and Pehcevski, J. Entity ranking in wikipedia. In SAC ’08: Proceedings of the 2008 ACM symposium on Applied computing (New York, NY, USA, 2008), ACM, pp. 1101–1106. [55] Webometrics. [56] WISDM. [57] Wu, T. C.-W., and Hsu, W.-L. Web directory integration using conditional random fields. In WI ’06: Proceedings of the 2006 IEEE/WIC/ACM Interna- tional Conference on Web Intelligence (Washington, DC, USA, 2006), IEEE Computer Society, pp. 540–543. [58] Xu, J., and Li, H. Adarank: a boosting algorithm for information retrieval. In SIGIR ’07: Proceedings of the 30th annual international ACM SIGIR con- ference on Research and development in information retrieval (New York, NY, USA, 2007), ACM, pp. 391–398. [59] Xu, Y., and Fern, A. On learning linear ranking functions for beam search. In ICML ’07: Proceedings of the 24th international conference on Machine learning (New York, NY, USA, 2007), ACM, pp. 1047–1054. [60] Yang, C. C., and Lin, J. Integrating web directories by learning their structures. In WWW ’07: Proceedings of the 16th international conference on World Wide Web (New York, NY, USA, 2007), ACM, pp. 1239–1240. [61] Yu, H. Svm selective sampling for ranking with application to data retrieval. In KDD ’05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining (New York, NY, USA, 2005), ACM, pp. 354–363. TÀI LIỆU THAM KHẢO 58 [62] Yue, Y., Finley, T., Radlinski, F., and Joachims, T. A support vector method for optimizing average precision. In ACM Conference on Research and Development in Information Retrieval (SIGIR) (2007), pp. 271–278. [63] Zaragoza, H., and Robertson, S. The probabilistic relevance model: Bm25 and beyond, 2007. [64] Zaragoza, H., Rode, H., Mika, P., Atserias, J., Ciaramita, M., and Attardi, G. Ranking very many typed entities on wikipedia. In CIKM ’07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management (New York, NY, USA, 2007), ACM, pp. 1015–1018. [65] Zeng, H.-J., He, Q.-C., Chen, Z., Ma, W.-Y., and Ma, J. Learning to cluster web search results. In SIGIR ’04: Proceedings of the 27th annual inter- national ACM SIGIR conference on Research and development in information retrieval (New York, NY, USA, 2004), ACM, pp. 210–217. [66] Zheng, Z., Chen, K., Sun, G., and Zha, H. A regression framework for learning ranking functions using relative relevance judgments. In SIGIR ’07: Proceedings of the 30th annual international ACM SIGIR conference on Re- search and development in information retrieval (New York, NY, USA, 2007), ACM, pp. 287–294. [67] Zhu, D., and Dreher, H. Improving web search by categorization, cluster- ing, and personalization. In ADMA ’08: Proceedings of the 4th international conference on Advanced Data Mining and Applications (Berlin, Heidelberg, 2008), Springer-Verlag, pp. 659–666. [68] Zhu, J., Song, D., and Ru¨ger, S. Integrating document features for entity ranking. Focused Access to XML Documents: 6th International Workshop of the Initiative for the Evaluation of XML Retrieval, INEX 2007 Dagstuhl Castle, Germany, December 17-19, 2007. Selected Papers (2008), 336–347. P h ụ l ụ c A Dữ liệu A.1 Dữ liệu tìm kiếm thuốc Tập nhân các trang web để thu thập dữ liệu cho tìm kiếm thực thể thuốc: 1. 2. 3. pham/giathuoc/Index.htm 4. pham/Thuoc goc/Thuocgoc1.asp 5. pham/Phan loai thuoc/Phanloaithuoc.asp 6. pham/Thongbao/index.asp 7. pham/Danhmucthuoc/index.asp 8. Pham.html 59 PHỤ LỤC A. DỮ LIỆU 60 9. 10. 11. 12. 13. 14. 15. A.2 Cây wiki Cây phân mục được lấy từ vn.wikipedia.com Nhãn Số tài liệu trong cụm Cong nghe thong tin (36) Internet (35) Sinh hoa hoc (14) Sinh hoc (61) Sinh hoc phan tu (27) Te bao hoc (23) Tin sinh hoc (12) Duoc pham (20) Bảng A.1: Dữ liệu học: cụm mức 1 PHỤ LỤC A. DỮ LIỆU 61 Nhãn Số tài liệu trong cụm Dai hoc (20) Mon hoc (6) Truong trung hoc (14) Hoc vi (24) Phuong phap giao duc (3) Tu duy (8) Bảng A.2: Dữ liệu học - cụm chủ đề giáo dục Nhãn Số tài liệu trong cụm lop thu (13) ho trau bo (10) dong vat thuan hoa (8) dong vat nguyen sinh (5) dong vat ky sinh (2) bo se (31) bo ca da tron (7) Bảng A.3: Dữ liệu kiểm tra - cụm chủ đề động vật học Nhãn Số tài liệu trong cụm Cong nghe thong tin (778) Internet (210) Sinh hoa hoc (14) Sinh hoc (1283) Sinh hoc phan tu (27) Te bao hoc (23) Tin sinh hoc (12) Duoc khoa (25) Y hoc (13) Vien thong (23) Thuc vat hoc (6) Khoa hoc suc khoe (4) Dong vat hoc (339) Giao duc (2457) Bảng A.4: Dữ liệu wiki đầy đủ mức 1 Danh sách hình vẽ 2.1 Xếp hạng với SVM [34] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Xác định ngưỡng phân thứ hạng [20] . . . . . . . . . . . . . . . . . . . . 13 3.1 Đồ thị web với khung nhìn thực thể [18] . . . . . . . . . . . . . . . . . . 19 3.2 Mô hình tìm kiếm truyền thống và tìm kiếm thực thể [56] . . . . . . . . 19 3.3 Kiến trúc hệ thống[19] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4 Impression model [18] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.5 Ví dụ rút trích thực thể thuốc . . . . . . . . . . . . . . . . . . . . . . . . 24 3.6 So sánh độ chính xác MRR [18] . . . . . . . . . . . . . . . . . . . . . . . 29 3.7 Mô hình học xếp hạng trong máy tìm kiếm thực thể . . . . . . . . . . . 30 3.8 Ví dụ xác định trọng số cục bộ p(α(γ)) . . . . . . . . . . . . . . . . . . . 33 3.9 So sánh độ chính xác trung bình AP trên 5 query . . . . . . . . . . . . . 35 62 Danh sách bảng 3.1 Ví dụ kết quả trả về của truy vấn q . . . . . . . . . . . . . . . . . . . . . 18 3.2 So sánh MRR, MAP của BM25, Impression, LTR . . . . . . . . . . . . . 35 4.1 So sánh MRR, MTRR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2 So sánh Match@N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 A.1 Dữ liệu học: cụm mức 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 A.2 Dữ liệu học - cụm chủ đề giáo dục . . . . . . . . . . . . . . . . . . . . . 61 A.3 Dữ liệu kiểm tra - cụm chủ đề động vật học . . . . . . . . . . . . . . . . 61 A.4 Dữ liệu wiki đầy đủ mức 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 61 63