association rule mining
data mining
Pattern minig
Basic Concepts
- pattern: dataset 안에서 함께 자주 발생하는 subsequences, substructures, set of items
- 이 pattern은 인과관계를 의미하진 않는다.
- Association rule minig: 최소 지지도나 신뢰도를 넘는 모든 항목에 대해 pattern을 찾는다.
Applications
- association rule, correlation, classification, clustering data mining의 기반이 될 수 있다.
- 장바구니 분석
- 연속 구매 분석
Terminologies
- 지지도(Support): 전체 거래 중 특정 항목 집합이 포함된 거래의 비율.
- 신뢰도(Confidence): 항목 X를 포함하는 거래 중에서 항목 Y도 함께 포함하는 거래의 비율.
- 빈발 패턴(frequent): 최소 지지도를 넘는 pattern
- 빈발 항목 집합(frequent itemset): 단순한 묶음
- 빈발 시퀀스
closed pattern
- x가 빈발이고, 지지도가 상위 집합들과 다른 집합 (지지도는 상위로 갈 수록 떨어짐)
- 지지도 정보를 유지할 수 있다.
- 신뢰도 계산할 때 사용할 수 있음
max patterns
- x가 빈발이고, 상위 집합들 모두가 빈발 집합이 아닌 집합
- 지지도 정보는 유지되지 않음.
- 신뢰도 계산할 때 사용할 수 없어서 사실 상 결과 요약 외의 용도는 없음
- Downward closure property: 어떤 itemset이 빈발하지 않으면, 그 모든 superset은 무조건 빈발하지 않는다. 대우도 성립
- 교수님은 anti-monotone property로 설명하셨지만 이게 더 자주 사용되는 용어
Association Rule
- find frequent itemsets
- Apriori (breadth-first search)
- FP-Growth
- Eclat (depth-first search)
- generate association rules
- 모든 빈발 itemset I에 대해 모든 I의 subset s로 ‘s -> (I - s)’ 규칙을 생성
- 최소 신뢰도 조건을 만족하는 규칙만 남김
Algorithm
Apirori
- Monotone 성질을 이용하여 빈발하지 않는 집합은 후보에서 제거
- scan DB once to get 1-itemsets
- 반복
- k개의 itemset에 대해 k+1-itemset의 후보를 생성
- self-join: k-itemset을 두 개 합쳐서 k+1-itemset을 생성
- prune: k+1-itemset을 생성할 때, k-itemset의 subset이 모두 빈발해야 k+1-itemset이 빈발할 수 있다.
- k+1-itemset 후보에 대해 DB를 scan하여 빈발한 itemset을 찾는다.
- k += 1
- 빈발 itemset이 없으면 종료
- k개의 itemset에 대해 k+1-itemset의 후보를 생성
- Apriori의 단점: DB scan을 여러 번 해야함, 후보가 많아질 수 있음
- 후보 수를 줄이는 방법: Hashing
DHP (Direct Hashing and Pruning)
Hash값이 같은 itemset의 count를 합하고, minimum support를 넘는 itemset만 남김
Hash table을 매번 만드는 번거로움이 있지만, apriori보다 빠름
반복
- 빈발 항목 찾기, 후보 해시 테이블 생성
- 데이터베이스를 scan하여 최소 지지도를 넘는 1-itemset 후보를 찾음
- 동시에 조합 가능한 2-itemset을 만들어 mapping된 해시 테이블 bucket에 count += 1
- 가지치기
- 1-itemset 후보를 이용해 self-join, prune으로 2-itemset 후보 생성
- 완성된 후보를 1단계에서 만든 hash table에 매핑해서 최소 지지도를 넘는 2-itemset bucket이 아닐 경우 배제
- 빈발 항목 찾기, 후보 해시 테이블 생성