Apriori는 1994년에 R. Agrawal과 R. Srikant가 개발한 중요한 알고리즘으로 부울 연관 규칙에 대한 빈번한 항목 집합을 생성합니다. 알고리즘은 알고리즘이 빈번한 항목 집합 속성에 대한 사전 지식이 필요한 경우에 따라 다릅니다.
Apriori는 k-항목 집합이 (k+1)-항목 집합을 탐색할 수 있는 수준별 검색이라는 반복적인 방법을 사용합니다. 먼저, 데이터베이스를 탐색하여 각 항목의 개수를 수집하고 최소 지원을 충족하는 항목을 수신하여 빈번한 1-itemset 집합을 검색합니다. 결과 집합은 L1로 표시됩니다. .
다음으로 L1 L2를 찾을 수 있습니다. , L3을 찾을 수 있는 빈번한 2개 항목 집합의 집합 , 등등, 더 이상 빈번한 k-itemsets를 발견할 수 없을 때까지. 각 Lk의 결과 데이터베이스 전체를 한 번 스캔해야 했습니다.
Apriori 속성으로 알려진 필수 속성인 빈번한 항목 집합의 수준별 생성 효율성을 높일 수 있습니다. 검색 공간을 줄일 수 있습니다.
선험적 속성 − 빈번한 항목 집합의 비어 있지 않은 일부 하위 집합도 자주 있어야 합니다.
Apriori 속성은 다음 관찰에 따라 다릅니다. 설명에 따르면 항목 집합 I이 최소 지원 임계값인 min sup를 충족하지 않으면 I가 자주 발생하지 않습니다. 즉, P(I)
항목 A가 항목 집합 I에 삽입되면 결과 항목 집합(즉, I ∪ A)이 I보다 규칙적으로 나타날 수 없습니다. 따라서 I∪A는 P(I ∪ A)
이 속성은 집합이 테스트를 변경할 수 없는 경우 일부 상위 집합도 유사한 테스트를 거부한다는 의미에서 안티모노톤으로 알려진 속성 요소에 속합니다. 속성이 테스트를 거부하는 맥락에서 단조롭기 때문에 안티모노톤으로 알려져 있습니다.
다음과 같은 조인 및 정리 작업을 포함하여 2단계 프로세스를 따릅니다. -
가입 단계 − Lk를 찾을 수 있습니다. , 후보 k-itemset의 집합은 Lk를 결합하여 생성됩니다. -1 자신과 함께. 이 후보 집합은 Ck로 표시됩니다. . L1 및 L2 Lk의 항목 집합이 됩니다. -1. 문서 Li [j]는 Li의 j번째 항목을 정의합니다. (예:L1 [k−2]는 L1의 마지막 항목에서 두 번째 항목을 정의합니다. ).
정리 단계 - Ck Lk의 상위 집합입니다. 즉, 그 구성원은 빈번할 수 없지만 일부 빈번한 k-itemset은 Ck에 포함됩니다. . Ck의 모든 후보자 수를 결정하기 위한 데이터베이스 스캔 Lk를 결정할 수 있습니다. (즉, 최소 지원 수 이상의 수를 가진 일부 후보자는 설명에 의해 빈번하므로 Lk에 속합니다. ). Ck 클 수 있으며 큰 계산을 포함할 수 있습니다.