...

ĐẠ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 Ngun - 2011

Số hóa bởi Trung tâm Học liệu – ĐHTN




ĐẠ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




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 hồ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 ln khuyến khích, động viên và
giúp đỡ tơi trong mọi hồ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 hồ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


Số hóa bởi Trung tâm Học liệu – ĐHTN




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 tồ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 hồn tồ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




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 tồ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 tồ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




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 tốn cắt tỉa dữ liệu khơng gian đầu vào ..............37
2.2.2. Đánh giá thuật tố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 tốn tạo tập thƣờng xun ................................................................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 xun đóng........................................48
2.3.2.2. Thuật tố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 tố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




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




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 xun có kích thƣớc 2,3,4 có
chứa phụ thuộc ....................................................................................................... 28

Số hóa bởi Trung tâm Học liệu – ĐHTN




vii

DANH MỤC CÁC HÌNH

Hình 1.1: Lƣu trữ dữ liệu địa lý trong các CSDL quan hệ........................................... 4
Hình 1.2: Quan hệ khơng gian tiềm ẩn ...............................................................................5
Hình 1.3: Quan hệ khơng gian có các phụ thuộc địa lý đã biết .......................................6
Hình 1.4: Các quan hệ khơng gian ............................................................................... 7
Hình 1.5: Một phần lƣợc đồ CSDL địa lý mức khái niệm và logic ............................. 9
Hình 1.6: Thể hiện của geo-ontology......................................................................... 11
Hình 1.7: Tập dữ liệu có 6 bộ và các tập thƣờng xuyên với minsup = 50% ............. 13
Hình 1.8: Tập dữ liệu có 6 bộ và các tập thƣờng xuyên đóng có minsup=50% ........ 15
Hình 1.9: Quan hệ khoảng cách trong thực tế và quan hệ giữa các điểm trung
tâm .............................................................................................................................. 19
Hình 1.10: Phân cấp khái niệm của nguồn nƣớc ....................................................... 29
Hình 1.11: a) Tập dữ liệu có nguồn nƣớc ở mức 2 và b) Các tập thƣờng xuyên với
minsup=30% ............................................................................................................. 31
Hình 1.12: a) Tập dữ liệu có nguồn nƣớc ở mức 3 và b) Các tập thƣờng xuyên với
minsup 30% ................................................................................................................ 33
Hình 2.1. Sơ đồ khai phá luật kết hợp khơng gian từ các CSDL địa lý ..................... 25
Hình 2.2: Giả mã của thuật tốn trích chọn các phụ thuộc từ lƣợc đồ CSDL ........... 36
Hình 2.3: Giả mã của thuật tốn tiền xử lý dữ liệu ................................................... 38

Hình 2.4. Tập dữ liệu có 6 bộ và các tập thƣờng xuyên với minsnup= 50%............. 40
Hình 2.5: Đồ thị thể hiện các tập thƣờng xuyên có phụ thuộc {D} (trái) và các
tập thƣờng xun khơng có phụ thuộc {D} (phải) ..................................................... 41
Hình 2.6: Thuật toán Apriori – KC tạo các tập thƣờng xun khơng có các phụ
thuộc đã biết ............................................................................................................... 43
Hình 2.7: Đồ thị thể hiện các tập thƣờng xuyên có phụ thuộc {A, W} (trái) và các
tập thƣờng xun khơng có phụ thuộc {A, W} (phải) ............................................... 46

Số hóa bởi Trung tâm Học liệu – ĐHTN




viii

Hình 2.8: Đồ thị thể hiện các tập thƣờng xuyên có phụ thuộc {D} và {A, W} (trái)
và các tập thƣờng xun khơng có phụ thuộc {D} và {A, W} (phải) ...................... 47
Hình 2.9: Các tập thƣờng xuyên và các tập thƣờng xun đóng ............................... 48
Hình 2.10: Đồ thị thể hiện các tập thƣờng xuyên đóng có các phụ thuộc đã biết
(trái) và các tập thƣờng xun đóng khơng có các phụ thuộc đã biết (phải) ............. 49
Hình 2.11: Đồ thị thể hiện các tập thƣờng xun khơng có phụ thuộc đã biết và các
tập thƣờng xuyên không dƣ thừa cực đại khơng có các phụ thuộc đã biết (phải) ..... 51
Hình 2.12: Giả mã của thuật tốn Max-FGP ............................................................. 52
Hình 3.1: Quá trình khai phá luật kết hợp từ CSDL địa lý của chƣơng trình
Weka-geo ................................................................................................................... 57
Hình 3.2: Một lƣợc đồ CSDL địa lý........................................................................... 58
Hình 3.3: Cấu trúc lƣu trữ dữ liệu dịa lý trong OGC ................................................. 61
Hình 3.4: Giao diện kết nối CSDL ............................................................................. 61
Hình 3.5: Giao diện tiền xử lý dữ liệu địa lý ............................................................. 62
Hình 3.6: Giao diện tạo các cặp phụ thuộc địa lý ...................................................... 63

Hình 3.7: Message khi khơng tìm thấy quan hệ khơng gian ...................................... 64
Hình 3.8: Message khi file .arff đã đƣợc tạo ra.......................................................... 65
Hình 3.9: Giao diện thẻ Association các thuật tốn khai phá luật kết hợp ................ 66
Hình 3.10: Giao diện xuất kết quả của thuật toán khai phá luật kết hợp khơng
gian ............................................................................................................................ 66

Số hóa bởi Trung tâm Học liệu – ĐHTN




1

MỞ ĐẦU

1. Đặt vấn đề
Những tiến bộ trong các công nghệ CSDL và các kỹ thuật thu thập dữ liệu
nhƣ đọc mã số mã vạch, viễn thám, ghi nhận thông tin từ các vệ tinh,… đã thu gom
đƣợc một lƣợng lớn dữ liệu trong các CSDL khổng lồ. Việc dữ liệu tăng lên một
cách dữ dội đòi hỏi phải đƣợc khai phá để trích chọn ra các tri thức hữa ích phục vụ
cho công tác chuyên môn. Chính điều này đã dẫn đến sự ra đời của một lĩnh vực
mới đầy hứa hẹn gọi là khai phá dữ liệu hay khai phá tri thức trong các CSDL. Khai
phá tri thức trong các CSDL có thể đƣợc định nghĩa là khai phá tri thức đáng quan
tâm, tiềm ẩn và chƣa biết trƣớc trong các CSDL lớn [21]. Khai phá dữ liệu là sự kết
hợp của một số lĩnh vực bao gồm học máy, các hệ thống CSDL, thể hiện dữ liệu,
thống kê và lý thuyết thơng tin.
Đã có nhiều nghiên cứu về khai phá dữ liệu trong các CSDL quan hệ và giao
dịch, nhƣng đối với các CSDL không gian vấn đề khai phá dữ liệu vẫn còn là những
thách thức cần đƣợc giải quyết.
Dữ liệu không gian là dữ liệu liên quan đến các đối tƣợng trong không gian.

Một CSDL không gian lƣu trữ các đối tƣợng không gian bao gồm các kiểu dữ liệu
không gian và các quan hệ không gian giữa các đối tƣợng. Dữ liệu không gian mang
thơng tin hình học và khoảng cách thƣờng đƣợc tổ chức theo các cấu trúc chỉ mục
không gian và truy cập bằng các phƣơng pháp truy cập khơng gian. Chính các đặc
trƣng khác biệt này của các CSDL không gian đã đặt ra nhiều trở ngại nhƣng cũng
mang đến nhiều cơ hội cho khai phá tri thức từ CSDL không gian. Khai phá dữ liệu
không gian hay khai phá tri thức trong CSDL khơng gian là trích trọn ra các tri thức
tiềm ẩn, các quan hệ không gian hay các mẫu chƣa rõ lƣu trữ trong các CSDL
không gian [21].

Số hóa bởi Trung tâm Học liệu – ĐHTN




2

Các nghiên cứu trƣớc đây về học máy, các hệ thống CSDL và thống kê đã
đặt nền móng cho nghiên cứu khai phá tri thức trong các CSDL. Và những tiến bộ
của các CSDL không gian nhƣ cấu trúc dữ liệu khơng gian, lập luận khơng gian,
tính tốn hình học,… đã mở đƣờng cho khai phá dữ liệu không gian. Trở ngại lớn
nhất trong khai phá dữ liệu không gian là hiệu quả của các thuật toán khai phá dữ
liệu không gian do lƣợng dữ liệu không gian khổng lồ, các kiểu dữ liệu không gian
và các phƣơng pháp truy cập không gian phức tạp.
Các phƣơng pháp khai phá dữ liệu khơng gian tập trung theo ba hƣớng chính
là khai phá luật kết hợp không gian, phân lớp không gian và phân cụm không gian.
Với mong muốn nghiên cứu về khai phá luật kết hợp không gian, luận văn đi sâu
tìm hiểu một lĩnh vực nhỏ trong khơng gian đó là không gian địa lý.
2. Mục tiêu của luận văn
Luận văn tập trung nghiên cứu về các kỹ thuật khai phá luật kết hợp không

gian trong CSDL địa lý nhằm trích rút ra các dữ liệu địa lý có ích tiềm ẩn bên trong
các kho tri thức địa lý khổng lồ. Cụ thể luận văn hƣớng vào các công việc:
-

Thu thập một số lớp dữ liệu bản đồ (bao gồm cả dữ liệu hình học và dữ
liệu thuộc tính) để thử nghiệm với thuật toán khai phá luật kết hợp khơng
gian.

-

Nghiên cứu một vài thuật tốn tiền xử lý dữ liệu phục vụ cho khai phá dữ
liệu không gian và một vài thuật toán khai phá luật kết hợp truyền thống
để mở rộng áp dụng trên dữ liệu địa lý.

-

Cài đặt chƣơng trình thử nghiệm thuật tốn lựa chọn nhằm khai phá luật
kết hợp với dữ liệu hình học và dữ liệu thuộc tính của một số lớp bản đồ.

3. Tóm tắt nội dung luận văn
Phần cịn lại của luận văn đƣợc tổ chức nhƣ sau:
Chƣơng 1: Tổng quan về dữ liệu không gian và khai phá luật kết hợp không
gian. Bao gồm các phần nhƣ: Giới thiệu khái quát về dữ liệu địa lý, luật kết hợp,

Số hóa bởi Trung tâm Học liệu – ĐHTN




3


luật kết hợp khơng gian, những vấn đề khó khăn trong khai phá luật kết hợp không
gian.
Chƣơng 2: Một số thuật tốn khai phá luật kết hợp khơng gian. Bao gồm:
các phƣơng pháp tiền xử lý dữ liệu không gian phục vụ khai phá dữ liệu và các
phƣơng pháp khai phá luật kết hợp không gian trên cả dữ liệu hình học và dữ liệu
thuộc tính.
Chƣơng 3: Cài đặt chương trình thử nghiệm. Bao gồm mơ tả bài tốn, xây
dựng dữ liệu thử nghiệm, thiết kế chƣơng trình, cài đặt thuật tốn và đánh giá kết
quả thử nghiệm.
Kết luận trình bày những nghiên cứu về khai phá luật kết hợp khơng gian,
những đóng góp của luận văn và những định hƣớng nghiên cứu sắp tới.

Số hóa bởi Trung tâm Học liệu – ĐHTN




4

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

Cơ sở dữ liệu địa lý
CSDL địa lý lƣu trữ các thực thể trong thế giới thực hay còn gọi là các đối

tƣợng địa lý thuộc một vùng nghiên cứu nào đó. Các đối tƣợng địa lý chứa cả các
thuộc tính khơng gian (tọa độ địa lý x,y) và các thuộc tính phi khơng gian (tên, dân
số,…). Đó là hai thành phần chính của dữ liệu không gian.

Dữ liệu địa lý của các đối tƣợng địa lý thƣờng đƣợc lƣu trữ trong các CSDL
quan hệ hoặc CSDL quan hệ đối tƣợng. Hình 1.1 thể hiện dữ liệu địa lý đƣợc lƣu
trữ trong CSDL quan hệ, trong đó các đối tƣợng địa lý nhƣ đƣờng, nguồn nƣớc và
siêu thị là các quan hệ khác nhau (các bảng CSDL), chúng có cả các thuộc tính
khơng gian (dữ liệu hình học) và các thuộc tính phi khơng gian (dữ liệu thuộc tính).
a) Duong
Gid Name

Shape

1

Trần Duy Hưng

Multiline[(x1,y1),(x2,y2),...]

2

Bưởi

Multiline[(x1,y1),(x2,y2),...]

b) NguonNuoc
Gid Name

Shape

1

Hồ Hồn Kiếm


Multiline[(x1,y1),(x2,y2),...]

2

Sông Tô Lịch

Multiline[(x1,y1),(x2,y2),...]

c) SieuThi
Gid Name

Shape

1

Big C Thăng Long Point[(x1,y1)]

2

Plaza Tràng Tiền

Point[(x1,y1)]

Hình 1.1: Lưu trữ dữ liệu địa lý trong các CSDL quan hệ
Ví dụ đặc trƣng khơng gian Siêu thị Big C Thăng Long có dữ liệu hình học
là điểm đƣợc biểu diễn trong CSDL là cặp tọa độ, dữ liệu thuộc tính có thể là số loại
mặt hàng kinh doanh, doanh thu hàng ngày... của cửa hàng.

Số hóa bởi Trung tâm Học liệu – ĐHTN





5

Ví dụ khác là đặc trƣng khơng gian đƣờng phố Trần Duy Hƣng (Hà Nội), có
dữ liệu hình học là tập các điểm để tạo nên đƣờng gấp khúc, dữ liệu thuộc tính có
thể là số làn xe, chiều dài của đƣờng phố...
Các thuộc tính khơng gian của các đối tƣợng địa lý (hình 1.1) có các quan hệ
khơng gian: gần (close), xa (far), chứa (contains), cắt (intersects). Do đó, các đối
tƣợng gần nhau trong thế giới thực thƣờng có ảnh hƣởng lẫn nhau hay phụ thuộc lẫn
nhau. Đây chính là đặc trƣng của dữ liệu địa lý trong khai phá dữ liệu và cũng là sự
khác biệt của việc khai phá dữ liệu không gian so với các phƣơng pháp khai phá dữ
liệu truyền thống.
Q trình trích chọn quan hệ không gian sẽ tạo ra rất nhiều kết hợp khơng
gian mà có thể đƣợc ngƣời sử dụng quan tâm hoặc khơng quan tâm. Hình 1.2 là ví
dụ về các quan hệ không gian tiềm ẩn giữa các siêu thị, các trạm ATM và các
đƣờng phố, khơng có một mối quan hệ rõ ràng nào giữa các dữ liệu này. Tuy nhiên,
trong thực tế những ngƣời đi mua hàng ở siêu thị hay tìm đến các các trạm ATM
gần đó để rút tiền nên việc trích chọn ra các quan hệ không gian giữa các trạm
ATM, các siêu thị và đƣờng sẽ đƣợc quan tâm trong quá trình khai phá dữ liệu. Nói
cách khác, chúng có sự phụ thuộc địa lý giữa các đối tƣợng khơng gian.

Hình 1.2: Quan hệ khơng gian tiềm ẩn

Số hóa bởi Trung tâm Học liệu – ĐHTN





6

Hình 1.3 là hai ví dụ về các quan hệ khơng gian trong đó thể hiện các phụ
thuộc địa lý đã biết. Hình 1.3 (trái) cho thấy cầu vƣợt ln cắt đƣờng cịn cầu ln
cắt các sơng, trong đó cả cầu vƣợt và cầu đều có cùng ngữ nghĩa là nối các đƣờng.
Hình 1.3 (phải) có một phụ thuộc địa lý đã biết là mỗi siêu thị đều nằm trên ít nhất
một đƣờng.

Hình 1.3: Quan hệ khơng gian có các phụ thuộc địa lý đã biết
Khác biệt chính giữa các ví dụ ở hình 1.2 và hình 1.3 là: hình 1.3 chứa các
quan hệ khơng gian đã biết. Ví dụ: is_a(Cau_vuot)intersects(Duong) hoặc
is_a(Sieu_thi)intersects(Duong). Cịn hình 1.2 chứa các quan hệ khơng gian tiềm
ẩn có thể đƣợc quan tâm trong q trình khai phá dữ liệu.
Các phụ thuộc địa lý đã biết là các quan hệ không gian bắt buộc thể hiện các
ràng buộc tồn vẹn khơng gian đƣợc sử dụng để đảm bảo sự thống nhất của dữ liệu.
Chúng thƣờng đƣợc thể hiện rõ trong các lƣợc đồ CSDL địa lý.
1.1.1. Quan hệ khơng gian và ràng buộc tồn vẹn khơng gian
Có ba kiểu quan hệ khơng gian chính là: quan hệ khoảng cách, quan hệ
hƣớng và quan hệ topo.
Quan hệ khoảng cách dựa trên khoảng cách Euclid giữa 2 đối tƣợng địa lý
(hình 1.4a). Đặt dist là hàm khoảng cách, operator là tốn tử thuộc tập {<, >,<=, >=,

Số hóa bởi Trung tâm Học liệu – ĐHTN




7


=}, d là một số thực, A và B là hai đối tƣợng địa lý. Khi đó khoảng cách giữa A và
B đƣợc biểu diễn bởi hàm dist(A,B) có giá trị là d.
Quan hệ hướng thể hiện vị trí của đối tƣợng này so với các đối tƣợng khác
trong quan hệ khơng gian (hình 1.4b).
Quan hệ topo có kiểu đặc trƣng điển hình là giao giữa hai đối tƣợng địa lý và
chúng bất biến trên các phép biến đổi hình học nhƣ quay và co giãn. Có nhiều
phƣơng pháp để xác định các quan hệ topo giữa các điểm, đƣờng, vùng. Hầu nhƣ,
chúng đều dựa trên mơ hình giao nhau nhƣ: bên trong và đƣờng bao hoặc bên trong,
bên ngoài và đƣờng bao [15]. Phép giao là sự phối hợp của các toán tử logic và(  )
và or(  ). Các mơ hình giao nhau xác định 8 quan hệ topo nhị phân là: cắt (crosses),
chứa (contains), trong (within), bao (covers), bao bở (-coveredBy), trùng (equals),
không nối (disjoint), chồng (overlaps) [28].
Quan hệ topo cũng có thể đƣợc xác định theo phƣơng pháp tích phân hoặc
phƣơng pháp mở rộng chiều. Các phƣơng pháp này xác định 6 quan hệ không gian
là: crosses, contains, within, equals, disjoint, overlaps (hình 1.4c).
Quan hệ topo mức cao là không nối (disjoint) và nối (connected). Khi các
đối tƣợng đƣợc nối với nhau thì chúng chỉ có các quan hệ là: crosses, contains,
within, covers, coveredBy, equals, overlaps.

Hình 1.4: Các quan hệ khơng gian
Quan hệ khơng gian giữa hai đối tƣợng địa lý có thể thuộc một trong các
dạng: khả năng (possible), bắt buộc (mandatory) và cấm (prohibited). Quan hệ khả

Số hóa bởi Trung tâm Học liệu – ĐHTN




8


năng là quan hệ có thể tồn tại hoặc khơng tồn tại trong CSDL (Ví dụ: đƣờng cắt
sơng, thành phố có các nhà máy). Quan hệ bắt buộc và quan hệ cấm thể hiện ràng
buộc tồn vẹn khơng gian trong CSDL nhất qn [p37.45].
Ràng buộc tồn vẹn khơng gian chứa các tính chất riêng của dữ liệu địa lý và
các quan hệ không gian để đảm bảo cũng nhƣ duy trì chất lƣợng và sự nhất quán
của các đối tƣợng địa lý trong CSDL địa lý. Ràng buộc toàn vẹn không gian giữa
hai đối tƣợng địa lý A và B có thể đƣợc xác định bởi các quan hệ thơng qua các
ràng buộc tốn học. Ví dụ, quan hệ bắt buộc giữa siêu thị và đƣờng có thể đƣợc thể
hiện bởi quan hệ 1-1 (một-một) hoặc 1-n (một-nhiều) có nghĩa là mỗi siêu thị phải
liên quan đến ít nhất một đƣờng. Quan hệ bắt buộc thể hiện phụ thuộc địa lý đã biết,
mà phụ thuộc địa lý đã biết lại tạo ra các mẫu đã biết, chúng không đƣợc quan tâm
trong khai phá luật kết hợp không gian.
1.1.2. Phụ thuộc địa lý
Trong không gian địa lý, ”mỗi đối tƣợng đều có quan hệ đến các đối tƣợng
khác nhƣng những đối tƣợng gần thì có quan hệ mật thiết hơn những đối tƣợng
xa”[p186, 29]. Tuy nhiên có một số đối tƣợng ln có quan hệ với các đối tƣợng
khác khơng phụ thuộc vào khoảng cách. Khi đó, chúng đƣợc gọi là một phụ thuộc
địa lý.
Định nghĩa 1 (Phụ thuộc địa lý): là quan hệ không gian bắt buộc giữa hai
đối tƣợng địa lý A và B, trong đó mỗi trƣờng hợp của A phải liên quan với ít nhất
một trƣờng hợp của B.
Phụ thuộc địa lý gọi là đã biết khi chúng đƣợc thể hiện rõ ràng trong lƣợc đồ
CSDL địa lý để đảm bảo sự tồn vẹn khơng gian của dữ liệu địa lý. Lƣợc đồ CSDL
địa lý là sự mở rộng của lƣợc đồ quan hệ thực thể (ER) hoặc lƣợc đồ hƣớng đối
tƣợng (OO) để xử lý các kiểu dữ liệu địa lý. Trong các lƣợc đồ CSDL địa lý, các
phụ thuộc địa lý là quan hệ không gian (Ví dụ: giáp, chứa) hoặc là quan hệ 1-1 hay
1-n giữa các bảng dữ liệu.

Số hóa bởi Trung tâm Học liệu – ĐHTN





9

Hình 1.5 là ví dụ thể hiện một phần của lƣợc đồ CSDL địa lý mức khái niệm
và một phần của lƣợc đồ mức logic tƣơng ứng cho CSDL quan hệ và CSDL hƣớng
đối tƣợng. Trong lƣợc đồ thể hiện các quan hệ bắt buộc (ví dụ: siêu thị và đƣờng,
đƣờng và thành phố, nguồn nƣớc và thành phố), còn các quan hệ khả năng không
thể hiện các phụ thuộc đã biết nhƣng có thể là đáng đƣợc quan tâm trong khai phá
tri thức thì khơng đƣợc thể hiện (ví dụ: siêu thị và nguồn nƣớc).
Ở mức logic quan hệ bắt buộc thể hiện bởi quan hệ 1-1 hoặc 1-n của các
khóa ngoại trong CSDL địa lý quan hệ hoặc thể hiện bởi con trỏ trỏ tới các lớp
trong CSDL địa lý hƣớng đối tƣợng.

Một phần của lược đồ ER
Creat Table Duong
(duongid integer,
ten varchar(30),
geometry integer,
Primary Key (duongid))
Creat Table SieuThi
(sieuthiid integer,
ten varchar(30),
diachi varchar(30),
geometry integer,
Primary Key (sieuthiid)
Foriegn Key (duongid) reference Duong)

Một phần của lược đồ OO

Public class Duong{
private varchar(30) ten;
private integer geometry;
public Duong() { }
}
Public class SieuThi{
private varchar(30) tene;
private varchar(30) diachi;
private integer geometry;
Duong Duong
public SieuThi() { }
}

Hình 1.5: Một phần lược đồ CSDL địa lý mức khái niệm và logic

Số hóa bởi Trung tâm Học liệu – ĐHTN




10

1.1.3. Geo-Ontology và ràng buộc tồn vẹn khơng gian
Năm 1993, Gruber [24] đƣa ra một định nghĩa về ontology: “Một ontology là
một đặc tả rõ ràng, mang tính hình thức của một khái niệm có thể chia sẻ”. Định
nghĩa của Gruber về ontology là một định nghĩa chung của ontology, ontology có
thể đƣợc định nghĩa theo những ngữ cảnh cụ thể và có những đặc điểm sau:
 Các ontology đƣợc dùng để miêu tả một miền xác định.
 Các thuật ngữ và các quan hệ của các thuật ngữ đƣợc miêu tả rõ ràng
trong miền dữ liệu đó.

 Tồn tại một cơ chế để tổ chức các thuật ngữ (ví dụ cấu trúc phân cấp).
 Có sự thống nhất giữa những ngƣời dùng về ý nghĩa của các thuật ngữ
đƣợc sử dụng trong miền.
Gần đây, khái niệm ontology đã đƣợc sử dụng nhiều trong các lĩnh vực khác
nhau nhƣ: khoa học máy tính, trí tuệ nhân tạo, CSDL, mơ hình khái niệm,... Do đó,
có nhiều ontology đƣợc đƣa ra và cũng nhiều mơ hình, ngơn ngữ, cơng cụ đƣợc
phát triển. Chaves đã định nghĩa đƣợc một geo-ontology cho quản trị dữ liệu của
nƣớc Bồ Đào Nha và một siêu mô hình (meta-model) tên là GKB, đây chính là
điểm khởi đầu cho việc định nghĩa một ontology cho dữ liệu địa lý [14].
Trong geo-ontology, các ràng buộc tồn vẹn khơng gian đƣợc thể hiện bởi
các thuộc tính của dữ liệu địa lý. Chúng đƣợc xem nhƣ là các thuộc tính giới hạn và
đƣợc xác định nhƣ một quan hệ không gian và phi không gian với các ràng buộc
nhỏ nhất và lớn nhất tƣơng ứng,... Ví dụ: khái niệm đảo là một khu đất có nƣớc bao
quanh, có quan hệ 1-1 với khái niệm nước.
Hình 1.6 là ví dụ của một geo-ontology định nghĩa về các quan hệ topo khác
nhau để minh họa xem các ràng buộc ngữ nghĩa bắt buộc đƣợc thể hiện nhƣ thế nào.
Trong ví dụ ở hình 1.6 bus stop (trạm xe buýt) và gas station (trạm xăng) có
một ràng buộc bắt buộc với road (đƣờng) vì mỗi trạm xe buýt và mỗi trạm xăng
phải nằm trên (touch) ít nhất một đường nào đó. Tuy nhiên, đường khơng nhất thiết
Số hóa bởi Trung tâm Học liệu – ĐHTN




11

phải có trạm xe buýt hay trạm xăng. Sự kết hợp một chiều thể hiện quan hệ bắt buộc
mà các trạm xe buýt và trạm xăng phải có với đường.
Để đánh giá số lƣợng các phụ thuộc đã biết trong các geo-ontology, chúng ta
phân tích geo-ontology đầu tiên của Bồ Đào Nha tên là geo-net-pt01 [14]. Mặc dù,

không phải tất cả các thành phần của miền địa lý đƣợc định nghĩa trong geo-netpt01 nhƣng ở đây cũng có nhiều phụ thuộc 1-1 và 1-n.
Kho geo-ontology lƣu trữ tại 3 mức thông tin: mức quản trị (geoadministrative), mức vật lý (geo-physical) và mức mạng (network). Mức quản trị
lƣu trữ thông tin quản trị về phân chia phạm vi và gồm các đối tƣợng địa lý nhƣ các
đô thị (municipality), các đƣờng (road),... Mức vật lý lƣu trữ các đối tƣợng nhƣ các
lục địa (continent), các đại dƣơng (ocean), các hồ (lake), các vịnh (bay),... Mức
mạng lƣu trữ các dữ liệu phi không gian và các quan hệ của tầng quản trị nhƣ dân số
của một thành phố.
Geo-net-pt01 có 58 đối tƣợng địa lý và 55 quan hệ 1-1.

Hình 1.6: Thể hiện của geo-ontology
1.2.

Luật kết hợp
Luật kết hợp là một biểu thức có dạng: XY, trong đó X và Y là tập các

mục cùng xuất hiện trong một bộ cho trƣớc [3].

Số hóa bởi Trung tâm Học liệu – ĐHTN




12

Bài tốn luật kết hợp thơng thƣờng đƣợc đặc tả hình thức nhƣ sau:
-

Cho một tập mục F = {f1, f2,..., fk,…, fn} và bộ dữ liệu  là tập các dịng
(cịn gọi là các giao tác) W, trong đó W là một tập mục (bộ) và thỏa mãn
W  F; W là một véc tơ nhị phân mà phần tử w[k]=1 nếu W chứa thuộc

tính fk và w[k]=0 trong trƣờng hợp ngƣợc lại.

-

Trong mỗi giao tác sẽ có đúng một dòng trong tập dữ liệu đƣợc khai phá.
Xét X là một tập của F, W chứa X nếu với  fk  X đều có w[k]=1. Tƣơng
tự Y là một tập của F, W chứa Y nếu với  fk  Y đều có w[k]=1.

-

Luật kết hợp là một biểu thức có dạng XY, trong đó X, Y  F; X, Y≠ Ø
và X  Y=Ø.

-

Độ hỗ trợ (support) s của một tập mục X là phần trăm số dòng X xuất
hiện nhƣ là một tập con so với số dòng của tập mục. Độ hỗ trợ của luật
XY đƣợc ký hiệu là s(X  Y).

-

Luật XY thỏa mãn tập  với độ tin cậy 0  c  1 nếu có ít nhất c% các
trƣờng hợp của 

thỏa mãn cả X và Y, đƣợc ký hiệu là

c(XY)=s(X  Y)/s(X).
Bài toán khai phá luật kết hợp đƣợc thực hiện qua hai bƣớc [3]:
-


Bước 1 Tìm tất cả các tập mục thường xuyên: một tập mục là thƣờng
xuyên nếu độ hỗ trợ của nó lớn hơn hoặc bằng một ngƣỡng nào đó gọi là
minsup.

-

Bước 2 Tạo luật mạnh (luật có độ tin cậy cao): luật là mạnh nếu độ hỗ
trợ của nó lớn hơn hoặc bằng độ hỗ trợ nhỏ nhất minsup và độ tin cậy của
nó thì lớn hơn hoặc bằng một ngƣỡng nào đó gọi là minconf.

Nếu tập thuộc tính Z là tập thƣờng xun thì tất cả các tập con của nó đều là
tập thƣờng xuyên. Nếu tập thuộc tính Z khơng phải là tập thƣờng xun thì tất cả
các tập chứa nó cũng khơng phải là tập thƣờng xuyên. Nếu tập Z thỏa mãn ràng

Số hóa bởi Trung tâm Học liệu – ĐHTN




13

buộc về độ hỗ trợ thì tất cả các luật đƣợc tạo ra từ tập Z cũng thỏa mãn ràng buộc về
độ hỗ trợ [3].
Thuật toán khai phá luật kết hợp Apriori tạo ra các tập ứng viên và sau đó
tính mức độ thƣờng xun của chúng để tạo ra các tập thƣờng xuyên. Việc tạo ra
các tập ứng viên đƣợc thực hiện bằng cách duyệt đa cấp trên tập dữ liệu.
Đầu tiên, tính độ hỗ trợ của các phần tử riêng lẻ để xác định các tập thƣờng
xuyên (gọi là tập mục k thƣờng xuyên). Các bƣớc con, nhóm các tập thƣờng xuyên
Lk-1 vào các tập Ck có k phần tử. Tính độ hỗ trợ của từng tập ứng viên, nếu độ hỗ trợ
lớn hơn hoặc bằng minsup thì tập đó đƣợc coi là tập thƣờng xuyên. Lặp lại quá trình

trên cho đến khi tập thƣờng xuyên trong kết quả của bƣớc duyệt là tập rỗng,... Các
luật kết hợp đƣợc tạo ra từ các tập thƣờng xuyên kết quả đạt minsup.
a) Tập dữ liệu
Tid itemset

b) Các tập thƣờng xuyên với minsup = 50%
k

Các tập thƣờng xuyên

1

A, C, D, T, W

1

{A}, {C}, {D}, {T}, {W}

2

C, D, W

2

3

A, D, T, W

{A,C}, {A,D}, {A,T}, {A,W}, {C,D},
{C,T}, {C,W}, {D,T}, {D,W}, {T,W}


4

A, C, D, W

3

{A,C,D}, {A,C,W}, {A,D,T}, {A,D,W},
{A,T,W}, {C,D,T}, {C,D,W}, {D,T,W}

5

A, C, D, T, W

4

{A,C,D,T}, {A,D,T,W}

6

C, D, T
Hình 1.7: Tập dữ liệu có 6 bộ và các tập thường xuyên với minsup = 50%
Đã có nhiều thuật tốn áp dụng cho dữ liệu phi khơng gian đƣợc đƣa ra nhằm

giảm thiểu thời gian tính toán, số lƣợng các tập thƣờng xuyên và các luật kết hợp.
Các thuật toán giảm thiểu cả số lƣợng các tập thƣờng xuyên và các luật kết hợp
đƣợc phân làm hai loại: các thuật toán Apriori-like tạo ra các tập thƣờng xuyên và
sử dụng các độ đo khác nhau để giảm thiểu các luật kết hợp; và các thuật toán tạo
các tập thƣờng xuyên đóng nhằm giảm thiểu các tập thƣờng xuyên và các luật dƣ
thừa.


Số hóa bởi Trung tâm Học liệu – ĐHTN




14

Các thuật toán Apriori-like đều tập trung vào các luật đáng quan tâm. Một số
đại lƣợng đã đƣợc đƣa ra sử dụng nhƣ độ hỗ trợ, độ tin cậy, entropy gain, gini, độ
cải tiến, độ chắc chắn,... Tuy nhiên, theo Bayardo khó có thể có đƣợc một đại lƣợng
đơn giản để xác định mức độ đáng quan tâm hay mức độ tốt của một luật kết hợp
[6]. Trong hầu hết các thuật tốn này, các luật khơng đáng quan tâm thƣờng bị khử
trong quá trình tạo luật – bƣớc cuối cùng trong khai phá dữ liệu.
Các ngƣỡng và các ràng buộc khác nhau đã đƣợc áp dụng, chỉ có các luật
thỏa mãn các ràng buộc đó mới đƣợc tạo ra. Các phƣơng pháp xem xét độ mong đợi
và tin cậy yêu cầu xác định các thông tin đáng tin cậy phức tạp nhƣ các khả năng
phụ thuộc vào điều kiện cụ thể mà trong thực tế chúng khó có thể đạt đƣợc [23].
Srikant đã sử dụng phân cấp khái niệm để khử các tập ứng viên chứa mức cha (ví
dụ: cloth) và mức con (ví dụ: jacket, dress) của một phân cấp trong cùng một tập
[30]. Trong thực tế khai phá dữ liệu ở các mức khác nhau trong một q trình khai
phá khơng phải là phổ biến. Phƣơng pháp này giảm thiểu các luật nên tránh trong
quá trình tiền xử lý dữ liệu, ví dụ: jacket=yesclothes=yes. Vì vậy, khơng nên xét
đồng thời các loại dữ liệu này trong cùng một quá trình khai phá.
Định nghĩa 2 (tập thƣờng xuyên đóng): tập thƣờng xuyên L là tập thƣờng
xuyên đóng nếu  (L)=L [28].
Trong đó,  (L) là tập cực đại trong tất cả các tập ở giao tác có chứa tập
thƣờng xuyên L. Toán tử  cho phép xác định tất cả các tập thƣờng xuyên đóng
(các tập thƣờng xuyên không dƣ thừa nhỏ nhất). Mà các tập thƣờng xuyên khơng
đóng lại có cùng độ hỗ trợ với tập thƣờng xuyên đóng tƣơng ứng của nó nên tập

thƣờng xuyên cực đại là tập thƣờng xun đóng. Tính chất này đảm bảo không bị
mất mát thông tin và các luật đƣợc tạo ra từ các tập thƣờng xun khơng đóng sẽ là
dƣ thừa so với các luật đƣợc tạo ra từ các tập thƣờng xuyên đóng tƣơng ứng.
Các phƣơng pháp tạo các tập thƣờng xun đóng thực hiện tìm các tập
thƣờng xuyên sau đó loại bỏ đi các tập thƣờng xuyên khơng phải là đóng. Để hiểu
đƣợc khái niệm tập thƣờng xun đóng chúng ta xét ví dụ ở hình 1.8.

Số hóa bởi Trung tâm Học liệu – ĐHTN




15

Tập {A,D,W} là tập thƣờng xun vì nó đạt đƣợc minsup=50%. Nó cũng là
tập thƣờng xun đóng vì trong tập giao tác (1345) khơng có tập nào lớn hơn tập
{A,D,W} (lớn hơn theo nghĩa số lƣợng các phần tử) đạt đƣợc minsup. Tập thƣờng
xuyên {A,D,T} xuất hiện trong giao tác (135), nhƣng trong cùng giao tác này tập
thƣờng xuyên {A,D,T,W} cũng đƣợc tạo ra. Trong trƣờng hợp này
tidset(A,D,T)=135, tidset(A,D,T,W)=135 và (A,D,T)  (A,D,T,W) nên tập thƣờng
xuyên {A,D,T} không phải là đóng.
a) Tập dữ liệu
Tid itemset

b) Các tập thƣờng xuyên đóng
k

Các tập thƣờng xuyên đóng

1


A, C, D, T, W

1

{D}

2

C, D, W

2

{C,D}, {D,T}, {D,W}

3

A, D, T, W

3

{A,D,W}, {C,D,T}, {C,D,W}

4

A, C, D, W

4

{A,C,D,T}, {A,D,T,W}


5

A, C, D, T, W

6

C, D, T

c) Các tập thƣờng xuyên trong cùng một giao tác
TidSet

Tập phổ biến L

123456 {D}
12456

{C}, {C,D}

12345

{W}, {D,W}

1245

{C,W}, {C,D,W}

1345

{A}, {A,D}, {A,W}, {A,D,W}


1356

{T}, {D,T}

145

{A,C}, {A,C,W}, {A,C,D}, {A,C,D,W}

135

{T,W}, {A,T}, {A,D,T}, {D,T,W}, {A,D,T,W}

156

{C,T}, {C,D,T}

Hình 1.8: Tập dữ liệu có 6 bộ và các tập thường xuyên đóng có minsup=50%

Số hóa bởi Trung tâm Học liệu – ĐHTN