Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
이 논문은 클라인버그의 불가능성 정리(Kleinberg's Impossibility Theorem)에 의해 제약을 받는 평면 클러스터링과 달리, 계층적 클러스터링은 그 다양성에도 불구하고 공통된 구조적 중추를 공유하는 셀 수 없이 많은 허용 가능한 방법들의 존재를 통해 풍부성(richness), 일관성(consistency), 척도 불변성(scale invariance)의 공리들을 동시에 만족할 수 있음을 입증한다.
원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기
데이터 과학의 세계에는 클러스터링(clustering)이라 불리는 근본적인 작업이 있습니다. 과일 섞임, 사람들의 집단, 혹은 문서 세트와 같은 아이템들의 모임을 상상해 보십시오. 여러분은 이 아이템들을 서로 얼마나 유사한지에 따라 의미 있는 그룹으로 분류하고자 합니다. 여러분에게는 어떤 사과가 어느 것인지 알려주는 라벨이 없습니다. 단지 각 아이템이 다른 모든 아이템과 얼마나 다른지를 측정하는 척도만을 가지고 있을 뿐입니다. 목표는 데이터가 스스로 말하게 하여 그 안에 숨겨진 구조를 드러내는 것입니다. 수십 년 동안 연구자들은 이 분류 작업을 수행하는 완벽한 방법을 정의하기 위해 노력해 왔습니다. 그들은 좋은 분류 방법이라면 마땅히 따라야 할 일련의 기본 규칙들을 제안했습니다. 한 가지 규칙은 그 방법이 측정 단위에 구애받지 않아야 한다는 것입니다. 거리를 미터로 측정하든 마일로 측정하든, 그룹은 동일하게 유지되어야 합니다. 또 다른 규칙은 그 방법이 데이터가 적절하다면 어떤 가능한 그룹화도 찾아낼 수 있을 만큼 충분히 유연해야 한다는 것입니다. 세 번째 규칙은 만약 그룹 내의 아이템들이 서로 더 유사해지고 그룹 간의 아이템들이 서로 더 달라진다면, 그 방법이 갑자기 그 그룹을 해체하기로 결정해서는 안 된다는 것입니다.
오랫동안, 단 하나의 방법이 이 세 가지 규칙을 동시에 만족시킬 수는 없다고 믿어져 왔습니다. 이 분야의 유명한 결과는, 만약 여러분이 데이터를 단 하나의 평평한 층의 그룹으로만 나누어야 한다면—마치 카드 한 덱을 단 하나의 무더기로 분류하는 것처럼—결국 한 가지 규칙을 어기게 될 것이라는 점을 보여주었습니다. 데이터의 척도를 무시하거나, 유효한 특정 그룹화를 무시하거나, 혹은 데이터가 약간 변했을 때 불안정해질 수밖에 없습니다. 이는 마치 데이터를 평평한 그룹으로 분류하는 것의 본질 자체가 결함이 있는 것처럼 느껴지게 하여, 일종의 한계 의식을 만들어냈습니다. 하지만 만약 해결책이 데이터를 단 하나의 층으로 강제하는 것이 아니라, 데이터가 나무(tree) 형태로 펼쳐지도록 두는 것이라면 어떨까요? 만약 단순히 "이것들이 그룹이다"라고 말하는 대신, "이것들이 그룹이고, 그 그룹 안에는 더 작은 그룹들이 있으며, 그 안에는 또 더 작은 것들이 있다"라고 말할 수 있다면 어떨까요? 이것이 계층적 클러스터링(hierarchical clustering)의 개념이며, 여기서의 출력값은 평평한 목록이 아닌 중첩된 구조가 됩니다.
스위스 연방 공과대학교(EPFL)와 프랑스 구스타프 에펠 대학교의 연구진은 이 계층적 접근 방식이 모든 것을 바꾼다는 것을 이제 보여주었습니다. 그들은 평평한 클러스터링을 불가능하게 만들었던 세 가지 엄격한 규칙을 가져와서, 출력이 계층 구조라면 이 규칙들을 만족할 수 있는지 물었습니다. 답은 확고한 '예'였습니다. 그들은 이 세 가지 규칙을 동시에 만족시키는 방법이 단 하나가 아니라, 셀 수 없이 많다는 것을 증und히 입증했습니다. 실제로 그들은 이러한 유효한 방법들의 공간이 믿기 힘들 정도로 방대하고 다양하다는 것을 발견했습니다. 그 공간은 너무나 커서 그 목록을 다 나열할 수도 없으며, 이 광대한 집합 안에는 근본적으로 서로 양립할 수 없는 많은 방법이 존재합니다. 여러분은 모든 것을 완벽하게 수행하는 단 하나의 "최고의" 방법을 단순히 고를 수 없습니다. 왜냐하면 모든 다른 방법들을 정교하게 다듬어내는 궁극적인 승자로서의 단일 방법은 존재하지 않기 때문입니다.
연구진은 단순히 이러한 방법들이 존재한다는 것을 증명하는 데 그치지 않고, 그것들이 어떻게 작동하는지 보여주기 위해 여러 가지를 직접 구축했습니다. 그들은 가장 가까운 두 아이템을 먼저 병합하는 방식과 같은 일반적인 데이터 분류 방식들을 살펴보았습니다. 그들은 두 개 이상의 그룹이 똑같이 가까울 때 한꺼번에 병합하는 것을 허용하는 특정 버전의 이 방식이 완벽하게 작동한다는 것을 발견했습니다. 또한 그들은 그룹 간의 분리 정도를 기반으로 한 새로운 방법들을 발명했습니다. 한 방법은 그룹 내부의 아이템들이 외부의 그 무엇보다 훨씬 더 가까운 경우를 찾습니다. 또 다른 방법은 약간 다른 종류의 분리도를 찾습니다. 그들은 이 방법들이 모두 유효하면서도 서로 다른 결과를 낸다는 것을 보여주었습니다. 어떤 방법들은 매우 엄격하여 가장 명확하고 잘 분리된 그룹만을 찾아냅니다. 반면 어떤 방법들은 더 관대하여 더 미묘한 연결 관계들을 찾아냅니다.
이러한 엄청난 다양성에도 불구하고, 연구진은 숨겨진 질서를 발견했습니다. 방법들이 세부적인 사항에서는 의견이 다를지라도, 그들은 가장 명확하고 잘 분리된 구조에 대해서는 모두 동의합니다. 어떤 두 유효한 방법을 가져와서 그들이 공통적으로 동의하는 그룹을 살펴본다면, 여러분은 매우 뚜렷하고 구별되는 클러스터들로 이루어진 공통된 뼈대를 발견하게 될 것입니다. 이는 방법들이 데이터의 복잡하고 모호한 중간 지대를 처리하는 방식은 다를 수 있지만, 모두 동일한 견고한 토대를 존중한다는 것을 의미합니다. 연구진은 또한 네 번째 규칙, 즉 만약 데이터에 이미 완벽한 나무 형태의 구조가 내재되어 있다면 그 방법이 정확히 그 나무를 찾아내야 한다는 규칙을 추가했을 때 어떤 일이 일어나는지 탐구했습니다. 이 더 엄격한 요구 조건 하에서도 방법들의 방대한 다양성은 유지되지만, 이제는 다른 모든 방법의 출발점이 되는 단 하나의 가장 거친(coarsest) 방법이 존재하게 됩니다.
이 연구는 우리가 데이터를 조직하는 방식에 대한 이해를 재편합니다. 이는 우리가 원하는 모든 것을 만족시키는 분류 방법을 만드는 것이 불가능한 이유가 우주의 근본적인 결함 때문이 아니라, 데이터를 단 하나의 평평한 층으로 강제하려는 제한 때문임을 보여줍니다. 데이터를 중첩된 그룹의 이야기로 풀어내게 함으로써, 우리는 두 마리 토끼를 모두 잡을 수 있습니다. 우리는 척도 불변성을 가지면서도, 유연하고, 안정적인 방법을 동시에 가질 수 있습니다. 연구진은 또한 이러한 방법들이 단위 변경이나 숫자 변환과 같은 일반적인 전처리 방식에 대해 얼마나 강건한지(robust)를 보여주었습니다. 이는 이 프레임워크가 단순한 수학적 호기심이 아니라, 실제 환경의 파이프라인에서 사용될 수 있는 실용적인 도구임을 시사합니다. 이 연구는 세상의 다양한 측면을 보여주면서도, 가장 중요한 특징들에 대해서는 모두가 동의하는, 수많은 유효한 분류 방식들로 가득 찬 풍경을 우리에게 제시합니다.
연구 분야의 논문에 파묻히고 계신가요?
연구 키워드에 맞는 최신 논문의 일일 다이제스트를 받아보세요 — 기술 요약 포함, 당신의 언어로.