Khai phá luật kết hợp trong cơ sở dữ liệu (Association rule in data mining) là gì?

Khai phá luật kết hợp trong cơ sở dữ liệu

Khái niệm

Khai phá luật kết hợp trong cơ sở dữ liệu trong tiếng Anh gọi là: Association rule in data mining.

Khai phá luật kết hợp (KPLKH) là một kĩ thuật quan trọng của khai phá dữ liệu. Mục tiêu nhằm phát hiện mối quan hệ giữa các mục dữ liệu trong cơ sở dữ liệu.

Mô hình đầu tiên của bài toán KPLKH là mô hình nhị phân (hay còn gọi là mô hình cơ bản) được R. Agrawal, T. Imielinski và A. Swami đề xuất vào năm 1993, xuất phát từ nhu cầu phân tích dữ liệu của cơ sở dữ liệu giao tác, phát hiện các mối quan hệ giữa các tập mục hàng hóa (Itemsets) đã bán được tại các siêu thị.

Việc xác định các quan hệ này không phân biệt vai trò khác nhau cũng như không dựa vào các đặc tính dữ liệu vốn có của các mục dữ liệu mà chỉ dựa vào sự xuất hiện cùng lúc của chúng.

Bài toán khai phá luật kết hợp

Bài toán KPLKH có thể phát biểu như sau: Cho cơ sở dữ liệu giao tác DB, ngưỡng độ hỗ trợ tối thiểu minsup và ngưỡng độ tin cậy tối thiểu minconf.

Yêu cầu: Tìm tất cả các luật kết hợp X→Y trên cơ sở dữ liệu DB sao cho sup(X→Y) > minsup và conf (X→Y) > minconf.

KPLKH này được gọi là bài toán cơ bản hay bài toán nhị phân, vì ở đây, giá trị của mục dữ liệu trong cơ sở dữ liệu là 0 hoặc 1 (xuất hiện hay không xuất hiện).

Bài toán KPLKH trong cơ sở dữ liệu chia thành hai bài toán con:

(1) Tìm tất cả các tập mục thường xuyên: Một tập mục là thường xuyên được xác định qua tính độ hỗ trợ và thoả mãn độ hỗ trợ cực tiểu.

(2) Sinh ra các luật kết hợp từ các tập mục thường xuyên đã tìm được thỏa mãn độ tin cậy tối thiểu cho trước.

Khi KPLKH trong cơ sở dữ liệu DB thì mọi khó khăn nằm ở bài toán thứ nhất là tìm tập mục thường xuyên.

Thuật ngữ Khai phá dữ liệu ra đời vào cuối những năm 80 thế kỷ trước. Có nhiều định nghĩa khác nhau về khai phá dữ liệu, nhưng diễn đạt một cách dễ hiểu thì khai phá dữ liệu là quá trình tìm kiếm những thông tin (tri thức) có ích, tiềm ẩn và mang tính dự đoán trong các khối cơ sở dữ liệu lớn.

(Tài liệu tham khảo: Tổng quan về khai phá dữ liệu và phương pháp khai phá luật kết hợp trong cơ sở dữ liệu, Nguyễn Thị Việt Hà, Tạp chí Công thương, 2020)