FOSC-X: 계층적 클러스터링으로부터 최적의 국소적 절단 및 비수평적 클러스터 선택을 위한 확장된 프레임워크

계층 구조(hierarchy)로부터 평면적인 클러스터링 솔루션(flat clustering solution)을 추출하는 것은 실제 클러스터 분석에서 흔히 발생하는 작업이며, 최적화 문제(optimisation problem)로 공식화될 수 있습니다. 기존의 접근 방식들은 단일 최적 솔루션을 찾는 데 집중합니다. 본 연구에서는 계층적 클러스터 트리(hierarchical cluster tree)의 국소적이고 비수평적인 절단(local, non-horizontal cuts)으로부터 상위 M개의 전역적으로 최적화된 평면 클러스터링(globally optimal flat clusterings)을 추출하는 프레임워크인 FOSC-X를 소개하며, 선택적으로 클러스터 수에 대한 제약 조건(constraints)을 적용할 수 있습니다. 이를 통해 계층 구조의 서로 다른 측면을 포착하는 여러 개의 고품질 대안 클러스터링을 자동으로 식별할 수 있습니다. 제약 조건이 없는 경우, 서브트리(subtrees) 내의 국소적으로 최적인 부분 후보(locally optimal partial candidates)들이 결합되어 클러스터 수를 자동으로 결정하면서 전역적으로 최적인 솔루션을 형성할 수 있다는 성질을 활용하여, 동적 계획법(dynamic programming)을 통해 다항 시간(polynomial time) 내에 상위 M개(top-M) 문제를 해결할 수 있습니다. 그러나 이는 결과적으로 바람직하지 않은 수의 클러스터를 가진 솔루션으로 이어질 수 있습니다. 예를 들어, 특정 응용 도메인 내에서 의미가 있거나 실질적으로 분석하기에는 너무 많은 수의 클러스터가 생성될 수 있습니다. 클러스터 수 제약을 부과하면, 국소적으로 최적인 부분 후보들이 더 이상 실행 가능한 전역 최적 솔루션으로 결합되지 않을 수 있기 때문에 제약 없는 동적 계획법 접근 방식의 근간이 되는 최적성 성질(optimality property)이 깨지게 됩니다. FOSC-X는 실행 불가능하거나 지배된 조합(dominated combinations)을 가지치기(pruning)하는 동시에, 하한 및 상한 실행 가능 경계(lower and upper feasibility bounds)를 사용하여 실행 가능한 후보들의 압축된 집합을 유지하는 동적 계획법 전략을 통해 이 문제를 해결합니다. 결과적으로 도출된 방법은 클러스터 수 제약 조건의 유무와 관계없이, 클러스터 노드 수와 데이터셋 크기에 대해 선형 시간 복잡도(linear-time complexity)로 상위 M개 솔루션의 최적 순위(optimal rankings)를 보장합니다. 실험을 통해 FOSC-X가 단일 솔루션 추출 방식에서는 간과되었던 대안적인 클러스터링 구조를 효율적으로 드러낸다는 것을 보여줍니다.