Post

데이터베이스 마이닝

Posted
By Jaebaek Lee
15 min read
데이터베이스 마이닝

Association Rule Mining

DB에 감춰진 관계들을 발견

  • 예시 상황
    transaction set이 주어졌을 때, transaction에서 item occurence를 이용해 다른 item occurrence 정보를 예측하는 rule 찾는 것이 목적

market basket transaction

TIDItems
1Bread, Milk
2Bread, Diaper, Beer, Egg
3Milk, Diaper, Beer, Coke
4Bread, Milk, Diaper, Beer
5Bread, Milk, Diaper, Coke
  • Association Rule의 예
    • {Diaper} → {Beer}
    • {Bread, Milk} → {Diaper}
    • {Milk} → {Coke}
    • {Beer} → {Diaper, Bread}

co-occurrence일뿐, causality는 아님

Itemset

  • itemset: $X$
    • 한개 이상의 아이템들의 집합
    • e.g. {Bread, Diaper, Beer}
    • k-itemset: k개의 item 갖고있는 itemset
  • support count: $\sigma(X)$
    • itemset $X$의 출현 횟수
    • e.g. $\sigma({Bread, Milk, Diaper}) = 2$
  • support: $s(X)$
    • itemset $X$가 transaction에서 나타나는 비율
      • $s(X) = \frac{\sigma(X)}{T}$
      • e.g. $s({Bread, Milk}) = \frac{3}{5} = 0.6$
  • frequent itemset
    • support가 $minsup$ threshold 이상인 itemset

Association Rule

  • association rule: $X \rightarrow Y$
    • $X$와 $Y$는 disjoint한 itemset
    • e.g. ${Bread, Milk} \rightarrow {Diaper}$
  • confidence: $c(X \rightarrow Y)$
    • rule의 신뢰도 : $X$를 포함하는 transaction에서 $Y$의 등장빈도의 비율
      • $c(X \rightarrow Y) = \frac{\sigma(X \cup Y)}{\sigma(X)}$
      • e.g. $c({Bread, Milk} \rightarrow {Diaper}) = \frac{2}{3} = 0.67$
  • support: $s(X \rightarrow Y)$
    • rule의 support : 전체 transaction에서 $X$와 $Y$가 함께 나타나는 비율
      • $s(X \rightarrow Y) = \frac{\sigma(X \cup Y)}{T}$
      • e.g. $s({Bread, Milk} \rightarrow {Diaper}) = \frac{2}{5} = 0.4$

  • transaction set $T$가 주어졌을때, 다음 두 조건을 만족하는 모든 Rule을 찾는게 Rule mining의 목적:

    1. Support: $s(X \rightarrow Y) \geq minsup$
      • Rule의 support가 최소 support threshold 이상이어야 함.
    2. Confidence: $c(X \rightarrow Y) \geq minconf$
      • Rule의 confidence가 최소 confidence threshold 이상이어야 함.
  • brute-force로 전부 찾으면 계산량 과부하

Apriori Algorithm

  • Rule의 예시 (support, confidence)
    • ${Milk, Diaper} \rightarrow {Beer}$ (0.4, 0.67)
    • ${Milk, Beer} \rightarrow {Diaper}$ (0.4, 1.0)
    • ${Diaper, Beer} \rightarrow {Milk}$ (0.4, 0.67)
    • ${Beer} \rightarrow {Milk, Diaper}$ (0.4, 0.67)
    • ${Diaper} \rightarrow {Milk, Beer}$ (0.4, 0.5)
    • ${Milk} \rightarrow {Diaper, Beer}$ (0.4, 0.5)
  • 관찰
    • 위 모든 rule은 {Milk, Diaper, Beer}의 이진분할
    • 따라서 같은 support, 다른 confidence 가짐
    • support와 confidence를 따로 접근
  • 두 단계 접근
    • $support \geq minsup$을 만족하는 itemset 생성
    • 각 frequent itemset에 대해 $minconf$ 이상의 confidence 갖는 rule 생성
      • 여기서 rule은 freq itemset의 이진분할
    • 여전히 계산량은 많음
    • $I$개의 item이 있을떄, $2^I$개의 가능한 itemset 존재

Frequent Itemset Generation

  • Brute-force
    • $2^I$개의 itemset에 대해 $T$를 스캔하며 각 itemset의 support를 계산
    • time complexity: $O(TMw)$
      • $M = 2^I$이므로 복잡도 매우 높음
    • 가능한 association rule(이진분할 개수):
      $R = 3^I-2^{I+1}+1$
  • 가능한 전략
    • $M$(number of candidate) 줄이기
      • pruning
    • $TM$(number of comparison) 줄이기
      • 각 candidate itemset의 support를 구하기 위해 $T$를 스캔해야함
      • 비교 횟수를 줄이기 위해 candidate들을 hash구조에
    • $T$(number of transaction) 줄이기
      • itemset 크기 k가 증가함에 따라 고려 대상이 되는 $T$ 줄이기
  • Apriori Principle
    • 어떤 frequent itemset의 subset도 frequent
    • 즉, $X$가 infrequent하면 $X$의 superset도 infrequent
    • pruning에 활용 가능
    • 예제:
      • 예제:

        • transaction set:
          | TID | Items |
          |—–|———————|
          | 1 | Bread, Milk |
          | 2 | Bread, Diaper, Beer |
          | 3 | Milk, Diaper, Beer |
          | 4 | Bread, Milk, Diaper |
          | 5 | Bread, Milk, Beer |

        • $minsup = 0.6$일 때,
          1. 1-itemset의 support 계산:
            • ${Bread}: 4/5 = 0.8$
            • ${Milk}: 4/5 = 0.8$
            • ${Diaper}: 3/5 = 0.6$
            • ${Beer}: 3/5 = 0.6$
          2. frequent 1-itemset: ${Bread}, {Milk}, {Diaper}, {Beer}$
          3. 2-itemset 생성 및 support 계산:
            • ${Bread, Milk}: 3/5 = 0.6$
            • ${Bread, Diaper}: 2/5 = 0.4$
            • ${Bread, Beer}: 2/5 = 0.4$
            • ${Milk, Diaper}: 2/5 = 0.4$
            • ${Milk, Beer}: 2/5 = 0.4$
            • ${Diaper, Beer}: 2/5 = 0.4$
          4. frequent 2-itemset: ${Bread, Milk}$
          5. 3-itemset 생성 불가 (frequent 2-itemset 부족)
        • 결과: frequent itemset = ${Bread}, {Milk}, {Diaper}, {Beer}, {Bread, Milk}$

  • Apriori Algorithm

    1. Initialization
      • 모든 1-itemset의 support를 계산하여 frequent 1-itemset을 찾음.
    2. Iterative Candidate Generation and Pruning
      • $k$-itemset을 기반으로 $(k+1)$-itemset을 생성.
      • Apriori Principle을 활용하여 infrequent한 candidate를 pruning.
      • pruning된 candidate의 support를 계산하여 frequent $(k+1)$-itemset을 찾음.
      • frequent $(k+1)$-itemset이 없을 때까지 반복.
    3. Rule Generation
      • frequent itemset으로부터 association rule을 생성.
      • 각 rule의 confidence를 계산하여 $minconf$를 만족하는 rule만 선택.
  • Candidate Generation
    • $k$-itemset을 기반으로 $(k+1)$-itemset 생성
    • $k$-itemset 중 frequent한 것들만 사용
    • pruning을 통해 candidate 수를 줄임
  • Support Counting
    • candidate itemset의 support를 계산
    • transaction을 스캔하며 candidate와 매칭
  • Pruning
    • infrequent한 itemset 제거
    • Apriori Principle을 활용하여 pruning

Rule Generation

  • frequent itemset $Y$에 대해 $Y$를 두개의 non empty subset $X$와 $Y-X$로 분리해 association rule 생성하고, $minconf$ 만족하는지 검사
  • $Y=k$일때, $2^k-2$개의 candidate rule 존재
  • 특징:
    • $X \rightarrow Y - X$의 confidence: $\frac{\sigma(Y)}{\sigma(X)}$
    • $Y$가 frequent itemset이므로, $X$도 frequent itemset
      (freq itemset generation 과정 거쳤으므로)
  • 예시:
    • frequent itemset: ${Bread, Milk, Diaper}$
      • 가능한 rule:
        • ${Bread, Milk} \rightarrow {Diaper}$
          • $c = \frac{\sigma({Bread, Milk, Diaper})}{\sigma({Bread, Milk})} = \frac{2}{3} = 0.67$
        • ${Bread, Diaper} \rightarrow {Milk}$
          • $c = \frac{\sigma({Bread, Milk, Diaper})}{\sigma({Bread, Diaper})} = \frac{2}{2} = 1.0$
        • ${Milk, Diaper} \rightarrow {Bread}$
          • $c = \frac{\sigma({Bread, Milk, Diaper})}{\sigma({Milk, Diaper})} = \frac{2}{2} = 1.0$
        • ${Bread} \rightarrow {Milk, Diaper}$
          • $c = \frac{\sigma({Bread, Milk, Diaper})}{\sigma({Bread})} = \frac{2}{4} = 0.5$
        • ${Milk} \rightarrow {Bread, Diaper}$
          • $c = \frac{\sigma({Bread, Milk, Diaper})}{\sigma({Milk})} = \frac{2}{4} = 0.5$
        • ${Diaper} \rightarrow {Bread, Milk}$
          • $c = \frac{\sigma({Bread, Milk, Diaper})}{\sigma({Diaper})} = \frac{2}{3} = 0.67$
      • $minconf = 0.6$일 때, 선택된 rule:
        • ${Bread, Milk} \rightarrow {Diaper}$
        • ${Bread, Diaper} \rightarrow {Milk}$
        • ${Milk, Diaper} \rightarrow {Bread}$
        • ${Diaper} \rightarrow {Bread, Milk}$
Confidence Measure의 특징
  • 2개의 rules $X \rightarrow Y, \quad \tilde{X}\rightarrow\tilde{Y}$ 가정
    • $\tilde{X} \subseteq X, \quad \tilde{Y}\subseteq Y$ 여도 confidence가 누가 더 큰지 알 수 없음
      • anti-monotone 성질 없음
  • 그러나, 같은 frequent itemset $Y$로부터 생성된 rule들은 anti-monotone 성질 가짐
    • 즉, $\tilde{X} \subseteq X$에 대해, $\tilde{X} \rightarrow Y - \tilde{X}$는 절대 $X \rightarrow Y$를 넘을 수 없음
      • confidence의 분모는 작거나 같고, 분자는 크거나 같다
      • rhs의 item 수에 대해 anti-monotone

  • 따라서 low confidence rule $W \rightarrow Y-W$에 대해, $W$의 부분집합이 lhs인 경우 모두 pruning

  • Rule generation algoritm
    1. Initialization
      • 모든 frequent itemset $Y$를 대상으로 rule generation을 시작.
    2. Recursive Rule Generation
      • $Y$를 두 개의 non-empty subset $X$와 $Y-X$로 분리하여 candidate rule $X \rightarrow Y-X$ 생성.
      • $X \rightarrow Y-X$의 confidence 계산:
        $c(X \rightarrow Y-X) = \frac{\sigma(Y)}{\sigma(X)}$
      • $c(X \rightarrow Y-X) \geq minconf$를 만족하지 않으면 pruning.
    3. Pruning
      • anti-monotone 성질을 활용하여 low confidence rule을 pruning.
        • $X \rightarrow Y-X$가 $minconf$를 만족하지 않으면, $X$의 subset이 lhs인 rule도 pruning.
    4. Iterative Refinement
      • pruning된 rule을 기반으로 subset을 줄여가며 새로운 rule 생성.
      • 모든 가능한 rule이 생성되거나 pruning이 완료될 때까지 반복.

Association pattern의 평가

  • 알고리즘이 너무 많고 중복되는 rule을 도출하는 경향이 있음
    • butter → bread는 뻔함, diaper → beer는 흥미로움
  • Interesting measure를 pattern 평가에 사용

Interesting measure

  • rule $X \rightarrow Y$가 주어졌을 때, 다음의 contingency 테이블로부터 interesting measure 계산
 $Y$$\bar Y$Total
$X$$f(X \cap Y)$$f(X \cap \bar Y)$$f(X)$
$\bar X$$f(\bar X \cap Y)$$f(\bar X \cap \bar Y)$$f(\bar X)$
Total$f(Y)$$f(\bar Y)$$|T|$

  • Confidence의 한계

     $Coffee$$\widehat{Coffee}$Total
    $Tea$15520
    $\widehat{Tea}$75580
    Total9010100
    • rule: $Tea \rightarrow Coffeee$
    • confidence: $P(CoffeeTea) = 0.75$
    • 하지만, $P(Coffee)=0.9$
    • Confidence는 높으나, 오해의 소지가 있음
      • $P(Coffee\widehat{Tea}) = 0.9375$
  • Lift
    • rule의 confidence와 rule consequent에 해당하는 itemset의 support와 ratio
      • X가 발생했을때 Y도 발생할 확률이, Y가 발생할 확률보다 얼마나 높나?
    • 정의:
      \(\text{Lift}(X \rightarrow Y) = \frac{P(Y|X)}{P(Y)} = \frac{P(X \cap Y)}{P(X) \cdot P(Y)} = \frac{c(X \rightarrow Y)}{P(Y)}\)
    • 해석:
      • $\text{Lift} > 1$: $X$와 $Y$는 양의 상관관계.
      • $\text{Lift} = 1$: $X$와 $Y$는 독립적.
      • $\text{Lift} < 1$: $X$와 $Y$는 음의 상관관계.
    • 예시:
      • 위의 예시에서, $P(Coffee|Tea) = 0.75$, $P(Coffee)=0.9$이므로
        $\text{Lift}(Tea \rightarrow Coffee) = \frac{0.75}{0.9}$

  • Lift의 한계

     $Y$$\bar Y$Total
    $X$88050930
    $\bar X$502070
    Total930701000
    • $P(Y)=0.93$, $P(YX)=0.95$, $L(X,Y) \approx 1$
     $W$$\bar W$Total
    $Z$2050930
    $\bar Z$5088070
    Total930701000
    • $P(W)=0.07$, $P(WZ)=0.29$, $L(Z,W) \approx 4$
    • $L(X,Y)=\frac{f_{XY}f_{\bar{X}\bar{Y}}}{f_{\bar{X}Y}f_{\bar{X}Y}}$이므로, highly imbalanced인 경우에는 confidence 계열 measure 사용해 비교하는것이 바람직

Nearest Neighbor

  • Classifier의 종류
    • eager learner: 모델이 training data를 미리 학습
    • lazy learner: 입력이 들어와야 training data 사용
      • Rote classifier
        training data에 test instance와 같은 instance가 있을 때만 classification 수행
      • Nearest Neighbor
        분류를 위해 k개의 가장 가까운 데이터포인트 사용

k-Nearest Neighbor (k-NN)

  • 정의
    • k-NN은 lazy learning 알고리즘으로, 새로운 데이터 포인트를 분류하기 위해 가장 가까운 k개의 이웃을 참조
      • 이를 위해 라벨된 record 필요
    • 거리 기반으로 분류를 수행하며, 일반적으로 유클리드 거리(Euclidean Distance)를 사용
  • 알고리즘
    1. Initialization
      • k값을 설정
    2. Distance Calculation
      • 새로운 데이터 포인트와 모든 training 데이터 포인트 간의 거리를 계산
    3. Neighbor Selection
      • 계산된 거리 중 가장 가까운 k개의 이웃을 선택
    4. Majority Voting
      • 선택된 이웃의 클래스 중 가장 많이 등장하는 클래스를 새로운 데이터 포인트의 클래스로 할당

  • 유클리드 거리 공식
    \(d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}\)

  • 특징
    • 간단하고 구현이 쉬움.
    • 비선형 데이터에도 효과적.
    • 계산 비용이 높음 (특히 데이터가 많을 때).
    • k값과 거리 측정 방법에 따라 성능이 민감하게 변함.
      • k값이 너무 작으면 노이즈에 민감.
      • k값이 너무 크면 경계가 흐려짐.
      • 일반적으로 홀수로 설정하여 동률을 방지.
    • scaling 이슈
      • 하나의 특성이 다른 특성보다 domain이 크다면, 해당 특성이 전체 거리를 dominate할 수 있음

PEBLS

  • PEBLS (Parallel Exemplar-Based Learning System)
    • PEBLS는 k-NN 알고리즘의 변형으로, 주로 명목형(nominal) 데이터에 사용됨.
    • 각 데이터 포인트의 거리를 계산하기 위해 명목형 속성에 적합한 distance metric을 사용.
  • 특징
    • 명목형 데이터에 적합한 distance metric 제공.
    • 데이터의 noise와 missing value에 대해 더 강건함.
    • 일반적인 k-NN보다 더 효율적.
  • 알고리즘
    1. Distance Metric 정의
      • 명목형 속성에 대해 distance를 정의.(MVDM)
    2. Instance Weighting
      • 각 데이터 포인트에 가중치를 부여하여 중요도를 반영.
    3. Classification
      • k-NN과 유사하게 가장 가까운 이웃을 기반으로 분류 수행.
  • Modified Value Difference Metric (MVDM)
    • MVDM은 명목형 데이터의 속성 간 거리를 계산하기 위한 방법.
    • 각 속성 값의 분포를 기반으로 거리를 정의.

    • 두 값 $v_i$와 $v_j$의 MVDM은 다음과 같이 계산:
      \(\text{d}(v_i, v_j) = \sum_{c \in C} \left| P(c|v_i) - P(c|v_j) \right|\)
      여기서 $C$는 클래스 집합, $P(c|v)$는 값 $v$가 클래스 $c$에 속할 확률.

    • 예시
      • 속성 값 $v_1$과 $v_2$가 주어졌을 때, 클래스 $C = {A, B}$에 대해:
        • $P(Av_1) = 0.6$, $P(Bv_1) = 0.4$
        • $P(Av_2) = 0.3$, $P(Bv_2) = 0.7$
        • $\text{d}(v_1, v_2) =0.6 - 0.3+0.4 - 0.7= 0.6$
  • 가중치 계산
    • $X$와 $Y$간 가중치 거리는 다음과 같이 계산됨
      $\Delta(X, Y) = w_X w_Y \sum_{i=1}^{n} d(x_i, y_i)$
      여기서 $W_X = \frac{num.\ of\ times\ X\ is\ used\ for\ pred.}{num.\ of\ times\ X\ predicts\ correctly}$

해당 포스트는 서울대학교 산업공학과 박종헌 교수님의 데이터관리와 분석 25-1학기 강의를 정리한 내용입니다.

데이터베이스
데이터베이스 DB 강의정리
This post is licensed under CC BY 4.0 by the author.