Nghiên Cứu Phát Hiện Luật Kết Hợp Hiếm Và Ứng Dụng Trong Công Nghệ Thông Tin

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.

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ể.

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.

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ả.

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.

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í.

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.

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.

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.

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.

Để 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.

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.

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.

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.