편집 ] k - 중앙값 클러스터링 [ 30 ] [ 31 ] 은 각 클러스터의 무게중심을 구하기 위해 평균을 사용하는 대신 중앙값을 사용한다. L 2 { displaystyle L - { 2 } } 거리를 최소화하는 k - 평균과는 달리, k - 중앙값 클러스터링은 L 1 { displaystyle L - { 1 } } 거리를 최소화 한다. 퍼지 C - 평균 클러스터링 [ 편집 ] 퍼지 C - 평균 클러스터링 의 경우 k - 평균 알고리즘과는 다르게 각 점이 완전히 하나의 클러스터에 속하는 것이 아니라, 해당 클러스터에 속한 정도를 나타내는 수치를 갖는다. 그러므로 각 클러스터의 무게중심은 해당 클러스터에 속한 정도를 비중두어 모든 점들의 평균을 계산한 값이 된다. [ 32 ] 각 데이터에 대해 편중 계수를 임의의 값으로 초기화 한다. 계산된 편중 계수의 변화가 주어진 { displaystyle varepsilon } 보다 작을 때 까지 다음 단계를 반복한다. 계산된 편중 값을 적용하여 각 클러스터의 무게중심을 계산한다. 데이터가 각 클러스터에 속한 정도를 계산하여 새로운 편중 계수로 설정한다. 퍼지 C - 평균 클러스터링은 k - 평균 알고리즘의 완화 버전 ( soft version ) 이라고 할 수 있다. 참고 문헌 [ 편집 ] D. Art
데이터 순서에 대해 독립적이다. 무작위 분할의 경우 초기 클러스터가 각 데이터들에 대해 고르게 분포되기 때문에 각 초기 클러스터의 무게중심들이 데이터 집합의 중심에 가깝게 위치하는 경향을 띈다. 이러한 특성 때문에 k - 조화 평균이나 퍼지 k - 평균에서는 무작위 분할이 선호된다. [ 9 ] Forgy [ 편집 ] Forgy 알고리즘은 1965년 Forgy에 의해 고안되었으며 [ 10 ] 현재 주로 쓰이는 초기화 기법 중 하나로, 데이터 집합으로부터 임의의 k { displaystyle k } 개의 데이터를 선택하여 각 클러스터의 초기 i { displaystyle mu - { i } } 로 설정한다. 무작위 분할 기법과 마찬가지로 Forgy 알고리즘은 데이터 순서에 대해 독립적이다. [ 8 ] Forgy 알고리즘의 경우 초기 클러스터가 임의의 k { displaystyle k } 개의 점들에 의해 설정되기 때문에 각 클러스터의 무게중심이 중심으로부터 퍼져있는 경향을 띈다. 이러한 특성 때문에 EM 알고리즘이나 표준 k - 평균 알고리즘에서는 Forgy 알고리즘이 선호된다. [ 9 ] MacQueen [ 편집 ] 1967년 MacQueen에 의해 고안된 MacQueen 알고리즘은 [ 2 ] Forgy 알고리즘과 마찬가지로 데이터 집합으로 부터 임의의 k { displaystyle k } 개의 데이터
##hanta, R., Shaji, A., Smith, K., Lucchi, A., Fua, P., &, 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. ↑ ↑ Arthur, D. and Vassilvitskii, S. ( 2007 ). 〈 k - means : the advantages of careful seeding 〉 ( PDF ). 《 Proceedings of the eighteenth annual ACM - SIAM symposium on Discrete algorithms 》. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. 1027 - 1035쪽. CS1 관리 - 여러 이름 ( 링크 ) ↑ Kaufman, L. and Rousseeuw, P. J. ( 1987 ). " Clustering by means of Medoids ". North - Holland : 405 - 416. CS1 관리
##alysis 각주 [ 편집 ] ↑ Steinhaus, H. ( 1957 ). " Sur la division des corps matériels en parties ". 《 Bull. Acad. Polon. Sci. 》 ( 프랑스어 ) 4 ( 12 ) : 801 - 804. MR 0090073. Zbl 0079. 16403. ↑ 가 나 MacQueen, J. B. ( 1967 ). 《 Some Methods for classification and Analysis of Multivariate Observations 》. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press. 281 - 297쪽. MR 0214227. Zbl 0214. 46201. 2009년 4월 7일에 확인함. ↑ Lloyd, S. P. ( 1957 ). " Least square quantization in PCM ". 《 Bell Telephone Laboratories Paper 》. Published in journal much later : Lloyd., S. P. ( 1982 ). " Least squares quantization in PCM " ( PDF ). 《 IEEE Transactions on Information Theory 》
##ow 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 ) 를 목적으로 처음으로 고안 하였으나 1982년이 되어서야 컴퓨터 과학 매거진에 처음 공개되
##의 수에 각각 비례한다. 또한 알고리즘이 해가 수렴하기까지 반복되므로, 알고리즘이 반복된 횟수에도 비례한다. 즉, n개의 d - 차원 데이터 벡터들을 i번의 반복을 통해 k개의 클러스터로 묶는데 걸리는 시간은 O ( n k d i ) { displaystyle O ( nkdi ) } 이다. 보통 데이터 오브젝트의 개수보다 클러스터의 개수가 훨씬 적으므로 k ≪ n { displaystyle k ll n } 이고, 알고리즘 반복 횟수 역시 데이터 오브젝트 개수보다 훨씬 적으므로 i ≪ n { displaystyle i ll n } 이다. 따라서, k - 평균 알고리즘은 많은 환경에서 빠르게 수렴하고, 대규모 데이터를 처리하는데 적합하므로 널리 사용된다. Smoothed analysis 경우의 복잡도는 다항 시간이다. [ 0, 1 ] d { displaystyle [ 0, 1 ] ^ { d } } 내의 임의의 n개의 점들의 집합에 대해, 집합 내의 각 점들이 평균 0, 분산 2 { displaystyle sigma ^ { 2 } } 의 정규분포를 이룬다면, 해당 집합을 k개의 클러스터로 묶는데 걸리는 시간이 O ( n 34 k 34 d 8 log 4 ( n )
##ata Mining : Concepts and Tech - niques 》. Morgan Kaufmann. 451쪽. ↑ 가 나 다 J. M., J. A. Lozano, P. ( 1999 ). " An empirical comparison of four initialization methods for the K - Means algorithm " ( PDF ). CS1 관리 - 여러 이름 ( 링크 ) ↑ 가 나 Hamerly, G. and Elkan, C. ( 2002 ). 〈 Alternatives to the k - means algorithm that find better clusterings 〉 ( PDF ). 《 Proceedings of the eleventh international conference on Information and knowledge management ( CIKM ) 》. CS1 관리 - 여러 이름 ( 링크 ) ↑ M. R. Anderberg ( 1973 ). 《 Cluster Analysis for Applications 》. Academic Press. ↑ Qiang Du, Tak - win Wong ( 2002 ). " Numerical Studies of MacQueen's k - Means Algorithm for Computing the Centroidal Voronoi Tessellations " ( PDF ). ↑ L. Kaufman
##6 - 616. doi : 10. 1007 / s00454 - 011 - 9340 - 1. ↑ Kanti Mardia ; 외. ( 1979 ). 《 Multivariate Analysis 》. Academic Press. CS1 관리 - et al. 의 직접적인 사용 ( 링크 ) ↑ Cyril Goutte, Lars Kai Hansen, Matthew G. Liptrot & Egill Rostrup ( 2001 ). " Feature - Space Clustering for fMRI Meta - Analysis ". 《 Human Brain Mapping 》 13 ( 3 ) : 165 - 183. PMID 11376501. doi : 10. 1002 / hbm. 1031. 2012년 12월 17일에 원본 문서에서 보존된 문서. 2015년 4월 30일에 확인함. CS1 관리 - 여러 이름 ( 링크 ) see especially Figure 14 and appendix. ↑ 가 나 Manning, Christopher D. ; Raghavan, Prabhakar ;, Hinrich. 《 Introduction to Information Retrieval 》. Cambridge University Press. ISBN 978 - 0 - 521 - 86571 - 5. ↑ Dunn, J. ( 1974 )
##ast squares quantization in PCM " ( PDF ). 《 IEEE Transactions on Information Theory 》 28 ( 2 ) : 129 - 137. doi : 10. 1109 / TIT. 1982. 1056489. 2009년 4월 15일에 확인함. ↑ E. W. Forgy ( 1965 ). " Cluster analysis of multivariate data : efficiency versus interpretability of classifications ". 《 Biometrics 》 21 : 768 - 769. ↑ J. A. Hartigan ( 1975 ). 《 Clustering algorithms 》. John Wiley & Sons, Inc. ↑ Hartigan, J. A. ; Wong, M. A. ( 1979 ). " Algorithm AS 136 : A K - Means Clustering Algorithm ". 《 Journal of the Royal Statistical Society, Series C 》 28 ( 1 ) : 100 - 108. JSTOR 2346830. ↑ 가 나 Han Jiawei, Jian Pei and Micheline Kamber ( 2012 ). 《 Data Mining : Concepts and Tech - niques 》. Morgan Kaufmann. 451쪽. ↑
##playstyle S - { i } ^ { ( t ) } = { x - { p } : | x - { p } - mu - { i } ^ { ( t ) } | ^ { 2 } leq | x - { p } - mu - { j } ^ { ( t ) } | ^ { 2 } forall j, 1 leq j leq k } } 클러스터 중심 재조정 : i { displaystyle mu - { i } } 를 각 클러스터에 있는 데이터들의 무게중심 값으로 재설정해준다. i ( t 1 ) = 1 | S i ( t ) | x j S i ( t ) x j { displaystyle mu - { i } ^ { ( t1 ) } = { frac { 1 } { | S - { i } ^ { ( t ) } | } } sum limits - { x - { j } in S - { i } ^ { ( t ) } } x - { j } } 만약 클러스터가 변하지 않는다면 반복을 중지한다. 맨 처음, 각 점들을 k { displaystyle k } 개 집합으로 나눈다. 이때 임의로 나누거나, 어떤 휴리스틱 기법을 사용할 수도 있다. 그 다음 각 집합
k-평균 알고리즘(K-means clustering algorithm)은 주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다. 이 알고리즘은 자율 학습의 일종으로, 레이블이 달려 있지 않은 입력 데이터에 레이블을 달아주는 역할을 수행한다. 이 알고리즘은 EM 알고리즘을 이용한 클러스터링과 비슷한 구조를 가지고 있다.