Tài liệu Khai phá luật kết hợp trong cơ sở dữ liệu và ứng dụng

i ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN VĂN TƢ KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái nguyên, năm 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN VĂN TƢ KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60. 48. 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC TS. NGUYỄN HUY ĐỨC Thái nguyên, năm 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i LỜI CAM ĐOAN Tôi xin cam đoan toàn bộ nội dung trong Luận văn là đƣợc thực hiện theo đúng đề cƣơng đã đƣợc hội đồng khoa học trƣờng Đại học Thái nguyênkhoa Công nghệ thông tin phê duyệt, nội dung thực hiện trong đề cƣơng đã đƣợc cán bộ hƣớng dẫn giao cho và kiểm soát. Nội dung luận văn, các phần trích lục các tài liệu hoàn toàn chính xác. Nếu có sai sót tôi hoàn toàn chịu trách nhiệm. Tác giả luận văn Nguyễn Văn Tư Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii LỜI CẢM ƠN Tôi xin chân thành cảm ơn các thầy cô Trƣờng Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên, các Thầy cô Viện công nghệ thông tin – Viện Khoa học và Công nghệ Việt Nam, các anh chị lớp Cao học K8 - khóa 2009-2011 đã giúp đỡ tôi trong quá trình nghiên cứu và thực hiện luận văn. Tôi xin trân trọng cảm ơn TS. Nguyễn Huy Đức – Khoa Thông tin Máy tính, Trƣờng Cao đẳng Sƣ phạm Trung ƣơng, ngƣời thầy trực tiếp hƣớng dẫn, đƣa ra ý tƣởng, định hƣớng, đóng góp các ý kiến chuyên môn và tận tình giúp đỡ tôi trong suốt quá trình nghiên cứu và thực hiện luận văn thạc sĩ ngành khoa học máy tính. Tôi xin cảm ơn các bạn bè đồng nghiệp và gia đình đã giúp đỡ, đóng góp ý kiến và động viên tôi trong suốt qua trình học, quá trình nghiên cứu và hoàn thành luận văn . Tác giả Nguyễn Văn Tƣ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii MỤC LỤC Trang Lời cam đoan……………………………………………………….…….………………i Lời cảm ơn…..…………………………………………….…………….……………….ii Mục lục……………………..…………………………………….….……………..……iii DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT .............................................................v DANH MỤC CÁC BẢNG BIỂU ................................................................................................. vi DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ...................................................................................... vii MỞ ĐẦU.......................................................................................................................................1 Chƣơng 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU ..............................3 1.1. Quá trình phát hiện tri thức từ cơ sở dữ liệu. ........................................ 3 1.2. Kiến trúc của hệ thống khai phá dữ liệu ............................................... 6 1.3. Quá trình khai phá dữ liệu .................................................................... 8 1.4. Nhiệm vụ của khai phá dữ liệu. .......................................................... 10 1.5. Các phƣơng pháp chính trong khai phá dữ liệu .................................. 11 1.5.1. Phƣơng pháp luật kết hợp ............................................................ 12 1.5.2. Phƣơng pháp cây quyết định ........................................................ 12 1.5.4. Các phƣơng pháp dựa trên mẫu .................................................... 14 1.6. Các ứng dụng của khai phá dữ liệu..................................................... 15 Kết luận chƣơng 1: .................................................................................... 16 Chƣơng 2: KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU ......................................17 2.1. Bài toán mở đầu ................................................................................. 17 2.2. Các khái niệm cơ sở ........................................................................... 18 2.2.1.Cơ sở dữ liệu giao tác ................................................................... 19 2.2.2. Biểu diễn cơ sở dữ liệu giao tác ................................................... 19 2.2.3. Tập mục thƣờng xuyên ................................................................ 21 2.2.4. Luật kết hợp ................................................................................. 22 2.2.5. Độ hỗ trợ và độ tin cậy của luật kết hợp ....................................... 22 2.3. Khai phá luật kết hợp ......................................................................... 24 2.4. Các cách tiếp cận khai phá tập mục thƣờng xuyên ............................. 26 2.5. Các thuật toán điển hình khai phá tập mục thƣờng xuyên ................... 27 2.5.1 Thuật toán Apriori ........................................................................ 28 2.5.2.Thuật toán FP_growth................................................................... 33 2.6. Thuật toán sinh luật kết hợp: .............................................................. 41 2.7. Một số mở rộng khai phá luật kết hợp trong cơ sở dữ liệu. ................. 44 Kết luận chƣơng 2: .................................................................................... 46 Chƣơng 3: KHAI PHÁ LUẬT KẾT HỢP CÓ TRỌNG SỐ ......................................................47 3.1. Một số khái niệm về luật kết hợp có trọng số ..................................... 47 3.2. Khai phá luật kết hợp trọng số không chuẩn hóa ................................ 49 3.3. Khai phá luật kết hợp trọng số chuẩn hóa ........................................... 52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv 3.3.1. Một số khái niệm về trọng số chuẩn hóa..................................... 52 3.3.2. Thuật toán khai phá luật kết hợp trọng số chuẩn hóa (MINVAL(W)) ...................................................................................... 54 Kết luận chƣơng 3: .................................................................................... 56 Chƣơng 4: THỰC NGHIỆM KHAI PHÁ LUẬT KẾT HỢP....................................................57 4.1. Giới thiệu bài toán .............................................................................. 57 4.2. Dữ liệu thực nghiệm........................................................................... 58 4.3. Xây dựng chƣơng trình ...................................................................... 60 4.4. Thực nghiệm khai phá ........................................................................ 61 4.5. Kết quả thực nghiệm .......................................................................... 63 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN.................................................................................... 63 1. Những kết quả đã đạt đƣợc.................................................................... 63 2. Hƣớng phát triển của đề tài là: .............................................................. 64 TÀI LIỆU THAM KHẢO ........................................................................................................... 65 PHỤ LỤC ................................................................................................................................... 67 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT Ký hiệu Diễn giải KPDL Khai phá dữ liệu CSDL Cơ sở dữ liệu DB Cơ sở dữ liệu giao tác TID Định danh của giao tác I Tập các mục dữ liệu T Giao tác (transaction) Ck Tập các ứng viên là tập mục có k mục dữ liệu Lk Tập các tập mục thƣờng xuyên có k mục dữ liệu k-itemset Tập mục gồm k mục BFS Breadth First Search DFS Depth First Search FP-growth Frequent-Pattern Growth FP-tree Frequent pattern tree Sup Độ hỗ trợ (support) Minsup Ngƣỡng hỗ trợ tối thiểu SC(X) Số lƣợng giao dịch chứa tập mục X SRC Kỹ thuật lấy mẫu ngẫu nhiên Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vi DANH MỤC CÁC BẢNG BIỂU Bảng 2.1: Danh mục các tập mục trong CSDL ............................................. 19 Bảng 2.2: Biểu diễn ngang của CSDL giao tác. ............................................ 20 Bảng 2.3: Biểu diễn dọc của CSDL giao tác. ................................................ 20 Bảng 2.4: Ma trận giao tác của CSDL bảng 2.2 ............................................ 21 Bảng 2.5: Cơ sở dữ liệu DB ......................................................................... 24 Bảng 2.6: Độ hỗ trợ của các mục .................................................................. 25 Bảng 2.7: Độ hỗ trợ của các tập mục ............................................................ 25 Bảng 2.8: Độ tin cậy của các luật ................................................................. 26 Bảng 2.9: CSDL giao tác minh hoạ cho thuật toán Apriori ........................... 31 Bảng 2.10: CSDL giao tác minh hoạ cho thuật toán FP- growth. .................. 34 Bảng 3.1.a. Tập giao tác DB ......................................................................... 48 Bảng 3.1.b. Thông tin của cửa hàng.............................................................. 48 Bảng 4.1: Dữ liệu đã trích chọn để khai phá ................................................. 58 Bảng 4.2: Mã hóa các mặt hàng.................................................................... 59 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1. Quá trình khám phá tri thức ............................................................ 5 Hình 1.2. Kiến trúc của hệ thống khai phá dữ liệu .......................................... 7 Hình 1.3: Quá trình khai phá dữ liệu .............................................................. 9 Hình 1.4: Mẫu kết quả với phƣơng pháp cây quyết định .............................. 12 Hình 1.5: Phân cụm các đối tƣợng k-Mean ( + là tâm của cụm) ................... 13 Hình 2.1: Phân loại các thuật toán khai phá tập mục thƣờng xuyên. ............. 27 Hình 2.2: Cây FP-tree đƣợc xây dựng dần khi thêm các giao tác t1, t2, t3. ... 35 Hình 2.3: Cây FP-tree của CSDL DB trong bảng 2.10 ................................ 36 Hình 2.4: FP-tree phụ thuộc của m ............................................................... 39 Hình 2.5 : Các FP-tree phụ thuộc của am, cm và cam................................... 39 Hình 4.1: Dữ liệu đã mã hóa chuẩn bị cho khai phá...................................... 60 Hình 4.2: Giao diện chƣơng trình ................................................................. 61 Hình 4.3: Giao diện kết quả khai phá tập mục thƣờng xuyên........................ 62 Hình 4.4: Giao diện kết quả khai phá luật kết hợp ........................................ 62 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỞ ĐẦU Trong những năm qua, việc nắm bắt, xử lý đƣợc thông tin đƣợc coi là cơ sở của mọi hoạt động của đời sống xã hội, đặc biệt là trong sản xuất, kinh doanh. Những thông tin tiềm ẩn mang tính dự đoán trong các khối dữ liệu là rất lớn. Mỗi cá nhân hoặc tổ chức nào thu thập và hiểu đƣợc thông tin, hành động dựa trên các thông tin đƣợc kết xuất từ các thông tin đã có sẽ đạt đƣợc thành công trong mọi hoạt động. Chính vì lý do đó, việc tạo ra thông tin, tổ chức lƣu trữ và khai phá ngày càng trở nên quan trọng và gia tăng không ngừng. Sự tăng trƣởng vƣợt bậc của các cơ sở dữ liệu (CSDL) trong cuộc sống nhƣ: thƣơng mại, quản lý và khoa học …đã làm nảy sinh và thúc đẩy sự phát triển của kỹ thuật thu thập, lƣu trữ, phân tích và khai phá dữ liệu không chỉ bằng các phép toán đơn giản thông thƣờng nhƣ: phép đếm, thống kê mà đòi hỏi cách xử lý thông minh hơn, hiệu quả hơn. Từ đó các nhà quản lý có đƣợc thông tin có ích để tác động lại quá trình sản xuất, kinh doanh của mình đó là tri thức. Các kỹ thuật cho phép ta khai phá đƣợc tri thức hữu dụng từ CSDL (lớn) đƣợc gọi là các kỹ thuật khai phá dữ liệu (DM – Data Mining). Khai phá luật kết hợp là một nội dung quan trọng trong khai phá dữ liệu. Một trong những nội dung cơ bản nhất trong khai phá dữ liệu và rất thƣờng xuyên là phát hiện các luật kết hợp trong kho cơ sở dữ liệu khổng lồ, nhằm tìm ra các tập mục thƣờng xuyên 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 tập mục thƣờng xuyên dẫn đến sự xuất hiện của một (hay một tập) mục thƣờng xuyên khác nhƣ thế nào, do vậy khai phá luật kết hợp trong kho cơ sở dữ liệu có ý nghĩa rất quan trọng, có lợi ích to lớn trong việc tổng hợp và cung cấp những thông tin cần thiết trong nguồn cơ sở dữ liệu lớn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 Xuất phát từ thực tế nói trên và với mục đích tìm hiểu về bài toán tìm luật kết hợp trong cơ sở dữ liệu, em đã quyết định lựa chọn đề tài: “Khai phá luật kết hợp trong cơ sở dữ liệu và ứng dụng” Ứng dụng khai phá luật kết hợp trong cơ sở dữ liệu đã mang lại những lợi ích to lớn trong việc tổng hợp và cung cấp những thông tin trong các nguồn cơ sở dữ liệu lớn. Đây là một đề tài không chỉ có ý nghĩa khoa học mà còn mang đậm tính thực tiễn. Phƣơng pháp nghiên cứu của luận văn là tổng hợp các kết quả nghiên cứu về khai phá tập mục thƣờng xuyên, khai phá luật kết hợp đã công bố trên các bài báo khoa học, hội thảo chuyên ngành trong và ngoài nƣớc, từ đó, trình bày làm rõ vấn đề khai phá luật kết hợp và xây dựng chƣơng trình thực nghiệm đánh giá một số thuật toán. Luận văn gồm 4 chƣơng và phần kết luận Chƣơng 1: Tổng quan về cơ sở dữ liệu và khai phá dữ liệu Chƣơng 2: Khai phá luật kết hợp trong cơ sở dữ liệu Chƣơng 3: Khai phá luật kết hợp có trọng số Chƣơng 4: Thực nghiệm khai phá luật kết hợp Trong suốt quá trình tìm hiểu, nghiên cứu và hoàn thành luận văn, đƣợc sự hƣớng dẫn tận tình của Thầy hƣớng dẫn TS. Nguyễn Huy Đức - Khoa Thông tin - Máy tính, Trƣờng Cao đẳng Sƣ phạm Trung ƣơng; mặc dù em đã cố gắng, nỗ lực hết sức nhƣng không thể tránh khỏi thiếu sót, em tha thiết kính mong tiếp tục nhận đƣợc sự giúp đỡ, chỉ bảo của các thầy cô để đề tài đƣợc hoàn thiện hơn. Em xin chân thành cảm ơn ! Thái Nguyên, ngày 30 tháng 10 năm 2011 Học viên: Nguyễn Văn Tƣ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chƣơng 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU 1.1. Quá trình phát hiện tri thức từ cơ sở dữ liệu. Trong thời đại ngày nay, với sự phát triển vƣợt bậc của công nghệ thông tin, các hệ thống thông tin có thể lƣu trữ một khối lƣợng lớn dữ liệu về hoạt động hàng ngày của chúng. Lƣợng dữ liệu đƣợc lƣu trữ dẫn đến một đòi hỏi cấp bách phải có những kỹ thuật mới, những công cụ tự động mới trợ giúp con ngƣời một cách thông minh trong việc chuyển đổi một lƣợng lớn dữ liệu thành thông tin hữu ích. Một số nhà khoa học xem khai phá dữ liệu nhƣ là một cách gọi khác của một thuật ngữ cũng rất thông dụng là khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases – KDD), vì cho rằng mục đích của quá trình khám phá tri thức là thông tin và tri thức có ích, nhƣng đối tƣợng mà chúng ta phải xử lý rất nhiều trong suốt quá trình khám phá tri thức lại chính là dữ liệu. Một số nhà khoa học khác thì xem khai phá dữ liệu nhƣ là một bƣớc chính trong quá trình khám phá tri thức. Hiểu quá trình khám phá, phát hiện tri thức ở đây là gì? Thông thƣờng chúng ta coi dữ liệu nhƣ là một dãy các bit, các số và các ký hiệu, hoặc các “đối tƣợng” đƣợc gửi cho một chƣơng trình dƣới một định dạng nhất định nào đó. Chúng ta sử dụng các bit để đo lƣờng thông tin, khi sử dụng xem nó nhƣ là dữ liệu đã đƣợc lọc bỏ dƣ thừa, đƣợc rút gọn tới mức tối thiểu. Bít đƣợc dùng làm đơn vị đặc trƣng cho dữ liệu. Chúng ta có thể xem tri thức nhƣ là các thông tin tích hợp, bao gồm các sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể đƣợc học, đƣợc hiểu, đƣợc phát hiện ra. Nói cách khác, tri thức có thể coi là dữ liệu có độ trừu tƣợng và tổ chức cao. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Phát hiện tri thức là quá trình nhận biết cái logic, cái mới lạ, những tri thức tiềm tàng hữu ích từ cơ sở dữ liệu, cuối cùng là việc hiểu đƣợc các mẫu các mô hình trong cơ sở dữ liệu. Vì vậy mà kỹ thuật phát hiện tri thức đã ra đời và ngày càng phát triển để đáp ứng nhu cầu của con ngƣời trong việc xử lý các thông tin trong kho cơ sở dữ liệu khổng lồ. Thuật ngữ KPDL (Khai phá dữ liệu) ra đời vào những năm cuối của thập kỷ 1980. Khai phá dữ liệu bao gồm nhiều hƣớng tiếp cận, là sự kết hợp của nhiều ngành nhƣ: Cơ sở dữ liệu; Hiển thị dữ liệu; Học máy; Trí tuệ nhân tạo; Lý thuyết thông tin; Xác suất thống kê; Tính toán hiệu năng cao, và các phƣơng pháp tính toán mềm v. v…. Có rất nhiều định nghĩa khác nhau về "KPDL" đã đƣợc đƣa ra, ta có thể hiểu khai phá dữ liệu đƣợc định nghĩa là quá trình tìm kiếm những thông tin (tri thức) có ích, tiềm ẩn và mang tính dự đoán trong các khối cơ sở dữ liệu lớn. KPDL là cốt lõi của quá trình khám phá tri thức. Nó gồm có các giải thuật KPDL chuyên dùng, dƣới một số quy định về hiệu quả tính toán chấp nhận đƣợc. KPDL là nhằm tìm ra những mẫu mới, mẫu có tính chất không tầm thƣờng, những thông tin tiềm ẩn mang tính dự đoán chƣa đƣợc biết đến và có khả năng mang lại lợi ích cho ngƣời sử dụng. Nói tóm lại, mục đích chung của việc phát hiện tri thức từ dữ liệu và KPDL là tìm ra các mẫu đƣợc quan tâm nhất tồn tại trong cơ sở dữ liệu, nhƣng chúng lại bị che dấu bởi một số lƣợng lớn dữ liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 Quá trình khám phá tri thức đƣợc tiến hành qua các bƣớc sau: Các Tri thức Các mẫu Dữ liệu đã sạch Dữ liệu đã chọn 5.Đánh giá và biểu diễn tri thức knowledge representation & evaluation 4.Khai phá dữ liệu data mining Kho dữ liệu 3.Biến đổi dữ liệu data transformation 2. Tiền xử lý dữ liệu data preprocessing 1. Trích chọn dữ liệu data selection Hình 1.1. Quá trình khám phá tri thức Bƣớc 1: Trích chọn dữ liệu (data selection): là bƣớc trích chọn những tập dữ liệu cần đƣợc khai phá từ các tập dữ liệu lớn (databases, data warehouses) Bƣớc 2: Tiền xử lý dữ liệu (data preprocessing): là bƣớc làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, v.. v), rút gọn dữ liệu (sử dụng các phƣơng pháp thu gọn dữ liệu, histograms, lấy mẫu, . v. .v ), rời rạc hoá dữ liệu (dựa vào histograms, entropy, phân khoảng, v. . v ). Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và đƣợc rời rạc hoá. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 Bƣớc 3: Biến đổi dữ liệu (data transformation): là bƣớc chuẩn hoá và làm mịn dữ liệu để đƣa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở bƣớc sau. Bƣớc 4: Khai phá dữ liệu (data mining): đây là bƣớc quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai phá(phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn đƣợc các mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu. Bƣớc 5: Đánh giá và biểu diễn tri thức (knowledge representation & evaluation ): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã đƣợc khai phá ở bƣớc trên biểu diễn theo dạng gần gũi với ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu, luật,. v. v. Đồng thời bƣớc này cũng đánh giá những tri thức khai phá đƣợc theo những tiêu chí nhất định. Trong giai đoạn khai phá dữ liệu, có thể cần sự tƣơng tác của ngƣời dùng để điều chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận đƣợc cũng có thể đƣợc lƣu và sử dụng lại. 1.2. Kiến trúc của hệ thống khai phá dữ liệu Khai phá dữ liệu là quá trình rút trích thông tin bổ ích từ những kho dữ liệu. Khai phá dữ liệu là quá trình chính trong khai phá tri thức từ cơ sở dữ liệu. Kiến trúc của một hệ thống khai phá dữ liệu có các thành [3,8] phần nhƣ sau: * CSDL, kho dữ liệu hoặc lưu trữ thông tin khác: Đây là một hay các tập CSDL, các trang tính hay các dạng khác của thông tin đƣợc lƣu trữ. Các kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể đƣợc thực hiện. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 Giao diện đồ họa cho ngƣời dùng ( Graphical user interface) ( Pattern evaluation) Đánh giá mẫu cơ sở tri thức (Data mining engine) Máy khai phá dữ liệu (Knowledge-base) (Database or Warehouse Server) Máy chủ CSDL hay kho dữ liệu Làm sạch ; tích hợp dữ liệu; lọc Cơ sở dữ Cơ liệusở dữ liệu Kho dữ liệu Các lƣu trữ thông tin khác Hình 1.2. Kiến trúc của hệ thống khai phá dữ liệu * Máy chủ CSDL (Database or Warehouse Server): Máy chủ có trách nhiệm lấy những 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 dùng để tìm kiếm hay đánh giá độ quan trọng của các mẫu kết quả thu đƣợc. Tri thức này có thể bao gồm một sự phân cấp khái niệm dùng để tổ chức các tập mục dữ liệu ở các mức trừu tƣợng khác nhau. * Máy khai phá dữ liệu (Data mining engine): là một hệ thống khai phá dữ liệu cần phải có một tập các Modul chức năng để thực hiện công việc, chẳng hạn nhƣ kết hợp, phân lớp, phân cụm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 * Modul đánh giá mẫu ( Pattern evaluation): Bộ phận tƣơng tác với các Modul khai phá dữ liệu để tập trung vào việc duyệt tìm các mẫu đáng đƣợc quan tâm. Nó có thể dùng các ngƣỡng về độ quan tâm để lọc mẫu đã khai phá đƣợc. Cũng có thể Modul đánh giá mẫu đƣợc tích hợp vào Modul khai phá dữ liệu, tùy theo cách cài đặt của phƣơng pháp khai phá dữ liệu đƣợc dùng. * Giao diện đồ họa cho người dùng ( Graphical user interface): Bộ phận này cho phép ngƣời dùng giao tiếp với hệ thống khai phá dữ liệu. Thông qua giao diện này ngƣời dùng tƣơng tác với hệ thống bằng cách đặc tả một yêu cầu khai phá hay một nhiệm vụ, cung cấp thông tin trợ giúp cho việc tìm kiếm và thực hiện khai phá thăm dò trên các kết quả khai phá trung gian. Ngoài ra bộ phận này còn cho phép ngƣời dùng xem các lƣợc đồ CSDL, lƣợc đồ kho dữ liệu, các đánh giá mẫu và hiển thị các mẫu trong các khuôn dạng khác nhau. 1.3. Quá trình khai phá dữ liệu Quá trình khai phá dữ liệu là một bƣớc trong quá trình khai phá tri thức, đƣợc thực hiện bằng việc xác định những vấn đề cần giải quyết, từ đó sẽ xác định dữ liệu liên quan dùng để xây dựng giải pháp và những việc cần thực hiện, xử lý chúng thành một dạng sao cho thuật toán khai phá dữ liệu có thể hiểu đƣợc. Với những dữ liệu đã thu thập, ta tiến hành tích hợp và chỉnh sửa dữ liệu, lọc dữ liệu, đây là quá trình tiền xử lý. Dữ liệu đƣợc thu thập từ nhiều nguồn khác nhau, qua những dữ liệu trực tiếp ta thống kê tóm tắt, trong khi đó có thể có những sự sai sót, dƣ thừa và trùng lặp. Lọc dữ liệu là cắt bỏ những dƣ thừa để dữ liệu đƣợc định dạng thống nhất. Có thể dễ hiểu hơn qua thực tế ví dụ sau: Ngƣời kinh doanh bán hàng nhiều mặt hàng, muốn tăng doanh thu thì phải giải đƣợc bài toán tìm quy luật Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 mua hàng của khách hàng, ta tìm xem khách hàng thƣờng cùng mua những mặt hàng nào để sắp xếp những món hàng đó gần nhau. Từ dữ liệu có nhiều mục không cần thiết cho khai phá dữ liệu nhƣ: Mã khách hàng, nhà cung cấp, đơn giá hàng, ngƣời bán hàng… Các dữ liệu này cần cho quản lý bán hàng nhƣng không cần cho khai phá dữ liệu, ta loại bỏ các mục dữ liệu này khỏi dữ liệu trƣớc khi khai phá dữ liệu. Dữ liệu sau khi lọc và chỉnh sửa sẽ nhỏ hơn, xử lý nhanh chóng hơn. Quá trình khai phá dữ liệu đƣợc thể hiện bởi hình 1.3 sau: Thống kê tóm tắt Xác định nhiệm vụ Xác định dữ liệu liên quan Thu thập và tiền xử lý DL Giải thuật khai phá DL Mẫu Dữ liệu trực tiếp Hình 1.3: Quá trình khai phá dữ liệu Công việc tiếp theo sử dụng các thuật toán khác nhau để khai phá các kiến thức tiềm ẩn trong kho dữ liệu sau khi đã xử lý và đƣợc thống kê tóm tắt cùng các dữ liệu trực tiếp. Kết quả của quá trình khai phá dữ liệu là đạt đƣợc nhiệm vụ đặt ra. Nhiều kỹ thuật khai phá dữ liệu đƣợc ứng dụng cho một nguồn dữ liệu, các kỹ thuật cho các kết quả có thể khác nhau. Các kết quả đƣợc ƣớc lƣợng bởi những quy tắc nào đó, nếu cuối cùng kết quả không thỏa mãn yêu cầu, chúng ta phải làm lại với kỹ thuật khác cho đến khi có kết quả mong muốn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 1.4. Nhiệm vụ của khai phá dữ liệu. Mục đích của khai phá dữ liệu là đƣa ra kết quả chiết xuất tri thức từ dữ liệu. Khi cơ sở dữ liệu đã trở nên khổng lồ thì những khâu nhƣ: thu thập dữ liệu, tiền xử lý và xử lý dữ liệu đều đòi hỏi phải đƣợc tự động hóa.. bƣớc khai phá dữ liệu sẽ thực hiện hai mục đích mô tả (description) và dự đoán (prediction). Các mẫu mà khai phá dữ liệu phát hiện đƣợc nhằm vào các mục đích này. Để đạt đƣợc hai mục đích trên, nhiệm vụ chính của khai phá dữ liệu bao gồm là: Phân cụm, phân loại, phân nhóm, phân lớp: Nhiệm vụ là trả lời câu hỏi: Một dữ liệu mới thu thập sẽ thuộc về nhóm nào? Quá trình này thƣờng đƣợc thực hiện một cách tự động. Khai phá luật kết hợp: Nhiệm vụ là phát hiện ra những mối quan hệ giống nhau của các bản ghi giao tác. Luật kết hợp X=>Y có dạng tổng quát là: Nếu một giao tác đã chứa các tính chất X thì đồng thời nó cũng chứa các tính chất Y, ở một mức độ nào đó. Khai phá luật kết hợp đƣợc hiểu theo nghĩa: Biết trƣớc các tính chất X, vậy các tính chất Y là những tính chất nào? (chúng ta sẽ tìm hiểu sâu hơn ở chƣơng 2 và chƣơng 3) Lập mô hình dự báo: Bao gồm hai nhiệm vụ: hoặc là phân nhóm dữ liệu vào một hay nhiều lớp dữ liệu đã xác định từ trƣớc, hoặc là sử dụng các trƣờng đã cho trong một cơ sở dữ liệu để dự báo sự xuất hiện (hoặc không xuất hiện) của các trƣờng khác. Phân tích đối tượng ngoài cuộc: Một cơ sở dữ liệu có thể chứa các đối tƣợng không tuân theo mô hình dữ liệu. Các đối tƣợng dữ liệu nhƣ vậy gọi là các đối tƣợng ngoài cuộc. Hầu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 hết các phƣơng pháp khai phá dữ liệu đều coi các đối tƣợng ngoài cuộc là nhiễu và loại bỏ chúng. Sự phân tích dữ liệu ngoài cuộc đƣợc coi nhƣ là phai phá các đối tƣợng ngoài cuộc. Một số phƣơng pháp đƣợc ứng dụng để phát hiện đối tƣợng ngoài cuộc: Sử dụng các hình thức kiểm tra mang tính thống kê trên cơ sở một phân phối dữ liệu hay một mô hình xác suất cho dữ liệu, dùng các độ đo khoảng cách mà theo đó các đối tƣợng có một khoảng cách đáng kể đến cụm bất kỳ khác đƣợc coi là đối tƣợng ngoài cuộc, dùng các phƣơng pháp dựa trên độ lệch để kiểm tra sự khác nhau trong những đặc trƣng chính của các nhóm đối tƣợng. Phân tích sự tiến hóa: Phân tích sự tiến hóa thực hiện việc mô tả và mô hình hóa các quy luật hay khuynh hƣớng của những đối tƣợng mà ứng xử của chúng thay đổi theo thời gian. Phân tích sự tiến hóa có thể bao gồm cả đặc trƣng hóa, phân biệt, tìm luật kết hợp, phân lớp hay phân cụm dữ liệu liên quan đến thời gian, phân tích dữ liệu theo chuỗi thời gian, so sánh mẫu theo chu kỳ và phân tích dữ liệu dựa trên tính tƣơng tự. Trong quá trình phát triển nền Kinh tế - Xã hội hiện nay, rất nhiều lĩnh vực đa ngành, nhiệm vụ khai phá dữ liệu phải làm là phát hiện ra những giả thuyết mạnh trƣớc khi sử dụng những công cụ tính toán thống kê, đó là những công việc luôn thu hút các lĩnh vực khoa học nhƣ trí tuệ nhân tạo, cơ sở dữ liệu, hiển thị dữ liệu, marketing, toán học, tin sinh học, nhận dạng mẫu, tính toán thống kê … 1.5. Các phƣơng pháp chính trong khai phá dữ liệu Khai phá dữ liệu gồm nhiều hƣớng tiếp cận phù hợp với từng cơ sở dữ liệu của các lĩnh vực khoa học và đời sống xã hội. Một số phƣơng pháp chính trong khai phá dữ liệu là: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn