[Data Science] Classification - Rule-based classification

Rule-based Classification

  • Rule-based classification은 IF-THEN rule을 사용하여 classification을 하는 기법이다.
  • 예를 들어, IF age = youth AND student = no THEN buys_computer = no와 같은 방식이다.
  • 이 방식은 데이터의 수가 적은 경우에 적합하다.
  • 도메인 지식을 가진 전문가가 rule을 만드는 경우도 존재한다.
  • 하나의 데이터가 2개 이상의 rule에 일치하는 경우도 발생할 수 있다. 이를 conflict라고 하는데 이 경우 conflict resolution이 필요하다.
    예를 들어, 다음과 같은 rule이 있다고 하자.
    Rule1. IF age = youth AND student = no AND human = yes THEN buys_computer = no
    Rule2. IF age = youth AND earning = low THEN buys_computer = yes
    이때, data의 feature가 <age=youth, student=no, earning=low, human=yes>라면 rule1, 2 둘 다에 겹치게 되어 conflict가 발생하게 된다.
    • Size ordering: 가장 엄격한 조건으로 우선순위를 결정한다. (즉, 조건이 많은 rule 우선. 위의 경우 Rule1 선택.)
    • Class-based ordering: potential misclassification cost가 낮은 순서대로 우선순위를 결정한다.
      위의 예시에서 Rule1에 대해 잘 못 분류했을 때 비용이 5라고 하였을 때, Rule2에 대해서 10이라고 한다면 Rule1을 우선하여 선택한다.
    • Rule-based ordering (decision list): rule quality나 도메인 전문가에 의해 rule마다 priority를 미리 선정해놓고 그에 따라 conflict를 해소한다.

Rule Extraction from a Decision Tree

  • Decision tree에서 rule을 추출해서 rule-based classification으로 사용할 수 있다.
  • Pros
    • Tree로 보는 것보다 이해하기 더 쉽다.
    • 하나의 rule이 root node에서 leaf node까지의 정보를 담고 있다.
    • Conflict가 발생하지 않는다.

Associative Classification (Association Rule Mining)

  • Associative classification은 association rule mining을 활용하여 classification을 하는 깁버이다..
    • P1 ^ P2 ... ^ Pl → "A_class = C" (with defined confidence and support levels)
  • Minimum support와 minimum confidence를 사용해서 feature-value 사이에서 연관성을 파악해서 높은 연관성의 feature를 사용하여 classification의 성능을 높인다.
  • 그러나 이 경우, rule이 상호배타적이지 않기 때문에 conflict가 발생할 확률이 높다. 이에 대한 관리는 해주어야 한다.
  • Minimum confidence를 높게 설정하면 연관성이 높은 feature를 확실하게 알 수 있다는 점이 장점이다.
  • 근데 coverge가 낮을 수 있다.

Coverage and Accuracy of a rule R

  • Coverage: rule R에 맞는 데이터의 비율
    • 예를 들어, IF student = yes THEN eat_lunch=yes 라는 rule이 있을 때, 전체 데이터 10개 중 rule에 속하는 데이터가 4개라면 coverage는 4/10이다.
  • Accuracy: rule R로 분류한 데이터 중 정확하게 분류한 데이터의 비율
    • 위의 경우, 분류된 데이터 4개 중 정확하게 분류된 데이터가 3개라면 accuracy는 3/4이다.