Boruta 알고리즘

 

변수 선택은 예측 모델을 만드는데 있어서 중요한 단계이다. 데이터의 변수들을 모두 사용하는 것은 과적합(overfitting)을 발생시킬 수 있으며, 많은 시간과 비용이 든다. 실제로, 많은 머신러닝 알고리즘들은 최적의 변수보다 많은 변수를 사용하면 예측 정확도가 감소한다고 알려져 있다(Kohavi and John, 1997). 또한, 실용적인 관점에서 가능한 최고의 분류 결과를 산출하는 변수 집합을 고르는 것이 중요하며(최소-최적 문제 (minimal-optimal problem) (Nilsson et al., 2007)), 몇몇 상황에서 분류와 관련 있는 모든 변수들을 찾아내는 것 역시 중요하다(다중 연관 문제 (all-relevant problem) (Nilsson et al., 2007)). 

 

이러한 이유로 변수 선택은 분석 절차에서 중요하게 인식되고 있으며 크게 3가지 방식으로 분류할 수 있다.

 

• Filter Method : 모델링 기법에 의존하지 않고 데이터에 대한 통계적 특성 예를들면, 상호 정보량, 상관계수로부터 변수 순위를 정하고 가장 높은 순위의 변수들을 선택하는 방법
• Wrapper Method : 변수의 일부만을 사용해 모델링을 수행하고 그 결과를 확인하는 작업을 반복하여 변수를 선택하는 방법으로, 예측 정확도 측면에서 가장 좋은 성능을 보이는 부분집합을 뽑아내는 방법. 일반벅으로 필터방법보다 래퍼 방법의 정확도가 더 높다. 
• Embedded Method : 모델링 기법 자체에 변수 선택이 포함되어 있는 방법

---

Basic

 

보루타 알고리즘은 랜덤포레스트를 기반으로 변수를 선택하는 래퍼 방법(Wrapper Method)으로 기본적인 아이디어는 기존 변수를 복원추출해서 만든 변수(shadow) 보다 모형 생성에 영향을 주지 못했다고 하면 이는 가치가 크지 않은 변수로 인식하여 제거하는 것이다.

 

 

이제 천천히 스텝을 밟아가보자. 먼저, 랜덤포레스트를 기반으로 변수 선택을 수행한다고 했는데 랜덤포레스트에 대해 간략하게 설명하면, 다른 알고리즘과 비교했을 때 상대적으로 빠르며, 모수 튜닝없이 수행될 수 있고 변수의 중요도를 수치로 산출해준다는 장점을 가지고 있다. 디폴트로 이용되는 변수의 중요도는 MDI(Mean Decrease in Impurity)방법으로 특정 변수로 인해 분리되는 노드의 중요도(불순도)를 계산하는 것이다. 이는 각 트리에서 사용된 변수마다 산출되며 최종적으로 모든 트리에 대해 평균한 값을 사용한다. 이때, 목적이 분류(Classification)인 경우에는 지니계수, 엔트로피를 이용하고, 목적이 회귀(Regression)인 경우에는 MSE를 이용하여 노드의 중요도(불순도)를 계산한다. 연속형 변수 또는 범주의 수가 매우 많은 변수일수록 변수 중요도가 높게 산출된다는 단점이 있다. 이를 개선한 방법으로 Permutation Importance가 존재하며 추후 포스팅에서 다루도록할 것이다. 지금까지 랜덤포레스트에서 변수중요도를 구하는 원리를 알아보았으며 보루타 알고리즘에 대해 자세히 다뤄보자.

 

---

Boruta

 

보루타 알고리즘은 다음과 같은 절차로 수행된다.

 

1. 모든 독립변수에 대한 복제한 랜덤 변수를 생성한다. 예를 들어, 원 데이터에 5개 보다 적은 독립 변수가 있을 때, 적어도 5개의 변수를 복제한다. 이를 우리는 "shadow features" or "permuted copies" 라고 부른다. 

2. 반응변수와의 상관을 제거하기 위해 복제된 자료를 랜덤하게 섞고 원 자료와 결합한다. 

3. 결합된 데이터와 원 데이터에 대해 랜덤포레스트 모형을 생성하고, 변수중요도(MDI)를 계산한다. 

4. 그런 다음, Z-score를 계산하는데 이는 정확도 손실의 평균을 정확도 손실 표준편차로 나눈 값이다.그런 다음, Z-score를 계산하는데 이는 변수마다 [(각 트리에 대한 정확도 손실 값 - 전체 트리의 정확도 손실의 평균) / 정확도 손실 표준편차]로 나눈 값이다. $z = (x-\mu)/\sigma$ 

5. 쉐도우 변수들 중 가장 높은 Z-score(MZSA, Maximum Z score among Shadow Attributes)를 찾는다. 

6. 원 자료에 대한 Z-score가 MZSA보다 큰 경우 Hit를 +1 해준다. (이는 MZSA보다 클때 중요한 변수를 표시하는 수단)

7. 위의 6번 과정을 랜덤포레스트가 수행되는 횟수만큼 또는 모든 변수들이 중요한 변수와 중요하지 않은 변수로 tagged 될 때까지 반복한다. 

 

우(원 변수), 좌(쉐도우 변수)

결합한 데이터에 RF모형을 적합시켜 변수중요도를 계산

MZSA보다 높은 변수중요도를 가진 원 변수는 hit, 작은 변수는 not hit 

4개의 변수에 대해 보투타 알고리즘을 3번 반복한 예시

---

Point

 

보루타 알고리즘의 장점은 목적이 분류와 회귀인 경우에 모두 잘 적용되며, 랜덤포레스트에서 산출되는 변수중요도를 개선한 방법이다. 즉, 랜덤포레스트 방법은 수행할 때마다 변수의 중요도가 바뀔수 있지만, 보루타 알고리즘은 랜덤 포레스트를 반복하여 중요도가 변동되는 점을 개선하였다. 또한, all-relevant 방법으로 선택된 변수는 모두 반응변수와 관련이 있다. (반대로 다른 대부분의 변수선택 방법은 mininal optimal 방법으로 예측 정확도를 높이는 방향으로 변수의 부분집합을 선택하므로 변수와는 관련이 적을 수 있다.) 변수들간에 교호작용이 있어도 적용가능하다. 

 

 

 

=> R에서 Boruta 알고리즘 사용하기

 

 

 

참고문헌

 

data-newbie.tistory.com/494

danielhomola.com/feature%20selection/phd/borutapy-an-all-relevant-feature-selection-method/

blog.exploratory.io/finding-variable-importance-with-random-forest-boruta-28badd116197

soohee410.github.io/iml_tree_importance

velog.io/@vvakki_/%EB%9E%9C%EB%8D%A4-%ED%8F%AC%EB%A0%88%EC%8A%A4%ED%8A%B8%EC%97%90%EC%84%9C%EC%9D%98-%EB%B3%80%EC%88%98-%EC%A4%91%EC%9A%94%EB%8F%84Variable-Importance-3%EA%B0%80%EC%A7%80

www.datasciencecentral.com/profiles/blogs/select-important-variables-using-boruta-algorithm