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.

Nội dung chính

Tổng quan luận án

Phát hiện luật kết hợp (Association Rule Mining) là một trong những hướng nghiên cứu cốt lõi của lĩnh vực khai phá dữ liệu (Data Mining), được Rakesh Agrawal và cộng sự giới thiệu lần đầu tiên vào năm 1993. Mục tiêu của bài toán là xác định các mối quan hệ dạng điều kiện - hệ quả ($X \to Y$) giữa các phần tử dữ liệu trong các tập dữ liệu lớn. Phần lớn các thuật toán truyền thống tập trung tìm kiếm các luật có độ hỗ trợ (support) và độ tin cậy (confidence) cao (luật mạnh). Tuy nhiên, trong thực tiễn, nhiều sự kiện có tần suất xuất hiện rất thấp nhưng lại mang giá trị thông tin đặc biệt quan trọng (ví dụ: các giao dịch mua hàng có giá trị lớn nhưng ít phát sinh, quan hệ giữa các triệu chứng hiếm và bệnh lý trong y khoa, hiện tượng hỏng hóc thiết bị viễn thông hoặc dấu vết tràn dầu trên ảnh vệ tinh).

Khi áp dụng các thuật toán truyền thống như Apriori để tìm các luật kết hợp hiếm, người dùng bắt buộc phải thiết lập ngưỡng độ hỗ trợ cực tiểu ($\text{minSup}$) rất thấp. Việc này dẫn đến hiện tượng bùng nổ số lượng tập phổ biến ứng viên, làm tăng đột biến chi phí tính toán và bộ nhớ ($O(2^{|I|})$). Các hướng nghiên cứu về luật hiếm trước đây tập trung vào việc sử dụng ràng buộc phần hệ quả hoặc thiết lập đường biên phân chia giữa tập phổ biến và không phổ biến trên cơ sở dữ liệu tác vụ, song còn tồn tại các hạn chế: phải sinh ra toàn bộ các tập không phổ biến, chi phí không gian nhớ cao và tạo ra nhiều luật dư thừa. Đối với cơ sở dữ liệu định lượng, các nghiên cứu trước mới dừng lại ở việc tìm luật từ các tập chỉ chứa các mục dữ liệu không phổ biến thuần túy, chưa giải quyết trường hợp kết hợp giữa mục phổ biến và không phổ biến, đồng thời gặp hiện tượng "điểm biên gãy" khi rời rạc hóa thuộc tính số. Tại Việt Nam, trước thời điểm luận án thực hiện, chưa có công trình luận án tiến sĩ nào nghiên cứu chuyên sâu về phát hiện luật kết hợp hiếm.

Mục tiêu cụ thể của luận án gồm hai nội dung chính:

1. Nghiên cứu cơ sở lý thuyết, phát triển bài toán và đề xuất các thuật toán hiệu quả để phát hiện luật kết hợp hiếm trên cả hai loại cơ sở dữ liệu: cơ sở dữ liệu tác vụ (nhị phân) và cơ sở dữ liệu định lượng.
2. Triển khai ứng dụng một phần kết quả nghiên cứu lý thuyết vào việc xây dựng mô hình phân tích và dự báo cho hai bài toán kinh tế cụ thể: dự báo chỉ số chứng khoán (HNX) và chỉ số giá tiêu dùng (CPI) tại Việt Nam.

Quy trình phát hiện luật kết hợp hiếm tổng quát gồm hai giai đoạn:

• Giai đoạn 1: Tìm tất cả các tập mục dữ liệu hiếm (tập hiếm).
• Giai đoạn 2: Từ các tập hiếm tìm được, sinh ra toàn bộ các luật hiếm thỏa mãn ngưỡng độ tin cậy cực tiểu ($\text{minConf}$).

Luận án xác định phạm vi nghiên cứu tập trung giải quyết Giai đoạn 1 — giai đoạn phức tạp và tốn kém chi phí tính toán nhất. Đối tượng nghiên cứu là các dạng luật kết hợp hiếm Sporadic (tuyệt đối và không tuyệt đối), luật kết hợp có ràng buộc mục dữ liệu âm trên cơ sở dữ liệu tác vụ và cơ sở dữ liệu định lượng (sử dụng lý thuyết tập mờ), cùng mô hình hồi quy chuyển tiếp trơn phi tuyến (STR/LSTR) trong dự báo chuỗi thời gian kinh tế.

---

Tổng quan tài liệu và vị trí của luận án

Luận án đã hệ thống hóa toàn diện các công trình nghiên cứu trong và ngoài nước liên quan đến bài toán phát hiện luật kết hợp và luật kết hợp hiếm, phân định thành các nhóm tiếp cận chính:

1. Khai phá luật kết hợp trên cơ sở dữ liệu tác vụ với một ngưỡng độ hỗ trợ:

   • Phương pháp duyệt toàn bộ tập phổ biến: Duyệt theo chiều rộng (BFS) như thuật toán Apriori của R. Agrawal và R. Srikant (1994), thuật toán phân hoạch Partition của A. Savasere và cộng sự (1995); duyệt theo chiều sâu (DFS) như FP-Growth của J. Han và cộng sự (2000), ECLAT của M. J. Zaki (2000).
   • Phương pháp dựa trên tập phổ biến đóng: N. Pasquier và cộng sự (1999) đề xuất thuật toán CLOSE; M. J. Zaki và C. J. Hsiao (2000, 2002) phát triển thuật toán CHARM dựa trên kết nối Galois và toán tử đóng Galois; J. Pei và cộng sự (2001) đề xuất CLOSET+. Hướng tiếp cận này giúp giảm không gian tìm kiếm từ $2^{|I|}$ xuống kích thước của dàn tập đóng $|LC| = 2^{K|D|}$ (với $K$ là độ dài tập đóng cực đại).
   • Phương pháp dựa trên tập phổ biến cực đại: R. J. Bayardo (1998) với Max-Miner; D. Burdick và cộng sự (2001) với MAFIA; K. Gouda và M. J. Zaki (2001) với GENMAX.

2. Khai phá luật kết hợp với độ hỗ trợ khác nhau, có trọng số hoặc không sử dụng ngưỡng hỗ trợ:

   • Độ hỗ trợ nhiều mức: B. Liu và cộng sự (1999) đề xuất MSApriori dựa trên ngưỡng $\text{MIS}$ cho từng mục dữ liệu; W. Y. Yun và cộng sự (2003) đề xuất thuật toán RSAA sử dụng độ hỗ trợ tương đối; L. Chunjiang và cộng sự (2004); L. S. Reddy và B. P. Rao (2008, 2011) đề xuất thuật toán IMSApriori và mô hình ràng buộc cực tiểu cho cơ sở dữ liệu thưa.
   • Ràng buộc mục dữ liệu và trọng số: R. Srikant và cộng sự (1997); F. Tao và cộng sự (2003) đề xuất khai phá với độ hỗ trợ có trọng số (item weight, itemset weight); S. U. Rahman và cộng sự ứng dụng xử lý song song và tập đóng có trọng số.
   • Ràng buộc độ dài và không sử dụng ngưỡng hỗ trợ: M. Seno và G. Karypis (2005) đề xuất LPMiner với ràng buộc độ hỗ trợ giảm theo độ dài; K. Wang và cộng sự (2002) với mô hình ràng buộc theo thùng dữ liệu; E. Cohen và cộng sự (2001) tiếp cận ma trận thưa qua hàm băm; K. Wang và cộng sự (2003) phát hiện luật tin cậy dựa trên tính chất đóng không gian (upward closure); H. Xiong và cộng sự (2006) đề xuất độ đo H-độ tin cậy khai phá mẫu bó cụm cao (hyperclique).

3. Khai phá luật kết hợp trên cơ sở dữ liệu định lượng:

   • R. Agrawal và R. Srikant (1996) đề xuất phương pháp phân khoảng rời rạc hóa đưa về cơ sở dữ liệu tác vụ, bộc lộ hạn chế làm phình to dữ liệu và gây hiện tượng "biên gãy".
   • Khắc phục biên gãy bằng lý thuyết tập mờ: C. M. Kuok và cộng sự (1998) định nghĩa luật kết hợp mờ và độ hỗ trợ mờ; A. Teuhola (2002) đề xuất kỹ thuật phân hoạch mờ đa chiều từ trên xuống (top-down) với các hàm thành viên chuẩn hóa.

4. Khai phá luật kết hợp hiếm:

   • Ràng buộc phần hệ quả: I. Rahal và cộng sự (2004) dùng cấu trúc SE-tree và P-tree; J. Li và cộng sự (2005) đề xuất phương pháp Emerging Pattern (EP); R. J. Bayardo và cộng sự (2000) phát triển thuật toán Dense-Miner dựa trên hệ số cải tiến ($\text{Imp}$).
   • Đường biên phân chia và tìm kiếm hiếm: L. Szathmary và cộng sự (2007, 2012) đề xuất Apriori-Rare, MRG-Exp, ARIMA và mô hình luật mRG; L. Zhou và cộng sự (2007) đề xuất thuật toán MBS, HBS tìm luật hiếm giữa các mục không phổ biến trên cơ sở dữ liệu tác vụ và định lượng; L. Troiano và cộng sự (2009) đề xuất thuật toán Rarity tìm kiếm từ đỉnh không gian xuống (top-down).
   • Luật Sporadic: Y. S. Koh và N. Rountree (2005) định nghĩa luật Sporadic tuyệt đối và đề xuất thuật toán Apriori-Inverse với ngưỡng $\text{maxSup}$ và $\text{minAS}$; Y. S. Koh và cộng sự (2008) định nghĩa luật Sporadic không tuyệt đối (4 dạng) và thuật toán MIISR.

Khoảng trống nghiên cứu luận án lựa chọn giải quyết: Luận án định vị nghiên cứu vào việc giải quyết hai hạn chế căn bản: (1) Trên cơ sở dữ liệu tác vụ, thay vì tìm kiếm toàn bộ các tập hiếm gây bùng nổ không gian và dư thừa luật, luận án tiếp cận theo hướng tìm kiếm không gian tập hiếm đóng (kế thừa và mở rộng tư tưởng thuật toán CHARM); (2) Trên cơ sở dữ liệu định lượng, khắc phục hạn chế của các phương pháp rời rạc hóa và mở rộng bài toán luật hiếm ngoài phạm vi các mục không phổ biến đơn thuần bằng cách kết hợp lý thuyết tập mờ, định nghĩa luật Sporadic mờ hai ngưỡng và xây dựng thuật toán phát hiện tương ứng.

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Luận án xây dựng nội dung nghiên cứu dựa trên các hệ thống lý thuyết, mô hình toán học và phương pháp luận sau:

Khung lý thuyết và khái niệm hình thức

1. Lý thuyết tập thô và kết nối Galois:

   • Ngữ cảnh khai phá dữ liệu là bộ ba $\hat{D} = (O, I, R)$, trong đó $O = {t_1, t_2, \dots, t_m}$ là tập các tác vụ, $I = {i_1, i_2, \dots, i_n}$ là tập các mục dữ liệu, $R \subseteq I \times O$ là quan hệ nhị phân.
   • Cặp ánh xạ Galois $(f, g)$ giữa $2^O$ và $2^I$ được xác định bởi $f(O') = {i \in I \mid \forall t \in O', (i, t) \in R}$ và $g(I') = {t \in O \mid \forall i \in I', (i, t) \in R}$.
   • Toán tử đóng Galois: $h = f \circ g$ trong $2^I$. Một tập mục $X \subseteq I$ được gọi là tập đóng nếu $h(X) = X$.
   • Tính chất cặp Tập mục dữ liệu $\times$ Tập định danh (IT-pair: $X \times g(X)$): Cho phép cắt tỉa không gian tìm kiếm dựa trên 4 trường hợp quan hệ giữa $g(X_1)$ và $g(X_2)$.

2. Khái niệm luật kết hợp và luật Sporadic:

   • Luật kết hợp cơ bản: $X \to Y$ với $X, Y \subset I, X \cap Y = \emptyset$. Độ hỗ trợ $\sup(X \to Y) = \sup(X \cup Y) / |D|$; độ tin cậy $\text{conf}(X \to Y) = \sup(X \cup Y) / \sup(X)$.
   • Luật Sporadic tuyệt đối hai ngưỡng: Thỏa mãn $\text{conf}(X \to Y) \ge \text{minConf}$, $\sup(X \cup Y) < \text{maxSup}$, và $\forall x \in X \cup Y, \sup(x) < \text{maxSup}$.
   • Luật Sporadic không tuyệt đối hai ngưỡng: Thỏa mãn $\text{conf}(X \to Y) \ge \text{minConf}$, $\sup(X \cup Y) < \text{maxSup}$, và $\exists x \in X \cup Y, \sup(x) \ge \text{maxSup}$.

3. Lý thuyết tập mờ và phân hoạch mờ:

   • Cơ sở dữ liệu mờ liên kết mỗi thuộc tính định lượng $x_j$ với tập khái niệm mờ $F_{x_j}$.
   • Độ hỗ trợ của tập dữ liệu mờ $\langle X, A \rangle$ được tính thông qua toán tử T-norm ($\otimes$) và hàm thành viên $\mu_{c_{x_j}}$ có ngưỡng cắt $w_{c_{x_j}}$: $$\sup(\langle X, A \rangle) = \frac{1}{|O|} \sum_{t_i \in O} \left( \bigotimes_{x_j \in X} \mu'{c{x_j}}(t_i[x_j]) \right)$$
   • Phân hoạch mờ nhiều chiều của A. Teuhola xác định các đường biên $d_i^+, d_j^-$ kết hợp tham số chồng lấp $p$ (%) để xây dựng hàm thành viên hình thang/tam giác liên tục.

4. Mô hình kinh tế lượng hồi quy chuyển tiếp trơn:

   • Mô hình hồi quy chuyển tiếp trơn phi tuyến dạng Logistic (LSTR - Logistic Smooth Transition Regression) phục vụ dự báo các biến động kinh tế có sự thay đổi trạng thái cấu trúc.

Phương pháp thực tế và kỹ thuật xử lý

• Thiết kế thuật toán: Áp dụng phương pháp tiếp cận cấu trúc cây không gian trạng thái, kỹ thuật duyệt cây theo chiều sâu kết hợp kỹ thuật cắt tỉa dựa trên các tính chất của toán tử đóng Galois và danh sách tác vụ (TID-list).
• Thực nghiệm kiểm chứng: Thực hiện cài đặt thuật toán, đo lường thời gian thực thi, số lượng tập mục sinh ra và lượng bộ nhớ tiêu thụ trên các tập dữ liệu chuẩn.

Nguồn tư liệu và dữ liệu thực nghiệm

Luận án sử dụng các nguồn dữ liệu cụ thể sau trong quá trình đánh giá:

• Dữ liệu tổng hợp (Synthetic datasets): Tạo ra từ chương trình sinh dữ liệu chuẩn của IBM Almaden Quest Data Mining Project, bao gồm các tập $T5I1000D10K$, $T30I1000D10K$.
• Dữ liệu thực nghiệm chuẩn: Tệp dữ liệu $Mushroom$ từ kho lưu trữ dữ liệu học máy UCI Machine Learning Repository.
• Dữ liệu kinh tế vĩ mô và tài chính Việt Nam: Dữ liệu chuỗi thời gian giao dịch giá cổ phiếu trên Sở Giao dịch Chứng khoán Hà Nội (tính toán chỉ số HNX) và chuỗi số liệu thống kê giá các nhóm mặt hàng tiêu dùng phục vụ tính toán chỉ số CPI của Tổng cục Thống kê Việt Nam.

---

Nội dung chính theo từng chương

Chương 1 – Phát hiện luật kết hợp và luật kết hợp hiếm

Chương này tổng kết cơ sở lý thuyết tổng quan về luật kết hợp và luật kết hợp hiếm:

• Định nghĩa hình thức bài toán phát hiện luật kết hợp, quy trình chuẩn hai giai đoạn và chứng minh độ phức tạp tính toán $O(2^{|I|})$ của bước tìm tập phổ biến.
• Khảo sát các kỹ thuật khai phá trên cơ sở dữ liệu tác vụ một ngưỡng (Apriori, CHARM, Max-Miner), nhiều ngưỡng (MSApriori, RSAA, IMSApriori), có trọng số và không dùng ngưỡng hỗ trợ.
• Trình bày kỹ thuật khai phá trên cơ sở dữ liệu định lượng, chỉ rõ các nhược điểm của phương pháp rời rạc hóa khoảng số và thiết lập khung lý thuyết cơ sở dữ liệu mờ, các công thức hàm thành viên phân hoạch mờ của Teuhola.
• Tổng hợp các khuynh hướng nghiên cứu luật kết hợp hiếm, phân tích chi tiết hai dạng luật hiếm Sporadic tuyệt đối (thuật toán Apriori-Inverse) và Sporadic không tuyệt đối (thuật toán MIISR).

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ụ

Chương 2 trình bày các đóng góp lý thuyết và thuật toán trọng tâm trên cơ sở dữ liệu tác vụ. Tác giả chứng minh hai tính chất nền tảng: (1) Tập tất cả các tập hiếm cực đại bằng tập tất cả các tập hiếm đóng cực đại; (2) Tập các luật kết hợp hiếm sinh ra từ các tập hiếm và từ các tập hiếm cực đại là như nhau. Từ đó, tác giả đề xuất 3 thuật toán:

1. Thuật toán MCPSI (Mining Closed Perfectly Sporadic Itemsets): Phát hiện tập mục Sporadic tuyệt đối hai ngưỡng đóng. Thuật toán kết hợp không gian tìm kiếm cặp IT-pair và cơ chế cắt tỉa 4 tính chất của CHARM để chỉ sinh ra các tập hiếm đóng, loại bỏ các tập dư thừa.
2. Thuật toán MCISI (Mining Closed Imperfectly Sporadic Itemsets): Phát hiện tập mục Sporadic không tuyệt đối hai ngưỡng đóng. Thuật toán xử lý trường hợp các tập mục kết hợp giữa các mục dữ liệu phổ biến và không phổ biến nhưng có độ hỗ trợ chung nhỏ hơn $\text{maxSup}$.
3. Thuật toán NC-CHARM (Negative Constrains - Closed Association Rules Mining): Phát hiện tập dữ liệu đóng với ràng buộc mục dữ liệu âm, cho phép khai phá các luật kết hợp phản ánh sự vắng mặt của các mục dữ liệu.

Các thuật toán được kiểm nghiệm trên các bộ dữ liệu giả định và tập dữ liệu $Mushroom$, $T5I1000D10K$, $T30I1000D10K$. Kết quả thực nghiệm cho thấy phương pháp tìm tập hiếm đóng giúp giảm đáng kể số lượng tập mục cần lưu trữ và thời gian thực thi so với thuật toán Apriori-Inverse.

Thuật toán	Loại luật / Tập mục phát hiện	Không gian tìm kiếm	Cơ chế cắt tỉa
MCPSI	Sporadic tuyệt đối hai ngưỡng đóng	Cặp IT-pair ($X \times g(X)$)	4 tính chất toán tử đóng Galois
MCISI	Sporadic không tuyệt đối hai ngưỡng đóng	Cặp IT-pair mở rộng	Ràng buộc cận trên $\text{maxSup}$ và cận dưới $\text{minSup}$
NC-CHARM	Tập phổ biến/hiếm có ràng buộc mục âm	Cây tìm kiếm IT-pair âm	Cắt tỉa nhánh chứa mục âm không thỏa mãn

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

Chương 3 mở rộng bài toán sang cơ sở dữ liệu định lượng thông qua lý thuyết tập mờ nhằm khắc phục vấn đề biên gãy:

• Định nghĩa hình thức hai dạng luật mới: Luật kết hợp Sporadic tuyệt đối hai ngưỡng mờ và Luật kết hợp Sporadic không tuyệt đối hai ngưỡng mờ.
• Đề xuất 2 thuật toán khai phá:
  1. Thuật toán MFPSI (Mining Fuzzy Perfectly Sporadic Itemsets): Phát hiện tập mục Sporadic tuyệt đối hai ngưỡng mờ, phát triển dựa trên cấu trúc sinh ứng viên của Apriori kết hợp với tính toán độ hỗ trợ mờ.
  2. Thuật toán MFISI (Mining Fuzzy Imperfectly Sporadic Itemsets): Phát hiện tập mục Sporadic không tuyệt đối hai ngưỡng mờ, xây dựng theo tư tưởng của thuật toán MCISI trên cấu trúc nút dữ liệu mờ.
• Tiến hành thử nghiệm thực nghiệm qua 5 trường hợp cấu hình tham số trên cơ sở dữ liệu mờ, phân tích chi tiết bảng độ hỗ trợ của các tập 1-thuộc tính mờ, 2-thuộc tính mờ và các tập Sporadic mờ thu được tại các nút tìm kiếm.

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ế

Chương 4 trình bày việc ứng dụng liên ngành giữa kỹ thuật khai phá luật kết hợp mẫu âm (thuộc Công nghệ thông tin) và mô hình hồi quy chuyển tiếp trơn logistic phi tuyến LSTR (thuộc Kinh tế lượng):

• Ứng dụng dự báo chỉ số chứng khoán (HNX): Sử dụng thuật toán khai phá mẫu âm để phát hiện mối quan hệ tác động nghịch chiều giữa biến động giá của các mã cổ phiếu thành phần và chỉ số chung HNX. Từ các mẫu âm phát hiện được, lựa chọn các biến chuyển tiếp thích hợp để xây dựng phương trình hồi quy phi tuyến LSTR. Kết quả tính toán chỉ số HNX theo mô hình được đối sánh với dữ liệu thực tế tại Bảng 4.1.
• Ứng dụng dự báo chỉ số giá tiêu dùng (CPI): Ứng dụng khai phá luật mẫu âm để xác định mối quan hệ giữa biến động giá của các nhóm mặt hàng tiêu dùng và chỉ số CPI. Thiết lập mô hình hồi quy chuyển tiếp trơn LSTR dự báo chỉ số CPI. Bảng 4.2 trong luận án tổng hợp kết quả so sánh giá trị CPI tính theo mô hình xây dựng và số liệu thống kê thực tế.

---

Kết quả và những đóng góp mới

Luận án đã đạt được các đóng góp khoa học và thực tiễn chính như sau:

1. Đóng góp về lý luận và thuật toán:

   • Đề xuất hướng tiếp cận mới trong phát hiện luật kết hợp hiếm trên cơ sở dữ liệu tác vụ dựa trên không gian tập dữ liệu hiếm đóng. Chứng minh tính đúng đắn của việc thu hẹp không gian tìm kiếm về tập hiếm đóng cực đại, giúp giải quyết triệt để vấn đề bùng nổ không gian nhớ và hạn chế tối đa các luật hiếm dư thừa.
   • Xây dựng thành công 3 thuật toán mới trên cơ sở dữ liệu tác vụ: MCPSI (tìm tập Sporadic tuyệt đối đóng), MCISI (tìm tập Sporadic không tuyệt đối đóng), và NC-CHARM (tìm tập đóng với ràng buộc mục dữ liệu âm) dựa trên tư tưởng của thuật toán CHARM.
   • Mở rộng thành công bài toán phát hiện luật kết hợp hiếm trên cơ sở dữ liệu định lượng bằng việc tích hợp lý thuyết tập mờ. Định nghĩa hai khái niệm luật Sporadic tuyệt đối hai ngưỡng mờ và không tuyệt đối hai ngưỡng mờ; đề xuất hai thuật toán tương ứng MFPSI và MFISI giúp biểu diễn luật tự nhiên và triệt tiêu hiện tượng "điểm biên gãy".

2. Đóng góp về thực tiễn và ứng dụng:

   • Đề xuất mô hình kết hợp phương pháp phát hiện luật kết hợp mẫu âm trong Công nghệ thông tin với mô hình hồi quy chuyển tiếp trơn phi tuyến (STR/LSTR) trong Kinh tế lượng.
   • Ứng dụng thành công mô hình này vào bài toán phân tích và dự báo biến động của chỉ số chứng khoán HNX và chỉ số giá tiêu dùng CPI tại Việt Nam, mang lại kết quả có độ chính xác cao khi kiểm định với số liệu thực tế.

---

Hạn chế và hướng nghiên cứu tiếp

Dựa trên các nội dung được trình bày trong luận án, một số hạn chế và định hướng phát triển được xác định:

• Hạn chế: Luận án tập trung chủ yếu vào Giai đoạn 1 (bài toán tìm tập mục hiếm và tập mục hiếm đóng); quy trình sinh luật ở Giai đoạn 2 chưa được tối ưu hóa chuyên biệt cho tất cả các dạng luật. Dữ liệu thực nghiệm cho phần ứng dụng mới tập trung vào bài toán kinh tế lượng chuỗi thời gian (HNX, CPI) tại Việt Nam.
• Hướng nghiên cứu tiếp:
  1. Nghiên cứu các giải pháp sinh luật trực tiếp không dư thừa từ tập hiếm đóng tìm được ở Giai đoạn 1.
  2. Nghiên cứu phát triển các độ đo đánh giá độ thú vị (interestingness measures) chuyên biệt cho luật hiếm nhằm nâng cao khả năng lọc nhiễu trong cơ sở dữ liệu thực.
  3. Mở rộng thuật toán phát hiện luật hiếm trên các cấu trúc dữ liệu phức tạp hơn như dữ liệu dòng (data stream), cơ sở dữ liệu đồ thị hoặc dữ liệu phân tán.

---

Giá trị tham khảo

Luận án là tài liệu tham khảo có giá trị chuyên môn cao cho các nhóm đối tượng:

• Nghiên cứu sinh, học viên cao học, giảng viên ngành Công nghệ thông tin và Hệ thống thông tin: Tham khảo chi tiết Chương 1, Chương 2 và Chương 3 về kỹ thuật kết nối Galois, cấu trúc toán tử đóng, thuật toán khai phá tập đóng (CHARM), thuật toán khai phá luật Sporadic và kỹ thuật phân hoạch mờ đa chiều.
• Nhà nghiên cứu, chuyên gia phân tích dữ liệu trong lĩnh vực Kinh tế, Tài chính, Thống kê: Tham khảo Chương 4 về quy trình phối hợp giữa kỹ thuật khai phá mẫu âm (Negative Patterns) và mô hình hồi quy phi tuyến chuyển tiếp trơn (LSTR) để xử lý dữ liệu chuỗi thời gian vĩ mô và dự báo chỉ số tài chính.

---

Câu hỏi thường gặp

1. Tại sao các thuật toán phát hiện luật kết hợp truyền thống (như Apriori) không hiệu quả khi tìm luật kết hợp hiếm?

Khi tìm luật kết hợp hiếm bằng thuật toán truyền thống, người dùng phải hạ ngưỡng $\text{minSup}$ xuống mức rất nhỏ để bao hàm được các mục dữ liệu hiếm. Điều này dẫn đến sự bùng nổ số lượng tập phổ biến ứng viên ở các mức kích thước khác nhau (độ phức tạp $O(2^{|I|})$), trong khi phần lớn các tập tìm được không phải là tập hiếm mục tiêu, gây lãng phí bộ nhớ và chi phí quét cơ sở dữ liệu.

2. Sự khác nhau giữa luật Sporadic tuyệt đối và luật Sporadic không tuyệt đối là gì?

Luật Sporadic tuyệt đối đòi hỏi toàn bộ các mục dữ liệu đơn lẻ cấu thành nên luật đều phải có độ hỗ trợ nhỏ hơn ngưỡng $\text{maxSup}$ ($\forall x \in X \cup Y, \sup(x) < \text{maxSup}$). Ngược lại, luật Sporadic không tuyệt đối chỉ yêu cầu độ hỗ trợ của toàn bộ tập hợp luật nhỏ hơn $\text{maxSup}$ ($\sup(X \cup Y) < \text{maxSup}$), nhưng cho phép tồn tại ít nhất một mục dữ liệu đơn lẻ có độ hỗ trợ lớn hơn hoặc bằng $\text{maxSup}$ ($\exists x \in X \cup Y, \sup(x) \ge \text{maxSup}$).

3. Cơ sở lý thuyết nào cho phép luận án chỉ tìm tập hiếm đóng thay vì toàn bộ tập hiếm trên cơ sở dữ liệu tác vụ?

Luận án dựa trên hai tính chất toán học: (1) Tập tất cả các tập hiếm cực đại và tập tất cả các tập hiếm đóng cực đại là bằng nhau; (2) Các luật kết hợp hiếm sinh ra từ tập hiếm và từ tập hiếm cực đại là như nhau. Do không gian tập đóng nhỏ hơn nhiều so với không gian toàn bộ các tập con, việc chỉ tìm tập hiếm đóng giúp giảm tối đa chi phí tính toán và loại bỏ các luật dư thừa.

4. Thuật toán NC-CHARM được phát triển nhằm mục đích gì?

Thuật toán NC-CHARM (Negative Constrains - Closed Association Rules Mining) được tác giả phát triển dựa trên tư tưởng của thuật toán CHARM nhằm phát hiện tập dữ liệu đóng có chứa các ràng buộc mục dữ liệu âm. Thuật toán phục vụ việc khai phá các luật kết hợp thể hiện mối quan hệ xuất hiện của mục này kéo theo sự vắng mặt của mục khác.

5. Việc áp dụng lý thuyết tập mờ vào khai phá luật kết hợp định lượng giải quyết được vấn đề gì?

Phương pháp rời rạc hóa truyền thống chia thuộc tính số thành các khoảng rời rạc dẫn đến hiện tượng "biên gãy" (các giá trị rất gần nhau như 59 tuổi và 60 tuổi bị phân vào hai khoảng đối lập "trung niên" và "già"). Lý thuyết tập mờ cho phép một giá trị thuộc về nhiều tập mờ với các mức độ thuộc khác nhau thông qua hàm thành viên liên tục, giúp phản ánh dữ liệu tự nhiên và tránh làm phình to số lượng thuộc tính nhị phân.

---

Kết luận

Luận án tiến sĩ của tác giả Cù Thu Thủy đã giải quyết trọn vẹn bài toán phát hiện tập mục hiếm (Giai đoạn 1) cho cả hai loại cơ sở dữ liệu tác vụ và định lượng. Bằng việc đề xuất hướng tiếp cận không gian tập đóng và tích hợp lý thuyết tập mờ, luận án đã xây dựng 5 thuật toán mới (MCPSI, MCISI, NC-CHARM, MFPSI, MFISI) giúp tối ưu hóa hiệu năng tính toán và loại bỏ luật dư thừa. Đồng thời, công trình đã chứng minh tính ứng dụng thực tiễn thông qua việc kết hợp luật mẫu âm với mô hình hồi quy phi tuyến LSTR để phân tích và dự báo chính xác các chỉ số kinh tế vĩ mô (HNX, CPI) tại Việt Nam.

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.