어두운 지도를 조금씩 밝혀나가는 데에서 즐거움을 느낀다면
- Frequent Pattern (빈발 패턴) : 데이터 셋에서 자주 발생하는 패턴
ex) itemset, subsequence(부분순차), substructure (부분 구조)....
- 93년 Agrawal, Imielinski, Swami가 frequent itemset과 association rule mining (연관 관계 마이닝)으로 처음 제시
- 목적 : 데이터에 내재되어있는 규칙성의 발견
- ex)
- 적용 : 장바구니 분석, 크로스마케팅, 카탈로그 디자인, 판매 캠페인 분석, 웹로그 분석, DNA 시퀀스 분석...
- Frequent Pattern : 데이터셋의 본질적이고 중요한 성질
- 다양한 중요 데이터 마이닝 작업의 기초로 작용
- itemset (항목 집합) : 하나 이상의 항목의 집합 I = {I1, I2, ... , Im}
- k - itemset : k개의 항목으로 이루어진 집합 X = {X1, X2, ... , Xk}
- 항목집합 X의 absolute support (절대적 지지도, support count) : X가 발생한 트랜잭션의 수
- 항목집합 X의 relative support (상대적 지지도) : 전체 트랜젝션에서 X가 발생한 트랜잭션의 비율
( == 트랜젝션이 X를 포함할 확률)
- 항목집합 X의 상대적 지지도가 사전에 정의한 최소 지지도 임계갑 (min_sup)을 만족한다면 X를 Frequent하다고 한다
- 연관 규칙 : X → Y (s, c)
- 항목집합 X가 발생하면 Y도 발생한다는 연관 규칙
- support (지지도, s) : 트랜잭션이 X와 Y를 모두 포함할 확률
- confidence (신뢰도, c) : X를 포함하는 트랜잭션이 Y도 포함할 조건부 확률
- 최소 지지도 임계값 (min_sup)과 최소 신뢰도 임계값 (min_conf)를 모두 만족하는 규칙을 강한 규칙이라 함
- Apriori 알고리즘 : 후보 생성 및 검사 접근법
- Improving the Efficiency of Apriori : Apriori 알고리즘을 활용하여 효율을 개선한 접근법
- FPGrowth (FP 성장, Frequent Pattern Growth) Approach
- ECLAT (Equivanlence Class Transformation) : 수직 데이터 형태를 이용한 Frequent Itemset Mining
- ex) basket data에서 itemset {beer, diaper, milk}가 frequent하다면 부분집합 {diaper, milk}도 frequent
-> Apriori 알고리즘은 이 명제의 대우를 사용 (한 명제가 참이면 그 명제의 대우 역시 참이다.)
- Apriori pruning principle (가지치기 원리)
: 어떤 itemset이 frequent하지 않다면 그 itemset의 초집합 역시 frequent하지 않다.
ex) {diaper, milk}가 frequent하지 않다면 초집합인 {beer, diaper, milk) 역시 frequent하지 않다
-> frequent하지 않은 itemset의 초집합은 frequent itemset 후보로 생성하지 않는다.
- 먼저, 데이터 베이스를 스캔하여 frequent한 1-itemset (항목이 하나인 itemset)을 얻어내고 다음을 반복
- frequent한 k-itemset으로 부터 후보가 될 (k+1)-itemset을 얻어낸다
- 데이터베이스를 이용해 후보를 검사한다 (후보가 min_sup과 min_conf를 만족하는지 검사한다)
- 더이상 frequent한 itemset이나 후보 itemset을 생성할 수 없다면 반복을 종료한다.
- 위의 Transaction data에서 min_sup = 0.2, min_conf = 0.7이 주어졌을 때 Apriori 알고리즘을 이용한 frequent itemset과 association rule의 탐색
1-1. 먼저 후보 1-itemset C1 생성
1-2. C1에서 min_sup을 만족하는 frequent 1-itemset L1 생성 (min_sup = 0.2 ≒ 2/9)
2-1. L1을 self-join 하여 후보 2-itemset C2 생성
2-2 C2에서 min_sup을 만족하는 frequent 2-itemset L2 생성 (min_sup = 0.2 ≒ 2/9)
-> {I1, I4}, {I3, I4}, {I3, I5}, {I4, I5}는 frequent하지 않음
3-1. L2을 self-join 하여 후보 3-itemset C3 생성
-> {I1, I4}, {I3, I4}, {I3, I5}, {I4, I5}를 포함하는 itemset은 apriori pruning priciple에 의해 생성하지 않음
3-2 C3에서 min_sup을 만족하는 frequent 3-itemset L3 생성 (min_sup = 0.2 ≒ 2/9)
이후 C4는 생성할 수 없으므로 반복 종료 : {I1, I2, I3, I5}만이 만들어지는데 이는 prune의 대상이 됨
4. 만들어진 frequent itemset에서 association rule을 만들어내고 min_conf = 0.7를 만족하는지 검사
- {I1, I2, I3}
-> min_conf를 만족하는 rule : X
- {I1, I2, I5}
-> min_conf를 만족하는 rule : I5 -> {I1, I2} / {I1, I5} -> I2 / {I2, I5} -> I1
- Pattern Mining을 통해 도출된 모든 강한 규칙이 관심대상인 것은 아님
-> interestingness measure를 통한 패턴 평가가 필요함
- lift : 두 itemset의 종속성, 상관관계를 파악하기 위한 지표
- lift < 1 : 두 itemset 사이에 음의 상관관계가 존재 -> 한 사건이 발생하면 다른 사건은 발생하지 않음
- lift = 1 : 두 itemset은 서로 독립, 두 사건 사이에는 상관관계가 존재하지 않음
- lift > 1 : 두 itemset 사이에 양의 상관관계가 존재
- lift, chi-square(X^2)가 상관관계 분석에 주로 사용
- 이외에도 20개가 넘는 interestingness measure가 존재 -> 상황에 따라 사용
Frequent Pattern Analysis
1. Frequent Pattern Analysis (빈팔 패턴 분석)
1) Frequent Pattern Analysis이란 무엇인가
- Frequent Pattern (빈발 패턴) : 데이터 셋에서 자주 발생하는 패턴
ex) itemset, subsequence(부분순차), substructure (부분 구조)....
- 93년 Agrawal, Imielinski, Swami가 frequent itemset과 association rule mining (연관 관계 마이닝)으로 처음 제시
- 목적 : 데이터에 내재되어있는 규칙성의 발견
- ex)
- 적용 : 장바구니 분석, 크로스마케팅, 카탈로그 디자인, 판매 캠페인 분석, 웹로그 분석, DNA 시퀀스 분석...
2) Frequent Pattern Mining의 중요성
- Frequent Pattern : 데이터셋의 본질적이고 중요한 성질
- 다양한 중요 데이터 마이닝 작업의 기초로 작용
2. Frequent Pattern Analysis의 기본 개념
1) Frequent Pattern
- itemset (항목 집합) : 하나 이상의 항목의 집합 I = {I1, I2, ... , Im}
- k - itemset : k개의 항목으로 이루어진 집합 X = {X1, X2, ... , Xk}
- 항목집합 X의 absolute support (절대적 지지도, support count) : X가 발생한 트랜잭션의 수
- 항목집합 X의 relative support (상대적 지지도) : 전체 트랜젝션에서 X가 발생한 트랜잭션의 비율
( == 트랜젝션이 X를 포함할 확률)
- 항목집합 X의 상대적 지지도가 사전에 정의한 최소 지지도 임계갑 (min_sup)을 만족한다면 X를 Frequent하다고 한다
2) Association Rule (연관 규칙)
- 연관 규칙 : X → Y (s, c)
- 항목집합 X가 발생하면 Y도 발생한다는 연관 규칙
- support (지지도, s) : 트랜잭션이 X와 Y를 모두 포함할 확률
- confidence (신뢰도, c) : X를 포함하는 트랜잭션이 Y도 포함할 조건부 확률
- 최소 지지도 임계값 (min_sup)과 최소 신뢰도 임계값 (min_conf)를 모두 만족하는 규칙을 강한 규칙이라 함
3. Frequent Itemset Mining (빈발 항목집합 마이닝) 방법
- Apriori 알고리즘 : 후보 생성 및 검사 접근법
- Improving the Efficiency of Apriori : Apriori 알고리즘을 활용하여 효율을 개선한 접근법
- FPGrowth (FP 성장, Frequent Pattern Growth) Approach
- ECLAT (Equivanlence Class Transformation) : 수직 데이터 형태를 이용한 Frequent Itemset Mining
4. Apriori 알고리즘
1) 원리 : frequent한 itemset의 모든 (공백이 아닌) 부분집합은 frequent하다.
- ex) basket data에서 itemset {beer, diaper, milk}가 frequent하다면 부분집합 {diaper, milk}도 frequent
-> Apriori 알고리즘은 이 명제의 대우를 사용 (한 명제가 참이면 그 명제의 대우 역시 참이다.)
- Apriori pruning principle (가지치기 원리)
: 어떤 itemset이 frequent하지 않다면 그 itemset의 초집합 역시 frequent하지 않다.
ex) {diaper, milk}가 frequent하지 않다면 초집합인 {beer, diaper, milk) 역시 frequent하지 않다
-> frequent하지 않은 itemset의 초집합은 frequent itemset 후보로 생성하지 않는다.
2) 방법
- 먼저, 데이터 베이스를 스캔하여 frequent한 1-itemset (항목이 하나인 itemset)을 얻어내고 다음을 반복
- frequent한 k-itemset으로 부터 후보가 될 (k+1)-itemset을 얻어낸다
- 데이터베이스를 이용해 후보를 검사한다 (후보가 min_sup과 min_conf를 만족하는지 검사한다)
- 더이상 frequent한 itemset이나 후보 itemset을 생성할 수 없다면 반복을 종료한다.
3) 예시
- 위의 Transaction data에서 min_sup = 0.2, min_conf = 0.7이 주어졌을 때 Apriori 알고리즘을 이용한 frequent itemset과 association rule의 탐색
1-1. 먼저 후보 1-itemset C1 생성
1-2. C1에서 min_sup을 만족하는 frequent 1-itemset L1 생성 (min_sup = 0.2 ≒ 2/9)
2-1. L1을 self-join 하여 후보 2-itemset C2 생성
2-2 C2에서 min_sup을 만족하는 frequent 2-itemset L2 생성 (min_sup = 0.2 ≒ 2/9)
-> {I1, I4}, {I3, I4}, {I3, I5}, {I4, I5}는 frequent하지 않음
I1, I41I3, I40I3, I51I4, I503-1. L2을 self-join 하여 후보 3-itemset C3 생성
-> {I1, I4}, {I3, I4}, {I3, I5}, {I4, I5}를 포함하는 itemset은 apriori pruning priciple에 의해 생성하지 않음
I1, I2, I4 (PRUNED)I1, I3, I4(PRUNED)I1, I3, I5(PRUNED)I1, I4, I5(PRUNED)I2, I3, I4(PRUNED)I2, I3, I5(PRUNED)I2, I4, I5(PRUNED)I3, I4, I5(PRUNED)3-2 C3에서 min_sup을 만족하는 frequent 3-itemset L3 생성 (min_sup = 0.2 ≒ 2/9)
이후 C4는 생성할 수 없으므로 반복 종료 : {I1, I2, I3, I5}만이 만들어지는데 이는 prune의 대상이 됨
4. 만들어진 frequent itemset에서 association rule을 만들어내고 min_conf = 0.7를 만족하는지 검사
- {I1, I2, I3}
-> min_conf를 만족하는 rule : X
- {I1, I2, I5}
-> min_conf를 만족하는 rule : I5 -> {I1, I2} / {I1, I5} -> I2 / {I2, I5} -> I1
5. Pattern Evaluation Methods (패턴 평가 방법)
- Pattern Mining을 통해 도출된 모든 강한 규칙이 관심대상인 것은 아님
-> interestingness measure를 통한 패턴 평가가 필요함
1) Correlation (lift)
- lift : 두 itemset의 종속성, 상관관계를 파악하기 위한 지표
- lift < 1 : 두 itemset 사이에 음의 상관관계가 존재 -> 한 사건이 발생하면 다른 사건은 발생하지 않음
- lift = 1 : 두 itemset은 서로 독립, 두 사건 사이에는 상관관계가 존재하지 않음
- lift > 1 : 두 itemset 사이에 양의 상관관계가 존재
- lift, chi-square(X^2)가 상관관계 분석에 주로 사용
- 이외에도 20개가 넘는 interestingness measure가 존재 -> 상황에 따라 사용
'전공 과목 공부 > 데이터 사이언스' 카테고리의 다른 글