logo

비에토리스-립스 컴플렉스의 정의 📂위상데이터분석

비에토리스-립스 컴플렉스의 정의

정의 1 2

쉬운 정의

유클리드 공간 $\left( \mathbb{R}^{d} , \left\| \cdot \right\|_{2} \right)$ 와 양수 $\varepsilon > 0$ 이 주어져 있다고 하자. 유한집합 $S \subset \mathbb{R}^{d}$ 에 대해 다음의 두 조건을 만족하는 심플리셜 컴플렉스 $\text{VR}_{\varepsilon} (S)$ 를 비에토리스-립스 컴플렉스vietoris-Rips Complex라 한다.

  • (i): $S$ 를 버텍스의 집합으로 가진다.
  • (ii): $k$-심플렉스 $\left[ v_{0} , v_{1} , \cdots, v_{k} \right]$ 가 $\text{VR}_{\varepsilon} (S)$ 에 속한다는 것은 모든 $0 \le i,j \le k$ 에 대해 다음이 성립하는 것과 동치다. $$ \left\| v_{i} - v_{j} \right\|_{2} \le 2 \varepsilon $$

어려운 정의

거리공간 $\left( X, d \right)$ 와 양수 $\varepsilon > 0$ 이 주어져 있다고 하자. 유한집합 $S \subset X$ 에 대해 다음과 같이 정의된 추상 심플리셜 컴플렉스 $\text{VR}_{\varepsilon} (S)$ 을 비에토리스-립스 컴플렉스vietoris-Rips Complex라 한다. $$ \text{VR}_{\varepsilon} (S) := \left\{ \sigma \subset S : \diam \sigma \le 2 \varepsilon \right\} $$ 여기서 $\diam$ 는 지름diameter로써, 다음과 같이 주어진 집합 $\sigma \subset X$ 의 모든 점끼리의 거리의 슈프리멈으로써 정의된다. $$ \diam \sigma := \sup_{x_{1} , x_{2} \in \sigma} d \left( x_{1} , x_{2} \right) $$

설명

비에토리스-립스 컴플렉스vietoris-Rips Complex는 가끔 줄여서 그냥 VR 컴플렉스립스 컴플렉스라 불리기도 한다.

조금 다르게 적히긴 했지만, 쉬운 정의가 되었든 어려운 정의가 되었든 핵심은 심플렉스가 되기 위한 조건이 거기에 포함된 모든 점들의 거리가 $2 \varepsilon$ 이하라는 것이다. 이를 그림으로 그려보면 다음과 같이 $0$-심플렉스인 버텍스들이 중심이고 반지름 $\varepsilon$ 인 볼들을 생각했을 때 두 볼끼리 닿는 것을 기준으로 $1$-심플렉스를 만들고, 세 버텍스가 $1$-심플렉스로 이어져 있으면 $2$-심플렉스를 만드는 식으로 VR 컴플렉스를 구성할 수 있다.

20220306_203242.png

비에토리스-립스 컴플렉스와 체흐 컴플렉스의 차이

비에토리스-립스 컴플렉스: $$\text{VR}_{\varepsilon} (S) := \left\{ \sigma \subset S : \diam \sigma \le 2 \varepsilon \right\}$$

체흐 컴플렉스: $$\check{C}_{\varepsilon} (S) := \left\{ \sigma \subset S : \bigcap_{x \in \sigma} B_{d} \left( x ; \varepsilon \right) \ne \emptyset \right\}$$

다음 그림은 같은 데이터에 대해 비에토리스-립스 컴플렉스와 체크 컴플렉스를 비교한 것이다. 위는 $\text{VR}_{\varepsilon}$, 아래는 $\check{C}_{\varepsilon}$ 다.

20220314_124807.png

  • 비에토리스-립스는 $k$-심플렉스를 포함하는 조건으로써 그 페이스face인 $k-1$-심플렉스가 존재하는 것만을 요구한다. 예시에서는 $1$-심플렉스인 $AB$, $BC$, $CA$ 가 존재하므로 $2$-심플렉스인 $ABC$ 가 포함된다.
  • 그에 반해 체흐 컴플렉스는 그 페이스들을 포함하는 것은 물론, $ABC$ 자체도 그 볼들이 한 점으로 묶여야만한다. 이는 체흐 컴플렉스를 구축하는 조건이 비에토리스-립스 컴플렉스를 구축하기보다 까다롭다는 것을 의미하며, 이에 따라 다음을 알 수 있다. $$ \check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon} $$ 더 나아가, 다음의 팩트가 알려져있다. $$ \check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon} \subset \check{C}_{2 \varepsilon} $$

정의로써 짐작할 수 있는 것은 아마도 체흐 컴플렉스가 비에토리스-립스 컴플렉스에 비해 조금 더 많은 정보를 가질 수 있다는 점이다. $\text{VR}_{\varepsilon}$ 은 $k \le n$ 개의 점이 주어졌을 때 이들이 서로 연결되어있기만 하면 얄짤없이 그 $k-1$-심플렉스가 존재한다고 말한다. 말하자면 심플렉스의 존재성과 그 모든 페이스들의 존재성 사이에 차이가 없다. 예로써 $2$-심플렉스인 $ABC$ 가 존재한다는 말이나 $1$-심플렉스인 $AB$, $BC$, $CA$ 가 존재한다는 말은 그냥 정확히 동치고, 조금 과감하게 말해서 둘 중 하나를 안다면 솔직히 나머지 하나는 무의미한 정보다. 반면 $\check{C}_{\varepsilon}$ 은 $AB$, $BC$, $CA$ 가 존재한다는 것만으로 $ABC$ 의 존재성을 장담할 수 없고 별도의 확인을 거쳐야한다. 이러한 점에서 체흐 컴플렉스는 비에토리스-립스 컴플렉스에 비해 데이터를 조금 더 디테일하게 바라보고 있는 것이라 기대할 수 있는 것이다.

한편 실제 계산의 측면에서는 비에토리스-립스 컴플렉스를 구축하는 계산 비용이 압도적으로 저렴하다. 그도 그럴 것이, 단순히 고정됨 점과 점 사이의 거리를 계산하는 $\text{VR}_{\varepsilon}$ 과 달리 $\check{C}_{\varepsilon}$ 은 점들의 볼들이 어디서 만나는지도 알 수 없으며 만난다고 할지라도 그것이 $\varepsilon$ 보다 긴지 짧은지 알 수가 없기 때문이다. 이를 극복하고 체흐 컴플렉스를 구축하기 위한 방법 중 하나로 벨츨 알고리즘 등으로 최소내포디스크를 찾는 방식을 고려해볼 수 있는데, 그 한 번 한 번의 계산들이 꽤 비싼데다가 그 비싼 계산을 가능한 모든 점의 조합에 대해 반복해야한다.


  1. Raul Rabadan. (2020). Topological Data Analysis for Genomics and Evolution: p126. ↩︎

  2. Edelsbrunner, Harer. (2010). Computational Topology An Introduction: p74. ↩︎