Bài giảng môn học Khai phá dữ liệu: Bài mở đầu - ThS. Nguyễn Vương Thịnh

Bài giảng môn học Khai phá dữ liệu: Bài mở đầu - Tổng quan về khai phá dữ liệu trình bày về nhu cầu khai phá dữ liệu, khái niệm về dữ liệu; mẫu; tri thức và khai phá dữ liệu, các bài toán khai phá dữ liệu cơ bản, các giai đoạn trong khai phá dữ liệu, kiến trúc điển hình của một hệ thống khai phá dữ liệu, các nguồn dữ liệu phục vụ cho khai phá và ứng dụng của khai phá dữ liệu.
Nội dung trích xuất từ tài liệu:
Bài giảng môn học Khai phá dữ liệu: Bài mở đầu - ThS. Nguyễn Vương Thịnh TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG MÔN HỌC KHAI PHÁ DỮ LIỆU BÀI MỞ ĐẦU TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Giảng viên: ThS. Nguyễn Vương Thịnh Bộ môn: Hệ thống thông tin Hải Phòng, 2011 Thông tin về giảng viên Họ và tên Nguyễn Vương Thịnh Đơn vị công tác Bộ môn Hệ thống thông tin – Khoa Công nghệ thông tin Học vị Thạc sỹ Chuyên ngành Hệ thống thông tin Cơ sở đào tạo Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội Năm tốt nghiệp 2012 Điện thoại 0983283791 Email thinhnv@vimaru.edu.vn 2 Tài liệu tham khảo 1. Jiawei Han and Micheline Kamber, Data Mining Concepts and Techniques, Elsevier Inc, 2006. 2. Robert Nisbet, John Elder, Gary Miner, Handbook of Statistical Analysis and Data Mining Applications, Elsevier Inc, 2009. 3. Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4th Edition), Pearson Education Inc, 2004. 4. Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú, Giáo trình Khai phá dữ liệu Web, NXB Giáo dục, 2009. 3 4 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 0.1. NHU CẦU KHAI PHÁ DỮ LIỆU 0.2. KHAI PHÁ DỮ LIỆU LÀ GÌ? 0.3. KHÁI NIỆM VỀ DỮ LIỆU, MẪU VÀ TRI THỨC 0.4. CÁC BÀI TOÁN KHAI PHÁ DỮ LIỆU CƠ BẢN 0.5. CÁC GIAI ĐOẠN TRONG KHAI PHÁ DỮ LIỆU 0.6. KIẾN TRÚC ĐIỂN HÌNH CỦA MỘT HỆ THỐNG KPDL 0.7. CÁC NGUỒN DỮ LIỆU PHỤC VỤ CHO KHAI PHÁ 0.8. ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU 5 0.1. NHU CẦU KHAI PHÁ DỮ LIỆU SỰ BÙNG NỔ THÔNG TIN!  Nhiều dữ liệu được sinh thêm:  Web, văn bản, ảnh …  Giao dịch thương mại, cuộc gọi, ...  DL khoa học: thiên văn, sinh học …  Thêm nhiều dữ liệu được nắm giữ:  Công nghệ lưu giữ nhanh hơn và rẻ hơn.  Hệ quản trị CSDL có thể quản lý các cơ sở dữ liệu với kích thước lớn hơn. 6 7  Vấn đề bùng nổ dữ liệu  Các tiện ích thu thập dữ liệu tự động và công nghệ cơ sở dữ liệu lớn mạnh dẫn tới một lượng lớn dữ liệu được tích lũy và/hoặc cần được phân tích trong cơ sở dữ liệu, kho dữ liệu và trong các nguồn chứa dữ liệu khác.  Chúng ta bị ngập lụt trong dữ liệu mà khát tri thức!  Giải pháp: Kho dữ liệu và Khai phá dữ liệu (mining)  Tạo lập kho dữ liệu và quá trình phân tích dữ liệu trực tuyến OLAP.  Khai phá tri thức hấp dẫn (luật, quy luật, mẫu, ràng buộc) từ dữ liệu 8 trong CSDL lớn. 0.2. KHAI PHÁ DỮ LIỆU LÀ GÌ? Theo J.Han và M.Kamber (2006) [1]: Quan niệm 1: Khai phá dữ liệu (Data Mining) là quá trình trích chọn ra tri thức từ trong một tập hợp rất lớn dữ liệu. Khai phá dữ liệu = Phát hiện tri thức từ dữ liệu (KDD: Knowledge Discovery From Data). 9 Quan niệm 2: Khai phá dữ liệu (Data Mining) chỉ là một bước quan trọng trong quá trình phát hiên tri thức từ dữ liệu (KDD). Áp dụng các phương pháp “thông minh” để trích chọn ra các mẫu dữ liệu (data pattern). 10 Theo Hà Quang Thụy và các tác giả (2009) [4] (trang 11 và 16): Khái niệm 1: Phát hiện tri thức trong cơ sở dữ liệu (đôi khi còn được gọi là khai phá dữ liệu) là một quá trình không tầm thường nhằm phát hiện ra những mẫu có giá trị, mới, hữu ích tiềm năng và có thể thể hiểu được từ dữ liệu. Khái niệm 2: Khai phá dữ liệu là một bước trong quá trình phát hiện tri thức trong cơ sở dữ liệu, thi hành một thuật toán khai phá dữ liệu để tìm ra các mẫu từ dữ liệu theo khuôn dạng thích hợp 11 0.3. KHÁI NIỆM VỀ DỮ LIỆU, MẪU VÀ TRI THỨC A. Khái niệm về dữ liệu và mẫu  Dữ liệu (tập dữ liệu)  Là một tập F gồm hữu hạn các trường hợp (sự kiện).  Trong khai phá dữ liệu, tập dữ liệu F thường phải gồm rất nhiều trường hợp.  Mẫu  Trong quá trình khai phá, người ta sử dụng ngôn ngữ L để biểu diễn các tập con các sự kiện (dữ liệu) thuộc vào tập sự kiện F.  Mỗi biểu thức E trong ngôn ngữ L biểu diễn tập con FE tương ứng các sự kiện trong F. ⟹ E được gọi là mẫu nếu nó đơn giản hơn so với việc liệt kê các sự kiện thuộc FE. Ví dụ: Mẫu “Thu nhập < T” 12 B. Tính có giá trị của mẫu  Mẫu được phát hiện phải có giá trị đối với các dữ liệu mới (xuất hiện trong tương lai) theo một mức độ chân thực nào đấy.  Tính có giá trị: một độ đo tính có giá trị (chân thực) là một hàm C ánh xạ một biểu thức thuộc ngôn ngữ biểu diễn mẫu L tới một không gian đo được (bộ phận hoặc toàn bộ) MC. Một biểu thức E trong L biểu diễn một tập con FE ⊂ F có thể được gán một độ đo chân thực c = C(E,F). Với mẫu THUNHẬP < $t”: đường biên xác định mẫu dịch sang phải (biến THUNHẬP nhận giá trị lớn hơn) thì độ chân thực giảm xuống do bao gói thêm các tình huống vay tốt lại bị đưa vào vùng không cho vay nợ. Với mẫu “a*THUNHẬP + b*NỢ < 0”: tình trạng người vay nợ rơi vào tình trạng không thể chi trả tương ứng với nửa mặt phẳng trên ⟹ cho độ chân thực cao hơn. 13 C. Tính mới và hữu dụng tiềm năng Tính mới: Mẫu phải là mới trong một miền xem xét nào đó, ít nhất là hệ thống đang được xem xét. Tính mới có thể đo được khi quan tâm tới sự thay đổi trong:  Dữ liệu: so sánh giá trị hiện tại với giá trị quá khứ hoặc giá trị kỳ vọng  Tri thức: tri thức mới quan hệ như thế nào với các tri thức đã có. ⟹Tổng quát, điều này có thể được đo bằng một hàm N(E,F) hoặc là độ đo về tính mới hoặc là độ đo kỳ vọng. Hữu dụng tiềm n ...