LỜI MỞ ĐẦU Ngày nay, cuộc cách mạng của kỹ thuật số cho phép số hóa thông tin dễ dàng và chi phí lƣu trữ thấp.Với sự phát triển của phần mềm, phần cứng và trang bị nhanh hệ thống máy tính trong kinh doanh. Số lƣợng dữ liệu khổng lồ đƣợc tập trung và lƣu trữ trong cơ sở dữ liệu trên các thiết bị điện tử nhƣ: đĩa cứng, băng từ, đĩa quang,… Tốc độ tăng dữ liệu quá lớn. Từ đó dẫn đến kết quả là sự pha trộn của kỹ thuật thống kê vào các công cụ quản trị dữ liệu không thể phân tích đầy đủ dữ liệu rộng lớn đƣợc nữa. Dữ liệu sau khi phục vụ cho một mục đích nào đó đƣợc lƣu lại trong kho dữ liệu và theo ngày tháng khối lƣợng dữ liệu đƣợc lƣu trữ ngày càng lớn.
Trong khối lƣợng dữ liệu to lớn này có rất nhiều thông tin có ích mang tính tổng quát, thông tin có tính quy luật vẫn còn đang tiềm ẩn mà chúng ta chƣa biết. Từ khối lƣợng dữ liệu rất lớn cần có những công cụ tự động rút các thông tin và kiến thức có ích. Một hƣớng tiếp cận có khả năng giúp các công ty khai thác các thông tin có nhiều ý nghĩa từ các tập dữ liệu lớn đó là khai phá dữ liệu (Data Mining). Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều hiệu quả đối với khoa học cũng nhƣ các hoạt động thực tế, trong đó khai phá dữ liệu là một trong những lĩnh vực mang lại hiệu quả thiết thực cho con ngƣời.
KPDL đã giúp ngƣời sử dụng thu đƣợc những tri thức hữu ích từ những cớ sở dữ liệu hoặc các kho dữ liệu khổng lồ khác. Đề tài đề cập đến các khái niệm và vấn đề cơ bản trong KPTT và KPDL, ngoài ra Đề tài còn đề cập đến một số phƣơng pháp khai phá dữ liệu dạng đóng đƣợc áp dụng trong nhiều lĩnh vực thực tiễn. Cấu trúc đồ án: Chƣơng 1 giới thiệu tổng quan về KPTT và KPDL. Chƣơng 2 Tìm hiểu phƣơng pháp khai phá tập phổ biến.
Chƣơng 3 Tìm hiểu phƣơng pháp khai phá tập phổ biến đóng trong không gian. Chƣơng 4 Cài đặt chƣơng trình thử nghiệm. TÀI LIỆU THAM KHẢO. 6 CHƢƠNG 1: TỔNG QUAN VỀ KPTT VÀ KPDL.1 Giới thiệu chung về khai phá tri thức và khai phá dữ liệu.
- Nếu cho rằng, điện tử và truyền thông chính là bản chất của khoa học điện tử, thì dữ liệu, thông tin, và tri thức hiện đang là tiêu điểm của một lĩnh vực mới để nghiên cứu và ứng dụng, đó là khai phá tri thức và khai phá dữ liệu. - Thông thƣờng, chúng ta coi dữ liệu nhƣ là một chuỗi các bits, hoặc các số và các ký hiệu hay là các “đối tƣợng” với một ý nghĩa nào đó khi đƣợc gửi cho một chƣơng trình dƣới một dạng nhất định. Các bits thƣờng đƣợc sử dụng để đo thông tin, và xem nó nhƣ là dữ liệu đã đƣợc loại bỏ phần tử thừa, lặp lại, và rút gọn tới mức tối thiểu để đặc trƣng một cách cơ bản cho dữ liệu. Tri thức đƣợc xem nhƣ là các thông tin tích hợp, bao gồm các sự kiện và mối quan hệ giữa chúng, đã đƣợc nhận thức, khám phá, hoặc nghiên cứu.
Nói cách khác, tri thức có thể đƣợc coi là dữ liệu ở mức độ cao của sự trừu tƣợng và tổng quát. - Khái phá tri thức hay phát hiện tri thức trong CSDL là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng hợp, hợp thức, khả ích và có thể hiểu đƣợc. - Khai phá dữ liệu là một bƣớc trong quá trình khám phá tri thức, gồm các thuật toán khai thác dữ liệu chuyên dùng dƣới một số qui định về hiệu quả tính toán chấp nhận đƣợc để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói cách khác, mục tiêu của Khai phá dữ liệu là tìm kiếm các mẫu hoặc mô hình tồn tại trong CSDL nhƣng ẩn trong khối lƣợng lớn dữ liệu.2 Quá trình khai phá tri thức.
Bao gồm các bƣớc sau: - Làm sạch dữ liệu (Data Cleaning): Loại bỏ dữ liệu nhiễu và dữ liệu không nhất quán. - Tích hợp dữ liệu (Data Intergation): Dữ liệu của nhiều nguồn có thể đƣợc tổ hợp lại. - Lựa chọn dữ liệu (Data Selection): Lựa chọn những dữ liệu phù hợp với nhiệm vụ phân tích trích rút từ cơ sở dữ liệu. - Chuyển đổi dữ liệu (Data Transformation): Dữ liệu đƣợc chuyển đổi hay đƣợc hợp nhất về dạng thích hợp cho việc khai phá.
- Khai phá dữ liệu (Data Mining): Đây là một tiến trình cốt yếu trong đó các phƣơng pháp thông minh đƣợc áp dụng nhằm trích rút ra mẫu dữ liệu. - Đánh giá mẫu (Pattern Evaluation): Dựa trên một độ đo nào đó xác định lợi ích thực sự, độ quan trọng của các mẫu biểu diễn tri thức. - Biểu diễn tri thức (Knowledge Presentation): Ở giai đoạn này các kỹ thuật biểu diễn và hiển thị đƣợc sử dụng để đƣa tri thức lấy ra cho ngƣời dùng.1: Quá trình KPTT.3 Quá trình khai thác dữ liệu. - KPDL là một giai đoạn quan trọng trong quá trình KPTT.
Về bản chất, nó là giai đoạn duy nhất tìm ra đƣợc thông tin mới, thông tin tiềm ẩn có trong CSDL chủ yếu phục vụ cho mô tả và dự đoán. - Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu mà con ngƣời có thể hiểu đƣợc. - Dự đoán là dựa trên những dữ liệu hiện thời để dự đoán những quy luật đƣợc phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu trên cơ sở đó chiết xuất ra các mẫu, dự đoán đƣợc những giá trị chƣa biết hoặc những giá trị tƣơng lai của các biến quan tâm. Quá trình KPDL bao gồm các bƣớc chính đƣợc thể hiện nhƣ Hình 1.2: Quá trình KPDL.
Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết. Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp. Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền xử lý chúng sao cho thuật toán KPDL có thể hiểu đƣợc. Đây là một quá trình rất khó.
8 khăn, có thể gặp phải rất nhiều các vƣớng mắc nhƣ: dữ liệu phải đƣợc sao ra nhiều bản (nếu đƣợc chiết xuất vào các tệp), quản lý tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi), vv. Thuật toán khai phá dữ liệu: Lựa chọn thuật toán KPDL và thực hiện việc PKDL để tìm đƣợc các mẫu có ý nghĩa, các mẫu này đƣợc biểu diễn dƣới dạng luật kết hợp, cây quyết định. tƣơng ứng với ý nghĩa của nó.4 Các phƣơng pháp khai phá dữ liệu. Với hai mục đích khai phá dữ liệu là Mô tả và Dự đoán, ngƣời ta thƣờng sử dụng các phƣơng pháp sau cho khai phá dữ liệu: Luật kết hợp (association rules) Phân lớp (Classfication) Hồi qui (Regression) Trực quan hóa (Visualiztion) Phân cụm (Clustering) Tổng hợp (Summarization) Mô hình ràng buộc (Dependency modeling) Biểu diễn mô hình (Model Evaluation) Phân tích sự phát triển và độ lệch (Evolution and deviation analyst) Phƣơng pháp tìm kiếm (Search Method) Tập phổ biến đóng(Frequent Closed Patterns) Có nhiều phƣơng pháp khai phá dữ liệu đƣợc nghiên cứu ở trên, trong đó có ba phƣơng pháp đƣợc các nhà nghiên cứu sử dụng nhiều nhất đó là: Luật kết hợp, Phân lớp dữ liệu và Phân cụm dữ liệu.5 Các lĩnh vực ứng dụng thực tiễn của khai phá dữ liệu.3: Các lĩnh vực ứng dụng KPDL.6 Các hƣớng tiếp cận trong khai phá dữ liệu.
Các hƣớng tiếp cận của KPDL có thể đƣợc phân chia theo chức năng hay lớp các bài toán khác nhau. Sau đây là một số hƣớng tiếp cận chính. Phân lớp và dự đoán (classification & prediction): xếp một đối tƣợng vào một trong những lớp đã biết trƣớc. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết.
Hƣớng tiếp cận này thƣờng sử dụng một số kỹ thuật của machine learning. 9 nhƣ cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network),. Phân lớp còn đƣợc gọi là học có giám sát (học có thầy supervised learning). Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ ở dạng khá đơn giản.
Ví dụ: “60 % nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua thêm thịt bò khô”. Luật kết hợp đƣợc ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính & thị trƣờng chứng khoán,. Khai phá chuỗi theo thời gian (sequential/temporal patterns): tƣơng tự nhƣ khai phá luật kết hợp nhƣng có thêm tính thứ tự và tính thời gian. Hƣớng tiếp cận này đƣợc ứng dụng nhiều trong lĩnh vực tài chính và thị trƣờng chứng khoán vì nó có tính dự báo cao.
Phân cụm (clustering/segmentation): xếp các đối tƣợng theo từng cụm (số lƣợng cũng nhƣ tên của cụm chƣa đƣợc biết trƣớc. Phân cụm còn đƣợc gọi là học không giám sát (học không có thầy – unsupervised learning). Mô tả khái niệm (concept description & summarization): thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản.
Khai phá tập phổ biến (mining frequent pattern): thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản.7 Phân loại các hệ khai phá dữ liệu. - KPDL là một công nghệ tri thức liên quan đến nhiều lĩnh vực nghiên cứu khác nhau nhƣ CSDL, kỹ thuật máy học (machine learning), giải thuật, trực quan hóa (visualization),. Chúng ta có thể phân loại các hệ thống KPDL dựa trên các tiêu chí khác nhau.
- Phân loại dựa trên kiểu dữ liệu đƣợc khai phá: CSDL quan hệ (relational database), kho dữ liệu (data warehouse), CSDL giao dịch (transactional database), CSDL hƣớng đối tƣợng, CSDL không gian (spatial database), CSDL đa phƣơng tiện (multimedia database), CSDL Text và WWW,. - Phân loại dựa trên dạng tri thức đƣợc khám phá: tóm tắt và mô tả (summarization & description), luật kết hợp (association rules), phân lớp (classification), phân cụm (clustering), khai phá chuỗi (sequential mining),. - Phân loại dựa trên kỹ thuật đƣợc áp dụng: hƣớng CSDL (database-oriented), phân tích trực tuyến (OnLine Analytical Processing – OLAP), machine learning (cây quyết định, mạng nơ ron nhân tạo, k-min, giải thuật di truyền, máy vectơ hỗ trợ - SVM, tập thô, tập mờ,. - Phân loại dựa trên lĩnh vực đƣợc áp dụng: kinh doanh bán lẻ (retail), truyền thông (telecommunication), tin-sinh (bio-informatics), y học (medical treatment), tài chính & thị trƣờng chứng khoán (finance & stock market), Web mining, .8 Các thách thức - khó khăn trong KPTT và KPDL.