k-표준 클러스터화 클러스터링

k-평균 군집화는 원래 신호 처리에서 나온 벡터 양자화 방법으로서, n개의 관측치를 각 관측치가 가장 가까운 평균(군집 중심 또는 군집 중심)을 갖는 군집 k개로 분할하여 군집의 원형 역할을 하는 것을 목표로 합니다.이것은 데이터 공간을 Voronoi 셀로 분할하는 결과를 초래한다. k-평균 클러스터링은 클러스터 내 분산(제곱 유클리드 거리)을 최소화하지만 정규 유클리드 거리는 최소화하지 않는다. 이것은 더 어려운 베버 문제일 것이다: 평균 제곱 오류는 최적화하고 기하학적 중위수만 유클리드 거리를 최소화한다.예를 들어, 더 나은 유클리드 해는 k-중간 및 k-중간체를 사용하여 찾을 수 있다.

이 문제는 계산적으로 어렵다(NP-hard). 그러나 효율적인 휴리스틱 알고리즘은 로컬 최적화에 빠르게 수렴한다.이는 보통 k-평균과 가우스 혼합 모델링에 의해 채택된 반복 정제 접근방식을 통해 가우스 분포 혼합에 대한 기대-최대화 알고리즘과 유사하다.둘 다 군집 중심을 사용하여 데이터를 모형화하지만, k-평균 군집 분석에서는 유사한 공간 범위의 군집을 찾는 경향이 있는 반면 가우스 혼합물 모형에서는 군집 모양이 서로 다를 수 있습니다.

비지도 k-평균 알고리즘은 이름 때문에 종종 k-평균과 혼동되는 분류를 위한 인기 있는 감독 기계 학습 기술인 k-가장 가까운 이웃 분류기와 느슨한 관계를 가지고 있다.k-평균으로 얻은 클러스터 센터에 가장 가까운 1-근접 인접 분류자를 적용하면 새 데이터가 기존 클러스터로 분류됩니다.이것은 가장 가까운 중심 분류기 또는 로키오 알고리즘으로 알려져 있습니다.

묘사

각 관측치가 d차원 실벡터인 관측치 집합₁(x_2n, x, ..., x)이 주어졌을 때, k-점수 군집화는 군집 내 제곱합(WCSS_k)(즉, 분산)을 최소화하기 위해 n개의 관측치를 k개(124n₁₂) 집합으로 분할하는 것을 목표로 한다.공식적으로 목표는 다음을 찾는 것입니다.

${\displaystyle {\mathbf {S}{i=1}^{k}\sum S_{i}\left\mathbf {x} -{\boldsymbol {mu}_i}\right ^{funders}$

여기서_i μ는 S에서_i 점의 평균입니다.이는 동일한 군집 내 점의 쌍 제곱 편차를 최소화하는 것과 같습니다.

${\displaystyle {\mathbf {S} {\operatorname {display,min}} {i=1}^{k}, {\frac {1} {S_{i}}},\sum _{\mathbf {x},\in S_i}\mathbf {y} \mathbf} - sum$

등가성은 ${\displaystyle 아이덴티티{}_{}}$ ${\displaystyle \underset{}{Si\mathbf{}}}$ ${\displaystyle \sum {}_{}\underset{}{}}$ ${\displaystyle \underset{}{{Si}_{}}}$ ${\displaystyle \underset{}{{}_{}}{{\mathit{}}_{}}^{}}$ ${\displaystyle {{}_{}}^{}}$ x -${\displaystyle {{}_{}}^{}\underset{}{{}_{}}}$ i ${\displaystyle {\mathrm{}}^{}}$ 2 ${\displaystyle {}^{}}$ ${\displaystyle \sum _{}}$ ${\displaystyle \underset{}{x\mathbf{}}}$ ${\displaystyle \underset{}{y\mathbf{}}}$ ${\displaystyle \underset{}{\Vert }}$ ${\displaystyle {Si\mathbf{}}^{}}$ ${\displaystyle \underset{}{{}_{}}{x\mathbf{}}^{}}$ - ${\$ 2 { $displaystyle S_{i$} \ $sum _$ { \ $in S_{i}$ \ \ $\$ \ $mathbf x$ } \ $bold$ mu} \ symbold mong } { symb} - mbold mong$2$ 2 。$${$y}$ \$right\^{2$ 총 분산은 일정하므로 서로 다른 군집(군집 간 제곱합, BCSS)^[1]에 있는 점 사이의 편차의 제곱합을 최대화하는 것과 같습니다$.$이 결정론적 관계는 확률론의 전분산 법칙과도 관련이 있습니다.

역사

"^[2]k-평균"이라는 용어는 제임스 맥퀸이 1967년에 처음 사용했지만,^[3] 그 아이디어는 1956년에 휴고 스타인하우스로 거슬러 올라간다.표준 알고리즘은 1957년 벨 연구소의 스튜어트 로이드(Stuart Lloyd)에 의해 펄스 코드 변조 기술로 처음 제안되었지만 1982년까지 ^[4]저널 기사로 발표되지 않았다.1965년 에드워드 W.Forgy는 기본적으로 같은 방법을 출판했고, 이것이 Lloyd라고 불리는 이유이다.포기 ^[5]알고리즘

알고리즘

표준 알고리즘(naive k-means)

가장 일반적인 알고리즘은 반복 정제 기술을 사용합니다.그 보편성 때문에, 이것은 종종 "k-평균 알고리즘"이라고 불리며, 특히 컴퓨터 사이언스 커뮤니티에서는 로이드 알고리즘이라고도 불린다.훨씬 더 빠른 ^[6]대안이 존재하기 때문에 "순진한 k-평균"이라고도 한다.

k의 초기 세트가 m, ...m_k⁽¹⁾(아래 참조)을 의미할₁⁽¹⁾ 경우 알고리즘은 두 단계를 ^[7]번갈아 가면서 진행됩니다.

할당 단계:각 관측치를 가장 가까운 평균, 즉 유클리드 ^[8]거리의 제곱이 최소인 관측치를 군집에 할당합니다(수학적으로 이는 평균에 의해 생성된 Voronoi 다이어그램에 따라 관측치를 분할하는 것을 의미합니다).

$\displaystyle S_{i}^{(t)}=\left\{x_{p}-m_{i}^{(t)}\right\leq \left\x_{p}-m_{j}^{(t)^{2}\right\left\leq\l j,\leq\lek}\left\left\left\left\left\lep}$

여기서 각 $x{\displaystyle {}_{}}$ $(\$p$$})는 둘 이상의 S(\$displaystyle$ S$^{(t$에 할당될 수 있는 경우에도 정확히 $하나$의 S${\displaystyle {(}^{}}$)에 할당됩니다.

업데이트 순서:각 군집에 할당된 관측치에 대한 평균(중심)을 다시 계산합니다.

${\displaystyle m_{i}^{(t+1)}=flac {1}{\left S_{i}^{(t)}\right }}\sum_{x_{j}\in S_{i}^{(t)}}}}{x_{j}}}$

할당이 변경되지 않게 되면 알고리즘이 수렴됩니다.알고리즘이 ^[9]최적임을 보증하는 것은 아닙니다.

알고리즘은 종종 거리에 따라 가장 가까운 클러스터에 개체를 할당하는 것으로 나타납니다.(제곱) 유클리드 거리가 아닌 다른 거리 함수를 사용하면 알고리즘이 수렴되지 않을 수 있습니다.구면 k-평균 및 k-중간과 같은 k-평균의 다양한 수정이 다른 거리 측정을 사용할 수 있도록 제안되었다.

초기화 방법

일반적으로 사용되는 초기화 방법은 Forgy 및 Random ^[10]Partition입니다.Forgy 방법은 데이터 집합에서 k개의 관측치를 랜덤으로 선택하고 이러한 관측치를 초기 평균으로 사용합니다.랜덤 분할 방법은 먼저 각 관측치에 군집을 랜덤하게 할당한 다음 업데이트 단계를 진행하므로 초기 평균이 군집이 랜덤하게 할당된 점의 중심이 될 수 있습니다.Forgy 방법은 초기 평균을 분산하는 경향이 있는 반면 랜덤 파티션은 모든 평균을 데이터 집합의 중심에 가깝게 배치합니다.Hamerly ^[10]등에 따르면 랜덤 분할 방법은 일반적으로 k-조화 평균 및 퍼지 k-평균과 같은 알고리즘에 선호된다.기대 최대화 및 표준 k-평균 알고리즘의 경우 Forgy 초기화 방법이 바람직하다.그러나 Celebi ^[11]등의 포괄적인 연구에 따르면 Forgy, Random Partition, Maximin과 같은 일반적인 초기화 방법은 종종 성능이 떨어지는 반면 Bradley와 Fayyad의 접근^[12] 방식은 "최고의 그룹"에서 "일관적으로" 수행되며 k-평균+는 "일반적으로 잘 수행된다"고 합니다.

• 표준 알고리즘 시연
• 

  1. k 첫 번째 "color"(이 경우 k=3)는 데이터 영역 내에서 무작위로 생성됩니다(컬러로 표시됨).

• 

  2. k개의 군집은 모든 관측치를 가장 가까운 평균과 연결하여 생성됩니다.여기서의 파티션은 수단에 의해 생성된 Voronoi 다이어그램을 나타냅니다.

• 

  3. 각 k개 군집의 중심이 새 평균이 됩니다.

• 

  4. 컨버전스에 도달할 때까지 스텝2와 스텝3을 반복합니다.

이 알고리즘은 글로벌 최적화에 대한 컨버전스를 보증하지 않습니다.결과는 초기 클러스터에 따라 달라질 수 있습니다.알고리즘은 일반적으로 속도가 빠르기 때문에 시작 조건이 다른 상태에서 여러 번 실행하는 것이 일반적입니다.그러나 최악의 경우 성능이 느려질 수 있습니다. 특히 특정 포인트 집합은 2차원에서도 지수 시간, 즉 ^[13]2차원으로^Ω(n) 수렴됩니다.이러한 점 집합은 실제로 발생하지 않는 것으로 보인다. 이는 k-평균의 평활화된 실행 시간이 ^[14]다항식이라는 사실로 입증된다.

"할당" 단계는 "예상 단계"라고 하며, "업데이트 단계"는 최대화 단계이며, 이 알고리즘은 일반화된 기대 최대화 알고리즘의 변형입니다.

복잡성

d 차원의 관측치에 대한 k-평균 군집화 문제에 대한 최적의 해법은 다음과 같습니다.

• 일반 유클리드 공간(d차원)의 NP-hard는 두 개의 ^[15][16]군집에도 해당된다.
• NP-hard는 ^[17]평면에 있는 일반 클러스터 수 k에 대해서도 마찬가지입니다.
• k와 d(치수)가 고정되어 있는 경우 문제는 $($ d${\displaystyle {}^{}}$k${\displaystyle {}^{}}$+ ${\displaystyle 1^{}}$) {$display style O(n^{dk+$1$\}\})$로 정확하게 해결할 수 있습니다.여기서 n은 ^[18]클러스터화할 엔티티의 수입니다.

따라서 위에 제시된 로이드 알고리즘과 같은 다양한 휴리스틱 알고리즘이 일반적으로 사용된다.

Lloyd 알고리즘(및 대부분의 바리안트)의 실행 시간은 $O{\displaystyle }$(${\displaystyle n}$ ${\displaystyle k}$ $){$ $displaystyle$O ($nkdi$^[9][19] 입니다.

• n은 (클러스터화할) d차원 벡터 수입니다.
• k 군집 수
• i 컨버전스까지 필요한 반복 횟수.

클러스터링 구조를 가진 데이터에서는 컨버전스까지의 반복 횟수가 적은 경우가 많고 처음 12회 반복한 후에는 결과가 약간 개선됩니다.그러므로 로이드 알고리즘은 ^[20]수렴될 때까지 수행되었을 때 최악의 경우 초다항식이지만 실제로는 종종 "선형" 복잡성으로 간주된다.

• 최악의 경우 Lloyd 알고리즘은 i ${\displaystyle =}$ ${\displaystyle {2\Omega \mathrm{}}^{}}$ ${\displaystyle {(n\sqrt{}}^{}}$) { $displaystyle$ i$= 2^{\Omega}}}$의 반복이 $필요$하므로 Lloyd 알고리즘의 최악의 경우 복잡도는 초다항식이다.^[20]
• Lloyd의 k-평균 알고리즘은 다항식 평활 실행 시간을 가지고 있다.만약 각 지점 독립적으로 정상적인 분포에 의해 평균 0과 가변성 σ 2{\displaystyle \sigma ^{2}}과 냉정을 잃다 그것은 that[14]와 점의[0,1]d{\displaystyle[0,1]^{d}내의 임의의 집합},, 그때 k-means 알고리즘의 예상 가동 시간은 O형을 경계로 한다(n34k34d8로그 4. ⁡ ${\displaystyle (n}$ )${\displaystyle }$/ ${\displaystyle {6\mathrm{}}^{}}$6 $)({displaystyle$O($n^{34}k^{34}d^{8}\log ^{4}($n)/\sigma$^{6$ (n, k, d $및{\displaystyle \mathrm{}1}$/ ${\$ { $displaystyle$ 1$/\sigma$}).
• 단순한 경우에서 더 나은 경계가 입증되었습니다.예를 들어 정수격자${\displaystyle }${${\displaystyle 1,}$ ${\displaystyle \dots ,}$ ${\displaystyle M}$ ${\displaystyle {}^{}}$ {\$displaystyle \{1,\dots,M\}^{$$d$$\}\}$^[21]의 n개${\displaystyle }$포인트에 대해 k-평균 알고리즘의 ${\displaystyle \mathrm{실행시간}}$은 $O(dn$4 M2${\displaystyle {}^{}}$에 $의해{\displaystyle }$ 제한됨을 알 수 있습니다.

Lloyd의 알고리즘이 이 문제에 대한 표준 접근법이다.그러나 각 k개의 군집 중심과 n개의 데이터 지점 사이의 거리를 계산하는 데 많은 시간을 소비합니다.포인트는 보통 몇 번의 반복 후에도 동일한 클러스터에 유지되기 때문에 이 작업의 대부분은 불필요하며, 따라서 순진한 구현이 매우 비효율적이다.일부 구현에서는 경계를 만들고 Lloyd의 ^{[9][22][23][24][25]}알고리즘을 가속화하기 위해 캐싱과 삼각 부등식을 사용합니다.

바리에이션

• Jenks 자연 휴식 최적화: 일변량 데이터에 적용되는 k-평균
• k-중간자 클러스터링에서는 평균 대신 각 차원에서 중앙값을 사용하며, 이 방법으로 ${\displaystyle {L\mathrm{}}_{}}$ 1$({$}) 규범$$(택시카브 지오메트리)을 $최소화$합니다.
• k-중간값(중간값 주변 분할, PAM)은 평균 대신 중위수를 사용하며, 이렇게 하면 임의 거리 함수에 대한 거리의 합을 최소화할 수 있습니다.
• 퍼지 C-평균 군집화는 k-평균의 소프트 버전이며, 여기서 각 데이터 포인트는 각 클러스터에 속하는 퍼지 정도를 가집니다.
• 기대-최대화 알고리즘(EM 알고리즘)으로 훈련된 가우스 혼합물 모델은 결정론적 할당 대신 확률론적 할당과 평균 대신 다변량 가우스 분포를 유지한다.
• k-평균++는 WCSS 목표에 입증 가능한 상한을 부여하는 방식으로 초기 중심을 선택한다.
• 필터링 알고리즘은 kd-tree를 사용하여 각 k-평균 ^[26]스텝의 속도를 높입니다.
• 일부 방법은 삼각 ^{[22][23][24][27][25]}부등식을 사용하여 각 k-평균 단계의 속도를 높이려고 시도한다.
• 클러스터 ^[9]간에 점을 스왑하여 로컬 최적화를 회피합니다.
• 구면 k-평균 클러스터링 알고리즘은 텍스트 ^[28]데이터에 적합합니다.
• 이등분할 k-평균,^[29] X-평균 클러스터링^[30] 및 G-평균 클러스터링과^[31] 같은 계층적 변형은 반복하여 클러스터를 분할하여 계층을 구축하며 데이터 집합에서 최적의 클러스터 수를 자동으로 결정하려고 시도할 수도 있습니다.
• 클러스터 실루엣과 같은 내부 클러스터 평가 척도는 클러스터 수를 결정하는 데 도움이 될 수 있습니다.
• 민코프스키 가중치 k-평균은 군집별 피쳐 가중치를 자동으로 계산하여 피쳐가 서로 다른 ^[32]피쳐에서 서로 다른 관련성을 가질 수 있다는 직관적인 생각을 뒷받침한다.또한 이러한 가중치를 사용하여 주어진 데이터 세트를 재스케일링할 수 있으므로 ^[33]군집 유효성 지수가 예상되는 군집 수로 최적화될 수 있습니다.
• 미니 배치 k-평균:^[34] 메모리에 맞지 않는 데이터 세트에 대해 "미니 배치" 샘플을 사용한 k-평균 변동.
• 오츠법

하티건왕법

Hartigan과 Wong의 방법은^[9] 서로 다른 솔루션 업데이트에서 최소 제곱합 문제의 국소적 최소값으로 진행되는 k-평균 알고리즘의 변형을 제공한다.메소드는 로컬 검색으로, 이 프로세스를 통해 목적 기능이 개선되는 한 샘플을 다른 클러스터로 반복적으로 재배치하려고 시도합니다.목표를 개선하여 샘플을 다른 클러스터로 재배치할 수 없는 경우 메서드는 중지됩니다(로컬 최소값).기존의 k-평균과 유사한 방법으로, 이 접근방식은 최종 솔루션이 전지구적으로 최적임을 반드시 보장하지는 않기 때문에 휴리스틱으로 남는다.

$s$($$S j ) {$display$ \ $varphi$( S _$${ j ) ${\displaystyle \}}$ ${\displaystyle \underset{}{let}}$ s ${\displaystyle S_{}}$${\displaystyle \underset{}{{}_{}}\underset{}{j_{}}}$$$(${\displaystyle x}$ - ${\displaystyle {\mu }_{}{}^{}}$j )${\displaystyle 2^{}}$ ($display$$style$ \ $sum$ _ { $x$\ $in$ $S$_ { $j$$$} ( x - \ $mu$_ j )^$2$} ( $x$ - { $display$ style \ sum \$$mu { ${\displaystyle j_{}}$} ) ） 、 $。$

할당 단계:Hartigan과 Wong의 방법은 점을 랜덤 클러스터${\displaystyle }${ ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {\{}_{}}$ { ${\displaystyle 1_{}}$,${\displaystyle {\cdots }_{}}$ ${\displaystyle k_{}}$ $}$ { $display$ \ { $S _$ { j$$} \ { j$$\$in$ \ 1, \ $cdots$ k \$$}$$}로 분할하는 것으로 시작합니다.

업데이트 순서: 다음으로 다음 함수가 최대치에 도달하는n${\displaystyle }$, ${\displaystyle m1}$ {${\displaystyle }$1 , ${\displaystyle ...}$ , $}$ { $displaystyle$n ,$m$ \ $in$\ { 1$,$ $\ldots$,$k$\ ${\displaystyle \}}$ 및$$ x ${\displaystyle x_{}}$ S$$n { $displaystyle$x \ $in S$_ { $n$} 를$$ $결정$합니다.

$\displaystyle \Delta (m,n,x)=\varphi (S_{n})+\varphi (S_{m})-\varphi (S_{n}\smallsetminus \{x\})-\varphi (S_{m}\cup \x\})}$

x${\displaystyle ,}$ ${\displaystyle n,}$ $({displaystyle$ x, $n, m$})이 최대값에 도달하면$$x({$displaystyle$$$$x$})가$$ $클러스터{\displaystyle {}_{}}$ $({$에서 $클러스터{\displaystyle {}_{}}$ $({$으로 이동합니다.

종료:알고리즘은 $모든{\displaystyle }$ x${\displaystyle ,}$ ${\displaystyle n,}$ \ $displaystyle$$$x$, n$${\displaystyle ,}$ ${\displaystyle x}$)의$$$\delta {\displaystyle \mathrm{}}$ (${\displaystyle m}$, $n , x$ )이 0보다 작을 때 종료됩니다.

다른 이동 승인 전략을 사용할 수 있습니다.첫 번째 개선 전략에서는 개선된 이전을 적용할 수 있지만, 최선의 개선 전략에서는 가능한 모든 이전을 반복적으로 테스트하고 각 반복마다 최상의 이전만 적용합니다.전자의 접근방식은 속도를 선호하지만, 후자의 접근방식은 일반적으로 추가적인 계산 시간을 희생하는 솔루션 품질을 선호한다.이전 결과 계산에 사용되는 함수$\delta {\displaystyle \mathrm{}}$(\$displaystyle\Delta)$도 등식을 사용하여 효율적으로^[35] 평가할 수 있습니다.

$\displaystyle \Delta ( x , n , m ) = scdfrac { mid S _ { n } \ mid - 1 } \ cdot \ lVert \ mu _ { n } - x \ rVert ^2} - { \ frac { mid S _ { m} \ mid \ CD _ { { mid }}$

글로벌 최적화 및 메타 휴리스틱스

기존의 k-평균 알고리즘과 그 변동은 다음과 같이 정의된 최소 제곱합 군집화 문제의 국소 최소값에만 수렴하는 것으로 알려져 있다.

${\displaystyle {\mathbf {S}{\operatorname {s}{i=1}^{k}\sum _{\mathbf {x}\in S_{i}\left\mathbf {x} -{\boldsymbol {mb}_{i}}\right ^{2}.}$

많은 연구가 알고리즘의 수렴 동작을 개선하고 전역 최적(또는 적어도 더 나은 품질의 로컬 최소)에 도달할 가능성을 극대화하려고 시도했다.이전 섹션에서 설명한 초기화 및 재시작 기술은 보다 나은 솔루션을 찾기 위한 하나의 대안입니다.최근에는 분기 및 경계 및 반확정 프로그래밍을 기반으로 한 글로벌 최적화 알고리즘이 최대 4,177개의 엔티티와 20,531개의 ^[36]기능을 갖춘 데이터셋에 대해 "실증적으로 최적의" 솔루션을 생산했습니다.예상대로, 인접하 최적화 문제의 NP-경도 때문에, K-평균에 대한 최적 알고리즘의 연산 시간은 이 크기를 넘어 빠르게 증가한다.중소규모를 위한 최적의 솔루션은 다른 휴리스틱의 품질을 평가하는 벤치마크 도구로서 여전히 가치가 있습니다.제어된 계산 시간이었지만 최적성 보장 없이 내에서 고품질의 국소 최저치를 찾기 위해 다른 작품. 점진적인 접근법과 볼록 optimization,[37]무작위 swaps[38](즉, 로컬 검색이고 거기에 GGQ), 가변 동네 search[39]와 유전자에 따라 metaheuristics이나 여타 세계적인 최적화 기술, 예를 탐사하였습니다.알고리즘최소 제곱합 클러스터링 문제에서 더 나은 로컬 최소값을 찾는 것은 ^[41]고차원 피쳐 공간에서 클러스터 구조를 복구하는 데 실패하느냐 실패하느냐의 차이를 만드는 것으로 알려져 있습니다.^[40][41]

논의

k-평균의 효율성을 높이는 세 가지 주요 특징이 종종 가장 큰 결점으로 간주된다.

• 유클리드 거리는 측정기준으로 사용되며 분산은 클러스터 산란 측정기준으로 사용됩니다.
• 군집 수 k는 입력 모수입니다. k를 잘못 선택하면 결과가 좋지 않을 수 있습니다.따라서 k-평균을 수행할 때 데이터 집합의 군집 수를 결정하기 위해 진단 검사를 실행하는 것이 중요합니다.
• 로컬 최소값으로의 수렴은 반직관적인("잘못된") 결과를 초래할 수 있습니다(그림의 예 참조).

k-평균의 주요 제한 사항은 군집 모형입니다.이 개념은 평균이 군집 중심 쪽으로 수렴되도록 분리할 수 있는 구형 군집을 기반으로 합니다.군집의 크기가 비슷해야 가장 가까운 군집 중심으로의 할당이 올바른 할당입니다.예를 들어 잘 ${\displaystyle \mathrm{알려진}}$ Iris 꽃 데이터 세트에 k ${\displaystyle =}$3(\$displaystyle$ k$=3)$의 값을 가진 k-time을 적용하면 데이터 세트에 포함된 세 개의 Iris 종을 분리하지 못하는 경우가 많습니다.k ${\displaystyle =}$ ${\displaystyle 2}(\backslash$$displaystyle$ k$=2)$의 경우 눈에 보이는 두 개의 클러스터(1개는 두 개의 종을 포함)가 발견되는 반면, k ${\displaystyle =}$(\$displaystyle$ k$=3)$의 $경우{\displaystyle }$ 두 클러스터 중 하나는 짝수 부분으로 분할됩니다.실제로 데이터 집합에는 3개의 클래스가 포함되지만 이 데이터 집합에는 k $2$(\$style$ k$=$2)가 더 적합합니다.다른 군집 분석 알고리즘과 마찬가지로 k-평균 결과는 데이터가 특정 기준을 충족한다고 가정합니다.일부 데이터 세트에서는 잘 작동하지만 다른 데이터 세트에서는 실패합니다.

k-평균의 결과는 군집 평균의 보로노이 셀로 볼 수 있습니다.데이터는 군집 평균 사이의 중간 지점에서 분할되므로 "마우스" 예제에서 볼 수 있듯이 최적의 분할이 되지 않을 수 있습니다.기대-최대화 알고리즘(논쟁적으로 k-평균의 일반화)에 의해 사용되는 가우스 모델은 분산과 공분산을 모두 가지므로 더 유연하다.따라서 전자파 결과는 상관된 군집뿐만 아니라 k-평균보다 가변 크기의 군집을 훨씬 더 잘 수용할 수 있다(이 예에서는 그렇지 않음).반대로, EM은 더 많은 수의 자유 매개변수의 최적화를 필요로 하며 클러스터가 사라지거나 상태가 좋지 않은 공분산 행렬로 인해 몇 가지 방법론적 문제를 제기한다.K-평균은 비모수 베이지안 ^[43]모델링과 밀접한 관련이 있습니다.

적용들

k-평균 클러스터링은 특히 Lloyd의 알고리즘과 같은 휴리스틱을 사용할 때 대규모 데이터 세트에 적용하기가 비교적 쉽다.그것은 시장 세분화, 컴퓨터 비전, 천문학 등 많은 분야에서 성공적으로 사용되어 왔다.이것은 다른 알고리즘의 전처리 단계(예를 들어 시작 Configuration을 찾기 위해)로 자주 사용됩니다.

벡터 양자화

k-module은 신호 처리에서 발생하며 이 도메인에서 계속 사용됩니다.예를 들어 컴퓨터 그래픽스에서 색 양자화는 화상의 색 팔레트를 일정한 색수 k로 줄이는 작업이다.k-평균 알고리즘은 이 작업에 쉽게 사용할 수 있으며 경쟁력 있는 결과를 산출한다.이 접근방식의 활용 사례는 이미지 분할입니다.벡터 양자화의 다른 용도로는 비랜덤 샘플링이 있습니다. k-평균은 추가 분석을 위해 대규모 데이터 세트에서 k개의 다른 프로토타입 객체를 쉽게 선택할 수 있기 때문입니다.

클러스터 분석

군집 분석에서 k-평균 알고리즘을 사용하여 입력 데이터 집합을 k개의 파티션(군집)으로 분할할 수 있습니다.

그러나 순수 k-평균 알고리즘은 매우 유연하지 않기 때문에 제한적으로 사용됩니다(상기와 같은 벡터 양자화가 실제로 바람직한 사용 사례인 경우는 제외).특히, 매개변수 k는 외부 제약조건에 의해 주어지지 않을 경우 선택하기 어려운 것으로 알려져 있다(위에서 논의한 바와 같이).또 다른 제한사항은 임의 거리 함수 또는 비숫자 데이터에 사용할 수 없다는 것입니다.이러한 사용 사례에서는 다른 많은 알고리즘이 우수합니다.

기능 학습

k-수치 클러스터링은 (수치) 지도 학습 또는 비지도 ^[44]학습에서 기능 학습(또는 사전 학습) 단계로 사용되어 왔다.기본 접근법은 먼저 입력 훈련 데이터를 사용하여 k-평균 군집화 표현을 훈련하는 것이다(라벨링 필요 없음).그런 다음 입력 데이터를 새로운 특징 공간에 투영하기 위해 중심 위치를 가진 기준의 임계값 행렬 곱과 같은 "인코딩" 함수는 기준에서 각 중심까지의 거리를 계산하거나 단순히 가장 가까운 ^[44][45]중심에 대한 ^[46]지시 함수 또는 거리의 부드러운 변환을 계산합니다.또는, 가우스 RBF를 개입시켜 샘플 클러스터 거리를 변환하는 것으로, 레이디얼 베이스 함수 네트워크의 ^[47]은닉층을 얻는다.

이러한 k-평균의 사용은 (특히 명명된 실체 인식에 ^[48]대한) NLP와 컴퓨터 비전에서 반감독 학습을 위한 단순 선형 분류기와 성공적으로 결합되었다.객체 인식 작업에서 자동 인코더 및 제한된 볼츠만 ^[46]기계와 같은 보다 정교한 기능 학습 접근법으로 비교 가능한 성능을 보이는 것으로 밝혀졌다.그러나 각 데이터 지점이 하나의 "기능"^[44]에만 기여하기 때문에 일반적으로 동일한 성능을 위해 더 많은 데이터가 필요합니다.

다른 알고리즘과의 관계

가우스 혼합 모형

k-평균 클러스터링을 위한 느린 "표준 알고리즘"과 관련된 기대-최대화 알고리즘은 특히 모든 공분산을 대각선이고 동일하며 극히 작은 ^{[49]: 850} 분산을 가지도록 고정할 때 가우스 혼합 모델의 특별한 경우이다.작은 분산 대신 하드 클러스터 할당을 사용하여 "하드" 가우스 혼합물 ^{[50]: 354, 11.4.2.5} 모델링의 특수한 경우에 대한 k-평균 군집화의 또 다른 동등성을 보여줄 수도 있다.이는 k-평균을 계산하기 위해 가우스 혼합물 모델링을 사용하는 것이 효율적이라는 것이 아니라 단지 이론적인 관계가 있다는 것을 의미하며, 가우스 혼합물 모델링은 k-평균의 일반화로 해석될 수 있다. 반대로, k-평균 군집화를 사용하여 가우스 혼합물 모델리의 시작점을 찾는 것이 제안되었다.어려운 ^{[49]: 849} 데이터에 대응합니다.

K-SVD

k-평균 알고리즘의 또 다른 일반화는 데이터 포인트를 "코드북 벡터"의 희박한 선형 조합으로 추정하는 K-SVD 알고리즘이다. k-평균은 가중치가 ^[51]1인 단일 코드북 벡터를 사용하는 특수한 경우에 해당한다.

주성분 분석

군집 지시자로 지정된 -평균 군집 분석의 완화 솔루션은 주성분 분석(PCA)^[52][53]에 의해 제공됩니다.직관적으로 k-평균은 구형(공 모양) 군집을 나타냅니다.데이터에 클러스터가 2개인 경우 두 개의 중심을 연결하는 선이 최적의 1차원 투영 방향이며, 이 방향도 첫 번째 PCA 방향입니다.질량 중심에서 선을 자르면 군집이 분리됩니다(이것이 이산 군집 지시자의 연속 완화).데이터에 클러스터가 3개인 경우 클러스터 중심 세 개에 걸쳐 있는 2차원 평면이 최상의 2-D 투영입니다.이 평면은 처음 두 개의 PCA 치수로도 정의됩니다.잘 분리된 군집은 공 모양의 군집에 의해 효과적으로 모델링되고 따라서 k-평균에 의해 발견됩니다.비구형 군집은 가까이 있으면 분리하기 어렵습니다.예를 들어, 공간에 얽힌 두 개의 반달 모양 클러스터는 PCA 부분 공간에 투영될 때 잘 분리되지 않습니다. k-평균은 이 데이터에서 ^[54]잘 분리되지 않을 것입니다.클러스터 중심 부분 공간이 주방향에 ^[55]의해 확장된다는 진술에 대한 반례를 생성하는 것은 간단합니다.

평균 시프트 클러스터링

기본 평균 이동 클러스터링 알고리즘은 데이터 점 집합을 입력 데이터 집합과 동일한 크기로 유지합니다.처음에 이 세트는 입력 세트에서 복사됩니다.그런 다음 이 집합은 해당 지점에서 지정된 거리 내에 있는 집합 내 점의 평균으로 반복적으로 대체됩니다.반면, k-평균은 이 갱신 세트를 입력 데이터 세트의 포인트 수보다 훨씬 적은 k개의 포인트로 제한하고, 이 세트의 각 포인트를 다른 포인트보다 그 포인트에 가까운 입력 세트의 모든 포인트의 평균(예: 각 갱신 포인트의 Voronoi 파티션 내)으로 대체한다.우도 평균 이동이라고 하는 k-평균과 유사한 평균 이동 알고리즘은 변경 ^[56]집합의 지정된 거리에 있는 입력 집합의 모든 점의 평균으로 치환되는 점 집합을 대체합니다.k-평균에 비해 평균 이동의 장점 중 하나는 군집 수가 미리 지정되지 않았다는 것입니다. 왜냐하면 평균 이동은 적은 수의 군집만 찾을 가능성이 높기 때문입니다.그러나 평균 이동은 k-평균보다 훨씬 느릴 수 있으며 여전히 대역폭 매개 변수를 선택해야 합니다.평균 변속은 부드러운 변형을 가집니다.

독립 성분 분석

희소성 가정과 미백 변환으로 입력 데이터를 전처리할 때 k-평균은 선형 독립 성분 분석(ICA) 작업에 대한 솔루션을 생성한다.이것은 기능 학습에 ^[57]k-평균을 성공적으로 적용하는 데 도움이 된다.

양방향 필터링

k-module은 입력 데이터 세트의 순서가 중요하지 않다고 암묵적으로 가정합니다.양방향 필터는 k-평균 및 평균 이동과 유사하며, 수단에 의해 반복적으로 대체되는 데이터 점 집합을 유지합니다.그러나 양방향 필터는 입력 데이터 순서에 가까운 점만 포함하도록 (커널 가중치)^[56] 평균의 계산을 제한합니다.이를 통해 이미지 내의 픽셀의 공간 배치가 중요한 이미지 노이즈 제거와 같은 문제에 적용할 수 있습니다.

유사한 문제

군집 함수를 최소화하는 오차 제곱 집합에는 각 군집의 중앙점이 실제 점 중 하나가 되도록 강제하는 접근 방식인 k-중간 알고리즘도 포함됩니다. 즉, 중심점 대신 중간점을 사용합니다.

소프트웨어 구현

알고리즘의 실장에 따라 성능 차이가 나타나며 테스트 데이터 세트의 가장 빠른 것은 10초, 가장 느린 것은 25,988초(~7시간)^[1]가 소요됩니다.이러한 차이는 구현 품질, 언어와 컴파일러의 차이, 서로 다른 종료 기준과 정밀도 수준, 가속을 위한 인덱스 사용에 기인할 수 있습니다.

무료 소프트웨어/오픈 소스

다음 구현은 Free/Open Source Software 라이센스로 사용할 수 있으며, 공개적으로 사용할 수 있는 소스 코드도 있습니다.

• Acord.NET에는 k-평균, k-평균++ 및 k-모드에 대한 C# 구현이 포함되어 있습니다.
• ALGLIB에는 k-평균 및 k-평균++에 대한 병렬화된 C++ 및 C# 구현이 포함되어 있습니다.
• AOSP에는 k-평균에 대한 Java 구현이 포함되어 있습니다.
• CrimeStat는 두 개의 공간 k-평균 알고리즘을 구현하며, 그 중 하나는 사용자가 시작 위치를 정의할 수 있도록 합니다.
• ELKI에는 k-평균(Lloyd 및 MacQueen 반복, k-평균+초기화 등 다양한 초기화)과 다양한 고급 클러스터링 알고리즘이 포함되어 있습니다.
• Smile에는 k-평균 및 기타 다양한 알고리즘과 결과 시각화(java, kotlin 및 scala용)가 포함되어 있습니다.
• Julia는 JuliaStats 클러스터링 패키지에 k-평균 구현을 포함합니다.
• KNIME에는 k-평균 및 k-medoid에 대한 노드가 포함되어 있습니다.
• Mahout에는 MapReduce 기반의 k-평균이 포함되어 있습니다.
• mlpack에는 K-평균의 C++ 구현이 포함되어 있습니다.
• 옥타브는 k-평균을 포함합니다.
• OpenCV에는 k-평균 구현이 포함되어 있습니다.
• 주황색에는 k 및 클러스터 실루엣 스코어링 자동 선택 기능을 갖춘 k-평균 클러스터링을 위한 구성 요소가 포함되어 있습니다.
• PSPP에는 k-평균이 포함되어 있습니다.QUICK CLUSTER 명령은 데이터셋에서 k-평균 클러스터링을 수행합니다.
• R에는 세 가지 k-평균 변형이 포함되어 있습니다.
• SciPy 및 skikit-learn에는 여러 k-평균 구현이 포함되어 있습니다.
• Spark MLlib은 분산형 k-평균 알고리즘을 구현합니다.
• 토치에는 k-평균 클러스터링을 제공하는 언업 패키지가 포함되어 있습니다.
• Weka에는 k-평균과 x-평균이 포함되어 있습니다.

독자 사양

이하의 실장은, 독자적인 라이센스 조건에 근거해 이용할 수 있습니다.또, 공개되고 있는 소스 코드가 없는 경우가 있습니다.

「 」를 참조해 주세요.

• BFR 알고리즘
• 중심 보로노이 테셀레이션
• 헤드/테일 브레이크
• k q-syslog
• K-평균++
• 린드-부조-그레이 알고리즘
• 자기 조직 지도

레퍼런스