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ĩ

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:. Đ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. Lê Văn Sơn và PGS. 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 .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. THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN. TỔNG QUAN VỀ HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN. Các đặc điểm cơ bản của hệ cơ sở dữ liệu phân tán.

Các mục tiêu của hệ cơ sở dữ liệu phân tán. Kiến trúc của hệ cơ sở dữ liệu phân tán. Các mô hình hệ cơ sở dữ liệu phân tán. THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN.

Các chiến lƣợc thiết kế. Các vấn đề thiết kế cơ sở dữ liệu phân tán. Kỹ thuật thiết kế cơ sở dữ liệu phân tán. Các quy tắc phân mảnh đúng đắn.

Thảo luận về thiết kế cơ sở dữ liệu phân tán. THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN BẰNG CÁC KỸ THUẬT PHÂN MẢNH. Kỹ thuật phân mảnh ngang. Kỹ thuật phân mảnh dọc.

Thuật toán phân mảnh FC. Kỹ thuật phân mảnh hỗn hợp. Thảo luận các kỹ thuật phân mảnh. KẾT CHƢƠNG.

PHÂN CỤM DỮ LIỆU TRONG THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN. TIẾP CẬN KHAI PHÁ DỮ LIỆU. Khai phá tri thức và khai phá dữ liệu. Những thách thức trong khai phá dữ liệu.

Các bài toán khai phá dữ liệu. KỸ THUẬT PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU. Kỹ thuật phân cụm. Các kiểu dữ liệu và độ đo trong phân cụm.

Một số phƣơng pháp phân cụm dữ liệu. Thảo luận về các kỹ thuật phân cụm. PHÂN MẢNH DỮ LIỆU DỰA VÀO KỸ THUẬT PHÂN CỤM. Đề xuất cải tiến thuật toán phân mảnh dọc VFC.

Đề xuất cải tiến thuật toán phân mảnh ngang HFC. Đánh giá kết quả thực nghiệm. KẾT CHƢƠNG. 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.

THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN THEO TIẾP CẬN TẬP THÔ .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ô. Hệ thông tin. Quan hệ không phân biệt, bất khả phân biệt trong hệ thông tin. Thuộc tính và vector đặc trƣng tham chiếu.

PHÂN CỤM DỮ LIỆU PHÂN TÁN THEO TIẾP CẬN TẬP THÔ. Thuật toán phân cụm thô KR (K-Means Rough). Kết quả thực nghiệm thuật toán phân cụm thô KR. THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN THEO PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN.

Phƣơng pháp tối ƣu hóa đàn kiến. Từ đàn kiến tự nhiên đến đàn kiến nhân tạo. Thuật toán ACO tổng quát. Thuật toán hệ kiến AS.

Tổ chức dữ liệu và các khái niệm độ đo. PHÂN CỤM DỮ LIỆU PHÂN TÁN THEO TIẾP CẬN TỐI ƢU ĐÀN KIẾN. Phân cụm dữ liệu phân tán theo tiếp cận ACO. Đề xuất các thuật toán phân mảnh dọc theo phân cụm đàn kiến.

Kết quả thực nghiệm thuật toán đề xuất VFAC. KẾT CHƢƠNG. 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 .2 Ma trận ái lực thuộc tính AA .1 Bảng sự kiện cho biến nhị phân [I] .2 Ma trận khoảng cách đối tượng .3 Ma trận khoảng cách các cụm sau gom cụm bước 3 .4 Khoảng cách giữa các cụm sau khi gom cụm bước 3 .5 Khoảng cách giữa các cụm sau 4 lần gom cụm .6 Vector hóa các bản ghi .7 Ma trận OCM .8 Bảng biểu diễn 6 đối tượng (p1, p2,.9 Khoảng cách Euclide giữa 6 đối tượng .10 Tập D gồm 20 đối tượng cần phân cụm .11 So sánh kết quả với phân cụm k-Means và VFC .12 Kết quả phân mảnh ngang cải tiến HFC .13 Kết quả phân mảnh ngang theo k-Medoids.1 Tập D gồm 20 đối tượng cần phân cụm .2 So sánh kết quả phân cụm thô KR và k-Means .3 Bảng tham số .4 Tập dữ liệu D gồm 20 giao tác .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 .2 Mô hình kiến trúc hệ cơ sở dữ liệu phân tán .3 Ma trận định vị điểm tách Top_A và Bot_A .4 Sơ đồ cây phân mảnh hỗn hợp .1 Quá trình khám phá tri thức .2 Khoảng cách ngắn nhất giữa hai cụm .3 Khoảng cách lớn nhất giữa hai cụm .4 Khoảng cách trung bình giữa hai cụm.5 Kết quả cây phân cụm phân cấp tích tụ .6 Tập các đối tượng p cần phân cụm .7 Kết quả phân cụm theo khoảng cách ngắn nhất .8 Kết quả phân cụm theo khoảng cách lớn nhất .9 Kết quả phân cụm theo thuật toán k-Means (k = 3) .10 Kết quả phân cụm theo thuật toán k -Means (k = 15) .11 Kết quả phân cụm theo thuật toán VFC (số cụm k = 3) .1 Minh họa gom cụm vào bộ các xấp xỉ dưới và xấp xỉ trên .2 Kết quả phân cụm theo thuật toán k-Means (k = 6) .3 Kết quả phân cụm theo thuật toán k-Means (k = 15) .4 Kết quả phân cụm thô KR (k = 6) .5 Kết quả phân cụm theo thuật toán k-Means (k = 10) .6 Kết quả phân cụm thuật toán VFAC (k = 10).7 Kết quả phân cụm với thuật toán VFAC (k = 3).8 So sánh chi phí trung bình lỗi trên k-Means và VFAC .9 Đánh giá độ ổn định theo số cụm trên k-Means và VFAC. 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ệ.