Luận văn 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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THU TRANG 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 Ngành: Công nghệ Thông tin Chuyên ngành: Hệ thống Thông tin Mã số: 60 48 05 luận văn thạc sĩ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Hà Quang Thụy Hà Nội - 2008 Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu của bản thân. Các số liệu, kết quả trình bày trong luận văn này là trung thực và chưa từng được ai công bố trong bất kỳ công trình luận văn nào trước đây. Học Viên Nguyễn Thu Trang ii Lời cảm ơn Trước tiên, em muốn gửi lời cảm ơn sâu sắc nhất đến PGS.TS Hà Quang Thụy - Người thầy kính yêu, người hướng dẫn, chỉ bảo em tận tình từ những bước nghiên cứu đầu tiên và hoàn thành luận văn. Tôi chân thành cảm ơn các thầy cô trong bộ môn Các Hệ Thống Thông Tin, và phòng thí nghiệm SISLAB, nhóm xemina Data Mining và đặc biệt gửi lời cảm ơn tới ThS.Nguyễn Cẩm Tú đã giúp đỡ, hỗ trợ tôi trong quá trình nghiên cứu, hoàn thành đề tài. Tôi cảm ơn các thầy cô và các cán bộ của trường Công nghệ đã tạo cho tôi những điều kiện thuận lợi để học tập và nghiên cứu. Cuối cùng, xin gửi lời cảm ơn tới gia đình, GB và bạn bè nguồn động viên tinh thần to lớn với tôi, luôn cổ vũ và tin tưởng tôi. Nguyễn Thu Trang iii Mục lục MỞ ĐẦU 1 1 Xếp hạng đối tượng 2 1.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Phương pháp PageRank . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Xếp hạng đối tượng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Phương pháp đánh giá xếp hạng . . . . . . . . . . . . . . . . . . . . . 6 1.5 Tổng kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Học xếp hạng 9 2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Phương pháp học xếp hạng . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1 Hồi quy có thứ tự và Pairwise . . . . . . . . . . . . . . . . . . 11 2.2.2 Học xếp hạng danh sách Listwise . . . . . . . . . . . . . . . . 13 2.3 Tổng kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Xếp hạng trong máy tìm kiếm thực thể 16 3.1 Máy tìm kiếm thực thể . . . . . . . . . . . . . . . . . . . . . . . . . . 17 iv MỤC LỤC v 3.2 Xếp hạng thực thể . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2.1 Mô hình Impression . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.2 Nhận xét, đánh giá mô hình Impression . . . . . . . . . . . . . 27 3.2.3 Mô hình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.1 Công cụ sử dụng . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.2 Dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.3 Kết quả và đánh giá . . . . . . . . . . . . . . . . . . . . . . . 34 3.4 Tổng kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4 Tạo nhãn cụm tài liệu 37 4.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 Phương pháp lựa chọn nhãn . . . . . . . . . . . . . . . . . . . . . . . 39 4.3 Học xếp hạng nhãn cụm . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3.1 Các đặc trưng . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3.2 Học hàm tính hạng . . . . . . . . . . . . . . . . . . . . . . . . 44 4.4 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.4.1 Nguồn dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.4.2 Dữ liệu học . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.4.3 Kết quả và đánh giá . . . . . . . . . . . . . . . . . . . . . . . 47 4.5 Tổng kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Kết luận 49 Tài liệu tham khảo 51 A Dữ liệu 59 MỤC LỤC vi A.1 Dữ liệu tìm kiếm thuốc . . . . . . . . . . . . . . . . . . . . . . . . . . 59 A.2 Cây wiki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Danh sách hình vẽ 62 Danh sách bảng 63 Bảng ký hiệu và từ viết tắt Từ viết tắt Mô tả Trang định nghĩa IR Information Retrieval 6 SVM Suport Vector Machine 2 LTR Learning To Rank 1 MAP Mean Average Precision 7 OR Ordinal Regression 10 vii MỞ ĐẦU Xếp hạng các đối tượng (trang Web, tác giả, chủ đề, trường đại học, công ty...) có ý nghĩa quan trọng trong lĩnh vực khai phá dữ liệu, là trung tâm của nhiều ứng dụng - điển hình là máy tìm kiếm. Các phương pháp tính hạng được nghiên cứu và phát triển từ rất nhiều năm trước, nhưng khoảng 3 năm trở lại đây, hướng tiếp cận sử dụng phương pháp học máy để xếp hạng đối tượng trở thành một vấn đề thu hút được rất nhiều sự quan tâm như trong SIGIR 2007 và SIGIR 2008 đã tổ chức hội thảo chuyên đề về học xếp hạng (learning to rank: LTR)[49]. Học xếp hạng đang được nhiều nhà khoa học trên thế giới quan tâm nghiên cứu và ứng dụng, như cải tiến hàm tính hạng trong máy tìm kiếm của nhóm Yuehua Xu tại ICML năm 2007 [59], mô hình tính hạng thực thể trong máy tìm kiếm thực thể của nhóm các tác giả Tao Cheng, Kevin Chang trong [17, 18, 19], và sử dụng học xếp hạng để đánh giá trọng số của các cụm từ [65, 53]. Luận văn 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 thực hiện khảo sát, phân tích các phương pháp học xếp hạng đang được quan tâm hiện nay và từ đó đưa ra mô hình xếp hạng thực thể áp dụng vào máy tìm kiếm thực thể trong tiếng Việt, cụ thể là tìm kiếm thực thể thuốc và học xếp hạng để tạo nhãn cho cụm tài liệu. Qua đó cho thấy ứng dụng to lớn và ý nghĩa quan trọng của bài toán học xếp hạng. Luận văn này gồm bốn chương, nội dung được mô tả như dưới đây. Chương 1. Tổng quan về xếp hạng đối tượng giới thiệu những nội dung cơ bản nhất về bài toán xếp hạng và đặt vấn đề học xếp hạng đối tượng. 1 MỞ ĐẦU 2 Chương 2. Học xếp hạng đối tượng trình bày hai phương pháp học xếp hạng cơ bản. Đồng thời, chương này cũng giới thiệu thuật toán học được sử dụng nhiều trong học xếp hạng là máy véc-tơ hỗ trợ (SVM) và hồi quy tuyến tính. Chương 3. Học xếp hạng trong máy tìm kiếm thực thể đưa ra mô hình học xếp hạng đối tượng và thực nghiệm tính hạng thực thể thuốc trong máy tìm kiếm thực thể. Chương 4. Gán nhãn cụm tài liệu phân tích, áp dụng và báo cáo kết quả thực nghiệm học xếp hạng từ/cụm từ để tạo nhãn cho các cụm tài liệu. Phần kết luận tổng kết và tóm lược nội dung chính của luận văn. C h ư ơ n g 1 Xếp hạng đối tượng 1.1 Giới thiệu Trong nhiều ứng dụng cần xếp hạng các đối tượng theo tiêu chí nào đó, đơn giản như việc xếp hạng học sinh trong một lớp theo điểm trung bình, hay xếp hạng các trường đại học,.. và đặc biệt là việc xếp hạng các kết quả trả về của máy tìm kiếm. Xếp hạng đối tượng là việc sắp xếp các đối tượng theo độ phù hợp với tiêu chí tùy vào từng ứng dụng cụ thể. Do đó cần xác định hàm tính giá trị về độ phù hợp để sắp xếp của các đối tượng theo tiêu chí đã đặt ra, và hàm đó được gọi là hàm tính hạng (ranking function: RF). Mỗi khi nói tới xếp hạng đối tượng chúng ta quan tâm tới hàm tính hạng. Một điển hình của bài toán xếp hạng là việc xếp hạng các kết quả trả về của máy tìm kiếm. Trong máy tìm kiếm thông thường (như Google, Yahoo) độ quan trọng hay còn gọi hạng trang là đại lượng cơ sở để xếp hạng. Giá trị này được xác định dựa vào việc phân tích đồ thị liên kết giữa các trang web. Với tập các tài liệu D = d1, ..dn, khi có truy vấn q của người dùng máy tìm kiếm cần tìm những tài liệu 2 CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 3 trong D phù hợp với truy vấn q, và sau đó sắp xếp các tài liệu theo độ phù hợp với truy vấn và độ quan trọng giảm dần. Đó là quá trình xếp hạng và hàm tính hạng là hàm kết hợp của giá trị độ tương tự giữa tài liệu với truy vấn similarity(q, di) và hạng trang thành chỉ số xếp hạng được Arvind Arasu và các tác giả đề cập tới trong [6]. Việc xác định hàm tính hạng đóng vai trò quan trọng và quyết định đối với chất lượng của máy tìm kiếm. Từ những năm 98, Cohen [21] đã đưa ra nhận định rằng có nhiều ứng dụng cần sắp xếp các đối tượng hơn là cần phân lớp chúng. Mọi ứng dụng mà kết quả trả về cho người dùng là một danh sách các đối tượng cần được sắp xếp, xếp hạng giúp người dùng nhanh chóng tiếp cận với kết quả gần với yêu cầu của mình nhất có thể. Thực tế chúng ta gặp rất nhiều các bảng xếp hạng như ví dụ ở trên. Điều đó cho thấy, xếp hạng là một bài toán quan trọng và có ý nghĩa. Tuy nhiên khái niệm xếp hạng (ranking) ra đời ban đầu với định hướng xếp hạng các đối tượng trên Web - cụ thể là các trang web. Các trang web cần được sắp xếp theo độ quan trọng giảm dần. Giá trị độ quan trọng đó gọi là hạng trang và PageRank [43] là phương pháp tính hạng đầu tiên, tính hạng trang các trang web dựa vào phân tích mối liên kết giữa các trang web trong đồ thị Web. 1.2 Phương pháp PageRank Page và các đồng tác giả [43] đã đưa ra ý tưởng: độ quan trọng của một trang chịu ảnh hưởng của độ quan trọng từ các trang liên kết đến nó. Và công thức tính PageRank cho một trang u, gọi là piu được tính như sau: piu = ∑ i∈BI (i) pii Ni (1.1) Với BI(i) là tập hợp các trang có liên kết đến trang i và Ni là số trang liên kết ra từ trang i. Biểu diễn đồ thị Web bởi ma trận chuyển P , khi đó phương trình 1.1 được viết lại dưới dạng ma trận: pi = piP (1.2) CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 4 Trong đó: pi = (pi1, pi2, . . . pin) là véc-tơ hạng các trang web, với thành phần pii là hạng của trang i. Từ 1.2 cho thấy véc-tơ hạng trang pi chính là véc-tơ riêng của ma trận chuyển P tương ứng với giá trị riêng λ = 1. Do tính chất của chuỗi Markov, để tính véc-tơ riêng của P thuật toán giả thiết rằng đồ thị trang web là liên thông, tức với cặp hai trang web i, j bất kì luôn có đường đi từ i tới j và ngược lại. Tuy nhiên thực tế trên World Wide Web (WWW) vẫn tồn tại không ít các trang web không có liên kết đến hoặc liên kết ra nên việc giả thiết đồ thị Web liên thông là không hợp lý. Và trong ma trận P vẫn tồn tại hàng chỉ toàn số 0, nên không tồn tại một phân phối xác suất dừng ổn định của P hay chính là véc-tơ hạng trang. Vì vậy cần phải biến đổi ma trận P thành P ′ sao cho phù hợp. Định nghĩa véc-tơ v, được chuẩn hóa ‖v‖ = 1, xác định xác suất phân phối với vi là xác suất trang web i được gọi đến ở lần duyệt web đầu tiên. véc-tơ v có vai trò trong việc hướng kết quả PageRank theo chủ đề, lĩnh vực mong muốn. Khi không xét đến ngữ cảnh đó có thể chọn vi = 1n với ∀i = 1, 2..n . Gọi d là véc-tơ n× 1 xác định các trang không có liên kết ra (dangling nút trên đồ thị Web): di = { 1 nếu N(i) = 0 0 ngược lại Ma trận P ′ được xác định: P ′ = P + dv (1.3) Khi thay đổi ma trận P như vậy tức thêm các liên kết ảo từ các dangling nút tới tất cả các nút khác trong đồ thị Web theo phân phối xác suất v. Điều đó giúp tránh việc khi duyệt các trang không có liên kết ra sẽ không duyệt tiếp được. Để đảm bảo phân phối dừng ổn định (duy nhất), chuỗi Markov tương ứng với quá trình duyệt Web của người dùng cần có tính chất ergodic, tức từ một trang web người dùng có thể chuyển tới một trang bất kì khác. Do vậy ma trận Markov P˜ được xác định như sau: P˜ = αP ′ + (1− α) J (1.4) CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 5 Với: J = [1]n×1 v và α: là hệ số hãm α thường được chọn giá trị 0.85, với ý nghĩa tại mỗi bước duyệt Web người dùng có thể chuyển tới một trang trong các liên kết ra từ trang hiện tại với xác suất α và chuyển tới các trang khác trong đồ thị Web với xác suất (1− α) theo phân phối v. Khi đó, thay vì tính vector riêng của ma trận P ta tính vector riêng pi của ma trận P˜ : pi = piP˜ . Theo tính chất của chuỗi Markov, tổng các thành phần của véc-tơ pi bằng 1:∑n i=1 pii = 1 Vậy véc-tơ hạng trang chính là véc-tơ riêng của ma trận P˜ . 1.3 Xếp hạng đối tượng Hạng trang PageRank là độ đo đầu tiên để xếp hạng các trang web. Và vì vậy, có thể coi hạng trang là hàm xếp hạng các đối tượng - cụ thể đối tượng trong trường hợp này là các trang web. Và ngày càng có nhiều các nghiên cứu về xếp hạng không chỉ là các trang web như xếp hạng các trường đại học [4, 3, 55], xếp hạng các nhà khoa học, bài báo [48]... Với những xếp hạng đơn giản như xếp hạng học sinh theo điểm trung bình, xếp hạng các doanh nghiệp theo doanh thu năm...có một tiêu chí xếp hạng rõ ràng và hàm tính hạng "dễ dàng" xác định. Tuy nhiên trong nhiều ứng dụng như xếp hạng các trường đại học, xếp hạng các nhà khoa học, xếp hạng các kết quả trả về của máy tìm kiếm,...mỗi loại đối tượng cần xếp hạng có nhiều đặc trưng khác nhau, cần tìm ra mối quan hệ về độ quan trọng của các đặc trưng đó. Và từ đó kết hợp các đặc trưng thành một hàm gọi l hàm tính hạng để xếp hạng các đối tượng. Đối tượng có giá trị hạng càng cao thì có thứ hạng càng cao (thứ hạng cao nhất là 1, và lần lượt giảm dần 2, 3 ..) Ví dụ, vấn đề xếp hạng các trường đại học đang nhận được nhiều sự quan tâm. Webometric [55, 4] là một phương pháp xếp hạng trường đại học dựa vào các thông tin trên web với có 4 chỉ số đặc trưng được xác định. Hàm xếp hạng các trường là CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 6 một hàm tuyến tính của 4 chỉ số đó và Webometric cũng đưa ra hệ số cụ thể cho từng chỉ số. Việc xếp hạng các trường đại với độ đo Webometric vẫn đang được các nhà khoa học quan tâm nghiên cứu [55, 4] với các nghiên cứu về các chỉ số và xác định hàm xếp hạng. Học xếp hạng được Joachims [36, 49] đánh giá là lĩnh vực nổi lên với sự phát triển lớn mạnh trong các nghiên cứu về truy tìm thông tin (information retrieval)và học máy (machine learning). Nói một cách khác, học hàm tính hạng hiện đang là vấn đề được quan tâm trong lĩnh vực học máy và có nhiều ứng dụng trong truy tìm thông tin, theo [61]. Học xếp hạng là học hàm của các đặc trưng để sắp xếp các đối tượng theo độ phù hợp, ưu tiên hay độ quan trọng...tùy vào từng ứng dụng cụ thể. Hiện nay nghiên cứu các phương pháp học tính hạng đang được nhiều nhà khoa học trên thế giới quan tâm [8, 12, 16, 26, 37, 44, 46, 45, 50], có nhiều phương pháp học xếp hạng được đưa ra như RankSVM [34], SVM-MAP [62].. Chương sau sẽ giới thiệu cụ thể các phương pháp học xếp hạng hiện nay. 1.4 Phương pháp đánh giá xếp hạng Để đánh giá chất lượng một xếp hạng, các độ đo thông dụng trong học máy như độ chính xác (precision), độ hồi tưởng (recall), độ đo F không sử dụng. Xếp hạng yêu cầu các đối tượng "đúng" (phù hợp tiêu chí) cần được xếp ở các vị trí đầu tiên của bảng xếp hạng càng tốt. Giả sử 6 đối tượng tương ứng là: a, b, c, d, e Trong đó a, b, c là các đối tượng phù hợp và d, e là các đối tượng không phù hợp. Một xếp hạng của các đối tượng cần đánh giá là: c, a, d, b, e. Các độ đo về độ chính xác của xếp hạng thường được sử dụng: CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 7 Độ chính xác mức K: P@K Độ chính xác xếp hạng ở mức K - Precision@K (P@K): độ chính xác của K đối tượng đầu bảng xếp hạng. Xác định số đối tượng đúng ở K vị trí đầu tiên của xếp hạng và gọi là Match@K, và độ chính xác mức K: P@K = Match@K K Với ví dụ trên ta có: P@3 = 2/3 ; P@4 = 3/4; P@5 = 3/5; Độ chính xác trung bình: MAP Độ chính xác trung bình là giá trị trung bình của các P@K tại các mức K có đối tượng đúng. Gọi I(K) là hàm xác định đối tượng ở vị trí hạng K nếu đúng I(K) =1 và ngược lại I(K) = 0. Độ chính xác trung bình: AP = ∑n K=1 P@K × I(K)∑n j=1 I(j) Với n là số đối tượng được xét. Giá trị trung bình trên m xếp hạng (với bài toán tìm kiếm thì đó là giá trị trung bình của AP trên các truy vấn): MAP = ∑m i=1 APi m Ví dụ trên có: MAP = 1 3 .( 1 1 + 2 2 + 3 4 ) Trung bình nghịch đảo thứ hạng: MRR Xác định vị trí hạng của đối tượng đúng đầu tiên trong bảng xếp hạng: r, khi đó nghịch đảo hạng: RR = 1/r. Với ví dụ trên, ta có RR = 1/1. Trung bình nghịch đảo thứ hạng là giá trị trung bình nghịch đảo thứ hạng RR của tất cả các truy vấn/hay xếp hạng đang xét. MRR = ∑m i=1 RRi m CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 8 Một số độ đo khác Các độ đo ít được sử dụng hơn như: • Số đối tượng đúng ở mức K: Match@K. • Trung bình tổng nghịch đảo thứ hạng của các đối tượng đúng (MTRR): Với giá trị tổng nghịch đảo được xác định: TRR = n∑ i=1 ( 1 i × I(i)) Trong ví dụ ta có TRR = 1/1 + 1/2 1.5 Tổng kết Xếp hạng là một bài toán phổ biến, có ý nghĩa quan trọng và có nhiều ứng dụng trong thực tế. Vấn đề học xếp hạng là vấn đề thời sự đang nhận được nhiều sự quan tâm của các nhà khoa học. Hướng tiếp cận bài toán học xếp hạng đã được giới thiệu trong chương này, các chương sau tiếp tục làm rõ hơn về bài toán học xếp hạng và ứng dụng. C h ư ơ n g 2 Học xếp hạng 2.1 Giới thiệu Các nghiên cứu về học xếp hạng chủ yếu tập trung vào ứng dụng xếp hạng các tài liệu trả về từ máy tìm kiếm dựa theo truy vấn. Có tập các tài liệu D = {d1, d2, ..., dn} và với truy vấn q, cần xác định hàm xếp hạng r để sắp xếp các tài liệu D theo độ phù hợp với truy vấn. Tổng quát bài toán xếp hạng đối tượng nói chung, ta có: tập X ⊂ Rn của các đối tượng x = (x1, .., xn) ∈ Rn, với n là số đặc trưng của mỗi đối tượng. Cần tìm hàm h(x) : X → R để sắp xếp các đối tượng x theo độ phù hợp. Dữ liệu học S là xếp hạng đúng của một tập các đối tượng X ′ ⊂ X được đưa ra để học hàm h(x). Tùy từng ứng dụng mà người dùng có các mức yêu cầu khác nhau về sắp xếp thứ hạng đúng và có các kiểu dữ liệu học: 1. Xác định giá trị độ phù hợp y cụ thể của từng đối tượng trong S. Do trong ứng dụng xếp hạng, người dùng quan tâm nhiều tới thứ tự thay vì giá trị xếp 9 CHƯƠNG 2. HỌC XẾP HẠNG 10 hạng (độ phù hợp) nên y thường được xác định: • Hai giá trị tương ứng xếp hạng phù hợp (releval) và không phù hợp (inreleval). Người dùng chỉ quan tâm các đối tượng có phù hợp tiêu chí đặt ra hay không (2 hạng). • N giá trị xác định tương ứng N hạng nhất định, ví dụ: rất phù hợp, phù hợp, có thể phù hợp, không phù hợp. 2. Đưa ra các so sánh độ phù hợp của từng cặp đối tượng. 3. Danh sách sắp thứ tự đúng của "tất cả" các đối tượng theo độ phù hợp. Với mỗi kiểu dữ liệu trên, xác định các kiểu ràng buộc xếp hạng khác nhau và có các phương pháp học xếp hạng tương ứng. Các phương pháp học xếp hạng theo Soumen Chakrabarti [14] và Tie-Yan Liu [40]: Hồi quy (Regression): Có S = {(xi, yi)} mỗi đối tượng xi xác định giá trị yi tương ứng về độ phù hợp. Học hàm h(x) thỏa mãn: h(xi) = yi với ∀x ∈ X ′ Trong học xếp hạng, khi giá trị yi xác định thứ hạng của đối tượng xi thì phương pháp gọi là hồi quy có thứ tự (Ordinal Regression). Cặp thứ tự (Pairwise): Có S = {(xi, xj)} là tập các cặp đối tượng được sắp thứ tự, với mỗi cặp (xi, xj) có nghĩa xi có thứ hạng cao hơn xj (xi phù hợp hơn xj : xi  xj). Tìm h(x): ∀(xi, xj) ∈ S có xi  xj thì h(xi) > h(xj) Danh sách sắp xếp (Listwise): Một thứ tự sắp xếp của tất cả các đối tượng được xác định [62]. Tuy nhiên trong nhiều ứng dụng (ví dụ máy tìm kiếm), việc sắp thứ tự của tất cả các đối tượng là không khả thi, thì một xếp hạng của K đối tượng đầu tiên được xác định, và tất cả các đối tượng khác đều có hạng thấp hơn [12] Có S = {x1, x2, ..., xm} với xi ∈ X ′ là một sắp thứ tự (x1  x2  ...  xm) tìm hàm h(x) sao cho: h(x1) > h(x2) > ... > h(xm) CHƯƠNG 2. HỌC XẾP HẠNG 11 2.2 Phương pháp học xếp hạng 2.2.1 Hồi quy có thứ tự và Pairwise Học xếp hạng với phương pháp hồi quy có thứ tự: tập dữ dữ liệu học S = {(xi, yi)}li=1với yi ∈ 1, 2, ...R là một tập sắp thứ tự, cần học hàm h(x) thỏa mãn: Với mọi cặp (xi, yi) và (xj , yj) thuộc S thì yi > yj ⇔ h(xi) > h(xj) Gọi P là tập hợp tất cả các cặp (i, j) mà thứ hạng của xi cao hơn của xj (xi  xj) trong S: P = {(i, j) : yi > yj} và |P | = m. Do vậy có thể phát biểu lại bài toán: có các cặp so sánh thứ tự S ′ = {(xi, xj) ∣∣xi  xj}, tìm h(x) thỏa mãn: ∀(xi, xj) ∈ S ′ có xi  xj thì h(xi) > h(xj) Như vậy, từ bài toán hồi quy có thứ tự đã được chuyển về bài toán Pairwise. Ví dụ có tập sắp thứ tự S = {(d1, 2), (d2, 1), (d3, 1)} khi đó có các cặp so sánh thứ tự S ′ = {(d2, d1), (d3, d1)}. Với ví dụ này có d2 và d3 không xác định thứ tự so sánh (cùng thứ hạng trong S). Để giải quyết bài toán Pairwise, vấn đề xếp hạng (ranking) được đưa về bài toán phân lớp cho từng cặp đối tượng [40, 66, 34, 9, 30, 33, 22]. Giá trị của hàm phân lớp là giá trị xếp hạng đối tượng. Hàm tính hạng h : X → R h(x) = wTx SVM[33] (Support Vector Machine - máy véc-tơ hỗ trợ) là phương pháp học máy học bộ phân lớp nhị phân (chia các đối tượng thành hai lớp). Tư tưởng chính của SVM là xác định biên (siêu phẳng) chia không gian các đối tượng thành hai nửa và tìm siêu phẳng tốt nhất (tối ưu) mà khoảng cách từ siêu phẳng tới đối tượng gần nhất trong cả 2 tập phân chia là lớn nhất. Với dữ liệu có thể phân tách tuyến tính, siêu phẳng có dạng wTx + b = 0. Dễ dàng nhận thấy mối liên hệ giữa hàm tính hạng h(x) và siêu phẳng. Do vậy với phương pháp SVM tìm được siêu phẳng ta suy ra hàm tính hạng h(x). CHƯƠNG 2. HỌC XẾP HẠNG 12 Để xác định siêu phẳng tối ưu, Joachims [33] đưa ra công thức tối ưu: min w,ξi≥0 (1 2 wTw + C n n∑ i=1 ξi ) Với ∀i ∈ {1, ..., n} : yi.(wTxi) ≥ 1− ξij. Trong đó ξi là hệ số nới lỏng được mô tả như trong hình 2.2. Herbrich [30] đã dựa vào công thức tối ưu trên của Joachims để đưa ra tối ưu tương tự trong hồi quy có thứ tự gọi là ordinal regression SVM (OR-SVM): min w,ξi,j≥0 (1 2 wTw + C m ∑ (i,j)∈P ξij ) Với ∀(i, j) ∈ P : (wTxi) ≥ (wTxj) + 1− ξij Thuật toán SVM với tối ưu này tìm hàm h(x) tuyến tính, siêu phẳng tốt nhất mà làm cực tiểu số cặp đối tượng x phải hoán đổi vị trí trong sắp xếp được dùng bởi siêu phẳng. Mô tả ý tưởng như hình 2.1. Viết lại ràng buộc của công thức tối ưu trên ta có: với ∀(i, j) ∈ P : wT (xi − xj) ≥ 1− ξij Công thức tương tự với công thức của ràng buộc trong tối ưu phân lớp SVM [33]. Do vậy mọi biến đổi tối ưu trên phân lớp SVM đều có thể được thực hiện đối với hồi quy có thứ tự như các biến đổi của Joachims [34]. Vậy hồi quy có thứ tự đã được đưa về bài toán học phân lớp nhị phân, sử dụng phân lớp SVM để học được mô hình tham số w cho hồi quy tuyến tính, được gọi là phương pháp RankSVM. Wei Chu và S. Sathiya Keerthi [20] năm 2005 cũng đưa ra phương pháp học hồi quy có thứ tự dựa vào SVM với việc xác định các ngưỡng phân chia thứ hạng: Với r thứ hạng trong S cần tối ưu (r − 1) ngưỡng để phân các đối tượng vào từng lớp, mô tả trong hình 2.2. Ngoài ra, các phương pháp trong [11, 35] cũng dựa vào tối ưu của SVM tương tự như trên. Công cụ SVM light do Joachims [34] cung cấp đã cho người dùng lựa chọn học xếp hạng đối tượng dựa vào phương pháp này. CHƯƠNG 2. HỌC XẾP HẠNG 13 Hình 2.1: Xếp hạng với SVM [34] b 2 b1 y=1 y=2 y=3 b 2 -1 b 2 +1b 1 -1 b 1 +1 ξ i *1+1 ξ i2 ξ i *2+1 ξ i1 f(x) = w φ(x). Hình 2.2: Xác định ngưỡng phân thứ hạng [20] 2.2.2 Học xếp hạng danh sách Listwise Với các ứng dụng xếp hạng, như xếp hạng các trang web trả về cho người dùng trong máy tìm kiếm, người dùng nhận được danh sách các kết quả được sắp xếp theo thứ tự độ phù hợp giảm dần thay vì so sánh thứ hạng của mỗi cặp kết quả. Xét ví dụ các đối tượng được xếp thành 3 thứ hạng (p: rất tốt, g: tốt và b: không tốt), khi đó giả sử có 5 đối tượng được xếp hạng lần lượt: (p, g, g, b, b). Có hai danh sách xếp hạng được đưa ra như sau: (g, p, g, b, b) và (p, g, b, g, b). CHƯƠNG 2. HỌC XẾP HẠNG 14 Hai xếp hạng trên đều chỉ xếp hạng sai một cặp đối tượng, nhưng có thể thấy việc xếp sai g,p là lỗi lớn hơn so với xếp sai b,g. Đây chính là điểm yếu của phương pháp Pairwise. Do chỉ xét từng cặp đối tượng để so sánh nên phương pháp Pairwise không tối ưu các độ đo đánh giá chất lượng xếp hạng ví dụ như MAP, vì vậy không phân biệt được sự khác nhau giữa hai xếp hạng trên [40]. Do đó, thay vì chuyển bài toán xếp hạng về bài toán hồi quy và phân lớp, học xếp hạng từ danh sách sắp thứ hạng đã được các tác giả [62, 12, 10, 50] quan tâm. Với Listwise, dữ liệu học là tập S = {x1, ..., xn} các đối tượng thuộc X với thứ hạng sắp xếp tương ứng Y = {y1, ..., yn} Phương pháp học xếp hạng trực tiếp từ danh sách xếp hạng do Yisong Yue và các đồng tác giả [62] đưa ra sử dụng SVM để tìm tối ưu và ràng buộc về độ đo đánh giá MAP trên danh sách xếp hạng. Yisong Yue đã dựa vào tối ưu Multivar [35] của Joachims, công thức: minw,ξi,j≥0 1 2 wTw + C m N∑ i=1 ξij Với ràng buộc: ∀i, ∀y ∈ Y có wTΨ(xi, yi) ≥ wTΨ(xi, y) + ∆(yi, y)− ξi Trong đó Ψ(x, y) là độ đo xác định độ khác biệt giữa các sắp xếp thứ hạng với sắp thứ hạng đúng. Yisong Yue hướng tối ưu độ đo MAP và xác định: Ψ(x, y) = ∑ i:rel ∑ j:!rel yij.(xi − xj) và ∆(y, y′) = 1−MAP (y′) Với MAP (y′) là độ chính xác trung bình của xếp hạng y′. (i : rel) có nghĩa thứ hạng i được xếp đúng và (j :!rel) là thứ hạng j xếp sai. yij = 1 nếu xi có thứ hạng cao hơn xj và ngược lại yij = −1 nếu xi có thứ hạng thấp hơn xj . Khi số lượng đối tượng được xếp hạng tăng thì số ràng buộc cũng tăng nhanh, do vậy Yisong Yue và các đồng tác giả đưa ra phương pháp học từng bước. Mỗi bước, xác định ràng buộc mà bị vi phạm lớn nhất (lỗi nhất) trong tập các ràng buộc CHƯƠNG 2. HỌC XẾP HẠNG 15 và tìm tối ưu thỏa mãn ràng buộc đó. Và quá trình tối ưu trên từng ràng buộc như vậy được lặp đi lặp lại tới khi không tìm được ràng buộc bị vi phạm. Đó là học xếp hạng Listwise với tối ưu MAP, ngoài ra có các phương pháp với các tối ưu khác như các phương pháp AdaRank [58], SoftRank [50], ListNet [12],... Với kết quả do Yisong Yue đưa ra và qua phân tích các kết quả công bố trên LETOR∗ (một dự án về học xếp hạng), phương pháp SVM-MAP có chất lượng cao (so với các phương pháp đã công bố kết quả của cùng dữ liệu của LETOR). 2.3 Tổng kết chương Chương này đã giới thiệu chung về các phương pháp học xếp hạng hiện nay và hai phương pháp học xếp hạng SVM-MAP, RankSVM được đề cập. Đó là hai phương pháp được áp dụng vào hai ứng dụng học xếp hạng được trình bày ở chương sau. ∗ C h ư ơ n g 3 Xếp hạng trong máy tìm kiếm thực thể Các máy tìm kiếm thông dụng hiện nay như Google, Yahoo, MSN, truy vấn người dùng đưa vào là tập các từ khóa và kết quả trả về là danh sách các địa chỉ tới các trang web. Do vậy để nhận được thông tin mong muốn, người dùng phải duyệt qua từng địa chỉ web đó, và có thể phải duyệt qua nhiều trang không có thông tin mong muốn. Với sự phát triển của các kỹ thuật rút trích thông tin (Information Extraction- IE) cụ thể là rút trích các thực thể, hướng phát triển máy tìm kiếm thực thể đã được Kevin Chang và các cộng sự [17, 18, 19] nghiên cứu, xây dựng. Truy vấn của người dùng trên máy tìm kiếm thực thể không đơn thuần là các từ khóa mà người dùng xác định rõ hơn về loại đối tượng dữ liệu đang muốn tìm và ngữ cảnh tìm kiếm. Kết quả trả về cho người dùng thay vì chỉ là các địa chỉ web, người dùng còn nhận được các thông tin cụ thể về đối tượng mình mong muốn tìm kiếm. Cũng như với máy tìm kiếm thông thường xếp hạng là vấn đề quan trọng, xếp hạng thực thể 16 CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 17 là cốt lõi và quan trọng của máy tìm kiếm thực thể. Không chỉ các tác giả T.Cheng, X.Yan, K.Chang [17, 18, 19] mà xếp hạng thực thể thu hút được sự quan tâm của nhiều nhà khoa học với các nghiên cứu xếp hạng thực thể trên các trang web của wikipedia∗ [51, 23, 68, 24, 54, 64]. Đặc điểm dữ liệu wiki là các trang web đều được xác định chủ đề/thể loại (category) và trong mỗi trang có các khái niệm (concept) được đánh dấu (tag) hay tạo liên kết tới các trang mô tả khái niệm đó. Do vậy, với cấu trúc web giàu ngữ nghĩa đó, việc xếp hạng các thực thể trên wikipedia thường dựa trên các liên kết giữa các thực thể (hay các khái niệm), liên kết giữa các trang web, độ tương đồng ngữ nghĩa giữa các khái niệm như được đề cập trong [23]. Song song với các nghiên cứu đó là các nghiên cứu xếp hạng thực thể dựa trên việc xây dựng đồ thị quan hệ giữa các thực thể, mạng xã hội các thực thể trên web [47, 15, 13, 2, 7]. Qua phân tích các nghiên cứu [51, 23, 24, 54, 47, 13, 15, 17, 18, 19], với định hướng xây dựng hệ tìm kiếm thực thể trên web nói chung, việc xếp hạng trong tìm kiếm thực thể của nhóm T.Cheng, X.Yan và K.Cheng được quan tâm và phân tích. 3.1 Máy tìm kiếm thực thể Người dùng thường tìm kiếm thông tin về đối tượng nào đó, ví dụ như khi sử dụng truy vấn "thuốc chống viêm", người dùng muốn tìm các thực thể thuốc mà có tác dụng chống viêm. Và các máy tìm kiếm hiện nay (như Google, Yahoo, MSN) bằng cách so sánh văn bản (text) trên từng trang web với truy vấn và trả về cho người dùng địa chỉ các trang mà có chứa từ khóa trong truy vấn. Do vậy người dùng không trực tiếp nhận được thông tin mong muốn mà phải duyệt qua nội dung các trang web trả về đó và không chắc chắn có được thông tin mong muốn ở những kết quả đầu tiên. Đó là nhược điểm của các máy tìm kiếm này, không hiểu mục đích tìm kiếm của người dùng, và tìm kiếm trên các trang web độc lập chỉ dựa vào từ khóa. Theo [17] máy tìm kiếm thực thể hướng người dùng tốt hơn, cho phép chỉ ra trong truy vấn đối tượng mà người dùng muốn tìm. Và kết quả trả về của máy tìm kiếm là ∗ CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 18 các thực thể của đối tượng cần tìm, mỗi thực thể được xác định không chỉ xét trên một trang độc lập mà có thể được tổng hợp qua nhiều trang web. Ví dụ máy tìm kiếm thực thể của dự án WISDM∗ của nhóm T.Cheng, X.Yan và K.Chang. Với truy vấn thông thường q = "phone number of New York Department of Motor Vehices" tức người dùng đang cần tìm điện thoại của văn phòng của "Motor Vehices" ở "New York". Khi đó truy vấn của người dùng tương ứng trong máy tìm kiếm thực thể WISDM là q = "New York DMV #phone", chỉ rõ đối tượng muốn tìm "phone" và ngữ cảnh xuất hiện của đối tượng "New York DMV". Kết quả trả về của máy tìm kiếm là các số điện thoại, và với mỗi số điện thoại có danh sách các địa chỉ web tương ứng chứa thông tin điện thoại đó như bảng 3.1. Bảng 3.1: Ví dụ kết quả trả về của truy vấn q phone urls 1-800-225-5368 https://www.nysdot.gov/about-nysdot/contact, ... ... Sơ đồ hình 3.2 cho thấy sự khác biệt cơ bản giữa máy tìm kiếm thông thường với máy tìm kiếm thực thể. Máy tìm kiếm thực thể đã xem không gian web không chỉ là tập các trang web với các từ khóa như máy tìm kiếm thông thường mà còn là tập các đối tượng hay các kiểu thực thể E = E1, E2, ..., En như hình 3.1. Mỗi đối tượng Ei có các thực thể ei tương ứng được trích ra từ các trang web, ví dụ đối tượng thuốc #drug có các thực thể {"Diclofenac", "Steroid", "Chloramphenicol",...}. Khi đó ngoài chỉ mục (index) từ, máy tìm kiếm còn có chỉ mục cho thực thể. Bài toán tìm kiếm thực thể được phát biểu [18]: • Giả thiết: Có tập các tài liệu D = {d1, ..., dn} và các kiểu thực thể E = {E1, ..., EN} • Input: Truy vấn q = α(E1, ..., Em, k1, ..., kl) là một hàm của các kiểu thực thể và các từ khóa thể hiện yêu cầu của người dùng tìm kiếm các loại thực thể ∗ CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 19 Hình 3.1: Đồ thị web với khung nhìn thực thể [18] Tìm kiếm truyền thống Tìm kiếm thực thể Các từ khóa Thực thể Kết quả Kết quả Hình 3.2: Mô hình tìm kiếm truyền thống và tìm kiếm thực thể [56] E1, ..., Em với ngữ cảnh các từ khóa k1, ..., kl. • Output: Danh sách đã xếp hạng của các bộ t = (e1, ..., em). Tao Cheng, X.Yan và Kevin C.C Chang tại SIGMOD’07 [19] đã đưa ra kiến trúc cơ bản của hệ thống tìm kiếm thực thể hình 3.3. Hệ thống được chia thành hai phần: một phần xử lý ngoại tuyến (offline) gồm rút trích thực thể (Entity extraction) và CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 20 Global Query Processing Ranking Model Keyword&Entity Indexer entity query results, scores Entity Extractor Local Query Local Index Local Index… Processing Local Query Processing … Aggregation Local Index Local Query Processing Sort Merge Join , 05, 71,, 21 62 ddamazon ,...8 0 ,123,, 32# 6dphone ...... Hình 3.3: Kiến trúc hệ thống[19] đánh chỉ mục (indexing) (khối được bao nét đứt), và phần xử lý trực tuyến (online) đó là xếp hạng thực thể (khối bao nét liền Ranking Model). Entity Extraction thực hiện việc rút trích các thực thể từ các trang tài liệu được lấy về. Indexing tạo chỉ mục và chỉ mục ngược của các thực thể được trả về từ mô-dul rút trích trên. Ranking xếp hạng các thực thể, với hai bước chính: cục bộ (locally), và toàn cục CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 21 (globally). Như kiến trúc được đề cập ở phần trên do T.Cheng, X.Yan và K.Chang [19] đưa ra, modul xếp hạng gồm có hai thành phần chính: xử lý truy vấn cục bộ (local) và xử lý truy vấn toàn cục (global). 1. Xử lý cục bộ: Từ chỉ mục ngược của tất cả các thực thể thuộc kiểu Ei và từ khóa kj, modul thực hiện phép nối trên tài liệu để tìm các tài liệu chứa các thực thể thuộc Ei, và các từ khóa kj thỏa mãn hàm α. Trọng số cục bộ (local score) được xác định dựa vào độ tin cậy của thực thể được rút trích và mối quan hệ ngữ cảnh giữa các thực thể đó với các từ khóa trong từng tài liệu. 2. Xử lý toàn cục: Module thực hiện nhận truy vấn người dùng, gửi truy vấn cho modul xử lý cục bộ, sau đó đợi kết quả trả về từ modul xử lý cục bộ. Sau khi nhận được tất cả các trọng số cục bộ, modul tiến hành tổng hợp trọng số cho từng bộ thực thể t, kết hợp trọng số cục bộ với trọng số xác định cho t trên toàn tập tài liệu để có giá trị Score cuối cùng cho xếp hạng. Trong giới hạn của luận văn này, tôi tập trung phân tích thành phần xếp hạng. Vấn đề xếp hạng thực thể được phân tích ở phần tiếp sau và mô hình áp dụng vào bài toán xếp hạng thực thể thuốc được đề cập. 3.2 Xếp hạng thực thể Máy tìm kiếm thực thể trả về cho người dùng kết quả là danh sách các thực thể. Không chỉ tìm được thực thể mà vấn đề của máy tìm kiếm là những thực thể phù hợp nhất với truy vấn cần được đưa lên từ những kết quả đầu tiên trả về cho người dùng. Do đó xếp hạng thực thể là vấn đề quan trọng, cốt lõi của máy tìm kiếm thực thể. Giả thiết có tập tài liệuD = {d1, d2, ..., dn}, tập các kiểu thực thểE = {E1, ..., EN}, truy vấn q = α(E1, ..., Em, k1, ..., kl) với kj là các từ khóa, và bộ các thực thể t = (e1, ..., em). Khi đó độ phù hợp của t đối với truy vấn q trên tập tài liệu D được CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 22 xác định bởi: Score(q(t)) = p(q(t)|D) = ∑ d∈D p(d)× p(q(t)|d) (3.1) Với p(q(t)|d) là xác suất xảy ra quan hệ α của t trên tài liệu d. Giá trị của Score(q(t)) được dùng để xếp hạng các bộ kết quả trả về, do đó việc xác định hàm Score(q(t)) là vấn đề quan trọng chúng ta quan tâm. Những đặc điểm của tìm kiếm thực thể có ảnh hưởng tới giá trị xếp hạng Score() đã được đưa ra trong [18]: R-Contextual : Xác suất liên kết giữa thực thể và từ khóa phụ thuộc vào các ngữ cảnh khác nhau và ảnh hưởng bởi hai yếu tố chính: • Pattern: Từ khóa và thực thể có thể liên kết với nhau theo các mẫu, ví dụ: tên thường xuất hiện liền trước số điện thoại. • Proximity: Từ khóa và thực thể có thể xuất hiện nhiều lần trong trang web và không giống nhau, khi chúng càng gần nhau thì mối quan hệ càng có ý nghĩa cao hơn. R-Holistic: Một thực thể có thể xuất hiện cùng với từ khóa nhiều lần trong một trang, do đó cần ước lượng tìm liên kết phù hợp nhất R-Uncertainty: Việc rút trích thực thể không chính xác tuyệt đối, do đó cần có giá trị độ tin cậy tương ứng cho mỗi thực thể. R-Associative: Cần phân biệt liên kết giữa từ khóa và thực thể là liên kết mang ý nghĩa thực hay chỉ là sự xuất hiện ngẫu nhiên giữa chúng. Do đó cần có kiểm định để loại bỏ những liên kết ngẫu nhiên. R-Discriminative: Các thực thể trên các trang phổ biến hơn sẽ được đánh giá cao hơn so với trên trang ít phổ biến hơn. 3.2.1 Mô hình Impression Từ những phân tích về máy tìm kiếm thực thể, nhóm tác giả Tao Cheng[18] đã đưa ra mô hình xếp hạng "Impression Model" hình 3.4. Mô hình gồm 3 tầng: Truy CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 23 Global Access Layer Local Recognition Layer Global Access Layer Local Recognition Layer Validation Layer Collection E over D Virtual Collection E’ over D’ ... ... ... ... ... ... : ?? : ?? ... ... ... ... ... ... : ?? : ?? ... ... ... ... ... ... : ?? : ?? randomize Hình 3.4: Impression model [18] nhập toàn cục (Global Access), nhận dạng cục bộ (Local Recognition), đánh giá (Validation). Tầng truy nhập Để đảm bảo tính "R-Discriminative" của tìm kiếm thực thể, nhiệm vụ của modul này xác định trọng số toàn cục p(d), là khả năng để một tài liệu d được quan sát, xét tới. Trong ngữ cảnh máy tìm kiếm với các tài liệu web, giá trị này là độ phổ biến của trang web, hay chính là độ quan trọng của trang web - hạng trang. Và do đó tác giả Tao Cheng đã chọn PageRank (PR) [43] để xác định: p(d) = PR[d]. Ta có: Score(q(t)) = ∑ d∈D PR[d]× p(q(t)|d) (3.2) CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 24 DICLOFENAC Tên gốc: Diclofenac Tên thương mại: VOLTAREN, CATAFLAM, VOLTAREN-XR Nhóm thuốc và cơ chế: Diclofenac là một thuốc chống viêm phi steroid (NSAID) hiệu quả trong điều trị sốt, đau và viêm trong cơ thể. Các NSAID là những thuốc không gây ngủ giảm các chứng đau từ nhẹ đến vừa do nhiều nguyên nhân gây ra, như chấn thương, thống kinh, viêm khớp và các chứng bệnh cơ xương khác. Vì mỗi bệnh nhân có đáp ứng khác nhau với NSAID, O1 O2 . . . Hình 3.5: Ví dụ rút trích thực thể thuốc Tầng nhận dạng Với mỗi tài liệu d được xét ở tầng truy nhập, trọng số cục bộ - xác suất xuất hiện của từng bộ thực thể t = (e1, ..., em) với các từ khóa k = {k1, ..., kl} trong tài liệu đó được xác định bởi p(q(t)|d). Gọi γ = (o1, ..., og) là một quan sát (xuất hiện) của q(t) = α(e1, ..., em, k1, ..., kl) trên d (có g = m + l). Ví dụ: trong hình 3.5 với E = {#drug}, k ="viêm", q = {"viêm"#drug} thì ta có một quan sát γ = (o1, o2). Trong mỗi tài liệu có thể có nhiều quan sát γ (tính chất R-Holistic) và do đó p(q(t)|d) cần được ước lượng trên tất cả các quan sát γ đó, [18] đưa ra công thức ước lượng: p(q(t)|d) = max γ p(α(γ)) (3.3) Với p(α(γ)) là xác suất/khả năng mà một quan sát γ phù hợp với hàm ngữ cảnh α. Tuy nhiên khi được rút trích từ tài liệu d, các quan sát oi biểu diễn một thực thể ei là một thể hiện của kiểu Ei và được xác định với một xác suất p(ei ∈ Ei|d) (tính chất R-Uncertainty). Giá trị này do modul rút trích xác định, và lưu lại trong khi đánh chỉ mục nên có thể được xác định một cách đơn giản bằng ei.conf . Vì vậy, ta có: p(α(γ)) = ∏ ei∈γ ei.conf × pcontext(α(γ) (3.4) CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 25 Thay vào công thức 3.3 suy ra: p(q(t)|d) = max γ (∏ ei∈γ ei.conf × pcontext(α(γ) ) (3.5) Theo tính chất R-Contextual, độ phù hợp của γ trong ngữ cảnh α phụ thuộc vào hai yếu tố: độ phù hợp mẫu (pattern) gọi là αB và độ gần nhau (proximity) giữa thực thể và từ khóa gọi là αP . Do đó ta có: pcontext(α(γ)) = αB(γ)× αP (γ) • αB là hàm lô-gic trả về giá trị 0 hoặc 1, cho biết quan sát γ với các oi có thỏa mãn ràng buộc về mẫu không. Ví dụ mẫu phrase(o1, ..., om) yêu cầu các oi phải xuất hiện đúng thứ tự như xác định. • αP là xác suất quan sát γ phù hợp với t trong cửa sổ quan sát s. Để đơn giản, trong [18] các tác giả đã sử dụng mô hình Span Proximity để ước lượng xác suất này, và đưa ra công thức: αP (γ) = p(s|γ). Thay vào công thức 3.5 ta được: p(q(t)|d) = max γ (∏ ei∈γ ei.conf × αB(γ)× p(s|γ) ) (3.6) Vậy công thức Score(q(t)) được xác định: Score(q(t)) = ∑ d∈D PR[d]×max γ (∏ ei∈γ ei.conf × αB(γ)× p(s|γ) ) (3.7) Tầng đánh giá Phía bên phải của mô hình (hình 3.4) gọi là một quan sát ảo, tập dữ liệu D′ được lấy ngẫu nhiên từ D để làm đối chứng so sánh những nhận định trên D. Tầng đánh giá kiểm định giả thuyết thống kê, với giả thuyết không H0 (null hypothesis) và G-test theo [18] để đánh giá độ tin cậy thông tin nhận được từ D. Giả thuyết không: giả thiết rằng liên kết giữa các thực thể, từ khóa trong t = (e1, ..., em, k1, ..., kl) xảy ra ngẫu nhiên. Tập D′ được lấy ngẫu nhiên từ tập D, D′ CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 26 cần "giống" với D ngoại trừ trong D′ liên kết của các từ khóa và các thực thể hoàn toàn là ngẫu nhiên. Xây dựng tập D′ từ D bằng việc tạo các tài liệu d′ ngẫu nhiên: Đưa ngẫu nhiên các thực thể và từ khóa vào d′, mỗi thực thể, từ khóa được đưa vào độc lập, với xác suất giống như xác suất xuất hiện của chúng trong D. Do đó mối liên hệ giữa thực thể và từ khóa là ngẫu nhiên, nhưng vẫn đảm bảo xác suất quan sát một từ khóa, hay thực thể trong D′ cũng giống như trong D: p(ei ∈ d ′) = ∑ ei∈d,d∈D p(d) ; p(kj ∈ d ′) = ∑ kj∈d,d∈D p(d) Do đặc điểm của D′ trên nên giá trị trung bình của độ tin cậy của tất cả các thực thể ej trong D cũng là độ tin cậy của các thực thể ej (xác suất ej là Ej) trong D′: ej .conf . Và ta có nếu q(t) không xuất hiện trong d′ thì p(q(t)|d′) = 0, ngược lại nếu q(t) ∈ d′ thì p(q(t)|d′) là như nhau với mọi d′. Do đó: p(q(t)|D′) = ∑ d′∈D′&q(t)∈d′ p(d′)× p(q(t)|d′) = p(q(t)|d′)× ∑ d′∈D′&q(t)∈d′ p(d′) = p(q(t)|d′)× p(q(t) ∈ d′) (3.8) Trong đó p(q(t) ∈ d′) là xác suất của t xuất hiện trong d′. Do từ khóa và các thực thể được lấy độc lập vào d′ nên xác suất xuất hiện của q(t) trong d′ được tính bởi: p(q(t) ∈ d′) = j=1∏ m p(ej ∈ d ′) l∏ i=1 p(ki ∈ d ′) Tương tự như công thức 3.5, lấy giá trị trung bình ta có: p(q(t)|d′) = ( m∏ j=1 ej.conf)× pcontext(q(t)|d ′) Trong đó, với q(t) ∈ d′, tương tự công thức tính pcontext(q(t)|d) có: pcontext(q(t)|d ′) = p(q(t)|s) Từ đó suy ra: pcontext(q(t)|d ′) = p(q(t)|s) = ∑ s p(q(t)|s) |s| CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 27 Với |s| là số các giá trị s được xét. Thay các công thức trên vào 3.8 được: p(q(t)|D′) = j=1∏ m p(ej ∈ d ′) l∏ i=1 p(ki ∈ d ′)× × ( m∏ j=1 ej .conf)× ∑ s p(q(t)|s) |s| (3.9) Sử dụng kiểm định giả thiết thống kê G-test so sánh quan sát p0 với ngẫu nhiên pr để kiểm tra quan sát p0 có phải là ngẫu nhiên không: Score(q(t)) = 2(p0 log p0 pr + (1− po) log 1− p0 1− pr ) (3.10) Do p0, pr  1 nên công thức 3.10 có thể ước lượng: Score(q(t)) ∝ p0 log p0 pr Trong đó: p0 = p(q(t)|D) = ∑ 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