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

Các kỹ thuật khai thác mẫu âm (Negative Patterns) là gì?

Lớp đầu tiên của các kỹ thuật được tạo ra cho khai thác mẫu không thường xuyên (infrequent patterns) xem xét mỗi mặt hàng như một biến nhị phân đối xứng (symmetric binary variable). Thông tin giao dịch (transaction data) có thể được nhị phân hóa (binarized) bằng cách mở rộng (augmenting) nó với các mặt hàng âm (negative items). Nó hiển thị một ví dụ của việc thay đổi dữ liệu ban đầu thành giao dịch có cả mặt hàng dương tính (positive) và âm tính (negative). Bằng cách sử dụng thuật toán tạo tập mục thường xuyên hiện có bao gồm Apriori trên các giao dịch mở rộng, một số tập mục âm (negative itemsets) có thể được suy ra.

Cách tiếp cận như vậy chỉ có thể nếu một số biến được coi là nhị phân đối xứng (tức là, nó tìm kiếm mẫu âm chứa sự phủ định của chỉ một số lượng nhỏ mặt hàng). Nếu mỗi mặt hàng nên được coi là nhị phân đối xứng, vấn đề trở nên khó khăn về mặt tính toán vì các lý do sau.

Số lượng mặt hàng gấp đôi khi mỗi mặt hàng được mở rộng với mặt hàng âm tương ứng của nó. Thay vì khám phá lưới tập mục kích thước 2ᵈ, nơi d là số mặt hàng trong tập dữ liệu ban đầu, lưới trở nên lớn hơn.

Cắt tỉa dựa trên hỗ trợ (Support-based pruning) không còn hiệu quả khi các mặt hàng âm được mở rộng. Đối với mọi biến x, hoặc x hoặc x' có hỗ trợ lớn hơn hoặc bằng 50%. Do đó, ngay cả khi ngưỡng hỗ trợ lớn như 50%, một nửa mặt hàng sẽ thường xuyên.

Đối với ngưỡng thấp hơn, một số mặt hàng và có thể tập mục bao gồm chúng sẽ thường xuyên. Các phương pháp cắt tỉa dựa trên hỗ trợ được thuê bởi Apriori chỉ hiệu quả khi hỗ trợ cho hầu hết tập mục thấp; do đó, các tập mục thường xuyên khác nhau tăng theo cấp số mũ.

Chiều rộng của mỗi giao dịch cải thiện khi các mặt hàng âm được mở rộng. Xét rằng có d mặt hàng có sẵn trong tập dữ liệu ban đầu. Đối với tập dữ liệu thưa (sparse data sets) bao gồm giao dịch giỏ hàng thị trường, chiều rộng mỗi giao dịch xu hướng nhỏ hơn nhiều so với d.

Theo đó, kích thước tối đa của tập mục thường xuyên, bị giới hạn bởi chiều rộng giao dịch tối đa w_max, xu hướng tương đối nhỏ. Khi các mặt hàng âm được chứa, chiều rộng giao dịch tăng lên d vì một mặt hàng hiện diện trong giao dịch hoặc vắng mặt từ giao dịch, nhưng không phải cả hai.

Vì chiều rộng giao dịch tối đa đã tăng từ w_max lên d, điều này sẽ làm tăng nhanh chóng số lượng tập mục thường xuyên đa dạng. Theo đó, một số thuật toán hiện tại xu hướng bị phá vỡ (break down) khi chúng được dùng cho tập dữ liệu dài.

Cách tiếp cận brute-force trước đó tốn kém tính toán vì nó ép chúng ta phải quyết định hỗ trợ cho một số lượng lớn mẫu dương tính và âm tính. Thay vì mở rộng tập dữ liệu với mặt hàng âm, một cách tiếp cận khác là quyết định hỗ trợ của các tập mục âm tùy thuộc trên hỗ trợ của các mặt hàng dương tương ứng của chúng.