K-평균 알고리즘

3. 목표

k-평균 클러스터링 알고리즘은 주어진 데이터를 k개의 클러스터로 묶는 방법으로, 각 클러스터 내 데이터와 중심점 간의 거리 제곱합(WCSS)을 최소화하는 것을 목표로 한다.^[79]

n개의 d-차원 데이터 오브젝트 ('''x'''₁, '''x'''₂, …, '''x'''_''n'') 집합이 주어졌을 때, k-평균 알고리즘은 이 데이터들을 각 집합 내 오브젝트 간 응집도를 최대로 하는 $k(\backslash leq\; n)$ 개의 집합 '''S''' = {''S''₁, ''S''₂, …, ''S''_''k''}으로 나눈다.

목표는 다음 식을 최소화하는 클러스터 집합 S를 찾는 것이다.

4. 알고리즘

k-평균 클러스터링 알고리즘은 주어진 데이터를 k개의 클러스터로 묶는 방법으로, 각 클러스터는 중심점(centroid)을 가진다. 이 알고리즘의 목표는 각 데이터와 해당 데이터가 속한 클러스터 중심점 간의 거리 제곱합을 최소화하는 것이다. 이렇게 함으로써 같은 클러스터 내 데이터들은 서로 유사하고, 다른 클러스터의 데이터와는 덜 유사하게 된다.^[79]

• 할당 단계: 각 데이터를 가장 가까운 중심점에 할당한다.
• 업데이트 단계: 각 클러스터의 중심점을 새로 계산한다.

4. 1. 표준 알고리즘 (Naive k-means)

알고리즘을 요약하면 다음과 같다.

위 표에서 '''2'''는 할당 단계에 해당하고, '''3''' 과정은 업데이트 단계에 해당한다.^[79]

K-평균 알고리즘은 일반적으로 다음과 같은 흐름으로 구현된다.^[71][72] 데이터 수를 $n$, 클러스터 수를 $k$로 둔다.

# 각 데이터 $x\_i(i=1,\; \backslash dotsc,\; n)$에 대해 무작위(랜덤)로 클러스터를 할당한다.

# 할당된 데이터를 기반으로 각 클러스터의 중심 $V\_j(j=1,\; \backslash dotsc,\; k)$를 계산한다. 계산은 일반적으로 할당된 데이터의 각 요소의 산술 평균이 사용되지만, 필수적인 것은 아니다.

# 각 $x\_i$와 각 $V\_j$와의 거리를 구하고, $x\_i$를 가장 가까운 중심의 클러스터에 다시 할당한다.

# 위의 처리에서 모든 $x\_i$의 클러스터 할당이 변하지 않은 경우, 또는 변화량이 사전에 설정한 일정 임계값을 밑도는 경우, 수렴했다고 판단하고 처리를 종료한다. 그렇지 않은 경우에는 새롭게 할당된 클러스터에서 $V\_j$를 다시 계산하고 위의 처리를 반복한다.

결과는 최초 클러스터의 무작위 할당에 크게 의존하는 것으로 알려져 있으며, 한 번의 결과로 최상의 결과를 얻을 수 있다고는 할 수 없다. 그렇기 때문에, 몇 번 반복하여 최상의 결과를 선택하는 기법이나, k-means++법처럼 최초 클러스터 중심점의 할당 방법을 고안하는 기법 등이 사용되는 경우가 있다.

이 알고리즘에서는 클러스터 수 k는 처음에 주어진 것으로 정하므로, 최적의 클러스터 수를 선택하기 위해서는 다른 계산 등을 통한 고찰이 필요하다.

4. 2. 초기화 기법

• 무작위 분할 (Random Partition): 각 데이터를 임의의 클러스터에 할당하고, 각 클러스터에 할당된 점들의 평균 값을 초기 중심점으로 설정한다.^[80] 데이터 순서에 독립적이며, 초기 클러스터가 각 데이터에 대해 고르게 분포되기 때문에 각 초기 클러스터의 무게중심이 데이터 집합의 중심에 가깝게 위치하는 경향이 있다.^[82] k-조화 평균이나 퍼지 k-평균에서 선호된다.^[82]
• 포지 (Forgy): 데이터 집합에서 임의의 k개의 데이터를 선택하여 초기 중심점으로 설정한다.^[81] 무작위 분할과 마찬가지로 데이터 순서에 독립적이다.^[80] 초기 클러스터가 임의의 k개의 점들에 의해 설정되기 때문에 각 클러스터의 무게중심이 중심으로부터 퍼져있는 경향이 있다.^[82] EM 알고리즘이나 표준 k-평균 알고리즘에서 선호된다.^[82]
• 맥퀸 (MacQueen): 포지 알고리즘과 마찬가지로 데이터 집합으로부터 임의의 k개의 데이터를 선택하여 초기 중심점으로 설정한다.^[74] 이후 선택되지 않은 각 데이터에 대해 가장 가까운 클러스터를 찾아 데이터를 배당하고, 모든 데이터가 클러스터에 배당되면 각 클러스터의 무게중심을 다시 계산하여 초기 중심점으로 설정한다. 최종 수렴에 가까운 클러스터를 찾는 것은 비교적 빠르지만, 최종 수렴에 해당하는 클러스터를 찾는 것은 매우 느리다.^[83]
• 카우프만 (Kaufman): 전체 데이터 집합 중 가장 중심에 위치한 데이터를 첫 번째 중심점으로 설정하고, 이후 선택되지 않은 각 데이터에 대해 가장 가까운 무게중심보다 선택되지 않은 데이터 집합에 더 근접하게 위치한 데이터를 순차적으로 k개의 중심점이 설정될 때까지 반복한다.^[84] 무작위 분할과 마찬가지로 초기 클러스터링과 데이터 순서에 대해 비교적 독립적이기 때문에 해당 요소들에 의존적인 다른 알고리즘들보다 월등한 성능을 보인다.^[80]

5. 복잡도

일반적인 유클리드 공간에서 k-평균 알고리즘의 최적 해를 찾는 것은 NP-난해 문제이다.^[85][86]

Lloyd 알고리즘의 시간 복잡도는 클러스터의 수, 데이터 벡터의 차원, 데이터 벡터의 수에 각각 비례한다. 또한 알고리즘이 해가 수렴하기까지 반복되므로, 알고리즘이 반복된 횟수에도 비례한다. 즉, n개의 d-차원 데이터 벡터들을 i번의 반복을 통해 k개의 클러스터로 묶는데 걸리는 시간은 $O(nkdi)$이다.

Smoothed analysis 경우의 복잡도는 다항 시간이다. $[0,\; 1]^d$내의 임의의 n개의 점들의 집합에 대해, 집합 내의 각 점들이 평균 0, 분산$\backslash sigma^2$의 정규분포를 이룬다면, 해당 집합을 k개의 클러스터로 묶는데 걸리는 시간이 $O(n^\{34\}k^\{34\}d^8\backslash log^4(n)/\backslash sigma^2)$임이 증명된 바 있다.^[88]

다항을 넘는(superpolynomial) 시간($2^\{\backslash Omega(\backslash sqrt\{n\})\}$)이 걸리는 경우도 존재한다.^[89]

공간 복잡도의 경우, 알고리즘은 각 클러스터의 무게중심 벡터들에 대한 정보를 추가로 저장해야 하고, 이 무게중심 벡터들은 매 반복마다 독립적이기 때문에, k-평균 알고리즘은 $O((n+k)d)$의 공간 복잡도를 가진다.

6. 한계점

K-평균 알고리즘은 다음과 같은 몇 가지 한계점을 가지고 있다.

• 클러스터 개수(k) 설정 문제: 사용자가 사전에 클러스터 개수 k를 지정해야 하며, 적절한 k 값을 선택하기 어렵다. k값에 따라 결과가 완전히 달라지므로, 부적절한 k값은 좋지 않은 결과를 초래할 수 있다. 예를 들어, 실제 클러스터 수보다 k값이 작으면 하나의 클러스터가 여러 개의 클러스터로 분할될 수 있고, k값이 크면 하나의 클러스터가 여러 개로 쪼개질 수 있다.^[51] 따라서, K-평균 알고리즘을 수행할 때는 데이터 집합에서 군집 수 결정을 위한 진단 검사를 실행하는 것이 중요하다.
• 지역 최솟값 수렴 문제: 알고리즘이 전역 최솟값(global optimum)이 아닌 지역 최솟값(local optimum)으로 수렴할 가능성이 있다. 초기 중심값에 따라 결과가 달라지며, 지역 최솟값에 수렴하면 사용자가 기대한 결과를 얻지 못할 수 있다. 이를 완화하기 위해 담금질 기법을 사용하거나, 서로 다른 초기값으로 여러 번 시도하여 가장 낮은 에러 값을 갖는 결과를 선택하는 방법 등이 사용된다.^[51]
• 이상치(outlier) 민감성: 이상치에 민감하게 반응하여 클러스터 중심이 왜곡될 수 있다. 이상값은 다른 데이터와 멀리 떨어진 데이터를 의미하며, 중심점 갱신 과정에서 평균 값을 크게 왜곡시켜 중심점이 실제 클러스터의 중심에서 벗어나 이상치 방향으로 치우치게 만들 수 있다. 이를 방지하기 위해 K-평균 알고리즘을 실행하기 전에 이상값을 제거하거나, k-대푯값 알고리즘을 사용할 수 있다.
• 구형(spherical) 클러스터 가정: 유클리드 거리를 사용하여 중심점으로부터 구형으로 군집화가 이루어지기 때문에, 구형이 아닌 클러스터를 찾는 데에는 적절하지 않다. 주어진 데이터 집합의 분포가 구형이 아닐 경우, 클러스터링 결과가 예상과 다를 수 있다. 이러한 경우에는 DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 알고리즘이나 mean-shift 클러스터링 알고리즘을 사용하면 원하는 결과를 얻을 수 있다.
• 데이터 순서 민감성: 무작위 분할, Forgy, MacQueen 초기화 기법의 경우 데이터의 순서에 따라 결과가 달라질 수 있다.^[71][72]

7. 클러스터 수 결정

k-평균 클러스터링에서 최적의 클러스터 수(''k'')를 결정하는 방법은 다음과 같다.

• Rule of thumb: 데이터의 수가 ''n''일 때, 필요한 클러스터의 수는 $k\; \backslash approx\; \backslash sqrt\{n/2\}$ 와 같이 계산할 수 있다.^[90]
• 엘보 방법 (클러스터링): 클러스터 수를 순차적으로 늘려가면서 결과를 확인한다. 클러스터를 추가했을 때 이전보다 훨씬 더 나은 결과를 나타내지 않는다면, 이전의 클러스터 수를 사용한다.
• 정보 기준 접근법: 클러스터링 모델에 대해 가능도를 계산하여 베이지안 정보 기준 등을 사용한다. k-평균 클러스터링 모델의 경우 가우시안 혼합 모델에 가깝기 때문에, 가우시안 혼합 모델에 대한 가능도를 만들어 정보 기준 값을 설정할 수 있다.^[91]
• 실루엣 (클러스터링): 실루엣 분석은 클러스터링의 품질을 측정하고 결과 클러스터 간의 분리 거리를 나타낸다.^[29] 높은 실루엣 점수는 객체가 자체 클러스터에 잘 일치하고 인접 클러스터에 잘 일치하지 않음을 의미한다.
• 갭 통계량: 갭 통계량은 데이터의 널 참조 분포에서 예상 값과 다른 k 값에 대한 총 클러스터 내 변동을 비교한다.^[30] 최적의 k는 가장 큰 갭 통계량을 생성하는 값이다.
• 데이비스-볼딘 지수: 데이비스-볼딘 지수는 클러스터 간의 분리 정도를 측정하는 것이다.^[31] 이 지수가 낮을수록 분리가 더 잘 된 모델을 나타낸다.
• 칼린스키-하라바스 지수: 이 지수는 조밀함과 분리를 기반으로 클러스터를 평가한다. 클러스터 간 분산과 클러스터 내 분산의 비율을 사용하여 계산되며, 값이 높을수록 클러스터가 더 잘 정의된다.^[32]
• 랜드 지수: 두 클러스터 간의 일치 비율을 계산하여 동일하거나 다른 클러스터에 올바르게 할당된 요소 쌍을 모두 고려한다.^[33] 값이 높을수록 유사성이 크고 클러스터링 품질이 향상된다. 조정된 랜드 지수(ARI)는 우연으로 인한 모든 페어링의 예상 유사성을 조정하여 랜드 지수를 수정한다.^[34]

8. 클러스터링 평가 척도

클러스터링이 얼마나 잘 되었는가를 측정하는 방법으로 내부 평가 혹은 외부 평가, 크게 2가지 방법론을 이용할 수 있다.

8. 1. 내부 평가

8. 2. 외부 평가

• $TP$는 참인 것을 참이라고 답한 것의 개수
• $TN$은 거짓인 것을 거짓이라고 답한 것의 개수
• $FP$는 거짓인 것을 참으로 판정한 것의 개수
• $FN$는 참인 것을 거짓으로 판정한 것의 개수

= \frac{TP}{TP + FP + FN}



이 값은 두 데이터 집합 간의 공통 원소들의 개수를 두 데이터 집합의 합집합의 원소 개수로 나눈 것이다.

9. 응용

k-평균 알고리즘은 시장 분할, 컴퓨터 비전, 지질통계학, 천문학 및 농업 등 광범위한 분야에 적용될 수 있다. 이 기법은 주로 어떤 알고리즘을 수행하기 전 데이터를 전처리하는 용도로 많이 쓰인다.

컴퓨터 비전 분야에서 이미지 분할은 디지털 이미지를 여러 개의 부분, 즉 픽셀들의 집합으로 나누는 과정이다. 이미지 분할의 목표는 주어진 이미지를 단순화하고 이미지 표현 방식을 단순화하여 이미지를 좀 더 분석하기 편한 형태로 만드는 것이다. k-평균 알고리즘을 기반으로 한 이미지 분할 기법을 통해 이미지 내 비슷한 색상 및 위치에 있는 픽셀들끼리 하나의 부분으로 묶을 수 있고, 이를 통해 이미지를 크게 단순화할 수 있다.^[96]

k-평균 알고리즘은 신호 처리 분야에서 나온 것이며, 컴퓨터 그래픽스 분야에서는 색상 양자화를 하는데 사용된다. 색상 양자화는 이미지에 사용된 색의 종류를 k개의 색으로 줄이는 과정이다. 예를 들어, 벡터 양자화는 이미지의 색상 팔레트를 ''k''로 알려진 고정된 수의 색상으로 줄이는 작업과 관련이 있다. 벡터 양자화를 달성하는 데 널리 사용되는 방법 중 하나는 ''k''-평균 클러스터링을 사용하는 것이다. 이 과정에서 ''k''-평균은 이미지의 색상 공간에 적용되어 이미지를 k개의 클러스터로 분할하며, 각 클러스터는 이미지의 고유한 색상을 나타낸다. 이 기술은 특히 유사한 색상을 식별하고 그룹화하는 데 도움이 되는 이미지 분할 작업에 유용하다.

클러스터 분석 시, k-평균 알고리즘은 입력 데이터를 k개의 파티션 (클러스터)으로 나누는 데 사용될 수 있다. 그러나 순수 k-평균 알고리즘은 k 값을 정하기 어렵고, 비 수치 데이터를 입력으로 받았을 때나 임의의 거리 측도를 이용해야 할 때는 사용될 수 없는등 적용성이 떨어진다. 이러한 경우에는 일반적으로 k-평균 알고리즘 이외의 다른 알고리즘을 사용한다.

군집 분석은 데이터 마이닝과 기계 학습의 기본적인 작업으로, 유사성에 따라 데이터 포인트 집합을 클러스터로 그룹화하는 것을 포함한다. ''k''-평균 군집화는 데이터를 k개의 클러스터로 분할하는 데 사용되는 인기 있는 알고리즘이며, 각 클러스터는 중심점으로 표현된다.

예를 들어, 마케팅에서 ''k''-평균 군집화는 유사한 특성이나 행동을 가진 고객을 함께 그룹화하는 시장 세분화에 자주 사용된다.

10. 다른 알고리즘과의 관계

''k''-SVD 알고리즘은 "코드북 벡터"의 희소 선형 결합으로 데이터 포인트를 추정하며, ''k''-평균은 가중치가 1인 단일 코드북 벡터를 사용하는 특수한 경우에 해당한다.^[60]

EM 알고리즘 (기댓값 최대화 알고리즘)은 가우시안 혼합 모델을 이용하며, k-평균 알고리즘과 밀접하게 연관되어 있다.^[97] k-평균 알고리즘은 각 데이터 오브젝트를 하나의 클러스터에만 속하게 하는 반면(hard assignment), EM 알고리즘은 각 클러스터에 속할 확률값으로 표현하여 여러 클러스터에 속할 수 있게 한다(soft assignment).^[58][59]

평균점 이동 클러스터링은 데이터 분포에서 밀도가 가장 높은 곳(최빈값)을 찾아 그룹화한다. k-평균 알고리즘과 달리 클러스터 개수(k)를 미리 지정할 필요가 없지만, 수행 시간이 더 오래 걸린다.^[65]

10. 1. EM 알고리즘

가우시안 혼합 모델을 이용한 EM 알고리즘 (기댓값 최대화 알고리즘)과 k-평균 알고리즘은 밀접하게 연관되어 있다.^[97] k-평균 알고리즘은 각 데이터 오브젝트를 클러스터에 강하게 결속시킨다. 즉, 데이터 오브젝트는 오로지 하나의 클러스터에만 속하는데, 이를 hard assignment라고 한다. 반면, EM 알고리즘은 데이터 오브젝트를 클러스터링할 때 클러스터 소속 여부를 해당 클러스터에서 데이터 오브젝트가 나타날 확률값으로 표현한다. 즉, 데이터 오브젝트들이 k-평균 알고리즘과 다르게 어느 한 클러스터에만 결속되지 않는데, 이를 soft assignment라고 한다.

공분산 행렬을 단위 행렬 (identity matrix)에 ε을 곱한 (εΙ) 가우시안 혼합 모델을 가정할 때, ε은 분산값을 조절하는 파라미터로, 모든 식의 구성요소가 공유한다. 그러면 가우시안 혼합 모델이 주어졌을 때 데이터 오브젝트가 나타날 우도 확률은 다음과 같다.

$$

P(\mathbf{x}\vert\boldsymbol{\mu}_k, \boldsymbol{\sigma}_k) = \frac{1}{(2\pi\epsilon)^{M/2}}\exp \left\{-\frac{1}{2\epsilon} \left\| \mathbf x - \boldsymbol\mu_k \right\|^2\right\}





이 식에서 EM 알고리즘을 k 개의 가우시안 혼합 모델에 적용할 때, ε값을 추정해야 할 값으로 보지 않고 고정된 값으로 만든다. 한편, 데이터 오브젝트 $\backslash mathbf\{x\}\_n$에 대한 가우시안 혼합 모델에서의 사후 확률은 다음과 같다.

$$

\gamma(z_{nk}) = \frac{\sum_{j}{\pi}_j\exp\left\{-\left\| \mathbf x_n - \boldsymbol\mu_j \right\|^2/{2\epsilon} \right\}}



만약 ε값을 0에 근접시키면, 분모의 $\backslash left\backslash |\; \backslash mathbf\; x\_n\; -\; \backslash boldsymbol\backslash mu\_j\; \backslash right\backslash |^2$가 가장 작을 때, 0으로 가장 천천히 근접해갈 것이다. 따라서, 그 경우에 데이터 오브젝트 $\backslash mathbf\{x\}\_n$의 사후 확률값 $\backslash gamma(z\_\{nk\})$은 j값 이외의 경우 모두 0으로 근접하게 된다. 즉, $\backslash frac\{\backslash infty\}\{\backslash infty\}$에서 분모에 데이터 오브젝트로부터 가장 가까운 평균값일때만 1이 되고, 그 이외의 경우는 0이 되는 것이다. 결과적으로, 데이터 오브젝트의 사후 확률은 하나의 클러스터에만 1의 값을 가지고, 나머지 클러스터에서는 0의 값을 가지게 된다. 따라서, 데이터 오브젝트 들은 가장 가까운 평균점에 hard-clustering이 되고, 이는 k-평균 알고리즘의 결과와 일치한다.

k-평균 알고리즘에서 클러스터 설정 과정은 EM 알고리즘에서의 E-step에 해당하고, 클러스터 중심 재조정 과정은 M-step에 해당한다.

''k''-평균 클러스터링의 "표준 알고리즘"과 관련 기대값-최대화 알고리즘은 가우시안 혼합 모델의 특수한 경우이며, 특히 모든 공분산을 대각선으로 고정하고 동일하며 무한히 작은 분산을 갖는 극한의 경우이다.^[58] 작은 분산 대신에, "하드" 클러스터 할당을 사용하여 ''k''-평균 클러스터링을 "하드" 가우시안 혼합 모델링의 특수한 경우와 동일하게 나타낼 수도 있다.^[59] 이것은 가우시안 혼합 모델링을 사용하여 ''k''-평균을 계산하는 것이 효율적이라는 의미는 아니지만, 단지 이론적인 관계가 있다는 것과 가우시안 혼합 모델링이 ''k''-평균의 일반화로 해석될 수 있다는 것을 의미한다.

10. 2. 평균점 이동 클러스터링 (Mean-shift clustering)

평균점 이동 클러스터링은 비모수적인 클러스터링 방법으로, 데이터 오브젝트들의 분포에서 그 밀도가 가장 높은 곳 (mode - 최빈값)을 찾는 방식으로 그룹화를 수행한다. 이 알고리즘은 각 데이터 오브젝트에서 미리 지정된 크기의 윈도우 이내의 데이터 오브젝트들을 찾고, 윈도우 내의 평균 값을 구한다. 그리고 그 평균값에서 같은 크기의 윈도우 이내의 데이터 오브젝트들을 찾고, 윈도우 내의 평균 값을 구하는 방식을 반복한다. 이 과정을 반복하면 데이터 오브젝트들의 지역 밀도가 최대인 곳에서 윈도우의 움직임이 멈추게 되는데, 이곳이 데이터 오브젝트 밀도의 지역 최댓값 (최빈값)이다. 이런 방식으로 모든 데이터 오브젝트에 대해 지역 최댓값을 알아낸다. 이 때, 같은 최빈값으로 수렴한 데이터 오브젝트는 같은 클러스터로 간주하고, 한 클러스터로 묶어준다.

k-평균 알고리즘과 달리 k값을 필요로 하지 않는다는 장점이 있다. 하지만 모든 데이터 오브젝트로부터 무게 중심 이동 과정을 수렴할 때까지 거쳐야 하므로 k-평균 알고리즘보다 수행 시간이 훨씬 오래 걸린다.^[65]

평균점 이동 클러스터링은 컴퓨터 비전 및 이미지 프로세싱 분야에서 주로 사용되며, 이미지 분할, 객체 추적 등에 이용된다.

기본적인 평균 이동 클러스터링 알고리즘은 입력 데이터 세트와 동일한 크기의 데이터 포인트 집합을 유지한다. 처음에 이 집합은 입력 집합에서 복사된다. 그런 다음 모든 점은 주변 점들의 평균을 향해 반복적으로 이동한다. 반대로, ''k''-평균은 클러스터 집합을 ''k''개의 클러스터로 제한하며, 일반적으로 입력 데이터 세트의 점 수보다 훨씬 적으며, 중심점을 위해 다른 점보다 해당 점에 더 가까운 이전 클러스터의 모든 점의 평균을 사용한다(예: 각 업데이트 점의 보로노이 분할 내). ''k''-평균과 유사한 평균 이동 알고리즘인 ''가능도 평균 이동''은 변경되는 집합을 주어진 거리 내에 있는 입력 집합의 모든 점의 평균으로 대체한다. 평균 이동 클러스터링이 ''k''-평균보다 갖는 장점은 클러스터 수를 결정하는 매개변수가 없기 때문에 데이터 세트에서 임의의 수의 클러스터를 감지한다는 것이다. 평균 이동은 ''k''-평균보다 훨씬 느릴 수 있으며, 여전히 대역폭 매개변수를 선택해야 한다.

11. 변형

K-평균 알고리즘은 다양한 방식으로 변형되어 사용될 수 있다.

• 젠크스 자연 휴식 최적화: 단변량 데이터에 적용되는 ''k''-평균 알고리즘의 일종이다.
• ''k''-중앙값 클러스터링: 각 차원에서 평균 대신 중앙값을 사용하여 $L\_1$ 노름(택시 기하학)을 최소화한다.
• ''k''-메도이드 (PAM, Partitioning Around Medoids): 평균 대신 메도이드를 사용하여 임의의 거리 함수에 대한 거리 합을 최소화한다.
• 퍼지 C-평균 클러스터링: 각 데이터 포인트가 각 클러스터에 대해 퍼지 정도를 갖는 ''k''-평균의 소프트 버전이다.
• 가우시안 혼합 모델: 기대값 최대화 알고리즘(EM 알고리즘)으로 학습되며, 클러스터에 대한 확률적 할당을 유지하고, 평균 대신 다변량 가우시안 분포를 사용한다.
• ''k''-평균++: WCSS 목표에 대한 증명 가능한 상한을 제공하는 방식으로 초기 중심을 선택한다.
• 필터링 알고리즘: ''k''-d 트리를 사용하여 각 ''k''-평균 단계를 가속화한다.^[35]
• 삼각 부등식: 일부 방법은 삼각 부등식을 사용하여 각 ''k''-평균 단계를 가속화한다.^{[22][23][24][36][25]}
• 클러스터 간 포인트 교환: 지역 최적에서 벗어나기 위해 클러스터 간의 포인트를 교환한다.^[9]
• 구형 ''k''-평균 클러스터링 알고리즘: 텍스트 데이터에 적합하다.^[37]
• 이분 ''k''-평균,^[38] X-평균 클러스터링^[39] 및 G-평균 클러스터링^[40]: 반복적으로 클러스터를 분할하여 계층을 구축하며, 데이터 세트의 최적 클러스터 수를 자동으로 결정하려고 시도한다.
• 내부 클러스터 평가 측정값(예: 클러스터 실루엣): 클러스터 수 결정에 도움을 줄 수 있다.
• 민코프스키 가중치 ''k''-평균: 클러스터별 특징 가중치를 자동으로 계산하여 특징이 다른 특징에서 다른 관련성 정도를 가질 수 있다는 직관적인 아이디어를 지원한다.^[41] 이러한 가중치는 또한 클러스터 유효성 지수가 예상 클러스터 수에서 최적화될 가능성을 높여 주어진 데이터 세트를 다시 스케일링하는 데 사용할 수 있다.^[42]
• 미니 배치 ''k''-평균: 메모리에 맞지 않는 데이터 세트에 대한 "미니 배치" 샘플을 사용하는 ''k''-평균 변형.^[43]
• 오츠의 방법

11. 1. k-중간점 (k-medoids)

k-중간점은 클러스터의 무게중심을 구하기 위해 데이터의 평균 대신 중간점을 사용하는 방식으로, k-평균 알고리즘과 다르게 유클리드 거리뿐 아니라 임의의 거리 함수에 대해서도 동작한다. k-중간점 알고리즘은 1987년 Kaufman과 Rousseeuw에 의해 고안되었다.^[100] 가장 일반적인 예로 중간점 주변 분할 알고리즘이 있다.

k-중간점 알고리즘의 작동 방식은 다음과 같다.

k-중간점 알고리즘의 경우 데이터 간의 거리를 계산하기 위해 대부분의 시간을 소비한다. 때문에 데이터 간 거리 값을 미리 계산하여 저장하거나 휴리스틱 기법 등을 이용하여 알고리즘의 속도를 빠르게 할 수 있다.^[101]

제곱 오차를 최소화하는 클러스터 함수 집합에는 각 클러스터의 중심점을 실제 점 중 하나로 강제하는 접근 방식인 k-메도이드 알고리즘도 포함되어 있는데, 이는 중앙값 대신 중심점을 사용하는 방식이다.

11. 2. k-중앙값 클러스터링 (k-medians clustering)

11. 3. 퍼지 C-평균 클러스터링 (Fuzzy C-means clustering)

퍼지 C-평균 클러스터링은 k-평균 알고리즘의 완화 버전(soft version)이라고 할 수 있다.

11. 4. k-평균++ (k-means++)

k-평균++ 알고리즘은 초기값 설정을 위해 추가적인 시간을 필요로 하지만, 이후 선택된 초기값은 k-평균 알고리즘이 $O(log\; k)$ 시간 안에 최적의 k-평균 해를 찾는 것을 보장한다. 이러한 장점 때문에 k-평균++은 데이터 마이닝에서 일반적으로 사용된다.

참조

_[1] 논문 The (black) art of runtime evaluation: Are we comparing algorithms or implementations?
_[2] conference Some Methods for classification and Analysis of Multivariate Observations http://projecteuclid[...] University of California Press 2009-04-07
_[3] 논문 Sur la division des corps matériels en parties
_[4] 논문 Least squares quantization in PCM http://www.cs.toront[...] 2009-04-15
_[5] 논문 Cluster analysis of multivariate data: efficiency versus interpretability of classifications
_[6] 서적 Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining ACM Press 1999
_[7] 서적 Information Theory, Inference and Learning Algorithms http://www.inference[...] Cambridge University Press
_[8] 문서
_[9] 논문 Algorithm AS 136: A ''k''-Means Clustering Algorithm
_[10] conference Alternatives to the ''k''-means algorithm that find better clusterings http://people.csail.[...]
_[11] 논문 A comparative study of efficient initialization methods for the ''k''-means clustering algorithm
_[12] conference Refining Initial Points for ''k''-Means Clustering
_[13] 논문 k-means requires exponentially many iterations even in the plane http://cseweb.ucsd.e[...]
_[14] conference k-means has polynomial smoothed complexity
_[15] 논문 NP-hardness of Euclidean sum-of-squares clustering
_[16] 논문 Random Projection Trees for Vector Quantization 2009-07
_[17] 서적 WALCOM: Algorithms and Computation
_[18] conference Applications of weighted Voronoi diagrams and randomization to variance-based ''k''-clustering
_[19] 서적 Introduction to information retrieval Cambridge University Press 2008
_[20] 서적 Proceedings of the twenty-second annual symposium on Computational geometry ACM 2006-01-01
_[21] 웹사이트 A theoretical analysis of Lloyd's algorithm for ''k''-means clustering https://gautam5.cse.[...]
_[22] 서적 Acceleration of ''k''-Means and Related Clustering Algorithms Springer 2002
_[23] conference Using the triangle inequality to accelerate ''k''-means http://www-cse.ucsd.[...]
_[24] 서적 Proceedings of the 2010 SIAM International Conference on Data Mining 2010
_[25] 서적 Partitional Clustering Algorithms 2015
_[26] 문서
_[27] 문서
_[28] 간행물 Stop using the elbow criterion for k-means and how to choose the number of clusters instead ACM SIGKDD Explorations Newsletter 2023-06-22
_[29] 문서
_[30] 문서
_[31] 문서
_[32] 문서
_[33] 문서
_[34] 문서
_[35] 논문 An efficient ''k''-means clustering algorithm: Analysis and implementation http://www.cs.umd.ed[...] 2009-04-24
_[36] 논문 Accelerated ''k''-means with adaptive distance bounds http://opt.kyb.tuebi[...] 2012
_[37] 논문 Concept decompositions for large sparse text data using clustering
_[38] 논문 "A comparison of document clustering techniques". In
_[39] 논문 X-means: Extending ''k''-means with Efficient Estimation of the Number of Clusters http://cs.uef.fi/~zh[...] 2000-06
_[40] 논문 Learning the k in k-means http://papers.nips.c[...]
_[41] 논문 Minkowski Metric, Feature Weighting and Anomalous Cluster Initialisation in ''k''-Means Clustering
_[42] 논문 Recovering the number of clusters in data sets with noise features using feature rescaling factors
_[43] 간행물 Web-scale ''k''-means clustering http://dl.acm.org/ci[...] ACM 2016-12-21
_[44] 웹사이트 Hartigan's Method: ''k''-means Clustering without Voronoi http://proceedings.m[...]
_[45] 논문 SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering http://pubsonline.in[...] 2022-03-28
_[46] 논문 Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems
_[47] 논문 Efficiency of random swap clustering
_[48] 논문 J-Means: A new local search heuristic for minimum sum of squares clustering
_[49] 논문 Genetic k-means algorithm https://www.research[...]
_[50] 논문 HG-means: A scalable hybrid metaheuristic for minimum sum-of-squares clustering
_[51] 웹사이트 K-means and ''k''-medoids applet http://www.math.le.a[...] 2016-01-02
_[52] 서적 ICML Association for Computing Machinery 2012-06-26
_[53] 서적 Neural Networks: Tricks of the Trade Springer
_[54] 간행물 Visual categorization with bags of keypoints https://www.cs.cmu.e[...]
_[55] 간행물 An analysis of single-layer networks in unsupervised feature learning http://www.stanford.[...]
_[56] 논문 Three learning phases for radial-basis-function networks
_[57] 간행물 Phrase clustering for discriminative learning http://www.aclweb.or[...]
_[58] 서적 Numerical Recipes: The Art of Scientific Computing Cambridge University Press
_[59] 서적 Machine learning : a probabilistic perspective MIT Press
_[60] 논문 K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation http://www.cs.techni[...]
_[61] 논문 Spectral Relaxation for ''k''-means Clustering http://ranger.uta.ed[...] 2001-12
_[62] 논문 K-means Clustering via Principal Component Analysis http://ranger.uta.ed[...] 2004-07
_[63] 논문 Clustering large graphs via the singular value decomposition http://www.cc.gatech[...] 2012-08-02
_[64] arXiv Dimensionality reduction for ''k''-means clustering and low rank approximation (Appendix B)
_[65] 논문 Generalized methods and solvers for noise removal from piecewise constant signals. I. Background theory https://doi.org/10.1[...]
_[66] 논문 K-means Recovers ICA Filters when Independent Components are Sparse http://www.cs.huji.a[...]
_[67] 논문 Sur la division des corps matériels en parties
_[68] 논문 Cluster analysis of multivariate data: efficiency versus interpretability of classifications
_[69] 간행물 Some Methods for classification and Analysis of Multivariate Observations http://projecteuclid[...] University of California Press 2009-04-07
_[70] 서적 統計的学習の基礎 ―データマイニング・推論・予測― 共立出版 2014-06-25
_[71] 웹사이트 クラスタリング (クラスター分析) http://www.kamishima[...] 2013-08-07
_[72] 웹사이트 クラスタ生成の統計アルゴリズム　～　階層的手法、k-means法 http://www.antecanis[...] 2013-08-07
_[73] 저널 Sur la division des corps matériels en parties
_[74] 콘퍼런스 Some Methods for classification and Analysis of Multivariate Observations http://projecteuclid[...] University of California Press 2009-04-07
_[75] 저널 Least square quantization in PCM
_[75] 저널 Least squares quantization in PCM http://www.cs.toront[...] 2009-04-15
_[76] 저널 Cluster analysis of multivariate data: efficiency versus interpretability of classifications
_[77] 서적 Clustering algorithms John Wiley & Sons, Inc.
_[78] 저널 Algorithm AS 136: A K-Means Clustering Algorithm
_[79] 서적 Data Mining: Concepts and Tech-niques Morgan Kaufmann
_[80] 저널 An empirical comparison of four initialization methods for the K-Means algorithm http://ac.els-cdn.co[...]
_[81] 서적 Cluster Analysis for Applications https://archive.org/[...] Academic Press
_[82] 콘퍼런스 Alternatives to the k-means algorithm that find better clusterings http://charlotte.ucs[...] 2015-04-18
_[83] 저널 Numerical Studies of MacQueen’s k-Means Algorithm for Computing the Centroidal Voronoi Tessellations http://www.personal.[...] 2015-04-18
_[84] 서적 Finding Groups in Data. An Introduction to Cluster Analysis https://archive.org/[...] Wiley, Canada
_[85] 저널 NP-hardness of Euclidean sum-of-squares clustering
_[86] 저널 Random Projection Trees for Vector Quantization 2009-07
_[87] 저널 The Planar k-Means Problem is NP-Hard
_[88] 콘퍼런스 k-means has polynomial smoothed complexity
_[89] 저널 k-means requires exponentially many iterations even in the plane http://cseweb.ucsd.e[...]
_[90] 서적 Multivariate Analysis https://archive.org/[...] Academic Press
_[91] 저널 Feature-Space Clustering for fMRI Meta-Analysis http://www3.intersci[...] 2015-04-30
_[92] 서적 Introduction to Information Retrieval https://archive.org/[...] Cambridge University Press
_[93] 저널 Well separated clusters and optimal fuzzy partitions
_[94] 저널 Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis
_[95] 저널 Objective criteria for the evaluation of clustering methods American Statistical Association
_[96] 간행물 Slic superpixels 2010
_[97] 서적 Pattern recognition and machine learning New York: springer 2006
_[98] 웹사이트 http://stanford.edu/[...]
_[99] 콘퍼런스 k-means++: the advantages of careful seeding http://ilpubs.stanfo[...] Society for Industrial and Applied Mathematics Philadelphia, PA, USA 2015-04-27
_[100] 콘퍼런스 Clustering by means of Medoids North-Holland
_[101] 콘퍼런스 A simple and fast algorithm for K-medoids clustering
_[102] 서적 Algorithms for Clustering Data https://archive.org/[...] Prentice-Hall
_[103] 콘퍼런스 Clustering via Concave Minimization MIT Press
_[104] 서적 Pattern Recognition with Fuzzy Objective Function Algorithms https://archive.org/[...]