rule based classifier

• "if...then..." rules
  
• LHS = rule antecedent or precondition
• RHS = rule consequent
  

Applying Rule-Based Classifier

rule r은 attributes가 rule의 precondition을 만족시킨다면 instance x를 cover한다.
(or, an instance trigger or fire a rule r)

Quality Measures for classification Rule

a dataset D and a classification rule r: A->y

• Coverage of a rule
  -rule의 precondition을 만족하는 d의 record 비율
• Accuracy of a rule
  -class label이 y와 같은 r에 의해서 유도되는 record의 비율

Properties of Rule-Based Classifier

• mutually exclusive rule set

• 모든 레코드는 하나의 룰에 의해 Cover된다.
• 각 Rule은 Mutually Exclusive 하다.
  -Every instance is covered by at most one rule

• exhaustive rule set
  -Every instance is covered by at least one rule

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

두 속성 만족

• 모든 instance가 정확히 한가지 rule에 의해 커버된다고 보장한다
• 실제로 많은 분류기가 해당 특성을 갖고있지 않다

when a rule set is not exhaustive

• rule을 추가한다
  

• yd는 default class

when a rule set is no mutually exclusive

• Ordered Rules
  -모든 규칙이 우선순위에 따라 정렬(based on accuracy)
  -highest-ranked rule에 따라 결정된다

• Unordered Rules(다수결)
  -하나의 시험항목이 복수의 분류규칙에 의해 적용되고 결과는 특정 class에 대한 투표로 간주 한다
  -majority voting, weighted voting by accuracy

Ordered Rules

• ordered rule set = decision list
• Rule based ordering
  -rule별로 ordering
• Class-based ordering
  -같은 class가 나타나도록

분류 규칙 생성방법

• Direct Method
  -data set으로부터 rule을 직접 만든다
  -Examples: RIPPER, CN2, Holte’s 1R
• Indirect Method
  -다른 분류 모델로부터 rule을 가져온다(decision tree)
  -C4.5rules

Direct Method for Rule Extraction

• Sequential covering approach
  -greedy fashion으로 rule 생성
  -rule을 한번에 하나 추출

1. empty rule에서 시작
2. Learn-One-Rule funciton을 이용해서 rule 생성
3. rule에 의해 커버되는 training instance 제거
4. 2,3 반복 멈출때까지

Learn-One-Rule function: 가능한 많은 positive example, 가능한 적은 negative example 훈련데이터에서

Rule-Growing Strategy: Learn-One-Rule

• General-to-specific
  -stopping criterion 만날 때까지 rule qualit개선하도록 조건 계속 추가
  
• Specific-to-general
  -randomly chosen
  -조건 없애면, 개선
  -계속 제거하다, rule의 quality가 좋아지지않으면 멈춘다
  

Rule Evaluation

• 조건 추가될지 말지 결정한다.
  

Stopping Criterion

• gain or accuracy 계산
• 이득 없으면 멈춰

Rule Pruning

• generalization error 개선목적 -> overfitting 방지목적
• post-pruning of decision tree랑 비슷
• reduced error pruning

1. rule에서 조건 중 하나 제거
2. pruning 이전과 이후에 validation dataset에서 error measure 비교
3. error 개선시, 가지친다.

Indirect Methods for Rule Extraction

• decision tree로부터 reul set 가져온다

• mutually exclusive, exhaustive 처리

• rule simplification 효과
  -rule은 더이상 mutually exclusive하지 않다 - Ordered rule set
  -rule은 더이상 exhaustive하지 않다 - use a default class

-> C4.5 RULES

• unpruned decision tree로부터 rule들을 가져온다
• Rule ordering: class ordering scheme