Đặ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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Ý 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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ả.