BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
-------------
LƢƠNG VĂN NGHĨA
THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN
THEO TIẾP CẬN KHAI PHÁ DỮ LIỆU
LUẬN ÁN TIẾN SĨ KỸ THUẬT
ĐÀ NẴNG – 2019
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
-------------
LƢƠNG VĂN NGHĨA
THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN
THEO TIẾP CẬN KHAI PHÁ DỮ LIỆU
Chuyên ngành: KHOA HỌC MÁY TÍNH
M :
LUẬN ÁN TIẾN SĨ KỸ THUẬT
Ngƣời hƣớng dẫn khoa học:
. PGS.TS. Lê Văn Sơn
. PGS.TS. Đoàn Văn Ban
ĐÀ NẴNG – 2019
i
LỜI CAM ĐOAN
Tôi xin cam đoan Luận án "Thiết kế cơ sở dữ liệu phân tán theo tiếp cận
khai phá dữ liệu” là công trình nghiên cứu do tôi thực hiện, dưới sự hướng dẫn
của PGS.TS. Lê Văn Sơn và PGS.TS. Đoàn Văn Ban.
Tôi cam đoan các kết quả nghiên cứu được trình bày trong luận án là
trung thực và không sao chép từ bất kỳ luận án nào khác. Một số kết quả nghiên
cứu là thành quả tập thể và đã được các đồng tác giả đồng ý cho sử dụng. Mọi
trích dẫn đều có ghi nguồn gốc xuất xứ rõ ràng và đầy đủ.
Tác giả
Lƣơng Văn Nghĩa
.
ii
MỤC LỤC
LỜI CAM ĐOAN ..................................................................................................................... i
MỤC LỤC ................................................................................................................................. ii
DANH MỤC CÁC CỤM TỪ VIẾT TẮT .......................................................................... v
DANH MỤC THUẬT NGỮ ANH - VIỆT ........................................................................ vi
DANH MỤC CÁC BẢNG ................................................................................................. viii
DANH MỤC CÁC HÌNH ..................................................................................................... ix
MỞ ĐẦU.................................................................................................................................... 1
Chƣơng 1. THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN .................................................. 6
1.1. TỔNG QUAN VỀ HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN ...................................... 6
1.1.1. Các đặc điểm cơ bản của hệ cơ sở dữ liệu phân tán ................................ 7
1.1.2. Các mục tiêu của hệ cơ sở dữ liệu phân tán ............................................. 8
1.1.3. Kiến trúc của hệ cơ sở dữ liệu phân tán ................................................. 10
1.1.4. Các mô hình hệ cơ sở dữ liệu phân tán .................................................. 11
1.2. THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN ....................................................... 12
1.2.1. Các chiến lƣợc thiết kế ........................................................................... 12
1.2.2. Các vấn đề thiết kế cơ sở dữ liệu phân tán............................................. 14
1.2.3. Kỹ thuật thiết kế cơ sở dữ liệu phân tán ................................................ 16
1.2.4. Các quy tắc phân mảnh đúng đắn .......................................................... 18
1.2.5. Thảo luận về thiết kế cơ sở dữ liệu phân tán ......................................... 18
1.3. THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN BẰNG CÁC KỸ THUẬT
PHÂN MẢNH .......................................................................................................... 19
1.3.1. Kỹ thuật phân mảnh ngang .................................................................... 20
1.3.2. Kỹ thuật phân mảnh dọc ........................................................................ 25
1.3.3. Thuật toán phân mảnh FC ...................................................................... 29
1.3.4. Kỹ thuật phân mảnh hỗn hợp ................................................................ 33
1.3.5. Thảo luận các kỹ thuật phân mảnh......................................................... 34
1.4. KẾT CHƢƠNG ................................................................................................. 36
Chƣơng 2. PHÂN CỤM DỮ LIỆU TRONG THIẾT KẾ CƠ SỞ DỮ LIỆU
PHÂN TÁN ............................................................................................................................. 38
iii
2.1. TIẾP CẬN KHAI PHÁ DỮ LIỆU .................................................................... 38
2.1.1. Khai phá tri thức và khai phá dữ liệu ..................................................... 38
2.1.2. Những thách thức trong khai phá dữ liệu ............................................... 40
2.1.3. Các bài toán khai phá dữ liệu ................................................................. 41
2.2. KỸ THUẬT PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU ............................. 42
2.2.1. Kỹ thuật phân cụm ................................................................................. 42
2.2.2. Các kiểu dữ liệu và độ đo trong phân cụm ............................................ 44
2.2.3. Một số phƣơng pháp phân cụm dữ liệu ................................................. 48
2.2.4. Thảo luận về các kỹ thuật phân cụm ...................................................... 58
2.3. PHÂN MẢNH DỮ LIỆU DỰA VÀO KỸ THUẬT PHÂN CỤM ................... 59
2.3.1. Đề xuất cải tiến thuật toán phân mảnh dọc VFC ................................... 60
2.3.2. Đề xuất cải tiến thuật toán phân mảnh ngang HFC ............................... 61
2.3.3. Đánh giá kết quả thực nghiệm ............................................................... 64
2.4. KẾT CHƢƠNG ................................................................................................. 70
Chƣơng 3. THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN THEO PHÂN CỤM THÔ
VÀ TỐI ƢU ĐÀN KIẾN ...................................................................................................... 72
3.1. THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN THEO TIẾP CẬN TẬP THÔ ...... 72
3.1.1 Rời rạc hoá dữ liệu và trích chọn thuộc tính theo tiếp cận tập thô ......... 73
3.1.2. Hệ thông tin ............................................................................................ 74
3.1.3. Quan hệ không phân biệt, bất khả phân biệt trong hệ thông tin ............ 74
3.1.4. Thuộc tính và vector đặc trƣng tham chiếu ............................................ 75
3.2. PHÂN CỤM DỮ LIỆU PHÂN TÁN THEO TIẾP CẬN TẬP THÔ ............... 76
3.2.1. Thuật toán phân cụm thô KR (K-Means Rough) ................................... 76
3.2.2. Kết quả thực nghiệm thuật toán phân cụm thô KR ............................... 80
3.3. THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN THEO PHƢƠNG PHÁP TỐI
ƢU ĐÀN KIẾN ........................................................................................................ 83
3.3.1. Phƣơng pháp tối ƣu hóa đàn kiến .......................................................... 83
3.3.2. Từ đàn kiến tự nhiên đến đàn kiến nhân tạo .......................................... 83
3.3.3. Thuật toán ACO tổng quát ..................................................................... 84
3.3.4. Thuật toán hệ kiến AS ............................................................................ 85