03) 분할 정복 : 규칙 기반의 분류

| 분류 규칙 이해

분류 규칙(Classification rules) 클래스를 레이블이 없는 예시에 할당하는 논리적인 if-else문 형태로 지식을 표현한다. 조건부(antecedent) 와 결론부(consequent)를 명시한다.

​

가지의 결정에 따라 적용되는 트리와 달리 규칙은 독립된 사실을 서술한 것처럼 읽을 수 있는 명제다.

​

규칙 학습자는 일반적으로 특징이 주로 또는 전체적을 명목형인 문제에 적용된다. 희고한 사건이 특징 값 사이에 매우 특정한 상호작용에서 발생하더라도 규칙 학습자는 희소 사건을 잘 식별한다.

​

| 분리 정복

분류 규칙 알고리즘은 분리 정복(separate and conquer)으로 알려진 휴리스틱을 활용한다. 규칙이 추가되면서 데이터의 부분집합도 추가적으로 분리되고, 전체 데이터셋이 모두 커버되고 더 이상의 예시가 남아있지 않을 까지 진행된다. 분리 정복이 많은 점에서 앞서 설명한 분할 정복(divide and conquer)휴리스틱과 유사하지만 미묘한 차이가 있다.

​

규칙 학습자는 동질적인 그룹을 발견하고자 가용한 특징을 이용한다.

​

규칙이 데이터의 부분을 커버하는 것처럼 보이기 때문에 분리 정복 알고리즘은 커버링 알고리즘(covering algorithms) 이라고 하며, 만들어진 규칙은 커버링 규칙이라고 한다.

​

| 1R 알고리즘

ZeroR )

어떠한 특징도 고려하지 않으며 아무 규칙도 학습하지 않는 규칙 학습자

이 방법은 특징 값에 상관없이 레이블되지 않은 모든 예시에 대해 가장 흔한 클래스를 예측한다.

​

1R 알고리즘 )

하나의 규칙을 선택하는 방식으로 ZeroR을 개선, 정교한 알고리즘의 정확도에 자주 근접한다.

1R은 각 특징에 대해 유사한 값을 기준으로 데이터를 그룹으로 분리한다. 그런 다음 알고리즘은 각 세그먼트에 대해 대다수 클래스를 예측한다. 각 특징에 기반을 두는 규칙의 오류율을 계산하고 최소 오류를 갖는 규칙을 단일 규칙으로 설정한다. 알고리즘은 가장 중요한 단일 규칙을 발견하고 종료한다.

​

| 리퍼 알고리즘

초기의 규칙 학습 알고리즘은 느렸다. 노이즈가 섞인 데이터의 경우 쉽게 부정확해졌다. 규칙 학습 알고리즘을 여러 회 반복하는 방식에서 진화한 리퍼 알고리즘은 규칙 학습용 효율적인 휴리스틱들을 여러 부분으로 연결했다. 일반적으로 알고리즘은 다음과 같은 3단계의 과정으로 이해할 수 있다.

1. 기르기

규칙에 조건을 탐욕스럽게 추가하고자 분할 정복 기법 사용, 데이터의 부분집합을 완벽하게 분류하거나 분할을 위한 속성이 없어질 때까지 진행된다.

​

2. 가지치기

규칙의 구체성이 증가돼도 더 이상 엔트로피가 줄지 않을 때 규칙은 즉시 가지치기된다.

​

1단계, 2단계가 종료 조건에 도달할 때까지 반복된다.

​

3. 최적화하기

종료 조건은 규칙의 전체 집합이 다양한 휴리스틱으로 최적화되는 지점이다.

​

복수의 조건부를 갖는 규칙을 생성할 수 있다. 따라서 복잡한 데이터를 모델링하는 알고리즘 능력은 향상되지만, 의사 결정 트리처럼 금방 규칙을 파악하기가 어려워진다.

​

| 의사 결정 트리에서 규칙 구성

규칙을 생성하고자 의사 결정 트리를 사용하는 방식의 주요 단점은 생성된 규칙이 규칙 학습 알고리즘으로 학습된 규칙보다 더 복잡하다는 것이다. 의사 결정 트리에 사용된 분할 정복 전략은 규칙 학습자의 전략과는 다르게 결과를 편향시킨다.

​

| 무엇이 트리와규칙을 탐욕스럽게 만드는가?

의사 결정 트리와 규칙 학습자는 탐욕 학습자이다. 선입 선처리 기반으로 데이터를 사용하기 때문이다.

​

의사 결정 트리에서 사용되는 분할 정복 휴리스틱 / 규칙 학습자에서 사용되는 분리 정복 휴리스틱 모두 한 번에 하나의 파티션을 만들고자 하며, 먼저 가장 동질적인 파티션을 찾고 난 후에 차선을 찾고, 모든 예시가 다 분류될 때까지 계속해서 찾는다.

​

특정 데이터셋에 최적이고, 가장 정확하고, 최소 개수로 된 규칙을 생성하는 것을 보장하지는 못한다. 가장 쉽게 달성할 수 있는 목표를 빨리 이룸으로써 데이터의 한 부분 집합에 대해 정확한 한 개의 규칙을 빠르게 발견할 수 있다. 하지만, 학습자는 전체 데이터셋에 대해 더 나은 전반적인 정확도를 갖기는 어렵다.

​

규칙을 만드는 방법에서 미묘한 차이를 보이는 트리와 규칙 !

트리는 이전 결정의 이력에 의해 영원히 제한된다. 그에 반해 분리 정복으로 규칙을 발견하면 규칙의 모든 조건으로 커버되지 않는 어떤 예시든 재정복 될 수 있다.

​

예시 ::

규칙학습자 )

• 땅에서 걷고 꼬리가 있는 동물은 포유류다 (곰, 고양이, 개, 코끼리, 돼지, 토끼, 쥐, 코뿔소)
• 동물이 털이 없다면 포유류가 아니다 (새, 독수리, 물고기, 개구리, 곤충, 상어)

개구리 재정복

• 그렇지 않으면 동물은 포유류다 (박쥐)

​

의사 결정 트리)

• 동물이 땅에서 걷고 털이 있다면 포유류다 ( 곰, 고양이, 개, 코끼리, 돼지, 토끼, 쥐, 코뿔소)

개구리를 자체 규칙에 배치

• 동물이 땅에서 걷고 털이 없으면 포유류가 아니다 (개구리)
• 동물이 땅에서 걷지 않고 털이 있으면 포유류다 (박쥐)
• 동물이 땅에서 걷지 않고 털이 없으면 포유류가 아니다 (새, 곤충, 상어, 물고기, 독수리)

​

규칙 학습자는 궁극적으로 고려됐지만 이전 규칙들로 커버되지 않는 경우를 다시 관찰할 수 있기 때문에 의사 결정 트리에서 생성된 규칙보다 좀 더 인색한 규칙들으 찾아낸다. 또한 이런 데이터의 재사용은 규칙 학습자의 계산 비용이 의사 결정에 드는 비용보다 좀 더 높을 수 있다는 것을 의미한다.

​

| 예제 : 규칙 학습자를 이용한 독버섯 식별

| 1단계 : 데이터 수집

버섯 필드 가이드

• 확실히 식용인 (definitely edible)
• 확실이 독이있는 (definitely poisonous)
• 독이 있을 가능성이 있으며 먹는 것을 권장하지 않는 (likely poisonous and not recommended to be eaten)
• 독이 있는 (poisonous)
• 독이 없는 (nonpoisonous)
• 갓 모양 (cap shape)
• 갓 색상 (cap color)
• 냄새 (odor)
• 주름 크기와 색 (size and color)
• 줄기 모양 (stalk shape)
• 서식지 (habitat)

​

| 2단계 : 데이터 탐색과 준비

버섯 샘플의 약 52%는 식용이고, 48%는 독이 있다.

​

버섯 데이터에 있는 8214개의 샘플이 야생 버섯의 완전 집합을 이룬다고 가정하자. 이미 알려진 버섯 유형의 완전 집합을 정확히 설명하는 규칙을 찾으려고 한다. 동일 데이터에 대해 모델을 만들고 테스트 하자.

​

| 3단계 : 데이터로 모델 훈련

간단한 규칙은 종종 예측을 아주 잘하므로 아주 간단한 규칙 학습자가 버섯 데이터에 대해 어떻게 수행되는지 살펴보자. 목표를 달성하고자 타깃 클래스를 가장 잘 예측하는 특징을 하나 식별하고 규칙 집합을 구성하는 데 사용할 1R 분류기를 적용한다.

​

OneR() 함수는 R 수식 구문을 사용해 훈련할 모델을 지정한다. 학습할 클래스 변수는 틸드의 왼쪽에 쓰고 예측 변수 특징은 오른쪽에 + 연산자로 분리해 쓴다. y 클래스 및 예측 변수 x1 과 x2 사이의 관계에 대한 모델을 만들고 싶다면 y ~ x1 + x2 처럼 수식을 작성할 수 있다. 모델의 모든 변수를 포함하려고 한다면 특수 기호 . 을 사용한다. 예를 들어 y~ .은 y와 데이터셋의 모든 특징 간의 관계를 명시한다.

​

버섯 데이터에 있는 모든 특징을 고려하도록 했다.

​

규칙 생성에 냄새(odor) 특징이 선택 됐다. 아몬드 (almond) 아니스 (anise) 등과 같은 odor 의 범주에는 버섯이 식용인지 (edible) 독이 있는지 (poisonous) 여부에 대한 규칙이 명시 된다.

​

| 4단계 : 모델 성능 평가

8124 개의 버섯 샘플 중 8004 개의 식용 적합성을 정확하게 예측했다.

​

예측과 실제 값의 혼동 행렬을 살펴보자. 먼저 1R 모델의 예측을 생성한 후, 실제 값과 비교해봐야 한다.

​

독성이 있는 120개가 식용 가능하다는 판단이 나와 문제가 발생하였다.

​

| 5단계 : 모델 성능 개선

고도화된 규칙 학습자를 위해 자반 기반의 리퍼(RIPPER) 규칙 학습 알고리즘의 구현체인 JRip()을 사용하겠다. 비트에 맞는 자바 설치 후 JRip () 규칙 학습자를 훈련 시켜보자.

​

JRip() 분류기는 버섯 데이터에서 전체 8개의 규칙을 학습했다. if-else 문이 나열된 것으로 생각한다. 세 개의 규칙은 다음과 같다.

​

• 냄새가 악취이면 이 버섯 종류는 독이 있다.
• 주름 크기가 좁고 주름색이 담황색이면 이 버섯 종류는 독이있다.
• 주름 크기가 좁고 냄새가 톡 쏘면 이 버섯 종류는 독이 있다.

​

여덟번 째 규칙은 이전의 일곱 가지 규칙에 해당되지 않는 버섯 샘플은 식용이라는 것을 암시한다. 즉,

• 그렇지 않으면 버섯은 식용이다.

​

오분류된 버섯 샘플은 없다.

​

| 요약

탐욕 알고리즘을 사용하는 두 개의 분류 방법을 다뤘다. 의사 결정 트리는 분할 정복 전략을 사용해 플로차트와 같은 구조를 생성하는 반면, 규칙 학습자는 논리적인 if-else 규칙을 식별해 데이터를 분리하고 정복한다. 두 방법은 통계적 배경 없이도 해석될 수 있는 모델을 생성한다.

​

인기 있고 구성 능력이 뛰어난 의사 결정 트리 알고리즘 중 하나가 C5.0 이다. 부스팅과 비용에 민감한 오류를 위한 옵션을 사용해 정확도를 향상시켰다.

​

1R 알고리즘은 잠재적으로 치명적인 버섯 샘플을 식별하는 데 99% 정확도를 이루고자 하나의 특징을 사용했다. 한 편 좀 더 고도화된 리퍼 알고리즘에 의해 생성된 여덟 개의 규칙은 모든 버섯의 식용 적합성을 정확하게 식별했다.

​

​

​

​