Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.48 No.3 pp.104-111
DOI : https://doi.org/10.11627/jksie.2025.48.3.104

Proposing a New Gap Statistic-Based Estimation for the Number of Clusters

Dang Ha Thanh Huong^*

, Jaekyung Yang^**†

^*MIS Department, Shinhan Viet Nam Finance Company Ltd.
^**Department of Industrial and Information Systems Engineering, Jeonbuk National University

^†Corresponding Author : jkyang@jbnu.ac.kr

Received 01/09/2025 Finally Revised 03/09/2025 Accepted 03/09/2025

Abstract

In the era of big data, where massive volumes of information are collected at high velocity from various sources, data mining has become a crucial tool for organizations seeking competitive advantage. Among its core tasks, clustering plays a key role in uncovering hidden patterns within unlabeled data by grouping similar objects into distinct clusters. Widely used methods such as k-means and its robust counterpart PAM (Partitioning Around Medoids) require the number of clusters, k, to be predefined—a task that remains a major challenge despite extensive research. This study addresses the problem of selecting the optimal number of clusters by proposing three novel enhancements to the widely-used gap statistic method: the 1stDaccSEmax heuristic rule, the recursive gap strategy, and the two-way bootstrapping technique. Collectively termed the new gap, this approach aims to overcome the limitations of the original gap statistic, particularly in datasets with overlapping clusters, hierarchical structures, or large volumes. Extensive experiments on both synthetic and real-world datasets—including Iris, Breast Cancer, Seeds, and Khan gene expression datasets—demonstrate that the new gap method outperforms traditional techniques such as the elbow method, silhouette analysis, and the original gap statistic in both accuracy and computational efficiency. Although PAM was used throughout the experiments for its robustness, the proposed approach is algorithm-agnostic and can be integrated with other clustering methods that require the selection of k. The results suggest that the new gap method provides a more reliable and scalable solution for determining the number of clusters, thereby enhancing the effectiveness of clustering-based data analysis in real-world applications.

Key Words : Clustering , Gap Statistic , Number of Clusters

갭 통계량을 이용한 군집 개수 추정 방법

당하탄후엉^*, 양재경^**†

^*신한베트남금융 MIS
^**전북대학교 산업정보시스템공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

군집분석(Clustering Analysis)은 가장 중요한 탐색적 데 이터 마이닝 작업 중 하나이다. 그 일반적인 목적은 데이 터셋 내에 존재하는 군집 구조를 발견하는 데 있다[4]. 군 집분석 문제를 서로 다른 방식으로 다룬 많은 수의 다양한 기법이 연구되어 왔다.

일반적으로 군집분석 기법은 데이터를 여러 그룹(즉, 군 집, 클러스터)으로 나누는 과정이며, 같은 군집 내의 객체 들은 서로 유사하고, 다른 군집에 속한 객체들과는 상이하 도록 구성된다[7].

군집분석은 라벨이 없는(즉 분류가 정해지지 않은) 데 이터를 사용하기 때문에 기계학습에서 비지도 학습 (Unsupervised Learning)에 속한다[8].

군집분석 기법은 데이터 객체들을 의미 있는 그룹으로 나누고, 객체 분포의 숨겨진 구조를 밝혀낼 수 있다. 이러 한 구조에서 도출된 통찰은 비즈니스 및 마케팅(예: 시장 세분화), 생물정보학(예: 식물과 동물의 생태, 인간 유전자 군집분석), 사회과학(예: 범죄 분석, 유형 분류) 등 다양한 분야에서 큰 가치를 창출할 수 있다.

그러나, 수십 년간 연구되어 왔음에도 불구하고, 군집분 석에는 여전히 많은 미해결 과제가 존재한다. 그 중 하나 는 바로 클러스터의 개수(k)를 어떻게 결정할 것인가 하는 문제이다. k는 대부분의 군집분석 기법에서 중요한 역할을 하며, 잘못된 k를 선택하면 완전히 다른 군집분석 결과가 나오게 된다. 이는 데이터의 내재된 구조에 대한 잘못된 해석을 유도하고, 실제 응용에서 심각한 오류로 이어질 수 있다. 본 논문은 이 오래된 문제에 대한 해답을 제시하고 자 한다.

해당 문제는 군집분석 분야에서 가장 오랫동안 논의되 어 온 질문 중 하나이며, 수많은 연구자들이 다양한 해결 책을 제안해왔다. 그중 갭 통계량(Gap Statistic) 방법은 가 장 이론적으로 정교한 방법 중 하나로, 엘보우(Elbow)나 실루엣(Silhouette)과 같은 휴리스틱 방식보다 우수한 성능 을 보이는 것으로 알려져 있다. 그러나 갭 통계량 방법 또 한 몇 가지 한계점을 갖고 있어 실제 응용에서는 제약이 있다. 본 논문에서는 이러한 한계를 극복하기 위한 세 가 지 새로운 기법을 제안하며, 이들 기법을 결합한 새로운 방법을 새로운 갭(New Gap)이라고 명명한다.

2. 문헌 연구

2.1 엘보우 방법

k-평균 군집화 알고리즘에서의 클러스터 개수를 결정하 는 가장 오래된 방법으로는 엘보우 방법이 있다[10]. 엘보 우 방법의 아이디어는 데이터셋을 이용하며, 여러 개의 k 값(예: 1에서 10까지)에 대해 군집화를 실행하고, 각 k 값 마다 군집과 내부 지표(예: SSE(제곱 오차 합), 분산 비율 등)를 계산하는 것이다. 그 다음, 각 k 값에 대한 내부 지표 를 선 그래프로 그린다. 특정 k 값에서 내부 지표 값이 급 격히 감소하고, 그 이후에는 k가 더 커져도 거의 변하지 않고 평탄화 상태에 도달한다. 이 지점이 우리가 기대할 수 있는 최적의 k 값이다. <Figure 1>은 엘보우 방법이 어 떻게 작동하는지를 보여준다. 선 그래프는 k가 1에서 2로, 2에서 3으로 증가할 때 급격히 내려가며, 3에서 ‘팔꿈치’ 에 해당하는 지점에 도달한 이 후에는 매우 천천히 내려간 다. 따라서 k = 3이 적절한 클러스터 개수일 가능성이 높 음을 알 수 있다.

2.2 평균 실루엣 방법

평균 실루엣(Average silhouette) 방법은 서로 다른 k 값 들에 대해 관측치들의 평균 실루엣 값을 계산한다[3,9]. 최적의 클러스터 개수 k는 가능한 k 값들의 범위 중에서 평균 실루엣을 최대로 만드는 값이다[4].

k개의 클러스터 결과가 주어졌을 때, 관측치 i가 얼마나 잘 군집화 되었는지를 추정하기 위해 그 실루엣 통계량 s^k (i)를 계산할 수 있다.

s^{k} (i) = \frac{b (i) - a (i)}{\max {a (i), b (i)}}

여기서 a(i)는 관측치 i가 속한 클러스터 내 다른 관측 치 들과의 평균 거리이고, b(i)는 관측치 i와 가장 가까운 다른 클러스터에 속한 관측치 들과의 평균 거리이다.

s^k (i)가 큰 값을 가지면 그 관측치는 잘 군집화 됐다고 할 수 있다. 평균 실루엣 점수, aυgS(k)는 데이터셋을 k개 의 클러스터로 군집화 했을 때, 전체적인 군집화 품질을 추정해준다.

a υ g S (k) = \frac{1}{n} \sum_{i = 1}^{n} s^{k} (i)

따라서 우리는 평균 실루엣 점수를 최대로 만드는 k 값 을 선택한다. 그러나 이 평균 실루엣은 단순한 휴리스틱 지표에 불과하며, 많은 경우에서 성능이 떨어질 수 있다. 또한 k = 1인 경우에는 aυgS(k)가 정의되지 않는다.

2.3 하티간(Hartigan) 통계량 방법

Hartigan[2]은 다음과 같은 통계량을 제안하였다:

H (k) = \frac{\frac{W_{k}}{W_{k + 1}} - 1}{n - k - 1}

여기서 W_k 는 클러스터 평균을 중심으로 한 클러스터 내 제곱합의 평균이다. W_k 를 계산하는 공식은 다음 절의 갭 통계량 방법 부분에서 제시된다.

이 방법의 아이디어는 k = 1에서 시작하여, H (k) 값이 충분히 클 때까지 클러스터를 계속 추가하는 것이다. Hartigan은 “충분히 큰” 기준값으로 10을 제안하였다. 따 라서 추정된 클러스터 개수는 H (k) ≤ 10을 만족하는 최소 의 k ≥ 1 값이다.

2.4 갭(Gap) 통계량 방법

갭 통계량(Gap statistic)은 Tibshirani et al.[10]에 의해 제 안되었으며[1], 현재까지도 클러스터 개수 k를 추정하는 방 법으로 사용되고 있다. 이 방법은 합성 데이터와 실제 데이 터 모두에서 엘보우 방법, 평균 실루엣 방법, Hartigan 방법 보다 우수한 성능을 보이는 것으로 알려져 있다[6,10].

이 방법의 기본 아이디어는 귀무 기준 분포(Null Reference Distribution)를 가정하는 것이다. 이후, 실제 데 이터에서의 클러스터 내 분산 감소율과 기준 분포에서 기 대되는 감소율을 비교한다. 만약 k = K일 때 클러스터 내 분산이 기준 분포에서 기대되는 감소율보다 느리게 감소 하기 시작한다면, 갭 통계량은 k를 예상 클러스터 개수로 반환한다. 갭 통계량의 정식 정의는 다음과 같다:

여기서 d_ij = ‖x_i - x_j‖² 는 관측치 i와 j 사이의 유클리드 거리(Euclidean distance)를, Dr 는 클러스터 Cr 에 속한 n_r 개의 점들에 대해 모든 쌍(pairwise)의 거리 합을 의미한 다. 그러면 클러스터의 밀집도 W_k는 클러스터 평균을 중 심으로 한 클러스터 내 제곱합의 평균으로 정의된다.

W_{k} = \sum_{r = 1}^{k} \frac{1}{2 n_{r}} D_{r}

클러스터링의 목적은 주어진 k에서 최적의 W_k 를 찾는 것이다. k가 증가하면 W_k 는 감소하지만, 감소 속도 역시 점점 줄어든다. 엘보우 방법의 아이디어와 유사하나, 엘보 우 방법의 문제점은 비교할 기준 클러스터링이 없다는 점 과, W_k -W_k_{- 1} 의 차이가 정규화되지 않아 직접적인 비교 가 어렵다는 점이다.

갭 통계량 방법의 핵심 아이디어는 데이터의 적절한 귀 무(Null) 기준 분포 하에서 기대값과 비교하여, log(W_k ) 그 래프를 표준화 하는 것이다. 이 때 최적의 클러스터 개수 는 ( $\log W_{k}^{d a t a}$ )가 기준 곡선 log( $W_{k}^{n u l l}$ ) 보다 가장 크게 아래 로 떨어지는 지점의 k 값으로 추정된다.

G a p_{n} (k) = E_{n}^{*} {\log (W_{k}^{n u l l}) - \log (W_{k}^{d a t a})}

기준 분포에서 추출된 크기 n의 표본에서의 기대값을 $E_{n}^{*}$ 라 하면, 우리는 $E_{n}^{*} {\log (W_{k}^{n u l l})}$ 는 $\log (W_{k}^{n u l l})$ 의 B개 복제 샘플의 평균으로 추정한다. 각 $\log (W_{k}^{n u l l})$ 는 기준 분 포로부터 생성된 몬테카를로(Monte Carlo) 샘플을 사용하 여 계산된다. 몬테카를로 샘플을 k개의 그룹으로 군집화하 고, logW_kb 를 계산한다(b = 1,2, …, B, k = 1, 2, …, K). 이후 추정된 갭 통계량은 다음과 같이 계산된다:

G a p (k) = \frac{1}{B} Σ_{b = 1}^{B} (\log W_{k b}^{n u l l} - \log (W_{k}^{d a t a})

(1)

이때, B개의 몬테카를로 복제, logW_kb 값들은 표준 오 차 sd(k)를 가진다. 이는 시뮬레이션 오차를 고려하여 다 음과 같이 변환된다:

s_{k} = \sqrt{1 + \frac{1}{B}} \cdot s d (k)

(2)

최적의 클러스터 개수 K는 다음 조건을 만족하는 가장 작은 k 값이다:

G a p (k) \geq G a p (k + 1) - s_{k + 1}

(3)

이 규칙은 원래 갭 통계량 논문에서 제시된 것으로, 개발 툴인 R을 이용한 군집화 구현에서는 “Tibs2001SEmax” 규 칙이라고 불린다. 2001년 이후 이 규칙의 여러 대안이 제안 되었다. 예를 들어 “firstSEmax” 규칙이나 “globalSEmax” 규칙[1] 등이 있다. 본 연구에서는 모든 실험에서 Tibs2001SEmax 규칙을 기준 접근법(Baseline Approach)으 로 하였다. 본 논문에서 “갭 통계량”이라 함은, k 선택 규칙 으로 Tibs2001SEmax를 사용하는 Gap(k) 함수를 의미한다.

3. 제안 방법론

갭 통계량은 이론적 토대에 기반하고 있다는 점에서 강 점을 가지지만, 여전히 활용성을 제한하는 몇 가지 단점이 존재한다. 본 절에서는 합성(Synthetic) 데이터셋을 사용한 여러 실험을 통해 이러한 한계점들을 보여준다. 이 실험에 서 얻은 통찰을 바탕으로, 갭 통계량을 개선하기 위한 세 가지 기법을 제안하였다. 이어지는 다음 절에서는 이 기법 들을 결합해 만든 New Gap이 여러 잘 알려진 실제 데이터 셋에서 기존의 갭 통계량보다 더 우수함을 보여주었다.

3.1 갭 통계량 방법의 한계

3.1.1 클러스터 겹침 문제

갭 통계량은 데이터셋 내의 모든 클러스터가 서로 잘 분리되어 있을 때 잘 작동할 수 있다. 그러나 실제 상황에 서는 클러스터들이 일정 정도 겹치는(Overlap) 경우가 대 부분이다. 이러한 비중첩 가정은 갭 통계량 방법이 효과적 으로 사용되기 어렵게 만드는 주요 이유 중 하나이다. <Figure 2>는 합성 데이터셋에서 클러스터들이 일부 겹쳐 져 있는 경우에 갭 통계량이 올바른 k를 찾아내지 못하는 모습을 보여준다.

<Figure 2>는 합성 데이터셋(좌)의 산점도와 갭 통계량 (우) 변화 그래프를 보여주고 있다.

<Figure 2>의 위 좌측, ovl2Gauss 데이터셋(2차원 400개의 관측치)은 두 개의 2차원 가우시안분포, $N ([\begin{matrix} 0 \\ 0 \end{matrix}], [\begin{matrix} 1 & 0.7 \\ 0.7 & 1 \end{matrix}])$ 와 $N ([\begin{matrix} 4 \\ 0 \end{matrix}], [\begin{matrix} 1 & - 0.7 \\ - 0.7 & 1 \end{matrix}])$ 로부터 동일하게 샘플링을 통해서 구성 되었다. 이 데이터셋의 Tibs2001SE 규칙을 적용한 갭 통계량 방법은 이 데이터셋의 산점도에서 보듯이 k = 2가 맞음에도 불구하고 k = 3을 제안하고 있다. <Figure 2> 의 아래 좌측 산점도의 데이터셋(Oval3Gauss, 2차원 600개 관측치)은 3개 의 2차원 가우시안분포, $N ([\begin{matrix} 0 \\ 0 \end{matrix}], [\begin{matrix} 1 & 0.7 \\ 0.7 & 1 \end{matrix}])$ , $N ([\begin{matrix} 0 \\ 8 \end{matrix}], [\begin{matrix} 1 & 0.7 \\ 0.7 & 1 \end{matrix}])$ 와 $N ([\begin{matrix} 0 \\ 4 \end{matrix}], [\begin{matrix} 1 & - 0.7 \\ - 0.7 & 1 \end{matrix}])$ 를 통해 구성되었다. 적절해 보이는 3개의 클러스터 대신 4개의 클러스터 수가 더 적절하다는 결과를 보여주고 있다.

위에서 보듯이 클러스터들이 서로 많이 겹치면 “클러스 터”라는 개념이 매우 모호해진다. 이는 겹치는 영역의 데 이터 밀도가 두 클러스터의 밀도의 합으로 나타나기 때문 이다. 겹치는 영역이 또 하나의 클러스터처럼 보이게 만들 수 있다.

3.1.2 계층적 군집화 구조 문제

비중첩 가정 외에도, 갭 통계량은 데이터셋에 계층적 군 집 구조가 존재하지 않는다고 가정한다. 이는 즉, 데이터 셋 안에 여러 작은 클러스터들로 이루어진 더 큰 클러스터 가 존재하지 않는다는 의미이다.

<Figure 3>은 세 개의 작은 클러스터가 모여 하나의 더 큰 클러스터를 형성하는 계층적 군집 구조를 가진 합성 데이터셋을 보여준다. 갭 통계량이 올바른 k 값을 식별하 지 못하는 모습을 보여준다.

위 <Figure 3>의 윗 부분 산점도는 hier4Gauss 데이터셋으 로 4개의 가우시안 분포, $N ([\begin{matrix} 0 \\ 0 \end{matrix}], [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}])$ , $N ([\begin{matrix} 3 \\ 4 \end{matrix}], [\begin{matrix} 0.05 & 0 \\ 0 & 0.05 \end{matrix}])$ , $N ([\begin{matrix} 4 \\ 3 \end{matrix}], [\begin{matrix} 0.05 & 0 \\ 0 & 0.05 \end{matrix}])$ 와 $N ([\begin{matrix} 3 \\ 3 \end{matrix}], [\begin{matrix} 0.05 & 0 \\ 0 & 0.05 \end{matrix}])$ 로부터의 각각 200, 100, 100, 100개의 샘플로 구성되었다. 아래는 갭 통계량 을 변화를 보여주는 그래프이다. 이 그래프에서 보듯이 이번 에도 적절한 클러스터 수를 보여주지 못하고 있다. 실제에서 는 데이터가 계층적으로 분포하는 경우가 많다. 가장 흔한 예시는 인간 유전자 군집화 문제로, 이러한 유형의 데이터셋 에서는 Tibshirani[10] Dua and Graff[1]가 제안하기를, Tibs2001SEmax 규칙을 사용하는 대신 갭 차트(gap chart)를 직접 눈으로 살펴보고 k 값을 식별해야 한다고 지적하였다. 그러나 이 방법은 매우 주관적이며, 이로 인해 갭 통계량은 고전적인 엘보우(elbow) 방법보다 나은 해법이 되지 못한다.

3.1.3 빅데이터 문제

갭 통계량을 계산하기 위해서는 귀무 기준 분포에서의 기대값 $E_{n}^{*} {\log (W_{k})}$ 을 추정해야 하는데, 이는 매우 많은 계산 자원을 필요로 한다. 귀무 기준 분포를 B번(B ≥ 50) 샘플링해야 하며, 각 샘플 b마다 군집화 알고리즘을 실행 해야 한다. PAM을 사용하는 경우, 계산 복잡도는 O(n²) 이다. 따라서 $E_{n}^{*} {\log (W_{k})}$ 를 추정하기 위한 전체 알고리 즘의 계산 복잡도는 O (Bn²)가 된다. 만약 데이터셋의 관 측치가 매우 큰 경우 갭 통계량 방법을 적용하는 것은 사 실상 어렵다고 할 수 있다.

3.2 New Gap

3.2.1 겹쳐있는 클러스터를 위한 1stDaccSEmax

Tibs2001SEmax 규칙은 특정 지점의 갭(Gap) 값이 그 다음 갭 값보다 높을 유의한 가능성(1 표준오차 기준)이 있을 때, 그 지점의 최소 k 값을 반환한다. 그러나 앞 장에 서 보인 것처럼, 이 규칙은 겹치는 클러스터에 매우 민감 하다. 실제로 데이터셋에 겹치는 클러스터가 존재할 경우, 갭은 k = K 이후(여기서 K는 실제 클러스터 수) 감소하지 않고 오히려 약간 증가한다. 그 결과 k 값이 과대 추정되는 문제가 발생한다.

따라서 갭 통계량을 직접 사용하는 대신, 나는 갭 통계 량의 감소 속도(Deceleration)를 활용할 것을 제안한다. 이 를 줄여서 Dacc 통계량이라 부른다. Dacc는 다음과 같이 계산된다.

\begin{matrix} D a c c (k) = [G a p (k) - G a p (k - 1)] - [G a p (k + 1) - G a p (k)] \\ = 2 G a p (k) - G a p (k - 1) - G a p (k + 1) \end{matrix}

<Figure 4>는 Gap(k) 통계량으로부터 Dacc(k) 통계량을 어떻게 계산할 수 있는지를 보여준다 k가 1에서 K까지 증 가할 때, Gap(k)가 일정하거나 증가하다가, k = K 지점에 서 갑자기 증가 속도가 느려지거나, 심지어 감소하기 시작 한다는 점을 바탕으로 이 통계량을 설계하였다.

<Figure 5>는 여러 상황에서 Dacc(k)가 어떤 형태로 나 타나는지를 보여준다.

<Figure 5a>는 클러스터가 K개이고 겹치지 않는 데이터 의 경우를 보여주고 있다. k < K일 때 Gap(k)는 증가하다 가, k = K에서 첫 번째 국소 최대치에 도달하고, k = K + 1에서 감소하기 시작한다. 따라서 k = K는 Dacc(k)의 첫 번째 국소 최대치가 된다.

<Figure 5b>는 K 개인 클러스터들 중 일부가 약간 겹치 는 데이터의 경우이다. Gap(k)는 여전히 k = K에서 k = K + 1로 증가하기 때문에 Gap(k = K)는 더 이상 첫 번째 국소 최대치가 아니다. 그러나 겹침 영역이 작기 때문에, Gap(K)에서 Gap(K + 1)로의 증가 속도는 Gap(K - 1)에서 Gap(K)로의 증가 속도보다 적다. 따라서 Dacc 통계량은 여전히 k = K에서 최대값을 가지게 되며, 이로 인해 Dacc(k)는 약간의 겹침이 있는 데이터셋에서 Gap(k)보다 강건하다.

<Figure 5b>는 클러스터가 K개이고, 일부 클러스터가 강하게 겹치는 데이터셋의 경우로 클러스터 간의 구분이 매우 모호해진다. 두 개의 강하게 겹친 클러스터는 하나로 보거나, 둘로 보거나, 심지어 세 개로 보더라도 타당하다. 따라서 이 경우에는 Dacc와 갭 통계량 모두 예측 불가능 하다.

귀무 분포에서 기대값 W_k 를 추정할 때 발생하는 샘플 링 오차를 고려하기 위해, 표준 오차 s_k 를 Dacc(k)에 포함 시켜 DaccSE(k)를 정의하였다.

\begin{matrix} D a c c S E (k) = 2 G a p (k) - G a p (k - 1) - G a p (k + 1) - 0.5 s_{k - 1} \\ - 0.5 s_{k} + 1 - s_{k} \end{matrix}

k - 1, k, 또는 k + 1에서의 샘플링 오차가 클수록, DaccSE는 Dacc 추정값에 더 큰 패널티를 부여한다. 참고 로 DaccSE(k) 공식에서 표준 오차의 절반을 사용하였다. DaccSE가 얼마나 적극적이거나, 보수적으로 동작하기를 원하는지에 따라, 표준 오차에 다른 계수를 적용할 수도 있다.

<Figure 6a>에서 보듯이 데이터가 계층적 군집 구조를 가질 경우, 여러 개의 봉우리를 가질 수 있다. 따라서 DaccSE(k)가 전역 최대치에 도달하는 k를 선택하는 대신, 최초의 국소 최대치에 도달하는 k를 선택한다. 이 새로운 규칙은 1stDaccSEmax 규칙이라고 부른다. 일반적으로 1stDaccSEmax 규칙은 k = 2에서 k = kMax까지 순차적으 로 진행하면서 가장 높은 DaccSE 값을 갖는 k를 찾고, Gap(k)이 Gap(k + 1) − s(k + 1) 보다 높아지는 지점에서 멈춘다. <Figure 6>은 1stDaccSEmax 규칙이 다양한 상황 에서 어떻게 작동하는지를 보여준다.

<Figure 7>은 1stDaccSEmax가 클러스터 겹칩이 있는 합성 데이터셋에서 작동한 결과를 보여주고 있다. <Figure 7a>를 보면, Tibs2001SEmax는 클러스터가 겹침으로 인해 Gap(2)에서 Gap(3)으로 여전히 증가하기 때문에 k = 3을 제안하나 1stDaccSEmax는 k = 2에서의 감속이 k = 3에서 의 감속보다 크다는 점을 근거로 올바르게 k = 2를 예측한 다. 또한 <Figure 7b>를 보면 Tibs2001SEmax는 겹침 문제 로 인해 잘못하여 k = 4를 예측한다. 반면 1stDaccSEmax 규칙은 올바르게 k = 3을 예측한다.

3.2.2 계층 군집화 구조를 위한 재귀적 갭

계층적 군집 구조를 가진 데이터셋을 다루기 위해, 갭 통계량에 1stDaccSEmax 규칙을 재귀적으로 적용하는 방 법을 제안한다.

<Table 1>은 RecursiveGap(.) 함수의 의사코드(Pseudo Code)를 제시하고 있다. 각 단계에서 <Table 1>의 find1stDaccSEmax(.) 함수가 k > 1인 k 값을 제안하면, 데 이터셋을 k개의 클러스터로 분할한 뒤, 각 클러스터에 대 해 find1stDaccSEmax(.)를 재귀적으로 적용한다. 이 과정 을 모든 갭 통계량이 k = 1을 반환할 때까지 반복한다.

이때, 매번 갭 통계량을 계산할 때마다 주성분 분석(PCA) 를 사용하여 데이터를 다시 회전(Re-Rotate)하여 차원 (Dimension)을 줄여 킅러스터링 모델의 복잡도를 줄이고 귀무 기준 분포가 입력 데이터에 올바르게 정렬되도록 하기 위함이다. 또한, 재귀적 갭(Recursive Gap)에서는 원래의 Tibs2001SEmax 규칙 대신 1stDaccSEmax 규칙을 사용한다.

3.2.3 빅데이터를 위한 양방향 부트스트래핑

빅데이터의 계산 비용을 줄이기 위해, 양방향 (Two-ways) 접근법을 제안한다. 이 빙법에서는 귀무 분포 의 기대값 $W_{k}^{n u l l}$ 를 추정하기 위해 귀무 참조 분포를 B 번 샘플링할 뿐만 아니라, 데이터셋에서도 n_B개의 데이터 포 인트를 복원추출하여 B번 부트스트래핑을 수행함으로써 $W_{k}^{d a t a}$ 통계량을 계산한다. 이제 $W_{k}^{d a t a}$ 통계량은 B개의 재 표본화된 데이터셋에서 계산된 W_k의 평균값이 된다. 여기 서 n_B는 원래 데이터 크기 n보다 훨씬 작다. Gap(k)는 이 전 장의 식 (1)과 같이 여전히 $\log (W_{k}^{n u l l})$ 과 $\log (W_{k}^{d a t a})$ 의 차이로 계산된다.

B개의 몬테카를로 복제(Monte Carlo replicates)로부터 계산된 ( $\log W_{k b}^{n u l l} - \log W_{k b}^{d a t a}$ ) 값은 표준오차 sd(k)를 나타 낸다. 이 sd(k)는 두 가지 부트스트래핑 과정에서 발생하 는 표본추출 오차를 모두 반영하며, 일반적으로 기존의 부 트스트래핑 보다 값이 더 크게 나타난다. Gap(k)의 표준편 차는 다음과 같이 계산된다. 이 때 시뮬레이션 에러인 s_k 는 앞의 식 (2)와 같다.

s d (k) = \sqrt{\frac{1}{B} \sum_{b = 1}^{B} {(\log W_{k b}^{n u l l} - \log W_{k b}^{d a t a}) - G a p (k)}^{2}}

양방향 부트스트래핑 기법은 원본 데이터셋의 전체 데 이터 포인트 수 n보다 훨씬 작은 n_B 개의 데이터 포인트만 을 재표본화(Resampling)함으로써, 갭 통계량 알고리즘에 투입되는 데이터 포인트 수를 줄일 수 있다. 재표본화된 데이터가 원본 데이터셋을 충분히 대표한다면, 갭 통계량 은 여전히 k에 대한 좋은 추정치를 제공할 수 있다.

다음 간단한 예시는 이중 부트스트래핑 접근법의 효과 성을 보여준다. 데이터셋 크기가 n = 2000, 부트스트래핑 샘플 수 B = 50, 최대 군집 수 kMax = 10, 그리고 O(n²)의 복잡도를 가진 PAM 클러스터링 알고리즘을 사용할 경우, 기존 갭 통계량은 (B + 1) × kMax = 510번의 PAM 알고리 즘 실행을 2000개의 데이터 포인트에 대해 수행해야 한다. 이는 대략 510 × 2000² ≈ 20억 시간 단위가 소요된다.

반면 동일한 설정에서 n_B = 500개의 데이터 포인트를 사용하는 이중 부트스트래핑을 적용하면, 2 × B × kMax = 1000번의 PAM 알고리즘 실행을 500개의 데이터 포인 트에 대해 수행하면 된다. 이는 대략 1000×500² ≈ 2억 5 천만 시간 단위가 소요되며, 속도는 8배 이상 빨라진다. 특히 n이 증가할수록 속도 향상은 제곱으로 증가한다.

3.2절에서 제시한 세가지 알고리즘(1stDaccSEmax rule, 재귀적 갭(Recursive gap), 양방향 부트스래핑(Two-way bootstrapping))을 결합해 사용한다면 갭 통계량 기반의 클 러스터 개수를 예측하기 위한 새로운 방법(New Gap)을 제 안할 수 있다.

3.3 실험 결과

<Table 2>는 본 논문에서 사용된 모든 데이터셋의 개요 를 제시하고 있으며, <Table 3>은 본 논문에서 수행된 모 든 실험 결과를 요약하고 있다. 데이터셋 중 위 3개는 합성 데이터셋이며 나머지 5개는 UCI 저장소[5]에 있는 것들을 사용하였다. 또한 <Table 3>은 새로운 갭(New Gap) 접근 법이 기존 방법 및 다른 전통적인 방법들보다 효과적임을 입증한다.

<Table 3>은 기존 방법들 중에 많이 사용되는 3가지 방 법과 기존 갭 통계량 방법들과의 성능 비교 결과를 보여주 고 있다. 두 번째 열은 각 데이터셋의 최적의 클러스터 수 를 보여주고 있다. 이 때 일부 데이터셋은 복잡한 구조를 보여주고 있는데, 예를 들어 hier4Gauss 데이터셋의 경우 크게 보면 2개의 클러스터로 구성되어 있으나 이 중 1개의 클러스터를 보면 3개의 작은 클러스터로 구성되었다고 볼 수도 있기에 이를 1(3)으로 표현하였다. 이 실험 결과를 보면 새로운 갭(New Gap) 대부분의 경우에서 최적의 클러 스터 수를 찾거나, 비슷한 결과를 보여주어 성능이 다른 방법들에 비해 우수함을 알 수 있다.

4. 결 론

본 연구는 데이터셋의 군집 수 k를 예측하는 방법 중 하나인 기존 갭 통계량 방법을 개선하는 데 초점을 맞추었 다. 갭 통계량의 세 가지 주요 한계를 규명하고 이를 실증 적으로 보여주었다. 그 한계는 (1) 군집 간 중첩, (2) 계층 적 클러스터링 구조, (3) 대규모 데이터셋이 가지고 있던 문제이다. 이러한 통찰을 바탕으로 본 연구는 세 가지 기 법—1stDaccSEmax 규칙, 재귀적 갭(Recursive Gap), 그리 고 양방향(Two-way) 부트스트래핑 기법을 제안하였다. 또 한 이 세 가지 기법을 결합한 새로운 갭 방법(New Gap)이 라 부르는 새로운 알고리즘이 좋은 결과를 보일 수 있음을 보여주었다.

새로운 방법의 성능은 UCI 저장소에 공개된 여러 실제 데이터셋과 일부 합성 데이터셋을 통해 평가되었으며, 기존 갭 통계량 및 일반적인 전통적 접근법들과 비교되었다. 그 결과, 새로운 갭 방법은 모든 다른 접근법보다 우수한 성능 을 보였으며, 특히 데이터셋이 군집 간 중첩을 갖거나 계층 적 클러스터링 구조를 포함할 때 그 효과가 두드러졌다.

Figure

<Figure 1>.

Identification of Elbow Point

<Figure 2>.

Overlapping Clusters Problem with Gap Statistic

<Figure 3>.

Hierarchical Clustering Structure Problem

<Figure 4>.

How to Compute Dacc(k) from Gap(k)

<Figure 5>.

The Dacc(k) value in different scenarios

<Figure 6>.

1stDaccSEmax Works in Different Cases

<Figure 7>.

1st DaccSEmax works on Synthetic Datasets

Table

<Table 1>.

Pseudocode of the Function recursiveGap(.)

<Table 2>.

Data Description

Dataset	Variable	Synthetic	Data Point	Class
ovl2Gauss	2	Yes	400	2
ovl3Gauss	2	Yes	600	3
hier4Gauss	2	Yes	500	4
iris	3	No	150	3
unbalance 3-5	2	Yes	6500	8
breastcancer	10	No	684	2
seeds	7	No	210	3
khan	64	No	306	4

<Table 3>.

Performance Comparison with Existing Methods

Dataset	The Optimal K	Elbow	Silhouette	Hartigan	Old gap	New gap
ovl2Gauss	2clusters	2	2	4	3	2
ovl3Gauss	3 clusters	2 or 3	2	3	4	3
hier4Gauss	1 big clusters and one cluster with 3 small clusters inside: 1+1(3)	2	2	3	2	1+1(3)
iris	2 big clusters; one contains two small clusters: 1+1(2)	2	2	4	4	1+1(2)
unbalance 3-5	3 big clusters and 5 small clusters: 3+1(5)	4	2	1	4	3+1(5)
breastcancer	2 clusters	2	2	2	2	1+1(2)
seeds	3 clusters	2 or 3	2	6	3	3
khan	4 clusters	2	2	4	1	4

Reference

Dua, D. and Graff, C., UCI Machine Learning Repository, Irvine, CA: University of California, School of Information and Computer Science, 2019. Retrieved August 26, 2025, from http://archive.ics.uci.edu/ml
Hartigan, J.A., Clustering algorithms, New York Wiley - Wiley series in probability and mathematical statistics xiii, 1975, p. 351.
Kassambara, A., Determining The Optimal Number Of Clusters: 3 Must Know Methods, 2017, [online] Sthda.com. Available at: https://www.sthda.com/english/articles/29-cluster-validation-essentials/96-determining-the-optimal-number-of-clusters-3-must-know-methods/ [Accessed 13 Aug. 2018].
Kaufman, L. and Rousseeuw, P.J., Finding Groups in Data: An Introduction to Cluster Analysis, 1990, Wiley, New York.
Kelly, M., Longjohn, R., Nottingham, K., The UCI Machine Learning Repository, https://archive.ics.uci.edu
Kodinariya, T.M. and Makwana, P. R., Review on determining number of Cluster in k-means Clustering, International Journal of Advance Research in Computer Science and Management Studies, Volume 1, Issue 6, November 2013 pp. 90-95
Miranda, M.I., Clustering methods and algorithms [Online lecture notes], Department of Computer Science and Engineering, Indian Institute of Technology Bombay, 1999, Retrieved August 26, 2025, from http://www.cse.iitb.ac.in/dbms/Data/Courses/CS632/1999/clustering/dbms.html.
Osmar, R.Z., Principles of Knowledge Discovery in Databases, 1999, Chapter 8: Data Clustering. [Online]. Available: http://www.cs.ualberta.ca/~zaiane/courses/cmput690/slides/Chapter8/index.html
Rousseeuw, P.J., Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis, Journal of Computational and Applied Mathematics, 1987, Vol. 20, No. 1, pp. 53-65.
Tibshirani, R., Walther, G., and Hastie, T., Estimating the number of clusters in a data set via the Gap statistic, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2001, Vol. 63, No. 2, pp. 411-423.
Tibshirani, R., Walther, G., and Hastie, T., Estimating the number of data clusters via the Gap statistic, Journal of the Royal Statistical Society B, 2001, Vol. 63, pp. 411-423.

Description	The function recursiveGap(.) takes dataset D and kMax as input, and output the prediction about the hierarchical clustering structure of the dataset D.
Input:	D: multi-dimensional dataset; kMax: maximum number of k;
Output:	clusterTree: a tree that shows the hierarchical clustering structure of the dataset D. Each node stores the number of child clusters that it has. If a node has more than one cluster, it also stores the link to its child nodes.
Predefined Function:	find1stDaccSEmax (D, kMax): returns the number of clusters k using the 1stDaccSEmax
Define function recursiveGap(D, kMax):
Set kBest = find1stDaccSEmax(D, kMax)
If kBest = 1:
Return clusterTree with the root node
with value = 1 and has no child
Else
Run PAM(D, kBest) to cluster D into kBest
clusters: {D1,…,DkBest}
For each child dataset Di in {D1,…,DkBest}:
clusterSubTreei = recursiveGap(Di, kMax)
Return the clusterTree with the root node
with value = kBest and
cluster{clusterSubTreei, ...,
clusterSubTreekBest} as its children