Tổng Quan Về Khai Phá Dữ Liệu và Phụ Thuộc Hàm Xấp Xỉ

Luận văn thạc sĩ khám phá phụ thuộc hàm xấp xỉ qua phủ tối thiểu và lớp tương đương, cung cấp cái nhìn sâu sắc về ứng dụng toán học.

• Trường học: Đại Học Thái Nguyên
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Khai Phá Dữ Liệu và Phụ Thuộc Hàm Xấp Xỉ: Tổng Quan và Ứng Dụng
• Loại tài liệu: luận văn
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ PHỤ THUỘC HÀM, PHỤ THUỘC HÀM XẤP XỈ
• 1.1. Khai phá dữ liệu
• 1.2. Khám phá tri thức và khai phá dữ liệu
• 1.3. Kiến trúc của hệ thống khai phá dữ liệu
• 1.4. Quá trình khai phá dữ liệu
• 1.5. Một số kỹ thuật khai phá dữ liệu
• 2. CHƯƠNG 2: THUẬT TOÁN KHAI PHÁ PHỤ THUỘC HÀM XẤP XỈ SỬ DỤNG PHỦ TỐI THIỂU VÀ LỚP TƯƠNG ĐƯƠNG
• 2.1. Lớp tương đương và phủ tối thiểu
• 2.2. Sự phân hoạch
• 2.3. Phân hoạch mịn hơn
• 2.4. Phủ tối thiểu
• 2.5. Phụ thuộc hàm xấp xỉ và lớp tương đương
• 2.6. Thuật toán TANE sửa đổi
• 2.7. Thủ tục chính của thuật toán TANE sửa đổi
• 2.8. Độ phức tạp của thuật toán TANE sửa đổi
• 2.9. Thuật toán khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tương đương
• 2.10. Mô tả thuật toán
• 2.11. Độ phức tạp của thuật toán khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tương đương
• 2.12. Phân tích thử nghiệm, so sánh về độ phức tạp thời gian
• 3. CHƯƠNG 3: THỰC NGHIỆM KHAI PHÁ PHỤ THUỘC HÀM XẤP XỈ
• 3.1. Xây dựng chương trình thực nghiệm
• 3.2. Giới thiệu bài toán
• 3.3. Dữ liệu thử nghiệm
• 3.4. Thực nghiệm khai phá phụ thuộc hàm xấp xỉ
• 3.5. Kết quả thực nghiệm
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Khai Phá Dữ Liệu Khái Niệm Và Ý Nghĩa

Khai phá dữ liệu (KPDL) là quá trình rút trích tri thức từ khối lượng dữ liệu lớn. Quá trình này không chỉ giúp phát hiện các mẫu ẩn mà còn mang lại giá trị cho các lĩnh vực khác nhau. KPDL được coi là cốt lõi của phát hiện tri thức từ cơ sở dữ liệu (KDD). Việc hiểu rõ về KPDL là rất quan trọng trong bối cảnh công nghệ thông tin hiện đại.

1.1. Khái Niệm Khai Phá Dữ Liệu Và Các Bước Chính

KPDL bao gồm các bước như trích chọn dữ liệu, tiền xử lý, biến đổi dữ liệu, khai phá dữ liệu và đánh giá tri thức. Mỗi bước đều có vai trò quan trọng trong việc đảm bảo chất lượng và tính chính xác của thông tin được khai thác.

1.2. Tầm Quan Trọng Của Khai Phá Dữ Liệu Trong Thế Giới Hiện Đại

KPDL giúp các tổ chức tối ưu hóa quy trình ra quyết định, nâng cao hiệu quả kinh doanh và cải thiện dịch vụ khách hàng. Việc khai thác tri thức từ dữ liệu lớn ngày càng trở nên cần thiết trong mọi lĩnh vực.

II. Vấn Đề Và Thách Thức Trong Khai Phá Dữ Liệu Hiện Nay

Mặc dù KPDL mang lại nhiều lợi ích, nhưng cũng đối mặt với nhiều thách thức. Các vấn đề như dữ liệu không chính xác, dữ liệu thiếu và sự phức tạp trong việc xử lý dữ liệu lớn là những thách thức lớn. Những vấn đề này có thể ảnh hưởng đến độ tin cậy của kết quả khai thác.

2.1. Dữ Liệu Không Chính Xác Và Ảnh Hưởng Đến Kết Quả

Dữ liệu không chính xác có thể dẫn đến những quyết định sai lầm. Việc phát hiện và xử lý dữ liệu không chính xác là rất quan trọng để đảm bảo tính chính xác của các mẫu được khai thác.

2.2. Khó Khăn Trong Việc Xử Lý Dữ Liệu Lớn

Xử lý dữ liệu lớn đòi hỏi các công cụ và kỹ thuật tiên tiến. Sự phức tạp trong việc tích hợp và phân tích dữ liệu từ nhiều nguồn khác nhau cũng là một thách thức lớn.

III. Phương Pháp Khai Phá Dữ Liệu Các Kỹ Thuật Chính

Có nhiều phương pháp và kỹ thuật khác nhau trong KPDL, bao gồm phân lớp, phân nhóm, hồi quy và phát hiện mẫu. Mỗi phương pháp có ưu điểm và ứng dụng riêng, giúp khai thác tri thức từ dữ liệu một cách hiệu quả.

3.1. Phân Lớp Dữ Liệu Kỹ Thuật Dự Đoán

Phân lớp là kỹ thuật giúp phân loại dữ liệu thành các nhóm khác nhau. Kỹ thuật này thường được sử dụng trong các ứng dụng như dự đoán hành vi khách hàng.

3.2. Phân Nhóm Dữ Liệu Tìm Kiếm Mẫu Tương Tự

Phân nhóm là quá trình nhóm các đối tượng tương tự lại với nhau. Kỹ thuật này thường được áp dụng trong phân tích thị trường và phân khúc khách hàng.

3.3. Hồi Quy Dự Đoán Giá Trị Liên Tục

Hồi quy là kỹ thuật giúp dự đoán giá trị liên tục dựa trên các biến độc lập. Kỹ thuật này rất hữu ích trong các lĩnh vực như tài chính và y tế.

IV. Ứng Dụng Thực Tiễn Của Khai Phá Dữ Liệu Trong Nghiên Cứu

KPDL có nhiều ứng dụng thực tiễn trong các lĩnh vực như y tế, tài chính, marketing và giáo dục. Việc áp dụng KPDL giúp cải thiện quy trình ra quyết định và tối ưu hóa hiệu suất.

4.1. Ứng Dụng Trong Y Tế Dự Đoán Bệnh Tật

KPDL giúp phân tích dữ liệu bệnh nhân để dự đoán các bệnh tật tiềm ẩn. Việc này không chỉ nâng cao chất lượng chăm sóc sức khỏe mà còn tiết kiệm chi phí.

4.2. Ứng Dụng Trong Tài Chính Quản Lý Rủi Ro

Trong lĩnh vực tài chính, KPDL được sử dụng để phân tích rủi ro và tối ưu hóa danh mục đầu tư. Điều này giúp các nhà đầu tư đưa ra quyết định chính xác hơn.

4.3. Ứng Dụng Trong Marketing Tối Ưu Hóa Chiến Lược

KPDL giúp các doanh nghiệp phân tích hành vi khách hàng để tối ưu hóa chiến lược marketing. Việc này giúp tăng cường hiệu quả quảng cáo và nâng cao doanh thu.

V. Kết Luận Tương Lai Của Khai Phá Dữ Liệu Và Phụ Thuộc Hàm Xấp Xỉ

Khai phá dữ liệu và phụ thuộc hàm xấp xỉ đang trở thành xu hướng quan trọng trong nghiên cứu và ứng dụng công nghệ thông tin. Tương lai của KPDL hứa hẹn sẽ mang lại nhiều cơ hội mới cho các lĩnh vực khác nhau.

5.1. Xu Hướng Phát Triển Công Nghệ Khai Phá Dữ Liệu

Công nghệ KPDL sẽ tiếp tục phát triển với sự hỗ trợ của trí tuệ nhân tạo và học máy. Điều này sẽ giúp nâng cao khả năng phân tích và dự đoán.

5.2. Tầm Quan Trọng Của Phụ Thuộc Hàm Xấp Xỉ

Phụ thuộc hàm xấp xỉ sẽ đóng vai trò quan trọng trong việc xử lý dữ liệu không chính xác. Việc áp dụng các phương pháp này sẽ giúp cải thiện độ tin cậy của kết quả khai thác.

Nội dung chính

Tổng quan nghiên cứu

Trong thời đại bùng nổ thông tin, hơn 80% cơ sở dữ liệu tại các doanh nghiệp và tổ chức đều tồn tại dữ liệu nhiễu, không nhất quán hoặc xuất hiện các ngoại lệ ở mức từ 1% đến 5%. Trong lý thuyết cơ sở dữ liệu quan hệ truyền thống, khái niệm phụ thuộc hàm kinh điển đòi hỏi tính thỏa mãn tuyệt đối trên toàn bộ tập dữ liệu. Điều này dẫn đến sự cứng nhắc nghiêm trọng: một quan hệ chứa 10.000 bản ghi nhưng chỉ cần xuất hiện 2 đến 3 bộ dữ liệu sai lệch thì toàn bộ quy luật phụ thuộc hàm giữa các thuộc tính sẽ bị bác bỏ hoàn toàn, làm mất đi các tri thức cấu trúc tiềm ẩn vô cùng giá trị.

Nhằm khắc phục rào cản này, nghiên cứu tập trung giải quyết bài toán khai phá phụ thuộc hàm xấp xỉ, một hướng mở rộng cho phép chấp nhận một tỷ lệ sai số nhất định trong cơ sở dữ liệu quan hệ. Mục tiêu cụ thể của đề tài là xây dựng, phân tích và đánh giá hiệu năng của thuật toán khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tương đương, viết tắt là AFDMCEC, đồng thời tiến hành so sánh đối chuẩn với thuật toán TANE sửa đổi.

Nghiên cứu được tiến hành trên các tập dữ liệu thực nghiệm chuẩn từ kho dữ liệu máy học quốc tế UCI với các mức ngưỡng lỗi sai số biến thiên từ 0,01 đến 0,5. Về mặt ý nghĩa thực tiễn, thuật toán đề xuất giúp tối ưu hóa không gian tìm kiếm, giảm thời gian tính toán từ 25% đến 40% so với các phương pháp duyệt dàn tổ hợp truyền thống. Kết quả này mang lại công cụ đắc lực cho các bài toán chuẩn hóa lược đồ dữ liệu, làm sạch dữ liệu tự động và tối ưu hóa các câu truy vấn phức tạp trong các hệ thống thông tin quy mô lớn.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nền tảng vững chắc của lý thuyết thiết kế cơ sở dữ liệu quan hệ và các kỹ thuật khai phá dữ liệu hiện đại. Trước hết, hệ thống lý thuyết phụ thuộc hàm và hệ tiên đề Armstrong bao gồm 3 luật suy diễn căn bản: tính phản xạ, tính gia tăng và tính bắc cầu. Đây là cơ sở cốt lõi để xác định bao đóng thuộc tính và loại bỏ các phụ thuộc hàm dư thừa.

Bên cạnh đó, lý thuyết phân hoạch và lớp tương đương đóng vai trò chuyển đổi bài toán kiểm tra phụ thuộc hàm từ việc so sánh từng cặp bản ghi sang việc đối chiếu các tập hợp nhóm. Một phân hoạch chia tập hợp bản ghi thành các lớp tương đương dựa trên giá trị thuộc tính đồng nhất; mối quan hệ phân hoạch mịn hơn cho phép xác định trực tiếp tính thỏa mãn của phụ thuộc hàm.

Khung lý thuyết mở rộng tiếp theo là phụ thuộc hàm xấp xỉ với độ đo sai số g3. Độ đo này định lượng tỷ lệ giữa số lượng bản ghi tối thiểu cần loại bỏ trên tổng số bản ghi của quan hệ để phụ thuộc hàm trở nên đúng đắn. Một phụ thuộc hàm được công nhận là xấp xỉ khi giá trị sai số g3 không vượt quá ngưỡng lỗi epsilon cho trước nằm trong khoảng từ 0 đến 1. Cuối cùng, lý thuyết phủ tối thiểu được ứng dụng triệt để nhằm đảm bảo tập phụ thuộc hàm tìm được luôn có vế phải đơn thuộc tính và loại bỏ hoàn toàn các thuộc tính dư thừa ở vế trái.

Phương pháp nghiên cứu

Nghiên cứu kết hợp chặt chẽ giữa phân tích mô hình toán học lý thuyết và đánh giá thực nghiệm định lượng trên máy tính. Dữ liệu thực nghiệm được thu thập từ kho lưu trữ dữ liệu chuẩn UCI Machine Learning Repository, bao gồm các bảng quan hệ đa dạng có quy mô từ 5 đến 30 thuộc tính và dung lượng lên đến hàng chục nghìn bộ dữ liệu.

Phương pháp chọn mẫu áp dụng kỹ thuật trích chọn toàn bộ kết hợp lấy mẫu ngẫu nhiên phân tầng nhằm bảo toàn đầy đủ các mẫu phân phối đặc trưng và các trường hợp biên của dữ liệu thực tế. Lý do lựa chọn phương pháp phân tích lớp tương đương kết hợp phủ tối thiểu xuất phát từ tính vượt trội trong việc kiểm soát sự bùng nổ tổ hợp. Không gian tìm kiếm phụ thuộc hàm trên tập gồm m thuộc tính tăng trưởng theo cấp số mũ với kích thước dàn ứng viên lên tới 2 lũy thừa m. Việc tích hợp kiểm tra bao đóng tương đương cho phép thuật toán lập tức loại bỏ các nhánh thuộc tính trùng lặp, đưa độ phức tạp tổng thể về mức tối ưu theo hàm đa thức của số bản ghi và số thuộc tính.

Toàn bộ quá trình nghiên cứu được triển khai theo tiến trình 3 giai đoạn rõ ràng: giai đoạn 1 chuẩn hóa và mã hóa dữ liệu đầu vào, giai đoạn 2 thực thi song song thuật toán TANE sửa đổi và thuật toán AFDMCEC trên cùng tập tham số, giai đoạn 3 đo đạc thời gian thực thi và thống kê số lượng phụ thuộc hàm xấp xỉ trích xuất được.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình phân tích thực nghiệm và đánh giá độ phức tạp đã mang lại 4 phát hiện học thuật quan trọng:

• Khả năng cắt tỉa không gian ứng viên vượt trội: Bằng việc xác định các thuộc tính tương đương thông qua bao đóng xấp xỉ ở từng mức của dàn tìm kiếm, thuật toán AFDMCEC đã loại bỏ trung bình từ 30% đến 45% số lượng thuộc tính ứng viên dư thừa ngay từ các bước lặp ban đầu.
• Rút ngắn thời gian xử lý thực tế: Khi chạy trên các tập dữ liệu có trên 15 thuộc tính và 5.000 bản ghi, thuật toán AFDMCEC cho tốc độ thực thi nhanh hơn khoảng 35% so với thuật toán TANE sửa đổi.
• Quy luật biến thiên theo ngưỡng sai số: Khi điều chỉnh ngưỡng sai số epsilon tăng dần từ 0,05 lên 0,2 trên cùng một quan hệ thử nghiệm, số lượng phụ thuộc hàm xấp xỉ hợp lệ phát hiện được tăng từ 12 lên 38 phụ thuộc hàm, phản ánh đầy đủ các ràng buộc tiềm ẩn vốn bị che khuất bởi nhiễu dữ liệu.
• Tính cô đọng và tối tiểu của tập kết quả: 100% tập phụ thuộc hàm xấp xỉ do AFDMCEC sinh ra đều đạt tính chất phủ tối thiểu, không chứa bất kỳ thuộc tính dư thừa nào ở cả hai vế, giúp giảm dung lượng lưu trữ tri thức hơn 50% so với các thuật toán sinh phụ thuộc hàm thô.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp AFDMCEC đạt hiệu năng vượt trội nằm ở cơ chế lồng ghép tính toán phủ tối thiểu trực tiếp trong thủ tục sinh ứng viên mức tiếp theo. Thay vì phải sinh toàn bộ không gian rồi mới tiến hành lọc như các giải thuật truyền thống, việc loại bỏ sớm các thuộc tính có cùng bao đóng xấp xỉ đã ngăn chặn triệt để hiện tượng bùng nổ trạng thái.

Khi so sánh với các công trình kinh điển trong ngành, kết quả nghiên cứu hoàn toàn tương thích với các phân tích lý thuyết của những tác giả đi trước trong lĩnh vực khai phá phụ thuộc hàm từ năm 1999, đồng thời chứng minh tính cải tiến rõ rệt so với các công bố khoa học quốc tế năm 2009 về độ phức tạp tính toán.

Trong thực tế phân tích dữ liệu, các kết quả này có thể được biểu diễn trực quan hóa vô cùng hiệu quả:

• Biểu đồ đường biểu diễn sự thay đổi của thời gian chạy theo số lượng thuộc tính từ 5 đến 25, minh họa rõ nét độ dốc thời gian của AFDMCEC luôn thấp hơn đáng kể so với TANE sửa đổi.
• Bảng ma trận đối sánh số lượng phụ thuộc hàm tìm được tương ứng với từng mức sai số từ 0,01 đến 0,5, giúp các chuyên gia dữ liệu dễ dàng lựa chọn điểm cân bằng tối ưu giữa độ chính xác và mức độ bao phủ tri thức.

Đề xuất và khuyến nghị

Nhằm chuyển hóa các kết quả nghiên cứu thành giá trị thực tiễn trong ngành công nghệ thông tin và quản trị dữ liệu, 4 giải pháp trọng tâm được đề xuất như sau:

• Tích hợp module AFDMCEC vào hệ quản trị cơ sở dữ liệu: Các doanh nghiệp phần mềm cần phát triển công cụ phụ trợ chạy thuật toán AFDMCEC để tự động phân tích cấu trúc bảng, hướng tới mục tiêu giảm 50% thời gian thiết kế lược đồ quan hệ trong lộ trình triển khai từ 6 đến 12 tháng.
• Ứng dụng phụ thuộc hàm xấp xỉ trong làm sạch dữ liệu tự động: Bộ phận kỹ thuật dữ liệu tại các tổ chức cần khai thác tập phụ thuộc hàm xấp xỉ tìm được để tự động dự đoán và khôi phục từ 70% đến 85% các giá trị thuộc tính bị khuyết thiếu, áp dụng định kỳ trong quy trình kiểm tra chất lượng dữ liệu hàng quý.
• Cải tiến bộ tối ưu hóa truy vấn cơ sở dữ liệu: Các nhóm phát triển hệ thống cần ứng dụng các luật phụ thuộc xấp xỉ để viết lại câu lệnh truy vấn SQL, giúp cải thiện tốc độ phản hồi các truy vấn phức hợp lên ít nhất 20% trong giai đoạn thử nghiệm 3 tháng.
• Mở rộng thuật toán cho môi trường dữ liệu lớn: Các viện nghiên cứu và trường đại học chuyên ngành công nghệ thông tin cần tiếp tục nghiên cứu phiên bản song song hóa của AFDMCEC trên nền tảng phân tán như Apache Spark, đặt mục tiêu xử lý hiệu quả các tập dữ liệu có quy mô trên 10 triệu bản ghi trong thời gian 18 tháng tới.

Đối tượng nên tham khảo luận văn

Nội dung và kết quả của luận văn mang lại giá trị học thuật và ứng dụng chuyên sâu cho 4 nhóm đối tượng chính:

• Giảng viên, nghiên cứu sinh và học viên cao học ngành Công nghệ Thông tin: Tài liệu cung cấp cơ sở toán học chuẩn xác về lý thuyết phân hoạch, lớp tương đương, các độ đo sai số và phương pháp phân tích độ phức tạp thuật toán khai phá tri thức.
• Kỹ sư dữ liệu và chuyên viên thiết kế kiến trúc hệ thống: Hữu ích trong việc áp dụng các giải thuật tối ưu vào quy trình trích xuất, biến đổi và nạp dữ liệu, giúp nâng cao độ chính xác của các đường ống dữ liệu lên trên 95%.
• Quản trị viên cơ sở dữ liệu: Cung cấp phương pháp khoa học để tái cấu trúc và chuẩn hóa lược đồ bảng về dạng chuẩn 3 hoặc dạng chuẩn Boyce-Codd mà không làm đứt gãy các mối liên kết nghiệp vụ thực tế.
• Chuyên gia phân tích dữ liệu và kỹ sư học máy: Giúp ứng dụng phụ thuộc hàm xấp xỉ vào bài toán lựa chọn đặc trưng, loại bỏ ít nhất 20% các biến phụ thuộc dư thừa trước khi đưa vào huấn luyện mô hình dự báo.

Câu hỏi thường gặp

Phụ thuộc hàm xấp xỉ khác biệt như thế nào so với phụ thuộc hàm truyền thống? Phụ thuộc hàm truyền thống đòi hỏi tính chính xác tuyệt đối trên mọi bản ghi, chỉ cần một trường hợp sai lệch sẽ làm mất giá trị của quy luật. Ngược lại, phụ thuộc hàm xấp xỉ cho phép chấp nhận một tỷ lệ lỗi nhỏ trong khoảng từ 1% đến 5%, giúp giữ lại các mối quan hệ ngữ nghĩa tiềm ẩn trong dữ liệu thực tế.

Độ đo sai số g3 được hiểu và tính toán như thế nào? Độ đo g3 đại diện cho tỷ số giữa số lượng bản ghi tối thiểu cần loại bỏ để quan hệ trở nên thỏa mãn phụ thuộc hàm trên tổng số bản ghi của bảng dữ liệu. Ví dụ trong bảng 8 bản ghi, nếu chỉ cần bỏ đi 1 bản ghi để quy luật đúng thì sai số g3 bằng 1 phần 8, tức 0,125.

Tại sao thuật toán AFDMCEC lại đạt hiệu năng cao hơn thuật toán TANE sửa đổi? Thuật toán AFDMCEC tích hợp cơ chế phủ tối thiểu và kiểm tra bao đóng tương đương ngay trong quá trình duyệt dàn thuộc tính. Điều này giúp loại bỏ sớm khoảng 30% các nhánh ứng viên dư thừa, giúp giảm đáng kể số phép tính so với việc duyệt toàn bộ như TANE sửa đổi.

Nên thiết lập ngưỡng sai số epsilon ở mức bao nhiêu là phù hợp? Trong thực tế xử lý dữ liệu doanh nghiệp, ngưỡng sai số epsilon thường được khuyến nghị thiết lập trong khoảng từ 0,01 đến 0,1. Mức này vừa đủ để lọc bỏ các sai số nhập liệu ngẫu nhiên mà không làm sai lệch bản chất logic của các mối quan hệ nghiệp vụ cốt lõi.

Thuật toán AFDMCEC có thể ứng dụng trực tiếp cho dữ liệu dạng chuỗi văn bản không? Hoàn toàn có thể. Thuật toán sử dụng bước tiền xử lý mã hóa ánh xạ các giá trị định danh hoặc chuỗi văn bản sang tập số nguyên dương liên tiếp. Nhờ đó, việc phân hoạch lớp tương đương trên dữ liệu chuỗi được thực hiện với tốc độ xử lý tương đương dữ liệu số.

Kết luận

Luận văn đã giải quyết trọn vẹn và chuyên sâu bài toán khai phá tri thức dạng phụ thuộc hàm xấp xỉ trong cơ sở dữ liệu quan hệ thông qua 5 đóng góp cốt lõi:

• Hệ thống hóa toàn diện nền tảng lý thuyết về phụ thuộc hàm, các biến thể phụ thuộc dữ liệu và hệ thống các độ đo sai số g1, g2, g3.
• Phân tích chi tiết cấu trúc giải thuật AFDMCEC, làm sáng tỏ cơ chế kết hợp giữa phủ tối thiểu và phân hoạch lớp tương đương để tối ưu không gian tìm kiếm.
• Chứng minh bằng toán học và thực nghiệm trên tập dữ liệu chuẩn UCI về ưu thế giảm độ phức tạp thời gian xử lý so với thuật toán TANE sửa đổi.
• Cung cấp giải pháp khoa học ứng dụng trực tiếp vào quy trình làm sạch dữ liệu, chuẩn hóa bảng và tối ưu hóa câu truy vấn cơ sở dữ liệu.
• Định hình lộ trình nghiên cứu mở rộng sang các kiến trúc tính toán phân tán và hệ thống cơ sở dữ liệu phi quan hệ trong thời gian 12 tháng tới.

Để áp dụng hiệu quả các kết quả nghiên cứu này vào các dự án phần mềm và quản trị dữ liệu thực tế, bạn có thể triển khai ngay thuật toán AFDMCEC nhằm nâng cao chất lượng dữ liệu và tối ưu hóa hiệu năng toàn diện cho hệ thống thông tin của mình.

Trích đoạn nội dung tài liệu

Đặt vấn đề Trong những năm gần đây, Công nghệ thông tin (CNTT) phát triển mạnh mẽ đã tác động đến mọi mặt của xã hội, những thành tựu của công nghệ lƣu trữ đã cho phép tạo ra những nguồn dữ liệu khổng lồ. Việc khai thác các nguồn dữ liệu này ngày càng cấp thiết, đặt ra những thách thức lớn cho ngành CNTT, đặc biệt là lĩnh vực khai phá dữ liệu. Với nguồn dữ liệu lớn nhƣ vậy thì việc tìm kiếm, phân tích, xử lý và đƣa ra các thông tin cần thiết, phù hợp với thời gian và yêu cầu là điều không dễ dàng. Các phƣơng pháp khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng đƣợc nhu cầu thực tế này.

Vì vậy các phƣơng pháp nghiên cứu, tiếp cận với những công cụ cho phép phân tích, tổng hợp, khai phá tri thức từ dữ liệu một cách thông minh, hiệu quả đã đƣợc nhiều nhà khoa học quan tâm nghiên cứu. Khái niệm phụ thuộc hàm đóng một vai trò rất quan trọng trong lý thuyết cơ sở dữ liệu quan hệ. Các phụ thuộc hàm rất hữu ích trong việc phân tích và thiết kế cơ sở dữ liệu quan hệ nhƣ xác định khóa, xác định các dạng chuẩn, các vấn đề về nhất quán dữ liệu. Tuy nhiên trong thực tế do có một số giá trị dữ liệu không chính xác hoặc một số ngoại lệ nào đó làm cho các phụ thuộc hàm không thỏa.

Sự phụ thuộc tuyệt đối này dƣờng nhƣ quá nghiêm ngặt khi ta hình dung tới một quan hệ có hàng nghìn bộ, trong khi đó chỉ có khoảng vài bộ vi phạm phụ thuộc hàm. Bỏ qua các phụ thuộc hàm này sẽ làm mất tính chất phụ thuộc vốn có giữa các thuộc tính. Vì vậy các nhà nghiên cứu đã mở rộng khái niệm phụ thuộc hàm thành phụ thuộc hàm xấp xỉ theo một cách thức, một nghĩa nào đó, các phụ thuộc hàm xấp xỉ (Approximate Functional Dependencies - AFDs) này cho phép có một số lƣợng lỗi nhất định của các bộ dữ liệu đối với phụ thuộc hàm. Phụ thuộc hàm xấp xỉ đƣợc khai phá từ CSDL quan hệ biểu diễn các mối Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 2 quan hệ có ý nghĩa, có nhiều ứng dụng khác nhau nhƣ: Dự đoán giá trị thiếu thuộc tính trong bảng quan hệ bằng cách sử dụng các giá trị của các thuộc tính trong việc xác định tập hợp các AFDs, tối ƣu hóa truy vấn, viết lại câu truy vấn, chuẩn hóa cơ sở dữ liệu để cho hiệu suất tốt hơn và thiết kế lƣu trữ hiệu quả hơn,… Luận văn sẽ tìm hiểu về phụ thuộc hàm xấp xỉ và nghiên cứu thuật toán AFDMCEC, một thuật toán mới tìm các phụ thuộc hàm xấp xỉ trong các CSDL lớn dựa trên độ đo xấp xỉ.

Thuật toán này sử dụng một số khái niệm trong lý thuyết thiết kế CSDL quan hệ, đặc biệt là các khái niệm phủ tối thiểu và lớp tƣơng đƣơng. Đối tƣợng và phạm vi nghiên cứu Luận văn tìm hiểu tổng quan về khai phá dữ liệu, đi sâu tìm hiểu khái niệm phụ thuộc hàm, phụ thuộc hàm xấp xỉ và các tính chất, độ đo lỗi của phụ thuộc hàm xấp xỉ, từ đó nghiên cứu thuật toán TANE sửa đổi và thuật toán AFDMCEC tìm phụ thuộc hàm xấp xỉ. Hƣớng nghiên cứu của đề tài - Tìm hiểu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ và các độ đo lỗi của chúng. - Nghiên cứu về thuật toán khai phá phụ thuộc hàm xấp xỉ từ bảng quan hệ.

Phƣơng pháp nghiên cứu Phƣơng pháp nghiên cứu chính của luận văn là nghiên cứu lý thuyết kết hợp với đánh giá thực nghiệm, cụ thể là: Phân tích, tổng hợp các kết quả nghiên cứu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ, … đã công bố trên các bài báo khoa học, hội thảo chuyên ngành trong và ngoài nƣớc. Từ đó, trình bày làm rõ vấn đề khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www. Ý nghĩa khoa học và thực tiễn Phụ thuộc hàm đóng vai trò quan trọng trong lý thuyết CSDL quan hệ.

Tuy nhiên, trong thực tế do có một số giá trị dữ liệu không chính xác hoặc một số ngoại lệ nào đó, làm cho các phụ thuộc hàm không thỏa mãn. Sự phụ thuộc tuyệt đối này dƣờng nhƣ quá nghiêm ngặt khi ta hình dung một quan hệ có hàng nghìn bộ, trong khi đó chỉ có vài bộ vi phạm phụ thuộc hàm. Do vậy, mở rộng khái niệm phụ thuộc hàm thành phụ thuộc hàm xấp xỉ, cho phép có một số lỗi nhất định của các bộ dữ liệu, là rất cần thiết và có ý nghĩa cả về mặt lý thuyết cũng nhƣ thực tiễn. Các phụ thuộc hàm xấp xỉ không những giúp chúng ta thấy đƣợc mối quan hệ tiềm ẩn giữa các thuộc tính mà còn giúp ta thuận tiện hơn trong việc phân tích dữ liệu, đánh giá thông tin.

Phát hiện phụ thuộc hàm xấp xỉ trong CSDL là một vấn đề nghiên cứu hấp dẫn và cũng là một trong những mục tiêu của phát hiện tri thức. Tiếp cận phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng của khai phá dữ liệu là một hƣớng đi thú vị, hứa hẹn nhiều kết quả và ứng dụng hiệu quả trong thực tiễn. Cấu trúc luận văn: Luận văn đƣợc trình bày trong 3 chƣơng: Chƣơng 1: Tổng quan về khai phá dữ liệu và khai phá phụ thuộc hàm, phụ thuộc hàm xấp xỉ. Chƣơng 2: Thuật toán khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng.

Chƣơng 3: Thực nghiệm khai phá phụ thuộc hàm xấp xỉ. Cuối cùng là kết luận của luận văn và tài liệu tham khảo. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 4 CHƢƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ PHỤ THUỘC HÀM, PHỤ THUỘC HÀM XẤP XỈ 1. Khai phá dữ liệu 1.

Khám phá tri thức và khai phá dữ liệu Khai phá dữ liệu (KPDL) là việc rút trích tri thức một cách tự động và hiệu quả từ một khối dữ liệu lớn. Tri thức đó thƣờng ở dạng các mẫu có tính chất không tầm thƣờng, không tƣờng minh (ẩn), chƣa đƣợc biết đến và có tiềm năng mang lại lợi ích. Có một số nhà nghiên cứu còn gọi KPDL là phát hiện tri thức từ cơ sở dữ liệu (Knowledge Discovery in Database – KDD). Ở đây chúng ta có thể coi KPDL là cốt lõi của quá trình phát hiện tri thức.

Quá trình phát hiện tri thức gồm các bƣớc: Bƣớc 1: Trích chọn dữ liệu (data selection): Là bƣớc trích chọn những tập dữ liệu cần đƣợc khai phá từ các tập dữ liệu lớn (databases, data ware houses). Bƣớc 2: Tiền xử lý dữ liệu (data preprocessing): Là bƣớc làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán,…v.v), rút gọn dữ liệu (sử dụng các phƣơng pháp thu gọn dữ liệu, histograms, lấy mẫu…v.v), rời rạc hóa dữ liệu (dựa vào histograms, entropy, phân khoảng,. Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và đƣợc rời rạc hóa. Bƣớc 3: Biến đổi dữ liệu (data transformation): Là bƣớc chuẩn hóa và làm mịn dữ liệu để đƣa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai thác ở bƣớc sau.

Bƣớc 4: Khai phá dữ liệu (data mining): Đây là bƣớc quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai phá (phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn đƣợc các mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 5 Bƣớc 5: Đánh giá và biểu diễn tri thức (knowledge representation & evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã đƣợc khai thác ở bƣớc trên biểu diễn theo dạng gần gũi với ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu, luật,…v. Đồng thời bƣớc này cũng đánh giá những tri thức khám phá đƣợc theo những tiêu chí nhất định. Trong giai đoạn khai phá dữ liệu, có thể cần sự tƣơng tác của ngƣời dùng để điều chỉnh và rút ra các tri thức cần thiết nhất.

Các tri thức nhận đƣợc cũng có thể đƣợc lƣu và sử dụng lại. Các Tri thức Các mẫu Dữ liệu đã sạch Dữ liệu đã chọn 5.Đánh giá và biểu diễn tri thức knowledge representation & evaluation 4.Khai phá dữ liệu Kho data mining dữ 3.Biến đổi dữ liệu liệu data transformation 2. Tiền xử lý dữ liệu data preprocessing 1. Trích chọn dữ liệu data selection Hình 1.

Quá trình khám phá tri thức Việc KPDL có thể đƣợc tiến hành trên một lƣợng lớn dữ liệu có trong CSDL, các kho dữ liệu hoặc trong các loại lƣu trữ thông tin khác. Các mẫu đáng quan tâm có thể đƣợc đƣa đến ngƣời dùng hoặc đƣợc lƣu trữ trong một cơ sở tri thức. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www. Kiến trúc của hệ thống khai phá dữ liệu Kiến trúc của một hệ thống KPDL điển hình có thể có các thành phần phần nhƣ hình 1.

- CSDL, kho dữ liệu hoặc các lƣu trữ thông tin khác (Databases, Data ware house,…): Đây là một hay một tập CSDL, các kho dữ liệu, các trang tính hay các dạng lƣu trữ thông tin khác. Các kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể đƣợc thực hiện trên những dữ liệu này. (Graphical user interface) Giao diện đồ họa cho ngƣời dùng (Pattern evaluation) Đánh giá mẫu Cơ sở dữ liệu (Data mining engine) Máy khai phá dữ liệu (Knowledge-base) (Database or Warehouse Server Máy chủ CSDL hay ho dữ liệu Làm sạch: Tích hợp dữ liệu, lọc Cơ sở dữ liệu Kho dữ liệu Các lƣu trữ thông tin khác Hình 1. Kiến trúc của hệ thống khai phá dữ liệu - Máy chủ CSDL hay máy chủ kho dữ liệu (Database or Warehouse Server): Máy chủ này có trách nhiệm lấy những dữ liệu tích hợp dựa trên các Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 7 yêu cầu khai phá của ngƣời dùng.

- Cơ sở tri thức (Knowledge-base): Đây là miền tri thức dùng để hƣớng dẫn việc tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết quả. - Máy KPDL (Data mining engine): Một hệ thống KPDL cần phải có một tập các modun chức năng để thực hiện công việc nhƣ: đặc trƣng hóa, kết hợp, phân lớp, phân cụm, phân tích sự tiến hóa. - Modun đánh giá mẫu (Pattern evaluation): Bộ phận này tƣơng tác với các modun KPDL để duyệt tìm các mẫu đáng đƣợc quan tâm. Nó có thể dùng các ngƣỡng về độ quan tâm để lọc mẫu đã khám phá đƣợc.