데이터 클러스터링을 위한 최적의 그래프 이론적 접근: 이론 및 이미지 분할에의 적용

데이터 클러스터링을 위한 새로운 그래프 이론적 접근법이 제시되고, 이미지 분할 문제에의 적용이 보여집니다. 클러스터링될 데이터는 연결된 정점 간의 유사성을 반영하기 위해 용량이 할당된 비방향 인접 그래프 G로 표현됩니다. 클러스터링은 G의 아크를 제거하여 최대 이질 서브그래프의 최대 흐름을 최소화하는 상호 배타적 서브그래프를 형성함으로써 달성됩니다. 중간 크기(약 2000 정점)의 그래프에 대해서는 G의 흐름과 절단에 동등한 트리를 분할하여 최적의 해를 얻으며, 이를 Gomory-Hu 알고리즘(1961)을 사용하여 효율적으로 구축할 수 있습니다. 하지만 더 큰 그래프에 대해서는 이 방법이 비현실적입니다. 서브그래프 응축에 대한 새로운 정리가 도출되고, 이를 사용하여 훨씬 줄어든 크기의 부분적으로 동등한 트리를 계층적으로 구성하고 분할하는 빠른 알고리즘이 개발됩니다. 이 알고리즘은 완전 동등한 트리를 분할하여 얻은 것과 동등한 최적의 해를 제공하며, 수십만 개의 정점을 가진 매우 큰 그래프를 처리할 수 있습니다. 새로운 클러스터링 알고리즘은 이미지 분할 문제에 적용됩니다. 분할은 주로 강한 엣지로 구성된 엣지 요소의 폐쇄 윤곽선을 효과적으로 검색함으로써 달성되며, 고립된 강한 엣지를 포함하는 윤곽선은 거부됩니다. 이 방법은 지역 경계를 정확하게 찾을 수 있으며 동시에 폐쇄된 엣지 윤곽의 형성을 보장합니다.