Absolute indices for determining compactness, separability and number of clusters

이 논문은 기존 상대적 지수의 한계를 극복하고 데이터 구조에 의존하지 않는 새로운 절대적 군집 지수를 제안하여 군집의 응집도와 분리도를 정량화하고 최적의 군집 수를 결정하는 방법을 제시합니다.

핵심

이 논문은 **"데이터 속의 숨겨진 무리 (클러스터) 를 어떻게 찾아내고, 그 무리가 얼마나 잘 구분되어 있는지 판단할 수 있는 새로운 방법"**을 소개합니다.

기존의 방법들은 주로 "이 알고리즘과 저 알고리즘 중 어느 것이 더 나을까?"를 비교하는 데 초점을 맞췄다면, 이 논문은 **"이 데이터 자체가 정말로 명확한 무리들을 가지고 있는가?"**를 절대적인 기준으로 판단하는 새로운 나침반을 만들었습니다.

이 복잡한 개념을 쉽게 이해할 수 있도록 **'파티 (Party)'**와 **'방 (Room)'**에 비유해서 설명해 드릴게요.

---

1. 문제 상황: 파티에 온 손님들

데이터 분석을 마치 초대된 손님들이 가득한 거대한 파티라고 상상해 보세요.

• 목표: 이 파티에 있는 손님들을 "친구들끼리 모여 있는 무리 (클러스터)"로 나누는 것입니다.
• 어려움: "도대체 몇 개의 무리로 나누는 게 정답일까?"를 알기가 매우 어렵습니다.
  • 너무 많이 나누면 (예: 사람마다 따로 방을 줌) 의미가 없습니다.
  • 너무 적게 나누면 (예: 모두를 한 방에 몰아넣음) 혼란스럽습니다.

기존의 방법들은 "A 팀이 나눈 무리가 B 팀보다 낫다"라고 비교만 했지, "이 무리 자체가 진짜로 잘 나뉜 건가?"를 절대적으로 평가하는 기준이 부족했습니다.

2. 새로운 해법: 두 가지 절대 지수 (나침반)

이 논문은 무리를 판단하기 위해 두 가지 핵심 질문을 던집니다.

① 단단함 (Compactness): "방 안이 얼마나 빽빽한가?"

• 비유: 어떤 방에 사람들이 모여 있다고 칩시다.
  • 단단한 방 (좋은 무리): 사람들이 서로 어깨를 맞대고 빽빽하게 모여 있고, 빈 공간이 거의 없습니다.
  • 흐트러진 방 (나쁜 무리): 사람들은 방 구석구석에 흩어져 있고, 한가운데는 텅 비어 있습니다.
• 이 논문의 아이디어: 단순히 평균 거리를 재는 게 아니라, **"방 안의 빈 공간 (공백) 을 얼마나 잘 채우고 있는가?"**를 정밀하게 측정합니다. 빈 공간이 많으면 '단단함' 점수가 낮아집니다.

② 분리됨 (Separability): "방과 방 사이의 문이 얼마나 단단한가?"

• 비유: 여러 개의 방이 있다고 칩시다.
  • 잘 분리된 방: 방과 방 사이에 두꺼운 벽이 있거나, 아예 문이 없습니다. 서로 섞일 수 없습니다.
  • 섞인 방: 방과 방 사이의 벽이 얇거나, 사람들이 문 앞 (경계선) 에 모여 있어 서로 섞일 수 있습니다.
• 이 논문의 아이디어: 두 무리 (방) 의 가장자리 (경계) 에 있는 사람들만 골라내어, **"이 두 무리가 진짜로 섞이지 않고 명확히 구분되는가?"**를 계산합니다.

3. 결정의 순간: "최고의 파티 구성" 찾기

이제 이 두 가지 점수 (단단함 + 분리됨) 를 가지고 **의사결정 지도 (Decision-space plot)**를 그립니다.

• 지도의 의미: 가로축은 '단단함', 세로축은 '분리됨'입니다.
• 목표: 두 가지 점수가 모두 높은 곳 (지도의 오른쪽 위) 을 찾아야 합니다.
  • 하지만 보통은 단단하게 모으려고 하면 무리들이 서로 붙어버리고 (분리됨 떨어짐), 분리하려고 하면 무리들이 너무 흩어집니다 (단단함 떨어짐). 이것이 상충되는 문제입니다.
• 해결책: 이 논문은 "분리됨"을 가장 중요하게 여깁니다. 가장 잘 구분되는 (분리됨 점수가 높은) 상태를 찾아서, 그 상태가 "진짜 정답 (최적의 무리 개수)"이라고 선언합니다.

4. 왜 이 방법이 특별한가요? (절대 지수)

기존의 방법들은 "A 라는 알고리즘으로 나눈 결과 vs B 라는 알고리즘으로 나눈 결과"를 비교하는 상대적인 척도였습니다. 마치 "A 학생이 B 학생보다 시험 점수가 더 높다"라고만 알려주는 것과 같습니다.

하지만 이 논문이 제안한 방법은 절대적인 척도입니다.

• "이 데이터는 절대적으로 5 개의 무리로 나누는 것이 가장 자연스럽고, 5 개의 무리가 서로 명확히 구분된다"라고 스스로 판단할 수 있습니다.
• 마치 "이 파티는 5 개의 방으로 나누는 게 가장 자연스럽다"라고 객관적인 사실을 알려주는 나침반과 같습니다.

5. 결론: 데이터의 숨겨진 구조를 찾아내는 안목

저자들은 이 새로운 방법을 가짜 데이터 (정답을 알고 있는 데이터) 와 실제 데이터 (우리가 모르고 있는 데이터) 에 모두 적용해 보았습니다.

• 결과: 기존의 유명한 방법들보다 훨씬 정확하게 "진짜 무리의 개수"를 찾아냈습니다.
• 의미: 이제 우리는 데이터 분석을 할 때, "어떤 알고리즘을 쓸까?"만 고민하는 것이 아니라, **"이 데이터 자체가 가진 자연스러운 무리의 개수는 몇 개인가?"**를 절대적인 기준으로 판단할 수 있게 되었습니다.

한 줄 요약:

"이 논문은 데이터 속의 무리들이 **'얼마나 빽빽하게 모여 있는지'**와 **'서로 얼마나 명확히 구분되는지'**를 절대적인 눈으로 재는 새로운 자를 만들어, 데이터의 진짜 구조를 찾아내는 길을 제시했습니다."

기술 요약

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

• 핵심 문제: 데이터 마이닝에서 군집 분석 (Clustering) 의 가장 어려운 과제 중 하나는 데이터셋 내의 "진짜" 군집 수 (optimal number of clusters) 를 찾는 것입니다.
• 기존 방법의 한계:
  • 기존 군집 유효성 지수 (Cluster Validity Indices, 예: Davies-Bouldin, Silhouette, Calinski-Harabasz 등) 는 대부분 상대적 (Relative) 측도입니다. 이는 주로 서로 다른 군집 알고리즘을 비교하거나 알고리즘 파라미터를 튜닝하는 데 사용되며, 단일 알고리즘이 생성한 군집의 절대적인 품질 (응집성 및 분리성) 을 평가하는 데는 한계가 있습니다.
  • 복잡한 데이터 구조에서는 다양한 지수들이 상충되는 결과를 도출하여, 어떤 군집 수가 "최적"인지 판단하기 어렵습니다.
  • 기존의 절대적 지수들은 데이터 구조에 크게 의존하거나, 군집화 과정 자체에 통합되지 않는 경우가 많습니다.

2. 제안된 방법론 (Methodology)

저자들은 군집의 **응집성 (Compactness)**과 **분리성 (Separability)**을 독립적으로 평가할 수 있는 새로운 **절대적 유효성 지수 (Absolute Cluster Validity Indices)**를 제안했습니다.

가. 응집성 함수 및 지수 (Compactness Function & Index)

• 응집성 함수 ($f(t)$): 데이터 포인트와 군집 중심 (centroid) 사이의 거리 분포를 기반으로 정의됩니다.
  • 중심에서 거리 $t$ 이내의 점들의 집합 $S(t)$를 정의하고, 이 집합 내 점들의 평균 거리를 계산합니다.
  • 이 함수는 데이터가 균일하게 분포되어 있는지, 아니면 빈 공간 (sparse regions) 이 존재하는지를 감지하는 계단 함수 (step function) 형태를 가집니다.
• $\epsilon$-응집성 계수: 데이터가 균일하게 분포된 영역을 식별하기 위해 방향성 벡터 (positive spanning set) 를 사용하여 각 영역 내 점들의 분포 밀도를 측정합니다.
• $\epsilon$-응집성 지수 ($c_A(\epsilon)$): 데이터 포인트가 얼마나 조밀하고 균일하게 분포되어 있는지를 $[0, 1]$ 범위로 정규화하여 측정합니다. 값이 1 에 가까울수록 군집이 매우 응집되어 있음을 의미합니다.

나. 분리성 지수 (Separability Index)

• 인접 집합 (Adjacent Sets): 두 군집 $A_1, A_2$의 중심 사이 거리를 기준으로, 각 군집 내에서 다른 군집의 중심에 더 가까운 점들의 집합 ($Z_{12}, Z_{21}$) 을 정의합니다.
• 마진 (Margin): 두 군집의 중심 거리에서 각 군집의 인접 집합이 차지하는 반지름을 뺀 값으로 정의됩니다. 이는 두 군집 사이의 "여백"을 수치화합니다.
• 분리성 지수 ($\beta_{ij}$): 마진을 정규화하여 $[0, 1]$ 범위의 값으로 변환합니다.
  • $\beta_{ij} > 0.5$: 두 군집은 분리 가능 (separable).
  • $\beta_{ij} \le 0.5$: 두 군집은 분리 불가능 (inseparable).
• 전체 분리성 지수 ($s_k$): 모든 군집 쌍에 대한 분리성 지수를 종합하여 전체 군집 구조의 분리 정도를 평가합니다.

다. 군집 수 결정 전략 (Determining the Number of Clusters)

• 다목적 최적화 문제: 최적의 군집 수를 찾는 문제를 응집성 (높을수록 좋음) 과 분리성 (높을수록 좋음) 을 동시에 극대화하는 다목적 최적화 문제로 정의합니다.
• 결정 공간 도표 (Decision-space Plot): 각 군집 수 ($k$) 에 대해 (응집성 지수, 분리성 지수) 좌표를 가진 점을 2 차원 평면에 그립니다.
• 비우세 해 (Non-dominated Solutions) 선정:
  • 파레토 최적 (Pareto optimal) 인 점들 중에서 분리성 지수가 가장 높은 점을 선택하여 "진짜" 군집 수로 간주합니다.
  • 이를 위해 응집성과 분리성을 결합한 스칼라 지수 $T_k(\epsilon) = \frac{1 - C_k(\epsilon)}{s_k}$를 정의하여 최소화하는 방식을 사용하기도 합니다.

3. 주요 기여 (Key Contributions)

1. 절대적 유효성 지수 도입: 데이터 구조에 의존하지 않고, 단일 알고리즘의 결과를 절대적인 기준으로 평가할 수 있는 새로운 지수 체계를 제안했습니다.
2. 응집성과 분리성의 정량적 분리: 기존 지수들이 두 특성을 혼합하여 평가하는 것과 달리, 각 특성을 독립적으로 정의하고 측정할 수 있는 수학적 프레임워크를 제공했습니다.
3. 시각적 의사결정 도구: '결정 공간 도표'를 통해 다양한 군집 수 후보들을 시각화하고, 비우세 해를 통해 최적의 군집 수를 직관적으로 선택할 수 있는 방법을 제시했습니다.
4. 파라미터 $\epsilon$의 유연성: 데이터 크기에 따라 조정 가능한 매개변수 $\epsilon$을 도입하여 다양한 스케일의 데이터셋에 적용 가능하게 했습니다.

4. 실험 결과 (Results)

• 데이터셋: 합성 데이터 (A1, A2, A3, Unbalance, Dim256, DA1-3 등) 와 실제 세계 데이터 (Liver Disorders, Ionosphere, Shuttle Control, Person Activity 등) 를 총 8 개 이상 사용했습니다.
• 비교 대상: 평균 실루엣 (Sav), Davies-Bouldin (DB), Calinski-Harabasz (CH), Dunn (Dn), Xie-Beni (XB), 절대 G-지수 (Gstr, Grex) 등 기존 유명 지수들과 비교했습니다.
• 성능:
  • 합성 데이터: 실제 군집 수가 알려진 데이터셋에서 제안된 지수 ($T_k$) 는 거의 모든 경우 정확한 군집 수를 식별했습니다. 특히 DA3(중심 군집이 다른 군집과 섞인 경우) 와 같이 기존 지수들이 실패하거나 모호한 결과를 보였던 데이터셋에서도 우수한 성능을 발휘했습니다.
  • 실제 데이터: Shuttle Control 데이터 (7 개 군집) 와 Person Activity 데이터 (11 개 클래스) 에서는 제안된 지수가 다른 대부분의 유효성 지수와 일치하거나, 더 명확한 군집 구조를 제시했습니다.
  • 결정 공간 분석: 모든 실험에서 제안된 방법론에 의해 선정된 군집 수는 결정 공간 도표에서 비우세 해 (non-dominated solutions) 중 분리성이 가장 높은 점과 일치했습니다.

5. 의의 및 결론 (Significance)

• 데이터 순서 및 속성 불변성: 제안된 지수는 데이터 포인트의 순서나 속성의 순서에 영향을 받지 않으며, 정규화 (scaling) 되어 있어 서로 다른 데이터셋 간 비교가 가능합니다.
• 실용성: 군집화 알고리즘의 파라미터 튜닝뿐만 아니라, 단일 알고리즘이 생성한 결과의 절대적인 품질을 평가하는 데 유용한 도구로 작용합니다.
• 결론: 이 연구는 군집 분석의 "진짜" 군집 수를 찾는 문제를 해결하기 위해 응집성과 분리성을 체계적으로 통합한 새로운 절대적 지수를 제시하며, 기존 상대적 지수들의 한계를 극복하고 더 신뢰할 수 있는 군집 평가를 가능하게 합니다.