Median은 주어진 값들의 중간에 해당하는 값을 의미한다. 1차원 데이터가 주어졌을 때 median은 주어진 데이터를 크기 순서로 정렬을 한 후 중간에 해당하는 값을 취하면 된다. 데이터를 1차원 직선 위에 한 점으로 대응시킬 때 median을 찾는 것은 각 점으로부터 거리의 합이 최소인 데이터 위치를 찾으면 된다. 즉 1차원 median 찾기는
$$ C(y)= \sum _i | x_i - y|$$
로 정의되는 비용함수 $C(y)$를 최소로 만드는 $y$를 주어진 데이터 속에서 찾는 것으로 바뀐다.
증명: \begin{align} C (y) = \sum _{x_i < y} (y- x_i)+ \sum _{x_i > y} (x_i -y ) \\ \to ~~~\frac{dC}{dy} = \sum_{x_i < y} 1 - \sum _{x_i > y} 1=0 \end{align}
이어야 하므로 $y=\text{median}\{ x_i \}$임을 알 수 있다.
2차원 이상의 다차원 공간에서도 이 비용함수를 확장하면 다차원 공간에 분포하는 점들의 기하학적인 median을 정의할 수 있다.
$$ \text{median}( \{ \vec{x}_i\}) = \underset{y}{\text{argmin}} \sum _{i} || \vec{x}_i - \vec{y}||$$
1차원의 경우는 점들을 크기 순서대로 정렬을 하여 구할 수 있지만, 2차원 이상일 때 닫힌 해는 존재하지 않고, 반복적인 반복을 써서 구할 수 있음이 알려져 있다( Weiszfeld Algorithm). 이는 비용함수에 경사강하법(gradient descent method)을 적용한 알고리즘으로 볼 수 있다. 주어진 단계에서 근사적인 median이 $\vec{y}_{(t)}$일 때 다음 단계에서는 median update 식은
$$ \vec{y}_{(t+1)} = \frac{\sum_i w_i \vec{x}_i }{ \sum_i w_i}, \quad w_i = || \vec{x}_i - \vec{y}_{(t)}|| $$
로 계산한다. 이는 비용함수의 극소를 찾기 위해서 경사강하법을 적용할 때 step size (또는 learning rate)을
$$ \vec{y}_{(t+1)}= \vec{y}_{(t)} - \lambda \nabla C \\ \lambda = \frac{1}{\sum_i w_i} $$
로 선택한 결과이다. Weiszfeld algorithm에서는 강하 방향과 step size가 닫힌 형태로 계산되므로 일반적인 경사강하 알고리즘보다도 더 빠르게 근사해를 찾을 수 있다.
'Mathematics' 카테고리의 다른 글
Fermat Point (0) | 2024.07.12 |
---|---|
Basel Problem (0) | 2024.07.10 |
삼각형 내부에 외접원의 중심이 포함될 확률은? (1) | 2024.06.03 |
The Double Bubble Theorem (0) | 2024.05.27 |
Fourier Interpolation (0) | 2024.03.20 |