Tài liệu Khai phá dữ liệu bằng luật kết hợp

NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ................................................................................................................................ ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. ............................................................................................................................................. 1 LỜI NÓI ĐẦU Ngày nay các lĩnh vực khoa học kỹ thuật đang ngày một phát triển mạnh mẽ. Đặc biệt là nghành khoa học máy tính rất phát triển, nó được ứng dụng rất nhiều trong các lĩnh vực khác nhau của cuộc sống như: Giáo dục, Y tế, Kinh tế, Khoa học, Xây dưng, Nó đã trở thành một phần không thể thiếu được trong cuộc sống hàng ngày của con người.Việc dùng các phương tiện tin học để tổ chức và khai thác các cơ sở dữ liệu đã được phát triển từ những năm 60. Đặc biệt trong những năm gần đây vai trò của máy tính trong việc lưu trữ và xử lý thông tin ngày càng trở lên quan trọng. Bên cạnh đó các thiết bị thu thập dữ liệu tự động tương đối phát triển đã tạo ra những kho dữ liệu khổng lồ. Với sự phát triển mạnh mẽ của công nghệ điện tử tạo ra các bộ nhớ có dung lượng lớn, bộ xử lý tốc độ cao cùng với các hệ thống mạng viễn thông, người ta đã xây dựng các hệ thống thông tin nhằm tự động hoá mọi hoạt động kinh doanh của mình. Điều này đã tạo ra một dòng dữ liệu tăng lên không ngừng ví ngay từ các các giao dịch đơn gian nhất như một cuộc điện thoại, kiểm tra sức khỏe, sử dụng thẻ tín dụng, v.v.đều được ghi vào trong máy tính. Cho tới nay con số này đã trở lên khổng lồ, bao gồm các cơ sở dữ liệu, thông tin khách hàng, dữ liệu lịch sử các giao dịch, dữ liệu bán hàng, dữ liệu các tài khoản vay, sử dụng vốn,..Vấn đề đặt ra là làm thế nào để sử lý khối lượng thông tin cực lớn như vậy để phát hiện ra các tri thưc tiềm ẩn trong nó. Để làm được điều đó người ta đã sử dụng quá trính Phát hiện tri thức trong cơ sở dữ liệu( Knowledge Discovery in Database-KDD). Nhiệm vụ của KDD là từ dữ liệu sẵn có phải tìm ra những thông tin tiềm ẩn có giá trị mà trước đó chưa được phát hiện cũng như tìm ra những xu hướng phát triển và các xu hướng tác động lên chúng .Các kỹ thuật cho phép ta lấy được các tri thức từ cơ sở dữ liệu sẵn có đó được gọi là kỹ thuật Khai phá dữ liệu( Data Mining). Từ những lý do đó chúng em đã hiểu về đề tài Khai phá dữ liệu bằng luật kết hợp. Nhằm phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra những mẫu thông tin, hoạt động có tính chính quy trong tập dữ liệu mà người sử dụng mong muốn, đồng thời để áp dụng vào bài toán Quản lý bán hàng tại siêu thị. Trong quá trình làm đồ án để hoàn thành đề tài này chúng đã nhận được sự giúp đỡ chỉ bảo tận tình của các thầy cô giáo trong khoa công nghệ thông tin và các bạn trong lớp, đặc biệt là thầy giáo Trần Hùng Cường. Nhưng do thời gian có giới hạn và năng lực còn hạn chế nên không tránh khỏi những sai sót, chúng em mong nhận được sự góp ý hơn nữa của thầy cô và các bạn. Chúng em cũng xin chân thành cảm ơn các thầy giáo, cô giáo trong khoa Công Nghệ Thông Tin đã tạo điều kiện giúp đỡ chúng em trong xuốt thời gian làm đồ án và học tập tại trường. 2 Chúng em xin chân thành cảm ơn các bạn cùng lớp đã tạo điều kiện cho chúng em hoàn thành tốt luận văn này. Chúng em xin chân thành cảm ơn! Nhóm sinh viên thực hiện: Phạm Thị Hoàn Trần Việt Phương Đông Lớp CĐ-ĐH-KHMT3-K1 3 TÓM TẮT ĐỒ ÁN Nội dung của đồ án là những kiến thức về khai phá dữ liệu sử dụng luật kết hợp, các thuật toán kinh điển trong quá trình sử dụng luật kết hợp, cách áp dụng thuật toán Apriori vào một phần nhỏ trong bài toán Quản lý bán hàng tại siêu thị . Mục đích của đồ án là: Phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra những mẫu thông tin, hoạt động có tính chính quy trong tập dữ liệu mà người sử dụng mong muốn. Đưa ra các thuật toán cơ bản như Apriori, thuật toán tìm luật kết hợp không phát sinh ứng viên dựa vào cấu trúc cây FP- Tree, v.v.trong việc sử dụng luật kết hợp để phân tích một cơ sở dữ liệu nào đó. Phân tích cơ sở dữ liệu và cài đặt thuật toán Apriori để áp dụng một phần nhỏ vào bài toán Quản lý bán hàng tại siêu thị . Đồ án bao gồm có 3 chương, với các nội dung như sau: Chương I: Tổng quan về khai phá dữ liệu. Nội dung trong chương này sẽ được trình bày bao gồm: Khai phá dữ liệu và phát hiện tri thức, quá trình phát hiện tri thức từ cơ sở dữ liệu, khai phá dữ liệu có lợi ích gì? Các kỹ thuật khai phá dữ liệu, nhiêm vụ chính của khai phá dữ liệu, các phương pháp khai phá dữ liệu, ứng dụng của khai phá dữ liệu và một số thách thức đặt ra cho việc khai phá dữ liệu. Chương II: Tập phổ biến và luật kết hợp: Nội dung đuợc trình bày bao gồm: Một số khái niệm, tính chất cơ bản của tập phổ biến và luật kết hợp, tìm tập phổ biến, một số thuật toán cơ bản về luật kết hợp, một số ví dụ minh họa các thuật toán. Chương III: Cách cài đặt và thử nghiệm thuật toán tìm tập phổ biến và luật kết hợp: Phân tích một cơ sở dữ liệu, trình bày về cách cài đặt chương trình khai thác luật kết hợp trong việc quản lý bán hàng tại siêu thị. Dựa vào kết quả này mà người quản lý bán hàng tại thị siêu nắm bắt được những nhóm mặt hàng nào có liên quan tới nhau, phục vụ cho mục đích quản lý và lựa chọn các mặt hàng để kinh doanh. 4 SUMMARY OF THE PROJECT This project’s content is the knowledge of data mining which uses association rules, the classical algorithms in the proccess of using association rules, how to apply Apriori Algorithms to a small part on Sales Management Problem in supermarket. The purposes of this project are: Analysing data and using technique to find out sample informations, actions which have regular nature in data files that users want. Bringing out the classical algorithms such as Apriori, the algorithms of finding association rules without arising subsets (candidates) which base on FPTree Structure...etc in using association rules to analyse any database. Analysing database and installing Apriori Algorithms to apply partly to Sales Management Task in supermarket. The project has 3 chapters, with main content as follows: Chapter I: Overview of data mining. The contents of this chapter which will be presented consist of: Data Mining and Knowledge Discovery in database, the advantages of data mining? Techniques of data mining, main task of data mining, methods of data mining, application of data mining and some challenges which are set up for data mining. Chapter II: Frequent- Itemset and Association Rules. This chapter’s content includes in: some concepts, basic property of Frequent- Itemset and Association Rules, searching for Frequent- Itemset, some basic algorithms of Association Rules, some examples which illustrates algorithms. Chapter III: How to install and test The Algorithms of finding Frequent Itemset and Association Rules. They are: Analysing one database, presenting the way to install program “ Exploiting Frequent Itemset in Sales Management in supermarket”. Sales Manager bases on this result to know gather of related product to statisfy the purpose of management and choice products to do bussiness. 5 MỤC LỤC NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN................................................................1 LỜI NÓI ĐẦU.......................................................................................................................2 TÓM TẮT ĐỒ ÁN.................................................................................................................4 SUMMARY OF THE PROJECT.........................................................................................5 DANH SÁCH BẢNG BIỂU.................................................................................................9 DANH SÁCH CÁC TỪ VIẾT TẮT....................................................................................10 ..............................................................................................................................................11 MỞ ĐẦU..............................................................................................................................12 Chương I: TỔNG QUAN VỀ KHAI PHÁI DỮ LIỆU......................................................13 1.1. Đặt vấn đề...........................................................................................................................13 1.2. Khai phá dữ liệu và phát hiện tri thức..............................................................................14 1.3. Quá trình phát hiện tri thức từ cơ sở dữ liệu...................................................................14 1.3.1. Xác định bài toán...........................................................................................................................15 1.3.2. Thu thập và tiền xử lý....................................................................................................................15 1.3.2.1. Gom dữ liệu............................................................................................................................16 1.3.2.2. Chọn lọc dữ liệu.....................................................................................................................16 1.3.2.3. Làm sạch................................................................................................................................16 1.3.2.4. Làm giàu dữ liệu....................................................................................................................17 1.3.2.5. Mã hoá dữ liệu........................................................................................................................17 1.3.2.6. Đánh giá và trình diễn............................................................................................................17 1.3.3. Khai phá dữ liệu.............................................................................................................................18 1.3.4. Phát biểu và đánh giá kết quả.........................................................................................................18 1.3.5. Sử dụng tri thức đã phát hiện.........................................................................................................18 1.4. Khai phá dữ liệu có những lợi ích gì.................................................................................18 1.5. Các kỹ thuật khai phá dữ liệu...........................................................................................19 1.5.1. Kỹ thuật khai phá dữ liệu mô tả.....................................................................................................19 1.5.2. Kỹ thuật khai phá dữ liệu dự đoán.................................................................................................19 1.6. Nhiêm vụ chính của khai phá dữ liệu...............................................................................19 1.6.1. Phân lớp (Classification)................................................................................................................20 1.6.2. Hồi quy (Regression).....................................................................................................................20 1.6.3. Gom nhóm (Clustering).................................................................................................................20 1.6.4. Tổng hợp (Summarization)...........................................................................................................20 1.6.5. Mô hình ràng buộc (Dependency modeling).................................................................................20 1.6.6. Dò tìm biến đổi và độ lệch (Change and Deviation Dectection)...................................................21 1.7. Các phương pháp khai phá dữ liệu...................................................................................21 1.7.1. Các thành phần của giải thuật khai phá dữ liệu.............................................................................21 1.7.2. Một số phương pháp khai thác dữ liệu phổ biến............................................................................22 1.7.2.1. Phương pháp quy nạp (Induction)..........................................................................................22 1.7.2.2. Cây quyết định và luật............................................................................................................22 1.7.2.3. Phát hiện các luật kết hợp.......................................................................................................22 1.7.2.4. Mạng Neuron..........................................................................................................................23 1.7.2.5. Giải thuật di truyền.................................................................................................................24 6 1.8. Ứng dụng của khai phá dữ liệu.........................................................................................24 1.9. Một số thách thức đặt ra cho việc khai phá dữ liệu.........................................................25 Chương II: TẬP PHỔ BIẾN VÀ LUẬT KẾT HỢP..........................................................27 2.1. Mở đầu................................................................................................................................27 2.2. Các khái niệm cơ bản.........................................................................................................27 2.2.1. Định nghĩa 2. 2.1: Ngữ cảnh khai phá dữ liệu...............................................................................27 2.2.2. Định nghĩa 2. 2. 2: Các kết nối Galois...........................................................................................27 2.2.3. Định nghĩa 2.2.3: Độ hỗ trợ (Support)...........................................................................................27 2.2.4. Định nghĩa 2 2.4: Độ tin cậy ( Confidence)...................................................................................28 2.2.4.1. Tính chất 2. 2.4.1: Hỗ trợ của tập con....................................................................................28 2.2.4.2. Tính chất 2.2.4.2.....................................................................................................................28 2.2.4.3. Tính chất 2.2.4.3.....................................................................................................................28 2.2.4.4. Tính chất 2. 2.4.4....................................................................................................................28 2.2.5. Định nghĩa 2.2.5: Tập mặt hàng phổ biến......................................................................................29 2.2.6. Định nghĩa 2.2.6: Luật kết hợp......................................................................................................29 2.2.6.1. Tính chất 2.2.6.1: Luật kết hợp không có hợp thành.............................................................29 2.2.6.2. Tính chất 2.2.6.2: Luật kết hợp không có tính tách................................................................29 2.2.6.3. Tính chất 2.2.6.3: Luật kết hợp không có tính bắc cầu..........................................................30 2.2.6.4. Tính chất 2.2.6.4 ....................................................................................................................30 2.3. Tìm tập phổ biến................................................................................................................30 2.3.1. Một số khái niệm............................................................................................................................30 2.3.2. Thuật toán Apriori..........................................................................................................................31 2.3.2.1. Mô tả thuật toán.....................................................................................................................31 2.3.2.2. Ví dụ minh hoạ cho thuật toán Apriori..................................................................................33 2.3.2.3. Procedure-Code.....................................................................................................................34 2.3.2.4. Tạo tập ứng viên (k+1)- hạng mục.........................................................................................35 2.4. Tìm luật kết hợp.................................................................................................................36 2.4.1. Phát biểu bài toán khai phá luật kết hợp........................................................................................36 2.4.2. Phát triển giải pháp hiệu quả trong khai thác luật kết hợp.............................................................38 2.5. Quy trình khai thác luật kết hợp.......................................................................................40 2.6. Một số thuật toán khác......................................................................................................40 2.6.1. Thuật toán khai phá song song cho luật kết hợp mờ......................................................................40 2.6.2. Thuật toán FP-Growth...................................................................................................................42 2.6.2.1 Bản chất...................................................................................................................................42 2.6.2.2. Qui trình.................................................................................................................................42 2.6.2.3. Thuật toán FP_Growth...........................................................................................................51 Chương III: CÀI ĐẶT VÀ THỬ NGHIỆM THUẬT TOÁN TÌM TẬP PHỔ BIẾN VÀ LUẬT KẾT HỢP.................................................................................................................52 3.1. Phát biểu bài toán...............................................................................................................52 3.2. Lựa chọn thuật toán để cài đặt phần mềm.......................................................................52 3.3. Yêu cầu khi cài đặt thuật toán...........................................................................................52 3.4. Cơ sở dữ liệu.......................................................................................................................53 3.4.1. Giao diện chính của cơ sở dữ liệu..................................................................................................53 3.4.2. Bảng danh mục các Nhà cung cấp hàng hóa..................................................................................54 3.4.3. Bảng danh mục các Hàng Hoá.......................................................................................................55 3.4.4. Bảng danh mục các Khách Hàng...................................................................................................56 3.4.5. Bảng danh mục các Hoá Đơn.........................................................................................................57 3.4.6. Bảng danh mục chi tiết Hoá Đơn...................................................................................................58 3.4.7. Ghi XML........................................................................................................................................59 3.5. Giao diện chính chương trình............................................................................................59 7 3.6. Kết nối dữ liệu....................................................................................................................60 3.7. Thêm dư liệu Xml..............................................................................................................60 3.8. Kết quả phân tích...............................................................................................................61 3.9. Kết quả lọc MinSup = 10...................................................................................................61 3.10. Kết quả lọc MinCon = 40%.............................................................................................62 KẾT LUẬN CHUNG..........................................................................................................63 HƯỚNG PHÁT TRIỂN ĐỀ TÀI........................................................................................64 TÀI LIỆU THAM KHẢO...................................................................................................65 BẢNG ĐỐI CHIẾU THUẬT NGỮ VIỆT - ANH.............................................................66 DANH SÁCH HÌNH VẼ Hình 1.1. Quá trình phát hiện tri thức từ cơ sở dữ liệu....................................................14 Hình 1.2. Quá trình phát hiện tri thức ..............................................................................15 Hình 1.3: Mô hình lợi ích của khai phá dữ liệu................................................................19 Hình 1.4.Thể hiện sơ đồ khai phá dữ liệu bằng mạng Neunon.......................................24 Hình 2.5. Minh họa luật kết hợp không có tính tách........................................................30 Hình 3.1. Giao diện chính của cơ sở dữ liệu.....................................................................53 Hình 3.2. Danh mục nhà cung cấp....................................................................................54 Hình 3.3. Danh mục hàng hóa...........................................................................................55 Hinh 3.4.Danh mục khách hàng........................................................................................56 Hình 3.5. Danh mục hóa đơn.............................................................................................57 Hình 3.6. Danh mục chi tiết hóa đơn.................................................................................58 Hình 3.7. Ghi XML.............................................................................................................59 8 Hình 3.8. Giao diện chính của chương trình....................................................................59 Hình 3.9. Kết nối dữ liệu....................................................................................................60 Hình 3.10. Thêm dư liệu XML .........................................................................................60 Hình 3.11. Kết quả phân tích.............................................................................................61 Hình 3.12. Kết quả lọc độ phổ biến tối thiểu.....................................................................61 Hình 3.13. Kết quả lọc độ tin cậy.......................................................................................62 DANH SÁCH BẢNG BIỂU Bảng 2.1. CSDL sử dụng minh hoạ thuật toán Apriori....................................................33 Bảng 2. 2. Kết quả thực hiện thuật toán Aprori cho CSDL D..........................................34 Bảng 2. 3. Ví dụ về một CSDL giao dịch – D.....................................................................37 Bảng 2.4. Tập mục thường xuyên Minsup = 50%.............................................................37 Bảng 2.5. Luật kết hợp sinh từ tập mục phổ biến ABE....................................................38 Bảng 2.6. Cây FP................................................................................................................43 Bảng 2.7. Cây FP................................................................................................................43 Bảng 2.8. Cây FP................................................................................................................44 Bảng 2.9. Cây FP................................................................................................................45 Bảng 2.10. Cây FP..............................................................................................................46 Bảng 2.11. Cây FP..............................................................................................................48 Bảng 2.12. Cây FP..............................................................................................................48 Bảng 2.13. Cây FP..............................................................................................................48 9 Bảng 2.14.Cơ sở dữ liệu......................................................................................................50 DANH SÁCH CÁC TỪ VIẾT TẮT Từ viết tắt KDD DL Diễn giải Phát hiện tri thức trong cơ sở dữ liệu Dữ liệu CSDL Cơ sở dữ liệu KPDL Khai phá dữ liệu NCKPDL LKH Ngữ cảnh khai phá dữ liệu Luật kết hợp 10 11 MỞ ĐẦU Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin trong nhiều lĩnh vực của đời sống, kinh tế xã hội trong nhiều năm qua cũng đồng nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một nhiều lên. Họ lưu trữ các dữ liệu này vì cho rằng trong nó ẩn chứa những giá trị nhất định nào đó. Tuy nhiên, theo thống kê thì chỉ có một lượng nhỏ của những dữ liệu này (khoảng từ 5% đến 10%) là luôn được phân tích, số còn lại họ không biết sẽ phải làm gì hoặc có thể làm gì với chúng nhưng họ vẫn tiếp tục thu thập rất tốn kém với ý nghĩ lo sợ rằng sẽ có cái gì đó quan trọng đã bị bỏ qua sau này có lúc cần đến nó. Các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống không đáp ứng được kỳ vọng này, nên đã ra đời Kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining). Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng. Hiện nay có rất nhiều phương pháp để kinh doanh cũng như có rất nhiều phần mềm để quản lý việc kinh doanh đó. Ví dụ như phần mềm quản lý bán hàng tại thị siêu bằng Fox, C#, VB,...Tuy nhiên đề tài này chúng em không xây dựng một phần mềm quản lý bán hàng tại thị siêu hoàn chỉnh mà chỉ tìm hiểu và cài đặt một khía cạnh nhỏ trong bài toán Quản lý bán hàng tại siêu thị . Đó là phân tích dữ liệu bằng luật kết hợp trong quá trình tìm hiểu các mặt hàng có liên quan tới nhau như thế nào? Giúp cho nhà quản lý tìm hiểu, phân tích để lựa chọn các mặt hàng kinh doanh tốt hơn. Trong phạm vi của đề tài nghiên cứu này, chúng em xin được trình bày: Những kiến thức về khai phá dữ liệu sử dụng luật kết hợp. Đây là dạng luật kết hợp tương đối đơn giản nhưng tính hiệu quả cao, giúp tìm ra được những luật “quý hiếm”. Đưa ra các định nghĩa, tính chất và một số thuật toán cơ bản thường được áp dụng trong quá trình tìm luật kết hợp của một cơ sở dữ liệu. Phân tích và cài đặt thuật toán Apriori áp dụng vào một phần nhỏ trong bài toán Quản lý bán hàng tại siêu thị . 12 Chương I: TỔNG QUAN VỀ KHAI PHÁI DỮ LIỆU 1.1. Đặt vấn đề Trong kỉ nguyên Internet, Intranets, Warehouses, đã mở ra nhiều cơ hội cho những nhà doanh nghiệp trong việc thu thập và xử lý thông tin. Hơn nữa, các công nghệ lưu trữ và phục hồi dữ liệu phát triển một cách nhanh chóng vì thế cơ sở dữ liệu ở các cơ quan, doanh nghiệp, đơn vị ngày càng nhiều thông tin tiềm ẩn phong phú và đa dạng. Cơ sở dữ liệu trong các doanh nghiệp thì dữ liệu giao dịch đóng một vai trò rất quan trọng cho việc hoạch định kế hoạch kinh doanh trên thương trường vào những năm tiếp theo. Hiện tại, việc sử dụng các dữ liệu này tuy đã đạt được một số kết quả nhất định song vẫn còn một số vấn đề tồn đọng như: - Dựa hoàn toàn vào dữ liệu, không sử dụng tri thức có sẳn về lĩnh vực, kết quả phân tích khó có thể làm rõ được. - Phải có sự hướng dẫn của người dùng để xác định phân tích dữ liệu như thế nào và ở đâu. Trong điều kiện và yêu cầu của xã hội, đòi hỏi phải có những phương pháp nhanh, phù hợp, tự động, chính xác và có hiệu quả để lấy được thông tin có giá trị. Các tri thức chiết xuất được từ cơ sở dữ liệu trên sẽ là một nguồn tài liệu hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hoặc trong việc ra quyết định sản xuất kinh doanh. Vì vậy, tính ứng dụng của khai phá dữ liệu bằng luật kết hợp từ cơ sở dữ liệu giao dịch là một vấn đề đang được quan tâm đặc biệt trong xã hội hiện nay. Mục đích của việc nghiên cứu là xây dựng một giải pháp hiệu quả tính ứng dụng luật kết hợp trong việc ra quyết định của cơ quan doanh nghiệp dựa trên cơ sở dữ liệu giao dịch. Sự phát triển nhanh chóng các ứng dụng công nghệ thông tin và Internet vào nhiều lĩnh vực đời sống xã hội, quản lý kinh tế, khoa học kỹ thuật,... Đã tạo ra nhiều cơ sở dữ liệu khổng lồ ví dụ như cơ sở dữ liệu bán hàng của một siêu thị chứa hàng nghìn giao tác bán hàng; hay cơ sở dữ liệu của một hệ thống thông tin về khách hàng trong một ngân hàng,... Để khai phá hiệu quả nguồn thông tin từ các cơ sở dữ liệu lớn hỗ trợ tiến trình ra quyết định, bên cạnh các phương pháp khai thác thông tin truyền thống, các nhà nghiên cứu đã phát triển các phương pháp, kỹ thuật và phần mềm mới hỗ trợ tiến trình khai phá, phân tích tổng hợp thông tin. Có rất nhiều kỹ thuật khai phá dữ liệu khác nhau tuân theo các bước quá trình phát hiện tri thức, để giải quyết các nhiệm vụ để khai phá dữ liệu. Sau đây chúng em sẽ lần lượt trình bày những vẫn đề đã nêu ra. 13 1.2. Khai phá dữ liệu và phát hiện tri thức Yếu tố thành công trong mọi hoạt động kinh doanh ngày nay là việc biết sử dụng thông tin có hiệu quả. Điều đó có nghĩa là từ các dữ liệu có sẵn phải tìm ra những thông tin tiềm ẩn mà trước đó chưa được phát hiện, tìm ra những xu hướng phát triển và những yếu tố tác động lên chúng. Thực hiện công việc đó chính là quá trình phát hiện tri thức trong cơ sở dữ liệu mà trong đó kỹ thuật cho phép ta lấy được các tri thức chính ra từ kỹ thuật khai phá dữ liệu. Nếu quan niệm tri thức là mối quan hệ của các mẫu giữa các phần tử dữ liệu thì quá trình phát hiện tri thức chỉ toàn bộ quá trình triết xuất tri thức từ cơ sở dữ liệu, trong đó trải qua nhiều giai đoạn khác nhau như: Tìm hiểu và phát hiện vẫn đề, thu thập và tiền xử lý dữ liệu, phát hiện tri thức, minh hoạ và đánh giá tri thức đã phát hiện và đưa kết quả vào thực tế. Khai phá dữ liệu có những điểm khác nhau về mặt ngữ nghĩa so với phát hiện tri thức từ cơ sở dữ liệu nhưng thực tế ta thấy khai phá dữ liệu là chỉ một giai đoạn phát hiện tri thức trong một chuỗi các giai đoạn quá trình phát hiện tri thức trong cơ sở dữ liệu. Tuy nhiên đây là giai đoạn đóng vai trò chủ chốt và là giai đoạn chính tạo nên tính đa ngành của phát hiện tri thức trong cơ sở dữ liệu. 1.3. Quá trình phát hiện tri thức từ cơ sở dữ liệu Phát hiện tri thức từ cơ sở dữ liệu là một quá trình có sử dụng nhiều phương pháp và công cụ tin học nhưng vẫn là một quá trình mà trong đó con người làm trung tâm. Do đó nó không phải là một hệ thống phân tích tự động mà là một hệ thống bao gồm nhiều hoạt động tương tác thường xuyên giữa con người và cơ sở dữ liệu, tất nhiên là với sự hỗ trợ của các công cụ tin học. Hình 1.1. Quá trình phát hiện tri thức từ cơ sở dữ liệu Mặc dù có 5 giai đoạn như trên( hình 1.1) xong quá trình phát hiện tri thức từ cơ sở dữ liệu là 1 quá trình tương tác và lặp đi lặp lại theo kiểu xoắn chôn ốc, trong đó 14 lần lặp sau hoàn chỉnh hơn lần lặp trước. Ngoài ra giai đoạn sau lại dựa trên kết quả thu được của giai đoạn trước theo kiểu thác nước. Đây là một quá trình biện trứng mang tính chất học của quá trình phát hiện trí thức và là phương pháp luận trong viện phát hiện tri thức. Các giai đoạn đó sẽ được trình bày cụ thể như sau: 1.3.1. Xác định bài toán Đây là một quá trình mang tính định hình với mục đích xác định được lĩnh vực yêu cầu phát hiện tri thức và xây dựng bài toán tổng kết. Trong thực tế các cơ sở dữ liệu được chuyên môn hoá và phân chia theo các lĩnh vực khác nhau như: Sản phẩm, kinh doanh, tài chính, v.v.Với mỗi tri thức phát hiện được có thể có giá trị trong lĩnh vực này nhưng lại không mang nhiều ý nghĩa với một lĩnh vực khác. Vì vậy việc xác định lĩnh vực và định nghĩa bài toán giúp định hướng cho giai đoạn tiếp theo thu thập và tiền xử lý dữ liệu. 1.3.2. Thu thập và tiền xử lý Các cơ sở dữ liệu thu được thường chứa rất nhiều thuộc tính nhưng lại không đầy đủ, không thuần nhất, có nhiều lỗi và các giá trị đặc biệt. Vì vậy giai đoạn thu thập và tiền xử lý dữ liệu trở nên rất quan trọng trong quá trình phát hiện tri thức từ cơ sở dữ liệu. Có thể nói giai đoạn này chiếm từ 70%-80% giá thành trong toàn bộ bài toán. Người ta chia giai đoạn và tiền xử lý dữ liệu như: Gom dữ liệu, chọn dữ liệu, làm sạch, mã hoá dữ liệu, làm giàu, đánh giá và trình diễn dữ liệu. Các công đoạn này được thực hiện theo trình tự nhất định cụ thể như sau: Hình 1.2. Quá trình phát hiện tri thức 15 1.3.2.1. Gom dữ liệu Tập hợp dữ liệu là bước đầu tiên trong quá trình khai phá dữ liệu. Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. 1.3.2.2. Chọn lọc dữ liệu Ở giai đoạn này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó. Đây là giai đoạn chọn lọc, trích rút các dữ liệu cần thiết tứ cơ sở dữ liệu tác nghiệp vào một cơ sở dữ liệu riêng. Chúng ta chọn ra những dữ liệu cần thiết cho các giai đoạn sau. Tuy nhiên công việc thu gom dữ liệu vào một cơ sở dữ liệu thường rất kho khăn vì dữ liệu nằm rải rác khắp nơi trong cơ quan, tổ chức cùng một loại thông tin, nhưng được tạo lập theo các dạng hình thức khác nhau. Ví dụ nơi này dùng kiểu chuỗi, nơi kia lại dùng kiểu số để khai báo một thuộc tính nào đó của khách hàng. Đồng thời chất lượng dữ liệu của các nơi cũng không giống nhau. Vì vậy chúng ta cần chọn lọc dữ liệu thật tốt để chuyển sang giai đoạn tiếp theo 1.3.2.3. Làm sạch Giai đoan thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường mắc phải trong khi gom dữ liệu là tính không đủ chặt chẻ, logíc. Vì vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được “làm sạch - tiền xử lý - chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch nghiệm trọng. Giai đoạn này thực hiện một số chức năng sau: - Điều hoà dữ liệu: Công việc này nhằm giảm bớt tính không nhất quán dữ liệu lấy từ nhiều nguồn khác nhau. Phương pháp thông thường là khử các trường hợp trùng lặp dữ liệu và thống nhất các ký hiệu. Ví dụ một khách hàng có thể có nhiều bản ghi do việc nhập sai tên hoặc do quá trình thay đổi một số thông tin cá nhân gây ra và tạo ra sự nhầm lẫn là có nhiều khách hàng. - Xử lý các giá trị khuyết: Tính không đầy đủ của dữ liệu có thế gây ra hiện tượng dữ liệu chứa các giá trị khuyết. Đây là hiện tượng khá phổ biến. Người ta sử dụng nhiều phương pháp khác nhau để xứ lý các giá trị khuyết như: Bỏ qua các bộ có giá trị khuyết, điểm bổ sung bằng tay, dùng một hằng chung để bổ sung vào giá trị khuyết, dùng giá trị trung bình của mọi bản ghi trên thuộc tinh khuyết, dùng giá trị trung bình của mọi bản ghi cùng lớp hoặc dùng các giá trị mà tần suất xuất hiện lớn nhất. 16 - Xử lý nhiễu và các ngoại lệ: Thông thường nhiễu dữ liệu có thể là nhiễu ngẫu nhiên hoặc các giá trị bất bình thường. Để làm sạch nhiễu, người ta có thể sử dụng phương pháp làm trơn nhiễu hoặc dùng các giải thuật phát hiện ra các ngoại lệ để xử lý. 1.3.2.4. Làm giàu dữ liệu Mục đích của giai đoạn này là bổ sung thêm nhiều loại thông tin có liên quan vào cơ sở dữ liệu gốc. Để làm được điêu này, chúng ta phải có các cơ sở dữ liệu khác ở bên ngoài có liên quan tới cơ sở dữ liệu gốc ban đầu. Ta tiến hành bổ sung những thông tin cần thiết, làm tăng khả năng khám phá tri thức. Đây là bước mang tính tư duy trong khai phá dữ liệu.Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để trích ra các mẫu từ dữ liệu. Thuật toán thường dùng là nguyên tắc phân loại, nguyên tắc kết hợp hoặc các mô hình dữ liệu tuần tự, v. v. Quá trình làm giàu bao gồm việc tích hợp và chuyển đổi dữ liệu. Các dữ liệu từ nhiều nguồn khác nhau được tích hợp thành một kho thông nhất. Các khuôn dạng khác nhau của dữ liệu cũng được quy đổi, tính toán lại để đưa về một kiểu thống nhất, tiện cho quá trình phân tích. 1.3.2.5. Mã hoá dữ liệu Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra có thể sử dụng và điều khiển được bởi việc tổ chức lại nó. Dữ liệu đã được chuyển đổi phù hợp với mục đích khai thác. Mục đích của giai đoạn này là chuyển đổi kiểu dữ liệu về những dạng thuật tiện để tiến hành các thuật toán khám phá dữ liệu. Có nhiều cách mã hoá dữ liệu như: - Phân vùng: Dữ liệu là giá trị chuỗi, nằm trong các tập các chuỗi cố đinh. - Biến đổi giá trị năm thành con số nguyên là số năm đã trôi qua so với năm hiện hành. - Chia giá trị số theo một hệ số để tập các giá trị nằm trong vùng nhỏ hơn. - Chuyển đổi Yes-No thành 0-1. 1.3.2.6. Đánh giá và trình diễn Đây là giai đoạn cuối trong quá trình khai phá dữ liệu.Ở giai đoạn này, các mẫu dữ liệu được chiết xuất ra bởi phần mềm khai phá dữ liệu. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức cần chiết xuất ra. Trên đây là 6 giai đoạn trong quá trình khai phá dữ liệu. 17 1.3.3. Khai phá dữ liệu Giai đoạn khai thác dữ liệu được bắt đầu sau khi dữ liệu đã được thu thập và tiến hành xử lý. Trong giai đoạn này, công việc chủ yếu là xác định được bài toán khai phá dữ liệu, tiến hành lựa chọn các phương pháp khai thác phù hợp với dữ liệu có được và tách ta các tri thức cần thiết. Là giai đoạn thiết yếu, trong đó các phương pháp thông minh sẽ được áp dụng để trích xuất ra các mẩu dữ liệu. 1.3.4. Phát biểu và đánh giá kết quả Các tri thức phát hiện từ cơ sở dữ liệu cần được tổng hợp dưới dạng các báo cáo phục vụ cho các mục đích hỗ trợ các quyết định khác nhau. Do nhiều phương pháp khai thác có thể được áp dụng nên các kết quả có mức độ tốt, xấu khác nhau. Việc đánh giá các kết quả thu được là cần thiêt, Các tri thức phát hiện từ cơ sở dữ liệu cần được tổng hợp dưới dạng các báo cáo phục vụ cho các mục đích hỗ trợ các quyết định khác nhau. Do nhiều phương pháp khai thác có thể được áp dụng nên các kết quả có mức độ tốt, xấu khác nhau. Việc đánh giá các kết quả thu được là cần thiêt, giúp tạo cơ sở cho những quyết định chiến lược. Thông thường, chúng được tổng hợp, so sánh bằng các biểu đồ và được kiểm nghiệm, tin hoc. 1.3.5. Sử dụng tri thức đã phát hiện Củng cố, tinh chế các tri thức đã được phát hiện. Kết hợp các tri thức thành hệ thống. Giải quyết các xung đột tiềm tàng trong tri thức khai thác được. Sau đó tri thức được chuẩn bị sẵn sàng cho ứng dụng. Các kết quả của quá trình phát hiện tri thức có thể được đưa vào ứng dụng trong những lĩnh vực khác nhau. Do các kết quả có thể là các dự báo hoặc các mô tả nên chúng có thể được đưa vào các hệ thống hỗ trợ ra quyết định nhằm tự động hoá quá trình này. 1.4. Khai phá dữ liệu có những lợi ích gì - Cung cấp tri thức hỗ trợ ra quyết định. - Dự báo. - Khái quát dữ liệu. Hình 1.3 Là một mô hình thể hiện lợi ích của KPDL trong việc phân tích và ra quyết định cho việc ra tiếp thị của một loại sản phẩm nào đó 18 Tiếp thị CSDL Tiếp thị Nhà kho dữ liệu KDD & Data Mining Hình 1.3: Mô hình lợi ích của khai phá dữ liệu 1.5. Các kỹ thuật khai phá dữ liệu Kỹ thuật khai phá dữ liệu thường được chia làm 2 nhóm chính: 1.5.1. Kỹ thuật khai phá dữ liệu mô tả Có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Các kỹ thuật này gồm có: Phân cụm (clustering), tóm tắt (summerization), trực quan hoá (visualiztion), phân tích sự phát triển và độ lệch (Evolution and deviation analyst), phân tích luật kết hợp (association rules).v.v. 1.5.2. Kỹ thuật khai phá dữ liệu dự đoán Có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Các kỹ thuật này gồm có: Phân lớp (classification), hồi quy (regression)… 1.6. Nhiêm vụ chính của khai phá dữ liệu Rõ ràng rằng mục đích của khai phá dữ liệu là các tri thức chiết xuất được sẽ được sử dụng cho lợi ích cạnh tranh trên thương trường và các lợi ích trong nghiên cứu khoa học. Do đó, ta có thể coi mục đích chính của khai thác dữ liệu sẽ là mô tả và dự đoán. Các mẫu mà khai phá dữ liệu phát hiện được nhằm vào mục đích này. Dự đoán liên quan đến việc sử dụng các biến hoặc các trường trong cơ sở dữ liệu để chiết xuất ra các mẫu là các dự đoán những giá trị chưa biết hoặc những giá trị trong tương lai của các biến đáng quan tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có thể hiểu được. Để đạt được hai mục đích này, nhiệm vụ chính của khai phá dữ liệu là: - Phân lớp (Classification). - Hồi qui (Regression). - Gom nhóm (Clustering). 19 - Tổng hợp (Summarization). - Mô hình ràng buộc (Dependency modeling). - Dò tìm biến đổi và độ lệch (Change and Deviation Dectection). 1.6.1. Phân lớp (Classification) Phân lớp là việc phân loại một mẫu dữ liệu vào một trong số các lớp đã xác định. Mục tiêu của thuật toán phân lớp là tìm ra các mối quan hệ nào đó giữa các thuộc tính dự báo và thuộc tính phân lớp, từ đó sử dụng mối quan hệ này để dự báo lớp cho các bộ dữ liệu mới khác cùng khuông dạng. 1.6.2. Hồi quy (Regression) Hồi quy là việc l ọ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. Có rất nhiều ứng dụng khai phá dữ liệu với nhiệm vụ hồi quy, ví dụ như biết các phép đo vi sóng từ xa, đánh giá khả năng tử vong của bệnh nhân biết các kết quả xét nghiệm chẩn đoán, dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chỉ tiêu quảng cáo, v. v. 1.6.3. Gom nhóm (Clustering) Là việc mô tả chung để tìm ra các tập xác định các nhóm hay các loại để mô tả dữ liệu. Các nhóm có thể tách riêng nhau hoặc phân cấp hoặc gối lên nhau. Có nghĩa là một dữ liệu có thể vừa thuộc nhóm này, vừa thuộc nhóm kia. Các ứng dụng khai phá dữ liệu có nhiệm vụ gom nhóm như: Phát hiện tập các khách hàng có phản ứng giống nhau trong cơ sở dữ liệu tiếp thị, xác định các loại quang phổ từ các phương pháp đo tia hồng ngoại. 1.6.4. Tổng hợp (Summarization) Nhiệm vụ tổng hợp là việc sản sinh ra các mô tả đặc trưng cho một lớp. Các mô tả này là một kiểu tổng hợp, tóm tắt mô tả các đặc tính chung của tất cả các bộ dữ liệu dạng giỏ mua hàng thuộc một lớp. Các mô tả đặc trưng thể hiện dưới dạng các luật thường có khuôn dạng: “Nếu một bộ dữ liệu thuộc về một lớp đã chỉ ra trong tiền đề, thì bộ dữ liệu đó có tất cả các thuộc tính đã nêu trong kết luận”. Những luật này có những đặc trưng khác biệt so với các luật phân lớp. Luật phát hiện đặc trưng cho một lớp chỉ được sản sinh khi các bộ dữ liệu thuộc về lớp đó. 1.6.5. Mô hình ràng buộc (Dependency modeling) Bao gồm việc tìm kiếm một mô hình mô tả sự phụ thuộc đáng kể giữa các biến. Các mô hình phụ thuộc tồn tại dưới hai mức: Mức cấu trúc của mô hình xác định các biến nào là phụ thuộc cục bộ với nhau, mức định lượng của một mô hình xác định độ mạnh của sự phụ thuộc theo một thước đo nào đó. 20