기하중앙값

3. 특성

• 1차원 공간에서 기하 중앙값은 중앙값과 일치한다. 이는 1차원 중앙값 역시 각 점까지의 거리 합을 최소화하는 지점이기 때문이다. 다만, 점의 개수 ''n''이 홀수일 때는 정렬된 점들 중 정확히 가운데 위치한 점 $p\_\{(n+1)/2\}$이 기하 중앙값이 되지만, ''n''이 짝수일 때는 가운데 두 점 $p\_\{n/2\}$과 $p\_\{(n/2)+1\}$ 사이의 선분 위의 어떤 점도 기하 중앙값이 될 수 있어 유일하게 결정되지 않는다.
• 점들이 공선점이 아닌 경우, 기하 중앙값은 '''유일'''하게 결정된다.
• 기하 중앙값은 이동이나 회전과 같은 유클리드 닮음 변환에 대해 공변성을 가진다. 즉, 주어진 점들의 기하 중앙값을 구한 뒤 변환하거나, 점들을 먼저 변환한 뒤 기하 중앙값을 구해도 결과는 같다. 이는 기하 중앙값이 점들 사이의 거리에만 의존하며, 점들을 나타내는 직교 좌표계의 선택과는 무관하기 때문이다. 이와 달리, 다변량 데이터 집합에 대한 성분별 중앙값은 일반적으로 회전에 대해 불변하지 않으며 좌표계 선택에 따라 결과가 달라질 수 있다.
• 기하 중앙값의 파괴점은 0.5이다. 이는 전체 데이터 중 최대 절반까지의 점들이 임의의 값으로 손상될 수 있더라도, 기하 중앙값은 여전히 손상되지 않은 데이터 위치에 대한 강건 추정량을 제공할 수 있음을 의미한다.

4. 특수한 경우

점의 개수가 적은 몇 가지 특수한 경우 기하중앙값을 찾는 방법은 비교적 간단하다.

• '''3개의 점:''' 공선점이 아닌 세 점으로 이루어진 삼각형의 경우, 각도 조건에 따라 기하중앙값이 꼭짓점 중 하나가 되거나 삼각형 내부의 페르마 점이 된다.^[4] 세 점이 공선점이라면 중앙에 위치한 점이 기하중앙값이다.
• '''4개의 점:''' 공면점인 네 점의 경우, 점들의 배치에 따라 기하중앙값이 결정된다. 한 점이 나머지 세 점으로 이루어진 삼각형 내부에 있다면 그 점이 기하중앙값이고, 그렇지 않아 볼록 사변형을 이룬다면 대각선의 교점이 기하중앙값이 된다. 이는 네 점의 라돈 점과 같다.^[6]

4. 1. 3개의 점

• 삼각형의 한 각의 크기가 120° 이상이면, 기하중앙값은 바로 그 각의 꼭짓점이 된다.
• 만약 삼각형의 모든 각이 120°보다 작다면, 기하중앙값은 삼각형 내부에 위치한다. 이 점은 세 꼭짓점 각각의 쌍과 연결했을 때 이루는 각도가 모두 120°가 되는 특별한 점이다.^[10][4] 이 점을 삼각형의 페르마 점이라고 부른다.

4. 2. 4개의 점

5. 계산

기하 중앙값은 개념적으로 이해하기 쉽지만, 실제로 계산하는 것은 간단하지 않다. 각 점까지 거리의 제곱의 합을 최소화하는 무게 중심이나 질량 중심은 각 점의 좌표를 평균 내는 간단한 공식으로 구할 수 있다. 하지만 기하 중앙값의 경우, 일반적으로 명시적 공식이나 산술 연산과 ''k''제곱근만 사용하는 정확한 알고리즘은 존재하지 않는 것으로 알려져 있다. 따라서 이 계산 모델에서는 기하 중앙값에 대한 수치적 또는 기호적 근사만이 가능하다.^[7]

그러나 기하 중앙값의 근사값은 반복적인 절차를 통해 계산할 수 있다. 이러한 절차는 각 단계에서 더 정확한 근사값을 생성한다. 이 방법은 각 샘플 점까지의 거리가 볼록 함수이고, 볼록 함수의 합 역시 볼록 함수라는 성질을 이용한다. 따라서 각 단계에서 거리의 합을 줄여나가는 방식은 지역 최적해에 빠지지 않고 전역 최적해에 수렴할 수 있다.

이러한 접근 방식 중 대표적인 것은 '''Weiszfeld 알고리즘'''으로, 이는 Endre Weiszfeld의 연구^[8]에 기반하며 반복 재가중 최소 제곱 방법의 한 형태이다. 이 알고리즘은 현재 추정치 ''y''_''k''에서 각 샘플 점 ''x''_''i''까지의 거리에 반비례하는 가중치를 설정하고, 이 가중치를 적용한 샘플들의 가중 평균을 새로운 추정치 ''y''_''k''+1로 계산한다. 수식은 다음과 같다.

:$\backslash left.\; y\_\{k+1\}=\backslash left(\; \backslash sum\_\{i=1\}^m\; \backslash frac\{x\_i\}\{\backslash |\; x\_i\; -\; y\_k\; \backslash |\}\; \backslash right)\; \backslash right/\; \backslash left(\; \backslash sum\_\{i=1\}^m\; \backslash frac\{1\}\{\backslash |\; x\_i\; -\; y\_k\; \backslash |\}\; \backslash right).$

이 방법은 대부분의 초기 위치에서 수렴하지만, 추정치가 주어진 샘플 점 중 하나와 일치하게 되면 수렴하지 못할 수 있다. 이러한 경우를 처리하여 모든 초기점에 대해 수렴하도록 알고리즘을 수정할 수 있다.^[3]

Bose, Maheshwari, Morin은 2003년에 이 문제에 대한 근사 최적해를 찾는 더 정교한 기하학적 최적화 절차를 제시했다. Cohen, Lee, Miller, Pachocki는 2016년에 거의 선형 시간 안에 임의의 정밀도로 기하 중앙값을 계산하는 방법을 보여주었다.

또한, 기하 중앙값 문제는 2차 콘 프로그래밍 문제로 공식화될 수 있다.

:$\backslash underset\{y\; \backslash in\; \backslash mathbb\{R\}^n,\; \backslash \; s\; \backslash in\; \backslash mathbb\{R\}^m\}\{\backslash min\}\; \backslash \; \backslash sum\_\{i=1\}^m\; s\_i\; \backslash text\{\; subject\; to\; \}\; s\_i\; \backslash geq\; \backslash left\; \backslash |\; x\_i-y\; \backslash right\; \backslash |\_2\; \backslash text\{\; for\; \}\; i=1,\; \backslash ldots,\; m,$

이 문제는 일반적인 최적화 솔버를 사용하여 다항 시간 안에 해결할 수 있다.

6. 일반화

기하 중앙값은 유클리드 공간뿐만 아니라 더 일반적인 리만 다양체, 심지어 거리 공간으로까지 확장될 수 있다. 이는 리만 다양체에서 프레셰 평균을 정의할 때 사용하는 아이디어와 같다.^[9]

$M$을 거리 함수 $d(\backslash cdot,\; \backslash cdot)$를 갖는 리만 다양체라고 하자. $w\_1,\; \backslash ldots,\; w\_n$을 합이 1인 $n$개의 가중치라 하고, $x\_1,\; \backslash ldots,\; x\_n$을 $M$에서 관측된 $n$개의 값이라고 하자. 이때, 데이터 점들의 가중 기하 중앙값 $m$(또는 가중 프레셰 중앙값)은 다음 수식으로 정의된다.

: $m\; =\; \backslash underset\{x\; \backslash in\; M\}\{\backslash operatorname\{arg\backslash ,min\}\}\; \backslash sum\_\{i=1\}^n\; w\_i\; d(x,x\_i)$

만약 모든 가중치 $w\_i$가 같다면, $m$을 간단히 기하 중앙값이라고 부른다.

7. 같이 볼 문헌

• 메도이드
• 기하 중앙값 절대 편차

참조

_[1] 학술 Drezner, Klamroth, Schöbel, Wesolowsky, 2002
_[2] 서적 Geometric Methods and Optimization Problems Springer 1999
_[3] 학술 Vardi, Zhang, 2000
_[4] 학술 Haldane, 1948
_[5] 학술 Lopuhaä, Rousseeuw, 1991
_[6] 학술 Cieslik, 2006; Plastria, 2006
_[7] 학술 Bajaj, 1986; Bajaj, 1988
_[8] 학술 Weiszfeld, 1937; Kuhn, 1973; Chandrasekaran, Tamir, 1989
_[9] Conference Robust statistics on Riemannian manifolds via the geometric median https://ieeexplore.i[...] IEEE 2008-06-23
_[10] 학술 Haldane, 1948