Bài giảng Khai phá dữ liệu - Chương 1: Khái quát về khai phá dữ liệu

Chia sẻ: Nguyễn Thị Hiền Phúc | Ngày: | Loại File: PPTX | Số trang:41

Thêm vào BST

Báo xấu

88
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng cung cấp cho người học các kiến thức: Tổng quan về khai phá dữ liệu. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Khai phá dữ liệu - Chương 1: Khái quát về khai phá dữ liệu

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 CH ƯƠN G 1 : T ỔN G Q UA N V Ề K HA I P HÁ D Ữ LIỆU Gi ản g v iê n : Th S . N g u y ễn V ươn g Th ịn h B ộ m ô n : H ệ t h ốn g t h ô n g t in H ải P h ò n g ,
Th ô n g t in v ề g i ản g v iê 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 Website cá nhân http://scholar.vimaru.edu.vn/thinhnv 2
Th ô n g t in v ề h ọc p h ần Tên học phần Khai phá dữ liệu Tên tiếng Anh Data Mining Mã học phần 17409 Số tín chỉ 03 tín chỉ Số tiết lý thuyết 39 tiết (13 tuần x 03 tiết/tuần) Số tiết thực hành 10 tiết (05 tuần x 02 tiết/tuầ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 v N g h e g i ản g , t h ảo lu ận , t ra o đ ổi v ới g i ản g v iê n t rê n l ớp . P H ƯƠTNựG P n g HÁP h iê n Đ c ứ ÁNu tH GIÁ à i li ệu v à là m b à i t ập ở n h à . v v S V p h ải t h a m d ự ít n h ất 7 5 % t h ời g ia n . v Có 0 2 b à i k i ểm t ra v i ết g i ữa h ọc p h ần ( X = X2 = ( L1 + L2 ) /2 ) . 3 v Th i k ết t h ú c h ọc p h ần b ằn g h ìn h t h ức t r ắc n g h i ệm k h á c h q u a n t rê n m á y t ín h ( Z = 0 . 5 X + 0 . 5 Y) .
Tài liệu tham khảo 1. Jiawei Han and Micheline Kamber, D a t a Min in g Co n c e p t s a n d Te c h n iq u e s , Elsevier Inc, 2006. 2. Ian H. Witten, Eibe Frank, D a t a Min in g – P ra c t ic a l Ma c h in e Le a rn in g To o ls a n d Te c h n iq u e s ( t h e s e c o n d e d it io n ) , Elsevier Inc, 2005 (sử dụng kèm với công cụ Weka). 3. Elmasri, Navathe, Somayajulu, Gupta, Fu n d a m e n t a ls o f D a t a b a s e S y s t e m s ( t h e 4 t h Ed it io n ) , 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 t rìn h Kh a i p h á d ữ li ệu We b , NXB Giáo dục, 2009 4
5
Cô n g c ụ p h ần m ềm h ỗ t rợ Phần mềm Weka được phát triển bởi nhóm nghiên cứu của trường Đại học Waikato (New Zealand) từ năm 1999. Có thể download về tại địa chỉ: http://www.cs.waikato.ac.nz/ml/weka/downloading.html 6
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1. NHU CẦU KHAI PHÁ DỮ LIỆU 1.2. KHAI PHÁ DỮ LIỆU LÀ GÌ? 1.3. KHÁI NIỆM VỀ DỮ LIỆU, MẪU VÀ TRI THỨC 1.4. CÁC BÀI TOÁN KHAI PHÁ DỮ LIỆU CƠ BẢN 1.5. CÁC GIAI ĐOẠN TRONG KHAI PHÁ DỮ LIỆU 1.6. KIẾN TRÚC ĐIỂN HÌNH CỦA MỘT HỆ THỐNG KPDL 1.7. CÁC NGUỒN DỮ LIỆU PHỤC VỤ CHO KHAI PHÁ 1.8. ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU 7
1.1. NHU CẦU KHAI PHÁ DỮ LIỆU SỰ BÙNG NỔ THÔNG TIN !  N h i ều d ữ li ệu đ ược s in h t h ê m : v Web, văn bản, ảnh … v Giao dịch thương mại, cuộc gọi, ... v DL khoa học: thiên văn, sinh học …  Th ê m n h i ều d ữ li ệu đ ược n ắm g i ữ: v Công nghệ lưu giữ nhanh hơn và rẻ hơn. v 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. 8
9
10
 Vấn đề bùng nổ dữ liệu v 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) v Tạo lập kho dữ liệu và quá trình phân tích dữ liệu trực tuyến OLAP. v Khai phá tri thức hấp dẫn (luật, quy luật, mẫu, ràng buộc) từ dữ liệu 11 trong CSDL lớn.
12
1 . 2 . KHAI P HÁ 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). 13
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). 14
Th e o Hà Q u a n g Th ụy v à c á c t á c g i ả ( 2 0 0 9 ) [ 4 ] ( t ra n g 1 1 v à 1 6 ) : K h á i n i ệm 1 : P h á t h i ện t ri t h ức t ro n g c ơ s ở d ữ li ệu ( đ ô i k h i c ò n đ ược g ọi là k h a i p h á d ữ li ệu ) là m ột q u á t rìn h k h ô n g t ầm t h ườn g n h ằm p h á t h i ện ra n h ữn g m ẫu c ó g iá t r ị, m ới, h ữu íc h t i ềm n ă n g v à c ó t h ể t h ể h i ểu đ ược t ừ d ữ li ệu . K h á i n i ệm 2 : Kh a i p h á d ữ li ệu là m ột b ước t ro n g q u á t rìn h p h á t h i ện t ri t h ức t ro n g c ơ s ở d ữ li ệu , t h i h à n h m ột t h u ật t o á n k h a i p h á d ữ li ệu đ ể t ìm ra c á c m ẫu t ừ d ữ li ệu t h e o k h u ô n d ạn g t h íc h h ợp 15
1.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) v Là một tập F gồm hữu hạn các trường hợp (sự kiện). v 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 v 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. v 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
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
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: v 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 v Tri thức: tri thức mới quan hệ như thế nào với các tri thức đã có. ⟹Tổn g q u á t , đ i ều n à y c ó t h ể đ ược đ o b ằn g m ột h à m N ( E, F) h o ặc là đ ộ đ o v ề t ín h m ới h o ặc là đ ộ đ o k ỳ v ọn g . Hữu dụng tiềm năng: Mẫu cần có khả năng chỉ dẫn tới các tác động hữu dụng và đ ược đ o b ởi m ột h à m t iện íc h . Chẳng hạn: Hàm U ánh xạ các biểu thức trong L tới một không gian đo có thứ tự (bộ phận hoặc toàn bộ) MU theo đó u = U (E,F). 18
D. Tính hiểu được, tính hấp dẫn và khái niệm về tri thức  Tính hiểu được: Mẫu phải hiểu được v Mục tiêu của khai phá dữ liệu là tạo ra các mẫu mà con người hiểu chúng dễ dàng hơn các dữ liệu nền (dữ liệu sẵn có trong hệ thống). v “Có thể hiểu được" là tiêu chí khó đo được một cách chính xác ⟹ Đưa ra một số độ đo về sự dễ hiểu và các độ đo như vậy được sắp xếp từ cú pháp (tức là cỡ của mẫu theo bit) tới ngữ nghĩa (tức là dễ dàng để con người nhận thức được theo một tác động nào đó). v Giả định rằng tính hiểu được là đo được bằng một hàm S ánh xạ biểu thức E trong L tới một không gian đo được có thứ tự (bộ phận /toàn bộ) MS theo đó s = S(E,F).  Tính hấp dẫn: Độ hấp dẫn (được coi là độ đo tổng thể về mẫu) là sự kết hợp của các tiêu chí giá trị, mới, hữu ích và dễ hiểu. Các hệ thống KPDL thường: v Hoặc dùng một hàm hấp dẫn: i = I (E, F, C, N, U, S) ánh xạ biểu thức trong L vào một không gian đo được Mi. v Hoặc xác định độ hấp dẫn trực tiếp thông qua thứ tự của các mẫu 19 được phát hiện.
• Tri thức: Một mẫu E L được gọi là tri thức nếu như đối với một lớp người sử dụng nào đó, chỉ ra được một ngưỡng i Mi mà độ hấp dẫn I(E,F,C,N,U,S) > i. 20