5. 데이터 마이닝 - Classification (1)

1. Rule-Based Classifier

 1. 'if....then...' 즉 (Condition) -> y라고 생각하면 된다.

    ▪ Condition 부분을 LHS라고 부른다.

    ▪ Consequent 부분을 RHS라고 부른다.

    ▪ ex) (Blood Type=Warm) ∩ (Lay Eggs=Yes) -> Birds

 2. Cover : 'X' Rule은 Instance 'Y'를 Cover한다.
    ▪ 특정 Instance(Tuple)의 Attribute가 특정 Rule에 적용될 수 일을 때 Cover을 쓴다.
    ▪ 주어가 Rule

    ▪ Example

 3. Trigger : 'Y' Instance는 Rule 'X1'과 Rule 'X2'를 Trigger한다.

    ▪ Cover과 다르게 주어가 Instance이다.

    ▪ 복수의 룰이 하나의 인스턴스에 트리거가 될 수 있다.

 4. Rule Coverage & Rule Accuracy

    ▪ Rule : (Status = Single) -> No에 대해

    ▪ Coverage : 4/10 = 40%
    ▪ Accuracy : 2/4 = 50%

5. Rule-Based Classifier의 특징
    ▪ 상호 배타적 규칙

      - 모든 레코드는 하나의 룰에 의해 Cover된다.

      - 각 Rule은 Mutually Exclusive 하다.

    ▪ 포괄적 규칙

      - 모든 레코드는 적어도 하나 이상의 룰에 의해 Cover된다.

2. Decision Tree에서의 Rule-Based Classifier

 아래 왼쪽 Decision Tree에서 우측과 같은 Rule을 출출해 낸다.

 1. 규칙 단순화

    ▪ Rule은 단순화 되지만 위험성이 높다.

5. Ordered Rule Set
    ▪ 하나의 Record에 여러 Rule이 Cover될 때 사용

    ▪ Rule에다가 우선순위를 주고 높은 우선순위의 Rule을 적용

    

6. Rule Ordering Schemes
    ▪ Rule-based ordering : 우선순위가 낮은 Rule은 해석이 어려움

    ▪ Class-based ordering : 같은 class에 속하는 Rule을 연속적으로 순위를 둠. 우선 되어야하는 Rule이 밀려버릴 수 있음

3. 분류 규칙 생성 방법

 1. Direct Method

    ▪ 2개 이상의 class를 가지는 데이터 집단에서 하나의 class가 처리 될때까지 Rule을 추출하고 다음 class를 처리

    ▪ Sequential Covering

      - Rule Growing : 적용할 수 있는 Rule 중 많은 사례를 포함할 수 있는 Rule 선택
      - Instance Elimination : 예외(이상한거) Instance 제거

      - Rule Evaluation : 새로운 룰 추가 했을 시 좋아졌는지 평가

      - Stopping Criterion and Rule Pruning : 언제 멈출지 기준 및 규칙 설정

    ▪ RIPPER : repeated incremental pruning to produce error reduction

 2. Indirect Methods

    ▪ 의사 결정 트리와 같은 것을 이용
    ▪ C4.5
    ▪ C4.5와 RIPPER 비교

 3. Rule-Based Classifier의 장점

    ▪ 의사 결정 나무만큼 표현력이 뛰어남

    ▪ 쉽게 해석할 수 있음

    ▪ 쉽게 생성할 수 있음

    ▪ 새로운 인스턴스를 빠르게 분류할 수 있음

    ▪ 의사 결정 트리와 성능을 비교할 수 있음

3. Instance-Based Classifiers

 1. Memory based learning이라고도 함

    ▪ 이전의 데이터(memory에 있는 데이터)를 토대로 새로운 데이터를 분류함

    ▪ 사전 모델을 만들지 않음

 2. Rote learner classifier

    ▪ 훈련 데이터 전체를 암기한 후, 시험 사례 속성이 훈련  데이터와 정확히 일치할 때만 분류를 수행함

    ▪ 일부 시험 항목들이 어떠한 훈련 예와도 일치하지 않을 경우 분류가 안됨
    ▪ Nearest neighbor(인접 이웃) 찾기로 어느정도 해결함

 3. Nearest neighbor(KNN) classifier

    ▪ 학습된 Record 중 가장 distance가 가까운 Record들의 class를 따라감 

    ▪ 범위를 1(=K)라 했을 때, 1NN(KNN) classifier라고 한다.

    ▪ 너무 작은 범위를 데이터들의 class를 따라가면 Noise를 따라 갈수 있음

    ▪ 너무 큰 범위면 다른 클레스가 포함됨

    ▪ scale, curse of dimensionality에 대한 이슈가 있음

 4. PEBLS(Parallel Examplar-Based Learning System)

    ▪ Works with both continuous and nominal  features

    ▪ For nominal features, distance between two  nominal values is computed using modified value  difference metric (MVDM)

    ▪ Each record is assigned a weight factor

    ▪ Number of nearest neighbor, k = 1

    ▪ 예시

    - 위 사진에서 Marital Status Attribute에 대해 각 value 간 distance를 구했을 시 (Single,Married)와 (Married, Divorced)는 1, (Single, Divorced)는 0이다. 여기서 (Single, Divorced)는 거리가 1이기 때문에 같은 상태라고 생각해도 된다.

    - Refund의 d(Yes,No) 역시 1이다. 따라서 아래 2개의 tuple은 같은 것임으로 class는 No로 동일하다.

4. Bayes classifier

 확률론적 프레임워크로 class를 구별하는 방법이다. 해당 이론으로 classification을 하기엔 너무 어렵다.

 1. Bayesian classifier

    ▪ 위에서 C는 class, A는 다른 Attribute이다. Attribute는 여러개 일 수 있는데 확률이 가장 큰 것을 사용한다.

 

 2. Naïve Bayes classifier

    ▪ Since P(X|No)P(No) > P(X|Yes)P(Yes) Therefore P(No|X) > P(Yes|X)

    ▪ P(X|No)에서 X는 모든 Attribute이다. 따라서 모든 Attribute는 독립적이기 때문에 각각의 P(X|No)를 구해 곱한다.

 

 3. Naïve Bayes classifier Example

    ▪ 해당 Data는 P(X|No)P(No) > P(X|Yes)P(Yes)이기 때문에 P(No|X) > P(Yes|X)이고 따라서 Class는  No이다.