Apriori là một thuật toán tinh được phát triển bởi R. Agrawal và R. Srikant vào năm 1994 để phá hủy các tập phổ biến cho các quy tắc kết hợp Boolean. Thuật toán phụ thuộc vào trường hợp mà thuật toán cần có kiến thức trước đó về các thuộc tính của tập phổ biến.
Apriori sử dụng một phương pháp lặp lại được gọi là tìm kiếm theo cấp độ, trong đó k-itemets có thể khám phá (k + 1) -itemsets. Đầu tiên, tập hợp các tập 1 mục thường xuyên được phát hiện bằng cách duyệt cơ sở dữ liệu để tập hợp số lượng cho từng mục và nhận những mục đáp ứng hỗ trợ tối thiểu. Tập hợp kết quả được chỉ ra L 1 .
Tiếp theo, L 1 có thể tìm thấy L 2 , tập hợp các tập 2 mục thường xuyên, có thể tìm thấy L 3 , v.v., cho đến khi không thể phát hiện ra tập k-item thường xuyên hơn nữa. Kết quả của mỗi L k cần một lần quét hoàn chỉnh cơ sở dữ liệu.
Nó có thể làm tăng hiệu quả của việc tạo các tập phổ biến thường xuyên theo cấp độ khôn ngoan, một thuộc tính thiết yếu được gọi là thuộc tính Apriori. Nó có thể làm giảm không gian tìm kiếm.
Thuộc tính Apriori - Một số tập hợp con khác nhau của một tập phổ biến cũng nên thường xuyên.
Thuộc tính Apriori phụ thuộc vào quan sát sau đây. Theo mô tả, nếu một tập hợp vật phẩm I không thỏa mãn ngưỡng hỗ trợ tối thiểu, tối thiểu sup, thì tôi không thường xuyên; nghĩa là P (I)
Nếu một mục A được chèn vào tập hợp mục I, do đó tập hợp mục kết quả (tức là tôi ∪ A) không thể xuất hiện thường xuyên hơn I. Do đó, I∪A không thường xuyên, chẳng hạn như P (I ∪ A)
Thuộc tính này thuộc về một phần tử của các thuộc tính được gọi là antimonotone theo nghĩa là nếu một tập hợp không thể thay đổi một thử nghiệm, thì một số tập hợp siêu cấp cũng sẽ từ chối thử nghiệm tương tự. Nó được gọi là antimonotone vì thuộc tính là monotonic trong bối cảnh từ chối một bài kiểm tra.
Có quy trình hai bước được tuân theo, bao gồm các hành động nối và cắt tỉa như sau -
Bước tham gia - Nó có thể tìm thấy L k , một tập hợp k-itemets ứng viên được tạo ra bằng cách tham gia L k −1 với chính nó. Tập hợp các ứng cử viên này được chỉ ra C k . Hãy để L 1 và L 2 là các tập hợp vật phẩm trong L k −1. Tài liệu L i [j] xác định mục thứ j trong L i (ví dụ:L 1 [k − 2] xác định mục thứ hai đến mục cuối cùng trong L 1 ).
Bước cắt tỉa - C k là một tập hợp siêu của L k , tức là các thành viên của nó không thể thường xuyên, nhưng một số k-itemets thường xuyên có liên quan đến C k . Quét cơ sở dữ liệu để quyết định số lượng của mọi ứng cử viên trong C k có thể dẫn đến việc xác định L k (tức là, một số ứng cử viên có số lượng không ít hơn số lượng hỗ trợ tối thiểu là thường xuyên theo mô tả và do đó thuộc về L k ). C k có thể lớn và nó có thể bao gồm tính toán lớn.