기계학습에서 Data cleaning 기술

앞에서는 기계학습에서 발생하는 imbalanced data 문제를 해결하기 위해 여러가지의 샘플링 기반의 데이터 합성 기술을 살펴 보았다.
데이터를 합성하면 overlapping 문제가 생기는데, 이것은 정,부의 데이터들이 서로 뒤 섞여서 학습 성능을 저하시키는 것을 말한다.

따라서 Tomek link와 같은 데이터 삭제 기술을 적용하여 샘플링에 의한 합성 데이터로 생긴 overlapping을 제거할 수 있다.

Tomek link는 정의를 위해 샘플사이의 거리 값을 이용한다. 단, 서로 다른 부류가 연결된 것이며, 상호간의 최소 거리를 가진 두 샘플의 쌍(pair)을 말한다.
예를 들면, (xi, xj)의 쌍에 대해 xi는 Smin(minority of S)에 속하며, xj는 Smaj(majority of S)에 속한다.
또한 d(xi, xj)는 xi  xj사이의 거리이며, 만일 d(xi,xk)<d(xi,xj)이거나 d(xj,xk)<d(xi,xj)가 되는 샘플 xk가 없다면 이것을 Temek link라 부른다.

만일 어떤 두 샘플이 Tomek link를 형성한다면, 두 샘플의 어떤 하나는 노이즈이거나 둘 다가 부류의 경계근처에 있는 것으로 볼 수 있다.

따라서, 데이터 합성 후, 원치 않는 부류들 사이의 overlapping을 제거하기 위해 모든 Temek link를 찾아 제거한다.  제거 과정은 모든 최소 거리 연결 쌍이 같은 부류에 있을 때까지 계속된다.

overlapping 샘플들을 제거함에 의해 학습 샘플들은 잘 정의된 부류의 cluster를 얻을 수 있고, 이것은 결국 개선된 성능으로 나타난다.

그림 (a)는 overlapping이 있는 imbalanced된 원 데이터를 보여준다. 그림 (b)는 SMOTE에 의한 데이터 합성 후의 분포를 보여준다.  SMOTE에 의해 생긴 overlapping 증가가 나타난다.  그림 (c)에서 Tomek link는 점선 박스로 표시되고, 그림 (d)는 Tomek link를 제거한 결과를 보여준다.  잘 정의된 클래스의 cluster가 나타난다.



참고 논문

[1] Haibo He, et. al., Learning from Imbalanced data, IEEE Trans. Knowledge and data Eng., 21(9), 2009
[2] I, Tomek, Two modifications of CNN, IEEE Trans. System, Man, Cybernetics, 6(11), 1976.

기계학습에서 Imbalanced learning

교사학습(supervised learning)이란 학습 샘플과 이 샘플이 속하는 부류(class) 정보가 함께 주어질 때 수행하는 기계학습을 말한다.
교사학습에서 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.

Logistic regression 기반의 분류기

선형 회귀란 직선을 데이터에 정합하는 것이다.

분류에 회귀를 이용해 보자. 

기계학습 분야에서 적용은 라벨이 붙은 학습 데이터를 나누는 분류 직선(또는 평면)을 얻는 것이다. 

$f(z)={1 \over 1+exp(-z) }$

와 같은 함수가 있다.  $f$는 $z$가 음수로 증가하면 0이고 양수로 증가하면 1이 된다. 

샘플 데이터의 두 부류 라벨이 0과 1이라면 회귀 직선 $z$에 의한 $f(z)$ 값이 0과 1로 나오면 된다. 

직선(또는 고차공간에서 hyper-plane)은 파라메터 $w$와 샘플 특징 $x$의 곱으로

$z=w'x$

이다. $w$는 직선의 인자 값 벡터이고 $x$는 특징 벡터이다.

이 직선이 데이터를 잘 분류 하도록 $w$값을 정하는 문제를 최적화로 푼다. 

$f(z)$가 0과 1, 또는 그 사이 값이 되므로 확률과 유사하다. 

데이터 $(x_i,y_i)$가 주어진다면 $f(z)$는 $w$와 데이터의 함수이고 확률 형태 $p(w,x)=f(z)$으로 라벨 $y_i$와 함께 이용된다. 

목적함수는

$L(\omega)={\underset{i}{\prod}} p(\omega,x_i)^{y_i} (1-p(\omega, x_i))^{1-y_i}$

와 같다.  샘플이 주어지면 라벨 $y_i$(1 또는 0) 값에 따라 $L_i(w)$는 $f(z)$나 $1-f(z)$가 된다.
즉, $y_i=1$이면 $f(z)$는 1이 되면 되고, $y_i=0$이면 $f(z)$가 0이 되면 된다.   따라서 두 경우 모두 $f(z)$나 $1-f(z)$는 1이 되므로 $L(\omega)$는 최대화가 된다.

$\omega$를 구하는 식은

$\omega_{t+1}=\omega_t + \alpha \nabla L(\omega) = \omega_t + \alpha x (y-f(z))$

이다.  도함수를 구하는 식은 링크를 참고한다.