Nghiên cứu khai phá luật kết hợp trong cơ sở dữ liệu địa lý

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

LÊ THỊ HỒNG

NGHIÊN CỨU KHAI PHÁ LUẬT KẾT HỢP

TRONG CƠ SỞ DỮ LIỆU ĐỊA LÝ

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2011

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

LÊ THỊ HỒNG

NGHIÊN CỨU KHAI PHÁ LUẬT KẾT HỢP

TRONG CƠ SỞ DỮ LIỆU ĐỊA LÝ

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. ĐẶNG VĂN ĐỨC

Thái Nguyên – 2011

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

i

LỜI CẢM ƠN

Tôi xin gửi lời cảm ơn chân thành nhất tới PGS. TS Đặng Văn Đức - người

thầy đã tận tình hướng dẫn tôi trong suốt thời gian hoàn thành luận văn, đồng thời

cũng là người đã cho tôi những định hướng và ý kiến quý báu về lĩnh vực nghiên

cứu này.

Tôi xin bày tỏ lòng cảm ơn sâu sắc tới thầy cô, bạn bè cùng khóa, cùng lớp

đã giúp đỡ tôi trong suốt những năm học qua.

Xin cảm ơn gia đình, bạn bè, những người luôn khuyến khích, động viên và

giúp đỡ tôi trong mọi hoàn cảnh khó khăn.

Tôi xin cảm ơn các thầy cô trong trường Đại học Công nghệ thông tin &

truyền thông, Đại học Thái Nguyên, các thầy cô và đồng nghiệp trong khoa Công

nghệ thông tin & truyền thông, trường Đại học Hồng Đức, Thanh Hóa đã hết sức

tạo điều kiện cho tôi trong quá trình học và làm luận văn này.

Luận văn được hoàn thành trong thời gian hạn hẹp nên không thể tránh

được những thiếu sót. Tôi xin cảm ơn thầy cô, bạn bè, đồng nghiệp đã và sẽ có

những ý kiến đóng góp chân thành cho nội dung của luận văn, để tôi có thể tiếp tục

đi sâu tìm hiểu về lĩnh vực này trong tương lai.

Thái Nguyên, 9/2011

Lê Thị Hồng

[email protected]

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

ii

LỜI CAM ĐOAN

Tôi xin cam đoan kết quả đạt đƣợc trong luận văn là sản phẩm của riêng cá

nhân tôi, không sao chép lại của ngƣời khác. Trong toàn bộ nội dung luận văn,

những điều đã đƣợc trình bày hoặc là của riêng cá nhân tôi, hoặc là đƣợc tổng hợp

từ nhiều nguồn tài liệu. Tất cả các nguồn tài liệu tham khảo đƣợc dùng đều có xuất

xứ rõ ràng, đƣợc trích dẫn hợp pháp.

Tôi xin chịu hoàn toàn trách nhiệm và chịu mọi hình thức kỉ luật theo quy

định cho lời cam đoan của mình.

Thái Nguyên, 9/2011

Lê Thị Hồng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

iii

MỤC LỤC

TRANG

Trang phụ bìa

Lời cảm ơn .................................................................................................................. i

Lời cam đoan.............................................................................................................. ii

Mục lục......................................................................................................................iii

Danh mục các ký hiệu, các chữ viết tắt..................................................................... iv

Danh mục các bảng ................................................................................................... vi

Danh mục các hình (hình vẽ, ảnh chụp, đồ thị...) .................................................... vii

MỞ ĐẦU.....................................................................................................................1

CHƢƠNG 1: TỔNG QUAN VỀ DỮ LIỆU KHÔNG GIAN VÀ KHAI PHÁ DỮ

LIỆU KHÔNG GIAN .................................................................................................4

1.1. Cơ sở dữ liệu địa lý ..........................................................................................4

1.1.1. Quan hệ không gian và ràng buộc toàn vẹn không gian ..............................6

1.1.2. Phụ thuộc địa lý............................................................................................8

1.1.3. Geo-Ontology và ràng buộc toàn vẹn không gian......................................10

1.2. Luật kết hợp ...................................................................................................11

1.3. Luật kết hợp không gian ...............................................................................17

1.4. Tình hình nghiên cứu về khai phá luật kết hợp không gian...........................18

1.5. Khai phá luật kết hợp trong cơ sở dữ liệu địa lý............................................21

1.5.1. Phụ thuộc địa lý giữa đối tƣợng đích và đối tƣợng liên quan ....................21

1.5.1.1. Phụ thuộc địa lý và luật không đáng quan tâm...................................21

1.5.1.2. Phụ thuộc địa lý và kết nối không gian...............................................24

1.5.2. Phụ thuộc địa lý giữa các đối tƣợng liên quan ...........................................26

1.5.3. Phụ thuộc địa lý giữa các đối tƣợng liên quan ở các mức khác nhau ........28

CHƢƠNG 2: MỘT SỐ THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP KHÔNG

GIAN.........................................................................................................................34

2.1. Giới thiệu........................................................................................................34

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

iv

2.2. Tiền xử lý dữ liệu không gian phục vụ cho khai phá dữ liệu ........................36

2.2.1. Tiền xử lý dữ liệu, thuật toán cắt tỉa dữ liệu không gian đầu vào..............37

2.2.2. Đánh giá thuật toán cắt tỉa dữ liệu không gian đầu vào .............................40

2.3. Các thuật toán khai phá luật kết hợp không gian...........................................41

2.3.1. Thuật toán tạo tập thƣờng xuyên................................................................41

2.3.1.1. Thuật toán Apriori – KC.....................................................................42

2.3.1.2. Đánh giá thuật toán Apriori – KC.......................................................46

2.3.2. Thuật toán tạo tập thƣờng xuyên không dƣ thừa cực đại...........................47

2.3.2.1. Phụ thuộc địa lý và tập thƣờng xuyên đóng........................................48

2.3.2.2. Thuật toán Max-FGP ..........................................................................50

CHƢƠNG 3: CÀI ĐẶT CHƢƠNG TRÌNH THỬ NGHIỆM..................................53

3.1. Giới thiệu........................................................................................................53

3.2. Lựa chọn công nghệ .......................................................................................53

3.2.1. Công cụ biên tập, lƣu trữ và thể hiện các tầng dữ liệu bản đồ ...................53

3.2.2. Ngôn ngữ lập trình và hệ quản trị CSDL ...................................................55

3.3. Thiết kế chƣơng trình.....................................................................................56

3.4. Dữ liệu thử nghiệm ........................................................................................58

3.5. Cài đặt chƣơng trình.......................................................................................59

3.5.1. Dữ liệu đầu vào ..........................................................................................60

3.5.2. Mô đun tiền xử lý dữ liệu không gian ........................................................61

3.5.3. Các thuật toán khai phá luật kết hợp không gian .......................................65

3.6. Đánh giá kết quả thử nghiệm .........................................................................67

KẾT LUẬN...............................................................................................................67

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

PHỤ LỤC..................................................................................................................73

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

v

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

CSDL Cơ sở dữ liệu

GKB Geographic Knowledge Base

OGC Open Gis Consortium

GIS Geographic information system

GeoARM Geographic Association Rule Miner

SQL Structured Query Language

JDBC Java Database Connectivity

ODBC Open Database Connectivity

GUI Graphical User Interface

ER Entity Relationship

OO Object Oriented

GPS Global Positioning System

Max-FGP Maximal Frequent Geographic Patterns

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

vi

DANH MỤC CÁC BẢNG

Bảng 1.1: Tập dữ liệu đã đƣợc tiền xử lý cho khai phá tập thƣờng xuyên và luật

kết hợp không gian................................................................................................. 22

Bảng 1.2: Các tập thƣờng xuyên có độ hỗ trợ 50% ............................................... 22

Bảng 1.3: Các tập thƣờng xuyên và các luật có các phụ thuộc.............................. 23

Bảng 1.4: Các tập thƣờng xuyên đóng................................................................... 24

Bảng 1.5:Các quan hệ topo theo ngữ cảnh của các đối tƣợng địa lý ..................... 24

Bảng 1.6: Các quan hệ topo khả năng sử dụng trong khai phá dữ liệu.................. 25

Bảng 1.7: Các tập thƣờng xuyên có độ hỗ trợ = 50%............................................ 27

Bảng 1.8: Các luật kết hợp tạo ra từ các tập thƣờng xuyên có kích thƣớc 2,3,4 có

chứa phụ thuộc ....................................................................................................... 28