퍼셉트론 순환 신경망 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개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다. 이 알고리즘은 자율 학습의 일종으로, 레이블이 달려 있지 않은 입력 데이터에 레이블을 달아주는 역할을 수행한다. 이 알고리즘은 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 Method 5. 3 정보 기준 접근법 ( Information Criterion Approach )
작더라도, 일반적인 유클리드 공간 d에서 k - 평균 알고리즘의 최적 해를 찾는 것은 NP - 난해이다. [ 13 ] [ 14 ] 반대로 낮은 차원의 유클리드 공간일지라도, k개의 클러스터에 대해 최적 해를 찾는 것 또한 NP - 난해이다. [ 15 ] 이러한 이유로 k - 평균 알고리즘에서는 위와 같은 휴리스틱 기법을 주로 사용한다. Lloyd 알고리즘의 경우, 시간 복잡도는 클러스터의 수, 데이터 벡터의 차원, 데이터 벡터의 수에 각각 비례한다. 또한 알고리즘이 해가 수렴하기까지 반복되므로, 알고리즘이 반복된 횟수에도 비례한다. 즉, n개의 d - 차원 데이터 벡터들을 i번의 반복을 통해 k개의 클러스터로 묶는데 걸리는 시간은 O ( n k d i ) { [UNK] displaystyle O ( nkdi ) } 이다. 보통 데이터 오브젝트의 개수보다 클러스터의 개수가 훨씬 적으므로 k ≪ n { [UNK] displaystyle k [UNK] ll n } 이고, 알고리즘 반복 횟수 역시 데이터 오브젝트 개수보다 훨씬 적으므로 i ≪ n { [UNK] displaystyle i [UNK] ll n } 이다. 따라서, k - 평균 알고리즘은 많은 환경에서 빠르게 수렴하고, 대규모 데이터를 처리하는데 적합하므로 널리 사용된다. Sm
에는 일반적으로 k - 평균 알고리즘 이외의 다른 알고리즘을 사용한다. 다른 통계 기반 기계 학습 알고리즘간의 관계 [ 편집 ] EM 알고리즘 [ 편집 ] 가우시안 혼합 모델을 이용한 EM 알고리즘 ( 기댓값 최대화 알고리즘 ) 과 k - 평균 알고리즘을 비교했을 때 이 둘은 밀접한 연관성을 가지고 있다. [ 25 ] k - 평균 알고리즘은 각 데이터 오브젝트를 클러스터에 강하게 결속시킨다. 다시 말해, 데이터 오브젝트는 오로지 하나의 클러스터에만 속하게 되는데, 이를 hard assignment라고 한다. 반면에, EM 알고리즘은 데이터 오브젝트를 클러스터링할 때 클러스터에의 소속 여부를 해당 클러스터에서 데이터 오브젝트가 나타날 확률값으로 표현한다. 즉, 데이터 오브젝트들이 k - 평균 알고리즘과 다르게 어느 한 클러스터에만 결속되지 않게 된다. 이러한 클러스터링 방식을 soft assignment라고 한다. k평균 알고리즘과 EM 알고리즘을 맨 왼쪽의 데이터셋 " mouse " 에 적용한 결과. k - 평균 알고리즘은 같은 크기의 클러스터를 만드는 것을 선호하므로, 가운데와 같이 좋지 못한 결과를 낸다. 그러나 가우시안 혼합 모델을 사용한 EM 알고리즘은 분산값도 조정을 하기 때문에, k - 평균 알고리즘보다 좋은 결과를 보여준다. 공분산 행렬을 단위 행렬 ( identity mat
평균 알고리즘을 실시하기 전에 이상값을 제거하는 프로세스를 먼저 실행하거나, 분할법의 일종인 k - [UNK] 알고리즘 ( k - medoids algorithm ) 을 이용하면 이상값의 영향을 줄일 수 있다. 구형 ( spherical ) 이 아닌 클러스터를 찾는 데에는 적절하지 않다. k - 평균 알고리즘은 비용 함수를 계산할 때 중심점과 각 데이터 오브젝트간의 거리를 계산하게 된다. 이 때 사용하는 거리는 유클리드 거리이다. 따라서, 알고리즘 수행 시 중심점으로부터 구형으로 군집화가 이루어지게 된다. 만약 주어진 데이터 집합의 분포가 구형이 아닐 경우에는 클러스터링 결과가 예상과 다를 수 있다. 아래의 경우를 살펴보자. 비구형 클러스터 위의 경우에는 총 4개의 클러스터가 존재하는데, 구형인 클러스터는 2개만 존재한다. 위와 같은 경우 클러스터링을 시행하면 중심점으로부터 가까이 있는 데이터 오브젝트들을 한 그룹으로 묶게 되는데, 그러면 얼굴 형상의 데이터 분포를 고르게 4 조각으로 자르는 형상이 나오게 된다. 이는 알고리즘 사용자가 원하는 결과와는 크게 다르다. 위와 같은 경우에는 비슷한 밀도를 가진 데이터 군집을 하나의 클러스터링으로 묶는 방법인 DBSCAN ( Density - Based Sp
5 클러스터의 수 5. 1 Rule of thumb 5. 2 Elbow Method 5. 3 정보 기준 접근법 ( Information Criterion Approach ) 6 클러스터링 평가 척도 6. 1 내부 평가 6. 1. 1 Davies - Bouldin index 6. 1. 2 Dunn index 6. 1. 3 실루엣 기법 6. 2 외부 평가 6. 2. 1 랜드 측정 6. 2. 2 F 측정 6. 2. 3 자카드 지수 7 응용 7. 1 이미지 분할 7. 2 벡터 양자화 7. 3 클러스터 분석 8 다른 통계 기반 기계 학습 알고리즘간의 관계 8. 1 EM 알고리즘 8. 2 평균점 이동 클러스터링 9 의사 코드 [ 26 ] 10 변형 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 ) 를 목적으로 처음으로
초기화 기법 [ 편집 ] 무작위 분할 ( Random Partition ) [ 편집 ] 무작위 분할 알고리즘은 가장 많이 쓰이는 초기화 기법으로 [ 8 ], 각 데이터들을 임의의 클러스터에 배당한 후, 각 클러스터에 배당된 점들의 평균 값을 초기 [UNK] i { [UNK] displaystyle [UNK] mu - { i } } 로 설정한다. 무작위 분할 기법의 경우 다른 기법들과는 달리 데이터 순서에 대해 독립적이다. 무작위 분할의 경우 초기 클러스터가 각 데이터들에 대해 고르게 분포되기 때문에 각 초기 클러스터의 무게중심들이 데이터 집합의 중심에 가깝게 위치하는 경향을 띈다. 이러한 특성 때문에 k - 조화 평균이나 퍼지 k - 평균에서는 무작위 분할이 선호된다. [ 9 ] Forgy [ 편집 ] Forgy 알고리즘은 1965년 Forgy에 의해 고안되었으며 [ 10 ] 현재 주로 쓰이는 초기화 기법 중 하나로, 데이터 집합으로부터 임의의 k { [UNK] displaystyle k } 개의 데이터를 선택하여 각 클러스터의 초기 [UNK] i { [UNK] displaystyle [UNK] mu - { i } } 로 설정한다. 무작위 분할 기법과 마찬가지로 Forgy 알고리즘은 데이터 순서에 대해 독립적이다. [ 8 ] Forgy 알고리즘의 경우 초기 클러스터가 임의의 k { [UNK] displaystyle k } 개의 점들에 의해 설정되기 때문에 각 클러스터의 무게
은 각 데이터 오브젝트에서 미리 지정된 크기의 윈도우 이내의 데이터 오브젝트들을 찾고, 윈도우 내의 평균 값을 구한다. 그리고, 다시 그 평균값에서 같은 크기의 윈도우 이내의 데이터 오브젝트들을 찾고, 윈도우 내의 평균 값을 구한다. 이 방식을 계속하면 데이터 오브젝트들의 지역 밀도가 최대인 곳에서 윈도우의 움직임이 멈추게 된다. 이곳이 데이터 오브젝트 밀도의 지역 최댓값 ( 최빈값 ) 이다. 이런 방식으로 모든 데이터 오브젝트에 대해 지역 최댓값을 알아낸다. 이 때, 같은 최빈값으로 수렴한 데이터 오브젝트는 같은 클러스터로 간주하고, 한 클러스터로 묶어준다. 평균점 이동 클러스터링은 k - 평균 알고리즘과 다르게 k값을 필요로 하지 않는다는 장점이 있다. 하지만 모든 데이터 오브젝트로부터 무게 중심 이동 과정을 수렴할 때 까지 거쳐야 하므로 k - 평균 알고리즘보다 수행 시간이 훨씬 오래 걸린다. 참고로, 평균점 이동 클러스터링은 컴퓨터 비전 및 이미지 프로세싱 분야에서 주로 사용되며, 이미지 분할, 객체 추적 등에 이용된다. 의사 코드 [ 26 ] [ 편집 ] k - 평균 알고리즘 메인 함수 def kmeans ( dataSet, k ) : # Initialize centroids randomly numFeatures =
k - 평균 알고리즘 - 위키백과, 우리 모두의 백과사전 k - 평균 알고리즘 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 기계 학습과 데이터 마이닝 문제 분류 클러스터 분석 회귀 분석 이상 발견 연관 규칙 강화 학습 구조 기반 예측 특성 공학 특성 학습 온라인 기계 학습 준 지도 학습 비 지도 학습 Grammar induction 지도 학습 ( 통계적 분류. 회귀 분석 ) 결정 트리 학습법 앙상블 학습법 ( 배깅, Boosting, 랜덤 포레스트 ) 최근접 이웃 탐색 k - NN 선형 회귀 나이브 베이즈 인공신경망 로지스틱 회귀 퍼셉트론 상관 벡터 머신 ( RVM ) 서포트 벡터 머신 ( SVM ) 클러스터 분석 BIRCH Hierarchical clustering k - 평균 알고리즘 기댓값 최대화 알고리즘 DBSCAN OPTICS Mean - shift 차원 축소 요인 분석 CCA 독립 성분 분석 LDA 음수 미포함 행렬 분해 주성분 분석 t - SNE 그래프 모형 베이즈 네트워크 조건부 무작위장 은닉 마르코프 모델 혼합 모델 잠재 디리클레 할당 이상 발견 k - 최근접 이웃 알고리즘 Local outlier factor 인공 신경망 Autoencoder 딥 러닝 다층 퍼셉트론 순환 신경망 LSTM GRU Restricted Boltzmann machine 자기조직화지도 합성곱 신경망 강화 학습 Q 러닝 SARSA
Peter J. Rousseeuw에 의해 처음으로 서술된 실루엣 은 간단한 방법으로 데이터들이 얼마나 잘 클러스터링 되었는지를 나타낸다. [ 22 ] 하나의 데이터 i 에 대해, 해당 데이터가 속한 클러스터 내부의 데이터들과의 부동성을 a ( i ) { [UNK] displaystyle a ( i ) } 라 하고, 해당 데이터가 속하지 않은 클러스터들의 내부의 데이터들과의 부동성을 b ( i ) { [UNK] displaystyle b ( i ) } 라 할 때, 실루엣 s ( i ) { [UNK] displaystyle s ( i ) } 은 다음과 같이 계산될 수 있다. s ( i ) = b ( i ) - a ( i ) max { a ( i ), b ( i ) } { [UNK] displaystyle s ( i ) = { [UNK] frac { b ( i ) - a ( i ) } { [UNK] max [UNK] { a ( i ), b ( i ) [UNK] } } } } 이때 계산된 s ( i ) { [UNK] displaystyle s ( i ) } 는 다음의 값을 가진다. - 1 [UNK] s ( i ) [UNK] 1 { [UNK] displaystyle - 1 [UNK] leq s ( i ) [UNK] leq 1 } s ( i ) { [UNK] displaystyle s ( i ) } 가 1에 가까울 수록 데이터 데이터 i 는 올바른 클러스터에
46059. ↑ Peter J. Rousseeuw ( 1987 ). " Silhouettes : a Graphical Aid to the Interpretation and Validation of Cluster Analysis ". 《 Computational and Applied Mathematics 》 20 : 53 - 65. doi : 10. 1016 / 0377 - 0427 ( 87 ) 90125 - 7. ↑ Rand, W. M. ( 1971 ). " Objective criteria for the evaluation of clustering methods ". 《 Journal of the American Statistical Association 》 ( American Statistical Association ) 66 ( 336 ) : 846 - 850. JSTOR 2284239. doi : 10. 2307 / 2284239. ↑ Achanta, R., Shaji, A., Smith, K., Lucchi, A., Fua, P., & [UNK], S. ( 2010 ). Slic superpixels ( No. EPFL - REPORT - 149300 ) ↑ Bishop, C. M. ( 2006 ). Pattern recognition and machine learning ( Vol. 4, No. 4, p. 12 ). New York : springer. ↑
k-평균 알고리즘(K-means clustering algorithm)은 주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다. 이 알고리즘은 자율 학습의 일종으로, 레이블이 달려 있지 않은 입력 데이터에 레이블을 달아주는 역할을 수행한다. 이 알고리즘은 EM 알고리즘을 이용한 클러스터링과 비슷한 구조를 가지고 있다.