Luận án tiến sĩ Kỹ thuật: Thiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệu

Chia sẻ: Phong Tỉ | Ngày: | Loại File: PDF | Số trang:124

Thêm vào BST

Báo xấu

47
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu chính của luận án nhằm giải quyết bài toán phân mảnh dữ liệu phân tán bằng cách kết hợp một số kỹ thuật phân cụm trong KPDL, lý thuyết tập thô và phƣơng pháp tối ƣu hóa ACO,

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án tiến sĩ Kỹ thuật: Thiết kế cơ sở dữ liệu phân tán theo tiếp cận khai phá dữ liệu

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
iv 3.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
v DANH 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 2 AS Ant System Hệ 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 6 CFN Current Fragmentation Số mảnh hiện tại Number 7 FAC Fragmentation Ants Cluster Phân mảnh cho phân cụm kiến 8 FC Fragmentation Cluster Phân mảnh cho phân cụm 9 HFC Horizontal Fragmentation Phân cụm cho phân mảnh Cluster ngang 10 KDD Knowledge Discovery in Khám phá tri thức trong Database CSDL 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 Số mảnh tối ƣu Number 15 RST Rough Set Theory Lý thuyết tập thô 16 TA Top Attributes Thuộc tính đỉnh 17 TSP Travelling Salesman Bài toán ngƣời chào hàng Problem 18 VFAC Vertical Fragmentation Ants Phân cụm kiến cho phân Cluster mảnh dọc 19 VFC Vertical Fragmentation Phân cụm cho phân mảnh Cluster dọc
vi DANH 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ệ 3 Allocation Cấp phát 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 8 Big data Dữ liệu lớn 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) 14 Clustering Phân cụm 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 24 Equi-join Nối bằng 25 Fragmentation Phân mảnh 26 Fragmentation Transparency Trong suốt phân mảnh
vii 27 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ệ 38 Relevant Liên đới 39 Replication transparency Trong suốt nhân bản 40 Semi-join Nửa kết nối 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
viii 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 (p1, p2,...p6) ..................................... 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
ix DANH 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
x Hì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
1 MỞ ĐẦ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 đƣợc nhiề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ể
2 giải quyết bằng phân hoạch thành hai mảnh, cần phải thực hiện theo một phân mảnh hỗn hợp, gổm ít nhất một phân mảnh ngang và một phân mảnh dọc. - Các nghiên cứu gần đây, một số tác giả kết hợp giải bài toán phân mảnh và bài toán định vị bằng các kỹ thuật tối ƣu, kết hợp với các kỹ thuật heuristic [41]. Thời gian thực hiện các thuật toán này giảm đáng kể so với các thuật toán ban đầu. Tuy nhiên, các độ đo sự liên kết các thuộc tính là chƣa đƣợc sự 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ụm nà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:
3 - Kết hợp kỹ thuật phân cụm phân cấp tích tụ với phân cụm phân hoạch, cải tiến các thuật toán phân mảnh ngang, phân mảnh dọc dữ liệu trên cơ sở phát triển các độ đo tƣơng đồng và phƣơng thức xử lý các cụm sau phân mảnh. - Vận dụng lý thuyết tập thô và lý thuyết tối ƣu hóa đàn kiến ACO đề xuất thuật toán phân cụm dọc dữ liệu phân tán bằng kỹ thuật phân cụm thô KR và phân cụm đàn kiến VFAC. - Tiến hành so sánh, đánh giá và thử nghiệm các thuật toán cải tiến và thuật toán đề xuất mới với các thuật toán nguyên thủy trên các bộ dữ liệu lớn để làm rõ tính hiệu quả về chi phí, cũng nhƣ những ƣu điểm nổi trội qua thực nghiệm về chất lƣợng phân cụm sau phân mảnh. 2. MỤC TIÊU, ĐỐI TƢỢNG VÀ PHẠM VI NGHIÊN CỨU 2.1. Mục tiêu nghiên cứu Mục tiêu chính của luận án nhằm giải quyết bài toán phân mảnh dữ liệu phân tán bằng cách kết hợp một số kỹ thuật phân cụm trong KPDL, lý thuyết tập thô và phƣơng pháp tối ƣu hóa ACO, cụ thể là: - Nghiên cứu cải tiến thuật toán phân mảnh dọc và phân mảnh ngang dựa vào các kỹ thuật phân cụm tích hợp trong khai phá dữ liệu. - Nghiên cứu đề xuất mới thuật toán phân mảnh dọc dữ liệu phân tán dựa trên kỹ thuật phân cụm thô KR và phân cụm đàn kiến VFAC. 2.2. Đối tượng và phạm vi nghiên cứu Các đối tƣợng và phạm vi nghiên cứu luận án:  Các độ đo tƣơng đồng, việc xử lý khoảng cách cụm trong các thuật toán phân mảnh ngang, phân mảnh dọc dựa trên kỹ thuật phân cụm phân hoạch và phân cụm phân cấp tích tụ.  Kỹ thuật phân mảnh dọc dữ liệu phân tán dựa trên kỹ thuật phân cụm thô KR và phân cụm đàn kiến VFAC.  Vận dụng lý thuyết tập thô, các tiếp cận Meta-heuristic trong phƣơng
4 pháp tối ƣu hóa đàn kiến ACO để giải quyết bài toán phân cụm dữ liệu phục vụ cho các kỹ thuật phân mảnh trong thiết kế CSDL phân tán. 3. PHƢƠNG PHÁP NGHIÊN CỨU Các phƣơng pháp nghiên cứu của luận án: Phương pháp nghiên cứu lý thuyết: Nghiên cứu tổng quan tài liệu liên quan đến lý thuyết thiết kế CSDL phân tán và các kỹ thuật phân cụm trong khai phá dữ liệu để cải tiến, đề xuất các thuật toán phân mảnh dữ liệu phân tán theo kỹ thuật phân cụm thô và kỹ thuật phân cụm kiến FAC. Phương pháp thực nghiệm: Trên cơ sở các thuật toán phân mảnh đã cải tiến, đề xuất (VFC, HFC, KR và VAFC), luận án tiến hành cài đặt thử nghiệm với bộ công cụ mô phỏng SPMS, ngôn ngữ lập trình Java để phân tích, so sánh kết quả phân cụm các thuật toán đề xuất với những kỹ thuật phân mảnh nguyên thủy tiêu biểu nhƣ k-Means, k-Medoids, HAC. 4. ĐÓNG GÓP CỦA LUẬN ÁN 4.1. Về mặt khoa học  Vận dụng thành công cách tiếp cận tập thô và tối ƣu hóa đàn kiến ACO cho bài toán phân mảnh dọc trong thiết kế CSDL phân tán theo tiếp cận KPDL.  Nghiên cứu cải tiến thuật toán phân mảnh ngang HFC và phân mảnh dọc VFC bằng việc phát triển các độ đo tƣơng đồng và các kỹ thuật xử lý cụm trong phân cụm.  Nghiên cứu đề xuất thuật toán phân mảnh dọc theo kỹ thuật phân cụm thô KR và kỹ thuật phân cụm đàn kiến VFAC. 4.2. Về mặt thực tiễn Kết quả cài đặt thử nghiệm trong luận án cho thấy kết quả phân cụm bằng các thuật toán cải tiến HFC, VFC và các thuật toán đề xuất mới KR, VFAC tốt hơn về thời gian tính toán, chi phí bộ nhớ, số cụm sau phân mảnh và đặc biệt khi thực hiện trên các bộ dữ liệu với số đối tƣợng cần phân cụm lớn [30, 62].
5 5. BỐ CỤC CỦA LUẬN ÁN Ngoài phần mở đầu và kết luận, luận án đƣợc bố cục trong ba chƣơng: Chƣơng 1 trình bày các nghiên cứu về thiết kế cơ sở dữ liệu phân tán bao gồm các kỹ thuật phân mảnh dọc, phân mảnh ngang và thuật toán phân mảnh theo phân cụm FC (Fragmentation Cluster). Chƣơng 2 trình bày các nghiên cứu liên quan đến các kỹ thuật phân cụm trong khai phá dữ liệu đƣợc áp dụng cho các bài toán phân mảnh ngang, phân mảnh dọc dữ liệu phân tán và đề xuất cải tiến hai thuật toán VFC và HFC. Chƣơng 3 trình bày kỹ thuật phân mảnh dọc dữ liệu phân tán theo tiếp cận khai phá dữ liệu bằng các kỹ thuật phân cụm thô KR (k-Means Rough), phân cụm đàn kiến FAC (Fragmentation Ants Cluster). Cài đặt thực nghiệm và so sánh đối chiếu kết quả các thuật toán cải tiến, đề xuất mới so với thuật toán nguyên thủy k-Means, HAC.
6 Chƣơng . THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN Nội dung Chƣơng 1 gồm hai phần chính: phần đầu giới thiệu tổng quan về hệ cơ sở dữ liệu phân tán, phần thứ hai giới thiệu về bài toán phân mảnh trong thiết kế cơ sở dữ liệu phân tán với các yêu cầu, mục tiêu, chiến lƣợc thỏa mãn tính đúng, tính đầy đủ và tính tái thiết đƣợc. Các thuật toán cơ bản đƣợc xem xét trong chƣơng là bài toán phân mảnh dọc và phân mảnh ngang dữ liệu phân tán từ các thuật toán nguyên thủy nhƣ thuật toán BEA, thuật toán PHORIZONTAL hay thuật toán phân mảnh FC dùng kỹ thuật phân cụm CA. 1.1. TỔNG QUAN VỀ HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN Cơ sở dữ liệu phân tán (Distributed DataBase - DDB) [2] là một tập hợp nhiều CSDL có liên quan với nhau về mặt logic, nhƣng phân tán ở nhiều vị trí khác nhau. Các hệ thống CSDL kết nối, trao đổi với nhau bằng cách gửi, nhận các thông điệp thông qua mạng các máy tính. CSDL phân tán thỏa hai tính chất cơ bản sau:  Tính liên quan logic: Toàn bộ dữ liệu của CSDL phân tán thõa mản một số ràng buộc gắn kết chúng với nhau. Điều này cho phép có thể phân biệt CSDL phân tán với các CSDL cục bộ hoặc các tập tin lƣu trữ tại các vị trí khác nhau trong một mạng truyền thông.  Tính chất phân tán: Toàn bộ dữ liệu của CSDL phân tán không đƣợc lƣu trữ tại một trạm duy nhất mà đƣợc lƣu trữ trên nhiều trạm. Điều này cho phép phân biệt CSDL phân tán với CSDL tập trung truyền thống. Hệ CSDL phân tán (Distributed DataBase System - DDBS) là sự hợp nhất của hai hƣớng tiếp cận đối với một quá trình xử lý dữ liệu: công nghệ CSDL và công nghệ mạng máy tính. Để tạo ra một hệ CSDL phân tán, các tập tin không chỉ có liên quan logic, chúng còn phải có cấu trúc và đƣợc truy xuất qua một
7 giao diện chung. Minh họa mô hình hệ CSDL phân tán, gồm nhiều trạm liên lạc với nhau qua mạng truyền thông (Hình 1.1) : Trạm 1 Mạng Trạm i+1 Trạm 2 truyền thông ... Trạm i Hình 1.1 Minh họa mô hình hệ CSDL phân tán Hệ quản trị CSDL phân tán (Distributed Database Management System - D-DBMS) là một hệ thống phần mềm cho phép quản lý các hệ CSDL phân tán và làm cho sự phân tán về dữ liệu hay việc xử lý phân tán trở nên “trong suốt” đối với ngƣời sử dụng (NSD) [58]. 1.1.1. Các đặc điểm cơ bản của hệ cơ sở dữ liệu phân tán Hệ CSDL phân tán thƣờng có các đặc tính quan trọng sau [36, 47]:  Chia sẻ tài nguyên: Mỗi tài nguyên đƣợc quản lý bởi một chƣơng trình có giao diện truyền thông. Các tài nguyên đƣợc truy cập, cập nhật đảm bảo sự tin cậy và nhất quán. Tài nguyên phân tán đƣợc quản lý: lập kế hoạch dự phòng, thiết lập quyền giữa các trạm và ánh xạ tài nguyên vào địa chỉ truyền thông.  Tính mở: Cho phép tạo ra từ nhiều phần cứng không đồng nhất và từ nhiều bộ phần mềm khác nhau, đảm bảo các thành phần này phải tuân theo tiêu chuẩn chung. Tính mở hệ thống đƣợc hoàn thiện bằng cách phân định rõ các giao diện chính của hệ thống, làm cho nó tƣơng thích với nhiều nhà phát triển phần mềm. Ngoài ra, tính mở của hệ CSDL phân tán còn gắn với việc cung cấp cơ chế truyền thông giữa các tiến trình, công khai các giao diện trong truy cập và các tài nguyên dùng chung [41].
8  Khả năng mở rộng: Hệ CSDL phân tán có khả năng hoạt động và khai thác hiệu quả ở nhiều mức khác nhau. Khả năng mở rộng gắn với đặc tính không phải thay đổi phần mềm hệ thống và phần mềm ứng dụng. Yêu cầu mở rộng có thể về phần cứng, các hệ thống mạng và hệ phân tán trong thiết kế hệ CSDL phân tán [3].  Khả năng song song: Khả năng song song trong hệ CSDL phân tán đƣợc thực hiện dƣới hai tình huống: nhiều ngƣời sử dụng đồng thời ra các lệnh, tƣơng tác với nhiều chƣơng trình ứng dụng hoặc nhiều tiến trình server chạy đồng thời.  Khả năng thứ lỗi: Khả năng thứ lỗi của hệ CSDL phân tán dựa trên hai nguyên lý cơ bản, đó là khả năng thay thế để đảm bảo sự hoạt động liên tục, hiệu quả và khả năng hồi phục khi có xảy ra sự cố [71].  Tính trong suốt: Tính trong suốt của hệ CSDL phân tán chứa đựng một số đặc tính cơ bản: Tính trong suốt về vị trí, trong suốt trong việc sử dụng, trong suốt của việc phân chia và trong suốt của sự trùng lặp [3].  Tin cậy và nhất quán: Hệ CSDL phân tán yêu cầu độ tin cậy cao, đảm bảo sự bí mật dữ liệu và các chức năng khôi phục dữ liệu sau sự cố. Yêu cầu về tính nhất quán là rất quan trọng, thể hiện dƣới dạng các yêu cầu có mâu thuẫn trong nội dung dữ liệu, khi các thuộc tính dữ liệu khác nhau, các thao tác vẫn phải nhất quán [40]. 1.1.2. Các mục tiêu của hệ cơ sở dữ liệu phân tán Mục tiêu chính của các hệ CSDL phân tán là đảm bảo tính trong suốt và tính hiệu năng cao khi xử lý dữ liệu phân tán. Nghĩa là hệ CSDL phân tán phải cung cấp các mức độc lập khác nhau đối với dữ liệu và ngƣời dùng. 1.1.2.1. Tính độc lập đối với sự phân tán dữ liệu Ngƣời dùng không cần quan tâm tới sự phân tán của dữ liệu và có thể không biết có sự phân tán. Thông tin về phân tán dữ liệu đƣợc lƣu trữ trong từ