💻 computer science

CCKM: A Modified k-means Clustering using Concentric Circles

이 논문은 PCA로 차원이 축소된 공간에서 동심원 및 사분면 기반의 중심점 초기화 전략을 활용하여 여러 데이터셋과 평가 지표에 걸쳐 기존의 k-means 및 그 전신인 ECKM을 일관되게 능가하는 결정론적 k-means 클러스터링 알고리즘인 CCKM을 소개한다.

원저자: Barun Kr. Paul, Kinsuk Giri

게시일 2026-09-29

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Barun Kr. Paul, Kinsuk Giri

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

현대 데이터의 광대하고 고요한 대양 속에서, 라벨이나 명확한 경계 없이 떠다니는 수십억 개의 정보 지점들을 마주하며 과학자들은 종종 패턴을 찾아내야 합니다. 그들은 이 혼돈을 의미 있는 그룹으로 분류해야 하며, 이 작업은 클러스터링(clustering)이라고 알려져 있습니다. 모든 책이 제목도 없이 바닥에 뒤섞여 던져진 거대한 도서관을 정리한다고 상상해 보십시오. 이 컬렉션을 이해하기 위해, 당신은 내용에 따라 어떤 책들이 함께 속하는지 결정하여 유사한 이야기를 공유하는 더미들로 묶어야 합니다. 이것이 클러스터링의 근본적인 과제입니다. 즉, 뒤섞인 데이터셋을 가져와 각 그룹 내부의 항목들이 다른 그룹의 항목들보다 서로 더 닮아 있는 뚜렷한 클러스터들로 나누는 것입니다.

이 작업을 위한 가장 흔한 도구 중 하나는 k-means라고 불리는 알고리즘입니다. 이 알고리ло은 센트로이드(centroids)라고 불리는 몇 개의 시작점을 선택한 다음, 모든 데이터 지점이 가장 가까운 곳에 합류하도록 요청합니다. 데이터 지점들이 그룹을 선택하고 나면, 알고리즘은 실제 지점들이 위치한 곳을 기준으로 각 그룹의 중심을 재계산하고, 다시 한번 지점들에게 선택을 요청합니다. 이 순환은 그룹이 더 이상 변하지 않을 때까지 반복됩니다. 그러나 이 과정의 성공 여부는 전적으로 그 첫 번째 시작점들이 어디에 배치되느냐에 달려 있습니다. 만약 초기 추측이 좋지 않다면, 알고리즘은 최적이 아닌 배치에 갇혀, 깔끔해 보이지만 잘못된 이야기를 전달하는 지저분하고 부정확한 책 더미로 책들을 분류하게 될 수 있습니다. 수년간 연구자들은 무작위 추측에서 벗어나 더 의도적이고 기하학적인 전략을 사용하여 이러한 문제를 해결할 더 나은 방법을 찾기 위해 노력해 왔습니다.

최근 연구에서 인도의 바룬 크리슈나 팔(Barun Kr. Paul)과 긴수크 기리(Kinsuk Giri) 연구진은 이 초기 추측 문제를 다루는 새로운 방법을 제안했습니다. 그들은 동심원 기반 k-means, 즉 CCKM이라 불리는 방법을 도입했습니다. 무작위로 추측하거나 계산하기 어려운 복잡한 기하학적 모양을 사용하는 대신, 그들의 접근 방식은 단순하고 직관적인 아이디어, 즉 데이터의 중심을 기준으로 원을 그리는 것에 의존합니다. 연구진은 먼저 전체 데이터셋을 2차원으로 축소하여, 점들 사이의 관계가 보존되는 평면 지도를 만듭니다. 그런 다음 이 지도 위에서 모든 데이터 지점의 정확한 중심을 찾아 이를 원점, 즉 과녁의 중심점으로 취급합니다.

이 중심점에서 연구팀은 중심은 같지만 크기는 서로 다른 일련의 원들을 그리는데, 이는 마치 과녁의 동심원 링과 같습니다. 이 원들은 원들 사이의 공간을 뚜렷한 띠, 즉 고리(ring)로 나눕니다. 그다음 연구진은 각 고리에 얼마나 많은 데이터 지점이 떨어져 있는지 계산합니다. 각 고리 내에서 그들은 네 개의 구석, 즉 사분면(quadrant)을 살펴보고 어느 쪽이 가장 붐비는지 확인합니다. 그들은 각 고리에서 가장 붐비는 사분면의 중심을 새로운 클러스터의 시작점으로 선택합니다. 이렇게 함으로써, 그들은 시작점들이 데이터 전체에 걸쳐 퍼져 있고, 빈 공간에 떠 있거나 우연히 뭉쳐 있는 것이 아니라 실제 데이터가 밀집된 곳에 배치되도록 보장합니다.

연구팀은 이 새로운 방법을 표준 k-means 알고리즘 및 이전의 기하학적 방법인 빈 원 기반 k-means(Empty Circle based k-means)와 비교 테스트했습니다. 그들은 단순한 분리된 그룹부터 분류하기 어려운 복잡하고 구불구불한 형태에 이르기까지 열 가지의 서로 다른 데이터셋에 대해 실험을 수행했습니다. 결과는 그들의 동심원 접근 방식이 매우 효과적임을 보여주었습니다. 대부분의 테스트에서 새로운 방법은 무작위 방식보다 더 깨끗하고 정확한 그룹을 생성했습니다. 더 중요한 것은, 이 방법이 훨씬 더 빠르게 안정적인 해답에 도출되었다는 점입니다. 여러 데이터셋에서 새로운 방법은 작업을 마치는 데 현저히 적은 단계를 요구했습니다. 예를 들어, 한 데이터셋에서는 표준 방식이 8단계가 걸린 반면 단 4단계 만에 수렴했으며, 다른 데이터셋에서는 14단계 대신 7단계 만에 작업을 마쳤습니다. 이 속도는 컴퓨터가 계산하는 데 시간을 덜 쓰고 결과를 전달하는 데 더 집중할 수 있다는 점에서 매우 중요합니다.

이 연구는 또한 이 방법이 빛을 발하는 부분과 한계가 있는 부분을 강조했습니다. 이 방법은 데이터가 경로를 따라 배열되거나 불꽃 모양의 곡선 형태를 띠는 것과 같이 비선형적인 모양을 가진 데이터셋에서 탁월한 성능을 보였으며, 표준 방식이 종종 어려움을 겪는 부분에서도 그러했습니다. 또한 최대 15개의 뚜렷한 클러스터를 가진 시나리오를 성공적으로 처리하며 중간 규모의 그룹 수를 다루는 데에도 뛰어난 성과를 보였습니다. 그러나 연구진은 클러스터의 수가 데이터 크기에 비해 매우 커질 경우, 동심원의 경직된 구조가 제한 요소가 될 수 있다고 언급했습니다. 이러한 특정 고밀도 시나리오에서는 이 방법이 데이터를 분류하는 데 표준 방식보다 더 많은 단계가 필요하기도 했습니다. 이러한 경계에도 불구하고, 전반적인 연구 결과는 초기 클러스터 배치를 유도하기 위해 단순한 동심원을 사용하는 것이 복잡한 데이터를 조직화하는 강력하고 효율적이며 신뢰할 수 있는 방법임을 시사합니다. 연구진은 다른 사람들이 이 결과를 검증하고 자신들의 데이터 분류 과제에 이 기하학적 논리를 적용할 수 있도록 코드와 데이터를 공개했습니다.

기술 요약: CCKM – 동심원을 이용한 수정된 k-평균 클러스터링

문제 정의
전통적인 k-평균(k-means) 클러스터링 알고리즘은 단순성과 계산 효율성 덕분에 널리 사용되지만, 초기 중심점(centroid) 선택에 대한 민감성이라는 치명적인 취약점을 가지고 있다. 일반적인 무작위 초기화는 좋지 않은 지역 최적점(local optima)으로 수렴하여 부적절한 분할을 초래하고, 과도한 반복으로 인해 계산 시간을 증가시킨다. 통계적 휴리스틱부터 공집합 원 기반 k-평균(ECKM)과 같은 복잡한 계산 기하학적 접근 방식에 이르기까지 다양한 초기화 전략이 존재하지만, 기존의 기하학적 솔루션들이 가진 높은 구조적 복잡성을 피하면서도 기하학적으로 일관되고, 계산 효율적이며, 다양한 클러스터 기하 구조에 걸쳐 강건한 방법론에 대한 필요성이 여전히 남아 있다.

방법론: 동심원 기반 k-평균 (CCKM)
본 논문은 무작위 선택을 대신하여 동심원과 사분면 분할에 기반한 기하학적 절차를 사용하는 결정론적 중심점 초기화 기법인 CCKM을 제안한다. 알고리즘은 다음 단계로 작동한다:

전처리: 데이터셋은 z-점수 정규화를 통해 표준화되며, 평면 기하 구조 구축을 용이하게 하기 위해 주성분 분석(PCA)을 사용하여 2차원 공간으로 투영된다.
전역 중심점 계산: PCA로 축소된 데이터의 전역 중심점 $(C_x, C_y)$ 를 계산하고 이를 좌표계의 원점으로 설정한다.
동심원 구축: 원점으로부터 모든 데이터 포인트까지의 유클리드 거리를 계산하여 가장 가까운 점($np $)과 가장 먼 점($ fp $)을 식별한다.$ np $와$ fp $사이의 방사형 범위는$ k $개의 동일한 간격(원하는 클러스터 수$ k $)으로 나뉘어,$ k+1 $개의 동심원을 생성한다. 이는$ k$개의 환형 영역(annuli, 고리 모양 영역)을 정의한다.
사분면 분할: 각 환형 영역 내의 데이터 포인트들은 전역 중심점을 기준으로 4개의 사분면으로 세분화된다.
초기 중심점 선택: 각 환형 영역 내에서 가장 높은 데이터 밀도를 가진 사분면("타겟 사분면")을 식별한다. 이 타겟 사분면 내에 있는 점들의 기하학적 중심점이 해당 클러스터의 초기 중심점으로 선택된다.
실행: 이 $k$ 개의 결정론적 중심점들은 표준 반복적 k-평균 알고리즘의 시작점으로 사용된다.

주요 기여

새로운 초기화 전략: 본 논문은 ECKM에서 사용되는 보로노이 다이어그램(Voronoi diagrams)이나 볼록 껍질(convex hulls)과 같은 복잡한 계산 기하학적 구조 대신, 단순한 유클리드 기하학(동심원 및 환형)을 활용하는 결정론적 중심점 초기화 방법을 도입하였다.
계산 효율성: CCKM의 초기화 단계는 $O(nk) $의 시간 복서를 가지며, 이는 ECKM의 기하학적 구조 구축과 관련된$ O(n^2) $복잡도를 피한다. CCKM 알고리즘의 전체 복잡도는$ O(nd^2 + nkt)$(PCA 전처리 및 k-means 반복에 의해 결정됨)이지만, 특정 초기화 단계는 ECKM의 $O(nd^2 + n^2 + nkt)$ 와 비교했을 때 계산 비용과 클러스터 품질 사이에서 더 유리한 절충안을 제공한다.
결정론적 재현성: 무작위 초기화와 달리, CCKM은 주어진 데이터셋에 대해 일관된 결과를 생성하여 확률적 시작점에서 발생하는 변동성을 제거한다.

실험 결과
저자들은 10개의 벤치마크 데이터셋(Iris, Seeds, Ecoli 및 Aggregation, R15, D31과 같은 합성 데이터셋 포함)을 대상으로 7가지 지표(수렴까지의 반복 횟수(IT), 실루엣 점수(SH), 데이비스-볼딘 지수(DB), 균질도(HM), 완결성(CM), 평균 유클리드/맨해튼 클러스터 내 거리)를 사용하여 CCKM을 표준 k-평균(KM) 및 ECKM과 비교 평가하였다.

전반적인 성능: 70개의 지표-데이터셋 쌍 전체에서 CCKM은 50개 사례(71.4%)에서 최고 또는 공동 최고 값을 달축성하였으며, 이는 ECKM(47.1%)과 KM(35.7%)을 상회하는 수치이다.
수렴 속도: CCKM은 수렴에 필요한 반복 횟수를 일관되게 감소시켰다. 특히 Pathbased(7 vs. 12/14), Seeds(5 vs. 11/11), Iris(4 vs. 6/8) 데이터셋에서 주목할 만한 감소가 관찰되었다.
클러스터 품질: CCKM은 비볼록 체인(Chainlink), 경로 형태 구조(Pathbased), 이질적 밀도(Aggregation)와 같은 복잡한 기하 구조를 가진 데이터셋에서 우수한 성능을 보였다. 예를 들어, Aggregation 데이터셋에서 CCKM은 KM(0.8905)과 ECKM(0.8830)보다 현저히 높은 0.9287의 균질도 점수를 달성했다.
한계점: 논문은 높은 $k$ 및 큰 $n$ 시나리오(예: $k=31$ 인 D31 데이터셋)에서의 한계를 명시적으로 언급하였다. 이러한 경우, 고정된 동심원 구조(하나의 환형당 하나의 중심점)는 솔루션 공간을 충분히 커버하지 못해 베이스라인 모델들에 비해 최적화되지 않은 시딩(seeding)을 초래한다. 또한, PCA 축소에 대한 의존성 때문에 첫 두 개의 주성분이 실제 클러스터 구조를 포착하지 못할 경우 성능이 저하될 수 있다.

의의 및 주장
저자들은 CCKM이 분할 클러스터링(partitional clustering)을 위한 "단순하고, 기하학적으로 일관되며, 계산 효율적인" 중심점 초기화 대안을 제공한다고 주장한다. 본 연구의 의의는 기초적인 기하학적 개념(동심원 및 사분면)이 무작위 초기화를 효과적으로 대체하여 최종 클러스터링의 품질과 수렴 속도를 모두 개선할 수 있음을 입증한 데 있다. 저자들은 CCKM을 모든 클러스터 토폴로지를 위한 보편적인 솔버가 아니라, 표준 k-평균이나 복잡한 기하학적 초기화 도구(ECKM 등)가 성능이 저하되거나 더 높은 계산 비용을 발생시킬 수 있는 비자명한 기하 구조를 가진 데이터셋을 위한 강건한 방법론으로 포지셔닝한다. 저자들은 CCKM이 명확한 경계(특히 높은 $k$ 확장성 및 PCA 의존성 관련)를 가지고 있지만, 결정론적 초기화 전략의 중요한 진전임을 결론짓는다.

유사한 논문