Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Khai thác quy tắc liên kết đa cấp từ database giao dịch

Các phương pháp khai thác quy tắc liên kết đa cấp dựa trên khung hỗ trợ-độ tin cậy (support-confidence framework). Chiến lược từ trên xuống (top-down) được dùng nơi đếm được tích lũy để tính tập mục thường xuyên ở mỗi mức khái niệm, bắt đầu từ mức khái niệm 1 và tiến về mức khái niệm cụ thể thấp hơn cho đến khi không tìm thấy thêm tập mục thường xuyên dùng thuật toán Apriori.

Dữ liệu có thể khái quát hóa bằng cách thay thế khái niệm cấp thấp trong dữ liệu bằng khái niệm cấp cao hơn hoặc tổ tiên từ phân cấp khái niệm. Trong phân cấp khái niệm, được biểu diễn như cây với gốc là D tức là Dữ liệu liên quan đến nhiệm vụ (Task-relevant data).

Lĩnh vực ứng dụng phổ biến cho liên kết đa cấp là phân tích giỏ hàng, nghiên cứu thói quen mua sắm bằng cách tìm tập mặt hàng thường xuyên mua cùng nhau, hiển thị trong khái niệm phân cấp khái niệm.

Mỗi nút chỉ ra mục hoặc tập mục đã được kiểm tra. Có nhiều phương pháp tìm tập mục thường xuyên ở bất kỳ mức trừu tượng nào. Một số phương pháp dùng: 'sử dụng hỗ trợ tối thiểu đồng nhất cho tất cả mức', 'sử dụng hỗ trợ tối thiểu giảm ở mức thấp', 'độc lập từng mức'.

Database đa cấp cần bảng giao dịch mã hóa phân cấp thay vì bảng giao dịch ban đầu. Hữu ích khi chỉ quan tâm một phần database giao dịch như đồ ăn, thay vì tất cả mặt hàng. Cách này thu thập tập dữ liệu liên quan trước rồi lặp lại trên tập liên quan. Trong bảng giao dịch, mỗi mục được mã hóa như chuỗi chữ số.

Sử dụng hỗ trợ tối thiểu đồng nhất cho tất cả mức – Khi dùng ngưỡng hỗ trợ tối thiểu đồng nhất, thủ tục tìm kiếm đơn giản hóa. Kỹ thuật tối ưu hóa có thể áp dụng, dựa trên kiến thức tổ tiên là siêu tập của hậu duệ, tìm kiếm tránh kiểm tra tập mục chứa mục nào mà tổ tiên không có hỗ trợ tối thiểu.

Nhược điểm chính của phương pháp hỗ trợ đồng nhất: mục ở mức trừu tượng thấp sẽ xuất hiện thường xuyên như những mục ở mức trừu tượng cao.

Sử dụng hỗ trợ tối thiểu giảm ở mức thấp – Mỗi mức trừu tượng có ngưỡng hỗ trợ tối thiểu riêng. Cấp trừu tượng càng thấp, ngưỡng tương đương càng nhỏ. Các loại tìm kiếm khai thác liên kết đa cấp với hỗ trợ giảm:

  • Độc lập từng mức (Level by level independent) – Tìm kiếm chiều rộng đầy đủ, kiến thức nền về tập mục thường xuyên dùng cho cắt tỉa. Mỗi nút được kiểm tra bất kể nút cha có thường xuyên không.
  • Lọc chéo theo đơn mục (Level cross-filtering by single item) – Mục ở mức i được xác định nếu và chỉ nếu nút cha ở mức (i-1) thường xuyên.
  • Lọc chéo theo k-tập mục (Level cross-filtering by k-itemset) – Tập mục ở mức i được xác định nếu và chỉ nếu tập mục cha tương đương ở mức (i-1) thường xuyên.