Tài liệu Khai thác luật kết hợp từ cơ sở dữ liệu giao dịch của siêu thị bán lẻ

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN KHẮC GIÁO KHAI THÁC LUẬT KẾT HỢP TỪ CƠ SỞ DỮ LIỆU GIAO DỊCH CỦA SIÊU THỊ BÁN LẺ LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2013 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN KHẮC GIÁO KHAI THÁC LUẬT KẾT HỢP TỪ CƠ SỞ DỮ LIỆU GIAO DỊCH CỦA SIÊU THỊ BÁN LẺ Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS Vũ Đức Thi Hà Nội - 2013 3 LỜI CẢM ƠN Tôi xin bày tỏ lòng biết ơn sâu sắc đến: - GS.TS Vũ Đức Thi - Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, người thày đã tận tình hướng dẫn, chỉ bảo tôi hoàn thành tốt luận văn này. - Các thày cô giáo Khoa Công nghệ thông tin - Trường Đại học Công nghệ đã tận tâm giảng dạy, truyền đạt cho tôi những kiến thức, phương pháp nghiên cứu trong suốt hai năm học. - Các thày cô, các anh chị tại viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giúp đỡ tôi rất nhiều trong quá trình nghiên cứu. Cuối cùng xin cảm ơn gia đình và bạn bè đã giúp đỡ động viên, tạo điều kiện thuận lợi cho tôi trong suốt thời gian nghiên cứu. Hà Nội, tháng 9 năm 2013 Nguyễn Khắc Giáo 4 LỜI CAM ĐOAN Tôi xin cam đoan luận văn "Khai thác luật kết hợp từ cơ sở dữ liệu giao dịch của siêu thị bán lẻ" này là công trình nghiên cứu của tôi dưới sự hướng dẫn khoa học của GS.TS Vũ Đức Thi. Các số liệu, kết quả tham khảo trong luận văn là chính xác và được trích dẫn đầy đủ trong các tài liệu tham khảo. Phần ứng dụng thực tiễn do cá nhân tôi tự thực hiện. Tôi xin chịu trách nhiệm về luận văn của mình. Nguyễn Khắc Giáo 5 MỤC LỤC Danh mục hình vẽ ................................................................................................. 7 MỞ ĐẦU ............................................................................................................... 8 CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ................................... 11 1.1. Nhu cầu của khai phá dữ liệu ................................................................... 11 1.2. Định nghĩa khai phá dữ liệu ..................................................................... 12 1.3. Các ứng dụng của khai phá dữ liệu .......................................................... 13 1.4. Các bước của quá trình khai phá dữ liệu.................................................. 14 1.5. Kiến trúc của một hệ thống khai phá dữ liệu ........................................... 17 1.6. Kiểu dữ liệu trong khai phá dữ liệu ......................................................... 18 1.7. Các bài toán khai phá dữ liệu điển hình ................................................... 19 1.7.1. Mô tả khái niệm ................................................................................ 19 1.7.2. Quan hệ kết hợp ................................................................................ 20 1.7.3. Phân lớp (phân loại – classification) ................................................. 20 1.7.4. Phân cụm (clustering) ....................................................................... 20 1.7.5. Hồi quy (regression) .......................................................................... 20 1.7.6. Mô hình hóa sự phục thuộc (dependency modeling) ........................ 21 1.7.7. Phát hiện sự biến đổi và độ lệch (change and deviation detection) .. 21 1.8. Lợi thế của khai phá dữ liệu so với các phương pháp cơ bản.................. 22 1.8.1. Học máy (Machine Learning) ........................................................... 22 1.8.2. Phương pháp hệ chuyên gia .............................................................. 23 1.8.3. Phát kiến khoa học ............................................................................ 23 1.8.4. Phương pháp thống kê....................................................................... 23 1.9. Thách thức trong ứng dụng và nghiên cứu kỹ thuật khai phá dữ liệu ..... 24 1.9.1. Các vấn đề về CSDL ......................................................................... 24 1.9.2. Một số vấn đề khác ........................................................................... 26 1.10. Tình hình ứng dụng khai phá dữ liệu ..................................................... 27 CHƯƠNG 2. KHAI PHÁ DỮ LIỆU BẰNG LUẬT KẾT HỢP ........................ 29 2.1. Một số khái niệm ...................................................................................... 29 6 2.1.1. Độ hỗ trợ (support) ............................................................................ 29 2.1.2. Tập phổ biến ...................................................................................... 29 2.1.3. Luật kết hợp....................................................................................... 30 2.2. Phát biểu bài toán tìm luật kết hợp........................................................... 31 2.2. Một số hướng tiếp cận trong khai phá luật kết hợp ................................. 33 2.3. Một số thuật toán phát hiện luật kết hợp .................................................. 35 2.3.1. Thuật toán Apriori ............................................................................. 35 2.3.2. Thuật toán FP-Growth....................................................................... 40 CHƯƠNG 3. TÌM LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU GIAO DỊCH CỦA SIÊU THỊ BÁN LẺ ................................................................................... 50 3.1. Bài toán tìm luật kết hợp trong cơ sở dữ liệu giao dịch của siêu thị bán lẻ ......................................................................................................................... 50 3.1.1. Giới thiệu bài toán ............................................................................. 50 3.1.2. Thuật toán khai phá tập mục cổ phần cao AFSM – Advanced Fast Share Measure) ............................................................................................ 51 3.2. Xây dựng chương trình khai phá luật kết hợp trong cơ sở dữ liệu giao dịch của siêu thị bán lẻ .................................................................................... 59 3.2.1. Dữ liệu đầu vào ................................................................................. 59 3.2.2. Giao diện chương trình ..................................................................... 61 3.2.3. Thử nghiệm chương trình.................................................................. 66 3.2.4. Nhận xét ............................................................................................ 69 KẾT LUẬN ......................................................................................................... 70 Kết quả đạt được ............................................................................................. 70 Hướng nghiên cứu tiếp theo ............................................................................ 70 TÀI LIỆU THAM KHẢO ................................................................................... 72 7 Danh mục hình vẽ Hình 1.1. Tiến hóa công nghệ Cơ sở dữ liệu ................................................ 12 Hình 1.2. Quá trình phát hiện tri thức trong CSDL ...................................... 14 Hình 1.3. Quy trình phát hiện tri thức ........................................................... 15 Hình 1.4. Kiến trúc điển hình của hệ thống khai phá dữ liệu ....................... 17 Hình 2.1. Tính chất Apriori của tập mục phổ biến ....................................... 36 Hình 2.2. Nhánh tập cha không phổ biến sinh từ tập con không phổ biến ... 36 Hình 2.3. Ví dụ minh họa thuật toán Apriori ................................................ 39 Hình 3.1. Kết quả ví dụ về thuật toán AFSM ............................................... 57 Hình 3.2. Sơ đồ khối thuật toán AFSM ........................................................ 58 Hình 3.3. Dữ liệu dạng bảng ......................................................................... 59 Hình 3.4. Dữ liệu dạng CSDL....................................................................... 60 Hình 3.5. Dữ liệu dạng Text.......................................................................... 61 Hình 3.6. Form Giao diện chính ................................................................... 63 Hình 3.7. Form kết quả ................................................................................. 64 Hình 3.8. Giao diện mở file dữ liệu .............................................................. 65 Hình 3.9. Cảnh báo lỗi nếu nhập thiếu thông tin .......................................... 65 Hình 3.10. Cảnh báo lỗi nếu chọn sai dữ liệu ............................................... 66 8 MỞ ĐẦU Ngày nay, với sự phát triển nhanh chóng của công nghệ thông tin, tin học đã được ứng dụng trên nhiều mặt của kinh tế, đời sống xã hội. Kéo theo đó là một khối lượng dữ liệu đồ sộ được lưu trữ trong các hệ thống cơ sở dữ liệu, kho dữ liệu. Chúng ta biết rằng trong khối lượng dữ liệu khổng lồ đó đang ẩn chứa những giá trị nhất định. Chẳng hạn như, tập dữ liệu về thông tin khám bệnh của các bệnh nhân tại một bệnh viện hoặc một vùng có thể cho biết mối liên quan giữa các triệu chứng bệnh hay xảy ra: người bị nhức đầu thường hay bị sốt, người bị ho thường bị rát họng... ;Cơ sở dữ liệu giao dịch của một siêu thị có thể ẩn chứa thông tin về thói quen mua hàng của khách hàng tại siêu thị: khách hàng mua bánh mì thường mua sữa, khách hàng mua sữa bột thường mua bỉm, quần áo trẻ sơ sinh...; Lịch sử duyệt web của người dùng ẩn chứa thông tin về thói quen lướt web của người đó...v.v. Việc tìm ra những quy luật có thể được thực hiện bằng phương pháp thống kê nhưng khi làm việc với cơ sở dữ liệu vô cùng lớn thì phương pháp thống kê trở nên khó thực hiện và vô cùng tốn kém. Nhu cầu khai thác tri thức từ dữ liệu ngày càng lớn làm cho một khuynh hướng kỹ thuật mới ra đời: đó là phát hiện tri thức và khai phá dữ liệu KDD (Knowledge Discovery and Data Mining). Phát hiện tri thức trong cơ sở dữ liệu là một quá trình không tầm thường nhận ra những mẫu có giá trị, mới, hữu ích tiềm năng và hiểu được trong dữ liệu. KDD là sự kế thừa và phát triển các thành tựu của nhiều lĩnh vực nghiên cứu ứng dụng tin học trước đó như: Hệ chuyên gia, Trí tuệ nhân tạo, lý thuyết nhận dạng, … KDD được ứng dụng rất rộng rãi trong nghiên cứu khoa học, đời sống chính trị xã hội và kinh tế: nghiên cứu thiên văn học, tin sinh học, phát hiện gian lận, khai thác mạng xã hội, văn bản, phát hiện tội phạm, phát hiện lừa đảo, hỗ trợ ra quyết định, quản lý rủi ro... Hiện nay, thói quen mua sắm của người tiêu dùng tại các đô thị đang dần thay đổi. Với các hệ thống siêu thị rộng khắp, thuận tiện và an toàn hơn, người tiêu dùng chuyển sang mua sắm tại các siêu thị nhiều hơn. Nhờ việc ứng dụng tin học vào trong công tác quản lý, các giao dịch mua sắm của khách hàng được lưu lại trong cơ sở dữ liệu của siêu thị. Vấn đề đặt ra là, người quản lý siêu thị có thể tìm thấy những tri thức mới từ kho dữ liệu giao tác khổng lồ kia? Họ mong muốn tìm ra từ đó các quy luật mua sắm của khách hàng để điều phối, sắp xếp hàng hóa một cách phù hợp. Bài toán này có thể tìm ra lời giải bằng phương 9 pháp khai phá luật kết hợp thực hiện trên bảng cơ sở dữ liệu giao tác (giao dịch mua hàng). Trước đây, bảng dữ liệu đầu vào chỉ thể hiện việc có hay không thực hiện một giao tác nào đó (ví dụ như mặt hàng nào bán được ghi 1, không bán ghi 0), nhưng bảng dữ liệu còn thể hiện số lượng trong giao tác (mặt hàng nào không bán được ghi 0, mặt hàng bán được thì ghi số lượng của mặt hàng đó được bán. Điều này dẫn bài toán đến sát thực tiễn và có ý nghĩa thực tiễn hơn bài toán 0 và 1. Nhưng cũng vì thế mà làm biến đổi nhiều đặc tính của dữ liệu 0 và 1. Do đó nhiều nhà khoa học đã tiến hành nghiên cứu bảng dữ liệu giao tác có số lượng để tìm ra những quy luật sao cho việc tìm kiếm các tập mục phổ biến trong bảng giao tác có số lượng là nhanh nhất. Trong luận văn này, tôi chọn cách nghiên cứu và xây dựng thực nghiệm với bài toán khai thác luật kết hợp từ cơ sở dữ liệu của siêu thị bán lẻ mà các giao dịch không chỉ đơn thuần được thể hiện ở dạng nhị phân mà có cả số lượng hàng hóa được mua trong các giao dịch. Nội dung chính của luận văn gồm 3 chương: Chương 1: Tổng quan về khai phá dữ liệu Nêu những kiến thức cơ bản khai phá dữ liệu và phát hiện tri thức trong cơ sở dữ liệu: - Một số định nghĩa về khai phá dữ liệu. - Các phương pháp khai phá dữ liệu phổ biến và ứng dụng của chúng. - Khuynh hướng phát triển của khai phá dữ liệu. Chương 2: Khai phá dữ liệu bằng luật kết hợp - Giới thiệu về bài toán khai phá luật kết hợp, các khái niệm liên quan và các phương pháp khai phá luật kết hợp. - Giới thiệu một số thuật toán được sử dụng để khai phá luật kết hợp. Chương 3: Tìm luật kết hợp trong cơ sở dữ liệu giao dịch của siêu thị bán lẻ Mô tả bài toán thực nghiệm là tìm tập các luật kết hợp thể hiện thói quen mua sắm của các khách hàng từ tập cơ sở dữ liệu về các giao dịch mua bán của một siêu thị bán lẻ. Trong đó: - Mô tả sự khác biệt giữa cơ sở dữ liệu bán lẻ của siêu thị so với bảng dữ liệu nhị phân. 10 - Giới thiệu một số cách giải quyết mà các nhà khoa học đã công bố. - Xây dựng phần mềm tìm luật kết hợp dựa trên phương pháp AFSM. 11 CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1. Nhu cầu của khai phá dữ liệu Chúng ta đang sống trong thời kỳ công nghệ thông tin phát triển như vũ bão. Công nghệ thông tin ứng dụng trên hầu hết các lĩnh vực khoa học, đời sống, kinh tế, chính trị, xã hội. Đồng thời với đó là lượng dữ liệu được lưu trữ cũng được tăng lên nhanh chóng tạo ra những kho dữ liệu khổng lồ. Chúng ta biết rằng, ẩn chứa trong lượng dữ liệu đó có những giá trị nhất định. Tuy nhiên theo thống kê, chỉ một lượng nhỏ của những dữ liệu này (khoảng 5% - 10%) là luôn được phân tích, số còn lại không biết để làm gì nhưng chúng ta vẫn luôn phải lưu trữ vì sợ sẽ bỏ qua những thông tin quan trọng nào đó hoặc một ngày nào đó sẽ dùng tới chúng. Mặt khác, trong thời đại ngày nay, chúng ta cần có nhiều thông tin để trợ giúp ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Do đó, các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không thể đáp ứng được thực tế. Trong [13] hai tác giả Jiawei Han và Micheline Kamber đã nhận định rằng, tình trạng "giàu về dữ liệu mà nghèo về thông tin" là một động lực phát triển lĩnh vực khai phá dữ liệu và phát hiện tri thức trong cơ sở dữ liệu. Quá trình tiến hóa trong lĩnh vực công nghệ cơ sở dữ liệu được hai tác giả mô tả như Hình 1.1, trong đó công nghệ khai phá dữ liệu được coi là giai đoạn tiến hóa mới của công nghệ cơ sở dữ liệu. Quá trình tiến hóa này được bắt đầu từ cuối những năm 1980 và không ngừng được phát triển về cả bề rộng lẫn chiều sâu. Việc nghiên cứu và phát triển lĩnh vực khai phá dữ liệu và phát hiện tri thức trong CSDL nhằm giải quyết tình trạng "tràn ngập thông tin và thiếu thốn tri thức". Những kho dữ liệu khổng lồ về Web (Google, Alexa, Internet Achive), về CSDL (Yahoo, Max Phanck Institute for Meteorology, AT&T), kho dữ liệu về thiên văn, y tế, chứng khoán tài chính.... được xây dựng không ngoài mục đích tìm ra những thông tin có giá trị từ những dữ liệu đó. Chẳng hạn như, từ một giải pháp phân lớp trong khai phá dữ liệu Web (Web mining) có thể phát triển thành một thành phần của máy tìm kiếm để khi một trang web mới được tải về, máy tìm kiếm sẽ tự động phân nó vào một lớp trang web đã được xác định; việc phân lớp đó sẽ tạo thuận lợi cho việc tìm kiếm về sau của người sử dụng. Hay như giải pháp khai phá luật kết hợp từ một cơ sở dữ liệu về các lỗi của mạng di động cho ra được mối liên quan giữa các lỗi "phổ biến" xảy ra trong mạng di động với một xác suất nhất định (mức độ "phổ biến" này được xác định bằng 12 một ngưỡng cho trước của người khai phá) từ đó phần nào hỗ trợ người quản trị mạng có thể dự đoán được các lỗi xảy ra để có biện pháp phòng chống. Tập hợp dữ liệu và khởi tạo CSDL (tới cuối những năm 1960) - Xử lý file thô sơ Hệ quản trị CSDL (những năm 1970 và những năm đầu 1980) - Hệ thống CSDL phân cấp và mạng  Hệ thống CSDL quan hệ - Công cụ mô hình dữ liệu: Mô hình quan hệ thực thể... - Kỹ thuật đánh chỉ số và tổ chức dữ liệu: Cây B+, băm ... - Ngôn ngữ hỏi SQL... - Giao diện người dùng, nhập liệu và kết xuất - Xử lý truy vấn, tối ưu truy vấn - Quản lý giao dịch: khôi phục, điều khiển đồng thời... - Xử lý giao dịch trực tuyến (QL TP) Hệ CSDL mở rộng (những năm giữa 1980 đến nay) - Mô hình dữ liệu mở rộng: quan hệ mở rộng, hướng đối tượng, quan hệ - đối tượng, suy luận. - Định hướng ứng dụng không gian, thời gian, đa phương tiện, tích cực, khoa học, cơ sở tri thức. Kho dữ liệu và khai phá dữ liệu (những năm cuối 1980 đến nay) - Kho dữ liệu và công nghệ OLAP. - Khai phá dữ liệu & phát hiện tri thức Hệ CSDL dựa trên Web (những năm 1990 đến nay) - Hệ CSDL dựa trên XML. - Khai phá Web. Thế hệ mới hệ thông tin tích hợp (2000 -) Hình 1.1. Tiến hóa công nghệ Cơ sở dữ liệu 1.2. Định nghĩa khai phá dữ liệu "Khai phá dữ liệu được dùng để chỉ việc kết xuất hoặc khai thác tri thức từ lượng lớn dữ liệu"[13]. Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo trong kinh doanh, các hoạt động sản xuất, … Khai phá dữ liệu làm giảm chi phí về thời gian so với phương pháp truyền thống trước kia (ví dụ như phương pháp thống kê). Sau đây là các định nghĩa mang tính mô tả của các tác giả về khai phá dữ liệu được Friedman tổng hợp trong [11]: Định nghĩa của Fayyad: “Khai phá dữ liệu là một quá trình không tầm thường nhận ra những mẫu có giá trị mới, hữu ích tiềm năng và hiểu được trong dữ liệu” [10]. 13 Định nghĩa của Zekulin: "Khai phá dữ liệu là quá trình trích lọc những thông tin chưa biết, hiểu được và hữu ích từ những cơ sở dữ liệu lớn và dùng chúng để đưa ra những quyết định kinh doanh quan trọng". Định nghĩa của Ferruzza: “Khai phá dữ liệu là tập hợp các phương pháp được dùng trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các mối quan hệ và các mẫu chưa biết bên trong dữ liệu”. Định nghĩa của John: "Khai phá dữ liệu là quá trình phát hiện những mẫu có ích trong dữ liệu". Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết định, trong đó chúng ta tìm kiếm các mẫu thông tin chưa biết và bất ngờ trong CSDL lớn”. J. Han và M. Kamber cho rằng, cụm từ tiếng Anh "Data mining" (Khai phá dữ liệu) chưa diễn tả đầy đủ và toàn diện ý nghĩa của lĩnh vực nghiên cứu - triển khai mà nó mang tên. Như việc khai thác vàng từ đá hay cát không thể diễn đạt bằng cụm từ "Khai thác đá" hoặc "Khai thác cát"[13]. Tuy vậy, thuật ngữ "Khai phá dữ liệu" đã trở nên phổ biến trong các tài liệu tiếng Việt hiện nay. Hai thuật ngữ “Khám phá tri thức” và “Khai phá dữ liệu” đã xuất hiện và phổ biến trên thế giới, tuy nhiên ở việt nam thì những thuật ngữ này còn tương đối là mới mẻ do vậy rất nhiều người đã coi khai phá dữ liệu và khám phá tri thức trong cơ sở dữ liệu (knowledge discovery in databases - KDD) là như nhau. Tuy nhiên thực chất, khai phá dữ liệu chỉ là một khâu trong quá trình khám phá tri thức. Khái niệm về Khai phá dữ liệu của Frawley, Piatetski-Shapiro và Matheus: "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". 1.3. Các ứng dụng của khai phá dữ liệu Phát hiện tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực: thống kê, trí tuệ nhân tạo, CSDL, thuật toán, tính toán song song… Đặc biệt phát hiện tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực thống kê, sử dụng các phương pháp thống kê để mô hình hóa dữ liệu và phát hiện các mẫu. Khai phá dữ liệu có nhiều ứng dụng trong thực tế, ví dụ như: 14  Bảo hiểm, tài chính và thị trường chứng khoán: phân tích tình hình tài chính và dự báo giá của các loại cổ phiếu trong thị trường chứng khoán. Danh mục vốn và giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện gian lận …  Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định.  Điều trị y học và chăm sóc y tế: một số thông tin về chẩn đoán bệnh lưu trong các hệ thống quản lý bệnh viện. Phân tích mối liên hệ giữa các triệu chứng bệnh, chẩn đoán và phương pháp điều trị.  Sản xuất và chế biến: Quy trình, phương pháp chế biến và xử lý sự cố.  Text mining và Web mining: Phân tích lớp văn bản và trang web, tóm tắt văn bản.  Lĩnh vực khoa học: quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật học, tìm kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và một số bệnh di truyền…  Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám sát lỗi, sự cố, chất lượng dịch vụ, … 1.4. Các bước của quá trình khai phá dữ liệu Trình diễn Khai phá dữ liệu Tri thức Đổi dạng Tiền xử lý Mẫu Chọn lựa Dữ liệu đã chuyển dạng Dữ liệu đã tiền xử lý Dữ liệu đích Dữ liệu Hình 1.2. Quá trình phát hiện tri thức trong CSDL Theo [7,8,10] quy trình phát hiện tri thức thường tuân theo các nhóm bước như mô tả cụ thể như trong Hình 1.3. 15 Nhóm bước thứ nhất: Mở rộng hiểu biết về miền ứng dụng, về các tri thức với độ ưu tiên thích hợp và về mục đích của người dùng cuối. Có thể coi nội dung công việc này tương ứng với nội dung khảo sát bài toán trong quy trình xây dựng một hệ thống thông tin nói chung. Khởi tạo tập dữ liệu đích, tạo kho dữ liệu: chọn tập dữ liệu "và/hoặc" hướng trọng tâm tới các tập con các biến hoặc mẫu dữ liệu mà trên đó công việc phát hiện tri thức được tiến hành. Tri thức miền ứng dụng có được thông qua việc mở rộng hiểu biết về miền ứng dụng nói trên đóng vai trò là nền tảng tri thức để khởi tạo tập dữ liệu đích, kho dữ liệu. Tạo/lựa chọn CSDL đích Tạo kho dữ liệu 1 Lựa chọn kỹ thuật lấy mẫu và dữ liệu Bổ sung dữ liệu thất lạc Loại trừ dữ liệu tạp nhiễu 2 Chuẩn hóa dữ liệu Chuyển dạng dữ liệu Lựa chọn bài toán DM Lựa chọn phương pháp DM Tìm các thuộc tính quan trọng và các phạm vi có giá trị Tạo các thuộc tính xuất phát 3 Rút tri thức Test tri thức Tinh chế tri thức Chuyển sang các dạng trình diễn khác 4 5 Hình 1.3. Quy trình phát hiện tri thức Nhóm bước thứ hai: làm sạch và tiền xử lý dữ liệu: thực hiện các thao tác cơ sở như giải quyết thiếu vắng giá trị, loại bỏ nhiễu hoặc yếu tố ngoại lai, kết nối các thông tin cần thiết tới mô hình hoặc loại bỏ nhiễu, quyết định chiến lược nhằm nắm bắt các trường dữ liệu (các thuộc tính), tính toán dãy thông tin thời gian và sự biến đổi được định trước. Chất lượng của hệ thống khai phá dữ liệu phụ thuộc vào chất lượng của dữ liệu đầu vào. Mục tiêu làm sạch dữ liệu nhằm đảm bảo dữ liệu đầu vào có chất lượng tốt. Nhờ đó mà nâng cao chất lượng của hệ thống. 16 Thu gọn và trình diễn dữ liệu có mục tiêu tìm được các đặc trưng hữu ích nhằm trình bày mối phụ thuộc dữ liệu theo mục đích của bài toán. Thu gọn dữ liệu được thi hành về chiều ngang (giảm số lượng đối tượng), chiều dọc (giảm số lượng trường dữ liệu) hoặc cả hai nhằm làm giảm kích thước dữ liệu được xử lý, tăng tốc độ hoạt động của hệ thống. Sử dụng các phương pháp thu gọn hoặc biến đổi chiều nhằm rút gọn số lượng các biến cần quan tâm hoặc để tìm ra các mô tả bất biến đối với dữ liệu nhằm trình diễn dữ liệu phù hợp nhất. Do khối lượng dữ liệu trong bài toán KDD là rất lớn nên việc thực hiện bước này là rất cần thiết. Khi thu gọn theo chiều ngang cần lưu ý là tập dữ liệu được lựa chọn phải có tính đại diện cho toàn bộ dữ liệu của miền ứng dụng. Việc chọn lựa dữ liệu vào xây dựng mô hình khai thác dữ liệu thông thường cần được tiến hành theo một phương pháp đảm bảo tính "ngẫu nhiên" khi chọn lựa dữ liệu trong miền ứng dụng. Tương tự, khi thu gọn theo chiều dọc cần lưu ý các thuộc tính còn lại phải đảm bảo tính đại diện cho đối tượng trong bài toán khai phá dữ liệu đang xem xét. Trong nhiều bài toán khai phá dữ liệu, thu gọn theo chiều dọc thu được kết quả tốt hơn không chỉ về thời gian, không gian mà còn cả về chất lượng của bài toán khai phá dữ liệu cũng đạt độ chính xác cao hơn vì đã loại bỏ được một số thuộc tính gây nhiễu. Nhóm bước thứ ba: Chọn bài toán khai phá dữ liệu: quyết định mục tiêu của quá trình KDD là loại bài toán cụ thể nào. Chọn lựa phương pháp khai phá dữ liệu. Nội dung này bao gồm cả việc quyết định các mô hình và tham số có thể được chấp nhận và phương pháp khai phá dữ liệu phù hợp với tiêu chuẩn tổng thể của quá trình KDD. Thi hành thuật toán khai phá dữ liệu: tiến hành việc dò tìm các mẫu cần quan tâm dưới dạng trình bày riêng biệt, hoặc một tập các trình bày như quy tắc phân lớp, cây, hồi quy, phân đoạn, ... Trong bước này, sự hỗ trợ của người dùng vẫn đóng một vài trò quan trọng. Nhóm bước thứ tư: Giải thích mẫu đối với các mẫu được khám phá, có thể quay về một cách hợp lý tới bất kỳ bước nào từ bước đầu tiên tới bước thi hành thuật toán khai phá dữ liệu đã thực hiện. Bước thứ năm: Hợp nhất các tri thức đã được khám phá, kết hợp các tri thức này thành một hệ thống trình diễn hoặc được biên soạn dễ dàng và kết xuất thành những thành phần hấp dẫn. Kiểm tra và giải quyết xung đột đối với tri thức được trích chọn. Tóm lại: Khai phá tri thức là một quá trình kết xuất ra tri thức từ tập dữ liệu vô cùng lớn mà trong đó khai phá dữ liệu là công đoạn quan trọng nhất. 17 1.5. Kiến trúc của một hệ thống khai phá dữ liệu Kiến trúc của một hệ thống KPDL điển hình có thể có các thành phần như hình 1.4 [7, 8, 13] Giao diện đồ họa người dùng Đánh giá mẫu Máy khai phá dữ liệu Cơ sở tri thức Máy chủ CSDL hay kho dữ liệu Làm sạch và tích hợp dữ liệu Cơ sở dữ liệu Lọc Kho dữ liệu Hình 1.4. Kiến trúc điển hình của hệ thống khai phá dữ liệu - CSDL, kho dữ liệu hoặc các lưu trữ thông tin khác (Databases, Data warehouse, …): Đây là một hay một tập các CSDL, các kho dữ liệu, các trang tính hay các dạng lưu trữ thông tin khác. Các kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể được thể hiện trên những dữ liệu này. - Máy chủ CSDL hay máy chủ kho dữ liệu (Database or warehouse server): Máy chủ này có trách nhiệm lấy những dữ liệu thích hợp dựa trên các 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 được dùng để hướng dẫn việc tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết quả. - Máy KPDL (Data mining engine): Một hệ thống KPDL cần phải có một tập các modun chức năng để thực hiện công việc như: đặc trưng hoá, kết hợp, phân lớp, phân cụm, phân tích sự tiến hoá. - Modun đánh giá mẫu (Pattern evaluation): Bộ phận này tương tác với các modun KPDL để duyệt tìm các mẫu đáng được quan tâm. Nó có thể dùng các 18 ngưỡng về độ quan tâm để lọc mẫu đã khám phá được. Cũng có thể modun đánh giá mẫu được tích hợp vào modun khai phá, tuỳ theo sự cài đặt của phương pháp khai phá được dùng. - Giao diện đồ họa 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 KPDL. 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 (hay các cấu trúc dữ liệu), các đánh giá mẫu và hiển thị các mẫu trong khuôn dạng khác nhau. 1.6. Kiểu dữ liệu trong khai phá dữ liệu Nguồn dữ liệu được sử dụng để tiến hành khai phá dữ liệu rất phong phú và đa dạng, trong đó điển hình nhất là CSDL quan hệ, kho dữ liệu, CSDL giao dịch, các hệ thống dữ liệu và thông tin mở rộng khác. Cơ sở dữ liệu quan hệ: Tính phổ biến của hệ thống CSDL quan hệ hiện nay dẫn đến việc CSDL quan hệ là một nguồn đầu vào điển hình nhất, rất được quan tâm của khai phá dữ liệu. Các loại "quan hệ" tiềm ẩn trong CSDL quan hệ cũng là một trong những mối quan tâm của khai phá dữ liệu. Kho dữ liệu: theo định nghĩa của W.H. Inmon "kho dữ liệu là tập hợp các dữ liệu định hướng theo chủ đề, được tích hợp lại, có tính phiên bản theo thời gian và kiên định được dùng để hỗ trợ việc tạo ra quyết định trong quản lý", ngoài ra cũng còn nhiều định nghĩa khác về kho dữ liệu. Kho dữ liệu là một kết quả xuất hiện trong quá trình tiến hóa các hệ hỗ trợ ra quyết định. Quá trình phát hiện tri thức trong CSDL tiếp nhận đầu vào là các hệ thống CSDL, các nhà kho tổ chức dữ liệu từ các nguồn và các dữ liệu mô tả. Đồng thời với sự phát triển của công nghệ kho dữ liệu, các hệ thống tích hợp các nguồn dữ liệu cả dữ liệu trong quá khứ lẫn dữ liệu tác nghiệp đã được xây dựng. Nhiều hệ thống khai phá dữ liệu có đầu vào từ siêu dữ liệu cùng các nguồn dữ liệu trong các kho dữ liệu. Cơ sở dữ liệu giao dịch: Một lớp bài toán khai phá dữ liệu phổ biến là khai phá quan hệ kết hợp trong đó điển hình là bài toán khai phá luật kết hợp, được xuất phát từ việc xem xét các CSDL giao dịch (bán hàng). Dữ liệu giao dịch chính là dữ liệu nguyên thủy xuất hiện trong định nghĩa về luật kết hợp cùng với các độ do của luật như độ hỗ trợ và độ tin cậy. Khi mở rộng dữ liệu từ dữ liệu giao dịch sang dữ liệu vô hướng, hoặc dữ liệu phức tạp hơn có trong các CSDL quan hệ, các giải pháp khai phá luật kết hợp được cải tiến để thích ứng với sự biến đổi này. Các giải pháp ứng dụng lý thuyết tập mờ và lý thuyết tập thô tương ứng với việc mở rộng miền dữ liệu cần khai phá đã được tiến hành trong nhiều công trình nghiên cứu. 19 Các hệ thống dữ liệu mở rộng: CSDL hướng đối tượng, CSDL không gian thời gian, CSDL tạm thời, dữ liệu chuỗi thời gian, dữ liệu dòng, CSDL Text và CSDL đa phương tiện, CSDL hỗ tạp và CSDL thừa kế, Word Wide Web. 1.7. Các bài toán khai phá dữ liệu điển hình Quá trình khai phá dữ liệu là quá trình phát hiện ra mẫu thông tin. Trong đó giải thuật khai phá dữ liệu được xây dựng từ các phương pháp học máy, thiết kế mẫu, thống kê... Ở mức tổng quát, hai mục tiêu chủ yếu của khai phá dữ liệu là dự báo và mô tả, tương đương với hai dạng bài toán tổng quát của khai phá dữ liệu. Bài toán dữ báo sử dụng một số biến (hoặc trường) trong CSDL để dự đoán về những giá trị chưa biết hoặc là những giá trị sẽ xuất hiện trong tương lai của các biến. Bài toán mô tả hướng tới việc tìm ra các mẫu mô tả dữ liệu. Dự đoán và mô tả có tầm quan trọng khác nhau đối với các thuật toán khai phá dữ liệu riêng. Trong ngữ cảnh KDD, vấn đề mô tả có khuynh hướng quan trọng hơn vấn đề dự báo, điều này trái ngược với nội dung chủ yếu của các ứng dụng nhận dạng mẫu và học máy, thì vấn đề dự báo lại là quan trọng hơn. Ở mức chi tiết - cụ thể, dự báo và mô tả được thể hiện thông qua các bài toán cụ thể như mô tả khái niệm, quan hệ kết hợp, phân cụm, phân lớp, hồi quy, mô hình phụ thuộc, phát hiện biến đổi và độ lệch, và một số bài toán cụ thể khác. 1.7.1. Mô tả khái niệm Nội dung của bài toán mô tả khái niệm là tìm ra các đặc trưng và tính chất của khái niệm (dùng để mô tả khái niệm đó). Điển hình nhất trong bài toán mô tả khái niệm là các bài toán như tổng quát hóa, tóm tắt, phát hiện các đặc trưng dữ liệu ràng buộc... Bài toán tóm tắt là một bài toán mô tả điển hình áp dụng các phương pháp để tìm ra một mô tả cô đọng nhất đối với một tập con dữ liệu. Kỹ thuật tổng hợp thường áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động. Nhiệm vụ chính là sản sinh ra các mô tả đặc trưng cho một lớp. Mô tả loại này là một kiểu tổng hợp, tóm tắt lại các đặc tính chung của tất cả hay hầu hết các mục của một lớp. Các mô tả đặc trưng thể hiện theo luật có dạng sau: “Nếu một mục thuộc về lớp đã chỉ trong tiền đề thì mục đó có tất cả các thuộc tính đã nêu trong kết luận”. Lưu ý rằng luật dạng này có các đặc 20 biệt so với luật phân lớp. Luật phát hiện đặc trưng cho lớp chỉ sản sinh khi các mục đã thuộc về lớp đó. 1.7.2. Quan hệ kết hợp Phát hiện mối quan hệ kết hợp trong tập dữ liệu là một bài toán quan trọng trong khai phá dữ liệu. Một trong những mối quan hệ kết hợp điển hình là quan hệ kết hợp giữa các biến dữ liệu, trong đó bài toán khai phá luật kết hợp là một bài toán điển hình. Bài toán khai phá luật kết hợp (thuộc lớp quan hệ kết hợp) thực hiện việc phát hiện ra mối quan hệ giữa các tập thuộc tính (các tập biến) có dạng X Y, trong đó X, Y là hai tập thuộc tính. Về hình thức, luật kết hợp có dạng giống như phụ thuộc hàm trong CSDL quan hệ, nhưng nó không được định sẵn từ tri thức miền. 1.7.3. Phân lớp (phân loại – classification) Là việc xác định một hàm ánh xạ từ một tập mẫu dữ liệu vào một trong số các lớp đã được biết trước đó. Mục tiêu của thuật toán phân lớp là tìm ra mối quan hệ nào đó giữa thuộc tính dự báo và thuộc tính phân lớp. Như thế quá trình phân lớp có thể sử dụng mối quan hệ này để dự báo cho các mục mới. Các kiến thức được phát hiện biểu diễn dưới dạng các luật theo cách sau: “Nếu các thuộc tính dự báo của một mục thỏa mãn điều kiện của các tiền đề thì mục đó nằm trong lớp chỉ ra trong kết luận”. Ví dụ: Một mục biểu diễn thông tin về nhân viên có các thuộc tính dự báo là: Họ tên, tuổi, giới tính, trình độ học vấn, … và thuộc tính phân loại là trình độ lãnh đạo của nhân viên. 1.7.4. Phân cụm (clustering) Là việc mô tả chung để tìm ra các tập hay các nhóm, loại mô tả dữ liệu. Các nhóm có thể tách nhau hoặc phân cấp gối lên nhau. Có nghĩa là dữ liệu có thể vừa thuộc nhóm này lại vừa thuộc nhóm khác. Các ứng dụng khai phá dữ liệu có nhiệm vụ phân nhóm như phát hiện tập các khách hàng có phản ứng giống nhau trong CSDL tiếp thị; xác định tập quang phổ từ các phương pháp đo tia hồng ngoại, … Liên quan chặt chẽ đến việc phân nhóm là nhiệm vụ đánh giá dữ liệu, hàm mật độ xác suất đa biến, các trường trong CSDL. 1.7.5. Hồi quy (regression) Là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực. Nhiệm vụ của hồi quy tương tự như phân lớp, điểm khác nhau chính là ở chỗ thuộc tính để dự báo liên tục (không phải rời rạc). Việc dự báo các giá