Tài liệu Khóa luận 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 ...
40 trang |
Chia sẻ: haohao | Lượt xem: 1207 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Khóa luận Khai phá dữ liệu song ngữ từ web, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
ĐẠ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
KHỐ 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 tố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
tốn này. Đặc biệt chúng tơi đã mơ hình hĩa bài tốn cho bộ phân loại Nạ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 tố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 tốn lập trình động.................................................................................17
Chương 3. Mơ hình học máy cho bài tố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 tố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 ngồ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. Ngồ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 tố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
tố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 tồ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 tố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 tố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 tố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 tốn học máy, chúng tơi mơ hình hĩa và áp dụng cho hai thuật
tốn là Nạ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 tố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 tố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 tố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 ngồi chứa phần liên kết từ trang này đến trang kia <a
href="">Wikipedia sẽ hiển thị từ Wikipedia như
là một liên kết ngồ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:
12
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 tố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
13
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 tố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 =
)
)(
)(
)(
(
2
2
2
2
N
Y
Y
N
X
X
N
YX
XY
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
14
H0: = 0
HA: # 0
< 0
> 0
Tính giá trị kiểm định:
t =
2
1 2
n
r
pr
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.
15
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 tố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 E sao
cho mỗi đỉnh cĩ tối đa một cạnh trong M và Me hic , là lớn nhất. Thuật tốn MWBM
chạy nhanh nhất với độ phức tạp O(ve + v 2 logv) . Áp dụng tới bài tốn này thì độ
phức tạp là O(max(|X|,|Y|) 3 ) , ở đâ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
16
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 =
) matchingbest in links allPr(log
matching)best in links word-Pr(two log
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 =
matchingbest in links ofnumber
matchingbest in links word- twoofnumber
và
tsim =
wordof sum
matchingbest in links word- twoofnumber * 2
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
tốn MCBM cĩ độ phức tạp thời gian là O(e v ) hay O(|X|.|Y|. |||| YX , 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 tốn cĩ thời gian chạy tốt là thuật tốn tham ăn. Thuật tố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 tố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
Ngồ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
17
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ì ngồ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 tốn lập trình động
Quy hoạch động là thuật tố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. Ngồ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 tố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 tốn lớn thơng qua
18
nghiệm của các bài tố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 tốn con. Thuật tốn
được thiết kế bằng kỹ thuật quy hoạch động sẽ là thuật tố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 tố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 tố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 tố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 tốn
thơng qua nghiệm của các bài tốn con.
Thiết kế bảng để lưu nghiệm của các bài tốn con.
Tính nghiệm của các bài tốn con từ nhỏ đến lớn và lưu vào bảng.
Sau đây, chúng ta sẽ đưa ra thuật tốn được thiết kế bằng kỹ thuật quy hoạch
động cho bài tố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].
19
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.
20
Chương 3. Mơ hình học máy cho bài tố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ự đố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 tố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 tố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.
21
Thuật tố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
22
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ư tồ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ể đố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
23
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) =
c
i
ii pp
1
2log
ở đâ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
AValuesv
v SEntropy
S
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.
24
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
i
ii
S
S
S
S
1 2 ||
||
log
||
||
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 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
25
Á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 tốn được
giống như xác suất.
Với Bayes ngây thơ ngồ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) = )()(
)true/Cva ...vava(
2211
nn2211 trueCP
vavavaP
P
nn
P(C=false/ a1=v1a2=v2... an=vn) = )()(
)false/Cva ...vava(
2211
nn2211 falseCP
vavavaP
P
nn
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)
26
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 .
27
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 tồ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 tố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.
28
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
29
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
30
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
31
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).
32
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, ngồ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.
33
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%
34
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.
35
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
Tồ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à tồ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 tố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
36
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
Tồ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.
37
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.
38
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 hồn thiện hơn.
39
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.
Các file đính kèm theo tài liệu này:
- LUẬN VĂN-KHAI PHÁ DỮ LIỆU SONG NGỮ TỪ WEB.pdf