k-means++법

이 기사는 검증 가능한 참고 문헌이나 출전이 전혀 나타나지 않은지, 불충분합니다. 출전을 추가해 기사의 신뢰성 향상에 협력해 주십시오.(2013년 6월)

k-means++법은, 비계층형 클러스터링 수법의 하나로, k-means법의 초기치의 선택으로 개량을 행한 방법이다. 표준적인 k-means법이 빈번히 클러스터로 해서는 안되는 것에도 클러스터 할당을 실시해 버리는 문제나, k-means법이 NP 곤란한 문제인 것을 해소하기 위해서, 2007년에 David Arthur와 Sergei Vassilvitskii에 의해서 제안된[¹]. 2006년에 Rafail Ostrovsky등에 의해서 제안된 three seeding method[²]와 닮아 있지만 초기 배정의 분포가 다르다.

목차

배경

k-means법은 클러스터 중심을 찾아내는 알고리즘이다.클러스터 중심과는 클래스 비밀산을 최소화하는 점이며, 바꾸어 말하면 클래스내의 각각의 데이터점과의 거리의 제곱화를 최소화하는 점이다.임의의 입력에 대해서 k-means의 진정한 해를 요구하는 문제는 NP 곤란한 문제이기 위해, 해의 근사가 잘 행해진다.그 손법은 Lloyd 알고리즘 또는 k-means 알고리즘으로 불려 많은 응용 분야에서 이용되고 있어 고속으로 근사해를 얻을 수 있다.

그러나, k-means법에는 2개의 이론적인 문제가 있다.

1. 1번째는, 최악 계산 시간은 입력 사이즈에 대해서 초다항식(super-polynomial)인 것.
2. 또 하나는, 근사해는 최적인 클러스터링 결과와 비교해 관계해 얼마든지 나빠지는 일이 있는 것.

이 k-means++법은 2번째의 문제의 해소를 목표로 한 수법이며, 표준적인 k-means법의 반복을 실시하기 전에 클러스터 중심을 초기화하는 프로세스를 실시한다.k-means++법의 초기화는, 최적인 k-means법의 해에 비해 O(log k)의 근사 비율로 해를 얻는 것이 보증되고 있는[³].

알고리즘

이 k-means++법은, 초기의 k개의 클러스터 중심은 가능한 한 떨어져 있는 편이 좋다고 하는 생각에 의거하고 있다.우선 시작해에 데이터점을 랜덤에 선택해 1번째의 클러스터 중심으로 해, 모든 데이터점과 그 최근옆의 클러스터 중심의 거리를 요구해 그 거리의 제곱에 비례한 확률로 클러스터 중심으로서 선택되지 않은 데이터점을 클러스터 중심으로서 랜덤에 선택한다.

알고리즘은 이하의 순서로 행해진다.

 데이터점으로부터 랜덤에 1개 선택 그것을 클러스터 중심으로 한다. while ${\displaystyle k}$ 개의 클러스터 중심이 선택될 때까지 do     각각의 데이터점${\displaystyle x}$ 에 관해서, 그 점의 최근옆중심과의 거리${\displaystyle D(x)}$ (을)를 계산한다.     데이터점${\displaystyle x}$ 에 관해서 중량감 다해 확률 분포 ${\displaystyle {\frac {D(x)^{2}}{\sum D(x)^{2}}}}$ (을)를 이용하고, 데이터점중에서 새로운 클러스터 중심을 랜덤에 선택한다. 선택된 클러스터 중심을 초기치로서 표준적인 k-means법을 실시한다. 

이 초기 가격결정의 방법은 k-means법을 현저하게 개선한다. 초기 가격결정에 불필요한 시간이 걸리지만, k-means법은 수습이 도저히 빨리 계산 시간은 그만큼 걸리지 않는다. 저자등은 이 수법을 실데이터와 인공 데이터의 양쪽 모두로 실험을 실시해, 대체로 수습 스피드에 관해서는 2배, 어느 데이터 세트로는 오차가 1000분의 1이 된 것을 보고하고 있다. 일련의 실험으로는 스테디셀러 k-means법으로 속도와 오차에 관해서 항상 우수하고 있었다.

거기에 더해 이 알고리즘의 근사율이 계산되고 있다.k-means++법은 평균적으로${\displaystyle O(\log k)}$ 의 근사 비율로 근사 가능하다라고 하는 것이 보증되고 있다.${\displaystyle k}$ (은)는 클러스터수이다.이것에 대해, 표준적인 k-means법으로는 최적치에 대해서 임의의 정도로 나빠지는 일이 있다.

소프트웨어

• ELKI
• GNU R
• OpenCV
• Weka
• CMU's GraphLab

관련 항목

• x-means법- k=2로 재귀적으로 k-means를 실시하는 방법.종료 조건은 베이즈 정보량 규준(BSI: Bayesian information criterion)으로 결정한다.

참고 문헌

1. ^ Arthur, D. and Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding". Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 1027–1035. http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf 
2. ^ Ostrovsky, R., Rabani, Y., Schulman, L. J. and Swamy, C. (2006). "The Effectiveness of Lloyd-Type Methods for the k-Means Problem". Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). IEEE. pp. 165□174 
3. ^"k-means++: The Advantages of Careful Seeding". 2013년 10월 20일 열람.

「https://ja.wikipedia.org/w/index.php? title=K-means%2 B%2 B법&oldid=56105390」으로부터 취득

This article is taken from the Japanese Wikipedia k-means++법

This article is distributed by cc-by-sa or GFDL license in accordance with the provisions of Wikipedia.

Wikipedia and Tranpedia does not guarantee the accuracy of this document. See our disclaimer for more information.

In addition, Tranpedia is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CC-BY-SA license information.