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가 데이터의 불확실성과 복잡성을 잘 관리할 수 있음을 의미한다.
- 클래스 선택 및 정렬
RIPPER는 데이터에서 주요 클래스를 기본 클래스로 선정. 그리고 소수 클래스를 식별하는 규칙을 찾기 시작. 만약 클래스가 여러 개 있을 경우, 이러한 클래스들은 그들의 빈도수에 따라 정렬. \[{y}_{1},{y}_{2},...,{y}_{c}\]
로 표현되는 이러한 정렬에서 y1은 가장 적은 빈도의 클래스이며, yc는 가장 빈도가 높은 클래스다.
- 순차적 커버링
첫 번째 반복에서는 y1 클래스에 속하는 인스턴스를 양성 예제로 설정하고, 다른 클래스에 속하는 인스턴스는 음성 예제로 설정한다. 이렇게 양성과 음성 예제를 구별하는 규칙을 생성하는 순차적 커버링 방식을 사용한다. 그리고 다음으로 y2와 나머지 클래스를 구별하는 규칙을 찾아간다. 이 과정은 가장 빈도가 높은 클래스 yc가 선택될 때까지 반복.
- 규칙 확장 및 데이터 이득 측정
RIPPER는 규칙을 확장하기 위한 특별한 방법을 사용하며, 이때 FOIL(First Order Inductive Learner)의 데이터 이득 측정을 사용하여 규칙 전제부에 삽입될 최적의 조건을 결정. 만약 규칙이 음성 인스턴스를 시작으로 포함하면, 조건 추가를 중단한다.
- 검증 세트를 사용한 가지치기
생성된 규칙은 검증 세트에서의 성능에 따라 가지치기. \[\frac {p-n} {p+n}\]
이라는 지표가 사용되며, 여기서 p는 검증 세트에서 규칙에 의해 포함된 양성 예제의 수이고, n은 음성 예제의 수 다. 이 지표는 규칙의 정확도와 관련이 있다. 만약 가지치기 후에 지표가 향상된다면, 해당 조건은 규칙에서 제거된다.
- 규칙 최적화
RIPPER는 규칙 생성 후에 해당 규칙이 커버하는 일부 인스턴스를 제거. 만약 규칙이 최소 설명 길이 원칙에 위배되지 않는다면 규칙 집합에 추가. 만약 새로운 규칙이 규칙 집합의 총 표현 길이를 최소 d 비트(기본적으로 64 비트)만큼 향상시키지 못한다면, RIPPER는 규칙 추가를 중단. 추가로, 규칙의 오류율이 검증 세트에서 50%를 초과하면 안 된다.
대략적 Flowchart
시작 -> 데이터 로드 -> 첫 번째 클래스 선택
-> Grow Phase: 규칙 생성 (데이터 커버링 조건 추가)
-> Prune Phase: 규칙 최적화 (조건 제거)
-> 해당 클래스에 대한 규칙 완성 -> 다음 클래스로 이동
-> 모든 클래스에 대한 규칙 생성 완료? -> 종료
- 시작.
데이터에서 클래스 정렬: 클래스 빈도에 따라 아래 순서로 정렬. \[{y}_{1},{y}_{2},...,{y}_{c}\]
- y1을 양성으로 설정하고 나머지 클래스를 음성으로 설정.
- 규칙 생성:
- FOIL 데이터 이득을 사용하여 규칙 조건 추가.
- 음성 인스턴스를 포함할 경우 조건 추가 중지.
- 규칙 검증:
- 검증 세트를 사용하여 규칙 성능 평가.
- 아래 지표를 사용하여 가지치기 진행. \(\frac {p-n} {p+n}\)
- 규칙 최적화:
- 규칙 커버하는 인스턴스 제거.
- 최소 설명 길이 원칙을 만족하는지 확인.
- 만족하는 규칙이 있으면 규칙 집합에 추가.
- y2,y3,…,yc에 대한 규칙을 같은 방식으로 생성할 때까지 3-7 단계 반복.
- 종료.
RIPPER Algorithm의 예제
아래와 같이 가정해보자.
## 날씨 | 풍속 | 운동 여부
맑음 | 강함 | 아니오
맑음 | 약함 | 예
흐림 | 강함 | 아니오
흐림 | 약함 | 아니오
RIPPER 알고리즘을 적용하여 ‘운동 여부’ 를 예측하는 규칙을 만들면 다음과 같은 규칙들을 얻을 수 있을 것이다:
IF 날씨 = 맑음 AND 풍속 = 약함 THEN 운동 여부 = 예
IF 날씨 = 흐림 OR 풍속 = 강함 THEN 운동 여부 = 아니오
위의 예제는 매우 간단하게 RIPPER의 동작 원리를 보여주기 위한 것이므로, 실제 데이터셋에서는 더 많은 조건과 규칙이 생성될 수 있다.
