Đề tài Khai phá dữ liệu song ngữ từ web

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Văn Vinh KHAI PHÁ DỮ LIỆU SONG NGỮ TỪ WEB KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công Nghệ Thông Tin Cán bộ hướng dẫn: Lê Anh Cường HÀ NỘI - 2009 1 Tóm tắt Cơ sở dữ liệu song ngữ, bao gồm các cặp văn bản song ngữ hay các cặp câu song ngữ, đóng một vai trò rất quan trọng trong nhiều ứng dụng ngôn ngữ tự nhiên, như dịch máy thống kê, xây dựng từ điển song ngữ, tìm kiếm đa ngôn ngữ. Việc xây dựng cơ sở dữ liệu này bằng tay là một việc tốn nhiều chi phí và thời gian. May mắn thay là có rất nhiều dữ liệu song ngữ ở các dạng khác nhau trên Internet. Việc khai phá ra các thành phần tương đương (song ngữ) với chất lượng cao sẽ tạo nên một cơ sở dữ liệu song ngữ rất lớn phục vụ cho nhiều ứng dụng khác nhau. Luận văn tập trung vào nghiên cứu và phát triển các kỹ thuật trong khai phá cơ sở dữ liệu song ngữ Anh-Việt từ World Wide Web (WWW), cụ thể là trên các trang web song ngữ trong định dạng html. Nhiệm vụ của khai phá dữ liệu song ngữ là tự động tìm ra hai thành phần có ngữ nghĩa tương ứng trong tập những văn bản thuộc hai ngôn ngữ khác nhau. Hai thành phần được dóng hàng hoặc được ghép cặp này càng nhỏ thì thông tin hay tri thức thu được từ đó càng lớn. Thành phần ở đây có thể là văn bản, đoạn, câu và từ,... Loại thành phần mà chúng tôi xét đến trong luận văn này là văn bản. Để ghép cặp những văn bản html trong một tập văn bản trong hai ngôn ngữ mà luận văn khai thác là tiếng Anh và tiếng Việt, chúng tôi tìm hiểu các công nghệ trong các nghiên cứu hiện tại, xác định ưu điểm nhược điểm và tính khả thi để ứng dụng trong thực tiễn luận văn này. Có hai tiếp cận đối với bài toán này là dựa trên nội dung (thông thường là dựa trên đối sánh các cặp từ là bản dịch của nhau – từ điển song ngữ), hoặc là dựa trên sự tương đồng về cấu trúc trang html. Trong phạm vi luận văn này, chúng tôi theo tiếp cận dựa trên cấu trúc. Cụ thể chúng tôi khảo sát các đặc trưng cấu trúc khác nhau như độ tương đồng cấu trúc thẻ của văn bản, độ tương đồng cấu trúc url của văn bản, và nhiều yếu tố phụ để giảm thời gian chạy của hệ thống. Đồng thời chúng tôi cũng theo tiếp cận học máy (theo [5]), và áp dụng phương pháp học cây quyết định cho bài toán này. Đặc biệt chúng tôi đã mô hình hóa bài toán cho bộ phân loại Naïve Bayes và áp dụng lựa chọn thuộc tính và cho kết quả dóng hàng văn bản tốt hơn khi sử dụng cây quyết định như trong [5]. Để thực nghiệm, chúng tôi xây dựng một hệ thống làm các nhiệm vụ: chuẩn bị cơ sở dữ liệu thô từ Internet; một số bước tiền xử lý ngôn ngữ; và các mô đun dóng hàng văn bản. Kết quả đạt được là khá khả quan với độ chính xác dóng hàng văn bản khoảng 96% đối với mô hình phân loại Bayes. 2 Mục lục Tóm tắt Mục lục Mở đầu ......................................................................................................................3 Chương 1 Giới thiệu ..................................................................................................4 1.1. Vai trò tầm quan trọng của dữ liệu song ngữ .....................................................4 1.2. Các nghiên cứu liên quan ..................................................................................5 1.3. Mục tiêu và tiếp cận giải quyết vấn đề ...............................................................9 1.4. Cấu trúc luận văn.............................................................................................10 Chương 2. Các tiếp cận và kỹ thuật cho bài toán khai phá dữ liệu song ngữ .......11 2.1. Lọc theo cấu trúc .............................................................................................11 2.2. Lọc theo nội dung............................................................................................14 2.3 Các đặc trưng khác ...........................................................................................16 2.4. Thuật toán lập trình động.................................................................................17 Chương 3. Mô hình học máy cho bài toán đối sánh văn bản.................................20 3.1 Mô hình phân loại theo cây quyết định .............................................................20 3.2. Mô hình phân loại Bayes .................................................................................24 Chương 4. Thực nghiệm và kết quả........................................................................27 4.1. Kiến trúc tổng quan hệ thống...........................................................................27 4.2. Bộ công cụ download và xác định ngôn ngữ....................................................28 4.3. Xây dựng cơ sở dữ liệu thô..............................................................................31 4.4. Xây dựng bộ phân loại và kết quả phân loại ....................................................34 4.5. Hướng dẫn sử dụng chương trình ....................................................................36 Kết luận ....................................................................................................................38 Tài liệu tham khảo 3 Mở đầu Văn bản song ngữ có vai trò thiết yếu trong một số lĩnh vực của xử lý ngôn ngữ tự nhiên, như dịch máy thống kê, tìm kiếm thông tin trong môi trường đa ngữ, Trong dịch máy thống kê, các kho dữ liệu song ngữ bao gồm nhiều cặp văn bản với chất lượng dịch cao là nguồn tài nguyên quan trọng nhất quyết định chất lượng của hệ dịch. Đối với một số cặp ngôn ngữ, việc tạo ra kho dữ liệu song ngữ là không khó (nếu như cặp ngôn ngữ đó đều phổ biến rộng rãi trên thế giới, ví dụ với cặp tiếng Anh và tiếng Pháp). Tuy nhiên thật không may cho khá nhiều cặp ngôn ngữ như Anh-Việt, trong đó có một ngôn ngữ ít phổ biến hơn như tiếng Việt, việc xây dựng các kho dữ liệu song ngữ rất khó khăn. Điều này chủ yếu do số lượng các văn bản song ngữ có thể khai thác được còn quá ít và chất lượng dịch chưa cao. Thực hiện công việc này bằng tay là một việc nặng nề và tốn kém. Đây là một trở ngại lớn cho việc phát triển các ứng dụng xử lý ngôn ngữ tự nhiên dựa trên tiếp cận thống kê, nhất là cho các cặp ngôn ngữ như Anh - Việt. Hiện nay lượng thông tin trên Internet rất lớn, và do nhu cầu giao lưu quốc tế, số lượng trang web có hai ngôn ngữ Anh và Việt cũng trở nên phổ biến hơn. Đây là nguồn tài nguyên quý giá đối với việc khai thác dữ liệu song ngữ trên Internet. Hơn nữa, đối với tiếng Việt, các nghiên cứu về khai phá tự động dữ liệu song ngữ còn ít với kết quả còn hạn chế, hầu như chưa có kho ngữ liệu song ngữ nào được công bố rộng rãi. Do vậy, việc nghiên cứu phát triển các phương pháp tự động xây dựng các kho dữ liệu song ngữ cho các cặp ngôn ngữ Anh – Việt là một chủ đề nghiên cứu rất ý nghĩa. về mặt nghiên cứu và có tính thực tiễn cao. Trong luận văn này chúng tôi giới hạn mức dữ liệu ở mức văn bản, tức là khai phá các văn bản song ngữ Anh Việt (không phải mức câu hay mức từ). Chúng tôi với luận văn này mong muốn với lý thuyết đưa ra và hệ thống thực nghiệm hi vọng sẽ đáp ứng phần nào nhu cầu về văn bản song ngữ cho cặp ngôn ngữ Anh-Việt. Cụ thể luận văn sẽ tập trung vào hai nhiệm vụ chính: Tìm hiểu, nghiên cứu, phát triển các công nghệ trong bài toán khai phá dữ liệu song ngữ, cụ thể cho xây dựng các cặp văn bản song ngữ. Xây dựng công cụ khai phá các cặp văn bản song ngữ trên world wide web cho cặp ngôn ngữ Anh –Việt. 4 Chương 1 Giới thiệu 1.1. Vai trò tầm quan trọng của dữ liệu song ngữ Văn bản song ngữ là tài nguyên ngôn ngữ giàu có cho nhiệm vụ quản lý văn bản đa ngữ khác nhau, gồm trích rút văn bản ngôn ngữ bắt chéo, khai phá văn bản đa ngữ và ngôn ngữ máy tính. Một tập văn bản song ngữ là tài nguyên cơ bản cho tạo cơ sở tri thức ngôn ngữ đa ngữ như dịch máy và từ điển theo chủ đề đa ngữ. Với sự phát triển của World Wide Web, thông tin điện tử có thể truy cập có số lượng ngôn ngữ ngày càng tăng. Có thông tin nói rằng, ở trong năm 2005, hơn 50% nội dung trang web là thuộc về những ngôn ngữ khác ngoài tiếng Anh. Với sự đa dạng như vậy, Web thực sự là tập hợp khổng lồ tài liệu đa ngữ bởi nó tạo ra nơi lưu trũ văn bản lớn cho việc xây dựng dữ liệu song ngữ. Trong xử lý ngôn ngữ tự nhiên, điều cần đặc biệt lưu ý là cần phát triển tài nguyên từ vựng chuyên sâu gổm từ vựng ( ví dụ tập từ vựng cho ngữ pháp có tính rõ ràng về mặt ngôn ngữ, cho tập mẫu cho hệ thống trích thông tin, những bản thể cho chống nhập nhằng nghĩa). Tài nguyên này là thiết yếu cho tăng khả năng của hệ thống và thay đổi giữa các lĩnh vực dễ hơn. Ví dụ, để tin cậy, một hệ thống trích thông tin cần truy cập tới từ điển ngôn ngữ chất lượng cao. Hầu hết các tài nguyên từ điển ngôn ngữ đều được phát triển bằng tay với chuyên gia tạo từ điển ngôn ngữ. Dự án như vậy là đắt đỏ và kết quả tài nguyên có mức độ bao phủ thường giới hạn, và yêu cầu tập trung mức độ cao cho miền mới. Thu thập tự động từ vựng đang hứa hẹn nhiều và tiếp cận hiệu quả để thực hành và tăng khả năng đứng vững khi có sự phát triển gần đây của xử lý ngôn ngữ tự nhiên, kỹ thuật học máy và dữ liệu trong đó dữ liệu song ngữ ngày càng phát triển và trong đó dữ liệu Anh-Việt cũng đóng góp cho các đề tài liên quan đến hai ngôn ngữ này. Cơ sở các cặp câu song ngữ đóng vai tro thiết yếu trong dịch máy thống kê. Theo [2], dịch máy thống kê là một mô hình dịch máy trong đó những bản dịch được tạo ra trên nền tảng mô hinh thống kê mà tham số của chúng đã được lấy từ sự phân tích kho văn bản song ngữ. Tiếp cận thống kê tương phản với tiếp cận dựa trên luật trong dịch máy như là dịch máy dựa trên mẫu và hiện là tiếp cận mang lại thành công nhất đối trong lĩnh vực dịch máy. Cross-language information retrieval (CLIR) là sự truy tìm những tài liệu liên quan dựa trên cơ sở những câu hỏi được đưa ra bởi con người và trả lại một tập hợp tài 5 liệu thỏa mãn câu hỏi trong những ngôn ngữ khác ngôn ngữ của câu hỏi. Hệ thống CLIR có ba hướng tiếp cận chủ yếu: dịch máy, dữ liệu song ngữ hay có tính so sánh, và từ điển mà máy có thể đọc. Đối với tiếp cận sử dụng dữ liệu song ngữ, các truy vấn được dịch trên cơ sở của mục từ được trích từ tập tài liệu song ngữ hoặc so sánh. Trong tập văn bản song ngữ, cặp hay một tập tài liệu được xác định trong những ngôn ngữ khác nhau. Một văn bản so sánh được chứa những tài liệu trong những ngôn ngữ khác nhau. Từ các mô tả những lĩnh vực và yêu cầu văn bản song ngữ của từng lĩnh vực thì chúng ta có thể thấy rằng văn bản song ngữ đóng một vai trò quan trọng trong xử lý ngôn ngữ tự nhiên. 1.2. Các nghiên cứu liên quan Web là tài nguyên khổng lồ và hầu như miễn phí cho tất cả mọi người. Và xuất phát từ nhu cầu văn bản song ngữ của các lĩnh vực khác trong xử lý ngôn ngữ tự nhiên, nhiều nhà nghiên cứu đã phát triển và xây dựng các hệ thống tự động khai phá dữ liệu song ngữ từ Web. Theo [1, 3] các website song ngữ thường đặt tên tương tự nhau cho các trang web song ngữ. Chủ website song ngữ đặt như vậy để giữ lại dấu vết của những trang web theo ngôn ngữ của chúng. Những tên trang web luôn gồm có một substring chung chỉ ra tính song song song của những trang web, cùng đi với một substring khác được sử dụng như là cờ ngôn ngữ chỉ ra ngôn ngữ của mỗi tài liệu cụ thể. Như vậy những cờ ngôn ngữ thường nối vào đằng trước, ở giữa và cuối của substring chung của cặp tài liệu song ngữ. Hơn nữa, những cờ ngôn ngữ thường được nối tới phần chung bằng các ký tự gạch ngang ‘-’ hoặc gạch dưới ‘_’. Ví dụ, khi một trang web tiếng Anh với tên là “document-en.htm” được tạo thì một bản dịch của nó trong tiếng việt sẽ là “document- vn.htm” để chỉ ra tính song song để dễ quản lý website. Ở trường hợp khác cờ ngôn ngữ chỉ được nối tới tên file của những tài liệu của một ngôn ngữ cụ thể. Ví dụ, nếu tài liệu tiếng Anh được gọi là “document.htm” được tạo thì bản tiếng Việt của nó sẽ là document-vn.htm để chỉ ra sự khác biệt ngôn ngữ. Tất cả những điều trên sẽ hỗ trợ các tài liệu web song ngữ qua được model so sánh tên file - modul quan trọng nhất trong PTMiner. PTMiner có một cách tiếp cận trong so sánh cấu trúc thẻ html của trang web. Trong tiếp cận này, hệ thống phân ra hai loại thẻ, một loại có ý nghĩa - ảnh hưởng đến cấu trúc giao diện của trang web, còn loại thẻ còn lại sẽ không có ý nghĩa tức không có 6 ảnh hưởng đến cấu trúc trang web, ví dụ: với loại có ý nghĩa: , , , ,... còn loại không có ý nghĩa: , ,..Sau khi đã chuyển sang tuyến tính (hoặc có thể tạo cây) để dóng hàng, và số đặc trưng chỉ là 1, tỉ lệ thẻ không được dóng hàng, tỉ lệ này cũng có thể tối ưu bằng học máy kết hợp với các đặc trưng khác của hệ thống. Theo [5] STRAND lấy modul so sánh cấu trúc thẻ html làm trái tim của hệ thống. STRAND có nhiều phiên bản, ở phiên bản cũ, hệ thống khai phá web qua ba bước: Locating - xác định những trang có lẽ có bản dịch song ngữ Generating - tạo các cặp thí sinh có lẽ là bản dịch Structure filtering - lọc cấu trúc bỏ ra những cặp không là bản dịch Trong bước locating, STRAND sử dụng trình tìm kiếm AltaVista để tìm kiếm hai kiểu trang web đó là: cha và anh em. Một trang cha là một trang chứa những link đến nhiều phiên bản khác nhau của một tài liệu; ví dụ: Hình 1: Ví dụ về trang cha Nhìn vào ví dụ trên, trang cha chứa link đến các phiên bản khác nhau của cùng một nội dung. Các phiên bản là tiếng Anh, tiếng Trung, tiếng Việt. Sau đó để tạo cặp trang web thí sinh thì chỉ cần lấy hai link của hai bản tiếng Việt và Tiếng Anh với nhau. Trang anh em là trang trong một ngôn ngữ và nó chứa một link đến bản đó trong ngôn ngữ khác. Ví dụ: Hình 2: Ví dụ về trang anh em Nhìn vào ví dụ trên, trang này chứa một link đến một bản khác trong tiếng Anh. Để ghép tạo cặp thí sinh thì chỉ cần ghép trang này với bản tiếng Anh tương ứng. 7 Trong bước generating, cho những cặp url có khả năng chứa bản dịch qua modul so sánh url. STRAND cũng tạo các luật để so sánh, chẳng hạn, en -> vn. Ngoài ra, trong modul này của STRAND có thêm tính năng hỗ trợ thay thế, loại bỏ nhiều đoạn trong url, ví dụ: Hình 3: Ví dụ về loại bỏ nhiều đoạn Bước structure filtering thì sẽ được trình bày ở phần lọc cấu trúc. Trong STRAND phiên bản mới có thêm modul so sánh content, sẽ trình bày ở đoạn lọc nội dung. Theo [4] PCMS nói chung là giống STRAND. Nhưng có một số điểm khác biệt. Thứ nhất, trong phần tính độ tương tự cấu trúc url của hai trang web thì hệ thống tính toán cụ thể còn STRAND và PTMiner chỉ thay thế loại bỏ kiểm tra chúng có giống nhau hay không. PCMS tiền xử lý những thư mục con trong url mà xác định ngôn ngữ của trang web. PCMS thay thế chúng bằng chuỗi ký tự duy nhất. Ví dụ url: .../english/....file.htm sẽ thành ..../***/....file.htm. Tiếp đó, một số tiêu chí được tính toán như sau: Tỉ lệ số thư mục con của url của hai trang web. Công thức là: URL diff (A, B) = )()( |)()(| BlenAlen BlenAlen   Trong công thức trên len(A) là số thư mục con của url A, và len(B) là số thư mục con của url B. Nếu số thư mục con của A và B như nhau thì tỉ lệ khác nhau sẽ là 0. Tỉ lệ thư mục con có tên giống nhau. Công thức là: 8 URL dirsim(A, B) = )()( ),(*2 BlenAlen BAcomdir  Trong công thức trên, comdir(PA,PB) là số thư mục con có tên giống nhau. Thứ hai, trong modul so sánh nội dung, PCMS triển khai mô hình không gian vecto song ngữ. Ý tưởng của mô hình này là mỗi trang web được đại diện bởi một vecto các mục từ, và tập trang web của một ngôn ngữ là một không gian vecto có số chiều bằng số từ vựng của ngôn ngữ đó. Vì số mục từ của hai ngôn ngữ bất kỳ là khác nhau nên PCMS đưa ra cách chuyển đổi số chiều của không gian vecto của ngôn ngữ này bằng số chiều của không gian vecto của ngôn ngữ kia. Và công thức cosine coefficient được sử dụng để tính độ tương tự. Công thức như sau: Cosine ecoefficient =     p i i p i i p i ii yx yx 1 2 1 2 1 * Với p là số mục từ tiếng Anh. Theo [5], modul so sánh nội dung của hai trang web là quan trọng nhất của hệ thống. Và so sánh toàn bộ nội dung được quy về so sánh đoạn, so sánh đoạn dựa trên mô hình ánh xạ từ -từ Hai đoạn đã được dóng hàng với nhau đã thỏa mãn điều kiện số từ được dóng hàng lớn hơn một ngưỡng nào đó. Tổng số từ được dóng hàng của cả trang web bằng tổng của tất cả các đoạn. Đặc trưng rút ra là số từ được dóng hàng trên tổng số từ của hai trang web. Theo [6] Một hệ thống được xây dựng, tự động khai phá dữ liệu song ngữ dựa trên dóng hàng DOM Tree. Ý tưởng này rất hay ở chỗ nó đi vào thực tế của cấu trúc html của trang web là cấu trúc cây chứ không phải là tuyến tính. Mô hình DOM Tree có nhược điểm là nắm bắt khó hơn, liên quan đến xác suất có điều kiện. Thời gian chạy của dóng hàng cây DOM nhiều hơn so với dóng hàng tuyến tính. Ví dụ về DOM Tree: Hình 4: Sự khác nhau giữa mô hình DOM chuẩn và mô hình DOM sau thu gọn 9 Mô hình dóng hàng cây DOM định nghĩa dóng hàng như tiến trình không thay đổi thứ tự cây. Ví dụ node A được dóng hàng với node B thì con của A sẽ bị xóa hoặc được dóng hàng với con của B. Để thẩm tra một cặp trang web thí sinh có đúng là song song, một bộ phân lớp dựa trên maximum entropy nhị phân được sử dụng. Tiêu chi tương đồng cấu trúc hẻ html được tính như sau: tất cả thẻ html của trang web được nối thành một chuỗi. Sau đó khoảng cách nhỏ nhất giữa hai chuỗi thẻ liên quan đến cặp thí sinh được tính toán, và độ tương đồng thẻ html là tỉ lệ số thẻ giống nhau chia cho tổng số thẻ. Điểm cho dóng hàng câu được định nghĩa là tỉ lệ số câu đã dóng hàng và tổng số câu trong cả hai file. 1.3. Mục tiêu và tiếp cận giải quyết vấn đề Với vai trò, tầm quan trọng của dữ liệu song ngữ đối với các ứng dụng xử lý ngôn ngữ tự nhiên, đồng thời được thúc đẩy bởi việc thiếu cơ sở dữ liệu song ngữ Anh -Việt cho nhiều nghiên cứu khác, luận văn tập trung vào các công việc: Tìm hiểu, nghiên cứu, phát triển các công nghệ trong bài toán khai phá dữ liệu song ngữ, cụ thể cho xây dựng các cặp văn bản song ngữ. Xây dựng công cụ khai phá các cặp văn bản song ngữ trên World Wide Web cho cặp ngôn ngữ Anh –Việt. Phần 1.2 đã trình bày một cách tóm tắt những nghiên cứu trong khai phá dữ liệu song ngữ. Có thể chia làm hai tiếp cận chính là tiếp cận dựa trên nội dung và tiếp cận dựa trên cấu trúc của trang web. Đối với tiếp cận dựa trên nội dung, chúng ta phải sử dụng từ điển song ngữ. Do việc từ điển song ngữ Anh – Việt có quá nhiều nhập nhằng, hơn nữa do thời gian có hạn nên chúng tôi tập trung vào nghiên cứu theo tiếp cận thứ hai là dựa vào cấu trúc văn bản (trang web). Phương pháp được chúng tôi sử dụng và phát triển dựa trên nghiên cứu [3,5], với hai phần: Xác định các thuộc tính dùng để đo độ tương tự giữa hai trang html Áp dụng thuật toán học máy để xây dựng mô hình trên tập các thuộc tính trên. Đối với phần thứ nhất, chúng tôi sẽ sử dụng các thuộc tính sau: So sánh độ tương đồng tên file của trang web So sánh độ tương đồng cấu trúc url 10 So sánh cấu trúc html của cặp trang web Và một số tiêu chí khác để làm giảm thời gian chạy của hệ thống như ngày sửa, tỉ lệ âm tiết, tỉ lệ chunk. Đối với thuật toán học máy, chúng tôi mô hình hóa và áp dụng cho hai thuật toán là Naïve Bayes và Decision Tree (cây quyết định). 1.4. Cấu trúc luận văn Chương 1. Giới thiệu vai trò của dữ liệu song ngữ và bài toán khai phá dữ liệu song ngữ đặt ra. Chương 2. Đưa ra lý thuyết về các đặc trưng có thể trích ra các đặc trưng có thể dùng làm đặc trưng phân loại. Chương 3. Mô hình học máy cho bài toán đối sán h văn bản Chương 4. Đưa ra kiến trúc hệ thống dùng để thực nghiệm và kết quả phân loại Kết luận đánh giá kết quả hướng phát triển của hệ thống 11 Chương 2. Các tiếp cận và kỹ thuật cho bài toán khai phá dữ liệu song ngữ 2.1. Lọc theo cấu trúc Trên World Wide Web tồn tại nhiều dữ liệ