Thiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệuThiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệu
Trang 1BỘ 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
Trang 2BỘ 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
Trang 3LỜ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
Trang 4MỤ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
Trang 52.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
Trang 63.3.5 Tổ chức dữ liệu và các khái niệm độ đo 87
3.4 PHÂN CỤM DỮ LIỆU PHÂN TÁN THEO TIẾP CẬN TỐI ƯU ĐÀN KIẾN 89
3.4.1 Phân cụm dữ liệu phân tán theo tiếp cận ACO 89
3.4.2 Đề xuất các thuật toán phân mảnh dọc theo phân cụm đàn kiến 90
3.4.3 Kết quả thực nghiệm thuật toán đề xuất VFAC 95
3.5 KẾT CHƯƠNG 99
KẾT LUẬN 101 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ
TÀI LIỆU THAM KHẢO
Trang 7vDANH MỤC CÁC CỤM TỪ VIẾT TẮT
TT Từ viết tắt Tiếng Anh Tiếng Việt
1 ACO Ant Colony Optimization Tối ưu hóa đàn kiến
3 BA Bottom Attributes Thuộc tính đáy
4 BEA Bond energy algorithm Thuật toán năng lượng nối
5 CA Clustered Affintity Ái lực tụ thuộc tính
11 KO Knowledge-Oriented Hướng tri thức
12 KPDL Data Mining Khai phá dữ liệu
13 OCM Object-Condition Matrix Ma trận đối tượng-điều kiện
14 OFN Optimization Fragmentation
Number
Số mảnh tối ưu
15 RST Rough Set Theory Lý thuyết tập thô
16 TA Top Attributes Thuộc tính đỉnh
17 TSP Travelling Salesman
Problem
Bài toán người chào hàng
18 VFAC Vertical Fragmentation Ants
Trang 8DANH MỤC THUẬT NGỮ ANH - VIỆT
TT Thuật ngữ tiếng Anh Thuật ngữ tiếng Việt
1 Access frequency Tần số truy xuất
2 Affinity Ái lực quan hệ
4 Analysis & decision support Phân tích và hỗ trợ ra quyết định
5 Association rules Luật kết hợp
6 Attribute affinity Ái lực thuộc tính
7 Attribute affinity matrix Ma trận ái lực thuộc tính
9 Border object Đối tượng biên
10 Bottom-up approach Tiếp cận từ dưới lên
11 Cardinality Lực lượng
12 Classification & prediction Phân lớp và dự đoán
13 Cluster Affintity Matrix Ma trận ái lực cụm thuộc tính (CA)
15 Concept description Mô tả khái niệm
16 Conceptual design Thiết kế khái niệm
17 Contribution Đóng góp
18 Core object Đối tượng lõi
19 Database machine Máy CSDL
20 Dense region Vùng dày đặc
21 Density based cluster Cụm dựa trên mật độ
22 Distributed processing Xử lý phân tán
23 Distribution transparency Trong suốt phân tán
25 Fragmentation Phân mảnh
26 Fragmentation Transparency Trong suốt phân mảnh
Trang 927 Global affinity measure Số đo ái lực chung AM
28 Hetorogeneous DDBS Hệ CSDL phân tán không thuần nhất
29 Homogeneous DDBS Hệ CSDL phân tán thuần nhất
30 Horizontal Fragmentation Phân mảnh ngang
31 Hybrid Fragmentation Phân mảnh hỗn hợp
32 Minterm fragment Mảnh hội sơ cấp
33 Minterm predicate Vị từ hội sơ cấp
34 Minterm selectivity Độ tuyển hội sơ cấp
35 Net contribution Đóng góp thực
36 Noise object Đối tƣợng nhiễu
37 Outlier Phần tử ngoại lệ
39 Replication transparency Trong suốt nhân bản
41 Simple predicate Vị từ đơn
42 Top-down approach Tiếp cận từ trên xuống
43 Vertical fragmentation Phân mảnh dọc
44 View design Thiết kế khung nhìn
Trang 10viii DANH MỤC CÁC BẢNG
Bảng 1.1 Ma trận giá trị sử dụng thuộc tính 27
Bảng 1.2 Ma trận ái lực thuộc tính AA 27
Bảng 2.1 Bảng sự kiện cho biến nhị phân [I] 46
Bảng 2.2 Ma trận khoảng cách đối tượng 50
Bảng 2.3 Ma trận khoảng cách các cụm sau gom cụm bước 3 51
Bảng 2.4 Khoảng cách giữa các cụm sau khi gom cụm bước 3 51
Bảng 2.5 Khoảng cách giữa các cụm sau 4 lần gom cụm 51
Bảng 2.6 Vector hóa các bản ghi 62
Bảng 2.7 Ma trận OCM 62
Bảng 2.8 Bảng biểu diễn 6 đối tượng (p 1 , p 2 , p 6 ) 64
Bảng 2.9 Khoảng cách Euclide giữa 6 đối tượng 65
Bảng 2.10 Tập D gồm 20 đối tượng cần phân cụm 67
Bảng 2.11 So sánh kết quả với phân cụm k-Means và VFC 68
Bảng 2.12 Kết quả phân mảnh ngang cải tiến HFC 69
Bảng 2.13 Kết quả phân mảnh ngang theo k-Medoids 70
Bảng 3.1 Tập D gồm 20 đối tượng cần phân cụm 81
Bảng 3.2 So sánh kết quả phân cụm thô KR và k-Means 82
Bảng 3.3 Bảng tham số 87
Bảng 3.4 Tập dữ liệu D gồm 20 giao tác 96
Bảng 3.5 So sánh kết quả với phân cụm k-Means với VFAC 98
Trang 11DANH MỤC CÁC HÌNH
Hình 1.1 Minh họa mô hình hệ CSDL phân tán 7
Hình 1.2 Mô hình kiến trúc hệ cơ sở dữ liệu phân tán 11
Hình 1.3 Ma trận định vị điểm tách Top_A và Bot_A 30
Hình 1.4 Sơ đồ cây phân mảnh hỗn hợp 34
Hình 2.1 Quá trình khám phá tri thức 39
Hình 2.2 Khoảng cách ngắn nhất giữa hai cụm 48
Hình 2.3 Khoảng cách lớn nhất giữa hai cụm 48
Hình 2.4 Khoảng cách trung bình giữa hai cụm 48
Hình 2.5 Kết quả cây phân cụm phân cấp tích tụ 52
Hình 2.6 Tập các đối tượng p cần phân cụm 64
Hình 2.7 Kết quả phân cụm theo khoảng cách ngắn nhất 65
Hình 2.8 Kết quả phân cụm theo khoảng cách lớn nhất 66
Hình 2.9 Kết quả phân cụm theo thuật toán k-Means (k = 3) 67
Hình 2.10 K ết quả phân cụm theo thuật toán k-Means (k = 15) 68
Hình 2.11 Kết quả phân cụm theo thuật toán VFC (số cụm k = 3) 68
Hình 3.1 Minh họa gom cụm vào bộ các xấp xỉ dưới và xấp xỉ trên 77
Hình 3.2 Kết quả phân cụm theo thuật toán k-Means (k = 6) 80
Hình 3.3 Kết quả phân cụm theo thuật toán k-Means (k = 15) 81
Hình 3.4 Kết quả phân cụm thô KR (k = 6) 81
Hình 3.5 Kết quả phân cụm theo thuật toán k-Means (k = 10) 96
Hình 3.6 Kết quả phân cụm thuật toán VFAC (k = 10) 97
Trang 12Hình 3.7 Kết quả phân cụm với thuật toán VFAC (k = 3) 97
Hình 3.8 So sánh chi phí trung bình lỗi trên k-Means và VFAC 98
Hình 3.9 Đánh giá độ ổn định theo số cụm trên k-Means và VFAC 99
Trang 13MỞ ĐẦU
1 TÍNH CẤP THIẾT CỦA VIỆC NGHIÊN CỨU
Ngày nay, với việc dữ liệu đa dạng, được phân tán ở nhiều nơi trên toàn cầu làm cho các ứng dụng cơ sở dữ liệu (CSDL), các phương pháp quản trị và khai thác CSDL phân tán truyền thống tỏ ra ít hiệu quả, không đáp ứng đượcnhiều mục tiêu chia sẻ và còn khó khăn trong việc tích hợp và trao đổi thông tin
Để khắc phục được những hạn chế trên, các CSDL phân tán phải được thiết kế sao cho phù hợp hơn với yêu cầu sử dụng, truy xuất và xử lý dữ liệu phân tán Điều này có thể thực hiện được nhờ vào các kỹ thuật khai phá dữ liệu (KPDL),
cụ thể là dựa vào các kỹ thuật phân cụm phục vụ cho việc phân mảnh và phân tán, định vị dữ liệu khi thiết kế một CSDL phân tán [80]
Hiện có nhiều nghiên cứu liên quan đến bài toán thiết kế CSDL phân tán dựa vào các kỹ thuật phân cụm trong lĩnh vực khai phá dữ liệu, cụ thể như:
- Bài toán phân mảnh dữ liệu dựa vào phân cụm được quan tâm trong [18], sau đó được phát triển tiếp theo bởi Özsu M Tamer, Patrick Valduriez [58] Tuy nhiên, các kỹ thuật phân mảnh các đối tượng được phân cụm dựa vào
độ tương đồng nhóm thuộc tính chỉ dừng lại cho bài toán phân mảnh dọc trên các lược đồ quan hệ
- Hui Ma và các cộng sự đề xuất thuật toán phân cụm CA (Clustered
Affinity) dựa trên sự liên kết giữa các thuộc tính [48], sau đó Navathe và các
cộng sự phát triển thành thuật toán BEA (Bond Enegy Algorithm) phục vụ cho
bài toán phân mảnh dọc dữ liệu phân tán [58] Các thuật toán trên dựa theo ý tưởng các thuộc tính có tần suất xuất hiện đồng thời càng lớn thì thường thuộc về một cụm (phân mảnh) Phương án giải quyết bài toán này đưa về tối ưu hóa một biểu thức bậc 2 có độ phức tạp khá lớn Navathe và các cộng sự đề xuất tìm điểm
phân tách t sao cho biểu thức q = CTQ * CBQ - COQ2
[58] là cực đại Tuy nhiên, với các quan hệ có số thuộc tính hay số đối tượng lớn, bài toán không thể
Trang 14sự nhất trí chung của các nhà khoa học [47].
- Thuật toán tối ưu đàn kiến heuristic - ACO (Ant Colony Optimazation)
lần đầu tiên Dorigo và các cộng sự đề xuất năm 2011 [23] được ứng dụng nhiều
trong tìm kiếm và khai phá dữ liệu Hầu hết các nghiên cứu gần đây về ACO chỉ
tập trung vào việc phát triển các biến thể của thuật toán để làm tăng hiệu năng
tính toán của thuật toán hệ kiến AS (Ant System) ban đầu.
- Các nghiên cứu trong nước về ACO tập trung giải quyết các bài toán
tối ưu rời rạc như bài toán người bán hàng, bài toán lập lịch, bài toán an ninh
mạng [1] Một số hướng tiếp cận khác theo kỹ thuật phân cụm mờ [7, 13] cũng đang tập trung giải quyết cho một số bài toán thuộc lĩnh vực kỹ thuật, công nghệcao [25] Tuy nhiên, các cách tiếp cận và thử nghiệm cho loại bài toán phân cụmnày thường hay sử dụng các kỹ thuật tìm kiếm heuristic để tìm lời giải tối ưu cục
bộ cho các bài toán phân mảnh dữ liệu phân tán, tuy cho các kết quả tương đối nhanh nhưng không thể cải thiện thêm lời giải tìm được [37, 51]
- Về kỹ thuật phân cụm tích hợp, các nghiên cứu trong nước gần đây
được nhiều nhóm tác giả quan tâm và đã đề xuất các thuật toán hiệu năng cao Trong luận án này, tác giả đã vận dụng tích hợp giữa thuật toán tối ưu hóa đàn
kiến ACO và phân cụm thô với các kỹ thuật phân cụm nguyên thủy để đề xuất
các thuật toán phân cụm dọc dữ liệu phân tán nhằm tối ưu các chi phí tính toán
và chất lượng sau phân cụm cho các bộ dữ liệu lớn
Để giải quyết những vấn đề nêu trên, 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" được thực hiện theo định hướng:
Trang 15Luận án đầy đủ ở file: Luận án Full