연관 규칙을 위한 Apriori 알고리즘

Apriori 알고리즘의 주요 아이디어는 사물 데이터 세트에 존재하는 최대 빈발 항목 세트를 찾은 다음, 획득된 최대 빈발 항목 세트와 미리 설정된 최소 신뢰 임계값을 사용하여 강력한 항목을 생성하는 것입니다. 협회 규칙.

항목 세트는 항목 모음입니다. k개의 항목을 포함하는 항목 집합을 k-항목 집합이라고 합니다. 항목 집합의 발생 빈도는 해당 항목 집합을 포함하는 모든 거래의 개수로, 절대 지지 개수 또는 지지 개수라고도 합니다. 항목 집합 I의 상대적 지지도가 사전 정의된 최소 지지 임계값을 충족하면 I는 빈발 항목 집합입니다. 빈번한 k 항목 집합은 일반적으로 k로 표시됩니다.

항목 집합 A와 B가 동시에 발생할 확률을 연관 규칙의 지지(상대 지지라고도 함)라고 합니다.

항목 세트 A가 발생하면 항목 세트 B가 발생할 확률이 연관 규칙의 신뢰도입니다.

최소 지원은 지원을 측정하기 위해 사용자 또는 전문가가 정의한 임계값으로, 항목 세트의 가장 낮은 통계적 중요도를 나타냅니다. 최소 신뢰도는 사용자 또는 전문가가 신뢰도를 측정하기 위해 정의한 임계값입니다. 협회 규칙의. 최소 지원 임계값과 최소 신뢰 임계값을 모두 충족하는 규칙을 강력한 규칙이라고 합니다.

아이템 세트 A의 지원 횟수는 아이템 세트 A가 포함된 거래 데이터 세트의 거래 횟수로, 이를 아이템 세트의 빈도 또는 횟수라고 합니다.

빈발 항목 집합의 비어 있지 않은 모든 항목도 빈발 항목 집합이어야 합니다. 이 속성에 따르면, 트랜잭션 A가 빈발항목집합 I이 아닌 항목집합에 추가된다면, 새로운 항목집합 IUA 역시 빈발항목집합이 아니어야 한다는 결론을 내릴 수 있다.

1) 빈발항목집합을 모두 찾는다(지지도는 D에 부여된 최소 지지도보다 크거나 같아야 함). 이 과정에서 연결단계와 가지치기 단계가 병합되고 최종적으로 최대 빈발 항목 집합을 얻습니다.

연결 단계의 목적은 주어진 최소 지원 임계값에 대해 1개 항목 후보 집합 C1에 대해 임계값보다 작은 항목 집합을 제거하여 다음으로 1개 항목 빈발 항목 집합 L1을 찾는 것입니다. 한 단계에서는 L1 자체를 연결하여 2항목 후보집합 C2를 생성하고, 제약조건을 만족하는 C2의 항목집합을 그대로 유지하여 2항목 빈발집합을 구하고 다음 단계에서 L2로 기록하며, L2와 L3을 연결하여 3개의 항목 후보 집합 C3을 생성하고, 제약 조건을 만족하는 C2의 항목 집합은 그대로 유지되며, 제약 조건의 항목 집합은 3개의 빈발 항목 집합을 얻어 L3으로 기록되는데… 최대 빈발 항목 집합 Lk를 얻을 때까지 계속됩니다.

가지치기 단계는 연결 단계에 이어 후보 항목 Ck를 생성하는 과정에서 검색 공간을 줄이는 목적으로 사용됩니다. Ck는 Lk-1과 L1을 연결하여 생성되므로 빈발항목집합의 비어있지 않은 부분집합도 Apriori의 속성에 따라 빈발항목집합이어야 하므로 이 속성을 만족하지 않는 항목집합은 Ck에 존재하지 않게 된다. . 나뭇가지.

2) 빈발항목 집합으로부터 강한 연관 규칙 생성: 과정 1)에서, 나머지 규칙이 미리 정해진 최소 지원 임계값을 초과하지 않는 항목 집합이 제안되었음을 알 수 있다. 최소 신뢰도 임계값 이후 강력한 연관 규칙이 마이닝됩니다.