데이터 마 이 닝(7):Apriori 알고리즘:빈번 한 패턴 발굴

1 알고리즘 사상
알고리즘 은 빈번 한 항목 집합 성질 의 선험 지식 을 사용한다.Apriori 는 한 층 한 층 검색 이 라 고 불 리 는 교체 방법 을 사용 합 니 다.k 항목 집합 은 탐색(k+1)항목 집합 에 사 용 됩 니 다.우선 데이터 베 이 스 를 스 캔 하여 각 항목 의 수 를 누적 하고 최소 지원 도 를 만족 시 키 는 항목 을 수집 하여 빈번 한 1 개의 집합 을 찾 아 낸다.이 집합 은 L1 로 기록 되 어 있 으 며,L1 은 빈번 한 2 항 집합 인 L2 를 찾 는 데 사용 되 며,L2 는 빈번 한 k 항 집합 을 다시 찾 을 수 없 을 때 까지 L3 를 찾 는 데 사용 된다.모든 Lk 를 찾 으 려 면 데이터베이스 전체 스 캔 이 필요 합 니 다.
Apriori 특성 은 검색 공간 을 압축 하여 빈번 한 항목 집합 이 발생 하 는 효율 을 높 일 수 있 습 니 다.
Apriori 성질:빈번 한 항목 집합의 모든 비공 식 서브 집합 도 빈번 해 야 한다.
Apriori 알고리즘 은 주로 연결 스텝 과 가지치기 스텝 두 단계 로 구성 된다.연결 단계 와 가지치기 단계 에서 Apriori 성질 을 사용 하면 알고리즘 의 효율 을 높 일 수 있다.
1.1 연결 단계
이 단 계 는 빈번 한 k-1 항 집합 에서 후보 k 항 집합 을 만 드 는 데 사용 된다.
Lk 를 계산 하기 위해 서 는 Apriori 성질 에 따라 Lk-1 에서 연결 가능 한 모든 연결 에 대해 후보 k 항목 집합 을 만 드 는 집합 을 선택 하여 Ck 로 기록 해 야 합 니 다.항목 이 집 중 된 항목 을 사전 순서에 따라 정렬 한다 고 가정 하면 연결 할 수 있 는 쌍 은 두 개의 빈번 한 항목 집합 이 마지막 항목 만 다르다 는 것 을 말한다.예 를 들 어 Lk-1 의 요소 인 l1 과 l2 가 연결 이 가능 하 다 면 l1 과 l2 두 항목 의 k-1 항목 중 마지막 항목 만 다 르 고 이 조건 은 중복 되 지 않도록 하 는 데 만 사 용 됩 니 다.
1.2 가지치기 걸음
이 단 계 는 Ck 에 포 함 된 항목 집합 수 를 빠르게 줄 이 는 데 사 용 됩 니 다.
Apriori 성격 으로 얻 을 수 있 습 니 다.빈번 하지 않 은(k-1)항목 집합 은 빈번 한 k 항목 집합의 부분 집합 이 아 닙 니 다.따라서 Ck 의 한 후보 k 항목 집합의 임의의(k-1)항목 집합 이 Lk-1 에 없 으 면 이 후보 k 항목 집합 은 빈번 하지 않 기 때문에 Ck 에서 삭제 할 수 있 습 니 다.이 부분 집합 테스트 는 현재 모든 빈번 한 항목 집합 을 사용 하 는 해시 트 리 를 사용 하여 빠르게 완성 할 수 있 습 니 다.
Ck 는 Lk 의 초 집합 으로,부분 집합 테스트 를 거 쳐 Ck 를 압축 한 후 데이터 베 이 스 를 스 캔 하여 Ck 의 각 후보 수 를 확정 하여 Lk 를 확정 할 수 있다.
2 의사 코드
 

  ：Apriori，                     

  ：

    D：     ；

    min_sup：         。

  ：  L：D      。

  ：

1)  L1 = find_frequent_1_itemsets(D);

2)  for (k = 2; Lk-1 ≠ ∅; k++) {

3)    Ck = aproiri_gen(Lk-1,min_sup);

4)    for each transaction t∈D{ //  D    

5)      Ct = subset(Ck,t); //    t        k  ，

6)      for each candidate c∈Ct //   t       k       

7)        c.count++;

8)  }

9)    Lk={c∈Ck | c.count ≥ min_sup}

10) }

11) return L = ∪kLk；

procedure apriori_gen(Lk-1: frequent (k-1)-itemset; min_sup: support)

1) for each itemset l1∈Lk-1

2)   for each itemset l2∈Lk-1

3)     if (l1[1]=l2[1])∧...∧(l1[k-2]=l2[k-2])∧(l1[k-1]<l2[k-2]) then {

4)       c = l1    l2; //   :   candidates

5)       if has_infrequent_subset(c,Lk-1) then

6)         delete c; //    :       cadidate

7)       else add c to Ck;

8) }

9) return Ck;

procedure has_infrequent_subset(c:candidate k-itemset; Lk-1:frequent (k-1)-itemset)

//       

1) for each (k-1)-subset s of c

2)   if c∉Lk-1 then

3)     return TRUE;

4) return FALSE;

이 가운데 Lk-1 은 빈번 한 k-1 항 집 을 나타 낸다.
 
3 실현
예시
참고 자료:
(제2판)