RIPPER Algorithm 이란?

in Machine Learning & Engineering Last modified at:
RIPPER Algorithm 이란?

알고리즘 공부도 시작해야 할 듯 합니다.. 잊고있던 또는 모르던 알고리즘이 많네요. 차근차근 정리해보겠습니다!

RIPPER Algorithm의 배경

RIPPER (Repeated Incremental Pruning to Produce Error Reduction) 알고리즘은 주로 범주형 데이터에 대한 규칙 기반 분류(classification)를 위해 개발되었다. RIPPER는 대표적인 규칙 기반 분류 알고리즘 중 하나로 1995년 William W. Cohen에 의해 소개되었다. 이 알고리즘이 개발된 배경에는 전통적인 의사결정 나무(Decision Trees)와 같은 분류 방법의 한계를 극복하고자 한 목적이 있었다. RIPPER는 특히 Noise가 있는 Dataset에서도 잘 동작한다는 특징이 있다.

RIPPER Algorithm의 원리

  • 확장성 및 Noise 대응

RIPPER는 규칙 유도 알고리즘으로 널리 알려져 있다. 데이터 일부를 규칙 생성에, 다른 일부를 가지치기에 사용해 과적합을 줄이고, 규칙을 너무 복잡하게 늘리지 않도록 설명 길이도 고려한다. noise가 있다고 무조건 잘 맞는 것은 아니지만, 학습 데이터를 전부 설명하려고 조건을 끝없이 추가하는 것을 막는 구조다.

  • 클래스 선택 및 정렬

RIPPER는 데이터에서 주요 클래스를 기본 클래스로 선정. 그리고 소수 클래스를 식별하는 규칙을 찾기 시작. 만약 클래스가 여러 개 있을 경우, 이러한 클래스들은 그들의 빈도수에 따라 정렬. \[{y}_{1},{y}_{2},...,{y}_{c}\]

로 표현되는 이러한 정렬에서 y1은 가장 적은 빈도의 클래스이며, yc는 가장 빈도가 높은 클래스다.

  • 순차적 커버링

첫 번째 반복에서는 y1 클래스에 속하는 인스턴스를 양성 예제로 설정하고, 다른 클래스에 속하는 인스턴스는 음성 예제로 설정한다. 이렇게 양성과 음성 예제를 구별하는 규칙을 생성하는 순차적 커버링 방식을 사용한다. 그리고 해당 클래스의 규칙이 커버한 인스턴스를 제외한 데이터에서 y2와 나머지 클래스를 구별하는 규칙을 찾아간다. 가장 빈도가 높은 클래스 yc는 앞선 규칙에 해당하지 않을 때 예측할 기본 클래스로 남겨 둔다.

  • 규칙 확장 및 데이터 이득 측정

RIPPER는 규칙을 확장하기 위한 특별한 방법을 사용하며, 이때 FOIL(First Order Inductive Learner)의 정보 이득을 기준으로 규칙 전제부에 삽입할 조건을 결정. 규칙이 아직 음성 인스턴스를 포함하고 있다면, 이를 제외할 수 있도록 조건을 AND로 추가한다. 성장 데이터에서 음성 인스턴스를 더 이상 포함하지 않는 규칙을 만드는 것이 목표다. 조건을 더 추가할 수 없는 경우에도 성장을 멈춘다.

  • 검증 세트를 사용한 가지치기

생성된 규칙은 검증 세트에서의 성능에 따라 가지치기. \[\frac {p-n} {p+n}\]

이라는 지표가 사용되며, 여기서 p는 가지치기용 데이터에서 규칙에 의해 포함된 양성 예제의 수이고, n은 음성 예제의 수 다. 이 지표는 규칙의 정확도와 관련이 있다. 규칙 끝의 조건들을 제거한 후보를 비교해, 가지치기 데이터에서 좋은 성능을 보이는 규칙을 선택한다. 학습에 쓰는 데이터 일부를 나누는 것이지, 최종 평가용 test set으로 가지치기하는 것은 아니다.

  • 규칙 추가와 중단 조건

규칙을 생성하고 가지치기한 뒤 규칙 집합에 추가하고, 해당 규칙이 커버한 인스턴스를 제외한 데이터에서 다음 규칙을 찾는다. 중단 여부는 규칙 자체뿐 아니라 규칙으로 설명하지 못한 오류까지 포함한 설명 길이(DL, Description Length)를 기준으로 판단한다.

Weka의 JRip 구현에서는 지금까지 찾은 최소 DL보다 현재 DL이 64비트를 초과해 커지면 규칙 추가를 중단한다. 추가로 커버할 양성 예제가 없거나, 새 규칙의 오류율이 50% 이상인 경우에도 중단. 매번 64비트 이상 개선해야 한다는 의미는 아니다.

  • 규칙 최적화

초기 규칙 집합을 만든 뒤에는 각 규칙을 새로 만드는 후보와 기존 규칙에 조건을 더 붙이는 후보를 비교한다. 이 후보들도 가지치기한 다음 설명 길이를 비교해 최종 규칙을 고르고, 전체 DL을 증가시키는 규칙은 제거한다.

대략적 Flowchart

시작 -> 데이터 로드 -> 클래스 빈도순 정렬 -> 소수 클래스 선택

-> Grow Phase: 규칙 생성 (음성 예제를 제외하도록 조건 추가)

-> Prune Phase: 가지치기 (끝의 조건 제거 후보 비교)

-> DL·잔여 양성 예제·오류율로 규칙 추가/중단 판단

-> 계속? 같은 클래스에서 다음 규칙 생성

-> 중단? 규칙 집합 최적화 -> 다음 클래스로 이동

-> 마지막 클래스는 기본 예측으로 남김 -> 종료
  1. 시작.

  2. 데이터에서 클래스 정렬: 클래스 빈도에 따라 아래 순서로 정렬. \[{y}_{1},{y}_{2},...,{y}_{c}\]

  3. y1을 양성으로 설정하고 나머지 클래스를 음성으로 설정.
  4. 규칙 생성:
    • FOIL 데이터 이득을 사용하여 규칙 조건 추가.
    • 성장 데이터에서 음성 인스턴스를 제외하도록 조건을 계속 추가.
  5. 규칙 검증:
    • 검증 세트를 사용하여 규칙 성능 평가.
    • 아래 지표를 사용하여 가지치기 진행. \(\frac {p-n} {p+n}\)
  6. 규칙 추가 여부 판단:
    • 규칙과 오류의 DL이 지금까지의 최솟값보다 64비트를 초과해 커지는지 확인.
    • 잔여 양성 예제가 없는지, 새 규칙의 오류율이 50% 이상인지 확인.
  7. 중단 조건에 도달하지 않았다면 규칙이 커버한 인스턴스를 제외하고 같은 클래스의 다음 규칙 생성. 초기 규칙 집합을 만든 뒤에는 후보 규칙들을 비교해 최적화.
  8. y2,y3,…,y(c-1)도 같은 방식으로 처리하고, yc는 기본 클래스로 남김.
  9. 종료.

RIPPER Algorithm의 예제

아래와 같이 가정해보자.

## 날씨 | 풍속 | 운동 여부

맑음 | 강함 | 아니오
맑음 | 약함 | 예
흐림 | 강함 | 아니오
흐림 | 약함 | 아니오

소수 클래스인 ‘예’를 설명하는 규칙과, 어디에도 해당하지 않을 때 사용할 기본 클래스를 생각해보자. 이 네 행을 설명하는 규칙 집합은 아래처럼 표현할 수 있다:

IF 날씨 = 맑음 AND 풍속 = 약함 THEN 운동 여부 = 예
ELSE 운동 여부 = 아니오

한 규칙 안의 조건은 AND로 연결되고, 다른 규칙들은 위에서부터 차례로 확인한다. 아무 규칙에도 해당하지 않으면 기본 클래스인 ‘아니오’를 예측한다.

위의 예제는 규칙 집합을 읽는 방법을 보여주기 위한 것이고, RIPPER를 학습해서 얻은 출력은 아니다. 네 행뿐인 데이터에 실제 구현의 가지치기·최소 표본 수 조건을 적용하면 다른 규칙이 나올 수 있다. 실제 데이터셋에서는 더 많은 조건과 규칙이 생성될 수 있다.

참고: Weka JRip의 RIPPER 구현 설명, JRip 구현 코드 — 2026-10-12 확인.