Luận văn Khai phá dữ liệu song ngữ từ Web

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ó ả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. 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) = 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à: URL dirsim(A, B) = 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 = 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 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 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 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ệu, và nhiều kiểu định dạng dữ liệu, chẳng hạn htm, xhtml, doc, pdf,... và luận văn chỉ sử dụng văn bản định dạng html – trang web (có thể là html động khi download lưu vào ổ cứng nó có thêm đuôi html, ví dụ: *.cfm.html). Các trang web có nền tảng là text, có chứa thẻ đánh dấu, chỉ thị cho chương trình về cách hiển thị hay xử lý văn bản. Trong html có bốn loại phần tử đánh dấu: Đánh dấu có cấu trúc miêu tả mục đích của phần văn bản (ví dụ, Golf sẽ điều khiển phần mềm đọc hiển thị "Golf" là đề mục cấp một), Đánh dấu trình bày miêu tả phần hiện hình trực quan của phần văn bản bất kể chức năng của nó là gì (ví dụ, boldface sẽ hiển thị đoạn văn bản boldface). Đánh dấu liên kết ngoài chứa phần liên kết từ trang này đến trang kia Wikipedia sẽ hiển thị từ Wikipedia như là một liên kết ngoài đến một url). Các phần tử thành phần điều khiển giúp tạo ra các đối tượng (ví dụ, các nút và các danh sách) Bên dưới trang web là các thẻ html và văn bản thuần túy. Trong tiếp cận cấu trúc, có 2 kỹ thuật nhỏ: Thứ nhất, chỉ quan tâm đến các thẻ cấu trúc và điều khiển giống như lọc cấu trúc của hệ thống PTMiner. Thứ hai, tất cả thẻ có ảnh hưởng đến cái nhìn được từ phía người dùng, tức loại bỏ các comment trong file html. Để việc dóng hàng tốt hơn, việc phân biệt nonmarkup text và markup text là cần thiết. thuộc tính của thẻ là nonmarkup text hiển thị là markup text. Modul so sánh cấu trúc thực hiện hai bước sau: Bước 1: chuyển các thẻ nội dung của file html thành cấu trúc tuyến tính hay chuỗi tuần tự của các từ tố của các thẻ cho các trang web của hai ngôn ngữ mà hệ thống quan tâm ở đây là Anh và Việt, với modul này nội dung trang web được đưa về chuỗi của bốn loại từ tố: [start:label], label là tên thẻ html, ví dụ, [start:html], [start:script] [end:label] [chunk:length], length số ký tự khác ‘trắng’ của văn bản đánh dấu [chunka:length], length số ký tự khác ‘trắng’ của văn bản không đánh dấu Còn các yếu tố khác trong html như chú thích thì nó không ảnh hưởng nhiều đến sự tương đồng của hai trang web nên bị loại bỏ khi chuyển sang tuyến tính. Ví dụ: source: COLTECH sẽ được chuyển tuyến tính thành [start:font], [chunka:9], [chunk:7],[end:font]. Bước 2: dóng hàng hai chuỗi từ tố đại diện cho hai trang web song ngữ việc dóng hàng dùng thuật toán quy hoạch động sẽ được trình bày bên dưới. Ví dụ: Source trang web: Hình 5a: Ví dụ về source trang web Chuỗi từ tố: Hình 5b: Ví dụ về dóng hàng hai chuỗi từ tố cho hai văn bản Sau khi dóng hàng, để xác định hai trang web đưa ra có là bản dịch hay không thì cần phải có thông số để có thể tạo các quyết định với thông số này. Và bốn thông số được đưa ra kiểm nghiệm chất lượng dóng hàng trang web: dp: tỉ lệ từ tố không được dóng hàng n: số từ tố [chunka:length] đã dóng hàng nhưng độ dài length không bằng nhau r: độ tương quan độ dài của văn bản nonmarkup đã được dóng hàng. Chính là tương quan length trong [chunka:length] p: độ tin cậy của r Tỉ lệ khác nhau dp với ý nghĩa khác là chỉ ra lỗi của những từ tố trong chuỗi tuyến tính ở một bên không tương ứng với từ tố nào bên chuỗi còn lại. Từ ví dụ trên, một bên chứa H1 header nhưng không có trong bên văn bản kia. Lượng lớn lỗi như vậy sẽ chỉ ra hai tài liệu không có chất liệu giống nhau đủ để suy xét xem có phải là bản dịch hay không. Điều này có thể xảy ra, ví dụ, khi hai tài liệu đều là bản dịch của một, nhưng một tài liệu có nhiều nội dung hơn cái còn lại, thì dĩ nhiên tỉ lệ khác nhau là cao và là cặp thí sinh tồi. Số chunk văn bản không đánh dấu đã được dóng hàng chỉ ra chất lượng của dóng hàng. Thuật toán lập trình động cố gắng tối ưu việc dóng hàng đối với văn bản đánh dấu. Bên cạnh đó, chunk văn bản không đánh dấu sẽ tương ứng với chunk khác. Với hai tham số còn lại r và p chỉ ra các chunk văn bản không đánh dấu có tương quan theo độ dài không. Khi hai tài liệu được dóng hàng với cái khác là bản dịch, thì đáng tin cậy hơn nếu cái nào có mối tương quan tuyến tính theo độ dài của chunk văn bản không đánh dấu: ngắn đi với ngắn, trung bình đi với trung bình, dài đi với dài. Chỉ số tương quan Pearson được đưa ra chỉ ra mối quan hệ độ dài của chunk văn bản không đánh dấu, giá trị của p chỉ ra độ tin cậy của r. Trong luận văn này p được chọn 0.01. Công thúc của r như sau: r = Khi đã có r và p thì phải kiểm định giả thiết, các bước kiểm định giả thiết, Giả thuyết không và giả thuyết đối nghịch H0: = 0 HA: # 0 < 0 > 0 Tính giá trị kiểm định: t = Xác định giá trị khởi tạo tcritical từ bảng Pearson: Critical values for Pearson r Xem trong “critical r Pearson.bmp” Với df = n-1 thì : Với df = n – 2 thì: . tcritical = tα,df . tcritical = tα,df Tạo quyết định Nếu |t| > tcritical từ bỏ H0 Ngược lại không bác bỏ H0 Kết luận Nếu bác bỏ H0, giá trị r được chấp nhận, có tồn tại mối tương quan giữa độ dài. Nếu không bác bỏ H0, giá trị r không được chấp nhận, không tồn tại mối tương qua giữa hai độ dài. 2.2. Lọc theo nội dung Khi mà các tiêu chí đại diện cho độ tương đồng cấu trúc html của trang web không phát huy hiệu quả thì các tiêu chí tương đồng nội dung của trang web sẽ là lựa chọn tốt cho kiểm tra một cặp có đúng là bản dịch không. Tiếp cận này đưa ra chỉ số tốt hơn so với so chỉ số cấu trúc tài liệu, bởi vì nó đi thẳng vào vấn đề. Hai trang web là bản dịch của nhau tức là nội dung của trang này là bản dịch sang ngôn ngữ khác của nội dung trang kia. Như Ma và Liberma chỉ ra rằng không phải tất cả bản dịch trong giống bản gốc. Hơn nữa tương đồng theo cấu trúc chỉ áp dụng cho tập dữ liệu có đánh dấu, và chắc chắn rằng nhiều bộ sưu tập đa ngôn ngữ trên www tồn tại nhiều văn bản song ngữ không có cấu trúc thẻ. Cuối cùng, những ứng dụng khác cho phát hiện những bản dịch vẫn tiếp tục được nghiên cứu như dóng hàng văn bản tài liệu con, phát hiện trùng lặp. Tất cả nhận xét trên chỉ ra rằng tiếp cận theo content không phục thuộc vào độ tương đồng cấu trúc. Dưới dây chỉ ra cách tính chỉ số độ tương đồng nội dung. Chúng ta định nghĩa chỉ số tương đồng nội dung là tsim cho hai văn bản theo mô hình đối xứng từ-từ của văn bản song ngữ. Theo đó một link là một cặp (x,y) với x là từ trong ngôn ngữ L1 và y là từ trong ngôn ngữ L2. Mô hình chứa một từ điển song ngữ có chứa xác suất của tất cả kiểu link. Trong đó có một kiểu đặc biệt, là một từ có thể là Null, nhưng không thể cả hai. Mô hình này không quan tâm đến trật tự từ. Một ví dụ như sau: Hình 6: Ví dụ về hai văn bản có những link giữa các từ Tiếp theo tính xác suất của chuỗi link có khả năng lớn nhất như thế nào. Xác suất này có thể tính đơn giản là tổ hợp từ các xác suất những link có thể có. Theo [5] thì tập link tốt nhất là bài toán MWBM(maximum-weighted bipartie matching): có đồ thị có trọng số G = (V1 U V2, E), với trọng số ci,j (i € V1, j € V2) , phải tìm M sao cho mỗi đỉnh có tối đa một cạnh trong M và là lớn nhất. Thuật toán MWBM chạy nhanh nhất với độ phức tạp O(ve + vlogv) . Áp dụng tới bài toán này thì độ phức tạp là O(max(|X|,|Y|)) , ở đây X và Y là độ dài của văn bản tính theo từ. Để sử dụng MWBM tìm chuỗi link có khả năng lớn nhất, những từ L1 là V1 và L2 là V2 . Nếu hai từ x,y có xác suất p(x,y) > 0, một link sẽ tồn tại nối chúng lại với nhau với trọng số là log p(x,y), nếu một từ x, y là NULL với xác suất khác không thì một link được cộng vào đồ thị giữa x (y) và đỉnh NULL được cộng tới V2 (V1). Mỗi x hoặc y có thể liên kết tới NULL làm cho có nhiều link tới NULL. Một tổng trọng số của các link sẽ là xác suất tính theo log của chuỗi link đó, và là lớn nhất tổng các xác xuất. Tsim là cao khi nhiều link trong chuỗi tốt nhất không có đỉnh NULL. Hơn nữa nên được chia cho độ dài của văn bản. Bởi vậy: tsim = Một công thức đơn giản khác được áp dụng là coi tất cả từ vựng có xác suất bằng nhau. Giả định này đưa ra cộng thức cho tsim là : tsim = và tsim = Hai công thức này ý nghĩa là như nhau. Lý do tính tsim với giả định xác suất bằng nhau là vì chúng ta không cần tính MWBM, nhưng có thể tìm thấy MCBM(maximum cardinality bipartite matching) từ đây tất cả link có thể có đều có trong số như nhau. Thuật toán MCBM có độ phức tạp thời gian là O(e) hay O(|X|.|Y|., với X, Y như công thức trên. Ví dụ như hình 2 ta có tsim(X,Y) = 7/9. Một thuật toán có thời gian chạy tốt là thuật toán tham ăn. Thuật toán tham ăn sẽ chọn trong những cạnh còn lại một cạnh có trọng số lớn nhất, và bỏ ra khỏi đồ thị. Độ phức tạp của thuật toán tham ăn là O(max(X,Y)log max(X,Y)). Nếu các link có trọng số như nhau thì đơn giản là lấy ngẫu nhiên các cạnh đến khi không thể lấy được nữa. Với công thức tsim và giả định xác xuất như nhau thì ta có thể dùng lập trình động với hai chuỗi từ của hai văn bản. 2.3 Các đặc trưng khác Ngoài các yếu tố tương đồng cấu trúc html và tương đồng nội dung thì ta còn có thể tận dụng các yếu tố sau: Ratio n: có nghĩa là tỉ lệ số chunk văn bản không đánh dấu đã dóng hàng có độ dài không bằng nhau chia cho tổng số chunk văn bản không đánh dấu đã dóng hàng. Yếu tố này tại sao lại có ý nghĩa? Là vì giả sử nếu hai văn cùng được tạo cặp với một cái khác và đều có n = 10; nhưng tổng số chunk không đánh dấu khác nhau thì cặp nào có tổng số lớn hơn sẽ có ưu thế hơn trong việc chọn cặp vì như vậy tức tỉ lệ khác nhau ít hơn so với trang web còn lại. Ratio size file: kích thước file ở đây được tính theo số byte thực sự. tỉ lệ này cũng cung cấp một chỉ số đáng tin cậy. Nếu tỉ lệ này quá lớn thì cặp này đương nhiên sẽ bị loại bỏ. Date distance: Một file bản dịch của một file khác thường thì được up lên www cùng một thời gian hoặc chênh lệch ít. Nếu hai file cách nhau quá xa chẳng hạn như 1 tháng hoặc năm chẳng hạn dĩ nhiên là bỏ. Xin lưu ý ở đây là ngày modify chứa không phải ngày tạo vì khi ta download một file về thì ngày tạo chính là ngày nó được download về. File name similarity: thương các trang web lớn và song song thì ngoài cấu trúc thư mục thì cả tên file cũng song song thậm chí là giống nhau nếu thư mục khác nhau. Bởi vậy chỉ số này rất tốt cho phân loại đối với web site tuân thủ chặt chẽ về tên file. Chẳng hạn với www.undp.org.vn Directory number difference và directory name similarity, các web site song ngữ thường có cấu trúc thư mục phân cấp và song song, hai yếu tố này phản ánh phần nào sự song song đó. Thường thì các tên thư mụ là tương tự nhau chỉ trừ thư mục chỉ ngôn ngữ. Với ratio sylllable number và ratio chunk number: với ratio chunk number thì quá rõ bởi vì tỉ lệ dp không cho thấy sự tỉ lệ số chunk giữa hai trang web là bao nhiêu. Với ratio chunk làm nổi bật sự giống nhau về chunk. Ví dụ với 9, 10 chunk thì dp = 1 / 19, ratio chunk = 9/10 rõ ràng ratio chunk rõ rệt hơn (coi như dóng hàng tối đa). Ratio syllable number– tỷ lệ số âm tiết cũng như vậy nếu sự khác biệt là lớn thì cặp đang xét cũng sẽ bị bỏ qua. 2.4. Thuật toán lập trình động Quy hoạch động là thuật toán chính trong luận văn này nó được áp dụng nhiều lần để tính nhiều tiêu chí khác nhau. Nó được dùng để dóng hàng chuỗi từ tố của trang web phục vụ tính các đặc trưng tương đồng cấu trúc. Ngoài ra, nó cũng được dùng để tính một số đặc trưng liên quan đến tương đồng tên file, tương đồng cấu trúc thư mục của url. Bởi vậy thật quan trọng nghiên cứu quy hoạch động áp dụng vào lập trình. Quy hoạch động là kỹ thuật bottom-up, tính nghiệm của các bài toán từ nhỏ đến lớn và ghi lại các kết quả đã tính được. Khi tính nghiệm của bài toán lớn thông qua nghiệm của các bài toán con, ta chỉ việc sử dụng các kết quả đã được ghi lại. Điều đó giúp ta tránh được phải tính nhiều lần nghiệm của cùng một bài toán con. Thuật toán được thiết kế bằng kỹ thuật quy hoạch động sẽ là thuật toán lặp, điều này tiết kiệm thời gian chạy của hệ thống rất nhiều . Để thuận tiện cho việc sử dụng lại nghiệm của các bài toán con, chúng ta lưu lại các nghiệm đã tính vào một bảng. Tóm lại, để giải một bài toán bằng quy hoạch động, chúng ta cần thực hiện các bước sau: Đưa ra cách tính nghiệm của các bài toán con đơn giản nhất. Tìm ra các công thức (hoặc các quy tắc) xây dựng nghiệm của bài toán thông qua nghiệm của các bài toán con. Thiết kế bảng để lưu nghiệm của các bài toán con. Tính nghiệm của các bài toán con từ nhỏ đến lớn và lưu vào bảng. Sau đây, chúng ta sẽ đưa ra thuật toán được thiết kế bằng kỹ thuật quy hoạch động cho bài toán dóng hàng hai chuỗi từ tố. Trường hợp đơn giản nhất khi một trong hai dãy a và b rỗng (m = 0 hoặc n = 0), ta thấy ngay dãy con chung dài nhất là dãy rỗng. Ta xét các đoạt đầu của hai dãy a và b, đó là các dãy (a1,a2,…,ai) và (b1,b2,…,aj) với 0 ≤ i ≤ m và 0 ≤ j ≤ n. Gọi L(i,j) là độ dài lớn nhất của dãy con chung của hai dãy (a1,a2,…,ai) và (b1,b2,…,aj). Do đó L(n,m) là độ dài lớn nhất của dãy con chung của a và b. Bây giờ ta đi tìm cách tính L(i,j) thông qua các L(s,t) với 0 ≤ s ≤ i và 0 ≤ t ≤ j. Dễ dàng thấy rằng: L(0,j) = 0 với mọi j L(i,0) = 0 với mọi i (1) Nếu i > 0 và j > 0 và ai # bj thì L(i,j) = max [L(i,j-1), L(i-1,j)] (2) Nếu i > 0 và j > 0 và ai = bj thì L(i,j) = 1 + L(i-1,j-1) (3) Sử dụng các công thức đệ quy (1), (2), (3) để tính các L(i,j) lần lượt với i = 0,1,…,m và j = 0,1,…,n. Chúng ta sẽ lưu các giá trị L(i,j) vào mảng L[0..m][0..n]. Công việc tiếp theo là từ mảng L ta xây dựng dãy con chung dài nhất của a và b. Giả sử k = L[m][n] và dãy con chung dài nhất là c = (c1,…ck-1, ck). Ta xác định các thành phần của dãy c lần lượt từ phải sang trái, tức là xác định ck, rồi ck-1,…,c1. Ta xem xét các thành phần của mảng L bắt từ L[m,n]. Giả sử ta đang ở ô L[i][j] và ta đang cần xác định cr, (1 <= r <= k). Nếu ai = bj thì theo (3) ta lấy cr = ai, giảm r đi 1 và đi đến ô L[i-1][j-1]. Còn nếu ai # bj thì theo (2) hoặc L[i][j] = L[i][j-1], hoặc L[i][j] = L[i-1][j]. Trong trường hợp L[i][j] = L[i][j-1] ta đi tới ô L[i][j-1], còn nếu L[i][j] = L[i-1][j] ta đi tới ô L[i-1][j]. Tiếp tục quá trình trên ta xác định được tất cả các thành phần của dãy con dài nhất. Nhưng xin lưu ý rằng ý nghĩa ai = bj khác bình thường một chút, ở đây ai, bj là hai từ tố trong chuỗi tuyến tính nên ai = bj được định nghĩa là hoặc ai = bj hoặc ai, bj là chunk text có thể thể là không hoặc có đánh đâu nhưng phải thỏa mãn cùng loại tức cả hai cùng là văn bản đánh dấu hoặc cùng không. Chương 3. Mô hình học máy cho bài toán đối sánh văn bản 3.1 Mô hình phân loại theo cây quyết định Giải thuật học cây quyết định Sau đây sẽ là phần trình bày cây quyết định ID3 và một số cải tiến giải thuật tăng khả năng học. ID3 là biểu diễn khái niệm ở dạng cây quyết định. Biểu diễn này cho phép chúng ta xác định phân loại của một đối tượng bằng cách kiểm tra các giá trị của nó trên một số thuộc tính nào đó. Như vậy nhiệm vụ giải thuật ID3 là học cây quyết định từ một tập các ví dụ huấn luyện. Và giải thuật cây quyết định có: Đầu vào là một tập dữ liệu huấn luyện mỗi ví dụ trong tập có tập giá trị cho tập các thuộc tính trong đó có một thuộc tính đích Đầu ra là các cây quyết định phân loại đúng với các ví dụ trong tập dữ liệu và có thể phân loại (dự đoán) đúng với cả ví dụ trong tương lai. Cây quyết định là cây mà root và node trong là đại diện một thuộc tính, mỗi cạnh được gán một giá trị của thuộc tính của node phía trên, leaf được gán nhãn true hoặc false. Giải thuật ID3 xây dựng cây quyết định từ trên – xuống ID3 xây dựng cây quyết định từ trên xuống. Lưu ý rằng đối với bất kỳ thuộc tính nào, chúng ta cũng có thể phân vùng tập hợp các ví dụ rèn luyện thành những tập con tách rời, mà ở đó mọi ví dụ trong một phân vùng có giá trị chung cho thuộc tính đó. ID3 chọn một thuộc tính để kiểm tra tại nút hiện tại của cây và dùng thuộc này để phân vùng tập ví dụ thành những tập con; thuật toán khi đó xây dựng theo đệ quy một cây con cho từng phân vùng. Việc này tiếp tục cho đến khi một ví dụ của phân vùng đều thuộc vào một lớp (nhãn), và lớp (nhãn) đó trở thành nút lá của cây. Vì thứ tự của các thuộc tính là quan trọng đối với việc xây dựng một cây quyết định đơn giản, ID3 phụ thuộc rất nhiều vào tiêu chuẩn chọn lựa trắc nghiệm để làm gốc của cây. Trước hệ chúng tôi sẽ trình bày thuật toán xây dựng cây quyết định ID3, và việc làm thế nào chọn thuộc tính làm root tại mỗi lần đệ quy sẽ được tình bày trong phần tiếp theo. Thuật toán xây dựng cây quyết định từ tập huấn luyện và tập thuộc tính: Function DecisionTree(tập_huấn_luyện, tập_thuộc_tính) begin if mọi ví dụ đều thuộc trong cùng một lớp s then return nút lá gán nhãn s else if tập thuộc tính là rỗng then return nút này gán cái nhãn chiếm đa số trong tập_huấn_luyện else begin chọn một thuộc tính P từ tập_thuộc_tính làm gốc cho cây hiện tại xóa P ra khỏi tập thuộc tính với mỗi giá trị v của P begin tạo một nhánh có nhãn là v đặt vào phân_vùng_v các ví dụ trong tập_huấn_luyện có giá trị v của thuộc tính P if phân_vùng_v là rỗng then gắn nút có nhãn chiếm đa số trong tập_huấn_luyện vào nhánh v else gọi DecisionTree(phân_vùng_v, tập_thuộc_tính) gắn vào nhánh v end end end Trong quá trình xây dựng cây quyết định , phân vùng của một nhánh mới ở vào một trong những trường hợp sau: Tập ví dụ của một phân vùng có nhiều hơn một loại nhãn -> giải thuật tiếp tục đệ quy xây dựng cây con. Tất cả các ví dụ đều thuộc cùng một lớp, chẳng hạn như toàn true hoặc false -> node là với nhãn của phân vùng được trả về. Phân vùng không có ví dụ nào -> giải thuật trả về số nhãn tối đa trong tập mẫu của cây cha. Không còn thuộc tính nào -> nghĩa là dữ liệu bị nhiễu, khi đó giải thuật phải sử dụng luật nào đó để xử lý, chẳng hạn luật đa số, lớp nào có nhiều ví dụ hơn sẽ được dùng để gán nhãn cho nút lá trả về. Ta thấy rằng để có một cây quyết định đơn giản, hay một cây có chiều cao là thấp, ta nên chọn một thuộc tính sao cho tạo ra càng nhiều phân vùng chỉ chứa các ví dụ thuộc cùng một lớp càng tốt. Một phân vùng chỉ gồm có ví dụ thuộc cùng một lớp (nhãn), ta nối phân vùng đó có tính thuần nhất. Vậy để cây quyết định có kích thước nhỏ ta cần phương pháp để xác định thuộc tính tốt nhất cho việc tạo ra càng nhiều phân vùng thuần nhất càng tốt. ID3 sử dụng lý thuyết thông tin để tìm thuộc tính phân loại tốt nhất. Thuộc tính nào dùng để phân loại tốt nhất Một tập hợp là thuần nhất nếu như tất cả các phần tử của tập hợp đều thuộc cùng một loại, và khi đó ta nói tập hợp này có độ pha trộn là thấp nhất. Khi tập ví dụ là thuần nhất thì có thể nói: ta biết chắc chắn về nhãn của một ví dụ thuộc tập này, hay ta có lượng thông tin về tập đó là cao nhất. Khi tập ví dụ có độ pha trộn cao nhất, nghĩa là số lượng các ví dụ ở tất cả các nhãn là như nhau, thì khi đó ta không thể đoán chính xác một ví dụ trong tập này có nhãn là gì hay nói cách khác là lượng thông tin của tập mẫu này là ít nhất. Vậy làm thế nào chọn thuộc tính chia tập ví dụ ban đầu thành các tập con thuần nhất càng nhanh càng tốt. Và lý thuyết thông tin đã đưa ra cách tính độ thuần nhất của một tập hợp: entropy. Entropy đo tính thuần nhất của một tập ví dụ Khái niệm entropy của một tập S được định nghĩa trong lý thuyết thông tin là số lượng bít cần thiết để mã hóa thông tin của một lớp trong tập ví dụ. Trong trường hợp tối ưu , mã có độ dài ngắn nhất. Theo lý thuyết thông tin mã có độ dài tối ưu là mã gán –log2p bít cho lớp có xác suất là p. Entropy đo độ thuần nhất của tập dữ liệu, công thức tổng quát là: Entropy(S) = ở đây pi là xác suất của lớp i trong tập dữ liệu S. Giá trị của entropy thuộc đoạn [0,1] Nếu Entropy(S)=0 tức là tập dữ liệu thuần nhất. Nếu Entropy(S)=1 tức tập dữ liệu hỗn tạp nhất tất cả lớp đều có xác suất bằng nhau. Tóm lại Entropy(S) càng nhỏ thì tập ví dụ càng thuần nhất. Với c=2 ta có đồ thị của Entropy(S): Hình 7: đồ thị của Entropy với dữ liệu có hai nhãn Với mỗi thuộc tính, nó chia tập ví dụ S thành các tập con Sv thì lượng thông tin thu được information gain là: Gain(S,A) = Entropy(S) - Với mô hình cây quyết định, đôi khi xảy ra hiện tượng “quá khớp” hiện tượng này do dữ liệu ít phân bố không theo đúng tỉ lệ của mỗi giá trị của mỗi thuộc tính, để khắc phục hiện tượng này người ta lại chia tập huấn luyện thành 2 tập là tập huấn luyện và tập phê chuẩn. Người ta tìm cây thỏa mãn size(decision tree) + size(missclassifications(tree)) trên tập phê chuẩn, hoặc dừng không khai triển node trong nào có inforgain nhỏ nhất trong quá trình tạo cây. Với thuộc tính có nhiều giá trị thì càng nhiều giá trị càng kém tính khái quát bởi vậy một đơn vị đo khác được đưa ra đó là gainratio: GainRaio(S,A) = Gain(S,A) / SplitInformation(S,A) với SplitInformation(S,A) = - Cách phân loại của cây quyết định, với mỗi cặp trang web có tập giá trị tương ứng với tập thuộc tính, các giá trị của các thuộc tính này sẽ đi theo các nhánh của cây đã được xây dựng khi nào đến lá thì dừng và sẽ có nhãn tương ứng nhãn của lá. 3.2. Mô hình phân loại Naive Bayes Định lý Bayes cho phép tính xác suất xảy ra của một sự kiện ngẫu nhiên A khi biết sự kiện liên quan B đã xảy ra. Xác suất này được ký hiệu là P(A|B), và đọc là "xác suất của A nếu có B". Đại lượng này được gọi xác suất có điều kiện hay xác suất hậu nghiệm vì nó được rút ra từ giá trị được cho của B hoặc phụ thuộc vào giá trị đó. Theo định lí Bayes, xác suất xảy ra A khi biết B sẽ phụ thuộc vào 3 yếu tố: Xác suất xảy ra A của riêng nó, không quan tâm đến B. Kí hiệu là P(A) và đọc là “xác suất của A”. Đây được gọi là xác suất biên duyên hay xác suất tiên nghiệm, nó là "tiên nghiệm" theo nghĩa rằng nó không quan tâm đến bất kỳ thông tin nào về B. Xác suất xảy ra B của riêng nó, không quan tâm đến A. Kí hiệu là P(B) và đọc là "xác suất của B". Đại lượng này còn gọi là hằng số chuẩn hóa (normalising constant), vì nó luôn giống nhau, không phụ thuộc vào sự kiện A đang muốn biết. Xác suất xảy ra B khi biết A xảy ra. Kí hiệu là P(B|A) và đọc là "xác suất của B nếu có A". Đại lượng này gọi là khả năng (likelihood) xảy ra B khi biết A đã xảy ra. Chú ý không nhầm lẫn giữa khả năng xảy ra A khi biết B và xác suất xảy ra A khi biết B. Khi biết ba đại lượng này, xác suất của A khi biết B cho bởi công thức: Từ đó dẫn tới Áp dụng Naive Bayes cho mô hình phân loại của luận văn Những ứng dụng của Bayes thường được dựa trên một giả thuyết có tính triết học Bayesian probability ngầm định rằng độ bất định và kỳ vọng có thể tính toán được giống như xác suất. Với Bayes ngây thơ ngoài giả thuyết Bayes, thì còn giả thuyết ngây thơ, giả thuyết ngây thơ là các đặc trưng của cặp trang web là độc lập với nhau. Áp dụng cho xây dựng mô hình ngôn ngữ: Gọi C là lớp hay nhãn của cặp thí sinh. Giá trị của C là true hoặc false. Còn tập thuộc tính ký hiệu As tương ứng với một tập các đặc trưng hay tiêu chí phân lớp, tức là: As = a1 a2 ... an Mỗi ai có thể nhận một giá trị nguyên vj As = v1v2...vn. Vậy với mỗi cặp trang web, việc được gán nhãn gì thì phục thuộc vào hai xác suất có điều kiện sau: P(C=true/a1=v1a2=v2... an=vn) và P(C=false/a1=v1a2=v2... an=vn) Xác suất nào lớn hơn thì cặp trang web đó sẽ có nhãn tương ứng. Theo định lý Bayes ta có: P(C=true/ a1=v1a2=v2... an=vn) = P(C=false/ a1=v1a2=v2... an=vn) = Khi so sánh hai xác suất P(C=true/As=v1v2...vn) và P(C=false/As=v1v2...vn), vế phải của khai triển Bayes có mẫu chung ta có thể bỏ qua. Chỉ cần so sánh tử thôi. Vì có giả định ngây thơ là các đặc trưng độc lập với nhau, nên ta có: P(a1=v1a2=v2... an=vn/C=true)P(C=true) = P(a1=v1/C=true) P(a2=v2/C=true)... P(an=vn/C=true) P(C=true) P(a1=v1a2=v2... an=vn/C=false)P(C=false) = P(a1=v1/C=false) P(a2=v2/C=false)... P(an=vn/C=false) P(C=false) Từ đó ta chỉ cần tính xác suất từng thành phần ở bên phải, sau đó tích lại và so sánh xem cái nào lớn hơn thì gán nhãn tương ứng. Ta có các xác suất thành phần được tính dựa trên thống kê: P(C=true) = count(nhãn true) / số cặp trong tập huấn luyện. P(a1=v1/C=true) = count(nhãn true, có thuộc tính a1 có giá trị v1) / count(nhãn true). P(a2=v2/C=true) = count(nhãn true, có thuộc tính a2 có giá trị v2) / count(nhãn true). ...... P(an=vn/C=true) = count(nhãn true, có thuộc tính an có giá trị vn) / count(nhãn true). P(C=false) = count(nhãn false) / số cặp trong tập huấn luyện. P(a1=v1/C=false) = count(nhãn false, có thuộc tính a1 có giá trị v1) / count(nhãn false). P(a2=v2/C=false) = count(nhãn false, có thuộc tính a2 có giá trị v2) / count(nhãn false). ...... P(an=vn/C=false) = count(nhãn false, có thuộc tính an có giá trị vn) / count(nhãn false). Và mô hình ngôn ngữ Bayes chính là tất cả xác suất ở trên cho tất cả giá trị của tất cả thuộc tính trong hai class true và false, với mẫu bất kỳ, ví dụ: (input= u1u2...un) thì nhãn của ví dụ này sẽ là gì phụ thuộc vào kết quả của hai biểu thức: P(a1=u1/C=false) P(a2=u2/C=false)... P(an=un/C=false) P(C=false) và P(a1=u1/C=true) P(a2=u2/C=true)... P(an=un/C=true) P(C=true) Cách tính mỗi thành phần như trên hoặc tìm trong nơi lưu trữ các xác suất thành phần và lấy ra giá trị phù hợp, chẳng hạn P(a1=u1/C=false) = P(a1=v1/C=false) với v1=u1 . Chương 4. Thực nghiệm và kết quả 4.1. Kiến trúc tổng quan hệ thống Sơ đồ kiến trúc tổng quan Hình 8: Sơ đồ kiến trúc hệ thống Bước 1,2: hệ thống dùng tool GNU Wget để dowload toàn bộ file html tĩnh và động của website nào đó về máy. Bước 3,4: bước này làm nhiệm vụ tính toán tất cả thông số, đưa vào dữ liệu ban đầu, đồng thời với bộ lọc thô sẽ làm giảm kích thước dữ liệu làm giảm thời gian chạy cho các giai đoạn sau. Dữ liệu trong “Data with indexes” là các cặp trang web trong hai ngôn ngữ Anh-Việt cùng với chỉ số của các đặc trưng chính và phụ Bước 5,6: Để có hệ thống tốt thì cần phải có mô hình huấn luyện và kiểm tra, bước này có nhiệm vụ tạo dữ liệu huấn luyện, và kiểm tra bằng cách lấy ngẫu nhiên. Sau đó dùng cây quyết định, và Bayes ngây thơ Bước 7,8: Với mô hình đã có, tất cả dữ liệu ban đầu sẽ được đi qua, và kết quả cuối cùng sẽ ở Parallel text. 4.2. Bộ công cụ download và xác định ngôn ngữ Download Có hai cách tìm kiếm và download những website tiếng Việt Thứ nhất, làm bằng tay, tìm kiếm và xác định các địa chỉ website song ngữ Anh-Việt, sau đó dùng tool GNU Wget để download cả trang web đó về. Thứ hai, chạy tự động dùng tool GNU Wget download ở mỗi site của một trang web một số lượng nào đó, và nếu tồn tại số lượng trang web tiếng Anh-Việt lớn hơn giới hạn nào đó thì download cả trang web đó về. Luận văn này sử dụng cách thứ nhất, với mỗi địa chỉ website tiếng Việt chúng tôi thực hiện trong cửa sổ command line câu lệnh: wget.exe -r -nc -x -E --reject css,js,jpg,gif,wmv,wma pdf,mp3,mp4 -i urls.txt hoặc cũng có thể liệt kê những địa chỉ đó vào một file và dùng câu lệnh wget.exe -r -nc -x -E --reject css,js,jpg,gif,wmv,wma,pdf,mp3,mp4 url Một số website đã download xong, một số thì chưa. Kết quả download như sau: Bảng 1: Các websites và số lượng trang web tiếng Anh, tiếng Việt đã down được Số thứ tự website song ngữ số trang web tiếng Anh số trang web tiếng Việt 1 www.honda.com.vn 27 465 2 www.undp.org.vn 1652 1278 3 www.na.gov.vn 6352 5184 4 www.vietnamtourism.com 1410 1234 5 www.vietnamnet.vn và english.vietnamnet.vn 2060 17549 6 www.toyotavn.com.vn 8 169 7 www.cpv.org.vn 1920 16640 8 www.vietnamgateway.org:100 441 8640 9 www.nhandan.com.vn 453 3263 10 ww.voanews.com 2587 2863 11 www.bbc.co.uk và news.bbc.co.uk 6274 1232 12 ukinvietnam.fco.gov.uk 447 255 Xác định ngôn ngữ Thường trong các website song ngữ, các substring chỉ tính song song thì cũng là chỉ ngôn ngữ của trang web đó. Bởi vậy, nếu trong url của webpage có chứa thông tin liên quan đến ngôn ngữ tiếng Anh hoặc tiếng Việt thì sẽ được cho url trang web vào danh sách ngôn ngữ tương ứng. Trong khóa luận, dùng các substring định nghĩa trước, nếu một trong substring được tìm thấy trong url, thì ngôn ngữ trang sẽ tương ứng với substring đó. Chúng tôi dùng các substring sau: Substring là sự kết hợp của english, eng, en, e, tienganh, vietnamese, vietnam, vn, v, tiengviet, các substring kết hợp với .*., \*\, \*., _, -, lang=, language=. Bảng sau đây là những substring được tạo ra: Bảng 2a: Những substring ngôn ngữ có thể có trong url của trang web  Ngôn ngữ .*. \*\ \*. _* English .english. \english\ \english. _english Eng .eng. \eng\ \eng. _eng En .en. \en\ \en. _en E .e. \e\ \e. _e tienganh .tienganh. \tienganh\ \tienganh. _tienganh vietnamese .vietnamese. \vietnamese\ \vietnamese. _vietnamese vietnam .vietnam. \vietnam\ \vietnam. _vietnam Vn .vn. \vn\ \vn. _vn V .v. \v\ \v. _v tiengviet .tiengviet. \tiengviet\ \tiengviet. _tiengviet Và Bảng 2b: Những substring ngôn ngữ có thể có trong url của trang web  Ngôn ngữ *_ *- -* lang= language= English _english english- -english lang=english language=english Eng _eng eng- -eng lang=eng language=eng En _en en- -en lang=en language=en E _e e- -e lang=e language=e Tienganh _tienganh tienganh- -tienganh lang=tienganh language=tienganh Vietnamese _vietnamese vietnamese- -vietnamese lang=vietnamese language=vietnamese Vietnam _vietnam vietnam- -vietnam lang=vietnam language=vietnam Vn _vn vn- -vn lang=vn language=vn V _v v- -v lang=v language=v Tiengviet _tiengviet tiengviet- -tiengviet lang=tiengviet language=tiengviet Chẳng hạn, ngay một số url website chứa substring nêu trên: , ... Đếm số âm tiết Nếu trong url của trang web không có thông tin ngôn ngữ, thì với cách xác định ngôn ngữ bằng cách đếm số âm tiết của từng ngôn ngữ Anh và Việt. Sau đó tính tier lệ số âm tiết trên tổng số âm tiết của cả trang web(gồm cả âm tiết không phải là của tiếng Anh lẫn tiếng Việt) và xác định giới hạn của những tỉ lệ này. Việc xác định giới hạn này, chúng tôi sau nhiều lần khảo sát bằng tay đã gán như sau: Đặt te là tỉ lệ âm tiết của tiếng anh, đặt tv là tỉ lệ âm tiết tiếng việt, ta có điều kiện xác định ngôn ngữ như sau: Nếu tv > 0.7 và te < 0.3 thì webpage đó là tiếng việt Nếu không te > 0.7 và tv < 0.2 thì webpage đó là tiếng anh Bằng kết hợp substring ngôn ngữ và đếm số âm tiết, số lượng trang web tiếng Anh và tiếng Việt như bảng 1. 4.3. Xây dựng cơ sở dữ liệu thô Thông số lọc thô Chúng tôi tạo ra cặp thí sinh bằng cách ghép mỗi trang tiếng Anh với tất cả trang tiếng Việt trong một site. Vì vậy số cặp thí sinh là rất lớn. Và Bộ lọc thô có nhiệm vụ xác định giới hạn rộng, nhưng vẫn đảm bảo lọc bỏ nhiều cặp thí sinh để cho những giai đoạn sau giảm thời gian chạy của hệ thống. Tất cả đặc trưng (thuộc tính) được tận dụng để lọc thô. Các giới hạn (biên) để lọc thô, được thiết lập rộng bằng tay, nên không phải kiểm nghiệm nhiều. Sau đây là những đặc trưng và giới hạn (biên) để lọc thô: Tỉ lệ kích thước (tính theo byte) của hai trang web, thường thì các câu tiếng Anh khi được dịch sang tiếng Việt sẽ thành câu dài hơn, tương ứng thì kích thước trang web tiếng Việt thường lớn hơn nên giá trị thiết lập là: low = 0.8, high = 1.25. Khoảng cách thực ra trong hệ thống được tính theo mili giây nhưng chúng tôi quy về ngày. Khoảng cách ngày hai webpage tiếng anh được modify và up lên khác nhau nhỏ hơn max là 7.0 ngày. Tỉ lệ giống nhau giữa hai tên file. Với những website tuân thủ chặt chẽ tỉ lệ này thì cũng rất có lợi nếu chỉ xét những website này, nhưng vì nhiều website không chặt về đặc trưng này nên đặc trưng này không lọc được nhiều lắm. Ví dụ về tên hai trang web, index_en.html và index.html dùng lập trình động sẽ đưa ra kết quả là 0.8695652173913043. Biên của đặc trưng này là min = 0.3. Tỉ lệ giống nhau của tên các thư mục con. Cách tính như sau lấy số tên thư mục con giống nhau nhân hai chia cho tổng số thư mục con, nên nhớ tên thư mục con sẽ được thay thế bằng xâu cố định nếu tên thư mục chỉ ra ngôn ngữ của trang web. Ví dụ: ...\htx\english\c1330\ và ...\htx\vietnamese\... Khi cho hai xâu chỉ thư mục con này qua tiền xử lý sẽ trở thành: ...\htx\***\c1330\ và ...\htx\***\... Sau đó dùng lập trình động để tìm ra phần chung và tính độ tương đồng và kết quả là 2 * 2 / (3 + 2) = 0.8 với việc dóng hàn htx – htx, *** – *** (english – vietnamese). Giá trị biên được thiết lập cho đặc trưng này là min = 0.1. Tỉ lệ khác nhau của số thư mục con. Với đặc trưng này, chúng tôi coi rằng đã là trang web song ngữ thì cấu trúc thư mục là có cấu trúc song song. Đặc tính thể hiện hai trang web nằm trong cấu trúc song song và khác nhau không quá xa. Cách tính lấy trị tuyệt đối hiệu số thư mục con chia cho tổng số thư mục con của url của hai trang web. Ví dụ: ...\htx\english\c1330\ và ...\htx\vietnamese\... Chỉ cần đếm và tính kết quả là |5 – 4| / 5 = 0.2. Giá trị biên của đặc trưng tương đồng số thư mục con là max = 0.334. Tỉ lệ số âm tiết của hai webpage, âm tiết được tách bởi ký tự không phải chữ cái và không phải là ‘-’, bởi vậy số âm tiết là số âm tiết của tất cả ngôn ngữ. Giá trị biên của đặc trưng này là: low = 0.3, high = 1.25. tại sao lại lệch so với 1.0 thế? Là vì tỉ lệ ở đây là số âm tiết của trang tiếng Anh chia cho số âm tiết của trang tiếng Việt mà một câu tiếng Việt là bản dịch thì thường có độ dài hơn câu tiếng Anh. Tỉ lệ số chunk. Đặc trưng này rất có ý nghĩa là vì đã là bản dịch thì việc cấu trúc thẻ tương tự nhau thì khi dóng hàng số chunk cũng tương tự nhau. Nếu hai trang web có số chunk lệch nhau quá lớn thì không thể là bản dịch được. Giá trị biên của đặc trưng này là: low = 0.7, high = 1.35. Một trang web mà số chunk quá ít hoặc số âm tiết quá nhỏ thì không có ý nghĩa cho các lĩnh vực khác bởi vậy lọc số chunk, số âm tiết là cần thiết để tiết kiệm thời gian cho hệ thống. Còn nếu số chunk mà quá lớn thì khi dóng hàng lập trình động cần lượng bộ nhớ lớn để lưu trữ. Cũng tương tự với văn bản của trang web mà quá lớn nếu không cẩn thận thì khi dóng hàng nội dung hoặc dóng hàng câu của các ứng dụng khác không chạy được vì thiếu bộ nhớ. Bằng kiểm tra và trong quá trình thực hành giá trị biên dần được điều chỉnh cho phù hợp và giá trị của biên là số âm tiết min = 40; số min chunk là 20, max số chunk là 15000. Tuy bốn đặc trưng dp, n, r,p thể hiện chất lượng dóng hàng, nhưng qua đây ta cũng có thể lọc chúng để cho kích thước cặp thí sinh giảm xuống cho cả phần lọc cấu trúc và lọc nội dung (nếu hệ thống có). Chúng tôi gán cố định cho p là 0.01 để đảm bảo độ chặt chẽ của r. Bởi vậy qua tham khảo và kiểm nghiệm một số cặp chúng tôi đặt các biên rộng một chút đảm bảo không lọc lỗi các cặp là bản dịch. Cụ thể là: max dp = 0.25, max n = 40, min r = 0.9, ngoài ra một thông số n chia cho tổng số text nonmarkup đã được dóng hàng với biên là max 0.25. Kết quả lọc thô Kết quả sau khi sau xác định ngôn ngữ , tạo cặp và lọc thô ta có tương ứng với mỗi website có số lượng cặp trang web thí sinh như sau: Bảng 3: Các website và số lượng, tỉ lệ cặp thí sinh Số thứ tự website song ngữ số cặp thí sinh Tỉ lệ so với tổng số cặp thí sinh 1 www.honda.com.vn 42 0.1% 2 www.undp.org.vn 23545 56.25% 3 www.na.gov.vn 18169 43.40% 4 www.vietnamtourism.com 10 0.024% 5 www.vietnamnet.vn và english.vietnamnet.vn 0 0% 6 www.toyotavn.com.vn 16 0.038% 7 www.cpv.org.vn 0 0% 8 www.vietnamgateway.org:100 0 0% 9 www.nhandan.com.vn 0 0% 10 www.voanews.com 14 0.033% 11 www.bbc.co.uk và news.bbc.co.uk 0 0% 12 ukinvietnam.fco.gov.uk 65 0.155% tổng số 41861 100% 4.4. Xây dựng bộ phân loại và kết quả phân loại Chương này chính là thực hiện các bước 5,6,7,8 trong sơ đồ tổng quan hệ thống hình 8. Chuẩn bị dữ liệu Từ 41861 cặp trang web thí sinh, chúng tôi lấy ngẫu nhiên 5000 cặp huấn luyện và 1000 cặp test không giống với bất kỳ cặp huấn luyện nào. Sau đó chúng tôi gán nhãn bằng tay cho tất cả cặp huấn luyện và cặp test. Sau khi gán nhãn, thống kê cho thấy: trong tập huấn luyện có 687 cặp có nhãn true, trong tập test có 128 cặp nhãn true. Dữ liệu huấn luyện: teaching/teaching và teaching/teaching-labeled Dữ liệu kiểm tra: teaching/testing và teaching/testing-labeled Mỗi cặp thí sinh đều có thông số cho tất cả thuộc tính, theo đúng thứ tự sau: Bảng 4: Thuộc tính (đặc trưng) và thứ hạng theo sự xắp sếp sẵn 0 1 2 3 4 dp n ration r sizeratio 5 6 7 8 9 10 datedistance filenamesim dirnumdiff dirnamesim wordratio chunkratio Từ đây số được thay thế cho tên thuộc tính ví dụ thuộc tính 0 chính là dp, thuộc tính 6 chính là filenamesim,... Mô hình cây quyết định Từ các dữ liệu huấn luyện, chúng tôi xây dựng mô hình bằng tool jaDTi-0.5.1 của Jean-Marc Francois để tạo mô hình. Chúng tôi xây dựng hai mô hình, mô hình thứ nhất chỉ gồm ba thuộc tính, mô hình thứ hai gồm tất cả thuộc tính. Hai mô hình được tạo ra và chứa trong hai file là teaching/teaching-labeled3.dot và teaching/teaching-labeled11.dot tương ứng, sau đó chúng tôi dùng tool Graphviz 2.22 để từ mô hình tạo mô phỏng cây quyết định trong hai file ảnh: teaching/teaching-labeled3.jpg và teaching/eaching-labeled3.jpg. Kết quả trực quan thấy rằng cây quyết định dùng tất cả thuộc tính nhỏ hơn gọn hơn cây quyết định dùng ba thuộc tính dp, n, r. Kết quả thống kê trong bảng sau: Bảng 5: Độ chính xác và recall của decision tree số lượng thuộc tính sử dụng precision recall số lượng cặp song ngữ 3 0.55932203 0.515625 5221 11 0.92741935 0.898438 5404 Toàn bộ cặp song ngữ lấy từ dữ liệu ban đầu nằm trong hai file tương ứng với hai bộ thuộc tính: ./data3.paired, ./data11.paired Mô hình Naive Bayes Trước khi tạo được mô hình Naive Bayes, chúng ta phải chuẩn hóa các giá trị của từng thuộc tính. Và việc chuẩn hóa cần thông số gap khoảng cách của từng thuộc tính. Giá trị những gap được thiết lập bằng tay, qua nhiều lần kiểm nghiệm. Kiểm nghiệm bằng cách, mỗi lần chỉ cho tạo mô hình Naive Bayes, và cho chạy trên tập test, tính precison và recall, đối với mỗi thuộc tính, nếu precison và recall vẫn tăng thì gap của thuộc tính đó bị chia nhỏ cho đến khi precision và recall không tăng., hoặc tăng không đáng kể so với tỉ lệ gap bị chia nhỏ (gap càng nhỏ thì số lượng giá trị của thuộc tính đó càng nhiều, dữ liệu càng bị phân mảnh, cây quyết định giảm đi tính khái quát) . Dữ liệu huấn luyện đã chuẩn hóa: teaching/teaching-labeled-standarded Dữ liệu test đã chuẩn hóa: teaching/testing-labeled-standarded Riêng đối với Naive Bayes, chúng tôi thiết kế hệ thống để với bất kỳ tổ hợp thuộc tính nào cũng đưa ra được precison, recall và toàn bộ cặp song ngữ trong giữa liệu ban đầu. Chúng tôi đưa ra 2 bộ thuộc tính để tính toán precison và recall, bộ thứ nhất gồm dp, n, r và bộ ai gồm filenamesim và dirnamesim (6 và 8), bộ có recall và precision cao nhất được liệt kê trong file teaching/combinning-attributes.prerec Kết quả thống kê trong bảng sau: Bảng 6: Độ chính xác và recall của Naive Bayes số lượng thuộc tính sử dụng precision recall số lượng cặp song ngữ 3 0.44339622641509435 0.3671875 4718 Tối ưu 2 (6,8) 0.967479674796748 0.9296875 5198 Toàn bộ cặp song ngữ lấy từ dữ liệu ban đầu nằm trong hai file tương ứng với hai bộ thuộc tính: ./ data-nb013.paired, ./ data-nb68.paired 4.5. Hướng dẫn sử dụng chương trình Cài đặt tool/wget-1.11.4-1-setup.exe Chạy từ command line hoặc dùng wget.exe -r -nc -x -E --reject css,js,jpg,gif,wmv,wma -i urls.txt Hoặc wget.exe -r -nc -x -E --reject css,js,jpg,gif,wmv,wma url Urls.txt chứa các sites mà bạn muốn download, url là site mà bạn muốn download. Sử dụng: java -Xms128m -Xmx1300m -jar StructureIndexes.jar Với là path của input_example_sites.txt để dóng hàng và tạo các chỉ số khác chi tiết xem file output, trong config/input_example_sites.txt Sử dụng: java -jar CreatingData.jar Với là path của input_teaching.txt để tạo dữ liệu training và testing chi tiết xem file input_teaching.txt. Sử dụng: java -Xmx1300m -jar jaDTi-0.5.1.jar để tạo mô hình cây quyết định, thống kế độ chính xác, tạo file dot, list tất cả cặp thỏa mãn, chọn 11 (tất cả thuộc tính) hoặc 3 chỉ chọn dp, n, r làm thuộc tính tạo cây. trỏ đến thư mục chứa tất cả dữ liêu. Dùng tool/graphviz-2.22.2.msi để từ file .dot chứa mô hình tạo cây có cái nhìn trực quan hơn. Sử dụng: java -jar NaiveBayes.jar Với trỏ đến naivebayes-1.txt hoặc naivebayes-2.txt hoặc naivebayes-3.txt nếu muốn thống kê độ chính xác recall của tất tổ hợp thuộc tính hay đưa ra danh sách tất cả cặp song ngữ từ cặp dự thí ban đầu hay thống kê độ chính xác và recall của một tổ hợp thuộc tính cụ thể có ở trong file config. Kết luận Chúng tôi đã tìm hiểu, nghiên cứu những công nghệ mới nhất như mô hình DOM tree, so sánh cấu trúc html, so sánh content, của những trang web. Xây dựng hệ thống khai phá dữ liệu song ngữ trên world wide web cho cặp ngôn ngữ Anh –Việt. Tuy vậy do nhiều nguyên nhân nên hệ thống tích hợp không hết những công nghệ mới nhất mà chỉ đến so sánh cấu trúc html và sử dụng một số tiêu chí khác như tương đồng cấu trúc url, tên file,.... Kết quả đạt được là khả quan, dùng cây quyết định thì độ chính xác 92,74%, còn Naive Bayes thì 96,74%. Định hướng phát triển, tích hợp thêm tiêu chí tương đồng nội dung và điều chỉnh lại hệ thống cho hoàn thiện hơn. Tài liệu tham khảo [1] Van B. Dang, Ho Bao-Quoc. 2007. Automatic Construction of English-Vietnamese Parallel Corpus through Web Mining. Proceedings of 5th IEEE International Conference on Computer Science - Research, Innovation and Vision of the Future (RIVF’2007), Hanoi, Vietnam. [2] Christopher D. Manning and Hinrich Schütze Foundations of Statistical Natural Language Processing. MIT Press, 1999 [3] Jian-Yun Nie, Jiang Chen, Exploiting the Web as Parallel Corpora for Cross language Information Retrieval, 2008 [4] Bo li, Juan Liu, Mining Chinese-English Parallel Corpora from the Web [5] P. Resnik and N. A. Smith. 2003. The Web as a Parallel Corpus. Computational Linguistics, 2003, [6] Lei Shi, Cheng Niu, Ming Zhou, Jianfeng Gao. 2006. A DOM Tree Alignment Model for Mining Parallel Data from the Web. ACL 2006.