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, 2013 Thơng tin giảng viên Họ 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 Thông tin học phần Tên học phần Khai phá liệu Tên tiếng Anh Data Mining Mã học phần 17402 Số tín 02 tín Bộ mơn phụ trách Hệ thống thông tin PHƢƠNG PHÁP HỌC TẬP, NGHIÊN CỨU  Nghe giảng, thảo luận, trao đổi với giảng viên lớp  Tự nghiên cứu tài liệu làm tập nhà PHƢƠNG PHÁP ĐÁNH GIÁ  SV phải tham dự 75% thời gian  Có 02 kiểm tra viết học phần (X = X2 = (L1 + L2)/2)  Thi kết thúc học phần hình thức trắc nghiệm khách quan máy tính (Z = 0.3X + 0.7Y) Tài liệu tham khảo Jiawei Han and Micheline Kamber, Data Mining Concepts and Techniques, Elsevier Inc, 2006 Robert Nisbet, John Elder, Gary Miner, Handbook of Statistical Analysis and Data Mining Applications, Elsevier Inc, 2009 Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4th Edition), Pearson Education Inc, 2004 Hà Quang Thụy, Phan Xn Hiếu, Đồn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú, Giáo trình Khai phá liệu Web, NXB Giáo dục, 2009 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 0.1 NHU CẦU KHAI PHÁ DỮ LIỆU SỰ BÙNG NỔ THÔNG TIN!  Nhiều liệu đƣợc sinh thêm:  Web, văn bản, ảnh …  Giao dịch thương mại, gọi,  DL khoa học: thiên văn, sinh học …  Thêm nhiều liệu đƣợc nắm giữ:  Công nghệ lưu giữ nhanh rẻ  Hệ quản trị CSDL quản lý sở liệu với kích thước lớn  Vấn đề bùng nổ liệu  Các tiện ích thu thập liệu tự động công nghệ sở liệu lớn mạnh dẫn tới lượng lớn liệu tích lũy và/hoặc cần phân tích sở liệu, kho liệu nguồn chứa liệu khác  Chúng ta bị ngập lụt liệu mà khát tri thức!  Giải pháp: Kho liệu Khai phá liệu (mining)  Tạo lập kho liệu trình phân tích 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ừ liệu CSDL lớn 0.2 KHAI PHÁ DỮ LIỆU LÀ GÌ? Theo J.Han M.Kamber (2006) [1]: Quan niệm 1: Khai phá liệu (Data Mining) q trình trích chọn tri thức từ tập hợp lớn liệu Khai phá liệu = Phát tri thức từ liệu (KDD: Knowledge Discovery From Data) 10 0.5 CÁC GIAI ĐOẠN TRONG KHAI PHÁ DỮ LIỆU 23 Làm liệu (Data Cleaning): Loại bỏ nhiễu (noisy) liệu khơng qn Tích hợp liệu (Data Integration): Kết hợp liệu từ nguồn liệu khác Lựa chọn liệu (Data Selection): Dữ liệu phù hợp cho thao tác phân tích đƣợc lấy từ sở liệu Chuyển dạng liệu (Data Transformation): Dữ liệu đƣợc chuyển dạng hợp thành dạng phù hợp cho trình khai phá cách thực thao tác nhƣ tóm tắt (summary) gộp nhóm liệu (aggregation) Trích chọn mẫu (Data Patterns Extracting): Áp dụng phƣơng pháp “thông minh” để trích chọn mẫu thực đáng quan tâm từ liệu Đơi thân bƣớc đƣợc gọi khai phá liệu (Data Mining) (hiểu theo nghĩa hẹp) 24 Đánh giá mẫu (Pattern Evaluation): Dựa độ đo đặc trƣng, xác định mẫu đáng quan tâm biểu diễn tri thức Biểu diễn tri thức (Knowledge Presentation): Các kỹ thuật biểu diễn tri thức trực quan hóa (visualization) đƣợc sử dụng để biểu diễn tri thức khai phá đƣợc đến với ngƣời dùng Chú ý: Các giai đoạn từ đến gọi giai đoạn tiền xử lý liệu (data preprocessing) nhằm chuẩn bị liệu cho q trình khai phá (trích chọn mẫu) 25 0.6 KIẾN TRÚC ĐIỂN HÌNH CỦA MỘT HỆ THỐNG KHAI PHÁ DỮ LIỆU 26 Cơ sở liệu (Database), kho liệu (Data Warehouse), World Wide Web nguồn chứa thông tin khác:  Đây một nhóm sở liệu/kho liệu nguồn chứa thông tin (information repositories)  Các kỹ thuật làm liệu tích hợp liệu thực liệu Máy chủ sở liệu kho liệu (Database or Data Warehouse Server):  Chịu trách nhiệm lấy liệu phù hợp dựa yêu cầu khai phá người dùng Cơ sở tri thức (Knowledge Base):  Đây tri thức miền (domain knowledge) sử dụng để dẫn hướng trình tìm kiếm đánh giá độ hấp dẫn mẫu tìm thấy  Tri thức bao gồm phân cấp khái niệm (concept hierarchies) (được sử dụng để tổ chức thuộc tính giá trị thuộc tính thành mức trừu tượng khác nhau) 27 Engine khai phá liệu (Data Mining Engine):  Đây thành phần chủ yếu hệ thống KPDL  Bao gồm module thực tác vụ phân tích đặc trưng (characterization) quan hệ kết hợp (association/correlation analysis), phân lớp (classification), dự đốn (prediction), phân tích cụm (cluster analysis),… Module đánh giá mẫu (Pattern Evaluation Module):  Sử dụng độ đo hấp dẫn có tương tác với engine khai phá liệu nhằm tập trung vào việc tìm mẫu đáng quan tâm Có thể sử dụng ngưỡng độ hấp dẫn để lọc bớt mẫu tìm  Có thể tích hợp với module khai phá tùy thuộc vào phương pháp khai phá sử dụng cách thức cài đặt  Khuyến khích: Thao tác đánh giá mẫu cần tích hợp chặt chẽ tốt với tiến trình khai phá nhằm nâng cao hiệu khai phá (giới hạn việc tìm kiếm với mẫu đáng quan tâm) 28 Giao diện ngƣời sử dụng (User Interface): Module làm nhiệm vụ giao tiếp người dùng hệ thống KPDL:  Cho phép người dùng tương tác với hệ thống cách truy vấn tác vụ khai phá mong muốn  Cung cấp thơng tin giúp cho thao tác tìm kiếm tập trung  Thực khai phá thăm dò (Exploratory Data Mining) dựa kết khai phá trung gian  Cho phép người dùng duyệt sở liệu, lược đồ kho liệu cấu trúc liệu, đánh giá mẫu khai phá biểu diễn trực quan mẫu dạng thức khác 29 0.7 CÁC NGUỒN DỮ LIỆU PHỤC VỤ CHO KHAI PHÁ CƠ SỞ DỮ LIỆU QUAN HỆ (RELATIONAL DATABASE) 30 KHO DỮ LIỆU (DATA WAREHOUSE)  Là nơi tập trung liệu từ nhiều nguồn khác (multiple sources) lưu trữ lược đồ thống (unified shema) tập trung nơi  Được xây dựng thơng qua tiến trình làm liệu (data cleaning), tích hợp liệu (data integration), chuyển dạng liệu (data transformation), tải liệu (data loading) làm tươi liệu định kỳ (periodic data refreshing) 31 32  Để thuận tiện cho việc định, liệu kho liệu thường tổ chức xoay quanh chủ đề đáng quan tâm khách hàng (customer), hàng hóa (item), nhà cung cấp (supplier),…  Dữ liệu lưu trữ nhằm cung cấp thơng tin dựa nhìn tồn cảnh liệu tác nghiệp doanh nghiệp khoảng từ -10 năm thường tóm tắt (summarized) để thuận tiện cho xử lý  Kho liệu thường mơ hình hóa dạng cấu trúc sở liệu đa chiều (multidimensional database structure), chiều tương ứng với thuộc tính tập thuộc tích lược đồ (cell) lưu trữ giá trị số đại lượng gộp nhóm  Cấu trúc vật lý thực kho liệu dạng sở liệu quan hệ data cube đa chiều Một data cube cung cấp nhìn đa chiều liệu cho phép thực thao tác tiền tính tốn (precomputation) truy cập nhanh tới liệu tóm tắt 33 CƠ SỞ DỮ LIỆU GIAO DỊCH (TRANSACTION DATABASE)  Cơ sở liệu giao dịch tập hợp giao dịch Mỗi giao dịch bao gồm số hiệu giao dịch (trans_ID) danh sách mục (item) cấu thành giao dịch 34 Trans_ID Item List T1 Milk, Bread, Coke T2 Beer, Bread T3 Beer, Milk, Diaper, Coke T4 Beer, Milk, Diaper, Bread T5 Milk, Diaper, Coke CÁC DẠNG DỮ LIỆU NÂNG CAO  Dữ liệu văn bản: bao gồm dạng có cấu trúc, bán cấu trúc khơng có cấu trúc  Dữ liệu Multimedia: hình ảnh, âm thanh, video,…  Dữ liệu World Wide Web: liệu nội dung web, liệu cấu trúc web, liệu sử dụng web 35 0.6 ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU  Phân tích liệu hỗ trợ định  Phân tích quản lý thị trường  Tiếp thị định hướng, quản lý quan hệ khách hàng (CRM), phân tích thói quen mua hàng, bán hàng chéo, phân đoạn thị trường  Phân tích quản lý rủi ro  Dự báo, trì khách hàng, cải thiện bảo lãnh, kiểm soát chất lượng, phân tích cạnh tranh  Phát gian lận phát mẫu bất thường (ngoại lai)  Ứng dụng khác  Khai phá Text (nhóm mới, email, tài liệu) khai phá Web  Khai phá liệu dòng  Phân tích DNA liệu sinh học 36 Q&A 37 .. .Thông tin giảng viên Họ 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... Đồn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú, Giáo trình Khai phá liệu Web, NXB Giáo dục, 2009 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À... 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