단순심도

강력한 통계와 계산 기하학에서 단순화는 주어진 점을 포함하는 단순화에 의해 결정되는 중심적 경향의 척도다.유클리드 평면의 경우 주어진 점을 포함하는 표본 점의 삼각형 수를 카운트한다.

정의

$d{\displaystyle }$ ${\displaystyle d}$ -차원$$ 유클리드 공간에 있는$$ 점 $p{\displaystyle }${\$displaystyle$p}의 단순 깊이는 $p{\displaystyle }$ ${\displays$]를 포함하는 d {\$displaystyle{\displaystyle }$ d$}$차원 단순화(d + 1 {\$displaystyd+1}$ 샘플$$ 포인트 집합의 볼록한 선체)의 수입니다.$tyle p}$.무작위로 선택한 점$({\displaystyle \mathrm{d}}$+ 1 $)[\$디스플레이 $스타일(d+1)]$의 -tuple이$$ $p{\displaystyle }$ ${\displaystyle$p}을(를) 포함하는 볼록 선체를 가질 확률로 깊이를 정의함으로써 동일한 개념을 샘플 포인트 집합에서 주어진 경험적 분포가 아닌 평면의 점의 모든 확률 분포로 일반화할 수 있다$.$이 확률은 $p{\displaystyle }$ ${\dplaystyle$ p$}$을$($를) (${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{n}}{}}{\displaystyle }$d +${\displaystyle \genfrac{}{}{0ex}{}{1}{}}$)${\$ {n$}{d+$1}로$$나누어 p {\displaystyle p}을(를) 포함하는 단순화 수에서 계산할 수 있으며, 여기서$$ $n{\displaystyle }$ ${\displaystyn}$은 샘플 포인트 수입니다.^[L88][L90]

단순한 깊이의 표준 정의에 따르면 경계에 $p$ ${\displaystyle p}$이(가) 있는 단순성은 내부 내부에 p$$ ${\displaystyle p}$이(가) 있는 단순함과 동등하게 계산된다.이러한 정의의 일부 문제적 행동을 피하기 위해, Burr, Rafalin & Souvaine(2004)은 $경계$에 p ${\displaystyle p}$이(가) 있는$$ 단순화가 절반만 셀 수 있는 단순성의 수정 정의를 제안했다.마찬가지로, 이들의 정의는 $p{\displaystyle }$ ${\displaystyle p}$을(를) 포함하는 열린 단순화 수와 닫힌 단순화 수의 평균이다$.$^[BRS]

특성.

단순 깊이는 특이치에 대해 견고하다. 샘플 포인트 세트가 최대 깊이 포인트로 표현되는 경우, 대표 포인트의 위치를 크게 변경하지 않고 샘플 포인트의 일정한 부분까지 임의로 손상될 수 있다.그것은 또한 비행기의 부착 변형에도 불변한다.^[D][ZS][BRS]

그러나 단순화된 깊이는 중심 경향의 강력한 측정에 대해 바람직한 다른 특성을 갖지 못한다.중심 대칭 분포에 적용할 때 분포의 중심에 최대 깊이의 고유한 점이 있는 것은 아니다.그리고, 최대 깊이의 지점에서 광선을 따라, 단순한 깊이가 단조롭게 감소하는 것은 반드시 그런 경우는 아니다.^[ZS][BRS]

알고리즘

유클리드 평면에 있는$$ $n{\displaystyle }$ ${\displaystyle n}$ 샘플 포인트 집합(${\displaystyle }$ =${\displaystyle 2}${\$displaystyle d=2}$ )의 경우,$$ 다른 $포인트{\displaystyle }$ p ${\$$displaystyle p}$의 단순 깊이는 일부 계산 모델에서 최적 $시간{\displaystyle }$ O$($^{[KM][GSW][RR]}$n$ $⁡$ n${\displaystyle }$)로 $계산$할 수 있다$$.^[ACG]3차원에서 동일한 $문제$를 시간 O${\displaystyle ({}^{}}$ $){\displaystyle O(n^{2})$로 해결할 수 있다$.$^[CO]

어떤 차원에서도 조회당 거의 일정한 시간에 조회 지점의 단순 깊이를 근사할 수 있는 데이터 구조(시료 세트 또는 점 삽입을 진행 중인 샘플 세트)를 사용하여 데이터 구조를 구성할 수 있으며, 오류는 총 삼각형 수의 작은 부분인 근사치를 사용할 수 있다.견본대로^[BCE]2차원에서는 보다 정확한 근사 알고리즘이 알려져 있는데, 근사 오차는 단순 깊이 자체의 작은 배수다.또한 동일한 방법으로 인해 더 높은 차원의 빠른 근사 알고리즘이 구현된다.^[ASS]

Spherical depth, ${\displaystyle SphD(q;F)}$ is defined to be the probability that a point ${\displaystyle q}$ is contained inside a random closed hyperball obtained from a pair of points from ${\displaystyle F\in \mathbb {R} ^{n}}$. While the time complexity of most other data depths grows exponentially, the spherical depth grows only linearly in the dimension ${\displaystyle d}$ – the straightforward algorithm for computing the spherical depth takes ${\displaystyle O(dn^{2})}$. Simplicial depth (SD) is linearly bounded by spherical depth (${\displaystyle SphD\geq {\frac {2}{3}}SD}$).^[BS]

참조