RIPPER라는 널리 사용되는 규칙 유도 알고리즘입니다. 이 알고리즘은 여러 훈련 인스턴스와 거의 선형으로 확장되며 특히 오버로드된 클래스 분포가 있는 데이터 세트에서 모델을 구성하는 데 적합합니다. RIPPER는 검증 세트를 사용하여 모델 과적합을 방지하기 때문에 노이즈가 많은 데이터 세트에서도 잘 작동합니다.
RIPPER는 다수 클래스를 기본 클래스로 선택하고 소수 클래스를 식별하는 규칙을 이해합니다. 다중 클래스 문제의 경우 클래스는 빈도에 따라 시리즈입니다.
하자 (y1 y2 ...yc ) 정렬된 클래스, 여기서 y1 가장 빈도가 낮은 클래스이고 yc 가장 빈번한 수업입니다. 첫 번째 반복 동안 y1에 속하는 인스턴스 다른 클래스에 속하는 클래스는 부정적인 예로 레이블이 지정되는 반면 긍정적인 예로 Iabeled됩니다.
순차 적용 접근 방식은 긍정적인 예와 부정적인 예를 구별하는 규칙을 생성하는 데 사용할 수 있습니다. 다음으로 RIPPER는 y2를 구별하는 규칙을 추출합니다. 다른 나머지 클래스에서. 이 과정은 yc가 남을 때까지 반복됩니다. 기본 클래스로 지정됩니다.
RIPPER는 일반에서 특정으로 규칙을 늘리는 방법과 FOIL의 데이터 게인 측정을 사용하여 규칙 선행 항목에 삽입할 최상의 결합을 선택합니다. 규칙이 부정 인스턴스를 덮기 시작하면 접속사 삽입을 중지합니다.
새 규칙은 유효성 검사 세트의 구현에 따라 제거됩니다. 다음 메트릭은 가지치기가 필요한지 여부를 결정하기 위해 계산됩니다 - (p-n)/(p+n), 여기서 p(n)은 규칙이 적용되는 검증 세트의 긍정적(음수) 예제 수입니다.
이 메트릭은 유효성 검사 세트에 대한 규칙의 정확도와 단조롭게 관련되어 있습니다. 가지치기 후에 메트릭이 향상되면 결합이 제거됩니다. 규칙에 삽입된 마지막 conjunct부터 pruning이 완료됩니다. 예를 들어, ABCD → y 규칙이 주어지면 RIPPER는 D가 먼저 정리되어야 하는지, 그 다음에 CD, BCD 등으로 정리되어야 하는지 여부를 확인합니다. 초기 규칙은 긍정적인 인스턴스만 다루지만 정리된 규칙은 훈련 세트의 여러 부정적인 인스턴스를 포함할 수 있습니다.
규칙을 만든 후 규칙에 포함된 일부 긍정적 및 부정적 인스턴스가 제거됩니다. 그런 다음 최소 설명 길이 원칙을 기반으로 하는 중지 조건을 위반하지 않는 한 규칙이 규칙 집합에 추가됩니다.
새 규칙이 규칙 집합의 총 표현 길이를 최소 d비트만큼 향상시키면 RIPPER는 규칙 집합에 규칙 삽입을 중지합니다(기본적으로 d는 64비트로 선택됨). RIPPER에서 사용하는 또 다른 중지 조건은 유효성 검사 집합에 대한 규칙의 오류율이 50%를 초과해서는 안 된다는 것입니다. RIPPER는 규칙 집합의 여러 기존 규칙이 더 많은 대체 규칙으로 복원될 수 있는지 여부를 결정하기 위해 더 많은 최적화 단계를 구현합니다.