📊 statistics

Hierarchical Aggregation Clustering Algorithms Derived from the Bi-partial Objective Function

이 논문은 일반화된 이-부분적 (bi-partial) 목적 함수에서 유도된 최소 거리 병합 기반의 계층적 군집화 알고리즘의 구성 원리를 제시하여, 최적화와 계층적 군집화 알고리즘 간의 명시적이고 포괄적인 연결 고리를 확립함으로써 알고리즘의 이론적 근거를 강화하고 군집 품질 평가 및 병합 중단 기준을 마련합니다.

원저자: Jan W. Owsiński

게시일 2026-02-25

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Jan W. Owsiński

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

🎈 핵심 비유: "친구 모임을 만드는 두 가지 규칙"

데이터 분석에서 '클러스터링'은 비슷한 것끼리 묶는 작업입니다. 예를 들어, 파티에 온 100 명의 사람들을 비슷한 취향을 가진 그룹으로 나누는 상황을 상상해 보세요.

기존의 전통적인 방법 (계층적 군집화) 은 다음과 같이 작동합니다:

가장 가까운 두 사람을 먼저 짝을 짓습니다.
그 다음으로 가장 가까운 두 사람 (또는 그룹) 을 묶습니다.
이렇게 계속 묶어가다 보면, 결국 모든 사람이 한 큰 그룹이 될 때까지 **나무 모양의 다이어그램 (덴드로그램)**이 만들어집니다.

하지만 여기서 문제가 생깁니다.
이 나무 다이어그램이 완성되면, **"어디서 잘라야 진짜 의미 있는 그룹이 될까?"**를 결정하는 기준이 없습니다. 마치 "이 나무를 어디서 자를지 아무런 이유 없이 임의로 정하는" 것과 비슷합니다. 그래서 연구자는 "이 그룹이 정말 좋은가?"를 판단할 수 있는 명확한 나침반이 필요하다고 느낀 것입니다.

💡 이 논문이 제안하는 해결책: "두 가지 욕구를 동시에 만족시키는 저울"

저자는 **'이중 부분 목적 함수 (Bi-partial Objective Function)'**라는 개념을 소개합니다. 이를 쉽게 비유하자면, 두 가지 상반된 욕구를 동시에 저울질하는 도구입니다.

안쪽의 친밀감 (Similarity): 같은 그룹에 속한 사람들은 서로 매우 가까워야 합니다. (친구끼리는 서로 잘 어울려야 함)
바깥쪽의 거리감 (Distance): 다른 그룹에 속한 사람들은 서로 멀리 떨어져 있어야 합니다. (다른 팀끼리는 구분이 명확해야 함)

기존 방법들은 이 두 가지를 따로따로 생각하거나, 단순히 '가장 가까운 것'만 쫓았습니다. 하지만 이 논문은 **"이 두 가지를 하나의 공식으로 합쳐서, 언제 멈춰야 가장 완벽한 그룹이 되는지 계산해 내자"**고 말합니다.

🚀 어떻게 작동할까요? (단계별 설명)

이 논문은 다음과 같은 과정을 제안합니다:

시작: 모든 사람을 따로따로 놓습니다. (아직 그룹이 없음)
저울질: "누구를 묶으면 '안쪽 친밀감'은 늘고 '바깥 거리감'은 줄어들까?"를 계산합니다.
결정: 가장 좋은 조합을 찾아서 두 그룹을 합칩니다.
중요한 순간 (멈춤 신호): 이 과정을 반복하다 보면, 어느 시점에 **"이제 더 이상 묶으면 오히려 나빠진다"**는 신호가 나옵니다.
- 기존 방법들은 이 신호를 못 봤지만, 이 논문의 방법론은 수학적으로 "이제 여기서 멈추세요"라고 정확히 알려줍니다.

🌟 이 방법의 장점 (왜 중요한가?)

이유 있는 결정: "왜 여기서 그룹을 나눴지?"라고 물으면, "수학적으로 계산했을 때 이 지점이 가장 효율적이기 때문입니다"라고 명확히 답할 수 있습니다.
기존 알고리즘의 재발견: 우리가 이미 알고 있는 '단일 연결 (Single Linkage)', '완전 연결 (Complete Linkage)' 같은 유명한 방법들도 사실은 이 '이중 저울' 원리의 특별한 경우임을 증명했습니다. 즉, 기존 방법들이 왜 작동하는지 그 근본적인 이유를 밝혀낸 것입니다.
k-means 같은 방법에도 적용 가능: 유명한 'k-means' 알고리즘도 이 원리를 적용하면, "그룹을 몇 개로 나눌지"를 외부 기준 없이 스스로 결정할 수 있게 됩니다.

📝 요약

이 논문은 **"데이터를 그룹으로 묶을 때, 단순히 '가까운 것끼리'만 보는 게 아니라, '친밀함'과 '거리감'이라는 두 가지 가치를 저울에 올려놓고 가장 균형 잡힌 지점을 찾아내자"**는 아이디어를 제시합니다.

그 결과, 우리는 어디서 끊어야 할지 막연했던 기존 방법들에 명확한 '중단 신호'와 '품질 평가 기준'을 선물하게 되었습니다. 마치 안개 낀 길에서 나침반을 찾아낸 것과 같습니다.

1. 연구 배경 및 문제 제기 (Problem)

클러스터링의 본질적 문제: 클러스터링은 객체 집합을 내부적으로는 유사하고 (밀집), 외부적으로는 이질적인 (분리된) 하위 집합 (클러스터) 으로 분할하는 문제입니다. 그러나 구체적인 데이터에 대해 이 문제를 수학적으로 명확히 정의하고 해결하는 방법은 여전히 부족합니다.
기존 계층적 집계 알고리즘의 한계:
- 단일 연결 (Single linkage), 완전 연결 (Complete linkage), Ward 알고리즘 등 기존 계층적 알고리즘은 직관적이고 널리 사용되지만, 목적 함수 (Objective Function) 와의 명시적인 연결이 부재합니다.
- 이러한 알고리즘들은 주로 '최소 거리' 기반의 국소적 휴리스틱 (Greedy heuristic) 에 의존하며, 전체 분할 (Partition) 의 최적성을 보장하지 못합니다.
- 덴드로그램 (Dendrogram) 을 생성한 후, 적절한 클러스터 수를 결정하기 위해 외부 기준 (External criteria) 을 적용해야 하는 모호함이 존재합니다.
핵심 질문: 계층적 집계 알고리즘이 해결하려는 클러스터링 문제를 수학적으로 엄밀하게 표현하는 목적 함수는 무엇이며, 이 목적 함수로부터 알고리즘을 유도할 수 있는가?

2. 방법론 (Methodology)

저자는 이중 부분 목적 함수 (Bi-partial Objective Function) 개념을 도입하여 계층적 알고리즘과 최적화 문제를 연결합니다.

이중 부분 목적 함수의 정의:
- 클러스터링의 두 가지 핵심 목표인 '클러스터 내 유사성 극대화'와 '클러스터 간 거리 극대화'를 동시에 고려하는 목적 함수를 설계합니다.
- 일반화된 형태: $Q(P, r) = r \cdot Q_S(P) + (1-r) \cdot Q_D(P)$ $Q (P, r) = r \cdot Q_{S} (P) + (1 - r) \cdot Q_{D} (P)$
  - $P$ : 분할 (Partition)
  - $Q_S(P)$ : 클러스터 내 유사성 (Internal Similarity) 측정치
  - $Q_D(P)$ : 클러스터 간 거리 (Inter-cluster Distance) 측정치
  - $r \in [0, 1]$ : 두 목적 간의 가중치 파라미터
알고리즘 유도 과정:
1. 파라미터 $r$ 의 변화: $r=0$ (순수 거리 기반) 에서 시작하여 $r=1$ (순수 유사성 기반) 로 점진적으로 변화시킵니다.
2. 최적 분할의 전이: $r$ 이 증가함에 따라, 이전 분할 ( $P_{t-1}$ ) 보다 목적 함수 값을 개선하는 새로운 분할 ( $P_t$ ) 이 존재하는 임계값 $r_t$ 를 계산합니다.
3. 병합 규칙 (Merger Rule) 도출: 두 클러스터를 병합할 때 목적 함수가 개선되는 조건을 분석하여, 기존 계층적 알고리즘 (예: 평균 연결, Ward 등) 의 거리 업데이트 공식과 유사한 병합 기준을 유도합니다.
4. 그리디 하위 최적화 (Greedy Sub-optimization): 매 단계에서 $r_t$ 를 최소화하는 (또는 목적 함수 개선을 최대화하는) 클러스터 쌍을 선택하여 병합합니다. 이는 덴드로그램을 생성하는 과정과 일치합니다.
5. 종료 조건: $r=0.5$ (또는 목적 함수의 균형점) 에 도달하거나, 더 이상 개선이 없을 때 알고리즘을 종료합니다.

3. 주요 기여 (Key Contributions)

알고리즘과 목적 함수의 명시적 연결: 기존에 목적 함수와 무관하게 설계된 것으로 여겨졌던 계층적 집계 알고리즘들이, 실제로는 특정 형태의 이중 부분 목적 함수를 하위 최적화 (Sub-optimization) 하는 과정임을 수학적으로 증명했습니다.
알고리즘 유도 프레임워크 제시: 일반적인 목적 함수 형태에서 구체적인 병합 규칙 (Lance-Williams 공식 등) 을 유도하는 체계적인 방법을 제시했습니다.
정지 조건 및 품질 평가 기준 제공: 외부 기준 없이도 목적 함수 값 ( $Q(P,r)$ ) 을 기반으로 클러스터링의 품질을 평가하고, 덴드로그램을 언제 잘라야 할지 (클러스터 수 결정) 를 결정하는 내재적 기준을 마련했습니다.
다양한 사례 적용:
- 시설 입지 문제 (Facility Location): 클러스터 생성 비용과 거리 비용을 결합한 모델.
- 최소 거리/최대 유사성: 전통적인 클러스터링 정의에 기반한 모델.
- K-means 의 확장: K-means 알고리즘에 클러스터 간 유사성 항을 추가하여, 클러스터 수 ( $k$ ) 를 외부 기준 없이 자동으로 결정할 수 있는 이중 부분 K-means 모델을 제안했습니다.

4. 결과 및 실험 (Results)

이론적 검증: 유도된 병합 규칙이 기존 알고리즘 (평균 연결 등) 과 수학적으로 동치임을 보였습니다.
K-means 사례 연구:
- 학술용 데이터셋 (60 개 객체) 을 사용하여 이중 부분 목적 함수를 적용했습니다.
- 목적 함수 값 ( $Q_{DS}$ ) 을 클러스터 수 ( $p$ ) 에 따라 분석했을 때, $p=4$ 에서 명확한 최소값이 관찰되었습니다. 이는 데이터의 실제 구조와 일치하는 것으로 판단됩니다.
- 기존 K-means 가 외부 기준 (AIC, BIC 등) 없이 최적의 $k$ 를 찾기 어렵다는 점을 보완하여, 목적 함수 자체의 곡선 분석을 통해 최적의 클러스터 수를 식별 가능함을 입증했습니다.
중첩된 최적해 (Nested Partitions): 목적 함수 곡선을 통해 여러 단계의 준최적 (Quasi-optimal) 분할 구조를 시각화할 수 있음을 보였습니다.

5. 의의 및 결론 (Significance)

이론적 정당성 부여: 계층적 클러스터링 알고리즘이 단순한 휴리스틱이 아니라, 명확한 최적화 문제의 근사 해법임을 입증하여 알고리즘의 이론적 토대를 강화했습니다.
실용적 도구 제공: 클러스터링 결과의 품질을 평가하고, 최적의 클러스터 수를 결정하기 위해 외부 지표에 의존하지 않아도 되는 내재적 기준을 제공합니다.
유연성과 확장성: 이중 부분 목적 함수의 형태를 다양한 문제 (시설 입지, 퍼지 클러스터링 등) 에 맞게 수정하여 새로운 알고리즘을 설계할 수 있는 유연한 프레임워크를 제공합니다.
계산 효율성 고려: 대규모 데이터셋의 경우 순수 계층적 알고리즘의 계산 비용 문제를 해결하기 위해, K-means 와 같은 빠른 알고리즘으로 초기 군집을 형성한 후 이중 부분 규칙으로 병합하는 하이브리드 접근법을 제안했습니다.

요약하자면, 이 논문은 클러스터링의 핵심인 '분할' 문제를 목적 함수 최적화 관점에서 재정의하고, 이를 통해 기존 계층적 알고리즘의 작동 원리를 해석하고 개선하는 새로운 패러다임을 제시했습니다. 특히, 알고리즘의 정지 시점과 결과의 질을 평가하는 기준을 알고리즘 내부에서 도출했다는 점이 가장 큰 의의입니다.