I. Tổng Quan Nghiên Cứu Luật Kết Hợp Hiếm Trong Hệ Thống
Trong lĩnh vực khai phá dữ liệu (Data Mining), luật kết hợp (Association Rule) đóng vai trò quan trọng. Nó giúp chúng ta hiểu rõ mối quan hệ giữa các phần tử dữ liệu, ví dụ: sự xuất hiện của một tập mặt hàng này kéo theo sự xuất hiện của tập mặt hàng khác trong hệ thống thông tin. Phát hiện luật kết hợp chính là việc tìm kiếm những mối quan hệ này trong một tập dữ liệu cho trước. Lý thuyết về luật kết hợp được giới thiệu lần đầu tiên vào năm 1993 và nhanh chóng trở thành một trong những hướng nghiên cứu khai phá dữ liệu quan trọng, đặc biệt trong những năm gần đây. Luật kết hợp hiếm là những luật ít xảy ra. Mặc dù tần suất thấp, chúng lại có giá trị cao trong nhiều trường hợp. Một ví dụ điển hình là luật 'máy pha cà phê' → 'máy xay cà phê' có độ hỗ trợ thấp nhưng độ tin cậy cao và giá trị bán hàng đáng kể. Để khai phá hiệu quả luật kết hợp hiếm, các thuật toán đặc biệt đã được phát triển, tập trung vào việc tìm kiếm các mẫu dữ liệu ít phổ biến nhưng mang ý nghĩa quan trọng.
1.1. Khái niệm Luật Kết Hợp và Tầm Quan Trọng
Luật kết hợp mô tả mối quan hệ giữa các mục dữ liệu trong một tập dữ liệu lớn. Việc khai phá luật kết hợp giúp tìm ra các mẫu tiềm ẩn và hữu ích. Trong hệ thống thông tin, các luật này có thể giúp đưa ra các quyết định kinh doanh thông minh, cải thiện dịch vụ khách hàng, và tối ưu hóa quy trình hoạt động. Ví dụ, trong siêu thị, luật kết hợp có thể chỉ ra rằng khách hàng mua tã thường mua thêm sữa, từ đó giúp siêu thị sắp xếp hàng hóa hợp lý hơn. Việc ứng dụng luật kết hợp đã được chứng minh trong nhiều lĩnh vực kinh tế-xã hội.
1.2. Giới Thiệu Về Luật Kết Hợp Hiếm Rare Association Rules
Luật kết hợp hiếm, hay còn gọi là luật hiếm, là những luật ít khi xảy ra trong một tập dữ liệu. Mặc dù có tần suất xuất hiện thấp, những luật này thường mang lại những thông tin giá trị, đặc biệt trong các lĩnh vực như y tế, tài chính, và an ninh mạng. Việc phát hiện và phân tích luật kết hợp hiếm đòi hỏi các thuật toán và phương pháp đặc biệt, bởi vì các thuật toán truyền thống thường tập trung vào việc tìm kiếm các luật phổ biến. Rountree đã trình bày khái quát về ứng dụng của khai phá luật hiếm, trong đó giới thiệu ví dụ luật kết hợp hiếm “máy pha cà phê” → “máy xay cà phê” có độ hỗ trợ rất thấp là 0,8% song có độ tin cậy khá cao tới 80% và giá trị bán hai mặt hàng này rất đáng kể.
II. Thách Thức Khi Phát Hiện Luật Kết Hợp Hiếm Trong Data Mining
Việc phát hiện luật kết hợp hiếm đặt ra nhiều thách thức. Các thuật toán truyền thống tập trung vào các luật có độ hỗ trợ và độ tin cậy cao. Áp dụng chúng để tìm luật hiếm (độ hỗ trợ thấp) không hiệu quả. Điều này đòi hỏi việc đặt ngưỡng hỗ trợ tối thiểu rất nhỏ, dẫn đến số lượng lớn các tập phổ biến, làm tăng chi phí tìm kiếm. Các thuật toán phát hiện luật kết hợp hiếm ra đời để giải quyết vấn đề này. Hai hướng tiếp cận chính là sử dụng ràng buộc phần hệ quả của luật và tập trung vào các mục dữ liệu không phổ biến. Tuy nhiên, cả hai hướng đều có hạn chế, đòi hỏi các nghiên cứu tiếp theo để hoàn thiện.
2.1. Hạn Chế Của Thuật Toán Truyền Thống Với Luật Hiếm
Các thuật toán khai phá luật kết hợp truyền thống, như Apriori, thường được tối ưu hóa để tìm các luật có độ hỗ trợ và độ tin cậy cao. Khi áp dụng cho việc tìm kiếm luật kết hợp hiếm, những thuật toán này trở nên kém hiệu quả do phải hạ thấp ngưỡng hỗ trợ tối thiểu (minSup) xuống rất thấp. Điều này dẫn đến việc tạo ra một lượng lớn các tập mục phổ biến, phần lớn trong số đó không liên quan đến các luật hiếm mà chúng ta quan tâm. Kết quả là, chi phí tính toán tăng lên đáng kể, làm cho quá trình khai phá trở nên chậm chạp và tốn kém.
2.2. Khó Khăn Về Không Gian Nhớ Và Dư Thừa Luật
Một vấn đề lớn khác khi khai thác luật kết hợp hiếm là yêu cầu về không gian nhớ. Việc phải lưu trữ tất cả các tập mục không phổ biến, đặc biệt là khi ngưỡng hỗ trợ tối thiểu rất thấp, có thể tiêu tốn một lượng lớn bộ nhớ. Thêm vào đó, việc tạo ra các luật từ các tập hiếm này thường dẫn đến sự dư thừa, với nhiều luật có ý nghĩa tương tự hoặc không có giá trị thực tế. Điều này làm phức tạp thêm quá trình phân tích và đòi hỏi các phương pháp lọc và đánh giá luật hiệu quả.
III. Phương Pháp Phát Hiện Luật Kết Hợp Hiếm Trong Hệ Thống
Các thuật toán phát hiện luật kết hợp hiếm đã ra đời để giải quyết những thách thức trên. Một hướng tiếp cận là sử dụng ràng buộc phần hệ quả của luật. Phương pháp này đưa ra danh sách các mục dữ liệu sẽ xuất hiện trong một phần của luật và được sử dụng làm điều kiện khi sinh luật. Tuy nhiên, cách tiếp cận này chỉ hiệu quả khi biết trước thông tin về các mục dữ liệu, chẳng hạn phải xác định trước được mục dữ liệu nào sẽ xuất hiện trong phần hệ quả của luật. Hướng nghiên cứu này vẫn còn nhiều hạn chế. Do phải sinh ra tất cả các tập không phổ biến nên chi phí cho không gian nhớ rất cao, và xảy ra tình trạng dư thừa nhiều luật kết hợp được sinh ra từ các tập hiếm tìm được.
3.1. Sử Dụng Ràng Buộc Phần Hệ Quả Của Luật
Phương pháp này tập trung vào việc xác định trước các mục dữ liệu cụ thể mà chúng ta quan tâm trong phần hệ quả (consequent) của luật kết hợp. Bằng cách đặt ra các ràng buộc về sự xuất hiện của các mục này, chúng ta có thể giới hạn không gian tìm kiếm và tập trung vào các luật có liên quan đến các mục tiêu đã định. Ví dụ, nếu chúng ta quan tâm đến việc tìm các yếu tố dự đoán nguy cơ mắc một bệnh hiếm gặp, chúng ta có thể đặt ràng buộc rằng bệnh đó phải xuất hiện trong phần hệ quả của luật.
3.2. Tập Trung Vào Các Mục Dữ Liệu Không Phổ Biến
Một cách tiếp cận khác là tập trung trực tiếp vào việc tìm kiếm các tập mục không phổ biến (infrequent itemsets), tức là các tập mục có độ hỗ trợ thấp hơn một ngưỡng nhất định. Tuy nhiên, như đã đề cập ở trên, việc tìm kiếm tất cả các tập mục không phổ biến có thể rất tốn kém về mặt tính toán và bộ nhớ. Do đó, các thuật toán theo hướng này thường sử dụng các kỹ thuật tối ưu hóa như tỉa nhánh (pruning) và các cấu trúc dữ liệu hiệu quả để giảm thiểu chi phí.
IV. Ứng Dụng Thực Tiễn Luật Kết Hợp Hiếm Trong Hệ Thống
Luật kết hợp hiếm có nhiều ứng dụng thực tiễn quan trọng. Trong lĩnh vực y tế, nó có thể giúp phát hiện các tác dụng phụ hiếm gặp của thuốc hoặc các yếu tố nguy cơ dẫn đến các bệnh hiếm gặp. Trong lĩnh vực tài chính, nó có thể giúp phát hiện các giao dịch gian lận hoặc các hành vi bất thường. Trong lĩnh vực an ninh mạng, nó có thể giúp phát hiện các cuộc tấn công mạng hoặc các hành vi xâm nhập hệ thống. Việc khai thác và phân tích luật kết hợp hiếm có thể mang lại những thông tin quan trọng, giúp các tổ chức đưa ra các quyết định chính xác và kịp thời.
4.1. Phát Hiện Tác Dụng Phụ Hiếm Gặp Của Thuốc
Trong lĩnh vực y tế, việc sử dụng luật kết hợp hiếm có thể giúp phát hiện các tác dụng phụ hiếm gặp của thuốc mà có thể không được phát hiện trong các thử nghiệm lâm sàng thông thường do số lượng người tham gia hạn chế. Bằng cách phân tích dữ liệu từ hồ sơ bệnh án điện tử, chúng ta có thể tìm ra các mối liên hệ giữa việc sử dụng một loại thuốc cụ thể và sự xuất hiện của một triệu chứng hoặc bệnh lý hiếm gặp. Điều này có thể giúp các nhà quản lý y tế và bác sĩ đưa ra cảnh báo và hướng dẫn sử dụng thuốc an toàn hơn.
4.2. Phát Hiện Giao Dịch Gian Lận Trong Tài Chính
Trong lĩnh vực tài chính, luật kết hợp hiếm có thể được sử dụng để phát hiện các giao dịch gian lận hoặc các hành vi bất thường trong các hệ thống thanh toán và giao dịch chứng khoán. Ví dụ, một giao dịch có giá trị lớn bất thường hoặc một chuỗi các giao dịch nhỏ được thực hiện từ các địa điểm khác nhau có thể là dấu hiệu của gian lận. Bằng cách phân tích các mẫu giao dịch hiếm gặp, các tổ chức tài chính có thể phát hiện và ngăn chặn các hành vi gian lận một cách hiệu quả hơn.
V. Nghiên Cứu Giải Pháp Tìm Tập Hiếm Trên CSDL Tác Vụ
Luận án tập trung vào việc xác định một số dạng luật kết hợp hiếm Sporadic trên cả CSDL tác vụ và CSDL định lượng, đồng thời phát triển các thuật toán phát hiện các tập dữ liệu hiếm tương ứng cho các dạng luật hiếm này. Đối với bài toán phát hiện luật kết hợp hiếm trên CSDL tác vụ, luận án theo hướng tiếp cận đi tìm các tập không phổ biến đóng cho các luật kết hợp hiếm thay vì việc đi tìm tất cả các tập không phổ biến như các nghiên cứu về luật hiếm trước đây. Tập các tập không phổ biến đóng là nhỏ hơn tập các tập không phổ biến. Vì vậy, việc chỉ phải tìm tập hiếm đóng không những hạn chế được chi phí mà còn hạn chế được các luật hiếm dư thừa.
5.1. Tiếp Cận Dựa Trên Không Gian Tập Dữ Liệu Hiếm Đóng
Luận án đề xuất một phương pháp mới để phát hiện luật kết hợp hiếm trên CSDL tác vụ bằng cách tập trung vào không gian các tập dữ liệu hiếm đóng (closed infrequent itemsets). Thay vì tìm kiếm tất cả các tập không phổ biến, phương pháp này chỉ tìm các tập hiếm đóng, giúp giảm thiểu chi phí tính toán và loại bỏ các luật dư thừa. Cơ sở của phương pháp này dựa trên tính chất rằng 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, và các luật kết hợp hiếm được sinh ra từ các tập hiếm và từ các tập hiếm cực đại là như nhau.
5.2. Phát Triển Thuật Toán MCPSI MCISI Và NC CHARM
Luận án phát triển ba thuật toán mới để tìm các tập mục hiếm cho ba dạng luật kết hợp hiếm trên CSDL tác vụ: 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, 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, và thuật toán NC-CHARM (Negative Constraints - CHARM) phát hiện tập dữ liệu với ràng buộc mục âm. Cả ba thuật toán này đều được phát triển theo hướng bổ sung và phát triển các giải pháp cho phát hiện luật kết hợp Sporadic dựa theo cách tiếp cận và ý tưởng của thuật toán CHARM.
VI. Giải Pháp Phát Hiện Luật Kết Hợp Hiếm Trên CSDL Định Lượng
Luận án sử dụng lý thuyết tập mờ trong vấn đề phát hiện luật kết hợp hiếm trên CSDL định lượng. Việc ứng dụng tập mờ sẽ giúp biểu diễn luật kết hợp hiếm tự nhiên hơn, gần gũi hơn với người sử dụng và nhất là khắc phục được vấn đề “điểm biên gãy” trong phân khoảng các thuộc tính định lượng. Luận án đã phát triển hai thuật toán tìm tập hiếm cho hai dạng luật này. Thuật toán MFPSI (Mining Fuzzy Perfectly Sporadic Ite...).
6.1. Sử Dụng Lý Thuyết Tập Mờ Để Xử Lý Dữ Liệu Định Lượng
Để giải quyết vấn đề phát hiện luật kết hợp hiếm trên CSDL định lượng, luận án tiếp cận bằng cách sử dụng lý thuyết tập mờ (fuzzy set theory). Thay vì xử lý các giá trị định lượng một cách cứng nhắc, lý thuyết tập mờ cho phép chúng ta biểu diễn chúng dưới dạng các tập mờ, với các mức độ thuộc về khác nhau. Điều này giúp giảm thiểu ảnh hưởng của các điểm biên gãy (sharp boundaries) và cho phép chúng ta khai thác các luật một cách tự nhiên và linh hoạt hơn.
6.2. Thuật Toán MFPSI Và MFISI Cho Luật Sporadic Mờ
Luận án đề xuất hai thuật toán mới, MFPSI (Mining Fuzzy Perfectly Sporadic Itemsets) và MFISI (Mining Fuzzy Imperfectly Sporadic Itemsets), để phát hiện các luật kết hợp hiếm Sporadic trên CSDL định lượng sử dụng lý thuyết tập mờ. Các thuật toán này được thiết kế để tìm kiếm các tập mục mà độ hỗ trợ của chúng thay đổi đáng kể giữa các phân khoảng mờ khác nhau, cho phép chúng ta phát hiện các mối quan hệ hiếm gặp nhưng có ý nghĩa.
VII. Ứng Dụng Phân Tích Dự Báo Kinh Tế Với Luật Kết Hợp Hiếm
Luận án đề cập đến việc ứng dụng luật kết hợp cùng với mô hình hồi quy chuyển tiếp trơn để xây dựng mô hình phân tích và dự báo kinh tế. Việc ứng dụng các kỹ thuật khai phá luật kết hợp giúp xây dựng mô hình phân tích và dự báo kinh tế.
7.1. Phân Tích Dự Báo Kinh Tế
Các kỹ thuật khai phá luật kết hợp có thể giúp khám phá các mối quan hệ tiềm ẩn giữa các chỉ số kinh tế khác nhau, từ đó cung cấp thông tin đầu vào cho các mô hình dự báo. Bằng cách xác định các yếu tố có ảnh hưởng lớn đến sự thay đổi của một chỉ số kinh tế quan trọng, chúng ta có thể xây dựng các mô hình dự báo chính xác hơn.
7.2. Mô Hình Hồi Quy
Một mô hình hồi quy chuyển tiếp trơn (STR) cho phép mô hình hóa các mối quan hệ phi tuyến tính và sự thay đổi cấu trúc trong dữ liệu kinh tế. Việc kết hợp các luật kết hợp hiếm với mô hình STR có thể giúp chúng ta phát hiện các yếu tố hiếm gặp nhưng có ảnh hưởng lớn đến sự thay đổi của các chỉ số kinh tế, từ đó cải thiện khả năng dự báo.
