교사학습에서 imbalanced learning은 정(positive) 학습 샘플과 부(negative) 학습 샘플 수가 비슷하지 않거나 한 쪽의 수가 다른 쪽의 수보다 아주 작을 때 발생한다.
보통, negative 샘플 수는 아주 많고, positive 샘플 수는 상대적으로 작은 경우가 많다.
m개의 샘플을 가진 학습 데이터 집합을 S라 하자.
|S| = m.
이 때, S={(xi,yi)}, i=1,...,m이고 샘플 벡터 xi는 n차원의 특징 공간 X에 속한다.
X={f1,f2,...,fn}
즉, xi는 n개의 특징값을 가진 벡터이다. yi는 Y에 속하는데 Y={1,...,C}이다. 여기서, C는 xi에 대한 class label이다. C=2인 경우는 binary 분류 문제이다.
Imbalanced data에서 S는 두개의 부분 집합으로 나눌 수 있는데 Smin은 샘플 수가 작은(minority) 클래스의 샘플 집합이고, Smaj는 샘플 수가 큰(majority) 클래스의 샘플 집합이다. Smin과 Smaj의 교집합은 공집합이고, 합집합은 전체집합 S이다.
정, 부 샘플 수의 균형을 마추기 위해 샘플 수가 부족한 클래스에 합성 샘플(synthetic example)을 생성하여 샘플 수를 증가시키는 전략을 살펴보자.
SMOTE
SMOTE(synthetic minority oversampling technique)는 여러 응용분야에서 성공적인 결과를 보여준 방법이다.
Smin에 속하는 어떤 샘플 xi에 대해 K-NN(Nearest Neighbors)인 Smin 내의 샘플을 생각하자. K-NN은 기준 샘플 xi에 대해 xi에 가장 가까운 거리를 가진 K개의 샘플을 말한다. K는 어떤 정수 값이고, 메트릭은 특징 공간에서 euclidian거리이다.
합성 샘플을 만들기 위해 K-NN 중에서 한 샘플을 랜덤하게 선택한다. 합성 샘플은 다음과 같이 계산한다.
xnew = xi + (xi_h - xi) * delta
여기서 xi는 Smin에 속하는 기준 샘플이고 xi_h는 xi에 대한 K-NN의 하나이다. xi_h또한 Smin에 속한다. delta는 0과 1사이의 랜덤 수이다.
그림에서 원은 negative, 별은 positive샘플이다. 그림 (a)를 보면 기준 샘플 xi에 대해 가장 가까운 샘플 6개(K-NN)가 선택되었다. 이 중에서 임의로 선택된 샘플이 xi_h(hat of xi)이고, 위 수식에 따라 xi와 xi_h을 연결하는 직선 위에 존재하는 합성 샘플이 하나 추가 된다.
Borderline-SMOTE
SMOTE에서는 과도하게 발생하는 일반화(over generalization) 문제가 있다. 즉, SMOTE는 주변 샘플에 대한 고려 없이 Smin에 속하는 모든 개별 샘플에 대해 동일한 방법으로 합성 데이터를 생성시킨다. 이는 부류들 사이에서 중첩 발생(overlapping occurrence)를 증가시킨다.
Borderline-SMOTE는 이러한 문제점을 해결하기 위해 제안된 적응 샘플링 기법(adaptive sampling method)이다.
먼저, 각각의 Smin에 속하는 xi에 대해 m-NN을 구한다. 단, SMOTE와의 차이는 m-NN을 구할 때, Smin에 속하는 주변 샘플이 아니라 Smin, Smaj를 가리지 않고 가까운 m-NN을 구한다.
다음, m-NN 중에서 Smaj에 속하는 샘플의 수를 확인한다. 이 수를 Nh라고 하자.
최종으로, Nh가 m/2보다 크거나 같고 m보다 작은 조건을 만족하는 xi를 선택한다.
이러한 방법은 위 그림에서 보듯이, Smin보다 Smaj에 속하는 이웃을 더 많이 가진 xi가 선택되게 한다. 위 그림에서 DANGER set에 해당한다.
DANGET set에 속하는 샘플은 SMOTE 알고리즘에 의해 합성 샘플을 생성한다.
만일 m-NN의 모두가 Smaj라면 (즉, 위 그림에서 C에 해당한다), xi는 노이즈로 취급되고, 합성데이터는 발생되지 않는다.
Borderline-SMOTE는 SMOTE에 비해 경계(borderline)에 더 가까운 Smin의 샘플에서 합성 데이터를 생성시키는 효과가 있다.
ADASYN
ADASYN(adaptive synthetic sampling)도 SMOTE의 문제를 해결하기 위해 제안된 적응형 방법의 하나이다.
ADASYN은 주위 데이터의 분포에 따라 발생시킬 합성 데이터의 수를 좀 더 체계적으로 조절하는 방법이다.
먼저, Smin에 대해 발생할 합성 데이터의 수를 계산한다:
G = (|Smaj| - |Smin|) * beta
여기서 beta는 0과 1사이의 값으로 합성 데이터를 생성한 후에, 두 그룹간의 데이터 수의 균형을 정하기 위해 사용된다.
다음, Smin에 속하는 각 샘플 xi에 대해 euclidean거리에 따라 K-NN을 찾고, Gama(i)를 계산한다:
Gama(i) = (delta(i)/K) / Z, i=1,...,|Smin|
여기서 delta(i)는 xi의 K-NN 중에서 Smaj에 속하는 샘플의 수이다. Z는 Gama(i)가 p.d.f(probability density function)가 되도록 하는 정규화 상수(Sigma(Gama(i)) = 1)이다.
다음, Smin에 속하는 각각의 xi에 대해 발생될 필요가 있는 합성 데이터 샘플의 수를 결정한다.
g(i) = Gama(i) * G.
최종적으로, 각각의 xi에 대해 SMOTE에 따라 g(i)개의 합성 데이터를 생성한다.
위 식에서 delta(i)가 크면 많은 데이터를 발생 시킨다. 즉 Smaj에 속하는 샘플의 수가 많은 xi가 많은 데이터를 발생시킨다.
ADYSYN의 주요 아이디어는 합성 데이터의 수를 자동적으로 결정하기 위한 표준으로 p.d.f인 Gama를 사용하는 것이다.
참고 논문
[1] Haibo He, et. al., Learning from Imbalanced data, IEEE Trans. Knowledge and data Eng., 21(9), 2009
[2] N.V. Chawla, et. al., SMOTE: Synthetic Minority Over-Sampling Technique, J. Artificial Intelligence Research, 16, 2002.
[3] H. Han, et.al., Borderline-SMOTE: A New Over-Sampling Method in Imbalanced Data Sets Learning, Proc. ICIC, 2005.
[4] H. He, et. al., ADASYN: Adaptive Synthetic Sampling Approach for Imbalanced Learning, Proc. Int. J. Comf. Neural Networks, 2008.
댓글 없음:
댓글 쓰기