Nghiên Cứu Phát Hiện Luật Kết Hợp Hiếm và Ứng Dụng

Nghiên cứu luật kết hợp hiếm và ứng dụng của nó trong thực tiễn, mang lại cái nhìn sâu sắc về các hiện tượng phức tạp trong khoa học.

• Tác giả: Cù Thu Thủy
• Người hướng dẫn: PGS. Đỗ Văn Thành
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Phát Hiện Luật Kết Hợp Hiếm: Nghiên Cứu và Ứng Dụng
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2013
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỤC LỤC
• DANH MỤC CÁC KÍ HIỆU VÀ CHỮ VIẾT TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
• MỞ ĐẦU
• 0.1. Lý do chọn đề tài
• 0.2. Mục tiêu cụ thể và phạm vi nghiên cứu của luận án
• 0.3. Ý nghĩa khoa học và thực tiễn của luận án
• 0.4. Đóng góp của luận án
• 0.5. Cấu trúc của luận án
• 1. CHƯƠNG 1: PHÁT HIỆN LUẬT KẾT HỢP VÀ LUẬT KẾT HỢP HIẾM
• 1.1. Luật kết hợp và phương pháp chung phát hiện luật kết hợp
• 1.2. Bài toán phát hiện luật kết hợp
• 1.3. Quy trình hai bước phát hiện luật kết hợp
• 1.4. Phát hiện luật kết hợp từ CSDL tác vụ
• 1.5. Phát hiện luật kết hợp với một ngưỡng độ hỗ trợ
• 1.6. Phát hiện luật kết hợp với độ hỗ trợ khác nhau
• 1.7. Phát hiện luật kết hợp từ CSDL định lượng
• 1.8. Phát hiện luật kết hợp định lượng
• 1.9. Phát hiện luật kết hợp mờ
• 1.10. Phân hoạch mờ
• 1.11. Phát hiện luật kết hợp hiếm
• 1.12. Giới thiệu chung về luật kết hợp hiếm
• 1.13. Một số hướng nghiên cứu chính phát hiện luật kết hợp hiếm
• 1.14. Luật hiếm Sporadic
• 1.15. Khuynh hướng nghiên cứu về luật hiếm
• 2. CHƯƠNG 2: PHÁT HIỆN LUẬT KẾT HỢP HIẾM TRÊN CƠ SỞ DỮ LIỆU TÁC VỤ
• 2.1. Luật kết hợp Sporadic tuyệt đối hai ngưỡng
• 2.2. Giới thiệu về luật Sporadic tuyệt đối hai ngưỡng
• 2.3. Tập Sporadic tuyệt đối hai ngưỡng
• 2.4. Thuật toán tìm tập Sporadic tuyệt đối hai ngưỡng đóng
• 2.5. Luật kết hợp Sporadic không tuyệt đối hai ngưỡng
• 2.6. Giới thiệu về luật kết hợp Sporadic không tuyệt đối hai ngưỡng
• 2.7. Tập Sporadic không tuyệt đối hai ngưỡng
• 2.8. Thuật toán tìm tập Sporadic không tuyệt đối hai ngưỡng đóng
• 2.9. Luật kết hợp với ràng buộc mục dữ liệu âm
• 2.10. Giới thiệu về luật kết hợp với ràng buộc mục dữ liệu âm
• 2.11. Tập phổ biến có ràng buộc mục dữ liệu âm
• 2.12. Thuật toán tìm tập phổ biến với ràng buộc mục dữ liệu âm
• 3. CHƯƠNG 3: PHÁT HIỆN LUẬT KẾT HỢP HIẾM TRÊN CƠ SỞ DỮ LIỆU ĐỊNH LƯỢNG
• 3.1. Giới thiệu về phát hiện luật kết hợp hiếm trên CSDL định lượng
• 3.2. Luật kết hợp Sporadic tuyệt đối hai ngưỡng mờ
• 3.3. Giới thiệu về luật Sporadic tuyệt đối hai ngưỡng mờ
• 3.4. Tập Sporadic tuyệt đối hai ngưỡng mờ
• 3.5. Thuật toán tìm tập Sporadic tuyệt đối hai ngưỡng mờ
• 3.6. Luật kết hợp Sporadic không tuyệt đối hai ngưỡng mờ
• 3.7. Giới thiệu về luật Sporadic không tuyệt đối hai ngưỡng mờ
• 3.8. Tập Sporadic không tuyệt đối hai ngưỡng mờ
• 3.9. Thuật toán tìm tập Sporadic không tuyệt đối hai ngưỡng mờ
• 4. CHƯƠNG 4: ỨNG DỤNG LUẬT KẾT HỢP MẪU ÂM VÀ MÔ HÌNH HỒI QUY CHUYỂN TIẾP TRƠN TRONG PHÂN TÍCH VÀ DỰ BÁO KINH TẾ
• 4.1. Mô hình hồi quy chuyển tiếp trơn
• 4.2. Phân tích hồi quy
• 4.3. Mô hình hồi quy chuyển tiếp trơn logistic
• 4.4. Xây dựng mô hình hồi quy chuyển tiếp trơn logistic
• 4.5. Ứng dụng luật kết hợp mẫu âm và mô hình hồi quy chuyển tiếp trơn trong xây dựng mô hình phân tích và dự báo chỉ số chứng khoán
• 4.6. Dữ liệu phục vụ xây dựng mô hình
• 4.7. Phát hiện mối quan hệ giữa chỉ số chứng khoán và các cổ phiếu
• 4.8. Xây dựng mô hình dự báo chỉ số chứng khoán
• 4.9. Ứng dụng luật kết hợp mẫu âm và mô hình hồi quy chuyển tiếp trơn trong xây dựng mô hình dự báo chỉ số giá tiêu dùng (CPI)
• 4.10. Dữ liệu phục vụ xây dựng mô hình dự báo chỉ số CPI
• 4.11. Phát hiện mối quan hệ giữa giá hàng hóa và chỉ số CPI
• 4.12. Xây dựng mô hình dự báo chỉ số CPI
• KẾT LUẬN
• DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ CÓ LIÊN QUAN ĐẾN LUẬN ÁN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Phát Hiện Luật Kết Hợp Hiếm Trong Nghiên Cứu

Phát hiện luật kết hợp hiếm là một lĩnh vực nghiên cứu quan trọng trong khai phá dữ liệu. Luật kết hợp hiếm đề cập đến những mối quan hệ giữa các phần tử dữ liệu mà ít xảy ra nhưng lại có giá trị cao. Nghiên cứu này không chỉ giúp hiểu rõ hơn về các mối quan hệ trong dữ liệu mà còn mở ra nhiều ứng dụng thực tiễn trong các lĩnh vực như thương mại, y tế và tài chính.

1.1. Khái Niệm Về Luật Kết Hợp Hiếm

Luật kết hợp hiếm là những luật có tần suất xảy ra thấp nhưng lại mang lại thông tin quý giá. Ví dụ, luật kết hợp giữa 'máy pha cà phê' và 'máy xay cà phê' có độ hỗ trợ thấp nhưng độ tin cậy cao.

1.2. Lịch Sử Phát Triển Nghiên Cứu Luật Kết Hợp

Lý thuyết luật kết hợp được giới thiệu lần đầu tiên vào năm 1993 bởi Rakesh Agrawal. Từ đó, nhiều nghiên cứu đã được thực hiện để phát triển các thuật toán phát hiện luật kết hợp hiếm.

II. Thách Thức Trong Phát Hiện Luật Kết Hợp Hiếm

Mặc dù phát hiện luật kết hợp hiếm có nhiều tiềm năng, nhưng vẫn tồn tại nhiều thách thức. Việc tìm kiếm các luật hiếm thường gặp khó khăn do tần suất thấp và chi phí tính toán cao. Các thuật toán hiện tại thường không hiệu quả khi áp dụng cho luật hiếm.

2.1. Chi Phí Tính Toán Cao

Việc phát hiện luật kết hợp hiếm yêu cầu đặt ngưỡng độ hỗ trợ cực tiểu rất nhỏ, dẫn đến chi phí tính toán tăng cao do số lượng luật tìm được lớn.

2.2. Thiếu Hiệu Quả Trong Các Thuật Toán Hiện Tại

Nhiều thuật toán hiện tại chỉ tập trung vào các luật có độ hỗ trợ và độ tin cậy cao, bỏ qua các luật hiếm có giá trị.

III. Phương Pháp Phát Hiện Luật Kết Hợp Hiếm Hiệu Quả

Để giải quyết các thách thức trong phát hiện luật kết hợp hiếm, nhiều phương pháp mới đã được đề xuất. Các phương pháp này tập trung vào việc tối ưu hóa quy trình phát hiện và giảm thiểu chi phí tính toán.

3.1. Sử Dụng Ràng Buộc Trong Phát Hiện Luật

Một trong những phương pháp hiệu quả là sử dụng ràng buộc phần hệ quả của luật để giảm thiểu không gian tìm kiếm và tăng cường độ chính xác.

3.2. Thuật Toán MCPSI và NC CHARM

Các thuật toán như MCPSI và NC-CHARM được phát triển để tìm kiếm các tập mục hiếm một cách hiệu quả hơn, giảm thiểu chi phí tính toán.

IV. Ứng Dụng Thực Tiễn Của Luật Kết Hợp Hiếm

Luật kết hợp hiếm đã được ứng dụng trong nhiều lĩnh vực khác nhau, từ thương mại đến y tế. Các ứng dụng này không chỉ giúp cải thiện quy trình ra quyết định mà còn tối ưu hóa các chiến lược kinh doanh.

4.1. Ứng Dụng Trong Thương Mại

Trong thương mại, phát hiện luật kết hợp hiếm 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 dịch marketing.

4.2. Ứng Dụng Trong Y Tế

Trong lĩnh vực y tế, luật kết hợp hiếm có thể giúp phát hiện các mối liên hệ giữa các triệu chứng và bệnh tật, từ đó cải thiện quy trình chẩn đoán.

V. Kết Luận Về Nghiên Cứu Luật Kết Hợp Hiếm

Nghiên cứu về phát hiện luật kết hợp hiếm đang ngày càng trở nên quan trọng trong bối cảnh dữ liệu ngày càng lớn. Các phương pháp mới và ứng dụng thực tiễn sẽ tiếp tục được phát triển để tối ưu hóa quy trình phát hiện và ứng dụng luật kết hợp hiếm.

5.1. Tương Lai Của Nghiên Cứu Luật Kết Hợp Hiếm

Tương lai của nghiên cứu luật kết hợp hiếm hứa hẹn sẽ có nhiều tiến bộ với sự phát triển của công nghệ và thuật toán mới.

5.2. Đề Xuất Hướng Nghiên Cứu Mới

Cần tiếp tục nghiên cứu để phát triển các thuật toán hiệu quả hơn và mở rộng ứng dụng của luật kết hợp hiếm trong các lĩnh vực khác nhau.

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

Chương 1 – PHÁT HIỆN LUẬT KẾT HỢP VÀ LUẬT KẾT HỢP HIẾM Đầu tiên, chương này giới thiệu tổng quan về luật kết hợp: khái niệm luật kết hợp, bài toán phát hiện luật kết hợp, phương pháp chung phát hiện luật kết hợp, phát hiện luật kết hợp với độ hỗ trợ cực tiểu không giống nhau. Tiếp theo, vấn đề phát hiện luật kết hợp từ CSDL định lượng được trình bày. Phần cuối của chương sẽ trình bày về vấn đề phát hiện luật kết hợp hiếm: giới thiệu chung về luật kết hợp hiếm, một số hướng nghiên cứu chính và khuynh hướng nghiên cứu về luật kết hợp hiếm. Luật kết hợp và phương pháp chung phát hiện luật kết hợp 1.

Bài toán phát hiện luật kết hợp Mục đích của bài toán phát hiện luật kết hợp là tìm ra mối quan hệ giữa các tập mục dữ liệu trong các CSDL lớn và các mối quan hệ này là có ích trong hỗ trợ quyết định. Trong CSDL siêu thị, việc phát hiện được quan hệ "78% số khách hàng mua sữa và đường cũng mua bơ" sẽ rất có ích cho quyết định kinh doanh, chẳng hạn, quyết định về số lượng nhập các mặt hàng này hoặc bố trí chúng tại các ngăn hàng liền kề nhau. Trong CSDL dân số, quan hệ "60% số người lao động ở độ tuổi trung niên có thu nhập thấp hơn mức thu nhập bình quân" sẽ rất có ích cho việc điều chỉnh chính sách thu nhập [13, 14, 16]. Khái niệm luật kết hợp (Association Rule) và phát hiện luật kết hợp (Association Rule Mining) được Rakesh Agrawal và cộng sự đề xuất lần đầu tiên vào năm 1993 nhằm phát hiện các mẫu có giá trị trong CSDL tác vụ (transaction database) tại siêu thị [10].

Bài toán này được phát biểu hình thức như dưới đây., in} là tập các mục dữ liệu (mỗi mặt hàng trong siêu thị chính là một mục dữ liệu, và cũng có thể xem nó là một thuộc tính nhận giá trị nhị phân, khi đó I là các thuộc tính của CSDL); tập X Ì I được gọi là tập mục dữ liệu hoặc tập mục (itemset); và O = {t1, t2,., tm} là tập định danh của các tác vụ (mỗi vụ mua hàng được xem là một tác vụ). Quan hệ D Í I´O được gọi là CSDL tác vụ. 18 Mỗi tác vụ t được biểu diễn như một véc tơ nhị phân, trong đó t[k] = 1 nếu mặt hàng ik xuất hiện trong t và ngược lại t[k] = 0. Cho một tập mục dữ liệu X Í I, độ hỗ trợ của tập X, kí hiệu là sup(X), được định nghĩa là số (hoặc phần trăm) tác vụ trong D chứa X.

Luật kết hợp (association rule) được định nghĩa hình thức là biểu diễn mối quan hệ giữa hai tập mục dưới dạng X ® Y, trong đó X Í I, Y Í I, XÇY = Æ. X được gọi là phần tiền đề (antecedent) và Y được gọi là phần hệ quả (consequent) của luật. Độ hỗ trợ (support) của luật X ® Y, kí hiệu là sup(X ® Y), được định nghĩa là số (hoặc phần trăm) tác vụ trong D chứa XÈY. và cộng sự [13], luật kết hợp được phát hiện cần đáp ứng ràng buộc độ hỗ trợ (support constraint), theo đó, độ hỗ trợ của tập mục W = XÈY (hợp tập tiền đề và tập hệ quả của luật) phải vượt qua (không nhỏ thua) một ngưỡng hỗ trợ tối thiểu do người dùng đưa vào.

Mọi tập W có tính chất nói trên được gọi là tập phổ biến (frequent itemset) và còn được gọi là tập mục lớn (large itemset). Độ tin cậy (confidence) của luật X ® Y, kí hiệu là conf(X ® Y), được định nghĩa là số (hoặc phần trăm) tác vụ trong D chứa X cũng chứa Y.2) sup( X ) Luật kết hợp được phát hiện cần có tính tin cậy, theo đó nó cần có độ tin cậy vượt qua (không nhỏ thua) một ngưỡng tin cậy tối thiểu do người dùng đưa vào. Luật đáp ứng ràng buộc độ hỗ trợ và có tính tin cậy được gọi là luật mạnh (strong association rule). Quy trình hai bước phát hiện luật kết hợp Mục đích của bài toán phát hiện luật kết hợp trong CSDL tác vụ D là đi tìm tất cả các luật kết hợp mạnh (độ hỗ trợ cực tiểu và độ tin cậy cực tiểu do người sử dụng 19 đưa ra trong quá trình phát hiện luật).

Rất nhiều giải pháp phát hiện luật kết hợp đã được đề xuất, chẳng hạn, theo thống kê của MicroSoft [101], đã có 2671 tác giả công bố 1526 công trình khoa học có giá trị (với 10224 lần được chỉ dẫn) về phát hiện luật kết hợp. Phần lớn các thuật toán phát hiện luật kết hợp chia quá trình giải bài toán này thành hai giai đoạn như sau: (1) Giai đoạn 1: Tìm tất cả các tập phổ biến trong CSDL D. (2) Giai đoạn 2: Với mỗi tập phổ biến I1 tìm được ở giai đoạn 1, sinh ra tất cả các luật mạnh có dạng I2 ® I1 – I2, I2 Ì I1. Trong hai giai đoạn trên, giai đoạn 1 là khó khăn, phức tạp và tốn nhiều chi phí.

Bài toán tìm tập phổ biến trong không gian các tập con của tập mục I có độ phức tạp tính toán là O(2|I|). Giai đoạn 2 được giải quyết đơn giản hơn khi đã có các tập phổ biến và độ hỗ trợ của chúng. Các phần tiếp theo sẽ trình bày một cách cơ bản, tóm lược về tiến trình phát triển nghiên cứu về luật kết hợp. Ban đầu là nghiên cứu phát hiện luật kết hợp trong các CSDL tác vụ, có độ hỗ trợ cực tiểu chung như nhau và chúng đều là các luật mạnh,., tiếp theo được mở rộng sang CSDL định lượng, và/hoặc độ hỗ trợ cực tiểu của các luật kết hợp là không giống nhau và/hoặc các luật kết hợp là luật hiếm,.

Nói cách khác nghiên cứu phát hiện luật kết hợp càng càng được phát triển để thích ứng với nhu cầu đa dạng của thực tiễn. Phát hiện luật kết hợp từ CSDL tác vụ Phát hiện luật kết hợp trong CSDL tác vụ được khởi đầu từ phát hiện luật kết hợp với một ngưỡng độ hỗ trợ, và sau đó, tới phát hiện luật kết hợp với độ hỗ trợ khác nhau cho các mục dữ liệu. Phát hiện luật kết hợp với một ngưỡng độ hỗ trợ Trong giai đoạn đầu tiên, bài toán phát hiện luật kết hợp đề cập tới một ngưỡng độ hỗ trợ chung (độ hỗ trợ cực tiểu) do người sử dụng đưa vào. Việc phát hiện luật kết hợp tuân thủ theo quy trình chung hai bước, chủ yếu tập trung vào bước tìm ra tập các tập phổ biến, với ba hướng giải quyết: 20 - Tìm tất cả các tập phổ biến.

- Tìm tất cả các tập phổ biến đóng. - Tìm tất cả các tập phổ biến cực đại. Phát hiện luật kết hợp từ tất cả các tập phổ biến Đây là cách tiếp cận nguyên thủy [13]. Các phương pháp thuộc cách tiếp cận này được chia thành các phương pháp duyệt không gian tìm kiếm và các phương pháp xác định trước độ hỗ trợ.

Bỏ qua độ phức tạp vào – ra và tính toán khi duyệt CSDL, các thuật toán này đều thực hiện tìm kiếm trên cây các tập con của tập mục I vì vậy độ phức tạp tính toán là O(2|I|). Phương pháp duyệt không gian tìm kiếm được chia thành hai nhóm tương ứng khi duyệt cây các tập mục: duyệt theo chiều rộng (Breadth First Search - BFS) và duyệt theo chiều sâu (Depth First Search - DFS). Duyệt theo chiều rộng là duyệt theo kích thước k của các tập mục ứng viên lần lượt từ kích thước 1, 2. Một số thuật toán phổ biến theo cách tiếp cận này là: Apriori [16], Partition [70],., mà theo [88], thuật toán Apriori (hình 1.1, kí hiệu diễn giải ở trong bảng 1.1) được xếp vào tốp 10 thuật toán khai phá dữ liệu điển hình nhất.

Duyệt theo chiều sâu là duyệt xong các tập ứng viên liên quan với một tập mục phổ biến mới chuyển sang xem xét đối với tập phổ biến cùng kích thước khác. Các thuật toán điển hình theo cách tiếp cận này là: FP-Growth [42], ECLAT [96],.1: Bảng diễn giải các kí hiệu sử dụng trong thuật toán Apriori Kí hiệu Ý nghĩa k-itemsets Tập k – mục dữ liệu. Lk Tập các k - tập dữ liệu phổ biến. Mỗi một phần tử của tập này có 2 trường: i) tập dữ liệu và ii) độ hỗ trợ Ck Tập các k - tập dữ liệu ứng cử viên (tiềm năng là tập phổ biến).

Mỗi một phần tử của tập này có 2 trường: i) tập dữ liệu và ii) độ hỗ trợ 21 Đầu vào: CSDL D, độ hỗ trợ cực tiểu minSup Kết quả: Tập các tập phổ biến Thuật toán Apriori tìm các tập phổ biến: 1. L1 ¬ {1- tập mục dữ liệu phổ biến } 2. for (k ¬ 2; Lk-1 ¹ Æ; k++) do begin 3. Ck ¬ Apriori-gen(Lk-1); // sinh các ứng cử viên k-mục dữ liệu 4.

forall transactions tÎD do begin 5. Ct ¬ subset(Ck, t); // ứng cử viên được chứa trong t 6. forall candidates cÎ Ct do 7. Lk ¬{cÎ Ck | c.

Answer ¬ Èk Lk Hàm Apriori-Gen sinh ra ứng cử viên: Procedure apriori-gen(Lk-1) insert into Ck //bước kết nối select p.itemk-1 from Lk-1 p, Lk-1 q where p.itemk-1; forall itemsets c Î Ck do //bước tỉa forall (k-1)-subsets s of c do if (s Ï Lk-1) then delete c from Ck; Hình 1.1: Thuật toán Apriori Đối với các CSDL lớn, độ phức tạp vào-ra và tính toán khi duyệt CSDL là rất lớn, cho nên các phương pháp xác định trước độ hỗ trợ được phát triển nhằm làm giảm số lần truy cập CSDL. Một số phương pháp cho phép xây dựng các cấu trúc dữ liệu trung gian thích hợp để phát hiện các tập phổ biến chỉ cần hai lần duyệt CSDL [70, 71]. Phát hiện luật kết hợp từ các tập phổ biến đóng Như đã biết, bài toán tìm tập phổ biến nói chung có độ phức tạp tính toán O(2|I|). Một trong các hướng giảm độ phức tạp tính toán là phát triển các phương pháp giảm số lượng tập mục phải duyệt.

Hsiao [94] định nghĩa kết nối Galois và tập mục dữ liệu đóng, xây dựng dàn tập mục dữ liệu đóng để tìm tập phổ biến đóng cho phép giảm thiểu độ phức tạp tính toán do số lượng tập phổ biến đóng nhỏ hơn số lượng tập phổ biến. Về lý thuyết, kích cỡ của dàn tập mục đóng là |LC| = 2K|D| với K là độ dài của tập đóng cực đại. Kết quả thực nghiệm cho thấy tốc độ phát triển trung bình không gian tìm kiếm nhỏ hơn 2K. Một số thuật toán tìm tập phổ biến đóng thông dụng là: CHARM [94], CLOSE [64], CLOSET+ [65],.

Thuật toán CHARM được đánh giá là thuật toán hiệu quả nhất trong việc tìm các tập phổ biến đóng.