뚜리뚜벅

이번 게시글에는 PKDD 2003 컨퍼런스에서 발표된 SMOTEBoost 논문에 대해 작성하겠습니다.

Abstract

불균형 상황에서, 데이터 수가 적은 소수 클래스를 학습하게 되면 모델은 다수 클래스에 편향되게 학습이 되어서 다수 클래스에 대한 예측 정확도는 높아지지만, 소수 클래스에 대한 예측 정확도는 매우 낮아지는 문제가 흔히 발생합니다. 이를 해결하기 위해 대표적으로 소수 클래스를 생성하는 SMOTE기법을 사용하는데, SMOTE 기법은 소수 클래스 데이터를 Oversampling하기 위해 설계된 기법으로 불균형 상황에서 소수 클래스 예측 정확도를 높이는 데 효과적인 기법입니다.

이 논문에서는 불균형 데이터 셋에서 학습을 위해 SMOTE 기법과 Boosting 기법을 결합하여 새로운 접근법을 제시하고자 합니다.

SMOTEBoost는 소수 클래스를 생성함으로써 부스팅 알고리즘의 가중치 업데이트 방식에 영향을 미치며, 이를 통해 skewed distribution을 보완할 수 있게 합니다.

• SMOTE에 대해 혹시 모르신다면 이 글을 보고 오시는 것을 추천합니다!
  • https://enjoy0life.tistory.com/13

SMOTEBoost Algorithm

기존의 부스팅 알고리즘은 오분류된 데이터에 가중치를 부여해 오분류된 데이터를 잘 학습할 수 있도록 작동합니다. 하지만, 데이터가 심각하게 불균형한 경우, 부스팅 알고리즘이 다수 클래스에 편향된 분포를 학습하게 되어 소수 클래스의 분류 성능이 낮아지는 문제가 발생합니다.

저자의 목표는 불균형 데이터에서 발생하는 편향(bias)을 줄이고, 소수 클래스의 데이터 경계를 더 잘 학습할 수 있는 모델을 만드는 것입니다.(편향을 줄이기 위해서는 데이터의 균형을 맞춰야 해서 가장 대표적인 기법인 SMOTE 기법을 사용해서 데이터를 생성한 것 같습니다.)

이제 SMOTE 기법과 Boosting 알고리즘을 어떻게 결합시켜 불균형 문제를 완화시킬 수 있었는지 살펴보도록 하겠습니다.

SMOTEBoosting 알고리즘

1. SMOTE기법 적용
   1. 각 반복에서, 소수 클래스 데이터에 대해 SMOTE 기법을 적용해 데이터를 생성합니다.
2. 데이터 분포 업데이트 $D_t$
   1. 각 반복에서 생성된 샘플은 분포 $D_t$에 추가되어 사용됩니다. 소수 클래스 데이터가 추가되어서 소수 클래스의 가중치를 증가시키는 효과를 얻을 수 있습니다.
      1. 가중치를 증가시킨다는 것은 소수 클래스가 추가 되었으니 분류기가 다수 클래스로 편향되어 예측하지 않고 소수 클래스에 대해 조금 더 학습을 잘 할 수 있도록 돕는다는 것 같습니다.
3. SMOTE 데이터 삭제
   1. 각 반복단계에서 생성된 데이터는 제거되며 다음 부스팅단계에서 새롭게 생성된 데이터를 사용합니다.
   2. 생성된 데이터는 실제 데이터가 아니므로 노이즈가 될 수 있기 때문에 삭제하는 것 같습니다!
      1. 처음에는 생성된 데이터를 저장하여 계속 증가시키면 불균형이 완화되고 모델 성능이 좋아질거라고 생각했는데, SMOTEBoost의 목적을 확인해야 하는 것 같습니다.
      2. SMOTEBoost의 목적은 데이터 생성하여 균형을 맞추는 것이 아닌 소수 클래스의 패턴을 학습할 수 있는 기회를 늘리는 것이기 때문에 굳이 맞출필요는 없는 것 같습니다. 그리고 사실 SMOTE로 생성한 데이토 실제 소수 클래스가 아닌데, 소수 클래스라고 지정하고 학습하게 되면 오히려 노이즈로 작용할수도 있는 것 같습니다!
4. Decision boundary
   1. 생성된 데이터는 Decision boundary 학습하는데 도움을 줍니다.
5. 최종 분류기 학습
   1. 위 과정을 반복하여 최종 분류기를 학습하고, 데이터셋을 사용해 SMOTEBoost 적용하여 다른 기법들과 성능 비교

SMOTEBoost의 흐름을 설명해드렸고, 아래 사진은 알고리즘을 pseudo code로 작성한 것입니다.

Experimental Results

다음은 불균형한 데이터셋에서 SMOTEBoost의 성능을 다른 기법과 비교해보았습니다.

위 사진은 Mammography 데이터셋을 사용해서 F-value를 보았습니다. SMoteBoost에서 N=100으로 설정했을 때 분류기의 성능이 가장 좋은 것을 확인할 수 있습니다.

다음은 Satimage 데이터셋을 사용하여 F-value를 보았는데, 이때는 N=300으로 설정했을 때 성능이 가장 좋은 것을 확인할 수 있습니다.

이처럼 SMOTEBoost 모델이 기존의 SMOTE기법보다 성능이 좋은 것을 알 수 있으며 생성하는 숫자는 데이터셋마다 다른 것 같습니다.

확실히 SMOTE 기법만 사용하는 것보단 Boosting 모델을 결합하여 쓰면 성능이 좋은것을 알 수 있습니다.(아마도 부스팅의 목적이 오분류된 데이터를 더 잘 분류할 수 있도록 하는것이 목적이니까 소수 클래스를 잘 분류하는 모델을 만들어야하는 목적과 부합해서 좋은 시너지를 낼 수 있는 것 같습니다!)

참고문헌

1. SMOTEBoost : https://link.springer.com/chapter/10.1007/978-3-540-39804-2_12

이번 글에서는 2023년 5월 International Journal of Machine Learning and Cybernetics 저널에 게재된 OUBoost 논문에 대해 작성하겠습니다.

Abstract

현실 세계에서는 종종 불균형 데이터가 발생하며, 이는 다수 클래스를 잘 예측하지만 소수 클래스에 대해 분류기가 편향되어 예측 정확도가 떨어지는 문제를 야기합니다.

이 논문에서는 Peak clustering 방법을 사용해 다수 클래스의 데이터를 선택하여 undersampling을 수행하는 새로운 기술을 제안합니다. 또한, 소수 클래스에 대해 SMOTE 기반의 synthetic 데이터를 생성하고, 이를 부스팅 알고리즘과 결합한 새로운 OUBoost 알고리즘을 제시했습니다.

30개의 실제 불균형 데이터셋에 대해 여러 평가 지표를 사용하여 실험을 진행했으며, 대부분의 데이터셋에서 OUBoost를 사용했을 때 소수 클래스의 예측 성능이 개선되는 것을 확인했습니다.

아래 사진은 OUBoost 모델의 아키텍쳐입니다.

Density-peak clustering

이 논문에서 Density-peak clustering(DPC)방법을 사용하여 다수 클래스 데이터를 제거하였는데, DPC가 무엇인지 살펴보겠습니다.

Density-peak clustering (DPC) 알고리즘은 복잡한 구조를 가진 데이터셋에서 클러스터를 식별하기 위해 설계된 클러스터링 알고리즘입니다. 클러스터의 중심을 식별하기 위해 크게 2가지 과정을 거치게 됩니다.

1. 클러스터 중심은 local density가 낮은 샘플들 사이에 위치하며, 더 높은 밀도를 가진 샘플들로부터 상대적으로 멀리 떨어져 있습니다.
2. 샘플 간의 거리와 local density를 결합하여 클러스터를 정의합니다.

여기서 local density, distance라는 2가지 지표가 클러스터를 정의하는데 사용되기 때문에 각각의 정의들을 살펴보겠습니다.

local density($\eta_i$) : 샘플 j주변에 있는 샘플의 개수를 나타냅니다. 이는 반경 $t_r$ 내에 있는 이웃 샘플 수로 정의됩니다.

$\eta_j = \sum_{k \in S, k \neq j} \Omega(d(j, k) - t_r),$

$d(j,k)$ : 샘플 j와 k간의 거리

$t_r$ : 샘플 주변의 밀도를 결정하기 위한 임계값

$\Omega(y) =\begin{cases}1, & \text{if } y < 0, \\0, & \text{otherwise.}\end{cases}$

만약, 샘플 주변에 데이터가 많으면 $\Omega$값은 음수가 되므로 1을 출력하게 됩니다. 즉, 주변에 데이터가 많을수록 $\eta$값이 커집니다. (보통 클러스터 중심 주변에 데이터가 많이 모이게 되죠! 그러니까 $\eta$가 크다는 건 클러스터의 중심일수도 있다는 것입니다!)

최소 거리($\mu_j$) :더 높은 local density를 가진 샘플들로부터의 최소 거리를 계산합니다. 단, local density가 가장 높은 샘플의 경우, 이는 다른 모든 샘플로부터의 최대 거리로 정의됩니다.

$\mu_j = \begin{cases} \max \{d(j, k) \mid k \in S\}, & \text{if } \eta_j \geq \eta_k \text{ for all } k \in S, \\\min \{d(j, k) \mid \eta_j < \eta_k, k \in S\}, & \text{otherwise}.\end{cases}$

위 과정을 통해 각 데이터 포인트에 대해 $\eta_j$, $\mu_j$를 각각 구하여 클러스터의 중심을 결정합니다.

클러스터 중심

각 샘플의 Density와 Distance를 결합하여 새로운 값 $\lambda_j$를 계산합니다.($\lambda_j=\mu_j*\eta_j$)

$\lambda_j$ 값을 내림차순으로 정렬하고, 높은$\lambda_j$ 값을 가진 샘플을 클러스터 중심으로 선택합니다.

클러스터 할당

클러스터 중심이 결정된 이후, 나머지 샘플들은 가장 가까운 클러스터로 할당되게 됩니다.

$\Psi_j = \begin{cases} j, & \text{if } \eta_j \geq \eta_k \text{ for all } k \in S, \\\arg\min \{d(j, k) \mid \eta_j < \eta_k\}, & \text{otherwise}.\end{cases}$

예를 들어 설명해보겠습니다.

위 사진은 $\eta_1=\eta_2=\eta_3=\eta_4$(1~4번까지 같은 density를 가지고, 5는 다른 Density를 가진다)라고 가정하겠습니다.

그렇게 되면 $\lambda$를 계산하기 위해 최소 거리 $\mu$를 계산해야 합니다.(2번,3번 다음의 포인트가 바로 저 네모난 박스라고 하고 거리를 계산하겠습니다. 저 네모난 두 박스는 1,2,3,4보다는 Density가 더 높음)

$\mu_1,\mu_2,\mu_3,\mu_4$를 위의 식에 대입해보면 초록색 선이 거리가 될 것입니다. 1,2,3,4에 대해서 계산해보면 대략 $\mu_1,\mu_4,\mu_2,\mu_3$ 이 순서로 클 것 같습니다.(최소 거리를 계산해야하기 때문에 1,4번은 거리가 멀고 2,3번은 가까운 것을 알 수 있습니다!)

클러스터의 중심을 계산하기 위해 $\lambda$를 계산하게 되면 $\lambda_5,\lambda_1,\lambda_4,\lambda_2,\lambda_3$이 순서로 될 것이고 아마도 더 많은 샘플에서 수행하게되면 클러스터의 중심인 1,3,5만 클러스터링이 될 것 입니다! 그리고 나서 나머지 샘플들은 1,3,5 클러스터에 더 가까운 곳으로 할당이 된다고 생각하시면 됩니다!

Proposed Peak-based Undersampling Algorithm

이제는 DPC 알고리즘을 살펴보았으니 이 알고리즘을 통해 어떻게 Undersampling을 수행했는지 살펴보도록 하겠습니다.

1. 다수 클래스 데이터에 DPC 알고리즘을 적용시켜 e개의 클러스터 생성
2. 각 클러스터의 중심에서 소수 클래스와의 거리와 밀도를 계산
3. 새로운 측정값 $H_i$를 사용하여 다수클래스에서 가장 효과적인 샘플을 선택
   1. $H_i​=u×dens_i​+v×dist_i​,\ \ \ \ \ where \ \ \ \ \ u+v=1$
      1. $dens_i = \sum_{j \in \text{cluster}_i} \eta_j$
      2. $dist_i = \sum_{q \in \text{minclass}} d(p, q)$ $p : centroid\ of\ cluster_i$
4. $H_i$값이 높은 샘플 중 서로 너무 가깝지 않은 샘플을 선택합니다.
   1. 선택 기준은 $L = \{ x_i \mid x_i, x_j \in H \text{ and } d(x_i, x_j) > \theta \}$
5. 선택된 샘플과 Minority class data를 병합해 수정된 데이터셋을 생성합니다. 이 데이터는 여전히 불균형 하지만, 원본 데이터보다는 불균형 비율이 낮습니다.(아마 분류기를 계속 학습하면서 불균형이 완화될 것이라 보입니다.)

Proposed OUBoost Algorithm

이제 저자가 제안한 OUBoost 알고리즘의 전체 흐름을 살펴보겠습니다. 위에는 Undersampling을 위한 방법론을 소개했지만, OUBoost는 소수 클래스를 SMOTE를 사용해 데이터 생성하기 때문에 두 기법을 결합하여 알고리즘이 어떻게 진행되는지 살펴보겠습니다!

1. 데이터셋 분리 및 오버샘플링
   1. 원본 데이터셋 S를 소수 클래스와 다수 클래스로 나눕니다.
   2. SMOTE를 사용하여 소수 클래스에서 합성 데이터를 생성하고 이를 원본 데이터셋에 추가합니다.
2. 다수 클래스 언더샘플링
   1. 제안된 Peak 기반 언더샘플링 알고리즘을 사용하여 다수 클래스에서 샘플을 선택합니다.
3. 임시 데이터셋 생성
   1. 소수 클래스의 모든 샘플과 다수 클래스에서 선택된 샘플을 결합하여 새로운 임시 데이터셋 $S'_t$을 만듭니다.
   2. 이 데이터셋은 각 부스팅 단계에서 약한 학습기(weak learner)를 훈련하는 데 사용됩니다.
   3. 이때 불균형 비율이 되도록 임시 데이터셋 생성(불균형 비율은 우리가 선택할 수 있음)
      1. 만약 불균형 비율이 2:1이라고 하면, 생성된 소수 클래스의 데이터 수와 제거되고 남은 다수 클래스 데이터 수의 비율이 2:1이 되도록 데이터 정제
4. 가중치 업데이트 및 반복
   1. 각 단계에서 약한 학습기의 예측 오류율 $\epsilon_t$을 계산합니다.
   2. 오류율을 기반으로 가중치 업데이트 매개변수 $\alpha_t$를 계산 $\alpha_t=\frac{\epsilon_t}{1-\epsilon_t}$
   3. 데이터셋 S의 각 샘플에 대해 가중치를 업데이트하고 정규화합니다.
5. 최종 모델 생성
   1. T번의 반복 후, 최종 모델은 각 약한 학습기의 투표 결과를 기반으로 결정됩니다
      1. $H(x) = \arg\max_{y \in Y} \sum_{t=1}^{T} h_t(x, y) \log \frac{1}{\alpha_t}$

Results

위 그림은 OUBoost 과정이 진행되면서 데이터 생성, 제거 과정을 표현한 그림입니다. (빨간색 : 다수 클래스, 파란색 : 소수 클래스)

실제 불균형 데이터에 대해서 OUBoost를 적용한 모델과 다른 모델들에 대해서 F-score를 비교해보았습니다. 대부분의 경우 OUBoost의 성능이 우수한 것을 볼 수 있었습니다.

불균형 상황에서 잘 분류할 수 있다는 것은 큰 강점인 것 같습니다. 제조, 금융, 의료업에서는 아주 도움이 되는 모델이라고 느꼈습니다.

감사합니다.

참고문헌

1. OUBoost : https://link.springer.com/article/10.1007/s13042-023-01839-0