Luận văn thạc sĩ về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu

Luận văn thạc sĩ VNU UET nghiên cứu luật kết hợp mờ và toán tử ngưỡng trong khai phá dữ liệu, góp phần phát triển công nghệ thông tin.

• Tác giả: Lê Thị Thanh Hải
• Người hướng dẫn: PGS. Bùi Công Cường
• Trường học: Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu
• Loại tài liệu: Luận văn thạc sỹ
• Năm xuất bản: 2007
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: LUẬT KẾT HỢP
• 1.1. Ý NGHĨA THỰC TIỄN CỦA LUẬT KẾT HỢP
• 1.2. MÔ HÌNH HÌNH THỨC CỦA VẤN ĐỀ PHÁT HIỆN LUẬT
• 1.2.1. Thuộc tính và CSDL
• 1.2.2. Độ hỗ trợ của một tập thuộc tính
• 1.2.3. Tập phổ biến (Frequent Itemset)
• 1.2.4. Độ hỗ trợ của luật r = X → Y
• 1.2.5. Độ tin cậy của luật r = X → Y
• 1.2.6. Luật kết hợp mạnh
• 1.2.7. Bài toán luật kết hợp
• 1.2.8. Một số tính chất của tập phổ biến và luật kết hợp
• 1.3. THUẬT TOÁN TÌM LUẬT KẾT HỢP
• 1.3.1. Thuật toán Apriori nhị phân
• 1.3.2. Các bước thực hiện
• 1.3.3. Giải thích
• 2. CHƯƠNG 2: LUẬT KẾT HỢP MỜ
• 2.1. Ý NGHĨA VỀ LUẬT KẾT HỢP MỜ
• 2.2. Các phép toán trên tập mờ
• 2.2.1. Số mờ và một số dạng phổ biến
• 2.2.2. Định nghĩa tập mức
• 2.2.3. Định nghĩa số mờ
• 2.2.4. Các dạng phổ biến của số mờ
• 2.2.5. Các phép toán trong logic mờ (toán tử mờ)
• 2.2.5.1. Phép phủ định (negation)
• 2.3. LUẬT KẾT HỢP MỜ
• 2.3.1. Cơ sở dữ liệu và thuộc tính
• 2.3.2. Độ ủng hộ của bản ghi cho mệnh đề
• 2.3.3. Độ hỗ trợ của mệnh đề
• 2.3.4. Tập phổ biến
• 2.3.5. Độ hỗ trợ của một luật mờ
• 2.3.6. Độ tin cậy của một luật mờ
• 2.3.7. Ưu điểm của việc áp dụng tập mờ để rời rạc hoá dữ liệu
• 2.4. LUẬT KẾT HỢP MỜ VỚI CÁC TOÁN TỬ CÓ NGƯỠNG
• 2.4.1. Toán tử có ngưỡng
• 2.4.2. Định nghĩa: t-chuẩn có ngưỡng
• 2.4.3. Định nghĩa: t-đối chuẩn có ngưỡng
• 2.4.4. Các ký hiệu sử dụng trong thuật toán
• 2.4.5. Các chương trình con sử dụng trong thuật toán
• 2.4.6. Ví dụ minh họa thuật toán
• 2.4.6.1. Ví dụ 2. Chuyển luật kết hợp mờ về luật có thuộc tính số
• 2.4.7. Luật kết hợp mờ với thuộc tính được đánh trọng số
• 2.4.8. Luật thật sự có ích
• 2.4.9. Phương pháp loại bỏ luật thừa
• 2.4.10. Phương pháp tìm luật đơn giản
• 3. CHƯƠNG 3: CÀI ĐẶT THỬ NGHIỆM
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về Nghiên cứu luật kết hợp mờ và toán tử có ngưỡng

Nghiên cứu về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu đang trở thành một lĩnh vực quan trọng trong công nghệ thông tin. Với sự phát triển nhanh chóng của dữ liệu lớn, việc áp dụng các phương pháp khai thác dữ liệu hiệu quả là rất cần thiết. Luật kết hợp mờ cho phép xử lý các dữ liệu không chắc chắn và không rõ ràng, giúp cải thiện độ chính xác trong việc phát hiện các mẫu và mối quan hệ trong dữ liệu.

1.1. Khái niệm về luật kết hợp mờ

Luật kết hợp mờ là một dạng luật có thể mô tả mối quan hệ giữa các thuộc tính trong cơ sở dữ liệu. Nó cho phép xác định các mối quan hệ không chỉ dựa trên các giá trị nhị phân mà còn trên các giá trị mờ, giúp tăng cường khả năng phân tích dữ liệu.

1.2. Tầm quan trọng của toán tử có ngưỡng

Toán tử có ngưỡng giúp xác định các luật kết hợp mờ có độ tin cậy và độ hỗ trợ tối thiểu. Điều này rất quan trọng trong việc lọc ra các luật không có giá trị thực tiễn, từ đó nâng cao hiệu quả của quá trình khai phá dữ liệu.

II. Vấn đề và thách thức trong nghiên cứu luật kết hợp mờ

Mặc dù luật kết hợp mờ mang lại nhiều lợi ích, nhưng vẫn tồn tại một số thách thức trong việc áp dụng chúng. Một trong những vấn đề chính là việc xác định các tham số như độ hỗ trợ và độ tin cậy tối thiểu. Nếu các tham số này không được chọn đúng, có thể dẫn đến việc phát hiện ra các luật không chính xác hoặc không có giá trị thực tiễn.

2.1. Thách thức trong việc xác định tham số

Việc xác định ngưỡng hỗ trợ và độ tin cậy tối thiểu là một thách thức lớn. Nếu ngưỡng quá cao, có thể bỏ lỡ các luật quan trọng; nếu quá thấp, có thể phát hiện ra nhiều luật không có giá trị.

2.2. Vấn đề về dữ liệu không đồng nhất

Dữ liệu không đồng nhất có thể gây khó khăn trong việc áp dụng các thuật toán khai phá luật kết hợp. Các thuộc tính có thể có nhiều dạng khác nhau, làm cho việc phân tích trở nên phức tạp.

III. Phương pháp nghiên cứu luật kết hợp mờ hiệu quả

Để nghiên cứu và phát triển các thuật toán khai phá luật kết hợp mờ, cần áp dụng các phương pháp hiệu quả. Một trong những phương pháp chính là sử dụng thuật toán Apriori và các biến thể của nó để tìm kiếm các tập phổ biến trong cơ sở dữ liệu.

3.1. Thuật toán Apriori trong khai phá luật kết hợp

Thuật toán Apriori là một trong những thuật toán phổ biến nhất để tìm kiếm các tập phổ biến. Nó hoạt động bằng cách duyệt qua cơ sở dữ liệu nhiều lần để xác định các thuộc tính có độ hỗ trợ cao.

3.2. Các biến thể của thuật toán Apriori

Có nhiều biến thể của thuật toán Apriori như AprioriTid và FP-Growth, giúp cải thiện hiệu suất và giảm thiểu thời gian tính toán trong việc tìm kiếm các luật kết hợp mờ.

IV. Ứng dụng thực tiễn của luật kết hợp mờ

Luật kết hợp mờ có nhiều ứng dụng thực tiễn trong các lĩnh vực khác nhau như thương mại điện tử, phân tích thị trường và y tế. Chúng giúp các doanh nghiệp hiểu rõ hơn về hành vi của khách hàng và tối ưu hóa các chiến lược kinh doanh.

4.1. Ứng dụng trong thương mại điện tử

Trong thương mại điện tử, luật kết hợp mờ giúp phân tích hành vi mua sắm của khách hàng, từ đó đưa ra các gợi ý sản phẩm phù hợp, tăng cường trải nghiệm người dùng.

4.2. Ứng dụng trong phân tích thị trường

Luật kết hợp mờ cũng được sử dụng để phân tích các xu hướng thị trường, giúp các doanh nghiệp đưa ra quyết định chiến lược dựa trên dữ liệu thực tế.

V. Kết luận và tương lai của nghiên cứu luật kết hợp mờ

Nghiên cứu về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu đang mở ra nhiều cơ hội mới. Với sự phát triển không ngừng của công nghệ và dữ liệu lớn, việc áp dụng các phương pháp này sẽ ngày càng trở nên quan trọng hơn trong việc phân tích và xử lý thông tin.

5.1. Tương lai của nghiên cứu luật kết hợp mờ

Trong tương lai, nghiên cứu về luật kết hợp mờ sẽ tiếp tục phát triển, với nhiều cải tiến trong thuật toán và ứng dụng thực tiễn. Các nghiên cứu mới sẽ giúp tối ưu hóa quá trình khai phá dữ liệu và nâng cao độ chính xác của các kết quả.

5.2. Hướng nghiên cứu tiếp theo

Các hướng nghiên cứu tiếp theo có thể bao gồm việc phát triển các thuật toán mới, cải tiến các phương pháp hiện tại và mở rộng ứng dụng của luật kết hợp mờ trong các lĩnh vực khác nhau.

Trích đoạn nội dung tài liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Lê Thị Thanh Hải VẤN ĐỀ VỀ LUẬT KẾT HỢP MỜ VÀ CÁC TOÁN TỬ CÓ NGƢỠNG TRONG KHAI PHÁ DỮ LIỆU Ngành: Công nghệ thông tin Mã ngành: 1.10 TÓM TẮT LUẬN VĂN THẠC SỸ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. Bùi Công Cƣờng Hà Nội - 2007 N CHAT LUONG download : add luanvanchat@a Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu MỤC LỤC MỤC LỤC . 2 DANH MỤC BẢNG BIỂU, HÌNH VẼ, CÔNG THỨC & KÍ HIỆU VIẾT TẮT . CHƯƠNG 1 - LUẬT KẾT HỢP . Ý NGHĨA THỰC TIỄN CỦA LUẬT KẾT HỢP . MÔ HÌNH HÌNH THỨC CỦA VẤN ĐỀ PHÁT HIỆN LUẬT . Thuộc tính và CSDL . Độ hỗ trợ của một tập thuộc tính . Tập phổ biến (Frequent Itemset):. Độ hỗ trợ của luật r = X  Y . Độ tin cậy của luật: r = X  Y. Luật kết hợp mạnh: . Bài toán luật kết hợp . Một số tính chất của tập phổ biến và luật kết hợp . THUẬT TOÁN TÌM LUẬT KẾT HỢP. Thuật toán Apriori nhị phân . Các bước thực hiện . Giải thích: . Thuật toán AprioriTid . Giới thiệu thuật toán. Các bước thực hiện . Giải thích . Sinh ra các luật kết hợp mạnh từ tập phổ biến . Thuật toán nhanh hơn:. Thuật toán FP-Growth . CHƯƠNG 2 - LUẬT KẾT HỢP MỜ . Ý NGHĨA VỀ LUẬT KẾT HỢP MỜ . Định nghĩa tập mờ:. 31 2 LUAN VAN CHAT LUONG download : add [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu 2. Các phép toán trên tập mờ: . Số mờ và một số dạng phổ biến . Định nghĩa tập mức: . Định nghĩa số mờ: . Các dạng phổ biến của số mờ: . Các phép toán trong logic mờ (toán tử mờ) . Phép phủ định (negation) . LUẬT KẾT HỢP MỜ . Cơ sở dữ liệu và thuộc tính: . Độ ủng hộ của bản ghi cho mệnh đề . Độ hỗ trợ của mệnh đề . Tập phổ biến . Độ hỗ trợ của một luật mờ:. Độ tin cậy của một luật mờ . Ưu điểm của việc áp dụng tập mờ để rời rạc hoá dữ liệu. LUẬT KẾT HỢP MỜ VỚI CÁC TOÁN TỬ CÓ NGƯỠNG . Toán tử có ngưỡng . Định nghĩa: t-chuẩn có ngưỡng . Định nghĩa: t-đối chuẩn có ngưỡng . Các ký hiệu sử dụng trong thuật toán: . Các chương trình con sử dụng trong thuật toán: . Ví dụ minh họa thuật toán (Ví dụ 2. Chuyển luật kết hợp mờ về luật có thuộc tính số . Luật kết hợp mờ với thuộc tính được đánh trọng số . Luật thật sự có ích . Phương pháp loại bỏ luật thừa . Phương pháp tìm luật đơn giản . CHƯƠNG 3 - CÀI ĐẶT THỬ NGHIỆM . 51 TÀI LIỆU THAM KHẢO . 55 3 LUAN VAN CHAT LUONG download : add [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu DANH MỤC BẢNG BIỂU, HÌNH VẼ, CÔNG THỨC & KÍ HIỆU VIẾT TẮT DANH MỤC BẢNG BIỂU Bảng 1.1 CSDL giao dịch (Ví dụ 1.2 Độ hỗ trợ của các thuộc tính (Ví dụ 1.3 Danh sách các tập mục phổ biến (Ví dụ 1.4 Độ tin cậy của các luật sinh từ tập phổ biến (Ví dụ 1.5 Thực hiện các bước thuật toán Apriori .6 Cơ sở dữ liệu giao dịch (Ví dụ 1.7 Độ hỗ trợ của tất cả các thuộc tính (Ví dụ 1.8 Các tập phổ biến có 1 thuộc tính (Ví dụ 1.9 Cơ sở dữ liệu lần thứ 2 (Ví dụ 1.1 Cơ sở dữ liệu giao tác (Ví dụ 2.2 Cơ sở dữ liệu sau khi rời rạc hóa thuộc tính chỉ mục (Ví dụ 2.3 Cơ sở dữ liệu giao tác (Ví dụ 2.4 Cơ sở dữ liệu mờ (Ví dụ 2.5 Độ hỗ trợ của tập có 1 thuộc tính (Ví dụ 2.6 Độ hỗ trợ của tập có 2 thuộc tính (Ví dụ 2.7 Luật được sinh ra (Ví dụ 2. 45 DANH MỤC HÌNH VẼ Hình 1.1 Cây CSDL khi duyệt lại (Ví dụ 1.2 Cây CSDL kết hợp với bảng thuộc tính (Ví dụ 1.3 Số mờ dạng tam giác .4 Số mờ dạng hình thang .5 Số mờ dạng úp chuông .6 Đồ thị hàm thuộc của các tập mờ của thuộc tính Tuổi .7 Đồ thị hàm thuộc của các tập mờ của thuộc tính TGDSD .8 Đồ thị hàm thuộc của các tập mờ của thuộc tính TGSDHN .2 Giao diện xây dựng các thuộc tính mờ từ thuộc tính gốc ban đầu . 49 4 LUAN VAN CHAT LUONG download : add [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu Hình 3.3 Giao diện Cơ sở dữ liệu mờ .4 Giao diện kết quả sinh các luật tin cậy . 50 DANH MỤC CÔNG THỨC <1.1> Độ hỗ trợ của tập thuộc tính.2> Độ hỗ trợ của luật .3> Độ tin cậy của luật .1> Số mờ dạng tam giác M(a,b,c) .2> Số mờ dạng hình thang M(a,b,c,d) .3> Số mờ dạng úp chuông .4> Độ ủng hộ của bản ghi cho mệnh đề .5> Độ hỗ trợ của mệnh đề .6> Độ hỗ trợ của luật mờ .7> Độ tin cậy của luật mờ .8> Toán tử t-chuẩn có ngưỡng .9> Toán tử t-đối chuẩn có ngưỡng . 38 KÝ HIỆU VIẾT TẮT - CSDL - Database: cơ sở dữ liệu - fminconf - fuzzy minimum confidence: độ tin cậy tối thiểu mờ - fminsupp - fuzzy minimum support: độ hỗ trợ tối thiểu mờ - minconf - minimum confidence: độ tin cậy tối thiểu - minsupp - minimum support: độ hỗ trợ tối thiểu - t-conorm: t-đối chuẩn - TID - Transaction Identification : định danh thuộc tính - t-norm: t-chuẩn 5 LUAN VAN CHAT LUONG download : add [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu MỞ ĐẦU Ngày nay với sự bùng nổ của khoa học công nghệ, của kỹ thuật số đã cho phép số hóa thông tin một cách dễ dàng. Chính vì vậy, với lượng dữ liệu khổng lồ như công văn giấy tờ, chứng từ, tài liệu, thông tin khách hàng, số liệu kinh doanh,…việc đưa ra công cụ để phân tích và xử lý thông tin đã trở thành một vấn đề thiết yếu. Ví dụ đối với ngành kinh doanh, các vấn đề về quảng cáo mặt hàng như thế nào? nên sắp đặt bố trí, nhập hàng ra sao? thường xuyên được đặt ra. Và vì thế, khai phá dữ liệu đã trở thành một hướng nghiên cứu chính trong lĩnh vực khoa học máy tính và công nghệ tri thức để nhằm thực hiện các yêu cầu đó của xã hội. Để có thể chọn lọc được những thông tin có ý nghĩa, nhiều bài toán đã được đưa ra và một trong số đó là Khai phá luật kết hợp. Khai phá luật kết hợp lần đầu tiên được đưa ra vào năm 1993 do Rakesh Agrawal, Tomasz Imielinsky và Arun Swami giới thiệu. Sau đó, năm 1996 được Rakesh Agrawal, Heikki Mannila, Ramakrishnan Srikant, Hannu Toivonen và A. Inkeri Verkamo tiếp tục phát triển. Trong những năm gần đây, người ta tập trung vào cải tiến, phát triển thuật toán hiệu quả hơn từ các thuật toán đã có và xây dựng các thuật toán mới nhằm phát hiện các luật kết hợp có ý nghĩa. Các thông tin về dữ liệu trên thực tế không chỉ tồn tại ở dạng nhị phân (có hoặc không) mà còn định lượng. Chính vì vậy, các khái niệm của tập mờ đã được kết hợp với khai phá luật kết hợp để trở thành một hướng nghiên cứu mới. Việc kết hợp các tập mờ thông qua các toán tử (t-chuẩn, t-đối chuẩn) với ngưỡng là sự mở rộng hơn để giải quyết bài toán khai phá luật kết hợp. Do đây là một lĩnh vực nghiên cứu đang được quan tâm và có nhiều triển vọng nên tôi đã chọn “Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu” làm đề tài cho luận văn của mình. Luận văn được xây dựng trên nền của một số nghiên cứu về lĩnh vực này trong những năm gần đây. Luận văn được tổ chức thành 4 chương như sau: Chương 1: Luật kết hợp. Trong chương này tôi đã trình bày những nét khái quát nhất về khai phá dữ liệu bằng luật kết hợp thông qua việc đưa ra các khái niệm, định nghĩa và bài toán tìm luật kết hợp. Những thuật toán điển hình của luật kết hợp như thuật toán Apriori và một vài thuật toán khác cũng được đề cập để giải quyết bài toán. Chương 2: Luật kết hợp mờ với toán tử có ngưỡng. Ở phần đầu của chương tôi trình bày các khái niệm liên quan đến tập mờ để từ đó làm cơ sở đưa vào bài toán khai phá luật kết hợp. Với các bài toán có thuộc tính số và hạng mục thì việc rời rạc hóa dữ 7 LUAN VAN CHAT LUONG download : add [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu liệu có thể xảy ra một vài nhược điểm như vấn đề “điểm biên gãy”. Vì thế luật kết hợp mờ là một giải pháp rất hiệu quả. Phần cuối chương là các khái niệm về các toán tử có ngưỡng và đưa ra bài toán xây dựng luật kết hợp mờ với các toán tử có ngưỡng. Chương 3: Cài đặt thử nghiệm: Là phần cài đặt thử nghiệm chương trình dùng dữ liệu về việc sử dụng internet. Kết luận: Phần này nêu lại những việc đã thực hiện và kết quả đạt được của luận văn, vấn đề còn chưa được giải quyết thấu đáo và một số hướng nghiên cứu trong tương lai. 8 LUAN VAN CHAT LUONG download : add [e-mail] Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu 1. CHƢƠNG 1 - LUẬT KẾT HỢP Luật kết hợp là một lĩnh vực quan trọng trong khai phá dữ liệu và vì thế kỹ thuật khai phá luật kết hợp ngày càng được quan tâm và phát triển mạnh trong những năm trở lại đây, trở thành một hướng nghiên cứu lớn. Trong chương này, chúng ta cùng tìm hiểu các khái niệm cơ sở và các thuật toán kinh điển của luật kết hợp. Ý NGHĨA THỰC TIỄN CỦA LUẬT KẾT HỢP Luật kết hợp là những luật có dạng: X  Y Trong lĩnh vực bán hàng ta có thể có luật: “40% khách hàng mua cafe thì mua thêm bánh quy, 3% khách hàng mua cả cafe và bánh quy” Ở ví dụ này diễn tả mối quan hệ giữa cafe và bánh quy hay ta có luật X  Y tương đương với cafe  bánh quy. Cafe là tiền đề của luật và bánh quy là kết quả của luật.