Đặt vấn đề Ngày nay, con ngƣời đang sở hữu kho dữ liệu phong phú, đa dạng và khổng lồ. Đặc biệt sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin trong nhiều lĩnh vực đã làm cho kho dữ liệu ấy tăng lên nhanh chóng. Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tự động chuyển đổi lƣợng dữ liệu khổng lồ kia thành các tri thức có ích. Mặt khác, trong môi trƣờng cạnh tranh thì ngƣời ta ngày càng cần có thông tin với tốc độ nhanh để giúp cho việc ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả lời dựa trên khối lƣợng dữ liệu khổng lồ đã có.
Tiến hành các công việc nhƣ vậy chính là quá trình phát hiện tri thức trong cơ sở dữ liệu, trong đó kỹ thuật khai phá dữ liệu cho phép phát hiện tri thức tiềm ẩn ấy. Từ đó, các kỹ thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền Công nghệ thông tin thế giới hiện nay nói chung và Việt Nam nói riêng. Rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và thu đƣợc những lợi ích to lớn. Các kỹ thuật phát hiện tri thức và khai phá dữ liệu đƣợc thực hiện qua nhiều giai đoạn và sử dụng nhiều kỹ thuật: phân lớp (classification), phân cụm (clustering), phân tích sự tƣơng tự (similarity analysis), tổng hợp (summarization), luật kết hợp (association rules), … Một trong những nội dung cơ bản và phổ biến trong khai phá dữ liệu là phát hiện các luật kết hợp.
Phƣơng pháp này nhằm tìm ra các tập thuộc tính thƣờng xuất hiện đồng thời trong cơ sở dữ liệu và rút ra các luật về ảnh hƣởng của một tập thuộc tính dẫn đến sự xuất hiện của một hoặc nhiều tập thuộc tính khác nhƣ thế nào? Do đó việc phát hiện ra các luật kết hợp là một bƣớc rất quan trọng trong khai phá dữ liệu. Mặt khác, hiện nay nhu cầu song song hóa và xử lý phân tán là rất cần thiết bởi kích thƣớc dữ liệu lƣu trữ ngày càng lớn nên đòi hỏi tốc độ xử lý cũng nhƣ dung lƣợng bộ nhớ hệ thống phải đảm bảo. Vì vậy, yêu cầu cần có những thuật toán song song hiệu quả cho việc phát hiện các luật kết hợp trong khai phá dữ liệu là rất cần thiết, góp phần thúc đẩy khả năng ứng dụng của việc phát hiện tri thức, hỗ trợ ra quyết định vào trong hoạt động thực tiễn. Từ những vấn đề nêu trên, tôi chọn đề tài “Nghiên cứu các luật kết hợp song song trong khai phá dữ liệu” để làm luận văn tốt nghiệp.
Mục tiêu của luận văn Tìm hiểu khái quát về khai phá dữ liệu trong đó đi sâu về các luật kết hợp. Tìm hiểu một số mô hình tính toán song song. z 2 Nghiên cứu xây dựng các thuật toán luật kết hợp song song trong khai phá dữ liệu. Cài đặt một số thuật toán song song khai phá dữ liệu và phát hiện luật kết hợp.
Bố cục của luận văn Luận văn chia làm 3 chƣơng: Chƣơng 1: Tổng quan về khai phá dữ liệu Chƣơng này giới thiệu quá trình khai phá dữ liệu và phát hiện tri thức, phƣơng pháp khai phá dữ liệu, ứng dụng và một số khó khăn trong khai phá dữ liệu. Chƣơng 2: Khai phá các luật kết hợp song song Chƣơng này trình bày tóm tắt luật kết hợp, mô hình của bài toán khai phá luật kết hợp, các khái niệm cơ bản luật kết hợp, các phƣơng pháp khai phá các luật kết hợp và khai phá các luật kết hợp song song. Chƣơng 3: Cài đặt thuật toán khai phá các luật kết hợp song song ứng dụng cho bài toán khai phá dữ liệu. z 3 CHƢƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.
Khai phá dữ liệu 1. Khái niệm Khai phá dữ liệu Khai phá dữ liệu (Data Mining) là một khái niệm ra đời vào những năm cuối của thập kỷ 1980. Nó là quá trình khám phá thông tin ẩn đƣợc tìm thấy trong các cơ sở dữ liệu và có thể xem nhƣ là một bƣớc trong quá trình khám phá tri thức. Data Mining là giai đoạn quan trọng nhất trong tiến trình khai phá tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh, … Giáo sƣ Tom Mitchell [20] đã đƣa ra định nghĩa của Khai phá dữ liệu nhƣ sau: ―Khai phá dữ liệu là việc sử dụng dữ liệu lịch sử để khám phá những qui tắc và cải thiện những quyết định trong tƣơng lai.‖ Với một cách tiếp cận ứng dụng hơn, Tiến sĩ Fayyad [21] đã phát biểu: ―Khai phá dữ liệu, thƣờng đƣợc xem là việc khám phá tri thức trong các cơ sở dữ liệu, là một quá trình trích xuất những thông tin ẩn, trƣớc đây chƣa biết và có khả năng hữu ích, dƣới dạng các qui luật, ràng buộc, qui tắc trong cơ sở dữ liệu.‖ hay nói cách khác ―Khai phá dữ liệu – Data Mining là tiến trình khám phá tri thức tiềm ẩn trong các cơ sở dữ liệu.
Cụ thể hơn, đó là tiến trình trích lọc, sản sinh những tri thức hoặc các mẫu tiềm ẩn, chƣa biết nhƣng hữu ích từ cơ sở dữ liệu lớn‖ [2]. Nói tóm lại, Khai phá dữ liệu là một quá trình học tri thức mới từ những dữ liệu đã thu thập đƣợc [8]–[12]–[15]. Khai phá dữ liệu là tiến trình khái quát các sự kiện rời rạc trong dữ liệu thành các tri thức mang tính khái quát, tính quy luật hỗ trợ tích cực cho các tiến trình ra quyết định. Khai phá dữ liệu là việc trích rút tri thức một cách tự động và hiệu quả từ một khối dữ liệu rất lớn.
Tri thức đó thƣờng ở dạng các mẫu tin 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. Để hình dung vấn đề này ta có thể sử dụng một ví dụ đơn giản nhƣ sau: Khai phá dữ liệu đƣợc ví nhƣ tìm một cây kim trong đống cỏ khô. Trong ví dụ này, cây kim là một mảnh nhỏ tri thức hoặc một thông tin có giá trị và đống cỏ khô là một kho cơ sở dữ liệu rộng lớn. Nhƣ vậy, những thông tin có giá trị tiềm ẩn trong kho cơ sở dữ liệu sẽ đƣợc chiết xuất ra và sử dụng một cách hữu ích nhờ khai phá dữ liệu.
Chức năng khai phá dữ liệu gồm có gộp nhóm phân loại, dự báo, dự đoán và phân tích các liên kết. Năm 1989, Fayyad, Smyth và Piatestsky-Shapiro đã dùng khái niệm Phát hiện tri thức từ cơ sở dữ liệu (Knowledge Discovery in Database-KDD). Trong đó, khai phá dữ liệu là một giai đoạn rất đặc biệt trong toàn bộ quá trình, nó sử dụng các kỹ thuật để tìm ra các mẫu từ dữ liệu. Có thể coi khai phá dữ liệu là cốt lõi của quá trình phát hiện tri thức.
Quá trình khai phá dữ liệu sẽ tiến hành qua 6 giai đoạn nhƣ hình 1. 1 [7] z 4 Đánh giá mẫu Khai phá dữ liệu Data Mining Chuyển đổi dữ liệu Làm sạch, Tiền xử lý Chuẩn bị trƣớc dữ TRI THỨC liệu Lựa chọn dữ liệu Gom dữ liệu Internet,. Dữ liệu Hình 1. Quá trình khai phá dữ liệu Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức đƣợc chiết xuất ra.
Về lý thuyết thì có vẽ rất đơn giản nhƣng thực sự đây là một quá trình rất khó khăn gặp phải rất nhiều vƣớng mắc nhƣ: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình, … 1. Gom dữ liệu (Gathering): Tập hợp dữ liệu là bƣớc đầu tiên trong quá trình khai phá dữ liệu. Đây là bƣớc đƣợc khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. Trích lọc dữ liệu (Selection): Ở giai đoạn này dữ liệu đƣợc lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó, ví dụ chọn tất cả những ngƣời có tuổi đời từ 25 – 35 và có trình độ đại học.
Làm sạch, tiền xử lý và chuẩn bị trƣớc dữ liệu (Cleaning, Pre-processing and Preparation): Giai đoan thứ ba này là giai đoạn hay bị sao lãng, nhƣng thực tế nó là một bƣớc rất quan trọng trong quá trình khai phá dữ liệu. Một số z 5 lỗi thƣờng mắc phải trong khi gom dữ liệu là tính không đủ chặt chẽ, logíc. Vì vậy, dữ liệu thƣờng chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên.
Những dữ liệu dạng này đƣợc xem nhƣ thông tin dƣ thừa, không có giá trị. Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không đƣợc ―làm sạch - tiền xử lý - chuẩn bị trƣớc‖ thì sẽ gây nên những kết quả sai lệch nghiêm trọng. Chuyển đổi dữ liệu (Transformation): Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đƣa ra có thể sử dụng và điều khiển đƣợc bởi việc tổ chức lại nó. Dữ liệu đã đƣợc chuyển đổi phù hợp với mục đích khai thác.
Phát hiện và trích mẫu dữ liệu (Pattern Extraction and Discovery): Đây là bƣớc mang tính tƣ duy trong khai phá dữ liệu. Ở giai đoạn này nhiều thuật toán khác nhau đã đƣợc sử dụng để trích ra các mẫu từ dữ liệu. Thuật toán thƣờng dùng là nguyên tắc phân loại, nguyên tắc kết hợp hoặc các mô hình dữ liệu tuần tự, … 6. Đánh giá kết quả mẫu (Evaluation of Result): Đây là giai đoạn cuối trong quá trình khai phá dữ liệu.
Ở giai đoạn này, các mẫu dữ liệu đƣợc chiết xuất ra bởi phần mềm khai phá dữ liệu. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần phải ƣu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức (Knowledge). Trên đây là 6 giai đoạn trong quá trình khai phá dữ liệu, trong đó giai đoạn 5 là giai đoạn đƣợc quan tâm nhiều nhất, đó là khai phá dữ liệu.
Kiến trúc của một hệ thống khai phá dữ liệu Máy chủ cơ sở dữ liệu hay máy chủ kho dữ liệu (Database or warehouse server): Máy chủ này có trách nhiệm lấy dữ liệu thích hợp dựa trên những 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 đƣợc dùng để tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết quả.