C theory v. d. e. h k - 평균 알고리즘 ( K - means algorithm ) 은 주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다. 이 알고리즘은 자율 학습의 일종으로, 레이블이 달려 있지 않은 입력 데이터에 레이블을 달아주는 역할을 수행한다. 이 알고리즘은 EM 알고리즘을 이용한 클러스터링과 비슷한 구조를 가지고 있다. 목차 1 도입 1. 1 역사 1. 2 개요 1. 3 목표 2 알고리즘 2. 1 표준 알고리즘 2. 2 초기화 기법 2. 2. 1 무작위 분할 ( Random Partition ) 2. 2. 2 Forgy 2. 2. 3 MacQueen 2. 2. 4 Kaufman 3 복잡도 4 한계점 5 클러스터의 수 5. 1 Rule of thumb 5. 2 Elbow
평균 클러스터링 [ 편집 ] 퍼지 C - 평균 클러스터링 의 경우 k - 평균 알고리즘과는 다르게 각 점이 완전히 하나의 클러스터에 속하는 것이 아니라, 해당 클러스터에 속한 정도를 나타내는 수치를 갖는다. 그러므로 각 클러스터의 무게중심은 해당 클러스터에 속한 정도를 비중두어 모든 점들의 평균을 계산한 값이 된다. [ 32 ] 각 데이터에 대해 편중 계수를 임의의 값으로 초기화 한다. 계산된 편중 계수의 변화가 주어진 [UNK] { [UNK] displaystyle [UNK] varepsilon } 보다 작을 때 까지 다음 단계를 반복한다. 계산된 편중 값을 적용하여 각 클러스터의 무게중심을 계산한다. 데이터가 각 클러스터에 속한 정도를 계산하여 새로운 편중 계수로 설정한다. 퍼지 C - 평균 클러스터링은 k - 평균 알고리즘의 완화 버전 ( soft version ) 이라고 할 수 있다. 참고 문헌 [ 편집 ]
화 알고리즘 DBSCAN OPTICS Mean - shift 차원 축소 요인 분석 CCA 독립 성분 분석 LDA 음수 미포함 행렬 분해 주성분 분석 t - SNE 그래프 모형 베이즈 네트워크 조건부 무작위장 은닉 마르코프 모델 혼합 모델 잠재 디리클레 할당 이상 발견 k - 최근접 이웃 알고리즘 Local outlier factor 인공 신경망 Autoencoder 딥 러닝 다층 퍼셉트론 순환 신경망 LSTM GRU Restricted Boltzmann machine 자기조직화지도 합성곱 신경망 강화 학습 Q 러닝 SARSA 시간차 학습 이론 편향 - 분산 트레이드오프 Computational learning theory Empirical risk minimization PAC learning Statistical learning VC theory v. d. e. h k - 평균 알고리즘 ( K - means algorithm ) 은 주어진 데이터를 k
평균 클러스터링은 k - 평균 알고리즘의 완화 버전 ( soft version ) 이라고 할 수 있다. 참고 문헌 [ 편집 ] D. Arthur, S. Vassilvitskii ( 2006 ) : " How Slow is the k - means Method, " Proceedings of the 2006 Symposium on Computational Geometry ( SoCG ). H. - H. Bock ( 2007 ) : " Clutering Methods : A History of k - Means Algorithms ", Proceedings of Selected Contributions in Data Analysis and Classification, 2 : 161 - 172 Han Jiawei, Jian Pei and Micheline Kamber ( 2012 ). 《 Data Mining : Concepts and Tech - niques 》. Morgan Kauf
10. 1 k - 평균 10. 2 k - 중간점 10. 3 k - 중앙값 클러스터링 10. 4 퍼지 C - 평균 클러스터링 11 참고 문헌 12 각주 13 외부 링크 도입 [ 편집 ] 역사 [ 편집 ] " k - 평균 " 에 대한 개념은 1957년 후고 스테인하우스에 의해 소개되었으나, [ 1 ] 용어 자체는 1967년에 제임스 매퀸 ( 영어 : James MacQueen ) 에 의해 처음 사용되었다. [ 2 ] 현재 사용되고 있는 표준 알고리즘은 1957년에 스튜어트 로이드 ( 영어 : Stuart Lloyd ) 가 펄스 부호 변조 ( PCM ) 를 목적으로 처음으로 고안 하였으나 1982년이 되어서야 컴퓨터 과학 매거진에 처음 공개되었다. [ 3 ] 알고리즘이 공개되기 이전인 1965년에 E. W. Forgy 또한 같은 알고리즘을 제안하였다. [ 4 ] 차후 1975년과 1979년
알고리즘은 입력 데이터를 k개의 파티션 ( 클러스터 ) 으로 나누는 데 사용될 수 있다. 그러나 순수 k - 평균 알고리즘은 사용에 있어 적용성이 떨어진다. 위의 한계점에서 다루었듯이 k 값을 정하기 어렵고, 비 수치 데이터를 입력으로 받았을 때나 임의의 거리 측도를 이용해야 할 때는 사용될 수 없다. 이러한 경우에는 일반적으로 k - 평균 알고리즘 이외의 다른 알고리즘을 사용한다. 다른 통계 기반 기계 학습 알고리즘간의 관계 [ 편집 ] EM 알고리즘 [ 편집 ] 가우시안 혼합 모델을 이용한 EM 알고리즘 ( 기댓값 최대화 알고리즘 ) 과 k - 평균 알고리즘을 비교했을 때 이 둘은 밀접한 연관성을 가지고 있다. [ 25 ] k - 평균 알고리즘은 각 데이터 오브젝트를 클러스터에 강하게 결속시킨다. 다시 말해, 데이터 오브젝트는 오로지 하나의 클러스터에만 속하게 되
집합 내의 각 점들이 평균 0, 분산 [UNK] 2 { [UNK] displaystyle [UNK] sigma ^ { 2 } } 의 정규분포를 이룬다면, 해당 집합을 k개의 클러스터로 묶는데 걸리는 시간이 O ( n 34 k 34 d 8 log 4 ( n ) ( n ) / [UNK] 2 ) { [UNK] displaystyle O ( n ^ { 34 } k ^ { 34 } d ^ { 8 } [UNK] log ^ { 4 } ( n ) ( n ) / [UNK] sigma ^ { 2 } ) } 임이 증명된 바 있다. [ 16 ] 다항을 넘는 ( superpolynomial ) 시간 ( 2 [UNK] ( n ) ( n ) { [UNK] displaystyle 2 ^ { [UNK] Omega ( { [UNK] sqrt { n } } ) } } ) 이 걸리는 경우도 존재한다. [ 17 ] 공간 복잡도의
k } 개의 점들에 의해 설정되기 때문에 각 클러스터의 무게중심이 중심으로부터 퍼져있는 경향을 띈다. 이러한 특성 때문에 EM 알고리즘이나 표준 k - 평균 알고리즘에서는 Forgy 알고리즘이 선호된다. [ 9 ] MacQueen [ 편집 ] 1967년 MacQueen에 의해 고안된 MacQueen 알고리즘은 [ 2 ] Forgy 알고리즘과 마찬가지로 데이터 집합으로 부터 임의의 k { [UNK] displaystyle k } 개의 데이터를 선택하여 각 클러스터의 초기 [UNK] i { [UNK] displaystyle [UNK] mu - { i } } 로 설정한다. 이후 선택되지 않은 각 데이터들에 대해, 해당 점으로부터 가장 가까운 클러스터를 찾아 데이터를 배당한다. 모든 데이터들이 클러스터에 배당되고 나면 각 클러스터의 무게중심을 다시 계산하여 초기 [UNK] i { [UNK] displaystyle [UNK] mu - { i } } 로 다시
여러 이름 ( 링크 ) ↑ Mahajan, M. ; Nimbhorkar, P. ; Varadarajan, K. ( 2009 ). " The Planar k - Means Problem is NP - Hard ". 《 Lecture Notes in Computer Science 》 5431 : 274 - 285. doi : 10. 1007 / 978 - 3 - 642 - 00202 - 1 - 24. CS1 관리 - 여러 이름 ( 링크 ) ↑ Arthur, D. ; Manthey, B. ; Roeglin, H. ( 2009 ). 〈 k - means has polynomial smoothed complexity 〉. 《 Proceedings of the 50th Symposium on Foundations of Computer Science ( FOCS ) 》. CS1 관리 - 여러 이름 ( 링크 ) ↑ Vattan
vert { [UNK] boldsymbol { [UNK] mu } } - { k }, { [UNK] boldsymbol { [UNK] sigma } } - { k } ) = { [UNK] frac { 1 } { ( 2 [UNK] pi [UNK] epsilon ) ^ { M / 2 } } } [UNK] exp [UNK] left [UNK] { - { [UNK] frac { 1 } { 2 [UNK] epsilon } } [UNK] left [UNK] | [UNK] mathbf { x } - { [UNK] boldsymbol { [UNK] mu } } - { k } [UNK] right [UNK] | ^ { 2 } [UNK] right [UNK] } } 이 식에서 EM 알고리즘을 k 개의 가우시안 혼합 모델에 적용할 때, [UNK] 추정해야 할 값으로 보지 않고 고정된 값으로 만들자. 한편, 데이터 오브젝트 x n { [UNK] displaystyle [UNK] mathbf { x } -
k-평균 알고리즘(K-means clustering algorithm)은 주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다. 이 알고리즘은 자율 학습의 일종으로, 레이블이 달려 있지 않은 입력 데이터에 레이블을 달아주는 역할을 수행한다. 이 알고리즘은 EM 알고리즘을 이용한 클러스터링과 비슷한 구조를 가지고 있다.