Luận Văn Khai phá dữ liệu bằng luật kết hợp

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.


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 HÌNH VẼ 9
ANH SÁCH BẢNG BIỂU 10
DANH SÁCH CÁC TỪ VIẾT TẮT 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
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.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.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.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. 41
2.6.1. Thuật toán khai phá song song cho luật kết hợp mờ. 41
2.6.2. Thuật toán FP-Growth. 42
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.2. 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
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
BẢNG ĐỐI CHIẾU THUẬT NGỮ VIỆT - ANH 65
TÀI LIỆU THAM KHẢO 65