11. Rule Based Classification

Rule에 기반한 분류기

• 기본적인 아이디어는 IF-THEN을 사용하는 것
  • Ex) IF age = youth AND student = false THEN buys_computer = no
• 데이터의 수가 그렇게 많지 않은 경우에 사용할 수 있다
  • 이 Rule들은 Domain Experts (Human Experts)에 의해서 만들어진다
• 특정 데이터가 여러 개의 Rule에 부합하는 경우에는 Conflict Resolution이 필요하다
  • Size Ordering
    • Rule의 Size라는 것은 IF문에 걸려있는 Feature의 수
    • 즉, Size가 크다는 것은 Rule이 구체적이고 Toughest 하다는 것이다
    • Size가 큰 Rule일수록 더 높은 우선순위를 주는 방식
  • Class-based Ordering
    • Misclassification cost가 낮은 Rule을 선택하는 방식
  • Rule-based Ordering
    • Rule에 대한 우선순위를 미리 정해둔 List를 가지고 판단하는 방식
    • 각 Rule에 대한 우선순위 역시 Domain Experts가 정한다

 

Rule Extraction from a Decision Tree

---

Decision Tree가 사실 Rule-based라고 볼 수 있다

• Deicision Tree의 각 Path를 Rule로 변경 하면 된다
• Rule은 거대한 트리보다 이해하기가 쉽다
• 루트부터 리프노드까지의 Path 각각을 하나의 Rule로 정의한다
  • Path 상에 있는 Feature-Value 쌍은 각각 Rule에서 하나의 접속사를 형성한다
  • 리프노드는 최종적인 Class Prediction을 의미한다
  • Ex) age <= 30 AND

• Decision Tree로부터 Rule을 추출하면, Rule간에 Conflict가 발생하지 않는다 (Mutually Exclusive)
  • Decision Tree에서 내려갈 때, 여러 개의 Branch에 걸치는 경우는 없기 때문 에

 

Rule Extraction from Association Rule Mining

---

Association Rule Mining 을 기반으로 Rule을 생성

• Associative Classification으로도 불린다
  • Frequent Pattern Mining을 기반으로 Rule을 생성한다
  • min_sup, min_conf 값을 조절해서, Feature-Value(Condition)과 Class(Prediction) 사이에 강력한 연관관계를 찾을 수도 있다
    • 높은 Support, Confidence 값을 갖는 연관관계는 강력한 연관관계
  • Rule들은 Mutually Exclusive하지 않기 때문에 Conflict Resolution이 필요 하다
• Benefits and Limits
  • min_conf 값을 높게 잡으면, 만족하는 Frequent Pattern의 수가 줄어들 것이기 때문에 Rule의 수가 줄어들게 되어 Conflict가 감소하게 된다
  • 그렇지만 그럴 경우에는 Coverage가 낮아지는 문제 가 있다

 

Coverage and Accuracy of a Rule R

---

Rule R의 Coverage와 Accuracy

• Cover를 한다고해서 반드시 정확히 분류되는 것은 아니다
• Coverage는 전체 데이터 중에 얼마나 많은 데이터가 R에 의해서 판별이 될 수 있는지
• Accuray는 R이 얼마나 정확하게 분류를 하는지

 

Lazy vs Eager Learning

---

Lazy Learning과 Eager Learning의 차이를 알아보자

• Eager Learing
  • 주어진 Training Data를 가지고 미리 Classification Model을 학습 시켜둔다
  • 그리고 Test Data가 들어오면, 해당 모델을 통해서 분류를 한다
  • 미리 모델을 만들어두고 해당 모델을 통해 예측 을 하기 때문에 Eager하다고 한다
  • Machine Learning의 전형적인 방식
  • Ex) Decision Tree
• Lazy Learning
  • Test Data가 들어오기 전까지는 아무것도 하지 않는다
  • Training Data를 단지 저장만 하고 있는다
  • Test Data가 들어오면, Training Data를 기반으로 분류한다
  • Training에는 시간이 별로 소요되지 않지만, 예측을 하는데 많은 시간 이 걸린다
  • Ex) KNN Algorithm

 

K-Nearest Neighbor(KNN) Algorithm

---

대표적인 Lazy Learning 방식인 KNN 알고리즘에 대해 알아보자

K=5인 경우의 KNN 알고리즘

• 위의 예시는 K = 5인 경우이다
• 모든 데이터는 N차원 상에서 나타내진다 (N은 Data의 Feature의 수)
• 두 데이터 사이의 거리(dist(X1, X2))는 공간상에서 정의된다
  • 이때 dist function은 어떤 것을 사용해도 상관없다
  • Ex) Euclidean, Manhattan, ...
• Test Data와 가장 가까운 K개의 이웃들의 Class Label을 보고, 더 많은쪽으로 예측 (Voting)
  • Majority Voting (다수결)
  • 위의 예시에서는 5개의 이웃들 중에 - 가 더 많기 때문에 - 로 분류한다
• 그런데 K개의 데이터 중에서도 더 가까운 데이터들이 존재하지 않느냐! 라는 생각이 가능
  • 그래서 나온 방식이 Weighted Voting
  • K개의 이웃들에 대해서 개수만 세는 것이 아니라 이웃간의 거리도 고려해서 판단