세 방법은 같은 자료에서 같은 빈발 패턴을 찾는다. 다른 것은 지지도를 세는 방법과, 그 대가로 무엇을 많이 쓰느냐다. 고르는 질문은 둘이다. DB를 여러 번 훑을 여유가 있는가? 메모리에 무엇을 들고 있을 수 있는가?
어느 쪽일까
C1 (a) 거래 수억 건이 디스크에 있어 한 번 훑는 데 몇 시간 걸리고, 가장 긴 빈발 집합은 8개 항목쯤이다. (b) 거래 수천 건이 메모리에 다 들어가고, 구현을 하루 안에 끝내야 한다. Apriori와 FP-Growth 중 무엇이 알맞은가?
답: (a) FP-Growth. DB를 두 번만 훑는다. Apriori는 약 8번 훑어야 한다. (b) Apriori. 결합과 가지치기만으로 짧게 구현할 수 있고, 자료가 작아 여러 번 훑어도 부담이 없다.
C2 항목 수는 적지만(수십 개) 거래가 아주 많고, 항목마다 든 거래 번호를 비트열로 메모리에 둘 수 있다. 어느 방법이 잘 맞는가? 같은 자료에서 흔한 항목이 거의 모든 거래에 들어 있다면 무엇이 문제인가?
답: ECLAT. 비트열의 AND로 교집합을 빠르게 구하고 DB는 한 번만 읽는다. 다만 흔한 항목의 TID 목록은 거래 수만큼 길어 교집합 하나에도 시간과 메모리가 많이 든다.
C3 다음 설명은 어느 방법인가? ① 크기를 한 단계씩 늘리며 너비 우선으로 찾는다 ② 항목 → 거래 번호 표를 만든다 ③ 거래를 빈도순으로 정렬해 앞부분을 공유하는 트리로 압축한다 ④ 후보를 만들지 않는다
답: ① Apriori ② ECLAT ③ FP-Growth ④ FP-Growth. ECLAT은 깊이 우선이지만 교집합할 후보 짝은 만든다.
결정적 차이
세 방법을 나란히 놓으면 이렇다.
| Apriori | ECLAT | FP-Growth | |
|---|---|---|---|
| 데이터 형식 | 수평 (거래 목록) | 수직 (TID 목록) | 압축 (FP-tree, 조건부 트리) |
| DB 훑기 | 많다 (가장 긴 빈발 집합 크기만큼) | 1번 (TID 목록 만들 때) | 2번 |
| 후보 생성 | 한다 | 한다 | 하지 않는다 |
| 지지도 세는 법 | DB를 훑어 센다 | TID 목록의 교집합 | FP-tree에서 패턴을 키운다 |
| 탐색 순서 | 너비 우선 (크기별) | 깊이 우선 | 깊이 우선 |
| 메모리 | 많음 ~ 아주 많음 | 많음 ~ 아주 많음 | 적음 (FP-tree만) |
| 핵심 생각 | 아프리오리 성질로 후보 가지치기 | 교집합으로 지지도 | 앞부분 트리로 후보 생성 피하기 |
선택을 가르는 것은 “DB 훑기”와 “메모리” 두 줄이다. 디스크 읽기가 비싸면 Apriori가 빠지고, 메모리가 빠듯하면 ECLAT이 빠진다.
검증: 같은 자료(거래 9개, min_sup 2)에서 세 구현의 결과가 같고, 각각 무작위 자료 300개에서 모든 부분집합을 세는 방법과 같다 — 13_apriori_impl.py, 14_eclat_impl.py, 15_fp-growth_impl.py
셋 다 아닐 때
C4 세 방법 모두 결과가 너무 많아 쓸 수 없는 상황과, 그때의 선택지를 쓰라.
답: 최소 지지도를 낮추거나 거래가 길면 빈발 패턴이 수백만 개로 늘어난다. 이때는 모든 빈발 패턴 대신 닫힌 패턴이나 최대 패턴만 찾거나, 지지도·신뢰도 대신 리프트와 널 불변 측정으로 흥미로운 것만 고른다.