📊 statistics

A novel k-means clustering approach using two distance measures for Gaussian data

본 논문은 기존 방식에 비해 더 견고한 수렴과 개선된 이상치 처리를 달성하기 위해 칼린스키-하라바츠츠(Calinski-Harabasz) 기준과 더불어 군집 내 및 군집 간 거리 지표를 모두 활용하는 가우시안 데이터용 새로운 k-평균 클러스터링 알고리즘을 제안한다.

원저자: Naitik Gada (Rochester Institute of Technology)

게시일 2026-07-31

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Naitik Gada (Rochester Institute of Technology)

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

수천 명의 사람들이 어울리고 있지만 아무도 누구와 속해 있는지 모르는, 거대하고 혼란스러운 파티에 걸어 들어가는 모습을 상상해 보십시오. 이름표도 없고, 그룹 리더도 없으며, 서로 다른 테이블을 안내하는 표지판도 없습니다. 당신의 임무는 어떤 사람들이 자연스럽게 함께 어울리는지 알아내는 것입니다. 이것이 바로 컴퓨터 과학의 한 분야인 **비지도 학습(unsupervised learning)**의 세계입니다. 여기서 알고리즘은 정답을 미리 듣지 않은 채, 무질서한 데이터 속에서 숨겨진 패턴을 찾으려고 노력합니다. 이 일을 수행하는 가장 인기 있는 도구 중 하나가 **k-평균 군집화(k-means clustering)**라고 불리는 것입니다. 이것을 컴퓨터가 각 그룹의 '중심'을 찾아 사람들을 그 중심점으로 끌어당김으로써 유사한 항목들을 그룹화하려는 의자 뺏기 게임이라고 생각하십시오. 목표는 한 그룹 안에 있는 모든 사람이 서로 매우 유사하게 만들면서, 동시에 다른 그룹의 사람들과는 매우 다르게 만드는 것입니다. 하지만 이 게임에는 까다로운 결함이 있습니다. 컴퓨터가 그룹의 중심이 어디인지에 대해 무작위 추측으로 시작하기 때문에, 종종 국소적인 '충분히 괜찮은' 해결책에 갇혀버린다는 점입니다. 만약 잘못된 시작 지점을 선택한다면, 전체 그룹화가 잘못될 수 있습니다. 이는 현실 세계에서 고객 데이터를 정리하는 것부터 의료 영상을 분석하는 것에 이르기까지, 이 그룹들을 정확하게 파악하는 것이 현명한 결정을 내리는 데 매우 중요하기 때문에 의미가 있습니다.

이 논문은 이 클래식한 k-평균 게임에 더 신뢰할 수 있는 방식을 도입하기 위한 새로운 변화를 소개합니다. 저자인 Naitik H. Gada는 전통적인 방식이 오직 사람들이 자신의 그룹 중심과 얼마나 가까운지(군집 내 거리, within-cluster distance)만을 고려한다고 제안합니다. 새로운 접근 방식은 두 번째 규칙을 추가합니다. 즉, 서로 다른 그룹들이 서로로부터 얼마나 떨어져 있는지(군집 간 거리, inter-cluster distance)도 확인하는 것입니다. 만약 파티 참석자들을 그룹화하는 동안, 단순히 "당신은 친구들과 가까운가요?"라고 묻는 대신, "당신은 다른 테이블들로부터 충분히 멀리 떨어져 있나요?"라고도 묻는다면 어떨지 상상해 보십시오. 이 두 가지 측정값을 균형 있게 조절함으로써, 알고리즘은 그룹이 긴밀하게 결속될 뿐만 아니라 서로 명확하게 분리되도록 노력합니다.

연구진은 두 가지 유형의 데이터를 사용하여 이 아이디어를 테스트했습니다. 첫째, 그들은 깔끔하고 둥근 점 구름 형태(가우시안 데이터를 시뮬레이션함)를 가진 가상의 데이터 세트를 만들고, 다양한 수준의 "무질서함" 또는 분산을 적용했습니다. 또한 그들은 유명한 Iris 꽃 데이터, Wine 화학 분석 데이터, 그리고 Breast Cancer 의료 데이터 세트를 포함한 실제 세계의 벤치마크 데이터 세트에서도 알고리즘을 테스트했습니다. 결과는 두 가지 거리 측정치를 모두 사용하는 새로운 방식이 전통적인 k-평균보다 일관되리 더 우수한 성능을 보였다는 것을 보여주었습니다. 가짜 데이터 테스트에서, 새로운 알고리즘은 데이터가 무질서하거나 시작 지점이 까다로울 때 기존 방식보다 더 정확하고 실수를 덜 했습니다. 예를 들어, 높은 분산을 가진 2D 데이터 세트에서 새로운 방식은 0.9801의 정확도를 달성한 반면, 전통적인 방식은 0.9508을 기록했습니다. Iris 데이터 세트에서는 기존 방식의 0.7751에 비해 0.8420의 정확도에 도달했습니다.

또한 이 논문은 새로운 방식이 "아웃라이어(outliers)"—즉, 다른 사람들로부터 약간 떨어져 서 있는 파티 손님들—를 처리하는 데 더 뛰어나다는 점을 강조합니다. Wine 데이터 세트에서 전통적인 방식은 이러한 멀리 떨어진 점들을 때때로 잘못 분류했지만, 새로운 방식은 이들을 정확하게 식별했습니다. 그러나 저자들은 새로운 방식이 개선된 것이기는 하지만, 모든 문제를 해결하는 마법의 탄환은 아니라는 점을 주의 깊게 언급합니다. 이 방식은 여전히 그룹의 초기 시작 위치 문제로 인해 다소 어려움을 겪으며, 매우 고차원적인 데이터(9차원인 Breast Cancer 세트와 같은)에서의 성능은 전통적인 방식보다 약간 더 나은 수준이었습니다. 이 연구는 두 번째 거리 측정을 추가하는 것이 군집화를 "공고하고 더 견고하게(solidified and more robust)" 만들지만, 이는 여전히 진행 중인 작업이며 향후 더욱 정교한 연구를 위한 문을 열어준다는 점을 시사합니다.

기술 요약: 가우시안 데이터를 위한 두 가지 거리 측도를 이용한 새로운 k-평균 클러스터링 접근 방식

문제 정의
클러스터링 분석은 구조화되지 않은 라벨 없는 데이터 내에서 동질성을 식별하는 데 사용되는 기본적인 비지도 학습 기법이다. 다양한 방법 중 k-평균(k-means) 클러스터링은 계층적 접근 방식에 비해 계산 효율성이 높아 널리 활용된다. 그러나 전통적인 k-평균 방식은 두 가지 주요 한계를 갖는다:

초기화에 대한 민감도: 이 알고리즘은 초기 클러스터 중심의 위치에 매우 민감하며, 이로 인해 전역 최적해가 아닌 지역 최적해(local minima)로 수렴하는 경우가 자주 발생한다.
단일 지표 최적화: 표준 알고리즘은 그룹 내 동질성을 보장하기 위해 오직 군집 내 거리(Within-Cluster Distance, WCD)만을 최소화한다. 이는 서로 다른 그룹 간의 분리도(Inter-Cluster Distance, ICD)를 명시적으로 최대화하지 않는다.
사전 결정된 $k$ 에 대한 의존성: 클러스터의 수( $k$ )를 사전에 지정해야 하는데, 시각화가 불가능한 고차원 데이터에서는 이를 결정하는 것이 어렵다.

기존 문헌들은 다양한 초기화 방법(예: 유전 알고리즘, 시뮬레이티드 어닐링)과 대안적인 거리 측도(예: 맨해튼, 체비쇼프)를 통해 이러한 문제를 해결하려고 시도해 왔다. 그러나 많은 연구가 합성 데이터에 과도하게 의존하거나, F1-score 또는 민감도와 같은 지표를 통한 엄격한 정량화를 결여하고 있거나, 혹은 클러스터 간 분리를 최대화하기 위해 특별히 설계된 거리 측도를 통합하는 데 실패했다.

방법론
본 논문은 WCD와 ICD를 모두 거리 측도로 포함하는 표준 k-평균 알고리즘의 새로운 변형을 제안한다.

클러스터 결정: 클러스터의 수( $k$ )는 임의로 선택되지 않고 **칼린스키-하라바츠즈 지수(Calinski-Harabasz index)**를 사용하여 결정되며, 엘보우 방법(Elbow method)을 통해 검증된다.
알고리즘 로직:
- 초기화: 클러스터 중심은 데이터셋의 인덱스에 대한 무작위 순열을 통해 초기화된다.
- 이중 지표 최적화: 점들과 그 중심점 사이의 제곱 유클리드 거리 합(WCD)을 최소화하는 전통적인 k-means와 달리, 제안된 알고리즘은 상대 비용(relative cost) 함수를 최적화한다. 이 함수는 전체 WCD를 전체 ICD의 비율로 정의한다.
- WCD 정의: 클러스터 중심으로부터 해당 클러스터 내의 모든 점까지의 거리 제곱 합.
- ICD 정의: 클러스터 $i$ 에 속한 점과 클러스터 $i$ 에 속하지 않는 모든 점 사이의 거리 제곱 합을 모든 클러스터에 대해 합산한 것.
- 반복: 알고리즘은 이 상대 비용을 최소화하면서 중심점을 반복적으로 업데이트한다. 프로세스는 중심점이 안정화될 때까지 계속된다.
평가 지표: 성능을 정량화하기 위해 본 연구는 혼동 행렬(Confusion Matrix)을 사용하여 전체 정확도(OA), 정밀도(Precision, 양성 예측 가치), 재현율(Recall, 민감도), 그리고 F1 점수를 산출한다.

실험 설정
알고리즘은 두 가지 범주의 데이터셋에 대해 평가되었다:

합성 데이터: 다양한 차원(2D 및 3D)과 분산(0.5 및 1.0)을 가진 정규 분포에서 생성된 네 개의 데이터셋. 이들은 잘 정의된 클러스터와 겹치는(불분명한) 클러스터 모두에서 성능을 테스트하도록 설계되었다.
벤치마크 데이터: UCI 머신러닝 저장소의 세 가지 데이터셋:
- Iris: 150개 인스턴스, 4개 특성, 3개 클래스.
- Wine: 178개 인스턴스, 13개 화학적 속성, 3개 클래스.
- Breast Cancer (Wisconsin): 569개 인스턴스, 9개 특성, 2개 클래스(양성/악성).

모든 실험은 공정한 비교를 위해 제안된 알고리즘과 전통적인 k-means 알고리즘 모두에 동일한 무작위 초기화 시드를 사용하여 100회 반복 실행되었다.

주요 결과
제안된 알고리즘은 모든 데이터셋에서 전통적인 k-means보다 일관되게 우수한 성능을 보였으나, 개선의 폭은 다양했다:

합성 데이터:
- 분산 0.5인 2D 데이터에서 제안된 방법은 **97.05%**의 정확도를 달성하여 전통적인 k-means의 96.07%보다 높은 성능을 보였다.
- 더 겹치는 구조를 가진 2D 데이터(분산 1.0)의 경우, 격차는 98.01% 대 95.08%로 벌어졌다.
- 3D 데이터에서 제안된 방법은 상당한 강건성을 보여주었으며, 특히 전통적인 k-means가 불량한 초기화로 인해 특정 반복에서 정확도가 ~60%까지 떨어졌던 분산 0.5 시나리오에서도 제안된 방법은 100%에 근접한 성능을 유지했다.
벤치마크 데이터:
- Iris: 제안된 방법의 정확도는 **84.20%**로, 전통적 방식(77.51%)보다 높았다. 제안된 방법은 전통적 방식이 오분류한 특정 이상치를 정확히 식별하기도 했다.
- Wine: 제안된 방법의 정확도는 **75.16%**로, 전통적 방식(66.37%)보다 높았다. 제안된 방법은 반복 과정에서 현저히 낮은 변동성을 보였다.
- Breast Cancer: 차이는 미미했으나(96.12% 대 95.82%), 제안된 방법이 더 일관되고 변동성이 적은 모습을 보였다.

의의 및 주장
본 논문은 WCD와 함께 ICD 지표를 포함하는 것이 더 강건한 클러스터링 알고리즘을 만든다고 주장한다. 주요 기여는 다음과 같다:

강건성 향 향상: 이중 지표 접근 방식은 초기 클러스터 중심 위치에 대한 민감도를 줄여, 더 일관된 수렴과 알고리즘이 불량한 지역 최적해에 빠지는 사례를 감소시킨다.
이상치 처리: 제안된 방법은 전통적인 방법과 비교하여 이상치를 실제 클러스터로 올바르게 분류하는 데 있어 우수한 능력을 입증했다.
정량적 검증: 합성 데이터나 질적 평가에만 의존하는 많은 선행 연구와 달리, 본 연구는 포괄적인 지표(정확도, 정밀도, 재현율, F1)를 사용하여 실제 벤치마크 데이터셋에서 알고리즘을 검증했다.
고차원 적용 가능성: 알고리즘이 저차원 가우시안 데이터용으로 개념화되었음에도 불구하고, 9차원 Breast Cancer 데이터셋에 대한 스트레스 테스트는 이 접근 방식이 고차원 응용 분야에서도 충분히 강건함을 시사한다.

저자들은 고차원 사례에서 정확도 이득이 완만할 수 있지만, 변동성을 줄이고 모호한 데이터 구조를 개선하는 능력이 클러스터 내 동질성과 클러스터 간 이질성을 모두 최적화하는 것이 더 우수한 클러스터링 솔루션을 제공한다는 가설을 입증한다고 결론지었다. 본 연구는 k-means의 초기화 민감도를 해결하기 위한 미세한 수치적 방법론에 대한 후속 연구의 전례를 마련한다.

유사한 논문