TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM

KHOA CÔNG NGHỆ THÔNG TIN

THUYẾT MINH ĐỀ TÀI NCKH CẤP TRƯỜNG ĐỀ TÀI NGHIÊN CỨU KĨ THUẬT ĐÁNH GIÁ ĐỘ TƯƠNG ĐỒNG VĂN BẢN ỨNG DỤNG TRONG SO SÁNH VĂN BẢN TIẾNG VIỆT

Chủ nhiệm đề tài: Thành viên tham gia: Th.S NGUYỄN KIM ANH Th.S TRỊNH THỊ NGỌC HƯƠNG

Hải Phòng, tháng 05/2016

MỤC LỤC

MỤC LỤC ....................................................................................................................... 2

DANH SÁCH HÌNH ẢNH ............................................................................................. 4

DANH SÁCH BẢNG BIỂU ........................................................................................... 5

MỞ ĐẦU ......................................................................................................................... 6

CHƯƠNG I: TỔNG QUAN VỀ ĐỀ TÀI ....................................................................... 7

1.1. Lý do chọn đề tài ............................................................................................ 7

1.2. Mục đích nghiên cứu ...................................................................................... 7

1.3. Đối tượng nghiên cứu ..................................................................................... 7

1.4. Phương pháp nghiên cứu ................................................................................ 7

CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT ................................... 9

2.1. Bài toán so sánh văn bản ................................................................................ 9

2.2. Đặc điểm ngôn ngữ tiếng Việt ...................................................................... 10

2.2.1. Cấu tạo từ tiếng Việt ................................................................................. 10

2.2.2. Biến hình từ tiếng Việt .............................................................................. 11

2.2.3. Từ đồng nghĩa ........................................................................................... 11

2.2.4. Đặc điểm chính tả ...................................................................................... 12

2.2.5. Bảng mã tiếng Việt trên máy tính ............................................................. 12

2.3. Hướng tiếp cận cho bài toán so sánh văn bản tiếng Việt ............................. 13

2.3.1. Tiền xử lý văn bản tiếng Việt .................................................................... 13

2.3.2. Phương pháp tính độ tương đồng giữa các văn bản .................................. 14

2.3.3. Hướng tiếp cận cho bài toán so sánh văn bản tiếng Việt .......................... 16

CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT .............................. 18

3.1. Mô hình biểu diễn văn bản truyền thống ...................................................... 18

3.1.1. Mô hình logic ................................................................................................ 18

3.1.2. Mô hình vector .............................................................................................. 19

3.2. Mô hình đồ thị biểu diễn văn bản ................................................................. 22

3.2.1. Mô hình đồ thị khái niệm .............................................................................. 22

3.2.2. Mô hình đồ thị hình sao ................................................................................ 23

3.2.3. Mô hình đồ thị vô hướng sử dụng tần số xuất hiện ...................................... 23

3.2.4. Mô hình đồ thị có hướng, cạnh không gán nhãn .......................................... 24

3.3.5. Mô hình đồ thị có hướng, cạnh không gán nhãn, cạnh là khoảng cách n giữa hai từ trong văn bản ................................................................................................ 24

CHƯƠNG IV: PHƯƠNG PHÁP TÍNH ĐỘ TƯƠNG ĐỒNG VĂN BẢN .................. 26

4.1. Khái niệm độ tương đồng ............................................................................. 26

4.2. Độ tương đồng văn bản dựa trên tập từ chung ............................................. 26

4.2.1. Khoảng cách Jaro ...................................................................................... 26

4.2.2. Mô hình tương phản (Contrast model) ...................................................... 27

4.2.3. Hệ số Jaccard ............................................................................................. 27

4.3. Độ tương đồng văn bản dựa trên vector biểu diễn ....................................... 27

4.3.1. Độ tương đồng Cosine .............................................................................. 27

4.3.2. Độ tương đồng dựa vào khoảng cách Euclide .......................................... 28

4.3.3. Độ tương đồng dựa vào khoảng cách Manhattan ..................................... 28

4.4. Độ tương đồng văn bản trong tiếng Việt ...................................................... 29

4.4.1. Độ tương tự ngữ nghĩa từ - từ ................................................................... 29

4.4.2. Độ tương tự ngữ nghĩa của văn bản .......................................................... 30

4.4.3. Độ tương tự về thứ tự của từ trong văn bản .............................................. 31

4.4.4. Kết hợp giữa các độ đo để đánh giá độ tương tự giữa hai văn bản ........... 32

CHƯƠNG V: ỨNG DỤNG MÔ HÌNH ĐỒ THỊ ......................................................... 33

5.1. Mô hình hệ thống .......................................................................................... 33

5.1.1. Tiền xử lý .................................................................................................. 33

5.1.2. Xử lý từ ..................................................................................................... 33

5.1.3. * Vector hóa văn bản ................................................................................. 35

5.1.4. *Tính độ tương tự văn bản ........................................................................ 36

5.2. Mô hình thực nghiệm.................................................................................... 38

5.2.1. Môi trường thực nghiệm ........................................................................... 38

5.2.2. *Chương trình ứng dụng thử nghiệm ........................................................ 38

5.2.3. *Kết quả thử nghiệm ................................................................................. 38

KẾT LUẬN ................................................................................................................... 39

TÀI LIỆU THAM KHẢO ............................................................................................. 40

DANH SÁCH HÌNH ẢNH

Hình 1: Mô hình vector biểu diễn văn bản .................................................................... 19 Hình 2: Ví dụ mô hình đồ thị khái niệm ........................................................................ 22 Hình 3: Ví dụ mô hình đồ thị hình sao .......................................................................... 23 Hình 4: Ví dụ mô hình đồ thị vô hướng sử dụng tần số xuất hiện ................................ 24 Hình 5: Ví dụ mô hình đồ thị đơn giản .......................................................................... 24 Hình 6: Ví dụ mô hình đồ thị khoảng cách n đơn giản ................................................. 25 Hình 7: Mô hình hệ thống so sánh văn bản tiếng Việt .................................................. 33 Hình 8: Chương trình thử nghiệm so sánh độ tương tự văn bản ................................... 38

DANH SÁCH BẢNG BIỂU

Bảng 1: Tần suất xuất hiện độ dài từ tiếng Việt trên vdict.com .................................... 11 Bảng 2: Biểu diễn văn bản trong mô hình Logic........................................................... 18 Bảng 3: Vector biểu diễn văn bản ................................................................................. 20

MỞ ĐẦU

Hiện nay, với sự phát triển bùng nổ của các ứng dụng trên Internet, dữ liệu văn bản đã tăng nhanh cả về số lượng và nội dung. Trong kho dữ liệu ấy, một lượng lớn là văn bản tiếng Việt. Tuy nhiên, các nghiên cứu về khai thác thông tin trên văn bản tiếng Việt lại chưa nhiều so với tiếng Anh, hầu hết sử dụng các phương pháp đã đề xuất cho tiếng Anh để áp dụng sang tiếng Việt. Do đặc điểm của ngôn ngữ tiếng Việt có nhiều điểm khác so với ngôn ngữ tiếng Anh nên việc áp dụng các phương pháp ấy còn nhiều hạn chế.

Mục tiêu của đề tài là nghiên cứu mô hình biểu diễn văn bản tiếng Việt, các kỹ thuật tính độ tương đồng nhằm cải tiến các phép đo tương đồng và ứng dụng vào thiết kế, xây dựng thử nghiệm một số phần chức năng của hệ thống so sánh trên văn bản tiếng Việt.

Nội dung báo cáo gồm:

 Chương 1: giới thiệu tổng quan về đề tài, mục đích và nội dung nghiên

cứu.  Chương 2: trình bày đặc điểm ngôn ngữ tiếng Việt và phương pháp cho bài toán so sánh trên văn bản tiếng Việt.  Chương 3: trình bày các mô hình biểu diễn văn bản truyền thống và mô hình đồ thị, ứng dụng mô hình trong biểu diễn văn bản tiếng Việt.  Chương 4: trình bày phương pháp tính độ tương tự và những cải tiến trên văn bản tiếng Việt.  Chương 5: trình bày thiết kế hệ thống so sánh độ tương tự trong văn bản tiếng Việt.

Cuối cùng đề tài đưa ra một số kết luận về kết quả thực hiện và đề xuất các

hướng nghiên cứu trong tương lai.

Thuyết minh ĐT NCKH

CHƯƠNG I: TỔNG QUAN VỀ ĐỀ TÀI

CHƯƠNG I: TỔNG QUAN VỀ ĐỀ TÀI

1.1. Lý do chọn đề tài

Trong các loại dữ liệu thì dữ liệu văn bản là dạng phổ biến nhất. Ngày nay, với sự phát triển mạnh mẽ của Internet, dữ liệu văn bản đã trở nên phong phú về nội dung và tăng nhanh về số lượng. Chỉ bằng một vài thao tác đơn giản, tại bất kì đâu, tại bất kì thời điểm nào, ta cũng có thể nhận về một khối lượng khổng lồ các trang web và các tài liệu điện tử liên quan đến nội dung tìm kiếm. Chính sự dễ dàng này cũng mang đến cho chúng ta rất nhiều khó khăn trong việc chắt lọc ra các thông tin được coi là mới, là riêng, là hữu ích giữa các tài liệu ấy.

Cho đến thời điểm hiện tại, khai phá dữ liệu văn bản trong tiếng Anh đã có rất nhiều công trình nghiên cứu và đạt được nhiều kết quả. Nhìn một cách tổng quan, hầu hết các nghiên cứu này đều dựa vào mô hình biểu diễn văn bản dạng vector và tính toán dựa trên xác suất thống kê thông tin trọng số của các từ trong văn bản. Do các đặc điểm của tiếng Việt khác với tiếng Anh, phương pháp trên có nhược điểm là chưa quan tâm tới vấn đề ngữ nghĩa của văn bản như mối quan hệ giữa các từ/cụm từ, tần số, vị trí hoặc các từ …

1.2. Mục đích nghiên cứu

Nghiên cứu tổng quan vấn đề xử lý văn bản và một số phương pháp so sánh độ tương đồng câu đã được áp dụng và thu được kết quả khả quan như phương pháp tính độ tương đồng sử dụng độ đo Cosine, độ đo khoảng cách Euclide…

Nghiên cứu đặc điểm của văn bản tiếng Việt, xây dựng mô hình biểu diễn văn bản tiếng Việt nhằm cải tiến các phép đo tương đồng và ứng dụng vào thiết kế, xây dựng thử nghiệm một số phần chức năng của hệ thống so sánh trên văn bản tiếng Việt.

1.3. Đối tượng nghiên cứu

- Nghiên cứu một số mô hình tính toán độ tương đồng văn bản cả về cú pháp và ngữ nghĩa, xác định mức tương đồng văn bản ở cấp độ từ, câu, đoạn văn hay toàn bộ văn bản và ứng dụng trong tiếng Việt.

- Nghiên cứu phương pháp biểu diễn văn bản tiếng Việt và xây dựng đồ thị liên kết biểu diễn văn bản, tính độ tương tự giữa các văn bản dựa trên mô hình biểu diễn.

- Xây dựng ứng dụng thử nghiệm so sánh trên văn bản tiếng Việt, hỗ trợ đánh giá

việc sao chép bài điện tử.

1.4. Phương pháp nghiên cứu

Tìm hiểu, khảo sát và hệ thống hóa các kết quả nghiên cứu đã có về vấn đề độ

7

tương đồng văn bản và các ứng dụng đối với tiếng Việt.

Thuyết minh ĐT NCKH

CHƯƠNG I: TỔNG QUAN VỀ ĐỀ TÀI

Nghiên cứu lý thuyết về mô hình tính độ tương đồng văn bản, mô hình biểu diễn văn bản và ứng dụng các mô hình vào thiết kế, xây dựng thử nghiệm hệ thống so sánh độ tương đồng giữa các văn bản tiếng Việt.

8

Thực nghiệm trên các dữ liệu mẫu để đánh giá hệ thống.

Thuyết minh ĐT NCKH

CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT

CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT

2.1. Bài toán so sánh văn bản

Hiện nay, tình trạng sao chép, vi phạm bản quyền và gian dối, chống đối trong các kết quả học tập, nghiên cứu diễn ra khá sôi nổi và khó kiểm soát. Đặc biệt trong lĩnh vực giáo dục – đào tạo, việc người học tham khảo và chép bài của nhau là phổ biến, làm giảm khả năng tư duy và chất lượng nghiên cứu, học tập. Vấn đề đặt ra là làm thế nào để xác định được phép đo độ giống nhau giữa các văn bản, trên cơ sở đó đưa ra những kết luận về việc sao chép bài điện tử, làm căn cứ để phân loại và đánh giá kết quả bài luận, nghiên cứu của người học.

Thực tế đã có một số nghiên cứu đề xuất các phương pháp khác nhau đề xác định xem một đoạn văn bản của một tài liệu có nằm trong một tài liệu nào khác không. Các phương pháp này chủ yếu dựa trên tìm kiếm và so khớp chuỗi, tuy nhiên so khớp chuỗi chỉ có hiệu quả nếu việc sao chép là “nguyên văn”. Việc sao chép có sửa đổi như thay thế một số từ bằng từ đồng nghĩa hay thay đổi thứ tự các câu trong văn bản cần các phương pháp khác hiệu quả hơn.

Trong xử lý ngôn ngữ tự nhiên, các công trình nghiên cứu về đánh giá độ tương tự giữa các văn bản tiếng Anh đã và đang diễn ra sôi nổi. Nhiều công trình nghiên cứu và nhiều ứng dụng hữu ích đã thu được kết quả trong việc phát hiện sự vi phạm bản quyền tác giả trong các bài viết như Plagiarism-Detector Personal, Turnitin…

Đối với xử lý ngôn ngữ tiếng Việt, hiện nay cũng bắt đầu xuất hiện các nghiên cứu về so sánh trên văn bản tiếng Việt song vẫn chiếm tỉ lệ khá khiêm tốn. Trong tiếng Anh, kho ngữ liệu hay mạng từ tiếng Anh đã và đang phát triển rất tốt nên hiệu quả của các hệ thống so sánh đã cài đặt là rất cao. Do đặc điểm của từ tiếng Việt có nhiều điểm khác với tiếng Anh, việc xử lý văn bản và xây dựng được kho ngữ liệu chuẩn và đầy đủ là cả một vấn đề lớn. Các phương pháp đánh giá độ tương tự văn bản tiếng Việt dựa trên kho ngữ liệu vẫn đang được nghiên cứu và phát triển.

Một số phần mềm so sánh văn bản:

9

 Download Compare My Docs: đây là một chương trình so sánh văn bản cho phép người dùng so sánh cùng một lúc nhiều văn bản với nhau để tìm ra sự khác biệt giữa nội dung của chúng. Nhờ nó mà ta có thể biết được các văn bản tài liệu của mình có bị trùng với bất kỳ văn bản nào hay không? Phần mềm này cũng hỗ trợ cả các văn bản tiếng việt theo bảng mã Unicode.  Download UltraCompare: một trong những phần mềm so sánh file văn bản. Chương trình thực hiện so sách nội dung của các tài liệu và đưa ra tỷ lệ trùng, đánh dấu các nội dung trùng một cách chính xác. Ngoài ra chương trình còn cho phép người dùng tìm kiếm, đồng bộ các dữ liệu tìm kiếm và thư mục để thuận việc tìm kiếm, so sánh trở lên nhanh chóng hơn.

Thuyết minh ĐT NCKH

CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT

 Plagiarism-Detector Personal: phần mềm phát hiện các đoạn văn sao chép. Đây là ứng dụng độc đáo với các công cụ hữu ích nhằm hỗ trợ người sử dụng phát hiện ra những đoạn văn hay văn bản sao chép từ các nguồn khác nhau một cách chính xác.

 Turnitin: hệ thống hỗ trợ kiểm tra, đánh giá việc sao chép bài điện tử được triển khai tại FPT Polytechnic. Hệ thống này hiện đang làm việc với nhiều trường đại học hàng đầu thế giới và các trung tâm nghiên cứu lớn, một vài tổ chức chính phủ nhằm cung cấp một công cụ hiệu quả phát hiện sự vay mượn, sao chép.

2.2. Đặc điểm ngôn ngữ tiếng Việt

2.2.1. Cấu tạo từ tiếng Việt

Tiếng Việt là ngôn ngữ không biến hình từ và âm tiết tính, tức là mỗi âm tiết (tiếng) được phát âm tách rời và được thể hiện bằng một từ [4]. Hai đặc trưng này chi phối toàn bộ toàn bộ tổ chức của hệ thống ngôn ngữ tiếng Việt.

a) Tiếng

Tiếng là đơn vị cơ sở để cấu tạo lên từ. Tiếng là đơn vị nhỏ nhất có nội dung

được thể hiện. Xét về mặt ý nghĩa, các tiếng có thể chia thành các loại sau [1]:

- Tiếng tự thân nó đã có ý nghĩa, thường được quy chiếu vào một đối tượng,

khái niệm. Ví dụ: trời, đất, nước, cây, cỏ…

- Tiếng tự thân nó không có ý nghĩa, không được quy chiếu vào đối tượng, khái niệm nào cả mà chúng thường đi cùng với một tiếng khác có nghĩa và làm thay đổi sắc thái của tiếng đó, ví dụ như: (xanh) lè, (đường) xá, (nắng) nôi…

- Tiếng tự thân nó không có ý nghĩa nhưng có thể ghép với nhau để tạo thành từ có nghĩa, thường xuyên gặp ở những từ mượn như phéc-mơ-tuya, a-pa-tít, mì-chính...

Trong tiếng Việt các tiếng thuộc nhóm đầu tiên chiếm đa số, các tiếng thuộc hai nhóm sau thường chỉ chiếm số ít, đặc biệt là nhóm thứ 3, chúng thường được gọi là tiếng vô nghĩa.

b) Từ, cụm từ

Từ được cấu tạo từ một hoặc nhiều tiếng. Từ cấu tạo từ một tiếng gọi là từ đơn, ví dụ: tôi, bạn, nhà, hoa… Từ cấu tạo bởi nhiều tiếng là từ ghép, giữa các tiếng có mối quan hệ về nghĩa.

Từ ghép được phân thành từ ghép đẳng lập và từ ghép chính phụ. Đối với từ ghép đẳng lập các thành phần cấu tạo từ có mối quan hệ bình đẳng với nhau về nghĩa, 10

Thuyết minh ĐT NCKH

CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT

ví dụ: ăn nói, bơi lội… Đối với từ ghép chính phụ, các thành phần cấu tạo từ có mối quan hệ phụ thuộc với nhau về nghĩa, thành phần phụ có vai trò làm chuyên biệt hóa, tạo sắc thái cho thành phần chính, ví dụ: hoa hồng, đường sắt…

Cụm từ là những kiến trúc gồm hai từ trở lên kết hợp với nhau theo những quan

hệ ngữ pháp nhất định. Ví dụ:

- Từ “học” là từ gồm một tiếng. - Từ “đại học” là từ gồm hai tiếng. - Cụm từ “khoa học máy tính” gồm 2 từ hay 4 tiếng.

Theo như thống kê trên trang http://vdict.com thì độ dài của một từ tiếng Việt

được thể hiện trong bảng [6]:

Độ dài của từ 1 2 3 4 ≥5 Tổng cộng Tỉ lệ % 12,2 67.1 7.9 9.7 3.1 100

Tần số 8399 48995 5727 7040 2301 72994 Bảng 1: Tần suất xuất hiện độ dài từ tiếng Việt trên vdict.com

2.2.2. Biến hình từ tiếng Việt

Tiếng Việt không có hiện tượng biến hình từ bằng những phụ tố mang ý nghĩa ngữ pháp bên trong từ như tiếng Anh [4]. Tuy nhiên, tiếng Việt cũng có một số hình thức biến hình như trường hợp thêm từ “sự” trước một động từ để biến nó thành danh từ hay thêm tiếng “hóa” sau một danh từ để biến nó thành động từ tương đương, ví dụ như “lựa chọn” và “sự lựa chọn”, “tin học” và “tin học hóa”.

2.2.3. Từ đồng nghĩa

Từ đồng nghĩa là những từ tương đồng với nhau về nghĩa nhưng khác nhau về âm thanh và phân biệt với nhau về một vài sắc thái ngữ nghĩa hoặc phong cách nào đó, hoặc đồng thời cả hai [4]. Những từ đồng nghĩa với nhau lập thành một nhóm gọi là nhóm đồng nghĩa. Ví dụ: dễ, dễ dàng, dễ dãi là những nhóm từ đồng nghĩa.

Từ đồng nghĩa thực chất không phải là những từ trùng nhau hoàn toàn về nghĩa mà có những khác biệt nhất định. Chính sự khác biệt đó là lí do tồn tại và làm nên sự khác nhau giữa các từ trong một nhóm từ đồng nghĩa.

11

Thông thường các từ chỉ đồng nghĩa ở một nghĩa, một ngữ cảnh nào đó. Vì thế, một từ có nhiều nghĩa (đa nghĩa) có thể tham gia vào nhiều nhóm đồng nghĩa khác

Thuyết minh ĐT NCKH

CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT

nhau. Ví dụ, từ “coi” có thể tham gia vào các nhóm như coi – xem (coi hát, xem hát), coi – giữ (coi nhà, giữ nhà).

2.2.4. Đặc điểm chính tả

Đặc điểm chính tả tiếng Việt có ý nghĩa rất quan trọng trong các hệ thống xử lý

dữ liệu văn bản. Một số đặc điểm chính tả tiếng Việt cần quan tâm như [4]:

- Các tiếng đồng âm: kĩ/kỹ, lí, lý… thường bị sử dụng lẫn nhau như: lý luận,

lí luận, kĩ thuật, kỹ thuật…

- Các từ địa phương: một số từ địa phương sử dụng thay cho các từ phổ

thông, chẳng hạn: cây kiểng/cây cảnh, đờn/đàn, đậu phộng/lạc…

- Vị trí dấu thanh: theo quy định đánh dấu tiếng Việt, dấu được đặt trên nguyên âm có ưu tiên cao nhất. Tuy nhiên, khi soạn thảo văn bản nhiều bộ gõ không tuân thủ nguyên tắc này nên có hiện tượng dấu được đặt ở các vị trí khác nhau, chẳng hạn: toán, tóan, thuý, thúy…

- Cách viết hoa: theo quy định, chữ cái đầu câu và tên riêng phải viết hoa, tuy

nhiên vẫn tồn tại một số cách viết tuỳ tiện.

- Phiên âm tiếng nước ngoài: tồn tại cách viết giữ nguyên gốc tiếng nước

ngoài và phiên âm ra tiếng Việt, ví dụ: Singapore/Xin−ga−po.

- Từ gạch nối: do cách viết dấu gạch nối tuỳ tiện, không phân biệt được giữa

nối tên riêng hay chú thích.

- Kí tự ngắt câu: sử dụng nhiều loại kí tự đặc biệt như “.”, “;”, “!”, “?”, “…”

ngăn cách giữa các câu hoặc các vế câu trong câu ghép.

2.2.5. Bảng mã tiếng Việt trên máy tính

Hiện nay có khá nhiều cách mã hoá các kí tự tiếng Việt khác nhau, dẫn tới có nhiều bảng mã khác nhau được sử dụng khi trình bày văn bản. Theo thống kê, có tới trên 40 bảng mã tiếng Việt được sử dụng [4], có thể kể đến một số bảng mã dưới đây:

- Mã dựng sẵn:

o Mã dựng sẵn một bảng fonts: TCVN 5712-VN1, VISCII, BachKhoa 1, VietStar…: các bảng mã này mở rộng sang cả phần mã chuẩn, nên gây ảnh hưởng nghiêm trọng trong truyền thông.

o Mã dựng sẵn hai bảng fonts: TCVN 5712-VN3 (ABC), VietSea, VNU…: sử dụng 2 bảng mã cho một kiểu chữ nên gây dư thừa và không hiện thực việc phân biệt chữ hoa chữ thường trong các chương trình xử lý số liệu.

- Mã tổ hợp: Các bảng mã VietWare-X, Vni for Windows, TCVN 5712-VN2, BachKhoa II, VS2, 3C25… và các trang mã 1258 (Microsoft), 1129 (IBM), ISO 10646 sử dụng phương pháp mã tổ hợp.

12

Do chưa có sự thống nhất giữa các bảng mã biểu diễn tiếng Việt trên máy tính nên việc thu thập, khai thác xử lý tiếng Việt gặp nhiều khó khăn, đòi hỏi các hệ thống

Thuyết minh ĐT NCKH

CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT

xử lý văn bản tiếng Việt cần phải có bước tiền xử lý để nhận dạng và quy chuẩn các kí tự về một bảng mã chung.

2.3. Hướng tiếp cận cho bài toán so sánh văn bản tiếng Việt

2.3.1. Tiền xử lý văn bản tiếng Việt

Văn bản trước khi đưa vào mô hình xử lý cần được tiền xử lý. Quá trình này sẽ giúp nâng cao hiệu quả của mô hình và giảm độ phức tạp của thuật toán được cài đặt vì nó có nhiệm vụ làm giảm số từ có trong biểu diễn văn bản. Thông thường các bước tiền xử lý văn bản gồm:

 Tách văn bản thành các câu và các từ riêng lẻ để sử dụng cho mục đích tính

toán sau này.

 Loại bỏ từ dừng (stopwords), loại bỏ các ký tự không phải chữ cái hoặc chữ số.  Lưu các câu và các từ vào một cấu trúc dữ liệu phù hợp.

2.3.1.1.

Tách từ tiếng Việt

Tách từ có thể nói là giai đoạn quan trọng nhất, ảnh hưởng đến kết quả của mô hình xử lý. Bước này có nhiệm vụ xác định các từ có trong văn bản, kết quả của nó là một tập các từ riêng biệt. Các trường hợp đặc biệt như số, dấu ngoặc, dấu chấm câu thường bị loại ra trong khi phân tích vì một mình nó không mang lại ý nghĩa nào cho tài liệu (ngoại trừ một vài trường hợp đặc biệt, ví dụ trong thu thập thông tin về lĩnh vực lịch sử). Tuy nhiên trong một vài trường hợp, chẳng hạn đối với những từ ghép nối (state-of-the-art) không được phép bỏ dấu “-”, vì sẽ làm thay đổi nghĩa của từ.

Trong tiếng Việt, từ là sự hoàn chỉnh về mặt nội dung, là đơn vị nhỏ nhất để đặt câu. Người ta dùng từ để kết hợp thành câu chứ không dùng tiếng. Đối với các hệ thống xử lý ngôn ngữ tiếng Anh, để xác định các từ đặc trưng cho văn bản người ta có thể dựa vào khoảng trắng làm ranh giới. Tuy nhiên, trong tiếng Việt vì từ có thể là từ đơn hay từ ghép nên khoảng trắng không còn là dấu hiệu phân cách từ nữa. Vấn đề mà các mô hình tách từ tiếng Việt đều gặp phải đó là [1]:

 Xác định các từ chưa biết trước (đối với từ điển máy tính) như các câu thành

ngữ, từ láy, hoặc tên người, địa điểm…

 Sự nhập nhằng:

- Nhập nhằng chồng chéo: chuỗi “abcd” được gọi là nhập nhằng chồng chéo nếu như từ “abc”, “bcd” đều xuất hiện trong từ điển, ví dụ: trong câu “ông già đi nhanh quá” thì chuỗi “ông già đi” nhập nhằng chồng chéo vì các từ “ông già” và “già đi” đều có trong từ điển.

13

- Nhập nhằng kết hợp: chuỗi “abcd” gọi là nhập nhằng kết hợp nếu các từ thành phần “ab”, “cd”, “abcd” đều xuất hiện trong từ điển. Ví dụ trong câu “Tủ lạnh này còn rất mới” thì chuỗi “Tủ lạnh” bị nhập nhằng kết hợp do các từ “tủ”, “lạnh”, “tủ lạnh” đều có trong từ điển.

Thuyết minh ĐT NCKH

CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT

Hiện đã có nhiều công trình nghiên cứu xây dựng mô hình tách từ tiếng Việt, đa số là các mô hình đã được áp dụng thành công cho các ngôn ngữ khác (Anh, Trung, Nhật…) và được cải tiến để phù hợp với đặc điểm của tiếng Việt. Có thể kể đến các công trình điển hình như:

- Mô hình tách từ bằng WFST (Weighted Finit State Transduce) và mạng Neural đã được sử dụng trong công trình của tác giả Đình Điền (2001). Tác giả đã xây dựng hệ thống tách từ gồm tầng WFST để tách từ và xử lý các vấn đề liên quan đến một số đặc thù của tiếng Việt như từ láy, tên riêng… và tầng mạng Neural dùng để khử nhập nhằng về ngữ nghĩa sau khi đã tách từ nếu có. Mô hình này đạt được độ chính xác trên 97% theo như công bố của tác giả [2].

- JvnTextPro: công cụ tách từ do nhóm tác giả Nguyễn Cẩm Tú, Khoa Công nghệ - Trường Đại học Quốc gia Hà Nội xây dựng có thể nhận biết được các danh từ riêng, các từ đơn và từ ghép với có độ chính xác trung bình khá cao, khoảng 94,5%.

- Bộ công cụ tách từ vnTokenizer thuộc nhánh đề tài “Xử lý văn bản tiếng Việt” nằm trong Đề tài thuộc Chương trình Khoa học Công nghệ cấp Nhà nước “Nghiên cứu phát triển một số sản phẩm thiết yếu về xử lý tiếng nói và văn bản tiếng Việt” (2006) cũng cho độ chính xác cao, trên 97%.

2.3.1.2.

Loại bỏ từ dừng (stopwords)

Từ dừng là các từ thường xuất hiện nhiều trong các văn bản của tập dữ liệu, thường thì chúng không giúp ích gì trong việc phân biệt nội dung của các tài liệu. Ví dụ “như vậy”, “sau đó”, “một số”, “chỉ”…

2.3.1.3. Loại bỏ từ có tần số thấp

Có nhiều từ trong tập văn bản xuất hiện rất ít lần và có ảnh hưởng rất ít trong

văn bản. Vì vậy các từ này cũng nên loại bỏ.

2.3.1.4.

Xác định từ đồng nghĩa

Từ đồng nghĩa là những từ tương đương về nghĩa trong một số ngữ cảnh nào đó, bên cạnh sự tương đồng chúng có những khác biết nhất định mặc dù việc phát hiện những khác biệt đó không phải lúc nào cũng dễ dàng. Với bài toán so sánh trên văn bản thì việc nhận ra các từ đồng nghĩa có ý nghĩa quan trọng bởi trong các câu, các đoạn văn luôn có các từ đồng nghĩa hoặc gần nghĩa nhau được sử dụng thay thế. Việc phát hiện ra các từ đồng nghĩa sẽ làm nâng cao tính chính xác khi so sánh về độ tương đồng ngữ nghĩa giữa các đơn vị văn bản.

2.3.2. Phương pháp tính độ tương đồng giữa các văn bản

14

Độ tương đồng ngữ nghĩa giữa các câu đóng một vai trò quan trọng trong các nghiên cứu về xử lý văn bản. Nó được sử dụng như là một tiêu chuẩn của trích chọn

Thuyết minh ĐT NCKH

CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT

thông tin nhằm tìm ra những tri thức ẩn trong các cơ sở dữ liệu văn bản hay trên các kho dữ liệu trực tuyến. Hiện nay tồn tại một số phương pháp tính độ tương đồng giữa các câu, điển hình là các phương pháp dựa trên tính toán thống kê và các phương pháp dựa trên quan hệ ngữ nghĩa giữa tập các từ trong các câu đó.

- Với phương pháp dựa trên quan hệ ngữ nghĩa giữa các từ: một số hướng tiếp cận phân tích cấu trúc ngữ pháp, sử dụng mạng ngữ nghĩa đối với từ như Wordnet corpus hoặc Brown corpus... Các phương pháp này xử lý chậm hơn, tốn nhiều chi phí hơn nhưng xét về mặt ngữ nghĩa thì độ tương đồng chính xác cao hơn phương pháp thống kê.

- Với phương pháp thống kê: sử dụng các độ đo dựa vào tần suất xuất hiện của từ trong câu như phương pháp sử dụng độ đo Cosine, độ đo khoảng cách Euclide, Manhattan... Các phương pháp này tốc độ xử lý nhanh, tốn ít chi phí nhưng không đảm bảo độ chính xác cao về mặt ngữ nghĩa.

Do đặc điểm của tiếng Việt, vấn đề tương đồng ngữ nghĩa trên văn bản tiếng Việt phức tạp hơn khi so với ngôn ngữ tiếng Anh. Phần lớn các giải pháp hiện có thường quan tâm tới các độ đo dựa vào thống kê mà chưa khai thác các độ đo dựa vào xử lý ngôn ngữ tự nhiên. Các phương pháp tính dựa trên kho ngữ liệu Wordnet được đánh giá là cho kết quả cao, tuy nhiên WordNet chỉ hỗ trợ cho tiếng Anh, việc xây dựng kho ngữ liệu này cho tiếng Việt là chưa có. Một số phương pháp được đề xuất thay thế Wordnet như phương pháp phân tích chủ đề ẩn hay sử dụng mạng ngữ nghĩa Wikipedia thay thế được xem như là phương án khả thi và hiệu quả. Các phương pháp này tập trung vào việc bổ sung các thành phần ngữ nghĩa hỗ trợ cho độ đo tương đồng Cosine.

Một số đề tài đáng chú ý về so sánh, đánh giá độ tương tự văn bản như “Tính toán độ tương tự ngữ nghĩa văn bản dựa vào độ tương tự giữa từ với từ” của tác giả Đỗ Thị Thanh Nga (Đại học Công nghệ Đại học Quốc gia Hà Nội, 2010), đề tài “Nghiên cứu độ đo tương đồng văn bản trong tiếng Việt và ứng dụng” của tác giả Dương Thăng Long (Viện Đại học Mở Hà Nội, 2014).

15

Đề tài của tác giả Đỗ Thị Thanh Nga đưa ra mô hình tính độ tương tự ngữ nghĩa giữa hai văn bản dựa trên độ tương tự giữa từ với từ kết hợp với tần suất đặc trưng của từ [6]. Kết quả của đề tài tương đối khả quan với những cặp văn bản hoặc là giống nhau nhiều hoặc là khác nhau nhiều. Tuy nhiên, do phương pháp này chưa xét đến mối quan hệ về cấu trúc của từ/cụm từ, vị trí của câu… nên vẫn còn nhiều trường hợp chương trình thử nghiêm cho kết quả không chính xác. Cũng chình vì thế các văn bản có sự tương đồng cao về ngữ nghĩa không hẳn đã là giống nhau. Nói cách khác, độ tương đồng về ngữ nghĩa không phản ánh được chính xác sự sao chép trong các văn bản đem so sánh.

Thuyết minh ĐT NCKH

CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT

Đề tài của tác giả Dương Thăng Long giới thiệu phương pháp đánh giá độ tương tự văn bản tiếng Việt sử dụng 3 yếu tố: độ tương tự dựa trên vector đặc trưng ngữ nghĩa, độ tương tự dựa trên cấu trúc thứ tự các từ và độ tương tự dựa trên ma trận so sánh cặp từ vựng theo nhóm từ loại [5]. Sự kết hợp của 3 yếu tố trên làm tăng hiệu quả đánh giá, tuy nhiên, phương pháp đề xuất còn phụ thuộc vào kết quả của các xử lý trung gian, đặc biệt là dịch từ tiếng Việt sang tiếng Anh và đánh giá độ tương tự của cặp từ vựng tiếng Anh, dẫn đến độ tin cậy của kết quả đánh giá độ tương tự văn bản giảm nhiều.

2.3.3. Hướng tiếp cận cho bài toán so sánh văn bản tiếng Việt

Do việc xây dựng bộ tách từ khá phức tạp và nằm ngoài phạm vi của đề tài nên trong thực nghiệm, chúng tôi sử dụng bộ tách từ đã được viết sẵn và cung cấp miễn phí WordSegForTV để thực hiện bước tiền xử lý văn bản. Việc xác định các từ dừng trong văn bản được thực hiện thông qua một từ điển từ dừng. Ngoài ra, đối với tiếng Việt, do có một lượng lớn các từ đồng nghĩa thường được sử dụng nên khi tính độ tương tự giữa các câu trong văn bản cần sử dụng thêm một từ điển đồng nghĩa.

Sau khi phân tách từ thành công, văn bản sẽ gồm tập các từ khóa mà ngữ nghĩa của chúng tạo nên nội dung của văn bản. Trong đa số các hệ xử lý văn bản, các văn bản đều được coi là tập các từ khóa và biểu diễn chúng dưới dạng vector, chẳng hạn như Di = (di1,di2, …, din) với dik biểu diễn trọng số/tần xuất của từ tk trong Di. Việc so sánh độ tương tự giữa hai văn bản Di và Dj, kí hiêu là Sim(Di,Dj), được tính toán theo các công thức tính toán độ tương tự, ví dụ độ tương tự Cosine. Nếu độ tương tự này đạt đến một ngưỡng đủ lớn thì người ta nói rằng chúng có liên quan về mặt ngữ nghĩa và ta có thể thiết lập một liên kết giữa hai văn bản này.

Tuy nhiên, đối với các văn bản tiếng Việt, phương thức ngữ pháp chủ yếu là dựa trên trật tự của từ trong câu nên nếu áp dụng mô hình biểu diễn văn bản dựa trên tần số xuất hiện của từ có thể không cho kết quả chính xác như mong đợi. Nguyên nhân là do vector biểu diễn văn bản không đảm bảo giữ được mối liên quan về mặt ngữ nghĩa giữa các từ, vị trí các từ, cụm từ và vị trí của câu trong văn bản, hai vector có trật tự từ khác nhau vẫn có thể cho độ tương tự là hoàn toàn giống nhau.

Nhằm kế thừa ưu điểm của các phương pháp đã biết, hướng tiếp cận bài toán so sánh văn bản tiếng Việt là xác định độ tương tự của văn bản dựa trên độ tương tự của câu và trật tự câu, độ tương tự câu dựa trên độ tương tự của từ và trật tự của từ trong câu. Những cải tiến của phương pháp đề xuất so với so sánh văn bản tiếng Anh và các phương pháp đã biết là:

- Kết hợp sử dụng bộ tách từ, từ điển từ dừng và từ điển từ đồng nghĩa làm tăng

16

tính ngữ nghĩa của tập từ khóa và vector đặc trưng biểu diễn văn bản.

Thuyết minh ĐT NCKH

CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT

- Kết hợp độ tương tự ngữ nghĩa từ (có xử lý từ đồng nghĩa) và độ tương tự thứ tự từ vào tính độ tương tự của văn bản nhằm nâng cao chất lượng kết quả so sánh.

17

Trong các chương tiếp theo, chúng tôi sẽ trình bày chi tiết về các mô hình biểu diễn văn bản, phương pháp tính độ tương đồng câu và mô hình hệ thống so sánh văn bản tiếng Việt.

Thuyết minh ĐT NCKH

CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT

CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT

Biểu diễn văn bản là một bước quan trọng trong khai thác dữ liệu văn bản, truy vấn thông tin và xử lý ngôn ngữ tự nhiên. Các mô hình biểu diễn đóng vai trò trung gian giữa ngôn ngữ tự nhiên dạng văn bản và các chương trình xử lý. Văn bản ở dạng thô (chuỗi) sau khi được chuyển sang mô hình sẽ trở thành những cấu trúc dữ liệu trực quan, đơn giản hơn, thuận lợi cho việc hiểu và tính toán trên văn bản.

Vì vậy, các mô hình biểu diễn không ngừng phát triển. Tùy thuộc vào từng bài toán, từng thuật toán khác nhau mà chúng ta có mô hình biểu diễn phù hợp. Các mô hình biểu diễn văn bản truyền thống như mô hình túi từ, mô hình không gian vector là các mô hình thường được sử dụng nhất. Tuy nhiên, các mô hình này có nhược điểm là không nắm bắt được các thông tin cấu trúc quan trong của văn bản như trật tự các từ, vị trí của từ trong văn bản. Mô hình đồ thị biểu diễn văn bản là phương pháp đang được quan tâm và sử dụng trong các lĩnh vực khai phá dữ liệu văn bản hiện tại.

3.1. Mô hình biểu diễn văn bản truyền thống

3.1.1. Mô hình logic

Trong mô hình này, văn bản được biểu diễn dựa theo chỉ số của các từ có nghĩa. Từ có nghĩa là từ mang thông tin chính của văn bản, khi nhìn vào từ đó người ta biết chủ đề của văn bản cần biểu diễn là gì. Mỗi văn bản được đánh chỉ số theo qui tắc liệt kê các từ có nghĩa trong văn bản và với mỗi từ khóa, lưu vị trí xuất hiện cùng với mã của văn bản chứa nó [2].

Ví dụ, có hai văn bản VB1,VB2:

“Mô hình đồ thị biểu diễn văn bản” (VB1)

“Biểu diễn văn bản sử dụng mô hình đồ thị” (VB2)

Khi đó ta có cách biểu diễn như sau:

Từ mục Mã VB _ Vị trí XH

Mô VB1(1), VB2(7)

Hình VB1(2), VB2(8)

Đồ VB1(3), VB2(9)

Thị VB1(4), VB2(10)

Biểu VB1(5), VB2(1)

Diễn VB1(6), VB2(2)

Văn VB1(7), VB2(3)

Bản VB1(8), VB2(4)

Bảng 2: Biểu diễn văn bản trong mô hình Logic

18

Thuyết minh ĐT NCKH

CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT

Cách biểu diễn này cũng được các máy tìm kiếm ưa dùng. Khi biểu diễn văn bản theo mô hình này, người ta đưa các tìm kiếm sau: câu hỏi tìm kiếm được đưa ra dưới dạng Logic gồm một tập các phép toán (AND, OR,…) thực hiện trên các từ hoặc cụm từ, việc tìm kiếm dựa vào bảng Index đã tạo ra và kết quả trả lại là các văn bản thoả mãn toàn bộ các điều kiện trên

Ưu điểm: việc tìm kiếm có thể thực hiện nhanh và đơn giản do trước đó ta đã sắp xếp bảng Index theo các từ khóa. Hệ thống sẽ duyệt trên bảng Index để trỏ để trỏ đến Index tương ứng với từ khóa nếu từ khóa tồn tại trong hệ thống, và cho ta biết các tài liệu chứa từ khóa cần tìm.

Nhược điểm: đòi hỏi người tìm kiếm phải có kinh nghiệm tìm kiếm. Do câu hỏi tìm kiếm được đưa vào dưới dạng Logic nên kết quả trả lại cũng có giá trị Logic, một số tài liệu sẽ chỉ được trả lại khi thỏa mãn mọi điều kiện. Như vậy muốn tìm được tài liệu theo nội dung thì phải biết đích xác về tài liệu. Hơn nữa, việc Index các tài liệu phức tạp và tốn nhiều thời gian, không gian để lưu trữ; khi thêm, xóa từ khóa vào các bảng Index chỉ số Index của văn bản cũng thay đổi theo.

3.1.2. Mô hình vector

Mô hình vector là một trong những mô hình đơn giản và thường được sử dụng trong phần lớn các bài toán xử lý dữ liệu văn bản. Theo mô hình này, mỗi văn bản được biểu diễn thành một vector, mỗi thành phần của vector là một từ khóa trong tập văn bản gốc và được gán một giá trị trọng số xác định tần suất xuất hiện của từ trong văn bản.

Hình 1: Mô hình vector biểu diễn văn bản

Phát biểu của mô hình: Mỗi văn bản D được biểu diễn dưới dạng một vector 𝑉⃗ (vector đặc trưng cho văn bản D). Trong đó, 𝑉⃗ = (𝑣1, 𝑣2, … , 𝑣𝑛) và n là số lượng đặc trưng hay số chiều của vector văn bản(thường là số từ khóa), 𝑣𝑖 là trọng số của đặc trưng thứ i (với 1 ≤ 𝑖 ≤ 𝑛).

Ví dụ: xét 2 văn bản với trọng số đặc trưng là số lần xuất hiện của từ khóa thứ i

trong văn bản, vector biểu diễn tương ứng như sau:

19

VB1: Life is not only life

Thuyết minh ĐT NCKH

CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT

VB2: To life is to fight

Vector VB1 Vector VB2 Từ

Life 2 1

Fight 0 1

Only 1 0

Bảng 3: Vector biểu diễn văn bản

Trọng số của đặc trưng có thể tính dựa trên tần số xuất hiện của từ khóa trong văn bản. Ma trận biểu diễn trọng số (ma trận tần suất) W ={wij} được xác định dựa trên tần số xuất hiện của từ khóa ti trong văn bản dj. Một số phương pháp xác định wij:  Phương pháp Boolean weighting: giá trị là 1 nếu số lần xuất hiện của từ

khóa lớn hơn một ngưỡng nào đó, ngược lại 0).

 Phương pháp dựa trên tần số từ khóa (Term Frequency Weighting).  Phương pháp dựa trên nghịch đảo tần số văn bản (Inverse Document

Frequency).  Tf*idf weighting.

a) Phương pháp Boolean weighting

Mô hình vector với trọng số từ khóa ti nhận giá trị đúng nếu và chỉ nếu ti xuất

hiện trong văn bản đó.

Giả sử có một cơ sở dữ liệu gồm m văn bản, D = {d1, d2,… dm}. Mỗi văn bản được biểu diễn dưới dạng một vector gồm n từ khóa T = {t1, t2,…tn}. Gọi W = {wij} là ma trận trọng số, trong đó wij là giá trị trọng số của từ khóa ti trong văn bản dj.

𝑤𝑖𝑗 = { 1 𝑛ế𝑢 𝑡𝑖 𝑐ó 𝑡𝑟𝑜𝑛𝑔 𝑑𝑗 0 𝑛ế𝑢 𝑛𝑔ượ𝑐 𝑙ạ𝑖

b) Phương pháp dựa trên tần số từ khóa (Term Frequency)

Các giá trị wij được tính dựa trên tần số xuất hiện của từ khóa trong văn bản. Giả sử fij là số lần xuất hiện của từ khóa ti trong văn bản dj, khi đó wij được tính bởi một trong ba công thức:

𝑤𝑖𝑗 = 𝑓𝑖𝑗

𝑤𝑖𝑗 = 1 + 𝑙𝑜𝑔(𝑓𝑖𝑗)

𝑤𝑖𝑗 = √𝑓𝑖𝑗

20

Nếu số lần xuất hiện từ khóa ti trong văn bản dj càng lớn thì có nghĩa là văn bản dj càng phụ thuộc vào từ khóa ti, hay nói cách khác từ khóa ti mang nhiều thông tin

Thuyết minh ĐT NCKH

CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT

trong văn bản dj. Ví dụ, nếu trong văn bản xuất hiện nhiều từ khóa máy tính, điều đó có nghĩa là văn bản chủ yếu liên quan đến lĩnh vực tin học.

c) Phương pháp dựa trên nghịch đảo tần số văn bản

Trong phương pháp này, wij được tính theo công thức sau:

log ( ) 𝑛ế𝑢 𝑡𝑓𝑖𝑗 ≥ 1 𝑤(𝑖, 𝑗) = { 𝑁 𝑑𝑓𝑖

0 𝑛ế𝑢 𝑡𝑓𝑖𝑗 = 0

Trong đó N là số lượng văn bản và dfi là số lượng văn bản mà từ khóa ti xuất

hiện.

Trong công thức này, trọng số wij được tính dựa trên độ quan trọng của từ khóa ti trong văn bản dj. Nếu ti xuất hiện trong càng ít văn bản, thì khi nó xuất hiện trong dj, trọng số của nó đối với dj càng lớn (do tính nghịch đảo của hàm log), tức là hàm lượng thông tin trong nó càng lớn. Nói cách khác ti là điểm quan trọng để phân biệt dj với các văn bản khác.

d) Phương pháp TF × IDF

Đây là phương pháp kết hợp của hai phương pháp TF và IDF. Trọng số wij được tính bằng tần số xuất hiện của từ khóa ti trong văn bản dj và độ hiếm của từ khóa ti trong tập văn bản.

Công thức tính wij:

(1 + log(𝑓𝑖𝑗)) log ( ) 𝑛ế𝑢 𝑓𝑖𝑗 ≥ 1 𝑤𝑒𝑖𝑔ℎ(𝑖, 𝑗) = { 𝑁 𝑑𝑓𝑖

0 𝑛ế𝑢 𝑓𝑖𝑗 = 0

Trong đó:

o weigh(i,j): trọng số của từ thứ i trong văn bản thứ j. o fij (term frequency): số lần xuất hiện của từ thứ i trong văn bản thứ j, fij

càng cao thì từ đó càng miêu tả tốt nội dung văn bản. o dfi (document frequency): số văn bản có chứa từ thứ i.

Nhận xét:

Ưu điểm: mô hình vector là mô hình biểu diễn văn bản được sử dụng khá phổ biến trong các hệ xử lý văn bản. Mối quan hệ giữa các văn bản được tính toán dựa trên các vector biểu diễn nên dễ dàng thực hiện.

21

Nhược điểm: vì mỗi văn bản được biểu diễn thành một vector n chiều, với số chiều thường là số từ khác nhau trong tập văn bản, do đó không gian biểu diễn có số chiều tương đối lớn, việc lưu trữ và tính toán trên vector tốn kém và phức tạp.

Thuyết minh ĐT NCKH

CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT

Ngoài ra, hệ thống không linh hoạt khi lưu trữ các từ khóa. Chỉ cần một thay đổi nhỏ trong bảng từ vựng sẽ dẫn đến hoặc là vector hóa lại toàn bộ các tài liệu, hoặc là bỏ qua các từ có nghĩa bổ sung trong các tài liệu được mã hóa trước đó.

3.2. Mô hình đồ thị biểu diễn văn bản

Mô hình đồ thị biểu diễn văn bản được John F. Sowa đưa ra lần đầu tiên vào năm 1976 – mô hình đồ thị khái niệm (Conceptual Graphs CGs). Hiện nay, mô hình đồ thị không ngừng phát triển dựa trên ý tưởng của mô hình CGs và được ứng dụng rộng rãi vào các bài toán liên quan đến xử lý văn bản.

Trong mô hình đồ thị, mỗi đồ thị là một văn bản. Đỉnh của đồ thị có thể là câu, hoặc từ, hoặc kết hợp câu và từ. Cạnh nối giữa các đỉnh là vô hướng hoặc có hướng, thể hiện mối quan hệ trong đồ thị. Nhãn của đỉnh thường là tần số xuất hiện của đỉnh, còn nhãn của cạnh là tên mối liên kết khái niệm giữa hai dỉnh, hay tần số xuất hiện chung của hai đỉnh trong một phạm vi nào đó, hay tên vùng mà đỉnh xuất hiện.

Ví dụ, trong bài toán rút trích thông tin, đỉnh là từ hay từ kết hợp câu, cạnh thể hiện tần số đồng hiện. Trong bài toán phân lớp văn bản, đỉnh là từ, cạnh thể hiện trật tự xuất hiện của từ hay vị trí xuất hiện của từ trong văn bản. Trong bài toán tóm tắt văn bản, đỉnh là câu, cạnh thể hiện sự tương đồng giữa các câu.

Các dạng mô hình đồ thị:

 Mô hình đồ thị sử dụng đỉnh là từ trong văn bản: gồm mô hình đồ thị sử dụng mạng

ngữ nghĩa và mô hình đồ thị không sử dụng mạng ngữ nghĩa.

 Mô hình đồ thị sử dụng đỉnh là câu.  Mô hình đồ thị đỉnh là câu và từ.

Mô hình đồ thị khái niệm sử dụng mạng ngữ nghĩa để biểu diễn văn bản thành đồ thị. Mỗi từ trong văn bản là một khái niệm và được biểu diễn bẳng đỉnh hình vuông. Đỉnh hình oval thể hiện mối quan hệ giữa các khái niệm. Các đỉnh hình vuông được nối với nhau dựa trên mối quan hệ trong mạng ngữ nghĩa và qua trung gian là đỉnh hình oval.

Ví dụ ta có câu: “John is going to Boston by bus”, đồ thị khái niệm có dạng:

3.2.1. Mô hình đồ thị khái niệm

Hình 2: Ví dụ mô hình đồ thị khái niệm

22

Thuyết minh ĐT NCKH

CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT

Trong hình, các khái niệm là “Go”, “Person: John”, “City: Boston” và “Bus”,

Ưu điểm của CGs là mô hình hóa văn bản một cách trực quan, chính xác và logic. Hạn chế của mô hình là khác phức tạp, đòi hỏi phân tích ngữ nghĩa sâu, chuyên biệt và phụ thuộc vào lĩnh vực.

các mối quan hệ “Agnt”, “Dest” và “Inst”.

Trong đồ thị hình sao, đỉnh trung tâm là nét khái quát cấu trúc của văn bản. Sau khi đỉnh trung tâm được xác lập, các đỉnh còn lại sẽ được triển khai. Ngoài đỉnh trung tâm, các đỉnh còn lại biểu diễn từ trong văn bản. Cạnh nối giữa các đỉnh được gán nhãn, thể hiện mối quan hệ giữa các đỉnh.

Ví dụ:

3.2.2. Mô hình đồ thị hình sao

Hình 3: Ví dụ mô hình đồ thị hình sao

Mô hình được ứng dụng tốt vào các bài toán phân lớp, đặc biệt trong phân loại email do nắm được các thông tin cấu trúc của email (tiêu đề, nội dung), mối quan hệ giữa từ với các phần cấu trúc (đồng hiện của từ trong các phần tiêu đề, nội dung).

Trong mô hình này, đỉnh và cạnh đều được gán nhãn là tần số xuất hiện của đỉnh và cạnh tương ứng. Cạnh được nối giữa hai đỉnh nếu hai từ xuất hiện chung trong trong tập hợp (câu hoặc nhóm từ hoặc trang). Nhãn của đỉnh là tần số xuất hiện của từ trong văn bản, nhãn của cạnh là tần số xuất hiện chung của 2 từ trong tập hợp và tần số xuất hiện chung này lớn hơn ngưỡng cho phép.

Ví dụ:

23

3.2.3. Mô hình đồ thị vô hướng sử dụng tần số xuất hiện

Thuyết minh ĐT NCKH

CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT

Hình 4: Ví dụ mô hình đồ thị vô hướng sử dụng tần số xuất hiện

Ưu điểm của mô hình là khai thác được mối quan hệ giữa từ với từ trong cấu trúc văn

bản cũng như tần số xuất hiện của từ, hỗ trợ cho quá trình tìm kiếm thông tin nhanh chóng.

Mô hình này còn được gọi là mô hình đồ thị đơn giản. Mỗi đỉnh biểu diễn một từ riêng biệt và chỉ xuất hiện một lần trên đồ thị ngay cả khi từ đó xuất hiện nhiều lần trong văn bản. Nhãn đình là tên của từ. Sau bước tiền xử lý văn bản, nếu từ “a” đứng ngay trước từ “b” sẽ có cạnh nối từ đỉnh “a” đến đỉnh “b” (không kể các trường hợp phân cách bởi dấu câu).

Ví dụ: “Microsoft sẽ giới thiệu hệ điều hành Vista và trưng bày công nghệ bổ trợ được

xây dựng để cải tiến hệ điều hành”

3.2.4. Mô hình đồ thị có hướng, cạnh không gán nhãn

Hình 5: Ví dụ mô hình đồ thị đơn giản

Ưu điểm của mô hình là lưu trữ được các thông tin cấu trúc như thứ tự xuất hiện, vị trí của từ trong văn bản và làm tăng hiệu quả của các bài toán phân lớp cũng như gom cụm văn bản.

Mô hình này còn có tên gọi khác là mô hình khoảng cách n đơn giản. Trong mô hình này, người dùng cung cấp tham số n. Thay vì chỉ quan tâm từ “A” trực tiếp ngay trước từ “B” ta còn chú ý đến n từ đứng trước từ “B”. Cạnh được xây dựng giữa hai từ khi giữa chúng có

24

3.3.5. Mô hình đồ thị có hướng, cạnh không gán nhãn, cạnh là khoảng cách n giữa hai từ trong văn bản

Thuyết minh ĐT NCKH

CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT

số từ xuất hiện nhiều nhất là (n-1), ngoại trừ trường hợp các từ được phân cách bởi các dấu câu.

Ví dụ: ta có câu “Cánh đồng lúa xanh bát ngát”, với n = 2, mô hình biểu diễn câu như

sau:

Hình 6: Ví dụ mô hình đồ thị khoảng cách n đơn giản

Ưu điểm của mô hình là tận dụng được mối quan hệ giữa các từ, vùng lân cận của từ

trong câu và có thể áp dụng vào bài toán phân lớp văn bản.

25

Thuyết minh ĐT NCKHCHƯƠNG IV: PHƯƠNG PHÁP TÍNH ĐỘ TƯƠNG ĐỒNG VĂN BẢN

CHƯƠNG IV: PHƯƠNG PHÁP TÍNH ĐỘ TƯƠNG ĐỒNG VĂN BẢN

Các phép đo độ tương tự giữa văn bản và văn bản đã được quan tâm nghiên cứu từ rất lâu trong các ứng dụng của xử lý ngôn ngữ tự nhiên và các lĩnh vực liên quan. Một trong các ứng dụng sớm nhất của độ tương tự văn bản là tìm kiếm thông tin, ở đó các tài liệu có liên quan tới câu truy vấn được xếp hạng theo thứ tự của độ tương tự. Ngoài ra, độ tương tự văn bản còn được dùng cho phân lớp văn bản, trích chọn hay tóm tắt văn bản, phương pháp cho đánh giá dịch máy tự động hay đánh giá tính chặt chẽ của văn bản.

Nội dung chương trình bày một số phép tính độ tương đồng văn bản điển hình

và phương pháp để xác định độ tương đồng trên văn bản tiếng Việt.

4.1. Khái niệm độ tương đồng

Độ tương đồng là một đại lượng dùng để so sánh hai hay nhiều đối tượng với nhau, phản ánh cường độ của mối quan hệ giữa các đối tượng với nhau. Ví dụ: xét 2 câu “Tôi là nam” và “Tôi là nữ”, ta có thể nhận thấy hai câu trên có sự tương đồng khá cao.

Phát biểu bài toán tính độ tương đồng như sau:

Xét 2 văn bản di và dj. Mục tiêu là tìm ra một giá trị S(di,dj), S (0,1), thể hiện độ tương đồng giữa 2 văn bản di và dj. Giá trị càng cao thì sự giống nhau về nghĩa của hai văn bản càng nhiều.

Ví dụ trong mô hình không gian vector, ta sử dụng độ đo Cosine để tính độ

tương đồng giữa hai văn bản, mỗi văn bản được biểu diễn bởi một vector.

Độ tương tự ngữ nghĩa là khái niệm thể hiện tỷ lệ dựa trên sự giống nhau về nội dung ý nghĩa của tập các tài liệu hoặc các thuật ngữ trong một danh sách các thuật ngữ [6]. Độ tương đồng ngữ nghĩa phản ánh mối quan hệ ngữ nghĩa giữa các câu, các tài liệu văn bản.

4.2. Độ tương đồng văn bản dựa trên tập từ chung

4.2.1. Khoảng cách Jaro

Khoảng cách Jaro định nghĩa độ đo tương tự giữa hai chuỗi. Cho hai câu s1 và s2, khoảng cách Jaro d giữa s1 và s2 được tính như sau (Winkler, W. E., “String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage”, 1990):

26

) 𝑑 = + + 1 3 𝑚 − 𝑡 𝑚 𝑚 ( |𝑠1| 𝑚 |𝑠2|

Thuyết minh ĐT NCKHCHƯƠNG IV: PHƯƠNG PHÁP TÍNH ĐỘ TƯƠNG ĐỒNG VĂN BẢN

Trong đó m là số từ giống nhau, t là ½ số bước chuyển.

Phép chuyển vị trí sẽ được thực hiện khi hai từ giống nhau trong hai câu s1 và s2

có khoảng cách không lớn hơn giá trị:

⌊ ⌋ − 1 max (|𝑠1|, |𝑠2|) 2

Mỗi từ trong câu s1 được so sánh với tất cả các từ trong s2. Số bước chuyển được định nghĩa là số lượng từ giống nhau giữa hai câu (nhưng thứ tự trong chuỗi khác nhau) chia cho 2.

4.2.2. Mô hình tương phản (Contrast model)

Mô hình tương phản do Tversky đề xuất (“Features of similarity”,

Psychological Review, 1977) để tính độ tương tự giữa hai câu A và B như sau:

𝑆𝑖𝑚(𝐴, 𝐵) =∝∗ 𝑔(𝐴 ∩ 𝐵) − 𝛽 ∗ 𝑔(𝐴 − 𝐵) − 𝛾 ∗ 𝑔(𝐵 − 𝐴)

Trong đó g(A∩B) biểu diễn cho các từ chung giữa A và B, g(A-B) biểu diễn cho các từ riêng của A và g(B-A) biểu diễn cho các từ riêng của B. Hệ số ∝, 𝛽, 𝛾 được xác định trong quá trình thử nghiệm thuật toán.

4.2.3. Hệ số Jaccard

Hệ số Jaccard là một độ đo tương tự của các tập hợp dựa trên phương pháp thống kê. Theo đó, độ tương tự giữa hai câu A và B như sau (Paul Jaccard, “Etude comparative de la distribution orale dans une portion des Alpes et des Jura”. In Bulletin del la Socit Vaudoise des Sciences Naturelles, volume 37, pages 547-579):

𝑆𝑖𝑚(𝐴, 𝐵) = |𝐴 ∩ 𝐵| |𝐴 ∪ 𝐵|

4.3. Độ tương đồng văn bản dựa trên vector biểu diễn

4.3.1. Độ tương đồng Cosine

Trong phương pháp này, các văn bản được biểu diễn theo mô hình không gian vector, mỗi thành phần của vector chỉ đến một từ tương ứng trong danh sách mục từ đã thu được từ quá trình tiền xử lý văn bản đầu.

𝑡𝑓𝑖𝑗

Không gian vector hay số chiều của vector có kích thước bằng số mục từ trong danh sách mục từ. Giá trị mỗi phần tử của vector là độ quan trọng của mục từ trong câu. Độ quan trọng của từ được tính theo một trong các phương pháp đã trình bày ở trên, phần mô hình vector biểu diễn văn bản, ví dụ:

2 √∑ 𝑡𝑓𝑖𝑗 𝑗

với tfij là tần số xuất hiện của từ i trong câu j. 𝑤𝑖𝑗 =

27

Giả sử vector biểu diễn cho hai văn bản lần lượt có dạng:

Thuyết minh ĐT NCKHCHƯƠNG IV: PHƯƠNG PHÁP TÍNH ĐỘ TƯƠNG ĐỒNG VĂN BẢN

t là trọng số của từ thứ t trong không gian vector i.

1, …, wi 1, …, wj

t> với wi t> với wj

t là trọng số của từ thứ t trong không gian vector j.

Di =

Độ đo tương đồng được tính là Cosine của góc giữa hai vector biểu diễn cho hai

văn bản Di và Dj. Độ tương tự của chúng được tính theo công thức [2]:

𝑡 𝑘=1 𝑘)2

𝑘)2

𝑘𝑤𝑗 𝑘 𝑡 ∗ ∑ (𝑤𝑗 𝑘=1

𝑡 √∑ (𝑤𝑖 𝑘=1

∑ 𝑤𝑖 𝑆𝑖𝑚(𝐷𝑖𝑗) =

Nhận xét: vector biểu diễn cho các câu chưa quan tâm đến mối quan hệ ngữ nghĩa giữa các từ mục, do đó các từ đồng nghĩa sẽ không được phát hiện, kết quả tín độ tương tự chưa cao.

4.3.2. Độ tương đồng dựa vào khoảng cách Euclide

Khoảng cách Euclide cũng là một phương pháp khá phổ biến để xác định mức

độ tương đồng giữa các vector đặc trưng của hai văn bản[2].

𝑛

Cho hai vector 𝑣 a và 𝑣 b, khoảng cách Euclide được định nghĩa như sau:

𝑖=1

𝐸_𝑑𝑖𝑠𝑡(𝑣⃗ 𝑎,𝑣⃗ 𝑏) = √∑(𝑤𝑎𝑖 − 𝑤𝑏𝑖)2

𝑛

Mức độ tương đồng giữa hai vector được xác định bằng công thức:

𝑖=1

= 1 − √∑(𝑤𝑎𝑖 − 𝑤𝑏𝑖)2 𝐸_𝑠𝑖𝑚(𝑣⃗ 𝑎,𝑣⃗ 𝑏) = 1 − 𝐸_𝑑𝑖𝑠𝑡(𝑣⃗ 𝑎,𝑣⃗ 𝑏) 𝑛 1 𝑛

4.3.3. Độ tương đồng dựa vào khoảng cách Manhattan

Khoảng cách Manhattan là phương pháp tính độ tương đồng giữa các vector

đặc trưng biểu diễn cho hai văn bản [2].

𝑛

Cho hai vector 𝑣 a và 𝑣 b, khoảng cách Manhattan được định nghĩa như sau:

𝑖=1

𝑚𝑎𝑛_𝑑𝑖𝑠𝑡(𝑣⃗ 𝑎,𝑣⃗ 𝑏) = ∑ |𝑤𝑎𝑖 − 𝑤𝑏𝑖|

Mức độ tương đồng giữa hai vector được xác định bằng công thức:

𝑛 ∑ |𝑤𝑎𝑖 − 𝑤𝑏𝑖| 𝑖=1

28

𝑚𝑎𝑛_𝑠𝑖𝑚 = 1 − = 1 − 𝑚𝑎𝑛_𝑑𝑖𝑠𝑡(𝑣⃗ 𝑎,𝑣⃗ 𝑏) 𝑛 1 𝑛

Thuyết minh ĐT NCKHCHƯƠNG IV: PHƯƠNG PHÁP TÍNH ĐỘ TƯƠNG ĐỒNG VĂN BẢN 4.4. Độ tương đồng văn bản trong tiếng Việt

Thông thường khi đánh giá độ tương tự văn bản, chúng ta cần phân tích văn bản thành các đơn vị nhỏ hơn và thực hiện đánh giá dựa trên các đơn vị này. Việc xử lý văn bản và tách từ vựng đã được đề cập trong chương 2, phương pháp cho bài toán so tự sánh văn bản tiếng Việt. Một số bộ công cụ tách từ tiếng Việt như vnTokenizer, JvnTextPro đã được xây dựng và cho kết quả khả quan có thể sử dụng làm bước tiền xử lý cho hệ thống so sánh văn bản. Sau khi tách từ, mỗi văn bản Ti sẽ được biểu diễn bằng một vector các từ có dạng: 𝑇𝑖 = {𝑤1, 𝑤2, … , 𝑤𝑛𝑖} với ni là số từ tách được của Ti.

Trong nhiều trường hợp, độ tương tự giữa hai đoạn văn bản có thể xác định dựa trên so khớp từ đơn giản, điểm tương tự được xác định dựa trên số đơn vị từ vựng xuất hiện ở cả hai đoạn văn bản đầu vào. Tuy nhiên, phương pháp này không thể khẳng định được độ tương tự ngữ nghĩa của văn bản do chưa quan tâm tới hiện tượng đồng nghĩa của từ, tầm quan trọng của từ như tần suất xuất hiện, vị trí xuất hiện của từ và câu trong văn bản.

Các phương pháp đánh giá độ tương tự văn bản chủ yếu dựa trên hai yếu tố: độ

tương tự ngữ nghĩa giữa các từ và độ tương tự theo trật tự của các từ trong văn bản.

 Đánh giá độ tương tự ngữ nghĩa giữa các từ: một số phương pháp sử dụng mạng từ (WordNet), một số khác dựa trên kho ngữ liệu Web hoặc dựa trên phân tích ngữ nghĩa ẩn.

 Đánh giá độ tương tự theo trật tự của từ trong văn bản.

Đánh giá về độ tương tự ngữ nghĩa của từ được dùng để tạo ra các vector đặc trưng ngữ nghĩa của văn bản. Vector đặc trưng này sử dụng các công thức trong mục 4.2 cho ta một phép đo độ tương tự giữa hai văn bản tương ứng.

4.4.1. Độ tương tự ngữ nghĩa từ - từ

4.4.1.1. *Độ tương tự ngữ nghĩa từ - từ dựa trên WordNet

Wordnet là cơ sở dữ liệu tri thức từ vựng được thiết kế dựa trên những lý thuyết về ngôn ngữ tâm lý theo cách liên tưởng từ ngữ của con người [6]. WordNet được tổ chức dựa theo các quan hệ ngữ nghĩa. Một quan hệ ngữ nghĩa là một quan hệ giữa các nghĩa. Một từ có thể có nghiều nghĩa và khi đó mỗi nghĩa sẽ thuộc vào những tập đồng nghĩa khác nhau. Ngược lại, mỗi tập đồng nghĩa lại có thể chứa một hoặc nhiều hơn các từ khác nhau. Khi đó quan hệ ngữ nghĩa có thể được xem như là con trỏ giữa các tập đồng nghĩa.

4.4.1.2. Độ tương tự ngữ nghĩa từ - từ dựa trên ngữ liệu

29

Độ tương tự ngữ nghĩa dựa trên tập ngữ liệu (corpus) xác định mức độ tương tự về mặt ngữ nghĩa giữa các từ sử dụng thông tin xuất phát từ tập ngữ liệu lớn. Một số phương pháp xác định như sau:

Thuyết minh ĐT NCKHCHƯƠNG IV: PHƯƠNG PHÁP TÍNH ĐỘ TƯƠNG ĐỒNG VĂN BẢN

a) PMI (Pointwise Mutual Information) – thông tin chung dựa trên điểm

PMI được đưa ra bởi Turney 2001 như một độ đo không giám sát để đánh giá độ tương tự ngữ nghĩa của từ. PMI sử dụng dữ liệu đã tập hợp từ việc tìm kiếm thông tin (PMI-IR), dựa trên hiện tượng đồng xảy ra của các từ trên tập ngữ liệu lớn để xác định độ tương tự cho 2 từ w1 và w2 như sau:

𝑃𝑀𝐼(𝑤1, 𝑤2) = 𝑙𝑜𝑔2 𝑝(𝑤1, 𝑤2) 𝑝(𝑤1) ∗ 𝑝(𝑤2)

b) *LSA (Latent Semantic Analysis) – phân tích ngữ nghĩa ẩn - Xây dựng ma trận T (ma trận từ – tài liệu) thể hiện tập ngữ liệu. - Giảm số chiều SVD

SVD có thể được xem là cách khắc phúc một số hạn chế của mô hình không gian vecto chuẩn như số chiều cao, giúp cho LSA được tính với số chiều thấp hơn và mối quan hệ giữa từ - văn bản được khai thác. Độ tương tự trong không gian kết quả được đo bằng độ tương tự Cosine. Ngoài ra, LSA cũng sinh ra một mô hình không gian vector thể hiện sự đồng nhất giữa các từ, cụm từ và các văn bản.

4.4.2. Độ tương tự ngữ nghĩa của văn bản

Việc đánh giá độ tương tự ngữ nghĩa giữa hai văn bản trong đa số các nghiên cứu sử dụng vector đặc trưng cho ngữ nghĩa của văn bản. Mỗi thành phần trong vector này được thiết lập từ việc tính độ tương tự của một từ trong văn bản với các từ trong văn bản còn lại, trọng số của thành phần là độ đo tương tự lớn nhất.

Giả sử cho hai văn bản (đã được tách từ vựng) như sau:

T1 = { w11, w12, …, w1m1 }

T2 = { w21, w22, …, w2m2 }

Trong đó:

o wij là từ thứ j trong văn bản di (i=1,2) o mi là số lượng từ vựng tách được của văn bản Ti.

Tập các từ không giống nhau của cả hai văn bản là,

T = T1 ∪ T2 = { w1, w2, …, wm }

Véc-tơ đặc trưng ngữ nghĩa cho văn bản T1, ký hiệu V1 = (v11, v12, …, v1m)

được xây dựng như sau:

 Xét lần lượt từng từ wi ∈ T, tính độ tương tự ngữ nghĩa với mỗi từ trong T1, độ

30

đo tương tự lớn nhất được đưa vào thành phần v1i tương ứng trong V1. v1i = max{ sim(wi, w1j) | j =1..m1 }, với i=1..m

Thuyết minh ĐT NCKHCHƯƠNG IV: PHƯƠNG PHÁP TÍNH ĐỘ TƯƠNG ĐỒNG VĂN BẢN

 Độ tượng tự ngữ nghĩa của hai văn bản được tính dựa trên hai véc-tơ đặc trưng ngữ nghĩa tương ứng. Hệ số cosin là một trong các độ đo hay được sử dụng để tính độ tương tự này:

2

2

𝑚 ∑ 𝑣1𝑖 𝑖=1 𝑚 √∑ 𝑣1𝑖 𝑖=1

= 𝑠𝑖𝑚𝑆(𝑇1, 𝑇2) = 𝑉1. 𝑉2 |𝑉1|. |𝑉2| . 𝑣2𝑖 𝑚 √∑ 𝑣2𝑖 𝑖=1

Để tính toán độ tương tự (sim) giữa hai từ, trong tiếng Anh người ta có thể dựa vào mạng từ WordNet, tuy nhiên với tiếng Việt mạng từ chưa được xây dựng đầy đủ nên một phương án là sử dụng công cụ dịch từ tiếng Việt ra tiếng Anh, sau đó đánh giá độ tương tự đối với cặp từ tiếng Anh bằng mạng WordNet như trong đề tài của tác giả Dương Thăng Long [5]. Một số nghiên cứu khác sử dụng phương pháp phân tích ngữ nghĩa ẩn LSA hay PMI để đo độ tương tự của từ dựa trên tập ngữ liệu.

4.4.3. Độ tương tự về thứ tự của từ trong văn bản

Độ tương tự về thứ tự của từ là một yếu tố quan trọng ảnh hưởng đến độ tương tự của văn bản. Các văn bản cùng chứa một tập từ vựng giống nhau nhưng khác nhau về vị trí có thể có ý nghĩa hoàn toàn khác nhau.

Ví dụ cho hai câu:

T1 = { con_chó, cắn, con_mèo }

T2 = { con_mèo, cắn, con_chó }

Hai câu trên cùng chứa một tập các từ giống nhau và gần giống nhau về thứ tự từ, chỉ sai khác thứ tự của cặp từ “con_mèo” và “con_chó”. Nếu chỉ dựa trên độ tương tự ngữ nghĩa của văn bản thì hai văn bản nếu cùng chứa một tập từ giống nhau sẽ cho kết quả là hoàn toàn giống nhau, có nghĩa là sim(T1,T2)=1. Tuy nhiên, hai câu trên có ý nghĩa không giống nhau, sự khác nhau của hai câu chính là do sự sai khác về vị trí của các từ trong câu.

Tác giả Dương Thăng Long trong đề tài nghiên cứu của mình [5] đã đưa ra

phương pháp đánh giá độ tương tự của văn bản dựa trên thứ tự của từ như sau:

 Với mỗi cặp văn bản T1 và T2, xác định tập các từ vựng phân biệt của cả hai

văn bản T = T1 ∪ T2.

 Vector đặc trưng thứ tự từ của hai văn bản, kí hiệu R1 = (r11, r12, …, r1m) và R2

= (r21, r22, …, r2m), được tính dựa trên tập T.

o Vector thứ tự từ biểu diễn thứ tự của mỗi từ thuộc T nằm ở vị trí nào

trong văn bản tương ứng.

o Với mỗi từ wi ∈ T, tìm một từ đúng hoặc gần nghĩa nhất trong T1 để xác định trọng số cho phần tử r1i trong R1 theo một trong ba trường hợp sau:

31

 Nếu từ wi có trong T1 thì r1i là số thứ tự của từ đó trong T1.

Thuyết minh ĐT NCKHCHƯƠNG IV: PHƯƠNG PHÁP TÍNH ĐỘ TƯƠNG ĐỒNG VĂN BẢN

 Tìm từ trong T1 gần nghĩa nhất với wi, sử dụng phương pháp đo độ tương tự ngữ nghĩa giữa hai từ. Nếu độ đo này vượt ngưỡng θ cho trước thì r1i là số thứ tự của từ đó trong T1.

 Nếu không tìm thấy hoặc độ tương tự giữa từ các trong T1 và wi

không vượt ngưỡng thì đặt r1i là 0.

Vector đặc trưng thứ tự của từ biểu diễn thông tin về cấu trúc của từ trong văn bản. Mức độ giống nhau về cấu trúc của hai văn bản được tính toán dựa trên vector đặc trưng thứ tự từ bằng công thức sau:

𝑚 𝑖=1 𝑚 𝑖=1

𝑠𝑖𝑚𝑅 = 1 − = 1 − |𝑅1 − 𝑅2| |𝑅1 + 𝑅2| √∑ (𝑟1𝑖 − 𝑟2𝑖)2 √∑ (𝑟1𝑖 + 𝑟2𝑖)2

4.4.4. Kết hợp giữa các độ đo để đánh giá độ tương tự giữa hai văn bản

Trong các phân tích ở trên, độ tương tự ngữ nghĩa thể hiện phép đo dựa trên nghĩa từ vựng, còn độ tương tự cấu trúc của từ thể hiện mối quan hệ về thứ tự giữa các từ, các từ đứng trước hoặc sau các từ khác. Cả hai độ tương tự này đều có vai trò quan trọng trong xác định độ tương tự của văn bản. Do đó, để đo sự tương tự của các văn bản cần phải kết hợp của hai loại độ đo trên, độ tương tự về ngữ nghĩa và độ tương tự về thứ tự các từ trong văn bản. Biểu thức kết hợp giữa hai độ đo có dạng

𝑠𝑖𝑚 = 𝑎 ∗ 𝑠𝑖𝑚𝑆 + 𝑏 ∗ 𝑠𝑖𝑚𝑅 với a+ b = 1

32

Việc xác định bộ trọng số của mỗi độ đo tương tự (a,b) chưa có một công thức chung nào, chỉ có thể sử dụng phương pháp quan sát và thử nghiệm qua các dữ liệu thực tế để có lựa chọn tốt nhất cho hệ thống. Phương án cân bằng các tiêu chí là một lựa chọn, trong đó trọng số của các tiêu chí kết hợp có giá trị giống nhau, tức là a = 0.5 và b = 0.5.

Thuyết minh ĐT NCKH

CHƯƠNG V: ỨNG DỤNG MÔ HÌNH ĐỒ THỊ

CHƯƠNG V: ỨNG DỤNG MÔ HÌNH ĐỒ THỊ VÀO SO SÁNH VĂN BẢN TIẾNG VIỆT

5.1. Mô hình hệ thống

Nội dung của các văn bản đầu vào được lưu trữ trong file text. Sau khi thực hiện tiền xử lý văn bản ta sẽ thu được 2 file: một file chứa các từ được tách (các từ được phân cách bởi dấu “|”) và một file chứa các câu, ở đầu mỗi câu có chứa số thứ tự của câu đặt trong cặp dấu “[ ]”

2. Xử lý từ - Loại bỏ từ dừng 1. Tiền xử lý - Tách câu - Tách từ

- Xử lý từ đồng

nghĩa

Văn bản gốc

3. Vector hóa văn bản 4. Tính độ tương đồng văn bản

Hình 7: Mô hình hệ thống so sánh văn bản tiếng Việt

Trong mô hình này, đầu vào là các văn bản tiếng Việt. Các văn bản này được

xử lý qua 4 giai đoạn:

5.1.1. Tiền xử lý

Giai đoạn này có nhiệm vụ tách văn bản ra các từ và các câu. Do việc xây dựng bộ tách từ khá phức tạp và nằm ngoài phạm vi nghiên cứu nên đề tài sử dụng bộ tách từ WordSegForTV đã được viết sẵn để thực hiện bước tiền xử lý văn bản.

Nội dung của các văn bản đầu vào được lưu trữ trong file txt, doc. Sau khi thực hiện tiền xử lý văn bản ta sẽ thu được 2 file: một file chứa các từ được tách (các từ được phân cách bởi dấu “|”) và một file chứa các câu, ở đầu mỗi câu có chứa số thứ tự của câu đặt trong cặp dấu “[ ]”.

5.1.2. Xử lý từ

Giai đoạn này nhằm mục đích loại bỏ các từ dừng dựa trên từ điển từ dừng có trước, sau đó với mỗi từ trong câu, dựa vào từ điển từ đồng nghĩa để lập ra danh sách các từ đồng nghĩa.

33

Đầu vào của giai đoạn này là tập tin văn bản đã được thêm dấu phân tách từ ở bước trên. Thuật toán thực hiện việc chọn ra các từ, các câu, các từ đồng nghĩa và loại bỏ từ dừng được mô tả như sau:

Thuyết minh ĐT NCKH

CHƯƠNG V: ỨNG DỤNG MÔ HÌNH ĐỒ THỊ

Input: Tệp văn bản đã tách từ.

Output: Tập các từ Words, tập các câu Sents.

1. Mở tệp văn bản

ST=Nội dung file

2. //Tách ra các câu

n=0; //đếm số lượng câu

k=1;

while k

{

if ST(k)=Dấu kết thúc câu

{

n=n+1;

Sents(i)=Câu kết thúc tại vị trí k;

}

k=k+1;

}

3. //Tách ra các từ

k=1;

while k

{

if ST(k)= “|”

{

word=Chọn ra từ kết thúc tại k;

Chuẩn hoá word; //Loại bỏ dấu cách, chuyển về chữ thường

if word có trong từ điển từ dừng

word= “” ;

else if word có trong từ điển đồng nghĩa

Đưa word và các từ đồng nghĩa vào Tập từ Term;

Else Đưa word vào Tập từ Words;

34

}

Thuyết minh ĐT NCKH

CHƯƠNG V: ỨNG DỤNG MÔ HÌNH ĐỒ THỊ

Tăng k;

}

4. return Words, Sents;

Đề tài sử dụng từ điển các từ dừng do website www.xulyngonngu.com cung cấp để loại bỏ bớt các từ không có giá trị trong việc tính độ tương tự ngữ nghĩa giữa 2 câu. Từ điển đồng nghĩa được sử dụng trong đề tài dựa trên “Từ điển đồng nghĩa và trái nghĩa tiếng Việt dành cho học sinh”, tác giả Trần Trọng Dương, Nguyễn Quốc Khánh, 2008.

5.1.3. * Vector hóa văn bản

Giai đoạn này có nhiệm vụ xây dựng vector biểu diễn văn bản gồm vector đặc trưng ngữ nghĩa và vector thứ tự từ, sử dụng danh sách các câu và các từ đã được xử lý ở trên.

Để xây dựng vector biểu diễn văn bản ta cần thực hiện các bước sau:

- Xác định danh sách tập từ chung cho hai văn bản. Tập từ chung này bao gồm

tất cả những từ phân biệt có trong hai văn bản.

- Tính độ tương đồng về ngữ nghĩa cho các từ trong mỗi văn bản, cụ thể là trong

từng câu, đưa ra vector ngữ nghĩa cho các câu trong mỗi văn bản.

o Kết hợp độ tương tự ngữ nghĩa với tần suất đặc trưng của từ để tính lại trọng số của vector ngữ nghĩa nhằm tăng độ phủ của từ. Kĩ thuật tính tần suất đặc trưng dựa trên tần số từ khóa và tần số văn bản đảo ngược tf*idf cho phép nhấn mạnh vai trò của từ/cụm từ trong ngữ nghĩa, nội dung của văn bản.

- Tìm vị trí của từ đưa ra vector thứ tự từ của câu trong mỗi văn bản.

5.3.1.1. Vector đặc trưng ngữ nghĩa

Duyệt qua các từ trong mỗi văn bản, tính trọng số độ tương tự ngữ nghĩa của từ và tính Tf*idf cho các từ, dựa vào giá trị Tf*idf để loại bỏ các từ không mang nhiều ý nghĩa ra khỏi văn bản và WordList. Có thể chọn một ngưỡng nào đó, thường chọn ngưỡng = 0.2.

𝑖 = 𝑡𝑓(𝑡𝑖, 𝑠𝑒𝑛𝑡𝑗) ∗ 𝑖𝑑𝑓(𝑡𝑖)

Giả sử văn bản gồm n câu được đánh số là sent1, sent2, … sentn và m từ t1, t2, … tm, gọi nij là số lần xuất hiện của từ ti trong câu sentj. Thành phần thứ i của vector văn bản sentj được tính bằng:

𝑠𝑒𝑛𝑡𝑗

Trong đó:

 i = 1..m, j = 1..n  Giá trị tf(ti, sentj) có thể được tính bằng nhiều cách như dựa trên tổng số lần xuất hiện của các từ trong tài liệu hoặc số lần xuất hiện lớn nhất của 35

Thuyết minh ĐT NCKH

CHƯƠNG V: ỨNG DỤNG MÔ HÌNH ĐỒ THỊ

các từ, hoặc ln số lần xuất hiện số từ (sử dụng trong hệ thống Cornell SMART) [4].

Trong cài đặt thử nghiệm, tf(ti,sentj) được tính dựa vào ln số lần xuất hiện của

từ theo công thức:

𝑡𝑓(𝑡𝑖, 𝑠𝑒𝑛𝑡𝑗) = { 0 𝑖𝑓 𝑛𝑖𝑗 = 0 1 + ln(1 + 𝑙𝑛 𝑛𝑖𝑗) 𝑖𝑓 𝑛𝑖𝑗 > 0

 Với mỗi từ ti, giá trị idf(ti) được tính bẳng tỉ lệ các câu xuất hiện từ ti với

tổng số câu có được.

𝑛

Gọi S là tập hợp các câu và 𝑆𝑡𝑖 là tập các câu có chứa từ ti.

𝑆 = ⋃ 𝑠𝑒𝑛𝑡𝑗 1

𝑆𝑡𝑖 = {𝑠𝑒𝑛𝑡𝑗|𝑛𝑖𝑗 > 0}

Giá trị idf(ti) được tính bằng hàm logarit sau:

𝑖𝑑𝑓(𝑡𝑖) = 𝑙𝑜𝑔 1 + |𝑆| |𝑆𝑡𝑖|

5.3.1.2. Vector thứ tự từ

Độ tương tự cho toán bộ câu là sự kết hợp giữa độ tương tự của vector ngữ nghĩa và vector thứ tự biểu diễn hai câu. Các độ đo Cosine, Jaccard… thường được lựa chọn để xác định độ tương đồng giữa các vector biểu diễn câu. Trong thử nghiệm, đề tài sử dụng công thức tính độ tương tự Cosine.

 Độ tương tự ngữ nghĩa

∑

𝑚 𝑘,𝑙=1

𝑘 𝑠𝑒𝑛𝑡𝑖

𝑙 𝑠𝑒𝑛𝑡𝑗

𝑠𝑖𝑚(𝑠𝑒𝑛𝑡𝑖, 𝑠𝑒𝑛𝑡𝑗) =

√∑

𝑚 𝑘=1

𝑘 𝑠𝑒𝑛𝑡𝑖

𝑚 𝑙 √∑ 𝑠𝑒𝑛𝑡𝑖 𝑙=1

 Độ tương tự thứ tự từ

5.1.4. *Tính độ tương tự văn bản

Ma trận liên kết biểu thị mối quan hệ giữa các câu trong các văn bản được biểu diễn

như sau:

𝐷(𝑠𝑒𝑛𝑡𝑖, 𝑠𝑒𝑛𝑡𝑗) = {

0 𝑖𝑓 𝑠𝑖𝑚(𝑠𝑒𝑛𝑡𝑖, 𝑠𝑒𝑛𝑡𝑗) < 𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 𝑠𝑖𝑚(𝑠𝑒𝑛𝑡𝑖, 𝑠𝑒𝑛𝑡𝑗) 𝑖𝑓 𝑠𝑖𝑚(𝑠𝑒𝑛𝑡𝑖, 𝑠𝑒𝑛𝑡𝑗) ≥ 𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑

36

5.1.4.1. Ma trận liên kết

Thuyết minh ĐT NCKH

CHƯƠNG V: ỨNG DỤNG MÔ HÌNH ĐỒ THỊ

Với threshold là một ngưỡng được cho trước và được tính toán bằng thực nghiệm đối với các loại văn bản khác nhau. Trong cài đặt, qua tham khảo một số đề tài về xử lý tiếng Việt, đề tài sử dụng threshold = 0.2.

5.1.4.2. Thuật toán xây dựng ma trận liên kết

Input: Tập từ T, số lượng từ m, tập các câu Sent, số lượng câu n, ngưỡng

threshold.

Output: Đồ thị liên kết các câu Dis(i,j), i=1..m, j=1..n.

1. {Sắp xếp tập từ T}

HeapSort(T,m);

2. {Tính tf-idf}

for i = 1 to m

for j = 1 to n

if T(i)=T(j) then N(i,j) = N(i,j) + 1;

{Tính tf}

for i = 1 to m

for j = 1 to n

{

tf(i,j) = 0;

if N(i,j) > 0 then tf(i,j) = 1 + ln(1+ln(N(i,j)))

}

{Tính idf}

for i = 1 to m

{

count = 0;

for j = 1 to n

if N(i,j) > 0 then count = count + 1;

idf(i) = ln((1+n)/count)

}

3. {Tính toán độ tương đồng}

for i = 1 to m

37

for j = 1 to n

Thuyết minh ĐT NCKH

CHƯƠNG V: ỨNG DỤNG MÔ HÌNH ĐỒ THỊ

{

sim = cos(senti, sentj)

if sim > threshold then Dis(i,j) = sim;

}

4. return Dis(i,j)

5.2. Mô hình thực nghiệm

5.2.1. Môi trường thực nghiệm

Chương trình được xây dựng và thử nghiệm với các bộ hỗ trợ sau:

- Phần mềm WordSegForTV nhằm thực hiện tách từ trong văn bản. - Từ điển từ dừng: gồm 807 từ do website xulyngonngu.com cung cấp. - Từ điển đồng nghĩa: gồm 603 mục từ với tổng cộng 2867 từ đồng nghĩa. - Tập văn bản thử nghiệm gồm các văn bản có nội dung với nhiều lĩnh vực khác

nhau được lấy từ hai trang http://vnexpress.net và http://vietnamenet.vn.

5.2.2. *Chương trình ứng dụng thử nghiệm

Chương trình thử nghiệm được xây dựng đơn giản, cho phép nhập trực tiếp hai đoạn văn cần đánh giá hoặc chọn từ tệp, sau đó so sánh trên hai văn bản. Ngoài ra, chương trình cho phép chọn các trọng số kết hợp nhằm đánh giá sự ảnh hưởng của các tiêu chí tham gia đo độ tương tự giữa các văn bản.

Hình 8: Chương trình thử nghiệm so sánh độ tương tự văn bản

Các trọng số nên chọn ưu tiên cho yếu độ độ tương tự đặc trưng ngữ nghĩa bởi những câu nào, đoạn văn nào có sự tương tự về ngữ nghĩa vượt ngưỡng mới cần quan tâm về độ tương tự thứ tự của từ.

38

5.2.3. *Kết quả thử nghiệm

Thuyết minh ĐT NCKH

KẾT LUẬN

KẾT LUẬN

Xử lý ngôn ngữ tự nhiên, phân loại và so khớp nội dung tài liệu văn bản trong những năm gần đây là lĩnh vực đang được quan tâm của cộng đồng khoa học trong và ngoài nước. Mục đích của đề tài là nghiên cứu, xây dựng thử nghiệm hệ thống so sánh văn bản tiếng Việt dựa trên sự kết hợp của các yếu tố độ tương tự ngữ nghĩa và độ tương tự thứ tự từ. Các kết quả đạt được của đề tài:

 Nghiên cứu tổng quan về đặc điểm của ngôn ngữ tiếng Việt và phương pháp xử

lý như sử dụng bộ tách từ, từ điển từ đồng nghĩa, từ điển từ dừng.

 Nghiên cứu các phương pháp tính độ tương đồng văn bản, vector hóa đặc trưng

ngữ nghĩa và cấu trúc thứ tự từ văn bản.

 Các kết quả nghiên cứu được áp dụng vào xây dựng thử nghiệm hệ thống so

sánh độ tương đồng giữa các văn bản.

Những nội dung quan trọng trong nghiên cứu bao gồm:

- Nhờ việc sử dụng bộ tách từ có thể phân biệt được khá chính xác từ đơn và từ

ghép nên ngữ nghĩa của văn bản phần nào được đảm bảo.

- Tần số xuất hiện của từ được kết hợp trong biểu diễn vector đặc trưng ngữ nghĩa của văn bản. Đây là một độ đo hữu dụng được sử dụng trong phần lớn các công trình nghiên cứu về xử lý văn bản để đánh giá tầm quan trọng của từ. - Độ tương tự giữa các văn bản được tính dựa vào sự kết hợp của các yếu tố độ

tương tự ngữ nghĩa từ và độ tương tự thứ tự từ.

o Độ tương tự ngữ nghĩa từ được tính dựa trên đặc điểm của tập ngữ liệu so sánh, không phụ thuộc vào việc sử dụng các từ điển dịch từ tiếng Việt sang tiếng Anh hay mạng ngữ nghĩa.

o Công thức Cosine sử dụng để đo độ tương tự giữa các vector biểu diễn là công thức đã được áp dụng trong đa số các đề tài về xử lý văn bản tiếng Anh.

39

Độ tương tự văn bản có nhiều ứng dụng trong các bài toán khác nhau, từ mức độ thấp đến cao như trích chọn thông tin, tóm tắt văn bản, phân lớp văn bản… và đặc biệt trong bài toán chống sao chép, đạo văn. Do hạn chế về mặt thời gian và kĩ thuật nên hệ thống so sánh mới chỉ dừng ở việc so sánh trên các văn bản đơn, chưa thể ứng dụng để quét văn bản so với tập dữ liệu có trước. Hướng phát triển của đề tài tiếp tục nghiên cứu và hoàn thiện hơn công đoạn xử lý tiếng Việt như xử lý từ đồng nghĩa và từ dừng, kết hợp từ/cụm từ… để làm tăng tính ngữ nghĩa cho vector biểu diễn văn bản, từ đó mở rộng phạm vi ứng dụng của hệ thống so sánh để có thể thực hiện so sánh trên đa văn bản.

TÀI LIỆU THAM KHẢO

1. Nguyễn Trung Kiên, “Phân đoạn tiếng Việt sử dụng mô hình CRFs”, ĐH

Quốc gia Hà Nội, 2006.

2. Trần Ngọc Phúc, “Phân loại nội dung tài liệu Web”, Đại học Lạc Hồng, 2012.

3. “Mô hình biểu diễn văn bản thành đồ thị” – Đại học Khoa học Tự nhiên,

2008.

4. Lê Quý Tài, “Nghiên cứu các phương pháp xử lý tiếng Việt, ứng dụng cho

tóm tắt văn bản”, Đại học Quốc gia Hà Nội, 2011.

5. TS. Dương Thăng Long, “Nghiên cứu độ tương đồng văn bản trong tiếng Việt và ứng dụng hỗ trợ đánh giá việc sao chép bài điện tử”, Viện Đại học Mở Hà Nội, 2014.

6. Đỗ Thị Thanh Nga, “Tính toán độ tương tự ngữ nghĩa văn bản dựa vào độ tương tự giữa từ với từ”, Đại học Công nghệ Đại học Quốc gia Hà Nội, 2010.