Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng vnmatch

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

------------------------------------------

LUẬN VĂN THẠC SĨ KHOA HỌC

TÌM HIỂU VỀ ĐỐI SÁNH LƯỢC ĐỒ VÀ

XÂY DỰNG ỨNG DỤNG VNMATCH

NGÀNH: CÔNG NGHỆ THÔNG TIN

NGÔ VĂN QUÂN

HÀ NỘI 2006

i

Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch

Ngô Văn Quân, lớp cao học CNTT 2004

Lời cảm ơn

Trong lời đầu tiên của báo cáo luận văn tốt nghiệp “Tìm hiểu về đối sánh

lược đồ và xây dựng ứng dụng VNMatch” này, tôi muốn gửi những lời cảm ơn và

biết ơn chân thành của mình tới tất cả những người đã hỗ trợ, giúp đỡ tôi về

chuyên môn, vật chất và tinh thần trong quá trình thực hiện Đồ án.

Trước hết, tôi xin chân thành cảm ơn TS. Nguyễn Kim Anh, bộ môn Hệ

thống thông tin, Khoa Công nghệ thông tin trường Đại học Bách khoa Hà Nội,

người đã trực tiếp hướng dẫn, nhận xét, giúp đỡ tôi trong suốt quá trình thực hiện

luận văn.

Xin chân thành cảm ơn Khoa Công nghệ thông tin, Trung tâm Đào tạo và

Bồi dưỡng sau đại học Trường Đại học Bách Khoa Hà Nội đã giúp đỡ tôi trong suốt

quá trình học tập và nghiên cứu.

Tôi cũng muốn gửi lời cảm ơn tới TS. Đỗ Hồng Hải

1

, tác giả của hệ thống

COMA++; anh Lê Hồng Phương2

tác giả của vnTokenizer, vnLTag; Enrico May,

sinh viên nghiên cứu về dự án Cupid. Tôi cũng xin bày tỏ lòng biết ơn đến gia

đình và những người bạn thân đã giúp đỡ, động viên tôi rất nhiều trong suốt quá

trình học tập và làm luân văn tốt nghiệp.

Do thời gian thực hiện có hạn, kiến thức chuyên môn còn nhiều hạn chế

nên đồ án tôi thực hiện chắc chắn không tránh khỏi những thiếu sót nhất định.

Tôi rất mong nhận được ý kiến đóng góp của thầy, cô giáo và các bạn.

Xin chân thành cảm ơn !

Hà Nội, ngày 09 tháng 10 năm 2006

1

http://dbs.uni-leipzig.de/personen/hong_hai_do

2

Lê Hồng Phương, công tác tại trường Đại Học Quốc Gia Hà Nội, hiện đang làm nghiên

cứu sinh tại Pháp

ii

Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch

Ngô Văn Quân, lớp cao học CNTT 2004

Chương 1 Mở đầu ............................................................................. 1

1 Đối sánh lược đồ..........................................................................2

2 Sự hỗn tạp ngữ nghĩa...................................................................3

3 Định nghĩa bài toán......................................................................6

3.1 Schemas..............................................................................6

3.2 Đầu vào bài toán (Input)........................................................7

3.3 Đầu ra bài toán (Output)........................................................7

3.4 Kiến trúc chung ....................................................................8

4 Ứng dụng của bài toán đối sánh lược đồ..........................................9

4.1 Các ứng dụng tích hợp dữ liệu và data warehouse......................9

4.2 E-Business ......................................................................... 11

4.3 Semantic Web .................................................................... 12

5 Các vấn đề mở .......................................................................... 13

5.1 Khả năng biểu diễn của ngôn ngữ.......................................... 13

5.2 Làm việc với các lược đồ có kích thước lớn .............................. 13

5.3 Sự kết hợp của các phương pháp đối sánh .............................. 14

Chương 2 Các phương pháp tiếp cận ................................................. 15

1 Các dự án liên quan ................................................................... 15

1.1 COMA++ ........................................................................... 15

1.2 SEMINT ............................................................................. 16

1.3 LSD .................................................................................. 16

1.4 SKAT................................................................................. 16

1.5 TransScm .......................................................................... 16

1.6 DIKE ................................................................................. 17

1.7 SIMILARITY FLOODING ........................................................ 17

1.8 Cupid ................................................................................ 17

2 Các phương pháp đối sánh lược đồ ............................................... 20

2.1 Tiêu chuẩn phân loại ........................................................... 20

2.2 Đối sánh dựa trên schema (schema-based) ............................ 21

2.2.1 Phương pháp tiếp cận dựa trên ngôn ngữ (linguistic) .......... 22

2.2.2 Phương pháp tiếp cận dựa trên ràng buộc......................... 23

2.2.3 Phương pháp tiếp cận dựa trên cấu trúc ........................... 23

2.3 Đối sánh dựa trên dữ liệu ..................................................... 23

2.4 Đối sánh kết hợp................................................................. 24

2.5 Match Cardinality ................................................................ 24

2.6 Các hệ số mặc định trong bài toán đối sánh ............................ 25

3 Các phương pháp đánh giá hệ thống đối sánh ................................ 26

Chương 3 Thiết kế hệ thống đối sánh lược đồ. .................................... 30

1 Khảo sát................................................................................... 30

2 Giới thiệu ................................................................................. 33

2.1 Giới thiệu bài toán đối sánh lược đồ. ...................................... 33

2.2 Xử lý schema trong tiếng Việt ............................................... 33

3 Thiết kế.................................................................................... 35

iii

Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch

Ngô Văn Quân, lớp cao học CNTT 2004

3.1 Kiến trúc hệ thống .............................................................. 35

3.2 Input ................................................................................ 36

3.2.1 Schema ..............................Error! Bookmark not defined.

3.2.2 WordNet ...................................................................... 39

3.2.3 Output ........................................................................ 40

3.3 Mức ngôn ngữ (linguistic matching) ....................................... 41

3.3.1 Các thuật toán đối sánh cơ bản ....................................... 42

3.3.2 Thuật toán đối sánh kết hợp ........................................... 44

3.4 Mức cấu trúc ...................................................................... 51

3.5 Chọn lựa ánh xạ ................................................................. 55

4 Cài đặt và kết quả ..................................................................... 56

4.1 Cài đặt .............................................................................. 56

4.2 Kết quả thử ngiệm .............................................................. 60

5 Kết luận và hướng phát triển ....................................................... 71

5.1 Kết luận ............................................................................ 71

5.2 Hướng phát triển ................................................................ 72

Tài liệu tham khảo ............................................................................. 75

Sách, bài báo, luận văn.................................................................... 75

Website ......................................................................................... 75

iv

Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch

Ngô Văn Quân, lớp cao học CNTT 2004

Mục lục hình ảnh

Hình 1-1: Đối sánh lược đồ 2

Hình 1-2: Xung đột ngôn ngữ 5

Hình 2-1: Schemas 7

Hình 2-2: Kiến trúc chung của bài toán đối sánh lược đồ 8

Hình 2-3: Minh họa hệ thống tích hợp dữ liệu giúp người dùng tìm văn bản 10

Hình 2-4: Data warehouse 11

Hình 2-5: Kiến trúc COMA++ 15

Hình 2-6: Kiến trúc SEMINT Error! Bookmark not defined.

Hình 2-7: Các phương pháp đối sánh lược đồ 20

Hình 2-8: Xây dựng các hệ số ưu tiên 26

Hình 2-9: Đánh giá hệ thống đối sánh 27

Hình 2-10: So sánh F-Measure và Overall 28

Hình 3-1: Sự hỗn tạp của các nguồn dữ liệu 31

Hình 3-2:Lược đồ văn bản 33

Hình 3-3: Kiến trúc hệ thống 36

Hình 3-4: Hợp nhất các lược đồ phân tán 38

Hình 3-5: Hợp nhất các kiểu thiết kế schema 38

Hình 3-6: Loại bỏ nút có kiểu đơn giản 38

Hình 3-7: Tái sử dụng các định nghĩa 39

Hình 3-8:Sơ đồ đối sánh mức ngôn ngữ (linguistic matching) 41

Hình 3-9: Sơ đồ thuật toán đối sánh kết hợp 45

Hình 3-10: Phân tích phần tử đầu vào 46

Hình 3-11: Thực hiện bước Direction và Selection 48

Hình 3-12: Tổng hợp kết quả 49

Hình 3-13: SimCube theo phương pháp đối sánh kết hợp 50

Hình 3-14: Kết quả sau khi thực hiện Aggregation 50

Hình 3-15: Kết quả sau khi thực hiện Direction và Selection 50

Hình 3-16:Kết quả sau khi tổng hợp 51

Hình 3-17: Hệ số tương tự của 2 node lá 52

Hình 3-18: Hệ số tương tự của 2 node trong 52

Hình 3-19: Sự phụ thuộc của hệ số tương tự vào ngữ cảnh 55

Hình 3-20:Cấu trúc VNMatch 57

Hình 3-21: MatchLib, phần core của VNMatch 57

Hình 3-22: Lớp HybridMatcher 58

Hình 3-23: VNMatch Framework (đề xuất) 73

v

Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch

Ngô Văn Quân, lớp cao học CNTT 2004

Mục lục các công thức

Công thức 1: Cupid, hệ số tương tự của hai tập hợp................................ 19

Công thức 3 ...................................................................................... 19

Công thức 4 ...................................................................................... 19

Công thức 2: Công thức EditDistance biến đổi ........................................ 42

Công thức 3: Lấy Max......................................................................... 47

Công thức 4: Lấy theo trọng số............................................................ 47

Công thức 5: Lấy theo trung bình ......................................................... 47

Công thức 6: AverageSim ................................................................... 49

Công thức 7: DiceSim......................................................................... 49

Công thức 8: Wsim cho các node lá ...................................................... 54

Công thức 9: Liên kết mạnh ................................................................ 54

Công thức 10: ssim trong trường hợp là các node trong........................... 54

vi

Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch

Ngô Văn Quân, lớp cao học CNTT 2004

Bảng các từ viết tắt và thuật ngữ

Tiếng Anh Ý nghĩa Ghi chú

Data integration Tích hợp dữ liệu

Data translation Chuyển đổi dữ liệu

Data warehouse Nhà kho dữ liệu

DTD Document Type Definition

Global schema Lược đồ tổng thể

Holonym Bao hàm phần tử “Cây” bao hàm phần tử

“Thân cây”

Hypernym Bao hàm khái niệm thuật

ngữ

“Thực vật” bao hàm

khái niệm “Cây”

Hyponym Ngược với Hypernym “Cây” nằm trong khái

niệm “thực vật”

Local schema Lược đồ địa phương

Meronym Ngược với Holonym “Thân cây” là bộ phận

của cây

Ontology Đặc tả của khái niệm

OWL Web Ontology Language

Schema Lược đồ dữ liệu

Schema integration Tích hợp lược đồ

vii

Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch

Ngô Văn Quân, lớp cao học CNTT 2004

Semantic integration Tích hợp ngữ nghĩa

Schema mapping Ánh xạ lược đồ, tương tự

đối sánh lược đồ

Schema matching Đối sánh lược đồ

Synonym Từ đồng nghĩa

Web Semantic Web ngữ nghĩa

XSD XML Schema Definition