리퍼(RIPPER) 알고리즘의 개요
RIPPER(Repeated Incremental Pruning to Produce Error Reduction)는 널리 사용되는 규칙 유도(rule induction) 알고리즘입니다. 이 알고리즘은 학습 데이터 수에 거의 선형적으로 확장되며, 특히 클래스 분포가 불균형한 데이터셋에서 모델을 구축하는 데 매우 적합합니다.
RIPPER는 검증 세트(validation set)를 활용해 모델의 과적합(overfitting)을 방지하기 때문에, 노이즈가 많은 데이터셋에서도 안정적인 성능을 발휘한다는 장점이 있습니다.
다중 클래스 문제의 처리 방식
RIPPER는 다수 클래스(majority class)를 기본 클래스(default class)로 선택하고, 소수 클래스(minority class)를 식별하는 규칙을 학습합니다. 다중 클래스 문제의 경우, 클래스는 빈도순으로 정렬됩니다.
(y1, y2, ..., yc)가 빈도순으로 정렬된 클래스라고 할 때, y1은 가장 빈도가 낮은 클래스, yc는 가장 빈도가 높은 클래스입니다. 첫 번째 반복 단계에서 y1에 속하는 인스턴스는 양성(positive) 예제로, 나머지 클래스에 속하는 인스턴스는 음성(negative) 예제로 레이블링됩니다.
규칙 생성 과정
이후 순차적 커버링(sequential covering) 방식을 사용해 양성 예제와 음성 예제를 구분하는 규칙을 생성합니다. 그다음 RIPPER는 y2를 나머지 클래스들과 구분하는 규칙을 추출하며, 이 과정은 기본 클래스로 지정된 yc만 남을 때까지 반복됩니다.
규칙 확장에는 일반→특화(general-to-specific) 방식이 사용되며, FOIL의 정보 획득(information gain) 측도를 통해 규칙 선행부(antecedent)에 삽입할 최적의 접속사(conjunct)를 선택합니다. 규칙이 음성 인스턴스를 커버하기 시작하면 접속사 삽입을 중단합니다.
가지치기(Pruning) 메커니즘
새로운 규칙은 검증 세트에서의 성능을 기준으로 가지치기됩니다. 가지치기 필요 여부는 다음 지표로 판단합니다.
(p − n) / (p + n)
여기서 p와 n은 각각 해당 규칙이 커버하는 검증 세트 내 양성·음성 예제의 수입니다. 이 지표는 검증 세트에서의 규칙 정확도와 단조 관계를 가지므로, 가지치기 후 지표가 향상되면 해당 접속사가 제거됩니다.
가지치기는 마지막에 삽입된 접속사부터 시작됩니다. 예를 들어 ABCD → y라는 규칙이 주어지면, RIPPER는 먼저 D를 제거할지 검사한 후 CD, BCD 순으로 확인합니다. 초기 규칙은 양성 인스턴스만 커버하지만, 가지치기된 규칙은 학습 세트의 일부 음성 인스턴스를 커버할 수도 있습니다.
중단 조건과 최적화
규칙이 생성되면 해당 규칙이 커버하는 일부 양성·음성 인스턴스가 제거되고, 최소 기술 길이(MDL, Minimum Description Length) 원리에 기반한 중단 조건을 위반하지 않는 한 규칙 집합(ruleset)에 추가됩니다.
새로운 규칙이 규칙 집합의 전체 표현 길이를 최소 d비트(기본값 64비트) 이상 개선하지 못하면 RIPPER는 규칙 추가를 중단합니다. 또 하나의 중단 조건은 검증 세트에서 규칙의 오류율이 50%를 초과하지 않아야 한다는 것입니다.
마지막으로 RIPPER는 추가 최적화 단계를 수행하여, 규칙 집합에 있는 기존 규칙들을 더 나은 대체 규칙으로 교체할 수 있는지 판단함으로써 전체 모델의 성능을 한층 끌어올립니다.