Đề tài 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 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. 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 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. 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 FP- Tree 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. MỤC LỤC 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 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 44 Bảng 2.8. Cây FP 45 Bảng 2.9. Cây FP 46 Bảng 2.10. Cây FP 47 Bảng 2.11. Cây FP 48 Bảng 2.12. Cây FP 48 Bảng 2.13. Cây FP 49 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 Diễn giải KDD Phát hiện tri thức trong cơ sở dữ liệu DL Dữ liệu CSDL Cơ sở dữ liệu KPDL Khai phá dữ liệu NCKPDL Ngữ cảnh khai phá dữ liệu LKH Luật kết hợp 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ị . 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. 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 đó 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 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. - 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. 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 đó Tiếp thị CSDL Tiếp thị KDD & Data Mining Nhà kho dữ liệu 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). - 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 đó. 1.6.6. Dò tìm biến đổi và độ lệch (Change and Deviation Dectection) Tập trung vào khai thác những thay đổi đáng kể nhất trong dữ liệu từ các giá trị chuẩn hoặc được đo trước đó. Vì các nhiệm vụ khác nhau này yêu cầu số lượng và các dạng thông tin rất khác nhau nên chúng thường ảnh hưởng đến việc thiết kế và chọn giải thuật khai phá dữ liệu khác nhau. Ví dụ như giải thuật tạo cây quyết định tạo ra được một mô tả phân biệt được các mẫu giữa các lớp nhưng không có các tính chất và đặc điểm của lớp. 1.7. Các phương pháp khai phá dữ liệu Quá trình khai phá dữ liệu là quá trình phát hiện mẫu, trong đó, giải thuật khai phá dữ liệu tìm kiếm các mẫu đáng quan tâm theo dạng xác định như các luật, cây phân lớp, hồi quy, gom nhóm, v. v. 1.7.1. Các thành phần của giải thuật khai phá dữ liệu Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: biểu diễn mô hình, đánh giá mô hình, tìm kiếm mô hình. • Biểu diễn mô hình: Mô hình được biểu diễn bằng một ngôn ngữ L để mô tả các mẫu có thể khai thác được. Tức là người phân tích dữ liệu cần phải hiểu đầy đủ các giả thiết mô tả và cần phải diễn tả được các giả thiết mô tả nào được tạo ra bởi giải thuật. Mô hình đó sẽ được đánh giá bằng cách đưa các dữ liệu thử vào mô hình và thay đổi lại các tham số cho phù hợp nếu cần. • Đánh giá mô hình: Đánh giá xem một mẫu có đáp ứng được các tiêu chuẩn của quá trình phát hiện tri thức hay không. Việc đánh giá độ chính xác dự đoán dựa trên đánh giá chéo (Cross Validation). Đánh giá chất lượng mô tả liên quan đến độ chính xác dự đoán, độ mới, khả năng sử dụng, khả năng hiểu được của mô hình. Cả hai chuẩn thống kê và chuẩn logic đều có thể được sử dụng để đánh giá mô hình. • Phương pháp tìm kiếm: Phương pháp tìm kiếm bao gồm hai thành phần: tìm kiếm tham số và tìm kiếm mô hình. - Tìm kiếm tham số: Để tối ưu hóa các tiêu chuẩn đánh giá mô hình với các dữ liệu quan sát được và với một mô tả mô hình đã định. - Tìm kiếm mô hình: Xảy ra giống như một vòng lặp qua phương pháp tìm kiếm tham số: Mô tả mô hình bị thay đổi tạo nên một họ các mô hình. = > Với mỗi một mô tả mô hình, phương pháp tìm kiếm tham số được áp dụng để đánh giá chất lượng mô hình. Các phương pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm kiếm heuristic vì kích thước của không gian các mô hình có thể thường ngăn cản các tìm kiếm tổng thể, hơn nữa các giải pháp đơn giản không dễ đạt được. 1.7.2. Một số phương pháp khai thác dữ liệu phổ biến 1.7.2.1. Phương pháp quy nạp (Induction). Một cơ sở dữ liệu là một kho thông tin nhưng các thông tin quan trọng hơn cũng có thể được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực hiện việc này là suy diễn và quy nạp. • Phương pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các thông tin trong cơ sở dữ liệu. Phương pháp suy diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết xuất được bằng cách sử dụng phương pháp này thường là các luật suy diễn. • Phương pháp quy nạp: .Phương pháp quy nạp suy ra các thông tin được sinh ra từ cơ sở dữ liệu. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không phải bắt đầu với các tri thức đã biết trước. Các thông tin mà phương pháp này đem lại là các thông tin hay các tri thức cấp cao diễn tả về các đối tượng trong cơ sở dữ liệu. Phương pháp này liên quan đến việc tìm kiếm các mẫu trong CSDL. Trong khai phá dữ liệu, quy nạp được sử dụng trong cây quyết định và tạo luật. 1.7.2.2. Cây quyết định và luật • Cây quyết định: Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một số lớp nhất định. Các nút của cây được gán nhãn là tên các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá mô tả các lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây, qua các cạnh tương ứng với các giá trị, thuộc tính của đối tượng tới lá. • Tạo luật: Các luật được tạo ra nhằm suy diễn một số mẫu dữ liệu có ý nghĩa về mặt thống kê. Các luật có dạng Nếu P thì Q, với P là mệnh đề đúng với một phần trong CSDL, Q là mệnh đề dự đoán. Cây quyết định và luật có ưu điểm là hình thức mô tả đơn giản, mô hình suy diễn khá dễ hiểu đối với người sử dụng. Tuy nhiên, giới hạn của nó là mô tả cây và luật chỉ có thể biểu diễn được một số dạng chức năng và vì vậy giới hạn về cả độ chính xác của mô hình. 1.7.2.3. Phát hiện các luật kết hợp Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm được. Ta có thể lấy một ví dụ đơn giản về luật kết hợp như sau: sự kết hợp giữa hai thành phần A và B có nghĩa là sự xuất hiện của A trong bản ghi kéo theo sự xuất hiện của B trong cùng bản ghi đó: A = > B. Việc phát triển một thuật toán phải phát hiện luật này trong cơ sở dữ liệu lớn là không khó. Tuy nhiên, vấn đề là ở chỗ có thể có rất nhiều luật kiểu này hoặc là ta chỉ biết một tập nhỏ dữ liệu trong cơ sở dữ liệu lớn thoả mãn tiền đề của luật. Ví dụ chỉ có số ít người mua sách tiếng anh mà mua thêm đĩa CD. Số lượng các luật kết hợp trong một số cơ sở dữ liệu lớn gần như vô hạn. Do vậy thuật toán sẽ không thể phát hiện hết các luật và không phân biệt được luật nào là thông tin thực sự có giá trị và thú vị. Vậy chúng ta đặt ra câu hỏi là luật kết hợp nào là thực sự có giá trị? Chẳng hạn ta có luật: Âm nhạc, ngoại ngữ, thể thao = > CD, nghĩa là những người mua sách âm nhạc, ngoại ngữ, thể thao thì cũng mua đĩa CD. Lúc đó ta quan tâm đến số lượng trường hơp khách hàng thoả mãn luật này trong cơ sở dữ liệu hay độ hỗ trợ cho luật này. Độ hỗ trợ cho luật chính là phần trăm số bản ghi có cả sách âm nhạc, ngoại ngữ, thể thao và đĩa CD hay tất cả những người thích cả ba loại sách trên. Tuy nhiên giá trị hỗ trợ là không đủ. Có thể có trường hợp ta có một nhóm tương đối những người đọc cả ba loại sách trên nhưng lại có một nhóm với lượng lớn hơn những người thích sách thể thao, âm nhạc, ngoại ngữ mà không thích mua đĩa CD. Trong trường hợp này tính kết hợp rất yếu mặc dù độ hỗ trợ tương đối cao. Như vậy chúng ta cần thêm một độ đo thứ hai đó là độ tin cây (Confidence). Độ tin cậy là phần trăm các bản ghi có đĩa CD trong số các bản ghi có sách âm nhạc, thể thao, ngoại ngữ. Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật dạng X => B sao cho tần số của luật không nhỏ hơn ngưỡng Minsup cho trước và độ tin cậy của luật không nhỏ hơn ngưỡng Minconfi cho trước. Từ một cơ sở dữ liệu ta có thể tìm được hàng nghìn và thậm chí hàng trăm nghìn các luật kết hợp. 1.7.2.4. Mạng Neuron Mạng Neuron là tiếp cận tính toán mới liên quan tới việc phát triển cấu trúc toán học và khả năng học. Các phương pháp là kết quả của việc nghiên cứu mô hình học của hệ thống thần kinh con người. Mạng Neuron có thể đưa ra ý nghĩa từ các dữ liệu phức tạp hoặc không chính xác và có thể được sử dụng để chiết xuất các mẫu và phát hiện ra các xu hướng quá phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được. Khi đề cập đến khai thác dữ liệu, người ta thường đề cập nhiều đến mạng Neuron. Tuy mạng Neuron có một số hạn chế gây khó khăn trong việc áp dụng và phát triển nhưng nó cũng có những ưu điểm đáng kể. Hình 1.4.Thể hiện sơ đồ khai phá dữ liệu bằng mạng Neunon. Một trong số những ưu điểm phải kể đến của mạng Neuron là khả năng tạo ra các mô hình dự đoán có độ chính xác cao, có thể áp dụng được cho rất nhiều loại bài toán khác nhau, đáp ứng được nhiệm vụ đặt ra của khai phá dữ liệu như phân lớp, gom nhóm, mô hình hóa, dự báo các sự kiện phụ thuộc vào thời gian, v.v. 1.7.2.5. Giải thuật di truyền Giải thuật di truyền, nói theo nghĩa rộng là mô phỏng lại hệ thống tiến hóa trong tự nhiên, chính xác hơn đó là giải thuật chỉ ra tập các cá thể được hình thành, được ước lựợng và biến đổi như thế nào? Ví dụ như xác định xem làm thế nào để lựa chọn các cá thể tạo giống và lựa chọn các cá thể nào sẽ bị loại bỏ. Giải thuật cũng mô phỏng lại yếu tố gen trong nhiễm sắc thể sinh học trên máy tính để có thể giải quyết nhiều bài toán thực tế khác nhau. Giải thuật di truyền là một giải thuật tối ưu hóa. Nó được sử dụng rất rộng rãi trong việc tối ưu hóa các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng Neuron. Sự liên hệ của nó với các quá trình khai phá dữ liệu. Ví dụ như trong kỹ thuật cây quyết định, tạo luật. Như đã đề cập ở phần trước, các luật mô hình hóa dữ liệu chứa các tham số được xác định bởi các giải thuật phát hiện tri thức. Giai đoạn tối ưu hóa là cần thiết để xác định xem các giá trị tham số nào tạo ra các luật tốt nhất. Và vì vậy mà giải thuật di truyền đã được sử dụng trong các công cụ khai phá dữ liệu. 1.8. Ứng dụng của khai phá dữ liệu Khai phá dữ liệu là một lĩnh vực liên quan tới nhiều ngành học khác như: Hệ CSDL, thống kê, trực quan hoá.v.v. Hơn nữa, tuỳ vào cách tiếp cận được sử dụng, khai phá dữ liệu còn có thể áp dụng một số kỹ thuật như mạng nơron, lý thuyết tập thô, tập mờ, biểu diễn tri thức, v.v.So với các phương pháp này, khai phá dữ liệu có một số ưu thế rõ rệt. So với phương pháp học máy, khai phá dữ liệu có lợi thế hơn ở chỗ, khai phá dữ liệu có thể sử dụng với các CSDL chứa nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục. Trong khi đó phương pháp học máy chủ yếu được áp dụng trong các CSDL đầy đủ, ít biến động và tập dữ liệu không qua lớn. Phương pháp hệ chuyên gia: Phương pháp này khác với khai phá dữ liệu ở chỗ các ví dụ của chuyên gia thường ở mức cao hơn nhiều so với các dữ liệu trong CSDL, và chúng thường chỉ bao hàm được các trường hợp quan trọng. Hơn nữa các chuyên gia sẽ xác nhận giá trị và tính hữu ích của các mẫu phát hiện được. Phương pháp thống kê là một trong những nên tảng lý thuyết của khai phá dữ liệu, nhưng khi so sánh hai phương pháp với nhau ta có thể thấy các phương pháp thống kê còn tồn tại một số điểm yếu mà khai phá dữ liệu khắc phục được. Các phương pháp thống kê chuẩn không phù hợp với các kiểu dữ liệu có cấu trúc trong rất nhiều CSDL. Các phương pháp thống kê hoạt động hoàn toàn theo dữ liệu, nó không sử dụng tri thức có sẵn về lĩnh vực. Kết quả phân tích của hệ thống sẽ rất nhiều và khó có thể làm rõ ra được. Phương pháp thống kê cần 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. Với nhưng ưu điểm đó, khai phá dữ liệu hiện đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực kinh doanh và đời sống khác nhau như: Marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet.v.v.rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và thu được những lợi ích to lớn. Một số ứng dụng của khai phá dữ liệu trong lĩnh vực kinh doanh: Brandaid: Mô hình Marketing linh hoạt tập chung vào hàng tiêu dùng. Callpla: Giúp nhân viên bán hàng xác định số lần viếng thăm của khách hàng triển vọng và khách hàng hiện có. Detailer: Xác định khách hàng nào nên viếng thăm và sản phẩm nào nên giới thiệu trong từng chuyến viếng thăm. Geoline: Mô hình thiết kế địa bàn tiêu thụ và dịch vụ. Mediac: Giúp người quảng cáo mua phương tiện trong một năm, lập kế hoạch sử dụng phương tiện bao gồm phác hoạ khúc thị trường, ước tính tiềm năng. 1.9. Một số thách thức đặt ra cho việc khai phá dữ liệu Các cơ sở dữ liệu lớn. Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù hợp nữa. Dữ liệu bị thiếu hoặc nhiễu. Quan hệ giữa các trường phức tạp. Giao tiếp với người sử dụng và kết hợp với các tri thức đã có. Tích hợp với các hệ thống khác… * Kết luận chương I Qua chương I chúng ta đã biết được thế nào là tổng quan về khai phá dữ liệu. Nó bao gồm một số nội dung sau: Khai phá dữ liệu và phát hiện tri thức: Là quá trình khám phá tri thức tiềm ẩn trong cơ sở dữ liệu. Quá trình 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 để tìm ra một cơ sở dữ liệu có ích cho người sử dụng. Khai phá dữ liệu có lợi ích gì: Cung cấp tri thức và hỗ trợ việc ra quyết định, dự báo, khái quát dữ liệu. Các kỹ thuật khai phá dữ liệu: Có rất nhiều các kỹ thuật nhưng thường sử dụng kỹ thuật mô tả và dự đoán. Nhiệm vụ của khai phá dữ liệu: Phân lớp, hồi quy, gom nhóm, tổng hợp, mô hình ràng buộc, dò tìm biến đổi và độ lệch. Các phương pháp khai phá dữ liệu: Phương pháp quy nạp, cây quyết định và luật, phát hiện các luật kết hợp, mạng Neuron, giải thuật di truyền. Ứng dụng của khai phá dữ liệu: Marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet… Một số thách thức đặt ra cho việc khai phá dữ liệu: Cơ sở dữ liệu lớn, dữ liệu bị thiếu hoặc nhiễu, quan hệ giữa các trường phức tạp.v.v. Chương II: TẬP PHỔ BIẾN VÀ LUẬT KẾT HỢP 2.1. Mở đầu Hiện nay các công ty, doanh nghiệp đang lưu trữ một lượng thông tin lớn về bán hàng. Một bản ghi trong cơ sở dữ liệu này chứa các thông tin về ngày mua bán, số lượng hàng bán,... Từ cơ sở dữ liệu bán hàng, chúng ta có thể tìm ra các mối quan hệ giữa các cặp thuộc tính- giá trị thuộc tính. Đó là luật kết hợp tiêu biểu: Ví dụ có 80% khách hàng mua sách ngoại ngữ thì sẽ mua đĩa CD hoặc VCD. 2.2. Các khái niệm cơ bản 2.2.1. Định nghĩa 2. 2.1: Ngữ cảnh khai phá dữ liệu Cho tập O là tập hữu hạn khác rỗng các giao tác và I là tập hữu hạn khác rỗng các mặt hàng, R là một quan hệ hai ngôi giữa O và I sao cho với oO và iI, (o,i)R= > giao tác.o có chứa mặt hàng i. Ngữ cảnh khai phá dữ liệu (dưới đây sẽ gọi tắt là NCKPDL) là bộ ba (O, I, R). 2.2.2. Định nghĩa 2. 2. 2: Các kết nối Galois Cho NCKPDL (O, I, R), xét hai kết nối Galois ρ và λ được định nghĩa như sau: ρ : P (I) →P (O) và λ : P (O) →P (I): Cho S I, ρ (S) = {oO |iS, (o, i) R} Cho X O, λ (X) = {i I | oX, (o, i) R} Trong đó P (X) là tập các tập con của X. Cặp hàm (ρ, λ) được gọi là kết nối Galois. Giá trị ρ (S) biểu diễn tập các giao tác có chung tất cả các mặt hàng trong S. Giá trị λ (X) biểu diễn tập mặt hàng có trong tất cả các giao tác của X. 2.2.3. Định nghĩa 2.2.3: Độ hỗ trợ (Support) 2.2.3.1. Độ hỗ trợ của một tập mục X trong cơ sở dữ liệu D là tỉ số giữa các giao tác T D có chứa tập X là tổng số giao tác trong D (hay là phần trăm của các giao tác trong D có chứa tập mục X), kí hiệu là Supp (X). Supp (X)= Ta có 0 Supp (X) với mọi tập X. Hay có thế nói Support chỉ mức độ “thướng xuyên xảy ra” của mẫu. 2.2.3.2. Độ hỗ trợ của luật X→Y là tỉ số của số giao tác có chứa XY và số giao tác trong cơ sở dữ liệu D, kí hiệu là Supp (X→Y). Supp (X→Y)= Như vậy độ hỗ trợ của một luật bằng 50% nghĩa là có 50% số giao tác có chứa tập mục XY. Độ hỗ trợ có ý nghĩa thống kê của luật kết hợp. 2.2.4. Định nghĩa 2 2.4: Độ tin cậy ( Confidence) 2.2.4.1. Tính chất 2. 2.4.1: Hỗ trợ của tập con. Giả sử A,B I là tập các tập mục với A B thì Supp (A) Supp (B). Thật vậy, tính chất này có thể suy ra trực tiếp từ khái niệm tập mục phổ biến, vì tất cả các giao tác hỗ trợ B thì cũng hỗ trợ A. Như vậy giao tác nào chứa tập mục B thì cũng chứa tập mục A. 2.2.4.2. Tính chất 2.2.4.2 Giả sử A, B là hai tập mục, A, B I. Nễu B là tập mục phổ biến và A B thì A cũng là tập mục phổ biến. Thật vậy, nếu B là tập mục phổ biến thì Supp (B) Minsup, mọi tập mục A là tập mục con của tập mục B đều là tập mục thường xuyên trong cơ sở dữ liệu D vì Supp (A) Supp (B) (Theo tính chất 2.3.1). 2.2.4.3. Tính chất 2.2.4.3 Giả sử A, B là hai tập mục A B và A là tập mục không phổ biến thì B cũng là tập mục không phổ biến. Thật vậy, A là tập mục không thường xuyên nên Supp (A) Minsup mà A B nên Supp (A) Supp (B). Suy ra Supp (B)< Minsup vậy B là tập mục không phổ biến. 2.2.4.4. Tính chất 2. 2.4.4 Giả sử X, Y, Z I là những tập mục, sao cho X Y = Æ. Thì: Conf (XY) Conf (X/ZY Z). Thật vậy, từ X Y và X/Z X ta có: Độ tin cậy của một luật r = X→Y là tỉ số (phần trăm) của số giao tác trong D chứa XY với số giao tác trong D có chứa tập mục X. Kí hiệu độ tin cậy của một luật là Conf (r). Ta có 0 conf 1. Nhận xét: Độ hỗ trợ và độ tin cậy chính là xác suất sau: Supp (X→Y) = P (XY). Conf (X→Y) = P (Y/X) = Supp (XY)/Supp (X). Ta nói rằng với luật có độ tin cậy 85% thì có nghĩa là 85% các giao tác có chứa X thì cũng chứa Y. Độ tin cậy của một luật là thể hiện mức độ tường quan trong dữ liệu giữa hai tập X và Y. Độ tin cậy là độ đo mức độ tin cậy của một luật. 2.2.5. Định nghĩa 2.2.5: Tập mặt hàng phổ biến Cho NCKPDL (O, I, R) và Minsup (0, 1] là ngưỡng phổ biến tối thiểu. Cho S I, độ phổ biến của S ký hiệu là SP (S) là tỉ số giữa số các giao tác có chứa S và số lượng giao tác trong O. Nói cách khác SP (S)= |ρ (S)| / |O|. Cho S I, S là một tập các mặt hàng phổ biến theo ngưỡng Minsup nếu và chỉ nếu SP (S) ≥ Minsup. Trong các phần sau tập mặt hàng phổ biến sẽ được gọi tắt là tập phổ biến. Ký hiệu FS (O, I, R, Minsup) = {S P (I) | SP (S) ≥ Minsup). 2.2.6. Định nghĩa 2.2.6: Luật kết hợp Cho NCKPDL (O, I, R) và ngưỡng Minsup (0, 1]. Với một S FS (O, I, R, Minsup), gọi X và Y là các tập con khác rỗng của S sao cho S = XY và X Y = Æ. Luật kết hợp X với Y có dạng X→Y phản ánh khả năng khách hàng mua tập mặt hàng Y khi mua tập mặt hàng X. Độ phổ biến của luật kết hợp X→Y với S = X→Y là SP (S). Độ tin cậy của luật kết hợp X→Y được ký hiệu là CF (X→Y) và được tính bằng công thức CF (X→Y) = SP (XY)/SP (X) Nguyên lý Apriori. • Cho S FS (O, I, R, Minsup), nếu T S thì T FS (O, I, R, Minsup). • Cho T FS (O, I, R, Minsup), nếu T S thì S FS (O, I, R, Minsup). 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. Nếu XY và YZ thoả mãn trên D thì không nhất thiết X Y Z là đúng. Thật vậy, nếu xét trường hợp X Y= Æ và các giao dịch trên D hỗ trợ Z khi và chỉ khi chúng hỗ trợ X hoặc hỗ trợ Y. Khi đó Supp (X Y) = 0 và Conf (X Y) = 0. Tương tự, trường hợp có X Y và X Z, ta suy ra X Y Z. 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. Nếu X Y Z thì X Z và Y Z chưa chắc xảy ra. Chẳng hạn xét trường hợp Z có mặt trong giao tác chỉ khi cả tập X và Y cũng có mặt, tức là Supp (X Y) = Supp (Z). Nếu độ hỗ trợ X, Y đủ lớn hớn Supp (X Y) tức là Supp (X) Supp (X Y) và Supp (Y) Supp (X Y ) thì hai luật riêng biệt sẽ không đủ độ hỗ trợ. Tuy nhiên trương hợp ngựơc lại X Y Z thì suy ra được X Y và X Z. Để giải thích cho tính chất này ta phân tích ví dụ sau: T(Y) T(Z) T(X) Hình 2.5. Minh họa luật kết hợp không có tính tách Khi Z thể hiện trong một giao dịch chỉ nếu cả X và Y đều thể hiện giao dịch đó, nghĩa là Supp (X Y) = Supp (Z). Nếu Supp cho X và Y lớn hơn Supp (X Y), thì hai luật trên sẽ không có Conf yêu cầu. Nhưng nếu X Y Z thỏa mãn trên D thì có thể suy ra X Y và X Z cũng thỏa mãn trên D vì Supp (XY) Supp (XYZ) và Supp (XZ) Supp (XYZ). 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. Nếu XY và YZ thoả mãn trên D thì không thể khẳng định X Z thoả mãn trên D. Giả sử T (X) T (Y) T (Z) và Conf (X Y) = Conf (Y Z) = Minconf. Khi đó Conf (X Z) = Minconf2 < Minconf (vi 0 < Minconf < 1), suy ra luật X Z không có Conf tối thiểu, tức là X Z không thoả mãn trên D. 2.2.6.4. Tính chất 2.2.6.4 Nếu luật X (L-X) không thoả mãn độ tin cậy cực tiểu thì luật Y (L-Y) cũng không thoả mãn với các tập mục Y X L. 2.3. Tìm tập phổ biến 2.3.1. Một số khái niệm Cho NCKPDL (O, I, R) và Minsup (0, 1], tìm FS (O, I, R, Minsup). Thuật toán được xây dựng dựa trên nguyên lý Apriori. Đầu tiên thuật toán sẽ tìm các tập phổ biến có một phần tử. Sau đó các ứng viên của các tập phổ biến có hai phần tử sẽ được tạo lập bằng cách hợp các tập phổ biến có một phần tử. Một cách tổng quát, các tập ứng viên của tập phổ biến có k phần tử sẽ được tạo từ các tập phổ biến có k-1 phần tử. Gọi Fk = {S P (I) | SP (S) ≥ Minsup và |S|= k}. Thuật toán sẽ duyệt từng ứng viên để tạo Fk bao gồm các ứng viên có độ phổ biến lớn hơn hoặc bằng ngưỡng Minsup. - Tập các hạng mục (Itemset) I = {i1, i2, …, im}: VD : I = {sữa, bánh mì, ngũ cốc, sữa chua} Tập k hạng mục (k-Itemset). - Giao dịch t : tập các hạng mục sao cho t Í I VD : t = {bánh mì, sữa chua, ngũ cốc} - CSDL D = {t1, t2, …, tn}, ti= {ii1, ii2, …, iik} với iij Î I : CSDL giao dịch - Giao dịch t chứa X nếu X là tập các hạng mục trong I và X Í t VD : X = {bánh mì, sữa chua} - Độ phổ biến (supp) của tập các hạng mục X trong CSDL D là tỷ lệ giữa số các giao dịch chứa X trên tổng số các giao dịch trong D. Supp (X) = count (X) / | D | Tập các hạng mục phổ biến S hay tập phổ biến (Frequent Itemset) là tập các hạng mục có độ phổ biến thỏa mãn độ phổ biến tối thiểu Nếu Supp (S) ³ Minsup thì S - tập phổ biến. - Tính chất của tập phổ biến (Apriori). Tất cả các tập con của tập phổ biến đều là tập phổ biến. 2.3.2. Thuật toán Apriori 2.3.2.1. Mô tả thuật toán Đầu tiên thực hiện duyệt CSDL để tìm các mục riêng biệt trong CSDL và độ hỗ trợ tương ứng của nó. Tập thu được là C1. Duyệt tập C1 loại bỏ các mục có độ hỗ trợ < Minsup, các tập mục còn lại của C1 là các tập 1-Itemset (L1) phổ biến. Sau đó kết nối L1 với L1 để được tập các tập 2-Itemset C2. Duyệt CSDL xác định độ hỗ trợ của các tập mục trong C2. Duyệt C2 Loại bỏ các tập mục có độ hỗ trợ < Minsup, các tập mục còn lại của C2 là tập các tập 2-Itemset (L2) phổ biến. L2 lại được sử dụng để sinh ra L3 và cứ tiếp tục như vậy cho đến khi tìm được tập mục k-Itemset Lk mà Lk = Æ (tức là không có tập mục phổ biến nào được tìm thấy) thì dừng lại. Tập các tập mục phổ biến của CSDL là: Èki-1= L1. Để tăng hiệu quả của thuật toán trong quá trình sinh các tập mục ứng cử, ta sử dụng tính chất của tập mục phổ biến để làm giảm số lượng tập các tập ứng cử, không phải là tập phổ biến được sinh ra. Tính chất đó là: Tập các tập con khác rỗng của tập mục phổ biến đều là tập mục phổ biến. Bước nối: Input: Tập Lk+1 là tập (k+1)-Itemset phổ biến. Output: Tập Ck là tập các ứng cử viên cho tập mục phổ biến k-Itemset Tập các ứng cử k-Itemset được sinh ra từ việc kết nối Lk-1 với chính nó. Giả sử l1, l2 là các tập mục của Lk-1. Ta ký hiệu lj[i] là mục thứ Itemset trong tập mục lj,việc kết nối Lk-1 với Lk+1 được thực hiện như sau: Các tập mục của Lk-1 được kết nối với nhau nếu mục đầu của chúng trùng nhau và l1[k-1]<l2[k-1]. Tức là hai tập mục l1 và l2 của Lk-1 có thể kết nối được với nhau nếu thoả mãn: (L1[1] = L2[1])^(L1[2] = L2[2])^...^(L1[k-2] = L2[k-2])^(L1[k-1] = L2[k-1]) Điều kiện l1[k-1] < l2[k-1] để đảm bảo không sinh lặp lại các tập đã sinh. Kết quả tập mục thu được sau khi kết nối l1 và l2 sẽ là (l1[1], l1[2], v.v.l1[k-2], l1[k-1], l2[k-1]). Bước tỉa (Prune) Input: Ck – là tập các ứng cử k-Itemset Output: Lk – là tập các tập k-Itemset phổ biến Ta có Ck ÊLk các thành phần của Ck có thể là phổ biến hoặc không phổ biến, nhưng tất cả các tập k-Itemset đều nằm trong Ck. Bước này chúng ta thực hiện các công việc sau: Quét CSDL D một lần tính độ hỗ trợ cho mỗi tập mục trong Ck. Loại bỏ những tập mục có độ hỗ trợ nhỏ hơn hoặc bằng giá trị Minsup cho trước khỏi Ck. Tập Ck thu được chính là Lk. Tuy nhiên tập Ck có thể rất lớn và vì vậy nó làm cho công việc tính toán trở nên phức tập. Để giảm kích thước của tập Ck thì ta sử dụng tính chất Apriori: Bất kỳ một tập (k-1)-Itemset không phổ biến thì nó không thể là tập con của tập k-Itemset phổ biến, Do đó, nếu bất kỳ tập con (k-1)-Itemset của ứng cử k-Itemset không có mặt trong Lk-1 thì ứng cử đó không là phổ biến, và do vậy có thể loại bỏ tập mục này khỏi Ck. Việc kiểm tra các tập con (k-1)-Itemset có thể được thực hiện một cách nhanh chóng bằng cách duy trì một cây băm . 2.3.2.2. Ví dụ minh hoạ cho thuật toán Apriori Xét CSDL giao dịch D được cho trong bảng sau: Bảng 2.1. CSDL sử dụng minh hoạ thuật toán Apriori TID Danh sách các mục 1 I1 I2 I5 2 I2 I4 3 I2 I3 4 I1 I2 I4 5 I1 I3 6 I2 I3 7 I1 I3 8 I1 I2 I3 I5 9 I1 I2 I3 Trong lần lặp đầu tiên của thuật toán, mỗi mục là một thành viên của tập ứng cử C1. Thuật toán thực hiện quét tất cả các giao dịch của D theo đó đếm số số lần xuất hiện của mỗi mục. Giả sử độ hỗ trợ cực tiểu đếm số giao dịch là 2 (tức là Minsup = 2/9*100% = 22%). Khi đó tập mục phổ biến 1-Itemset (L1), được xác định như sau: L1 bao gồm tất cả các ứng cử 1-Itemset thoả mãn độ hỗ trợ tối thiểu. Tìm ra các tập mục phổ biến 2-Itemset (L2), thuật toán sử dụng kết nối L1 với L1 để sinh ra tập ứng cử 2-Itemset (C2). C2 bao gồm tổ hợp chập lj[i] của các phần tử có trong L1 do đó số lượng các phần tử của C2 được tính như sau: |C2| = C= C= = 10 Tiếp theo, quét các giao dịch trong D và tính độ hỗ trợ của các tập ứng cử trong C2. Tập mục phổ biến 2-Itemset L2 được xác định, bao gồm các tập mục 2-Itemset là ứng cử trong C2 có độ hỗ trợ lớn hơn hoặc bằng độ hỗ trợ tối thiểu Minsup. Sinh các tập ứng cử 3-Itemset, CL¬k-1 bằng cách, kết nối L2 với chính nó ta nhận được kết quả C3 là: C3 = {{I1, I2, I3}, {I1, I2, I5}, {I1, I3, I5}, {I2, I3, I4}, {I2, I3, I5}, {I2, I4, I5}} Sử dụng tính chất Apriori để tỉa bớt các ứng cử: Tất cả các tập con của tập phổ biến là tập phổ biến. Do đó 4 ứng cử viên của tập C3 không thể là tập phổ biến vì nó chứa các tập không phổ biến, ta thực hiện tỉa (loại) bốn tập ứng cử viên đó khỏi C3. Cụ thể như sau: + Các tập {I1, I3, I5}, {I2, I3, I5} không là phổ biến vì tập con {I3, I5} của nó không phổ biến (không có trong L2). + Tập {I2, I3, I4} không là phổ biến vì tập con {I3,I4} của nó không phổ biến (không có trong L2). + Tập {I2, I4, I5} không là phổ biến vì tập con {I4, I5} của nó không phổ biến (không có trong L2). Việc tỉa bớt các tập ứng cử này sẽ làm giảm bớt việc phải quét CSDL để tính độ hỗ trợ khi xác định L3. Lưu ý rằng, với ứng cử k-Itemset, chúng ta chỉ cần kiểm tra tập con (k-1)-Itemset có là phổ biến hay không? Vì thuật toán Apriori sử dụng chiến lược tìm kiếm theo chiều rộng. Như vậy sau khi thực hiện kết nối và tỉa ta thu được kết tập C3 là: C3 = {{I1, I2, I3}, {I1, I2, I5}} Quét các giao dịch trong CSDL để xác định L3, L3 bao gồm các ứng cử 3-Itemset trong C3 thoả mãn độ hỗ trợ tối thiểu. Ta có L3 là: L3 = {{I1, I2, I3}, {I1, I2, I5}} Sinh các tập ứng cử 3-Itemset, C3 bằng cách kết nối L3 với chính nó ta nhận được kết quả C4 là tập mục {I1, I2, I3, I5}. Sau đó thực hiện bước tỉa thì tập {I1, I2, I3, I5} bị tỉa vì nó chưa tập con {I2, I3, I5} không là tập phổ biến (không có trong L3). Như vậy ta có C4 = Æ đến đây thuật toán kết thúc. Vậy tập hợp tất cả các tập mục phổ biến đã được tìm. Các tập mục phổ biến tìm được từ CSDL giao dịch D với độ hỗ trợ tối thiểu Minsup = 22% (độ hỗ trợ tối thiểu tương đương với số giao dịch = 2). Bảng 2. 2. Kết quả thực hiện thuật toán Aprori cho CSDL D Loai tập mục phổ biến Các tập mục phổ biến 1-Itemset {I1} {I2} {I3} {I4} {I5} 2-Itemset {I1, I2} {I1, I3} {I1, I5} {I2, I3} {I2, I4} {I2, I5} 3-Itemset {I1, I2, I3} {I1, I2, I5} 2.3.2.3. Procedure-Code. Input : CSDL D, Minsup Output : L : các tập phổ biến trong D Ck : Tập ứng viên kích thước k Lk : Tập phổ biến kích thước k L1 = Tìm_tập_phổ_biến_1_hạng mục (D); for (k = 1; Lk ¹ Æ; k++ {Ck+1 = Apriori_gen (Lk); // Tạo tập ứng viên (k+1) hạng mục for mỗi giao tác t Î D {// Duyệt CSDL để tính Support Ct = subset (Ck+1, t); // Lấy ra tập con của t là ứng viên for mỗi ứng viên c Î Ct c. Count ++} Lk+1 = {c Î Ck+1| c. Count ³ Minsup }} return L = k È Lk; 2.3.2.4. Tạo tập ứng viên (k+1)- hạng mục. Hàm Apriori_gen nhận Lk và trả về tập ứng viên kích thước (k+1). Gồm 2 bước: Kết và loại bỏ. Procedure Apriori_gen (Lk : Tập phổ biến kích thước k) for mỗi Itemset l1Î Lk for mỗi Itemset l2Î Lk if (l1 [1] = l2 [1]) Ù (l1 [2] = l2 [2]) Ù …Ù (l1 [k-1] = l2 [k-1]) Ù (l1 [k] < l2 [k]) then {c = l1 vw l2 ; // Bước kết Lk với chính nó if has_infrequent_subset (c, Lk ) then Xóa c ; // Loại bỏ các ứng viên không có lợi else Thêm c vào Ck+1 ; } return Ck+1 ; Tạo tập ứng viên (k+1)- hạng mục (tt) Sử dụng tri thức để giảm Ck+1 Procedure has_infrequent_subset (c: Tập ứng viên kích thước k+1, Lk: Tập phổ biến kích thước k). for mỗi k-subset s Î c if s Ï Lk then return True ; return False ; 2.4. Tìm luật kết hợp Gọi I = {I1, I2,...., Im} là tập m thuộc tính riêng biệt, mỗi thuộc tính gọi là một mục. Gọi D là một cơ sở dữ liệu, trong đó mỗi bản ghi T là một giao dịch và chứa các tập mục, T Í I. Định nghĩa 2.4 1: Một luật kết hợp là một quan hệ có dạng X Þ Y, trong đó X, Y Ì I là các tập mục gọi là Itemsets, và .Ở đây, X được gọi là tiền đề, Y là mệnh đề kết quả. Thông số quan trọng nhất của luật kết hợp là độ hỗ trợ (s) và độ tin cậy (c). Định nghĩa 2.4.2: Độ hỗ trợ (Support) của luật kết hợp X Þ Y là tỷ lệ phần trăm các bản ghi với tổng số các giao dịch có trong cơ sở dữ liệu. Định nghĩa 2.4.3: Đối với một số giao dịch được đưa ra, độ tin cậy (confidence) là tỷ lệ của số giao dịch có chứa với số giao dịch có chứa X. Đơn vị tính %. Việc khai thác các luật kết hợp từ cơ sở dữ liệu chính là việc tìm tất cả các luật có độ hỗ trợ và độ tin cậy lớn hơn ngưỡng của độ hỗ trợ và độ tin cậy do người sử dụng xác định trước. Các ngưỡng của độ hỗ trợ và độ tin cậy được ký hiệu là Minsup và Mincof. Việc khai thác các luật kết hợp được phân tích thành hai vấn đề sau đây: - Tìm tất cả các tập mục thường xuyên xảy ra mà có độ hỗ trợ lớn hơn hoặc bằng Minsup. - Tạo ra các luật mong muốn sử dụng các tập mục lớn mà có độ tin cậy lớn hơn hoặc bằng Mincof. 2.4.1. Phát biểu bài toán khai phá luật kết hợp I = {i1, i2, …, in } là tập bao gồm n mục (Item – còn gọi là các thuộc tính - attribute).X I được gọi là tập mục (Itemset). T = {t1, t2, .v.v.tm} là tập gồm m giao dịch (Transasction – còn gọi là bản ghi - Record), mỗi giao dịch được định danh bởi TID (Transaction Identification). R là một quan hệ nhị phân trên I và T. Nếu giao dịch t có chứa mục I thì ta viết (i, t) R.(T, I, R) là ngữ cảnh khai thác dữ liệu. Một CSDL D, về mặt hình thức, chính là một quan hệ nhị phân R như trên. Về ý nghĩa, một CSDL là một tập các giao dịch, mỗi giao dịch t là một tập mục, t 2I (2I là tập các tập con của I). Ví dụ về CSDL giao dịch: I = {A, B, C, D, E}, T = {1, 2, 3, 4, 5, 6} Thông tin về các giao dịch cho ở bảng sau: Bảng 2. 3. Ví dụ về một CSDL giao dịch – D Định danh giao dịch (TID) Tập mục (Itemset) 1 A, B, D, E 2 BC, E 3 AB, DE 4 ABC, E 5 ABCDE 6 BCDE Cho một tập mục X I. Ký hiệu s (X) là Độ hỗ trợ (Support) của một tập mục X là tỷ lệ phần trăm số giao dịch trong CSDL D chứa X trên tổng số cac giao dịch trong CSDL D. S (X) = Card (X)/Card (D)% Tập mục phổ biến: Cho một tập mục X I và ngưỡng phổ biến tối thiểu Minsup (0, 1], (Minsup được xác định bởi người sử dụng). Một tập mục X được gọi là một tập phổ biến theo ngưỡng Minsup nếu và chỉ nếu độ hỗ trợ của nó lớn hơn hoặc bằng một ngưỡng Minsup: s (X) Minsup. Ký hiệu FX (T, I, R, Minsup) = {X I | s (X) Minsup} Với (T, I, R) trong ví dụ CSDL bảng 1, và giá trị ngưỡng Minsup = 50% sẽ liệt kê các tập mục phổ biến (Frenquent-Itemset) như sau: Bảng 2.4. Tập mục thường xuyên Minsup = 50% Tập mục phổ biến Độ hỗ trợ (s) tương ứng B 100% E, BE 83% A, C, D, AB, AE, BC, BD, ABE 67% AD, CE, DE, ABD, ADE, BCE, BDE 50% Độ hỗ trợ s của luật kết hợp X Y là tỷ lệ phần trăm các giao dịch trong D có chứa X và Y là s (X Y) = Card (XY)/Card (D) % Luật kết hợp có dạng X Y trong đó: X, Y là các tập mục thoả mãn điều kiện X Y = Ø và c là độ tin cậy. Độ tin cậy của luật c = s (X Y)/s (X)%: Là tỷ lệ phần trăm các giao dịch trong D có chứa X thì chứa Y. Về mặt xác suất, độ tin cậy c của một luật kết hợp là xác suất (có điểu kiện) xảy ra Y với điều kiện đã xẩy ra X Luật kết hợp tin cậy: Một luật được xem là tin cậy nếu độ tin cậy c của nó lớn hơn hoặc bằng một ngưỡng Minconf (0, 1] nào đó do người dùng xác định. Ngưỡng Minconf phản ánh mức độ xuất hiện của Y khi cho trước X.( ( c Minconf) (Minimum Confidence)) Luật kết hợp cần tìm là luật kết hợp thoả mãn Minsup và Minconf cho trước. Chúng ta chỉ quan tâm đến các luật có độ hỗ trợ lớn hơn độ hỗ trợ tối thiểu và độ tin cậy lớn hơn độ tin cậy tối thiểu. Hầu hết các thuật toán khai phá luật kết hợp thường chia thành 2 pha: Pha 1 : Tìm tất cả các tập mục phổ biến từ cơ sở dữ liệu tức là tìm tất cả các tập mục X thoả s (X) Minsup. Pha 2: Sinh các luật tin cậy từ các tập phổ biến đã tìm thấy ở pha 1. Nếu X là một tập mục phổ biến thì luật kết hợp được sinh ra từ X có dạng: X’ c X \ X’, trong đó: X’ là tập con khác rỗng của X. X\X’ là hiệu của hai tập hợp X và X’. c là độ tin cậy của luật thoả mãn c Minconf Với tập mục phổ biến trong bảng 4 thì chúng ta có thể sinh luật kết hợp sau đây: Bảng 2.5. Luật kết hợp sinh từ tập mục phổ biến ABE Luật kết hợp Độ tin cậy c Minconf ? ABE Có B AE Không E AB Có AB E Có AE B Có BE A Có Tập phổ biến tối đại: Cho M FX (T, I, R, Minsup) M được gọi là tập mục phổ biến tối đại nếu không tồn tại X FX (T, I, R, Minsup), M X, M X 2.4.2. Phát triển giải pháp hiệu quả trong khai thác luật kết hợp Bài toán luật kết hợp. Cho một tập các giá trị I, một CSDL giao dịch D, ngưỡng độ hỗ trợ tối thiểu Minsup, ngưỡng độ tin cậy Mincof, tìm các luật kết hợp dạng X Þ Y trên D thoả mãn điều kiện Support (X Þ Y) >= Minsup và Confidence (X Þ Y) >= Mincof. Tiến trình khai thác luật kết hợp. Xác định các tập mục lớn Việc xác định các tập mục lớn gồm có hai bước chính sau đây: Xác định các tập ứng cử viên (Ck). Xác định các tập mục lớn (L) dựa vào tập ứng cử viên Để xác định tập ứng cử viên, ta thực hiện các bước sau đây: 1. Tìm các tập ứng cử viên một mục. 2. Quét CSDL D để xác định độ hỗ trợ của các tập ứng cử viên. Trong vòng đầu tiên, các tập ứng cử viên cũng chính là tất cả các mục có trong CSDL. Tại vòng thứ k (k>1), các tập ứng cử viên được xác định dựa vào các tập mục lớn đã xác định tại vòng k – 1, sử dụng hàm Apriori-Gen () Sau khi đã xác định được các tập ứng cử viên, thuật toán quét từng giao dịch trong CSDL để tính độ hỗ trợ của các tập ứng cử viên. Quá trình xác định các tập mục sẽ kết thúc khi không xác định được thêm tập mục lớn nào nữa. 3. Nội dung hàm Apriori-gen (). Hàm Apriori-gen () thực hiện hai bước. 1. Bước đầu tiên, Lk – 1 được kết nối với chính nó thu được Ck. 2. Bước thứ hai, Apriori_gen () xoá tất cả các tập mục từ kết quả kết nối mà có một số tập con (k – 1) không có trong Lk – 1. Sau đó nó trả về tập mục lớn kích thước k còn lại. 3. Sinh các luật kết hợp từ tập mục lớn. Việc phát hiện các tập mục lớn là rất tốn kém về mặt tính toán. Tuy nhiên, ngay khi tìm được tất cả các tập mục lớn (l Î L), ta có thể dễ dàng sinh ra các luật kết hợp có thể có bằng các bước như sau: 1. Tìm tất cả các tập con không rỗng x, của tập mục lớn l Î L. 2. Với mỗi tập con x tìm được, ta xuất ra luật dạng x Þ (l - x) nếu tỷ lệ Support (l)/Support (x) >= Mincof (%). 3. Thủ tục sinh ra các tập con. 4. Đầu vào: 5. Tập mục lớn Lk Đầu ra: Tập luật thoả mãn điều kiện độ tin cậy >= Mincof và độ hỗ trợ >= Minsup Phương pháp: Forall Lk, k >= 2 do Call Genrules (Lk, Lk); Procedure Genrules (Lk: Large k-Itemset, am: Large m-Itemset) A= { (m-1)-Itemset am-1| am-1am} Forall am-1A do begin Conf = Support (Lk)/Support (am-1) If (Conf >= Mincof) then begin Output the rule am-1Þ (Lk – am-1) với Confidence = Mincof and Support = Support (Lk) If (m-1 >1) then Call Genrules (Lk, am-1); End; End; 4. Giải pháp hiệu quả Trong các phần trên, đã trình bày tiến trình cơ bản để khai thác các luật kết hợp trong CSDL, song vấn đề cần phải quan tâm nghiên cứu là tăng hiệu quả của thuật toán trong trường hợp: “Số lượng tập ứng cử viên được tìm thấy là rất lớn”. Trong phạm vi nghiên cứu của bài này, sẽ đưa ra một giải pháp mới để giải quyết vấn đề đã nêu. Tỉa các ứng cử viên: Việc tỉa các ứng cử viên nhằm mục đích bỏ đi các tập ứng cử viên không cần thiết, rút gọn số lượng của tập các tập ứng cử viên. Sau đây, sẽ trình bày kỹ thuật “tỉa” các ứng cử viên không cần thiết. Kỹ thuật này có tinh chất: Các mục trong tập ứng cử viên được sắp xếp theo thứ tự. Nội dung kỹ thuật: Forall Itesets c Î Ck do Forall (k – 1) – subsets s of c do If (s Ï Lk – 1) then Delete c from Ck Dựa vào đây, ta có thể tỉa được các tập ứng cử viên, từ đó có thể giới hạn miền tìm kiếm của nó trên tất cả các tập mục. 2.5. Quy trình khai thác luật kết hợp B1 : Tìm tất cả các tập phổ biến (theo ngưỡng Minsup). B2 : Tạo ra các luật từ các tập phổ biến. Đối với mỗi tập phổ biến S, tạo ra tất cả các tập con khác rỗng của S. Đối với mỗi tập con khác rỗng A của S. Luật A Þ (S - A) là LKH cần tìm nếu: conf (A Þ (S - A)) = supp (S) / supp (A) ³ Minconf 2.6. Một số thuật toán khác 2.6.1. Thuật toán khai phá song song cho luật kết hợp mờ Theo bài toán khai phá luật kết hợp mờ tuần tự trong phần trên, mỗi thuộc tính iu trong I được gắn với tập các tập mờ Fi u như sau: Fi u = {f, f, …,f} Đặt tập FN = {k1} {k2} .v.v.{kn} = {s1, s2, …sv} (v n vì có thể tồn tại những cặp ki và kj giống nhau) và N là số lượng BXL trong hệ thống, bài toán phân chia tập thuộc tính mờ cho các BXL như sau: Tìm một tập con Fn khác rỗng của tập FN sao cho tích các phần tử trong Fn bằng số lượng BXL trong hệ thống. Trong trường hợp không tìm thấy nghiệm đúng thì thuật toán sẽ trả về một nghiệm “chấp nhận được” tức là tích của các phần tử trong Fn là xấp xỉ dưới của N. Giả sử s = {k1, k2, …km} là một nghiệm của thuật toán phân chia (nghĩa là k1*k2 * …*km = N). Lúc đó, số lượng thuộc tính mờ giảm được tại các BXL so với thuật toán tuần tự là (k1 – 1 ) + (k2 – 1 ) + …+ (km – 1 ) = (k1, + k2,…, km – m ). Nghiệm tối ưu là nghiệm có giá trị của biểu thức (k1 + k2 + …+ km – m ) đạt cực đại, tức là số thuộc tính giảm được càng nhiều càng tốt. Để dễ tìm kiếm nghiệm tối ưu, tập FN trước tiên phải được sắp xếp giảm dần. Đây là chiến lược rất quan trọng bởi ta biết thời gian xử lý sẽ giảm theo hàm mũ khi giảm dần số lượng thuộc tính mờ. Một chiến lược khác để tìm nghiệm tối ưu là trong suốt quá trình tìm kiếm thuật toán chia phải tham chiếu đến độ hỗ trợ của các thuộc tính mờ (đã được cập nhật sau khi thực hiện hàm Counting) để xét xem chúng ta nên phân chia theo thuộc tính nào. Thuộc tính được phân chia phải có độ hỗ trợ của các thuộc tính mờ tương đối cân bằng. Chiến lược này giúp cân bằng tỉa giữa các BXL trong hệ thống ở các bước tiếp theo. Bài toán này có thể giải quyết bằng chiến lược quay lui (có đệ quy hoặc không). Bảng dưới đây được trình bày theo cách viết không đệ quy. Thuật toán Boolean Subset (FN,N,Idx) k = 1; Idx[1] = 0; S = 0; While (k > 0) { Idx[k] ++; If (Idx[k] <= sizeof (FN)) { If (S * FN[Idx[k]] <= N) { If (S * FN[Idx[k]] = = N) Return True; Else { S * = FN[Idx[k]]; Idx[k + 1] = Idx[k]; k + +; } } } else { K--; S= FN[Idx[k]]; } } Return False; FindSubset (FN, N, Idx, Fn) for (n = N; n > 0; n --) If (Subset (FN, n, Idx)) { Fn = {FN[i] | i Idx} Return; 1 } 2.6.2. Thuật toán FP-Growth 2.6.2.1 Bản chất. - Khai thác tập phổ biến không sử dụng hàm tạo ứng viên. - Nén CSDL thành cấu trúc cây FP (Frequent Patern) - Duyệt đệ qui cây FP để tạo tập phổ biến 2.6.2.2. Qui trình. B1 : Thiết lập cây FP B2 : Thiết lập cơ sở mẫu điều kiện (Conditional Pattern Bases) cho mỗi hạng mục phổ biến (mỗi nút trên cây FP). B3 : Thiết lập cây FP điều kiện (Conditional FP tree) từ mỗi cơ sở mẫu điều kiện B4 : Khai thác đệ qui cây FP điều kiện và phát triển mẫu phổ biến cho đến khi cây FP điều kiện chỉ chứa 1 đường dẫn duy nhất - tạo ra tất cả các tổ hợp của mẫu phổ biến Thiết lập cây FP (B1) TID Items bought (ordered) Frequent items 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 200 {a, b, c, f, l, m, o} {f, c, a, b, m} 300 {b, f, h, j, o, w} {f, b} 400 {b, c, k, s, p} {c, b, p} 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} Minsupp = 60% - Tìm tập phổ biến 1- hạng mục (duyệt CSDL 1 lần) - Sắp xếp tập phổ biến giảm dần vào trong F-List F-List = f-c-a-b-m-p - Duyệt CSDL lần nữa và thiết lập cây FP Bảng 2.6. Cây FP Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 TID Items bought (ordered) frequent items 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 200 {a, b, c, f, l, m, o} {f, c, a, b, m} 300 {b, f, h, j, o, w} {f, b} 400 {b, c, k, s, p} {c, b, p} 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} Minsupp = 3 - Tìm tập phổ biến 1- hạng mục (duyệt CSDL 1 lần) - Sắp xếp tập phổ biến giảm dần vào trong F-List F-List = f-c-a-b-m-p - Duyệt CSDL lần nữa và thiết lập cây FP Bảng 2.7. Cây FP Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 {} f:1 c:1 a:1 m:1 p:1 TID Items bought (ordered) frequent items 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 200 {a, b, c, f, l, m, o} {f, c, a, b, m} 300 {b, f, h, j, o, w} {f, b} 400 {b, c, k, s, p} {c, b, p} 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} Minsupp = 3 - Tìm tập phổ biến 1- hạng mục (duyệt CSDL 1 lần) - Sắp xếp tập phổ biến giảm dần vào trong F-List F-List = f-c-a-b-m-p - Duyệt CSDL lần nữa và thiết lập cây FP Bảng 2.8. Cây FP m:1 Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 {} f:2 c:2 a:2 b:1 p:1 m:1 TID Items bought (ordered) frequent items 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 200 {a, b, c, f, l, m, o} {f, c, a, b, m} 300 {b, f, h, j, o, w} {f, b} 400 {b, c, k, s, p} c, b, p} 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} Minsupp = 3 - Tìm tập phổ biến 1- hạng mục (duyệt CSDL 1 lần) - Sắp xếp tập phổ biến giảm dần vào trong F-List F-List = f-c-a-b-m-p - Duyệt CSDL lần nữa và thiết lập cây FP Bảng 2.9. Cây FP Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 {} f:3 c:2 a:2 b:1 m:1 p:1 m:1 b:1 TID Items bought (ordered) frequent items 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 200 {a, b, c, f, l, m, o} {f, c, a, b, m} 300 {b, f, h, j, o, w} {f, b} 400 {b, c, k, s, p} {c, b, p} 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} Minsupp = 3 - Tìm tập phổ biến 1- hạng mục (duyệt CSDL 1 lần) - Sắp xếp tập phổ biến giảm dần vào trong F-List F-List = f-c-a-b-m-p - Duyệt CSDL lần nữa và thiết lập cây FP Bảng 2.10. Cây FP p:1 m:1 {} f:4 c:1 Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 b:1 b:1 c:3 a:3 b:1 m:2 p:2 Ví dụ cây FP A:9 B:3 C:2 E:1 C:2 E:2 B:5 E:1 D:1 D:1 C:2 D:1 Null E:1 A – 9 B – 8 C – 6 E – 5 D – 3 A B B A C A B D E B A A C A B C B C B C D B E E A A C E A D E Minsupp = 25% Nếu Minsupp = 40% thì cây FP sẽ như thế nào ? b-Thuật toán FP- Growth (B2) - Bắt đầu từ mẫu phổ biến cuối bảng của cây FP - Duyệt cây FP theo kết nối của mỗi hạng mục phổ biến p - Gom tất cả đường dẫn tiền tố biến đổi (Transformed Prefix ) của hạng mục p để tạo cơ sở mẫu điều kiện của p Bảng 2.11. Cây FP Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 {} f:4 c:1 b:1 p:1 c:3 a:3 b:1 m:2 p:2 m:1 Conditional pattern bases item cond. Pattern base c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1 c- Thuật toán FP- Growth (B3) Với mỗi cơ sở mẫu : - Đếm số lượng mỗi mẫu trong cơ sở mẫu - Thiết lập cây FP cho tập phổ biến của mẫu cơ sở VD : Giả sử có cở mẫu điều kiện cho p: {fcam:2, cb:1} p-Conditional FP-tree Bảng 2.12. Cây FP {} Header Table Item frequency head c 3 c:3 Tất cả mẫu phổ biến liên quan đến p là : Ú p, cp Với mỗi cơ sở mẫu : - Đếm số lượng mỗi mẫu trong cơ sở - Thiết lập cây FP cho tập phổ biến của mẫu cơ sở Ví dụ : m-Conditional Pattern Base: fca:2, fcab:1 Bảng 2.13. Cây FP b:1 p:1 Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 {} f:4 c:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 {} f:3 c:3 a:3 m-Conditional FP-Tree Tất cả mẫu phổ biến liên quan đến m là : Ú Ú m, fm, cm, am, fcm, fam, cam, fcam Ví dụ Bảng 2.14.Cơ sở dữ liệu { } { } f { (f:3) } | c { (f:3) } c { (f:3, c:3) } | a { (fc:3) } a { } { (fca:1), (f:1), (c:1) } b { (f:3, c:3, a:3) } | m { (fca:2), (fcab:1) } m { (c:3) } | p { (fcam:2), (cb:1) } p Conditional FP-tree Conditional pattern-base Item d- Thuật toán FP- Growth (B4) Cond. pattern base of “am”: (fc:3) {} f:3 c:3 am-conditional FP-tree Cond. pattern base of “cm”: (f:3) cm-conditional FP-tree {} f:3 cam-conditional FP-tree Cond. pattern base of “cam”: (f:3) {} f:3 c:3 a:3 m-conditional FP-tree - Giả sử cây FP T có một đường dẫn đến (Single Path) P - Tập mẫu phổ biến cuối cùng của T sinh ra bằng cách liệt kê tất cả các tổ hợp của Sub-Paths thuộc P {} f:3 c:3 a:3 m-Conditional FP-Tree Tất cả mẫu phổ biến liên quan đến m m, fm, cm, am, fcm, fam, cam, fcam Ú 2.6.2.3. Thuật toán FP_Growth Pocedure FP_Growth (Tree, a) If cây FP chứa 1 path P then For mỗi tổ hợp b của nốt trên P Tạo mẫu b È a với Supp = Suppmin (các nốt trong b); Else for mỗi ai trên header của cây Tạo mẫu b= ai È a với supp = ai . Supp ; Thiết lập b’s Conditional Pattern base and b’s Conditional FP-Tree Tree b If Tree b ¹ Æ, gọi FP_Growth (Tree b, b). * Kết luật chương II: Qua chương II chúng ta biết được việc áp dụng các thuật toán vào các lĩnh vực của đời sống xã hội, nó có vai trò rất quan trọng trong việc xây dựng những hệ hỗ trợ ra quyết định. Khai phá luật kết hợp là một hướng đi đang được hoàn thiện. Để có thể áp dụng luật kết hợp trước tiên ta phải tiến hành mã hoá cơ sở dữ liệu hiện có, đây là một bước quan trọng, quyết định có thể sinh luật kết hợp tốt hay không. Thuật toán Apriori tìm tập mục phổ biến theo hướng sinh ứng cử. Thuật toán FP_Growth tìm tập mục phổ biến theo hướng không sinh ứng cử. Trên cơ sở là tập phổ biến tìm được ta áp dụng thuật toán khai phá luật kết hợp để sinh ra tập luật kết hợp đáng tin. 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 3.1. Phát biểu bài toán. Với sự phát triển của nền kinh tế hiện nay, thì việc kinh doanh đang là vấn đề được rất nhiều người quan tâm. Xã hội càng phát triển thì trình độ con ngươi ngày càng được nâng cao. Vì vậy phát triển giáo dục đang là vấn đề mà xã hội rất quan tâm, lên việc kinh doanh các tài liệu về sách giáo khoa, sách tham khảo, đồ dùng học tập,..đang là một hướng đi đúng. Nhưng để kinh doanh tốt thì người kinh doanh phải biết quán lý nó như thế nào cho đúng và hợp lý nhất. Từ những điều đó thiết nghĩa phải có một phần mềm quản lý bán sách, để hỗ trợ cho người quản lý trong việc lựa chọn các đầu sách để bán. Ví dụ khi bán sách giáo khoa thì bán kèm thêm sách tham khảo và đồ dùng học tập gì? Chúng có liên quan tới nhau như thế nào? Luật kết hợp cho ta biết việc lựa chọn các loại sách gì để bán, giúp người quản lý đưa ra quyết định nhanh, chính xác và hiệu quả nhất. 3.2. Lựa chọn thuật toán để cài đặt phần mềm. Có rất nhiều thuật toán để đưa ra việc lựa chọn các đầu sách trong việc quán lý bán sách, nhưng chúng em lựa chọn thuật toán Apriori để cài đặt. Mục đích của thuật toán này là đưa ra các luật kết hợp trong việc lựa chọn các đầu sách để bán. Ví dụ khi bán sách Toán thì bán kèm thêm sách Lý, Hoá. 3.3. Yêu cầu khi cài đặt thuật toán. - Về máy tính: + Cấu hình tối thiểu Ram 256. + Ổ cứng 2G còn trống. + CPU P4 1.7Ghz - Về phần mềm: + Cài đặt Visual Studio 2005 + DOT.NET 2.0. 3.4. Cơ sở dữ liệu. 3.4.1. Giao diện chính của cơ sở dữ liệu. Hình 3.1. Giao diện chính của cơ sở dữ liệu Mô tả một số chức năng trong giao diện: + Hệ Thống: Có chức năng thoát khỏi chương trình. + DM khách hàng: Có chức năng thêm, lưu, sửa, xóa dữ liệu cho khách hàng. + DM hàng: : Có chức năng thêm, lưu, sửa, xóa dữ liệu cho hàng hóa. + DM hóa đơn: : Có chức năng thêm, lưu, sửa, xóa dữ liệu cho hóa đơn. + DM Nhà CC: : Có chức năng thêm, lưu, sửa, xóa dữ liệu cho nhà cung cấp. + Apriori: Có chức năng ghi dữ liệu vào file XML. 3.4.2. Bảng danh mục các Nhà cung cấp hàng hóa. Cấu trúc và dữ liệu của bảng như sau: Hình 3.2. Danh mục nhà cung cấp Một số thuộc tính của bảng là: + MaNCC: Mã nhà cung cấp hàng hóa. + TenNCC: Tên nhà cung cấp hàng hóa. + DiaChi: Địa chỉ của nhà cung cấp hàng hóa. + DienThoai: Điện thoại của nhà cung cấp. + MaSoThue: Mã số thuế nhà cung cấp hang hóa. + Email: Email cua nhà cung cấp 3.4.3. Bảng danh mục các Hàng Hoá. Cấu trúc và dữ liệu của bảng hàng hoá như sau: Hình 3.3. Danh mục hàng hóa Một số thuộc tính của bảng là: + MaH: Mã hàng hoá. + MaNCC: Mã nhà cung cấp hàng hoá. + TenHang: Tên hàng hoá. + MoTa: Mô tả hàng hóa. + ChungLoai: Chủng loại hàng hóa. 3.4.4. Bảng danh mục các Khách Hàng. Cầu trúc và dữ liệu bảng khách hàng như sau: Hinh 3.4.Danh mục khách hàng Một số thuộc tính của bảng là: + MaKH: Mã khách hàng. + TenKH: Tên khách hàng. + SoCMND: Số chứng minh nhân dân. + DiaChi: Địa chỉ khách hàng. + DienThoai: Điện thoại khách hàng. + Email: Email của khách hàng 3.4.5. Bảng danh mục các Hoá Đơn. Cấu trúc và dữ liệu của bảng hóa đơm như sau: Hình 3.5. Danh mục hóa đơn Một số thuộc tính của bảng là: + MaHD: Mã hoá đơn. + MaKH: Mã khách hàng. + NgayHD: Ngày nhập hoá đơn. + Ghichu: Ghi chú hóa đơn. 3.4.6. Bảng danh mục chi tiết Hoá Đơn. Cấu trúc và dữ liệu của bảng chi tiết hóa đơm như sau: Hình 3.6. Danh mục chi tiết hóa đơn Một số thuộc tính của bảng là: + MaHD: Mã hoá đơn. + MaH: Mã hàng hóa. + SoLuong: Số lượng hàng hóa. 3.4.7. Ghi XML. Hình 3.7. Ghi XML 3.5. Giao diện chính chương trình. Hình 3.8. Giao diện chính của chương trình 3.6. Kết nối dữ liệu. Hình 3.9. Kết nối dữ liệu 3.7. Thêm dư liệu Xml Hình 3.10. Thêm dư liệu XML 3.8. Kết quả phân tích Hình 3.11. Kết quả phân tích 3.9. Kết quả lọc MinSup = 10 Hình 3.12. Kết quả lọc độ phổ biến tối thiểu 3.10. Kết quả lọc MinCon = 40% Hình 3.13. Kết quả lọc độ tin cậy * Kết luận chuơng III: Cài đặt bằng thuật toán Apriori áp dụng trong quản lý bán hàng tại thị siêu. Dựa vào kết quả này mà người quản lý biết được những nhóm mặt hàng nào 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. KẾT LUẬN CHUNG Trong quá trình hoàn thành đồ án này, dù đã đạt được những kiến thức nhất định, nhưng chúng em nhận thấy Khai phá dữ liệu nói chung và khai phá luật kết hợp nói riêng là một lĩnh vực nghiên cứu rộng lớn, nhiều triển vọng. Đề tài đã trình bày được các vấn đề cơ bản về khai phá dữ liệu: Tầm quan trọng của KPDL, các hướng tiếp cận khai phá dữ liệu và các kỹ thuật khai phá dữ liệu. Khai phá dữ liệu sử dụng luật kết hợp và một số thuật toán tìm tập mục thường xuyên theo hướng sinh ứng cử và không sinh ứng cử. Phần cài đặt chương trình đã cài đặt được thuật toán khai phá dữ liệu Apriori. Tuy nhiên, do những hạn chế về tài liệu và thời gian nên chưa hoàn thành được việc cài đặt thuật toán khai phá luật kết hợp, trong thời gian tiếp theo chúng em sẽ cố gằng hoàn thành phần cài đặt này để đề tài được hoàn thiện hơn. Chương I: Đã trình bày tổng quan về khai phá dữ liệu (Data Minning); Các loại tri thức tiềm ẩn trong cơ sở dữ liệu, các kỹ thuật khai thác dữ liệu. Chương II: Đã trình bày tổng quan về khai thác luật kết hợp, nêu ra những khái niệm, định nghĩa, tính chất của tập mục và luật kết hợp, cách xác định độ hỗ trợ của tập mục và luật, độ tin cậy của luật. Đưa ra các mô hình bài toán khai thác luật kết hợp, nó là tiền để để các thuật toán dựa vào đó phát triển và có những đánh giá so sánh giữa các thuật toán. Chương II: Cũng trình bày về các thuật toán khai thác luật kết hợp, thuật toán nổi tiếng là 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,… Chương III: 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 thị siêu. Dựa vào kết quả này mà người quản lý nắm bắt được những nhóm mặt hàng nào liên quan tới nhau, phục vụ cho mục đích quản lý, lựa chọn các mặt hàng để kinh doanh. Chương trình được cài đặt bằng thuật toán Apriori. HƯỚNG PHÁT TRIỂN ĐỀ TÀI Một trong những công việc quan trọng của khai phá luật kết hợp là tìm tất cả các tập phổ biến trong cơ sở dữ liệu, nên trong thời gian tới chúng em sẽ phát triển đề tài rộng ra theo hướng: Ứng dụng thuật toán song song áp dụng cho bài toán khai phá luật kết hợp mờ, là luật kết hợp trong các tập thuộc tính mờ. Thuật toán song song chia đều cơ sở dữ liệu và tập ứng viên cho các bộ vi sử lý, và các tập ứng viên sau khi chia cho từng bộ xử lý là hoàn toàn độc lập với nhau mục đich cải thiện chi phí tìm luật kết hợp mờ và thời gian mã hoá dữ liệu. Do nhược điểm của thuật toán Apriori là nếu dữ liệu lớn thì sự phân tích sẽ mất rất nhiều thời gian vì vậy để khắc phục được nhược điểm đó thì chúng ta cần sử dụng thêm một số thuật toán khác ví dụ như thuật toán FP_Growth, thuật toán song song,.. Tiếp tục hoàn thiện hệ thống Quản lý bán hàng tại siêu thị và có thể ứng dụng thêm vào các lĩnh vực khác như bán hàng tại các siêu thị, bán máy tính,.. Khi mà lượng dữ liệu thu thập và lưu trữ ngày càng tăng, cùng với nhu cầu nắm bắt thông tin, thì nhiệm vụ đặt ra cho Khai phá dữ liệu ngày càng quan trọng. Sự áp dụng được vào nhiểu lĩnh vực kinh tế xã hội, an ninh quốc phòng cũng là một ưu thế của khai phá dữ liệu. Với những mong muốn đó chúng em hy vọng sẽ dần đưa những kiến thức đã có từ đề tài này sớm trở thành thực tế, phục vụ cho cuộc sống con người chúng ta. TÀI LIỆU THAM KHẢO [1]. R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. I.Verkamo. Fast discovery of association rules. In Advances in Knowledge Discovery and Data Mining, pages 307–328,1996. [2]. R. Agrawal and R. Srikant. Fast algorithms for mining associationrules. The International Conference on Very LargeDatabases, pages 487–499, 1994. [3]. R. Agrawal and R. Srikant. Mining sequential patterns. InP. S. Yu and A. L. P. Chen, editors, Proc. 11th Int. Conf. DataEngineering, ICDE, pages 3–14. IEEE Press, 6–10 1995. [4]. N. F.Ayan, A. U. Tansel, and M. E. Arkun. An efficient algorithm to update large itemsets with early pruning. In KnowledgeDiscovery and Data Mining, pages 287–291, 1999. [5].TS Đỗ Phúc, Khai thác dữ liệu, Nhà xuất bản Đại Học Quốc Gia TP HCM 2005. [6].Phạm Hữu Khang, Kỹ thuật lập trình C#.Net, Nhà xuất bản Lao Động- Xã Hội. [7].Từng bước học lập trình Visual C#.Net, Nhà xuất bản Lao Động- Xã Hội. [8]. Giáo trình trí tuệ nhân tạo - cầu trúc dữ liệu - giải thuật di truyền, Nhà xuất bản Lao Động- Xã Hội. [9]. truy cập cuối cùng ngày 20/03/2009. [10]. truy cập cuối cùng ngày 22/03/2009. [11]. truy cập cuối cùng ngày 20-03-2009. [12]. truy cập cuối cùng ngày 22-03-2009. [13]. truy cập cuối cùng ngày 20-03-2009. BẢNG ĐỐI CHIẾU THUẬT NGỮ VIỆT - ANH Tiếng Anh Tiếng Việt Data Mining Khai phá dữ liệu Data Dữ liệu Knowledge Discovery in Database-KDD Phát hiện tri thức trong cơ sở dữ liệu Target Mục đích, mục tiêu. Clearsed Preprocessed Prepadated Làm sạch - Tiền xử lý - Chuẩn bị trước Transform Chuyển đổi Pattern Discovery Khám phá mô hình Knowlege Tri thức Clustering Phân cụm Summerization Tóm tắt Visualiztion Trực quan hoá Evolution and deviation analyst Phân tích sự phát triển và độ lệch Association rules Phân tích luật kết hợp Classification Phân lớp Regression Hồi quy Clustering Gom nhóm Summarization Tổng hợp Dependency modeling Mô hình ràng buộc Change and Deviation Dectection Dò tìm biến đổi và độ lệch Hồi qui Regression Cross validation Đánh giá chéo Support Phổ biến Minimum Support Độ phổ biến tối thiểu Confidence Độ tin cây Minimum Confidence Độ tin cây tối thiểu Itemset Hạng mục Procedure Thủ tục Code Mã, cốt Input Đầu vào Output Đầu ra Transasction Giao dịch Transaction Identification Giao dịch định danh Frenquent-Itemset Tập mục phổ biến Frequent Patern Mô hình phổ biến Conditional Pattern Bases Cơ sở mẫu điều kiện Conditional FP tree Cây FP điều kiện Transformed Prefix Tiền tố biến đổi