수학 개념 지도
데이터와 학습(Data and learning)

k-평균 군집(K-means clustering)

점들을 k개의 무리로 나누되, 각 점과 그 무리 중심 사이 거리 제곱의 합이 작아지도록 '가장 가까운 중심에 배정'과 '중심을 평균⁠(mean)⁠으로 옮기기'를 되풀이하는 방법.

min⁡C1,…,Ck∑j=1k∑x⃗∈Cj∥x⃗−μ⃗j∥2,μ⃗j=1∣Cj∣∑x⃗∈Cjx⃗\min_{C_1,\dots,C_k} \sum_{j=1}^{k} \sum_{\vec x \in C_j} \lVert \vec x - \vec\mu_j \rVert^2, \qquad \vec\mu_j = \frac{1}{|C_j|}\sum_{\vec x\in C_j}\vec x
먼저 보면 좋은 개념벡터기댓값최적화

이름표가 없는 점 150개를 k = 개의 무리로 나누고 싶습니다. 큰 점은 무리의 중심 후보입니다. 로이드 알고리즘⁠(Lloyd's algorithm)⁠이라 불리는 방법은 두 단계를 번갈아 합니다. 배정: 모든 점을 가장 가까운 중심의 무리에 넣습니다. 갱신: 각 중심을 제 무리 점들의 평균 자리로 옮깁니다. 아래 막대로 한 단계씩 넘겨 보세요. 큰 점은 직접 끌 수도 있습니다.

무작위로 다시 시작 나쁜 시작

배경의 색 영역은 각 중심이 가장 가까운 곳, 곧 중심들의 보로노이 칸입니다.

이 방법이 줄이려는 값은 각 점에서 제 무리 중심까지 거리 제곱의 합, 지금 입니다. 두 단계 모두 이 값을 결코 키우지 않습니다. 배정에서는 점마다 더 가까운 중심을 고르니 줄거나 그대로이고, 갱신에서는 평균이 거리 제곱의 합을 가장 작게 만드는 자리라서 역시 줄거나 그대로입니다. 거리의 합이 아니라 거리 제곱의 합이어야 평균이 답이라는 점은 중앙값⁠(median)⁠과 평균을 비교하면 보입니다. 나눔이 바뀔 때마다 값이 실제로 줄어들므로(거리가 같은 중심 사이에서는 늘 같은 규칙으로 고른다면) 한 번 떠난 나눔으로는 돌아오지 않고, 점을 나누는 방법은 유한하므로 반복은 반드시 어딘가에서 멈춥니다.

단계마다 기록한 거리 제곱합. 청록 점선은 무작위로 스무 번 시작해 얻은 가장 좋은 값입니다.

그러나 멈춘 곳이 가장 좋은 답이라는 보장은 없습니다. '나쁜 시작'을 누르고 ▶로 끝까지 돌려 보세요. 중심 두 개가 왼쪽 무리를 반으로 쪼개 나눠 갖고, 나머지 하나가 오른쪽의 두 무리 사이에 끼인 채로 멈춥니다. 어느 한 단계로도 더 나아질 수 없는 국소 최솟값입니다. 가장 좋은 나눔을 찾는 문제는 일반적으로 계산이 매우 어려운 문제(NP-난해⁠, NP-hard⁠)로 알려져 있어서, 실제로는 여러 번 무작위로 시작해 가장 좋은 답을 고르거나, 이미 고른 중심에서 먼 점일수록 높은 확률⁠(probability)⁠로 다음 시작점으로 뽑는 k-means++(2007) 같은 방법을 씁니다. 이것도 최적화⁠(optimization)⁠에서 흔히 만나는 함정입니다. 손실을 줄이는 쪽으로만 조금씩 움직이는 경사 하강법⁠(gradient descent)⁠도 같은 국소 최솟값⁠(local minimum)⁠에 걸릴 수 있습니다.

배경의 영역은 중심들이 만드는 보로노이 다이어그램⁠(Voronoi diagram)⁠입니다. 보로노이 칸은 늘 볼록하므로(칸 안의 두 점을 잇는 선분이 칸을 벗어나지 않으므로) k-평균의 무리들은 볼록한 칸으로 서로 갈라지고, 초승달이나 고리 모양의 무리는 찾지 못합니다. 유클리드 거리⁠(Euclidean distance)⁠의 제곱을 쓰기 때문에 축의 단위에 민감하고 멀리 떨어진 이상값⁠(outlier)⁠에 끌려갑니다. 맨해튼 거리⁠(Manhattan distance)⁠의 합을 줄이도록 바꾸면 중심은 평균 대신 좌표별 중앙값이 되는데, 이것이 k-중앙값 군집입니다. k는 어떻게 고를까요? k를 키우면 거리 제곱합은 늘 줄어들어 k가 점의 개수이면 0이 되므로, k에 따른 거리 제곱합을 그려서 값이 크게 줄다가 완만해지는 꺾이는 곳(팔꿈치처럼 꺾인다고 엘보 방법⁠(elbow method)⁠이라 부릅니다)을 고르는 경우가 많습니다.

이 반복은 스튜어트 로이드가 1957년 벨 연구소에서 신호를 몇 단계의 값으로 나타내는(양자화⁠, quantization⁠) 문제로 적은 보고서에 나오며, 논문으로는 1982년에야 나왔습니다. 'k-means'라는 이름은 1967년 미국의 통계학자 제임스 매퀸이 붙였습니다.

이어지는 곳. 이름표를 보고 배우는 최근접 이웃 분류⁠(k-nearest neighbors classification)⁠와 달리, k-평균은 정답 이름표 없이 데이터만 보고 구조를 찾는 비지도 학습입니다(기계 학습⁠, machine learning⁠). 무리마다 정규분포⁠(normal distribution)⁠를 가정하고 점을 확률로 부드럽게 나눠 배정하면 가우스 혼합⁠(Gaussian mixture)⁠ 모형이 되고, 그때 무리마다의 거리는 마할라노비스 거리⁠(Mahalanobis distance)⁠가 됩니다. 거꾸로 무리들이 모두 폭이 같은 둥근 정규분포라고 두고 그 폭을 0으로 줄이면, 가우스 혼합을 맞추는 EM 알고리즘⁠(algorithm)⁠의 부드러운 배정이 가장 가까운 중심으로의 배정이 되어 k-평균으로 돌아갑니다. 사진의 수많은 색을 k가지로 줄이는 것도 k-평균이고, 옮기는 비용을 거리 제곱으로 잡고, 데이터를 점 k개짜리 분포로 가장 싸게 옮기는 최적 수송⁠(optimal transport)⁠ 문제로 보아도 같은 답이 나옵니다. 차원이 높은 자료는 주성분 분석⁠(principal component analysis)⁠으로 먼저 줄인 뒤 군집을 찾기도 합니다. 점들의 최소 신장 트리⁠(minimum spanning tree)⁠에서 가장 긴 변 k − 1개를 끊어 k개 무리로 나누는 방법(단일 연결 군집⁠, single-linkage clustering⁠)은 k-평균과 달리 초승달처럼 길쭉한 무리도 찾아냅니다. 입력 공간을 영역으로 나눠 영역마다 담당자를 두는 생각은 전문가 혼합⁠(mixture of experts)⁠의 라우터⁠(router)⁠와 닮았는데, 거기서는 중심까지의 거리 대신 학습된 벡터⁠(vector)⁠와의 내적⁠(dot product)⁠으로 담당 '전문가'를 고르고, 영역도 모델의 손실을 줄이도록 함께 학습됩니다.

관련 인물루트비히 비트겐슈타인로널드 피셔
이 개념이 나오는 큰 생각가장 좋은 것 고르기

이 개념이 나오는 긴 글

거리와 유사도 까마귀와 택시 까마귀는 곧장 날고 택시는 블록을 돌아간다. '얼마나 먼가'에는 답이 하나가 아니고, 어떤 거리를 고르느냐가 통계와 기계 학습의 답을 바꾼다. 라플라시안 라플라시안, 가장 많이 재사용된 식 이웃의 평균에서 나를 뺀다. 이 한 줄이 열의 법칙이고, 도박꾼이 이길 확률이고, 전기 회로와 나무 세기이고, 북의 음색이고, 사진의 윤곽선이고, 그래프를 가르는 칼이고, 잡음에서 그림을 빚는 확산 모델의 밑그림이다.

이 개념 위에 세워진 것

EM 알고리즘과 가우스 혼합

이 개념을 언급하는 페이지

  • 최적화

    … 최선이 보장되는 문제는 구조가 특별한 경우입니다. 점들을 무리 지어 중심까지의 거리 제곱합을 줄이는k-평균 군집은 시작점에 따라 다른 골짜기에 빠지는 최적화의 좋은 예입니다. 여기서 골짜기는 주변보다는 낮지만 전체에서 …

  • 마할라노비스 거리

    … 거리는 B를 거쳐 가는 거리보다 길 수 없다)까지 지키는 진짜 거리 함수라서, 최근접 이웃 분류나k-평균 군집에서 유클리드 거리 대신 쓸 수 있습니다. 인도의 통계학자 프라산타 찬드라 마할라노비스가 여러 집단의 …

  • 최근접 이웃 분류

    … 거의 모든 점이 비슷하게 멀어져 '가장 가까운 이웃'이 뜻을 잃습니다(차원의 저주). 이름이 비슷한k-평균 군집은 이름표 없이 무리를 찾는 전혀 다른 방법입니다. 지금까지 찾은 가장 가까운 k개를 힙에 담아 두면, …

  • 차원의 저주

    … 모두가 모두에게서 비슷하게 멀면, '가장 가까운 이웃'을 찾는 최근접 이웃 분류나 가까운 점끼리 묶는k-평균 군집은 기댈 곳을 잃습니다. 까닭은 큰 수의 법칙입니다. 유클리드 거리의 제곱은 좌표마다의 차이 제곱을 …

  • 최적 수송

    … 매기면 평균입니다. 같은 거리 제곱 비용으로 데이터를 점 k개짜리 분포로 가장 싸게 옮기는 문제의 답은k-평균 군집의 답과 같습니다. 참 분포의 기댓값이 유한하면, 표본으로 만든 분포는 표본이 늘수록 참 분포에 바서슈타인 …

  • 거리 함수

    … 보다 커지니 제곱 거리의 삼각부등식이 깨지고, 직각이면 등호가 됩니다. 그래도 최소제곱법(선형 회귀)과k-평균 군집은 일부러 이 제곱 거리를 줄입니다. 제곱은 매끄러워서 미분하기 쉽고, 내적과 정사영으로 답이 …

  • 유클리드 거리

    … = 2/3입니다. 점들 사이를 지나는 직선을 찾는 최소제곱법의 선형 회귀와, 점들을 몇 무리로 나누는k-평균 군집도 제곱 거리의 합이 가장 작아지도록 답을 고릅니다. 종 모양의 정규분포도 거리로 읽을 수 있습니다. …

  • 보로노이 다이어그램

    … 점마다 가장 가까운 중심에 배정하고(보로노이 영역) 중심을 영역의 무게중심으로 옮기기를 되풀이하는 것은k-평균 군집을 푸는 로이드 알고리즘입니다(1957년 벨 연구소의 스튜어트 로이드가 제안). 무게중심은 영역 안 …

  • 은닉 마르코프 모델

    … 관측열의 확률이 줄지 않습니다. 중심으로 무리를 나누고, 나눈 무리로 중심을 다시 구하기를 되풀이하는k-평균 군집도 같은 '번갈아 고치기' 계열(기댓값 최대화, EM)의 방법입니다. 언어에서는 숨은 상태가 품사, …

  • 단어 임베딩

    … 수백 개만 남겨 낱말 벡터를 얻습니다. 벡터가 생기면 거리로 무리를 나눌 수 있어서, 임베딩 공간에서k-평균 군집을 돌리면 뜻이 비슷한 낱말 무리가 나옵니다. 앞 낱말 몇 개로 다음 낱말을 맞히는 n-그램 모델은 본 …

  • 경사 하강법

    … 한쪽으로는 오르고 다른 쪽으로는 내려가는 안장점일 수도 있고, 극소라 해도 최소라는 보장이 없습니다.k-평균 군집이 나쁜 시작에서 멈추는 것도 같은 모양입니다. 경사 하강법이 보장하는 것은 이 정도입니다. 기울기가 …

  • 최소 신장 트리

    … 나뉩니다. 이것을 단일 연결 군집이라 하며, 가까운 이웃을 사슬처럼 따라 묶기 때문에 둥근 무리를 가정하는k-평균 군집과 달리 길쭉한 무리도 잘 찾습니다. 두 점 사이를 '잇는 길 가운데 가장 긴 변이 가장 짧은 길의, 그 …

  • 율–왜곡 이론

    … 곧 무게중심입니다. 두 조건을 번갈아 맞추는 것이 로이드 알고리즘이고, 분포 대신 데이터 점에 쓰면 그대로k-평균군집입니다. 점을 한 대표값에 딱 잘라 배정하는 대신 확률로 나눠 배정하면, 정규분포들이 섞인 모형에 대한 …

  • 기계 학습

    … 정답 없이 자료만 주고 그 안의 구조를 찾게 하는 것은 비지도 학습 입니다. 비슷한 것끼리 무리 짓는k-평균 군집, 자료가 가장 넓게 퍼진 방향을 찾는 주성분 분석, 함께 나오는 낱말들로 낱말의 뜻을 벡터로 적는 …

  • EM 알고리즘과 가우스 혼합

    … 비율을 1/2로 고정하면 '더 가능성 높은 성분'은 '평균이 더 가까운 성분'이 되고, 알고리즘은 정확히k-평균 군집의 로이드 알고리즘이 됩니다. 공통 표준편차를 고정하고 0으로 보낼 때 부드러운 책임도가 0과 1로 …

  • 인공지능

    … 확률을 내는 로지스틱 회귀, 가장 가까운 예를 따르는 최근접 이웃 분류, 비슷한 점끼리 묶는k-평균 군집, 자료가 가장 많이 퍼진 방향을 찾는 주성분 분석, 숨은 값을 추측과 갱신을 되풀이해 찾는 ⟦EM …

  • 검색 증강 생성

    … 조금 틀릴 수 있는 대신 훨씬 빠른 근사 최근접 이웃 검색을 씁니다. 역색인(IVF) 방식은 벡터들을k-평균으로 묶어 두고, 질문과 가까운 묶음 몇 개 안에서만 찾습니다. 각 묶음이 맡는 영역은 중심점들의 …

이 페이지가 가리키는 개념

중앙값P 대 NP 문제경사 하강법보로노이 다이어그램유클리드 거리맨해튼 거리벨 연구소율–왜곡 이론최근접 이웃 분류기계 학습정규분포확률EM 알고리즘과 가우스 혼합마할라노비스 거리최적 수송주성분 분석최소 신장 트리전문가 혼합