IBM의 Apriori는 불가능한 후보를 가지치기하여 함께 구매되는 품목을 마이닝했다

소매업체들은 어떤 제품이 함께 구매되는지 알고 싶어 했지만, 가능한 항목 조합의 수는 SKU 수에 따라 기하급수적으로 폭발했다.

1994년에 발표된 Apriori는 한 가지 성질을 활용한다. 즉, 비빈발 항목집합의 모든 상위집합은 그 자체로 비빈발이어야 한다. 이는 단일 항목을 세고, 빈발한 항목을 유지하고, 이를 쌍으로 확장하고, 반복한다. 따라서 부모가 이미 실패한 후보는 절대 세지 않는다.

이 기법은 빠르게 감당하기 어려워지는 탐색을 빈발 집합의 작은 경계만 건드리는 탐색으로 바꾼다. 이는 장바구니 분석을 실용적인 데이터베이스 질의로 만들었다.

어떤 집합이 희귀하다면, 그 집합의 모든 상위집합도 희귀하다

하향 폐쇄성은 탐색이 커지기 전에 가지치기하므로, 실행 시간은 모든 집합이 아니라 빈발 집합에 비례한다.

레벨마다 한 번의 데이터베이스 스캔은 메모리를 후보 집합으로 제한한다.

이는 휴리스틱이나 샘플링 근사가 아닌 정확한 빈발 집합을 제공한다.

동일한 가지치기는 장바구니를 넘어 시퀀스 및 패턴 마이닝으로 일반화된다.

거대한 공간을 탐색하기 전에, 전체 가지를 한 번에 버릴 수 있게 해주는 단조 성질을 찾아라. 어떤 영역을 배제하는 규칙은 탐색을 지수적에서 선형으로 줄인다.

Apriori는 표준적인 연관 규칙 알고리즘이자 데이터 마이닝의 표준 교재 내용이 되었다. 이는 추천, 상품 구성 및 교차 판매 분석을 뒷받침하는 분야의 씨앗이 되었으며, 이후에는 그 스캔을 줄이는 fpgrowth 및 다른 방법들의 씨앗이 되었다.