직선거리와 경로 거리
반지름 1인 위쪽 반원에 각도 0,45,90,135,180도인 다섯 점을 놓자. 양 끝점의 직선거리는 2이다. 거리 1 이하인 점끼리만 연결하면 이웃한 점들만 이어진다. 각 연결 길이는 √(2-√2)이므로 양 끝을 잇는 그래프 경로는 약 3.061이다. 실제 반원의 호 길이 π와도 정확히 같지는 않다. 이 예제는 표본 그래프가 곡선을 따라가는 거리를 근사하는 모습을 보여 준다.
계산의 흐름
먼저 이웃 수나 거리 범위를 정해 그래프를 만들고 연결에 거리 가중치를 준다. 다음으로 표본 쌍 사이의 최단 경로 거리를 계산한다. 그 거리 관계로부터 저차원 좌표를 구하는 단계가 이어진다. 자료가 놓인 구조의 거리를 그래프 경로가 잘 근사한다는 가정이 중요하며, 좌표를 줄이는 것만으로 그 가정이 성립하지는 않는다.
이웃 범위의 영향
연결 범위가 너무 작으면 그래프가 여러 부분으로 끊겨 서로의 경로 거리를 정하기 어려워질 수 있다. 너무 크면 곡면을 따라가는 대신 서로 멀리 떨어진 부분 사이에 지름길이 생길 수 있다. 위 반원 예제에서도 모든 점을 직접 연결하면 양 끝의 최단 경로는 다시 2가 된다. 표본 밀도와 잡음에 따라 적절한 연결 범위가 달라진다.
결과의 검증
저차원 그림이 자연스럽게 보인다는 이유만으로 실제 잠재 구조를 복원했다고 판단할 수는 없다. 이웃 설정과 차원을 바꿨을 때 결과가 얼마나 달라지는지 확인한다. 표본 쌍의 거리 행렬과 최단 경로 계산은 자료가 커질수록 부담이 될 수 있다. 주성분 분석이나 다차원 척도법 등과 비교하되 무엇을 보존하려는 방법인지 구분해야 한다.
관련 문서
다차원 척도법 / 차원 축소 / 최단 경로 / 다익스트라 알고리즘 / 플로이드 워셜 알고리즘 / 유클리드 거리 / 주성분 분석